Clustering #1

■ Clustering이란?

- Data object의 그룹

 

1. 같은 그룹 안에서 다른 것들이 Similar 하거나 Related 하다.

2. 다른 그룹들에서 object가 Dissimilar 하거나 Unrelated하다.

 

이 두 가지 조건이 만족하게 되면 Cluster라고 부른다.

 

그렇다면 Clustering이란 무엇일까?

Unsupervised Learning의 일종으로 어떤 data object를 cluster로 나누고 그 cluster를 발견하는 것을 말한다.

데이터 분석을 위한 방법으로 전처리 과정에 해당한다.

 

 

■ Measuring Quality of Clustering

1. High-Quality Cluster

• High intra-class similarity : cluster의 cohesive(응집)
• Low inter-class similarity : cluster 간 distinctive(구분)

2. Clustering 방법

• cohesiveness(high) 와 distinctiveness(low)를 다루는 것
• 숨겨진 패턴을 발견하는 능력
• "충분한 유사성"을 정의하는 것 - 역치 결정 문제

3. Data set의 특성

• Huge data amount
• Complexity
• High dimensionality = feature = attributes

 

■ Clustering의 특징

1. 다른 유형의 데이터를 handling

2. 확장성(scalability)

3. 높은 차원(high dimensionality)

4. order와 관계없이 일정하게 결과 도출

5. noise와 outlier를 handling

6. 데이터의 다이내믹한 변화를 handling

7. usability

8. input parameters를 결정하는 도메인 지식이 요구됨

9. user에 맞는 구체적인 조건 설정

 

■ Partition-Based Methods

- k clusters 안에서 n objects 들의 data partition의 형성

- 최적의 clustering quality를 통한 partition(분할)의 발견 -> 높은 intra-class 유사성과 low inter-class 유사성

- Brute Force algorithms의 비효율성을 통해 Heurisitic algorithm의 도출

- 같은 input이라도 결과값이 달라질 수 있다는 점 생각

 

◇K-means Algorithm

- Heuristic clustering algorithm

- local optimum을 빠르게 모을 수 있다.

 

※ 처리 과정

1) Partition objects randomly into k clusters - O(1)

2) 각 cluster에 있는 object의 평균 포인트를 중심점으로 계산 - O(n)

3) 각 objects를 가장 가까운 중심점에 할당하고 k개의 새 클러스터를 생성 - O(nk)

4) 각 cluster의 objects가 변경되지 않을 때까지 2), 3)을 반복

 

★ 결론

- 장점 : Realtively efficient(n개 objects, k개 clusters, t번 iteration(반복)) - O((n+nk)t) ≒ O(nkt)

- 약점 :

    1. 구체적인 k, cluster 갯수가 사전에 필요함

    2. noise와 outliers들에 취약함

    3. 오직 numeric data에만 가능(평균이 정의 되어야 하기 때문에)

    4. 군집 모양이 아닌 cluster를 찾아내는데는 적절하지 않음

    5. local optimum에 가능, cluster의 global optimum은 인지할 수 없음.

 

2.3. Clustering — scikit-learn 1.1.2 documentation

2.3. Clustering

 

k-means 알고리즘은 sklearn의 위 사이트에 그림을 통해 자세하게 설명 되어 있으므로 참고하기 바란다.