几种经典聚类算法的比较研究_吕晓丹.pdf

数据库系统设计Database System Design电子技术与软件工程Electronic Technology&Software Engineering226聚类算法是一种无监督学习算法，与监督学习不同的是，无监督学习算法的数据都是没有标签（类别）的。聚类算法的最终目标是通过样本点的内部特征将数据集中的样本点划分为若干个子集，每一个子集称之为一簇。那么，聚类的最优准则就是：簇内相似度高且簇间相似度低1。作为一种深入挖掘数据内在联系的算法，聚类分析已经被广泛应用在机器视觉、图像处理、自然语言处理、生物信息、模式识别等众多领域中2-3。通常，我们将经典聚类算法分为四大类：（1）基于划分的聚类算法：这种方法首先指定簇的数量 k，然后按照一定的划分标准（比如欧式距离）将所有数据点进行划分，使得每个簇内部的点之间相似度高且不同簇的数据点间相似度低。典型的有：K-means算法、K-medoids 算法、K-modes 算法。（2）基于密度的聚类算法：这种方法不需要事先指定簇的数量 k，而是根据密度将处于同一密度区域的点归结为一类，同时忽视密度低或者孤立的数据点。代表性的算法有：DBSCAN算法、Density Peak Cluster算法。（3）基于模型的聚类算法：这种方法首先构建数据集遵守的函数模型，然后通过最小化误差的方法来确定模型参数和簇的划分。代表性的算法有：Spectral Cluster 算法、高斯混合模型、神经网络聚类等。（4）综合聚类算法：这种方法融合了两种以上的数学思想或聚类算法，形成新的综合性聚类算法。代表性的算法有：FCM 算法、模糊神经网络聚类算法。本文从四大类聚类算法中分别选取 K-means 算法、Density Peak Cluster 算法、Spectral Cluster 算法和 FCM算法作为比较研究对象，再从算法原理和对比实验两个方面来分析这几种经典算法的异同和优略。1 算法原理分析1.1 K-means算法K-means 算法又称 K-均值算法，它是由美国加州大学的 J.B.MacQueen 在 1967 年提出来的。K-means 的主要算法流程如下4：（1）K-means 算法会预先设定簇数为 K。（2）随机选择 K 个样本点作为初始簇中心，并计算数据集中每个样本点到簇中心的欧几里得距离。（3）根据“就近原则”将样本点分配到距其最近的簇中心所在的簇中。（4）重复执行第 2 步和第 3 步的内容，直到达到最大的迭代次数或者簇中心不再变化为止。由上述 K-means 的算法流程可知，在 K-means 中将两点间的欧式距离作为样本点间相似度的度量标准，也就是说两个样本点的空间欧式距离越近，则它们相似度越高，也就会被划分到同一个簇中去。K-means 算法简单直观、易于实现、便于解释。当簇是团状、球状且子簇之间存在一定距离时，便可以体现出 K-means 算法良好的聚类效果，这是因为 K-means 算法以欧式距离作为相似度的度量标准。但是，由于 K-means 算法采用贪心策略，会导致算法陷入局部最优解。与此同时，当以欧式距离作为相似度度量标准时，就会导致 K-means 算法对初始点的选择和噪声点离群点都十分敏感，导致算法效果不太稳定。1.2 Density Peak Cluster算法几种经典聚类算法的比较研究吕晓丹（湖北汽车工业学院汽车工程师学院 湖北省十堰市 442002）摘要：本文选取 K-means、FCM、Spectral Cluster、Density Peak Cluster 四种经典聚类算法作为研究对象，从理论和实验两个角度对它们进行比较研究。首先，本文介绍了聚类的含义、准则及应用；其次，本文分别阐述了四种算法的原理，并从理论角度分析它们的异同；再次，本文在 UCI 数据集上对四种算法执行了对比实验，比较它们的聚类准确率；最后，根据理论分析和对比实验的结果，得出四种算法适应不同类型数据集的结论。关键词：K-means；FCM；Spectral Cluster；Density Peak Cluster；比较研究数据库系统设计Database System Design电子技术与软件工程Electronic Technology&Software Engineering227Density Peak Cluster 算法（简称 DPC 算法）又称密度峰值聚类算法，是由 Alex Rodriguez 和 Alessandro Laio 两位学者于 2014 年提出的，相关成果发在 SCIENCE期刊上5。DPC 算法蕴含着一个假设，即：假设聚类中心拥有较高的本地密度并且距离其他高密度点有相对较远的距离。其次，通过公式（1）和公式（2）分别计算每个点的本地密度和与所有高密度点的相对距离的最小值。紧接着，将所有点的本地密度 和相对距离最小值 绘制成一张决策图，手动选取拥有高 值和较高 值的点作为聚类中心点，最后将剩余的点依照“就近原则”分配到相应中心点所在的簇中。i=j(dij-dc)（1）i=min(dij)for j:ji （2）DP 算法考虑了数据空间分布的特点，因此可以在对密度敏感的数据集上取得不错的效果，与此同时它的算法复杂度比 K-means 低。但是，由于它需要提前计算所有点的本地密度和相对距离，所以内存开销较大，不便于大数据量的处理。1.3 Spectral Cluster算法Spectral Cluster 算法又名谱聚类算法，它的思想源自图划分理论。在图论中，将数据集中的所有样本点都视作图的顶点 V，将样本点之间的连接视作图的加权边E，于是可以形成一张加权图 G（V，E）。聚类问题实质上就是图 G 的划分问题，图划分成的一个个子图就是数据聚类后得到的一个个簇。根据最优的聚类准则，最优的图划分方法具有如下特点：（1）划分后不同子图之间边的权重和尽可能小。（2）划分后同一子图内部边的权重和尽可能大。此时，定义一个目标函数 RatioCut：（3）在式（3）中，A1.Ak 代表分割后形成的 k 个簇，代表簇 A 和其他簇的相似度，代表簇 Ai 的节点数。谱聚类问题就转换成求 RatioCut 最小值的问题，然而直接求解往往十分困难，可以通过定义图 G 的相似度矩阵 W（公式（4）、拉普拉斯矩阵 L（公式（5）及 n 维向量 f（公式（6），然后经过一系列公式的推导（公式（7），最终将求 RatioCut 最小值的问题转换成在需满足公式（8）和公式（9）的前提条件下求解拉普拉斯矩阵最小特征值的问题。具体推导过程如下：（4）L=D-W （5）（6）（7）（8）（9）此外，由于拉普拉斯矩阵是一个半正定对称阵，所有的特征值都大于等于 0。而当 L 的特征值是 0 时，对应的特征向量是单位阵 E，很明显 E 不满足公式（9）中的限定性条件。根据 Rayleigh-Ritz 原理，第 2 小的特征值乃至于第 n 小的特征值都是可用的。于是，得到如下谱聚类算法流程6：（1）构建一个相似度矩阵 W，其中第 i 行第 j 列元素 Wij代表样本点 i 和样本点 j 之间的相似度，它的计算方法见公式（4）。（2）根据公式（5）计算相似度矩阵 W 的度矩阵和拉普拉斯矩阵 L。（3）求得拉普拉斯矩阵 L 的全部特征值，并按照递增的顺序排列。（4）获得前 k 个特征值和对应的特征向量，将这k 个特征向量组合成一个 n*k 的矩阵，对该矩阵的每一数据库系统设计Database System Design电子技术与软件工程Electronic Technology&Software Engineering228行执行 K-means 聚类，最终每行的类别就代表原始空间中每一个样本的类别。从公式（4）可以看出谱聚类改进了相似度的度量方式，从一定程度上考虑了数据空间分布的特点，适合非凸流行数据；从第 4 步可以看出，谱聚类实际上做了一定的降维操作，因而对高维数据有着较好的处理效果。但是，谱聚类仍然存在计算量大、时间复杂度和空间复杂度高、数据的先验信息利用不足等问题。1.4 FCM算法FCM算法的英文全称是Fuzzy C-means Clustering，它是一种模糊聚类算法，融合了模糊数学的软化分思想和聚类分析的原理。不同于硬划分理论，FCM 算法通过隶属度来确定每个数据点 xi 属于某一类 j 的概率 uij，也就是说一个点可能有 40%的概率属于 A 簇，也有60%的概率属于 B 簇，而不是百分之百属于某一个簇。FCM 算法的主要流程是7：（1）指定聚类数目 k 和模糊系数 m，并初始化隶属度矩阵 U。（2）更新聚类中心 vj （10）（3）更新隶属度矩阵 （11）（4）重复步骤 2 和步骤 3，直到两次得到的隶属度矩阵差距较小时或者达到最大迭代次数。2 对比实验验证为了将四种典型聚类算法的效果进行更为直观的对比，本部分将进行聚类准确率对比实验。本文中的实验环境含 PC 机一台，具体配置如下：（1）CPU 为 Intel(R)Core(TM)I5-6200U CPU 2.30GHz 2.4khz;（2）内存空间是 4G;（3）编程软件是 MATLAB;（4）编程语言是 m 语言。本实验采用单一变量原则，对 K-means 聚类算法、FCM 聚 类 算 法、Spectral Cluster 算 法、Density Peak Cluster 算法在三个 UCI 数据集8上进行聚类准确率的定量对比分析。所谓 UCI 数据集，指的是由加州大学欧文分校提出的一种适合模式识别和机器学习方向的开源数据集，很多学者会选择使用 UCI 上的数据集来验证自己算法的正确性。到目前为止，UCI 共维护了 622 个数据集，并且在持续更新中。这些数据集主要分为二值分类问题、多分类问题以及回归拟合问题。本文选取 UCI 数据集中的 BreastCancer、Transfusion和 Ecoli 三个子集。其中，Breast Cancer 数据集是由威斯康星大学诊疗中心和计算机科学研究所发布的乳腺癌数据集，它包括了乳房肿块的 FNA 数字化图像的计算特征。具体包含半径、文理、周长、面积、平滑度、紧凑度、凹度、凹点、对称、分形维数等十个实值特征和一个标签信息（良性或者恶性）。Transfusion 数据集是一个献血者数据库。它包括最近一次献血后的月数、献血总次数、献血总血量、首次献血后的月数等四个特征和一个是否在 2007 年 3 月献血的标签。Ecoli 数据库给出大肠杆菌基因组中每个ORF（潜在基因）特征的数据。提供了序列、同源性（与其他基因相似）、结构信息和表 1：UCI 数据集简介数据集名称特征类别数样本数数据来源BreastCancer102683UCITransfusion42748UCIEcoli72272UCI表 2：实验结果-聚类准确率数据集名称K-meansFCMSpectral ClusterDensity Peak ClusterBreastCancer0.34990.60320.34410.3438Transfusion0.26070.29280.52670.2396Ecoli0.02210.20220.18750.7045数据库系统设计Database System Design电子技术与软件工程Electronic Technology&Software Engineering229功能等七个特征。三个 UCI 数据集的简介如表 1 所示。依照惯例，我们采用聚类准确率作为衡量算法优略的核心指标，将四种聚类算法在三个 UCI 数据集上的聚类准确率用表格的方式呈现出来。由表 2 可以看出：四种算法在三个数据集上的表现各有千秋。在 BreastCancer 数据集上，FCM 算法的聚类准确率最高且达到 0.6032，这一数据说明有超过60%的数据点会被正确聚类；在 Transfusion 数据集上，Spectral Cluster 算法则表现最为突出，其聚类准确率达到了 0.5267；