Kajian Algoritma Optimasi K-Means untuk Meningkatkan Kualitas Cluster pada Data Sparse

Abstract

Perkembangan teknologi menyebabkan peningkatan jumlah data teks digital secara eksponensial. Analisis data teks penting untuk mengoptimalkan strategi dalam berbagai aspek. Text mining merupakan suatu teknik yang digunakan untuk mengekstrak informasi dari data tidak terstruktur, seperti email, media sosial, dan kumpulan ulasan. Text clustering adalah salah satu tugas dalam text mining yang memudahkan pemahaman informasi dengan mengelompokkan teks berdasarkan topik. Algoritma yang sering digunakan dalam text clustering adalah K-Means. Algoritma ini mensyaratkan pengguna untuk menentukan terlebih dahulu jumlah cluster yang akan dibentuk, namun terkadang penentuannya sulit untuk dipahami. Algoritma K-Means juga memiliki kelemahan yaitu hasil pengelompokannya sangat sensitif terhadap pemilihan centroid awal. Beberapa penelitian telah menggunakan algoritma optimasi K-Means untuk mengatasi permasalahan tersebut, diantaranya yaitu DB-Kmeans dan PSO-Kmeans. DB-Kmeans menggabungkan Density-Based Spatial Clustering of Application with Noise (DBSCAN) dan K-Means untuk memaksimalkan pemilihan centroid awal, sedangkan PSO-Kmeans menggunakan Particle Swarm Optimization (PSO) untuk mengoptimalkan pusat cluster (centroid). Penelitian ini mengimplementasikan algoritma optimasi K-Means untuk mengelompokkan data teks digital berupa kumpulan ulasan game Citampi Stories di Google Play Store. Ulasan ini dianalisis untuk memahami tanggapan pengguna dan membantu pengembang meningkatkan kualitas game. Penelitian berfokus pada pengelompokan dokumen teks pendek, yang menimbulkan masalah data sparse atau sparsitas. Data sparse mengacu pada kondisi di mana document-term-matrix yang digunakan untuk mewakili dokumen teks pendek berdasarkan kata-kata di dalamnya, memiliki banyak entri yang bernilai nol. Pengelompokan pada data sparse memperoleh hasil yang tumpang tindih dan tidak efektif. Pendekatan yang digunakan dalam penelitian ini adalah membagi data ulasan berdasarkan jumlah term untuk mengatasi masalah sparsitas dan memaksimalkan identifikasi topik dari hasil pengelompokan. Penelitian ini juga menggunakan algoritma optimasi K-Means pada data sparse sebagai pembanding, yaitu Robust Sparse Kmeans Clustering (RSKC). Penelitian ini bertujuan untuk mengevaluasi algoritma DB-Kmeans, PSO-Kmeans, dan RSKC untuk pengelompokan data teks digital serta mengatasi tantangan yang terkait dengan pengelompokan data sparse. Dua jenis data digunakan untuk menjawab tujuan penelitian ini, yaitu data simulasi dan data empiris. Hasil kajian simulasi menunjukkan DB-Kmeans memiliki performa yang lebih baik dalam mengelompokkan data dengan tingkat sparsitas rendah (5%), namun performanya cenderung lebih rendah dan setara dengan algoritma lainnya ketika sparsitas mencapai 10% atau lebih tinggi. Sparsitas pada data dapat mengurangi keunikan antar cluster, sehingga algoritma kesulitan membedakan cluster yang sebenarnya. Data empiris yang digunakan adalah ulasan game Citampi Stories yang kemudian dilakukan text preprocessing. Hasil preprocessing, selanjutnya dieksplorasi untuk memeriksa banyaknya ulasan yang memiliki jumlah term yang sama. Terdapat 35.000 ulasan yang memiliki kurang dari 10 term, yang akan menghasilkan data yang jarang (data sparse) ketika diubah menjadi bentuk document-term-matrix dengan tingkat sparsitas 98,46%. Penelitian ini menggunakan pendekatan dengan membagi data ulasan menjadi 3 skenario berikut. Skenario 1: semua data ulasan (Dataset 1), Skenario 2: data ulasan dibagi menjadi 2 dataset yaitu data dengan 10 term atau kurang (Dataset 2) dan data dengan lebih dari 10 term (Dataset 3), dan Skenario 3: data ulasan dibagi menjadi 2 dataset yaitu data dengan 15 term atau kurang (Dataset 4) dan data dengan lebih dari 15 term (Dataset 5). Data pada setiap skenario diubah menjadi document-term-matrix yang memuat bobot TF-IDF dari setiap term dan menjadi input untuk algoritma optimasi K-Means. Ketiga algoritma optimasi yang digunakan dievaluasi dengan melihat silhouette score yang dihasilkan, dengan K-Means dan DBSCAN sebagai pembanding. Hasil penerapan pada data empiris menunjukkan bahwa algoritma optimasi K-Means memiliki kinerja pengelompokan yang lebih baik dibandingkan K-Means dan DBSCN. Algoritma optimasi K-Means yang digunakan berhasil memperoleh silhouette score yang lebih tinggi pada beberapa dataset, yang menunjukkan kemampuannya dalam meningkatkan kualitas pengelompokan. DB-Kmeans berkinerja sangat baik karena mencapai silhouette score tertinggi pada tiga dataset dan PSO-Kmeans mencapai silhouette score tertinggi pada dua dataset. Temuan ini sejalan dengan hasil kajian simulasi yang menunjukkan bahwa performa ketiga algoritma optimasi tersebut cenderung sama baiknya, pada pengelompokkan data dengan tingkat sparsitas 10% atau lebih tinggi. Hasil pengelompokan menggunakan algoritma terbaik pada setiap dataset kemudian divisualisasikan menggunkan wordcloud untuk mengidentifikasi topik yang terbentuk. Pendekatan yang digunakan dengan membagi data berdasarkan jumlah term dapat menjadi solusi untuk pengelompokan data sparse, karena dapat menurunkan tingkat sparsitas pada data dan secara signifikan mempengaruhi optimalisasi pembentukan topik dalam setiap cluster. Skenario 2 dan Skenario 3 berhasil membentuk topik-topik yang lebih beragam dibandingkan dengan Skenario 1. Hal ini memberikan wawasan yang lebih dalam mengenai apa yang sebenarnya diinginkan oleh pengguna serta membantu dalam pengambilan keputusan untuk pengembangan fitur dan peningkatan kualitas game. Pendekatan yang digunakan pada penelitian ini tidak sepenuhnya mengatasi masalah sparsitas namun telah mampu menurunkan dampaknya, walaupun secara visualisasi masih terjadi tumpang tindih antar cluster. Hal ini juga terlihat dari silhouette score pada pengelompokan setiap dataset memperoleh nilai mendekati 0, yang mengindikasikan adanya tumpang tindih antar cluster.

The rapid development of technology has led to an exponential increase in the amount of digital text data. Text data analysis is important for optimizing strategies in various aspects. Text mining is a technique used to extract information from unstructured data, such as emails, social media, and collections of reviews. Text clustering is one of the tasks in text mining that facilitates the understanding of information by grouping texts based on topics. The algorithm that is often used in text clustering is K-Means. This algorithm requires users to first determine the number of clusters to be formed; however, sometimes this determination is difficult to understand. The K-Means algorithm also has the disadvantage that the clustering results are very sensitive to the selection of the initial centroid. Several studies have used K-Means optimization algorithms to address these issues, including DB-Kmeans and PSO-Kmeans. DB-Kmeans combines the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and K-Means to maximize the selection of initial centroids, while PSO-Kmeans uses Particle Swarm Optimization (PSO) to optimize the cluster center (centroid). This research implements the K-Means optimization algorithm to cluster digital text data in the form of a collection of Citampi Stories game reviews on the Google Play Store. These reviews are analyzed to understand user feedback and help developers improve the game's quality. The research focuses on clustering short text documents, which poses the problem of sparse data or sparsity. Sparse data refers to a condition where the document-term matrix used to represent short text documents based on their words contains many entries with zero values. Clustering on sparse data produces overlapping and ineffective results. The approach used in this research is to split the reviews data based on the number of terms to overcome sparsity and maximize topic identification from the clustering results. This research also uses the K-Means optimization algorithm on sparse data as a comparison, namely Robust Sparse K-Means Clustering (RSKC). This research aims to evaluate the DB-Kmeans, PSO-Kmeans, and RSKC algorithms for clustering digital text data and addressing the challenges associated with clustering sparse data. Two types of data are used to answer the objectives of this research, namely simulated data and empirical data. The results of the simulation study show that DB-Kmeans performs better in clustering data with low sparsity level (5%), but its performance tends to decrease and becomes comparable to the other algorithms when sparsity reaches 10% or higher. Sparsity in the data can reduce the uniqueness between clusters, making it difficult for the algorithm to distinguish actual clusters. The empirical data used is reviews of the game Citampi Stories, which underwent text preprocessing. The preprocessing result are then explored to examine how many reviews had the same number of terms. There are 35.000 reviews with fewer than 10 terms, which would produce sparse data when converted into a document-term matrix with a sparsity level of 98,46%. This research employs an approach by dividing the reviews data based on the number of terms in the following scenarios. Scenario 1: all reviews data (Dataset 1), Scenario 2: reviews data divided into 2 datasets, namely data with 10 terms or fewer (Dataset 2) and data with more than 10 terms (Dataset 3), and Scenario 3: reviews data divided into 2 datasets, namely data with 15 terms or fewer (Dataset 4) and data with more than 15 terms (Dataset 5). The data in each scenario is converted into a document-term matrix containing TF-IDF weights of each term and used as input for the K-Means optimization algorithms. The three optimization algorithms are evaluated by examining the resulting silhouette score, with K-Means and DBSCAN as comparisons. The results on the empirical data show that the K-Means optimization algorithms perform better than K-Means and DBSCAN. The K-Means optimization algorithms produced higher silhouette scores on several datasets, demonstrating their ability to improve clustering quality. DB-Kmeans performed very well by achieving the highest silhouette score on three datasets, and PSO-Kmeans achieved the highest silhouette score on two datasets. This finding is in line with the simulation study results which show that the performance of the three optimization algorithms tends to be equally good, when clustering data with a sparsity level of 10% or higher. The clustering results using the best algorithm on each dataset were then visualized using wordcloud to identify the topics formed. The approach used by dividing the data based on the number of terms can be a solution for clustering sparse data, as it can reduce the level of sparsity in the data and significantly impact the optimization of topic formation in each clusters. Scenario 2 and Scenario 3 successfully formed more diverse topics compared to Scenario 1. This provides deeper insights into what users actually want and helps in decision-making for feature development and game quality improvement. The approach used in this research does not completely solve the problem of sparsity but has been able to reduce its impact, although visually there is still overlap between clusters. This is also reflected in the silhouette score on the clustering each dataset, which obtained values close to 0, indicating the presence of overlap between clusters.