クラスタリングとは

機械学習でのクラスタリングの使用には、データセットの初期探索から進行中のプロセスの監視まで、さまざまな方法があります。新しいデータセットの探索的データ分析に使用すれば、根本的な傾向、パターン、外れ値を把握できます。あるいは、大きなデータセットを複数のデータセットに分割したり、次元削減を使用して削減したりすることが必要な場合もあります。このような場合、クラスタリングは前処理のステップになります。

クラスターの例には、音楽のジャンル、さまざまなユーザー・グループ、市場セグメンテーションの主要なセグメント、サーバー・クラスター上のネットワーク・トラフィックの種類、ソーシャル・ネットワークの友達グループ、その他の多種多様なカテゴリーがあります。クラスタリングのプロセスでは、データの1つの特徴だけを使用することも、データに存在するすべての特徴を使用することもできます。

クラスタリングにはどのようなカテゴリーが存在するのか、また何がそれらのカテゴリーを定義しているのかを理解するために、クラスタリングをデータ内の自然なグループ化を見つけようとする試みであると考えるとわかりやすいでしょう。クラスターは、データ・ポイント間の基礎的な関係を見つけて、カテゴリー間でどのような特徴や特性が共有されているかを確認するのに役立ちます。使用するクラスタリング・アルゴリズムによっては、データから外れ値を削除したり、外れ値としてラベルを付けたりできる場合があります。さらにクラスタリングは、どのデータ・ポイントがクラスター内に含まれていないか、またはどのデータ・ポイントがクラスターとの関連性が弱く、データ生成プロセスで異常である可能性があるのかを検出するので、異常検出にも役立ちます。

クラスタリングを使用すると、データの次元数を減らすことで、大規模なデータ・セットの複雑さを軽減することもできます。カテゴリーが2つまたは3つの特徴だけで定義されている場合は、無関係な特徴を削除するか、PCAなどの次元削減手法を使用できる可能性があります。クラスタリングは、データ・セットの視覚化を作成して、データの新たなプロパティーや、クラスター間の密度や関係を確認する場合にも非常に役立ちます。

クラスタリング・アルゴリズムは、ハード・クラスタリング（各データ・ポイントが単一のクラスターにのみ属し、クラスター内にあるかどうかを示すバイナリー値を持つ）を実行するか、ソフト・クラスタリング（各データ・ポイントに、識別された各クラスターに属する確率が与えられる）を実行するかで区別されることがあります。最適なこれ1つというクラスタリング・プロセスは存在せず、ニーズと扱うデータに最も適したアプローチを選択する必要があります。

クラスターを定義する方法は複数あり、さまざまなクラスタリング・アルゴリズムがあります。入力データのサイズ、データの次元、カテゴリーの厳格さ、データ・セット内のクラスターの数に応じて、さまざまなタイプのモデルにさまざまなアプローチが適します。アルゴリズムは、あるデータ・セットでは非常にうまく機能するものの、別のデータ・セットではうまくいかないという場合があることに注意してください。このセクションでは、クラスタリングに対して一般的に使用される5つのアプローチについて説明します。この記事の対象範囲外であるため取り上げていない手法もあります（スペクトル・クラスタリングやMean-Shiftクラスタリングなど）。

重心ベース・クラスタリングは、クラスタリング手法の一種であり、データ・セットを重心間の距離に基づいて類似のグループに区分または分割します。各クラスターの重心または中心は、データによってクラスター内のすべてのポイントの平均値または中央値になります。

最も一般的に使用される重心ベース・クラスタリング手法の1つは、K-means法クラスタリング・アルゴリズムです。K-means法では、各クラスターの中心が、重心までの距離尺度（主にユークリッド距離）を使用してクラスターを定義すると仮定します。クラスタリングを初期化するには、K-means法の「K」を表す予想されるクラスターの数を指定すると、アルゴリズムはその数に一致する適切なクラスターをデータ全体から見つけようとします。特定のデータ・セット内の最適なk個のクラスターは、各ポイントとその割り当てられたクラスター重心の間の合計距離を繰り返し最小化することによって特定されます。

K-means法はハード・クラスタリング・アプローチであり、各データ・ポイントは個別のクラスターに割り当てられ、クラスターのメンバーシップに関連付けられた確率はありません。K-means法は、クラスターのサイズがほぼ同じで、データ全体に大きな外れ値や密度の変化がない場合に適しています。K-means法は、データが高次元の場合や、クラスターのサイズや密度が大きく異なる場合に、パフォーマンスが低下することがよくあります。また、K-means法は、クラスター内のすべての値の平均値に基づいて重心を確立しようとするため、外れ値に対して特に敏感であり、それらの外れ値を含めるために過剰適合が発生しやすくなります。

K-means法に対する別の重心ベースのアプローチは、K-medoidsです。medoidは、データ・セットまたはデータ・セット内のクラスターの代表的なオブジェクトであり、クラスター内の他のオブジェクトまでの距離の合計が最小です。そのアルゴリズムは、任意の重心をグラフの中心にするのではなく、個々のデータ・ポイントをクラスターのmedoidまたは中心として使用してクラスターを作成します。K-medoidsアルゴリズムは、任意の重心ではなく既存のデータ・ポイントを使用するため、外れ値に対する感度が低くなります。

階層クラスタリングは、接続ベースのクラスタリングとも呼ばれ、属性の近接性と接続性に基づいてデータ・ポイントをグループ化します。この方法では、すべてのディメンションにわたってデータ・ポイントが互いにどれだけ近いかに基づいてクラスターが決定されます。これは、オブジェクトが互いに近くにあれば、離れているオブジェクトよりも密接に関連しているという考え方です。K-means法とは異なり、クラスターの数を事前に指定する必要はありません。代わりに、クラスタリング・アルゴリズムは、各階層レベルでクラスターのグラフ・ネットワークを作成します。このネットワークは階層構造であり、その中のノードは親ノードは1つだけしか持ちませんが、子ノードは複数持つことができます。階層クラスターを樹状図でグラフ化すると、検出されたクラスターとそれに含まれる可能性のある階層を視覚的に要約して整理するのに役立ちます。

階層的クラスター分析を実行するには、次の2つの方法があります。

凝集型：凝集型クラスタリングでは、個々のデータ・ポイントからボトムアップのアプローチを開始し、現在の階層レベルにあるすべてのクラスターの近接行列を計算することでクラスターを順次統合し、ツリー状の構造を作成します。すべてのクラスターのクラスター間類似性がまったくないか低いクラスターの1つのレベルが作成されると、アルゴリズムは新しく作成されたクラスターのセットに移動し、階層グラフの最上位に1つのルート・ノードが存在するまでプロセスを繰り返します。これらのクラスターを相互にどのようにマージするかについては、クラスタリングの品質と効率の点でトレードオフがあるさまざまな選択肢があります。単連結クラスタリングでは、2つのクラスター内の任意のデータ・ポイントのペア間の最短距離が類似性の尺度として使用されます。全ペア連結では、データ・ポイントのすべてのペアの平均が使用されますが、サンプル連結では、2つのクラスター内のデータポイントのサンプリングが平均距離の計算に使用されます。重心連結では、重心間の距離が使用されます。凝集型手法の課題の1つは、連鎖が発生する可能性があることです。連鎖が発生すると、大きなクラスターは他のポイントとの距離が近くなる方向に偏るため、ますます大きくなり続け、より多くのデータ・ポイントがクラスターに引き寄せられることになります。もう1つの欠点は、集合的な方法は階層を構築する分割的な方法よりもはるかに遅い可能性があることです。

分割型： 分割型の階層的クラスタリング法では、トップダウンのアプローチによって、データ・ポイントをツリー状構造に連続的に区分します。最初のステップとして、K-means法のようなフラット・クラスタリング手法を使用してデータセットをクラスターに分割します。次に、残差平方和（SSE）が最大のクラスターが、フラット・クラスタリング手法を使用してさらに区分されます。アルゴリズムは、個々のノードまたは最小SSEに到達すると停止します。こうした分割区分により、ツリーの階層構造とさまざまなクラスターのバランスの両面で柔軟性が向上します。さまざまなノードの深さに関して完全にバランスの取れたツリーや、すべての分岐の次数が正確に2であるツリーを持つ必要はありません。これにより、ノードの深さとノードの重み（ノード内のデータポイントの数）のバランスにおいてさまざまなトレードオフを可能にするツリー構造を構築できます。分割型階層クラスタリングは、特にデータが個々のデータポイントに至るまでツリーを構築する必要がない場合、凝集階層クラスタリングよりも高速になる可能性があります。

分布ベースのクラスタリングは、確率的クラスタリングとも呼ばれ、確率分布に基づいてデータ・ポイントをグループ化します。このアプローチでは、クラスター中心を作成するデータの各次元に対して正規分布を生成するプロセスがあると想定しています。重心ベースのクラスタリングとは異なり、ユークリッド距離やマンハッタン距離などの距離メトリクスを使用しません。代わりに、分布ベースのアプローチでは、各次元にわたって現れる明確に定義された分布を探します。クラスター平均は、各次元にわたるガウス分布の平均です。分布ベースのクラスタリングは、クラスターを見つけるために各次元にわたって分布を複数回適合させる必要があるため、クラスタリングに対するモデル・ベースのアプローチです。これは、大規模なデータ・セットを扱う場合に計算コストが高くなる可能性があることを意味します。

分布ベースのクラスタリングに対して一般的に使用されるアプローチの1つは、期待値最大化（EM）を通じて混合ガウス・モデル（GMM）を作成することです。GMMは、各クラスターがガウス分布（しばしば正規分布とも呼ばれる）によって定義されるという想定に基づいて名付けられました。

AとBという2つの異なるクラスターを持つデータ・セットがあるとします。これらのクラスターは、どちらも2つの異なる正規分布（1つはx軸に沿っており、もう1つはy軸に沿っている）によって定義されています。期待値最大化は、各軸に沿った2つの分布をランダムに推測することから始まり、次の2つのステップを交互に実行して反復的に改善していきます。

期待値：各データ・ポイントを各クラスターに割り当てて、それがクラスターAとクラスターBから来た確率を計算します。

最大化：各データ・ポイントがクラスターに属する可能性に基づいて、各クラスターを定義するパラメーター、加重平均位置、分散共分散行列を更新します。次に、方程式が各クラスターで観測された分布に収束するまで、期待値のステップを繰り返します。

各データ・ポイントには、クラスターに関連付けられる確率が与えられます。これは、期待値最大化によるクラスタリングがソフト・クラスタリング・アプローチであり、特定のポイントが確率的に複数のクラスターに関連付けられる可能性があることを意味します。これは、曲がフォーク調でもありロック調でもあるとか、ユーザーはスペイン語のテレビ番組を好むが英語の番組もときどき視聴するといったシナリオに有効です。

密度ベースのクラスタリングは、ポイントが集中している領域と、それらがばらけて空またはまばらな領域を検出することによって機能します。K-means法などの重心ベースのアプローチや、期待値最大化などの分布ベースのアプローチとは異なり、密度ベースのクラスタリングでは任意の形状のクラスターを検出できます。これは、クラスターが特定の場所または分布を中心に定義されていない場合に非常に役立ちます。K-means法や階層的クラスタリングなどの他のクラスタリング・アルゴリズムとは異なり、密度ベースのアルゴリズムは、データ内のあらゆる形状、サイズ、密度のクラスターを検出できます。密度ベースのクラスタリングでは、クラスターの一部であるデータ・ポイントと、ノイズとしてラベル付けされるべきデータ・ポイントを区別することもできます。密度ベースのクラスタリングは、ノイズや外れ値のあるデータ・セットを扱う場合、またはデータ内のクラスターの数について事前の知識がない場合に特に役立ちます。

DBSCANは、クラスタリングに密度ベースのアプローチを採用するクラスタリング・アルゴリズムの一例です。密度ベースの空間クラスタリング手法を使用して、空間重心を中心とするユーザーから渡された密度でクラスターを作成します。重心のすぐ周囲のエリアは近傍と呼ばれ、DBSCANは指定された密度を持つクラスターの近傍を定義しようとします。DBSCANは、クラスターごとに次の3種類のデータ・ポイントを定義します。

コア・ポイント：データ・ポイントの近傍に、ユーザーが指定した最小ポイント数と同数以上のポイントが含まれる場合、そのデータ・ポイントはコア・ポイントです。

境界ポイント：データ・ポイントは、そのデータ・ポイント周辺の近傍に含まれるデータ・ポイントの数が最小値より少なく、そのポイント周辺の近傍にコア・ポイントが含まれる場合に境界ポイントとなります。

外れ値：データ・ポイントがコア・ポイントでも境界ポイントでもない場合は外れ値です。本質的に、これは「その他」のクラスです。

HDBSCANはDBSCANのバリアントであり、パラメーターを設定する必要はなく、派生元よりもさらに柔軟に利用できる可能性があります。HDBSCANは、データ内のノイズや外れ値の影響をあまり受けません。また、DBSCANでは、密度が均一でないクラスターの識別に問題が生じる場合があります。これがHDBSCANを採用する主な動機であり、HDBSCANはさまざまな密度のクラスターをはるかに効果的に処理します。

グリッド・ベースのクラスタリング・アルゴリズムは、前の4つのアプローチほど頻繁には使用されませんが、他のクラスタリング・アルゴリズムではパフォーマンスが低い可能性がある高次元クラスタリングでは役立ちます。このアプローチでは、高次元データ・セットはアルゴリズムによってセルに区分されます。各セルにはセルIDと呼ばれる一意の識別子が割り当てられ、1つのセル内にあるすべてのデータ・ポイントは、同じクラスターの一部とみなされます。

グリッド・ベースのクラスタリングは、多くのクラスタリング方法で一般的なステップである最近傍の検索に必要な時間を短縮するため、大規模な多次元データ・セットを分析するには効率的なアルゴリズムです。

一般的なグリッド・ベースのクラスタリング・アルゴリズムの1つに、STINGがあります（STatistical INformation Grid：統計情報グリッドの略）。STINGでは、空間領域は長方形のセルと、解像度レベルの異なる複数のレベルのセルに分割されます。高レベルのセルは、いくつかの低レベルのセルに分割されます。STINGは、データ・セットを繰り返し細かいグリッドに区分してそのグリッド内のポイント数を評価するだけなので、データ・セットが極めて大きいビッグデータ・シナリオのクラスター計算に非常に効率的です。STINGの欠点は、クラスターの境界を水平または垂直に定義する必要があることです。アルゴリズムは非長方形のクラスター境界を検出できません。

高次元データに対して特に強力なもう1つのグリッド・ベースのアルゴリズムは、CLIQUE（Clustering In Quest）アルゴリズムです。CLIQUEは、グリッド・ベースと密度ベースのクラスタリング・アプローチを組み合わせています。このアルゴリズムでは、データ空間がグリッドに分割され、グリッドのセル内の点の相対密度が比較され、同様の密度を持つ部分空間がマージされます。このアプローチでは、関心の対象となるすべての部分空間で密なユニットを見つけて、類似したクラスターを相互に接続する必要があるかどうかを測定します。これは、CLIQUEが高次元データ内の任意の形状のクラスターを検出できることを意味します。

クラスター分析にはいくつかの評価メトリクスがあり、適切なメトリクスの選択は、クラスタリング・アルゴリズムの種類と対応するデータ・セットによって異なります。評価メトリクスは通常、「外的」と「内在的」の2つの主要カテゴリーに分類できます。

内在的尺度は、データ・セット内の情報のみを使用するクラスター分析の評価メトリクスです。これらは、ラベルのないデータを扱うときに役立ちます。分析の品質は、完全にデータ・ポイント間の関係に基づいています。これらは、データの事前知識やラベルがない場合に使用できます。一般的な内在的尺度には、次のものがあります。

シルエット・スコア：このメトリクスは、各データ・ポイントの個別のクラスターと他のすべてのクラスターに関する類似度と非類似度を測定します。メトリクス値の範囲は-1～+1です。高い値は、オブジェクトがそれ自体のクラスターとよく一致しているが、隣接するクラスターとはあまり一致していないことを示します。

Davies-Bouldin指数：このメトリクスは、クラスター間距離に対するクラスター内距離の比率を計算します。この指数のスコアが低いほど、クラスタリングのパフォーマンスは高いことになります。

Calinski-Harabasz指数：これは分散比指標（Variance Ratio Criterion）としても知られ、クラスター間分散とクラスター内分散の比率を測定します。Calinski-Harabasz比が高いほど、クラスターはより明確に定義されています。

これらの評価メトリクスは、さまざまなクラスタリング・アルゴリズムとモデルのパフォーマンスの比較、クラスタリング・パラメーターの最適化、クラスタリング結果の精度と品質の検証に役立ちます。

外的尺度では、グラウンド・トゥルースまたは外部情報を使用して、クラスタリング・アルゴリズムのパフォーマンスの妥当性を評価します。これには、各データ・ポイントが属するクラスまたはクラスターを確認する何らかの形式のラベル・データが必要です。この場合、クラスタリング分析の精度を、分類精度でよく使用されるメトリクスと比較できます。一般的な外的尺度には、次のようなものがあります。

Fスコア（Fメジャーとも呼ばれる）：このメトリクスは、提案されたクラスタリングをグランド・トゥルースと比較したときの精度と再現率に注目することで、クラスタリング・アルゴリズムの精度を決定します。Fスコアの場合、高いほど優れています。

純度：このメトリクスは、所属するクラスまたはクラスターに正しく割り当てられたデータ・ポイントの割合を測定します。純度の尺度の場合、高いほど優れています。

ランド指数：これはクラスタリング・アルゴリズムの真のラベルと予測されたラベルの間の類似性の尺度で、範囲は0～1です。値が大きいほど、クラスタリングのパフォーマンスが優れていることを示します。

情報の変動（共有情報距離とも呼ばれる）：これは2つのクラスタリング間で失われた情報と得られた情報の量を測定します。これは、グラウンド・トゥルース・クラスタリングとアルゴリズム生成クラスタリングの間、または2つの異なるクラスタリングの間で実施できます。数値が小さいほど、2つのクラスタリング結果間の距離が小さいことを示し、優れていることになります。

クラスタリングがデータ・マイニングや探索的データ分析にとって貴重なツールとなる応用分野は数多くあります。この種の分析の重要性を理解するために、ここでは応用分野のほんの一部をリストアップします。

クラスタリングは、クラスター分析で定義されたクラスタリング構造にどのデータ・ポイントが含まれていないかを測定することで、異常を発見するのに役立ちます。小さいクラスターまたは非常にまばらなクラスターに属しているデータ・ポイントや、割り当てられたクラスターから遠く離れているデータ・ポイントは、異常とみなされる可能性があります。期待値最大化などの密度ベースの手法は、高密度領域のデータ・ポイントを正常として識別し、低密度領域のデータ・ポイントを異常として識別するために使用されます。

どのような顧客のペルソナや市場のサブセットが存在するかを理解しようとする場合、クラスタリングは顧客セグメンテーションの実行に役立つ強力なツールになります。人口統計データと顧客行動データを組み合わせて、どのような種類の特性と購入パターンが最も頻繁に相関するかを見つけることができます。

画像のピクセルはさまざまな方法でクラスター化されており、画像をさまざまなセクションに切り分けて背景から前景を分割したり、色と明るさの類似性を使用してオブジェクトを検出したり、さらに処理するためにいくつかの対象領域に画像を分割したりするのに役立ちます。画像の場合、クラスタリング手法は画像内のピクセルを処理し、クラスターを表す画像内の領域を定義します。

クラスタリング分析は、ドキュメントをさまざまな方法で処理するのに役立ちます。ドキュメントを類似度によってグループ化し、どのドキュメントが互いに最も類似しているかを示すことができます。これは、ドキュメントの長さ、単語の頻度分布、またはドキュメントに関する主要な特徴を定量化するその他のさまざまな方法に基づくいたものにできます。もう1つの一般的なユースケースは、キーワードの頻度、文の長さ、または用語の分布に基づいてドキュメントのセクションのクラスターを分析することです。これは、ドキュメントの要約を行ったり、さらに分析するために大きなドキュメントを小さなデータ・セットに分割したりする場合に役立ちます。