python kmeans

Python-kmeans

K-means クラスタリングの Python 実装。 K 平均法は、同様のデータ ポイントをユーザーが指定した数のグループにグループ化しようとする教師なし学習手法です。以下の例は、k-means++ セントロイド初期化アルゴリズムを使用した Iris データ セットのクラスターの進行を示しています。

説明

k-means は、N 個の d 次元実数値ベクトルのセットから、ユーザーが指定した k(<N) 個のクラスターを識別しようとします。アルゴリズムは、クラスターの中心からクラスターのメンバーまでの距離の二乗の合計を最小化することを試みることによって進められます。正規アルゴリズムは 3 つのフェーズで進行します。

1. k 個のランダムな重心 (クラスター中心) を初期化します。
2. 距離メトリック (通常はユークリッド距離) に従って、データ ポイントを最も近いクラスターに割り当てます。
3. 重心をクラスターのメンバーの平均に更新します。
4. ステップ 2 の割り当てが変更されなくなるまで、ステップ 2 と 3 を繰り返します。

アルゴリズムの出力は、各データ ポイントのクラスター割り当てと、最終的な「歪み」レベルです。このアルゴリズムは、証明された最適な解を生成しません。また、初期のクラスター中心により、明らかに最適ではない局所的な最適解にアルゴリズムが行き詰まる可能性があります (「結果」セクションの基本的な 2 次元の例を参照)。

多くの研究は以下に焦点を当てています。

• 初期クラスター中心を選択します。 K-Means++ はよく知られた方法であり、この実装に含まれています。アルゴリズムの概要は次のサブセクションで説明します。
• 距離の計算、つまりユークリッド以外の尺度を使用する場合は、こちらを参照してください。

K 平均法++

上記のステップ 1 のようにランダムな重心を初期化するのではなく、k-means++ は確率的に初期重心を分散させて、不適切な初期構成を回避します。アルゴリズムは次のとおりです。

1. 最初の重心をランダムに選択します。
2. 各データ点 x について、x からすでに選択されている最も近い重心までの距離 d(x) を計算します。
3. d(x)2 に比例する重み付き確率を使用して、次の重心となるデータ ポイントを選択します。

この手法では、別の初期重心の近くにないデータ ポイントが優先され、遺伝的アルゴリズムでよく使用されるルーレット ホイール (または適合度比例) 選択を彷彿とさせる選択ポリシーが使用されます。

リソース

基本的なアルゴリズム

• K 平均法については、「データ マイニングのトップ 10 アルゴリズム」で説明されています。

• K 平均法については、「情報理論、推論、学習アルゴリズム」で概説されています。ここではその抜粋を示します。

• CMU のアンドリュー・ムーア教授がここにいくつかの良いメモを残しています。

• Edureka の例、犯罪データを使用

クラスターの初期化

• K-Means++、および論文全文はこちら

• K 平均法クラスタリング アルゴリズムの効率的な初期化方法の比較研究

なぜSciPyを使用しないのでしょうか?

SciPy には K 平均法が実装されています。この作業の目的は、学習を目的として純粋な Python 実装を構築し、他の人が K 平均法アルゴリズムを学習できるようにすることです。最小限の Python 経験しか持たない興味のある読者は、SciPy などのライブラリの複雑さを追加することなく、このコードを読んでステップ オーバーすることができます。決して本番環境での使用を目的としたものではありません:)

コードを実行する

依存関係

• Python 3.6.3
• matplotlib 2.1.1 - インストール手順については、ここを参照してください。

実行

Python インタープリターを使用してコードを実行します。

python kmeans.py ./resources/<config.cfg>

ここで、config.cfg はプレーンテキスト構成ファイルです。構成ファイルの形式は、次のフィールドを含む Python dict です。

 {
   'data_file' : '\resources\iris.csv',
   'data_project_columns' : ['sepal_length','sepal_width','petal_length','petal_width','class'],
   'k' : 3,
   'cluster_atts' : ['sepal_length','sepal_width','petal_length','petal_width'],
   'init_cluster_func' : 'kmeans_plus_plus',
   'plot_config' :
    {'output_file_prefix' : 'iris',
     'plots_configs': [
        {'plot_atts' : ['sepal_length','sepal_width']},
        {'plot_atts' : ['sepal_length','petal_length']},
        {'plot_atts' : ['sepal_length','petal_width']},
        {'plot_atts' : ['sepal_width','petal_length']},
        {'plot_atts' : ['sepal_width','petal_width']},
        {'plot_atts' : ['sepal_width','petal_width']}
     ]
   }
}

以下を指定する必要があります。

• CSV データ ファイル。
• ファイルから投影するフィールドのサブセット。
• 形成するクラスターの数、k。
• クラスタリングプロセスで使用される属性のサブセット。
• オプションで初期クラスター関数 (default='rand_init_centroids') を指定します。興味のある作成者は、独自の関数をコードに追加して、ここで指定します。
• 以下を含むプロット構成
  • プロセス中に作業ディレクトリに作成される png ファイルのプレフィックス。これが指定されていない場合、画像は生成されません。
  • 個々のプロット構成。プロットあたり 2 次元に制限されます。

結果

アイリスデータセット

アイリス データ セット (iris.config)、Lichman, M. (2013) より。 UCI 機械学習リポジトリ。カリフォルニア州アーバイン: カリフォルニア大学情報およびコンピューター サイエンス学部は、機械学習コミュニティでは非常によく知られたデータ セットです。私のランダムな初期クラスターの結果は次のとおりです。

基本的な合成2Dデータ

このデータはデバッグ目的で生成されたものであり (basic2d.config を参照)、初期ランダム クラスターの選択が適切でなかった場合の影響を示しています。以下の結果は、アルゴリズムが明らかなクラスター割り当てに到達するのを妨げる初期重心構成を示しています。この場合、赤い重心の配置は、青い重心が左下象限と右下象限のすべてのデータ ポイントを捕捉することを意味します。

犯罪

犯罪データ セット (crime.config) は Edureka からのものです (こちら)。