热门标签 | 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是最优值。


推荐阅读
  • 本文深入探讨了HTTP请求和响应对象的使用,详细介绍了如何通过响应对象向客户端发送数据、处理中文乱码问题以及常见的HTTP状态码。此外,还涵盖了文件下载、请求重定向、请求转发等高级功能。 ... [详细]
  • 本文详细探讨了HTML表单中GET和POST请求的区别,包括它们的工作原理、数据传输方式、安全性及适用场景。同时,通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]
  • Python处理Word文档的高效技巧
    本文详细介绍了如何使用Python处理Word文档,涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]
  • 利用决策树预测NBA比赛胜负的Python数据挖掘实践
    本文通过使用2013-14赛季NBA赛程与结果数据集以及2013年NBA排名数据,结合《Python数据挖掘入门与实践》一书中的方法,展示如何应用决策树算法进行比赛胜负预测。我们将详细讲解数据预处理、特征工程及模型评估等关键步骤。 ... [详细]
  • 本文将探讨2015年RCTF竞赛中的一道PWN题目——shaxian,重点分析其利用Fastbin和堆溢出的技巧。通过详细解析代码流程和漏洞利用过程,帮助读者理解此类题目的破解方法。 ... [详细]
  • 理解与应用:独热编码(One-Hot Encoding)
    本文详细介绍了独热编码(One-Hot Encoding)与哑变量编码(Dummy Encoding)两种方法,用于将分类变量转换为数值形式,以便于机器学习算法处理。文章不仅解释了这两种编码方式的基本原理,还探讨了它们在实际应用中的差异及选择依据。 ... [详细]
  • addcslashes—以C语言风格使用反斜线转义字符串中的字符addslashes—使用反斜线引用字符串bin2hex—函数把包含数据的二进制字符串转换为十六进制值chop—rt ... [详细]
  • Python并行处理:提升数据处理速度的方法与实践
    本文探讨了如何利用Python进行数据处理的并行化,通过介绍Numba、多进程处理以及Pandas DataFrame上的并行操作等技术,旨在帮助开发者有效提高数据处理效率。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 深入理解Redis的数据结构与对象系统
    本文详细探讨了Redis中的数据结构和对象系统的实现,包括字符串、列表、集合、哈希表和有序集合等五种核心对象类型,以及它们所使用的底层数据结构。通过分析源码和相关文献,帮助读者更好地理解Redis的设计原理。 ... [详细]
  • ABBYY FineReader:高效PDF转换、精准OCR识别与文档对比工具
    在处理PDF转换和OCR识别时,您是否遇到过格式混乱、识别率低或图表无法正常识别的问题?ABBYY FineReader以其强大的功能和高精度的识别技术,完美解决这些问题,帮助您轻松找到最终版文档。 ... [详细]
  • Python 工具推荐 | PyHubWeekly 第二十一期:提升命令行体验的五大工具
    本期 PyHubWeekly 为大家精选了 GitHub 上五个优秀的 Python 工具,涵盖金融数据可视化、终端美化、国际化支持、图像增强和远程 Shell 环境配置。欢迎关注并参与项目。 ... [详细]
  • 本文旨在探讨如何利用决策树算法实现对男女性别的分类。通过引入信息熵和信息增益的概念,结合具体的数据集,详细介绍了决策树的构建过程,并展示了其在实际应用中的效果。 ... [详细]
  • 利用R语言进行股票价格数据的线性回归分析
    本文介绍了如何使用R语言对Excel中的股票价格数据集执行线性回归分析。通过具体的代码示例,展示了数据的导入、处理及模型构建的过程。 ... [详细]
  • 主板市盈率、市净率及股息率的自动化抓取
    本文介绍了如何通过Python脚本自动从中国指数有限公司网站抓取主板的市盈率、市净率和股息率等关键财务指标,并将这些数据存储到CSV文件中。涉及的技术包括网页解析、正则表达式以及异常处理。 ... [详细]
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社区 版权所有