이 장에서는 사용자 그룹을 만드는 방법을 알아보겠습니다. 온라인 상거래 사이트는 사용자를 그룹으로 나누어 캠페인, 세일 등의 마케팅 전략을 세웁니다. 예를 들어 디비디와 블루레이를 판매하는 사이트에 20대 남성이 많을 경우, 20대 남성이 좋아할 만한 영화를 적극 프로모션하는 식 입니다.'20대 남성'과 같은 성별 및 연령 정보 말고도 구매 이력을 이용하여 그룹을 만들 수도 있습니다. 예를 들어 마블 슈퍼 히어로 영화를 구매하는 마블팬 그룹 같은 것 말이죠. 그러려면 제일 먼저 사용자으 ㅣ구매 이력을 살펴볼 필요가 있습니다. [표 4-1]은 가사의 사용자 구매 이력 데이터 입니다.
표 4-1 사용자 구매 이력 데이터
피처 피처값
사용자 ID abdc
구매일시 2017/04/01
구매상품영 [Blu-ray]캡틴 아메리카:시빌 워 2D + 3D Combo (2Disc)
구매상품 가격 30000
구매상품 수 1
구매상품 카테고리 DVD/블루레이
이 데이터를 이요해서 사용자의 구매 패턴을 정의해 봅시다. 일반회원/VIP(구매 횟수 및 구매 총액), 정기구매회원/단발성회원(구매횟수), 가전제품구매자/생활용품구매자(구매상품 카테고리), 저가 상품구매자(구매상품 가격의 평균), 마블팬(구매상품명) 등 하나의 데이터셋으로 무수한 패턴을 정의할 수 있습니다. 2장에서 설명한 대로 모델을 만들어 문제를 풀 경우 각 패턴에 대해 일일이 모데을 만들어야 합니다. 여기에서 사용자의 성별, 연령, 주소 등 사용자 정보까지 더해지면 계산이 매우 복잡해집니다. 어쩌면 우리가 상상도 할 수 없는 패턴이 존재할 수있습니다. 이와 같이 '사용자 그룹 만들기'는 수학적 모델을 만들기 어려운 대표적인 무제입니다. 이 문제를 푸는 방법으로 군집화에 대해 알아보겠습니다.
4.1 군집화
데이터 특징을 이요한 그룹핑 문제에서는 특정 패턴을 정의하여 모델을 만드는 방법보다 비슷한 데이터를 한데 모으는 방법이 더 효율적입니다. 이 방법을 군집화라고 합니다. 이 방법은 미리 그룹을 정의하지 않기 때문에 비지도학습에 속합니다. 크게 중심 기반 군집화, 계층적 군집화, 밀도 기반 군집화로 나눌 수 있습니다. 다음은 각 방법에 대한 간단한 소개입니다.
-중심 기반 군집화(prototype-based clustering): 클러스터를 크러스터 중심점으로 정의하는 기법입니다.
- 계층적 군집화(hierarchical clustering): 클러스터의 크기에 따라 클러스터의 계층을 정의하고 계층의 상하위를 이용하는 기법입니다.
- 밀도 기반 군집화(density-based clustering): 클러스터를 데이터가 높은 밀도로 모여 있는 공간으로 보는 기법입니다.
군집화의 핵심 아이디어는 비슷한 데이터를 한데 묶는다는 겁니다. 그렇다면 비슷하다는 것, 즉 유사도가 높다는것은 무슨 의미일까요? 데이터를 이루는 피처값이 비슷하다는 겁니다. 사용자 구매이력을 생각해보면, 비슷한 상품을 구매하는 사용자를 한데 묶을 수 있습니다. 또한 비슷한 연령대 사용자를 한데 묶을 수도 있습니다.
예를 들면 X는 사용자 1, Y는 사용자 2를 의미하고, 데이터를 X를 X={x1, x2, x3, x4,...xm}으로, 데이터 Y를 Y={y1, y2, y3....ym}으로 정의합니다. 여기서 m은 피처 수입니다. [표 4-1]을 기준으로 예를 들어보면 x1과 y1은 구매상품 개수, x2와 y2는 구매상품명 등으로 생각할 수 있습니다. 그럼 각 피처의 차이의 총합 가 적을 수록 비슷한 사용자라고 할 수 있습니다.
하지만 단순히 차이를 전부 한 피처에 대해 +가 나오고, 다른 한 피처에 대해 - 가 나오면 두 데이터 사이의 피처값이 많이 다름에도 불구하고 전체 합이 0이 될 수 있습니다. 따라서 단순한 차이 대신 그 차이를 제곱한 값을 더하여 얻어진 값에 루트를 사용합니다. 수학적 정의는 다음과 같습니다.
식4-1 유클리드 거리(민코스키 거리의 특수한 경우)
d(X, Y) = 루트(합((xi-yi)제곱))) = ||X-Y||
그러고 보니 이 식은 두 점사이의 최단 거리인 유클리드 거리(Euclidean distance)를 구하는 식과 같습니다. 일반적으로 유클리드 거리를 구하는 식은 계산의 편의를 위해 위 식을 제고(제곱유크릴드 거리)하여 사용합니다.
여기서 궁금한 점이 생깁니다. 가격 2만원과 1뭔의 차이인 100000이, 연령 25세와 25세의 차이인 1과 같다고 할 수 있을까요? 또 연령의 차이를 뺄셈으로 구하는 것 이해가 되는데, 상품명의 차이는 어떻게 구할 까요? 성별의 차이는 수학적으로 표현할 수 있을까요? 이에 대해서는 3.3절 '데이터 표준화'에서 살펴본 데이터 표준화 방법을 적ㅇ둉하면 됩니다. 또한 [식 4-1]에서 차이값을 제곱하지 않고 그냥 절댓값을 취하면 어떻게 될까요? 이에 대해서는 4.5절 '유사도 계산'에서 자세히 살펴보겠습니다.
4.2 K-중심 군집화
이 절에서는 중심기반 군집화의 대표적인 예인 K-중심 군집화( K-centroid clustering, K-medoid clustering) 에 대해 알아보겠습니다. 중심 기반 군집화는 클러스터 중심점을 정한 후 클러스터 중심점에 가까운 데이터들을 모아가며 클러스터를 확장하는 방법으므로 군집화 초기에 몇 개의 중심점을 어떻게 배치하는가 중요합니다. K-중심 군집화는 초기에 K개의 중심점을 랜덤으로 선택하여 군집화를 시작합니다.
중심 기반 군집화에서는 클러스터 수 K와 함께 클러스터 중심을 어떻게 구하느냐를 정할 필요가 있습니다. 여러 데이터를 요약하는 방법으로 평균(mean), 대푯값(median), 최빈값(mode)이 있다는 것은 아실 겁니다(중학교 때 변량, 도수 등을 배운 것 기억하시죠?). 클러스터 안의 데이터의 평균값을 중심으로 사용할 경우 K-평균 군집화, 대푯값을 사용할 경우 K-대푯값 군집화( K-medians clustering),최빈값을 사용할 경우 K-최빈값 군집화(K-modes clustering)라고 합니다. 3가지 방법 모두 중심점을 구르는 방법이 다를 뿐 전체 군집화 과정은 동일합니다.
K-주심 군집화는 다음 절차를 거칩니다.
1. 임의로 뽑은 K개의 데이터를 중심으로 하는 클러스터를 만듭니다(각 클러스터가 데이터 하나씩만 가지고 있습니다.)
2. 각 데이터와 클러스터 중심 간의 거리를 계산합니다.
3. 데이터와 클러스터 중심 간의 거리가 가장 짧은 클러스터에 데이터를 할당하고 이 데이터를 포함하여 클러스터 중심을 업데이트 합니다.
4. 과정 2와 3을 반복하는데, 과정3에서 더 이상 중심의 위치가 변하지 않거나, 업데이트 정후 중심점의 차이가 사용자가 지정한 허용 오차 이내이거나, 사용자가 지정한 횟수만큼 반복했으면 종료합니다.
과정 3에서 가장 가까운 클러스터에 데이터를 할당하고 있습니다. K-중심 군집화에서 클러스터는 클러스터 중심으로 정의되므로 결국 데이터와 클러스터 중심 사이의 거리가 가장 짧게 되는 클러스터를 찾는 것입니다.[식4-2]를 이용하여 거리를 구할 수 있습니다.
식4-2 클러스터 안의 데이터와 클러스터 중심 간의 거리
||x-uc||2
x:데이터
uc: 클러스터 c의 중심점
군집화는 각 데이터에 대해 [식4-2]의 값을 최소화하는 것이 목적입니다. 그런데[식4-2]를 자세히 보면 2.2.1절 '산술 손실함수'에서 살펴본 제곱 손실함수와 같은 형태임을 알 수 있습니다.
loss(f) = (y - y')2
f : 모델
y : 데이터로부터 주어진 출력
y':모델에 데이터로부터 주어진 입력을 넣어서 계산한 값
따라서 분산 분석과 같은 제곱 손실함수에 대한 이론을 k-중심 군집화에도 적용할 수 있습니다.
과정 4에서 업데이트가 없으면 군집화를 종료한다고 했는데, 이는 각 데이터가 속한 ㅡㄹ러스터가 변하지 않는 것, 즉 수렴한다는 것을 의미합니다. 하지만 수렴되기까지 상당한 시간이 걸리므로 실제로는 이전 단계의 총제봅합과 새로 얻은 총제곱합의 차이가 허용오차보다 작거나, 클러스터 중심 업데이트의 횟수가 사용자가 지정한 반복 횟수 이상이면 군집화를 종료합니다.
클러스터 수 k, 허용 오차, 반복 횟수 모두 사용자가 지정하는 파라미터이므로 군집화 결과를 보면서 바꾸어 가며 시도해야 데이터를 잘 표현하는 그룹을 만들 수 있습니ㅏㄷ. 이에 대해서는 10장에서 실제 구현을 통해 설명하겠습니다.
4.3 계층적 군집화
계층적 군집화에서의 계층은 클러스터의 계층을 의미합니다. 최상위 계층의 클러스터느 모든 데이터를 포함하는 하나의 클러스터입니다. 최하위 계층의 클러스터는 단 하나의 데이터만을 포함하므로 클러스터 수가 데이터 수와 같게 됩니다.
계층적 군집화에는 하향식인 분할적 군집화와 상향식인 집괴적 군집화가 있습니다. 사용자가 클러스터 수 k를 명시적으로 지정하는 k-중심 군집화와는 달리 계층적 군집화는 클러스터 수를 지정할 필요가 없습니다.
계층적 군집화는 각 단계마다 한 쌍의 클러스터를 비교하는데, 하향식인 분할적 군집화는 각 계층의 클러스터들을 둘로 쪼개어 하위 계층으로 진행하고, 상향식인 집괴적 군집화는 각 계층의 클러스터들 중에 가장 가까운 두 개를 하나로 합쳐 상위 계층의 클러스터를 만들어 갑니다.
같은 계통 트리를 만들어서 클러스터의 생성 과정을 시각화하기 쉽다는 것이 계층적 군집화의 장점입니다.
계층적 군집화에서 주의할 점은 늘 한쌍의 클러스터만 비교한다는 겁니다. 예를 들어 데이터에 실제 존재하는 클러스터가 3개라고 하더라도 계층적 군집화는 2n개의클러스터만 생성할 수 있으므로 데이터를 잘 표현할 수 없습니다. 군집화 전에 클러스터 수가 2n개가 아니라는 점을 알고 있다면 계층적 군집화보다는 k-중심 군집활르 하는 것이 좋습니다.
k-중심 군집화에서는 k 값에 따라 군집화의 성능이 달라지는 것과 마찬가지로, 계층적 군집화에서는 클러스터를 어느 정도로 분할 혹은 병합하는가에 따라 군집화의 성능이 달라집니다. 계통 트리를 통한 클러스터 생성 과정, 클러스터 안의 데이터 분석 등을 통해 적절한 클러스터를 찾을 수 있습니다.
집괴적 군집화는 다음 순서로 진행됩니다.
1. 하나의 데이터를 하나의 클러스터로 지정합니다.
2. 과정 1의 클러스터들에 대해 가장 유사도가 높음 클러스터 둘을 하나로 합칩니다.
3. 과정 2에서 생성된 클러스터들에 대해 다시 같은 과정을 반복합니다.
클러스터 둘을 합칠 때 복수의 데이터로 이루어진 클러스터 간의 유사도를 측정할 필요가 있습니다. 대표적인 방법으로 단일 연결법(single linkage), 완전 연결법(complete linkage), 평균 연결법(averae linkage)이 있습니다.
- 단일 연결법: 두 클러스터에 속하는 데이터들의 거리 중에 가장 짧은 거리를 클러스터 사이의 거리로 간주합니다.
- 완전 연결법: 두 클러스터에 속하는 데이터들의 거리 중에 가장 먼 거리를 클러스터 사이의 거리로 간주합니다.
- 평균 연결법: 두 클러스터에 속하는 데이터들의 거리 평균을 클러스터 사이의 거리로 간주합니다.
그럼 어떤 방법이 가장 나을까요? 알핏 생각하면 클러스터 안의 모든 데이터를 고려하는 평균 연결법이 가장 나을 것 같기도 합니다. 하지만 평균 연결법을 사용할 경우 한 쌍의 클러스터 내의 모든 데이터의거리를 구하므로 다른 두 방식보다 계산량이 늘어난다는 단점이 있습니다. 데이터에 따라서는 평균 연결법 혹은 단일 연결법이 시간이 덜 걸리고 비슷하게 좋은 클러스터를 만들 수도 있습니다.
분할적 군집화의 대표적인 예인 DIANA(Divisive Analysis,분할 분석)는 다음과 같은 과정으로 클러스터를 생성합니다.
1. 현 단계에서 가장 큰 클러스터를 선택합니다(가장 처음에는 전체 데이터를 하나의 클러스터 안에 있다고 간주합니다).
2. 과정 1의 클러스터에서 가장 이질적인 데이터를 찾습니다. 예를 들어 클러스터 안의 데이터 평균에서 가장 동떨어진 데이터를 찾습니다. 이로써 클러스터를 평균점과 이질적인 점을 중심으로 하는 두 클러스터로 나눌수 있게 됩니다.
3. 과정 2에서 구한 두 점(평균점, 이질적인 점)과 각 데이터의 거리를 계산하여 거리가 짧은 점을 중심으로 하는 클러스터로 데이터를 할당합니다.
4. 한 클러스터가 데이터 하나만을 가질 때까지 과정 1, 2, 3을 반복합니다.
분할적 군집화도 앞에서 사용한 연결 방법을 통해 거리를 측정합니다. 하지만 모든 데이터를 작은 클러스터로 나눈다는 점에서 k-중심 군집화와 굉장히 비슷한데다가, 클러스터 수의 지정이 자유로운 k-중심 군집화와는 달리 클러스터 수가 2n개라는 제약이 있어 많이 상요하지 않습니다.
4.4 밀도 기반 군집화
밀도 기반 군집환느 데이터 밀도가 높아지는 방향으로 데이터를 군집화하는 방식입니다. 대표적인 밀도 기반 군집화 알고리즘에는 평균이동 군집화와 DBSCAN(density-based spatial clustering of application with noise, 디비크캔, 노이즈를 가지느 애플리케이션의 밀도 기반 공간 군집화)이 있습니다.
평균이동 군집화는 다음과 같은 과정으로 진행됩니다.
1. 임의의 초기 중심점을 지정하거나 탐색 반경을 지정합니다(초기 중심점을 지정하지 않으면 탐색 반경에 따라 초기 중심점이 결정됩니다.)
2. 지정한 줌심점으로부터 지정한 반경을 가지는 원 안의 밀도를 계산한 후 데이터의 밀도가 가장 높은 곳을 중심점으로 재지정합니다. 데이터의 밀도가 높다는 것은 데이터가 많이 몰려 있다는 뜻입니다. 일반적으로 데이터가 정규분포(가우스분포)를 따른다고 가정하여 평균 주변에 데이터가 가장 많이 몰려 있다고보고, 반경 안의 평균점을 새로운 중심점으로 지정합니다.
3. 더 이상 중심점이 이동하지 않을 때까지, 즉 중심점이 가장 밀도가 높은 곳으로옮겨질 때까지 단계2를 반복합니다.
4. 단계 3에서 얻은 마지막 중심점이 클러스터의 중심점이 되고, 중심점의 이동 경로에 있던 데이터들을 그 클러스터에 할당합니다.
평균이동은 중심점을 갱신한다는 점에서 중심 기반 군집화로 분류되기도합니다.
DBSCAN은 반경의 밀도가 아니라 클러스터 중심의 데이터 수와 가장자리의 데이터 수의 차이를 이용합니다. DBSCAN에서 데이터는 다음과같이 나누어집니ㅏㄷ.
- 중심 포인트(core point):반경e 안에 일정 개수 이상의 데이터가 존재하는 데이터
- 경계 포인트(border point): 반경 e안에 있는 데이터 수는 중심 포인트보다 적지만, 중심 포인트로부터 반경 e안에 존재하는 데이터
- 노이즈 포인트(noise point): 중심 포인트도 경계 포인트도 아닌 데이터
데이터셋 안의 모든 데이터를 군집화하는 k-중심 군집화나 계층적 군집화와는 달리 밀도 기반 군집화는 예외 데이터를 정의하고 군집화 과정에서 그것을 제외시킵니다. 또한 클러스터 중시과 데이터 사이의 거리를 이용하는 k-중심 군집화와 계층적 군집화의 경우 중심으로부터의 같은 거리 안에 있는 모든 점이 같은 클러스터에 속하게 되므로 클러스터가 원형이 될 수빡에 없습니다. 이와 달리 밀도 기반 군집화는 클러스터 모양에 제한이 없습니다.
4.5 유사도계산
이 절에서는 유사도를 측정하는 대표적인 척도인 '거리'에 대해 자세히 살펴보겠습니다. 유사도가 클수록 거리가 줄어들기 때문에 거리가 가깝다는 것은 유사도가 크다는 것이고 거리가 멀다는 것은 유사도가 작다는 겁니다. 이절에서는 다음과 같은 거리를 다룹니다.
- 민코스키 거리: 벡터 공간 안의 두 점 사이의 거리
- 마할라노비스 거리: 점들의 분포를 고려한 거리
4.5.1 민코스키 거리
4.1절'군집화'에서 데이터를 X를 X={x1,x2, x3....xn},데이터Y를 Y={y1, y2, y3...yn}, 피처수를 m이라고 했을 때의 유크릴드 거리를 정의했습니다. 그때의 [식 4-1]은 민코스키 거르의 특수한 경우입니다. 민코스키 거리는 다음과 같이 정의됩니다.
식 4-3 민코스키 거리
d(x,y)= p루트(총함(i=1~m)|xi-yi|p
여기서 p가 1일 때는 맨해튼 거리(Manhattan distance혹은 L1 거리), 2일 때는 유크릴드 거리(Euclidean distance 혹은 L2거리)라고합니다.
맨해튼 거리는 맨해튼의 도로가 격자 모양으로 되어 있어서 한 빌딩에서 다른 빌딩까지의 이동 거리가 두 좌푯값의 차의 절댓값을 합한 값이 되기 때문에 붙여진 이름입니다.
그럼 언제 맨해튼 거리를 쓰고 언제 유클리드 거리를 싸야 할까요? 맨해튼 거리는 거리 계산 시 제약이 있을때 유용합니다. 예를 들어 체스 케임의 경우 각각의 말은 체스 판 위를 자유롭게 움직이는 게 아니라 움직일 수 있는 방향이 정해져 있습ㄴ디ㅏ. 비숏과비숍이 이동할 수 있는 칸을 별표로 표시했습니다. 체스 판의 한칸 (a1,b1)에서 다른칸(a2, b2)으로 비숍을 이동시킬 때 비숍의 디오거리는 루트 | a2 -a1| + | b2 - b1|이 됩니다. 반면 유클리드 거리는 두점 사이의 최소거리르 제약 없이 구할 때 사용합니다.
4.5.2 마할라노비스 거리
마할라노비스 거리(Mahalanobis distance)는 두 점사이의 거리를 계산할 때 데이터의 분포를 고려하는 거리입니다.
공분산이란 두 변수가 얼마나 연관성이 있는지 나타내는 값입니다. 공분산의 값이 1이면 한 변수가 증가할 때 다른 변수도 증가하는 것이고, -1이면 한 변수가 증가할 대 다른 변수가 감소하는 것입니다. 0이면 두 변수 간에 아무런 상관관계가 없습니다. X와 Y가 k개의 실수로 이루어진 벡터고, ux가 X값의 평균, uy가 Y값의 평균일 때, 공분산은 다음과 같이 계산합니다.
Cov(X,Y) = E[(X-ux)(Y-uy)]
X = {x1, x2, x3...,xk}
Y = {y1, y2, y3...yk}
ux = X값의 평균
uy = Y값의 평균
공분산을 고려한다는 것은 X값의 증감과 Y값의 증감의 관계를 거리 계산에 넣는 것입니다. 즉, 키가 평균에서 표준편차의 2배로 멀어지는 것은 몸무게가 평균에서 표준편차의 1배로 멀어지는 것과 같다는 정보를 이용합니다.
마할라노비스 거리는 거리 계산에 위에서 설명한 데이터의 분포 및 공분산을 사용합니다. 수식으로 표현하면 다음과 같습니다.
d(x,y) = 루트((xi-yi)TS-1(xi-yi))
댓글 없음:
댓글 쓰기