[ADsP] 데이터마이닝 - 군집분석 (Cluster Analysis)

군집분석 
- 군집분석이란? (정의, 종류, 거리척도)
- 계층적 군집분석
- 비계층적 군집분석
- 혼합 군집분석
- SOM 자기조직화지도
- R코드를 통한 군집분석
 

군집분석(Clustering)이란?

• 객체의 유사성으로 그룹을 만들고, 이질성에 의해 그룹을 나누는 기법
• 형성된 군집들의 특성을 파악해 군집들 사이의 관계를 분석
• 군집분석의 종류:
  • 1) 계층적 - 최단연결법, 최장연결법, 평균연결법, 중심연결법, Ward연결법
  • 2) 분할적 - k-중심 군집, 퍼지 군집

---

거리척도

연속형 변수: 

• 유클리디안 거리 (Euclidean) - 두 점 사이 거리 계산할 때 주로 사용됨. 가장 짧은 거리 계산, 통계적 개념 x
• 맨하탄 거리 (Manhattan) - 두 점의 최단거리 , 변수들 차이의 단순 합
• 체비셰프 거리 (Chebychev) - 변수 간 거리 차이중 최댓값

범주형 변수: 

• 자카드 거리: 1-J(A,B) = 1 -(|A∩B|/|A∪B|) 
• 코사인 거리 - 두 벡터 사시의 사잇각을 계산해서 유사한 정도를 구하는석
  • 코사인거리 = 1-코사인 유사도

---

계층적 군집분석 (Hierarchial Clustering) 

합병형 / 분리형

• n개의 군집으로 시작해 점차 군집 갯수를 줄여나가는 방법 
• 이상치에 민감함 (거리에 기반하기 때문)
• 사전에 군집 수 k를 설정할 필요 x (탐색적 모형)
• 합병형 방법 (bottom-up)과 분리형 방법 (top-down)이 있음
  • 합병형에서 한번 군집에 속하면 다른 군집으로 이동 x
• 매 단계가 지역적 최적화 
• 덴드로그램 혹은 중첩클러스터로 표현할 수 있음

합병형 군집의 종류

• 최단연결법 - (최단거리) 거리가 가장 가까운 데이터를 묶어서 군집 형성 (고립된 군집을 찾는데 중점) 
• 최장연결법 - 최장거리를 계산하여 군집형성
• 평균연결법 - 거리 평균을 계산하여 군집 형성. 계산양이 많아질 수 있음. 
• 와드연결법 - 군집내의 오차제곱합에 기반한 군집 형성. 크기가 비슷한 군집끼리 병합하는 경향이 있음. 

 
덴드로그램 Dendrogram

• 기출예시) 덴드로그램의 y축 값을 주고, 몇개의 군집으로 나뉘는지 묻는 질문에서, y축 값으로부터 x축 방향으로 직선을 그어 만나는 선의 개수가 군집의 개수

y=1.5일때 군집의 수는 4개

계층적 군집화 단계: 
1. 모든 개체 간의 거리를 계산해서 거리행렬(distance matrix)을 만듦
2. 거리가 가장 가까운 두 개체 묶어서 군집화 
3. 다시 거리 행렬을 계산해서 갱신 (2,3에서 만든 군집 포함) (연결법에 따라 다름)
4. 모든 개체가 하나의 군집이 될 때까지 반복함
 
R프로그래밍으로 알아보는 계층적 군집

idx <- sample(1:dim(iris)[1], 40)
iris.s <- iris[idx,]
iris.s$Species <- NULL
hc <- hclust(dist(iris.s), method="ave")
plot(hc, hang=-1, labels = iris$Species[idx])

 
결과_덴드로그램

---

비계층적 군집분석

k-means 군집

• 사전에 군집 갯수 k를 정해야 함
• k가 원 데이터 구조에 적합하지 않으면 좋은 데이터를 얻을 수 없음
• 알고리즘이 빠르고 단순해서 계층적 군집보다 많은 양의 자료를 처리함 
• 잡음이나 이상값에 영향 받기 쉬움 (분석 전에 이상값을 제거하거나, 중앙값을 사용하는 k-medoids 사용)

k-means 군집화 단계:
1. 초기 군집 중심으로 k개의 객체를 임의 방식으로 선택
2. 각 자료를 가까운 군집의 중심에 할당
3. 각 군집 내의 자료들의 평균을 계산하여 군집의 중심을 갱신
4. 군집 중심의 변화가 거의 없을 때 까지 2,3 단계 반복
 

k-means clustering

 
 

DBSCAN (Density-based clustering of application with Noise)

• 밀도기반 군집으로 점이 세밀하게 몰려 있어 밀도가 높은 부분을 군집함
• 어느 점을 기준으로 반경 내에 점이 n개 이상 있으면 하나의 군집으로 인식
• 임의적 모양의 군집분석에 적합
• k값 정할 필요 없음
• 이상치에 의한 성능 하락을 완하할 수 있음

R 프로그래밍으로 알아보는 k-means clustering

data(iris)
newiris <- iris
newiris$Species <- NULL
kc <- kmeans(newiris, 3)
table(iris$Species, kc$cluster)
plot(newiris[c("Sepal.Length", "Sepal.Width")], col=kc$cluster)

 
결과

---

혼합분포군집 (Mixture Distribution Clustering)

• k 지정필요
• 데이터가 k개의 모수적 모형의 가중합으로 표현되는 모집단 모형에서 나왔다는 가정하에, 추정된 k개의 모형 중 어느 모형으로부터 나왔을 확률이 높은지에 따라 군집 분류 수행
• 봉우리가 여러개인 분포인 경우 사용
• 군집 크기 up, 추정의 정도 down
• 모수와 가중치 추정에 EM 알고리즘 사용됨

mixture dist. clustering

EM 알고리즘 (Expectation Maximization)

• 최대가능도(MLE)와 관련된 알고리즘 
• EM 알고리즘 단계: 
  • 1. 모두에 대해 임의의 초기값을 정함
  • 2. E단계: k개의 모형 군집에 대해 모수를 사용해 각 군집에 속할 사후확률을 구함
  • 3. M단계: 사후확률을 이용해 최대 우도 추정으로 모수를 다시 추정하고, 이를 반복함 

기출예시) EM알고리즘을 사용한 혼합분포 모형의 결과의 해석으로 잘못된것은? 

반복횟수 2회만에 로그가능도함수가 최대가 됨을 알 수 있다. 

*2회에서 높아지고, 그 뒤로도 조금씩 올라가기 때문에 최대는 아님. 

---

자기조직화지도 SOM (Self-Organizing Map)

• a.k.a 코흐넨 신경망 (Kohonen Neural Network)
• 비지도 학습의 예시, 인공 신경망의 한 종류
• 차원 축소와 군집화를 동시에 수행하는 기법 (고차원 데이터 -> 저차원 데이터)
• 구성: 입력층과 2차원의 격자 형태의 경쟁층
• 입력층(input layer): 입력 벡터를 받는 층
  • 변수의 개수와 동일한 뉴런 수 존재. 유런들은 완전 연결 되어 있음. 
• 경쟁층(competitive layer): 입력벡터에 따라 벡터가 한점으로 클로스터링 되는 층
  • 입력데이터와의 유사성 경쟁 -> 승자만이 출력을 내고, 승자와 그의 이웃만이 연결 강도를 수정하는 승자 독점 
  • 경쟁층에는 입력데이터와 가장 유사한 뉴런인 승자만 나타남

SOM vs. 신경망 모형 (시험에 출제)

	SOM	신경망 모형
구성	입력층, 경쟁층 2차원 그리드	입력층, 은닉층, 출력층 연속적인 layer
학습방법	전방패스의 경쟁학습 (빠른 속도) feed-forward flow	오차 역전파 알고리즘  Back propagation
분류	비지도 학습	지도 학습

---

군집모형평가 

• 실루엣 계수 (Sihouette scores) : 군집안의 데이터들이 다른 군집에 비해 얼마나 비슷한가
  • 하나의 데이터와 나머지 모든 데이터와의 거리 활용
• Dunn Index: DI가 클수록 군집화가 잘된 것