خوارزميات تعلم الآلة
عنقدة البيانات (Data clustering) > خوارزمية العنقدة بالوسطاء المتعددين (K-means Clustering)

هي خوارزميه لجمع عدد من البيانات استادا إلى خصائص وسمات هذه البيانات، وتتم عمليه التجميع من خلال تقليل المسافات بين البيانات ومركز التجمع (cluster centroid).
وتتم هذه الخوارزمية من خلال الخطوات التالية:-
حساب إحداثيات مراكز التجميع
حساب المساقه بين كل البيانات ومراكز التجميع.
تجميع البيانات وتنظيمها في مجموعات بناء على اقل المسافات بين المركز ونقاط البيانات.
اعاده تنفيذ الخطوات من 1 – 3 حتى الوصول إلى حاله الثبات
يعتمد أداء هذه الخوارزمية على المواقع الأولية لمراكز التجمع (Centroid)، ومن المستحسن تنفيذ هذه الخوارزمية عدة مرات مع اختلاف المراكز في كل مرة عن المرات السابقة.
نفترض لدينا أربعة أنواع من الأدوية، وكل نوع من الأدوية لديه عدد من السمات، في هذا المثال كل نوع له سمتان.
| نوع الدواء (medicine) | مؤشر الوزن (Weight Index) | معامل الحموضة (pH) |
| --- | --- | --- |
A: 1
| B | 2 | 1 |
| C | 4 | 3 |
| D | 5 | 4 |
الهدف من هذا المثال، هو جمع أنواع هذه الأدوية في مجموعتين اعتمادا على سمات كل نوع من الأدوية، ولتحقيق هذا الهدف علينا تنفيذ خطوات خوارزمية التجميع التي سبق ذكرها.
1.القيم الابتدائية لمراكز التجمع: نفترض أن الدواء A والدواء B هما مراكز التجمع الأولى. لتكن c1 و c2 تدل على إحداثيات المراكز، حيث أن (c1=(1,1 و (c2=(2,1.
يبين الشكل 1.1 توزيع أنواع الأدوية المعبر عنها بالمعين الأزرق على المستوى الريكاردي، كما يبين مراكز التجمع الابتدائية، مع الأخذ بعين الاعتبار أن هذه المراكز تم افتراضها بشكل عشوائي.
2. المسافات بين النقاط والمراكز: نحسب المسافة بين مركز التجمع وكل نقطة من النقاط في المستوى. فينتج لدينا مصفوفة من المسافات.
كل عمود في مصفوفة المسافات يمثل نوع دواء واحد. الصف الأول من مصفوفة المسافات يتكون من المسافات بين كل نقطة ومركزالتجمع الأول، والصف الثاني يتكون من المسافات بين كل نقطة ومركزالتجمع الثاني. على سبيل المثال، المسافة بين الدواء C ومركز التجمع الأول هي:
والمسافة بين نفس الدواء ومركز التجمع الثاني هي: c، إلخ.
3. تجميع النقاط: نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. وهكذا، فان الدواء الأول (A) ينتدب إلى المجموعة الأولى، الدواء الثاني (B) إلى المجموعة الثانية، الدواء الثالث (C) إلى المجموعة الثانية، والدواء الرابع (D) يعود للمجموعة الثانية. ينتج لدينا مصفوفة المجموعات G التي تتكون من القيم 1 و 0، ويكون العنصر في مصفوفة المجموعات يساوي 1 فقط إذا كان الدواء مسند إلى تلك المجموعة.
4. التكرار الأول، تحديد مراكز التجمع: بعد معرفة عناصر كل مجموعة، نحسب مركز جديد لكل مجموعة اعتمادا على هذه العضويات الجديدة، كما يظهر في الشكل 1.2. المجموعة الأولى تتكون من عنصر واحد فقط، وتبقى إحداثيات مركز التجمع الأول كما هي دون تغيير (c1=(1,1.أما المجموعة الثانية والتي تتكون من ثلاث عناصر، تتغير إحداثيات مركز التجمع الثاني بالاعتماد على إحداثيات العناصر الثلاثة:
5. التكرار الأول، المسافات بين النقاط والمراكز: في هذه الخطوة يتم حساب المسافة بين كل نقطة ومراكز التجمع الجديدة. كما في الخطوة الثانية، ينتج لدينا مصفوفة من المسافات.
6. التكرار الأول، تجميع النقاط: على غرار الخطوة الثالثة، نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. بالعودة إلى مصفوفة المسافات الجديدة، ننقل الدواء الثاني (B) إلى المجموعة الأولى، بينما تبقى باقي الأدوية كما هي. تظهر مصفوفة المجموعات كالتالي
7. التكرار الثاني، تحديد مراكز التجمع: الآن نقوم بإعادة الخطوة الرابعة لحساب إحداثيات مراكز التجمع الجديدة بالاعتماد على عملية التجميع في التكرار الأول. يتكون كل من المجموعة الأولى والثانية من عنصرين، كما أن الإحدثيات الجديدة لمراكز التجمع تصبح
8. التكرار الثاني، المسافات بين النقاط والمراكز: نكرر الخطوة الثانية، فينتج لدينا مصفوفة مسافات جديدة كما يلي:
9. التكرار الثاني، تجميع النقاط:، مرة أخرى نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة.
ينتج لدينا في النهاية. بمقارنة التجمع بين التكرار الأول والتكرار الثاني، نلاحظ أن المجموعات لم تتغير من حيث عناصرها. هذا يعني أن عملية الحسابات في ال (k-mean clustering) وصلت إلى حالة الثبات، وهذا يعني أن هذه الخوارزمية لم تعد بحاجة إلى المزيد من التكرار، وبالتالي حصلنا على النتيجة النهائية للتجميع.