Abstrak —Klasterisasi dokumen adalah suatu proses pengelompokan dokumen secara otomatis dan unsupervised. Klasterisasi dokumen merupakan permasalahan yang sering ditemui dalam berbagai bidang seperti text mining dan sistem temu kembali informasi. Metode klasterisasi dokumen yang memiliki akurasi dan efisiensi waktu yang tinggi sangat diperlukan untuk meningkatkan hasil pada mesin pencari web, dan untuk proses filtering . Salah satu metode klasterisasi yang telah dikenal dan diaplikasikan dalam klasterisasi dokumen adalah K-Means Clustering . Tetapi K-Means Clustering sensitif terhadap pemilihan posisi awal dari titik tengah klaster sehingga pemilihan posisi awal dari titik tengah klaster yang buruk akan mengakibatkan K-Means Clustering terjebak dalam local optimum . KD-Tree K-Means Clustering merupakan perbaikan dari K-Means Clustering . KD-Tree K-Means Clustering menggunakan struktur data K-Dimensional Tree dan nilai kerapatan pada proses inisialisasi titik tengah klaster. Pada makalah ini diimplementasikan algoritma KD-Tree K-Means Clustering untuk permasalahan klasterisasi dokumen. Performa klasterisasi dokumen yang dihasilkan oleh metode KD-Tree K- Means Clustering pada data set 20 newsgroup memiliki nilai distorsi 3×10 5 lebih rendah dibandingkan dengan nilai rerata distorsi K-Means Clustering dan nilai NIG 0,09 lebih baik dibandingkan dengan nilai NIG K-Means Clustering .
Kata Kunci — K-Dimensional Tree , K-Means Clustering, KD- Tree K-Means Clustering , Klasterisasi Dokumen

## I. PENDAHULUAN
LASTERISASI dokumen adalah suatu proses pengelompokan dokumen secara otomatis dan unsupervised . Klasterisasi dokumen merupakan permasalahan yang sering ditemui dalam berbagai bidang seperti text mining dan sistem temu kembali informasi. Metode klasterisasi dokumen yang memiliki akurasi dan efisiensi waktu yang tinggi sangat diperlukan untuk meningkatkan hasil pada mesin pencari web,  dan untuk proses filtering .
Klasterisasi  dokumen  merupakan  proses  untuk  membagi sekumpulan dokumen ke dalam beberapa kelompok spesifik yang disebut sebagai klaster. Setiap klaster memiliki kumpulan dokumen yang memilki nilai kemiripan antar dokumen yang tinggi dan antar satu klaster dengan klaster yang lain memiliki dokumen dengan  nilai kemiripan yang minimal.
Secara umum, permasalahan  klasterisasi dapat dibagi menjadi 2 jenis yaitu Hierarchial Clustering dan Partitional Clustering . Partitional Clustering melakukan partisi sebuah data set menjadi sejumlah klaster  dengan memaksimalkan nilai kemiripan antar data-data pada klaster yang sama. Mencari hasil partisi yang menghasilkan nilai optimal pada
Partitional Clustering merupakan permasalahan NP- Complete . Tetapi terdapat beberapa strategi suboptimal untuk menyelesaikan permasalahan partitional clustering . Salah satu strategi suboptimal partitional clustering yang telah dikenal dan diaplikasikan dalam klasterisasi dokumen adalah K-Means Clustering . K-Means Clustering merupakan metode pengoptimalan lokal yang sensitif terhadap pemilihan posisi awal dari titik tengah klaster. Sehingga pemilihan posisi awal dari titik tengah klaster yang buruk akan mengakibatkan algoritma K- Means Clustering terjebak dalam solusi lokal optimal [1]. KD- Tree K-Means Clustering [2] merupakan perbaikan dari algoritma K-Means Clustering . KD-Tree K-Means Clustering menggunakan struktur data K-Dimensional Tree dan nilai kerapatan pada proses inisialisasi titik tengah klaster. Tetapi, hasil evaluasi oleh Redmond et al [2] tidak melingkupi performa KD-Tree K-Means Clustering pada data set dokumen.
Makalah ini bertujuan untuk melakukan analisa terhadap proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering. Proses klasterisasi dokumen tersebut akan diuji menggunakan data set 20 newsgroup dari KDD UCI Archive [3]. Diharapkan penggunaan KD-Tree K-Means Clustering dapat meningkatkan hasil dan performa dari klasterisasi dokumen dibandingkan dengan metode K-Means Clustering dasar yang menggunakan metode Forgy’s [4]. Makalah ini terorganisasi menjadi 5 bab. Bab I menguraiakan latar belakang serta tujuan penulisan makalah. Bab II menguraikan dasar teori yang digunakan untuk implementasi sistem. Bab III menguraiakan perancangan sistem klasterisasi dokumen.  Hasil uji coba diuraikan pada Bab IV. Bab V merupakan kesimpulan yang dapat diambil dari makalah ini.

## II. DASAR TEORI

## A. Algoritma K-Means Clustering
Algoritma K-Means Clustering merupakan salah satu metode dari  klasterisasi  yang  bertujuan  untuk  melakukan partisi dari sebuah data set ke dalam K klaster. Dalam prosesnya, K-Means Clustering akan mencari titik tengah dari semua klaster yang menghasilkan total nilai jarak dari setiap data observasi ke titik tengah klaster minimal [2]. Alur metode dari algoritma K-Means Clustering dapat dilihat pada Gambar 1.
Algoritma K-Means Clustering dengan nilai K tertentu secara umum memiliki kompleksitas NP-Hard [5]. Tetapi jika

## Implementasi KD-Tree K-Means Clustering untuk Klasterisasi Dokumen
Eric Budiman Gosno, Isye Arieshanti, dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS)
Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia
e-mail : i.arieshanti@if.its.ac.id
K
A
Ga
Fu Ga
dib M O( ob
B.
ya da m um ba se se be KD m be no de hy su pe ha
Di ad Pa m m di re pe
ko am

## URNAL TEKN
Algoritma K-Mean 1. Tentukan 2. Lakukan
3. Hubungk
4. Kalkulas
5. Hitung n
6. Apabila iterasi  < tidak, m ambar 1. Alur a
ungsi kdtree (list p 1. Pilih Atr
2. Urutkan
median a 3. Buat nod rekursif: node.left node.rig
ambar 2. Alur fu
berikan nilai Means Clusteri (ndk+1 log n bservasi [6].
K-Dimensio K-Dimension ang bersifat sp ari binary spa mengatur poin- mumnya diap anyak kunci p earch , dan nea Dalam imple etiap node pa erdimensi k .  S D-Tree akan memisakan sebu erada di daera ode yang ber engan setiap yperplane aka ubtree sebela embentukan K asil dari 2-dim Untuk menen imensional Tr dalah menggu ada metode in memiliki dimen menggunakan  r mensi yang m ntang terpanja emisah pada n Secara umu onstruksi KD-T mortized O( n l

## NIK POMITS
ns Clustering
n jumlah klaster K n proses inisialisa kan setiap data ob si ulang posisi titi nilai distorsi
ada perubahan
< jumlah iterasi aka kembalikan h algoritma K-Mea
point, depth ) ribut/ axis yang di ) atau ( data berdasarkan atau mean sebaga de dan konstruksi : ftChild := kdtree(p ghtChild := kdtree fungsi Build KD
Distorsi yang ing dapat di n) di mana
onal Tree
al Tree ( KD pace-partitioni ace partitionin -poin dalam plikasikan da pencarian ( mu arest neighbor ementasi, KD- ada binary tr Setiap node ya n menghasilk uah ruang me ah sebelah ki rada di subtr poin yang b an mereprese ah kanan [8] KD-Tree dapat mensional tree ntukan dimens ree terdapat  2 unakan modulo ni semua node nsi pemisah ya rentang dimen memiliki renta ang tersebut ode tersebut [2 m, kompleks Tree memenuh log n ) hingga O
Vol. 2, No. 2
K, dan jumlah iter si K titik tengah k bservasi ke klaste ik tengah klaster. ∑
1 … posisi titik teng maksimum, kem hasil klasterisasi . ans Clustering
gunakan sebagai
longest dime
n axis yang dipilih ai pivot value. i subtress dengan
(poin sebelum pivo e(poin setelah piv D-Tree
g diharapkan, m selesaikan de n menyataka
D-Tree ) [7] ad ing , dan meru ng tree . KD-Tr k–dimensiona alam pencaria ltidimensional search [8]. -Tree adalah ree tersebut  a ang bukan me kan sebuah enjadi 2 bagia iri hyperplane ree sebelah  k berada di dae entasikan nod ] . Alur met t dilihat pada dapat dilihat p si yang menja 2 metode. Me o dari nilai k pada kedalam ang sama. Cara nsi. Pada setia ang terpanjan akan digunak 2]. sitas waktu hi (1) yang me O( n log 2 n ) [8]
2, (2013) ISSN
rasi maksimum. klaster.
r terdekat , gah klaster atau mbali ke langkah pembatas ( ension ). h dan tentukan nil
melakukan fungs
ot value, depth+1 vot value, depth+1
maka Algoritm engan komple an banyaknya dalah data st upakan kasus s Tree bertujuan al space . KD an yang me l key ) seperti
binary tree d adalah sebuah erupakan leaf hyperplane an. Setiap poin e merepresent kiri. Demikian erah sebelah de yang bera tode dari Gambar 2. C pada Gambar 3 adi pemisah pa etode yang pe kedalaman nod man yang sama a yang kedua a ap node akan ng. Dimensi d kan sebagai di
untuk mela emilki komple ] .
N: 2337-3539 ( jumlah 3. Jika lai si
1); 1); ma  K- eksitas a data truktur spesial untuk D-Tree emiliki range
dimana h poin f pada yang n yang tasikan n pula kanan ada di fungsi Contoh 3.
ada K- ertama de [8].
a akan adalah dicari dengan imensi akukan eksitas
Gam
Kar inte disi seba
C.
K pen men men Clus stru titik mer mem teng P Mea den mak kera man men Red hasi pad nol. den tida P nila buc dida spac ( p 1 ,p U Mea tela leaf yan
(2301-9271 Pr
mbar 3. Contoh h
1
rena KD-Tree ernal node m mpulkan bahw anyak O( n ) [8

## KD-Tree K-M
KD-Tree K-M goptimalan  d nggunakan ni nentukan pos stering . KD- uktur data K-D k tengah kla rupakan meto miliki noise/ou gah klaster den roses inisialis ans Clusterin gan menetapk ksimal 20 d apatan dari se na N j menyata nyatakan volum dmond et al [2 il perkalian d da leaf bucket. . Maka nilai gan nilai geom ak bernilai nol osisi dari set ai rerata dari ket tersebut.  S apatkan sekum ce beserta  d p 2 ,…,p q ) [2]. Untuk memilih ans Clustering h didapatkan f bucket akan ng terbesar hin
rint)
hasil space par 2 merupakan b
menggunakan wa total kapa ].

## Means Clusteri
Means Cluster dari algoritma ilai kerapatan sisi awal ti -Tree K-Mea Dimensional aster. KD-Tre ode yang mam utlier dengan c ngan nilai kera sasi titik teng ng dimulai d kan bahwa leaf data. Selanju etiap leaf buck akan banyak me dari leaf b 2]  nilai volum dari semua re Ketika terdap rentang dim metric mean d [2]. iap leaf buck posisi data-d Sehingga untu mpulan point dengan nilai
h titik tengah g , akan diguna dari proses s n diurutkan be gga yang terke
titioning 2- dime
1,
1,
binary tree , da kapasitas  O asitas yang dip
ing ring [2] meru a KKZ/Katsou dan jarak anta itik tengah ans Clusterin Tree dalam ee  K-Means mpu menanga cara menghap apatan terenda gah klaster p dengan pemb af bucket dari K utnya akan ket dengan for data pada lea bucket j .  Pada me V j dapat d entang dimen pat dimensi de mensi tersebut dari nilai rent
ket akan diind ata yang bera uk leaf bucket leaf bucket ( kerapatan
h klaster awa akan informas sebelumnya.  M erdasarkan ni ecil. Leaf buck
A ensional tree an setiap leaf O(1), maka d perlukan KD-
upakan algor udivinis [9] y ar poin/data da klaster K-M ng menggun proses inisial Clustering ani data set y pus 20% calon ah [2]. pada KD-Tree entukan KD- KD-Tree mem dikalkulasi rmula af bucket j, da implementasi dinyatakan den nsi dari poin- engan nilai ren t akan digant tang dimensi y dentifikasi seb ada di dalam t sebanyak q ( m 1 ,m 2 ,..,m q ) dari setiap al pada prose si leaf bucket y Mula-mula, se lai kerapatan ket yang mem
A-433
(1)
f dan dapat -Tree ritma yang alam Means nakan lisasi juga yang n titik e  K- -Tree miliki nilai di an V j i dari ngan -poin ntang tikan yang
bagai leaf akan pada poin
s K- yang emua dari miliki
Algoritma KD-Tree K-Means Clustering
1. Pembentukan K-Dimensional Tree dari data set. K-Dimensional Tree yang dibuat memiliki leaf bucket dengan jumlah data maksimal 20 per leaf bucket .
2. Untuk setiap leaf bucket ( L 1 ,L 2 ,…,L j ) , kalkulasi nilai kerapatan (P j ) dari setiap leaf bucket L j , dan kalkulasi nilai titik tengah leaf bucket ( M j ) dengan mencari nilai rerata dari semua point yang ada pada leaf bucket L j .
3. Pilih titik tengah klaster pertama C 1 = M z , dimana arg max .
4. Untuk t = 2,…, K :  Untuk j = 1,..., q kalkulasi nilai ranking leaf bucket ( G j )
dengan fomula :
1 … , .  C t = M z , dimana arg max .
5. Hapus 20% leaf bucket dengan nilai kerapatan terendah. Kembali ke langkah 3 dan kalkulasi posisi K titik tengah klaster baru ( ĉ 1 , ĉ 2 ,…, ĉ k ).
6. Jalankan algoritma K-Means Clustering dengan nilai inisialisasi titik tengah ( C 1 ,...,C k ) dan ( ĉ 1 , ĉ 2 ,…, ĉ k ).
Gambar 4. Alur Algoritma KD-Tree K-Means Clustering
nilai kerapatan tertinggi akan dipilih sebagai titik tengah klaster pertama. Pemilihan titik tengah klaster yang berikutnya akan didasarkan pada nilai jarak antara calon titik tengah /leaf bucket dengan titik tengah yang telah ditetapkan, dan nilai kerapatan dari leaf bucket tersebut. Semakin jauh jarak leaf bucket dari posisi titik tengah yang telah ditetapkan dan semakin besar nilai kerapatan leaf bucket tersebut, maka semakin tinggi peluang leaf bucket tersebut menjadi titik tengah klaster yang baru [2]. Secara matematis, formula untuk menentukan nilai dari leaf bucket dapat dilihat pada (2).
… , (2)
Dengan fungsi d menyatakan fungsi jarak seperti euclidean distance , C k menyatakan posisi titik tengah klaster, M j menyatakan posisi leaf bucket , dan P j menyatakan nilai kerapatan dari leaf bucket . Untuk setiap iterasi, leaf bucket dengan nilai G j terbesar akan dipilih sebagai titik tengah klaster baru. Iterasi akan terus dijalankan hingga didapatkan Kc titik tengah klaster yang akan digunakan sebagai inisialisasi pada K-Means Clustering [2]. Alur kerja dari algoritma KD-Tree K-Means Clustering secara keseluruhan dapat dilihat pada Gambar 4 .
Untuk mengatasi permasalahan terkait dengan terpilihnya data outlier menjadi calon titik tengah, algoritma akan membuang 20% leaf bucket /calon titik tengah yang memiliki nilai kerapatan terendah. Dengan hanya menggunakan 80% leaf bucket yang memiliki kerapatan tertinggi, maka kemungkinan data outlier terpilih menjadi centroid cluster dapat diminimalisasi sebelum algoritma dijalankan [2].
Nilai kerapatan   dapat diganti dengan ranking density ( . Leaf Bucket dengan nilai terendah memiliki nilai   = 1 dan leaf bucket 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 [2].

## III. PERANCANGAN SISTEM KLASTERISASI DOKUMEN
Perancangan sistem klasterisasi dokumen ini dibagi menjadi 3 tahap yaitu tahap pra proses data set dokumen, tahap pembobotan kata/ term weighting dan tahap klasterisasi menggunakan KD-Tree K-Means Clustering .

## A. Tahap Pra Proses Data Set Dokumen
Sebelum dapat diterapkan proses pembelajaran seperti klasterisasi data set dokumen perlu untuk mengalami tahap pra proses terlebih dahulu. Tujuan dari tahap pra proses ini adalah mengubah data set dokumen ke dalam bentuk bag of words [10]. Bag of words merupakan suatu metode untuk merepresentasikan data set yang berbasis teks seperti dokumen, dan artikel ke dalam suatu matriks. Bag of words akan menyimpan informasi frekuensi kemunculan suatu kata dalam suatu dokumen dalam bentuk matriks 2 dimensi. Bag of words merupakan representasi dokumen yang bersifat orderless dimana bag of words akan mengabaikan unsur keterkaitan antara 1 kata dengan kata yang lain serta urutan kemunculan kata pada dokumen. Kalimat seperti “home made” akan memiliki nilai yang sama dengan “made home” pada bag of words [10].
Tahap pra proses akan dimulai dengan proses stemming kata, dan penghapusan stop word . Stop Word adalah kata-kata yang umum dan memiliki nilai yang tidak signifikan dalam proses machine learning pada dokumen. Sehingga stop word perlu untuk dihilangkan dari kamus vocabulary secara keseluruhan. Proses penghapusan stop word dapat mereduksi jumlah kata yang perlu disimpan pada proses pembelajaran secara signifikan [12]. Dalam implementasi makalah ini, penulis menggunakan daftar stop word yang dapat diunduh pada repository Journal of Machine Learning Research [13]. Stemming adalah sebuah metode untuk menyederhanakan suatu kata ke bentuk dasar/bentuk stem dari kata tersebut. Hasil kata pada stemming tidak harus identik dengan akar dari suatu kata secara morfologika. Tetapi hasil stemming cukup untuk menyederhanakan kata-kata yang berkaitan ke dalam bentuk stem /dasar yang sama. Algoritma stemming seringkali disebut juga sebagai stemmer . Sebagai contoh kata computer , computing , computation, dan computes akan memiliki bentuk stem yang sama yaitu comput [13]. Metode stemming yang digunakan pada proses ini adalah porter stemmer [14] yang telah umum digunakan dalam proses stemming kata berbahasa inggris.
Setelah kata-kata dalam artikel telah diseleksi dan disederhanakan dalam proses stemming , maka semua kata pada artikel yang tersisa akan dikumpulkan dan disimpan dalam bentuk bag of words . Untuk menghilangkan kata-kata yang berbentuk noise dan typo , kata yang dimasukkan ke dalam bag of words hanyalah kata yang muncul pada minimal 2 dokumen [13].

## B. Tahap Pembobotan Kata/Term Weighting
Sebelum melakukan proses klasterisasi, data set akan mengalami proses pembobotan kata/ term weigthing terlebih
dahulu. Proses pembobotan kata/ term weigthing adalah sebuah proses untuk memberikan nilai pada sebuah kata. Kata yang memiliki nilai signifikan pada proses machine learning akan memiliki nilai bobot yang tinggi. Sebaliknya kata yang tidak memberikan pengaruh signifikan pada proses machine learning akan memiliki nilai bobot yang rendah [11]. Untuk proses pembobotan kata akan digunakan perhitungan term  frequency – inverse document frequency (TF-IDF) [15]. Sebuah kata akan memiliki nilai tf-idf tinggi jika memiliki frekuensi kemunculan yang tinggi namun jumlah dokumen yang memuat kata tersebut dalam corpus sedikit [11] .
Tf-idf merupakan produk hasil perkalian dari 2 nilai statistic yaitu term frequency (TF), dan inverse document frequency (IDF) [11]. Secara matematis, (3) menunjukkan formula matematis dari tf-idf, di mana t menyatakan kata yang dicari nilainya, d menyatakan dokumen yang mengandung kata tersebut, dan D menyatakan koleksi dari dokumen secara keseluruhan.
, , , , (3)
Nilai tf-idf memiliki banyak variasi nilai tergantung pada formula perhitungan dari term frequency dan inverse document frequency .  Pada makalah ini akan digunakan formula perhitungan tf-idf yang menggunakan  fungsi logaritma dari term frequency dan inverse document frequency seperti yang ditunjukkan pada (4) dimana f(t,d) menyatakan frekuensi kata t pada dokumen d, N menyatakan banyak dokumen pada data set, dan Dft menyatakan frekuensi dokumen yang memuat kata t .
, , 1 log , (4)

## C. Tahap Klasterisasi Dokumen
Pada tahap ini data set yang telah mengalami tahap pra proses dan proses pembobotan kata akan diklasterisasi dengan menggunakan KD-Tree K-Means Clustering dan K-Means Clustering metode Forgy’s sebagai pembanding.

## IV. UJI COBA
Pada tahap ini akan dilakukan uji coba untuk menguji performa klasterisasi dokumen yang dihasilkan oleh KD-Tree K-Means Clustering . Data set yang digunakan sebagai bahan uji coba adalah data set 20 newsgroup dari KDD UCI Archive . Uji coba dilakukan dengan membandingkan performa KD- Tree K-Means Clustering dengan performa 15 kali proses K- Means Clustering .

## A. Parameter Evaluasi
Pengujian performa klasterisasi pada makalah ini akan dilakukan secara supervised dan unsupervised . Performa dari klasterisasi secara unsupervised akan ditentukan berdasarkan nilai distorsi atau jarak dari semua data ke titik tengah klaster terdekat. Pada data set yang sama, nilai distorsi yang semakin rendah menandakan hasil klasterisasi yang baik. Formula dari perhitungan nilai distorsi dapat dilihat pada (5) dimana d menyatakan fungsi jarak ( euclidean distance ), x i menyatakan data ke-i dan c j menyatakan klaster ke j .
∑ 1 … , (5)
Sedangkan untuk pengujian secara supervised akan dilakukan dengan cara menghitung nilai Normalized Information Gain (NIG) dari hasil klasterisasi [2]. NIG menggunakan konsep entropy sebagai pengukuran informasi. NIG merupakan hasil normalisasi dari Information Gain dimana nilai NIG akan bernilai 1 jika klasterisasi berhasil mendapatkan semua informasi sesuai dengan kelas, dan NIG akan bernilai 0 jika tidak ada informasi yang diterima dari hasil klasterisasi. Formula untuk menghitung NIG secara umum dapat dilihat pada (6). dimana EN Total merepresentasikan nilai Total Entropy atau rerata informasi yang ada di setiap data pada  data set dan wEN merepresentasikan nilai Weighted Entropy atau rerata informasi setiap poin pada setiap klaster. Weighted Entropy akan memberikan nilai 0 pada saat semua klaster homogen.
.
(6)
Perhitungan dari Total Entropy, dan Weighted Entropy dapat dilihat pada (7) dan (8) Nilai n menyatakan jumlah data pada data set, dan c l menyatakan banyaknya data pada kelas l untuk setiap l=1,..,L sehingga ∑ . Pada (8), K menyatakan banyaknya klaster. Untuk setiap k=1,..,K, n k menyatakan banyaknya data pada klaster k, dan EN k menyatakan nilai entropy dari klaster K. Nilai entropy dari sebuah klaster  dapat dihitung dengan menggunakan (9).
∑ (7) ∑ (8) ∑ (9)

## B. Parameter Uji Coba
Pada bagian ini akan dijelaskan nilai-nilai yang menjadi parameter pada hasil uji coba. Semua parameter pada hasil uji coba ini diturunkan dari 3 parameter utama perhitungan performa pada tugas akhir ini yaitu nilai distorsi , nilai Normalized Information Gain , dan waktu eksekusi proses klasterisasi dokumen dalam satuan milidetik. Daftar lengkap seluruh nilai parameter ini dapat dilihat pada Tabel 1.

## C. Hasil Uji Coba
Pada skenario ini dilakukan uji coba untuk menghitung performa dari algoritma KD-Tree K-Means Clustering pada klasterisasi dokumen. Hasil performa KD-Tree K-Means Clustering pada klasterisasi dokumen ini akan dibandingkan dengam hasil dari algoritma K-Means Clustering pada data set yang sama. Data set yang digunakan pada skenario uji coba ini adalah data set kumpulan artikel 20 newsgroup yang  telah mengalami pra proses dan proses term weighting . Hasil percobaan dari skenario ini dapat dilihat pada Tabel 2.
A-436 Tabel 1. Parameter Uji Coba Nama Parameter Deksripsi K Jumlah klaster pada proses klasterisasi m Jumlah fitur pada data set row Jumlah data pada data set D kd Nilai distorsi dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering Dmin fa Nilai distorsi minimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering μ fa Nilai rerata distorsi dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering
σ fa Standar deviasi distorsi dari 15 kali proses klasterisasi
dokumen menggunakan algoritma K-Means Clustering
N fa>kd Jumlah proses klasterisasi dokumen dari 15 kali iterasi menggunakan algoritma K-Means Clustering yang memiliki nilai distorsi lebih baik daripada KD-Tree K- Means Clustering
N fa <kd Jumlah proses klasterisasi dokumen dari 15 kali iterasi menggunakan algoritma K-Means Clustering yang memiliki nilai distorsi lebih baik daripada KD-Tree K- Means Clustering
NIG kd Nilai NIG dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering NIG fa Nilai NIG maksimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering
T kd Waktu eksekusi dari proses klasterisasi dokumen menggunakan algoritma KD-Tree K-Means Clustering Tmin fa Waktu eksekusi minimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Tmax fa Waktu eksekusi maksimum dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering Ttotal fa Waktu eksekusi total dari 15 kali proses klasterisasi dokumen menggunakan algoritma K-Means Clustering
Tabel 2. Hasil  Uji Coba Klasterisasi pada 20 newsgroup

## Parameter Nilai
K 20 m 20.536 D kd 4,14 x 10 7 Dmin fa 4,12 x 10 7 μ fa 4,17 x 10 7 σ fa 3,00 x 10 5 N fa>kd 4 N fa <kd 11 NIG kd 0,18 NIG fa 0,09 T kd 13.295.630 Tmin fa 2.535.463 Tmax fa 12.619.237 Ttotal fa 105.325.216
Dari hasil uji coba ini dapat dilihat bahwa proses klasterisasi dokumen pada algoritma KD-Tree K-Means Clustering memiliki nilai distorsi sebesar 4,14×10 7 . Hasil ini lebih buruk 2×10 5 dibandingkan nilai distorsi minimum hasil K-Means Clustering . Namun Hasil ini lebih baik 3×10 5 dibandingkan dengan nilai rerata distorsi dari K-Means Clustering dengan standar deviasi 9,9×10 4 . Sedangkan 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 K-Means Clustering.
Untuk waktu eksekusi dari algoritma KD-Tree K-Means Clustering pada klasterisasi dokumen 20 newsgroup memiliki waktu eksekusi 13.295.630 milidetik (3 jam 41 menit). Sedangkan waktu eksekusi dari sekali proses K-Means Clustering memiliki rentang antara 2.535.463 milidetik hingga 12.619.237 milidetik (42 menit hingga 3 jam 30 menit).

## V. KESIMPULAN
Dari hasil uji coba dapat diambil kesimpulan bahwa performa klasterisasi dokumen yang dihasilkan oleh metode KD-Tree K-Means Clustering pada data set 20 newsgroup menghasilkan nilai distorsi 3 × 10 5 lebih rendah  dibandingkan dengan nilai rerata distorsi dari K-Means Clustering dan nilai NIG 0,09 lebih baik dibandingkan nilai NIG maksimum K- Means Clustering . Sedangkan dari segi waktu, algoritma KD-Tree K-Means Clustering memiliki waktu training yang cukup lama. Oleh karena itu, perbaikan yang bisa dilakukan pada penelitian selanjutnya adalah dengan memperbaiki efisiensi running time dari KD-Tree K-Means Clustering sehingga waktu eksekusi dari KD-Tree K-Means Clustering secara keseluruhan dapat ditingkatkan.

## DAFTAR PUSTAKA
[1]  A.K. Jain, M.N. Murty, and P.J. Flynn, "Data clustering: A review," ACM Computation Surveys , vol. 31, no. 3., pp. 264–323, 1999.
[2]  Stephen J Redmond and Conor Heneghan, "A method for initialising the K-means clustering algorithm using kd-trees," Pattern Recognition Letters , vol. 28, no. 8, pp. 965–973, June 2007.
[3]  DD UCI Archive. (2013, March) 20 Newsgroups Dataset. [Online]. dd.ics.uci.edu/databases/20newsgroups/20newsgroups.html
[4]  E. W. Forgy, "Cluster analysis of multivariate data: efficiency versus interpretability of classifications," Biometrics , vol. 21, pp. 768–769, 1965.
[5]  M. Mahajan, P. Nimbhorkar, and K. Varadarajan, "The Planar k- Means Problem is NP-Hard," Lecture Notes in Computer Science , vol. 5431, pp. 274–285, 2009.
[6]  M. Inaba, N. Katoh, and H. Imai, "Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering," in Proceedings of 10th ACM Symposium on Computational Geometry , 1994, pp. 332–339.
[7]  J.L Bentley, "Multidimensional binary search trees used for associative searching," Communications of the ACM , vol. 18, no. 9, pp. 509-517, 1975.
[8]  M. da Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry, Algorithm and Applications , 3rd ed.: Springer, 2008.
[9]  I. Katsavounidis, C.C.J. Kuo, and Z. Zhen, "A new initialization technique for generalized lloyd iteration," IEEE Signal Processing Letter , vol. 1, no. 10, pp. 144–146, 1994.
[10] G. Salton and MJ. McGill, Introduction to modern information retrieval .: McGraw-Hill, 1986.
[11] Christopher D. Manning, Raghavan Prabhakar, and Hinrich Schütze, An Introduction to Information Retrieval , 1st ed., Cambridge University Press, Ed. Cambridge, England: Cambridge University Press, 2009.
[12] David D. Lewis, Yiming Yang, Tony G. Rose, and Fan Li. (2004) Journal of Machine Learning Research. [Online]. http://jmlr.csail.mit.edu/papers/volume5/lewis04a/a11-smart-stop- list/english.stop
[13] Harun U ğ uz, "A two-stage feature selection method for text categorization by using information gain, principal component
analysis, and genetic algorithm," Knowledge-Based System , vol. 24, no. 7, pp. 1024-1032, April 2011.
[14]  M.F. Porter, "An algorithm for suffix stripping," Program , vol. 14, no.
3, p. 130 − 137., 1980.
[15]  Gerard Salton and Christopher Buckley, "Term-weighting approaches in automatic text retrieval," Information Processing and Management , pp. 513-523, 1988.