摘要:聚类作为一种数据挖掘工具,在生物学,商务智能以及Web搜索等方面有着广泛的应用。

0. 引子

想象你是一名客户关系主管,你想根据客户的特征对客户进行分类,然后针对每一个类的客户聘用一个经理对改客户群体进行管理。每个类中的客户应该尽可能的相似(在需求,业务等方面)。

那么,如何才能知道哪个客户属于哪个类别呢?

这样的问题叫做聚类(Clustering)问题,与之前介绍的分类问题不同,客户所属的类别信息是未知的。

需要通过分析客户的特征,通过某些算法来将客户划分成不同的类别。这些算法叫做聚类算法。

数据嗨客 | 第9期:k-means-数据分析网

聚类作为一种数据挖掘工具,在生物学,商务智能以及Web搜索等方面有着广泛的应用。

1. 聚类算法K-Means

作为一种流行的聚类算法,K-Means最初起源于信号处理。

K-Means的目标是将n个样本的数据划分到k个簇(也就是类别)中,其中k为人为指定的簇的个数,每个样本属于距离自己最近的簇。

下图为K-Means 用于图像处理的一个应用:

数据嗨客 | 第9期:k-means-数据分析网

图 1 K-Means用于图像分割

图中给出了原始图像以及使用不同k值得到的K-Means聚类结果。

上图聚类的过程使用图片中每个像素点作为数据样本,聚类过程会将距离上比较接近的像素(图中的颜色)划分到同一簇。

划分完成后,使用簇的质心值(某种颜色)替代簇中每一个点的值(与质心颜色相似的颜色)。这样原图中原来假设有1000种颜色,聚类之后的图之用了2,3,10种不同的颜色(对应于k=2,3,10)。

由于只使用了少量的颜色,此这种方法也达到了图像压缩的目的。

2. 核心思想

现在我们就要介绍一些干货了,原理其实特别简单。

给定n个需要被聚类的样本的集合(x_1,x_2,...,x_n),xi是d维实数向量。同样引入一组d维向量ci,其中i=1,2,...,k,且ci表示第i个簇Ci,我们可以认为ci是簇Ci的中心。

如下图所示:

数据嗨客 | 第9期:k-means-数据分析网

图 2 样本点,簇以及簇心

簇的中心可以定义为所有划分到该簇的样本点的中心点。

我们的目标是为把每一个样本点划到离它最近的一个簇中,其中要用到样本点到簇中心点的距离的度量。

我们约定每一个属于某个簇的样本点

数据嗨客 | 第9期:k-means-数据分析网

其中,E是所有样本的误差的平方和,p是样本点,ci是簇的簇心。

换言之,对于每个簇中的每个样本,求样本到其簇中心距离的平方,然后对所有的样本的求和。这个目标函数试图使生成的结果簇尽可能紧凑和独立。

3. 算法过程

在掌握了聚类的核心思想后,我们来具体看一下其具体算法,同样非常简单。

**K-Means算法过程**

1)选择k个点作为初始质心;

2)repeat:

2.1)将每个样本点通过距离计算指派到最近的质心,形成k个簇

2.2)更新簇的中心点值,即重新计算每个簇的质心

2.3)until 质心不发生变化 ***

重复上述优化过程,直至聚类的分配不再改变(或迭代次数超过某个值)。

由于每次优化过程,都降低目标函数E的值,因此目标函数E是一定收敛的。

然后,算法可能收敛到一个局部最优解而不是全局最优解。K-Means算法聚类过程如下图所示:

数据嗨客 | 第9期:k-means-数据分析网

图 3 K-Means算法聚类过程

4. 质心的选择

前面,我们已经掌握了K-Means算法的主要内容,接下来我们了解一些其他的细节。

选择质心常见的做法是随机初始化质心,但是这种方法容易陷入局部最优化,不能得到最优的聚类结果,有时结果可能很糟糕。

常用处理方法:

  1. 多次运行,每次使用一组不同的随机初始质心,然后选取具有最小E值的簇集。该策略虽然简单,但是效果可能不好,取决于数据集和寻找的簇的个数。随机选择初始质心存在的问题即使重复运行多次也不能克服。
  2. 使用层次聚类技术对样本进行聚类,从层次聚类中提取k个簇,并用这些簇的中心作出初始质心。该方法通常很有效,使用条件为:1)样本数目不大;

    2)k相对样本大小较小。

  3. 随机地选择第一个样本点,或取所有点的质心作为第一个质心点。然后,对于每个后继初始质心,选择离已经选取过的初始质心最远的点。使用这种方法,确保了选择的初始质心不仅是随机的,而且是散开的。但是,这种方法可能选中离群点。

5. 常用距离

一般情况下我们使用欧氏距离作为K-Means算法的距离度量,然而,对于其他一些数据类型,欧氏距离并不一定适用,比如文本数据。

此时,可以选择其他的距离度量,如曼哈顿距离、余弦相似度和Jaccard距离等。

6. K-Means方法优缺点

优点:

(1)算法实现简单,直观

(2)不仅可以使用欧式距离,还支持多种距离计算

缺点:

(1)需要指定k值和初始化k个簇

(2)聚类结果依赖于初始k个簇的选择

(3)容易陷入局部最优

(4)不易处理非簇状数据,且容易受离群点的影响

7. 二分K-Means算法

在了解了经典的K-Means方法之后,另外一种二分K-Means算法也很容易理解。

它相当于是原始K-Means方法的一个逆过程,采用分裂的方式从一个簇分裂成k个簇。

二分K-Means算法每次从所有簇中选择具有最大E值的簇划分为两个簇,重复该过程,直至簇集合中含有k个簇。直观上看,该算法可以克服质心选择上的问题。


二分K-Means算法过程:

1)把所有数据作为一个簇加入到簇集合;

2)Repeat:

2.1)从簇集合中,挑选出一个E值最大的簇

2.2)使用随机初始化质心的方式,将该簇划分为两个簇(一个簇对)

2.3)重复上一步骤p次,产生p个簇对,从p个簇对中选择EE值最小的簇对加入到簇集合中

2.4)直至簇集合中含有k个簇


在步骤2.1中,对于簇的挑选标准很多,不仅可以选择E值最大的簇,也可以选择样本数目最多的簇,或者使用其他标准。二分K-Means算法,在每一次划分过程都对质心做多次选取,选择最优划分,但也不能保证最终得到的事全局最优解。

8. K-Means方法的其他变种:

  • K-medians clusetering:使用每个维度的中位数而不是均值来作为聚的中心;
  • K-medoids:使用簇中心位置的数据作为簇的中心,而不是每个簇的平均值;
  • K-Means++:K-Means++是一个为k-Means算法选取初始质心的算法,它主要在初始化过程,选择k个距离较远的质心;
  • 基于粗糙集的K-Means聚类:原始的K-Means方法每次迭代中,每个数据样本只能划分给一个簇,基于粗糙集的K-Means聚类,一个数据样本可能被划分给多个簇。

本文由 普林科技(微信公众号:普林科技) 投稿 数据分析网 发表,并经数据分析网编辑。版权归作者所有,转载此文请与作者联系。