Perpustakaan Digital ITB

Algoritma HMRF-KMeans telah memenuhi beberapa syarat document clustering yaitu mampu menangani data berdimensi tinggi, memenuhi aspek scalability, mencapai keakuratan yang lebih baik daripada algoritma KMeans, dan tidak tergantung terhadap pengetahuan awal. Sedangkan syarat yang belum dipenuhi adalah deskripsi cluster yang mempunyai arti dan representasi data yang mempertimbangkan urutan kata. Kedua syarat ini dipenuhi dengan pemakaian data yang diproses dengan mempertimbangkan aspek sequence. Algoritma HMRF-KMeans terdiri dari langkah inisialisasi, expectation, dan maximization. Langkah inisialisasi bertujuan menemukan centroid awal yang bagus. Di langkah expectation, setiap titik x ditetapkan ke cluster yang menurunkan kontribusi titik tersebut terhadap fungsi objektif. Di langkah maximization, centroid tersebut dihitung ulang berdasarkan hasil penetapan cluster di langkah expectation untuk menurunkan fungsi objektif. Selain itu parameter distance measure dihitung ulang untuk mereduksi fungsi objektif. Langkah E dan M dilakukan berulang kali sampai konvergen. Hal-hal yang dikembangkan terkait penerapan algoritma HMRF-KMeans untuk document clustering adalah penggunaan representasi n-gram, pengurangan dimensi, penggunaan cosine distance measure, dan pelabelan cluster menggunakan metode IGm. Hasil eksperimen menunjukkan bahwa pada representasi n-gram, pemakaian representasi 1-gram, 2-gram, 3-gram, dan 4-gram pada clustering menghasilkan cluster dengan perbedaan keakuratan yang tidak signifikan. Hal ini disebabkan dominasi 1-gram terhadap n-gram lainnya pada setiap representasi. Clustering dengan constraint menghasilkan cluster yang lebih akurat daripada clustering tanpa constraint, dan label yang dibentuk dengan representasi 1-gram mempunyai kualitas paling bagus, diikuti label yang dibentuk dengan representasi 2-gram, 3-gram, dan 4-gram. Pada algoritma HMRF-KMeans, pemakaian representasi 1-gram pada clustering menghasilkan cluster yang paling akurat dan label paling berkualitas daripada pemakaian representasi n-gram lainnya.