Algoritma K-Means Clustering


Algoritma K-Means Clustering adalah salah satu algoritma yang digunakan untuk mengelompokan data-data ke dalam 2 kelompok. Salah satunya adalah memisahkan data antara data yang layak dan data yang tidak layak, misalnya untuk menentukan lulus tidaknya siswa.

Contoh lain mengenai algoritma ini dapat dilihat di Algoritma K-Means Clustering

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data adalah sebagai berikut

Dim score(3, 3) As Double
score(0, 0) = 6
score(0, 1) = 70
score(0, 2) = 7
score(0, 3) = 60
score(1, 0) = 5
score(1, 1) = 80
score(1, 2) = 10
score(1, 3) = 80
score(2, 0) = 7
score(2, 1) = 40
score(2, 2) = 5
score(2, 3) = 60
score(3, 0) = 5
score(3, 1) = 50
score(3, 2) = 9
score(3, 3) = 30

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Kriteria Penilaian
Nilai tersebut akan dikelompokan ke dalam beberapa golongan, misalnya 3 golongan, yaitu rendah, sedang, tinggi
Maka tentukan masing-masing rentang skor untuk golongan tersebut
Contoh dalam kasus ini:
kolom 1: rendah 0-3, sedang 4-6, tinggi 7-10
kolom 2: rendah 0-30, sedang 40-60, tinggi 70-100
kolom 3: rendah 0-3, sedang 4-6, tinggi 7-10
kolom 4: rendah 0-30, sedang 40-60, tinggi 70-100

2. Konversi Skor menjadi Penilaian
Setelah menentukan kriteria penilaian, maka lakukan konversi skor tersebut.
Dalam kasus ini, rendah bernilai 33, sedang bernilai 66, dan tinggi bernilai 100

Dim konversiscore(3, 3) As Double
konversiscore(0, 0) = IIf(score(0, 0) <= 3, 33, IIf(score(0, 0) <= 6, 66, 100))
konversiscore(0, 1) = IIf(score(0, 1) <= 30, 33, IIf(score(0, 1) <= 60, 66, 100))
konversiscore(0, 2) = IIf(score(0, 2) <= 3, 33, IIf(score(0, 2) <= 6, 66, 100))
konversiscore(0, 3) = IIf(score(0, 3) <= 30, 33, IIf(score(0, 3) <= 60, 66, 100))
konversiscore(1, 0) = IIf(score(1, 0) <= 3, 33, IIf(score(1, 0) <= 6, 66, 100))
konversiscore(1, 1) = IIf(score(1, 1) <= 30, 33, IIf(score(1, 1) <= 60, 66, 100))
konversiscore(1, 2) = IIf(score(1, 2) <= 3, 33, IIf(score(1, 2) <= 6, 66, 100))
konversiscore(1, 3) = IIf(score(1, 3) <= 30, 33, IIf(score(1, 3) <= 60, 66, 100))
konversiscore(2, 0) = IIf(score(2, 0) <= 3, 33, IIf(score(2, 0) <= 6, 66, 100))
konversiscore(2, 1) = IIf(score(2, 1) <= 30, 33, IIf(score(2, 1) <= 60, 66, 100))
konversiscore(2, 2) = IIf(score(2, 2) <= 3, 33, IIf(score(2, 2) <= 6, 66, 100))
konversiscore(2, 3) = IIf(score(2, 3) <= 30, 33, IIf(score(2, 3) <= 60, 66, 100))
konversiscore(3, 0) = IIf(score(3, 0) <= 3, 33, IIf(score(3, 0) <= 6, 66, 100))
konversiscore(3, 1) = IIf(score(3, 1) <= 30, 33, IIf(score(3, 1) <= 60, 66, 100))
konversiscore(3, 2) = IIf(score(3, 2) <= 3, 33, IIf(score(3, 2) <= 6, 66, 100))
konversiscore(3, 3) = IIf(score(3, 3) <= 30, 33, IIf(score(3, 3) <= 60, 66, 100))

3. Tentukan Data Centroid
Data Centroid adalah baris data yang digunakan pada perhitungan berikutnya.
Diperlukan 2 Data Centroid pada setiap perhitungan,
Data Centroid 1 diambil dari baris pertama
Data Centroid 2 diambil dari rata-rata jumlah setiap baris data selain baris pertama

Dim DataCentroid(1, 3) As Double
DataCentroid(0, 0) = konversiscore(0, 0)
DataCentroid(0, 1) = konversiscore(0, 1)
DataCentroid(0, 2) = konversiscore(0, 2)
DataCentroid(0, 3) = konversiscore(0, 3)

DataCentroid(1, 0) = (konversiscore(1, 0) + konversiscore(2, 0) + konversiscore(3, 0)) / 3
DataCentroid(1, 1) = (konversiscore(1, 1) + konversiscore(2, 1) + konversiscore(3, 1)) / 3
DataCentroid(1, 2) = (konversiscore(1, 2) + konversiscore(2, 2) + konversiscore(3, 2)) / 3
DataCentroid(1, 3) = (konversiscore(1, 3) + konversiscore(2, 3) + konversiscore(3, 3)) / 3

4. Hitung jarak data dengan centroid euclidean
Ada 2 hasil perhitungan yang dihasilkan dari tiap-tiap baris data, karena ada 2 data Centroid dari perhitungan diatas.
Nilai 1 adalah akar dari jumlah data dari masing-masing kuadrat data baris tersebut dikurangi dengan data centroid 1
Nilai 2 adalah akar dari jumlah data dari masing-masing kuadrat data baris tersebut dikurangi dengan data centroid 2

Dim DataCentroidEuclidean(3, 1) As Double
DataCentroidEuclidean(0, 0) = Math.Sqrt(Math.Pow(konversiscore(0, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(0, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(0, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(0, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(0, 1) = Math.Sqrt(Math.Pow(konversiscore(0, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(0, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(0, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(0, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(1, 0) = Math.Sqrt(Math.Pow(konversiscore(1, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(1, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(1, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(1, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(1, 1) = Math.Sqrt(Math.Pow(konversiscore(1, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(1, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(1, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(1, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(2, 0) = Math.Sqrt(Math.Pow(konversiscore(2, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(2, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(2, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(2, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(2, 1) = Math.Sqrt(Math.Pow(konversiscore(2, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(2, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(2, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(2, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(3, 0) = Math.Sqrt(Math.Pow(konversiscore(3, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(3, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(3, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(3, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(3, 1) = Math.Sqrt(Math.Pow(konversiscore(3, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(3, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(3, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(3, 3) - DataCentroid(1, 3), 2))

5. Bandingkan hasil perhitungan centroid euclidean untuk tiap-tiap baris
Jika perhitungan nilai pertama kurang dari nilai kedua maka beri nilai baris itu dengan angka 1.
Jika perhitungan nilai pertama lebih dari nilai kedua maka beri nilai baris itu dengan angka 2.

Dim Result(3) As Double
If DataCentroidEuclidean(0, 0) < DataCentroidEuclidean(0, 1) Then Result(0) = 1 Else Result(0) = 2
If DataCentroidEuclidean(1, 0) < DataCentroidEuclidean(1, 1) Then Result(1) = 1 Else Result(1) = 2
If DataCentroidEuclidean(2, 0) < DataCentroidEuclidean(2, 1) Then Result(2) = 1 Else Result(2) = 2
If DataCentroidEuclidean(3, 0) < DataCentroidEuclidean(3, 1) Then Result(3) = 1 Else Result(3) = 2

6. Lakukan pengulangan data pada langkah 3,4,5
Untuk pada langkah ketiga, karena sekarang adalah pengulangan kedua, maka
Data Centroid 1 diambil dari n baris pertama, dimana n = 2
Data Centroid 2 diambil dari rata-rata jumlah setiap baris data selain n baris pertama

ReDim DataCentroid(1, 3)
DataCentroid(0, 0) = (konversiscore(0, 0) + konversiscore(1, 0)) / 2
DataCentroid(0, 1) = (konversiscore(0, 1) + konversiscore(1, 1)) / 2
DataCentroid(0, 2) = (konversiscore(0, 2) + konversiscore(1, 2)) / 2
DataCentroid(0, 3) = (konversiscore(0, 3) + konversiscore(1, 3)) / 2

DataCentroid(1, 0) = (konversiscore(2, 0) + konversiscore(3, 0)) / 2
DataCentroid(1, 1) = (konversiscore(2, 1) + konversiscore(3, 1)) / 2
DataCentroid(1, 2) = (konversiscore(2, 2) + konversiscore(3, 2)) / 2
DataCentroid(1, 3) = (konversiscore(2, 3) + konversiscore(3, 3)) / 2

ReDim DataCentroidEuclidean(3, 1)
DataCentroidEuclidean(0, 0) = Math.Sqrt(Math.Pow(konversiscore(0, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(0, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(0, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(0, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(0, 1) = Math.Sqrt(Math.Pow(konversiscore(0, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(0, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(0, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(0, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(1, 0) = Math.Sqrt(Math.Pow(konversiscore(1, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(1, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(1, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(1, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(1, 1) = Math.Sqrt(Math.Pow(konversiscore(1, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(1, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(1, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(1, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(2, 0) = Math.Sqrt(Math.Pow(konversiscore(2, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(2, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(2, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(2, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(2, 1) = Math.Sqrt(Math.Pow(konversiscore(2, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(2, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(2, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(2, 3) - DataCentroid(1, 3), 2))
DataCentroidEuclidean(3, 0) = Math.Sqrt(Math.Pow(konversiscore(3, 0) - DataCentroid(0, 0), 2) + Math.Pow(konversiscore(3, 1) - DataCentroid(0, 1), 2) + Math.Pow(konversiscore(3, 2) - DataCentroid(0, 2), 2) + Math.Pow(konversiscore(3, 3) - DataCentroid(0, 3), 2))
DataCentroidEuclidean(3, 1) = Math.Sqrt(Math.Pow(konversiscore(3, 0) - DataCentroid(1, 0), 2) + Math.Pow(konversiscore(3, 1) - DataCentroid(1, 1), 2) + Math.Pow(konversiscore(3, 2) - DataCentroid(1, 2), 2) + Math.Pow(konversiscore(3, 3) - DataCentroid(1, 3), 2))

ReDim Result(3)
If DataCentroidEuclidean(0, 0) < DataCentroidEuclidean(0, 1) Then Result(0) = 1 Else Result(0) = 2
If DataCentroidEuclidean(1, 0) < DataCentroidEuclidean(1, 1) Then Result(1) = 1 Else Result(1) = 2
If DataCentroidEuclidean(2, 0) < DataCentroidEuclidean(2, 1) Then Result(2) = 1 Else Result(2) = 2
If DataCentroidEuclidean(3, 0) < DataCentroidEuclidean(3, 1) Then Result(3) = 1 Else Result(3) = 2

7. Bandingkan hasil nilai pada perhitungan sebelumnya dengan perhitungan terakhir
Jika hasil nilainya sudah sama persis, maka perhitungan sudah selesai.
Jika hasil nilainya belum sama persis, maka ulangi kembali langkah 3,4,5 sebagai pengulangan ketiga.
Ulangi pengulangan sampai dengan hasil nilainya sudah sama persis atau sampai dengan perulangan ke baris data - 1
karena pada contoh ini menggunakan 4 baris data, maka pengulangan terakhir adalah pengulangan ketiga
Jika perhitungan sudah selesai, maka baris data dengan nilai hasil 1 akan dinyatakan lulus, sedangkan baris data dengan nilai hasil 2 akan dinyatakan tidak lulus

Hasil akhir adalah: (klik untuk perbesar gambar)

cmd2a


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *