Algoritma QT (Quality Threshold) Clustering

Algoritma QT (Quality Threshold) Clustering adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Contoh yang dibahas kali ini adalah mengenai penentuan penerimaan pengajuan kredit sepeda motor.
Inti perhitungan algoritma ini adalah:

• Tentukan diameter maksimal pada masing-masing cluster
• Buat calon cluster untuk masing-masing titik dengan cara menghitung secara terus menerus titik terdekat dalam sebuah grup sampai pada diameter titik terdekat sudah melebihi diameter maksimal
• Simpan calon cluster dengan titik terbanyak sebagai cluster jawaban yang pertama, dan hilangkan semua titik yang sudah termasuk dalam cluster tersebut
• Lakukan perhitungan pencarian cluster sampai semua titik sudah masuk ke dalam cluster

Diasumsikan ada 13 data pelanggan, yaitu Pelanggan A,B,C,D,E,F,G,H,I,J,K,L,M
Masing-masing pelanggan memiliki kriteria, yaitu umur, jenis kelamin, skor kepribadian
Maka tentukan kelompok data pelanggan menjadi 2 bagian, yaitu kelompok data Diterima atau Ditolak
Diasumsikan 13 data tersebut adalah sebagai berikut:

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:
Untuk Kriteria Jenis Kelamin:
Laki-laki dilambangkan dengan angka -1
Perempuan dilambangkan dengan angka +1

Dim data(12)() As Double
data(0) = New Double() {44, -1, 3.55}
data(1) = New Double() {52, +1, 4.71}
data(2) = New Double() {60, +1, 6.56}
data(3) = New Double() {56, -1, 6.8}
data(4) = New Double() {51, -1, 6.94}
data(5) = New Double() {46, +1, 6.52}
data(6) = New Double() {48, -1, 4.25}
data(7) = New Double() {58, +1, 5.71}
data(8) = New Double() {47, +1, 6.05}
data(9) = New Double() {52, -1, 5}
data(10) = New Double() {42, -1, 5.7}
data(11) = New Double() {59, -1, 3.9}
data(12) = New Double() {49, +1, 4.85}

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan diameter maksimal sebuah titik untuk membentuk area dengan radius tersebut menjadi cluster
Diasumsikan dalam kasus ini, maksimal diameter bernilai 5

Const maksDiameter As Double = 5.0

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses pengelompokan pada data awal (poin 1 – 2)

1. Lakukan proses perhitungan pada semua titik
Tentukan calon kumpulan titik terbaik untuk dimasukkan ke dalam cluster
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini

Dim daftarTitikTerbaik As List(Of Titik) = CariKumpulanTitikTerbaik(tmpDaftarTitik, maksDiameter)

Memasuki perhitungan pada fungsi CariKumpulanTitikTerbaik

1a. Pangkatkan nilai maksimal diameter sebanyak jumlah kriteria yang ada

maksDiameter = Math.Pow(maksDiameter, 3)

1b. Lakukan perulangan pada semua data titik (poin 1b1 – 1b5)

For i As Integer = 0 To daftarTitik.Count - 1
. . .

1b1. Apabila semua titik sudah tercluster maka hentikan perhitungan

If totalTitikTercluster = daftarTitik.Count Then Exit For

1b2. Apabila sebuah titik sudah dimasukkan ke dalam cluster, maka lanjutkan perhitungan ke titik berikutnya

If idxCalonDafterCluster(i) > 0 Then Continue For

1b3. buat calon cluster yang baru, kemudian masukkan titik ke dalam cluster tersebut

CalonTerpilih = New List(Of Titik)()
CalonTerpilih.Add(daftarTitik(i))

1b4. Lakukan perhitungan pada semua sisa titik pada daftar titik
Masukkan satu persatu titik dengan jarak terdekat sampai threshold terpenuhi (poin 1b4a – 1b4c)

1b4a. Apabila semua titik sudah tercluster maka hentikan perhitungan

If totalTitikTercluster = daftarTitik.Count Then Exit While

1b4b. Lakukan perulangan pada semua titik yang ada (poin 1b4b1 – 1b4b3)

For j As Integer = i + 1 To daftarTitik.Count - 1
. . .

1b4b1. Apabila sebuah titik sudah dimasukkan ke dalam cluster, maka lanjutkan perhitungan ke titik berikutnya

If idxCalonDafterCluster(j) > 0 Then Continue For

1b4b2. Hitung jarak titik sekarang dengan titik terakhir
Cari diameter terpanjang pada titik tersebut

Dim jarak As Integer = Titik.HitungJarak(titikTerakhir, daftarTitik(j))
If jarak > diameter(j) Then
	diameter(j) = jarak
End If

* Gunakan fungsi ini untuk menghitung jarak antara 2 titik
Rumus yang digunakan adalah jumlah dari kuadrat selisih pada masing-masing kriteria

Public Shared Function HitungJarak(t1 As Titik, t2 As Titik) As Integer
	Dim selisihX As Integer = t2.X - t1.X
	Dim selisihY As Integer = t2.Y - t1.Y
	Dim selisihZ As Integer = t2.Z - t1.Z
	Return selisihX * selisihX + selisihY * selisihY + selisihZ * selisihZ
End Function

1b4b3. Apabila diamter yang ditemukan kurang dari diameter minimal,
maka catat diameter ini sebagai diameter minimal
dan simpan titik ini sebagai jawaban titik terdekat

If diameter(j) < minDiameter Then
	minDiameter = diameter(j)
	idxTitikTerdekat = j
End If

1b4c. Apabila titik terdekat masih berada di dalam diameter maksimal,
maka tambahkan titik ini ke dalam calon terpilih
Selain itu, hentikan perhitungan untuk calon terpilih ini

If CDbl(minDiameter) <= maksDiameter Then
	CalonTerpilih.Add(daftarTitik(idxTitikTerdekat))
	idxCalonDafterCluster(idxTitikTerdekat) = idxCalonTerpilih
	totalTitikTercluster += 1
Else
	Exit While
End If

1b5. tambahkan calon terpilih ke dalam calon daftar cluster

CalonDaftarCluster.Add(CalonTerpilih)

1c. Temukan calon cluster dengan jumlah titik terbanyak

Dim jumlahTitikTerbanyak As Integer = -1
Dim idxCalonClusterTerbaik As Integer = 0
For i As Integer = 0 To CalonDaftarCluster.Count - 1
	If CalonDaftarCluster(i).Count > jumlahTitikTerbanyak Then
		jumlahTitikTerbanyak = CalonDaftarCluster(i).Count
		idxCalonClusterTerbaik = i + 1
	End If
Next

1d. Untuk semua titik yang sudah terpilih masuk ke dalam cluster, hilangkan semua titik tersebut dari daftar titik

For i As Integer = idxCalonDafterCluster.Length - 1 To 0 Step -1
	If idxCalonDafterCluster(i) = idxCalonClusterTerbaik Then
		daftarTitik.RemoveAt(i)
	End If
Next

1e. Nilai Jawaban kumpulan titik terbaik adalah pada calon daftar cluster dengan indeks terbaik

Return CalonDaftarCluster(idxCalonClusterTerbaik - 1)

2. Masukkan daftar titik terbaik ke dalam cluster jawaban

daftarCluster.Add(daftarTitikTerbaik)

3. Hitung nilai cluster pada masing-masing cluster
Nilai pada setiap cluster dihitung dari penjumlahan data pada masing-masing kolom
Pada Kriteria umur, semakin rendah nilainya, maka semakin tinggi nilai kolomnya, dan sebaliknya.
Pada Kriteria jenis kelamin dan skor kepribadian, semakin tinggi nilainya, maka semakin tinggi nilai kolomnya, dan sebaliknya.

nilaiCluster(i) += (10 - t.X / 10) + t.Y + t.Z

4. Lihat kembali matriks data awal yang sudah terkelompok
Bandingkan nilai total data antara kedua cluster
Nilai total data yang lebih tinggi akan masuk ke dalam kelompok Diterima, sedangkan nilai total data yang lebih rendah akan masuk ke dalam kelompok Ditolak

If nilaiCluster(0) > nilaiCluster(1) Then
	Console.WriteLine("Nilai Kelompok pertama (" & nilaiCluster(0) & ") lebih dari Kelompok kedua (" & nilaiCluster(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Diterima")
	Console.WriteLine("Kelompok kedua adalah kelompok Ditolak")
Else
	Console.WriteLine("Nilai Kelompok pertama (" & nilaiCluster(0) & ") kurang dari Kelompok kedua (" & nilaiCluster(1) & "), maka: ")
	Console.WriteLine("Kelompok pertama adalah kelompok Ditolak")
	Console.WriteLine("Kelompok kedua adalah kelompok Diterima")
End If

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung data nama dan nilai pada masing-masing kriteria. Deklarasi Class Titik adalah sebagai berikut:

Class Titik
    Public Nama As String
    Public X As Integer, Y As Integer, Z As Double

    Public Sub New(Nama As String, x As Integer, y As Integer, Z As Double)
        Me.Nama = Nama
        Me.X = x
        Me.Y = y
        Me.Z = Z
    End Sub
End Class

Hasil akhir adalah: (klik untuk perbesar gambar)

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.