데이터마이닝 _군집분석 :: 계층적군집, 비계층적군집, K-means clustering, EM알고리즘, SOM(자기조직화지도), 밀도기반함수, 실루엣계수, 응집도

데이터 마이닝

= 가정, 가설 없이 예측 가능한 분석에 초점을 두고 의미있는 정보를 찾아내는 방법

cf) 통계분석 = 가정, 가설을 가지고 추정하는것. 통계량과 그래프, 표를 이용하는 기술통계와 통계를 바탕으로 한 추측통계(ARIMA, 다차원척도법, 주성분분석) 가 있다.

 

미리 알아 맞추는 예측

1. 분류분석(classification)

2. 예측분석

 

데이터 특징을 나타냄으로써 사람, 상품에 대한 이해를 높이는 설명, 기술(description)이라는 목적

1. 군집분석(clustering)

2. 연관성분석

 

으로 크게 나눌 수 있다.

 

 

군집분석 (clustering)

= 관측된 변수값들로부터 유사성에만 기초하여 n개의 군집으로 집단화하여 집단의 특성을 분석하는 다변량 분석기법.

= 목적이 없는 비지도 학습.

 

 

통계적인 군집분석 방법으로는 아래와 같이 2개로 나눌 수 있다.

 

1. 계층적 군집 (군집개수 나중에)

= 유사한 개체를 군집화 하는 과정 반복

= 계층적 군집 형성 방법

• 병합적 방법 : 작은 군집으로 시작하여 군집 병합. 거리 가까우면 유사성 높음. R에서 stats패키지의  hclust()와 cluster패키지의 agnes(), mclust() 사용

• 분할적 방법 : 큰 군집에서 출발해서 군집 분리해나가는 방법. R에서 cluster패키지의 diana(), mona() 사용

= 군집의 결과는 계통도 또는 덴드로그램의 형태로 주어지며, 각 개체는 하나의 군집에만 속한다.

= 항목간의 거리, 군집간의 거리를 알 수 있고, 군집 내 항목간 유사정도를 파악하면서 군집의 견고성 해석 가능.

 

= 군집 간 거리 측정 기준(군집간 연결법)

• 최단연결법(=단일연결법) : 사슬모양 군집 발생 가능. 평균연결법보다 계산량 적다. 두 군집 사이의 거리는 하나의 관측값 뽑았을 때 나타날 수 있는 거리의 최소값으로 측정.

• 최장연결법(=완전연결법)

• 중심연결법 : 두 군집 결합시, 새로운 군집의 평균은 가중 평균 이용. 군집 내 편차들의 제곱합 고려하여 정보 손실 최소화.

• 평균연결법 : 모든 항목에 대한 거리 평균 구하면서 군집화. 계산량 많아짐.

• 와드연결법 : 군집 내 오차제곱합에 기초. 

= 군집 간 거리 측정 방법 (얼마나 유사한지 거리로 측정)

1) 연속형 변수

• 유클리드 거리 : 직선거리. 통계적 개념 내포 안됨. 산포정도 반영안됨.

• 맨하튼 거리 : 절댓값들의 합 

• 캔버라 거리 : ∑(x-y)/(x+y)

• 체비셰프 거리 : max(x-y)

• 민코프스키 거리 : m차원 민코프스키 공간에서의 거리.  맨하탄+유클리디안.

• 표준화 거리 : 통계적 거리. 측정단위 표준화. 표준편차 -> 유클리디안.

• 마할라노비스 거리 : 통계적 거리. 변수의 표준화 + 변수간의 상관성(공분산행렬) 고려

 

2) 명목형/범주형 변수

• 단순일치계수 : 매칭된(일치하는) 속성의 개수/ 전체 속성의 개수

• 자카드계수 : 0과 1사이 값의 유사도 측정. 불린 속성의 두개체일 경우, 동일하면 1, 완전 불일치이면 0.

• 코사인거리, 코사인계수

3) 순서형 자료

• 순위상관계수 : 값에 순위 매겨서 순위에 대한 상관계수 구함.

 

2. 비계층적 군집 (군집개수 미리 설정)

K means clustering (cl<-means(x,3) : 3개 군집)

= k개 초기 중심값은 임의로 선택.

= 초기 중심으로부터 오차제곱합 최소화하는 방향으로 형성. 군집 수정할 때 집단 내 제곱합 그래프.

= 100%가 seed 할당될 때까지군집 형성 후 다른 군집으로 이동 가능

= 이상값에 민감하여 경계설정 어려움

= 단점  보완 방법으로  k median clustering 사용하거나 이상값 미리 제거. PAM(Partioning Around Medoids)

= 비계층적, 분할적, prototype based

= 정규화 과정 필수

• mix-max : 0 또는 1 but 이상치 문제 발생

• z-score : 이상치에 대응 가능 but 정확히 동일한 척도로 계산 불가능.

 

3. 혼합 분포 군집

= 데이터가 k개 모수적 모형의 가중합으로 표현되는 모집단모형으로부터 나왔다는가정.

= 모수와 가중치를 추정하는 방법.

= k개의 각 모형은 군집을 의미하며, 각 모형에서 나왔을 확률에 따라 군집 분류.

= 확률 분포 도입하여 군집 수행.

= 군집을 몇 개의 모수로 표현할 수 있고, 서로 다른 크기의 군집을 찾을 수 있다.

= 이상값에 민감하므로 군집경계 설정이 어렵다. 이상값 제거 등 사전 조치 필요.

= 혼합 모형의 모수를 추정하는 경우, 미분을 통한 이론적 전개가 어려워 최대 가능도 추정을 위해 EM알고리즘 이용.

= EM알고리즘 모수추정에서 데이터가 커지면 수렴에 시간 걸림.

= 군집의 크기가 너무 작으면 추정의 정도가 떨어짐.

 

= EM알고리즘 (Expectation Maximize)

• 관측되지 않은 잠재변수에 의존하는 확률모델에서 최대가능도(*어떤 모수가 주어졌을 때, 원하는 값들이 나올 가능도를 최대로 만드는 모수를 선택하는 점추정방식) 나 최대사후확률(*모수의 사전확률과 결합된 확률 고려) 을 갖는 모수의 추정값을 찾는 반복적인 알고리즘.

• E step : 임의 파라미터 값 정하고 잠재변수 Z기대치 계산, M step : Z 이용하여 파라미터 추정 -> 가능도가 최대가 될때까지 반복하여 파라미터 추정값 도출.

 

그 외,

 

4. SOM Self Organization Map 자기 조직화 지도

= 대뇌피질과 시각피질의 학습과정을 기반으로 모델화한 인공신경망

= 자율학습방법에 의한 클러스터링 방법 적용

= 고차원의 데이터를 저차원의 뉴런으로 정렬하여 지도의 형태로 형상화한 비지도 신경망

= 차원축소와 군집화 동시에

= 입력변수의 위치관계를 그대로 보존한다

 

= 입력층 : 입력벡터를 받는 층으로 입력변수의 개수와 동일하게 뉴런 수 존재함. 학습을 통해 경쟁층에 정렬되어 map을 이룸. 입력층의 뉴런은 경쟁층의 뉴런과 각각 완전 연결되어 있음.

= 경쟁층 : 2차원 격자(grid)로 구성된 층으로, 입력 벡터의 특성에 따라 벡터의 한 점으로 클러스터링 되는 층. 전방패스(역전파X) 의 경쟁학습으로  각각의 뉴런이 입력 벡터와 얼마나 가까운지 계산하여 연결강도를 반복적으로 재조정 학습하면서, 입력패턴과 가장 유사한 경쟁층 뉴런이 승자가 된다. 승자뉴런만이 나타나며, 승자와 유사한 연결강도를 갖는 입력패턴이 동일한 경쟁 뉴런으로 배열됨.

 

= 알고리즘

1. 초기화 : SOM 맵 노드에 대한 연결 강도 초기화

2. 입력벡터 : 입력 벡터 제시

3. 유사도계산 : 유클리드 거리 사용해서 입력벡터와 프로토타입벡터 사이의 유사도 계산

4. 프로토타입 벡터 탐색 : 입력벡터와 가장 거리가 짧은 프로토타입벡터(Best Matching Unit BMU) 탐색

5. 강도 재조정 : BMU와 이웃들의 연결강도 재조정

6. 반복 : 단계2로 가서 반복.

5. 밀도 기반 군집 (=DB Optics, DEN CLUE)

= 어느 점을 기준으로 주어진 반경 내에 최소 개수만큼의 데이터를 가질 수 있게 한다.

= 특정 밀도 함수 혹은 밀도에 의해 군집을 형성해나가는 기법이다.

 

군집분석의 품질 평가

= 실루엣 평가 (실루엣 계수)

• 데이터 거리 짧을수록 응집도 ↑

• 군집 간 거리 멀수록 분리도 ↑(완벽분리 시, 실루엣 계수=1)