Algoritma k-NN (k-Nearest Neighbors)

Algoritma k-NN (k-Nearest Neighbors) adalah salah satu algoritma yang digunakan untuk klasifikasi atau pengelompokan data. Tetapi bisa juga digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah menentukan kelompok hasil jual tipe sepeda motor baru berdasarkan kelompok data yang sudah ada

Diasumsikan ada 4 tipe motor yang sudah diketahui datanya, yaitu Motor A,B,C,D
Masing-masing tipe motor memiliki kriteria, yaitu harga, jarak tempuh per liter, cc, dan memiliki hasil jual yaitu Laris / Tidak Laris
Diasumsikan data dari 4 tipe motor tersebut adalah sebagai berikut:

Selanjutnya ada 4 buah motor lagi, yaitu E,F,G,H, yang baru akan diluncurkan, sehingga tidak diketahui hasil jualnya
Maka tentukan data-data ini nantinya akan termasuk dalam kelompok hasil jual Laris / Tidak Laris
Diasumsikan data awalnya adalah sebagai berikut:

Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data awal adalah sebagai berikut:
Untuk kriteria hasil jual:
Nilai Laris dilambangkan dengan angka 1
Nilai Tidak Laris dilambangkan dengan angka 2

Dim MotorA As Double() = New Double() {10000000, 35, 110, 1}
Dim MotorB As Double() = New Double() {12000000, 45, 125, 1}
Dim MotorC As Double() = New Double() {11000000, 40, 150, 2}
Dim MotorD As Double() = New Double() {14000000, 37.5, 125, 2}

Dim contohData As New List(Of Double())()
contohData.Add(MotorA)
contohData.Add(MotorB)
contohData.Add(MotorC)
contohData.Add(MotorD)
		
Dim MotorE As Double() = New Double() {13000000, 45, 125, 0}
Dim MotorF As Double() = New Double() {12000000, 47, 110, 0}
Dim MotorG As Double() = New Double() {10500000, 43, 110, 0}
Dim MotorH As Double() = New Double() {13500000, 35, 125, 0}

Dim dataBaru As New List(Of Double())()
dataBaru.Add(MotorE)
dataBaru.Add(MotorF)
dataBaru.Add(MotorG)
dataBaru.Add(MotorH)

Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan normalisasi data untuk data contoh dan data yang baru.

Dim maks As Double = Double.MinValue
For j As Integer = 0 To 3
	If maks < contohData(j)(0) Then maks = contohData(j)(0)
	If maks < dataBaru(j)(0) Then maks = dataBaru(j)(0)
Next

For j As Integer = 0 To 3
	contohData(j)(0) /= maks
	dataBaru(j)(0) /= maks
Next

maks = Double.MinValue
For j As Integer = 0 To 3
	If maks < contohData(j)(1) Then maks = contohData(j)(1)
	If maks < dataBaru(j)(1) Then maks = dataBaru(j)(1)
Next

For j As Integer = 0 To 3
	contohData(j)(1) /= maks
	dataBaru(j)(1) /= maks
Next

maks = Double.MinValue
For j As Integer = 0 To 3
	If maks < contohData(j)(2) Then maks = contohData(j)(2)
	If maks < dataBaru(j)(2) Then maks = dataBaru(j)(2)
Next

For j As Integer = 0 To 3
	contohData(j)(2) /= maks
	dataBaru(j)(2) /= maks
Next

2. Tentukan parameter K, yaitu banyak jumlah titik tetangga yang diperhitungkan
Karena ada 4 data pada contoh awal, maka nilai K adalah 1 / 2 / 3 / 4
Diasumsikan dalam kasus ini, nilai K adalah 3, brarti hanya 3 titik tetangga terdekat yang diperhitungkan dalam setiap perhitungan

Const k As Integer = 3

3. Tentukan fungsi untuk menghitung jarak titik pada matriks normalisasi terhadap tiap-tiap titik pada matriks contohdata
Dalam contoh kasus ini, Ada 3 fungsi yang dapat digunakan, yaitu Euclidean, Chebyshev, dan Manhattan
Sebetulnya masih banyak fungsi pengukuran jarak yang lain seperti Spearman dan Pearson, tetapi fungsi-fungsi tersebut tidak dibahas dalam contoh ini.

Console.WriteLine("")
Console.WriteLine("Tentukan Fungsi yang digunakan untuk menghitung Jarak (1/2/3): ")
Console.WriteLine("1. Fungsi Euclidean")
Console.WriteLine("2. Fungsi Chebyshev")
Console.WriteLine("3. Fungsi Manhattan")
Dim input As Integer = CInt(Console.ReadLine)

4. Lakukan perhitungan jarak dengan fungsi yang telah ditentukan antara titik baru dengan semua titik data contoh
Karena ada 4 data contoh, maka lakukan 4 kali perhitungan untuk setiap titik baru

For j As Integer = 0 To 3
	Dim jarak As Double = 0
	If input = 1 Then
		jarak = Euclidean(dataBaru(i), contohData(j))
	ElseIf input = 2 Then
		jarak = Chebyshev(dataBaru(i), contohData(j))
	ElseIf input = 3 Then
		jarak = Manhattan(dataBaru(i), contohData(j))
	End If

	Dim dr As DataRow = dt.NewRow
	dr("index") = j
	dr("hasil jual") = contohData(j)(3)
	dr("jarak") = jarak

	dt.Rows.Add(dr)
Next

* Gunakan fungsi ini untuk menghitung jarak Euclidean antara 2 titik

Public Function Euclidean(X As Double(), Y As Double()) As Double
	Dim count As Integer = 0
	If X.GetUpperBound(0) <> Y.GetUpperBound(0) Then
		Throw New System.ArgumentException("Jumlah elemen data baru dan data contoh tidak sama")
	Else
		count = X.Length
	End If

	Dim jumlah As Double = 0.0
	For i As Integer = 0 To count - 2
		jumlah = jumlah + Math.Pow(Math.Abs(X(i) - Y(i)), 2)
	Next

	Dim jarak As Double = Math.Sqrt(jumlah)
	Return jarak
End Function

* Gunakan fungsi ini untuk menghitung jarak Chebyshev antara 2 titik

Public Function Chebyshev(X As Double(), Y As Double()) As Double
	Dim count As Integer = 0
	If X.GetUpperBound(0) <> Y.GetUpperBound(0) Then
		Throw New System.ArgumentException("Jumlah elemen data baru dan data contoh tidak sama")
	Else
		count = X.Length
	End If

	Dim jumlah As Double() = New Double(count - 2) {}
	For i As Integer = 0 To count - 2
		jumlah(i) = Math.Abs(X(i) - Y(i))
	Next
	Dim maks As Double = Double.MinValue
	For Each num As Double In jumlah
		If num > maks Then
			maks = num
		End If
	Next
	Return maks
End Function

* Gunakan fungsi ini untuk menghitung jarak Manhattan antara 2 titik

Public Function Manhattan(X As Double(), Y As Double()) As Double
	Dim count As Integer = 0
	If X.GetUpperBound(0) <> Y.GetUpperBound(0) Then
		Throw New System.ArgumentException("Jumlah elemen data baru dan data contoh tidak sama")
	Else
		count = X.Length
	End If

	Dim jumlah As Double = 0.0
	For i As Integer = 0 To count - 2
		jumlah = jumlah + Math.Abs(X(i) - Y(i))
	Next

	Dim jarak As Double = jumlah
	Return jarak
End Function

5. Lakukan pengurutan data berdasarkan jarak terendah

Dim dv As DataView = dt.DefaultView
dv.Sort = "jarak"
dt = dv.ToTable

6. Untuk k data teratas, yaitu 3, hitung jumlah data untuk hasil jual Laris dan Tidak Laris
Ambil kesimpulan berdasarkan jumlah data Laris / Tidak Laris yang lebih banyak

Dim Laris As Integer = 0
Dim TidakLaris As Integer = 0
For j As Integer = 0 To 3
	Console.WriteLine("Jarak ke Motor " & Chr(dt.Rows(j)("index") + 65) & " (" & IIf(dt.Rows(j)("hasil jual") = 1, "Laris", IIf(dt.Rows(j)("hasil jual") = 2, "Tidak Laris", "")) & ") -> " & Math.Round(dt.Rows(j)("jarak"), 2))

	If j <= k - 1 Then
		If dt.Rows(j)("hasil jual") = 1 Then
			Laris += 1
		ElseIf dt.Rows(j)("hasil jual") = 2 Then
			TidakLaris += 1
		End If
	End If
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

untuk perhitungan dengan fungsi Euclidean:

untuk perhitungan dengan fungsi Chebyshev:

untuk perhitungan dengan fungsi Manhattan:

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.