Formalisasi pengelompokan selain dari K-means untuk data yang dapat dipisahkan

Data dunia nyata kadang-kadang memiliki jumlah kluster alami (mencoba mengelompokkannya ke dalam jumlah klaster yang lebih rendah daripada beberapa k ajaib akan menyebabkan peningkatan dramatis pada biaya pengelompokan). Hari ini saya menghadiri kuliah oleh Dr. Adam Meyerson dan dia menyebut jenis data itu sebagai "data yang dapat dipisahkan".

Apa saja formalisasi pengelompokan, selain dari K-means, yang dapat menerima algoritma pengelompokan (perkiraan atau heuristik) yang akan mengeksploitasi pemisahan alami dalam data?

Salah satu model terbaru yang mencoba menangkap gagasan semacam itu adalah oleh Balcan, Blum, dan Gupta '09. Mereka memberikan algoritma untuk berbagai tujuan pengelompokan ketika data memenuhi asumsi tertentu: yaitu bahwa jika data sedemikian rupa sehingga aproksimasi untuk tujuan pengelompokan adalah dekat dengan pengelompokan yang optimal, maka mereka dapat memberikan algoritma yang efisien untuk menemukan suatu pengelompokan hampir-optimal, bahkan untuk nilai yang menemukan -approximation adalah NP-hard. Ini adalah asumsi tentang data yang entah bagaimana "baik" atau "dapat dipisahkan." Lipton memiliki posting blog yang bagus tentang ini.$c$$\epsilon$$c$$c$

Jenis kondisi serupa lainnya tentang data yang diberikan dalam makalah oleh Bilu dan Linial '10 adalah stabilitas-gangguan. Pada dasarnya, mereka menunjukkan bahwa jika data sedemikian rupa sehingga pengelompokan optimal tidak berubah ketika data terganggu (oleh beberapa parameter ) untuk nilai-nilai cukup besar , orang dapat secara efisien menemukan pengelompokan optimal untuk data asli, bahkan ketika masalahnya adalah NP-Hard pada umumnya. Ini adalah gagasan lain tentang stabilitas atau keterpisahan data.$\alpha$$\alpha$

Saya yakin ada karya sebelumnya dan gagasan yang relevan sebelumnya, tetapi ini adalah beberapa hasil teoritis terbaru yang terkait dengan pertanyaan Anda.

Terlepas dari karya-karya oleh Ostrovsky et al , dan karya oleh Arthur dan Vassilvitskii tentang perilaku k-means, ada tubuh karya teoritis tentang k-median Euclidean dan k-means yang mengarah ke algoritma waktu "linear" untuk pengelompokan di bawah formulasi ini. Yang menarik dari karya-karya ini adalah bahwa mereka menggunakan pemisahan sebagai alat dalam analisis, tetapi tidak memerlukannya dalam data.