机器学习之聚类分析算法详解

一、聚类相关概念

1、定义

Clustering (聚类)，简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在Machine Learning中被称作unsupervised learning (无监督学习)。 聚类中没有任何指导信息，完全按照数据的分布进行类别划分。

2、方法

聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分,且对象之间的相似度是基于对象间的距离来计算的。

3、距离计算

常用的距离的计算方法：

1）欧几里德距离

d = sqrt(∑(xi1-xi2)^)

2）曼哈顿距离

d = |X1-X2|+|Y1-Y2|

4、相似度计算

聚类结果：类内相似度越大越好，类间相似度越小越好;

相似度计算方法：

1）类别 – 类内相似度

2）类别 – 类间相似度

5、应用

1）经济领域

• 帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。
• 谁喜欢打国际长途，在什么时间，打到那里？
• 对住宅区进行聚类，确定自动提款机ATM的安放位置

2）生物学领域

• 推导植物和动物的分类
• 对基因分类，获得对种群的认识

3）数据挖掘领域

• 作为其他数学算法的预处理步骤，获得数据分布状况，集中对特定的类做进一步的研究

二、常用传统算法

1、层次方法

1）常见层次方法

a）凝聚的（agglomerative）方法（自底向上）

思想：一开始将每个对象作为单独的一类，然后根据同类相近，异类相异的原则，合并对象，直到所有 的类合并成一个，或达到一个终止条件为止。

b）分裂的方法（divisive）（自顶向下）

思想：一开始将所有的对象置于一类，在迭代的每一步中，一个 类不断地分为更小的类。

算法运行到某一阶段，类别划分结果达到聚类标准时即可停止分裂或凝聚，根据树结构就可以很容易得到聚类结果。

2）优点

1. 距离和规则的相似度容易定义，限制少
2. 不需要预先制定聚类数
3. 可以发现类的层次关系

3）缺点

1. 计算复杂度太高；
2. 奇异值也能产生很大影响；
3. 算法很可能聚类成链状

2、划分方法

给定一个n个数据对象的合集，构建k个分区，其中每个分区代表一个簇，并且k<<n，使的每个组至少包含一个对象。大部分划分方法是基于距离的，采用‘迭代的重定位技术’，例如k-均值和k-中心点算法。

1）K-均值（K-Means）

a）主要步骤

• 1. 将数据集划分为k个非空子集 ，然后随机选取K个质心，根据距离 将数据点到分配到对应的簇当中去
• 2. 计算当前簇的均值点作为新的质心
• 3. 重新分配各个数据对象，将每个对象指定为最近种子点所在的类
• 4. 返回步骤2，计算当前簇的均值点作为新的质心

直到质心的位置不再发生变化 我们可以认为聚类已经达到期望的结果，算法终止。

b）优点

1. 收敛速度快。
2. 在簇与簇之间区别明显时, 它的效果较好。
3. 需要调参的参数仅仅是簇数K。

c）缺点

1. 仅适用于能够定义平均值的数据
2. 需要预先指定k，即簇的数量，采取其他技术确定一个较好的k值
3. 初始质心的选择直接决定最终的聚类效果
4. 无法处理噪音数据和异常点
5. 针对k-means对异常点敏感的问题，提出K-中心点算法（K-Medoids）

2）K-中心（K-Medoids）

k-中心和k-均值很像，不同的是形心的更新选择，k-均值是通过求得均值进行更新形心的，而k-中心是随机选择k个对象作为初始的k个簇的代表点，反复用非代表点来代替代表点，直到找到误差平方和最小的那个点来作为数据中心点。这样划分方法是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的,这是 k-medoids 方法的基础。

a）主要步骤

• 1. 一开始也是随机选择K个初始对象
• 2. 将每个剩余的对象分配在临近的簇中当中去，计算当前代价
• 3. 随机选择一个非质心对象作为新质心
• 4. 计算用新质心的总代价S
• 5. If S <旧质心, t就替换用当前质心代替旧质心，形成新的k个簇

重复整个过程，直到质心位置不再发生变化。

• 6. 与k-means相比,k-中心对噪声和离群点的处理具有更好的鲁棒性，中心点不容易受离群点影响
• 7. 与k-means相同，k-中心也要事先指定具体的簇数k
• 8. k-medoids 方法的执行代价比 k-means 算法高，当n和k较大时，计算开销变得很大，远高于k-means

3、基于密度的方法

之前提到的层次与划分方法基于对象之间的距离进行聚类，这样的方法大多只能发现球状的类，而在发现任意形状的类上有困难。因此，出现了基于密度的聚类方法，其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，在一个给定范围的区域内必须至少包含某个数目的点。

基于密度的方法认为簇是数据空间中数据密集的区域，数据稀疏区域中的数据被认为是噪音数据。

1）DBscan

DBSCAN是基于密度的聚类方法，它的思想是一个簇被定义为所有紧密连接的数据点的最大集合。DBSCAN检查数据库中每个点p周围半径R的区域如果该区域包含的数据点的个数大于某个阈值M，则创建一个新cluster，该cluster的中心为p，然后把相关联的cluster进行合并。 DBSCAN进行聚类的过程就是不断执行区域查询的过程。

2）MeanShift

Meanshift会依次选中每一个点为圆心（质心），在选中一个点后，然后以半径R画一个圆，然后落在这个圆中的每一个点与圆心都会构成向量，把所有这些向量相加，我们会得到一个向量，就是下图中用黄色箭头表示的向量，这个向量就是meanshift向量。然后再以这个meanshift向量的终点为圆心，继续上述过程，可以得到很多连续的meanshift向量，这些向量首尾相连，最终迭代到收敛，在密度最大处停下来。最后的那个meanshift向量的终点就是最终得到的结果（最终质心）

3）相同数据下DBscan与MeanShift聚类表现

对于离群的稀疏点，dbscan处理的不是特别好，因为他算法的特性是区域包含的数据点的个数大于某个阈值M，则创建一个纳入到当前类。这也对应算法的优缺点，体现算法的特征 在实际应用中对应适合处理那些特征的数据集。

4）小结

这样的方法可以过滤“噪声”数据，发现任意形状的类。但算法计算复杂度高，一般为O(n2)，当数据量大时，就必须有大内存量支持，I/O消耗也非常大，对于密度分布不均的数据集，可能得不到满意的聚类结果。

4、基于网格的方法

基于网格的方法把对象空间量划为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。

基于网格的聚类算法常常与其他方法相结合,特别是与基于密度的聚类方法相结合。例如WaveCluster与CLIQUE。

1）主要步骤

• 1. 将数据空间划分为有限个网格单元;
• 2. 计算每个网格单元的密度;
• 3. 如果网格单元的密度大于一定阈值则此网格单元为密集网格;
• 4. 将临近的密集阈值网格单元合并为一个类别;

5、基于模型的方法

基于模型的方法主要是指基于概率模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。这里的概率模型主要指概率生成模型（generative Model），同一”类“的数据属于同一种概率分布。这样的方法通常包含的潜在假设是：数据集是由一系列的潜在概率分布生成的。其中最典型的有高斯混合模型（GMM，Gaussian Mixture Models）基于神经网络模型的方法，神经网络模型主要就是指SOM（Self Organized Maps）了，也是唯一一个非监督学习的神经网络了。

• GMM
• SOM

1）主要步骤

• 1. 确定神经元分布结构及神经元数，每个神经元代表一个类别;
• 2. 随机初始化神经元向量;
• 3. 随机选择输入数据;
• 4. 计算输入数据与每个神经元的相似度;
• 5. 选择具有最大相似度的神经元为获胜神经元;
• 6. 调整获胜神经元向量，及位于获胜神经元邻域范围内的神经元向量;
• 7. 判断是否满足收敛条件，如不满足，反复运行3～7 ;

6、基于约束的方法

真实世界中的聚类问题往往是具备多种约束条件的。这里的约束可以是对个体对象的约束,也可以是对聚类参数的约束。该方法的一个重要应用在于对存在障碍数据的二维空间数据进行聚类。比如典型的ATM分配问题。

COD (Clustering with Ob2structed Distance)就是处理这类问题的典型算法,其主要思想是用两点之间的障碍距离取代了一般的欧氏距离来计算其间的最小距离。

三、新发展的算法

1、基于模糊的算法

传统的聚类分析是一种“硬”聚类(Crisp Clustering)方法，隶属关系采用经典集合论中的要么属于要么不属于来表示，事物之间的界限有着截然不同的区别。然而，现实生活中很多事物特征无法给出一个精确的描述，例如把人按身高分为“高个子的人”，“矮个子的人”，“不高不矮的人”。然而，多高算高？多矮算矮？这样的分类判别是经典分类解决不了的问题。模糊聚类分析方法为解决此类问题提供了有力的分析工具。该方法把隶属关系的取值从笼{0,1}二值逻辑扩展到[0，1]区间，从而更合理地表示事物之间存在的中介性。

目前国内外对模糊聚类分析的研究非常重视，参与这个学科研究的国度遍布全球，研究人员与日俱增，模糊新产品不断问世，模糊技术不断被应用到高精尖领域，基础理论研究与实际应用研究也取得了丰硕的成果。模糊数学目前正沿着理论研究和应用研究两个方向迅速发展。理论研究主要是经典数学概念的模糊化。由于模糊集自身的层次结构，使得这种理论研究更加复杂，当然也因而更具吸引力。目前已形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计算机等模糊数学分支。应用研究主要是对模糊性之内在规律的探讨，对模糊逻辑及模糊信息处理技术的研究。模糊数学的应用范围已遍及自然科学与社会科学的几乎所有的领域。特别是在模糊控制、模式识别、聚类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著的成就。

伴随着模糊聚类理论的形成、发展和深化，针对不同的应用，人们提出了很多模糊聚类算法，比较典型的有基于目标函数的模糊聚类方法、基于相似性关系和模糊关系的方法、基于模糊等价关系的传递闭包方法、基于模糊图论的最小支撑树方法，以及基于数据集的凸分解、动态规划和难以辨别关系等方法。其中最受欢迎的是基于目标函数的模糊聚类方法，该方法把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。

该方法设计简单，解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于在计算机上实现。因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点。在基于目标函数的聚类算法中，FCM类型算法的理论最为完善、应用最为广泛。FCM类型的算法最早是从“硬”聚类目标函数的优化中导出的。

2、基于粒度的算法

从表面上看，聚类和分类有很大差异———聚类是无导师的学习，而分类是有导师的学习。具体说来，聚类的目的是发现样本点之间最本质的抱团性质的一种客观反映；分类需要一个训练样本集，由领域专家指明，而分类的这种先验知识却常常是主观的。如果从信息粒度的角度来看，就会发现聚类和分类的相通之处: 聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行计算的。在粒度原理下，聚类和分类的相通使得很多分类的方法也可以用在聚类方法中。作为一个新的研究方向，虽然目前粒度计算还不成熟，尤其是对粒度计算语义的研究还相当少，但是相信随着粒度计算理论本身的不断完善和发展，在今后几年，它将在数据挖掘中的聚类算法及其相关领域得到广泛应用。

3、量子聚类

在现有的聚类算法中，聚类数目一般需要事先指定，如Kohenon自组织算法、K-means算法和模糊K-means聚类算法。然而，在很多情况下类别数是不可知的，而且绝大多数聚类算法的结果都依赖于初值，即使类别数目保持不变，聚类的结果也可能相差很大。受物理学中量子机理和特性启发，可以用量子理论解决此类问题。一个很好的例子就是基于相关点的Pott自旋和统计机理提出的量子聚类模型。它把聚类问题看做一个物理系统。并且许多算例表明，对于传统聚类算法无能为力的几种聚类问题，该算法都得到了比较满意的结果。

量子力学研究的是粒子在量子空间中的分布, 聚类是研究样本在尺度空间中的分布情况。很多文献对量子聚类(Quantum clustering,QC)算法进行了深入的研究, 并应用于生物信息学的研究。QC 算法不需要训练样本, 是一种无监督学习的聚类方法。又因为它是借助势能函数, 从势能能量点的角度来确定聚类中心的, 所以它同样是基于划分的。实践已经证明QC 算法有效。

4、核聚类

核聚类方法增加了对样本特征的优化过程，利用Mercer核把输入空间的样本映射到高维特征空间，并在特征空间中进行聚类。核聚类方法是普适的，并在性能上优于经典的聚类算法，它通过非线性映射能够较好地分辨、提取并放大有用的特征，从而实现更为准确的聚类；同时，算法的收敛速度也较快。在经典聚类算法失效的情况下，核聚类算法仍能够得到正确的聚类。

近年来核方法被用在聚类分析中，Tax将支持向量方法用于数据域描述(即单一分类)中，提出了基于Gauss核的SVDD(Supprot Vector Domain Deseription)算法和支持向量聚类(support vector Clustering，SVC)

5、谱聚类

传统的聚类算法,如k-means算法、EM算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。为了能在任意形状的样本空间上聚类,且收敛于全局最优解,学者们开始研究一类新型的聚类算法,称为谱聚类算法(Spectral Clustering Algorithm)。该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLSI 设计等领域,最近才开始用于机器学习中,并迅速成为国际上机器学习领域的研究热点。

谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。但由于其涉及的理论知识较多,应用也还处于初级阶段,因此国内这方面的研究报道非常少。

四、参考文献

• JiaweiHan, MichelineKamber, JianPei, et al. 数据挖掘概念与技术[M]. 机械工业出版社, 第三版.
• 郭晓娟、刘晓霞．层次聚类算法的改进及分析，计算机应用与软件，第25卷第6期
• 甘丽．数据挖掘中的聚类分析研究．沿海企业与科技．2008年第03 期(总第94 期)
• 贺玲、吴玲达、蔡益朝．数据挖掘中的聚类算法综述．计算机应用研究,2007,(01):16-19
• 李东琦．聚类算法的研究．西南交通大学学位论文．2007.5.
• 郑洪英.数据挖掘聚类算法的分析和应用研究．重庆大学学位论文．2007.6
• 李明华、刘全、刘忠、郗连霞．数据挖掘中聚类算法的新发展．计算机应用研究．2008,25(1)