python kmeans

python-kmeans

implementasi python dari pengelompokan k-means. k-means adalah teknik pembelajaran tanpa pengawasan yang mencoba mengelompokkan titik data serupa ke dalam sejumlah kelompok yang ditentukan pengguna. Contoh di bawah ini menunjukkan perkembangan cluster untuk kumpulan data Iris menggunakan algoritma inisialisasi k-means++ centroid.

Keterangan

k-means mencoba mengidentifikasi jumlah cluster k(<N) yang ditentukan pengguna dari sekumpulan vektor bernilai nyata berdimensi N d. Algoritma ini melanjutkan dengan mencoba meminimalkan jumlah kuadrat jarak dari pusat cluster, ke anggota cluster. Algoritme kanonik berlangsung dalam tiga fase:

1. Inisialisasi k centroid acak (pusat cluster);
2. menetapkan titik data ke cluster terdekat berdasarkan metrik jarak (biasanya jarak Euclidean);
3. memperbarui centroid dengan rata-rata anggota cluster;
4. ulangi langkah 2 & 3 hingga tugas dari langkah 2 tidak berubah.

Output dari algoritme ini adalah penetapan cluster untuk setiap titik data, dan tingkat "distorsi" akhir. Algoritme ini tidak menghasilkan solusi yang terbukti optimal, dan pusat cluster awal dapat menyebabkan algoritma terjebak dalam solusi optimal lokal yang jelas-jelas sub-optimal (lihat contoh dasar 2d di bagian Hasil).

Banyak penelitian berfokus pada:

• memilih pusat cluster awal. K-Means++ adalah metode yang terkenal, dan termasuk dalam implementasi ini, algoritmanya diuraikan dalam sub-bagian berikut.
• menghitung jarak, yaitu menggunakan ukuran selain Euclidean lihat di sini.

K-Means++

Daripada menginisialisasi centroid acak seperti pada langkah 1 di atas, k-means++ secara probabilistik menyebarkan centroid awal untuk menghindari konfigurasi awal yang buruk, algoritmanya adalah:

1. Pilih centroid pertama secara acak.
2. Untuk setiap titik data x, hitung jarak d(x), dari x ke centroid terdekat yang telah dipilih.
3. Pilih titik data untuk menjadi pusat massa berikutnya menggunakan probabilitas tertimbang yang sebanding dengan d(x)2.

Teknik ini mengutamakan titik data yang tidak berada di dekat pusat massa awal lainnya, dan menggunakan kebijakan seleksi yang mengingatkan pada seleksi roda roulette (atau proporsional kebugaran) yang sering digunakan dalam algoritma genetika.

Sumber daya

Algoritma Dasar

• K-Means dijelaskan dalam 10 Algoritma Teratas untuk Penambangan Data;

• K-Means dituangkan dalam Teori Informasi, Inferensi, dan Algoritma Pembelajaran, kutipan di sini;

• Profesor Andrew Moore dari CMU mempunyai beberapa catatan bagus di sini;

• Contoh Edureka, menggunakan data kejahatan

Inisialisasi Cluster

• K-Means++, dan makalah lengkap di sini

• Studi Perbandingan Metode Inisialisasi yang Efisien untuk Algoritma K-Means Clustering

Mengapa tidak menggunakan SciPy?

SciPy memiliki implementasi k-means. Tujuan dari pekerjaan ini adalah untuk membangun implementasi python murni untuk tujuan pembelajaran, dan membantu orang lain mempelajari algoritma k-means. Pembaca yang tertarik dengan pengalaman python minimal akan dapat membaca, dan melangkahi kode ini tanpa kerumitan tambahan dari perpustakaan seperti SciPy. Ini sama sekali tidak dimaksudkan untuk penggunaan produksi :)

Menjalankan kode

Ketergantungan

• ular piton 3.6.3
• matplotlib 2.1.1 - lihat di sini untuk petunjuk instalasi.

Eksekusi

Jalankan kode dengan juru bahasa python:

python kmeans.py ./resources/<config.cfg>

Dimana config.cfg adalah file konfigurasi teks biasa. Format file konfigurasi adalah dict python dengan kolom berikut:

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

Anda harus menentukan:

• file data csv;
• subset bidang yang akan diproyeksikan dari file;
• jumlah cluster yang akan dibentuk, k;
• subset atribut yang digunakan dalam proses pengelompokan;
• secara opsional tentukan fungsi cluster awal (default='rand_init_centroids'), penulis yang tertarik harus menambahkan kode mereka sendiri dan menentukannya di sini;
• konfigurasi plot yang mencakup
  • awalan untuk file png yang dibuat selama proses di direktori kerja, jika ini tidak ditentukan, gambar tidak akan dihasilkan;
  • konfigurasi plot individu, dibatasi pada 2 dimensi per plot.

Hasil

Kumpulan Data Iris

Kumpulan data Iris (iris.config), dari Lichman, M. (2013). Repositori Pembelajaran Mesin UCI. Irvine, CA: University of California, School of Information and Computer Science., adalah kumpulan data yang sangat terkenal dalam komunitas pembelajaran mesin. Berikut hasil cluster awal acak saya:

Data Sintetis 2D Dasar

Data ini dihasilkan untuk tujuan debugging (lihat basic2d.config), dan mengilustrasikan dampak dari pilihan cluster acak awal yang buruk. Hasil di bawah ini menunjukkan konfigurasi centroid awal yang mencegah algoritma mencapai penetapan cluster yang jelas. Dalam hal ini penempatan centroid merah berarti centroid biru menangkap semua titik data di kuadran kiri bawah dan kanan bawah.

Kejahatan

Kumpulan data kejahatan (crime.config) berasal dari Edureka, di sini.