SCMDFC算法研究与应用

SCMDFO算法研究与应用赵双柱(兰州文理学院电子信息工程学院甘肃730000)【摘要】针对SCMD算法存在的两大不足提出了改进,改进的半监督聚类算法在原算法的基础上添加对两种问题的处理,问题一的解决方法是查找可能会丢失的簇,添加Es,以解决先验约束不充分时不能检测到所有的簇;问題二的解决方法是分配边界簇,以解决簇内多密度问題。实验证明 SCMDFC算法在处理多密度数据集时具有良妤的聚类质量。【关键词】SCMD; SCMDFC;多密度数据集中图分类号:TP311.13;TP39141文献标识码:A文章编号:1009-6833(2014)03-085-02Research and application of SCMDFC algorithmAbstract: At proposing improvements of the two existing deficiencies of SCMD algorithm Improved semi-supervised clusteringalgorithm adds processing of two kinds problem based on the original algorithm Solution of the first problem is in search of the clusterthat can be lost and adding the Eps in order to solve the problem of hardly fully detecting all the cluster in the condition of insufficiencyof a priori constraint Solution of the second problem is to allocate boundaries to solve the problem of cluster-headsmultidimensional Experiment proofs that SCMDFC algorithm has better clustering quality in dealing with a multidimensional data setKeywords: SCMD: SCMDFC; multidimensional data se0引言类算法 SCMDFC。该算法的主要思想是:在原算法的基础上添DBSCAN算法[是聚类分析中最经典的基于密度的聚类加对这两种问题的处理;问题一的解决方法是:充分利用给定分析算法,但算法存在一些问题:聚类质量对参数敏感;不能的先验知识,从约束条件集合中挖掘与可能会被丢失的簇的相处理多密度数据集。针对 DBSCAN缺点,学者们提出了改进算关信息,从中提取其密度信息,从而查找出所有的簇。问题法,如 GDBSCAN算法2], KNNCLUST算法,这些算法在执的解决方法是:簇内密度不均匀时,该簇会被聚为多个子簇行过程中不能获得任何关于数据项的类属信息,因而通常被看但在这些子簇中,有一个较大的簇是原来簇的主体部分,通过作是一种无监督学习。定的再分配准则将周围的小的子簇合并到较大的簇中,从而1半监督聚类算法ScMD获得自然的簇结构。1.1SCMD算法概述2.2算法详细描迷半监督聚类算法 SCMDI3]是 Yongqiang Yu等人针对多密度具体来说, SCMDFC算法主要增添了两种方法来弥补数据集提出的。算法中的先验信息以成对约束( must-link和SCMD算法的不足cannot-link)形式给出。算法中涉及到两个定义:k最近邻距离(1)查找可能会丢失的簇,添加Fps和k最近邻列表,分别用 P-Kdistance和 P-Kneighbor表示由SCMD算法可知,如果一个簇中不包含有提供的SCMD算法主要包括三部分内容:首先根据 must-link集计 must-link约束,则这个簇可能不会出现在聚类结果中,因为它算出参考Eps列表;然后根据 cannot-link条件从参考Eps列表的Eps没有被计算出来所以本文试图添加它的EpS到参考Eps中选择不同密度分布的代表Eps;最后,以这些代表Eps为参列表中来解决这个问题,关键是如何查找这样的簇。这里,假数的多阶段 DBSCAN算法运行于数据集,得到最终聚类结果。定这个簇虽然不包含 must-link约束,但是包含 cannot-link约束12SCMD算法存在的缺点中的点。根据约束的传递性,(A,B)属于must-link集表明数SCMD算法在一些数据集上确实有着良好的性能,但是仍据点A和B属于同一个簇,(B,C)也是一样,我们可以得出存在两个问题数据点A和C属于同一个簇。属于 cannot-link集,表(1)先验约束不充分时不能检测到所有的簇明数据点A和B不可能在同一个簇中。如果(A,C)是一个SCMD算法在聚类过程中用到的所有Eps都是从 must-link must-link约束,则数据点B和C也不可能在同一个簇中,我约束中计算而来,所以,如果有一个簇不包含 must-link约束,以从约束集合中得到传递闭包,则只包含一个数据点P的则这个簇可能不会出现在最终的聚类结果中。尤其是当这个不闭包就属于在聚类结果中可能会被丢失的簇,也就是 SCMDFC包含 must-link约束的簇是数据集中最稀疏的簇的时候,它一定算法要检测的簇,然后,把 P-Kdistance定义为该簇相应的Eps会被丢失,而簇中的所有点被分配成噪声。而实际情况是,专并将其加入到参考Fps列表中,这样,簇结构将不会丢失。家或者用户并不总能提供出数据集中所有簇的 must-link约束。(2)分配边界簇,解决簇内多密度问题(2)不能处理簇内多密度数据集定义1:(边界簇)一个簇C中的数据点数目小于K时,SCMD算法不能处理簇内密度不均的情况。而实际存在的这个簇是边界簇。即,CκK数据集合中,簇中间密集而边缘稀疏的情况又是很常见的,这为什么簇内数据点数目小于k的簇就是边界簇呢?它不也是一种多密度表现形式。对于簇之间密度不同的数据集定就位于某个较大的簇的边界,也许它是远离其他簇的一个独SCMD算法有良好的性能,因为它能够计算不同密度的不同立的簇呢?本算法中是不可能出现这种情况。一个簇必然含有Eps。而同理,对于一个密度不均的簇,用SCMD算法可以得个或多个核心点,因为簇是由核心点根据直接密度可达的规到两个或多个Eps,这样这个簇会被分割成几个小的子簇则扩展来的中国煤化工 Minpts(本算法中2基于极少约束的多密度半监督聚类算法 SCMDFC是k)个数捭则它的核心点不21算法主要思想可能有kCNMH小于k。所以该簇针对SCMD算法的不足,本文提出了一种改进的半监督聚中没有核心点。反证证得簇成员数目小于k的簇不是一个独立20144国安度与画用技术·应用的簇,而是位于某个较大的簇的边界。中的数据被分配成了噪声,如图2所示,而算法 SCMDFC仍能边界簇形成的原因是真实世界中的数据集是多密度的,簇精确地发现四个簇,如图2所示。的密度不均匀,且通常是中间密度高边界密度低。SCMD算法(2)簇内多密度情况的第三步,EpS值按升序排序,当较小的Eps作为参数用于扩数据集Data2包含1938个数据。该数据集具有三个自然的展簇时,某个簇中间绝大多数点被分配为同一个簇标签,而周簇结构且包含噪声,每个簇中的数据都是高斯分布的,也就是说簇中心密度高边缘密度低。设置K=20,实验结果显示应用前被分配为噪声的一个或多边界点变成核心点开始进行簇扩SCMD算法聚类三个簇中的大部分点都被正确分配,但簇边界展,但这些要扩展的点之前已经被标记,所以就形成了成员数的点被聚成了一些小的簇。改进的算法可以有效地发现三个完目小于k的边界簇整的簇,并正确的识别噪声边界簇就是 SCMDFC算法所要查找的需要再分配的小的3结论子簇。通过定义可以检测边界簇。查找到边界簇后,算法把边本文提出的 SCMDFC算法充分挖掘成对约束集中所包含界簇分别分配给距离它们相对较近的较大的簇。的信息,在 must-link集不充分的条件下,仍能完整査找到所有2.3实验结果及分析的簇结构,而且通过一定的再分配准则解决簇内多密度问题下面通过SCMD算法与改进算法 SCMDFC的实验对比,但也存在不足,在 must-link和 cannot-link约束均不充分的条件来分析 SCMDFC算法的优越性。我们选择了两个数据集作为实下,不能查找到全部的簇结构。在今后的研究工作中,希望能验数据集,均为多密度数据集,且含有噪声。实验结果中,不有进一步的改进。同的颜色结合不同的形状代表不同的簇,其中黑色圆点代表噪参考文献(1)成对约束( must-link)不充分情况[1]Martin Ester, Hans-Peter Kriegel, Jorg Sander, et al. ADensity-Based Algorithm for Discovering Clusters in Large SpatialDatabases with Noise[C]. In Proceedings of andInternationalConference on Knowledge Discovery and Data Mining( KDD深■■各96)1996:226-231[2Jorg Sander, Martin Ester, Hans-Peter Kriegel,etal Density-Based Clustering in Spatial Databases: The AlgorithmGDBSCAN and Its Applications[l Data Mining and Knowledge图1SCMD算法运行于Data1图2改进的算法运行于 DatalDiscovery.1998,2(2):169-194数据集 Datal(如图1和图2所示),包含1707个数据,[3 JYang-QiangYu, Tian-QiangHuang Gong-De Guo,et具有三种密度分布、四个簇结构,且包含噪声。其中两个方形al Semi-supervised clustering algorithm for multi-density and的簇具有相同的密度分布,“∞”形的簇是最稀疏的。设置k=6complex shape dataset[C]. In Chinese Conference on Pattem如果 must-link约束充分,即每种密度分布的簇中都至少包含Recognition(CCPR08)2008:1-6个 must-link约束,则SCMD算法和 SCMDFC算法均能有效作者简介:地发现簇结构。然而,当“∞形的簇中的 must-link约束没有提双柱(1972—),女,甘肃古浪,兰州文理学院电子信息工程供时,实验结果显示SCMD算法只能找到三个簇,“∞”形的簇学院讲师,从事计算机教学。(上接第84页)同样的个人计算机的处理能力也越来越出众,哪怕现在一个小3.2P2P下載小的手机都比前几年的PC处理速度要快很多,我们只需要很早期的下载技术不够成熟的时候,人们只能从固定服务器短的时间就可以看到网络带给我们更多的便利。另外,虽然计载自己想要的东西,随着P2P技术的发展,实现了资源高度算机远程网络通信技术能够带给我们极大的便利,但是我们不共享,也减轻了服务器的负载能忽略计算机网络安全方面的问题,因为网络通信技术已经与3、3流媒体技术我们的生活息息相关,倘若有人利用网络漏洞,就会给我们的早期的视频保存在服务器,人们只能通过下载到本机观看,生活造成很大的麻烦,网络通信改变生活,技术拯救世界。现在随着流媒体技术的成熟,实现了在线看高清电影,可以边参考文献:下载边看,不用等整整一部电影下载完毕再看。]李询涛计算机远程网络通讯技术的研究计算机光盘软件34电子公告板(BBS)与应用,2013(11)人们在网上公开的发表自己言论,表达自己的看法,早期比凹2]周亚峰计算机远程网络技术探析计算机光盘软件与应用,较有名的有猫扑、天涯等等,现在比较流行的就是百度贴吧了。2013(07)953.5博客、微博3]吕悦松计算机远程网络通讯技术在实际生活中的应用电实时发表自己的状态,关注自己朋友的信息子制作,2013,(05)36网络游戏[4]周山计算机远程网络通讯技术在实际生活中的应用硅谷,早期的网络游戏比较单一,玩起来需要打字输入命令,没2013(11)有图形化界面,随着3D技术以及网络技术的发展,人们实现作者简介:了大型3 DMMORPG网络游戏,丰富了业余生活。俞星磊(1984—),男,江苏太仓,本科,助理工程师,研究方4总结向:信息管理与信息技术。通过本文的介绍,相信读者可以对现阶段网络技术的应用庞燕萍(194中国煤化工工程师,研究方有了一个初步的认识。其实,网络通信技术发展的速度非常快向:计算机科学HCNMHG86丹敌真与用2014