K-means++法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

データマイニング分野において、k-means++法k-means法の初期値の選択に改良を行なった方法である。

標準的なk-means法が頻繁にクラスタとすべきではないものにもクラスタ割り当てを行ってしまう問題や、 k-means法がNP困難な問題であることを解消するために、2007年にDavid ArthurとSergei Vassilvitskiiによって提案された。 2006年にRafail Ostrovskyらによって提案されたthree seeding methodと似ているが初期シードの分布が異なる。

背景[編集]

k-means法はクラスタ中心を見つけるアルゴリズムである。クラスタ中心とはクラス内分散を最小化する点であり、言い換えるとクラス内のそれぞれのデータ点との距離の二乗和を最小化する点である。任意の入力に対してk-meansの真の解を求める問題はNP困難な問題であるため、解の近似がよく行われる。その手法はLloydアルゴリズムまたはk-meansアルゴリズムと呼ばれ、多くの応用分野で用いられており、高速に近似解が得られる。

しかし、k-means法には2つの理論的な問題がある。

  1. 1つ目は、最悪計算時間は入力サイズに対して超多項式(super-polynomial)であること。
  2. もうひとつは、近似解は最適なクラスタリング結果と比べ関していくらでも悪くなれる。

このk-means++法は2つ目の問題の解消を目指した手法であり、標準的なk-means法の反復式を動かす前にクラスタ中心を初期化するプロセスを行う。k-means++法の初期化は、k-means++法は、最適なk-means法の解に比べてO(log k) の近似比率で解を得ることが保証されている[1]

アルゴリズム[編集]

このk-means++法は、初期のk個のクラスタ中心はなるべく離れている方がいいという考えにもとづいている。まず始めにデータ点をランダムに選び1つ目のクラスタ中心とし、全てのデータ点とその最近傍のクラスタ中心の距離を求め、その距離の二乗に比例した確率でクラスタして選ばれていないデータ点をクラスタとしてランダムに選ぶ。

アルゴリズムは以下の手順で行われる。

  1. データ点からランダムに1つ選びそれをクラスタ中心とする。
  2. それぞれのデータ点xに関して、その点の最近傍中心との距離D(x)を計算する。
  3. データ点xに関して距離の二乗D(x)^2に比例する重みつき確率分布を用いて、データ点を新しいクラスタ中心としてランダムに選ぶ。
  4. k個のクラスタ中心が選ばれるまで2と3を繰り返す。
  5. 選ばれたクラスタ中心を初期値として標準的なk-means法を行う。

この初期値決めの方法はk-means法の著しく改善する。 初期値決めに余計な時間がかかるが、k-means法は収束がとても早く計算時間はそれほどかからない。 著者らはこの手法を実データと人工データの両方で実験を行い、 だいたい収束スピードに関しては2倍、あるデータセットでは誤差が1000分の1となったことを報告している。 一連の実験では定番のk-means法の速度と誤差の関してつねに優っていた。

それに加え、このアルゴリズムの近似率を計算されている。k-means++法は 平均的にO(log k)の近似比率で近似可能であることが保証されている。kはクラスタ数である。これに対し、標準的なk-means法では最適値に対して任意の精度で悪くすることができる。

ソフトウェア[編集]

関連項目[編集]

  • x-means法 k=2で再帰的にk-meansを行う方法。終了条件はベイズ情報量規準(BSI: Bayesian information criterion)で決める。

参考文献[編集]

  1. ^ k-means++: The Advantages of Careful Seeding”. 2013年10月20日閲覧。