\section{はじめに}
\label{sec:Intro}検索エンジン\textit{ALLTheWeb}\footnote{http://www.alltheweb.com/}において，英語の検索語の約1割が人名を含むという報告\footnote{http://tap.stanford.edu/PeopleSearch.pdf}があるように，人名は検索語として検索エンジンにしばしば入力される．しかし，その検索結果としては，その人名を有する同姓同名人物についてのWebページを含む長いリストが返されるのみである．例えば，ユーザが検索エンジンGoogle\footnote{http://www.google.com/}に``WilliamCohen''という人名を入力すると，その検索結果には，この名前を有する情報科学の教授，アメリカ合衆国の政治家，外科医，歴史家などのWebページが，各人物の実体ごとに分類されておらず，混在している．こうしたWeb検索結果における人名の曖昧性を解消する従来研究の多くは，凝集型クラスタリングを利用している\cite{Mann03}，\cite{Pedersen05}，\cite{Bekkerman-ICML05}，\cite{Bollegala06}．しかし，一般に人名の検索結果では，その上位に，少数の同姓同名だが異なる人物のページが集中する傾向にある．したがって，上位に順位付けされたページを種文書として，クラスタリングを行えば，各人物ごとに検索結果が集まりやすくなり，より正確にクラスタリングができると期待される．以下，本論文では，このような種文書となるWebページを「seedページ」と呼ぶことにする．本研究では，このseedページを用いた半教師有りクラスタリングを，Web検索結果における人名の曖昧性解消のために適用する．これまでの半教師有りクラスタリングの手法は，(1)制約に基づいた手法，(2)距離に基づいた手法，の二つに分類することができる．制約に基づいた手法は，ユーザが付与したラベルや制約を利用し，より正確なクラスタリングを可能にする．例えば，Wagstaffら\cite{Wagstaff00}，\cite{Wagstaff01}の半教師有り$K$-meansアルゴリズムでは，``must-link''（2つの事例が同じクラスタに属さなければならない）と，``cannot-link''（2つの事例が異なるクラスタに属さなければならない）という2種類の制約を導入して，データのクラスタリングを行なう．Basuら\cite{Basu02}もまた，ラベルの付与されたデータから初期の種クラスタを生成し，これらの間に制約を導入する半教師有り$K$-meansアルゴリズムを提案している．また，距離に基づいた手法では，教師付きデータとして付与されたラベルや制約を満たすための学習を必要とする．例えば，Kleinら\cite{Klein02}の研究では，類似した2点$(x_{i},x_{j})$間には``0''，類似していない2点間には$(\max_{i,j}D_{ij})+1$と設定した隣接行列を作成して，クラスタリングを行なう．また，Xingら\cite{Xing03}の研究では，特徴空間を変換することで，マハラノビス距離の最適化を行う．さらに，Bar-Hillelら\cite{Bar-Hillel03}の研究では，適切な特徴には大きな重みを，そうでない特徴には小さな重みを与えるRCA(RelevantComponentAnalysis)\cite{Shental02}により，特徴空間を変換する．一方，我々の提案する半教師有りクラスタリングでは，seedページを含むクラスタの重心の変動を抑える点において，新規性がある．本論文の構成は次のとおりである．\ref{sec:ProposedMethod}章では，我々の提案する新たな半教師有りクラスタリングの手法について説明する．\ref{sec:Experiments}章では，提案手法を評価するための実験結果を示し，その結果について考察する．最後に\ref{sec:Conclusion}章では，本論文のまとめと今後の課題について述べる．
\section{提案手法}
\label{sec:ProposedMethod}\ref{sec:Intro}章で述べた凝集型クラスタリングに基づいた人名の曖昧性解消は，クラスタリングを適切に導いていく基準がないため，正確なクラスタリングを行うことは難しい．一方，これまでに提案されている半教師有りクラスタリングは，クラスタ数$K$をあらかじめ設定する必要がある$K$-meansアルゴリズム\cite{MacQueen67}を改良することを目的としている．しかし，本研究においては，Web検索結果における同姓同名人物の数は，事前にわかっているわけではない．したがって，我々の手法においては，事前にクラスタ数を設定するのではなく，新たに生成されたクラスタと，すでに生成されているクラスタ間の類似度を計算し，これらの値がすべて，あらかじめ設定した閾値よりも小さくなった場合に，クラスタリングの処理を終え，その時点で生成されているクラスタ数を最終的な同姓同名人物の数とする．また，従来の半教師有りクラスタリングアルゴリズムは，制約を導入したり\cite{Wagstaff00}，\cite{Wagstaff01}，\cite{Basu02}，距離を学習したり\cite{Klein02}，\cite{Xing03}，\cite{Bar-Hillel03}することにのみ着目していた．しかし，半教師有りクラスタリングにおいて，より正確なクラスタリング結果を得るためには，seedページ間への制約の導入とともに，seedページを含むクラスタの重心の変動の抑制も重要である．これは，(1)seedページを導入して半教師有りクラスタリングを行なう場合，通常の重心の計算法では重心の変動が大きくなる傾向にあり，クラスタリングの基準となるseedページを導入する効果が得られない，(2)重心を完全に固定して半教師有りクラスタリングを行なう場合，その重心と類似度が高いWebページしかマージされなくなり，多数の独立したクラスタが生成されやすくなる，という二つの考えに基づく．したがって，seedページを含むクラスタの重心の変動を抑えることができれば，より適切なクラスタリングが実現できると期待される．本章では，我々の提案する半教師有りクラスタリングの手法について説明する．以下，検索結果集合$W_{p}$中のWebページ$p_{i}$の特徴ベクトル$\boldsymbol{w}^{p_{i}}$$(i=1,\cdots,n)$を式(\ref{Eq:featurevector_org})のように表す．\begin{equation}\boldsymbol{w}^{p_{i}}=(w_{t_{1}}^{p_{i}},w_{t_{2}}^{p_{i}},\cdots,w_{t_{m}}^{p_{i}})\label{Eq:featurevector_org}\end{equation}ここで，$m$は検索結果集合$W_{p}$における単語の異なり数であり，$t_{k}$$(k=1,2,\cdots,m)$は，各単語を表す．予備実験として，(a)TermFrequency(TF)，(b)InverseDocumentFrequency(IDF)，(c)residualIDF(RIDF)，(d)TF-IDF，(e)$x^{I}$-measure，(f)gainの6つの単語重み付け法を比較した．これらの単語重み付け法は，それぞれ，次のように定義される．\clearpage\noindent\textbf{(a)TermFrequency(TF)}TFは，与えられた文書において，ある単語がどれだけ顕著に出現するかを示し，この値が大きければ大きいほど，その単語が文書の内容をよく表現していることを示す．$tf(t_{k},p_{i})$をWebページ$p_{i}$における単語$t_{k}$の頻度とする．このとき，$\boldsymbol{w}^{p_{i}}$の各要素$w_{t_{k}}^{p_{i}}$は，式(\ref{eq:tf})によって定義される．\begin{eqnarray}w_{t_{k}}^{p_{i}}=\frac{tf(t_{k},p_{i})}{\sum_{s=1}^{m}tf(t_{s},p_{i})}\label{eq:tf}\end{eqnarray}\noindent\textbf{(b)InverseDocumentFrequency(IDF)}\cite{Jones73}によって導入されたIDFは，その単語が出現する文書数が少なければ少ないほど，その単語が出現する文書にとっては，有用であることを示すスコアである．このとき，$\boldsymbol{w}^{p_{i}}$の各要素$w_{t_{k}}^{p_{i}}$は，式(\ref{eq:idf})によって定義される．\begin{eqnarray}w_{t_{k}}^{p_{i}}=\log\frac{N}{df(t_{k})}\label{eq:idf}\end{eqnarray}ここで，$N$はWebページの総数，$df(t_{k})$は単語$t_{k}$が現れるWebページ数である．\noindent\textbf{(c)ResidualInverseDocumentFrequency(RIDF)}ChurchandGale\cite{Church95VLC,Church95JNLE}は，ほとんどすべての単語は，ポアッソンモデルのような独立性に基づいたモデルに応じて，非常に大きなIDFスコアを持つことを示した．また，単語の有用性は，推定されるスコアからは大きな偏差を持つ傾向があるという考えに基づいて導入したスコアがresidualIDFである．このスコアは，実際のIDFとポアッソン分布によって推定されるIDFとの差として定義される．$cf_{k}$を文書集合中における単語$t_{k}$の総出現数，$N$をWebページの総数としたとき，1つのWebページあたりの単語$t_{k}$の平均出現数は，$\lambda_{k}=\frac{cf_{k}}{N}$と表される．このとき，$\boldsymbol{w}^{p_{i}}$の各要素$w_{t_{k}}^{p_{i}}$は，式(\ref{eq:ridf})によって定義される．\begin{align}w_{t_{k}}^{p_{i}}&=IDF-\log\frac{1}{1-p(0;\lambda_{i})}\nonumber\\&=\log\frac{N}{df(t_{k})}+\log(1-p(0;\lambda_{k}))\label{eq:ridf}\end{align}ここで，$p$は，パラメータ$\lambda_{k}$を伴うポアッソン分布である．この手法は，少数の文書のみに出現する単語は，より大きなRIDFスコアを持つ傾向がある．\noindent\textbf{(d)TF-IDF}TF-IDF法\cite{Salton83}は，文書中の単語を重み付けするために，情報検索の研究において広く使われている．TF-IDFは，上述した(a)TFと(b)IDFに基づいて，式(\ref{eq:tfidf})のように定義される．\begin{eqnarray}w_{t_{k}}^{p_{i}}=\frac{tf(t_{k},p_{i})}{\sum_{s=1}^{m}tf(t_{s},p_{i})}\cdot\log\frac{N}{df(t_{k})}\label{eq:tfidf}\end{eqnarray}ここで，$tf(t_{k},p_{i})$と$df(t_{k})$は，それぞれ，Webページ$p_{i}$における単語$t_{k}$の頻度と，単語$t_{k}$が出現するWebページ数を表す．また，$N$はWebページの総数である．\noindent\textbf{(e)$x^{I}$-measure}BooksteinandSwanson\cite{Bookstein74}は，単語$t_{k}$に対する$x^{I}$-measureというスコアを導入した．$tf(t_{k},p_{i})$をWebページ$p_{i}$における単語$t_{k}$の頻度，$df(t_{k})$を単語$t_{k}$が現れるWebページ数とすると，$\boldsymbol{w}^{p_{i}}$の各要素$w_{t_{k}}^{p_{i}}$は，式(\ref{eq:xI})によって定義される．\begin{eqnarray}w_{t_{k}}^{p_{i}}=tf(t_{k},p_{i})-df(t_{k})\label{eq:xI}\end{eqnarray}この手法は，同程度の出現頻度である2つの単語のうち，少数の文書に集中して出現する単語ほど，高いスコアを示す．\noindent\textbf{(f)gain}一般に，IDFは単語の重要性を表すと考えられているが，Papineni\cite{Papineni01}は，IDFは単語の特徴を表す最適な重みに過ぎず，単語の重要性とは異なるものであるため，利得を単語の重要性と考え，gainを提案した．本手法では，$\boldsymbol{w}^{p_{i}}$の各要素$w_{t_{k}}^{p_{i}}$は，式(\ref{eq:gain})によって定義される．\vspace{-0.5\baselineskip}\begin{eqnarray}w_{t_{k}}^{p_{i}}=\frac{df(t_{k})}{N}\left(\frac{df(t_{k})}{N}-1-\log\frac{df(t_{k})}{N}\right)\label{eq:gain}\end{eqnarray}ここで，$df(t_{k})$は，単語$t_{k}$が現れるWebページ数を，$N$はWebページの総数を示す．本手法では，ほとんど出現しない単語と，非常に頻出する単語は，両方とも低いスコアとなり，中頻度の単語は高いスコアとなる．上述した(a)〜(f)の単語重み付け手法の中で，本研究においては，``(f)gain''が最も効果的な単語の重み付け法であることがわかったため，これを本研究における単語の重み付け法として用いる．さらに，クラスタ$C$の重心ベクトル$\boldsymbol{G}^{C}$を式(\ref{Eq:centroidvector})のように定義する．\begin{eqnarray}\boldsymbol{G}^{C}=(g^{C}_{t_{1}},g^{C}_{t_{2}},\cdots,g^{C}_{t_{m}})\label{Eq:centroidvector}\end{eqnarray}ここで，$g^{C}_{t_{k}}$は$\boldsymbol{G}^{C}$における各単語の重みであり，$t_{k}$$(k=1,2,\cdots,m)$は各単語を表す．なお，以下で述べるクラスタリング手法では，2つのクラスタ$C_{i}$，$C_{j}$間の類似度$sim(C_{i},C_{j})$を，式(\ref{eq:sim})によって計算する．\begin{eqnarray}sim(C_{i},C_{j})=\frac{\boldsymbol{G}^{C_{i}}\cdot\boldsymbol{G}^{C_{j}}}{|\boldsymbol{G}^{C_{i}}|\cdot|\boldsymbol{G}^{C_{j}}|}\label{eq:sim}\end{eqnarray}ただし，$\boldsymbol{G}^{C_{i}}$，$\boldsymbol{G}^{C_{j}}$は，それぞれ，クラスタ$C_{i}$，$C_{j}$の重心ベクトルを表す．\subsection{凝集型クラスタリング}\label{subsec:AggCls}凝集型クラスタリングにおいては，はじめに各Webページを，\pagebreak個々のクラスタとして設定する．次に，二つのクラスタ間の類似度が，あらかじめ設定された閾値より小さくなるまで，類似度が最大となる二つのクラスタをマージして新たなクラスタを生成する．図\ref{Fig:AggClsAlgorithm}に凝集型クラスタリングのアルゴリズムを示す．\begin{figure}[b]\begin{center}\includegraphics{16-4ia3f1.eps}\end{center}\caption{凝集型クラスタリングアルゴリズム}\label{Fig:AggClsAlgorithm}\end{figure}このアルゴリズムでは，あるクラスタ$C_{i}$(要素数$n_{i}$)を最も類似したクラスタ$C_{j}$(要素数$n_{j}$)にマージした後の，新たなクラスタ$C^{new}$の重心ベクトル$\boldsymbol{G}^{new}$は，式(\ref{eq:newagg-centroid})のように定義される．\begin{eqnarray}\boldsymbol{G}^{new}=\frac{\sum_{\boldsymbol{w}^{p}\inC_{i}}\boldsymbol{w}^{p}+\sum_{\boldsymbol{w}^{p}\inC_{j}}\boldsymbol{w}^{p}}{n_{i}+n_{j}}\label{eq:newagg-centroid}\end{eqnarray}\subsection{提案する半教師有りクラスタリング}\label{subsec:SSCls}一般に，seedページを含むクラスタ$C_{s_{j}}$と，seedページを含まないクラスタ$C_{i}$の類似度が大きい場合には，両者を新たなクラスタとしてマージすべきであるが，両者の距離が大きい場合には，通常の重心の計算法では，重心の変動が大きくなる傾向にある．そこで，はじめに，あるクラスタ$C_{i}$(重心ベクトル$\boldsymbol{G}^{C_{i}}$)を，seedページを含むクラスタ$C_{s_{j}}$(重心ベクトル$\boldsymbol{G}^{C_{s_{j}}}$)にマージする際，これらのクラスタの重心間の距離$D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}})$に基づいて，Webページ$p$の特徴ベクトル$\boldsymbol{w}^{p}\inC_{i}$を重み付けする．次に，この重み付けした特徴ベクトルを用いて重心の計算を行なうことで上述した傾向を防ぎ，重心の変動を抑える．まず，これまでに$k_{j}$個のクラスタがマージされたseedページを含むクラスタ$C_{s_{j}}^{(k_{j})}$(要素数$n_{s_{j}}$)に対して，クラスタ$C_{i}$(要素数$n_{i}$)が$k_{j}+1$回目にマージされるクラスタであるとする．なお，クラスタ$C_{s_{j}}^{(0)}$の要素は，初期のseedページとなる．\noindent\textbf{(1)}この$C_{s_{j}}^{(k_{j})}$にマージされるクラスタ$C_{i}$に含まれる各要素について，$C_{s_{j}}^{(k_{j})}$の重心$\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}}$と，クラスタ$C_{i}$の重心$\boldsymbol{G}^{C_{i}}$間の距離尺度$D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}})$を用いて，クラスタ$C_{i}$に含まれるWebページの特徴ベクトル$\boldsymbol{w}^{p_{l}}_{C_{i}}$$(l=1,\cdots,n_{i})$を重み付けし，その後に生成されるクラスタを$C_{i'}$(要素数$n_{i'}$)とする．このとき，$C_{i'}$の要素となる重み付けした後のWebページの特徴ベクトル$\boldsymbol{w}^{p_{l}}_{C_{i'}}$は，式(\ref{eq:TransferedCor})で表される．\begin{eqnarray}\boldsymbol{w}^{p_{l}}_{C_{i'}}=\frac{\boldsymbol{w}^{p_{l}}_{C_{i}}}{D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}})+c}\label{eq:TransferedCor}\end{eqnarray}本研究では，$D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}})$として，(i)ユークリッド距離，(ii)マハラノビス距離，(iii)適応的マハラノビス距離，の三つの距離尺度を比較する．また，$c$は$D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}})$が0に非常に近い値となったとき，$\boldsymbol{w}^{p}$の各要素が極端に大きな値となることを防ぐために導入した定数である．この$c$の値の影響については，3.3.1節で述べる．\noindent\textbf{(2)}次に，seedページを含むクラスタ$C_{s_{j}}^{(k_{j})}$(要素数$n_{s_{j}}$)に$C_{i'}$(要素数$n_{i'}$)の要素を追加し，クラスタ$C_{s_{j}}^{(k_{j}+1)}$(要素数$n_{s_{j}}+n_{i'}$)を作成する．\[C_{s_{j}}^{(k_{j}+1)}=\{\boldsymbol{w}^{p_{1}}_{C_{s_{j}}^{(k_{j})}},\cdots,\boldsymbol{w}^{p_{{n}_{s_{j}}}}_{C_{s_{j}}^{(k_{j})}},\boldsymbol{w}^{p_{1}}_{C_{i'}},\cdots,\boldsymbol{w}^{p_{n_{{i'}}}}_{C_{i'}}\}\]\noindent\textbf{(3)}このとき，$k_{j}+1$回目のクラスタをマージしたクラスタ$C_{s_{j}}^{(k_{j}+1)}$の重心$\boldsymbol{G}^{C_{s_{j}}^{(k_{j}+1)}}$は，式(\ref{eq:NewG})のように計算される．ここで，式(\ref{eq:TransferedCor})において，マージされるクラスタの特徴ベクトル$\boldsymbol{w}^{p_{l}}_{C_{i}}$に重み付けをしているため，重み付き平均の計算となるように，$n_{i'}$にも同様の重みを乗じている．\begin{eqnarray}\boldsymbol{G}^{C_{s_{j}}^{(k_{j}+1)}}=\frac{\sum_{\boldsymbol{w}^{p}\inC_{s_{j}}^{(k_{j}+1)}}\boldsymbol{w}^{p}}{n_{{s_{j}}}+n_{i'}\times\frac{1}{D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}^{(k_{j})}})+c}}\label{eq:NewG}\end{eqnarray}このように本研究では，seedページを含むクラスタを重視してクラスタリングの基準を明確にし，正確なクラスタリングを行うことを目的とする．もし，2つのクラスタが種用例を含まないのであれば，新たなクラスタの重心ベクトル$\boldsymbol{G}^{new}$は，式(\ref{eq:newcentroid(agg)})のように計算される．\begin{eqnarray}\boldsymbol{G}^{new}=\frac{\sum_{\boldsymbol{w}^{p}\inC_{i}}\boldsymbol{w}^{p}+\sum_{\boldsymbol{w}^{p}\inC_{j}}\boldsymbol{w}^{p}}{n_{i}+n_{j}}\label{eq:newcentroid(agg)}\end{eqnarray}本研究では，seedページを含むクラスタに，それと最も類似したクラスタをマージする際，seedページを含むクラスタの重心の変動を抑える半教師有りクラスタリングを適用して，Web検索結果における人名の曖昧性を解消する．従来の半教師有りクラスタリングの手法のうち，制約を導入する手法では，クラスタの基準となる重心についての検討は見逃されており，また，距離を学習する手法では，特徴空間が大域的に変換される．一方，我々の手法は，seedページを含むクラスタの重心の変動を抑え，その重心を局所的に調整できる効果が期待される．なお，seedページを導入することで，検索結果を改善することは，適合性フィードバック\cite{Rocchio71}に類似した手法であると考えられる．しかし，適合性フィードバックでは，検索結果中の文書に対して，ユーザが判断した適合文書・非適合文書に基づいた検索語の修正を目的としているのに対し，本手法は，あらかじめ設定したseedページに基づいて，検索結果の改善，特に本研究においては，検索結果のクラスタリング精度の改善を目的としている点が異なる．また，検索結果をクラスタリングする検索エンジンとして，``Clusty''\footnote{http://clusty.com}が挙げられる．しかし，そのクラスタリングされた検索結果には，適合しないWebページが含まれることも多く，クラスタリングを行う上で，何らかの基準が必要である．すなわち，本研究のように，seedページをクラスタリングの基準として導入し，かつ，そのseedページを含むクラスタの重心を抑えることで，その基準を保つような手法が必要であると考えられる．図\ref{Fig:SSClsAlgorithm}に，我々の提案する半教師有りクラスタリングアルゴリズムの詳細を示す．なお，提案する半教師有りクラスタリングでは，対象とするすべてのWebページが，いずれかのseedページを含むクラスタにマージされるのではなく，seedページを含まないクラスタにもマージされることに，注意されたい（図\ref{Fig:SSClsAlgorithm}下から7行目，``elseif''以降参照）．\begin{figure}[p]\begin{center}\includegraphics{16-4ia3f2.eps}\end{center}\caption{提案する半教師有りクラスタリングアルゴリズム}\label{Fig:SSClsAlgorithm}\end{figure}ここで，本研究において比較する式(\ref{eq:TransferedCor})直後に述べた(i)，(ii)，(iii)の3つの距離尺度は，それぞれ，以下のように定義される．\noindent\textbf{(i)ユークリッド距離}式(\ref{eq:TransferedCor})において，ユークリッド距離を導入した場合，seedページを含むクラスタの重心ベクトル$\boldsymbol{G}^{C_{s}}$と，あるクラスタ$C$の重心ベクトル$\boldsymbol{G}^{C}$間の距離$D(\boldsymbol{G}^{C_{s}},\boldsymbol{G}^{C})$は，式(\ref{Eq:centroidvector})に基づいて，式(\ref{Eq:Euclideandisrance})のように定義される．\begin{eqnarray}D(\boldsymbol{G}^{C_{s}},\boldsymbol{G}^{C})=\sqrt{\sum_{k=1}^{m}(g^{C_{s}}_{t_{k}}-g^{C}_{t_{k}})^{2}}\label{Eq:Euclideandisrance}\end{eqnarray}\noindent\textbf{(ii)マハラノビス距離}マハラノビス距離は，データ集合の相関を考慮した尺度であるという点において，ユークリッド距離とは異なる．したがって，ユークリッド距離を用いるよりもマハラノビス距離を用いた方が，クラスタの重心の変動を，より効果的に抑えられることが期待される．式(\ref{eq:TransferedCor})において，マハラノビス距離を導入した場合，seedページを含むクラスタ$C_{s}$の重心ベクトル$\boldsymbol{G}^{C_{s}}$と，あるクラスタ$C$の重心ベクトル$\boldsymbol{G}^{C}$間の距離$D(\boldsymbol{G}^{C_{s}},\boldsymbol{G}^{C})$は，式(\ref{Eq:Mahalanobisdistance})のように定義される．\begin{eqnarray}D(\boldsymbol{G_{C_{(s)}}},\boldsymbol{G_{C}})=\sqrt{(\boldsymbol{G}^{C_{s}}-\boldsymbol{G}^{C})^{T}\boldsymbol{\Sigma}^{-1}(\boldsymbol{G}^{C_{s}}-\boldsymbol{G}^{C})}\label{Eq:Mahalanobisdistance}\end{eqnarray}ここで，$\boldsymbol{\Sigma}$は，seedページを含むクラスタ$C_{s}$の要素によって定義される共分散行列である．すなわち，クラスタ$C_{s}$内の要素を，\[C_{s}=\{\boldsymbol{w}^{p_{1}}_{C_{s}},\boldsymbol{w}^{p_{2}}_{C_{s}},\cdots,\boldsymbol{w}^{p_{m}}_{C_{s}}\}\]と表せば，重心ベクトル$\boldsymbol{G}^{C_{s}}$，\[\boldsymbol{G}^{C_{s}}=\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{w}^{p_{i}}_{C_{s}}\]を用いて，共分散$\Sigma_{ij}$を式(\ref{eq:CovMHD})のように定義することができる．\begin{eqnarray}\Sigma_{ij}=\frac{1}{m}\sum_{i=1}^{m}(\boldsymbol{w}^{p_{i}}_{C_{s}}-\boldsymbol{G}^{C_{s}})(\boldsymbol{w}^{p_{j}}_{C_{s}}-\boldsymbol{G}^{C_{s}})^{T}\label{eq:CovMHD}\end{eqnarray}以上から，共分散行列$\boldsymbol{\Sigma}$は，\[\boldsymbol{\Sigma}=\left[\begin{array}{@{\,}cccc@{\,}}\Sigma_{11}&\Sigma_{12}&\cdots&\Sigma_{1m}\\\Sigma_{21}&\Sigma_{22}&\cdots&\Sigma_{2m}\\\vdots&\vdots&\ddots&\vdots\\\Sigma_{m1}&\Sigma_{m2}&\cdots&\Sigma_{mm}\end{array}\right]\]と表すことができる．\noindent\textbf{(iii)適応的マハラノビス距離}(ii)のマハラノビス距離は，クラスタ内の要素数が少ないときに，共分散が大きくなる傾向がある．そこで，seedページを含むあるクラスタ$C_{s_{j}}$について，このクラスタに含まれるWebページの特徴ベクトル間の非類似度を局所最小化することを考える．この局所最小化で得られる分散共分散行列を用いて計算した$C_{s_{j}}$の重心ベクトル$\boldsymbol{G}^{C_{s_{j}}}$と，このクラスタにマージされるクラスタ$C_{l}$の重心ベクトル$\boldsymbol{G}^{C_{l}}$間の距離が，適応的マハラノビス距離\cite{Diday77}である．この分散共分散行列は，次のように導出される．\noindent\textbf{(1)}まず，クラスタ$C_{s_{j}}$において，このクラスタに含まれるWebページの特徴ベクトル$\boldsymbol{w}^{p_{i}}$と，それ以外の特徴ベクトル$\boldsymbol{v}$$(\boldsymbol{w}^{p_{i}}\neq\boldsymbol{v})$との非類似度$d_{s_{j}}(\boldsymbol{w}^{p_{i}},\boldsymbol{v})$を，式(\ref{eq:intra-cls})により定義する．\begin{eqnarray}d_{s_{j}}(\boldsymbol{w}^{p_{i}},\boldsymbol{v})=(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})^{T}\boldsymbol{M}_{s_{j}}^{-1}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})\label{eq:intra-cls}\end{eqnarray}ただし，$\boldsymbol{M}_{s_{j}}$は$C_{s_{j}}$の分散共分散行列を表す．すなわち，クラスタ$C_{s_{j}}$内の要素を，\[C_{s_{j}}=\{\boldsymbol{w}^{p_{1}}_{C_{s_{j}}},\boldsymbol{w}^{p_{2}}_{C_{s_{j}}},\cdots,\boldsymbol{w}^{p_{m}}_{C_{s_{j}}}\}\]\pagebreakと表せば，重心ベクトル$\boldsymbol{G}^{C_{s_{j}}}$，\[\boldsymbol{G}^{C_{s_{j}}}=\frac{1}{m}\sum_{i=1}^{m}\boldsymbol{w}^{p_{i}}_{C_{s_{j}}}\]を用いて，共分散$M_{ij}$を式(\ref{eq:CovAMHD})のように定義することができる．\begin{eqnarray}M_{ij}=\frac{1}{m}\sum_{i=1}^{m}(\boldsymbol{w}^{p_{i}}_{C_{s_{j}}}-\boldsymbol{G}^{C_{s_{j}}})(\boldsymbol{w}^{p_{j}}_{C_{s_{j}}}-\boldsymbol{G}^{C_{s_{j}}})^{T}\label{eq:CovAMHD}\end{eqnarray}以上から，共分散行列$\boldsymbol{M_{s_{j}}}$は，\[\boldsymbol{M_{s_{j}}}=\left[\begin{array}{@{\,}cccc@{\,}}M_{11}&M_{12}&\cdots&M_{1m}\\M_{21}&M_{22}&\cdots&M_{2m}\\\vdots&\vdots&\ddots&\vdots\\M_{m1}&M_{m2}&\cdots&M_{mm}\end{array}\right]\]と表すことができる．\noindent\textbf{(2)}次に，目的関数\begin{align*}\Delta_{s_{j}}(\boldsymbol{v},\boldsymbol{M}_{s_{j}})&=\sum_{\boldsymbol{w}^{p_{i}}\inC_{s_{j}}}d_{s_{j}}(\boldsymbol{w}^{p_{i}},\boldsymbol{v})\\&=\sum_{\boldsymbol{w}^{p_{i}}\inC_{s_{j}}}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})^{T}\boldsymbol{M}_{s_{j}}^{-1}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})\end{align*}を定義し，これを局所最小化するような$C_{{s}_{j}}$の代表点の特徴ベクトル$\boldsymbol{L}_{s_{j}}$と分散共分散行列$\boldsymbol{S}_{{s}_{j}}$を求める．\noindent(i)まず，クラスタ$C_{s_{j}}$の要素により定義される共分散行列$\boldsymbol{M}_{s_{j}}$を固定し，$\Delta_{s_{j}}$を最小化する$\boldsymbol{L}_{s_{j}}$を求める．\begin{eqnarray}\boldsymbol{L}_{s_{j}}=\arg\min_{\boldsymbol{v}}\sum_{\boldsymbol{w}^{p_{i}}\inC_{s_{j}}}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})^{T}\boldsymbol{M}_{s_{j}}^{-1}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v})\label{eq:Lj}\end{eqnarray}式(\ref{eq:Lj})において，クラスタ$C_{s_{j}}$の重心$G$に最も近い点$G'$の特徴ベクトルを$\boldsymbol{v}_{G'}$と表せば，$\boldsymbol{L}_{s_{j}}=\boldsymbol{v}_{G'}$と求めることができる．\noindent(ii)次に，(i)で求めた代表点の特徴ベクトル$\boldsymbol{L}_{s_{j}}=\boldsymbol{v}_{G'}$を固定する．ここで，$det(\boldsymbol{M}_{s_{j}})=1$のもとで，$\Delta_{s_{j}}$を局所最小化する$\boldsymbol{S}_{s_{j}}$を求める．\begin{eqnarray}\boldsymbol{S}_{s_{j}}=\arg\min_{\boldsymbol{M}_{s_{j}}}\sum_{\boldsymbol{w}^{p_{i}}\inC_{s_{j}}}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v}_{G'})^{T}\boldsymbol{M}_{s_{j}}^{-1}(\boldsymbol{w}^{p_{i}}-\boldsymbol{v}_{G'})\label{eq:dj}\end{eqnarray}この$\boldsymbol{S}_{s_{j}}$は，クラスタ$C_{s_{j}}$の共分散行列$\boldsymbol{M}_{s_{j}}$を用いて，式(\ref{eq:AdpCov})によって与えられることが，文献\cite{Diday77}により示されている．\pagebreak\begin{eqnarray}\boldsymbol{S}_{s_{j}}=(det(\boldsymbol{M}_{s_{j}}))^{1/m}\boldsymbol{M}_{s_{j}}^{-1}\label{eq:AdpCov}\end{eqnarray}ただし，$det(\boldsymbol{M}_{s_{j}})\neq0$であり，$m$は検索結果集合における単語の異なり数を表す．以上から，seedページを含むあるクラスタ$C_{s_{j}}$において，Webページ間の非類似度を局所最小化することを考慮した分散共分散行列$\boldsymbol{S}_{s_{j}}$を求めることができる．この$\boldsymbol{S}_{s_{j}}$を用いて，$C_{s_{j}}$の重心ベクトル$\boldsymbol{G}^{C_{s_{j}}}$と，このクラスタにマージされるべきクラスタ$C_{l}$の重心ベクトル$\boldsymbol{G}^{C_{l}}$間の適応的マハラノビス距離は，式(\ref{Eq:Adapt.Mahalanobisdistance})のように定義される．\begin{eqnarray}D(\boldsymbol{G}^{C_{s_{j}}},\boldsymbol{G}^{C_{l}})=\sqrt{(\boldsymbol{G}^{C_{s_{j}}}-\boldsymbol{G}^{C_{l}})^{T}\boldsymbol{S}_{s_{j}}^{-1}(\boldsymbol{G}^{C_{s_{j}}}-\boldsymbol{G}^{C_{l}})}\label{Eq:Adapt.Mahalanobisdistance}\end{eqnarray}なお，式(\ref{Eq:Adapt.Mahalanobisdistance})は，上述した\textbf{(1)}〜\textbf{(2)}によるクラスタ$C_{s_{j}}$におけるWebページ間の非類似度を考慮して得られた式(\ref{eq:AdpCov})の分散共分散行列$\boldsymbol{S}_{s_{j}}$を適用している点で，式(\ref{Eq:Mahalanobisdistance})とは異なる．
\section{実験}
\label{sec:Experiments}\subsection{実験データ}\label{subsec:ExperimentalData}本研究では，``WebPeopleSearchTask''\cite{Artiles07}において作成された「WePSコーパス」を，実験に用いた．このWePSコーパスは，訓練集合とテスト集合から構成され，それぞれ49，30，合計で79の人名が含まれる．これらは，人名を検索語として，Yahoo!\footnote{http://www.yahoo.com/}の検索APIを通じて得られた上位100件の検索結果から取得されたものである．すなわち，このコーパスは約7,900のWebページから構成される．具体的な統計量を表\ref{tab:WePS-stat}に示す．まず前処理として，このコーパスにおけるすべてのWebページに対して，不要語リスト\footnote{ftp://ftp.cs.cornell.edu/pub/smart/english.stop}に基づいて，不要語を取り除き，PorterStemmer\cite{Porter80}\footnote{http://www.tartarus.org/\~{}martin/PorterStemmer/}を用いて語幹処理を行なった．次に，WePSコーパスの訓練集合を用いて類似したクラスタをマージするための最適なパラメータを決定し，これをWePSコーパスのテスト集合に適用した．\begin{table}[t]\caption{WePSコーパスにおける統計量}\label{tab:WePS-stat}\input{06table01.txt}\end{table}\subsection{評価尺度}\label{subsec:EvaluationMeasure}本研究では，``purity''，``inversepurity''と，これらの調和平均である$F$値\cite{Hotho05}に基づいて，クラスタリングの精度を評価する．これらは，``WebPeopleSearchTask''において採用されている標準的な評価尺度である．以下，生成されたクラスタに割り当てられるべき，人手で定めた正解を「カテゴリ」と呼ぶことにする．``purity''は，各クラスタにおいて最もよく現れるカテゴリの頻度に注目し，ノイズの少ないクラスタを高く評価する．$C$を評価対象となるクラスタの集合，$L$を人手で作成したカテゴリの集合，$n$をクラスタリング対象の文書数とすると，purityは，式(\ref{eq:Purity})に基づいて，最大となる適合率の重み付き平均をとることで計算される．\begin{eqnarray}Purity=\sum_{i}\frac{|C_{i}|}{n}\maxPrecision(C_{i},L_{j})\label{eq:Purity}\end{eqnarray}ここで，あるカテゴリ$L_{j}$に対するクラスタ$C_{i}$の適合率$Precision(C_{i},L_{j})$は，式(\ref{eq:Precision})によって定義される．\begin{eqnarray}Precision(C_{i},L_{j})=\frac{|C_{i}\bigcapL_{j}|}{|C_{i}|}\label{eq:Precision}\end{eqnarray}``inversepurity''は，各カテゴリに対して最大の再現率となるクラスタに着目する．ある一つのクラスタにおいて，各カテゴリで定められた要素を多く含むクラスタを高く評価する．inversepurityは，式(\ref{eq:InvPur})によって定義される．\begin{eqnarray}InversePurity=\sum_{j}\frac{|L_{j}|}{n}\maxRecall(C_{i},L_{j})\label{eq:InvPur}\end{eqnarray}ここで，あるカテゴリ$L_{j}$に対するクラスタ$C_{i}$の再現率$Recall(C_{i},L_{j})$は，式(\ref{eq:Recall})によって定義される．\begin{eqnarray}Recall(C_{i},L_{j})=\frac{|C_{i}\bigcapL_{j}|}{|L_{j}|}\label{eq:Recall}\end{eqnarray}また，purityとinversepurityの調和平均$F$は，式(\ref{eq:F})によって定義される．\begin{eqnarray}F=\frac{1}{\alpha\frac{1}{Purity}+(1-\alpha)\frac{1}{InversePurity}}\label{eq:F}\end{eqnarray}なお，本研究では，$\alpha=0.5$，$0.2$として，評価を行なった．以下，$\alpha=0.5$，$0.2$のときの$F$値を，それぞれ，$F_{0.5}$，$F_{0.2}$と示すことにする．\subsection{実験結果}\label{subsec:ExpResults}我々の提案する半教師有りクラスタリングの手法では，次の2種類のseedページを用いた実験を行なった．\begin{itemize}\item[(a)]Wikipedia\cite{Remy02}における各人物の記事，\item[(b)]Web検索結果において上位に順位付けされたWebページ．\end{itemize}\subsubsection{パラメータ$c$の設定}我々の提案する手法では，seedページを含むクラスタ$C_{s_{j}}$と，それに最も類似したクラスタ$C_{i}$をマージした後の新しいクラスタの重心ベクトルは，\ref{sec:ProposedMethod}章で述べたように，式(\ref{eq:TransferedCor})に基づいてクラスタ$C_{i}$に含まれるWebページの特徴ベクトル$\boldsymbol{w}^{p_{l}}_{C_{i}}$$(l=1,\cdots,n_{i})$を重み付けし，この重み付けした特徴ベクトルを用いて，式(\ref{eq:NewG})によって計算される．式(\ref{eq:TransferedCor})における$c$は，$D(\boldsymbol{G}^{C_{i}},\boldsymbol{G}^{C_{s_{j}}})$が0に非常に近い値となったとき，$\boldsymbol{w}^{p}$の各要素が極端に大きな値となることを防ぐために導入した定数であるが，この値によっては，クラスタリングの精度にも影響が及ぶものと考えられる．そこで，WePSコーパスの訓練集合を用いて，上述した2種類のseedページ(a)，(b)ともに7個までのseedページを用いた場合について，$0.1\lec\le50$として得られるクラスタリング精度について検証した．ここで，seedページの数を7個までと定めたのは，少数のseedページでの効果を確認するためである．この結果，表\ref{Table:CbyEuclidDistance}〜\ref{Table:CbyAdpMahalanobisDistance}に示す$c$の値のときに，$F_{0.5}$，$F_{0.2}$ともに，最良なクラスタリング精度が得られた．\begin{table}[b]\caption{ユークリッド距離を用いたときの最良なクラスタリング精度を与える$c$の値}\label{Table:CbyEuclidDistance}\input{06table02.txt}\end{table}なお，以下の3.3.3節では，距離尺度，seedページの種類とその数，に応じて，表\ref{Table:CbyEuclidDistance}〜\ref{Table:CbyAdpMahalanobisDistance}に示した$c$の値を，WePSコーパスのテスト集合に適用して得られた実験結果を示している．\begin{table}[t]\caption{マハラノビス距離を用いたときの最良なクラスタリング精度を与える$c$の値}\label{Table:CbyMahalanobisDistance}\input{06table03.txt}\end{table}\begin{table}[t]\caption{適応的マハラノビス距離を用いたときの最良なクラスタリング精度を与える$c$の値}\label{Table:CbyAdpMahalanobisDistance}\input{06table04.txt}\end{table}\subsubsection{文書全体を用いた実験結果}\noindent\textbf{(1)凝集型クラスタリングを用いた実験結果}凝集型クラスタリングによって得られた精度を表\ref{Table:AggCls}に示す．\begin{table}[t]\caption{凝集型クラスタリングを用いて得られたクラスタリング精度}\label{Table:AggCls}\input{06table05.txt}\end{table}\noindent\textbf{(2)半教師有りクラスタリングを用いた実験結果}seedページを導入することによる効果を確かめるため，はじめに一つのseedページを用いて実験を行なった．この際，\ref{subsec:ExpResults}節はじめに述べた2種類のseedページに関して，(a)は検索結果の上位にあるWikipediaの記事を，(b)は第1位に順位付けされたWebページを用いた．しかしながら，\ref{subsec:ExperimentalData}節で述べたWePSコーパスのテスト集合におけるすべての人名が，必ずしもWikipediaに対応する記事を有するわけではない．したがって，ある人名がWikipediaに記事を有するのであれば，これをseedページとして用いた．そうでなければ，Web検索結果において第1位に順位付けされたWebページを用いた．この方針に基づき，WePSコーパスのテスト集合における30の人名のうち，16の人名に対してはWikipediaの記事を，14の人名に対しては第1位に順位付けされたWebページをseedページとして用いた．なお，人名の曖昧性解消にWikipediaを利用した最近の研究として，Bunescu\cite{Bunescu06}らは，Wikipediaの構造を用いることによって固有名を同定するとともに，その固有名の曖昧性を解消している．表\ref{Table:OneSeedSSCls}に，一つのseedページでの半教師有りクラスタリングを用いて得られたクラスタリング精度を示す．\begin{table}[b]\hangcaption{1つのseedページを使い，提案する半教師有りクラスタリングを用いて得られたクラスタリング精度}\label{Table:OneSeedSSCls}\input{06table06.txt}\end{table}さらに，一つのseedページを用いた実験において，最も良い$F$値($F_{0.5}=0.68$，$F_{0.2}=0.66$)が得られた適応的マハラノビス距離に関して，seedページの数を変えることによって，さらなる実験を行なった．3.3.1節でも述べたように，少数のseedページでの効果を確認するために，導入するseedページの数は7個までとした．また，図\ref{Fig:SSClsAlgorithm}に示したように，これらのseedページの間には，``cannot-link''の制約を導入している．これは，上位に順位付けされる検索エンジンの出力結果を信頼し，それぞれのWebページが異なる人物について記述していると想定していることに基づく．図\ref{fig:multipleseeds(Wiki)}，\ref{fig:multipleseeds(Web)}は，それぞれ,複数のWikipedia記事，上位7位までに順位付けされたWebページを用いて得られたクラスタリング精度($F$値)を示す．また，この実験では，\ref{sec:ProposedMethod}章で述べたように，seedページを含むクラスタの重心と，それにマージされるクラスタの重心間の距離を考慮する．この提案手法の有効性を確認するために，\ref{sec:Intro}章で述べた距離を学習する半教師有りクラスタリング手法であるKleinら\cite{Klein02}，Xingら\cite{Xing03}，Bar-Hillelら\cite{Bar-Hillel03}の手法を用いて得られた結果との比較を示す．また，seedページを含むクラスタの重心の変動を抑えることによる効果を確認するために，重心を固定する手法との比較も示す．\begin{figure}[t]\begin{center}\includegraphics{16-4ia3f3.eps}\end{center}\caption{複数のseedページを用いて得られたクラスタリング精度(7つまでのWikipedia記事)}\label{fig:multipleseeds(Wiki)}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{16-4ia3f4.eps}\end{center}\hangcaption{複数のseedページを用いて得られたクラスタリング精度(上位7位までに順位付けされたWebページ)}\label{fig:multipleseeds(Web)}\end{figure}\subsubsection{文書を部分的に用いた実験結果}\label{subsec:ExpResults(Fragments)}3.3.2節で述べた実験では，検索結果のWebページとseedページの全文を用いた．しかし，人物について記述されたWebページにおいて，その人物を特徴付ける単語は，人名の周囲にしばしば現れること，また，検索結果のスニペットにおいても，同様の傾向が観察される．そこで，seedページを用いて最も良い結果が得られている場合，すなわち，図\ref{fig:multipleseeds(Wiki)}において，5つのWikipedia記事を用いた場合($F_{0.5}=0.76,F_{0.2}=0.74$)に，さらに精度が改善されるかを確認するために，\begin{itemize}\item[(i)]seedページと検索結果のWebページにおいて，人名前後の単語，および文の数を変化させる，\item[(ii)]検索結果のスニペットを用いる，\end{itemize}実験を行なった．(i)については，まず，WePSコーパスの訓練集合を用いて，最も良い$F$値を与えるseedページと検索結果のWebページのそれぞれにおいて用いる人名前後の単語数，または文数を求める．この結果を図\ref{fig:multipleseeds(Partial)}に示す．次に，これらのパラメータをテスト集合に適用し，評価する．(ii)についても同様に，WePSコーパスの訓練集合を用いて，最も良い$F$値を与えるseedページでの人名前後の単語数，または文数を求める．この結果を図\ref{fig:RsltSnippet}に示す．次に，これらのパラメータをテスト集合に適用し，評価する．最終的に(i)，(ii)の実験によって得られたクラスタリング精度を，表\ref{Table:ResultsByOthers}に示す．\begin{figure}[t]\begin{center}\includegraphics{16-4ia3f5.eps}\end{center}\hangcaption{図\ref{fig:multipleseeds(Wiki)}における5つのseedページ(Wikipedia記事)の場合に,seedページと検索結果のWebページで用いる人名前後の単語数と文数を変化させて得られるクラスタリング精度(``w''と``s''は,それぞれ「単語」と「文」を表す)}\label{fig:multipleseeds(Partial)}\end{figure}\begin{figure}[t]\begin{center}\includegraphics{16-4ia3f6.eps}\end{center}\hangcaption{図\ref{fig:multipleseeds(Wiki)}における5つのseedページ(Wikipedia記事)の場合に，検索結果のスニペットを用い，seedページ中の人名前後の単語数と文数を変化させて得られるクラスタリング精度(``w''と``s''は,それぞれ「単語」と「文」を表す)}\label{fig:RsltSnippet}\end{figure}\subsubsection{他手法との比較}\label{subsec:ComparisonWithOthers}``WebPeopleSearchTask''における上位3チームのクラスタリング精度($F値$)を，表\ref{Table:ResultsByOthers}に示す．なお，これらのチームで採用している手法の詳細については，表\ref{Table:ResultsByOthers}に示した文献を参照されたい．基本的には，凝集型クラスタリングの手法が採用されている．また，提案手法によって得られた結果も，比較のために示す．\begin{table}[t]\caption{WebPeopleSearchTaskにおける上位3チームと提案手法とのクラスタリング精度の比較}\label{Table:ResultsByOthers}\input{06table07.txt}\end{table}\subsection{処理時間に関する検討}\label{subsec:ProcessingTime}3.3.2節で述べたように，式(\ref{eq:TransferedCor})において，適応的マハラノビス距離を用いて，seedページを含むクラスタにマージされるクラスタに含まれるWebページの特徴ベクトルを重み付けし，この変換された特徴ベクトルを用いて重心の計算を行なった場合に，最良なクラスタリング精度が得られることがわかった．この場合について，7つまでのWikipedia記事，上位7位までに順位付けされたWebページをseedページとして用い，最も処理時間を要すると考えられる3.3.2節の文書全体を用いた場合についての処理時間を測定した．なお，提案手法は，PC(CPU:IntelPentiumM・2.0~GHz，Memory:2~GByte，OS:WindowsXP)上にPerlを用いて実装されている．図\ref{fig:time}に，その結果を示す．\begin{figure}[t]\begin{center}\includegraphics{16-4ia3f7.eps}\end{center}\caption{seedページ数を変化させたときのクラスタリングに要する処理時間}\label{fig:time}\end{figure}\subsection{考察}\label{subsec:Discussion}式(\ref{eq:TransferedCor})における$c$の値について，特徴ベクトルを重み付けする際には，表\ref{Table:CbyEuclidDistance}〜\ref{Table:CbyAdpMahalanobisDistance}から$c=0.95$前後の値を用いたときに，最良なクラスタリング精度が得られることがわかった．なお，$5\lec\le50$の大きな値のときには，それほど高いクラスタリング精度が得られないことも観察された．これは，式(\ref{eq:TransferedCor})において，距離尺度よりも$c$が支配的になることにより，クラスタにマージすべきWebページの特徴ベクトルの各要素の値が小さくなりすぎることによる影響であると考えられる．凝集型クラスタリングの手法においては，表\ref{Table:AggCls}から，purity(0.67)は，inversepurity(0.48)よりも高いことがわかる．このように，purityが高いことは，凝集型クラスタリングが，一つの要素しか含まないクラスタを生成する傾向にあることを示す．また，$F$値が$F_{0.5}$=0.52，$F_{0.2}$=0.49であり，それほど高い精度が得られていないことは，凝集型クラスタリングでは，クラスタリングを適切に行なうことが難しいことを改めて確認できたといえる．\ref{sec:ProposedMethod}章で述べた半教師有りクラスタリングの手法において，表\ref{Table:OneSeedSSCls}からpurityの値(0.47〜0.57)は，表\ref{Table:AggCls}の凝集型クラスタリングを用いて得られたpurityの値(0.67)を上回ることができなかったが，inversepurityの値(0.75〜0.88)は，すべての手法が凝集型クラスタリングの値(0.48)を上回っていることがわかる．また，良好なinversepurityの値によって，$F$値においても，良い結果が得られている．これは，seedページを導入したこと，ならびに，そのseedページを含むクラスタの重心の変動を抑えられたことによる効果であると考えられる．さらに，表\ref{Table:OneSeedSSCls}からは，seedページとしてWikipediaの記事を用い，適応的マハラノビス距離を適用した場合において，最も良い$F$値($F_{0.5}=0.68$，$F_{0.2}=0.66$)が得られたことがわかる．複数のseedページを用いた半教師有りクラスタリング手法においては，図\ref{fig:multipleseeds(Wiki)}，\ref{fig:multipleseeds(Web)}から，次の内容が観察される．まず，いずれのseedページを用いても，また，いずれの手法においても，導入する種文書数の増加とともに，クラスタリング精度($F$値)が改善されている．seedページの数について，7個まで導入したが，いずれのseedページとも5個の時点でのクラスタリング精度が最も良いことが観察される．さらに，重心を固定する方法は，他の手法に比べて非常に精度が劣る結果となった．これは，重心を完全に固定してしまうと，その重心と類似度が高いWebページしかマージされなくなるため，本来クラスタにマージされるべきWebページが独立したクラスタとなってしまうことが原因であると考えられる．この実験においては，高いpurityの値が得られていたことからも，上述した原因が裏付けられるといえる．一方，距離を学習するクラスタリング手法では，Bar-Hillelら\cite{Bar-Hillel03}，Xingら\cite{Xing03}，Kleinら\cite{Klein02}の手法の順に良いクラスタリング精度が得られている．\ref{sec:Intro}章で述べたように，Kleinらの手法では，類似した2点($x_{i},x_{j}$)間を0，類似していない2点間を($\max_{i,j}D_{ij}$)+1と設定した単純な隣接行列を作成した上で，クラスタリングを行なうのに対し，Xingら，Bar-Hillelらの方法では，特徴空間を適切に変換する手法が用いられている．後者の二つの手法では，この変換手法が有効に作用しているものと考えられる．しかし，これらの距離を学習する手法と比較しても，重心の変動を抑えたクラスタリングを行なう我々の提案手法が，最も良いクラスタリング精度を示した．これは，あるクラスタをseedページを含むクラスタにマージするたびに，そのseedページを含むクラスタの重心を局所的に調整できることによる効果であると考えられる．さらに，seedページについては，Wikipediaにおける各人物の記事を用いたほうが，Web検索結果の上位に順位付けされたWebページを用いるよりも良い精度が得られた．これは，クラスタリングのためのseedページとして，Wikipediaの記述内容を用いることが有効であることを示す事例であると考えられる．また，文書を部分的に用いた場合には，以下に述べるような傾向が観察される．まず，WePSコーパスの訓練集合において，3.3.3節(i)で述べたように，seedページ，および検索結果のWebページ中の人名前後の単語数または文数を変化させた場合，図\ref{fig:multipleseeds(Partial)}から，検索結果のWebページに関して，単語よりも文を用いることで，より良いクラスタリング精度が得られることが観察される．これは，人名前後の数語のみでは，人物の実体を識別することは難しいが，人名前後の数文を用いることで，その人物を特徴付ける情報を獲得でき，人物の実体を識別しやすくなったことによる効果であると考えられる．また，図\ref{fig:multipleseeds(Partial)}からは，seedページ，検索結果のWebページについて，それぞれ，人名前後の2文，3文を用いた場合に最も良い$F$値($F_{0.5}=0.79$，$F_{0.2}=0.80$)が得られることがわかった．これらの文数をWePSコーパスのテスト集合に適用した場合，[purity:0.80，inversepurity:0.83,$F_{0.5}=0.81$，$F_{0.2}=0.82$]の結果が得られた．特に$F$値は，$\alpha=0.5$のとき，表\ref{Table:ResultsByOthers}に示した``WebPeopleSearchTask''\cite{Artiles07}の第1位のチーム(CU\_COMSEM)の結果を0.03上回り，提案手法が有効であることが確認される．なお，3.3.2節(2)で述べたように，Wikipediaに記事のある16人名のうち，Wikipediaから取得した人名数は10(表\ref{tab:WePS-stat}参照，以下(A)とする)，ACL'06参加者リスト，アメリカ合衆国・国勢調査の人名のうち，Wikipediaにも記事のある人名数は6（表\ref{tab:WePS-stat}参照，以下(B)とする）である．これらの人名について，Wikipediaをseedページとしてクラスタリングした場合に，その精度に差があるか否かを検証した．その結果を表\ref{Table:WikiDetail}に示す．(A)の方が(B)よりも，0.02〜0.04上回る結果が得られているが，それほど大きな差ではない．このことから，seedページとしてWikipediaの記述内容を用いることは，(B)のように他分野から取得した人物のWebページに対しても有効であり，Wikipediaの記述内容の汎用性が特徴付けられる結果であると考えられる．また，クラスタ数については，seedページを導入したことで，このseedページを中心に，Webページのグループが形成され，実際の正解クラスタ数よりも少ない数のクラスタが生成される傾向が観察された．これは，表\ref{Table:ResultsByOthers}において，inversepurityの値が高いことからも裏付けられる．\begin{table}[b]\hangcaption{Wikipediaをseedページとした場合，(A)Wikipediaから取得した10人名と，(B)Wikipediaに記事はあるが，ACL'06参加者リスト，アメリカ合衆国・国勢調査から取得した6人名のクラスタリング精度の比較}\label{Table:WikiDetail}\input{06table08.txt}\end{table}\begin{table}[b]\hangcaption{``WebPeopleSearchTask''の上位3チームが使用した素性を，提案する半教師有りクラスタリングに適用して得られたクラスタリング精度}\label{Table:ClsRsltsbyWePSFeat}\input{06table09.txt}\end{table}なお，``WebPeopleSearchTask''の上位3チームは，凝集型クラスタリングの手法を採用しているが，これらの手法は素性を工夫することで，比較的高い精度を得ている．一方，我々の提案する半教師有りクラスタリングでは，seedページを含むクラスタの重心の変動を抑えることで，表\ref{Table:AggCls}に示した凝集型クラスタリングよりも精度が改善されている．我々が導入した素性は，\ref{sec:ProposedMethod}章で述べたように，gainによって単語を重み付けする簡単なものであるが，``WebPeopleSearchTask''の上位3チームが使用した素性を我々の手法に適用すれば，さらなる精度の向上が期待される．そこで，これらの3チームの素性を，我々の手法で用いた結果を表\ref{Table:ClsRsltsbyWePSFeat}に示す．なお，表\ref{Table:ResultsByOthers}に示した我々の提案手法で得られた最良の結果と比較するため，seedページとしてWikipediaにおける各人物の記事を5つ導入した場合についての比較を行った．まず，CU\_COMSEMについて，表\ref{Table:ResultsByOthers}に示した凝集型クラスタリングの$F$値($F_{0.5}=0.78$，$F_{0.2}=0.83$)と比較して，半教師有りクラスタリングの$F$値も高め($F_{0.5}=0.81$，$F_{0.2}=0.84$)となっている．しかし，$F_{0.5}$で0.03，$F_{0.2}$で0.01程度の改善に過ぎない．これは，文中の単語，URLのトークン，名詞句など，すでに多くの素性を導入しているため，半教師有りクラスタリングを適用しても，それほど効果は得られないことによると考えられる．IRST-BPについては，表\ref{Table:ResultsByOthers}に示した凝集型クラスタリングの$F$値($F_{0.5}=0.75$，$F_{0.2}=0.77$)と比較しても，半教師有りクラスタリングの精度は($F_{0.5}=0.76$，$F_{0.2}=0.81$)であり，改善の程度は$F_{0.5}$で0.01，$F_{0.2}$で0.04であった．このチームが使用している固有名詞，時制表現，人名のある段落で最も良く出現する単語といった素性は，あまり有効な素性ではないと考えられる．PSNUSについては，NE素性をTF-IDFで重み付けしたのみの単純な素性であるが，表\ref{Table:ResultsByOthers}に示した凝集型クラスタリングの$F$値($F_{0.5}=0.75$，$F_{0.2}=0.78$)と比較して，半教師有りクラスタリングで得られた$F$値は$F_{0.5}=0.78$，$F_{0.2}=0.82$であり，$F_{0.5}$で0.03，$F_{0.2}$で0.04の改善が観察される．一方，我々の手法では素性としてgainを用い，表\ref{Table:ResultsByOthers}に示したとおり，$F_{0.5}=0.81$，$F_{0.2}=0.82$の$F$値を得ている．これは，CU\_COMSEMで使用されている多数の素性で得られた$F$値とほぼ同じ値が得られていることから，gainによって単純にWebページ中の単語を重み付けした素性だけでも，我々の提案する半教師有りクラスタリングを適用することで，高い精度が得られることが確認された．また，表\ref{Table:AggCls}に示した凝集型クラスタリングによる$F$値($F_{0.5}=0.52$，$F_{0.2}=0.49$)と比較しても，$F_{0.5}$で0.29，$F_{0.2}$で0.33の改善が観察されたことから，我々の提案する半教師有りクラスタリングの有効性が確認される．次に，WePSコーパスの訓練集合において，3.3.3節(ii)で述べたように，検索結果のスニペットを用い，seedページ中の人名前後の単語数または文数を変化させた場合，図\ref{fig:RsltSnippet}から，seedページ中の人名前後の単語ではなく，同様に文を用いたときに，より良いクラスタリング精度が得られることが観察される．この場合も同様に，人名前後の数語の情報よりも，人名前後の数文を用いることで，その人物を特徴付ける情報が獲得でき，人物の実体が識別しやすくなった効果によるものと考えられる．また，図\ref{fig:RsltSnippet}からは，seedページについて，人名前後の3文を用いた場合に最も良い$F$値($F_{0.5}=0.64$，$F_{0.2}=0.67$)が得られることがわかった．この文数をWePSコーパスのテスト集合に適用した場合，[purity:0.70，inversepurity:0.62，$F_{0.5}=0.66$，$F_{0.2}=0.68$]の結果が得られた．この結果は，WebPeopleSearchTaskの上位3チームの結果，および本研究における他の実験結果と比較して，かなり劣っている．これは，スニペットのような数語程度の情報だけでは，seedページで人名前後の3文という情報を用いたとしても，該当する人物について述べた適切なWebページが，そのseedページには集まらず，結果として，クラスタリング精度が悪くなったことによるためであると考えられる．以上から，提案手法ではWikipediaの記事をseedページとして利用し，人名前後の2文を，また，検索結果のWebページについては人名前後の3文を用いた場合に，良好な検索結果が得られることがわかった．さらに，処理時間に関して，最良なクラスタリング精度が得られた適応的マハラノビス距離の式(\ref{Eq:Adapt.Mahalanobisdistance})における分散共分散行列の計算には，単語数の2乗の計算量が必要となるが，1人名について100件のWebページのクラスタリングを行なうのに，最も多い5つのseedページを用い，seedページと検索結果のWebページの双方ともに文書全体を用いた場合でも，0.8秒余りで処理できることが図\ref{fig:time}から観察され，妥当な応答性を実現できていると考えられる．
\section{むすび}
\label{sec:Conclusion}本論文では，Web検索結果における人名の曖昧性を解消するため，seedページを含むクラスタの重心の変動を抑える半教師有りクラスタリングの手法を提案した．実験の結果，最良な場合において，[purity:0.80，inversepurity:0.83，$F_{0.5}$:0.81，$F_{0.2}$:0.82]の評価値が得られた．今回は，上位に順位付けされる検索エンジンの出力結果が異なることを想定して実験を行った．すなわち，同一人物のseedページ間にも``cannot-link''の制約が導入されている可能性がある．しかし，クラスタが生成される過程で，seedページ以外の人物のページがクラスタ内の要素として支配的になり，最終的には比較的正確なクラスタが生成されることが観察された．同一人物のseedページ間でも，その人物を正確に表現しているページ，そうでないページがあることによるためであると考えられる．したがって，その人物についてより正確に記述されたWebページをseedページとして選択することが，今後の課題の一つとして挙げられる．また，Web検索結果における人名の曖昧性解消の精度を高めるには，その人物を特徴付ける単語の重みが大きくなるように，Webページの特徴ベクトルを作成して，クラスタリングを行なうことが重要である．そのために，特に，seedページの内容に適合する人物のページが集まるように，より的確なseedページの特徴ベクトルを作成するための手法を開発してクラスタリングを行なうことも，今後の課題として挙げられる．\bibliographystyle{jnlpbbl_1.4}\begin{thebibliography}{}\bibitem[\protect\BCAY{Artiles,Gonzalo,\BBA\Sekine}{Artileset~al.}{2007}]{Artiles07}Artiles,J.,Gonzalo,J.,\BBA\Sekine,S.\BBOP2007\BBCP.\newblock\BBOQTheSemEval-2007WePSEvaluation:EstablishingaBenchmarkfortheWebPeopleSearchTask.\BBCQ\\newblockIn{\BemProc.oftheSemeval2007,AssociationforComputationalLinguistics(ACL)},\mbox{\BPGS\64--69}.\bibitem[\protect\BCAY{Bar-Hillel,Hertz,\BBA\Shental}{Bar-Hillelet~al.}{2003}]{Bar-Hillel03}Bar-Hillel,A.,Hertz,T.,\BBA\Shental,N.\BBOP2003\BBCP.\newblock\BBOQLearningDistanceFunctionsUsingEquivalenceRelations.\BBCQ\\newblockIn{\BemProc.ofthe20thInternationalConferenceonMachineLearning(ICML2003)},\mbox{\BPGS\577--584}.\bibitem[\protect\BCAY{Basu,Banerjee,\BBA\Mooney}{Basuet~al.}{2002}]{Basu02}Basu,S.,Banerjee,A.,\BBA\Mooney,R.\BBOP2002\BBCP.\newblock\BBOQSemi-supervisedClusteringbySeeding.\BBCQ\\newblockIn{\BemProc.ofthe19thInternationalConferenceonMachineLearning(ICML2002)},\mbox{\BPGS\27--34}.\bibitem[\protect\BCAY{Bekkerman,El-Yaniv,\BBA\McCallum}{Bekkermanet~al.}{2005}]{Bekkerman-ICML05}Bekkerman,R.,El-Yaniv,R.,\BBA\McCallum,A.\BBOP2005\BBCP.\newblock\BBOQMulti-wayDistributionalClusteringviaPairwiseInteractions.\BBCQ\\newblockIn{\BemProc.ofthe22ndInternationalConferenceonMachineLearning(ICML2005)},\mbox{\BPGS\41--48}.\bibitem[\protect\BCAY{Bollegala,Matsuo,\BBA\Ishizuka}{Bollegalaet~al.}{2006}]{Bollegala06}Bollegala,D.,Matsuo,Y.,\BBA\Ishizuka,M.\BBOP2006\BBCP.\newblock\BBOQExtractingKeyPhrasestoDisambiguatePersonalNamesontheWeb.\BBCQ\\newblockIn{\BemProc.ofthe7thInternationalConferenceonComputationalLinguisticsandIntelligentTextProcessing(CICLing2006)},\mbox{\BPGS\223--234}.\bibitem[\protect\BCAY{Bookstein\BBA\Swanson}{Bookstein\BBA\Swanson}{1974}]{Bookstein74}Bookstein,A.\BBACOMMA\\BBA\Swanson,D.~R.\BBOP1974\BBCP.\newblock\BBOQProbabilisticModelsforAutomaticIndexing.\BBCQ\\newblock{\BemJournaloftheAmericanSocietyforInformationScience},{\Bbf25}(5),\mbox{\BPGS\312--318}.\bibitem[\protect\BCAY{Bunescu\BBA\Pasca}{Bunescu\BBA\Pasca}{2006}]{Bunescu06}Bunescu,R.\BBACOMMA\\BBA\Pasca,M.\BBOP2006\BBCP.\newblock\BBOQUsingEncyclopedicKnowledgeforNamedEntityDisambiguation.\BBCQ\\newblockIn{\BemProc.ofthe11thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguistics(EACL2006)},\mbox{\BPGS\9--16}.\bibitem[\protect\BCAY{Chen\BBA\Martin}{Chen\BBA\Martin}{2007}]{Chen07}Chen,Y.\BBACOMMA\\BBA\Martin,J.\BBOP2007\BBCP.\newblock\BBOQCU-COMSEM:ExploringRichFeaturesforUnsupervisedWebPersonalNameDisambiguation.\BBCQ\\newblockIn{\BemProc.oftheSemeval2007,AssociationforComputationalLinguistics(ACL)},\mbox{\BPGS\125--128}.\bibitem[\protect\BCAY{Church\BBA\Gale}{Church\BBA\Gale}{1995a}]{Church95VLC}Church,K.~W.\BBACOMMA\\BBA\Gale,W.~A.\BBOP1995a\BBCP.\newblock\BBOQInverseDocumentFrequency(IDF):AMeasureofDeviationfromPoisson.\BBCQ\\newblockIn{\BemProc.ofthe3rdWorkshoponVeryLargeCorpora},\mbox{\BPGS\121--130}.\bibitem[\protect\BCAY{Church\BBA\Gale}{Church\BBA\Gale}{1995b}]{Church95JNLE}Church,K.~W.\BBACOMMA\\BBA\Gale,W.~A.\BBOP1995b\BBCP.\newblock\BBOQPoissonMixtures.\BBCQ\\newblock{\BemJournalofNaturalLanguageEngineering},{\Bbf1}(2),\mbox{\BPGS\163--190}.\bibitem[\protect\BCAY{Diday\BBA\Govaert}{Diday\BBA\Govaert}{1977}]{Diday77}Diday,E.\BBACOMMA\\BBA\Govaert,G.\BBOP1977\BBCP.\newblock\BBOQClassificationAutomatiqueAvecDistancesAdaptatives.\BBCQ\\newblock{\BemR.A.I.R.O.InformatiqueComputerScience},{\Bbf11}(4),\mbox{\BPGS\329--349}.\bibitem[\protect\BCAY{Elmacioglu,Tan,Yan,Kan,\BBA\Lee}{Elmaciogluet~al.}{2007}]{Elmacioglu07}Elmacioglu,E.,Tan,Y.~F.,Yan,S.,Kan,M.-Y.,\BBA\Lee,D.\BBOP2007\BBCP.\newblock\BBOQPSNUS:WebPeopleNameDisambiguationbySimpleClusteringwithRichFeatures.\BBCQ\\newblockIn{\BemProc.oftheSemeval2007,AssociationforComputationalLinguistics(ACL)},\mbox{\BPGS\268--271}.\bibitem[\protect\BCAY{Hotho,N{\"{u}}rnberger,\BBA\Paa\ss}{Hothoet~al.}{2005}]{Hotho05}Hotho,A.,N{\"{u}}rnberger,A.,\BBA\Paa\ss,G.\BBOP2005\BBCP.\newblock\BBOQABriefSurveyofTextMining.\BBCQ\\newblock{\BemGLDV-JournalforComputationalLinguisticsandLanguageTechnology},{\Bbf20}(1),\mbox{\BPGS\19--62}.\bibitem[\protect\BCAY{Jones}{Jones}{1973}]{Jones73}Jones,K.~S.\BBOP1973\BBCP.\newblock\BBOQIndexTermWeighting.\BBCQ\\newblock{\BemInformationStrageandRetrieval},{\Bbf9}(11),\mbox{\BPGS\619--633}.\bibitem[\protect\BCAY{Klein,Kamvar,\BBA\Manning}{Kleinet~al.}{2002}]{Klein02}Klein,D.,Kamvar,S.~D.,\BBA\Manning,C.~D.\BBOP2002\BBCP.\newblock\BBOQFromInstance-levelConstraintstoSpace-levelConstraints:MakingtheMostofPriorKnowledgeinDataClustering.\BBCQ\\newblockIn{\BemProc.ofthe19thInternationalConferenceonMachineLearning(ICML2002)},\mbox{\BPGS\307--314}.\bibitem[\protect\BCAY{MacQueen}{MacQueen}{1967}]{MacQueen67}MacQueen,J.\BBOP1967\BBCP.\newblock\BBOQSomeMethodsforClassificationandAnalysisofMultivariateObservations.\BBCQ\\newblockIn{\BemProc.ofthe5thBerkeleySymposiumonMathmaticalStatisticsandProbability},\mbox{\BPGS\281--297}.\bibitem[\protect\BCAY{Mann\BBA\Yarowsky}{Mann\BBA\Yarowsky}{2003}]{Mann03}Mann,G.~S.\BBACOMMA\\BBA\Yarowsky,D.\BBOP2003\BBCP.\newblock\BBOQUnsupervisedPersonalNameDisambiguation.\BBCQ\\newblockIn{\BemProc.ofthe7thConferenceonNaturalLanguageLearning(CoNLL-2003)},\mbox{\BPGS\33--40}.\bibitem[\protect\BCAY{Papineni}{Papineni}{2001}]{Papineni01}Papineni,K.\BBOP2001\BBCP.\newblock\BBOQWhyInverseDocumentFrequency?\BBCQ\\newblockIn{\BemProc.ofthe2ndMeetingoftheNorthAmericanChapteroftheAssociationforComputationalLinguistics(NAACL2001)},\mbox{\BPGS\25--32}.\bibitem[\protect\BCAY{Pedersen,Purandare,\BBA\Kulkarni}{Pedersenet~al.}{2005}]{Pedersen05}Pedersen,T.,Purandare,A.,\BBA\Kulkarni,A.\BBOP2005\BBCP.\newblock\BBOQNameDiscriminationbyClusteringSimilarContexts.\BBCQ\\newblockIn{\BemProc.ofthe6thInternationalConferenceonComputationalLinguisticsandIntelligentTextProcessing(CICLing~2005)},\mbox{\BPGS\226--237}.\bibitem[\protect\BCAY{Popescu\BBA\Magnini}{Popescu\BBA\Magnini}{2007}]{Popescu07}Popescu,O.\BBACOMMA\\BBA\Magnini,B.\BBOP2007\BBCP.\newblock\BBOQIRST-BP:WebPeopleSearchUsingNameEntities.\BBCQ\\newblockIn{\BemProc.oftheSemeval2007,AssociationforComputationalLinguistics(ACL)},\mbox{\BPGS\195--198}.\bibitem[\protect\BCAY{Porter}{Porter}{1980}]{Porter80}Porter,M.~F.\BBOP1980\BBCP.\newblock\BBOQAnAlgorithmforSuffixStripping.\BBCQ\\newblock{\BemProgram},{\Bbf14}(3),\mbox{\BPGS\130--137}.\bibitem[\protect\BCAY{Remy}{Remy}{2002}]{Remy02}Remy,M.\BBOP2002\BBCP.\newblock\BBOQWikipedia:TheFreeEncyclopedia.\BBCQ\\newblock{\BemOnlineInformationReview},{\Bbf26}(6),\mbox{\BPG\434}.\bibitem[\protect\BCAY{Rocchio}{Rocchio}{1971}]{Rocchio71}Rocchio,J.\BBOP1971\BBCP.\newblock\BBOQRelevanceFeedbackinInformationRetrieval.\BBCQ\\newblockInSalton,G.\BED,{\BemTheSmartRetrievalSystem:ExperimentsinAutomaticDocumentProcessing},\mbox{\BPGS\313--323}.Prentice-Hall,EnglewoodCliffs,NJ.\bibitem[\protect\BCAY{Salton\BBA\McGill}{Salton\BBA\McGill}{1983}]{Salton83}Salton,G.\BBACOMMA\\BBA\McGill,M.~J.\BBOP1983\BBCP.\newblock{\BemIntroductiontoModernInformationRetrieval}.\newblockMcGraw-Hill.\bibitem[\protect\BCAY{Shental,Hertz,Weinshall,\BBA\Pavel}{Shentalet~al.}{2002}]{Shental02}Shental,N.,Hertz,T.,Weinshall,D.,\BBA\Pavel,M.\BBOP2002\BBCP.\newblock\BBOQAdjustmentLearningandRelevantComponentAnalysis.\BBCQ\\newblockIn{\BemProc.ofthe7thEuropeanConferenceonComputerVision(ECCV2002)},\mbox{\BPGS\776--792}.\bibitem[\protect\BCAY{Wagstaff\BBA\Cardie}{Wagstaff\BBA\Cardie}{2000}]{Wagstaff00}Wagstaff,K.\BBACOMMA\\BBA\Cardie,C.\BBOP2000\BBCP.\newblock\BBOQClusteringwithInstance-levelConstraints.\BBCQ\\newblockIn{\BemProc.ofthe17thInternationalConferenceonMachineLearning(ICML2000)},\mbox{\BPGS\1103--1110}.\bibitem[\protect\BCAY{Wagstaff,Rogers,\BBA\Schroedl}{Wagstaffet~al.}{2001}]{Wagstaff01}Wagstaff,K.,Rogers,S.,\BBA\Schroedl,S.\BBOP2001\BBCP.\newblock\BBOQConstrainedK-meansClusteringwithBackgroundKnowledge.\BBCQ\\newblockIn{\BemProc.ofthe18thInternationalConferenceonMachineLearning(ICML2001)},\mbox{\BPGS\577--584}.\bibitem[\protect\BCAY{Xing,Ng,Jordan,\BBA\Russell}{Xinget~al.}{2003}]{Xing03}Xing,E.~P.,Ng,A.~Y.,Jordan,M.~I.,\BBA\Russell,S.~J.\BBOP2003\BBCP.\newblock\BBOQDistanceMetricLearningwithApplicationtoClusteringwithSide-Information.\BBCQ\\newblock{\BemAdvancesinNeuralInformationProcessingSystems},{\Bbf15},\mbox{\BPGS\521--528}.\end{thebibliography}\begin{biography}\bioauthor{杉山一成}{1998年横浜国立大学工学部電子情報工学科卒業．2000年同大学院工学研究科電子情報工学専攻博士前期課程修了．KDDI（株）勤務を経て，2004年奈良先端科学技術大学院大学情報科学研究科博士後期課程修了，博士（工学）．（株）日立製作所勤務を経て，2006年東京工業大学精密工学研究所研究員，2009年シンガポール国立大学計算機科学科研究員，現在に至る．情報検索，自然言語処理に関する研究に従事．電子情報通信学会，情報処理学会，人工知能学会，IEEE，ACM，AAAI各会員．}\bioauthor{奥村学}{1984年東京工業大学工学部情報工学科卒業．1989年同大学院博士課程修了．工学博士．同年，東京工業大学工学部情報工学科助手．1992年北陸先端科学技術大学院大学情報科学研究科助教授，2000年東京工業大学精密工学研究所助教授，2009年同教授，現在に至る．自然言語処理，知的情報提示技術，語学学習支援，テキスト評価分析，テキストマイニングに関する研究に従事．電子情報通信学会，情報処理学会，人工知能学会，言語処理学会，認知科学会，計量国語学会，AAAI，ACL各会員．}\end{biography}\biodate\end{document}