Clustering berkelanjutan

9

Jadi saya punya masalah yang saya hadapi sehubungan dengan pengelompokan data langsung yang terus mengalir. Karena saya memiliki kumpulan data yang terus bertambah, saya tidak yakin apa cara terbaik untuk menjalankan pengelompokan yang efisien dan efektif. Saya telah menemukan beberapa solusi yang mungkin termasuk:

  1. Menetapkan batas pada berapa banyak titik data yang diizinkan, sehingga kapan pun batas tersebut tercapai saat titik data lain masuk pada titik terlama dihapus. Pada dasarnya, ini menunjukkan bahwa data yang lebih lama tidak cukup relevan bagi kita untuk peduli dengan apa yang kita kehilangan dengan membuangnya.

  2. Setelah ada cukup data untuk membuat pengelompokan yang baik, pertimbangkan ini "pengaturan" dan sebagai poin baru datang, daripada mengelompokkan kembali semua data hanya mencari tahu pusat cluster mana yang paling dekat dengan titik baru dan menambahkannya ke sana. Manfaatnya di sini adalah Anda dapat menghindari keharusan mengelompokkan kembali pada setiap titik baru dan Anda tidak perlu menyimpan semua titik lainnya, hanya pusat-pusat cluster, mengingat pengelompokan ini "cukup baik". The downside adalah bahwa menjalankan kembali algoritma dengan semua titik data dari awal mungkin lebih akurat.

Sementara itu adalah beberapa solusi potensial yang saya singgung, saya ingin tahu apakah ada teknik yang lebih dikenal untuk menghadapi masalah ini. Saya pikir situs-situs seperti Google harus menghadapinya entah bagaimana (dan saya berharap bahwa "tambahkan lebih banyak ram, server, dan prosesor" atau "terus kembangkan pusat data Anda" bukan satu-satunya jawaban yang tersedia).

Suresh Venkat
sumber

Jawaban:

9

Ada cukup banyak pekerjaan pada pengelompokan aliran (yang sedikit berbeda dengan metode online, tetapi pada dasarnya apa yang Anda inginkan). Referensi di atas oleh Guha et al adalah yang sangat bagus, dan untuk perspektif yang lebih umum tentang jenis teknik apa yang bekerja, dan metode apa yang telah digunakan di masa lalu (baik heuristik dan tepat), Anda mungkin ingin melihat survei saya tentang pengelompokan di aliran .

Suresh Venkat
sumber
7

Anda juga dapat melihat catatan untuk Kuliah 14 dan Kuliah 15 dari kursus saya tentang algoritma aliran data.

Piotr
sumber
4

Saya suka survei Suresh di atas, dan merangkum berbagai pendekatan dalam pengelompokan aliran. Anda tidak meminta ini, tetapi ada kemungkinan dalam beberapa kasus, masalahnya adalah bahwa data kontinu dilihat oleh server terdistribusi, kita harus memelihara pengelompokan di pusat, dan tidak harus memindahkan banyak data di sekitar. Lihat di sini .

saya juga
sumber
selamat datang, Muthu!
Suresh Venkat