Clustering Analysis

<군집(Cluster) : 주요 아이디어>
- 목표
  - 데이터 세트에 대한 통찰력을 생성할 목적으로 비슷한(동질적) 레코드들의 그룹(군집)형성

- 비슷한 고객 그룹으로 '시장을 세분화하는 데' 사용된다
  - characterize the clusters useful for the aims of the analysis
 - marketing strategy is tailored for each segment



<기타 적용>
- 원소 주기율표 : Mendeleev
- 생물 종 분류
- 주식 포트폴리오 그룹화 : balanced portforlios
- 경제 구조분석을 위한 회사 그룹화
- 육군 군복 크기 : 20 sizes with 5 measurements
- 마케팅 : 고객 정보를 이용한 시장 세분화
- 인터넷 검색엔진 : 사용자들이 검색한 검색어를 군집화하여 검색 알고리즘 향상



<2차원 이상으로 확장>
- 군집화는 눈으로 이루어진다
- 다차원의 경우, 다음과 같은 알고리즘이 필요
  - 거리 측정 방법
    - 군집을 형성하는 데에서 거리를 이용하는 방법

- 2개의 알고리즘 : 계층적 그리고 비계층적



<계층적 방법>
- 응집 방법
  - n-군집으로 시작(각각의 레코드를 자신의 군집으로)  
  - 하나의 군집이 남을 때까지 레코드들을 군집 안으로 합한다(완전한 데이터 세트)
  - 가장 많이 쓰인다

- 분할 방법
  - 전체를 포함하는 하나의 군집으로 시작
  - 더 작은 군집들로 계속 분할



<비계층적 방법>
- k-평균 군집화 방법
 - k개의 군집이 미리 정해져 있다
  - 계산 집약적이지 않으므로 대용량 데이터에서 선호



<거리측정>
- distance metric : dissimilarity measure
 - 레코드들 간
  - 군집들 간

- 2개의 레코드 간의 거리
  - 레코드 i와 레코드 j
  - 유클리드 거리가 가장 유명



<정규화>
- 문제점 : 원시적 거리 측정은 측정치의 단위에 크게 영향을 받는다
- 해법 : 먼제 데이터를 정규화(표준화)
  - 평균을 빼고 표준편차로 나눈다
  - z-scores라고도 부른다

- 22개 회사에 대해
  매출평균 = 8,914, 표준편차 = 3,550

- Arizona 매출 9,077의 정규화된 값
  (9,077 - 8,914)/3,550 = 0.046



<수치형 데이터의 여타 거리 측정>
- 두 레코드(i, j)간의 거리 : p개의 예측변수 사용
- 상관관계에 기반한 유사성: 거리 = 1 – 상관계수^2
- 통계적 거리 (마할라노비스)

- 맨해튼 거리 (절대 차이): 𝑑_𝑖𝑗=∑2_(𝑚=1)^𝑝▒|𝑥_𝑖𝑚−𝑥_𝑗𝑚 |
- 최대좌표거리: 𝑑_𝑖𝑗=max┬(𝑚=1,2,⋯𝑝) |𝑥_𝑖𝑚−𝑥_𝑗𝑚 |
- Gower의 유사도 (다양한 형식들을 혼합: 연속적 & 범주적 변수들을 포함하는 레코드인 경우)




<범주형 데이터의 유사성>
- 이진형 변수(0/1)로 구성된 2개 레코드 간의 거리를 측정하기 위해, 2x2 분할표 생성:

                  0     1   레코드j
레코드 i  0  a     b
              1  c     d
- 유사성 측도는 이 표에 근거: p=a+b+c+d (예측변수 개수)
- a: 두 레코드간 속성이 존재하지 않는 예측변수 개수
- d: 두 레코드간 속성이 존재하는 예측변수 개수
- 매칭 계수 = (a+d)/p
- 자카드 계수 = d/(b+c+d)  : 무속성 일치인 a는 무시
  - “1” 매칭이 “0” 매칭보다 유사성이 훨씬 드러나는 경우에 사용(e.g. “Corvette 스포츠카 소유” : 1 이 0보다 두 레코드간의 유사성에 더 큰 의미가 있음)




<군집 간의 거리 측정(군집A에서 군집B로)>
- 최단 거리(minimum distance)
 - 단일연결법('single' linkage)이라고도 한다
  - 두 군집 간의 거리는 가장 가까운 레코드 Ai와 Bj쌍 사이의 거리이디

- 최대 거리(maximum distance)
 - 완전연결법('complete' linkage)이라고도 한다
  - 두 군집 사이의 거리는 서로 가장 먼 레코드 Ai와 Bj 쌍 사이의 거리이다



<평균거리(average distance)>
- 평균연결법(‘average’ linkage)이라고도 함
- 두 군집 간의 거리는 모든 가능한 거리 쌍의 평균이다



<중심거리(centroid distance)>
- 두 군집 간의 거리는 두 개의 군집 중심점('centroid' linkage)사이의 거리이다
- 중심점은 군집 내 모든 레코드들을 변수 별로 평균한 벡터이다



<계층적 군집화 단계(응집 방법 사용)>
1. n 군집으로 시작 (각각의 레코드는 자신의 군집)
2. 가장 가까운 레코드 2개를 하나의 군집으로 병합
3. 각각의 연속적 단계에서, 서로 가장 가까운 2개의 군집이 병합된다

덴드로그램은 밑에서 위로 이 과정을 보여준다




<덴그로그램 읽기>
- 군집화 과정 보기: 아래쪽에 연결된 선들이 먼저 병합된다
  - New England and United will be merged first, then Madison and Northern

- 군집의 개수 결정: 주어진 “군집 간의 거리”에서, 수평선은 군집을 생성하기 위해 멀리 떨어진 군집들을 교차한다




<군집 타당성>
- 목표 : 의미 있고 유용한 군집을 얻는 것

- 군집의 바람직한 특성들
  1. Cluster Interpretability(군집의 설명 가능성)
  - 군집에 사용된 각 변수들의 요약통계량을 구한다
  - 또한 군집화에 사용되지 않은 변수 측면에서 군집을 검토한다
  - 군집에 적절한 라벨을 붙인다.
  - 개별 변수 값의 히트맵을 시각적으로 확인해 각 군집을 더 특성화 가능

  2. Cluster Stability(군집의 안정성) – 군집들과 군집 평가는 입력에서 작은 변화에 민감한가?
    -데이터를 A, B로 나누어서  A를 이용해서 군집 평균을 구한 후 이를 이용해서 B의 군집분석 결과와  A+B에서 군집분석결과와 유사한가를 비교

  3. Separation(군집의 분리) – 군집 내 변동에 대한 군집 간 변동의 비율을 검토(높을수록 좋다)

  4. Number of Clusters(군집의 개수) - 분석 목적에 맞는 유용한 군집 개수




<비계층적 군집 : k-평균 군집화 알고리즘(K-Means Clustering Algorithm)>
1. 원하는 군집의 개수, k를 선택  
2. k개의 군집으로 분할하면서 시작
 - k 중심점을 임의로 선택하는 것에 기반
3. 매 단계마다, 각각의 레코드를 가장 가까운 중심점의 군집으로 이동
4. 중심점 재계산, 3단계 반복
5. 레코드 이동이 군집 내 분산을 증가시킬 때 중단
   (주의) k=3으로 가정하고 동영상에서 설명



<k-평균 알고리즘 : k를 선택하고 초기 분할>
- 외적 고려 사항(사전지식, 실질적 제약 조건)이 있을 때 이를 고려해서 k를 선택
    또한 약간 다른 k로 실험해서 군집 결과를 비교
  e.g., “얼마나 많은 시장 세분화를 원하는가?”

- 군집으로의 초기 분할은 임의적이거나 domain 지식에 근거할 수 있다.
   만약 임의 분할이라면, 여러 개의 k로 임의 분할로 과정을 반복해서 비교.