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

تم تقديم الاسم في عام 1994 من قِبَل Rakesh Agrawal and Ramakrishnan Srikant، ويَعترف "Apriori" بالمعرفة المسبقة بمجموعات العناصر المتكررة التي تستخدمها الخوارزمية في الحوسبة. تشغِّل الخوارزمية بتشغيل التكرارات على البيانات لتحديد مجموعات العناصر k، ما يعني أن عناصر k تتصاحب بشكل متكرر. ثم تستخدم مجموعات العناصر k لتحديد مجموعات عناصر k+1. تعتمد خوارزمية Apriori على فكرة أن إضافة عناصر إلى إحدى المجموعات التي تُشترى بشكل متكرر يمكن أن يجعلها أقل تكرارًا، وليس أكثر تكرارًا. تعتمد العملية على خاصية Apriori التي تنص على أنه إذا ظهرت مجموعة عناصر بشكل متكرر في مجموعة بيانات، فيجب أن تكون جميع مجموعاتها الفرعية متكررة أيضًا. على العكس من ذلك، إذا تم تحديد مجموعة عناصر على أنها نادرة، فستُعَد جميع مجموعاتها الفائقة نادرة كذلك.

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

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

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

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

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

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

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

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

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

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

$S\left(I_A\right)=\frac{Occ\left(I_A\right)}{TotalTransactions}$

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

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

$S\left(I_{Apples}\right)=\frac{250}{2000}=0.125$

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

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

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

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

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

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

$C(Apples,Bananas)=\frac{150}{250}=0.6$

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

$C(Bananas,Apples)=\frac{150}{500}=0.3$

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

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

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

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


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

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

$L(Apples,Bananas)=\frac{0.6}{0.125}=4.8$

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

$L(Bananas,Apples)=\frac{0.3}{0.25}=1.2$

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

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

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

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

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

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

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

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

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