|
k-means++法は、非階層型クラスタリング手法の1つで、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つ目は、最悪計算時間は入力サイズに対して超多項式（''super-polynomial''）であること。 # もうひとつは、近似解は最適なクラスタリング結果と比べ関していくらでも悪くなることがあること。 この''k-means++法''は2つ目の問題の解消を目指した手法であり、標準的なk-means法の反復を行う前にクラスタ中心を初期化するプロセスを行う。k-means++法の初期化は、最適なk-means法の解に比べてO(log k) の近似比率で解を得ることが保証されている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-means++法」の詳細全文を読む スポンサード リンク
|