군집 분석 (Cluster Analysis) 2016년 가을학기 강원대학교 컴퓨터과학전공 문양세

K-Means 군집화 (K-Means Clustering) 계층 군집화 (Hierarchical Clustering) 강의 내용 Cluster Analysis 군집 분석의 개념과 종류 K-Means 군집화 (K-Means Clustering) 계층 군집화 (Hierarchical Clustering) 밀도기반 군집화 (Density-Based Clustering)

군집 분석이란? (What is Cluster Analysis?) 그룹내의 객체들은 유사하도록(관련이 있도록) 그룹간의 객체들은 유사하지 않도록(관련이 없도록), 주어진 객체들의 그룹 짓는 작업이다. Finding groups of objects such that the objects in a group will be similar (or related) to one another and different from (or unrelated to) the objects in other groups.

군집 분석의 응용 이해 (understanding) 요약 (summarization) Cluster Analysis 이해 (understanding) 브라우징을 위해 연관된 문서들을 그룹핑한다. 유사 기능을 갖는 유전자 혹은 단백질을 그룹핑한다. 유사한 가격 변화를 보이는 주식들을 그룹핑한다. 요약 (summarization) 대용량 데이터 집합의 크기를 줄인다.

군집 분석이 아닌 것은? Cluster Analysis

클러스터의 개념은 모호하다. Cluster Analysis Notion of a cluster can be ambiguous!

군집화(Clustering)의 종류 군집화란 클러스터의 집합(a set of clusters)을 구하는 작업이다. Cluster Analysis 군집화란 클러스터의 집합(a set of clusters)을 구하는 작업이다. 군집화는 크게 분할 군집화와 계층 군집화로 나눌 수 있다. 분할 군집화(Partitional Clustering): 데이터 객체들을 중복이 없는 부분집합으로 나눈다. 계층 군집화 (Hierarchical Clustering): 계층 트리에 의해 구성되며 하위 군집을 상위 군집이 포함(nest)하는 구조이다.

분할 군집화 Cluster Analysis

계층 군집화 Cluster Analysis

군집(Cluster)의 종류 잘 분리된 클러스터 (Well-separated clusters) Cluster Analysis 잘 분리된 클러스터 (Well-separated clusters) 중심기반 클러스터 (Center-based clusters) 연속된 클러스터 (Contiguous clusters) 밀도기반 클러스터 (Density-based clusters) 특성 클러스터 (Property clusters) 혹은 개념적 클러스터 (Conceptual Clusters)

군집 종류: Well-Separated Clusters Cluster Analysis

군집 종류: Center-Based Clusters Cluster Analysis

군집 종류: Contiguity-Based Clusters Cluster Analysis

군집 종류: Density-Based Clusters Cluster Analysis

군집 종류: Conceptual Clusters Cluster Analysis

Type of proximity or density measure Sparseness 입력 데이터 특징의 중요성 Cluster Analysis Type of proximity or density measure This is a derived measure, but central to clustering Sparseness Dictates type of similarity Adds to efficiency Attribute type Type of Data Other characteristics, e.g., autocorrelation Dimensionality Noise and Outliers Type of Distribution

K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 강의 내용 Cluster Analysis 군집 분석의 개념과 종류 K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 밀도기반 군집화 (Density-Based Clustering)

K-Means 군집화 Cluster Analysis

K-Means 군집화 – 상세 내용 Cluster Analysis

두 개의 서로 다른 K-Means 군집화 결과 Original Points Optimal Clustering Cluster Analysis Original Points Optimal Clustering Sub-optimal Clustering

K-Means 군집화 실행 예제 (1/2) Cluster Analysis

K-Means 군집화 실행 예제 (2/2) Cluster Analysis

K-Means 클러스터의 평가 군집화가 잘 되었는지의 평가: Sum of Squared Errors (SSE) Cluster Analysis 군집화가 잘 되었는지의 평가: Sum of Squared Errors (SSE)

초기 중심점 선택의 중요성 (1/2) Cluster Analysis

초기 중심점 선택의 중요성 (2/2) Cluster Analysis

초기 중심점 선택에서의 문제점 (1/4) 10 Clusters Example Cluster Analysis 10 Clusters Example Starting with two initial centroids in one cluster of each pair of clusters

초기 중심점 선택에서의 문제점 (2/4) 10 Clusters Example Cluster Analysis 10 Clusters Example Starting with two initial centroids in one cluster of each pair of clusters

초기 중심점 선택에서의 문제점 (3/4) 10 Clusters Example Cluster Analysis 10 Clusters Example Starting with some pairs of clusters having three initial centroids, while other have only one.

초기 중심점 선택에서의 문제점 (4/4) 10 Clusters Example Cluster Analysis 10 Clusters Example Starting with some pairs of clusters having three initial centroids, while other have only one.

초기 중심점 선택 문제의 해결책 Cluster Analysis

중심점의 점증적 갱신 (Updating Centers Incrementally) Cluster Analysis

Pre-processing and Post-processing Cluster Analysis

이등분 K-Means (Bisecting K-Means) Cluster Analysis 전통적 K-Means 알고리즘의 간단한 변형(variant) 하나의 클러스터에서 시작해서, SSE가 큰 클러스터들을 대상으로 이등분한다. 이등분은 2-Means 알고리즘을 적용하며, K개 클러스터를 얻을 때 까지 반복한다.

이등분 K-Means 예제 Cluster Analysis

K-Means 군집화의 한계 Cluster Analysis

K-Means 한계 – 크기가 다른 경우 Original Points K-means (3 Clusters) Cluster Analysis Original Points K-means (3 Clusters)

K-Means 한계 – 밀도가 다른 경우 K-means (3 Clusters) Original Points Cluster Analysis Original Points K-means (3 Clusters)

K-Means 한계 – 구형 모양 Original Points K-means (2 Clusters) Cluster Analysis Original Points K-means (2 Clusters)

K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 강의 내용 Cluster Analysis 군집 분석의 개념과 종류 K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 밀도기반 군집화 (Density-Based Clustering)

계층 군집화 Cluster Analysis 계층 트리로 구성된 중첩된 클러스터를 생성한다. (Produces a set of nested clusters organized as a hierarchical tree) 계통수(dendrogram)로 시각화될 수 있다. 계통수 형태의 트리는 레코드들의 병합/분할의 순서를 나타낸다.

계층 군집화의 장점 클러스터의 개수를 미리 가정/결정할 필요가 없다. Cluster Analysis 클러스터의 개수를 미리 가정/결정할 필요가 없다. 적당한 레벨에서 계통수를 자름(cutting)으로서 원하는 개수의 클러스터를 얻을 수 있다. 계통수(계층 트리)는 의미 있는 분류체계 (taxonomy)와 대응되기도 한다. 예제: 생물학에서 동물계(animal kingdom) 혹은 계통 재구성(phylogeny reconstruction)

계층 군집화의 두 가지 접근방식 병합형(agglomerative) 방식 분할형(divisive) 방식 Cluster Analysis 병합형(agglomerative) 방식 분할형(divisive) 방식 전통적 계층 알고리즘은 유사도(similarity) 혹은 거리 행렬(distance matrix)를 사용한다.

병합형 군집화 알고리즘 Cluster Analysis

시작 상황 (Starting Situation) Cluster Analysis

중간 상황(Intermediate Situation) (1/2) Cluster Analysis

중간 상황(Intermediate Situation) (2/2) Cluster Analysis

통합 이후(After Merging) Cluster Analysis

클러스터간 유사도의 정의는? (1/5) Cluster Analysis

클러스터간 유사도의 정의는? (2/5) Cluster Analysis

클러스터간 유사도의 정의는? (3/5) Cluster Analysis

클러스터간 유사도의 정의는? (4/5) Cluster Analysis

클러스터간 유사도의 정의는? (5/5) Cluster Analysis

클러스터 유사도 – MIN (1/2) Cluster Analysis 1 2 3 4 5

클러스터 유사도 – MIN (2/2) 5 1 3 5 2 1 2 3 6 4 4 Nested Clusters Dendrogram Cluster Analysis 5 1 2 3 4 5 6 4 3 2 1 Nested Clusters Dendrogram

MIN 사용 시 장점 Can handle non-elliptical shapes Two Clusters Cluster Analysis Two Clusters Original Points Can handle non-elliptical shapes

MIN 사용 시 단점 Sensitive to noise and outliers Two Clusters Cluster Analysis Two Clusters Original Points Sensitive to noise and outliers

클러스터 유사도 – MAX (1/2) Cluster Analysis 1 2 3 4 5

클러스터 유사도 – MAX (2/2) 5 4 1 2 3 4 5 6 2 3 1 Dendrogram Nested Clusters Cluster Analysis 5 4 1 2 3 4 5 6 2 3 1 Dendrogram Nested Clusters

MAX 사용 시 장점 Less susceptible to noise and outliers Two Clusters Cluster Analysis Two Clusters Original Points Less susceptible to noise and outliers

MAX 사용 시 단점 Tends to break large clusters Cluster Analysis Two Clusters Original Points Tends to break large clusters Biased towards globular clusters

클러스터 유사도 – Group Average (1/3) Cluster Analysis 1 2 3 4 5

클러스터 유사도 – Group Average (2/3) Cluster Analysis 5 4 1 2 3 4 5 6 2 3 1 Dendrogram Nested Clusters

클러스터 유사도 – Group Average (3/3) Cluster Analysis

계층 군집화 – 비교 Cluster Analysis 5 5 1 2 3 4 5 6 4 4 1 2 3 4 5 6 3 2 2 1 MIN MAX 3 1 5 5 1 2 3 4 5 6 4 4 1 2 3 4 5 6 2 2 Ward’s Method 3 3 1 Group Average 1

계층 군집화 – 복잡도 분석 Cluster Analysis

계층 군집화 – 문제점 및 한계 Cluster Analysis

K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 강의 내용 Cluster Analysis 군집 분석의 개념과 종류 K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 밀도기반 군집화 (Density-Based Clustering)

DBSCAN – 대표적 밀도기반 군집화 알고리즘 Cluster Analysis

DBSCAN: Core, Border, and Noise Points Cluster Analysis

DBSCAN 알고리즘 먼저, noise points를 제거한다. 나머지 points를 대상으로 밀도기반 군집화를 수행한다. Cluster Analysis 먼저, noise points를 제거한다. 나머지 points를 대상으로 밀도기반 군집화를 수행한다.

DBSCAN 예제 – Core, Border, and Noise Points Cluster Analysis

DBSCAN이 잘 동작하는 경우 Original Points Clusters Resistant to Noise Cluster Analysis Clusters Original Points Resistant to Noise Can handle clusters of different shapes and sizes

DBSCAN이 잘 동작하지 않는 경우 Original Points Varying densities Cluster Analysis (MinPts=4, Eps=9.75). Original Points Varying densities High-dimensional data (MinPts=4, Eps=9.92)

DBSCAN: EPS와 MinPts의 결정방법 Cluster Analysis 기본 아이디어: 클러스터내의 각 점들에 대해서, 해당 점의 k번째 인접 이웃(k-th nearest neighbor)이 대충(roughly) 동일한 위치에 있도록 한다. 노이즈는 k번째 인접 이웃이 다른 점들에 비해 멀리 떨어진 경우이다. 결국, 모든 점들에 대해서, 각 점들의 k번째 인접 이웃의 거리를 정렬하여 나타내고, 이를 바탕으로 적당한 EPS와 MinPts를 결정한다.

클러스터 유용성 (Cluster Validity) Cluster Analysis 감독 분류(supervised classification)에서는 모델을 평가하는 다양한 척도가 존재하였다. (예: accuracy, precision, recall) 군집 분석에서도, 결과로 얻어낸 클러스터들에 대해서 “얼마나 잘 군집화가 되었느냐?”와 같이 클러스터 질에 대한 질문을 수행할 수 있다. 그러나, 군집화 결과는 보는 사람의 관점(eye of the beholder)에 따라 좋고 나쁨이 달라질 수 있다. 그렇다면, 왜 군집화의 결과를 평가해야 하는가? To avoid finding patterns in noise To compare clustering algorithms To compare two sets of clusters To compare two clusters

랜덤 데이터에서 발견된 클러스터 DBSCAN Random Points K-means Complete Link(MAX) Cluster Analysis DBSCAN Random Points K-means Complete Link(MAX)

클러스터 유용성의 척도 Cluster Analysis

밀도기반 군집화의 다른 방법 격자기반 군집화 (Grid-Based Clustering) Cluster Analysis 격자기반 군집화 (Grid-Based Clustering) 데이터 공간을 격자(cell)로 나누고, 주어진 임계치보다 큰 밀도 값을 갖는 격자들을 추려낸 후, 연속된 격자들을 연결하여 클러스터를 형성한다. 부분공간 군집화 (Subspace Clustering) 전체공간이 아닌 부분공간을 대상으로 클러스터링을 수행한다. 다시 말해, 전체 속성이 아니 부분 속성을 대상으로 클러스터링을 수행한다.

격자기반 군집화 사례 Cluster Analysis

부분공간 군집화 사례 Cluster Analysis

K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 강의 내용 Cluster Analysis 군집 분석의 개념과 종류 K-Means 군집화 (k-Means Clustering) 계층 군집화 (Hierarchical Clustering) 밀도기반 군집화 (Density-Based Clustering)