PowerPoint プレゼンテーション

知能システム論
森下真一
講義日程 10/3, 10/10, 10/17, 10/24, 10/31
内容
• Web グラフと検索エンジン
• クラス分類問題
• アソシエーションルール
• クラスタリング
検索エンジンとページランキング
Spam: 上位にページランキングされるためのトリック
• 検索頻度の大きい語句の使用
• 小さなフォント、文字の無色化、METAタグの悪用
• ハイパーリンク情報を利用した検索エンジンの登場
Web Graph
WWW全体を web page をノード、hyper-link を有向辺
とする有向グラフとみなす
各ページの重要度
(importance) を実数で表現
Ne
重要度順にページランキング
MS
Am
初期値を１
 Ne0  1

  
 MS0   1
 Am  1
0

 
Page Ranking – google.com
重要度が収束するまで繰返す
1. リンク先に重要度を均等に分配
2. 分配された和を重要度として更新
Ne
MS
Am
Ne MS Am
 Nei 1  1 / 2 0 1 / 2  Nei 

 


 MSi 1    0 0 1 / 2  MSi 
 Am  1 / 2 1 0  Am 
i 1 
i



1. Am はその重要度を Ne と MS に均等に分配
2. Nei 1  1 / 2 Nei  1 / 2 Ami
Page Ranking – google.com
Ne
MS
Am
 Ne0  1

  
 MS0   1
 Am  1
0

 
 Nei 1  1 / 2 0 1 / 2  Nei 

 


 MSi 1    0 0 1 / 2  MSi 
 Am  1 / 2 1 0  Am 
i 1 
i



 Nei   6 / 5 
 5 / 4   9 / 8   5 / 4   1  1

 


 
 
 
  
lim MSi    3 / 5      11/ 16    1 / 2    3 / 4    1 / 2   1
i 
 Am   6 / 5 
17 / 16 11/ 8   1   3 / 2  1
i




 
 
 
  
Page Ranking – google.com
Ne
Dead End
MS
Am
 Nei 1  1 / 2 0 1 / 2  Nei 

 


 MSi 1    0 0 1 / 2  MSi 
 Am  1 / 2 0 0  Am 
i 1 
i



 Nei   0 
 1 / 2   5 / 8   3 / 4   1  1

  

 
 
 
  
lim MSi    0      3 / 16   1 / 4    1 / 4   1 / 2   1
i 
 Am   0 
 5 / 16  3 / 8   1 / 2  1 / 2  1
i

 

 
 
 
  
Page Ranking – google.com
Ne
Spider Trap
MS
Am
 Nei 1  1 / 2 0 1 / 2  Nei 

 


 MSi 1    0 1 1 / 2  MSi 
 Am  1 / 2 0 0  Am 
i 1 
i



 Nei   0 
 1 / 2   5 / 8   3 / 4   1  1

  

 
 
 
  
lim MSi    3      35 / 16   2    7 / 4    3 / 2   1
i 
 Am   0 
 5 / 16   3 / 8   1 / 2   1 / 2  1
i

 

 
 
 
  
Page Ranking – google.com
 Nei 1 
1 / 2 0 1 / 2  Nei 
1





 
 MSi 1   (1  tax) 0 1 1 / 2  MSi   tax1
 Am 
1 / 2 0 0  Am 
1
i 1 
i



 
Sprider Trap の回避
重要度の一部を
税金として徴収
Dead End 効果の回避
税金の再配分
例
tax  0.2
 Nei   7 / 11 
1

 

 
lim MSi    21/ 11    1
i 
 Am   5 / 11 
1
i



 
Page Ranking – Hubs & Authorities
Page Ranking – Hubs & Authorities
Hubs
Authorities
Page Ranking – Hubs & Authorities
１
２
３
４
0

２ 0

A
３ 0


４ 0

1
0
0
0
1
1
0
0
0

1

1


0
１
1
3
2
4
隣接(adjacency)行列
Page Ranking – Hubs & Authorities
 2  0
  
２  2
0

0
３ 1
  
0
４ 0
  
１
1
3
2
4
Hub
weight
1
0
0
0
1
1
0
0
0 1
 
1 1



1 1
 



0 1
authority
weight
Page Ranking – Hubs & Authorities
転置
隣接
行列
1
3
2
4
１
２
３
１
0

２ 1

T
A 
３ 1

0
４

１
２
３
0
0
1
1
0
0
0
1
４
0

0
0

0 
４
0 0
  
 2 1

 4 1
  
 3  0
  
authority
weight
0
0
1
1
0
0
0
1
0  2 
 
0  2 



0 1
 



0  0 
Hub
weight
Page Ranking – Hubs & Authorities
1
3
2
4
0

1
T
A A
1

0

0
0
1
1
0
0
0
1
0  0

0  0
0  0

0  0
1
0
0
0
1
1
0
0
0  0
 
1 0


1
0
 
0   0
authority weight
 0   0   0   0  1

        
 61   19   6   2  1
 
    

136
42
13
4
1

        
108  33 10  3  1

        
0
1
1
0
0
1
2
1
0

0
1

2 
Page Ranking – Hubs & Authorities
A A は実対称行列
T
ある直交行列 U により対角化可能
1
 ある対角行列 D が存在して A A  U DU
T






T
i
1
i
1
i
ai  A A a0  U DU a0  U D U a0
Page Ranking – Hubs & Authorities
Authority Weight の正規化
Authority Weight が無意味に増大しないように
毎回の正規化（Hub Weight についても同様）

Authority weight ai
 
Initialize a0 (1, K ,1)T
For i  0,1,2, K
  T 
ai 1 A Aai

 
Normalize ai 1 s.t. ai 1 1
Page Ranking – 参考文献
google.com
• Sergey Brin and Lawrence Page.
The Anatomy of a Large-Scale Hypertextual Web Search Engine.
7th International World Wide Web Conference. April 1998.
http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm
Hubs and Authorities
• Jon M. Kleinberg: Authoritative Sources in a Hyperlinked Environment.
JACM 46(5): 604-632 (1999)
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P.
Raghavan, S. Rajagopalan, A. Tomkins, Hypersearching the Web.
Scientific American, June 1999.
Rank Aggregation
• データ収集法、ランキング法が異なる検索エンジンの
ランキング結果をまとめたランキングを生成する技術
• 特定の検索エンジンだけで不当なほど高順位を得て
いる spam の除去に役立つ
• 検索エンジン間の比較
参考文献
Rank aggregation methods for the Web; Cynthia Dwork, Ravi Kumar, Moni
Naor and D. Sivakumar; Proceedings of the tenth international World Wide
Web conference on World Wide Web, 2001, Pages 613 - 622
Rank Aggregation
– ランキング間の距離
S は n 個の要素からなる集合
ランキング　 : S  {1,2, ..., n}
 は全単射. S の新たな全順序を定義 .
ランキング  と  の距離
n
Spearmanfootruledistance F ( , )    (i )   (i )
i 1
位置の差の総和
Kendall tau distance
K ( , )  {(i, j ) | i  j ,  (i )   ( j ), (i )   ( j )}
ランクが逆転するペアの総数
重複カウントを避ける
ため S の元に全順序を仮定
Rank Aggregation
1
2
3
4
5
σ
A
C
E
D
B
– ランキング間の距離
τ
C
A
B
D
E
Spearman footrule =1+2+1+0+2 = 6
Kendall tau =|{(A,C), (B,D), (B,E), (D,E)}| = 4
Optimal Rank Aggregation
ランキング　 , 1 ,..., k : S  {1,2, ..., n}
とその他  1 ,..., k間の距離
1
Spearmanfootruledistance F ( , 1 ,..., k ) 
k
k
 F ( ,
j 1
j
)
Kendall tau distanceも同様に定義
 1 ,..., kが与えられたとき F ( , 1 ,..., k )を最小化する を
footruleoptimalrank aggregation
Optimal Rank Aggregationの計算
重み付き完全二部グラフ
1
1
F ( , 1 ,..., k )
1

k
k
 F ( ,
j 1
j
)
2
2
n
n
1 k n
   (i )   j (i )
k j 1 i 1
1 n k
   (i )   j (i )
k i 1 j 1
i
x
k
 x 
j 1
j
(i )
ランキングσは二部グラフの完全マッチングとみなせる
重み最小の完全マッチングσが Optimal rank aggregation
O(n2.5)の時間計算量で計算可能
Cyber Communities
• 共通の内容に関するサイトの集合(cyber community)
を発見したい
• 現時点で活発な community を探したい
• ポータルサイトの容易な構築（Yahoo の自動化）
参考文献
• Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins.
Trawling the web for emerging cyber-communities.
The Eighth International World Wide Web Conference. May 1999.
http://www8.org/w8-papers/4a-search-mining/trawling/trawling.html
Cyber Communities
Cyber Community の核となる「コア」を探す
• fan と center (Hub と authority)
からなる二部グラフをコアとして
内部にもっていると「仮定」
i
j
• fan が i 個、center が j 個以上の
完全二部グラフを探す (i,j)-コア
• center は類似した内容でも互いに
リンクしないページ
(Microsoft と Sun のような関係)
• fan はポータルサイト
fan
center
(i,j)-コア
Cyber Communities
• 少なくとも６個以上別サイトにリンクを
張るページを対象（全体の１２％）
i
j
• replicated page の削除
• ある閾値以上リンクされている
ページは削除（あまりに有名で
小さな community の元と考えにくいので）
fan
center
(i,j)-コア
• 明らかに無駄な arc の排除
out-going arc の数が j 個未満の fan を削除
in-coming arc の数が i 個未満の center を削除
主記憶が小さい環境なので二次記憶を使い source node および
destination node でソートする二次記憶型システム．
Cyber Communities
• inclusion-exclusion pruning
out-going arc の数が j 個の fan X を選択
i
j
(i,j)-コアを構成するか否かチェック
j 個の center を指す fan が X 以外に
(i-1) 個以上存在するか調べる
存在しない場合、fan X を削除
以上を繰り返す
• (i,j)-コアを出力
fan
center
(i,j)-コア
Cyber Communities
実験結果
• i = 3～6, j=3
で 13 万 5 千の
cyber communities
• non-nepotistic core
fan がすべて異なる
web site にある
• inclusion-exclusion
pruning のおかげで
core は殆ど disjoint
i
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
6
j
3
5
7
9
3
5
7
9
3
5
7
9
3
5
7
9
Number of cores.
Number of nonnepotistic cores.
89565
70168
60614
53567
29769
21598
17754
15258
11438
8062
6626
5684
4854
3196
2549
2141
38887
30299
26800
24595
11410
12626
10703
9566
7015
4927
4071
3547
2757
1795
1425
1206
Copyright http://www8.org/w8-papers/4a-search-mining/trawling/trawling.html
Cyber Communities
• (i,j)=(3,5) で 400 サンプルの信憑性を調べる
• 16 (4%) の中身は無関係
• 122(30%) は現在は消滅
→ cyber community の一過性を示唆
• 56% は当時（1年半前）の Yahoo! に載っていない
29% は現在でも載っていない
→ 人手で cyber community を見つけることの限界
Web Graph Structure
“Bow-tie” Theory
Copyright http://www.almaden.ibm.com/cs/k53/www9.final/
Web Graph Structure
• 使用データ Alta Vista
203Mページ, 1466Mリンク, 9.5GB (May 1999)
URL 10byte, link 3.4 byte
271Mページ, 2130Mリンク (October 1999)
• 使用計算機 Compaq AlphaServer (465MHz, 12GB MM)
Web Graph Structure
Power Law の検証
「あるページを指しているリンクの数が
i である確率は 1/xi に比例する」
Web Graph Structure
1
2.1i
in-degree ＝ in-coming arc の数
Copyright http://www.almaden.ibm.com/cs/k53/www9.final/
Web Graph Structure
1
2.72i
out-degree = out-going arc の数
Copyright http://www.almaden.ibm.com/cs/k53/www9.final/
Web Graph Structure
参考文献
• Andrei Broder(1), Ravi Kumar(2), Farzin Maghoul(1), Prabhakar
Raghavan(2), Sridhar Rajagopalan(2), Raymie Stata(3), Andrew
Tomkins(2), Janet Wiener(3):
Graph structure in the web. WWW9. May 2000.
1 Alta Vista, 2 IBM Almaden, 3 Compaq
• Nature 誌 2000年5月号
• Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D.
Sivakumar, Andrew Tomkins (IBM Almaden),
and Eli Upfal (Brown).
The Web as a Graph. PODS2000, May 2000
Wayback Machine
過去5年間の100億ページものWebページを
保管したWebアーカイブが公開
http://web.archive.org/
Wayback Machine
http://www.is.s.u-tokyo.ac.jp/
Wayback Machine
カリフォルニア大学バークリー校のバンクロフト図書館で
2001年10月24日に開かれた式典で披露
過去のWebページのライブラリは100テラバイトにも達する
さらに毎月10テラバイト増加
保管するデータ容量は米国議会図書館を初めとする
あらゆる図書館を上回り、現存する世界最大のデータベース

Download Report