大数据聚类算法知多少?如何无需编程快速实践?算法干货

欢迎关注数据超市微信公众号

最近做的项目中用到了这几个算法(实际上是调用了大数据机器学习算法的开源接口spark的ml库)我也总结一下。

先说说聚类相关的内容:

(一)k-means算法

k-means算法是聚类分析中使用最广泛的算法之一

首先是k-means算法,k-means算法是聚类分析中使用最广泛的算法之一。

它把n个样本根据它们的属性特征分为k个聚类,也常被称作k个簇,以便使得所获得的聚类满足:同一聚类(同一个簇)中的样本相似度较高;而不同聚类(不同簇)中的样本相似度较小。

1、k-means算法的基本过程如下所示:

(1)任意选择k个初始中心c_,c_,...,c_ 。

(2)计算X中的每个样本与这些中心的距离;并根据最小距离重新对相应样本进行划分。

(3)重新计算每个中心对象 C_ 的值。

(4)计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则重复步骤(2),(3)。

2、k-means算法的缺点,k-means算法虽然简单快速,但是存在下面的缺点:

(1) 聚类中心的个数K需要事先给定,但在实际中K值的选定是非常困难的,很多时候我们并不知道给定的数据集应该分成多少个类别才最合适。

(2) k-means算法需要随机地确定初始聚类中心,不同的初始聚类中心可能导致完全不同的聚类结果。

(3) 第一个缺陷我们很难在k-means算法以及其改进算法中解决,但是我们可以通过k-means++算法来解决第二个缺陷。

(二)k-means++算法

初始的聚类中心之间的相互距离要尽可能的远

1、k-means++算法选择初始聚类中心的基本原则是:

初始的聚类中心之间的相互距离要尽可能的远。它选择初始聚类中心的步骤是:

(1)从输入的数据点集合中随机选择一个点作为第一个聚类中心 c_ 。

(2)对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x),并根据概率选择新的聚类中心 c_ 。

(3)重复过程(2)直到找到k个聚类中心。

注意:第(2)步中,依次计算每个数据点与最近的种子点(聚类中心)的距离,依次得到D(1)、D(2)、...、D(n)构成的集合D,其中n表示数据集的大小。在D中,为了避免噪声,不能直接选取值最大的元素,应该选择值较大的元素,然后将其对应的数据点作为种子点(聚类中心)。

2、那么如何选择值较大的元素呢,下面是spark中实现的思路:

求所有的距离和Sum(D(x)) ,取一个随机值,用权重的方式来取计算下一个“种子点”。这个算法的实现是,先用Sum(D(x))乘以随机值Random得到值r,然后用currSum += D(x),直到其currSum > r,此时的点就是下一个“种子点”。

为什么用这样的方式呢?我们换一种比较好理解的方式来说明。把集合D中的每个元素D(x)想象为一根线L(x),线的长度就是元素的值。将这些线依次按照L(1)、L(2)、...、L(n)的顺序连接起来,组成长线L。L(1)、L(2)、…、L(n)称为L的子线。 根据概率的相关知识,如果我们在L上随机选择一个点,那么这个点所在的子线很有可能是比较长的子线,而这个子线对应的数据点就可以作为种子点。

(三)二分k-means算法

二分k-means算法是分层聚类(Hierarchical clustering)的一种

1、二分k-means算法是分层聚类(Hierarchical clustering)的一种,分层聚类是聚类分析中常用的方法。

分层聚类的策略一般有两种:

(1)聚合:这是一种自底向上的方法,每一个观察者初始化本身为一类,然后两两结合分。

(2)分裂:这是一种自顶向下的方法,所有观察者初始化为一类,然后递归地分裂它们二分k-means算法是分裂法的一种。

2、二分k-means算法是k-means算法的改进算法,相比k-means算法,它有如下优点:

二分k-means算法可以加速k-means算法的执行速度,因为它的相似度计算少了能够克服k-means收敛于局部最小的缺点。

二分k-means算法的一般流程如下所示:

(1)把所有数据初始化为一个簇,将这个簇分为两个簇。

(2)选择满足条件的可以分解的簇。选择条件综合考虑簇的元素个数以及聚类代价(也就是误差平方和SSE)

(3)使用k-means算法将可分裂的簇分为两簇。

(4)一直重复(2)(3)步,直到满足迭代结束条件。

以上过程隐含着一个原则是:因为聚类的误差平方和能够衡量聚类性能,该值越小表示数据点越接近于它们的质心,聚类效果就越好。 所以我们就需要对误差平方和最大的簇进行再一次的划分,因为误差平方和越大,表示该簇聚类越不好,越有可能是多个簇被当成一个簇了,所以我们首先需要对这个簇进行划分。

(四)高斯混合模型

数据可以看作是从多个高斯分布中生成出来

顾名思义,就是数据可以看作是从多个高斯分布中生成出来的。

从中心极限定理可以看出,高斯分布这个假设其实是比较合理的。 为什么我们要假设数据是由若干个高斯分布组合而成的,而不假设是其他分布呢?实际上不管是什么分布,只K取得足够大,这个XX Mixture Model就会变得足够复杂,就可以用来逼近任意连续的概率密度分布。只是因为高斯函数具有良好的计算性能,所GMM被广泛地应用。

每个GMM由K个高斯分布组成,每个高斯分布称为一个组件(Component),这些组件线性加成在一起就组成了GMM的概率密度函数。

如果我们要从GMM分布中随机地取一个点,需要两步:

1、随机地在这K个组件之中选一个,每个组件被选中的概率实际上就是它的系数pi_k;选中了组件之后,再单独地考虑从这个组件的分布中选取一个点。

2、怎样用GMM来做聚类呢?其实很简单,现在我们有了数据,假定它们是由GMM生成出来的,那么我们只要根据数据推出GMM的概率分布来就可以了,然后GMM的K个组件实际上就对应了K个聚类了。

看了以上算法,是否能够快速的对数据做一个验证呢?这里有一个无需编程即可调用算法组件的方式,谷歌浏览器打开www.BigData711.com注册使用即可。先总结这么多,希望对大家有帮助。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180131A0NW2J00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区