고정 헤더 영역
상세 컨텐츠
본문
군집화의 이해
군집화는 데이터를 클러스터(Cluster – 유사한 데이터 그룹)로 자동 분리하는 자율(unsupervised) 머신 러닝입니다. 군집화의 기본 아이디어는 유사성(similarity)을 바탕으로 합니다. 즉 클러스터 안에 있는 아이템은 서로 비슷해야 합니다. 반면 클러스터 밖에 있는 아이템과는 달라야 합니다.
군집화는 비지도 학습이고 정답이 없습니다. 찾고 있는 것이 무엇인지 모르기 때문에 군집화는 예측, 분류보다는 지식의 발견에 사용됩니다. 즉 군집화는 데이터를 그룹화하고 이 그룹에 대한 통찰력을 제공합니다.
군집화는 복잡한 데이터를 적은 개수의 그룹화 할 때 유용하며, 데이터 간 관계 패턴에 통찰력을 제공하여 의미 있고 실행 가능한 데이터 구조를 만듭니다.
군집화 사용 예
- 마케팅 캠페인을 위해 유사한 인구 통계나 구매 패턴을 가진 그룹으로 고객을 세분화
- 클러스터 밖의 사용 패턴을 찾아 무단 네트워크 침입과 같은 이상 행동을 탐지
- 유사한 값을 갖는 특징을 적은 개수의 동질적인 범주로 그룹화해 초대형 데이터셋을 단순화
군집화는 분류, 수치 예측, 패턴 감지 작업과는 조금 다릅니다. 분류, 수치 예측, 패턴 감지 작업에서 모델은 데이터 내에 존재하는 패턴을 설명합니다. 이와 대조적으로 군집화는 새로운 데이터를 생성합니다. 즉 데이터 내의 관계를 바탕으로 추론된 레이블을 제공합니다. 이를 자율 분류(unsupervised classification)이라고 합니다.
주목할 점은 자율 분류기에서 얻은 클래스 레이블은 본질적으로 의미가 없습니다. 군집화는 어떤 예시 그룹이 긴밀하게 연관돼 있는지는 말해주지만 실행 가능하고 의미 있는 레이블을 적용하는 것은 사람이 책임입니다.
K-평균 군집화 – K-Mean Clustering
K-평균 알고리즘은 비지도 학습이며 군집화 알고리즘 중 하나입니다. K평균 알고리즘은 군집화 방법 중 분할법에 속한다. 분할법은 주어진 데이터를 여러 파티션 (그룹)으로 나누는 방법이다.
K-평균은 N개의 데이터를 K개의 클러스터 중 하나에 할당합니다. 이 알고리즘의 목표는 클러스터 내의 차이를 최소화하고 클러스터 간의 차이를 최대화하는 것입니다.
군집을 구성할 때 모든 데이터의 오차함수를 최소화하려면 계산 비용이 매우 많이 듭니다(NP-난해(NP-hardness)문제로 알려졌습니다). 이 방법은 K와 N이 크면 연산량이 기하급수적으로 증가합니다.
대신 K-평균 알고리즘은 지역 최적(locally optimal) 해를 찾는 휴리스틱(heuristic)과정을 사용합니다. 이는 로컬 최솟값을 빠르게 수렴하는 방법으로 클러스터 할당을 취한 초기의 추정으로 시작해 그 다음에는 할당을 조금 수정하고 그 변경이 클러스터 내 동질성을 향상하는지 확인합니다.
K-평균의 경험적(heuristic) 특성 때문에 시작 조건을 약간 변경하면 최종 결과가 다소 달라질 수 있습니다. 결과가 크게 변한다면 문제가 있다는 것을 가리킵니다. 예를 들어 데이터가 적합한 그룹에 포함되지 않거나 K값이 잘못 선택된 경우입니다.
K-평균 알고리즘 수행 방법
1. 초기단계: K개 중심의 초기 집합을 결정합니다.
2. 할당단계: 각 데이터를 가장 가까운 클러스터에 할당합니다.
3. 수정단계: 각 클러스터에 대해 새로운 중심을 계산하여 새 클러스터에 할당합니다.
4. 종료단계: 중심점 이동이 없으면 종료합니다.
초기 단계
K-평균은 특정 값을 다차원 특징 공간의 좌표로 취급합니다. K-평균 알고리즘은 특징 공간에서 클러스터의 중심인 K개의 점을 선택합니다. 보통 이 점들은 훈련 데이터셋에서 임의로 골라서 선택합니다.
K-평균 알고리즘은 출발 위치에 매우 민감합니다. 즉 최종 클러스터 집합에 상당한 영향을 미친다는 의미입니다.
다음 그림은 K를 3개의 점이 임의로 선택한 경우입니다.
할당단계
초기 클러스터 중심을 선택한 이후 각 예시는 거리 함수에 따라 가장 가까운 클러스터 중심에 할당됩니다. K-평균은 유클리드 거리(Euclidean distance)를 대중적으로 사용하며, 맨해튼 거리(Manhattan distance), 민코스키 거리(Minkowski distance)도 사용합니다.
이 거리 함수를 이용해 각 데이터와 각 클러스터 중심 사이의 거리를 알아냅니다. 거리를 계산하므로 모든 특징은 수치여야만 합니다.
점선은 클러스터 중심에 의 생성된 브로노이 다이어그램(Voronoi diagram)의 경계를 나타냅니다. 브로노이 다이어그램은 다른 것보다 특정 클러스터 중심에 더 가까운 영역을 나타냅니다. 또한 세 경계가 만나는 점은 세 클러스터의 중심으로부터 최대 거리입니다. 이 경계를 이용해 초기 K-평균 시드(seed)가 차지하는 영역을 알 수 있습니다.
수정단계
수정단계는 초기 중심을 각 클러스터에 할당된 점들의 평균 위치로 이동합니다. 이 새로운 위치를 중심점(centroid)라고 합니다. 다음 다이어그램을 클러스터 중심이 새로운 중심점으로 이동할 때 보로노이 다이어그램의 경계도 이동되며 Cluster B에 있었던 점이 Cluster A로 추가되는 과정을 보여줍니다.
재할당 단계가 완료되면 다음 수정단계가 수행됩니다. 같은 방법으로 새 중심점을 계산하고 클러스터 경계를 수정하며, 데이터를 새 클러스터에 재할당합니다.
종료단계
두 개의 점이 추가로 재할당됐기 때문에 중심점을 옮기고 클러스터 경계를 수정하는 또 다른 수정 단계가 수행돼야만 합니다. 그러나 이러한 변경으로 재할당이 일어나지 않기 때문에 k-평균 알고리즘은 중단합니다.
보고단계
최종 클러스터는 두 가지 방법 중 하나로 보고될 수 있습니다.
1. A, B, C 와 같은 클러스터 할당을 보고합니다.
2. 최종 수정 후 클러스터 중심점의 좌표를 보고합니다.
두 가지 보고 방법 중 하나가 주어지면 중심점을 계산하거나 각 예시를 가장 가까운 클러스터에 할당함으로써 클러스터 경계를 정의할 수 있습니다
적합한 클러스터 개수 선택
K-평균은 클러스터 수에 매우 민감합니다. K를 크게 설정하면 클러스터의 동질성이 향상되며, 동시에 데이터에 과적합될 가능성이 높습니다.
이상적으로 실제 그룹에 대한
K 개수를 결정하는 가장 좋은 방법은 선험적(Priori) 지식입니다. 위 예시를 예로 들면 데이터 과학 컨퍼런스 좌석 문제에서 K는 초대된 학문적 연구분야 수를 반영할 수 있습니다.
사전 지식이 없다면 경험 법칙 중 하나는 k를 (n/2)의 제곱근 방법으로 결정합니다. 하지만 이 경험 법칙은 대형 데이터셋의 경우 많은 클러스터를 만들어 낼 수 있습니다.
다른 방법으로 엘보법(elbow method)이 있습니다. 이 기법은 다양한 K값에 대해 클러스터 내의 동질성(homogeneity)과 이질성(heterogeneity)이 어떻게 변하는지를 측정합니다.
다음 다이어그램에서 묘사된 것처럼 클러스터 내의 동질성은 클러스터가 추가되면서 증가할 것으로 예상되고, 이질성은 더 많은 클러스터와 함께 계속해서 감소할 것입니다. 목표는 동질성을 최대화하고 이질성을 최소화하는 것이 아니라 클러스터 수 변화가 미치는 영향이 작아지는 적절한 K를 찾는 것입니다. 이 K 값을 엘보 포인트(elbow point)라고 하는데 팔꿈치를 닮았기 때문입니다.
비고)
NP-hardness: 보통 입력 값이 많아질수록 알고리즘을 수행하는 데 걸리는 시간이 늘어나게 됩니다(예를 들면 n^k, k는 상수)만큼의 시간 안에 풀 수 있는 문제는 P 풀 수 있을지 모르는 문제를 NP문제라고 합니다. NP 난해 문제는 가장 어려운 NP 문제만큼 어려운 문제들이며 하나의 NP 난해 문제라도 다항식 시간 안에 풀 수 있다면 모든 NP 문제도 다항식 시간 안에 풀 수 있다고 합니다. 오차함수를 최소화하려고 일일이 모든 경우의 수를 다 확인해보는 것은 NP 난해 문제로 알려져 있습니다.
휴리스틱한 방법은 최적값으로 수렴한다는 보장은 없으며, 결과는 초기 중심을 어떻게 정했는지에 영향을 받습니다. 일반적으로 이 알고리즘의 속도는 매우 빠르므로 초기 중심을 바꿔가면서 여러 번 알고리즘을 수행하여 결과들을 비교해보고 최종 결과를 결정합니다.
글이 도움이 되셨다면 공감 부탁 드립니다.
감사합니다.
[References]
Tensorflow 첫걸음
R을 활용한 머신러닝
댓글 영역