聚类算法之K均值算法(k-means)

算法简介

K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。

聚类问题

通常，人们根据样本间的某种距离或者相似性来定义聚类，即把相似的（或距离近的）样本聚为同一类，而把不相似的（或距离远的）样本归在其他类。

所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。

k-means算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

算法步骤

1. 从D中随机取k个元素，作为k个簇的各自的中心。

2. 分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。

3. 根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。

4. 将D中全部元素按照新的中心重新聚类。

5. 重复第4步，直到聚类结果不再变化。

6. 将结果输出。

算法实现

import numpy as np
import random
import matplotlib.pyplot as plt

def euclDistance(vector1, vector2):
    '''
    计算两个元素之间的欧氏距离
    '''
    return np.sqrt(np.sum(np.power(vector2 - vector1, 2)))

def initCentroids(dataSet, k):
    '''
    随机生成K个初始质心
    '''
    numSamples, dim = dataSet.shape #得到dataSet的行和列
    index = random.sample(range(numSamples),k) #随机生成K个不重复的实数，返回一个列表。
    centroids = np.array([dataSet[i,:] for i in index]) #创建K个初始质心放在一个数组中
    return centroids

def kmeans(dataSet, k):
    numSamples = dataSet.shape[0]
    clusterAssment = np.zeros((numSamples, 2)) #创建一个numSamples行2列的全零矩阵用于存储元素的所属簇和元素本身
    centroids = initCentroids(dataSet, k) #初始质心
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(numSamples):
            #遍历每一个元素
            minDistance = float("inf")  #设定元素与质心之间的初始距离为无穷大
            ownGroup = 0 #设定元素初始所属簇
            for j in range(k):
                #计算第i个元素分别与k个质心的距离
                distance = euclDistance(centroids[j, :], dataSet[i, :])
                if distance < minDistance:
                    #把元素归为与质心欧式距离最小的那个簇中
                    minDistance = distance
                    ownGroup = j
            if clusterAssment[i, 1] != ownGroup:
                #判断该元素所属组是否发生变化，若变化了就继续进行循环，直到每个元素所属组不在变化就结束循环
                clusterAssment[i, 1] = ownGroup
                clusterChanged = True
        for j in range(k):
            '''
            遍历完所有元素后更新K个质心
            clusterAssment[:, 1] == j #判断每个元素是否属于j组，是的话就返回True,否则返回False
            np.nonzero(clusterAssment[:, 1] == j)[0] #返回一个有两个元素的tuple,第一个元素是这个数组(元素是布尔值的形式)中元素是True的下标
            dataSet[np.nonzero(clusterAssment[:, 1] == j)[0]] #得到属于某个组的全部元素
            np.mean(pointsInCluster, axis=0) #计算每一个簇中所有元素的均值作为各自簇的新的质心
            '''
            pointsInCluster = dataSet[np.nonzero(clusterAssment[:, 1] == j)[0]]
            centroids[j, :] = np.mean(pointsInCluster, axis=0)
    return centroids,clusterAssment

def showCluster(dataSet, k, centroids, clusterAssment):
    '''
    可视化
    '''
    numSamples, dim = dataSet.shape
    if dim != 2:
        print "Sorry! I can not draw because the dimension of your data is not 2!"
        return 1
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print "Sorry! Your k is too large! please contact Zouxy"
        return 1
    for i in xrange(numSamples):
        #不同的组显示不同的颜色("o"表示形状为圆形，后面表示不同的颜色)
        markIndex = int(clusterAssment[i, 1])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    for i in range(k):
        # 标识出质心("D"表示形状为菱形，后面表示不同的颜色)
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.show()

if __name__ == "__main__":
    '''
    需求是给一个数据集，根据各个元素之间的关系把具有相似属性的元素归为一类，就是把数据集根据不同的分类要求分成不同的类。
    '''
    dataSet = []
    f = open("数据集在很多博客里面可以找到，在此就不贴出了",'r')
    for line in f.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])
    dataSet = np.array(dataSet)
    k = 4
    centroids, clusterAssment = kmeans(dataSet, k)
    showCluster(dataSet, k, centroids, clusterAssment)

结果展示

看起来还不错

jieguo

算法评估

1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献中，是根据方差分析理论，应用混合 F统计量来确定最佳分类数，并应用了模糊划分熵来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的 RPCL 算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。
2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。
3. 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

应用场景

分析一个公司的客户分类，这样可以对不同的客户使用不同的商业策略，或是电子商务中分析商品相似度，归类商品，从而可以使用一些不同的销售策略，等等。