    \documentclass[japanese]{jnlp_1.3e}
\usepackage{jnlpbbl_1.1}
\usepackage{amsmath}

\usepackage{graphicx}

\Volume{14}
\Number{5}
\Month{Oct.}
\Year{2007}
\received{2007}{2}{26}
\revised{2007}{4}{7}
\accepted{2007}{5}{24}

\setcounter{page}{107}

\jtitle{NMFによる重み付きハイパーグラフを用いた\\
	アンサンブル文書クラスタリング}
\jauthor{新納　浩幸\affiref{Author_1} \and 佐々木　稔\affiref{Author_1}}
\jabstract{
	本論文では Non-negative Matrix Factorization (NMF) を利用したアンサン
ブル文書クラスタリングを提案する．

NMF は次元縮約を利用したクラスタリング手法であり，文書クラスタリングの
ようにデータが高次元かつスパースとなる場合に効果を発揮する．ただし NMF
は初期値によって得られるクラスタリング結果が異なるという問題がある．
そのために通常は初期値を様々に変えて，複数個得られたクラスタリング結果から，NMF の分解の精度
の最もよい結果を選択する．しかし NMF の分解の精度はクラスタリング結果の精度を直
接表しているわけではないので，最適な選択が行える保証はない．

ここでは NMF によるクラスタリングの精度を高めるために，
複数個得られたクラスタリング結果をアンサンブルすることを試みる．
アンサンブルは，複数個のクラスタリング結果からハイパーグラフを作成し，そのハイパーグラフ
で表現されたデータをクラスタリングすることで行える．従来，そのハイパーグラフ
は 0 か 1 のバイナリ値が用いられていたが，ここでは NMF の結果を用いて，適
切な実数値の重みを与えることで改良する．実験では k-means，NMF，通常のハイ
パーグラフを用いたアンサンブル手法および重み付きハイパーグラフを用いたア
ンサンブル手法（本手法）のクラスタリング結果を比較し，本手法の有効性を
示す．
}
\jkeywords{アンサンブルクラスタリング，NMF，ハイパーグラフ，局所解，アンサンブル学習}

\etitle{Ensemble Document Clustering Using Weighted Hypergraph Generated by NMF}
\eauthor{Hiroyuki Shinnou\affiref{Author_1} \and Minoru Sasaki\affiref{Author_1}} 
\eabstract{
	In this paper, we propose a new ensemble clustering method using
Non-negative Matrix Factorization (NMF).

NMF is a kind of the dimensional reduction method which is effective
for high dimensional and sparse data like document data.  
NMF has the problem that the result depends on the initial value of
the iteration.  The standard countermeasure for this problem is that
we generate multiple clustering results by changing the initial value,
and then select the best clustering result estimated by 
the NMF decomposition error.  However, this selection does not work well because 
the NMF decomposition error does not always measure the accuracy of the clustering.

To improve the clustering result of NMF, we propose a new ensemble clustering
method.  Our method generates multiple clustering results by using the
random initialization of NMF.  And they are integrated through the
weighted hypergraph, which can directly be constructed through the result
of NMF, instead of the traditional binary hypergraph.

In the experiment, we compared the k-means, NMF, the ensemble method
using the standard hypergraph and the ensemble method using the weighted
hypergraph (our method).  Our method achieved best.
}
\ekeywords{ensemble clustering, NMF, hypergraph, local optimum solution, ensemble learning}

\headauthor{新納，佐々木}
\headtitle{NMFによる重み付きハイパーグラフを用いたアンサンブル文書クラスタリング}

\affilabel{Author_1}{茨城大学工学部情報工学科}{Department of Computer and Information Sciences, Ibaraki University}

\begin{document}
\maketitle


\section{はじめに}


本論文では，ランダムな初期値を使ってNon-negative Matrix Factorization (NMF) による
文書クラスタリングを複数回行い，それらの結果をアンサンブルすることで，
より精度\footnote{本論文において用いる「（クラスタリングの）精度」とは，
クラスタリングの正解率(accuracy)と同義である．
つまり，ここでは暗にクラスタリングの正解があることを想定しており，
得られた結果がどの程度正解に近いかという尺度の意味で
「（クラスタリングの）精度」という用語を用いる．}
の高い文書クラスタリングの実現を目指す．
複数のクラスタリング結果を統合する部分で，従来のハイパーグラフの代わりに
重み付きハイパーグラフを用いることが特徴である．

文書クラスタリングは，文書の集合に対して，知的な処理を行う基本的な処理であり，
その重要性は明らかである．例えばテキストマイニングの分野では，
文書クラスタリングは基本的な構成要素であるし\cite{TextMiningBook}，
情報検索の分野では，検索結果の概観を視覚化するために
検索された文書の集合をクラスタリングする研究が盛んに行われている
\cite{hearst96reexamining}\cite{leuski01evaluating}\cite{zeng-learning}\cite{kummamuruwww2004}．

文書クラスタリングでは，まずデータとなる文書をベクトルで表現する．
通常，bag of words のモデルを用い，次に TF-IDF などによって次元の重みを調整する．
このようにして作成されたベクトルは高次元かつスパースになるために，
文書クラスタリングではクラスタリング処理を行う前に主成分分析や特異値分解などの
次元縮約の手法を用いることが行われる\cite{boley99document}\cite{deerwester90indexing}．
次元縮約により高次元のベクトルが構造を保った状態で低次元で表現されるため，
クラスタリング処理の速度や精度が向上する．

NMF は次元縮約の手法を応用したクラスタリング手法である\cite{nmf}．
今，クラスタリング対象の\( m \)次元で表現された\( n \)個の文書を\( m \)行\( n \)列の
索引語文書行列\( X \)で表す．
目的とするクラスタの数が\( k \)である場合，NMF では\( X \)を以下のような
行列\( U \)と\( V^{T} \)に分解する．そして行列\( V \)がクラスタリング結果に対応する．
\[
X = U V^{T}    
\]
ここで\( U \)は\( m \)行\( k \)列，\( V \)は\( n \)行\( k \)列である．
\( V^{T} \)は\( V \)の転置を表す．また\( U \)と\( V \)の要素は非負である．

与えられた\( X \)と\( k \)から，ある繰り返し処理により
\( U \)と\( V \)を得ることができる\cite{lee00algorithms}．
しかしこの繰り返し処理は局所最適解にしか収束しない．
つまり NMF では，与える初期値によって得られるクラスタリング結果が異なるという問題がある．
通常は適当な初期値を与える実験を複数回行い，
それらから得た複数個のクラスタリング結果の中で
\( X \) と \( U V^{T} \) の差\footnote{差は\( || X - U V^{T} ||_{F} \) により測定する．}
が最小のもの，つまり\( X \)の分解の精度が最も高いものを選ぶ．
しかし分解の精度は，直接的にはクラスタリングの精度を意味してはいないため，
最も精度の高いクラスタリング結果を選択できる保証がない．

ここでは NMF の分解の精度を用いて，複数個のクラスタリング結果から最終的なクラスタリング結果を
選ぶのではなく，複数個のクラスタリング結果をアンサンブルさせて，
より精度の高いクラスタリング結果を導くアンサンブルクラスタリングを試みる．

一般にアンサンブルクラスタリングの処理は2段階に分けられる．
まず第1段で複数個のクラスタリング結果を生成し，
次の第2段でそれらを組み合わせ，最終的なクラスタリング結果を導く．
複数個のクラスタリング結果を生成する手法としては，
k-means の初期値を変化させたり\cite{fred02data}，
ランダムプロジェクションにより利用する特徴を変化させたり\cite{fern_clustensem03}，
``weak partition'' を生成する研究などがある\cite{topchy03combining}．  
また複数個のクラスタリング結果を組み合わせる手法としては，
データ間の類似度を新たに構築する手法\cite{fred02data}や，
データの表すベクトルを新たに構築する手法\cite{strehl02}などがある．
ここでは後者の手法を改良して用いる．

論文\cite{strehl02}では，データの表すベクトルを新たに構築するために，
複数個のクラスタリング結果から，データセットに対するハイパーグラフを作成する．
このハイパーグラフは，データセットが表す行列に相当する．
このハイパーグラフで表現されたデータに対してクラスタリングを行い，
最終的なクラスタリング結果を得る．

ただしこのハイパーグラフではエッジの重みが 0 か 1 のバイナリ値である．
ハイパーグラフが行列に相当すると考えると，
エッジの重みの意味は同じクラスタに属する度合いとなり，
バイナリ値で表すよりも非負の実数で表す方がより適切と考えられる．
そこで本論文ではハイパーグラフのエッジの重みに非負の実数値を与える．
具体的には，NMF のクラスタリング結果が行列\( V \)で得られ，
同じクラスタに属する度合いが\( V \)から直接求められることを利用する．
またここでは，この実数値の重みを付けたハイパーグラフを重み付きハイパーグラフと呼ぶことにする．

実験では k-means，NMF，通常のハイパーグラフを用いたアンサンブル手法および
重み付きハイパーグラフを用いたアンサンブル手法（本手法）
の各クラスタリング結果を比較し，本手法の有効性を示す．



\section{NMF と初期値の問題}


\subsection{NMF とその特徴}

NMF は\( m \times n \)の索引語文書行列\( X \)を，\( m \times k \)の行列\( U \)と
\( n \times k \)の行列\( V \)の転置行列\( V^{T} \)の積に分解する\cite{nmf}．
ただし\( k \)はクラスタ数である．
\[
X = U V^{T}   
\]

NMF はクラスタに対応したトピックの次元を\( k \)個想定し，その基底ベクトルの線形和によって，
文書ベクトル及び索引語ベクトルを表現することに対応する．
つまり基底ベクトルの係数が，そのトピックとの関連度を表しているので，
行列\( V \)自体がクラスタリング結果と見なせる．
具体的には，\( i \)番目の文書\( d_i \)は，
行列\( X \)の第\( i \)列のベクトルで表現され，
その次元圧縮された結果が，行列\( V \)の第\( i \)行のベクトルとなる．
このとき，\( V \)の第\( i \)行のベクトルは
\[
(v_{i1}, v_{i2}, \cdots, v_{ik})
\]
と表せ，文書\( d_i \)のクラスタの番号は
\[
\arg \max_{j \in 1:k} v_{ij}
\]
となる．

\subsection{NMF のアルゴリズム}

与えられた索引語文書行列\( X \)から，\( U \)と\( V \)は
以下の繰り返しで得ることができる\cite{lee00algorithms}． 
\begin{gather}
  \label{eq:1}
 u'_{ij} \leftarrow u_{ij} \frac{(XV)_{ij}}{(UV^{T}V)_{ij}}   \\
  \label{eq:2}
 v'_{ij} \leftarrow v_{ij} \frac{(X^{T}U)_{ij}}{(VU^{T}U)_{ij}} 
\end{gather}

ここで \( u_{ij} \)と\( v_{ij} \)はそれぞれ\( U \)と\( V \)の\( i \)行\( j \)列の
要素を表す．また \( (X)_{ij} \) により行列\( X \)の\( i \)行\( j \)列の要素を表す．
上記の式により，現在の\( U \)と\( V \)から，\( u'_{ij} \)と\( v'_{ij} \) が得られる，
つまり新たな\( U' \)と\( V' \)が得られるので，それを\( U \)と\( V \)と見なして，
上記の式を繰り返し適用する．

また各繰り返しの後に\( U \)を以下のように正規化する．
\begin{equation}
 u'_{ij} \leftarrow \frac{u_{ij}}{\sqrt{\sum_{i} u_{ij}^2}} 
\end{equation}

繰り返しの終了は，繰り返しの最大回数を決めておくか，
\( UV^{T} \)と\( X \)との距離\( J \)の変化量から判定する．
\begin{equation}
  \label{eq:3}
J = || X - UV^{T} ||_{F}           
\end{equation}

\( J \)の値は NMF の分解の精度を表現している．NMF ではこの分解の精度が
クラスタリングの目的関数となっており，この分解の精度が高い，つまり\( J \)の値が
小さいほど，良好なクラスタリングであると推定する．

また\( || \cdot ||_{F} \)は Frobenius ノルムを表し，\( m \times n \) の行列\( A \)の
Frobenius ノルムは以下で定義される．
\[
|| A ||_{F} = \sqrt{\sum_{i = 1}^{m} \sum_{j = 1}^{n} {a_{ij}}^2}
\]


\subsection{NMF の解の多様性}

通常，行列\( V \)と\( U \)の初期値にはランダムな値を与える．
しかし\mbox{式\ref{eq:1}と\ref{eq:2}}による繰り返しは局所最適解にしか収束しないために，
\( V \)と\( U \)の初期値の与え方によって，最終的に得られる\( V \)と\( U \)は大きく異なり，
結果としてクラスタリングの精度も大きく異なる．

例えば，\mbox{図\ref{tr45a}}は本論文の実験で用いた文書データセット tr45 に対して，
NMF によるクラスタリングの実験を20回行った結果である．
ただし各実験での NMF の初期値にはランダムな値を与えており，
各実験の初期値は異なる．
\mbox{図\ref{tr45a}}の横軸は実験の番号を示し，縦軸はクラスタリングの精度を表している．
\mbox{図\ref{tr45a}}から初期値によって得られる精度が大きく異なることが確認できる．

\begin{figure}[t]
\begin{center}
\includegraphics{14-5ia4f1.eps}
\caption{初期値とクラスタリングの精度}\label{tr45a}
\end{center}
\end{figure}

つまり，NMF は初期値によって得られるクラスタリング結果が異なる．
通常は適当な初期値を与える実験を複数回行い，
それらから得た複数個の解の中で\( X \)の分解の精度が最も高いものを選ぶ．
しかし分解の精度は，直接的にはクラスタリングの精度を意味していないため，
最も精度の高いクラスタリング結果を選択できる保証がない．

ここでは複数個のクラスタリング結果から1つを選択するのではなく，
それらをアンサンブルするアンサンブルクラスタリングを試みる．


\section{アンサンブルクラスタリング}


\subsection{ハイパーグラフによるデータの再表現}

本手法のアンサンブルクラスタリングでは，NMF の初期値を様々に変化させて，
複数個のクラスタリング結果を生成する．次に複数個得られたクラスタリング結果から
各データに対するベクトル表現を新たに作成し，その新たにベクトル表現されたデータに
対してクラスタリングを行うことで，アンサンブルクラスタリングを実現する．

ここでは複数個得られたクラスタリング結果からデータに対する新たなベクトル表現を
作る方法を説明する．基本的には論文\cite{strehl02}で提案された
ハイパーグラフを用いる．

クラスタの数が\( k \)個であり，得られているクラスタリング結果が\( m \)種類の場合，
各データは\( k m \)次元のベクトルで表現される．
データ\( d \)の\( k (i - 1) + c \)次元の値は，
\( i \)番目のクラスタリング結果として，データ\( d \)が
クラスタ番号\( c \)のクラスタに属していれば 1 を，属していなければ 0 を与える．
この結果，データ\( d \)の\( k m \)次元のベクトル表現が得られる．

例を示す．\( k = 3\)，\( m = 4\)とする．またデータは\( \{ d_1,d_2, \cdots, d_7 \} \) の
7つとする．4種類のクラスタリング結果が以下のようになっていたとする．

第1のクラスタリング結果：
\[
\{ d_1,d_2,d_5 \}, \{ d_3,d_4 \}, \{ d_6,d_7 \}
\]
この結果から目的の行列の1列目から3列目が得られる．
\[
                        \begin{array}{c}
                                 d_1\\
                                 d_2\\
                                 d_3\\
                                 d_4\\
                                 d_5\\
                                 d_6\\
                                 d_7\\
                        \end{array}
\left[
                        \begin{array}{rrr}
                                 1& 0& 0\\
                                 1& 0& 0\\
                                 0& 1& 0\\
                                 0& 1& 0\\
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 0& 0& 1
                        \end{array}
\right]
\]

第2のクラスタリング結果：
\[
\{ d_1,d_5 \}, \{ d_2,d_3 \}, \{ d_4,d_6,d_7 \}
\]
この結果から目的の行列の4列目から6列目が得られる．
\[
                        \begin{array}{c}
                                 d_1\\
                                 d_2\\
                                 d_3\\
                                 d_4\\
                                 d_5\\
                                 d_6\\
                                 d_7\\
                        \end{array}
\left[
                        \begin{array}{rrr}
                                 1& 0& 0\\
                                 0& 1& 0\\
                                 0& 1& 0\\
                                 0& 0& 1\\
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 0& 0& 1
                        \end{array}
\right]
\]


第3のクラスタリング結果：
\[
\{ d_2,d_5 \}, \{ d_1, d_4 \}, \{ d_3, d_6,d_7 \}
\]
この結果から目的の行列の7列目から9列目が得られる．
\[
                        \begin{array}{c}
                                 d_1\\
                                 d_2\\
                                 d_3\\
                                 d_4\\
                                 d_5\\
                                 d_6\\
                                 d_7\\
                        \end{array}
\left[
                        \begin{array}{rrr}
                                 0& 1& 0\\
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 0& 1& 0\\
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 0& 0& 1
                        \end{array}
\right]
\]


第4のクラスタリング結果：
\[
\{ d_1,d_5,d_7 \}, \{ d_3,d_4 \}, \{ d_2, d_6 \}
\]
この結果から目的の行列の10列目から12列目が得られる．
\[
                        \begin{array}{c}
                                 d_1\\
                                 d_2\\
                                 d_3\\
                                 d_4\\
                                 d_5\\
                                 d_6\\
                                 d_7\\
                        \end{array}
\left[
                        \begin{array}{rrr}
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 0& 1& 0\\
                                 0& 1& 0\\
                                 1& 0& 0\\
                                 0& 0& 1\\
                                 1& 0& 0
                        \end{array}
\right]
\]

以上の4つの行列を結合させ，以下の\( 7 \times 12 \)の行列を得る．
これがハイパーグラフである．このハイパーグラフにおける行ベクトルが，
各データ（本論文の場合，文書）の新たなベクトル表現に対応している．
このベクトルの類似度に基づいて，データをクラスタリングする．
\[
                        \begin{array}{c}
                                 d_1\\
                                 d_2\\
                                 d_3\\
                                 d_4\\
                                 d_5\\
                                 d_6\\
                                 d_7\\
                        \end{array}
\left[
                        \begin{array}{rrrrrrrrrrrr}
 1& 0& 0 &  1& 0& 0 & 0& 1& 0 & 1& 0& 0 \\
 1& 0& 0 &  0& 1& 0 & 1& 0& 0 & 0& 0& 1 \\
 0& 1& 0 &  0& 1& 0 & 0& 0& 1 & 0& 1& 0 \\
 0& 1& 0 &  0& 0& 1 & 0& 1& 0 & 0& 1& 0 \\
 1& 0& 0 &  1& 0& 0 & 1& 0& 0 & 1& 0& 0 \\
 0& 0& 1 &  0& 0& 1 & 0& 0& 1 & 0& 0& 1 \\
 0& 0& 1 &  0& 0& 1 & 0& 0& 1 & 1& 0& 0
                        \end{array}
\right]
\]

\subsection{重み付きハイパーグラフ}

ハイパーグラフが表す行列の各要素の値は 0 か 1 のバイナリ値である．
しかし値の意味を考えれば，その次元に対応する
あるクラスタリング結果のあるクラスタに属する度合いと捉えられる．
そのため 0 か 1 のバイナリ値ではなく，非負の実数値を与える方が適切である．

しかも NMF の場合，各クラスタリング結果では各クラスタに属する度合いに
対応する値が行列\( V \)に記載されている．
そこでここではハイパーグラフの要素が 1 である部分を，
行列\( V \)の値から得ることで，非負の実数値を与えることにした．
このようにして作成したハイパーグラフを，ここでは重み付きハイパーグラフと呼ぶ．

\mbox{図\ref{ensemble}}に重み付きハイパーグラフの作成例を示す．これは先の
第1のクラスタリング結果に対応する部分である．
\( d_1 \) から \( d_7 \)の7個の文書データセットを
NMF により3グループにクラスタリングする．結果は行列\( V \)で表される．
次に行列\( V \)を正規化する．\( V \)の各行に注目し，最大値の部分を 1に，それ以外を
0 に変換したものが通常のハイパーグラフである．
\( V \)の各行に注目し，最大値の部分はそのままに，それ以外を
0 に変換したものが本論文で提案する重み付きハイパーグラフである．

\begin{figure}[tbp]
\begin{center}
\includegraphics{14-5ia4f2.eps}
\caption{行列 V から作られる重み付きハイパーグラフ}\label{ensemble}
\end{center}
\end{figure}



\section{実験}


本手法の有効性を示すために，k-means，NMF，通常のハイパーグラフを使う
アンサンブル手法および重み付きハイパーグラフを使うアンサンブル手法（本手法）
の4種のクラスタリング結果を比較する．

利用するデータセットは以下のサイトで提供されている18種類である（\mbox{表\ref{tab:dataset}}）．

\begin{verbatim}
      http://glaros.dtc.umn.edu/gkhome/cluto/cluto/download
\end{verbatim}


データセットは通常の索引語文書行列で表現されており，正規化されていない．
ここでは TF-IDF によって正規化を行った．

\begin{table}[tbp]
\input{04t1.txt}
\end{table}


\begin{table}[tbp]
\input{04t2.txt}
\end{table}

実験結果を\mbox{表\ref{tab:result}}に示す．
表の値はクラスタリング結果のエントロピーを表し，
低い値ほどクラスタリングが良好であることを意味する．

なお，ハイパーグラフのデータからのクラスタリングには，
簡単のために，クラスタリング toolkit の CLUTO\footnote{
	{\tt http://glaros.dtc.umn.edu/gkhome/views/cluto}}を利用した．
CLUTO はクラスタリング手法や類似度関数を様々に設定できるが，ここでは default の
設定である k-way clustering と呼ばれる手法と cosine の類似度を用いた．
またハイパーグラフのデータからのクラスタリング手法には任意のものが利用可能であり，
高機能なクラスタリング手法を用いて，更に高い精度を得ることも可能である．
ただしここではアンサンブルすることの効果と，ハイパーグラフに重みを付ける効果を
明確に確認するために，簡易なものを用いた．

また，エントロピーについても注記しておく．エントロピーはクラスタリング結果を評価する
ための1つの尺度である．データセットのクラスタリングの正解が\( \{ K_h \}_{h=1}^{k} \)
であり，得られたクラスタリングが\( \{ C_j \}_{j=1}^{k} \) となっているとき，
クラスタ\( C_i \)に対するエントロピー\( E_i \)は以下で定義される．
\[
E_{i} = - \sum_{h = 1}^{k} P(K_{h}|C_i) \log P(K_{h}|C_i)
\]
各クラスタに対して\( E_i \)を求め，クラスタのデータ数による重み付き平均をとることで
全体のエントロピーが定義される．すなわち以下の式となる．
\[
\sum_{i=1}^{k} \frac{|C_i|}{N} E_{i}
\]
ここで\( N \)は全データ数を表す．また定義中に確率\( P(K_{h}|C_i) \)が出ているが，
これは\( K_{h} \)と\( C_i \)に共通に存在するデータの数を\( n_{hi} \)と置き，
\( n_{hi}/|C_i| \)によって推定する．
またクラスタリングの精度は，クラスタリング結果の各クラスタを正解のクラスタに
対応つけ，\( n_{hi} \)の合計を\( N \)で割った値により求まる．
つまりエントロピーの値の低さとクラスタリングの精度はほぼ対応していると見なせる．

本実験の場合，クラスタリングの精度を求めて，評価を行うことも可能ではあるが，
クラスタリングの精度を求めるには，クラスタリング結果の各クラスタを正解のクラスタに
対応させなくてはならない．この処理は組み合わせ最適化問題になっているために，
単純には最適解が求まらない．そのために，ここではエントロピーによる評価を行っている．

NMF の実験では初期値を20個用意し，得られた20個のクラスタリング結果において，
NMF の分解の精度（\mbox{式\ref{eq:3}}の値）が最も高いものを選び，
それを NMF のクラスタリング結果とした．
NMF mean とあるのは，20個のクラスタリング結果の平均のエントロピーである．
表の standard hypergraph が通常のハイパーグラフを使うアンサンブル手法，
weighted hypergraph が重み付きハイパーグラフを使うアンサンブル手法（本手法）を意味する．

NMF と NMF mean を比較すると，NMF の方が若干エントロピーが大きい．つまり
クラスタリング結果を評価するのに，\mbox{式\ref{eq:3}}を使うのは最良ではないことがわかる．
また NMF mean と weighted hypergraph を比較すると，18 個のデータセット中 17 個で本手法の方が
エントロピーが小さい．つまりこの点からアンサンブルすることの効果が確認できる．
また standard hypergraph と weighted hypergraph を比較すると，
18 個のデータセット中 13 個で本手法の方がエントロピーが小さく，
ハイパーグラフに重みを与える効果も確認できる．

なお 18 個中 13 個の改善は，統計的には以下のような観点から有意とみなした．
standard hypergraph と weighted hypergraph のパフォーマンスが同程度である場合，
standard hypergraph のエントロピーから weighted hypergraph のエントロピーを
引いた値（値が大きいほど改善の度合いが高い）は平均 0 の正規分布と考えられる．
そこで有意水準 0.05 として t-検定の片側検定を用いると，
棄却域は自由度が 17 であることに注意すると\( 1.74 \)以上となる．実際の値は
standard hypergraph のエントロピーから weighted hypergraph のエントロピーを
引いた値の標本平均が 0.03706，標本分散が 0.007389 なので，
\[
\frac{0.03706 - 0}{\sqrt{0.007389 / 17}} = 1.78 > 1.74
\]
\noindent
となり，パフォーマンスが同程度という仮説が棄却できる．



\section{考察と関連研究}



一般に複数の解をアンサンブルすると，複数の解の平均よりも良い値が得られると考えられる．
本実験でも 18 個のデータセット中 17 個でアンサンブルの効果が得られているが，
データセット tr23 に関しては，本手法のエントロピーの値の方が高い．
これは解の分散の影響と考えられる．

実験で得られた各データセットに対する NMF による 20 個のクラスタリング結果の
エントロピーの分散と，\mbox{表\ref{tab:result}}における
NMF mean と weighted hypergarph との差（つまりアンサンブルによる改善の度合い）を
プロットした図を\mbox{図\ref{kou}}に示す．図の横軸が分散を示し，
縦軸がweighted hypergarph と NMF mean との差（改善の度合い）を示している．

\begin{figure}[tbp]
\begin{center}
\includegraphics{14-5ia4f3.eps}
\caption{解の分散とアンサンブルによる改善}\label{kou}
\end{center}
\end{figure}

\mbox{図\ref{kou}}をみると，分散が大きい2つ（cranmad と reviews）は，
アンサンブルによる改善の度合いも大きいことが分かる．
そして3番目に分散が大きなデータセットが tr23 である．
つまり分散の大きな解をアンサンブルすると，非常に良い結果を
得ることもあるが，逆に悪い結果を得ることもあり得ると考えられる．

データセット tr23 に対する NMF の結果を見ると，1つだけ非常にエントロピーの
低いクラスタリング結果が得られていた．この解を取り除いて，
19個のクラスタリング結果で本手法によるアンサンブルを試したところ，
NMF mean のエントロピーは 0.493，weighted hypergarph のエントロピーは 0.492 となり，
アンサンブルの効果が現れた．

また，ここでは NMF で複数個のクラスタリング結果を生成する際に，
個々のクラスタリング結果のクラスタ数は，最終的な
クラスタ数と一致させている．
しかしハイパーグラフの考え方を用いれば，
生成される個々のクラスタリング結果のクラスタ数は任意でかまわない．
実際に k-means では少ないクラスタ数に直接クラスタリングするよりも，
多数のクラスタに分割してから，目的のクラスタ数にまとめた方が
効果があることが経験的にわかっている．
論文\cite{fred02data}ではこのヒューリスティクスを利用して，
多数のクラスタに分割してから，アンサンブルを行っている．
本手法においても，そのような工夫を取り入れることも可能である．


本手法ではハイパーグラフの値として，1 に当たる部分を行列\( V \)の
値を用いることで，実数値に変換した．
この効果は実験で確認できている．
この工夫を更に進めると，0 に当たる部分にも行列\( V \)
の値を用いることで，実数値に変換することが考えられる．
この場合，ハイパーグラフは単純に各クラスタリング結果に
対応する行列\( V \)を結合させたものになる．
実際にこのようにして作ったハイパーグラフに対して，クラスタリングを
行ってみた．結果を表\ref{tab:vresult}に示す．
ここで hypergraph V が行列\( V \)を結合させてハイパーグラフを作成する手法を示す．

\begin{table}[tbp]
\input{04t3.txt}
\end{table}

通常のハイパーグラフを使うよりも結果は良好であるが，
1 に当たる部分だけを精密化する方が効果があることがわかる．
また 0 の値はそのままにしている方が，ハイパーグラフがスパースになり，
データ間の類似度が 0 であるケースが生じやすくなる．
そのためグラフスペクトル理論を用いたクラスタリング手法\cite{graph-minmax-cut}なども使えるように
なるために好ましい．

最後にアンサンブル学習\cite{breiman96bagging}との関連について述べる．
アンサンブル学習とアンサンブルクラスタリングの違いは，
クラスタにラベルがつくかどうかである．
アンサンブル学習ではデータにラベルが付くので，
そのラベルをもつデータがラベル付きのクラスタと見なせる．
アンサンブルクラスタリングの場合は，クラスタにラベルがついていない．
もしもクラスタにラベルをつけることができれば，
アンサンブル学習の手法を直接利用できるために，
さらなる改良や発展が可能である．
クラスタにラベルをつける処理は，
クラスタ数が 2 や 3 などの小さい場合はそれほど大きな問題ではないので，
今後はクラスタにラベルをつけるという戦略で，アンサンブルを行う手法を開発したい．


\section{おわりに}


本論文では，NMF を用いたアンサンブルクラスタリングの手法を提案した．
NMF の初期値を変化させて，複数個のクラスタリング結果を得る．
次に得られた複数個のクラスタリング結果をハイパーグラフで表現し，
それをクラスタリングすることで最終的なクラスタリング結果を得る．
ハイパーグラフを作成する際に，NMF より得られた行列\( V \)を
利用して，1 の部分に実数値の重み付けする工夫を取り入れた．

実験では 18 個のデータセットを用いて，
k-means，NMF，通常のハイパーグラフを使うアンサンブル手法
および重み付きハイパーグラフを使うアンサンブル手法（本手法）の比較を行った．
エントロピーで評価を行い，本手法の有効性を確認できた．

個々のクラスタリングで生成させるクラスタ数を変化させること，
クラスタ数が小さい場合は，クラスタにラベルを与えて，
アンサンブル学習の手法を利用することなどを今後の課題とする．





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

\bibitem[\protect\BCAY{Boley, Gini, Gross, Han, Hastings, Karypis, Kumar,
  Mobasher, \BBA\ Moore}{Boley et~al.}{1999}]{boley99document}
Boley, D., Gini, M.~L., Gross, R., Han, E.-H., Hastings, K., Karypis, G.,
  Kumar, V., Mobasher, B., \BBA\ Moore, J. \BBOP 1999\BBCP.
\newblock \BBOQ Document Categorization and Query Generation on the World Wide
  Web Using WebACE\BBCQ\
\newblock {\Bem Artificial Intelligence Review}, {\Bbf 13}  (5-6), \mbox{\BPGS\
  365--391}.

\bibitem[\protect\BCAY{Breiman}{Breiman}{1996}]{breiman96bagging}
Breiman, L. \BBOP 1996\BBCP.
\newblock \BBOQ Bagging Predictors\BBCQ\
\newblock {\Bem Machine Learning}, {\Bbf 24}  (2), \mbox{\BPGS\ 123--140}.

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

\bibitem[\protect\BCAY{Ding, He, Zha, Gu, \BBA\ Simon}{Ding
  et~al.}{2001}]{graph-minmax-cut}
Ding, C., He, X., Zha, H., Gu, M., \BBA\ Simon, H. \BBOP 2001\BBCP.
\newblock \BBOQ {Spectral Min-max Cut for Graph Partitioning and Data
  Clustering}\BBCQ\
\newblock In {\Bem Lawrence Berkeley National Lab. Tech. report 47848}.

\bibitem[\protect\BCAY{Fern \BBA\ Brodley}{Fern \BBA\
  Brodley}{2003}]{fern_clustensem03}
Fern, X.~Z.\BBACOMMA\ \BBA\ Brodley, C.~E. \BBOP 2003\BBCP.
\newblock \BBOQ Random Projection for High Dimensional Data Clustering: A
  Cluster Ensemble Approach\BBCQ\
\newblock In {\Bem the 20th International Conference of Machine Learning
  (ICML-03)}.

\bibitem[\protect\BCAY{Fred \BBA\ Jain}{Fred \BBA\ Jain}{2002}]{fred02data}
Fred, A.~L.\BBACOMMA\ \BBA\ Jain, A.~K. \BBOP 2002\BBCP.
\newblock \BBOQ {Data Clustering Using Evidence Accumulation}\BBCQ\
\newblock In {\Bem the 16th international conference on pattern recognition},
  \mbox{\BPGS\ 276--280}.

\bibitem[\protect\BCAY{Hearst \BBA\ Pedersen}{Hearst \BBA\
  Pedersen}{1996}]{hearst96reexamining}
Hearst, M.~A.\BBACOMMA\ \BBA\ Pedersen, J.~O. \BBOP 1996\BBCP.
\newblock \BBOQ {Reexamining the cluster hypothesis: Scatter/gather on
  retrieval results}\BBCQ\
\newblock In {\Bem {Proceedings of SIGIR-96}}, \mbox{\BPGS\ 76--84}.

\bibitem[\protect\BCAY{Kummamuru, Lotlikar, Roy, Singal, \BBA\
  Krishnapuram}{Kummamuru et~al.}{2004}]{kummamuruwww2004}
Kummamuru, K., Lotlikar, R., Roy, S., Singal, K., \BBA\ Krishnapuram, R. \BBOP
  2004\BBCP.
\newblock \BBOQ {A Hierarchical Monothetic Document Clustering Algorithm for
  Summarization and Browsing Search Results}\BBCQ\
\newblock In {\Bem Proceedings of WWW-04}, \mbox{\BPGS\ 658--665}.

\bibitem[\protect\BCAY{Lee \BBA\ Seung}{Lee \BBA\
  Seung}{2000}]{lee00algorithms}
Lee, D.~D.\BBACOMMA\ \BBA\ Seung, H.~S. \BBOP 2000\BBCP.
\newblock \BBOQ Algorithms for Non-negative Matrix Factorization\BBCQ\
\newblock In {\Bem {NIPS}}, \mbox{\BPGS\ 556--562}.

\bibitem[\protect\BCAY{Leuski}{Leuski}{2001}]{leuski01evaluating}
Leuski, A. \BBOP 2001\BBCP.
\newblock \BBOQ {Evaluating Document Clustering for Interactive Information
  Retrieval}\BBCQ\
\newblock In {\Bem {Proceedings of CIKM-01}}, \mbox{\BPGS\ 33--40}.

\bibitem[\protect\BCAY{{Michael W. Berry}}{{Michael W.
  Berry}}{2003}]{TextMiningBook}
{Michael W. Berry}\BED\ \BBOP 2003\BBCP.
\newblock {\Bem {Survey of Text Mining: Clustering, Classification, and
  Retrieval}}.
\newblock Springer.

\bibitem[\protect\BCAY{Strehl \BBA\ Ghosh}{Strehl \BBA\ Ghosh}{2002}]{strehl02}
Strehl, A.\BBACOMMA\ \BBA\ Ghosh, J. \BBOP 2002\BBCP.
\newblock \BBOQ {Cluster Ensembles - A Knowledge Reuse Framework for Combining
  Multiple Partitions}\BBCQ\
\newblock In {\Bem {Conference on Artificial Intelligence (AAAI-2002)}},
  \mbox{\BPGS\ 93--98}.

\bibitem[\protect\BCAY{Topchy, Jain, \BBA\ Punch}{Topchy
  et~al.}{2003}]{topchy03combining}
Topchy, A., Jain, A.~K., \BBA\ Punch, W. \BBOP 2003\BBCP.
\newblock \BBOQ {Combining Multiple Weak Clusterings}\BBCQ\
\newblock In {\Bem In The Third IEEE International Conference on Data Mining
  (ICDM'03)}.

\bibitem[\protect\BCAY{Xu, Liu, \BBA\ Gong}{Xu et~al.}{2003}]{nmf}
Xu, W., Liu, X., \BBA\ Gong, Y. \BBOP 2003\BBCP.
\newblock \BBOQ {Document clustering based on non-negative matrix
  factorization}\BBCQ\
\newblock In {\Bem {Proceedings of SIGIR-03}}, \mbox{\BPGS\ 267--273}.

\bibitem[\protect\BCAY{Zeng, He, Chen, Ma, \BBA\ Ma}{Zeng
  et~al.}{2001}]{zeng-learning}
Zeng, H.-J., He, Q.-C., Chen, Z., Ma, W.-Y., \BBA\ Ma, J. \BBOP 2001\BBCP.
\newblock \BBOQ {Learning to Cluster Web Search Results}\BBCQ\
\newblock In {\Bem {Proceedings of SIGIR-04}}, \mbox{\BPGS\ 33--40}.

\end{thebibliography}

\begin{biography}
\bioauthor{新納　浩幸}{
昭和60年東京工業大学理学部情報科学科卒業．
昭和62年同大学大学院理工学研究科情報科学専攻修士課程修了．
同年富士ゼロックス，翌年松下電器を経て，
平成5年4月茨城大学工学部システム工学科助手．
平成9年10月同学科講師，平成13年4月同学科助教授，
現在，茨城大学工学部情報工学科准教授．博士（工学）．
機械学習や統計的手法による自然言語処理の研究に従事．
言語処理学会，情報処理学会，人工知能学会，ACL 各会員．
}
\bioauthor{佐々木　稔}{
平成8年徳島大学工学部知能情報工学科卒業．
平成13年同大学大学院博士後期課程修了．博士（工学）．
平成13年12月茨城大学工学部情報工学科助手．
現在，茨城大学工学部情報工学科講師．
機械学習や統計的手法による情報検索，自然言語処理等に関する研究に従事．
言語処理学会，情報処理学会 各会員．
}
\end{biography}

\biodate


\end{document}
