Ekstraksi Data Pada Halaman Web Menggunakan Partial Tree Alignment

Ekstraksi Data Pada Halaman Web Menggunakan Partial Tree Alignment

Web mining merupakan penggunaan teknik data mining untuk menemukan dan mengekstrak informasi dari dokumen dan layanan web . Tantangan dari web mining adalah jumlah informasi yang banyak untuk mempermudah akses dengan pengembalian data baik online maupun offline dari source teks dari web . Penelitian web mining terintegrasi dengan berbagai macam penelitian disiplin ilmu pengetahuan lainnya seperti Database (DB),Datamining , Information Retrieval ,Machine Learning (ML),Natural Language Process (NLP). Web mining dapat dibagi menjadi tiga kategori utama yaitu : content mining , usage mining ,dan structure mining .

Gambar Taksonomi web mining

Pada tugas akhir ini memfokuskan kepada web content mining. Web content mining yaitu ,merupakan apliakasi untuk ,me-mining , mengekstrak dan menggabungkan data, informasi dan pengetahuan yang bermanfaat dari isi halaman web data web content tediri dari :

1. Unstructured data (teks bebas).

2. Semi structured data (dokumen HTML).

3. More structured data (data pada table, DB yang dihasilkan halaman HTML).

Pada intinya web content mining mendeskripsikan penemuan informasi yang berguna dari data, dokumen atau isi web pada halaman web. Ada dua cara pandang yang berbeda dalam melakukan penelitian mengenai web content mining, yaitu :

1. Cara pandang database: cara pandang ini mencoba untuk memodelkan data pada web dan mengintegrasikannya agar dapat digunakan sebaik mungkin.

2. Cara pandang information retrieval: cara pandang ini membantu atau memperbaiki kualitas informasi yang ditemukan dalam web atau dengan kata lain menyaring informasi didasarkan pada keinginan pemakai.

Gambar  Cara pandang web content mining 

Web content mining kadangkala disebut juga web text mining karena isi teks lebih sering digunakan sebagai penelitian. Teknologi yang biasanya digunakan web content mining adalah NLP dan IR [13] tetapi pada tugas akhir ini hanya menggunakan IR saja. Kegunaan web content mining pada World Wide Web antara lain menemukan informasi yang relevan dan menciptakan pengetahuan dari informasi yang ada, sehingga informasi dalam jumlah yang banyak di situs web tetapi mudah untuk mengaksesnya. Informasi tersebut berupa semi-structured dengan kode HTML, yang mana biasanya halaman web berisi campuran informasi seperti main content (isi utama), iklan, navigation panel, copyright notice, logo, dan lain-lain. Sedangkan pada tugas akhir ini akan memanfaatkan teks dalam hal ini hanya tag string pada HTML yang akan di-mining. 

Konsep Mining Data Record

Ide pokok dari pemilihan algoritma MDR (Mining Data Records in web pages) pada tugas akhir ini karena lebih efektif dan efisien daripada metode otomatis yang sudah ada lainnya, seperti OMINI dan IEPAD. Efektif karena hanya melakukan dua pengamatan, yaitu mengamati data record yang berada pada halaman web dan algoritma pencocokan string. Sedangkan efisien karena hanya melakukan pencocokan string pada node children yang satu parent saja, contohnya pada Gambar 5, tidak seperti data record memulai dari TD* dan berakhir di TD#. Berdasarkan penelitian yang telah ada dengan menggunakan algoritma MDR untuk me-mining data record pada halaman web dapat menghasilkan akurasi yang jauh lebih bagus dibandingkan dengan OMINI dan IEPAD. 

Pada gambar 3 dapat dilihat pengertian secara umum sebuah data region dan sebuah data record. Sebuah data region adalah daerah yang sangat relevan dari halaman web, seperti daerah pada situs web yang berisi sebuah daftar produk membentuk daerah data. Sebuah data record adalah sekumpulan data yang bersama-sama merepresentasikan entitas bermakna yang berdiri sendiri, seperti daftar produk dalam data region pada situs web. Algoritma MDR termasuk teknik unsupervised learning, yaitu sistem diberikan hanya satu halaman web dengan banyak data record, kemudian sistem mengekstrak data secara otomatis.

Gambar  Halaman web yang menjelaskan data record dan data region

Menurut paper rujukan berasumsi bahwa data record pada halaman web biasanya terdapat pada tag HTML dalam bentuk yang berhubungan dengan tabel dan form, misalnya tag table, form, tr, td dan lain sebagainya. Pada tugas akhir ini, algoritma MDR didasarkan pada dua pengamatan, yaitu:

Gambar  Halaman web dengan dua data record 

1. Data region (atau data record region) adalah sekumpulan data record berisi deskripsi dari kelompok obyek serupa yang ditampilkan secara khusus pada halaman web dengan region berdekatan dan disusun menggunakan tag HTML yang serupa. Seperti Gambar 4 diatas, dua notebook ditampilkan pada satu region yang berdekatan serta disusun menggunakan tag HTML. 

2. Struktur bersarang dari tag HTML pada halaman web biasanya membentuk sebuah tag tree dan sekumpulan data record serupa dibentuk oleh beberapa node children dari sub-tree pada node parent yang sama. Contohnya pada Gambar 5, merupakan tag tree untuk halaman web pada gambar 4. Misalnya setiap notebook (atau sebuah data record) pada gambar 4 diekstrak ke dalam 5 node TR dengan bagian tree di bawah node parent TBODY yang sama pada Gambar 5, sehingga terdapat dua data record pada dua kotak garis putus-putus. 

Gambar  Contoh tag tree HTML dari halaman web pada Gambar 4 

Pada tugas akhir ini, untuk melakukan teknik mining data record pada sebuah halaman web terdapat tiga langkah, yaitu:

1. Membangunan HTML tag tree.

2. Mining data region dalam halaman web dengan menggunakan tag tree dan perbandingan string. Mining data region dilakukan terlebih dahulu, karena sangat susah dalam mining data record secara langsung. Oleh karena itu, mining data region dilakukan untuk mendapatkan data record di dalam data region tersebut. Contohnya, pada Gambar 5, menemukan satu data region di bawah node TBODY.

3. Mengidentifikasi data record dari setiap data region. Contohnya, pada Gambar 5, langkah ini menemukan data record 1 dan data record 2 pada data region di bawah node TBODY.

Membangun HTML Tag Tree

Pada tugas akhir ini, hanya menggunakan tag-tag dalam perbandingan string untuk menemukan data record. Kebanyakan tag-tag HTML bekerja dalam pasangan. Setiap pasang terdiri dari sebuah tag pembuka (opening tag) dan sebuah tag penutup (closing tag), masing-masing diindentifikasi dengan “< >” dan “</ >”. Dalam setiap pasangan tag dapat berhubungan dengan 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 dari tag dipertimbangkan menjadi satu node.

Mining Data Region

Langkah ini adalah me-mining setiap data region pada halaman web yang berisi data record serupa, tetapi tidak 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 membentuk sebuah data region. Dari setiap data region, akan mengidentifikasi data record yang sesungguhnya.

Node generalized (atau sebuah node kombinasi) dengan panjang r dimana terdiri dari r (r > 1) node pada HTML tag tree dengan dua karakteristik sebagai berikut:

1. Semua node yang mempunyai parent yang sama.

2. Node-node yang berdekatan.

Node generalized menjelaskan bahwa sebuah obyek (atau data record) mungkin terisi dalam node-node tag sibling yang jumlahnya lebih daripada satu. Node generalized berbeda dengan node tag. Sedangkan node tag adalah setiap node tag pada tag tree pada Gambar-5.

Data region adalah kumpulan dari dua atau lebih node generalized dengan mempunyai beberapa karakteristik sebagai berikut :

1. Semua node generalized mempunyai parent yang sama.

2. Semua node generalized mempunyai 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 ditentukan.

Pada Gambar, menunjukkan bahwa dapat membentuk dua node generalized. Pertama terdiri 5 node children dari TR awal untuk TBODY, dan kedua yaitu 5 node children dari TR berikutnya untuk TBODY. Meskipun node generalized pada data region mempunyai panjang yang sama (mempunyai jumlah node children yang sama dari satu parent pada tag tree) tetapi node dengan level terbawahnya dapat sangat berbeda.

Perbedaan antara node generalized dengan data region dijelaskan pada Gambar-6 dengan menggunakan sebuah tag tree buatan dan nomer ID yang menggambarkan node tag pada tag tree. Daerah gelap adalah node generalized. Node 5 dan 6 adalah node generalized dengan panjang 1 dan mendefinisikan data region dengan label 1 jika kondisi edit distance terpenuhi. Node 8, 9, dan 10 adalah node generalized dengan panjang 1 dan mendefinisikan data region dengan label 2 jika kondisi edit distance terpenuhi. Pasangan dari node (14, 15), (16, 17) dan (18, 19) adalah node generalized dengan panjang 2 dan mendefinisikan data region dengan label 3 jika kondisi edit distance terpenuhi.

Gambar  Ilustrasi dari node generalized dan data region 

Pada tugas akhir ini, mengasumsikan bahwa node-node membentuk sebuah data region dari parent yang sama. Contohnya, tidak seperti data region dimulai dari node 7 dan akan berakhir pada node 14. Sebuah node generalized mungkin bukan mempresentasikan sebuah data record, tetapi itu digunakan untuk menemukan data record.

Mengidentifikasi Data records

Data yang telah terbentuk dalam region-region (direpresentasikan dengan node generalized ) sangat bermacam-macam kombinasinya ,berikut 2 kasus utama dalam mengidentifikasi data record

1. Non – Contiguous Data Records : Case 1

Dalam beberapa halaman web dalam mendeskripsikan sebuah data object (record) tidak dapat dianalisis kedekatannya berdasarkan 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 kasus ini ,data regions terdiri dari dua generalized nodes, dimana masing-masing generalized nodes terdiri dari dua tag nodes (dua rows), yang mengindikasikan bahwa dua tag node (rows) tersebut diatas tidak ada kesamaan satu sama lain . Tetapi masing-masing tag node memiliki jumlah children node yang sama dan children node ini memiliki kesamaan satu sama lain. 

Untuk kasus ini kita dapat menulisnya menjadi satu row lists untuk nama yang diambil dari dua object dalam dua cells dan row lists selanjutnya. Sehingga dapat ditulis name 1,name 2,description 1,description 2,name 3,name 4, description 3, description 4.

Non-Contiguous Data Records:Case 2

Bentuk adjecent data regions yang mempunyai lebih dari satu non-contiguous data records 

Kasus diatas terdiri dari dua atau lebih data regions dari multiple data records ,diamana dalam gambar diatas row 1 dan row 2 tidak memiliki kesamaan satu sama lain, dimana bentuk row 1 dari sebuah data regions dan bentuk row 2 berasal dari data region yang berbeda. 

DATA EXTRACTION

Dalam data extraction ini kita akan menerapkan sebuah teknik yang dinamakan dengan partial tree alignment , yang kunci pokoknya adalah bagaimana mencocokkan corresponding data item atau field dari data semua data records. Ada dua langkah penting dalam 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 di susun ulang ke dalam single tree .Masing-masing data record ada kemungkinan memiliki lebih dari satu sub-trees dari sebuah original tag tree pada sebuah halaman , dan masing-masing data record mungkin tidak memiliki kesamaan (Case 1 dan Case 2 pada kasus Pengidentifikasian data record). Sub-step ini diperlukan untuk menyusun single tree untuk masing-masing data record(sebuah root node buatan yang dapat di tambah setiap saat). 

2. Partial tree aligment: tag trees dari semua data dalam masing-masing data region di aligned menggunakan metode partial alignment berdasarkan tree matching

Dalam data extraction akan melalui berbagai tahapan yaitu sebagai berikut:

Tree Edit Distance

Tahap tree edit distance adalah mengukur kesamaan antara dua trees A dan B(root trees yan telah terlabel terurut ) berdasarkan cost dalam sebuah minimum set dari operasi yang diperlukan untuk mentransform A kedalam B. Menurut formula klasik,kumpulan dari operasi yang digunakan untuk menentukan tree edit distance adat tiga tahap: node removal,node insertion ,node replacement. Sebuah cost biasanya di assign terlebih dahulu pada masing-masing operasi. 

Masalah tree edit distance adalah penemuan minimum-cost mapping antara dua tree ,berikut adalah salah satu contoh konsep mapping tersebut diatas:

Misalkan X adalah tree dan misalkan X[i] adalah node ke-i dari tree X dalam tahapan preorder . Mapping M antara tree A yang berukuran n1 dan tree B yang berukuran n2 adalah kumpulan dari pairs(i,j) yang telah terurut dari setiap tree ,berikut adalah algoritma untuk kondisi (i1,j1)(i2,j2) ε M :

(1) i1 = i2 iff j1 = j2;

(2) 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 saat melakukan mapping dan diurutkan antara sibling node dan hierarichal relation antara kedua node yang telah ada. Berikut adalah gambar yang menunjukan mapping .

Berikut beberapa algoritma yang telah dilakukan untuk mencari minimum set dari operasi untuk men-transform satu tree ke dalam lainnya,dimana dalam setiap formula memiliki kompleksitas kuadratik(O(n1n2h1h2)), dimana n1 dan n2 ukuran sebuah tree dan h1 dan h2 adalah kedalaman sebuah tree hal ini juga ditunjukan pada kasus tree yang tidak terurut. 

Simple Tree matching 

Pada umumnya mapping dapat dilakukan antara node a di tree A dan node b di tree B secara silang ,disini juga terdapat replacement node b di dalam A node h di dalam B. Dalam kasus ini kita menggunakan restricted matching algorithm ,yang pertama di usulkan untuk membandingkan dua program computer dalam software engineering.Algoritma ini disebut dengan simple tree matching (STM). STM ini mengevaluasi similarity dari dua trees yang menghasilkan maximum matching dalam sebuah dynamic programming dengan complexity O(n1.n2),dimana n1 dan n2 ukuran dari trees A dan B (tidak menggunakan replacement dan no level crossing masih diijinkan). 

Missal A dan B dua buah tree dan i ε A,j ε B adalah node di A dan B .A matching antara dua trees ditujukan untuk mapping M dimana setiap pasangan (i,j) ε M dan i dan j adalah non-root nodes , (parents(i),parent(j)) ε M . A maximum matching adalah matching dengan jumlah pairs maximum.

Misal A = <RA,A1,A2,…Am> dan B =< RB,B1,B2,…Bm > dua trees ,dimana RA dan RB adalah root dari A dan B dan Ai,Aj adalah level pertama sub trees ke i dan j dari A dan B . ketika RA dan RB terdiri dari identical symbol , maximum matching antara A dan B adalah MA,B+1 ,dimana MA,B adalah maximum matching antara < A1,A2,…Am> dan <B1,B2,…Bm> . MA,B dapat diperoleh dari dynamic programming scheme:

1. Jika maximum matching antara Am dan Bm lebih besar dari pada maximum matching antara Am dan Bi(1≤iMA,B adalah maximum matching antara < A1,A2,…Am-1> dan <B1,B2,…Bm-1> ditambah maximum matching antara Am dan Bm.

2. Terkadang , MA,B adalah maximum matching antara < A1,A2,…Am> dan <B1,B2,…Bn-1> atau antara < A1,A2,…Am-1> dan <B1,B2,…Bn>

Dalam algoritma Simple tree matching , root dari A dan B dibandingkan pertama kali (line 1). Jika root terdiri dari distinct symbol maka dua tree tersebut tidak memiliki kesamaan sama sekali. Jika root terdiri dari identical symbol maka algoritma STM secara recursive menemukan maximum matching antara first-level sub-trees dari A dan B dan menyimpan hasilnya dalam matriks W (line 8). Berdasarkan pada matriks W , dynamic programming maximum matching antara dua tree A dan 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 dan N15 telah dahulu dibandingkan (compared first). Seteleh N1 dan N15 telah 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 berdasarkan pada matriks W1-15 dan masing-masing nilai masukan dalam W1-15 ,kemudian dikatakan bahwa W1-15 [i,j] adalah maximum matching antara first-level sub-trees ke i dan ke j pada A dan B ,dimana secara recursive dihitung berdasarkan 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 dengan mengisi nilai nol pada column dan row nya.(Note : untuk matriks M dan W yang sedang dalam penghitungan diberi garis bawah ).

Selama proses matching (atau setelah proses matching) ,kita dapat men-trace back matriks M untuk menemukan node yang cocok atau memiliki kesamaan(matched /aligned) dari dua tree,ketika menemukan lebih dari satu yang cocok untuk node yang memberikan nilai maximum. Kemudian kita pilih satu yang paling rendah kedalamannya dalam tree. Contoh ,node c dalam tree A dapat dilakukan pencocokan pada waktu pertama atau akhir node c pada tree B, setelah itu pilih node c yang pertama dalam B . heuristic ini digunakan untuk visual effectiveness dalam halaman web. Jika sebuah node yang paling dekat adalah node x dalam tree A cocok maka lanjutkan pada node y pada tree B ,biasanya akan terdapat beberapa tag sebelum x. Heuristic ini sejauh ini telah efektif dalam beberapa experiment.

Two trees with more than one possible match

Multiple Alignment

Setiap data region yang memiliki multiple data record pada suatu halaman selain akan dilakukan proses align menggunakan multiple tag trees , juga akan dimasukan ke dalam sebuah single table dalam database yang berkorespondensi satu sama lain dengan data items/field dalam kolom yang sama dalam table.Dimana data table ini masing-masing rownya merepresentasikan dalam sebuuh tree(data record),dan masing-masing kolomnya merepresnetasikan data field di masing-masing data record. 

Berikut ini adalah salah satu algoritma yang ada untuk menangani multiple sequences / trees yaitu Multiple alignment method , Multiple alignment method adalah sebuah metode yang menggunakan multidimensional dynamic programming ,metode ini sudah optimal tetapi membutuhkan kompleksitas waktu yang besar (exponential) dan tidak praktis,dan banyak juga metode heuristic untuk menangani masalah ini salah satunya adalah Center string method yang akan digunakan dalam multiple sequence alignment untuk menangani masalah particular heuristic method .

Dalam Center string method ,sequence adalah xc dimana minimasinya adalah (D(xi,xc) adalah jarak antara dua 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 ,waktu untuk menemukan center O(k2n2) dan waktu masing-masing langkah iterative pada pair-wise alignment adalah O(n2) . Dapat dikatakan untuk time costnya adalah O(k2n2).

Dalam mengukur similarity, kita tentukan center tree Tc dan meng-align tree lainnya dengan Tc ,ada dua cara untuk mengimplementasikan teknik ini 

Pertama ,walaupun pada setiap algoritma memiliki waktu kompleksitas polynomial , tetapi berjalan dengan lambat untuk halaman yang terdiri pada banyak data record atau data record yang memiliki banyak atribut. 

Yang kedua ,jika center tree tidak mempunyai bagian data item ,data record yang lain yang terdiri dari data yang sama pada center tree tidak perlu mengalami proses alignment . 

Partial Tree Alignment

Partial Alignment of two trees

Missal dua buah tree Ts dan Ti telah melakukan proses matching ,beberapa node Ti dilakukan proses align dengan menghubungkan node dalam Ts (saling sama satu sama lain).untuk setiap node Ti yang tidak cocok akan dimasukan ke dalam Ts . Ada dua kemungkinan ketika memasukan node ni dari Ti ke dalam seed tree Ts tergantung apakah lokasi dalam Ts benar-benar unik untuk dimasukan node ni .Faktanya disini bukan hanya membandingkan dalam single node ni , hal ini di lakukan untuk mengatasi jika ada node yang unmatched masuk kedalam parent dari Ti (ni .. nj).

Assumsi bahwa parent node (ni .. nj) mempunyai kecocokan dalam Ts dan kita ingin memasukan (ni .. nj) kedalam Ts dibawah node parentnya. Kita hanya dapat memasukan (ni .. nj) kedalam Ts jika posisi untuk memasukan (ni .. nj) adalah bersifat unik dalam Ts . Sebaliknya kita tidak akan bisa memasukan kedalam Ts dan unalignment kiri yang bersifat partial.

Untuk menentukan lokasi unik agar kita dapat memasukan node (ni .. nj) 

1. Jika (ni .. nj) mempunyai dua tetangga sibling dalam Ti ,satu di sisi kanan dan satu di sisi kiri yang cocok dengan consecutive sibling pada Ts . gambar dibawah ini akan menunjukan keadaan ini, yang memberikan satu bagian pada Ts dan satu bagian dalam Ti . Kita dapat melihat node c dan node d (consecutive sibling) dalam Ti dan dimasukan kedalam Ts antara node b dan e (matched ) .

2. Jika (ni .. nj) mempunyai satu tetangga kiri x dalam Ti dan x cocok dengan node kanan x dalam Ts ,kemudian (ni .. nj) dimasukan setelah node x dalam Ts.

3. Jika (ni .. nj) mempunyai satu tetangga kanan x dalam Ti dan x cocok dengan node kiri x dalam Ts ,kemudian (ni .. nj) dimasukan sebelum node x dalam Ts.

Terkadang kita tidak dapat memiliki lokasi node yang tidak unik untuk 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