웨이블릿 변환과 WaveCluster의 원리
WaveCluster는 데이터 공간에 다차원 격자(grid) 구조를 적용하여 레코드를 먼저 요약하는 멀티해상도(multiresolution) 클러스터링 알고리즘입니다. 이 알고리즘은 웨이블릿 변환(wavelet transform)을 활용해 원래의 특징 공간(feature space)을 변환하고, 변환된 공간에서 밀집 영역(dense region)을 찾아냅니다.
이 방식에서는 각 격자 셀이 해당 셀에 매핑된 점들의 그룹 데이터를 요약합니다. 요약된 데이터는 일반적으로 주 메모리에 저장될 만큼 작기 때문에, 멀티해상도 웨이블릿 변환과 이후의 클러스터 분석 과정에서 효율적으로 활용됩니다.
웨이블릿 변환은 신호를 여러 개의 주파수 서브밴드로 분해하는 신호 처리 기법입니다. 1차원 웨이블릿 변환을 d번 적용하면 d차원 신호에도 웨이블릿 모델을 사용할 수 있습니다. 웨이블릿 변환을 적용하면 데이터가 여러 해상도 수준에서 객체 간 상대 거리를 보존하는 형태로 변형되며, 이를 통해 데이터에 존재하는 자연스러운 군집(cluster)이 더욱 뚜렷하게 드러납니다. 새로운 공간에서 밀집 영역을 탐색함으로써 군집을 식별할 수 있습니다.
웨이블릿 변환의 주요 장점
1. 비지도 클러스터링 지원
웨이블릿 변환은 모자(hat-shaped) 형태의 필터를 사용하여 점들이 모여 있는 영역은 강조하고, 군집 경계 바깥의 약한 데이터는 억제합니다. 따라서 초기 특징 공간의 밀집 영역은 인접한 점들에게는 끌어당김(attractor)으로 작용하고, 거리가 먼 점들에게는 배척(inhibitor)으로 작용합니다. 이로 인해 데이터 내 군집이 자동으로 두드러지게 나타나며 주변 영역이 '정리'됩니다. 여기에 더해 웨이블릿 변환은 이상치(outlier)를 자동으로 제거하는 효과도 얻을 수 있습니다.
2. 멀티해상도 분석 가능
웨이블릿 변환의 멀티해상도 특성 덕분에 다양한 정확도 수준에서 군집을 탐지할 수 있습니다. 큰 규모의 군집부터 세부적인 군집까지 유연하게 파악할 수 있다는 의미입니다.
3. 뛰어난 연산 효율
웨이블릿 기반 클러스터링은 매우 빠르며, 계산 복잡도는 O(n)입니다(여기서 n은 데이터베이스 내 객체 수). 또한 알고리즘 구현을 병렬화할 수 있어 대용량 데이터 처리에도 유리합니다.
4. 격자 기반·밀도 기반 알고리즘의 강점 결합
WaveCluster는 격자 기반(grid-based)이면서 동시에 밀도 기반(density-based) 알고리즘으로, 좋은 클러스터링 알고리즘이 갖추어야 할 여러 조건을 충족합니다. 대규모 데이터셋을 효율적으로 처리하고, 임의의 모양을 가진 군집을 찾아내며, 이상치를 효과적으로 다루고, 입력 순서에 민감하지 않습니다. 또한 군집 수나 이웃 반경(neighborhood radius)과 같은 입력 매개변수를 사전에 정의할 필요가 없습니다.
예비 연구 결과에 따르면 WaveCluster는 BIRCH, CLARANS, DBSCAN과 비교했을 때 효율성과 클러스터링 품질 모두에서 우수한 성능을 보였습니다. 아울러 최대 20차원까지의 고차원 데이터도 안정적으로 처리할 수 있는 것으로 확인되었습니다.