Parallel Local Triangular Kernel Clustering Menggunakan CUDA Untuk Data Dimensi Tinggi

SALIM ABDI FITRI, Aina Musdholifah, S.Kom., M.Kom., Ph.D.

2017 | Tesis | S2 Ilmu Komputer

Pengelompokan adalah tugas membagi titik ke dalam kelompok alami yang disebut cluster sehingga titik dalam suatu kelompok sangat mirip, sedangkan titik di kelompok yang berbeda memiliki ketidakmiripan sejauh mungkin. Sejumlah algoritme pengelompokan kesulitan dalam mengelompokan data dimensi tinggi. Local Triangular Kernel Clustering (LTKC) telah terbukti mampu mengatasi kekurangan dalam pengelompokan data dimensi tinggi. LTKC merupakan algoritme pengelompokan berbasis kepadatan (density-based) yang menentukan kepadatan data menggunakan kombinasi dari dua prosedur estimasi kepadatan tanpa parameter. Kecenderungan estimasi kepadatan (kernel density estimation) pada umumnya memerlukan waktu komputasi yang tinggi (time consuming). Disisi lain guna mendapatkan hasil k yang optimal, algoritme LTKC dijalankan berulang menggunakan nilai k yang berbeda, dengan menjalankan algoritme LTKC sekali untuk tiap nilai k dari 2 ke n-1. Penelitian bertujuan untuk mengelompokan data dimensi tinggi dengan algoritme Local Triangular Kernel Clustering (LTKC) secara paralel dengan CUDA. Algoritme LTKC diaplikasikan secara paralel menggunakan CUDA untuk tiap dataset yang digunakan. Pekerjaan yang dilakukan dibagi menjadi proses nomalisasi, hitung jarak, pencarian k tetangga terdekat, proses kepadatan Triangular Kernel, perhitungan Silhouette Coefficient, perhitungan Dunn Index. Semua data diproses dalam bentuk matriks dan karena terbatasnya kapasitas memory pada device proses pekerjaan dibagi menjadi 8 tahap dengan rentang k sebesar 128 tiap tahapnya. Hasil penelitian Algoritme LTKC yang dijalankan secara paralel dengan CUDA dengan nilai k antara 2 sampai dengan n-1 mampu meningkatkan kinerja pengelompokan dalam hal kecepatan sebesar 5,9X dibandingkan algoritme LTKC yang dijalankan secara serial.

Clustering is the task of dividing point into natural groups called clusters so that the points in a group are very similiar, whereas the points in different groups have dissimilarity as much as possible. A number of clustering algorithms have difficulty in clustering high dimensional data. Local Triangular Kernel Clustering (LTKC) has been shown to overcome the deficiencies in clustering high dimensional data. LTKC is a density-based clustering algorithm that determines data density using a combination of two density estimation method with no parameters. The tendency kernel density estimation in general requires a high computation time. On the other hand in order to obtain optimal k results, LTKC algorithms are run repeatedly using different k values, by running the LTKC algorithm once for each k value from 2 to n-1. The study aims to cluster high-dimensional data with Local Triangular Kernel Clustering (LTKC) algorithm in parallel with CUDA. The LTKC algorithm is applied in parallel using CUDA for each dataset used. The work is divided into normalized, calculate the distance, find k nearest neighbor, Triangular Kernel process, Silhouette Coefficient & Dunn Index calculation. All data is processed in matrix form and due to limited memory capacity in device the work process is divided into 8 stages with k range of 128 for each step. The results of LTKC algorithms run in parallel with CUDA with k values of 2 to n-1 were able to improve the clustering performance in terms of speed by 5.9X compared to the serial-run LTKC algorithm.

Kata Kunci : Pengelompokan, Data Dimensi Tinggi, Local Triangular Kernel Clustering, Parallel, CUDA