モーメント法によるノイズ推定を用いたスペクトラルクラスタリング
理学専攻 情報科学コース

1

はじめにデータをまとまりごとに集めてグループ分けをする
ことは, クラスタリングと呼ばれている. クラスタリン
グは, 階層的手法と非階層的手法の 2 つに大きく分類され, 非階層的手法の代表例に K− 平均法がある. K−平均法は非常に有効なクラスタリング手法ではあるが,反復演算を必要とする点と, 収束解が必ずしも目的関数を最適にするものではないという欠点がある. スペ
クトラルクラスタリングでは, クラスタリングの問題を固有値問題として定式化することによって, これらの問題点を避けるアルゴリズムを構成することが出来る.
本研究では, データから得られるカーネル行列のスペクトル分布を, ランダム行列理論で知られているスペクトル分布と, モーメント法を用いて照らし合わせ,データの構造部を推定する. そして, 構造部のスペクトルのみを用いて, スペクトラルクラスタリングを行うことにより, その精度を向上させる手法を試みる.

2

Wishart 行列

各成分が独立に N (0, 1) の標準正規分布に従う変数をもつ n × p の行列を C とする. このランダム行列 Cから1S = C TCnで求められる n × n 対称ランダム行列 S を Wishart行列という. p/n = λ を保ちながら, n → ∞, p → ∞の極限をとると, Wishart 行列 S の固有値の経験分布は, λmin ≤ t ≤ λmax のときに以下の確率密度関数に収束することが知られている.
−(t − λmax )(t − λmin )1,p(t) =2πλt 2λmaxmin = (1 ± λ) .
また, このような確率密度関数を持つ分布は MarcenkoPastur 分布と呼ばれている.

2.2|| ||2 は通常のユークリッド 2 乗距離で, β ∈ R は適当なパラメータである.
また, Wishart 行列の固有値分布と, ガウスカーネルで写像した特徴空間における内積行列の固有値分布は等価であると知られており, これによりガウスカー
ネル行列におけるノイズ部に相当する固有値分布もMarcenko-Pastur 分布と同様の性質を持つことがわかる.

3モーメント法f (x) を連続確率変数 X の密度関数とするとき, 原点まわりの k 次モーメント mk は,
 ∞
mk =xk f (x)dx−∞と表せ, これらの値は確率分布の特徴を与える. また,先にランダム行列理論で述べた Marcenko-Pastur 分布のモーメントは,ランダム行列理論

一般に, ランダム行列とは確率変数を要素に持つ行列であり, その代表例として Wishart 行列が挙げられる.

2.1(指導教員：吉田裕亮)

茨木志織

ガウスカーネル

変数の集合の二つの要素 x, x に対し、カーネル関数
k(x, x ) は x, x それぞれの特徴ベクトルどうしの内積k(x, x ) = φ(x)T φ(x )として定義される. カーネルには様々なものがあるが,その中でもガウスカーネル

k(x, x ) = exp(−β||x − x ||2 )を用いて特徴空間に写像した行列は, 相関行列と同じような振る舞いをすることが知られている. ここで,

mk =

2k!
mkk!(k + 1)! 1で与えられる.
本研究では, 観測データからの標本モーメント列を理論値と比較することにより, 最適なノイズ部の推定を行う. 目視でスペクトルを比較するより, 定量的な推定が行える.

4

スペクトラルクラスタリング

スペクトラルクラスタリングは, サンプル点をグラフ構造として考え, 各頂点がサンプル点で, 枝にはサンプル点同士の近さを表す重みがついているとする. 例
えば, サンプル点を 2 つのグループに分けると, それに伴いグラフも 2 分割される. 分割されたグループ間を結ぶ枝のことを分割のカットと呼び, このカットの重みの合計が小さくなるようにグループ分けを行う. 式
で表すと, 以下のようになる.
minKij (βi − βj )2 = 2 TβP β, βi = ±1βi,jn
ここで, P は対角行列 Λ を Λii = j=1 Kij として,P = Λ − K と書ける. β は 2 値ベクトルという制約がある. それは整数計画問題と呼ばれ, 一般には解くのが困難である. そこで, 整数という制約を取り払って任意の実数ベクトルに, TβΛβ = 1 という条件の下, 制約を緩めることにより推定を行うことになる. この場合, 最小固有値 0 が存在するが, これはすべてのサンプルを 1 つにまとめてしまうという意味のない解のため, 実際には 2 番目以降の固有ベクトルの成分符号に基づいてクラスタリングを行う.

5提案手法

本研究では、以下のようにスペクトラルクラスタリングを行うことを提案する.

1. サンプルデータのガウスカーネル行列 Kk(x1 , x1 ) k(x2 , x1 ) k(x1 , x2 ) k(x2 , x2 )
K =
..
..

.
.
k(x1 , xn ) k(x2 , xn )······..
.

k(xn , x1 )k(xn , x2 ) 
..

.

···

k(xn , xn )を構成し, そのスペクトル分布を求める.
2. Marcenko-Pastur 分布のモーメント列に最も適合するように, 1 で求めたスペクトルからモーメント法を用いてノイズ部と構造部を推定する.
3. 構造部のスペクトルのみを用いてカーネル行列 K を再構成する.
4. この新たな K  を与えられたカーネル行列と見なし, スペクトラルクラスタリングを行う.

6のモーメント列に最も適合することが分かった ( 図 2).
その 338 個のスペクトルを目安にして, 実際にサンプルデータのヒストグラムと Marcenko-Pastur 分布を重ね合わせてみると, 図 3 のように分布が合っていることも見て取れる. (今回, ガウスカーネル行列 K は, 正方行列なので λ は 1 となり, マルチェンコパスツール
分布は図 3 の曲線のような形となっている.)
そこで, Marcenko-Pastur 分布から外れた残りのス
ペクトル 62 個がサンプルデータの構造部であると考え, このスペクトルのみを用いてカーネル行列を再編成し, スペクトラルクラスタリングを行った.

6.2

結果
1.5
1.00.5321

実験例

1230.5

図 1 のような, 線形で分けることの出来ない 3 群のデータを用意する. 1 群, 2 群が各 100 点, 3 群が 200点の合計 400 点のサンプルデータとなっている. これらをスペクトラルクラスタリングで, 3 つにクラス分けする.

1.0
1.5

図 4: ノイズを除いた場合
1.5
1.00.50.5

2

113221123

0.5
0.5

1.0
1.5

1.0

図 5: 除いていない場合

図 1: サンプルデータ

6.1

ノイズ部スペクトルの推定

図 2: Marcenko-Pastur 分布のモーメント理論値 (上段) とスペクトル 338 個のモーメント値 (下段) の比較

このとき, 図 4 の結果が得られた. 比較の為, 下に通常のスペクトラルクラスタリングの結果 ( 図 5) を並べておく. 図 4 は, ほぼ設定通りに 3 つにクラス分けが出来ている. ノイズを除いた場合の方が, クラスタリングが適切に行えていることが分かる.

7

まとめ

今回の実験で, データに含まれるノイズを除去することにより, スペクトラルクラスタリングの精度を高めることが可能である場合があることが, 確認出来た.
また, ノイズ推定の際, モーメント法を用いて理論値と比較することによって, 目視でスペクトルを比較するより, 定量的な推定が行えることが分かった. また今後の課題として, Marcenko-Pastur 分布の適切なスケーリングパラメータの推定を行いたいと考えている.

参考文献

図 3: ヒストグラムと Marcenko-Pastur 分布
サンプルデータのガウスカーネル行列のスペクトルをもとにモーメントを計算していったところ, 値の小さい方から 338 個用いた時に, Marcenko-Pastur 分布

1. 赤穂昭太郎, カーネル多変量解析〜非線形データ解析の新しい展開, 岩波書店 (2008)
2. 伊藤里江, ランダム行列理論を用いた Gaussian
カーネルにおける雑音の推定, お茶の水女子大学
大学院理学専攻情報科学コース修士論文, 2009 年