خوارزمية Apriori

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

خوارزمية Apriori [ 1 ] هي خوارزمية لاستخراج مجموعات العناصر المتكررة وتعلم قواعد الارتباط في قواعد البيانات العلائقية . تعمل هذه الخوارزمية عن طريق تحديد العناصر الفردية المتكررة في قاعدة البيانات، ثم توسيعها لتشمل مجموعات عناصر أكبر فأكبر كلما زاد تكرار ظهور هذه المجموعات في قاعدة البيانات. يمكن استخدام مجموعات العناصر المتكررة التي تحددها Apriori لتحديد قواعد الارتباط التي تُبرز الاتجاهات العامة في قاعدة البيانات ، وهذا له تطبيقات في مجالات مثل تحليل سلة التسوق .

ملخص

اقترح أغراوال وسريكانت خوارزمية Apriori عام 1994. صُممت Apriori للعمل على قواعد البيانات التي تحتوي على معاملات (مثل مجموعات المنتجات التي اشتراها العملاء، أو تفاصيل زيارات موقع ويب، أو عناوين IP [ 2 ] ). صُممت خوارزميات أخرى لإيجاد قواعد الارتباط في البيانات التي لا تحتوي على معاملات ( مثل Winepi وMinepi)، أو التي لا تحتوي على طوابع زمنية ( مثل تسلسل الحمض النووي ). تُعتبر كل معاملة مجموعة من العناصر ( مجموعة عناصر ). عند تحديد عتبة معينة،ج{\displaystyle C}تحدد خوارزمية Apriori مجموعات العناصر التي هي مجموعات فرعية من على الأقلج{\displaystyle C}المعاملات في قاعدة البيانات.

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

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

يُقدّم أدناه رمز زائف للخوارزمية لقاعدة بيانات المعاملاتتي{\displaystyle T}وعتبة دعم قدرهاε{\displaystyle \varepsilon }يتم استخدام الترميز المعتاد لنظرية المجموعات، مع ملاحظة أنتي{\displaystyle T}هي مجموعة متعددة .جك{\displaystyle C_{k}}هل تم تحديد المرشح للمستوىك{\displaystyle k}في كل خطوة، يُفترض أن تقوم الخوارزمية بتوليد مجموعات المرشحين من مجموعات العناصر الكبيرة للمستوى السابق، مع مراعاة نظرية الإغلاق التنازلي.جouنت[ج]{\displaystyle \mathrm {count} [c]}يصل إلى حقل من بنية البيانات يمثل مجموعة المرشحينج{\displaystyle c}، والتي يُفترض مبدئيًا أنها تساوي صفرًا. تم حذف العديد من التفاصيل أدناه، وعادةً ما يكون الجزء الأكثر أهمية في التنفيذ هو بنية البيانات المستخدمة لتخزين مجموعات المرشحين، وحساب تردداتها.

Apriori (T, ε) L 1 ← {مجموعات العناصر الفردية الكبيرة} k ← 2 بينما L k−1 ليس فارغًا C k ← Generate_candidates(L k−1 , k) for transactions t in T D t ← {c in C k : c ⊆ t} للمرشحين c في D t count[c] ← count[c] + 1 L k ← {c in C k : count[c] ≥ ε} k ← k + 1 أعد اتحاد (L k ) على جميع k توليد_المرشحين (L، k) النتيجة ← مجموعة فارغة() لكل p ∈ L، q ∈ L حيث يختلف p و q في عنصر واحد فقط ج ← ف ∪ ق إذا كان u ∈ L لكل u ⊆ c حيث |u| = k-1 result.add(c) إرجاع النتيجة

أمثلة

المثال 1

لنفترض قاعدة البيانات التالية، حيث يمثل كل صف معاملة، وتمثل كل خلية عنصرًا فرديًا من عناصر المعاملة:

αβε
αβθ
αβε
αβθ

قواعد الارتباط التي يمكن تحديدها من قاعدة البيانات هذه هي التالية:

  1. تحتوي جميع المجموعات التي تحتوي على α على β أيضًا
  2. 50% من المجموعات التي تحتوي على α و β تحتوي أيضًا على ε
  3. 50% من المجموعات التي تحتوي على α و β تحتوي أيضًا على θ

ويمكننا أيضاً توضيح ذلك من خلال مجموعة متنوعة من الأمثلة.

المثال 2

لنفترض أن سلسلة متاجر كبيرة تتتبع بيانات المبيعات حسب وحدة حفظ المخزون (SKU) لكل صنف: كل صنف، مثل "الزبدة" أو "الخبز"، يُعرَّف برقم SKU. تمتلك السلسلة قاعدة بيانات للمعاملات، حيث تمثل كل معاملة مجموعة من وحدات SKU التي تم شراؤها معًا.

لنفترض أن قاعدة بيانات المعاملات تتكون من مجموعات العناصر التالية:

مجموعات العناصر
{1,2,3,4}
{1,2,4}
{1,2}
{2، 3، 4}
{2,3}
{3,4}
{2,4}

سنستخدم خوارزمية Apriori لتحديد مجموعات العناصر المتكررة في قاعدة البيانات هذه. وللقيام بذلك، سنعتبر مجموعة العناصر متكررة إذا ظهرت في 3 معاملات على الأقل في قاعدة البيانات: القيمة 3 هي عتبة الدعم .

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

غرضيدعم
{1}3
{2}6
{3}4
{4}5

جميع مجموعات العناصر ذات الحجم 1 لها دعم لا يقل عن 3، لذا فهي جميعها متكررة.

الخطوة التالية هي إنشاء قائمة بجميع أزواج العناصر المتكررة.

على سبيل المثال، فيما يتعلق بالزوج {1،2}: يُظهر الجدول الأول من المثال 2 ظهور العنصرين 1 و2 معًا في ثلاثة من مجموعات العناصر؛ لذلك، نقول إن العنصر {1،2} له دعم ثلاثة.

غرضيدعم
{1,2}3
{1,3}1
{1,4}2
{2,3}3
{2,4}4
{3,4}3

الأزواج {1,2}، {2,3}، {2,4}، و{3,4} جميعها تحقق أو تتجاوز الحد الأدنى للدعم وهو 3، لذا فهي متكررة. أما الزوجان {1,3} و{1,4} فليسا متكررين. ولأن {1,3} و{1,4} ليسا متكررين، فإن أي مجموعة أكبر تحتوي على {1,3} أو {1,4} لا يمكن أن تكون متكررة. وبهذه الطريقة، يمكننا تقليص المجموعات: سنبحث الآن عن الثلاثيات المتكررة في قاعدة البيانات، ولكن يمكننا بالفعل استبعاد جميع الثلاثيات التي تحتوي على أحد هذين الزوجين.

غرضيدعم
{2، 3، 4}2

في المثال، لا توجد ثلاثيات متكررة. المجموعة {2، 3، 4} أقل من الحد الأدنى، وتم استبعاد الثلاثيات الأخرى لأنها مجموعات فائقة من أزواج كانت بالفعل أقل من الحد الأدنى.

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

القيود

على الرغم من أهميتها التاريخية، تعاني خوارزمية Apriori من عدد من أوجه القصور أو المفاضلات، مما أدى إلى ظهور خوارزميات أخرى. تُنتج عملية توليد المرشحين أعدادًا كبيرة من المجموعات الفرعية (تحاول الخوارزمية تحميل مجموعة المرشحين بأكبر عدد ممكن من المجموعات الفرعية قبل كل مسح لقاعدة البيانات). ولا يجد استكشاف المجموعات الفرعية من الأسفل إلى الأعلى (وهو في الأساس اجتياز عرضي لشبكة المجموعات الفرعية) أي مجموعة فرعية قصوى S إلا بعد كل...2|S|-1{\displaystyle 2^{|S|}-1}من مجموعاتها الفرعية المناسبة.

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

كما أن تعقيد الوقت والمساحة لهذه الخوارزمية مرتفع للغاية:يا(2|د|){\displaystyle O\left(2^{|D|}\right)}وبالتالي، أسية، حيث|د|{\displaystyle |D|}يمثل العرض الأفقي (إجمالي عدد العناصر) الموجودة في قاعدة البيانات.

تحاول الخوارزميات اللاحقة مثل Max-Miner [ 3 ] تحديد مجموعات العناصر المتكررة القصوى دون تعداد مجموعاتها الفرعية، وتقوم بتنفيذ "قفزات" في مساحة البحث بدلاً من اتباع نهج تصاعدي بحت.

مراجع

  1. ↑ راكيش أغراوال وراماكريشنان سريكانت. خوارزميات سريعة لاستخراج قواعد الارتباط . وقائع المؤتمر الدولي العشرين حول قواعد البيانات الكبيرة جدًا، VLDB، الصفحات 487-499، سانتياغو، تشيلي، سبتمبر 1994.
  2. ↑ علم البيانات وراء مطابقة عناوين IP ، نُشر بواسطة deductive.com، 6 سبتمبر 2018، تم الاطلاع عليه في 7 سبتمبر 2018
  3. ↑ بايارو الابن، روبرتو ج. (1998). "استخراج الأنماط الطويلة من قواعد البيانات بكفاءة" (ملف PDF) . سجل ACM SIGMOD . 27 (2): 85-93 . doi : 10.1145/276305.276313 .
  • ARtool ، تطبيق GPL Java لاستخراج قواعد الارتباط مع واجهة مستخدم رسومية، يقدم تطبيقات لخوارزميات متعددة لاكتشاف الأنماط المتكررة واستخراج قواعد الارتباط (بما في ذلك Apriori).
  • يقدم SPMF تطبيقات مفتوحة المصدر بلغة Java لخوارزمية Apriori والعديد من الاختلافات مثل AprioriClose و UApriori و AprioriInverse و AprioriRare و MSApriori و AprioriTID وخوارزميات أخرى أكثر كفاءة مثل FPGrowth و LCM.
  • يُقدّم كريستيان بورغلت تطبيقات بلغة C لخوارزمية Apriori والعديد من خوارزميات استخراج الأنماط المتكررة الأخرى (مثل Eclat وFPGrowth وغيرها). ويتم توزيع الكود كبرنامج مجاني بموجب ترخيص MIT .
  • تحتوي حزمة R المسماة arules على Apriori و Eclat وبنية تحتية لتمثيل ومعالجة وتحليل بيانات وأنماط المعاملات.
  • Efficient-Apriori هي حزمة بايثون تتضمن تطبيقًا للخوارزمية كما هو موضح في الورقة الأصلية.