V ol.16, No.4 ?2005 Journal of Software 软 件 学 报 1000-9825/2005/16(04)0496 基于Bagging 的选择性聚类集成
?
唐 伟, 周志华+ (南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093)
Bagging-Based Selective Clusterer Ensemble
TANG Wei, ZHOU Zhi-Hua +
(National Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China)
+ Corresponding author: Phn: +86-25-83686268, E-mail: zhouzh@https://www.doczj.com/doc/0715490605.html,, https://www.doczj.com/doc/0715490605.html,/people/zhouzh/
Received 2003-11-03; Accepted 2004-07-27
Tang W, Zhou ZH. Bagging-Based selective clusterer ensemble. Journal of Software , 2005,16(4):496?502. DOI: 10.1360/jos160496
Abstract : This paper uses ensemble learning technique to improve clustering performance. Since the training data used in clustering lacks the expected output, the combination of component learner is more difficult than that under supervised learning. Through aligning different clustering results and selecting component learners with the help of mutual information weight, this paper proposes a Bagging-based selective clusterer ensemble algorithm. Experiments show that this algorithm could effectively improve the clustering results.
Key words : machine learning; ensemble learning; clustering; unsupervised learning; selective ensemble
摘 要: 使用集成学习技术来提高聚类性能.由于聚类使用的训练样本缺乏期望输出,与监督学习下的集成相比,在对个体学习器进行结合时更加困难.通过对不同的聚类结果进行配准,并基于互信息权进行个体学习器的选择,提出了基于Bagging 的选择性聚类集成算法.实验表明,该算法能够有效地改善聚类结果.
关键词: 机器学习;集成学习;聚类;非监督学习;选择性集成
中图法分类号: TP181 文献标识码: A
聚类分析技术将未标记对象通过其相似度进行分组,使得组内对象的相似度最大而组间对象的相似度最小,从而发现对象中的内在特性.由于聚类分析技术在数据挖掘、模式识别等诸多领域有着广泛的应用前景,一直是机器学习领域的一个研究热点[1].
集成学习(ensemble learning)[2]技术利用基学习器的多个版本来解决同一个问题,可以显著地提高学习系统的泛化能力.最近几年,在机器学习、神经网络、统计学等领域的很多研究者都投入到集成学习的研究中,使得该领域成为了一个相当活跃的研究热点,并被认为是当前机器学习领域的4大研究方向之首[2].现在已经有很多集成学习算法,Bagging 算法[3]就是其中比较著名的一个.该算法在训练阶段,各学习器的训练集由原始训练集利用可重复取样(bootstrap sampling)技术获得,训练集的规模通常与原始训练集相当.这样,原始训练集中
? Supported by the National Outstanding Youth Foundation of China under Grant No.60325207 (国家杰出青年科学基金)
作者简介: 唐伟(1978－),男,湖南祁阳人,硕士,主要研究领域为机器学习,数据挖掘;周志华(1973－),男,博士,教授,博士生导师,主要研究领域为机器学习,数据挖掘,模式识别,信息检索,神经计算,进化计算.
唐伟等:基于Bagging的选择性聚类集成497
某些示例可能在新的训练集中出现多次,而另外一些示例则可能一次也不出现.研究表明[3],Bagging可以显著提高不稳定的基学习器的泛化能力.以往的集成学习算法在生成多个个体学习器之后,通常是对所有的个体都进行结合,因此很多研究者尝试使用大规模的集成来解决问题.Zhou等人[4]提出了“选择性集成 (selective ensemble)”的概念,并证明通过选择部分个体学习器来构建集成可能要优于使用所有个体学习器构建的集成,这就意味着利用中小规模的选择性集成就可以获得很好的性能.
需要注意的是,Bagging算法和其他大多数的集成学习算法都是为监督学习而设计的,对聚类这样的非监督学习来说,由于训练样本缺乏类别标记,聚类结果之间没有直接的对应关系,这将使得对个体学习器的结合难以直接进行.因此,用于非监督学习的集成学习算法比一般的用于监督学习的集成学习算法设计起来更加困难.实际上,利用集成学习技术来提高聚类分析的性能已经引起了一些研究者的关注.例如,在Strehl和Ghosh[5]的工作中,他们利用互信息(mutual information)把聚类集成问题定义为一个基于互信息的优化问题,但同时又指出由于该优化问题的计算开销过于庞大,因此难以应用于实际领域.
本文对聚类集成进行研究,提出了基于Bagging的选择性聚类集成算法.第1节介绍本文所用到的标记和术语,并简单介绍作为聚类集成个体的k均值(k-means)算法.第2节具体介绍基于Bagging的选择性聚类集成算法.第3节通过实验对该算法进行性能测试并对实验结果进行分析.最后一节是对本文的工作进行总结并展望进一步的工作.
1 背景知识
1.1 标记和术语
为了下文讨论的方便,本节将对有关聚类集成中所涉及的标记和术语进行约定.假设χ={x1,x2,…,x n}??d为d维特征空间中一组类别未知的向量集.该向量集中的第i个元素x i为一个d维的特征向量[x i1,x i2,…,x id]T,T表示矩阵的转置.不失一般性,假设特征向量中的每一个分量均为数值属性.对于某个聚类器(clusterer)可以将向量集χ中的元素划分为k个聚类,可用一个标记向量λ(m)=[λ1,λ2,…,λn]T∈Νn表示,其中λi∈{1,2,…,k}为聚类标记.聚类集成算法首先通过M个聚类器对向量集χ进行聚类,然后将所有聚类器产生的标记向量{λ(1),λ(2),…,λ(M)}进行结合,最后得到结果标记向量λ.
1.2 k均值算法
MacQueen提出的k均值算法[6]是一个著名的聚类学习算法.它根据相似度距离迭代地更新向量集的聚类中心,当聚类中心不再变化或者满足某些停止条件,则停止迭代过程得到最终的聚类结果.k均值算法的具体步骤为:
(1) 随机选择k个数据项作为聚类中心;
(2) 根据相似度距离公式,将数据集中的每一项数据分配到离它最近的聚类中去;
(3) 计算新的聚类中心;
(4) 如果聚类中心没有发生改变,算法结束;否则跳转到第(2)步.
由于所选择的相似度距离公式的不同,k均值算法所得到的聚类结果将存在较大的差异.为了简化讨论,本文采用欧氏距离作为k均值算法的相似度距离公式.但值得注意的是,本文工作对其他距离公式同样是适用的.
2 基于Bagging的选择性聚类集成
集成学习一般包含两个阶段,即个体生成阶段和个体学习器的结合阶段.在个体生成阶段,通过不同的个体生成方式产生不同的个体标记向量.在个体学习器的结合阶段,可以采用投票等方式将个体标记向量进行结合.
在个体生成阶段,考虑到需要聚类的对象数可能非常庞大,对所有对象进行聚类势必将增加聚类算法的运行开销.因此,可以考虑对整个空间中分布在某个局部的对象进行聚类从而得到结果,但是,由于聚类对象的空间分布可能很不均匀,所得到的聚类结果可能只代表某个局部信息而不是全局的聚类结果.为了解决这个问题,本文采用类似Bagging算法中产生个体训练集的方式产生用于聚类的训练集,即通过可重复取样技术从原向量
498 Journal of Software 软件学报 2005,16(4) 集χ中产生若干训练集{S i },i =1,…,T ,对每个训练集S i 用k 均值聚类器进行聚类.由于聚类对象受到某种程度的扰动,将进一步增大聚类结果中个体标记向量之间的差异,这有助于获得更好的集成.另一方面,由于k 均值聚类器只对原向量空间中的某一个局部进行了聚类,从而降低了聚类器的算法开销.需要注意的是,通过可重复取样技术产生的训练集S i 并不代表原向量集χ,故其并不代表全局的聚类结果.本文首先记录下k 均值聚类器对S i 进行聚类后达到稳定状态时的k 个聚类中心,然后用这k 个聚类中心对原向量集χ中的元素进行重新分配,最后得到针对向量集χ的标记向量.
然而,通过这种方式得到的标记向量由于缺乏先验的类别信息,并不能直接用于下一阶段的结论合成.例如,对于标记向量[1,2,2,1,1,3,3]T 和[2,3,3,2,2,1,1]T ,虽然它们的表达方式不同,但是却表示着同一个聚类结果.所以为了对聚类结果进行结合,个体标记向量必须经过匹配建立相互之间的对应关系.一般来说,有对应关系的聚类标记所覆盖的相同对象的个数应该是最大的.因此,可以根据这一启发式来对标记向量进行配准.假设存在着两个标记向量λ(a )和λ(b ),每个标记向量分别把原向量集划分为k 个聚类,分别用聚类标记{C 1(a ),C 2(a ),…,C k (a )}和{C 1(b ), C 2(b ),…,C k (b )}表示.首先,将这两个标记向量中每一对聚类标记C i (a )和C j (b )所覆盖的相同对象的个数记录在k ×k 的OVERLAP 矩阵中,然后选择其中覆盖相同对象个数最大的聚类标记建立对应关系,并将其结果从OVERLAP 矩阵中移除.重复以上过程,直到所有聚类标记都建立了对应关系为止.
当存在M (M >2)个聚类标记向量时,则随机选取某个标记向量作为匹配基准,将其他标记向量和基准标记向量进行匹配.匹配算法只需要对M －1个标记向量做一次扫描,共需(M －1)×k 2大小的存储空间来保存OVERLAP 矩阵.整个匹配过程是快速和高效的.
在个体学习器的结合阶段,本文采用的是一种基于权值的选择性投票策略.在用于投票的个体标记向量的权值计算上,受Strehl 和Ghosh 工作[5]的启发,本文认为聚类标记向量间的互信息在某种程度上能够刻画聚类个体间的紧密程度,因此,利用互信息来表示个体标记向量的权值将有助于得到更好的集成结论.假设通过k 均值聚类器对大小为n 的向量集进行聚类,分别得到具有k 个聚类的标记向量λ(a )和λ(b ),用聚类标记{C 1(a ), C 2(a ),…,C k (a )}和{C 1(b ),C 2(b ),…,C k (b )}来表示.假设聚类标记C i (a )中含有n i 个元素,聚类标记C j (b )中有n j 个元素,其中C i (a )和C j (b )中的相同元素有n ij 个.那么,互信息可定义如下:
()()()∑∑==???
?????=k i k j j i ij k ij b a NMI n n n n n n 112log 2,λλΦ (1) 对于个体标记向量,其平均互信息可用下式表示:
∑≠==?=t m
l l l m NMI m t m t ,1)()()1,2,...,( ),(11λλΦβ (2) 当βm 越大时,标记向量λ(m )所包含的其他标记向量所不具备的统计信息也就越少.所以,个体标记向量的权值可定义如下:
),...,2,1( 1
t m Z w m m ==β (3)
其中,Z 用于将权值规范化,使聚类标记的权值满足:
1 and ),...,2,1(01∑===>t
m m m w t m w (4)
本文将前面所定义的个体标记向量的权值作为选择聚类集成个体标记向量的依据.当标记向量的权值低于某个预设阈值如1/T (T 为集成中个体标记向量的个数)时,该个体标记向量将不参加最后的结论合成.最后,将挑选出的个体标记向量再基于权值进行投票.
基于Bagging 的选择性聚类集成算法的伪码描述如下.
Input: number of cluster centers k , data set S , number of bootstap sampling T
Output: cluster label C *(x ) for data object x
For t =1 to T Do
唐伟 等:基于Bagging 的选择性聚类集成
499
S t = bootstrap sample from S λ(t ) = kmeans(k ,S t )
/* λ(t ) is represented as {C 1(t ),C 2(t ),…,C k (t )} */
/* for data object x , its cluster label determined by λ(t ) is λ(t )(x )∈{C 1(t ),C 2(t ),…,C k (t )} */
End of For
λ(baseline ) = randomly selected from {λ(t )},t =1,…,T
Delete λ(baseline ) from {λ(t )}, t =1,…,T
For each λ(t ) in {λ(t )}Do
For i =1 to k , j =1 to k Do
OVERLAP(i ,j )=Count(C i (t ),C j (baseline ))
End of For
/* OVERLAP is a k ×k matrix; Count(A , B ) counts the number of same */
/* elements labeled by A and B */
Γ=?
While Γ≠{C 1(baseline ), C 2(baseline ),…,C k (baseline )} Do
(u ,v )=argmax(OVERLAP(i ,j )) /* OVERLAP(u , v ) is the biggest element */
C v (t )=C u (baseline ) /* align C v (t) to C u (baseline ) */
Delete OVERLAP(u ,*)
Delete OVERLAP(*,v )
Γ=Γ∪{C v (t )}
End of While
End of For
For t =1 to T Do
Calculate w t for each λ(t )
End of For
)(max arg )()()/1()1(*x w x C t t T w T t t λ>∧≤≤=
3 实验测试
本文除对基于Bagging 的选择性聚类集成(sel-b-voting)算法进行了实验测试,还对基于简单投票的聚类集成(即随机初始化聚类中心产生个体标记向量,再进行简单投票)和基于加权投票的聚类集成(即随机初始化聚类中心产生个体标记向量,并根据相互间的互信息计算权值,然后进行基于权值投票)做了实验测试.
我们采用UCI 机器学习数据库[7]中的10个数据集对上述聚类集成方法进行了实验.在这10个数据集中,除了类别属性以外,其余属性均为数值属性.其中,Image Segmentation 数据集中由于存在一列常数属性,对以后的聚类过程没有帮助而被删除.这10个数据集的具体信息见表1.
当数据有分类信息时,可认为该分类信息在一定程度上表达了数据的一些内部分布特性,如果该分类信息没有被聚类过程所利用,则可以用它来评价聚类效果.在Modha 和Spangler [8]的工作中就是利用数据的分类信息来评价聚类结果的好坏.如果标记向量中某聚类标记和类别属性中某已知类别所覆盖的相同对象个数最多,则将该聚类标记对应为这个已知类别.这样,多个聚类标记可以对应同一个类别,而一个聚类标记则不能对应多个类别.通过这样的匹配,聚类结果就可以利用分类信息来进行评价.
500 Journal of Software 软件学报 2005,16(4)
Table 1 Data sets used in the experiments
表1 实验所用数据集
Data set No.attributes No.classes No.instances
Image segmentation 18 7 2 310
Ionosphere 34 2 351
Iris 4 3 150
Liver disorder 6 2 345
Page bocks 10 5 5 473
Vehicle 18 4 846
Waveform-21 21 3 5 000
Waveform-40 40 3 5 000
Wine 13 3 178
Wpbc 33 2 198
假设大小为n 的向量集中存在的已知类别标记为C ,可用{C 1,C 2,…,C h }来表示.通过k 均值聚类器对该向量集进行聚类所得到的结果为一个具有k 个聚类标记的标记向量λ,可用{λ1,λ2,…,λk }来表示.通过上述的匹配过程,聚类标记向量中的每一个λi 将对应为类别标记中的某一个C j .假设αi 为λi 中被正确分类为对应类别C i 的示例个数,那么该聚类标记向量的结果可用Micro-precision 进行衡量,具体的定义公式如下:
∑==k i i a n 1
1p -micro (5) Micro-precision 的值越大,则表示聚类的标记向量越好.需要注意的是,这种评价策略只能用于比较能产生固定聚类个数的聚类器性能,而不能用于评价聚类个数产生具有不确定性的聚类器.因此,在本节的实验中,k 均值聚类器的聚类个数固定设置为其已知的类别数.
实验中,k 均值聚类器的最大迭代步数设为100,误差停止阈值为1e-5.对于每个数据集,用上述所提到的5种聚类集成算法构造大小为5,8,13,20和30规模的集成.其中对于每一种测试都重复10次实验,然后记录下平均的Micro-precision 和标准偏差.同时,单个k 均值聚类器的结果也记录了下来,以便于和集成结果进行比较.
表2给出了在显著程度0.05时的双边t 检验结果,其中voting 表示基于简单投票的聚类集成算法,w-voting 表示基于加权投票的聚类集成,sel-b-voting 表示基于Bagging 的选择性聚类集成.“win”表示聚类集成结果显著地比单个k 均值聚类器的结果“好”,“loss”表示聚类集成结果显著地比单个k 均值聚类器的结果“差”,而“tie”则表示聚类集成结果和单个k 均值聚类器的结果没有显著差异.
Table 2 Results of pairwise two-tailed t tests with significance level 0.05
表2 显著程度0.05时双边t 检验的结果
Ensemble size Voting win/tie/loss W-Voting win/tie/loss Sel-B-Voting win/tie/loss
8 0/8/2 3/6/1 4/5/1
13 2/6/2 2/6/2 6/3/1
20 1/6/3 3/4/3 5/4/1
30 1/5/4 3/4/3 5/4/1
由表2可以看出,基于简单投票的聚类集成在性能上比单个k 均值聚类器要差;基于加权投票的聚类集成和单个k 均值聚类器所得到的结果相差不大;而基于Bagging 的选择性聚类集成则比单个k 均值聚类器要好.特别是当集成的大小为13的时候,所有10个数据集中,选择性聚类集成所得到的结果仅在1个数据集上比单个k 均值聚类器所得到的结果要差,而在6个数据集上,其结果比单个k 均值聚类器所得到的结果要好.这说明选择性集成方法在非监督学习领域特别是对于聚类问题同样有效.
表3给出了不同集成规模下,选择性聚类集成实际使用的个体聚类器数目占所有个体聚类器数目的百分比.由表3可以看出,基于Bagging 的选择性聚类集成仅使用了28%~40%的个体聚类器参与构造最后的集成.
从以上的实验数据分析可以看出,选择性聚类集成仅利用了少数个体聚类器就达到了比利用所有个体聚类器更好的效果.
同时,实验中对于每一个数据集都构造了规模不等的聚类集成.为了解聚类集成的结果是否会受到集成规模变化的影响,本文也记录了相关的实验结果.图1给出了聚类集成的性能随着集成规模的大小而变化的关系图.其中,voting 表示基于简单投票的聚类集成算法,w-voting 表示基于加权投票的聚类集成,sel-b-voting 表示基
唐伟 等:基于Bagging 的选择性聚类集成
501
于Bagging 的选择性聚类集成.
Table 3 The average percentage of component clusterers selected by the proposed algorithm under different ensemble sizes
表3 在不同集成规模下,本文方法所选用的个体聚类器的平均百分比
Ensemble size Percentage of component clusterers selected (%)
5 39.2 (1.96/5)
8 38.1 (3.05/8)
13 33.7 (4.38/13)
20 31.8 (6.36/20)
30 28.0 (8.41/30)
Fig.1 The influence of ensemble size on the performance of clusterer ensemble
图1 集成规模变化对聚类集成的性能的影响
从图1可以看出,基于Bagging 的选择性聚类集成随着集成规模的增大,其聚类性能也有所提高.而对基于简单投票的聚类集成,当集成的规模增大时,其性能反而有下降的趋势.产生这种现象的原因可能是由于随着集成规模的增大,将产生更多的个体标记向量覆盖整个向量空间,而并不是所有的标记向量都有助于提高集成的性能,其中某些个体可能存在着严重的误导性.图1也验证了Zhou 等人[9]的结论,即当拥有一组个体学习器时,进行选择性集成比用所有个体集成更好.需要注意的是,图中横轴显示出的是个体聚类器的总数,由于基于Bagging 的选择性聚类集成算法仅对挑选出的个体聚类器进行集成,其实际规模要远小于图1中显示的值. 4 结束语
本文提出了基于Bagging 的选择性聚类集成算法.实验结果表明,基于Bagging 的选择性聚类集成算法能有效地利用集成学习技术来提高聚类性能.由于选择性聚类集成只利用到了部分而不是所有聚类个体,这就降低了计算开销和存储开销.另外,由于该算法利用互信息计算权值的过程只对k 均值聚类器的结果标记向量进行分析,这与选择什么样的聚类分析算法无关,所以本文提出的基于Bagging 的选择性聚类集成算法同样也能适用于k 均值外的其他聚类器.本文使用的个体聚类器均采用欧氏距离,由于不同的相似度距离对聚类结果有不同程度的影响,因此也可以尝试使用多种距离度量的个体聚类器进行集成.
值得注意的是,在本文工作进行时,将集成学习技术用于聚类的工作还非常少[5,9],但到目前已经出现了很多此类工作[10?12],这说明利用集成学习技术来改善聚类性能是一个新兴的研究热点.事实上,集成学习技术除了被用于监督学习和非监督学习,还被用于多示例学习[13,14].这一方面说明集成学习的效用已经受到了广泛的认可,其适用范围正逐渐扩大;另一方面也说明集成学习的研究空间还很大,尤其是将集成学习技术应用到监督学习之外的场合,还有很多重要的问题需要研究.
References :
[1] Estivill-Castro V. Why so many clustering algorithms —A position paper. SIGKDD Explorations, 2002,4(1):65?75.
[2] Dietterich TG. Machine learning research: Four current directions. AI Magazine, 1997,18(4):97?136.
[3] Breiman L. Bagging predicators. Machine Learning, 1996,24(2):123?140.
0.64
0.66
0.68
0.700.72
5 8 13 2030Ensemble size A v e r a g e m i c r o -p Voting W-Voting Sel-B-Voting
502 Journal of Software软件学报2005,16(4)
[4] Zhou ZH, Wu J, Tang W. Ensembling neural networks: Many could be better than all. Artificial Intelligence, 2002,137(1?2):
239?263.
[5] Strehl A, Ghosh J. Cluster ensembles—A knowledge reuse framework for combining partitionings. In: Dechter R, Kearns M,
Sutton R, eds.Proc. of the 18th National Conf. on Artificial Intelligence. Menlo Park: AAAI Press, 2002. 93?98.
[6] MacQueen JB. Some methods for classification and analysis of multivariate observations. In: LeCam LM, Neyman J, eds. Proc. of
the 5th Berkeley Symp. on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967,1:281?297.
[7] Blake C, Keogh E, Merz CJ. UCI Repository of machine learning databases. Irvine: Department of Information and Computer
Science, University of California, 1998. https://www.doczj.com/doc/0715490605.html,/~mlearn/MLRepository.html
[8] Modha DS, Spangler WS. Feature weighting in k-means clustering. Machine Learning, 2003,52(3):217?237.
[9] Zhou ZH, Tang W. Clusterer ensemble. Technical Report, Nanjing: AI Lab., Department of Computer Science & Technology,
Nanjing University, 2002.
[10] Fern XZ, Brodley CE. Random projection for high dimensional data clustering: A cluster ensemble approach. In: Fawcett T, Mishra
N, eds. Proc. of the 20th Int’l Conf. on Machine Learning. Menlo Park: AAAI Press, 2003. 186?193.
[11] Fern XZ, Brodley CE. Solving cluster ensemble problems by bipartite graph partitioning. In: Greiner R, Schuurmans D, eds. Proc.
of the 21st Int’l Conf. on Machine Learning. 2004. http://www.aicml.cs.ualberta.ca/ banff04/icml/pages/proceedings.htm
[12] Topchy A, Jain AK, Punch W. A mixture model for clustering ensembles. In: Berry MW, Dayal U, Kamath C, Skillicorn DB, eds.
Proc. of the 4th SIAM Int’l Conf. on Data Mining. Philadelphia: SIAM, 2004. https://www.doczj.com/doc/0715490605.html,/meetings/sdm04/proceedings/ index.htm
[13] Zhou ZH, Zhang ML. Ensembles of multi-instance learners. In: Lavra? N, Gamberger D, Blockeel H, Todorovski L, eds. Lecture
Notes in Artificial Intelligence 2837, Berlin: Springer-Verlag, 2003. 492?502.
[14] Xu X, Frank E. Logistic regression and boosting for labeled bags of instances. In: Dai H, Srikant R, Zhang C, eds. Lecture Notes in
Artificial Intelligence 3056, Berlin: Springer-Verlag, 2004. 272?281.
基于K-means聚类算法的入侵检测系统的设计 基于K-means聚类算法的入侵检测系统的设计 今天给大家讲述的是K-means聚类算法在入侵检测系统中的应用首先，介绍一下 聚类算法 将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的研究，就形成了历史学，有关世界空间地域的研究，则形成了地理学。 又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不同的界、门、纲、目、科、属、种之中。 事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。 通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analysis）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。 （聚类分析我们说得朴实一点叫做多元统计分析，说得时髦一点叫做数据挖掘算法，因为这个算法可以在一堆数据中获取很有用的信息，这就不就是数据挖掘吗，所以大家平时也不要被那些高大上的名词给吓到了，它背后的核心原理大多数我们都是可以略懂一二的，再
比如说现在AI这么火，如果大家还有印象的话，以前我们在大二上学习概率论的时候，我也和大家分享过自然语言处理的数学原理，就是如何让机器人理解我们人类的自然语言，比如说，苹果手机上的Siri系统，当时还让杨帆同学帮我在黑板上写了三句话，其实就是贝叶斯公式+隐含马尔可夫链。估计大家不记得了，扯得有点远了接下来还是回归我们的正题，今天要讨论的聚类算法。） K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，结果稳定，聚类的效果也还不错, 相异度计算 在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。 要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个特征变量来刻画，就比如说我们举一个例证，就有一项比较神奇的技术叫面部识别技术，其实听起来很高大上，它是如何做到的，提取一个人的面部特征，比如说嘴巴的长度，鼻梁的高度，眼睛中心到鼻子的距离，鼻子到嘴巴的距离，这些指标对应得数值可以组成一个向量作为每一个个体的一个标度变量（）,或者说叫做每一个人的一个特征向量。 如果对于一群有待分类的样本点需用p 个特征变量值描述，则每
Software Engineering and Applications 软件工程与应用, 2016, 5(2), 114-121 Published Online April 2016 in Hans. https://www.doczj.com/doc/0715490605.html,/journal/sea https://www.doczj.com/doc/0715490605.html,/10.12677/sea.2016.52013 Video Key Frame Recognition Technology Research Based on the Content Qian Liu, Gui’e Luo, Xianru Liu* Central South University, Changsha Hunan Received: Mar. 17th, 2016; accepted: Apr. 2nd, 2016; published: Apr. 5th, 2016 Copyright ? 2016 by authors and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY). https://www.doczj.com/doc/0715490605.html,/licenses/by/4.0/ Abstract The key frame extraction is vital for automatic segmentation of video; the standard of extracted key frame directly affects the final result. Based on the analysis and research about project video, the paper proposes template matching, histogram comparison, the key frame detection and key frame recognition algorithm, and for the recognition accuracy and recognition rate of template matching and histogram comparison, the paper also does the comparison. In the recognition, the key frames adopted a new character segmentation algorithm. Finally, the paper summarizes the advantages of this method and good results have been achieved. Keywords Key Frame, Template Matching, Character Segmentation 基于内容的项目视频关键帧识别技术研究 刘倩，罗桂娥，刘献如* 中南大学，湖南长沙 收稿日期：2016年3月17日；录用日期：2016年4月2日；发布日期：2016年4月5日 摘要 关键帧的提取对于视频的自动切分至关重要，提取的好坏直接影响最终的结果，本文通过对项目视频的*通讯作者。
1.function[Ax]=F_tj(A,m0)%定义函数 %模糊统计，m0划分区间个数 [n,m]=size(A);%获得矩阵的行列数 Amin=A(1,1);%A的最小值 Amax=A(1,2);%A的最大值 for(i=1:n) if(A(i,1)>A(i,2))x=A(i,2);A(i,2)=A(i,1);A(i,1)=x;end%A的最小值 if(A(i,1) CLOPE：针对交易的数据快速有效聚类算法 摘要 本文研究分类数据的聚类问题，特别针对多维和大型的交易数据。从增加聚簇直方图的高宽比的方法得到启发，我们开发了一种新的算法---CLOPE，这是一种非常快速、可伸缩，同时又非常有效的算法。我们展示了算法对两个现实数据集聚类的性能，并将CLOPE与现有的聚类算法进行了比较。 关键词 数据挖掘，聚类，分类数据，可伸缩性 1.简介 聚类是一种非常重要的数据挖掘技术，它的目的是将相似的交易[12, 14, 4, 1]分组在一起。最近，越来越多的注意力已经放到了分类数据[10,8,6,5,7,13]的聚类上，分类数据是由非数值项构成的数据。交易数据，例如购物篮数据和网络日志数据，可以被认为是一种特殊的拥有布尔型值的分类数据，它们将所有可能的项作为项。快速而精确地对交易数据进行聚类的技术在零售行业，电子商务智能化等方面有着很大的应用潜力。 但是，快速而有效聚类交易数据是非常困难的，因为这类的数据通常有着高维，稀疏和大容量的特征。基于距离的算法例如k-means[11]和CLARANS[12]都是对低维的数值型数据有效。但是对于高维分类数据的处理效果却通常不那么令人满意[7]。像ROCK这类的分层聚类算法在分类数据聚类中表现的非常有效，但是他们在处理大型数据库时表现出先天的无效。 LargeItem[13]算法通过迭代优化一个全局评估函数对分类数据进行聚类。这个评估函数是基于大项概念的，大项是在一个聚簇内出现概率比一个用户自定义的参数——最小支持度大的项。计算全局评估函数要远比计算局部评估函数快得多，局部评估函数是根据成对相似性定义的。这种全局方法使得LargeItem算法非常适合于聚类大型的分类数据库。 在这篇文章中，我们提出了一种新的全局评估函数，它试图通过增加聚簇直方图的高度与宽度之比来增加交易项在聚簇内的重叠性。此外，我们通过引用一个参数来控制聚簇紧密性的方法来泛化我们的想法，通过修改这个参数可以得到 聚类分析原理及步骤——将未知数据按相似程度分类到不同的类或簇的过程 1》传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 典型使用 1》动植物分类和对基因进行分类 2》在网上进行文档归类来修复信息 3》帮助电子商务的用户了解自己的客户，向客户提供更合适的服务 主要步骤 1》数据预处理——选择数量，类型和特征的标度（（依据特征选择和抽取）特征选择选择重要的特征，特征抽取把输入的特征转化 为一个新的显著特征，它们经常被用来获取一个合适的特征集来为避免“维数 灾”进行聚类）和将孤立点移出数据（孤立点是不依附于一般数 据行为或模型的数据） 2》为衡量数据点间的相似度定义一个距离函数——既然相类似性是定义一个类的基础，那么不同数据之间在同一个特 征空间相似度的衡量对于聚类步骤是很重要的，由于特征类型和特 征标度的多样性，距离度量必须谨慎，它经常依赖于使用，例如， 通常通过定义在特征空间的距离度量来评估不同对象的相异性，很 多距离度都使用在一些不同的领域一个简单的距离度量，如 Euclidean距离，经常被用作反映不同数据间的相异性，一些有关相 似性的度量，例如PMC和SMC，能够被用来特征化不同数据的概 念相似性，在图像聚类上，子图图像的误差更正能够被用来衡量两 个图形的相似性 3》聚类或分组——将数据对象分到不同的类中【划分方法 （划分方法一般从初始划分和最优化一个聚类标准开始，Cris p Clustering和Fuzzy Clusterin是划分方法的两个主要技术，Crisp Clustering，它的每一个数据都属于单独的类；Fuzzy Clustering，它的 每个数据可能在任何一个类中）和层次方法（基于某个标准产生一 个嵌套的划分系列，它可以度量不同类之间的相似性或一个类的可分 离性用来合并和分裂类）是聚类分析的两个主要方法，另外还有基于 密度的聚类，基于模型的聚类，基于网格的聚类】 4》评估输出——评估聚类结果的质量（它是通过一个类有效索引来 评价，，一般来说，几何性质，包括类间的分离和类内部的耦合，一般 都用来评价聚类结果的质量，类有效索引在决定类的数目时经常扮演 了一个重要角色，类有效索引的最佳值被期望从真实的类数目中获取， 一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳 值，这个索引能否真实的得出类的数目是判断该索引是否有效的标准， 很多已经存在的标准对于相互分离的类数据集合都能得出很好的结 果，但是对于复杂的数据集，却通常行不通，例如，对于交叠类的集 合。） 聚类分析的主要计算方法原理及步骤划分法 1》将数据集分割成K个组（每个组至少包 含一个数据且每一个数据纪录属于且 仅属于一个分组），每个组成为一类2》通过反复迭代的方法改变分组，使得每 一次改进之后的分组方案都较前一次 好（标准就是：同一分组中的记录越近 越好，而不同分组中的纪录越远越好， 使用这个基本思想的算法有： 一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。 基于关键帧提取的静态视频摘要技术研究 随着互联网的广泛使用和视频采集技术的逐渐成熟,数字视频数 量呈爆炸式增长。为了从海量视频中快速准确搜索到有效信息,通过 精简的关键帧概括原始视频的主要内容,视频摘要技术应时而生。现 有视频摘要方法,不仅专门用于解决视频关键帧相似性度量问题的理 论仍处于形成期,而且大多数的图像相似性计算方法主要依据的是传 统图像特征,较少考虑到图像像素空间的拓扑结构。针对以上问题, 围绕静态视频摘要技术,本文对关键帧提取和关键帧图像相似性计算 中涉及的关键技术进行了研究,主要工作概括如下:(1)以光流运动分 析为基础,提出将光流技术与改进的爬山搜索相结合的关键帧提取方法。首先,使用光流法计算视频帧序列的运动曲线。然后,通过改进的爬山法实现对搜索初始点的预设,引导算法向更合理的解空间搜索运 动曲线的局部极小值;通过变步长搜索,使算法迅速地收敛于局部最 优解。最后,提取运动局部极小值对应的视频帧作为关键帧。该方法 根据连续帧之间光流位移的变化剧烈程度提取关键帧,其获得的关键 帧不仅较全面地涵盖视频内容,而且能突出视频的重要内容;同时可 应用于视频的快速浏览和检索。(2)提出基于超像素分割的关键帧相 似性计算方法。该方法使用超像素分割算法对关键帧图像的像素进行局部聚类,可将像素点提升至更具语义空间的图像区域。如此操作, 能够有效地利用像素间的区域拓扑关系,以实现对图像块的准确比对。利用该方法对提取出的相邻关键帧进行相似性计算,并以此为依据压 缩关键帧间类似的冗余帧,同时不会遗漏人们感兴趣的视频信息,进 而得到更有效且性能更优的静态视频摘要结果。(3)将本文提出的静态摘要方法在两个公开基准数据集,即OVP数据集和YouTube数据集上完成实验,并与几种具有代表性的静态视频摘要方法进行对比。通过主观展现及客观性能分析,证明本文获取的视频摘要与人工摘要结果具有更高的一致性,且比以往方法表现出更好的性能,从而验证本文所提方法的有效性和先进性。 1.聚类定义 “聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset）,这样让在同一个子集中的成员对象都有一些相似的属性”——wikipedia “聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。”——百度百科 说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理解，如果一个数据集合包含N个实例，根据某种准则可以将这N 个实例划分为m个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这个过程就叫聚类了。 2.聚类过程: 1) 数据准备:包括特征标准化和降维. 2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中. 3) 特征提取:通过对所选择的特征进行转换形成新的突出特征. 4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量;而后执行聚类或分组. 5) 聚类结果评估:是指对聚类结果进行评估.评估主要有3 种:外部有效性评估、内部有效性评估和相关性测试评估. 3聚类算法的类别 没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法.聚类算法有多种分类方法将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法,如图1 所示 的4 个类别. 第37卷第11期 2000年11月计算机研究与发展JOU RNAL O F COM PU T ER R ESEA RCH &D EV ELO PM EN T V o l 137,N o 111N ov .2000 原稿收到日期:1999209220;修改稿收到日期:1999212209.本课题得到国家自然科学基金项目(项目编号69743001)和国家教委博士点教育基金的资助.周水庚,男,1966年生,博士研究生,高级工程师,主要从事数据库、数据仓库和数据挖掘以及信息检索等的研究.周傲英,男,1965年生,教授,博士生导师,主要从事数据库、数据挖掘和W eb 信息管理等研究.曹晶,女,1976年生,硕士研究生,主要从事数据库、数据挖掘等研究.胡运发,男,1940年生,教授,博士生导师,主要从事知识工程、数字图书馆、信息检索等研究. 一种基于密度的快速聚类算法 周水庚 周傲英 曹 晶 胡运发 (复旦大学计算机科学系 上海 200433) 摘 要 聚类是数据挖掘领域中的一个重要研究方向.聚类技术在统计数据分析、模式识别、图像处理等领域有广泛应用.迄今为止人们提出了许多用于大规模数据库的聚类算法.基于密度的聚类算法DBSCAN 就是一个典型代表.以DBSCAN 为基础,提出了一种基于密度的快速聚类算法.新算法以核心对象邻域中所有对象的代表对象为种子对象来扩展类,从而减少区域查询次数,降低I O 开销,实现快速聚类.对二维空间数据测试表明:快速算法能够有效地对大规模数据库进行聚类,速度上数倍于已有DBSCAN 算法. 关键词 空间数据库,数据挖掘,聚类,密度,快速算法,代表对象 中图法分类号 T P 311.13;T P 391 A FAST D ENSIT Y -BASED CL USTER ING AL G OR ITH M ZHOU Shu i 2Geng ,ZHOU A o 2Y ing ,CAO J ing ,and HU Yun 2Fa (D ep a rt m en t of Co mp u ter S cience ,F ud an U n iversity ,S hang ha i 200433) Abstract C lu stering is a p rom ising app licati on area fo r m any fields including data m in ing ,statistical data analysis ,p attern recogn iti on ,i m age p rocessing ,etc .In th is paper ,a fast den sity 2based clu stering algo rithm is developed ,w h ich con siderab ly speeds up the o riginal DB SCAN algo rithm .U n like DB SCAN ,the new DB SCAN u ses on ly a s m all num ber of rep resen tative ob jects in a co re ob ject’s neighbo rhood as seeds to exp and the clu ster so that the execu ti on frequency of regi on query can be decreased ,and con sequen tly the I O co st is reduced .Experi m en tal resu lts show that the new algo rithm is effective and efficien t in clu stering large 2scale databases ,and it is faster than the o riginal DB SCAN by several ti m es . Key words spatial database ,data m in ing ,clu stering ,den sity ,fast algo rithm ,rep resen tative ob jects 1 概 述 近10多年来,数据挖掘逐渐成为数据库研究领域的一个热点[1].其中,聚类分析就是广为研究的问题之一.所谓聚类,就是将数据库中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同.聚类技术在统计数据分析、模式识别、图像处理等领域都有广泛的应用前景.迄今为止,人们已经提出了许多聚类算法[2～7].所有这些算法都试图解决大规模数据的聚类问题.以基于密度的聚类算法DB SCAN [4]为基础,本文提出一种基于密度的快速聚类算法.通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,快速算法减少了区域查询的次数,从而减低了聚类时间和I O 开销 .本文内容安排如下:首先在第2节中介绍基于密度的聚类算法DB SCAN 的基本思想,并分析它的局限 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 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思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.doczj.com/doc/0715490605.html, Journal of Software, Vol.19, No.7, July 2008, pp.1683?1692 https://www.doczj.com/doc/0715490605.html, DOI: 10.3724/SP.J.1001.2008.01683 Tel/Fax: +86-10-62562563 ? 2008 by Journal of Software. All rights reserved. ? 一种基于K-Means局部最优性的高效聚类算法 雷小锋1,2+, 谢昆青1, 林帆1, 夏征义3 1(北京大学信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871) 2(中国矿业大学计算机学院,江苏徐州 221116) 3(中国人民解放军总后勤部后勤科学研究所,北京 100071) An Efficient Clustering Algorithm Based on Local Optimality of K-Means LEI Xiao-Feng1,2+, XIE Kun-Qing1, LIN Fan1, XIA Zheng-Yi3 1(Department of Intelligence Science/National Laboratory on Machine Perception, Peking University, Beijing 100871, China) 2(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China) 3(Logistics Science and Technology Institute, P.L.A. Chief Logistics Department, Beijing 100071, China) + Corresponding author: E-mail: leiyunhui@https://www.doczj.com/doc/0715490605.html, Lei XF, Xie KQ, Lin F, Xia ZY. An efficient clustering algorithm based on local optimality of K-Means. Journal of Software, 2008,19(7):1683?1692. https://www.doczj.com/doc/0715490605.html,/1000-9825/19/1683.htm Abstract: K-Means is the most popular clustering algorithm with the convergence to one of numerous local minima, which results in much sensitivity to initial representatives. Many researches are made to overcome the sensitivity of K-Means algorithm. However, this paper proposes a novel clustering algorithm called K-MeanSCAN by means of the local optimality and sensitivity of K-Means. The core idea is to build the connectivity between sub-clusters based on the multiple clustering results of K-Means, where these clustering results are distinct because of local optimality and sensitivity of K-Means. Then a weighted connected graph of the sub-clusters is constructed using the connectivity, and the sub-clusters are merged by the graph search algorithm. Theoretic analysis and experimental demonstrations show that K-MeanSCAN outperforms existing algorithms in clustering quality and efficiency. Key words: K-MeanSCAN; density-based; K-Means; clustering; connectivity 摘要: K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究 工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基 础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的 子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子 簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率. 关键词: K-MeanSCAN;基于密度;K-Means;聚类;连通性 中图法分类号: TP18文献标识码: A ? Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA12Z217 (国家高技术研究发 展计划(863)); the Foundation of China University of Mining and Technology under Grant No.OD080313 (中国矿业大学科技基金) Received 2006-10-09; Accepted 2007-07-17 聚类分析法 先用一个例子引出聚类分析 一、聚类分析法的概念 聚类分析又叫群分析、点群分析或者簇分析，是研究多要素事物分类问题的数量，并根据研究对象特征对研究对象进行分类的多元分析技术，它将样本或变量按照亲疏的程度，把性质相近的归为一类，使得同一类中的个体都具有高度的同质性，不同类之间的个体都具有高度的异质性。 聚类分析的基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 描述亲属程度通常有两种方法：一种是把样本或变量看出那个p维向量，样本点看成P 维空间的一个点，定义点与点之间的距离；另一种是用样本间的相似系数来描述其亲疏程度。有了距离和相似系数就可定量地对样本进行分组，根据分类函数将差异最小的归为一组，组与组之间再按分类函数进一步归类，直到所有样本归为一类为止。 聚类分析根据分类对象的不同分为Q型和R型两类，Q--型聚类是对样本进行分类处理，R--型聚类是对变量进行分类处理。 聚类分析的基本思想是，对于位置类别的样本或变量，依据相应的定义把它们分为若干类，分类过程是一个逐步减少类别的过程，在每一个聚类层次，必须满足“类内差异小，类间差异大”原则，直至归为一类。评价聚类效果的指标一般是方差，距离小的样品所组成的类方差较小。 常见的聚类分析方法有系统聚类法、动态聚类法（逐步聚类法）、有序样本聚类法、图论聚类法和模糊聚类法等。 二、对聚类分析法的评价 聚类分析也是一种分类技术。与多元分析的其他方法相比，该方法较为粗糙，理论上还不完善，但应用方面取得了很大成功。与回归分析、判别分析一起被称为多元分析的三大方法。 聚类的目的：根据已知数据，计算各观察个体或变量之间亲疏关系的统计量（距离或相关系数）。根据某种准则（最短距离法、最长距离法、中间距离法、重心法），使同一类内的 SPSS软件聚类分析过程的图文解释及结果的全面分析 SPSS聚类分析过程 聚类的主要过程一般可分为如下四个步骤： 1.数据预处理（标准化） 2.构造关系矩阵（亲疏关系的描述） 3.聚类（根据不同方法进行分类） 4.确定最佳分类（类别数） SPSS软件聚类步骤 1. 数据预处理（标准化） →Analyze →Classify →Hierachical Cluster Analysis →Method 然后从对话框中进行如下选择 从Transform Values框中点击向下箭头，此为标准化方法，将出现如下可选项，从中选一即可： 标准化方法解释：None：不进行标准化，这是系统默认值；Z Scores：标准化变换；Range –1 to 1：极差标准化变换（作用：变换后的数据均值为0，极差为1，且|x ij*|<1，消去了量纲的影响；在以后的分析计算中可以减少误差的产生。）；Range 0 to 1（极差正规化变换 / 规格化变换）； 2. 构造关系矩阵 在SPSS中如何选择测度（相似性统计量）: →Analyze →Classify →Hierachical Cluster Analysis →Method 然后从对话框中进行如下选择 常用测度（选项说明）：Euclidean distance：欧氏距离（二阶Minkowski距离），用途：聚类分析中用得最广泛的距离；Squared Eucidean distance：平方欧氏距离；Cosine：夹角余弦(相似性测度；Pearson correlation：皮尔逊相关系数； 3. 选择聚类方法 SPSS中如何选择系统聚类法 常用系统聚类方法 a）Between-groups linkage 组间平均距离连接法 方法简述：合并两类的结果使所有的两两项对之 聚类分析原理及步骤 聚类分析原理及步骤——将未知数据按相似程度分类到不同的 类或簇的过程 1》传统的统计聚类分析方法包括系统聚类法、分解法、加入法、 动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用 k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名 的统计分析软件包中，如SPSS、SAS等。 典型应用 1》动植物分类和对基因进行分类 2》在网上进行文档归类来修复信息 3》帮助电子商务的用户了解自己的客户，向客户提供更合适 的服务 主要步骤 1》数据预处理——选择数量，类型和特征的标度((依 据特征选择和抽取)特征选择选择重要的特征，特征抽取把输入的特征转化 为一个新的显著特征，它们经常被用来获取一个合适的特征集来为避免“维数灾”进行聚类)和将孤立点移出数据(孤立点是不依附于一般数 据行为或模型的数据) 2》为衡量数据点间的相似度定义一个距离函数—— 既然相类似性是定义一个类的基础，那么不同数据之间在同一个特 征空间相似度的衡量对于聚类步骤是很重要的，由于特征类型和特 征标度的多样性，距离度量必须谨慎，它经常依赖于应用，例如， 通常通过定义在特征空间的距离度量来评估不同对象的相异性，很 多距离度都应用在一些不同的领域一个简单的距离度量，如 Euclidean距离，经常被用作反映不同数据间的相异性，一些有关相 似性的度量，例如PMC和SMC，能够被用来特征化不同数据的概 念相似性，在图像聚类上，子图图像的误差更正能够被用来衡量两 个图形的相似性 3》聚类或分组——将数据对象分到不同的类中【划分方法 (划分方法一般从初始划分和最优化一个聚类标准开始，Crisp Clustering和Fuzzy Clusterin是划分方法的两个主要技术，Crisp Clustering，它的每一个数据都属于单独的类;Fuzzy Clustering，它的每个数据可能在任何一个类中)和层次方法(基于某个标准产生一 个嵌套的划分系列，它可以度量不同类之间的相似性或一个类的可分 离性用来合并和分裂类)是聚类分析的两个主要方法，另外还有基于 密度的聚类，基于模型的聚类，基于网格的聚类】 4》评估输出——评估聚类结果的质量(它是通过一个类有效索引来 评价，，一般来说，几何性质，包括类间的分离和类内部的耦合，一般都用来评价聚类结果的质量，类有效索引在决定类的数目时经常扮演 了一个重要角色，类有效索引的最佳值被期望从真实的类数目中获取，一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳 值，这个索引能否真实的得出类的数目是判断该索引是否有效的标准，很多已经存在的标准对于相互分离的类数据集合都能得出很好的结 果，但是对于复杂的数据集，却通常行不通，例如，对于交叠类的集合。) 聚类分析的主要计算方法原理及步骤划分法 1》将数据集分割成K个组(每个组至少包 聚类算法: 1. 划分法：K-MEANS算法、K-M EDOIDS算法、CLARANS算法； 1）K-means 算法： 基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。 K-Means聚类算法主要分为三个步骤： (1)第一步是为待聚类的点寻找聚类中心 (2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去 (3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2： (a)未聚类的初始点集 (b)随机选取两个点作为聚类中心 (c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 (e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 优点： 1.算法快速、简单; 2.对大数据集有较高的效率并且是可伸缩性的; 3.时间复杂度近于线性，而且适合挖掘大规模数据集。 缺点： 1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。CLOPE-快速有效的聚类算法
聚类分析原理及步骤
(完整word版)各种聚类算法介绍及对比
基于关键帧提取的静态视频摘要技术研究
(完整版)聚类算法总结
一种基于密度的快速聚类算法
各种聚类算法的比较
一种基于K-Means局部最优性的高效聚类算法
聚类分析法总结
SPSS软件聚类分析过程的图文解释及结果的全面分析
聚类分析原理及步骤
聚类算法比较
相关主题
文本预览