简单聚类方法K-means方法的实现

忘是亡心i 2022-06-18 03:22 158阅读 0赞

实例：根据药品的特征对药品进行分类  
实现：根据python实现的K-means聚类  
1.1 归类  
聚类属于非监督学习，无类别标记  
1.2 K-means算法  
1.Clustering中的经典算法，数据挖掘十大经典算法之一  
2.算法接受参数K，然后将事先输入的n个对象划分为K个聚类以便使获得的聚类满足：同一聚类的对象 相似度比较高，而不同聚类的对象相似度较小。  
3.算法思想：  
以空间当中的K个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类效果。  
4.算法描述  
（1）适当选择C个类的初始中心  
（2）在第K次迭代中，对任意一个样本，求其到C各中心的距离，将该样本归到距离最短的中心所在的类；  
（3）利用均值等方法更新该类的中心值  
（4）对于所有的C个聚类中心，如果利用（2）（3）的迭代算法更新之后，值保持不变，或者达到一定的迭代次数，或者分类的变化小于一个阈值，则迭代结束，否则继续迭代  
5.算法流程  
![这里写图片描述][SouthEast]  
![药品实例这里写图片描述][SouthEast 1]  
优点：速度快，简单  
缺点：最终结果与初始点的选择相关，容易陷入局部最优，需要知道K值

代码实现：

#coding=utf-8
    #简单聚类方法K-means方法的实现
    
    import numpy as np
    #数据集需要加一列
    #参数：数据集，分为几类，迭代次数
    def kmeans(X,k,maxIt):
        #返回行列维度
        numPoints,numDim = X.shape
        #增加一列作为分类标记
        dataSet = np.zeros((numPoints,numDim+1))
        # 所有行，除了最后一列
        dataSet[:,:-1] = X
        #随机选取K行，包含所有列
        centroids = dataSet[np.random.randint(numPoints,size = k),:]
        #centroids = dataSet[0:2,:]
        #给中心点分类进行初始化
        centroids[:,-1] = range(1,k+1)
        iterations = 0
        oldCentroids = None
    
        while not shouldStop(oldCentroids,centroids,iterations,maxIt):
            print "iteration:\n",iterations
            print "dataSet:\n", dataSet
            print "centroids:\n", centroids
            #不能直接用等号，不然会指向同一个变量
            oldCentroids = np.copy(centroids)
            iterations += 1
            #根据数据集以及中心点对数据集的点进行归类
            updateLabels(dataSet,centroids)
            # 更新中心点
            centroids = getCentroids(dataSet,k)
        return dataSet
    #实现函数循环结束的判断
    #当循环次数达到最大值，或者中心点不变化就停止
    def shouldStop(oldCentroids,centroids,iterations,maxIt):
        if iterations > maxIt:
            return True
        return  np.array_equal(oldCentroids,centroids)
     #根据数据集以及中心点对数据集的点进行归类
    def updateLabels(dataSet,centroids):
        #返回行（点数），列
        numPoints,numDim = dataSet.shape
        for i in range(0,numPoints):
            #对每一行最后一列进行归类
            dataSet[i,-1] = getLabelFromCLoseCentroid(dataSet[i,:-1],centroids)
    #对比一行到每个中心点的距离，返回距离最短的中心点的label
    def getLabelFromCLoseCentroid(dataSetRow,centroids):
        #初始化label为中心点第一点的label
        label = centroids[0,-1]
        #初始化最小值为当前行到中心点第一点的距离值
        #np.linalg.norm计算两个向量的距离
        minDist  = np.linalg.norm(dataSetRow - centroids[0,:-1])
        #对中心点的每个点开始循环
        for i in range(1,centroids.shape[0]):
            dist = np.linalg.norm(dataSetRow - centroids[i,:-1])
            if dist < minDist:
                minDist = dist
                label = centroids[i,-1]
        print "minDist",minDist
        return label
    # 更新中心点
    #参数：数据集（包含标签），k个分类
    
    def getCentroids(dataSet,k):
        #初始化新的中心点矩阵
        result = np.zeros((k,dataSet.shape[1]))
        for i in range(1,k+1):
            #找出最后一列类别为i 的行集,即求一个类别里面的所有点
            oneCluster = dataSet[dataSet[:,-1]==i,:-1]
            #axis = 0 对行求均值，并赋值
            result[i-1,:-1] = np.mean(oneCluster,axis=0)
            result[i-1,-1] = i
        return result
    x1 = np.array([1,1])
    x2 = np.array([2,1])
    x3 = np.array([4,3])
    x4 = np.array([5,4])
    testX = np.vstack((x1,x2,x3,x4))#将点排列成矩阵
    print testX
    result =  kmeans(testX,2,10)
    print "final result:"
    print result

[SouthEast]: /images/20220618/213edeed83944f00b7087b3737d0be6e.png
[SouthEast 1]: /images/20220618/20ab5f723931483fa9aaccae9a8f0eec.png