Document Clustering Algorithm

Untuk melakukan proses clustering pada document, bisa digunakan beberapa metode clustering yang telah umum digunakan seperti k-means clustering algorithm, atau variasinya: bisecting k-means, dan hierarchical clustering algorithm, baik Agglomerative atau Divisive.

Dalam melakukan proses clustering, perbandingan kesamaan (similarity) juga perlu diukur. Dalam kegiatan Document Clustering similarity measure yang banyak digunakan adalah cosine measure yang didefinisikan sebagai berikut:

cosine (d1, d2) = (d1 . d2) / (||d1|| ||d2||)

dimana . adalah vector dot product dan ||d|| adalah panjang dari vector d.

Untuk menghitung centroid dari cluster digunakan rumus berikut ini:

c = 1/|S| sum_(d in S) d

yang tidak lain merupakan vector yang didapatkan dengan merata-ratakan weight dari berbagai macam terms yang ada di dalam dokumen S.

Goodness of fit dalam document clustering yang menggunakan cosine sebagai similarity measure adalah sebagai berikut:

1/|S|^2 sum_(d in S, d’ in S) cosine (d’, d) = ||c||^2

Untuk mengukur kualitas cluster dapat digunakan
1. Entropy: memanfaatkan probabilitas dari cluster yang terbentuk yang dihitung dengan rumus E_j = – sum_i p_(ij) log p_(ij) dimana p_(ij) adalah probabilitas suatu anggota di cluster j untuk masuk ke cluster i.
2. F Measure: memanfaatkan ide presisi dan recall, dimana recall(i,j) = n_ij/n_i dan precision(i,j) = n_(ij)/n_j. n adalah jumlah anggota cluster. F Measure dihitung dengan rumus F(i,j) = (2 * recall(i,j) * precision(i,j)) / ((precision(i,j) + recall(i,j)).

Referensi:
Michael Steinbach, George Karypis, dan Vipin Kumar (2000). A Comparison of Document Clustering Techniques. Technical Report #00-034, Department of Computer Science and Engineering, University of Minnesota.