Set data machine learning dapat memiliki jutaan contoh, tetapi tidak semua algoritma pengklasteran dapat diskalakan secara efisien. Banyak pengelompokan algoritma ini menghitung kesamaan antara semua pasangan contoh, berarti runtime-nya akan meningkat seiring dengan kuadrat jumlah contoh \(n\), dilambangkan sebagai \(O(n^2)\) dalam notasi kompleksitas. \(O(n^2)\) algoritma tidak praktis untuk kumpulan data dengan jutaan contoh.
Algoritma k-means memiliki kompleksitas \(O(n)\), yang berarti bahwa algoritma diskalakan secara linear dengan \(n\). Algoritma ini akan menjadi fokus dalam materi ini.
Jenis-jenis clustering
Untuk daftar lengkap berbagai pendekatan pengklasteran, lihat Survei Komprehensif Algoritma Pengelompokan Xu, D. & Tian, Y. An. Data. Sains (2015) 2: 165. Setiap pendekatan paling cocok untuk distribusi data tertentu. Materi ini secara singkat membahas empat pendekatan.
Pengelompokan berbasis sentroid
Senroid cluster adalah rata-rata aritmatika dari semua titik dalam . Pengelompokkan berbasis pusat mengatur data ke dalam data non-hierarki klaster. Algoritma pengklasteran berbasis sentroid efisien tetapi sensitif terhadap kondisi awal dan pencilan. Dari jumlah tersebut, k-means adalah banyak digunakan. Ini mengharuskan pengguna untuk menentukan jumlah sentroid, k, dan bekerja baik dengan kelompok yang berukuran kira-kira sama.
Pengelompokan berbasis kepadatan
Pengelompokan berbasis kepadatan menghubungkan area berdekatan dari kepadatan contoh tinggi ke dalam klaster. Hal ini memungkinkan penemuan sejumlah cluster dengan bentuk apa pun. Pencilan tidak ditetapkan ke cluster. Algoritma ini memiliki kesulitan dengan klaster dengan kepadatan berbeda dan data dengan dimensi tinggi.
Pengelompokan berbasis distribusi
Pendekatan pengklasteran ini mengasumsikan data terdiri dari probabilistik seperti distribusi Distribusi GAussian. Di beberapa Gambar 3, algoritma berbasis distribusi mengelompokkan data ke dalam tiga Gaussian distribusi. Ketika jarak dari pusat distribusi meningkat, probabilitas bahwa suatu poin termasuk dalam distribusi akan berkurang. Pertunjukan band penurunan probabilitas tersebut. Ketika Anda tidak nyaman mengasumsikan distribusi data yang mendasarinya, Anda harus menggunakan algoritma yang berbeda.
Pengelompokan hierarkis
Pengelompokan hierarkis membuat pohon cluster. {i>Hierarchical clustering<i}, tidak heran, sangat cocok untuk data hierarkis, seperti taksonomi. Lihat Perbandingan 61 Genom Escherichia coli Urutan oleh Oksana Lukjancenko, Trudy Wassenaar & Dave Ussery sebagai contohnya. Berapa pun jumlah cluster dapat dipilih dengan menebang pohon pada tingkat yang tepat.
