PRESENTASI TUGAS AKHIR – KI091391 IMPLEMENTASI KD-TREE K-MEANS CLUSTERING PADA KLASTERISASI DOKUMEN (Kata kunci: KD-Tree K-Means Clustering, Klasterisasi Dokumen, KDimensional Tree, K-Means Clustering)
Penyusun Tugas Akhir :
Eric Budiman Gosno (NRP : 5109.100.153) Dosen Pembimbing :
Isye Arieshanti, S.Kom, M.Phil. Rully Soelaiman, S.Kom., M.Kom. 26 Juli 2013
Tugas Akhir – KI091391
1
TAHAPAN PRESENTASI
Pendahuluan
Latar Belakang
Rumusan Masalah Sistem Klasterisasi Dokumen Batasan Masalah
Uji Coba Tujuan
Kesimpulan dan Saran
10 Juli 2013
Tugas Akhir - KI091391
2
LATAR BELAKANG
K-Means Clustering sensitif terhadap inisialisasi posisi titik tengah klaster. Inisialisasi posisi titik tengah yang buruk akan algoritma K-Means Clustering menghasilkan solusi local optimum. KD-Tree K-Means Clustering adalah perbaikan dari metode KMeans Clustering dengan inisialisasi titik tengah klaster menggunakan struktur data K-Dimensional Tree dan nilai kerapatan/density Hasil evaluasi oleh Redmond et al tidak melingkupi performa KDTree K-Means Clustering pada data set dokumen.
26 Juli 2013
Tugas Akhir – KI091391
3
RUMUSAN MASALAH
1. Bagaimana mengimplementasikan algoritma KD-Tree K-Means Clustering pada kasus klasterisasi dokumen? 2. Bagaimana hasil dan performa dari algoritma KD-Tree K-Means Clustering dibandingkan dengan metode K-Means Clustering pada kasus klasterisasi dokumen?
26 Juli 2013
Tugas Akhir – KI091391
4
BATASAN MASALAH
1. Data set yang digunakan untuk uji performa implementasi pada klasterisasi non dokumen adalah data set Pen-Based Recognition of Handwritten Digits(http://archive.ics.uci.edu/ml/datasets/PenBased+Recognition+of+Handwritten+Digits) dan data set Image Segmentation (http://archive.ics.uci.edu/ml/datasets/Image+Segmentation) dari UCI Machine Learning Repository. 2. Data set yang digunakan untuk uji performa pada klasterisasi dokumen adalah data set 20 newsgroup dari KDD UCI Archive (http://kdd.ics.uci.edu/databases/20newsgroups/20newsgroups. html) 3. Algoritma yang digunakan sebagai perbandingan performa KDTree K-Means pada klasterisasi dokumen adalah K-Means Clustering dengan inisialisasi Forgy’s Method 26 Juli 2013
Tugas Akhir – KI091391
5
BATASAN MASALAH
4. Parameter evaluasi yang digunakan adalah distorsi euclidean distance dan Normalized Information Gain 5. Metode stemmer yang digunakan pada pra proses dokumen adalah porter stemmer
26 Juli 2013
Tugas Akhir – KI091391
6
TUJUAN
1. Mengimplementasikan algoritma KD-Tree K-Means Clustering dalam permasalahan klasterisasi dokumen. 2. Melakukan uji performa dari algoritma KD-Tree K-Means Clustering dalam permasalahan klasterisasi dokumen.
26 Juli 2013
Tugas Akhir – KI091391
7
TAHAPAN PRESENTASI
Gambaran umum sistem
Pendahuluan Alur Sistem Klasterisasi Dokumen
Sistem Klasterisasi Dokumen
Tahap Pra Proses
K-Dimensional Tree
Uji Coba KD-Tree K-Means Clustering
Kesimpulan dan Saran
10 Juli 2013
Tugas Akhir - KI091391
8
GAMBARAN UMUM SISTEM
Data set Kumpulan Dokumen / Artikel
26 Juli 2013
Dokumen-dokumen yang telah diklasterisasi
Tugas Akhir – KI091391
9
ALUR SISTEM KLASTERISASI DOKUMEN
Tahap Pra-Proses Dokumen
Data set Kumpulan Dokumen / Artikel
Data set dengan format bag of word
Proses Klasterisasi Dokumen
Input data set & Term Weighting
Dokumen-dokumen yang telah diklasterisasi 26 Juli 2013
Tugas Akhir – KI091391
10
Tahap Pra – Proses Dokumen Menyederhanakan kata ke Menghapus kata Hasil bagyang of word Hapusdata kataset yang hanya muncul dalam merupakan stop word dalam Pada satu dokumen Bentuk stem Bahasa Inggris
Data set Kumpulan Dokumen / Artikel
Data set dengan format bag of word
Penghapusan stop word
Proses Stemmming kata
26 Juli 2013
Proses seleksi kata typo Tugas Akhir – KI091391
11
Proses pembobotan kata (term weighting)
Bertujuan untuk memberikan bobot penilaian pada setiap kata yang menjadi fitur Menggunakan perhitungan Term Document Frequency (TF-IDF)
26 Juli 2013
Tugas Akhir – KI091391
Frequency
–
Inverse
12
Proses pembobotan kata (term weighting)
Data set setelah term weighting
Data set sebelum term weighting
26 Juli 2013
Tugas Akhir – KI091391
13
K-Dimensional Tree
Data struktur yang bersifat space-partitioning dan merupakan kasus spesial dari binary space partitioning tree Setiap node non-leaf pada KD-Tree merupakan garis yang memisakan sebuah ruang menjadi 2 bagian Menggunakan nilai median atau mean sebagai nilai pivot
26 Juli 2013
Tugas Akhir – KI091391
14
K-Dimensional Tree
Pemilihan atribut pemisah/pivot
Proses rekursif pada subtree child
tidak Penentuan nilai pemisah/pivot value subtree adalah leaf Pembuatan child subtree kiri dan kanan
Proses pemilihan atribut Child subtree sebelah kiri akan Jika subtree telahmenggunakan memenuhi Pivot Value dapat pemisah: memiliki data dengan nilai kriteria leaf atau (kedalaman tertentu Nilai median mean dari atribut < pivot / jumlah data value. maksimal) Nilai-nilai pada atributSedangkan pemisah Umumnya ditentukan Child subtree Maka fungsi sebelah rekursif kanan selesai berdasarkan kedalaman dari akan memilikilebih datasering dengan nilai Nilai median Jikanode tidak, maka lanjutkan ini atribut > saat pivot value digunakan karena menghasilkan proses child axis rekursif = depth ke mod k subtree tree lebih balance dibandingkan atau node.leftChild := kdtree(points < nilai mean = longest dimension pivotaxis value, depth+1); node.rightChild := kdtree(points > pivot value, depth+1);
ya
Fungsi selesai
26 Juli 2013
Tugas Akhir – KI091391
15
K-Dimensional Tree
Contoh hasil partisi K-Dimensional Tree pada data set 2 dimensi 26 Juli 2013
Tugas Akhir – KI091391
16
KD-Tree K-Means Clustering
Metode K-Means Clustering dengan perbaikan pada proses inisialisasi titik tengah klaster Menggunakan struktur data K-Dimensional Tree dan nilai/ranking kerapatan dari leaf bucket untuk memilih posisi awal titik tengah
Nilai kerapatan
=
(
: Banyak poin pada leaf bucket,
:
Volume area leaf bucket). nilai volume Vj : hasil perkalian dari semua rentang dimensi pada leaf bucket. Dimensi dengan nilai rentang nol akan digantikan dengan nilai geometric mean dari nilai rentang dimensi yang tidak bernilai nol. Leaf bucket yang dipilih sebagai titik tengah adalah leaf bucket yang memiliki jarak terjauh dari titik tengah dan nilai kerapatan tertinggi 26 Juli 2013
Tugas Akhir – KI091391
17
KD-Tree K-Means Clustering
Pembentukan struktur data KD-Tree dari data set
K-Means Clustering dengan hasil inisialisasi titik tengah
Penghapusan 20% Leaf bucket dengan nilai kerapatan terendah dan proses diulang
Perhitungan nilai kerapatan dari setiap leaf bucket
ya Proses pemilihan titik tengah dari leaf bucket
• Untuk talgoritma =leaf 1, pilih titikdengan tengah Jalankan K-Means Hapus 20% bucket Untuk setiap leaf Pembentukan K-Dimensional klaster pertama C1 = ulangi Mz, Clustering dengan nilai nilai kerapatan terendah, bucket(L ,L ,…,L ) , kalkulasi 2 set. Tree dari 1data K- (C ,...,C . k) dimana = tengah argj max inisialisasi titik proses dan kalkulasi posisi 1 K nilai kerapatan(P ) dari setiap j yang dibuat Dimensional Tree dan (ĉ , ĉ ,…, ĉ ). titik tengah klaster (ĉ1, 1 2 k leaf bucket Lj, leaf danbaru kalkulasi akan memiliki bucket Untuk t = 2,…,K: ĉ2•nilai ,…, ĉk). tengah titik leaf maksimal bucket(Mj) dengan jumlah data Untuk j =mencari 1,...,q kalkulasi nilai dengan nilai rerata dari 20 per leaf bucket. ranking leaf bucket (G ) dengan semua point yang adaj pada fomula leaf bucket Lj. , × = = 1… = Pilih titik tengah klaster Ct = Mz, dimana = arg max .
Jumlah titik tengah = Jumlah klaster
tidak 26 Juli 2013
Tugas Akhir – KI091391
18
KD-Tree K-Means Clustering
Nilai
dapat diganti dengan ranking density ( ). Leaf Bucket = 1 dan leaf bucket dengan nilai terendah memiliki nilai dengan nilai tertinggi memiliki nilai = n. Tujuan dari penggunaan ranking density adalah untuk mencegah nilai kerapatan yang terlalu dominan dibandingkan dengan jarak leaf bucket ke titik tengah Tujuan dari menghapus 20% leaf bucket terendah adalah untuk mencegah leaf bucket yang merupakan outlier menjadi titik tengah
26 Juli 2013
Tugas Akhir – KI091391
19
KD-Tree K-Means Clustering
Leaf Bucket Density Rank : 18,409 Density :5 Leaf Bucket Density 18,22 Density :Rank :4
Centroid 1 Distance : 193,28
Centroid 2
Leaf Bucket Density 18,04 Density :Rank :3
Distance : 9,635 min Distance : 9,635
Leaf Bucket Density Rank : 18,00 Density :2
Distance : 9,635 min Distance : 9,635
Leaf Bucket Density Rank : 17,35 Density :1 26 Juli 2013
Centroid 3 Distance : 200,915
Distance : 200,915 Distance : 145,195 min Distance :139,92 Distance : 139,92 Tugas Akhir – KI091391
20
TAHAPAN PRESENTASI
Pendahuluan
Skenario Uji Coba
Evaluasi Performa Sistem Klasterisasi Dokumen Parameter Uji Coba
Uji Coba
Hasil Skenario Uji Coba 1
Hasil Skenario Uji Coba 2
Kesimpulan dan Saran
10 Juli 2013
Tugas Akhir - KI091391
21
SKENARIO UJI COBA
Skenario 1 : Uji coba implementasi KD-Tree K-Means Clustering pada klasterisasi non dokumen menggunakan data set Image Segmentation dan Pen-Based Recognition of Handwritten Digits. Skenario 2 : Uji coba perbandingan hasil klasterisasi dokumen KD-Tree K-Means Clustering dan K-Means Clustering pada data set dokumen 20 newsgroup. Uji coba dilakukan dengan membandingkan performa hasil KDTree K-Means Clustering dengan 15 kali proses K-Means Clustering.
26 Juli 2013
Tugas Akhir – KI091391
22
EVALUASI PERFORMA (1)
Perhitungan menggunakan nilai distorsi euclidean distance (Nilai total kuadrat euclidean distance data ke titik tengah klaster)
D = nilai distorsi data set n = jumlah data pada data set K = jumlah klaster hasil Xi = data ke-i pada data set Cj = klaster ke-j D(…,….) = Perhitungan jarak euclidean distance 26 Juli 2013
Tugas Akhir – KI091391
23
EVALUASI PERFORMA (2)
Perhitungan menggunakan Normalized Information Gain
ENTOTAL : nilai Total Entropy atau rerata informasi yang ada di setiap data pada data set =−
L = Jumlah label pada kelas data set cl = Jumlah data yang memiliki label l pada data set
26 Juli 2013
Tugas Akhir – KI091391
24
EVALUASI PERFORMA (3)
wEN: Rerata informasi data pada setiap klaster, memberikan nilai 0 pada saat semua klaster homogen K =Jumlah klaster nk = Jumlah data pada klaster k n = Jumlah data pada data set Enk : Nilai entropy dari sebuah klaster K =Jumlah label pada kelas data set nk = Jumlah data pada klaster k clk = Jumlah data yang memiliki label l pada klaster k 26 Juli 2013
Tugas Akhir – KI091391
25
PARAMETER UJI COBA (1)
Nama Parameter K m row Dkd Dminfa μfa σfa Nfa>kd
26 Juli 2013
Deskripsi Jumlah klaster pada proses klasterisasi Jumlah fitur pada data set Jumlah data pada data set Nilai distorsi dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering Nilai distorsi minimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Nilai rerata distorsi dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Standar deviasi distorsi dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Jumlah proses klasterisasi dokumen dari 15 kali iterasi menggunakan algoritma K-Means Clustering yang memiliki nilai distorsi lebih baik daripada KD-Tree KMeans Clustering Tugas Akhir – KI091391
26
PARAMETER UJI COBA (2)
Nama Parameter Nfa=kd
Nfa
NIGkd NIGfa Tkd Tminfa Tmaxfa
Ttotalfa
26 Juli 2013
Deskripsi Jumlah proses klasterisasi dokumen dari 15 kali iterasi menggunakan algoritma K-Means Clustering yang memiliki nilai distorsi sama dengan KD-Tree K-Means Clustering Jumlah proses klasterisasi dokumen dari 15 kali iterasi menggunakan algoritma K-Means Clustering yang memiliki nilai distorsi lebih buruk daripada KD-Tree KMeans Clustering Nilai NIG dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering Nilai NIG maksimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Waktu eksekusi dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering Waktu eksekusi minimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Waktu eksekusi maksimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Waktu eksekusi total dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering
Tugas Akhir – KI091391
27
SKENARIO 1 : UJI KINERJA NON-1 HasilKLASTERISASI Uji Coba Skenario DOKUMEN KD-TREE K-MEANS CLUSTERING Parameter K m row Dkd Dminfa μfa σfa Nfa>kd Nfa=kd Nfa
Image Segmentation 7 19 2310 1,40 × 107 1,40 × 107 1,46 × 107 1,82 × 106 4 0 11 0,49 0,55 3876 2884 11535 84645
Hasil KD-Tree K-Means Clustering memiliki nilai NIG 0,06 lebih buruk dibandingkan nilai NIG maksimum K-Means Clustering. Tetapi menghasilkan hasil distorsi sama dengan nilai minimum distorsi dan lebih baik 6 × 105 dibandingkan dengan rerata nilai distorsi KMeans Clustering. Selain itu dari 15 proses K-Means Clustering hanya 4 proses saja yang memiliki nilai distorsi lebih baik dibandingkan hasil dari KD-Tree KMeans Clustering.
Tugas Akhir – KI091391
28
SKENARIO 1 : UJI KINERJA NON-1 HasilKLASTERISASI Uji Coba Skenario DOKUMEN KD-TREE K-MEANS CLUSTERING
Parameter
K m row Dkd Dminfa μfa σfa Nfa>kd Nfa=kd Nfa
Pen-based Recognition Handwritten Digits 10 16 10992 5,01 × 107 5,00 × 107 5,17 × 107 1,27 × 106 2 0 13 0,67 0,69 33497 20449 134524 675462
Hasil KD-Tree K-Means Clustering memiliki nilai NIG 0,02 lebih buruk dibandingkan nilai NIG maksimum K-Means Clustering. Tetapi menghasilkan hasil distorsi lebih baik 1,7 × 106 dibandingkan dengan rerata nilai distorsi KMeans Clustering. Selain itu dari 15 proses K-Means Clustering hanya 2 proses saja yang memiliki nilai distorsi lebih baik dibandingkan hasil dari KD-Tree KMeans Clustering.
Tugas Akhir – KI091391
29
SKENARIO 2 : UJI PERFORMA K-MEANS2 Hasil KD-TREE Uji Coba Skenario CLUSTERING PADA DATA SET DOKUMEN
Parameter K m Dkd Dminfa μfa σfa Nfa>kd Nfa
Nilai 20 20536 4,14 x 107 4,12 x 107 4,17 x 107 3,00 x 105 4 11 0,18 0,09 13295630 2535463 12619237 105325216
Hasil uji coba menunjukkan bahwa hasil klasterisasi dokumen menggunakan KDTree K-Means Clustering memiliki nilai distorsi lebih buruk 2 × 105 dibandingkan nilai distorsi minimum hasil K-Means Clustering. Namun Hasil ini lebih baik 3 × 105 dibandingkan dengan nilai rerata distorsi dari K-Means Clustering. Pada perhitungan nilai NIG, hasil dari KD-Tree K-Means Clustering memiliki nilai NIG 0,18. Hasil ini lebih baik 0,09 dibandingkan dengan nilai NIG maksimum yang didapatkan oleh KMeans Clustering.
TAHAPAN PRESENTASI
Pendahuluan
Sistem Klasterisasi Dokumen
Uji Coba
Kesimpulan dan Saran
08 Juli 2013
Tugas Akhir - KI091391
31
KESIMPULAN
1. Performa klasterisasi yang dihasilkan oleh metode KD-Tree KMeans Clustering pada data set non dokumen yaitu Image Segmentation dan Pen-Based Recognition of Handwritten Digits memiliki hasil distorsi yang lebih baik dibandingkan dengan nilai rerata distorsi 15 kali proses K-Means Clustering. Selain itu, metode KD-Tree K-Means Clustering juga memiliki waktu eksekusi yang relatif sama dengan waktu eksekusi dari K-Means Clustering.
2. Performa yang dihasilkan oleh metode KD-Tree K-Means Clustering pada klasterisasi dokumen data set 20 newsgroup memiliki nilai distorsi 3 × 105 lebih rendah dibandingkan dengan nilai rerata distorsi dari K-Means Clustering. Selain itu nilai NIG KD-Tree K-Means Clustering 0,09 lebih baik dibandingkan nilai NIG maksimum K-Means Clustering. 26 Juli 2013
Tugas Akhir – KI091391
32
SARAN
1. Performa dari KD-Tree K-Means Clustering untuk klasterisasi dokumen dapat ditingkatkan salah satunya dengan melakukan proses seleksi fitur. Akan tetapi pemilihan metode seleksi fitur harus dilakukan secara hati-hati sesuai dengan karakteristik dan problem dari klasterisasi teks yang berdimensi tinggi.
2. Perbaikan lain yang bisa dilakukan adalah dengan memperbaiki efisiensi running time dari KD-Tree K-Means Clustering karena KD-Tree K-Means Clustering membutuhkan waktu training yang lama pada klasterisasi data set berdimensi tinggi seperti data set dokumen.
26 Juli 2013
Tugas Akhir – KI091391
33
SELESAI
TERIMA KASIH
26 Juli 2013
Tugas Akhir – KI091391
34