Bagaimana K-Means Clustering Bekerja - Amazon SageMaker
Langkah 1: Tentukan Pusat Cluster AwalLangkah 2: Ulangi Dataset Pelatihan dan Hitung Pusat ClusterLangkah 3: Kurangi Cluster dari K ke K

Terjemahan disediakan oleh mesin penerjemah. Jika konten terjemahan yang diberikan bertentangan dengan versi bahasa Inggris aslinya, utamakan versi bahasa Inggris.

Bagaimana K-Means Clustering Bekerja

K-means adalah algoritma yang melatih model yang mengelompokkan objek serupa bersama-sama. Algoritma k-mean menyelesaikan ini dengan memetakan setiap pengamatan dalam dataset input ke suatu titik di ruang n -dimensi (di mana n adalah jumlah atribut pengamatan). Misalnya, kumpulan data Anda mungkin berisi pengamatan suhu dan kelembaban di lokasi tertentu, yang dipetakan ke titik (t, h) dalam ruang 2 dimensi.

catatan

Algoritma pengelompokan tidak diawasi. Dalam pembelajaran tanpa pengawasan, label yang mungkin terkait dengan objek dalam kumpulan data pelatihan tidak digunakan. Untuk informasi selengkapnya, lihat Pembelajaran tanpa pengawasan.

Dalam k-means clustering, setiap cluster memiliki pusat. Selama pelatihan model, algoritma k-mean menggunakan jarak titik yang sesuai dengan setiap pengamatan dalam kumpulan data ke pusat cluster sebagai dasar pengelompokan. Anda memilih jumlah cluster (k) untuk membuat.

Misalnya, Anda ingin membuat model untuk mengenali digit tulisan tangan dan Anda memilih kumpulan data MNIST untuk pelatihan. Dataset menyediakan ribuan gambar digit tulisan tangan (0 hingga 9). Dalam contoh ini, Anda dapat memilih untuk membuat 10 cluster, satu untuk setiap digit (0, 1,..., 9). Sebagai bagian dari pelatihan model, algoritma k-means mengelompokkan gambar input ke dalam 10 cluster.

Setiap gambar dalam dataset MNIST adalah gambar 28x28-piksel, dengan total 784 piksel. Setiap gambar sesuai dengan titik dalam ruang 784 dimensi, mirip dengan titik dalam ruang 2 dimensi (x, y). Untuk menemukan kluster di mana suatu titik berada, algoritma k-means menemukan jarak titik itu dari semua pusat cluster. Kemudian memilih cluster dengan pusat terdekat sebagai cluster tempat gambar berada.

catatan

Amazon SageMaker menggunakan versi algoritma yang disesuaikan di mana, alih-alih menentukan bahwa algoritme membuat kluster k, Anda dapat memilih untuk meningkatkan akurasi model dengan menentukan pusat cluster tambahan (K = k*x). Namun, algoritma pada akhirnya mengurangi ini menjadi kluster k.

Di SageMaker, Anda menentukan jumlah cluster saat membuat pekerjaan pelatihan. Untuk informasi selengkapnya, lihat CreateTrainingJob. Di badan permintaan, Anda menambahkan peta HyperParameters string untuk menentukan k dan extra_center_factor string.

Berikut ini adalah ringkasan cara kerja k-means untuk pelatihan model di SageMaker:

  1. Ini menentukan pusat cluster K awal.

    catatan

    Dalam topik berikut, kluster K mengacu pada k* x, di mana Anda menentukan k dan x saat membuat pekerjaan pelatihan model.

  2. Ini mengulangi data pelatihan input dan menghitung ulang pusat cluster.

  3. Ini mengurangi cluster yang dihasilkan menjadi k (jika ilmuwan data menentukan pembuatan k*x cluster dalam permintaan).

Bagian berikut juga menjelaskan beberapa parameter yang mungkin ditentukan oleh ilmuwan data untuk mengonfigurasi pekerjaan pelatihan model sebagai bagian dari peta HyperParameters string.

Langkah 1: Tentukan Pusat Cluster Awal

Saat menggunakan k-mean in SageMaker, pusat cluster awal dipilih dari pengamatan dalam batch kecil sampel acak. Pilih salah satu strategi berikut untuk menentukan bagaimana pusat klaster awal ini dipilih:

  • Pendekatan acak—Pilih pengamatan K secara acak dalam kumpulan data input Anda sebagai pusat cluster. Misalnya, Anda dapat memilih pusat cluster yang menunjuk ke ruang 784 dimensi yang sesuai dengan 10 gambar dalam kumpulan data pelatihan MNIST.

  • Pendekatan k-means++, yang berfungsi sebagai berikut:

    1. Mulailah dengan satu cluster dan tentukan pusatnya. Anda secara acak memilih observasi dari dataset pelatihan Anda dan menggunakan titik yang sesuai dengan pengamatan sebagai pusat cluster. Misalnya, dalam kumpulan data MNIST, pilih gambar digit tulisan tangan secara acak. Kemudian pilih titik dalam ruang 784 dimensi yang sesuai dengan gambar sebagai pusat cluster Anda. Ini adalah cluster center 1.

    2. Tentukan pusat untuk cluster 2. Dari pengamatan yang tersisa dalam dataset pelatihan, pilih pengamatan secara acak. Pilih salah satu yang berbeda dari yang Anda pilih sebelumnya. Pengamatan ini sesuai dengan titik yang jauh dari pusat cluster 1. Menggunakan dataset MNIST sebagai contoh, Anda melakukan hal berikut:

      • Untuk setiap gambar yang tersisa, cari jarak titik yang sesuai dari pusat cluster 1. Kuadratkan jarak dan tetapkan probabilitas yang sebanding dengan kuadrat jarak. Dengan begitu, gambar yang berbeda dari yang Anda pilih sebelumnya memiliki probabilitas lebih tinggi untuk dipilih sebagai pusat cluster 2.

      • Pilih salah satu gambar secara acak, berdasarkan probabilitas yang ditetapkan pada langkah sebelumnya. Titik yang sesuai dengan gambar adalah pusat cluster 2.

    3. Ulangi Langkah 2 untuk menemukan pusat cluster 3. Kali ini, cari jarak gambar yang tersisa dari pusat cluster 2.

    4. Ulangi proses ini sampai Anda memiliki pusat cluster K.

Untuk melatih model SageMaker, Anda membuat pekerjaan pelatihan. Dalam permintaan, Anda memberikan informasi konfigurasi dengan menentukan peta HyperParameters string berikut:

  • Untuk menentukan jumlah cluster yang akan dibuat, tambahkan k string.

  • Untuk akurasi yang lebih besar, tambahkan extra_center_factor string opsional.

  • Untuk menentukan strategi yang ingin Anda gunakan untuk menentukan pusat cluster awal, tambahkan init_method string dan atur nilainya ke random atauk-means++.

Untuk informasi selengkapnya tentang estimator SageMaker k-means, lihat K-means dalam dokumentasi Amazon Python SageMaker SDK.

Anda sekarang memiliki satu set awal pusat cluster.

Langkah 2: Ulangi Dataset Pelatihan dan Hitung Pusat Cluster

Pusat cluster yang Anda buat pada langkah sebelumnya sebagian besar acak, dengan beberapa pertimbangan untuk dataset pelatihan. Pada langkah ini, Anda menggunakan kumpulan data pelatihan untuk memindahkan pusat-pusat ini menuju pusat cluster yang sebenarnya. Algoritma mengulangi dataset pelatihan, dan menghitung ulang pusat cluster K.

  1. Baca sejumlah kecil pengamatan (subset kecil yang dipilih secara acak dari semua catatan) dari kumpulan data pelatihan dan lakukan hal berikut.

    catatan

    Saat membuat pekerjaan pelatihan model, Anda menentukan ukuran batch dalam mini_batch_size string di peta HyperParameters string.

    1. Tetapkan semua pengamatan dalam batch mini ke salah satu cluster dengan pusat cluster terdekat.

    2. Hitung jumlah pengamatan yang ditugaskan untuk setiap cluster. Kemudian, hitung proporsi poin baru yang ditetapkan per cluster.

      Misalnya, pertimbangkan cluster berikut:

      Cluster c1 = 100 poin yang ditetapkan sebelumnya. Anda menambahkan 25 poin dari mini-batch di langkah ini.

      Cluster c2 = 150 poin yang ditetapkan sebelumnya. Anda menambahkan 40 poin dari mini-batch di langkah ini.

      Cluster c3 = 450 poin yang ditetapkan sebelumnya. Anda menambahkan 5 poin dari mini-batch di langkah ini.

      Hitung proporsi poin baru yang ditetapkan untuk masing-masing cluster sebagai berikut:

      p1 = proportion of points assigned to c1 = 25/(100+25)
p2 = proportion of points assigned to c2 = 40/(150+40)
p3 = proportion of points assigned to c3 = 5/(450+5)

    3. Hitung pusat poin baru yang ditambahkan ke setiap cluster:

      d1 = center of the new points added to cluster 1
d2 = center of the new points added to cluster 2
d3 = center of the new points added to cluster 3

    4. Hitung rata-rata tertimbang untuk menemukan pusat cluster yang diperbarui sebagai berikut:

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1)
Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2)
Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)

  2. Baca mini-batch berikutnya, dan ulangi Langkah 1 untuk menghitung ulang pusat cluster.

  3. Untuk informasi lebih lanjut tentang mini-batch k -means, lihat Pengelompokan k-means skala Web).

Langkah 3: Kurangi Cluster dari K ke K

Jika algoritma membuat kluster K — (K = k*x) di mana x lebih besar dari 1—maka itu mengurangi kluster K menjadi kluster k. (Untuk informasi lebih lanjut, lihat extra_center_factor pada diskusi sebelumnya.) Ini dilakukan dengan menerapkan metode Lloyd dengan kmeans++ inisialisasi ke pusat cluster K. Untuk informasi lebih lanjut tentang metode Lloyd, lihat k-means clustering.