Document Clustering Algorithm

20 09 2011

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.


Actions

Information

8 responses

24 12 2012
ilkom

pak, saya mau bertanya bagaimana menurut anda menggunakan kmeans yang dioptimasi dengan algoritma genetika untuk klasterisasi dokumen?
apakah analisis tersebut layak kira2 untuk dijadikan topik TA?
apakah hal tersebut sudah umum?
trimakasih pak.

26 02 2014
Yudi Agusta

Ya bisa dengan GA untuk menentukan model clustering khususnya untuk pemodelan jumlah cluster. Regards,

13 04 2012
salsabila

Assalamu’alaikum
pak,,ada contoh script untuk algoritma k-means nya ??

26 02 2014
Yudi Agusta

Mmm saya tidak banyak mendiskusikan coding lebih ke teori saja untuk bisa dimengerti

5 03 2012
limtien

pak clustering untuk mencari kesamaan dari pembeli itu apa ya?

jadi nanti jika pembeli A membeli suatu barang, maka dia akan mendapatkan rekomendasi orang-orang yang membeli barang yang setipe dengan dia sehingga dia bisa mengajak orang tersebut untuk membeli barang yang sama

26 02 2014
Yudi Agusta

Yang paling sederhana bisa menggunaka metode k-means clustering.

Regards,

10 10 2011
Affandy Achmad

pak yudi, saya mau tanya,
kalo clustering text menggunakan k-harmic means apa memungkinkan?
apa sebenarnya pengertian harmonic itu pak?tolong bantuannya pak.

11 10 2011
Yudi Agusta

Memungkinkan apabila tipe variabel dari masing-masing data text itu adalah data buka categorical.

Harmonic merupakan istilah yang dipakai untuk merepresentasikan agar data dalam satu kelompok tidak terlalu dipengaruhi oleh data di sekitarnya yang masuk dalam kelompok yang lain, dengan memberikan weight pada masing-masing data.

Baca tulisan saya tentang k-harmonic di https://yudiagusta.wordpress.com/k-means/

Semoga menjawab.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: