ما هي خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

إنّ نظام (GSP) خوارزمية مهمة جدًا في التنقيب عن البيانات، حيث يتم استخدامه في التنقيب التسلسلي من قواعد البيانات الكبيرة، كما تعتمد جميع خوارزميات التنقيب عن التسلسل تقريبًا بشكل أساسي على خوارزمية سابقة.

ما هي خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

خوارزمية تنقيب الأنماط المتسلسلة المعممة (GSP): هي طريقة تنقيب نمطية متسلسلة تم إنتاجها بواسطة (Srikant) و(Agrawal) في عام (1996م)، وهي امتداد لخوارزميتهم الأساسية لتنقيب مجموعة العناصر المعتادة والتي يشار إليها باسم (Apriori)، ويحتاج نظام (GSP) إلى طبيعة الإغلاق التنازلي للأنماط المتسلسلة ويتبنى نهجًا متعدد المسارات وإنشاء الطلب واختباره.

في الآونة الأخيرة نمت الرغبة في جمع البيانات وتحليلها، ويُعد ختم الوقت لمجموعة البيانات جزءًا مهمًا من التحليل واستخراج البيانات، حيث يمكن أن يوفر معلومات أكثر فائدة وتم تصميم تقنيات التعدين المختلفة لتنقيب بيانات السلاسل الزمنية والأنماط المتسلسلة، والتي تسعى إلى العلاقات بين حدوث الأحداث المتسلسلة والاكتشافات في حالة وجود أي ترتيب محدد للوقائع وتم اعتماد العديد من الخوارزميات لدراسة هذا النوع من البيانات بناءً على نهج (apriori)، بحيث تعتمد خوارزمية (GSP)على خوارزميات (Apriori).

ملاحظة:“GSP” هي اختصار لـ “Generalized Sequential Pattern”.

كيفية عمل خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

في المسح الأول لقاعدة البيانات يمكن اكتشاف بعض العناصر المتكررة أي تلك التي لديها الحد الأدنى من الدعم، حيث ينتج عن كل عنصر تسلسل متكرر لحدث واحد بما في ذلك هذا العنصر، وتبدأ كل تمريرة لاحقة بمجموعة أولية من الأنماط المتسلسلة ومجموعة الأنماط المتسلسلة الموجودة في التمريرة السابقة.

يمكن لمجموعة الأنماط الأولية هذه إنشاء أنماط جديدة من المحتمل أن تكون متكررة وتُعرف باسم التسلسلات المرشحة، حيث تتضمن كل سلسلة مرشحة عنصرًا واحدًا أكثر من النمط التسلسلي الأولي الذي تم إنشاؤه منه، حيث يمكن أن يتضمن كل حدث في النمط عنصرًا واحدًا أو عدة عناصر.

المثيلات المتعددة للعناصر في تسلسل هي ارتفاع التسلسل، لذلك سيكون لبعض التسلسلات المرشحة في ممر معين نفس الارتفاع ويحدد تسلسل بطول (k) كتسلسل (k)، وكما أنّ (C) تشير إلى مجموعة متواليات (k) المرشحة، حيث يكتشف التمرير فوق قاعدة البيانات الدعم لكل تسلسل (k) مرشح، والمرشحين في (C_k) مع الحد الأدنى من (min_sup) النموذج، و(L_k) هي مجموعة كل متواليات (k) المتكررة.

خطوات عمل خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

تتطور هذه المجموعة إلى مجموعة الأنماط للمرور التالي (k + 1)، حيث تزيل الخوارزمية عند عدم اكتشاف نمط تسلسلي جديد في مسار أو لا يمكن إنشاء تسلسل مرشح، ويستخدم (GSP) خاصية (Apriori) لتقصير مجموعة المرشحين على النحو التالي وفي التمرير (k) تكون السلسلة مرشحًا فقط، إذا كان كل من طولها (k −1) اللاحقة عبارة عن نمط تسلسلي تم اكتشافه عند التمرير (k −1).

يقوم مسح جديد لقاعدة البيانات بتجميع الدعم لكل تسلسل مرشح واكتشاف مجموعة جديدة من الأنماط المتسلسلة (L_k) وكما تتطور هذه المجموعة إلى بذرة للممر التالي، بحيث تزيل الخوارزمية عند عدم اكتشاف نمط تسلسلي في مسار أو عند عدم إنشاء تسلسل مرشح.

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

يوفر معرف الحدث كطابع زمني داخل تسلسل، حيث أنّ معرف الحدث لمجموعة العناصر (أو الحدث) في تسلسل هو (i) ويمكن أن تظهر مجموعة العناصر في أعلى من تسلسل واحد، كما تتحد مجموعة (معرف التسلسل ومعرف الحدث) لمجموعة عناصر معينة تشكل (ID_list) لمجموعة العناصر.

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

مبدأ خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

يستخدم نظام (GSP) نموذجًا على مستوى المستوى للعثور على جميع أنماط التسلسل في البيانات ويبدأ بإيجاد العناصر المتكررة بالحجم الأول ثم يمررها كمدخلات إلى التكرار التالي لخوارزمية (GSP)، كما يتم تمرير قاعدة البيانات عدة مرات لهذه الخوارزمية وفي كل تكرار يزيل نظام (GSP) جميع مجموعات العناصر غير المتكررة، ويتم ذلك بناءً على تردد عتبة يسمى “الدعم”.

يتم الاحتفاظ فقط بمجموعات العناصر التي يكون ترددها أكبر من عدد الدعم وبعد التمرير الأول يجد نظام (GSP) جميع التسلسلات المتكررة للطول (-1) والتي تسمى التسلسلات (1)، وهذا يجعل الإدخال إلى المسار التالي فهو مرشح لتسلسل (2) وفي نهاية هذا المرور يُنشئ نظام (GSP) كل التسلسلات الثنائية المتكررة، ممّا يجعل الإدخال للتسلسلات الثلاثية المرشحة ويتم استدعاء الخوارزمية بشكل متكرر حتى لا يتم العثور على مجموعات عناصر متكررة.

يعد التنقيب عن الأنماط المتسلسلة مشكلة مهمة في التنقيب عن البيانات ذات تطبيقات واسعة، وتكتشف خوارزمية (GSP) الأنماط المتسلسلة المعممة، ومع ذلك لا يزال نظام (GSP) يواجه مشكلات عندما تكون قاعدة بيانات التسلسل كبيرة أو عندما تكون الأنماط التسلسلية المراد استخراجها طويلة.

تكمل مصادر الخوارزمية (PrefixSpan) أنماطًا متسلسلة أسرع من نظام (GSP) لكنّها لا تستطيع تنقيب الأنماط المتسلسلة المعممة مع قيود الوقت أو النوافذ الزمنية أو التصنيف، وهي خوارزمية تتبع نهجًا تصاعديًا للعثور على أنماط متكررة، حيث في البداية يعتبر كل عنصر مرشحًا للطول (1)، وبناءً على الحد الأدنى من الدعم يتم تحديد التسلسلات المتكررة للطول (1) وباستخدام تجاهل التسلسلات الفائقة للتسلسلات النادرة ذات الطول (1) (Apriori Pruning)، ويتم إنشاء سلاسل فائقة بطول (2) كمرشحين.

أساسيات خوارزمية تنقيب الأنماط المتسلسلة المعممة GSP

1- التسلسل Sequence

يتم تعريف التسلسل رسميًا على أنه مجموعة العناصر المرتبة {s1، s2، s3،…، sn}، وكما يوحي الاسم إنّه تسلسل العناصر التي تحدث معًا ويمكن اعتبارها معاملة أو عناصر مشتراة معًا في سلة.

2- المجموعة الفرعية من التسلسل Subsequence

المجموعة الفرعية من التسلسل تسمى اللاحقة، وافترض أنّ {a، b، g، q، y، e، c} عبارة عن تسلسل يمكن أن تكون النتيجة التالية {a, b, c} أو {y, e}، كما أنّ ما يلي ليس بالضرورة للعناصر المتتالية من التسلسل ومن تسلسل قواعد البيانات يتم العثور على التسلسلات اللاحقة التي تم العثور على أنماط التسلسل (GSP) منها في النهاية.

3- نمط التسلسل

يسمى التسلسل الفرعي بالنمط عندما يتم العثور عليه في تسلسلات متعددة، والهدف من خوارزمية نظام (GSP) هو استخراج أنماط التسلسل من قاعدة البيانات الكبيرة، حيث تتكون قاعدة البيانات من التسلسلات وعندما يكون للتردد اللاحق تردد يساوي أكثر من قيمة “الدعم”.

طرق التنقيب المتسلسل للأنماط

1- المناهج المستندة إلى Apriori

• نظام (GSP).

• سبيد (SPADE).

2- المناهج المستندة إلى نمط النمو

• FreeSpan

• البادئة (PrefixSpan).