Apa perbedaan antara vektor eigen matriks afinitas dan vektor vektor eigen Laplacian dalam konteks pengelompokan spektral?

8

Dalam pengelompokan spektral, ini adalah praktik standar untuk memecahkan masalah vektor eigen

L.v=λv

di mana adalah grafik Laplacian, adalah vektor eigen yang terkait dengan nilai eigen .L.vλ

Pertanyaan saya: mengapa repot-repot mengambil grafik Laplacian? Tidak bisakah saya memecahkan masalah vektor eigen untuk grafik (matriks afinitas) itu sendiri, seperti yang dilakukan pria dalam video ini ?

PS: Saya membuat pertanyaan yang sama di CrossValidated tapi saya pikir ini adalah saluran yang lebih tepat. Maafkan saya jika saya salah.

machine-learning clustering graphs felipeduque
sumber
Tautan video rusak :(
wcochran

Jawaban:

4

Konsepnya sama tetapi Anda semakin bingung dengan jenis data. Clustering Spektral sebagai Ng et al. jelaskan tentang pengelompokan data standar sedangkan matriks Laplacian adalah matriks yang diturunkan grafik yang digunakan dalam teori grafik aljabar.

Jadi intinya adalah bahwa setiap kali Anda mengkodekan kesamaan objek Anda ke dalam matriks, matriks ini dapat digunakan untuk pengelompokan spektral.

Jika Anda memiliki data standar yaitu matriks fitur-sampel, Anda dapat menemukan kedekatan atau afinitas atau apa pun yang Anda ingin menyebutnya sebagai matriks dan menerapkan pengelompokan spektral.

Jika Anda memiliki grafik, afinitas ini akan menjadi apa saja seperti matriks adjacency, distance distance atau matriks Laplacialn dan memecahkan fungsi eigen untuk matriks semacam itu memberi Anda hasil yang sesuai.

Poin tentang menggunakan Laplacian daripada kedekatan adalah untuk menjaga apa yang disebut matriks afinitas positif semi-pasti (dan matriks Laplacian yang dinormalisasi adalah pilihan yang lebih baik karena memberi Anda nilai eigen yang dinormalisasi antara 0 dan 2 dan mengungkapkan struktur grafik yang jauh lebih baik).

Jadi, cerita panjangnya adalah bahwa selama Anda memiliki matriks yang berisi afinitas data Anda, Anda dapat menggunakan spektral clustering secara umum. Perbedaannya adalah dalam rincian (ig milik Laplacian dinormalisasi yang baru saja saya sebutkan)

Kasra Manshaei
sumber
Ya, saya pikir saya agak bingung. Masih belum jelas bagi saya. Jika saya memiliki data standar (tidak ada afinitas terkait), saya dapat menjadikannya matriks afinitas A dengan mengambil jarak berpasangan antara sampel data. Sekarang jika saya melihat A sebagai grafik, saya dapat mengambil Laplacian dan menyelesaikan untuk vektor eigen dan mendapatkan solusi; jika saya tidak melihat A sebagai grafik, saya cukup memecahkan vektor vektor eigen (PCA) dan mendapatkan solusi. Apa bedanya?
felipeduque
Saya membaca pertanyaan Anda lagi. Jawabannya adalah properti (misalnya yang saya sebutkan dalam jawaban saya) Matriks Laplacian memberikan dekomposisi yang lebih baik. Namun Anda absolutly dapat fungsi eigen tunggal untuk setiap matriks terkait kesamaan dan mendapatkan beberapa hasil yang berbeda hanya dalam detail. Misalnya tentang PCA yang Anda sebutkan: PCA mengambil matriks kovarians sehingga menangkap di mana variansnya tinggi tetapi secara umum konsepnya mengikuti arah yang sama dengan teknik dekomposisi spektral lainnya. Saya akan mengoreksi jawaban saya segera setelah saya melihat beberapa kalimat "Saturday Night";)
Kasra Manshaei