[Clustering] 1

리뷰: 비지도 학습

• 데이터의 잠재적 의미 표현 찾기
  • 클러스터링: 데이터 내에서 유사한 예제의 그룹을 검색
    • 예: K-평균 클러스터링
  • 차원 축소: 고차원 공간에서 더 낮은 차원 공간으로 데이터를 투영
    • 예: 주성분분석(PCA)
  • 밀도 추정: 입력 공간 내의 데이터 분포를 결정
    • 예: 가우시안 혼합 모델(GMM)
  • 행렬 완성: 부분적으로 관찰된 행렬의 누락된 항목을 채움
    • 예: LRA(low-rank approximation)

클러스터 분석이란?

• 클러스터: 데이터 개체 모음
  • 동일한 그룹 내에서 서로 유사(또는 관련)함
  • 다른 그룹의 튜플과 유사하지 않음(또는 관련 없음)
• 클러스터 분석(또는 클러스터링, 데이터 세분화)
  • 데이터에 포함된 특성에 따른 데이터 간 유사성 정의
  • 유사한 데이터 튜플을 클러스터로 그룹화

좋은 클러스터링이란 무엇입니까?

• 좋은 클러스터링 방법은 고품질 클러스터를 생성
  • 클래스 내 유사성이 높음: 클러스터 내에서 응집력 있음
  • 클래스 간 유사성이 낮음: 클러스터 간에 구별됨 
• 클러스터링 방법의 품질은 주로 유사성 측도에 의존

예제: 군집 및 이상치

포인트에 적합한 클러스터링은 무엇입니까?

클러스터링 품질 측정

• 비유사성/유사성 메트릭
• 유사성은 거리 함수에 의해 정의: d(i,j)
• 거리 함수는 일반적으로 데이터 유형(간격 척도, 부울 변수 및 범주형 변수)에 따라 다름
• 가중치는 애플리케이션 및 데이터 의미론에 따라 다양한 변수와 연관되어야 함

클러스터 분석을 위한 고려사항

• 분할기준
  • 단일 레벨 대 계층적 파티션
  • 다단계 계층 분할이 바람직할 수 있다.
• 클러스터 분리
  • 독점: 하나의 튜플은 하나의 클러스터에만 속함
  • 비배타: 하나의 튜플이 하나 이상의 클러스터에 속할 수 있다.
• 유사도 측도
  • 거리 기반(예: Euclidian, 도로망, 벡터) 
  • 연결 기반(예: 밀도 또는 연속성)
• 클러스터링 공간
  • 전체 공간(저차원인 경우 종종)
  • 부분 공간(종종 고차원 클러스터링)

주요 클러스터링 접근 방식

• 파티셔닝 접근법
  • 클러스터를 구성하고 어떤 기준에 따라 클러스터를 평가
  • 제곱 오차의 합 최소화
  • 방법: k-means, k-medoid, CLARANS
• 계층적 접근
  • 어떤 기준을 사용하여 데이터 집합의 계층적 분해를 구축
  • 방법: 다이아나, 아그네스, 버치, 카메룬 주요 클러스터링 접근 방식
• 밀도 기반 접근법
  • 연결 및 밀도 함수를 사용
  • 방법: DBSCAN, Optics, DenClue
• 그리드 기반 접근법
  • 고차원 데이터에서 다단계 세분화를 사용
  • 방법: STING, WaveCluster, CLIKE

파티셔닝 접근법의 기본 개념

• 분할방법
• 집합 D의 n 튜플을 k개의 클러스터로 분할
• 거리 제곱의 합은 최소화됨(여기서 ci는 클러스터 Ci의 중심 또는 메도이드)

파티셔닝 접근 방식

• k가 주어지면 선택한 분할 기준을 최적화하는 k개의 클러스터 분할을 찾음
  • 전역 최적: 모든 파티션을 철저히 열거
  • 휴리스틱 방법: k-means와 k-medoid 알고리즘 
• k-means 
  • 각 클러스터는 클러스터의 중앙으로 표시
• k-medoids (medoids 주위의 파티션)
  • 각 클러스터는 클러스터의 개체 중 하나로 표시

k-평균 군집화

• 유클리드 공간/거리를 가정
• 클러스터 개수인 k를 선택하는 것으로 시작
• 클러스터당 한 점을 선택하여 클러스터를 초기화
  • 예: 임의로 한 점을 선택한 다음 k-1개의 다른 점을 선택. 각각은 이전 점에서 가능한 한 멀리 떨어져 있다.

군집 채우기

1) 각 점에 대해 현재 중심이 가장 가까운 클러스터에 배치

2) 모든 점이 할당된 후 k개의 클러스터의 중심 위치를 업데이트

3) 모든 점을 가장 가까운 중심에 다시 할당

• 클러스터 간에 점을 이동하는 경우가 있다.
• 수렴할 때까지 2와 3을 반복합니다.
  • 수렴: 점들이 군집들 사이에서 이동하지 않고 중심들이 안정화

예: 클러스터 할당

k 맞추기

k를 선택하는 방법?

k가 증가함에 따라 평균 중심까지의 거리 변화를 보면서 다른 k를 시도

평균은 오른쪽 k까지 빠르게 하락한 다음 거의 변화하지 않음

예: picking k

너무 적음;

중심까지의 먼 거리.

 

딱 좋습니다;

다소 짧은 거리.

 

너무 많음;

평균 거리가 거의 개선되지 않음

k-평균 군집화

• 힘
  • 효율성: O(tkn), 여기서 n은 #객체, k는 #클러스터, t는 #반복 ( 일반적으로 k,t ≪ n. )
  • 종종 로컬 최적으로 종료
• 약점
  • 클러스터 개수인 k를 미리 지정해야 함
  • 노이즈가 많은 데이터와 이상치에 민감

k-평균 군집화의 문제점

• k-평균 알고리즘은 특이치에 민감
  • 값이 매우 큰 물체는 데이터의 분포를 상당히 왜곡시킬 수 있으므로
• k-메도이드
  • https://en.wikipedia.org/wiki/K-medoids
  • 클러스터에 있는 개체의 평균값을 기준점으로 삼는 대신 메도이드를 사용할 수 있다.
  • Medoid: 클러스터에서 가장 중앙에 위치한 개체

k-Medoids 클러스터링

• 초기화: 메도이드로 k개의 객체를 임의로 선택(교체 없이)
• 각 데이터 포인트를 가장 가까운 메도이드에 연결
• 구성 비용이 감소하는 동안:
  • 각 메도이드에 대해 비메도이드 데이터 점 o
    • m과 o를 교환하고 비용(메도이드에 대한 점 거리의 합)을 다시 계산
    • 이전 단계에서 구성의 총 비용이 증가한 경우 스왑을 취소