k means algorithm

K 平均法アルゴリズム

これは、最適な K を選択するためのエルボー法とシルエット法を含む K 平均法アルゴリズムの Python 実装です。

K 平均法は、データを K 個のクラスターに分割するために使用される一般的なクラスタリング アルゴリズムです。これは、各データ ポイントを最も近いクラスターの重心に繰り返し割り当て、割り当てられたデータ ポイントに基づいて各クラスターの重心を再計算することで機能します。このプロセスは収束するまで繰り返されます。

アルゴリズム

• データ ポイントから K 個の初期クラスター重心をランダムに選択します。
• 各データ ポイントを最も近いクラスターの重心に割り当てます。
• 各クラスターに割り当てられたデータ ポイントに基づいて、各クラスターの重心を再計算します。
• 収束するまで (つまり、クラスターの割り当てが変更されなくなるまで) ステップ 2 ～ 3 を繰り返します。

目的関数

K 平均法の目的は、各データ ポイントとその割り当てられたクラスター重心間の二乗距離の合計を最小化することです。目的関数は次のように記述できます。 $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$どこ $x_i^j$はクラスターj内のi-thデータ点、 μjはクラスターjの重心、 Nデータ点の総数です。

エルボ法

エルボー法は、K-Means クラスタリングで最適なクラスター数を決定するために使用されるヒューリスティックです。この方法では、各観測値とそれに割り当てられた重心の間の二乗距離の合計をクラスター数の関数としてプロットします。プロット上の「エルボ」点は、クラスターを追加しても二乗距離の合計が大幅に減少しないクラスターの数を示します。

エルボー法は次の手順で要約できます。

• k 値の範囲に対して K-Means クラスタリングを実行します。
• 各 k 値の距離の二乗和を計算します。
• 距離の二乗和を k の関数としてプロットします。
• プロット上の「エルボ」点を特定します。

シルエット法

シルエット法は、K-Means クラスタリングで最適なクラスター数を決定するために使用されるもう 1 つのヒューリスティックです。この方法では、シルエット係数を計算することで、各観測値のクラスター割り当ての品質を測定します。シルエット係数の範囲は -1 ～ 1 で、値 1 は観測値が適切にクラスター化されていることを示し、値 -1 は観測値が誤分類されていることを示します。データ点iのシルエット係数を計算する式は次のとおりです。 $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ここで、 a(i)はiとそのクラスター内の他のすべてのデータ点の間の平均距離、 b(i)はiと他のすべてのクラスター (つまり、次に近い重心を持つクラスター) の間の最小平均距離です。クラスタリング全体のシルエット係数は、すべてのデータ ポイントのシルエット係数の平均です。

シルエットの方法は次の手順で要約できます。

• k 値の範囲に対して K-Means クラスタリングを実行します。
• 観測ごとにシルエット係数を計算します。
• 各 k 値の平均シルエット係数を計算します。
• 平均シルエット係数を k の関数としてプロットします。
• 最も高い平均シルエット係数を持つ k 値を特定します。