What is clustering?
- Clustering is the process of grouping a set of objects into classes of similar objects.
- Clustering is the commonest form of unsupervised learning.
- Unsupervised learning: learning from raw data where any classification of examples is not given.
- Supervised learning: learning from supervised data where a classification of examples is given. - Clustering is a common and important task that finds many applications in IR and other places.
Partitioning methods
n개의 객체 혹은 투플이 주어졌을 때, 분할기법은 k≤n 이 되도록 군집을 나타내는 데이터 분할을 k개 만든다. 즉, 데이터를 모두가 다음의 요구를 만족하도록 k개의 그룹으로 구분한다.
- 각 그룹은 적어도 하나의 객체를 가지고 있어야 한다.
- 각 객체는 정확히 하나의 그룹에 속해야한다.
잡음값이나 이상치가 존재할 때 medoid 값이 평균에 비해 이상치나 다른 극단적인 값들에 덜 영향받기 때문에 k-means 보다 k-medoids가 더 견고하다. 하지만 그에 비해 고비용 방법이다. 또한 작은 데이터 집합에서 작용하지만 큰 데이터 집합에 확장적용은 쉽지 않다.
Hierarchical methods
주어진 데이터 객체 집합을 계층적으로 분해한다. 계층적 기법은 어떻게 계층적 분해가 형성되는지에 기초하여, 집괴적(agglomerative)이거나 분할적(divisive)으로 분류한다.
- 집괴적 계층 군집화 기법: AGNES(AGglomerative NESting)
- 분할적 계층 군집화 기법: DIANA(DIvisive ANAlysis)
- 통합된 계층 군집화 기법: BIRCH(Balanced Iterative Reducing and Clustering Using Hierarchies)
객체의 수에 관한 선형확장성과 양질의 데이터 군집화에 좋은 성능을 보인다. 하지만 군집이 공간적으로 구형이 아니면 잘 실행되지 않는다. - 대표값을 이용한 군집화: CURE(Clustering Using REpresentatives)
- 이상치에 관하여 매우 견고하다. - 동적인 모델을 이용한 계층 군집화 알고리즘: Chameleon
- CURE와 DBSCAN보다 좋은 성능으로 임의적인 형태의 군집을 찾는데 매우 강력하다. 하지만 고차원 데이터의 처리비용은 가장 최악의 경우 n개의 객체에 대해 O(n2)의 시간이 필요하다.
Density-based methods
대부분의 분할 기법은 객체간의 거리에 기초하여 객체들을 군집한다. 그러한 기법들은 구형의 군집만을 찾을 수 있고, 임의의 형태의 군집을 찾는데는 어려움이 있다. 따라서 임의의 형태의 군집을 찾기 위해 밀도 기반 군집화 기법이 발전해왔다. 그것은 전형적으로 낮은 밀도의 영역들(잡음 영역)로 분리된 데이터 공간에서 객체들이 조밀한 영역을 군집으로 여긴다.
- 밀도 기반 군집화 기법: DBSCAN(Density-Based Spatial Clustering of Applications with Noise)
- 군집 구조 식별을 위한 순서화: OPTICS
- 밀도분포 함수에 기초한 군집화: DENCLUE(DENsity-based CLUstEring)
Grid-based methods
객체공간을 격자구조로 이루어진 유한개의 공간으로 만든다. 이러한 접근의 주된 이점은 빠른 처리시간인데, 데이터 객체 수에 독립적이고 단지 양자화된 공간의 각 차원에서 셀의 수에만 의존한다.
- 통계정보 격자: STING(STatistical INformation Grid)
- 웨이블릿 변환을 이용한 군집화: WaveCluster
- 고차원 공간 군집화: CLIQUE(Clustering In QUEst)
Model-based methods
각 군집에 모델을 가정하고 주어진 모델에서 가장 잘 맞는 데이터를 찾는다. 모델기반 알고리즘은 데이터 포인트의 공간적 분포를 반영한 질량함수를 구축함으로써 군집들을 위치시키기도 한다. 모델기반 군집화 기법은 두 가지 중요한 접근 방식들을 따른다.
- 통계적 접근방식(statistical approach)
- 신경망 접근방식(network approach) - 코호넨 네트워크(kohonen network)