# 定義歐式距離
import numpy as np
def get_distance(x1, x2):
    return np.sqrt(np.sum(np.square(x1-x2)))

import random
# 定義中心初始化函數(shù)，中心點(diǎn)選擇的是樣本特征
def center_init(k, X):
    n_samples, n_features = X.shape
    centers = np.zeros((k, n_features))
    selected_centers_index = []
    for i in range(k):
        # 每一次循環(huán)隨機(jī)選擇一個(gè)類別中心,判斷不讓centers重復(fù)
        sel_index = random.choice(list(set(range(n_samples))-set(selected_centers_index)))
        centers[i] = X[sel_index]
        selected_centers_index.append(sel_index)
    return centers

# 判斷一個(gè)樣本點(diǎn)離哪個(gè)中心點(diǎn)近， 返回的是該中心點(diǎn)的索引
## 比如有三個(gè)中心點(diǎn)，返回的是0，1，2
def closest_center(sample, centers):
    closest_i = 0
    closest_dist = float('inf')
    for i, c in enumerate(centers):
        # 根據(jù)歐式距離判斷，選擇最小距離的中心點(diǎn)所屬類別
        distance = get_distance(sample, c)
        if distance < closest_dist:
            closest_i = i
            closest_dist = distance
    return closest_i

# 定義構(gòu)建聚類的過(guò)程
# 每一個(gè)聚類存的內(nèi)容是樣本的索引，即對(duì)樣本索引進(jìn)行聚類，方便操作
def create_clusters(centers, k, X):
    clusters = [[] for _ in range(k)]
    for sample_i, sample in enumerate(X):
        # 將樣本劃分到最近的類別區(qū)域
        center_i = closest_center(sample, centers)
        # 存放樣本的索引
        clusters[center_i].append(sample_i)
    return clusters

# 根據(jù)上一步聚類結(jié)果計(jì)算新的中心點(diǎn)
def calculate_new_centers(clusters, k, X):
    n_samples, n_features = X.shape
    centers = np.zeros((k, n_features))
    # 以當(dāng)前每個(gè)類樣本的均值為新的中心點(diǎn)
    for i, cluster in enumerate(clusters):  # cluster為分類后每一類的索引
        new_center = np.mean(X[cluster], axis=0) # 按列求平均值
        centers[i] = new_center
    return centers

# 獲取每個(gè)樣本所屬的聚類類別
def get_cluster_labels(clusters, X):
    y_pred = np.zeros(np.shape(X)[0])
    for cluster_i, cluster in enumerate(clusters):
        for sample_i in cluster:
            y_pred[sample_i] = cluster_i
            #print('把樣本{}歸到{}類'.format(sample_i,cluster_i))
    return y_pred

# 根據(jù)上述各流程定義kmeans算法流程
def Mykmeans(X, k, max_iterations,init):
    # 1.初始化中心點(diǎn)
    if init == 'kmeans':
        centers = center_init(k, X)
    else: centers = get_kmeansplus_centers(k, X)
    # 遍歷迭代求解
    for _ in range(max_iterations):
        # 2.根據(jù)當(dāng)前中心點(diǎn)進(jìn)行聚類
        clusters = create_clusters(centers, k, X)
        # 保存當(dāng)前中心點(diǎn)
        pre_centers = centers
        # 3.根據(jù)聚類結(jié)果計(jì)算新的中心點(diǎn)
        new_centers = calculate_new_centers(clusters, k, X)
        # 4.設(shè)定收斂條件為中心點(diǎn)是否發(fā)生變化
        diff = new_centers - pre_centers
        # 說(shuō)明中心點(diǎn)沒(méi)有變化，停止更新
        if diff.sum() == 0:
            break
    # 返回最終的聚類標(biāo)簽
    return get_cluster_labels(clusters, X)

# 測(cè)試執(zhí)行
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
# 設(shè)定聚類類別為2個(gè)，最大迭代次數(shù)為10次
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans')
# 打印每個(gè)樣本所屬的類別標(biāo)簽
print("最后分類結(jié)果",labels)
## 輸出為  [1. 1. 1. 0. 0.]

# 使用sklearn驗(yàn)證
from sklearn.cluster import KMeans
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init = 'random').fit(X)
# 由于center的隨機(jī)性，結(jié)果可能不一樣
print(kmeans.labels_)

## 得到kmean++中心點(diǎn)
def get_kmeansplus_centers(k, X):
    n_samples, n_features = X.shape
    init_one_center_i = np.random.choice(range(n_samples))
    centers = []
    centers.append(X[init_one_center_i])
    dists = [ 0 for _ in range(n_samples)]

    # 執(zhí)行
    for _ in range(k-1):
        total = 0
        for sample_i,sample in enumerate(X):
            # 得到最短距離
            closet_i = closest_center(sample,centers)
            d = get_distance(X[closet_i],sample)
            dists[sample_i] = d
            total += d
        total = total * np.random.random()

        for sample_i,d in enumerate(dists): # 輪盤法選出下一個(gè)聚類中心
            total -= d
            if total > 0:
                continue
            # 選取新的中心點(diǎn)
            centers.append(X[sample_i])
            break
    return centers

X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
# 設(shè)定聚類類別為2個(gè)，最大迭代次數(shù)為10次
labels = Mykmeans(X, k = 2, max_iterations = 10,init = 'kmeans++')
print("最后分類結(jié)果",labels)
## 輸出為  [1. 1. 1. 0. 0.]

# 使用sklearn驗(yàn)證
X = np.array([[0,2],[0,0],[1,0],[5,0],[5,2]])
kmeans = KMeans(n_clusters=2,init='k-means++').fit(X)
print(kmeans.labels_)