使用python实现经典的k-means算法

k-means聚类算法

K-means聚类算法是一种常用的聚类算法，它是重复移动数据类中心的过程，然后划分内部成员，其具体执行过程如下：

1.首先随机选取k个样本作为初始均值向量

2.计算每一个样本与均值向量之间的欧式距离，选取与当前样本欧式距离最小均值向量的类别作为当前样本的类别

3.计算每一个类别的向量的均值重新作为新的均值向量

4.重复2-3的过程直到均值向量没有变化或者达到一定的迭代次数结束

本文采用鸢尾花作为数据集，使用python语言实现，采用Jaccard系数作为评价指标，Jaccard系数计算过程如下：

遍历选取两个不同的样本，分为以下四种情况

1. 如果两个样本当前类别一样，并且目标类别一样，a+1
2. 如果两个样本当前类别一样，并且目标类别不一样，b+1
3. 如果两个样本当前类别不一样，并且目标类别一样，c+1
4. 如果两个样本当前类别不一样，并且目标类别不一样，d+1

Jaccard=a/(a+b+c),jaccard系数越接近1，说明聚类效果越好

初始k个样本不同时的聚类结果如下：

由上述结果可知，对于不同初始样本的选取，聚类效果差别很大

1. means的缺点：

1. 初始K值的个数无法预测
2. 初始的均值向量选取

1. means的改进：

1. 对于K值的个数无法预测，可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。

2.对于初始的均值向量选取，假设已经选取了n个初始聚类中心(0<n<k),则在选取第n+1个聚类中心时:距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心.在选取第一个聚类中心(n=1)时同样通过随机的方法。

以下是实现代码：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
import numpy as np

def load_data():
    iris = load_iris()
    iris_data = iris['data']
    iris_target = iris['target']
    x_train, x_test, y_train, y_test = train_test_split(iris_data, iris_target, test_size=0.2, random_state=22)
    return x_train,x_test,y_train,y_test
def judge(pre_u,u):
    arr=pre_u-u
    for i in range(u.shape[0]):
        for j in range(u.shape[1]):
            if arr[i][j]!=0:
                return False
    return True

def k_means(x_data,y_data,k,cnt):
    rand_k=np.random.randint(0,x_data.shape[0],size=(k,))   #初始化随机选取k个样本作为均值
    u=np.zeros(shape=(k,x_data.shape[1]))
    direct = {}
    for i in range(k):
        u[i,:]=x_data[rand_k[i],:]
        direct[rand_k[i]]=i
    for i in range(x_data.shape[0]):
        if i not in rand_k:
            d=u-x_data[i,:]
            dist=d*d
            s=np.sum(dist,axis=1)
            min_v=np.argmin(s)
            direct[i]=min_v

    pre_u=u
    epoch=1
    while True:
        u = np.zeros(shape=(k, x_data.shape[1]))          #重新计算u均值
        num_u=np.zeros(shape=(3,))
        for i in range(x_data.shape[0]):
            u[direct[i]]+=x_data[i]
            num_u[direct[i]]+=1
        for i in range(k):
            u[i]/=num_u[i]
        if judge(pre_u,u) or epoch>=cnt:
            break
        pre_u=u
        direct = {}
        for i in range(x_data.shape[0]):
                d = u - x_data[i, :]
                dist = d * d
                s = np.sum(dist, axis=1)
                min_v = np.argmin(s)
                direct[i] = min_v
        epoch+=1
    print('迭代次数为：')
    print(epoch)
    ind=np.zeros(shape=(4,))
    for i in range(x_data.shape[0]-1):
        for j in range(i+1,x_data.shape[0]):
            if direct[i]==direct[j] and y_data[i]==y_data[j]:
                ind[0]+=1
            elif direct[i]==direct[j] and y_data[i]!=y_data[j]:
                ind[1]+=1
            elif direct[i]!=direct[j] and y_data[i]==y_data[j]:
                ind[2]+=1
            else:
                ind[3]+=1
    print('Jaccard系数：')
    print(float(ind[0])/float(ind[0]+ind[1]+ind[2]))

if __name__ == '__main__':
    x_train, x_test, y_train, y_test=load_data()
    k_means(x_train,y_train,3,100)