\section{はじめに}
\label{sec:intro}今日，Webからユーザーの望む情報を得る手段としてGoogleなどのサーチエンジンが一般的に利用される．しかし，ユーザーの検索要求に合致しないWebページも多数表示されるため，各ページがユーザーの望む情報を含むかどうかを判断するのに時間と労力を割かなければならない．このような負担を軽減するための検索支援手法として，検索結果をクラスタに分類して表示するWeb文書クラスタリングが挙げられる．Webページのクラスタリング手法として，WebページのHTMLタグの構造\cite{Orihara08}やWebページ間のリンク関係\cite{Ohno06,Wang02}などWebページに特有の情報を用いた手法も提案されているが，Webページの内容（Webページに含まれるテキスト・文章）に基づく手法が一般的であり，多くの手法が提案されている\cite<e.g.,>{Eguchi99,Ferragina05,Hearst96,Hirao06,Narita03,Zamir98}．Webページの内容に基づくクラスタリング手法は，{\bfWebページ間の類似度に基づく手法}と{\bf共通する語句に基づく手法}に大別できる\cite{Fung03}．前者は，ベクトル空間モデルなどを用いて各文書間の（非）類似度を計算し，k-means法などのクラスタリングアルゴリズムを適用する手法である．例えば，最初のWebページクラスタリングシステムと言われているScatter/Gather\cite{Hearst96}や江口らのシステム\cite{Eguchi99}はこの手法を用いている．類似度に基づく手法は文書クラスタリング手法として広く用いられている\cite{Kishida03}が，実時間性が要求される検索結果のクラスタリングにはあまり適していない．Webページ間の類似度を適切に計算するためには，Webページそのものを取得する必要があるが，その取得時間がかかるとともに，文書規模が大きくなると類似度計算にも時間がかかる．よって，サーチエンジンの検索結果をクラスタリングする手法として，Webページ（スニペット）集合に共通して出現する語句に基づく手法が多く用いられている\cite{Ferragina05,Fung03,Hirao06,Narita03,Zamir98}．この手法では，検索結果として得られるページタイトルやスニペットから何らかの方法を用いて基準となる語句を抽出し，それらの語句を含む文書集合をひとつのクラスタとする．一般的に，ひとつのWebページ（スニペット）には複数の頻出語句が含まれるため，この手法は本質的に非排他的なクラスタリング（ひとつの文書を複数のクラスタに割り振ることを許すクラスタリング）を行うことになる．この手法は，タイトルやスニペットの情報のみを用いるために情報の取得時間が短く，文書間の類似度を計算する必要がないために処理時間も短く，ノイズとなる単語が混ざりにくいなどの利点がある．さらに，\citeA{Zamir98}は，スニペットのみの情報を用いたクラスタリングの性能はWebページ全体を用いる場合に比べて遜色ないこと，共通語句に基づくクラスタリング手法がWebページ間の類似度に基づく手法よりも高性能であることを実験的に示している．共通語句に基づく手法で重要となるのが，クラスタのベースとなる語句の抽出手法である．既存研究では，文書頻度\cite{Hirao06,Osinski05,Zamir98}，tfidf\cite{Ferragina05,Zeng04}，検索結果のランキング\cite{Narita03}，語句の長さ\cite{Zamir98,Zeng04}などの情報を用いて語句をランク付けし，上位の語句を選択するという手法が用いられている．しかし，この抽出方法では語句間の意味的な類似関係を考慮していないので，クラスタのベースとなる語句どうしが類似した話題を表していると，同じ文書を多く含む類似したクラスタを出力してしまうという欠点がある．特に，検索結果のWebページ集合には共通する話題が多いことを考えると，この問題点は深刻である．抽出語句からクラスタを作成した後に重複の大きいクラスタをマージする手法\cite<e.g.,>{Zamir98}も考えられているが，話題が似ているからクラスタが重複する場合（ひとつのクラスタとすべきである場合）と，複数の異なる話題が共通しているから重複する場合（別々のクラスタにすべきである場合）かの区別はできない．この問題に対して，本研究では，語句間の意味関係を考慮してクラスタのベースとなる語句を選択することによって，類似したクラスタをできるだけ出力せずにWebページを分類できると考える．さらに，作成されるクラスタに含まれる文書数はその語句の文書頻度と同じであるため，文書頻度が低い語句が重要語として多く選択される場合には，どのクラスタにも属さない文書の数が多くなってしまう．そこで抽出語句を基準にWebページ集合に含まれる単語のクラスタを作成し，単語グループから文書クラスタを作成することによって，どのクラスタにも属さないWebページを減らすことができると考えられる．本論文では，以上の考え方に基づいて，検索結果のスニペットとタイトルから互いに話題が類似しない重要語を抽出し，それらを核とした単語グループを生成し，単語グループに基づいてWebページをクラスタリングする手法を提案する．そして，実際に人手で分類したWebページ群を用いて従来手法（語句間の類似度を考慮しない方法）との比較評価を行い，本手法のほうがクラスタリング性能が高く，かつ類似したクラスタを生成してしまうという従来手法の問題点が解消できることを示す．
\section{単語グループに基づくWeb検索結果のクラスタリング手法}
\label{sec:method}\subsection{概要}\label{subsec:overview}提案する手法の概要は以下の通りである．\begin{enumerate}\itemユーザの入力したクエリを受け取り，Googleによる検索結果のタイトルとスニペットを文書として取得する．本論文の以下では，各ページのタイトルとスニペットをひとつの「文書」と呼ぶ．\item各文書に対して，茶筌(http://chasen-legacy.sourceforge.jp/)を用いて形態素解析を行う．\item形態素解析で名詞・英字と判断された単語から，複合名詞を含む名詞を抽出する．\item抽出した名詞から，クラスタの話題を表すと考えられる互いに類似していない重要語を，指定された文書クラスタ数だけ抽出する．\item手順(3)で抽出されたすべての単語に対して，各重要語から単語グループを生成する．\item単語グループを用いて，文書クラスタを生成する．\end{enumerate}以下の\ref{sec_WM}節から\ref{sec_bun}節では，上記の手順(3)から(6)の各処理の詳細を述べる．\subsection{形態素解析結果からの名詞抽出}\label{sec_WM}まず形態素解析により名詞及び英字と判断された単語を抽出する．この際に，非自立の名詞や代名詞などは除き，英字の連続はひとつの名詞とする．また，各単語$w_i$の文書頻度$df(w_i)$（$w_{i}$を含む文書数）を検索結果の文書集合全体から計算し，一定値$C_W$以下の単語を除外する．さらにクエリ及びクエリの一部となる単語は，ほぼ全ての文書に出現するため，手順(4)の重要語の抽出に大きな影響を及ぼすので除外する．次に，これらの単語から構成される名詞の$n$グラム（複合名詞）を，重要語候補として抽出すべきかどうかを判断する．例えば，文書集合中で「情報」や「検索」という名詞が，ほぼ「情報検索」という複合名詞でしか用いられていない場合には，「情報検索」をひとつの単位として抽出すべきである．また，形態素解析が固有名詞と認識できないために不適切に分解されてしまう固有名詞（例：「エースコック」）を適切に抽出することも意図している．以下の手法により，重要語の候補として抽出すべき（複合名詞を含む）名詞を決定する．\begin{enumerate}\item$\Sigma_1\leftarrow$（すべての単語の集合），$n\leftarrow1$とする．\item$\Sigma_{n+1}\leftarrow\phi$とする．\item集合$\bigcup_{i=1}^n\Sigma_i$中の単語$w_{i}$と，集合$\Sigma_n$中の単語$w_{j}$のすべての組み合わせ（ただし$w_i\neq{w_j}$）に対して，以下の処理を行う．\begin{enumerate}\item2つの単語をつなぎ合わせた語句$w_{i}w_{j}$，$w_{j}w_{i}$のうちで，全文書における出現頻度が高い方を合成候補$Str$とする．ただし，一方の単語がもう一方の単語を部分文字列として含む場合には，合成はせずに長いほうの単語を$Str$とする．\item全文書における$w_{i}$，$w_{j}$及び$Str$の出現頻度（\ref{sec_weight}節の式(\ref{eqn:tf})で定義される）をそれぞれ$tf(w_i)$，$tf(w_i)$，$tf(Str)$としたとき，次式で定義される値$WM$を計算する．\[WM=\frac{tf(Str)}{\max(tf(w_i)，tf(w_j))}\]\item上記で計算した$WM$が閾値$C_{WM}(>0.5)$以上ならば，$\Sigma_{n+1}\leftarrow\Sigma_{n+1}\cup\{Str\}$，$\Sigma_1\leftarrow\Sigma_1-\{w_i\}$，$\Sigma_n\leftarrow\Sigma_n-\{w_j\}$とする．つまり，$w_{i}$，$w_{j}$の代わりに$Str$を複合名詞として用いることになる．\end{enumerate}\item$\Sigma_{n+1}=\phi$ならば，$\Sigma=\bigcup_{i=1}^n\Sigma_i$を複合名詞（重要語候補）の集合として終了する．$\Sigma_{n+1}\neq\phi$ならば，$n$を1増やしてから手順(2)に戻る．\end{enumerate}閾値$C_{WM}$を適切に（0.5より大きく）設定することによって，$w_{i}$や$w_{j}$が単独で出現するよりも複合名詞$Str$として出現することが多い場合に，複合名詞として抽出することができる．なお，本論文の以下では，複合名詞を含む重要語候補（$\Sigma$の要素）のことを単に「名詞」や「単語」と表記する．\subsection{重要語の抽出}\label{sec_weight}前節で得られた名詞集合$\Sigma$から，以下の手順を用いて，重要語を抽出する．\begin{enumerate}\item抽出されたすべての名詞に対して，\ref{subsubsec:weight}節で述べる重み付け手法を用いて，ランク付けする．結果として得られた名詞のランク付きリストを$S$とする．\itemリスト$S$の中でランクの最上位にある名詞を取り出して，重要語とする．\item抽出した重要語との類似度（\ref{subsubsec:cosine}節参照）が基準値$C$以上のすべての名詞をリスト$S$から取り除く．なお，\ref{subsubsec:threshold}節で述べるように，基準値$C$は文書集合に応じて自動的に決定する．\item重要語の個数が指定されたクラスタ数$n$に満たない場合には，手順(2)に戻る．\end{enumerate}上記の手順(3)において，抽出された重要語と話題が類似する名詞を重要語（クラスタのベースとなる語）としないことによって，本手法は重要語どうしの類似度が低くなるように重要語を抽出する．なお，\ref{sec:intro}章で述べた従来の手法は，手順(1)で得られるリスト$S$のランク上位$n$個をクラスタのベースとなる重要語として抽出することに相当する．\subsubsection{名詞の重み付け}\label{subsubsec:weight}上記の手順(1)における名詞の重み付け手法としては，以下の基準が考えられる．なお，\ref{sec:evaluation}章で述べる評価実験では，これらのどの基準を用いても本手法のほうが優れていることを示す．\begin{description}\item[文書頻度df]名詞$w_i$の出現する文書数である$df(w_i)$の値が大きいほど，その名詞が重要であると考える．なお，計算に用いる文書は検索結果の文書集合全体である．\item[出現頻度tf]次式で計算される文書集合中の総出現頻度$tf(w_i)$が高い名詞が重要であると考える．\begin{equation}tf(w_i)=\sum_{j=1}^{N}tf(w_i,d_j)\label{eqn:tf}\end{equation}ただし，$tf(w_i,d_j)$は文書$d_j$における単語$w_i$の出現数，$N$は文書数をそれぞれ表す．\item[tfidf]次式で定義されるtfidf値が高い（特定の文書に多く出現する）名詞が重要であると考える．\begin{align}tfidf(w_{i})&=tf(w_i)\timesidf(w_i)\\idf(w_i)&=log_{2}\left(\frac{N}{df(w_{i})}\right)+1\end{align}\item[SP,LP\cite{Narita03}]次式で定義される$SP(w_i)$もしくは$LP(w_i)$が高い，つまり検索結果のランキング上位の文書に多く含まれる名詞ほど重要であるとする指標である．\begin{align}SP(w_{i})&=\sum_{j=1}^{N}\left[tf(w_{i},d_{j})\timessin\left({\frac{\pi}{1+\sqrt{j}}}\right)\right]\timesidf(w_{i})\\LP(w_{i})&=\sum_{j=1}^{N}\left[tf(w_{i},d_{j})\timeslog_{N}\left(\frac{N}{j}\right)\right]\timesidf(w_{i})\end{align}ただし，$d_j$はサーチエンジン（本研究ではgoogle）の検索結果のランキングが$j$番目の文書を表す．\item[TR\cite{Gelgi07}]$TR(w_i)$は単語をノード，共起の有無をエッジとするグラフのPageRankのように計算される値であり，$TR(w_i)$が高い（つまり重要な）単語と多く共起している単語は重要であると考える指標である．\begin{equation}TR^{(t+1)}(w_i)=\sum_{j=0}^{N}\frac{TR^{(t)}(w_{j})corres(w_i,w_j)}{\sum_{k=0}^{N}corres(w_k,w_j)}\label{eq:TR}\end{equation}ただし，{$corres(w_i,w_j)$}は{$w_i$}と{$w_j$}の共起回数，{$t$}は繰り返し計算回数を表し，{$TR^{(0)}(w_i)=tf(w_i)$}である．\end{description}\subsubsection{名詞どうしの類似度の計算}\label{subsubsec:cosine}上記の手順(3)において，名詞どうしの類似度$sim(w_i,w_j)$（抽出された重要語とリスト$S$に含まれる名詞との類似度）には，次式のコサイン(cos)類似度を用いる．\begin{equation}sim(w_i,w_j)=cos(V_{i},V_{j})=\frac{\sum_{k=1}^{N}{tf(w_i,d_k)\cdottf(w_j,d_k)}}{\sqrt{\sum_{k=1}^{N}tf(w_i,d_k)^2}\sqrt{\sum_{k=1}^{N}tf(w_j,d_k)^2}}\label{eqn:cosine}\end{equation}つまり，名詞$w_i$を，文書$d_k$における出現頻度$tf(w_i,d_k)$を要素とする$N$次元ベクトルで表現したときのコサイン類似度に相当する．\subsubsection{基準値$C$の設定}\label{subsubsec:threshold}基準値$C$が0.05〜0.5（0.05刻み）のいずれかの値をとるものとして，それぞれの値で実際に文書クラスタリングを行い，最も多くの文書を分類できる（つまりどのクラスタにも属さない文書が最も少ない）値を基準値$C$として採用する．ただし抽出した重要語が指定したクラスタ数に満たなかった場合\footnote{\ref{sec_weight}節の手順(3)において，重要語と類似しているとして多くの単語が取り除かれる場合に，このようが現象が生じるときがある．}には，指定したクラスタ数に最も近いものの中での最適値を基準値とする．なお，この判定に用いる文書クラスタリング手法は，\ref{subsec:word_clustering}節で述べる単語グループを用いた方法ではなく，本節で述べた方法で抽出した重要語を含む文書をクラスタとする方法である．\subsection{単語クラスタリング}\label{subsec:word_clustering}前節の方法で得られた重要語に対して，以下のアルゴリズムを用いて単語グループを生成する．\begin{enumerate}\item各重要語$x_i$に対応する単語グループ$WG_i$を以下の方法で生成する．\begin{enumerate}\item重要語$x_i$とのcos類似度（(\ref{eqn:cosine})式）が基準値$C'$以上の名詞（重要語は除く）をリスト$S$からすべて抽出する．\item抽出した名詞集合に対し，重要語$x_i$とのcos類似度の平均値$M$を求める．\item重要語$x_i$とのcos類似度が平均値$M$以上の名詞のみを，その重要語を核とした単語グループ$WG_i$に含める．\end{enumerate}\item複数の単語グループに含まれる名詞を，すべての単語グループから取り除く．\end{enumerate}基準値$C'$は0.05〜0.5（0.05刻み）のいずれかの値をとるものとし，それぞれの値で実際に文書クラスタリングを行い，最も多くの文書を分類できる値を基準値$C'$として採用する．この判別に用いる文書クラスタリング手法は，\ref{sec_bun}節で述べる手法を用いる．\subsection{単語グループからの文書クラスタリング}\label{sec_bun}以下のアルゴリズムを用いて，単語グループから文書クラスタを生成する．\begin{enumerate}\item単語グループ$WG_i\,(i=1,\cdots,n)$に対応する空の文書クラスタ$DC_i=\phi$を生成する．\item以下の方法で，各文書$d_j\,(j=1,\cdots,N)$がどの文書クラスタに含まれるかを決定する．\begin{enumerate}\item文書$d_j$が単語グループ$WG_i$の核となった重要語$x_i$を含んでいれば，文書$d_j$を単語グループに対応する文書クラスタ$DC_i$に含める．（複数の重要語$x_i$を含んでいれば，複数の文書クラスタに属することになる．）\item全ての単語グループ$WG_i$に対し，以下の式で定義される$S_i(d_j)$を計算する．\begin{align}S_i(d_j)&=\frac{\sum_{w_k\in{WG_i}}\delta(w_k,d_j)}{|WG_i|}\\\delta(w_k,d_j)&=\begin{cases}1&\text{（名詞$w_k$が文書$d_j$に出現する場合）}\\0&\text{（名詞$w_k$が文書$d_j$に出現しない場合）}\end{cases}\nonumber\end{align}そして，$S_i(d_j)$の値が以下の不等式を満たすならば，文書$d_j$を文書クラスタ$DC_i$に含める．\begin{equation}S_i(d_j)\geq\frac{1}{2}\sum_{k=1}^nS_k(d_j)>0\end{equation}直観的に言うと，文書$d_j$が他の単語グループよりも単語グループ$CW_i$の単語を多く含んでいれば，その文書は$CW_i$に対応する文書クラスタ$DC_i$に分類されることになる．\end{enumerate}\end{enumerate}
\section{評価実験}
\label{sec:evaluation}\subsection{評価データ}Googleの検索結果を人手により分類したものを評価用の正解データとして用いた．正解データ作成にあたり20代の男女10人に協力を頼んだ．協力者が自由にクエリを入力して，Googleの検索結果上位30件をタイトルとスニペットのみから分類してもらい，15セットの正解データ（平均クラスタ数3.6，最大クラスタ数5，最小クラスタ数2，クラスタに含まれる文書数の平均9.040）を得た．正解データ作成のために協力者が選んだクエリを表{\ref{tab:query}に示す．検索結果を30件としたのは，検索エンジンのユーザの54\%が上位10件以内，73\%が上位20件以内の検索結果しか閲覧しないという調査結果\cite{Jansen03}から，検索結果30件をクラスタリングすることで十分な情報をユーザに与えられると考えたためである．なお，情報の少なさや内容の曖昧さから協力者が分類できないと判断した文書や文書数が1であるクラスタは正解データから除外した．\begin{table}[t]\caption{評価に用いたクエリ}\label{tab:query}\input{03table01.txt}\end{table}\subsection{評価方法}本研究の手法と比較手法のそれぞれを用いて，15セットの評価データのクラスタリングを行い，その性能を比較した．比較手法は，名詞の重み上位順に（\ref{sec_weight}節の概要の(1)のリスト$S$の順に）指定されたクラスタ数だけ重要語を抽出し，重要語を含む文書集合を文書クラスタとするという，\ref{sec:intro}章で述べた従来手法\cite<e.g.,>{Hirao06,Narita03,Zamir98}とした．両手法において，名詞の重み付けには\ref{subsubsec:weight}節の手法を用いた．また，システムが出力するクラスタ（以下，システムクラスタと呼ぶ）の数$n$は各正解データセットのクラスタ数とした．なお，正解クラスタ数より少ない重要語しか抽出できなかった場合には，空のクラスタを出力したとみなして評価を行った．さらに，提案手法によるクラスタリングにおいて，\ref{sec_WM}節における閾値を$C_W=2$，$C_{WM}=0.6$と設定した．\subsection{評価基準}評価基準として，F値，CR(clusteringratio),OR(overlappingratio)を用いる．これらの値はすべて各データセットごとに計算する．クラスタリングの精度を表すF値は以下の手順で求めることができる\cite{Orihara08}．まず，システムクラスタ$SC_i\(1\leqi\leqn)$と正解クラスタ$AC_j\(1\leqj\leqn)$のすべての対に対して，F値$F(SCi,ACj)$を次式で計算する．\begin{align}F(SC_i,AC_j)&=\frac{2\timesR(SC_i,AC_j)\timesP(SC_i,AC_j)}{R(SC_i,AC_j)+P(SC_i,AC_j)}\\R(SC_i,AC_j)&=\frac{|SC_i\capAC_j|}{|AC_j|}\\P(SC_i,AC_j)&=\frac{|SC_i\capAC_j|}{|SC_i|}\end{align}次に，次式の$F(M)$が最大となるようなシステムクラスタと正解クラスタの一対一対応$M$を求め，そのときの値をこのシステムクラスタのF値とする．\begin{equation}F(M)=\sum_{(SC_i,AC_j)\in{M}}\frac{|AC_j|}{\sum_{k=1}^n|AC_k|}\F(SC_i,AC_j)\end{equation}これは，システムクラスタと正解クラスタを2つの頂点集合として，それらの間の枝の重みを$\frac{|AC_j|}{\sum_{k=1}^n|AC_k|}F(SC_i,AC_j)$とする二部グラフの最大マッチング問題を解くことに相当する．CRは文書集合のうちのどれだけの割合の文書をクラスタに分類できるかを表しており，次式で計算される\cite{Narita03}．なお，{$N$}は検索結果の文書数である．\begin{equation}CR=\frac{\displaystyle\left|\bigcup_{i=1}^nSC_i\right|}{N}\end{equation}本研究で扱っている共通の語句に基づくクラスタリング手法では，どのクラスタにも属さない文書が生じてしまう可能性がある．したがってCRが高い（1に近い）ほうが望ましい結果であると言える．ORはクラスタ間で文書が重複する割合の平均であり，次式で計算される．\begin{equation}OR=\frac{1}{{}_n{C}_2}\sum_{i=1}^n\sum_{j=i+1}^n\frac{|SC_i\capSC_j|}{|SC_i\cupSC_j|}\end{equation}この値は単純に低いほど（もしくは高いほど）望ましいというわけではなく，正解クラスタのOR値に近いほうが望ましい結果であると言える．
\section{評価結果と考察}
本章では，\ref{sec:evaluation}章で述べた評価実験について，以下の観点から評価結果を述べるとともに，考察を行う．\begin{itemize}\itemクラスタリングの精度：正しい分類をしているか\itemクラスタリングの被覆度：どのくらいの文書をクラスタリングできるか\itemシステムクラスタ間の類似度：過度に類似したクラスタを出力していないか\item単語グループの必要性：互いに類似していない重要語を抽出するだけでは不十分か\item複合名詞の抽出手法：\ref{sec_WM}節における複合名詞抽出はどの程度影響があるか\end{itemize}なお，以下で示す評価値はすべて各セットごとに求めた値の平均値を用いている．\subsection{クラスタリング精度}\label{subsec:F}クラスタリングの精度を示す評価基準であるF値の結果（全セットの平均値）を表\ref{tab_F}に示す．なお，表\ref{tab_F}（およびこれ以降の表）において，「本手法」の値として「単語グループ無」と「単語グループ有」の2種類の値が示されている．「単語グループ有」の値は，\ref{sec:method}章で述べた提案手法による評価結果を示している．一方，「単語グループ無」の値は「\ref{subsec:overview}節の概要の手順(5)の単語クラスタリング（\ref{subsec:word_clustering}節）を行わず，手順(4)で抽出した重要語を含む文書の集合を文書クラスタとする方法」による評価結果である．つまり，本研究の提案手法と従来手法の中間に位置する手法と言える．単語グループを用いずに文書クラスタリングを行った場合の評価結果を示したのは，\ref{subsec:necessity}節で単語グループの必要性（類似していない重要語の抽出だけで十分かどうか）を検証するためである．\begin{table}[t]\caption{各手法におけるF値}\label{tab_F}\input{03table02.txt}\end{table}表\ref{tab_F}より，全ての重み付け手法において，本手法のF値は従来手法よりも高くなった．また従来手法と本手法（単語グループ有）間で平均値の差の検定を行ったところ，df，tf以外での重み付け手法において有意差が見られた({$p<0.05$})．dfとtfについても平均値の差は有意傾向(df：{$p=0.061$}，tf：{$p=0.067$})となった．この結果から，本手法は従来手法よりもクラスタリング精度が高い（人手に近いクラスタリングを行うのに有効である）と言える．さらに，単語グループを考慮しなくても従来手法より性能が高いことから，\ref{sec_weight}節の重要語の抽出手法そのものも有効であると言える．特に，TRは検索結果を分類するのに有用な(discriminative)単語が上位にランクされやすい指標である\cite{Gelgi07}ので，TRに従来手法を適用しただけで意味的に類似したクラスタを生成しにくくなる可能性がある．しかし，従来手法のTRのF値（0.511）は本手法よりも有意に低い値であることから，この可能性は排除できる．つまり，表\ref{tab_F}の結果は，本研究の手法に基づいて重要語を抽出するほうがTRによるランキングに基づく手法よりも性能が高いことを示している．\subsection{クラスタリングの被覆度}\label{subsec:CR}クラスタの被覆度（クラスタに含まれる文書の割合）を表す評価基準であるCRの結果（全セットの平均値）を表\ref{tab_CR}に示す．表\ref{tab_CR}より，全ての重み付け手法において，本手法のCRは従来手法よりも高くなった．また従来手法と本手法（単語グループ有）間で平均値の差の検定を行ったところ，全ての重み付け手法において有意差が見られた({$p<0.05$})．この結果から，本手法は従来手法よりも多くの文書を分類できると言える．さらに，単語グループを考慮しなくても従来手法よりCRが高いことから，互いに意味的に類似しない単語のみを抽出する本研究の重要語抽出手法そのものがより多くの文書を分類するのに有効であると言える．\begin{table}[t]\caption{各手法におけるCR}\label{tab_CR}\input{03table03.txt}\end{table}\begin{table}[t]\caption{各手法における平均クラスタサイズ}\label{tab_Size}\input{03table04.txt}\end{table}しかし，本研究では非排他的クラスタリングを行っているので，単純により多くの文書をひとつのクラスタに含めてしまえば，つまり，クラスタのサイズを大きくしてしまえば，不適切にCRを高くすることが可能である．そこで，適切なクラスタサイズを保ちつつ本手法のCRが高くなっているかどうかを調べるために，表\ref{tab_Size}に平均クラスタサイズ（各クラスタに含まれる文書数の平均）を示す．表\ref{tab_Size}を見ると，本手法（単語グループ有）のクラスタサイズは従来手法よりは大きくなっているものの，正解データの平均クラスタサイズである9.040を大幅に越えるものはない．（重み付け手法がdfの場合にクラスタサイズが大きくなっているが，これは従来手法と本手法に共通した現象であり，本手法だけが不当にクラスタサイズを大きくしているわけではない．）さらに，単語グループを考慮しない場合には従来手法よりもクラスタサイズが小さくなっている．よって，本手法は，不当にクラスタサイズを大きくせずに，より多くの文書を分類することができると結論づけられる．\subsection{クラスタ間の類似度}\ref{sec:intro}章で述べた，不適切に類似したクラスタを出力してしまうという従来手法の問題点が本手法で解決されているかどうかを評価するために，クラスタ間の重複割合の平均値であるORの結果（全セットの平均値）を表\ref{tab_OR}に示す．全ての重み付け手法において，本手法のORは従来手法よりも低い値であり，正解クラスタの値（0.029）にかなり近くなっている．したがって，本手法は従来手法よりも類似したクラスタを出力しにくく，従来手法の問題点を解決していると言える．\begin{table}[t]\caption{各手法におけるOR}\label{tab_OR}\input{03table05.txt}\vspace{-1\baselineskip}\end{table}\subsection{単語グループの必要性}\label{subsec:necessity}本節では，本手法において単語グループを用いる場合と用いない場合の評価結果を比較することによって，単語グループを用いてクラスタリングすることの必要性を検証する．表\ref{tab_F}と表\ref{tab_CR}から，重み付け手法に関係なく，単語グループを用いたほうが用いないよりもF値，CRともに高いことがわかる．この結果は，単語グループの必要性を支持している．表\ref{tab_Size}のクラスタサイズに注目すると，単語グループを用いない場合には，正解データのクラスタサイズである9.040よりかなり小さいサイズになっている．これは，本研究の重要語抽出方法が出現頻度が低い名詞を抽出しやすいためである．一方，単語グループを用いた本手法のクラスタサイズは正解データのサイズ9.040と同程度である．したがって，出現頻度が低い単語が重要語として抽出された場合でも，単語グループを用いることによって適切なクラスタサイズの文書クラスタを生成できると言える．つまり，クラスタサイズの点からも単語グループが必要であると結論できる．なお，表\ref{tab_OR}のクラスタ間の類似度ORは単語グループの有無による差はほぼなく，単語グループを用いることは類似したクラスタを出力しないという利点そのものには貢献していない．しかし，単語グループを用いない場合と同程度のクラスタ類似度のままで性能（F値，CR）を向上させていることになり，総合的に単語グループの必要性を示しているといえる．\subsection{複合名詞の抽出手法の評価}\label{subsec:marge}本節では，{\ref{sec_WM}}節で述べた複合名詞の抽出手法の性能を評価するために，この抽出手法を用いる場合と用いない場合の評価結果の比較を行う．まず，{\ref{sec_WM}}節の単語合成手法で実際に抽出された複合名詞の例を表{\ref{tab:exe_WN}}に示す．{\ref{sec_WM}}節で意図したように，「情報」や「限定」などの一般的な単語に代わり，「店舗情報」，「限定発売」などの具体的な話題を表す複合名詞が抽出されている．また，形態素解析では複数の名詞に分割されてしまう「綿陽」のような地名や「ブロードバンド」のような専門用語も正しく抽出されている．\begin{table}[b]\caption{単語合成手法で抽出された複合名詞の例（括弧内は形態素解析による区切りを表す）}\label{tab:exe_WN}\input{03table06.txt}\end{table}\begin{table}[b]\caption{複合名詞抽出の有無によるF値の比較}\label{tab:nomarge_F}\input{03table07.txt}\end{table}\begin{table}[b]\caption{複合名詞抽出の有無によるCRの比較}\label{tab:nomarge_CR}\input{03table08.txt}\end{table}次に，複合名詞抽出を行う場合と行わない場合のF値，CR，ORをそれぞれ表{\ref{tab:nomarge_F}}，表{\ref{tab:nomarge_CR}}，表{\ref{tab:nomarge_OR}}に示す．表{\ref{tab:nomarge_F}}より，本手法では全ての重み付け手法で複合名詞抽出を行うほうが行わないよりもF値が高いことがわかる．一方，従来手法では，重み付け手法がLP，TRのときに複合名詞抽出を行うほうがF値が高くなるものの，その他の重み付け手法では同じ値となった．また表{\ref{tab_CR}}と表{\ref{tab_OR}}より，CRとORは従来手法，本手法の全ての重み付け手法においてほぼ同じ結果となった．以上の結果から，複合名詞抽出はクラスタリングの被覆度やクラスタ間の類似度にはあまり影響を与えないが，本手法のクラスタリング精度を向上させる効果があると結論できる．また，語句間の類似度を考慮しない従来方法に対しては，複合名詞抽出はほとんど効果がないと言える．\begin{table}[b]\caption{複合名詞抽出の有無によるORの比較}\label{tab:nomarge_OR}\input{03table09.txt}\end{table}\begin{table}[b]\caption{クエリ「伊右衛門」における重要語，単語グループ，文書クラスタ}\label{tab:exe_iemon}\input{03table10.txt}\end{table}\subsection{生成されたクラスタについて}\label{subsec:qualty}本節では，評価に用いたデータセットに対するクラスタリング結果の実例を示すことによって，本手法を定性的に考察する．表{\ref{tab:exe_iemon}}〜{\ref{tab:exe_choco}}に，いくつかのクエリによる検索結果を本手法でクラスタリングした結果（重要語，単語グループ，文書クラスタ）を示す．表{\ref{tab:exe_iemon}}のクエリ「伊右衛門」による検索結果のクラスタリング例では，3種類のクラスタ（サントリーから発売されている緑茶「伊右衛門」，京極夏彦の小説「嗤う伊右衛門」，「伊右衛門」をタイトルに含むブログ）が生成されているが，これらのクラスタは正解クラスタと一致する．一方，従来手法では，どの重み付け手法でも「ブログ」に関する単語（表{\ref{tab:exe_iemon}}では「日記」）が重要語として抽出されず，代わりに緑茶に関する単語（サントリー，飲料，緑茶など）が重複して重要語として抽出されてしまう．\begin{table}[t]\caption{クエリ「四川」における重要語，単語グループ，文書クラスタ}\label{tab:exe_shisen}\input{03table11.txt}\end{table}\begin{table}[t]\begin{center}\caption{クエリ「チョコボール」における重要語，単語グループ，文書クラスタの例}\label{tab:exe_choco}\input{03table12.txt}\end{table}表{\ref{tab:exe_shisen}}や表{\ref{tab:exe_choco}}の例を見ても，表{\ref{tab:exe_iemon}}と同様に，類似する単語が重要語として選ばれておらず，それらの重要語を核とする単語グループには，同じ話題を表す同義語や関連語（例えば，表{\ref{tab:exe_shisen}}の「地震」から「震源」や「ニュース」）が適切に分類されている．また，表{\ref{tab:exe_choco}}において，重要語「エンゼル」から「金」，「銀」，「確率」といった単語が選ばれ，「金（または銀）のエンゼルが当たる確率に関するページ集合」というように，文書クラスタの内容が推測しやすくなる単語グループも見られる．しかし，「商品」や「サイト」といった広い意味を持つ一般的な単語が単語グループに含まれてしまうために，結果的に文書クラスタの精度が下がってしまう例（表{\ref{tab:exe_shisen}}の「ゲーム」における「サイト」）も見受けられる．
\section{おわりに}
本研究では，サーチエンジンの検索結果としてのWebページ集合をクラスタリングするために，検索結果のスニペットとタイトルから互いに類似していない話題（トピック）を表す重要語を抽出し，それらの重要語を元に文書中の単語をクラスタリングして，それらの単語グループから文書クラスタを生成する手法を提案した．そして，評価実験を通して，重みによるランク上位の単語を単純に取り出してその単語を含む文書をクラスタとする従来手法に比べて，提案手法はクラスタリングの精度，被覆度ともに優れていることを示した．さらに，提案手法によって生成されるクラスタのサイズや重複割合も適切であることを明らかにした．これらの結果は，本研究の提案手法の有効性を示すものである．今後の課題としては，検索支援という観点からは検索結果を階層的にクラスタリングすることが望ましいので，本手法を階層的クラスタリングに応用することである．ひとつの適用方法としては，本手法を用いて生成したクラスタから出発して，それらを凝集もしくは分割していき，階層を生成することが考えられる．また，これに関係して，適切な（初期）クラスタ数をどのように自動に決めるかという課題も残されている．さらに，検索支援の観点からは，生成されたクラスタの内容が何かを示すことも重要であり，そのためのラベル付けや説明文の生成なども興味深い課題である．\bibliographystyle{jnlpbbl_1.5}\begin{thebibliography}{}\bibitem[\protect\BCAY{江口\JBA伊藤\JBA隈元\JBA金田}{江口\Jetal}{1999}]{Eguchi99}江口浩二\JBA伊藤秀隆\JBA隈元昭\JBA金田彌吉\BBOP1999\BBCP.\newblock\JBOQ漸次的に拡張されたクエリを用いた適応的文書クラスタリング法\JBCQ\\newblock\Jem{電子情報通信学会論文誌},{\BbfJ82-D-I}(1),\mbox{\BPGS\140--149}.\bibitem[\protect\BCAY{Ferragina\BBA\Gulli}{Ferragina\BBA\Gulli}{2005}]{Ferragina05}Ferragina,P.\BBACOMMA\\BBA\Gulli,A.\BBOP2005\BBCP.\newblock\BBOQAPersonalizedSearchEngineBasedon{W}eb-SnippetHierarchicalClustering.\BBCQ\\newblockIn{\BemProceedingsofthe14thInternationalWorldWideWebConference(WWW'05)},\mbox{\BPGS\801--810}.\bibitem[\protect\BCAY{Fung,Wang,\BBA\Ester}{Funget~al.}{2003}]{Fung03}Fung,B.,Wang,K.,\BBA\Ester,M.\BBOP2003\BBCP.\newblock\BBOQHierarchicalDocumentClusteringUsingFrequentItemsets.\BBCQ\\newblockIn{\BemProceedingsofthe2003SIAMInternationalConferenceonDataMining},\mbox{\BPGS\59--70}.\bibitem[\protect\BCAY{Gelgi,Davulcu,\BBA\Vadrevu}{Gelgiet~al.}{2007}]{Gelgi07}Gelgi,F.,Davulcu,F.,\BBA\Vadrevu,S.\BBOP2007\BBCP.\newblock\BBOQTermRankingforClusteringWebSearchResults.\BBCQ\\newblockIn{\BemProceedingsofthe10thInternationalWorkshoponWebandDatabases(WebDB2007)}.\bibitem[\protect\BCAY{Hearst\BBA\Pedersen}{Hearst\BBA\Pedersen}{1996}]{Hearst96}Hearst,M.\BBACOMMA\\BBA\Pedersen,J.\BBOP1996\BBCP.\newblock\BBOQReexaminingtheClusterHypothesus:Scatter/GatheronRetrievalResults.\BBCQ\\newblockIn{\BemProceedingsofthe19thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'96)},\mbox{\BPGS\76--84}.\bibitem[\protect\BCAY{Jansen\BBA\Spink}{Jansen\BBA\Spink}{2003}]{Jansen03}Jansen,B.\BBACOMMA\\BBA\Spink,A.\BBOP2003\BBCP.\newblock\BBOQAnAnalysisofWebDocumentsRetrievedandViewed.\BBCQ\\newblockIn{\BemProceedingsofthe4thInternationalConferenceonInternetComputing},\mbox{\BPGS\65--69}.\bibitem[\protect\BCAY{岸田}{岸田}{2003}]{Kishida03}岸田和明\BBOP2003\BBCP.\newblock\JBOQ文書クラスタリングの技法：文献レビュー.\JBCQ\\newblock{\BemLibraryandInformationScience},{\Bbf49},\mbox{\BPGS\33--75}.\bibitem[\protect\BCAY{成田\JBA太田\JBA片山\JBA石川}{成田\Jetal}{2003}]{Narita03}成田宏和\JBA太田学\JBA片山薫\JBA石川博\BBOP2003\BBCP.\newblock\JBOQWeb文書の非排他的クラスタリング手法及びその評価手法.\JBCQ\\newblock\Jem{データベースとWeb情報システムに関するシンポジウム(DBWeb2003)論文集},\mbox{\BPGS\85--92}.\bibitem[\protect\BCAY{大野\JBA渡辺\JBA片山\JBA石川\JBA太田}{大野\Jetal}{2006}]{Ohno06}大野成義\JBA渡辺匡\JBA片山薫\JBA石川博\JBA太田学\BBOP2006\BBCP.\newblock\JBOQMaxFlowアルゴリズムを用いたWebページのクラスタリング方法とその評価.\JBCQ\\newblock\Jem{情報処理学会論文誌：データベース},{\Bbf47}(SIG4(TOD29)),\mbox{\BPGS\65--75}.\bibitem[\protect\BCAY{折原\JBA内海}{折原\JBA内海}{2008}]{Orihara08}折原大\JBA内海彰\BBOP2008\BBCP.\newblock\JBOQHTMLタグを用いたWebページのクラスタリング手法.\JBCQ\\newblock\Jem{情報処理学会論文誌},{\Bbf49}(8),\mbox{\BPGS\2910--2921}.\bibitem[\protect\BCAY{Osi\'nski\BBA\Weiss}{Osi\'nski\BBA\Weiss}{2005}]{Osinski05}Osi\'nski,S.\BBACOMMA\\BBA\Weiss,D.\BBOP2005\BBCP.\newblock\BBOQAconcept-drivenalgorithmforclusteringsearchresults\BBCQ\\newblock{\BemIEEEIntelligentSystems},{\Bbf20}(3),\mbox{\BPGS\48--54}.\bibitem[\protect\BCAY{Wang\BBA\Kitsuregawa}{Wang\BBA\Kitsuregawa}{2002}]{Wang02}Wang,Y.\BBACOMMA\\BBA\Kitsuregawa,M.\BBOP2002\BBCP.\newblock\BBOQEvaluatingContents-linkCoupled{W}ebPageClusteringfor{W}ebSearchResults.\BBCQ\\newblockIn{\BemProceedingsofthe11th{ACM}InternationalConferenceonInformationandKnowledgeManagement(CIKM'02)},\mbox{\BPGS\499--506}.\bibitem[\protect\BCAY{Zamir\BBA\Etzioni}{Zamir\BBA\Etzioni}{1998}]{Zamir98}Zamir,O.\BBACOMMA\\BBA\Etzioni,O.\BBOP1998\BBCP.\newblock\BBOQWebCocumentClustering:AFeasibilityDemonstration.\BBCQ\\newblockIn{\BemProceedingsofthe21stAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'98)},\mbox{\BPGS\46--54}.\bibitem[\protect\BCAY{Zeng,He,Chen,Ma,\BBA\Ma}{Zenget~al.}{2004}]{Zeng04}Zeng,H.,He,Q.,Chen,Z.,Ma,W.,\BBA\Ma,J.\BBOP2004\BBCP.\newblock\BBOQLearningtoCluster{W}ebSearchResults.\BBCQ\\newblockIn{\BemProceedingsofthe27thAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval(SIGIR'04)},\mbox{\BPGS\210--217}.\bibitem[\protect\BCAY{平尾\JBA竹内}{平尾\JBA竹内}{2006}]{Hirao06}平尾一樹\JBA竹内孔一\BBOP2006\BBCP.\newblock\JBOQ複合名詞に着目したWeb検索結果のクラスタリング.\JBCQ\\newblock\Jem{情報処理学会研究報告},{\Bbf2006--NL--175},\mbox{\BPGS\35--42}.\end{thebibliography}\begin{biography}\bioauthor{仁科朋也}{2008年電気通信大学電気通信学部システム工学科卒業．2010年同大学院電気通信学研究科システム工学専攻博士前期課程修了．在学中は自然言語処理の研究に従事．}\bioauthor{内海彰}{1988年東京大学工学部反応化学科卒業．1993年東京大学大学院工学系研究科情報工学専攻博士課程修了．博士（工学）．東京工業大学大学院総合理工学研究科システム科学専攻助手，同研究科知能システム科学専攻専任講師を経て，2000年から電気通信大学電気通信学部システム工学科助教授，2010年より同大学院情報理工学研究科総合情報学専攻准教授となり，現在に至る．言語を中心とした認知科学，認知修辞学，言語情報処理の研究に従事．日本認知科学会，情報処理学会，言語処理学会，人工知能学会，CognitiveScienceSociety等各会員．}\end{biography}\biodate\end{document}