[Clustering] Overview, Approach, Cluster Analysis

 

Cluster Analysis

Cluster - 같은 집단은 비슷하거나 연관있도록, 다른 집단은 비슷하지 않거나 적게 연관되도록 군집화한다.

Cluster analysis (clustering, data segmentation) - 데이터간의 특징을 통해 유사성을 찾아서 유사한 군집으로 매칭한다.

Unsupervised learning: predefined class가 필요하지 않다. 

clustering 자체만으로도 데이터 분포에 대한 정보를 얻을 수 있지만(stand-alone tool), 다른 알고리즘을 적용하기 전에 전처리 단계로 사용할 수 있다. (preprocessing step)

 

Clustering as a Preprocessing Tool

Summarization - regression, classification, PCA, association analysis 등의 전처리 단계로 사용할 수 있다.

Compression - Image processing에서 사용. (vector quantization)

Finding kNN - Localizing search

Outlier detection - outlier는 모든 cluster로부터 많이 떨어져있을 것이다.

 

Quality: What is good clustering?

Clustering Quality

클러스터 내의 원소들의 거리는 최소, 클러스터 간의 거리는 최대로 하는 것이 좋다.

Considerations for Cluster Analysis

Partitioning criteria

single level vs hierarchical partitioning

일반적으로 multi-level hierarchical paritioning이 좋다.

 

Separation of clusters

exclusive: 고객 한 명은 하나의 지역에 거주한다.

non-exclusive: 한 문서는 다양한 주제에 포함될 수 있다.

 

Similarity measure

Distance-based: Euclidian, road network,vector

Connectivity-based: density, contiguity

 

Clustering space

Full space: low dimensional

Subspaces: high dimensional clustering

반응형

Major Clustering Approaches

Partitioning approach

• 어떤 기준(예. sum of square error를 최소화)에 따라 partition을 나눈다.
• k-means, k-medoids, CLARANS

Hierarchical approach

• 같은 기준으로 데이터셋을 계층으로 분해한다.
• Diana, Agnes, BIRCH, CAMELEON

Density-based approach

• density function에 기반하여 데이터 연결성을 판단한다.
• DBSCAN, OPTICS, DenClue

Grid-based approach

• multiple-level granularity structure
• STING, WaveCluster, CLIQUE

Model-based

• 각 클러스터마다 모델이 있다고 가정하여 best fit model을 찾는다.
• EM, SOM, COBWEB

Frequent pattern-based

• analysis of frequent patterns
• p-Cluster

User-guided or constraint-based

• user-specified, application-specific constraint 를 고려하여 클러스터링
• COD, constrained clustering

Link-based clustering

• 각 객체(object)들은 다양한 방법으로 서로 연결되어있다.
• 매우 많은 연결(link)은 cluster object로 생각할 수 있다.
• SimRank, LinkClus