Set data machine learning dapat memiliki jutaan contoh, tetapi tidak semua algoritma pengelompokan diskalakan secara efisien. Banyak algoritma pengelompokan menghitung kesamaan antara semua pasangan contoh, yang berarti runtime-nya meningkat sebagai kuadrat jumlah contoh \(n\), yang dilambangkan sebagai \(O(n^2)\) dalam notasi kompleksitas. \(O(n^2)\) Algoritma ini tidak praktis untuk set data dengan jutaan contoh.
Algoritme k-means memiliki kompleksitas \(O(n)\), yang berarti algoritme diskalakan secara linear dengan \(n\). Algoritma ini akan menjadi fokus kursus ini.
Jenis pengelompokan
Untuk mengetahui daftar lengkap berbagai pendekatan untuk pengelompokan, lihat A Comprehensive Survey of Clustering Algorithms Xu, D. & Tian, Y. Ann. Data. Sci. (2015) 2: 165. Setiap pendekatan paling cocok untuk distribusi data tertentu. Kursus ini secara singkat membahas empat pendekatan umum.
Pengelompokan berbasis sentroid
Centroid cluster adalah rata-rata aritmetika dari semua titik dalam cluster. Pengelompokan berbasis sentroid mengatur data ke dalam cluster non-hierarkis. Algoritma pengelompokan berbasis sentroid efisien, tetapi sensitif terhadap kondisi awal dan pencilan. Dari semua algoritma tersebut, k-means adalah yang paling banyak digunakan. Algoritma ini mengharuskan pengguna menentukan jumlah centroid, k, dan berfungsi dengan baik dengan cluster yang ukurannya kira-kira sama.
Pengelompokan berbasis kepadatan
Pengelompokan berbasis kepadatan menghubungkan area yang berdekatan dengan kepadatan contoh tinggi ke dalam cluster. Hal ini memungkinkan penemuan cluster dalam jumlah berapa pun dengan bentuk apa pun. Nilai ekstrem tidak ditetapkan ke cluster. Algoritma ini mengalami kesulitan dengan cluster kepadatan yang berbeda dan data dengan dimensi tinggi.
Pengelompokan berbasis distribusi
Pendekatan pengelompokan ini mengasumsikan bahwa data terdiri dari distribusi probabilistik, seperti distribusi Gaussian. Pada Gambar 3, algoritma berbasis distribusi mengelompokkan data ke dalam tiga distribusi Gaussian. Seiring meningkatnya jarak dari pusat distribusi, probabilitas bahwa suatu titik termasuk dalam distribusi akan menurun. Band menunjukkan penurunan probabilitas tersebut. Jika tidak yakin dengan asumsi distribusi data yang mendasarinya, Anda harus menggunakan algoritma yang berbeda.
Pengelompokan hierarkis
Pengelompokan hierarkis membuat hierarki cluster. Tidak mengherankan, pengelompokan hierarkis sangat cocok untuk data hierarkis, seperti taksonomi. Lihat Perbandingan 61 Genom Escherichia coli yang Diurutkan oleh Oksana Lukjancenko, Trudy Wassenaar & Dave Ussery untuk mengetahui contohnya. Jumlah cluster yang dapat dipilih dengan memotong hierarki di tingkat yang tepat.
