内容纲要

欢迎转载，作者：Ling，注明出处：机器学习：原理简明教程14-聚类

 

一句话概括（聚类）：聚类是无监督学习，需要将没有标注类别的实例，自动归类。

一句话概括（K-Means）: K-Means通过预先给定类别数目K，随机选择K个初始点，然后将其他节点分别归入最近的节点的类，然后再找每个类的中心，再反复进行归类。

一句话概括（DBSCAN）：选定一些核心对象，然后求所有密度可达的的点进行聚类得到不同的簇，该过程可能会合并一些簇，所谓密度可达，即在一定距离内，可以直接或者间接到达。

一句话概括（密度最大值聚类）：局部密度指在一定距离内的点的数目，高密距离指在i点周围所有的点中，局部密度大于i点且距离i最近的那个距离值，我们将具有较大局部密度和较大的高密距离的点作为簇中心点进行分类叫做密度最大值聚类。

一句话概括（谱聚类）：一种对K邻近图进行子图划分的聚类方法。

 

聚类方法有很多，其中比较好的聚类方法有：

  • K-Means聚类
  • 层次聚类
  • 密度聚类：DBSCAN，密度最大值聚类
  • 谱聚类

 

定义：

聚类就是对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使

类别内的数据相似度较大而类别间的数据相似度较小，属于无监督学习

 

相似度/距离计算方法：

ml_cluster_001

 

聚类基本思想

ml_cluster_002

Kmeans：

摘要：在数据挖掘中，K-Means算法是一种 cluster analysis 的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。

在数据挖掘中，K-Means算法是一种cluster analysis的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。

问题

K-Means算法主要解决的问题如下图所示。我们可以看到，在图的左边有一些点，我们用肉眼可以看出来有四个点群，但是我们怎么通过计算机程序找出这几个点群来呢？于是就出现了我们的K-Means算法（Wikipedia链接）

ml_cluster_003

K-Means要解决的问题

算法概要

这个算法其实很简单，如下图所示： 

ml_cluster_004

从上图中，我们可以看到，A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。

然后，K-Means的算法如下：

  1. 随机在图中取K（这里K=2）个种子点。
  2. 然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）
  3. 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
  4. 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。

这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”。

求点群中心的算法

一般来说，求点群中心点的算法你可以很简的使用各个点的X/Y坐标的平均值。不过，我这里想告诉大家另三个求中心点的的公式：

1）Minkowski Distance公式——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。

ml_cluster_005

2）Euclidean Distance公式——也就是第一个公式λ=2的情况

ml_cluster_006

3）CityBlock Distance公式——也就是第一个公式λ=1的情况

ml_cluster_007

这三个公式的求中心点有一些不一样的地方，我们看下图（对于第一个λ在0-1之间）。

ml_cluster_008

ml_cluster_009

ml_cluster_010

（1）Minkowski Distance     （2）Euclidean Distance    （3） CityBlock Distance

上面这几个图的大意是他们是怎么个逼近中心的，第一个图以星形的方式，第二个图以同心圆的方式，第三个图以菱形的方式。

K-Means的演示

如果你以”K Means Demo“为关键字到Google里查你可以查到很多演示。这里推荐一个演示：http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html

操作是，鼠标左键是初始化点，右键初始化“种子点”，然后勾选“Show History”可以看到一步一步的迭代。

注：这个演示的链接也有一个不错的K Means Tutorial。

K-Means++算法

K-Means主要有两个最重大的缺陷——都和初始值有关：

  • K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）
  • K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）

我在这里重点说一下K-Means++算法步骤：

  1. 先从我们的数据库随机挑个随机点当“种子点”。
  2. 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
  3. 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
  4. 重复第（2）和第（3）步直到所有的K个种子点都被选出来。
  5. 进行K-Means算法。

相关的代码你可以在这里找到“implement the K-means++ algorithm”（墙）另，Apache的通用数据学库也实现了这一算法

K-Means算法应用

看到这里，你会说，K-Means算法看来很简单，而且好像就是在玩坐标点，没什么真实用处。而且，这个算法缺陷很多，还不如人工呢。是的，前面的例子只是玩二维坐标点，的确没什么意思。但是你想一下下面的几个问题：

1）如果不是二维的，是多维的，如5维的，那么，就只能用计算机来计算了。

2）二维坐标点的X，Y 坐标，其实是一种向量，是一种数学抽象。现实世界中很多属性是可以抽象成向量的，比如，我们的年龄，我们的喜好，我们的商品，等等，能抽象成向量的目的就 是可以让计算机知道某两个属性间的距离。如：我们认为，18岁的人离24岁的人的距离要比离12岁的距离要近，鞋子这个商品离衣服这个商品的距离要比电脑 要近，等等。

只要能把现实世界的物体的属性抽象成向量，就可以用K-Means算法来归类了。

在《k均值聚类(K-means)》 这篇文章中举了一个很不错的应用例子，作者用亚洲15支足球队的2005年到1010年的战绩做了一个向量表，然后用K-Means把球队归类，得出了下面的结果，呵呵。

  • 亚洲一流：日本，韩国，伊朗，沙特
  • 亚洲二流：乌兹别克斯坦，巴林，朝鲜
  • 亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼

其实，这样的业务例子还有很多，比如，分析一个公司的客户分类，这样可以对不同的客户使用不同的商业策略，或是电子商务中分析商品相似度，归类商品，从而可以使用一些不同的销售策略，等等。

最后给一个挺好的算法的幻灯片：http://www.cs.cmu.edu/~guestrin/Class/10701-S07/Slides/clustering.pdf

 

Kmeans优缺点：

优点：

  • 是解决聚类问题的一种经典算法，简单、快速
  • 对处理大数据集，该算法保持可伸缩性和高效率
  • 当结果簇是密集的，它的效果较好

缺点

  • 在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用
  • 必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。
  • 不适合于发现非凸形状的簇或者大小差别很大的簇
  • 对躁声和孤立点数据敏感

 

可作为其他聚类方法的基础算法，如谱聚类

 

层次聚类方法（了解）

    层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：

凝聚的层次聚类：AGNES算法

  • 一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。

分裂的层次聚类：DIANA算法

  • 采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件

AGNES (AGglomerative NESting)算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的距离由这两个不同簇中距离最近的数据点对的相似度来确定；聚类的合并过程反复进行直到所有的对象最终满足簇数目。

DIANA (DIvisive ANAlysis)算法是上述过程的反过程，属于分裂的层次聚类，首先将所有的对象初始化到一个簇中，然后根据一些原则（比如最大的欧式距离），将该簇分类。直到到达用户指定的簇数目或者两个簇之间的距离超过了某个阈值

 

密度聚类方法：

密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个阈值，就把它加到与

之相近的聚类中去。这类算法能克服基于距离的算法只能发现“类圆形”(凸)的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。

  • DBSCAN
  • 密度最大值算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise):

    一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为

密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的

数据中发现任意形状的聚类。

概念：

ml_cluster_011

ml_cluster_012

算法：

  • DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。
  • 如果一个点p的ε-邻域包含多于m个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束

实例：

ml_cluster_013

密度最大值聚类

ml_cluster_014

ml_cluster_015

ml_cluster_016

ml_cluster_017

密度最大值聚类效果：

ml_cluster_018

 

谱聚类

      给你博客园上若干个博客，让你将它们分成K类，你会怎样做？想必有很多方法，本文要介绍的是其中的一种——谱聚类。

      聚类的直观解释是根据样本间相似度，将它们分成不同组。谱聚类的思想是将样本看作顶点，样本间的相似度看作带权的边，从而将聚类问题转为图分割问题：找到一种图分割的方法使得连接不同组的边的权重尽可能低（这意味着组间相似度要尽可能低），组内的边的权重尽可能高（这意味着组内相似度要尽可能高）。将上面的例子代入就是将每一个博客当作图上的一个顶点，然后根据相似度将这些顶点连起来，最后进行分割。分割后还连在一起的顶点就是同一类了。更具体的例子如下图所示：

ml_cluster_019

在上图中，一共有6个顶点（博客），顶点之间的连线表示两个顶点的相似度，现在要将这图分成两半（两个类），要怎样分割（去掉哪边条）？根据谱聚类的思想，应该去掉的边是用虚线表示的那条。最后，剩下的两半就分别对应两个类了。

      根据这个思想，可以得到unnormalized谱聚类和normalized谱聚类，由于前者比后者简单，所以本文介绍unnormalized谱聚类的几个步骤（假设要分K个类）：

(a)建立similarity graph，并用 W 表示similarity graph的带权邻接矩阵

(b)计算unnormalized graph Laplacian matrix L(L = D - W, 其中D是degree matrix)

(c)计算L的前K个最小的特征向量

(d)把这k个特征向量排列在一起组成一个N*k的矩阵，将其中每一行看作k维空间中的一个向量，并使用 K-means 算法进行聚类

 

算法原理解析

     这一节主要从大体上解释unnormalized谱聚类的四个步骤是怎么来的，不涉及具体的公式推导。

(a)谱聚类的思想就是要转化为图分割问题。因此，第一步就是将原问题转化为图。转为图有两个问题要解决：一是两个顶点的边要怎样定义；二是要保留哪些边。

      对于第一个问题，如果两个点在一定程度上相似，就在两个点之间添加一条边。相似的程度由边的权重表示（上图中边上面的数值就是权重了）。因此，只要是计算相似度的公式都可用，不过常用的是Gaussian similarity function

      要保留部分边的原因有：边太多了不好处理；权重太低的边是多余的。常用的保留边的方法是建立k-nearest neighbor graph。在这种图中，每个顶点只与K个相似度最高的点连边。

(b)unnormalized graph Laplacian matrix(以下用L表示)有很多很好的性质，也正是这个原因，才要在第二步中计算这么一个矩阵。最重要的性质是下面这一组性质：

ml_cluster_020

这一组性质将在之后的公式推导中起到决定性作用。

(c)将原问题转化为图后，接下来的工作就是决定怎样分割了。图分割问题实际上就是最小割问题(mincut problem)。最小割问题可定义为最小化以下目标函数：

ml_cluster_021

其中k表示分成k个组，Ai表示第i个组，

ml_cluster_022

表示第Ai的补集，W(A,B)表示第A组与第B组之间的所有边的权重之和。

      这个式子的直观意义：如果要分成K个组，那么其代价就是进行分割时去掉的边的权重的总和。可惜的是直接最小化这式子通常会导致不好的分割。以分成2类为例，这个式子通常会将图分成这样的两类：一个点为一类，剩下的所有点为另一类。显然，这样的分割是很不好的。因为我们期望着每个类都有合理的大小。所以，要对这个式子进行改进，改进后的公式（称为RatioCut)如下：

ml_cluster_023

其中|A|表示A组中包含的顶点数目。

      在RatioCut中，如果某一组包含的顶点数越少，那么它的值就越大。在一个最小化问题中，这相当于是惩罚，也就是不鼓励将组分得太小。现在只要将最小化RatioCut解出来，分割就完成了。不幸的是，这是个NP难问题。想要在多项式时间内解出来，就要对这个问题作一个转化了。在转化的过程中，就用到上面提到的L的那一组性质，经过若干推导，最后可以得到这样的一个问题：

ml_cluster_024

其中H是一个矩阵，它的元素的定义(Eq.(5))如下：

ml_cluster_025

如果H矩阵的元素

ml_cluster_026

不为0，则说明第i个点属于第j个类。也就是说，只要得到H矩阵，就能知道要怎样分割了。可惜的是，这个问题仍然是NP难问题。但是，如果我们让H矩阵的元素能够取任意值，这个问题就变成多项式时间内可解的了，此时问题变为：

ml_cluster_027

根据Rayleigh-Ritz theorem，这个问题的解是L的前k个最小的特征向量组成的矩阵H，其中特征向量是按列来排，即H的每一列，均为一个特征向量。

(d)在第三步中，我们为了松驰NP难问题，让H矩阵取任意值，因此，解出来的H矩阵不再具有原来的性质——元素值能指出哪个点属于哪一类。尽管如此，对于k-means来说，将H矩阵的每一行当作一个点进行聚类还是挺轻松的。因此，用k-means对H矩阵进行聚类作为谱聚类的最终结果。