Algoritma apa yang harus saya gunakan untuk mengelompokkan dataset biner besar ke dalam beberapa kategori?

Saya memiliki matriks besar (650K baris * 62 kolom) data biner (hanya 0-1 entri). Matriksnya sebagian besar jarang: sekitar 8% diisi.

Saya ingin mengelompokkannya menjadi 5 grup - misalnya dinamai dari 1 hingga 5. Saya telah mencoba pengelompokan hierarkis dan tidak dapat menangani ukurannya. Saya juga telah menggunakan algoritma clustering k-means berbasis hamming distance, mengingat 650K bit vektor panjang 62. Saya tidak mendapatkan hasil yang tepat dengan semua ini.

Tolong bantu.

clustering dataset k-means binary-data Tidak terikat26
sumber

Saya tidak bisa berkomentar b / c dari 1 perwakilan saya jadi saya harus mengetik ini sebagai jawaban. Anda mungkin melihat kesamaan Jaccard. Saya pikir python scipy memiliki implementasi itu. Jaccard ...

gobrewers14

Apakah ada alasan untuk menganggap data secara alami terbagi dalam lima kelompok, setidaknya sampai batas tertentu? Apakah Anda benar-benar tertarik pada pengelompokan baris, atau apakah Anda juga tertarik pada hubungan antara 62 sifat yang dikodekan dalam vektor bit? Jika yang terakhir, maka teknik lain lebih cocok.

micans

Jawaban:

Anda mengajukan pertanyaan yang salah.

Alih-alih bertanya "algoritma apa", Anda harus bertanya "apa kategori / klaster yang berarti dalam aplikasi Anda".

Saya tidak terkejut bahwa algoritma di atas tidak berfungsi - mereka dirancang untuk kasus penggunaan yang sangat berbeda. k-means tidak bekerja dengan jarak lain yang berubah-ubah. Jangan gunakan dengan jarak Hamming. Ada alasan mengapa ini disebut k- means , itu hanya masuk akal untuk digunakan ketika rata- rata aritmatika bermakna (yang bukan untuk data biner).

Anda mungkin ingin mencoba k-mode sebagai gantinya, IIRC ini adalah varian yang sebenarnya dimaksudkan untuk digunakan dengan data kategororial, dan data biner agak kategororial (tetapi sparsity mungkin masih membunuh Anda).

Tapi pertama-tama, sudahkah Anda menghapus duplikat untuk menyederhanakan data Anda, dan menghapus kolom unik / kosong misalnya?

Mungkin APRIORI atau pendekatan serupa juga lebih berarti untuk masalah Anda.

Either way, pertama cari tahu apa yang Anda butuhkan, lalu algoritma mana yang bisa menyelesaikan tantangan ini. Bekerja berdasarkan data , bukan dengan mencoba algoritma acak.

Memiliki QUIT - Anony-Mousse
sumber

Bisakah Anda jelaskan mengapa "Jangan gunakan dengan jarak Hamming"? Mungkin masuk akal, setelah semua itu tersedia di Matlab. Saya tidak keberatan membuka pertanyaan baru, jika masuk akal.

Dror Atariah

Karena artinya. Rata-rata aritmatika tidak ada artinya dengan jarak hamming atau data biner. Gunakan mode atau medoid sebagai gantinya.

Memiliki QUIT - Anony-Mousse

Hanya untuk memastikan saya melakukannya dengan benar: matlab menggunakan mean aritmatika ketika memperbarui centroid saat menggunakan k-means bersama dengan metrik hamming. Apakah itu benar? Apa cara yang tepat untuk menggunakan metrik ini di matlab?

Dror Atariah

k-means disebut k- means karena menggunakan mean. Kalau tidak, itu disebut k-medoid, k-mode, dll. Rata-rata baik untuk L2 - jumlah penyimpangan kuadrat.

Memiliki QUIT - Anony-Mousse

Jadi, matlab menggunakan k- means bersama dengan metrik hamming; ini tidak masuk akal.

Dror Atariah

Mungkin saya agak terlambat dengan jawaban, tapi mungkin itu akan berguna untuk beberapa orang di masa depan.

Teori Resonansi Adaptif adalah algoritma yang baik untuk masalah klasifikasi biner. Periksa tentang ART 1. Informasi lebih lanjut dapat Anda lihat di buku Neural Network Design gratis di bab 19.

Jaringan ini menggabungkan ide biologis yang hebat dan implementasi matematika yang baik. Algoritma ini juga mudah diimplementasikan dan, dalam buku ini, Anda juga dapat menemukan instruksi langkah demi langkah tentang cara membuat classifier ini.

itdxer
sumber

Algoritma klasik untuk pengelompokan data biner adalah model Bernoulli Mixture. Model ini dapat disesuaikan menggunakan metode Bayesian dan dapat digunakan juga menggunakan EM (Ekspektasi Maksimalisasi). Anda dapat menemukan contoh kode python di seluruh GitHub sementara yang pertama lebih kuat tetapi juga lebih sulit. Saya memiliki implementasi C # dari model di GitHub (menggunakan Infer.NET yang memiliki lisensi terbatas!).

Modelnya cukup sederhana. Pertama-tama, sampel cluster yang menjadi titik data. Kemudian, sampel secara independen dari Bernoullis sebanyak yang Anda miliki dimensi dalam dataset Anda. Perhatikan bahwa ini menyiratkan independensi bersyarat dari nilai-nilai biner yang diberikan cluster!

Dalam pengaturan Bayesian, penugasan cluster yang sebelumnya adalah distribusi Dirichlet. Ini adalah tempat untuk meletakkan prior jika Anda yakin beberapa cluster lebih besar dari yang lain. Untuk setiap cluster, Anda harus menentukan sebelumnya, distribusi Beta, untuk setiap distribusi Bernoulli. Biasanya ini sebelumnya adalah Beta (1,1) atau seragam. Akhirnya, jangan lupa untuk secara otomatis menginisialisasi penugasan cluster ketika data diberikan. Ini akan merusak simetri dan sampler tidak akan macet.

Ada beberapa fitur keren dari model BMM dalam pengaturan Bayesian:

Pengelompokan online (data dapat diterima sebagai aliran)
Model dapat digunakan untuk menyimpulkan dimensi yang hilang

Yang pertama sangat berguna ketika dataset sangat besar dan tidak akan muat dalam RAM mesin. Yang kedua dapat digunakan dalam semua jenis tugas imputasi data yang hilang misalnya. menusuk bagian yang hilang dari gambar MNIST biner.

Vladislavs Dovgalecs
sumber