专栏首页数据猿深入机器学习系列之:快速迭代聚类

深入机器学习系列之:快速迭代聚类

来源:星环科技

数据猿官网 | www.datayuan.cn

今日头条丨一点资讯丨腾讯丨搜狐丨网易丨凤凰丨阿里UC大鱼丨新浪微博丨新浪看点丨百度百家丨博客中国丨趣头条丨腾讯云·云+社区

1

谱聚类算法的原理

在分析快速迭代聚类之前,我们先来了解一下谱聚类算法。谱聚类算法是建立在谱图理论的基础上的算法,与传统的聚类算法相比,它能在任意形状的样本空间上聚类且能够收敛到全局最优解。 谱聚类算法的主要思想是将聚类问题转换为无向图的划分问题。

谱聚类算法的一般过程如下:

1、输入待聚类的数据点集以及聚类数k;

2、根据相似性度量构造数据点集的拉普拉斯矩阵L;

3、选取L的前k个(默认从小到大,这里的k和聚类数可以不一样)特征值和特征向量,构造特征向量空间(这实际上是一个降维的过程);

4、使用传统方法对特征向量聚类,并对应于原始数据的聚类。

谱聚类算法和传统的聚类方法(例如K-means)比起来有不少优点:

·和K-medoids类似,谱聚类只需要数据之间的相似度矩阵就可以了,而不必像K-means那样要求数据必须是N维欧氏空间中的向量。

·由于抓住了主要矛盾,忽略了次要的东西,因此比传统的聚类算法更加健壮一些,对于不规则的误差数据不是那么敏感,而且性能也要好一些。

·计算复杂度比K-means要小,特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。

快速迭代算法和谱聚类算法都是将数据点嵌入到由相似矩阵推导出来的低维子空间中,然后直接或者通过k-means算法产生聚类结果,但是快速迭代算法有不同的地方。下面重点了解快速迭代算法的原理。

2

快速迭代算法的原理

在大多数情况下,我们只关心第k(k不为1)大的特征向量,而不关注最大的特征向量。 这是因为最大的特征向量是一个常向量:因为W每一行的和都为1。

快速迭代的收敛性在文献【1】中有详细的证明,这里不再推导。

快速迭代算法的一般步骤如下:

3

快速迭代算法的源码实现

在spark中,文件org.apache.spark.mllib.clustering.PowerIterationClustering实现了快速迭代算法。我们从官方给出的例子出发来分析快速迭代算法的实现。

在上面的例子中,我们知道数据分为三列,分别是起始id,目标id,以及两者的相似度,这里的similarities代表前面章节提到的矩阵A。有了数据之后,我们通过PowerIterationClustering的run方法来训练模型。PowerIterationClustering类有三个参数:

·k:聚类数

·maxIterations:最大迭代数

·initMode:初始化模式。初始化模式分为Random和Degree两种,针对不同的模式对数据做不同的初始化操作

下面分步骤介绍run方法的实现。

(1)标准化相似度矩阵A到矩阵W

通过mapTriplets的计算,我们可以得到从点v1到v2,v3,v4的边的权重分别为1/3,1/3,1/3;从点v2到v1,v3,v4的权重分别为1/3,1/3,1/3;从点v3到v1,v2的权重分别为1/2,1/2;从点v4到v1,v2的权重分别为1/2,1/2。 将这个图转换为矩阵的形式,可以得到如下矩阵W。

·随机初始化

·度初始化

在这里,度初始化的向量我们称为“度向量”。度向量会给图中度大的节点分配更多的初始化权重,使其值可以更平均和快速的分布,从而更快的局部收敛。详细情况请参考文献【1】。

(3)快速迭代求最终的v

(4)使用k-means算法对v进行聚类

本文分享自微信公众号 - 数据猿(datayuancn)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-13

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • XGBoost缺失值引发的问题及其深度分析

    XGBoost模型作为机器学习中的一大“杀器”,被广泛应用于数据科学竞赛和工业领域,XGBoost官方也提供了可运行于各种平台和环境的对应代码,如适用于Spar...

    数据猿
  • 戴口罩的人脸数据被公开贩卖:两毛一张,能用于训练算法精准度也能申请信用贷款!

    “新冠疫情之下,京东数科、汉王、百度、腾讯、云从科技、中科视拓等众多科技企业纷纷推出或开放了自己“戴口罩状态下的人脸识别”技术。殊不知,方便了居民、秀了肌肉的同...

    数据猿
  • 数据中台盛行,DataOps兴起,数据架构才是未来

    “在数字化转型的浪潮下,数据架构备受关注。作为企业架构中的关键纽带,数据架构解决了业务与数据的映射,规范了应用架构的数据集成关系,指导了技术架构的技术选型。伴随...

    数据猿
  • 开发 | 机器学习之确定最佳聚类数目的10种方法

    AI科技评论按,本文作者贝尔塔,原文载于知乎专栏数据分析与可视化,AI科技评论获其授权发布。 在聚类分析的时候确定最佳聚类数目是一个很重要的问题,比如kmean...

    AI科技评论
  • 深入浅出聚类算法!如何对王者英雄聚类分析,探索英雄之间的秘密

    寄语:首先,对聚类算法进行了介绍;然后,解释了EM算法E步、M步的原理;最后,对sklearn参数进行了详解,并对王者荣耀英雄利用EM算法聚类,助力深入理解EM...

    Datawhale
  • 【机器学习】确定最佳聚类数目的10种方法

    在聚类分析的时候确定最佳聚类数目是一个很重要的问题,比如kmeans函数就要你提供聚类数目这个参数,总不能两眼一抹黑乱填一个吧。之前也被这个问题困扰过,看了很多...

    小莹莹
  • 聚类方法的区别解读:各种聚类分析呀呀呀

    k 均值聚类法 快速高效,特别是大量数据时,准确性高一些,但是需要你自己指定聚类的类别数量 系统聚类法则是系统自己根据数据之间的距离来自动列出类别,所以通过系统...

    学到老
  • K均值聚类(k-means clustering)

    K均值聚类算法是先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们...

    easyAI
  • R语言从入门到精通:Day15(聚类分析)

    聚类分析是一种数据归约技术,旨在揭露一个数据集中观测值的子集。它可以把大量的观测值归约为若干个类。

    用户6317549
  • 独家 | 如何在BigQueryML中使用K-均值聚类来更好地理解和描述数据(附代码)

    本文教你如何在BigQueryML中使用K均值聚类对数据进行分组,进而更好地理解和描述。

    数据派THU

扫码关注云+社区

领取腾讯云代金券