DENCLUEとは？密度ベースクラスタリング手法の基礎と特徴を解説

クラスタリングとは

クラスタリングは、知識発見のための重要なデータマイニング手法のひとつです。探索的データ分析（EDA）に分類される手法であり、複数のデータオブジェクトを「クラスタ」と呼ばれる同質のグループへと分類します。

DENCLUEの概要

DENCLUEは「Density-based Clustering（密度ベースクラスタリング）」を表す用語です。密度分布関数の集合に基づくクラスタリング手法で、カーネル密度推定に基づくクラスタモデルを採用しています。クラスタは、推定された密度関数の局所的最大値（ローカルマキシマム）として表現されます。

ただし、DENCLUEは一様分布に従うレコードには適していません。高次元空間では「次元の呪い（curse of dimensionality）」の影響により、データは常に一様分布に近く見えるため、一般的に高次元データに対しては十分な性能を発揮できません。

DENCLUEの基本的な考え方

この手法は、以下の3つのアイデアに基づいて構築されています。

• 各データ点の影響は、影響関数（influence function）と呼ばれる数学的関数によって正式にモデル化できます。影響関数は、近傍内におけるデータ点の影響力を記述します。
• データ領域全体の密度は、各データ点に適用される影響関数の総和として、解析的にモデル化できます。
• クラスタは、密度アトラクタ（density attractors）を数値的に識別することで決定できます。密度アトラクタとは、全体密度関数の局所的最大値のことです。

影響関数の数学的定義

xとyを、d次元入力空間 f^d 内のオブジェクト（点）とします。データオブジェクトyがxに与える影響関数は、基本影響関数 f_B を用いて次のように定義される関数です。

$$\mathrm {f_B^y(X)=f_{B}(X,Y)}$$

これは、yがxに与える影響を表します。原理的には、影響関数は近傍内の2つのオブジェクト間の距離から決定できる任意の関数であり得ます。距離関数 d(x, y) は反射律と対称性を満たす必要があり、ユークリッド距離関数などがこれに該当します。

実用上は、次のような方形波影響関数が用いられることがあります。

$$\mathrm{f_{square}(X,Y)=\begin{Bmatrix}0 \:\:\:\:\:\:\:\:\:\:\mathrm{if\:d(x, y) > \sigma}\\1\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\mathrm{otherwise}\end{Bmatrix}}$$

また、次のようなガウス影響関数も広く使用されます。

$$\mathrm{f_{Gauss}(x, y)=e-\frac{d(x, y)^2}{2{\sigma}^2}}$$

DENCLUEの利点

DENCLUEには、以下のような利点があります。

• 堅牢な数学的基盤を持ち、分割法・階層的手法・密度ベース手法といった複数のクラスタリングアプローチを一般化した手法です。
• 大量のノイズを含むデータセットに対して、優れたクラスタリング特性を発揮します。
• 高次元データセットにおける任意の形状のクラスタを、コンパクトな数値記述で表現できます。
• グリッドセルを利用しますが、実際にデータ点を含むグリッドセルの情報のみを保持します。これらのセルをツリーベースのアクセス構造で管理するため、DBSCANなどの有力なアルゴリズムと比較して大幅に高速に動作します。

注意点：パラメータ選択の重要性

一方で、DENCLUEでは密度パラメータσとノイズ閾値ξを慎重に選択する必要があります。これらのパラメータの選択はクラスタリング結果の品質に大きな影響を与えるため、適切なチューニングが実用上の鍵となります。