機械学習データセットには数百万のサンプルを含めることができますが、すべてのクラスタリング アルゴリズムが効率的にスケーリングできるわけではありません。多くのクラスタリング アルゴリズムは、すべてのサンプルペア間の類似性を計算します。つまり、実行時間はサンプル数の 2 乗（複雑さの表記では \(O(n^2)\) ）に比例して増加します。 \(O(n^2)\) アルゴリズムは、数百万のサンプルを含むデータセットには実用的ではありません。 \(n\)
K 平均法アルゴリズムの複雑さは \(O(n)\)です。つまり、アルゴリズムは \(n\)に比例してスケーリングされます。このコースでは、このアルゴリズムに焦点を当てます。
クラスタリング タイプ
クラスタリングに関するさまざまなアプローチの包括的なリストについては、Xu、D の A Comprehensive Survey of Clustering Algorithms をご覧ください。& Tian, Y. Ann. Data. Sci. (2015) 2: 165. 各アプローチは、特定のデータ分布に最適です。このコースでは、4 つの一般的なアプローチについて簡単に説明します。
重心ベースのクラスタリング
クラスタのセントロイドは、クラスタ内のすべてのポイントの算術平均です。重心ベースのクラスタリングでは、データを非階層クラスタに編成します。重心ベースのクラスタリング アルゴリズムは効率的ですが、初期条件と外れ値に敏感です。これらの中で、最も広く使用されているのは K 平均法です。ユーザーが重心の数（k）を定義する必要があり、サイズがほぼ同じクラスタで適切に機能します。
密度ベースのクラスタリング
密度ベースのクラスタリングは、サンプル密度の高い連続した領域をクラスタに接続します。これにより、任意の形状のクラスタを任意の数検出できます。外れ値はクラスタに割り当てられません。これらのアルゴリズムは、密度の異なるクラスタや高次元のデータには対応していません。
分布ベースのクラスタリング
このクラスタリング アプローチでは、データがガウス分布などの確率分布で構成されていることを前提としています。図 3 では、分布ベースのアルゴリズムがデータを 3 つのガウス分布にクラスタ化しています。分布の中心からの距離が長くなるほど、点が分布に属する確率は低くなります。帯は、その確率の低下を示しています。データの特定の基盤となる分布を想定できない場合は、別のアルゴリズムを使用する必要があります。
階層クラスタリング
階層型クラスタリングでは、クラスタのツリーが作成されます。階層クラスタリングは、分類などの階層データに適しています。例については、Oksana Lukjancenko、Trudy Wassenaar、Dave Ussery による 61 個の Escherichia coli ゲノムの配列の比較をご覧ください。適切なレベルでツリーをカットすることで、任意の数のクラスタを選択できます。
