ウェーブレット変換がクラスタリングに役立つ理由とは？WaveClusterの仕組みを解説

WaveClusterとは

WaveClusterはマルチ解像度クラスタリングアルゴリズムの一つで、まずデータ空間に多次元グリッド構造を適用することでレコードを要約します。その後、ウェーブレット変換を利用して元の特徴空間を変換し、変換後の空間における高密度領域を検出することでクラスタを見つけます。

この手法では、各グリッドセルがそのセルにマッピングされた点群のデータを要約します。要約データは通常メインメモリに収まるため、マルチ解像度ウェーブレット変換やその後のクラスタ分析を効率的に実行できます。

ウェーブレット変換の仕組み

ウェーブレット変換は、信号を複数の周波数サブバンドに分解する信号処理手法です。1次元ウェーブレット変換をd回適用することで、d次元の信号にも対応できます。

ウェーブレット変換を適用すると、複数の解像度レベルにおいてオブジェクト間の相対的な距離が保持される形でデータが変換されます。これにより、データ内に本来存在する自然なクラスタがより検出しやすくなり、新しい空間における高密度領域を探索することでクラスタを識別できます。

ウェーブレット変換の主な利点

1. 教師なしクラスタリングが可能

ウェーブレット変換では、点が密集する領域を強調し、クラスタ境界の外側にある弱いデータを抑制する「帽子型フィルタ」を使用します。

その結果、初期の特徴空間における高密度領域は、近接する点を引き寄せる「アトラクタ」として機能し、離れた点に対しては抑制的に働きます。これにより、データ内のクラスタは自動的に際立ち、その周囲の領域が「クリア」されます。さらに、ウェーブレット変換は外れ値（ノイズ）を自動的に除去できるという利点もあります。

2. マルチ解像度によるクラスタ検出

ウェーブレット変換のマルチ解像度特性により、複数の精度レベルでクラスタを検出できます。大まかな構造から詳細な構造まで、目的に応じた粒度でクラスタリングを行うことが可能です。

3. 高速な処理性能

ウェーブレットベースのクラスタリングは非常に高速で、計算量はO(n)です（nはデータベース内のオブジェクト数）。また、アルゴリズムの実装は並列化することもできます。

4. グリッドベースかつ密度ベースのアルゴリズム

WaveClusterはグリッドベースと密度ベースの両方の特徴を持ち、優れたクラスタリングアルゴリズムに求められる多くの要件を満たしています。

• 大規模なデータセットを効率的に処理できる
• 任意の形状のクラスタを検出できる
• 外れ値を適切に処理できる
• 入力データの順序に影響されない
• クラスタ数や近傍半径といった入力パラメータの事前定義が不要

他のアルゴリズムとの比較

予備研究では、WaveClusterは効率性とクラスタリング品質の両面において、BIRCH、CLARANS、DBSCANを上回る性能を示すことが判明しました。また、WaveClusterは最大20次元のデータを処理できる能力を持つことも明らかになっています。