欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

机器学习之K-means算法(小白入门级别)

程序员文章站 2022-06-22 08:37:29
K-means算法算法流程描述算法流程K值的选择质心的初始化距离的度量新质心的计算是否停止K-meanspython实现代码各方法的解释代码数据集介绍结果分析聚类结果结论改进二分K-meansK-means++后处理降低SSE算法流程描述  K-means算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。  其算法思想大致为:先从样本集中随机选取 k个样本作为簇中心,并计算所有样本...

算法流程描述

  K-means算法又名k均值算法,K-means算法中的k表示的是聚类为k个簇,means代表取每一个聚类中数据值的均值作为该簇的中心,或者称为质心,即用每一个的类的质心对该簇进行描述。
  其算法思想大致为:先从样本集中随机选取 k个样本作为簇中心,并计算所有样本与这 k个“簇中心”的距离,对于每一个样本,将其划分到与其距离最近的“簇中心”所在的簇中,对于新的簇计算各个簇的新的“簇中心”。
  根据以上描述,我们大致可以猜测到实现K-means算法的主要四点:
  (1)簇个数 k 的选择
  (2)各个样本点到“簇中心”的距离
  (3)根据新划分的簇,更新“簇中心”
  (4)重复上述2、3过程,直至"簇中心"没有移动

算法流程


基本K均值算法


1.选择K个点作为初始质心。
2.repeat
3.  将每个点指派到最近的质心,形成K个簇。
4.   重新计算每个簇的质心。
5. until 质心不再发生变化


K值的选择

  K值的选择影响聚类效果,在进行离群点检测时,对象是否被认为是离群点可能依赖于聚类的个数。K 的选择一般是按照实际需求进行决定,或在实现算法时直接给定 K 值。

质心的初始化

  选择恰当的初始质心是基本K均值过程的关键步骤,常见的方法是随机选取,但是这样簇的质量往往很差,可能只能得到局部最优。
  处理选取质心问题的一种常用技术是:多次运行,每次使用一组不同的随机初始质心,然后选取具有最小SSE的簇集。还有其他更加有效的技术,比如K-means++、二分K-means、使用后处理来“修补”所产生的簇集等,在文章最后的结论中有讲解。
  在下面的实现中初始的质心是随机选取的。

距离的度量

  将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略,在欧式空间中采用的是欧式距离,在处理文档中采用的是余弦相似度函数,有时候也采用曼哈顿距离作为度量,不同的情况实用的度量公式是不同的。
  欧氏距离:机器学习之K-means算法(小白入门级别)
  曼哈顿距离:机器学习之K-means算法(小白入门级别)
  余弦相似度函数:机器学习之K-means算法(小白入门级别)

新质心的计算

  对于分类后的产生的k个簇,分别计算到簇内其他点距离均值最小的点作为质心(对于拥有坐标的簇可以计算每个簇坐标的均值作为质心)。经过这一步会产生K个质心,继续作为上一步的聚类中心。

是否停止K-means

  当质心不再改变,或给定loop最大次数loopLimit时结束算法。

python实现代码

各方法的解释

  calcDis函数用于计算欧拉距离,classify函数用于计算新的质心,kmeans函数用于kmeans分类,loadDataSet函数用于加载数据集。最初的k值为随机确定。

代码

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

# 计算欧拉距离
def calcDis(dataSet, centroids, k):
    clalist = []
    for data in dataSet:
        diff = np.tile(data, (k, 1)) - centroids  # 相减   (np.tile(data,(k,1))就是把data先沿x轴复制1倍,即没有复制,比如是 [0,1,2]。
        # 再把结果沿y方向复制k倍得到array([[0,1,2],[0,1,2],...]))
        squaredDiff = diff ** 2  # 平方
        squaredDist = np.sum(squaredDiff, axis=1)  # 和  (当axis为1时,是压缩列,即将每一行的元素相加,将矩阵压缩为一列)
        distance = squaredDist ** 0.5  # 开根号
        clalist.append(distance)
    clalist = np.array(clalist)  # 返回一个每个点到质点的距离len(dateSet)*k的数组
    return clalist

# 计算质心
def classify(dataSet, centroids, k):
    # 计算样本到质心的距离
    clalist = calcDis(dataSet, centroids, k)
    # 分组并计算新的质心
    minDistIndices = np.argmin(clalist, axis=1)  # axis=1 表示求出每行的最小值的下标
    newCentroids = pd.DataFrame(dataSet).groupby(minDistIndices).mean()  # DataFramte(dataSet)对DataSet分组,groupby(min)按照min进行统计分类,mean()对分类结果求均值
    newCentroids = newCentroids.values

    # 计算变化量
    changed = newCentroids - centroids
    # 返回变化量和新的质心
    return changed, newCentroids

# 使用k-means分类
def kmeans(dataSet, k):
    # 随机取质心,取k个
    centroids = random.sample(dataSet, k)

    # 更新质心 直到变化量全为0
    changed, newCentroids = classify(dataSet, centroids, k)
    while np.any(changed != 0):
        changed, newCentroids = classify(dataSet, newCentroids, k)

    centroids = sorted(newCentroids.tolist())  # tolist()将矩阵转换成列表 sorted()排序

    # 根据质心计算每个集群
    cluster = []
    clalist = calcDis(dataSet, centroids, k)  # 调用欧拉距离
    minDistIndices = np.argmin(clalist, axis=1)
    for i in range(k):
        cluster.append([])
    for i, j in enumerate(minDistIndices):  # enymerate()可同时遍历索引和遍历元素
        cluster[j].append(dataSet[i])
    # 返回质心和集群
    return centroids, cluster

# 加载数据集
def loadDatadet(infile,k):
    f=open(infile,'r')
    sourceInLine=f.readlines()
    dataset=[]
    for line in sourceInLine:
        temp1=line.strip('\n')
        temp2=temp1.split(' ')
        dataset.append(temp2)
    for i in range(0, len(dataset)):
        for j in range(k):
            dataset[i].append(float(dataset[i][j]))
        del(dataset[i][0:k])
    return dataset

if __name__ == '__main__':
    dataset = loadDatadet('./西瓜数据集', 2)
    centroids, cluster = kmeans(dataset, 3)
    print('质心为:%s' % centroids)
    print('集群为:%s' % cluster)
    for i in range(len(cluster[0])):
        plt.scatter(cluster[0][i][0], cluster[0][i][1], marker='o', color='yellow', s=40, label='集群1')
        # 记号形状、颜色、点的大小、设置标签
    for i in range(len(cluster[1])):
        plt.scatter(cluster[1][i][0], cluster[1][i][1], marker='o', color='blue', s=40, label='集群1')
        # 记号形状、颜色、点的大小、设置标签
    for i in range(len(cluster[2])):
        plt.scatter(cluster[2][i][0], cluster[2][i][1], marker='o', color='green', s=40, label='集群1')
        # 记号形状、颜色、点的大小、设置标签
    for j in range(len(centroids)):
        plt.scatter(centroids[j][0], centroids[j][1], marker='x', color='red', s=50, label='质心')
    plt.show()

数据集介绍

  使用的数据是西瓜数据集4.0,来自于西瓜书。第一列是密度,第二列是含糖量,两个变量都是连续变量,共计有30条记录。已经归一化到 [0,1] ,不用进行标准化处理,且无缺失项,异常值检测省略,直接作为模型输入即可。
机器学习之K-means算法(小白入门级别)

结果分析

聚类结果

  经过测试,得出聚类结果如下图:
机器学习之K-means算法(小白入门级别)

K=3聚类结果

  如果将聚类K值改为2和4,得到的结果如下所示:
机器学习之K-means算法(小白入门级别)

K=2聚类结果

机器学习之K-means算法(小白入门级别)

K=4聚类结果

  多次执行后,由于初始质心为随机选择,会造成最终聚类效果不同。
机器学习之K-means算法(小白入门级别)

K=3另一聚类结果

结论

  1. 聚类是一种无监督的学习方法。聚类区别于分类,即事先不知道要寻找的内容,没有预先设定好的目标变量。
  2. 聚类将数据点归到多个簇中,其中相似的数据点归为同一簇,而不相似的点归为不同的簇。相似度的计算方法(距离计算方法)有很多,具体的应用选择合适的相似度计算方法。
  3. K-means聚类算法,是一种广泛使用的聚类算法,其中k是需要指定的参数,即需要创建的簇的数目,K-means算法中的k个簇的质心可以通过随机的方式获得,但是这些点需要位于数据范围内。在算法中,计算每个点到质心得距离,选择距离最小的质心对应的簇作为该数据点的划分,然后再基于该分配过程后更新簇的质心。重复上述过程,直至各个簇的质心不再变化为止。
  4. K-means算法虽然有效,但是容易受到初始簇质心的情况而影响,有可能陷入局部最优解。为了解决这个问题,可以使用另外一种称为二分K-means的聚类算法。

改进

二分K-means

  二分K-means算法首先将所有数据点分为一个簇;然后使用K-means(k=2)对其进行划分;下一次迭代时,选择使得SSE(误差平方和)下降程度最大的簇进行划分;重复该过程,直至簇的个数达到指定的数目为止。算法流程如下:


二分K均值和初始化


1.初始化簇表,使之包含由所有点组成的簇。
2.repeat
3.  从簇表中取出一个簇。
4.  {对选定的簇进行多次“二分”实验。}
5.  for i=1 to 实验次数 do
6.    使用基本K均值,二分选定的簇。
7.  end for
8.  从二分实验中选择具有最小总SSE的两个簇。
9.  将这两个簇添加到簇表中。
10.until 簇表中包含K个簇。


  实验表明,二分K-means算法的聚类效果要好于普通的K-means聚类算法。通过记录K均值二份簇所产生的簇类序列,我们还可以使用二分K均值产生层次聚类。

K-means++

  K-means++的详解可见:https://blog.csdn.net/a19990412/article/details/89000149

后处理降低SSE

  一种明显降低SSE(这里的误差可以是欧式距离)的方法是找出更多的簇,即使用较大的K。然而在很多情况下,我们希望降低SSE,但是不想增加K的个数。这时我们可以选择采用多种技术来“修补”结果簇。策略是关注每一个簇,因为总的SSE不过是每个簇的SSE之和。一种常用的方法是交替地使用簇分裂和簇合并,使用这种方法,常常可以避开局部极小,并且仍然可以得到期望个数的簇。
  通过增加簇的个数来降低总SSE的两种策略:

  1. 分裂一个簇:通常选择具有最大SSE的簇,也可以分列在特定属性上具有最大标准差的簇。
  2. 引进一个新的质心:通常选择离所有质心最远的点。另一种方法是从所有的点或者具有最高SSE的点中随机地选择。
      减少簇的个数,并且试图最小化总SSE的增长的两种策略:
  3. 拆散一个簇:通常选择使总SSE增加最少的簇,删除簇的质心,并将簇中的点重新指派到其他的簇。
  4. 合并两个簇:通常选择质心最近的两个簇,显然上面的方法更好一些。(这两种方法在层次聚类中也有使用,称为志新方法和Ward方法。)

优点与缺点

基本K-means算法的缺点很明显,有如下几点:

  1. 受离群点影响大。当存在离群点时,结果簇的质心可能不如没有离群点时那样有代表性,并且导致SSE也比较高。解决方法:预处理时识别并删除离群点。
  2. 随机选择初始质心造成的簇的质量下降。解决方法:改进中的方法。
  3. 如果所有的点在指派步骤都未分到某一个簇中,就会得到空簇。解决办法:采用某种策略选择一个替补质心,如选择一个距离当前任何质心最远的点,或者从具有最大SSE的簇中选择一个替补质心。
  4. 不适用于所有的数据类型。它不能处理非球形、不同尺寸和不同密度的簇。

优点有:

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

本文地址:https://blog.csdn.net/weixin_43903564/article/details/107232617