فهم (النمط المتكرر) خوارزمية نمو FP | ما هي خوارزمية FP؟

لفهم خوارزمية FP Growth، نحتاج أولاً إلى فهم قواعد الارتباط.

تكشف قواعد الاقتران عن العلاقة بين سمتين أو أكثر. هو أساسا في شكل – إذا كانت سابقة من اللاحقة. 

على سبيل المثال، يرى أحد المتاجر الكبرى أن هناك 200 عميل مساء يوم الجمعة. 

من بين 200 عميل، 100 عميل اشترى دجاجًا، ومن بين 100 عميل اشتروا دجاجًا، 50 عميلًا اشترى بصلًا. وبالتالي، فإن قاعدة الارتباط ستكون: إذا اشترى العملاء الدجاج، فاشتروا البصل أيضًا، بدعم 50/200 = 25% وثقة 50/100 = 50%.

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

1. العثور على Itemsets المتكررة
2. إنشاء قواعد ارتباط قوية من مجموعات العناصر المتكررة

العثور على مجموعات العناصر المتكررة

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

تقوم خوارزمية Apriori بإنشاء كافة مجموعات العناصر عن طريق مسح قاعدة بيانات المعاملات الكاملة. 

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

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

لذلك سيقتصر موضوع المناقشة على خوارزمية نمو FP في هذا المنشور. 

1. بناء شجرة FP عن طريق ضغط قاعدة البيانات التي تمثل العناصر المتكررة

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

لذلك دعونا نبدأ ببيانات المعاملات الصغيرة لفهم بناء شجرة FP. نفترض أن المعاملة التي نعتبرها هنا تتكون من 5 عناصر مثل-

الهليون (أ)، الذرة (ج)، الفاصوليا (ب)، الطماطم (ت) والقرع (ص)

الجدول 1

على سبيل المثال، بالنسبة للمعاملة الأولى، يتكون T1 من ثلاثة عناصر مثل الفاصوليا (B)، والهليون (A)، والطماطم (T). وبالمثل، تحتوي المعاملة T6 على العناصر الهليون (A) والاسكواش (S). 

دعونا نعتبر أيضًا أن الحد الأدنى لدعم بيانات المعاملات الصغيرة هذه هو 2. وبالتالي، min_support = 2.

أولاً، نحتاج إلى إنشاء جدول بأعداد العناصر في قاعدة بيانات المعاملات بأكملها على النحو التالي:

الجدول 2

هذا ببساطة هو عدد كل عنصر، كما لو أننا نرى أن الإسكواش (S) قد تم شراؤه في 6 معاملات، أي T3 وT5 وT6 وT7 وT8 وT9، وبالتالي فإن عدد الدعم هو 6 للاسكواش.

بعد ذلك، نحتاج فقط إلى فرز قائمة العناصر بترتيب تنازلي لعدد الدعم الخاص بها. 

ومن ثم قد يكون جدول عدد الدعم الآن كما هو موضح في الجدول 3 أدناه:

الجدول 3

الفاصوليا (ب) والاسكواش (س) لهما نفس عدد الدعم وهو 6 ويمكن كتابة أي منهما أولاً. لقد كتبنا هنا الفاصوليا (B) أولاً. وبالمثل، يمكن أيضًا إدراج الذرة (C) والطماطم بنفس الطريقة.

نحن الآن على استعداد للبدء في بناء شجرة FP. عادةً ما يتم تمثيل عقدة جذر شجرة FP بعقدة جذر NULL.

 الآن فكر في المعاملة T1. يتكون T1 من الفاصوليا (B)، والهليون (A)، والطماطم (T). الآن من بين هذه العناصر الثلاثة، نحتاج إلى البحث عن العنصر الذي يحتوي على الحد الأقصى لعدد الدعم.

 نظرًا لأن الهليون (A) يتمتع بأعلى عدد دعم يبلغ 7، فسنقوم بتمديد الشجرة من عقدة الجذر إلى A مثل الهليون. وبما أن هذه هي المعاملة الأولى، تتم الإشارة إلى العدد بالرمز A:1. 

دعونا ننظر أبعد، من بين الفاصوليا (B) والطماطم (T)، عدد الدعم للفاصوليا هو 6، وعدد الدعم للطماطم هو 2.

من الهليون، يمكننا تمديد الشجرة إلى الفاصوليا (B:1 للمعاملة الأولى تتكون من الفول) وبعد ذلك T:1 للطماطم. هيكل الشجرة كما هو موضح في الشكل 1.

بالمضي قدمًا في المعاملة T2، هناك عنصران هما الهليون (A) والذرة (C). نظرًا لأن عدد الدعم للهليون هو 7 والذرة (C) هو 2، فنحن بحاجة إلى النظر في الهليون (A) أولاً والانتقال من العقدة الجذرية نحتاج إلى معرفة ما إذا كان هناك أي فرع يمتد إلى الهليون (A) وهو صحيح في هذه الحالة، ويمكننا زيادة العدد إلى A:2 (الشكل 2). 

ولكن بعد ذلك، لا توجد عقدة متصلة بالهليون (A) بالذرة (C) نحتاج إلى إنشاء فرع آخر للذرة مثل C:1.

وبالمثل، بالنسبة للمعاملة T3، لدينا الهليون (A) ثم الاسكواش (S) بالترتيب التنازلي لعدد الدعم الخاص بهم. 

لذلك تمت زيادة عدد الهليون (A) من A:2 إلى A:3، علاوة على ذلك، يمكننا أن نرى أنه لا توجد أي عقد للاسكواش من الهليون، لذلك نحتاج إلى إنشاء فرع آخر لعقدة الاسكواش S: 1، كما هو موضح في الشكل 3.

بالنسبة للمعاملة 4، يمكننا رسم العقدة كما هو موضح أدناه في الشكل 4. هنا تمت زيادة عدد الهليون والفاصوليا إلى A:4 وB:2، ولكن بعد ذلك، يمكننا أن نرى أنه لا يوجد أي فرع يمتد إلى الذرة (C)، لذلك نحن بحاجة إلى إنشاء عقدة لـ C:1.

بالنسبة للمعاملة 5، يمكننا أن نرى أنها تحتوي على Beans (B) وSquash (S)، ولكن لا توجد أي عقدة مباشرة مرتبطة بالفاصوليا من العقدة الجذرية Null، نحتاج إلى إنشاء فرع جديد من العقدة Null كما هو موضح في الشكل 5 مع التهم B:1 وS:1.

المعاملة من 6 إلى المعاملة 10 لا تحتاج إلى شرح. للرجوع إليها، تم تقديم الأرقام لكل معاملة. لذا، بالنسبة للمعاملة 6، تحقق من الشكل 6، وبالنسبة للمعاملة 7، تحقق من الشكل 7، وما إلى ذلك. 

يمكننا الآن التحقق من صحة البيانات باستخدام الشكل 9 والجدول 3. يبلغ عدد الهليون (A) A:7، وهو ما يشبه الجدول 3. إذا تحققنا من Beans، فهناك عقدتان B:4 وB:2 ومن ثم، فإن العدد يتطابق مع عدد الفاصوليا 6 في الجدول 3.

2. ضغط قاعدة البيانات الشرطية

نحن الآن بحاجة إلى إنشاء جدول لقاعدة النمط الشرطي وبالتالي توليد النمط المتكرر. الآن دعونا ننظر إلى الجدول في الشكل 10، نحتاج إلى النظر في العنصر الذي لديه أقل عدد دعم، هنا، الطماطم (T) لديها أقل عدد دعم وهو 2.

نحن بحاجة إلى معرفة مكان وجود الطماطم. يمكننا أن نرى أن هناك مسارين لعبور الطماطم (T) من العقدة الجذرية. واحد منهم هو ABT، حيث T له عدد 1، أي T:1. حتى نتمكن من إنشاء قاعدة النمط الشرطي كما في الصف 1 من الجدول 4 {أ، ب:1}.

أيضًا، مسار الاجتياز الثاني هو ABST وT له عدد 1 (T:1) لذا فإن قاعدة النمط الشرطي هي {A, B, S;1}. 

إذن هناك قاعدتان للنمط الشرطي {{A,B:1},{A,B,S:1}}.

 الآن من هذا، سنقوم ببناء عمود شجرة FP الشرطي في الجدول 4. هنا A موجود في {A,B:1} و{A,B,S:1} بحيث يكون لكل منهما عدد نهائي قدره 1 ويصل مجموع كل منهما إلى < A:2>، وبطريقة مماثلة <B:2> و<S:1> أخيرًا يصبح <A:2,B:2, S:1>، لكننا لن نأخذ S:1 في الاعتبار لأننا لقد أخذنا الحد الأدنى لعدد الدعم ليكون 2.

لذا أخيرًا يجب أن تكون القيمة <A:2, B:2> للصف الأول، أي الطماطم (T).

الآن لإنشاء إنشاء النمط المتكرر (العمود الأخير في الجدول 4) نحتاج إلى ربط عمود شجرة FP الشرطي مع العنصر في الجدول 4.

الانضمام إلى <A:2> مع الطماطم (T) يمكننا كتابة {A,T:2}، بعد ذلك قم بربط <B:2> بالطماطم (T) فينتج {B,T:2}. ثم نحتاج إلى ربط A وB مع T ومن ثم {A,B,T:2} بحيث يصبح توليد النمط المتكرر لصف الطماطم (T) {A,T:2} ,{B,T:2}، {أ، ب، ت: 2}.

هنا يكون لكل من A وB عدد 2 لذلك كتبنا {A, B, T:2}، ولكن في بعض الأحيان قد تنشأ الحالة أن وB لهما أعداد مختلفة، في هذه الحالة، نحتاج إلى النظر في الحد الأدنى لعدد العنصر والكتابة بنفس الطريقة.

الآن بالنسبة لصفوف الذرة (C)، يمكننا أن نرى في الشكل 10 أنه يمكننا الوصول إلى الذرة (C) من خلال مسارين مختلفين ABC وAC. في كلا مساري الاجتياز، يكون عدد الذرة (C) هو 1.

وبالتالي، {{A,B:1} ,{A:1}} هي قاعدة النمط الشرطي. الآن بالنسبة لعمود شجرة FP الشرطية، نحتاج إلى التحقق من عدد كل عنصر في قاعدة النمط الشرطي، لأن لدينا 2 كحساب لـ و1 كحساب لـ B. نظرًا لأن الحد الأدنى لعدد الدعم الذي أخذناه في الاعتبار هو 2، نحتاج إلى إهمال B. لذا فإن أعمدة شجرة FP الشرطية تكون <A:2>. بعد ذلك، قم بربط عمود شجرة FP الشرطي بعمود العنصر للذرة (C) والذي يصبح {A, C:2}

الآن فكر في صف الاسكواش (S). يمكننا الوصول إلى لعبة الإسكواش من خلال 3 مسارات اجتياز ABS وAS وBS. 

بما أن عدد الاسكواش هو 2 في ABS يمكننا كتابة {A,B:2} بالمثل، بالنسبة للمسارين الآخرين يمكننا كتابة {A;2} & {B:2} وبالتالي فإن قاعدة النمط الشرطي تقف عند {{A، ب:2}، {أ:2}، {ب:2}}.

 بالنسبة لأعمدة شجرة FP الشرطية، يمكننا أن نرى أنه تم الوصول إلى <B:2> من الفرع الأيمن من العقدة Null والاثنان الآخران من خلال الفرع الأيسر المنشأ من الجذر Null.

ومن ثم، علينا أن نكتب بشكل مختلف وليس إضافة واحد، يمكننا أن نكتب <A:4, B:2>,<B:2>. الآن ضم A:4 من <A:4,B:2> مع الاسكواش (S) يعطي {A,S:4}. الآن من <A:4,B:2> الانضمام إلى Squash (S) يعطي} ،{B,S:2} ولكننا كتبنا {B,S:4}. لقد كتبنا {B, S:4} العدد كـ 4 نظرًا لأن لدينا <B:2> آخر في عمود شجرة FP الشرطية. 

جمع كل من B مع S من <A:4,B:2> وB مع S من <B:2> يصبح العدد {B,S:4}. الآن بربط <A:4,B:2> مع S (الربط النهائي لجميع العناصر) نحصل على {A,B,S:2} وليس {A,B,S:4} لأننا بحاجة إلى مراعاة الحد الأدنى للعدد الذي هو 2.

أخذ الحد الأدنى من العدد مطلوب لأننا نحتاج إلى التحقق من الأعداد المتكررة حيث يحدث كل من A وB مع S وليس فقط عنصر واحد. هذه العناصر الثلاثة الهليون (أ)، الفاصوليا (ب)، 

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

الجدول 4

إنشاء قواعد ارتباط قوية من مجموعات العناصر المتكررة

كما تمت مناقشته سابقًا، فإن نمو FP يولد قواعد ارتباط قوية باستخدام الحد الأدنى من الدعم الذي يحدده المستخدم، وما فعلناه حتى الآن هو الوصول إلى الجدول 4 باستخدام الحد الأدنى للعدد = 2 وأخيرًا تم إنشاء مجموعات عناصر متكررة والتي هي في الأخير عمود إنشاء الأنماط المتكررة في الجدول 4.

لذا، بالنظر إلى العمود الأخير في الجدول 4 الخاص بإنشاء الأنماط المتكررة، فقد أنشأنا مجموعة متكررة مكونة من 3 عناصر مثل {A,B,T:2} & A,B,S:2}. 

وبالمثل، المجموعات المتكررة المكونة من عنصرين هي {A,T:2}، {B,T:2}، {A,C:2}، {A,S:4}، {B,S:4} & {A, ب:4). كما يمكننا أن نرى أننا وصلنا إلى مجموعات متميزة.

 لا شيء من المجموعات متشابهة في هذه القضية. 

بالمقارنة مع خوارزمية Apriori، قمنا بإنشاء الأنماط المتكررة فقط في مجموعات العناصر بدلاً من جميع مجموعات العناصر المختلفة. 

على سبيل المثال، لم نقم هنا بإنشاء الطماطم (T) والقرع (S) أو الذرة (C) والفاصوليا (B) حيث لا يتم شراؤها معًا في كثير من الأحيان، وهو الجوهر الرئيسي وراء معايير قواعد الارتباط وخوارزمية نمو FP. 

المصدر: mygreatlearning

قد يهمك:

أفضل استضافة مواقع

أفضل استضافة ووردبريس

قوالب ووردبريس

سيرفر بيع متابعين

ما هو الذكاء الاصطناعي

ما هو شات جي بي تي

ما هو التسويق الإلكتروني

دعم سناب شات