5 خوارزميات تجميع ينبغي على كل عالم بيانات الإلمام بها

كتابة: George Seif   ترجمة: البتول العيظه   مراجعة: فارس القنيعير

خوارزميات التجميع (Clustering) من أكثر الخوارزميات استعمالاً في تعلم الآلة (Machine Learning) تحت تصنيف التعلم من دون إشراف (Unsupervised Learning)، وهو أسلوب شائع لتحليل البيانات الإحصائية المستخدمة في العديد من المجالات. تعمل خوارزميات التجميع على تصنيف نقاط البيانات المتشابهة إلى مجموعات محددة (Clusters). حيث أن نقاط البيانات المصنفة بنفس المجموعة لها خصائص أو ميزات متشابهة، بينما نقاط البيانات المصنفة في مجموعات مختلفة لها خصائص أو ميزات مختلفة للغاية.

وللتوضيح: نقاط البيانات المقصود فيها، الملاحظات (Observations) أو الصفوف (Rows) الموجودة في البيانات، وعلى سبيل المثال: تصنيف المنتجات التي تتشارك قيم أرباح متشابهة إلى مجموعات.

دعونا نبدأ! …

1. خوارزمية التجميع بالمتوسطات (K-Means)

خوارزمية التجميع (K-Means) من أكثر خوارزميات التجميع المعروفة بين علماء البيانات، وتقدّم في كثير من المحاضرات المتعلقة بعلوم البيانات؛ لسهولة فهمها و تطبيقها. انظر إلى الصورة المتحركة أدناه للتوضيح.

الخطوات

1. في البداية سنقوم يدوياً باختيار عدد المجموعات المتوقعة (N)، ثم ستقوم الخوارزمية بتحديد النقاط المركزية لكل مجموعة بشكل عشوائي. ولمعرفة عدد المجموعات (N)، سنقوم بصرياً بالقاء نظرة سريعة على البيانات وتوقع عدد المجموعات المحتملة والمتميزة عن بعض. النقاط المركزية هي متجهات بنفس طول كل متجه من متجهات نقاط البيانات وهي (X) في الصورة المتحركة أعلاه، وهنا نجد أيضاً أن N = 3.
2. ولتصنيف انتماء أي نقطة بيانات لمجموعة محددة، سيتم حساب المسافة بين تلك النقطة ومركز كل مجموعة (X) ، ومن ثم تصنيف النقطة لتكون في المجموعة التي يكون مركزها (X) الأقرب (الأصغر مسافة) لتلك النقطة.
3. وعندما ننتهي من تصنيف جميع النقاط، سنقوم بتغيير مواقع مراكز المجموعات (X) عن طريق إعادة حساب مركز كل مجموعة، بأخذ متوسط (mean) قيمة جميع متجهات النقاط التي صنفت مؤخراً في تلك المجموعة.
4. أخيراً، سنقوم بتكرار الخطوات من 1 إلى 3 لعدد معين من المرات، حتى نحصل على نتيجة مقنعة، أو حتى لا نجد أي تغيير ملحوظ لمراكز المجموعات (X).

من مميزات خوارزمية  ( K -Means)  أنها سريعة جداً؛ لقلة الحسابات المستخدمة لتحديد المجموعات ومراكزها، حيث أن تعقيد الخوارزمية والوقت المستهلك لكامل العملية، فقط تزيد خطياً بزيادة مجموع عدد النقاط الموجودة في البيانات (O(n.

من ناحية أخرى، توجد بعض السلبيات:

• كما نعلم، تحديد عدد المجموعات (N) يتم يدوياً وبدون مساعدة من الخوارزمية، لكن من المهم للمستخدم أن تقوم هذه العملية باستخدام الخوارزمية؛ لمساعدة المستخدم على فهم طبيعة البيانات، والحصول على بعض التطلعات.
• الخوارزمية تقوم بدايةً بتحديد النقاط المركزية (X) بشكل عشوائي، مما يؤدي إلى عدم التناسق و نتائج غير قابلة للإعادة؛ حيث أننا سوف نحصل على نتائج (مراكز مجموعات) مختلفة في كل مرة نقوم بتشغيل الخوارزمية على نفس البيانات!

وفي الجهة الأخرى، خوارزمية (K- Medians) هي خوارزمية تجميع أخرى تتعلق بخوارزمية ( K -Means) ، لكن بدلاً من إعادة حساب نقطة مركز المجموعة باستخدام المتوسط (mean) سنستخدم الوسيط (median) للمجموعة. (K- Medians) أقل حساسية تجاه القيم الشاذة (Outliers)؛ بسبب استخدام الوسيط، ولكنها أبطأ بكثير من خوارزمية ( K -Means).

ملاحظة: توجد البعض من التقنيات التي تساعدك بتحديد عدد المجموعات (N)، للمزيد من المعلومات والتطبيق العملي اضغط هنا

2. خوارزمية التجميع بالمتوسط المتحول (Mean-Shift)

خوارزمية التجميع (Mean-Shift) تعتمد على أسلوب النافذة المنزلقة (sliding-window) التي تحاول العثور على المناطق الكثيفة بنقاط البيانات. وهي أيضاً خوارزمية مركزية، بمعنى أن الهدف هو تحديد موقع النقاط المركزية لكل مجموعة من خلال تحديث انزلاق النافذة، وتحديث النقاط التي بداخلها ومن ثم أخذ متوسطهم (mean) كمركز للمجموعة. وفي حال كان لدينا العديد من النوافذ المرشحة كمركز للمجموعة الواحدة، تتم تصفية هذه النوافذ المرشحة في مرحلة ما بعد المعالجة للقضاء على النسخ المكررة تقريبًا، والإبقاء على نافذة واحدة لكل مجموعة، و تحديد نقطة المركز عن طريق متوسط (mean) النافذة. أنظر إلى الصورة المتحركة أدناه للتوضيح.

الخطوات

1. بدايةً للشرح المبسط للخوارزمية، سننظر في مجموعة من النقاط في الفضاء ثنائي الأبعاد، مثل الموضح في الصورة المتحركة أعلاه. نبدأ مع نافذة انزلاق دائرية الشكل، التي تحتوي عدد من النقاط (C) المختارة عشوائياً، ولديها نصف قطر ((Radius (r) كنواة للنافذة. العملية تشبه تسلق التل، الذي يقوم على تدريج حركة النواة بشكل متكرر إلى منطقة ذات كثافة أعلى، في كل خطوة حتى التقارب (Convergence).
2. في كل تكرار يتم انتقال النافذة المنزلقة إلى مناطق ذات كثافة أعلى من النقاط، مع انتقال نقطة المركز بحساب المتوسط لكل نافذة متنقلة أو متحولة (ومن هنا جاء اسم الخوارزمية). الكثافة داخل النافذة المنزلقة تتناسب مع عدد النقاط التي بداخلها.
3. ستقوم الخوارزمية بمواصلة انزلاق النافذة، حتى لا يكون هناك أي اتجاه آخر يمكن أن يستوعب نافذة جديدة بنقاط أكثر (كثافة أكبر) من النافذة السابقة. انظر إلى الصورة المتحركة أعلاه؛ نستمر في تحريك الدائرة ومن ثم نتوقف عندما لا تصبح النافذة الجديدة بنقاط أكثر (كثافتها أقل من السابقة).
4. عادةً تتم هذه العملية من الخطوات 1 إلى 3 مع العديد من النوافذ المنزلقة (كما في الصورة المتحركة أدناه)، حتى تقع كافة النقاط داخل نافذة واحدة. عندما تتداخل النوافذ المنزلقة، تقوم الخوارزمية على إبقاء النافذة الأعلى كثافة، والتي تحتوي على نقاط أكثر. وأخيراً، كل نقطة بيانات ستنتمي للنافذة التي تقيم فيها كمجموعة لها.

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

على النقيض من (K-means)، في خوارزمية (Mean-Shift) لا توجد حاجة لتحديد عدد المجموعات (N) مسبقاً، حيث أن الخوارزمية ستقوم تلقائياً بكشف عدد من المجموعات. طريقة عمل الخوارزمية بتحديد مناطق الكثافة تعتبر ميزة قوية، حيث أنها أيضاً بديهية الفهم ومتناسبة مع طبيعة توجه البيانات. لكن عملية تحديد حجم النافذة أو الدائرة (r) تعتبر من السلبيات لأنها تتم عشوائياً ويدوياً بدون مساعدة الخوارزمية.

ملاحظة: لمزيد من المعلومات والتطبيق العملي اضغط هنا

3. خوارزمية التجميع المكاني المستند إلى الكثافة للتطبيقات ذات الضوضاء (Density-Based Spatial Clustering of Applications with Noise (DBSCAN))

خوارزمية (DBSCAN) تعتمد على الكثافة مثل خوارزمية (Mean-Shift)، ولكن مع ميزتين إضافيتين و بارزتين. أنظر إلى الصورة المتحركة أدناه، ودعنا نبدأ!

الخطوات

1. تعتمد الخوارزمية على تحديد كل نقطة إذا تمت زيارتها أو لم تتم زيارتها. تبدأ الخوارزمية مع نقطة بيانات التي لم تتم زيارتها مسبقاً، ثم يتم استخراج النقاط المجاورة (neighborhood) لهذه النقطة، باستخدام مسافة إبسيلون (epsilon ε)، حيث أن جميع النقاط التي تقع ضمن مسافة ε هي نقاط مجاورة لتلك النقطة.
2. إذا كان هناك عدد كاف من النقاط المجاورة وفقا لأدنى حد من النقاط (minPoints) سوف تبدأ عملية التجميع، و تصبح نقطة البيانات الحالية هي النقطة الأولى في المجموعة الجديدة. و إذا لم يكن هناك عدد كافي من النقاط المجاورة، سيتم تحديد النقطة كضوضاء (لاحقاً هذه النقطة المعلمّة كضوضاء قد تصبح جزء من المجموعات). لكن في كلتا الحالتين، ستقوم الخوارزمية بتعليم هذه النقطة التي تشكل ضوضاء كنقطة تمت زيارتها.
3. بالنسبة لهذه النقطة الأولى في المجموعة الجديدة، جميع النقاط المجاورة لهذه النقطة (التي تكون ضمن نطاق مسافة إبسيلون ε) تصبح معها في نفس المجموعة الجديدة. ثم تتكرر هذه الخطوة لجميع النقاط التي أضيفت مؤخراً في المجموعة.
4. وتكرر الخطوات من 1 إلى 3 لكل مجموعة، إلى أن يتم تحديد جميع النقاط المجاورة، كنقطة تمت زيارتها للمجموعة الحالية.
5. بمجرد الانتهاء من المجموعة الحالية (عندما لا نجد نقاط إضافية مجاورة)، يتم البدء مجدداً من خطوة 1، وعشوائياً ستقوم الخوارزمية بتحديد نقطة جديدة لم يتم زيارتها مسبقاً، لمعالجتها و اكتشاف إذا كانت بداية لمجموعة جديدة أو مجرد ضوضاء لا تنتمي لمجموعة جديدة. هذه العملية تتكرر حتى يتم وضع علامة على كافة النقاط الموجودة في البيانات على أنه تمت زيارتها. وفي النهاية، ستقوم الخوارزمية بتعليم جميع النقاط، كنقاط منتمية لمجموعةٍ ما، أو مجرد ضوضاء.

خوارزمية (DBSCAN) تطرح مزايا منافسة مقارنة بخوارزميات التجميع الأخرى. أولاً، لا يتطلب مسبقاً من المستخدم تحديد عدد المجموعات (N). كما أنه يأخذ القيم المتطرفة أو الضوضاء (Outliers) بعين الاعتبار، على عكس الخوارزميتين السابقتين، حيث أن المتوسط (Mean) يتأثر بالقيم المتطرفة حتى لو كانت مختلفة جداً عن المجموعة. أيضاً تتميز الخوارزمية بقدرتها على تحديد شكل و حجم المجموعات بطريقة جيدة للغاية.

السلبية الرئيسية لخوارزمية (DBSCAN) هي أنها لا تؤدي لنتيجة جيدة عندما تكون المجموعات متفاوتة الكثافة. وذلك لأنه عندما نحدد نطاق أو عتبة مسافة إبسيلون ε و الحد الأدنى من النقاط المجاورة (minPoint) سوف نجد أداء مختلف باختيار النقاط المجاورة من مجموعة إلى مجموعة أخرى عندما تختلف الكثافة بينهم. هذه السلبية تحدث أيضاً في البيانات التي تتّسم بأبعاد عالية، حيث يصبح تحديد مسافة إبسيلون ε تحدياً كبيراً.

ملاحظة: لمزيد من المعلومات والتطبيق العملي اضغط هنا

4. خوارزمية التجميع بتعظيم القيمة المتوقعة (Expectation–Maximization (EM)) باستخدام نموذج جاوس المختلط (Gaussian Mixture Models (GMM))

واحدة من العيوب الرئيسية لخوارزمية (K-means)، هو استخدامها البسيط لقيمة متوسط المجموعة كمركز لها. يمكننا أن نرى لماذا هذه الطريقة ليست الأفضل للقيام بالتجميع لبعض البيانات، من خلال النظر إلى الصورة أدناه. على الجانب الأيسر يبدو لنا واضحاً تماماً للعين البشرية، أن هناك دائرتين مع أنصاف أقطار مختلفة، حيث نجد أن خوارزمية (K-means)  لا يمكنها التعامل مع هذا النوع من البيانات؛ لأن القيم المتوسطة للمجموعتين قريبة جدًا من بعضها البعض. أيضاً في الجانب الأيمن، نجد أن الخوارزمية فشلت في تحديد المجموعتين؛ لأن المجموعتين غير متمحورتين حول المركز أو المتوسط، وهذا الفشل يحدث بسبب استخدام متوسط المجموعات.

نموذج جاوس المختلط (GMMs) يعطينا المزيد من المرونة مقارنةً بخوارزمية (K-means). مع (GMMs) نفترض أن نقاط البيانات تتبع التوزيع الجاوسي (Gaussian distribution)، أي التوزيع الطبيعي. ومع افتراض أن البيانات تتبع هذا التوزيع، تقل القيود المفروضة. على العكس في خوارزمية (K-means)، نفترض أن البيانات دائرية ومتمحورة حول المتوسط ( المركز).

و بهذه الخوارزمية (GMMs)، لدينا مدخلين لوصف شكل المجموعات: المتوسط (Mean) والانحراف المعياري (Standard deviation). على سبيل المثال، في البيانات ثنائية الأبعاد يمكن للمجموعات أن تأخذ أي شكل من الأشكال البيضاوية (بما أنه لدينا الانحراف المعياري في كلاً من الاتجاهين x و y)، وبالتالي يتم تعيين كل توزيع جاوسي (GMM) إلى مجموعة واحدة.

ومن أجل العثور على مدخلات جاوس لكل مجموعة (مثل المتوسط والانحراف المعياري)، سوف نستخدم خوارزمية تحسين (Optimization algorithm) تسمى تعظيم القيمة المتوقعة (Expectation–Maximization (EM)). أنظر إلى الصورة المتحركة أدناه، يوجد توضيح للتوزيع الجاوسي (GMMs) على المجموعتين. بعد ذلك، يمكننا المضي قدماً في عملية التجميع (EM) باستخدام (GMMs).

الخطوات

1. نبدأ بتحديد عدد المجموعات (N)، وبشكل عشوائي سنقوم يدوياً بتحديد مدخلات التوزيع الجاوسي لكل مجموعة. ويمكننا أيضاً أن نحاول تخمين المدخلات الأولية، من خلال إلقاء نظرة سريعة على البيانات. لكن ليس من الضروري محاولة إيجاد المدخلات عن طريق النظر للبيانات، كما نرى في الصورة المتحركة أعلاه، بدأ التوزيع بشكل ضعيف جداً، ثم تحسنت النتائج بشكل سريع من خلال التكرار.
2. بناءً على توزيعات جاوسي المعطاة لكل مجموعة، ستقوم الخوارزمية بحساب احتمالية انتماء كل نقطة بيانات إلى توزيع أو مجموعة معينة. كلما كانت النقطة أقرب إلى مركز (متوسط) التوزيع الجاوسي للمجموعة الواحدة، كلما كان من المرجح أن تنتمي إلى تلك المجموعة (التوزيع) ، وهذا أمر بديهي بما أننا نفترض أن أغلب البيانات في المجموعة، قريبة من مركز المجموعة.
3. استناداً إلى هذه الاحتمالات، ستقوم الخوارزمية بتحديث حسابات جديدة من المدخلات لتوزيعات جاوس لكل مجموعة، حيث أنها تقوم بأقصى زيادة لاحتمالية انتماء النقاط لتوزيع أو مجموعة معينة.
4. يتم إعادة الخطوتين 2 و 3 بشكل متكرر حتى الوصول إلى حالة التقارب، حيث أنه مهما قمنا بتكرار الخطوات لا تتغير التوزيعات (GMMs) بشكل ملحوظ.

يتم حساب هذه المدخلات الجديدة عن طريق استخدام الجمع الموزون (weighted sum) لأماكن نقاط البيانات، حيث أن وزن كل نقطة يشير إلى مدى احتمالية انتمائها لمجموعة معينة. ولشرح العملية بشكل أفضل، نجد في الصورة المتحركة أعلاه، وعلى وجه الخصوص سنأخذ المجموعة الصفراء كمثال، نرى أن التوزيع يبدأ للمجموعة الصفراء بشكل عشوائي في التكرار الأول، ونلاحظ أن معظم النقاط الصفراء تقع يمين أعلى المجموعة أو التوزيع، وعندما نقوم بحساب وزن احتمالية انتماء النقاط الصفراء للمجموعة، نجد أنها قريبة للمجموعة الصفرا من المجموعة البرتقالية، لكن!  بالرغم من ذلك، أغلب النقاط بعيدة في جهة اليمين. وبالتالي بطبيعة الحال، في التكرارات الأخرى سوف يتم تحديث وتحويل متوسط التوزيع أو المجموعة الجديد بشكل أقرب إلى النقاط الواقعة يمين التوزيع. يمكننا أيضاً ملاحظة أن معظم النقاط التابعة للمجموعة الصفراء هي “من أعلى اليمين إلى أسفل اليسار”؛ ولذلك يتغير الانحراف المعياري لإنشاء مجموعة بيضاوية أكثر تناسباً لاتجاه وتوزيع هذه النقاط، مما يؤدي إلى الوصول إلى أقصى زيادة لاحتمالية النقاط الصفراء بأن تكون منتمية للمجموعة الصفراء؛ عن طريق القرب من مركزها الحقيقي.

تتميز هذه الخوارزمية بنقطتين:

• أولاً، خوارزمية (GMMs) أكثر مرونة من حيث  التغاير المجموعي (cluster covariance) مقارنةً بخوارزمية (K-means)؛ وذلك بسبب مدخل الانحراف المعياري، التي يمكن أن تميز المجموعات التي تكون على أي شكل بيضاوي، أو شكل ناقص غير دائري. خوارزمية (K-means) هي في الواقع حالة خاصة لخوارزمية (GMM)؛ حيث أن تغاير أو تباين كل مجموعة من خلال كل الأبعاد يساوي صفراً.
• ثانياً، بما أن (GMMs) تستخدم أسلوب الاحتمالات، من الممكن أن تصنف نقطة البيانات الواحدة ضمن أكثر من مجموعة في نفس الوقت. لذلك إذا كانت النقطة مرجحة بأن تكون في مجموعتين، نستطيع ببساطة أن نصنفها لكل فئة بناءً على احتمالية أن تكون فيه تلك الفئة، على سبيل المثال: نقطة البيانات تنتمي بنسبة X للمجموعة الأولى، ونسبة X للمجموعة الأخرى. بمعنى آخر، (GMMs) تدعم الاختلاط ومن هنا جاءت التسمية.

ملاحظة: لمزيد من المعلومات والتطبيق العملي اضغط هنا

5. خوارزمية التجميع الهرمية (Agglomerative Hierarchical)

بشكل عام، خوارزميات التجميع الهرمية تنقسم إلى فئتين: التجميع الهرمي من الأعلى إلى الأسفل (Divisive clustering)، أو من الأسفل إلى الأعلى (Agglomerative Hierarchical). خوارزمية التجميع من الأسفل إلى الأعلى تقوم بالبداية بمعاملة كل نقطة بيانات كمجموعة مستقلة بذاتها، ومن ثم تبدأ بالتدريج بدمج أزواج من نقاط البيانات المتشابهة، مكونة مجموعات جديدة، تستمر العملية حتى يتم دمج كل المجموعات تحت مجموعة واحدة. وبالتالي يطلق على التجميع الهرمي من أسفل إلى أعلى: التكتل الهرمي (Agglomerative Hierarchical)  أو  (HAC). يتم تمثيل هذا التسلسل الهرمي كشجرة أو (dendrogram). حيث أن جذر الشجرة هو مجموعة فريدة من نوعها، حيث تجمع كل نقاط البيانات، وأوراق الشجرة تمثل نقاط البيانات كمجموعات فردية (من نقطة واحدة فقط). أنظر للصورة المتحركة بالأسفل للمزيد من التوضيح قبل الانتقال لشرح خطوات الخوارزمية.

الخطوات

1. نبدأ بالتعامل مع كل نقطة بيانات فردية كمجموعة بحد ذاتها؛ أي إذا كان لدينا عدد من نقاط البيانات تساوي X، سوف نحصل في البداية على عدد مجموعات (N) تساوي X. لاحقاً سنقوم بقياس المسافة بين المجموعات الفردية. يوجد عدة مقاييس للمسافة من الممكن استخدامها مع التجميع الهرمي، على سبيل المثال، سنستخدم متوسط الربط (average linkage) الذي يحدد المسافة بين مجموعتين، لتكون المسافة المحسوبة هي متوسط المسافة بين نقاط البيانات في المجموعة الأولى، ونقاط البيانات في المجموعة الثانية.
2. في كل مرحلة تكرار نقوم تدريجياً بدمج مجموعتين في مجموعة واحدة، ويتم اختيار المجموعتين اللتين سيتم دمجهما بناءً على المجموعتين ذات المسافة الأقصر (أصغر قيمة لمتوسط الربط)؛ أي وفقا لقصر المسافة تعتبر المجموعتين المدموجتين أكثر تشابهاً.
3. يتم تكرار الخطوة 2 حتى نصل إلى جذر الشجرة؛ أي يصبح لدينا مجموعة أو كتلة واحدة فقط والتي تحتوي على جميع نقاط البيانات. وفي النهاية يمكننا اختيار عدد المجموعات (N) التي نريدها، ببساطة بتحديد متى نتوقف عن الجمع بين المجموعات؛ أي عندما نتوقف عن بناء الشجرة ونقوم بقطعها (tree cut-off).

لا يتطلب التجميع الهرمي بتحديد عدد المجموعات (N) مسبقاً، حيث يمكننا تحديد عدد المجموعات لاحقاً، بناءً على المجموعات التي تبدو أفضل بصرياً عند قطع الشجرة بعد بنائها. بالإضافة إلى أن الخوارزمية غير حساسة لاختيار نوع مقياس المسافة (distance measure)؛ كل مقياس يعمل بشكل جيد، ويعطي نفس النتائج بشكل تقريبي، على العكس من باقي الخوارزميات، تتأثر بشكل كبير وتعطي نتائج مختلفة تماماً عند اختلاف مقياس المسافة المستخدم ، واختيارها أمر في بالغ الأهمية.

وعملياً، من الأمثل استخدام خوارزمية التجميع الهرمي في حالة معرفتنا السابقة بوجود تسلسل هرمي للبيانات، ونرغب من الخوارزمية أن تكشف لنا النمط الهرمي بين البيانات، وهذا لا يمكن الوصل له باستخدام الخوارزميات الأخرى. ولكن من السلبيات، عملية التسلسل الهرمي منخفضة الكفاءة مقارنة بباقي الخوارزميات، نظراً لزيادة التعقيد الخطي و الوقت المستهلك لبناء المجموعات، حيث أنها تزيد بشكل أسّي (O(n³، على عكس التعقيد الخطي لـ (K-Means) و (GMM).

ملاحظة: للمزيد من المعلومات والتطبيق العملي اضغط هنا

في الختام

لقد تطرقنا لخمس خوارزميات تجميع ينبغي على كل عالم بيانات الإلمام بها! وسوف ننهي المقال بعرض صورة رائعة توضح أداء الخوارزميات المذكورة في هذا المقال وأخرى! على مجموعة من أشكال البيانات المختلفة. للمزيد من المعلومات، الصورة مأخوذة من ScikitLearn.