聚类算法（精选12篇）
聚类算法 篇1
聚类分析是依据样本间关联的量度标准将其自动分成几个群组, 且使同一群组内的样本相似, 而属于不同群组的样本相异的一组方法[1]。聚类分析已经广泛地用在许多应用中, 包括模式识别、数据分析、图像处理, 以及市场研究。通过聚类, 能够识别密集的和稀疏的区域, 因而发现全局的分布模式, 以及数据属性之间的有趣的相互关系[2]。
模糊c-均值聚类算法 (fuzzy C-means 简称FCM) 和层次聚类算法是两种非常重要的聚类算法, 然而两种算法都存在着一些缺点。通过对两种聚类算法的分析, 本文将层次聚类算法与FCM算法结合, 先用改进的凝聚层次算法得到最佳聚类数和初始聚类中心, 然后再用FCM算法进行聚类, 以此得到更好的聚类结果。
1 凝聚层次聚类算法
1.1 凝聚层次聚类算法介绍
在层次聚类分析中, 不需要在输入中指定要分成的类的个数, 一个层次的聚类方法将数据对象组成一棵聚类的树, 根据层次分解是自底向上还是自顶向下形成, 层次的聚类方法可以进一步分为凝聚的和分裂的层次聚类。
凝聚型层次聚类又称为合并型层次聚类, 是一种自底向上的方法。首先将每一个对象看作一个簇, 然后根据某些准则合并这些原子簇为越来越大的簇, 直到所有的对象都在一个簇中, 或者某个终结条件被满足。
算法中簇间合并准则有以下几种:
(1) 单链接:d (C1, C2) =min (drs) ; r∈C1, s∈C2。
(2) 全链接:d (C1, C2) =max (drs) ; r∈C1, s∈C2。
(3) 平均链接:
(4) 重心法:d (C1, C2) =d (x1, x2) ; x1, x2分别为C1, C2的重心。
其中C1, C2是两个样本类, n1表示C1中的样本个数, n2表示C2中的样本个数, drs表示C1, C2之间的距离的字母简称。本文采用全链接法计算类间距离, 在全链接算法中, 两个类间的距离是每对样本的距离中的最大值。
层次聚类方法尽管简单, 但是一旦一组对象被合并或分裂, 就不能修正。如果在某一步没有很好地选择合并或分裂的决定, 可能会导致低质量的聚类结果。而且, 这种聚类方法不具有很好的可伸缩性, 因为合并或分裂的决定需要检查和估算大量的对象或簇。所以通常会将层次聚类算法与其他聚类算法结合, 以达到更好的聚类质量。
1.2 凝聚层次聚类算法改进
层次聚类算法每合并完一个类对象后, 就必须重新计算合并后类间的距离, 对于有大量数据的样本集而言, 计算量是惊人的。假定聚类的对象有n个, 那么按照层次聚类算法的思想, 第一次合并之前距离矩阵大小为n2, 当合并完一个类之后, 剩下的类数为n-1, 在第二次合并之前必须重新计算类与类之间的距离, 距离矩阵大小变为 (n-1) 2, 依次递推, 直至所有类合并为一个类为止, 由此可以看出层次聚类算法所需的距离矩阵存储空间是n2 阶, 而类间距离每次又要重新计算, 相应计算量为n2 阶。对于海量数据来说, 这需要耗费大量的存储空间和计算时间[3]。
基于以上考虑, 本文对算法做了一些改进。改进后的凝聚层次聚类算法描述如下:
(1) 输入n个用于分类的样本x1, x2, …, xn, 把一个样本作为一个类, 即ci={xi} (i=1, 2, …, n) , 这个样本集最初有n个聚类;
(2) 首先为所有不同的无序样本对的类间距离lk (如根据欧式距离) 构造一个距离矩阵drs (r∈ci, s∈cj) , 然后按升序对这个矩阵中的各值进行排序组成一个三元组
(3) 第一次合并距离矩阵中值最小的两个类, 即合并三元组lk (k=1) 中的两个类, 合并的新类记为类Gm (m=1) , 合并完后删除原来的两个类;
(4) 下一次合并时从距离矩阵中取次小值, 即合并三元组lk (k自增1) 中的两个类, 如果lk中的两个类的样本点不属于合并后的产生的新类Gm (m自增1) , 那么合并;如果属于, 那么把样本点所在的类按照全链接法得出新的类间距离, 如果等于lk中的距离, 那么合并, 如果不等于, 那么放弃此次的操作。每次合并结束都把样本点所在的两个类删除。
(5) 以此类推重复步骤4直至整个合并过程结束。
(6) 在合并过程中可以通过评价指标[4]或评价所获得划分的良好性, 也可以在合并结束后通过相似度阈值截取聚类效果最好的分类。
由于各类之间合并后不需要重新计算类间距离, 而是直接利用初始距离矩阵的数据, 所以节省了大量的计算时间, 从而提高算法效率。
2 模糊c-均值聚类算法
2.1 模糊c-均值聚类算法介绍
FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法, 该聚类算法是传统硬聚类算法的一种改进, 目的在于划分那些类属具有模糊性的数据, 使其结果更具客观实际性[5]。
模糊c均值聚类算法的描述如下:设数据集X={x1, x2, …, xn}, 它的模糊c划分可用模糊矩阵U=[uij]表示, 矩阵U的元素uij表示第j (j=1, 2…, n) 个数据点属于第i (i=1, 2, …, c) 类的隶属度, uij满足如下条件:∀j,
2.2 与凝聚层次聚类算法结合的FCM算法
FCM算法对初始聚类中心敏感, 并且聚类的质量和聚类数目密切相关。传统的FCM算法采用随机产生c个点作为初始聚类中心的方法, 这种方法的迭代次数多, 收敛速度慢, 而且可能使结果为局部最优解。另外FCM算法要求预先对聚类数目c进行确定, 但对于不同的数据集, 事先很难确定聚类的种类个数, 聚类数c的不同, 产生的效果就不同[6]。
通过改进后的凝聚层次聚类算法, 我们得到了基于此算法的最佳分类结果。基于分类这个结果, 用FCM进行再次聚类, 这样既可以使凝聚层次聚类算法的聚类结果更精确, 又可以克服FCM的缺点。
首先将分类数作为FCM算法的聚类类别数c, 这样可以避免人为输入聚类类别数的盲目性。然后计算各个分组的质心作为FCM算法的初始聚类中心V0= (v1, v2, …, vc) , 这样能避免结果收敛于局部最优解。
结合凝聚层次聚类算法的FCM算法的具体流程如下:
(1) 输入聚类类别数c, 初始聚类中心V0= (v1, v2, …, vc) , 设定权重指数m, 设定迭代停止阈值ε (ε>0, ε一般取0.001和0.01之间) , 设置迭代计数器b=0;
(2) 计算或更新划分矩阵Ub。∀i, k, if∃d
(3) 更新聚类中心Vb+1。
(4) 如果
3 试验结果分析
本文采用两组样本集D1和D2, D1中有100个样本数据, 通过凝聚聚类算法得到最佳分类数为3类, D2中有200个样本数据, 通过凝聚聚类算法得到最佳分类数为4类。将两个数据集分别用传统的凝聚聚类算法、FCM算法、及改进后的算法进行聚类。试验结果如表1所示。
从表1可以看出改进后的凝聚层次聚类算法的执行时间明显比传统的凝聚层次聚类算法快, 从表2可以看出与凝聚层次聚类算法结合后的FCM算法迭代次数少于传统的FCM算法, 并且聚类的质量比传统的FCM算法好。其中SPRSQ和R2是聚类方法的评价指标, SPRSQ指标表示组内偏差值, SPRSQ越大表明组内越聚合;R2指标表示组间偏差值, R2越大表明组间较分离, 这两个评价指标都由Ward法得到。
4 结束语
聚类的目标是生成一些分组, 这些分组满足最大程度的内部聚合和最大程度的外部分离, 试验结果表明本文采用的改进凝聚层次聚类算法与FCM算法结合的聚类算法符合这一目标, 得到了较好的聚类结果。
参考文献
[1]Kantardzic M.数据挖掘——概念、模型、方法和算法.闪四清, 陈茵, 程雁, 等译.北京:清华大学出版社, 2003;8:108—111
[2]Han Jiawei, Kamber M.数据挖掘概念与技术.范明, 孟小峰, 等译.北京:机械工业出版社, 2001;8:236—241
[3]段明秀, 杨路明.对层次聚类算法的改进.湖南理工学院学报 (自然科学版) , 2008;21 (2) :28—36
[4]Giudici P.实用数据挖掘.袁方, 王煜, 王丽娟, 等译.北京:电子工业出版社, 2004;6:58—64
[5]王琼, 顾文轩, 徐汀荣.结合关联规则与FCM的用户聚类改进.微电子学与计算机, 2008;25 (3) :98—103
[6]张姣玲.利用FCM求解最佳聚类数的算法.计算机工程与应用, 2008;44 (22) :65—67
聚类算法 篇2
摘 要：在传统的医疗过程中，医护人员随机分配，患者被动接受治疗的护理管理模式不仅会浪费有限的医疗资源，使患者承受较高医疗费用，有时还会延误最佳治疗时机，引发并发症，给患者和其家庭带来更多的痛苦和困扰。文章通过将几种常见的聚类算法在护理管理中的应用进行比较，最终选择了先验假设较少的层次聚类算法，基于R语言探讨了哟尉劾嗨惴ǚ掷嗷だ砘颊叩氖迪止程，说明了层次聚类算法在患者与护理资源的最优匹配中的应用方法，为医院开展科学护理管理提供一定的参考依据。
关键词：聚类算法;护理管理;层次
中图分类号：TP399 文献标识码：A
Abstract：In the process of traditional healthcare，health care providers are randomly assigned and patients are passive to accept various treatments.Besides the high expense of medical treatment and the waste of limited medical resources，it would delay the best treatment time and cause complications，bringing great suffering to patients and their families.By comparing clustering algorithms，this paper chooses the hierarchical clustering algorithm with fewer priori assumptions.Based on R Language，this paper elaborates on the implementation process of hierarchical clustering algorithm in clustering patients，and the methods of using hierarchical algorithm to optimally match the patients and nursing resources，thus providing certain reference and basis to the scientific nursing management.
Keywords：clustering algorithm;nursing management;hierarchical
1 引言(Introduction)
护理管理是医疗机构以改善和提高医疗水平，合理利用医疗设备，最大程度发挥医护人员护理能力为目标的过程。然而，在传统的医疗护理管理过程中，医护人员随机分配，患者被动接受治疗方案，不仅会浪费医疗资源，使患者承受较高医疗费用，有时还会延误治疗，引发并发症，给患者和其家庭带来更多痛苦和困扰。随着信息化“智慧医疗”时代的到来，医院信息系统的普及，医疗数据采集、整理、分析不再受到传统人工操作在时间、效率、成本和疗效等方面的制约，取而代之的是高效、便捷、智能、科学的大数据分析处理过程。“互联网+医疗护理”的模式已悄然走近我们身边。许多学者开始尝试通过计算机算法精准识别患者、最优分配护理医生、优化患者转诊流程等方式来提高护理效果和降低医疗费用。在识别患者和分配医生时，为了更好地进行分类识别，聚类算法受到了广泛关注。
2 聚类算法(Clustering algorithm)
聚类就是按照“物以类聚”的思想，将抽象数据集划分成若干簇的过程，其中在每一簇中数据间具有高度的相似性[1，2]。聚类分析是当前数据挖掘中的重要手段。迄今，研究者已提出了多种聚类算法[3]。常用的聚类算法有基于划分、密度、网格、模型和层次的方法等[4]。
2.1 基于划分的聚类方法
基于划分的聚类方法需要提前设定聚类的数目，如K均值法和K中心点法等。这类方法分析时需要首先在数据集中随机选择聚类数目的对象，每个对象作为该聚类的中心或平均值，通过距离远近等方法将其余对象逐步聚类到每个类中。基于划分的聚类分析结果与初始值关系非常密切，不同的初始值往往会导致不同的聚类结果，通常会呈现出局部最优解。基于这种情况，基于划分的聚类方法在实际应用中往往要求穷举所有可能的划分。
2.2 基于密度的聚类方法
基于密度的聚类分析依据数据是否属于相连的密度域将数据对象进行归类。常用的基于密度的聚类算法为DBSCAN。这种聚类方法可以剔除噪声点，同时可以发现任意形状的聚类而不局限于球状的类[5]。但DBSCAN必须指定邻域半径和最少点数这两个参数，同时聚类的结果对这两个参数的依赖性很强。
2.3 基于网格的聚类方法
基于网格的聚类方法将空间分成有限数目的多维网格，利用网格结构实现聚类。如CLIQUE算法和STING算法。CLIQUE算法主要适用于处理高维数据，同时它综合了密度算法，可以发现其中的密集聚类。STING算法是一种将空间划分成直方形网格单元，不同方形对应不同分辨率，以实现聚类分析的方法[6]。
2.4 基于模型的聚类算法
基于模型的聚类算法是通过寻找数据对每个类预先设置好的模型的最佳拟合而实现的。最典型的基于模型的聚类算法是COBWEB算法。COBWEB算法不需要用户提供参数，可以自动划分簇的数目[7]。
2.5 基于层次的聚类算法
基于层次的聚类算法对数据集按照凝聚或分裂的层次方式进行聚类。凝聚型将每个对象看作一个单独的类，然后通过合并相近的类实现聚类。分裂型将所有数据归到一个类中，然后通过迭代，分层分裂成小类。常见的基于层次的聚类算法有CURE、ROCK和Chamelemon。Chamelemon算法在合并类的过程中，可以综合考虑类的内在特征、近似度和互连性，可以构造任意大小的聚集簇[8]。
2.6 几种聚类算法比较分析
基于模型的聚类算法要求对象在每个属性具有独立的概率分布，但在实际生活中，这种假设是不存在的。基于网格的聚类算法需要选择合适大小的单元数目，基于密度的聚类算法和基于划分的聚类算法需要用户设置一定的参数来产生可接受的聚类结果。在基于层次的聚类算法中，执行合并或分裂后无法回退修正，其质量受到一定的影响，但由于层次聚类算法无需提前知道最终所需的集群数量，其先验假设较少，因此通用性很强。目前，层次聚类算法已广泛应用于各个领域。
3 护理管理中聚类算法的应用研究(The application of clustering algorithm in Nursing management)
3.1 算法选择
在护理管理中，聚类可以帮助科研人员从医院信息管理系统中区分患者，聚类分析作为数据挖掘的重要分析方法，可以发现每类患者更深层次的信息，归纳总结出每类患者的个体特征和临床检验特征，有针对性的为患者提供精准治疗，减轻患者心理和财力方面的负担，缩短就医疗程，提高患者的生活质量。根据患者个体参数合理聚类患者往往不同于其他领域聚类分析。首先，患者的个体特征属性并不满足独立的概率分布。患者某项指标的偏离往往依赖于其他体征。其次，护理管理初期通过设置一定的参数来产生可接受的聚类结果，需要具备丰富的医学经验和较高的计算机理论水平，实际应用中难度很大。再者，患者病情差异较大，选择合适大小的单元数目可操作性较低。综合分析几种聚类算法，层次聚类算法需要的先验假设更少，对患者的聚类集群更科学，更适合当前大数据背景下医院开展科学、高效的护理管理，因此本文基于凝聚型层次聚类算法探讨聚类算法在护理管理中的应用。
3.2 数据预处理
护理管理中我们收到的患者数据往往具有异构性、冗余性、复杂性等特征，在对数据进行分析时首先需要进行集成、清理和归约[9]。
数据集成：患者个体数据来源主要有几个方面：(1)医学检验中心;(2)体检中心;(3)急诊科室;(4)门诊科室;(5)住院科室;(6)医学影像诊断中心;(7)社区卫生服务中心;(8)县级医院;(9)专科医院。不同的医疗机构对数据的存储格式、方法和实体的命名规则不同，在数据集成过程中需要考虑统一实体、删除冗余数据、处理冲突数据等。集成过程中可以考虑可视化分析和相关性分析等方法实现。
数据清理：由于医疗数据的特殊性，临床检验数据获取时间较长，人工填补缺失值困难大，而替代邻近值处理噪声数据又可能导致分析结果的不准确性，因此清理数据主要通过识别异常值并删除相应元组的方法实现。
数据归约：随着大数据时代的到来，可获得的患者个体数据越来越多，对患者属性进行归约处理可以有效地降低分析的时间复杂度，提高分析质量。因此，在分析过程中可以通过属性约简等方法归约处理数据。
3.3 基于R语言的层次聚类算法及其在护理管理中的应用
在数据预处理的基础上，将每个患者视为一类，利用欧几里得距离、曼哈顿距离、切比雪夫距离等方法计算出每类之间的相似度。接着，将相似度最高的合并为一个类，重复计算，直至相似度大于某个终止条件值时结束聚类。简言之，层次聚类算法是通过计算每个类中的数据点与所有数据点之间的距离来确定其相似性，距离越小，相似度越高[10]。在R语言中，具体实现步骤如下：
(1)计算距离矩阵：利用dist()函数计算患者间的距离矩阵。
d<-dist(x，method=”euclidean”)
其中，x为患者数据集，method表示计算距离的`方法，常用的方法有euclidean、manhattan、maximum等。方法的选择可根据患者具体数据而不同。
(2)聚类分析：在距离矩阵的基础上，使用hclust( )函数合并聚类簇。
hc<-hclust(d，method=“ward.D2”)
其中，d为患者数据的距离矩阵，method表示合并的方法，常用的方法有complete、ward、median、average、centroid等。
(3)剪枝操作：在数据分析中，患者数据的层次聚类结果有时很复杂，cutree()函数可以实现对聚类结果的剪枝操作，分析时可综合层次聚类结果和医生数选择合适的聚类数。
clusterCut<-cutree(hc，k)
其中，k为层次聚类结果的指定聚类数。最佳聚类数的选择是层次聚类剪枝中最复杂的一个问题，可以使用mclust、Nbclust、factoextra等包计算出最优聚类数。
4 护理管理分析(The analysis of Nursing
management)
在实际护理管理中，广义上讲护理管理人员涵盖的范围不仅包括医院护士、家庭护理人员[11]，还包括专家和医生。传统的护理管理中，专家、住院医生、护士随机分配和组合，往往会产生不同的治疗效果和医疗费用。为了改善这一现状，部分学者开始探讨优化护理流程、改善护理模式来提高护理质量。但这些方法虽然在某种程度上改善了护理质量，但护理方法的针对性较差。因此，在护理管理分析中，可以考虑事先仿真不同医生对每位患者的治疗效果。使用聚类分析方法，将患者进行科学分类，综合聚类结果、患者最终的治愈情况和医疗费用，发现每类患者的最佳护理者，从而为医院开展科学护理管理提供一定的参考依据。
5 结论(Conclusion)
随着“互联网+医疗护理”的发展，信息化技术在医学中的运用一定会越来越普及，越来越智能。我们探讨基于R语言的层次聚类算法在护理中的应用，就是要充分发挥层次聚类算法的先验假设较少的优点，可以直接对患者进行科学分类，达到患者与护理资源的最优匹配，既有效提高临床护理效率和效果，又能节省有限的医疗人力、物力、财力，最终达到医患关系的和谐融洽，相信随着互联网时代的到来，人工智能、计算机算法必将渗透到医疗护理的每一个环节，深入学习探讨各种算法在临床护理实际中的运用，将具有较大的科研和现实意义。
参考文献(References)
[1] 王有为，吴迪.聚类技术在医学数据中的应用[J].河南教育学院学报(自然科学版)，2016，2：32-35.
[2] 李雪梅，张素琴.数据挖掘中聚类分析技术的应用[J].武汉大学学报，2009，42(3)：396-399.
[3] 陈黎飞，姜青山，王声瑞.基于层次划分的最佳聚类数确定方法[J].软件学报，2008，19(1)：62-72.
[4] Jiawei Han，MichelineKamber.范明，孟小峰，译.数据挖掘概念与技术[M].北京：机械工业出版社，2004：1-262.
[5] 杨海斌.一种新的层次聚类算法的研究与应用[D].兰州：西北师范大学，2011：8.
[6] 张鑫.层次聚类算法的研究与应用[D].赣州：江西理工大学，2008：19.
[7] 段明秀.层次聚类算法的研究及应用[D].长沙：中南大学，2009：9.
[8] 毕鹏.改进的Chameleon层次聚类算法在目标分群中的应用研究[D].杭州：浙江大学，2009：17.
[9] 尤婷婷.健康大稻菰ご理技术及其应用[D].成都：电子科技大学，2017：6-16.
[10] 张良均，谢佳标，杨坦等.R语言与数据挖掘[M].北京：机械工业出版社，2017(8)：204-206.
[11] Katie M.Dean，Laura A.Hatfield，et al.Preliminary Data on a Care Coordination Program for Home Care Recipients[J].The American Geriatrics Society，2016(64)：1900-1903.
作者简介：
一种改进的模糊聚类算法研究 篇3
关键词：聚类分析；模糊聚类；点密度；隶属度
中图分类号：TP311 文献标识码：A 文章编号：1006-8937（2016）02-0055-03
1 概 述
作为一种无监督的学习方法，聚类是根据数据集中样本之间的相似度将数据集划分为若干个簇的过程，在图像处理、生物信息学、目标识别、医学诊断等领域有着极其广泛的应用[1，2，3]。按照样本的隶属度划分，可以将聚类方法分为硬聚类和模糊聚類。硬聚类将样本属于某一簇的隶属度设为0或1，其中取值为1表示该样本完全属于某一个簇，反之则完全不属于，即样本的类别是分明的。然而，在现实生活中，很多事物的属性带有模糊性，因此模糊聚类将每个样本对各个簇的隶属度扩展到区间[0，1]上来表示模糊性，对于簇彼此之中有噪声和交集数据的数据集，模糊聚类的结果在一定程度上要比硬聚类方法更加科学[4]，可以满足广泛的应用需求。
Dunn对硬C-均值算法HCM进行了坚实的分析后，提出了新的模糊划分概念，采用了Ruspini定义的集合，用目标函数的方式表达出硬C-均值算法，且可以应用到模糊性的环境，得到了更简单和易懂的模糊C-均值聚类算法FCM[5]。这种类聚算法可以依据隶属度而知道每个数据点隶属哪个聚类的聚类算法。Bezdek为硬C均值聚类（HCM）方法改进提出了这种方法。随后，Bezdek对算法持续改进，且证明了算法的收敛性[6]。Bezdek的贡献为聚类问题提供了一个很实际且有效的办法，为未来模糊集理论的发展奠定了基础。
在聚类算法中用于度量样本相似性或相异性的距离函数对于聚类结果有着重要的影响。经典模糊C-均值算法使用Euclid distance度量样本的相似度，优点是简单运算。缺点是对簇的大小/形状，算法初始值都比较敏感，如在某些特定情况下，不能很好的划分，Euclid distance方式也不能划分密度接近的簇。通常，改变这一距离度量方式[7，8]可以部分的控制这些因素的影响。本文沿袭了这一思路，提出了改进的基于点密度的模糊C均值聚类算法PD-FCM，即根据点密度信息生成一个修正参数来弥补Euclid distance的缺陷，形成样本与聚类中心的距离矩阵，从实现对FCM算法的优化。
2 PD-FCM算法
给定由n个样本组成的数据集X={x1，x2，...，xn}，xi∈Rs，以及簇个数k。模糊聚类的基本思想是将数据集X划分为k个簇s1，s2，...sk，使得公式（1）所示的目标函数最小。
Euclid distance方法计算样本和样本的相似性，由于简单运算比较，不能处理形状不对称或者不是椭球形的簇，且不能划分簇间数据密度不同的数据集。为此，引入点密度的概念，表示任意样本点的密度，用于对距离度量方式进行改进，其计算方法如公式（2）：
3 实验部分
为了验证算法的有效性，将本文提出的PD-FCM与经典的模糊C-均值算法FCM进行对比分析，实验中采用了两种来源的数据集，一类是人造数据集，另一类是从UCI中选取的知名的数据集。所有实验程序采用JDK 1.6版本开发，关键的参数模糊系数m设为2.0。每次实验重复10次，实验结果取平均值，评价标准采用准确率precision：
3.1 人造数据集
采用随机产生数据的方式构造了1组人造数据集，该数据集包含两个簇，两个簇中的数据点的分布均采用二维正态分布，样本个数均为100个，其中第1个簇中样本点分布在坐标原点为圆心，半径为1的圆内，而第2个簇中样本点分布在以（5.5，0）为圆心，半径为5的圆内。显然，第1簇中的数据密度大于第2组的。实验结果，如图1所示。
从图中可以直观地看出PD-FCM更为准确地将人造数据集划分为了两个簇。进一步地，计算得到的准确率如表1所示，同样验证了PD-FCM对于FCM而言在针对第2簇的分类准确率上有较大优势，这是因为参考密度来更新距离的密度因子，因此提高FCM算法的准确性。两种算法的准确率，见表1。
3.2 UCI数据集
从UCI数据集中选择了两组用于聚类任务的知名数据集，Wine和IRIS数据集，对PD-FCM和FCM算法进行对比实验。IRIS数据集一共有150个样本，维数为4，类别为3类，每类均有50个样本。
第一类为Iris Setosa，该类别的样本与其它类别的样本的距离较大，而第2类Iris Versicolour和第3类Iris Virginica对应的数据相距则较为接近，而且有一部分数据是交叉或者重叠的。
WINE数据集有178个样本，维数为13，类别也为3类，三类样本数分别是59、71和48，该数据集存在高维稀疏的特性。
首先对算法的有效性进行分析。在这两组数据集上的实验结果，见表2。
从表中可以看出，对于IRIS数据集，由于第1类数据距离其他两组数据较远，所以2种算法均能很好地将其分离出来，对于数据之间存在融合的第2类和第3类数据，PD-FCM算法表现出更高的准确性，较FCM算法提高了1%。但是，第2类的分类正确数有所下降。
对于Wine数据集而言，由于数据集本身具有高维稀疏的特性，这导致两种算法的准确率都比较低；但PD-FCM算法由于采用了密度调节因子，所以准确率提升了4.9%，同样地对第2类的分类结果也有影响，正确个数也小幅下降，但并未影响算法的准确率。
隸属度的准确性也是评价模糊聚类算法的有效性的一个重要度量。下面以wine数据集为例，对两种算法的最终隶属度进行分析。首先给出两种算法正确分类样本的隶属度分布图，如图2所示。
图上的隶属度越接近于1，则代表该算法的隶属度的准确性越高。从图中可以看出，在PD-FCM算法在第1类和第3类数据上获得的隶属度均较FCM算法有所提高，而第2类的隶属度则有所下降，这就表明采用了密度信息的PD-FCM算法更加适用于模糊信息系统的生成。
4 结 语
相似性度量方法是聚类算法的重要组成部分，对于聚类结果有着重要的影响。本文为了克服欧氏距离度量方法对于簇的形状、大小都比较敏感的问题，从优化相似性度量方法着手，提出了改进的基于点密度的模糊C均值聚类算法PD-FCM，该算法将样本点的密度信息融入到距离度量方法和优化目标函数中，能否适应多种不同的簇形状和大小，实验结果也表明改进后的算法在准确率和隶属度的准确性方面优于模糊C-均值聚类算法。
实验结果也发现PD-FCM并不是总是优于FCM算法，因此未来的工作可以考虑如何集成多种类型的模糊聚类算法，充分利用每种算法的优势进一步提高算法的分类准确性。
参考文献：
[1] Sajith， A. G.， & Hariharan， S. Spatial fuzzy C-means clustering base
ed segmentation on CT images[A].The 2nd IEEE International Confer
ence on Electronics and Communication Systems （ICECS）[C].2015.
[2] 陈科尹，邹湘军，熊俊涛，等.基于视觉显著性改进的水果图像模糊聚类 分割算法[J].农业工程学报，2013，（6）.
[3] 李波，邱红艳.基于双层模糊聚类的多车场车辆路径遗传算法[J].计算 机工程与应用，2014，（5）.
[4] Velmurugan， T. Performance based analysis between k-Means and F
uzzy C-Means clustering algorithms for connection oriented telecomm
unication data.[J].Applied Soft Computing 2014，（19）.
[5] Bezdek，J.C.，Ehrlich，R.，Full，W.FCM：The fuzzyc-mean sclustering algorit
hm[J].Computers & Geosciences，1984，（2）.
[6] Pal， Nikhil R.， and James C. Bezdek. On cluster validity for the fuz
zy c-means model[J].IEEE Transactions on Fuzzy Systems，1995，（3）.
[7] WuKL， YangMS. Alternative c-means clustering algoritllms.[J] Pattem
Recognition.2002，（10）.
[8] Menard M， Courboulay V， Dardignac P. Possibilistic and probabililist
ic fuzzy clustering： Unification within the framework of the non-exte
一种基于层次聚类的双聚类算法 篇4
随着DNA芯片技术的不断发展, 基因表达数据实验得到极大地发展, 实验要求也相应提高, 使得传统聚类方法存在的缺陷日益明显。传统聚类仅在整个数据矩阵的单个方向聚类, 或者行方向或者列方向, 无法发现列集合下行的局部信息, 无法适应生物理论下数据的多功能特点。此外聚类经常会分散相互表达的数据块产生错误决策, 使得基因信息简单化。为了克服传统聚类方法存在的缺陷, Cheng和Church[1]首先提出双聚类并应用于基因表达数据挖掘中。双聚类被定义为一个具有统一标准的基因表达数据子集, 即分别通过交换矩阵的行和列, 将数值相似的数据聚合在一起形成子矩阵。为了评价该子矩阵的相似程度Cheng和Church [1]提出了均方残值的概念, 均方残值越低表明子矩阵的数据相似性越强, 即表达相关性越强, 集合捕获基因数据中有生物意义的基因信息越强。图1表示双聚类与聚类的区别。从图1中可以看出, 行方向为基因, 列方向为实验条件, 整个基因表达数据表达的是基因在不同的实验条件下表现出的不同数值。双聚类是数据矩阵中数据相似块, 双聚类与双聚类之间可以重叠。
Cheng和Church[1]运用贪心策略移动行和列来搜索双聚类。Yang et al [2]在Cheng和Church[1]算法的基础上, 提出了概率算法 (FLOC) , 该算法能够同时发现k个具有可重叠性的双聚类集合。Zhang et al [3]提出DBF算法即运用频繁模式挖掘确定双聚类, 该算法在第一阶段频繁模式下产生较高质量的双聚类集合, 在第二阶段迭代过程中, 通过进一步增加行和列扩大双聚类。
本文使用均方残值策略为双聚类的表达水平打分。为了避免随机值干扰并实现可重叠双聚类, 我们采用自底向上的思想。首先对基因表达数据的行和列分别使用层次聚类生成行集合和列集合, 行集合和列集合再分别组合成数据子矩阵, 并作为双聚类初始种子;然后采用启发式策略对种子分别添加行和列, 用全局优化找出均方残值最低的双聚类;并使用生成双聚类种子的热核图, 也叫做伪彩色图, 在伪彩色图中, 不同的数据表示不同的颜色, 数据相似度越大, 颜色也就越接近。最后将算法的结果与其他流行的算法结果进行比较。
2 双聚类模型
在基因表达数据矩阵中, A为表达矩阵, 行集合为基因集合X, 列集合为条件集合Y, aIJ为表达矩阵A的元素值, 表示在第j列条件下第i行基因的表达值。 (I, J) 对表示子矩阵AIJ, 其中I为基因集合的子集I⊆X, J为条件集合的子集J⊆Y。
双聚类的一致性表现在行和列的数据分别具有相似性。在理想状态下, 每行或者每列的值可以通过其他行和列减去一个值产生。这时, 双聚类中每个元素值根据它的行均值aiJ, 列均值aIj, 矩阵均值aIj确定。差值aIj-aiJ为第J列关于该双聚类中其他列的相对偏差;对行差值亦然。因而, 双聚类的元素值aij可以定义为行均值加上列均值减去矩阵均值。
aij=aiJ+aIj-aIJ (1)
然而基因数据中存在噪声, 双聚类并不一定是理想的, 因此定义残差量化一个元素的真实值与相关的行均值、列均值、矩阵均值的期望。非理想状态下元素值的残差定义为:
RSIJ (i, j) =aij-aiJ-aIj+aIJ (2)
为了评价双聚类在噪声影响下的质量, Cheng 和Church[1]在残差的基础上定义了Hscore (均方残值) 为双聚类行与列的相关性打分。均方残值公式如下:
其中, 存在当δ≥0, 如果满足H (I, J) ≤δ的条件, 则子矩阵AIJ叫做δ-双聚类。
3 双聚类算法
3.1 层次聚类算法生成种子
本节首先介绍层次聚类的基本概念, 再介绍层次聚类的算法, 并阐明该算法计算公式。一个层次聚类算法将数据组织成一棵聚类的树, 根据层次是自底向上还是自顶向下形成, 可以进一步将层次聚类算法分为凝聚型和分裂型聚类算法。根据所采用的计算类间距离方法的不同, 层次聚类算法主要有单连接SL ( Single- Link) , 全连接CL (Complete-Link) 和平均连接AL (Average- Link) 三种。单连接也叫做最近邻居, 就是求两个类之间的最短距离。本文采用分裂型、单连接算法, 分别对矩阵的行和列方向上进行聚类。在行方向进行层次算法时, 将所有行归于同一个类, 采用欧式距离计算每个行之间的距离, 并采用单连接的方法计算每个类之间的相似度, 当两个类之间的距离小于等于阈值, 则合并这两个类。然后将该层类分裂成两个下层的类, 重复计算, 直至达到符合条件为止。列方向方法同样。在matlab中实现的代码如下:
本文对数据矩阵的行和列分别使用层次聚类算法生成m, n聚类, 整个数据集就划分成m×n数据块, 将所有的数据块作为我们双聚类起始的种子。
3.2 启发式更新种子生成初始双聚类
采用启发式方法更新前面生成的种子。先添加列, 计算Hscore值是否超过设定的阈值, 没有则将该列添加到数据矩阵中;对行做同样的操作直到Hscore值达到设定的阈值。
3.3 全局优化生成最终的双聚类
生成种子的质量会影响双聚类的质量, 因此, 我们不是取Hscore值最小的前100个作为我们双聚类起始的种子, 而是使用所有的种子并进行分组更新优化。优化步骤如下:
(1) 初始化双聚类, 设定种子数为n ;
(2) 计算每个种子的行均值, 列均值, 矩阵均值, 和Hscore值, 启发式更新种子 ;
(3) 对于每个种子, 将自己的Hscore值与所经历过的最好Hscore值进行比较, 如果较好, 则将其作为当前的最好的Hscore值;
(3) 对于每组种子, 将该组Hscore值与所有组经历过的最好的Hscore值进行比较, 如果较好, 则将其作为当前的所有种子集合的最好Hscore值;
(4) 根据式子 (1) 、 (2) 扩张种子;判断是否达到终止条件, 如果达到则跳出, 否则转 (2) 。
4 实验结果比较
4.1 算法可行性验证
我们采用理想状态下无噪声干扰的模拟数据矩阵。矩阵大小为50×20, 取值为0或1。图2为模拟数据的热核图, 图3为模拟数据双聚类的热核图, 通过图2和图3可验证本算法的正确性。
4.2 植物数据的实验结果
植物数据包含三种类型植物叫做Setosa、Versicolour、Virginica, 每一种植物约有50个样本。列描述植物的属性分别为萼片长、宽, 花瓣长、宽。
从图4和图5的热核图可看出, 本文方法在四种属性条件下可以找出三种不同类型的植物。
4.3 酵母数据实验结果
进行测试使用的第三个数据集是酵母细胞表达数据。我们采用Cheng 和Church[1]使用的酵母数据集, 目的是比较双聚类的结果。该基因数据集包含2884个基因, 17个条件, 数据取值在[0, 600]之间, 其中缺失的数据用-1来替代。
种子好坏决定双聚类聚类最终结果, 使用层次聚类算法先将酵母细胞数据划分为1000个种子, 并全部用于双聚类的搜索中。
图6、图7两组图一个是原始酵母数据集热核图, 另一个是所有种子组合的热核图, 图7的热核图是通过层次聚类得到的结果, 从中可以看出, 颜色一致的部分是均方残值相似种子组合成, 双聚类在此基础上进行优化搜索, 既能减少搜索偶然性, 又能提高双聚类的搜索速度。
Cheng和Church[1]算法采用阈值为300, 在本算法中设定同样的阈值300, 双聚类的结果比较如表1所示。
4.4 算法存在的一些问题以及改进
对于层次聚类算法生成种子过程, 我们发现该算法对数据大小设定很敏感, 不当的设置会分裂好的双聚类, 并对最后双聚类的生成影响很大, 因此采用分裂层次聚类算法还有很多待改进的地方。
5 结束语
聚类算法 篇5
Kmeans聚类与多光谱阈值相结合的MODIS云检测算法
摘要：采用Kmeans聚类与多光谱阈值相结合的方法进行云检测.在地物光谱分析的基础上,应用Kmeans聚类算法对聚类特征数据初始分为两类,第一类为云、烟雾和雪,而植被、水体和陆地等其他下垫面为第二类;然后应用光谱阈值判断排除烟雾和雪等的干扰,对MODIS数据中的云体实现检测.还研究了我国典型区域在不同季节、小同时棚的.数据.在不同下垫面的情况下,通过目视方法对该算法的性能进行检验,发现该算法能有效地检测出一些小面积云点像元,并且排除其他因素的干扰,为下一步火灾识别工作奠定良好的基础. 作者： 王伟[1] 宋卫国[1] 刘士兴[2] 张永明[1] 郑红阳[1] 田伟[1] Author： WANG Wei[1] SONG Wei-guo[1] LIU Shi-xing[2] ZHANG Yong-ming[1] ZHENG Hong-yang[1] TIAN Wei[1] 作者单位： 中国科学技术大学火灾科学国家重点实验室,安徽,合肥,230027合肥工业大学电子科学与应用物理学院,安徽,合肥,230009 期 刊： 光谱学与光谱分析 ISTICEISCIPKU Journal： SPECTROSCOPY AND SPECTRAL ANALYSIS 年，卷(期)： 2011, 31(4) 分类号： X87 关键词： MODIS 云检测 Kmeans 亮温 机标分类号： TP3 TU9 机标关键词： 聚类算法 多光谱 阈值 MODIS数据 检测算法 Kmeans Clustering Detection Algorithm 不同下垫面 地物光谱分析 算法的性能 烟雾 特征数据 判断排除 基础 干扰 方法 云检测 植被 水体 识别 基金项目： 科技部林业公益性行业科研专项，中国科学技术大学青年创新基金项目 Kmeans聚类与多光谱阈值相结合的MODIS云检测算法[期刊论文] 光谱学与光谱分析 --2011, 31(4)王伟 宋卫国 刘士兴 张永明 郑红阳 田伟采用Kmeans聚类与多光谱阈值相结合的方法进行云检测.在地物光谱分析的基础上,应用Kmeans聚类算法对聚类特征数据初始分为两类,第一类为云、烟雾和雪,而植被、水体和陆地等其他下垫面为第二类;然后应用光谱阈值判断排除烟...
数据挖掘中聚类分析算法性能分析 篇6
关键词：数据挖掘；聚类分析算法；性能分析
中图分类号：TP311.13；TP18 文献标识码：A 文章编号：1674-7712 （2014） 16-0000-01
在技术水平的发展之下，数据挖掘技术也得到了迅速的发展，在传统领域下，数据挖掘技术仅仅是基于统计学与计算机技术基础上产生的技术，目前，数据挖掘技术已经在各个行业中得到了广泛的应用，其最大的目标市场主要集中在数据集市、数据仓库与决策支持业界之中，下面就针对数据挖掘中聚类分析算法的性能进行深入的分析。
一、数据挖掘中聚類分析算法的应用
聚类就是将数据集划分不同类的一个过程，不同聚类数据对象相似度小于同一个聚类对象相似度，在使用聚类分析方法应用数据集后便可以帮助研究人员分析出数据集的稠密区域与稀疏区域，辨别出各个数据之间的相关性。将聚类分析法应用在商业领域可以帮助研究人员对客户群体进行深入的挖掘，并根据客户群体的消费心理与特征来制定营销策略；将聚类分析法应用在生物学领域能够帮助了解人员了解人类的基因；将聚类分析法应用在经济领域中能够帮助研究人员来评价各个地区的经济发展能力。同时，聚类分析还可以帮助用户挖掘出网页中的有用信息，聚类分析能够作为独立工具，也可以与其他数据挖掘算法进行联合使用。
二、聚类分析算法的应用要求与方法简介
聚类分析算法的应用需要满足几个特性，这包括可扩展性、不同类型属性处理能力、任意形状聚类、减少输入参数量、噪声数据处理力、高维问题、约束聚类几个内容。根据处理数据目的、要求与类型的不同，聚类分析算法可以分为几种不同的形式，其中代表性的算法有层次方法、划分方法、基于网格算法与基于密度算法。
（一）层次方法
层次方法是一种层次广泛的分析方法，层次方法有两种类型，即自上而下分析法与自下而上分析法，前者强调将数据对象作为独立分组，对这些对象组进行合并处理，直至满足终止条件；后者将所有对象作为一个分析，逐步将其分为小组，直至满足终止条件。常用的分析法有CURE算法与BIRCH算法两种类型。
层次方可可以得出粒度不同的多层次聚类结构，但是，由于各类因素的影响，这一分析法也有一些缺陷，其中最大的问题就是难以进行回溯，在分析的时候必须要考虑到这一问题。
在进行计算时，需要按照相似度来进行分析，也能够将不相似的部分分离开来，判断各个类的相似性，再根据距离来计算出类与类的差异度。
层次分析法引入了聚类特征树与聚类特征，是针对大规模数据的一种算法，该种算法可以有效减少数据处理量，在完成压缩之后也能够满足聚类信息需求，也不会影响聚类的质量。此外，该种算法只要进行一次扫描即可完成聚类，但是，该种算法只能够使用直径与半径概念进行分析，因此，只能够用于对象为球形的计算中，如果数据输入顺序不同，那么就很可能产生不同的聚类结果。
（二）分析方法
使用分析方法可以将数据集划分为k个聚类，这些聚类需要满足几个条件：（1）聚类是要包含一个及以上数据对象的；（2）每一个数据对象只与一个聚类相关，对于一些模糊划分方法，能够适当放宽要求。
对于所有聚类，都需要使用优化的分析方法进行划分，缩小聚类对象距离，分析划分方法质量的标准就是聚类相似度，理想的划分方法能够提升数据对象相似度，常用的划分法包括K-medoids算法与K-means算法两种类型。
（三）基于网格方法
基于网格方法强调将对象空间划分成网格结构，这些网格结构的数目单元是有限的，一般情况下，如果划分过于粗糙，就会影响边界的清晰度，如果划分过于细致，也会导致小聚类数量过多。为此，在使用网络分析法时，就需要从小单元先进行聚类，在逐步增加其体积，指导聚类质量达到标准。
划分对象网格数对于数据库集处理时间有着重要的影响，这会有效简化个数对于数据的影响，这即可有效提升网格分析法的处理速度。
假设N为数据库对象数据，且N无限大，数据对象特征会产生d维特征空间，在进行计算时，数据复杂度是o（N），在对象扫描完成后需要将其分配到相应单元中，若特征空间一个维有m个单元，就一共会出现md个单元，在下一步，就可以使用小波转换来进行处理，建立好查询表，在数据引入其中之后，即可处理相关数据，这些数据复杂度与数据对象数是没有直接关联的，算法时间复杂度即为o（N）。
（四）基于密度算法
基于密度算法可以分析出各种形状聚类，这一算法主要通过获得聚类到相邻密度阈值获取结果，该种算法可以起到很好的除燥作用，挖掘出形状不同的聚类，其中最为常用的基于密度算法就是DBCLUES、OPTICS与DBSCAN。
三、结束语
总而言之，聚类分析已经在数据挖掘领域中得到了广泛的使用，聚类分析算法可以分为几种不同的形式，其中代表性的算法有层次方法、划分方法、基于网格算法与基于密度算法。每一种算法都有其不同的特征与适用性，层次方法适宜用在不同粒度多层次聚类结构的分析；划分方法多用于球形聚类形状；基于网格算法能够迅速处理数据对象；基于密度算法可以能够有效消除噪声，相信在大数据时代的发展下，聚类分析技术定可以得到更加广泛的使用。
参考文献：
[1]王成，王继顺.基于因子分析与聚类分析的学生成绩综合评价[J].甘肃联合大学学报（自然科学版），2011（01）.
[2]王亮红，宋代清，徐娜.聚类分析在学生成绩分析中的应用[J].东北电力大学学报（社会科学版），2009（04）.
[3]刘思，徐静瑞，张建伟.基于蚂蚁孵化分类行为的聚类算法[J].郑州轻工业学院学报（自然科学版），2009（05）.
并行DBSCAN聚类算法 篇7
随着信息技术的高速发展, 出现了越来越多诸如地理信息、卫星图像等大规模空间数据库。大规模空间数据库对于聚类算法的要求更高, 要求算法能够发现任何形状的类并能高效聚类。DBSCAN是面向空间数据库的基于密度的聚类算法, 其主要思想为:如果一个对象在半径为ε的领域内包含至少MinPts个对象, 那么该区域是密集的。其优点是能够发现任意形状的类, 并且不受异常值 (噪声) 的影响, 然而当数据库规模增大时, 该算法要求较大的内存支持, I/O消耗大, 采用串行算法, 无论是运算速度还是内存, 都无法满足对大规模数据库聚类的需求。
针对该算法的计算效率问题, 本文提出一种基于内存的并行DBSCAN算法。首先基于投影进行数据分区, 之后在每一处理器上分别聚类, 最后合并聚类结果。实验证明该算法较DBSCAN算法速度有很大提高, 并且聚类的准确程度亦有所改善。
1 DBSCAN算法介绍[1]
首先给出DBSCAN算法的几个基本概念, 其中D为数据库, Eps和MinPts为给定阈值。
定义1.1 (Eps-邻域) 对于空间任意一个点P, 其Eps领域记作NEps (p) ={q∈D dist (p, q) ≤Eps}。
定义1.2 (核心点) 对于一个点, 如果在其Eps-邻域内至少包含MinPts个对象, 则称该对象为核心对象。
定义1.3 (直接密度可达) 点p从点q直接密度可达, 若它们满足:
(1) p∈NEps (q) ;
(2) NEps (q) ≥MinPts。
定义1.4 (密度可达) 点p从点q密度可达, 若存在p1, p2, .., pn, 其中p1=q, pn=p, 且pi+1从pi直接密度可达。
定义1.5 (密度相连) 点p和点q是密度连接的, 若存在对象o, 使p和q都从o密度可达。
定义1.6 (类) 数据库D的非空集合C是一个类, 当且仅当C满足以下条件:
(1) 任意点p, q, 若p∈C, 且q从p密度可达, 则q∈C (最大性) ;
(2) 任意点p, q∈C, 则p, q密度连接 (连通性) 。
定义1.7 (噪声) 数据库D中不属于任何类的点为噪声。
DBSCAN算法思路如下:对数据库中任何一个点, 对其进行区域查询, 判断是否是核心点, 如是, 建立新类C, p及其邻域内的点均属于该类。考察C中尚未被考察过的点q, 若q是核心点, 则将其领域内未属于任何一类的点追加到类C。不断重复此过程, 直到没有新的点可以追加为止。类C是一个密度相连的, 基于密度可达性最大的点集。以同样程序寻找其他的类, 不属于任何类的点为噪声。
DBSCAN算法的复杂度为O (n2) , 其中n是对象的总数。为了提高聚类效率, DBSCAN算法采用空间数据库索引R*-TREE来实现区域查询, 使计算复杂度降为O (nlogn) 。在进行聚类前, 需要建立针对所有数据的R*-TREE。另外, DBSCAN要求用户指定一个全局Eps参量。为了确定Eps值, DBSCAN计算任意点与它的第k个最邻近点间的距离, 然后, 根据求得的距离由小到大进行排序, 并绘出排序后的图, 称作k-dist图。k-dist图中的横坐标表示空间点, 纵坐标则为该点的k-dist值。R*-TREE的建立和k-dist图的绘制都是消耗时间的过程, 当面对的数据库规模很大时, DBSCAN串行算法在内存和计算速度方面都存在很大的障碍。
基于以上分析, 本文提出一种基于数据分区的的并行DBSCAN算法——P-DBSCAN。该算法适用于共享内存的并行计算系统, 例如单台多核计算机;也同样适用于分布式非共享内存的并行计算系统。在本文的研究中, 主要针对单台多核计算机。
2 P-DBSCAN算法
2.1 并行算法相对DBSCAN的主要改进点
2.1.1 针对数据空间分布特点进行数据分区
扫描数据库通过程序计算找出数据的分布特征, 对数据库在每一坐标轴上进行投影, 从而找到数据库在每一维上的分布特征, 进行合理的数据库划分。这是人机交互的过程。
分割原数据库需要遵循两个原则:
(1) 依据空间分布特点进行数据块划分。寻找能显示数据分布特征的点, 从该处进行区域划分。
(2) 划分数据块的多少, 要根据数据库大小及计算环境来共同决定。当数据库较小及计算节点较少时, 均不宜将其划分成过多的数据块。原因是将消耗过多的合并成本。
此数据库划分原则, 适应于任何维数的数据空间, 为了演示方便, 本文仅以如下带有噪声的二维数据库进行图示说明 (如图1所示) 。
例如, 对如图1所示数据库, 将其投影至X、Y轴, 投影结果如图2所示。
我们目前仅用双核单台计算机实验, 将数据库划分为两块比较合适, 故可仅在X轴的A点将数据库进行划分。
2.1.2 合并算法
(1) 如果某点Z分别属于类1和类2, Z至少有一次为核心对象, 则类1和类2合并为一个类。
(2) 如果某点Z在类1和类2中都是边界点, 则Z可以属于类1或类2, 但类1和类2不能合并。
(3) 如果Z有一次属于类1, 而另一次是噪声点, 则Z属于类1。
(4) 如果Z点两次都是噪声点, Z在全局聚类中就是噪声点。
2.2 P-DBSCAN算法流程
(1) 将数据库进行数据分区。
(2) 将数据块分配到各个处理器进行计算, 在每一处理器上:
(1) 对每一数据区建立PR-TREE;
(2) 检查数据块中尚未检查过的对象P, 如果P未被处理 (归入某个类或标记为噪声) , 则检查其Eps邻域NEps (P) , 若NEps (P) 包含的对象数不小于Min Pts, 则建立新类C, 将NEps (P) 中所有点加入C;
(3) 对C中所有尚未被处理的对象q, 检查其Eps邻域NEps (q) , 若NEps (q) 包含至少Min Pts个对象, 则将NEps (q) 中未归入任何一个类的对象加入C;
(4) 重复步骤 (3) , 继续检查C中未处理对象, 直到没有新的对象加入当前类;
(5) 重复步骤 (2) (3) (4) , 直到所有对象都归入了某个类或标记为噪声。
(3) 合并各处理器的计算结果。
(4) 输出计算结果。
3 实验
本实验设备为一台采用Windows操作系统, Inte2.0 GHz (双核) , 3 GB内存的笔记本;编程工具和运行环境为JDK 1.5。实验对象为如图1所示的数据库。两个处理器的聚类结果如图3所示。
从图3可以看出, 由于数据库先分割后由两个处理器进行分别聚类, 所以将原来原本属于同一个类的类5与类6分割成两个类。合并两个处理器的聚类结果, 得到正确的聚类如图4所示。
从图4我们了解到, 并行聚类可以得到与串行聚类同样的聚类效果;而且通过大量的实验发现, 并行聚类算法的效率比串行算法有了大幅度提高。实验还发现, 参数中的半径, 即Eps是影响搜索速度的关键, 而在Eps确定之后, Min Pts却对速度几乎没有影响。在我们的实验中, 参数Eps及Min Pts分别选定为2, 7。采用串行算法的计算时间为30 531ms;同一台计算机, 采用并行算法的计算时间为16 781ms, 仅为串行算法执行时间的55%。
4 结论
本文提出了一种并行聚类算法——P-DBSCAN, 根据数据分布特征进行数据库划分, 将其分配到多核处理器分别聚类, 之后合并聚类结果。实验证明P-DBSCAN算法不但能得到正确的聚类结果, 而且在双核处理器上的计算速度可以提高50%。该算法可以扩展到分布式并行计算环境, 下一步的研究将在分布式计算环境中实现P-DBSCAN并行算法。
参考文献
[1]Martin Easter, Hans-Peter Kriegek, et al.A Density-based Algorithm for Discovering Clusters in Large Databases with Noise[C]//Proceedings of the2nd International Conference on Knowledge Discovery and Data Mining, 1996:226-231.
[2]Norbert Beckmann, Hans-Peter Kriegel, et al.The R*-tree:An Efficient and Robust Access Method for Points and Rectangles[C]//Proceedings of SIGMOD International Conference on Management of Data, 1990:322-331.
聚类算法 篇8
模糊K-Prototypes (FKP) 算法能够对包含数值属性和分类属性相混合的数据集进行有效聚类, 较好地处理大规模混合数据类型, 模糊技术体现聚类的边界特征, 使得更适合于含有噪声和缺失数据的数据库。
然而, FKP算法中仅仅考虑了分类属性对结果的不同影响, 隐含假定待分析样本中数值属性对分类的贡献是均匀的, 而在实际应用中, 由于构成样本特征矢量的各维特征来自不同的传感器, 存在量纲差异和精度的不同, 另外, 所选择的各维特征对分类的贡献程度也是有所不同的。
特征选择在数据挖掘、图象处理、数据压缩、模式识别等诸多方面有广泛的应用, 其基本任务是如何从许多特征中找出那些最有效的特征。ReliefF算法是公认的效果比较好的特征评估方法, 根据特征对近距离样本的区分能力来对特征进行评估, 最后给特征集中每一特征赋予一定的权重, 权重越大, 这个特征区分不同类的样本的重要性越强。
为了考虑特征矢量中各维特征对模式分类的不同贡献, 利用特征选择技术ReliefF对特征进行加权选择, 给予每个特征一个权重。在文章后面的实验部分, 通过实验结果可以看出该方法可以得到较为理想的聚类。
二、模糊K-Prototypes算法
K-Prototypes算法是由Huang提出的可以对分类属性和数值属性相混合的数据进行聚类的一种有效的算法。模糊K-Prototypes算法是对K-Prototypes算法的扩展, 对聚类中的对象分派隶属度, 通过交替更新聚类中心和划分矩阵使得目标函数值达到最小, 使得对于混合数据能够得到较好的聚类结果。
算法简单描述如下:假定数据库表是由m个属性A1, A2, ...Am描述的一组数据对象X={X1, X2, ...XN}, 其中Xi=[xi1, xi2, ..., xim]表示具有m个属性值的数据对象。设K是一个正整数, 对X聚类的目的就是要将N个对象划分到K个不同的类别中。一般使用以下代价函数最小作为聚类的准则:
其中, Z={Z1, Z2, ...ZK}, 元素Zk=[zk1, zk2, ...zkm]是能够代表聚类k的向量或称作聚类中心, ZkjDOM (Aj) , 1≤j≤m;W={wki}是K×N的划分矩阵, 每一个元素wki表示对象Xi划分到聚类k中的隶属度, 且满足
>1是模糊指数, d (Xi, Zk) 是差异测度, 假设数据对象Xi的m个属性中, [xi1, xi2, ..., xip]为数值属性, [xip, xip+1, ..., xim]为分类属性, 那么差异测度定义如下:
在第τ个属性上的取值, γτ是聚类的分类属性的权值。如果对所有聚类, γτ取同一值, 则用γ表示, 当γ=0时, 模糊K-Prototypes算法就是模糊K-means算法, 数据的分类属性不起作用, 聚类过程完全由它的数值属性决定。
划分矩阵的更新方法如下:
聚类中心的更新方法如下:对于数值型属性Aj (1≤j≤p) :
(Aj) , 且γ满足
其中nj表示分类属性Aj取值个数。
综上所述, 模糊K-Prototypes聚类算法步骤描述如下:
初始化聚类数K和聚类中心Z0, 并按公式 (7) 确定W0;
确定Zλ+1, 若│F (Wλ, Zλ+1) -F (Wλ, Zλ) │<ε, 算法停止, 返回Wλ, Zλ+1;
确定Wλ+1, 若│F (Wλ+1, Zλ+1) -F (Wλ, Zλ+1) │<ε, 算法停止, 返回Wλ+1, Zλ+1;
令λ=λ+1, 转至2。
三、Relief F算法
特征选择是从一系列相关或无关的特征中选择出相关性最强的若干特征来表征一个概念或事务的过程。选择不仅能减少特征提取阶段采集、变换等操作的计算压力, 还有利于降低噪声干扰、提高分类的准确性。
基本的Relief算法是由Kira和Rendell在1992年提出, 当时局限于解决两类的分类问题, 是一种权值搜索的特征子集选择方法, 它为每个特征赋予一个权值, 这个权值表征了特征与类别的相关性。其思想为好的特征应该使同类的样本接近, 而使不同类的样本之间远离, 通过不断调整权值逐步凸现特征的相关程度。Kononenko于1994年扩展了Relief算法, 提出了可以解决多类别情况、噪声数据和不完整数据的ReliefF算法。
设X={X1, X2, ..., Xn}是待分析的对象全体, 其中Xi={Xi1, Xi2, ..., Xim}表示第i个样本的m个属性值。ReliefF算法从所有的训练样本中随机选择S个样本, 对于其中任意一个样本Xi, 首先找出β个与Xi同类的最近邻的样本Hj (xi) , 然后在每一个与Xi不同类的子集中找出β个最近邻的样本Mj (C) , 计算样本在各个属性上的间隔, 并累加起来做为属性的权值。样本Xi更新属性p的权值可表示为:
对于离散属性, 函数定义为:
而对于连续属性:
其中, max (p) , min (p) 分别是该属性值的上下届。
当一个属性较容易区分类别时, 意味着同类样本间的距离较近, 而不同类样本间距离较远。因此, 如果属性与分类毫无关系, 那么其权值将趋于零或者很小的数。相反, 如果属性与类别存在很强的相关性, 那么其权值会较高。权值为负数表示同类近邻样本距离比非同类近邻样本距离还大。
函数diff同样用来寻找样本Xi的β个近邻样本。将所有属性的间隔累加起来, 从而得到任意两个样本的距离。
噪声会使特征数据发生微量的偏移, 干扰特征对类别的准确表示。当噪声影响多个属性时, 会严重干扰同类、非同类最近邻样本的判定, 从而对选择产生不利的后果。ReliefF算法中针对此问题, 选择使用β近邻样本而不是最近邻样本进行计算。通过β个样本的平均, 在一定程度上削弱了噪声对数据的影响。
ReliefF算法的步骤描述如下:
·初始化各个属性的权值:λτ0=0;
·随机选取样本Xi;
·找出与Xi最近邻的β个同类别的H (xi) ;
·对每个类c≠class (xi) , 找到与Xi最近邻的β个Mj (C) ;
·按 (6) 式更新每一个属性的权值;
四、改进的模糊K-Prototypes算法 (R-FKP算法)
原始的K-Prototypes算法, 利用权值来控制数值属性和分类型属性的比例, 但在数值属性中, 每一维数值特征对分类的贡献是均匀的。因此, 在K-Prototypes算法的基础上, 对每一维属性都进行加权, 这样, 聚类目标函数修正如下:
ReliefF算法是针对分类技术的, 在分类中, 每一个样本的类别标记是确定的, 而在聚类分析中, 每一个样本的类别标记是未知的, 这时, 我们可以先对待分析的样本集进行一次聚类。
在使用ReliefF算法时, 需要随机抽取一定数量的样本, 而在数据库中, 有时候不同类的样本数量相差悬殊。ReliefF的随机选择样本策略会使得小样本类别选中进行权值计算的概率较小, 甚至可能被忽略, 这样影响了对分离小样本有明显作用的属性。改进的方法是, 在抽取样本时按照第一次聚类得到的各类之间的数量比来从不同类中抽取。
利用ReliefF算法改进FKP算法的流程如下:
·执行FKP算法一次;
·按照各类的数量比, 抽取S个样本Xi (在同一类中选择隶属度较大的) , 分别找出与Xi同类以及不同类的最近邻的β个样本, 再按照前面所述ReliefF算法方法计算各个属性的权值;
·利用得到的权值对各维特征进行加权后, 再执行FKP算法, 就可以得到最后的聚类分析结果。
五、实验结果
本文将FKP算法和ReliefF改进后的算法进行了比较。实验数据Iris和Zoo都来自著名的UCI的机器学习数据库, 有关信息如表1所示。
(一) Iris样本
Iris样本是用来测试聚类或分类算法性能的一个著名基准函数数据集。在数据记录中, 每组数据包含Iris花的四种属性:萼片长度, 萼片宽度、花瓣长度和花瓣宽度。数据集包含三类:Setosa、Versicolor和Virginica, 每类各有50个样本。Hathaway在1995年给出了这组测试数据集的实际类中心位置分别为:Zl= (5.00, 3.42, 1.46, 0.24) , Z2= (5.93, 2.77, 4.
在实验中, FKP算法允许的最小误差为10-6, 模糊指数=1.1, 各算法的聚类中心数为其类别数, 训练样本数S=50, 近邻样本数β=7。将算法分别运行50次, 统计各项指标的平均值, E是分类错误的样本所占的比例, 实验结果如表2所示。
从表中数据可以看到, ReliefF改进的FKP算法, 错误率明显降低, 而且聚类中心更接近实际的类中心位置。其四个属性的平均权值为:[0.030797, 0.022 704, 0.11 518, 0.14981], 可以看出花瓣长度和花瓣宽度这两个属性的贡献比较大, 萼片宽度的贡献最小。
(二) Zoo样本
Zoo样本是动物园的实际数据集, 并且是混合数据集, 包含15个数值属性和1个分类型属性。样本最后被分成7个动物类别, 名称和包含的样本数为:哺乳类 (41) 、鸟类 (20) 、鱼类 (13) 、昆虫类 (8) 、软体类 (10) 、爬行类 (5) 和两栖类 (4) 。
在实验中, FKP算法允许的最小误差为模糊指数, 各算法的聚类中心数为其类别数。训练样本数S=50, 近邻样本数β=3。
表3为R-FKP算法得到的各个属性的权值, 权值越大, 对分类的贡献越大。可以看到, milk这个属性的权值最大, 它描述了动物是否哺乳, 而7个动物类别中哺乳类的数目最多, 正好与之对应。Venomous和domestic这两个属性的权值最小, 接近与0, 它们分别描述了动物是否有毒和是否家禽, 与分类的相关性比较小。predator这个属性的权值也较小, 它描述了是否是食肉动物。同时, 错分率E由原来的14.9%下降到5.94%。
六、结束语
本文在FKP算法的基础上, 将ReliefF算法与其相结合。实验表明, 该算法能够有效地提高聚类性能, 更便于分析各维属性对分类的贡献程度。
参考文献
[1]CHEN N, CHEN A, ZHOU L.Fuzzy K-prototypes algorithm for clustering mixed numeric and categorical valued data (in English) [J].软件学报, 2001.
[2]Kira K, Rendell L A.A practical approach to feature selection[A].In:Sleeman D, Edwards P, eds.Proceedings of the9th International Workshop on Machine Learning[C].San Francisco, CA:Morgan Kaufmann, 1992.
[3]Kononenko I.Estimating attributes:Analysis and extensions of Relief[A].In:De Raedt L, Bergadano F, eds·Proceedings of the7th European Conference on Machine Learning[C].Berlin:Springer, 1994.
FCM聚类算法的改进 篇9
模糊聚类分析作为非监督机器学习的主要技术之一,建立了样本类属的不确定性的描述,能够比较客观地反映现实世界[1],在图像分割、模式识别等诸多领域有着广泛地应用。模糊聚类算法中以模糊C均值(FCM)聚类算法应用最为广泛,但其有一些自身的缺点,比如聚类数目难以确定,如何确定有效的初始聚类中心和初始隶属度矩阵,迭代容易陷入局部极值,对大数据集聚类时的运算开销太大等。
针对FCM算法如何确定初始聚类中心及计算量大的问题,许多人对算法进行了改进,并提出了新算法。文献[2]和[3]分别使用网格和密度法,免疫记忆机理的方法来获取初始的聚类中心,减少算法的迭代次数,提高了算法的聚类效率;文献[4]和[5]通过对数据集的特征值的量化、合并、聚合,使数据集压缩、减少,从而把对数据集的聚类转化为对特征集的聚类。
本文结合两者优势,提出了一种改进算法:先通过数据集精简,压缩参与迭代运算的数据集,减少每次迭代过程的运算时间;接着对精简后的数据集采用密度函数法获得FCM算法的初始聚类中心,以减少FCM算法收敛所需的迭代次数;最后用FCM算法进行聚类。改进的FCM算法不仅较好地解决了聚类初值问题,且减少了算法的迭代次数和运行时间。
1 标准FCM算法
FCM算法是基于对目标函数优化基础上的一种数据聚类方法。设待分析数据集X={x1,x2,…,xn},分为C类,n为待聚类的样本数,由于任一数据点xj几乎不可能被严格地划分给某一类,定义它隶属于第i类的程度为Uik,Uik满足以下条件,如式(1)所示:
FCM算法的实质就是求使(2)式所示的聚类准则函数Jm最小的模糊划分矩阵U和类中心矩阵P,m∈[0,∞]是模糊加权指数。准则函数表示了各类数据点到相应聚类中心的加权距离平方和:
式(2)中,(dik)2=‖xk-p‖i2,dik表示样本xk到聚类中心pi的距离;P=(p1,p2,…,pc)表示各类的聚类中心。为使上述目标函数取得最小值,经数学推导得出满足条件的U和P的迭代公式如下:
算法的主要实现步骤如下:
(1)确定聚类类别数C和加权指数m,取dik为欧氏距离,设定迭代停止阈值ε为一小正数,初始化迭代次数l=0和模糊分类矩阵U(0);
(2)根据式(3)计算或更新模糊划分矩阵U(l);
(3)根据式(2),利用更新U(l),p(l)得到新的模糊分类矩阵p(l+1);
(4)选用适宜的矩阵范数比较p(l)和p(l+1),若‖p(l+1)-p(l)‖≤ε,迭代停止,否则置l=l+1,返回(2),继续迭代。
2 FCM算法的改进
由于在FCM算法中,运算量很大且其初始类中心又是随机选取的,本文从这两个方面提出了一种改进的FCM算法。
2.1 精简数据集
通过数据精简,使得具有相同特征的向量属于同一个类别,即对样本的特征向量进行压缩,使聚类的不同的样本数目从n减少到q(n>>q)。设数据集X中有q种特征的向量,则可以得到新的数据集X′={x1′,x2′,…,xq′},每种特征对应的向量个数为H=[h1,h2,…,hq],即hi为特征xi所对应的特征向量的数目。为了便于比较算法的性能,数据集X精简为X′以后,采用随机初始化聚类中心,用FCM算法对数据集X′聚类。本文将这种改进的FCM算法记为CFCM。
2.2 初始聚类中心的选取
上述数据集X精简以后,FCM算法采用随机函数对类中心初始化,由于初始化的随意性,使FCM算法需要很长的迭代过程才能收敛。所以,本文采用文献[6]中所定义的密度函数法,对精简后的数据集X'提取类中心,将它作为整个算法的初始聚类中心,用于FCM算法聚类。样本点Xi处的密度函数定义为:
式(4)中,fd=4/rd2,rd是领域密度有效半径,它的选择与数据集合的分布特性有关。这里取rd为N个样本的均方根距离的1/2,即:
由式(5)可知,在xi周围样本点越密集,则Di(0)值越大。故可以用来表示在样本空间中样本点的密集程度。令D1(*)=MAX{Di(0),i=1,2,…,N},对应x1(*)的取为第一个初始聚类中心,求后续初始聚类中心的密度函数迭代公式为:
式(6)中,C为聚类数目,Dk(*)=MAX{Di(k-1),i=1,2,…,N},对应的样本点xk(*)取为第k个初始聚类中心位置。
2.3 改进的FCM算法
本文从精简数据集节省迭代时间、初始化聚类中心减少迭代次数两个方面对FCM算法进行改进,这种改进的算法记为MFCM,其主要实现过程如下:
(1)确定类别数C和加权指数m,初始化迭代次数l=0和模糊分类矩阵U(0);
(2)精简数据,将数据集X压缩为X',得到q和H;
(3)对新数据集X′采用密度函数法,得到初始聚类中心;
(4)根据式(7)和式(8)计算或更新模糊划分矩阵U(l)和p(l),得到新的模糊分类矩阵p(l+1);
(5)若‖p(l+1)-p(l)‖≤ε,迭代停止,否则置l=l+1,返回(4),继续迭代。
3 实验结果
实验采用标准IRIS数据集进行算法测试,以检验算法的有效性。该数据集是150个关于三种花的生物统计数据,每个类别包含50个样本,其中第一个种类和其它两个种类完全分离,另外两个种类有交叉。其实际类中心为p1=(5.00,3.42,1.46,0.24),p2=(5.93,2.77,4.26,1.32),p3=(6.58,2.97,5.55,2.02)。为了测试改进算法的聚类性能,将原IRIS数据集放大10倍至1500个数据作为测试样本集。取聚类数c=3,加权指数m=2,用3种算法分别重复5次聚类实验。试验结果如表一所示,其中三种算法的聚类正确率依次为89.67%,92%,92%。
从表一可以看出,通过数据集精简,可以减少FCM算法的运行时间,CFCM算法减少了93.3%以上,而HFCM算法的运行时间减少了95.8%以上。由于HFCM算法采用密度函数法获取初始聚类中心,大大地减少了算法的迭代次数,CFCM算法的迭代次数减少了42.5%,而HFCM算法的减少了67.5%。此外,三种算法迭代结束后的聚类中心非常接近,表明改进的算法相对于FCM算法,聚类效果基本是一致的。
所以,实验证明了改进算法的有效性,改进的算法HFCM不但提高了算法的运行速度和收敛速度,而且保证了算法的聚类效果。
4 结束语
本文针对FCM算法对于初始值非常敏感、面对大数据集聚类运算量过大的缺点,通过优化参与计算的数据集和采用密度函数法获取初始聚类中心两个方面来优化算法,提出了改进的FCM算法HFCM。它在减少算法的迭代次数的同时,提高了算法的运行速度,并且保证了聚类效果的一致性。
参考文献
[1]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.
[2]盛莉,邹开其,等.基于网格和密度的模糊c均值聚类初始化方法[J].计算机应用与软件,2008,25(3):22-24.
[3]刘笛,朱学峰,苏彩红.一种新型的模糊c均值聚类初始化方法[J].计算机仿真,2004,21(11):148-151.
[4]Hung M C,Yang D L.An efficient fuzzy c-means clustering algorithm[C]//IEEE InternationalConference on Data Mining(ICDM2001),California,USA,2001:225-232.
[5]Eschrich S,Ke J W,Hall L O.Fast fuzzy clus-tering of infrared images[C]//IFSA World Congressand 20th AFIPS International Conference,Joint 9th,Vancouver,BC,Canada,2001,2:1145-1150.
聚类算法的改进的研究 篇10
Web文本挖掘作为Web数据挖掘的一个重要分支,可以对文档集合的内容进行分类、聚类、关联分析等。聚类是知识发现的重要工具,它是一种无指导的学习,能够从海量的数据中分析并挖掘出人们需要的东西,已经被广泛应用到信息管理、搜索引擎、推荐系统等多个领域。
1 类间距离
聚类就是按照对象的类间距离将距离近的放在一类,距离远的放在一类。聚类时常用的类间距离公式如下:
Single linkage(单连通):
Complete linkage(完全连通):
Average group(平均连通):
Centroid distance(质心距离):
2 层次聚类算法
2.1 传统层次凝聚算法
根据结果的生成顺序,层次聚类可以分为两类:分裂的层次聚类、凝聚的层次聚类。大部分层次聚类都属于后者,它先把每个对象看做一个类,然后将距离最近的两个类合并,直到所有对象都在一个类中,或者达到预定的停止条件。
下面举个例子来理解一下层次聚类算法的执行过程。假设有8个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(3,4)、C(1.5,1.5)、D(2,3)、E(4,4)、F(3,3.5)、G(5,5)、H(5,3.5)。我们选用欧几里得距离计算对象之间的初始化距离矩阵,结果如表1所示。
我们选用公式1,找到距离的最小值dB→F=0.50,然后将B、F归为一类(B,F),重新计算距离矩阵。经过一系列地合并、计算距离矩阵,最后我们得到聚类的层次为((((((B,F),E),D),H),G),(A,C)),如图1所示。
分析上面的计算过程,第一次合并的是距离最小的两个类,重新计算该类与其他类之间的距离时我们选择的是公式1,例如:d((B,F),E)→D=min(dBD,dFD,dED),其中dBD、dFD和dED都是从初始距离矩阵中得到的,即新的距离矩阵的值都来源于初始距离矩阵。第二次迭代时是从新的距离矩阵中取的最小值,那么这个最小值应该是初始距离矩阵中的次小值。依此类推,直到所有的对象合并完为止。
2.2 改进后的层次聚类算法
在上面的例子中可以看出,合并过程中每次迭代都要重新计算类间距离,比较浪费时间,我们发现合并是按照初始距离矩阵从小到大的顺序进行的,如果我们把初始距离矩阵中的元素用线性结构存储起来,对其进行从小到大的排序,那么合并类时只要顺序遍历线性结构就行了,这样就提高了层次聚类的速度。具体描述如下:
(1)将给定数据中的每个对象看做一类,计算各个类之间的距离dij,将距离存储在一维数组中。
(2)对一维数组进行升序排列。
(3)对于数组中的当前元素dij(即对象ix与xj之间的距离),可以分为三种情况:(1)如果xi∈Cm,xj∈Cn,则Ck=Cm∪Cn。(2)如果xi∈Cm,xj没有合并到类中,则Cm=Cm∪xj。(3)如果ix、xj都没有合并到类中,则
(4)重复步骤(3),直到数组中所有的元素处理完毕。
文献证明了改进后的层次聚类算法的运行速度提高了近3倍,而聚类的结果不受影响。
3 k-means算法
3.1 传统k-means聚类算法
k-means算法是一种应用最广泛的划分算法,它的聚类结果是平面的,一般用不相交的集合来表示。k-means聚类算法的基本思想:给定n个数据,随机地选择k个对象作为初始聚类中心,计算各个对象到聚类中心的聚类,将剩下的对象分配到聚类最近的类中,然后重新计算聚类中心,不断重复这个过程,直到所有的聚类不再发生变化为止。
下面举个例子来理解一下k-means算法的执行过程。假设有6个对象,每个对象有两个(也可以是多个)属性1x、2x:A(1,1)、B(2,1)、C(3,4)、D(4,3)、E(2,2)、F(5,4),我们的目标是将它们归为两类即K=2。选用A、B作为初始聚类中心,则C1=(1,1),C2=(2,1),选用欧几里得距离计算距离矩阵,如表2所示。
我们根据公式1,将对象划分到距离最近的那个类中,即,然后重新计算聚类中心,采用各个对象的平均值作为新的聚类中心,则再计算各个对象到新的聚类中心的距离。经过一系列地划分、计算聚类中心,最后得到的聚类结果为:C1=(A,B,E),C2=(C,D,F),如图2所示。
在k-means算法执行过程中,每次迭代都把数据分配到距离最近的类中,新的分类产生后,需要计算新的聚类中心,这个过程的时间复杂度为O(nd),则该算法总的时间复杂度为O(nkd),其中d是对象的维数,k是指定的聚类个数,n是数据对象的总个数。当数据量比较大时,算法的时间开销是非常大的。
3.2 改进后的k-means算法
在计算对象到聚类中心的距离时,我们采用的是欧几里得距离,该种计算方法具有4种性质(文档与自身的距离为0、非负性、对称性、三角不等式),其中三角不等式即从对象i到对象j的直接距离小于等于途径其他对象的距离。k-means算法每次迭代都要计算对象到每个聚类中心的距离,通过比较将对象分配到距离最近的聚类中,这些不必要的比较和距离计算比较浪费时间,我们可以利用三角不等式来减少每次迭代的计算次数,这样就可以处理大数据量时的时间开支问题。
具体流程为:
(1)任意选择k个对象作为初始聚类中心。
(2)计算每两个聚类中心的距离d(C i,Cj),其中i,j=1,2,k。
(3)对于每个对象ix,设它当前属于类ξi,ξi类的中心为iC,计算ix与iC的距离d(x i,C i)。如果d(C i,Cj)≥2d(x i,C i),则ix所在的类不变,否则,计算d(x i,Cj);如果d(x i,Cj)
(4)重复(2)、(3)步,直到所有聚类都不变化。
文献证明了该改进算法获得了很好的聚类效果,提高了算法的效率。
4 混合文本聚类算法
凝聚型层次聚类算法能够生成层次化的嵌套簇,准确度较高,但时间复杂性较高,运行速度较慢,在进行合并之后无法回溯。k-means聚类算法的运行速度较快,但是必须事先确定k的取值,对初始聚类中心的依赖性比较强,不适合发现非凸形状的聚类,虽然可以保证局部最小,但不能保证全局最小。
如果将凝聚型层次聚类算法与k-means算法结合起来,利用凝聚型层次聚类算法来产生k-means算法所需要的k值和初始聚类中心,可以有效的克服k-means算法的不足。
为了能更准确的发现用户的兴趣所在,本算法将2.2节改进的凝聚型层次聚类算法和3.2节改进的k-means聚类算法结合起来。
具体流程如下:
(1)计算给定的文档集合D={d 1,di,dn}中各个数据间的距离dij,将距离存放在一维数组中。
(2)对一维数组进行升序排列。
(3)将文档集合D看成是一个聚类C={c 1,ci,cn},其中ci={d i}。
(4)设定一阈值ξm,如果数组中的当前元素dij≤ξm,则分为三种情况:(1)如果di∈cm,dj∈cn,则ck=cm∪cn。(2)如果di∈cm,dj没有合并到类中,则cm=cm∪dj。(3)如果di、dj都没有合并到类中,则ck=di∪dj。重复步骤(4),直到数组中所有元素处理完。否则如果dij>ξm,凝聚算法结束,得到含有k个子类的聚类C={c 1,ci,ck}。
(5)将C={c 1,ci,ck}作为k-means算法的初始聚类中心。
(6)计算每两个聚类中心的距离d(c i,c j)。
(7)对于D中的每个文档di,设它当前属于类ξi,ξi类的中心为ic,计算di与ic的距离d(d i,c i)。如果d(c i,c j)≥2d(d i,c i),则di所在的类不变,否则,计算d(d i,c j);如果d(d i,c j)
(8)重复步骤(6)、(7),直到所有聚类都不再变化。
5 结论
本文提出的混合文本聚类算法的难点就是阈值的确定,要通过相关领域知识来选定阈值,才能得到满意的聚类结果。笔者将该算法用到了一个小型的个性化搜索引擎中,通过试验将阈值定义为5.0,对用户的浏览记录进行聚类,较好的挖掘出了用户感兴趣的内容。
随着Web技术的发展以及用户的需求和行为日益多元化,如何从海量的数据中分析并挖掘出人们需要的内容,个性化的搜索引擎已经成为人们研究的热点,聚类的研究也将成为人们研究的热点。
参考文献
[1]段明秀,杨路明.对层次聚类算法的改进[J].湖南理工学院学报(自然科学版).2008.
[2]王会芬.基于Web的网页聚类系统的研究与实现[D].天津大学硕士学位论文.2005.
[3]严华.一种改进的k-means算法[J].计算机与现代化.2009.
[4]易珺.改进的k-means算法在客户细分中的应用研究[J].微型机与应用.2005.
聚类算法 篇11
关键词：kmeans算法；簇心；kd树；剪枝策略；CKmeans算法
中图分类号：TN914文献标识码：A
1引言
数据挖掘是一种经典有效的数据分析方法，聚类分析是数据挖掘中的重要研究内容。数据对象通过聚类分析，可以形成簇或者类内部数据对象相似度高且不同簇之间的数据对象相似度低的簇组。目前主要的聚类方法有：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法[1]。kmeans算法是一种传统的聚类算法，其算法易于实现、时间复杂度小和可以处理大型数据集等优势明显。
Kmeans算法作为一种常用的聚类算法，在处理多维和海量数据时，由于需要提前给定簇的个数，聚类结果随初始质心变化的波动大，重新计算质心时受到孤立点影响，而且仅适用于类簇之间区别较大的情况，同时聚类过程时间消耗过长，因此提高该算法的执行效率。
在文献[2]中，李涛等提出了一种引入竞争策略的聚类算法。受文献[2]、[3]的影响，本文提出一种kmeans算法的改进算法称为Ckmeans算法。该算法从多维数据中随机选取某一维数值并均分为k个数值域。初始聚类中心从k个数值域中选取，以减少迭代次数来提高算法效率。引入了K-d树，对样本点的数据结构进行标准化，从而便于节点的遍历和查询。同时，该算法采用了剪枝的策略，减少参与计算节点和候选聚类簇心之间欧式距离的计算量，从而能够明显地降低算法时间复杂度。在剪枝时，计算最小距离时利用k-d树最近邻查询算法，计算最大距离时利用数据节点代表的空间范围最大值，从而大大提高了剪枝策略的有效性。通过对传统的kmeans聚类算法进行此方法的改进，进而提高了算法的运行效率。
2Kmeans 算法
2.1Kmeans 算法简介
Kmeans算法是一种基于划分的传统聚类方法，该算法的基本思想是：在n个数据对象中，首先随机初始化k个簇心，每个点分派给最近的簇心，分派到同一个簇心的所有数据对象的集合构成一个簇，接着根据分派到簇的点，更新每个簇的簇心，重复分派和更新簇心过程，直到簇的簇心不发生变化，最终得到目标函数最小的k个类。
计算技术与自动化2015年12月
第34卷第4期高亮等：基于Kd树改进的高效Kmeans聚类算法
2.2Kmeans 算法的优势
Kmeans算法是一种高效的聚类算法，在科学研究和工程应用中得到了应用和推广，它的算法流程比较简单，并且收敛速度很快，对于大数据集也有较好的分类效果，其时间复杂度为O（tkdn）， t是迭代次数，k是簇类的个数，d是数据集的维数，n是样本点数。在对大型数据集聚类时，Kmeans算法比层次聚类算法快得多[4]。
2.3Kmeans 算法的不足
1）必须提前给定要形成的聚类个数k。
Kmeans算法必须提前给定要形成的聚类个数k，聚类的结果对此有很大的依赖性，然而通常最恰当划分数据集的聚类的个数并不是事先可知的，一般需要通过多次反复试验才能得到该聚类个数，因此在算法的开始就指定聚类个数会影响聚类过程和结果是很明显的。
2）聚类结果随初始聚类中心变化的波动大。
Kmeans算法随机指定初始聚类中心，这给聚类结果带来很大影响，聚类结果变得不稳定，有可能导致局部最优。
3）重新计算质心时受到孤立点影响。
在聚类的迭代过程中，要重新计算以形成新的质心，但是与类簇距离明显的孤立点导致计算的质心也偏离真正的数据密集区，质心的代表性下降，新的聚类过程受到孤立点的影响大。
4）仅适用于类簇之间区别较大的情况。
由于Kmeans算法根据欧式距离度量各个点之间的距离，并且聚类准则函数使用偏差和准则函数，聚类过程参考该准则函数。只有当类簇之间区别明显是，聚类才会有效，否则可能导致聚类的过程反复不定，不断将形成的类簇分割的情况。
5）聚类过程时间消耗。
Kmeans算法的聚类是一个不断的迭代的过程。一旦形成类簇，就重新计算质心，然后重新计算距离并指派，当解决大数据量的问题时，算法的聚类过程会消耗大量的时间。
本文针对Kmeans算法对海量数据和多维数据运算速度慢，时间消耗大的缺陷，提出改进算法CKmeans，以期提高算法的运算效率。
3KD树
Kd树（多维二叉搜索树）是由Bentley于1975年提出[5]，k是空间数据对象的维度数，在多维的空间数据结构中，Kd树常用来数据索引和数据查询。kd树通过把一个空间划分成多个不相交的子空间来进行高效的组织k维空间中点的集合。kd树中内部节点对象包含有某一维的区分值，其中小于或等于区分值的点划分到左子树，大于区分值的点划分到右子树。Kd树本质上是一种二元搜索树，它用超平面把一个空间划分成若干子空间来对数据搜索，可以快速而准确地找到某一点的最近邻。
3.1Kd树构造算法
Kd树的构造是多次使用垂直于坐标轴的超平面分割k维空间实现的，所有的对象都组织到树中，其中根节点代表所有的对象。
在Kd树的构造中，一方面考虑在数据对象维度进行分割时，选择基于顺序循环分割或者基于维的长度优先分割；另一方面考虑分割点的判断，选择基于中点的方法或者基于中值点的方法。在文献[6]中的研究表明，这两个因素的选择分别为从最长的维度开始分割和选择中点的方法较好，本文采用上述方法。Kd树构造是多次递归地调用Kd树构造函数实现的，Kd树构造算法的时间复杂是O（nlogn）。
Kd树的构造算法[7]如下：
输入：维度为d的数据对象集合X和Kd树的深度Depth；
输出：包含所有数据对象的Kd树根节点KD。
1）若数据对象集合X为空，返回空Kd树；
2）调取节点判断的函数，
（1）计算数据对象每一维数值的方差值，分割维Split的顺序按方差大小来判断，
（2）取每一维的中点值作为分割点MidPoint；
3）在Split维时分割点MidPoint划分数据集合，得到子集合X1和X2，X1：在Split维的数据对象都小于或等于MidPoint，X2：在Split维的数据对象都大于MidPoint；
4）Lchild为KD的左子节点，Rchild为KD的右子节点，Lchild=KdConstruct（X1，Depth+1），Rchild=KdConstruct（X2， Depth +1），递归地调用直到子节点为叶子节点；
5）把Lchild和Rchild 合并为Node，返回Node。
3.2Kd树上的最邻近查找算法
Kd树是一种很好寻找最近邻问题的数据结构，Kd树的查找有最近邻搜索和范围搜索两种基本方式。Kd树上的最邻近查找算法即在Kd树中检索与某一查询点欧式距离最近的数据点[8-9]。kd树最近邻查找算法描述如下：
输入：Kd树类型的KD和查找对象Object；
输出：最近邻数据点。
1）若数据KD为Null，返回；
2）从根节点递归地向下搜索，进行二叉搜索；
3）搜索到叶子节点，记为当前最近邻Nearest；
4）回溯搜索：
if 超球与父节点超平面相交，进入相反的空间搜索，更新Nearest，else继续向上回溯，父节点相反的空间不查找；
5）回溯到根节点，结束并返回最近邻。
4Ckmeans算法
本节内容为Ckmeans算法的详细设计描述。
4.1Ckmeans 算法设计
在改进Kmeans算法过程中，通过对Kmeans算法运行时间进行分析来提出改进，提高算法的运行效率。设初始簇心时间为Tinit，分派样本点时间Tassign，重新计算簇心时间为Tagain，Kmeans算法迭代次数为t，Kmeans算法的运行时间Tsum。则有以下算法的运行公式：
Tsum=Tinit+tx（Tassign+Tagain）…（1）
由公式（1）可知，若要提高算法的运行效率，可以通过减少算法的迭代次数和指派时间来实现。
对于d维数据集X，在d维选取其中的一维数值，对该维数值进行排序，则存在一个对应的区间[m，n]，给定一个整数常量k，把区间[m，n]分成k个子区间，子区间长度是相同的，则规定C={C1，C2，...，Ck-1}为区间等间隔集，当i=1时，C1=（m-n）/k；当i=2，3，…，k-1时，Ci=Ci-1+C1。pkmeans算法的k个初始簇心分别从C（k等分）的每一个子区间中选取。通过对kmeans算法选取初始簇心的随机性进行改进，达到减少迭代次数来提高Ckmeans算法运行效率的目的。
在Kmeans算法分配数据样本点的过程中，需要保证数据集X中的样本点被指派给最近的簇心，当所有样本点分配结束之后，重新计算簇心。Kmeans算法对于X中的样本点，需要计算其与所有簇心的距离，然后找到最近距离的簇心。
在Ckmeans算法中，通过引入Kd树，使得样本点数据结构标准化，便于遍历和查询。通过采用剪枝策略，减少了要参与计算的点和候选簇心的欧式距离计算量，可以显著的减少算法的时间复杂性。剪枝策略：首先搜索候选簇心集中的每个簇心到该节点对象所代表的空间区域的最近邻距离MinDis，最小距离采用Kd树最近邻查询算法获取，然后把该节点对象所代表的空间区域的最大距离记作MaxDis，最大距离采用节点所代表的空间范围的最大值，最后把最近邻距离大于最大距离的最小者的簇心剪去。
Ckmean算法的基本思想是：将数据集初始成Kd树，从d维数据集X中选取一维数值，排序后形成区间等间隔集，得到算法的初始簇心集。从初始化后的Kd树的根节点对象开始，根据最小距离最大距离原则剪枝，根节点对象于全部候选簇心集计算欧式距离，而子节点只从父节点的候选簇心集剪枝。分配数据对象后，再次计算簇心，直到目标函数值收敛。如图1所示，Ckmeans算法可以描述：
输入：聚类个数k以及包含d维的n个数据对象数据集X；
输出：满足目标函数值QUOTE最小的k个聚类。
1）将样本集合X构造Kd树；
2）簇心初始化，在数据集d维中取一维排序成区间等间隔集，取k个初始簇心；
3）修剪节点对象的候选簇心集；
4）计算节点对象到修剪后的候选簇心的距离并当距离最小时把对象Xi分配给簇Cj；
5）重新计算：重新计算与簇心；
6）重复步骤3）和4），直到值收敛。
4.2Ckmeans 算法中剪枝策略
剪枝原则如下：首先搜索候选簇心集中的每个质心到该节点对象所代表的空间区域的最近邻距离MinDis，然后把该节点对象所代表的空间区域的最大距离记作MaxDis（在构造kd树的过程中形成的数据结构），最后把最近邻距离大于最大距离的最小者的质心剪去。
具体的剪枝策略如下：假设存在一个数据集合X，数据集X为{（3.5，4），（1.5，5.5），（5.5，2），（1，3），（2.5，7），（4.5，0.5），（6.5，7.5），（2，2.5），（8.5，5）}，对该数据集构建K-d树结构如图2所示：
已经选择的候选簇心集为：{（9.5，9.5），（9.7，1.5），（4，5.5），（1.5，9.5），（2，4）}，根节点为O1（3.5，4.0），候选簇心集为{ X1，X2，X3，X4，X5}，该点被指派给质心：X3；根节点的左叶子节点O2（1.5，5.5），所代表的空间范围为（1，2.5）和（3.5，7）所包围的矩形，父节点的候选簇心的个数为：5，即{ X1，X2，X3，X4，X5}，针对5个候选簇心有如表1的计算结果。
如表所示，其中最大距离中的最小者为6.3246。将最近邻距离大于最大距离的最小者的质心剪去后，只剩下3个质心，即{X3，X4，X5}。则针对左叶子节点O2（1.5，5.5）的候选簇心集为：{X3，X4，X5}，该点被指派给质心：X5。对于各个候选簇心与该节点对象的最近距离与最远距离表示如图3所示。以此类推，对节点O2（1.5，5.5）的左叶子节点O8（2，2.5）也进行剪枝，其中参与剪枝的候选簇心集合只从其父节点的候选簇心集合中选取，结果是{X3，X4，X5}，在剪枝工作之后的候选簇心集合是{X3，X5}。对于其他的节点对象也采取相同的操作策略，对数据集合所构建的k-d树的左子树上的各个节点，在采取了剪枝操作之后，相应的候选簇心情况如图4所示。
从图4中我们可以看到，在经过了剪枝操作之后，每个节点都拥有相应的候选簇心集合，并且这个候选簇心集合中质心的个数明显少于初始的整体簇心集合，如此就能减少节点与质心之间欧式距离的计算量，从而有效地减少运算时间，提高了运算的效率。
5实验结果及分析
在试验中，算法的程序用Java语言实现，编译环境为Eclipse。实验的计算机环境为： Intel（R） Core（TM） i3-2120 CPU，3.30 GHz，2.85G内存，操作系统为windows XP Sp3。
本文用到的测试数据集来源于文献[10]中，并没有数据集进行任何特殊的优化。为了体现算法对不同数据规模体现的效率，选用2个测试数据集对Kmeans和Ckmeans进行实验，分别是data[1024，2]和data[1024，10]。data[1024，2]数据集表示由1024个数据点和2维属性构成，data[1024，10]类同。在这2个数据集上对k=20、30、40、50、60、70、80、90分别进行测试。针对每种情况进行20次试验。
实验结果如下图5和图6所示。由实验结果分析可知：与Kmeans算法相比，Ckmeans算法在精度上与其近似，但是Ckmeans算法在运行效率上明显优于Kmeans算法。
1）在运行效率上，Ckmeans算法优于Kmeans算法，随着数据集维度增加和聚类个数的增加，Ckmeans算法的优势更加明显。当数据集维度为10时，Ckmeans算法的运行时间相对于Kmeans算法的节省了2～3倍。
2）当数据集维度为2时，Ckmeans算法的运行效率优势比较微弱，但在此数据规模下当聚类个数不断增加，Pkmeans算法的运行效率优势显示出来。
6结论
通过对经典Kmeans的分析和研究，为了提高算法的运行效率，对Kmeans算法进行改进。改进的算法优化了传统随机选取簇心的初始化方法，提出了基于Kd树和剪枝策略的Ckmeans算法。经过实验结果比较，改进后的算法与原有算法具有相似的精度，但是改进后的算法的运行效率明显提高，尤其是对于高维数据效果更明显。把它应用在农业气象灾害区划系统之中，对于提高气候区划的精度，以及系统的反应速度都有着比较好的参考价值和意义，同时对满足其他科学的研究和工程应用需求也提供了非常良好的借鉴作用。然而，这仅仅是在数值计算领域得到了验证，如何将其应用于非数值数据的聚类分析与计算中，仍然是今后的研究方向。
参考文献
[1]WANG Qian，WANG Cheng.Review of Kmeans clustering algorithm[J].Electronic Design Engineering，2012.
[2]Tao Li，Shuren Bai，Jinyang Ning.An improved Kmeans Algorithm Based on Competitive Strategy[J].In： International Conference on Information and Multimedia Technology.Hong Kong：IEEE Computer Society，2010，2：76-80
[3]ZHAI Dong-hai，YU Jiang，GAO Fei.K-means text clustering algorithm based on initial cluster centers selection according to maximum distance[J].Application Research of Computers.2014.
[4]HUANG Z.A fast clustering algorithm to cluster very large categorical data sets in data mining. In： Tucson： the SIGMOD Workshop on Research Issues on Data Mining and knowledge Discovery.Tuncson， 1997， 146～151
[5]BENTLEY J.Multidimensional binary search trees used for associative searching[J].Journal of Communications of the ACM， Vol.18， No.9： 509- 517，1975.
[6]Jiang Xiaoping，Li chenghua.Parallel implementing kmeans clustering algorithm using MapReaduce programming mode[J].J.Huazhong Univ.of.Sci&Tech.（Matural Science Edition）.2011
[7]Chen Xiaokang，Liu Zhusong.K Nearest Neighbor Query Based on Improved KdTree Construction Algorithm[J].Journal of Guangdong University of Technology.2014
[8]MOORE A W. An introductory tutorial on kdtrees[D]. Extract from Andrew Moore's PhD Thesis： Efficient Memorybased Learning for Robot Control Technical Report No. 209.1991
[9]STEPHEN J.Redmond，Conor Heneghan.Method for Initializing the Kmeans Clustering Algorithm Using Kdtrees[J]. Pattern Recognition Letters， 2007，28（8）：965-973.
聚类算法 篇12
关键词：车牌识别,车牌定位,K-均值,聚类,字符识别
机动车号牌识别系统主要功能是通过图像采集和图像识别的手段识别机动车的身份。对车牌识别领域的研究最初起源于二十世纪九十年代的发达国家, 而国内的研究起源于二十世纪末。号牌识别的最主要的步骤是:车牌定位、字符分割和字符识别。而后两者现在基本已经达成共识, 字符分割采用对二值化图片进行垂直投影和水平投影, 字符识别使用模板匹配方法或者SVM方式。最重要而且方案最多样化的步骤还是在车牌定位上。
车牌定位基本可以分为三种大的研究方向:对灰度图像进行边缘检测、对灰度图像进行角点检测和对彩色图像进行颜色模型处理。边缘特征是人类视觉感知的重要来源, 文献将边缘检测理论、形态学填充、腐蚀开运算后得到车牌待选区域, 最后分析获取车牌位置, 边缘检测作为研究范围最广和目前大多数产品使用的技术, 的确具有速度快、准确率较高的特点, 尽管现有的边缘检测算子十分成熟, 但是没有一种适应于任何图像质量、任何图形环境的边缘提取方法, 而且为了得到高识别率, 对于每幅图像要选用合适的边缘检测算子。文献将彩色图像转换到HSV颜色空间中对色彩进行分层处理是车牌定位彩色图像处理方向较新颖的方法, 但是这类方法的缺点也是很明显的, 当车身颜色与牌照颜色相近时, 辨识就变的几乎不可能了。文献提出了角点检测法, 因为角点代表的特征像素点占图像像素总数的百分之一, 却构成物体大部分的外形要素, 由于牌照的字符部分角点数较多, 所以作者使用Harris算法获取整幅图像的所有角点, 然后使用一个固定大小的滑窗去遍历图中的角点以得到牌照待选区域。通过角点获取牌照区域受干扰小, 识别的效率也比较高, 是应该深入研究的方向。
1 车牌标准分析
现行的《中华人民共和国公共安全行业标准——中华人民共和国机动车号牌》 (GA36-2007) , 于2007年9月28日发布, 同年11月1日实施, 用来代替原来的国标GA36-1992。按照GA36-2007的标准, 为了我们计算机识别的方便, 我重新整理从号牌行数和号牌特征着手归纳, 见表1。
经过归类并简化后, 很大程度上避免了排列方式对识别算法的干扰, 在字符分割阶段对车牌进行横向投影分析号牌分类是单行牌照还是双行牌照, 并根据上表优化算法, 可以达到快速准确的目的, 见图1。
下面从典型的单行牌照, 分析其字符规律。牌照中的字符分为三段:第一个字符是省、自治区或者直辖市的简称, 确定为汉字字符;第二个字符是发牌机关代号, 是大写的英文字母;第三至第七个字符为序号, 通常为大写英文字符和阿拉伯数字字符的排列, 对于特别号段的车辆会在末位字符出现“警”“领”“学”“临”“试”“港”“澳”等汉字字符。
典型的双行牌照, 见图2。双行牌照第一行就是单行牌照分割点前的两个字符, 第二行是单行牌照的第三位到第七位。双行牌照和单行牌照相比, 长宽比更小。
从颜色方面看, 无论是单行的牌照还是双行的牌照, 都有多种颜色的排列组合。但是归纳来说, 牌照背景颜色和牌照字体颜色的组合一共是四种, 分别是:黄底黑字、蓝底白字、黑底白字、白底黑字。特殊分类的字符颜色为红色, 而且特殊字符不会出现在蓝底背景的牌照上面。
2 原始K-均值算法
用Harris角点检测算法运算后的图像, 通过观察可以发现“牌照区域肯定是角点聚集的区域, 但是角点聚集的区域不一定是牌照所在区域”, 需要使用一个聚类分析方法来找到若干个角点聚集区域, 然后通过对区域特征的筛选, 最终决定牌照位置。K-均值算法是一种得到了广泛使用的基于划分的聚类算法, 算法把n个数据点按照目标函数分为k个簇, 以使簇内数据点具有较高的相似度, 而这个目标函数可以是欧氏距离。K-均值算法满足了希望把n个角点以欧氏距离分为k个号牌待选区域的思想, 而且它的时间复杂度是O (tkn) , t是迭代次数, 所以对图3 (a) 上由Harris算法得到的角点执行K-均值算法, 经t次迭代得到k个簇, 见图3。
3 改进K-均值算法
使用原始K-均值算法并不能在每次收敛后都得到牌照正确的区域 (见图4) , 因为其算法本身是用于数据挖掘的, 算法中初始点是随机决定的, 目标函数使用的是欧氏距离, 为适应号牌识别的效率和识别率双重的要求, 需要对其修改。在这个过程中, 参考了文献, 但是考虑到文中AP算法的时间复杂度高, 所以还是用K-均值算法。
首先从算法的随机取初始点着手, 通过实验发现初始随机点选择的结果不同, 收敛后的簇是可能不一致的, 所以尽量要选择一种既能接近最终收敛簇的形心, 又能是一种快速稳定的初始点提取算法。研究后决定用分冶思想把图像分成若干个矩形区域, 算法1的步骤如下:
步骤2, 遍历Ci, 2这张存放了角点的二维表, , 1/ij=C×M W, k Ci, 2N/H=×, Aj, kAj, k1=+。
步骤3, 设值max, 遍历Aj, k, 当Aj-1, k, Aj+1, k, Aj, k-1, Aj, k+1均未被访问过时, max=Aj, k, 并标记Aj, k为已访问过。
步骤4, 循环到步骤3, 所有的初始点都选出为止。
第二点的改进是传统的K-均值聚类时使用的欧氏距离, 而牌照的规格不是圆, 需要使用标准化的欧氏距离公式。两个n维向量a (x11, x12, ..., x1n) 与
b (x21, x22, ..., x2n) 间的标准化欧氏距离公式为:
其中ks是分量的标准差, 对于最常见的440mm×140mm的机动车牌照上二维的角点数据, 公式可以推导为
于是整个号牌定位的算法可以这样描述:
步骤1, 使用FAST角点算法获取图中角点。
步骤2, 使用算法1提取K-均值的初始点。
步骤3, 以计算出的中心点执行K-均值算法。
步骤4, 修改K-均值算法使用公式1。
步骤5, 在聚类后获取的簇所组成的矩形中, 根据车牌标准, 删除以下情况:高要比宽大;宽大于高的3.5倍;宽小于高的2倍;号牌颜色面积小于总面积50%。
执行上述算法后得到图5, 其中左边一张是通过上述算法得到的初始点, 右图是通过初始点再调用K-均值算法得到最终的角点分类后各个区域的中心, 从中可以发现初始点已经很接近最终的收敛结果, 所以这种算法可以大大的加快K-均值算法迭代的速度, 而且使得K-均值算法的执行速度是快速的, 结果是稳定的。
4 算法效率实验
测试数据集的描述:本文采用从网上随机选取的二十七张车辆正面图片作为样本来验证改进后的算法的效率。通过FAST角点检测, 其中每张图产生一千个以下的角点。
算法对比:分别用传统K-均值算法、滑窗定位法和改进过的K-均值算法分别对样本图片的角点进行聚类, 分别从平均识别速度和平均识别率两个方面进行对比, 见表2。
表2是对三种不同聚类算法的实验结果的汇总, 给出了具体量化的数据, 通过表2可看出传统K-均值算法由于迭代次数多而收敛速度慢, 并且识别率低。而改进后的K-均值算法虽然算法复杂但是由于迭代过程的改进使得识别速度和平均识别率都得到了很好的平衡。
5 车牌字符分割算法研究
本章节将讨论车牌字符分割问题。车牌字符的分割是车辆号牌识别流程中承上启下的环节, 主要是继续前章车牌定位的工作结果, 主要任务是从一张车牌图像中准确可靠的分割得到各个字符并完成归一化的工作, 提供给下面字符识别环节来进行分析。
由于机动车牌照存在单行车牌和双行车牌, 所以进行列分割之前要首先进行判断。通过分析车牌区域的水平投影图的形态就可以知道, 见图7。
因为车牌尺寸不同, 必须对它进行归一操作:将牌照灰度图缩放到100×50像素, 计算各行中段约25%~75%的区域, 在这个区域中搜索灰度值最小点, 若该点在接近1/3处, 该号牌就是双行车牌, 否则是单行车牌。下面介绍用列分割方法把单行车牌进行字符分割。首先对车牌定位后的图像进行二值化操作 (临界灰度值是160) , 这样得到的二值化图像减少了光照不均的影响。然后对单行车牌区域的二值化图像做垂直投影, 见图8。
然后通过下列的步骤实现字符分割, 其中投影图为P。
步骤1:令max P=MAX (P) , 得到投影图中的最值。
步骤2:寻找N中的0值点, 以0值点将N分为若干块:recti, i=1, 2, 3, ...。
步骤4:各块宽度为width=imax (recti) -min (recti) 。宽度中值为media Width。将widthi<media Width×1.2的块就近合并。
步骤5:若recti的宽度大于两倍中值宽度, 按中点将其分拆成两块。
步骤6:重复步骤4和5, 直到无合并或拆分操作为止。
步骤7:如果块宽度小于各块平均宽度, 以该块中心左右往外media Width2作为分割点;否则以该块左右边界为分割点。
步骤8:按照分割点分割图像, 按照各分割块的左右次序对其编号。
步骤9:分析各块底色 (二值化图像为0的点) 的平均色度值, 将其和车牌区域底色比较, 删除误差超过50%的块。
这样就把字符从定位好的牌照图像中分离出来了, 见图9。
6 车牌字符分割识别研究
支持向量机来识别号牌字符, 利用其良好的分类能力, 可以用来对字符进行分类, 有很高的字符识别率。
1992年开始在统计学习理论领域发展了一种称为支持向量机 (Support Vector Machine, SVM) 的新的模式识别方法, 在解决小样本、非线性及高维模式识别的问题中表现出很好的性能。由于同时神经网络遇到了网络结构固定、过学习和欠学习问题, 所以支持向量机方法成了机器学习领域内新的热点。
SVM方法从线性可分的最优分类面 (Optimal Hyper-plane) 提出了二类分类技术。它通过构造最优超平面使得不同样本类的距离最大化。
yi[ (wixi) +b]-1≥0, i=1, 2, ..., n就得到了最优的分类面。表述成约束优化问题就是在 (l) d的条件下, 求方程
对w和b偏微分并使之等于0, 得到对偶问题
在线性不可分情况下, 增加了松弛项ξi≥0, 分类条件方程变成:
所谓SVM的训练, 就是通过已有的样本, 求得支撑最优分类面的样本向量。由于SVM自身的特点, 相对于识别的样本, 只需要少量样本进行训练。这一点就满足车牌字符识别系统的要求。同时, 如果把整个字符作为输入数据, 输入样本就具有高维度的特征, 这要求分类器能够进行高效的高维度数据分类能力, 这也是SVM的优势所在。鉴于以上这些原因, 构造了用于车牌字符识别的支持向量机, 并使用大量实际数据效验所设计方法的有效性。训练中从100多张尺寸为800×600的各类机动车照片中分割出700多张字符照片, 其中某种字符的照片数是大于1的, 按照字符分类, 每种字符抽取一张, 一共71张字符照片, 手动选定字符系统自动对其进行缩放操作, 统一成32×16像素的图片, 然后再进行灰度化操作和二值化操作 (通过实验二值化的阀值定为灰度值160) , 这样每个字符照片所包含的信息量是相同的。实验中使用的支持向量机是由台湾林智仁教授开发的libsvm, 由于Objective-C是向下支持C语言的, 所以libsvm (C语言版) 是可以直接用于Objective-C开发的, 见图10。使用svm_train来进行训练。
识别的步骤和训练的步骤是相似的。对于从字符分割后的字母/数字图片, 首先进行灰度化和二值化处理 (二值化的阀值定为灰度值160) , 这样把产生的二进制数值作为一个svm节点, 加载SVM自识别系统在磁盘上的识别模型, 返回识别的结果。
7 号牌识别应用
最后在一台联想Think Pad T430上, 安装了Mac OS Mountain Lion (10.8.5) X64位操作系统和Xcode编程开发软件, 并把APP运行在一台i Phone 4 (操作系统IOS7.1.2) 上实现了号牌识别的全部功能, 见图11。
经过号牌定位、字符分割和字符识别三大步骤后, 实验在真机上的运行效果如图10所示。
8 结语
针对车牌定位这个难点问题, 本文将K-均值算法用于号牌识别的算法并进行了优化, 首先提出用分冶思想用于K-均值算法的初始点选取;然后对K-均值算法得到的结果, 也就是号牌候选区域进行筛选, 结合形状和颜色等因素来最后精确定位车牌, 这样既提高了算法的收敛速度, 又增加了算法的准确性。经IOS平台上实现的整个号牌识别程序实验结果, 证明改进后的号牌定位算法提高了识别率, 成效显著。
参考文献
[1]王晓雪, 苏杏丽.数字图像处理在车牌识别中的应用[J].自动化仪表, 2010, 31 (7) :22.
[2]迟晓君.一种基于支持向量机的车牌字符识别方法[J].信息技术与信息化, 2007, (6) :
【聚类算法】推荐阅读：
聚类分割算法05-12
聚类分析算法08-31
模糊聚类:遗传算法10-01
凝聚聚类算法11-04
C均值聚类算法08-17
K-最近邻聚类算法06-07
数据流聚类算法研究07-07
动态K-均值聚类算法09-03
k-mean聚类算法论文10-03
算法及算法评价09-30