Halaman ini diterjemahkan oleh Cloud Translation API.

Menjalankan Algoritme Pengelompokan

Dalam machine learning, terkadang Anda menemukan set data yang dapat memiliki jutaan contoh. Algoritme ML harus diskalakan secara efisien ke set data besar ini. Namun, banyak algoritme pengelompokan tidak diskalakan karena mereka perlu menghitung kesamaan antara semua pasangan titik. Ini berarti runtime-nya meningkat sebagai kuadrat jumlah titik, yang dinyatakan sebagai $O(n^2)$. Misalnya, algoritme pengelompokan hierarkis aglomeratif atau divisi melihat semua pasangan titik dan masing-masing memiliki kompleksitas $O(n^2 log(n))$ dan $O(n^2)$.

Kursus ini berfokus pada k-average karena skalanya diskalakan sebagai $O(nk)$, dengan $k$ adalah jumlah cluster. k-berarti grup menunjuk ke dalam $k$ cluster dengan meminimalkan jarak antara titik dan cluster tersebut sentroid (seperti yang terlihat pada Gambar 1 di bawah ini). centroid cluster adalah rata-rata dari semua titik dalam cluster.

Seperti yang ditunjukkan, k-average menemukan cluster yang kira-kira melingkar. Secara konseptual, ini berarti k-memanfaatkan data secara efektif sebagai terdiri dari sejumlah distribusi yang hampir melingkar, dan mencoba menemukan cluster yang sesuai dengan distribusi ini. Pada kenyataannya, data berisi pencilan dan mungkin tidak sesuai dengan model tersebut.

Sebelum menjalankan k-intent, Anda harus memilih jumlah cluster, $k$. Awalnya, mulailah dengan tebakan untuk $k$. Nanti, kita akan membahas cara menyaring angka ini.

Algoritme Pengelompokan Cluster

Untuk mengelompokkan data menjadi $k$ cluster, k-berarti mengikuti langkah-langkah berikut:

Grafik k-intent saat inisialisasi — **Gambar 1: k-intent saat inisialisasi.**

Langkah Pertama

Algoritme secara acak memilih sentroid untuk setiap cluster. Dalam contoh, kita memilih $k$ dari 3, sehingga algoritme secara acak memilih 3 sentroid.

Langkah Kedua

Algoritme menetapkan setiap titik ke sentroid terdekat untuk mendapatkan $k$ cluster awal.

Komputasi sentroid — **Gambar 3: Perhitungan sentroid.**

Langkah Ketiga

Untuk setiap cluster, algoritme menghitung ulang sentroid dengan mengambil rata-rata dari semua titik dalam cluster. Perubahan dalam sentroid ditunjukkan pada Gambar 3 oleh panah. Karena sentroid berubah, algoritme kemudian menetapkan ulang titik ke sentroid terdekat. Gambar 4 menunjukkan cluster baru setelah penetapan ulang.

**Gambar 4: Cluster setelah penetapan ulang.**

Langkah Keempat

Algoritme mengulangi penghitungan sentroid dan penetapan titik hingga titik tersebut berhenti mengubah cluster. Saat mengelompokkan set data yang besar, Anda akan menghentikan algoritme sebelum mencapai konvergensi, menggunakan kriteria lain sebagai gantinya.

Anda tidak perlu memahami matematika di balik k-intent untuk kursus ini. Namun, jika Anda ingin tahu, lihat bukti matematika di bawah.

Klik ikon plus untuk bukti matematika

Mengingat $n$ contoh yang ditetapkan untuk $k$ cluster, minimalkan jumlah jarak contoh ke sentroidnya. Dalam hal ini:

$A_{nk} = 1$ ketika contoh $n$ditetapkan ke cluster $k$, dan 0 jika tidak
$\theta_k$ adalah sentroid cluster $k$

Kami ingin meminimalkan ekspresi berikut: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ tunduk pada: $$A_{nk} \in \{0,1\} \forall n,k$$ dan $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Untuk meminimalkan ekspresi sehubungan dengan cluster centroid $\theta_k$, ambil turunan yang terkait dengan $\theta_k$ dan samakan dengan 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Pembilang adalah jumlah dari semua jarak sentroid contoh dalam cluster. Penyebutnya adalah jumlah contoh dalam cluster. Jadi, cluster sentroid$\theta_k$ adalah rata-rata jarak yang berpusat pada contoh di cluster. Oleh karena itu, terbukti.

Karena posisi sentroid awalnya dipilih secara acak, k-intent dapat menampilkan hasil yang sangat berbeda pada urutan berturut-turut. Untuk mengatasi masalah ini, jalankan k-intent beberapa kali dan pilih hasilnya dengan metrik kualitas terbaik. (Kami akan menjelaskan metrik kualitas nanti dalam kursus ini.) Anda memerlukan k-berarti versi lanjutan untuk memilih posisi sentroid awal yang lebih baik.