التجميع الطيفي: ماذا تضيف روابط التشابه إلى تقسيم النقاط؟

الخلاصة السريعة

التجميع الطيفي ينظم روابط التشابه في تمثيل جديد. اختيار الروابط جزء من المسألة؛ وضوح رسمها لا يثبت أن التقسيم الناتج هو الصحيح.

• في الرسم التوضيحي غير الموجه، النقاط عقد والروابط تحمل تشابهًا غير سالب؛ نتتبع ما يقطعه التقسيم بدل افتراض مركز أصلي لكل مجموعة.
• قيم affinity الأكبر تعني تشابهًا أعلى؛ مصفوفة المسافات التي يكبر فيها البعد لا تحمل التفسير نفسه. ^[1]
• مع روابط أ–ب=3 وج–د=3 وب–ج=0.1، يقطع تقسيم {أ،ب}|{ج،د} وزنًا 0.1، ويقطع {أ،ج}|{ب،د} وزنًا 6.1.
• المقارنة بين هذين التقسيمين ليست تشغيلًا طيفيًا؛ تعتمد الطرق الطيفية على إرخاء مسائل قطع الرسم، لا ضمان حل أمثل شامل. ^[2]

النقاط تظهر كعقد مترابطة

نفترض أربع نقاط نسميها أ وب وج ود. لا نعطيها إحداثيات، بل نحدد رابطتين قويتين: أ–ب وج–د، وزن كل منهما ثلاثة. توجد رابطة أضعف بين ب وج بوزن 0.1.

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

يمكن للقارئ مراجعة شكل الاتصال دون البحث عن متوسط إحداثيات لم نقدمها. هذا لا يعني أن الطريقة تلغي دور البيانات الأصلية؛ بناء هذا الرسم منها سيكون خطوة تحتاج تعريفًا مستقلًا في التطبيق.

هل المدخل تشابه أم مسافة؟

توضح واجهة SpectralClustering أن المصفوفة المعطاة مسبقًا تمثل التشابه: القيم الكبيرة للأزواج الأكثر تشابهًا، والقيم غير سالبة. ^[1]

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

اكتب بجانب كل وزن كيف حسبته وما الذي تعنيه زيادته. وفي مثالنا تعني الثلاثة تشابهًا أقوى من 0.1 فقط؛ لا نحولها إلى احتمال أن النقطتين تنتميان إلى فئة حقيقية واحدة.

مقارنة تقسيمين عبر الروابط المقطوعة

التقسيم الأول يضع أ وب معًا، وج ود معًا. لا يقطع رابطتي الوزن ثلاثة؛ يقطع ب–ج فقط، فيكون الوزن المقطوع 0.1. التقسيم الثاني يضع أ وج معًا، وب ود معًا.

في التقسيم الثاني تعبر الروابط الثلاث بين الجزأين، فنحصل على 3+3+0.1=6.1. عدد النقاط في كل جزء اثنتان في الحالتين، لذلك ليس اختلاف العدد سبب اختلاف هذا المجموع.

هذا حساب لوزن القطع في رسم معين، وليس حساب درجة معيارية أو قيمة ذاتية. نقارن تقسيمين محددين، ولا ندعي أننا جربنا جميع الحلول أو حسبنا خرج خوارزمية طيفية.

من المقارنة اليدوية إلى الطريقة الطيفية

تشرح الورقة الطرق الطيفية باعتبارها حلولًا لإرخاءات مسائل تقسيم الرسم؛ تتبعها إعادة تحويل إلى مجموعات منفصلة. ^[2]

يفيد حسابنا في رؤية سبب تفضيل إبقاء بعض الروابط داخل المجموعة عند هذه المقارنة. لكنه لا يحل محل الإسقاط أو التجميع في البرنامج، ولم ننفذ أيًا منهما لنقاطنا الأربع.

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