수안이의 컴퓨터 연구실
출처 : http://progray.vogle.com/1215
군집분석의 개요
객체간의 유사성 척도
이를 일반화시킨 것을 민코우스키 거리(Minkowski distance)라 하는데 이는 다음과 같이 정의된다.
군집분석의 개요
하나의
객체(object)가 여러 속성(attribute)을 갖는다 하고 이러한 객체가 다수 있다고 할 때 군집분석이란 유사한 속성들을
갖는 객체들을 묶어 전체의 객체들을 몇 개의 그룹 또는 군집(cluster)으로 나누는 것을 말한다. 예를 들어, 회사에서
관리하는 고객들에 대하여 구매행태를 반영하는 속성들에 대한 데이터가 수집된다고 할 때 유사한 구매행태를 보이는 고객들을 서로
그룹핑하는 것을 군집분석이라 할 수 있겠다. 따라서 이 예의 경우 군집분석의 목적 중 하나는 서로 다른 그룹의 고객들에게 서로
다른 마케팅 전략을 수립하는 것이 될 것이다.
군집분석을 수리적으로 표현한다면 전체 n개의 객체가 있다고 할 때 이들을 서로 배타적인 k개의 부분집합으로 나누는 것이다. 군집방법(clustering method)은 무수히 많으나 크게 계층적 방법(hierarchical method)과 비계층적 방법(non-hierarchical method)으로 구분된다.
계층적 방법은 사전에 군집 수 k를 정하지 않고 단계적으로 서로 다른 군집결과를 제공하는 것인데, 이는 다시 집괴법(agglomerative method)과 분리법(divisive method)으로 나뉜다. 집괴법이란 각 객체를 하나의 군집으로 간주함을 시작으로 유사한 객체들을 묶어 군집으로 만들고 다시 유사한 군집들을 묶어 새로운 군집을 만들어 나가는 과정을 전체의 객체들이 하나의 군집이 되기까지 반복한 후 어떤 규칙에 의하여 최종적인 군집결과를 제공하는 방법이다. 분리법은 집괴법의 역순이라 할 수 있는데, 즉 전체의 객체를 하나의 군집으로 간주함을 시작으로 유사성이 떨어지는 객체들을 분리시켜다른 군집으로 만들어 나가는 과정을 각 객체가 하나의 군집이 될 때까지 반복한 후 어떤 규칙에 의하여 최종적인 군집결과를 제공하는 것이다.
비계층적 방법은 사전에 군집 수 k를 정한 후 각 군집의 대표값 또는 대표 객체를 정하고 각 객체를 k개 중 하나의 군집에 배정하는 것이다. 이러한 배정은 대체로 한번에 이루어지는 것은 아니고 배정 후 새로운 군집 대표값을 산출하여 각 객체에 대한 새로운 배정을 하는 과정을 군집결과가 수렴할 때까지 반복적으로 시행한다.
군집방법의 기본 아이디어는 한 군집내의 객체들 간의 유사성은 가능한 한 크게, 서로 다른 군집간의 유사성은 가능한 한 작도록 군집들을 형성하는 것이다. 이를 위해서는 객체간의 유사성 및 군집간의 유사성의 정의가 필요하다. 군집분석을 위한 데이터에는 분류분석의 경우와는 달리 목표변수(target/dependent variable)이 없으므로 학습의 과정이 없음이 특징이다.
군집분석을 수리적으로 표현한다면 전체 n개의 객체가 있다고 할 때 이들을 서로 배타적인 k개의 부분집합으로 나누는 것이다. 군집방법(clustering method)은 무수히 많으나 크게 계층적 방법(hierarchical method)과 비계층적 방법(non-hierarchical method)으로 구분된다.
계층적 방법은 사전에 군집 수 k를 정하지 않고 단계적으로 서로 다른 군집결과를 제공하는 것인데, 이는 다시 집괴법(agglomerative method)과 분리법(divisive method)으로 나뉜다. 집괴법이란 각 객체를 하나의 군집으로 간주함을 시작으로 유사한 객체들을 묶어 군집으로 만들고 다시 유사한 군집들을 묶어 새로운 군집을 만들어 나가는 과정을 전체의 객체들이 하나의 군집이 되기까지 반복한 후 어떤 규칙에 의하여 최종적인 군집결과를 제공하는 방법이다. 분리법은 집괴법의 역순이라 할 수 있는데, 즉 전체의 객체를 하나의 군집으로 간주함을 시작으로 유사성이 떨어지는 객체들을 분리시켜다른 군집으로 만들어 나가는 과정을 각 객체가 하나의 군집이 될 때까지 반복한 후 어떤 규칙에 의하여 최종적인 군집결과를 제공하는 것이다.
비계층적 방법은 사전에 군집 수 k를 정한 후 각 군집의 대표값 또는 대표 객체를 정하고 각 객체를 k개 중 하나의 군집에 배정하는 것이다. 이러한 배정은 대체로 한번에 이루어지는 것은 아니고 배정 후 새로운 군집 대표값을 산출하여 각 객체에 대한 새로운 배정을 하는 과정을 군집결과가 수렴할 때까지 반복적으로 시행한다.
군집방법의 기본 아이디어는 한 군집내의 객체들 간의 유사성은 가능한 한 크게, 서로 다른 군집간의 유사성은 가능한 한 작도록 군집들을 형성하는 것이다. 이를 위해서는 객체간의 유사성 및 군집간의 유사성의 정의가 필요하다. 군집분석을 위한 데이터에는 분류분석의 경우와는 달리 목표변수(target/dependent variable)이 없으므로 학습의 과정이 없음이 특징이다.
객체간의 유사성 척도
객체간의 유사성의 정도를 정량적으로 나타내기 위해서
척도가 필요하다. 가장 보편적으로 많이 사용되는 것이 거리(distance)인데 거리와 같이 클수록 유사성이 적어지는 척도는
보다 엄밀하게 비유사성 척도(dissimilarity measure)라 한다.
각 객체가 p개의 속성 또는 변수(variable)를 갖는다 하고 객체 i의 j번째 변수를
라 하면 객체 i의 p차원 공간에서의 좌표는 다음과 같은 열벡터로 표현된다.
각 객체가 p개의 속성 또는 변수(variable)를 갖는다 하고 객체 i의 j번째 변수를
이 때 객체 i와 객체 j의 유클리드 거리(Euclidean distance)는 다음과 같이 정의된다.
이를 일반화시킨 것을 민코우스키 거리(Minkowski distance)라 하는데 이는 다음과 같이 정의된다.
여
기서 m=2일 때 유클리드 거리를 나타내며, m=1일 때는 맨하탄 거리(Manhattan or rectilinear
distance)를 나타낸다. 그러나 군집분석에서는 통상 유클리드 거리가 가장 많이 사용되며, 별도의 언급이 없는 한
‘거리’라고 하면 유클리드 거리를 지칭한다.
위의 거리의 정의에서 보듯이 변수들 간의 단위 등이 다른 경우 큰 값을 갖는 변수가 거리의 값을 주도할 수 있다. 이러한 불합리를 해소하기 위하여 종종 표준화된 거리(standardized distance)를 사용한다. 변수간의 상관관계가 있는 경우 이를 고려하는 거리척도로 마할라노비스 거리(Mahalanobis distance) 가 있다. 이는 표준화된 거리를 보다 일반화한 것으로 변수의 분산-공분산 행렬(variance-covariance matrix)을 사용하는 것이다.
위의 거리의 정의에서 보듯이 변수들 간의 단위 등이 다른 경우 큰 값을 갖는 변수가 거리의 값을 주도할 수 있다. 이러한 불합리를 해소하기 위하여 종종 표준화된 거리(standardized distance)를 사용한다. 변수간의 상관관계가 있는 경우 이를 고려하는 거리척도로 마할라노비스 거리(Mahalanobis distance) 가 있다. 이는 표준화된 거리를 보다 일반화한 것으로 변수의 분산-공분산 행렬(variance-covariance matrix)을 사용하는 것이다.
계층적 군집방법
개요에서 언급한 바와 같이 계층적 군집방법에는 집괴법과 분리법이 있으나 여기서는 집괴법에 대하여 주로 소개한다. 계층적 군집방법에서는 주로 군집간의 유사성 척도를 활용하고 있는데, 편의상 거리와 관련된 다음과 같은 비유사성 척도를 사용하고 있다.
개요에서 언급한 바와 같이 계층적 군집방법에는 집괴법과 분리법이 있으나 여기서는 집괴법에 대하여 주로 소개한다. 계층적 군집방법에서는 주로 군집간의 유사성 척도를 활용하고 있는데, 편의상 거리와 관련된 다음과 같은 비유사성 척도를 사용하고 있다.
1) 단일연결법(single linkage method; nearest neighbor method)
단일연결법에서는 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 거리 중 가장 가까운 거리를 사용한다. 단일연결법은 두 군집의 유사성을 가장 짧은 거리를 갖는 객체 쌍으로 평가하고자 하는 것이다. 이를 최단거리법이라고도 한다.
단일연결법에서는 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 거리 중 가장 가까운 거리를 사용한다. 단일연결법은 두 군집의 유사성을 가장 짧은 거리를 갖는 객체 쌍으로 평가하고자 하는 것이다. 이를 최단거리법이라고도 한다.
2) 완전연결법(complete linkage method; farthest neighbor method)
완전연결법에서는 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 거리 중 가장 먼 거리를 사용한다. 완전연결법은 두 군집의 유사성을 가장 먼 거리를 갖는 객체 쌍으로 평가하고자 하는 것이다.
완전연결법에서는 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 거리 중 가장 먼 거리를 사용한다. 완전연결법은 두 군집의 유사성을 가장 먼 거리를 갖는 객체 쌍으로 평가하고자 하는 것이다.
3) 평균연결법(average linkage method)
평균연결법은 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 평균거리를 사용한다.
평균연결법은 군집간의 유사성 척도로 두 군집의 모든 객체 쌍의 평균거리를 사용한다.
4) 중심연결법(centroid linkage method)
군집을 이루는 객체들의 중심이 되는 좌표를 그 군집의 중심(centroid)라 하는데, 중심연결법은 군집간의 유사성 척도로 두 군집의 중심간 거리를 사용한다.
군집을 이루는 객체들의 중심이 되는 좌표를 그 군집의 중심(centroid)라 하는데, 중심연결법은 군집간의 유사성 척도로 두 군집의 중심간 거리를 사용한다.
위의 네 가지 군집방법은 군집간 유사성 척도 평가방법이 다를 뿐 군집화를 위한 알고리즘은 동일하게 아래와 같이 진행된다.
연결법 군집 알고리즘
단계 0. (1) 각 객체를 하나의 군집으로 간주한다.
(2) k=n
단계 1. (1) 현재의 군집 결과에 있는 모든 군집 간의 쌍에 대하여 군집간 유사성척도를 산출하며,
이 중 최소가 되는 군집 i와 군집 j를 묶어 하나의 군집으로 만든 후 군집결과를 수정한다.
(2)
단계 2. k=1이면 Stop, 그렇지 않으면 단계 1을 반복한다.
이
상과 같이 연결법에 의한 계층적 군집방법은 각 객체를 하나의 군집으로 시작하여 군집들을 묶어가는 과정을 반복하여 결국 모든
객체가 하나의 군집이 되도록 하는 것이다. 따라서 적절한 군집수를 결정하는 문제가 중요하게 되는데 통상적으로 단계별 군집 결과를
시각화한 트리(tree)형태의 덴드로그램(dendrogram)을 그린 후 정성적으로 판단한다.
비계층적 군집방법
비
계층적 군집방법은 분할방법(Partitioning method)이라고도 하는데, 군집의 수를 사전에 지정하고 대상 객체들을
적절한 군집에 배정하는 방법이다. 이 방법은 n개의 객체를 k개의 군집에 할당하는 것이라고 할 수 있으며, 대표적인 방법으로
K-means 방법, K-medoids 방법, 퍼지 K-means 방법 등이 있다.
1) K-means clustering
K-means 군집방법은 비계층적 군집방법 중 가장 널리 사용되는 것으로 그 절차는 다음과 같다.
K-means 군집방법은 비계층적 군집방법 중 가장 널리 사용되는 것으로 그 절차는 다음과 같다.
단계 0. (초기 객체선정) 어떤 규칙에 의하여 k개의 객체의 좌표를 초기 군집의 중심좌표(centroid)로 선정한다.
단계 1. (객체의 군집배정) 각 객체에 대하여 k개의 군집 중심좌표와의 거리를 산출한 후 가장 가까 운 군집에 그 객체를 배정한다.
단계 2. (군집 중심좌표의 산출) 새로운 군집에 대한 중심좌표를 산출한다.
단계 3. (수렴조건 점검) 새로 산출된 중심좌표값과 이전 좌표값을 비교하여 수렴조건 내에 들면 마치 며, 그렇지 않으면 단계 1을 반복한다.
2) K-medoids clustering
군집의 대표 객체(medoid)란 그 군집에 속하는 객체 중 다른 객체들과의 평균(또는 전체) 거리가 최소가 되는 객체를 말한다. K-medoids 군집방법은 객체들을 주어진 수의 군집으로 구분하는데, 각 객체와 그 객체가 속한 군집의 대표 객체와의 거리의 총합을 최소로 하는 방법이다. K-medoids 군집방법의 알고리즘으로 잘 알려진 것에는 다음과 같은 것이 있다.
군집의 대표 객체(medoid)란 그 군집에 속하는 객체 중 다른 객체들과의 평균(또는 전체) 거리가 최소가 되는 객체를 말한다. K-medoids 군집방법은 객체들을 주어진 수의 군집으로 구분하는데, 각 객체와 그 객체가 속한 군집의 대표 객체와의 거리의 총합을 최소로 하는 방법이다. K-medoids 군집방법의 알고리즘으로 잘 알려진 것에는 다음과 같은 것이 있다.
(1) PAM (Partitioning Around Medoids)
(2) CLARA (Clustering LARge Applications)
(3) CLARANS (Clustering Large Applications based on RANdomized Search)
본 방법은 K-means에 비하여 이상치에 덜 민감한 장점은 있으나 계산 시간이 오래 걸리는 단점이 있다.
3) Fuzzy K-means clustering
이 방법은 K-means 방법과 유사하나, 하나의 객체가 여러 군집에 속할 가능성을 허용하는 확률(아래에서 Pij 또는 이를 확장한 퍼지) 개념을 도입한 것이다. 즉, Fuzzy k-means 알고리즘은 다음과 같이 진행된다.
이 방법은 K-means 방법과 유사하나, 하나의 객체가 여러 군집에 속할 가능성을 허용하는 확률(아래에서 Pij 또는 이를 확장한 퍼지) 개념을 도입한 것이다. 즉, Fuzzy k-means 알고리즘은 다음과 같이 진행된다.
단계 0. k, m(퍼지상수), 수렴조건을 정한다.
초기 k개의 군집을 임의로 정한다(Pij=1 또는 0).
단계 1. 각 군집의 중심좌표를 산출한다.
단계 2. 객체 i가 군집 j에 속할 확률 Pij을 산출한다.
단계 3. 객체 i를 Pij가 가장 큰 군집 j에 배정하여 군집결과를 얻는다.
이전의 군집결과와 비교하여 동일하면 Stop, 그렇지 않으면 단계 1로.
"Database" 카테고리의 다른 글
- Business Intelligence (0)2008/10/07
- 정보공학 기반 모델링 vs 객체지향 모델링 (0)2008/06/04
- 데이터마이닝 기법 : 군집분석 (1)2007/08/20
- Introduction to SQL (0)2007/07/25
- Mysql의 root 비밀번호 변경하기 (0)2006/12/19
Leave your greetings.
데이터마이닝이 무엇인지 궁금해서 이리저리 둘러보다가 오게 되었습니다.
2009/08/04 13:35 [ Permalink : Modify/Delete : Reply ]정리 정말 잘 해놓으셨네요.
감사히, 잘 보고 갑니다!