Algoritma Pengelompokan: Dari Awal Hingga Terkini

Ini bukan waktu yang buruk untuk menjadi Ilmuwan Data. Orang yang serius mungkin tertarik pada Anda jika Anda mengalihkan percakapan ke "Big Data", dan kerumunan pesta lainnya akan tertarik ketika Anda menyebutkan "Kecerdasan Buatan" dan "Pembelajaran Mesin". Bahkan Google menganggap Anda tidak buruk, dan Anda menjadi lebih baik. Ada banyak algoritme 'pintar' yang membantu ilmuwan data melakukan keajaiban mereka. Semuanya mungkin tampak rumit, tetapi jika kita memahami dan mengatur algoritma sedikit, bahkan tidak sulit untuk menemukan dan menerapkan algoritma yang kita butuhkan.

Kursus tentang data mining atau pembelajaran mesin biasanya akan dimulai dengan pengelompokan, karena sederhana dan bermanfaat. Ini adalah bagian penting dari area Pembelajaran Tanpa Pengawasan yang agak lebih luas, di mana data yang ingin kami gambarkan tidak diberi label. Dalam kebanyakan kasus ini adalah di mana pengguna tidak memberi kami banyak informasi tentang apa keluaran yang diharapkan. Algoritme hanya memiliki data dan harus melakukan yang terbaik. Dalam kasus kami, itu harus melakukan clustering – memisahkan data ke dalam kelompok (cluster) yang berisi titik data yang sama, sedangkan perbedaan antar kelompok setinggi mungkin. Titik data dapat mewakili apa saja, seperti klien kami. Pengelompokan dapat berguna jika kita, misalnya, ingin mengelompokkan pengguna yang serupa dan kemudian menjalankan kampanye pemasaran yang berbeda di setiap klaster.

Pengelompokan K-Means

Setelah pengenalan yang diperlukan, kursus Data Mining selalu dilanjutkan dengan K-Means; efektif, banyak digunakan, algoritme pengelompokan serba guna. Sebelum benar-benar menjalankannya, kita harus mendefinisikan fungsi jarak antar titik data (misalnya jarak Euclidean jika kita ingin mengelompokkan titik-titik dalam ruang), dan kita harus mengatur jumlah klaster yang kita inginkan (k).

Algoritma dimulai dengan memilih k titik sebagai centroid awal ('pusat' cluster). Kita bisa saja memilih k titik acak, atau kita bisa menggunakan beberapa pendekatan lain, tetapi memilih titik acak adalah awal yang baik. Kemudian, kami mengulangi dua langkah secara iteratif:

1. Langkah penetapan: masing-masing m poin dari dataset kami ditugaskan ke cluster yang diwakili oleh k centroid terdekat. Untuk setiap titik, kami menghitung jarak ke setiap centroid, dan cukup memilih yang paling tidak jauh.

2. Langkah pembaruan: untuk setiap cluster, centroid baru dihitung sebagai rata-rata semua titik dalam cluster. Dari langkah sebelumnya, kami memiliki satu set poin yang ditugaskan ke sebuah cluster. Sekarang, untuk setiap set tersebut, kami menghitung rata-rata bahwa kami mendeklarasikan centroid baru dari cluster.

Setelah setiap iterasi, centroid bergerak perlahan, dan jarak total dari setiap titik ke centroid yang ditetapkan semakin rendah. Kedua langkah tersebut dilakukan secara bergantian sampai konvergen, artinya sampai tidak ada lagi perubahan penugasan cluster. Setelah beberapa iterasi, kumpulan titik yang sama akan diberikan ke setiap centroid, oleh karena itu mengarah ke centroid yang sama lagi. K-Means dijamin konvergen ke optimum lokal. Namun, itu tidak serta merta harus menjadi solusi keseluruhan yang terbaik (global optimum).

Hasil pengelompokan akhir dapat bergantung pada pemilihan centroid awal, jadi banyak pemikiran telah diberikan untuk masalah ini. Salah satu solusi sederhana adalah menjalankan K-Means beberapa kali dengan tugas awal yang acak. Kami kemudian dapat memilih hasil terbaik dengan mengambil satu dengan jumlah jarak minimal dari setiap titik ke klasternya – nilai kesalahan yang kami coba minimalkan sejak awal.

Pendekatan lain untuk memilih titik awal dapat mengandalkan pemilihan titik yang jauh. Ini dapat menghasilkan hasil yang lebih baik, tetapi kita mungkin memiliki masalah dengan outlier, titik-titik langka yang hanya "tidak aktif" yang mungkin hanya beberapa kesalahan. Karena mereka jauh dari cluster yang berarti, setiap titik tersebut mungkin berakhir menjadi 'cluster' sendiri. Keseimbangan yang baik adalah varian K-Means++ [Arthur dan Vassilvitskii, 2007], yang inisialisasinya masih akan memilih titik acak, tetapi dengan probabilitas sebanding dengan jarak kuadrat dari centroid yang ditetapkan sebelumnya. Poin yang lebih jauh akan memiliki probabilitas lebih tinggi untuk dipilih sebagai centroid awal. Akibatnya, jika ada sekelompok poin, probabilitas bahwa satu poin dari grup akan dipilih juga menjadi lebih tinggi karena probabilitasnya bertambah, menyelesaikan masalah outlier yang kami sebutkan.

K-Means++ juga merupakan inisialisasi default untuk implementasi Scikit-learn K-Means Python. Jika Anda menggunakan Python, ini mungkin perpustakaan pilihan Anda. Untuk Java, perpustakaan Weka mungkin merupakan awal yang baik:

Jawa (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-belajar)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

Dalam contoh Python di atas, kami menggunakan contoh dataset standar 'Iris', yang berisi dimensi kelopak bunga dan sepal untuk tiga spesies iris yang berbeda. Kami mengelompokkan ini menjadi tiga kelompok, dan membandingkan kelompok yang diperoleh dengan spesies (target) yang sebenarnya, untuk melihat bahwa mereka cocok dengan sempurna.

Dalam hal ini, kami tahu bahwa ada tiga kelompok (spesies) yang berbeda, dan K-Means mengenali dengan benar mana yang cocok. Tapi, bagaimana kita memilih jumlah cluster k yang baik secara umum? Pertanyaan semacam ini cukup umum di Machine Learning. Jika kita meminta lebih banyak cluster, mereka akan lebih kecil, dan oleh karena itu kesalahan total (total jarak dari titik ke cluster yang ditetapkan) akan lebih kecil. Jadi, apakah ide yang baik hanya untuk menetapkan k yang lebih besar? Kita mungkin berakhir dengan memiliki k = m, yaitu, setiap titik menjadi pusat massanya sendiri, dengan setiap cluster hanya memiliki satu titik. Ya, kesalahan totalnya adalah 0, tetapi kami tidak mendapatkan deskripsi yang lebih sederhana tentang data kami, juga tidak cukup umum untuk mencakup beberapa poin baru yang mungkin muncul. Ini disebut overfitting, dan kami tidak menginginkan itu.

Cara untuk mengatasi masalah ini adalah dengan memasukkan beberapa penalti untuk jumlah cluster yang lebih besar. Jadi, kami sekarang mencoba meminimalkan tidak hanya kesalahan, tetapi kesalahan + penalti . Kesalahan hanya akan menyatu menuju nol saat kami meningkatkan jumlah cluster, tetapi penalti akan bertambah. Di beberapa titik, keuntungan dari menambahkan cluster lain akan kurang dari penalti yang diperkenalkan, dan kami akan mendapatkan hasil yang optimal. Sebuah solusi yang menggunakan Bayesian Information Criterion (BIC) untuk tujuan ini disebut X-Means [Pelleg dan Moore, 2000].

Hal lain yang harus kita definisikan dengan benar adalah fungsi jarak. Terkadang itu adalah tugas yang mudah, tugas yang logis mengingat sifat data. Untuk titik dalam ruang, jarak Euclidean adalah solusi yang jelas, tetapi mungkin rumit untuk fitur 'unit' yang berbeda, untuk variabel diskrit, dll. Ini mungkin memerlukan banyak pengetahuan domain. Atau, kami dapat menghubungi Machine Learning untuk meminta bantuan. Kita sebenarnya bisa mencoba mempelajari fungsi jarak. Jika kita memiliki set poin pelatihan yang kita tahu bagaimana mereka harus dikelompokkan (yaitu poin yang diberi label dengan klasternya), kita dapat menggunakan teknik pembelajaran terawasi untuk menemukan fungsi yang baik, dan kemudian menerapkannya ke set target kita yang belum mengelompok. .

Metode yang digunakan dalam K-Means, dengan dua langkah bergantian menyerupai metode Expectation-Maximization (EM). Sebenarnya, ini dapat dianggap sebagai versi EM yang sangat sederhana. Namun, jangan bingung dengan algoritma pengelompokan EM yang lebih rumit meskipun memiliki beberapa prinsip yang sama.

Pengelompokan EM

Jadi, dengan pengelompokan K-Means, setiap titik ditugaskan ke hanya satu cluster, dan sebuah cluster hanya dijelaskan oleh centroid-nya. Ini tidak terlalu fleksibel, karena kita mungkin memiliki masalah dengan cluster yang tumpang tindih, atau yang tidak berbentuk lingkaran. Dengan EM Clustering, sekarang kita dapat melangkah lebih jauh dan mendeskripsikan setiap cluster berdasarkan centroid (mean), kovariansnya (sehingga kita dapat memiliki cluster elips), dan weight (ukuran cluster). Probabilitas bahwa suatu titik milik sebuah cluster sekarang diberikan oleh distribusi probabilitas Gaussian multivariat (multivariat - tergantung pada beberapa variabel). Itu juga berarti bahwa kita dapat menghitung probabilitas sebuah titik berada di bawah 'lonceng' Gaussian, yaitu probabilitas sebuah titik milik sebuah cluster.

Kami sekarang memulai prosedur EM dengan menghitung, untuk setiap titik, probabilitasnya menjadi milik masing-masing cluster saat ini (yang, sekali lagi, dapat dibuat secara acak di awal). Ini adalah E-langkah. Jika satu cluster adalah kandidat yang sangat baik untuk suatu titik, itu akan memiliki probabilitas mendekati satu. Namun, dua atau lebih cluster dapat menjadi kandidat yang dapat diterima, sehingga titik memiliki distribusi probabilitas di atas cluster. Properti dari algoritma ini, dari titik-titik yang tidak terbatas pada satu cluster disebut "soft clustering".

Langkah-M sekarang menghitung ulang parameter setiap klaster, menggunakan penetapan titik ke kumpulan klaster sebelumnya. Untuk menghitung mean, kovarians, dan bobot baru dari sebuah cluster, setiap data titik dibobot dengan probabilitasnya untuk menjadi bagian dari cluster, seperti yang dihitung pada langkah sebelumnya.

Mengganti dua langkah ini akan meningkatkan total kemungkinan log hingga konvergen. Sekali lagi, maksimum mungkin lokal, sehingga kami dapat menjalankan algoritma beberapa kali untuk mendapatkan cluster yang lebih baik.

Jika sekarang kita ingin menentukan satu cluster untuk setiap titik, kita cukup memilih yang paling mungkin. Memiliki model probabilitas, kita juga dapat menggunakannya untuk menghasilkan data yang serupa, yaitu mengambil sampel lebih banyak titik yang mirip dengan data yang kita amati.

Propagasi Afinitas

Affinity Propagation (AP) diterbitkan oleh Frey dan Dueck pada tahun 2007, dan semakin populer karena kesederhanaan, penerapan umum, dan kinerjanya. Ini mengubah statusnya dari state of the art menjadi standar de facto.

Kelemahan utama K-Means dan algoritma serupa adalah harus memilih jumlah cluster, dan memilih set poin awal. Propagasi Afinitas, sebaliknya, mengambil langkah-langkah input kesamaan antara pasangan titik data, dan secara bersamaan menganggap semua titik data sebagai contoh potensial. Pesan bernilai nyata dipertukarkan antara titik data hingga kumpulan eksemplar berkualitas tinggi dan klaster yang sesuai secara bertahap muncul.

Sebagai masukan, algoritme mengharuskan kami untuk menyediakan dua set data:

1. Kesamaan antar titik data, merepresentasikan seberapa cocok suatu titik menjadi percontohan bagi yang lain. Jika tidak ada kesamaan antara dua titik, karena mereka tidak dapat berada di cluster yang sama, kesamaan ini dapat dihilangkan atau diatur ke -Infinity tergantung pada implementasi.

2. Preferensi, mewakili kesesuaian setiap titik data untuk dijadikan contoh. Kami mungkin memiliki beberapa informasi apriori poin mana yang dapat disukai untuk peran ini, sehingga kami dapat mewakilinya melalui preferensi.

Baik kesamaan maupun preferensi sering direpresentasikan melalui matriks tunggal, di mana nilai-nilai pada diagonal utama mewakili preferensi. Representasi matriks bagus untuk kumpulan data yang padat. Jika hubungan antar titik jarang, lebih praktis untuk tidak menyimpan seluruh matriks nxn dalam memori, tetapi menyimpan daftar kesamaan dengan titik yang terhubung. Di balik layar, 'bertukar pesan antar titik' sama saja dengan memanipulasi matriks, dan itu hanya masalah perspektif dan implementasi.

Algoritma kemudian berjalan melalui sejumlah iterasi, sampai konvergen. Setiap iterasi memiliki dua langkah penyampaian pesan:

1. Menghitung tanggung jawab: Tanggung jawab r(i, k) mencerminkan akumulasi bukti tentang seberapa cocok poin k untuk dijadikan sebagai contoh untuk poin i, dengan mempertimbangkan potensi contoh lain untuk poin i. Tanggung jawab dikirim dari titik data i ke calon contoh titik k.

2. Menghitung ketersediaan: Ketersediaan a(i, k) mencerminkan akumulasi bukti seberapa tepat titik i memilih titik k sebagai contoh, dengan mempertimbangkan dukungan dari titik lain bahwa titik k harus menjadi contoh. Ketersediaan dikirim dari calon eksemplar titik k ke titik i.

Untuk menghitung tanggung jawab, algoritme menggunakan kesamaan asli dan ketersediaan yang dihitung pada iterasi sebelumnya (awalnya, semua ketersediaan disetel ke nol). Tanggung jawab ditetapkan pada kesamaan input antara titik i dan titik k sebagai contoh, dikurangi jumlah kesamaan dan ketersediaan terbesar antara titik i dan calon contoh lainnya. Logika di balik menghitung seberapa cocok suatu poin untuk sebuah contoh adalah bahwa poin itu lebih disukai jika preferensi apriori awal lebih tinggi, tetapi tanggung jawab menjadi lebih rendah ketika ada poin serupa yang menganggap dirinya kandidat yang baik, jadi ada ' kompetisi' antara keduanya sampai satu diputuskan dalam beberapa iterasi.

Menghitung ketersediaan, kemudian, menggunakan tanggung jawab yang diperhitungkan sebagai bukti apakah setiap kandidat akan menjadi teladan yang baik. Ketersediaan a(i, k) diatur ke tanggung jawab sendiri r(k, k) ditambah jumlah tanggung jawab positif yang diterima kandidat contoh k dari poin lain.

Akhirnya, kita dapat memiliki kriteria penghentian yang berbeda untuk menghentikan prosedur, seperti ketika perubahan nilai turun di bawah beberapa ambang batas, atau jumlah maksimum iterasi tercapai. Pada setiap titik melalui prosedur Affinity Propagation, penjumlahan matriks Responsibility (r) dan Availability (a) memberi kita informasi pengelompokan yang kita butuhkan: untuk titik i, k dengan maksimum r(i, k) + a(i, k) mewakili titik saya teladan. Atau, jika kita hanya membutuhkan himpunan eksemplar, kita dapat memindai diagonal utama. Jika r(i, i) + a(i, i) > 0, titik i adalah contoh.

Kami telah melihat bahwa dengan K-Means dan algoritme serupa, menentukan jumlah klaster bisa jadi rumit. Dengan AP, kita tidak perlu secara eksplisit menentukannya, tetapi mungkin masih memerlukan beberapa penyetelan jika kita mendapatkan cluster yang lebih banyak atau lebih sedikit daripada yang mungkin kita anggap optimal. Untungnya, hanya dengan menyesuaikan preferensi kita bisa menurunkan atau menaikkan jumlah cluster. Menetapkan preferensi ke nilai yang lebih tinggi akan menghasilkan lebih banyak kelompok, karena setiap titik 'lebih pasti' dari kesesuaiannya untuk menjadi contoh dan oleh karena itu lebih sulit untuk 'mengalahkan' dan memasukkannya ke dalam 'dominasi' titik lain. Sebaliknya, pengaturan preferensi yang lebih rendah akan menghasilkan lebih sedikit cluster; seolah-olah mereka mengatakan "tidak, tidak, tolong, Anda adalah contoh yang lebih baik, saya akan bergabung dengan kelompok Anda". Sebagai aturan umum, kami dapat mengatur semua preferensi ke kesamaan median untuk jumlah cluster sedang hingga besar, atau ke kesamaan terendah untuk jumlah cluster sedang. Namun, beberapa putaran dengan preferensi penyesuaian mungkin diperlukan untuk mendapatkan hasil yang benar-benar sesuai dengan kebutuhan kita.

Propagasi Afinitas Hierarki juga layak disebut, sebagai varian dari algoritma yang menangani kompleksitas kuadrat dengan membagi kumpulan data menjadi beberapa himpunan bagian, mengelompokkannya secara terpisah, dan kemudian melakukan pengelompokan tingkat kedua.

Pada akhirnya…

Ada berbagai macam algoritma pengelompokan, masing-masing dengan pro dan kontra mengenai jenis data yang mereka gunakan, kompleksitas waktu, kelemahan, dan sebagainya. Untuk menyebutkan lebih banyak algoritma, misalnya ada Hierarchical Agglomerative Clustering (atau Linkage Clustering), bagus untuk saat kita tidak harus memiliki cluster melingkar (atau hyper-spherical), dan tidak tahu jumlah cluster sebelumnya. Dimulai dengan setiap titik menjadi cluster yang terpisah, dan bekerja dengan menggabungkan dua cluster terdekat di setiap langkah hingga semuanya berada dalam satu cluster besar.

Dengan Hierarchical Agglomerative Clustering, kita dapat dengan mudah menentukan jumlah cluster setelahnya dengan memotong dendrogram (diagram pohon) secara horizontal dimana kita anggap cocok. Ini juga dapat diulang (selalu memberikan jawaban yang sama untuk kumpulan data yang sama), tetapi juga memiliki kompleksitas yang lebih tinggi (kuadrat).

Kemudian, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) juga merupakan algoritma yang layak disebut. Ini mengelompokkan titik-titik yang saling berdekatan, memperluas klaster ke segala arah di mana ada titik terdekat, sehingga berurusan dengan berbagai bentuk klaster.

Algoritme ini layak mendapatkan artikelnya sendiri, dan kami dapat menjelajahinya di pos terpisah nanti.

Dibutuhkan pengalaman dengan beberapa percobaan dan kesalahan untuk mengetahui kapan harus menggunakan satu algoritma atau yang lain. Untungnya, kami memiliki berbagai implementasi dalam bahasa pemrograman yang berbeda, jadi mencobanya hanya membutuhkan sedikit kemauan untuk bermain.