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

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

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

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

تعتمد طريقة الكوع على نسبة التباين المُفسَّر كدالة لعدد المجموعات: ينبغي اختيار عدد من المجموعات بحيث لا تُحسِّن إضافة مجموعة أخرى نمذجة البيانات بشكل ملحوظ. بتعبير أدق، عند رسم نسبة التباين المُفسَّر بواسطة المجموعات مقابل عددها، تُضيف المجموعات الأولى معلومات قيّمة (تُفسِّر جزءًا كبيرًا من التباين)، ولكن عند نقطة معينة، ينخفض ​​التحسن الهامشي، مُشكِّلًا زاوية في الرسم البياني. يُحدَّد عدد المجموعات عند هذه النقطة، ومن هنا جاء "معيار الكوع". في معظم مجموعات البيانات، يكون هذا "الكوع" غامضًا، ^{[ 1 ]} مما يجعل هذه الطريقة ذاتية وغير موثوقة. نظرًا لأن مقياس المحاور اعتباطي، فإن مفهوم الزاوية غير مُحدَّد بدقة، وحتى مع البيانات العشوائية المنتظمة، يُنتج المنحنى "كوعًا"، مما يجعل الطريقة غير موثوقة إلى حد كبير. ^{[ ٢ ]} نسبة التباين المُفسَّر هي نسبة التباين بين المجموعات إلى التباين الكلي، وتُعرف أيضًا باختبار F. ويُظهر شكلٌ مُعدَّلٌ قليلاً من هذه الطريقة منحنى التباين داخل المجموعات. ^{[ ٣ ]}

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

في الإحصاء واستخراج البيانات ، يُعد التجميع باستخدام خوارزمية X-means أحد أشكال التجميع باستخدام خوارزمية k-means ، حيث يعمل على تحسين تصنيفات المجموعات من خلال محاولة التقسيم الفرعي بشكل متكرر، والاحتفاظ بأفضل التقسيمات الناتجة، حتى يتم الوصول إلى معيار مثل معيار معلومات أكايكي (AIC) أو معيار معلومات بايز (BIC). ^{[ 5 ]}

تُعدّ معايير المعلومات، مثل معيار معلومات أكايكي (AIC) ومعيار معلومات بايز (BIC) ومعيار معلومات الانحراف (DIC) ، مجموعة أخرى من الطرق لتحديد عدد المجموعات، وذلك في حال إمكانية إنشاء دالة احتمالية لنموذج التجميع. على سبيل المثال: يُعتبر نموذج k -means نموذجًا "شبه" لمزيج غاوسي ، ويمكن إنشاء دالة احتمالية لهذا النموذج، وبالتالي تحديد قيم معايير المعلومات. ^{[ 6 ]}

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

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

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

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

JumpMethod(X): ليكن Y = (p/2) قم بتهيئة قائمة D، بحجم n+1 ليكن D[0] = 0 من أجل k = 1 ... n: تجميع X مع k مجموعة (على سبيل المثال، باستخدام k-means) لنفترض أن d = تشويه التجميع الناتج D[k] = d^(-Y) عرّف J(i) = D[i] - D[i-1]، ثم أوجد قيمة k بين 1 و n التي تُعظّم J(k).

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

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

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

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

يُعدّ متوسط ​​معامل التشابه (Silhouette) للبيانات معيارًا مفيدًا آخر لتقييم العدد الأمثل للمجموعات. يُقاس معامل التشابه لبيانات معينة بمدى تطابقها مع البيانات داخل مجموعتها، ومدى تقاربها مع بيانات المجموعة المجاورة، أي المجموعة التي يكون متوسط ​​المسافة بينها وبين البيانات هو الأدنى. ^{[ 8 ]} يشير معامل التشابه القريب من 1 إلى أن البيانات تقع في المجموعة المناسبة، بينما يشير معامل التشابه القريب من -1 إلى أن البيانات تقع في المجموعة الخاطئة. تُفيد تقنيات التحسين، مثل الخوارزميات الجينية، في تحديد عدد المجموعات الذي يُحقق أكبر معامل تشابه. ^{[ 9 ]} من الممكن أيضًا إعادة تحجيم البيانات بحيث يُرجّح أن يصل معامل التشابه إلى أقصى قيمة له عند العدد الصحيح من المجموعات. ^{[ 10 ]}

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

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

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

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

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

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

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

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