Tutorial

Tutorial pemelajaran mesin: metode pengklasteran K-means

10 Mins read

Pada artikel kali ini, saya akan membahas metode pengklasteran data dengan menggunakan salah satu metode pemelajaran mesin (machine learning) yaitu K-means. Metode pengklasteran ini termasuk ke dalam paradigma pemelajaran tanpa supervisi (unsupervised learning). Tujuan dari paradigma ini adalah untuk mendapatkan gambaran dari data dengan hanya mengandalkan karakteristik intrinsik dari data tersebut, tanpa adanya suatu label atau kelas sebenarnya yang mendefinisikannya. Begitu pun dengan metode pengklasteran, kita mengharapkan mendapat suatu klaster / kelompok dari suatu data dengan melihat persebaran data tersebut.

Intuisinya adalah apabila sampel-sampel memiliki karakteristik yang sama, masing sampel-sampel tersebut akan berdekatan satu sama lain (di suatu dimensi tertentu) dan membentuk suatu kelompok / klaster. Sebaliknya, apabila terdapat sampel yang berbeda karakteristik, maka sampel yang berlainan tersebut akan berjauhan. Hal ini menjadi suatu tantangan tersendiri dikarenakan ketiadaan label atau kelas sebenarnya dari kelas tersebut.

Dataset Bunga Iris

Pada tutorial ini kita akan menggunakan data riil dari dunia nyata, yaitu dataset bunga iris sebagai data masukan untuk metode pengklasteran K-means. Dataset ini dipublikasikan pada tahun 1936 oleh Ronald Fisher di karya ilmiahnya yang berjudul “The Use of Multiple Measurements in Taxonomic Problems as an Example of Linear Discriminant Analysis. Dataset bunga iris ini terdiri dari 50 sampel pengukuran per spesies. Spesies bunga iris yang dimaksud ialah setosa, versicolor dan virginica — yang jika dilihat sekilas mirip satu sama lain(llihat ilustrasi). Kemudian, dari pengamatan beliau, panjang (length) dan lebar (width) diukur di bagian sepal dan petal dari bunga tersebut seperti pada ilustrasi berikut.

Sampel dataset bunga Iris dengan berbagai spesies yang hampir mirip satu dengan lainnya.
Sampel dataset bunga Iris dengan berbagai spesies yang hampir mirip satu sama lain. Sumber: rpub.som

Dataset ini kemudian banyak digunakan oleh para praktisi sebagai dataset sederhana dalam melatih metode machine learning untuk berbagai keperluan, misalnya klasifikasi, pengurangan dimensi (dimensionality reduction), atau pun pengklasteran yang akan kita bahas kali ini.

Pengklasteran Bunga Iris dengan Menggunakan K-means

Kita akan mencoba melakukan pengklasteran bunga iris tersebut dengan menggunakan metode pengklasteran K-means. “K” di sini mengindikasikan suatu bilangan untuk jumlah klaster yang ingin kita temukan dari suatu dataset. Sementara itu, means merujuk pada proses penghitungan titik sentra (centroid), yang dihitung menggunakan rumus rata-rata.

Terlebih dahulu kita definisikan data yang kita punyai sebagai \mathbf{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_i, \ldots, \mathbf{x}_N\} \in \mathbb{R}^{N \times D} dengan N sebagai jumlah total sampel dan D sebagai jumlah fitur.

Algoritma K-means dapat diringkas ke dalam langkah-langkah berikut:

  1. Pilih k sentra klaster (centroids) dari sampel secara acak sebagai sentra klaster awal
  2. Untuk masing-masing sampel, tentukan kelompok berdasarkan jarak terdekat ke sentra klaster yang didefinisikan sebagai \mathbf{\mu}_j dengan j \in \{1,\ldots, k\}
  3. Hitung ulang sentra klaster berdasarkan sampel-sampel yang telah dikelompokkan pada langkah 2
  4. Ulangi langkah 2-3 sampai tidak ada perubahan pada klaster (bisa dengan mendefinisikan toleransi dan atau maksimum iterasi)

Pada langkah 2 kita dapat menghitung jarak untuk mengelompokkan sampel menggunakan rumus jumlah kuadrat galat atau sum of squared errors (SSE) berdasarkan perhitungan Euclidean sebagai berikut

SSE = \sum_{i=1}^N \sum_{j=1}^k || \mathbf{x}_i – \mathbf{\mu}_j ||^2

Jadi K-means bisa dikatakan menyelesaikan permasalahan optimisasi dengan menggunakan pendekatan perulangan untuk meminimalisasi SSE atau bisa juga disebut sebagai insersia klaster (cluster inertia) .

Menyiapkan Halaman Google Colab

Pada tutorial ini, kita akan menerapkan algoritma tersebut di atas dengan menggunakan bahasa pemrograman Python. Penulisan kode ini dapat dilakukan langsung pada file *.py (kemudian dikompilasi) atau melalui halaman khusus yang memudahkan proses kompilasi dan eksekusi baris kode seperti Jupyter Notebook atau Google Colaboratory. Pada tutorial ini kita akan memanfaatkan Google Colaboratory sebagai salah satu layanan dari Google yang disediakan secara gratis.

Sebagai rujukan, kode lengkap dari tutorial ini dapat diakses dan diunduh pada tautan berikut.

Sebelumnya kita buat terlebih dulu halaman Google Colab tersebut. Agar memudahkan, saya masuk ke dalam folder Google Drive saya, kemudian saya arahkan ke folder Colab Notebooks > Clustering (folder baru yang saya buat). Kemudian untuk membuat halaman tersebut dapat menggunakan klik kanan > More > Google Colaboratory. Dengan demikian, halaman baru Google Colab akan terbuat dan siap dipakai untuk menulis kode.

Ilustrasi pembuatan halaman Google Colab.
Ilustrasi pembuatan halaman Google Colab.

Untuk menjalankan baris kode, kamu tinggal menekan ikon Play yang ada di bagian sebelah kiri blok kode tersebut atau dengan menekan tombol CTRL + ENTER (Windows, Linux) atau ⌘ + ENTER (Mac) untuk menjalankan blok; SHIFT + ENTER (untuk menjalankan blok dan berpindah ke blok selanjutnya)

Ilustrasi penulisan baris kode pada halaman Google Colab.
Ilustrasi penulisan baris kode pada halaman Google Colab.

Impor librari yang diperlukan

# Import librari yang diperlukan
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris

Pertama-tama, kita harus melakukan impor librari yang dibutuhkan pada tutorial ini yaitu numpy untuk memudahkan kita membuat array dan pencarian index pada array; matplotlib untuk memvisualisasikan data; dan sklearn untuk memuat data bunga Iris.


Memuat dataset bunga iris

# Memuat data Iris
iris = load_iris()

# Pengecekan keys dari list bernama iris
iris.keys()

Dataset bunga iris dapat kita muat hanya dengan menggunakan fungsi load_iris() yang kemudian kita tampung pada peubah iris. Setelah itu, kita lakukan pengecekan kata kunci yang terdapat pada list iris tersebut dengan meggunakan metode iris.keys(). Setelah dijalankan kita akan mendapatkan keluaran sebagai berikut.

dict_keys(['data', 'target', 'target_names', 'DESCR', 'feature_names', 'filename'])


# Pengecekan nama fitur dan label dari list tersebut
iris.feature_names, iris.target_names, 

Selain itu, kita juga dapat melakukan pengecekan fitur-fitur dan nama label yang tersedia. Keluaran dari baris kode di atas adalah sebagai berikut.

(['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)'], array(['setosa', 'versicolor', 'virginica'], dtype='<U10'))


Pengambilan fitur dari sampel

# Gunakan Petal Length dan Width sebagai fitur
X = iris.data[:,2:]
y = iris.target

# Cek dimensi dari data yang akan kita gunakan
# N: Jumlah sampel, D: Jumlah fitur
N, D = X.shape
print('N: %d, D: %d' %(N,D))

Pada tutorial ini kita akan menggunaan fitur petal length dan petal width (indeks ke-2 dan 3 pada array iris.data) yang disimpan pada peubah X. Kemudian untuk kepentingan visualisasi awal, kita juga memuat label yang tersedia pada iris.target yang disimpan pada peubah y. Supaya memudahkan, kita juga menyimpan jumlah sampel pada peubah N dan jumlah fitur pada peubah D.


Pengecekan label sebenarnya

# Cek nilai-nilai label 0: Setosa, 1: Versicolor, 2: Virginica
np.unique(y)

Walaupun sebenarnya kita tidak memerlukan label pada proses pengklasteran, tetapi karena dataset bunga iris ini tersedia label dari masing-masing spesies, kita dapat menggunakannya untuk melihat apakah hasil pengklasteran kita sesuai atau tidak dengan label aslinya (hanya sebagai pembanding). Keluaran dari baris kode di atas ialah array([0, 1, 2]), dengan 0: setosa, 1: versicolor dan 2: viriginica sesuai dengan urutan pada iris.target_names.


Normalisasi data

# Cek rentang nilai dari data
X.mean(0), X.std(0)

# Normalisasi data dengan menggunakan teknik standardization
X_norm = np.array([(X[:,i] - X[:,i].mean()) / X[:,i].std() for i in range(X.shape[1])]).T

# Cek rentang nilai dari data setelah normalisasi
X_norm.mean(0), X_norm.std(0)

Pada baris kode ke-2 di atas kita terlebih dahulu melakukan pengecekan rata-rata dan standar deviasi dari sampel yang mendapatkan keluaran sebagai berikut.

(array([5.84333333, 3.05733333]), array([0.82530129, 0.43441097]))

Data tersebut dapat dibilang bervariasi sehingga suatu model kecerdasan artifisial kemungkinan akan mengalami kesulitan untuk dilatih. Dalam berbagai praktik pelatihan metode machine learning, sering kali kita dianjurkan untuk melakukan normalisasi pada data yang kita punyai. Oleh karena itu, pada baris ke-5 kita lakukan terlebih dahulu normalisasi dengan menggunakan rumus z-score standardization sebagai berikut.

\mathbf{X}_{norm} = \frac{\mathbf{X} – \mathbf{\mu}}{\mathbf{\Sigma}}

Alhasil pada baris kode ke-8 kita mendapatkan data dengan rata-rata mendekati nol dan standard deviasi satu (unit standard deviation) sebagai berikut.

(array([-4.73695157e-16, -7.81597009e-16]), array([1., 1.]))


Visualisasi data mentah

# Tampilkan semua data tanpa melihat spesies
plt.scatter(X_norm[:,0], X_norm[:,1], c='white', marker='o', edgecolor='black', s=50)
plt.xlabel('Petal Length (Norm)')
plt.ylabel('Petal Width (Norm)')
plt.grid()
plt.show()

Selanjutnya, kita akan coba tampilkan terlebih dahulu data yang telah kita normalisasi tersebut dengan menggunakan llibrari matplotlib. Hasil dari kode tersebut ialah grafik berikut.

dataset bunga Iris ternormalisasi

Visualisasi data dengan label sebenarnya

# Tampilkan data berdasarkan spesies
plt.scatter(X_norm[:,0][np.where(y == 0)], X_norm[:,1][np.where(y == 0)], marker='s', label='Setosa')
plt.scatter(X_norm[:,0][np.where(y == 1)], X_norm[:,1][np.where(y == 1)], marker='D', label='Versicolor')
plt.scatter(X_norm[:,0][np.where(y == 2)], X_norm[:,1][np.where(y == 2)], label='Virginica')
plt.xlabel('Petal Length (Norm)')
plt.ylabel('Petal Width (Norm)')
plt.legend()
plt.grid()
plt.show()

Sebagai pembanding, kita juga tampilkan terlebih dahulu data tersebut dengan menggunakan label sebenarnya. Dengan catatatan bahwa, ini dapat kita lakukan karena tersedianya label pada dataset bunga iris ini. Akan tetapi, dalam praktiknya di lapangan dengan dataset lain, belum tentu label ini tersedia.

dataset bunga Iris dengan label yang sebenarnya

Seperti yang terlihat dari ilustrasi tersebut di atas, terdapat tiga label berdasarkan spesies bunga iris. Karena kita menggunakan fitur petal, terlihat bahwa setosa (biru) memiliki karakteristik tersendiri sehingga membentuk kelompok yang terpisah. Akan tetapi, pada beberapa sampel spesies versicolor dan virginica, karakteristik tersebut samar. Hal ini terlihat dari sampel oranye dan hijau yang hampir bercampur. Untuk memastikan, silakan lihat kembali foto ketiga spesies bunga iris di atas.


Konfigurasi parameter untuk algoritma K-means

# Tentukan random seed agar hasilnya sama setiap kali program dijalankan
np.random.seed(0)

# Tentukan beberapa parameter pelatihan
n_klaster = 3 #Jumlah kluster yang kita inginkan
max_iter = 100
toleransi = 0.001

# Secara acak, tetapkan k sampel sebagai sentra klaster
sentra = X_norm[np.random.randint(0, N, n_klaster),:]
sentra

Pada baris kode ke-2, kita tentukan terlebih dahulu random seed dari librari numpy, agar hasil pengacakannya selalu sama setiap kali program dijalankan. Selanjutnya kita masuk ke dalam inisialisasi beberapa parameter untuk algoritma K-means, yaitu n_klaster untuk menentukan jumlah klaster yang ingin dicari, max_iter untuk menentukan maksimum iterasi untuk pelatihan, dan toleransi sebagai ambang batas apakah klaster berubah dari iterasi ke iterasi. Selanjutnya kita masuk ke bagian algoritma K-means langkah pertama, yaitu inisialisasi peubah sentra secara acak dengan baris kode ke-9 di atas.


Visuasisasi titik sentra awal

# Tampilkan semua data tanpa melihat spesies
plt.scatter(X_norm[:,0], X_norm[:,1], c='white', marker='o', edgecolor='black', s=50)
for i in range(n_klaster):
  plt.scatter(sentra[i,0], sentra[i,1], color='r', marker='x', s=100)
plt.xlabel('Petal Length (Norm)')
plt.ylabel('Petal Width (Norm)')
plt.grid()
plt.show()

Sebelum menjalankan algoritma K-means, kita cek terlebih dahulu sampel yang dipilih secara acak sebagai sentra pada bagian sebelumnya. Tanda centang merah pada ilustrasi berikut menunjukkan 3 titik sentra yang terpilih.

dataset bunga Iris dengan tititk sentra

Melatih metode pengklasteran K-means secara iteratif

# Iterasi sampai batas maksimal iterasi yang telah ditentukan
for t in range(max_iter):
    # Tetapkan setiap sampel masuk ke sentra klaster terdekat
    # berdasarkan jarak sampel tersebut ke sentra klaster

    # Set inisialisasi jarak dengan nilai 0
    jarak = np.zeros((N, n_klaster))
    # Iterasi setiap untuk setiap sentra klaster
    for i, s in enumerate(sentra):
        # Hitung jarak menggunakan rumus 'Sum of Squared Difference'
        jarak[:, i] = np.sum(np.power(X_norm - s, 2),1)

    # Tentukan sentra klaster untuk masing-masing sampel berdasarkan jarak terdekat
    sentra_idx = np.argmin(jarak, 1)

    # Hitung ulang sentra klaster berdasarkan penentuan sentra klaster terbaru
    sentra_baru = np.array([np.mean(X_norm[np.where(sentra_idx==i)], 0) for i in range(n_klaster)])

    # Hitung selisih antara sentra lama dan baru
    selisih = np.abs(np.sum(sentra - sentra_baru))
    
    # Tetapkan sentra baru sebagai sentra saat ini
    sentra = sentra_baru

    # Berhenti apabila selisih sudah terlalu kecil (kurang dari toleransi)
    if selisih < toleransi:
        break

Algoritma K-means dirancang untuk dijalankan secara iteratif. Oleh karena itu, pada baris ke-2 terlebih dahulu kita buat suatu perulangan dengan kondisi max_iter sebagai suatu array perulangan. Pada baris kode ke-7 kita inisialisasi terlebih dahulu matriks jarak dengan nilai nol. Kemudian kita perlu melakukan perhitungan jarak (dengan menggunakan rumus SSE pada baris kode ke-11) masing-masing sampel terhadap 3 titik sentra yang telah kita pilih sebelumnya.

Pada tahap selanjutnya kita tentukan titik sentra mana yang paling dekat untuk setiap sampel dengan menggunakan fungsi numpy np.argmin() pada baris kode ke-14 dan menyimpannya di peubah sentra_idx. Setelah itu karena anggota klaster tersebut kemungkinan sudah berubah, kita harus menghitung ulang titik sentra dengan menggunakan rumus sederhana, yaitu rata-rata pada baris kode ke-17 dan menyimpannya di sentra_baru.

Untuk melakukan evaluasi apakah pelatihan harus terus dilanjutkan atau tidak, kita perlu menghitung selisih antara sentra dan sentra_baru pada baris ke-20. Dan kita tetapkan sentra_baru sebagi sentra saat ini untuk keperluan iterasi berikutnya.


Visualisasi hasil metode pengklasteran

# Tampilkan data berdasarkan klaster
for i in range(n_klaster):
  plt.scatter(X_norm[:,0][np.where(sentra_idx == i)], X_norm[:,1][np.where(sentra_idx == i)], label='Klaster %d' % i)
  plt.scatter(sentra[i,0], sentra[i,1], color='r', marker='x', s=100)
plt.xlabel('Petal Length (Norm)')
plt.ylabel('Petal Width (Norm)')
plt.legend()
plt.grid()
plt.show()

Dari algoritma K-means tersebut kita dapat memperoleh hasil pengklasteran seperti pada ilustrasi sebelah kiri berikut. Jika dibandingkan dengan label sebenarnya pada ilustrasi sebelah kanan, boleh dibilang metode pengklasteran K-means ini sudah bagus, walaupun tentu saja dengan beberapa galat pada bagian tengah antara versicolor dan virginica yang memang bercampur. Dapat dicatat bahwa warna pada klaster hanya sebagai pembeda (tidak mencerminkan kelas / label sebenarnya).

dataset bunga Iris dengan metode pengklasteran K-Means
dataset bunga Iris dengan metode pengklasteran K-means
dataset bunga Iris dengan label yang sebenarnya
Dataset bunga Iris dengan label yang sebenarnya

Visualisasi pengklasteran per iterasi

Agar dapat lebih memahami proses perubahan anggota klaster per iterasi, kita akan mengubah beberapa baris kode, yaitu penentuan peubah sentra.

# Tetapkan sentra di titik origin dengan menambahkan suatu nilai kecil secara acak
sentra = np.zeros((n_klaster, 2)) + (np.random.rand(n_klaster, 2) * 0.1)

Kita ubah penetapan sentra pada langkah inisialisasi yang tadinya acak menjadi berada pada titik origin dengan suatu nilai acak yang kecil. Jika ditampilkan maka ketiga titik sentra awal akan terlihat seperti berikut.

dataset bunga Iris dengan titik sentra terpusat di titik origin
# Definisi fungsi visualiasi data
def visualisasi(X, sentra_idx, sentra, n_klaster, iter):
  for i in range(n_klaster):
    plt.scatter(X[:,0][np.where(sentra_idx == i)], X[:,1][np.where(sentra_idx == i)], label='Klaster %d' % i)
    plt.scatter(sentra[i,0], sentra[i,1], color='r', marker='x', s=100)
  plt.xlabel('Petal Length (Norm)')
  plt.ylabel('Petal Width (Norm)')
  plt.title('Iterasi %d' %iter)
  plt.legend()
  plt.grid()
  plt.show()

Demi kemudahan, kita definisikan sebuah fungsi bernama visualisasi untuk menampilkan grafik klaster beserta titik sentra dengan beberapa argumen masukan diantaranya ialah data sample X, index pengelompokan sampel sentra_idx, koordinat titik sentra sentra, jumlah klaster n_klaster, dan iterasi iter.

    ....

    # Hitung selisih antara sentra lama dan baru
    selisih = np.abs(np.sum(sentra - sentra_baru))

    # Tetapkan sentra baru sebagai sentra saat ini
    sentra = sentra_baru
    
    # Visualisasi hasil pengklasteran setiap iterasi
    visualisasi(X_norm, sentra_idx, sentra, n_klaster, t)
    print('Selisih %f' % selisih)
    print('---')

    ...

Kemudian kita sisipkan pemanggilan fungsi tersebut setelah baris kode penetapan sentra_baru sebagai sentra saat ini. Sebagai tambahan, kita juga menampilkan nilai selisih.

Dari visualisasi berikut terlihat bahwa tiap iterasi anggota klaster berubah mendekati suatu kesetimbangan sampai akhirnya tidak ada lagi perubahan (tidak ada selisih) pada iterasi ke-5 (dihitung dari 0).

dataset bunga Iris dengan metode pengklasteran K-Means pada iterasi 0
dataset bunga Iris dengan metode pengklasteran K-Means pada iterasi 1
dataset bunga Iris dengan metode pengklasteran K-Means pada iterasi 4

Bagaimana menentukan jumlah klaster?

Pada algoritma K-means, kita diharuskan menentukan berapa jumlah klaster yang ingin dicari. Yang menjadi pokok pertanyaan ialah bagaimana cara kita menentukan jumlah klaster dari suatu data? Untuk itu, kita dapat mencoba menjalankan algoritma K-Means dengan beberapa kali percobaan berdasarkan pada jumlah klaster. Kemudian dengan menghitung SSE sebagai insersia klaster untuk seluruh sampel, kita dapat memilih berapa jumlah klaster yang optimal berdasarkan metode siku (elbow method) seperti pada ilustrasi berikut.

grafik metode pengklasteran K-Means berdasarkan jumlah klaster

Dari grafik di atas, terlihat bahwa jumlah klaster yang disarankan ialah berada pada nilai 3, yang mana ini mencerminkan jumlah label pada dataset bunga iris ini.

Materi lebih lanjut: metode K-means++

Algoritma K-means yang kita pelajari pada artikel ini memiliki kekurangan, yaitu pada tahap inisialisasi titik sentra secara acak. Jika titik sentra yang terpilih tersebut posisinya tidak bagus, hal ini memungkinkan klaster yang didapat juga tidak akan bagus / optimal dan/atau menyebabkan konvergensi yang lambat.

Salah satu solusi yang dapat kita lakukan adalah dengan menjalankan algoritma K-means tersebut beberapa kali (dengan random seed yang berbeda tentunya). Kemudian kita pilih mana yang terbaik dengan menghitung SSE sebagai insersia klaster. Selain itu, solusi lainnya ialah dengan menggunakan algoritma K-means++, yaitu dengan menginisialisasi titik sentra dengan menggunakan metode distribusi probabilitas berbobot (weighted probability distribution).

Referensi

1.
Fisher, R. A. The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics 7, 179–188 (1936).
1.
Raschka, S. & Mirjalili, V. Python machine learning: machine learning and deep learning with Python, scikit-learn, and TensorFlow. (Packt Publishing, 2019).

Jika ada pertanyaan, koreksi, ataupun ingin sekadar berdiskusi lebih lanjut, silakan gunakan kolom komentar untuk berkomunikasi dengan penulis.

About author
Mahasiswa program doktoral di Korea University, Korea Selatan dengan jurusan Brain & Cognitive Engineering | Anggota dari Machine Intelligence Lab @ Korea University | Perintis dari Konsep.AI
Articles
Related posts
Tutorial

Rekomendasi film Indonesia dengan kecerdasan artifisial

14 Mins read
Menonton film mungkin menjadi suatu hobi bagi kebanyakan dari kita. Terlepas dari selera genrenya yang berbeda-beda, tetap saja aktivitas ini membawa kegembiraan…
Daftarkan email kamu untuk mendapatkan ulasan terkini seputar teknologi kecerdasan buatan!

 

Leave a Reply

Your email address will not be published. Required fields are marked *

×
Ulasan

Mengenal Jaringan Saraf Tiruan (Neural Networks)