機械学習: 教師なし学習: 9 つのクラスタリングアルゴリズム

今日は、機械学習の教師なし学習における一般的なクラスタリング手法をいくつか紹介したいと思います。

教師なし学習では、データにラベルが付いていないため、教師なし学習で必要なのは、この一連のラベルなしデータをアルゴリズムに入力し、アルゴリズムにデータに暗黙的に含まれる構造を見つけさせることです。下の図のデータから、データセット内のポイントを 2 つの別々のポイントセット (クラスター) に分割できるという構造が見つかります。これらのクラスターを循環させることができるアルゴリズムは、クラスタリングアルゴリズムと呼ばれます。

クラスタリングアルゴリズムの応用

市場セグメンテーション: データベース内の顧客情報を市場ごとにグループ化し、異なる市場に応じて個別に販売したりサービスを改善したりします。
ソーシャルネットワーク分析: 最も頻繁にメールを送信する相手と、最も頻繁にメールを送信する相手に基づいて、親密なグループを見つけます。
コンピュータクラスターの編成: データセンターでは、コンピュータクラスターが連携して、リソースの再編成、ネットワークの再レイアウト、データセンターの最適化、データの通信を行うことがよくあります。
天の川の構成について学びましょう。この情報を活用して天文学を学びましょう。

クラスター分析の目的は、同じクラスターに割り当てられた観測値間のペアワイズ差が、異なるクラスター内の観測値間の差よりも小さくなるように、観測値をグループ (「クラスター」) に分割することです。クラスタリングアルゴリズムは、組み合わせアルゴリズム、ハイブリッドモデリング、パターン検索の 3 つのカテゴリに分類されます。

一般的なクラスタリングアルゴリズムには次のようなものがあります。

K平均法クラスタリング
階層的クラスタリング
凝集型クラスタリング
親和性の伝播
平均シフトクラスタリング
K平均法の二分法
DBスキャン
光学
バーチ

K平均法

K-means アルゴリズムは、最も人気のあるクラスタリング手法の 1 つです。

K 平均法は、1957 年にベル研究所のスチュアートロイドによって提案されました。当初はパルス符号変調に使用されていましたが、アルゴリズムは 1982 年まで公開されませんでした。 1965 年に Edward W. Forgy が同じアルゴリズムを公開したため、K-Means は Lloyd-Forgy と呼ばれることもあります。

クラスタリングの問題では、ラベルのないデータセットが与えられ、アルゴリズムによってこれらのデータを自動的に一貫したサブセットまたはクラスターに分割できることを期待します。 K-means アルゴリズムは、最も人気があり、広く使用されているクラスタリングアルゴリズムです。

K-means アルゴリズムの直感的な理解:

ラベルのないデータセット（上図の左側）があり、それを 2 つのクラスターに分割するとします。次に、K 平均法アルゴリズムを実行します。具体的な操作は次のとおりです。

最初のステップは、ランダムに 2 つのポイントを生成することです (データを 2 つのカテゴリにクラスタリングするため) (上の図の右側)。これらの 2 つのポイントは、クラスタセントロイドと呼ばれます。
2 番目のステップは、K 平均法アルゴリズムの内部ループを実行することです。 K-means アルゴリズムは、2 つのことを実行する反復アルゴリズムです。1 つ目はクラスターの割り当て、2 つ目は重心を移動することです。

内側のループの最初のステップは、クラスター割り当てを実行することです。つまり、各サンプルを走査し、クラスターセンターからの距離に基づいて各ポイントを異なるクラスターセンターに割り当てます。この例では、データセットを走査し、各ポイントを赤または青で色付けします。

内側のループの 2 番目のステップは、クラスターの中心を移動して、赤と青のクラスターの中心をそれぞれのポイントの平均 (各ポイントグループの平均位置) に移動することです。

次のステップは、新しいクラスターの中心からの距離に基づいてすべてのポイントを新しいクラスターに割り当て、クラスターの中心の位置が反復で変化しなくなり、ポイントの色も変化しなくなるまでこのサイクルを繰り返すことです。この時点で、K 平均法が集約されたと言えます。このアルゴリズムは、データ内の 2 つのクラスターを非常にうまく見つけ出します。

K-Means アルゴリズムの利点:

理解しやすく、計算速度が速く、大規模なデータセットに適しています。

欠点:

例えば、非球形クラスターの処理能力は低く、初期クラスター中心の選択の影響を受けやすく、クラスター数 K を事前に指定する必要があります。
さらに、データポイント間にノイズや外れ値がある場合、K-Means アルゴリズムによってそれらが間違ったクラスターに割り当てられる可能性があります。

階層的クラスタリング

階層的クラスタリングは、その名前が示すように、サンプルセットを特定のレベルに従ってクラスタ化します。ここでのレベルは、実際には特定の距離の定義を指します。

階層的クラスタリングの最終的な目標はカテゴリの数を減らすことなので、その動作はツリー図がリーフノードからルートノードに移動するプロセスに似ており、この動作は「ボトムアップ」とも呼ばれます。

より一般的には、階層的クラスタリングでは、初期化された複数のクラスターをツリーノードとして扱います。各反復で、類似のクラスターが新しい大きなクラスターにマージされ、このプロセスは 1 つのクラスター (ルートノード) だけが残るまで繰り返されます。

階層的クラスタリング戦略は、凝集型（ボトムアップ）と分割型（トップダウン）の 2 つの基本パラダイムに分けられます。

階層的クラスタリングの反対は、DIANA (Divise Analysis) とも呼ばれる分割クラスタリングで、「トップダウン」方式で動作します。

K-means を適用した結果は、検索するクラスターの数の選択と開始構成の割り当てによって異なります。対照的に、階層的クラスタリング手法ではそのような仕様は必要ありません。代わりに、ユーザーは、2 つの観測グループ間のペアワイズ非類似度に基づいて、観測の (互いに素な) グループ間の非類似度の尺度を指定する必要があります。名前が示すように、階層表現が生成され、階層の各レベルのクラスターは、次の下位レベルのクラスターをマージすることによって作成されます。最下位レベルでは、各クラスターに 1 つの観測値が含まれます。最高レベルでは、すべてのデータを含むクラスターが 1 つだけあります。

アドバンテージ：

距離とルールの類似性は定義が簡単で、制限もほとんどありません。
クラスターの数を事前に決定する必要はありません。
クラスの階層関係を発見できます。
他の形状にクラスター化できます。

欠点:

計算の複雑さが高すぎる。
特異値も大きな影響を与える可能性があります。
アルゴリズムはチェーン状に集まる可能性があります。

凝集型クラスタリング

凝集型クラスタリングは、各データポイントを初期クラスターとして扱い、停止条件に達するまで徐々にそれらをより大きなクラスターにマージするボトムアップクラスタリングアルゴリズムです。このアルゴリズムでは、各データポイントは最初に個別のクラスターとして扱われ、その後、すべてのデータポイントが 1 つの大きなクラスターに結合されるまで、クラスターは段階的に結合されます。

アドバンテージ：

さまざまな形状やサイズのクラスターに適用でき、クラスターの数を事前に指定する必要はありません。
このアルゴリズムは、クラスター階層を出力することで、簡単に分析および視覚化することもできます。

欠点:

特に大規模なデータセットを処理する場合は計算の複雑さが増し、大量の計算リソースとストレージスペースが必要になります。
このアルゴリズムは初期クラスターの選択にも敏感であり、異なるクラスタリング結果をもたらす可能性があります。

親和性の伝播

アフィニティ伝播 (AP) アルゴリズムは、通常、近隣伝播アルゴリズムまたはアフィニティ伝播アルゴリズムとして翻訳されます。

アフィニティ伝播は、グラフ理論に基づくクラスタリングアルゴリズムであり、データ内の「標本」(代表的なポイント) と「クラスター」(クラスター) を識別することを目的としています。 K-Means などの従来のクラスタリングアルゴリズムとは異なり、Affinity Propagation では、クラスターの数を事前に指定する必要はなく、クラスターの中心をランダムに初期化する必要もありません。代わりに、データポイント間の類似性を計算することで、最終的なクラスタリング結果を取得します。

アドバンテージ：

最終的なクラスター数を指定する必要はありません
新しいクラスターセンターを生成する代わりに、既存のデータポイントが最終的なクラスターセンターとして使用されます。
モデルはデータの初期値の影響を受けません。
初期の類似性マトリックスデータの対称性は必要ありません。
k-center クラスタリング法と比較すると、結果の二乗誤差は小さくなります。

欠点:

このアルゴリズムは計算が非常に複雑であり、大量のストレージスペースと計算リソースを必要とします。
ノイズポイントや外れ値を処理する能力が弱い。

平均シフトクラスタリング

平均シフトクラスタリングは、密度ベースのノンパラメトリッククラスタリングアルゴリズムです。基本的な考え方は、データポイントの密度が最も高い場所 (「局所的最大値」または「ピーク」と呼ばれる) を見つけることで、データ内のクラスターを識別することです。アルゴリズムの中核は、各データポイントに対してローカル密度推定を実行し、密度推定の結果を使用してデータポイントの移動方向と距離を計算することです。アルゴリズムの中核は、各データポイントに対してローカル密度推定を実行し、密度推定の結果を使用してデータポイントの移動方向と距離を計算することです。

アドバンテージ：

クラスターの数を指定する必要がなく、複雑な形状のクラスターにも適しています。
このアルゴリズムは、ノイズの多いデータも効果的に処理できます。

欠点:

特に大規模なデータセットを処理する場合は計算の複雑さが増し、多くの計算リソースとストレージスペースが必要になります。
このアルゴリズムは初期パラメータの選択にも敏感であり、パラメータの調整と最適化が必要です。

K平均法の二分法

二分 K 平均法は、K 平均法アルゴリズムに基づく階層的クラスタリングアルゴリズムです。基本的な考え方は、すべてのデータポイントを 1 つのクラスターに分割し、そのクラスターを 2 つのサブクラスターに分割し、各サブクラスターに K 平均法アルゴリズムを個別に適用し、クラスターの数が所定の数に達するまでこのプロセスを繰り返すことです。

このアルゴリズムは、まずすべてのデータポイントを 1 つの初期クラスターと見なし、次にこのクラスターに K-Means アルゴリズムを適用し、クラスターを 2 つのサブクラスターに分割して、各サブクラスターの二乗誤差の合計 (SSE) を計算します。次に、二乗誤差の合計が最大となるサブクラスターが選択され、再度 2 つのサブクラスターに分割され、このプロセスがクラスターの所定の数に達するまで繰り返されます。

アドバンテージ：

精度と安定性が高く、大規模なデータセットを効果的に処理でき、初期のクラスター数を指定する必要がありません。
このアルゴリズムは、クラスタリング階層を出力することもできるため、分析や視覚化が容易になります。

欠点:

特に大規模なデータセットを処理する場合は計算の複雑さが増し、大量の計算リソースとストレージスペースが必要になります。
さらに、このアルゴリズムは初期クラスターの選択にも敏感であり、異なるクラスタリング結果が生じる可能性があります。

DBスキャン

ノイズを含むアプリケーションの密度ベース空間クラスタリング (DBSCAN) は、典型的な密度ベースの空間クラスタリングアルゴリズムです。

密度ベースの方法の特徴は、距離ではなく密度に依存するため、距離ベースのアルゴリズムでは「球状の」クラスターしか発見できないという欠点を克服できることです。

DBSCAN アルゴリズムの基本的な考え方は、特定のデータポイントについて、その密度が特定のしきい値に達するとクラスターに属し、それ以外の場合はノイズポイントとみなされるというものです。

アドバンテージ：

このタイプのアルゴリズムは、距離ベースのアルゴリズムでは「準円形」（凸型）のクラスターしか見つけられないという欠点を克服できます。
任意の形状のクラスターを見つけることができ、ノイズの多いデータの影響を受けません。
クラスターの数を指定する必要はありません。
アルゴリズムには、スキャン半径 (eps) と含まれるポイントの最小数 (min_samples) の 2 つのパラメーターのみがあります。

欠点:

計算の複雑さ: 最適化を行わない場合、アルゴリズムの時間計算量は O(N^{2}) であり、通常は R ツリー、kd ツリー、ボールを使用できます。
ツリーインデックスは計算を高速化し、アルゴリズムの時間計算量を O(Nlog(N)) に削減するために使用されます。
EPSの影響を大きく受けます。クラス内のデータ分布密度が不均一な場合、eps が小さいと、密度が小さいクラスターは類似した特性を持つ複数のクラスターに分割され、eps が大きいと、距離が近く密度が大きいクラスターは 1 つのクラスターに結合されます。高次元データでは、次元の呪いにより eps の選択が困難になります。
距離の式の選択によって異なります。次元の呪いのため、距離メトリックは重要ではありません。
EPS とメトリックの選択が難しいため、密度差が大きいデータセットには適していません。

光学

OPTICS (Ordering Points To Identify the Clustering Structure) は、クラスターの数を自動的に決定し、任意の形状のクラスターを検出し、ノイズの多いデータを処理できる密度ベースのクラスタリングアルゴリズムです。

OPTICS アルゴリズムの中心的な考え方は、特定のデータポイントについて、他のポイントまでの距離を計算することで、密度の観点からの到達可能性を決定し、密度ベースの距離グラフを構築するというものです。次に、距離マップをスキャンすることで、クラスターの数が自動的に決定され、各クラスターが分割されます。

アドバンテージ：

クラスターの数を自動的に決定し、任意の形状のクラスターを処理し、ノイズの多いデータを効果的に処理できます。
このアルゴリズムは、クラスタリング階層を出力することもできるため、分析や視覚化が容易になります。

欠点:

特に大規模なデータセットを処理する場合は計算の複雑さが増し、大量の計算リソースとストレージスペースが必要になります。
このアルゴリズムでは、密度の差が大きいデータセットの場合、クラスタリング結果が悪くなる可能性があります。

バーチ

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) は、階層的クラスタリングに基づくクラスタリングアルゴリズムです。大規模なデータセットを迅速に処理でき、任意の形状のクラスタに優れた効果を発揮します。

BIRCH アルゴリズムの中心的な考え方は、データセットに対して階層的クラスタリングを実行することでデータサイズを徐々に削減し、最終的にクラスター構造を取得することです。 BIRCH アルゴリズムは、CF ツリーと呼ばれる B ツリーに似た構造を使用します。これにより、サブクラスターをすばやく挿入および削除でき、クラスターの品質と効率を確保するために自動的にバランスをとることができます。