4/23/13
Text dan Web Mining - TI UKDW
1
ANALISIS LINK Budi Susanto
Text dan Web Mining - TI UKDW
2
Tujuan • memahami karakteristik link antar laman yang dapat
dimodelkan sebagai graf. • memahami algoritma PageRank • memahami Hubs and Authority
1
4/23/13
Text dan Web Mining - TI UKDW
3
Struktur Web • struktur hypertextual memberikan sebuah jaringan
informasi
• node mewakili laman yang berisi informasi • link menyatakan relasi antar node. • Bentuk hypertextual pertama adalah konsep citation di
antara book atau artikel ilmiah. • node mewakili buku/artikel
• edge mewakili citation dari satu karya ke lainnya. • perbedaan utama dengan web: citation dikelola lebih kuat berdasar
waktu. • citation mengarah pada karya sebelumnya.
• Bentuk hypertextual lain adalah cross-references dalam
ensiklopedia
Text dan Web Mining - TI UKDW
4
Contoh citation hypertextual
2
4/23/13
Text dan Web Mining - TI UKDW
5
Contoh Cross Reference network
Text dan Web Mining - TI UKDW
6
Pemikiran Vannevar Bush • Bush menyatakan bahwa informasi yang tersimpan pada
buku, perpustakaan, atau bahkan memori komputer adalah linear. • berisi koleksi item yang diurutkan dalam urutan tertentu.
• Bush membayangkan sebuah hypothetical prototype,
disebut Memex, yang fungsinya serupa dengan Web • berisi bentuk digital dari pengetahuan manusia yang saling
berhubungan dengan associative link.
• Pemikiran tentang Web: • web sebagai ensiklopedia universal, • web sebagai sistem socio-economic raksasa, • web sebagai otak global.
3
4/23/13
Text dan Web Mining - TI UKDW
7
Web sebagai Directed Graph • Tautan navigasi membentuk struktur backbone dari Web,
daripada memperkaya isi. • tautan antar laman Web diterapkan sebagai bentuk graf berarah, mengingat bentuk tautan dapat bersifat asimetrik. • blog Anda memiliki link ke UKDW, namun tidak tentu UKDW
memiliki link ke blog Anda.
Text dan Web Mining - TI UKDW
8
Contoh Web Directed Graph
4
4/23/13
Text dan Web Mining - TI UKDW
9
Strongly Connected • Sebuah directed graph dikatakan terhubung kuat jika
terdapat sebuah jalur dari setiap node ke setiap node lainnya. • Contoh pada slide 8 bukanlah directed graph yang terhubung kuat. Mengapa? • Jika sebuah directed graph tidak terhubung kuat, maka perlu diperhatikan atribut lain, yaitu: reachability. • mengenali node mana saja yang “reachable” dari node lain melalui
jalur-jalur yang terbentuk.
Text dan Web Mining - TI UKDW
10
Strongly Connected Component • SCC dalam directed graph adalah sebuah subset node
sedemikian rupa, sehingga: • setiap node dalam subset memiliki sebuah jalur ke node lainnya,
dan • subset bukan merupakan bagian himpunan yang lebih besar
lainnya dengan properti bahwa setiap node dapat mencapai setiap node lainnya.
5
4/23/13
Text dan Web Mining - TI UKDW
11
Strongly Connected Component
Text dan Web Mining - TI UKDW
12
Link • Link dapat menjadi sumber keaslian dan pengakuan/
otoritas. • mail spam • phone call log • host quality
?
Good
?
?
Bad
?
6
4/23/13
Text dan Web Mining - TI UKDW
13
Link • Node Good tidak akan menunjuk ke node Bad. • Jika sebuah node menunjuk ke node Bad, maka node
tersebut Bad. • Jika node Good menunjuk sebuah node, maka node tersebut juga Good.
Good
?
Bad
Text dan Web Mining - TI UKDW
14
Link dan IR • Sebagian besar sistem IR didasarkan pada isi dari teks. • Link dapat digunakan untuk: • scoring dan ranking • link-based clustering • struktur topik dari link
• Link sebagai feature dalam klasifikasi • dokumen yang bertautan dengan dokumen lain dikatakan mungkin
dalam satu subjek.
• Crawling menggunakan link untuk mengambil dokumen
lainnya.
7
4/23/13
Text dan Web Mining - TI UKDW
15
Web sebagai Directed Graph • Assumption 1: sebuah hyperlink antar halaman
menyatakan sebuah pengakuan otoritas (sinyal kualitas) • Assumption 2: teks dalam anchor dari sebuah hyperlink mengambarkan halaman sasaran (textual context)
Page A
Anchor
hyperlink
Page B
Text dan Web Mining - TI UKDW
16
Web sebagai Directed Graph • G = (V, E) • G adalah directed graf • V adalah himpunan halaman web • N adalah jumlah halaman web • |V| = N • Jika halaman u memiliki link ke halaman v, maka
(u, v) ∈ E
8
4/23/13
Text dan Web Mining - TI UKDW
17
Pengindeksan Teks Anchor • Ketika mengindeks dokumen D, teks anchor disertakan
dari link yang menunjuk ke D.
Armonk, NY-based computer giant IBM announced today www.ibm.com
Joe’s computer hardware links Sun HP IBM
Big Blue today announced record profits for the quarter
Text dan Web Mining - TI UKDW
18
Pengindeksan Teks Anchor • Namun terkadang tidak semua teks anchor adalah benar. • Dapatkah memberi bobot terhadap teks anchor? • bobot dapat dilakukan dengan memberikan tanda pada setiap halaman yang memiliki teks anchor. • jika web tersebut dipercaya, misalnya Google, Yahoo!, maka teks anchor memiliki bobot tinggi. • Aplikasi lainnya • pembobotan terhadap link dalam graf • menghasilkan deskripsi halaman dari teks anchor.
9
4/23/13
Text dan Web Mining - TI UKDW
19
PageRank • Mengukur kualitas dari sebuah halaman web tidak dapat
hanya menggunakan in-links. • Sebuah web page dikatakan memiliki reputasi baik, jika halaman web bereputasi baik menunjuk web page tersebut. • PageRank merupakan metode pembobotan setiap halaman dengan nilai antara 0 – 1.
∑∏
v
=1
v∈V
∀v, ∏V ≥ 0
Text dan Web Mining - TI UKDW
20
PageRank • Setiap halaman web akan memiliki bobot PageRank,
dengan notasi:
∏U
• menyatakan: • berapa banyak halaman lain yang menunjuk ke halaman u. • PageRank sebuah halaman adalah jumlah dari semua PageRank dari setiap halaman yang menunjuk ke halaman tersebut (indegree).
∏V =
∑∏
U
(U ,V )∈E
10
4/23/13
Text dan Web Mining - TI UKDW
21
Naïve PageRank • Jika halaman A menunjuk halaman B, A berkontribusi
dari PageRanknya untuk halaman B. • Halaman B mengumpulkan kontribusi dari semua halaman yang menunjuk ke B, untuk menentukan PageRank B.
1 dA
∏B 2 ∏ ∏C = B 2 ∏ B = ∏ A + ∏C ∏A =
B
C
A
∏ A + ∏ B + ∏C = 1
Text dan Web Mining - TI UKDW
22
Contoh B
B
E A
A
D
C
C
B
A
C
D
11
4/23/13
Text dan Web Mining - TI UKDW
23
Kelemahan Naïve PageRank • vulnerable to collision • apa yang disebut sebagai link spam. • pada slide 22, node C, D, dan E adalah link spam. • dapat menghasilkan solusi tak terbatas Q
B
C
A
P
R
• tidak menemukan solusi
Text dan Web Mining - TI UKDW
24
PageRank • Menurut Page dan Brin (1998), untuk menghindari masalah
naïve pagerank, diasumsikan pemakai mengunjungi tautan secara random dengan suatu probability tertentu.
∏V = P1 + P2 $ ∏U ' )) P1 = λ && ∑ d % (U,V )∈E U ( (1− λ ) P2 = N
• Nilai λ pada umumnya bernilai 0.85
• P1 adalah probabilitas mengunjungi v dari halaman lain • P2 adalah probabilitas mengunjungi v secara acak
12
4/23/13
Text dan Web Mining - TI UKDW
25
PageRank • Karena pada kenyataannya jumlah halaman web yang
dihitung sangatlah banyak, maka dilakukan pendekatan iteratif untuk setiap nilai PageRank halaman. • Dalam tiap iterasi, digunakan formula: • p(k+1) = p(k) * H
• p adalah vektor PageRank tiap halaman web • Untuk inisialisasi, p(0), digunakan nilai 1/n untuk tiap
halaman. • n adalah jumlah halaman dalam graf.
• kemudian dilakukan perulangan sampai nilai perbedaan
antar kedua vektor terakhir cukup kecil. • ditentukan dengan sebuah threshold.
Text dan Web Mining - TI UKDW
26
PageRank • Untuk mencegah adanya hasil PageRank adalah 0 jika
ditemukan adanya dangling nodes, maka matrix teleporation H, harus diubah dengan langkah: • Buat matrix untuk Dangling Node • dij = 0 jika Hij > 0 • dij = 1 jika Hij = 0
• Update matrix H dengan G (Google) Matrix:
H = λH + (λd + (1 − λ )e)
transporter
1 T e N
• matrix eT adalah vektor berisi 1.
13
4/23/13
Text dan Web Mining - TI UKDW
27
PageRank: Contoh B
0
1/3
1/3
1/3
0
0
½
½
1
0
0
0
0.5
0
0.5
0
A H= C
D
Non Zero baris ke-i menunjukkan outlinking page dari halaman ke-i. Non Zero kolom ke-j menunjukkan inlinking page dari halaman ke-j.
Text dan Web Mining - TI UKDW
28
PageRank: Contoh 0 dangling=
0
1 e=
1
0
1
0
1
eT=
1
1
1
1
G = λ H + (λ d + (1− λ )e)
G=
0.04
0.32
0.32
0.32
0.04
0.04
0.46
0.46
0.89
0.04
0.04
0.04
0.46
0.04
0.46
0.04
1 T e N
14
4/23/13
Text dan Web Mining - TI UKDW
29
PageRank: Contoh 0.25 p0=
0.25
0.04 0.32 0.32 0.32
0.25
0.04 0.04 0.46 0.46 = 0.2500
0.25
0.25
0.89 0.04 0.04 0.04
0.2500
0.25
0.25
0.46 0.04 0.46 0.04
0.2500
0.25
p1=
0.2479
|p1-p0| = abs(0.2479-0.25)+ abs(0.25-0.25)+ abs(0.25-0.25)+ abs(0.25-0.25)=0.0021
Text dan Web Mining - TI UKDW
30
PageRank: Contoh p2=
0.2479
0.04 0.32 0.32 0.32
0.2500
0.04 0.04 0.46 0.46 = 0.2499
0.2500
0.89 0.04 0.04 0.04
0.2481
0.2500
0.46 0.04 0.46 0.04
0.2490
0.2478
|p2-p1| = abs(0.2478-0.2479)+ abs(0.2499-0.25)+ abs(0.2481-0.25)+ abs(0.249-0.25)=0.0030
Sehingga p1 adalah vektor v* (equilibrium value) yang merupakan nilai PageRank untuk tiap halaman yang diharapkan.
15
4/23/13
Text dan Web Mining - TI UKDW
31
Algoritma HITS • HITS singkatan dari Hypertext Induced Topic Search. • Ketika pemakai memberikan query, HITS pertama akan
mendapatkan hasil dokumen yang relevan dengan query oleh mesin pencari dan menghasilkan 2 rangking: • authority ranking • hub ranking
• Authority adalah sebuah halaman dengan in-links • Hub adalah sebuah halaman dengan out-links.
Text dan Web Mining - TI UKDW
32
HITS AT&T Alice
Authorities
Hubs
ITIM Bob O2 Mobile telecom companies
16
4/23/13
Text dan Web Mining - TI UKDW
33
Text dan Web Mining - TI UKDW
34
Algoritma HITS
Contoh HITS B A=
A
0
0
1
0
0
1
0
0
0
C
1 u=
AT=
0
0
0
0
0
0
1
1
0
1 1
17
4/23/13
Text dan Web Mining - TI UKDW
35
Text dan Web Mining - TI UKDW
36
Contoh HITS 0 v= AT.u =
0
0
1
0
0
0
1
1
1
0
1
0 =
0 2
Update vector hub 0 u= A.v =
0
1
0
0
0
1
0
0
0
0
2
2 =
2 0
Halaman C paling authoritative, sedangkan A, dn B hub penting.
TERIMA KASIH budi susanto
18