[ تمت الإجابة ]FP-Growth Algorithm

السلام عليكم

اقتباس

كل الروابط، التي أرفقها الأستاذ حسام (جزاه الله خير) موجوده لدي سلفا، بلغة c#, جافا، وc
وواجهت صعوبه في فهمها أما بسبب عدم خبرتي باللغات (جافا,c#) أو بسبب تعقيد البرنامج المكتوب بلغة c

 

لا بأس, هناك متطلبات يجب عليك معرفتها من أجل فهم الخوارزمية, مثل هياكل البيانات و خصوصا الأشجار (trees).

اقتباس

لم أذكر ذلك في ردي السابق على الأستاذ حسام لسببين

 

أتفهم جيدا ردك لكن بطبيعة الحال, نحن هنا في المنتدى بمثابة إخوة و لاتوجد بيننا حساسيات أو ما شابه و بالتالي إذا قدم لك أحد الأعضاء (بشكل عام) مساعدة لم تؤدي إلى حل مشكلتك فيمكنك بكل بساطة أن توضحي له (و لمن يقرأ الموضوع من بعده) الأشياء التي لم تفهميها بالتحديد حتى يعلم القارئ أن الموضوع لم تتم الإجابة عليه بعد.

بالنسبة لخوارزمية FP-growth فتُدْرَسُ في مادة Data Mining و بالتحديد عند البحث عن الـ Association Rules.

FP تمثل طريقة مختلفة عن تلك التي تتبعها خوارزمية Apriori حيث تسمح باستخراج الـ itemsets المتكررة بدون توليد الـ candidates.

تقوم FP-growth (Frequent Pattern growth)l بضغط قاعدة البيانات و جعلها على شكل compact structure تُعرف باسم FP-tree, ثم تقوم بتقسيم الـ Data Base و ضعطها مجددا إلى under projections تُسمى conditional databases.

كل projection تابع لـ item متكرر, استخراج itemsets المتكررة يتم عملها في كل projection على حدة.

الهيكل الذي يُمثل FP-tree يجب أن يحتوي على عنصرين أساسيين :

1. structure على شكل شجرة يُسمى جذرها (root) بـ null.
2. بالإضافة إلى index (مصفوفة من الـ pointers تُشير إلى العناصر المتكررة).

بالنسبة للشجرة فتتكون من جذر يُرمز له عادة بـ null بالإضافة إلى مجموعة من العقد تبدأ من الجذر. كل عقدة يتم تمثيلها بـ :

• Item-name : اسم العنصر.
• Count : عدد الـ transaction التي يظهر فيها جزء من المسار (portion of path) وصولا إلى العقدة الحالية.
• Node-link : مؤشر يُشير إلى العقدة الموالية التي تحمل نفس الـ item-name أو null إن لم توجد عقدة تحقق الشرط.

بالنسبة لـ index فهو عبارة عن جدول عناوين (header table) يحتوي على لائحة الـ items المتكررة, الجدول يخزن أو يُشير إلى أول ظهرو لكل عنصر.

الهدف من تمثيل كهذا هو معرفة الـ frequent associations التي يظهر فها العنصر المتكرر من خلال متابعة inter-nodes links.

لبناء الـ FP-Tree نتبع الخطاوت التالية :

1. نقوم بالمرور على عناصر الـ transaction database من أجل تحديد العناصر المتكررة بدلالة الـ minimum support threshold. هذه العناصر سيتم ترتيبها لاحقا حسب support-descending.
2. نقوم بالمرور مرة أخرى على تلك العناصر من أجل ترتيب كل transaction حسب ترتيب العناصر (items) بعد أن نقوم بإنشاء العقدة null. في نفس الوقت يتم إنشاء branching لكل transaction, جميع الـ transaction التي تملك نفس الـ prefix ستتقاسم بداية الفرع.أيضا إذا وجد two transactions متطابقتان سيتم تمثيلها في فرع واحد.

أرجو أن أكون قد أفدتك.

إذا كنت تجيدين الإنجليزية, أنصحك بقراءة المقالة التالية, ستفيدك كثيرا :

The LUCS-KDD Implementation of the FP-growth algorithm

تحياتي.