군집 알고리즘

 

 

• 이번 강사님의 오티를 듣는데 체계적이고 실습도 많을 것 같아서 재밌어보인다는 생각이 들었다
• 기대가 되는구만
• 그리고 어제부터 조대협의 대항로 1기를 5주간 진행하게 되었는데 다들 15년차 급의 시니어들에다가 사업하시는 분들도 있고... 20대에 신입은 나 밖에 없는 것 같다;;
• 팀을 구성해서 프로젝트를 진행해야 하는데 조금 부담쓰~
• 근데 머 일단 해보자. 설마 죽기야 하겄어?

 

 

 

 

---

 

 

 

 

 

1. 군집 알고리즘의 개념 및 활용

• 군집 알고리즘이란 주어진 데이터에서 구조와 패턴을 찾아서 유사한 개체를 그룹화하는 군집 분석에 쓰이는 알고리즘이다

• 그럼 군집 알고리즘을 통해서 무엇을 할 수 있을까?
• 이전에 했었던 분류랑 다르게 군집 분석은 비지도 학습이다. 군집 분석을 활용하면 기존에 알고 있던 기준이 아니라 새로운 관점에서 그 데이터 자체만을 가지고 구분짓고 싶을 때 사용할 수 있다
• 군집 분석을 통해 고객의 특성을 분류한다거나, 지역을 도 • 시 • 군 이런 식이 아니라 새로운 기준으로 분류할 수 있다

• 군집 분석 사용 예시
  
  1. 머신 러닝 과정에서 학습 데이터의 구조적 이해
  2. 새로운 데이터의 분류
  3. 비정상적인 행위 탐지
     : 알려진 군집 이외에 속하는 사용 패턴을 식별하여 비인가된 침입으로 판별
  4. 대량 데이터셋을 소수의 균일한 범주로 단순화
     : 인스타그램, 페이스북 등 SNS에서 유사한 행동을 보이는 사람들을 그룹화하여 마케팅 전략을 세울 수 있음
• 군집 분석의 유형으로는 두가지가 있다
  1. 하드 클러스터링 : 각 개체가 하나의 군집에만 속함
  2. 소프트 클러스터링 : 각 개체가 하나 이상의 군집에 속할 수 있음
• 그렇다면 그룹화할 때 무엇을 기준으로 해야할까? 각 개체들의 거리 기반
• 각 데이터들간의 거리가 가까우면 유사성이 높고, 멀면 유사성이 낮다고 판단한다
• 거리 측정에는 유클리디안 거리 또는 맨헤튼 거리 측정 기법을 사용한다
• 각 데이터끼리의 거리 측정은 유클리디안 이런 걸 쓰는건 알겠는데 클러스터끼리의 거리 측정은 어떻게...?

거리 측정	설명
최단 연결법 (단일 연결법)	각 클러스터에서 가장 가까운 요소를 뽑아 연결한 거리로 군집 간 거리를 측정 (최근접 이웃 방법)
최장 연결법 (완전 연결법)	각 클러스터에서 한 점을 뽑아 연결할 수 있는 가장 최장 거리를 군집 거리로 판단 (가장 먼 이웃 방법)
중심 연결법	두 군집 중심 간의 거리를 군집 간 거리로 판단
평균 연결법	첫 번째 군집의 각 구성원과 두 번째 군집의 각 구성원 사이의 거리를 평균하여 계산 (군집의 모든 관측치 간의 거리 평균을 최소화)
와드 연결법 (Ward)	모든 군집 내에서 차이 제곱의 합을 최소화 (분산 최소화 접근 방식)

• 같은 데이터라도 클러스터 간의 거리를 어떻게 측정했냐에 따라 결과가 달라질 수 있다

• 군집 알고리즘에는 다양한 알고리즘이 있으며 각 알고리즘마다 결과가 달라질 수 있다

https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparsion.html#sphx-glr-auto-examples-clulster-plot-cluster-comparison-py

2. 계층적 군집 알고리즘

• 군집 알고리즘 중 하나이다
• 상향식 또는 하향식 접근 방식이 있다

• 계층적 군집 분석에는 거리 행렬을 사용하여 그룹화할 수 있다. 여기서는 최단 거리를 기준으로 분류하였다

• 계층적 군집 알고리즘에서 위에 트리처럼 표현하는 것을 덴드로그램이라고 한다

• 덴드로그램을 사용해서 군집을 몇개로 나눌 것인지 정할 수 있다

• 계층적 군집 알고리즘은 데이터 수가 적을 때 사용하면 적합하다
• 반대로 데이터의 수가 많을 때에는 적합하지 않다

3. K-Means, K-Medoids

• K는 하이퍼 파라미터이다. 몇개의 그룹으로 나눌 것인지를 정하는 것이다
• 클러스터를 대표하는 대푯값으로는 크게 3가지가 있다

대푯값	설명
Centroids (중심점)	- 클러스터의 중간에 있는 점 - 데이터 세트의 실제 점이 아닐 수 있음
Medoids (중앙점)	- 클러스터 중앙에 위치한 실제 지점 - 데이터 세트의 실제 점임
Representative Points (대표점)	- 군집을 대표하는 군집 주변의 점 - 원형이 아닌 클러스터의 경우 중심점 또는 중앙점을 사용하는 것보다 더 분명하게 표현할 수 있음

3-1. K-Means

• 처음에 임의의 두점(서로 멀어야 어느 정도 그룹화를 잘 할 수 있음)을 정하고 그 점들을 기준으로 그룹화 시작
• 군집에서 객체들의 평균값을 취해서 중심점을 기준으로 사용하기 때문에 중심점이 실제 데이터가 아닐 수 있음
• 계속 반복하여 중심점이 바뀌지 않을 때 종료 (물론 계속 바뀌는 경우가 있을 수 있음. 그래서 이 때는 최대 횟수를 정해주거나 K 값을 잘 설정해주어야 함. 최적의 K를 구하는 기준을 밑에 따로 설명, 보통 K는 2~5 사이의 작은 정수로 설정)

3-2. K-Medoids

• 중심에서 가장 가까운 객체를 기준으로 클러스터 사이의 거리를 측정하여 그룹화를 진행
• 실제 데이터를 기준으로 계속 사용
• K-Means에 비해 이상치(기존 범주에 벗어나 유독 값이 작거나 큰 데이터)에 덜 민감하다

왼쪽이 K-means, 오른쪽이 K-Medodis

• K-Medoids 군집 생성 과정

3-3. 최적의 K를 구하는 방법

• 사실 최적의 K를 구하는 방법은 없다
• K 값을 다양하게 설정하고, 각 K 값에 대한 목적함수를 계산하여 K의 값을 결정해야 한다
• 목적 함수란 클러스터의 중심에서 각 점까지의 거리의 제곱의 합을 의미한다

• K 값에 따른 목적함수를 보면 일정 K 값 이상부터는 목적함수의 변화가 미미해진다
• 그 K 값을 사용하며 된다

4. 군집 알고리즘 평가 방법

• 클러스터 내 객체들의 유사성이 높고, 클러스터 간의 유사성이 낮으면 좋은 알고리즘이라고 할 수 있다
• 그럼 어떤게 좋은 좋은 군집 알고리즘인지 판단하는 기준은 무엇일까?
• 판단 기준은 목적 변수가 있느냐, 없느냐로 구분할 수 있다

4-1. 목적 변수가 있는 경우

• 군집의 실제값이 존재하므로 좀 더 정확한 평가를 할 수 있음

1. Homogeneity
   • 각 군집들이 각 범주의 데이터만 포함하는지 여부 (빨간 공 주머니 안에 빨간 공의 비율이 몇인지)
   • 0.0~1.0 (1.0에 가까울 수록 좋은 성능
2. Completeness
   • 주어진 범주의 모든 데이터가 같은 군집 내에 있는지 여부 (빨간 공 주머니 안에 다른 색이 더 들어있어도 상관 없고 일단 내가 갖고 있는 빨간 공들이 모두 들어있는지)
3. V-Measure
   • Homegeneity와 Completeness의 조화 평균(역수의 평균값을 다시 역수를 취한 값)

• 최적의 K값을 구할 때처럼 일정 클러스터의 갯수 이상부터는 변화가 미미해지고 저 지점에서 최적의 성능을 보여준다고 판단할 수 있다

4-2. 목적 변수가 없는 경우

• 실루엣 분석(Silhouette analysis)을 진행한다
•  각 군집 간의 거리가 얼마나 효율적으로 분리되어 있는지 나타냄
• 실루엣 계수
  • 해당 데이터가 같은 군집 내의 데이터와 얼마나 가깝게 군집화 되어 있고, 다른 군집에 있는 데이터와는 얼마나 멀리 분리되어 있는지 나타내는 지표
  • 실루엣 계수의 평균값은 0~1 사이, 1에 가까울 수록 좋음
• 전체 실루엣 계수의 평균값과 더불어 개별 군집의 평균값의 편차가 크지 않아야 함

• 하지만 평균 실루엣 점수가 낮다고 좋은건 아님
• 실제 결과값을 보고 내가 어떻게 나누면 좋을지에 대한 고민을 해보고 결정해야 함

 

 

 

 

 

---