Local and Global Optimization Techniques in Graph-based Clusteringを読んだのでメモ
はじめに
Local and Global Optimization Techniques in Graph-based Clusteringを読んだのでメモ.札幌で開催されたMIRU2018で著者の方が発表されていて気になったので読んでみた次第.
graph-based clustering
この論文では以下の目的関数の最小化問題としてのgraph-based clusteringに着目している.
ここで,はn個のデータ点に対するaffinity matrixで,はassignment matrixを表す.assignment matrixは番目のデータがクラスタに属する場合,となるような行列.つまり各データ点がどのクラスタに属するかを表している.はコスト関数ごとに異なる関数.
Graph-based clusteringはk-meansやGMMのようなrepresentative-based clusteringと違い,データ間のつながり(グラフの構造)を利用したクラスタリングが可能という利点がある.
論文ではgraph-based clusteringの3つの重要な要素としてaffinity matrixの構成,目的関数,最適化の方法をあげていて,それぞれの観点から関連研究をまとめている.
Affinity matrix
最も単純なaffinity matrixの作り方は距離に基づく方法で例としては-NNやガウスカーネルを使う方法がある.その他にはデータからの学習によるaffinity matrixの獲得方法もあり,学習ベースでは線形結合の係数行列によってaffinity matrixが表現される.
objective function
従来,macro averageに基づく指標,例えばやなど(ただしは全ての要素が1の縦ベクトル)が用いられていた.ただ,macro averageに基づく目的関数は望まない小さなクラスタを生成してしまうため,クラスタサイズのバランスを取るような目的関数,balanced association(BA)が2017年に提案されている.BAの目的関数は以下で表される.
がクラスたのサイズを調整する係数で大きいほど各クラスタのサイズが等しくなる.論文のTable 1に提案手法の目的関数を含め各目的関数がまとまっている.
optimization methods
最初に与えられたはNP-hardな組合せ最適化の問題であり,大局的な最適解を見つけるのは難しい.normalizing cutやspectral cluseringはspectral緩和を使うことで解いていて,最も広く使われている.これらの類似手法であるmacro-AAでは目的関数は次のような形で表現される.
これはをのように緩和することでの固有ベクトルを利用することで上で解くことが可能.問題としては緩和が必要なことやmacro-average-based cost functionを用いること,の計算コストなどがあげられる.
その他の方法としてはkernel k-meansなどで知られるbound optimization method (BO)などがあり,BOは次のような上界の最小化を行う.
Macro-AAにおいてはであり,normalizing cutにおいてはとして表現される.これはが半正定値行列である場合に厳密なbound functionになる.
Micro-average association
関連研究で議論されていたようにnormalizing cut等に用いられるmacro-average-based cost functionは小さなクラスタを生成してしまう場合がある.ここではこの問題を解決するために,以下のmicro average associtationに基づく目的関数を提案する.
これはとしたもので,によってクラスタの大きさをコントロールできる.つまり,分母が各クラスタに入っているデータ数の総数の乗の総和で定義されているため,コスト関数を最大化するには均一に近い方が望ましいということ.これをここではmicro average association cost (micro-AA)と呼ぶ.
Micro-AAの利点は小さなクラスタの出現を防ぐことで,同様の効果を持つBAと比べて実験的にmicro-AAの方が良いクラスタリング結果を実現したとのこと.ただし,micro-AAはNP-hardであることと,既存手法には適用できない問題がある.
direct local optimization
ここでは目的関数の上昇が保証されている繰り返し最適化手法であるdirect local optimization (DLO)を提案.DLO単体では良いクラスタリング結果を得るためには良い初期値が必要であるが,同時に提案するgreedy incremental algorithm (GIA)を適用することで初期値の影響を受けにくくする事が可能.
まずDLOの説明の前にaffinity matrixを対称行列と仮定する.仮にaffinity matrixが非対称行列だった場合とすれば対称行列になることから一般性は失わない.また,の列ベクトルと行ベクトルをそれぞれ,と定義する.
DLOは座標降下法の一種で,目的関数の値が繰り返しの度に上昇することが保証されている.iteration における解が与えられた時,DLOは行ベクトルごとに最適化していく.
最大化問題は,ある番目のサンプルの所属クラスタを変えた時に最もエネルギー関数が上昇するクラスタをそのサンプルに割り振ることで解かれる.すなわち一回の更新に対しクラスタ数回の計算を行う.これは少なくともサンプルを同じクラスタに割り振れば目的関数の値は等しくなるため,目的関数の値を下げることはない.
サンプルの選び方はrandomized, cyclic, greedyの3つのタイプに分けられる.randomized coordinate descentはサンプルの集合からランダムにサンプルを選び,cyclic coordinate descentは順番にを選ぶ.greedy coordinate descentは目的関数を最も上昇させるサンプルを選ぶ.3つの中でもgreedyなものは最良のサンプルを選択するため計算コストがかさむが,良いサンプルを選択することができるため実践的にはrandomなものよりも計算コストにおいて良いパフォーマンスを示す.そのためこの論文ではgreedyな選択をすることにしたとのこと.
回目の更新の時にサンプルを番目のクラスタに割り振った時の目的関数の値をとする.この目的関数の値を愚直に計算するとコストが高いため,回目の更新時の目的関数の値を利用することで効率良く計算する.繰り返しにおいてサンプルが所属するクラスタをとすれば目的関数は次のように書ける.
ただし,
との計算オーダーはそれぞれになるが,次のように効率的に計算が可能.
結局,上記のような方法で計算をすればそれぞれの計算オーダーはになる.最終的には全てのに関する目的関数の計算オーダーは繰り返し1回目は,その後はとなる.
greedy incremental algorithm
DLOは局所最適化法なため良い解を得るためには良い初期値が必要となる.初期値としてspectral clusteringの結果を使う方法などもあるがspectral clusteringは特定の場合においてはうまく機能しない問題がある.そこでここでは初期値の影響を減らすことのできるgreedy incremental algorithm (GIA)を提案する.
まずの初期値をとし,とする.さらにまだクラスタの割り当てが決まっていないサンプルの集合をとする.DLOと同様の手順を用いて目的関数の値を計算し,目的関数の値を最大にするサンプルとクラスを用いてとを更新する.要は初期の割り振りを与えずにDLOをするという感じ.これにより初期値に依存をしないためDLOのパフォーマンスを改善できるというもの.GIAの計算オーダーはでは繰り返し回数.
提案手法を含む多くのgraph-clustering最適化手法は局所解につかまりやすいという問題があるよう.そこで論文ではGIAを用いる上で大局的な最適解を導きやすくする二つの方法を紹介している.
GIAはaffinity matrixが疎な行列である場合,悪い局所解にトラップされる傾向にあるらしい.そこでgraduated optimization (GO)を適用することでこれを回避する術を紹介している.凸でない関数を解く上でGOはまずはじめに平滑化された関数を解き,更新とともに徐々にをへと変形していく.graph-clusteringの文脈では平滑化されたaffinity matrix を使うことで平滑化された関数を得る.論文中のFigure 3にはを変えた際のaffinity matrixの変化が示されていて,疎な行列がが大きくなるにつれ徐々に密になっていることがわかる.GOのやり方に従えば,最初はを大きな値に設定して最適化を行い,最終的にになるよう徐々にの値を小さくしていくことで局所解にトラップされることを防ぐ.
もう一つの局所解を回避する方法としてclustering ensemble (CE)がある.GIAは局所解にトラップされても,部分的には綺麗なクラスタを形成していることが論文中のFigure 4の結果からわかる.そこで,GIAの個の解からco-association matrix を計算する.簡単に言ってしまえば複数の結果の平均を最終的な結果としようというもの.ただし,クラスタリングの結果を得るためにはという変換が必要になる.そこでaffinity matrixをとして目的関数を解くことでこの変換を達成する.ただし,目的はgraph-based clusteringの大局的最適解を達成することなので,から得られた解を使って元のaffinity matrix 上でDLOを使い最適解を得る.
実験
実験に用いたデータセットの多くで既存手法を大きく上回るクラスタリング精度を達成している.特にCOIL-20ではクラスタリング精度100%となっていて驚き.ただ,clustering ensembleがうまく働かない,すなわちクラスタリング結果にバイアスが乗るようなデータでは若干悪い結果となるようで,実際クラス毎のサンプル数に偏りのあるHopkins 155ではspectral clusteringを6%程下回る結果になっている.
まとめ
Graph-based clusteringに関する知識があまりにもないため若干理解しきれていない部分(目的関数の根本的なところや各手法の嬉しさなど)があるからお盆の間に基本的なところから勉強して理解したい.逆にそんな知識不足の中読んだ論文なのでメモの内容は謝りを多く含むかもしれないので注意。。。