K-Means聚类算法

K-Means算法是一种无监督算法,不用标注分组信息即可完成模型的训练,K-Means算法思路清晰、使用简单,是一种高效聚类算法,其核心思想是利用距离函数,将属性相似的样本数据尽量聚集成一个集合,称每个集合为一个簇,同时要让不同簇之间的差异尽量的大。

一、K-Means算法介绍及实现

K-Means算法首先设定k个分类,假设样本的数据个数为N,具体步骤如下:

1任选样本中k个点作为k个簇的质心(重心),如有μ1μ2μ3、...,μk

2计算每个样本与μ1、μ2、μ3、...,μk的距离,常见的距离函数有欧氏距离、曼哈顿距离、闵可夫斯基距离等;如第j个样本点yj与质心uii<=k)之间距离最短,则将yj归为i类,保存yj的分类i。

3遍历每个样本点,将每个样本点按本轮分类分别以向量形式累加后,除以每个分类的个数,得到新的质心,计算公式如下:

png.png

4)将新的质心与本轮初始质心比较,当两者误差小于一定阈值后退出计算,得到最终的分类质心,否则重复第2)步。

下面以鸢尾花数据为例,分别用系统自带的K-Means算法与自实现的代码比较,为了演示方便,选择了鸢尾花数据中的两个分类

import numpy as np
from sklearn.cluster import  KMeans
from sklearn.datasets import  load_iris
import  matplotlib.pyplot as plt
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus'] = False
colors=['b','r','y']
ERROR=1e-5
def load():
    #加载鸢尾花数据,为方便二维演示只加载两类
    data = load_iris()
    classOne = np.where(data["target"] == 0)
    classTwo = np.where(data["target"] == 1)
    v=np.concatenate((data["data"][classOne,:2],data["data"][classTwo,:2]),axis=1)
    return np.squeeze(v)

#计算两个向量欧氏距离
def getdistance(v1,v2):
    v=v1-v2
    return  np.dot(v,v.T)

#KMeans实现
def KMeansNew(data,k1=None,k2=None):
    if(k1 is None or k2 is None  ):
        k1, k2 = data[0, :-1], data[1, :-1]
    for d  in range(data.shape[0]):
        d1=getdistance(data[d,:-1],k1 )
        d2 =getdistance(data[d,:-1],k2)
        data[d,2] = (0 if d1<d2 else 1)
    #计算新聚类集合质心
    u1,u2=np.zeros([1,2]),np.zeros([1,2])
    k1count,k2count=0,0
    for d in range(data.shape[0]):
        if(data[d,2]==0):
            u1[0, :]=u1[0,:]+data[d,0:-1]
            k1count=k1count+1
        else:
            u2[0, :]= u2[0,:] + data[d, 0:-1]
            k2count = k2count + 1
    newk1, newk2 =  u1[0, :]/k1count, u2[0, :]/k2count
    #小于设定阈值后从递归函数返回
    if(getdistance(newk1,k1)<=ERROR  and getdistance(newk2,k2)<=ERROR):
        return data
    else:
        return  KMeansNew(data, newk1, newk2)

def KmeansSystem(data:np.ndarray,n_clustersnumber):
    model = KMeans(n_clusters=n_clustersnumber, init='k-means++')
    model.fit(data)
    lables = model.labels_
    return  lables

def testKmeans():
    data = load()
    datacpy = data.copy()
    datacpy = np.insert(datacpy, 2, 0, axis=1)
     # 自定义KMeans
    datanew=KMeansNew(datacpy)
    #自带KMeans++实现
    lables=KmeansSystem(data,2)
    plt.subplot(211)
    for i in range(data.shape[0]):
        plt.scatter(data[i, 0], data[i, 1], c=colors[lables[i]], marker='o')
    plt.title('Kmeans算法')
    plt.subplot(212)
    for i in range(datanew.shape[0]):
        plt.scatter(datanew[i, 0], datanew[i, 1], c=colors[ int(datanew[i,2])  ] , marker='o')
    plt.title('自实现Kmeans算法')
    plt.show() 

if __name__=='__main__':
    testKmeans()

计算结构如下图:

Figure_1.png

二、K-Means++算法

K-Means算法初始时任意选择k个样板点作为质心,这导致后期更多次数的迭代,K-Means++算法改进了对初始质心的选择,通过计算,选择最为接近目标分类质心的位置作为初始质心,得到初始质心后接下来的算法与K-Means算法一致,初始质心的计算步骤如下:

-免费试读结束-
登录|注册后打赏作者吧! 1.0元
上一篇  C/C++、Java调用python函数
评论区