opencv python - K-Means Clustering

T-shirt size problem

아래는 옷을 생산할 때 , 참고하기 위해 만든 사람들의 키와 몸무게에 대한 데이터를 도식화한 그림이다.

회사 입장에서는 모든 사이즈를 만들 수 없기 때문에 아래 그림처럼 사람들의 신체사이즈를 그룹화하여 3개 혹은 5개의 그룹으로 만들어서 제품을 생산하게 된다. 이때 사용할 수 있는 것이 K-Means Clustering이다. 

How does it work ?

이 알고리즘은 반복적인 처리(iterative process) 알고리즘이다.  단계별로 두 개의 데이터 그룹으로 그룹화 해보도록 하자.

1단계 : 알고리즘은 임의로 두 개의 중심점(centroid)인 C1과 C2를 선택한다.   C1, C2 ( 중심 점으로 두 개의 데이터를 선택하기도 한다. )

2단계 : 두 개의 중심점으로 부터 각 점들까지의 거리를 계산한다.  C1에 가까운 데이터엔 0으로 이름 붙이고 C2에 가까운 데이터엔 1이라고 이름을 붙인다.  이미지상에서는 0으로 라벨붙인 점들은 빨간색, 1로 라벨붙인 점들은 파란색으로 표현되었다.

3단계 :  빨간 점들과 파란점 들의 좌표들에 대해 각각 평균점을 구한다. 이점이 새로운 C1과 C2가 된다. 다시 2단계를 반복한다. 아래 그림은 새로운 평균점이 이동한 후.. 다시 가까운쪽 중심점에 속하는 점들을 나눈 결과이다. 

2단계와 3단계를 계속 반복한다. 중심점이 더 이상 이동하지 않으면 반복이 종료된다.

(C1 중심점과 빨간색 점들간의 거리의 합  + C2중심점과 파란색 점들간의 거리의 합 ) 이 최소가 되는 것을 찾으면 종료되는 것이다. 최종적으로는 아래와 같이 두 그룹으로 나누어 질것이다.

10번 반복하거나 정확도(accuracy of epsilon)가 1.0에 도달했을때 반복을 중단하고 결과를 내놓도록 기준을 정해서 태스트하는 예제이다.

1. #-*- coding: utf-8 -*-  
2.   
3. import numpy as np  
4. import cv2  
5. from matplotlib import pyplot as plt  
6.   
7. #25~50사이의 숫자를 랜덤으로 2차원 데이터 (x,y) 25개 뽑음  
8. a = np.random.randint(25,50,(25,2))  
9.   
10. #60~85사이의 숫자를 랜덤으로 랜덤으로 2차원 데이터 (x,y) 25개 뽑음  
11. b = np.random.randint(55,85,(25,2))  
12.   
13. #수직방향으로 값들을 넣어준다.  
14. z = np.vstack((a,b))  
15.   
16. #float32타입으로 데이터를 변경한다.  
17. z=np.float32(z)  
18.   
19.   
20.   
21.  # Define criteria = ( type, max_iter = 10 , epsilon = 1.0 )  
22. criteria = (cv2.TERM_CRITERIA_EPS+cv2.TERM_CRITERIA_MAX_ITER,10,1.0)  
23.   
24. #초기 중심점을 랜덤으로 정한다.  
25. flags = cv2.KMEANS_RANDOM_CENTERS  
26.   
27.   
28. #KMeans를 적용한다. k=2, 10번 반복한다.  
29. compactness,labels,centers = cv2.kmeans( z, 2, criteria, 10, flags )  
30.   
31. #라벨을 보고 데이터를 두 그룹으로 나눈다.  
32. A = z[labels.ravel()==0]  
33. B = z[labels.ravel()==1]  
34.   
35. #화면에 출력  
36. plt.scatter(A[:,0], A[:,1], c='b')  
37. plt.scatter(B[:,0], B[:,1], c='r')  
38. plt.scatter( centers[:,0], centers[:,1], s=80, c='y', marker='s')  
39.   
40. plt.xlabel('Height')  
41. plt.ylabel('Weight')  
42. plt.show()  

원본글

http://docs.opencv.org/3.0.0/de/d4d/tutorial_py_kmeans_understanding.html

http://docs.opencv.org/3.0.0/d1/d5c/tutorial_py_kmeans_opencv.html