K-means++法

k-means++法の概要

k-means++法は、データをクラスタに分けるための非階層型クラスタリング手法の一つで、2007年にDavid ArthurとSergei Vassilvitskiiによって提案されました。この手法は、従来のk-means法における初期値選択の問題を改善し、より効率的で安定したクラスタリングを可能にします。

背景

k-means法はクラスタリングアルゴリズムとして広く利用されており、与えられたデータセット内でクラスタ中心を特定することを目的としています。具体的には、クラスタ中心はクラス内のデータ点からの距離の二乗和を最小化する点を示します。しかし、この最適解を求める問題はNP困難であるため、近似解を得ることが一般的です。

k-means法にはいくつかの理論的な制約があります。最も顕著なのは、最悪の場合の計算時間が入力データのサイズに対して超多項式である点と、得られる近似解が最適解から大きく外れる可能性がある点です。k-means++法は、特に二つ目の問題を解決することを目指し、標準的なk-means法の反復処理に先立ち、クラスタ中心を効果的に初期化する手順を盛り込んでいます。この初期化により、時間計算量はO(log k)の近似比率で解を得ることができると保証されています。

アルゴリズムの手順

k-means++法は「初期のクラスタ中心は互いにできるだけ離れているほうが良い」という考え方に基づいています。手続きは以下のように進行します。

1. データセット内からランダムに一つの点を選びます。これが最初のクラスタ中心です。
2. 次に、各データ点について、選択されたクラスタ中心との距離を計算します。
3. この距離の二乗を基に、未選択のデータ点をクラスタ中心として新たに選びます。選び方は、距離の二乗に比例した確率で行います。
4. このプロセスをk個のクラスタ中心が選ばれるまで繰り返します。
5. 選定したクラスタ中心を基に、標準的なk-means法を実行します。

初期値の選定には一定の時間がかかりますが、その後のk-means法は収束が非常に早く、計算時間がそれほど増えることはありません。実験では、k-means++法が従来のk-means法に比べて約2倍の収束速度を持ち、特定のデータセットでは誤差が1000分の1に達したことが示されています。また、様々な実データと人工データを用いた実験で、この手法が常に速度と誤差の両面で優れていることが確認されています。

ソフトウェアサポート

k-means++法は、複数のフレームワークやソフトウェアで実装されており、以下のようなツールが一般的に使用されています。

• - ELKI
• - GNU R
• - OpenCV
• - Weka
• - CMU's GraphLab

関連項目

さらに深くクラスタリング手法を探求する際は、x-means法など、kに基づく再帰的な手法もあります。x-means法は、ベイズ情報量規準(BSI)を用いて終了条件を決定し、k=2からスタートします。このような手法も併せて学ぶことで、幅広いクラスタリング技術の理解を深めることができるでしょう。

もう一度検索