تحديد عدد المجموعات في مجموعة البيانات

إن تحديد عدد المجموعات في مجموعة بيانات، وهي الكمية التي غالبًا ما يتم تسميتها بـ ن أو k كما في الخوارزمية التصنيفية، هي مشكلة متكررة في التحليل العنقودي، وهي قضية منفصلة عن عملية حل مشكلة التجميع الفعلية.

بالنسبة لفئة معينة من خوارزميات التجميع (على وجه الخصوص خوارزميات التجميع بالمتوسط وبالمنتصف وخوارزمية التوقع والتعظيم)، هناك معلمة يشار إليها عادةً باسم k والتي تحدد عدد المجموعات المراد اكتشافها. لا تتطلب الخوارزميات الأخرى مثل خوارزمية DBSCAN وOPTICS تحديد هذه المعلمة؛ حيث يتجنب التجميع الهرمي المشكلة تمامًا.

غالبًا ما يكون الاختيار الصحيح لـ ن غامضًا، حيث تعتمد التفسيرات على شكل ومقياس توزيع النقاط في مجموعة البيانات ودقة التجميع المطلوبة للمستخدم. بالإضافة إلى ذلك، فإن زيادة ن بدون حد سيقلل دائمًا من مقدار الخطأ في التجميع الناتج، إلى الحالة القصوى المتمثلة في الخطأ صفر إذا تم اعتبار كل نقطة بيانات عبارة عن مجموعة خاصة بها (أي عندما يكون ن مساويًا لعدد نقاط البيانات). وبالتالي، بديهيًا، فإن الاختيار الأمثل لـ ن سيحقق التوازن بين الحد الأقصى لضغط البيانات باستخدام مجموعة واحدة، والحد الأقصى للدقة عن طريق تعيين كل نقطة بيانات إلى مجموعتها الخاصة. إذا لم تكن القيمة المناسبة لـ ن واضحة من المعرفة المسبقة لخصائص مجموعة البيانات، فيجب اختيارها بطريقة ما. هناك عدة فئات من الأساليب لاتخاذ هذا القرار.

طريقة الكوع

تنظر طريقة الكوع إلى نسبة التباين الموضح كدالة لعدد المجموعات: يجب اختيار عدد من المجموعات بحيث لا يؤدي إضافة مجموعة أخرى إلى إعطاء نمذجة أفضل للبيانات. بتعبير أدق، إذا رسمنا النسبة المئوية للتباين الذي تفسره المجموعات مقابل عدد المجموعات، فإن المجموعات الأولى ستضيف الكثير من المعلومات (تشرح الكثير من التباين)، ولكن في مرحلة ما سوف ينخفض المكسب الهامشي، مما يعطي زاوية في الرسم البياني. يتم اختيار عدد المجموعات في هذه المرحلة، ومن هنا يأتي "معيار الكوع". في معظم مجموعات البيانات، يكون هذا "المرفق" غامضًا، مما يجعل هذه الطريقة ذاتية وغير موثوقة. نظرًا لأن مقياس المحاور تعسفي، فإن مفهوم الزاوية غير محدد جيدًا، وحتى في البيانات العشوائية المنتظمة، ينتج المنحنى "مرفقًا"، مما يجعل الطريقة غير موثوقة إلى حد ما. ^[1] نسبة التباين الموضحة هي نسبة التباين بين المجموعات إلى التباين الإجمالي، والمعروفة أيضًا باسم اختبار إف. يؤدي اختلاف طفيف في هذه الطريقة إلى رسم انحناء التباين داخل المجموعة.

يمكن إرجاع هذه الطريقة إلى تكهنات روبرت إل ثورندايك في عام 1953. ^[2] رغم أن فكرة طريقة الكوع تبدو بسيطة ومباشرة، إلا أن الطرق الأخرى (كما هو مفصل أدناه) تعطي نتائج أفضل.

التجميع باستخدام طريقة متوسط X

في الإحصاء وتعدين البيانات، يعتبر التجميع باستخدام متوسط X أحد أشكال التجميع باستخدام المتوسط الذي يعمل على تحسين تعيينات المجموعة من خلال محاولة التقسيم بشكل متكرر، والاحتفاظ بأفضل التقسيمات الناتجة، حتى يتم الوصول إلى معيار مثل معيار معلومات أكايكي (AIC) أو معيار المعلومات البايزي (BIC). ^[3]

نهج معيار المعلومات

هناك مجموعة أخرى من الأساليب لتحديد عدد المجموعات وهي معايير المعلومات، مثل معيار معلومات أكايكي (AIC)، أو معيار المعلومات البايزي (BIC)، أو معيار معلومات الانحراف (DIC) — إذا كان من الممكن إنشاء دالة احتمالية لنموذج التجميع. على سبيل المثال: نموذج المتوسط هو "تقريبًا" نموذج خليط غاوسي ويمكن للمرء أن يبني احتمالية لنموذج الخليط الغوسي وبالتالي تحديد قيم معيار المعلومات أيضًا. ^[4]

المنهج المعلوماتي النظري

تم تطبيق نظرية تشوه المعدل على اختيار K والتي تسمى طريقة "القفزة"، والتي تحدد عدد المجموعات التي تزيد من الكفاءة مع تقليل الخطأ وفقًا لمعايير نظرية المعلومات. ^[5] تتمثل استراتيجية الخوارزمية في إنشاء منحنى تشويه لبيانات الإدخال عن طريق تشغيل خوارزمية التجميع القياسية مثل الخوارزمية التصنيفية لجميع قيم k بين 1 وn، وحساب التشويه (الموصوف أدناه) للتجميع الناتج. ويتم بعد ذلك تحويل منحنى التشوه بقوة سلبية يتم اختيارها بناءً على أبعاد البيانات. ثم تشير القفزات في القيم الناتجة إلى خيارات معقولة لـ k، حيث تمثل القفزة الأكبر الخيار الأفضل.

يتم تعريف تشوه تجميع بعض بيانات الإدخال رسميًا على النحو التالي: دع مجموعة البيانات يتم نمذجتها كمتغير عشوائي X ذو p بعد، يتكون من توزيع خليط من مكونات G مع تغاير مشترك، $Γ$ . إذا كانت $c_{1}\ldots c_{K}$ مجموعة من مراكز المجموعة K، مع $c_{X}$ أقرب مركز لعينة معينة من X، فإن الحد الأدنى للتشوه المتوسط لكل بعد عند ملاءمة مراكز K للبيانات هو:

d_{K}={\frac {1}{p}}\min _{c_{1}\ldots c_{K}}{E[(X-c_{X})^{T}\Gamma ^{-1}(X-c_{X})]}

وهذا أيضًا هو متوسط مسافة ماهالانوبيس لكل بُعد بين X وأقرب مركز مجموعة $c_{X}$ . نظرًا لأن التقليل إلى أدنى حد على جميع مجموعات مراكز المجموعة الممكنة معقد للغاية، يتم حساب التشوه عمليًا عن طريق إنشاء مجموعة من مراكز المجموعة باستخدام خوارزمية تجميع قياسية وحساب التشوه باستخدام النتيجة.

اختيار قوة التحويل $Y=(p/2)$ يتم تحفيزه من خلال التحليل المقارب باستخدام نتائج من نظرية تشوه المعدل. دع البيانات X لها توزيع غاوسي واحد تعسفي ذو p بعج، ودع البيانات الثابتة $K=\lfloor \alpha ^{p}\rfloor$ ، لبعض $α$ أكبر من الصفر. ثم يكون تشوه مجموعة من K مجموعة في الحد عندما تتجه p إلى ما لا نهاية هو $\alpha ^{-2}$ . يمكن أن نرى أنه بشكل مقارب، تشويه التجميع إلى القوة $(-p/2)$ يتناسب مع $\alpha ^{p}$ ، والذي بحكم التعريف يساوي تقريبًا عدد المجموعات K. بعبارة أخرى، بالنسبة لتوزيع غاوسي واحد، فإن زيادة K بما يتجاوز العدد الحقيقي للمجموعات، والذي يجب أن يكون واحدًا، يسبب نموًا خطيًا في التشويه. يعد هذا السلوك مهمًا في الحالة العامة لمزيج من مكونات التوزيع المتعددة.

ليكن X مزيجًا من توزيعات غاوسية ذات p بعد ذات تباين مشترك. ثم بالنسبة لأي قيمة ثابتة K أقل من G، فإن تشوه التجميع عندما يتجه p إلى ما لا نهاية يكون لانهائيًا. بديهيًا، هذا يعني أن التجميع الذي يحتوي على عدد أقل من العدد الصحيح من التجمعات غير قادر على وصف البيانات عالية الأبعاد بشكل مقارب، مما يتسبب في زيادة التشوه دون حدود. إذا، كما هو موضح أعلاه، تم جعل K دالة متزايدة لـ p ، أي، $K=\lfloor \alpha ^{p}\rfloor$ ، يتم تحقيق نفس النتيجة المذكورة أعلاه، مع قيمة التشويه في الحد مع انتقال p إلى ما لا نهاية مساوية لـ $\alpha ^{-2}$ . وعليه، هناك نفس العلاقة التناسبية بين التشوه المحول وعدد المجموعات، K.

من خلال جمع النتائج أعلاه معًا، يمكننا أن نرى أنه بالنسبة للقيم المرتفعة بدرجة كافية لـ p، فإن التشوه المحول $d_{K}^{-p/2}$ تكون تقريبًا صفرًا بالنسبة لـ K < G، ثم تقفز فجأة وتبدأ في الزيادة خطيًا بالنسبة لـ K ≥ G. تستخدم خوارزمية القفز لاختيار K هذه السلوكيات لتحديد القيمة الأكثر احتمالية للعدد الحقيقي للمجموعات.

وعلى الرغم من أن الدعم الرياضي للطريقة يتم تقديمه من حيث النتائج المقاربة، فقد تم التحقق تجريبياً من أن الخوارزمية تعمل بشكل جيد في مجموعة متنوعة من مجموعات البيانات ذات الأبعاد المعقولة. بالإضافة إلى طريقة القفزة الموضعية الموضحة أعلاه، توجد خوارزمية ثانية لاختيار K باستخدام نفس قيم التشوه المحولة والمعروفة باسم طريقة الخط المكسور. تحدد طريقة الخط المكسور نقطة القفزة في رسم التشويه المحول عن طريق إجراء ملاءمة خطية بسيطة لخطأ المربعات الصغرى لقطعتي خط، والتي من الناحية النظرية ستقع على طول المحور السيني لـ K < G، وعلى طول الطور المتزايد خطيًا لمخطط التشويه المحول لـ K ≥ G. تعتبر طريقة الخط المكسور أكثر قوة من طريقة القفزة في أن قرارها عالمي وليس محليًا، لكنها تعتمد أيضًا على افتراض مكونات الخليط الغاوسي، في حين أن طريقة القفزة غير معيارية تمامًا وقد ثبت أنها قابلة للتطبيق لتوزيعات الخليط العامة.

طريقة الصور الظلية

ويشكل متوسط الصورة الظلية للبيانات معيارًا مفيدًا آخر لتقييم العدد الطبيعي للمجموعات. تُعد الصورة الظلية لمثيل البيانات مقياسًا لمدى قرب مطابقتها للبيانات داخل مجموعتها ومدى ضعف مطابقتها لبيانات المجموعة المجاورة، أي المجموعة التي تكون المسافة المتوسطة بينها وبين البيانات هي الأدنى. ^[6] تشير الصورة الظلية القريبة من 1 إلى أن البيانات موجودة في مجموعة مناسبة، في حين أن الصورة الظلية القريبة من 1- تشير إلى أن البيانات موجودة في المجموعة الخاطئة. تعتبر تقنيات التحسين مثل الخوارزميات الوراثية مفيدة في تحديد عدد المجموعات التي تؤدي إلى أكبر صورة ظلية. ^[7] من الممكن أيضًا إعادة قياس البيانات بطريقة تجعل من المرجح أن يتم تعظيم الصورة الظلية عند العدد الصحيح من المجموعات. ^[8]

التحقق المتقاطع

يمكنك أيضًا استخدام عملية التحقق المتقاطع لتحليل عدد المجموعات. في هذه العملية، يتم تقسيم البيانات إلى v جزء. يتم بعد ذلك تخصيص كل جزء من الأجزاء بدوره كمجموعة اختبار، ويتم حساب نموذج التجميع على مجموعات التدريب v − 1 الأخرى، ويتم حساب قيمة دالة الهدف (على سبيل المثال، مجموع المسافات التربيعية إلى مراكز الثقل لمتوسطات k) المحسوبة لمجموعة الاختبار. يتم حساب قيم v هذه ومتوسطها لكل عدد بديل من المجموعات، ويتم اختيار رقم المجموعة بحيث تؤدي الزيادة الإضافية في عدد المجموعات إلى انخفاض صغير فقط في دالة الهدف.

العثور على عدد المجموعات في قواعد البيانات النصية

عند تجميع قواعد بيانات النصوص باستخدام معامل الغلاف في مجموعة مستندات محددة بواسطة مصفوفة المستندات حسب المصطلح D (بحجم m×n، حيث m هو عدد المستندات وn هو عدد المصطلحات)، يمكن تقدير عدد المجموعات تقريبًا بالصيغة ${\tfrac {mn}{t}}$ حيث t هو عدد العناصر غير الصفرية في D. لاحظ أنه في D يجب أن يحتوي كل صف وكل عمود على عنصر غير صفري واحد على الأقل. ^[9]

تحليل مصفوفة النواة

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

وبالتالي، يمكن تحليل مصفوفة النواة من أجل العثور على العدد الأمثل للمجموعات. ^[10] وتستمر الطريقة من خلال تحلل القيمة الذاتية لمصفوفة النواة. وتقوم بعد ذلك بتحليل القيم الذاتية والمتجهات الذاتية للحصول على مقياس لمدى ضغط توزيع المدخلات. وأخيرًا، سترسم مخطط، حيث يشير مرفق هذا المخطط إلى العدد الأمثل للمجموعات في مجموعة البيانات. على عكس الطرق السابقة، لا تحتاج هذه التقنية إلى إجراء أي تجميع مسبق. وتقوم بالعثور مباشرة على عدد المجموعات من البيانات.

إحصائيات الفجوة

اقترح روبرت تيبشيراني وجونتر والثر وتريفور هاستي تقدير عدد المجموعات في مجموعة بيانات من خلال إحصائية الفجوة. ^[11] تقوم إحصاءات الفجوة، استنادًا إلى أسس نظرية، بقياس مدى المسافة بين مجموع المربعات المجمعة داخل المجموعة حول مراكز المجموعة ومجموع المربعات المتوقعة في ظل توزيع البيانات المرجعي الصفري. يتم تقدير القيمة المتوقعة من خلال محاكاة بيانات مرجعية فارغة لخصائص البيانات الأصلية، ولكنها تفتقر إلى أي مجموعات فيها. يتم بعد ذلك تقدير العدد الأمثل للمجموعات كقيمة k التي يكون فيها مجموع المربعات المرصودة أقل من المرجع الصفري.

على عكس العديد من الطرق السابقة، يمكن لإحصائيات الفجوة أن تخبرنا أنه لا توجد قيمة لـ k والتي يوجد لها تجميع جيد، ولكن تعتمد الموثوقية على مدى معقولية التوزيع الصفري المفترض (على سبيل المثال، التوزيع الموحد) على البيانات المقدمة. يميل هذا إلى العمل بشكل جيد في الإعدادات الاصطناعية، لكنه لا يستطيع التعامل مع مجموعات البيانات الصعبة، مثل السمات غير المعلوماتية، بشكل جيد لأنه يفترض أن جميع السمات مهمة بنفس القدر. ^[12]

يتم تنفيذ إحصائيات الفجوة كدالة clusGap في حزمة المجموعة ^[13] في R.

مراجع

^ Schubert, Erich (22 Jun 2023). "Stop using the elbow criterion for k-means and how to choose the number of clusters instead". ACM SIGKDD Explorations Newsletter (بالإنجليزية). 25 (1): 36–42. arXiv:2212.12189. DOI:10.1145/3606274.3606278. ISSN:1931-0145. Archived from the original on 2024-12-19.
^ Robert L. Thorndike (ديسمبر 1953). "Who Belongs in the Family?". Psychometrika. ج. 18 ع. 4: 267–276. DOI:10.1007/BF02289263. S2CID:120467216.
^ D. Pelleg؛ AW Moore. "X-means: Extending K-means with Efficient Estimation of the Number of Clusters" (PDF). Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000). مؤرشف من الأصل (PDF) في 2024-08-12. اطلع عليه بتاريخ 2016-08-16.
^ Cyril Goutte, Lars Kai Hansen, Matthew G. Liptrot & Egill Rostrup (2001). "Feature-Space Clustering for fMRI Meta-Analysis". Human Brain Mapping. ج. 13 ع. 3: 165–183. DOI:10.1002/hbm.1031. PMC:6871985. PMID:11376501.{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link) see especially Figure 14 and appendix.
^ Catherine A. Sugar؛ Gareth M. James (2003). "Finding the number of clusters in a data set: An information-theoretic approach". Journal of the American Statistical Association. ج. 98 ع. January: 750–763. DOI:10.1198/016214503000000666. S2CID:120113332.
^ Peter J. Rousseuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics. ج. 20: 53–65. DOI:10.1016/0377-0427(87)90125-7.
^ R. Lleti؛ M.C. Ortiz؛ L.A. Sarabia؛ M.S. Sánchez (2004). "Selecting Variables for k-Means Cluster Analysis by Using a Genetic Algorithm that Optimises the Silhouettes". Analytica Chimica Acta. ج. 515 ع. 1: 87–100. Bibcode:2004AcAC..515...87L. DOI:10.1016/j.aca.2003.12.020.
^ R.C. de Amorim & C. Hennig (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. ج. 324: 126–145. arXiv:1602.06989. DOI:10.1016/j.ins.2015.06.039. S2CID:315803.
^ Can، F.؛ Ozkarahan، E. A. (1990). "Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases". ACM Transactions on Database Systems. ج. 15 ع. 4: 483. DOI:10.1145/99935.99938. hdl:2374.MIA/246. S2CID:14309214. especially see Section 2.7.
^ Honarkhah, M؛ Caers, J (2010). "Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling". Mathematical Geosciences. ج. 42 ع. 5: 487–517. Bibcode:2010MatGe..42..487H. DOI:10.1007/s11004-010-9276-7. S2CID:73657847.
^ Robert Tibshirani؛ Guenther Walther؛ Trevor Hastie (2001). "Estimating the number of clusters in a data set via the gap statistic". Journal of the Royal Statistical Society, Series B. ج. 63 ع. 2: 411–423. DOI:10.1111/1467-9868.00293. S2CID:59738652.
^ Brodinová, Šárka; Filzmoser, Peter; Ortner, Thomas; Breiteneder, Christian; Rohm, Maia (19 Mar 2019). "Robust and sparse k-means clustering for high-dimensional data". Advances in Data Analysis and Classification (بالإنجليزية). 13 (4): 905–932. arXiv:1709.10012. DOI:10.1007/s11634-019-00356-9. ISSN:1862-5347.
^ "cluster R package". 28 مارس 2022.

روابط خارجية

مخطط العنقود – مخطط تشخيص العنقود – للتشخيص البصري لاختيار عدد ( k ) من العناقيد (كود R )
ثماني طرق لتحديد قيمة k المثلى لتحليل k -means – إجابة على stackoverflow تحتوي على كود R لعدة طرق لحساب القيمة المثلى لـ k لتحليل مجموعة k -means

[1] Schubert, Erich (22 Jun 2023). "Stop using the elbow criterion for k-means and how to choose the number of clusters instead". ACM SIGKDD Explorations Newsletter (بالإنجليزية). 25 (1): 36–42. arXiv:2212.12189. DOI:10.1145/3606274.3606278. ISSN:1931-0145. Archived from the original on 2024-12-19.

[2] Robert L. Thorndike (ديسمبر 1953). "Who Belongs in the Family?". Psychometrika. ج. 18 ع. 4: 267–276. DOI:10.1007/BF02289263. S2CID:120467216.

[3] D. Pelleg؛ AW Moore. "X-means: Extending K-means with Efficient Estimation of the Number of Clusters" (PDF). Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000). مؤرشف من الأصل (PDF) في 2024-08-12. اطلع عليه بتاريخ 2016-08-16.

[4] Cyril Goutte, Lars Kai Hansen, Matthew G. Liptrot & Egill Rostrup (2001). "Feature-Space Clustering for fMRI Meta-Analysis". Human Brain Mapping. ج. 13 ع. 3: 165–183. DOI:10.1002/hbm.1031. PMC:6871985. PMID:11376501.{{استشهاد بدورية محكمة}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link) see especially Figure 14 and appendix.

[5] Catherine A. Sugar؛ Gareth M. James (2003). "Finding the number of clusters in a data set: An information-theoretic approach". Journal of the American Statistical Association. ج. 98 ع. January: 750–763. DOI:10.1198/016214503000000666. S2CID:120113332.

[6] Peter J. Rousseuw (1987). "Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis". Computational and Applied Mathematics. ج. 20: 53–65. DOI:10.1016/0377-0427(87)90125-7.

[7] R. Lleti؛ M.C. Ortiz؛ L.A. Sarabia؛ M.S. Sánchez (2004). "Selecting Variables for k-Means Cluster Analysis by Using a Genetic Algorithm that Optimises the Silhouettes". Analytica Chimica Acta. ج. 515 ع. 1: 87–100. Bibcode:2004AcAC..515...87L. DOI:10.1016/j.aca.2003.12.020.

[8] R.C. de Amorim & C. Hennig (2015). "Recovering the number of clusters in data sets with noise features using feature rescaling factors". Information Sciences. ج. 324: 126–145. arXiv:1602.06989. DOI:10.1016/j.ins.2015.06.039. S2CID:315803.

[9] Can، F.؛ Ozkarahan، E. A. (1990). "Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases". ACM Transactions on Database Systems. ج. 15 ع. 4: 483. DOI:10.1145/99935.99938. hdl:2374.MIA/246. S2CID:14309214. especially see Section 2.7.

[10] Honarkhah, M؛ Caers, J (2010). "Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling". Mathematical Geosciences. ج. 42 ع. 5: 487–517. Bibcode:2010MatGe..42..487H. DOI:10.1007/s11004-010-9276-7. S2CID:73657847.

[11] Robert Tibshirani؛ Guenther Walther؛ Trevor Hastie (2001). "Estimating the number of clusters in a data set via the gap statistic". Journal of the Royal Statistical Society, Series B. ج. 63 ع. 2: 411–423. DOI:10.1111/1467-9868.00293. S2CID:59738652.

[12] Brodinová, Šárka; Filzmoser, Peter; Ortner, Thomas; Breiteneder, Christian; Rohm, Maia (19 Mar 2019). "Robust and sparse k-means clustering for high-dimensional data". Advances in Data Analysis and Classification (بالإنجليزية). 13 (4): 905–932. arXiv:1709.10012. DOI:10.1007/s11634-019-00356-9. ISSN:1862-5347.

[13] "cluster R package". 28 مارس 2022.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]