📚Dasar Teori
Last updated
Last updated
1. K-Means Clusterring
Clustering, juga dikenal sebagai analisis cluster, adalah salah satu algoritma pembelajaran mesin yang digunakan untuk mengidentifikasi objek di dalam koleksi data atau koleksi lain yang memiliki objek serupa di dalamnya tetapi berbeda dengan objek di koleksi lain. Berdasarkan proses pengelompokan data, ada dua jenis metode pengelompokan: partisi dan hierarkis. Partisi (pengelompokan datar) adalah metode yang paling mudah dan tahan lama untuk mengelompokkan data tanpa menggunakan struktur organisasi yang kompleks (Lee, Luo dan Sang, 2021). Metode partisi yang lebih populer dan sering digunakan adalah K-Means. Sebaliknya, pengelompokan hierarkis menghasilkan struktur keluaran klaster hierarkis. Metode yang paling umum menggunakan pengelompokan hierarkis pada data teks adalah pendekatan aglomeratif algoritmik.
Sistem rekomendasi terkadang menggunakan pengelompokan untuk menemukan item atau media lain yang akan menarik bagi konsumen. Contoh penerapan clustering antara lain adalah,
a. Menemukan segmentasi nasabah berdasarkan transaksi yang dilakukan.
b. Dalam biologi, pengelompokan digunakan untuk mengidentifikasi kumpulan gen dengan pola ekspresi yang sebanding.
c. Mengaitkan pengguna di jejaring sosial berdasarkan kesamaan komunitas atau sastra.
Salah satu metode unsupervised learning yang digunakan untuk masalah clustering adalah K-means. Pembelajaran tanpa pengawasan menggunakan kumpulan data dengan label atau kelas yang tidak diketahui. Metode pembelajaran tanpa pengawasan akan menambang kumpulan data yang tidak berlabel untuk pola data tersembunyi. Tujuan pembelajaran tanpa pengawasan adalah untuk menemukan pola data berdasarkan seberapa mirip data tersebut. Gambar 7.1 menunjukkan ilustrasi Klater menggunakan algoritma K-Means.
Simbol K pada K-means clustering menandakan jumlah kluster yang digunakan. Kluster mengacu pada kumpulan titik data yang dikumpulkan bersama karena kesamaan tertentu. Jika K = 2, maka akan ada 2 kluster, dan jika K = 3 maka terdapat 3 kluster, begitu seterusnya.
Algoritma K-means mengambil dataset yang tidak berlabel sebagai input, kemudian membagi dataset menjadi sejumlah k cluster, dan mengulangi proses tersebut sampai tidak menemukan cluster terbaik. Nilai k harus ditentukan sebelumnya dalam algoritma ini.
Algoritma k-means clustering melakukan dua tugas utama, yakni:
Menentukan nilai terbaik untuk titik pusat K atau centroid dengan proses iteratif (perulangan).
Menetapkan setiap titik data ke pusat k terdekat. Titik-titik data yang dekat dengan pusat-k tertentu, kemudian dibuatkan sebuah kluster
Oleh karena itu setiap cluster memiliki titik data dengan beberapa kesamaan, dan cukup jauh dari cluster lainnya. Gambar 7.2 menunjukkan ilustrasi cara kerja Algoritma Clustering K-means
Centroid cluster digunakan untuk mewakili cluster dalam teknik partisi K-means, yang pertama kali diusulkan oleh MacQueen pada tahun 1967. Karena kecepatan dan skalabilitasnya, algoritma clustering K-means adalah algoritma clustering yang umum. Saat menggunakan K-means, centroid awal dipilih secara acak dari sekumpulan 𝑘𝑘 centroid. Hyperparameter 𝑘𝑘, yang harus berupa bilangan bulat positif kurang dari jumlah instance (atau titik data dalam kumpulan data), mendefinisikan berapa banyak cluster yang harus dihasilkan. Terkadang, konteks masalah clustering mempengaruhi jumlah cluster.
Setelah itu dicari centroid dengan cara merata-ratakan titik-titik data yang ditunjuk sebagai anggota cluster. Langkah awal adalah memilih jumlah 𝑘𝑘 centroid berdasarkan cluster yang akan dibuat. Selain itu, akan ditentukan seberapa dekat data tambahan ke centroid menyerupai centroid. Algoritma K- Means kemudian memilih data dengan kemiripan terbaik antara dokumen centroid dan non-centroid untuk menentukan anggota cluster. Selain itu, centroid baru untuk setiap cluster ditentukan dengan rata-rata anggota cluster. Ketika tidak ada lagi perubahan anggota cluster, iterasi berlanjut.
Euclidean distance merupakan salah satu cara untuk menghitung jarak pada algoritma K-Means. Perhitungan jarak dapat dimodifikasi agar sesuai dengan situasi. Komputasi kesamaan kosinus dapat digunakan saat melakukan pengelompokan dokumen. Menemukan nilai 𝑘𝑘 yang ideal, atau jumlah cluster di mana data dapat dikategorikan secara efektif, adalah tahap kunci dalam algoritme
Dalam teknik siku, grafik antara nilai 𝑘𝑘 dan fungsi biaya dibuat dengan membuat grafik nilai fungsi biaya yang dihasilkan oleh berbagai nilai 𝑘𝑘. Grafik metode siku menunjukkan bahwa ketika 𝑘𝑘 meningkat, nilai fungsi biaya menurun dan setiap instance semakin dekat ke pusat massa yang sesuai.
Perhatikan Gambar 8.1. Jumlah cluster yang ideal menurut Gambar 8.1 adalah 𝑘𝑘 = 3. Namun, karena data di dunia nyata mungkin tidak selalu dapat diakses dalam kelompok data, hanya dengan melihat data mungkin tidak selalu memberikan hasil yang optimal.
2. Self-Organizing Map (SOM)
Self-Organizing Map (SOM) atau sering disebut topology-preserving map pertama kali diperkenalkan oleh Teuvo Kohonen pada tahun 1996. SOM merupakan salah satu teknik dalam Neural Network yang bertujuan untuk melakukan visualisasi data dengan cara mengurangi dimensi data melalui penggunaan self-organizing neural networks sehingga manusia dapat mengerti high-dimensional data yang dipetakan dalam bentuk low-dimensional data. Metode pembelajaran yang digunakan SOM adalah tanpa bimbingan dari suatu data input-target atau unsupervised learning yang mengasumsikan sebuah topologi yang terstruktur menjadian unit-unit kelas/cluster (Kohonen, 1989 dan Fausett, 1993).
Pada algoritma SOM, vektor bobot untuk setiap unit cluster berfungsi sebagai contoh dari input pola yang terkait dengan cluster itu. Selama proses self-organizing, cluster satuan yang bobotnya sesuai dengan pola vektor input yang paling dekat (biasanya, kuadrat dari jarak Euclidean minimum) dipilih sebagai pemenang. Unit pemenang dan unit tetangganya (dalam pengertian topologi dari unit cluster ) terus memperbarui bobot merek (Fausett, 1993). Setiap output akan bereaksi terhadap pola input tertentu sehingga hasil Kohonen SOM akan menunjukkan adanya kesamaan ciri antar anggota dalam cluster yang sama.
Dalam jaringan SOM, neuron target tidak diletakkan dalam sebuah baris seperti layaknya model JST yang lain. Neuron target diletakkan dalam dua dimensi yang bentuk/topologinya dapat diatur. Topologi yang berbeda akan menghasilkan neuron sekitar neuron pemenang yang berbeda sehingga bobot yang dihaslkan juga akan berbeda. Pada SOM, perubahan bobot tidak hanya dilakukan pada bobot garis yang terhubung ke neuron pemenang saja, tetapi juga pada bobot garis ke neuron-neuron di sekitarnya. neuron di sekitar neuron pemenang ditentukan berdasarkan jaraknya dari neuron pemenang.
Arsitektur SOM merupakan jaringan yang terdiri dari dua lapisan (layer), yaitu lapisan input dan lapisan output. Setiap neuron dalam lapisan input terhubung dengan setiap neuron pada lapisan output. Setiap neuron dalam lapisan output merepresentasikan kelas (cluster )dari input yang diberikan.
Sedangkan untuk topologi, SOM memiliki 3 jenis topologi hubungan ketetanggaan (neighborhood) yaitu linear array, rectangular dan heksagonal grid.
Topologi linear aray menunjukkan cluster unit yang tersusun secara linear. Cluster unit yang menjadi pemenang [#] memiliki dua unit tetangga (neighbour) yang berjarak 1 (R = 1), dan mempunyai dua unit tetangga yang berjarak 2 (R = 2).
Rectangular grid adalah topologi dari cluster unit dua dimensi. Unit tetangga (neighbour) dari unit pemenang membentuk bujur sangkar. Unit pemenang [#] memiliki 8 neighbour berjarak 1 (R=1) dan 16 neighbour berjarak 2 (R=2).
Dalam topologi heksagonal grid, unit tetangga (neighbour) yang berjarak 1 (R=1) dari unit pemenang adalah 6 dan yang berjarak 2 (R=2) adalah 12.
Cara kerja SOM
Secara umum, cara kerja SOM ditunjukkan oleh Gambar 7.8 dibawah ini:
Terdapat titik (x) pada ruang input untuk dipetakan ke titik I(x) pada ruang output. Setiap titik (I) dalam ruang output akan memetakan ke titik yang sesuai dalam ruang input melalui bobot wI(x).
Menurut Haykin (1999) terdapat tiga komponen penting dalam SOM yaitu:
1. Competition: Untuk setiap pola input, neuron menghitung nilai masing-masing fungsi diskriminan yang memberi dasar untuk kompetisi. Neuron tertentu dengan nilai terkecil dari fungsi diskriminan dinyatakan sebagai pemenang.
2. Cooperation: Neuron pemenang menentukan lokasi spasial dari lingkungan topologi excited neuron untuk memberi dasar kerjasama dalam suatu lingkungan neuron.
3. Synaptic Adaption: Excited neuron menurunkan nilai fungsi diskriminan yang berkaitan dengan pola input melalui penyesuaian bobot terkait sehingga respon dari neuron pemenang keaplikasi berikutnya dengan pola input yang sama akan meningkat.
Pustaka
Fausett. L.V (1993). Fundamental of Neural Network: Architectures, Algorithm, And Application. Prentice Hall, 1st edition. ISBN-13: 978-0133341867.
Haykin, S. (1999). Neural Networks: A Comprehensive Foundation. England: Pearson Education. Hal. 23, 43-45.
Kohonen, T (1989). “Self-organizing feature maps.” Self-organization and associative memory. Springer Berlin Heidelberg. 119-157.
Kohonen, T.,Schroeder, M. R and Huang, T (2001)Self-organizing map. Springer-Verlag New York. Inc., Secaucus, NJ, 43, 2.
K-Means. Metode Siku (elbow method) adalah teknik yang populer untuk menentukan nilai 𝑘𝑘 yang ideal. Nilai fungsi biaya (cost function) diplot menggunakan berbagai nilai 𝑘𝑘 pada teknik siku. Sum of Square Error dapat dimanfaatkan sebagai salah satu fungsi biaya.
