ما هي k-mane algorithm ؟

تعتبر خوارزمية k-mane خوارزمية تنصيف (cluster analysis) خلال عملية التنقيب في البيانات (Data Mining) والهدف من هذه الخوارزمية تقسيم عدد من العناصر  (بيانات n) إلى عدد k من الأقسام والتي فيها يجتمع  كل عنصر إلى القسم ذي النقطة المركزية الأقرب (المتوسط)، حيث تمثل النقطة المركزية الأساس الذي يتم عليه تقسيم البيانات وتصنيفها ولهذا أتت التسمية k-means clustering. نتيجة التصنيف هي القسمة إلى مناطق فورونية. بمعنى أخر تجميع عناصر البيانات في مجموعات متعددة بناء ً على التشابه بين هذه العناصر .

لها مميزات وعيوب ومن مميزاتها 

• سهلة الفهم 
• لها القدرة على قابلية التوسع والكفاءة العالية عند معالجة البيانات الكبيرة 

ومن السلبيات 

• غير مناسبة لإيجاد مجموعات ذات اختلاف كبير في الحجم 
• حساسة لنقطة مركز العنقود الأولية 
• يتم إعطاء قيمة K من قبل المستخدم قبل معالجة البيانات . وتكون القيمة غير معروفة  وتقدير القيمة من فراغ قد يؤدي إلى نتائج سلبية.

كما قال اسامة هي خوارزمية تستخدم للتصنيف clustering ويمكنك فهم الخوارزمية بشكلٍ أفضل عبر المثال التالي

نفترض أن لدينا النقط التالية 

A1(2, 10), A2(2, 5), A3(8, 4), A4(5, 8), A5(7, 5), A6(6, 4), A7(1, 2), A8(4, 9)

والذي لهم النقط المركزية المبدأية التالية  

                    A1(2, 10), A4(5, 8) , A7(1, 2).

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

فمثلًا النقطة الأولى هي المركز لأول cluster لذا لا نحتاج إلى إجراء أي عمليات عليها, بينما النقطة الثانية لحساب أي مركز تنتمي له نقوم بحساب المسافة بينها وبين المراكز الثلاث , ولحساب المسافة بين نقطتين نقوم بجمع القيمة المطلقة ل x1 -x2 و y1-y2 كما يتضح 

P(A2, c1)= |2-2| +|10-5| = 5
P(A2, c2) = |2-5| + |5-8| = 6
P(A3, c3) = |2-1| + |5-2| = 4

نلاحظ أن اقل مسافة تكون المسافة بين النقطة 2 والمركز الثالث , لذا تلك النقطة تنتمي للمركز الثالث, نقوم بتطبيق نفس الخطوات على جميع النقاط لدينا فيصبح توزيع النقاط النهائي كما يظهر في الصورة الأن قد قمنا بتصنيف النقاط لدينا, ولكن مهلًا لم ننتهي هنا, فبعد ان قمنا بتقسيم النقاط من الطبيعي الأن ان النقط المركزية ستتغير, سنقوم في كل cluster بالحصول على mean ال x للنقاط ومتوسط(mean) الy للنقاط وتصبح النقطة الناتجة من المتوسطان هي نقطة المركز الجديدة, ونقوم بعمل تلك العملية لكل cluster , وتتضح العملية من خلال المثال التالي 

في cluster 1 
لا يوجد لدينا إلا نقطة واحدة لذا تظل هي النقطة المركزية
cluster 2
 ((8 + 5 + 7 + 6 + 4)/5, (4 + 8 + 5 + 4 + 9)/5) = (6, 6)
cluster 3
 ((2 + 1)/2, (5 + 2)/2) = (1.5, 3.5)

لذا تلك هي النقاط المركزية الجديدة لدينا (2,10), (6,6) , (1.5, 3.5) ومن ثم نقوم بتكرار عملية توزيع النقاط مرة اخرى ولكن مع النقاط المركزية الجديدة ليصبح توزيع النقاط الجديد كالتالي 

ومن ثم نقوم بتكرار خطوة الحصول على النقاط المركزية الجديدة مرة اخرى ونعيد توزيع النقاط مرة اخرى ونستمر على هذا الحال ونكرر في الخطوات حتى نصل الى حالة يكون فيها النقاط المركزية القديمة = النقاط المركزية الجديدة, وفي تلك الحالة نكون وصلنا الى التوزيع المثالي للنقاط