Ekstraksi Data Pada Halaman Web Menggunakan Partial Tree Alignment
Web mining merupakan penggunaan teknik data mining buat menemukan serta mengekstrak fakta dari dokumen dan layanan web . Tantangan berdasarkan web mining merupakan jumlah keterangan yg poly untuk mempermudah akses dengan pengembalian data baik online juga offline berdasarkan source teks dari web . Penelitian web mining terintegrasi menggunakan berbagai macam penelitian disiplin ilmu pengetahuan lainnya misalnya Database (DB),Datamining , Information Retrieval ,Machine Learning (ML),Natural Language Process (NLP). Web mining dapat dibagi menjadi tiga kategori primer yaitu : content mining , usage mining ,serta structure mining .
Gambar Taksonomi web mining
Pada tugas akhir ini memfokuskan kepada web content mining. Web content mining yaitu ,adalah apliakasi buat ,me-mining , mengekstrak serta menggabungkan data, informasi dan pengetahuan yang berguna berdasarkan isi halaman web data web content tediri berdasarkan :
1. Unstructured data (teks bebas).
2. Semi structured data (dokumen HTML).
3. More structured data (data pada table, DB yang dihasilkan page HTML).
Pada intinya web content mining menggambarkan inovasi fakta yg bermanfaat dari data, dokumen atau isi web dalam page web. Ada 2 cara pandang yang tidak sinkron dalam melakukan penelitian mengenai web content mining, yaitu :
1. Cara pandang database: cara pandang ini mencoba buat memodelkan data dalam web serta mengintegrasikannya supaya dapat digunakan sebaik mungkin.
2. Cara pandang information retrieval: cara pandang ini membantu atau memperbaiki kualitas kabar yang ditemukan pada web atau dengan istilah lain menyaring warta didasarkan dalam keinginan pemakai.
Gambar Cara pandang web content mining
Web content mining kadangkala disebut juga web text mining karena isi teks lebih seringkali digunakan sebagai penelitian. Teknologi yang umumnya dipakai web content mining merupakan NLP dan IR [13] tetapi pada tugas akhir ini hanya menggunakan IR saja. Kegunaan web content mining dalam World Wide Web antara lain menemukan warta yg relevan serta membentuk pengetahuan dari berita yang terdapat, sehingga berita dalam jumlah yg banyak di situs web tetapi mudah buat mengaksesnya. Informasi tadi berupa semi-structured menggunakan kode HTML, yg mana umumnya page web berisi adonan liputan seperti main content (isi primer), iklan, navigation panel, hak cipta notice, logo, dan lain-lain. Sedangkan pada tugas akhir ini akan memanfaatkan teks pada hal ini hanya tag string pada HTML yang akan pada-mining.
Konsep Mining Data Record
Ide pokok dari pemilihan prosedur pemecahan MDR (Mining Data Records in web pages) dalam tugas akhir ini karena lebih efektif dan efisien daripada metode otomatis yg telah terdapat lainnya, misalnya OMINI dan IEPAD. Efektif lantaran hanya melakukan dua pengamatan, yaitu mengamati data record yang berada dalam page web dan algoritma pencocokan string. Sedangkan efisien karena hanya melakukan pencocokan string dalam node children yang satu parent saja, contohnya dalam Gambar lima, tidak seperti data record memulai dari TD* dan berakhir di TD#. Berdasarkan penelitian yang telah ada menggunakan memakai algoritma MDR buat me-mining data record dalam halaman web dapat menghasilkan akurasi yang jauh lebih rupawan dibandingkan dengan OMINI dan IEPAD.
Pada gambar tiga dapat ditinjau pengertian secara generik sebuah data region serta sebuah data record. Sebuah data region adalah daerah yang sangat relevan berdasarkan page web, seperti wilayah pada situs web yg berisi sebuah daftar produk membentuk wilayah data. Sebuah data record adalah sekumpulan data yg beserta-sama merepresentasikan entitas bermakna yg berdiri sendiri, misalnya daftar produk pada data region pada situs web. Algoritma MDR termasuk teknik unsupervised learning, yaitu sistem diberikan hanya satu halaman web dengan banyak data record, lalu sistem mengekstrak data secara otomatis.
Gambar Halaman web yang menjelaskan data record dan data region
Menurut paper rujukan berasumsi bahwa data record pada laman web biasanya masih ada pada tag HTML pada bentuk yg berhubungan dengan tabel serta form, misalnya tag table, form, tr, td serta lain sebagainya. Pada tugas akhir ini, prosedur pemecahan MDR didasarkan pada dua pengamatan, yaitu:
Gambar Halaman web dengan 2 data record
1. Data region (atau data record region) merupakan sekumpulan data record berisi deskripsi dari kelompok obyek serupa yg ditampilkan secara spesifik dalam laman web menggunakan region berdekatan dan disusun menggunakan tag HTML yg serupa. Seperti Gambar 4 diatas, dua notebook ditampilkan dalam satu region yg berdekatan serta disusun menggunakan tag HTML.
2. Struktur bersarang menurut tag HTML dalam laman web umumnya membentuk sebuah tag tree serta sekumpulan data record serupa dibentuk oleh beberapa node children dari sub-tree pada node parent yg sama. Contohnya dalam Gambar 5, adalah tag tree buat laman web dalam gambar 4. Misalnya setiap notebook (atau sebuah data record) pada gambar 4 diekstrak ke dalam lima node TR menggunakan bagian tree pada bawah node parent TBODY yg sama pada Gambar lima, sehingga masih ada 2 data record pada 2 kotak garis putus-putus.
Gambar Contoh tag tree HTML dari laman web dalam Gambar 4
Pada tugas akhir ini, buat melakukan teknik mining data record dalam sebuah page web terdapat 3 langkah, yaitu:
1. Membangunan HTML tag tree.
2. Mining data region dalam halaman web menggunakan menggunakan tag tree dan perbandingan string. Mining data region dilakukan terlebih dahulu, lantaran sangat susah dalam mining data record secara langsung. Oleh karenanya, mining data region dilakukan buat mendapatkan data record di dalam data region tadi. Contohnya, dalam Gambar lima, menemukan satu data region pada bawah node TBODY.
3. Mengidentifikasi data record dari setiap data region. Contohnya, dalam Gambar 5, langkah ini menemukan data record 1 serta data record dua pada data region di bawah node TBODY.
Membangun HTML Tag Tree
Pada tugas akhir ini, hanya menggunakan tag-tag dalam perbandingan string buat menemukan data record. Kebanyakan tag-tag HTML bekerja pada pasangan. Setiap pasang terdiri berdasarkan sebuah tag pembuka (opening tag) dan sebuah tag epilog (closing tag), masing-masing diindentifikasi menggunakan “< >” serta “ >”. Dalam setiap pasangan tag dapat herbi pasangan tag yang lain, sehingga mengakibatkan blok bersarang pada kode HTML. Pembangunan sebuah tag tree dengan menggunakan kode HTML secara natural. Pada tag tree, setiap pasang menurut tag dipertimbangkan menjadi satu node.
Mining Data Region
Langkah ini merupakan me-mining setiap data region pada halaman web yang berisi data record serupa, namun nir dapat me-mining data record secara langsung, karena susah, pertama kali yang dilakukan adalah me-mining node generalized pada halaman web. Sekumpulan node generalized yang berdekatan membangun sebuah data region. Dari setiap data region, akan mengidentifikasi data record yg sesungguhnya.
Node generalized (atau sebuah node kombinasi) menggunakan panjang r dimana terdiri berdasarkan r (r > 1) node pada HTML tag tree menggunakan dua ciri menjadi berikut:
1. Semua node yg memiliki parent yg sama.
2. Node-node yang berdekatan.
Node generalized mengungkapkan bahwa sebuah obyek (atau data record) mungkin terisi pada node-node tag sibling yang jumlahnya lebih daripada satu. Node generalized tidak selaras menggunakan node tag. Sedangkan node tag adalah setiap node tag dalam tag tree pada Gambar-lima.
Data region adalah formasi menurut dua atau lebih node generalized menggunakan memiliki beberapa karakteristik menjadi berikut :
1. Semua node generalized mempunyai parent yang sama.
2. Semua node generalized memiliki panjang yang sama.
3. Semua node generalized yang berdekatan.
4. Normalisasi edit distance (perbandingan string) antara node generalized yang berdekatan lebih kecil daripada batasan yang telah dipengaruhi.
Pada Gambar, memberitahuakn bahwa dapat membentuk dua node generalized. Pertama terdiri 5 node children berdasarkan TR awal buat TBODY, dan kedua yaitu 5 node children dari TR berikutnya buat TBODY. Meskipun node generalized pada data region mempunyai panjang yg sama (memiliki jumlah node children yang sama dari satu parent pada tag tree) namun node menggunakan level terbawahnya dapat sangat tidak sama.
Perbedaan antara node generalized dengan data region dijelaskan dalam Gambar-6 dengan menggunakan sebuah tag tree buatan serta nomer ID yang mendeskripsikan node tag dalam tag tree. Daerah gelap merupakan node generalized. Node lima dan 6 merupakan node generalized menggunakan panjang 1 dan mendefinisikan data region dengan label 1 bila kondisi edit distance terpenuhi. Node 8, 9, dan 10 merupakan node generalized dengan panjang 1 dan mendefinisikan data region dengan label 2 bila syarat edit distance terpenuhi. Pasangan menurut node (14, 15), (16, 17) dan (18, 19) adalah node generalized menggunakan panjang 2 dan mendefinisikan data region dengan label 3 jika kondisi edit distance terpenuhi.
Gambar Ilustrasi menurut node generalized serta data region
Pada tugas akhir ini, mengasumsikan bahwa node-node membangun sebuah data region dari parent yg sama. Contohnya, nir seperti data region dimulai berdasarkan node 7 dan akan berakhir dalam node 14. Sebuah node generalized mungkin bukan mempresentasikan sebuah data record, namun itu dipakai untuk menemukan data record.
Mengidentifikasi Data records
Data yang telah terbentuk dalam region-region (direpresentasikan dengan node generalized ) sangat beragam kombinasinya ,berikut 2 masalah utama dalam mengidentifikasi data record
1. Non – Contiguous Data Records : Case 1
Dalam beberapa page web pada menggambarkan sebuah data object (record) nir dapat dianalisis kedekatannya dari HTML code-nya(contiguous segment) . Amati dalam gambar berikut
Multiple-record data region: masing-masing node terdiri lebih dari satu non-contiguous data record
Dalam perkara ini ,data regions terdiri menurut 2 generalized nodes, dimana masing-masing generalized nodes terdiri menurut dua tag nodes (dua rows), yg menandakan bahwa 2 tag node (rows) tadi diatas tidak terdapat kecenderungan satu sama lain . Tetapi masing-masing tag node memiliki jumlah children node yg sama serta children node ini mempunyai kecenderungan satu sama lain.
Untuk kasus ini kita bisa menulisnya menjadi satu row lists untuk nama yang diambil menurut dua object pada 2 cells dan row lists selanjutnya. Sehingga bisa ditulis name 1,name 2,description 1,description 2,name 3,name 4, description tiga, description 4.
Non-Contiguous Data Records:Case 2
Bentuk adjecent data regions yg mempunyai lebih berdasarkan satu non-contiguous data records
Kasus diatas terdiri berdasarkan dua atau lebih data regions dari multiple data records ,diamana pada gambar diatas row 1 dan row 2 tidak memiliki kesamaan satu sama lain, dimana bentuk row 1 dari sebuah data regions serta bentuk row 2 asal dari data region yang berbeda.
DATA EXTRACTION
Dalam data extraction ini kita akan menerapkan sebuah teknik yg dinamakan dengan partial tree alignment , yang kunci pokoknya merupakan bagaimana mencocokkan corresponding data item atau field menurut data seluruh data records. Ada dua langkah penting pada data extraction:
1. Membuat satu root tag tree untuk masing-masin data record :
Setelah semua data record telah teridentifikasi, sub-trees pada masing data records pada susun ulang ke dalam single tree .masing-masing data record terdapat kemungkinan memiliki lebih dari satu sub-trees menurut sebuah original tag tree pada sebuah halaman , serta masing-masing data record mungkin nir memiliki kesamaan (Case 1 serta Case 2 dalam perkara Pengidentifikasian data record). Sub-step ini diharapkan buat menyusun single tree buat masing-masing data record(sebuah root node protesis yang dapat di tambah setiap ketika).
2. Partial tree aligment: tag trees menurut seluruh data dalam masing-masing data region di aligned menggunakan metode partial alignment menurut tree matching
Dalam data extraction akan melalui banyak sekali tahapan yaitu sebagai berikut:
Tree Edit Distance
Tahap tree edit distance merupakan mengukur kesamaan antara dua trees A serta B(root trees yan sudah terlabel terurut ) berdasarkan cost dalam sebuah minimum set menurut operasi yang dibutuhkan buat mentransform A kedalam B. Menurut formula klasik,deretan dari operasi yang dipakai buat memilih tree edit distance adat 3 tahap: node removal,node insertion ,node replacement. Sebuah cost umumnya di assign terlebih dahulu dalam masing-masing operasi.
Masalah tree edit distance merupakan inovasi minimum-cost mapping antara 2 tree ,berikut adalah keliru satu contoh konsep mapping tersebut diatas:
Misalkan X merupakan tree serta misalkan X[i] merupakan node ke-i berdasarkan tree X dalam tahapan preorder . Mapping M antara tree A yg ukuran n1 dan tree B yg berukuran n2 merupakan gugusan menurut pairs(i,j) yang sudah terurut berdasarkan setiap tree ,berikut merupakan prosedur pemecahan buat syarat (i1,j1)(i2,j2) ε M :
(1) i1 = i2 iff j1 = j2;
(dua) A[i1] is on the left of A[i2] iff B[j1] is on the left B[j2];
(3) A[i1] is an ancestor of A[i2] iff B[j1] is an ancestor of B[j2].
Masing-masin node dihilangkan satu kali ketika melakukan mapping dan diurutkan antara sibling node dan hierarichal relation antara kedua node yang sudah terdapat. Berikut merupakan gambar yg menandakan mapping .
Berikut beberapa algoritma yg telah dilakukan buat mencari minimum set menurut operasi buat men-transform satu tree ke dalam lainnya,dimana pada setiap formula mempunyai kompleksitas kuadratik(O(n1n2h1h2)), dimana n1 serta n2 berukuran sebuah tree serta h1 serta h2 adalah kedalaman sebuah tree hal ini pula ditunjukan dalam kasus tree yang nir terurut.
Simple Tree matching
Pada umumnya mapping dapat dilakukan antara node a di tree A dan node b di tree B secara silang ,disini pula terdapat replacement node b di pada A node h di pada B. Dalam kasus ini kita menggunakan restricted matching algorithm ,yang pertama di usulkan untuk membandingkan 2 program computer dalam aplikasi engineering.algoritma ini diklaim menggunakan simple tree matching (STM). STM ini mengevaluasi similarity dari dua trees yang membentuk maximum matching dalam sebuah dynamic programming dengan complexity O(n1.N2),dimana n1 serta n2 ukuran dari trees A dan B (nir menggunakan replacement serta no level crossing masih diijinkan).
Missal A dan B 2 butir tree serta i ε A,j ε B adalah node pada A dan B .A matching antara 2 trees ditujukan buat mapping M dimana setiap pasangan (i,j) ε M serta i dan j merupakan non-root nodes , (parents(i),parent(j)) ε M . A maximum matching adalah matching menggunakan jumlah pairs maximum.
Misal A = dan B =< RB,B1,B2,…Bm > 2 trees ,dimana RA serta RB adalah root dari A dan B dan Ai,Aj merupakan level pertama sub trees ke i serta j berdasarkan A serta B . Saat RA dan RB terdiri menurut identical symbol , maximum matching antara A dan B adalah MA,B+1 ,dimana MA,B adalah maximum matching antara < A1,A2,…Am> serta . MA,B bisa diperoleh menurut dynamic programming scheme:
1. Apabila maximum matching antara Am dan Bm lebih akbar dari dalam maximum matching antara Am serta Bi(1≤iMA,B merupakan maximum matching antara < A1,A2,…Am-1> dan ditambah maximum matching antara Am serta Bm.
2. Terkadang , MA,B adalah maximum matching antara < A1,A2,…Am> dan atau antara < A1,A2,…Am-1> dan
Dalam prosedur pemecahan Simple tree matching , root berdasarkan A serta B dibandingkan pertama kali (line 1). Apabila root terdiri dari distinct symbol maka dua tree tadi nir memiliki kecenderungan sama sekali. Apabila root terdiri dari identical symbol maka prosedur pemecahan STM secara recursive menemukan maximum matching antara first-level sub-trees menurut A serta B serta menyimpan hasilnya pada matriks W (line 8). Berdasarkan pada matriks W , dynamic programming maximum matching antara 2 tree A serta B.
1. Algorithm: Simple_Tree_Matching(A, B)
2. If the roots of the two trees A and B contain distinct symbols
3. Then return (0);
4. Else m:= the number of first-level sub-trees of A;
5. N:= the number of first-level sub-trees of B;
6. Initialization: M[i, 0]:= 0 for i = 0, …, m;
7. M[0, j] := 0 for j = 0, …, n;
8. For i = 1 to m do
9. For j = 1 to n do
10. M[i,j]:=max(M[i,j-1], M[i-1, j], M[i-1, j-1]+W[i, j]);
11. Where W[i,j] = Simple_Tree_Matching(Ai, Bj)
12. Endfor;
13. Endfor;
14. Return (M[m, n]+1)
15. Endif
(A) Tree A; (B) Tree B; (C) M matrix for the first level sub-trees of N1 and N15; (D) W matrix for the first level sub-trees of N1 and N15; (E)-(H) M matrixes and W matrixes for the lower level sub-trees.
Untuk menemukan maximum matching antara tree A dan B ,dimana rootnya ,N1 serta N15 telah dahulu dibandingkan (compared first). Seteleh N1 serta N15 sudah masuk kedalam identical symbol , nilai M1-15[4,2]+1 dikembalikan sebagai nilai maximum matching antara tree A dan B (line 11) . M1-15 di hitung menurut pada matriks W1-15 dan masing-masing nilai masukan dalam W1-15 ,kemudian dikatakan bahwa W1-15 [i,j] merupakan maximum matching antara first-level sub-trees ke i dan ke j pada A dan B ,dimana secara recursive dihitung dari matriks M . Contoh W1-15 [4,2] dihitung secara recursive dengan membangun matriks (E)-(H) ,semua cell yang relevant akan dikumpulkan .matriks M akan di inisialisasi menggunakan mengisi nilai nol dalam column serta row nya.(Note : buat matriks M serta W yang sedang pada penghitungan diberi garis bawah ).
Selama proses matching (atau selesainya proses matching) ,kita dapat men-trace back matriks M buat menemukan node yg cocok atau mempunyai kesamaan(matched /aligned) menurut 2 tree,saat menemukan lebih menurut satu yg cocok buat node yg menaruh nilai maximum. Kemudian kita pilih satu yang paling rendah kedalamannya pada tree. Contoh ,node c dalam tree A dapat dilakukan pencocokan pada ketika pertama atau akhir node c pada tree B, selesainya itu pilih node c yg pertama pada B . Heuristic ini dipakai untuk visual effectiveness pada page web. Jika sebuah node yang paling dekat merupakan node x dalam tree A cocok maka lanjutkan dalam node y dalam tree B ,umumnya akan terdapat beberapa tag sebelum x. Heuristic ini sejauh ini sudah efektif pada beberapa experiment.
Two trees with more than one possible match
Multiple Alignment
Setiap data region yg mempunyai multiple data record dalam suatu page selain akan dilakukan proses align menggunakan multiple tag trees , jua akan dimasukan ke dalam sebuah single table dalam database yg berkorespondensi satu sama lain dengan data items/field dalam kolom yang sama pada table.dimana data table ini masing-masing rownya merepresentasikan dalam sebuuh tree(data record),serta masing-masing kolomnya merepresnetasikan data field di masing-masing data record.
Berikut ini merupakan salah satu prosedur pemecahan yg terdapat buat menangani multiple sequences / trees yaitu Multiple alignment method , Multiple alignment method merupakan sebuah metode yang memakai multidimensional dynamic programming ,metode ini sudah optimal namun membutuhkan kompleksitas waktu yang besar (exponential) dan nir praktis,dan poly pula metode heuristic buat menangani perkara ini keliru satunya merupakan Center string method yang akan digunakan pada multiple sequence alignment buat menangani masalah particular heuristic method .
Dalam Center string method ,sequence merupakan xc dimana minimasinya merupakan (D(xi,xc) adalah jarak antara 2 String) ∑ D(xi,xc) ,kemudian pair-wise alignment ditunjukan dalam (xi,xc) dimana i≠c . Asumsi ada k sequences dan semua sequences mempunyai panjang n ,ketika buat menemukan center O(k2n2) serta saat masing-masing langkah iterative pada pair-wise alignment adalah O(n2) . Dapat dikatakan buat time costnya merupakan O(k2n2).
Dalam mengukur similarity, kita tentukan center tree Tc dan meng-align tree lainnya menggunakan Tc ,ada 2 cara buat mengimplementasikan teknik ini
Pertama ,walaupun dalam setiap algoritma mempunyai saat kompleksitas polynomial , tetapi berjalan dengan lambat buat halaman yang terdiri pada banyak data record atau data record yg memiliki poly atribut.
Yang kedua ,jika center tree nir mempunyai bagian data item ,data record yang lain yang terdiri berdasarkan data yang sama pada center tree tidak perlu mengalami proses alignment .
Partial Tree Alignment
Partial Alignment of two trees
Missal dua butir tree Ts serta Ti sudah melakukan proses matching ,beberapa node Ti dilakukan proses align dengan menghubungkan node pada Ts (saling sama satu sama lain).buat setiap node Ti yg tidak cocok akan dimasukan ke dalam Ts . Ada 2 kemungkinan ketika memasukan node ni menurut Ti ke pada seed tree Ts tergantung apakah lokasi pada Ts benar-sahih unik buat dimasukan node ni .faktanya disini bukan hanya membandingkan pada single node ni , hal ini pada lakukan buat mengatasi bila terdapat node yg unmatched masuk kedalam parent berdasarkan Ti (ni .. Nj).
Assumsi bahwa parent node (ni .. Nj) mempunyai kecocokan pada Ts dan kita ingin memasukan (ni .. Nj) kedalam Ts dibawah node parentnya. Kita hanya bisa memasukan (ni .. Nj) kedalam Ts jika posisi buat memasukan (ni .. Nj) merupakan bersifat unik dalam Ts . Sebaliknya kita nir akan bisa memasukan kedalam Ts serta unalignment kiri yang bersifat partial.
Untuk menentukan lokasi unik agar kita bisa memasukan node (ni .. Nj)
1. Jika (ni .. Nj) mempunyai 2 tetangga sibling pada Ti ,satu pada sisi kanan serta satu pada sisi kiri yg cocok menggunakan consecutive sibling dalam Ts . Gambar dibawah ini akan menerangkan keadaan ini, yg memberikan satu bagian dalam Ts dan satu bagian pada Ti . Kita bisa melihat node c dan node d (consecutive sibling) dalam Ti serta dimasukan kedalam Ts antara node b serta e (matched ) .
2. Jika (ni .. Nj) mempunyai satu tetangga kiri x pada Ti dan x cocok dengan node kanan x dalam Ts ,kemudian (ni .. Nj) dimasukan setelah node x dalam Ts.
3. Jika (ni .. Nj) memiliki satu tetangga kanan x pada Ti dan x cocok menggunakan node kiri x pada Ts ,kemudian (ni .. Nj) dimasukan sebelum node x pada Ts.
Terkadang kita tidak bisa memiliki lokasi node yang nir unik buat proses pencocokan node antara Ti dan Ts
Figure 1 Expanding the seed tree: (A) and (B) Unique expansion; (C) Insertion ambiguity.
Full Algorithm
Algorithm PartialTreeAlignment(S)
1. Sort trees in S in descending order according to the number of data items that are not aligned;
2. Ts = the first tree (which is the largest) and delete it from S;
3. Flag = false; R = ∅; I = false;
4. While (S ≠ ∅)
5. Ti = select and delete next tree from S;
6. Simple_Tree_Matching(Ts, Ti);
7. L = alignTrees(Ts, Ti); // based on the result from line 6
8. If Ti is not completely aligned with Ts then
9. I = InsertIntoSeed(Ts, Ti);
10. If not all unaligned items in Ti are inserted into Ts then
11. Insert Ti into R;
12. Endif;
13. Endif;
14. If (L has new alignment) or (I is true) then
15. Flag = true
16. Endif;
17. If S = ∅ and flag = true then
18. S = R; R = ∅;
19. Flag = false; I = false
20. Endif;
21. Endwhile;
22. Output data fields from each Ti to the data table based on the alignment results.
Ilustrasi