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

الخوارزمية التصنيفية أو التجميع بالمتوسط^[1] أو التجمع^[2] بالمتوسط (بالانجليزية: 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)). العلاقة الرياضية تُعطى كالآتي:

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}}$

حيث μ_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) داخل كل منطقة.

معرض صور

• 
• 
• 

المصادر

1. معجم البيانات والذكاء الاصطناعي (PDF) (بالعربية والإنجليزية)، الهيئة السعودية للبيانات والذكاء الاصطناعي، 2022، ص. 79، QID:Q111421033
2. موفق دعبول؛ مروان البواب؛ نزار الحافظ؛ نوار العوا (2017)، قائمة مصطلحات المعلوماتية (بالعربية والإنجليزية)، دمشق: مجمع اللغة العربية بدمشق، ص. 65، QID:Q112244705
3. MacQueen، J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations". Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. ج. 1. ص. 281–297. MR:0214227. Zbl:0214.46201. مؤرشف من الأصل في 2019-10-29. اطلع عليه بتاريخ 2009-04-07.
4. Steinhaus, H. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (بالفرنسية). 4 (12): 801–804. MR:0090073. Zbl:0079.16403.
5. Lloyd، S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd.، S. P. (1982). "Least squares quantization in PCM" (PDF). IEEE Transactions on Information Theory. ج. 28 ع. 2: 129–137. DOI:10.1109/TIT.1982.1056489. مؤرشف من الأصل (PDF) في 2009-06-17. اطلع عليه بتاريخ 2009-04-15.
6. E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. ج. 21: 768–769. JSTOR:2528559.
7. J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc.
8. MacKay، David (2003). "Chapter 20. An Example Inference Task: Clustering". Information Theory, Inference and Learning Algorithms. Cambridge University Press. ص. 284–292. ISBN:0-521-64298-1. MR:2012999. مؤرشف من الأصل (PDF) في 2017-05-08.