데이터 군집분석 및 클러스터링

군집분석이란?

---

• 우리가 레코드에 포함된 변수들에 기초해서 유사한 레코드를 가진 그룹 또는 군집들을 만들고자 하는 사용되는 클러스터링 분석
• 분석의 목적에 맞도록 군집들을 찾아내서 이들의 특징들을 연결하는 것
• 사용처 : 천문학, 교육학, 생물학자들이 특정한 종에 대해 분류하고자 할 때, 상위/하위 집단을 광범위하게 사용한다.
• • 마케팅에서 시장을 세분화하기 위해..
  • 인구 통계
  • 시장 세분화 전략 수립
• 그룹의 개체가 서로의 유사한 부분을 가지고 있는 것들을 찾아낸다.

• 내가 가질 수 있는 최소한의 거리를 값들을 찾는다.

• 최근에 빅데이터라는 부분에서 사용되고 있다.

• • 어떤 사용자의 질의에 의해서 만들어진다. 질의에 의해서 나타내는데 여러개의 질의 군을 나타내서 사용할 수 있다.
  • 검색 알고리즘의 성능을 향상시키는데 사용할 수 있다.

클러스터링 분석이 아닌것은?

• 감독 구분
• • 클래스 레이블 정보 보유
• 단순 분할
• • 학생을 성별로 알파벳 순으로 다른 최종 등록 그룹으로 나눈다.
• 쿼리 결과
• • 그룹화는 외부 사양의 결과이다
• 그래프 분할
• • 상호 관련성 및 시너지 효과도 있지만 영역이 동일하지 않음

클러스터의 개념은 모호할 수 있습니다.

• 클러스터 간의 간격은 작아야하고, A와 B와 C가 있다하면 각각의 그룹은 멀어야 한다.
• 클러스터링을 하게되기 위해서는 첫번째로 객체 집합의 군집을 집합으로 만드는 방법
• 1. 그룹 지정하는 방식을 만든다.
• 1. 군집하는 종류
• 같은 그룹에 속해있으면 유사성이 높다고 말한다.
• 차이가 넓다하면 객체간의 뚜렷한 차이점이 나타난다고 할 수 있다.

• 위 사진은 두개의 그룹으로 나타낸다.

• 점들의 모양에 군집들을 표현할 수 있는 방법

클러스터링 타입

• 클러스터링은 클러스터들의 집합이다.

• 클러스터의 계층 집합과 파티션 집합 간의 중요한 구별

• 파티션 클러스터링(분할 군집화)

• • 데이터 개체를 겹치치 않는 부분 집합(클러스터)로 분할하여 각 데이터 개체가 정확히 하나의 부분 집합 안에 있도록 함
  • 데이터의 중복이 없는 부분집합
• 계층적 클러스터링(계층 군집화)

• • 계층 트리로 구성된 중첩 클러스터 집합
  • 계층적 = 부분적인 방법
  • 다른 계층에서 병합하거나 분할하는 방법도 있다.
  • 병합은 n개가 있으면 n개의 군집이 1개가 남을 때까지 p2, p3를 합쳐서 p라고 하는 것을 p4와 합쳐서 pj로 만나고 p1과 만나서 대문자 P라고 나타낼 수 있다.

베타적 vs 베타적이지 않은

• 베타적이지 않은 클러스터링 안에서 점들은 많은 클러스터에 소속될 수도 있다.
• 많은 클래스들 또는 선 점으로 대신될 수 있다.

Fuzzy versus non-fuzzy

• 퍼지 군집화는 수학적인 관점에서 모든 집합에 대해 0과 1사이에 소속되어 있는 것들
• weight 합은 1이어야 한다.

Partial versus complete

• 경우에 따라 일부 데이터만 클러스터링한다.

이종 vs 동종

• 크기, 모양 및 밀도가 매우 다른 클러스터

군집의 종류

• 잘 구분된 클러스터

• • 군집은 군집의 어떤 점들이 군집에 없는 어떤 점들보다 군집의 다른 모든점들과 더 가깝거나 더 비슷하도록 만든 점들의 집합
• 중앙 기반 클러스터 : 중심점을 갖고 있는 평균값

• • 클러스터는 객체들의 집합이다. 클러스터 안에 있는 객체는 클러스터의 중앙에 가깝다. 어떤 다른 클러스터의 중앙에 보다
• • 클러스터의 중앙은 종종 중심부이거나, 클러스터 안에 있는 모든 점들의 평균이거나 매개체이다. 대부분 대표적인 클러스터의 점이다.
• 근접기반 클러스터

• • 내가 가질 수 있는 점에서 얼마나 우리가 나타낼 수 있는지.
• 밀도 기반 클러스터

• • 우리가 가지고 있는 전체에서 얼마나 모여있는지
• • 높은 밀도를 갖는다.
  • 높은 밀도를 갖는 각각의 값을 표현한다.
  • 목적 함수에 의해 어떤 값들을 갖고 있다
• 재산이나 개념

• 목적 함수

• • 목표 함수를 최소화하거나 최대화해서 클러스터링 해야한다. 분리해서 나타내거나 중심점들의 값들을 나타내거나 또는 평균을 나타내거나 해서 처리를 하는데. 클러스터링 할때 전체 군집들을 나눌 수 있게 가능한 모든 방법들을 열거한 다음에 함수를 사용하는데 이때 사용하는게 목적함수이다.
  • 목적 함수는 어떤 목적을 갖고 있거나 계층을 갖고 있다.
  • 클러스터링을 하기 위해서는 필요한 것은 목적이다. 이 목적에서 가질 수 있는 것은 공유할 수 있는 값들이 들어갈 수 있다. 공유객체에 집합으로 표현할 수 있다. 아니면 우리가 병합을 하거나 join해서 사용할 수 있다.
  • 주로 군집들이 불규칙하거나 얽힌 경우에 잡음과 이상치가 있는 경우에 밀도 군집들을 사용할 수 있다.
  • 모든 객체들 간에 동일한 평균에 가까운 것들을 사용한다.
  • 복잡하거나 패턴이 여러개로 넘어갈 경우 복잡하다고 얘기하는데, 거기에서 사용하는 것들을 찾아내야 한다.

군집간에는 최소화하고 군집내에서는 엣지를 최대화한다.

클러스터링 알고리즘

---

• 전체 사용자에서 사용자가 지정한 갯수의 군집들 (K)를 찾기 위한 것 = K-manes and its variants
• Hierarchical clustering = 병합/분할 => 트리구조 => 계층적 클러스터링 = 그래프 기반
• Density-based clustering = 밀집도기반 클러스터링 = 저밀도에서는 잡음으로 처리한다. 고밀도에서는 한쪽으로 많이 표현한다.

K-means 클러스터링

• 분할 클러스터링 접근
• 각 클러스터링은 중앙에 위치해있다.
• 각 점은 가장가까운 중앙 클러스터에 지정된다.
• 각각의 점은 가장 가까운 중심적으로 나타난다.

K-means 클러스터링 알고리즘

Two different K-means Clusterings

1. 초기의 중심점(전체값)
2. 갱신 중심점 할당

위 과정을 중심점이 바뀌지않을 때까지 무한 반복

1. 분할 되었다.

K-means 클러스터를 평가하는 것

• 클러스터의 수 k를 늘리는 것

군집의 이상 초기값 해결법

• 다중 실행
• 계층 군집을 사용해서 초기 이상값을 해결
• 군집을 나눠서 사용한다.
• 새로운 군집의 중심점을 넣는다
• 두 군집을 병합한다.
• 군집을 나눌 경우 가장 군집이 큰 것을 찾아서 사용하는 방법, 멀리 떨어져 있는 점 선택, 다른 중심점을 선택하는 방법

빈 클러스터들을 다루는 법

• 기본 k-means 알고리즘은 빈 클러스터들을 산출할 수 있다.

• 여러 전략들

• • SSE 방법 (오차 제곱 합)

  • 가장 높은 SSE 클러스터로부터 점을 선택한다.
  • 만약 빈 여러개의 클러스터가 있다면 여러 시간을 반복될 수 있다.

점진적으로 센터를 업데이팅 하는 것

• 기본 k-means 알고리즘에서 중심점은 업데이트 된다. 모든 점들이 중앙에 배정된 후에
• 대안은 중심점을 업데이트 하는 것이다. 각각 지정된 후에
• • 각 위치는 0 또는 2 중심점으로 업데이트 된다.
  • 보다 비싸다
  • 순서 의존성을 소개한다.
  • 더이상 빈 클러스터를 가지지 않는다
  • “가중치”를 사용하여 영향 변화 가능

전처리 (Pre-processing)

• 데이터를 일반화한다.
• 특이치를 제거한다.

후처리 (Post-processing)

• 특이치를 나타낼 수 있는 작은 군집 제거

• SSE가 상대적으로 높은 군집, 즉 분할 ‘느슨한’ 군집

• SSE가 상대적으로 낮은 ‘접근’ 클러스터 병합

• 클러스터링 프로세스 중에 이 단계를 사용할 수 있습니다.

• • ISODATA

  이등분 K-means (Bisecting K-means)

  • K-means의 변수는 부분적 또는 계층적 클러스터링을 만들 수 있다.

  

K 평균의 한계 (Limitations of K-means)

• 사이즈가 다르거나
• 밀도가 다르거나
• 그래프 모양이 틀리거나
• 특이치가 포함되어 있으면 특정 문제가 있다고 말한다.

div >= 0 양질의 성질

did = 0 근사성

dij = dii 대칭성

dij <= dii+dik 삼각형에 가까운 점