聚类算法原理及python实现

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/78524599

本文主要内容:

  1. 聚类算法的特点
  2. 聚类算法样本间的属性(包括,有序属性、无序属性)度量标准
  3. 聚类的常见算法,原型聚类(主要论述K均值聚类),层次聚类、密度聚类
  4. K均值聚类算法的python实现,以及聚类算法与EM最大算法的关系
  5. 参考引用

先上一张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个子类算法):
  1. K均值聚类算法
  2. 学习向量量化
  3. 高斯混合聚类
2. 密度聚类
3. 层次聚类

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

算法基本思想:

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

算法流程如下:

主要是三个步骤:

  1. 初始化选择K个簇心,假设样本有 m个属性,则相当于k个m为向量
  2. 对于k个簇,求离其最近的样本,并划分新的簇
  3. 对于每个新的簇,更新簇心的向量(一般可以求簇的样本的属性的均值)
  4. 重复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. 参考引用

https://datasciencelab.wordpress.com/2013/12/12/clustering-with-k-means-in-python/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏null的专栏

机器学习算法实现解析——libFM之libFM的训练过程之Adaptive Regularization

本节主要介绍的是libFM源码分析的第五部分之二——libFM的训练过程之Adaptive Regularization的方法。 5.3、Adaptive Re...

69070
来自专栏AI研习社

感知机(Perceptron)是怎么实现“知错能改”的?

感知机(perceptron)是二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别,取+1和-1二值。感知机对应于输入空间中将实例划分为正负两类的...

39680
来自专栏LhWorld哥陪你聊算法

【TensorFlow篇】--DNN初始和应用

正向传播:在开始的每一层上都有一个参数值w,初始的时候是随机的,前向带入的是每一个样本值。

14520
来自专栏张俊红

Sklearn参数详解—GBDT

这篇介绍Boosting的第二个模型GBDT,GBDT和Adaboost都是Boosting模型的一种,但是略有不同,主要有以下两点不同:

20840
来自专栏闪电gogogo的专栏

《统计学习方法》笔记五 决策树

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点。内部结点表示一个特征或属性,叶结点表示一个类。

10120
来自专栏杨熹的专栏

用 Doc2Vec 得到文档/段落/句子的向量表达

本文结构: Doc2Vec 有什么用 两种实现方法 用 Gensim 训练 Doc2Vec ---- Doc2Vec 或者叫做 paragraph2vec, s...

2K100
来自专栏null的专栏

利用Theano理解深度学习——Auto Encoder

注:本系列是基于参考文献中的内容,并对其进行整理,注释形成的一系列关于深度学习的基本理论与实践的材料,基本内容与参考文献保持一致,并对这个专题起名为“利用The...

38280
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

基于模糊集理论的一种图像二值化算法的原理、实现效果及代码

  这是篇很古老的论文中的算法,发表与1994年,是清华大学黄良凯(Liang-kai Huang) 所写,因此国外一些论文里和代码里称之为Huang's fu...

312110
来自专栏机器学习算法原理与实践

感知机原理小结

    感知机可以说是最古老的分类方法之一了,在1957年就已经提出。今天看来它的分类模型在大多数时候泛化能力不强,但是它的原理却值得好好研究。因为研究透了感知...

9120
来自专栏LhWorld哥陪你聊算法

【机器学习】--层次聚类从初识到应用

聚类就是对大量未知标注的数据集,按数据的内在相似性将数据集划分为多个类别,使类别内的数据相似度较大而类别间的数据相似度较小. 数据聚类算法可以分为结构性或者分...

30030

扫码关注云+社区

领取腾讯云代金券