|
Chakrabarti, Soumen.a, Dom, Byron.a, Raghavan Prabhakar.a, Rajagopalan, Sridhar.a, Gibson, David.b, Kleinberg, Jon.c "Automatic resource compilation by analyzing hyperlink structure and associated text," Proceedings of the 7th International World Wide Web Conference. 1998.
a) IBM Almaden Research Center K53.
b) Computer Science Division, Soda Hall University of California, Berkeley.
c) Department of Computer Science, Upson Hall Cornell University.
※図表、注・引用文献は原文献をご参照下さい。
1. 概観
本稿では、特定のトピックについての権威あるWebページのリストを自動的に編集するシステム、ARC（Automatic Resource Compiler）の設計と評価を行う。
YahooやInfoseekは（一部）人的に編集されたリストであるが、ここでは、完全に自動化され、なんら手を加えないリストを提供する。
評価の段階では、それらについて、利用者による比較が行われる。
1.1. 関連する先行研究
ハイパーリンクを潜在的な利用者による評価であるとみなして、優れたページを発見するために用いるという検索手法は、これまでにもしばしば行われている。
本研究は、このうち、Kleinbergによって提供されたアルゴリズムを基盤とし、拡張したものである。
1.2. ロードマップ
→論文の構成について（省略）
2. アルゴリズム
我々のアルゴリズムは、（1）検索と拡張の段階、（2）重み付けの段階、（3）反復と出力の段階、の三つの段階から成っている。
まず、AltaVistaによって、上位200件のページを検索して根集合（root set）とし、そこからリンクの張られているページ、そこにリンクを張っているページを併せて増幅集合（augmented set）を構成する。
但し、Kleinbergでは1ホップまでであったが、ここでは、2ホップまでをその対象とする。
その結果、増幅集合はトピックによって数百から3,000程度のページとなった。
ある主題についての豊富な情報を保持しているページをオーソリティ（authority）、ある主題についての豊富な情報を保持しているページへ、多くのリンクを提供しているページをハブ（hub）と呼ぶ。
そこで、（1）あるページpにリンクを張っているページのハブ・スコア（h(p)）の和を、pのオーソリティ・スコア（a(p)）に置き換え、（2）pからリンクを張られているページのa(p)の和を、pのh(p)に置き換えるという計算を反復して行う。
具体的には、ページqがページpにリンクしているか否かを示す行列W（厳密には、2.1で示す重み付けを行っている）、及び、その転置行列をZ、ベクトルhの初期値を1として、以下に示す計算式を5度反復し、ハブ・スコアとオーソリティ・スコアを定義した。
a = Wh
h = Za
そして、主題ごとに、トップ15のオーソリティとハブを抽出した。
トップ15という数は任意であるが、ブラウザ1ページで一度に見やすい数として選択した。
2.1. 重みw(p, q)の計算
重みw(p, q)は、ある特定の主題についてのページqから、ページpへリンクが張られている場合1となり、オーソリティの尺度となる。ここでは、単純なリンク関係だけでなく、hrefの付近にあるテキスト情報をこの重みに反映した。
プレ調査のために5,000ページをダウンロードし、例えば、Yahooへのリンクの場合、そのアンカー・タグの前後のどの位置にYahooという文字が出現するのかを確認した（→表1）。
その結果を受けて、前後50文字内に主題を示す情報が出現した場合、w(p, q)=1+n(t)という式に基づいて、重み付けを行った（n(t)は当該タームの出現頻度）。
2.2. 実装
→以上のアルゴリズムをどのような環境でどのように実装したか（省略）
3. 実験
3.1. 比較のための主題と基礎
実験のための主題は、たとえ被験者がその主題の専門家ではなくとも、ブラウジングを行えば、その出力結果の質についての判断が行えるようなものを選択した。
ほとんどの主題はYahooやInfoseekからピック・アップした。最終的に、28の主題が選択された（→付録）。
3.2. 協力者とテストの準備
参加者は、北アメリカやアジアから来た20代から50代までの人々で、全員がWebブラウジングと検索の経験を有している。
中には、計算機科学の学生や専門家が含まれている。
それぞれの参加者には、一つ～二つの主題が割り当てられた。
提示されるリストはYahoo!, Infoseek, 及び、ARCによって出力されたリストであり、前者二つについては該当する主題のページが提示され、我々のリストについては、トップ15のハブとトップ15のオーソリティーが提示された（→表2, 表3）。
実験の際に、その情報源を隠したり、リストの数を同じにしたりはしなかった。
参加者は、これらのリストを開始点として、15～30分かけてWebをブラウジングしてもらい、当該主題についての学習を行った後、三つのリストについて、①正確性と精度、②網羅性と再現率、③全体の価値といった三つの観点から、1-10の評価尺度で点数化するよう要請された。
さらに、これら三つのリストについて、なんらかのコメントを依頼した。
4. 結果
4.1. 実験データの要約
まず、全体の質についての比較を行った。図1はYahoo!, InfoseekとARCとのスコアの比率を示したものである。
y軸が1であれば両者に差はなく、1以上であればARCの方が優れており、1未満であればARCの方が劣っていることを表している。
その結果、ARCはYahoo!やInfoseekと充分に比較可能であると評価されたと言える。
Yahoo!がARCよりも良ければInfoseekもよく、Infoseekが劣ればYahoo!も劣ることが多かった。
また、概ね、Web上に多くの情報源がある場合はARCは分が悪く、あまり多くの情報源のないものについてはARCは優れているという傾向が見られた。
また、図2（精度）、図3（再現率）についても、図1と類似の傾向が見受けられた（相関係数0.6）。
図4は、精度と再現率を散布図上にプロットしたものである。
通常両者はトレードオフの関係にあるが、ここでは、緩やかな正の相関（0.26）がある。
4.2. 評価者によるコメントの要約
参加者たちの多くはハブとオーソリティの区別を明示することを好んだ。
また、何人かはオーソリティ・ページとされるもののうち幾つかは、明らかに、ハブ・ページと呼び得るものであると指摘した。
開始点としては、やはり、ハブ・ページの方が価値あるものと見なされた。
殆どの評価者は、必ずしも、三つのリストを最後まで利用してはいない。
評価者がARCの提供するリストよりも、主題のより広いレベル、もしくは、主題のより限定されたレベルを求めるケースもあった。
粒度のコントロールは、おそらく、階層的分類の最も有効な特徴である。
ARCを改良するための提言として、最も共通に述べられたコメントとしては、①Yahoo!のように、現在の主題が分類階層のどこに位置しているのかを明示すべきである。
②平坦なリストだけでなく、ページについての簡潔な要約文が提示されることが望ましい、等が挙げられる。
本研究では、プレゼンテーションについては考慮していなかったが、今後、この領域に改善の余地があるだろう。
5. 結論
本研究は、我々の知る限り、Webページの分類を自動的に行った最初の業績である。
また、利用者による評価の結果、（1）ARCのリストは人的に編集されたリストと同じくらい網羅的であり、場合によっては、それらよりも良い場合があった。
（2）単にリストだけを提供することは、Yahoo!やInfoseekのリストに較べて不利であった、こと等が明らかになった。
【付録．選択された28の主題】
affirmative action, alcoholism, amusement parks, architecture, bicycling, blues, classical guitar, cheese, cruises, computer vision, field hockey, gardening, graphic design, Gulf war, HIV, lyme disease, mutual funds, parallel architecture, rock climbing, recycling cans, stamp collecting, Shakespeare, sushi, telecommuting, Thailand tourism, table tennis, vintage cars, zen buddhism
|