k-均值聚类算法

聚类算法是对样本集按相似性进行分簇，因此，聚类算法能够运行的前提是要有样本集，以及能对样本之间的相似性进行比较的方法。

样本的相似性差异也称为样本距离，相似性比较称为距离度量。

算法基本思想：

K-means 算法的基本思想是让簇内的样本点更“”紧密“”一些。让每个样本点到本簇中心的距离更近一些。让每个样本点到本簇中心的距离的平方和尽量小时k-means算法的优化目标。

import numpy as np
import matplotlib.pyplot as plt

def L2(vecXi,vecXj):
    '''
    计算欧式距离函数
    :param vecXi: 点坐标
    :param vecXj: 点坐标
    :return: 两点之间的欧式距离
    '''
    return np.sqrt(np.sum(np.power(vecXi-vecXj,2)))

def kMeans(S,k,distMeans=L2):
    '''
    K-means聚类
    :param S: 样本集
    :param k: 簇的个数
    :param distMeans:欧氏距离函数
    :return sampleTag:一维数组，存放样本点所对应的簇
    :return clusterCents:一位数组，存放簇的坐标
    :return SSE：误差平方和
    '''
    m = np.shape(S)[0]#获得样本数量
    sampleTag = np.zeros(m)#创建m个0的一维数组，用来存放样本点相对应的簇

    n = np.shape(S)[1]#获得样本集的特征数
    # 初始化3个簇点坐标，随机定义 np.mat用来定义数组函数
    clusterCents = np.mat([[-1.93964824,2.33260803],[7.79822795,6.72621783],[10.64183154,0.20088133]])

    sampleTagChanged = True
    SSE = 0.0
    while sampleTagChanged:
        sampleTagChanged = False#防止死循环
        SSE= 0.0

        #计算每个样本点到各个簇点的距离
        for i in range(m):#外层for用来实现从样本集中顺序挑选点进行计算与每个簇点的距离
            minD = np.inf# np.inf 表示是无穷大
            minIndex = -1#初始化索引值
            for j in range(k):#将第i个样本点与k个簇点分别进行计算
                d = distMeans(clusterCents[j,:],S[i,:])#调用距离函数
                if d <minD:#查找样本点所属的簇点
                    minD = d
                    minIndex = j
            if sampleTag[i]!=minIndex:#判断样本点是否所属簇变化
                sampleTagChanged = True
            sampleTag[i] = minIndex
            SSE+=minD**2
        print(clusterCents)
        #簇点散点图
        plt.scatter(clusterCents[:,0].tolist(),clusterCents[:,1].tolist(),c='r',marker='^',linewidths=7)
        #样本散点图
        plt.scatter(S[:,0],S[:,1],c=sampleTag,linewidths=np.power(sampleTag+0.5,2))
        plt.show()
        print(SSE)

        #更新簇点
        for i in range(k):
            #np.nonzero(sampleTag[:]==i)筛选第i个簇有哪些样本点，得到样本点的索引值
            ClustI = S[np.nonzero(sampleTag[:]==i)[0]]#得到第i个簇中样本坐标
            clusterCents[i,:]=np.mean(ClustI,axis = 0)#求均值，更新簇坐标
    return clusterCents,sampleTag,SSE

if __name__ =='__main__':
    samples = np.loadtxt("kmeansSamples.txt")
    clusterCents,sampleTag,SSE = kMeans(samples,3)
    plt.show()
    print(clusterCents)
    print(SSE)