Skip to content
Kembali ke hasil pencarian

Spectral Clustering

Diperkenalkan oleh
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
Tahun
2002
Jenis
Graph-based clustering (spectral method)

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Spectral Clustering adalah algoritma pembelajaran tanpa pengawasan berbasis graf, yang diformalkan oleh Ng, Jordan, dan Weiss pada tahun 2002, yang memetakan titik data ke dalam *eigenspace* berdimensi rendah yang berasal dari Laplacian graf kesamaan sebelum menerapkan k-means. *Embedding* spektral ini memungkinkan pemulihan klaster berbentuk sebarang — cincin, bulan sabit, spiral yang saling terkait — yang secara konsisten gagal dipisahkan oleh metode berbasis jarak Euclidean.

Intuisi di balik metode

K-means standar mempartisi ruang berdasarkan jarak garis lurus, sehingga hanya dapat menemukan *blob* cembung yang kira-kira berbentuk bola. Spectral Clustering melewati ini dengan terlebih dahulu menganggap data sebagai jaringan: setiap titik adalah simpul, dan tepi antar simpul membawa bobot yang mencerminkan seberapa mirip kedua titik tersebut. Klaster sesuai dengan wilayah jaringan yang terhubung padat secara internal tetapi terhubung longgar ke bagian lainnya. Matriks Laplacian graf mengkodekan struktur konektivitas ini, dan *eigenvector* terkecilnya bertindak seperti sistem koordinat mulus yang meregangkan data sehingga klaster yang terpisah dengan baik berakhir berjauhan meskipun mereka saling terkait di ruang asli. Langkah k-means sederhana di sistem koordinat baru itu kemudian memisahkannya dengan bersih.

Sejarah

Dasar-dasar teoretis pengelompokan spektral berasal dari karya Fiedler tahun 1973 tentang konektivitas graf dan *eigenvalue* konektivitas aljabar. Shi dan Malik (2000) membawa pendekatan ini ke visi komputer melalui kriteria *normalized-cuts* mereka untuk segmentasi gambar. Ng, Jordan, dan Weiss (2002) menyajikan algoritma yang bersih dan serbaguna di NIPS — yang sekarang paling sering dikutip — bersama dengan analisis teori perturbasi yang menjelaskan kapan dan mengapa metode ini bekerja. Tutorial Von Luxburg tahun 2007 di Statistics and Computing menyatukan berbagai formulasi yang bersaing, mengklarifikasi peran normalisasi Laplacian, dan menjadi referensi standar bagi praktisi. Pengelompokan spektral sekarang menempati tempat sentral dalam kurikulum pembelajaran mesin dan tetap menjadi topik penelitian aktif, dengan pekerjaan yang sedang berlangsung pada perkiraan yang dapat diskalakan, kernel yang kuat, dan ekstensi ke graf dan manifold.

Kapan digunakan

Spectral Clustering sangat cocok ketika klaster dalam data bersifat non-cembung, tidak dapat dipisahkan secara non-linear, atau terhubung oleh jembatan tipis yang tidak dapat dideteksi oleh metode partisi Euclidean — contoh umum termasuk klaster berbentuk cincin, spiral yang saling terkait, dan segmen gambar. Ini sesuai ketika kesamaan berpasangan antar titik dapat dihitung secara bermakna (baik dari kernel pada fitur mentah atau dari matriks afinitas yang diberikan sebelumnya), dan ketika jumlah klaster k diketahui atau dapat diperkirakan dari heuristik *eigengap*. Metode ini tidak memerlukan asumsi distribusi pada bentuk klaster. Keterbatasan praktis termasuk memori kuadratik terhadap jumlah titik (untuk matriks afinitas penuh) dan waktu kubik untuk *eigendecomposition*, membuat formulasi standar mahal di atas sekitar 10.000 titik. Metode perkiraan (*Nystrom*, graf jarang, SVD acak) memperluas jangkauannya ke kumpulan data yang lebih besar.

Batasan dan pertimbangan

  • Membangun matriks afinitas n-kali-n penuh memerlukan memori O(n^2) dan waktu O(n^3) untuk *eigendecomposition*, membuat algoritma naif tidak layak untuk kumpulan data besar.
  • Hasil sensitif terhadap pilihan *bandwidth* kernel sigma dan strategi konstruksi graf; pilihan yang buruk dapat menggabungkan atau memecah klaster.
  • Inisialisasi k-means dalam *embedding* spektral memperkenalkan keacakan; beberapa kali eksekusi dapat menghasilkan partisi yang berbeda.
  • Tidak berskala dengan baik ke ruang fitur berdimensi sangat tinggi tanpa pemilihan kernel yang cermat.
  • Memberikan label klaster saja; tidak menawarkan model generatif dan tidak ada ekstensi *out-of-sample* alami untuk titik baru.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Mendeteksi klaster berbentuk sebarang, termasuk konfigurasi non-cembung dan tidak dapat dipisahkan secara non-linear yang mengalahkan k-means dan model campuran Gaussian.
  • Dapat beroperasi pada matriks kesamaan berpasangan apa pun, tidak hanya jarak Euclidean, membuatnya dapat diterapkan pada graf, string, dan data terstruktur lainnya.
  • Heuristik *eigengap* memberikan panduan berbasis data yang berprinsip untuk memilih jumlah klaster k.
  • Didasarkan pada teori graf spektral yang kaya, memungkinkan analisis konvergensi dan kualitas klaster secara formal.
  • Konseptual sederhana dan mudah diimplementasikan menggunakan pustaka aljabar linear standar.

Penerapan

  • Segmentasi gambar: mempartisi piksel atau *superpixel* menjadi wilayah yang koheren secara perseptual menggunakan kesamaan fitur tingkat piksel.
  • Deteksi komunitas dalam jaringan sosial dan biologis di mana konektivitas berpasangan daripada vektor fitur mendefinisikan struktur.
  • Bioinformatika: mengelompokkan gen atau protein berdasarkan kesamaan profil ekspresi, di mana klaster ekspresi jarang cembung dalam ruang gen.
  • Pemrosesan bahasa alami: pengelompokan dokumen atau kalimat menggunakan kernel kesamaan semantik.
  • Visi komputer: segmentasi gerakan dan partisi *point-cloud* di mana batas klaster tidak beraturan.
  • Analisis data eksploratif: mengungkap struktur klaster yang tidak jelas sebelum menerapkan metode konfirmasi.

Cara kerjanya

Cara kerjanya

1

Matriks kesamaan (afinitas) berpasangan W dibangun dari data. Pilihan yang paling umum adalah kernel Gaussian (RBF), yang memberikan bobot tinggi pada pasangan yang berdekatan dan bobot mendekati nol untuk yang berjauhan. Parameter *bandwidth* sigma mengontrol seberapa cepat kesamaan meluruh seiring jarak; memilihnya dengan baik sangat penting. Alternatifnya, graf tetangga terdekat k (*k-nearest-neighbour graph*) dapat digunakan untuk representasi yang lebih jarang pada kumpulan data besar.

Rumus
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

Matriks derajat D adalah matriks diagonal yang entri ke-i adalah jumlah baris ke-i dari W. Dari W dan D, Laplacian graf ternormalisasi (simetris) L_sym dibentuk. Matriks ini menangkap struktur konektivitas penuh dari graf kesamaan; spektrum *eigenvalue*-nya mengungkapkan berapa banyak klaster alami yang dimiliki data dan seberapa bersih pemisahannya.

Rumus
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

K *eigenvector* yang sesuai dengan k *eigenvalue* terkecil dari L_sym dihitung. *Eigenvector* ini membentuk kolom matriks *embedding* U, yang memiliki satu baris per titik data. Dalam ruang spektral k-dimensi ini, titik-titik yang termasuk dalam klaster yang sama ditarik berdekatan meskipun mereka saling terkait di ruang fitur asli.

Rumus
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

Setiap baris U dibagi dengan norma Euclidean-nya untuk memproyeksikan titik-titik yang di-*embed* ke *hypersphere* satuan. Normalisasi ini, yang diperkenalkan oleh Ng, Jordan, dan Weiss, menghilangkan perbedaan skala palsu antar *eigenvector* dan memastikan bahwa langkah k-means berikutnya berfokus pada struktur sudut dari *embedding* daripada pada besaran.

Rumus
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

Pengelompokan k-means standar diterapkan pada baris matriks *embedding* ternormalisasi T. Karena *embedding* spektral telah mengurai geometri klaster, k-means menemukan partisi yang bermakna bahkan untuk bentuk klaster non-cembung. Label klaster kemudian dipetakan kembali ke titik data asli.

Kesalahan umum

  • Memilih sigma tanpa validasi silang atau penyetelan mandiri yang berprinsip; *bandwidth* yang terlalu kecil menciptakan graf yang terputus, sementara yang terlalu besar menggabungkan klaster yang berbeda.
  • Mengabaikan normalisasi baris matriks afinitas sebelum k-means (langkah normalisasi baris oleh Ng dkk. sangat penting untuk stabilitas).
  • Mengabaikan *eigengap*: menggunakan k tetap tanpa memeriksa spektrum *eigenvalue* sering kali menyebabkan segmentasi yang kurang atau berlebihan.
  • Menerapkan algoritma penuh pada kumpulan data dengan puluhan ribu titik tanpa beralih ke varian perkiraan atau jarang.
  • Membingungkan Laplacian yang tidak ternormalisasi (L = D - W) dan ternormalisasi (L_sym, L_rw), yang dapat mengubah penugasan klaster secara substansial.

Pertanyaan yang sering diajukan

Bagaimana cara memilih jumlah klaster k?

Heuristik *eigengap* adalah panduan standar: hitung *eigenvalue* dari Laplacian ternormalisasi secara berurutan dan cari celah terbesar antar *eigenvalue* berurutan. Indeks di mana celah ini terjadi menunjukkan jumlah klaster alami. Ketika *eigengap* ambigu, pendekatan berbasis stabilitas — menjalankan algoritma untuk beberapa nilai k dan membandingkan penugasan klaster di seluruh perturbasi — dapat membantu.

Bagaimana cara mengatur *bandwidth* kernel Gaussian sigma?

Heuristik umum adalah median jarak berpasangan dalam kumpulan data, atau skema penyetelan mandiri tetangga terdekat (*nearest-neighbour self-tuning scheme*) (Zelnik-Manor & Perona, 2004) yang menetapkan *bandwidth* lokal ke setiap titik. Dalam praktiknya, sigma harus divalidasi dengan memeriksa konektivitas graf afinitas yang dihasilkan: setiap titik harus memiliki setidaknya beberapa tetangga berbobot tinggi, dan graf tidak boleh terfragmentasi menjadi komponen terisolasi.

Mengapa langkah normalisasi baris diperlukan?

*Eigenvector* Laplacian dapat berbeda secara substansial dalam skala. Tanpa menormalisasi setiap baris matriks *embedding* ke panjang satuan, langkah k-means dapat didominasi oleh *eigenvector* dengan magnitudo besar dan mengabaikan komponen yang informatif tetapi bermagnitudo kecil. Normalisasi baris yang diperkenalkan oleh Ng, Jordan, dan Weiss memetakan semua titik ke bola satuan sehingga k-means merespons geometri sudut dari *embedding*.

Bisakah pengelompokan spektral menangani kumpulan data yang sangat besar?

Tidak dalam bentuk naifnya, yang memerlukan waktu O(n^2) memori dan O(n^3) *eigendecomposition*. Untuk n besar, solusi standar meliputi: membangun graf tetangga terdekat k yang jarang (*sparse k-nearest-neighbour graph*) alih-alih matriks afinitas penuh; menggunakan perkiraan Nystrom untuk memperkirakan *eigenvector* dari sub-sampel; atau menerapkan SVD acak. Metode perkiraan ini memulihkan sebagian besar akurasi dengan biaya yang lebih sedikit.

Metode terkait

Sumber

  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.

    Buka referensi publikasi
    Disalin.
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    Buka referensi DOI
    Disalin.
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    Buka referensi DOI
    Disalin.