データマイニングの分野でトップ 10 の古典的なアルゴリズムの 1 つ - K-Means アルゴリズム (コード付きで非常に詳細)

k-means アルゴリズムは比較的単純です。 k-means アルゴリズムでは、クラスターはクラスターを表すために使用されます。k-means アルゴリズムの収束は、すべての重心が変化しなくなることと同等であることが簡単に証明できます。基本的な k-means アルゴリズムのプロセスは次のとおりです。

導入

K 平均法アルゴリズムとも呼ばれ、教師なし学習におけるクラスタリング アルゴリズムです。

基本的な考え方

k-means アルゴリズムは比較的単純です。 k-means アルゴリズムでは、クラスターはクラスターを表すために使用されます。k-means アルゴリズムの収束は、すべての重心が変化しなくなることと同等であることが簡単に証明できます。基本的な k-means アルゴリズムのプロセスは次のとおりです。

k 個の初期重心を選択します (初期クラスターとして、各初期クラスターには 1 つのポイントのみが含まれます)。

繰り返す：

• 各サンプル ポイントについて、最も近い重心を計算し、そのカテゴリを重心に対応するクラスターとしてマークします。
• k 個のクラスターに対応する重心を再計算します (重心はクラスター内のサンプル ポイントの平均です)。
• 重心が変化しなくなるまで 12345

繰り返し回数によってアルゴリズムの反復回数が決まります。実際、k-means の本質は、各点からそのクラスターの重心までの距離の二乗の合計である目的関数を最小化することです。

• Nは要素の数、xは要素を表し、c(j)はj番目のクラスターの重心を表す。
• アルゴリズムの複雑さ
• 時間の計算量は O(nkt) です。ここで、n は要素の数、t はアルゴリズムの反復回数、k はクラスターの数を表します。

長所と短所

• アドバンテージ
• シンプルで高速。
• 大規模なデータセットに対して効率的かつスケーラブルです。
• 時間の計算量は線形に近いため、大規模なデータセットのマイニングに適しています。

欠点

• K-means はローカル *** であるため、初期重心の選択に敏感です。
• 目的関数の最高のパフォーマンスを達成できる k 値を選択することは非常に困難です。

コード

コードはgithubに実装されており、ここにも投稿されています。

テストデータセットの取得アドレスはtestSetです