[Clustering] 2

K-Medoids 클러스터링

K-Medoids 클러스터링은 데이터를 여러 개의 군집으로 나누는 비지도 학습 알고리즘 중 하나입니다. K-Means와 유사하지만, 군집의 중심(centroid) 대신 실제 데이터 포인트(메도이드, medoid)를 사용한다는 점에서 차이가 있습니다. K-Medoids는 특히 이상치(outlier)에 덜 민감하여 보다 안정적인 군집화를 제공하는 특징이 있습니다. 

 

1. 임의로 k개의 개체를 초기 메도이드로 선택

• 설명: 처음에 k개의 메도이드(중심 포인트)를 선택해야 합니다. 이는 K-Medoids 알고리즘에서 군집의 중심 역할을 하는 포인트입니다.
• 방법: 데이터셋에서 임의로 k개의 데이터를 선택합니다. 이 데이터들은 초기 메도이드가 됩니다.
• 주의사항: 메도이드는 실제 데이터 포인트여야 하며, 임의로 선택되므로 초기화에 따라 결과가 달라질 수 있습니다.

2. 나머지 각 개체를 가장 가까운 메도이드에 할당

• 설명: 각 데이터 포인트를 가장 가까운 메도이드에 할당합니다. 이를 통해 각 메도이드 주위에 군집이 형성됩니다.
• 거리 측정 방법: 거리 측정은 보통 유클리드 거리(Euclidean distance)나 맨하탄 거리(Manhattan distance) 등을 사용
• 할당 과정: 각 데이터 포인트는 자신과 가장 가까운 메도이드로 할당되어 해당 군집의 일원이 됩니다.

3. 임의로 비메도이드 개체 선택

• 설명: 현재 메도이드가 아닌 데이터 포인트 중 하나를 임의로 선택합니다. 이 포인트는 잠재적으로 메도이드가 될 수 있습니다.
• 선택 이유: 기존 메도이드를 대체하여 군집의 품질을 향상시킬 가능성이 있는지 확인하기 위해서입니다.
• 방법: 임의로 비메도이드 개체를 선택합니다. 이때 비메도이드 개체는 기존의 메도이드 포인트를 제외한 데이터 중 하나입니다.

4. 총 스왑 비용 계산

• 설명: 선택한 비메도이드 포인트를 새로운 메도이드로 바꿀 경우, 군집화의 품질이 어떻게 변화하는지 평가합니다.
• 계산 과정:
  • 기존 메도이드와 임의로 선택된 비메도이드 포인트를 교체합니다.
  • 이 교체로 인해 발생하는 총 비용 변화를 계산합니다. 비용은 군집 내 모든 데이터 포인트와 메도이드 간의 거리 합계로 측정됩니다.
  • 스왑 후의 총 비용이 기존보다 낮으면 군집화의 품질이 향상된 것으로 간주됩니다.

5. 품질이 향상되면 O와 Orandom If를 교환

• 설명: 만약 교체로 인해 군집화의 품질이 개선된다면, 기존 메도이드를 새로운 비메도이드 포인트로 교체합니다.
• 조건: 새로운 메도이드가 될 포인트와 기존 메도이드 간의 총 거리 비용이 감소해야 합니다.
• 결과: 군집화 품질이 향상되었다면, 메도이드 교체가 이루어지고 해당 군집에 속하는 데이터 포인트들이 업데이트됩니다.
• 반복
• 설명: 위 과정을 반복하여 군집화가 더 이상 개선되지 않을 때까지, 또는 일정 반복 횟수에 도달할 때까지 지속합니다.
• 종료 조건: 메도이드가 더 이상 변하지 않거나 총 비용이 크게 감소하지 않으면 알고리즘이 종료됩니다.

요약

K-Medoids 알고리즘은 K-Means와 유사하지만 실제 데이터 포인트를 중심으로 사용하여 이상치에 더 강건합니다. 각 단계에서 메도이드와 비메도이드를 교환하면서 군집의 품질을 점진적으로 향상시키는 방식으로 작동합니다.

k-means 대 k-Medoids

• 예제
• 어느 것이 더 낫습니까?
• https://en.wikipedia.org/wiki/K-medoids

계층적 클러스터링

• 거리 행렬을 군집화 기준으로 사용
• 이 방법은 입력으로 클러스터 수 k가 필요하지 않지만 종료 조건이 필요

AGNES(집적 네스팅)

• Kaufmann and Rousseouw (1990)에 소개됨
• 단일 링크 방법과 비유사성 행렬을 사용
• 차이점이 가장 적은 노드를 병합
• 하강하지 않는 방식으로 진행
• 결국 모든 노드는 동일한 클러스터에 속함

예: 응집 클러스터링

• 덴드로그램
• 데이터 개체를 덴드로그램(dendrogram)이라고 하는 여러 수준의 중첩 분할(클러스터 트리)로 분해
• 데이터 개체의 클러스터링은 덴드로그램을 원하는 수준으로 절단하여 얻은 후 연결된 각 구성 요소가 클러스터를 형성

클러스터 간 거리

• 계층적 클러스터링에서는 클러스터 간의 거리를 정의해야 함
• 단일 링크
  • 한 클러스터의 요소와 다른 클러스터의 요소 사이의 최소 거리
• 완전 링크
  • 한 클러스터의 요소와 다른 클러스터의 요소 사이의 가장 큰 거리

클러스터 간 거리

• 평균
  • 한 군집에 있는 원소와 다른 군집에 있는 원소 사이의 평균 거리
• 구심점
  • 두 군집의 중심점 사이의 거리

밀도 기반 접근법

• 파티셔닝 및 계층적 접근의 문제점
  • 클러스터링의 모양은 구형
  • 임의 모양의 클러스터를 찾기 어렵다

DBScan: 밀도 기반 클러스터링

• 2개의 파라미터
  • � : 인근 최대 반경
  • ���DEF: 점의 �-근접에서 최소 점 수 �G � : � ∈ � ���� �, � ≤ �}
• 직접 밀도 도달 가능: 점 q에서 점 p가 직접 밀도 도달 가능 
  • p는 � HDF �에 속함
  • 핵심 포인트 조건 : |�G � ≥ ��� DEF

DBScan: 밀도 기반 클러스터링

• 강점
  • 클러스터 수를 결정할 필요가 없다
  • 임의 형상의 군집 찾기
  • 노이즈 객체, 즉 이상치 제거
• 약점
  • 완전히 결정론적이지는 않다
  • 하나 이상의 클러스터에서 도달할 수 있는 경계 지점은 처리 순서에 따라 두 클러스터 중 하나에 속할 수 있다.
  • 고차원 데이터에서는 잘 작동하지 않음
• 예제
  • https://www.youtube.com/watch?v=Gu9RvzsjxJg