DM_Lect_3_Associations_(FP_Growth)_-_video_-_03-11-2020
السلام عليكم، دي حتبقي المحاضرة التالتة في الـ data في course الـ data mining إن شاء الله، هو إحنا المرة اللي فاتت كنا ابتدئينا نتكلم عن الـ association rules والنهاردة حنكمل بقية كلامنا على الـ association rules بردو وحناخد algorithms تانية للـ generation بتاعة الـ association rules.زي ما قلنا المرة اللي فاتت والمحاضرة الأولانية إن إحنا
عندنا الـ data mining techniques اللي إحنا حنتكلم فيها في ال course دا مقسومة تلاتة categories، الـ frequent patterns mining والـ clustering والـ classification. فإحنا حنبدأ ال course بالـ frequent patterns mining ودا اللي إحنا ابتدئينا فيه المرة اللي فاتت وابتدئينا بأول حاجة في الـ frequent patterns mining اللي هي الـ association rules.
وقلنا إن الـ association rules بتتعامل مع اللي إحنا بنقول عليها الـ transactional database، اللي هو الشكل اللي موجود قدامنا دا.
اللي هو عبارة عن إن أنا عندي IDs للـ transactions لكل transaction بتحصل في الـ system ومع الـ ID بتاع الـ transaction دي الـ items اللي موجودة جوه الـ transaction دي. تمام؟ وزي ما قلنا الـ items دي مش لازم تكون زي ما هي موجودة قدامنا كدا اللي هي market basket data، ممكن تكون أي حاجة
تانية ممكن تكون applications الناس بتعملها download ممكن تكون pages الناس بتدخل عليها ممكن تكون أي نوع من الـ data يعني بس لازم تكون بالـ format اللي إحنا قايلينه هنا دا. والهدف من الـ algorithms اللي بتطلع الـ association rules دي إنها تطلع rules بالـ format اللي هنا دا اللي هو if X then Y.
وقلنا إن X و Y دول مش لازم يكونوا single items لكن ممكن يكونوا itemsets. فممكن أقول مثلاً إن هي مثلاً لو في الـ database اللي قدامنا دي فممكن أقول مثلاً if bread and milk then coffee مثلاً، فيبقى أي عدد من الـ items موجود في X جوه X أو Y.وقلنا إن إحنا عندنا two parameters علشان نحكم على الـ quality بتاعة الـ rule أو نقول إن الـ rule دي كويسة أو لأ.
اللي هم الـ support والـ confidence. قلنا الـ support هو الـ joint probability اللي هو إيه الـ probability إن كل الـ item اللي في الـ rule دي كل الـ items اللي في الـ rule دي يظهروا مع بعض أيا كان عدد الـ items دي إيه، يعني لو X دي فيها two items و Y فيها two items يبقى الـ four items دول كلهم مع بعض بيظهروا كام مرة.
على الـ total number of transactions اللي في الـ data set كلها ودي حتطلعلي الـ percentage بتاع الـ support. وقلنا إن الـ support مبيختلفش لو الـ rule بتاعتي if X then Y أو if Y then X لأن إحنا بنقول دا عدد دا الـ total items دي كلها بتظهر مع بعض كام مرة أيا كانت. فقلنا إن إحنا عندنا parameter تاني اللي هو الـ confidence.
الـ confidence دي بتقولي الـ probability إن Y تحصل given إن X حصلت. تمام؟ فهو حيبقى العدد الـ transactions اللي فيها بردو X و Y نفس نفس الـ support بس مقسومة المرة دي على عدد الـ transactions اللي فيها X بس عشان يديني الـ conditional probability.
واتكلمنا المرة اللي فاتت على أول algorithm في الـ algorithms اللي بتتعامل مع الـ association rule mining اللي هو الـ apriori algorithm وقلنا إنه دي اللي قدامنا دي هي الـ steps بتاعته، إنه بيبتدي الأول بالـ frequent one itemsets أو بمعنى أصح الـ frequent items وبعدين يبتدي
يعمل الـ iterations بتاعته في كل iteration بيبتدي يطلع candidate itemsets اللي هو بيـ join الـ items اللي طلعت frequent في الـ round اللي قبلها، بيطلع منهم الـ candidate itemsets، وبعدين بيعمل الـ candidate pruning اللي هو بيـ check على الـ subsets بتاعة الـ itemsets دول إذا كانوا كلهم frequent ولا لأ، وبعدين بيحسب الـ support للـ itemsets دي اللي فضلت بقى من بعد الـ step بتاعة الـ candidate pruning، وفي الآخر بيشيل الـ items اللي هي مش frequent.
بعد ما ويفضل يعمل كدا لحد ما يبقى ما عنديش أي أي combinations أقدر أعملها generation، بعد ما يخلص دا بيبتدي من الـ frequent itemsets يطلع الـ strong rules اللي هي الـ confidence بتاعتها equal أو أعلى من الـ minimum confidence اللي هي الـ user بيدخلهالي.
طيب أول كلامنا في المحاضرة بتاعت النهاردة حنتكلم على إزاي بنـ represent الـ frequent itemsets. يعني إيه بنـ represent الـ frequent itemsets؟ هو إحنا لو فاكرين من المحاضرة اللي فاتت إحنا لما عملنا generation للـ frequent itemsets أنا كان عندي dataset صغننة جداً فيها عشرة transactions وكلها ستة items ومع ذلك إحنا طلعنا منها حاجة مثلاً
around تلاتين item frequent itemset. فلو كانت الـ database بتاعتي أو الـ dataset بتاعتي أكبر من كدا بكتير، لو بنتكلم بقى في الأرقام اللي إحنا بنتعامل بيها لما تبقى data mining يعني، فحيبقى عندي آلافات الـ frequent itemsets، فهل أنا حـ store كل المجموعة دي من الـ itemsets؟ المفروض إنه لأ.
فابتدوا يفكروا في إن أنا طب إزاي إن أنا أختار مجموعة من الـ frequent itemset ميبقوش كلهم أخليهم هم يعملوا representation لكل الـ frequent itemsets اللي عندي. فقالوا في نوعين من الـ representations حنتكلم عليهم.أول نوع من الـ representation بنسميها الـ maximal frequent itemset.
الـ maximal frequent itemset تعريفها هي itemset frequent بس مفيش ولا واحدة من الـ super sets بتوعها frequent. يعني كمثال لو أنا عندي itemset مثلاً فيها A و B و C.
تمام؟ فأنا الـ itemset دي حقول عليها maximal لو مفيش زي ما قلنا أي واحدة من الـ super sets بتوعها frequent. طبعاً هي لازم تكون هي frequent وما يكونش في أي واحدة من الـ super sets بتوعها frequent. فالـ itemset فبالتالي مثلاً ميبقاش مثلاً ABCD frequent ولا أي حاجة تانية من الـ super sets بتوعها frequent.
تمام؟ هي دي ميزتها إن أنا دلوقتي أنا لو عرفت إن ABC frequent فأنا أقدر من ABC دي أعرف إن كل الـ sub sets بتوعها frequent، فأنا عارفة إن AB frequent و AC frequent و BC frequent و A لوحدها و B لوحدها و C لوحدها كل واحدة فيهم frequent لأن مادام الـ
frequent فيبقى كل الـ sub sets بتوعها frequent. تمام؟ بس هنا حتقابلني مشكلة إن أنا ok أنا قلت إن أنا ABC frequent وبالتالي أنا عارفة إن AB frequent. بس هل أقدر أعرف الـ support بتاع AB كام؟ لأ، ماعنديش طريقة إن أنا أعرف الـ support بتاع AB. يعني ok أنا عارفة إن أنا مادام ABC مثلاً بتحصل عشر مرات، فـ AB حتكون بتحصل يا عشر مرات
يا أكتر. تمام؟ بس كام أكتر؟ ماعنديش أي طريقة إن أنا أعرفها. فبالتالي قالوا لأ يعني هو دا مش حيوصلني للحاجة اللي أنا عايزاها، إن دا ميبقاش هو الـ representation اللي أنا بدوّر عليه. فابتدوا يفكروا في حاجة تانية. فكانت اللي هم قالوا بعد كدا إن في حاجة سموها الـ closed frequent itemset.
أوكي، تعريف الـ closed frequent itemset هي itemset بردو frequent بس مفيش ولا واحدة من الـ super sets بتاعها ليها نفس الـ support. أوكي، ممكن يكونوا الـ super sets دول frequent فبالتالي هي مش maximal. بس مفيش ولا واحدة فيهم الـ support بتاعها هي نفسها بالظبط.
تعالوا نشوف دا كدا بـ example. أوكي الشكل اللي قدامنا دا بس عشان إحنا أول مرة نشوفه إحنا بنسميه في الـ data mining اسمه itemset lattice. هو أنا هنا عندي dataset فيها أربعة items اللي هم A و B و C و Dو E، مفيش E سوري، A B C D.
وأنا هنا بـ represent كل الـ combinations اللي ممكن تطلع من الأربعة items دول. فهنا دي الـ combinations of 1، دي 2، ودي 3، ودول 4. تمام؟ والـ lines اللي ما بينهم دول معناها إن الـ itemset subset من دي، يعني A
ABC مثلاً هنا subset من ABCD وهكذا. تمام؟ أو طبعاً العكس إن ABCD super set لدول، بس الـ connections دي أو الـ lines دي معناها إن دي is a subset super set relation يعني. تمام؟ طيب، اللي أنا معلمة عليهم بالـ boxes الخضرا دي هم دول الـ closed frequent itemsets بتوعي.
فمثلاً لو بصيتوا مثلاً على item زي C، حتلاقوا إن دي الـ support بتاعها أربعة، هو هنا أنا حاطة الـ transactions اللي ظهرت فيها. فالـ support بتاعها أربعة. بصوا على كل الـ super sets بتوعها، AC الـ support بتاعها تلاتة، BC الـ support بتاعها تلاتة، CD الـ support بتاعها اتنين. يبقى إذاً مفيش ولا واحدة من الـ super sets بتوعها ليها نفس الـ support.
أنا هنا مش قايلة إيه الـ minimum support، أنا مفترضة إن كل الـ items اللي قدامي دي frequent يعني، فأنا مش قايلة الـ minimum support، بس يعني هو في الآخر حتى لو هم في حاجة frequent أو حاجة مش frequent هي مش دي الفكرة، الفكرة إنهم كلهم مفيش حاجة ليها نفس الـ support. طيب، دا مفيد في إيه؟ مفيد في إن أنا لو عندي itemset
ماهياش closed زي مثلاً AD، أنا أقدر أعرف الـ support بتاعها من الـ support بتوع الـ super sets بتوعها. يعني مثلاً AD، الـ super sets بتاعتها هي ABD و ACD. طيب، أنا أعرف طب دي واحدة فيهم الـ support بتاعها اتنين وواحدة الـ support ، سوري الـ support بتاعها واحد وواحدة الـ support بتاعها اتنين.
أنا أعرف AD الـ support بتاعها كام إزاي؟ ما إحنا قايلين إن الـ itemset closed، صح؟ فيبقى إذاً closed دي قلنا معناها إن مفيش لو الـ itemset closed يبقى معناها إن مفيش ولا واحدة من الـ super sets بتوعها ليها نفس الـ support. طب لو هي مش AD closed دي مش closed فيبقى إذاً لازم يكون في واحدة من الـ super sets بتوعها ليها نفس الـ support.
طيب أنهي واحدة فيهم؟ اللي الـ support بتاعها أعلى. ليه؟ لأن إحنا عارفين إن الـ itemset دايماً الـ support بتاعها أعلى أو equal للـ super sets بتوعها، فهي لا يمكن تكون الصغيرة دي، لا يمكن تكون الـ super set الـ support بتاعها أقل من الـ sub set. دايماً لازم يا equal يا أعلى. فيبقى إذاً هي
الـ support بتاعها زي ACD اللي هي الـ support الأكبر اللي هي اتنين. وهكذا، دا نقدر نطبقه على أي itemset من اللي هم مش closed، اللي هم مش عليهم الـ squares الخضرا دي. فكدا أنا أقدر يعني أنا عرفت، قللت عدد الـ itemsets اللي أنا بخزنها، بس في نفس الوقت قدرت أعرف
الـ supports بتاتعهم كام من الـ items اللي أنا مخزناها. فدا الشكل اللي إحنا بنتكلم فيه إن أنا عندي الغالبية هي الـ frequent itemset، دا الـ set كلها. تمام؟ لو حاولنا إن إحنا نطلع الـ maximal فهتلاقوا دا أقل عدد من الـ items أنا أقدر أحتفظ.
بيه. دا اللي هو بيقولي مين الـ itemsets الـ frequent ومالهمش super sets frequent فدول اللي أنا أعرف أطلع منهم كل حاجة. بس زي ما قلنا دول مادوناش الـ information بتاعة الـ support، فبالتالي اخترنا الـ closed. الـ closed آه عددهم هيبقوا أكتر شوية من الـ maximal تمام؟ بس في الآخر بيدوني الـ information بتاعة الـ support وأقدر أعرف الـ support بتاع الـ items منها .
طيب هنا هنبتدي نتكلم على تاني algorithm من الـ algorithms اللي هي بتعمل بتـ generate الـ frequent itemsets، إحنا هنا مش هنتكلم عن الـ generation بتاعة الـ rules لأن طريقة الـ generation بتاعة الـ rules هي هي زيها زي الـ apriori algorithm فإحنا مش هنعيدها تاني لكن هنتكلم بس على الـ algorithm إزاي بتـ generate الـ frequent item
أوكي الـ algorithm اللي إحنا هنتكلم عليه النهاردة اسمه FP-growth، وهنبتدي بقى نتكلم نشوف هو بيشتغل إزاي.طيب إحنا المرة اللي فاتت زي ما قلنا شرحنا الـ apriori algorithm وقلنا إن الـ apriori algorithm بيشتغل بنسميها breadth first search اللي هو هو زي ما إحنا عارفين هو بيبتدي
بيخلص كل الـ one itemsets، أوكي once إن هو يـ generate الـ one itemsets دي بيطلع منها الـ two itemsets وبعدين الـ three وهكذا تمام الـ FP-growth بقى لأ بيشتغل depth first فهو يعني إيه depth first يعني هو مثلاً هنا بيبص على الـ A.
لقى A frequent يبتدي يبص على AB، لقى AB frequent يبتدي يبص على ABC وهكذا، لقاها frequent يبتدي يبص على ABCD، لقى دي frequent تمام خلاص كدا ماعندوش حاجة تاني، يرجع للـ step اللي قبلها ويشوف الـ combinations بتاعة AB اللي بعد كدا فيجرب ABD وهكذا، تمام لحد ما يخلص كل الـ options اللي عنده.
طيب الـ FP-growth هي FP دي stands for Frequent Patterns فالـ FP-growth دا فكرته الأساسية إن هو بيعالج مشكلة كانت موجودة في الـ apriori algorithm اللي هي مشكلة الـ database scans. يعني إيه الـ database scan
زي ما اتكلمنا وإحنا بنقول الـ apriori algorithm قلنا إن أنا عشان أ count الـ support بتاع أي itemset لازم بعدي على الـ database بتاعتي كلها من أولها لآخرها عشان أشوف في كام transaction الـ item دي ظهرت فيهم. فدي اللي بنسميها الـ database scan إن أنا كل ما هحسب support لـ item هـ scan الـ database كلها من الأول.
تمام فدي زي ما قلنا حاجة بتاخد processing time كبير جداً جداً إن أنا أ scan الـ databases هذا العدد من المرات. فالـ FP-growth قال لأ أنا مش هعمل مش هـ  scan الـ database أنا هتعامل هـ  scan الـ database مرة واحدة بس هطلع منها representation للـ data set
في tree اسمها الـ FP-tree. وonce إن أنا عملت الـ FP-tree دي خلاص أنا مش هرجع للـ database تاني ولا هحسب أي حاجة من الـ database ولا هـ scan الـ database تاني بعد ما عملت الـ FP-tree. كل شغلي بعد كدا هيبقى في الـ FP-tree دي نفسها.طيب إحنا هنشرح الـ algorithm بتاعنا على نفس الـ example اللي إحنا قلناه المرة اللي فاتت اللي هو دي الـ transactional database بتاعتي.
تمام وهنقول إن الـ minimum support بتاعنا 30%. طبعاً أنا هنا زي ما قلتلكم محطيتش minimum confidence لأن إحنا مش هنـ generate الـ rules هي الـ rules بتبقى generated بنفس الطريقة بتاعة الـ apriori algorithm.طيب أول step بتتعمل في الـ FP-growth algorithm هي زيها زي الـ apriori algorithm بالظبط
بيبتدي يمسك كل item عندي في الـ database ويبتدي يحسبلها الـ support. تمام؟ ولو في عندي حاجة مش frequent زي f كدا هيشيلها من الـ list. تمام؟ وبعدين بقى يبتدي يعمل إيه؟ بعد ما حسب الـ support بتاع كل item لوحدها هيبتدي يـ sort الـ itemsets دي
من الأعلـى support للأقل support. تمام؟ وبعدين مش بس كدا، هيبتدي يـ sort كل transaction لوحدها بنفس الترتيب دا، يعني الـ transaction دي كانت مكتوبة A B C D E، لأ هو هنا راح غيّر ترتيبها وجابها زي ما إحنا مرتبين الـ items كدا فجاب الـ A الأول وبعدين الـ C وبعدين الـ B والـ E والـ D وهكذا
في كل transaction هنا A C E D، آه جاب الـ E الأول قبل الـ D لأن الـ E الـ support بتاعها أعلى من الـ D فهو بيـ sort كل الـ items جوه كل transaction بنفس ترتيب الـ supports بتاعتها okay. طبعاً إحنا هنا شلنا الـ transactions اللي كان فيها f شلنا منها الـ f، فخلاص إحنا الـ f دلوقتي مش حنستعملها خالص، فشلنا الـ f وتاني عملنا sort.
للـ items جوه كل transaction بحسب الـ supports بتاعتها.بعد كدا بقى هنبتدي نبني اللي هي الـ FP-tree. الـ FP-tree دي بقى بتتبني إزاي؟ بنبتدي نمسك transaction by transaction بعد ما عملنا لهم sorting ونبتدي. هبتدي بـ tree أول node فيها labeled null.
تمام؟ وبعدين أبتدي الـ path بتاعي الأولاني اللي هو A C B E D هحطه زي ما هو كدا بس بـ counts على الـ nodes كلها 1 .تمام؟ يبقى دي أول أول transaction. تاني transaction بقى، هبتدي أشوف طيب هبتدي من أول الـ node اللي هي null دي وأقول أول هنا أول item هنا عندي A.
طيب هل الـ A موجودة؟ آه موجودة، يبقى هعمل إيه؟ هغيّر الـ count اللي هنا دا بدل واحد أخليه اتنين. طيب بعد كدا C، C موجودة؟ آه موجودة، يبقى هغيّر الـ count بتاع دي أخليها باتنين. طيب وبعد كدا الـ item اللي بعد كدا هي E. تمام؟ فيبقى طيب هل أنا هنا عندي E؟
أنا عندي E تحت بس لأ ماعنديش E طالعة directly من الـ C، يبقى حروح هنا أعمل path لوحده كدا وأحط فيه الـ E دي.فهيبقى الشكل بالمنظر اللي قدامنا دا. والـ E دي طبعاً هيتطلهم counts بـ 1. تمام؟ نيجي بقى الـ transaction اللي بعد كدا مثلاً C E D، أنا هبتدي من الـ node الأولانية هل أنا هنا عندي C خارجة directly من الـ node الأولانية؟ لأ يبقى هطلع path لوحده جديد خالص فيه C E.
D. يبقى دا اللي إحنا عملناه هنا إن أنا طلعتلي C E D كـ path لوحدها. طيب نفس الكلام الـ transaction اللي هنا B، هل أنا هنا عندي من الـ node الأصلية اللي هي الـ null دي في حاجة B؟ لأ يبقى هطلع path لوحده في B اوكي فاحنا هنا طلعنا.
الـ node اللي هي قلنا الـ node اللي هي B اللي هي الـ count بتاعها بـ 1 على طول طلعت directly من الـ null node. الـ transaction اللي بعد كدا A C B D، فإحنا هنا عندي الـ A أهي يبقى أنا هغيّر الـ count بتاعها أخليه تلاتة، بعدين C هغيّر بردو الـ count بتاعها أخليه تلاتة، وبعدين عندي B
هنا أهي يبقى هغيّر الـ count بتاعها بدل واحد أخليه اتنين، وبعدين هلاقي مفيش D بقى direct يبقى أنا هنزل من هنا node بـ label D والـ count بتاعها واحد.زي الشكل اللي قدامنا كدا. تمام؟ نيجي بعد كدا الـ transaction اللي بعد كدا هي A B E.
A B E أنا هنا بردو هاجي عند الـ A وهغيّر الـ count بتاعها أخليه أربعة، بس أنا ماعنديش B بقى هنا خارجة منها، فهبتدي هنا أطلع path لوحده كدا فيه B E بـ counts 1.ودا هيبقى الشكل اللي قدامنا. وهكذا بقى نكمل، أنا عندي مثلاً الـ transaction اللي بعد كدا A C B، يبقى أنا A C B موجودة اهي هغيّر بس الـ counts بتوع.
التلاتة nodes دول بالشكل اللي قدامنا دا. الـ transaction اللي بعد كدا A B E، فـ أنا عندي already A B E فـ أنا برضه هزوّد الـ count بتاع كل الـ nodes دي بواحد بالشكل اللي قدامنا كدا. وهكذا، اللي بعد كدا A C.
برضه أنا عندي A و C يبقى هبتدي بس أغير برضه الـ count بتاع الـ nodes دي بالشكل اللي قدامنا دا. وآخر حاجة A C E D أنا عندي أهو برضه A C E D يبقى أنا برضه كل اللي هعمله إن أنا هغيّر الـ counts اللي على الـ node دي هزوّدها بواحد يبقى هيبقى عندي الشكل كدا.
يبقى إذًا اللي قدامنا دي هي الـ final FP-tree اللي إحنا عملناها. دي بتـ represent كل الـ transaction اللي موجودة في الـ dataset بتاعتي. تمام؟ أنا خلاص كدا دلوقتي مش محتاجة الـ transactional database اللي هنا دي
خالص خلاص أنا مش عايزاها، ومش هرجعلها تاني، هطلع كل الـ frequent itemsets بتاعتي اللي أنا اللي أنا محتاجاها من الـ tree دي. تمام؟ طيب، هنعمل الكلام دا بقى إزاي؟ قال لي إن أنا ببتدي إن أنا أطلع الـ combinations بتاعتي ببتدي من الـ item اللي ليها أقل support.
تمام؟ وأبتدي أشوف الـ paths اللي آخرهم الـ item دي وبعدين أبتدي أعمل حاجة بنسميها الـ conditional FP-tree. تمام؟ وكل ما ألاقي حاجة frequent أبتدي أطلع منها combinations. تمام؟ دا حاجة كدا هتتعمل recursive كدا هنمشي فيها معاها ونشوف سوا هتتعمل إزاي.
طيب، فإحنا من الـ tree اللي إحنا عملناها اللي هي الـ tree الأصلية، طلعنا كل الـ paths اللي هم آخرهم D. أي path الـ leaf node اللي فيه D خدته من الـ tree وشيلت الـ paths التانية يعني لو فاكرين كان في هنا path فيه B مثلاً لوحدها دا شيلناه، كان في هنا برضه من A طالع path فيه B دا شيلناه. إحنا بنشيل بنخلّي بس الـ paths اللي آخرها D لأن دي هي أقل item في الـ support.
تمام؟ طيب، الـ step بقى اللي بعد كدا إن احنا بنعمل ايه بنعمل حاجة بنسميها الـ conditional FP-tree بتاعة D. طيب، الـ conditional FP-tree دي بتمشي على تلاتة steps. أول واحدة فيهم إحنا بنقول عليها إن احنا بنـ update الـ support.
بنـ update الـ support على أساس إيه؟ بصوا كدا على الـ example اللي قدامنا دا، أنا هنا بقول إن أنا عندي الـ node A، أنا بـ update الـ support بتاع A بحيث إن أنا أشوف علاقتها بـ D شكلها إيه. تمام؟ فالتمانية دا دا الـ total number of times اللي A ظهرت فيه، لكن أنا عايزة أشوف
A لما بـ in relation to D يعني علاقتها بـ D بتظهر كام مرة؟ فهبتدي أشوف كدا، طيب أنا آدي الـ node A أهي، طيب أنا عندي كام node في الـ children بتوع بتوع A labeled D؟ اللي هم التلاتة اللي إحنا معلمين عليهم دول. طيب، مجموع الـ supports أو مجموع الـ counts اللي عليهم كام؟ هنلاقي هنا اتنين.
plus واحد plus واحد، اللي هي أربعة. يبقى أنا هغيّر الـ support بتاع A دا بدل ما كان تمانية أخليه أربعة. تمام؟ نفس الكلام الـ C، هم نفس الـ nodes دول، يبقى أنا هغيّر الـ count بتاعها بدل ستة أخليه أربعة. طيب، B بقى مثلاً؟ أنا عندي two nodes أهو بس اللي هي دي
وD والـ counts بتاعتهم واحد، يبقى إذًا B دي هتتغير التلاتة دي هتبقى اتنين. وهكذا لكل الـ nodes اللي في الـ tree. فهيبقى الشكل بالمنظر اللي قدامنا دا إن إحنا عملنا زي ما قلت عملنا updating للـ supports بتاعتنا بحيث إنها تـ reflect D. يبقى دي أول step.
طيب تاني step إيه بقى؟ تاني step إن أنا بشيل الـ nodes اللي هي بتاعة D أصلاً خالص من الـ tree. تمام؟ فيبقى أنا بقى الشكل الشكل اللي قدامي دا. تمام؟ تالت step. تالت step لو في حاجة مش frequent هشيلها. تمام؟ إحنا حاطين الـ minimum support بتاعنا 30% يعني الـ minimum count اللي أنا بقبله هو تلاتة.
تمام؟ بس نخلي بالنا إن الـ count مش الـ count اللي على الـ node، لكن الـ total count. يعني مثلاً أنا أشوف مثلاً هل أنا هشيل C ولا لأ، مجيش أقول مثلاً الـ node دي والله الـ count بتاعها واحد يبقى هي مش frequent فأنا هشيلها، لأ. أنا عندي دي واحد plus في واحدة تانية C الـ count عليها أربعة يبقى C الـ total count بتاعها خمسة يبقى C بالنسبة لي frequent.
وهكذا نفس الكلام مثلاً للـ E، الـ E أنا عندي تلاتة nodes أهم مجموع الـ counts اللي عليهم أربعة فيبقى إذًا E frequent. لكن B هي node واحدة والـ count بتاعها اتنين، فيبقى إذًا أنا هشيل B من الـ path بتاعي. طيب شيلت B هيبقى الشكل قدامي كدا، أو طبعاً ممكن أ join الاتنين nodes دول في node واحدة الـ count بتاعها تلاتة، يعني نفس هيبقى دي نفس الفكرة.
تمام؟ طيب، دي بقى هي اللي اسمها زي ما قلنا الـ conditional FP-tree بتاعة D. تمام؟ أنا عملت دي هبتدي بقى من دي أطلع كل الـ combinations اللي فيها D. طيب هعمل كدا إزاي؟ هرجع لنفس الـ steps اللي إحنا عملناها هعملها تاني أكررها تاني.
فأنا من أول هنا هشوف إيه أقل item ليها support، E. يبقى أنا هجيب كل الـ paths اللي آخرهم E. فهيبقى بالشكل اللي قدامنا دا. طيب أنا الـ counts اللي على E كام؟ لو عديتوهم حتلاقوهم أربعة. دا معناه إيه؟ معناه إن DE أو ED بقى يعني زي ما تفرق هي مش فارقة الترتيب في حاجة، إحنا عارفين إن إحنا في الـ item sets مش بيفرق الترتيب.
تمام؟ في يعني DE أو ED أنا كدا عارفة إن ED لأن تاني دي الـ conditional FP-tree بتاعة D فأنا هنا لما بقول E الـ count اللي عليها أربعة دا مش معناه إن E حصلت أربعة مرات، دا معناه إن E مع D حصلت أربعة مرات. فبالتالي هنا أنا أقدر أقول إن DE frequent.
طيب عملت كدا، أعمل إيه؟ أرجع أعمل نفس التلاتة steps اللي إحنا طبقناهم على على الـ tree الأصلية عشان نطلع الـ conditional tree بتاعة D، هنا هعمل نفس الـ step وهطلع الـ conditional tree بتاعة E أو المفروض بقى نسميها ED  تمام؟ فإحنا هنا فإحنا هنا هنقول إن دي بداية الـ conditional tree بتاعة ED.
تمام فإحنا برضه هنمشي على نفس الـ steps، هنـ update الـ supports، فإحنا كدا عملنا update للـ supports دي كان الـ count أربعة إحنا خليناه تلاتة لأن هو الـ count اللي على الـ nodes اللي هي labeled E مجموع تلاتة وهكذا، وعدلنا الـ support دي. تاني step شيلنا الـ nodes اللي هم E كلهم.
أوكي، تالت step لو في حاجة مش frequent هنشيلها. هنا الـ A الـ count بتاعها تلاتة والـ C الـ count بتاعها أربعة، فيبقى إذًا كله frequent، يبقى كدا تمام. تمام؟ يبقى دي الـ conditional tree بتاعة ED. تمام؟ نرجع تاني نفس الـ steps بتتكرر تاني، هجيب الـ paths اللي آخرهم C.
هم برضه اللي قدامنا دول، يبقى إذًا أنا هفهم من كدا، لأن دي الـ conditional tree بتاعة ED، يبقى إذًا CDE أو CED بقى زي ما قلت مش هتفرق، دي frequent والـ count بتاعها 4. تمام؟ وبعدين أرجع تاني أعمل conditional FP-tree، أبديت وأشيل الـ C وأشيل الـ nodes اللي مش frequent.
هتفضل لي الـ tree اللي قدامنا دي، دي أفهم منها، دي الـ conditional FP-tree بتاعة CDE بقى، يبقى دي أفهم منها إن ACDE frequent والـ count بتاعها 3. أوكي كدا أنا خلصت كل الحاجة اللي connected بـ E.
أعمل إيه بعد كدا؟ أرجع بقى أنا برجع steps، فبرجع تاني للـ conditional tree مثلاً، يعني أنا دلوقتي أنا دي كانت الـ conditional tree بتاعة C. أرجع تاني خلصت طلعت منها كل الـ paths اللي آخرهم A وهكذا، أرجع بقى الـ step اللي قبلها. طيب زي ما قولنا ان انا كده لما خلصت ال paths وصلت لحد الpath اللي هو A C D E هرجع تاني بقى step
لورا، فهجيب الـ conditional هجي في الـ conditional tree بتاعة ED اللي أنا كنت جبت منها الـ paths اللي آخرهم C وعملت كل القصة اللي إحنا عملناها دي، هرجع تاني للـ conditional tree بتاعة ED، يعني أنا برجع step لورا كدا. فالـ conditional tree بتاعة ED هجيب الـ paths اللي آخرهم A، هلاقي إن A أهي الـ count بتاعها 3، يبقى دا معناه إن AED
frequent والـ count بتاعها 3. طيب بعد ما إحنا في الـ slide اللي قبل كدا طلعنا إن AED frequent، كدا إحنا المفروض إن إحنا خلصنا كل الحاجة اللي فيها أي combination فيها E مع D تمام. فزي ما قلنا إحنا متفقين إن إحنا بنرجع step لورا، يبقى إحنا بنرجع تاني لل
للـ tree بتاعة D، أوكي هبتدي هنا بقى، أنا خلصت كل الحاجة اللي فيها E خلاص في الـ round اللي قبل دي. يبقى هنا هبتدي أطلع الـ paths اللي آخرهم C. يبقى هنا طلعت الـ paths اللي آخرهم C، دا معناه إن CD
frequent والـ count بتاعها 5. وهبتدي أطلع برضه الـ conditional tree بتاعتها، تمام؟ الـ conditional tree بتاعتها هتبقى اللي إحنا هنقوله دلوقتي. هتبقى الـ conditional tree هتبقى المنظر اللي قدامنا دا، اللي هو هنا أقدر أقول إن ACD frequent والـ count بتاعها 4.
تمام؟ يبقى أنا كدا خلصت كل الحاجة اللي فيها C مع D. أرجع تاني للـ conditional FP-tree بتاعة D تاني، أجيب الـ paths اللي آخرهم A. يبقى إحنا هيبقى الشكل بالمنظر دا، يبقى دا معناه إن AD frequent والـ count بتاعها 4. طيب أنا كدا المفروض إن أنا معناها دلوقتي خلصت كل الـ combination اللي في الدنيا اللي فيهم D.
الـ step اللي بعد كدا إيه؟ إن أنا برجع بقى خالص لأول tree خالص اللي هي الـ tree الأصلية اللي هي قدامنا هنا، وأبتدي أطلع منها، أنا كدا خلصت زي ما قلت كل الـ combinations of D، هبتدي أعمل الـ combinations بتاعة E.
يبقى هجيب كل الـ paths اللي آخرها E. هيطلع لي الشكل اللي قدامي دا. هبتدي أمشي على الـ steps بتاعة الـ conditional FP-tree كلها تاني، إن أنا هعدل الـ supports زي ما إحنا قلنا، فدا تعديل الـ supports بتاعتنا بالنسبة للـ E، فزي ما قلنا كدا A، آدي الـ nodes اللي خارجة منها labeled E فدول مجموعهم 5.
C آدي دول يبقى مجموعهم 3 وهكذا. تمام؟ وبعدين أشيل الـ E، ولو في حاجة مش frequent هشيلها. هنا كل الـ nodes frequent. أوكي وأبتدي بقى أجيب هنا مثلاً هجيب كل الـ paths اللي آخرهم B، يبقى آدي الـ paths اللي آخرهم B فأنا كدا عرفت إن BE frequent والـ count بتاعها 3.
وهكذا هنستمر بقى بنفس الطريقة دي لحد ما نطلع كل الـ combinations of frequent itemsets. أوكي، الكلام دا يبدو إن هو processing كتير بس في الآخر زي ما قلنا الـ FP-tree دي حاجة صغيرة وممكن تكون موجودة في لو الـ dataset مش كبيرة ممكن تكون كلها موجودة في الـ memory فـ أنا مش مضطرة إن أنا أ scan الـ database خالص.
أوكي وكدا نبقى إحنا خلصنا كلامنا على الـ FP-growth algorithm. طيب، يفضلنا بس حاجة صغيرة هنتكلم فيها في المحاضرة دي إن إحنا بنتكلم على طريقة للـ storage بتاعت الـ data برضه بتسهل عملية الـ إن إحنا نلاقي الـ frequent itemsets.
اللي إحنا اشتغلنا عليهم سواء كانت الـ Apriori أو الـ FP-growth algorithms بيستعملوا حاجة اسمها الـ horizontal representation. أوكي، الـ horizontal representation دا هو اللي إحنا واخدين عليه اللي هو الشكل اللي هو transaction وفيها items. زي الشكل اللي موجود هنا، إن أنا عندي transaction معينة ودي الـ items اللي جوه الـ transaction.
تمام في algorithms ابتدت تعمل حاجة بيسموها الـ vertical representation اللي هو الشكل اللي قدامنا هنا دا. دا بيـ store الـ data إزاي؟ بدل ما بيـ store transaction وإيه الـ items اللي جواها لأ، بيـ store الـ item وبعدين يقول إيه الـ transactions اللي الـ item دي ظهرت فيها. فمثلاً أنا عارفة إن A دي ظهرت في transaction 1 و 2 و 5 و 6 و 7 و 8 وهكذا.
دا ميزته إيه؟ أولاً ممكن يكون برضه الـ representation أقل شوية من الـ data set الأصلية وكمان إن أنا هنا مثلاً لو عايزة أعرف الـ count بتاع A كام فأنا مجرد إن أنا هبص على الـ record دا بس لوحده مش هـعدي على الـ database كلها ولا حاجة، أنا هبص على الـ record دا بس هعرف.
A دي بتظهر كام مرة لأن أنا هعد الـ items الـ transactions يعني الـ items اللي جوه الـ cell دي هعرف إنها بتظهر تمان مرات. وهكذا الـ B بتظهر ستة وهكذا. طيب، لو عايزة أعرف A و B مع بعض بيظهروا كام مرة؟ هاخد الـ two sets اللي هنا دول وأعمل لهم intersection وأشوف إيه الحاجة الـ common هيقول لي A و B بيظهروا كام مرة.
فهو representation أحسن بياخد وقت أقل شوية في الـ processing أقل بـ significantly يعني عن إن أنا أ scan الـ database الأصلية كلها تاني. من أشهر الـ algorithms اللي بتستعمل vertical representation algorithm اسمه الـ Eclat أو هي اختصار equivalence class transformation.
تمام أنا مش هشرح الـ algorithm هو بس إحنا يعني نبقى فاهمين إن هو الـ algorithm دا هو بيستعمل الـ vertical representation وإن هو بيستعمل set intersection عشان يلاقي الـ frequent itemsets. وطبعاً ميزته زي ما قلنا إن أنا مش محتاجة إن أنا خالص إن أنا أ store أ scan الـ database تاني ولا حاجة، أنا بس أنا عندي الـ transaction IDs وهي دي اللي أنا اللي أنا ببص ببص عليها وبعمل intersection ما بينها ودي فيها كل الـ support information اللي أنا عايز.
العيب بس إن ممكن تكون الـ transaction ID sets دي كبيرة شوية فإن أنا أعمل الـ intersection دا ممكن ياخد وقت شوية معايا عشان أعرف إن أنا أعمل الـ intersection دا، لكن في الآخر هو برضه مازال أقل من الوقت اللي أنا بحتاجه عشان أ scan الـ database كلها عشان أحسب الـ support تمام .
كده احنا خلصنا النهاردة كلامنا على الـ Association Rules و الـ Algorithms بتاعة الـ Association Rules Starting من المرة الجاية ان شاء الله هنبتدي نتكلم على نوع تاني مختلف من الـ Frequent Patterns اللي هو الـ Sequence Data شكراً