비지도 학습 (Clustering ; K-means, DBSCAN, *Semi-supervised Learning, Active Learning)

(hands-on machine learning with scikit-learn, keras&tensorflow의 unsupervised learning techniques 챕터 정리)

 

대표적인 클러스터링 방법과 그 활용 방법에 대해서 정리.

Semi-supervised Learning의 동작 방식에 대해서도 정리.

활용 분야

• Customer Segmentation ; 웹사이트 상에서 유저의 행동을 기반으로 클러스터링 적용, 고객 분석 및 추천 시스템에 응용
• Data Analysis
• Dimensionality Reduction ; 클러스터링 후, 특정 아이템의 각 k개의 클러스터와의 affinity를 측정, k-dim 피쳐로 표현
• Anomaly Detection (Outlier Detection) ; 모든 클러스터에 대한 affinity가 낮은 경우 anomaly라고 판단 가능
• Semi-supervised Learning ; un-labled 데이터는 많고, 라벨링된 인스턴스는 적을 때
• Search Engine ; 비슷한 이미지 / 문서 그루핑

K-means

1. 랜덤한 centroids로 시작
2. centroids가 주어지면, 모든 인스턴스를 가장 가까운 centroid에 배정
3. 동일한 클러스터 내의 새로운 centroid를 업데이트
4. centroid가 변하지 않을 때 까지 [2-3] 반복

계산 복잡도는 인스턴스 개수 m, 클러스터 개수 k, 데이터의 차원 n에 선형적으로 비례

 

반드시 수렴하는 것이 보장되나, 시작 지점에 따라 결과가 달라질 수 있다.

따라서, 랜덤하게 n번 시도 후 가장 나은 것을 선택하는 방법이 있음.

 

'inertia' ; 인스턴스와 가장 가까운 centroid와의 mean squared distance

 

초기화 방법을 좀 더 효율적으로 개선하는 K-means++ 방법이 제안되기도 함.

(centroid를 서로 멀리 떨어진 녀석들로 선택함으로써 최적의 답을 찾는데 걸리는 시간을 많이 단축 시킴)

 

mini-batch K-means라는 변형 알고리즘도 있음.

각 이터레이션에 full data를 보는게 아니라, 미니 배치에 대해서만 보고 centroid를 업데이트

따라서 메모리에 다 들어오지 못하는 데이터의 규모에 대해서도 대응 가능

 

그럼, 최적의 클러스터 개수는 어떻게 찾나?

뭐 다 시도해보고 inertia 같은 지표로 비교해서 가장 낮은 모델 선택하면 되지 않나? 라는 생각을 할 수 있지만

클러스터 개수가 늘어날 수록 어쨌든 inertia는 줄어들게 되있음

 

휴리스틱 하게는, 클러스터 개수의 변화에 따른 inertia 값의 변화를 추적해보고

기울기가 급격히 줄어들다가 완만해 지는 부분 (Elbow) 부분을 택하면 된다.

hands on machine learning (2nd edition)

 

좀 더 나은 방법은 silhouette coefficient를 비교하는 것 (계산 시간은 오래 걸림)

= (b-a)/max(a,b)

a ; mean dist. to the other instances in the same cluster ; mean intra-cluster distance

b ; mean nearest-cluster distance ; the mean distance to the instances of the next closest cluster (b를 최소화 하는 것)

 

실루엣 계수는 -1 ~ +1 의 범위를 갖는다.

+1에 가까울 수록 인스턴스가 해당 클러스터 안에 잘 위치하고 다른 클러스터로는 멀리 위치해 있음을 의미.

 0에 가까울 수록 클러스터 경계에 가깝 다는 것.

-1에 가까울 수록 잘못된 클러스터에 배정되었을 가능성이 큰 것.

hands on machine learrning (2nd edition)

 

K-means의 한계는?

빠르고 스케일러블 하지만 완벽하진 않다.

sub-optimal solution에서 벗어나기 위해 여러 번 돌려야 하고,

클러스터 개수를 명시해야 한다는 단점...

클러스터의 사이즈가 다양하거나, density가 다르거나, 완전한 구의 형태가 아닐 때 잘 동작 못할 수 있다.

(예를 들어, 타원형의 클러스터에 적용했을 때, inertia 수치가 괜찮게 나온다 해도 실제로 확인했을 때 엉망일 수)

* 가우시안 믹스쳐는 타원형의 클러스터에 대해서도 잘 동작함.

* k-means 적용시 인풋에 대한 스케일은 맞춰주도록 하자.

 

DBSCAN

Local Density Estimation을 통해 임의의 모양을 가지는 클러스터에도 대응이 가능한 클러스터링 방법

• 거리를 의미하는 ε 파라미터를 두어 ε 반경 안에 들어오는 region을 ε-neighborhood라고 정의
• 정의된 minimum samples 개수를 넘어서는 ε-neighborhood 라면 core instance로 취급
• core instance의 ε 반경 안에 들어오는 인스턴스들은 모두 같은 클러스터에 속하게 된다.
• 만약 그 안에 또 다른 core instance가 있다면? 연쇄적으로 같은 클러스터를 이루게 된다.
• 어떤 그룹에도 속하지 못하는 인스턴스는 anomaly로 취급 가능!

 

노이즈에도 강한 알고리즘이지만, density가 전체적으로 다양하다면 적절히 동작 안할 수도 있음.

 

* Semi-Supervised Learning

unlabled-data가 넘쳐날 때, 클러스터링을 이용하여 다음과 같은 방법으로 분류 모델을 구현할 수 있다.

MNIST 데이터 & K-means 알고리즘 기준

1. 데이터를 50개의 클러스터로 클러스터링 (10개 클래스지만, 클래스 안에서도 여러 케이스가 있으니... 넉넉히)
2. 50개의 클러스터의 각 centroid에 가장 근접한 대표 이미지를 뽑는다.
3. 50개 이미지에 대해 라벨링 한다.
4. 대표 이미지의 라벨을 참고해서, 같은 클러스터의 인스턴스에 라벨링을 한다 (label propagation)
   * 클러스터 경계에 있는 데이터는 mislabled 가능성이 있으므로 중심으로 부터 몇 % 정도만 전파 시킴
5. 라벨링된 데이터로 분류모델을 학습&평가 한다.

 

Active Learning ?

데이터 레이블링을 좀 더 효과적으로 진행하기 위해 제안된 학습 방법으로,

불확실하다고 판단되는 데이터를 선별하여, 사람에게 레이블링을 요구하는 방법이다.

 

Active Learning에는 라벨링 되어야할 데이터를 선택하는

Query Strategy에 따라 다양한 방법이 있지만,

가장 흔히 쓰이는 것 중 하나로 'uncertainty sampling'이 있음

1. 지금까지 라벨링 된 데이터로 학습된 모델을 이용해서 모든 언레이블드 데이터에 대해 예측
2. 모델이 자신 없어 하는 인스턴스에 대해 전문가의 라벨링 요청 (estimated probability 가 낮은 불확실한/모호한 것들)
3. 성능이 개선 될 때 까지 반복

그 외

• 다른 알고리즘/모델을 이용해 예측했을 때 불일치가 가장 많았던 인스턴스에 대해 라벨링
• 모델에 변화를 가장 많이 가져올 인스턴스에 대해 라벨링
• 모델의 벨리데이션 에러에 가장 큰 손해를 가져오는 인스턴스에 대해 라벨링
• 등등 여러가지...