数极客首页

T级数据量下的划分聚类方法CLARANS+

在常规聚类案例中,数据普通
都是以iris集或者缺乏
GB级的数据作为测试案例,理论

商业运用中,数据量级要远远大于这些。比如

滴滴出行15年日均单量就抵达

1000万单,出行轨迹的数据存储抵达

上百TB,常规的k均值聚类,二分聚类等无法完成如此量级的数据聚类。

大学课程教员

以一个公式概括过这样的过程:max(子集内相似

度/子集间相似

度),我觉得也很形象便于了解

什么是划分聚类?

聚类办法

有很多种,包括基于划分、基于密度、基于网格、基于层次、基于模型等等,这边主要引见
基于划分的聚类办法

,剩余的办法

会在后续的文章中持续更新(假定

不鸽的话)。划分聚类普通
是:采取互斥族(子集)划分,说的更直白一点就是每个点属于且仅属于一个族(子集)

常见的划分聚类有哪些?

k均值划分:

input:
- k:族的个数
- D:输入数据汇合

output:
k个族(子集)的数据汇合

methods:

1.在D中任选(常用的包库中都是这样做,但是倡议

自己

写的同窗
以密度先分块,在密度块中任选)k个对象作为初始中心

2.计算剩余对象到k对象的聚类,聚类远近分配到对应的族

3.更新族均值作为新的族中心

4.重复

2-4直到中心不变化

如图过程:

kmeans

以上为最简单的k均值,很容易看出,它存在几个问题,第一
计算量十分

的大,假定
有m条数据,k个中心点,那距离

计算的次数就是o(mkt)=k*(m-k)*迭代次数t,重复

t次直到收敛的过程是十分

大的计算过程;再而,假定

数据均为‘男、女’,‘高、中、低’等,那距离

定义就是十分

不合理的,此外,初始k难肯定
,非凸数据,离群点等等都存在问题

盘绕
中心划分(PAM):

刚才

说到了异常点会影响k均值,那么我们看看为什么?

假定
与点1、2、3、8、9、10、25,一眼就知道

{1、2、3},{8,9,10}为族,但假定

由k均值的话,以k=2为例,{{1,2,3},{8,9,10,25}},mse=196;{{1,2,3,8},{9,10,25}},mse=189.7;它重复

以mse为损失函数,而不去思索
数据能否
合理,所以针对的,我们有绝对误差规范

绝对误差规范

这样做,经过
全局距离

最小化,能够

一定水平

上避免

异常点的问题,但是,思索

一下计算量是什么?是o(**2),这意味着对数据量大的问题,这就是一个典型的NP问题(一定有解,但是不一定在有限时间资源内能够

被解出来)。

input:
- k:族的个数
- D:输入数据汇合

output:
k个族(子集)的数据汇合

methods:

1.D中任选k个对象最为初始种子

2.仿照k均值分配剩余对象

3.随机选取非种子对象O

4.计算若是以O为中心下的总损失函数代价S=原始种子下的绝对误差E-新的对象O下的绝对误差E

5.假定

S>0,则以新对象O交流

旧的种子对象,否则不变化

6.重复

2-5,直到收敛


其实看了以上两个算法,大同小异,但是都不可避免

有一个弱点,就是计算量上都是随着初始数据量的增大而几何增长的,所以这边需求
对数据量中止

控制。

大家回想一下,同样的对数据量中止

控制的算法有哪些给我们有启示

数据均衡

算法

这种办法

似乎

能够

减少数据量,哪有没有历史胜利

案例支持呢?

基于决策树引申出的集成算法

貌似存在一个叫做adaboost、randomforest这类的算法,似乎

就用了数据均衡

的算法

那么,我们能否
能够

用在聚类里面呢?答案是能够

的,我们往常

看一个由上述思绪
得到的CLARANS算法,理论

开发中,我们team对其中止

了优化,内部称之为CLARANS+

在了解

CLARANS+之前,我们先了解

CLARA:


肯定
中心

在数据量较少的子集上,我们能够

重复

肯定
每个子集的中心Medoid,这边计算中心的办法

有很多,包括上述讲到的K均值,PAM,也能够

参考相似

度比如

常见的余弦相似

,likelihood rate,高斯核相似

等等

最终
采取随机抽取,或者投票加权等办法

肯定
原始样本的中心即可。

CLARA的有效性依赖于样本的大小,散布

及质量,所以该算法一定水平

上会依赖于初始抽样的质量。除此之外,每一个随机样本的计算担任
度为O(ks*s+k(-k)),s为样本的大小,k为族数,n为总对象数,若抽取样本子集过少,其简化计算的水平

也越低。

说到这里,CLARA的算法是肯定
了中心后不在改动
,这就有一定的运气成分,假定
肯定
的k个钟均离最佳中心很远的状况

下,CLARA最终
无论怎样
去选已知中心,都得不到最优秀的聚类中心。

所以,我们来看看能够

进步
CLARA的聚类质量及可伸缩性的CLARANS算法

上述思绪
不变,但在CLARA肯定
中心之后,我们新增了一步,就是依照

PAM中的办法

一样,我们在子集上选取一个与当前中心x(Medoid)不一样的对象y(New Medoid),计算用y(New Medoid)交流

x(Medoid)后绝对误差能否
降落
,降落
则交流

否则不变,重复

l次之后,我们能够

以为
此时的中心点为部分

中心最优解;整体数据集一切
子集均重复

m次后,得出的中心点为全局部分

最优解。如下图:

新增New Medoid

理论上讲,以上的算法结果曾经
尽可能的保证了数据的合理紧缩
,紧缩
后的数据集内的中心点足够鲁棒,但是理论

运用过程中,我们没有尽可能的思索
到开头说的那句:

什么是聚类?

定义是这样的,把一个数据对象,划分红
子集的过程,使得子集内相似

度大,子集外相似

度小。这样的一个过程叫做聚类。

所以,我们尝试性的做了CLARANS+,我们把CLARANS里面肯定
出来的每个sample data子集里面最优秀的top k个New Medoids映射回同一个空间:

以绿色和天蓝色数据集为例子:

CLARANS

橘色方框内为CLARANS最终
肯定
中心后做的随机或者加权投票后采用
的被橘黄色框框住的天蓝色数据与绿色数据的中心点,很显然
能够

看出,这样招致
的结果违犯
了“子集外相似

度最小的准绳
”。

我们,仿照Lasso对应lambda.1se的方式,思索
除了最优点外,在其可接受

的范围左近
,以为
他们同样属于最优点,也就是top k个New Medoids重新选择距离

最远的点作为最优中心,也就是如下图中的紫色方框中的点:

最远距离

经过
理论

的业务测试,我们倡议

top k个点中的个默许
为2-3比较

好(数据散布

差别

大选择2,否则选择3),假定

不能肯定
,就默许
为3。

以上理论办法

就解释了怎样
在大量数据量下,简单快速的寻觅
到最优中心点的过程,谢谢大家。

参考文献:
[1] Jiawei Han.[数据挖掘

概念与技术]2001,8
[2] 毛国君等.数据挖掘

原理与算法[M].北京:清华大学出版社,2005.
[3]?数据均衡

算法
[4]?基于决策树引申出的集成算法
[5]?http://scikit-learn.org/stable/modules/clustering.html#clustering
[6]?https://en.wikipedia.org/wiki/Clustering

本文作者:沙韬伟,苏宁高级算法工程师。曾任惠普中国算法研讨
员,贡献

了开源散布

式R:distributed-R;曾任滴滴出行高级战略
剖析

师,设计了滴滴用户个人征信体系,滴滴租车风控战略
团队担任
人。

链接:http://www.jianshu.com/p/23c498b26836

本文由作者投稿至数据剖析

网并经编辑发布,版权归原作者一切
,转载请与作者联络

发表评论

评论已关闭。

相关文章