بسم الله والحمد لله والصلاة والسلام على رسول الله
أهلا وسهلا بكم في تكملة الـ Protective chapter
Modelling أو الـ Frequent Pattern كنا تكلمنا سابقا
على مفهوم الـ Frequent Pattern للتسجيلات السابقة على مفهوم
الـ Frequent Pattern وشو هو ال association rule
وتكلمنا على الـ support و الـ confidence as
measurement
تحديد قوة الـ association rule و الـ frequent pattern
واتكلمنا على الـ Apriori algorithm كواحد من أهم الـ
algorithms في وجود الـ ... أو في الوصول إلى الـ
association rules و لكن قلنا أن في عندنا مجموعة من
الـ drawbacks على مستوى الـ Algorithm التي
عندنا منها أنه أنا فعلياً في عندي multiple scans
طبعاً من الـ drawbacks هذه التي علاقتها كلها بالـ
computation أنه بتزيد من التكلفة الزمنية أو
الحسابية للـ algorithm الموجود عندنا، الـ multiple
scans أو عدد الـ number of candidates وببدأ من
candidate واحد وببدأ أجمعهم وبالتالي كان العدد
كبيراً، العمل ممل وتكراره في موضوع حساب الـ
support الموجود عندنا، ممكن نقلل
عدد مرات القراءة للـ database أو نقلل عدد الـ
candidates الموجودين عندنا
بنتكلم عن طريقة كيف نسرّع فيها أو نحسّن فيها موضوع
حساب الـ candidates نحسب الـ support للـ candidates
الموجودة عندنا وبشكل عام ممكن نعتمد على الـ parallel
computing من أجل تسريع هذه العملية بشكل عام، الآن
إن شاء الله تعالى سنتكلم عن أحد الحلول
المتاحة عندي، أنه أنا أحاول أوجد الـ
frequent patterns بدون ما يكون في عندي candidate
generation، طبعاً نحن الآن من باب التأكيد أن الـ
bottleneck أو الحلق الذي ... لنقل نقطة الازدحام
أو الحلق الأضعف في الـ Apriori approach هو الـ
breadth-first search، breadth-first search لأن
معنى الكلام هي مصطلحات مألوفة موجودة في الـ data
structure، إذا كنا نتذكرها، ومقصود فيها أنه أنا
البحث يتم على مستوى الـ level-wise، ماذا يعني الـ level-
wise؟ المبدأ هذا جاء من أن في عندي موضوع Tree بغض
النظر عن الـ Structure التابعة للـ Tree ثنائية أو رباعية
أو غيرها، فمفهوم الـ breadth-first أنه أنا آخذ level
level وأنتقل إلى كل عناصر الـ level، بعدين أذهب إلى
الـ level الثاني وأمشي فيه، طبعاً هذه الـ approach
لأنها فعلياً كانت تبني كل الـ candidates من C1
وبعد ذلك ننتقل إلى Candidate C2 من الـ two elements
و Candidate C3 وهكذا، وهذا طبعاً ما يستهلك وقتاً
طويلاً جداً، بينما الـ ... الـ ... الـ FP-
growth أو الـ Frequent Pattern Growth approach التي
أنا أبدأ العمل بدون البحث عن الـ candidates، أبدأ العمل
على مبدأ الـ depth-first search، أنه دائماً أنزل أعمق
نقطة في الـ tree، تمام؟ وبعدها أبحث عن النقطة الأعمق
والمساوية لها وهكذا حتى أصل إلى قاعدته، وبالتالي هنا
يصبح في عندي إلغاء للموضوع
الـ candidate generation، يعني يصبح في عندي بشكل
تلقائي تجنّب
الأساسي، المصطلح أو الفلسفة الأساسية التي بُني عليها
الـ FP-Growth أن الـ long patterns
ممكن أن تُبنى من الـ short patterns التي كانت frequent
items only، وعشان كل هذا الكلام، يعني بكل بساطة أقول لك
أنا لو كان في عندي مجموعة من الـ short frequent
patterns، هذه المجموعة من الـ short patterns ممكن أن تكون
جزءاً من patterns أطول، على سبيل المثال لو كان
في عندي الـ ABC frequent pattern في الـ data set
الذي عندي، معناه أنك ممكن أن تذهب وتجلب كل الـ patterns أو
الـ transactions التي تحتوي على الـ ABC مثلاً، لو كان
frequent، يعني أن كل الـ patterns التي تحتوي على الـ
ABC سنقول أن لو كان في عندي أيضاً frequent
أيضاً frequent pattern آخر، D وليكن على
سبي المثال، يعني لو أضفت الـ D إلى كل frequent
patterns الموجودة عندي هنا، إلى الموجودة من
الـ database، سيكون عندي الـ A, B, C, D عبارة عن
frequent pattern، يعني أنا عندي A, B, C عبارة عن
frequent pattern وعندي الـ D أيضاً frequent pattern
فحتما سيكون عندي A, B, C, D frequent pattern حتى لو
انخفض الـ support التابع له، لكن لن ينزل عن الـ minimum support
لماذا؟ لأنه بما أن الـ support لهذا أكبر من أو يساوي الـ
minimum support، و أن الـ support التابع له أقل من أو
يساوي الـ minimum support، فحتماً هذا المجموع سيكون
أكبر من أو يساوي الـ minimum support، لن يقل عنه بأي
حالة من الأحوال، لأن الاثنين frequent، الفكرة مرة أخرى
أن أنا أحاول أن أعمل نمو تكراريا لـ
frequent patterns، أنشئ الـ pattern بشكل تكراريا
بشكل تلقائي، يعني كل pattern يحاول أن يضيف
patterns الموجودة عنده، pattern by pattern
frequent pattern by pattern، و الـ Database
Partitioning، وبالتالي أنا أقسم الـ database وممكن
أن أشتغل عليها بالتوازي، يقال أن الـ FP-Growth كـ
algorithm أو كـ method ستكون أفضل نتيجة أو أسرع من
الـ Apriori للوصول إلى الـ frequent patterns الموجودة
لأنها for each frequent item، لكل frequent item set
construct its conditional pattern، أنشئ
conditional pattern التابع لها بناءً على ما أنتجته، Then
it's conditional FP-tree، واذهب أنشئ الـ tree التي
بعد ذلك خاصة بها، سنرى الـ FP-tree ونفهم ماذا
هو الـ conditional pattern الذي تم إنشاؤه عليه، الـ
conditional pattern، كيف تم الوصول إليه؟ وما
هي الشروط التي جعلته frequent؟ repeat the
process on each newly created conditional pattern
FP-tree until resulting FP-tree is empty، لا يكون
فيه شيء، وكرر العملية حتى لا يبقى شيء في الـ FP-tree
and or it contains only one path, single path، طبعاً
وهذا يكون generation all combinations، وهكذا أنا
أكون قد جمعت كل الـ sub paths الموجودة، يعني الخطوات
الخاصة بالخوارزمية، أنا أذهب وأعمل database scan
once، وهي أول عملية قراءة للـ database، مثل الـ Apriori
وأخذت وجلبت الـ first frequent pattern، تمام، نحن
يقال depth-first، صحيح breadth-first، depth-first، عفواً، وهكذا أنا ذهبت
إلى الـ pattern الأول، ليست قضية كبيرة، sort الـ frequent
patterns، وهنا شيء جديد، أن نرتب الـ frequent
patterns بناءً على الـ support، بترتيب تنازلي
Descending Support Counting, Making a Less than
Minimal، أعمل scan أيضاً للـ tree وأعمل
Construction للـ FP-tree الموجودة، التي سنراها
Mining the FP-tree By Creating Conditional أو Sub
patterns الموجودة، تعالوا لنرى ماذا يمكننا أن
نقول، يمكننا أن نعود إلى الـ benefits أو ننهيها الآن
completeness، متكاملة، preserve complete information
يحتوي على معلومات كاملة عن الـ frequent patterns التي
أنا قمت باستخراجها، يعني دائماً هو يحتفظ بالـ
support التابع لها، هذه المعلومة التي تهمّني، الـ
frequent pattern كم مرة ظهرت، never break long
patterns of any transaction، ممكن ألا تنتمي إلى transaction
مطلقاً، وهذا هو المشكلة، نحن لم نحسّنها مع الـ Apriori
لكن يُقال أنه عندما تكون عند الـ
data set التعاملات كبيرة، والعناصر الموجودة فيها
كثيرة، ممكن أن يحدث فيها تكرار أو ضغط أو
انخفاض في المعلومات، المعلومات، المعلومات، المعلومات،
المعلومات، المعلومات، المعلومات، المعلومات، المعلومات،
المعلومات، المعلومات، المعلومات،
العناصر بترتيب تنازلي
الكثير، يمكن أن يحدث الكثير، يمكن أن يتم شرح ما هو
موجود في أعلى القائمة هو غالباً هو الأكثر تكراراً
الموجود، Never be larger than the original
database، مستحيل أن يطلع عندي حجم أكبر من الموجود
عندنا، Not count node links and count field، أنا
لا أعدّ الروابط، فقط عدد مرات الظهور في المجموعة، كما
العادة، بالمثال يتضح الكلام، فلنرى الآن بالمثال
الموجود عندنا هنا، سأقول افترض أن في
عندي هذه الـ data، الـ transactional data set التي
تحتوي على خمسة عناصر، I1, I2, I3, I4, I5، وفي عندي
تسعة، عفواً، ليست...
I discard I transaction رقم تسعة، للأمانة، الخطأ
يحدث، وهذا طبعاً كررته هنا لأن copy و paste
اشتغلت هنا في المثال عندما عدلته، وعندما حدث ذلك أيضاً
إن شاء الله هكذا تمام، الآن، افترض أن الـ minimum
support التابعة لي هي عبارة عن اثنين، الـ minimum support
المطلوبة هي عبارة عن اثنين من تسعة، يعني 22% تقريباً، الـ
step الأولى، أقرأ الـ database مع الـ first أو one
item set، كل المجموعات التي هي عنصر واحد، وأحسب الـ
support التابعة لها، بعد ذلك، الخطوة الثانية، أرتبها
الآن، بكل بساطة، لو أنا جئت وقلت لك: ها هو I1، الـ
support له هي 1، 2، 3، 4، 5، 6، من ضمن العناصر الموجودة، الـ
frequent هي 6، موجود أكثر عنصر موجود عندي، more
frequent هو I2، هو عدد مرات تكراره 7 مرات
الثلاثة والأربعة والخمسة مع بعض، الاثنين والواحد والستة جاءوا
نفس الـ frequent، طيب، من أقدم فيهم، الذي يظهر معك
أولاً في الـ data set، لا تُلخّص نفسك دائماً، أو لا
تُلخّص نفسك دائماً، أنا آخذ أول عنصر يظهر في
frequent set أو في الـ item set هو الذي أقدّمه
في حالة تساوي عنصرين من ناحية عدد الـ support، الآن
بعد ذلك، أبدأ ببناء الـ FP-tree، وهي تتحدث عن خطوات
بنائها، أبدأ من null label، تمام، وبناءً عليه، أعمل الـ
second time، الـ second scan للـ database، المرة
الثانية، في كل transaction، أتعامل are processed in
الـ L order، بناءً على الـ sort order الموجودة عندها
والجزء يُصنَع لكل transaction مع الأشياء التي تدعمها، تدعمها،
تدعمها، تدعمها، تدعمها، تدعمها، تدعمها، تدعمها،
تدعمها، تدعمها، تدعمها، تدعمها، تدعمها، تد
الـ data set الموجودة عندي، أقول له: رتبها لي، سأرتبها،
رتبتها الآن، يا جماعة، هي الـ transactional
data set التابعة لي،
سبعة تمام دعوني أغير بالسلون
سبعة صحيحة الآن، واحد المفروض ستة، واحد هي عندي
هنا أربعة وعندي هنا اثنين، فالكلام صحيح مئة بالمئة
مجموعهم ستة الآن، ثلاثة، ستة كذلك، ثلاثة عندي
موجود، ثلاثة ست مرات، أين، ثلاثة، هذه
مرتين هنا، هي مرتين هنا هي
مرة هي، ثانية، اثنين، اثنين، اثنين، اثنين، اثنين
اثنين، اثنين، اثنين، اثنين، اثنين، اثنين، اثنين
اثنين، اثنين، اثنين، اثنين، اثنين، اثنين، اثنين، اثنين
اثنين، اثنين
طيب، أي ثلاثة تمام، أي أربعة مرتين، هيهم، لا
هنا مرة واحدة، مش أربعة، هنا المفروض ما عدلناهاش مرة
واحدة، وهي مرة واحدة، مرتين، تمام، هذه الـ I5 مرتين
يعني الـ tree تبعتنا هكذا بتكون سليمة، والعنصر
تبعتها موجودة في هذه الـ tree فعليًا اللي إحنا عاملينه
كنا بنحاول نرسمها، I2، I4، I5، بيمشي مع العناصر، اعفوا
I1، I5 مع ال transaction، I2، I4 هيها، I2، I3 هيها، في
كل مرة بأمر على I2 أنا بزيد ال counter تبعها لحد ما
تتحقق العناصر، ودائمًا بقصها بالمقاطعة هذه، جمعت خير
بس عشان أورّجيكم، هم وين النقاط اللي أنا عم بجمعهم
يعني هي هنا وهنا، هذول مع بعض بيمثلوا الستة، طيب تمام
أنا هكذا أنا حصلت على ال tree اللي موجودة عندي الآن
بدي أروح أشوف أنشئ ال conditional pattern تبعتي، أو
ال conditional pattern نعملها من الـ tree اللي موجودة
عندها، فممكن أنا أبدأ أمرّ على أو أعمل traversing للـ
tree اللي موجودة عندها عشان أشوف ال occurrence تبع
ال pattern اللي عندها الآن، المشكلة تبعتي كيف أنا
بدي أحصل على ال frequent pattern من ال database
تمام، ال database is transferred للـ tree، وهذا
الآن بدي أجيب من ال tree اللي عندها عشان تقدر تنقب
أو تطلع أو تعمل extraction، military، وتبني أو تعتمد
على ال conditional pattern اللي موجود عندك هنا
أبدأ مع ال frequent pattern اللي من واحد، as
initial suffix، suffix، يعني من البداية بدك تشتغل
Construct Conditional Pattern Based Which Consists
Of The Prefix Paths
In Every Tree Co-occurring With The Suffix In The
Motion، أبدأ مع الـ Tree اللي بتبدأ بالـ Suffix
اللي موجود عندك، Construct Conditional Pattern Tree
And Perform Mining On Such Tree، اللي عندك هنا، هيبدأ
يزيد معايا، growth is achieved by concatenation the
suffix مع ال frequent pattern اللي ظهر عندي، وأعيد
ذلك كثيرًا في خطوة أربعة، لحد ما تخلص ال tree، تعال
نشوف عندي هنا إيش اللي بيصير هنا، أو خليني أحتفظ
بفقط ال tree، وأشوف ال header إيش هذا بده عشان
بعدين بنشوفه، خليني بس أوقف هنا
الآن، عشان أنا أنشئ ال tree، أو أنا أبدأ أنشئ الـ
conditional ال pattern base، وال tree تبعتي، بناءً
على ال tree اللي موجودة عندنا، اللي أنشأناها
سابقا، الآن يا جماعة الخير، كان بيقول لي في المثال
السابق، أن أول حاجة أبدأ مع ال frequent pattern
length واحد، تمام؟ as initial suffix pattern، طيب
الفكرة، هل أنا بدي آخذ أي
اثنين، أو أي واحد، أو أي اثنين، أو أي اثنين، أو أي
اثنين، أو أي اثنين، أو أي اثنين، أو أي اثنين، أو أي
اثنين، أو أي اثنين، أو اثنين، أو اثنين، أو اثنين، أو
اثنين، أو اثنين، أو اثنين، أو اثنين، أو اثنين، أو اثنين
أو اثنين، أو اثنين، أو اثنين، أو اثنين، أو اثنين، أو
اثنين، أو اثنين، أو اثنين، أو اثنين، Depth Search، مظبوط
جالك Depth Search، Tree الـ Traversing، وبالتالي هو
بدوش أشتغل Breadth، بدوش أشتغل Depth، معناته Depth
بدّي أروح لأعمق نقطة، من أعمق نقطة؟ هذه النقاط
تبعتي، وأشتغل عليها، من النقاط اللي موجودة عندي في
ال leaves، يا جماعة الخير، I5، I4، I3، مظبوط، طيب وبعد
هنا كنت بدي أطلع لحد ما هي في عندي node، وبالتالي
النقاط تبعتها، كل العناصر، معدمين مع بعضهم، هذول
اللي موجودة فوق خالص، اللي هم جايين من النل، لأن هذول
هم بيمثلوا عندي، بيمثلوا المفتاح الأساس في الشغل، تمام
الآن، بما أن أنا هأشتغل، هأشتغل كالتالي، من خلال ال tree
اللي موجودة عندي، وزي ما قلنا، حأبدأ من ال I خمسة
إيه ال I خمسة؟ لا أنا بأصل لها من خلال مين يا جماعة
الخير؟ ال I خمسة أنا بأصل لها من خلال I اثنين و I
أربعة، عفواً، I2 و I1، كم مرة مرّيت عليهم عشان أصل للـ
element هذا؟ خليني، برضه، إحنا قلنا المعلومات تبعتنا
بدها تكون دائمًا موجودة عندي، خليني بس أجيب ال data
set عشان تظلّ حاضرة عندنا، هي هذه
وبدي أجيبها هنا على الآخر، لماذا
لا أشوف ال animation، حقيقية animation
team group، لا أريد animation حقيقية
كل هاي ال elements اللي أنا بدي أشتغل عليهم، طيب الـ
I الآن
جمعت الخيار، فهذا الجدول، هيلزمني عشان أنا أقدر
أتذكر أنا فعليًا ال conditional pattern base، أنا
وصلت للـ I خمسة، خلال الـ I5، أنا وصلت لها من خلال
وصلت لها مرتين، مرة من خلال I2 و I1 لحالهم، هذه كانت
مرة مظبوط، ومرة كانت من خلال I1 و I3، I2، I1، I3، هذه
كمان مرة، معناته أنا، هي ال path أو هي المسارات اللي
ودّتني لمين؟ ل I5 اللي موجودة هنا، وبناءً عليه أنا الـ
nodes اللي فعليًا بتهمّني في عدد تكرارها، مين اللي
ظهرت مرتين؟ عندها في ال conditional، I2 ظهرت مرتين، و
I1 ظهرت مرتين، I3 ما بتلزمني، لأنها ظهرت لمرة واحدة، طب
إيش ال frequent pattern اللي بنعملها generation؟
معناته أنا بقدر أجي أقول I2، I5، هذا frequent
pattern، وعدد مرات ظهوره اثنين، في عند I1، I5، وهذا عدد
مرات ظهوره برضه عدد مرات ظهوره اثنين، وفي عند ال pattern
الثالث اللي هو I2، I1، I5، اللي هو الـ combination
عفواً، لهم كلهم، لأن هذه frequent وهذه frequent، فلما
نضيفهم مع بعض، هيكون في عندي frequent، وهي ال pattern
تبعتها، وبالتالي هذه هي ال generated frequent
pattern اللي طلعت عندي، كمان مرة نشوفها مع I4، I4
إيش عمليات الوصول اللي كانت لها؟ كانت من خلال 2
هذه المسارات، I2 مباشرة لحالها، أي اثنين، كم مرة وصلت
لها؟ اللي، عفواً، عندها، أي اثنين، أي أربعة، كان عندي عدد
مرات الظهور، مرة عبر أي واحد، ومرة عبر أي اثنين، يعني
أي اثنين مرة واحدة، مظبوط، ومرة من خلال أي اثنين، أي
واحد، كذلك مرة
الآن، من يلزمّني من هؤلاء اللي أظهر مرتين على الأقل؟
الـ I2، معناته الـ Conditional Pattern Tree تبعتي
ال I2 مرتين، وبالتالي بأجي، ال frequent pattern
تبعتي، حتكون I2، I4، وهي ال support تبعتها، ال minimum
support تبعتها 2، بأجي للـ I3، بنفس الكلام، I3 كيف وصلت
لها؟ إيش المسارات تبعتها؟ I3، I3، I3، I3، I3، I3، I3، I3، I3، I3
I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3
I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3، I3
هنا برضه مرتين، عبر I2، I1، I2، I1، برضه مرتين، مين الـ
frequent pattern عندي هنا؟ كلهم frequent، لأن I1 و
I2 عبارة عن frequent patterns، وبالتالي الـ
conditional tree تبعتي، I2 ظهرت أربع مرات، و I1 ظهرت
مرتين، عفواً، أي واحد ظهرت مرتين كذلك، في عندي أي واحد
ظهرت لحالها، طبعاً أنا جمعت هذول الاثنين مع بعض، إن
هذي وهذي، في بينهم intersection، أو جايين مع بعضهم
صحيح، اللي هم في pattern واحد، فإذا أنا بأعتبر إن
هذي pattern واحد، معناته إن هي ال pattern اللي عندي
أو ال condition اللي أريه، وعندي هنا أي واحد ظهرت
لحالها مرتين، إيش ال frequent pattern اللي عندي
حتكلم على combination، I2، I3 مرتين، كذلك عندي I1، I3
عفواً، ليش مرتين؟ أربع مرات، لأن I2 أربع مرات ظهرت، هي
أربعة وهنا I3
أي، أي اثنين مرتين هنا و مرتين هنا يعني أربعة، مرتين
ومرتين يعني أربعة، وهنا في عندي أي اثنين، أي واحد
أي ثلاثة، وهذا كذلك ظهر مرتين، وبالتالي
أنا هاي ال patterns اللي موجودة عندي، وهكذا بتظهر
عندي بجهة ال letter، وبالتالي هذه الـ pre، كل الـ
patterns، هذه مجموعة الـ generated frequent
patterns اللي أنا اشتغلت عليهم، أعمل ما بين الـ
patterns هذول، عبارة عن ال association rules اللي
موجودة عندها، ال FP growth method transforms the
problem of finding long frequent patterns، حولت
لها من البحث عن long frequent patterns searching
for shorter ones recursively and concatenating the
suffix، ودائمًا بأجمع لها ال suffix اللي بتكون
موجودة، it uses the least frequent items as suffix
ليش؟ لأن هم هذول الموجودين تحت خالص، تمام، offering
good selectivity، وتوفر عليها الموضوع، وهذا اختيار
مناسب، the method .. the method، عفواً
substantially .. substantially reduces the search
cost، لأنها بتشتغلش في ال breadth، depth، عفواً الـ
search، طيب
خلينا، بدنا نشوف المثال التالي
هذا مثال .. مثال ثاني، تكمّلونه لوحدكم إن شاء الله
تعالوا، فرصة لكم تتدربوا وتشوفوا الخطوات، لإنشاء الـ
header tree، أو ال table السابق، وكيف إحنا اشتغلنا
عليه خطوة بخطوة، الآن بيقول لي أن في عندي transaction
data set من خمس عناصر، فيها ال elements اللي أنتَ
مشتركها، ال minimum support تبعتها، minimum support
معناته، يا جماعة الخير، بدي أجي أعدّ، والله، ال F واحدة
اثنين، ثلاثة، أربعة، أكبر من ال minimum support
معناته ال F frequent، ال A، مرة، اثنين، ثلاثة
ال A frequent، ال C، مرة، اثنين، ثلاثة، أربعة، ال C
frequent، هنا