Pengelompokan yang efisien ruang

Kebanyakan algoritma pengelompokan yang saya lihat dimulai dengan membuat jarak masing-masing untuk setiap titik, yang menjadi masalah pada kumpulan data yang lebih besar. Apakah ada yang tidak melakukannya? Atau apakah itu dalam semacam pendekatan parsial / perkiraan / terhuyung-huyung?

Algoritma / implementasi clustering mana yang membutuhkan waktu kurang dari O (n ^ 2) ruang?

Apakah ada daftar algoritma dan persyaratan Ruang dan Waktu di suatu tempat?

K-Means dan Mean-Shift menggunakan deskriptor sampel mentah (tidak perlu melakukan pra-komputasi matriks afinitas).

Jika tidak, untuk pengelompokan spektral atau pengelompokan daya iterasi, Anda dapat menggunakan representasi matriks jarang (misalnya Baris Terkompresi Terkini) dari matriks afinitas k-tetangga terdekat (untuk beberapa jarak atau metrik afinitas). Jika k kecil (misalkan 5 atau 10). Anda akan mendapatkan representasi yang sangat efisien ruang (2 * n_samples * k * 8 byte untuk nilai floating point presisi ganda).

Beberapa algoritma pengelompokan dapat menggunakan struktur indeks spasial. Ini memungkinkan misalnya DBSCAN dan OPTICS untuk berjalan dalam waktu (selama indeks memungkinkan O ( log n ) query).$O(n\log n)$$O(\log n)$

Jelas, suatu algoritma yang berjalan dalam kompleksitas ini tidak membangun matriks jarak .$O(n^2)$

Untuk beberapa algoritma, seperti pengelompokan hierarkis dengan hubungan tunggal dan hubungan lengkap, ada algoritma yang dioptimalkan tersedia (SLINK, CLINK). Hanya saja kebanyakan orang menggunakan apa pun yang mereka dapat dan apa pun yang mudah diterapkan. Dan hirarkis pengelompokan mudah untuk menerapkan naif, menggunakan iterasi atas n 2 matriks jarak (yang mengakibatkan O ( n 3 ) algoritma ...).$n$$n^2$$O(n^3)$

Saya tidak mengetahui daftar lengkap yang membandingkan algoritma pengelompokan. Mungkin ada 100+ algoritma clustering. Setidaknya ada selusin varian k-means, misalnya. Plus, ada kompleksitas run-time serta kompleksitas memori; ada kasus rata-rata dan terburuk. Ada perbedaan implementasi yang sangat besar (misalnya, single-link yang disebutkan di atas; dan implementasi DBSCAN yang tidak menggunakan indeks, dan dengan demikian berada di , dan sementara mereka tidak perlu menyimpan matriks jarak n × n penuh , mereka maka masih perlu menghitung semua jarak berpasangan). Plus ada banyak parameter. Untuk k-means, $O(n^2)$$n\times n$$k$sangat penting. Untuk hampir semua algoritma, fungsi jarak membuat perbedaan besar (banyak implementasi hanya memungkinkan jarak Euclidean ...). Dan begitu Anda mendapatkan fungsi jarak yang mahal (di luar hal-hal sepele seperti Euclidean), jumlah perhitungan jarak dapat dengan cepat menjadi bagian utama. Jadi, Anda perlu membedakan antara jumlah operasi secara total, dan jumlah perhitungan jarak yang dibutuhkan. Jadi suatu algoritma yang ada dalam operasi tetapi hanya perhitungan jarak O ( n ) yang dapat dengan mudah mengungguli algoritma yang O ( n log n $O(n^2)$$O(n)$$O(n \log n)$di keduanya, ketika fungsi jarak benar-benar mahal (katakanlah, fungsi jarak itu sendiri adalah ).$O(n)$

Pertanyaan bagus. Metode pembuat jerami untuk mengatakan 3 tetangga terdekat adalah dengan sampel Nsample tetangga setiap titik data, menjaga yang terdekat 3. Sementara sepele, menjalankan ini untuk beberapa nilai Nsample akan memberi Anda beberapa gagasan tentang rasio sinyal / kebisingan, kebisingan dekat / latar belakang , mudah diplot untuk data Anda . Trik tambahan adalah memeriksa tetangga tetangga, untuk melihat apakah ada yang lebih dekat daripada tetangga langsung. Juga, jika data input sudah dikocok dengan baik, sampel dalam blok, jika tidak cache akan thrash.

(Ditambahkan): lihat fastcluster di R dan saya percaya pada SciPy v0.11.
Untuk teks, lihat pencarian google-all-pair-similarity .

Ulangi, "Ukuran ketidaksamaan yang tepat jauh lebih penting dalam memperoleh kesuksesan dengan pengelompokan daripada pilihan algoritma pengelompokan" - memilih-metode pengelompokan .