K-Means

简介

K-Means算法是无监督的聚类算法，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

输入输出

K-Means是根据样本之间距离的大小来判断是否属于同一个簇的，所以样本必须能够计算距离，即必须包含坐标信息。将样本集划分为K个簇，即参数为K。

输入依赖： 包含坐标信息的样本集、要划分为K个簇的K值，输出：给样本集标注每个样本分别属于哪一个K簇

思想

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

执行过程

1.（随机）选择K个聚类的初始中心；

2.对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代n次；

3.每次迭代过程中，利用均值等方法更新各个聚类的中心点(质心)；

4.对K个聚类中心，利用2,3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束。

优点 & 缺点

优点

1. 原理比较简单，实现也是很容易，收敛速度快。
2. 聚类效果较优。
3. 算法的可解释度比较强。
4. 主要需要调参的参数仅仅是簇数k。

缺点

1. K值的选取不好把握
2. 对于不是凸的数据集比较难收敛
3. 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。
4. 最终结果和初始点的选择有关，容易陷入局部最优。
5. 对噪音和异常点比较的敏感。

代码注释

# 这里简单的计算了一个欧氏距离
# @param {*} vecA 节点A
# @param {*} vecB 节点B
# @returns 两个向量之间的距离
def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2))) 

# 构建聚簇中心，取k个随机质心
def randCent(dataSet, k):
    n = shape(dataSet)[1]
    centroids = mat(zeros((k,n)))   # 每个质心有n个坐标值，总共要k个质心
    for j in range(n):
        minJ = min(dataSet[:,j])
        maxJ = max(dataSet[:,j])
        rangeJ = float(maxJ - minJ)
        centroids[:,j] = minJ + rangeJ * random.rand(k, 1)
    return centroids

# k-means 聚类算法
# @param {*} dataSet          数据集
# @param {*} k                将数据集分为k个簇
# @param {*} distMeans        节点之间的距离计算方法
# @param {*} createCent       创建簇中心的算法
# @returns randCent           质心坐标
# @returns clusterAssment     一个二维数组 包含每个簇的每个节点
def kMeans(dataSet, k, distMeans =distEclud, createCent = randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))    # 用于存放该样本属于哪类及质心距离
    # clusterAssment第一列存放该数据所属的中心点，第二列是该数据到中心点的距离
    centroids = createCent(dataSet, k)
    clusterChanged = True   # 用来判断聚类是否已经收敛
    while clusterChanged:
        clusterChanged = False;
        for i in range(m):  # 把每一个数据点划分到离它最近的中心点
            minDist = inf; minIndex = -1;
            for j in range(k):
                distJI = distMeans(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; minIndex = j  # 如果第i个数据点到第j个中心点更近，则将i归属为j
            if clusterAssment[i,0] != minIndex: clusterChanged = True;  # 如果分配发生变化，则需要继续迭代
            clusterAssment[i,:] = minIndex,minDist**2   # 并将第i个数据点的分配情况存入字典
        print centroids
        for cent in range(k):   # 重新计算中心点
            ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]   # 去第一列等于cent的所有列
            centroids[cent,:] = mean(ptsInClust, axis = 0)  # 算出这些数据的中心点
    return centroids, clusterAssment

小结

K-Means是一个简单的聚类算法，仍有一定的问题，例如对初始点，异常点较为敏感，同时对于抽象的大数据集不易给出K值。

参考 & 引用

https://blog.csdn.net/weixin_42029738/article/details/81978038

https://blog.csdn.net/weixin_42029738/article/details/81978038