非階層的クラスタリングと階層的クラスタリング

はじめに

クラスタリングとは、データセットに含まれる観測値やデータポイントをいくつかの「クラスタ」（群）に分ける方法です。クラスタリングの目的は、同じクラスタに属するデータポイントが互いに似ている一方で、異なるクラスタに属するデータポイントは異なっているようにすることです。この手法は、統計学や機械学習、データ解析など、さまざまな分野で利用されます。

クラスタリングには大きく分けて「非階層的クラスタリング」と「階層的クラスタリング」という2つの方法があります。この記事では、これら2つのクラスタリング手法について、基礎理論や物理的な概念を重視しながら、数式を用いてわかりやすく解説していきます。

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

クラスタリングとは？

クラスタリングとは、データをいくつかのクラスタ（集合、グループ）に分割する手法です。クラスタリングの主な目標は、同じクラスタに属するデータが互いに類似しており、異なるクラスタに属するデータが互いに異なることを保証することです。

具体的には、データポイント $x_1, x_2, \dots, x_n$ をいくつかのクラスタに分割し、各クラスタ内のデータポイント同士が似た性質を持つようにします。

クラスタリングの主な目的は以下の通りです。

1. データの構造を理解する: 大量のデータがある場合、どのデータがどのように関連しているかを知るためにクラスタリングを行います。たとえば、顧客データを分析して顧客の購買傾向をグループ化することができます。
2. 分類の補助: 事前にラベルがついていないデータに対してクラスタリングを適用し、データのグループごとに何らかの意味を見出すことができます。
3. データの可視化: 多次元データを2次元または3次元の空間に投影する際、クラスタリングを用いることで、データのパターンや構造を視覚的に把握しやすくなります。

クラスタ間の距離

クラスタリングにおいて重要な概念の1つが「距離」です。データポイント間の距離を測定することで、どのデータポイントがどのクラスタに属するかを決定します。距離を測定する手法にはいくつかの方法がありますが、最も一般的な方法は「ユークリッド距離」です。

ユークリッド距離は、2点 $x = (x_1, x_2, \dots, x_n)$ と $y = (y_1, y_2, \dots, y_n)$ の間の距離を次のように定義します。

$$
d(x, y) = \sqrt{(x_1 – y_1)^2 + (x_2 – y_2)^2 + \dots + (x_n – y_n)^2}
$$

この式は、データポイントの各次元における差を二乗し、それをすべて足し合わせて平方根をとることで、データポイント間の距離を算出しています。ユークリッド距離は、直感的に「2点間の直線距離」と捉えることができ、多くのクラスタリング手法で利用されます。

非階層的クラスタリング

概要

非階層的クラスタリング（Non-Hierarchical Clustering）は、データポイントを固定された数のクラスタに一度に分割する手法です。この手法は「平らなクラスタリング」とも呼ばれ、最初にクラスタの数を指定してからデータをその数に基づいて分割します。最も代表的な非階層的クラスタリング手法として「$k$-meansクラスタリング」があります。

$k$-meansクラスタリング

$k$-meansクラスタリングは、データセットを事前に指定された$k$個のクラスタに分割する手法です。アルゴリズムの概要は以下の通りです。

1. 初期クラスタ中心の設定: $k$個のクラスタの中心（セントロイド）をランダムに選択します。
2. クラスタ割り当て: 各データポイントを、最も近いクラスタ中心に割り当てます。ユークリッド距離を用いて、各データポイントと各クラスタ中心との距離を計算し、最も近いクラスタに属するようにします。
3. クラスタ中心の更新: 各クラスタに割り当てられたデータポイントの平均を計算し、その平均を新しいクラスタ中心とします。
4. 反復: クラスタの割り当てとクラスタ中心の更新を繰り返し、クラスタの割り当てが変わらなくなるまでこのプロセスを続けます。

アルゴリズムの目的は、クラスタ内のデータポイント同士の類似性を最大化し、クラスタ間の類似性を最小化することです。このとき、次の目的関数を最小化します。

$$
J = \sum_{i=1}^{k} \sum_{x_j \in C_i} |x_j – \mu_i|^2
$$

ここで、$C_i$はクラスタ$i$、$\mu_i$はクラスタ$i$の中心、$x_j$はデータポイントです。この式は、各クラスタ内のデータポイントとクラスタ中心の距離の二乗和を表しています。

非階層的クラスタリングの特徴

• クラスタ数の指定: 非階層的クラスタリングでは、最初にクラスタの数を指定する必要があります。たとえば、$k$-meansでは$k$を設定します。
• 反復的手法: 非階層的クラスタリングでは、クラスタの割り当てとクラスタ中心の計算が反復的に行われます。アルゴリズムは、クラスタ内のデータの分布が安定するまで実行されます。
• 計算の高速性: 非階層的クラスタリングは、比較的高速にクラスタを計算できます。しかし、初期のクラスタ中心の選び方によって結果が大きく変わることがあります。

非階層的クラスタリングの応用例

非階層的クラスタリングは、以下のような状況でよく使われます。

• 市場セグメンテーション: 顧客データをもとに市場を複数のセグメントに分割し、各セグメントに異なるマーケティング戦略を適用する場合に使われます。
• パターン認識: 画像や音声のデータをクラスタリングして、同じ特徴を持つパターンを見つけることができます。

階層的クラスタリング

概要

階層的クラスタリング（Hierarchical Clustering）は、データを階層的に分割または統合していく手法です。この方法は、データポイントをツリー状にグループ化し、階層構造を持つクラスタを作成します。階層的クラスタリングには、次の2つのアプローチがあります。

1. 凝集型（アグロメレーティブ）クラスタリング: すべてのデータポイントを個別のクラスタとして開始し、それらを順次結合していく手法です。
2. 分割型（ディビジブ）クラスタリング: すべてのデータポイントを1つのクラスタとして開始し、それを順次分割していく手法です。

この記事では、特に凝集型クラスタリングについて詳しく説明します。

凝集型クラスタリング

凝集型クラスタリングは、次のようなプロセスを経てクラスタリングを行います。

1. 初期化: 各データポイントを個別のクラスタとして開始します。つまり、$n$個のデータポイントがあれば、最初は$n$個のクラスタが存在します。
2. **クラスタ間の距離

計算**: すべてのクラスタ間の距離を計算します。クラスタ間の距離を定義する方法はいくつかありますが、最も一般的なのは以下の3つです。

• 単一結合法（Single Linkage）: 2つのクラスタ間の最も近いデータポイント間の距離をクラスタ間の距離とします。
• 完全結合法（Complete Linkage）: 2つのクラスタ間の最も遠いデータポイント間の距離をクラスタ間の距離とします。
• 平均結合法（Average Linkage）: 2つのクラスタに属するすべてのデータポイント間の平均距離をクラスタ間の距離とします。

1. クラスタの結合: 最も近い2つのクラスタを結合します。
2. 反復: クラスタが1つになるまで、または希望するクラスタ数になるまで、クラスタ間の距離計算と結合を繰り返します。

凝集型クラスタリングの結果は「デンドログラム」と呼ばれる木構造で表されます。デンドログラムは、クラスタの結合順序を視覚的に示すもので、どのクラスタがどの順序で結合されたかがわかります。

階層的クラスタリングの特徴

• 階層構造の保持: 階層的クラスタリングでは、クラスタの階層構造が保持されます。このため、クラスタリング結果をより詳細に分析することが可能です。
• クラスタ数の自動決定: 非階層的クラスタリングとは異なり、階層的クラスタリングでは、クラスタ数を事前に指定する必要はありません。クラスタリング結果から適切なクラスタ数を決定することができます。
• 計算コスト: 階層的クラスタリングは、非階層的クラスタリングに比べて計算コストが高い傾向があります。特に、大量のデータを処理する際には計算量が増加します。

階層的クラスタリングの応用例

階層的クラスタリングは、以下のような状況でよく使われます。

• 系統樹の作成: 生物の進化的関係を調べる際に、DNAやタンパク質の配列データをもとに系統樹を作成する場合に使われます。
• 文章のクラスタリング: 文書やテキストデータをクラスタリングして、類似したトピックを持つ文書をグループ化することができます。

非階層的クラスタリングと階層的クラスタリングの比較

最後に、非階層的クラスタリングと階層的クラスタリングの違いを比較してみましょう。

まとめ

非階層的クラスタリングと階層的クラスタリングは、それぞれ異なる特性と利点を持つクラスタリング手法です。非階層的クラスタリングは、クラスタの数を事前に指定し、データを高速に分割することができます。一方、階層的クラスタリングは、クラスタ間の階層構造を明確にし、データの全体像を視覚的に把握できるメリットがあります。どちらの手法もデータの構造を理解するための強力なツールであり、解析の目的に応じて適切な手法を選択することが重要です。