データマイニングのためのK平均法アルゴリズムのグラフィカルな説明

K-means クラスタリング アルゴリズム 中国語名は「K-means クラスタリング アルゴリズム」と呼ばれ、統計やデータ マイニングの分野でよく使用されるアルゴリズムです。 Wikipedia では次のように紹介されています: k 平均法クラスタリングは、n 個の観測値を k 個のクラスターに分割し、各観測値が最も近い平均値を持つクラスターに属するようにするクラスター分析の手法です (n 個の観測値を k 個のクラスに分割し、各クラスの観測値がそのクラスの平均に最も近くなり、他のクラスの平均から遠ざかるようにします)。

まず、最もシンプルで直感的な図を見てみましょう。

上の図にはたくさんの点があります。これを 3 つのクラスターに分割したいのですが、どうすればよいでしょうか。 人間であれば一目でわかりますが、コンピュータが分類するのはそれほど簡単ではありません。何らかのアルゴリズムを使用する必要がありますが、k-means はその 1 つです。 K-means は 2 次元空間でのクラスタリングだけでなく、n 次元ベクトル空間に拡張することもでき、文字、画像、音声なども扱うことができます。

上の図を例にとると、K-means アルゴリズムの基本的な手順は次のようになります。
入力: 処理対象となるデータセット（上図の点集合など）、クラスター数（3など）、平均計算方法（2点間の距離関数など）
ステップ 1. まず、各ポイントにランダムに色を付け、同じ色のポイントの座標の算術平均を計算して、対応する平均ポイントを示します。
ステップ 2. 現在計算されている平均ポイントに基づいてすべてのポイント セットを 3 つのカテゴリに分割し、各カテゴリの各ポイントを最も近い平均ポイントと同じ色でマークします。どうやって分けるの？ここでは、「タイソン多角形法」を紹介します。英語名は「ボロノイ図」です（記事参照***Wikipediaリンク）。それで、以下の写真ができました。

ステップ 3. すべてのポイントの色が変化しなくなるまで、ステップ 2 を繰り返します。
アルゴリズムが終了し、次の結果が出力されます。

上記の例は単純な2次元空間での例ですが、3次元空間に配置する場合は平均の計算方法を変更する必要があります。実際、多次元空間や文字、画像などの問題を扱う場合、問題によって計算式が異なります。この場合、mean の意味は「平均」ではない可能性があります。個体間の関係性を測るには、「類似性」と「相違点」を使用する方が良いかもしれません。詳細については、参考記事 1 を参照してください。

いつものように、私が書いた k-means アルゴリズムのコードを下に貼り付けるべきなのですが、残念ながらまだ Python の numpy ライブラリと matplotlib ライブラリを使って絵を描く方法を調べているところです。参考記事 2 に Python 言語のコードがあります。

***この記事の写真はすべて彼のスライドから取ったものなので、データマイニングの講師である Devert Alexandre 氏に感謝したいと思います。 ^_^

参考記事 1 参考記事 2Dベースk平均法 Wikipediaリンク ティーセン多角形法 Wikipediaリンク (ボロノイ図)

オリジナルリンク: http://blog.nlogn.cn/%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98-k-means-%E7%AE%97%E6%B3%95/