ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/7f15136013.html,
Journal of Software, Vol.19, No.3, March 2008, pp.663?673 https://www.doczj.com/doc/7f15136013.html, DOI: 10.3724/SP.J.1001.2008.00663 Tel/Fax: +86-10-62562563
? 2008 by Journal of Software. All rights reserved.
?
基于Tri-Training和数据剪辑的半监督聚类算法
邓超+, 郭茂祖
(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨 150001)
Tri-Training and Data Editing Based Semi-Supervised Clustering Algorithm
DENG Chao+, GUO Mao-Zu
(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
+ Corresponding author: Phn: +86-451-86402407, E-mail: dengchao@https://www.doczj.com/doc/7f15136013.html,, https://www.doczj.com/doc/7f15136013.html,/dc.html
Deng C, Guo MZ. Tri-Training and data editing based semi-supervised clustering algorithm. Journal of
Software, 2008,19(3):663?673. https://www.doczj.com/doc/7f15136013.html,/1000-9825/19/663.htm
Abstract: In this paper, a algorithm named DE-Tri-training semi-supervised K-means is proposed, which could
get a seeds set of larger scale and less noise. In detail, prior to using the seeds set to initialize cluster centroids, the
training process of a semi-supervised classification approach named Tri-training is used to label unlabeled data and
add them into the initial seeds set to enlarge the scale. Meanwhile, to improve the quality of the enlarged seeds set, a
nearest neighbor rule based data editing technique named Depuration is introduced into Tri-training process to
eliminate and correct the mislabeled noise data in the enlarged seeds. Experimental results show that the novel
semi-supervised clustering algorithm could effectively improve the cluster centroids initialization and enhance
clustering performance.
Key words: semi-supervised clustering; semi-supervised classification; K-means; seeds set; Tri-training;
depuration data editing
摘要: 提出一种半监督聚类算法,该算法在用seeds集初始化聚类中心前,利用半监督分类方法Tri-training的迭
代训练过程对无标记数据进行标记,并加入seeds集以扩大规模;同时,在Tri-training训练过程中结合基于最近邻规
则的Depuration数据剪辑技术对seeds集扩大过程中产生的误标记噪声数据进行修正、净化,以提高seeds集质量.
实验结果表明,所提出的基于Tri-training和数据剪辑的DE-Tri-training半监督聚类新算法能够有效改善seeds集对
聚类中心的初始化效果,提高聚类性能.
关键词: 半监督聚类;半监督分类;K-均值;seeds集;Tri-Training;Depuration数据剪辑
中图法分类号: TP18文献标识码: A
? Supported by the National Natural Science Foundation of China under Grant Nos.60702033, 60772076 (国家自然科学基金); the
National High-Tech Research and Development Plan of China under Grant No.2007AA01Z171 (国家高技术研究发展计划(863)); the
Science Fund for Distinguished Young Scholars of Heilongjiang Province of China under Grant No.JC200611 (黑龙江省杰出青年科学基
金); the Natural Science Foundation of Heilongjiang Province of China under Grant No.ZJG0705 (黑龙江省自然科学重点基金); the
Foundation of Harbin Institute of Technology of China under Grant No.HIT.2003.53 (哈尔滨工业大学校基金)
Received 2006-06-21; Accepted 2007-03-07
664 Journal of Software软件学报 V ol.19, No.3, March 2008
监督学习需要大量带标记数据作训练集以保证泛化能力.但在文本处理、生物信息学和网页分类等实际应用中,对数据进行人工标记的代价很高,容易获取的是大量无标记数据.无监督学习属于无任何监督信息的自动学习,虽然不需要带标记数据,但所得模型却不够精确.因此,将少量带标记数据和大量无标记数据结合的半监督学习成为机器学习的研究热点.按照学习任务的不同,半监督学习分为半监督聚类和半监督分类[1].
半监督聚类算法研究无监督学习中如何利用少量的监督信息来提高聚类性能[2].少量的监督信息可以是数据的类别标记或一对数据是否属于同一类的连接约束关系.按照监督信息的使用方式不同,分为基于距离(distance-based)的方法和基于约束条件(constraint-based)的方法[3].基于约束条件的方法目前研究应用较多[2?4],它用监督信息约束最优聚类的搜索过程,典型算法包括将约束条件加入聚类目标函数的算法[5]、强制满足连接约束条件的COP-K-均值算法[6]、基于隐马尔可夫随机域模型的HMRF-K-均值算法[7]以及Generative模型结合EM理论支持的Seeded-K-均值和Constrained-K-均值算法[8].其中,Seeded-K-均值和Constrained-K-均值算法是基于seeds集的,它们用少量带标记数据形成seeds集来改善K-均值聚类的初始化效果,进而提高整个数据集上的聚类性能.然而,Basu等人[4]通过实验表明,这两种基于seeds集的半监督聚类算法对seeds集的规模和噪声都十分敏感,规模大、噪声小的seeds集将显著地提高聚类性能.
半监督分类是从监督学习的角度出发,考虑带标记训练样本不足时如何利用大量无标记样本信息辅助分类器的训练[9],已有方法包括基于EM算法的Generative模型参数估计法[10?12]、基于转导推理(transductive inference)的支持向量机方法[13]及Graph-cut方法[14].Blum和Mitchell[15]提出的Co-training算法是另一种著名的半监督学习范型.该算法独立地训练两个分类器,然后采用互助方式迭代地扩充带标记数据集并重新训练.标准Co-training算法要求属性集能够分为两个不相交的子集,且每个属性子集都能独立训练出分类器,这在实际问题中很难得到满足.为此,Goldman等人[16]提出了一种改进的Co-training算法,不受属性集划分的约束,可用整个属性集训练两个分类器,但要求两个分类器所用的监督学习算法能够将实例空间划分为等价类集合,而且训练过程需要频繁使用耗时的交叉验证作决定.Tri-training算法是Zhou等人[17]提出的一种新的Co-training模式半监督分类算法,它使用3个分类器进行训练.Tri-training对属性集和3个分类器所用监督学习算法都没有约束,而且不使用交叉验证,因此适用范围更广、效率更高,而且比Goldman的改进算法更适合解决带标记样本少的分类问题.
实际聚类应用中带标记数据非常少,而基于seeds集的半监督聚类算法受seeds集规模和质量的影响显著.针对这个矛盾,本文借鉴Tri-training训练过程能够用少量带标记数据指导对无标记数据进行标记,使带标记训练集增大的优点,在由seeds集初始化聚类中心前,用Tri-training训练过程增大初始seeds集的规模.然而,与文献[2,18]所指出的,当少量带标记数据不足以反映大量无标记数据所蕴含的完整聚类结构时,半监督分类方法无法取代半监督聚类算法完成聚类任务的情形一样,当初始seeds集比例小时,Tri-training扩大的seeds集会包含大量误标记和噪声数据,甚至出现类别缺失的现象,因此,Tri-training训练过程只适合在聚类中心初始化前辅助扩大seeds集规模.为弥补Tri-training过程中不可避免的误标记所导致的seeds集噪声增大和类别缺失这样的负面影响,本文同时考虑将基于最近邻规则的数据剪辑技术结合到Tri-training对seeds集规模的扩大过程中,进行消噪、修正误标记等净化操作,以提高seeds集质量,为聚类提供大规模、低噪声的seeds集.
本文第1节简单介绍Seeded-K-均值和Constrained-K-均值两种基于seeds集的半监督聚类算法.第2节阐述用Tri-training扩大seeds集过程和Depuration数据剪辑技术净化seeds集操作,提出基于Tri-training和Depuration数据剪辑的DE-Tri-training半监督K-均值聚类算法,并给出时间复杂度分析.第3节通过实验对算法进行性能测试并对结果进行比较分析.第4节对本文工作进行总结与展望.
1 Seeded-K-均值和Constrained-K-均值算法
MacQueen[19]提出的K-均值算法是著名的无监督聚类算法.它随机初始化k个聚类中心,按距离测度分配数据点到最近的聚类中心,使数据集聚类中心迭代地更新,直至不再变化.最终聚类结果是局部最小化式(1)所示的数据点到聚类中心距离平方和的目标函数.
邓超 等:基于Tri-Training 和数据剪辑的半监督聚类算法
665 21||||i h k
KMeans i h h x X J x μ=∈=?∑∑ (1)
其中,1{}n i i x =是数据集,1{}k
h h X =是k 个聚类,1{}k h h μ=是k 个聚类中心.
与K-均值算法随机初始化k 个聚类中心不同,Basu 等人[8]提出的Seeded-K-均值和Constrained-K-均值算法用少量带标记的数据作seeds 集,并按标记将seeds 集划分为k 个聚类,由此计算k 个聚类初始中心.另外,在数据点分配过程中,Constrained-K-均值算法还强制约束seeds 集中数据点所属聚类不变,只对无标记数据点重新分配.
Basu 通过实验表明[4]:当无噪声seeds 集所占比例增大时,两种算法的性能都显著提高;相反地,当seeds 集中噪声比例增大时,Constrained-K-均值性能显著降低.尽管Seeded-K-均值分配数据点时不受seeds 集中初始标记的约束,因而相对于Constrained-K-均值抗噪性稍强,但与无噪声时的Seeded-K-均值相比,性能下降仍十分显著. 2 基于Tri -Training 和数据剪辑的半监督聚类算法
Seeded-K-均值与Constrained-K-均值算法的性能受seeds 集规模和质量的影响显著,如果能在增大seeds 集规模的同时提高seeds 集质量,则其性能的提高也将十分显著.为此,在初始化聚类中心之前,本文利用Tri-training 的迭代训练过程增大seeds 集规模,同时,对扩大的seeds 集进行Depuration 数据剪辑,以提高seeds 集质量.
2.1 Tri -Training 扩大Seeds 集
Tri-Training 分类算法的详细伪代码见文献[17],本文借鉴Tri-training 执行的Co-training 式训练过程来实现seeds 集扩大:假设初始少量带标记的数据集为L (即初始seeds 集),由L 训练得到3个不同分类器H 1,H 2,H 3,x 是无标记数据集U 内任意一点,如果H 2和H 3对x 的分类结果H 2(x )和H 3(x )一致,那么,可将x 标记为H 2(x )并加入
H 1的训练集,如此形成H 1的新训练集1
23{|()()}S L x x U H x H x ′=∪∈=且.类似地,H 2和H 3的训练集分别扩充为2
S ′和3S ′,然后,3个分类器重新训练,如此重复迭代,直至H 1,H 2,H 3都没有变化,训练过程结束.Tri-training 训练过 程中,3个分类器相应训练集的迭代扩充过程就是实现初始seeds 集逐步扩大的过程.本文的算法正是以训练结
束时3个分类器相应训练集的并集1
23S S S ′′′∪∪作为扩充后的seeds 集,为初始化聚类中心做准备. 显然,seeds 集扩大过程中,H 2和H 3共同标记x 为H 2(x ).给H 1作训练数据时,如果准确性足够高,会优化H 1的训练结果;否则,会在H 1的训练集中加入噪声,影响训练效果.为此,Zhou 等人[17]证明:在PAC 可学习框架下,如果新标记的训练样本足够多且式(2)定义的约束条件满足,则H 1重新训练所得假设的分类性能会迭代提高. 111111||||||||||12||12||||t t t t t t L L t t ηL e L ηL e L L L L L L L L L ????????++∪?>∪?????∪∪????
(2) 其中,L t 是第t 次迭代H 2和H 3为H 1新标记的训练集,1t e
是H 2和H 3第t 次迭代的错误率上限,ηL 是初始训练集L 的噪声率.ηL 通常很小,假定111005t t -e
,e .≤< ,则当|L t |>|L t ?1|时,由公式(2)可推出1111||||t t t t e L e L ??< ,即等价于公 式(3): 1111||01||t t t t e L e
L ??<<< (3) 其中,1t e
和11t e ? 可用H 2和H 3在初始带标记数据集L 上的错误率近似.在Tri-training 训练过程中,用公式(3)来判断由H 2和H 3给出相同标记的数据点x 组成的数据集1t L 是否应该被加入到H 1的新训练集中.
2.2 Depuration 剪辑seeds 集
如上所述,我们可以用Tri-training 训练过程对无标记数据作标记,实现seeds 集的扩充.尽管有约束条件保证各分类器在新标记训练样本足够大时分类精度迭代提高,但实际应用中,初始带标记数据集规模很小,不足以训练出高精度分类器,所以,Tri-training 训练过程中误标记相当数量的数据是难免的,这使得在进行下次迭代时,
666 Journal of Software 软件学报 V ol.19, No.3, March 2008 另一个分类器的训练集包含许多噪声[20].如果迭代过程中(尤其迭代的早期)能够找到这些误标记数据并修剪,seeds 集质量会得到提高,算法会有更好的聚类效果.各种数据剪辑技术能够有效地改善训练集的质量,本文在Tri-training 迭代训练中结合了数据剪辑技术,在每个分类器获得新的训练集,在重新训练之前对新训练集进行数据剪辑操作.如此改进的Tri-training 训练过程称为带数据剪辑的Tri-training,为方便起见,记作DE-Tri-training.
考虑到K-均值聚类算法“最小化类内距离”[4]的目标与最近邻规则的思想一致,所以将最近邻规则下的数据剪辑技术用于聚类算法中seeds 集的精化是合理的.基于最近邻规则的Depuration 技术是第1种应用原型选
择策略的剪辑技术,它从有标记数据集中移除“可疑”数据并修改其他数据的误标记,达到消除训练集噪声、
误标记和偏离数据的目的[21].具体操作为:按最近邻规则选取一个数据的k 个近邻,观察其中是否有k ′个近邻标记相同,以决定移除数据或修改标记.k 和k ′按generalised editing 规定的条件(k +1)/2≤k ′≤k 给定.文献[21]指出,当k 和k ′设为3和2时,Depuration 实际效果最好.本文的算法采用这个设定.
2.3 基于Tri -Training 和数据剪辑的DE -Tri -Training 半监督K -均值算法
图1是新的半监督聚类算法在初始化聚类中心前,由DE-Tri-training 训练过程对初始少量带标记数据集经过扩充和数据剪辑形成大规模、低噪声seeds 集的详细过程.seeds 集规模的扩充通过DE-Tri-training 迭代训练过程对无标记数据不断标记,形成新的训练集来实现.逐步扩大的seeds 集中噪声和误标记数据的剪辑操作分布在两个阶段:第1阶段是DE-Tri-training 训练过程每次迭代标记后,对新训练集的Depuration 数据剪辑操作,主要消除误分类引起的噪声,同时,对初始seeds 集中可能存在的误标记和偏离数据也能起到净化作用;第2阶段是在训练结束时,DE-Tri-training 所得联合分类器{H 1,H 2,H 3}对训练集的并集重新分类标记后进行的Depuration 数据剪辑操作.这样,在联合分类器对seeds 集重新标记的基础上进一步消除噪声和误标记,提高用于聚类中心初始化的seeds 集质量.
Fig.1 The process of enlargement and data editing on seeds set
图1 Seeds 集的扩充和数据剪辑过程
算法. 基于Tri-training 和数据剪辑的DE-Tri-training 半监督K-均值聚类算法.
输入:数据集1{}n i i X x ==,x i ∈?d ,聚类数目k ,带标记seeds 集1k
h h S S ==∪(S h 非空),数据点所属聚类的重新分配
方式(seeded 方式或constrained 方式),未训练的分类器H 1,H 2,H 3;
输出:数据集X 上k 个不相交的聚类划分1{}k
h h X =.
Step 1. DE-Tri-training 训练过程对S 迭代扩充、剪辑
(a) L ←S ,U ←X ?L ;对L 进行Bootstrap 采样,产生3个训练集1S ′,2
S ′,3S ′分别训练H 1,H 2,H 3. (b) 对每个H i (i =1,2,3),从无标记数据集U 中由H j 和H k (j ,k ≠i )选择满足式(3)判别条件的子集
邓超 等:基于Tri-Training 和数据剪辑的半监督聚类算法
667
L i ={x |x ∈U 且H j (x )=H k (x )}进行标记,并生成H i 新训练集i i S L L ′=∪. (c) 对每个i S ′中的新标记数据子集L i 进行Depuration 数据剪辑操作:
i S S ′′←; 遍历考察非空L i 中每个新标记元素x ,在{}i S x ′?中找到x 的3个最近邻点.如果某个标记c 在x 的3个最近邻点中至少出现2次,就把S ′中的x 标记为c ;否则,如果不存在这样的标记c ,就从S ′移除x ;
i S S ′′←.
(d) 对每个H i (i =1,2,3),若||||i S S ′′>,则用i S ′重新训练.
(e) 如果H 1,H 2,H 3中至少有1个发生变化,则转(b).
(f) 1
23S S S S ′′′←∪∪;训练所得联合分类器{H 1,H 2,H 3}按加权投票规则对S 中新标记数据重新分类标记. (g) 对S 中由{H 1,H 2,H 3}重新标记的数据子集进行Depuration 数据剪辑操作.
Step 2. 初始化k
个聚类中心 将扩充的seeds 集S 中数据点按标记划分为k 个聚类(即1k
h h S S ==∪,S h 非空),并计算k 个聚类初始 中心1||h
h x S h x S μ∈=∑,h =1,...,k . Step 3. 重新分配数据点
若是Seeded 方式,则X 中每个数据点x 都重新分配到距离最近的聚类中;
若是Constrained 方式,对X 中每个数据点x ,如果x ∈S h ,就保留分配到聚类X h ;否则,分配到最近的
聚类
Step 4. 重新计算聚类中心:1||h
h x X h x X μ∈=∑,h =1,…,k . Step 5. 如果k 个聚类中心都未改变,则算法结束;否则,转Step 3.
需要指出的是,为保证由初始数据集L 训练得到3个不同的分类器,算法Step 1(a)步沿用文献[17]采用的Bootstrap 采样技术.在文献[17]中,Tri-training 训练结束对新数据分类时,训练所得联合分类器{H 1,H 2,H 3}采用多数投票规则.考虑到实际聚类数目通常大于2,新算法中DE-Tri-training 训练所得联合分类器采用式(4)所示加权投票规则进行类别标记(算法Step 1(f)),权重由3个分类器在初始带标记数据集L 上的分类准确率A i (L )所决定. 3
1
{1,2,3}31(,())()()arg max ()
i i i c label i i c H x A L H x A L δ=∈=×=∑∑ (4) 其中,1, ()(,())0, (
)i i i H x c c H x H x c δ=?=?≠?. 另外,为便于考察新算法中Tri-training 和Depuration 的作用,本文考虑初始seeds 集无噪声的情况,所以,算法Step 1(c)和Step 1(g)只对新标记的数据子集进行Depuration 数据剪辑操作.
2.4 算法复杂性分析
算法Step 1(a)对基分类器训练若采用基于迭代的学习算法(如神经网络)则可设定初始带标记数据集L 上 的分类错误率阈值为迭代结束条件;Step 1(e)Tri-training 迭代可以新训练集i S ′不再变化为结束条件;Step 5聚 类迭代则可用相应聚类中心的距离误差阈值作为结束条件.
假设数据集规模为n ,维数为d ,新算法时间复杂度主要包括两个阶段的时间代价.第1阶段,DE-Tri-training 对初始seeds 集扩大和剪辑共m 1次迭代,时间代价为O (m 1×[2×T c (H ;n ?|L |)+|L t |×(|L |+|L t |)×d +T t (H ;|L |+|L t |)]),其中, T c (H ;n ?|L |)是分类器对无标记数据标记的代价,T t (H ;|L |+|L t |)是用新标记训练集重新训练分类器的代价,二者都由具体选用的分类器H 所决定,|L t |×(|L |+|L t |)×d 是Depuration 按最近邻规则对新标记数据集L t 剪辑的代价.因此,第1阶段最坏情况下,(|L |→0;|L t |→n )代价为O (m 1×(T c (H ;n )+T t (H ;n )+dn 2)).第2阶段进行半监督K-均值聚类的代价主要集中在重新分配数据点和重新计算聚类中心的m 2次迭代过程上,代价为O (m 2×kdn ).所以,算法最坏情况
668 Journal of Software软件学报 V ol.19, No.3, March 2008 下的时间复杂度为max{O(m1×T c(H;n)),O(m1×T t(H;n)),O(m1×dn2),O(m2×kdn)}.
3 实验分析
本文采用UCI机器学习数据库[22]中的6个数据集进行实验,测试新算法的聚类性能,表1列出了这些数据集的信息,其中,Letters数据子集是从手写字符集中随机抽取{I,J,L}这3个最难识别字符的10%所组成.类似地,Digits数据子集是从{3,8,9}中随机抽取10%所组成.Image segmentation中1个常数属性对聚类过程帮助不大,所以被删除.本文实验数据集、程序和实验过程详细记录可从https://www.doczj.com/doc/7f15136013.html,/dc.html获得.
Table 1Information of UCI datasets in the experiments
表1实验所用UCI数据集
Data set No. of instances No. of attributes No. of classes
Wine 178 13 3
Letters 227 16 3
Digits 318 16 3
Ionosphere 351 34 2
Image segmentation 2310 18 7
为便于比较,我们测试随机初始化的K-均值算法、Seeded-K-均值算法、Constrained-K-均值算法及本文提出的DE-Tri-training半监督K-均值算法(DE-Tri-training Seeded-K-均值和DE-Tri-training Constrained-K-均值).为明确分析Tri-training和数据剪辑的作用,对只用Tri-training而无数据剪辑的半监督K-均值算法(Tri-training Seeded-K-均值和Tri-training Constrained-K-均值)也进行了实验比较.
聚类性能评价采用目前广泛使用的正则化互信息(normalized mutual information,简称NMI)指标[2,4,23].NMI 可确定聚类算法在测试集上的类别标记结果与实际结果之间的共有信息量,NMI越大,则聚类效果越好.NMI定义方式有多种,本文中NMI计算采用文献[23]给出的定义.
每个数据集上不同聚类算法的学习曲线和相应seeds集规模的比较如图2~图5所示,曲线上每个点是每种算法独立运行10次10-folds交叉验证的结果.具体方案为:数据集等分为10个fold,每次取1个fold作测试集(整个数据集的10%),其余9个fold(占90%)按预定的比例划分为有标记seeds集和无标记数据子集(子集中不同类别数据的比例与整个数据集中比例一致),然后运行被测算法,10个fold依次被选作测试集,相应10个结果的平均值作为一次10-folds交叉验证结果.如此独立运行10次10-folds交叉验证实验,取平均值作为学习曲线上的一点.每种聚类算法都是在整个数据集上运行,但只在测试集上计算NMI值.
在Tri-training中,3个分类器H1,H2,H3采用3层BP神经网络(BPNN).K-均值聚类和Depuration数据剪辑中距离测度均采用欧氏距离,最大迭代步数为200,误差停止阈值为1e?5.实验分为两组:第1组主要考察Tri-training的作用,在Tri-training训练过程中为每个BPNN分类器设定充足的训练迭代次数,以保证当初始seeds集的比例为0.1时,Tri-training训练所得联合分类器中至少有两个分类器对初始seeds集的分类准确率大于0.9;第2组主要考察Depuration的作用,每个BPNN分类器训练次数不足,当初始seeds集的比例为0.1时,联合分类器中至少有1个分类器对初始seeds集的分类准确率小于0.7.
3.1 BPNN分类器训练充分时Tri-training作用的分析
第1组实验,6个数据集上7种不同聚类算法的NMI学习曲线的比较如图2所示.图中Constrained-K-均值和Seeded-K-均值优于Random K-均值,这与文献[4]的结果基本一致,但所有Seeded模式的K-均值算法比Constrained模式要差,这可由文献[2]中的结果来解释.本文算法相关的DE-Tri-training Constrained-K-均值和Tri-training Constrained-K-均值的NMI曲线明显优于Random K-均值、Seeded-K-均值和Constrained-K-均值,这是因为每个BPNN分类器泛化能力得到保证时,seeds集的规模扩大且Tri-training训练过程标记新数据和联合分类器重新标记seeds集的高准确率都保证了用于聚类中心初始化的seeds集是大规模低噪声的.
邓超 等:基于Tri-Training 和数据剪辑的半监督聚类算法
669
(a) Iris: 8 nodes in hidden layer, 500 iterations, (b) Wine: 8 nodes in hidden layer, 300 iterations,
learning rate=0.1 learning rate=0.1
(a) Iris: 隐层结点8个,迭代次数500次,学习速率=0.1 (b) Wine: 隐层结点8个,迭代次数300次,学习速率=0.1
(c) Letters: 8 nodes in hidden layer, 300 iterations, (d) Digits: 10 nodes in hidden layer, 300 iterations,
learning rate=0.1 learning rate=0.1
(c) Letters: 隐层结点8个,迭代次数300次,学习速率=0.1 (d) Digits: 隐层结点10个,迭代次数300次,学习速率=0.1
(e) Ionosphere: 12 nodes in hidden layer, 500 iterations, (f) Image segmentation: 12 nodes in hidden layer,
learning rate=0.1 1000 iterations, learning rate=0.3
(e) Ionosphere: 隐层结点12个,迭代次数500次,学习速率=0.1 (f) Image segmentation: 隐层结点12个,迭代次数1000次, 学习速率=0.3
Fig.2 NMI comparison on six datasets when BPNN trained sufficiently
图2 BPNN 分类器训练充分时6个数据集上NMI 的比较
0.900.850.800.750.700.950 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9Fraction of initial labeled seeds in all data N M I
Random
Tri-Training seeded
Constrained
DE-Tri-Training constrained Seeded
DE-Tri-Training seeded
Tri-Training constrained 0.900.850.800.750.700.650.600.550.500.450.950 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Fraction of initial labeled seeds in all data
N M I
Random Tri-Training seeded Constrained DE-Tri-Training constrained Seeded DE-Tri-Training seeded
Tri-Training constrained 0.80.70.60.50.40.30.20.90 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9Fraction of initial labeled seeds in all data N M I
Random Tri-Training seeded Constrained DE-Tri-Training constrained Seeded DE-Tri-Training seeded
Tri-Training constrained 0.950.900.850.800.750.700.650.600.550.501.000 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Fraction of initial labeled seeds in all data N M I
Random Tri-Training seeded Constrained
DE-Tri-Training constrained Seeded
DE-Tri-Training seeded
Tri-Training constrained 0.60.50.40.30.20.10.70 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.80.9Fraction of initial labeled seeds in all data N M I
Random
Tri-Training seeded
Constrained
DE-Tri-Training constrained Seeded
DE-Tri-Training seeded
Tri-Training constrained 0.850.800.750.700.650.600.550.500.900 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Fraction of initial labeled seeds in all data N M I
Random Tri-Training seeded Constrained DE-Tri-Training constrained Seeded DE-Tri-Training seeded
Tri-Training constrained
670
Journal of Software 软件学报 V ol.19, No.3, March 2008
图3(a)和图3(b)是Iris 和Digits 数据集上3种模式算法用于聚类中心初始化的最终seeds 集规模的比较.显然,Tri-training 模式和DE-Tri-training 模式的算法中,Tri-training 训练过程对seeds 集规模的扩大有十分显著的作用.
(a) Iris: 8 nodes in hidden layer, 500 iterations, learning rate=0.1 (b) Digits: 10 nodes in hidden layer, 300 iterations, learning rate=0.1
(Corresponding to NMI curves in Fig.2(a)) (Corresponding to NMI curves in Fig.2(d))
(a) Iris: 隐层结点8个,迭代次数500次,学习速率=0.1 (b) Digits: 隐层结点10个,迭代次数300次,学习速率=0.1 (对应图2(a)中NMI 曲线) (对应图2(d)中NMI 曲线) Fig.3 Size comparison of final seeds used to cluster centroids initialization when BPNN trained sufficiently
图3 BPNN 分类器训练充分时用于聚类中心初始化的seeds 集规模的比较
此外我们发现,在Wine,Ionosphere 以及Iris(初始seeds 集比例大于0.5后)3个数据集上,Tri-training Constrained-K-均值优于DE-Tri-training Constrained-K-均值,这说明每个分类器训练充分时Tri-training 的作用大于Depuration.然而,图2(a)Iiris 数据集上的NMI 学习曲线表明,当初始seeds 集比例小于0.1时,无数据剪辑的Tri-training Constrained-K-均值的NMI 值不仅低于带数据剪辑的DE-Tri-training Constrained-K-均值,而且低于Constrained-K-均值.随着初始seeds 集比例的增大,Tri-training Constrained-K 均值由于训练样本增大使新样本的标记准确性提高,所以NMI 值迅速超过Constrained-K-均值,但与DE-Tri-training Constrained-K-均值相比,由于后者的Depuration 对seeds 集不断剪辑,在规模增大的同时又保证了质量的提高,因而直至初始seeds 集比例达0.55时,后者性能一直优于前者;但初始seeds 集比例大于0.55后,前者由于训练集充分而保证新标记数据集准确性大幅度提高,后者由于Depuration 固有的误差率使性能趋于稳定,但即使前者在0.9时达到的NMI 最大值也仅与后者在0.4时就已达到的最大值相当,这说明在Iris 数据集上DE-Tri-training Constrained-K-均值用相对小的初始带标记seeds 集就能获得较好的聚类性能.
3.2 BPNN 分类器训练不充分时Depuration 作用分析
图4、图5是第2组实验,由于训练不充分,使Tri-training 训练过程标记新数据准确率降低时,Iris 和Digits 两个典型数据集上7种算法的性能比较.与图3(a)和图3(b)相比,图4(a)和图4(b)表明,Tri-training 模式和DE-Tri-training 模式中seeds 集规模的扩大程度受到极大影响,尤其当初始seeds 集比例小时扩大规模明显降低.
(a) Iris: 8 nodes in hidden layer, 50 iterations, learning rate=0.1 (b) Digits: 10 nodes in hidden layer, 20 iterations, learning rate=0.1
(Corresponding to NMI curves in Fig.5(a)) (Corresponding to NMI curves in Fig.5(b))
(a) Iris: 隐层结点8个,迭代次数50次,学习速率=0.1 (b) Digits: 隐层结点10个,迭代次数20次,学习速率=0.1 (对应图5(a)中NMI 曲线) (对应图5(b)中NMI 曲线)
Fig.4 Size comparison of final seeds used to cluster centroids initialization when BPNN trained insufficiently
图4 BPNN 分类器训练不充分时用于聚类中心初始化的seeds 集规模的比较
Constrained/Seeded
Tri-Training mode S i z e o f f i n a l s e e d s Fraction of initial labeled seeds in all data
S i z e o f f i n a l s e e d s
Fraction of initial labeled seeds in all data
S i z e o f f i n a l s e e d s
Fraction of initial labeled seeds in all data S i z e o f f i n a l s e e d s Fraction of initial labeled seeds in all data
邓超 等:基于Tri-Training 和数据剪辑的半监督聚类算法
671
图5(a)表明,无数据剪辑的Tri-training Constrained-K-均值和Tri-training Seeded-K-均值在初始seeds 集比例小于0.3时,性能远差于其他所有算法,即使初始比例增至0.9,NMI 值都一直小于Constrained-K-均值;而在带数据剪辑的DE-Tri-training Constrained-K-均值和DE-Tri-training Seeded-K-均值中,Depuration 数据剪辑操作能够对误标记引起的噪声数据加以纠正,有效弥补了训练不充分带来的负面影响,在初始seeds 集比例小于0.2时,其性能就远好于无数据剪辑的算法,并接近Constrained-K-均值和Seeded-K-均值的性能,尤其是DE-Tri-training Constrained-K-均值从初始比例大于0.2时,NMI 值就一直大于Constrained-K-均值.同样,图5(b)表明,Digits 上初始seeds 集比例小时,DE-Tri-training Constrained-K-均值和DE-Tri-training Seeded-K-均值的优势更明显.因而,该组实验进一步证明了新算法中Depuration 操作对增大的seeds 集所含噪声进行有效净化的关键作用.
(a) Iris: 8 nodes in hidden layer, 50 iterations, learning rate=0.1 (b) Digits: 10 nodes in hidden layer, 20 iterations, learning rate=0.1 (a) Iris: 隐层结点8个,迭代次数50次,学习速率=0.1 (b) Digits: 隐层结点10个,迭代次数20次,学习速率=0.1
Fig.5 NMI comparison on two typical datasets when BPNN trained insufficiently
图5 BPNN 分类器训练不充分时2个典型数据集上NMI 的比较
3.3 纵向比较分析
纵向比较两组实验而发现,第1组中Tri-training 模式与DE-Tri-training 模式算法性能的差异程度远不如第2组显著.由图4(a)和图4(b)可以看出,最终seeds 集规模的差异并不是造成第2组中二者性能明显差异的主要原因,而应该是seeds 集质量的差异.第2组各分类器训练不充分时,互标记准确率低,Tri-training 迭代出现严重误标记传播现象.尽管DE-Tri-training 可通过剪辑操作减少误标记噪声降低误标记传播,但与第1组训练充分时Tri-training 模式性能的差距仍十分明显,这说明提高Tri-training 中各分类器标记精度是避免误标记数据传播的关键.
两组实验中,Constrained-K-均值性能曲线表明,在保证seeds 集质量的前提下,聚类性能随着seeds 数量的增加而提高.新算法中,seeds 集质量由Tri-training 中各分类器互标记准确率保证.当标记准确率低时,Depuration 剪辑可辅助提高seeds 集质量.在实际应用中,seeds 集质量可通过Tri-training 当前迭代所得联合分类器对初始seeds 集L 的标记准确率进行评价,当seeds 集数量增大但Tri-training 在L 上出现过拟合情形时,即可认为种子数量达到平衡.
如前所述,新算法假定初始seeds 集无噪声,便于考察Depuration 对Tri-training 迭代扩大seeds 集时所产生误标记噪声的有效净化作用.实际应用中考虑初始seeds 集噪声,依据文献[21]中Depuration 能够获得高质量训练集的结论,可在Step 1用DE-Tri-training 扩充、剪辑seeds 集之前,先用Depuration 剪辑操作对初始seeds 集消噪
.
Fraction of initial labeled seeds in all data N M I
Random Tri-Training seeded Constrained DE-Tri-Training constrained Seeded
DE-Tri-Training seeded
N M I Random Tri-Training seeded Constrained DE-Tri-Training constrained Seeded
672 Journal of Software软件学报 V ol.19, No.3, March 2008 4 结论与展望
本文提出了基于Tri-training和数据剪辑的DE-Tri-training半监督K均值聚类算法.实验结果表明,在聚类中心初始化之前,新算法能够有效利用带数据剪辑的Tri-training训练过程,对无标记数据标记,并对噪声数据剪辑,使得seeds集规模迭代增大的同时质量有所提高,最终达到改善聚类性能的效果.
相比其他基于约束条件的半监督聚类典型算法,如COP-K-均值算法和利用遗传算法优化含约束条件K-均值聚类目标函数的算法而言,新算法通过获取大规模低噪声seeds集,有效地弥补了因随机初始化聚类中心而易陷入局部极优的不足;此外,对不可避免的噪声标记,COP-K-均值算法会因噪声数据引起约束条件不一致而聚类失败,新算法则通过Depuration对噪声数据剪辑而具有更好的鲁棒性和聚类性能.
实验结果启示我们,对DE-Tri-training半监督K.均值算法中Depuration数据剪辑误差率和Tri-training训练过程中新数据标记准确率这两个指标间的关系进行理论分析,确定不同情形下Depuration的最佳启动时机,应是今后新算法的重要研究方向.
值得注意的是,这种从少量带标记数据出发,用半监督分类方法对无标记数据进行标记,增大聚类所需的监督信息,同时结合数据剪辑技术提高监督信息质量的思想,可推广到对其他半监督聚类算法的改进.但是,仍有许多重要问题需要解决,比如数据剪辑技术应如何选择、当监督信息不是类别标记而是其他约束条件形式(如数据间must- link和cannot-link连接关系)时如何实现数据剪辑操作,都需要深入的研究和探讨.
References:
[1] Olivier C, Bernhard S, Alexander Z. Semi-Supervised Learning. Cambridge: MIT Press, 2006.
[2] Zhong S. Semi-Supervised model-based document clustering: A comparative study. Machine Learning, 2006,65(1):3?29.
[3] Bilenko M, Basu S, Mooney RJ. Integrating constraints and metric learning in semi-supervised clustering. In: Carla EB, ed. Proc.
of the 21st Int’l Conf. on Machine Learning (ICML 2004). Banff: ACM Press, 2004. 81?88.
[4] Basu S. Semi-Supervised clustering: Probabilistic models, algorithms and experiments [Ph.D. Thesis]. Austin: University of Texas
at Austin, 2005.
[5] Demiriz A, Bennett KP, Embrechts MJ. Semi-Supervised clustering using genetic algorithms. In: Dagli CH, ed. Proc. of the
Intelligent Engineering Systems Through Artificial Neural Networks 9 (ANNIE’99). New York: ASME Press, 1999. 809?814.
[6] Wagstaff K, Cardie C, Rogers S, Schroedl S. Constrained K-means clustering with background knowledge. In: Carla EB, Andrea
PD, eds. Proc. of the 18th Int’l Conf. on Machine Learning (ICML 2001). San Fransisco: Morgan Kaufmann Publishers, 2001.
577?584.
[7] Basu S, Bilenko M, Mooney RJ. A probabilistic framework for semi-supervised clustering. In: Won K, Ron K, Johannes G,
William D, eds. Proc. of the 10th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining (KDD 2004). Seattle: ACM Press, 2004. 59?68.
[8] Basu S, Banerjee A, Mooney RJ. Semi-Supervised clustering by seeding. In: Claude S, Achim GH, eds. Proc. of the 19th Int’l Conf.
on Machine Learning (ICML 2002). San Fransisco: Morgan Kaufmann Publishers, 2002. 19?26.
[9] Seeger M. Learning with labeled and unlabeled data. Technical Report, Edinburgh: University of Edinburgh, 2002.
[10] Nigam K, McCallum AK, Thrun S, Mitchell T. Text classification from labeled and unlabeled documents using EM. Machine
Learning, 2000,39(2-3):103?134.
[11] Ghahramani Z, Jordan MI. Supervised learning from incomplete data via an EM approach. In: Jack DC, Gerald T, Joshua A, eds.
Proc. of the Advances in Neural Information Processing Systems Vol.6 for the 7th NIPS Conf. Denver: Morgan Kaufmann Publishers, 1994. 120?127.
[12] Miller DJ, Browning J. A mixture model and EM-based algorithm for class discovery, robust classification, and outlier rejection in
mixed labeled/unlabeled data sets. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2003,25(11):1468?1483.
[13] Joachims T. Transductive inference for text classification using support vector machines. In: Ivan B, Saso D, eds. Proc. of the 16th
Int’l Conf. on Machine Learning (ICML’99). San Fransisco: Morgan Kaufmann Publishers, 1999. 200?209.
邓超等:基于Tri-Training和数据剪辑的半监督聚类算法673
[14] Blum A, Lafferty J, Rwebangira M, Reddy R. Semi-Supervised learning using randomized mincuts. In: Carla EB, ed. Proc. of the
21st Int’l Conf. on Machine Learning (ICML 2004). Banff: ACM Press, 2004. 934?947.
[15] Blum A, Mitchell T. Combining labeled and unlabeled data with co-training. In: Peter B, Yishay M, eds. Proc. of the 11th Annual
Conf. on Computational Learning theory (COLT’98).Madison: ACM Press, 1998. 92?100.
[16] Goldman S, Zhou Y. Enhancing supervised learning with unlabeled data. In: Pat L, ed. Proc. of the 17th Int’l Conf. on Machine
Learning (ICML 2000). San Francisco: Morgan Kaufmann Publishers, 2000. 327?334.
[17] Zhou ZH, Li M. Tri-Training: Exploiting unlabeled data using three classifiers. IEEE Trans. on Knowledge and Data Engineering,
2005,17(11):1529?1541.
[18] Bouchachia A, Pedrycz W. Data clustering with partial supervision. Data Mining and Knowledge Discovery, 2006,12(1):47?78.
[19] MacQueen J. Some methods for classification and analysis of multivariate observations. In: Le L, Neyman J, eds. Proc. of the 5th
Berkeley Symp. on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967. 281?297.
[20] Li M, Zhou ZH. SETRED: Self-Training with editing. In: Proc. of the Advances in Knowledge Discovery and Data Mining
(PAKDD 2005). LNAI 3518, Heidelberg: Springer-Verlag, 2005. 611?621.
[21] Sánchez JS, Barandela R, Marqués AI, Alejo R, Badenas J. Analysis of new techniques to obtain quality training sets. Pattern
Recognition Letters, 2003,24(7):1015?1022.
[22] Blake C, Keogh E, Merz CJ. UCI repository of machine learning databases. Irvine: University of California, 1998. http://www.ics.
https://www.doczj.com/doc/7f15136013.html,/~mlearn/MLRepository.html
[23] Strehl A, Ghosh J, Mooney R. Impact of similarity measures on Web-page clustering. In: Proc. of the AAAI on Workshop on
Artificial Intelligence for Web Search (AAAI 2000). Menlo Park: AAAI Press/MIT Press, 2000. 58?64.
邓超(1978－),男,山西长治人,博士生,主要研究领域为机器学习,数据挖掘.
郭茂祖(1966－),男,博士,教授,博士生导师,主要研究领域为机器学习与数据挖掘,计算生物学与生物信息学.
本文在阐述聚类分析方法的基础上重点研究FCM 聚类算法。FCM 算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。 第 1 章概述 聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚” 。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。 为获得基于划分聚类分析的全局最优结果，则需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid 算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。 而模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dunn [10] 首先将其推广到加权WGSS 函数，后来由Bezdek 扩展到加权WGSS 的无限族，形成了FCM 聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。 第 2 章聚类分析方法 2-1 聚类分析 聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：①类内相似性：属于同一类的数据应尽可能相似。②类间相异性：属于不同类的数据应尽可能相异。图2.1是一个简单聚类分析的例子。
数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现 系别： 专业： 学号： 姓名： 指导教师： 时间：
毕业论文（设计）开题报告 系别:计算机与信息科学系专业:网络工程 学号姓名高华荣 论文（设计）题目PAM聚类算法的分析与实现 命题来源□√教师命题□学生自主命题□教师课题 选题意义(不少于300字): 随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。 在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。 在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。 研究综述(前人的研究现状及进展情况，不少于600字): PAM（Partitioning Around Medoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。 由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（Cluster LARger Application）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（Cluster Larger Application based upon RANdomized
Density-Based Clustering for Real-Time Stream Data 基于密度的实时数据流聚类(D-Stream) 翻译by muyefei E-mail: muyefei@https://www.doczj.com/doc/7f15136013.html, 注释：版权归作者所有，文档仅用于交流学习，可以用大纲视图查看文档结构 摘要：现有的聚类算法比如CluStream是基于k-means算法的。这些算法不能够发现任意形状的簇以及不能处理离群点。而且，它需要预先知道k值和用户指定的时间窗口。为了解决上述问题，本文提出了D-Stream算法，它是基于密度的算法。这个算法用一个在线部分将数据映射到一个网格，在离线部分计算网格的密度然后基于密度形成簇。算法采用了密度衰减技术来捕获数据流的动态变化。为了探索衰减因子、数据密度以及簇结构之间的关系，我们的算法能够有效的并且有效率地实时调整簇。而且，我们用理论证明了移除那些属于离群点的稀疏网格是合理的，从而提高了系统的时间和空间效率。该技术能聚类高速的数据流而不损失聚类质量。实验结果表明我们的算法在聚类质量和效率是有独特的优势，并且能够发现任意形状的簇，以及能准确地识别实时数据流的演化行为。 关键词 流数据挖掘基于密度的聚类D-Stream 分散的网格 1 介绍 实时聚类高维数据流是困难的但很重要。因为它在各个领域应用到。比如... 聚类是一项关键的数据挖掘任务。挖掘数据流有几项关键的挑战： （1）单遍扫描 （2）将数据流视为数据一个很长的向量在很多应用中捉襟见肘，用户更加关注簇的演化行为。 近来，出现了许多数据流聚类方法。比如STREAM、CluStream以及扩展（在多数据流，分布式数据流，并行数据流上的扩展）等。 CluStream以及扩展的算法有以下一些缺陷： 1、只能发现球形簇，不能发现任意形状的簇。 2、不能够识别噪声和离群点。 3、基于k-means的算法需要多次扫描数据（其实CluStream利用两阶段方法和微簇解决了该问题）。 基于密度的聚类算法介绍。基于密度的方法可以发现任意形状的簇，可以处理噪声，对原始数据集只需一次扫描。而且，它不需要像k-means算法那样预先设定k值。 文本提出了D-Stream,一种基于密度的数据流聚类框架。它不是简单用基于密度的算法替代k-means的数据流算法。它有两项主要的技术挑战： 首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减
3)国家自然科学基金(60172012)。刘青宝 博士生,副教授,主要研究方向为数据仓库技术和数据挖掘;戴超凡 博士,副教授,主要研究方向为数据仓库技术和数据挖掘;邓 苏 博士,教授,主要研究方向指挥自动化、信息综合处理与辅助决策;张维明 博士生导师,教授,主要研究方向为军事信息系统、信息综合处理与辅助决策。 计算机科学2007Vol 134№13 基于网格的数据流聚类算法3) 刘青宝 戴超凡 邓 苏 张维明 (国防科学技术大学信息系统与管理学院 长沙410073) 摘 要 本文提出的基于网格的数据流聚类算法,克服了算法CluStream 对非球形的聚类效果不好等缺陷,不仅能在 噪声干扰下发现任意形状的类,而且有效地解决了聚类算法参数敏感和聚类结果无法区分密度差异等问题。关键词 聚类,数据流,聚类参数,相对密度 G rid 2based Data Stream Clustering Algorithm L IU Qing 2Bao DA I Chao 2Fan DEN G Su ZHAN G Wei 2Ming (College of Information System and Management ,National University of Defense Technology ,Changsha 410073) Abstract With strong ability for discovering arbitrary shape clusters and handling noise ,grid 2based data stream cluste 2ring algorithm efficiently resolves these problem of being very sensitive to the user 2defined parameters and difficult to distinguish the density distinction of clusters.K eyw ords Clustering ,Data stream ,Clustering parameter ,Relative density 随着计算机和传感器技术的发展和应用,数据流挖掘技术在国内外得到广泛研究。它在网络监控、证券交易分析、电信记录分析等方面有着巨大的应用前景。特别在军事应用中,为了获得及时的战场态势信息,大量使用了各种传感器,对这些传感器数据流的分析处理已显得极为重要。针对数据流数据持续到达,且速度快、规模大等特点,数据流挖掘技术的研究重点是设计高效的单遍数据集扫描算法[12]。数据流聚类问题一直是吸引许多研究者关注的热点问题,已提出多种一次性扫描的方法和算法,如文[1～4]等等,但它们的聚类结果通常是球形的,不能支持对任意形状类的聚类[5]。 本文提出的基于网格的数据流聚类算法,在有限内存条件下,以单遍扫描方式,不仅能在噪声干扰下发现任意形状的类,而且有效地解决了基于绝对密度聚类算法所存在的高密度聚类结果被包含在相连的低密度聚类结果中的问题。 本文第1节简要介绍数据流聚类相关研究,并引出基于网格的数据流聚类算法的思路及其与相关研究的异同;第2节给出基于网格的数据流聚类算法所使用到的基本概念;第3节给出一个完整的基于网格的数据流聚类算法,详细解析算法的执行过程;第4节进行算法性能分析对比;最后总结本文的主要工作和贡献,并指出需要进一步研究和改进的工作。 1 相关研究 在有限内存约束下,一般方法很难对数据流进行任意形状的聚类。第一个增量式聚类挖掘方法是文[6]提出的In 2crementalDBSCAN 算法,它是一个用于数据仓库环境(相对稳定的数据流)的有效聚类算法,可以在有噪声的数据集中发现任意形状的类。但是,它为了形成任意形状的类,必须用类中的所有点来表示,要求获得整个数据流的全局信息,这在内存有限情况下是难以做到的。而且,它采用全局一致的绝对 密度作参数,使得聚类结果对参数值非常敏感,设置的细微不同即可能导致差别很大的聚类结果。 Aggarwal 在2003年提出的一个解决数据流聚类问题的框架CluStream [1]。它使用了两个过程来处理数据流聚类问题:首先,使用一个在线的micro 2cluster 过程对数据流进行初级聚类,并按一定的时间跨度将micro 2cluster 的结果按一种称为pyramid time f rame 的结构储存下来。同时,使用另一个离线的macro 2cluster 过程,根据用户的具体要求对micro 2cluster 聚类的结果进行再分析。但它采用距离作为度量参数,聚类结果通常是球形的,不能支持对任意形状类的聚类。而且,它维护的是micro 2cluster 的聚类特征向量(CF 2x ;CF 1x ;CF 2t ;CF 1t ;n ),这在噪声情况下,会产生干扰误差。 2006年,Feng Cao 等人在文[5]中提出了针对动态进化数据流的DenStream 算法。它相对CluStream 有很大的改进,继承了IncrementalDBSCAN 基于密度的优点,能够支持对有噪声的动态进化(非稳定)的数据流进行任意形状的聚类。但由于采用全局一致的绝对密度作参数,使得聚类结果对参数值非常敏感。同时,与CluStream 算法相比,它只能提供对当前数据流的一种描述,不能反映用户指定时间窗内的流数据的变化情况。 朱蔚恒等在文[13]中提出的基于密度与空间的ACluS 2tream 聚类算法,通过引入有严格空间的意义聚类块,在对数据流进行初步聚类的同时,尽量保留数据的空间特性,有效克服了CluStream 算法不能支持对任意形状聚类的缺陷。但它在处理不属于已有聚类块的新数据点时,使用一种类似“抛硬币”的方法来猜测是否为该点创建一个新的聚类块,误差较大。而且它以绝对密度做参考,所以在聚类结果中无法区分密度等级不同的簇[7]。 本文提出的基于网格的数据流聚类算法GClustream
基于K-means聚类算法的入侵检测系统的设计 基于K-means聚类算法的入侵检测系统的设计 今天给大家讲述的是K-means聚类算法在入侵检测系统中的应用首先，介绍一下 聚类算法 将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的研究，就形成了历史学，有关世界空间地域的研究，则形成了地理学。 又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不同的界、门、纲、目、科、属、种之中。 事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。 通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analysis）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。 （聚类分析我们说得朴实一点叫做多元统计分析，说得时髦一点叫做数据挖掘算法，因为这个算法可以在一堆数据中获取很有用的信息，这就不就是数据挖掘吗，所以大家平时也不要被那些高大上的名词给吓到了，它背后的核心原理大多数我们都是可以略懂一二的，再
比如说现在AI这么火，如果大家还有印象的话，以前我们在大二上学习概率论的时候，我也和大家分享过自然语言处理的数学原理，就是如何让机器人理解我们人类的自然语言，比如说，苹果手机上的Siri系统，当时还让杨帆同学帮我在黑板上写了三句话，其实就是贝叶斯公式+隐含马尔可夫链。估计大家不记得了，扯得有点远了接下来还是回归我们的正题，今天要讨论的聚类算法。） K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，结果稳定，聚类的效果也还不错, 相异度计算 在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。 要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个特征变量来刻画，就比如说我们举一个例证，就有一项比较神奇的技术叫面部识别技术，其实听起来很高大上，它是如何做到的，提取一个人的面部特征，比如说嘴巴的长度，鼻梁的高度，眼睛中心到鼻子的距离，鼻子到嘴巴的距离，这些指标对应得数值可以组成一个向量作为每一个个体的一个标度变量（）,或者说叫做每一个人的一个特征向量。 如果对于一群有待分类的样本点需用p 个特征变量值描述，则每
论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对
数据挖掘考试题 公司内部编号：（GOOD-TMMT-MMUT-UUPTY-UUYY-DTTI-
数据挖掘考试题 一．选择题 1. 当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离( ) A.分类 B.聚类 C.关联分析 D.主成分分析 2. ( )将两个簇的邻近度定义为不同簇的所有点对邻近度的平均值，它是一种凝聚层次聚类技术。 A.MIN(单链) B.MAX(全链) C.组平均 D.Ward方法 3.数据挖掘的经典案例“啤酒与尿布试验”最主要是应用了( )数据挖掘方法。 A 分类 B 预测 C关联规则分析 D聚类 4.关于K均值和DBSCAN的比较，以下说法不正确的是( ) A.K均值丢弃被它识别为噪声的对象，而DBSCAN一般聚类所有对象。 B.K均值使用簇的基于原型的概念，DBSCAN使用基于密度的概念。 C.K均值很难处理非球形的簇和不同大小的簇，DBSCAN可以处理不同大小和不同形状的簇 D.K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN 会合并有重叠的簇 5.下列关于Ward’s Method说法错误的是：( ) A.对噪声点和离群点敏感度比较小 B.擅长处理球状的簇
C.对于Ward方法，两个簇的邻近度定义为两个簇合并时导致的平方误差 D.当两个点之间的邻近度取它们之间距离的平方时，Ward方法与组平均非常相似 6.下列关于层次聚类存在的问题说法正确的是：( ) A.具有全局优化目标函数 B.Group Average擅长处理球状的簇 C.可以处理不同大小簇的能力 D.Max对噪声点和离群点很敏感 7.下列关于凝聚层次聚类的说法中，说法错误的事：( ) A.一旦两个簇合并，该操作就不能撤销 B.算法的终止条件是仅剩下一个簇 C.空间复杂度为()2m O D.具有全局优化目标函数 8.规则{牛奶，尿布}→{啤酒}的支持度和置信度分别为：( ) 9.下列( )是属于分裂层次聚类的方法。 A.Min B.Max C.Group Average D.MST 10.对下图数据进行凝聚聚类操作，簇间相似度使用MAX计算，第二步是哪两个簇合并：( ) A.在{3}和{l,2}合并 B.{3}和{4,5}合并 C.{2,3}和{4,5}合并
《人工智能与机器学习》 实验报告 年级__ xxxx班____________ 专业___________xxxxx____ _____ 学号____________6315070301XX___________ 姓名_____________gllh________________ 日期___________2018-5-12 __
实验五聚类算法实现 一、实验目的 1、了解常用聚类算法及其优缺点 2、掌握k-means聚类算法对数据进行聚类分析的基本原理和划分方法 3、利用k-means聚类算法对已知数据集进行聚类分析 实验类型：验证性 计划课间：4学时 二、实验内容 1、利用python的sklearn库函数对给定的数据集进行聚类分析 2、分析k-means算法的实现流程 3、根据算法描述编程实现，调试运行 4、对所给数据集进行验证，得到分析结果 三、实验步骤 1、k-means算法原理 2、k-means算法流程 3、k-means算法实现 4、对已知数据集进行分析 四、实验结果分析 1.利用python的sklearn库函数对给定的数据集进行聚类分析： 其中数据集选取iris鸢尾花数据集 import numpy as np from sklearn.datasets import load_iris iris = load_iris() def dist(x,y):
return sum(x*y)/(sum(x**2)*sum(y**2))**0.5 def K_means(data=iris.data,k=3,ping=0,maxiter=100): n, m = data.shape centers = data[:k,:] while ping < maxiter: dis = np.zeros([n,k+1]) for i in range(n): for j in range(k): dis[i,j] = dist(data[i,:],centers[j,:]) dis[i,k] = dis[i,:k].argmax() centers_new = np.zeros([k,m]) for i in range(k): index = dis[:,k]==i centers_new[i,:] = np.mean(data[index,:],axis=0) if np.all(centers==centers_new): break centers = centers_new ping += 1 return dis if __name__ == '__main__': res = K_means() print(res) （1）、首先求出样本之间的余弦相似度： sum(x*y)/(sum(x**2)*sum(y**2))**0.5 （2）、设置k类别数为3，最大迭代次数为100 K_means(data=iris.data,k=3,ping=0,maxiter=100):
数据挖掘聚类算法课程设计报告
数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。能够这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理
2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如：abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi abelmoschus moschatus,hi,pr 上述数据中第行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的两行分别列出了属于abelmoschus 科属的两种具体植物及其分布地区。从中能够看出后两行给出的所有地区的并集正是第一行给出的地区集合。在聚类过程中第行数据是无用的，因此要对其进行清理。 2.2数据变换 本实验是依据植物的分布区域进行聚类，所给数据集中的分布区域是字符串形式，不适合进行聚类，因此将其变换成适合聚类的数值形式。具体思想如下： 数据集中总共包含68个区域，每一种植物的分布区域是这68个区域中的一部分。本实验中将68个区域看成是数据对象的68个属性，这68个属性是二元类型的变量，其值只能去0或者1。步骤如下： 1.把68个区域按一定顺序存放在字符串数组(记为str)中(顺序能够自己定，确定后不能改变)。
K-均值聚类算法 1.初始化：选择c 个代表点,...,,321c p p p p 2.建立c 个空间聚类表：C K K K ...,21 3.按照最小距离法则逐个对样本X 进行分类： ),(),,(min arg J i i K x add p x j ?= 4.计算J 及用各聚类列表计算聚类均值，并用来作为各聚类新的代表点（更新代表点） 5.若J 不变或代表点未发生变化，则停止。否则转2. 6.),(1∑∑=∈=c i K x i i p x J δ 具体代码如下： clear all clc x=[0 1 0 1 2 1 2 3 6 7 8 6 7 8 9 7 8 9 8 9;0 0 1 1 1 2 2 2 6 6 6 7 7 7 7 8 8 8 9 9]; figure(1) plot(x(1,:),x(2,:),'r*') %%第一步选取聚类中心，即令K=2 Z1=[x(1,1);x(2,1)]; Z2=[x(1,2);x(2,2)]; R1=[]; R2=[]; t=1; K=1;%记录迭代的次数 dif1=inf; dif2=inf; %%第二步计算各点与聚类中心的距离 while (dif1>eps&dif2>eps) for i=1:20 dist1=sqrt((x(1,i)-Z1(1)).^2+(x(2,i)-Z1(2)).^2); dist2=sqrt((x(1,i)-Z2(1)).^2+(x(2,i)-Z2(2)).^2); temp=[x(1,i),x(2,i)]'; if dist1 朴素贝叶斯： 有以下几个地方需要注意： 1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。 2. 计算公式如下： 其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知， = ，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。 3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace 光滑, 分母加k的原因是使之满足全概率公式）。 朴素贝叶斯的优点： 对小规模的数据表现很好，适合多分类任务，适合增量式训练。 缺点： 对输入数据的表达形式很敏感。 决策树： 决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。 信息熵的计算公式如下: 其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。 现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。 决策树的优点： 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征； 缺点： 容易过拟合（后续出现了随机森林，减小了过拟合现象）； Logistic回归： Logistic是用来分类的，是一种线性分类器，需要注意的地方有： 1. logistic函数表达式为： 其导数形式为： 2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为： 到整个样本的后验概率： 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 内容摘要本文在分析和实现经典k-means算法的基础上，针对初始类中心选择问题，结合已有的工作，基于对象距离和密度对算法进行了改进。在算法实现部分使用vc6.0作为开发环境、sql sever2005作为后台数据库对算法进行了验证，实验表明，改进后的算法可以提高算法稳定性，并减少迭代次数。 关键字 k-means；随机聚类；优化聚类；记录的密度 1 引言 1.1聚类相关知识介绍 聚类分析是直接比较各事物之间性质，将性质相近的归为一类，将性质不同的归为一类，在医学实践中也经常需要做一些分类工作。如根据病人一系列症状、体征和生化检查的结果，将其划分成某几种方法适合用于甲类病的检查，另几种方法适合用于乙类病的检查，等等。聚类分析被广泛研究了许多年。基于聚类分析的工具已经被加入到许多统计分析软件或系统中，入s-plus,spss,以及sas。 大体上，聚类算法可以划分为如下几类： 1) 划分方法。 2) 层次方法。 3) 基于密度的算法。 4) 基于网格的方法。 5) 基于模型的方法。 1.2 研究聚类算法的意义 在很多情况下，研究的目标之间很难找到直接的联系，很难用理论的途径去解决。在各目标之间找不到明显的关联，所能得到的只是些模糊的认识，由长期的经验所形成的感知和由测量所积累的数据。因此，若能用计算机技术对以往的经验、观察、数据进行总结，寻找个目标间的各种联系或目标的优化区域、优化方向，则是对实际问题的解决具有指导意义和应用价值的。在无监督情况下，我们可以尝试多种方式描述问题，其中之一是将问题陈述为对数分组或聚类的处理。尽管得到的聚类算法没有明显的理论性，但它确实是模式识别研究中非常有用的一类技术。聚类是一个将数据集划分为若干聚类的过程，是同一聚类具有较高相似性，不同聚类不具相似性，相似或不相似根据数据的属性值来度量，通常使用基于距离的方法。通过聚类，可以发现数据密集和稀疏的区域，从而发现数据整体的分布模式，以及数据属性间有意义的关联。 2 k-means算法简介 2.1 k-means算法描述 k-means 算法接受输入量k，然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”来进行计算的。k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。 k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 2.2 k-means算法实现步骤 在原始的k-means算法中，由于数据对象的分类被不断地调整，因此平均误差准则函数在每次迭代过程中的值必定在不断减小。当没有数据对象被调整时，e（e指每个对象到该类中心的距离平方之和）的值不再变化，说明算法运行结果已经达到最优，同时算法运行结束。数据挖掘主要算法
各种聚类算法的比较
K-MEANS聚类算法的实现及应用
相关主题
文本预览