ANALISIS KLASTER MENGGUNAKAN ALGORITMA CHAMELEON

Fasya Nabila Ramadhani, Prof. Drs. Subanar, Ph.D.

2019 | Skripsi | S1 STATISTIKA

Analisis klaster metode hierarki memulai pengelompokan dengan dua atau lebih objek yang mempunyai kesamaan paling dekat hingga klaster akan membentuk semacam pohon dimana terdapat tingkatan (hierarki) yang jelas antar objek, dari yang paling mirip hingga yang paling tidak mirip. Namun, metode hierarki sebelumnya seperti CURE dan ROCK memiliki kekurangan utama dalam hal penggabungan pasangan klaster yaitu hanya mempertimbangkan salah satu di antara informasi interconnectivity atau closeness, Oleh karena itu, dalam penelitian ini akan dibahas mengenai algoritma CHAMELEON yaitu metode analisis klaster hierarki berdasarkan model dinamis yang menggunakan kedua informasi tersebut. Algoritma CHAMELEON menggunakan pendekatan algoritma k-nearest neighbor graph yang kemudian graf dipartisi menggunakan library METIS untuk mendapatkan initial sub-cluster. Selanjutnya digunakan algoritma analisis klaster hierarki agglomerative untuk menemukan klaster akhir dengan berulang kali menggabungkankan nilai relative interconnectivity dan relative closeness dari klaster-klaster yang sebelumnya terbentuk. Untuk mengetahui kualitas dan validitas dari klaster, digunakan validasi internal silhouette width.

Hierarchical clustering starts grouping with two or more objects that have the closest similarity so that the cluster will form a tree where there are clear levels (hierarchy) between objects, from the most similar to the least similar. But the existing hierarchical clustering algorithms like CURE and ROCK have a major disadvantage when it comes to combining cluster pairs, they only consider one of the interconnectivity or closeness information. Therefore, in this work we will discuss the CHAMELEON algorithm which is a hierarchical clustering using dynamic modeling that uses both information. CHAMELEON algorithm uses the k-nearest neighbor graph algorithm approach which is then partitioned using the METIS library to get the initial sub-cluster. Then the agglomerative hierarchical clustering algorithm is used to find the final cluster by repeatedly combining the value of relative interconnectivity and relative closeness of the clusters that were previously formed. To determine the quality and validity of the cluster, internal validation silhouette width was used.

Kata Kunci : analisis klaster, klaster hierarki, model dinamis, algoritma chameleon, k-nearest neighbor graph, METIS, interconnectivity, closeness , silhouette width