异构数据的结构熵聚类算法_李志华
第38卷 第2期2011年2月计算机科学Computer Science Vo l .38No .2Feb 2011
到稿日期:2010-03-24 返修日期:2010-07-09 本文受国家自然科学基金青年科学基金项目(60704047),2007年度教育部高等学校创新工程重大培育项目资助。
李志华(1969-),男,博士,副教授,硕士生导师,主要研究方向为优化理论、智能信息处理、模式识别和网络技术,E -mail :ezh l i @yahoo .com .cn ;顾 言(1974-),男,硕士生;陈孟涛(1986-),男,硕士生;王士同(1964-),男,教授,博士生导师,主要研究方向为人工智能、模式识别、模糊系统、生物信息学;陈秀宏(1964-),男,博士后,教授,主要研究方向为模式识别、模糊系统、图像处理。
异构数据的结构熵聚类算法
李志华1 顾 言1 陈孟涛1 王士同1 陈秀宏2
(江南大学信息工程学院 无锡214122)1 (江南大学数字传媒学院 无锡214122)
2
摘 要 研究了语义数据的聚类问题,提出了一种基于样本内在结构的结构熵聚类SEC 算法。通过给出语义属性相
异性度量测度的新定义,挖掘蕴含于数据样本中的结构信息,提出了一种根据结构信息计算样本信息熵的优化方法,即通过熵来确定样本的聚类中心,从而完成样本的聚类,并把此方法向异构数据进行了拓展。SEC 算法能实现不平衡数据的聚类,能自动确定初始类中心和聚类数目,具有无需迭代、效率高和相当的鲁棒性优势。实验表明,算法是有效的,与文献中的已有方法相比,聚类准确率得到显著提高,具有一定的实用价值。关键词 异构数据,相异性度量,聚类线索,结构熵,聚类算法中图法分类号 T P393 文献标识码 A
Structure -based Entropy Clustering Algorithm for Heterogeneous Data
L I Zhi -hua 1 G U yan 1 CHEN M eng -tao 1 W A NG Shi -tong 1 CH EN Xiu -ho ng 2
(S hool of Information and Engineerin g ,Jiangnan University ,W uxi 214122,C hina )
1
(Digital M edia College ,Jiangn an University ,Wu xi 214122,China )
2
A bstract T he dissimilarity measur e and clustering appro ach about the heterog eneo us datase t w ere studied ,and a struc -tur e -based entr opy clustering S EC alg orithm was presented in this paper .Data often do appear in homo geneous g roups ,the SEC utilizes these st ruc tur al info rmatio n to impro ve the cluste ring accuracy .U nlike the distributio n o f numeric da -ta ,no minal data are o ften unbalancedly distributed ,whose distributio n a re often unrelated with their distance measure ,due to the above ,a new structural info rma tion -ba sed e nt ropy co mputing technolog y w as pro po sed .By mining the clues in st ructura l informa tion ,co nstructing the weig ht implying the different dist ribution info rma tion o f nominal a nd nume ric attributes ,the SEC can automatically identifies the initial locations and numbe r of cluster centriods ,and ex hibits its ro -bustness to initialization and no itera tion in algo rithm .Experimental results co mpa ring w ith o ther reference s demo n -st rate that the pr oposed method has pr omising per forma nce .
Keywords H eterog eneo us data ,Dissimilarity measur e ,Clustering clue ,Str uctural entropy ,Clustering alg orithm
1 引言
聚类分析的主要任务是通过挖掘样本中的各种聚类线索,从而有效地选择聚类算法中的合适参数,以达到确定最佳聚类数目的目的。当前,很多数据样本,如网络安全事件、网页分类和疾病诊断数据等,这些数据集的组成复杂,存在着大量“构造相似”的同质样本[1],同时其属性组成呈异构性特点,既有语义属性又有连续属性,而语义属性的数据类型又可能是字符、二值属性和一些具有枚举数据特征的数值等,表现出鲜明的结构特征。
研究语义属性样本的聚类,必须首先能有效地确定聚类中心,并实现对异构属性相异性的同时度量。由于语义属性数据分布固有的无序性,样本的分布不平衡、分布与空间距离无关[2],因此对其相异性度量比较困难,造成现今大多数聚类
算法不能实现语义属性数据、异构属性数据的聚类。如著名的FCM 算法就不能实现这两种数据集的聚类。只有少数几个从k -均值算法演变而来的算法[3-5]能实现语义属性数据的聚类,只有基于混合属性数据(k -proto type )的聚类算法[6]等能实现异构属性数据的聚类。但算法或多或少存在一些不足,如需要处理大量的二进制数据、对初始类中心敏感和需要选取特殊的模式[3-5]等。
虽然基于熵的聚类算法[7]已经存在,但同样不适宜异构属性数据的聚类,更没有充分挖掘样本中有利于聚类的结构线索。本文通过给出一种语义属性数据相异性度量测度的新定义,深入挖掘样本中的结构信息,根据信息理论构造了一种体现异构属性数据分布结构的计算熵的新方法,在充分挖掘了样本中的聚类线索后提出了结构熵聚类(Str ucture -based Entro py Clustering ,SEC )算法,算法能实现语义属性数据和
异构属性数据的聚类。
2 相异性度量
假设有样本集x i ∈X ,x i =(x i 1,x i 2,…,x il ,x i (l +1),…,
x i (l +m )
)T
,1≤i ≤n ,且前l 维为语义属性,后m 维为连续属性,即X 为异构数据集。2.1 语义属性相异性度量的计算
对于语义属性数据的聚类算法的研究,最为关键的就是聚类对象(如样本、聚类中心等)间相异性的定义,又称距离的定义。已有算法中已有不同的定义方法[2-6]。以下给出一种新的相异性度量测度的定义,对语义属性样本进行相异性度量。为了讨论方便,假设X 中仅包含前l 维语义属性。则语义属性的相异性度量测度定义如下。
定义1 语义属性的相异性度量测度:s (x i ,x j )=∑l
p =1θ(x ip ,x jp )
θ(x ip ,x jp )=
1, x ip =x jp
0, x ip ≠x jp
(i ≠j ,1≤i ≤n ,1≤j ≤n ,1≤p ≤l )d (x ip ,x jp )=[dim s -s (x i ,x j )]/dim s
(1)
式中,dim s 是语义属性数据的维数。则语义属性样本间的差
为x i -x j =D S (x i ,x j ),其中D S (x i ,x j )形式化地定义为
D S (x i ,x j )=(d (x i 1,x j 1),d (x i 2,x j 2),…,d (x il ,x jl ))
T
(2)
为了进一步计算传统意义上的”距离”,即相异性度量测
度,对于语义属性而言,可以采用Euclidean 距离或M aha -lanobis 距离等具体形式计算。
根据距离度量的性质不难证明,式(1)满足距离的非负性、自反性和对称性,但不能总是满足三角不等式原则,即式(1)实质上是一个度量异构样本集的广义(G ene ralized )距离测度。
2.2 异构距离的计算
本文选用M ahala nobis 距离的基本形式,用加权的M a -halano bis 距离计算异构距离,因为M ahalanobis 距离考虑了样本的协方差,协方差越大,M ahalanobis 模越小,体现了样本的结构[2]。同时,为了计算方便,给出异构样本之间差的形式化表示:
x i -x j =(D S (x i ,x j ),x i (l +1)-x j (l +1),…,x i (l +m )-x j (l +m )
)T
(3)
式中,D S (x i ,x j )见式(2)。
另一方面,从样本的内在结构出发构造一个权重,给M a -halano bis 距离加权,这个权值体现了样本分布中的不平衡信息。算法区分两种情况来分别计算异构样本之间的距离:当
两个样本属于同一类时,其间的M ahalano bis 距离用式(4)计算:
D m (x i ,x j ,∑)=(x i -x j )T
∑-1(x i -x j )
(4)
当两个样本属于两个不同的类S i ,S j 时,其间的距离用加权的M ahalanobis 距离如式(5)进行计算
[1]
:
D wm (x i ,x j )=
s i s i + s j D 2m (x i ,x j ,∑i )+ s j
s i + s j D 2m (x i ,x j
,∑j )
(5)
式中,∑为相应的样本的协方差:∑=1S X T X -1 S
2X T
1
S
1T S X 。若∑为奇异矩阵,则计算它的伪逆:
∑+=A T G -1A ,其中G 是一个仅包含∑正的特征值的对角矩阵,A 是一个包含∑的特征向量的单位正交矩阵; S i , S j 是相应类的一阶范数。式(5)更好地体现了样本的结构特征,充分挖掘了样本集中的结构信息。
3 结构熵聚类算法
3.1 熵及EFC 算法简介
据信息论可知,熵是信息度量的一个有力工具,通常作为某信源所蕴含的信息量的度量,即不确定性的度量。不确定性越小,即概率越大,则熵就越小,相应的信息量也就越小。而对数据样本集而言,熵可以度量一个随机变量的不确定性,度量数据样本集中数据元素依赖关系强弱的程度;从平均意义上而言,熵是随机变量总体信息测度的一个表征[7]。所以文献[7]提出了一种基于样本间相似性度量的熵计算方法,如式(6)所示,并提出了一种基于熵的模糊聚类(Entro py -based fuzzy clustering ,EF C )算法[7]。算法逐个计算每一个样本相对于其它样本的熵,并通过标准
化处理,使熵值在区间[0.0,1.0]之内。若熵值趋近于区
间的下限值0时,说明样本离得很近或很远(如离群样本);若熵值趋近于区间的上限值1时,样本以接近该样本集的平均分布距离分布。可见,在不考虑离群样本的情况下,对于熵值趋近于0的样本,说明其周围样本分布的密度比较大,可以将其选作为聚类中心,这就是EF C 算法的精髓。
E i =-∑j ≠i
j ∈X (S ij log 2S ij +(1-S ij )log 2(1-S ij ))
(6)
式中,S ij 用样本间的欧氏距离计算S ij =ex p (-αD ij ),是样本
x i 和样本x j 之间的相似性度量,α表示指数函数的曲率,估算成α=-ln0.5/D ,D 表示数据集的平均距离。EFC 算法的主要思想:用熵值最小的样本充当聚类中心,用相似性来度量聚类。EF C 算法的最大优点是算法中无需迭代,只需遍历样本数据集一遍,算法的效率高。3.2 异构数据结构熵的计算
异构数据具有明显的结构特征。不仅有样本组成方面的特殊结构,而且有“维”组成方面的特殊性。由于不同的属性具有不同的分布特征,根据信息论可知,它们所包含的信息量不同。在本节的算法中,通过分别计算不同类型属性的熵,再通过加权计算成样本的熵,式(7)从样本“维”的角度同样挖掘了样本中的组成结构信息。
E i =ωE n ij ′+(1-ω)E s ij ″,(
1≤i ≤n ,1≤j ′≤m ,1≤j ″≤l )(7)
式中,ω称为属性权重,用来调整不同类型属性对样本x i 熵
的贡献,E n ij ′,E s
ij ″分别为样本的连续属性和语义属性的熵。此时,为了充分地挖掘样本结构中的聚类线索,式(6)中的相似性系数S ij 中的欧氏距离用式(4)或式(5)所示的异构距离代替。
显然,式(7)的一个关键就是属性权重ω的选择。由于j ′表示的是样本x i 中连续属性的维数,j ″表示的是x i 中语义属性的维数,j ′+j ″才是样本x i 的维数,因为ω的取值在[0,1]之间,理论上讲有无穷多个取值。为了缩短算法的训练时间,提高属性权重系数ω的准确度,我们假设ω是j 的函数。这
样ω的选择就变成一个多目标优化问题,描述如下: min{E i=(E n ij,E s ij)}
0≤ω≤1
(8)式(8)是该优化问题的一个妥协模型。为了求得模型的妥协解,把此多目标优化问题转换成单目标优化问题。根据非线性规划中的α-法求解[8]方法,给出一种近似α-法求解的ω参数的估算方法,过程描述如下:
假设
E n ij＊
1=min
1≤j≤n
E n ij′
E s ij＊
2=min
1≤j≤n
E s ij″
根据α-法求解法的性质[8],有
E n ij＊
2≥E n ij＊
1
E s ij＊
1≥E s ij＊
2
属性权重ω最后估算成
ω=E s ij＊
1
-E s ij＊
2
(E n ij＊
2-E n ij＊
1
)+(E s ij＊
1
-E s ij＊
2
)
(9)
式中,E n ij＊
1,E s ij＊
2
分别为对应样本的连续属性和语义属性的熵
值的最小值,E s ij＊
1,E n ij＊
2
分别为对应样本的语义属性和连续属
性的熵值的平均值。这一方法可以为异构样本估算一个参考的属性权重ω,是一个近似寻优的方法,起到了明显缩短算法训练时间的作用。
3.3 结构熵聚类算法
对于样本的聚类,可以把极小熵的样本作为聚类中心[7],用本文第2.1节定义的异构距离作为度量尺度完成样本聚类。于是,可以定义这样一个过程为聚类算法,样本集中的连续属性用文献[9]的方法进行离散化处理,算法具体描述如下。
算法1 结构熵聚类(St ruc ture-based Entro py Cluste-ring,SEC)方法
S tep1 初始化c=0,β,mat,c是聚类个数、β是度量阈值、ma t是距离权重矩阵;
S tep2 对异构样本,根据式(9)估算参数ω;
S tep3 根据式(7)计算样本的熵E;
S tep4 c=c+1;
S tep5 在未被聚类的样本中找E min=min
n
{E n},且令E(x k)=E m in, v c=x k,为第c类聚类中心;
S tep6 把满足条件D(x i,v c)<β的所有样本x i,假设v c表示存在的聚类中与x i最相近的那个聚类,则把x i聚成第v c类,并从
样本集X中删除x i;
S tep7 根据新的聚类结果刷新并修改距离权重矩阵mat;
S tep8 如果X为空,算法结束,否则转步骤4。
算法中距离权重矩阵mat的初始化方法是:首先产生一个随机值矩阵,并根据训练样本对矩阵元素进行第一轮“权重值”的替代,这样首先得到一个真实值和随机值混合的权重矩阵mat;距离权重矩阵mat的刷新方法是,当算法执行到步骤7时,在测试样本中,对于那些训练样本中已出现过的类,矩阵元素保持不变。对于新出现的样本,若无法成功聚类,就把它们当成一个新类,并重新计算相关的距离权重值,并刷新矩阵mat。
以上算法产生c个聚类,聚类中心用v i(1≤i≤c)表示。不难看出,该算法从相当程度上把有关熵聚类的算法在语义属性数据、异构数据上进行了有效的推广。并且,从式(7)可知,当属性权重值ω=1时,算法演变为一个纯连续属性样本的聚类算法,即基于加权M ahalanobis距离度量的熵聚类算法;当属性权重值ω=0时,算法演变为一个纯语义属性样本的聚类算法。该特性大大增强了有关熵聚类算法的应用范围。
3.4 SEC算法的时空复杂度分析及特点
SEC方法的空间开销主要来自两部分:样本存储的空间复杂度O(n)、在求每个样本熵时的相似性度量存储空间开销n(n-1)/2,所以最坏情况下的空间复杂度为O(n2);时间复杂度方面,SEC方法的本质是一个聚类过程,根据文献[10]可知,从总体上而言,SEC方法的时间复杂度就是其期望复杂度O(nk m),其中n是样本个数、k是聚类个数、m是属性的维数,这样的复杂度通常达不到平方阶O(n2)。但是,因为算法中的第4步涉及到样本间的相似性计算,所以当以样本间“相似性计算”为基本操作时,算法在最坏情况下的时间复杂度还是为O(n2)。
通过分析研究,SEC方法具有如下特点:
(1)算法无需迭代,能一次性确定聚类中心;
(2)算法充分地挖掘了样本集中的各种聚类线索,如样本的组成结构和维组成信息;
(3)类中心的选择方法决定算法对初始类中心的选择不敏感和不容易收敛到局部极小值;
(4)算法拓展了基于熵聚类算法的应用范围。
4 仿真实验及分析
算法的调试环境是M A T L A B7.0,在具有P IV2.4G H z CP U、1G B内存、Window s XP操作系统的机器上运行。
本节引进一个聚类准确率γ的概念,是指各个类中所有被正确聚类的样本数总和与样本集样本总数的比值,如式(10)所示:
γ=
∑c
i=1
number i
n
(10)式中,number i为第i类中被正确聚类的样本个数,n为样本的总数。γ值越大,就说明聚类准确度越高,聚类效果越好;越小,则刚好相反。
为了评价SEC算法对语义属性数据、异构属性数据的聚类能力,仿真实验使用了一个纯语义属性数据样本集和两个异构属性数据样本集。样本集的组成如表1所列[11],它们充当仿真实验的测试样本。训练样本从原始样本中随机抽取,如表1所列。SEC算法均采用有监督学习的样本训练方式,并把SEC算法的聚类结果与文献[3-6]的结果进行比较。
表1 实验样本集的组成
样本名称属性类型样本数训练样本数维数类
Soy bean
disea se
cate go rical4725214 Flag
dataset
he teroge neous194100304 Kddcup99
dataset
he teroge neous181100415第1个so ybean样本集共分为4类,即4种疾病:P hy to-phtho ra Ro t,Diapor the S tem Canker,Charcoal Rot,Rhizocto-nian Roo t,样本个数分别为17,10,10,10,仿真实验仅选用其中的21维语义属性;第2个flag样本集,30维中有10维是
连续属性,其余20维是语义属性,是一个典型的异构属性数据集[6],可以根据该样本预测某个国家所在的地区、宗教信仰等,本文算法在去掉第1维国家名后,按照zone属性进行聚类,预测样本所属的象限为N E,SE,SW和NW,即4类,每类样本的个数分别为91,29,16和58;第3个是从kddcup99的10%标准子集中随机抽取的样本集,共有5类:normal, smur f,land,pod,ipsweep,相应样本的数量分别为32,100, 47,1,1。
So ybean数据集是国际公认[3-5]的语义属性数据样本集,所以它是进行算法比较的主要样本数据集。通过多次实验,当参数值β=9.6时,SEC算法聚类效果最佳,聚类准确率γ=93.62%,聚类结果如表2所列。并把该算法同文献[3]的硬k-mode s算法、文献[4]的模糊k-mo des算法从聚类准确率、聚类稳定性的角度进行比较,硬k-modes算法和模糊k-mode s算法的参数α=1.1,初始模式(initial mo des)选用文献[3]中提供的,比较结果如表3所列。由于文献[3,4]两种经典的语义属性数据聚类算法,在聚类的过程中,每次迭代均需要重新计算新的聚类中心,造成算法对初始类中心敏感,因此每两次间聚类的效果不一定相同。进一步在表3中给出了上述两种算法、概念k均值(Conceptual K-means,CK M)聚类算法[5]和本文的SEC算法的100次聚类运算的聚类准确度的统计平均值的比较。这一指标体现了算法的聚类稳定性, S EC算法明显高于参与比较的算法,但SEC算法的聚类准确率低于文献[4]的模糊k-mo des算法的最佳聚类准确率γ= 95.7%。
表2 S EC对soybean数据集的聚类结果
No.of cluste rβ=9.6
1234
A ctual110
Class210
L abel373
417
表3 不同算法对s oyb ean数据集的聚类准确率比较(100次统计平均)
Conceptua l K-me ans
H ard
k-m odes
Fuzzy
k-m ode s
SEC
准确率(%)70.4078.207993.62
对flag样本集的聚类,当属性权重参数ω∈[0.6,0.7]时,算法的鲁棒性最好。度量阈值β=45.5时,样本被正确地聚成4类,聚类准确率γ=80.928%。聚类效果如表4所列,虽然同文献[6]的参照属性不同,但单纯从聚类准确率γ而言,明显高于文献[6]的66%。并且从表4可以看出,被错分的样本仅19个。
表4 S EC对flag数据集的聚类结果
No.of clusterβ=45.5
1234
A ctual1190
Class229
L abel316
438182
kddcup99样本集,其结构复杂,是一个分布不平衡的样本数据集[1]。当把样本聚成6类,属性权重参数ω∈[0.6,0.7]时,聚类结果如表5所列,其中第3,4类可以认为是噪音数据,此时的聚类准确率γ=98.34%,并仅有1个样本被错分。
表5 SEC对kddcup99数据集的聚类结果
No.of cluste rβ=18.9
123456
A ctua l11130
Class2100
Label347
41
51
通过实验发现,SEC算法具有比较高的聚类准确率、更高效的算法运行效能、更佳的聚类稳定性和更好的鲁棒性,能实现高维的语义属性数据和异构属性数据的聚类。
结束语 异构属性数据的分布特殊,样本分布不平衡,样本集中往往蕴含有各种有利于聚类的线索,充分挖掘它们,能显著提高聚类性能。本文通过对语义属性、异构属性相异度量的研究和挖掘样本中的结构线索,提出了一种结构熵聚类SEC算法。SEC算法继承了EFC算法的优点,是一种非监督学习的聚类算法,文中总结了此算法的优点。通过仿真实验及同其它算法的比较,说明此算法具有比较好的算法聚类性能。由于聚类结果对距离权重矩阵的依赖性比较大,所以更高效地挖掘样本中的结构信息是下一步的研究重点。
参考文献
[1]W ang De-feng,Yeung D S,T san g E C C.Weighted M ahalanobis
Distance Kernels for Support Vector M achines[J].IEEE T ran-s action on Neu ral Netw orks,2007,18(5):1453-1462
[2]Kim M,Ramak rishn a R S.Projected Clus tering for Categorical
Datasets[J].Pattern Recognition Letters,2006,27(12):1405-1417
[3]H uang Zhexue.Exten s ions to the k-M eans Algo rith m for Clu s-
tering Large Data Sets w ith Categorical Values[J].Data M ining and Know ledge Discovery,1998,2(3):283-304
[4]H uang Zhe-x ue,Ng M K.A Fu zzy k-modes Algorith m for Clu s-
tering Categorical Data[J].IEE E Transactions on Fuz zy S ys-tem,1999,7(4):446-452
[5]Ralamb on drainy H.A Con ceptual version of the k-means Algo-
rithm[J].Pattern Recognition Letter,1995,16(11):1147-1157 [6]C hen Ning,Ch en A n,Zhou Long-xiang.Fuzzy k-prototypes al-
go rithm for clu stering mixed numeric and categorical valued data [J].Journal of Software,2001,12(8):1107-1119
[7]Yao J,Dash M,Tan S T,et al.E ntropy-based fuzzy clus tering
and fuzzy modeling[J].FUZZY S ets and Sy stems,2001,113
(3):381-388
[8]陈宝林.最优化理论与算法[M].北京:清华大学出版社,2005
[9]郭山清,谢立,曾英佩,入侵检测在线规则生成模型[J].计算机
学报,2006,29(9):1523-1531
[10]Jiang S heng-yi,S ong Xiao-yu,W ang Hui,et al,A clu stering-
b ased m ethod for uns upervis ed intrusion detection s[J].Pattern
Recognition Letters,2007,28(13):989-1003
[11]UC I repository of machine learning database[EB/OL].h ttp://
w w w.ics.UC https://www.wendangku.net/doc/0f9690327.html,/～mlearn/M LRepository.html,1998
数据挖掘考试题目聚类
数据挖掘考试题目——聚类 一、填空题 1、密度的基于中心的方法使得我们可以将点分类为：__________、________ 、_________。 2、DBSCAN算法在最坏的情况下，时间复杂度是__________、空间复杂度是__________。 3、DBSCAN算法的优点是_______、__________________________。 4、DBSCAN算法的缺点是处理_________________、_____________的数据效果不好。 5、DBSCAN算法的参数有：___________、____________。 6、簇的有效性的非监督度量常常可以分为两类：__________、__________，它常采用的指标为__________。 7、簇的有效性的监督度量通常称为___________，它度量簇标号与外部提供的标号的匹配程度主要借助____________。 8、在相似度矩阵评价的聚类中，如果有明显分离的簇，则相似度矩阵应当粗略地是__________。 9、DBSCAN算法的参数确定的基本方法是观察____________________的特性。 10、不引用附加的信息，评估聚类分析结果对数据拟合情况属于__________技术。 答案： 1、核心点边界点噪声点 2、O(n2) O(n) 3、耐噪声能够处理任意大小和形状的簇 4、高维数据变密度的 5、EPS MinPts 6、簇的凝聚性簇的分离性均方差(SSE) 7、外部指标监督指标的熵 8、块对角的 9、点到它的第K个最近邻的距离（K-距离） 10、非监督 二、选择题 1、DBSCAN算法的过程是（B）。 ①删除噪声点。 ②每组连通的核心点形成一个簇。 ③将所有点标记为核心点、边界点和噪声点。 ④将每个边界点指派到一个与之关联的核心点的簇中。 ⑤为距离在Eps之内的所有核心点之间赋予一条边。 A：①②④⑤③ B：③①⑤②④ C：③①②④⑤ D：①④⑤②③ 2、如果有m个点，DBSCAN在最坏的情况下的时间复杂度度为（C）。 A O(m) B O(mlogm) C O(m2) D O(logm) 3、在基本DBSCAN的参数选择方法中，点到它的K个最近邻的距离中的K选作为哪一个参数（B）。 A Eps B MinPts C 质心 D 边界
数据挖掘中的聚类分析方法
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
《数据挖掘》试题与标准答案
一、解答题（满分3０分，每小题5分) 1. 怎样理解数据挖掘和知识发现的关系?请详细阐述之 首先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式;然后,调用相应的算法生成所需的知识;最后对生成的知识模式进行评估，并把有价值的知识集成到企业的智能系统中。 知识发现是一个指出数据中有效、崭新、潜在的、有价值的、一个不可忽视的流程，其最终目标是掌握数据的模式。流程步骤:先理解要应用的领域、熟悉相关知识，接着建立目标数据集，并专注所选择的数据子集;再作数据预处理，剔除错误或不一致的数据；然后进行数据简化与转换工作；再通过数据挖掘的技术程序成为模式、做回归分析或找出分类模型；最后经过解释和评价成为有用的信息。 2.时间序列数据挖掘的方法有哪些，请详细阐述之 时间序列数据挖掘的方法有: １)、确定性时间序列预测方法:对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。 ２）、随机时间序列预测方法：通过建立随机模型,对随机时间序列进行分析,可以预测未来值。若时间序列是平稳的,可以用自回归(Auto Ｒegressiｖe，简称AR)模型、移动回归模型(Ｍovｉng Ａveｒage,简称ＭＡ）或自回归移动平均(Aｕto Regrｅssive Moｖiｎg Aｖeraｇe，简称AＲMＡ)模型进行分析预测。 3)、其他方法:可用于时间序列预测的方法很多,其中比较成功的是神经网络。由于大量的时间序列是非平稳的,因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型,用于时间序列的预测。
数据流聚类算法D-Stream
Density-Based Clustering for Real-Time Stream Data 基于密度的实时数据流聚类(D-Stream) 翻译by muyefei E-mail: muyefei@https://www.wendangku.net/doc/0f9690327.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的数据流算法。它有两项主要的技术挑战： 首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减
1基于网格的数据流聚类算法
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
一种利用信息熵的群体智能聚类算法
---------------------------------------------------------------最新资料推荐------------------------------------------------------ 一种利用信息熵的群体智能聚类算法 !#$%计算机工程与应用前言数据挖掘是一个多学科交叉的研究领域，涉及数据库技术、人工智能、机器学习、统计学、知识获取、生物计算等学科。 这些学科的发展为数据挖掘的研究提供了新的机遇与挑战。 聚类是数据挖掘的重要任务之一，目前主要的聚类算法可以划分为如下几类()： 划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法等。 这些方法大多数需要一些参数限制，设定聚的数目，而且聚类结果对初始状态及参数非常敏感。 近年来，一些学者开始应用群体智能（*+,-. /01233452062）(!)的思想研究聚类问题。 因为群体智能源于对简单个体组成的群落社会系统的模拟，如蚁群、蜂群，在没有任何先验知识和无统一指挥的分布环境下，它们具有自我组织、合作、通信等特点。 在文献(%)中，720289:8-5 等首次模拟幼蚁自动分类（即较小的幼虫在中心，较大的幼虫在外围）及蚁尸聚积现象，提出了聚类基本模型。 随后 ;8.2- 和 ,421, 在文献(#)中改进了 720289:8-5的基本模型，提出了 ; 算法并应用于数据分析中。 1 / 12
虽然以上方法可以获得较好的聚类结果，但是需较长的计算时间，还需设置较多的参数。 文献(，=)采用群体智能与均值算法相结合的方法加快聚类速度。 论文在 ; 算法中利用信息熵来控制蚂蚁拾起和放下对象动作，既可以减少参数的个数，又可以加快聚类的进程。 !蚁群聚类的基本模型和 ; 算法在自然界中，一些蚂蚁可以将蚁尸聚成公墓，也可将幼虫按大小分类。 720289:8-5 等根据这两种现象提出了两种模型(%)，两者的原理是一致的，即一群蚂蚁在一个二维区域内任意移动，允许按规则拾起和放下物体。 一个任意移动的未载物体的蚂蚁拾起一个物体的可能性 !按公式（）计算；一个任意移动的载有物体的蚂蚁放下一个物体的可能性 !#按公式（!）计算，其中 $是蚂蚁周围物体的个数，%和 %!均为常数。 !?%%@$!（）#?$%!@$!!（!）;8.2- 和 ,421, 在文献(#)中，基于 720289:8-5 的基本模型，提出了以下算法： A B/0414,34C,14:0 B A:- 2D2-E 412. F:G3,62 -,0F:.3E :0 5-4FH0F :-:- ,33 ,5201I F:G3,62 ,5201 ,1 -,0F:.3E I232612F I412H0F :-A B J,40 3::G B A:- (? 1: (.,K F::- ,33 ,5201I F:/L （（,5201 803,F20）,0F （I412 :668G42F 9E 412. ））1M20N:.G812 $ （）,0F （）7-,+ -,0F:. -2,3 08.92- ) 921+220 ,0F /L （)!
数据挖掘考试题精编版
数据挖掘考试题 公司内部编号：（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}合并
一种基于粒子群算法的聚类算法
第35卷第1期2009年3月延边大学学报(自然科学版) Journal of Yanbian University (Natural Science )Vol.35No.1Mar.2009 收稿日期:2008-10-18 作者简介:姜浩(1981— ),男,硕士研究生,研究方向为粒子群算法.文章编号:100424353(2009)0120064204 一种基于粒子群算法的聚类算法 姜浩, 崔荣一 (延边大学工学院计算机科学与技术系智能信息处理研究室,吉林延吉133002) 摘要:提出一种基于粒子群算法的聚类算法,该算法利用粒子群算法随机搜索解空间的能力找到最优解.首先,将样本所属类号的组合作为粒子,构成种群,同时引入极小化误差平方和来指导种群进化的方向.其次,通过对全局极值的调整,搜索到全局最优值.最后,通过仿真实验的对比,验证了该算法在有效性和稳定性上要好于K 2means 算法. 关键词:粒子群;聚类;极小化误差平方和中图分类号:TP301.6 文献标识码:A A Method of Clustering B ased on the P article Sw arm Optimization J IAN G Hao , CU I Rong 2yi (I ntelli gent I nf ormation Processing L ab.,De partment of Com puter Science and Technolog y , College of Engineering ,Yanbian Universit y ,Yanj i 133002,China ) Abstract :A clustering method based on the particle swarm optimization is provided ,using the ability of PSO algorithm which can search all of the solution space to find the optimum solution.Firstly ,the combination of the cluster number of the samples was taken as particles to consist a swarm.Meanwhile ,the evolution trend was used to modulate with the theory of the L MS error criterion.Secondly ,according to the modulating for global best ,the algorithm researched the global optimum.Finally ,the simulation results show that the new algorithm of proposed algorithm is more efficient and stable than K 2means algorithm.K ey w ords :particle swarm optimization ;clustering ;L MS error criterion 0 引言 聚类分析研究具有很长的历史,其重要性及 与其他研究方向的交叉特性得到人们的肯定[1].聚类是数据挖掘、模式识别等研究方向的重要研究内容之一,在识别数据的内在结构方面具有极其重要的作用.聚类技术广泛应用于语音识别、字符识别、图像分割、机器视觉、数据压缩和文献信息检索等领域.聚类的另一主要应用是数据挖据(多关系数据挖掘)、时空数据库应用(GIS 等)、序列和一类数据分析等.此外,聚类还应用于统计科学.值得一提的是,聚类分析对生物学、心理学、考 古学、地质学、地理学以及市场营销等研究也都有重要应用. 粒子群优化(Particle Swarm Optimization ,PSO )算法是由Eberhart 和Kennedy [2]于1995年提出的一类基于群智能的随机优化算法.该算法模拟鸟群飞行觅食的行为,通过个体之间的集体协作和竞争来实现全局搜索,是一种基于群智能的演化计算技术.同遗传算法相比,虽然同是基于迭代的进化算法,但没有交叉和变异算子,群体在解空间中根据自身经历的最好位置,以及群体最优解来进行搜索.由于PSO 算法有着参数少,
聚类分析、数据挖掘、关联规则这几个概念的关系
聚类分析和关联规则属于数据挖掘这个大概念中的两类挖掘问题， 聚类分析是无监督的发现数据间的聚簇效应。 关联规则是从统计上发现数据间的潜在联系。 细分就是 聚类分析与关联规则是数据挖掘中的核心技术； 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。 聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。 从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets)，第二阶段再由这些高频项目组中产生关联规则(AssociationRules)。 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。 关联规则挖掘的第二阶段是要产生关联规则(AssociationRules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(MinimumConfidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。
数据挖掘主要算法
朴素贝叶斯： 有以下几个地方需要注意： 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回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为： 到整个样本的后验概率：
数据挖掘实验报告-聚类分析
数据挖掘实验报告（三） 聚类分析 姓名：李圣杰 班级：计算机1304 学号：1311610602
一、实验目的 1、掌握k-means 聚类方法； 2、通过自行编程，对三维空间内的点用k-means 方法聚类。 二、实验设备 PC 一台，dev-c++5.11 三、实验内容 1.问题描述： 立体空间三维点的聚类. 说明：数据放在数据文件中(不得放在程序中)，第一行是数据的个数，以后各行是各个点的x,y,z 坐标。 2.设计要求 读取文本文件数据，并用K-means 方法输出聚类中心 3. 需求分析 k-means 算法接受输入量k ；然后将n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： 2 1∑∑=∈-=k i i i E C p m p (1) 其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 四、实验步骤 Step 1.读取数据组，从N 个数据对象任意选择k 个对象作为初始聚类中心； Step 2.循环Step 3到Step 4直到每个聚类不再发生变化为止； Step 3.根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； Step 4.重新计算每个（有变化）聚类的均值（中心对象）。 代码 #include
数据挖掘第三版第十章课后 习题答案
10.1 简略介绍如下聚类方法：划分方法、层次方法。每种给出两个例子。 (1)划分方法：给定一个有N个对象的集合，划分方法构造数据的K个分区，每一个分区表示一个簇，且K≤N。而且这K个分组满足下列条件：第一，每一个分组至少包含一条记录；第二，每一条记录属于且仅属于一个分组(注意：这个要求在某些模糊聚类算法中可以放宽)；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的记录越远越好。 使用这个基本思想的算法有：K-MEANS 算法、K-MEDOIDS 算法、CLARANS 算法。 (2)层次方法：这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”方案中，初始时每一个数据记录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。 代表算法有：BIRCH 算法、CURE 算法、CHAMELEON 算法等。 10.2 假设数据挖掘的任务是将如下的8个点（用(x, y)代表位置）聚类为3个簇。 A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9)距离函数是欧氏距离。假设初始我们选择A1、B1和C1分别为每个簇的中心，用k-均值算法给出： （a）在第一轮执行后的3个簇中心。 （b）最后的3个簇。 (a)第一轮后, 三个新的簇为(1){A1} (2){B1,A3,B2,B3,C2} (3){C1,A2} 簇中心分别为(1) (2, 10), (2) (6, 6), (3) (1.5, 3.5).
数据挖掘关于Kmeans算法的研究(含数据集)
浙江大学算法研究实验报告 数据挖掘 题目：K-means
目录 一、实验内容 (5) 二、实验目的 (7) 三、实验方法 (7) 3.1软、硬件环境说明 (7) 3.2实验数据说明 (7) 图3-1 (7) 3.3实验参数说明/软件正确性测试 (7) 四、算法描述 (9) 图4-1 (10) 五、算法实现 (11) 5.1主要数据结构描述 (11) 图5-1 (11) 5.2核心代码与关键技术说明 (11) 5.3算法流程图 (14) 六、实验结果 (15) 6.1实验结果说明 (15) 6.2实验结果比较 (21) 七、总结 (23)
一、 实验内容 实现K-means 算法，其中该算法介绍如下： k-means 算法是根据聚类中的均值进行聚类划分的聚类算法。 输入：聚类个数k ，以及包含n 个数据对象的数据。 输出：满足方差最小标准的k 个聚类。 处理流程： Step 1. 从n 个数据对象任意选择k 个对象作为初始聚类中心； Step 2. 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； Step 3. 重新计算每个（有变化）聚类的均值（中心对象） Step 4. 循环Step 2到Step 3直到每个聚类不再发生变化为止； k-means 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： 21∑∑=∈-=k i i i E C p m p (1) 其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 重点要求：用于聚类的测试级不能仅为单独的一类属性，至少有两种属性值参与聚类。
数据挖掘中的聚类算法综述
收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺 玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘 要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。 关键词:数据挖掘;聚类;聚类算法 中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1 引言 随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序 的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。 本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2 DM 中现有的聚类算法 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。 聚类 层次聚类算法 聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类 分割聚类算法基于密度的聚类基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类:概率聚类、最近邻 聚类、K 2medoids 、K 2means 基于约束的聚类算法 机器学习中的聚类算法 人工神经网络方法 基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法 子空间聚类 联合聚类 图1 聚类算法分类示意图 211 层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代 表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用 单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以