范文一:有约束的半监督聚类方法
数据库信息处理◎、◎
有约束的半监督聚类方法
刘应东
LIU Ying-dong
兰州交通大学 交通运输学院,兰州 730070
,,,School of Traffic and TransportationLanzhou Jiaotong UniversityLanzhou 730070China
:E-mailfenxinshi@163.com
,,():LIU Ying-dong.Semi-supervised clustering method with constrains.Computer Engineering and Applications20094522100-102.
: ,,AbstractIn many data mining domainsthere is a large supply of unlabeled data but limited labeled datawhich can be
,,,expensive to generate.Consequentlysemi -supervised clusteringwhich uses a small amount of labeled data to aid unlabeled clustering
,has become a topic of significant recent interest.This paper presents a new algorithmcalled semi-supervised clustering algorithm
,,based on constrains learningwhich obtains the similarity and dissimilarity criterions of data objectsadjusts them in the process of
,,clusteringand uses them to constrain and supervise clustering.Demonstrated the clustering algorithm with Gaussian datasetand the experimental results confirm that the clustering algorithm significantly improves the accuracy and speed of clustering when given a
relatively small amount of supervision.
:;;;Key wordsdata mininglabeled dataconstrainssemi-supervised clustering
摘 要:在数据挖掘领域的很多实际应用中,获取大量的无标签样本非常容易,而获取有标签的样本通常需要付出较大的代价,并
且有时不可能得到所有的数据的标签,半监督聚类就是使用一小部分的标签数据对无标签数据的聚类过程进行指导。提出了一种 新的
半监督聚类算法,它利用标签数据提供的信息来初步确定数据的相似性和不相似性标准,并在聚类过程中对其进行自动调 整,利用
它们对聚类过程进行约束和指导。通过在标准数据集高斯数据集上的测试,该算法相对于无指导聚类来说有更高的精度 和更快的速度。
关键词:数据挖掘;标签数据;约束;半监督聚类
:文章编号:()文献标识码:中图分类号:DOI10.3778/j.issn.1002-8331.2009.22.033 1002,8331200922-0100-03 A TP301
基于相似性的方法是首先在标签数据集上进行训练学习得到 聚类是数据挖掘、模式识别、机器学习中的一项重要的数 [4]相似矩阵,然后利用相似矩阵对聚类过程进行指导。对相似 据分析技术。聚类试图把一个数据集分割成若干类,使得同一
矩阵的训练方法有:使用 算法对串的编辑距离进行训练 类中的数据对象之间具有较强的相似性,而不同类之间的数据 EM [4][5]学习,使用最短路径算法修改欧氏距离,使用凸优化方法训 对象具有较弱的相似性,但是作为一个非指导的学习任务,很 [6]练明考斯基距离()。Mahalanobis distance 难确定一个给定的数据集中到底包含了多少个类、最后的聚类
提出一种半监督聚类算法,基于约束的半监督聚类算法它。 结果是否和实际相符合。为了解决这种类型的问题,对数据集
首先通过对标签数据的学习得到标签数据的相似性阈值和 不中的一小部分数据进行研究,弄清这部分数据的特性并对其作
相似性阈值,把这两个阈值作为聚类过程中的数据对象必须 标记,使其作为标签数据,由于时间和经济问题,标签数据所占 的
满足的两个条件(约束)。由于标签数据所占比例较小,可能导 比例较小。如何有效地利用这些标签数据对聚类过程进行指导,
致相似性阈值过小而不相似性阈值过大,使得聚类结果中类的 是半监督聚类中研究的核心问题。
数目较大,有可能需要对其中的某些类进行合并。使用类间的 利用标签数据的标签信息来改善无监督聚类算法的性能,
影响因子来衡量两个类间的相似程度,使用标签数据、数据对 是半监督聚类研究的热点问题。根据对标签数据的标签信息的
使用方法,半监督聚类通常被划分为基于搜索的方法(象间的不相似性阈值和影响因子对某些类进行合并,在合并的 search-
)和基于相似性的方法(过程中自动更新约束和影响因子的值。在高斯数据集上的实验 based approachessimilarity-based ap,
表明该算法不但能够利用标签数据的信息,还不受制于标签数 )。基于搜索的方法使用用户提供的标签信息或限制对 proaches[7]聚类过程进行指导,在聚类过程中通过修改目标函数使其满足 据(这对于残缺数据来说是很重要的),相对于非监督聚类而
[1-2][3]限制条件,或者基于标签数据来对聚类算法进行初始化。 言,半监督聚类算法具有更好聚类结果和更快的速度。
作者简介:刘应东(),男,讲师,主要研究方向:数据挖掘、模式识别研究。 1971-
收稿日期:修回日期:2008-10-30 2009-01-14
刘应东:有约束的半监督聚类方法 2009,45:22: 101
基于约束的半监督聚类算法1 ),,)。j1?ij?k
这里要提出一个基于约束的半监督聚类算法,为了叙述的 ()计算影响因子矩阵 ((,),,)。7αα=αij1?ij?k 方便,首先给出几个相关定义。 ()如果 (,),转到(),否则,令7.1centerdisij?2Crad[max]7.2
(,)并转到步骤()。αij=0 8 定义 类的半径。对于一个类 来说,其半径为 中的 1 CCi i ()计算 中的数据对象 和 的距离,如果 (, 数据对象到其中心的最大距离,即:(,),其中 7.2CxydisyCrad[i]=max disxyj j i iji 表示 的半径,(,)表示 中的任一数据对象 与 Crad[i]CdisxyCx),令 (的初值为 ),继 i ji i j x?Crad[max]counter=countercounter+1 0j 续计算 中的下一个数据对象和 的距离,然后确定是否对 Cy的中心 之间的距离。j i Cy i i 进行更新,直到 中的数据对象都被计算过并且只被 counterCj 定义 类间的影响因子。给定两个类 和 ,它们之间的 2 CCi j计算一次。 影响因子 (,)定义为:αij
()(,)。7.3αij=counter/|C| i(,)numbij (,)αij= ()找出影响因子矩阵 中的最大值 (,),如果 (,)|C| 8α αijαij? i
其中 (,)(,)并且 (,),那么把 合并到 中,在合并的numbij=|x|disxy ,,(,)是 αdisCC?dis_minCC i?Crad [max]x?C|disxyx min ij i j j i 过程中,如果发现合并后的类中包含具有不同标签的标签数 和 的中心 之间的距离,是所有类的半径中的最CyCrad[max] i j
大值。表示合并后的新类,否则令据,那么取消合并。如果 ,令 [7] i
定义 类间的距离。给定两个类 和 ,它们之间的距3 CC 表示合并后的新类。更新新类的半径、中心 和类的最大i jCy j i 半径(如果需要)。如果 (,)或者 (,)Crad[max] αij<αdiscc> min ij 离是类 中的所有数据对象 到 的中心,的距离的最小Cx Cy j i i 值,即: ,那么转到()。dis_min10
()使用步骤()更新影响因子矩阵 ,并更新 ,转 97αdis_min(,)(,) disCC=min disyx基于约束的半监督聚类算法首ij i到()。8 先利用标签数据的标签信
()更新所有的聚类中心,重新把 分配到距其最近的 10Du 息把标签数据集中相同标签的数据作为一类。然后计算这些同 中心中去。 类数据对象的相似性标准和类间数据对象的不相似性标准。由 ()输出所有的类。11 于标签数据的数量相对于无标签数据来说很小,这将会导致下 算法 利用标签数据集 初步确定数据对象间的相似性 1 Dl 面的两种情况的发生,一是无标签数据集中类的数目大于标签 阈值 和类间不相似性阈值 ,如果数据集 中的数据 ε dis_minDu 数据的标签的数目;二是数据对象的相似性标准比其实际值要 对象与现有的所有类中心间距离的最小值大于 ,它就被认为 ε小,直接利用这个标准对无标签数据集进行聚类,导致聚类结 是与现有的所有的类都不相似,这时就增加一个类,并把该数 果中类的数目比其实际值大,必须要对某些类进行合并,在这 据对象作为这个新类的中心,重复这样的过程,直到 中的所D u 里使用标签数据、类间的影响因子和不相似性标准来决定是否 有数据对象都被处理完毕,这就是算法 的前 步的目的。由1 3 要对类进行合并,这是本算法的核心部分。利用这些标准对聚 于使用 来确定 的值,可能导致 的值过小,在第 步重新 Dε ε 4 l 类过程进行约束、指导和学习,并自动调整这些标准的值。为了 分配时,将产生较多的类,同时有可能导致 中的标签相同的 Dl 能够得到一个较快的算法,通过两个定理对聚类过程中的两个 数据对象被分配到了不同的类中,这时就将这些包含相同标签
数据对象的类合并为一个类,这是步骤()的目的。关键计算步骤进行加速。下面给出算法描述并对其进行说明。 5
第 步和第 步是算法 的核心部分。第 步用来计算类 7 8 1 7 算法 基于约束的半监督聚类算法1
间的影响因子,这是决定类是否合并的一个重要条件。但是影 输入:具有 个标签的标签数据集 、包含 个无标签数 h DN l响因子的计算是一个很耗时的工作。假设共有 个类,每个类 k 据对象的数据集 和类间的影响因子阈值 。Dα u min需要计算()个影响因子,但对于某一个类 来说,这() k-1Ck-1i 输出:所有的类。算法描述: 个影响因子最多只能用到一个(即当其中的一个是影响因子矩 ()利用数据对象的标签把 分成 个类,记为 (1Dh C1? l i 阵中的最小值时,才能被用到)。所以算法 的第 步在计算影 1 7 )。i?h 响因子矩阵时 ,并不是计算所有的影响因子,只有满足一定 α()计算类 ()的中心 、半径 和类间距离 2C1?i?hyCrad[i]i i的条件时才计算某两个类的类间的影响因子。这样的计算方法 的最小值 (类间的不相似性标准),令 ,把 dis_minε=max Crad[i]ε 能够提高算法 的速度,主要是由下面的定理 保证的。1 1 1?i?h 和 作为约束,对聚类过程进行约束。dis_min 定理 如果两个类中心间的距离是这两个类半径中大的 1 ()令 ,对数据集 中的数据对象 (从 到 ),找 3k=hDxi 1 Nu i [7]那个半径的 倍,那么这两个类的类间影响因子为 。2 0 出到 最近的类中心 :(,)(,),如果 (,xydisxy= min disxydisx i mimij i1?j?k 算法 的第 步是利用影响因子、标签数据信息和类间的 1 8 ),令 ,,否则,令 。y>εk=k+1y=xi=i+1 mki不相似性阈值确定是否对类进行合并,这是决定算法 最后结 1 ()把数据集 和 中的数据分配到距其最近的类中 4DDl u 果的关键步骤。在对类进行合并后,要对类间的不相似性标准 去,用 ()来表示这些类。C1?i?k i 进行更新,但是需要计算这个新类与其他所有类的不 dis_min ()如果 和 ()中的标签数据的标签相同,则合并 5CCi?ji j 相似性后才能得到 ,这是一个比较耗时的计算,为了提dis_min 这两个类。如果 ,令 表示合并后的新类,否则令 表示合i
表 中可以看出当 的值太小时,算法具有较长的运行时间,,那么 (,),这里 ,分别为类 和 dis_mindisCCdis_minyyCC2 ε ?ij ij i j
的中心,(,)为 和 之间的距离,(,)为类 和 disyyyydisCCCCij i j ij i j 但是在算法运行前又没有办法衡量 的取值到底是大是小。从 ε 之间的不相似性 。而可以看出利用标签数据对聚类算法进行约束、指导,在算法
证明 在类 中至少存在一个数据对象 满足下面的三 Cx j 的结果和速度上都有较大的提高。 角不等式 类间的影响因子是一个衡量类间相似性的较好的度量方
(,)(,)(,)(,)法,但是在进行类的合并时,同样需要给出其阈值,表 给出了 disCC=disyx?disyy-disxy? 3 ij iij j
(,)文献()中算法为了能够得到正确的结果时影响因子的取值范 disyy-Crad[j ]1 [7]ij
因为 围与相似性阈值 的关系。ε
(,)() disyyCrad[j]dis_min 2-?ij 表 影响因子的取值范围与 的关系3 ε 所以相似阈值 ε 合并前类的数目 影响因子的取值范围 合并后类的数目 (,)(,)(,)() disCC=disyx?disyy-Crad[j]?dis_min 3ij iij 0.13 12 0.5~1.180 11 即定理得证。 0.12 15 0.5~0.815 11 0.10 17 0.5~0.815 11 实验结果2 0.09 22 0.5~0.815 11 为了验证算法 具有较好的结果和较快的速度,使用标准 1 从表 中可以看出,当影响因子阈值 小于 时,文献 2 α0.5 min 数据集高斯数据集进行测试,并和文献中的算法进行比较。 [7]中的算法将不能给出正确的聚类结果。而算法 在进行类合 [7]1 高斯数据集是一个包含了 个类、个数据对象的标准数 11 2 000
并时并不是只利用 来确定是否对某两个类进行合并,而是 α据集。从高斯数据集中通过随机选取数据并对其进行标记,使 min
使用的时三个条件,这扩大了 的取值范围,表 就是在 其作为标签数据集,然后运行算法 并与文献中的算法进行 α1 1 [7]min
比较。文献中的算法是一个聚类结果较好、速度较快的一个 时的聚类结果。从而说明算法 具有较好的性能。[7]α=0.3 1 min
聚类算法。
这里从高斯数据集中按照一定的比例随机选取 个子集, 4 结论3
对每个子集中的数据打上标签,然后将其放回到高斯数据集中 提出的基于约束的半监督聚类算法利用标签数据产生数 作为算法 的测试集,这 个数据集中有两个数据集中标签数 1 4 据对象的相似性阈值和类间的不相似性阈值,利用这两个阈值 据的标签数目少于其实际数目。令 ,运行算法 ,表 α=0.311min对聚类过程进行约束指导,并在聚类过程中根据数据对象和类 给出了其中一次的运行结果。 的特性进行阈值的自动调整。通过对标签数据的学习,使得类
间影响因子阈值的选择范围大大增加,是对参数的选择更自 表 算法 在高斯数据集子集上的运行结果1 1
由,在高斯数据集上的测试表明该算法具有较快的速度和更好
的结果。由于使用数据与类中心的距离来作为类内和类间数据 标签数据所 标签 相似阈 合并前类 合并后类 运行时间数据集 /s 对象的相似性的一个重要指标,这对球形聚类具有很好的效 值 占比例()ε / % 数目 的数目 的数目 果,对于非球形聚类未必合适,这是以后研究的研究内容和要 1.013 7 数据集数据集1 10 11 0.085 6 18 11 数据集数5 11 0.083 0 22 11 1.326 5 2 3 解决的问题。 据集 1.514 3 4 10 5 8 0.082 0 24 11 11 1.281 6 8 0.080 9 25 参考文献: 从表 中可以看出,无论标签数据的标签数目等于其实际 ,,1 [1] Demiriz ABennett K PEmbrechts M J.Semi-supervised clustering
using genetic algorithms[C]//Artificial Neural Networksin Engineer, 值还是小于其实际值,最后算法 都能给出正确的结果,这说 1
,,:ingANNIE-991999809-814. 明算法 不但能够利用标签数据的信息,还不受标签数据的约 1 ,,,[2] Wagstaff KCardie CRogers Set al.Constrained K-means cluster, 束(即使标签数据的标签数目小于其实际值也能不受限制而得 ,ing with background knowledge[C]//Brodley C EDanyluk A P.Proc 到类的实际数目)。从标签数据集中得到的相似行阈值 的值 ε ’,’of the 18th Intl Conf on Machine LearningICML01.Willam, 差别不大,文献中需事先给出 的一个值,实际上这也是一 [7]ε :,:stownMorgan Kaufmann Publishers2001577-584. 个较难的问题,有时为了能够保证算法的有效性,不得不给出 ,,[3] Basu SBanerjee AMooney R.Semi-supervised clustering by seed, 一个较小的值,这大大降低了算法的速度。表 给出了文献2 [7] ,,,:ing[C]//ICML-2002SydneyAustraliaJuly 200219-26. 中的算法对于 的不同的值的执行结果。ε ,[4] Bilenko MMooney R J.Adaptive duplicate detection using learn,
表 类的数目与 的关系’,:2 ε ablestring similaritymeasures[C]//SIGKDD03200339-48.
,,[5] Klein DKamvar S DManning C.From instance -level constraints 相似阈值 ε 运行时间合并前类的数目 合并后类的数目 /s :to space-level constraintsMaking the most of prior knowledge in 11.485 0.05 61 11 ’,:data clustering[C]//ICML022002307-314. 0.10 18 11 1.367 ,,,,Xing E PNg A YJordan M Iet al.Distance metric learningwith [6] 0.15 11 11 0.156 application to clustering with side - information [ C]// Advances in 0.20 10 10 0.172 :,:Neural Information Processing Systems 15. [S.l.]MIT Press2003 从表 中可以看出,当 的值超过了 后,就不能得到2 ε 0.20 505-512. 一种基于影响因子的快速 均值算法计 冷明伟,陈晓云,颜清正确的聚类结果。如果不利用标签数据提供的信息,而是直接[7] .K-[J].
算机应用,,():200727123042-3044. 给出 的值,为了保证算法不得不给其一个较小的值,但是从ε
范文二:有标记的文本聚类方法研究
总第 178 期 舰 船 电 子 工 程Vol . 29 No . 4 2009 年第 4 期 Ship Elect ro nic Engineering 104
3
有标记的文本聚类方法研究
吴铁洲 孙 杨 夏防震
() 湖北工业大学电气与电子工程学院 武汉 430068
摘 要 聚类分析是一种模式识别无监督的分类方法 。对于根据类别先验知识已经分类的文本 ,提出一种有标记的文本聚类分类方法 。这种方法是在模糊聚类算法基础上进行了改进 ,通过有标记的文本样本 ,利用模糊聚类算法提取分类规 则 ,然后用模糊推理方法进行分类的一种算法 。文中讨论了此算法的具体数学模型 ,给出了算法流程 。并通过实验验证了 这种聚类方法是一种有效的文本分类手段 。
关键词 聚类 ;模糊聚类算法 ;文本分类 ;有标记的文本
中图分类号 T P391 . 4
A Met hod of Cl us t e ri ng wi t h M a r ke d Te xt
W u Tie z h ou S u n Ya ng Xi a Fa n gz h e n
( )School of Elect ro nical & Elect ro nic Engin. , H ubei U niv. of Technolo gy , Wuhan 430068
A b s t r a c t Cl ustering i s a kind of pat ter n reco gnitio n a nd unsupervi sed cla ssificatio n. Ba sed o n t he t ype of a p rio ri kno wledge of t he cla ssified ver sio n , t hi s p aper describe s a met ho d wit h t he cl ustering in text catego rizatio n. Thi s p aper de2 scribe s a met ho d wit h t he cl usteri ng in text catego rizatio n , w hich o btains t he r ule of ma r ked text by f uzzy cl ustering algo2 rit hm and catego r y by f uzzy rea so ning met ho ds. The paper di scusse s t hi s specific mat hematical mo del of t he algo rit hm , a nd give s t he al go rit hm p rocess. Finally , an implementatio n of t hi s algo rit hm i s given , a nd t he test o n t he data set p ro ve s t he va2 lidit y of t he algo rit hm.
Ke y w o r ds cl ustering , f uzzy cl ust ering algo rit hm , t ext catego rizatio n , ma r ked text
Cl a s s N u m b e r T P391 . 4
是具有类别先验知识的 。在利用聚类分析的划分 1 引言结果时 ,由于聚类结果与先验知识并不一致 ,故要
随着互联网应用的普及 ,网络信息膨胀迅速 , 对原有聚类算法进行改进 ,使之能处理有类别标记 使得信息处理的意义变得更加重要 ,文本自动分类 的文本 。本文在模糊聚类算法基础上进行改进 ,提 已成为信息处理领域一项重要的研究课题 。目前 , 出了一种基于标记文本的聚类方法。
[ 1 ] 近邻、 已经出现了多种文本分类方法 , 如 : K -2 模糊聚类算法[ 2 ] [ 3 ] Baye s、支持向量机等 。 [ 8 ] ( ) 聚类分析是发现数据信息中存在的各种关系模糊聚类算法 FCM是一种基于目标函数 和规则 ,对信息进行正确分类 ,并进行快速信息检 的聚类方法 ,它把聚类归结成一个带约束的非线性 索的有效途径 ,是近年来研究的热点问题之一 。当 规划问题 ,通过优化求解获得数据集的模糊划分和
[ 4,7 ] 前有多种聚类算法,这些算法广泛地应用在各 聚类 。其基本思想是通过反复修改聚类中心 V 和 领域。聚类是一种无监督分类方法 , 而处理的文本 分类矩阵 U 来实现动态的迭代聚类 , 使得被划分
3 收稿日期 :2008 年 11 月 17 日 ,修回日期 :2008 年 12 月 24 日
作者简介 :吴铁洲 ,男 ,副教授 ,硕士生导师 ,研究方向 :计算机应用 ,语义网格 。孙杨 ,女 ,硕士研究生 ,研究方向 :计算
机网络 。
相似度最小。本 d 的模糊特征向量 , 每个文本有 s 个特征项 , x i ijn ( 给定观察空间中的一个有限样本集 x ?R kk 为第 i 个文本中的第 j 个特征项的权重 , 则中文文
本的模糊特征向量空间模型为 : ) = 1 , 2 , , n, 则 FCM 的目标函数的形式如下 :
n c D n 1 , d2 ,m 2= { d , d } (μ) ) ( ) ( ))dJ U , P m = ik ik m ?[ 1 , ? ??k = 1 i = 1 ( ) d) i = 1 , 2 , , n ( = x i1 , x i2 ,, x im i ?M f c st . U x ij 1 , 2 , )( , n ; j = ?[ 0 , 1 ] ,i = 1 , 2 , , s
m ( )1 2 X = 1 , i = 1 , 2 , )ij( , n ) ?其中 c 是类别数 , x k 为第 k 个样本 , m ?[ 1 , ?是j = 1
μ 一个加权指数。?[ 0 , 1 ] 是 x 属于类 i 的隶属ik k ( ) 用 pik i = 1 , 2 ,1 , 2 , = , n表示第 k, q; k
度 , 且 个训练样本隶属于第 i 个类的指示函数 :c 1 x ?类 ik μ( )= 1 , Π k ?{ 1 ,ik2 , k} ?( )6 P=ik i = 1 x | 类 ? 0 k( )b 对于 Π i , k , 如果 ? d> 0 , 则有隶属度迭代公 ik 3 . 2 文本特征提取[ 9 ] 式 :文本特征的提取 , 有多种方法。论文采用 K - 1 2( ) b [ 10 ] c m - 1 ( ) - L Ka r h une n - Loeve变换 。该变换是一种常( )d b ik μ ( )3 = ( )b ik ?用的正交变换 , 可以在最小均方差意义下获得数据 j = 1 d jk特征的最优压缩 , 且不受分类模式的限制 。在用于 ( )b 特征选择时 , 相当于一种线性变换 , 使随机矢量在 如果 ? i , r , 使得 d= 0 , 则有 ir ( )( )b b μ( )μ4 = 1 , 且对于 j ?r ,= 0 ir ij Φ 一组正交函数集 上展开 , 用展开式的部分系数表 其中 d是第 k 个样本与第 i 个聚类中心的 Eucli dik 征矢量 X 。本文采用的展开式的系数为模式总体 2 T ( ) ( ) ( ) 距离 , 可由式 d= x - pA x -p计算。ik k i k i 协方差矩阵 , 其随机矢量 x ?X 散布矩阵的定义
聚类中心的迭代公式 :为 :
n ( )b+1 T (μ( ) ( ) ω) ?x S i = E{ x - m0 x - m0 } , x ?Πi , i = 1 , 2 , kik ? ( )b+1 k = 1 ( )p= 5 n i, s ( )b+1 (μ)ik 其中 m ?ω 为 x 的均值矢量 ,表示第 i 个类 , s 为类0 i k = 1
FCM 算法步骤如下 :别数 。
3 . 3 文本分类算法 ( ) , k 是样步骤 1 : 给定聚类类别数 C 2 Φ c Φ k
经过模糊聚类算法 , 从训练样本中得到的是 cε 本个数 , 设定迭代停止阈值, 设置算法迭代计数器
个轴线平行于特征轴的超椭球类超长方体 , 即找到 b = 0 ; 了可以覆盖模式样本集的 c 个超椭球体。为了便 步骤 2 : 用值在[ 0 , 1 ] 间的随机数初始化隶属 于提取 IF - T H EN 规则 , 将其改为平行于特征轴 ( ) 矩阵 U , 使其满足式 2中的约束条件; 的超长方体来覆盖每个聚类 。超长方体可用一个 ( ) b( ) ( ) μ步骤 3 :用式 3和 4更新划分矩阵;( ) b+1( ) 步骤 4 :用式 5更新原型模式矩阵 p ;(α β) α (α α α ) , 二元组 B = i , i 表示 , 其中 : i = i1 , i2 ,isi ( )b( ) 步骤 5 :根据式 1计算目标函数 , 如果‖p β) β(ββ ,是每条是超长方体的中心坐标 ,= ,,is i i1 i2 ( )b+1 p ε - ‖ > , 则令 b = b + 1 , 转步骤 3 , 否则算法边的半长度。可用下式求得 :
停止 , 输出隶属度矩阵和聚类中心。n n 1 α( μμ) ik = ma x {ij x jk } + mi n {ij x jk } , k = 1 , 2 ,j = 1 j = 1 2 3 有标记样本的聚类算法 ( )7 , s ( 文本聚类主要包括文本的表示 即文本数据的 n n 1 β( μ ik = ma x {ij x jk } -μ) mi n {x } , k = 1 , 2 ,ij jk ) 数学表示、文本特征提取、文本划分方法三个方面 j = 1 j = 1 2 的问题 , 下面讨论具体的数学表示和模型。 )( 8 , s 3 . 1 文本的表示 对于给定的训练样本集 D , 特征空间的模糊划
分可以看作是寻找一组包容或覆盖来自各类样本 设给定的训练样本集 D = { d,d, , d} , 样1 2 n
106 吴铁洲等 :有标记的文本聚类方法研究总第 178 期
的合适的超长方体的过程。就每一个类别来说 , 寻T H EN 规则。
找超长方体的过程是独立的 , 以便于用序列的方法
4 实验验证来操作划分过程。
i 目前 ,在中文文本分类中还没有一个标准的、( 假定类 i 的训练样本可用 c 个超长方体 B i i k
) 普遍可接受的训练集和测试集 。论文下载了《人民= 1 , 2 , , q ; k = 1 , 2 , , c所包容 , 但是超长方体i
日报》网站的有关经济、政治和娱乐的网页 1722 的具体数目未知 , 本文给超长方体包容样本的比率
i ) ( 个 ,作为实验数据。所有网页下载时网站已经分好 ( i = 1 , 2 , , q; k = 1 , 设定一个阈值T , 用 R B k R
类 ,将其中 1446 个已经标号的网页用于训练 ,其余 ) 2 , , c来表示超长方体包容样本的比率 , 其计算i
276 个用于测试。针对这些数据 , 做了两个实验。 式如下 :
测试中 ,经过 K - L 变换 ,取得特征属性 35 个。并p ij ?i x ?B 且设定阈值 T R = 0 . 9 。测试环境为 P IV2 . 0 G、i j k( )R B ( )= 9 k p + p ijrj V C7 . 0 。具体的实验结果如下表所示 : ???i i r ?ix ?B x ?B j kj j 表 1模糊聚类的聚类结果i ( 当类 i 的所有 c 个超长方体中的 R B ) 都满i k 样本数 政治经济娱乐i ( ) 足 R B Ε T R 时 , 划分终止。否则 , 增加一个超长 k 识别数 537 486 423 方体继续划分。 经济496 31 15 3 . 4 分类算法的优化 政治 [ 11 ] 36 449 7 聚类算法本身是一个爬山法, 很容易陷入 娱乐 5 6 401 局部极值点。因此该算法将会产生一些冗余的超
长方体 , 导致 IF - T H EN 的规则增多 , 需要对产生 表 2有标记的样本聚类结果
的超长方体进行处理 , 获得精练的规则集 , 本系统 测试数 政治经济娱乐 采用的是同一类超长方体的合并。对于类 i 的 c i 识别数 101 95 80
识别数i i 96 4 97 6 83 5 , 个超长方体 B k , 从超长方体集合{ B j , j = 1 , 2 ,/ 误分数 识i i ( ) c} 中任取 2 个 , 分别为 B , B 1 Φ j , k Φc, 利用下i k j i 91 . 08 95 . 78 97 . 50 别百分比
面的策略进行合并 : 说明 :识别百分比 = 正确识别数/ 测试数i i ( ) 经过测试 ,从表 1 和表 2 中可以发现 : 两种聚 R B ?B Ε T R k j i f t he n m e r g i n g
类方法对文本分类都有较高的识别率。因为政治 ( )else not m e r g i n g 10
与经济两类别有较大的相似性 ,在聚类过程中 ,模 得到类 i 的所有超长方体后 , 对应于每个超长糊聚类方法产生了较大的误差。有标记的文本聚 方体就产生了一条模糊 IF - T H EN 规则 , 表示该 类方法较好地解决了这个问题 ,识别率得到较大的 超长方体代表该类别的可信度 。形式如下 : 提高 。而对于娱乐类别来说 ,两种方法得到的结果
)c , ( B ?类 i k = 1 , 2 ,k 比较相近。分析表 2 知 :有标记的文本聚类方法对 k( 文本的分类达到了 94 . 78 %的正确率 三类平均 ?b, s , x x ?B , i . e. , f o rj j = 1 , 2 j i f k
) 值,是一个有效的分类方法 。 i t he n x ?类 i 的可信度 C F = C Fk
根据上面的实验结果得出 ,有标记文本聚类方 结合 FCM 算法和对有预先标记网页的分类策
法能提高相似度较高的不同类别的识别度 ,并且分 略 , 改进后的算法为 :
() 步骤 1 :给定已知类别数 C2 Φc Φ k, 样本个数 类准确率较好。这充分说明了有标记文本聚类方
k ,设定比率阈值 T= 0. 9 ,设置算法迭代计数器 b = 0 ; R 法在文本分类中实际意义。步骤 2 :用 FCM 算法输出每类 i 的 c 个超椭球
体;
( ) ( ) 步骤 3 :用式 8和 9转换超椭球体为适合抽 5 结语取规则的超长方体;
本文研究了基于模糊聚类算法分类网页的方
法 ,通过实验取得了令人满意的结果。在论文中 , i ( ) 步骤 4 :如果 R B Ε T 成立 ; 停止算法 , 输出k R 验证时所处理的网页是一个较少的类别 ,如果要处 超长方体 。否则转步骤 2 ;()下转第 132 页 ( ) 步骤 5 :根据式 10优化超长方体 , 提取 IF -
进行比较 。,一旦传输业务阻断 ,将造现在传输容量越来越大
()) 1业务容量 仅考虑主用业务 成巨大的经济损失和负面的社会影响。SD H 的各
单向通道保护环的最大业务容量是 S TM -种自愈环所表现出来的性价比不同 ,在进行网络结
N ,双纤双向复用段保护环的业务容量为 M/ 2 ×构优化时 ,一般依照需要在各个层次分别组环 ,然
) ( S TM - N M 是环上节点数。 后实现它们的互连互通 ; 通过网络结构的优化 ,从
) 2复杂性 二纤单向通道保护环无论从控制而提高 SD H 传输网络的安全性 、可靠性。自愈环
协议的复杂 的互连互通必将在 SD H 传输网络的实际组网应用 性 ,还是操作的复杂性来说 ,都是各种倒换环中最 中起到越来越重要的作用。
简单的 ,由于不涉及 A PS 的协议处理过程 ,因而业
务倒换时间也最短 。二纤双向复用段保护环的控
制逻辑则是各种倒换环中最复杂的。 参 考 文 献
) 3兼容性 二纤单向通道保护环仅使用已经
完全规定好
了的通道 A IS 信号来决定是否需要倒换 , 与现行 [ 1 ] 吴彦文 ,郑大力 ,仲肇伟. 光网络的生存性技术[ M ] . 北
京 :北京邮电大学出版社 ,2003 SD H 标准完全相容 , 因而也容易满足多厂家产品 [ 2 ] YD/ T ,1078 - 2000 . SD H 传输网技术要求 —网络保护 兼容性要求。 结构间的互通[ S ] . 2001
二纤双向复用段保护环使用 A PS 协议决定倒 [ 3 ] 华为传输产品日常维护与故障分析[ Z ] . 华为技术有限
公司 换 ,而 A PS 协议尚未标准化 ,所以复用段倒换环目
[ 5 ] [ 4 ] 肖萍萍. SD H 原理与技术[ M ] . 人民邮电出版社 ,2008 , 前都不能满足多厂家产品兼容性的要求。
10
( ) [ 5 ] 吴铭峰 ,高淑芬 ,刘培莹. 子网连接保护 SN CP在传输 5 结语() 网中应用分析[J ] . 天津通信技术 ,2003 , 3:33,36
SD H 传输网络是运营商的基础网络 ,网络的
() 上接第 106 页
[ 4 ] 李飞 ,薛彬 ,黄亚楼. 初始中心优化的 K2Mea ns 聚类算 理多类别的分类 ,特征属性的选取及数量的大小对 () 法[J ] . 计算机科学 ,2002 ,29 7:94,96 聚类效果都存在很大影响 ,因此也是值得继续深入 [ 5 ] 周水庚 ,周傲英 ,曹晶. 基于数据分区的 DB SCA N 算法 研究的方向。() [J ] . 计算机研究与发展 ,2000 ,37 10:1153,1159 [ 6 ] 黄永光 ,刘挺 ,车万翔 ,等. 面向变异短文本的快速聚类 参 考 文 献
() 算法[J ] . 中文信息学报 , 2007 , 21 2: 63,68 [ 1 ] W L A M , C Y Ho . U sing a generalized i nsta nce set fo r [ 7 ] 谷波 ,李济洪 ,刘开瑛. 基于 CO SA 算法的中文文本聚
() 类[J ] . 中文信息学报 , 2007 , 21 6: 65,70 2 rizatio n [ C ] . The 21t h A nn Int a uto matic text catego
[ 8 ] 钮永莉 ,陈水利. 模糊 C 均值算法的改进[J ] . 模糊系统 A CM SI GIR Co nf erence o n Re sea rch a nd Develop ment () 与数学 , 2004 , 18 9: 304,308 ( ) in Info r matio n Ret rieval SI GIR’98, 1998 : 81,89
[ 9 ] 庞景安. Web 文本特征提取方法的研究与发展[ J ] . 信 [ 2 ] A MCCALL U M , K N I GA M . A co mpa ri so n of event () 息系统 ,2006 ,29 3:338,340 mo del s fo r naive bayes text cla2ssificatio n [ C ] . A AA I2 [ 10 ] 余秋星 ,李志舜. 基于状态空间重构与 K2L 变换的特 98 Wo r k shop o n L ea r ning fo r t ext catego rizatio n ,1998 () 殊提取[J ] . 西北工业大学学报 ,2003 ,21 2:5,7 [ 3 ] T HO RS T EN J OCA C H IM S. Text Cat ego rizatio n wit h [ 11 ] 张维 ,潘福铮. 一种基于遗传算法的模糊聚类 [ J ] . 湖 Suppo rt Vecto r Machine :L ea r ning wit h Many Releva nt () 北大学学报 , 2004 ,24 2:101,104 Feat ure s [ C ] . Europea n Co nf erence o n Machine L ea r n2
( ) ing ECML ’97, 1997 : 170,179
范文三:基于PCA和K_均值聚类的有监督分裂层次聚类方法
3
基于 PCA和 K2均值聚类的有监督分裂层次聚类方法
1 , 2 1 1 1 1浦路平 , 赵鹏大 , 胡光道 , 张振飞 , 夏庆霖
( ) 1. 中国地质大学 遥感地质与数学地质所 , 武汉 430074; 2. 桂林工学院 现代教育中心 , 广西 桂林 541004摘 要 : 提出了一种新的基于 PCA 和 K2均值聚类的有监督二叉分裂层次聚类方法 PCA SHC,用 K2均值聚类进 行逐次二叉聚簇分裂 ,选择 PCA 第一主成分相距最远样本点作为 K2均值聚类初始聚簇中心 ,解决了 K2均值聚类 初始中心随机选择导致结果不确定的问题 ,用聚簇样本类别方差作为聚簇样本不纯度控制聚簇分裂水平 ,避免 过拟合 ,可学习到合适的聚类数目 。用四组 UC I标准数据集对其进行了 10 折交叉验证分类误差检验 ,与另外七 种分类器相比说明 PCA SHC有较高的分类精度 。
关键词 : 数据挖掘 ; 机器学习 ; 有监督聚类 ; 分裂层次聚类
( ) 中图分类号 : TP301 文献标志码 : A 文章编号 : 100123695 2008 0521412203
PCA and K2m ean s ba sed sup e rvised sp lit h ie ra rchy c lu ste ri ng m e thod
1, 2 1 1 1 1PU L u2p i ng, ZHAO Peng2da, HU Guang2dao, ZHAN G Zhen2fe i, X IA Q i ng2li n ( 1. R esea rch Institu te of M a them a tica l Geology, C h ina U n iversity of Geosciences, W uhan 430074, Ch ina; 2. M odern Educa tion Techn ica l
)C en ter, Gu ilin U n iversity of Technology, Gu ilin Guangx i 541004, C h ina
( A b stra c t: The p ap e r p re sen ted a new sup e rvised b in2sp lit h ie ra rchy c lu ste ring m e thod, PCA SHC PCA sp lit sup e rvised h ie r2
) a rchy c lu ste ring. The m e thod b in2sp lited c lu ste r by K2m ean s c lu ste ring w ith in itia l cen te rs unde rtaken by the samp le s of m axim um and m in im um of first p rinc ip a l componen t of p rinc ip a l componen t ana lysis of the c lu ste r, wh ich so lve the p rob lem of unce rta in re su lt a s a re su lt of the unce rta in cho ice of in itia l cen te rs. In the m e thod, the va riance of the c la sse s of the samp le s in c lu ste r wa s cho se a s m ea su re of imp u rity of c lu ste r samp le s c la ss, wh ich con tro ls the slip leve l of c lu ste r, avo id ove r2fitting and can find ou t the p rop e r num be r of c lu ste rs. The m e thod te sted w ith 10 2fo ld c ro ss va lida tion fo r c la ssifying of 4 UC I da ta2 se ts. It p rove s the m e thod ha s exce llen t c la ssifying accu racy ra te comp a ring of the e rro r ra te of it to o the r 7 rep re sen ta tive c la s2 sifie rs fo r c la ssifying of sam e da ta se ts w ith sam e te st way.
Key word s: da ta m in ing; m ach ine lea rn ing; sup e rvised c lu ste ring; sp lit h ie ra rchy c lu ste ring
而数量尽可能少的聚簇聚类方案 。现有多种形式 ,如学习向量 引言[ 2, 3 ] [ 4, 5 ] 量化网络 、基于划分和增量的动态聚类方法 、支持向量
[ 5 ] 机 等 。学习向量量化网络在竞争学习网络中按分类结果对 ,可以提供样聚类分析依照物以类聚原理将研究对象分组 错进行奖惩来调整权值学习 。基于划分和增量的动态聚类方 本分布的结构信息 ,是一种重要数据挖掘方法 ,在自然科学和 法常用聚簇内类别不纯度惩罚指标最小化方法 。支持向量机 社会科学中得到广泛应用 。经典聚类方法是无监督学习方法 , 结合样本类别的约束信息 ,通过核函数非线性映射到高维希尔 要预先指定聚簇数目 ,如果聚簇数目不正确 ,无法得到正确聚伯特空间 ,使其在新的空间中同类样本相聚一起 ,异类样本分
类结果 。因此正确的聚簇数目是很重要的聚类参数和样本结 离加大 ,可以用超平面划分 ,实现有监督聚类 。这些方法在要
求指定聚簇数目 、学习及分类效率和提供显式的子类分布结构 构信息 ,从样本特征数据中学习到合适的聚簇数目意义重大 。
信息上各有长短 。 K2均值聚类方法和层次聚类方法都需要提供正确的聚簇 ()K2均值聚类 又称 C2均值聚类 是一种普遍采用的基于划 数目 。前人曾用逐步增加聚簇数目的 K2均值聚类或层次聚类分的动态聚类方法 ,是在选定的相似性距离度量和评价聚类结 [ 1 ] 方法寻找正确的聚簇数目 ,但拐点不明显时无法使用 。 为果质量的准则函数基础上给定某个初始分类后 ,用迭代算法找 [ 1 ] 了通过数据挖掘从样本特征数据中学习到正确的聚簇 出使准则函数取极值的最好聚类结果 。其最佳初始划分尚 数目 ,可以利用带有类别标签的样本进行有监督聚类 。有监督 无解决良方 ,现多用随机方法 ,有较大不确定性 。 非监督的增 聚类因有样本类别标签分布信息的教师监督信号 ,极大地降低 量 逐 次 K2均 值 聚 类 法 有 时 可 以 学 习 聚 簇 数 了信息的不确定性 ,工作效率较高 ,分类结果为明确的真实类 目 。它是通过逐渐增加聚簇数目 K和进行 K2均值聚类法 ,直别 ,能反映出子类等样本分布结构 。 有监督聚类的目的是找
出划分样本为聚簇内样本纯度大
( ) (收稿日期 : 2007 202 230; 修回日期 : 2007 207 230 基金项目 : 国家自然科学基金资助项目 402721122 ; 广西教育厅资助项目 桂教科研
) [ 2004 ] 4 号
( ) ( 作者简介 :浦路平 1958 2,男 ,江苏南通人 ,博士 ,主要研究方向为矿产资源定量预测及勘察评价 、G IS应用和地学数据挖掘 p u lup ing@ sina. ) ( ) ( ) com ; 赵鹏大 1931 2,男 , 辽宁清原人 ,中国科学院院士 ,教授 ,博导 ,主要研究方向为矿产普查与勘探学和数学地质学 ; 胡光道 1945 2,男 ,北京
人 ,教授 ,博导 ,主要研究方向为矿产资源定量预测及勘察评价 、资源环境遥感研究 、地质资源信息系统软件研究 、G IS及计算机应用软件开发等 ; 张 ( ) ( ) 振飞 1961 2,男 ,教授 ,博士 ,主要研究方向为矿产勘察和矿床统计预测 ;夏庆霖 1968 2,男 ,副教授 ,博士 ,主要研究方向为矿产勘察和矿床统计
预测.
第 5 期〃1413〃 浦路平 ,等 :基于 PCA 和 K2均值聚类的有监督分裂层次聚类方法
T T T) (( ) ( ) () J = E VV = E U X - M X - M U = 到评价聚类结果质量的准则函数值对 K的变化率达到一个拐 D T T T 点时停止 , 此时的 K作为正确的聚 类数目 。如果没有 明显的 ) (CE U CU = 1 /D ?u uj j j = 1 拐点 ,则此法失效 。 T ( ) ( )( )式中协方差矩阵C = X - M X - M 3 [ 1, 6, 7 ] 层次聚类分析也是一种普遍采 用的主要聚类方法 , T 因为 U 是正交归一矩阵 ,所以其元素应满足 用指定的样本相似性距离度量和聚簇间相似性距离度量 ,用合 1 i = j T u = u( )并或分裂手段 ,把样本从每个样本自成一簇到所有样本全为一 4 i j 0 i?j 簇的多级层次聚簇树 ,但要靠人为指定聚簇数目等参数来将其( ) 用拉格朗日乘子法可以求出在满足式 4 正交条件约束 划分为若干子聚簇 。下 , 求 J 取最大极值的变换 U , 所有点到这条直线的垂直距离 2 ) ( 合并层次聚类算法计算复杂度较大 ,为固定的 O N , 只 ()的平方和最小 ,而在这条直线上的方差 投影分布区间 最大 。令 能用于中小样本学习 ; 分裂层次聚类法可用 K2均值聚类法等 D D T T T )( ) ( ) 5 ( λG U = ?u C u - ?u u - 1 ; j = 1, 2, , D j j j j j 基于划分的动态聚类方法进行分裂 ,计算复杂度随样本分布情j = 1 j = 1
() 况而变化 ,最好时与 K2均值聚类法相同 ,为 O N , 多数近于 O( )( )将式 5 对 uj = 1, 2, , D 求导数并令其等于 0: j 2 (() ) ( ) N logN , 极为罕见的极端分布最差时为 O N 。因为是 ( )( λ() ) 2 6 5G U / 5u = C - Iu = 0; j = 1, 2, , D j j j
在已有聚簇基础上进行继续分裂 , 所以比每次从头开始的增量 λλλ解此方程可得协方差矩阵 C 的特征值 ,, , 。其 1 2 D 逐次 K2均值聚类法计算量要小 。 λλλ中 :?? ?。 1 2 D 用有监督逐步增加聚簇数目的 K2均值聚类或层次聚类方 λλλλ , 若最后 k 个特征值 , ,,为 0, 则 其 D - k + 1 D 2k + 2 D - 1 D 法可以找到正确的聚簇数目 ,但合并层次聚类方法计算复杂度 相对应的特征向量和主成分也为 0: u= 0; v= 0; j = D - k + 1, j j 较大 。因 K2均值聚类初始化困难而多用随机初始化 , 带来了 D - k + 2, , D - 1, D。即变换矩阵 U 降维成 U ?D ×D , 式中 s s K2均值聚类结果不确定问题 。 余维数 D = D - k, 对应的主成分 V 降维成 V ?D ×N 。 s s s 为此本文提出了一种新的有监督聚类方法 ,即主成分有监λ对应的第一主成分 u在样主成分分析中最大特征值 1 1 ( 督 层 次 聚 类 方 法 PCA sup e rvised h ie ra rchy c lu ste ring, 本属性空间方差最大 ,延伸最长 ,变量载荷最大 ,拥有样本信息 ) PCA SHC。它用聚簇内样本不纯度作为停止分裂的准则函数 量最大 。根据这个特点 ,可用相距最远的聚簇样本第一主成分 进行逐次二叉层 次分裂 , 以 聚簇样本类别方差作为不 纯度测 最大值和最小值作为两个初始聚簇中心 ,进行两类 K2均值聚 度 ,聚簇分裂用两类 K2均值聚类方法 ,用 PCA 第一主成分进行类 。由于这是确定性过程 ,解决了 K2均值聚类方法分裂时其 确定性初始化的 K2均值聚类 ,消除了通常 K2均值聚类因随机 初始化聚簇难以确定和因初始值随机选取而产生的结果不确初始化引起的聚类结果不确定性 ,可学习到合适的聚簇数目 , 定问题 。学习效率较高 。用多组 UC I标准数据对其 进行了检验 , 其结 在样本属性向量空间中 ,每个样本为一点 。两个样本点之 果与其他七种分类器比较 ,证明此方法有较高的分类精度 。间距离表示其不相似的程度 ,相距越近越相似 。聚类是把相似
的样本划为一组 。但相似是相对的 ,所以聚类可以有不同层次原理和算法 级别 :从每个样本各自为一聚簇到所有样本全为一聚簇 ,如果
后者为拟合不足的话 ,前者则可能是拟合过度了 ,一般是介于这 1 原理
有监督聚类的目标是划分出类别不纯度最小的尽可能少 两者之间的某个划分 。如何判断是最佳拟合的聚簇划分呢 ? 带 的聚簇集合 。分裂层次有监督聚类是从所有样本为一类开始 类别样本的分布提供了从分类角度判断最佳聚簇划分的信息 。不断分裂聚簇成多个子聚簇 ,直到聚簇样本类别不纯度小于指 在不断分裂的层次聚类过程中可以通过类别不纯度及其 定阈值时停止 。用 K2均值聚类分裂层次有监督聚类是用 K2均 阈值来控制拟合程度 :当聚簇样本类别的不纯度小于阈值时 , 值聚类方法把聚簇分裂成两个或多个子聚簇 。K2均值聚类的 聚簇停止分裂 ;否则继续分裂成更小的子聚簇 。 主要问题是初始化困难和随机初始化带来的结果不确定性问
)( 聚簇样本类别方差 va r y可以表示聚簇样本的类别不纯题 ,这可用主成分分析方法解决 。
( ) 主成分分析 p rinc ip a l componen t ana lysis, PCA 是 一 种 把 度 ,因此将其作为测度聚簇类别不纯度的指标 。 设有样本属原来由多个变量表示的样本转换为可用较少的互不相关的新 ( ) ( ( ) 性向量及其类别集合 D = X , Y = x, y, 1 1 综合变量表示的统计方法 。新的综合变量由多个原有变量线 d ( ) ) ) ( x, y, , x, y, x? , y? { 1, 2, , c} , i = 1, 2, , 2 2 n n i i 性组合而成 ,称为主成分 ,可以通过计算特征值方法求得 。然 N 。 后在有用信息丢失最少的原则下保留特征值大的那部分主成 N - 1 分 ,舍弃那些仅含少量信息的主成分 ,从而达到降低维数的目 m = N ? y y i i = 1 的 。其公式推导如下 : N - 1 2 )( ( ) ( )7 var y= N ? y - m i y i = 1
1 有监督分裂二叉层次聚类算法 d , i = 1, 2, , N 。设有样本集合 X = { x, x,, x} , x? 1 2 n i 输入 :一组 n个 m 维 c类训练样本对象集合 D = X ×Y =
其均值向量 M 的分量为Nm ) ( }{ x , y 。其中 :样本的属性 x?R ; 样本的类别 y?{ 1, i i i i i = 1 N - 1 m = N ? x ( )1 j ij2, , c} , i = 1, 2, , N ; 聚簇样本的类别不纯度阈值 T?0。 i = 1 T 输出 :各样 本 对 象 所 属 的 聚 簇 号 集 合 Z = { z} , z? { 1,i i 如果用正交归一矩阵 U 定义一对线性变换 :T 2, , h } , i = 1, 2, , n。 ( ) V = U X - M
( )方法 : X = UV +M 2
) a聚簇 a ?{所有样本编号 } , 聚簇集合 A ?{ a } , 聚簇集合各样本向量到样本均值向量 M 的距离平方和的期望是
)) 1 和图 1 可见 ,在分类器对 Eco li、Gla ss、Iris和 W ine由表 b如果聚簇集合 A 为空结束 , 转向 e; 否则继续 。
)(c对聚簇集合 A 中每个聚簇 a依次作 : 四种 数 据 集 的 分 类 误 差 当 中 , PCA SHC 有 两 项 最 好 其 中 对 k
( )) a从 A 取出聚簇 a作为当前工作聚簇 B : B ?a, A ?A - Eco li数据集各种分类器误差都较大时 SHCC误差最小 ,两项 k k
{ a} 。 第二 ,说明 PCA SHC分类精度较高 。 k
( )( ) ( ( ) ) b用式 7 计算聚簇 B 的类别 方差 va r y B 。如 果 ( () ) va r y B < t,="" 则="" e="" b="" }="">
( ) c用 PCA K2均值聚类法分裂聚簇 B 。
( )( )( ) ?按式 3 和 6分别计算聚簇 B 中样本 x B 的均值向
量 M 和 PCA 变换矩阵 U;
?用第一主成分变换向量 u计算聚簇 B 内各样本第一主 1 T ( () ) 成分值 v= ux B - M ; 1 1
?寻找聚簇 B 内 第 一 主 成 分 值 的 最 小 值 和 最 大 值v、 m in
v对应的样本向量 x、x; m axm in m ax
?以 x、x为二聚簇初始中心 ,用 K2均值聚类把聚簇 B m in m ax
分为 B 和 B 两个聚簇 , A ?A ?{ B , B } 。 1 2 1 2
)) d转向 b;
)e为聚簇集合 E中各样本 z赋予所在聚簇编号 ,返回 Z。 i 结束语
实验 )理论和实验说明 : a基于 PCA 和 K2均值聚类的有监督二
叉分裂层次聚类方法是一种性能良好的有监督学习方法 ,可由 实验所用程序为 MA TLAB 615编程实现的算法 ,计算用的
)样本类别分布信息自动学习到聚簇数目 。 b用 PCA 第一主成 计算机 CPU 为 Pen tium 1173 GH z, 内 存 512 MB , 操 作 系 统 为
分相距最远的二极端值样本点作为初始聚簇中心来作二叉分 W indow s XP。
裂 K2均值聚类可得到确定性结果 ,避免了 K2均值聚类的初值1 标准数据集测试
)不确定性 。 c用聚簇样本类别方差作为聚簇样本不纯度控制 2 1111 数据集 聚簇分裂水平 ,使之达到最佳拟合 ,可自动学习到有监督聚类 实验测试数据选择了四个 UC I数据集 : Iris、Gla ss、W ine和的最优化聚簇划分 ,无须人为指定聚簇间距离阈值 、指定聚簇 [ 8 ] Eco li,所有属性均为连续数值型 ,其各参数如表 1下部所示 。 数目或划分最大树深度等划分聚簇的参数 。聚簇样本类别方表 1 七种分类器和 SHCC对这四组 UC I数据集作 10 折 交叉) 差阈值默认值为 0,此时聚类结果为类别纯净的同类聚簇 。 d()验证分类误差率 除 SHCC外的所有数据来源于文献 [ 9 ] PCA SHC与分类 器 组 合 成 的 有 监 督 层 次 聚 类 分 类 器 对 四 组 Eco li Gla ss Iris W ine 分类器 UC I标准数据的 10组交叉验证分类结果与七种其他代表性的 0. 134 0. 070 0. 040 0. 045 libSVM 2L inea r
分类器比较 ,具有较高的分类精度 。 0. 172 0. 687 0. 467 0. 117 libSVM 2Po ly
0. 152 0. 088 0. 047 0. 017 libSVM 2RB F N 参考文献 : 0. 140 0. 159 0. 053 0. 028 a?ve B aye s C4. [ 1 ] 边肇祺 , 张 学 工. 模 式 识 别 [ M ]. 2 版. 北 京 : 清 华 大 学 出 版 社 , 0. 193 0. 023 0. 047 0. 062 5 2000: 235 2237. B P 0. 143 0. 047 0. 027 0. 039 KOHON EN T. The self2lea rn ing m ap [ J ]. P ro c o f IE EE , 1990 , 7 8: [ 2 ] Pe rcep tron 0. 238 0. 389 0. 327 0. 140 1464 21480. 0. 128 0. 032 0. 023 0. 019 PCA SHC 样本[ 3 ] 程剑锋 ,徐俊艳. 基于 EM 算法的有监督 LVQ 神经网络及其应用集特征数 样本4 9 13 7 ( ) 集类数 样本集[ J ]. 系统工程与电子技术 , 2005 , 2 7 1 : 121 2123.3 6 3 8 样本数 [ 4 ] 宋彤 ,宋保强. 一种新的监督聚类学习方法及其在故障诊断中的 150 214 178 336
( ) 应用 [ J ]. 计算机工程与科学 , 2001 , 23 5 : 63 269. 2 1112 PCA SHC分类方法 [ 5 ] D ETTL IN G M , BUHLMANN P. Sup ervised c lu ste ring of gene s 用 PCA SHC把 已 知 类 别 训 练 样 本 聚 类 成 若 干 聚 簇 , 用 [ C ] / / P roc of the 15 th Confe rence in Comp u ta tiona l Sta tistic s. 2002. MA TLAB 统计工具箱的线性分类器 c la ssify和训练样本及其聚 DUDA R O , HAR T P E, STOR K D G. 模式分类 [M ]. 北京 : 机械 [ 6 ] 工业出版社 , 2003: 442 2447. 簇类把待测样本分类成聚簇类别 ,按聚簇类原来的模式类别变
赵鹏大 ,胡旺亮 ,李紫金. 矿床统计预测 [ M ]. 北京 : 地质出版社 , 换成模式类别 。[ 7 ] 1983: 157 2161. 2 1113 测试方法N EWMAN D J , H ETT ICH S, BLA KE C L , et a l. UC I repo sito ry of [ 8 ] 本实验以 10组交叉验证的方式 ,将样本材料随机分成 10( ) m ach ine lea rn ing database s[ EB /OL ]. 2006 210 206 . h ttp: / /www. 组 ,每组轮流当测试样本 , 其余为训练样本 ,如此执行完 10 次 ic s. uc i. edu / ,m lea rn /MLR epo sito ry. h tm l. 后 ,得到了 10组分类误差率 ,共进行 10次 ,把分类误差率作为 ( ) [ EB /OL ]. 2006 210 206 . h ttp: / / fina lfan tasyxi. inf. c s. cm u. edu / [ 9 ] 该样本集的平均误差率 。MA TLABA rsena l /MA TLABA rsena l. h tm. 2 1114 实验结果分析 用目前具有一定代表性的七种分类器[ 10 ] F INL EY T, JOACH IM S T. Sup e rvised c lu ste ring w ith suppo rt vec to r 对此四个数据集进 m ach ine s[ C ] / / P roc of the 22 nd In te rna tiona l Confe rence on M ach ine
行分类的 10 折交叉验证结果进行了比较 ,对比数据来源于网L earn ing. Bonn: [ s. n. ] , 2005.
范文四:几种聚类方法的比较
几种聚类方法的比较
李世蜂黄磊铷昌平
中国科学院自动纯研究所
E-maihshifengJi@maiLia.ac.
摘要:聚类已经不仅仅限于经典的模式识别领域,而广泛应用于统计理论、机器学习和数据挖掘.除了提取样本的统计分布特征作为识别的有力手段,聚类在高维、大规模数据库的数据分析方面也发挥着越来越重要的作用,推动了相关理论的快速发展.本文介绍了聚类中常用的若干方法及其改进,提出一种新的聚类方法,并应用于脱机手写数字的识副,以期通过比较反映这些方法的某些特性.关键词:聚类算法,合法性.
EvaluationofClusteringAlgorithms
LIShi-feng,HUANGLei,LIUChang-ping
InstituteofAutomation,ChineseAcademyofSciences
Abstract:lnadditiontoapplicationtoclassicaIpatternrecognitiondomain.clusteringhasbeenwidelyusedinstatisticaItheory,machineIearninganddatamining.Aswellasapowerfultoolinrecognitionbyextractingstatisticalfeatureslyingininputpatterns.clusteringisplayingamoreandmoreimportantroleindataanalysisofhigh—dimensional,large.scaledatabases,thus
promotingarapidtheoreticdevelopment.Thepapersummarizessomecqmmonlyusedalgorithmsandnewimprovementinclustering,includingonewhichisadvancedforthefirsttimebyus.whichareimplementedInoff-linehand-writtendigitsrecognition.toevaluatetheproperty.
Keywords:Clusteringalgorithm,Evaluation.
1.引言
聚类可以定义为将一群数据组织为若干个内部成员相似的群体的过程:作为一种反映数据特征的手段.聚类的目的是使数据样本的类内相似性晟大.而使类问相似性最小.总体上来说。聚类方法分为两种:分割聚类(PartitionalClustering)和分层聚类(HierarchicalClustering).
分割聚类是一种平面聚类.其本质是将所有输入样本用若干个具有代表意义的中心点来表征。这些中心点形成字典用于匹配.在定义花费函数c:{z:xES)—÷婀+后,分割聚.103.
类转化为使总花费函数yc(S。)最小化的优化过程.常用的花费函数如平方和函数.分割百
聚类优化准则的普遍缺陷是聚类结果偏于超球型结构.同时对“噪声”处理程度不够.K.均值作为一种典型的分割聚类,因其理论简单且易于实现得到了广泛的应用,但只能逼近局部最优而非全局最优,且对初值的选取敏感。
分层聚类本质是分类的逐步细化求精过程,包括自上而下的分裂算法和自下而上的聚集算法,后者在实现上简单一些,将所有样本S分配到互斥集合S…S∥。S。,根据花费函数不断找到(s,,s,)对,使得其合并的“代价”煨小.常用的花费函数如Single.1ink、Axerage-link、Complete.1ink.这些基于中心或基于所有点的、以最小化方差为目标的优化方法,类间的大小差别以及类形状是否为超球有很大的影响,另外类问噪声也往往会引起误分类。
本文的目的是比较和评价几种聚类算法的特性.本节对聚类做了一个大致的描述:第二节介绍了几种常用的聚类算法并指出了各自的优缺点;第三节列举了这些算法用于脱机手写数字识别的试验结果并作评价;第四节对聚类方法的发展作了展望.
2.聚类算法介绍
2.1基于对称的K.均值聚类
su和Chou对类中样本点的分布情况作了台理的假设,即样本空间中每一类的样本点关于该类中心具有对称性【l】?输入样本x,和类C(类中心为c)之间的对称性距离定义为
d(XC)=
m呲wnⅣ
当z,在C中有完全对称的样本时,d,(x,,C)取得最小值0?将K.均值算法与对称性距离相结合,su和Chou提出了改进的基于类对称距离的SBKM算法.并且在人脸检测中取得了不错的效果.但是,由于确定对称性距离需要遍历整个样本集.计算量很大.一
.104-22J-均值聚类考虑到K一均值算法中可能引起的退化,Hansen等提出了弓I入启发式策略、在局部最优情况下搜索近邻并重定位样本的J-均值算法f2j.定义自身为类中心的样本点为被“占据”的样本点,优化目标函数为L.J-均值中类中心的重定位倾匍于相邻的、未被“占据”的样本点.具体如下:1.K_均值算法过程得到M个初始类中心,并找到未被。占据”的样本点(误差范围内):2.搜索相邻样本点:对每个样本x.(J=1,--.N)重复以下步骤:
2.I(重定位)[trJ果xJ耒被“占据”,则增加新的类中心;^,“=工』,找到最适合
删除的类中心j?记‰为目标函数的改变量
2.2(找最优)记录使K最小的f和』
?3.移动:用_.替换类中心;-?重新分布样本,修改,‘=厶+’,
4如果厂>-,0,错iaL;否则接受移动-转2步.
引入了启发式策略对类中心重定位.不仅防止了退化,而且有可能跳出传统K一均值的局部最优.使聚类结果得到改善.
2.3增长细胞模型(GCS)
在神经网络中通过邻近单元的相互学习(竞争学习),可以自适应地发展成为对于不同性质信号敏感的区域.GCS模型就是这样一种利用Hebb规则修改权值,在激励区、弱激励区、抑制区形成“墨西哥草帽”效果并实现数据聚类的一种自适应算法t4]【5】【6】.在无监督的情况下,GCS能通过细胞的不断加入和删除,最终自动找到合适的网络拓扑结构.在理想的结果状态下。每个输入样本出现在各细胞(类中心)处的概率相等.对应的信息熵值达到最大,反映出GCS在估计样本的未知概率密度分布方面的良好能力.
GCS的算法步骤如下:
1.初始化拓扑结构和相应权值:
2,从样本集中输入样本x,由指定的距离函数确定最佳匹配(获胜)单元(竟争过程):3.确定激发邻域A(协作过程),并且根据Hebb规则修改权值:
4当满足特定条件时增加或删除节点单元:
5.返回2直到满足结束条件.
GCS只需要预先取得少量细胞节点,其拓扑结构通过学习利用细胞的不断加入和剥除发展而来,因而针对具体问题有更好的适应性.与GCS类似方法的模型是增长神经气体(GrowingNeuralGas,GNG)f91和增长格子(GrowingGrid,GG)【7】.
2.4概率GCS(PGCS)
Vlassis等将贝叶斯决策规则MAP与GCS聚类过程相结合.提出概率GCS[8].假设类中样本服从多维高斯分布
仇(w%∑。)=(2F)…2刚。”exp(-去扣叫。)∑?o一,~)7)
先验概率黼F卜÷善p(‘J‘)
对输入样本x..根据MAP确定其所属类盘如果.相应调撬类中心和类方差
“““’=∥:”+q:””【x.+l—pp’】.105.
盯;(^“’=盯;‘”’+叩{““’[(x。“一∥j”1)(x。+l一∥{”’)7一?,12扣’】
躺糕黼~躲龃:掣申(g)2掣雌V%参,
PGCS中细胞节点的插入和删除考虑了样本的先验分布以及类的方差.而且聚类过程中同时调整类中心和方差,所以能得到更好的聚类效果.
2.5多代表聚类(ClusteringUsingRepresentatives.CURE)
在一般的分割聚类和分层聚类方法中,各类往往只由类中心来代表,即主观假设类形状为超球:而且优化目标函数往往以最小化方差为目标.这样当类的形状和大小相差很大或存在噪声时往往导致误分类.例如著名的“锁链效应”.
Guha等提出的多代表分层聚类(CURE)【13】具有非常简洁的思想.每个类的所有样本点不再由单个类中心代表,而是由多个敞布于类中、能够表现类几何形状的样本点代表:同时为了消除外围噪声带来的影响,这些散布的样本点向类中心“收缩”一个比例因子,力求在表现类形状的同时减小噪声的扰动.正是这样的特点使得CURE能够较好地分辨任意形状的类,同时对噪声具有很好的鲁棒性.
记初始代表点集合RepSet=t6,取得类代表的算法如下:
while(现有代表点数目<欲取得的代表点数目)
{如果现有代表点数目为0:
找到类中距高类中心最远的点作为第一个代表点,将其放入集合RepSet;
否则:
{求类中每个样本点与RepSet中所有代表点的最小距离;
在这些最小距离中取最大,该距离对应的样本点是新的代表点,加入RepSet;
}
)
所有代表点向其类中心方向收缩:
P=(1一a)P+aMP为代表点的权值,M为类中心权值,a为收缩因子
在多代表分层聚类算法中,节点(子类)之间的距离由其代表点之间的最近距离确定.相比BIRCH对非超球形状的误分类、MST对噪声的敏感度,CURE在聚类效果上占有优势.2.6交迭聚类(OverlappingClustering)
交迭聚类是我仃J在商标闰像检索中提出的一种新方法,其主要思想是:考虑到采用不同特征的聚类结果往往呈现不同的风格.为了充分融合这些风格井使单一特征可能引起的误分类的影响降到晟低,得到更加逼近真实的类样本分布情况的聚类结果,我们采用了两种相近似的特征.分别聚类后按照其结果交迭程度的大小合井得到最终的聚类结果.相比一般的分割聚类.该方法的优点是既保持了类中样本的动态调整,又能够使类中样本尽可能完备.
表1对以上列举的各种聚类方法的属性作了一个小结,以便于比较..106.
聚类方法
类型
K一均潼
j.均瀣
GcS所羁输入参数分割分割分割
分割
分层聚类数目聚类数目聚类数目、是大邻居数聚类数目、最大邻居数、类先验概率、协方差聚类数目、初始粗分类
表ISingle-link优化g标平方和函数平方和函数平方和函数MAP聚类移拣球形球形球形任意任意是否特魏处理噪声否是否否是PGcscURE聚类方法及属性
3.试验结果
在实际工作中,我们将上述的某些方法用于脱机手写数字的聚类,得到了相应的数据如下表。考虑到结果的可推广性,试验对象采用美国国家标准与技术局收集的MNIST手写数字样本库,训练样本和测试样本分别为6万和l万个,样本除线性归一化未作其它任何处理。样本特征采用在实际工作中证明效果良好的方向线索特征(DirectionalElementFemum,DEF)【17】,同时考虑到样本集中样本的数量.为了防止维数灾难出现。196维DEF特征通过线性PCA降为48维。其它需要说明的是:
1.除PGCS中采用贝叶斯分类器外,其余方法均采用最近欧式距离分类器;
2.K一均值方法由于随机选取的初值影响较大,故而在试验多次之后取最优.实践证明
即便每次初值选取不同.识别率结果相差也在很小的范围内:
3.所有聚类的结果未作进一步的学习优化。
聚类方法
圻
翻讽练集K.均值3.均值基于对称的K.均缱GcsPGCsCURE交迭聚类950395.7495.16950097.3l961395.87墓
一looj搠试蕖94.769525
表294.8294.8796.6l958095.58不同聚类方法用于MNIST库的识别结果
98
97.5
97入
。.r∥一。|.7》。96.5
96,’/\k。蠢+.
∥
一/..\95.595,7√k、‰。、
。。r。.?、//1—,一:::弦94.5
94
93.5
93”-j..%I瓣c。“礅’a钟冉、?;气t‘v一’p^t}争、一日gp。一".4焉器蝴节霄霸黑_■g.”;。
GcsrGcs、;童§.,、.辩错l鲢g.“’一1、囊o.∞、.鼍ic-均flijj嚣茕≮毫‘霸蹲_霹ff-均fti薷王骂鬻
Itt1c啦交迭聚粪MNIST库的识别结果比较圈..107..
由上表可见:
1.基于对称的K-均值和普通K.均值在识别率上的微小差异,证明了由K-均值得到的
聚类结果已经具有较好的对称性——考虑到K.均值聚类结果偏于超球状的特性,这
一点是可以理解的.引入启发策略的J.均值由于较多地考虑到了噪声,同时可能避
免局部极小的出现。因而得到较好的结果:
2.对于MNIST数字库,GCS对K-均值未能特别体现出优势,然而我们在对其它尤其
是大样本库的测试中。GCS要明显优于K.均值:
3.相比K.均值,CURE算法的结果识别率说明多代表在反映类几何形状方面的良好能
力,然而付出的代价是计算复杂度的提高.而且对于类内方差相对较小的手写数字
样本,我们认为分层聚类的CURE算法并不能完全体现出优势;
4.PGCS方法中,贝叶斯规则充分利用了样本的先验信息,同时类内的协方差矩阵部
分地反映了类的形状特征.所以能取得良好表现.事实上.在其它的样本情况下.
我们也有同样的结论.
4.结论与展望
聚类作为一种数据分析的手段,经过儿十年的发展.已经形成了多种具体方法.然而,处理实际问题时,面对的主要挑战并不是聚类算法形式的选择,而是算法背后针对不同问题的优化思想的选择。优化目标不同时,得到的聚类结果往往大不相同;因而,怎样确定聚类效果评价标准,根据具体样本的特点选择算法以尽量避免误分类,是聚类时需要考虑的首要问题。
一般来说.评价聚类算法好坏的标准体现在:1)处理噪声的有效程度;2)能否反映任意形状的类;3)输入样本数据是否顺序无关:4)高维样本情况下的运算效率;5)输入参数的个数等方面。目前的聚类算法在这些方面还没有达到让人满意的程度。
事实上,所有的聚类算法都对输入的样本数据作出了或多或少的先验假设,如预定义的距离(相烈性衡量)函数的台理性、数据在所定义的样本空问是正确可分的,或者高斯混台模型中的类中样本服从高斯分布等等,至今尚没有办法从理论上对这些假设作出完整的评价。
与聚类相关的一个重要的问题是聚类合法性问题,即怎样评价聚类结果的问题。其中最重要的方面是样本空问中内在“子结构”数目即聚类数目的确定:聚类数目选取不当,常常会引起误分类及识别率的降低。评价聚类的合法性最常见的方法是引入一个静态评价指标。聚类的数目就是使该指标取得极大的数目.与这种不断迭代确定最优的方法不同,动态方法往往通过一定规则下子类的分裂和合并确定虽佳聚类数目。
为了提高聚类结果的准确性和加速聚类过程的进行,对样本数据进行某些处理是必要的,方法包括样本提取及变换、维数压缩等,限于篇幅,本文未作涉及。.108—
参考文献
(IJMu—ChunSu,Chien-HsingChou。“A
onModifiedVersionoftheonK?Mea|IsAlgorithmwithaDistanceBasedClusterSymmetry”、lEEETransactionPattemAnalysisandMaehine
Intelligence,VoL23,No6,June2001
(2]Piegre
ofHa^sen,NenadM[adenovic,“J-Means:aRecognitionnewlocalsearchheuristicforminimumsumsquaresclustering’’,Pattem34(2001)405?413
【3】T.Kanungo,DM.Mount,S.Netanyahu,CPiatko,R.Silverman,A.Y,Wu,“AnEfficient
K—MeansClusteringAlgorithm:AnalysisandImplementation”。Proceedingsofthe160ACMSymposiumonComputationalGeometry,June2000.100?109
【4】BerndFritzke,“GrowingCellStructure--ASelf-OrganizingNetworkforUnsupervisedand
SupervisedLearning’jNeumlNetworks,Vol7,No.9。1994
Clustering【5】BemdFritzke,“Unsupervised
Seattle.IEEEWithGrowingCellStructures”。ProcOftheIJCNN-91
(61BerndFritzke,‘'GrowingSelf-organizingNetworks--Why?”,ESANN’96,D-FactoPublishers,
Brussles,1996
【7】BemdFritzke,“GrowingGrid—ASelf-organizingNetworkWithConstantNeighborhood
RangeandAdaptationStrength’jNeuralProcessingLetters,V01.2,No.5,9-13,1995
Papaknnstantinou,“TheProbabilistic
Networks,【8】NikosA.Vlassis,ApostolosDimopoulos,GeorgeStructuresGrowingCellAlgorithm”,Proc.7”Int.Conf.OnArtificialNeural
Lausanne,Switzerland,Oct1997
【9】BemdFritzke,“SomeCompetitiveLearningMethods”,technicalreport,InstituteforNeural
Computation,Ruhr-UniversityBochum,Apr1997
f10】Wen’Jy;Hwang,Bo-YuanYe,Chin-TsaiLin,“Anovelpetitivelearningalgorithmforthe
parametricclassificationwithGaussiandistributions”,PattemRecognitionLeaers2I(2000)
【11】JLarsen,A.Szymknwiak,L.KHansen,“ProbabilisticHierarchicalClusteringwithLabeled
UnlabeledData”,technicalreport,InformationandandMathematicalModeling,Technical
EMUniversityofDenmark,2001【12】ShotaroAkaho,“Mixture
report,April1995modelofimageunderstandingandthealgorithm”.technical
【13】SudiptoGuha,Rajeev
forRastogi,KyuseokShim,“CURE:AnEfficientClusteringAlgorithmonLargeDatabases”.InProceedingsofthe15“InternationalConferenceManagementofData,(SIGM01D),Volume27(2)ofSIGM01DRecord,pp73?84,Seattle,、№,USA,1998
MixtureswithUnknownNumberof【14】边肇祺.张学工。“模式识别”,清华大学出版社fl5JSRichardson,P.Green,“OnBayesian
Components”,J.RoyalStatisticalAnalysisofSoc.(B).Vol59,pp731-792,1997
【16】VF.Wond,“Clusteringdatabymelting”,NeuralComputation,1993,5(I):89-104
[I7lNeiKato,MasatuSuki,Shin’ichiroOmachl,HirotomoAsc,YoshiakiNemoto,“A
Handwritten
AsymmetricCharacterRecognitionSystemUsingDirectionalonElementFeatureandandMahalanobisDistance”。IEEE
1999TransactionPattemAnalysisMachineIntelligence,V01.2l,No.3,March
.109.
几种聚类方法的比较
作者:李世峰, 黄磊, 刘昌平
作者单位:中国科学院自动化研究所
被引用次数:2次
1. 李德军. 吕艳华. 王润田 模式识别技术在泥浆浓度反演中的应用[期刊论文]-中国工程科学 2007(5)
2. 李德军 泥浆浓度反演建模[学位论文]硕士 2006
本文链接:http://d.g.wanfangdata.com.cn/Conference_4203552.aspx
范文五:融合减法聚类与C_均值聚类的目标定位方法
计 算机仿真2012 29 7 7 第 卷 第 期年 月
, 9348( 2012) 07 , 0269 , 05: 1006 文章编号
C, 均值聚类的目标定位方法融合减法聚类与
1 1 2 ,,张君昌李 明谷卫东
( 1, ,710072; 2, ,710071)西北工业大学电子信息学院陕西 西安 西安电子科技大学电子工程学院陕西 西安 。:摘要视频运动目标的检测与定位是视频监控系统的主要技术之一针对现有视频监控系统目标定位过程在目标被浅度遮
,。、挡或存在噪声时定位不准确的问题提出了一种新的视频运动目标定位方法采用减法聚类聚类有效性函数与加权模糊 C , 。, ,,C 均值聚类方法相结合首先利用减法聚类获得初始聚类中心再通过加权模糊 均值聚类算法对视频运动进行目标
,。。,定位避免了算法陷入局部最优而获取了全局最优然后引入聚类有效性函数获得视频序列中目标的最佳个数仿真结
,,,果表明改进方法对存在噪声或野点的情况具有较好的鲁棒性并可以在不需要人为给定待检测图像目标个数的情况下对 存
。在浅度遮挡区域的目标进行准确定位
:; ; ; 关键词减法聚类模糊均值聚类聚类有效性目标定位
:TP317, 4 :B中图分类号文献标识码
Joint Subtractive Clustering and C ,M eans Clustering
Obect Locaton Agothm jilri
1 1 2ZHANG Jun ,chan g,LI Ming,GU Wei ,d ong
( 1, Schoo of ectroncs and nformaton,orthwestern Poytechnca nversty,an Shanx 710072,Chna lEliIiNlilUiiXiii;’
2, School of Electronic Engineering,Xidian University,Xi’an Shanxi 710071,China)
ABSTRACT: Movng obect detecton and ocaton are core technooges in vdeo surveance system, In order to m- ijililiiilliprove the present boect ocaton methods vdeo surveance system,a nove movng obect ocaton method was jliin iilllijliproposed, The new agorthm combnes the subtractve custerng,custerng vadty functon wth the weghted fuzzy C liiilililiiiii,mean s custerng, The subtractve custerng was used to obtan nta custerng centers,and then the ewghted liiliiiiilliifuzzy C ,mean s clustering was used to locate the moving object,which makes the algorithm able to avoid local opti- mum and get theg lobal optimum, Finally,the clustering validity function was introduced to obtain the optimal number of the clusters, Simulation results show that thep roposed method has a good robustnesseve n in a high noisy or outli- ers envroment,and can accuratey ocate the movng obects whch has overap areas wthout the gven number of the illijilii
obects in the detectedm ages, ji
EYORDS: Subtractve custerng; Fuzzy means custerng agorthm; Custerng vadty; Obect ocaton KWilililililiijli
,区域生长的方法是将目标空域分成若干区域后进行定位因 1 引言
此在目标空域连通性较差的情况下容易导致重复定位的问 ,视频图像是人们从客观世界获取信息的主要来源近年
。,、、 基于水平垂直投影的方法是将目标检测中提取的二值 视频监控技术已经被广泛地运用到交通安全工业生产题来
。,物流和电力等领域视频运动目标的检测与定位是视频监 通过记 图像对水平轴和垂直轴分别做垂直投影和水平投影
,是其它后续的视频信号处理如目标 ,控系统的关键技术之一但该方法不适用于 录的像素点个数来确定运动目标的位置,1,,2,,3,,、、视频压缩编码视频检索等应用的基础能否准 确地跟踪。基于模式分类的方法主要是数据聚类 多目标定位的场合
。 定位出视频运动目标将直接影响着后续视频处理的效 果
, , 。,K ,,C 均值聚类减法聚类均值聚类等的方法其中包括 : 现有的目标定位方法主要有三种基于区域生长的方 ,4,、。 基于水平垂直投影的方法及基于模式分类的方法基于 Severne Dubusson K , ,ii等人采用 均值聚类进行定位但由法
,于该方法需要人为给定待定位目标的个数并且容易受噪声
,。因此该算法在具体应用场合受到一定的限制孙志 的影响 海和孔万增将减法聚类用到图像人脸和视频运动目标的定,5,,位中该方法在目标区域存在浅度遮挡的情况下定位效果 , 06 , 29 : 2011 , 09 , 30: 2011 收稿日期修回日期
,,针对上述问题本文提出了一种新的视频运动目标定位标进行准确地聚类克服噪声环境下聚类不够准确的问题,6, ,C , ,FC M) ( NW 方法将改进加权的模糊 均值聚类算法与 ,但由于该算法的划分矩阵和聚类中心随机给定使得该算,7,,FC M ,NW ,减法聚类相容融合在利用 算法对目标进行 定容易陷入局部最优值在目标定位中不能够准确地获取目
位之前首先通过改进减法聚类来获得目标的初始聚类中 ,,的聚类中心并且若将该方法用在实时定位场合设定的 ,,心使得该算法获得全局最优值达到获取准确目标中心的 ,代终止条件不一定能够得到聚类最佳个数因此在应用时 ,。目的再利用聚类有效性函数进行聚类最佳个数的确定理 ,,在一定的局限性为此本文在该算法进行定位之前首先
,论分析和仿真结果表明本文方法可以有效解决了目标中存 ,。减法聚类 用减法聚类获取运动目标的初始聚类中心
,在噪声或者遮挡区域情况下定位不准确的问题并且不需要 Chu ,i提出的一种基于密度指标值的模糊聚类算法通过密
,人为给定目标聚类个数弥补了当前目标定位算法中在实时 ,值函数来估计所有样本点的密度值并选择密度值最高的
,性和准确性上所存在的缺陷而且在噪声环境下也具有较好 ,本点作为第一个聚类中心然后修正其他所有样本点的密 。鲁棒性 ,。:指标直至确定足够多的聚类中心其算法步骤如下
1)( 1) ;通过式来计算所有样本点的密度值n 2 运动目标定位方法问题的提出22 ,4x, x/ r‖‖ jai P= e( 1 i? ,FC M NW 基于减法聚类与聚类有效性函数 算法的视 j = 1
r,;1 。其中 是一个正数为聚类中心有效领域半径频目标定位可由图 来表示通过背景差技术检测出来的 a
( 、差值图像经过预处理以后包括去噪最优阈值化以及下采 2) 1 x,如果通过步骤 所得到密度指标最大的样本点 1 ) ,,NW ,FC M 样首先利用减法对目标区域进行聚类获取 算 P,( 2) 应的密度值为 则利用式来修正样本点的密度指 1 ,NW ,FC M ;法的初始聚类中心避免了 算法陷入局部最优值 值
,,而获得全局最优然后利用该算法对目标中心进行定位将 2 ,, ( 2PP,P * exp / r ,4 x,x ‖‖ i i 1 i 1 b这两种聚类算法结合以后应用到定位技术中不仅能够有效 3) ( 3) ,,判断式是否成立若成立则停止计算否则跳解决目前视频运动目标定位场景中存在浅度遮挡区域的定 2 ,1 ) ,。( 到步骤 继续执行参数 δδ 是事先给定的参数此 ,位问题而且可以将目标从噪声或者野点环境下准确定位出 。数决定了初始化聚类中心的数目 ,,来最后通过比较聚类有效性指标值在不需要人为给定的
P/ P, ( 3δ 。情况下即可获得目标的最佳个数 i 1
,从上述步骤中可以看出减法聚类主要是计算所有数
,点的密度值因此密度函数值的计算对算法效率是会产生
( 4) ,r = 1,a = 4 。响的减法聚类的密度函数为式在 时可 近
( 5) ,,似地写成式本文借鉴核函数的非参数密度估计 法
Chiu ,将 所定义减法聚类的密度值函数做适当的优化
( 5) Epanechikov ( 6) ,式密度值函数近似用 核函数所代替
( 5)( 6) x 。和中的 代表归一化后两向量点的距离 2 = exp( , x,x / r )f( x)α‖‖ ( 4c 2 , ,0 x 1exp "",4 x =f( x)( 5 , 其它 0 1 图视频目标定位系统 3 2, ,0 x 1"" 1 ,x 4 = f( x)( 6, NW ,FC M 基于减法聚类与聚类有效性函数 算法的视 0其它1 。频目标定位可由图 来表示通过背景差技术检测出来的
( 、差值图像经过预处理以后包括去噪最优阈值化以及下采 表 1不同循环次数下密度函数的耗时比较 ) ,,NW ,FC M 样首先利用减法对目标区域进行聚类获取 算 8 9 10 函数式101010次循环次循环次循环 ,NW ,FC M 法的初始聚类中心避免了 算法陷入局部最优值 2 ,,, 1s, 5s, 1s77091而获得全局最优然后利用该算法对目标中心进行定位将 exp( ,4 x) 这两种聚类算法结合以后应用到定位技术中不仅能够有效 2 0, 9s 5, 7s 12, 3s 3( 1 ,x ) /4 解决目前视频运动目标定位场景中存在浅度遮挡区域的定
c。,。佳个数 样本点的密度值直到找到所有有效的聚类中心
2, 4 C , 2, 2 融合减法聚类与模糊 均值聚类的运动目标定位方 视频运动目标定位
NW ,FC M 。法本文采用 算法对视频运动目标进行定位这
本文将融合减法聚类与聚类有效性函数的改进加权模 ,利用聚类均值增加 种算法利用权重均值增加分类的准确性
, 。C 糊 均值聚类算法运用到视频运动目标定位中该算法 ,在准确性和稳定性上要明显优于传统的模糊 算法的稳定性
,聚类中心的数目是根据 采用减法聚类确定初始聚类中心时C , ,、均值聚类算法解决了样本数据中存在噪声点外界野点
0, 5 ,选定的 δ 来确定实验发现在 δ ?时得到的聚类个数比 ,将该算法用到视频 或者区域交叉情况聚类不够准确的问题,9,, 5 K ,,= 0较合理其中在 δ 时得到的聚类数目 最多在获取 ,解决了目标区域存在遮挡情况下的定位问 目标定位当中
NW ,FC M ,算法的初始聚类中心时聚类中心出现的顺序由 ,。并且对噪声也具有较好的鲁棒性该算法的目标函数 题
,,c NW , 的 因此在进行聚类个数为 其密度指标值所决定: 为
c n FCM ,c ,算法时只需要选择前 个聚类中心并不重新进行减
,。从而提高了算法的效率本文利用固定间隔帧间的 法聚类m 2, , , m , ( 7)udist 1,J = ? ,M x !ij?? jji, 采用背景差技术检测积累差异信息自适应地建立背景模型 i = 1 j = 1
,Mu,m 其中 为划分矩阵 为模糊权重指数为权重均j j ii
:值 ,Ostu ,出前景目标区域并利用 二值化方法进行最优阈值化 nn ,1,1然后对目标区域下采样以后用本文所提出的方法对目标进 =u( 8)c,x c,x Mux/ ‖‖ ‖‖ it j k j t ij k k i? ? ,,行定位比较计算有效性指标值后获得目标的最佳个数其 k = 1,kj t = 1,tj ??c 。2 整体流程如图 所示 j,u= 1 ,在约束条件 下利用拉格朗日乘数法即可ij ? i = 1
U。NW ,FC M 求得拉格朗日乘子 ξ和隶属度矩阵 算法的聚j ( 9) 。类中心通过式来计算
nn mm j = 1,2,…,n( 9)= ux/ uc ij j iki ?? j = 1 k = 1
2, 3 目标最佳个数获取
NW , FCM ,本文将聚类有效性函数引入到 算法中以达
。紧致性和分离性常 到获取视频运动目标的最佳个数的目的
。常用的聚类有效性函数 被用作验证聚类有效性的重要指标
eBen V( U,V; X) Xi_i有 提出的聚类有效性函数 以 及 XB
FukayamaSugeno V( U,V; X) _。提出的 等由于在目标中存在 FS
,大多数的指标都不能有效地检测 重叠区域或噪声的情况下,8, Rezaee,Babak 出聚类最佳个数因此 提出了一种有效性指 V( c,U) , 利用该有效性函数中所提出的紧密度和分离度 标SC
指标可以在样本间存在重叠区域或含噪声的情况下准确地
。:该算法分离度有效性函数为 检测出目标个数
2 ×Sep( c,U) = c( c ,1 ) ( 10) c n
, , , , , ,, , , ,c ×m in ×h u,uxxx ??FFj j j p q qp j = 1 ?
,c ,u( x) j 其中表示聚类的个数表示第 个样本点属于Fi j c
, , , , , , i = , ulogu。,h 第 类的隶属度大小紧致xxxFa F? j j j i i i = 1
:度有效性函数为
c n2 2, , Comp = u,v ( 11)x ‖‖c,U ij j i?? = 1 j = 1i 将分离度和紧致度函数综合后的聚类有效性指标值可 ( 12) :以通过式来计算 图 2 目标定位算法流程图
, , , , , , V= Sep / max Sep + c,U c,U c,U SC c = 2,…,c max ( 12) 3实验结果与分析, , , ,Comp / max Comp c,U c,U AMD,CPU 为了说明本文所提出方法的有效性在 为 c = 2,…,c max
V( c,U) , 定义为紧致度和分离度的和最小值对应了聚类最SC Athlon( tm) 64 X2 Dual Core Processor440 0 + @ 2, 31GHz,内
nter xt 。E_Ei_了定位实验本文采用的视频序列一部分是
Crossing_Paths ,HighwayII _raw 视频序列一部分是标准的 视 表 2聚类中各有效性函数指标值 ,320 ×24 0,RGB ,24 频序列视频大小压缩为 图像每个像素 比 有效性函数,, 特来测试该方法的有效性并与其它视频运动目标定位 方类别数 , 5VVV( 10 )FS SCXB 。法进行了比较
20, 02902, 0, 38701, 8602 , 13本文方法定位效果以及与其它方法的比较 3, 04044, 0, 6884, 1340013 Enter_Exit _Crossing _Paths 215 图 为 视频序列的第 帧 4 0, 02989 , 1, 2686 1, 1636 ,,图像的定位效果图利用了不同方法对目标进行定位并标 5 0, 05631 , 1, 1852 1, 5802 。3 ( b) ,记了聚类中心坐标的位置从图 可以看出该视频序
,列右侧的两目标区域间存在浅度遮挡通过本文所提出的定
,位方法可以准确地将视频中的运动目标定位出来并且不需 V2 V2,从表 中可以看出通过 检测到的聚类个数为 XB 。要人为给定待检测目标个数 4,检测到的为 而利用本文的聚类有效性函数检测到的聚
3,个数目为 说明本文方法的有效性函数在样本间有交叉
,域的情况下检测结果要优于其他两种方法通过计算聚类
,效性函数来确定最佳聚类个数解决了在视频运动目标定
。系统当中需要人为给定待检测目标个数的问题通过上
: ,仿真得知本文方法在遮挡情况下定位更加准确而且可
。自适应获得目标最佳个数
3, 2 噪声环境下的定位情况
,为了说明本文方法在噪声环境下的定位效果使其与
Hghwayraw 117 iII_统的区域生长法对 第 帧图像进行了定
。4 ( b) ,分析和比较如图 中所示在未通过滤波二值化的
,,况下图像的连通性较差并且存在噪声点如果用传统的 域
,, 生长法定位效果并不好不仅对目标进行了重复定位且
( 4 ( d) 把噪声点也作为目标进行了定位图 最右侧两个 框
) ,。所标记而本文所提出的方法并没有受到干扰该仿 说
明了本文所提出的方法不但可以在连通情况较差的情 下
,能对多目标进行定位而且在噪声点存在的情况下也具 较
,。好鲁棒性说明本文方法具有很强的实用性
3 图不同方法的定位效果
3( b) ,,K 从图 中可以发现右侧两人存在浅度遮挡用 均
,值聚类的方法对目标的聚类中心点定位不准确将右侧两人
( 3 ( d) ) ,的目标中心点定位在了同一个人身上图 所示并且
3,需要人为指定聚类的个数为 用减法聚类虽然能够将三个
,( 3( e) ) ,目标定位出来但在该方法中图 所示定位出的右上
,方目标中心与真实的目标中心之间存在一定的误差并且减
法聚类需要给定适合的聚类半径才能够得到聚类的最佳个
3, 3 :新方法的有效性分析参考文献
Enter 3 _ 表 列出了利用本文提出的方法与其他方法在 ,1,Ca Lng,He Le,Xu Yren,Zhao Yuming,Xin Yang, Mut ,o b-iiiili
Exit_Crossing_Paths 215 ect detecton and tracng by stereo vson,J,, Pattern ecognjikiiiRi- 视频序列的第 帧图像中定位性能的
,:如下所示 tion Letters,43,2010: 4028 , 4041, 比较
Fatih Porikli, Real ,T ime Video Object Segmentation for MPEG ,2, Encoded Video Sequences,J,, SPIE Conference on Real ,T ime I- 表 3 不同方法的聚类中心比较 magining VIII,2004,5297: 195 , 203, ,均值聚 类减法聚类改进聚类采用的方法K ,3,Changick Kim, Fast and AutomaticVideo Object Segmentation and
333聚类个数Tracng for Content ,B ased ppcatons,J,, Transactons on kiAliiIEEE i 107, 3 30, 3 12, 7 Crcuts and Systemsf or deo Technoogy,2002,12 ( 2 ) : 122 距离误差iiVil
( 141,31) ( 128,30) ( 128,32) , 129,
,4,(( 163,11) 161,26) ( 165,84) Severine Dubuisson,Jonathan Fabrizio, Optimal recursive cluste- 目标中心值
(( 166,86) 169,95) ring of likelihood functions for multiple object tracking,J,, Pattern ( 169,132)
Recognition Letters,30,2009: 606 , 614,
,5, ,,, 孙志海孔万增朱善安基于减法聚类算法的视频运动目标 ,物理定义中标准的目标中心值由目标内所有坐标点的,J,, ,2008,7: 0012 , 0016,定位光电工程 ,3 : 坐标之和除以总点数获得表 中目标的标准中心点为 ,6,Hung Chih ,Ch eng,S Kulkarni,Bor ,Ch en Kuo, A New Weigh- ( 127,29) ,( 164,30 ) ,( 173,93 ) ,: =距离误差利用公式Δ ted Fuzzy C ,M eans Clustering Algorithm for Remotely Sensed Im- 2 2, , , , ,3 +计算获得比较表 中的距离误x,x y,y age Classification,J,, IEEE Journal of Selected Topics in Signal i 0 i 0 槡
, ,K 差项可以发现基于 均值聚类和减法聚类的定位方法所Processng,2010, i
,,,7,获得的目标中心并不准确距离误差较大有个别目标点较 S L Chiu, Extracting fuzzy rules for pattern classification by cluster
, ( ( 3) d) ,K 大的偏离标准目标中心图并且 均值的聚类个数 estimation,M,, Proceedings of the Sixth International Fuzzy Sys- tem ,δ 减法聚类是在调整合适 值下获得 是在实验中人为设定的s A ssociation World Congress ,IFSA95,Sao Paulo,B razil, July,,而本文方法通过引入有效性函数可以自适应确 的聚类个数1995: 1 , 4, ,距离误差是三种方法中最小 ,8,定聚类个数并进行准确定位Babak ezaee, A custer vadty ndex for fuzzy custerngRlliiili,。 在时间少量增加的情况下获取准确的定位信息的,J,,F uzzy Sets and Systems16 1,2010: 3014 , 3025, ,9,Nikhil R Pal,D Chakraborty, Mountain and subtractive clustering
method: Improvements and generalizations,J,, International Jour- 4 结论nal of Intelligent Systems,2000,15(4 ) : 329 , 341, ,本文针对现有视频目标定位技术存在的不足之处提出
、, C 聚类有效性函数和改进加权模糊 了一种融合减法聚类 ,,作者简介。均值聚类算法的视频运动目标定位方法该方法首先利用 ( 1969 ,) ,( ) ,,张君昌男汉族陕西武功人二站博 ,C , 然后通过加权模糊 改进减法聚类来获得初始聚类中心,,,士后西北工业大学副教授硕士生导师主要研究
,,均值聚类算法来进行聚类修正目标的聚类中心值最后由 ,;领域为信号处理无线通信
,实现对视频运动目标 聚类有效性函数确定聚类的最佳个数( 1985 ,) ,( ) ,,李 明男汉族湖南岳阳人西北工
。,本文方法可以应用在目标区域中存在浅度遮 业大学硕士研究生主要研究领域为信号与信息处 的准确定位 。 挡或含噪声的视频运动目标定位场合 ;理
( 1968 ,) ,( ) ,,,,谷卫东男汉族陕西西安人博士生副教授主要研 究
3G 、。方向为 通信网技术智能天线技术等
(217 )上接第 页
,11, ,, / 申涛褚静多输入 多输出系统动态矩阵控制鲁棒稳定性 ,,作者简介,J,, ,2005,22( 3) : 445 , 448,控制理论与应用 ( 1987 ,) ,( ) ,,旋男汉族湖北荆州市人硕士 赵 ,12,, M,, : ,俞立鲁棒控制线性矩阵不等式处理方法北京清华( ;,研究生主要研究方向为网络化预测控制,2003,大学出版社 ( 1979 ,) ,( ) ,,,何德峰男汉族浙江义乌人副教授 W Zhang, Stability analysis of networked control systems ;,13,主要研究领域为复杂系统先进控制 ,D,,C leveland,Ohio: Case Western Reserve University,2001, ( 1961 ,) ,( ) ,,,俞 立男汉族浙江富阳人教授博 士
,、。生导师主要研究领域为网络控制鲁棒控制等
转载请注明出处范文大全网 » 有约束的半监督聚类方法
αdiscc>