# 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 最終找到穩定不在更新的群體中心點
Sign in with Wallet
Connect another wallet