비지도학습_군집화

개념

군집화?

-데이터 집합의 분포 특성을 분석하여 서로 교차하지 않는 복수 개의 부분집합(cluster)으로 나누는 문제

 입력 데이터로부터 추출된 특징 공간에서 특징 값의 유사성에 따라 비슷한 데이터들끼리 묶음

 

분류-데이터가 주어질때 클래스 레이블까지 주어진다, 지도학습 사용

군집화- 출력값 없이 데이터만 주어짐, 비지도 학습 사용

 

sample, 대표벡터, 확률분포 결과 표현 할수 있다.

 

군지화 표현 적용 방법론

k-평균 군집화 (K-means clustering), 계층적 군집화(hierarchical clustering)

가우시안 혼합( Gaussian mixture )모델, SOM (Self Organizing Feature Map)

 

군집화가 적용 가능한 데이터 

-데이터에 대한 클래스 레이블이 주어지지 않는 경우

-데이터에 대한 클래스 레이블링에 비용이 많이 드는 경우

 

k-평균 군집화

? 주어진 데이터 집합을 K개의 그룹으로 묶는 알고리즘

*K-NN (분류기) 와 K-평균 군집화 헷갈릴수 있음

-수행 단계 

시작(초기화) -> 데이터그룹핑->대표벡터수정->반복여부결정

대표벡터와 거리를 계산하여 그룹핑 후 대표벡터 수정 후 반복여부 결정

 

실제 문제에 적용할 떄 고려해야 할 사항

-대표 벡터 계산과 데이터 그룹핑 과정의 반복적인 수행을 통해 좋은 군집을 찾는 것이 확실히 보장되는가?

-초기 대표 벡터의 설정이 군집화의 성능에 미치는 영향은?

-데이터에 의존하는 적절한 k값을 어떻게 선택할 것 인가?

 

k-평균 군집화 알고리즘은 목적함수 J를 극소화하는 지역 극소점을 찾는 것을 보장

반복할 때마다 매개변수를 최소화 시키는 방향으로 학습이 진행되서 좋은 군집을 보장한다

 

초기에 임의로 결정하는 대표벡터에 따라 최종적으로 찾아지는 해가 달라짐

 

K값에 따른 변화

적절한 K값의 선정은 주어진 문제에 의존적

다양한 K값에 대해 군집화 결과들을 비교하여 선택?

계층적 군집화 알고리즘

 

계층적 군집화

? 전체 데이터를 몇개의 배타적인 그룹으로 나누는 대신, 큰 군집이 작은 군집을 포함하는 형태로 계층을 이루도록 군집화를 수행하여 그 구조를 살펴보는 방법

-병합적 방법

 각데이터가 하나의 군집을 이루는 최소 군집으로 시작하여 가까운 군집끼리 단계적으로 병합하여 더 큰 군집을 만들어 가는 과정

n-1번의 병합 과정이 필요 

-분할적 방법

모든 데이터가 하나의 군집에 속하는 최대 군집에서 시작하여 특정 기준에 따라 군집들을 분할해 가는 방법

가능한 분할 방법의 가지수 2n-1 -1개 > 비실용적 

 

dendrogram > 계층적인 군집화 결과를 보여주는 그림

 

군집간의 거리를 계산하는 방식

최단 연결법 > 가장 가까운 데이터 쌍 간의 거리/고립된 군집을 찾는 데 유용

최장 연결법 > 가장 멀리 떨어진 데이터 쌍 간의 거리/ 응집된 군집을 착는데 중점을 둠

중심 연결법 > 주 군집의 평균간의 거리 / 특이 값에 강건함

평균 연결법 > 모든 데이터 쌍 간 거리의 평균 / 작은 분산을 가지는 군집을 형성함

Ward's 방법 > 병합 후의 클러스터 내부의 분산 값 / 비슷한 크기의 군집을 병합함

dendrogram으로부터 적합한 군집의 수를 결정하는 방법

dendrogram에서 클러스터 간의 거리가 증가하는 동안 클러스터의 수가 늘어나지 않고 일정 기간 유지되는 지점을 선택

정리

1. 군집화의 개념
   - 군집화 → 데이터 집합의 분포 특성을 분석하여 서로 교차하지 않는 복수 개의 부분집합(군집)으로 나누는 문제 → 바람직한 출력값에 대한 정보가 없으므로 비지도학습을 수행 → 주요 방법: K-평균 군집화, 계층적 군집화, 신경망(SOM) 등 → 응용: 영상 데이터의 그룹핑, 영상분할 등
2.  K–평균 군집화
   - 데이터 집합을 K개의 그룹으로 묶는 알고리즘
   - 알고리즘의 수행 단계
   ① 시작 → 데이터 집합으로부터 임의로 K개의 벡터를 선택하여 K개의 초기 대표 벡터 집합을 생성함
   ② 데이터 그룹핑 → 각 데이터에 대해 K개의 대표 벡터들과의 거리를 계산한다. 만약 i번째 데이터가 j번째 대표 벡터에 가장 가깝다면 이 데이터를 클러스터 j에 속하도록 레이블링한다. 이 과정을 통해 데이터 집합을 K개의 클러스터로 나눔
   ③ 대표 벡터 수정 → 단계 ②에서 구한 새로운 클러스터에서 각각의 대표 벡터를 갱신함
   ④ 반복 여부 결정 → 수정 전의 대표 벡터와 수정 후의 대표 벡터의 차이를 계산하여 그 값에 변화가 없거나 설정된 반복 횟수에 도달할 때까지 단계 ②~④를 반복함
   - 실제 문제에 적용할 때 고려사항
   ① 좋은 군집을 찾는 것이 확실히 보장되는가? ⇒ 대표 벡터의 계산과 군집화 과정이 번갈아 반복할 때마다 목적함수의 값을 감소시켜서 지역 극소점을 찾는 것을 보장함
   ② 초기 대표 벡터의 설정이 군집화의 미치는 영향 ⇒ 초기에 임의로 결정한 초기값(대표 벡터)들을 잘 선택해 주는 것은 좋은 군집화 결과를 얻기 위해 매우 중요한 과정이며, 각 데이터 간의 거리가 어느 기준 이상 떨어진 것들을 후보로 선택하거나 전체 입력 범위를 균등 분할하여 선택하는 등의 방법을 사용함
   ③ 적절한 K값의 선정 ⇒ 적절한 값의 선정은 중요하지만, 이는 지극히 문제에 의존적임
3. 계층적 군집화
   - 전체 데이터를 몇 개의 배타적인 그룹으로 나누는 대신에 큰 군집이 작은 군집을 포함하는 형태로 계층을 이루도록 군집화를 수행하여 그 구조를 살펴보는 방법 → 병합적 방법과 분할적 방법으로 구분
   - 병합적 방법 → 각 데이터가 하나의 군집을 이루는 최소 군집에서 시작하여 가까운 군집들끼리 단계적으로 병합하여 더 큰 군집을 만들어 가는 방법
   - 분할적 방법 → 모든 데이터가 하나의 군집에 속하는 최대 군집에서 시작하여 특정 기준에 따라 군집을 분할해 가는 방법
   - 계층적 군집화 알고리즘(병합적 방법)의 수행 단계
   ① 데이터 집합으로부터 각 데이터가 각각의 군집이 되도록 N개의 군집을 설정함
   ② 가능한 모든 군집 쌍에 대해 군집 간의 거리를 계산함
   ③ 거리가 가장 가까운 두 군집을 선택하고 병합하여 새로운 하나의 클러스터를 생성함
   ④ 새로운 클러스터를 클러스터 풀에 넣고, 원래의 두 클러스터는 제거함
   ⑤ 오직 하나의 클러스터가 남을 때까지 ②~⑤의 과정을 반복함
   - 계층적 군집화 알고리즘를 적용할 때 고려사항
   ① 군집 간의 거리를 계산하는 방식 → 예) 최단 연결법, 최장 연결법, 중심 연결법, 평균 연결법, Ward’s 방법 등
   ② 계층적 군집화로부터 얻어진 덴드로그램을 분석하여 주어진 데이터에 적합한 군집의 수를 결정하는 문제 → 덴드로그램에서 클러스터 간의 거리가 증가하는 동안 클러스터의 수가 늘어나지 않고 일정 기간 유지되는 지점을 찾음