k -means++

في مجالي استخراج البيانات والتعلم الآلي ، تُعدّ خوارزمية k -means++ ^{[ 1 ] [ 2 ]} خوارزمية لاختيار القيم الأولية/المراكز (أو "البذور") لخوارزمية التجميع k -means . وقد اقترحها ديفيد آرثر وسيرجي فاسيلفيتسكي عام 2007 كخوارزمية تقريبية لمسألة k - means الصعبة حسابيًا (NP-hard) ، وذلك لتجنب نتائج التجميع الضعيفة التي قد تنتجها خوارزمية k -means القياسية. وهي مشابهة لأولى طرق تحديد البذور الثلاث التي اقترحها رافائيل أوستروفسكي ويوفال رباني وليونارد شولمان وشايتانيا سوامي في عمل مستقل عام 2006 [ 3 ] . ^{( يختلف توزيع} البذرة الأولى).

تتمثل مشكلة خوارزمية k -means في إيجاد مراكز التجميع التي تُقلل التباين داخل الفئة، أي مجموع مربعات المسافات من كل نقطة بيانات يتم تجميعها إلى مركز مجموعتها (المركز الأقرب إليها). على الرغم من أن إيجاد حل دقيق لمشكلة k -means لأي مدخلات يُعدّ مسألة صعبة حسابيًا (NP-hard)، ^{[ 4 ]} فإنّ الأسلوب القياسي لإيجاد حل تقريبي (يُسمى غالبًا خوارزمية لويد أو خوارزمية k -means) يُستخدم على نطاق واسع، وغالبًا ما يُسفر عن حلول معقولة بسرعة.

ومع ذلك، فإن خوارزمية k -means تعاني من عيبين نظريين رئيسيين على الأقل:

• أولاً، لقد ثبت أن أسوأ وقت تشغيل للخوارزمية هو وقت متعدد الحدود فائق بالنسبة لحجم المدخلات. ^{[ 5 ]}
• ثانيًا، يمكن أن يكون التقريب الذي تم التوصل إليه سيئًا بشكل تعسفي فيما يتعلق بدالة الهدف مقارنة بالتجميع الأمثل.

تعالج خوارزمية k -means++ العقبة الثانية من خلال تحديد إجراء لتهيئة مراكز المجموعات قبل المضي قدمًا في تكرارات تحسين k -means القياسية. مع تهيئة k -means++، تضمن الخوارزمية إيجاد حلٍّ يُنافس حل k -means الأمثل من حيث زمن التهيئة O(log k ) . 

مثال على التجميع غير الأمثل

لتوضيح إمكانية أداء خوارزمية k -means بشكل سيئ للغاية فيما يتعلق بدالة الهدف المتمثلة في تقليل مجموع مربعات المسافات بين نقاط المجموعة ومركز ثقل مجموعاتها المخصصة، لنأخذ مثالًا لأربع نقاط في${\displaystyle \mathbb {R} ^{2}}$التي تشكل مستطيلاً محاذياً للمحاور يكون عرضه أكبر من ارتفاعه.

لو${\displaystyle k=2}$وبما أن مركزي التجميع الأوليين يقعان في منتصفي القطعتين المستقيمتين العلوية والسفلية للمستطيل المُشكّل من نقاط البيانات الأربع، فإن خوارزمية k -means تتقارب فورًا دون تحريك هذين المركزين. ونتيجةً لذلك، تتجمع نقطتا البيانات السفليتان معًا، وتتجمع نقطتا البيانات اللتان تُشكّلان الجزء العلوي من المستطيل معًا أيضًا - وهو تجميع غير مثالي لأن عرض المستطيل أكبر من ارتفاعه.

لنفترض الآن أننا نريد تمديد المستطيل أفقيًا إلى أي عرض مطلوب. ستستمر خوارزمية k -means القياسية في تجميع النقاط بشكل غير مثالي، وبزيادة المسافة الأفقية بين نقطتي البيانات في كل مجموعة، يمكننا جعل أداء الخوارزمية ضعيفًا للغاية مقارنةً بدالة هدف k -means.

يكمن الحدس وراء هذا النهج في أن توزيع مراكز التجميع الأولية k هو أمر جيد: يتم اختيار مركز التجميع الأول بشكل عشوائي ومنتظم من نقاط البيانات التي يتم تجميعها، وبعد ذلك يتم اختيار كل مركز تجميع لاحق من نقاط البيانات المتبقية باحتمالية تتناسب مع مربع المسافة من أقرب مركز تجميع موجود للنقطة.

الخوارزمية الدقيقة هي كالتالي:

1. اختر مركزًا واحدًا بشكل عشوائي ومنتظم من بين نقاط البيانات.
2. لكل نقطة بيانات x لم يتم اختيارها بعد، احسب D( x )، المسافة بين x وأقرب مركز تم اختياره بالفعل.
3. اختر نقطة بيانات جديدة عشوائيًا كمركز جديد، باستخدام توزيع احتمالي مرجح حيث يتم اختيار نقطة x باحتمالية تتناسب مع D( x ) ^² . وهذا يضمن اختيار نقطة مختلفة تمامًا عن المركز المحدد سابقًا كمركز تالٍ.
4. كرر الخطوتين 2 و 3 حتى يتم اختيار مراكز k .
5. بعد اختيار المراكز الأولية، تابع باستخدام التجميع القياسي k -means .

الشفرة الزائفة

يوضح الكود الزائف أدناه تطبيقًا لخوارزمية k-means++. kmeans()تقوم الدالة بتنفيذ إجراء التجميع القياسي لخوارزمية k-means .

الدالة kmeans++ (k, points) هي // تهيئة قائمة مراكز الثقل بنقطة واحدة مختارة عشوائياً المراكز ← قائمة فارغة firstIndex ← عدد صحيح عشوائي من 0 إلى طول (النقاط) - 1 centroids. append (points[firstIndex]) // اختر المراكز المتبقية k - 1 طالما أن طول (مراكز الثقل) < k نفّذ المسافات المربعة ← قائمة فارغة // لكل نقطة، احسب المسافة التربيعية إلى أقرب مركز محدد for i ← 0 to length (points) - 1 do نقطة ← نقاط[i] minDistance ← distance (point, centroids[0]) for j ← 1 to length(centroids) - 1 do d ← distance(point, centroids[j]) إذا كانت المسافة d < minDistance، فـ المسافة الدنيا ← د distancesSquared. append (minDistance * minDistance) // اختر المركز التالي باحتمالية تتناسب مع D(x)^2 المجموع الكلي ← مجموع مربعات المسافات العتبة ← رقم عشوائي من 0 إلى الإجمالي التراكمي ← 0 for i ← 0 to length(points) - 1 do التراكمي ← التراكمي + مربع المسافات[i] إذا كان المجموع التراكمي أكبر من أو يساوي العتبة، فأضف النقاط[i] إلى قائمة المراكز. ثم توقف. // تشغيل خوارزمية k-means clusters ← kmeans(k, points, centroids) إرجاع المجموعات

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

بالإضافة إلى ذلك، يحسب المؤلفون نسبة تقريب لخوارزميتهم. تضمن خوارزمية k -means++ نسبة تقريب O(log k ) في المتوسط ​​(على أساس عشوائية الخوارزمية)، حيث ${\displaystyle k}$يمثل عدد المجموعات المستخدمة. وهذا يختلف عن خوارزمية k -means التقليدية، التي قد تُنتج مجموعات أسوأ من الأمثل. ^{[ 6 ]} يُقدم تعميم لأداء خوارزمية k-means++ فيما يتعلق بأي مسافة عشوائية في ^{[ 7 ] .}

تم تطبيق خوارزمية k -means++ منذ اقتراحها الأولي. في مراجعة شيندلر ^{[ 8 ]} ، التي تشمل أنواعًا عديدة من خوارزميات التجميع، ذُكر أن هذه الطريقة تتغلب بنجاح على بعض المشكلات المرتبطة بطرق أخرى لتحديد مراكز التجميع الأولية لخوارزمية k -means. وقد أبلغ لي وآخرون ^{[ 9 ]} عن تطبيق لخوارزمية k -means++ لإنشاء مجموعات جغرافية من الصور الفوتوغرافية بناءً على معلومات خطوط الطول والعرض المرفقة بها. كما أبلغ هوارد وجوهانسن ^{[ 10 ]} عن تطبيق لها في مجال التنويع المالي . وتتوفر أيضًا أدلة أخرى تدعم هذه الطريقة ومناقشات جارية على الإنترنت ^{[ 11 ]} . ونظرًا لأن تهيئة خوارزمية k-means++ تتطلب k من المرور على البيانات، فإنها لا تتناسب جيدًا مع مجموعات البيانات الكبيرة. وقد اقترح بهماني وآخرون نسخة قابلة للتوسع من خوارزمية k-means++ تُسمى k-means|| (وتُقرأ "k-means parallel")، والتي توفر نفس الضمانات النظرية، ومع ذلك فهي قابلة للتوسع بدرجة كبيرة ^{[ 12 ] .}

• يحتوي Accord.NET على تطبيقات C# لـ k -means و k -means++ و k -modes.
• تحتوي مكتبة ALGLIB على تطبيقات متوازية بلغة C++ و C# لخوارزمية k -means و k -means++.
• يحتوي Apache Commons Math على k-means++
• يحتوي إطار عمل ELKI لاستخراج البيانات على العديد من متغيرات k-means، بما في ذلك k-means++ للتهيئة.
• يحتوي برنامج MATLAB على تطبيق K-Means يستخدم k-means++ كإعداد افتراضي للتهيئة.
• يحتوي OpenCV على تطبيق K-means بلغة C++ ولغة Python (مع تهيئة اختيارية لبذور k-means).
• يتضمن Orange واجهة مستخدم k-means++ ودعم API
• تتضمن لغة البرمجة R خوارزمية k-means، ويمكن لحزمة "flexclust" تنفيذ خوارزمية k-means++
• يحتوي scikit-learn على تطبيق K-Means الذي يستخدم k-means++ بشكل افتراضي.
• يحتوي برنامج Weka على خوارزمية التجميع k-means (مع خوارزمية k-means++ الاختيارية) وخوارزمية التجميع x-means.