論文

DBSJ Letters Vol.6, No.1

URL の類似性に着目した WWW
空間からの関連語自動収集手法

空間から自動収集することを目的とする．ここで，関連語とは基底単語と共起関係にある単語（関連候補語）の中でも特に意味的なつながりがある単語を表す．
従来のWWW空間からの関連語収集手法は，Webページ内の出現単語の頻度情報を利用するものがほとんどであった．特に，基底単語とその関連候補語との意味的な関連性を双方の単語と共に出現する共起単語の頻度情報に基づいて相互情報量やJaccard係数により計算する手法[3]，[4]が主であった．
しかし，これらの手法では関連候補語と共起する単語群を得るために，WWW検索エンジンを用いて関連候補語が存在するページを検索し，それら大量のページにアクセスしなければならず，関連語収集に莫大な時間コストを必要としていた．
例えば，100個の関連候補語を対象にして各単語につき検索結果上位100件のページを取得すると，10,000件ものページをダウンロードすることになる．
この問題に対して，我々は WWW 上の各ページに URL が付随していることに着目し，URL を手がかりにして，WWW 空間から関連語を自動収集する手法を提案する．URL には各ページ間の階層関係を含んでいるため，基底単語群が存在するページの URL 集合と関連語が存在する URL 集合間に類似性があると予測される．また，URL に関する情報は，検索結果のサマリページから取得可能であるため，個々のページをダウンロードする必要がなく，高速な関連語収集が可能になる．
本手法では，既存のWWW検索システムに対する各関連候補語の検索結果から得られるURL集合と，基底単語群から得られたURL集合との間でパス毎の一致性が高ければ，その関連候補語を関連語として採用する．例えば，基底単語“本塁打”と“ホームラン”から得られたURL集合には，同一のサイトやホスト名に類似性をもつサイトが多数出現する．そして，関連候補語“松井秀喜”の検索結果から得られるURL集合が基底単語群のURL集合と高い類似性をもっていれば，この関連候補語は関連語であると判断する．

A Collection Method of Related Words
Automatically from WWW by the Similarity
of URL

獅々堀 正幹1
山本 一晴2
小泉 大地3
北 研二4
Masami SHISHIBORI Issei YAMAMOTO
Daichi KOIZUMI Kenji KITA

本論文では，数個のシーズとなる単語（基底単語）を準備し，その基底単語群の関連語を WWW 空間から効率的に自動収集する手法を提案する．WWW 空間から関連語を収集するにあたり，単語が存在するページの URL に着目する．
URL には各ページ間の階層関係を含んでいるため，基底単語群が存在するページの URL 集合と関連語が存在するURL 集合間に類似性があると予測される．そこで本手法では，基底単語群を既存の WWW 検索システムに入力することで得られる検索結果の URL に対して，URL のパス毎に出現頻度を重み付けすることにより，基底単語群の URL 集合と類似した URL 集合を有する単語を関連語として収集する．
In this paper, we propose the method to collect related
words from WWW space by using related basis words, whichhave the same meaning. We paid attention the URL of thepage where each word appears, because there is therelationship between the set of URL of basis words andrelated words if basis words have the same meaning. Thismethod gives the frequency weight to each pass of URL andcollects related words from Web sites where have highrelation to basis words.

2. 従来の関連語収集手法
従来の代表的な関連語収集技術を大別すると，単語の共起情報を基に求めた相互情報量により関連語を収集する方法[1]，[6]，及び検索結果内に出現する単語の類似性により関連語を収集する方法[3]に分類できる．
まず，相互情報量を用いる手法では，出現頻度の極端に低い固有名詞との共起頻度が悪影響を及ぼすため， WWW空間における関連語収集手法としては不適切である．次に，出現単語の類似性による関連語収集手法について説明する．これは，2つの単語xとyをそれぞれWWW検索システムを用いて検索し，検索結果から得られる共通単語に対して，頻度ベクトル間の類似度を式(2)で得られるJaccard係数で評価する．

1. はじめに関連語の自動収集に関する研究は，自然言語処理システムにおける言語知識辞書の構築[1]，[2]，また，情報検索システムにおける検索質問拡張など，様々な分野で有効活用されている．特に近年，インターネット技術の発達に伴い，WWW空間から関連語を自動収集する研究が活発に取り組まれている[3]-[5]．本研究では，数個のシーズとなる単語（基底単語）を準備し，基底単語群に意味的に関連した単語をWWW

ni" (CF ( x ), CF ( y )) = n2in(2)

i=1

i=1

ここで，単語xとyの共通単語に対する頻度ベクトルを

1 正会員

12i=1
n

$ csi + $ cwi % $ csi # cwi
i=1

徳島大学大学院ソシオテクノサイエンス研究部
bori@is.tokushima-u.ac.jp
2 非会員 徳島大学大学院工学研究科博士前期課程
issei@is.tokushima-u.ac.jp
3 非会員 徳島大学大学院工学研究科博士後期課程
koizumi@is.tokushima-u.ac.jp
4 非会員 徳島大学高度情報化基盤センター
kita@is.tokushima-u.ac.jp$ cs # cw

CF ( x) = (cs1, cs 2, L, csi, L, csn)!

CF ( y) = (cw1, cw 2, L, cwi, L, cwn)とする．
Webの内容解析による関連語の収集手法は，関連候補語数の影響でWWW空間へのアクセス数が多くなり，収集に膨大な!
時間を費してしまう．また，基底単語の検索結果における出現単語と関連候補語の検索結果における出力単語の共起単

日本デー タベー ス学会 Le tte rs V ol .6 , No. 1

論文

DBSJ Letters Vol.6, No.1

語に着目して関連度を計算するため，“今日”や“私”など一般的に用いられる語句も関連度に影響を及ぼしてしまうという問題点がある．

3. URL の類似性に基づく 関連語収集手法
3. 1

本 手法の 概要

図 1 に提案する関連語自動収集手法の概要を示し，収集手順を説明する．なお，手順 2 で示す URL データベースの構
築方法[6]，及び手順 5 で示す関連度の計算方法については3.2，3.3 で詳しく述べる．

図1
Fig.1

本収 集手 法 の概 要図

Outline of the Proposed Method.

［関 連語 収集 ア ルゴ リズ ム］
手順 1 ：基 底 単語 が存 在す る ペー ジを 検索
あらかじめ人手で登録した基底単語群 keyi（1≦i≦n ）をWWW 検索システムに入力し，各基底単語毎に上位 m 件の検索結果 URLij（1≦j≦m）を得る．
手順 2 ： URL デー タベ ース の 構築
手順 1 で得た検索結果 URLij からパス毎の頻度を計算し，各頻度に対して WWW 空間全体の大域的頻度を用いて正規化を行い，URL データベースを構築する．
手順 3 ：ペ ー ジ内 容の 解析 （ 単語 出現 頻度 の 計算 ）手順 1 で得た検索結果のサマリページを形態素解析し，名詞系単語 wk（1≦k≦p）の出現頻度 Freq(wk)を集計する．
ここで，出現頻度上位の単語を関連候補語とする．
手順 4 ：出 現 単語 の URL を取 得
各関連候補語 wk を WWW 検索システムに入力し，単語毎に上位 M 件の検索結果 URLkl（1≦l≦M）を得る．
手順 5 ：関 連 度の 計算
URL データベースと URLkl とのマッチングを行い，各関連候補語 wk の関連度を求める．
手順 6 ：関 連 語の 特定
手順 5 で求めた関連度と出現頻度 Freq(wk)の積から類似度を求め，類似度上位の関連候補語を関連語と特定する．
以上に示す通り本手法では，上記アルゴリズムの手順 2 において，基底単語群が出現する URL 集合を特定し，手順 4において関連候補語が出現する URL 集合を求め，手順 5 において双方の URL 集合の類似性を計算している．

2

3. 2

U RL データ ベース の構築 方法

3.1 の手順 1 で得られた URLij に対し，WWW 空間中のURL 出現頻度で正規化する．これより，基底単語群と関連性の低い Web サイトの検出を抑え，関連性の高いと思われる Web サイトを特定することができる．以下に URL データベースの構築手順を示す．
［UR L デ ータ ベ ース 構築 アル ゴ リズ ム］
手順 1 ：部 分 URL 毎の 出 現頻 度の 計算
URLij 内に出現する部分 URL の出現頻度を求める．部分
URL は，“/”を区切りとして分割したものである．例として，“http://www.tokushima-u.ac.jp/G-life/main.htm” の URLに対して部分 URL を求めると“www.tokushima-u.ac.jp”,“www.tokushima-u.ac.jp/G-life”の 2 つの部分 URL が作成される．これらの部分 URL の各パスの共通部分の頻度を出現頻度とする．
手順 2 ：部 分 URL の大 域 的頻 度の 取得
各部分 URL を WWW 検索システムの URL 検索機能に入力し，検索結果内の「検索件数」を部分 URL が WWW 空間中に存在する大域的出現頻度とする．
手順 3 ：部 分 URL の出 現 頻度 の正 規化
手順 1 の出現頻度を以下のように大域的出現頻度で正規化し，その値を関連度とする．
関連度=部分 URL の出現頻度／部分 URL の大域的出現頻度
図 2 に上記の手順に従い，部分 URL の出現頻度の正規化を行う例を示す．この例では，3 つの URL から作成される
部分 URL が登録されている．部分 URL は(a)www.tokushima-u.ac.jp(b)www.tokushima-u.ac.jp/G-lifeの 2 つであり，(a)のデータベース内での出現頻度は 3，(b)は 2 である．次に，各部分 URL を WWW 検索システムのURL 検索機能に入力して検索を行うと(a)は 8570 件，(b)は78 件の 検 索結 果 を 得る ． 最 後に 正 規 化 を行 う と ，(a)は0.00035，(b)は 0.0256 となる．この関連度は，基底単語群が出現しやすい Web サイトとの関連性を示している．

図2Fig.23. 3

部分 URL 出現 頻度 の正 規 化の 例

Normalization of Partial URL Frequency.

部分 U RL マッチ ングに よる関 連度計 算

3.1 の手順 5 では，構築した URL データベースと関連候補語の検索結果から取得した URL 集合間で，部分 URL 毎にマッチングを行い，マッチングに成功した部分 URL の関連度の総和を求める．例として，図 3 の URL データベースに用いて，関連候補語の URL 集合が以下の(1)~(3)であった場合の処理内容を示す．
(1) www.tokushima-u.ac.jp(2) www.tokushima-u.ac.jp/G-life

日本デー タベー ス学会 Le tte rs V ol .6 , No. 1

論文

DBSJ Letters Vol.6, No.1

(3) www.tokushima-u.ac.jp/a2/G-life
まず，(1)の URL は URL データベースと照合すると，“www.tokushima-u.ac.jp”まで一致しているので，関連度は 0.00035 となる．次に，(2)は“www.tokushima-u.ac.jp/G-life”まで一致しているため 0.0256 となる．(3)については，“www.tokushima-u.ac.jp”まで一致しているため，(1)と同じ 0.00035 となる．このように，部分 URL のマッチングを行い，この関連候補語の URL 集合における関連度は，(1)~(3)の URL の関連度を総和とする．なお，本手法では，URL データベース内において部分 URL とのマッチングを効率的に行うため，共通接尾辞を併合できるトライ構造[7]によって URL データベースを構築している．

4. 評価
4. 1

実 験条件

本手法の有効性を確かめるため，7 種類の分野（野球，車，有害，競馬，アイドル，サッカー，相撲）の基底単語群について単語数を変化させて（1 個，3 個，5 個）収集した関連語を評価した．まず，各基底単語群を Google サーチエンジン[9]に入力して得たサマリを形態素解析[10]し，名詞系単語のうち出現頻度上位 500 件の単語を関連候補語とした．そして，提案手法と従来手法を関連候補語に適用した際の上位100 件の関連語に対する平均適合率[11]を評価した．なお，従来手法としては Jaccard 係数を用いる手法[3]を採用し，正解データは人手で判定した．

4. 2

図3Fig.3

Graph of the Average Precision on One
Basis Word.

従 来手法 との収 集精度 の比較

図 3~図 5 に提案手法と従来手法との比較実験結果を示す．
各グラフ内で，“jaccard_summary”が検索結果のサマリに対して従来手法を適用した結果，“jaccard_html”がサマリからリンクする各 HTML ページに対して従来手法を適用した結果，“url_base”が提案手法を示す．
まず，検索結果のサマリに対して従来手法を適用した場合の精度が極端に悪くなっている．これは，基底単語と関連候補語のそ れぞ れのサ マリに 出現す る共通 単語 が少な く，Jaccard 係数では的確に関連性を評価できないことが要因となっている．次に，HTML ページに対して従来手法を適用した場合と提案手法を比較すると，ほとんどの分野において提案手法の平均適合率が従来手法よりも上回っており，提案手法は収集精度に関して有効であるといえる．
しかし，提案手法における分野毎の結果を比較すると，精度に大きな違いが生じている．特に，アイドル分野とサッカー分野で平均適合率が低下している．これは，アイドル分野におけるアイドルの名字・名前が的確に切り出せていないことや，“画像”や“壁紙”など曖昧な意味を有する単語が頻繁に出現しノイズになっていることが原因と考えられる．また，サッカー分野では形態素解析の辞書に登録されているサッカー用語，国名や外国人選手の氏名が少なく，形態素解析の失敗が精度を低下させる原因となっていた．
次に，基底単語の個数を増加させると，平均的に収集精度が上昇した．これは，基底単語の個数を増やすことで，サマリに出現する適合単語の種類や頻度も増加したために収集精度が上昇したと考えられる．また，URL データベースを構築する際の URL データが増加し，より高精度のデータベースが構築できたと考えられる．

図4Fig.4

基底 単 語 3 個 に対 する 平均 適 合率

Graph of the Average Precision on Three
Basis Words.

図5Fig.5

3

基底 単 語 1 個 に対 する 平均 適 合率

基底 単 語 5 個 に対 する 平均 適 合率

Graph of the Average Precision on Five
Basis Words.

日本デー タベー ス学会 Le tte rs V ol .6 , No. 1

論文
4. 3

従 来手法 との収 集時間 の比較

今回の実験では，関連語収集の際に両手法が WWW 空間にアクセスした回数により比較を行った．表 1 に，両手法の基底単語数の違いによる平均 WWW 空間アクセス数を示す．
表 1 に示すように，サマリに対する従来手法が最もアクセス数を少ない．しかし，4.2 で示したように，サマリに対する従来手法は収集精度が極端に悪くなってしまう．そこで，HTML に対する従来手法とサマリに対する提案手法を比較すると，提案手法の方が少ないアクセス数で関連語を収集できている．すなわち，検索結果のサマリに対して提案手法を適用した場合が短時間，かつ，精度よく関連語収集を行うことができる．
これは，従来手法において関連候補語を検索する手順と提案手法の手順 4 における WWW アクセス数の差が要因となっている．HTML に対する従来手法では，関連候補語の検索結果に含まれるすべてのページにアクセスしなければならない．一方，提案手法では，関連候補語の検索結果としてURL 一覧が掲載されたサマリページのみを取得するだけで関連語が特定できる．例えば，関連候補語の検索結果 100 件の URL を対象とした場合，従来手法では 100 回のアクセスが必要であるが，検索結果 1 ページ内に 100 件の URL が表示されると仮定すると，提案手法では 1 回のアクセスで手順を進めることができる．ただし，提案手法では，URL デー
タベースを構築する際，各部分 URL の大域的頻度を得るためにパス毎の URL 検索を行う必要がある．そのため，提案手法では，サマリに対する従来手法よりも URL 検索のためのアクセス数が増加する．
表１ 関連語収集に必要な平均 WWW アクセス数
Table 1 Average Number of WWW Accesses Required forCollection of Related Words.
基底単語数
従来手法
従来手法
提案手法
(summary)(html)(summary)
1個
501
50,100733
3個503
50,3001,095
5個505
50,5001,455

5. まとめと今後の課題
本論文では，特定の分野に関連する基底単語群を用いて，WWW 空間から関連語を自動収集する手法を提案した．本手法では，WWW 空間の各ページに URL が付随すること着目し，基底単語群が存在するページの URL 集合と類似したURL 集合を有する単語を関連語として収集する．本手法を実装する上で，各単語が存在する URL 集合は，WWW 検索エンジンの検索結果のサマリページのみから取得できるため，高速に関連語を収集することも可能になる．評価実験では，提案手法を用いることにより，従来手法よりも関連語収集の精度と速度が向上することを示した．
今後は，形態素解析辞書に登録されていない新語や未知語についても高精度に収集するアルゴリズムを組み入れて評価を行う予定である．更に，収集した関連語を用いたアプリ
ケーションを開発し，本手法の有効性を高めたい．

DBSJ Letters Vol.6, No.1

[文献][1] 渡部広一，河岡司：常識判断のための概念間の関連度評価モデル，自然言語処理，Vol.8，No.2，pp.39-54 (2001)．
[2] 池野篤司，濱口佳孝，山本英子，井佐原均：Web 文書集
合からの専門用語獲得，情報処理学会論文誌，Vol.47，No.6(2006)．
[3] 小原恭介，山田剛一，絹川博之，中川裕志：ウェブを利用した関連語収集，第 3 回情報科学技術フォーラム（FIT2004），E-033，pp.183-184 (2004)．
[4] 岡田信哉，村上淳哉，渡部広一，河岡司：Web を用いた新概念の自動学習，第 3 回情報科学技術フォーラム（FIT2004），F-001，pp.195-198 (2004)．
[5] 大塚真吾，豊田正史，喜連川優：大域ウェブアクセスロ
グを用いた関連語の発見方法に関する一考察，情報処理学
会：データベース，Vol.46，No.SIG 8，pp.82-92 (2005)．
[6] 北研二，中村哲，永田昌明：音声言語処理-コーパスに基づくアプローチ-，森北出版 (1996)．
[7] 小泉大地，獅々堀正幹，中川嘉之，柘植覚，北研二：WWW
画像検索システムにおける有害画像フィルタリング手法，
情 報 処 理 学 会 ： デ ー タ ベ ー ス ， Vol.47 ， No.SIG 8 ，pp.147-156 (2006)．
[8] 山本一徳，獅々堀正幹，柘植覚，北研二：パトリシアト
ライの一次元配列構造への圧縮方法，言語処理学会第 11回年次大会，P4-4，pp.688-690 (2005)．
[9] Google，http://www.google.co.jp/．
[10] Mecab，http://mecab.sourceforge.jp/．
[11] 北研二，津田和彦，獅々堀正幹：情報検索アルゴリズム，共立出版 (2002)．

獅々堀 正幹M asa mi S HI SH IB ORI

徳島大学大学院ソシオテクノサイエンス研究部准教授．1993
徳島大学大学院工学研究科博士前期課程修了．博士（工学）．
マルチメディア情報検索，自然言語処理の研究に従事．著書「情報検索アルゴリズム」共立出版，情報処理学会第45回全国大会奨励賞受賞．電子情報通信学会，情報処理学会，言語処理学会，日本データベース学会正会員．

山本 一晴

Is se i YAM AM OT O

2007 徳島大学大学院工学研究科博士前期課程知能情報工学専攻修了．2005 徳島大学工学部知能情報工学科卒業．自然
言語処理の研究に従事．現在，大坂ソフトハウス勤務．

小泉 大地Da ic hi KO IZ UM I

2007 徳島大学大学院工学研究科博士後期課程情報システム工学専攻修了．2002 徳島大学工学部知能情報工学科卒業．
マルチメディア情報検索，自然言語処理の研究に従事．現在，㈱ジャストシステムに勤務．情報処理学会正会員．

北 研二

K en ji K IT A

徳島大学高度情報化基盤センター教授．1986 早稲田大学理工学科数学科卒業．博士（工学）．自然言語処理，マルチメディア情報検索等の研究に従事．平成 6 年日本音響学会技術開発賞受賞．著書「確率的言語モデル」東京大学出版会，「情報検索アルゴリズム」共立出版など．電子情報通信学会，言語処理学会正会員．

[謝辞 ]本研究の一部は，科学研究費補助金基盤研究(B)(17300036)，科学研究費補助金基盤研究(C)(17500644)
を受けて行われた．

4

日本デー タベー ス学会 Le tte rs V ol .6 , No. 1