[DataMining] 바이오빅데이터와데이터마이닝 2. Clustering(클러스터링) 모델

본 글은 필자가 2021년도 2학기에 변정현 교수님의 바이오빅데이터와데이터마이닝 수업을 듣고 내용 복기차 작성한 정리글입니다. 데이터 마이닝에 쓰이는 여러가지 모델들 중 대표적인 Classification, Clustering 모델을 배웠습니다. 본 글은 Clustering 부분 (+시계열 데이터 마이닝) 에 해당되는 모델을 모아놓았습니다.

Clustering

: 군집 분석, 그룹 내의 객체들은 유사하도록(관련이 있도록, minimized distance)  / 그룹간의 객체들은 유사하지 않도록 (관련이 없도록, maximize distance)

주어진 객체들을 그룹짓는 작업

- Well-separated cluster: 한 군집의 모든 점은 서로 더 가깝거나 유사한 점을 갖는다.

0) Types of Clustering

계층 여부에 따라

- Partitional Clustering분할 군집화: 데이터 객체들을 중복이 없는 부분집합으로 나눈다.

- Hierarchical Clustering계층 군집화: 계층 트리에 의해 구성되며 하위 군집을 상위 군집이 포함하는 구조 (중첩O)

 

입력 데이터의 특성에 따라

- Contiguity-based Clusters연속성 기반 클러스터: 클러스터 한 점은 동일한 클러스터의 하나 이상의 점에 더 가깝거나 유사하다.

- Contiguous cluster(Nearest neighbor)

- Connectivity-based cluster(neighborhood)

- Density-based Clusters밀도 기반 클러스터: 밀도가 높은 다른 지역과 저밀도 영역으로 구분되는 점의 밀도가 높은 영역으로 구분, 클러스터가 불규칙하거나 얽혀있을 때, 노이즈 및 특이치가 있을 때 사용

- Conceptual Clusters개념적 클러스터: 공통 속성을 공유하거나 특정 개념을 나타내는 클러스터

1) K-Means Clustering

: 각 클러스터는 Centroid와 관련, 각 점들은 가장 가까운 centroid를 가진 클러스터에 할당. 분할 클러스터링 접근 방식

- Closeness근접성 기준 및 측정 (: Euclidean distance, cosine similarity, correlation etc.)

- 평가: SSE(Sum of Squared Errors) 각 점에 대한 오차는 가장 가까운 군집까지의 거리 / SSE를 줄이는 한 가지 방법은 클러스터 수인 K를 늘리는 것

 

- 고려 요소: 초기 중심점 선택 (중심저의 점증적 갱신), Pre-processing(Normalize the data, Eliminate outliers), Post-processing(outlier로 간주될 수 있는 작은 클러스 제거, 느슨한 클러스터 분할, 가까운 클러스터 병합)

- 한계: Data containing outliers, when clusters are of (different size, different densities, non-globular shapes)

- 이등분 K-Means

2) Hierarchical Clustering

- Inter-Cluster Similarity

- Min(두 군집 사이의 거리를 각 군집에서 하나씩 관측값을 뽑았을 때 나타날 수 있는 거리의 최솟값): 노이즈 및 특이치에 덜 민감, 구형의 군집만을 찾는 경향

- Max(최대값): 큰 클러스터를 깨는 경향

- Group average(두 클러스터 점 사이의 쌍별 근접성의 평균): 전체 근접성은 큰 클러스터의 경우 더 크므로, 스케일링이 필요

- Distance between centroids(중심 간의 거리), Ward’s method

- Agglomerative Clustering Algorithm

1. Compute the proximity matrix

2. Let each data point be a cluster

Repeat {

Merge two closest clusters

Update the proximity matrix

}Until only a single cluster remains

3) Density-Based Clustering (DBSCAN)

- Density: 지정된 반경 내의 포인트 수

→ Core point: 한 점의 eps-반경 내에 minpts보다 많은 개체가 포함되면, Border point: eps 내에 minpts보다 적지만 core point 가 eps 반경 경계에 위치한 점, noise point: eps 반경 내에 minpts보다 작은 수의 개체를 포함하는 점이며 core point나 border point가 아닌 점

• Algorithm

1. eps와 minpts를 설정하여 점들을 구분

2. noise points를 제거한다.

3. eps - 반경 안에 있는 코어 점들을 서로 연결

4. 연결된 코어점들을 하나의 군집으로 형성

5. 경계점은 관련된 코어점을 포함하는 군집 중 하나에 할당

 

• 약점: 밀도 분포가 다양할 때 <-> 장점: 잡음에 견고함, 다양한 모양과 크기의 클러스터 처리 가능

 

Time-series Data Mining

- 시계열 데이터: 시간에 따른 반복 측정을 통해 수집되는 데이터

: 시계열 데이터 마이닝, 시계열 데이터에서 다양한 마이닝 기술로 의미를 찾는 작업. 시계열 데이터간의 유사도를 측정 (= 시계열 데이터간의 유사함을 판단한 수치, Euclidean distance. DTW distance)

1) Dynamic Time Warping(DTW)

: 시계열 분석에서, 속도가 다를 수 있는 두개 간의 시간-시퀀스 간의 유사성을 측정하는 알고리즘