التجميع الطيفي

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

${\displaystyle L:=DA}$،

أين${\displaystyle D}$هي المصفوفة القطرية

${\displaystyle D_{ii}=\sum _{j}A_{ij},}$

و A هي مصفوفة التجاور .

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

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

تُعد خوارزمية القطع المعيارية أو خوارزمية شي-مالك، التي قدمها جيانبو شي وجيتندرا مالك ^{[ 2 ]} ، إحدى تقنيات التجميع الطيفي المعياري الشائعة، وتُستخدم عادةً في تجزئة الصور . وهي تقسم النقاط إلى مجموعتين.${\displaystyle (B_{1},B_{2})}$بناءً على المتجه الذاتي${\displaystyle v}$يتوافق مع ثاني أصغر قيمة ذاتية لمؤثر لابلاس المتناظر المعياري المعرف على النحو التالي

${\displaystyle L^{\text{norm}}:=ID^{-1/2}AD^{-1/2}.}$

المتجه${\displaystyle v}$وهو أيضًا المتجه الذاتي المقابل لثاني أكبر قيمة ذاتية لمصفوفة التجاور المتناظرة المعيارية ${\displaystyle D^{-1/2}AD^{-1/2}.}$

يُعرَّف لابلاس المُعَيَّر ذو المسار العشوائي (أو الأيسر) على النحو التالي :

${\displaystyle L^{\text{rw}}:=D^{-1}L=ID^{-1}A}$

ويمكن استخدامها أيضًا للتجميع الطيفي. وتأخذ خوارزمية مكافئة رياضيًا ^{[ 3 ]} المتجه الذاتي${\displaystyle u}$المقابل لأكبر قيمة ذاتية لمصفوفة التجاور المعيارية للمشي العشوائي${\displaystyle P=D^{-1}A}$.

المتجه الذاتي${\displaystyle v}$من لابلاس المعياري المتناظر والمتجه الذاتي${\displaystyle u}$ترتبط قيم لابلاس المعيارية اليسرى بالتطابق${\displaystyle D^{-1/2}v=u.}$

معرفة${\displaystyle n}$-بواسطة-${\displaystyle k}$مصفوفة${\displaystyle V}$من المتجهات الذاتية المختارة، عملية رسم الخرائط - التي تسمى التضمين الطيفي - للأصل${\displaystyle n}$يتم إجراء عمليات جمع البيانات وفقًا لـ${\displaystyle k}$فضاء متجهي ذو أبعاد n باستخدام صفوف${\displaystyle V}$. الآن، يقتصر التحليل على تجميع المتجهات مع${\displaystyle k}$المكونات، والتي يمكن القيام بها بطرق مختلفة.

في أبسط الحالات${\displaystyle k=1}$، المتجه الذاتي المفرد المختار${\displaystyle v}$، والذي يُسمى متجه فيدلر ، يُقابل ثاني أصغر قيمة ذاتية. باستخدام مكونات${\displaystyle v,}$يمكن وضع جميع النقاط التي يكون مكونها في${\displaystyle v}$موجب في المجموعة${\displaystyle B_{+}}$والباقي في${\displaystyle B_{-}}$وبالتالي، يتم تقسيم الرسم البياني إلى قسمين وتسمية نقاط البيانات بعلامتين. يتبع هذا النهج القائم على الإشارة التفسير البديهي للتجميع الطيفي عبر نموذج الكتلة والنابض - في نمط الاهتزاز منخفض التردد الذي يمثله متجه فيدلر${\displaystyle v}$تمثل هذه الخوارزمية مجموعة بيانات واحدة، حيث تتحرك نقاط البيانات التي تم تحديدها بكتل مترابطة بقوة معًا في اتجاه واحد، بينما تتحرك نقاط البيانات في المجموعة المكملة، والتي تم تحديدها بكتل متبقية، معًا في الاتجاه المعاكس. ويمكن استخدام هذه الخوارزمية للتجميع الهرمي من خلال تقسيم المجموعات الفرعية بشكل متكرر بنفس الطريقة.

في الحالة العامة${\displaystyle k>1}$، يمكن استخدام أي تقنية لتجميع المتجهات، على سبيل المثال، DBSCAN .

يمكن إنشاء مصفوفة لابلاس للرسم البياني، وهو أمر شائع، من مصفوفة التجاور. يمكن إجراء هذا الإنشاء دون استخدام المصفوفات، أي دون تشكيل مصفوفة مصفوفة لابلاس للرسم البياني بشكل صريح ودون استخدام خوارزمية AO. كما يمكن إجراؤه بدلاً من مصفوفة التجاور دون زيادة في استهلاك الذاكرة. في كلتا الحالتين، تتحدد تكلفة إنشاء مصفوفة لابلاس للرسم البياني بشكل أساسي بتكلفة إنشاء مصفوفة التجاور.${\displaystyle n}$-بواسطة-${\displaystyle n}$مصفوفة تجاور الرسم البياني.

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

إنّ الإنشاءات البسيطة لمصفوفة تجاور الرسم البياني ، على سبيل المثال باستخدام نواة RBF، تجعلها كثيفة، وبالتالي تتطلب${\displaystyle n^{2}}$الذاكرة و${\displaystyle n^{2}}$AO لتحديد كل من${\displaystyle n^{2}}$عناصر المصفوفة. يمكن استخدام طريقة نيستروم ^{[ 6 ]} لتقريب مصفوفة التشابه، لكن المصفوفة التقريبية ليست موجبة العناصر ^{[ 7 ]،} أي لا يمكن تفسيرها على أنها تشابه قائم على المسافة.

تعتمد الخوارزميات المستخدمة لإنشاء مصفوفة تجاور الرسم البياني كمصفوفة متفرقة عادةً على البحث عن أقرب جار ، حيث تقوم هذه الخوارزمية بتقدير أو أخذ عينة من جوار نقطة بيانات معينة بحثًا عن أقرب الجيران، ثم تحسب المدخلات غير الصفرية لمصفوفة التجاور من خلال مقارنة أزواج الجيران فقط. وبالتالي، يحدد عدد أقرب الجيران المختارين عدد المدخلات غير الصفرية، وغالبًا ما يكون هذا العدد ثابتًا بحيث لا يتطلب ذلك استخدامًا كبيرًا للذاكرة.${\displaystyle n}$-بواسطة-${\displaystyle n}$مصفوفة تجاور الرسم البياني هي فقط${\displaystyle O(n)}$، فقط${\displaystyle O(n)}$يلزم إجراء عمليات حسابية متسلسلة لحساب${\displaystyle O(n)}$المدخلات غير الصفرية، ويمكن تشغيل العمليات الحسابية بسهولة بالتوازي.

تكلفة حساب${\displaystyle n}$-بواسطة-${\displaystyle k}$(مع${\displaystyle k\ll n}$مصفوفة المتجهات الذاتية المختارة للرسم البياني. عادةً ما تكون مصفوفة لابلاس متناسبة مع تكلفة ضرب المتجهات الذاتية المختارة.${\displaystyle n}$-بواسطة-${\displaystyle n}$يتم تمثيل مصفوفة لابلاس بيانيًا بواسطة متجه، وتختلف هذه التكلفة اختلافًا كبيرًا بناءً على ما إذا كانت مصفوفة لابلاس البيانية كثيفة أم متفرقة. في حالة المصفوفة الكثيفة، تكون التكلفة كالتالي:${\displaystyle O(n^{2})}$التكلفة التي يتم الاستشهاد بها بشكل شائع في الأدبيات${\displaystyle O(n^{3})}$يأتي ذلك من الاختيار${\displaystyle k=n}$ومن الواضح أن هذا مضلل، لأنه، على سبيل المثال، في التجميع الطيفي الهرمي${\displaystyle k=1}$كما هو محدد بواسطة متجه فيدلر .

في الحالة النادرة لـ${\displaystyle n}$-بواسطة-${\displaystyle n}$مصفوفة لابلاس للرسم البياني مع${\displaystyle O(n)}$المدخلات غير الصفرية، وتكلفة ضرب المصفوفة في المتجه، وبالتالي تكلفة حساب${\displaystyle n}$-بواسطة-${\displaystyle k}$مع${\displaystyle k\ll n}$مصفوفة المتجهات الذاتية المختارة هي${\displaystyle O(n)}$، مع حجم الذاكرة فقط${\displaystyle O(n)}$— كلاهما يمثلان الحد الأدنى الأمثل لتعقيد التجميع${\displaystyle n}$نقاط البيانات. علاوة على ذلك، يمكن لخوارزميات حل القيم الذاتية الخالية من المصفوفات، مثل LOBPCG، أن تعمل بكفاءة بالتوازي، على سبيل المثال، على وحدات معالجة رسومية متعددة ذات ذاكرة موزعة ، مما ينتج عنه ليس فقط مجموعات عالية الجودة، والتي تشتهر بها عملية التجميع الطيفي، ولكن أيضًا أداءً فائقًا. ^{[ 8 ]}

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

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

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

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

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

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

تعتمد خوارزمية DBSCAN على تحديد المناطق المتصلة كثافتها في فضاء الإدخال: وهي نقاط يمكن الوصول إليها من بعضها البعض عبر سلسلة من النقاط المجاورة ضمن نصف قطر محدد (ε)، وتحتوي على الحد الأدنى من النقاط (minPts). تتفوق هذه الخوارزمية في اكتشاف تجمعات ذات أشكال عشوائية وفصل التشويش دون الحاجة إلى تحديد عدد التجمعات مسبقًا.

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

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

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