    \documentclass[japanese]{jnlp_1.3a}
\usepackage{jnlpbbl_1.1}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[dvips]{graphicx}


\Volume{14}
\Number{2}
\Month{Apr.}
\Year{2007}
\received{2006}{2}{1}
\revised{2006}{7}{5}
\rerevised{2007}{1}{9}
\accepted{2007}{1}{16}

\setcounter{page}{3}
\jtitle{Web上の情報を用いた関連語のシソーラス構築について}
\jauthor{榊　　剛史\affiref{u-tokyo} \and 松尾　　豊\affiref{AIST} 
	\and 内山　幸樹\affiref{hottolink} \and 石塚　　満\affiref{u-tokyo}}
\jabstract{
本論文ではWeb上の情報を利用し，自動的に関連語のシソーラスを構築する手法を提案する．
検索エンジンを利用し，$\chi^2$値による語の関連度の指標を用い，
従来のWebを用いた関連度の指標の問題点を解決する．
また，新しいクラスタリング手法であるNewman法を用いて語のネットワークを
クラスタリングすることで，従来手法より適切に関連語を同定する．
コーパスおよび既存のシソーラスから生成した関連語正解セットを用い，
提案手法の効果についての検証を行う．
}
\jkeywords{シソーラス，クラスタリング，共起情報，\textit{Web}マイニング}

\etitle{Construction of Related Terms Thesauri from the Web}
\eauthor{Takeshi Sakaki\affiref{u-tokyo} \and Yutaka Matsuo\affiref{AIST} \and Koki Uchiyama\affiref{hottolink} \and \\Mitsuru Ishizuka\affiref{u-tokyo}
} 
\eabstract{
This paper describes a method to costruct related terms thesauri automatically based on Web information.
We utilize Web search engine to obtain word co-occurrence information and propose 
a new efficient similarity metrics applying $\chi^2$ value to solve problems of the existing methods.
We also introduce a new method to identify related terms using word-clustering.
We do word-clustering on that assocative network to identyfy related terms
using latest clustering methods, ``Newman method''.
We make evaluations and show the effectiveness of our approach using sets of related terms extracted from a corpus
 and a current thesaurus.
}
\ekeywords{thesaurus, co-occurence, word-clustering, Web mining}

\headauthor{榊，松尾，内山，石塚}
\headtitle{Web上の情報を用いた関連語のシソーラス構築について}

\affilabel{u-tokyo}{東京大学情報理工学系研究科電子情報学専攻}{
	Graduate School of Information Science and Technology}
\affilabel{hottolink}{株式会社ホットリンク}{hottolink, Inc.}
\affilabel{AIST}{産業総合研究所情報技術研究部門}{
	National Institute of Advanced Indutrial Science and Technology}



\begin{document}
\maketitle




\section{はじめに}

シソーラスは，機械翻訳や情報検索のクエリー拡張，語の曖昧性の解消など，
言語処理のさまざまな場面で用いられる．
シソーラスは，WordNet \cite{Miller90}やEDR電子化辞書\cite{EDR}，日本語語
彙大系\cite{goitaikei}など，人手で長い年月をかけて作られたものがよく用いられている\footnote{2003年からはWordNetだけに焦点を当てたInternational WordNet conferenceも開催されている．}．
しかし，こういったシソーラスを作成するのは手間がかかり，また日々現れる新しい語に対応するのも大変である．
一方で，シソーラスを自動的に構築する研究が以前から行われている\cite{Crouch92,Grefenstette94}．
Webページをはじめとする大規模で多様な文書を扱うには，
シソーラスを自動で構築する，もしくは
既存のシソーラスを自動で追加修正する手段が有効である．


シソーラスの自動構築は，
語の関連度の算出と，その関連度を使った関連語の同定という段階に分けられる\cite{Curran02-2}．
2語の関連度は，コーパス中の共起頻度を用いて求めることができる
\cite{Church90}．これまでの研究では，コーパスとして新聞記事や学術文書が用いられることが多かった．
それに対し，近年ではWebをコーパスとして用いる手法が提案されている．
Kilgarriffらは，Webをコーパスとして用いるための手法やそれに当たっての調査
を詳細に行っている\cite{Kilgarriff03}．佐々木らはWebを用いた関連度
の指標を提案している\cite{Sasaki05}．



Webには，新聞記事や論文といった従来からある整形された文書のみならず，
日記や掲示板，ブログなど，よりユーザの日常生活に関連したテキストも数多く存在している．世界全体で80億ページを超えるWebは，
間違いなく現時点で手に入る最大のコーパスであり，今後も増え続けるだろう．
Kilgarriffらが議論しているように，Webの文書が代表性を持つのか
といった議論はこれからも重要になるが，Webはコーパスとしての大きな可能性を秘めていると著者らは考えている．
Webをコーパスとして扱う際にひとつの重要な手段になるのが，
検索エンジンである．これまでに多くの研究が検索エンジンを用いて，Web上の文書を収集したり，
Webにおける語の頻度情報を得ている\cite{Turney01,Heylighen01}．
しかし検索エンジンを用いる手法とコーパスを直接解析する手法には違いがある
ため，従来使われてきた計算指標がそのまま有効に働くとは限らない．


本論文では，Webを対象とし，検索エンジンを用いて関連語のシソーラスを構築する手法を提案する．
特に，検索エンジンを大量に使用すること，統計的な処理を行うこと，
スケーラブルなクラスタリング手法を用いていることが特徴である．
ただし，類義・同義語に加え，上位・下位語や連想語など，
より広い意味である語に関連した語を関連語とする．


まず，2章で関連研究について述べる．そして，3章で検索エンジンを用いた
関連度の指標を提案し，さらに4章では関連語ネットワークを
クラスタリングする手法について
紹介する．そして，5章では評価実験を行い，この手法の効果について議論を行う．

\section{関連研究}


語の関連性を自動的に得る方法は，これまでにさまざまな研究が行われている．
コーパス中での語の共起情報をもとに語の関連度を測る指標として，様々なものが提案され用いられており
\cite{Church90,Wettler93,Croft99,Curran02-2}，それらは大きく2つに分けられる．
1つは単語ベクトルを用いたベクトル空間手法である．
これは，単語を多次元ベクトル空間の単語ベクトルで表現し，
それぞれの単語ベクトルを比較することで関連度を測る手法である．
ベクトル空間手法では，表\ref{CompareMethod}のようにベクトルの内積をもとにした計算指標が用いられている．
表\ref{CompareMethod}において，$x_i,y_i$はそれぞれ単語ベクトル$\vec{x},\vec{y}$の$i$番目の要素を表す．
なお，overlap係数はバイナリベクトルにしか用いることはできない．
単語ベクトルの要素の取り方は研究によって様々であり，
各文書への出現頻度を要素とするベクトルや
各単語との共起頻度を要素とするベクトルなどが考えられる．
ただし，独立な事象の確率は足し合わせることができないため，
内積を用いる関連度では，語の出現確率を単語ベクトルの要素とすることは不適切と考えられる．


もう1つはコーパス中での確率を用いる確率手法である．
この手法では，2語がコーパス中で共起する確率をもとに
関連度を算出している．確率手法で用いられている計算指標を表\ref{CompareMethod}に示す．
表\ref{CompareMethod}において，$p(w \cap w')$は語$w,w'$の共起確率を表し，
$p(w \cup w')$は語$w,w'$のどちらかが出現する確率を表す．
また$f$は\cite{Lin98a}で定義されている関数であり，$f(w,r,w')$は語$w,w'$が$r$の関係を持って
出現する頻度を，$f(*,r,w')$は語$w'$がいずれかの語と$r$の関係を持って出現する頻度を表す．
これらの計算指標は，ベクトル空間手法で用いられている指標を書き換えたものが多い．
また，単語同士の共起確率ではなく，
各単語が他の語と共起する確率の確率分布関数の類似性を
用いて関連度を算出する研究も数多く行われている\cite{Brown92,Baker98,Slonim00}．
確率分布関数を用いた類似度は，確率分布類似度(Distributional Similarity)と呼ばれる．
類似した名詞は共通した動詞と共起すると仮定し，動詞との共起分布の類似性
から関連度を算出している．

\begin{table}[b]
 \begin{center}
  \caption{類似度の計算指標}
    \label{CompareMethod}
  \begin{tabular}{|c|c|c|c|}
   \hline
    \multicolumn{2}{|c|}{ベクトル空間手法} & \multicolumn{2}{|c|}{確率手法} \\ \hline
   cosine &
       $\frac{\vec{x} \cdot \vec{y}}{\sqrt{|\vec{x}||\vec{y}|}}$ &
   相互情報量 & 
   $\log \left( \frac{p(w \cap w')}{p(w)p(w')}\right)$  \\ \hline

   dice & 
   $\frac{2(\vec{x} \cdot \vec{y})}{\sum(x_i+y_i)}$ &
   dice & 
   $\frac{2p(w \cap w')}{p(w \cup w')}$ \\ \hline

   Jaccard & 
   $\frac{\vec{x} \cdot \vec{y}}{\sum(x_i+y_i)}$ &
   Jaccard & 
   $\frac{p(w \cap w')}{p(w \cup w')}$  \\ \hline

   overlap & 
   $\frac{|\vec{x} \cap  \vec{y}|}{min(|\vec{x}|,|\vec{y}|)} $ &
   T検定 & 
   $\frac{p(w \cap w')-p(w')p(w)}{\sqrt{p(w')p(w)}}$ \\ \hline

       Lin$^{*1}$ & 
   $\frac{\sum(x_i+y_i)}{|\vec{x}| + |\vec{y}|}$ & 
       Lin98A$^{*2}$\footnotemark &
   $\log \left(\frac{f(w,r,w')f(*,r,*)}{f(*,r,w')f(w,r,*)}\right)$ \\   \hline   
\multicolumn{4}{l}{$^{*1}$ \cite{Lin98a}で提案されている手法．}\\
\multicolumn{4}{l}{$^{*2}$ \cite{Lin98a}で提案されている手法．}
   \end{tabular}
  \end{center}
\end{table}


語の関連度が得られれば，関連度に基づいて語をクラスタリングすることで関連語が得られる．
実際には，同じクラスタに分類された語同士を関連語や同義語であるとしている．
語のクラスタリングには分布クラスタリング(Distributional Clustering)が用いられることが多い．
分布クラスタリングとは，類似した名詞は共通した動詞と共起すると仮定し，
各語の動詞との確率分布の類似度に基づいて，
データを結合もしくは分割していくクラスタリング手法である\cite{Pereira93,HangLi98,Dhillon02}．

これらコーパスから関連度を自動的に算出する手法では，コーパス内に出現する
語しか扱えないという欠点がある．
そのため，広範囲の語をカバーするためには，広範囲の内容をカバーする
コーパスが必要となる．

近年では，より広範囲の語をカバーするためにWebをコーパスとして用いることが提案されている．
しかしWeb上の文書は莫大であり，直接収集し，解析するためには非常に大きな時間コストと
設備コストがかかる．そのため，Web全体での語の出現頻度や2語の共起頻度を獲得するためには
従来のコーパスを用いたシソーラス構築とは異なる工夫が必要である．
そのような工夫の一つとしてKilgarriffらは検索エンジンを用いた
手法を紹介している\cite{Kilgarriff03}．「語$w_a$」をクエリーとして検索エンジンを利用すると，
語$w_a$のWeb上でのヒット件数が得られる．検索エンジンは非常に多くのページを
クローリングしているため，このヒット件数を語$w_a$のWeb全体での出現頻度と近似できる．
同様にして，「語$w_a$ and 語$w_b$」をクエリーとすれば，
Web上での語$w_a$と語$w_b$の共起頻度を獲得することができる．

検索エンジンから獲得できる頻度情報を用いて関連度を算出する手法としては，次のようなものがある．
Heylighenは検索エンジンのヒット件数を用いた語の関連度の尺度により，語の分類や語の曖昧性解消，より優れた検索エンジンの開発
の可能性を示唆している\cite{Heylighen01}．
BaroniやTuerneyは，類義語を同定するために，検索エンジンを用いた語の関連性の尺度を提案している\cite{Baroni04,Turney01}．
Turneyはその結果を用いることでTOEFLのシソーラスの問題で平均的な学生よりもよい得点を挙げたことを報告している．
佐々木らは検索エンジンの上位ページとヒット件数を利用した専門用語集の自動構築を行っている\cite{Sasaki05}．
Szpektorは名詞ではなく動詞の関連度を検索エンジンを用いて定義している\cite{Szpektor04}．
これら検索エンジンを用いて関連度の計算を行っている研究では，条件付き確率や表\ref{CompareMethod}の確率手法で定義されているような
相互情報量，Jaccard係数が計算指標として用いられている．


\section{検索エンジンを用いた関連性の測定}
  
本章では，Web上の情報を用いて語の関連度を測る手法を提案する．

\subsection{検索エンジンのヒット件数の利用と従来手法の問題点}

検索エンジンのヒット件数を用いて2語の関連度を計算する手法について説明す
る．
ここでは，従来研究で用いられている相互情報量を計算指標として関連度を算
出する．そして，その関連度を検証し，従来手法の問題点について述べる．


具体的な例を使って説明しよう．ここで用いられている手法は，
\cite{Baroni04}のものと同一である\footnote{ただし，Baroniらは検索エンジンとしてAltavistaを用いているが，
Altavistaは日本語に正式に対応していないため，検索エンジンはGoogleを用いた．}．
関連度を測りたい語を，例えば
「インク」「インターレーザー」「プリンタ」「印刷」「液晶」「Aquos」「テレビ」「Sharp」の8語とする．
これらの語群は，Epsonのプリンタであるインターレーザーに関する語と，Sharpの液晶TVであるAquosに関する語であり，
各語の関連度を得ることで，2つのグループを適切に分けたいと仮定する．

表\ref{singlehit}に示しているのは，語群の各語に対して，
検索エンジンによって得られたヒット件数である．
表\ref{cooccur-list}には，語群中の2語を検索エンジンのクエリーとしたときのヒット件数を行列形式にしたものを示す．
例えば，「インク」と「プリンタ」であれば，
\begin{center}
``インク''  \ \ \ ``プリンタ''
\end{center}
をクエリーとして検索エンジンに入力し，そのヒット件数を調べる\footnote{ダブルクオーテーションで囲んでいるのは，
2単語以上からなるフレーズに対しても適切に処理するためである．}．8語に対してこの行列を得るには，$_8 C_2 = 28$回のクエリーが必要となる．

\begin{table}[b]
\begin{center}
\caption{語単独でのヒット件数}
\label{singlehit}
\begin{tabular}{c|c|c|c|c|c|c|c}
プリンタ & 印刷 &  \hspace{-0.5zw} {\footnotesize インターレーザー} \hspace{-0.5zw} & インク & 液晶 & テレビ & Aquos & Sharp \\ \hline
17000000 & 103000000 & 215 & 18900000 & 69100000 & 192000000 & 2510000 & 186000000 \\ 
	\end{tabular}
	\end{center}
    \vspace{\baselineskip}
\caption{2語でのヒット件数の行列}
\label{cooccur-list}
 \setlength{\tabcolsep}{2.5pt}
\begin{tabular}{c|cccccccc|c}
語/語  & プリンタ  & 印刷  
	&  \hspace{-1.3zw} \scalebox{0.6}[1]{インターレーザー} \hspace{-1.3zw}  
	& インク  & 液晶  & テレビ  & Aquos  & Sharp  & 合計 \\ \hline
プリンタ  & 0  & 4780000  & 273  & 4720000  & 4820000  & 5090000  & 201000  & 990000  & 20601273 
\\ 
印刷  & 4780000  & 0  & 183  & 4800000  & 6520000  & 11200000  & 86400  & 1390000  & 28776583 
\\ 
    \hspace{-1.3zw} \scalebox{0.6}[1]{インターレーザー} \hspace{-0.3zw}  
& 273  & 183  & 0  & 116  & 176  & 91  & 0  & 0  & 839 
\\ 
インク  & 4720000  & 4800000  & 116  & 0  & 3230000  & 4950000  & 144000  & 656000  & 18500116 
\\ 
液晶  & 4820000  & 6520000  & 176  & 3230000  & 0  & 18400000  & 903000  & 4880000  & 38753176 
\\ 
テレビ  & 5090000  & 11200000  & 91  & 4950000  & 18400000  & 0  & 840000  & 2830000  & 43310091 
\\ 
Aquos  & 201000  & 86400  & 0  & 144000  & 903000  & 840000  & 0  & 1790000  & 3964400 
\\ 
Sharp  & 990000  & 1390000  & 0  & 656000  & 4880000  & 2830000  & 1790000  & 0  & 12536000 
\\ \hline
合計  & 20601273  & 28776583  & 839  & 18500116  & 38753176  & 43310091  & 3964400  & 12536000 & 166442478 \\ 
\end{tabular}
\end{table}

Baroniらは，この2つの情報を使って求めた相互情報量の値が，語の関連度を示すよい指標になると述べている．
相互情報量は，語$w_a$の出現確率を$p(w_a)$，語$w_b$の出現確率を$p(w_b)$，語$w_a$と語$w_b$の同時出現確率を$p(w_a \cap w_b)$とすると，
\pagebreak
\begin{align}
     \label{MI}
 MI(w_a,w_b) & = \log \frac{ p(w_a \cap w_b) }{p(w_a) p(w_b)}\\ \nonumber
      & = \log \frac{ N n(w_a,w_b)}{n(w_a) n(w_b)}
\end{align}
と表される．
ここで$n(w_a)$は語$w_a$をクエリーとしたときのヒット数，
$n(w_a ,w_b)$は「語$w_a$ 語$w_b$」をクエリーとしたときのヒット数であり，
また，$N$は検索エンジンのクロールした全ページ数である．Baroniら
は$N$を3億5千万ページとしているが，2006年末現在では，Googleは約150億ページ，
AltaVistaは約120億のページである．ここでは$N=100 \times 10^8$とした．


表\ref{mutual}に相互情報量を示す．
「液晶」の行に注目すると，
「液晶」と関連が強いとあらかじめ想定している語は「テレビ」「Aquos」「Sharp」であるが，「プリンタ」や「インターレーザー」との相互情報量が大きく，
「テレビ」や「Sharp」との値は小さくなっており，適切な関連度が算出されていない．

\begin{table}[b]
	\begin{center}
	\caption{相互情報量行列}
	\label{mutual}
	\begin{tabular}{c|cccccccc}
	
語/語 & プリンタ & 印刷 
	& \scalebox{0.8}[1]{インターレーザー} 
	& インク & 液晶 & テレビ & Aquos & Sharp \\ \hline
プリンタ  & 0  & 4.195  & 7.504  & 5.878  & 4.602  & 3.635  & 4.740  & 2.029 \\ 
印刷  & 4.195  & 0  & 5.302  & 4.093  & 3.103  & 2.622  & 2.094  & 0.567 \\ 
    \scalebox{0.8}[1]{インターレーザー}  
	& 7.504  & 5.302  & 0  & 6.542  & 5.663  & 3.981  & 0.000  & 0.000 \\ 
インク  & 5.878  & 4.093  & 6.542  & 0  & 4.096  & 3.501  & 4.301  & 1.512 \\ 
液晶  & 4.602  & 3.103  & 5.663  & 4.096  & 0  & 3.518  & 4.840  & 2.222 \\ 
テレビ  & 3.635  & 2.622  & 3.981  & 3.501  & 3.518  & 0  & 3.746  & 0.655 \\ 
Aquos  & 4.740  & 2.094  & 0.000  & 4.301  & 4.840  & 3.746  & 0  & 4.534 \\ 
Sharp  & 2.029  & 0.567  & 0.000  & 1.512  & 2.222  & 0.655  & 4.534  & 0 \\ \hline

	\end{tabular}
	\end{center}
\end{table}

この原因は，相互情報量が「出現確率の影響を受ける」という特徴を持つためである．
この特徴は式(\ref{MI})を次式のように書き換えるとわかりやすい．
\begin{equation}
MI(w_a,w_b)=\log p(w_a|w_b) - \log p(w_a)
\end{equation}
$p(w_a|w_b)$は語$w_b$が出現するときに語$w_a$と語$w_b$が共起する条件付き確率を表す．
$p(w_a|w_b)$が等しい場合は，$p(w_a)$の出現確率が小さいほど
相互情報量は大きい値になる．この特徴自体は「共起する確率が同じなら，
出現確率の低い語と共起する方が関連性が強い」と考えられるので，問題がない．
しかし，検索エンジンにおいては語によって出現頻度に大きなばらつきがあり，
また全事象を表す$N$が非常に大きいために出現確率の違いによる影響が大きくなり過ぎてしまう．
例えば，「テレビ」のように出現確率の極端に大きい語と他の語の相互情報量が小さくなる．
表\ref{mutual}の「テレビ」の列に注目すると，いずれの語においても「テレビ」との相互情報量が
小さくなっていることが分かる．
実際に表\ref{singlehit}の語のヒット件数と表\ref{mutual}の各行との
相関係数（式\ref{correlation}）は$-0.35$となり，
相互情報量と語の出現確率にやや強い負の相関があることが分かる．
それに対し，表\ref{cooccur-list}の共起ヒット件数と
表\ref{mutual}の相互情報量のとの相関係数は$0.06$となり，
ほとんど相関がないことが分かる．
\begin{equation}
\label{correlation}
r=\frac{\sum_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}
{\sqrt{\sum_{i=1}^n{(x_i-\bar{x})^2}}{\sqrt{\sum_{i=1}^n{(x_i-\bar{x})^2}}}}
\left(\bar{x} :x_iの平均値\right)
\end{equation}


このように，従来用いられてきた相互情報量は語の出現確率に影響を受けるため，
関連度を測る際に各語の出現確率に数千倍，数万倍といった開きがある場合，
値の信頼性は低くなるという問題がある．
これは，Jaccard係数やdice係数など他の類似度の指標についても当てはまる．







\subsection{$\chi^2$値を用いた関連度の指標}

本論文では，$\chi^2$値を使った関連度の指標を用いる．
$\chi^2$値は，あるデータ集合内での統計的な偏りを表す指標であり，機械翻訳
やコロケーション処理など，
多くの手法で用いられている．
語の関連度としてはCurranらが用いている\cite{Curran02-2}．


$\chi^2$値を関連度に用いるのは，語の出現頻度のばらつきによる
影響を排除するためである．
相互情報量やJaccard係数を関連度に用いる場合の問題点は，語の出現確率に大きな影響を受ける点である．
この問題の解決策として，出現確率を適切に正規化するというアプローチが考えられる．
$\chi^2$値では，語群を構成する語の出現頻度を正規化要素とし，
値の正規化を行ったうえで，共起の偏りを算出するので，出現確率のばらつきによる影響を抑えることができる\cite{Yang97}．
このため，値のばらつきが大きい検索エンジンのヒット件数を用いて関連度を算出する場合，
$\chi^2$値を計算指標として用いることが適切であると考えられる．


対象とする語群の中で，共起の偏りを統計的に調べるために，
1つ1つの語について，語群内の他の語との共起頻度を標本値とし，
「$w_i,w_j\in G$が共起する確率は，語$w_i$と語群$G$内の語が共起する確率と等
しい」という帰無仮説をおいて検定を行う．
語$w_i$と語$w_j$の実際の共起頻度を$n(w_i,w_j)$，
語$w_i$と語群Gの語との共起頻度の和を$\displaystyle S_{w_i}=\sum_{k} n(w_i,w_k)$，
全ての共起頻度の和を$\displaystyle S_G=\sum_{w_i \in G} S_{w_i}$とするとき，
語$w_i$と語$w_j$に関する$\chi^2$値は次式で表される．
\begin{align}
 \chi^2(w_i,w_j) & = \frac{n(w_i,w_j) - E(w_i,w_j)}{E(w_i,w_j)}  \nonumber \\
 E(w_i,w_j) & = S_{w_i} \times \frac{S_{w_j}}{S_G} 
\label{chi}
\end{align}
$E(w_i,w_j)$は語$w_i,w_j$の
共起頻度の期待値を表している．
例えば，語$w_i$を「プリンタ」，語$w_j$を「インターレーザー」とすると，
$n(w_i,w_j)$ は $273$，$S_{w_i}=20601273$，${S_{w_j}}/{S_G}=839/166552478$となる．
表\ref{chilist}は，表\ref{cooccur-list}から計算された$\chi^2$値行列である．
表\ref{chilist}では，「プリンタ」は「印刷」や「インク」と偏って共起している．
また，「インターレーザー」は「プリンタ」との共起が，「Aquos」は「Sharp」との共起が強いなど，良好な結果となっている．


また，表\ref{chilist2}のような，「プリンタ」「液晶」との関連が低いと考えられる4語と「プリンタ」「液晶」の2語
で構成される計6語の語群を与えた場合を考える．
この語群では，表\ref{singlehit}の語群と違い，「プリンタ」と「液晶」の関連性が強いと考えられる．
「プリンタ」の行に注目すると，確かに「プリンタ」と「液晶」の$\chi^2$値が大きくなっており，
語群に基づいた適切な結果が得られている．


\begin{table}[tb]
		\caption{$\chi^2$ 行列}
	\label{chilist}
	\begin{tabular}{c|cccccccc}
	
 語/語 & プリンタ  & 印刷  
	& \hspace{-1.3zw} \scalebox{0.8}[1]{インターレーザー} \hspace{-1.3zw} 
	& インク  & 液晶  & テレビ  & Aquos  & Sharp \\ \hline
プリンタ  & 0.000  & 416649  & 275.5  & 2579092  & 113.8  & 0.000  & 0.000  & 0.000 \\ 
印刷  & 416649  & 0.000  & 9.925  & 801848  & 0.000  & 1840173  & 0.000  & 0.000 \\ 
    \hspace{-1.3zw} \scalebox{0.8}[1]{インターレーザー} \hspace{-0.3zw} 
	& 275.5  & 9.925  & 0.000  & 5.548  & 0.000  & 0.000  & 0.000  & 0.000 \\ 
インク  & 2579092  & 801848  & 5.548  & 0.000  & 0.000  & 3846  & 0.000  & 0.000 \\ 
液晶  & 113.8  & 0.000  & 0.000  & 0.000  & 0.000  & 6858012  & 0.000  & 1317796 \\ 
テレビ  & 0.000  & 1840173  & 0.000  & 3846  & 6858012  & 0.000  & 0.000  & 0.000 \\ 
Aquos  & 0.000  & 0.000  & 0.000  & 0.000  & 0.000  & 0.000  & 0.000  & 7449430 \\ 
Sharp  & 0.000  & 0.000  & 0.000  & 0.000  & 1317796  & 0.000  & 7449430  & 0.000 \\ \hline 

	\end{tabular}
\end{table}

\begin{table}[tb]
	\begin{center}
		\caption{$\chi^2$ 行列-2}
	\label{chilist2}
	\begin{tabular}{c|cccccc}
	 語/語 & プリンタ & 小説 & 液晶 & 紅茶 & バイオリン & 化粧品 \\ \hline
	 プリンタ & 0.000 & 0.000 & 2402760 & 0.000 & 0.000 & 0.000 \\ 
	 小説 & 0.000 & 0.000 & 0.000 & 277513 & 712208 & 19024 \\ 
	 液晶 & 2402760 & 0.000 & 0.000 & 0.000 & 0.000 & 116983 \\ 
	 紅茶 & 0.000 & 277513 & 0.000 & 0.000 & 11149 & 597032 \\ 
	 バイオリン & 0.000 & 712208 & 0.000 & 11149 & 0.000 & 0.000  \\ 
	 化粧品 & 0.000 & 19024 & 116983 & 597032 & 0.000 & 0.000 \\ \hline
	\end{tabular}
	\end{center}
\end{table}


\section{関連度を用いたネットワークに基づくクラスタリング}


従来は，確率分布の類似度に基づいた分布クラスタリングの方法を用いて，
関連語をクラスタに分けることが多かった．
本研究では，語の関連度からネットワークを構築し，ネットワークに基づく新
しいクラスタリングの方法を適用する．
関連語ネットワーク上でNewman法によりクラスタリングを行い，
その結果，同じクラスタに分類されたもの同士を関連語として取り出す．
このクラスタリング法は，語の数が大規模になったときにでも適用でき，
対象によってはよいクラスタを生成するので近年注目を集めている．

\subsection{関連語ネットワークの構築}

まず，語の関連性を用いて，語のネットワークを構築する．
ノードが語，エッジが強い関連を表す．
本論文では，これを関連語ネットワークと呼ぶ．

関連語ネットワークは次のように構成される．

\begin{figure}[b]
\begin{center}
  \includegraphics[width=120mm,clip]{network.eps}
 \caption{関連語ネットワーク}
 \label{related-network}
\end{center}
\end{figure}


\begin{enumerate}
\item 語群$G$を与える．
\item 次式により2語$w_i， w_j \in G$の関連度$\chi^2_{w_i, w_j}$を計算する．
\begin{align}
\label{chi2}
 \chi^2_{w_i,w_j} & = \frac{n(w_i,w_j) - E(w_i,w_j)}{E(w_i,w_j)}   \nonumber \\
 E(w_i,w_j) & = S_{w_i} \times \frac{S_{w_j}}{S_G} \\
 S_{w_i} & = \sum_{k} n(w_i,w_k) \nonumber \\
 S_G & = \sum_{w_i \in G} S_{w_i} \nonumber 
\end{align}
\item 各語$w_i \in G$をノードとして配置する．
\item $\chi^2_{w_i,w_j} > 0$のとき，ノード$w_i$，$w_j$間にエッジを張る．
\end{enumerate}


例を図\ref{related-network}に示す．
これは，Webから獲得したコーパス中に高頻度に出現する
計90語をこのネットワークの構成語として用い，
ヒット件数を得る検索エンジンとしてGoogleを用いた関連語ネットワークである．
この関連語ネットワーク上では，関連の強い語同士が近く配置されている．
例えば，図\ref{related-network}の左下には「疾患」「患者」などの医学関連の語が密集している．
また，上部では「アプリケーション」「ファイル」などのコンピュータ関連の語が密集している．
このように関連語ネットワーク上では，関連の強い語同士が密集して存在している．


\subsection{ネットワークに基づくクラスタリング}


従来のシソーラス構築における語のクラスタリングには
確率分布を用いた分布クラスタリング手法が一般的に用いられている．
\cite{Pereira93,Dhillon02}．
また情報検索の分野では，語を属性とする高次元のベクトルを用いた語のクラスタリング手法も多く，
LSAやrandom projectionといった次元を圧縮する手法も有効である\cite{Deerwester90,papadim98}．

一方で，近年ではデータをネットワークとして表した上で，それを分析する
手法が提案され，着目を集めており，語の関係性の分析にも用いられている\cite{Widdows02,motter02,Palla05}．
SigmanはWordNetがネットワーク構造としての性質を持っていることを示し，
WordNetにネットワーク分析の手法を適用できることを示している\cite{sigman02}．

\begin{table}[b]
	\begin{center}
		\caption{階層的クラスタリングで用いられる距離関数$D(c_i,c_j)$}
	\label{Hierarchical}
	\begin{tabular}{|c|c|c|c|}
	\hline
	手法 & 最大距離法 & 最小距離法 & 群平均法  \\ \hline
	$D(c_i,c_j)$ & $\displaystyle \max_{w_k \in c_i, w_l \in c_j} Sim(w_k,w_l)$ & $\displaystyle \min_{w_k \in c_i, w_l \in c_j} Sim(w_k,w_l)$ & 
	$\frac{1}{n_i n_j} \displaystyle \sum_{w_k \in c_i} \sum_{w_l \in c_j} Sim(w_k,w_l)$ \\ \hline
	\end{tabular}
	\end{center}
\end{table}

ネットワークのクラスタリングには，従来，
表\ref{Hierarchical}のように距離関数$D(c_i,c_j)$を定義し（$n_i$はクラスタ$c_i$に含まれる語の数，$Sim(w_k,w_l)$は$語w_k,w_l$の類似度を表す），
距離の近い順に各クラスタをマージしていく階層的クラスタリング手法や，
EMアルゴリズム，NaiveBayesといった機械学習の手法を用いたクラスタリング手法が一般的に用いられてきた．
しかし，ここ数年で新たなクラスタリング手法がいくつも提案されている．
代表例としては，betweennessクラスタリングがあげられる．betweennessクラスタリングは，グラフ\footnote{ネットワークは，エッジに重みや長さなどの数値が付加されているのに対し，
グラフはエッジに数値の付加されていない，接続関係だけを表すものである．}のbetweennessというエッジの媒介性を表
す指標（あるエッジが他のエッジの最短パスにどの程度の割合で含まれているか）
に注目し，できるだけ部分グラフをつなぐようなbetweennessの高いエッジを削除し
ていくことにより，密度の濃いサブグラフを同定する手法である\cite{Newman02}．


これらの手法は高次元のベクトルに対しても有効であり，以前の手法と比べて
高い精度で現実のクラスタ構造を再現することができる．
その反面，時間計算量が大きく，大規模なネットワークに適用することは難しい．
例えば，ネットワークのノード数を$n$，エッジ数を$m$とするとき，
betweennessクラスタリングの時間計算量は$O(n^3)$または$O(m^2n)$であり，ノード数が多いネットワーク上で
betweennessクラスタリングを行うことは困難である．
そこで，本研究では大規模なネットワークにも適用可能な
クラスタリング手法であるNewman法を用いる．


Newman法は，階層的クラスタリング手法の一つであるが，クラスタリングを評価関数$Q$の最大値導出問題に置き換えた手法である\cite{Newman04}．
評価関数$Q$とは，各クラスタの結合度を表す関数であり，$Q$が大きいほど
各クラスタ内の結合が強いことを表している．
Newman法では，$Q$の高い状態がより適切にクラスタリングされた状態であると定義している．
そして，$Q$の最大値を求めることで，
そのネットワークに最適なクラスタリング結果を得ることを目標としている．


評価関数$Q$は次式で表される．
\begin{equation}
\label{newman}
Q=\frac{1}{2m}\left[ \left( \sum_{v,w} A_{vw}\delta(c_v,c_w)\right) - 
\left(\sum_{v,w} \frac{k_v k_w}{2m}\delta(c_v,c_w)\right) \right] 
\end{equation}

$k_v$は頂点vが持っているエッジの本数，$m$は全エッジ本数の合計，
$c_v$は頂点$v$が属しているクラスタを表
している．$\delta(c_v,c_w)$はクロネッカーの$\delta$である．
式(\ref{newman})の第1項において，$A_{vw}$は頂点$v,w$間のエッジの有無を表しており，
また頂点$v,w$が同じクラスタのときのみ，$\delta(c_v,c_w)=1$となる．
つまり，第1項は各クラスタ内に含まれるエッジの本数の合計を表している．
同様に第2項においては，$\frac{k_v k_w}{2m}$は頂点$v,w$間にエッジが引かれる確率を表しているため，
第2項は，各クラスタ内に含まれるエッジの本数の合計の期待値を表している．

すなわち，評価関数$Q$とは，クラスター内に存在するエッジの本数の合計が期待値からどの程度ずれているかを相対的に表した値である．
クラスター内のエッジ本数の和が期待値と同じなら$Q=0$，
それより強いクラスターなら$Q>0$であり，弱いクラスターなら$Q<0$となる．
$Q$が最大であるとき，各クラスター内での結合度が最大であるので，
ネットワーク全体として最も良くクラスタリングされた状態であると考えられる．


しかし$Q$の最大値を求める場合，エッジ数$m$，ノード数$n$のとき，計算量が
$O(n^3)$もしくは$O(m^2n)$となり，大きくなってしまう．
そこでNewman法ではGreedyアルゴリズムを用いて
$Q$の値が極大値をとるようにクラスタリングを行う．
Greedyアルゴリズムなので，「$Q$の変化量$\Delta Q$が最大になるようにクラ
スタ，もしくはノードをマージする」という手順を繰り返していく．
そして「$\Delta Qの最大値<0$」となった時点でクラスタリングを終了とする．
このようにして$Q$の極大値を求めている．
この際，常に「$\Delta Q$が最大になるような2つのクラスタを選んでマージ」
するため，クラスタがマージされていく順序は一意であり，
初期条件によってクラスタリングの結果は変化しない．
また，クラスタ数を任意に制御したい場合は，終了条件を
$\Delta Q < 0$ではなくクラスタ数にすることも可能である．

Newman法とbetweennessクラスタリングを比較すると，NewmanらによりNewman法は
betweennessクラスタリングとほぼ同じ精度のクラスタリング結果が得られることが示されている．
また，Newman法の時間計算量は$O((m+n)n)$もしくは$O(n^2)$であり，
時間計算量が$O(m^2n)$あるいは$O(n^3)$であるbetweennessクラスタリングと比べ，
計算量が少なく，高速な手法となっている．
そのため，Newman法はノード数やエッジ数が大きい大規模ネットワークに適用可能である．

\subsection{Newman法による関連語の獲得}

語群$G$を用いてシソーラスを構築する場合，Newman法を用いて関連語を同定する
手順は次のようになる．

\begin{enumerate}
\item 検索エンジンのヒット件数と$\chi^2$値を用いて語群$G$の語の関連度を算出する．
\item 関連度をもとに語群$G$を構成語とする関連語ネットワークを構築する．
\item 1つの語を1つのクラスタとする．
\item ある2つのクラスタが1つのクラスタになったと仮定して，$Q$の変化量
      $\Delta Q$（式\ref{deltaq}）を計算する．

\item (4)を全てのクラスタの組み合わせについて行う．
\item $\Delta Q$が最大となるような2つのクラスタをマージし，1つのクラスタとする．ただし，
      最大の$\Delta Q<0$なら(8)へ．
\item マージしたクラスタの$e_{ij},a_i$を再計算し，(4)に戻る．
\item 同じクラスタに属している語を関連語とみなす．
\end{enumerate}
\begin{align}
\label{deltaq}
 \Delta Q_{ij} & = 2(e_{ij}-a_i a_j) \nonumber \\
 e_{ij} & = クラスタi，j間のエッジの本数（割合）  \\
 a_i & = \sum_{i} e_{ii} \nonumber 
\end{align}


\section{評価} 


\subsection{評価実験の概要と正解セットの作成}

シソーラスを評価する手法として，
WordNetやEDRなど人手で構築された既存のシソーラスと比
較する方法\cite{Jarmasz03,Curran02}，
綿密に作られたアンケートや語の分類タスクを人が行い，
その結果と比較することでシソーラスの適切さを評価する方法\cite{Croft99,Hodge02}がある．
前者の手法はWordNetに出現する語しか評価できないため語の範囲が限ら
れてしまい，後者はコストがかかるのが問題である．


本研究では，提案手法で構築されたシソーラスと，2種類のシソーラスを比較することで，提案手法の評価を行う．
1つ目はWebより収集したコーパスから作成したシソーラスであり，
これを関連語の正解セット作成用のデータとして用いることで提案手法と従来のコーパスを用いた手法との比較を行う．
2つ目は既存のシソーラスであり，これから作成した関連語の正解セットを用いて，
人手によって構築されたシソーラスと提案手法との比較を行う．

また，1つ目の正解セットにはWebに特徴的な語が多く含まれるのに対し，
2つ目の正解セットでは，既存のシソーラスに含まれるような，いわゆる汎用
的な語が多く含まれる．そのため，それぞれの正解セットを評価実験に用いることで，
Webに特徴的な語に対する提案手法の有効性，汎用的な語に対する提案手法の
有効性を検証することにもなる．

\subsubsection{OpenDirectoryを用いた正解セットの作成}
シソーラスを作成するコーパスとしてOpenDirectory\footnote{http://dmoz.org/World/Japanese/}を用い，あらかじめ各カテゴリに特徴的な語を抽出することで，
正解となるシソーラスを模擬的に作成する．
OpenDirectoryは，ボランティア方式で運営される世界最大のウェブディレクトリであり，
各カテゴリは，担当のエディタによって管理されている．Webディレクトリの中では，カテゴリ分類の信頼性が高いもののひとつである．
各カテゴリに特徴的に出現する語は互いに関連しているという仮定のもとで，
提案手法および比較手法による語の関連性の適切さを評価する．


OpenDirectoryの14個のカテゴリの中から，「アート」，「スポーツ」，「コンピュータ」，「ゲーム」，「社会」，
「家族」，「科学」，「健康」，「レクリエーション」の9つのカテゴリを用い\linebreak
た\footnote{なお，「ニュース」，
    「キッズ＆ティーンズ」，「ビジネス」，「オンラインショップ」，
「各種資料」は，他のカテゴリとの重複が大きいため除いた．}．
各カテゴリ内に含まれるWebページを用い，次のようにカテゴリに特徴的な語を抽出する．


\begin{enumerate}
\item 各カテゴリ$C_i(i=1...9)$ごとに登録順に1000ページの文書を取得する．
\item 全ての文書に形態素解析\footnote{茶筌．http://chasen.aist-nara.ac.jp/.}を行う．そして連接する名詞5-gramまでを単語として取り出す\cite{Manning99}．
\item カテゴリ$C_i$内で，単語$w_a$が含まれる文書の数を$f^i_{w_a}$とする．
また，全てのカテゴリで語$w_a$が含まれる文書数を$f^{all}_{w_a}$とする．
\item カテゴリ$C_i$における語$w_a$の重みを次のように計算する．
\begin{equation}
score^i_{w_a} = f^i_{w_a} \times \log (N/f^{all}_{w_a})
\label{tfidf}
\end{equation}
ただし，$N$は全文書数である．
\item カテゴリ$C_i$ごとにscoreの高い語$w_a$を取り出し，それらをそのカテゴリに特徴的な語群$R_{C_i}$とする．
すなわち，$R_{C_i} = \{w_k | rank_i(w_k) \leq 10\}$である（$rank_i(w_k)は，カテゴリC_i内での語w_kのscoreの順位を表す$）．
また，$A=\{w| w \in R_{C_i}, i=1...9\}$とする．
\end{enumerate}
ここでは，各カテゴリごとに特徴的に現れる語を，tfidfの考え方を用いて重み付けしている．
また上記説明の(1)において「登録順に」とあるが，これはOpenDirectoryのサイ
トから文書データを収集する際に，
データが得られる順番を意味している．この順番は，文書の内容に関係なく無作為に並んでおり，
特定のルールはないと考えられるため，ランダムな順番と考えても問題ないと言える．




\begin{table}[b]
\caption{OpenDirectoryから取り出した関連語群}
\label{wordlist}
\begin{center}
\begin{tabular}{l l}
\hline
カテゴリー & 関連語群 \\ \hline
アート & 画廊，作品，劇場，サックス，短歌，ライブ，ギター，披露，バレエ，個展 \\
コンピュータ & 掲示板，ソースコード，無料レンタル，アクセス数，文字コード，初期値，拡張子 \\
科学 & 情報処理，実証，方法論，社会科学，研究対象，格差，研究員，専門，専攻，討論
 \\ \hline
\end{tabular}
\end{center}
\end{table}


得られた語の一部を表\ref{wordlist}に示す．
例えば「アート」カテゴリから取り出された語に注目すれば，
「画廊」「作品」「個展」は絵画関連の語，「サックス」「ライブ」「ギター」は音楽関連の語，
「バレエ」「披露」「劇場」はパフォーミングアート関連の語，「短歌」は文芸関連の語となっており，
いずれも「アート」に関連した語が取り出されている．
こうして得られたカテゴリごとの特徴的な語を用いて，
\begin{itemize}
\item ある2語が同一カテゴリ内に含まれれば，関連している
\item ある2語が異なるカテゴリであれば，関連していない
\end{itemize}
と見なす．

ここでの評価法は，カテゴリごとの特徴語の抽出に基づいている．
各カテゴリに特徴的に現れる語を重み付けする方法は，\cite{Nagao76}や
\cite{Xu02}で用いられている．後者では，
各カテゴリに特徴的な語をtfidfで重み付けし，tfidf値の高い語を
カテゴリに特徴的な語として抽出している．
さらに\cite{Chang05}では，OpenDirectoryのカテゴリ分類を用いて各カテゴリに特徴的な語を取得し，
その結果，人手による評価で平均65\%，最大で81\%の正解率を得ている．
もちろん，ここでの関連語の正解セットは完全ではなく，異なるカテゴリに含まれていても関連している場合もあるかもしれないし，同一カテゴリ内であっても，
その関連の度合いは程度の差が大きいかもしれない．
しかし，本研究では，このデータを手法の比較を行うための目安として用いており，比較手法の優劣を示すには十分であると考えている．


\begin{figure}[b]
\begin{center}
  \includegraphics[width=8cm,clip]{evaluate.eps}
\end{center}
 \caption{評価実験の概略図}
 \label{evaluate}
\end{figure}


図\ref{evaluate}に全体の概要を図示する．OpenDirectoryから獲得したカテゴ
リ分類されたコーパスを用いて関連語の正解セットを作成する．
その正解セットの語を用いて提案手法および比較手法によって
関連語を出力する．その際，比較手法はコーパス内の共起情報を用いて
関連度の算出を行う．そして出力結果と正解セットを比較し，手法の評価を行う．

図\ref{evaluate}に示すとおり，本評価実験では
正解セット作成用コーパス，比較手法で用いる関連度学習用コーパス
の2種類のコーパスが必要となる．
そこで，全部で各カテゴリから5000ページずつ計4万5千ページの文書をコーパスとして用意し，
$1/5$を正解セット作成用に，$4/5$を関連度の学習用に用いて5分割交差検定を行った
\footnote{ただし，関連度の学習を行う際はコーパスの持つカテゴリ分類は無視し，flatなコーパスとして扱った．}．
正解セット作成用のコーパスを変えたそれぞれの正解セットを$Ao_i(i=1,2,3,4,5)$とする．

関連度の評価は，適合率，再現率，Inverse Rank Scoreによって測る．
Inverse Rank Scoreとは正解とマッチした語の順位の逆数の合計値であり，
正解となる語が上位にランクされる程大きい値となる．
この値を用いることで，順位を考慮した比較を行うことができる．

\begin{table}[t]
\caption{評価実験の例（ヴァイオリン）}
\label{ex-experiment}
\begin{center}
\begin{tabular}{l|c|c|c|c}
	& 関連語   & 適合率 & 再現率 & InvR \\ \hline
正解セット & ビオラ，チェロ，笛，ギター & &  & \\ \hline
手法1 & 1位:ビオラ  2位:チェロ 3位:ビール 4位:ピック & 0.5 & 0.5 & 1.50 \\ \hline
手法2 & 1位:ピック 2位:ビール  3位:ビオラ 4位:チェロ 5位:ギター & 0.6 &
 0.75 & 0.78 \\ \hline
\end{tabular}
\end{center}
\end{table}

簡単な算出例を表\ref{ex-experiment}に示す．この場合，手法1による出力は
4語中2語が正解であるので$適合率=\frac{2}{4}=0.50$，正解セット4語のうち2語が
手法1により出力に含まれているので，$再現率=\frac{2}{4}=0.50$となる．
同様に手法2では$適合率=\frac{3}{5}=0.60$，$再現率=\frac{3}{4}=0.75$とな
り，手法2の方が優位となる．しかし，正解の語が上位にランクされている手法1の方が
手法としての実用性が高い，とも考えられる．このような場合に各手法の
Inverse Rank Scoreを求めると手法1では，$\frac{1}{1}+\frac{1}{2}=1.50$，
手法2では$\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=0.78$となり，
手法1の方が優位となる．

このように適合率，再現率に加え，Inverse Rank Scoreを用いることで，
順位を加味した評価を行うことができる．\cite{Widdows02,Curran02}．



\subsubsection{既存シソーラスを用いた正解セットの作成}
本論文では，Curranら\cite{Curran02}の手法を元にして，
提案手法と既存のシソーラスを比較を行う．そのために，正解セット作成用シソーラ
スと比較用シソーラス，2種類のシソーラスを用意する．
まず，正解セット作成用シソーラスから関連語を取り出し，正解セットを作成する．
この正解セットの語群に対して提案手法と比較用シソーラスを適用して関連語の
分類を行う．その結果，どの程度正しく語群が関連語群に分類されるかによって
提案手法と既存シソーラスとの比較を行う．
本論文では，Curranらが用いたRoget's Thesaurusの最新版である
Roget's Millenium Thesaurus~\cite{RogetMillenium}を正解セット作成用のシソー
ラスとして用い，
WordNet及びMoby Thesaurus~\cite{MobyThesaurus}を比較用のシソーラスとして
用いる．

Roget's Millenium Thesaurusは見出語を持ち，その見出語がそれぞれ関連語
群を持つ，という2層構造をしたシソーラスである．
本実験においては，1つの見出語から取り出される関連語群をそのまま正解の関
連語群とした．ただし，比較用シソーラスに含まれない語は除くものとする．
関連語の例は表\ref{WordNetExample}のようになる．
今回，見出語としてはTOEIC最頻出英単語リスト
    \footnote{http://www.linkage-club.co.jp/ExamInfo\&Data/toeic.htm}に含まれ
る名詞の計220語を用いる．
これらの見出語から無作為に10語選び，その10語からそれぞれ関連語群を取り出
し，1組の関連語正解セットとする．
本実験では，計10組の正解セット$Aw_i(i=1,2,...,10)$を作成した．


また比較用のシソーラスを用いた関連語群の分類では，算出した関連度に基づい
て行うのではなく，各2語が比較用シソーラスで関連語とされているか，いないかの
2値的な判定によって行うものとする\footnote{WordNetを用いて2語の関連度を算出する方法もあるが，
予備実験により関連語の分類には適さないことが判明したので，
本論文では採用しなかった．}．
この際，どの2語を関連語とみなすかは，シソーラスの構造によって違う方法を
用いた．
Roget's Thesaurusと同様に見出語と関連語群の2層構造を持つ
Moby Thesaurusにおいては，見出語とその関連語群同士，
及び同じ見出語を持つ語同士を関連語とみなす．
木構造を持つWordNetにおいては，見出語とHyponyms（下位語），
見出語とHypernyms（上位語）
及び見出語とCoordinate Terms（共通の上位語を持つ語）同士を関連語とみなす．

関連度の評価指標としては，OpenDirectoryを用いる場合と同様に，
適合率とInverse Rank Scoreを用いる．



\begin{table}[t]
\caption{正解用シソーラスから取り出した関連語群}
\label{WordNetExample}
\begin{center}
\begin{tabular}{l l}
\hline
見出語 & 関連語群 \\ \hline
access & admission, contact, door, entrance, entree, \\
	& ingress, introduction, open door, road, route,  \\
election & acclamation, appointment, by-election, referendum \\
		 & polls, primary , selection, voting \\
pollution & abuse, contamination, corruption, decomposition, uncleanness\\
	 & dirtying, impurity, infection, rottenness, spoliation\\ 
agriculture & agronomy, culture, horticulture, tillage, husbandry \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{関連度の指標の評価}


関連度の指標に関する評価を行う．
提案手法では，関連度の計算に$\chi^2$値を用いているが，この有効性を示すた
め，相互情報量，Jaccard係数を用いた関連度と比較する．
検索エンジンを利用する際，日本語のみを扱うOpenDirectoryによる正解セットでは，
検索時のオプションとして「日本語のページを検索」を選択した値を用い，
英語のみを扱う既存のシソーラスによる正解セットでは検索時のオプションとし
て「ウェブ全体から検索」を選択した値を用いる\footnote{Googleではオプショ
ンによって検索するページの対象範囲をコントロールできる．}．

また，コーパスを用いて学習する手法との比較も行う．コーパスを用いる手法で
は，tfidf値を要素とする単語ベクトルを用い，計算指標としてはcosineを用いた．実験の手順を以下に示す．

\begin{enumerate}
\item 正解セット$A_i$に含まれる全ての語について，各指標ごとに2語の関連度
      を計算する（比較用シソーラスを用いる際はこの手順は省略）．
\item 各指標ごとに語$w_i$と関連度の高い上位9語を$A_i$から選び，それを語
      $w$の関連語群$G_{w}$とする（比較用のシソーラスを用いる場合は，
      比較用シソーラスにおいて語$w_i$の関連語とされる語を全て取り出し，
      $G_{w}$とする）．$G_{w}$と正解セットを比較し，適合率を計算する．
\item (2)を語$w_i \in A_i$全てについて行い，指標ごとに適合率の平均値を算出する．
\item (1)から(3)を正解セット$A_i(i=1〜n)$について行う．
\end{enumerate}

OpenDirectoryから作成した正解セットの適合率の平均値を表\ref{result-word}に，
Inverse Rank Scoreの平均値を表\ref{result-word-inv}に示す．

\begin{table}[b]
	\begin{center}
	 \caption{OpenDirectoryを用いた正解セットでの適合率}
	 \label{result-word}
	 \begin{tabular}{c|c|c|c|c}
	  正解セット/指標 & cosine & 相互情報量 & Jaccard係数 & $\chi^2$値 \\ \hline
	セット$Ao_1$ & 0.557 & 0.447 & 0.424 & 0.567 \\ 
	セット$Ao_2$ & 0.513 & 0.406 & 0.389 & 0.493 \\ 
	セット$Ao_3$ & 0.519 & 0.396 & 0.376 & 0.539 \\ 
	セット$Ao_4$ & 0.561 & 0.404 & 0.417 & 0.569 \\ 
	セット$Ao_5$ & 0.529 & 0.421 & 0.404 & 0.519 \\ \hline
	  平均 & 0.535 & 0.415 & 0.402 & 0.538 \\ 
	 \end{tabular}
    \vspace{\baselineskip}

	 \caption{OpenDirectoryを用いた正解セットでのInverse Rank}
	 \label{result-word-inv}
	 \begin{tabular}{c|c|c|c|c}
	  正解セット/指標 & cosine & 相互情報量 & Jaccard係数 & $\chi^2$値 \\ \hline
	セット$Ao_1$ & 2.42 & 1.58 & 1.63 & 2.36 \\ 
	セット$Ao_2$ & 2.41 & 1.90 & 1.43 & 2.75 \\ 
	セット$Ao_3$ & 1.97 & 1.09 & 1.02 & 1.64 \\ 
	セット$Ao_4$ & 2.29 & 2.04 & 1.84 & 2.52 \\ 
	セット$Ao_5$ & 1.70 & 2.17 & 1.83 & 2.20 \\ \hline
	  平均 & 2.16  & 1.76 & 1.55 & 2.29 \\ 
	 \end{tabular}
	\end{center}
\end{table}
まず，検索エンジンを用いた手法同士で比較すると，
どの正解セットにおいても$\chi^2$値が
他の2つの計算指標よりもよい適合率，Inverse Rank Scoreを示している．
これより，$\chi^2$値が検索エンジンを用いる手法の関連度の指標として
有効であることが分かる．
また，コーパスを用いて学習した手法であるcosineと検索エンジンを用いた手法を比較すると
Jaccard係数，相互情報量はcosineよりも低い適合率，Inverse Rank Scoreである．
cosineと$\chi^2$値を比較すると正解セットによって2つの評価指標の優劣が変化している．
しかし，平均ではほとんど
差がないことから，$\chi^2$値とcosineはほぼ同じ適合率であると考えられる．
ただし，コーパスから学習する手法ではコーパス中に出現する語しか扱えないという欠点を持つのに対し，
検索エンジンを用いる手法ではWeb上に出現するほとんどの語を扱うことができる．
そのため同じ適合率ならば，$\chi^2$値を計算指標として検索エンジンを用いる手法の方が優れていると言える．

また，表\ref{result-word}, \ref{result-word-inv}において，
5つの正解セットにおける標準偏差（式\ref{hensa}）を求める．

\begin{equation}
\label{hensa}
\sigma^2=\frac{1}{n} \sum_{i=1}^{n}\left(x_i - \bar{x}\right) 
\left(\bar{x} :x_iの平均値\right)
\end{equation}

すると適合率の標準偏差は0.014，
Inverse Rank Scoreの標準偏差は0.12であり，いずれも
標準偏差は10\%以内に収まっている．
このことから，正解セットによる
ばらつきによる影響はあまり大きくないと考えられる．


次にRoget's Thesaurusから作成した正解セットを用いた既存シソーラスと提
案手法の比較実験の結果を表\ref{result-wordnet}と
    \ref{result-wordnet-inv}に示す．
ただし，比較用シソーラスにおいては，全ての関連語が等価に
扱われており順位が存在しないため，Inverse Rank Scoreの算出は省略する．

\begin{table}[b]
	\begin{center}
	 \caption{既存シソーラスを用いた正解セットでの適合率}
	 \label{result-wordnet}
	 \begin{tabular}{c|c|c|c|c}
	  正解セット/指標 & シソーラス & 相互情報量 & Jaccard係数 & $\chi^2$値 \\ \hline
	  セット$Aw_1$ & 0.385 & 0.324 & 0.374 & 0.405 \\
	  セット$Aw_2$ & 0.375 & 0.322 & 0.311 & 0.353 \\
	  セット$Aw_3$ & 0.342 & 0.365 & 0.402 & 0.411 \\
	  セット$Aw_4$ & 0.370 & 0.291 & 0.295 & 0.320 \\
	  セット$Aw_5$ & 0.438 & 0.459 & 0.487 & 0.515 \\
	  セット$Aw_6$ & 0.339 & 0.390 & 0.369 & 0.374 \\
	  セット$Aw_7$ & 0.391 & 0.287 & 0.335 & 0.345 \\
	  セット$Aw_8$ & 0.290 & 0.337 & 0.330 & 0.339 \\
	  セット$Aw_9$ & 0.468 & 0.295 & 0.279 & 0.316 \\
	  セット$Aw_{10}$ & 0.444 & 0.375 & 0.368 & 0.390 \\ \hline
	  平均  & 0.392 & 0.345 & 0.349 & 0.369 \\
	 \end{tabular}
    \vspace{\baselineskip}

	 \caption{既存シソーラスを用いた正解セットでのInverse Rank}
	 \label{result-wordnet-inv}
	 \begin{tabular}{c|c|c|c}
	  正解セット/指標 & 相互情報量 & Jaccard係数 & $\chi^2$値 \\
	  \hline
	  セット$Aw_1$ & 1.260 & 1.277 & 1.441 \\
	  セット$Aw_2$ & 1.145 & 1.263 & 1.290 \\
	  セット$Aw_3$ & 1.329 & 1.390 & 1.477 \\
	  セット$Aw_4$ & 1.184 & 1.006 & 1.144 \\
	  セット$Aw_5$ & 1.526 & 1.453 & 1.572 \\
	  セット$Aw_6$ & 1.498 & 1.273 & 1.241 \\
	  セット$Aw_7$ & 1.250 & 1.183 & 1.255 \\
	  セット$Aw_8$ & 1.337 & 1.354 & 1.432 \\
	  セット$Aw_9$ & 1.033 & 1.101 & 1.298 \\
	  セット$Aw_{10}$ & 1.320 & 1.313 & 1.301 \\ \hline
	  平均  & 1.288 & 1.255 & 1.3321 \\ 
	 \end{tabular}
	\end{center}
\end{table}



まず，Webを用いる手法同士を比較すると，OpenDirectoryを用いた正解セットと
比べて適合率の差が小さくなってはいるが，
シソーラスを用いた正解セットにおいても，
$\chi^2$値が他の計算指標よりよい数値を示している．
これより，提案手法の優位性は小さくなるものの，
Web上での出現頻度にばらつきの少ない汎用的な語に対しても，
提案手法が有効であることがわかる．


次に$\chi^2$値と既存のシソーラスを比較すると，
既存のシソーラスの精度の方が若干高い数値を出してはいるものの，
ほぼ同程度の精度・適合率が得られている．
これより，関連語を同定するタスクにおいて，
提案手法を用いることで既存シソーラスと同程度の効果が得られると言える．

以上より，提案手法を用いることで，検索エンジンを用いた既存手法やコーパスから学習する手法よりも
適切に関連度を算出することができていると考えられる．
ただし，コーパスから学習する手法ではcosine以外の計算指標を用いた手法があるため，
今後それらの指標とも比較する必要がある．


\subsection{クラスタリングの評価}

次に，クラスタリングの評価を行う．
提案手法ではNewton法を用いているが，
比較手法としては，群平均法を距離関数とする階層的クラスタリングを用いる．

クラスタリング手法の評価手法を以下に示す．

\begin{enumerate}
\item 正解セット$A_i$に含まれる全ての語について，2語の関連度を計算する．
\item 関連度をもとに関連語ネットワークを構築する．その際，ネットワークの密度が$0.3$
\footnote{$\chi^2$値による関連度を用いた関連語ネットワークの密度の平均値が約$0.3$であるため．}になるように
関連度の低いエッジを切る．ネットワークの密度とは，エッジ数を存在し得る最大のエッジ数（ノード数を$n$とすると$_n C_2$）で割ったものである\cite{Scott00}．
\item 提案手法及び比較手法により，クラスタリングを行う．今回は，使用したカテゴリ数が$9$であるため，
群平均法はクラスタ数が$9$になった時点でクラスタリングを終了とする．
また，本実験では条件を均一化するためにNewman法においても終了条件を
    $\Delta Q < 0$ではなくクラスタ数9とする．
\item 同一クラスタに属する2語は関連語，異なるクラスタに属する2語は非関連語とする．
この結果を正解セットと比較し，適合率・再現率・F値を求める．
\item (1)から(4)を正解セット$A_i(i=1〜n)$について行う．
\end{enumerate}



\begin{table}[b]
	\begin{center}
	 \caption{関連語抽出実験結果（上段：適合率 \ 中段：再現率
	\  下段：F値）　OpenDirectory使用}
	\label{result-cluster}
	 \begin{tabular}{c|c|cccc}
	  クラスタリング &  & cosine  & 相互情報量 & Jaccard係数 & $\chi^2$値 \\ \hline
	  群平均法 & 適合率  & 0.772 & 0.864 & 0.848 & 0.812 \\ 
	           & 再現率  & 0.209 & 0.222 & 0.208 & 0.221 \\     
	           & F値     & 0.328 & 0.353 & 0.333 & 0.347 \\ \hline
	  Newman法 & 適合率  & 0.815 & 0.792 & 0.797 & 0.738 \\ 
	           & 再現率  & 0.344 & 0.332 & 0.346 & 0.631 \\ 
	            & F値    & 0.483 & 0.465 & 0.482 & 0.680 \\ \hline
	 \end{tabular}
    \vspace{\baselineskip}

	 \caption{関連語抽出実験結果（上段：適合率 \ 中段：再現率
	\  下段：F値）　Roget's Thesaurus使用}
	\label{result-cluster-wordnet}
	 \begin{tabular}{c|c|ccc}
	  クラスタリング &  & 相互情報量 & Jaccard係数 & $\chi^2$値 \\ \hline 
	  群平均法 
	  & 適合率 & 0.887 & 0.861 & 0.852 \\ 
	  & 再現率 & 0.174 & 0.186 & 0.184 \\ 
	  & F値    & 0.291 & 0.305 & 0.302 \\ \hline
	  Newman法 
	  & 適合率 & 0.688 & 0.705 & 0.598 \\ 
	  & 再現率 & 0.329 & 0.302 & 0.411 \\ 
	  & F値    & 0.440 & 0.419 & 0.485 \\ \hline
	 \end{tabular}
	\end{center}
\end{table}

OpenDirectoryによる正解セットを用いた評価結果を表\ref{result-cluster}に，
Roget's Thesaurusによる正解セットを用いた評価結果を表\ref{result-cluster-wordnet}に示す．
示されている値はそれぞれ，5個のOpenDirectory正解セット$Ao_i(i=1〜5)$と
10個のRoget's Thesaurus正解セット$Aw_i(i=1〜10)$について
実験を行った結果の平均値である．
各計算指標の群平均法とNewman法の結果を比較すると，いずれも群平均法では適
合率が高く，再現率が低い．
クラスタリングの評価では一般的なことであるが，
これは1つのクラスタにほとんどの語が含まれ，残り8つのクラスタにそれぞれ1〜3語程度の語が含まれている状態と考えられる．
例えば，極端な例ではクラスタ内の語数が1であれば適合率が$\frac{1}{1}=1.0$
になる．そのため，
含まれている語数の少ないクラスタが多数できる手法の方が精度が上がりやすい．
しかし，再現率やF値で見ると，各クラスタに含まれる語数が均等に近くなるようなクラスタリング手法の評価が高くなる．


表\ref{result-cluster}, 表\ref{result-cluster-wordnet}から群平均法の代わりにNewman法を用いることで，
いずれの指標においてもF値が高くなっている．
このことから，提案手法を用いることでより適切に語がクラスタリングされていると言える．
ただし，群平均法がこの実験に適していない可能性も考えられるので，
今後他の手法との比較を行う必要がある．
Newman法を用いた場合の各指標を比較すると，表\ref{result-cluster}, 表\ref{result-cluster-wordnet}いずれにおいても，
$\chi^2$値が最も良いF値を示している．これより，語のクラスタリングを行う関連語ネットワークの構築には
$\chi^2$値による関連度を用いることが適切であると言える．

次に評価手法(3)におけるNewman法の終了条件を「クラスタ数9」とした場合と
「$\Delta Q<0 $」とした場合の評価実験結果を表\ref{final-condition}
に示す．
またその際の正解セットごとのクラスタ数のグラフを図\ref{cluster-num}に示
す．

\begin{table}[b]
	\begin{center}
	 \caption{終了条件による比較($\chi^2$)（上段：適合率 \ 中段：再現率
	\  下段：F値）}
	\label{final-condition}
	 \begin{tabular}{c|cc|cc}
	  & \multicolumn{2}{c|}{OpenDirectory} &
	  \multicolumn{2}{c}{WordNet} \\ \hline
	  & クラスタ数指定 & 自動終了($\Delta Q<0 $) & クラスタ数指定 &
	  自動終了($\Delta Q<0 $) \\ \hline 
	 
	  適合率 & 0.738 & 0.601 & 0.598 & 0.470 \\ 
	  再現率 & 0.631 & 0.911 & 0.411 & 0.591 \\ 
	  F値    & 0.680 & 0.722 & 0.485 & 0.520 \\ \hline
	 \end{tabular}
	\end{center}
\end{table}

表\ref{final-condition}より，終了条件を「$\Delta Q<0$」とした方が
「クラスタ数指定」とした場合よりも高いF値を示している．
しかし，その差は4ポイント程度であり，精度に大きな違いはないといえる．
これより，提案手法においては，条件としてクラスタ数を与えない場合でも，
与えた場合とほぼ同程度の精度で
関連語のクラスタリングを行うことができることがわかる．

\begin{figure}[b]
 \begin{center}
  \includegraphics[width=8cm,clip]{cluster.eps}
 \end{center}
 \caption{クラスタ数　横軸：正解セット　縦軸：クラスタ数}
  \label{cluster-num}
\end{figure}
\begin{table}[b]
\caption{クラスタリング結果の具体例}
\label{cluster-example}
\begin{center}
\begin{tabular}{l|c|c}
終了条件 & クラスタ名   &  \\ \hline
クラスタ数指定 & クラスタ$A_1$ & 情報処理，方法論，実証，ソースコード，文字コード，初期値 \\ 
\cline{2-3}
              & クラスタ$A_2$ & 無料レンタル，掲示板，アクセス数 \\ \hline
$\Delta Q<0$ & クラスタ$B$ & 情報処理，方法論，実証，ソースコード，文字コード \\ 
 & &  初期値，無料レンタル，掲示板，アクセス \\ \hline
\end{tabular}
\end{center}
\end{table}



ただし，今回の実験ではそれぞれの終了条件によって違う傾向を持っている．
「クラスタ数指定」では，$適合率 > 再現率$となっているが，
「$\Delta Q<0$」では，$適合率 < 再現率$となっている．
これは，終了条件によるクラスタ数の違いと
Webを用いて関連度を算出する際に必ずしも目的とする語の関連性が得られないた
めである，
これに関して，クラスタリング結果の具体例を
表\ref{cluster-example}に示す．
ここに用いられている語は表\ref{ex-experiment}に示されている語である．

本実験では，表\ref{ex-experiment}より，表\ref{cluster-example}の正解セッ
トでは「科学」及び「コンピュータ」という関連性によっ
てクラスタリングされることが想定されている．
しかし，実際には
「クラスタ数指定」のクラスタ$A_1$に含まれる語は，「情報科学」及び
「プログラミング」という共通の関連性を持っていると考えられる．
クラスタ$A_2$に含まれる語は「Web掲示板」という共通の関連性を持っていると
考えられる．
また「$\Delta Q<0$」では，クラスタ$A_1, A_2$が1つにマージされ
$クラスタB$を構成している．

このように提案手法では，正解セットで目的としている関連性とは
異なる関連性に基づいてクラスタリングされる場合が多い．
これはクラスタリング手法によるものではなく，主に算出された関連度による
ものである．
実際には，クラスタ$A_1$のように2つ以上のカテゴリの語で構成されるクラスタ
やクラスタ$A_2$のように1つのカテゴリの語の一部のみで構成されるクラスタな
ど，正解セットのカテゴリ分けとは異なるクラスタができてしまっている．
今回の実験においては，「クラスタ数指定」ではクラスタ$A_2$のような
クラスタが多かったために$適合率 > 再現率$となっている．
また，クラスタ数の少なかった「$\Delta Q <0$」では
クラスタ$B$のようなクラスタが多かったために$適合率 < 再現率$となっている．

以上より，提案手法の精度を高めていくためには，
目的にあわせた関連度を取得する手法と
より適切にクラスタ数を自動取得する手法が必要となってくる．



また，ネットワークのノード数とクラスタリングの実行時間の関係を図\ref{scalable}に示す\footnote{実行環境　CPU:Pentium4 3.0Ghz　メモリ:1GB}．
基準線は，$x$をノード数，$z$をエッジ数とするとき，式$y=1.8 \times 10^{-8} x(z+x)$のあらわす曲線である（$1.8 \times 10^{-8}は比例定数）$．
図\ref{scalable}で実測値と基準線を比較するとほぼ一致しており，確かにNewman法の計算量が
$O(n(m+n))$に比例している．そして，$n=4029$, $m=7146169$のとき実行時間は$532$秒であり，
$n,m$が大きい大規模ネットワークにも提案手法が適用可能であると考えられる．


\begin{figure}[t]
 \begin{center}
  \includegraphics[width=8cm,clip]{scale.eps}
 \end{center}
 \caption{ノード数と実行時間　横軸：ノード数　縦軸：実行時間（秒）}
  \label{scalable}
\end{figure}


以上の評価実験の結果より，提案手法について以下の3点を述べることができる．
\begin{itemize}
\item 既存手法よりも適切に関連語のクラスタリングを行うことができる
\item クラスタ数が未知の場合でも，クラスタ数が既知の場合と同程度の精度で
      関連語のクラスタリングを行うことができる
\item 大規模なネットワークにも適用可能である
\end{itemize}



\section{議論}
語の関連は，相対的なものである．候補となる語群によって，あるときは関連した語同士でも，他の場合には関連していないこともあり得る．
ある語群において全ての語同士の関連度が分かっている
とき，どの語とどの語を関連語と見なすかは，関連度によって規定される語の関
係性によると考えられる．語の関連性を図\ref{ex-clustering}のようなネット
ワーク図（ノード間の距離を（1/語の関連度）とおく）で可視化すると，図
\ref{ex-clustering}-aのような時
は部分集合A,B,Cそれぞれが，関連語の集まった関連語群であると言える．
同様に図\ref{ex-clustering}-bであれば，部分集合A,B,C,Dそれぞれが関連語群
であると言える．このように語のネットワー
ク上で周囲と比べて密度が高くなっている部分を抽出することで，各語の関連語
を同定することができる．

\begin{figure}[b]
 \begin{center}
  \includegraphics[width=8cm,clip]{ex-clustering.eps}
 \end{center}
 \caption{クラスタリングによる関連語の同定}
  \label{ex-clustering}
\end{figure}


Webは非常に多様性に富んだテキストから構成されている．
したがって，目的に合わせた語の関連性を得るには，
Webから適切な文書集合を切り出した上で，
その文書集合内での関連度を求めるという方法が考えられる．これには，
検索クエリーに特定の検索語(keyword spice)を加える方法が有効であろう\cite{Oyama04}．


本論文では，関連語ネットワーク上のエッジには重みを与えていないが，語の関連性が多値的であることを考えると，
重みを考慮する必要がある．ただし，既存のNewman法は重みのあるネットワークに対応していない．
そこで，重みを扱えるようにNewman法を改良することで，重みつきのネットワーク上でクラスタリングを行うことが考えられる．
語の関連性を「関連がある，ない」の2値ではなく，重みという多値で扱うこと
で，クラスタ数の自動取得も含めて，より適切なクラスタリング結果が
得られることが予想される．


加えて，Newman法では1語が1つのクラスタリングにしか所属できないハードクラスタリングであるため，
語の持つ多義性を解消することができない，という問題点がある．
しかし，Newman法をもとにしたソフトクラスタリングの手法も提案されており\cite{Reichard04}，
この手法を関連語ネットワークに適用することで語の多義性を解消できると考えられる．


また本研究では，同義・類義，上位語・下位語，連想語をすべて関連語としたが，
こういった語を関係性を分類していくことも重要であろう．
こういった研究には，前置詞を手がかりとして語の関係性を同定する\cite{Litkowski02}の手法があるが，
これを検索エンジンを利用していかに効率的に行うかは今後の検討課題のひとつである．



\section{結論}

本論文では，自動的に関連語のシソーラスを構築する手法について提案した．
提案手法では，検索エンジンを利用し，Webをコーパスとして用いる．Newman法をクラスタリング法として用いる部分が大きな特徴のひとつである．

検索エンジンを用いて語の関連度を取得する研究においては，コーパスを直接解析する手法と比べ，
共起頻度以外の文法的な情報が得られないため，クラスタリングによって関連語を同定し，高い精度を得られている研究はなかった．
本論文では，共起頻度のみを用いたクラスタリングで精度の高い関連語の同定に成功しており，
そのような点で非常に有意義な研究だと考えられる．


また，語の関係の相対性に着目し，相対性を考慮した手法を用いた．
$\chi^2値$は語群内での相対的な偏りを示す統計的指標であり，また
Newman法はネットワーク全体で相対的に結合度の強いノードをマージする
クラスタリング手法である．
これらの手法を用いることにより，より適合率が高く，適用範囲の広い
シソーラスの構築手法を提案することができた．

Webは重要な言語資源であり，その利用のためには検索エンジンの利用や大規模な処理への対応など，Webならではのアルゴリズムの工夫が必要になる．
今後，検索エンジンを利用した言語処理の可能性をさらに追求していきたい．

\acknowledgment

株式会社社長ホットリンク下大園貞寛氏，
国立情報学研究所大向一輝氏をはじめ，本研究にアドバイスをくださった
全ての方に感謝いたします．


\bibliographystyle{jnlpbbl_1.1}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Baker \BBA\ McCallum}{Baker \BBA\
  McCallum}{1998}]{Baker98}
Baker, D.\BBACOMMA\ \BBA\ McCallum, A. \BBOP 1998\BBCP.
\newblock \BBOQ Distributional Clustering for Text Classification\BBCQ\
\newblock In {\Bem Proceedings of SIGIR-98,21st ACM International Conference on
  Research and Development in Information Retrieval}, \mbox{\BPGS\ 96--103}.

\bibitem[\protect\BCAY{Barbara Ann~Kipfer}{Barbara
  Ann~Kipfer}{2006}]{RogetMillenium}
Barbara Ann~Kipfer, P.\BED\ \BBOP 2006\BBCP.
\newblock \Jem{Roget's New Millennium Thesaurus, First Edition}.
\newblock Lexico Publishing Group.

\bibitem[\protect\BCAY{Baroni \BBA\ Bisi}{Baroni \BBA\ Bisi}{2004}]{Baroni04}
Baroni, M.\BBACOMMA\ \BBA\ Bisi, S. \BBOP 2004\BBCP.
\newblock \BBOQ Using cooccurrence statistics and the web to discover synonyms
  in a technical language\BBCQ\
\newblock In {\Bem In Proceedings of LREC2004}, \mbox{\BPGS\ 26--28}.

\bibitem[\protect\BCAY{Brown, Pietra, deSouza, Lai, \BBA\ Mercer}{Brown
  et~al.}{1992}]{Brown92}
Brown, P., Pietra, V., deSouza, P., Lai, J., \BBA\ Mercer, R. \BBOP 1992\BBCP.
\newblock \BBOQ Class-based n-gram model of natural language\BBCQ\
\newblock {\Bem Comput. Linguist.}, {\Bbf 18}  (4), \mbox{\BPGS\ 467--479}.

\bibitem[\protect\BCAY{Chang}{Chang}{2005}]{Chang05}
Chang, J. \BBOP 2005\BBCP.
\newblock \BBOQ Domain Specific Word Extraction from Hierarchical Web
  Documents: A First Step Toward Building Lexicon Trees from Web Corpora\BBCQ\
\newblock In {\Bem Proceedings of the Fourth SIGHAN Workshop on Chinese
  Language Processing}, \mbox{\BPGS\ 64--71}.

\bibitem[\protect\BCAY{Church \BBA\ Hanks}{Church \BBA\ Hanks}{1990}]{Church90}
Church, W.\BBACOMMA\ \BBA\ Hanks, P. \BBOP 1990\BBCP.
\newblock \BBOQ Word association norms, mutual information, and
  lexicography\BBCQ\
\newblock {\Bem Comput. Linguist.}, {\Bbf 16}  (1).

\bibitem[\protect\BCAY{Crouch \BBA\ Yang}{Crouch \BBA\ Yang}{1992}]{Crouch92}
Crouch, C.~J.\BBACOMMA\ \BBA\ Yang, B. \BBOP 1992\BBCP.
\newblock \BBOQ Experiments in automatic statistical thesaurus
  construction\BBCQ\
\newblock In {\Bem SIGIR '92: Proceedings of the 15th annual international ACM
  SIGIR conference on Research and development in information retrieval},
  \mbox{\BPGS\ 77--88}.

\bibitem[\protect\BCAY{Curran}{Curran}{2002}]{Curran02}
Curran, J. \BBOP 2002\BBCP.
\newblock \BBOQ Ensemble Methods for Automatic Thesaurus Extraction\BBCQ\
\newblock In {\Bem Proceedings of the 2002 Conference on Empirical Methods in
  NLP}, \mbox{\BPGS\ 222--229}.

\bibitem[\protect\BCAY{Curran \BBA\ Moens}{Curran \BBA\
  Moens}{2002}]{Curran02-2}
Curran, J.\BBACOMMA\ \BBA\ Moens, M. \BBOP 2002\BBCP.
\newblock \BBOQ Improvements in Automatic Thesaurus Extraction\BBCQ\
\newblock In {\Bem Proceedings of the Workshop of the ACL SIGLEX}, \mbox{\BPGS\
  59--66}.

\bibitem[\protect\BCAY{Deerwester, Dumais, Landauer, Furnas, \BBA\
  Harshman}{Deerwester et~al.}{1990}]{Deerwester90}
Deerwester, S., Dumais, S., Landauer, T., Furnas, G., \BBA\ Harshman, R. \BBOP
  1990\BBCP.
\newblock \BBOQ Indexing by Latent Semantic Analysis\BBCQ\
\newblock {\Bem Journal of the American Society of Information Science}, {\Bbf
  41}  (6), \mbox{\BPGS\ 391--407}.

\bibitem[\protect\BCAY{Dhillon}{Dhillon}{2002}]{Dhillon02}
Dhillon, S. \BBOP 2002\BBCP.
\newblock \BBOQ Enhanced Word Clustering for Hierarchical Text
  Classification\BBCQ\
\newblock In {\Bem Proceedings of the 8th ACM SIGKDD}, \mbox{\BPGS\ 191--200}.

\bibitem[\protect\BCAY{Girvan \BBA\ Newman}{Girvan \BBA\
  Newman}{2002}]{Newman02}
Girvan, M.\BBACOMMA\ \BBA\ Newman, M. \BBOP 2002\BBCP.
\newblock \BBOQ Community structure in social and biological networks\BBCQ\
\newblock In {\Bem Proceedings of National Academic Science}, \mbox{\BPGS\
  7821--7826}.

\bibitem[\protect\BCAY{Grefenstette}{Grefenstette}{1994}]{Grefenstette94}
Grefenstette, G. \BBOP 1994\BBCP.
\newblock {\Bem Explorations in Automatic Thesaurus Discovery}.
\newblock Kluwer Academic Publishers.

\bibitem[\protect\BCAY{Heylighen}{Heylighen}{2001}]{Heylighen01}
Heylighen, F. \BBOP 2001\BBCP.
\newblock \BBOQ Mining Associative Meanings from the Web: from word
  disambiguation to the global brain\BBCQ\
\newblock In {\Bem Proceedings of the International Colloquium: Trends in
  Special Language \& Language Technology, R. Temmerman \& M. Lutjeharms},
  \mbox{\BPGS\ 15--44}.

\bibitem[\protect\BCAY{Hodge \BBA\ Austin}{Hodge \BBA\ Austin}{2002}]{Hodge02}
Hodge, V.\BBACOMMA\ \BBA\ Austin, J. \BBOP 2002\BBCP.
\newblock \BBOQ {Hierarchical word clustering---automatic thesaurus
  generation}\BBCQ\
\newblock {\Bem Neurocomputing}, {\Bbf 48}, \mbox{\BPGS\ 819--846}.

\bibitem[\protect\BCAY{Jarmasz \BBA\ Szpakowicz}{Jarmasz \BBA\
  Szpakowicz}{2003}]{Jarmasz03}
Jarmasz, M.\BBACOMMA\ \BBA\ Szpakowicz, S. \BBOP 2003\BBCP.
\newblock \BBOQ Roget's Thesaurus and Semantic Similarity\BBCQ\
\newblock In {\Bem Proceedings of Conference Recnet Advances in NLP},
  \mbox{\BPGS\ 212--219}.

\bibitem[\protect\BCAY{Kilgarriff \BBA\ Grefenstette}{Kilgarriff \BBA\
  Grefenstette}{2003}]{Kilgarriff03}
Kilgarriff, A.\BBACOMMA\ \BBA\ Grefenstette, G. \BBOP 2003\BBCP.
\newblock \BBOQ Web as Corpus\BBCQ\
\newblock In {\Bem In Proceedings. of the ACL Workshop on Intellignent Scalable
  Text Summarization}.

\bibitem[\protect\BCAY{Li \BBA\ Abe}{Li \BBA\ Abe}{1998}]{HangLi98}
Li, H.\BBACOMMA\ \BBA\ Abe, N. \BBOP 1998\BBCP.
\newblock \BBOQ Word clustering and disambiguation based on co-occurrence
  data\BBCQ\
\newblock In {\Bem Proceedings of the 17th international conference on
  Computational linguistics}, \mbox{\BPGS\ 749--755}. Association for
  Computational Linguistics.

\bibitem[\protect\BCAY{Lin}{Lin}{1998}]{Lin98a}
Lin, D. \BBOP 1998\BBCP.
\newblock \BBOQ Automatic retrieval and clustering of similar words\BBCQ\
\newblock In {\Bem Proceedings of the 17th international conference on
  Computational linguistics}, \mbox{\BPGS\ 768--774}\ Morristown, NJ, USA.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Litkowski}{Litkowski}{2002}]{Litkowski02}
Litkowski, C. \BBOP 2002\BBCP.
\newblock \BBOQ Digraph Analysis of Dictionary Preposition definition\BBCQ\
\newblock In {\Bem Proceedings of the SIGLEX/SENSEVAL Workshop on Word Sense
  Disambiguation: Recent Successes and Future Directions}, \mbox{\BPGS\ 9--16}.

\bibitem[\protect\BCAY{Manning \BBA\ Schutze}{Manning \BBA\
  Schutze}{1999}]{Manning99}
Manning, C.\BBACOMMA\ \BBA\ Schutze, H. \BBOP 1999\BBCP.
\newblock \BBOQ Foundations of statistical natural language processing\BBCQ\
\newblock In {\Bem MITPress}.

\bibitem[\protect\BCAY{Miller}{Miller}{1990}]{Miller90}
Miller, G. \BBOP 1990\BBCP.
\newblock \BBOQ WordNet:an on-line lexical database\BBCQ\
\newblock In {\Bem International Booktitle of Lexicography}.

\bibitem[\protect\BCAY{Motter, Moura, Lai, \BBA\ Dasgupta}{Motter
  et~al.}{2002}]{motter02}
Motter, A., Moura, A., Lai, Y., \BBA\ Dasgupta, P. \BBOP 2002\BBCP.
\newblock \BBOQ Topology of the conceptual network of language\BBCQ\
\newblock {\Bem Physical Review E}, {\Bbf 65}  (065102).

\bibitem[\protect\BCAY{長尾\JBA 水谷\JBA 池田}{長尾\Jetal }{1976}]{Nagao76}
長尾真\JBA 水谷幹男\JBA 池田浩之 \BBOP 1976\BBCP.
\newblock \JBOQ 日本語文献における重要語の自動抽出\JBCQ\
\newblock \Jem{情報処理}, {\Bbf 17}  (2), \mbox{\BPGS\ pp.110--117}.

\bibitem[\protect\BCAY{Newman}{Newman}{2004}]{Newman04}
Newman, M. \BBOP 2004\BBCP.
\newblock \BBOQ Fast algorithm for detecting community structure in
  networks\BBCQ\
\newblock In {\Bem Phys. Rev. E 69,2004}.

\bibitem[\protect\BCAY{Oyama, Kokubo, \BBA\ Ishida}{Oyama
  et~al.}{2004}]{Oyama04}
Oyama, S., Kokubo, T., \BBA\ Ishida, T. \BBOP 2004\BBCP.
\newblock \BBOQ Domain-Specific Web Search with Keyword Spices\BBCQ\
\newblock {\Bem IEEE Transactions on Knowledge and Data Engineering (TKDE)},
  {\Bbf 16}  (1), \mbox{\BPGS\ 17--27}.

\bibitem[\protect\BCAY{Palla, Der{\'e}nyi, Farkas, \BBA\ Vicsek}{Palla
  et~al.}{2005}]{Palla05}
Palla, G., Der{\'e}nyi, I., Farkas, I., \BBA\ Vicsek, T. \BBOP 2005\BBCP.
\newblock \BBOQ {Uncovering the overlapping community structure of complex
  networks in nature and society}\BBCQ\
\newblock {\Bem Nature}, {\Bbf 435}, \mbox{\BPGS\ 814--818}.

\bibitem[\protect\BCAY{Papadimitriou, Tamaki, Raghavan, \BBA\
  Vempala}{Papadimitriou et~al.}{1998}]{papadim98}
Papadimitriou, C., Tamaki, H., Raghavan, P., \BBA\ Vempala, S. \BBOP 1998\BBCP.
\newblock \BBOQ Latent Semantic Indexing: A Probabilistic Analysis\BBCQ.

\bibitem[\protect\BCAY{Pereira, Tishby, \BBA\ Lee}{Pereira
  et~al.}{1993}]{Pereira93}
Pereira, F., Tishby, N., \BBA\ Lee, L. \BBOP 1993\BBCP.
\newblock \BBOQ Distributional Clustering of English words\BBCQ\
\newblock In {\Bem Proceedings of the 31st annual meeting on Association for
  Computational Linguistics}, \mbox{\BPGS\ 183--190}.

\bibitem[\protect\BCAY{Reichardt \BBA\ Bornholdt}{Reichardt \BBA\
  Bornholdt}{2004}]{Reichard04}
Reichardt, J.\BBACOMMA\ \BBA\ Bornholdt, S. \BBOP 2004\BBCP.
\newblock \BBOQ Detecting Fuzzy Community Structures in Complex Networks with a
  Potts Model\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bbf 93}.

\bibitem[\protect\BCAY{Sanderson \BBA\ Croft}{Sanderson \BBA\
  Croft}{1999}]{Croft99}
Sanderson, M.\BBACOMMA\ \BBA\ Croft, B. \BBOP 1999\BBCP.
\newblock \BBOQ Deriving concept hierarchies from text\BBCQ\
\newblock In {\Bem SIGIR '99: Proceedings of the 22nd annual international ACM
  SIGIR conference on Research and development in information retrieval},
  \mbox{\BPGS\ 206--213}. ACM Press.

\bibitem[\protect\BCAY{Scott}{Scott}{2000}]{Scott00}
Scott, J. \BBOP 2000\BBCP.
\newblock {\Bem Social Network Analysis: A Handbook}.
\newblock {SAGE Publications}.

\bibitem[\protect\BCAY{Sigman \BBA\ Cecchi}{Sigman \BBA\
  Cecchi}{2002}]{sigman02}
Sigman, M.\BBACOMMA\ \BBA\ Cecchi, G. \BBOP 2002\BBCP.
\newblock \BBOQ Global organization of the Wordnet lexicon\BBCQ\
\newblock {\Bem PNAS}, {\Bbf 99}  (3), \mbox{\BPGS\ 1742--1747}.

\bibitem[\protect\BCAY{Slonim \BBA\ Tishby}{Slonim \BBA\
  Tishby}{2000}]{Slonim00}
Slonim, N.\BBACOMMA\ \BBA\ Tishby, N. \BBOP 2000\BBCP.
\newblock \BBOQ Document Clustring using Word Cluster via the Information
  Bottle neck Method\BBCQ\
\newblock In {\Bem Research and Development Information Retrieval},
  \mbox{\BPGS\ 208--215}.

\bibitem[\protect\BCAY{Szpektor, Tanev, Dagan, \BBA\ Coppola}{Szpektor
  et~al.}{2004}]{Szpektor04}
Szpektor, I., Tanev, H., Dagan, I., \BBA\ Coppola, B. \BBOP 2004\BBCP.
\newblock \BBOQ Scaling Web-based Acquisition of Entailment Relations\BBCQ\
\newblock In {\Bem Proceedings of EMNLP 2004}, \mbox{\BPGS\ 41--48}.
  Association for Computational Linguistics.

\bibitem[\protect\BCAY{Turney}{Turney}{2001}]{Turney01}
Turney, P. \BBOP 2001\BBCP.
\newblock \BBOQ Mining the web for synonyms: PMI-IR versus LSA on TOEFL\BBCQ\
\newblock In {\Bem EMCL '01: Proceedings of the 12th European Conference on
  Machine Learning}, \mbox{\BPGS\ 491--502}.

\bibitem[\protect\BCAY{Ward}{Ward}{1996}]{MobyThesaurus}
Ward, G.\BED\ \BBOP 1996\BBCP.
\newblock {\Bem Moby Thesaurus}.
\newblock Moby Project.

\bibitem[\protect\BCAY{Wettler \BBA\ Rapp}{Wettler \BBA\
  Rapp}{1993}]{Wettler93}
Wettler, M.\BBACOMMA\ \BBA\ Rapp, R. \BBOP 1993\BBCP.
\newblock \BBOQ Computation of word associations based on the co-occurrences of
  words in large corpora\BBCQ\
\newblock In {\Bem In Proceedings of the 1st Workshop on Very Large
  Corpora:Academic and Industrial Perspectives}, \mbox{\BPGS\ 84--93}.

\bibitem[\protect\BCAY{Widdows \BBA\ Dorow}{Widdows \BBA\
  Dorow}{2002}]{Widdows02}
Widdows, D.\BBACOMMA\ \BBA\ Dorow, B. \BBOP 2002\BBCP.
\newblock \BBOQ A Graph Model for Unsupervised Lexical Acquisition\BBCQ\
\newblock In {\Bem COLING 2002, 19th International Conference on Computational
  Linguistics}.

\bibitem[\protect\BCAY{Xu, Kurz, Piskorski, \BBA\ Schmeier}{Xu
  et~al.}{2002}]{Xu02}
Xu, F., Kurz, D., Piskorski, J., \BBA\ Schmeier, S. \BBOP 2002\BBCP.
\newblock \BBOQ A Domain Adaptive Approach to Automatic Acquisition of Domain
  Relevant Terms and their Relations with Bootstrapping\BBCQ\
\newblock In {\Bem Proceedings of the 3rd International Conference on Language
  Resources an Evaluation (LREC'02), May 29-31}.

\bibitem[\protect\BCAY{Yang \BBA\ Pedersen}{Yang \BBA\ Pedersen}{1997}]{Yang97}
Yang, Y.\BBACOMMA\ \BBA\ Pedersen, J. \BBOP 1997\BBCP.
\newblock \BBOQ A Comparative Study on Feature Selection in Text
  Categorization\BBCQ\
\newblock In {\Bem ICML '97: Proceedings of the Fourteenth International
  Conference on Machine Learning}, \mbox{\BPGS\ 412--420}. Morgan Kaufmann
  Publishers Inc.

\bibitem[\protect\BCAY{佐々木靖弘\JBA 佐藤理史\JBA 宇津呂武仁}{佐々木靖弘\Jetal
  }{2005}]{Sasaki05}
佐々木靖弘\JBA 佐藤理史\JBA 宇津呂武仁 \BBOP 2005\BBCP.
\newblock \JBOQ ウェブを利用した専門用語集の自動編集\JBCQ\
\newblock \Jem{言語処理学会第11回年次大会発表論文集}, \mbox{\BPGS\ 895--898}.

\bibitem[\protect\BCAY{池原悟\JBA 宮崎正弘\JBA 白井諭\JBA 横尾昭男\JBA
  中岩浩巳\JBA 小倉健太郎\JBA 大山芳史\JBA 林良彦}{池原悟\Jetal
  }{1997}]{goitaikei}
池原悟\JBA 宮崎正弘\JBA 白井諭\JBA 横尾昭男\JBA 中岩浩巳\JBA 小倉健太郎\JBA
  大山芳史\JBA 林良彦\JEDS\ \BBOP 1997\BBCP.
\newblock \Jem{日本語語彙大系}.
\newblock 岩波書店.

\bibitem[\protect\BCAY{日本電子化辞書研究所}{日本電子化辞書研究所}{1996}]{EDR}
日本電子化辞書研究所\JED\ \BBOP 1996\BBCP.
\newblock \Jem{EDR電子化辞書 仕様説明書}.
\newblock 日本電子化辞書研究所.

\end{thebibliography}




\begin{biography}

\bioauthor{榊　　剛史}{
2000年東京大学工学部電子情報工学科卒業．2006年同大学院情報理工学系研究科
 修士課程修了．研究分野はWebマインニング，言語処理．}

\bioauthor{松尾　　豊}{1997年東京大学工学部電子情報工学科卒業．2002年同大学院博士課程修了．同年より産業技術総合研究所に勤務．
現在同研究所情報技術研究部門勤務，スタンフォード大学客員研究員．高次Webマインニングに興味がある．人工知能学会，情報処理学会，AAAI，各会員．}

\bioauthor{内山　幸樹}{株式会社ホットリンク代表取締役社長．1995年，東京大学大学院在学中にマジックマウスの設立に加わり，日本最初期のサーチ
エンジンの開発に携わる．97年マジックマウス入社．98 年デジット常務．2000年6月，技術とアイディアで世界に勝負するためホットリンクを設立する．
近年では，HottoLaboやてくてく.jpなど研究者・技術者の交流支援事業などを立ち上げている．}

\bioauthor{石塚　　満}{1971年東京大学工学部電子卒．1976年同大学院博士課程修了．NTT，
東大大学院生産技術研究所・助教授，同大学工学部電子情報・教授を経て，
現在は2005年より同大学院情報理工学系研究科創造情報学専攻・教授．研究分野は人工知能，Webインテリジェンス，
次世代Web情報基盤，マルチモーダルエージェント．人工知能学会（会長），IEEE，AAAI，情報処理学会，電子情報通信学会の会員．}

\end{biography}



\biodate

\end{document}
