خوارزمية تصنيفية

نأخذ العناصر المعطاة (x1, x2, …, xn) ، حيث كل عنصر يمثل متجها بُعده d. بعد تطبيق الخوارزمية على العناصر فيتم تقسيمها حسب التشابه بينها إلى عدد (k ≤ n) k من الأجزاء S: S = {S1, S2, …, Sk} بحيث يؤخذ القيمة الدنيا لمجموع التربيع بين كل عنصر وبين النقاط المركزية والتي عددها k (within-cluster sum of squares (WCSS)). العلاقة الرياضية تُعطى كالآتي:

حيث μ_i هي متوسط العناصر في الجزء S_i.

أول من استخدم مصطلح ال "k-means" كان جيمس ماكوين في عام 1967 ^[3] بيدَ أن الفكرة خلف هذا المصطلح ترجع إلى هوجو شتاين هاوس في عام 1957.^[4] التطبيق الكلاسيكي للخوارزمية تم اقتراحه من قبل ستوارت لويد في عام 1957 كتقنية تطبيقية للتضمين الرقمي، إلا أن النشر الأول لم يتم حتى عام ^[5] 1982.
في عام 1965 نشر E.W.Forgy نفس الطريقة، ولهذا يتم تسمية الخوارزمية أحيانا على إسمه.^[6] تطوير اضافي على الخوارزمية تم نشرها من قِبَل هارتيجان ووونج في 1975/1979.^[7]

التطبيق الخوازمي لل k-means يستعمل تقنية تكرار التصنيف. ابتداءً من نقاط عشوائية للمراكز m1(1),…,mk(1) يمر التطبيق في الخطوتين التاليتين:^[8]

في هذه الخطوة يتم تصنيف كل عنصر إلى إحدى النقاط المركزية وفق نتيجة المسافة الإقليدية (WCSS) والتي تُعبر عن المتوسط الأقرب للنقاط. هذا يعني قسمة العناصر إلى مناطق فورونية، ويعطى رياضياً بالعلاقة الآتية:

${\displaystyle S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},}$ 

حيث كل عنصر ${\displaystyle x_{p}}$  يتم دمجه إلى منطقة مركزية ${\displaystyle S^{(t)}}$  واحدة بالتحديد.

في هذه الخطوة يتم حساب النقاط المركزية من جديد بحيث تكون المراكز المحدثة للقطع (clusters) الجديدة.

${\displaystyle m_{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$ 

حساب النقاط المركزية الجيدية (الأنسب) يعني أيضا تقليل الحساب المتوسطي بين العناصر ومراكزها (WCSS) داخل كل منطقة.