Penerapan Metode K-Means-ACO Untuk Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 2, No. 4, April 2018, hlm. 1657-1666

e-ISSN: 2548-964X http://j-ptiik.ub.ac.id

Penerapan Metode K-Means-ACO Untuk Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji Pangestu Ari Wijaya1, Rekyan regasari Mardi Putri2, Dian Eka Ratnawati3 Program Studi Teknik Informatika, Fakultas Ilmu Komputer, Universitas Brawijaya Email: [email protected], [email protected], [email protected] Abstrak Wijen merupakan salah satu bahan makanan yang menghasilkan minyak nabati. Kebutuhan wijen saat ini semakin meningkat sehingga perlu adanya kualitas yang baik dalam memproduksi wijen. Untuk melakukan proses persilangan tanaman wijen, warna cangkang biji wijen sangat berpengaruh pada kualitasnya. Dari beberapa penelitian sebelumnya telah dilakukan pengelompokan biji wijen dengan metode kualitatif dan kuantitatif. Pada metode kualitatif dilakukan dengan pengamatan langsung sedangkan pada metode kuantitatif dilakukan dengan mengolah data wijen dari hasil pengukuran menggunakan alat chromameter yang menghasilkan atribut warna L*, a* dan b*. Beberapa penelitian sebelumnya telah berhasil melakukan pengelompokan dengan metode kuantitatif yaitu metode IWOKM, PSOKM dan GAKM. Penelitian ini akan mengelompokan dan membandingkan hasil data wijen dengan data yang sama menggunakan metode K-Means ACO dengan metode sebelumnya. Dari beberapa jurnal metode tersebut terbukti metode K-Means-ACO memiliki hasil yang optimal, karena dalam pengelompokkannya menggabungkan metode algoritma optimasi dan clustering. Berdasarkan hasil pengujian metode K-Means-ACO dibandingan dengan metode sebelumnya, hasilnya baik dalam mengelompokan biji wijen berdasarkan sifat warna cangkang biji. Hal ini dibuktikan dengan hasil pengelompokan yang hampir mirip dengan penelitian sebelumnya yaitu 233 : 58. Sehingga dapat disimpulkan bahwa metode K-Means-ACO dapat digunakan sebagai metode alternatif untuk pengelompokan biji wijen berdasarkan sifat warna cangkang biji. Kata kunci: Ant Colony Optimization , K-Means, K-Means-ACO, wijen, chromameter, pengelompokan, kualitatif, kuantitatif

Abstract Sesame is one kinds of the groceries that produce vegetable oil. Nowadays, the needs of sesame is increasing so it is necessary to pick a good quality in producing sesame. To conduct sesame plants crossing, the color of sesame seed shell is very infuential on its quality. Several previous studies used in this research has been done to cluster sesame seed with qualitative and quantitative method. The qualitative method in this research is conducted by field observation while the quantitative method is conducted by processing the sesame data from measurement result by using chromameter which resulted of an L*, a* and b* color. Several previous studies has successfully done the clustering by using qualitative method namely IWOKM, PSOKM and GAKM method. This study will categorize and compare the result of sesame data with same of data by using K-Means-ACO method with the previous method. From several journals, the method is proved that K-Means-ACO method has optimal results because in the analysis step combined the optimization and clustering algorithm method. Based on the test results of the K-Means-ACO method compared with the previous method, the good result of clustering sesame seed based on the color of the seed shell. It is proven by the grouping result is 233:58. After all, this research could be concluded that the K-Means-ACO method could be used as the alternative method to conduct the sesame seed classification based on its seed shell color. Keywords: Ant Colony Optimization , K-Means, K-Means-ACO, sesame, chromameter, grouping, qualitative, quantitative

Fakultas Ilmu Komputer Universitas Brawijaya

1657

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

1. PENDAHULUAN Sesame atau dalam bahasa latin disebut Sesamum indicum L yang dikenal sebagai wijen, anggota family Pedaliaceae merupakan salah satu tanaman oilseed (biji minyak) paling kuno (El Khier, 2008). Wijen memiliki peran penting dalam hal pemenuhan gizi manusia. Sebagian besar biji wijen diolah sebagai minyak dan sisanya untuk pemenuhan bahan makanan (El Khier, 2008). Perkembangan pangan di seluruh dunia saat ini semakin meningkat, wijen menjadi bahan baku makanan yang paling banyak dikonsumsi. Saat ini, penyebaran wijen telah mendunia. Produsen wijen dunia yaitu Sudan, Nigeria, Birma, meksiko, Ethiopia, Uganda, dan Turki. Kian lama, wijen telah mencapai Amerika dan sebagian di Asia (Handayani, 2002). Kebutuhan wijen saat ini semakin meningkat sehingga perlu adanya peningkatan untuk memproduksi wijen yang berkualitas baik. Dalam menentukan kualitas wijen faktor terpenting adalah dari warna biji cangkang. Warna cangkang biji wijen yang paling berkualitas dan bagus adalah warna putih, karena kandungan proteinnya yang sangat tinggi sehingga bisa menghasilkan minyak wijen yang bagus. Sedangkan wijen berwarna hitam kurang baik untuk menghasilkan minyak, namun wijen hitam memiliki kelebihan kandungan fosfor dan karbohidrat yang lebih tinggi dari pada biji wijen yang berwarna putih (Zhang, 2013). Warna cangkang biji wijen merupakan atribut paling penting untuk memperkenalkan wijen di pasaran. Warnanya bervariasi dari putih hingga hitam. Warna cangkang biji salah satu sifat penting di pasar ekspor sehingga menjadi hal utama dalam pemuliaan atau pembudidayaan biji wijen (Laurentin, 2014). Untuk menghasilkan wijen yang berkualitas baik dan beragam, perlu dilakukan persilangan wijen. Dari hasil persilangan tersebut akan muncul berbagai macam biji wijen dan kualitas yang berbeda – beda. Setiap biji wijen hasil persilangan memiliki warna cangkang biji yang hampir mirip dengan kualitas biji yang berbeda – beda. Sehingga dari warna cangkang wijen yang beragam tersebut sebaiknya perlu adanya metode pengelompokan biji wijen berdasarkan kedekatan warna untuk mengetahui kualitas atau kemiripan sifat cangkang biji wijen (Adikadarsih, 2015 dalam Ihwanudien, 2017). Pada penelitian yang dilakukan Adikadarsih tentang Pewarisan Sifat Warna Cangkang Biji Fakultas Ilmu Komputer, Universitas Brawijaya

1658

pada Persilangan Wijen (Sesamum indicum L.) Kultivar ‘SBR2’ × ‘SBR3’ dan ‘SBR3’ × Turki ‘Det 36’ (Adikadarsih, 2015). Dari penelitian tersebut dilakukan perbandingan antara pengelompokan kualitatif dan kuantitatif, pada pengelompokan kualitatif yaitu dengan mengelompokan warna cangkang dengan pengamatan secara langsung, sedangkan pada pengelompokan dengan cara kuantitatif yaitu menggunakan bantuan dengan alat chromameter. (Adikadarsih, 2015 dalam Ihwanudien, 2017). Dalam penelitian tersebut menunjukkan bahwa hasil pengelompokan antara kualitatif dengan kuantitatif hampir mirip. Menurut penelitian Adikadarsih, walaupun telah ada gabungan dua metode tersebut diharapkan di masa akan dating terdapat suatu model pengelompokan lain berdasarkan kedekatan warna (Robbani, 2017). K-Means adalah metode pengelompokan data yang biasa digunakan untuk pembelajaran tanpa pengawasan (unsupervised learning) (Ding, 2005). Semakin banyak perkembangan metode maka ada beberapa penelitian yang menggabungan K-Means dengan metode lainnya agar memperoleh hasil yang lebih baik. Beberapa penelitian tersebut diantaranya : Pengelompokan Biji Wijen berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode IWOKM (Robbani, 2017) dengan nilai fitness 10,1461 dan nilai kekompakan 0,7714, Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode PSOKM (Devi, 2017) dengan nilai fitness 10,4136 dan nilai kekompakan 0,7686 dan Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode GA – K-Means (Maulida, 2017) dengan nilai fitness 10,2084 dan nilai kekompakan 0,7701. Peneltian tersebut memiliki nilai fitness dan nilai kekompakan yang berbeda. Sehingga pada penelitian ini mengusulkan metode lain yang harapannya akan lebih akurat dalam pengelompokan warna biji wijen. Metode pengelompokan menggunakan KMeans umumnya sering digunakan karena cepat dan mudah dalam pembelajarannya, namun memiliki kelemahan yaitu buruknya inisialisasi awal pusat cluster (Hamerly, 2002). Sehingga algoritma K-Means sulit untuk konvergen pada solusi yang optimal (Xu, 2010). Kemudian pada penelitian ini menggunakan metode K-MeansACO dengan menggabungkan metode K-Means dan metode Ant Colony Optimization (ACO)


yang diharapkan dapat konvergen pada solusi yang optimal. Metode clustering K-Means akan melakukan proses pengelompokan, sedangkan metode Ant Colony Optimization akan melakukan proses iterasi hingga menemukan hasil yang paling optimal. Untuk membuktikan bahwa metode gabungan antara K-Means-ACO dapat melakukan proses pengelompokan didukung pada penelitian terdahulu yaitu Hyperspectal Image Clustering Using Ant Colony Optimization (ACO) Improved by KMeans Algorithm (Xu, 2010). Berdasarkan penjelasan latar belakang diatas, maka disusunlah skripsi ini yang berjudul “Penerapan Metode K-Means-ACO untuk Pengelompokan Bji Wijen Berdasarkan Sifat Warna Cangkang Biji”. Atribut data yang dipakai dalam penelitian ini berjumlah tiga atribut warna dengan menggunakan format warna CIELAB yaitu L*, a*, b*. Dalam pengukuran warna tersebut menggunakan alat chromameter. Penelitian ini diharapankan apakah metode K-Means-ACO lebih baik dari penelitian sebelumnya yang memakai metode IWOKM, PSOKM, GAKM. Untuk mengetahui performa dari metode K-Means-ACO apakah lebih baik dari penelitian sebelumnya maka dilakukan pengujian nilai fitness dan nilai kekompakannya. Pengujian ini untuk mengetahui apakah metode K-Means-ACO pengelompokannya lebih baik daripada metode K-Means saja. Pada hasil dari penelitian ini adalah untuk mengetahui apakah dapat digunakan untuk metode alternatif dalam pengelompokan biji wijen berdasarkan sifat warna cangkang biji. 2. PERSILANGAN WIJEN Komponen dari tanaman wijen yang memiliki nilai ekonomi yang tinggi adalah warna biji wijen. Jika biji wijen tersebut bersih akan memiliki harga yang lebih tinggi, selain itu beberapa penelitian terdahulu dari warna biji wijen mempengaruhi hasil wijen, kadar minyak, dan kandungan biokimia pada wijen (Adikadarsih, 2015 dalam Robbani, 2017). Persilangan wijen pada penelitian Adikadarsih (2015) menggunakan kultivar SBR 3 dan SBR 2. SBR 3 sebagai induk betina yang berwarna coklat bergenotipe TT. SBR 2 sebagai induk jantan yang berwarna putih bergenotipe tt. Hasil persilangan dua kultivar tersebut yaiu populasi bergenotipe Tt yang berwarna coklat seluruhnya. Sedangkan untuk respiroknya, pada Fakultas Ilmu Komputer, Universitas Brawijaya

1659

SBR 2 sebagai induk betina yang berwarna putih bergenotipe tt, lalu pada SBR 3 sebagai induk jantan yang berwarna putih seluruhnya bergenotipe TT. Hasil dari persilangan tersebut berwarna putih bergenotipe Tt. Sehingga dapat diketahui bahwa warna pada induk betina memiliki pengaruh paling besar pada hasil persilangan wijen. (Adikadarsih, 2015 dalam Robbani, 2017) Dari hasil persilangan F0, disilangkan Tetua Tt dengan warna coklat dan tetua Tt dengan warna putih, menghasilkan biji wijen berwarna coklat dengan genotipe TT : Tt : tt = 1 : 2 : 1. Lalu dilakukan persilangan hasil F1, tetua Tt : Tt = coklat : putih, yang menghasilkan biji berwarna coklat dan putih dengan perbandingan 3:1. (Adikadarsih, 2015 dalam Robbani, 2017)

Gambar 1. Model alur pewarisan gen warna cangkang biji hasil persilangan SBR3 x SBR2 dan resikproknya

Persilangan serupa juga terjadi antara SBR3 dengan Dt36, SBR 3 sebagai induk betina yang berwarna coklat bergenotipe TT. Dt36 sebagai induk jantan yang berwarna putih bergenotipe tt. Hasil persilangan dua kultivar tersebut yaitu populasi bergenotipe Tt yang berwarna coklat seluruhnya. Sedangkan untuk respiroknya, pada Dt36 sebagai induk betina yang berwarna putih bergenotipe tt, lalu pada SBR 3 sebagai induk jantan yang berwarna coklat seluruhnya bergenotipe TT. Hasil dari persilangan tersebut berwarna putih bergenotipe Tt. Sehingga dapat diketahui bahwa warna pada induk betina memiliki pengaruh paling besar pada hasil persilangan wijen. (Adikadarsih, 2015 dalam Robbani, 2017) Dari hasil persilangan F0, disilangkan Tetua Tt dengan warna coklat dan tetua Tt dengan warna putih, menghasilkan biji wijen berwarna coklat dengan genotipe TT : Tt : tt = 1 : 2 : 1. Lalu dilakukan persilangan hasil F1, tetua Tt : Tt = coklat : putih, yang menghasilkan biji


berwarna coklat dan putih dengan perbandingan 3:1. (Adikadarsih, 2015 dalam Robbani, 2017)

1660

sampai fungsi error tidak berubah secara signifikan atau keanggotaan dari kelompok tidak ada perubahan lagi. (Gan, 2007) Algoritma K-Means menurut Hartigan (1975) akan di deskripsikan lebih jelas sebagai berikut : Misal D adalah sebuah data set dengan n objek dan C1, C2, . . . .,Ck, k merupaka cluster terpisah dari D. Fungsi error dapat di definisikan sebagai berikut : (Gan, 2007) 2

𝐸 = ∑𝑘𝑖=1 ∑𝑝 𝜖 𝐶𝑖 √(𝑥1 − µ(𝐶1 )) + ⋯ + (𝑥𝑛 − µ(𝐶𝑛 ))

Gambar 2. Model alur pewarisan gen warna cangkang biji hasil persilangan SBR3 x Dt36 dan resikproknya

Pada penelitian sebelumnya dilakukan perhitungan hasil pengelompokan warna secara kualitatif dan kuantitatif seperti pada Tabel 2.2. pada table tersebut menunjukkan bahwa ada perbedaan pada generasi F2 (Adikadarsih, 2015, dalam Robbani, 2017). Tabel 1. Hasil Pengelompokan biji wijen secara kuantitatif dan kualitatif GENOTIF

SBR 3 SBR 2 Dt 36 F0 SBR3 x SBR2 F0 SBR2 x SBR3 F0 SBR3 x Dt36 F0 Dt36 x SBR3 F1 SBR3 x SBR2 F1 SBR2 x SBR3 F2 SBR3 x Dt36 F1 Dt36 x SBR3 F2 SBR3 x SBR2 F2 SBR2 x SBR3 F2 SBR3 x Dt36 F2 Dt36 x SBR3

KUANTITATIF KUALITATIF Coklat Coklat Putih Coklat Coklat Putih muda muda 255 255 23 23 185 185 3 3 5 5 3 3 4 4 57 57 17 17 11 11 25 25 216 15 60 210 27 54 201 35 92 196 38 94 308 76 38 298 82 42 92 25 29 90 23 33

3. K-MEANS Algoritma K-Means merupakan salah satu algoritma yang paling sering digunakan untuk pengelompokan. Algoritma ini dirancang untuk cluster data numerik di mana setiap cluster memiliki pusat yang disebut mean. Algoritma KMeans diklasifikasikan sebagai metode pengelompokan partitional atau nonhierarchical. Pada algoritma ini, jumlah cluster k harus didefinisikan diawal. Adapun fungsi error algoritma K-Means yaitu memberikan inisialisasi k cluster dengan mengalokasikan data yang tersisa untuk cluster terdekat dan kemudian berulang kali mengubah keanggotaan kelompok menurut fungsi error Fakultas Ilmu Komputer, Universitas Brawijaya

(1) µ(Ci) : Centroid dari cluster Ci d(x, µ(Ci))2 : jarak antara titik data x dan titik pusat µ(Ci) Secara ringkas, algoritma K-Means konvensional dapat dijelaskan sebagai berikut : (Gan, 2007) Require : Data set D, jumlah cluster k, dimensi d Tahap Inisialisasi K-Means 1. (C1, C2, . . . .,Ck) = Inisialisasi pusat cluster secara acak diambil dari dataset D Tahap Iterasi. 2. dij = jarak antara titik I ke cluster j (Persamaan 2.1); Hitung dij = jarak antara titik i ke cluster j menggunakan rumus Euclidean Distance. 3. nij = arg min i ≤ j ≤ k dij ; Tentukan nilai min jarak terdekat titik i ke cluster j. 4. Tetapkan titik i tergolong ke dalam cluster ke berapa nI . 5. Hitung rata-rata centroid cluster. 6. Ulangi langkah 2 – 5 hingga tidak ada perubahan anggota cluster. 7. Hasil Output. Algoritma K-Means ini memilki dua tahap yaitu tahap inisialisasi dan tahap iterasi. Pada tahap inisialisasi, secara acak memilih centroid k cluster dari data set. Lalu pada tahap iterasi, menghitung jarak antara setiap objek dengan setiap cluster dan menentukan objek yang paling dekat dengan cluster. 4. ANT COLONY OPTIMIZATION Ant Colony Optimization (ACO) adalah salah satu metode untuk membantu meningkatkan kinerja clustering. Swarm intelligence adalah pendekatan yang relatif baru untuk pemecahan masalah yang mengambil inspirasi dari perilaku serangga dan hewan lainnya. Secara khusus, semut telah mengilhami sejumlah metode dan teknik di antara yang paling dipelajari dan yang paling sukses adalah


tujuan umum teknik optimasi yang dikenal sebagai optimasi koloni semut. Optimasi koloni semut mengeksploitasi mekanisme yang sama untuk memecahkan sebuah optimasi masalah. Dari awal tahun sembilan puluhan, ketika pertama koloni semut optimasi algoritma diusulkan, ketertarikan beberapa peneliti terhadap metode ACO semakin meningkat dan banyak aplikasi yang sukses yang telah digunakan pada metode tersebut (Gnanapriya, 2013). Berikut dibawah ini adalah contoh solusi hasil jarak terpendek yang berhasil dilewati semut ditunjukan pada Gambar 3.

1661 𝑛𝑒𝑤 𝜏𝑖𝑗 = 𝑜𝑙𝑑 𝜌𝜏𝑖𝑗 + 𝑄/𝑓𝑚𝑖𝑛 𝑦𝑖𝑗 𝑎𝑑𝑎𝑙𝑎ℎ 𝑝𝑎𝑡ℎ 𝑡𝑒𝑟𝑏𝑎𝑖𝑘 { (3) 𝑜𝑙𝑑 𝑦𝑖𝑗 𝑎𝑑𝑎𝑙𝑎ℎ 𝑏𝑢𝑘𝑎𝑛 𝑝𝑎𝑡ℎ 𝑡𝑒𝑟𝑏𝑎𝑖𝑘 𝜌𝜏𝑖𝑗

Keterangan : τij = Pheromone baru ρ = Koefisien penguapan τ𝑜𝑙𝑑 = Inisialisasi pheromone 𝑖𝑗 Q = Kecepatan pheromone fmin = Fungsi optimal (nilai fitness terkecil) 5. METODE 5.1 Data

Gambar 3. Solusi Jarak Optimal Ant Colony Optimization (ACO)

Untuk menentukan nilai probabilitas digunakan untuk semut mencari jalan/path terbaik. Hasil yang didapat dari nilai probabilitas yang tertinggi akan diproses untuk update pheromone. Jika semut menempati sebuah path yang terbaik, maka nilai probabilitas tersebut akan bernilai/mendekati 1. Dan jika semut tidak menempati path terbaik maka nilai probabilitas bernilai/mendekati 0. Metode ACO sendiri bekerja dengan mancari solusi optimal, berikut merupakan tahap metode ACO : 1. Memprediksi perilaku semut : menghitung probabilitas semut k pada simpul i ke simpul tujuan j. 𝜏𝑖𝑗

∑𝑘 𝑗=1 𝜏

𝑥𝑖 ∉ 𝑋 ′

1 𝑥𝑖 ∈𝑋 ′ 𝑎𝑛𝑑 𝑗=arg max{𝜏𝑖𝑗 }

𝑝𝑖𝑗 =

𝑗

{

(2)

0 𝑥𝑖 ∈𝑋 ′ 𝑎𝑛𝑑 𝑗=arg max{𝑡𝑖𝑗 } 𝑗

Keterangan : Pij = Probabilitas pada semut ke i iterasi j τij = pheromon pada semut ke i iterasi j 2. Penambahan dan Penguapan Pheromon (Update Pheromone) : Semut k akan meninggalkan pheromon pada ruas ij, jumlah pheromon pada ruas i,j akan dihitung dengan rumus: Fakultas Ilmu Komputer, Universitas Brawijaya

Teknik pengumpulan data yang digunakan adalah data sekunder dari hasil observasi sifat warna cangkang biji yang diukur dengan alat chromameter pada hasil persilangan Tanaman Wijen Kultivar ’SBR2’ x ‘SBR3’ dan ‘SBR3’x Turki ‘Det 36’ (Adikadarsih, 2015). Pada data yang diambil dengan alat chromameter dengan format CIELAB menghasilkan tiga atribut, yaitu L*, a*, b*. Berikut merupakan contoh kumpulan data hasil dari persilangan wijen pada Tabel 2. Tabel 2. Jumlah data hasil persilangan wijen

Data keL* a* b* 1 31,7800 10,5700 13,3200 2 28,3900 11,0200 11,6700 3 51,8600 9,1850 18,2650 4 27,7900 5,2100 4,0350 5 28,2800 10,2900 10,3350 ... ... ... ... 291 56,0750 11,9650 23,6350 Pada penelitian ini menggunakan sampel data persilangan SBR3 x SBR 2 yang berjumlah 291.

5.2 Tahapan Metode Dalam siklus penyelesaian ini terdapat beberapa proses yang dilakukan untuk melakukan sebuah penyelesaian dalam masalah pengelompokan biji wijen dengan menggunakan metode hybrid yaitu K-Means dan Ant Colony Optimization. Pada proses pertama yang akan dilakukan adalah menghitung hasil dari proses klustering dengan menggunakan algoritma KMeans dan mendapatkan nilai probabilitasnya (p’). Dalam menentukan nilai probabilitas yaitu dihitung dari nilai fitness hasil klustering. Berikut merupakan tahapan ini untuk menyelesaikan sebuah masalah pengelompokan


biji wijen dengan menggunakan metode KMeans-ACO adalah : 1. Inisialisasi Parameter Awal Inisialisasi parameter awal dibagi menjadi dua. Data warna cangkang biji wijen dan parameter algoritma K-Means-ACO. a. Data warna cangkang biji wijen meliputi 3 variabel yaitu L*, a*, dan b*. b. Parameter K-Means-ACO meliputi jumlah kelompok, jumlah koloni semur, standart deviasi awal, standart deviasi akhir, dan jumlah limit. 2. Proses tahapan metode K-Means-ACO a. Inisialisasi posisi awal koloni semut menggunakan Persamaan 4. 𝑗

𝑗

𝑗

𝑥𝑖 = 𝑥𝑚𝑖𝑛 + 𝑟𝑎𝑛𝑑(0,1)(𝑥𝑗𝑚𝑎𝑥 − 𝑥𝑚𝑖𝑛 )

(4)

Dimana, 𝑗 𝑥𝑖 = data random cluster j, data i. 𝑗 𝑥𝑚𝑖𝑛 = batas nilai minimal 𝑗 𝑥𝑚𝑎𝑥 = batas nilai maksimal b. Menentukan keanggotaan data menggunakan algoritma K-Means menggunakan Persamaan 1. - Menghitung jarak data ke titik pusat cluster. - Menentukan keanggotaan data c. Menghitung nilai rata-rata fitness dengan menggunakan Persamaan 5. 1 1 𝑁 2 fitness (x, y) = 𝑀 ∑𝑁 𝑗=𝑖 (𝑁 ∑𝑗=1(𝑥𝑗 − 𝑦𝑗 ) ) (5) Dimana, x = nilai x ke indeks j y = nilai y ke indeks j M = jumlah titik pusat N = jumlah data - Menghitung jarak data fitness. - Menghitung jumlah anggota cluster. - Menghitung nilai fitness setiap cluster. - Menghitung nilai fitness semut. d. Menghitung nilai probabilitas dengan menggunakan Persamaan (2). e. Menghitung update pheromone pada setiap iterasi dengan menggunakan Persamaan (3). f. Menghitung update posisi semut di iterasi selanjutnya memiliki dua proses yaitu untuk pheromone terbaik update posisi semut di iterasi selanjutnya tidak akan berubah, sedangkan pada semut Fakultas Ilmu Komputer, Universitas Brawijaya

1662 lainnya pada posisi semut akan dihitung berdasarkan nilai mean semut pada pheromone terbaik menggunakan Persamaan (6). 𝑥 = 𝑅𝐴𝑁𝐷𝐵𝐸𝑇𝑊𝐸𝐸𝑁

(

(𝑀𝑒𝑎𝑛−𝑆𝑡.𝐷𝑒𝑣)∗10000 ; ) (𝑀𝑒𝑎𝑛+𝑆𝑡.𝐷𝑒𝑣)∗ 10000 10000

(6)

g. Ulangi proses iterasi koloni semut hingga batas iterasi sampai konvergen, jika belum konvergen lakukan langkah (a). Jika proses sudah konvergen maka pengelompokan dan proses iterasi akan berhenti. Berikut merupakan tahapan proses Algoritma K-Means-ACO untuk menyelesaikan masalah pengelompokan biji wijen berdasarkan warna cangkang biji ditunjukan pada Gambar 4. Mulai

Data Warna Biji Wijen dan Parameter Algoritma K-Means-ACO

Inisialisasi Posisi Awal Koloni Semut

Menentukan keanggotaan data menggunakan K-Means

Menentukan Rata – Rata Nilai Fitness

Menentukan Nilai Probabilitas

Menghitung Update Pheromone

Menghitung Update Posisi

Posisi Terbaik == true Ya Hasil Pengelompokan

Selesai

Gambar 4. Diagram alir tahapan proses pengelompokan biji wijen dengan menggunakan algoritma K-Means-ACO

Tidak


Hasil pengelompokkan dengan metode KMeans-ACO sama dengan hasil penelitian sebelumnya yang menggunakan metode IWOKM, PSOKM dan GAKM yaitu 233:58. Nilai parameter optimal yaitu dengan jumlah koloni sebanyak 300, standar deviasi awal bernilai 1, standar deviasi akhir bernilai 0,001, dan limit sebanyak 15. 6.1 Perbandingan Metode K-Means dan KMeans-ACO Pada hasil metode K-Means-ACO performanya cukup bagus jika dibandingkan pada metode K-Means. Dari hasil nilai fitness pada metode K-Means, hasilnya tidak bisa lebih baik dari 10,4262. Sedangkan pada hasil dari metode K-Means-ACO sendiri mendapatkan hasil yang cukup baik dari metode K-Means yaitu 10,1370. Metode K-Means masih belum bisa mencapai nilai fitness yang bagus dibandingkan dengan nilai fitness terendah pada metode K-Means-ACO yaitu 10,1676. Hasil yang didapat dari rata-rata nilai fitness dalam pengujian sebanyak 48 kali pada metode KMeans-ACO yaitu 10,1469, sedangkan pada hasil rata-rata nilai fitness metode K-Means yaitu 10,4262. Dapat disimpulkan bahwa nilai fitness yang didapat pada metode K-MeansACO jauh lebih baik dibandingkan dengan metode K-Means. Berikut merupakan hasil perbandingan nilai fitness pada metode K-Means dan K-Means-ACO yang ditunjukan pada Gambar 5. Nilai Fitness Metode K-Means dan KMeans ACO 10,5

Nilai FItness

10,4 10,3 10,2 10,1 10 9,9 1 5 9 13 17 21 25 29 33 37 41 45

Jumlah Pengujian K-Means

K-Means-ACO

Gambar 5. Grafik nilai fitness metode K-Means dan K-Means-ACO

Fakultas Ilmu Komputer, Universitas Brawijaya

Hasil dari perbandingan nilai kekompakan kelompok dengan menggunakan silhouette coefisien untuk metode K-Means dan metode KMeans-ACO. Dapat disimpulkan bahwa pengujian nilai kekompakan kelompok pada metode K-Means hasilnya tidak lebih bagus dari 0, 7660, sedangkan pada metode K-Means-ACO sendiri pada pengujian nilai kekompakannya memiliki hasil yang cukup baik dari metode KMeans yaitu sebesar 0,7734. Hasil rata-rata yang didapatkan pengujian ini dari metode K-Means yaitu sebesar 0,7660, sedangkan pada metode KMeans-ACO sebesar 0,7715. Dapat disimpulkan bahwa nilai kekompakan kelompok pada metode K-Means-ACO lebih baik daripada K-Means. Berikut merupakan hasil grafik pengujian nilai kekompakan kelompok pada perbandingan metode K-Means-ACO dan K-Means yang ditunjukkan pada Gambar 6. Nilai Silhouette Coeffisient Metode KMeans- dan K-Means-ACO Nilai Silhouette

6. HASIL DAN PEMBAHASAN

1663

0,774 0,772 0,77 0,768 0,766 0,764 0,762 1 5 9 13 17 21 25 29 33 37 41 45

Jumlah Pengujian K-Means

K-Means-ACO

Gambar 6. Grafik nilai silhouette coeffisient metode K-Means dan K-Means-ACO

6.2 Perbandingan Metode KM, K-MeansACO, IWOKM, PSOKM dan GAKM. Dapat disimpulkan bahwa metode KMeans-ACO mendapatkan hasil yang cukup baik dalam performanya. Dari hasil pengujian nilai fitness yang didapat pada metode K-MeansACO sebesar 10,1469. Sedangkan pada hasil dari metode IWOKM mendapatkan nilai yang cukup baik yaitu 10,1461, metode PSOKM, dan GAKM mendapatkan hasil 10,4136 dan 10,2084. Berikut dibawah ini merupakan grafik perbandingan nilai fitness pada metode KMeans, K-Means-ACO, IWOKM, PSOKM, dan GAKM yang ditampilkan pada Gambar 7.


Perbandingan Nilai Fitness Metode KM, K-Means-ACO, IWOKM, PSOKM, GAKM

Nilai Fitness

10,6

1664

Hasil dari pengelompokan biji wijen berdasarkan sifat warna cangkang biji menggunakan metode K-Means-ACO dengan penelitian sebelumnya ditunjukan pada Tabel 3. Tabel 3. Perbandingan hasil pengelompokan dengan penelitian terdahulu

10,4 10,2 10 9,8 1

2

3

4

5

6

Jumlah Pengujian KM IWOKM

K-Means_ACO PSOKM

Gambar 7. Grafik nilai fitness K-Means, K-MeansACO, IWOKM, PSOKM, GAKM

Kesimpulan dari pengujian ini adalah bahwa metode K-Means-ACO mendapatkan hasil yang cukup baik dalam performanya. Dari hasil rata-rata nilai kekompakan kelompok dengan menggunakan silhouette coeffisient yang didapat pada metode K-Means-ACO sebesar 0,7715. Sedangkan pada hasil dari metode IWOKM mendapatkan nilai yang cukup baik yaitu 0,7714, dibandingkan dengan metode KMeans-ACO hasilnya tidak jauh berbeda dengan IWOKM. Sedangkan metode PSOKM dan GAKM hasilnya tidak cukup baik yaitu 0,7686 dan 0,7701. Berikut merupakan grafik hasil dari perbandingan nilai kekompakan kelompok dengan menggunakan silhouette coefisien pada metode K-Means, K-Means-ACO, IWOKM, PSOKM, dan GAKM yang ditampilkan pada Gambar 8. Perbandingan Nilai Silhoutte Coeffisient Metode KM, K-Means-ACO, IWOKM, PSOKM, GAKM

Metode Kualitatif Kuantitatif K-Means IWOKM PSOKM GAKM K-Means-ACO

C1 54 60 60 58 58 58 58

C2 237 231 231 233 233 233 233

Dapat disimpulkan dari perbandingan hasil pengujian pengelompokan pada penelitian terdahulu sebagai berikut: 1. Dari hasil perbandingan metode K-MeansACO pada penelitian sebelumnya yaitu IWOKM, PSOKM, dan GAKM metode ini memiliki hasil nilai yang tidak berbeda jauh dengan nilai rata-rata fitness dan nilai kekompakan dengan menggunakan silhouette coeffisient pada metode sebelumnya. Sehingga metode ini bisa digunakan sebagai metode alternatif pengelompokan biji wijen berdasarkan sifat warna cangkang biji. 2. Pada metode K-Means-ACO maupun metode K-Means untuk perbandingan hasil pengelompokannya dengan penelitian yang dilakukan oleh Adikadarsih (2015) yaitu dengan metode kualitatif dan kuantitatif hasil pengelompokannya tidak jauh berbeda. Sehingga bisa disimpulkan bahwa metode KMeans-ACO dapat menjadi metode alternatif untuk pengelompokan biji wijen berdasarkan sifat warna cangkang biji.

Nilai Silhouette

0,78

7. KESIMPULAN

0,775 0,77 0,765 0,76 1 KM IWOKM GAKM

2

3 4 Jumlah Pengujian

5

6

K-Means-ACO PSOKM

Gambar 8. Grafik nilai silhouette coeffisient KMeans, K-Means-ACO, IWOKM, PSOKM, GAKM Fakultas Ilmu Komputer, Universitas Brawijaya

Pada penelitian pengelompokan biji wijen berdasarkan sifatwarna cangkang biji dengan metode K-Means-Ant Colony Optimization (KMeans-ACO) makan dapat disimpulkan sebagai berikut: 1. Untuk menentukan performa dalam metode K-Means-ACO dilakukan pengujian nilai fitness dan nilai kekompakan kelompok dengan menggunakan silhouette coeffisient, sehingga metode K-Means-ACO dapat diterapkan untuk mengelompokan biji wijen berdasarkan sifat warna cangkang


bijinya. Metode K-Means-ACO dapat digunakan sebagai metode kuantitatif alternatif lain dalam mengelompokan biji wijen berdasarkan sifat warna cangkang biji. 2. Hasil pengelompokkan dengan metode KMeans-ACO sama dengan hasil penelitian sebelumnya yang menggunakan metode IWOKM, PSOKM dan GAKM yaitu 233:58. Nilai parameter optimal yaitu dengan jumlah koloni sebanyak 300, standar deviasi awal bernilai 1, standar deviasi akhir bernilai 0,001, dan limit sebanyak 15. Sedangkan hasil pengelompokan dengan metode pada penelitian Adikadarsih tidak jauh berbeda yaitu 237:54 untuk metode kualitatif dan 231:60 untuk metode kuantitatif. 3. Berdasarkan hasil pengujian perbandingan metode K-Means-ACO dengan metode KMeans menunjukkan bahwa metode KMeans-ACO lebih baik dalam mengelompokan biji wijen. Hal ini dibuktikan dengan rata–rata nilai fitness pada metode K-Means-ACO mencapai 10,1469 sedangkan pada K-Means mencapai 10,4262. Selain itu juga dibuktikan dengan rata–rata nilai kekompakan kelompok pada metode KMeans-ACO mencapai 0,7715, sedangkan pada K-Means hanya mencapai 0,7660. 4. Berdasarkan hasil pengujian perbandingan metode K-Means-ACO dengan metode sebelumnya yaitu IWOKM, PSOKM dan GAKM menunjukkan bahwa metode KMeans-ACO lebih baik dari pada metode PSO-KM dan GAKM namun hanya memiliki selisih sangat kecil dibanding metode IWOKM. Berikut rata–rata nilai fitness K-Means-ACO mencapai 10,1469 dengan nilai kekompakan kelompok mencapai 0,7715. Sedangkan metode IWOKM rata–rata nilai fitness mencapai 10,1461 dan nilai kekompakan kelompok mencapai 0,7714. Metode GAKM untuk rata – rata nilai fitness sebesar 10,2084 dan nilai kekompakan kelompok sebesar 0,7701. Metode PSOKM untuk rata – rata nilai fitness hanya mencapai 10,4136 dan nilai kekompakan kelompok hanya mencapai 0,7686. Berdasarkan hasil penelitian untuk pengelompokan biji wijen berdasarkan sifat warna cangkang biji menggunakan metode KMeans-ACO terbukti bahwa metode ini dapat Fakultas Ilmu Komputer, Universitas Brawijaya

1665

menghasilkan proses pengelompokan yang optimal sehingga metode K-Means-ACO dapat digunakan pada data lain untuk proses pengelompokan data dengan kemungkinan hasil yang lebih baik jika dibandingkan dengan menggunakan metode K-Means saja. Pada penelitian selanjutnya dapat menggunakan metode pengelompokan yang lain, sehingga bisa mendapatkan metode yang lebih baik lagi untuk pengelompokan biji wijen berdasarkan sifat warna cangkang biji. 8.

DAFTAR PUSTAKA

Adikadarsih, S., 2015. Pewarisan SIfat Warna Cangkang Biji Pada Persilangan Wijen (Sesamum Indicum) Kultivar 'SBR2' x 'SBR3' dan 'SBR3' x Turki 'Det 36'. Devi, A. P., 2017. Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode PSO – KMeans. Ding, C., 2005. K-Means Clustering via Principal Component Analysis. El Khier, M. I. K. &. Y. A. E. A., 2008. Chemical Composition and Oil Characteristics of Sesame Seed Cultivars Grown in Sudan. pp. 761-766. Gan, G. M. C. W. J., 2007. Dalam: Data Clustering : Theory, Algorithm, and Application. Pennsylvania: SIAM (Society for Industrial and Applied Mathematic. Gnanapriya, S. a. R. S., 2013. International Journal of Enginerring Reserach and Science & Technology (IJERST). Initialization K-Means Using Ant Colony Optimization, 2 May.Volume 2. Hamerly, G. C. E., 2002. Alternative to the Kmeans Algorithm that Find Better Clusterings. 4-9 November, Volume 2, p. 600. Handayani, S., 2002. Studi Pendahuluan Karakteristik Produk Berbahan Baku Wijen. s.l., Seminar Nasional PATPL. Laurentin, H. a. T. B., 2014. Inheritance of Seed Coat Color in Sesame. Volume 49, p. 290. Maulida, H., 2017. Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode PSO – KMeans.


Robbani, I. H., 2017. Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji dengan Menggunakan Metode IWOKM. Xu, S. Z. B. Y. L. L. S. &. G. L., 2010. Hyperspectal Image Clustering Using Ant Colony Optimization (ACO) Improved by K-Means Algorithm. Zhang, H. e. a., 2013. Genetic Analysis and QTL Mapping of Seed Coat Color in Sesame (Sesamum Indicium L.).

Fakultas Ilmu Komputer, Universitas Brawijaya

1666

Penerapan Metode K-Means-ACO Untuk Pengelompokan Biji Wijen Berdasarkan Sifat Warna Cangkang Biji

Recommend Documents