---
# System prepended metadata

title: k-means 筆記
tags: [機器學習]

---

# k-means 筆記

```python=
import random
import matplotlib.pyplot as plt
import numpy as np

#距離比較，並存取哪個點離中心點近存取
def distance_cmp(num_k, b_data, k_center): #num_k: 中心點座標, b_data: 原始資料, k_center: 欲算的k值   
    x_cluster = [[] for i in range(k_center)] #存取群聚的點
    for i in range(len(b_data)):

        Dis = []
        for j in range(k_center):
            sum = 0 
            for k in range(4): #(4維值)
                sum = sum + (num_k[j][k] - b_data[i][k]) ** 2
            sum = sum ** 0.5
            Dis.append(sum)
        for dis_index in range(k_center):
            if(Dis[dis_index] == min(Dis)):
                x_cluster[dis_index].append(i) #取最小值抓入
    for i in range(k_center):
        final_cluster_point[i] = x_cluster[i]
        print("No.", i + 1, "cluster :", final_cluster_point[i])
    update_cmp(x_cluster, b_data, k_center) #更新群心點座標

#更新群心點座標
def update_cmp(c_data, b_data, k_center): #c_data: 每個群的點, b_data: 原始資料, k_center: 欲算的k值 
    x_update = [[] for i in range(k_center)]
    for j in range(k_center):
        for i in range(4):
            sum = 0 
            for k in c_data[j]:
                sum = sum + (b_data[k][i])
            x_update[j].append(sum / len(c_data[j]))  #更新群心點座標
    for i in range(k_center):
        x[i] = x_update[i]
        print("No.", i + 1, "x_update :", x[i])


#算出最佳k值解(SSE)
def sum_squared_error(stable_data, source_data, cluster_data, k_num):
    sum_all_point_dis = 0
    for num_cluster in range(k_num):
        for i in cluster_data[num_cluster]:
            sum_dis = 0
            for j in range(4):
                sum_dis = sum_dis + (stable_data[num_cluster][j] - source_data[i][j]) ** 2
            sum_dis = sum_dis ** 0.5
            sum_all_point_dis = sum_all_point_dis + sum_dis
    optimal_k.append(sum_all_point_dis)

optimal_k = []
for k in range(1, 10):
    data = np.loadtxt('k-means_data.txt', dtype = np.int32)
    x = [[0] * 4 for i in range(k)]
    final_cluster_point = [[] for i in range(k)]
    
    y = range(len(data))
    index = random.sample(y, k)
    for i in range(k):
        x[i] = data[index[i]]

    for i in range(k):
        print("No.", i + 1, "k =", x[i])
    print("\n")

    x_stable = [[] * 4 for i in range(k)]
    for i in range(k):
        for j in range(4):
            x_stable[i].append(x[i][j])
    print("Iteration 1")
    distance_cmp(x, data, k)
    print("\n")

    #迭代上限77
    for iteration in range(77):
        #判斷是否迭代完有更新
        if(x_stable != x):
            x_stable = [[] * 4 for i in range(k)]
            for i in range(k):
                for j in range(4):
                    x_stable[i].append(x[i][j])
            print("Iteration ", iteration + 2)
            distance_cmp(x, data, k)
            print("\n")
        else :
            break
    sum_squared_error(x_stable, data, final_cluster_point, k)

print(optimal_k)
n_k = [1, 2, 3, 4, 5, 6, 7, 8, 9]
plt.xlabel('k')
plt.ylabel('SSE')
plt.plot(n_k, optimal_k)
plt.show()
```

### 從這開始講解

```python=
def distance_cmp(num_k, b_data, k_center): #num_k: 中心點座標, b_data: 原始資料, k_center: 欲算的k值   
    x_cluster = [[] for i in range(k_center)] #存取群聚的點
    for i in range(len(b_data)):
        Dis = []
        for j in range(k_center):
            sum = 0 
            for k in range(4): #(4維值)
                sum = sum + (num_k[j][k] - b_data[i][k]) ** 2
            sum = sum ** 0.5
            Dis.append(sum)
        for dis_index in range(k_center):
            if(Dis[dis_index] == min(Dis)):
                x_cluster[dis_index].append(i) #取最小值抓入
    for i in range(k_center):
        final_cluster_point[i] = x_cluster[i]
        print("No.", i + 1, "cluster :", final_cluster_point[i])
    update_cmp(x_cluster, b_data, k_center) #更新群心點座標
```

- 假設目前資料有 10 筆, 想要找到最佳分群數目 最爛就是10群 最好1群, 所以可以用窮舉法 用 k_center(1~10)去算
- 現在去算 從 k_center = 1開始算 到 10(隨機)選一個數當中心點 用這個點去與其他點算兩點距離(舉例兩個4維座標 A(x1, y1, z1, k1), B(x2, y2, z2, k2) 可得出 兩點距離公式
$$
sqrt{(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 + (k1-k2)^2})
$$

- 就是上方程式中第 9~10行 最後存近一個 Dis = [] 的list

#### 接著上方程式中第 3~13行

- 第3行 由於for 迴圈 i 是歷遍所有資料點 10 筆 所以 每筆點都有一個 Dis = [] , 在第5行時 當 k_center = 1 時 Dis = [] 裡面只會有1筆資料, k_center = 2 時 Dis = [] 裡面只會有2筆資料, 此 Dis 存放的資料為此點距離 k_center 中心點的距離 
- 舉例 當k_center = 2時 中心點為 A 跟 B, 此時 C 的 

$$
Dis = ((C-A的距離), (C-B的距離))
$$


#### 第11行 當 k_center = 2 開始 
- 
```python=
for dis_index in range(k_center)
```
- for迴圈 dis_index 會 從 0~1 對應著上述舉例 (C-A的距離) 與 (C-B的距離), min(Dis) 則是返回 最短距離那個 找出 C離 A還是B哪個近

```python=
x_cluster[dis_index].append(i) #取最小值抓入
```
- C 最靠近哪個中心點則放進那個群體 **x_cluster[dis_index]**, i 是 C 那個點的index

```python=
update_cmp(x_cluster, b_data, k_center) #更新群心點座標
```
- 這行功能是對那個群體做中心點的更新 

```python=
#更新群心點座標
def update_cmp(c_data, b_data, k_center): #c_data: 每個群的點, b_data: 原始資料, k_center: 欲算的k值 
    x_update = [[] for i in range(k_center)]
    for j in range(k_center):
        for i in range(4): #(4維值)
            sum = 0 
            for k in c_data[j]:
                sum = sum + (b_data[k][i])
            x_update[j].append(sum / len(c_data[j]))  #更新群心點座標
    for i in range(k_center):
        x[i] = x_update[i]
        print("No.", i + 1, "x_update :", x[i])
```


- 先定義更新後的中心點座標
```python=
x_update = [[] for i in range(k_center)]
```
- 更新群心點座標顧名思義 選取那個群體的所有點取中心, 假設現在有3個4維的點 A(x1, y1, z1, k1), B(x2, y2, z2, k2), C(x3, y3, z3, k3)
$$
中心sum(sumx, sumy, sumz, sumk) =(((x1 + x2 + x3)/3),((y1 + y2 + y3) / 3),((z1 + z2 + z3) / 3),((k1 + k2 + k3) / 3))
$$

```python=
sum / len(c_data[j])
```

- for k in c_data[j]: 中的 k 是歷遍 c_data[j] 此群體裡面的值, 而這個值代表所有資料點的 那個 index 位置

### 此處要注意 更新完後的群心點座標後 要在帶入回 distance_cmp 這個function 等到 中心點不在更新後 確認群體的中心點

```python=
#最終算出最佳k值解(SSE)
def sum_squared_error(stable_data, source_data, cluster_data, k_num):
    sum_all_point_dis = 0
    for num_cluster in range(k_num):
        for i in cluster_data[num_cluster]:
            sum_dis = 0
            for j in range(4):
                sum_dis = sum_dis + (stable_data[num_cluster][j] - source_data[i][j]) ** 2
            sum_dis = sum_dis ** 0.5
            sum_all_point_dis = sum_all_point_dis + sum_dis
    optimal_k.append(sum_all_point_dis)
```

- stable_data 為最終穩定的中心點, source_data 所有資料點, cluster_data 群體, k_num 為 幾個群心

- SSE 算出穩定中心點與它群體的所有點距離合 作為分幾群的評判指標
- 資料如果為n筆資料 則 迭代 n 次
- 一直重複 distance_cmp 與 update_cmp function 最終找到穩定不在更新的群體中心點