Clustering Algorithm/聚类算法[一]


聚类(clustering),其实本质就是寻找联系紧密的事物,把他们区分出来。如果这些事物较少,人为的就可以简单完成这一目标。但是遇到大规模的数据时,人力就显得十分无力了。所以我们需要借助计算机来帮助寻找海量数据间的联系。

聚类过程中有一个关键的量,这个量就是标识两个事物之间的关联度的值,称为相关距离度量(distance metrics),之前的两篇博文相似性度量皮尔逊相似性系数 都是计算这种距离度量的方法。根据实际情况的不同,选择不同的适用的度量方法。这一点十分重要,直接影响聚类的结果是否符合实际需要和情况。

聚类是一个无监督学习(unsupervised learning)的过程,不需要进行样本数据的训练。设计出适合的距离度量方法后,即可对目标数据集进行聚类。

聚类方法的类别大致有一下关键字:

1、层次、划分
2、互斥、重叠、模糊
3、完全、部分

下边循循渐进介绍一些经典的聚类算法。

一、分级聚类(Hierarchical Clustering)

个人感觉应该是最简单暴力好用的方法(突然想起来sky说的人族干兽族solo,就是带塔一波流,简单粗暴有效),算法过程就是连续不断的将最为相似的两个群组合并,来构造一个新的群组。这样从最开始的单一元素开始,最后我们能够把所有的元素都聚在一个大类里。如下图所示:
分级聚类
上图中有ABCDE五个元素,最开始AB最近,就聚在一起,然后把群组(AB)(C)(D)(E)比较,发现(AB)(C)最近,则把(ABC)变成一类,这样一直下去就完成了这个算法。两两群组相似性的判断可以简单的这样判断:群组1和群组2里的元素一一对比对相关性求和取平均数,像(AB)(C),相关性为:(BC相关性+AC相关性)/2,当然也可以有其他方法,但是请保证各个组之间距离值计算时不应该让数量的多少占据较大权重,即应该尽量消除数量上对距离值的影响。

一般的定义类之间的临近性的方法:
1、单链(single link)
2、全链(complete link)
3、组平均(group average)
4、Ward方法
5、质心方法
6、Lance-Williams公式
详细的请参看《数据挖掘导论》层次聚类部分。

这一过程止于最后决定的聚类个数,如果是1的话,就最后全部聚成一类,把这一聚类过程可以画出树状图,能方便看出聚类过程使决策者方便作出决策。

但是这个算得缺点也是明显的:计算量十分的巨大,数据规模大的时候这个时间是无法接受的。如果是上边的方法计算相关性,则时间复杂度为O(n^2log(n)),聚成树形是log(n),然后各个元素都需要两两进行比较所以是n方。空间复杂度对现在的存储设备来讲,并不是考虑的重点(空间复杂度O(n^2))。

另外还有一些类似的分级聚类的算法:
自顶向下分裂算法:整体数据为一个类,每次根据分类模型对数据进行分裂,最终分裂成每个单独的数据点结束。
单链接算法:就是每一轮设置一个距离度量的一个阈值,在阈值内的分为一个类别里,这样每级分类都扩大这个阈值,最后完成整个聚类过程。
平均链接的算法:它是单链接算法的改进,就是检查两个类别的数据点之间的距离度的平均值小于阈值,其实就是上边说的距离度量计算方法的不同,本质还是同一算法。
ROCK算法:一种粗暴的算法,直观的把两个类别内数据有链接的,并且连接的多的聚在一类里边。抛弃了距离度量,只用是否有链接来衡量。
当然了,最小生成树算法也属于分级分类算法里的,没啥特别要说的。
其实变来变去都是核心的分层聚类。都是自底向上的层层聚类,不同的就是距离度量的衡量标准不同。

层次聚类的主要问题:
1、缺乏全局目标函数,也就是说层次聚类技术使用各种标准,在每一步局部地确定哪些类应该合并或者分裂。
2、需要考虑大小类的临近合并能力
3、每次合并或分裂都是局部最优的,但一旦做出决策不能撤销,阻碍了局部最优解变成全局最优。
4、最噪点、多维数据处理比较困难。
5、由于较高的时间复杂度,一般会较少使用。

二、K-均值聚类(K-Means Clustering)

这个是经典的聚类算法,无论时间复杂度还是空间复杂度都是比较好的。这个算法的名称已经说明了算法的核心意图,会对数据进行K个类别的聚类。算法过程就是:

1、在数据集里随机选K个点,当作每个类别的中心点(你也可以通过一定方法选择K个点)
2、通过距离度量,把数据集里的所有点根据距离远近分配给这K个中心点(即数据分给最近的一个中心点),组成一个类别,即获得K个类别。
3、在获得的K个类别里进行均值计算,算出新的中心点(根据需求进行不同模型的均值计算,一般就是选个中心点使相应聚类里的所有点到这个点的距离和最小),把得到的中心点替换各个类别的K点值。
4、判断新获得的一组K值是否和上一次的一组K值相同,如果不同则跳到第2步。如果相同则完成了聚类过程。

算法流程如下图:

上图就随机获得两个中心点K值组,然后第一次把AB分为一个类别,CDE分为一个类别。然后重新计算中心点,把旧中心点移动到新中心点再次分配数据集。获得ABC为一个类别,DE为一个类别。递归这个算法知道中心点不再变化,或者当中心点变化小于一个阈值(threshold)即停止聚类。

这个算法有一个问题,就是中心点的选取的问题。第一就是初始的K值集合如果选择不当,会造成聚类结果有严重的偏差或错误,这个等说到Canopy算法的时候说。另外一个就是如果要聚类的数据集是一个离散的、具体的物体或者实际存在的事物,而通过均值计算出的中心点是不存在于数据集里的点,这样会造成这个中心点无意义的情况。而一个无意义的中心点是无法计算它跟各个实际存在的有意义的数据点的距离值的。所以针对K-Means算法有一个改进,改进的地方就是对K值选取的改进。
第一次随机选取K个值是在数据集里选取的。以后每次的K值选取都是在相应的类别内的数据集里选取某一个中心元素的计算(如某个类别里的数据集是一个图结构,可以使用最小生成树的根节点),然后把该点当新的K值。

当然这个改进是在有选择点需要有意义的情况下使用的。如果计算距离值的方法是曼哈顿或者什么任意坐标下能计算距离的点,其实没必要使用这种改进,因为这种改进使时间复杂度升高很多。这个算法改进前时间复杂度为O(n),改进后因为O(nlog(n))甚至是O(n^2log(n)),视K值选取模型算法的不同而定,一般都会更复杂。

这里额外提一点K-Means算法的一个应用。一般的对数据集聚类就不说了,很容易想到也用上。这里说的是对图片、视频等的压缩。这里要提到矢量量化(Vector Quantization)的一个概念,较多的应用于信号处理、信息压缩等领域。个人理解的通俗来讲就是:把连续的数据离散化的一种技术。比如说信号、波,一般都是连续的信号,比如[0,1)、[1,2)……等,对其进行离散化成0,1……等,这样更方便来使用计算机处理和压缩数据。

转回图像处理上,考虑一个简单的灰度图片,0 为黑色,1 为白色,每个像素的值为 [0, 1] 上的一个实数。现在要把它编码为 256 阶的灰阶图片,一个最简单的做法就是将每一个像素值 x 映射为一个整数 floor(x*255) 。当然,原始的数据空间也并不以一定要是连续的。比如,你现在想要把压缩这个图片,每个像素只使用 4 bit (而不是原来的 8 bit)来存储,因此,要将原来的 [0, 255] 区间上的整数值用 [0, 15] 上的整数值来进行编码,一个简单的映射方案是 x*15/255 。这样压缩图像,问题也就来了,如果一个255阶的灰度图是由0-14种颜色组成的,那么压缩后的图片则变为全黑的一副图。

这里较好的做法就是使用聚类算法。实际做法就是:将每个像素点当作一个数据,跑一下 K-means ,得到 k 个图心(centroids),然后用这些 centroids 的像素值来代替对应的 cluster 里的所有点的像素值。对于彩色图片来说,也可以用同样的方法来做,例如 RGB 三色的图片,每一个像素被当作是一个 3 维向量空间中的点。如下四个图分别为:原图,使用k=100个图心的缩略图,使用k=10个图心的缩略图,使用k=2个图心的缩略图。




这样把原来的许多颜色值用 centroids 代替之后,总的颜色数量减少了(如上k=2,10,100),重复的颜色增加了。考虑一种最简单的压缩办法:单独存储centroids 的颜色信息(每个图心占8*8*8 24bit),然后每个像素点存储 centroid 的索引而不是颜色信息值,索引值只需要 8 bits (128种类别以内)来存放,这样就起到了压缩的效果。去掉索引值占的24bit,那么一张图片就压缩为原来的1/3,图片尺寸大小不变。

当然也可以使用图片尺寸压缩的办法来处理图像的压缩,在一定压缩区域内聚类出较大类别的图心来代替原来区域。

三、DBSCAN聚类算法(Density-Based Spatial Clustering of Applications with Noise)

这种聚类算法是基于数据点密度的算法。这个算法有两个重要的参数设定,一个是密度范围eps,一个是密度范围内的数据个数minPoints。结合下图解释这个算法:

图上一堆点,其中标出ABCN四个点,首先随机选择到A点为实施算法的入口点,我们设定eps范围为图中的圆的半径,minPoints为3(在这个图中,其实设置为4也一样结果)。这样我们根据A为中心,半径为eps的范围,找到了周围的点,这些点个数是大于等于minPoints的,所以他们成为一个簇,并都标记为边缘点,A标记为中心点,用红色表示。然后在标记的边缘点中选取一个再次画半径为eps的圆,如果该圆内的Points个数超过minPoints,则该点也标记为中心点,把新入的标为边缘点再次递归该算法。这样下去就标记完了以A为起始的一个聚类,为图中红色的中心点和黄色的边缘点。直到所有边缘点处理完毕,如果还有Points未处理,再次新产生一个类别来重新启动这个算法过程。所有数据都跑过一遍后,如果有点既不是边缘点也不是中心点的点,最后标记为噪音。

这样的一个过程就完成了基于密度的DBSCAN聚类算法。算法复杂度,如果填入了各个点的索引优化,时间复杂度就是所有点便利一遍n,每个点查询周围的数据log(n),所以是O(nlog(n))。还是很不错的算法。

[参考]:
wiki、集体智慧编程、智能web算法、pluskid

ps:整篇没有写数学公式,只给出了算法的一步步的流程,为了不使刚看的人产生不想看下去的想法。另外整片也没有一句代码,是因为聚类一般处理的都是大数据,写单节点代码处理少量测试数据个人认为是没有任何意义和参考价值的,所以就样例代码也不写了(吐槽书里整片整片的粘贴代码纯粹是增加页码,没有任何实际参考价值,根本用不到大规模数据处理上,都需要自己另行设置相关模型和算法的实施代码)。

个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

7 Comments - Leave a comment
  1. 火星十一郎--河南理工说道:

    “每次合并或分裂都是局部最优的,但一旦做出决策不能撤销,阻碍了局部最优解变成全局最优。”不是不能撤销,而是考虑到效率问题不进行回溯..........我博客http://www.cnblogs.com/hxsyl/

  2. Jian Xu说道:

    正是我在研究的方向,大赞~~~

  3. iphxer说道:

    占个位儿再看~

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 11 月 19 日