《基于密度峰值的混合型数据聚类算法设计-李晔.pdf》由会员分享，可在线阅读，更多相关《基于密度峰值的混合型数据聚类算法设计-李晔.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Journal of Computer Applications计算机应用，2018，38(2)：483490，496IsSN 100l一9081CODEN JYIIDU20180210http：wwwjogacn文章编号：1001-9081(2018)02048308 DOI：1011772jissn100190812017082053基于密度峰值的混合型数据聚类算法设计李晔12，陈奕延1，张淑芬2(1中国市场学会服务质量专业委员会，北京100048； 2河北省数据科学与应用重点实验室(华北理工大学)，河北唐山063210)(通信作者电子邮箱townjam_sovietnia163C01)摘
2、要：针对k-prototypes算法无法自动识别簇数以及无法发现任意形状的簇的问题。提出一种针对混合型数据的新方法：寻找密度峰值的聚类算法。首先，把CFSFDP(Clustering by Fast Search and Find ofDensity Peaks)聚类算法扩展到混合型数据集，定义混合型数据对象之间的距离后利用CFSFDP算法确定出簇中心，这样也就自动确定了簇的个数，然后其余的点按照密度从大到小的顺序进行分配。其次，研究了该算法中阚值(截断距离)及权值的选取问题：对于密度公式中的闽值，通过计算数据场中的势熵来自动提取；对于距离公式中的权值，利用度量数值型数据集和分类型数据集聚类趋
3、势的统计量来定义。最后通过在三个实际混合型数据集上的测试发现：与传统k-prototypes算法相比，寻找密度峰值的聚类算法能有效提高聚类的精度。 关键词：聚类分析；混合型数据；数据场；聚类趋势；密度峰值中图分类号：TP3016 文献标志码：ADesign of mixed data clustering algorithm based on density peakU Yel”，CHEN YiyanP，ZHANG Shufen2(1Service Query Specialty Committee，Chinese Association ofMarket D泖却tnertt，&讲增10004
4、8，Chna；21tebei研Laboratory of Data Science and Applwation(North China University of Science and Technology)，Tangshan ttebei 063210，Chna)Abstract：Focusing on the issue that k-prototypes algorithm is incapable of identifying automatically the number ofclusters and discovering clusters with arbitrary sh
5、ape，a mixed data clustering algorithm based on searching for density灿Was proposedFirstly，CFSFDP(Clustering by fast Search and Find of Density Peaks)clustering algorithm w鹪extended tomixed datasets in which the distances between mixed data objects were calculated to determine the cluster centers by u
6、singCFSFDP algorithm，that is，the number of clusters Was determined automaticallyThe rest points were then assigned to thecluster in order of their density from large to smallSecondly，the selection method of threshold and weight in the proposedalgorithm was introducedIn the density formula，the thresh
7、old(cutoff distance)was extracted automatically by calculatingpotential entropy of data field；in the distance formula，the weight Was defined through certain statistic which Can measureclustering tendency of numeric datasets and categorical datasetsFinally，experimental results on three real mixed dat
8、asetsshow that compared with k-prototypes algorithm，the proposed algorithm can effectively improve the accuracy of clusteringKey words：duster analysis；mixed data；data field；clustering trendeney；density peak0 引言随着互联网技术的迅速发展，人们采集与获取信息的能力大大提高。当海量信息出现时，人们希望从繁多复杂的数据中得到有价值的信息。聚类分析是数据挖掘中一个极其重要的分支。文献1指出聚类是一
9、个把数据对象划分成子集的过程，每个子集是一个簇，使得簇中的对象彼此相似，但与其他簇中的对象不相似。根据数据对象(数据点)每个属性值的数据类型，可把数据分为数值型数据、分类型数据(无序分类变量构成的数据)及混合型数据。很多科研工作者为保证数据分析的普适性和全面性，采用的调查数据大多为既含数值型属性又含分类型属性的混合型数据。由于面对的数据类型日益多样化，聚类分析也需要处理不同类型的数据，然而目前的聚类算法大多是针对数值型数据提出的，也有一部分可用来处理分类型数据，但能够处理混合型数据的聚类算法却相对较少。文献2指出这两种属性在属性值的取值范围、分布和特点上差异较大，许多研究人员认为针对单一属性数
10、据的传统聚类算法已不适用于混合属性数据。因此，设计更多针对混合型数据的聚类算法是聚类分析中一项极具意义的工作。最早用于混合型数据的聚类算法是k-prototypes算法p1，该算法结合了k-means和k-modes两种方法，故而不像很多传统的聚类算法一样只能处理单一属性的数据集。另外，该算法具备了k-means算法高效性的特点，应用十分广泛，尤其是对于大型数据集也十分有效。虽然k-prototypes算法有很多优点且被人们广泛使用，但仍存在以下一些不足：1)无法实现对数据分布的适应性。对于簇中的数值部分，k-prototypes算法同k-means算法一样只能发现球状分布的簇。2)无法自动确
11、定簇的个数。3)没有考虑聚类过程中的模糊性问题。很多情况下，数据对象很可能同时分属多个簇，有时簇边界附收稿日期：20170810；修回日期：201709一11。 基金项目：河北省数据科学与应用重点实验室开放课题资助项目(20170320002)。作者简介：李哗(1992一)，女，河北保定人，博士研究生，CCF会员，主要研究方向：机器学习、数据分析；陈奕延(1986一)，男，北京人，工程师，经济师，博士研究生，CCF会员，主要研究方向：统计建模、技术经济；张淑芬(1972一)，女，河北唐山人，教授，硕士，CCF会员，主要研究方向：云计算、数据安全、隐私保护。万方数据计算机应用 第38卷近的数据对
12、象的归属问题会很模糊，而k-prototypos算法并未考虑这一点。4)对混合属性数据簇原型(中心)的表示可能造成严重的信息丢失。5)没有考虑每个属性对聚类结果影响的差异性。6)受初始值的影响很大。由于k-prototypes算法是一种迭代算法，只能收敛于局部最优解，因此对初值的选取十分敏感。近年来有不少研究者纷纷对上述缺点进行了不同程度的改进。针对缺点3)：文献4在k-prototypes算法的基础上提出了fuzzy k-prototypes聚类算法，通过在k-prototypes算法中引入模糊理论的概念，增加了数据对象分配到簇原型时的不确定性，使改进的算法具有分析模糊性和不确定性问题的能力
13、；文献5中则认为常用于混合型数据模糊聚类的fuzzyk-prototypes算法仅仅是在原始的模糊C均值(Fu=y CMeans，FCM)聚类算法中使用了不同的相异性函数，从而使其可用于同时具有数值型属性和分类型属性的混合型数据，于是该文中提出了一个全新的FCM-type算法，采用全概率相异性函数来处理混合属性数据，通过交叉熵使得模糊目标函数正则化，最终达到提高聚类精度的目的。针对缺点4)，文献6提出了fuzzy k-prototypes聚类算法的一种改进算法，该算法改进了簇原型的选取方式，对每个有P种不同取值的分类型属性，将其看成是一个P维的属性，迭代过程中原型的计算也要将每个分类型属性看成
14、一个P维的属性，按每个分类型属性的可能取值在所属簇中的比例来定义簇原型，从而也间接改变了分类型属性的相异性度量方式。这样的原型选取方式包含了更多的数据信息，从而提高了聚类的精度。针对缺点5)：文献7提出了基于聚类相似性的算法sBAC算法，它是一个凝聚层次聚类算法，引入了一个相似度的度量方式来计算数据对象间的相似性；文献8提出了基于熵权法的针对混合属性数据的聚类算法，改进了数据对象之间距离的度量方式，利用信息熵作为各个属性的权值，从而提高了聚类的精度和稳定性；文献9中利用类内和类间信息熵来度量各个属性在聚类过程中的作用，由此给不同的属性分配不同的权重，从而使得数据对象可以在统一的框架下更客观地度
15、量彼此之间以及对象与簇原型之间的相异性。针对缺点6)，文献10对k-prototypes聚类算法初始点选取方法作了改进，通过对模糊k-prototypes的分析，分别对数值型属性部分和分类型属性部分进行划分，在每个划分中选取初值，最后将两部分和在一起组成初始的簇原型。该方法降低了数据对初值的敏感度，从而减少了聚类算法的迭代次数，同时还能避免选取到相同的初始簇原型。虽然目前国内外针对缺点3)一6)有诸多改进，但却鲜有针对缺点1)和2)的改进算法，故本文主要针对这两个不足之处提出一种可用于混合型数据的新型聚类算法。2014年，文献11提出一种用于数值型数据的CFSFDP(Clustering by
16、Fast Search and Find of Density Peaks)聚类算法，该算法具有能发现任意形状数据集且能自动确定簇数的优点，但使用范围局限于数值型数据。之后文献12进行了基于CFSFDP算法的模糊聚类研究；3c献13提出了基于近邻距离曲线和类合并优化CFSFDP的聚类算法；文献14提出一种基于簇中心点自动选择策略的密度峰值聚类算法；文献15提出一种基于粒子群算法的CFSFDP算法。这些改进虽然提高了CFSFDP算法的性能，但仍然不能用于混合型数据的聚类。因此，本文首先重新定义了混合型数据之间的距离，接着把CFSFDP算法扩展到混合型数据，这样可以克服k-prototypes算法
17、相应的1)、2)两个缺点，使得该算法能够自动确定簇数，并且对于任意形状的簇都有一个比较满意的聚类效果。接着对算法复杂度进行分析，并且研究了算法中的阈值d。及权值7的选取问题，分别利用数据场中的势熵和可度量数值型及分类型数据集聚类趋势的统计量来确定这两个参数。最后用文献16中的三个混合型数据集作为实验对象，通过和kprototypes算法的比较来验证针对混合型数据的寻找密度峰值算法的有效性。1 寻找密度峰值的聚类算法本文把CFSFDP算法扩展到混合型数据，提出一种可用于混合型数据的寻找密度峰值聚类算法，该算法的基本思想是簇中心应该同时满足以下两点：1)簇中心的密度比它周围的点的密度更大；2)簇中
18、心离比自身密度大的点的距离较远，即不同的簇中心之间的距离相对较远。该想法是整个聚类过程的基础，找到簇中心以后，也就自动确定了簇的个数。对于任意一个非簇中心数据点i，认为点i跟所有比它密度更大的点中与之距离最近的那个点属于同一个簇。该算法中簇的分配在一步中完成，这与那些通过迭代来优化目标函数的算法是不同的。11相关定义接下来介绍针对混合型数据的寻找密度峰值聚类算法中涉及的一些相关定义。考虑给定的混合型数据集S=h羔。，厶=1，2，为相应指标集，d。=dist(x；，并，)表示混合型数据集中点茗；和墨之间的距离，利用以下公式来度量：这里当P=q时，8(p，q)=O；当Pq时，8(p，g)=1。对于
19、对象i和J，石；和菇；表示数值型属性的取值，而石：和茗；表示分类型属性的取值。m，和m。分别表示数值型和分类型属性的个数。y是分类型属性的权重。对于s中的任何一个数据点并；，可为其定义Pi和6；两个量，利用这两个量可以确定出簇中心。111计算pf计算密度时常用的核函数包括截断核(Cutoff kernel)、高斯核(Ganssian kernel)和指数核(Exponential kernel)，它们的定义分别如下：圹军删一一dch=矗：三： n=exp一(略d。)2 (3)P；=exp一(如d。2) (4)式(2)(4)中的参数d。0为阈值(截断距离)，需由使用者事先指定。112计算最设qi
20、墨。为P。墨。的一个降序排列下标序，满足式(5)：P口lP屯P口 (5)然后定义驴i瓢mindq q，三 (6)。稚c进算，L占荟y+、，孙一r诸茁L叶=一Vd万方数据第2期 李晔等：基于密度峰值的混合型数据聚类算法设计至此，对于S中的每个数据点气，可利用式(2)、(3)或(4)以及式(6)为其计算(见，龟)(iIs)。根据Pi，抗的定义可知，当某个点的这两个量同时取值较大时，这个点就满足前文提到的成为簇中心的两个条件，因此可以利用以P为横轴，6为纵轴的图(称为决策图)来判断哪些点同时具有较大的P值和6值，即哪些点可以被当成是簇中心。12算法步骤及流程本节给出寻找密度峰值算法的具体流程，为了方
21、便描述，先引入一些记号。仍考虑给定的混合型数据集S=h墨。，设其包含n，(1)个簇。1)m辈，：各个簇中心对应的数据点编号，即x。，为第J个簇的中心。2)c；墨。：记录数据点所属的簇，即Ci表示s中第i号数据点归属于第C；个簇。3)R羔。：ni表示|s中所有比一的密度大的点中，与之距离最近的数据点的编号。其定义为：farg m!nd， i2nqi2 F“。 其中q篓。的含义同式(5)，表示P；是。的一个降序排列下标序。注意，n；篓。是为非簇中心的数据点而定义的，确定好簇中心后，将利用n；竺。来确定非簇中心的数据点的归类。4)h；墨。：数据点中“簇核心”(cluster core)和“簇光晕”(
22、cluster halo)的标识。一个簇中的数据点可分为“簇核心”和“簇光晕”两部分，核心部分的局部密度较大，光晕(边缘)部分的局部密度较小，常说的“离群点”就分布在“簇光晕”中。这里，若h。=1，则表示筏属于“簇光晕”中；若h。=0，则表示缸属于“簇核心”中。下面利用上述符号给出寻找密度峰值聚类算法的具体步骤。步骤1初始化及预处理。I)给定用于确定阈值(截断距离)以的参数t(0，1)。2)给定权值y。3)计算距离di，并令叱=di(i1，则将每个簇中的数据点进一步分为“簇核心”和“簇光晕”。1)初始化标记hi=0(iIs)。2)确定每个簇的边界区域。这个区域中的数据点定义如下：它们属于该簇，
23、且在与其距离不超过d。的范围内，存在属于其他簇的数据点。3)利用边界区域计算每个簇的平均局部密度上界P?：。 4)局部密度小于p；：。的点标识为cluster halo。13算法复杂度分析在针对混合型数据的寻找密度峰值算法中，给定阈值d。及权值7后，该算法的时间复杂度主要包括距离矩阵的计算，本文算法需计算n(n一1)2个距离值，n是数据集中的数据对象数，因此算法时间复杂度为0(n2)。k-prototypes算法的时间复杂度为0(f+1)kn)，其中k是簇数，n是数据集中的数据对象数，z是k-prototypes算法收敛所需的迭代次数。当n很大时，本文算法的时间复杂度可能会远高于k-proto
24、types算法。2 阈值和权值的选取从以上论述可知，新算法中可能影响最终聚类结果的因素主要有两个：1)密度公式中的阈值(截断距离)d。；2)距离公式中的权值7。接下来需进一步讨论并验证这两个因素对聚类结果的影响，并给出一个相对合理的方式来选取这两个参数，以达到最理想的聚类效果。21阈值d，的选取对于d。的选取，文献11给出了一种一般性的方法：选取一个d，使每个数据点的平均“邻居”个数大约为数据点总数的1一4，这里的“邻居”是指与其距离不超过d。的点，具体的比例通常根据研究人员的经验和实际的数据集而定。以上方法需要根据个人实际经验来确定d，但通过下文的实验(这些实验的细节会在213节中介绍)可以
25、看到，聚类结果会受到阈值d的影响，而根据经验很难估计出最优的阈值以。对同一数据集，若阈值的经验估计值不同，则聚类的结果可能也不同。为了解决这一问题，使用数据场中的势熵从混合型数据集中自动提取最优的阈值d。文献17提出用数据场去描述数据空间中对象之间共同的交互作用，同时文献18一19指出对于同样的参数，数据点在稠密区域有较高的势而在稀疏区域有较低的势。可用于计算势的势函数有很多种，如高斯核、指数核、截断核等。接下来介绍如何通过数据场中的势熵计算出在不同势函数和不同数据集下的最优阈值。211数据场假设在数据空间lf2中有一个混合型数据集X=菇。，石：，菇。文献19指出受到物理上场论的影响，将J中的
26、一个数据对象当成一个在给定的任务中传播它的数据分布的物理对象，这就形成了数据场。对于一个任意的点茗i力(1=1，2，n)，场函数按如下公式定义：纯=科(xixyor (7)J=1其中：盯是一个影响因子；吁是誓的质量；K(髫)是一个单位势函数，算ixj是点i和另-+Aj之间的方位距离。Or对最终的势分布有一定的影响。K(x)给出了数据对象把它的数据分布扩散到数据场中的规则，通常情况下K(戈)选择为高万方数据计算机应用 第38卷斯核函数。212利用数据场提取最优的截断距离在式(7)中，如果数据场是一个标量场，则mj=l，当K(菇)选择高斯核函数时，戈；一巧变成略，dg表示点算；和吩之间的某种距离，
27、那么每一个点的势纯由如下公式计算：妒；=exp(一dJo)2 (8)如果式(8)中的di和新算法中d#的度量方式相同，并且如果新算法在计算密度时也选取高斯核函数，那么点薯在数据场中的势妒i和在新算法中的密度pi是等价的，也就是说式(8)与式(3)是等价的。同理，当数据场中的势函数和密度公式都取为截断核函数或指数核函数时，点兢在数据场中的势妒i和在新算法中的密度P。是也等价的。因此在寻找密度峰值的聚类算法中，阈值d。的最优化问题可以转化为数据场中影响因子or的最优化问题。我们希望找到一个影响因子or使得随机变量的不确定性达到最小。在信息论与概率统计中，熵啪3是随机变量不确定性的度量，熵越大，随机
28、变量的不确定性越大。设x是一个取有限个值的离散随机变量，其概率分布为：P(X：z。)=Pi；i=l，2，。n (9)则随机变量X的熵定义为：(x)=一Pi log(p) (10)因此，可以使用熵来最优化or。对于数据集x，如果数据场中每个点的势为妒，妒：，妒。，则熵的定义如式(11)：n，日=一等log(纯Z) (11)I 2l 其中Z=乏：妒i是一个标准化因子。 青由于取相同的核函数时，数据场中的影维既不是连续的也不是有序的。因此对每个数据集加入分类值时，我们使分类型属性可能的取值个数等于仅考虑数值型属性时二维平面中簇的个数，这样做是为了分别利用数值型属性和分类型属性进行聚类时簇的个数相等，
29、把两个属性放在一起考虑时也可以有一个统一的聚类簇数(在此先不考虑数值型属性和分类型属性的权重问题)，同时也可以在模拟实验中看到该算法自动选取的簇数是否合理。xcm(a)原始数值型数据集xlcm(b)加入类标号的数据集图l 原始数值型数据集和加人类标号的数据集IFig1 Original numeric data set and data set with the class label lxcm(a)原始数值型数据集xcmb)加入类标号的数据集图2原始数值型数据集和加入类标号的数据集Fig2 Ori西nal numeric dataset and dataset with class labe
30、l II响因子or与新算法中密度公式里的阈值噍等价，因此通过计算使熵日达到最小的影响因子or，就可以得到寻找密度峰值聚类算法中的最优阈值d。213实验和分析为了更加直观地看到选取不同阈值时的聚类结果，且为了验证基于数据场的方法提取最优阈值的合理性，本节使用具有两个数值型和一个分类型属性的混合型数据集进行模拟，数据的记录按照如下方法产生。首先生成四组二维数据点。第一组包含四个正态分布并且包含300个点(如图l(a)；第二组包含七个正态分布并且包含840个点(如图2(a)；第三组是两个环状分布并且包含400个点(如图3(a)。然后给每个点加入一个分类值，从而把这些点扩展到3维，分别记这三个数据集为
31、I、和(如图l(b)、2(b)、3(b)(文献21展示了本文所有彩色原图)。需要注意的是，一个点的分类值不能表明它是哪个类成员。事实上，这些点完全没有类，分类值仅仅代表对象在第三对于第一个数据集，把每个正态分布看成一部分，并且给每部分的大多数点分配其中一个分类型属性值，使得拥有这个分类型属性值的点数与拥有其余的分类型属性值的点数大致相等。例如在图1(b)左上角的部分中大多数点被分配属性值A，并且这部分其余的点被分配属性值B、C或者D。所有的分配都是随机的。剩下两个数据集的分类值的分配情况类似(如图2(b)、3(b)。对于同样的数据集选择相同类型的核函数和相同的距离公式，如果聚类结果不同，说明阈
32、值d。对该聚类算法的聚类结果有重要的影响。在本实验中使用数据集I，并且度量数据集中数据点的密度时选用高斯核函数。将数据集中所有对象之间的距离d。(i聚类效果彩色图【EBOL】【2017-09-09】http：Iblogcsdnnetdr_chenyiyanarticledetails77914036(CHEN Y YDesign ofhybrid data clustering algorithm based on density peak：Chromaticeffect diagrams in clustering【EBOL】【20170909】http：blogcsdnnetdr_chen
33、yiyanarticledetails77914036)【22】 ALSHAMMARY D，KHILI I，TARI Z，et a1Fractal self-similar-ity measurements based clustering technique for SOAP Web messages【J】Journal of Parallel and Distributed Computing，2013，73(5)：664676This work is partially supported by the Open Project Program of HebeiKey Laborator
34、y of Data Science and Application(20170320002)LI Ye，bom in 1992，PhDcandidateHer research interestsinclude machine learningdata analysisCIIEN Ylyan，born in 1986，PhDcandidate，engineer，economic engineerHis research interests include statistical modeling，technologi-cal economiesZHANG Shufen，born in 1972，MS，professorHer researchinterests include cloud computing，data security，privacy pmtection万方数据