1 つの記事でクラスタリング アルゴリズムを理解する

1. クラスタリングの基本概念

1.1 定義

クラスタリングはデータマイニングにおける概念であり、特定の基準（距離など）に従ってデータセットを異なるクラスまたはクラスターに分割し、同じクラスター内のデータオブジェクトの類似性が最大になり、異なるクラスター内のデータオブジェクトの相違が最大になるようにします。つまり、クラスタリング後、同じカテゴリのデータは可能な限りクラスタリングされ、異なるカテゴリのデータは可能な限り分離されます。

1.2 クラスタリングと分類の違い

クラスタリングとは、簡単に言えば、類似するものをグループ化することです。クラスタリングを行う際、特定のカテゴリが何であるかは気にしません。私たちの目標は、類似するものをグループ化することだけです。したがって、クラスタリング アルゴリズムは通常、類似性の計算方法を知っていれば動作を開始できるため、クラスタリングでは通常、学習にトレーニング データを使用する必要はなく、機械学習ではこれを教師なし学習と呼びます。

分類。分類器の場合、通常は「これは特定のカテゴリに分類されます」などの例をいくつか伝える必要があります。理想的には、分類器は取得したトレーニング セットから「学習」し、未知のデータを分類する能力を持つようになります。トレーニング データを提供するこのプロセスは、通常、教師あり学習と呼ばれます。

1.3 クラスタリングプロセス

1. データ準備: 特徴の正規化と次元削減を含む。
2. 特徴選択: 初期特徴から最も効果的な特徴を選択し、ベクトルに保存します。
3. 特徴抽出: 選択された特徴を変換して新しい顕著な特徴を形成します。
4. クラスタリング（またはグループ化）：まず、適切な特徴タイプの距離関数を選択（または新しい距離関数を構築）して近接度を測定し、次にクラスタリングまたはグループ化を実行します。
5. クラスタリング結果の評価：クラスタリング結果の評価を指します。評価には、外部妥当性評価、内部妥当性評価、相関テスト評価の 3 つの主な種類があります。

1.4 クラスタリングアルゴリズムの品質を測定する基準

1. 大規模なデータセットを処理する能力。
2. ギャップのあるネストされたデータを含む任意の形状のデータを処理する機能。
3. アルゴリズム処理の結果がデータ入力の順序に関連しているかどうか、つまりアルゴリズムがデータ入力の順序から独立しているかどうか。
4. データノイズを処理する能力。
5. クラスターの数を事前に知る必要があるかどうか、およびユーザーがドメイン知識を提供する必要があるかどうか。
6. 多くの属性を持つデータを処理するアルゴリズムの能力、つまり、データの次元に敏感であるかどうか。

2. クラスタリング手法の分類

主に、階層型クラスタリングアルゴリズム、パーティション型クラスタリングアルゴリズム、密度ベースクラスタリングアルゴリズム、グリッドベースクラスタリングアルゴリズム、モデルベースクラスタリングアルゴリズムなどに分けられます。

2.1 階層的クラスタリングアルゴリズム

ツリー クラスタリング アルゴリズムとも呼ばれ、階層構造を通じてデータを繰り返し分割または集約します。代表的なものとしては、BIRCH アルゴリズム、CURE アルゴリズム、CHAMELEON アルゴリズム、シーケンス データ大まかなクラスタリング アルゴリズム、グループ間平均アルゴリズム、最遠近傍アルゴリズム、最近傍アルゴリズムなどがあります。

典型的な凝集型階層的クラスタリング:

各オブジェクトは最初にクラスターと見なされ、その後、すべてのオブジェクトが 1 つのクラスターに含まれるか、終了条件が満たされるまで、これらのアトミック クラスターはより大きなクラスターにマージされます。

アルゴリズムフロー:

1. 各オブジェクトをクラスとして扱い、それらの間の最小距離を計算します。
2. 距離が最小の 2 つのクラスを新しいクラスにマージします。
3. 新しいクラスとすべてのクラス間の距離を再計算します。
4. すべてのクラスが最終的に 1 つのクラスに結合されるまで、2 と 3 を繰り返します。

2.2 パーティションクラスタリングアルゴリズム

クラスターの数またはクラスター中心を事前に指定し、反復を繰り返すことで目的関数の誤差値を徐々に減らしていき、収束させて最終結果を得ます。 K-means、K-modes-Huang、K-means-CP、MDS_CLUSTER、特徴重み付けファジークラスタリング、CLARANS など。

古典的な K-means アルゴリズムのプロセス:

1. 最初にクラスターの中心を表す k 個のオブジェクトをランダムに選択します。
2. 残りの各オブジェクトについては、各クラスターの中心からの距離に応じて最も近いクラスターに割り当てます。
3. 各クラスターの平均値を再計算し、新しいクラスターの中心に更新します。
4. 基準関数が収束するまで手順 2 と 3 を繰り返します。

2.3 モデルベースのクラスタリングアルゴリズム

各クラスターにはモデルが想定され、特定のモデルに最もよく適合するデータが検索されます。同じ「クラス」のデータは同じ確率分布に属します。つまり、データは基礎となる確率分布に従って生成されると想定されます。主に統計モデルに基づく方法とニューラルネットワークモデルに基づく方法、特に確率モデルに基づく方法があります。モデルベースのアルゴリズムでは、データ ポイントの空間分布を反映する密度関数を構築することでクラスターを特定できます。モデルベースのクラスタリングは、特定のデータと何らかのデータ モデル間の適合性を最適化しようとします。

SOM ニューラル ネットワーク アルゴリズム:

このアルゴリズムは、入力オブジェクトに何らかの位相構造または秩序があると仮定し、入力空間 (n 次元) から出力平面 (2 次元) への次元削減マッピングを実現します。このマッピングは位相特徴を保存する特性があり、実際の脳の処理と強い理論的つながりがあります。

SOM ネットワークは入力層と出力層で構成されます。入力層は高次元の入力ベクトルに対応し、出力層は 2 次元グリッド上に編成された一連の順序付けられたノードで構成されます。入力ノードと出力ノードは重みベクトルによって接続されます。学習プロセス中に、その出力層ユニットとの距離が最短となるユニット、つまり勝利ユニットが見つかり、それが更新されます。同時に、出力ノードが入力ベクトルのトポロジ特性を維持するように、隣接領域の重みが更新されます。

アルゴリズムフロー:

1. ネットワークを初期化し、出力層の各ノードの重みに初期値を割り当てます。
2. 入力サンプルから入力ベクトルをランダムに選択し、入力ベクトルとの距離が最小となる重みベクトルを見つけます。
3. 勝利ユニットを定義し、勝利ユニットの近傍の重みを調整して入力ベクトルに近づけます。
4. 新しいサンプルを提供し、トレーニングを実施します。
5. 近傍半径を縮小し、学習率を下げ、許容値より小さくなるまで繰り返し、クラスタリング結果を出力します。

2.4 密度ベースのクラスタリングアルゴリズム

主なアイデア:

近傍の密度（オブジェクトまたはデータポイントの数）が一定の閾値を超えている限り、クラスタリングは継続されます。

不規則な形状のクラスタリング問題を解決するのに優れており、空間情報処理、SGC、GCHL、DBSCAN アルゴリズム、OPTICS アルゴリズム、DENCLUE アルゴリズムなどで広く使用されています。

DBスキャン:

集中したエリアでより効果的です。任意の形状のクラスターを発見するために、このタイプの方法では、クラスターをデータ空間内の低密度エリアで区切られた密なオブジェクトエリアと見なします。これは、高密度の接続エリアに基づく密度ベースのクラスタリング方法です。このアルゴリズムは、十分に高い密度を持つエリアをクラスターに分割し、ノイズの多い空間データ内の任意の形状のクラスターを発見します。

2.5 グリッドベースクラスタリングアルゴリズム

グリッドベースの方法では、オブジェクト空間を有限数のセルに量子化し、グリッド構造を形成します。すべてのクラスタリング操作は、このグリッド構造 (つまり、量子化された空間) 上で実行されます。この方法の主な利点は、データ オブジェクトの数に依存せず、量子化された空間の各次元のセルの数のみに依存する高速処理速度です。ただし、アルゴリズムの効率が向上すると、クラスタリング結果の精度が低下します。密度ベースのアルゴリズムと組み合わせて使用​​されることが多いです。

代表的なアルゴリズムとしては、STING アルゴリズム、CLIQUE アルゴリズム、WAVE-CLUSTER アルゴリズムなどがあります。

2.6 新しい開発手法

制約ベースの方法:

現実世界のクラスタリング問題には、複数の制約が存在する場合が多くありますが、この手法では、対応する制約を正確に表現できず、制約知識を推論に有効活用できず、動的制約を効果的に活用できないため、広く普及・適用されていません。ここでの制約は、個々のオブジェクトに対する制約、またはクラスタリング パラメータに対する制約であり、どちらも関連分野の経験的知識から得られます。この方法の重要な応用は、2 次元空間データを障害物データとクラスタリングすることです。 COD (障害物距離によるクラスタリング) は、この種の問題に対処するための典型的なアルゴリズムです。その主な考え方は、一般的なユークリッド距離の代わりに 2 点間の障害物距離を使用して、それらの間の最小距離を計算することです。

ファジーベースのクラスタリング手法:

ファジー集合理論に基づくクラスタリング手法では、サンプルは一定の確率で特定のクラスに属します。代表的なものとしては、目的関数に基づくファジークラスタリング法、類似関係とファジー関係に基づく方法、ファジー同値関係に基づく推移閉包法、ファジーグラフ理論に基づく最小全域木法、データセットの凸分解、動的計画法、識別不可能な関係に基づく方法などがあります。

FCM ファジー クラスタリング アルゴリズムのプロセス:

1. データ マトリックスを正規化します。
2. ファジー類似度行列を確立し、メンバーシップ行列を初期化します。
3. アルゴリズムは、目的関数が最小値に収束するまで反復を開始します。
4. 反復結果に応じて、最終的なメンバーシップ マトリックスによってデータが属するクラスが決定され、最終的なクラスタリング結果が表示されます。

粒度ベースのクラスタリング手法:

粒子サイズの原理に基づくと、研究はまだ不完全です。

量子クラスタリング:

物理学における量子のメカニズムと特性にヒントを得た量子理論は、クラスタリングが初期値に依存し、カテゴリの数を指定する必要があるという問題を解決するために使用できます。良い例としては、関連する点のポットスピンと統計メカニズムに基づく量子クラスタリングモデルが挙げられます。クラスタリング問題を物理システムとして扱います。また、多くの例から、このアルゴリズムは、従来のクラスタリング アルゴリズムでは解決できないいくつかのクラスタリング問題に対して、比較的満足のいく結果を得ていることがわかります。

カーネルクラスタリング:

カーネル クラスタリング メソッドは、サンプル機能の最適化プロセスを追加し、Mercer カーネルを使用して入力空間内のサンプルを高次元機能空間にマッピングし、機能空間内でクラスタリングを実行します。カーネル クラスタリング法は汎用性が高く、パフォーマンスの面では従来のクラスタリング アルゴリズムを上回ります。非線形マッピングにより有用な特徴をより適切に区別、抽出、増幅できるため、より正確なクラスタリングが実現します。同時に、アルゴリズムの収束も速くなります。従来のクラスタリング アルゴリズムが失敗した場合でも、カーネル クラスタリング アルゴリズムは正しいクラスタリングを取得できます。代表的なアルゴリズムとしては、SVDD アルゴリズムや SVC アルゴリズムなどがあります。

スペクトルクラスタリング:

まず、与えられたサンプルデータセットに従って、ペアになったデータポイントの類似性を記述する類似性行列が定義され、行列の固有値と固有ベクトルが計算されます。次に、異なるデータポイントをクラスタ化するために適切な固有ベクトルが選択されます。スペクトルクラスタリングアルゴリズムは、もともとコンピュータービジョンやVLSI設計などの分野で使用されていましたが、最近になって機械学習でも使用され始め、急速に国際的に機械学習分野の研究のホットスポットとなっています。

スペクトル クラスタリング アルゴリズムは、グラフ理論のスペクトル グラフ理論に基づいています。その本質は、クラスタリング問題をグラフの最適分割問題に変換することです。これは、ポイントツーポイント クラスタリング アルゴリズムです。

クラスタリング アルゴリズムの簡単な分類アーキテクチャ図

一般的なアルゴリズム機能の比較表

3. 簡単なコード例

4. 学習教材

クラスタリング アルゴリズムは、機械学習またはデータ マイニングの分野に属します。その範囲は比較的狭く、一般的には機械学習の一部、またはデータ マイニングの分野のアルゴリズムの一種と見なされています。機械学習と組み合わせて学習できます。

Scikit Learn: NumPy と SciPy をベースにした Python 用の機械学習ライブラリ。

スタンフォード機械学習: スタンフォードの機械学習コースは、Coursera で視聴できます。このコースは Andrew Ng が指導しており、説明が非常にわかりやすいです。

データ サイエンスと機械学習のリソースのリスト: 専門家によってまとめられた学習リソースのリスト。