クラスタリング アルゴリズムのタイプと、各タイプを選択すべきタイミングを簡単に見ていきましょう。
クラスタリング アルゴリズムを選択する際は、アルゴリズムがデータセットにスケーリングされるかどうかを検討する必要があります。機械学習のデータセットには何百万もの例が含まれていますが、すべてのクラスタリング アルゴリズムが効率的にスケールされるわけではありません。多くのクラスタリング アルゴリズムは、すべての例のペア間の類似性を計算することで機能します。つまり、サンプル数の割合が 2 の割合になるにつれてランタイムが増加し、 \(n\)\(O(n^2)\) 複雑度表記で示されます。サンプル数が数百万の場合、アルゴリズムは現実的ではありません。このコースでは、K 平均法アルゴリズムを中心に説明します。このアルゴリズムは \(O(n)\)が複雑であるため、 \(n\)に比例してスケールします。
クラスタリングのタイプ
クラスタリングを行うには、いくつかの方法があります。網羅的なリストについては、A Comprehensive Survey of Clustering Algorithms(Xu、D)をご覧ください。Tian, Y. Ann. データ。Sci。(2015)2: 165それぞれのアプローチは、特定のデータ分散に適しています。以下では、K 平均法を使用したセントロイド ベースのクラスタリングに焦点を当てた、4 つの一般的なアプローチについて簡単に説明します。
セントロイド ベースのクラスタリング
以下で定義されている階層化クラスタリングとは対照的に、セントロイドベースのクラスタリングは、データを階層化されていないクラスタに編成します。K 平均法は、最も広く使用されているセントロイド ベースのクラスタリング アルゴリズムです。セントロイド ベースのアルゴリズムは効率的ですが、初期条件や外れ値の影響を受けやすいためです。このコースでは K 平均法に焦点を当てていますが、これは効率的で効果的、かつシンプルなクラスタリング アルゴリズムであるためです。
密度ベースのクラスタリング
密度ベースのクラスタリングは、サンプル密度が高い領域をクラスタに接続します。高密度領域を接続できる限り、任意の形状の分布が可能です。これらのアルゴリズムでは、さまざまな密度の密度と高次元のデータには困難があります。また、これらのアルゴリズムでは、外れ値をクラスタに割り当てません。
分布ベースのクラスタリング
このクラスタリング アプローチでは、データがガウス分布などの分布で構成されていることを前提としています。図 3 では、分布ベースのアルゴリズムにより、データが 3 つのガウス分布にクラスタ化されています。分布の中心からの距離が遠くなると、そのポイントが分布に属する確率は減少します。帯は、確率が減少することを示しています。データの分布の種類が不明な場合は、別のアルゴリズムを使用する必要があります。
階層クラスタリング
階層クラスタリングは、クラスタのツリーを作成します。階層型クラスタリングは、分類のような階層データに適しています。例については、Oksana Lukjancenko、Trudy Wassenaar、Dave Ussery による 61 Sequenceed Escherichia coli Genomes をご覧ください。また、ツリーを適切なレベルでカットすることで、任意の数のクラスタを選択できることもメリットの一つです。