\documentstyle[epsf,jnlpbbl]{jnlp_j_b5}

\def\mathbf#1{}

\setcounter{page}{41}
\setcounter{巻数}{10}
\setcounter{号数}{5}
\setcounter{年}{2003}
\setcounter{月}{10}
\受付{2003}{1}{6}
\再受付{2003}{3}{13}
\採録{2003}{7}{22}

\setcounter{secnumdepth}{2}

\title{1次元自己組織化マップを用いた\\高次元データの高速近傍検索}
\author{北 研二\affiref{TU1} \and 獅々堀 正幹\affiref{TU2}}

\headauthor{北，獅々堀}
\headtitle{1次元自己組織化マップを用いた高次元データの高速近傍検索}

\affilabel{TU1}{徳島大学高度情報化基盤センター}
{Center for Advanced Information Technology, The University of Tokushima}
\affilabel{TU2}{徳島大学工学部}
{Faculty of Engineering, The University of Tokushima}

\jabstract{
高次元空間における最近傍検索(nearest neighbor search)は，
マルチメディア・コンテンツ検索，データ・マイニング，パターン認識等の
分野における重要な研究課題の1つである．高次元空間では，ある点の最近点
と最遠点との間に距離的な差が生じなくなるという現象が起こるため，
効率的な多次元インデキシング手法を設計することが極度に困難となる．
本稿では，1 次元自己組織化マップを用いた近似的最近傍検索の手法を提案し，
提案した手法の有効性を類似画像検索と文書検索の2種類の実験により評価する．
自己組織化マップを用いて，高次元空間での近傍関係をできる限り保ちつつ，
高次元データを 1 次元空間へ配置し，1 次元マップから得られる情報で探索範囲
を限定することにより，きわめて高速な最近傍検索が可能となる．
}

\jkeywords{最近傍検索，多次元インデキシング，マルチメディア・コンテンツ検索，自己組織化マップ}

\etitle{Efficient Multidimensional Indexing \\Using One-dimensional
Self-Organizing Maps}
\eauthor{Kenji Kita\affiref{TU1} \and Masami Shishibori\affiref{TU2}} 

\eabstract{
Nearest neighbor search in high dimensional spaces is an interesting
and important problem which is relevant for a wide variety of applications,
including multimedia information retrieval,
data mining, and pattern recognition.
For such applications, the curse of high dimensionality
tends to be a major obstacle in the development of efficient indexing methods.
This paper addresses the problem of designing an efficient multidimensional indexing
structure for high dimensional nearest neighbor search.
More specifically, using self-organizing maps (SOM),
high-dimensional vector data are first transformed into one-dimensional units
while preserving the higher order topology by mapping similar data items
to the same or the neighboring unit.
Then, given a query vector, only data items whose location is
close to the unit location of the query are considered
as candidates.
Experimental results indicate that our scheme scales well
even for a very large number of dimensions.
}

\ekeywords{Nearest neighbor search, Multidimensional indexing, Multimedia contents retrieval,
Self-organizing map}

\begin{document}
\maketitle

\section{はじめに}
\thispagestyle{empty}
計算機の高性能化や記憶容量の大容量化および低価格化にともない，
情報のマルチメディア化が急速に進行しており，このような背景のもと，
マルチメディア・コンテンツに対する情報検索技術の必要性がますます大きくなってきている．
マルチメディア・コンテンツ検索では，マルチメディア情報そのものから得られる
特徴量に基づき類似検索を行なうという内容型検索(content-based retrieval)
が近年の主流であるが，多くの場合，複数の特徴量を多次元ベクトルで表現し，
ベクトル間の距離によりコンテンツ間の類似性を判定している．
たとえば，文書検索の場合には，索引語の重みベクトルで文書や検索質問を
表現することができるし\cite{Salton75,Sasaki01}，
画像の類似検索の場合には，カラーヒストグラム，テクスチャ特徴量，形状特徴量
などから成る特徴量ベクトルにより画像コンテンツを
表現する\cite{Flickner95,Pentland96}．

特徴量ベクトルに基づくコンテンツの類似検索は，
検索質問として与えられたベクトルと距離的に近いコンテンツ・データベース中の
ベクトルを見つけるという最近傍検索(nearest neighbor search)の問題に帰着することができる．
データベース中のベクトルと逐次的に比較する線形探索では，
データベースの規模に比例した計算量が必要となるため，
データベースが大規模化した際の検索システムの処理効率に
深刻な影響を及ぼすことになる．
したがって，最近傍検索を効率的に行なうための多次元インデキシング技術
の開発が重要な課題として，従来より活発に研究されてきた\cite{Katayama01,Gaede98}．

ユークリッド空間における多次元インデキシング手法には，
R-tree \cite{Guttman84}, SS-tree \cite{White96}, SR-tree \cite{Katayama97} など
が提案されており，
また，より一般の距離空間を対象にしたインデキシング手法としては，
VP-tree \cite{Yianilos93}, MVP-tree \cite{Bozkaya99}, M-tree \cite{Ciaccia97} など
が提案されている．
これらのインデキシング手法は，多次元空間を階層的に分割することにより，
探索範囲を限定することを基本としている．
しかし，高次元空間では，ある点の最近点と最遠点との間に距離的な差が生じなく
なるという現象が起こるため\cite{Aggarwal01,Beyer99}，
探索する領域を限定することができず，
線形探索に近い計算量が必要になってしまうという問題点がある．

高次元空間における上記の問題点に対処するために，
近似的な最近傍検索についても研究が進められている．
たとえば，ハッシュ法に基づく近似検索手法\cite{Gionis99}や
空間充填曲線(space-filling curve)を用いて高次元空間の点を索引付けする手法
\cite{Liao00,Shepherd99}などが提案されている．

我々は，現在，テキストと画像のクロスメディア情報検索に関する研究の一環として，
類似画像検索システムを開発しているが
\cite{Koizumi02a,Koizumi02b}，
クロスメディア情報検索では，
ユーザとのインタラクションを通じて所望の検索結果を得ることが多々あるため，
特徴量ベクトルに基づく最近傍検索の実行回数が必然的に多くなってしまう．
このような場合，完全な最近傍検索は必要ではなく，
むしろ高速な近似的最近傍検索のほうが望ましい．

本稿では，1 次元自己組織化マップを用いた，
高速な近似的最近傍検索の手法を提案し，
提案した手法の有効性を類似画像検索と文書検索という2種類の実験により評価する．
最近傍検索を行なう際の一番のボトルネックは，2次記憶上のデータへの
アクセスであるが，提案する手法は，
次元数がきわめて多い場合でも効率的にディスク・アクセスを行なうことが
できるという利点を持っている．


\section{自己組織化マップを用いた最近傍検索}

\subsection{自己組織化マップ}

自己組織化マップ(self-organizing map; SOM)\cite{Kohonen95}は，
教師なし競合学習により，
高次元データを低次元データに写像する2階層型のニューラルネットワークである．
自己組織化マップでは，
高次元空間での近傍関係をできる限り保ちつつ，低次元空間へデータを配置するという
位相的整列性と呼ばれる特徴を持っている．
自己組織化マップの典型的な適用例は，多次元データの可視化であり，
この場合には高次元データを 2 次元平面上に配置するということを行なう\cite{Kohonen00,Oja99}．

図~\ref{Fig:SOM} は，$n$ 次元の入力データを 2 次元平面上に配置する
自己組織化ネットワークの例を示している．
ネットワークの入力層は，2 次元平面上に格子状に配置されたすべてのユニットと
結合されており，各ユニットには，入力層に入力されるデータと同じ次元数の
参照ベクトル(reference vector)が対応している．
学習の過程では，入力層に入力されたベクトルと最も近い参照ベクトルを
持つユニットを探し，このユニットとその近傍にあるユニットの参照ベクトルを
入力ベクトルに近づけるという操作を繰り返す．
このようにして，同じような位相的特徴を持ったユニットが近傍領域に集まり，
結果的に入力データの位相的特徴を反映した自己組織化マップが作られることになる．

自己組織化マップの学習アルゴリズムをまとめると，以下のようになる．
\begin{enumerate}
\item	参照ベクトル $\mathbf{m}_i$ をランダムな値で初期化する．
\item	入力ベクトル $\mathbf{x}$ に最も近い参照ベクトル $\mathbf{m}_c$ を持つ
ユニット $c$ を見つける．
\begin{equation}
\mathbf{m}_c = \mathop{\mbox{argmin}}_{\mathbf{m}_i} || \mathbf{x} - \mathbf{m}_i ||
\end{equation}
\item	ユニット $c$ および $c$ の近傍領域の参照ベクトル$\mathbf{m}_i$ を
次式により更新する．
\begin{equation}
\mathbf{m}_i = \mathbf{m}_i + h_{ci} ( \mathbf{x} - \mathbf{m}_i )
\end{equation}
ここで，$h_{ci}$ はユニット $c$ から離れるにつれ，小さな値になるように設定する．
また，$h_{ci}$ は学習が進むにつれ，単調に減少するようにする．
\item	ステップ 2 より繰り返す．
\end{enumerate}

\begin{figure}
\begin{center}
\epsfile{file=fig01.eps,scale=1.0}
\end{center}
\caption{自己組織化マップ}
\label{Fig:SOM}
\end{figure}

\begin{figure*}[t]
\begin{center}
\epsfile{file=fig02.eps,scale=0.75}
\end{center}
\caption{1 次元自己組織化マップを用いた多次元インデキシング}
\label{Fig:SOMIndexing}
\end{figure*}

\subsection{自己組織化マップを用いた最近傍検索手法}

上で述べたように，自己組織化マップでは，
高次元空間での近傍関係をできる限り保ちつつ，
入力データを低次元空間へ配置することができるという特徴を持っている．
この特徴を用いると，高次元空間での最近傍検索を
低次元空間での最近傍検索問題に置き換えることができると考えられる．
しかし，自己組織化マップの学習には誤差がともなううえ，
低次元のマップ上では，高次元空間での距離が保存されていないため，
低次元マップだけを用いて最近傍検索を行なうことは不可能である．

我々は，自己組織化マップにより得られた低次元空間での近傍関係から，
最近傍検索の探索範囲を限定し，限定されたデータに関してだけ，
元の高次元空間上で距離を計算するという方法を考えた．
また，探索範囲の限定を効率的に行なうことができるように，
1 次元の自己組織化マップを用いることにした．
以下に，1 次元自己組織化マップを用いた最近傍検索手法をまとめる(図~\ref{Fig:SOMIndexing} 参照)．

\vspace*{2mm}
\noindent
{\bf 多次元インデキシングの作成}

\begin{enumerate}
\item	自己組織化マップの学習アルゴリズムにより，
多次元データを 1 次元上に配置する．
ユニット数を $k$ とすると，データは $k$ 個のクラスタに分割されることになる．

\item	各クラスタに属するデータを，2 次記憶上の連続した領域に格納する．
また，この際，1 次元マップ上の各ユニットに 2 次記憶領域へのポインタを持たせる．
なお，2 次記憶領域には，元の多次元データを格納する．
\end{enumerate}

\noindent
{\bf 最近傍検索}

\begin{enumerate}
\item	与えられた検索質問ベクトルに最も近い参照ベクトルを持つユニット $c$ を見つける．

\item	ユニット $c$ の近傍ユニットに配置されたデータに対してのみ，
検索質問との距離計算を行なう．
距離計算の際には，2 次記憶上に格納されている多次元データを用いる．

\item	上記で計算された結果を，距離の小さい順にソートし，
これを最近傍検索の結果として出力する．
\end{enumerate}

\vspace*{2mm}

検索質問ベクトルと距離計算の行なわれるデータは，
2 次記憶上の連続した領域に格納しているため，
2 次記憶へのアクセスはきわめて効率的に行なうことが可能である．
3節で実験結果を述べるが，1 次元マップ上の各ユニットに割り当てられるデータ数が
大きく偏ることはなく，概ね平均化している．
したがって，2 次記憶へのアクセス回数は数回程度である．
なお上記では，1 次元の自己組織化マップを用いたが，
2 次元の自己組織化マップを用いることも可能である．
ただし，2 次元自己組織化マップを用いる場合には，
近傍ユニットに属するデータを必ずしも 2 次記憶上の連続した領域に格納できるとは
限らないため，最近傍検索の手続きが多少複雑になる．

上記で提案した多次元インデキシング手法の本質は，
多次元データのクラスタリングに 1 次元自己組織化マップを用いている点であり，
クラスタ(あるいは近傍クラスタ)内の検索は基本的に線形探索によって行われている．
自己組織化マップ以外にも，他のクラスタリング手法を用いて同様の
インデキシングを行うことも考えられる．
たとえば，主成分分析を用いて第 1 主成分により 1 次元上にデータをマッピングする
こともできるが，主成分分析はデータの分布が正規分布に近い場合には有効であるが，
そうでない場合には自己組織化マップを用いたほうが近似の精度が高いという利点がある．
また，ベクトル量子化は，
ユニット中のセントロイド(コードブック)により入力データを近似するという点で
自己組織化マップに類似しているが，
ベクトル量子化では高次元空間での近傍関係を保つという位相的整列性を
特別に考慮していない．
提案した最近傍検索手法では，検索の際に近傍ユニットを探索することから，
位相的整列性を備えた自己組織化マップを用いた手法のほうが良いと考えられる．


\section{実験結果}

自己組織化マップを用いた最近傍検索手法の有効性を調べるために，
類似画像検索実験と文書検索実験を行なった．
以下で実験の概要および実験結果について述べる．

\subsection{類似画像検索実験}
\label{Sec:ImageRetrieval}

類似画像検索実験では，Corel データベースから抽出した 42,381 件の
カラー写真画像を用いた．
また，このうち，424 件(全体の 1\,\%)の画像データをランダムに抽出し，検索画像とした．
これらの画像データから，表~\ref{Tab:ImageFeatures} に示すような，
次元数の異なる 4 種類の特徴量ベクトルを作成した．

\begin{table*}[t]
\begin{center}
\caption{画像検索実験に用いた特徴量}
\label{Tab:ImageFeatures}
\begin{tabular}{c|r|p{10cm}}
\hline
\hline
特徴量	& 次元数 & \multicolumn{1}{c}{特徴量の概略} \\
\hline
RGB-48  & 48
	& 画像全体から 256 階調の R, G, B のヒストグラムを求め，各色 16 次元(計 48 次元)に圧縮した特徴量 \\
\hline
HSI-192 & 192
	& 画像全体から 256 階調の色相(hue)，彩度(saturation)，輝度(intensity)に関する HSI 特徴量を求め，
各特徴量を 64 次元(計 192 次元)に圧縮した特徴量\\
\hline
HAAR-256 & 256
	& 画像全体の輝度成分に対して 2 レベルの Haar Wavelet 変換を行い，
高域成分の Wavelet 係数を $16 \times 16$ の各部分画像領域ごと(計 256 次元)に加算平均した特徴量\\
\hline
HSI-432	& 432
	& 画像全体を $3 \times 3$ の部分画像に分割し，各部分画像に対して HSI 特徴量を求め，
各部分画像の HSI 特徴量を 48 次元(計 432 次元)に圧縮した特徴量\\
\hline
\end{tabular}
\end{center}
\end{table*}

自己組織化マップを用いた最近傍検索の精度を調べるためには，
検索された画像のうち，どれが正解であるかという情報が必要である．
このため，各検索画像と全画像データとの間のユークリッド距離を線形探索により求め，
距離の小さい 400 件を正解データとした．
与えられた検索画像から，自己組織化マップを用いた最近傍検索により，
上位 400 件の検索結果を出力し，
これを正解データと比較することにより適合率を算出した．

自己組織化マップを用いた最近傍検索では，検索条件によって適合率は変化する．
適合率が変化する主な要因は，
1 次元マップ上の総ユニット数，および，検索の際に用いる近傍数である．
ここで，近傍数とは，探索候補の絞り込みの際にいくつのユニットを参照したかを
意味しており，具体的には，
検索質問の属するユニットに加え，その近傍のユニットをいくつ参照したかを示す．
以下では，検索質問の属するユニットのみを参照したときは近傍数 1，
検索質問の属するユニットに加え，その左右両側のユニットを
参照したときは近傍数 3 というように表すことにする．
なお，近傍数 3 の際，検索質問が 1 次元マップ上の左端(あるいは右端)のユニットに属している場合には，
そのユニットの右側(あるいは左側)しか参照しない．

図~\ref{Fig:ImageResults} は，ユニット数が 10 あるいは 20，近傍数 3 のときの
適合率曲線を示している．
横軸方向は検索結果数を，縦軸方向は平均適合率を表しており，
グラフは上位 $n$ 件の結果が検索された時点での平均適合率をプロットしたものである．
図から分かるように，検索結果数が増えるに連れ平均適合率は単調に減少しており，
次元数が大きほど適合率が減少する度合が大きくなっている．
しかし，ユニット数 10，近傍数 3 およびユニット 20，近傍数 3 のいずれの条件下でも，
上位 100 件程度の近傍検索では，近似解の精度がほぼ 100\,\% に達している．
一方，従来の近似検索手法 \cite{Gionis99,Shepherd99} での実験結果では，
最も次元数が高い 256 次元のデータから近傍検索数 10 件の検索を行うのに，
全データ数の約1割程度の距離計算回数を費やすことで約 90\,\% の近似解の精度が得られたと
報告している．
このことから，他の近似検索手法と比べ，提案手法による検索精度の高さが分かる．

また，表~\ref{Tab:ImageResults} は，
さまざまな条件のもとでの平均 $R$ 適合率
\footnote{
$R$ 適合率($R$-precision)とは，検索質問に適合する結果の総数を $R$ とするとき，
上位から $R$ 番目までの検索結果を出力した時点での適合率を意味する\cite{IRbook}．
$R$ 適合率は，上位に順位付けされた検索結果の有効性を示す評価尺度である．
}
と検索質問 1 件当たりの平均距離計算回数を示している．
表~\ref{Tab:ImageResults} から分かるように，
同じ検索条件のもとでは，
適合率は次元数が大きくなるにつれ低下する傾向にあるが，
距離計算回数は次元数によらずにほぼ一定である．
したがって，本手法は，次元数が増大した場合にも高速性が失われることはない．
なお，距離計算回数が次元数によらず一定である理由は，
各ユニットに割り当てられるデータ数が概ね平均化しているためである．
図~\ref{Fig:UnitNumDat} に，
ユニット数 20 の際に各ユニットに割り当てられたデータ数を示すが，
1 次元マップ上の各ユニットに割り当てられるデータ数が
極端にばらついていないことを読み取ることができる．

また，特徴量ベクトルから 1 次元自己組織化マップに基づく多次元インデキシングを
行うのに要したCPU時間は，ユニット数 10 の場合，
RGB-48 に対しては 525 秒，
HSI-192, HAAR-256, HSI-432 に対してはいずれも 1000 秒程度であり，
次元数の増加にともないインデキシング時間が極端に増加するという
ことはなかった．
なお，今回実験を行ったマシンの OS は Linux，
CPU は Intel Xeon 2.4GHz，主記憶容量は
1,024Kバイトである．


参考のために，各画像特徴量に対する SR-tree の平均距離計算回数を
表~\ref{Tab:SRtree} に示す．
SR-tree では，検索対象データに対する多次元インデクスを
作成する際に多次元空間を木構造を用いて階層的に分割しているが，
検索時には木構造の内部ノードとの距離計算も行うため，
検索対象データ数よりも多くの距離計算が行われることがある．
表~\ref{Tab:SRtree} では，検索対象データとの平均距離計算回数を
括弧内に示している．

表~\ref{Tab:SRtree} から分かるように，
SR-tree の場合には，与えられた検索質問に距離的に近い検索結果を
上位何件求めるかにより距離計算回数が異なるが，
検索件数が増えるに従い距離計算回数は単調に増加する傾向にある．
上位 1 件のみを求める場合には距離計算回数はきわめて少ないが，
それ以外の場合にはいずれの特徴量においても自己組織化マップを
用いた検索よりも計算回数が多くなっている．
実際に類似検索を行う際には，上位 1 件のみの検索結果だけが必要である
ことは稀であると考えられるため，この場合には自己組織化マップを用いた
提案手法のほうが高速な検索を行うことが可能である．

\begin{figure*}
\bigskip
\begin{center}
\epsfile{file=u10.eps,scale=0.75}
\begin{center}
(a) ユニット数 10，近傍数 3
\end{center}
\epsfile{file=u20.eps,scale=0.75}
\begin{center}
(b) ユニット数 20，近傍数 3
\end{center}
\end{center}
\caption{画像検索の平均適合率}
\label{Fig:ImageResults}
\end{figure*}

\begin{table*}
\small
\begin{center}
\caption{画像検索の $R$ 適合率および平均距離計算回数}
\vspace*{2mm}
\label{Tab:ImageResults}

\newcommand{\mrow}[1]{}
\begin{tabular}{c|*{3}{p{17pt}|p{20pt}|p{17pt}|}p{17pt}|p{19pt}|p{17pt}}
\hline
\hline
\multicolumn{1}{c|}{特徴量}
	& \multicolumn{3}{c|}{RGB-48}
	& \multicolumn{3}{c|}{HSI-192}
	& \multicolumn{3}{c|}{HAAR-256}
	& \multicolumn{3}{c}{HSI-432} \\
\hline
\multicolumn{1}{c|}{{\footnotesize ユニット数}}   & \multicolumn{1}{c|}{5} & \multicolumn{1}{c|}{10} & \multicolumn{1}{c|}{20} & \multicolumn{1}{c|}{5} & \multicolumn{1}{c|}{10} & \multicolumn{1}{c|}{20} & \multicolumn{1}{c|}{5} & \multicolumn{1}{c|}{10} & \multicolumn{1}{c|}{20} & \multicolumn{1}{c|}{5} & \multicolumn{1}{c|}{10} & \multicolumn{1}{c}{20} \\
\hline
\multicolumn{1}{c|}{近傍数}       & \multicolumn{1}{c|}{1} & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{1} & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{1} & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c|}{1}  & \multicolumn{1}{c|}{3}  & \multicolumn{1}{c}{3} \\
\hline
$R$適合率	& 0.73 & 0.93 & 0.82 & 0.60 & 0.84 & 0.76 & 0.73 & 0.88 & 0.75 & 0.61 & 0.78 & 0.68 \\
\hline
平均距離 &&&&&&&&&&&&\\
計算回数 
	& \mrow{8940} & \mrow{12226} & \mrow{6211}
	& \mrow{9320} & \mrow{11998} & \mrow{6209}
	& \mrow{8884} & \mrow{11190} & \mrow{6121}
	& \mrow{9005} & \mrow{11528} & \mrow{5989} \\
\hline
\end{tabular}
\end{center}
\end{table*}

\begin{figure*}
\begin{center}
\epsfile{file=numdat.eps,scale=0.8}
\end{center}
\caption{各ユニット中のデータ数}
\label{Fig:UnitNumDat}
\end{figure*}


\begin{table}
\begin{center}
\caption{SR-tree の平均距離計算回数}
\label{Tab:SRtree}
\begin{tabular}{|c|c|c|c|c|}
\hline
    &  RGB-48           & HSI-192           & HAAR-256          & HSI-432 \\
\hline
1   & 153.3 (104.2)     & 79.0 (48.5)       & 613.1 (538.2)     & 283.4 (211.7)\\
5   & 16548.3 (16162.9) & 22048.0 (19966.4) & 41108.7 (37393.8) & 38885.7 (31452.7)\\
10  & 18265.2 (17865.3) & 23985.0 (21830.6) & 41430.0 (37710.9) & 40825.1 (33283.2)\\
50  & 22013.7 (21584.7) & 28387.4 (26084.6) & 42128.2 (38398.3) & 44426.9 (36715.4)\\
100 & 23723.8 (23283.4) & 30425.6 (28060.7) & 42432.8 (38698.2) & 45675.8 (37909.2)\\
200 & 25429.1 (24976.1) & 32530.8 (30104.3) & 42750.1 (39010.7) & 46736.0 (38921.4)\\
\hline
\end{tabular}
\end{center}
\end{table}



\begin{figure*}
\begin{center}
\epsfile{file=IR.eps,scale=0.8}
\end{center}
\caption{文書検索の平均適合率}
\label{Fig:DocResults}
\end{figure*}



\subsection{文書検索実験}

\ref{Sec:ImageRetrieval} において，類似画像検索を対象にした実験結果を示した．
画像特徴量の次元数は，数 10 $\sim$ 数 100 次元程度であるが，
これよりも次元数が大きい場合の手法の有効性を調べるために，
ベクトル空間モデル(vector space model; VSM)に基づく文書検索を対象とした実験を行なった．
なお，文書検索では通常，検索質問中の索引語が現われる文書しか対象にしないため，
転置ファイル\cite{IRbook} に基づく方法が用いられ，この場合には高速な
検索を行うことが可能である．
ここでの実験は，次元数が大きい場合にも提案手法が有効かどうかを
検証することを主な目的として行ったものである．

ベクトル空間モデルでは，文書中から索引語を抽出し，
文書を索引語の出現頻度に基づくベクトルで表現する\cite{IRbook,Salton75}．
文書ベクトルの次元数は，文書集合全体にわたる索引語の総数と等しいため，
次元数はきわめて大きくなる．

本実験では，情報検索評価用のテストコレクションである MEDLINE を用いた．
MEDLINE は，検索対象文書 1,033 文書，検索質問 30 文書から成る
小規模なコレクションであり，各検索質問には，
どの文書が適合しているかという適合情報が用意されている．
なお，各検索質問に対する平均適合文書数は 23.2 文書である．

まず前処理として，MEDLINE コレクションから ``a'' や ``about'' などの
不要語 439 単語，および全文書中に 1 回しか出現しなかった単語を削除した．
その後，ポーター・アルゴリズム(Porter algorithm)\cite{Porter80}によるステミングを
行なった結果，4,329 個の索引語が得られた．
以上の処理により得られた索引語から 4,329 次元の文書ベクトルを構成した．
この際，索引語の重み付けとして，
局所的重み付けには対数化索引語頻度を，
大域的重み付けにはエントロピーを，
文書正規化にはコサイン正規化を用いた\cite{IRbook}．


文書検索の評価では，通常のベクトル空間モデルに基づく最近傍検索(線形探索)と
自己組織化マップを用いた最近傍検索の両者とも 30 件の検索結果を出力し，
出力結果を MEDLINE の適合情報と比較することにより適合率を求めた．
この際，自己組織化マップを用いた最近傍検索では，ユニット数 20，近傍数 3 の
条件で検索を行なった．
図~\ref{Fig:DocResults} に，文書検索の適合率曲線を示すが，
自己組織化マップを用いた検索のほうがわずかながら良い結果を与えている．
なお，ベクトル空間モデルに基づく検索の $R$ 適合率は 0.53 であり，
自己組織化マップを用いた検索の $R$ 適合率は 0.58 であった．
また，自己組織化マップを用いた最近傍検索の平均距離計算回数
は 1 検索質問当たり 141 回であり，これは線形探索の約 1/7 に相当する．

以上は MEDLINE コレクションの適合情報に対する評価であるが，
次に，自己組織化マップによる最近傍検索の近似誤差について述べる．
ベクトル空間モデルの検索結果を正解とみなした場合，
自己組織化マップを用いた検索結果の $R$ 適合率は 0.68 であった．
したがって，上位 30 件までの検索では 32\,\% の近似誤差が生じていることになる．
しかし，近似誤差があるにもかかわらず，
MEDLINE の適合情報に対する評価では，通常のベクトル空間モデルよりも適合率が高くなっている．
潜在的意味インデキシング(latent semantic indexing; LSI)\cite{Berry99}
などによる検索では，次元数を削減すると検索精度が逆に向上することなどから，
高次元空間そのものにおける検索が質的に良い検索結果を与えるとは限らない．
我々の提案した手法の近似の程度と検索精度の関係等を調査することは，
今後の課題である．

\section{おわりに}

本稿では，1 次元自己組織化マップを用いた高次元データの近似的な最近傍検索手法を提案した．
提案した手法では，自己組織化マップを用いて，高次元空間での近傍関係をできる限り保ちつつ，
高次元データを 1 次元マップ上に配置することにより，
最近傍検索の探索範囲を大きく削減することができる．
また，本手法では，実際に距離計算の行なわれるデータは，
2 次記憶上の連続した領域に格納できるため，
2 次記憶へのアクセスを効率的に行なうことができるという大きな利点を持っている．
このため，大規模なデータ集合に対しても，
きわめて高速な最近傍検索を行なうことが可能である．

従来の SR-tree 等の正確な最近傍検索では，
高次元の場合に線形探索に近い計算量が必要となってしまうという問題点があるため，
現実的，応用的な場面においては，
本手法のような高速な近似的最近傍検索のほうが望ましいと考えられる．


\acknowledgment

本研究の実験の一部に協力頂いた修士課程 1 年の原一眞君に感謝する．
また，本研究の一部は，財団法人 放送文化基金の援助によった．


\bibliographystyle{jnlpbbl}
\bibliography{433atari}

\begin{biography}
\biotitle{略歴}
\bioauthor{北 研二}{
昭和56年，早稲田大学理工学部数学科卒業．
昭和58年，沖電気工業(株)入社．
昭和62年，ATR 自動翻訳電話研究所出向．
平成4年，徳島大学工学部講師．
平成5年，同助教授．
平成12年，同教授．
平成14年，同大学高度情報化基盤センター教授．工学博士．
自然言語処理，情報検索等の研究に従事．
平成6年日本音響学会技術開発賞受賞．
著書『確率的言語モデル』(東京大学出版会)，
『情報検索アルゴリズム』(共著，共立出版)など．
}
\bioauthor{獅々堀 正幹}{
平成3年，徳島大学工学部情報工学科卒業．
平成5年，同大学院博士前期課程修了．
平成7年，同大学院博士後期課程退学．
同年，同大学工学部知能情報工学科助手．
現在，同大学工学部知能情報工学科助教授．
博士(工学)．
情報検索，文書処理，自然言語処理の研究に従事．
情報処理学会第45回全国大会奨励賞受賞．
著書『情報検索アルゴリズム』(共著，共立出版)．
電子情報通信学会，情報処理学会会員．
}

\bioreceived{受付}
\biorevised{再受付}
\bioaccepted{採録}

\end{biography}

\end{document}

