13. Budi Susanto

4/23/13

Text dan Web Mining - TI UKDW

1

ANALISIS LINK Budi Susanto


2

Tujuan •  memahami karakteristik link antar laman yang dapat

dimodelkan sebagai graf. •  memahami algoritma PageRank •  memahami Hubs and Authority

1

4/23/13


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


4

Contoh citation hypertextual

2

4/23/13


5

Contoh Cross Reference network


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


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.


8

Contoh Web Directed Graph

4

4/23/13


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.


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


11

Strongly Connected Component


12

Link •  Link dapat menjadi sumber keaslian dan pengakuan/

otoritas. •  mail spam •  phone call log •  host quality

?

Good

?

?

Bad

?

6

4/23/13


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


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


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


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


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


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


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


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


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


22

Contoh B

B

E A

A

D

C

C

B

A

C

D

11

4/23/13


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


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


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.


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


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.


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


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


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


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.


32

HITS AT&T Alice

Authorities

Hubs

ITIM Bob O2 Mobile telecom companies

16

4/23/13


33


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


35


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

13. Budi Susanto

Recommend Documents