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

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

المقالة الرئيسية: مخطط فورونوي

المشكلة تكمن في صعوبة الحساب، بمعنى صعوبة الوصول إلى نتيجة يتم على أساسها تضمين عنصر ما إلى قسم معين. وبرغم التشابه مع خوارزمية تعظيم التوقع (expectation-maximization algorithm EMA)، إلا أن ال k-means لا تُنتج أشكال مختلفة للبيانات المُجزئة كما تفعل ذلك الأولى (EMA).

الوصف

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

$\underset{\mathrm{r}}{\mathrm{a}}\sum _{i=1}^k{\sum }_{\mathbf{x}\in S_i}{\Vert \mathbf{x}-{{\mu }}_i\Vert }^2$

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

التاريخ

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

التطبيق الخوارزمي

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

تصنيف أولي

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

$S_i^{(t)}=\{x_p:\Vert x_p-m_i^{(t)}{\Vert }^2\le \Vert x_p-m_j^{(t)}{\Vert }^2\mathrm{\forall }j,1\le j\le k\},$

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

تحديث المراكز

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

$m_i^{(t+1)}=\frac{1}{\left|S_i^{(t)}\right|}{\sum }_{x_j\in S_i^{(t)}}{x}_j$

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

معرض صور

• 
• 
• 
•