# 2020/3/15-3/16 K-means Clustering (K-means 集群分析)
K-means Clustering，顧名思義它是一種 Clustering Algorithm。 Clustering 的中文可以翻作**分群、集群或聚類**。

基本上 Clustering Algorithm 都是在做<span style = 'background-color:yellow'>**非監督式學習**</span> ( Unsupervised Learning )，而今天要介紹的K-means 也不例外。所謂的監督式學習與非監督式學習，它們的差別就在於資料集本身，監督式學習使用的資料集裡面除了資料本身之外，還帶有一個 Ground Truth 的正確解答；而非監督式學習使用的資料集裡面就只有資料本身。

舉例，我給你一組身高和體重的資料，但我沒有跟你說這組資料哪些是男生哪些是女生。我希望你用這組資料分出男生女生，這種時候就是用非監督式學習。

<font color = '#3A96B8' size = 4>**Clustering 就是一個「物以類聚」的概念。**</font>
我們的目的是希望讓男生的資料可以自己變成一群，女生的資料自己變成另一群。理論上同一群的資料應該會具有某依些相似的特徵，所謂的"相似"在數學上就是距離比較近 ( e.g. 1、2、97、99，1跟2就相似，97跟99比較相似。)
## K-means 運作的流程步驟
1. 首先設定要分成多少群：K
2. 然後在特徵空間中隨機設定K個群心。
3. 計算每一個資料點到K個群心的距離 ( 基本上使用 L2距離，但也是可以換成別的。)
4. 將資料點分給距離最近的那個群心。
5. 在所有資料點都分配完畢後，每一群再用剛剛分配到的資料點算平均(means)來更新群心。

6. 最後不斷重複3–5 的動作，直到收斂 ( 每次更新後群心都已經不太會變動 ) 後結束。

我拿其他網站的GIF圖來解釋K-means的流程步驟

K-means分群的時間複雜度為 O(NKT) ， N 是數據數量， K 是群集數量， T 是重複次數。
我們無法預先得知群集數量、重複次數。數據分布情況、群集中心的初始位置，都會影響重複次數，運氣成份很大。

## K-means程式說明及使用
進入前，先說明「疊代」的意思：
**疊代**是重複回饋過程的活動，其目的通常是為了接近併到達所需的目標或結果。每一次對過程的重複被稱為一次「疊代」，而每一次疊代得到的結果會被用來作為下一次疊代的初始值。
<pre><font size = 2>程式碼函式：
<b>cv2.kmeans(data, K, bestLabels, criteria, attempts, flags)</b>
引數含義：
data - 分類數據，最好是np.float32的數據
(np.float32數據類型運算速度快，同樣的數據下如果是uint型數據將會很慢。)
K - 類別數
bestLabels - 預設的分類標籤(沒有的話 None)
criteria - 疊代終止的條件，有3個引數，格式為（type,max_iter,epsilon）
attempts - 重複試驗kmeans算法次數，將會返回最好的一次結果
flags - 初始類別中心的選擇，兩種方法

輸出引數：
compactness - 集聚性，指每個點到相應聚類中心點的距離平方的和；
labels - 聚類的標識序列（‘0’， ‘1’……）；
centers - 聚類中心的序列。</font>
</pre>

<pre><font size = 2>criteria的引數：
type:
1. cv2.TERM_CRITERIA_EPS :精確度（誤差）滿足epsilon停止。
2. cv2.TERM_CRITERIA_MAX_ITER：疊代次數超過max_iter停止。
3. cv2.TERM_CRITERIA_EPS+cv2.TERM_CRITERIA_MAX_ITER：兩者合一，任意一個滿足結束。
max_iter ： 最大疊代次數
epsilon ： 精確度</font>
</pre>

<pre><font size = 2>flags的兩種方法：
1. cv2.KMEANS_PP_CENTERS : 該方法首先疊代整個圖像以確定可能的中心，然後開始收斂。
2. cv2.KMEANS_RANDOM_CENTERS：該方法總是從一組隨機的初始樣本開始，並嘗試從那裡收斂。</font>
</pre>

### 彩色圖片
程式碼

import cv2
import numpy as np
import matplotlib.pyplot as plt
image = cv2.imread("58.png")# read the image
image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB)# convert to RGB

# reshape the image to a 2D array of pixels and 3 color values (RGB)
pixel_values = image.reshape((-1, 3))

# convert to float 
pixel_values = np.float32(pixel_values)
print(pixel_values.shape)

# define stopping criteria
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 100, 0.2)
k = 3
_, labels, (centers) = cv2.kmeans(pixel_values, k, None, criteria, 10, cv2.KMEANS_RANDOM_CENTERS)
# convert back to 8 bit values
centers = np.uint8(centers)
# flatten the labels array
labels = labels.flatten()
# convert all pixels to the color of the centroids
segmented_image = centers[labels.flatten()]
# reshape back to the original image dimension
segmented_image = segmented_image.reshape(image.shape)
# show the image
plt.imshow(segmented_image)
plt.show()

呈現結果

### 灰色圖片
程式碼

import cv2
import numpy as np
import matplotlib.pyplot as plt

img = cv2.imread('US8925200B2.png',0) # image read be 'gray'

#change img(2D) to 1D
img1 = img.reshape((img.shape[0]*img.shape[1],1))
img1 = np.float32(img1)

#define criteria = (type,max_iter,epsilon)
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER,10,1.0)

#set flags: hou to choose the initial center
#---cv2.KMEANS_PP_CENTERS ; cv2.KMEANS_RANDOM_CENTERS
flags = cv2.KMEANS_RANDOM_CENTERS
# apply kmenas
compactness,labels,centers = cv2.kmeans(img1,4,None,criteria,10,flags)

img2 = labels.reshape((img.shape[0],img.shape[1]))

plt.subplot(121),plt.imshow(img,'gray'),plt.title('original')
plt.xticks([]),plt.yticks([])
plt.subplot(122),plt.imshow(img2, 'gray'),plt.title('kmeans')
plt.xticks([]),plt.yticks([])
plt.show()

呈現結果

## 心得
K-means 在分類上如果未有正確資料時，是一個可以拿來試的方法，在圖片上，則是一個適合前處理使用的方法，現在的圖片都是RGB且顏色的色調太多，無法正確的去掉雜質，這時K-means就是一個好方法。