K-平均クラスタリングのためのワンストップショップ

「K-平均クラスタリングを実現するワンストップショップ」

似たようなデータポイントをクラスタリングして意味を成す方法はありますか？まあ、K-Meansはその一つです。この記事では、K-Meansクラスタリングについてほとんどすべてをまとめています。ただし、私はコードを書いていません 🙂

アウトライン —

1. K-Meansクラスタリングとは
2. クラスタの特性
3. K-Meansクラスタリングのアルゴリズム
4. 収束/停止基準
5. セントロイドの初期化: K-Means ++
6. 最適なKの選択
7. クラスタの品質評価

〜類似するものは一緒に群れる

• ９／１０から１５／１０までの週のトップ重要なコンピュータビジョン論文
• ユニバーサルシミュレータ(UniSim)をご紹介します：生成モデリングを通じたリアルワールドの対話をインタラクティブにシミュレートするシミュレータ
• ChatGPT vs. BARD’の比較

1. K-Meansクラスタリングとは？

K-Meansクラスタリングは、我々のデータ内で似たようなデータポイントをクラスタ化するための教師なし学習アルゴリズムです。これらのクラスタは、データポイントが共有する特徴を表し、それらの類似性を示します。

簡単に言えば、K-MeansはほぼKNNのようなもので、類似性のためにK個のの近くのポイントを見ます。K-Meansクラスタリングでは、ポイントがクラスタ内にグループ化され、共通の特性を共有するようにK個のクラスタを形成します。以下の図がより明確にします:

私たちは、データを入力パラメータとして渡すだけで、K-Meansを使用して上記のようなグラフを実現することができます。データポイントを基にクラスタを形成しているため、これらのポイントに対してyラベルは必要ありません。したがって、クラスタリングは教師なし学習アルゴリズムであり、データポイントに対するラベルは不要です。

クラスタリングの応用例 —

1. 顧客セグメンテーション 2. ドキュメントセグメンテーション 3. 画像セグメンテーション 4. 推薦システムなど

2. クラスタの特性

これらのクラスタには、意味のある特性があります。

1. クラスタ内のすべてのデータポイントはできるだけ似ているべきです — クラスタ内のデータポイントは非常に近いです。つまり、特徴空間では、データポイントは類似の特性を表します。さらに、似たようなポイントはより良くクラスタを形成します。したがって、クラスタ内のポイントはできるだけ似ているべきです。
2. 異なるクラスタのデータポイントはできるだけ異なるべきです — 異なるクラスタのデータポイントは互いに遠いです。つまり、特徴空間では、これらのポイントは非常に異なる特性を表します。さらに、異なるポイントはクラスタを形成しません。したがって、異なるクラスタのポイントはできるだけ異なるべきです。
3. 各クラスタには重心が存在します — 形成する各クラスタには、それに関連するすべてのポイントの重心があります。この重心は、クラスタを形成し、クラスタ内のポイントの平均に基づいて調整されます。

〜まあ、特性についてはあまり気にしないでください。それは単なるつまらない理論です。次の部分が楽しいです

3. クラスタリングのためのアルゴリズム

このアルゴリズムが美しいクラスタを生成する方法について詳しく見ていきましょう。

アルゴリズム —

• [ステップ1] — クラスタの数(K)を選択 — 現時点では任意に選択することができます。後で値Kの選び方を決めるためです。アルゴリズムを開始する際には、通常、ランダムなK=3の値が選ばれます。
• [ステップ2] — K個のランダムな点をK-セントロイドとして選択 — これらの点は各クラスタのセントロイドを形成するためにランダムに選択されます。これらの点は、データや別の場所からランダムに選ぶことができます。
• [ステップ3] — 各データポイントを最も近いセントロイドに割り当てる — データセット内の各点とすべてのK-セントロイドとの距離を計算します。その点は、そのセントロイドからの最も小さい距離を持つセントロイドに割り当てられます。以下のように視覚化することができます：

このプロセスは各点に対して繰り返され、最終的にすべての点がいずれかのセントロイドに割り当てられます。この方法で、K個のクラスタが得られます。通常、点とセントロイドの距離を計算するためにユークリッド距離が使用されます。

• [ステップ4] — 新しいセントロイドを計算する — すべての点をいずれかのセントロイドに割り当てた後、各クラスタのすべての点の平均を取ることで新しいセントロイドを計算します。新しいセントロイドは、すべてのデータポイントのx座標とy座標の平均を取ることで計算することができます。

ここで、‘m’は特定のクラスタ内のデータポイントの数です。

• [ステップ5] — 収束/停止条件が満たされるまでステップ3とステップ4を繰り返す

視覚化しましょう：

1. [ステップ1] — k = 22を選択しましょう。 [ステップ2] —

3. [ステップ3] —

4. [ステップ4] —

5. [ステップ5] —

4. 収束/停止条件

上記のアルゴリズムが収束しない場合、無限に繰り返されます。そのため、上記のアルゴリズムには停止基準が必要です。以下の停止基準があります：

1. 特定のクラスタに割り当てられたデータポイントが変化しない — データポイントが新しいクラスタに割り当てられるまでアルゴリズムを実行します。 これは非常に遅く、多くの時間を要する可能性があります。
2. 重心が変わらない — 新しく計算された重心が前の重心と同じであるまでアルゴリズムを実行します。 これは非常に遅く、多くの時間を要する可能性があります。
3. データポイントから重心までの距離が最小である — データポイントから重心までの距離の閾値を設定します。この閾値が達成されると、アルゴリズムは停止します。 これは速いですが、距離の閾値を非常に注意して選択する必要があります。
4. 固定回数の反復が終了した — 反復の回数の閾値を設定し、この閾値に達すると停止します。 これは速いですが、不適切な閾値設定によりクラスタの形成が悪くなる可能性があります。

これらの停止条件を実装することで、早期収束と適切なクラスタリングを行うことができます。

5. 重心の初期化

K-Meansでは、重心をランダムに初期化します。これにはいくつかの問題があり、クラスタの形成が悪くなる可能性があります。

• 重心が遠くにある（外れ値）場合、この重心に割り当てられるデータポイントが存在しないかもしれません。これにより、同じ重心に複数のクラスタが割り当てられる可能性があります。
• 2つ以上の重心が非常に近い位置に初期化された場合、同じクラスタに複数の重心が割り当てられる可能性があります。

これらの問題は、以下の図で視覚化できます :

そのため、重心の初期化にはより良い方法が必要です。以下の2つのアプローチのいずれかを使用できます :

1. 最適なクラスタを得るまで何度もK-Meansを繰り返す
2. K-Means ++アルゴリズムを使用する

前者は明らかな理由から時間の面で非常に非効率です。そのため、重心の初期化にはK-Means ++アルゴリズムを使用します。

K-Means ++

これは重心の初期化のためのアルゴリズムであり、K-Meansアルゴリズムの他の部分は同じです。

アルゴリズム：

1. 最初の重心をランダムに選択します
2. 次に、各点から最も近い重心（アルゴリズムの最初の重心）までの距離を計算します
3. 次に、各点に確率値を割り当てます。確率値は、点と前の重心との距離に比例します。つまり、最も距離が遠い点が次の重心として選択される確率値が最も高くなります。
4. これらのステップをK個の重心が得られるまで繰り返します。

このような初期化により、各重心が他の重心からできるだけ遠ざかることが保証されます。したがって、1つのクラスタに2つ以上の重心が割り当てられることはありませんし、同じ重心に複数のクラスタが割り当てられることもありません。

その後、データポイントは最も近い重心に割り当てられ、以降の処理がK-Meansアルゴリズムによって続けられます。

6. 最適なKの選択

最適なKの値を選ぶことは非常に重要です。美しく構造化されたクラスタや不整理なクラスタにつながる可能性があります。

Kの値を選ぶ方法はいくつかありますが、最も最適な方法は「エルボー法」と呼ばれる方法です。ここでの目的は、クラスタ内の平方誤差の和（WCSSE）が最も少ないKの値を見つけることです。

WCSSEは、同じクラスタ内のデータポイントから重心までの二乗距離の合計を表します。

エルボーメソッド

エルボーメソッドは、各Kの結果を見てK値を選択できる手法です。

WCSSEは、すべてのクラスタに対して計算され、異なるK値に対してグラフにプロットされます。グラフ上のWCSSEが急激に減少するポイントが、私たちが探しているポイントです。このポイントは、WCSSEが急激に減少しほぼ一定になる特定のK値を示しています。したがって、このポイント以降、Kの値を増やしてもWCSSEはあまり減少せず、このポイントが最適なK値となります。

エルボーメソッドの手順は以下の通りです：

• 1から10までの範囲でKを選択します
• この範囲の各K値について、すべてのクラスタのWCSSEを見つけます
• 次に、Kに対してWCSSEをプロットします
• WCSSEの値が急激に減少し、エルボーのような形になっているKが、私たちが選択するKの最適な値です

上のグラフからわかるように、K値が5の場合、WCSSEが急激に減少し、その後ほぼ一定になります。したがって、5つのクラスタを超えると、WCSSEはあまり減少しません。したがって、K=5を選択します。

7. クラスタの品質評価

クラスタが意味を持つためには、各クラスタの品質を評価する必要があります。品質とは、クラスタがデータをどれだけよく説明しているかを指します。そのためには、クラスタの特性に戻る必要があります。すべての特性を満たすクラスタは、良いクラスタとみなされます。では、クラスタの特性を数学的に評価するにはどうすればいいのでしょうか？

評価する方法は2つあります:1. イントルーダ2. ダン指数

1. イントルーダ

イントルーダは、特定のクラスタの点とクラスタの中心点の距離の合計を指します。これは、クラスタ内の点の間の距離を計算しているため、イントラクラスタ距離とも考えることができます。クラスタの中心点C1に対して、イントルーダを次のように定義できます：

ここで、iは1からm（そのクラスタ内の点の数）までの範囲で変化します

上の図は、クラスタ間の距離またはイントルーダを示しています。

クラスタが意味を持つためには、その点と重心の間の距離が小さいほどよいです。したがって、クラスタは最初の特性を満たすことができます。

したがって、良いクラスタのためには、イントルーダの値ができるだけ小さくなる必要があります。

2. ダン指数

ダン指数はクラスタの2番目の特性を測定する指標です。クラスタ間の距離を測定し、2つのクラスタの特性の違いを示します。ダン指数は、クラスタ間およびクラスタ内の距離を計算することで行います。

クラスタ間の距離は、2つのクラスタ間の距離を指します。この差は、測定方法によっても異なる場合があります。

— 2つのクラスタの重心の差である場合があります — 2つのクラスタの最も遠い点の差である場合があります — 2つのクラスタの最も近い点の差である場合があります

クラスタ間距離を測定するために選ばれた基準によらず、ダン指数は以下のように表されます：

2つのクラスタができるだけ異なる/遠い場合、分子は非常に大きくなり、分母は非常に小さくなる必要があります。したがって、

• 分子を大きな値にするためには、2つのクラスタ間の最小距離[min(クラスタ間距離)]が非常に大きい値である必要があります。
• 分母を小さな値にするためには、各クラスタの点とその重心の間の最大距離[max(クラスタ内距離)]が非常に小さい値である必要があります。

クラスタが重要であるためには、クラスタ間の距離ができるだけ大きい値である必要があります。したがって、クラスタは2番目の条件を満たす可能性があります。

したがって、ダン指数は良いクラスタの場合、できるだけ大きくなる必要があります。

うーん、それでK-Meansクラスタリングについてのほぼすべてが語られました。それでは、コーディングしましょう。

これもチェックしてみてくださいね—

1. KNN
2. ロジスティック回帰
3. サポートベクターマシン
4. ナイーブベイズ
5. 評価メトリック – クラス分類

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!