Penentuan Titik Pusat Awal Klaster Pada Algoritma K-Means Menggunakan Titik Representasi Berbasis Kepadatan

Lestari, Citra (2008) Penentuan Titik Pusat Awal Klaster Pada Algoritma K-Means Menggunakan Titik Representasi Berbasis Kepadatan. Masters thesis, Institut Teknologi Sepuluh Nopember Surabaya.

Text 5105201012-Master_Thesis.pdf - Accepted Version Download (7MB)

Abstract

Algoritma k-Means melakukan klasterisasi dengan meletakkan titik data ke dalam klaster yang titik pusatnya berjarak terdekat. Karenanya, kualitas algoritma k-Means sangat bergantung pada pemilihan k titik pusat awal klaster. Telah banyak penelitian dilakukan untuk memperbaiki akurasi atau kecepatan algoritma k-Means. Salah satunya adalah algoritma k-Means sederhana yang membagi set data menjadi beberapa blok per dimensi dan merepresentasikannya dalam sebuah titik representasi. Cara tersebut memang sederhana dan cepat, namun dapat mengakibatkan hilangnya korelasi antar dimensi dalam set data. Titik representasi dalam algoritma penelitian ini dibuat dengan pendekatan berbasis kepadatan. Awalnya algoritma mencari titik inti dalam set data, lalu mengelompokkan titik-titik inti yang berjangkauan kepadatan satu sama lain kedalam sebuah grup. Setiap grup diwakili oleh titik representasi yang berada di tengah-tengah grup. Algoritma kemudian melakukan klasterisasi berbasis k-Means pada titik-titik representasi untuk menentukan titik pusat awal klaster. Karena titik representasi mewakili titik inti dan berada di tengah-tengah titik inti, maka besar kemungkinan titik pusat awal klaster yang dihasilkan telah berada di tengah klaster. Titik pusat awal kalster itu digunakan untuk klasterisasi semua titik data. Hasil uji coba menunjukkan bahwa kinerja algoritma dalam penelitian ini bergantung pada batas kepadatan. Hasil kinerja optimal diperoleh pada saat beberapa set data dalam uji coba diberikan batas kepadatan 4 dan 17. Untuk penentuan kedua batas kesalahan ini dihasilkan kesalahan klasterisasi yang relatif rendah dan waktu komputasi yang relatif cepat. Selain itu algoritma yang dikembangkan dalam penelitian ini juga memberikan akurasi klasterisasi yang lebih tinggi daripada algoritma pembandingnya
=====================================================================================================================================
The k-Means algorithm performs clustering by placing data points into clusters whose centers are the closest. Therefore, the quality of the k-Means algorithm is highly dependent on the selection of k initial cluster center points. A lot of research has been carried out to improve the accuracy or speed of the k-Means algorithm. One of them is a simple k-Means algorithm that divides the data set into blocks per dimension and represent it in a point representation. This method is simple and fast, but can result in loss of correlation between dimensions in the data set. The representation points in this research algorithm are created using a density-based approach. Initially, the algorithm looks for core points in the data set, then groups core points within a density range of each other into a group. Each group is represented by a representation point in the middle of the group. The algorithm then performs k-Means based clustering on the representation points to determine the initial center point of the cluster. Because the representation point represents the core point and is in the middle of the core point, it is very likely that the initial center point of the resulting cluster is in the middle of the cluster. The initial center point of the cluster is used for clustering all data points. The test results show that the performance of the algorithm in this study depends on the density limit. Optimal performance results were obtained when several data sets in the trial were given density limits of 4 and 17. Determining these two error limits resulted in relatively low clustering errors and relatively fast computing times. Apart from that, the algorithm developed in this research also provides higher clustering accuracy than the comparison algorithm

Item Type:	Thesis (Masters)
Additional Information:	RTIf 005.1 Les p-1 2008
Uncontrolled Keywords:	k-Means, titik pusat klaster, titik representasi berbasis kepadatan, titik inti; k-Means, cluster center point, point based representation density, core point
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Information Technology > Informatics Engineering > 55101-(S2) Master Thesis
Depositing User:	EKO BUDI RAHARJO
Date Deposited:	01 Jul 2024 03:49
Last Modified:	01 Jul 2024 03:49
URI:	http://repository.its.ac.id/id/eprint/108095

Actions (login required)

View Item