خوارزميات التجميع: من البداية إلى حالة الفن

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

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

K-Means Clustering

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

تبدأ الخوارزمية باختيار نقاط k كنقطة انطلاق ("مراكز" المجموعات). يمكننا فقط تحديد أي نقطة عشوائية k ، أو يمكننا استخدام طريقة أخرى ، لكن اختيار نقاط عشوائية يعد بداية جيدة. ثم نكرر بشكل متكرر خطوتين:

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

2. خطوة التحديث: لكل مجموعة ، يتم حساب النقطه الوسطى الجديدة كمتوسط ​​لجميع النقاط في الكتلة. من الخطوة السابقة ، لدينا مجموعة من النقاط التي تم تخصيصها لمجموعة. الآن ، لكل مجموعة من هذه المجموعات ، نحسب متوسطًا نعلنه عن النقطه الوسطى الجديدة من الكتلة.

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

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

يمكن أن تعتمد الطرق الأخرى لاختيار النقاط الأولية على اختيار النقاط البعيدة. يمكن أن يؤدي هذا إلى نتائج أفضل ، ولكن قد تكون لدينا مشكلة مع القيم المتطرفة ، تلك النقاط النادرة الوحيدة التي تكون "متوقفة" فقط والتي قد تكون مجرد بعض الأخطاء. نظرًا لأنها بعيدة كل البعد عن أي مجموعة ذات مغزى ، فقد ينتهي الأمر بكل نقطة من هذا القبيل لتكون "مجموعة" خاصة بها. التوازن الجيد هو متغير K-Means ++ [Arthur and Vassilvitskii ، 2007] ، والذي سيظل التهيئة الخاصة به يختار نقاطًا عشوائية ، ولكن مع احتمال يتناسب مع المسافة المربعة من النقط الوسطى المعينة سابقًا. سيكون للنقاط البعيدة احتمال أكبر ليتم اختيارها كنقاط بداية. وبالتالي ، إذا كانت هناك مجموعة من النقاط ، فإن احتمال اختيار نقطة من المجموعة يزداد أيضًا مع زيادة احتمالاتها ، مما يحل المشكلة الخارجية التي ذكرناها.

K-Means ++ هي أيضًا التهيئة الافتراضية لتطبيق Scikit-Learn K-Means في Python. إذا كنت تستخدم Python ، فقد تكون هذه هي مكتبتك المفضلة. بالنسبة إلى Java ، قد تكون مكتبة Weka بداية جيدة:

جافا (ويكا)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

بايثون (Scikit-Learn)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

في مثال Python أعلاه ، استخدمنا نموذجًا قياسيًا لمجموعة بيانات "Iris" ، والتي تحتوي على بتلات الزهور وأبعاد sepal لثلاثة أنواع مختلفة من القزحية. قمنا بتجميع هذه المجموعات في ثلاث مجموعات ، وقارننا المجموعات التي تم الحصول عليها بالأنواع الفعلية (الهدف) ، لنرى أنها تتطابق تمامًا.

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

تتمثل إحدى طرق التعامل مع هذه المشكلة في تضمين بعض العقوبة لعدد أكبر من المجموعات. لذلك ، نحاول الآن تقليل ليس فقط الخطأ ، ولكن الخطأ + العقوبة . سيقترب الخطأ من الصفر حيث نزيد عدد المجموعات ، لكن العقوبة ستزداد. في بعض النقاط ، سيكون الربح من إضافة مجموعة أخرى أقل من العقوبة المقدمة ، وسنحصل على النتيجة المثلى. الحل الذي يستخدم معيار المعلومات البايزية (BIC) لهذا الغرض يسمى X-Means [Pelleg and Moore ، 2000].

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

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

الكتلة EM

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

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

تعيد M-step الآن حساب معلمات كل مجموعة ، باستخدام تعيينات النقاط إلى المجموعة السابقة من المجموعات. لحساب المتوسط ​​الجديد والتغاير والوزن للمجموعة ، يتم ترجيح بيانات كل نقطة من خلال احتمالية الانتماء إلى الكتلة ، كما تم حسابه في الخطوة السابقة.

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

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

انتشار التقارب

تم نشر Affinity Propagation (AP) بواسطة Frey and Dueck في عام 2007 ، ولا يزال أكثر شيوعًا نظرًا لبساطته وقابليته للتطبيق بشكل عام وأدائه. إنه يغير وضعه من حالة الفن إلى المعيار الواقعي.

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

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

1. أوجه التشابه بين نقاط البيانات ، والتي تمثل مدى ملاءمة نقطة ما لتكون نموذجًا آخر. إذا لم يكن هناك تشابه بين نقطتين ، حيث لا يمكن أن تنتمي إلى نفس المجموعة ، يمكن حذف هذا التشابه أو تعيينه إلى -Infinity اعتمادًا على التنفيذ.

2. التفضيلات ، التي تمثل ملاءمة كل نقطة بيانات لتكون نموذجًا. قد يكون لدينا بعض المعلومات المسبقة التي يمكن تفضيلها لهذا الدور ، وبالتالي يمكننا تمثيلها من خلال التفضيلات.

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

ثم يتم تشغيل الخوارزمية من خلال عدد من التكرارات ، حتى تتقارب. يحتوي كل تكرار على خطوتين لتمرير الرسائل:

1. حساب المسؤوليات: تعكس المسؤولية r (i، k) الأدلة المتراكمة على مدى ملاءمة النقطة k للعمل كنموذج للنقطة i ، مع الأخذ في الاعتبار النماذج المحتملة الأخرى للنقطة i. يتم إرسال المسؤولية من نقطة البيانات i إلى نقطة النموذج المرشح k.

2. حساب التوفر: يعكس التوافر أ (i ، k) الأدلة المتراكمة حول مدى ملاءمة اختيار النقطة k كنموذج لها ، مع الأخذ في الاعتبار الدعم من النقاط الأخرى التي يجب أن تكون النقطة k نموذجًا لها. يتم إرسال التوفر من نقطة نموذجية مرشح k إلى النقطة i.

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

إذن ، فإن حساب التوفر يستخدم المسؤوليات المحسوبة كدليل على ما إذا كان كل مرشح سيشكل نموذجًا جيدًا. يتم تعيين التوفر أ (i ، k) على المسؤولية الذاتية r (k، k) بالإضافة إلى مجموع المسؤوليات الإيجابية التي يتلقاها المرشح النموذجي k من نقاط أخرى.

أخيرًا ، يمكن أن يكون لدينا معايير إيقاف مختلفة لإنهاء الإجراء ، مثل عندما تكون التغييرات في القيم أقل من حد معين ، أو عند الوصول إلى الحد الأقصى لعدد التكرارات. في أي وقت من خلال إجراء نشر التقارب ، يمنحنا تلخيص مصفوفات المسؤولية (r) والتوافر (أ) معلومات التجميع التي نحتاجها: بالنسبة للنقطة i ، يمثل k بحد أقصى r (i، k) + a (i، k) النقطة أنا نموذجي. أو ، إذا احتجنا فقط إلى مجموعة النماذج ، فيمكننا مسح القطر الرئيسي. إذا كانت r (i، i) + a (i، i)> 0 ، فإن النقطة i هي نموذج.

لقد رأينا أنه باستخدام K-Means والخوارزميات المماثلة ، قد يكون تحديد عدد المجموعات أمرًا صعبًا. مع AP ، لا يتعين علينا تحديدها بشكل صريح ، ولكنها قد تظل بحاجة إلى بعض الضبط إذا حصلنا على مجموعات أكثر أو أقل مما قد نجدها أفضل. لحسن الحظ ، فقط من خلال تعديل التفضيلات يمكننا خفض أو زيادة عدد المجموعات. سيؤدي تعيين التفضيلات إلى قيمة أعلى إلى مزيد من المجموعات ، حيث تكون كل نقطة "أكثر يقينًا" من ملاءمتها لتكون نموذجًا وبالتالي يصعب "التغلب عليها" وإدراجها تحت "هيمنة" نقطة أخرى. وعلى العكس من ذلك ، سيؤدي تحديد تفضيلات أقل إلى وجود مجموعات أقل ؛ كما لو كانوا يقولون "لا ، لا ، من فضلك ، أنت مثال أفضل ، سوف أنضم إلى مجموعتك". كقاعدة عامة ، قد نقوم بتعيين جميع التفضيلات على متوسط ​​التشابه لعدد متوسط ​​إلى كبير من المجموعات ، أو إلى أدنى تشابه لعدد معتدل من المجموعات. ومع ذلك ، قد تكون هناك حاجة إلى عدة دورات مع ضبط التفضيلات للحصول على النتيجة التي تناسب احتياجاتنا تمامًا.

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

فى النهاية…

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

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

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

تستحق هذه الخوارزميات مقالًا خاصًا بها ، ويمكننا استكشافها في منشور منفصل لاحقًا.

يتطلب الأمر خبرة مع بعض التجارب والخطأ لمعرفة متى يجب استخدام خوارزمية أو أخرى. لحسن الحظ ، لدينا مجموعة من التطبيقات بلغات برمجة مختلفة ، لذا فإن تجربتها لا تتطلب سوى القليل من الرغبة في اللعب.