تعلم قواعد الارتباط

☰ جدول المحتويات

نبذة تمهيدية
التعريف
مفاهيم مفيدة
الخوارزميات
- خوارزمية ابريوري
- خوارزمية ايلكات
المراجع
روابط خارجية
- الببليوغرافيات

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

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

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

التعريف

مثال لقاعدة بيانات تتكون من 5 معاملات و 5 مواد
معرف المعاملة	حليب	خبز	زبدة	بيرة	حفاضات
1	1	1	0	0	0
2	0	0	1	0	0
3	0	0	0	1	1
4	1	1	1	0	0
5	0	1	0	0	0

باتباع التعريف الأصلي المقدم من سوارمي، ليملينسكي واغراوال^[3]، يتم تعريف مشكلة التنقيب عن قواعد الارتباط على النحو التالي:

لتكن ي = {ي1، ي2، ي3 .. ي ن}

ولتكن د = {ت1، ت2، ت3... ت م}

كل معاملة في د لديها معرف معاملة فريد ويحتوي على مجموعة فرعية من العناصر في ي.

تُعرَّف القاعدة بما يلي:

$X\Rightarrow Y$ , حيث $X,Y\subseteq I$ .

في بحث سوارمي وزملاءه ^[3] يتم تعريف القاعدة فقط بين مجموعة وبين عنصر واحد، حيث تنطبق القاعدة س على أحد عناصر ي.

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

لتوضيح ذلك، نأخذ مثالًا صغيرًا من بيانات السوبر ماركت. مجموعة من العناصر هي ي = {حليب، خبز، بيرة، زبد، حفاظات} وفي الجدول، نرى قاعدة البيانات الصغيرة التي تحتوي على هذه العناصر، حيث تعني القيمة 1 في كل إدخال وجود العنصر في المعاملة المقابلة، وتمثل القيمة 0 عدم وجود عنصر في تلك المعاملة.

يمكن أن تكون قاعدة مثال للسوبر ماركت {زبد، خبز >> حليب} وهذا يعني أنه إذا تم شراء الزبد والخبز، فإن العملاء يمكن أن يشتروا الحليب أيضًا.

مفاهيم مفيدة

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

الدعم

الدعم هو مؤشر لمدى تكرار ظهور مجموعة العناصر في مجموعة من البيانات.

دعم س بالنسبة للمعاملات ت، يعرف بأنه نسبة المعاملات هـ في مجموعة البيانات التي تحتوي على مجموعة العناصر س.

الثقة

الثقة هي إشارة إلى عدد المرات التي وجدت فيها القاعدة صحيحة.

قيمة الثقة للقاعدة المتمثلة بـ س إلى ص، للمجموعة ت من المعاملات، هي نسبة المعاملات التي تحتوي س وتحتوي ص أيضاًَ.

الرفع

يعرف الرفع لقاعدة معينة بأنه بأنه حاصل ضرب قسمة الدعم لكل من س وص سوية، مقسوماً على [الدعم لـ س مضروباً في الدعم لـ ص]

إذا كان رفع القاعدة مساوياً لـ 1، فهذا يعني أن احتمالية حدوث العناصر السالفة والنتيجة مستقلة عن بعضها البعض. عندما يكون الحدثان مستقلين عن بعضهما البعض، فلا يمكن وضع قاعدة تتضمن هذين الحدثين.

إذا كان الرفع أكبر من 1 ، فذلك يتيح لنا معرفة الدرجة التي تعتمد عليها هاتان التكرارات على بعضها البعض، ويجعل هذه القواعد مفيدة للتنبؤ بالنتيجة في مجموعات البيانات المستقبلية.

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

قيمة الرفع تأخذ بنظر الاعتبار دعم القاعدة وإجمالي ما تحتويه مجموعة البيانات^[4].

الخوارزميات

تم اقتراح العديد من الخوارزميات لتكوين قواعد الارتباط.

بعض الخوارزميات معروفة جداً مثل ابريوري و Eclat و FP-Growth، لكنها تؤدي نصف المهمة فقط، لأنها خوارزميات لاستخراج مجموعات العناصر المتكررة. ثم يجب القيام بخطوة أخرى بعدها لإنشاء قواعد من العناصر المتكررة الموجودة في قاعدة البيانات.

خوارزمية ابريوري

تستخدم ابريوري^[5] استراتيجية بحث أولية واسعة لحساب دعم مجموعات العناصر وتستخدم دالة لتوليد المجاميع المرشحة تستغل خاصية الإغلاق الهابط التي يمتاز بها الدعم.

خوارزمية ايلكات

ايلكات^[6] هي خوارزمية بحث أول عمق تعتمد على تقاطع مجموعة. إنها مناسبة للتنفيذ المتسلسل والتوازي مع خصائص تحسين الموقع. ^[7] ^[8]

المراجع

Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
"How Does Association Learning Work?". deepai.org. مؤرشف من الأصل في 17 فبراير 2019.
Agrawal, R.; Imieliński, T.; Swami, A. (1993). "Mining association rules between sets of items in large databases". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. صفحة 207. doi:10.1145/170035.170072. .
Hahsler, Michael (2005). "Introduction to arules – A computational environment for mining association rules and frequent item sets" ( كتاب إلكتروني PDF ). Journal of Statistical Software. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 30 أبريل 2019.
Agrawal, Rakesh; and Srikant, Ramakrishnan; Fast algorithms for mining association rules in large databases, in Bocca, Jorge B.; Jarke, Matthias; and Zaniolo, Carlo; editors, Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), Santiago, Chile, September 1994, pages 487-499 نسخة محفوظة 30 نوفمبر 2016 على موقع واي باك مشين.
Zaki, M. J. (2000). "Scalable algorithms for association mining". IEEE Transactions on Knowledge and Data Engineering. 12 (3): 372–390. doi:10.1109/69.846291.
Zaki, Mohammed Javeed; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). "New Algorithms for Fast Discovery of Association Rules": 283–286.
Zaki, Mohammed J.; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). Data Mining and Knowledge Discovery. 1 (4): 343–373. doi:10.1023/A:1009773317876.