分割型クラスタリングアルゴリズムの種類とは？K-means法と最近傍法を徹底解説

分割型アルゴリズムの2つの種類

分割型（partitional）クラスタリングアルゴリズムには、主に以下の2種類があります。

• K-meansクラスタリング（k平均法）
• 最近傍法（Nearest Neighbour Algorithm）

K-meansクラスタリング（k平均法）とは

K-meansクラスタリングは、最も広く利用されている分割型アルゴリズムです。データセット内の各データを、新しく形成された複数のクラスタのうちいずれか1つに再割り当てします。個々のレコードやデータポイントは、距離または類似度の尺度を用いて、最も近いクラスタへと割り当てられます。

K-meansクラスタリングの主な手順は以下の通りです。

• K個の初期クラスタ重心 c₁, c₂, c₃, …, c_k を選択します。
• 各インスタンス x を、その重心が x に最も近いクラスタ S に割り当てます。
• 各クラスタについて、そのクラスタに含まれる要素に基づいて重心を再計算します。
• 収束が完了するまで、割り当て処理を繰り返します。
• オブジェクト（データポイント）を K 個のクラスタに分離します。
• クラスタ中心（重心）は、そのクラスタ内の全データポイントの平均値として定義されます。
• 距離関数を用いて、各ポイントを重心が最も近いクラスタに割り当てます。

平均値の初期値は任意に設定されます。ランダムに割り当てることもできますし、最初の k 個の入力データの値をそのまま利用することも可能です。収束判定は二乗誤差に基づくのが一般的ですが、必ずしもそれである必要はありません。たとえば、一定回数の反復後に終了する手法もあります。収束しない場合でも確実に処理を停止できるよう、最大反復回数を設けることも有効です。

K-meansアルゴリズムの流れ

入力

D = {t1, t2, …, tn}　// 要素の集合
k　// 目標とするクラスタ数

出力

K　// クラスタの集合

K-meansアルゴリズムの手順：

1. 平均値 m₁, m₂, …, m_k の初期値を設定する
2. 繰り返し：各項目 t_i を、最も近い平均値を持つクラスタに割り当てる
3. 各クラスタの新しい平均値を計算する
4. 収束基準が満たされるまで 2〜3 を繰り返す

最近傍法（Nearest Neighbour Algorithm）とは

単一リンク法（single link technique）に類似したアルゴリズムが、最近傍法です。この逐次型アルゴリズムでは、アイテムが反復的に、現時点で最も近いクラスタへと統合されていきます。また、閾値 t を設けることで、アイテムを既存のクラスタに挿入するか、あるいは新しいクラスタを生成するかを判断できます。

最近傍法アルゴリズムの流れ

入力

D = {t1, t2, …, tn}　// 要素の集合
A　// 要素間の距離を表す隣接行列

出力

K　// クラスタの集合

最近傍法の擬似コード：

K1 = {t1};
K = {K1};
k = 1;
for i = 2 to n do
    K 内のクラスタ Km から、dis{ti, tm} が最小となる tm を探索する;
    if dis{ti, tm} ≤ t then
        Km = Km ∪ ti
    else
        k = k + 1;
        Kk = {ti}

まとめ

分割型クラスタリングでは、K-means法がシンプルかつ高速である一方、クラスタ数 k を事前に指定する必要があります。一方、最近傍法は閾値 t によってクラスタ形成を制御でき、階層的なアプローチに近い挙動を示します。データの性質や目的に応じて、適切なアルゴリズムを選択することが重要です。