热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

K-Means算法原理

原理给定样本集,k-means算法得到聚类,使得下面平方误差最小其中表示聚类的中心点。实现上式最小化是一个NP难问题,实际上采用EM算法可以求得近似解。算法伪代码如下输入:,聚
原理

给定样本集,k-means算法得到聚类,使得下面平方误差最小

其中表示聚类的中心点。

实现

上式最小化是一个NP难问题,实际上采用EM算法可以求得近似解。算法伪代码如下

输入:,聚类数量k

从D中随机选择k个样本点作为k个聚类的中心
repeat
    循环所有样本点,把样本点划分到最近的聚类中:arg min||x - ui||
    更新聚类中心:ui = (∑x) / n
util 聚类中心不再变化

输出:

实例

sklearn已经实现上述算法,测试代码如下

import pandas as pd
from matplotlib import pyplot as plt
from sklearn.cluster import k_means

# 1、读取数据文件
df = pd.read_csv("data.csv", header=0)
df.head()

# 2、原始文件画图
X = df['x']
y = df['y']
plt.scatter(X, y)
plt.show()

# 3、k-means分为三类
model = k_means(df, n_clusters=3)
print(model)

# 4、分类后画图
cluster_centers = model[0]
cluster_labels = model[1]
plt.scatter(X, y, c=cluster_labels)
for center in cluster_centers:
    plt.scatter(center[0], center[1], marker="p", edgecolors="red")
plt.show()

k_means计算得到的model包含三部分

(1)各个聚类的中心

(2)样本点的类别数组

(3)所有样本点到各自聚类中心的距离平方和

运行结果如下

k值的确定

当我们不知道样本有几类时,可以采用以下两种方式确定最优k值

1、肘部法则

对于上面k_means方法返回值得第三部分,样本点到聚类中心点的距离平方和s。很明显,k = m时(m表示样本数量),s = 0,s随着k的增加而减小,s减小幅度随着k增加而减小。我们找到s变化率改变最大时对应的k值(即肘部)作为最优k值。代码如下

# 肘部法则
index = [] # 横坐标数组
inertia = [] # 纵坐标数组

# K 从 1~ 10 聚类
for i in range(9):
    model = k_means(df, n_clusters=i + 1)
    index.append(i + 1)
    inertia.append(model[2])

# 绘制折线图
plt.plot(index, inertia, "-o")
plt.show()

运行结果如下,显然k = 3是最优值

2、轮廓系数

假设我们已经通过一定算法,将待分类数据进行了聚类,得到k个簇 。对于其中的一个点 i 来说:

a(i) = i向量到它所属簇中其它点的距离平均值

b(i) = i向量到所有其他簇的点的平均距离的最小值

那么点i的轮廓系数就为:

可见轮廓系数的值是介于 [-1,1] ,越趋近于1代表内聚度和分离度都相对较优。将所有点的轮廓系数求平均,就是该聚类结果总的轮廓系数。

代码实现如下

#轮廓系数
from sklearn.metrics import silhouette_score # 导入轮廓系数计算模块

index2 = [] # 横坐标
silhouette = [] # 轮廓系数列表

# K 从 2 ~ 10 聚类
for i in range(8):
    model = k_means(df, n_clusters=i + 2)
    index2.append(i + 2)
    silhouette.append(silhouette_score(df, model[1]))

print(silhouette) # 输出不同聚类下的轮廓系数

# 绘制折线图
plt.plot(index2, silhouette, "-o")
plt.show()

实验结果如下,显然k = 3是最优值。


推荐阅读
  • 超级简单加解密工具的方案和功能
    本文介绍了一个超级简单的加解密工具的方案和功能。该工具可以读取文件头,并根据特定长度进行加密,加密后将加密部分写入源文件。同时,该工具也支持解密操作。加密和解密过程是可逆的。本文还提到了一些相关的功能和使用方法,并给出了Python代码示例。 ... [详细]
  • 不同优化算法的比较分析及实验验证
    本文介绍了神经网络优化中常用的优化方法,包括学习率调整和梯度估计修正,并通过实验验证了不同优化算法的效果。实验结果表明,Adam算法在综合考虑学习率调整和梯度估计修正方面表现较好。该研究对于优化神经网络的训练过程具有指导意义。 ... [详细]
  • 本文介绍了Python对Excel文件的读取方法,包括模块的安装和使用。通过安装xlrd、xlwt、xlutils、pyExcelerator等模块,可以实现对Excel文件的读取和处理。具体的读取方法包括打开excel文件、抓取所有sheet的名称、定位到指定的表单等。本文提供了两种定位表单的方式,并给出了相应的代码示例。 ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • sklearn数据集库中的常用数据集类型介绍
    本文介绍了sklearn数据集库中常用的数据集类型,包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集,包含了波士顿506处房屋的13种不同特征以及房屋价格,适用于回归任务。 ... [详细]
  • Python瓦片图下载、合并、绘图、标记的代码示例
    本文提供了Python瓦片图下载、合并、绘图、标记的代码示例,包括下载代码、多线程下载、图像处理等功能。通过参考geoserver,使用PIL、cv2、numpy、gdal、osr等库实现了瓦片图的下载、合并、绘图和标记功能。代码示例详细介绍了各个功能的实现方法,供读者参考使用。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 怎么在PHP项目中实现一个HTTP断点续传功能发布时间:2021-01-1916:26:06来源:亿速云阅读:96作者:Le ... [详细]
  • Day2列表、字典、集合操作详解
    本文详细介绍了列表、字典、集合的操作方法,包括定义列表、访问列表元素、字符串操作、字典操作、集合操作、文件操作、字符编码与转码等内容。内容详实,适合初学者参考。 ... [详细]
  • 欢乐的票圈重构之旅——RecyclerView的头尾布局增加
    项目重构的Git地址:https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集:http:www.jianshu.comno ... [详细]
  • 十大经典排序算法动图演示+Python实现
    本文介绍了十大经典排序算法的原理、演示和Python实现。排序算法分为内部排序和外部排序,常见的内部排序算法有插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。文章还解释了时间复杂度和稳定性的概念,并提供了相关的名词解释。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • 1,关于死锁的理解死锁,我们可以简单的理解为是两个线程同时使用同一资源,两个线程又得不到相应的资源而造成永无相互等待的情况。 2,模拟死锁背景介绍:我们创建一个朋友 ... [详细]
  • 基于dlib的人脸68特征点提取(眨眼张嘴检测)python版本
    文章目录引言开发环境和库流程设计张嘴和闭眼的检测引言(1)利用Dlib官方训练好的模型“shape_predictor_68_face_landmarks.dat”进行68个点标定 ... [详细]
  • 本文介绍了一种在PHP中对二维数组根据某个字段进行排序的方法,以年龄字段为例,按照倒序的方式进行排序,并给出了具体的代码实现。 ... [详细]
author-avatar
何cecilio
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有