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(n**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，直到收敛

我们看这个图好理解一点，就是存在族（集合）中任一点p，当前的初始种子为Q1，随机选取剩余其他对象为族中心Qrandom1，计算PQ1的距离与PQrandom1的距离，图中dist(PQ1)<dist(PQrandom1)的距离，所以P仍属于Q1为中心的族，若存在族中心Qrandom2，使得dist(PQ1)>dist(PQrandom2)，则更新族中心为Qrandom2,此时绝对误差E会变化，计算是否降低了绝对误差E以确定是否更好族中心。

其实看了以上两个算法，大同小异，但是都不可避免有一个弱点，就是计算量上都是随着初始数据量的增大而几何增长的，所以这边需要对数据量进行控制。

大家回想一下，同样的对数据量进行控制的算法有哪些给我们有启发？

数据平衡算法

这种方法好像可以减少数据量，哪有没有历史成功案例支持呢？

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

貌似存在一个叫做adaboost、randomforest这类的算法，好像就用了数据平衡的算法。

那么，我们是否可以用在聚类里面呢？答案是可以的，我们现在看一个由上述思路得到的CLARANS算法，实际开发中，我们team对其进行了优化，内部称之为CLARANS+

在理解CLARANS+之前，我们先理解CLARA:

从这张图上，我们可以很清晰的看出，CLARA首先通过类似randomforest里面的随机抽样的方法，将原始数据集随机抽样成若干个子数据集sample data，理论上采样的子集分布应该与原分布近似，所以样本中心点必然与原分布中心近似。

确定中心

在数据量较少的子集上，我们可以重复确定每个子集的中心Medoid，这边计算中心的方法有很多，包括上述讲到的K均值，PAM，也可以参考相似度比如常见的余弦相似，likelihood rate，高斯核相似等等

最后采取随机抽取，或者投票加权等方法确定原始样本的中心即可。

CLARA的有效性依赖于样本的大小，分布及质量，所以该算法一定程度上会依赖于初始抽样的质量。除此之外，每一个随机样本的计算负责度为O（ks*s+k（n-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

本文由作者投稿至数据分析网并经编辑发布，版权归原作者所有，转载请与作者联系。