analisis link - lecturer.ukdw.ac.idlecturer.ukdw.ac.id/budsus/pdf/genap12/twm/minggu12.pdfdalam satu...

4/23/13

1

ANALISIS LINK Budi Susanto

Text dan Web Mining - TI UKDW 1

Tujuan • memahami karakteristik link antar laman yang dapat

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


4/23/13

2

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


Contoh citation hypertextual


4/23/13

3

Contoh Cross Reference network


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.


4/23/13

4

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.


Contoh Web Directed Graph


4/23/13

5

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.


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.


4/23/13

6

Strongly Connected Component


Link •  Link dapat menjadi sumber keaslian dan pengakuan/

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


?

?

?

? Good Bad

4/23/13

7

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

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.


4/23/13

8

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 hyperlink Page B Anchor

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


Evu ∈),(

4/23/13

9

Pengindeksan Teks Anchor • Ketika mengindeks dokumen D, teks anchor disertakan

dari link yang menunjuk ke D.


www.ibm.com

Armonk, NY-based computer giant IBM announced today

Joe’s computer hardware links Sun HP IBM

Big Blue today announced record profits for the quarter

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.


4/23/13

10

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.


1=∏∑∈Vv

v 0, ≥∏∀ Vv

PageRank • Setiap halaman web akan memiliki bobot PageRank,

dengan notasi:

• 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 (in-degree).


U∏

∑∈

∏=∏EVUUV

),(

4/23/13

11

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.


Ad1

A

B

C 1

2

2

=∏+∏+∏

∏+∏=∏

∏=∏

∏=∏

CBA

CAB

BC

BA

Contoh


A

B

C

A

B

C D

E

A

B

C D

4/23/13

12

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

•  tidak menemukan solusi


A

B

C P

Q

R

PageRank •  Menurut Page dan Brin (1998), untuk menghindari masalah

naïve pagerank, diasumsikan pemakai mengunjungi tautan secara random dengan suatu probability tertentu.

•  Nilai λ pada umumnya bernilai 0.85 •  P1 adalah probabilitas mengunjungi v dari halaman lain •  P2 adalah probabilitas mengunjungi v secara acak


∏V = P1 +P2

P1 = λ∏U

dU(U,V )∈E∑

$

%&&

'

())

P2 =(1−λ)N

4/23/13

13

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.


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:

•  matrix eT adalah vektor berisi 1.


TeN

edHH 1))1(( λλλ −++=

transporter

4/23/13

14

PageRank: Contoh


A

B

C

D

0 1/3 1/3 1/3

0 0 ½ ½

1 0 0 0

0.5 0 0.5 0

H=

Non Zero baris ke-i menunjukkan outlinking page dari halaman ke-i. Non Zero kolom ke-j menunjukkan inlinking page dari halaman ke-j.

PageRank: Contoh


dangling=

0

0

0

0

e=

1

1

1

1

eT= 1 1 1 1

G = λH + (λd + (1−λ)e) 1NeT

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

G=

4/23/13

15

PageRank: Contoh


p0=

0.25

0.25

0.25

0.25

p1=

0.25

0.25

0.25

0.25

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

0.2479

0.2500

0.2500

0.2500

=

|p1-p0| = abs(0.2479-0.25)+ abs(0.25-0.25)+ abs(0.25-0.25)+ abs(0.25-0.25)=0.0021

PageRank: Contoh


p2=

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

0.2478

0.2499

0.2481

0.2490

=

0.2479

0.2500

0.2500

0.2500

|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.

4/23/13

16

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.


HITS


AT&T Alice ITIM Bob O2

Mobile telecom companies

Hubs

Authorities

4/23/13

17

Algoritma HITS


Contoh HITS


A

B

C

0 0 1

0 0 1

0 0 0

A=

0 0 0

0 0 0

1 1 0

AT=

u=

1

1

1

4/23/13

18

Contoh HITS


v= AT.u = 1

1

1

0 0 0

0 0 0

1 1 0

= 0

0

2

Update vector hub

u= A.v = 0

0

2

0 0 1

0 0 1

0 0 0

= 2

2

0

Halaman C paling authoritative, sedangkan A, dn B hub penting.

TERIMA KASIH budi susanto


analisis link - lecturer.ukdw.ac.idlecturer.ukdw.ac.id/budsus/pdf/genap12/twm/minggu12.pdfdalam satu...

Documents