الانتقال إلى المحتوى
العودة إلى نتائج البحث

التجميع الطيفي (Spectral Clustering)

قدّمه
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
السنة
2002
النوع
Graph-based clustering (spectral method)

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

التجميع الطيفي هو خوارزمية تعلم غير خاضع للإشراف قائمة على الرسوم البيانية، وقد صاغها نج (Ng) وجوردان (Jordan) ووايس (Weiss) في عام 2002. تقوم هذه الخوارزمية بتحويل نقاط البيانات إلى فضاء ذاتي منخفض الأبعاد مشتق من مصفوفة لابلاس للرسم البياني التشابهي قبل تطبيق خوارزمية k-means. يتيح هذا التضمين الطيفي استعادة تجمعات ذات أشكال عشوائية — مثل الحلقات، والهلاليات، والحلزونات المتداخلة — والتي تفشل طرق التجميع القائمة على المسافة الإقليدية باستمرار في فصلها.

الفكرة الحدسية وراء الطريقة

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

التاريخ

تعود الأسس النظرية للتجميع الطيفي إلى عمل فيدلر (Fiedler) عام 1973 حول اتصال الرسوم البيانية وقيمة أيغن للاتصال الجبري. أدخل شي (Shi) ومالك (Malik) (2000) هذا النهج في رؤية الحاسوب من خلال معيار القطع المعيارية لتجزئة الصور. قدم نج (Ng) وجوردان (Jordan) ووايس (Weiss) (2002) خوارزمية نظيفة وعامة الغرض في مؤتمر NIPS — وهي الأكثر استشهادًا بها حاليًا — جنبًا إلى جنب مع تحليل نظري للاضطراب يوضح متى ولماذا تعمل الطريقة. وحدت محاضرة فون لوكسبورغ (Von Luxburg) عام 2007 في الإحصاء والحوسبة (Statistics and Computing) الصيغ المتنافسة، ووضحت دور تطبيع لابلاس، وأصبحت المرجع القياسي للممارسين. يحتل التجميع الطيفي الآن مكانة مركزية في مناهج تعلم الآلة ويظل موضوع بحث نشط، مع عمل مستمر على التقريبات القابلة للتطوير، والنوى القوية، والامتدادات للرسوم البيانية والمنوعات.

متى تُستخدم

التجميع الطيفي مناسب تمامًا عندما تكون التجمعات في البيانات غير محدبة، أو غير قابلة للفصل خطيًا، أو متصلة بجسور رفيعة لا تستطيع طرق التقسيم الإقليدية اكتشافها — وتشمل الأمثلة الشائعة التجمعات الحلقية، والحلزونات المتداخلة، وقطاعات الصور. وهو مناسب عندما يمكن حساب التشابه الزوجي بين النقاط بشكل ذي معنى (إما من نواة على الميزات الخام أو من مصفوفة تقارب مقدمة مسبقًا)، وعندما يكون عدد التجمعات k معروفًا أو يمكن تقديره من استدلال فجوة القيم الذاتية (eigengap heuristic). لا تتطلب الطريقة أي افتراضات توزيعية على أشكال التجمعات. تشمل القيود العملية الذاكرة التربيعية في عدد النقاط (لمصفوفة التقارب الكاملة) والوقت التكعيبي لتحليل القيم الذاتية، مما يجعل الصياغة القياسية مكلفة بما يتجاوز حوالي 10,000 نقطة. الطرق التقريبية (Nystrom، الرسوم البيانية المتفرقة، تحليل القيم المفردة العشوائي SVD) توسع نطاقها إلى مجموعات بيانات أكبر.

الحدود والاعتبارات

  • يتطلب بناء مصفوفة التقارب الكاملة n-by-n ذاكرة من رتبة O(n^2) ووقتًا من رتبة O(n^3) لتحليل القيم الذاتية، مما يجعل الخوارزمية الساذجة غير عملية لمجموعات البيانات الكبيرة.
  • تتأثر النتائج باختيار عرض نطاق النواة sigma واستراتيجية بناء الرسم البياني؛ وقد تؤدي الخيارات السيئة إلى دمج أو تجزئة التجمعات.
  • يُدخل تهيئة k-means في التضمين الطيفي عشوائية؛ وقد تؤدي التشغيلات المختلفة إلى تقسيمات مختلفة.
  • لا تتوسع بشكل جيد إلى مساحات الميزات عالية الأبعاد جدًا دون اختيار دقيق للنواة.
  • توفر تسميات التجمع فقط؛ ولا تقدم نموذجًا توليديًا ولا امتدادًا طبيعيًا خارج العينة للنقاط الجديدة.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • يكشف عن تجمعات ذات أشكال عشوائية، بما في ذلك التكوينات غير المحدبة وغير القابلة للفصل خطيًا التي تفشل فيها خوارزميات k-means ونماذج الخليط الغاوسي.
  • يمكن أن تعمل على أي مصفوفة تشابه زوجي، وليس فقط المسافات الإقليدية، مما يجعلها قابلة للتطبيق على الرسوم البيانية، والسلاسل، وغيرها من البيانات المهيكلة.
  • يوفر استدلال فجوة القيم الذاتية (eigengap heuristic) إرشادًا مبدئيًا يعتمد على البيانات لاختيار عدد التجمعات k.
  • تستند إلى نظرية الرسم البياني الطيفي الغنية، مما يتيح التحليل الرسمي للتقارب وجودة التجمع.
  • بسيطة من الناحية المفاهيمية وسهلة التنفيذ باستخدام مكتبات الجبر الخطي القياسية.

التطبيقات

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

كيف يعمل

كيف يعمل

1

يتم بناء مصفوفة تشابه (تقارب) زوجي W من البيانات. الخيار الأكثر شيوعًا هو نواة غاوس (RBF)، والتي تعين وزنًا عاليًا للأزواج القريبة ووزنًا قريبًا من الصفر للأزواج البعيدة. يتحكم معامل عرض النطاق sigma في مدى سرعة اضمحلال التشابه مع المسافة؛ واختياره جيدًا أمر بالغ الأهمية. بدلاً من ذلك، يمكن استخدام رسم بياني لأقرب k-جيران لتمثيلات أكثر تباعدًا في مجموعات البيانات الكبيرة.

الصيغة
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

مصفوفة الدرجة D هي مصفوفة قطرية تكون مدخلتها i-th هي مجموع الصف i-th من W. من W و D تتشكل مصفوفة لابلاس المتماثلة المعيارية L_sym. تلتقط هذه المصفوفة بنية الاتصال الكاملة للرسم البياني التشابهي؛ ويكشف طيف قيمها الذاتية عن عدد التجمعات الطبيعية التي تحتويها البيانات ومدى فصلها بوضوح.

الصيغة
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

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

الصيغة
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

يتم قسمة كل صف من U على معياره الإقليدي لإسقاط النقاط المضمنة على الكرة الفائقة الوحدوية. هذا التطبيع، الذي قدمه نج (Ng) وجوردان (Jordan) ووايس (Weiss)، يزيل اختلافات الحجم الزائفة بين متجهات أيغن ويضمن أن خطوة k-means اللاحقة تركز على البنية الزاوية للتضمين بدلاً من التركيز على الحجم.

الصيغة
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

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

الأخطاء الشائعة

  • اختيار sigma دون التحقق المتقاطع المبدئي أو الضبط الذاتي؛ عرض نطاق صغير جدًا ينشئ رسمًا بيانيًا غير متصل، بينما عرض نطاق كبير جدًا يدمج تجمعات مميزة.
  • إهمال تطبيع صفوف مصفوفة التقارب قبل k-means (خطوة تطبيع الصفوف التي قدمها نج وآخرون ضرورية للاستقرار).
  • تجاهل فجوة القيم الذاتية (eigengap): استخدام k ثابت دون فحص طيف القيم الذاتية غالبًا ما يؤدي إلى تجزئة أقل أو أكثر من اللازم.
  • تطبيق الخوارزمية الكاملة على مجموعات بيانات تحتوي على عشرات الآلاف من النقاط دون التحول إلى نسخة تقريبية أو متفرقة.
  • الخلط بين مصفوفات لابلاس غير المعيارية (L = D - W) والمعيارية (L_sym, L_rw)، مما قد يغير تعيينات التجمعات بشكل كبير.

الأسئلة الشائعة

كيف أختار عدد التجمعات k؟

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

كيف يجب أن أضبط عرض نطاق نواة غاوس sigma؟

من الاستدلالات الشائعة هو وسيط المسافات الزوجية في مجموعة البيانات، أو مخطط ضبط ذاتي لأقرب الجيران (Zelnik-Manor & Perona, 2004) الذي يعين عرض نطاق محلي لكل نقطة. عمليًا، يجب التحقق من صحة sigma عن طريق فحص اتصال الرسم البياني التشابهي الناتج: يجب أن تحتوي كل نقطة على الأقل على عدد قليل من الجيران ذوي الأوزان العالية، ويجب ألا يتجزأ الرسم البياني إلى مكونات معزولة.

لماذا خطوة تطبيع الصفوف ضرورية؟

يمكن أن تختلف متجهات أيغن لمصفوفة لابلاس بشكل كبير في الحجم. بدون تطبيع كل صف من مصفوفة التضمين إلى طول الوحدة، قد تهيمن متجهات أيغن ذات المقادير الكبيرة على خطوة k-means وتتجاهل المكونات الإعلامية ولكن ذات المقادير الأصغر. يقوم تطبيع الصفوف الذي قدمه نج (Ng) وجوردان (Jordan) ووايس (Weiss) برسم جميع النقاط على الكرة الوحدوية بحيث تستجيب k-means للهندسة الزاوية للتضمين.

هل يمكن للتجميع الطيفي التعامل مع مجموعات البيانات الكبيرة جدًا؟

ليس في شكله الساذج، الذي يتطلب ذاكرة من رتبة O(n^2) ووقت تحليل القيم الذاتية من رتبة O(n^3). بالنسبة لـ n الكبيرة، تشمل العلاجات القياسية: بناء رسم بياني متفرق لأقرب k-جيران بدلاً من مصفوفة تقارب كاملة؛ استخدام تقريب نيستروم (Nystrom approximation) لتقدير متجهات أيغن من عينة فرعية؛ أو تطبيق تحليل القيم المفردة العشوائي (randomized SVD). تستعيد هذه الطرق التقريبية معظم الدقة بجزء بسيط من التكلفة.

طرق ذات صلة

المصادر

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    افتح مرجع المنشور
    تم النسخ.
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    افتح مرجع DOI
    تم النسخ.
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    افتح مرجع DOI
    تم النسخ.