عن التَّعنقُد الطيفي: تحليل وخوارزمية

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

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

نبدأ بتحويل نقاط البيانات الخام إلى مبيان. إذا كان لدينا $n$ نقطة $s_1, \ldots, s_n$، نبني مصفوفة تشابه $A$ بحيث يُعبّر العنصر $A_{ij}$ عن مدى قرب النقطتين $i$ و$j$ من بعضهما. تعتمد الورقة على نواة غاوسية (RBF) لحساب هذا التشابه:

الفكرة بسيطة: كلّ زوج من النقاط يحصل على درجة تشابه تتناقص بشكل أُسّي كلّما ابتعدت النقطتان عن بعضهما. المُعامل $\sigma$ يتحكّم في مدى اتّساع دائرة «الصداقة»: قيمة صغيرة لـ $\sigma$ تعني أنّ الجيران القريبين جداً فقط يُعتبرون أصدقاء، وقيمة كبيرة تعني أنّ حتى النقاط البعيدة تحتفظ ببعض الارتباط. أمّا عناصر القُطر فتُضبط على صفر ($A_{ii} = 0$) حتى لا تُعامَل أيّ نقطة كجارة لنفسها.

يمكنك التفكير في مصفوفة التشابه هذه كأنّها مصفوفة جوار لمبيان مُرجَّح: كل نقطة تمثّل عقدة، ووزن الحافة بين أيّ عقدتين يعكس قوة الارتباط بينهما.

مصفوفة التشابه الخام وحدها لا تكفي، لأنّ العقد في المناطق الكثيفة تملك ارتباطات قوية كثيرة، بينما العقد المعزولة لديها ارتباطات قليلة. لذلك نحتاج إلى تقييس يُعادل بين هذه الفروقات. نُعرِّف أولاً مصفوفة الدرجات $D$: وهي مصفوفة قُطرية يساوي فيها العنصر $D_{ii}$ مجموع الصف $i$ في المصفوفة $A$ — بمعنى آخر، تقيس مدى «شعبية» كل عقدة. ثم نُشكّل لابلاسيان المبيان المُقيَّس:

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

هنا جوهر الفكرة. لنبدأ بالحالة المثالية: لو كانت البيانات تحتوي $k$ عناقيد منفصلة تماماً — بلا أيّ حواف بينها — لأصبح لابلاسيان المبيان $L$ مصفوفة كُتلية قُطرية، ولكانت أعلى $k$ متجهات ذاتية له متجهات مؤشِّرة: كلّ واحد منها يأخذ قيمة ثابتة داخل عنقود معيّن وصفراً خارجه. حين نُكدّس هذه المتجهات كأعمدة في مصفوفة $X$، تصبح الصفوف التي تنتمي إلى العنقود نفسه متطابقة، وعندها تسترجعها k-means بلا عناء.

في الواقع طبعاً، العناقيد ليست منفصلة بالكامل — هناك دائماً حواف ضعيفة تعبر بين عنقود وآخر. هنا يأتي دور نظرية اضطراب المصفوفات التي تُخبرنا أنّ اضطرابات صغيرة في مصفوفة كتلية قُطرية تُنتج اضطرابات صغيرة في متجهاتها الذاتية. بمعنى أنّ صفوف $X$ لن تكون متطابقة تماماً داخل العنقود الواحد، لكنّها ستكون متقاربة جداً — قريبة بما يكفي لتتمكّن k-means من فصلها بسهولة.

تخيّل الأمر هكذا: المتجهات الذاتية تشبه شوكات رنّانة للمبيان — كل واحدة تتردّد مع تجمّع طبيعي مختلف. النقاط التي تهتزّ معاً بالنمط نفسه تنتمي إلى المجموعة نفسها.

بعد أن نستخرج أعلى $k$ متجهات ذاتية ونضعها في مصفوفة $X$، نُقيّس كل صف ليصبح طوله وحدوياً، فنحصل على مصفوفة $Y$ حيث $Y_{ij} = X_{ij} / (\sum_j X_{ij}^2)^{1/2}$. عملياً، هذا يعني إسقاط كل نقطة على سطح كرة وحدوية في فضاء ذي $k$ بُعداً.

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

المؤلفون يصفون هذه الخطوة بأنّها «تجميلية» — أي يمكن تخطّيها أحياناً — لكن عملياً تُحسّن النتائج بشكل واضح عند التعامل مع بيانات تتفاوت فيها كثافة العناقيد.

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

المُعامل الفائق $\sigma$ في النواة الغاوسية هو أكثر عنصر تأثيراً في الخوارزمية. يُحدّد هذا المُعامل النطاق الذي «ترى» فيه الخوارزمية البنية الكامنة في البيانات:

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

تُبيّن الورقة أنّه متى ضُبط $\sigma$ بشكل صحيح، تتحقّق الضمانات النظرية للخوارزمية. من الناحية العملية، يحتاج اختيار $\sigma$ إلى خبرة بطبيعة البيانات أو طرق تجريبية مثل استخدام وسيط المسافات الثنائية. وقد طوّر زلنيك-مانور وبيرونا لاحقاً (2004) أسلوب التقييس المحلي — بتخصيص قيمة $\sigma_i$ مختلفة لكل نقطة — ليتكيّف تلقائياً مع بيانات متعددة المقاييس.

الأساس النظري للورقة يقوم على مبرهنة ديفيس-كاهان من نظرية اضطراب المصفوفات. لنتتبّع خطّ الاستدلال:

نبدأ بتخيّل مصفوفة تشابه «مثالية» $\hat{A}$ كتلية قُطرية بالكامل — أي لا يوجد أيّ تشابه بين العناقيد. في هذه الحالة، تكون أعلى $k$ متجهات ذاتية هي متجهات مؤشِّرة مثالية. المصفوفة الحقيقية $A$ ليست سوى اضطراب لهذه المصفوفة المثالية: $A = \hat{A} + H$، حيث $H$ تحتوي التشابهات الضعيفة العابرة بين العناقيد.

ما تقوله مبرهنة ديفيس-كاهان هو أنّ المتجهات الذاتية لـ $A$ تبقى قريبة من تلك الخاصة بـ $\hat{A}$ ما دام حجم الاضطراب $\|H\|$ صغيراً مقارنةً بفجوة القيم الذاتية $\delta$ — وهي الفجوة بين القيمة الذاتية رقم $k$ ورقم $k+1$. بشكل أدقّ، الزاوية بين الفضاءين الفرعيين الحقيقي والمثالي محدودة بـ $O(\|H\| / \delta)$.

المعنى العملي واضح: حين تكون العناقيد منفصلة جيداً ($\|H\|$ صغير و$\delta$ كبير)، تتراصّ صفوف مصفوفة المتجهات الذاتية $X$ في تجمّعات مُحكَمة قرب المواضع المثالية، وتتمكّن k-means من استعادتها بسهولة.

التعنقد الطيفي يتفوّق في سياقات معيّنة، لكنّه ليس بديلاً شاملاً لـ k-means في كل حالة. إليك أبرز الحالات التي يتألّق فيها:

• عناقيد غير محدّبة — كالحلقات واللوالب والمتشعّبات. إذا كانت بياناتك ذات بنية هندسية معقّدة، يستطيع التعنقد الطيفي فصل ما تعجز عنه k-means.
• بيانات ذات بنية مبيانية أصلاً — كالشبكات الاجتماعية ومبيانات الاستشهاد والشبكات البيولوجية. هنا مصفوفة الجوار موجودة مسبقاً ولا نحتاج إلى بنائها.
• تجزئة الصور — البكسلات تُشكّل مبياناً شبكياً طبيعياً، والتعنقد الطيفي يُحدّد المناطق بناءً على الارتباط لا المسافة.

وهناك حالات يجب فيها الحذر:

• مجموعات البيانات الكبيرة — الخوارزمية تحتاج حساب وتحليل مصفوفة بحجم $n \times n$، وهذا يعني تعقيداً بمقدار $O(n^3)$. لقيم $n$ الكبيرة لا بدّ من اللجوء إلى طرق تقريبية كتقريب نيستروم.
• اختيار σ وk — على خلاف k-means التي تحتاج تحديد $k$ فقط، يتطلّب التعنقد الطيفي ضبط $\sigma$ أيضاً. فجوة القيم الذاتية تساعد في تحديد $k$، لكنّ $\sigma$ يحتاج عناية خاصّة.
• لا امتداد لنقاط جديدة — إضافة نقاط جديدة تتطلب إعادة تشغيل الخوارزمية بالكامل (قيد مشترك مع t-SNE).

لعلّ أهمّ ما تركته ورقة NJW ليس الخوارزمية بحدّ ذاتها، بل الرؤية العميقة بأنّ المتجهات الذاتية لـلابلاسيان المبيان تحمل في طيّاتها بنية التجميع الطبيعية للمبيان. هذه الفكرة امتدّت مباشرةً إلى الشبكات الالتفافية البيانية، حيث تؤدّي المتجهات الذاتية للابلاسيان دور «أساس فورييه» للمبيان، ممّا يُتيح إجراء التفاف على بنى غير منتظمة. في كل مرة تتعلّم فيها شبكة عصبية بيانية تصنيف العقد أو التنبّؤ بخصائص الجزيئات، فإنّها تبني على الأساس الذي أرساه التعنقد الطيفي.