論文 / 著書情報
Article / Book Information
論題(和文)

Wikipediaのセクションを考慮したリンク解析による関連項目検索の実
現

Title(English)

Extraction of Related Articles using Links and Sections in Wikipedia (O)著者(和文)

近藤直樹, 渡辺陽介, 横田治夫

Authors(English)

Naoki KONDOH, Yousuke WATANABE, Haruo YOKOTA

出典(和文)

, , ,

A5-2

Citation(English)

, , ,

A5-2

発行日 / Pub. date2010, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2010 A5-2

Wikipedia のセクションを考慮したリンク解析による関連項目検索の実現
(O)
近藤

直樹†

渡辺

陽介††

横田 治夫††† 東京工業大学工学部情報工学科 〒 152-8552 東京都目黒区大岡山 2-12-1†† 東京工業大学学術国際情報センター 〒 152-8550 東京都目黒区大岡山 2-12-1
E-mail: †{naoki,watanabe}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらましWikipedia などの不特定参加型の百科事典サイトの登録項目数は爆発的に増えている。その結果、内容的に関連する項目を探し出す場合に、キーワード検索や項目内のリンクをたどるだけでは探し出すことが困難になっている。本研究では、Wikipedia においてリンクの結びつきを関連とし、項目内のリンクだけでは得られない関連項目も検索できる手法を検討する。各項目はセクション毎に内容が整理されており、セクションの情報を用いることで利用者の検索意図に合った関連項目の絞り込みが可能であると考えられる。提案手法では、項目内のセクションでリンク解析をすることによってより的確な関連項目を検索する手法を提案する。また、本稿では評価実験により提案手法の有効性を評価する。
キーワード

Wikipedia、リンク解析、セクション構造

Extraction of Related Articles using Link Structure and Content
Structure in Wikipedia (O)Naoki KONDOH† , Yousuke WATANABE†† , and Haruo YOKOTA††† Department of Computer Science, School of Engineering, Tokyo Institute of Technology 2-12-1
Oookayama, Meguro-ku Tokyo, 152-8552 Japan†† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology 2-12-1 Oookayama,
Meguro-ku Tokyo, 152-8550
E-mail: †{naoki,watanabe}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
Abstract The number of articles in web-based encycropedia like wikipedia is increasing. Since links between
articles are also increasing, link structure of articles becomes more complicated. We often need important articles
related to the speciﬁc article we focus on, but it is diﬃcult to ﬁnd them by only traversing links and using keyword
search. In this paper, we propose a method to extract related articles using both link structure and content structure. An article consists of multiple sections based on subtopics, and each section has links to articles related tothe subtopic. Our method performs section-level link analysis, and it extracts more focused results related to thesection of the article. We also evaluate eﬀectiveness of the method by experiments.
Key words Wikipedia, Link Analysis, Section

1. は じ め にる。Wikipedia は項目の自由な利用を認めるコピーレフトなラ
イセンス形態をとり、誰でも自由に文章の編集を行えるウィキ

Wikipedia [1] のような不特定参加者によるオンライン百科システムを採用している。Wikipedia は全世界で利用されて事典サイトが注目されている。これらは無料で使用でき、誰でおり、約 15 万人が編集に関わっている。項目の分野は幅広く、も簡単に執筆、編集できる特徴がある。この特徴により、不特一般の百科事典にない項目も多い。例えば、Wikipedia 日本語

定参加者によるオンライン百科事典サイトは世間に浸透し、項版 [1] の項目数は 64 万以上 (2009 年 7 月) となっている。

目数は爆発的に増えている。
オンライン百科事典サイトの代表例として、Wikipedia があ

オンライン百科事典サイトの他の特徴として、本の百科事典とは違い、項目中に記述されている語がハイパーリンクされてࠕ࢖ࣥࣇ࢚ࣝࣥࢨࠖࡢ㡯┠

索する手法を提案する。まず、百科事典データからセクションࠕᴫせࠖࡢࢭࢡࢩࣙࣥ

とリンク情報を抽出しておく。入力は、百科事典の項目中の利ࠕṔྐࠖࡢࢭࢡࢩࣙࣥ

用者の着目するセクションとする。入力セクションを中心にセࠕ἞⒪᪉ἲࠖࡢࢭࢡࢩࣙࣥ

クションとリンク情報からリンク解析に必要なグラフデータを

㡯┠༢఩ࡢ
ࣜࣥࢡゎᯒ

ࢭࢡࢩࣙࣥ༢఩

取得する。その際、年月のようにどんな内容からでもリンクさࡢࣜࣥࢡゎᯒ

れる一般的な項目をフィルターにより除去する。次に、項目間ࠕ࢖ࣥࣇ࢚ࣝࣥࢨࠖࡢ

ࠕ࢖ࣥࣇ࢚ࣝࣥࢨࠖࡢ

のリンクをセクション間のリンクに変換する処理を行う。最後㛵㐃㡯┠ࠕ἞⒪᪉ἲࠖ

に、重要なリンクに重みを付けてリンクを解析する。出力は、

ࡢ㛵㐃㡯┠

リンク解析の結果の上位 n 件を項目とセクションのペアで出 ࣥࣇ࢚ࣝࣥࢨ

ឤᰁ⑕࢜ࢭࣝࢱ࣑ࣅࣝ
ᅜ❧ឤᰁ⑕◊✲ᡤ

࢜ࢭࣝࢱ࣑ࣅࣝ

力する。本稿では評価実験を行って、提案手法の有効性を評価࢔ࢭࢺ࢔࣑ࣀࣇ࢙ࣥ
ࢨࢼ࣑ࣅࣝ


する。
以降、2. 節に関連研究を述べる。3. 節では主な百科事典サイトをあげる。4. 節では提案手法について述べる。5. 節では提図 1 項目単位での関連項目とセクション単位での関連項目

案手法の実験結果を述べる。6. 節ではまとめと今後の課題を述べる。

いるので、その語の項目に簡単に移動できることである。項目が違う項目をリンクしていることによって、オンライン百科事
典サイトはグラフ構造と見ることができ、リンク解析が可能である。しかし、項目数の増加に伴って、関連項目が多すぎてどれが重要な関連項目かわかりにくくなったり、関連しているにもかかわらずリンクが張られてなかったり、といった問題が起きている。そのため、百科事典サイトにおいて関連項目を検索する仕組みを提供することが重要となってきた。

Wikipedia などのオンライン百科事典サイトにおいては、項目間のリンク構造を解析することで、項目同士の結びつきの強さや、直接リンクされていない項目との関係も発見できると考えられる。これまでにも Wikipedia の関連項目をリンク解析等
で探すことは試みられている [2]。しかし、詳細に解説された項目の場合、そこからリンクされた項目の数自体が多く、またそれらがカバーする分野も広いため、利用者が本当に必要な関連項目を探し出すことは難しい。例えば、Wikipedia の「インフルエンザ」の項目には、病原体の性質に関する記述や、病気の症状に関する記述、治療方法に関する記述などがあり、それぞれ扱う内容が異なっている。扱う内容の違いから、それぞれについての関連項目は異なっており、またそれらを検索したいシ
チュエーションも違う可能性が高い。既存研究で行われたような項目単位でのリンク解析では、このような内容ごとの関連項
目の違いを考慮していなかった。
そこで本研究ではリンク構造だけでなく項目内の文書構造にも着目する。Wikipedia 等では、多くの情報を含んだ項目は複数のセクションに構造化されており、各セクションは特定の内容・分野のみについて記述されていることが多い。そのため、項目単位でリンク解析を行う場合よりも、セクション単位でリ
ンク解析をした方が内容を絞った関連項目の探索が可能である。
例えば、図 1 のように項目インフルエンザのセクション治療方法を中心にリンク解析を行って関連項目を探索した場合、項目全体を対象にした場合よりも、治療方法に特化した関連項目が提示できると考えられる。
本研究では、リンク関係に基づく重要度を用いて、オンライ
ン百科事典サイトにおいて項目内のセクションの関連項目を検2. 関 連 研 究
2. 1 リンク解析
リンク解析は、グラフ構造のリンクを解析することによって、どのノードが重要であるかを調べる手法である。特に有名なアルゴリズムは、PageRank [3] と HITS [4] である。

HITS は Web 検索によく用いられ、Web ページを Authorityと Hub で評価する。Authority とはページ自体の価値を表し、Hub とは価値の高いページをどのくらいリンクしているかを表す。HITS のアイディアは、Hub の高いページからリンクされると Authority が高くなり、Authority の高いページをリンク
すると Hub が高くなるということである。
今回、HITS を使う理由に、百科事典のリンクを多く集めている項目が Hub の高い項目、一般的な項目で重要なものがAuthority の高い項目になると考えたからである。HITS では
本来リンクに重みは付いておらず隣接行列の値は 0 か 1 であるが、本研究では、相互リンク等の重要度を考慮しているので隣接行列に重みを付けて HITS の計算をしている。

2. 2 Wikipedia におけるリンク解析
Wikipedia 英語版の全項目に PageRank や HITS を適用したらどのようになるかが報告されている [2]。

HITS の Authority では、場所や日時の項目が上位を占めているのに対し、PageRank では、文化的な項目も上位にランキングされている。これは HITS によってカテゴリー、一覧やリストの項目はそれらを指すリンクが多いことによってランキン
グが高くなることと、PageRank では歴史や文化のような一般的な語が高くなることを示している。
この報告では項目単位にリンク解析を適用しているのに対し、本研究ではセクション単位でリンク解析を行う。その際、場所や日時の項目など一般的な内容の項目は in-リンクが多いことから、リンク解析の前に in-リンクの数によってこれらを除き、ランキングの上位に表れないようにする。

2. 3 シソーラス辞書構築
Wikipedia や Web から類語辞書を構築する研究も行われている。類語辞書があることによって、キーワード検索で直接キーワードが含まれないものを検索することや自然言語処理の形態素解析において未知語の解析精度向上が可能になる。
手法には、tﬁdf のキーワード抽出やリンク解析をする手法 [5]や HTML の木構造を利用する手法 [6] やリンク構造とセクション構造を利用して語の一般性・局所性・専門性を求める手法 [7]がある。
本研究では、関連項目を探す目的でリンク解析やセクション
構造を利用しており、これらの研究とは目的が異なる。

図 2 ”インフルエンザ”のセクション

2. 4 コミュニティ発見

LQ ࣜࣥࢡ

HITS はコミュニティ発見の手法でもあり、Authority と Hub

RXW ࣜࣥࢡ

を用いてグラフを 2 部グラフ構造と仮定している。他の 2 部グラ
㡯┠フを使った手法 [8] では、2 部グラフによって fan と community

図 3 中心の項目から見たリンクの名称

center を表現する。他にも、グラフの最大フロー問題を使った手法 [9] では、最小カットでコミュニティを分割する。
本研究では、オンライン百科事典サイトに HITS を適用して、関連項目を発見する。

3. オンライン百科事典サイト
オンライン百科事典サイトの例として、Wikipedia [1]、はてなキーワード [10]、Yahoo!百科事典 [11]、コトバンク [12] など

  㡯┠がある。
オンライン百科事典サイトは、様々な分野の語を網羅し、項

図 4 項目単位でのリンク解析

目の追加が容易であるので、項目数は爆発的に増えている。これらの共通点は、項目中の語がハイパーリンクされて、サイト

内の他の項目へ簡単に移動できることである。
本研究では、百科事典サイトにリンクだけでなくセクション
構造を必要とする。実験対象として Wikipedia を用いるが、提

案手法は条件に合う百科事典サイトなら適用可能である。

3. 1 Wikipedia  㡯┠Wikipedia 日本語版の統計によると、項目は一般的な項目以外にもカテゴリー、テンプレート、議論のページなどを含み約
図5168 万以上ある。また、一般的な項目いわゆる記事は約 64 万セクション単位でのリンク解析

以上ある。
次に、Wikipedia 日本語版の 2009 年 11 月 17 日のダンプファ
イル (jawiki-20091117-pages-article.xml.bz2) による統計を述める。

4. 提 案 手 法

べる。

•
•

トップレベルのセクション 約 243 万

4. 1 目

リンク先が存在する内部リンク 約 3 千万

本研究では、利用者が閲覧している百科事典サイトの項目 A

的– このうち項目の特定のセクションを指すリンク 約 28 万に対して、項目 A 内の特定のセクション B との関連が強い項– 他は項目へのリンク 約 3 千 92 万

目 (およびセクション) のリストを提示することを目的とする。

トップレベルのセクションとは一段目のセクションのことで

ただし、百科事典の関連項目を探したい時、図 4 のようにそのあり、図 2 で言うとセクション 1,2,3 などのことである。統計

項目内のリンク先を探すだけでは関連項目が得られない。そのを見ると、Wikipedia の内部リンクはほとんど項目へのリンク

項目をリンクしている項目や、複数ステップ先のリンクの項目であることが分かる。セクション単位でのリンク解析を行う本も関連が高い可能性がある。本研究では、これらの項目も関連研究において、セクションを直接指すリンクの数が少ないこと項目として扱う。

は重要な問題となる。これについての対処は 4. 節で述べる。

4. 2 アプローチ

本研究では、被リンクも合わせてリンクと呼ぶ。リンクを呼百科事典のセクションで関連項目を探すために、項目をセク

び分けるときは、図 3 のように普通のリンクを out-リンク、被ション単位に分けて考える必要がある。図 4 では、項目 A 全

リンクを in-リンクと呼ぶ。項目毎の in-リンク数で言うと、in-体の関連項目として探すと欲しい項目が含まれているが、利用リンクが 100 以下の項目が 96% 以上、80 以下の項目が 95% 占者にとってあまり興味のない方面の項目も多く含まれる。そこ

㡯┠ $

㡯┠ &

その際、百科事典データから項目毎にデータを抽出し、その後

項目の情報からセクションやリンクの情報を抽出する。データ
ベースには、百科事典の項目、セクション、リンクの情報、項
目毎の in-リンク数情報がそれぞれテーブルとして格納されている。項目のテーブルには、タイトル、項目固有 ID、項目のテ

図6

相互リンクでセクションを特定するࣃ࣓࣮ࣛࢱ㜈್ 7BVࣃ࣓࣮ࣛࢱධຊࢭࢡࢩࣙࣥࡢ RXW ࣜࣥࢡࡢ㔜ࡳ :BRࣃ࣓࣮ࣛࢱ㜈್ 7BL┦஫ࣜࣥࢡࡢ㔜ࡳ :BF

ࣃ࣓࣮ࣛࢱ
㊥㞳 G

ධຊ

キストが含まれる。セクションのテーブルには、セクション名、

 
   

ࢧࣈࢢࣛࣇ

ࣇ࢕ࣝࢱ࣮

ࣇ࢕ࣝࢱ࣮



㡯┠᝟ሗ

㔜ࡳ

ࣜࣥࢡ


  ゎᯒ

リンク解析をするために、データベースからセクションとリฟຊ᧯సࢹ࣮ࢱ࣮࣋ࢫ

図7

クション位置番号が含まれる。項目毎の in-リンク数のテーブ

4. 3. 2 ステップ 1ࣜࣥࢡⓒ⛉஦඾ࢧ࢖ࢺ

ブルには、リンク元とリンク先のそれぞれの項目固有 ID とセルには、項目固有 ID とその項目の in-リンク数が含まれる。

ࢭࢡࢩ࣭ࣙࣥ

࢜ࣥࣛ࢖ࣥ

項目固有 ID、セクション位置番号が含まれる。リンクのテー

システム概略図

ンク情報を取得する。リンク解析のために取得する範囲は、入力セクションから in-リンク、out-リンクを使って距離 d でたどれるセクションとリンクである。その際、セクションはトップレベルのセクションを考え、下位のセクションはそのトップレ
ベルのセクションの中に属しているとみなす。また、項目へのリンクはその項目内のすべてのセクションへのリンクの集合にで、図 5 のように利用者の興味のあるセクション B に限ると、欲しい項目を探しつつ欲しくない項目を減らすことができる。
セクションの関連項目を探すので、リンク解析の際に入力セクションからのリンクは重要である。また、セクション中のリン
ク先の項目以外の関連項目を探し出すため、本研究では入力セクションを起点として in-リンクおよび out-リンクから距離 d
でたどれるセクション集合をリンク解析の対象とする。
しかし、3. 1 節で述べたようにリンクの多くは項目全体を指していて、本来どこのセクションを指しているのかを考慮する必要がある。そこで、リンク先が項目の場合は、まず項目内のすべてのセクションを指す弱いリンクの集合であるとみなし、さらにそれらのセクション内にリンク元への相互リンクがあれば、そのセクションを本来のリンク先であるとみなしてそのリンクの重みをより高くする。例えば図 6 のような、項目 A のセクション B から項目 C にリンクがあり、項目 C のセクション

D から項目 A にリンクがあれば、リンクはそれぞれセクション
D とセクション B を本来のリンク先であるとみなす。
このようにして得られる重み付きグラフに対して、リンク解析をする。本研究では、百科事典の一般的な項目を Authority、
カテゴリーや一覧の項目を Hub とみなせるので、HITS を用いるのがよいと考える。

4. 3 実現

システム概略を図 7 に示し、以下詳しく説明する。
本システムへの入力は項目名とその項目内のセクション名である。出力はリンク解析の上位 n 件の項目名とセクション名のペアをリストとして返す。内部の処理は、関連項目抽出前の準備段階と、関連項目抽出のための 3 ステップからなっており、以降では各処理について述べる。

4. 3. 1 準

備百科事典の情報を格納するデータベースを準備する。このデータベースは、事前に百科事典データを解析して構築する。

変換する。
上記の方法で取得したセクション集合には、年月や国名の項目といった多数の項目からリンクされている広い概念についての項目が含まれていることがある。このような項目は入力セクションとの関連が薄い上にリンク解析に影響を与えやすいのでフィルターにより取り除く。本研究では、2 つのフィルターを用いる。

a ) in-リンクフィルター
年月や国名の項目のようにどんな内容の項目からもリンクされる可能性のある項目は、in-リンク数は非常に多いが入力セ
クションとの関係は非常に弱いと考えられるので、本研究ではin-リンクが閾値 Ti より多い項目の in-リンク側はたどらない。
つまり、in-リンクが多い項目のセクションは out-リンク側だけをたどる。in-リンクフィルターは、セクションとリンクの取得
途中で使用する。

b ) サブグラフフィルター
サブグラフフィルターは、セクションとリンクの取得終了後に使用する。入力セクションが扱う話題に特化していないセク
ションを除くことを目的とする。その際、図 8 のように、取得したセクションとリンクのグラフを百科事典全体のサブグラフと考え、項目のサブグラフ内からの in-リンク数が全体の in-リ
ンク数に比べて割合が少なければ、サブグラフ外の項目にも関連する広い概念の項目であると考えられる。つまり、全体からの in-リンク数と比べサブグラフ内からの in-リンク数の割合が
閾値 Ts より小さい項目を除く。
これらのフィルターの効果については 5. 3 節で評価する。

4. 3. 3 ステップ 2
入力セクションを起点に取得したサブグラフ G(V, E) に対して、リンク解析のための隣接行列を作成する。HITS 等の通常のリンク解析では、ノード i とノード j の間にリンクがあれば、隣接行列の要素 Li,j の値は 1 にするが、ここでは重要なリンクを考慮するために重みを付ける。

ྲྀᚓࡋࡓࢧࣈࢢࣛࣇ

表 1 項目”デフレーション” セクション”デフレスパイラル” Wo =3, Wc = 10ࢧࣈࢢࣛࣇእ࠿ࡽ
ከ࠸

図8in-リンク サブグラフ 結果

ࢧࣈࢢࣛࣇෆ࠿ࡽ
ᑡ࡞࠸ᗈ࠸ᴫᛕࡢ㡯┠取得したセクション外にも関連する広い概念の項目•

重み Wo : 入力セクションの out-リンク•

重み Wc : すべての相互リンク

計算時間

フィルター フィルター

HITS 適用時のセクション数

なし

なし

表2

あり

なし

表3

7 分 28 秒

4774

なし

あり

表4

56 分 58 秒

7651

あり

あり

表5

5 分 15 秒

464•

5 時間 5 分 28 秒 40325

in-リンクフィルターおよびサブグラフフィルターの効果の確認

入力セクションの out-リンクであり、相互リンクするようなリ•ンクの場合は、大きいほうの重みにする。まとめると以下の式

前者については 5. 3 節で、後者については 5. 4 節で述べる。

のようになる。

5. 2 実 験 環 境


Wo if (i, j) ∈ E and i = 入力セクションLi,j = max

Wc if (i, j) ∈ E and (j, i) ∈ E(1)
1 if (i, j) ∈ E
0 otherwise

これらの重みはパラメータであり、5. 節の実験では重みを変えた時の効果について評価する。

4. 3. 4 ステップ 3

リンク重みのパラメータ Wo , Wc の影響の調査

提案手法を適用する実験環境を以下に示す。

•

CPU Intel Xeon x5570 2.93GHz (クアッドコア)•

Memory 16GB (4GBx4)•

HDD 450GBx4 (RAID5)•

開発言語 Java (JDK1.6.0 17)•

使用 RDBMS PostgreSQL 8.4.2•

Wikipedia データ Wikipedia 日本語版 2009 年 11 月 17日時点の内容 (jawiki-20091117-pages-articles.xml.bz2)

ステップ 2 で求めた隣接行列を用いてリンク解析を行う。こ

提案手法では入力セクションから到達可能な距離 d のセク

こでは HITS を適用する。HITS のアルゴリズムを以下に説明

ションを解析対象とする。今回の実験では計算量およびデータする。グラフ G = (V, E) を Authority と Hub で評価する。L

サイズの制限から d = 2 を用いた。

を隣接行列とする。ページ i ∈ V の Authority を a(i)、Hub

5. 3 フィルター効果の比較

を h(i) で表す。

ここでは、4. 3. 2 節で提案した in-リンクフィルターおよびサ∑a(i) =h(j)(2)

うに変化するかを調べる。

(j,i)∈E∑h(i) =

ブグラフフィルターにより、出力結果および処理時間がどのよ

a(j)

(3)

各フィルターのパラメータを以下のように設定する。in-リン
クフィルターが項目の除去を判定する際のパラメータは Ti = 80(i,j)∈E

k 番目の Authority をベクトル Ak = (a(1), a(2), .., a(n))T 、
Hub をベクトル Hk = (h(1), h(2), ..., h(n))T で表し、上の式を変形させる。

にする。これは、in-リンクが 80 以上の項目は全体の 5% に過ぎず、その大部分が一般的な項目であると考えられるからである。サブグラフフィルターのパラメータは Ts = 0.3 にする。これは、全体のバランスを考慮して決定した。

T

Ak = L Hk−1

(4)

Hk = LAk−1(5)2 種類のフィルターを適用した場合としない場合の計 4 通りの組合せに対して実験を行う。入力データとして項目”デフレーション”、セクション”デフレスパイラル”を与えた。入力デー

本来の HITS では初期値を A0 = H0 = (1, 1, ..., 1)T とするが、タとして項目”インフルエンザ”、セクション”治療方法”では、本研究では、入力セクションを中心とした関連項目を求めるた

取得セクション数が莫大でリンク解析に多くの時間がかかるた

めに、HITS の初期値には入力セクションに 1、それ以外は 0

め、今回は実験対象としなかった。

とする。

項目”デフレーション”、セクション”デフレスパイラル”、リ最終的な出力は、この HITS で計算される Authority の上位

n 件の項目名とセクション名のペアをリストとして返す。

5. 実

験

5. 1 目

的

ンクの重み Wo = 3, Wc = 10 で実験した結果を表 1 に示す。各組合せの出力結果のランキングは表 2, 表 3, 表 4, 表 5 である。
出力のそれぞれの列は、順位、項目名、セクション名、入力セ
クションの out-リンク先の項目かどうかを表している。また、セクション名の null はその項目の見出しを表す。

本研究では提案手法により関連する項目・セクションを発見

2 つのフィルターを使わない表 2 の結果は、関係のない年号できるかを評価するため評価実験を行った。より具体的には以の項目が出力されよくないことが分かる。表 3 の結果では、年下の内容について評価を行った。

の項目は除去できたが、まだ国名等の入力セクションの分野と表 2項目”デフレーション” セクション”デフレスパイラル” d =2, Ti = なし, Ts = なし, Wo = 3, Wc = 10
項目名セクション名入力の out-リンク

1

1985 年

誕生なし

21980 年

誕生なし

31978 年

誕生なし

41973 年

誕生なし

51983 年

誕生なし

61971 年

誕生なし

71984 年

誕生なし

82004 年

死去

なし

91968 年

誕生なし

101979 年

誕生なし

図 9 Wc = 1 に固定し、入力セクションの out-リンクの重み Wo を
変化させる

表 3

項目”デフレーション” セクション”デフレスパイラル” d =2, Ti = 80, Ts = なし, Wo = 3, Wc = 10の分野の一般的な項目が上位に来ている。2 つのフィルターを項目名セクション名入力の out-リンク

1

アメリカ合衆国

歴史なし

使った表 5 の結果は、他の 3 つの結果と比べ入力セクションの2

アメリカ合衆国

政治

なし

out-リンク先の項目のような入力と関係のある項目が出力され

3

第二次世界大戦

影響なした。また、計算時間がフィルターを使うほど短くなる点でフィ

4

日本

安全保障

なし

5

日本

外交

なし

6

第二次世界大戦

概要なし

5. 4 リンクの重みパラメータの効果

7

日本

経済・産業

なし

ここでは、4. 3. 3 節で述べた”入力セクションからの out-リン

8

日本

概要

なし

クの重み Wo ”と”相互リンクの重み Wc ”が出力結果に与える影

9

第二次世界大戦

経過（欧州・北アフリカ）

なし

10

フランス

経済

なし

ルターの効果が確認できた。

響について評価する。5. 3 節の実験で 2 つのフィルターを用いることの有効性を確認したので、ここでは常に両フィルターを用い

表 4項目”デフレーション” セクション”デフレスパイラル” d =るものとする。フィルターの閾値をそれぞれ Ti = 80, Ts = 0.30

2, Ti = なし, Ts = 0.30, Wo = 3, Wc = 10

とする。

項目名

セクション名入力の out-リンク

1

経済学

専門分野

なし

2

経済学

概要

なし

3

経済学

分類

なし

か人間が評価する。正解とする関連セクションは、セクション

4

経済学

歴史

なし

の記述に入力項目名またはその同義語 (例:淡路島と淡路) を含

5

経済学

特徴

なし

み、また入力セクションの内容に適合した記述を含むセクショ6

経済学

経済学における主な用語・概念

なし

7

経済学

外部リンク

なし

8

経済学

論争

なし

9

経済学

脚注欄

なし

リンク間の重み Wo , Wc をともに 1 にした場合は、すべての

10

経済学

関連項目

なし

リンクを等価値とみなして純粋に HITS を適用した場合と同等

5. 4. 1 評 価 方 法
出力の上位 40 件中どのくらい関連セクションが含まれているン (例:歴史に関する記述であるか等) とする。

5. 4. 2 比 較 対 象

である。よって、これをベースラインとして比較を行う。
表 5項目”デフレーション” セクション”デフレスパイラル” d =2, Ti = 80, Ts = 0.30, Wo = 3, Wc = 10

5. 4. 3 実 験 結 果
実験する入力セクションを以下に示す。

項目名セクション名入力の out-リンク

1

新自由主義

関連項目

あり

•

項目”インフルエンザ” セクション”治療方法”

2

新自由主義

概要

あり

•

項目”淡路島” セクション”歴史”

3

新自由主義

議論

あり

•

項目”淡路島” セクション”地域”

4

市場原理主義

関連項目

あり

5

グローバル資本主義

概要なし

相互リンクの重み Wc = 1 に固定して、入力セクションの

6

新保守主義

特徴

なし

out-リンクの重み Wo を変化させた結果を図 9 に示す。横軸は

7

新自由主義

null

あり

重み Wo の値、縦軸は上位 40 件中の正解数である。図 9 より、

8

小さな政府

関連項目

あり

Wo を大きくすることで関連するセクションがより多く発見で

9

小さな政府

歴史

あり

10

グローバル資本主義

関連項目

なし

きていることが分かる。また、ベースラインである Wo = 1 かつ Wc = 1 の場合よりも結果が改善されている。

は無関係の項目が上位に来ている。これは、HITS が一般的な項目を上位にランキングするからである。サブグラフフィル
ターのみを使った表 4 の結果は、表 3 と比べ入力セクション

次に、Wc を変化させた場合の実験を行う。Wo の値については、すでに上記実験から Wo >= 5 の場合が良いことが分かっているので、結果の安定していると思われる Wo = 10 に固定する。Wc を変化させた結果を図 10 に示す。結果より、「項目”イ

表 6 項目”インフルエンザ” セクション”治療方法” d = 2, Ti =80, Ts = 0.30, Wo = 10, Wc = 10
項目名

図 10

Wo = 10 に固定し、相互リンクの重み Wc を変化させる

ンフルエンザ”、セクション”治療方法”」と「項目”淡路島”、セセクション名正解

1

オセルタミビル

null

○

2

オセルタミビル概要○

3

非ステロイド性抗炎症薬

概要

×

4

非ステロイド性抗炎症薬

NSAID の分類

×5

非ステロイド性抗炎症薬

代表的な薬物×6

アセトアミノフェン

null

○

7

オセルタミビル

耐性

○

8

ザナミビル

概要

○

9

ノイラミニダーゼ阻害薬

null

×

10

エフ・ホフマン・ラ・ロシュ

歴史

○

11

非ステロイド性抗炎症薬

COX-3

×

12

後発医薬品

主な取扱会社×13

ジャーナル・オブ・ジ・ア

他の主要な医学雑誌など

×クション”地域”」では Wc を上げることで正解数が伸びている。

メリカン・メディカル・ア
ソシエーション

一方、「項目”淡路島”、セクション”歴史”」では Wc = 5 が最
14

ザナミビル

null

○

15

非ステロイド性抗炎症薬

関連項目

×

の場合でも Wc = 1 のケースよりも正解数が上がっており、相16

非ステロイド性抗炎症薬

脚注

×

互リンクを重視する提案手法の効果があることが確認できる。

17

非ステロイド性抗炎症薬

副作用の例

×

「項目”インフルエンザ”、セクション 治療方法 」は Wo = 1018

非ステロイド性抗炎症薬

禁忌

×

19

非ステロイド性抗炎症薬

COX-2

×

20

非ステロイド性抗炎症薬

NSAID 使用の注意点

×が、実際のランキング (表 6) を見ると上位 10 位までに 6 件正21

非ステロイド性抗炎症薬

歴史

×解が提示できており、提案手法が関連するセクションに高い順

22

非ステロイド性抗炎症薬

作用機序

×

位を与えられていることが確認できる。また、10 位の項目”エ23

非ステロイド性抗炎症薬

null

×

24

後発医薬品

オレンジブック×25

ジャーナル・オブ・ジ・ア

編集の中立性×

高で、Wc = 10 では逆に正解数が落ちている。しかし、いずれ

かつ Wc = 10 の場合でも正解が上位 40 件中に 8 件しかない

フ・ホフマン・ラ・ロシュ”、セクション”歴史”は正解であり、しかも入力セクションから直接リンクがない関連セクションでメリカン・メディカル・ア

ある。このように提案手法では入力から直接リンクさせていな

ソシエーション

26

エフ・ホフマン・ラ・ロシュ

null

×

27

総合感冒薬

null

×

28

オセルタミビル

外部リンク

×

5. 3 節の実験により、提案手法のフィルターによって一般的

29

オセルタミビル

参考文献

×

な項目が除去されて、関連項目が発見できることがわかった。

30

オセルタミビル

合成法

×

また、フィルターによって計算時間の短縮ができることがわ

31

オセルタミビル

副作用

○

32

オセルタミビル

一般的臨床成績

×

33

後発医薬品

外部リンク

×

5. 4 節の実験により、入力セクションの out-リンクの重み Wo

34

後発医薬品

関連項目

×

と相互リンクの重み Wc を高くすると、Wo = 1, Wc = 1 より

35

後発医薬品

脚注

×

も良い結果となった。

36

後発医薬品

その他

×

37

後発医薬品

処方箋様式

×

38

後発医薬品

日本での経緯

×

39

後発医薬品

品質再評価

×

40

後発医薬品

生物学的同等性試験

×い関連項目であっても発見可能である。

5. 5 実験のまとめかった。

これらの実験結果から、提案手法が多くの関連セクションをより効率的に探せることが確認された。

6. お わ り
本論文では、百科事典サイトの関連項目検索をセクション単ンクの重みの効果も確認された。

位でするために、相互リンクに着目し重み付けをしたグラフに

今後の課題として、入力に対する最適なパラメーターの発見

対して HITS を適用する方法を提案した。また、HITS を適用

やより多くの多様な項目・セクションに適用させた場合の実験するセクションを取得する際の、項目の in-リンクの多さによっをする必要がある。また、計算量の削減によるさらなる高速化て取得するセクションを制限するフィルターと一般項目を除去

も重要な課題である。

するフィルターを提案した。
実験システムを用いた実験の結果、提案手法の 2 つフィルターによる一般的な項目の除去が可能であることが確認された。一般的な項目が除去されたことによって、関連項目の発見が可能になった。また、2 つのフィルターは計算時間の短縮にも効果を示した。入力セクションの out-リンクの重みと相互リ

謝辞本研究の一部は文部科学省科学研究費補助金特定領域研究(#21013017) の助成により行われた。

文

献[1] Wikipedia 日本語版. http://ja.wikipedia.org/.
[2] F.Bellomi and R.Bonato. Network analysis for wikipedia.
Proceedings of Wikimania, 2005.
[3] S.Brin and L.Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, pp. 107–117,
1998.
[4] J.Kleinberg. Authoritative sources in a hyperlinked environment. the 9th ACM SIAM Symposium on Discrete Algorithms, pp. 668–677, 1998.
[5] 伊藤雅弘, 中山浩太郎, 原隆浩, 西尾章治郎. センテンスを考慮したリンク共起性解析による wikipedia からの連想シソーラス辞書構築に関する一考察. DEWS2008, 2008.
[6] 渡邉陽太郎, 浅原正幸, 松本裕治. HTML の木構造を利用した条件付確率場による固有表現分類:wikipedia からのシソーラス半自動構築. 情報処理学会研究報告, 2007.
[7] 中谷誠, 手塚太郎, Adam Jatowt, 田中克己. Wikipedia と web
検索を用いたトピック構造の抽出. DEWS2008, 2008.
[8] R.Kumar, P.Raghavan, S.Rajagopalan, and A.Tomkins.
Trawling the web for emergine cyber-communities. In Proc.
Of the 8th Intl. World Wide Web Conference, 1999.
[9] L.R.Ford Jr and D.R.Fullerson. Maximal ﬂow through a
network. Canadian Journal Mathematics, 1956.
[10] はてなキーワード. http://d.hatena.ne.jp/keyword/.
[11] Yahoo!百科事典. http://100.yahoo.co.jp/.
[12] コトバンク. http://kotobank.jp/.