Menentukan berbagai kelompok data 1d dari basis data

24

Saya memiliki tabel transfer data antara node yang berbeda. Ini adalah basis data yang sangat besar (dengan hampir 40 juta transfer). Salah satu atribut adalah jumlah byte (nbytes) transfer yang berkisar dari 0 byte hingga 2 tera byte. Saya ingin mengelompokkan nbytes sehingga diberikan k cluster beberapa transfer x1 milik k1 cluster, x2 transfters ke k2 dll.

Dari terminologi yang saya gunakan, Anda mungkin sudah menebak apa yang sedang saya lakukan: K-means. Ini adalah data 1d karena nbytes adalah satu-satunya fitur yang saya pedulikan. Ketika saya mencari metode yang berbeda untuk ini saya melihat EM disebutkan beberapa kali bersama dengan pendekatan non-clustering. Saya ingin tahu tentang pandangan Anda tentang cara mendekati masalah ini (khususnya apakah akan mengelompok atau tidak untuk mengelompok).

Terima kasih!

clustering k-means Shaun
sumber
Apa itu "transfer x1", "transfer x2" dll.? Apakah "tipe transfer" adalah variabel kedua?
Peter Flom - Pasang kembali Monica
Transfer x1 hanyalah cara bagi saya untuk mengatakan bahwa 500 transfer ini memiliki ukuran transfer sekitar nilai tertentu (ini akan menjadi rata-rata untuk kluster tersebut dalam k-means).
Shaun
5
Saya bukan ahli pengelompokan, tetapi dengan begitu banyak data & hanya 1 dimensi, saya ingin tahu apakah Anda bisa membuat beberapa plot kepadatan kernel menggunakan bandwidth yang berbeda dan melihat berapa banyak mode / puncak yang Anda temukan, & apakah hasilnya tampak seperti itu akan berguna untukmu.
gung - Reinstate Monica
1
Anda bertanya apakah akan mengelompok atau tidak. Apa yang akan menjadi tujuan Anda dari pengelompokan? Apakah Anda akan menggunakan cluster untuk tujuan lain, atau ini kepentingan teoretis?
Peter Flom - Reinstate Monica
Beberapa atribut lain dari tabel adalah nama pengguna, tanggal mulai dan berakhir. Harapan saya adalah dengan mengelompokkan transfer berdasarkan ukuran transfer, saya kemudian dapat merujuk atribut lain dari transfer tertentu untuk melihat siapa yang mentransfer berapa pada bulan apa tahun tersebut. Apa yang akan kita lakukan dengan pengamatan ini, saya belum tahu. Tapi itu semacam tujuan saya.
Shaun

Jawaban:

43

Dalam data satu dimensi, jangan gunakan analisis kluster.

Analisis cluster biasanya merupakan teknik multivariat. Atau izinkan saya mengatakannya sebaliknya: untuk data satu dimensi - yang benar-benar dipesan - ada teknik yang jauh lebih baik. Menggunakan k-means dan teknik serupa di sini adalah pemborosan total, kecuali jika Anda berupaya cukup untuk benar-benar mengoptimalkannya untuk kasing 1-d.

Sekedar memberi Anda contoh: untuk k-berarti adalah umum untuk menggunakan objek acak k sebagai seed awal. Untuk data satu dimensi, cukup mudah untuk melakukan yang lebih baik dengan hanya menggunakan kuantil yang sesuai (1 / 2k, 3 / 2k, 5 / 2k dll.), Setelah mengurutkan data satu kali , dan kemudian mengoptimalkan dari titik awal ini. Namun, data 2D tidak dapat diurutkan sepenuhnya. Dan dalam kotak, kemungkinan akan ada sel kosong.

Saya juga tidak akan menyebutnya cluster. Saya akan menyebutnya interval . Apa yang benar-benar ingin Anda lakukan adalah mengoptimalkan batas interval. Jika Anda melakukan k-means, itu akan menguji untuk setiap objek jika harus dipindahkan ke cluster lain. Itu tidak masuk akal dalam 1D: hanya objek pada batas interval yang perlu diperiksa. Itu jelas jauh lebih cepat, karena hanya ada ~ 2k objek di sana. Jika mereka belum memilih interval lain, lebih banyak objek pusat tidak akan baik.

Anda mungkin ingin melihat teknik seperti optimasi Breaks Jenks , misalnya.

Atau Anda dapat melakukan estimasi kepadatan kernel dan mencari minimum kepadatan lokal untuk dipecah di sana. Yang menyenangkan adalah Anda tidak perlu menentukan k untuk ini!

PS silakan gunakan fungsi pencarian. Berikut adalah beberapa pertanyaan tentang pengelompokan data 1-d yang Anda lewatkan:

Anony-Mousse
sumber
Kuantitas tidak selalu setuju dengan kluster. Distribusi 1d dapat memiliki 3 cluster alami di mana dua menampung 10% dari data masing-masing dan yang terakhir berisi 80% dari data. Jadi saya pikir mungkin untuk mengelompokkan di sini, meskipun saya setuju masuk akal untuk mengoptimalkan proses dengan memilih benih dengan cerdas, dll. Atau menggunakan ide lain.
Bitwise
Kuantil mungkin adalah titik awal yang baik untuk mengoptimalkan , itulah yang saya maksudkan. Dan hanya untuk memberikan contoh tentang apa yang dapat Anda lakukan dalam 1D yang tidak bekerja dengan baik dalam dimensi 2+.
Anony-Mousse
Saya setuju bahwa akan layak dicoba untuk menggunakan kuantil sebagai benih, tetapi saya masih akan mencoba beberapa inisialisasi acak (untuk contoh seperti yang saya berikan). Bagaimanapun, metode terbaik adalah dengan hanya melihat plot histogram / kepadatan dan secara manual memilih benih dan kemudian mengoptimalkannya dengan pengelompokan. Itu akan menyatu dengan sangat cepat ke solusi yang baik.
Bitwise
3
Jenks adalah k-means dalam 1D.
whuber
1
@whuber bahkan jika secara matematis, saya harap dia cukup pintar untuk mengeksploitasi bahwa data dapat dipesan . Jika Anda menggunakan pendekatan Lloyd untuk melakukan k-means pada data 1-d, Anda bodoh, karena Anda melakukan banyak perhitungan yang bisa Anda lewatkan. Dan bagi kebanyakan orang, k-means adalah Lloyd. Dan beberapa orang sangat peduli untuk menghindari perhitungan ulang yang tidak perlu.
Anony-Mousse
1

Apakah pertanyaan Anda apakah Anda harus mengelompokkan atau metode apa yang harus Anda gunakan untuk mengelompokkan?

Mengenai apakah Anda harus mengelompokkan, itu tergantung apakah Anda ingin mempartisi data Anda secara otomatis (misalnya jika Anda ingin mengulangi partisi ini beberapa kali). Jika Anda melakukan ini hanya sekali, Anda bisa melihat histogram dari distribusi nilai-nilai Anda, dan mempartisi dengan mata, seperti yang diusulkan dalam komentar. Saya akan merekomendasikan melihat data dengan mata, karena itu dapat membantu Anda menentukan berapa banyak cluster yang Anda inginkan dan juga apakah clustering "bekerja".

Mengenai jenis pengelompokan, k-means harus baik-baik saja jika ada cluster "nyata" dalam data. Jika Anda tidak melihat klaster apa pun dalam histogram, toh tidak masuk akal mengelompokkannya, karena setiap partisi rentang data Anda akan memberikan kluster yang valid (atau dalam kasus inisiasi kman secara acak, Anda akan mendapatkan kluster yang berbeda setiap dijalankan).

Bitwise
sumber