\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}

\setcounter{page}{101}
\setcounter{巻数}{5}
\setcounter{号数}{1}
\setcounter{年}{1998}
\setcounter{月}{1}
\受付{1997}{8}{20}
	
\採録{1997}{10}{24}

\setcounter{secnumdepth}{2}

\title{確率的クラスタリングを用いた文書連想検索}
\author{岩山 真\affiref{HARL} \and 徳永 健伸\affiref{TIT}}

\headauthor{岩山 真・徳永 健伸}
\headtitle{確率的クラスタリングを用いた文書連想検索}

\affilabel{HARL}{(株)日立製作所 基礎研究所}
{Advanced Research Laboratory, Hitachi, Ltd.}
\affilabel{TIT}{東京工業大学 大学院理工学研究科}
{Department of Computer Science, Tokyo Institute of Technology}

\jabstract{
本論文では，指定した文書と類似する文書を検索する文書連想検索のための確
率的クラスタリング HBC (Hierarchical Bayesian Clustering) を提案する．
文書連想検索を実現する際の問題点は，類似文書の検索に時間がかかることで
ある．単純な網羅検索では，比較対象の大きさ $N$ に比例した $O(N)$ の検
索時間を要する．本論文では，クラスタ検索と呼ばれる検索手法を用いること
でこの問題を解決する．クラスタ検索では，通常，クラスタリングによりクラ
スタの二分木をあらかじめ構築しておき，その上でトップダウンに二分木検索
を行うため，検索時間を $O(\log_2 N)$ に抑えることができる．ところが，
従来のクラスタ検索では，検索時に使う距離尺度とクラスタリング時に使う距
離尺度が直接関係ないため，単純な二分木検索では十分な検索精度が得られな
かった．それに対し HBC は，クラスタリングの対象文書を自己検索した際の
精度を最大化するため，検索により適したクラスタリングである．実験では，
「現代用語の基礎知識」を用いて，HBC を用いたクラスタ検索が Ward 法を用
いた従来のクラスタ検索よりも優れていることを実証する．また，「Wall
Street Journal」を用いて，HBC を用いたクラスタ検索が網羅検索に比べノイ
ズ頑健性に優れていることを実証する．}

\jkeywords{文書検索, クラスタ検索，文書クラスタリング，文書分類}

\etitle{Associative Document Search using a \\Probabilistic Document Clustering}
\eauthor{Makoto IWAYAMA\affiref{HARL} \and Takenobu TOKUNAGA\affiref{TIT}}

\eabstract{
This paper presents a hierarchical clustering algorithm called HBC
(Hierarchical Bayesian Clustering) for associative document search which
is retrieving similar documents to a given query document. A major issue
in realizing an associative document search is its efficiency in
searching similar documents. A straightforward exhaustive search takes
$O(N)$ search time. In this paper we discuss the use of cluster-based
search in which a document collection is automatically organized \mbox{into} a
binary cluster tree and a query document is then compared with each
cluster rather than each document. By searching a cluster tree in the
top down direction, search time can be reduced to $O(\log_2 N)$ on
average. However since clustering algorithms adopted in previous
cluster-based search frameworks used different similarity measure from
that used in top down document searching, search accuraccy for these
frameworks was not promissing.  HBC, on the other hand, directly seeks
the maximum search performance on the given document collection by
maximizing the self recall for it. In an experiment using ``Gendai
y\^ogo no kisotisiki,'' we verified the advantage of our cluster-based
search using HBC over the well known cluster-based search using Ward's
method. Also in an experiment using ``Wall Street Journal,'' we
confirmed that cluster-based search using HBC is more noise tolerant
than the exhaustive search.}

\ekeywords{Text Retrieval, Cluster-based Search, Text Clustering, Text Categorization}

\begin{document}
\thispagestyle{myheadings}
\maketitle

\section{はじめに}
\label{sec:introduction}

文書検索では，検索対象の文書集合が大きくなるにつれ，高速/高精度な検索が
困難になる．例えば，AltaVista~\footnote{{\tt
http://altavista.digital.com}}に代表されるインターネット上のキーワード検
索エンジンでは，検索時に入力されるキーワード数が極端に
少ないため~\footnote{ AltaVistaでは平均2個弱のキーワードしか入力されない}，
1) 望んた文書が検索されない(再現率の問題)，2) 望まない文書が大量に検索さ
れる(適合率の問題)，といった問題が生じている．そのため，要求拡張(query
expansion)~\cite{smeaton:83:a,peat:91:a,schatz:96:a,niwa:97:a}，関連度フィー
ドバック(relevance feedback)~\cite{salton:83:a,salton:90:a}などの手法が
提案されてきた．これらの手法はいずれも，要求となるキーワード集合を拡張し
たり洗練したりすることで，ユーザの検索意図を明確かつ正確なものに導いてい
く．

これに対し，検索時にキーワード集合ではなく文書それ自身を入力し，入力文書
と類似する文書を検索する方法が考えられる~\cite{wilbur:94:a}．この検索方
法を{\gt 文書連想検索}と呼ぶ．文書連想検索が有効なのは，検索要求と関連
する文書を我々が既に持っているという状況や，キーワード検索の途中で関連
する文書を一つでも見つけたという状況である．また，論文，特許など，我々
自身が書いた文書もそのまま検索入力として利用できる．文書連想検索を使う
ことにより，適切なキーワード集合を選択することなしに，関連する文書を見
つけることができる．

文書連想検索を実現する際の問題点は，類似文書の検索に時間がかかることで
ある．単純な網羅検索では，検索対象の大きさ $N$ に比例した $O(N)$ の時
間を要する．そこで本論文では，{\gt クラスタ検索}~\cite{salton:83:a}と
呼ばれる検索方法を用いる．クラスタ検索では，通常，クラスタリングにより
クラスタの二分木をあらかじめ構築しておき~\footnote{クラスタリングにも，
対象データ集合を平坦なクラスタ集合に分割する方法(非階層的クラスタリン
グ)もあるが~\cite{anderberg:73:a}，本論文では，クラスタの階層的な木構
造を構築する方法(階層的クラスタリング)に限る．また，クラスタ木も相互背
反な二分木に限る．}，その上でトップダウンに二分木検索を行う．よって，
検索時間は平均 $O(\log_2 N)$ に抑えられる．ところが，クラスタ検索に関
する従来の研究~\cite{croft:80:a,willett:88:a}では，単純な二分木検索で
は十分な検索精度が得られないという問題があった．その理由の一つは，クラ
スタリング時と検索時に異なる距離尺度を用いていたことである．ほとんどの
研究では，クラスタリングの手法として単一リンク法，Ward 法などを用いて
いたが，これらの手法は，後の検索で使われる尺度(例えば，TF$\cdot$IDF法
や確率)とは直接関係のない尺度でクラスタの二分木を構築していく．これに
対し本論文では，クラスタリングの対象文書それぞれを自己検索した際の精度
を最大化していく確率的クラスタリングを提案する．よって本クラスタリング
法は，検索に適した手法であると言える．実際に，クラスタ検索に本クラスタ
リング法を用いた場合，単純な二分木検索でも十分な検索精度を得ることがで
きる．

検索速度が速い点に加え，クラスタ検索には幾つかの利点がある．クラスタ検索
が提案されたそもそもの理由は，「密接に関連した文書群は，同じ検索要求に対
する関連性も同等に高い」という
{\gt クラスタ仮説}~\cite{van-rijsbergen:74:a}である．通常のキーワード検
索では，検索要求と単一文書を厳密なキーワード符合に基づいて比較するため，
キーワードの表記の異なりにより関連する文書をとり逃すこともあるが，クラス
タ検索では，検索要求を意味的にまとまった文書集合(クラスタ仮説で言うとこ
ろの「密接に関連した文書群」)と比較するため，この問題も起りにくくなる．
クラスタ仮説は，特に検索精度の向上という点において実験的に検証されていな
い仮説であったが，近年，Hearst 等により，キーワード検索で検索した文書集
合を絞りこむという状況で，その有効性が実証されている~\cite{hearst:96:a}．
本論文では，クラスタ検索が検索対象に含まれているノイズの影響を受けにく
いこと(ノイズ頑健性)に注目し，本論文で提案するクラスタ検索が網羅検索に
比べ優れていることを実証する．

以下，\ref{sec:cluster_based_search}~節では，クラスタ検索について説明す
る．\ref{sec:hbc}~節では，本論文で提案する確率的クラスタリングについて説
明する．\ref{sec:experiment}~節では，本論文で提案したクラスタ検索の有効
性を調べるために行なった幾つかの実験について述べる．

\section{クラスタ検索}
\label{sec:cluster_based_search}

クラスタ検索に限らず，文書対文書の比較を行うには，まず文書間の距離を定義
する必要がある．本論文では，条件付き確率 $P(C|d)$ を用い，文書 $d$ から
文書集合 $C$ への方向性のある類似性を定義する．ある文書集合を検索する際
は，$d$ が入力文書(検索要求)となり，$C$ がこれから検索しようとする文書集
合の部分集合となる．最も極端な例が網羅検索であり，$C$ は文書集合の各文書
それ自身になる(図~\ref{fig:search_strategies}~(a)参照)．一方，クラスタ検
索では，$C$ は何らかの指針により自動/人手で作られたクラスタである．
$P(C|d)$ を推定する方法は幾つか
提案されているが~\cite{robertson:76:a,fuhr:89:a,kwok:90:a}，本論文では 
Iwayama 等の推定法~\cite{iwayama:94:b}を用いることにする．
付録~\ref{app:SVMV}に $P(C|d)$ の推定法を記す．

図~\ref{fig:search_strategies}~(b)が典型的なクラスタ検索を図式化したもの
である．本論文で扱うクラスタ検索では，文書集合を二分木として自動的に構成
し(このステップを{\gt クラスタリング}または{\gt 訓練}と呼ぶ)，検索要求を
各クラスタ(ノード)と比較することによって，検索要求と類似する文書を指定し
た数だけとりだす(このステップを{\gt 検索}または{\gt テスト}と呼ぶ)．最も
単純な検索法は{\gt 二分木検索}であり(図~\ref{fig:search_strategies}~(b)
参照)，クラスタ木の根からトップダウンに木をたどり，指定した数の文書を含
むクラスタを探す．木をたどる際は，各ノードでそれぞれの子ノードについて 
$P(C|d)$ を計算し，どちらに進むかを決定する．二分木検索は，平均 
$O(\log_2 N)$ の検索時間しか必要とせず，網羅検索($O(N)$)に比べ高速な検索
が可能である．

一般に，網羅検索はその検索コストのため大規模な文書集合の検索/ランキング
には適用しづらい．事実，現実に運用されている検索システムのほとんどは，ラ
ンク付きの検索出力が提供されていないか，提供されていても
近似計算~\cite{cutting:97:a}である場合が多い．
連想検索のように検索要求が長い場合は，ランク付けの計算に検索要求の全情報
を使わないこともある~\cite{frakes:92:a}．検索コストを軽減する効果的な方
法は，キーワードから文書への逆インデクス(inverted
file)~\cite{salton:83:a}を使い，検索要求に含まれているキーワードを全く
含まない文書を検索対象から除外することである~\cite{perry:83:a}．残った
文書集合を網羅検索することで計算量も幾分軽減できる．しかし，逆インデク
スの導入は問題の本質的解決ではなく，原理的には依然として $O(N)$ の検索
コストが必要である．

\begin{figure*}
\begin{center}
\epsfile{file=iwayama1.eps,width=0.9\textwidth}
\end{center}
\caption{連想検索における文書検索法: 網羅検索とクラスタ検索}
\label{fig:search_strategies}
\vspace{-2mm}
\end{figure*}

クラスタ木上をトップダウンに二分木検索する方法とは逆に，葉からボトムアッ
プにクラスタ木を検索する方法もある．この検索法は{\gt ボトムアップクラ
スタ検索}と呼ばれ，二分木検索よりも精度的に有効であることが実証されて
いる~\cite{croft:80:a,willett:88:a}．ところが，ボトムアップクラスタ検
索では，まず検索の出発点となる葉ノードを決める必要がある．既に何らかの
方法で出発点がわかっている場合はよいが，そうでない場合はゼロからこのノー
ドを見つけるため，網羅検索に近い計算量が必要となる．本論文では，その簡
素さと高速性のため，トップダウンな二分木検索を使うことにする．また，二
分木検索にも，ビーム幅内を並行して検索する，検索の出発ノードを葉に近い
ノードにするなど様々な拡張が考えられるが，本論文では，断わりのない限り
単純な二分木検索に限ることにする．

\section{確率的クラスタリング(HBC)}
\label{sec:hbc}

クラスタ検索におけるクラスタリングの目的は，検索を行った際に高い精度を
与えるようなクラスタ木を構築することである．不適切なクラスタ木は，検索
要求に対して関連の低い文書を出力してしまう．特に，クラスタ木の根に近い
部分は，与えられたほとんどの文書集合を含むため漠然性が高く，二分木検索
もこの部分での比較で誤りを起しやすい．従来のクラスタ検索において二分木
検索の精度が悪かったのは主にこの理由である．以下では，二分木検索でも高
い精度を与えるような確率的クラスタリングを提案する．核となるアイデアは，
クラスタリング(訓練)にも検索(テスト)にも前節で説明した確率 $P(C|d)$ を
用いることである．

まず，クラスタリングで使う尺度として{\gt\bf 自己再現率(self recall)}を定
義する．あるクラスタ $C$ に関する自己再現率 $SR(C)$ を以下のように定義す
る．
\begin{equation}
  SR(C) = \prod_{d \in C} P(C|d).
\end{equation}
自己再現率は，クラスタ内の各文書が自分自身を含むクラスタを見つけること
ができる確率，と解釈することができる．あるクラスタ $C$ にとって，
$SR(C)$ の値が大きいということは，$C$ 内の各文書を検索入力とした時，そ
れらが $C$ を見つける確率が高いということである．

文書集合 ${\cal D}$ がクラスタの集合 $\{C_1, C_2, \ldots\}$ に分割されて
いるとすると，その文書集合 ${\cal D}$ に対する自己再現率は以下のように定
義できる．
\begin{equation}
  SR({\cal D}) = \prod_{C \in {\cal D}} SR(C)
	      = \prod_{C \in {\cal D}} \prod_{d \in C} P(C|d).
\end{equation}
これは，文書集合全体に関する自己検索の精度に関連する．ここまでで，クラス
タリングの目的は「文書集合 ${\cal D}$ が与えられた時，$SR({\cal D})$ が
最大となる分割を見付けること」と詳細化できる．
ただし，通常は山登り法になどにより局所的な最大分割を求めることが多い．
例えば，$SR({\cal D})$ を
評価関数として非階層的クラスタリングアルゴリズム~\cite{anderberg:73:a}を
適用すると，文書集合を平坦なグループに分割することができる．また，文書集
合 ${\cal D}$ に対して階層的な二分クラスタ木を構築するには，以下に示す凝
集型アルゴリズムを適用すればよい．
\begin{enumerate}
  \item 初期クラスタ集合を，
	${\cal D}$ 内の各文書それ自身のみからなるクラスタの集合とする．
  \item マージにより $SR({\cal D})$ の増分が最大になるような
	クラスタのペアを見つけ実際にマージする．
  \item 残りのクラスタの数が 1 でなければステップ 2 に戻る．
\end{enumerate}
以上のアルゴリズムを{\gt\bf 階層的ベイズクラスタリング(HBC: Hierarchical
Bayesian Clustering)}と呼ぶ．
HBC の詳細については，\cite{iwayama:95:b,iwayama:95:a}を参照されたい．
そこでは，HBC と従来のクラスタリング手法との比較実験も行われている．ま
た，付録~\ref{app:hbc}に HBC の形式的な記述を示す．

従来のクラスタ検索における実験では，二分木検索に関して否定的な結果がでて
いた．考えられる理由は，クラスタリング(訓練)と検索(テスト)で異なった尺度
(原理)を用いていたことである．従来の実験では，単一リンク法や Ward 法をク
ラスタリングの方法として用いていたが，これらの方法は，検索に使う尺度とは
直接関係のない尺度を使いクラスタ木を構築している．例えば単一リンク法では，
二つのクラスタ間の距離として，それらのクラスタを構成する要素(文書)間の最
も近い距離を使う．よって，クラスタ内の他の構成要素の情報は無視されてしま
う．また，構成要素(文書)とクラスタ全体との関係が考慮されていない．検索で
用いるのは文書とクラスタとの距離である．これらの欠点は，完全リンク法や平
均リンク法にもあてはまる．Ward 法は，群内誤差の平方和によりクラスタ間の
距離を計算するため，上記の欠点はない．しかし，群内誤差の平方和は，検索時
に用いる距離尺度とは直接関係がない．それに対し HBC は，文書集合が与え
られると，それらを自己検索した時の精度(具体的には自己再現率)を最大化す
るようなクラスタ木を構築する．つまり，訓練例に対する検索精度の最大化を
行っているため，クラスタ検索という用途に直接関連した手法である．次節で
は，HBC をクラスタ検索に用いた場合の有効性を実験により検証する．なお，
単一リンク法や Ward 法も統計解析という元々の用途には有効な手法である．

\section{実験}
\label{sec:experiment}

\subsection{実験方式とデータについて}

実験では，連想検索の精度を評価するために{\gt トピック割り付け}を行った．
トピック割り付けとは，あらかじめ定義されたトピックの中から 1 個以上のト
ピックを文書に割り付けるタスクである．例えば，ある文書に $\{x, y, z\}$ 
という 3 個のトピックが付いているとする．これらの正解トピックは，通常，
専門家によって割り付けられる．そして，自動的な方法により，同じ文書に 
$\{x, w\}$ という 2 個のトピックが割り付けられたとする．ここで，$x$ とい
う 1 つのトピックのみが 3 個の正解トピックから再現されたという意味で，
{\gt\bf 再現率(recall)}は $1/3$ となる．また，$x$ という 1 つのトピック
のみが，自動的に割り付けられた 2 個のトピックのなかで正解であったという
意味で，{\gt\bf 適合率(precision)}は $1/2$ となる．

自動的なトピック割り付け法としては，$k$-NN 法($k$-Nearest Neighbor
classifiers)~\cite{weiss:90:a,masand:92:a,mouri/97/a}を用いた．$k$-NN 法
では，ある文書 $d$ にトピックを割り付ける際，あらかじめ専門家によりトピッ
クが割り付けられている文書集合(訓練データ)の中から $d$ に近いものを $k$ 
個検索する． この検索法に，文書連想検索の手法(網羅検索，クラスタ検索)
を用い比較した．検索した $k$ 個の訓練データには既にトピックが付いてい
るため，それぞれのトピックを重み付きで集計し，あるしきい値以上になるト
ピックを $d$ に割り付ける．重みとしては，$d$ と各々の訓練データとの距
離(条件付き確率)を用いた．ここで，$d$ に割り付けられるべき正解トピック
が既にわかっているため，再現率/適合率が計算できる．また，自動割り付け
におけるしきい値を変化させることで，再現率/適合率のトレードオフ曲線が
描ける．

実験データには，「現代用語の基礎知識(92年版)~\cite{gk/92/a}(GK)」と
「Wall Street Journal~\cite{liberman:91:a}(WSJ)」を用いた．それぞれの特
徴は以下のとおりである．
\begin{description}
 \item[{\gt\bf 現代用語の基礎知識(GK)}]\strut\\
	    日本語の辞書データ．
	    $18,476$ 個の辞書見出しを持ち，
	    それぞれ $149$ の小カテゴリいずれかに分類されている．
	    この小カテゴリをトピックとして用いた．
	    つまり，
	    各辞書見出しは単一の正解トピックを持っていることになる．
	    各辞書見出しの説明文は，
	    $13$ から $1,938$，
	    平均 $287$ の文字長を持つ．
	    短い説明文の影響を除くため，
	    説明文中に名詞，未知語(抽出法については後述)を $100$ 個以下
	    しか含まない辞書見出しを除去した．
	    また，
	    辞書見出しを少数しか持たないカテゴリの影響を除くため，
	    辞書見出しを $20$ 個以下しか含まないカテゴリを除去した．
	    この結果，残った辞書見出し数は $1,072$，
	    カテゴリ数は $39$ となった．
 \item[{\gt\bf Wall Street Journal(WSJ)}]\strut\\
	    英語の新聞記事データ．
	    '89/7/25 から '89/11/2 までの $8,907$ 記事を使った．
	    各記事には，
	    $78$ 個のトピックの中から複数のトピックが割り付けられている．
	    一つもトピックを持たない記事は取り除いた．
	    記事に割り付けられている平均トピック数は $1.94$ 個である．
\end{description}

これら二つのデータセットには，日本語と英語という大きな相違点の他に，以下
の特筆すべき相違点がある．
\begin{itemize}
 \item GK の各文書が単一のトピックしか持たないのに対し，
       WSJ は複数(平均 $1.94$ 個)のトピックを持つ．
 \item GK は，
       文書長，および各トピックが持つ文書数が
       比較的均一なデータセットであるのに対し，
       WSJ は非均一なデータセットである．
       GK には各トピックを担当する編集者が存在し，
       その編集者が担当トピックの辞書見出しを管理しているからである.
       それに加え，
       GK では，
       短い辞書見出し，
       辞書見出し数が少ないトピックを上記の方法により強制的に除去している．
       よって，
       WSJ に比べ，
       GK はよりノイズの少ないデータセットであると言える．
       逆の視点から見ると，
       WSJ はより現実データに近いと言える．
\end{itemize}

実験の前処理として，まず，文書表現として用いるタームを抽出する必要がある．
両データセットとも，名詞と未知語をタームとして用いた．タガーとして，GK 
では JUMAN~\cite{juman/94/a} を，WSJ では Xerox Part-of-Speech
Tagger~\cite{cutting:93:a} を用いた．WSJ に関しては，
ispell~\cite{ispell} を用いて語尾処理を行ない，単語の原形のみ用いた．

また，トピック割り付けを行うには，データセットを訓練データとテストデータ
に分割する必要がある．GK は文書数が少ないため，4 分割のクロスバリデーショ
ンを行った．WSJ では，'89/7/25 から '89/9/29 までの $5,820$ 記事を訓練デー
タとして，'89/10/2 から '89/11/2 までの $3,087$ 記事をテストデータとして
使った．

\subsection{従来のクラスタ検索との比較}

まず，比較的ノイズの少ない GK を用いて，HBC を用いたクラスタ検索と従来か
ら行われていたクラスタ検索を比較する．従来法としては，クラスタリングに 
Ward 法~\cite{anderberg:73:a}を，検索に確率モデルを用いた．よって，両者
はクラスタリングの手法のみが異なる．また，比較対象として，網羅検索による
実験も行った．網羅検索における文書間の距離尺度には，クラスタ検索と同じ確
率モデルを用いた．以上は $k$-NN 法によるトピック割り付けであるが，この他
にトピック割り付けの代表的な方法(以下，{\gt トピック検索法}と呼ぶ)も比較
対象として実験に用いた．トピック検索法では，まず，各トピック毎にそのトピッ
クが割り付けられている文書を集め，トピックを表現する文書集合とする．次
に，トピックを割り当てようとする文書と，各トピックを表現している文書集
合との間の距離を計算して，距離が近いトピックを文書に割り当てる．距離尺
度としては，上記手法と同じ確率モデルを用いた．

GK では，割り当てられるべきトピックが一つであるため，実験に用いた手法で
も，上位 1 位のトピックを割り付け，それが正解となっている割合で精度を
測定した．実験結果を図~\ref{fig:gk}に示す．図中，X 軸は，$k$-NN 法でい
うところの $k$，つまり，判定に用いた訓練データ数である．

\begin{figure}
 \begin{center}
   
   
   \epsfile{file=iwayama2.eps,width=0.9\textwidth}
 \end{center}
 \vspace{-2mm}
 \caption{トピック割り付けにおける連想検索の比較(GK)}
 \label{fig:gk}
 \vspace{-2mm}
\end{figure}

図~\ref{fig:gk}から，$k$ が極端に小さくない場合，網羅検索の精度が最も良
いことがわかる．また，HBC を用いたクラスタ検索も，網羅検索の精度曲線を良
く近似している．このことから，検索に要する速度などを考えると，HBC を用い
たクラスタ検索は速度/精度の点でバランスの取れた手法であると言える．逆に，
Ward 法を用いたクラスタ検索が与える精度曲線は，網羅検索の精度曲線とは極
端に異なり，特に $k$ が $300$ 以下での精度が非常に悪くなっている．興味深
いのは，網羅検索，二つのクラスタ検索共に，$k$ が大きくなるにつれトピック
検索法が与える精度に収束していく点である．ただし，HBC を用いたクラスタ検
索，網羅検索が，$k$ を適当に設定するとトピック検索法を上回るのに対し，
Ward 法を用いたクラスタ検索は，常にトピック検索法を下回る．

以上の実験結果から，HBC を用いたクラスタ検索法は，従来のクラスタ検索より
も有効であることが確認できた．次節では，ノイズを含むより実データに近い 
WSJ を用いて，HBC を用いたクラスタ検索と網羅検索との違いを詳しく調べる．

\subsection{クラスタ検索のノイズ頑健性}

クラスタ検索は，網羅検索と比べると汎化能力という点で優れている．クラス
タ検索は訓練データを一般化したクラスタ集合を扱うためである．網羅検索は
訓練データそれ自体を扱うため，訓練データ中に存在するノイズの影響を受け
やすい．前節の GK による実験では，この点が確かめられなかったが，これは 
GK がノイズの少ない均一なデータセットであることによる．本節では，WSJ 
を使って，データセット中に存在するノイズがトピック割り付け(すなわち連
想検索)に及ぼす影響を調べる．

WSJ の各文書には複数のトピックが割り付けられているため，前述の再現率/適
合率で評価を行った．トピック割り付け戦略としては以下の 3 種類を用い比較
した．
\begin{description}
 \item[{\gt\bf 定数割り付け(k-per-doc)}]\strut\\
	    各テストデータに，
	    均一に $k$ 個づつトピックを割り当てる．
	    ここでは $k$ の値を変化させて再現率/適合率曲線を描く．
 \item[{\gt\bf 確率的割り付け(probability threshold)}]\strut\\
	    各テストデータに割り付けられるトピックには，
	    確率から重みが計算できる．よって，あるしきい値以上の重みを
	    持つトピックを各テストデータに割り付ける．ここでは
	    割り付けのしきい値を変化させて再現率/適合率曲線を描く．
 \item[{\gt\bf 比例配分割り付け(propotional assignment)~\cite{lewis:92:a}}]\strut\\
	    各トピック毎に
	    テストデータを重みの順にソートしておき，
	    訓練データ中でそのトピックが占める割合に比例した数のテスト
	    データにそのトピックを割り付ける．
	    例えば，
	    訓練データ中で $2\%$ の文書に割り付けられているトピックは，
	    比例配分の定数を $0.1$ とすると，
	    テストデータ中の $0.2\%$ の文書に割り付けられる．
	    比例配分の定数を $5$ とすると，
	    テストデータ中の $10\%$ の文書に割り付けられる．
	    ここでは，
	    比例配分の定数を変化させて再現率/適合率曲線を描く．
\end{description}
従来行なわれた実験~\cite{lewis:92:a,iwayama:94:b,nishino/95/a}では，比例
配分割り付けの優位性が確認されている．しかし，比例配分割り付けを行うには，
あらかじめ十分な数のテストデータがそろっている必要がある．よって，比例配
分割り付けは，バッチ的な割り付け処理の局面では有効であるが，オンライン
(リアルタイム)で割り付けを行なうような状況に適用することはできない．

\begin{figure}
 \begin{center}
  
  
  \epsfile{file=iwayama3.eps,width=0.9\textwidth}
 \end{center}
 \vspace{-1.5mm}
 \caption{トピック割り付けにおける連想検索の比較(WSJ, 定数割り付け)}
 \label{fig:wsj-kdoc}
 \vspace{-1.5mm}
\end{figure}

\begin{figure}
 \begin{center}
  
  
  \epsfile{file=iwayama4.eps,width=0.9\textwidth}
 \end{center}
 \vspace{-1.5mm}
 \caption{トピック割り付けにおける連想検索の比較(WSJ, 確率的割り付け)}
 \label{fig:wsj-thresh}
 \vspace{-1.5mm}
\end{figure}

\begin{figure}
 \begin{center}
  
  
  \epsfile{file=iwayama5.eps,width=0.9\textwidth}
 \end{center}
 \vspace{-1.5mm}
 \caption{トピック割り付けにおける連想検索の比較(WSJ, 比例配分割り付け)}
 \label{fig:wsj-prop}
 \vspace{-1.5mm}
\end{figure}

図~\ref{fig:wsj-kdoc}~$\sim$~\ref{fig:wsj-prop}にそれぞれの割り付け戦略
による実験結果を示す．ここでは，HBC によるクラスタ検索と網羅検索を比較し
ている．また，ベースラインとして，トピック検索法による結果も示した．Y 軸
の breakeven とは，再現率/適合率トレードオフ曲線において，再現率と適合率
が等しくなる点の値である．X 軸は，前節と同じく $k$-NN 法における $k$ の
値である．

図~\ref{fig:wsj-kdoc}~$\sim$~\ref{fig:wsj-prop}から，まず，他の二つの割
り付け戦略に比べ，比例配分割り付けが優れていることがわかる．また，比例配
分割り付けでは，網羅検索，クラスタ検索共に，トピック検索と同程度の精度で
ある．更に，両者共に $k$-NN 法の $k$ による影響をあまり強く受けていない．
よって，比例配分割り付けは，検索の手法に対して安定した割り付け戦略である
と言える．ところが，前述したように，比例配分割り付けはバッチ処理に限られ
るという制限がある．

定数割り付け，確率的割り付けでは，網羅検索，クラスタ検索共に，ベースラ
インのトピック検索を大きく上回っている．これは，$k$-NN 法の優位性を示
している．ここで注目して欲しいのは，$k$-NN 法でも，網羅検索の精度曲線
が $k$ の値に大きく影響を受けている点である．特に，最大 breakeven を与
える $k$ の範囲が非常に狭く，それより $k$ の値が大きくなると，
breakeven が急激に低下している．これは，訓練データ中に存在するノイズの
影響を強く受けていることを意味している．一方，クラスタ検索の精度曲線は 
$k$ に依存せず安定している．つまり，最大 breakeven を与える $k$ の範囲
が広いため，微妙なパラメータ($k$)設定を行う必要がない．これは，クラス
タリングという汎化操作により，訓練データ中のノイズの影響があらわれにく
くなっていることを意味している．以上から，HBC を用いたクラスタ検索は，
網羅検索に比べノイズ頑健性に優れていると言える．

\section{おわりに}

本論文では，文書連想検索のための新しいクラスタ検索法を提案した．提案し
たクラスタ検索では，与えられた文書集合を自己検索した時の精度を最大化す
る確率的クラスタリングを用いている．よって，本クラスタリング手法は，従
来のクラスタ検索で用いられていたクラスタリング手法に比べると，検索に密
接に関連した手法であると言える．「現代用語の基礎知識」「Wall Street
Journal」を用いた実験の結果，従来のクラスタ検索に対する本手法の優位性
が確認できた．また，網羅検索に対しては，本手法がノイズ頑健性という点で
優れていることが確認できた．

以下，問題点と今後の課題を挙げる．
\begin{description}
 \item[{\gt クラスタリングの高速化}]\strut\\
	    本論文で提案したクラスタリングに限らず，通常の階層的クラスタ
	    リングは，サイズ $N$ の文書集合をクラスタリングするのに 
	    $O(N^2)$ の空間的/時間的計算資源を要する．今後は，特に大規模
	    文書集合の文書連想検索に対処するために，クラスタリングに要
	    する計算量を抑える必要がある．この問題に関して近年，文書表
	    現として用いる単語の次元数を減らす~\cite{schutze:97:a}，ク
	    ラスタ間の距離を計算せず単語分布を調べる~
	    \cite{tanaka/97/a}などの方法が提案されている．我々は，HBC 
	    の近似アルゴリズムによりこの問題を解決することを考えており，
	    既に幾つかの手法を提案し，予備的な実験で有望な結果を得てい
	    る~\cite{iwayama/97/a}．今後は，大規模データに適用してその
	    有効性を実証する必要がある．
 \item[{\gt 多重分類}]\strut\\
	    現状のクラスタ木は単純な二分木であるため，同一文書が複数の観
	    点から分類されるといった多重分類を扱えない．この問題について
	    は，クラスタ生成時に同一文書が複数のクラスタに分類されること
	    を許す，あるいは検索時に複数の検索パスを探索するなどの手法が
	    考えられる．前者の手法については，既に提案した HBC の近似ア
	    ルゴリズム~\cite{iwayama/97/a}が有望である．また，後者の手法
	    については，シソーラス構築というタスクで有効な結果を
	    得ている~\cite{tokunaga:97:a}．
 \item[{\gt 動的な文書集合への対応}]\strut\\
	    通常のクラスタリングでは，対象となる文書集合が文書の追加/削
	    除などにより変化すると，一からクラスタリングを実行し直さなけ 
	    ればならない．クラスタリングの高速化により再計算の時間が軽減
	    されるとはいえ，大規模な文書集合を変化の都度再クラスタリング
	    するのは非現実的である．この問題については，ほとんど研究が
	    なされていない~\cite{crouch:75:a,can:89:a}．我々は，HBC の近
	    似アルゴリズム~\cite{iwayama/97/a}の一種がインクリメンタルに
	    動作することに着目し，動的な文書集合に対応することを考えてい
	    る．
\end{description}

\vspace{-2mm}

\bibliographystyle{jnlpbbl}
\bibliography{IFIR,jIFIR}

\clearpage
\begin{biography}
\biotitle{略歴}
\bioauthor{岩山 真}{
1987年東京工業大学工学部情報工学科卒業．
1992年同大学院理工学研究科博士後期課程修了．
同年(株)日立製作所基礎研究所入所．
博士(工学)．
自然言語処理，情報検索の研究に従事．
情報処理学会，人工知能学会，AAAI, ACM SIGIR各会員．
}
\bioauthor{徳永健伸}{
1983年東京工業大学工学部情報工学科卒業．
1985年同大学院理工学研究科修士課程修了．
同年(株)三菱総合研究所入社．
1986年東京工業大学大学院博士課程入学.
現在，同大学大学院情報理工学研究科助教授．
博士(工学)．
自然言語処理，計算言語学，情報検索などの研究に従事．
情報処理学会，人工知能学会，計量国語学会，Association for Computational
Linguistics, ACM SIGIR各会員．
}

\bioreceived{受付}
\bioaccepted{採録}
\end{biography}

\vspace{-3mm}
\appendix

\section{$P(C|d)$ の推定法}
\label{app:SVMV}

まず，「存在する全てのターム~\footnote{本研究ではタームとして名詞および
未知語を用いた．}から一つを乱数抽出したとき，それが $t$ と等しい」という
事象を``$T=t$''とする．$P(C|d)$ を可能な全ての``$T=t$''で条件付けすると
\begin{eqnarray}
  P(C|d)
    &=& \sum_{t} P(C|d,T=t) P(t|d)\nonumber\\
    &\approx& \sum_{T=t} P(C|T=t) P(T=t|d).\label{eq:svmv1}
\end{eqnarray}
となる．ここでの近似は，$T=t$ が与えられたという条件下での $C$ と $d$ の
条件付き独立性の仮定による~\footnote{詳しくは $P(C|d,T=t)=P(C|T=t)$．こ
の式は，もし $T=t$ を知れば，$C$に関する情報と $d$ に関する情報は独立で
あることを示している．これは強い仮定であるが，$T=t$ が $d$ の特殊化され
た表現だと考えると妥当である．}．ベイズの定理を用いると，
(\ref{eq:svmv1})は以下のようになる．
\begin{equation}
  P(C|d) = P(C) \sum_{T=t} \frac{P(T=t|C) P(T=t|d)}{P(T=t)}.
    \label{eq:svmv2}
\end{equation}
ここで，
各々の要素確率を以下のように推定する．
\begin{itemize}
  \item $P(T=t|C)$: $C$ における $t$ の相対頻度．
  \item $P(T=t|d)$: $d$ における $t$ の相対頻度．
  \item $P(T=t)$: 与えられた文書集合全体における $t$ の相対頻度．
  \item $P(C)$: 本論文では定数として扱った．
\end{itemize}

\section{階層的ベイズクラスタリング(Hierarchical Bayesian Clustering)}
\label{app:hbc}

\fbox{
\begin{minipage}{100mm}
  \baselineskip=12pt
  \sfcode`;=3000
  \def\q{}
  {\bf Input}: \\
  \q ${\cal D}=\{d_{1},d_{2},\ldots,d_{N}\}$: a set of $N$ documents; \\
  \q\\
  {\bf Initialize}: \\
  \q $M_0=\{C_1,C_2,\ldots,C_N\}$: a set of clusters; \\
  \q $C_i = \{d_{i}\}$ for $1 \le i \le N$ \\
  \q calculate $SR(C_i)$ for $1 \le i \le N$ \\
  \q calculate $SR(C_i \cup C_j)$ for $1 \le i < j \le N$ \\
  \q\\
  {\bf for} $k = 1$ {\bf to} $N-1$ {\bf do} \\
  \q $(C_x,C_y) = \arg \max_{C_x,C_y}
	\frac{SR(C_x \cup C_y)}
	{SR(C_x) SR(C_y)}$ \\
  \q $M_k = M_{k-1}-\{C_x,C_y\}+\{C_x \cup C_y\}$\\
  \q calculate $SR(C_x \cup C_z)$
	for all $C_z \in M_k$ where $z \ne x$ \\
  \q\\
  {\bf Function} $SR(C)$ \\
  \q {\bf return} $\prod_{d \in C} P(C|d)$
\end{minipage}
}

\end{document}
