استخراج الأنماط المتسلسلة

الموسوعة الحرة

يُعدّ استخراج الأنماط المتسلسلة فرعًا من فروع استخراج البيانات، ويهتمّ بإيجاد أنماط ذات دلالة إحصائية بين أمثلة البيانات التي تُقدّم قيمها في تسلسل. [ 1 ] [ 2 ] يُفترض عادةً أن القيم منفصلة، ​​وبالتالي يرتبط استخراج السلاسل الزمنية ارتباطًا وثيقًا به، ولكنه يُعتبر نشاطًا مختلفًا في الغالب. ويُعدّ استخراج الأنماط المتسلسلة حالة خاصة من استخراج البيانات المهيكلة .

تُعالج في هذا المجال عدة مشكلات حسابية تقليدية رئيسية، منها بناء قواعد بيانات وفهارس فعّالة لمعلومات التسلسل، واستخراج الأنماط المتكررة، ومقارنة التسلسلات لتحديد التشابه ، واستعادة عناصر التسلسل المفقودة. وبشكل عام، يمكن تصنيف مشكلات استخراج التسلسلات إلى استخراج السلاسل النصية ، الذي يعتمد عادةً على خوارزميات معالجة السلاسل النصية، واستخراج مجموعات العناصر ، الذي يعتمد عادةً على تعلم قواعد الارتباط . وتُوسّع نماذج العمليات المحلية [ 3 ] نطاق استخراج الأنماط التسلسلية ليشمل أنماطًا أكثر تعقيدًا، قد تتضمن خيارات (حصرية)، وحلقات، وبنى تزامنية، بالإضافة إلى بنية الترتيب التسلسلي.

استخراج الخيوط

يتعامل استخراج السلاسل عادةً مع مجموعة محدودة من الأحرف للعناصر التي تظهر في تسلسل ، ولكن قد يكون التسلسل نفسه طويلاً جدًا. ومن أمثلة هذه الأحرف: مجموعة أحرف ASCII المستخدمة في النصوص الطبيعية، وقواعد النيوكليوتيدات A وG وC وT في تسلسلات الحمض النووي DNA ، أو الأحماض الأمينية في تسلسلات البروتينات . في التطبيقات البيولوجية، يُمكن استخدام تحليل ترتيب الأحرف في السلاسل لفحص تسلسلات الجينات والبروتينات لتحديد خصائصها. إن معرفة تسلسل أحرف الحمض النووي DNA أو البروتين ليس غاية في حد ذاته، بل إن المهمة الرئيسية هي فهم التسلسل من حيث بنيته ووظيفته البيولوجية . ويتحقق ذلك عادةً بتحديد المناطق أو الوحدات البنائية الفردية داخل كل تسلسل، ثم إسناد وظيفة لكل وحدة بنائية. في كثير من الحالات، يتطلب ذلك مقارنة تسلسل معين بتسلسلات دُرست سابقًا. وتصبح المقارنة بين السلاسل معقدة عند حدوث إضافات أو حذف أو طفرات في السلسلة.

يقدم أبو الهدى وغانم (2010) مسحًا وتصنيفًا للخوارزميات الرئيسية لمقارنة التسلسلات في المعلوماتية الحيوية، والتي تشمل: [ 4 ]

  • المشاكل المتعلقة بالتكرار: التي تتعامل مع العمليات على التسلسلات الفردية ويمكن أن تستند إلى مطابقة السلسلة الدقيقة أو طرق مطابقة السلسلة التقريبية لإيجاد التكرارات ذات الطول الثابت المتفرق والتكرارات ذات الطول الأقصى، وإيجاد التكرارات المتتالية، وإيجاد التسلسلات الفرعية الفريدة والتسلسلات الفرعية المفقودة (غير المكتوبة).
  • مشاكل المحاذاة: هي تلك التي تتعامل مع مقارنة السلاسل النصية من خلال محاذاة تسلسل واحد أو أكثر أولاً؛ ومن الأمثلة على الطرق الشائعة BLAST لمقارنة تسلسل واحد مع عدة تسلسلات في قاعدة بيانات، و ClustalW للمحاذاة المتعددة. يمكن أن تعتمد خوارزميات المحاذاة على طرق دقيقة أو تقريبية، ويمكن تصنيفها أيضًا إلى محاذاة شاملة، ومحاذاة شبه شاملة، ومحاذاة محلية. انظر محاذاة التسلسل .

تعدين مجموعات العناصر

تُتيح بعض مسائل استخراج التسلسلات إمكانية اكتشاف مجموعات العناصر المتكررة وترتيب ظهورها، فعلى سبيل المثال، نسعى إلى إيجاد قواعد من نوع "إذا اشترى عميل سيارة، فمن المرجح أن يشتري تأمينًا خلال أسبوع واحد"، أو في سياق أسعار الأسهم، "إذا ارتفع سهم نوكيا وإريكسون، فمن المرجح أن يرتفع سهم موتورولا وسامسونج خلال يومين". يُستخدم استخراج مجموعات العناصر تقليديًا في تطبيقات التسويق لاكتشاف الأنماط المتكررة بين العناصر التي تظهر معًا في المعاملات الكبيرة. فعلى سبيل المثال، من خلال تحليل معاملات سلال التسوق للعملاء في أحد المتاجر الكبرى، يمكن استخلاص قاعدة تنص على أنه "إذا اشترى عميل البصل والبطاطس معًا، فمن المرجح أن يشتري أيضًا لحم الهامبرغر في نفس المعاملة".

يقدم هان وآخرون (2007) دراسة استقصائية وتصنيفًا للخوارزميات الرئيسية لاستخراج مجموعات العناصر. [ 5 ]

إن التقنيتين الشائعتين اللتين يتم تطبيقهما على قواعد بيانات التسلسل لاستخراج مجموعات العناصر المتكررة هما خوارزمية apriori المؤثرة وتقنية FP-growth الأحدث .

التطبيقات

مع تنوع المنتجات وسلوكيات الشراء لدى المستخدمين، تُعدّ رفوف العرض من أهم الموارد في قطاع التجزئة. فبإمكان تجار التجزئة زيادة أرباحهم وخفض التكاليف من خلال الإدارة الفعّالة لتخصيص مساحة الرفوف وعرض المنتجات. ولحلّ هذه المشكلة، اقترح جورج وبينو (2013) منهجًا لاستخراج أنماط شراء المستخدمين باستخدام خوارزمية PrefixSpan، ووضع المنتجات على الرفوف بناءً على ترتيب أنماط الشراء المستخرجة. [ 6 ]

الخوارزميات

تشمل الخوارزميات الشائعة الاستخدام ما يلي:

  • خوارزمية GSP
  • اكتشاف الأنماط المتسلسلة باستخدام فئات التكافؤ (SPADE)
  • فريسبان
  • نطاق البادئة
  • MAPres [ 7 ]
  • Seq2Pat (لاستخراج الأنماط التسلسلية القائمة على القيود) [ 8 ] [ 9 ]

انظر أيضاً

مراجع

  1. ↑ مبروكه، ن. ر.؛ إيزيف، س. إ. (2010). "تصنيف خوارزميات استخراج الأنماط المتسلسلة". مجلة ACM Computing Surveys . 43 : 1-41 . CiteSeerX 10.1.1.332.4745 . doi : 10.1145/1824795.1824798 . S2CID 207180619 .  
  2. ↑ بيتشيني، أ.؛ بوندييلي، أ.؛ ديل أوجليو، ب.؛ مارسيلوني، ف. (2023). "من المناهج الأساسية إلى التحديات والتطبيقات الجديدة في استخراج الأنماط المتسلسلة" . الحوسبة التطبيقية والذكاء . 3 (1): 44-78 . doi : 10.3934/aci.2023004 . hdl : 11568/1172332 .
  3. ^ الضرائب، ن. سيدوروفا، ن.؛ حكما، ر. فان دير آلست، ويل إم بي (2016). “التعدين نماذج العمليات المحلية”. مجلة الابتكار في النظم البيئية الرقمية . 3 (2): 183– 196. أرخايف : 1606.06066 . دوى : 10.1016/j.jides.2016.11.001 . S2CID 10872379 . 
  4. ↑ أبو الهدى، م.؛ غانم، م. (2010). "استخراج السلاسل النصية في المعلوماتية الحيوية". في جابر، م.م. (محرر). التنقيب العلمي عن البيانات واكتشاف المعرفة . سبرينغر. doi : 10.1007/978-3-642-02788-8_9 . ISBN 978-3-642-02787-1.
  5. ↑ هان، ج.؛ تشنغ، هـ.؛ شين، د.؛ يان، ش. (2007). "استخراج الأنماط المتكررة: الوضع الحالي والاتجاهات المستقبلية" . استخراج البيانات واكتشاف المعرفة . 15 (1): 55-86 . doi : 10.1007/s10618-006-0059-1 .
  6. ↑ جورج، أ.؛ بينو، د. (2013). "نهج لتحديد مواقع المنتجات في محلات السوبر ماركت باستخدام خوارزمية PrefixSpan" . مجلة جامعة الملك سعود - علوم الحاسب والمعلومات . 25 (1): 77-87 . doi : 10.1016/j.jksuci.2012.07.001 .
  7. ↑ أحمد، اشتياق؛ قاضي، وجاهات م.؛ خورشيد، أحمد؛ أحمد، منير؛ هوسلي، دانيال س.؛ خواجة، عفت؛ تشودري، م. إقبال؛ شكوري، عبد الرحيم؛ ناصر الدين (1 مايو 2008). "MAPRes: استخراج أنماط الارتباط بين بقايا الأحماض الأمينية المفضلة في جوار الأحماض الأمينية المستهدفة للتعديلات ما بعد الترجمة". علم البروتينات . 8 (10): 1954-1958 . doi : 10.1002/pmic.200700657 . PMID 18491291. S2CID 22362167 .  
  8. ↑ حسين نسب أ، فان هوف دبليو جيه، سير إيه إيه (2019). "استخراج الأنماط المتسلسلة القائمة على القيود باستخدام مخططات القرار" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 33 : 1495-1502 . arXiv : 1811.06086 . doi : 10.1609/aaai.v33i01.33011495 . S2CID 53427299 . 
  9. ↑ "Seq2Pat: مكتبة توليد الأنماط من التسلسل" . GitHub . 9 أبريل 2022.
  • يتضمن SPMF تطبيقات مفتوحة المصدر لـ GSP و PrefixSpan و SPADE و SPAM وغيرها الكثير.