طريقة التجميع هي مهمة تجميع مجموعة من الكائنات بطريقة تجعلها في نفس المجموعة أكثر تشابهًا مع بعضها البعض من الكائنات الموجودة في الصناعات الأخرى. إنها المهمة الأساسية لاستخراج البيانات وتقنية التحليل الإحصائي العامة المستخدمة في العديد من المجالات ، بما في ذلك التعلم الآلي ، والتعرف على الأنماط ، والتعرف على الصور ، واسترجاع المعلومات ، وضغط البيانات ، ورسومات الكمبيوتر.
مشكلة التحسين
طريقة التجميع في حد ذاتها ليست خوارزمية واحدة محددة ، ولكنها مهمة عامة تحتاج إلى حل. يمكن تحقيق ذلك باستخدام خوارزميات مختلفة تختلف اختلافًا كبيرًا في فهم ما يشكل مجموعة وكيفية العثور عليها بكفاءة. يتضمن استخدام طريقة التجميع لتشكيل metasubjects استخدام مجموعة ذاتمسافات صغيرة بين الأعضاء ، أو مناطق كثيفة من الفضاء ، أو فترات زمنية ، أو توزيعات إحصائية معينة. لذلك ، يمكن صياغة المجموعات على أنها مشكلة تحسين متعددة الأهداف.
الطريقة المناسبة وإعدادات المعلمة (بما في ذلك عناصر مثل وظيفة المسافة التي يجب استخدامها ، أو عتبة الكثافة ، أو عدد المجموعات المتوقعة) تعتمد على مجموعة البيانات الفردية والاستخدام المقصود للنتائج. التحليل على هذا النحو ليس مهمة تلقائية ، ولكنه عملية تكرارية لاكتشاف المعرفة أو التحسين التفاعلي متعدد الأهداف. تتضمن طريقة التجميع هذه محاولات المحاولة والخطأ. غالبًا ما يكون من الضروري تعديل المعالجة المسبقة للبيانات ومعلمات النموذج حتى تحقق النتيجة الخصائص المطلوبة.
بالإضافة إلى مصطلح "التجميع" ، هناك عدد من الكلمات ذات المعاني المتشابهة ، بما في ذلك التصنيف التلقائي ، والتصنيف العددي ، وعلم الأحياء ، والتحليل التصنيفي. غالبًا ما تكمن الفروق الدقيقة في استخدام طريقة التجميع لتشكيل علاقات الموضوع الأساسي. أثناء استخراج البيانات ، تكون المجموعات الناتجة ذات أهمية ، في التصنيف التلقائي ، تكون القوة التمييزية هي التي تؤدي هذه الوظائف بالفعل.
استند تحليل الكتلة إلى العديد من الأعمال التي قام بها Kroeber في عام 1932. تم إدخاله إلى علم النفس من قبل زوبين في عام 1938 وروبرت تريون في عام 1939. وقد استخدم كاتيل هذه الأعمال منذ عام 1943 للإشارة إلى تصنيف طرق التجميع من الناحية النظرية.
مصطلح
لا يمكن تعريف مفهوم "الكتلة" بدقة. هذا هو أحد أسباب وجود العديد من طرق التجميع. هناك قاسم مشترك: مجموعة من كائنات البيانات. ومع ذلك ، يستخدم باحثون مختلفون نماذج مختلفة. وكل استخدام من طرق التجميع هذه يتضمن بيانات مختلفة. يختلف المفهوم الذي وجدته الخوارزميات المختلفة اختلافًا كبيرًا في خصائصها.
استخدام طريقة التجميع هو المفتاح لفهم الاختلافات بين التعليمات. تشمل أنماط الكتلة النموذجية:
- سنترويد ق. هذا ، على سبيل المثال ، عندما يمثل k-mean clustering كل كتلة ذات متجه متوسط واحد.
- نموذج الاتصال s. هذا ، على سبيل المثال ، هو التجميع الهرمي ، الذي يبني النماذج على أساس الاتصال عن بعد.
- نموذج التوزيع ق. في هذه الحالة ، يتم نمذجة المجموعات باستخدام طريقة التجميع لتشكيل توزيعات إحصائية metasubject. مثل الفصل العادي متعدد المتغيرات ، والذي ينطبق على خوارزمية تعظيم التوقعات.
- نموذج الكثافة ق. هذه ، على سبيل المثال ، DBSCAN (خوارزمية التجميع المكاني بالضوضاء) و OPTICS (نقاط الطلب لاكتشاف الهيكل) ، والتي تحدد المجموعات على أنها مناطق كثيفة متصلة في مساحة البيانات.
- نموذج الفضاء الفرعي ج. في biclustering (المعروف أيضًا باسم التجميع المشترك أو وضعين) ، يتم نمذجة المجموعات باستخدام كلا العنصرين والسمات المناسبة.
- موديل s. بعض الخوارزميات لا تفعل ذلكصقل العلاقة لطريقة التجميع الخاصة بهم لإنشاء نتائج موضوع التعريف وتوفير تجميع المعلومات ببساطة.
- نموذج يعتمد على الرسم البياني s. الزمرة ، أي مجموعة فرعية من العقد ، بحيث يمكن اعتبار كل اتصالين في جزء الحافة نموذجًا أوليًا لشكل الكتلة. يُعرف ضعف الطلب الكلي باسم شبه الزمر. يتم تقديم نفس الاسم بالضبط في خوارزمية تجميع HCS.
- النماذج العصبية ق. أشهر شبكة غير خاضعة للإشراف هي الخريطة ذاتية التنظيم. وهذه النماذج هي التي يمكن وصفها عادةً بأنها مشابهة لواحدة أو أكثر من طرق التجميع المذكورة أعلاه لتشكيل نتائج موضوع التعريف. يتضمن أنظمة الفضاء الجزئي عندما تنفذ الشبكات العصبية الشكل الضروري لتحليل المكون الرئيسي أو المستقل.
هذا المصطلح هو ، في الواقع ، مجموعة من هذه المجموعات ، والتي تحتوي عادةً على جميع الكائنات في مجموعة طرق تجميع البيانات. بالإضافة إلى ذلك ، يمكن أن يشير إلى علاقة المجموعات ببعضها البعض ، مثل التسلسل الهرمي للأنظمة المضمنة في بعضها البعض. يمكن تقسيم التجميع إلى الجوانب التالية:
- طريقة تجميع النقطه الوسطى الصلبة. هنا كل كائن ينتمي إلى مجموعة أو خارجها.
- نظام ناعم أو غامض. في هذه المرحلة ، ينتمي كل كائن بالفعل إلى حد معين إلى أي كتلة. وتسمى أيضًا طريقة c-mean fuzzy clustering.
وهناك اختلافات أكثر دقة ممكنة أيضًا. على سبيل المثال:
- التقسيم الصارم العنقودية. هناكل كائن ينتمي إلى مجموعة واحدة بالضبط.
- تقسيم صارم مع القيم المتطرفة. في هذه الحالة ، قد لا تنتمي الكائنات أيضًا إلى أي مجموعة وتعتبر غير ضرورية.
- مجموعات متداخلة (بديل أيضًا ، مع طرق عرض متعددة). هنا ، يمكن أن تنتمي الكائنات إلى أكثر من فرع. عادة ما تنطوي على عناقيد صلبة.
- طرق التجميع الهرمي. تنتمي الكائنات التي تنتمي إلى مجموعة فرعية أيضًا إلى النظام الفرعي الأصلي.
- تشكيل الفضاء الجزئي. على الرغم من تشابه المجموعات المتداخلة ، داخل نظام محدد بشكل فريد ، يجب ألا تتداخل المجموعات المتبادلة.
تعليمات
كما هو مذكور أعلاه ، يمكن تصنيف خوارزميات التجميع بناءً على نموذج الكتلة الخاص بهم. ستدرج المراجعة التالية فقط أبرز الأمثلة على هذه التعليمات. نظرًا لأنه قد يكون هناك أكثر من 100 خوارزمية منشورة ، فلا تقدم جميعها نماذج لمجموعاتها وبالتالي لا يمكن تصنيفها بسهولة.
لا توجد خوارزمية تجميع صحيحة بشكل موضوعي. ولكن ، كما هو مذكور أعلاه ، تكون التعليمات دائمًا في مجال رؤية المراقب. غالبًا ما يتعين اختيار خوارزمية التجميع الأنسب لمشكلة معينة بشكل تجريبي ، ما لم يكن هناك سبب رياضي لتفضيل نموذج على آخر. وتجدر الإشارة إلى أن الخوارزمية المصممة لنوع واحد لا تعمل عادة معهامجموعة بيانات تحتوي على موضوع مختلف تمامًا. على سبيل المثال ، لا يمكن للوسائل k العثور على مجموعات غير محدبة.
مجموعات قائمة على الاتصال
هذا الاتحاد معروف أيضًا باسمه ، النموذج الهرمي. يعتمد على الفكرة النموذجية القائلة بأن الكائنات أكثر ارتباطًا بالأجزاء المجاورة أكثر من تلك التي تكون بعيدة جدًا. تربط هذه الخوارزميات الكائنات ، وتشكل مجموعات مختلفة ، اعتمادًا على بعدهم. يمكن وصف المجموعة بشكل أساسي من خلال أقصى مسافة مطلوبة لربط الأجزاء المختلفة من الكتلة. في جميع المسافات الممكنة ، سيتم تشكيل مجموعات أخرى ، والتي يمكن تمثيلها باستخدام مخطط dendrogram. وهذا يفسر من أين يأتي الاسم الشائع "المجموعات الهرمية". أي أن هذه الخوارزميات لا توفر قسمًا واحدًا من مجموعة البيانات ، ولكنها توفر بدلاً من ذلك ترتيبًا واسعًا للسلطة. إنه بفضله أن هناك استنزافًا مع بعضنا البعض على مسافات معينة. في مخطط الأسنان ، يشير المحور الصادي إلى المسافة التي تتجمع عندها المجموعات. والأشياء مرتبة على طول الخط X بحيث لا تختلط المجموعات.
التجميع القائم على الاتصال هو مجموعة كاملة من الطرق التي تختلف في طريقة حساب المسافات. بالإضافة إلى الاختيار المعتاد لوظائف المسافة ، يحتاج المستخدم أيضًا إلى تحديد معيار الاتصال. نظرًا لأن الكتلة تتكون من عدة كائنات ، فهناك العديد من الخيارات لحسابها. يُعرف الخيار الشائع باسم التجميع أحادي الذراع ، وهذه هي الطريقةالارتباط الكامل ، الذي يحتوي على UPGMA أو WPGMA (مجموعة أزواج غير مرجحة أو مرجحة ذات متوسط حسابي ، تُعرف أيضًا باسم تجميع الارتباط المتوسط). بالإضافة إلى ذلك ، يمكن أن يكون النظام الهرمي تكتليًا (يبدأ بالعناصر الفردية ويجمعها في مجموعات) أو ينقسم (يبدأ بمجموعة بيانات كاملة ويقسمها إلى أقسام).
المجموعات الموزعة
ترتبط هذه النماذج ارتباطًا وثيقًا بالإحصاءات القائمة على الانقسامات. يمكن تعريف المجموعات بسهولة على أنها كائنات تنتمي على الأرجح إلى نفس التوزيع. من الميزات المفيدة لهذا الأسلوب أنه مشابه جدًا لطريقة إنشاء مجموعات البيانات الاصطناعية. بأخذ عينات من الكائنات العشوائية من التوزيع.
في حين أن الأساس النظري لهذه الأساليب ممتاز ، إلا أنها تعاني من مشكلة رئيسية واحدة ، تُعرف باسم overfitting ، ما لم يتم فرض قيود على تعقيد النموذج. عادةً ما يفسر الارتباط الأكبر البيانات بشكل أفضل ، مما يجعل من الصعب اختيار الطريقة الصحيحة.
نموذج خليط غاوسي
تستخدم هذه الطريقة جميع أنواع خوارزميات تعظيم التوقع. هنا ، عادةً ما يتم تصميم مجموعة البيانات باستخدام عدد ثابت (لتجنب تجاوز) توزيعات Gaussian التي تمت تهيئتها بشكل عشوائي والتي يتم تحسين معلماتها بشكل متكرر لتلائم مجموعة البيانات بشكل أفضل. سوف يتقارب هذا النظام إلى المستوى الأمثل المحلي. هذا هو السبب في أن عدة أشواط يمكن أن تعطينتائج مختلفة. للحصول على التجميع الأكثر إحكامًا ، غالبًا ما يتم تعيين الميزات إلى التوزيع الغاوسي الذي من المرجح أن تنتمي إليه. وبالنسبة للمجموعات الأكثر ليونة ، هذا ليس ضروريًا.
التجميع القائم على التوزيع ينشئ نماذج معقدة يمكنها في النهاية التقاط الارتباط والتبعية بين السمات. ومع ذلك ، تفرض هذه الخوارزميات عبئًا إضافيًا على المستخدم. بالنسبة للعديد من مجموعات البيانات في العالم الحقيقي ، قد لا يكون هناك نموذج رياضي محدد بدقة (على سبيل المثال ، بافتراض أن التوزيع الغاوسي هو افتراض قوي إلى حد ما).
التجميع القائم على الكثافة
في هذا المثال ، تُعرَّف المجموعات أساسًا على أنها مناطق ذات نفاذية أعلى من بقية مجموعة البيانات. الأشياء في هذه الأجزاء النادرة ، والتي تعتبر ضرورية لفصل جميع المكونات ، تعتبر عادة ضوضاء ونقاط حافة.
أكثر طرق التجميع المعتمدة على الكثافة شيوعًا هي DBSCAN (خوارزمية تجميع الضوضاء المكانية). على عكس العديد من الطرق الجديدة ، فإنه يحتوي على مكون كتلة محدد جيدًا يسمى "قابلية الوصول للكثافة". على غرار التجميع المستند إلى الارتباط ، فإنه يعتمد على نقاط الاتصال ضمن حدود مسافة معينة. ومع ذلك ، فإن هذه الطريقة تجمع فقط العناصر التي تفي بمعيار الكثافة. في الإصدار الأصلي ، المُعرَّف على أنه الحد الأدنى لعدد الكائنات الأخرى في نصف القطر هذا ، تتكون الكتلة من الكلالعناصر المتعلقة بالكثافة (والتي يمكن أن تشكل مجموعة حرة الشكل ، على عكس العديد من الطرق الأخرى) ، وجميع الكائنات الموجودة ضمن النطاق المسموح به.
خاصية أخرى مثيرة للاهتمام لـ DBSCAN وهي أن تعقيدها منخفض جدًا - فهي تتطلب عددًا خطيًا من استعلامات النطاق مقابل قاعدة البيانات. ومن غير المعتاد أيضًا أنه سيجد نفس النتائج بشكل أساسي (هذا أمر حتمي للنقاط الأساسية والضوضاء ، ولكن ليس للعناصر الحدودية) في كل شوط. لذلك لا داعي لتشغيله عدة مرات
العيب الرئيسي لـ DBSCAN و OPTICS هو أنهم يتوقعون بعض الانخفاض في الكثافة لاكتشاف حدود الكتلة. على سبيل المثال ، في مجموعات البيانات ذات التوزيعات الغوسية المتداخلة - حالة استخدام شائعة للأجسام الاصطناعية - غالبًا ما تظهر حدود المجموعة التي تم إنشاؤها بواسطة هذه الخوارزميات عشوائية. يحدث هذا لأن كثافة المجموعات تتناقص باستمرار. وفي مجموعة بيانات خليط Gaussian ، تتفوق هذه الخوارزميات دائمًا تقريبًا على طرق مثل مجموعات EM ، والتي تكون قادرة على نمذجة هذه الأنواع من الأنظمة بدقة.
متوسط الإزاحة هو أسلوب تجميع ينتقل فيه كل كائن إلى المنطقة الأكثر كثافة في الحي بناءً على تقدير النواة بأكملها. في النهاية ، تتقارب الكائنات مع الحد الأقصى لمانع الاختراق المحلي. على غرار تجميع الوسائل k ، يمكن أن تعمل "عوامل جذب الكثافة" هذه كممثلين لمجموعة بيانات. لكن يعني التحوليمكن الكشف عن المجموعات ذات الشكل التعسفي المشابهة لـ DBSCAN. نظرًا للإجراء التكراري الباهظ وتقدير الكثافة ، يكون متوسط الإزاحة عادةً أبطأ من DBSCAN أو k-Means. بالإضافة إلى ذلك ، فإن تطبيق خوارزمية التحول النموذجية على البيانات عالية الأبعاد أمر صعب بسبب السلوك غير المنتظم لتقدير كثافة النواة ، مما يؤدي إلى التجزئة المفرطة لذيول الكتلة.
التقييم
التحقق من نتائج التجميع صعب مثل التجميع نفسه. تشمل المناهج الشائعة التقييم "الداخلي" (حيث يتم تقليل النظام إلى مقياس واحد للجودة) وبالطبع التقييم "الخارجي" (حيث تتم مقارنة التجميع بتصنيف "الحقيقة الأساسية" الحالي). ويتم العثور على النتيجة اليدوية للخبير البشري والنتيجة غير المباشرة من خلال فحص فائدة التجميع في التطبيق المقصود.
تعاني مقاييس العلم الداخلي من المشكلة المتمثلة في أنها تمثل ميزات يمكن اعتبارها في حد ذاتها أهدافًا مجمعة. على سبيل المثال ، من الممكن تجميع البيانات المقدمة بواسطة معامل Silhouette ، باستثناء أنه لا توجد خوارزمية فعالة معروفة للقيام بذلك. باستخدام مثل هذا المقياس الداخلي للتقييم ، من الأفضل مقارنة تشابه مشاكل التحسين.
للعلامة الخارجية مشاكل مماثلة. إذا كانت هناك تسميات مثل "الحقيقة الأساسية" ، فلا داعي للتكتل. وفي التطبيقات العملية ، عادة لا توجد مثل هذه المفاهيم. من ناحية أخرى ، تعكس التسميات قسمًا واحدًا ممكنًا من مجموعة البيانات ، وهذا لا يعنيأنه لا يوجد مجموعات أخرى (ربما أفضل).
لذلك لا يمكن لأي من هذه الأساليب أن تحكم في النهاية على الجودة الفعلية. لكن هذا يتطلب تقييمًا بشريًا ، وهو أمر شخصي للغاية. ومع ذلك ، يمكن أن تكون هذه الإحصائيات مفيدة في تحديد التجمعات السيئة. لكن لا ينبغي لأحد أن يستبعد التقييم الذاتي للشخص.
علامة داخلية
عندما يتم تقييم نتيجة التجميع بناءً على البيانات التي تم تجميعها في حد ذاتها ، يُشار إلى هذا المصطلح. تحدد هذه الطرق بشكل عام أفضل نتيجة لخوارزمية تنشئ مجموعات ذات تشابه كبير داخل المجموعات منخفضة بين المجموعات. من عيوب استخدام المعايير الداخلية في تقييم الكتلة أن الدرجات العالية لا تؤدي بالضرورة إلى تطبيقات فعالة لاسترجاع المعلومات. أيضًا ، هذه النتيجة منحازة نحو الخوارزميات التي تستخدم نفس النموذج. على سبيل المثال ، k-mean clustering يحسن بشكل طبيعي مسافات المعالم ، ومن المحتمل أن يبالغ معيار داخلي قائم على أساسه في تقدير التجميع الناتج.
لذلك ، فإن إجراءات التقييم هذه هي الأنسب للحصول على فكرة عن المواقف التي تؤدي فيها خوارزمية ما أداءً أفضل من الأخرى. لكن هذا لا يعني أن كل معلومة تعطي نتائج موثوقة أكثر من غيرها. تعتمد فترة الصلاحية التي يقاسها هذا المؤشر على التأكيد على وجود الهيكل في مجموعة البيانات. لا توجد فرصة لخوارزمية تم تطويرها لبعض الأنواع إذا كانت المجموعة تحتوي على جذريتكوين مختلف أو إذا كان التقييم يقيس معايير مختلفة. على سبيل المثال ، يمكن لتجميع الوسائل k العثور على مجموعات محدبة فقط ، والعديد من مؤشرات الدرجات تتخذ نفس التنسيق. في مجموعة البيانات ذات النماذج غير المحدبة ، من غير المناسب استخدام الوسائل k ومعايير التقييم النموذجية.
تقييم خارجي
مع هذا النوع من الكرات ، يتم تقييم نتائج التجميع بناءً على البيانات التي لم يتم استخدامها للتجميع. أي ، مثل تسميات الفئات المعروفة والاختبارات الخارجية. تتكون هذه الأسئلة من مجموعة من العناصر المصنفة مسبقًا وغالبًا ما يتم إنشاؤها بواسطة خبراء (بشر). على هذا النحو ، يمكن اعتبار المجموعات المرجعية المعيار الذهبي للتقييم. تقيس هذه الأنواع من طرق تسجيل الدرجات مدى قرب التجميع من فئات مرجعية معينة. ومع ذلك ، فقد نوقش مؤخرًا ما إذا كان هذا مناسبًا للبيانات الحقيقية أم فقط للمجموعات التركيبية ذات الحقيقة الأساسية الفعلية. نظرًا لأن الفئات قد تحتوي على بنية داخلية ، وقد لا تسمح السمات الحالية بفصل المجموعات. أيضًا ، من وجهة نظر اكتشاف المعرفة ، قد لا ينتج عن إعادة إنتاج الحقائق المعروفة بالضرورة النتيجة المتوقعة. في سيناريو التجميع المقيّد الخاص حيث يتم استخدام المعلومات الوصفية (مثل تسميات الفئة) بالفعل في عملية التجميع ، فليس من التافه الاحتفاظ بجميع المعلومات لأغراض التقييم.
الآن من الواضح ما الذي لا ينطبق على طرق التجميع ، وما هي النماذج المستخدمة لهذه الأغراض.
