import numpy as np # numpy：数值计算
import pandas as pd # pandas：数据处理与分析
import matplotlib.pyplot as plt # matplotlib：绘图
import random # random：生成随机数


dataset = pd.read_csv('watermelon.csv', delimiter=",")
data = dataset.values # 将数据转换为numpy数据，便于后续处理

print(dataset)

# 定义距离计算函数
def distance(x1, x2):  # 计算距离
    return sum((x1-x2)**2) # 计算两个样本点之间的欧几里得距离的平方
                           # 这里没有开平方根，因为比较距离大小时平方值同样有效。


def Kmeans(D,K,maxIter): # D：数据集，是一个二维数组
                         # K：聚类的类别数
                         # maxIter：最大迭代次数
    m, n = np.shape(D) # m：样本数量 n：特征数量
    if K >= m: # 若K大于等于样本数，则直接返回数据集D
        return D
    # 1.初始化质心
    initSet = set()
    curK = K
    while(curK > 0):  # 随机选取k个样本
        randomInt = random.randint(0, m-1) # 随机选取K个样本作为初始质心
        if randomInt not in initSet:
            curK -= 1
            initSet.add(randomInt)
    U = D[list(initSet), :]  # 均值向量,即质心
    C = np.zeros(m) # C数组用于存储样本所属的类别
    curIter = maxIter  # 最大的迭代次数
    # 2.聚类过程
    while curIter > 0:
        curIter -= 1
        # 对于每一个样本，计算其到所有质心的距离
        for i in range(m):
            p = 0
            minDistance = distance(D[i], U[0])
            for j in range(1, K):
                if distance(D[i], U[j]) < minDistance: # 选择最近的质心所属的类别作为该样本的类别
                    p = j
                    minDistance = distance(D[i], U[j])
            C[i] = p
        # 3.更新质心
        newU = np.zeros((K, n)) # newU：新的质心
        cnt = np.zeros(K) # cnt：每个类别（簇）中所含的样本数量

        for i in range(m):
            newU[int(C[i])] += D[i]
            cnt[int(C[i])] += 1
        changed = 0
        # 判断质心是否发生变化，如果发生变化则继续迭代，否则结束
        for i in range(K):
            newU[i] /= cnt[i]
            for j in range(n):
                if U[i, j] != newU[i, j]:
                    changed = 1
                    U[i, j] = newU[i, j]
        if changed == 0:
            return U, C, maxIter-curIter
    return U, C, maxIter-curIter

U, C, iter = Kmeans(data,3,20) # 调用K-means函数，设置类别数为3，最大迭代次数为20
                               # U：最终的质心 C：每个样本的类别 iter：实际迭代的次数

# 可视化结果
f1 = plt.figure(1)
plt.title('watermelon')
plt.xlabel('density') # 横轴：密度
plt.ylabel('ratio') # 纵轴：比例
plt.scatter(data[:, 0], data[:, 1], marker='o', color='g', s=50) # 绿色圆点表示所有样本点
plt.scatter(U[:, 0], U[:, 1], marker='o', color='r', s=100) # 红色圆点表示质心
m, n = np.shape(data)
for i in range(m):
    plt.plot([data[i, 0], U[int(C[i]), 0]], [data[i, 1], U[int(C[i]), 1]], "c--", linewidth=0.3) # 青色虚线连接每个样本点和其所属类别的质心
plt.show()

时间复杂度分析：
1.初始化质心（O(k * m)） – 随机选择k个样本作为初始质心；最坏情况下，可能需要遍历m个样本才能找到K个不重复的样本。
2.聚类过程（O(maxIter * m * K * n)） – 外层循环最多执行maxIter次；对于每个样本（一共m个），需要计算其到K个质心的距离，每次距离计算需要O(n)时间。
3.更新质心（O(m * n + K * n)） - 遍历所有样本（m 个），将样本累加到对应类别的质心，时间复杂度为O(m * n)；更新每个质心（K 个），时间复杂度为O(K * n)。

综上：将上述部分的时间复杂度相加，得到整个 K-Means 算法的时间复杂度为：
O(K * m + maxIter * m * K * n + maxIter * (m * n + K * n))

附录：Watermalon数据集（摘选），保存为Watermelon.csv
density,ratio
0.697,0.460
0.774,0.376
0.634,0.264
0.608,0.318
0.556,0.215
0.403,0.237
0.481,0.149
0.437,0.211
0.666,0.091
0.243,0.267
0.245,0.057
0.343,0.099
0.639,0.161
0.657,0.198
0.360,0.370
0.593,0.042
0.719,0.103
0.359,0.188
0.339,0.241
0.282,0.257
0.748,0.232
0.714,0.346
0.483,0.312
0.478,0.437
0.525,0.369
0.751,0.489
0.532,0.472
0.473,0.376
0.725,0.445
0.446,0.459