K-means

阅读数: 10000次 2022-01-29

K-means及其作业

K–means

介绍

K–means又称K–均值算法，聚类与分类算法的最大区别在于, 分类的目标类别已知(监督学习), 而聚类的目标类别是未知的(无监督学习)。K-Means算法(K-均值算法)就是无监督算法之一，主要用于样本的聚类。其思想很简单，对于给定的样本集，按照样本与聚类中心之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连接在一起,让簇间的距离尽量的大。

算法描述

步骤描述

1）数据准备:需要数值型数据类计算距离, 也可以将标称型数据映射为二值型数据再用于距离计算。

2）对于未聚类数据集，首先随机初始化 K 个（代表拟聚类簇个数）中心点，如图红色五角星所示。

3）每一个样本按照距离自身最近的中心点进行聚类(计算距离)，等效于通过两中心点连线的中垂线划分区域。

4）依据上次聚类结果，移动中心点到个簇的质心位置(新的质心的位置为新簇内点的x和y分别的的平均值)，并将此质心作为新的中心点

5）反复迭代，直至中心点的变化满足收敛条件（变化很小或几乎不变化），最终得到聚类结果。

距离计算方法

这里的距离指的是平面上两个点的直线距离。常用的距离计算公式有：

闵可夫斯基距离
欧几里得距离
曼哈顿距离
切比雪夫距离
马氏距离
余弦相似度
皮尔逊相关系数
汉明距离
杰卡德相似系数
编辑距离
DTW 距离
KL 散度

K值选择

1）手肘法

在介绍之前我们先了解一个概念:SSE(sum of the squared errors，误差平方和)

手肘法的核心思想：

随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。
当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。

2）轮廓系数

使用轮廓系数(silhouette coefficient)来确定，选择使系数较大所对应的k值

优缺点

优点:

属于无监督学习，无须准备训练集；
原理简单，实现起来较为容易；
结果可解释性较好。

缺点

聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果，这也是为什么要进行特征检查来决定数据集的聚类数目了；
可能收敛到局部最小值, 在大规模数据集上收敛较慢；
对于异常点、离群点敏感。

本次运用的公式

更新质心公式

就是新的质心的值等于当前该质心所属簇的所有点的平均值
$$
c_j=(1/N_j)\sum_{i=1}^{N_j}x_i,y_i
$$

传统K-means改进

在学习了传统K-means算法的基础上,我们清楚了K-means的局限性,因此我们将要说一下K-Means的优化变体方法。这其中包括初始化优化K-Means++, 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

K-means++

在学习K-means算法时我们提到，k个初始化的质心的位置选择对最后的聚类结果和运行时间都有很大的影响，因此需要选择合适的k个质心。如果仅仅是完全随机的选择，有可能导致算法收敛很慢。K-Means++算法就是对K-Means随机初始化质心的方法的优化。

elkan K-means

在传统的K-Means算法中，我们在每轮迭代时，要计算所有的样本点到所有的质心的距离，这样会比较的耗时。那么，对于距离的计算有没有能够简化的地方呢？elkan K-Means算法就是从这块入手加以改进。它的目标是减少不必要的距离的计算。

Mini Batch K-means

在统的K-Means算法中，要计算所有的样本点到所有的质心的距离。如果样本量非常大，比如达到10万以上，特征有100以上，此时用传统的K-Means算法非常的耗时，就算加上elkan K-Means优化也依旧。在大数据时代，这样的场景越来越多。此时Mini Batch K-Means应运而生。

顾名思义，Mini Batch，也就是用样本集中的一部分的样本来做传统的K-Means，这样可以避免样本量太大时的计算难题，算法收敛速度大大加快。当然此时的代价就是我们的聚类的精确度也会有一些降低。一般来说这个降低的幅度在可以接受的范围之内。

**注意:**此部分为扩展内容,如果你想真正的去优化你的算法,更详细的优化步骤你可以去刘建平Pinard-K-Means聚类算法原理或者是百度一下。

代码：

import numpy
import random
import matplotlib.pyplot as plt


def findCentroids(data_get, k):    # 随机获取k个质心
    return random.sample(data_get, k)


def calculateDistance(vecA, vecB):    # 计算向量vecA和向量vecB之间的欧氏距离
    return numpy.sqrt(numpy.sum(numpy.square(vecA - vecB)))


def minDistance(data_get, centroidList):
    # 计算data_get中的元素与centroidList中k个聚类中心的欧式距离，找出距离最小的
    # 将该元素加入相应的聚类中
    clusterDict = dict()  # 用字典存储聚类结果
    for element in data_get:
        vecA = numpy.array(element)  # 转换成数组形式
        flag = 0  # 元素分类标记，记录与相应聚类距离最近的那个类
        minDis = float("inf")  # 初始化为最大值

        for i in range(len(centroidList)):
            vecB = numpy.array(centroidList[i])
            distance = calculateDistance(vecA, vecB)  # 两向量间的欧式距离
            if distance < minDis:
                minDis = distance
                flag = i  # 保存与当前item距离最近的那个聚类的标记

        if flag not in clusterDict.keys():  # 簇标记不存在，进行初始化
            clusterDict[flag] = list()
        clusterDict[flag].append(element)  # 加入相应的类中

    return clusterDict  # 返回新的聚类结果


def getCentroids(clusterDict):
    centroidList = list()
    for key in clusterDict.keys():
        centroid = numpy.mean(numpy.array(clusterDict[key]), axis=0)  # 求聚类中心即求解每列的均值
        centroidList.append(centroid)

    return numpy.array(centroidList).tolist()


def calculate_Var(clusterDict, centroidList):
    # 计算聚类间的均方误差
    # 将类中各个向量与聚类中心的距离进行累加求和

    sum = 0.0
    for key in clusterDict.keys():
        vecA = numpy.array(centroidList[key])
        distance = 0.0
        for item in clusterDict[key]:
            vecB = numpy.array(item)
            distance += calculateDistance(vecA, vecB)
        sum += distance
    return sum


def showCluster(centroidList, clusterDict):
    # 画聚类结果
    colorMark = ['or', 'ob', 'og', 'ok', 'oy', 'ow']  # 元素标记
    centroidMark = ['dr', 'db', 'dg', 'dk', 'dy', 'dw']  # 聚类中心标记
    for key in clusterDict.keys():
        plt.plot(centroidList[key][0], centroidList[key][1], centroidMark[key], markersize=12)  # 画聚类中心
        for item in clusterDict[key]:
            plt.plot(item[0], item[1], colorMark[key])  # 画类下的点
    plt.show()


data = [[0.0, 0.0], [3.0, 8.0], [2.0, 2.0], [1.0, 1.0], [5.0, 3.0],
        [4.0, 8.0], [6.0, 3.0], [5.0, 4.0], [6.0, 4.0], [7.0, 5.0]]


if __name__ == '__main__':

    centroidList = findCentroids(data, 3)  # 随机获取3个聚类中心
    clusterDict = minDistance(data, centroidList)  # 第一次聚类迭代
    newVar = calculate_Var(clusterDict, centroidList)  # 计算均方误差值，通过新旧均方误差来获得迭代终止条件
    oldVar = -0.0001  # 初始化均方误差

    print('***** 第1次迭代 *****')
    for key in clusterDict.keys():
        print('聚类中心: ', centroidList[key])
        print('对应聚类: ',clusterDict[key])
    print('平均均方误差: ', newVar)
    showCluster(centroidList, clusterDict)  # 展示聚类结果

    k = 2
    while abs(newVar - oldVar) >= 0.0001:  # 当连续两次聚类结果差距小于0.0001时，迭代结束
        centroidList = getCentroids(clusterDict)  # 获得新的聚类中心
        clusterDict = minDistance(data, centroidList)  # 新的聚类结果
        oldVar = newVar
        newVar = calculate_Var(clusterDict, centroidList)

        print('***** 第%d次迭代 *****' % k)

        for key in clusterDict.keys():
            print('聚类中心: ', centroidList[key])
            print('对应聚类: ', clusterDict[key])
        print('平均均方误差: ', newVar)
        showCluster(centroidList, clusterDict)  # 展示聚类结果
        k += 1

作业

对代码进行补充

完整代码如下：

from random import uniform
from math import sqrt
import matplotlib.pyplot as plt
#创建一个数据集。
#注意：本方法创建的数据集每次运行结果都不相同
m = 60 #数据个数
data = [[],[]] #[[存储 x 轴数据],[存储 y 轴数据]]
for i in range(m):
    if i < m/3: 
        data[0].append(uniform(1,5))#随机设定
        data[1].append(uniform(1,5))
    elif i < 2*m/3:
        data[0].append(uniform(6,10))
        data[1].append(uniform(1,5))
    else:
        data[0].append(uniform(3,8))
        data[1].append(uniform(5,10))
print(data) #输出初始化的数据
#将创建的数据集画成散点图
plt.scatter(data[0],data[1])
plt.xlim(0,11)     #设置x轴坐标范围
plt.ylim(0,11)     #设置y轴坐标范围
plt.show()

#定义欧几里得距离计算1,2距离
def distEuclid(x1,y1,x2,y2):

    return sqrt((x1-x2)**2+(y1-y2)**2)

cent0 = [uniform(2,9),uniform(2,9)] #定义 K=3 个质心，随机赋值
cent1 = [uniform(2,9),uniform(2,9)] #[x,y]
cent2 = [uniform(2,9),uniform(2,9)]
mark = [] #标记列表
dist = [[],[],[]]#各质心到所有点的距离列表
#核心
for n in range(50):                                           #跌代次数
    #计算K个质心到所有点data的距离
    for i in range(m):
        dist[0].append(distEuclid(cent0[0],cent0[1],data[0][i],data[1][i]))
        dist[1].append(distEuclid(cent1[0],cent1[1],data[0][i],data[1][i]))
        dist[2].append(distEuclid(cent2[0],cent2[1],data[0][i],data[1][i]))
    #对数据进行整理
    sum0_x = sum0_y = sum1_x = sum1_y = sum2_x = sum2_y = 0
    number0 = number1 = number2 = 0
    #按距离分类
    for i in range(m):
        if dist[0][i]<dist[1][i] and dist[0][i]<dist[2][i]:
            mark.append(0)                                    #标记不同的质心
            sum0_x += data[0][i]
            sum0_y += data[1][i]
            number0 += 1
        elif dist[1][i]<dist[0][i] and dist[1][i]<dist[2][i]:
            mark.append(1)                                    #标记不同的质心
            sum1_x += data[0][i]
            sum1_y += data[1][i]
            number1 += 1
        elif dist[2][i]<dist[0][i] and dist[2][i]<dist[1][i]:
            mark.append(2)                                    #标记不同的质心
            sum2_x += data[0][i]
            sum2_y += data[1][i]
            number2 += 1    
    #按公式更新质心
    cent0 = [sum0_x/number0,sum0_y/number0]
    cent1 = [sum1_x/number1,sum1_y/number1]
    cent2 = [sum2_x/number2,sum2_y/number2]
#画图
for i in range(m):   #不同的质心用不同的颜色画出
    if mark[i] == 0:
        plt.scatter(data[0][i],data[1][i],color='red')  
    if mark[i] == 1:
        plt.scatter(data[0][i],data[1][i],color='blue')
    if mark[i] == 2:
        plt.scatter(data[0][i],data[1][i],color='green')     
plt.scatter(cent0[0],cent0[1],marker='*',color='red')  #画出最后更新的质心cent0
plt.scatter(cent1[0],cent1[1],marker='*',color='blue') #画出最后更新的质心cent1
plt.scatter(cent2[0],cent2[1],marker='*',color='green') #画出最后更新的质心cent2
plt.xlim(0,11) #规定x轴坐标范围
plt.ylim(0,11) #规定y轴坐标范围
plt.show()
#上述代码数据选择是随机生成的，每次运行结果是不同的，分类结果有好有坏。

理论参考链接：https://stoic-shaw-839c64.netlify.app/ai/knn/