Title
基本情報技術者試験の正誤解答キーワードへのWikipediaのリン
ク構造の関連度計算の応用
Author(s)
蔡ﾘ巾, 菅亮太, 史一華, 徐海燕
Citation
福岡工業大学研究論集 第45巻1号（通巻68号） P1-P8
Issue Date
2012-9
URI
http://hdl.handle.net/11478/1275
Right
Type
Departmental Bulletin Paper
Textversion Publisher
福岡工業大学 機関リポジトリ
FITREPO
基本情報技術者試験の正誤解答キーワードへの
Wikipediaのリンク構造の関連度計算の応用
蔡
（大学院情報工学専攻)菅
亮
太
（大和コンピューターサービス株式会社)一
華
（西南学院大学商学部経営学科)徐
海
燕
（大学院情報工学専攻)Computing Semantic Relatedness between Right Answer and Distracters of
Fundamental Information Technology Engineer Examination
Based on the Link Structure of Wikipedia
Shuai C
AI(Graduate School of Computer Science and Engineering)
Ryota S
UGA(Daiwa Computer Service Co., Ltd.)
Yihua S
HI(Faculty of Commerce, Seinan Gakuin University)
Haiyan X
U(Graduate School of Computer Science and Engineering)
Abstract
With the spread of WWW, Wikipedia,a collaborative Web-based encyclopedia,has been published. In order to make use of the huge data of Wikipedia,we calculate semantic relatedness between right answer and distracters of 33 selected questions of Fundamental Information Technology Engineer Examination based on the link structure of Wikipedia. With Wikipedia API and Google API we resolve the nonexistent pages and ambiguous pages problems. We also propose the method to differentiate the semantic relatedness between right answer and distracters in the same category. Calculations are carried out through Wikipedia API and MySQL database.
Key words:Semantic relatedness, Wikipedia, Link structure, Relational database.
１. はじめに WWW の爆発的な普及に伴い，Wikipediaに代表される Web 事典が 開されてきた。Wikipediaは，Wikiを利用し て構築された百科事典であり，文化，歴 ，科学，社会， 学問，自然，技術，地理などの幅広い 野の概念をカバー している。Wikipediaでは，Webブラウザを通じて，他の ユーザと議論しながら自由に記事を編集することができる ことが大きな特徴である。Wikipediaの記事数および精度 は，多くの専門家が集まって作成した百科事典「Britannica」 と同等であると Nature誌の調査で報告されている［２］。 通常の電子事典の大きな違いは，多言語間のリンク，カテ ゴリリンク構造，リダイレクトリンクなどによる密なリン ク構造を持っていることである。Wikipediaの持つリンク 構造は，近年知識抽出のために研究者から注目を集めてお り，Wikipediaを用いた様々な研究が行われている［１，３-８，13-20］。概念間の関連度の測定において，概念の網羅 性を向上させることができ，自然言語処理における未知語 の対応，同義語や多義語の判別など，これまでの自然言語 処理手法における課題を意識せずに解析することができ る。 Wikipediaの 特 徴 を 利 用 し，わ れ わ れ は Wikipediaの データを用語の学習に活用する研究を行っている［９-12］。 ただし，Wikipediaデータを e-Learning のための演習問題 の自動出題に活用する研究を行っている際に，次のような 課題が浮き彫りになってきた。 基本情報技術者試験といった国家試験の資格問題にお いて，正解と誤選択肢間の関連度は Wikipediaを用い て計算可能であろうか。言い換えれば，計算可能な割 平成24年５月７日受付
合はどのぐらいであろうか。 計算可能な部 に対して，さらに関連度の値はどのぐ らいであろうか。どのような性質があるのか。 これらの課題を明らかにするために，われわれは，過去 の基本情報技術者試験の資格問題中のアルゴリズム関係と データベース関係の資格問題33問の正解と誤選択肢の99組 に対して，Wikipediaのリンク構造に基づく関連度の計算 手法の応用を行なった。９割以上の正解と誤選択肢間の関 連度の計算ができており，Wikipediaのリンク構造に基づ く関連度の計算手法は一つの有効な方法である結果が得ら れている。具体的に，上記の結果は次の二つの問題を解決 したことによって得られている。 存在しないページ問題：資格問題中の「２ 木」と Wikipedia中の「二 木」，「線形探索法」と「線形探索」， 「２ 探索法」と「二 探索」，「ネットワークモデル」 と「ネットワーク型データモデル」というような両者 の記述法の微妙な違いによって検索できないキーワー ドが存在する。さらに，「内部スキーマ」，「論理スキー マ」，「外部スキーマ」というようなページ名としては 存在しないが，セッション名として存在するキーワー ドも存在する。われわれは，Wikipedia API と Google API を用い る こ と で 存 在 し な い ページ に 対 応 す る キーワードを見つけることにしている。 曖昧ページ問題：資格問題中の「LIFO」，「木構造」， 「キュー」などのキーワードが Wikipediaでは多義性 があるため，曖昧さの回避が求められている。われわ れは「計算機科学」カテゴリに所属する候補を選択す ることで多義性のある曖昧ページ問題を解決してい る。 さらに，計算結果から同一カテゴリ内における誤選択肢 と正解間の関連度が同じという問題が存在することも判明 した。そのため，記事のリード部 （冒頭文）を重要文と 見做して解析する LSP法も取り入れた LSPLchを提案し， 問題の解消を試みる。計算結果より差別化できたことを確 認している。 本論文は，次のように構成される。２章では，Wikipedia の特徴と関連研究について述べる。資格問題の正解と誤選 択肢間の関連度の計算を行い，存在しないページや曖昧 ページ問題の解決方法，解決後の結果と結果についての 析は３章で報告する。４章は LSP法を用いて同一カテゴリ の Lch計算結果の問題点を解消する試みについて述べる。 ５章は全体のまとめである。 ２. Wikipedia の特徴と関連研究 2.1. Wikipediaリンク構造に基づく関連度計算 Wikipedia（ウィキペディア）は，ウィキメディア財団が 運営するインターネット百科事典である。Wikipediaは，閲 覧によって情報を得るという活用以外に，研究者にとって は機械処理によって知識抽出を行う対象として注目されて いる。Wikipediaから知識抽出する際に有効な特徴を以下 に示す。 １. 質の高いリアンカーテキスト ２. コンテンツの網羅性 ３. 密なリンク構造 ４. 多言語間のリンク ５. URL による概念の一意性 ６. カテゴリリンク構造 ７. リダイレクトリンク 2011年６月28日の段階で Wikipedia（日本語版）の記事数 は約121万記事である。この記事の記事間リンク数は，約 5454万であることが かっている。これは，１つの記事あ たり平 44.9のリンク数を持っている。これらのリンクは サイト内に対するリンクのみをカウントしたものであり， サイト外へのリンクは含まれてない。これは，Wikipediaで は閉じられた空間の中で密なリンク構造を持っており，リ ンク構造を解析することで有用な情報を抽出できる可能性 が高いことを示している。 Wikipediaの特徴の１つとして言語間のリンクがある。 Wikipediaは2011年６月現在，日本語，英語，中国語，ドイ ツ語など283言語で展開されている。次に，カテゴリリンク は，ある記事（概念）がどのようなカテゴリに属するかを 指定するためのリンクである。カテゴリには専用のページ （カテゴリページ）があり，カテゴリページはさらに別の カテゴリページに属することが可能である。Wikipediaの カテゴリ構造は，図１示しているように実際にはネット ワーク構造となっている。 また，URL により語彙（概念）の一意性が確立されてい る点は，Wikipediaの大きな特徴の１つである。通常の辞書 では，１つの見出し語に対して複数の意味で詳細が書かれ ている。一方，Wikipediaでは１つの URL に１つの記事 （概念）が割り当てられているため，多義性が URL によっ 基本情報技術者試験の正誤解答キーワードへの Wikipediaのリンク構造の関連度計算の応用（蔡・菅・ ・徐) 図１ Wikipediaカテゴリ構造の例 2
て解決されている点が特徴である。一つのキーワードが二 つ以上の意味や物に用いられている場合，異なる用法を一 覧している曖昧さ回避のためのページが表示され，利用者 に一番近い記事を選ばせることにしている。一方，リダイ レクトリンクは，ある記事が参照された際に別の記事へと リダイレクトする機能を提供するリンクである。例えば， 記 事「ワール ド ワ イ ド ウェブ」を 参 照 し た 場 合，記 事 「WorldWideWeb」へと自動的にリダイレクトされる。 Wikipediaに関する研究は，大きく２つの 野に 類で きる。１つは，Wikipediaを社会現象として解明する研究で ある。例えば，Wikipediaに参加する人の目的や行動を調査 し，社会現象として Wikipediaを解析するといった研究で ある。もう一方の研究 野は，Wikipediaを言語リソースと して利用や 析をする研究である。例えば，記事（概念） 間の関係性などの有用な情報を抽出し，アプリケーション に適用する研究がこの 野に 類される。Wikipediaを解 析して概念間関連度を測定する先行研究として，大きく けると記事間リンクに基づく手法，記事内テキストに基づ く手法，カテゴリリンクに基づく手法がある。 Wikiデータを利用するには，Wikipedia API による利用 方法と，ダンプされた Wikipediaのファイルをダウンロー ドして利用方法の二つの方法がある。本論文では，３章は 前者の方法，４章は後者の方法というように二つの利用方 法とも用いている。なお，４章は2011年６月28日にダンプ された Wikipedia日本語版のファイルをダウンロードし て利用している。 2.2. Wikipediaリンク構造に基づく関連度計算 Wikipediaを概念間関連度に利用することは，2.1節にあ げ た よ う な 様々な 特 徴 に よ る 多 く の 利 点 が あ る。Wi-kipediaを解析して概念間関連度を測定する先行研究とし て，大きく けると記事間リンクに基づく手法，記事内テ キストに基づく手法，カテゴリリンクに基づく手法がある。 １つ目の関連度計算手法は，リンクの構造を解析して関 連度計算を行うのが記事間リンクの解析手法である。Wi-kipediaの記事を概念として扱い，リンクは意味的な関係を 表す。Wikipedia内部で概念同士が密なリンク構造を形成 しているため，リンク構造を解析することで概念間の関係 性を抽出することが可能である。この特徴を生かし，リン クの構造を解析して関連度計算を行うのが記事間リンクに 基づく解析手法である。 ２つ目の関連度計算手法は，テキスト内容を比較し，そ の類似度を利用する手法である。テキストを用いた手法は， 概念に関する記事内容が充実している場合に有効な手法で あり，一般にテキストに出現する単語が重複している頻度 が高いほど関連度が高くなるという えに基づく手法であ る。Gabrilovichらの研究［１］では，単語やテキストの意 味を表現するための手法として，Explicit Semantic Analy-sisを提案している。ESA では，特定の単語またはテキスト の意味を，Wikipediaの概念を基底とする高次元ベクトル で表す。これは，人間の認識に基づく明らかな概念を用い ている。 記事テキストを利用した手法では，言語によっては高度 な自然言語処理が必要であり，特に日本語では形態素解析 や構文解析などが精度に大きく影響するといった側面を 持っている。また記事テキストの量は膨大であり，解析コ ストが非常に大きいという問題点がある。 ３つ目の関連度計算手法は，Wikipediaのカテゴリ構造 を利用する方法である。Wikipediaのカテゴリ構造は記事 （概念）を 類するための階層的構造であるが，カテゴリ リンクに基づく手法はカテゴリ構造において記事（概念） 間のパスの長さが短いほど関連度が高くなるという えに 基づいている。主な研究として，Strubeらの WikiRelate! ［３］が挙げられる。Strubeらは，WordNetに用いられて きた関連度計算の手法が Wikipediaのカテゴリ構造に適 用できることを証明し，複数の条件によって精度が向上す ることを示した。WikiRelate!では，カテゴリ構造の解析手 法を２つに 類している。 ① カテゴリ構造における概念間のパスの長さに基づく手 法 ② カテゴリ構造における情報の共有度に基づく手法 評価実験において最も精度が良かった手法であるカテゴ リ構造におけるパスの長さに基づいて関連度を測定する手 法 Lchを示す。 Lch 1， 2 ＝−log 2 1， 2 (1.1) c1と c2は計算対象の２つの記事（概念）であり，length （c1，c2）は c1と c2間のカテゴリ構造を介した最短経路（図 ２）の長さであり，D はカテゴリ構造の全体の深さを表す。 ３. 資格問題の正解と誤選択肢間の関連度計算 本章では，基本情報技術者試験という国家試験の資格問 題において，正解と誤選択肢間の関連度を Wikipediaのカ テゴリ構造に基づく測定手法 Lchを用いた場合の関連度 計算について述べる。 図２ 最短経路
?? ?? △ （??） （??） （△） （??） （??） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （??） （??） （??） （??） （△） （△） （△） △ ?? （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （△） （#） （??） （#） （??） （#） （??） （??） （#） （??） （??） （??） （△） △ ?? △ 3.1. 資格問題の正解と誤選択肢間の関連度計算 基本情報技術者試験の午前問題は，正解と３つの誤選択 肢による四択問題である。コンピュータ科学基礎，コン ピュータシステム，システム開発，システム運用，ネット ワーク技術，データベース技術，セキュリティ，標準化， 経営など，幅広い 野から出題される。問題の形式は計算 問題やキーワードに関する問題などがある。 われわれは，基本情報技術者試験の午前問題の過去問中 のキーワードに関する問題中のアルゴリズム関係とデータ ベース関係の問題を選び，資格問題の正解と誤選択肢の キーワードに対する関連度計算を行った。アルゴリズム関 係とデータベース関係のキーワード関係の問題を最大限選 択するという方針で選択された問題は合計33問である。「ア ルゴリズム」関係の主な正誤選択肢ペアを表１，「データ ベース」関係の主な正誤選択肢ペアを表２に示す。 表１，表２に下線や「 」，「 」「#」記号で示されたよう に，関連度計算より前に次の問題に直面した。 １) 」という記号でマークされた多義性のあるキーワー ドが存在することである。「LIFO」など15個のキー ワードがこの種類に属する。 ２) 」という記号でマークされた存在しないキーワード が存在することである。「２ 木」などの44個のキー ワードがこの種類に属する。 表１ アルゴリズム」関係の正誤選択肢ペア 正解 誤選択肢 ２ 探索木 ヒープ ２ 探索木 AVL 木 ２ 探索木 Ｂ木 FIFO LIFO FIFO LILO
FIFO LRU（Least Recently Used)
キュー ２ 木 キュー スタック キュー ヒープ クイックソート 単純挿入ソート クイックソート 単純選択ソート クイックソート 単純 換ソート クイックソート 選択ソート クイックソート 挿入ソート クイックソート バブルソート ハッシュ法 線形探索法 ハッシュ法 ２ 探索法 ハッシュ法 二 木 ヒープソート クイックソート ヒープソート シェルソート ヒープソート バブルソート 一様 布 ２項 布 一様 布 正規 布 一様 布 ポアソン 布 再帰的（再帰） リユーザブル（プロセス） 再帰的（再帰） リロケータブル 再帰的（再帰） リエントラント 前判定繰返し 後判定繰返し 前判定繰返し 双岐選択 前判定繰返し 多岐選択 木構造 キュー 木構造 スタック 木構造 リスト構造 線形リスト（連結リスト） ２ 木 線形リスト（連結リスト） スタック 線形リスト（連結リスト） 配列 配列 連結リスト 配列 循環連結リスト 配列 重連結リスト 注：下線：redirectされた結果 ：存在しない ：曖昧 表２ データベース」の関係の正誤選択肢ペア 正解 誤選択肢 E-R モデル 階層モデル E-R モデル 関係モデル E-R モデル ネットワークモデル ボイス・コッド正規形 階層モデル ボイス・コッド正規形 関係モデル ボイス・コッド正規形 ネットワークモデル 内部スキーマ 概念スキーマ 内部スキーマ 外部スキーマ 内部スキーマ サブスキーマ 射影 結合 射影 選択 射影 和 結合 射影 結合 選択 結合 挿入 注： ：存在しない ：曖昧 #：注釈あるページ このため，われわれは，まず存在しないページ問題と曖 昧ページ問題の解決に着手することにしている。解決方法 と解決結果をそれぞれ次の二つの節で報告する。 4 基本情報技術者試験の正誤解答キーワードへの Wikipediaのリンク構造の関連度計算の応用（蔡・菅・ ・徐)
△ 3.2. 存在しないページ問題の解決 GoogleAPI を用いて存在しないページ問題の解決を試 みた。表３と表４では，それぞれ表１と表２において「 」 記号でマークされたキーワードの処理結果を示している。 存在しないページの一部の処理結果を次に示す。 ・２ 木→二 木 ・線形探索法→線形探索 ・２ 探索法→二 探索 ・リスト構造→連結リスト ・循環連結リスト→連結リスト ・E-R モデル→実体関連モデル ・階層モデル→・階層型モデル ・前判定繰返し→ループ ・内部スキーマ→スキーマ 処理結果を 析すると，資格問題のキーワードに対して， Wikipediaにページ（記事）として存在しない原因が次の二 つに けられる。 １) 用語の記述方法が異なる場合。上に示した処理結果中 の最後の二つ以外は全部この種類に属する。「２」か 「二」，「法」や「型」という字を入るかどうかという 細かい記述方法の違いがある。 ２) 詳細度が異なる場合。上に示した処理結果中の最後の 二つのキーワード，「前判定繰返し」，「内部スキーマ」 は，ページ（記事）としては存在しないが，「ループ」， 「スキーマ」というページ内のセッションとしては存 在している。すなわち，資格問題中のキーワードは Wikipedia中のページの名前のみでなく，セッション の名前として表れていることもある。 存在しないキーワード中，処理できなかったキーワード は，表３においては「多岐選択」「双岐選択」の２つのみで あり，表４においては「挿入」の１つのみである。それぞ れ表３と表４において，太字で表示している。 3.3. 曖昧ページ問題の解決 多義性を持つキーワードに対しては，候補の所属するカ テゴリによって判定することで処理している。例えば， 「LIFO」に対する候補は，次の二つである。 後入先出法：会計における LIFO スタック：コンピュータにおける LIFO 前者の候補「後入先出法」の所属するカテゴリは，「会計」 であり，後者の候補「スタック」の所属するカテゴリは， 「データ構造」，「データ型」である。われわれは基本情報 技術者試験という資格問題を対象にしているため，図１に 示しているように「計算機科学」という親カテゴリに属す る候補を選ぶことにした。具体的に，ここでは，後者の「ス タック」が選ばれることになる。 曖昧処理に関する一部の結果を，次に示す。 ・LIFO→スタック ・キュー→キュー（コンピュータ） ・ハッシュ法→コンシステントハッシュ法 ・木構造→木構造（データ構造） ・キュー→キュー（コンピュータ） ・結合→関係代数（結合） 処理結果を 析すると，資格問題のキーワードに対して， Wikipediaに複数の候補が存在する場合は，資格問題の性 質より「計算機科学」という親ディレクトリ内の候補を選 ぶ方法で，適切に曖昧問題を処理することができた。 表３と表４には存在しないページ問題と曖昧ページ問題 を処理後のキーワードに対して，Wikipedia API による Lch の計算結果を示している。括弧内は Lch をパーセン テージに換算した結果を示している。なお，カテゴリ構造 に閉路が存在する場合は，下から最初に出会った親を選択 するという最短経路方法で処理している。 表３ 表１に対する処理結果 正解 誤選択肢 Lch（％) ２ 探索木 ヒープ 1.3424226808222(1) ２ 探索木 AVL 木 1.3424226808222(1) ２ 探索木 Ｂ木 1.3424226808222(1) FIFO スタック 1.3424226808222(1) FIFO LILO 0.74036268949424(0.55151235156485) FIFO LRU（Least Recently Used） 0.74036268949424 (0.55151235156485) キ ュ ー （ コ ン ピュータ） 二 木 1.3424226808222(1) キ ュ ー （ コ ン ピュータ） スタック 1.3424226808222(1) キ ュ ー （ コ ン ピュータ） ヒープ 1.3424226808222(1) クイックソート 挿入ソート 1.3424226808222(1) クイックソート 選択ソート 1.3424226808222(1) クイックソート 換ソート 1.3424226808222(1) クイックソート 選択ソート 1.3424226808222(1) クイックソート 挿入ソート 1.3424226808222(1) クイックソート バブルソート 1.3424226808222(1) コンシステント ハッシュ法 線型探索 1.3424226808222(1) コンシステント ハッシュ法 二 探索 1.3424226808222(1) コンシステント ハッシュ法 二 木 1.3424226808222(1) ヒープソート クイックソー ト 1.3424226808222(1) ヒープソート シェルソート 1.3424226808222(1) ヒープソート バブルソート 1.3424226808222(1) 一様 布 二項 布 1.3424226808222(1)
一様 布 正規 布 1.3424226808222(1) 一様 布 ポアソン 布 1.3424226808222(1) 再帰的（再帰） リユーザブル （プロセス） 0.74036268949424 (0.55151235156485) 再帰的（再帰） リロケータブ ル 1.3424226808222(1) 再帰的（再帰） リエントラン ト 1.3424226808222(1) ループ（前判定 繰返し） ループ（後判 定繰返し） 1.3424226808222(1) ループ（前判定 繰返し） 双岐選択 ― ループ（前判定 繰返し） 多岐選択 ― 木構造（データ 構造） キュー（コン ピュータ） 1.3424226808222(1) 木構造（データ 構造） スタック 1.3424226808222(1) 木構造（データ 構造） 連結リスト 1.3424226808222(1) 線形リスト（連 結リスト） 二 木 1.3424226808222(1) 線形リスト（連 結リスト） スタック 1.3424226808222(1) 線形リスト（連 結リスト） 配列 1.3424226808222(1) 配列 連結リスト 1.3424226808222(1) 配列 連結リスト （循環連結リ スト） 1.3424226808222(1) 配列 連結リスト （重連結リス ト） 1.3424226808222(1) 注：二重下線：曖昧処理，存在しないページ処理，または リダイレクトページ処理された結果 太字：処理できなかったキーワード 表４ 表２に対する処理結果 正解 誤選択肢 Lch（％) 実体関連モデル 階層型データ モデル 1.3424226808222(1) 実体関連モデル 関係モデル 1.3424226808222(1) 実体関連モデル ネットワーク 型データモデ ル 1.3424226808222(1) リレーションの 正規化 階層型データ モデル 1.3424226808222(1) リレーションの 正規化 関係モデル 1.3424226808222(1) リレーションの 正規化 ネットワーク 型データモデ ル 1.3424226808222(1) スキーマ（内部 スキーマ） スキーマ（概 念スキーマ） 1.3424226808222(1) スキーマ（内部 スキーマ） スキーマ（外 部スキーマ） 1.3424226808222(1) スキーマ（内部 スキーマ） スキーマ（サ ブスキーマ） 1.3424226808222(1) 射影 関係代数（結 合） 0.64345267648619 (0.47932196444423) 射影 関係代数（選 択） 0.64345267648619 (0.47932196444423) 射影 関係代数（和) 0.64345267648619 (0.47932196444423) 関係代数（結 合） 射影 0.64345267648619 (0.47932196444423) 関係代数（結 合） 関係代数（選 択） 1.3424226808222(1) 関係代数（結 合） 挿入 ― 注：二重下線：曖昧処理，存在しないページ処理，または リダイレクトページ処理された結果 太字：処理できなかったキーワード 3.4. 結果 析 表３と表４に示された「アルゴリズム」関係と「データ ベース」関係の資格問題の正誤選択肢間の関連度 Lchの パーセンテージ（％）に変換後の結果はほぼ１，つまり100％ ということが かる。100％でない次の各場合について，さ らに 析を行うことにした。 １) FIFOと LILO ２) FIFOと LRU ３) 再帰的とリユーザブル ４) 射影と結合，選択，和 最初の２つの場合は，「FIFO」と「LILO」や「LRU」は 意味的の関連度は高くないが，記述上類似していることが かる。すなわち，資格問題では，意味的に近いキーワー ドのみを解答の誤選択肢に出題しているとは限らず，記述 上類似しているキーワードも出題していることがある。最 後の場合は，「射影」というキーワードで一意にページが決 められるが，そのページはここで必要とする「関係代数」 ページ中の「射影演算」ではないことに原因があることが 判明した。そのページにはる「関係代数」ページ中の「射 影演算」への注釈はあるが，われわれの処理はそれを処理 し切れてなかったことに原因がある。 まとめると，同一カテゴリに所属する二つのキーワード は，経路の長さによって，計算された Lchに違いはあるが， パーセンテージに換算した方がより意味が明確になる。た だし，いずれの記述方法にせよ，各資格問題の正解と同一 6 基本情報技術者試験の正誤解答キーワードへの Wikipediaのリンク構造の関連度計算の応用（蔡・菅・ ・徐)
カテゴリ内の３つの誤選択肢間の関連度はほぼ同じである ことが判明した。自動出題の時には，与えられた正解に対 して，関連度の高い候補を誤選択肢にするので，同じカテ ゴリに属するキーワードの関連度の差別化という課題が浮 き彫りになった。 ４. カテゴリリンク間関連度計算による問題と改良法 ３章に示しているように，同一カテゴリ内のページ（記 事）の Lch計算結果に差がない。一方，LSP法とは，記事 のリード部 （冒頭文）を重要文と見做して解析する手法 である［３］。これは，Wikipediaの各記事において，リー ド部 が多くの場合に他の概念との明確な意味関係を定義 した文であることを利用した手法である。特に，Wikipedia におけるリード部 は，ほかの概念に対する is-a関係が豊 富に定義されていることが中山らの調査によって判明して いる。 われわれは，LSP法を用いて同一カテゴリの Lch計算結 果の問題点を解消することを試みるために，LSPLch法を 提案している［９］。LSPLch法では，LSP法の え方を基 に Wikipediaの重要文を冒頭の概要部 と定め，重要文に 含まれるハイパーリンクを計算の対象概念とした。２つの 概念（記事）Ａ，Ｂから以下に式（4.1）を示す。
概念Ａのハイパーリンク ＝ a ，a ，…a ，a 概念Ｂのハイパーリンク ＝ b ，b ，…b ，b LSPLch＝12 1n∑Lch a ，B ＋m1∑Lch b，B (4.1) 概念Ａのハイパーリンクは，概念Ａに関する説明用語で あると え，対象の概念Ｂと Lch計算することで概念Ａと の関係性の指標を増やす目的がある。同じように，概念Ｂ のハイパーリンクも概念Ａに対して Lch計算を行う。各リ ンク数の平 をとり足し合わせ，最後に全体で割ることで LSPLch の値とする。 図３には，同じ「ソート」カテゴリに属する「クイック ソート」（正解）と，「挿入ソート」，「選択ソート」，「バブ ルソート」という３つの誤選択肢，「ヒープソート」（正解） と，「クイックソート」，「シェルソート」。「バブルソート」 という３つの誤選択肢間の LSPLChによる計算結果を示 している。明らかに，同一カテゴリ内における各キーワー ド間の差別化を図ることができた。 ただし，記事によってハイパーリンクの い方に差があ り，影響を受けやすいことがある。例えば，図３の計算結 果において，クイックソート（正解）と，「挿入ソート」， 「選択ソート」，「バブルソート」３つの誤選択肢との関連 度の順が， ① 選択ソート」 ② バブルソート」 ③ 挿入ソート」 というようになっているが，正解のクイックソートは， バブルソートと同じ 換ソートの 類に属するので，①と ②の順序が素直になるほどとはいきにくい。同じく「ヒー プソート」が正解の後者の問題の場合も，②番の「バブル ソート」と③番の「クイックソート」の順序もなるほどと はいきにくい。すなわち，LSPLch法では同一カテゴリ内に おける各キーワード間の差別化をすることはできるが，記 事の質によって左右されることがある。 ５. まとめ 本研究では，Wikipediaのリンク構造のカテゴリリンク に基づく概念間の関連度計算を，基本情報技術者試験の資 格問題中のアルゴリズム関係とデータベース関係の資格問 題33問に応用した。存在しないページ問題や曖昧ページ問 題を処理した後は，９割以上の正誤解答のキーワード間の 関連度の計算ができた。 Wikipedia のリンク構造に基づ く関連度の計算手法は，資格問題の正誤解答のキーワード 間の関連度において一つの有効な方法であることを確認で きた。言い換えれば，正解のキーワードを決めれば，誤選 択 肢 は Wikipediaにお い て 正 解 と 同 じ ディレ ク ト リ の キーワードか関連項目中のキーワードから選択すれば，実 用的な演習システムを構築できる結果が得られた。 なお，同一カテゴリに所属するページ（記事）の差別化 を図るため，LSP法の えを基にした LSPLch手法による 計算も行った。その結果，同一カテゴリ内の記事を差別化 することができた。ただし，関連度計算結果は記事の質に よって左右されることがある。今後の課題としては，同じ ページの異なるセッションに属するキーワード間の関連度 の処理などが上げられる。 参 文献
１) Gabrilovich, E., and Markovitch, S. : Computing 図３ LSPLchによる計算結果
Semantic Relatedness Using Wikipedia based Explicit Semantic Analysis., in Pros. of Inter. Joint Conf. on Artificial Intelligence(IICAI 2007),pp.1606-1611(2007) ２) Giles, J. : Internet Encyclopedias Go Head to Head,
Nature, Vol.438, pp. 900-901 (2005)
３) Strube,M.,and Ponzetto,S.P.:WikiRelate!Comput-ing Semantic Relatedness UsPonzetto,S.P.:WikiRelate!Comput-ing Wikipedia, in Proc. of the American Association for Artificial Intelligence (AAAI 2006), pp. 1419-1424 (2006)
４) Shuai Cai, Ryota Suga and Haiyan Xu :Path based Semantic Relatedness Comparison among Wikipedia Language Editions, 64 Record of Joint Conf. of Elec. and Elec. Eng. in Kyushu, 07-2A-07 (2011)
５) Torsten Zesch, Iryna Gurevych. : Analysis of the Wikipedia category graph for nlp applications,in Pros.of the Workshop TextGraphs-2 :Graph-Based Algorithms for Natural Language Processing at HLT-NAACL 2007, pp. 1-8 (2007)
６) 伊藤 雅弘：Wikipediaを用いた概念間の関連度測定 に関する研究, Osaka University Knowledge Archive (OUKA) (2011) ７) 新井 嘉章, 福原 知宏, 増田 英孝, 中川 裕志： Wikipediaの言語間リンクに関する 析, 第22回人工知 能学会 全大（JSAI 2008), 2D3-02（2008） ８) 新井 嘉章, 福原 知宏, 増田 英孝, 中川 裕志： Wikipediaを用いた多言語情報アクセスに関する研究： 言語間リンクの 析と応用, 第20回セマンティックウェ ブとオントロジー研究会,pp.SIG-SWO-A803-15（2009） ９) 菅 亮太, 徐 海燕：Wikipediaリンク構造の関連度 による用語抽出及び用語問題の自動生成, 火の国情報シ ンポジウム2012, B-4-4（2012） 10) 菅 亮太, 徐 海燕：Wikipediaカテゴリ構造の関連 度計算による用語抽出および演習システムへの適用, 平 23九州連大, 07-2A-07（2011） 11) 菅 亮太, 徐 海燕：Wikipediaのリンクを活用した 用語問題に関する演習システムの構築, 平23信学 全 大, ISS-273（2011） 12) 菅 亮太, 徐 海燕：Wikipediaを利用した用語問題 に関する演習システムの構築, 平22九州連大, 08-2A -11（2010） 13) 鈴木 優, 吉川 正俊：Wikipediaにおけるキーパー ソン抽出による信頼度算出精度および速度の改善, 第21 回セマンティックウェブとオントロジー研究会（第２回 Wikipedia ワーク ショップ）（SIG-SWO), A901-01 （2009） 14) 杉原 大悟, 増市 博, 梅基 宏, 鷹合 基行：Wi-kipediaカテゴリ階層構造の固有名詞 類実験における 効果, 情報処理学会研究報告. 情報学基礎研究会報告 2009(2), pp. 57-64（2009） 15) 玉川 奨, 桜井 慎弥, 手島 拓也, 森田 武 , 和 泉 憲 明, 山 口 高 平：日 本 語 Wikipediaイ ン フォ ボックスからのプロパティ自動抽出, the 24th Annual Conf. of the Japanese Society for Artificial Intelligence (JSAI 2010), 2I3-NFC4-3（2010） 16) 中山 浩太郎, 原 隆浩, 西尾 章治郎：Wikipedia マイニングによるシソーラス辞書の構築手法, 情処学論 47(10), pp. 2917-2928（2006） 17) 中山 浩太郎, 原 隆浩, 西尾 章治郎：自然言語処 理とリンク構造解析を利用した Wikipediaからの Web オントロジ自動構築に関する一手法, 電子情報通信学会 第19回データ工学ワークショップ, A3-2（2008） 18) 森 竜也, 増田 英孝, 清田 陽司：Wikipediaを活 用した言語間差異比較システムの提案, DEIM Forum 2010, A5-5（2010） 19) 舟生 日出男, 穐山 雅 , 平嶋 宗：問題解決プロ セスを利用した選択問題の誤選択肢および解説の自動生 成, 2010.3.1, 信 学 誌 D, Vol. J93-D, No.3, pp. 292-302（2010） 20) 山崎 由佳, 井 崇, 熊坂 賢次：Wikipediaにお ける編集者の活動 析, 第21回セマンティックウェブと オントロジー研 究 会（第 ２ 回 Wikipediaワークショッ プ）（SIG-SWO), A901-01（2009） 8 基本情報技術者試験の正誤解答キーワードへの Wikipediaのリンク構造の関連度計算の応用（蔡・菅・ ・徐)
