python实现聚类算法原理

作者:FishBear_move_on 时间:2022-07-23 23:42:33 

本文主要内容:

  • 聚类算法的特点

  • 聚类算法样本间的属性(包括,有序属性、无序属性)度量标准

  • 聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类

  • K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系

  • 参考引用

先上一张gif的k均值聚类算法动态图片,让大家对算法有个感性认识:

python实现聚类算法原理

其中:N=200代表有200个样本,不同的颜色代表不同的簇(其中 3种颜色为3个簇),星星代表每个簇的簇心。算法通过25次迭代找到收敛的簇心,以及对应的簇。 每次迭代的过程中,簇心和对应的簇都在变化。

聚类算法的特点

聚类算法是无监督学习算法和前面的有监督算法不同,训练数据集可以不指定类别(也可以指定)。聚类算法对象归到同一簇中,类似全自动分类。簇内的对象越相似,聚类的效果越好。K-均值聚类是每个类别簇都是采用簇中所含值的均值计算而成。

python实现聚类算法原理

聚类样本间的属性(包括,有序属性、无序属性)度量标准 1. 有序属性

例如:西瓜的甜度:0.1, 0.5, 0.9(值越大,代表越甜)

我们可以使用明可夫斯基距离定义:

python实现聚类算法原理

2. 无序属性

例如:色泽,青绿、浅绿、深绿(又例如: 性别: 男, 女, 中性,人yao…明显也不能使用0.1, 0.2 等表示求距离)。这些不能使用连续的值表示,求距离的,一般使用VDM计算:

python实现聚类算法原理

python实现聚类算法原理

聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类

聚类算法分为如下三大类:

1. 原型聚类(包含3个子类算法):

K均值聚类算法

学习向量量化

高斯混合聚类

2. 密度聚类:

3. 层次聚类:

下面主要说明K均值聚类算法(示例来源于,周志华西瓜书)

算法基本思想:

K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为 K-均值 是因为它可以发现 K 个不同的簇,且每个簇的中心采用簇中所含值的均值计算而成.簇个数 K 是用户指定的, 每一个簇通过其质心(centroid), 即簇中所有点的中心来描述.

算法流程如下:

python实现聚类算法原理

主要是三个步骤:

  • 初始化选择K个簇心,假设样本有 m个属性,则相当于k个m为向量

  • 对于k个簇,求离其最近的样本,并划分新的簇

  • 对于每个新的簇,更新簇心的向量(一般可以求簇的样本的属性的均值)

  • 重复2~3直到算法收敛,或者运行了指定的次数

下面给出西瓜书的示例:

西瓜包含下面两个属性,密度以及含糖率,这两个属性构成的二维向量,作为输入向量(具体数据如下表)

python实现聚类算法原理

算法大致过程如下:

python实现聚类算法原理

下图是分类的,每一轮簇心的更新结果,图中横坐标为密度属性,纵坐标为含糖率属性:

python实现聚类算法原理

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

下面给出程序的运行结果, 由图可见经过三次迭代程序收敛,并且找到最佳节点:

python实现聚类算法原理

下面再给出,另一次运行结果,可见由于初始化点选择不一样,得到的结果也是不一样的,初始点的选择对聚类算法的影响还是很大。

python实现聚类算法原理

K-means实际上是EM算法的一个特例,根据中心点(簇心)决定数据点归属是expectation,而根据构造出来的cluster更新中心(簇心)则是maximization。理解了K-means,也就顺带了解了基本的EM算法思路。

5. 参考引用

参考引用地址

来源:http://blog.csdn.net/haluoluo211/article/details/78524599

标签:python,聚类算法
0
投稿

猜你喜欢

  • Python基于模块Paramiko实现SSHv2协议

    2021-10-17 22:21:38
  • XMLHTTP中setRequestHeader的参数问题

    2008-09-30 10:48:00
  • 关于Python 列表的索引取值问题

    2022-09-08 05:39:54
  • 分享4个Python中高效省时的技巧

    2021-02-14 22:32:09
  • mysql-connector-java与mysql版本的对应关系说明

    2024-01-19 07:35:36
  • 订单转化率之回访确认

    2009-08-24 12:40:00
  • JS字符串拼接的几种方式(最新推荐)

    2024-04-10 16:11:41
  • python 创建一个空dataframe 然后添加行数据的实例

    2022-05-08 01:51:59
  • 微信小程序录音实现功能并上传(使用node解析接收)

    2024-04-16 08:46:56
  • 轻松实现TensorFlow微信跳一跳的AI

    2021-11-24 10:35:40
  • Python 实现集合Set的示例

    2021-10-04 06:27:19
  • Python中datetime模块参考手册

    2021-04-21 23:31:12
  • 3个常用的JS时间代码

    2009-03-22 15:29:00
  • xorm根据数据库生成go model文件的操作

    2024-01-16 00:29:22
  • GO中的条件变量sync.Cond详解

    2024-02-10 15:08:35
  • MySQL5.6升级5.7时出现主从延迟问题排查过程

    2024-01-27 03:27:34
  • 如何用mysql自带的定时器定时执行sql(每天0点执行与间隔分/时执行)

    2024-01-16 01:58:31
  • javascript+css3开发打气球小游戏完整代码

    2024-05-02 16:15:54
  • Python实现绘制多角星实例

    2023-08-26 13:42:14
  • JS统计Flash被网友点击过的代码

    2024-05-03 15:06:18
  • asp之家 网络编程 m.aspxhome.com