clustering

data mining
공개

2025년 6월 14일

전제 조건

  1. scalability
  2. 다양한 타입의 속성을 처리해야 함
    • k-means는 수치형만 처리 가능
  3. 인위적인 형상의 군집도 발견할 수 있어야 함
    • k-means는 non-convex 형태는 잘 못찾음
  4. 파라미터 설정에 전문지식을 요하지 않아야함
  5. noise와 outliers를 처리해야 함
  6. 데이터가 입력되는 순서에 민감하면 안됨
  7. 차원 수가 높아도 잘 처리할 수 있어야함
  8. 사용자 정의 제약조건도 수용할 수 있어야함
  9. 해석과 사용이 용이해야함

전처리

  1. scaling 필요
  2. one hot encoding

model

  • Distance-based methods
    • Partitioning methods
      • k-means1:
        • polinominal 시간 안에 해결 가능
        • noise, outlier에 민감함
        • 수치형만 처리 가능
        • non-convex 형태는 잘 못찾음
      • k-modes: 범주형 데이터 처리 가능. 빈도수로 유사도 처리함
      • k-prototype: 범주형, 수치형 섞인거 처리 가능
      • k-medoids: 중심에 위치한 데이터 포인트를 사용해서 outlier 잘 처리함
        • PAM: Partitioning Around Medoids
          • scalability 문제 있음
        • CLARA: sampling을 통해서 PAM의 scalability 문제를 해결
          • 샘플링 과정에서 biased될 수 있음
        • CLARANS: medoid 후보를 랜덤하게 선택함
      • k-means++: 초기 centroids를 더 잘 잡음
    • Hierarchical methods
      • top-down: divisive, dia
      • bottom-up: agglomerative
        • ward’s distance: 군집 간의 거리 계산을 군집 내의 분산을 최소화하는 방식으로 계산
          • ESS: 각 군집의 중심으로 부터의 거리 제곱합
  • Density-based methods
    • 다양한 모양의 군집을 찾을 수 있음
    • noise, outlier에 강함
    • DBSCAN: 잡음 포인트는 군집에서 제외
      1. core point를 찾음(eps 이내에 minPts 이상 있는 점)
      2. core point를 중심으로 군집을 확장
        • core point가 아닌 경우 확장 종료
      • 고정된 파라미터를 사용하기 때문에 군집간 밀도가 다를 경우 잘 못찾음
      • 군집간 계층관계를 인식하기 어렵다
    • OPTICS: DBSCAN의 단점을 보완
      • 군집의 밀도가 다를 때도 잘 처리함
      • 군집의 계층 구조를 인식할 수 있음
      • eps, minPts 파라미터가 필요함
  • Grid-based methods: 대표만(각 grid를 대표) 가지고 군집분석 하는거
    • 속도와 메모리 측면에서 효율적
  • Model-based clustering methods
  • 거리기반 군집의 단점:
    • 군집의 모양이 구형이 아닐 경우 찾기 어려움
    • 군집의 갯수 결정하기 어려움
    • 군집의 밀도가 높아야함

평가

  • silhuette score: \(\frac{\sum_{i=1}^{n} s(i)}{n}\)
    • s(i): \(\frac{b(i) - a(i)}{max((a(i), b(i)))}\)
      • a(i): 군집 내 노드간의 평균 거리
      • b(i): 가장 가까운 군집과의 노드 간 평균 거리
    • 1에 가까울 수록 좋음
맨 위로

각주

  1. 장단점 기말고사 언급하심↩︎