고차원 데이터를 클러스터링하는 방법은 크게 부분공간 탐색 기법, 상관관계 기반 클러스터링 기법, 바이클러스터링(Biclustering) 기법의 세 가지 그룹으로 분류할 수 있습니다.
부분공간 탐색 기법(Subspace Search Technique)
부분공간 탐색 방법은 여러 개의 부분공간을 검색하여 클러스터를 찾습니다. 따라서 클러스터란 특정 부분공간 안에서 서로 동일한 특성을 보이는 객체들의 부분집합이라 할 수 있습니다. 이때 유사도는 거리(distance)나 밀도(density)와 같은 전통적인 측정 기준을 통해 계산됩니다.
대표적인 예로 CLIQUE 알고리즘이 있습니다. CLIQUE는 차원을 점진적으로 늘려가는 순서로 부분공간과 해당 부분공간 내의 클러스터를 식별하며, 반단조성(antimonotonicity)을 활용해 클러스터가 더 이상 존재할 수 없는 부분공간을 가지치기(pruning)합니다. 부분공간 탐색 기법이 직면하는 가장 큰 과제는 수많은 부분공간을 얼마나 효율적으로 검색하느냐는 것입니다.
이를 위해 두 가지 유형의 방법이 사용됩니다.
상향식(Bottom-up) 방법: 저차원 부분공간에서 시작하여, 더 높은 차원의 부분공간에 클러스터가 존재할 가능성이 있는 경우에만 고차원 검색을 진행합니다. 검색해야 할 고차원 부분공간의 수를 줄이기 위한 다양한 가지치기 기법이 연구되어 왔으며, CLIQUE가 대표적인 상향식 방법의 예입니다.
하향식(Top-down) 방법: 전체 공간에서 시작하여 점점 작은 부분공간을 재귀적으로 검색합니다. 하향식 방법은 클러스터의 부분공간이 국소 이웃(local neighborhood)을 통해 결정될 수 있다는 국소성 가정(locality assumption)이 성립할 때에만 효율적으로 동작합니다.
상관관계 기반 클러스터링 방법(Correlation-Based Clustering)
부분공간 탐색 방법이 거리나 밀도 같은 전통적인 메트릭으로 계산된 유사도를 기반으로 클러스터를 찾는 반면, 상관관계 기반 방법은 보다 정교한 상관관계 모델로 표현되는 클러스터를 발견할 수 있습니다.
PCA 기반 접근법은 먼저 PCA(주성분 분석, Principal Components Analysis)를 사용해 데이터를 새로운 비상관(uncorrelated) 차원 집합으로 변환한 뒤, 변환된 새로운 공간 또는 그 부분공간에서 클러스터를 마이닝합니다. PCA 외에도 Hough 변환(Hough transform)이나 프랙탈 차원(fractal dimensions)과 같은 다른 공간 변환 기법을 활용할 수 있습니다.
바이클러스터링 방법(Biclustering)
일부 응용 분야에서는 객체와 속성을 동시에 클러스터링해야 하는 경우가 있습니다. 이렇게 생성된 클러스터를 바이클러스터(bicluster)라고 하며, 바이클러스터는 다음 네 가지 조건을 만족합니다.
클러스터에는 일부 객체들만 참여합니다.
클러스터에는 일부 속성들만 포함됩니다.
하나의 객체는 여러 클러스터에 참여할 수도 있고, 어떤 클러스터에도 속하지 않을 수도 있습니다.
하나의 속성 역시 여러 클러스터에 포함될 수도 있고, 어느 클러스터에도 포함되지 않을 수도 있습니다.
바이클러스터링 기법은 유전자 발현(gene expression) 데이터 분석의 요구를 충족시키기 위해 처음 제안되었습니다. 유전자(gene)는 생명체의 형질이 자손에게 전달되는 단위로, 일반적으로 DNA의 한 구간으로 이루어져 있습니다.
유전자는 특정 단백질과 기능성 RNA 사슬을 규정하기 때문에 모든 생명체에 필수적입니다. 유전자는 생명체의 세포를 구축하고 유지하는 데 필요한 정보를 제공하며, 유전 형질을 자손에게 물려줍니다.
유전형(genotype)은 세포, 개체 또는 개인의 유전적 구성을 의미하고, 표현형(phenotype)은 개체에게서 관찰되는 눈에 보이는 특징을 말합니다. 유전자 발현은 유전형이 표현형으로 나타나게 만드는 유전학의 핵심 단계입니다.