글
클러스터링 알고리즘 탐구
클러스터링 기법은 크게 분할(partitioning) 접근과 계층적(hierarchical) 접근으로 나눌 수 있습니다. 분할 접근은 범주 함수를 최적화시키는 K개의 분할 영역을 결정해 나가는 방법으로 유클리드 거리(euclidean distance) 측정법에 기반합니다. 숫자 속성(numeric attribute) 데이터를 군집화하는데 쓰이는 가장 오래되고 잘 알려진 파티션 알고리즘 중에 K-평균(K-means) 알고리즘이라는 것이 있습니다. 이 알고리즘을 사용하려면 몇 개의 그룹으로 나누기 원하는지 K를 입력해야 합니다. 그러면 알고리즘은 일단 K개의 평균점을 지정하고 모든 데이터를 하나씩 보면서 가장 가까운 평균점에 해당되는 그룹에 할당합니다. 그 후에 다시 평균점들을 조금씩 바꾸어 나가면서 데이터를 가까운 그룹에 재할당합니다. 이 과정은 군집 상태를 나타내는 척도 함수가 더 이상 변하지 않을 때까지 반복되며 더 이상 변하지 않게 되면 그 상태의 그룹들을 군집화의 결과로 정합니다.
계층적 접근은 처음에 각각의 데이터 점을 하나의 클러스터로 설정한 후 이들 쌍 간의 거리를 기반으로 하여 분할, 합병해 나가는 상향식(bottom-up) 방식으로 모든 점들이 하나의 대형 클러스터에 속하게 될 때까지 그 히스토리 정보를 유지해 나가게 됩니다. 이것은 agglomerative hierarchical clustering이라 하며 ‘가까운’ 객체끼리 군집화시키는 방법입니다. 이 알고리즘에서는 우선 모든 n개의 데이터가 n개의 서로 다른 그룹이라 가정한 후에 그룹간의 유사성(similarity)을 보고 가장 유사한 두 개의 그룹을 합병해(merge) 그룹 수를 줄여가는 과정을 전제 그룹 수가 K개가 될 때까지 반복함으로써 K개의 그룹을 찾아냅니다. 또한 군집의 병합 또는 분리되는 과정은 이차원 도면의 Dendrogram을 사용하여 간략히 표현되며 군집화 과정에서 어떤 개체가 일단 다른 군집에 속하면 다시는 다른 군집에 속하지 못합니다.
클러스터링 알고리즘에서 사용하는 기본적인 용어와 전제 조건, 그리고 표기 방법에 대해서 정리해 보겠습니다. 일반적으로 p개의 변수를 서로 다른 두 개체 Xi와 Xj를 각각 다음과 같이 표현할 경우 다음과 같습니다.
Xi = (Xi1, Xi2, …, Xip)
Xj = (Xj 1, Xj 2, …, Xj p)
두 개체 사이의 거리 dij는 dij = d(Xi, Xj )으로 표현하며 다음의 조건을 만족합니다.
dij ≥ 0, dij = 0
dij = dji
dik ＋ djk ≥ dij
예를 들어 데이터가 <표 3>과 같고 클러스터의 수 K=2를 발견하기 위해서 클러스터링 기법을 적용해 보겠습니다. 이때 유사성을 나타내는 함수는 두 점간의 Euclidean 거리로 사용하면 ID 1과 ID 2의 거리는 다음과 같이 계산되며 각 점들의 거리는 <표 4>와 같습니다.
<표 3> 수입과 명품 선호도 데이터
<표 4> 각 개체 사이의 거리
이때 ID 4와 ID 5가 가장 거리가 가깝기 때문에 <그림 3>과 같이 먼저 그룹화됩니다.
생성된 군집과 각 개체간의 거리를 구하기 위해서 첫 번째 군집에 속한 임의의 두 개체와 아직 군집에 속하지 않은 각 개체 사이의 거리 중 최단거리로 군집과 개체간의 유사성을 결정하는 최단 연결법을 적용하여 거리를 구하면 다음과 같습니다.
<그림 3> 첫 번째 군집 생성
d {(C1, C2)} = min { d (x, y)｜x ∈ C1, y ∈ C2 }
d {(1), (4, 5)} = min { d14, d15 } = d14 = 61.0
d {(2), (4, 5)} = min { d24, d25 } = d24 = 42.4
d {(3), (4, 5)} = min { d34, d35 } = d34 = 18.6
즉, <표 5>에서 그룹화된 (4, 5)는 ID 3과 거리가 가장 가깝기 때문에 <그림 4>와 같이 (3, 4, 5)로 그룹화됩니다.
생성된 군집과 각 개체간의 거리를 다시 최단 연결법을 적용하여 거리를 구하면 다음과 같습니다.
<표 5> 첫 번째 군집과 개체 사이의 거리
<그림 4> 두 번째 군집 생성
d {(1), (3, 4, 5)} = min { d13, d14, d15 } = d14 = 61.0
d {(2), (3, 4, 5)} = min { d23, d24, d25 } = d24 = 42.4
즉, <표 6>에서 보면 ID 1과 ID 3이 거리가 가장 가깝기 때문에 <그림 5>와 같이 그룹화되며 이런 방식으로 남아 있는 그룹의 개수가 K일 때까지 반복합니다. 여기서는 초기 설정한 군집의 수 K=2를 만족하므로 클러스터링 분석을 마칩니다. 이것은 <그림 6>과 같이 Dendrogram으로 표현됩니다.
<표 6> 두 번째 군집과 개체 사이의 거리
<그림 5> 세 번째 군집 생성
<그림 6> 군집 생성 Dendrogram
이 알고리즘의 장점 중 하나는 군집화를 마칠 때까지의 과정이 트리 구조를 가지고 있어 drill down하거나 drill up하면서 어느 단계에서 군집화를 멈추는 것이 가장 잘 된 군집화인지를 사용자가 모두 확인해 보고 가장 좋다고 생각되는 것을 선택할 수 있다는 것입니다. 일반적으로 다차원 데이터를 군집화하기 위해 유사성을 계산할 때 여러 가지 함수를 쓸 수 있습니다. Euclidean 거리, Mahalanobis 거리, Manhattan 거리, Minkowski 거리 등 여러 가지가 있는데 그 중에 어떤 것을 사용해 군집화를 하느냐에 따라 다른 특성을 갖는 군집화가 이뤄집니다.
지금까지는 주로 숫자 속성을 가진 데이터의 군집화 알고리즘을 설명했는데 범주형 속성의 경우 거리라는 개념의 적용이 쉽지 않습니다. 즉 범주형 속성의 경우 X ≠ Y는 알 수 있으나 X ＞ Y 혹은 X ＜ Y는 알 수 없습니다. 그래서 일반적으로 범주형 변수로 측정되는 두 개체 사이의 거리는 두 개체가 서로 다른 범주에 속한 횟수를 이용합니다. 예를 들면 <표 7>과 같이 성별(sex), 직업(job), 거주지역(address) 같은 범주형 데이터가 있다고 가정합니다. 이 경우 ID 1과 ID 2 사이의 거리는 2(불일치수=2), ID 1과 ID 3 사이의 거리는 1(불일치수=1), ID 2과 ID 3 사이의 거리는 3(불일치수=3)이 됩니다. 그러나 속성이 연속형과 범주형이 혼합되어 있을 때는 이와 같은 방법은 더 이상 유용하지 않습니다. 따라서 일반적인 클러스터링 알고리즘에서는 최소한 순서형 범주를 갖는 이산형 변수까지를 분석대상으로 포함하는 경우가 많습니다. 클러스터링 알고리즘은 이렇게 다양한 다차원 데이터의 분포 상태나 패턴 등을 효율적으로 찾아내기 위한 방안과 데이터베이스 지향적인 제약 사항들(제한된 메모리 양, I/O 시간 최소화 등)을 해결하기 위해서 계속 연구되고 있습니다.
<표 7> 범주형 변수 데이터
계층적 클러스터링의 군집간 거리 계산법
◆ 최단 연결법(Single Linkage Method)
군집 U와 군집 V 사이의 거리 dUV를 각 군집에 속하는 임의의 두 개체들 사이의 거리 중 최단거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
◆ 최장 연결법(Complete Linkage Method)
군집 U와 군집 V 사이의 거리 dUV를 각 군집에 속하는 임의의 두 개체들 사이의 거리 중 최장거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
◆ 평균 연결법(Average Linkage Method)
군집 U와 군집 V 사이의 거리 dUV를 각 군집에 속하는 모든 개체들의 평균거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
◆ 중심 연결법(Centroid Linkage Method)
군집 U의 중심점과 군집 V의 중심점 사이의 거리를 두 군집 사이의 거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
◆ 중위수 연결법(Median Linkage Method)
군집 U와 군집 V 사이의 거리 dUV를 각 군집에 속하는 임의의 두 개체들 평균을 합하여 2로 나눈 값(군집의 크기를 고려하지 않은 단순평균)을 근간으로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
◆ Ward의 방법
군집 U와 군집 V를 묶을 때 생기는 새로운 군집 i에 속해 있는 객체들의 오차 제곱합을 ESSi라고 하고 전체 군집의 오차 제곱합을 ESS = ∑ESSi 라고 할 때 새로운 군집으로 인하여 파생되는 ESS의 증가량을 두 군집 사이의 거리로 정의하여 가장 유사성이 큰 군집을 묶어 나가는 방법
<그림 7> 군집간 거리 계산 도해
distribution 을 이용하여 극한 값을 가려낼 수 있는데, 데이터의 극한 값을 찾는데 쓰이기도 한다. 그 판단의 기준은 
RECENT COMMENT