PENGGALIAN FREQUENT TREES DALAM KLASTERISASI DOKUMEN XML

Prosiding Seminar Nasional Manajemen Teknologi VIII Program Studi MMT-ITS, Surabaya 2 Agustus 2008

PENGGALIAN FREQUENT TREES DALAM KLASTERISASI DOKUMEN XML Rinci Kembang Hapsari dan Arif Djunaidy Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Email: [email protected]

ABSTRAK Dengan standarisasi XML sebagai sebuah pertukaran bahasa melalui jaringan Internet, sebagian besar informasi diformat dalam bentuk dokumen XML dan penyimpanannya dalam bentuk tabel-tabel relasi. Dimana proses query terhadap tabeltabel relasi dalam jumlah besar akan sangat mahal karena diperlukan sejumlah operasi join yang lebih banyak sehingga penyimpanan data mengalami fragmentasi. Penggalian klasterisasi (mining cluster) terhadap dokumen-dokumen XML berdasarkan strukturnya dapat mengurangi fragmentasi data hasil proses klasterisasi. Dalam Thesis ini akan meneliti aplikasi dari metode klasterisasi untuk pengelompokkan dokumen XML berdasarkan dari penggalian frequent tree Pemodelan dokumen XML sebagai tree berlabel terurut berakar (rooted ordered labeled tree), dengan menerapkan algoritma klasterisasi hirarkikal aglomerative. Dalam klasterisasi ini terdapat tiga tahapan, yaitu penggalian frequent tree, pembentukan klaster awal, dan prunning. Hasil yang didapat dari penelitian ini menunjukkan bahwa parameter yang sangat mempengaruhi adalah nilai minsup(minimum support) dan minCsup (minimum Cluster Support). Nilai minsup digunakan untuk penggalian frequent tree yang digunakan untuk label klaster dan minCsup yang digunakan untuk menghitung nilai cluster support dan menentukan klaster frequent support yang digunakan untuk melakukan pemecahan klaster. Semakin kecil nilai minCsup maka running time yang dihasilkan akan semakin besar, karena untuk setiap klaster terdapat klaster frequent support dalam jumlah banyak. Pada tahapan pembentukan klaster, matrik global frequent tree discan dua kali, satu untuk pembentukan klaster awal dan satu lagi untuk membuat klaster disjoint. Semakin mengerucut dendogram maka kesamaan inter klaster semakin kecil dan berlau sebakiknya bahwa semakin melebar dendogram maka kesamaan inter klasternya semakin besar. Kata kunci: dokumen XML, frequent tree, minsup, minCsup, klasterisasi

PENDAHULUAN Latar belakang. Dengan standarisasi XMLsebagai sebuah pertukaran bahasa melalui jaringan Internet, sebagian besar informasi diformat dalam bentuk dokumen XML yang digunakan untuk menganalisis informasi secara efisien. Pemisahan dokumen-dokumen XML dan penyimpanan umumnya dalam bentuk tabel-tabel relasi, tetapi dalam banyak kasus proses query menjadi sangat mahal. Hal ini disebabkan sejumlah join yang diperlukann lebih banyak untuk memperoleh informasi dari data yang telah di fragmentasi. Penggalian klaster (mining cluster) dalam dokumen-dokumen XML bisa mengurangi masalah fragmentasi. Dalam hal ini akan dilakukan klasterisasi (clustering) dokumen XML berdasarkan pada frequent tree yang didapatkan. Pengelompokkan dokumen XML


berdasarakan kesamaan strukturnya berhubungan dengan aplikasi metode klasterisasi menggunakan suport bobot (weight support) yang digunakan untuk menghitung kesamaan antar dokuemn yang direpresentasikan dengan sebuah tree T. Selama bahasa XML dapat dituliskan dalam hirarki data, klasterisasi dokumen XML dapat dimanfaatkan dalam domain aplikasi yang membutuhkan managemen dari struktur hirarki. Kontribusi utama dari penelitian ini adalah tidak dipengaruhi oleh jarak kluster yang berubah-ubah. Metode klasterisasi ini dapat menampilkan kluster pada berbagai jarak karena kriteria klasterisasi didasarkan pada fungsi score. M. J. Zakki telah mengenalkan TreeMiner, sebuah algoritma efisien untuk permasalahan mining frequent subtree dalam sebuah hutan (database). Algoritma ini digunakan pada permasalahan penemuan embeded subtree dalam sebuah koleksi dari tree yang rooted terurut dan berlabel. Ide dari sebuh scope untuk sebuah node dalam sebuah tree, yang menunjukkan bagaimana tree direpresentasikan sebagai sebuah list dari scope node dalam format vertikal baru yang disebut scope-list. Teknik tree mining dengan meninjau kemiripan prefix dari string encoding akan diterapkan untuk klasterisasi dokumen XML berdasarkan weight support dari setiap tree T pada sebuah label klaster yang didapatkan. Perumusan Masalah Masalah penelitian (Statement of the problem) dalam penelitian ini adalah “Penggalian Frequent Tree dalam Klasterisasi dokumen.” Dengam menjalan klasterisasi berdasarkan hasil dari penggalian frequent tree dengan merepresentasikan dalam string encoding dan menggunakan XML document akan dianalisa kemampuannya dalam melakukan klasterisasi. Dalam penelitian ini dibatasi pada dokumen XML yang bisa dituliskan dalam hirarki data, dan dalam klasterisasi dokumen XML untuk menentukan kesamaan dari dokumen-dokumen XML dengan menggunakan kemiripan prefixnya. LANDASAN TEORI Klasterisasi Dalam sub-bab ini akan dibahas mengenai pengertian klsaterisasi dan teknikteknik dalam klasterisasi. Pengertian Klasterisasi Berdasarkan definisi klasterisasi pada sub-bab 2.2, klasterisasi (clustering) merupakan metode untuk mengelompokkan objek, di mana kelompok yang terbentuk memiliki karakteristik objek yang serupa(mirip) dan berbeda karakteristiknya pada kelompok lain. Klasterisasi juga dikenal dengan unsupervised learning karena objekobjek dalam database tidak memiliki klas (tipe) yang membedakan antara satu objek dengan objek yang lain. Klasterisasi adalah teknik yang berguna untuk mengeksplorasi data, digunakan pada saat banyak kasus dan tidak memiliki pengelompokan secara alami. Klaster sendiri adalah grup dari obyek-obyek yang anggotanya lebih mirip (similar) satu sama lain dari pada anggota klaster lain. Kategori pengelompokkan klasterisasi adalah proses bootom-up, dimana kategori merupakan bagian dari luaran (ouput), bukan dari masukan (input). Klasterisasi dengan Pendekatan Hirarki Klasterisasi dengan pendekatan hirarki atau sering disebut dengan hierarchical clustering mengelompokkan data dengan membuat suatu hirarki berupa dendogram

ISBN : 978-979-99735-6-6 C-22-2


dimana data yang mirip akan ditempatkan pada hirarki yang berdekatan dan yang tidak pada hirarki yang berjauhan. Ada dua metode yang sering diterapkan yaitu agglomerative hieararchical clustering dan divisive hierarchical clustering. Agglomerative melakukan proses clustering dari N cluster menjadi satu kesatuan cluster, dimana N adalah jumlah data, sedangkan divisive melakukan proses clustering yang sebaliknya yaitu dari satu cluster menjadi N cluster. Metode Klasterisasi Agglomerative Hirarkikal Sebuah metode agglomerative hirarkikal (hierarchical Agglomerative Clustering (HAC)) bekerja berdasarkan pengelompokkan data objek (dokumen) menjadi sebuah tree klaster, yang disebut juga sebagai dendogram. Metode ini karena berbentuk hirarki memungkinkan penelusuran simpol-simpol dari topic yang paling umum sampai topic yang lebih khusus. Perbedaan metode HAC terdapat dalam bagaimana klaster digabungkan pada tiap-tiap tingkat. Gambar 1. memberikan gambaran proses dasar dari algoritma HAC. Dalam gambar 1, tahap 3 bisa diselesaikan dalam beberapa cara. Dimana pada tahap akan membedakan jenis klasterisasi dengan single linkage, complete-linkage atau average-linkage. 1 2 3 4

Dimulai dengan menetapkan tiap-tiap item menjadi sebuah klaster, sehingga jika ada N item, berarti terdapat N klaster. Hitung jarak (similarity) antar klaster Cari pasangan klaster yang terdekat (most similar) dan gabungan (merge) sehingga menjadi satu klaster baru. Hitung jarak (similarity) antara klaster baru dengan tiap-tiap klaster yang lama Ulangi langkah 2 dan 3 sampai semua item berada dalam sebuah klaster tunggal berukuran N Gambar 1. Langkah Dasar Metode Umum HAC

Aturan Struktur Tree Sebuah rooted tree berlabel T = (V,E) adalah sebuah grap directed, terhubung yang acyclic, dengan V = {0, 1, 2, . . ., n} sebagai himpunan dari vertek atau node, E = {( x, y ) x, y ∈ V } sebagai himpunan dari edge. Sebuah vertek terkenal r ∈ V dicalonkan sebagai root, dan untuk semua x ∈ V , terdapat sebuah path unik dari r ke x. l : V → L adalah sebuah fungsi label yang memetakkan vertek pada sebuah himpunan label L = {l1 , l 2 , . . .} . Ukuran T adalah jumlah node dalam T. Dalam sebuah tree terurut, children dari setiap vertex terurut (yaitu jika sebuah vertex memiliki k children, maka kita dapat mencalonkannya sebagai child pertama, kedua sampai child ke-k), selain itu adalah tree yang tak terurut. Diasumsika bahwa vertek x ∈ V searti dengan (jumlah kemunculan pada) posisi nx dalam kunjungan dept-first (preorder) dari tree T (untuk contoh root r adalah vertek n ). Diberikan T ( x ) menotasikan subtree rooted pada x, dan diberikan y daun yang 0

paling kanan (atau nomor descendant yang paling tinggi) dibawah x. Kemudian, scope n ,n dari x diberikan sebagai s( x ) = [x, y ] (atau x y ). Secara intuisi s(x) membatasi range

[

dari vertek dibawah x.

ISBN : 978-979-99735-6-6 C-22-3

]


Support

S ≤ {i,e} T Jika , juga dikatakan T contains S atau S muncul dalam T. Setiap kemunculan S dalam T dapat diidentifikasi dengan match label yang unik, yang ϕ ( x 0 ) ϕ (x1 ) ⋅ ⋅ ⋅ ϕ x s diberikan oleh serangkaian dimana x i ∈ V s . Dimana match label dari S diberikan sebagai set dari posisi matching dalam T. δ T (S ) menotasikan jumlah dari munculnya subtree S dalam suatu tree T, diberikan dT dijadikan variabel indikator, dengan dT(S) = 1 jika δ T (S ) > 0 dan dT(S) = 0 jika δ T (S ) = 0 . D menotasikan sebuah database (sebuah forest) dari tree. Support dari sebuah subtree S dalam database dinotasikan sebagai berikut : σ (S ) = ∑T ∈D d T (S ) (2.1) yaitu jumlah dari tree dalam D yang mengandung setidaknya satu S yang muncul. Pembobotan (weighted) support S didefinisikan sebagai : σ w (S ) = ∑T ∈D δ T (S ) (2.2) yaitu total S yang muncul pada keseluruhan tree dalam D Sebuah tree T didefinisikan absolute support dalam D (database tree (forest)) A dinotasikan π (T , D ) yang merupakan jumlah kemunculan tree T dalam D yang muncul paling sedikit sekali. π A (T , D ) = ∑ d s (T ) = {S ∈ D | T ≤ S } S ∈D (2.3) w Untuk weight support T dinotasika dengan π (T , D ) yang merupakan jumlah total kemunculan T diatas semua tree dalam D, yang dirumuskan dengan : π w (T , D ) = ∑ δ s (T ) S ∈D (2.4) (Relative) support T dalam D dinotasikan π (T , D ) didefinisikan sebagai bagian kecil tree dalam D yang terdiri dari T, sebagai berikut : π A (T , D ) π (T , D ) = D (2.5) T dikatakan frequent tree dalam D jika : π (T , D ) ≥ π min (2.6)

( )

min F dimana π adalah sebuah threshold minimum user. Kita notasikan sebagai k yang merupakan himpunan semua frequent subtree yang berukuran k disebut juga k(sub) tree.

Algoritma TreeMiner TreeMiner melaukan Dept-First Search (DFS) untuk frequent subtree, menggunakan gambaran baru tree yang disebut scope-list untuk perhitungan support dengan cepat. 1 2 3 4 5 6 7 8 9

TREEMINER(D,minsup): F1={frequent 1-subtree}; F2={class[P]1 dari frequent 2-subtree}; for semua [P]1 ∈ E do Enumerate-Frequent- Subtrees([P]1); ENUMERATE-FREQUENT-SUBTREES([P]): for each element(x,i) ∈ [P] do

[P ]= φ ; i x

for setiap elemen(y,i) ∈ [P] do

ISBN : 978-979-99735-6-6 C-22-4


11

ℜ = {( x, i ) ⊗ ( y, j )} ; L(ℜ) = {L( x ) I ⊗ L( y )} ;

12

if untuk R ∈ ℜ , R adalah frequent then

10

13 14

[P ] = [P ]U {R}; i x

i x

Enumerate-Frequent-Subtrees

([P ]); i x

Gambar 2. Algoritma TreeMiner

Model Vector Space dan Klasterisasi Dokumen Dalam model vector space, setiap dokumen d diberikan sebagai sebuah vektor, d, dalam term-space. Setiap dokumen ditunjukkan dalam term frequency (TF) vektor d tf = (tf 1 , tf 2 ,..., ft n ) (2.7) dimana fti adalah frekuensi term ke-i dalam dokumen. Dalam penambahan digunakan model bobot (weight) setiap term base dala inverse document frequency (IDF) dalam koleksi dokumen. Kesamaan antara dua dokumen harus diukur dalam beberapa cara jika sebuah algoritma klasterisasi digunakan. Terdapat sejumlah kemungkinan pengukuran untuk menghitung kesamaan antar dokumen, tetapi secara umum adalah untuk menghitung cosine [MST-00] dan didefinisikan sebagai berikut : (d • d 2 ) similarity (d1 , d 2 ) = cos ine(d 1 , d 2 ) = 1 d1 ⋅ d 2 (2.8) d dimana • menyatakan vector dot product dan adalah panjang vektor d. Diberikan himpunan dokumen S dan representasi hubungan vektor, definisi dari centroid vector c menjadi : 1 c = ∑d S d∈S (2.9) Kesamaan antar dua vector centroid dan antar sebuah dokumen dan sebuah vector centroid dihitung dengan menggunakan pengukuran cosine sebagai berikut : (d , c ) = d • c cos ine(d , c ) = d c c (2.10) c •c cos ine(c1 , c 2 ) = 1 2 c1 c 2 (2.11) Catatan meskipun vektor dokumen merupakan satuan panjang, tetapi vektor centroid tidak selalu merupakan unit panjang. Pada penggalian frequent tree dalam klasterisasi dokumen xml ini, digunakan dua definisi untuk menjelaskan teknik hirarkikal agglomerative, yaitu intra-cluster similarity dan inter-cluster similarity. Inter cluster similarity adalah keseluruhan kesamaan antar dokumen dari dua klaster yang berbeda. Sedangkan intra-cluster similarity adalah keseluruhan kesamaan antar dokumen dalam sebuah klaster. DESAIN ALGORITMA Berdasarkan permasalahan pada bab 1, maka dalam bab ini dijelaskan mengenai desain algoritma sistem klasterisasi dokumen XML berdasarkan frequent tree, yang meliputi desain klasterisasi dan desain sistem secara keseluruhan.

ISBN : 978-979-99735-6-6 C-22-5


Sistem Klasterisasi Dokumen XMLmenggunakan Klasterisasi berdasar frequent tree Sistem klasterisasi dokumen XMLberdasarkan frequent tree terdiri dari tiga bagian, antara lain: (a) bagina pra klasterisasi, (b) bagian konstruksi klaster, dan (c) bagian membangun pohon klaster. Blok diagram sistem klasterisasi dokumen XMLberdasarkan frequent tree ditunjukkan pada gambar 3.1. Input dari sistem klasterisasi ini dibatasi berupa dokumen XMLdan hasil output sistem adalah dokumen XMLyang terklasterisasi.

Input : Dokumen XML

Pra klasterisasi

Konstruksi Klaster

Membangun Pohon Klaster

Output : Dokumen Terklasterisasi

Gambar 3. Blok Diagram Sistem Klasterisasi Dokumen XMLmenggunakan Klasterisasi berdasarkan frequent tree.

Pra Klasterisasi Blok diagram pra klasterisasi ditunjukkan dalam gambar 3.2 yang terdiri dari dua bagian, yaitu : (a) Parsing dokumen XMLke tree dan (b) Menentukan frequent tree.

Gambar 4. Blok Diagram Pra Klasterisasi Input untuk bagian proses pra klaster adalah dokumen XML sedangkan output yang dihasilkan dari proses pra klaster adalah frequent tree. Semua Tree yang merupakan frequent ini akan digunakan sebagai inputan pada proses konstruksi klaster.

Konstruksi Klaster Dalam blok diagram konstruksi klaster yang ditunjukkan dalam gambar 3.8, yang terdiri dari dua bagian, yaitu : (a) Pembentukan klaster awal, (b) membuat klaster disjoint dan (c) prunning klaster. Input dalam proses konstruksi klaster ini merupakan output dari blok diagram sebelumnya (blok proses pra klasterisasi), yaitu frequent tree yang didapatkan dengan menggunakan algoritma treeminer dengan database (forest) D.

Gambar 5. Blok Diagram Konstruksi Klaster

Pembentukan Klaster Awal Sebuah global frequent tree menyatakan himpunan tree(subtree) yang muncul lebih besar atau sama dengan penggunaan spesifikasi nilai minimum support (minsup).

ISBN : 978-979-99735-6-6 C-22-6


Global support dari sebuah tree (subtree) adalah total tree (subtree) yang muncul pada keseluruhan tree dalam database (forest) D, yang secara khusus diberikan sebagai prosentase dari jumlah tree dalam forest D.

Membentuk KlasterDisjoint Sebuah klaster inisial Ci baik untuk sebuah tree Tj jika terdapat global frequent tree dalam Tj yang muncul dalam beberapa tree dalam Ci. Sehingga kita dapat mempertimbangkan himpunan frequent tree dari setiap klaster sebagai titik referensi untuk klaster, dan menggunakan frequent tree klaster untuk mengklasterisasi dokumen yang sama. Secara formal, dapat dikatakan bahwa sebuah tree t adalah cluster frequent dalam sebuah klaster Ci jika t terdapat dalam beberapa tree T dalam Ci. Cluster support dari t dalam Ci adalah presentase dari tree dalam Ci yang terdapat t.   Score(C i ← Tree j ) = ∑ n( x ) * cluster _ sup port ( x)  x 

  − ∑ n( x′)* global _ sup port ( x′)  x′  (3.1) Dimana : x x’ n(x) n(x’)

: global frequent tree Tj dan tree juga cluster frequent dalam Ci : global frequent tree Tj yang bukan cluster frequent dalam Ci : weight (bobot) support x dari Tj : weight (bobot) support x’ dari Tj.

DATA UJI COBA Untuk mengukur kinerja dari sistem klasterisasi ini dilakukan uji coba. Data uji coba berupa kumpulan file-file XML yang berada dalam sebuah direktori tertentu. Sebagian besar dataset ysng digunakan diperoleh dari internet [BDL-01]. Tabel 5.1 menunjukkan karakteristik masing-masing dataset. Tabel 1. Spesifikasi Data Uji Coba

No 1 2 3 4

Nama dataset DT_1 DT_3 DT_4 DT_5

Jumlah File 6 9 15 32

Jumlah Node 5 13 12 8

Kedalaman Dokumen 1 3 2 dan 3 1

Size (Byte) 24.576 36.864 61.440 135.168

Dataset DB_1 merupakan kumpulan dari dokumen XML dimana isi file tersebut tidak mempunyai simpul elemen (element node) yang sama, jika dipassing ke dalam sebuah tree setiap file XML yang ada dalam DT_1 hanya sampai level 1. Dataset DT_2 hampir sama dengan DT_1 perbedaannya adalah sebagian file XML dari dataset DT_2 mempunyai simpul elemen (element node) yang sama. Dataset DT_3 merupakan kumpulan dari dokumen XML yang memiliki kedalaman sampai level 3. Dataset DB_4 merupakan kumpulan dari dokumen XML yang memiliki kedalaman level 2 dan level 3.

Pelaksanaan Uji Coba Uji coba dilakukan pada dataset masukan yang telah diuraikan pada sub bab sebelumnya.

ISBN : 978-979-99735-6-6 C-22-7


Uji Coba Pengaruh Parameter Algoritma yang digunakan dalam klasterisasi ini memerlukan dua parameter input yaitu minimum support (minsup) dan minimum cluster support (minCsup). Sesuai dengan skenario uji coba pengaruh parameter maka pada tiap-tiap dataset dilakukan uji coba dengan memberikan nilai parameter minsup dan minCsup yang bervariasi. Dari uji coba yang telah dilakukan terhadap semua dataset dengan menggunakan variasi parameter inputan yang diberikan, dapat dilihat bahwa besar kecilnya nilai minsup merupakan support minimum untuk penggalian frequent tree dan merupakan suatu input mandatory. Uji Coba Validasi Tabel 2. Hasil Klaster Disjoint

Klaster conference, name -1 author (C1) Journal, name -1 author (C2) conference, name -1 author -1 publisher (C3) journal, name -1 author -1 publisher (C4)

Anggota klaster T0, T1 T3, T4 T2 T5

Tabel 3. Hasil perhitungan Similarity dan Inter_Cluster (iterasi ke- 1)

Pasangan klaster (Ci , Sim(C ← C ) Sim(C ← C ) Inter _ sim(Ca ↔ Cb ) i j j i Cj) C1 dan C2 0,96 0,96 0,96 C1 dan C3 1,45 2 1,70 C1 dan C4 0,91 1,01 0,96 Proses perhitungan similarity akan berhenti jika semua item berada dalam satu klaster.

Uji Coba Kinerja Berdasarkan pada pelaksanaan uji coba, dalam uji coba kinerja ini diujikan semua dataset untuk mengukur kecepatan aplikasi dalam melakukan klasterisasi. Nilai minsup digunakan variasi, yaitu 1%, 10%, 20%, 25%, 30%, 40%, 50%, 60%, 70% dan 80%. Sedangkan untuk parameter minCsup menggunakan variasi nilai 10% dan 60%. Uji coba dataset dilakukan sebanyak 10 kali untuk setiap parameter masukan yang bervariasi. Hasil uji coba ditunjukkan oleh gambar berikut : Dataset DT_1

Dataset DT_2

0.180 0.156 0.156

0.180

0.160

minCSup =60%

0.154 0.153

minCSup =10%

0.113 0.113

0.120

0.094

0.100 0.099 0.098

0.080

0.091

0.072 0.062 0.062 0.062

0.060 0.061 0.060 0.059 0.056

0.040 0.020

R u n n in g T im es (sec)

R u n n i n g T i m e (s e c )

0.140

0.160

0.163 0.159 0.167 0.163

0.140

0.144

0.138

minCsup =10%

0.147 0.145

minCsup =60%

0.120 0.100

0.084 0.084 0.083

0.080

0.085 0.085 0.085

0.060

0.064

0.056

0.067 0.058

0.040 0.020 0.000

0.000 1

10

20

30

40

50

60

70

1

80

Minimum Support

10

25

30

40

50

Minimum Support

ISBN : 978-979-99735-6-6 C-22-8

60

70

80


Dataset DT_3 4.500

Dataset DT_4 3.000

4.124 4.127

2.655

3.714 3.711 3.500

minCsup =10% minCsup =60%

3.000 2.500 2.000 1.500 1.000

0.592 0.577

2.500

R unning Tim es(sec)

R u n n in g T im es (sec)

4.000

0.000 1

10

25

30

40

50

60

70

minCsup =10% minCsup =60%

1.500

1.162 1 1.14

1.000

0.520 0.500

0.267 0.249 0.170 0.170 0.170 0.572 0.571 4 6 .2 0 0.243 0.169 0.168 0.166

0.500

0 2.26 2.000

6 0.50

0.361 8 0.34

0.000 1

80

10

25

0.263 0.210 0.193 0.177 0.138 5 0 0.18 0.17 0.134

2 0.25 0.200

30

40

50

60

70

80

Minimum Support

Minimum Support

Gambar 6. Grafik perbandingan parameter minsup dengan running time yang dibutuhkan pada dataset

KESIMPULAN DAN SARAN Kesimpulan Dari uji coba dapat diambil kesimpulan sebagai derikut : a. Besar kecilnya nilai minsup merupakan support minimum untuk penggalian frequent tree dan merupakan suatu input mandatory. Sedangkan nilai minCsup tidak memberikan pengaruh pada saat penggalian frequent tree tetapi parameter ini akan digunakan untuk dimana membedakan apakah suatu item merupakan frekuensi kluster. b. Berdasarkan hasil uji coba kinerja dari sistem klasterisasi didapatkan bahwa semakin kecil nilai minCsup maka running time yang dihasilkan semakin besar dikarenakan dengan minCsup yang besar maka akan semakin banyak frequent cluster support untuk setiap klaster yang mempengaruhi pada saat penghitungan score untuk melakukan pemecahan klaster (cluster disjoint) c. Metode kita terdiri dari 3 tahap yaitu menemukan global frequent tree, melakukan klasterisasi awal, melakukan pemecahan klaster (cluster disjoint) dan prunning (yang digunakan untuk menyusun dendogram). Masalah penggalian global frequent tree telah dipelajari secara intensif pada sumber data literature. Pada fase pembentukan klaster, matrik global frequent tree discan dua kali, satu untuk pembentukan klaster awal dan satu lagi untuk membuat klaster disjoint. Selama klaster awal diberi label oleh global frequent tree f yang mengandung dokumen ∑ f ∈F global _ sup port ( f ) untuk global_support (f), tahap ini membuat perhitungan penyusunan kluster dan score. Banyaknya kerja yang dilakukan ini tidak lebih dari perhitungan support dalam penggalian global frequent tree. Pada saat prunning hanya satu scan dari kluster. Untuk ringkasan, tahapannya menyangkut pembentukan klaster awal, pemecahan klaster (cluster disjoint) dan prunning tidak lagi mahal dibandingkan penggalian global frequent tree.

SARAN Klasterisasi dokumen menggunakan frequent tree yang telah dilakukan saat ini sangat tergantung dari jumlah frequent tree yang ditemukan, dari frequent tersebut

ISBN : 978-979-99735-6-6 C-22-9


dibentuk sebuah matrik (matrik global frequent tree) yang disimpan pada memori utama. Scalability mungkin menjadi suatu masalah pada kasus dimana data setnya terlalu luas. Arahan yang mungkin untuk penelitian ke depan adalah mengembangkan versi disk resident untuk data set yang sangat luas, contohnya Yahoo! Subjek hirarki dengan jutaan dokumen.

DAFTAR PUSTAKA DataBase systems and Logic Programming (DBLP) XML http://www.acm.org/sigmod/dblp/db/index.html, Februari 2001

record,

D. Sankoff, J. Kruskal, Time Warps (1999) , String Edits and Macromolecules, The Thory and Practice of Sequence Comparison, CSLI Publications. F. Beil, M. Ester, and X. Xu (2002), Frequent term-based text clustering. In Proc. 8th Int. Conf. on Knowledge Discovery and Data Mining (KDD)’2002, Edmonton, Alberta, Canada. Giudici Paolo (2003), Applied Data Mining Statistical Methods for Business and Industry, John Wiley & Sons Ltd Dunham. Margaret H., (2003), Data Mining Introductory and Advanced Topics, Prentice Hall, Pearson Education Inc. J. Han and M. Kamber (2006) , Data Mining Concepts and Techniques, 2nd edition, Morgan Kaufmann Publishers, San Francisco. Junaedi M, “Pengantar XML”, http://www.ilmukomputer.com Lian, Wang, David Wai-lok Cheung, Nikos Mamolius, Siu Ming Yiu, (Januari 2004) An Efficient and Scalable Algorithm for Clustering XMLDocuments By Structure, IEEE Transaction on Knowledge and data Engineering, vol. 16, no.1. Mohammed J. Zaki (Juli 2002), Efficiently Mining Frequent Trees in a Forest, Proc. Eighth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining. Mohammed J. Zaki (Agustus 2005), Efficiently Mining Frequent Trees in a Forest : Algorithms and Applications. IEEE Transaction on Knowledge and data Engineering, vol. 17, no.8. M. Steinbach, G. Karypis, and V. Kumar (2000), A Comparison Of Document Clustering Techniques. KDD Workshop on Text Mining’00, S. Abiteboul, H. Kaplan, dan T. Milo(Januari, 2001), Compact Labeling Schemes for Ancestor Queries, Proceedings ACM Symp. Discrete Algorithms. V. Vapnik (1995), The Nature of Statistical Learning Theory, Springer-Verlag Publisher, NY. Extensible Markup Language (XML) 1.0 http://www.w3.org/TR/2000/REC-xml-20001006

ISBN : 978-979-99735-6-6 C-22-10

(Edisi

Kedua),

PENGGALIAN FREQUENT TREES DALAM KLASTERISASI DOKUMEN XML

Recommend Documents