K-means++法
k-means法はクラスタ中心を見つけるアルゴリズムである。クラスタ中心とはクラス内分散を最小化する点であり、言い換えるとクラス内のそれぞれのデータ点との距離の二乗和を最小化する点である。任意の入力に対してk-meansの真の解を求める問題はNP困難な問題であるため、解の近似がよく行われる。その手法はLloydアルゴリズムまたはk-meansアルゴリズムと呼ばれ、多くの応用分野で用いられており、高速に近似解が得られる。
しかし、k-means法には2つの理論的な問題がある。
1つ目は、最悪計算時間は入力サイズに対して超多項式(super-polynomial)であること。
もうひとつは、近似解は最適なクラスタリング結果と比べ関していくらでも悪くなることがあること。
このk-means++法は2つ目の問題の解消を目指した手法であり、標準的なk-means法の反復を行う前にクラスタ中心を初期化するプロセスを行う。k-means++法の初期化は、最適なk-means法の解に比べてO(log k) の近似比率で解を得ることが保証されている。