Saya sudah berpikir tentang menulis posting blog tentang analisis yang menarik ini oleh Kleinberg (2002) yang mengeksplorasi kesulitan pengelompokan. Kleinberg menguraikan tiga desiderata yang tampaknya intuitif untuk fungsi pengelompokan dan kemudian membuktikan bahwa tidak ada fungsi tersebut. Ada banyak algoritma pengelompokan yang memuaskan dua dari tiga kriteria; Namun, tidak ada fungsi yang dapat memuaskan ketiganya secara bersamaan.

Secara singkat dan tidak resmi, tiga desiderata yang diuraikannya adalah:

• Scale-Invariance : Jika kita mentransformasikan data sehingga semuanya terentang merata ke segala arah, maka hasil pengelompokan seharusnya tidak berubah.
• Konsistensi : Jika kita merentangkan data sehingga jarak antara cluster meningkat dan / atau jarak dalam cluster berkurang, maka hasil clustering tidak boleh berubah.
• Kekayaan : Fungsi pengelompokan secara teoritis harus dapat menghasilkan partisi / pengelompokan titik data yang sewenang-wenang (dengan tidak adanya mengetahui jarak berpasangan antara dua titik)

Pertanyaan:

(1) Apakah ada intuisi yang baik, gambaran geometris yang dapat menunjukkan ketidakkonsistenan antara ketiga kriteria ini?

(2) Ini mengacu pada rincian teknis untuk kertas. Anda harus membaca tautan di atas untuk memahami bagian pertanyaan ini.

Di koran, bukti untuk teorema 3.1 agak sulit bagi saya untuk mengikuti pada poin. Saya terjebak di: "Biarkan $f$ menjadi fungsi pengelompokan yang memenuhi Konsistensi. Kami mengklaim bahwa untuk setiap partisi $\Gamma \in \text{Range}(f)$ , ada bilangan real positif $a < b$ sehingga pasangan $(a, b)$ adalah $\Gamma$ - memaksa. "

Saya tidak melihat bagaimana ini bisa terjadi ... Bukankah partisi di bawah contoh-counter di mana $a > b$ (yaitu jarak minimum antara cluster lebih besar dari jarak maksimum dalam cluster)?

Sunting: ini jelas bukan contoh tandingan, saya bingung sendiri (lihat jawaban).

• Ackerman & Ben-David (2009). Ukuran Kualitas Clustering: Satu Set Aksioma Aksi untuk Clustering
  • Tunjukkan beberapa masalah dengan aksioma "konsistensi"

Dengan satu atau lain cara, setiap algoritma pengelompokan bergantung pada beberapa gagasan "kedekatan" poin. Tampaknya secara intuitif jelas bahwa Anda dapat menggunakan gagasan relatif (invarian skala) atau gagasan kedekatan mutlak (konsisten), tetapi tidak keduanya .

Pertama saya akan mencoba mengilustrasikan ini dengan sebuah contoh, dan kemudian melanjutkan untuk mengatakan bagaimana intuisi ini cocok dengan Teorema Kleinberg.

Contoh ilustratif

Misalkan kita memiliki dua set dan S 2 dari 270 poin masing-masing, diatur dalam pesawat seperti ini:$S_1$$S_2$$270$

$\hskip{6em}$

Anda mungkin tidak melihat poin di salah satu dari foto-foto ini, tapi itu hanya karena banyak poin yang sangat berdekatan. Kami melihat lebih banyak poin ketika memperbesar:$270$

$\hskip{3em}$

Anda mungkin akan secara spontan setuju bahwa, dalam kedua set data, poin-poin tersebut diatur dalam tiga kelompok. Namun, ternyata jika Anda memperbesar salah satu dari tiga kelompok , Anda melihat yang berikut:$S_2$

$\hskip{3em}$

Jika Anda percaya pada gagasan kedekatan mutlak, atau konsistensi, Anda akan tetap mempertahankannya, terlepas dari apa yang baru saja Anda lihat di bawah mikroskop, hanya terdiri dari tiga cluster. Memang, satu-satunya perbedaan antara S 1 dan S 2 adalah bahwa, di dalam setiap kluster, beberapa titik sekarang lebih dekat satu sama lain. Di lain pihak, jika Anda meyakini gagasan tentang kedekatan, atau invariansi skala, Anda akan cenderung berpendapat bahwa S 2 tidak terdiri dari 3 tetapi dari 3 × 3 = 9 cluster. Tidak satu pun dari sudut pandang ini yang salah, tetapi Anda harus membuat pilihan dengan satu atau lain cara.$S_2$$S_1$$S_2$$S_2$$3$$3×3 = 9$

Kasus untuk invarian isometri

Jika Anda membandingkan intuisi di atas dengan Teorema Kleinberg, Anda akan menemukan bahwa mereka sedikit berselisih. Memang, Teorema Kleinberg tampaknya mengatakan bahwa Anda dapat mencapai skala invarian dan konsistensi secara bersamaan selama Anda tidak peduli dengan properti ketiga yang disebut kekayaan. Namun, kekayaan bukan satu-satunya properti yang hilang jika Anda secara bersamaan bersikeras pada invarian skala dan konsistensi. Anda juga kehilangan properti lain yang lebih mendasar: isometry-invariance. Ini adalah properti yang tidak ingin saya korbankan. Karena tidak muncul di koran Kleinberg, aku akan memikirkannya sebentar.

Singkatnya, algoritma pengelompokan adalah invarian isometrik jika outputnya hanya bergantung pada jarak antara titik, dan bukan pada beberapa informasi tambahan seperti label yang Anda lampirkan ke poin Anda, atau pada pemesanan yang Anda terapkan pada poin Anda. Saya harap ini terdengar seperti kondisi yang sangat ringan dan sangat alami. Semua algoritma yang dibahas dalam makalah Kleinberg adalah isometri invarian, kecuali untuk algoritma keterkaitan tunggal dengan kondisi berhenti -cluster. Menurut uraian Kleinberg, algoritma ini menggunakan urutan leksikografis dari poin, jadi hasilnya mungkin tergantung pada bagaimana Anda memberi label. Misalnya, untuk satu set tiga titik yang sama, output dari algoritma hubungan tunggal dengan $k$$2$kondisi berhenti -cluster akan memberikan jawaban yang berbeda sesuai dengan apakah Anda label tiga poin Anda sebagai "kucing", "anjing", "tikus" (c <d <m) atau sebagai "Tom", "Spike", "Jerry" (J <S <T):

$\hskip{6em}$

Perilaku yang tidak alami ini tentu saja dapat dengan mudah diperbaiki dengan mengganti kondisi berhenti cluster dengan “ ( ≤ k ) kondisi berhenti positif”. Idenya adalah tidak memutuskan hubungan antara titik yang sama, dan untuk berhenti menggabungkan cluster segera setelah kami telah mencapai paling banyak k cluster. Algoritma yang diperbaiki ini masih akan menghasilkan klaster k sebagian besar waktu, dan itu akan menjadi invarian isometry dan skala invarian. Dalam perjanjian dengan intuisi yang diberikan di atas, bagaimanapun tidak akan lagi konsisten.$k$$(≤ k)$ $k$$k$

Untuk definisi invarian isometry yang tepat, ingat bahwa Kleinberg mendefinisikan algoritma pengelompokan pada himpunan terbatas sebagai peta yang menetapkan untuk setiap metrik pada S sebuah partisi S : Γ : { metrik pada  S } → { partisi  S $S$$S$$S$ Sebuahisometry i antara dua metrik d dan d ' pada S adalah permutasi i : S → S sehingga d ' ( i ( x ) , i ( y ) ) = d ( x , y ) untuk semua poin x dan y di S .

Definisi: Algoritma pengelompokan adalah isometri invarian jika memenuhi syarat berikut: untuk setiap metrik d dan d ′ , dan setiap isometri i di antara keduanya, titik i ( x ) dan i ( y ) terletak pada gugus yang sama Γ ( d ′ ) jika dan hanya jika titik asli x dan y terletak pada gugus Γ ( d ) yang sama .$Γ$$d$$d'$$i$$i(x)$$i(y)$$Γ(d')$$x$$y$$Γ(d)$

Ketika kita berpikir tentang algoritma pengelompokan, kita sering mengidentifikasi himpunan abstrak dengan himpunan titik konkret di pesawat, atau di beberapa ruang ambient lainnya, dan bayangkan memvariasikan metrik pada S sebagai memindahkan titik S di sekitar. Memang, inilah sudut pandang yang kami ambil dalam contoh ilustrasi di atas. Dalam konteks ini, invarian isometri berarti bahwa algoritma pengelompokan kami tidak peka terhadap rotasi, refleksi, dan terjemahan.$S$$S$$S$

$\hskip{6em}$

Sebuah varian dari Teorema Kleinberg

Intuisi yang diberikan di atas ditangkap oleh varian berikut dari Teorema Kleinberg.

Teorema: Tidak ada algoritma pengelompokan isometri-invarian non-trivial yang secara bersamaan konsisten dan berskala-invarian.

Di sini, dengan algoritma pengelompokan sepele , maksud saya salah satu dari dua algoritma berikut:

1. $S$

2. $S$

Klaimnya adalah bahwa algoritma konyol ini adalah satu - satunya dua algoritma invarian isometry yang konsisten dan invarian-skala.

$S$$Γ$$d₁$$S$$d₁(x,y) = 1$$x ≠ y$$S$$Γ$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$d$$S$$≥ 1$$d$$Γ(d) = Γ(d₁)$$Γ$$Γ(d₁)$$d$$S$$≤ 1$$Γ(d)=Γ(d₁)$$Γ$

Tentu saja, bukti ini sangat dekat dengan bukti Margareta Ackerman tentang teorema asli Kleinberg, yang dibahas dalam jawaban Alex Williams.

Ini adalah intuisi yang saya hasilkan (cuplikan dari posting blog saya di sini ).

$d_1$$d_2$$d_3$$d_2$$d_3$$d_1$$d_1 \rightarrow d_3$$d_2 \rightarrow d_3$