python实现聚类算法原理
作者:FishBear_move_on 发布时间:2022-07-23 23:42:33
本文主要内容:
聚类算法的特点
聚类算法样本间的属性(包括,有序属性、无序属性)度量标准
聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类
K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系
参考引用
先上一张gif的k均值聚类算法动态图片,让大家对算法有个感性认识:
其中:N=200代表有200个样本,不同的颜色代表不同的簇(其中 3种颜色为3个簇),星星代表每个簇的簇心。算法通过25次迭代找到收敛的簇心,以及对应的簇。 每次迭代的过程中,簇心和对应的簇都在变化。
聚类算法的特点
聚类算法是无监督学习算法和前面的有监督算法不同,训练数据集可以不指定类别(也可以指定)。聚类算法对象归到同一簇中,类似全自动分类。簇内的对象越相似,聚类的效果越好。K-均值聚类是每个类别簇都是采用簇中所含值的均值计算而成。
聚类样本间的属性(包括,有序属性、无序属性)度量标准 1. 有序属性
例如:西瓜的甜度:0.1, 0.5, 0.9(值越大,代表越甜)
我们可以使用明可夫斯基距离定义:
2. 无序属性
例如:色泽,青绿、浅绿、深绿(又例如: 性别: 男, 女, 中性,人yao…明显也不能使用0.1, 0.2 等表示求距离)。这些不能使用连续的值表示,求距离的,一般使用VDM计算:
聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类
聚类算法分为如下三大类:
1. 原型聚类(包含3个子类算法):
K均值聚类算法
学习向量量化
高斯混合聚类
2. 密度聚类:
3. 层次聚类:
下面主要说明K均值聚类算法(示例来源于,周志华西瓜书)
算法基本思想:
K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇,且每个簇的中心采用簇中所含值的均值计算而成.簇个数 K 是用户指定的, 每一个簇通过其质心(centroid), 即簇中所有点的中心来描述.
算法流程如下:
主要是三个步骤:
初始化选择K个簇心,假设样本有 m个属性,则相当于k个m为向量
对于k个簇,求离其最近的样本,并划分新的簇
对于每个新的簇,更新簇心的向量(一般可以求簇的样本的属性的均值)
重复2~3直到算法收敛,或者运行了指定的次数
下面给出西瓜书的示例:
西瓜包含下面两个属性,密度以及含糖率,这两个属性构成的二维向量,作为输入向量(具体数据如下表)
算法大致过程如下:
下图是分类的,每一轮簇心的更新结果,图中横坐标为密度属性,纵坐标为含糖率属性:
4. K均值聚类算法的python实现
下面给出K-means cluster算法的实现的大致框架:
class KMeans(object):
def __init__(self, k, init_vec, max_iter=100):
"""
:param k:
:param init_vec: init mean vectors type: k * n array(n properties)
"""
self._k = k
self._cluster_vec = init_vec
self._max_iter = max_iter
def fit(self, x):
# 迭代最大次数
for i in xrange(self._max_iter):
print 'iteration %s' % i
# 求每个簇心的簇类
d_cluster = self._cluster_point(x)
# 对现有的簇类,更新簇心
new_center_node = self._reevaluate_center_node(d_cluster)
# 检测簇心是否变化,判断算法收敛
if self._check_converge(new_center_node):
print 'found converge node'
break
else:
self._cluster_vec = new_center_node
def _cal_distance(self, vec1, vec2):
return np.linalg.norm(vec1 - vec2)
def _cluster_point(self, x):
# 求每个簇心的簇
pass
return d_cluster
def _reevaluate_center_node(self, d_cluster):
# 对新的簇,求最佳簇心
return arr_center_node
def _check_converge(self, vec):
# 判断簇心是否改变,算法收敛
return np.array_equal(self._cluster_vec, vec)
具体的算法,以及见本人的github
下面给出程序的运行结果, 由图可见经过三次迭代程序收敛,并且找到最佳节点:
下面再给出,另一次运行结果,可见由于初始化点选择不一样,得到的结果也是不一样的,初始点的选择对聚类算法的影响还是很大。
K-means实际上是EM算法的一个特例,根据中心点(簇心)决定数据点归属是expectation,而根据构造出来的cluster更新中心(簇心)则是maximization。理解了K-means,也就顺带了解了基本的EM算法思路。
5. 参考引用
参考引用地址
来源:http://blog.csdn.net/haluoluo211/article/details/78524599
猜你喜欢
- 概念如果索引包含所有满足查询需要的数据的索引成为覆盖索引(Covering Index),也就是平时所说的不需要回表操作判断标准使用expl
- 一、导出数据。 先说明一下自己的环境:Mac OS X 10.8.3, MySQL Community Server 5.6.10, MyS
- 这一篇MobaXterm详细使用教程,我们来介绍一下如何设置并用MobaXterm来连接Linux服务器。MobaXterm 又名 Moba
- 刚开始学习python,python相对于java确实要简洁易用得多。内存回收类似hotspot的可达性分析, 不可变对象也如同java得I
- 目录openpyxl介绍openpyxl安装openpyxl基本概念openpyxl对excel进行操作新建excel打开已存在的文件读取单
- python使用socket创建tcp服务器和客户端。服务器端为一个时间戳服务器,在接收到客户端发来的数据后,自动回复。客户端,等待用户输入
- 如下所示:#随机数的使用import random #导入randomrandom.randint(0,9)#制定随机数0到9i=rando
- 一、概述前提:已安装 Python,如下图所示:1.1 检查是否已配置成功(选)1. 打开运行窗口 (1) 快捷键  
- 基本操作图片的基本读取与保存。读取图片读取和文件读取类似,需要先获取流:注册图片的解码器(如:jpg则import _ "imag
- 前言:前面文章讲述了 MySQL 系统中常见的几种日志,其实还有事务相关日志 redo log 和 undo log 没有介绍。相对于其他几
- 1、重装后启动mysql服务,提示 本地计算机无法启动 mysql 服务 错误 1067:进程意外终止。2、查看mysql根目录下有一 计算
- 在一个规范化的研发流程中,一般遵循如下流程:开发阶段:研发功能或者修复bug,在本地自测。代码审核阶段:提交代码,并请求团队内人员做code
- Pyinstaller库简介:简单来说,就是直接将python语言编写的py程序打包为exe可执行文件,对方不需要安装python环境即可直
- 目录一、环境准备二、问题分析三、spider四、item五、setting六、pipelines七、middlewares八、使用jupyt
- SELECT *FROM ( &n
- 问题:测试时 收发流采用TestCenter、SmartBit等仪表来进行。如果仍采用其进行自动化冒烟,则会带来效率低、成本高的问题。解决方
- python 实现pacs功能 推送下拉影像dcmtk关联pacs技术笔记:简介1、dcmtk关联pacs的参数介绍2、dcmtk命令介绍3
- 一,json.load()和json.dump只要用于读写json数据1json.load()从文件中读取json字符串with open(
- 如果你象作者一样记性不好,那么你可能根本记不住人们的名字。我遇到人时,多半只是点点头,问句“吃了嘛!”,而且期望问候到此为止 。如果还需要表
- 目录Python的内置数据类型中的数字1、变量2、数据类型总览3、Python是弱类型的语言4、各数据类型的详细介绍4.1 整数(int)4