في K-means++ الأصلية، يختار المركز الأول عشوائيًا بالتساوي، ثم تتناسب فرصة النقطة مع مربع بعدها عن أقرب مركز مختار. [1]
الخلاصة السريعة
تهيئة K-means++ توزع فرص البداية وفق المسافات؛ لا تفرض اختيار النقطة الأبعد دائمًا، ولا تجعل كل تشغيل حلًا مثاليًا.
- في النسخة الأصلية غير المرجحة، يبدأ الاختيار بالتساوي؛ المسافات اللاحقة تقاس إلى أقرب مركز مختار. [1]
- مع النقاط 0 و 1 و 5 و 6، وبشرط اختيار صفر أولًا، تكون فرص الاختيار الثاني 0 و 1/62 و 25/62 و 36/62.
- إذا اختيرت 5 ثانيًا، تصبح فرص 1 و 6 متساوية عند اختيار ثالث؛ نعيد الحساب إلى أقرب المركزين، لا إلى الأخير فقط.
- الضمان الأصلي حد على الكلفة المتوقعة، بينما تنفذ المكتبة افتراضيًا تهيئة جشعة متعددة المحاولات المحلية. [1] [2]
ما الذي نثبته قبل حساب الفرص؟
نستعمل أربع نقاط على خط عددي: 0 و 1 و 5 و 6، بمسافة إقليدية وأوزان متساوية. ندرس النسخة الأصلية من التهيئة وحدها، قبل إسناد النقاط إلى مجموعات وتحديث مراكزها.
نفترض أن السحب الأول أعطى صفرًا. هذا شرط لبقية الحساب، وليس نتيجة حتمية؛ كان يمكن أن يبدأ السحب من نقطة أخرى. ولا نختار صفرًا لأنه أصغر قيمة أو لأنه يمثل المجموعة أفضل.
اكتب المراكز المختارة في قائمة منفصلة عن النقاط المرشحة. بهذه الطريقة نعرف ما الذي يحدد المسافة في الجولة الحالية، ونميز السحب العشوائي من النتيجة التي افترضناها للتوضيح.
لماذا لا يفوز الأبعد دائمًا؟
المسافات إلى صفر هي 0 و 1 و 5 و 6. مربعاتها 0 و 1 و 25 و 36، ومجموعها 62. نقسم كل مربع على 62 لنحصل على فرصة النقطة في السحب التالي.
النقطة 6 صاحبة الفرصة الأكبر: 36/62، أي نحو 58.1%. لكن النقطة 5 لها فرصة 25/62 أيضًا. لذلك يمكن أن يقع الاختيار على 5، رغم أن بعدها أقل من بعد 6.
هذه فرص سحب في مثال مشروط، وليست احتمالات صحة المجموعات. ولم نسحب أرقامًا عشوائية أو نشغل البرنامج؛ حسبنا توزيع الجولة حتى نفهم لماذا تختلف البدايات الممكنة.
كيف يتغير الحساب بعد إضافة مركز؟
لنفترض اختيار 5 ثانيًا، ونريد مركزًا ثالثًا. أصبحت قائمة المراكز {0، 5}. المسافة المطلوبة لكل نقطة هي الأصغر بين بعدها عن صفر وبعدها عن 5.
مربعات هذه المسافات هي 0 و 1 و 0 و 1. مجموعها اثنان؛ لذلك فرصتا 1 و 6 تساويان النصف، وفرصتا المركزين المختارين تساويان صفرًا. بعد 6 عن صفر لم يعد أساس حسابها.
الاعتماد على المركز الأخير وحده سيعطي صفرًا مسافة خمسة رغم أنه مركز موجود بالفعل. هذا الخطأ في سجل الحساب يشرح أهمية كلمة «أقرب» في القاعدة، دون الحاجة إلى مثال كبير.
أي نسخة تقرأ وأي ضمان تقصد؟
تقدم الورقة الأصلية حدًا للكلفة المتوقعة عبر الاختيارات العشوائية، لا ضمانًا للنتيجة المثالية في كل تشغيل. [1]
في kmeans_plusplus الموثقة، يتيح n_local_trials=1 النسخة الأصلية؛ القيمة الافتراضية تستخدم محاولات محلية متعددة وتختار الأفضل بينها. [2]
لذلك سجل اسم التنفيذ وإعداداته قبل مقارنة مراكز فعلية بتوزيعنا البسيط. الحساب هنا لا يتنبأ بالمركز الذي سيخرجه تنفيذ جشع، ولا يحدد عدد المجموعات المناسب للبيانات؛ إنه يشرح كيف تبنى بداية محددة.
المصادر ومتابعة القراءة
- Arthur and Vassilvitskii: k-means++ (يفتح في نافذة جديدة)theory.stanford.edu
- scikit-learn: kmeans_plusplus (يفتح في نافذة جديدة)scikit-learn.org
أُعدّ هذا المقال بصياغة عربية أصلية بالاستناد إلى المصادر أعلاه، وهو مدخل تمهيدي إلى الموضوع. اقرأ منهجية المحتوى وحدوده.