論文

DBSJ Letters Vol.2, No.1

る．しかしながら，ポータルサイトで得られる URL を起点リンク構造に基づく Web イジング に，クリックして得られる
Web 上のデータは部分的なもの
検索モデルの提案であるため，大量の Web ページの内容やリンク関係を解析し，意味ある有用な情報を抽出する Web マイニングと呼ばれる研究や技術開発が活発に行われている [1, 3, 4, 6, 7, 9]．
なお，情報抽出の際に用いられるデータは，Web ページ中に記述されたテキストやハイパーリンク，Web サーバ上のログ，さらに，利用者側のブラウジング履歴などが対象となる．
阿部 友一1
河野 浩之2
本稿では，新たな Web 検索アプローチとして，磁性体の臨界現象を良く表すイジングモデルを，Web のリンク構造
Tomokazu ABE Hiroyuki KAWANOに対して応用する Web 検索モデルを提案する．そして，提案した Web 検索モデルが，検索処理に関わる不要ページの排除や抑制効果を示すかの検証を行う．特に，実際の Web
PageRank や HITS アルゴリズムをはじめとする多数の Web データを用いてモデル化と検索を行い，磁性体の特性を表構造マイニングの研究がなされている．しかし ，検索エンジンの す幾つかのパラメータを変化させることで，検索対象領域性能指標となる検索精度や検索時間などのバランスを確保した上 の大きさを，どの程度小さくすることができるかを示す．
以下，2 章では Web モデリングに用いるイジングモデル
で，どれだけの規模の Web ページ群を対象とした Web マイニングを行うかは大きな課題である．そこで，本稿では，Web リンク を説明する．3 章で，実際に提案する Web 検索モデルの提構造に注目した Web 構造マイニングを効率良く行うために，磁 案を行い，4 章で Web データを用いて実験を行った際の環性体を表す基礎的な物理モデルであるイジングモデルを用いて， 境説明，パラメータ変化による振る舞いの結果を示す．最Web 情報をモデル化する．そして，大規模な Web ページ群を効率 後に，結論と今後の課題を 5 章で述べる．

Proposal for Web Ising Retrieval Model
Based on Link Structure

よく検索するリンク構造型イジング検索 (Link structural IsingRetrieval) を行う LIR アルゴリズムを提案し ，NTCIR 情報検索
システム評価用テスト コレクション構築プロジェクト で利用されている Web データを用いて，その有効性を検証する．特に，提案する LIR アルゴリズムに関係する幾つかの熱力学的パラメータの変動が，検索速度や検索精度にどのような影響を与えるかを，不要ページの抑制効果の面から議論する．

PageRank, HITS and other web mining algorithms havebeen developed for discovering web documents with usefulness and high quality. In web mining models, the significant
issue is the scalability of web page groups and keeping a balance between the search time and search accuracy, which indicate the performance of the search engine. In this paper,
we employed the Ising model, which is known as a fundamental physical model of magnetism to perform efficient web
structure mining based on its link relation. We propose LIRalgorithm (Link structural Ising Retrieval) which efficiently
reduces the size of informative web pages in a large web community. We evaluated the validity of LIR algorithm using actual web data of the NTCIR (NII-NACSIS Test Collection forIR Systems) Project. We argue the characteristics of search
speed and search accuracy by changing several thermodynamic parameters related to the LIR algorithm.

1. はじめに2.

イジングモデル

物質は低温では秩序的な状態を取り，高温では無秩序な状態を取る．例えば，磁性体は低温では磁力を保っているが，ある温度を超えると，磁力を突然失ってしまう臨界現象を起こす．この臨界現象を適切に再現するモデルとしてイジングモデルがある．そこで，Web モデルの新たな可能性を求めて，本稿では Web のモデル化を行う際にイジングモデルを用いる．なお，本章では，2 次元イジングモデルを中心に，イジングモデルに関係する典型的な熱力学量を説明し，Web イジング検索に必要なアルゴ リズムを紹介する．

2.1

イジングモデルの性質

2 次元イジングモデルは，各格子点にスピンが配置されたモデルである．磁性を持つ原子に対してスピンが与えられ，各スピンはスピン変数 Si で表現される．ここで，Si = 1 の時にスピン Si が上向きの磁力を持ち，Si = −1 の時スピンSi が下向きの磁力を持つとする．
次に，イジングモデルに用いる幾つかの熱力学量を導入する．スピン Si の相互作用エネルギー Ei を (1) 式により，ある状態 S のハミルトニアン H(S) を (2) 式で表す．
Ei = −JSi Sj − BSi(1)jインターネット上の情報流通量の増大には目覚しいものがあるが，その技術変化も劇的なものであるゆえに，大きな社会現象を起こし続けている．特に，Web システムの成長は著しく，非常に豊富で密度の濃い情報源になりつつあ
1 学生会員

京都大学大学院情報学研究科博士前期課程
2 正会員 京都大学大学院情報学研究科システム科学専攻
kawano@i.kyoto-u.ac.jp

1

H(S) = −J<i,j>

Si Sj − B

Si(2)iJ は結合定数，B は外部磁場，Sj はスピン Si の隣接スピン，< i, j > は隣接する 2 つのスピンの組み合わせを表すものとする．一般に，J > 0 のモデルは強磁性体，J < 0 のモデルは反強磁性体である．統計物理学において，このモデルの日本データベース学会 Letters Vol.2, No.1

論文

DBSJ Letters Vol.2, No.1

 − 1 H(S)
任意の状態 S の出現確率を，分布関数 Z = S e kB T
3. Web イジング検索法の提案を用いて，(3) 式で与える．ここで，kB はボルツマン定数，本稿では，Web structure mining の領域に関係するハT は温度である．
イパーリンク構造に注目しながら，Web ページ検索において既に得られた情報を有効に利用するために，Web グラフ
e−βH(S)(3) に対するイジングモデルによるアプローチを提案する．実
ボルツマン分布 ω(S) =Z
際，Web 検索で扱う問題では，ユーザーが必要とするページかそうでないかの 2 状態にページ群が分類されるため，各Web ページをイジングモデルのスピンで表現することが可
2.2 イジング探索法
能である．加えて，一連の検索過程において必要なページランダムに選択されたスピン Si に対して，スピン Si の かど うかの判定情報を外部磁場として組み込むことで，ス
周辺スピンと外部磁場と関連のある相互作用エネルギー Ei ピンフリップ・ダ イナミクスを利用し ，ハイパーリンクにを最小にするようにスピンの向きを変える操作のことをス よる関連 Web ページの状態を確率的に推定できる．
ピン・フリップ・ダ イナミクス (spin flip dynamics) という．

3.1

【スピン・フリップ・ダイナミクス】

1. スピン Si を選択する．
2. スピン Si をフリップした時の変動エネルギー ∆Ei を計算する．
3. e−β∆Ei に比例した確率に応じてスピン Si をフリップ✷する．
ここで，相互作用エネルギー Ei が小さくなるようにスピンをフリップするということは，スピン Si の周辺に上向きのスピンが多数あれば上向きに，下向きのスピンが多数あれば下向きにフリップすると考えられる．
次に，イジングモデルで用いていた相互作用エネルギーに含まれる外部磁場を，(4) 式で与える．

B = Hd (md (a) − θd )(4)

ここで，Hd は外部磁場との結合定数，md (a) はスピン Saの探索物らしさ，θd は探索物であるかど うかの閾値である．
この時，イジング探索アルゴ リズム [2] は次のようになる．

Web グラフに対するイジングモデルの適用

イジングモデルの 1 スピンを，Web 上の 1 ページに対応させる．また，スピン間の結合定数 J を，Web ページ間の結びつきの強さとみなす．ここで，Web ページ群を強磁性体と考え，J > 0 とする．なお，二次元イジングモデル
ではスピン Si に隣接するスピン Sj 数は 4 であるが，これを Web ページ Si がリンクしている Web ページ Sj に隣接しているモデルに拡張する．また，外部磁場定数 Hd ，ページ Sa に対してユーザーが必要としているページらしさをmd (a)，必要なページであるかど うかの閾値を θd とする．
まず，取り扱うスピン数を M とし，対象となる Web ページに対してスピン S1 , S2 , · · · , SM を割り当てる．また，あるスピン Si に隣接するスピン Sj の数を N (i) とする．なぜならば ，2 次元格子モデルで一般の磁性体構造を近似するのに対して，Web 構造は 2 次元格子モデルに制約されないからである．よって，本稿では，イジングモデルにおける相互作用エネルギー Ei を，式 (5) と定義する．

Ei = −4J 
Si Sj − Hd (md (a) − θd )Si
N (i) j(5)

【 イジング探索アルゴリズム】

また，スピン Si をフリップした時の変動エネルギー ∆Ei
1. 全領域のスピンを探索物状態（ Si = −1 ）とし ，探索 を (6) 式で与える．
物候補だけを格納したリストを作る．
8J 
2. 探索物候補のリストの中からランダムに 1 つのスピン∆Ei =Si Sj + 2Hd (md (a) − θd )Si(6)N (i) j
Sa を選ぶ．
3. スピン Sa の探索物らしさ md (a) を求める．
4. スピン Sa の周辺で状態を確定していないスピンに対して spin flip dynamics を数回行う．
3.2 Web グラフに対する LIR アルゴリズム
5. 探索物である状態から探索物でない状態にフリップしたスピンをリストから取り除き，逆に探索物でない状
本節では，リンク構造型イジング検索 (Link structural
態から探索物の状態にフリップしたスピンは探索物候 Ising Retrieval, LIR と略す) アルゴ リズムを提案する．
補に加える．
6. 探索物候補がなくなるまで，2 から 5 の操作を繰り返 【 LIR アルゴリズム】✷す探索を進める．
1. まず，全 Web ページを検索物である状態（下向きスピ
上述したイジング探索法の特徴は探索の全領域内においン：Sj = −1 ）とし ，検索物候補だけを格納したリスて探索物らしさが連続的な変化を示す性質を利用する点でトを生成する．
2. 検索物候補のリストの中からランダムに 1 つのページある．例えば ，連続的な値を取る対象物として，画像デーSa を選択する．
タ内の顔検出 [2] などが対象となっており，イジング探索法
3. ページ Sa の検索物らしさ md (a) を求める．
を用いることによる検出回数の削減や計算速度の向上が研
4. 以下の操作を数回繰り返す．
究されている．

2

日本データベース学会 Letters Vol.2, No.1

論文

DBSJ Letters Vol.2, No.1

5. 検索物候補がなくなるまで，2 から 4 の操作を繰り返し検索する．
✷4.

実験と考察

0.40.38
重要度

a Sa からリンクされるページ Si を選択する．ただし，Si は検索物らしさを測定していないものとし，このような Si が存在しない時は (5) に移る．
b e−β∆Ei に比例する確率で，Si をフリップする．
c Si の値が −1 から 1 に変わった時，Si を検索物候補リストに入れ，逆に Si の値が 1 から −1 に変わった時，Si を検索物候補リストから取り除く．

0.36

0.34

全検索

01Hd

図 1: 検索されたページの重要度の平均値 (J, β) = (0.4,0.2)

本章では，LIR アルゴ リズムの検索性能を論ずる．

4.1

LIR法

10.9

Web データを用いた実験割合

国立情報学研究所 NTCTR-3 Web 用に収集された jp ド
0.8
メイン中心の約 1500 万ページの Web ド キュメントのリ検索比率
ンク関係データ，およびアンカーテキストに関するデータ検索精度を，実験データとして使用した [8]．処理は，1.2TB (CDS30.78RS-8x160) ハードデ ィスクに格納し ，Sun Cobalt LX50012（ Intel Pentium III 1.5GHz 512MB SDRAM ）と，In外部磁場結合定数 Htel(R) Xeon(TM) Processor 1.80GHz 等で構成する機器で行った．
最初に，実験データに対して，リンクがある時に 1，無い時に 0 を対応させた，疎行列となるリンク関係行列を作 図 2: 外部磁場結合定数 Hd に対する検索比率・精度 (J =成する．そして，非ゼロ要素（この場合は 1 のみ）の要素 1.0, β = 0.5)情報のみを 2 つのベクトル col-ind と row-ptr によって格納する圧縮手法の一つである CRS 法 (Compressed RawStorage) を用いる [5]．なお，col-ind ベクトルは，どこに 要となったページ数の比，検索精度とは全検索によって得リンクしているかの情報を格納するベクトル，row-ptr ベ られるページ数に対して LIR アルゴ リズムで得られたペー
クトルは対応するページのリンク先情報が col-ind ベクト ジ数の比である．
ルのどの成分に格納されているかの情報を格納するベクト
図 1 は点線が全検索を行った時にヒットしたページの重ルである．
要度の平均値であり，その値は 0.350756 である．また，実線は LIR アルゴ リズムによってヒットしたページの重要度の平均値である．図 1 からは，LIR アルゴ リズムを適用することによって，重要度の低いページが排除され，重要度4.2 検索範囲の縮小の平均値が大きくなることが分かる．なお，以下に示す幾
本実験では，キーワード「 mining 」をアンカー部とアン つかのパラメータに対しても同様の結果を得た．
カー部の前後に含むページ群を，約 1500 万ページ群から
図 2 は，外部磁場の結合定数 Hd に対する検索結果の挙抽出し ，さらにそのページ群から 7,8 先リンク程度で辿る 動を示す．ここで，実線は検索比率，破線は検索精度を示ことのできるページ群を加えることによって検索対象ペー し，共に値が低い方が望ましい．すなわち，Hd の値は小さジ群を構成した．その結果，LIR アルゴ リズムを適用する い方が良いと考えられる．
検索対象ページ総数は 34,423 ページとなった．
図 3 は，温度に反比例する β と検索比率の関係を示している．温度低下とともに評価処理回数が減少する．逆に，温度を上げると，高温下の分子運動がリンク関係を切断する
かのように振る舞い，検索比率が上昇する．今後，詳細な検4.3 パラメータ変動による検索結果の挙動討を必要とするが，イジングモデルは臨界温度に到達する
初めに，式 (5) 中に含まれるイジングモデルを記述する と，周りの振る舞いとは極めて異なる性質を示すため，こ熱力学的パラメータ，外部磁場結合定数 Hd ，β ，結合定数 のような単調でない挙動を生じた可能性がある．
J に対する検索結果の挙動を調べる．検索結果は検索比率
表 1 では，検索比率 (I) と検索比率 (II) において，LIR ア(retrieval rate) と検索精度で評価する．検索比率とは検索 ルゴ リズムの 4 ステップ目の処理回数の影響を調べた．検対象ページ総数に対して LIR アルゴ リズムで評価処理が必 索比率 (I) は，対象となるスピンが張っているリンクの数，
d3

日本データベース学会 Letters Vol.2, No.1

論文

DBSJ Letters Vol.2, No.1

[謝辞]

0.9

Web リンク情報を提供して頂いた国立情報学研究所 NTCIR 情報検索システム評価用テストコレクション構築プロ
ジェクト [8] に感謝する．本稿の一部は，文部省科学研究費(15017248, 13680482, 14019049, 14213101) の研究成果
による．

割合0.8

検索比率0.7

検索精度

[文献]
00.1

0.2

[1] S. Chakrabarti: “Mining the Web: Analysis ofHypertext and Semi Structured Data,” Morgan
Kaufmann Publishers, (2002).

β

図 3: 温度に反比例する β に対する検索比率・精度 (J =1.0, Hd = 0.5)
表 1: 隣接リンク段数 (n) による影響 (II)n113
3(J,Hd ,β)( 1.0 , 0.1 , 0.5 )( 1.0 , 0.5 , 0.5 )( 1.0 , 0.1 , 0.5 )( 1.0 , 0.5 , 0.5 )検索比率 (I)0.799529
0.848270
0.804665
0.847538

検索比率 (II)0.756965
0.790315
0.744264
0.772083[2] K. Hotta, M. Tanaka and T. Mishima: “MultilevelIsing Search for Human Face Detection,” SPIEApplications of Digital Image Processing XXI,
pp.202–213, 1998.
[3] Hiroyuki Kawano, Minoru Kawahara: “Mondou: Information Navigator with Visual Interface,” Data Warehousing and Knowledge Discovery, Second International Conference, DaWaK
2000, pp.425-430, 2000.
[4] 河野浩之, 川原稔: “Web 検索におけるテキストマイニング ,” 人工知能学会誌, Vol.16, No.2, pp.212–218,
2001.

検索比率 (II) は，その値を 3 倍したものである．この時，[5] 河瀬基公子，川原稔，岩下武史，河野浩之，金澤正憲:
表 1 の全ての場合で，検索比率が減少している．なお，検“Web コミュニティ発見のための大規模 Web グラフ
索比率 (II) を，さらに数倍以上大きくした実験も行ったが，に対するデータ圧縮計算手法,” データベースと Web
検索比率 (II) の場合と大きな変化はなかった．
情報システムに関するシンポジウム (DBWeb2002)，
pp.423-430，2002.

5.

結論と今後の課題

近年の計算処理能力の向上により，大規模問題を扱うアルゴ リズムや手法の実装が進んでいる．しかし，Web ペー
ジをはじめとして，単調増加するネットワークコンテンツを適切に処理するには，演算能力の向上のみでは解決ができないため，計算コストを削減する多様な技術を必要とする．そこで，本稿では，物理現象を扱うイジングモデルを用いて Web モデリングを行い，Web イジング検索モデルとして提案した．また，提案した LIR アルゴ リズムによって，検索対象となる Web ページ群から，適切に候補削減できる可能性があることを実データを用いた実験により確かめた．さらに，イジングモデルで扱われる温度に対する臨界現象などの性質に基づき，温度パラメータに対して Webイジング検索モデルにおいても特徴的な振る舞いを与えることを示した．
本稿では，磁性体を表すモデルとして最も簡単で解析が十分に成されているイジングモデルを用いたが，ハイゼンベルグモデルのような連続的なスピン状態を用いたモデルへの拡張なども検討すべき課題である．また，イジングモデルにより臨界現象を適切に表現できることが良く知られているので，本実験により示した性質が理論的にどのような意味をもつかを追求する必要もある．

4[6] J. M. Kleinberg: “Authoritative Sources in aHyperlinked Enviroment,” Journal of the ACM,
pp.604–632, 1999.
[7] 那須川哲哉, 河野浩之, 有村博紀: “テキストマイニン
グ基盤技術,” 人工知能学会誌, Vol.16, No.2, pp.201–
211, 2001.
[8] http://research.nii.ac.jp/˜ntcadm/index-ja.html[9] 坂本比呂志, 有村博紀: “ウェブ・マイニング ,” 人工知能学会, Vol16, No.2, pp.233–238, 2001.

阿部 友一

Tomokazu ABE

京都大学大学院情報学研究科博士前期課程 (2003 修了).
2001 京都大学工学部情報学科卒業．日本データベース学会
学生会員.

河野 浩之

Hiroyuki KAWANO

1997 京都大学大学院情報学研究科システム科学専攻助教
授. 1990 京都大学大学院工学研究科数理工学専攻博士後期課程. 工学博士. ネットワークシステム，データベース，データマイニングなど ，情報システムに関わる範囲に興味を持つ. 電子情報通信学会，情報処理学会，人工知能学会など 所属.
日本データベース学会 Letters Vol.2, No.1