Clustering이란?

클러스터링이란

• 범주 구조를 생성하는 통계적 기법입니다.
• 동일 그룹에 속하는 개체들은 결속력이 강하고, 다른 그룹에 속하는 개체들은 결속력이 약합니다.
• classfication과 차이점 : 클러스터 그룹이 알려져 있지 않습니다.

클러스터링 기법의 분류

• 분류하기전, 각 문서들에 대해 matrix 연산을 진행해야 합니다.
• 계층적 구조와 비계층적 구조로 나뉠 수 있습니다.
• 응집 vs 분할 방식으로 나눌 수 있습니다.
• Distribution-based(분포 기반) vs density-based(밀집 기반)
  • cluster의 분포를 중요시 한다면 각 cluster들의 크기가 일정합니다.
  • cluster의 밀집도를 중요시 한다면 DBSCAN과 같은 방식을 사용할 수 있습니다. 이러한 방식은 불규칙을 처리가능 하며, Noise와 outlier가 많을 때 비교적 사용 가능합니다.

Clustering 방법

• N object를 M groups으로 바꿉니다.
• Agglomerative(응집) vs Divisive(분할)
  • 응집 : unclustered data set -> N-1 pairwise joins 진행
  • 분할 : 하나의 single cluster안에 있는 모든 object가 존재 -> N-1 division 진행

계층적 클러스터링 알고리즘

• HACM(Hierarchical Agglomerative Clustering method)이라고 불리며 연결기반 클러스터링 알고리즘입니다.
• 해당 클러스터 구조는 Dendrogram형식을 띕니다.
• SLINK, CLINK, Group Average Link, Ward'method 등이 존재합니다.

1. SLINK (Single Linkage):
   • SLINK는 가장 가까운 이웃 간의 거리를 클러스터 간 거리로 사용하는 방법입니다.
   • 이 방법은 단일 연결법이라고도 불립니다.
   • SLINK는 클러스터의 크기가 크거나 이상치(outlier)가 있는 경우에 민감할 수 있습니다.
   • 길쭉한 형태의 클러스터가 생성됨
2. CLINK (Complete Linkage):
   • CLINK는 가장 먼 이웃 간의 거리를 클러스터 간 거리로 사용하는 방법입니다.
   • 두 클러스터에서 가장 먼 데이터 포인트 사이의 거리를 클러스터 간 거리로 측정합니다.
   • 이 방법은 완전 연결법이라고도 불립니다.
   • CLINK는 이상치에 대해 상대적으로 덜 민감하며, 클러스터 내의 다양성을 보존하는 경향이 있습니다.
3. GA Link (Group Average Link):
   • 그룹 평균 연결법(Group Average Linkage)은 두 클러스터 내의 모든 데이터 포인트 쌍의 평균 거리를 사용하여 클러스터 간 거리를 측정합니다.
   • 모든 데이터 포인트 사이의 거리를 고려하여 클러스터 간의 거리를 계산합니다.
   • 이 방법은 SLINK와 CLINK의 중간 정도로 간주되며, 일반적으로 이상치에 대해 상대적으로 덜 민감합니다.
4. Ward's method:
   • Ward의 방법은 클러스터를 합치면서 클러스터 내 분산 증가를 최소화하는 방향으로 클러스터를 형성합니다. 이때 중심점 사이의 계산은 유클리안 distance를 기반으로 함.
   • 각 클러스터를 합치면서 총 제곱 오차(Sum of Squares Error, SSE)를 최소화하는 방향으로 클러스터 간 거리를 정의합니다.
   • 동질적인 클러스터와 대칭적인 계층 구조를 생성하는 경향이 있습니다
   • 클러스터 무게중심에 대한 정의는 클러스터를 나타내는 유용한 방법을 제공합니다

비계층적 클러스터링 알고리즘

• 자료 집합이 N이 클러스터 M보다 매운 큰 자료 집합을 분할하는데 계층적 방법보다 효율적임
• 계산자원에 한계가 있었던 초기의 클러스터링 연구에 사용함
• 단일 패스
  • 단일패스 알고리즘은 데이터를 한 번만 스캔하여 클러스터를 형성합니다.
  • 일반적으로 알고리즘은 데이터 포인트를 하나씩 순서대로 처리하면서, 각 데이터 포인트를 기존 클러스터에 할당하거나 새로운 클러스터를 만듭니다.
  • 각 데이터 포인트와 클러스터 간의 거리나 유사성을 기준으로 클러스터링을 수행합니다
• 재배치
  • 재배치 알고리즘은 초기 클러스터를 임의로 생성한 후, 데이터 포인트를 다시 할당하여 클러스터의 중심 또는 경계를 조정하는 방식으로 클러스터를 개선합니다.
  • 주로 k-means와 같은 알고리즘이 재배치 알고리즘의 대표적인 예입니다.
  • k-means algorithm
    • 클러스터 개수 k가 주어졌을 때 각 클러스터들에 대한 전체 분산을 총합v를 최소화하는 s을 찾는 기계학습 알고리즘
• 유사도 측정 방법
  • Dice coefficient
  • Jaccard coefficient
  • Cosine coefficient
• 문서 클러스터링 방법
  • 문서들을 벡터화하여 유사한 문서끼리 클러스터를 이루게 하는것이 문서 클러스터링이다.
    각 문서들을 벡터화(document-term matrix) 합니다
    tf-idf를 이용하여 유사도를 비교해서 유사도가 큰 문서끼리 클러스터를 생성
    비교 및 평가를 하면서 바꾼다.