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

قُدِّم اسم "أبريوري" في عام 1994 بواسطة راكيش أجراوال وراماكريشنان سريكانت (الرابط موجود خارج موقع ibm.com)، وهو اسم يعترف بالمعرفة المسبقة لمجموعات العناصر المتكررة التي تستخدمها الخوارزمية في الحساب. تقوم الخوارزمية بتشغيل التكرارات على البيانات لتحديد مجموعات العناصر k، ما يعني أن عناصر k تتصاحب بشكل متكرر. ثم تستخدم مجموعات العناصر k لتحديد مجموعات عناصر k+1. تعتمد خوارزمية أبريوري على فكرة أن إضافة عناصر إلى إحدى المجموعات التي تُشترى بشكل متكرر يمكن أن يجعلها أقل تكرارًا، وليس أكثر تكرارًا. تعتمد العملية على خاصية أبريوري التي تنص على أنه إذا ظهرت مجموعة عناصر بشكل متكرر في مجموعة بيانات، فيجب أن تكون جميع مجموعاتها الفرعية متكررة أيضًا. على العكس من ذلك، إذا حُدِّدت مجموعة عناصر على أنها نادرة، فستُعد جميع مجموعاتها الفائقة نادرة كذلك.

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

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

لقد دُمجت دالة أبريوري في العديد من لغات البرمجة الشائعة بما في ذلك Python وJava وR، ما يجعل من السهل دمج توليد قواعد الارتباط عالية الجودة إلى جانب مجموعات العناصر المتكررة في التطبيقات أو الأنظمة الحالية.

تعمل كل خطوة من الخطوات الرئيسية في خوارزمية أبريوري على تحديد مجموعات العناصر وجميع مجموعاتها الفائقة الممكنة بحثًا عن المجموعات الأكثر شيوعًا لإنشاء قواعد الارتباط.

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

باستخدام خاصية أبريوري، تجمع الخوارزمية مجموعات العناصر المتكررة لتكوين مجموعات عناصر أكبر. تُقلَّم تراكيب مجموعات العناصر الأكبر ذات الاحتمالية الأقل. ويقلل هذا من مساحة البحث ويجعل الحساب أكثر كفاءة.

تكرر الخوارزمية الخطوتين 1 و2 حتى يتم الإنشاء الشامل لجميع مجموعات العناصر المتكررة التي تلبي احتمال الحد المحدد. وينتج عن كل تكرار اقترانات أكثر تعقيدًا وشمولية في مجموعات العناصر.

بمجرد أن تنشئ أبريوري مجموعات العناصر، يمكن التحقيق في قوة الارتباطات والعلاقات التي أُنشأت.

تستخدم خوارزمية أبريوري مقاييس الدعم والثقة والرفع لتحديد معايير التشغيل الخاصة بها وتحسين كفاءة الأداء.

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

$S\left({\mathrm{خبير}}_{\mathrm{في}}\right)=\frac{OCC\left({\mathrm{خبير}}_{\mathrm{في}}\right)}{Tot\mathrm{في}LTr\mathrm{في}NS\mathrm{في}CtioNS}$

حيث يكون I_A هو العنصر A، وOcc(I_A) هو عدد مرات ورود العنصر A، وS(I_A) = دعم العنصر A

على سبيل المثال، في أحد متاجر البيع بالتجزئة، قد تتضمن 250 معاملة من أصل 2000 معاملة على مدار اليوم شراء التفاح. باستخدام الصيغة:

$S\left({\mathrm{خبير}}_{\mathrm{في}ppLES}\right)=\frac{250}{2000}=0.125$

تشير هذه النتيجة إلى وجود احتمال بنسبة 12.5% أن يكون قد تم شراء التفاح في ذلك اليوم.

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

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

$C(\mathrm{في},B)=\frac{OCC(\mathrm{في}\cap B)}{OCC\left(\mathrm{في}\right)}$

حيث A هو السابق، وB هو التالي، وC(A,B) هي الثقة بأن A يؤدي إلى B.

وبتوسيع نطاق المثال السابق، افترض أن هناك 150 معاملة تم فيها شراء التفاح والموز معًا. يتم احتساب الثقة على النحو التالي:

$C(\mathrm{في}ppLES,B\mathrm{في}N\mathrm{في}N\mathrm{في}S)=\frac{150}{250}=0.6$

تشير هذه النتيجة إلى احتمالية بنسبة 60% أن يؤدي شراء التفاح إلى شراء الموز. وبالمثل، بافتراض ما مجموعه 500 معاملة للموز، فإن الثقة في أن شراء الموز يؤدي إلى شراء التفاح يتم حسابه كالتالي:

$C(B\mathrm{في}N\mathrm{في}N\mathrm{في}S,\mathrm{في}ppLES)=\frac{150}{500}=3.0$

هنا، توجد احتمالية بنسبة 30% فقط أن يؤدي شراء الموز إلى شراء التفاح.

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

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

$L(\mathrm{في},B)=\frac{C(\mathrm{في},B)}{S\left(\mathrm{في}\right)}$ 


لما كان L_A,B هو الرفع للعنصر A المؤدي إلى العنصر B وC_A,B هي الثقة في أن العنصر A يؤدي إلى العنصر B، فإن S_A هو الدعم للعنصر A.

في المثال الوارد أعلاه، يمكننا أن نرى ما يلي: 

$L(\mathrm{في}ppLES,B\mathrm{في}N\mathrm{في}N\mathrm{في}S)=\frac{0.6}{0.125}=4.8$

تشير قيمة الرفع العالية إلى أن احتمالية شراء التفاح والموز معًا أعلى بمعدل 4.8 مرة من احتمالية شراء التفاح وحده. كما يمكن ملاحظة ما يلي: 

$L(B\mathrm{في}N\mathrm{في}N\mathrm{في}S,\mathrm{في}ppLES)=\frac{3.0}{0.25}=1.2$

تشير قيمة الرفع المنخفضة هنا إلى أن عملية شراء الموز التي تؤدي إلى شراء التفاح قد تكون مجرد مصادفة.

في كثير من الحالات، قد يكون تطبيق نهج القوة الغاشمة (الرابط موجود خارج موقع ibm.com) لاحتساب حدود الدعم والثقة لكل قاعدة ثم تقليم القواعد التي لا تلبي الحد الأدنى من الناحية الحسابية. ولزيادة كفاءة تطبيق خوارزمية أبريوري، غالبًا ما تُدمج مع تقنيات استخراج قواعد الارتباط الأخرى. اثنان من أكثر الطرق شيوعًا هما خوارزمية FP-growth (الرابط موجود خارج موقع ibm.com) ومتغيرها FP-Max لتقليل قيود الذاكرة والحوسبة. يمكن أيضًا دمج خوارزمية أبريوري مع شبكات القرارات، حيث تحدد خوارزمية أبريوري مجموعات العناصر المتكررة، وتساعد تقنية شبكة القرارات في تحديد قواعد الارتباط.

هناك متغير شائع آخر لخوارزمية أبريوري وهو العد الديناميكي لمجموعات العناصر (DIC) (الرابط موجود خارج موقع ibm.com) والذي يبدأ في عد مجموعات العناصر المحتملة مبكرًا، من دون انتظار تسجيل جميع المعاملات. يقسم العد الديناميكي لمجموعات العناصر (DIC) مجموعة البيانات إلى شرائح أصغر ويعالج كل جزء على حدة. يتيح هذا التقسيم التوقف المبكر عندما تكون الخوارزمية غير قادرة على تحديد أي عناصر متكررة، ولكن تقسيم البيانات يساعد أيضًا في تقليل تكلفة الحوسبة بشكل كبير.

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

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

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

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

كما يمكن تطبيق خوارزميات أبريوري في قواعد البيانات غير المتعلقة بالمعاملات. غالبًا ما يستخدم محللو البيانات خوارزميات أبريوري للتنقيب عن استخدام الويب، لتحليل بيانات تدفق النقرات، وتفسير سلوك المستخدمين.

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