クラス外ノイズを考慮したスペクトラルクラスタリング
戸井田明

1(指導教員：吉田裕亮)
4

はじめにクラスタリングとは, 与えられたいくつかのデータをいくつかのある集合に明確に分類することである.
つまり, あるクラスタを考えるときに, １つ１つのデータがそのクラスタに属するか属さないかが明確に判別される. しかし, すべてを明確に判別することは現実的ではない場合もある. 実際にはどのクラスにも属さないノイズが混入していることもあり得ると考えられる.
そこで本研究ではこのような不明確なデータをどのクラスタにも属さないような, クラスタリングの手法について考察する.

2

βi,jnここで, P は対角行列 Λ を Λii =j=1 Kij として,P = Λ − K と書ける. β は２値ベクトルという制約がある. これは整数計画問題と呼ばれ, 一般には解くのが困難である.

クラスタリング

クラスタリングは, 階層的手法と非階層的手法の２つに大きく分類され, 非階層的手法の代表例に K−平均法がある. K− 平均法は非常に有効なクラスタリング手法ではあるが, 初期値に依存するアルゴリズムなので, 収束解が必ずしも目的関数を最適にするものではないという点と, 反復演算を必要とするという欠点がある.

そこで, 整数という制約を取り払って任意の実数ベクトルに, T βΛβ = 1 という条件の下, 制約を緩めることにより推定を行うことになる. この場合, 最小固有値 0 が存在するが, これはすべてのサンプルを 1 つにまとめてしまうという意味のない解のため, 実際には２番目以降の固有ベクトルの成分符号に基づいてクラスタリングを行うことになる.

スペクトラルクラスタリングでは, クラスタリングの問題を固有値問題として定式化することによって,これらの問題点を避けるアルゴリズムを構成することができる.

5

また, K− 平均法は, データを最も近いクラスタに分類するという線形なクラスタリング手法なので,データの形によってはうまくいかない場合もある. しかしスペクトラルクラスタリングは, 与えられたデータをカーネル法を用いて高次元の特徴空間上に写像してからクラスタリングを行うので, 非線形なクラスタリングに拡張され, 非線形性なクラス形状をもつデータでも上手くクラスタリングすることができる.

3

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

スペクトラルクラスタリングは, サンプル点をグラフ構造として考え, 各頂点がサンプル点で, 枝にはサンプル点同士の近さを表す重みがついているとする.
したがって, 例えばサンプル点を 2 つのグループに分けると, それに伴いグラフも２分割される. 分割されたグループ間結ぶ枝のことを分割カットと呼び, このカットの重みの合計が小さくなるようにグループ分けを行う. 式で表すと, 以下のようになる.
β,Ki,j (βi − βj )2 = β T Pββi = ±1min

データ間距離の計算

カーネル法では, 非線形なデータを一度高次元の特徴空間上に表現し, 写像することで, 解析しやすいデータに変換し, その特徴空間上で線形なモデルを組み立て, 問題を解く. このとき, 特徴空間上での内積をカーネル関数を用いて計算することにより, 計算量を抑えることができるという利点がある.
各クラスの重心とサンプルデータの距離を測るた
めに, 距離 di は以下のようにカーネルを用いて特徴空間上で計算する.

カーネル関数

非線形なクラス形状をもつ複雑なデータを扱うために, カーネル関数を用いる. カーネル関数 k(x, x ) とは, データ変数の集合の２つの要素 x, x に対し, x, xのそれぞれの特徴ベクトル φ(x), φ(x ) どうしの内積

di=||xi − µ||2=K(xi , xi ) −n+k(x, x ) = φ(x)T φ(x )n2
K(xi , xj )n j=1n1 K(xj , xl )n2 j=1l=1として定義される. カーネルには様々なものがあるが,その中でもガウスカーネル

xi は各データの値, µ は各クラスタの平均, n はそのクラスタのデータの数である.

k(x, x ) = exp(−β||x − x ||2 )本研究では, この値が大きいもの, つまり特徴空間上において, 重心から離れているデータをカットし, ノイズとして推定する.

を用いて特徴空間上に写像した行列は, 相関行列と同じような振る舞いをすることが知られている. ここで,|| · ||2 は通常のユークリッド距離２乗で, β ∈ R は適当なパラメータである.

6提案手法

まずデータを与え, そのデータから与えられるカーネル行列に非線形にクラスタリングする. クラス分け

23

された各クラスタに対し, もう一度適当なパラメータを用いてカーネル行列を計算し, 特徴空間上での各クラスタの重心とデータの距離を計算する. そしてその重心から遠いデータをノイズとし, 抽出するという手法を試みる.

うにノイズを含め, 非線形に２つのクラスに分かれた.
このときパラメータ β の値を 100 とした.

7.2

２つに分かれたクラスタのうちの１つのクラスタに対し, データ間距離を計算し, ある閾値より大きいものをノイズとした結果下の図のようになった.

本研究では, 以下のような手法を提案する.

1. 与えられたデータのガウスカーネル行列 Kk(x1 , x1 ) k(x2 , x1 ) . . . k(xn , x1 ) k(x1 , x2 ) k(x2 , x2 ) . . . k(xn , x2 ) 

K=
..
..
..
..

.

.
.
.
k(x1 , xn ) k(x2 , xn )...

ノイズを抽出k(xn , xn )を構成し, スペクトラルクラスタリングを行う.
2. クラス分けされたうちの各クラスタに対し, 適当なパラメータを選び, もう一度ガウスカーネル行列を計算する.
3. この新たなガウスカーネル行列を用い, クラスタの重心とデータの距離を計算し, そのデータ間距離の値がある閾値より大きいデータをノイズと推定する.
4. これをすべてのクラスタに対して実行し, すべてのノイズを抽出する.

図３：ノイズの抽出結果
この例では 1.000435 より大きいものをノイズとして抽出した. またもう１つのクラスタに対しても同じ操作を施す.

8

実験結果
最終的には以下のような良好な判別結果が得られた.

7

実験例

図 1 のような, 線形で分けることのできない２つの群からなるサンプルデータを用意する. 250 個ずつの２つの群に, ノイズとして-0.8 から 0.8 の一様乱数300 個を加えた, 計 800 個のサンプルデータとなっている. このデータをスペクトラルクラスタリングで, ２つのクラスとそれ以外のノイズに分ける.
図４：実験結果

9

まとめ

複雑なサンプルデータを非線形にクラス分けすることができ, ある程度上手くノイズを抽出することができた.
しかし, スペクトラルクラスタリングを実行する
際に, パラメータ β の値によって結果が大きく左右するので, 適切な β の値を探すのが困難である. また, サ
ンプルデータをどの程度ノイズとするか, つまり閾値をどこに設定するか, という課題が残されている.

図１：サンプルデータ

7.1

スペクトラルクラスタリング実行参考文献
1. 赤沼昭太郎, カーネル多変量解析〜非線形データ解析の新しい展開〜, 岩波書店, 東京, 2009.
2. 西田英郎, クラスター分析とその応用, 内田老鶴
圃, 東京, 1988.
3. 茨木志織, モーメント法によるノイズ推定を用いたスペクトラルクラスタリング, お茶の水女子大学大学院理学専攻情報科学コース修士論文,2011.

図２：スペクトラルクラスタリングの実行結果
サンプルデータのガウスカーネル行列を計算し, スペクトラルクラスタリングを実行した結果, 図２のよ24