[ADP 필기] 군집분석

<군집분석>

– 유사성이 높은 대상 집단을 분류하고
– 군집에 속한 객체들의 유사성과 서로 다른 군집에 속한 객체 간의 상이성을 규명
– 교차타당성으로 안정성 검토

• vs 요인분석: 유사한 변수를 함께 묶어줌
• vs 판별분석: 사전에 집단이 나누어져 있음

<거리 구하기>

*연속형 변수의 경우

 

① 유클리디안 거리: 데이터간 유사성을 측정할 때 많이 사용
(통계적 개념이 내포되지 않아 변수들의 산포 정도가 전혀 감안 되어 있지 X)

 

② 표준화 거리: 해당 변수의 표준편차로 척도 변환한 후 유클리디안 거리 계산
→ 유클리디안 거리 + 표준화
→ 척도차이, 분산차이로 인한 왜곡을 피할 수 있음

 

③ 마할라노비스 거: 통계적 개념 포함, 변수들의 산포를 고려하여 이를 표준화한 거리
→ 유클리디안 거리 + 통계적 표본공분산
– 두 벡터 사이의 거리를 산포를 의미하는 표본공분산으로 나누어줘야 함
– 그룹에 대한 사전 지식 없이는 표본공분산 S를 계산할 수 없으므로 사용 곤란

④ 체비셰프 거리: 두 점 사이의 거리를 각 차원에서의 최대 차이로 정의

⑤ 맨하탄 거리: 두 점 사이의 거리를 각 차원의 절대 차이의 합으로 정의
→ 각 방향 직각의 이동거리 합으로 계산

⑥ 캔버라 거리: 두 점 사이의 차이를 각 차원별로 정규화한 뒤 합산

⑦ 민코우스키 거리: 유클리디안 거리(L1)와 맨하탄 거리(L2)를 일반화한 형태
*p는 거리 지수로, p=1일 때 맨하탄 거리, p=2일 때 유클리디안 거리

*범주형 변수의 경우

① 자카드 거리: 주로 이진 데이터에 적용되며, 범주형 데이터나 부울 데이터의 유사성을 측정

② 코사인 거리: 문서를 유사도 기준으로 분류 혹은 그룹핑할 때 유용하게 사용

*코사인 유사도 – 두 개체의 벡터 내적 코사인 값 이용, 측정된 벡터 간의 유사한 정도

 

*예제) A=[1, 0, 5], B= [4, 7, 3]

*계층적 군집분석

– n개의 군집으로 시작해 점차 군집 개수를 줄여 나가는 방법, 합병형/분리형

• 최단연결법: n*n 거리 행렬에서 거리가 가장 가까운 데이터를 묶어서 군집 형성
• 최장연결법
• 평균연결법
• 와드연결법: 군집 내 편차들의 제곱합을 고려→ 군집 간 정보 손실을 최소화하기 위해 군집화
• 군집화: 거리행렬 → 관계규명 → 덴드로그램 → 적절한 군집 수 선정 (5개 이상 X)

*비계층적 군집 분석

– n개 개체를 g개 군집으로 나눌 수 있는 모든 가능한 방법을 점검해 최적화한 군집 형성

• k-평균 군집 분석- 각 클리스터와 거리 차이의 분산을 최소화하는 방식으로 동작
  (군집의 개수, seed) → 군집을 형성 → 가장 가까운 seed*의 군집으로 분류→ 재계산
  *임의로 선택 가능, 가급적 멀리 떨어지게

→ 연속형 변수에 활용 가능
→ 초기 중심값의 선정에 따라 결과가 달라질 수 있음
→ 초기 중심값으로 부터의 오차 제곱합을 최소화하는 방향으로 군집 형성되는 탐욕적 알고리즘

• (장점) 단순, 빠름, 多 데이터 처리 가능, 사전 정보 없이 의미 있는 자료구조 생성 가능, 다양한 데이터
• (단점) 초기 군집 수 결정에 어려움, 잡음/이상값 영향, 결과 해석 어려움, 군집 수, 가중치와 거리 정의가 어려움
  → 이상값 극복하는 방법: k-median, PAM(Partitioning Around Medoids)

*혼합 분포 군집

– 모형 기반의 군집 방법 (정규분포 or 다변량 정규분포를 가정), k개의 모형은 군집을 의미
– 모수와 함께 가중치를 자료로부터 추정하는 방법 사용 → EM 알고리즘

*EM알고리즘 (Expectation Maximization)

– 각 자료에 대해 z의 조건부분포로부터 조건부 기댓값을 구할 수 있음
– (x, z)에 대한 로그-가능도 함수에 z의 조건부 기댓값을 대입하면 로그-기능도 함수를 최대로 하는 모수를 쉽게 찾을 수 있다

• E-단계: 잠재변수 z의 기대치 계산
• M-단계: 잠재변수 z의 기대치를 이용하여 파라미터 추정
  → 확률분포 도입, 이상치 자료에 민감하므로 사전에 조치가 필요함

*SOM(Self Organizing Map) – 자기조직화 지도, 코호넨 맵

– 비지도 신경망, 고차원 데이터를 이해하기 쉬운 저차원 뉴런으로 정렬 → 지도로 형상화 → 패턴발견, 이미지분석 good

→ 경쟁학습, 각 뉴런이 입력 벡터와 얼마나 가까운지 계산, 연결 강도를 반복적으로 재조정
이 과정을 거치면서 연결강도는 입력패턴과 가장 유사한 경쟁층 뉴런이 승자 BMU(Best Matching Unit)

 

*최신 군집분석 기법– K-means, Hierarchical 클러스터링

 

*재표본 추출

• k-fold cross validation: K-1 학습, 1 테스트 → 반복, MSE 평균
• 붓스트랩: 단순 랜덤 복원추출법
• 홀드아웃 방법

*밀도기반 군집분석

• DBSCAN(Density-based Spatial Clustering of Application with Noise) → 군집화 + noise
  → 밀도 한계점에 따라 군집 형성
• OPTICS: 부가적 순서 생성
• DENCLUE(DENsity-based CLUSTEring): 밀도 분포함수에 기초

*격자기반 군집분석

– 데이터가 존재하는 공간을 격자구조로 이루어진 유한 개의 셀들로 양자화한 뒤, 데이터 포인트 대신 셀을 이용해 군집화과정을 수행하는 기법, 빠름

• STING(Statistical Information Grid): 격자 셀에 있는 통계 정보를 탐색
• Wave Cluster: Wavelet 변환 기법을 사용하여 객체들을 군집화
• CLIQUE(Clustering in QUEst): 고차원 데이터 공간의 군집화를 위한 격자 밀도 기반

*군집분석의 타당성 지표

• Silhouette(실루엣): 군집 내의 응집도(↓)와 군집 간 분리도(↑)를 이용한 지표 → 전체값 ↑

*a는 응집도, b는 분리도
→ 완벽한 군집화인 경우 1, 군집화가 전혀 이루어지지 않은 경우 -1

• Dunn Index: 군집 간 거리 최소를 분자, 군집 내 거리 최대를 분모로 → 클수록 군집이 잘된 것
  → 분자값 클수록 군집 간 거리↑, 부모값 작을수록 군집 내 요소 모여있음??

→ 최소값은 0에 가깝고, 최대값은 가능한 큰 값을 가지는 것이 이상적