基于数据场的粗糙聚类算法
第36卷 第2期2009年2月计算机科学Comp uter Science Vol.36No.2Feb.2009
到稿日期:2008203220 本文受国家自然科学基金资助项目(60475019,60775036),2006年博士学科点专项科研基金(20060247039)资助。李 学(1984-),男,硕士生,研究方向为数据挖掘、粗糙集,E 2mail :lixue0501@hot https://www.wendangku.net/doc/be11587134.html, ;苗夺谦 教授,博士生导师,主要研究方向为粗糙集、数据挖掘、粒度计算;冯琴荣 博士生,研究方向为粒度计算。
基于数据场的粗糙聚类算法
李 学 苗夺谦 冯琴荣
(同济大学计算机科学与技术系 上海201804)
摘 要 聚类分析是数据挖掘的研究热点。传统的聚类算法都是把一个对象精确地划分到一个聚类簇中,类别之间
的界限是非常精确的。随着Web 挖掘技术的发展,精确地划分每个对象的聚类算法面临着巨大的挑战。根据数据场理论和经典粗糙集理论所具有处理不精确与不确定性数据的特性,提出一种新的基于数据场的粗糙聚类算法,该粗糙聚类算法采用势值作为对象的划分依据,避免传统粗糙聚类算法一贯采用基于欧氏距离的划分方法。算法首先通过对数据对象进行粗分然后再不断迭代细分,直至形成稳定的聚类簇。实验分析过程中,把提出的算法与粗糙K 2means 算法和粗糙K 2medoids 算法进行了比较,结果表明该算法在交叉数据集上具有较好的聚类效果,而且收敛速度较快。关键词 粗糙聚类,数据场,势值,Davies 2bouldin 指标
R ough Clustering Algorithm B ased on Data Field
L I Xue MIAO Duo 2qian FEN G Qin 2rong
(Depart of Computer Science and Technology ,Tongji University ,Shanghai 201804,China )
Abstract Clustering analysis is the hotspot in Data mining ,all the conventional clustering algorithms precisely put the each object into one cluster ,the bounders between clusters are precise ,as the development of the Web mining ,clustering algorithms that precisely divide each object face great challenges.Based on the data field theory and classic rough set theory ’s character that processes the uncertainty and imprecise data ,a novel rough clustering algorithm based on data field was proposed ,it divides the objects through computing potential value ,which avoids the conventional rough cluste 2ring partition method based on euclidean distance.The approach iterates f rom rough to un 2rough incessantly till the sta 2ble clusters form.At the experimental analysis process ,we compared the algorithm that we proposed with rough K 2means algorithm and rough K 2medoids algorithm ,the result shows the algorithm that we proposed has better clusters on the crossed datasets and fast convergence.
K eyw ords Rough clustering ,Data field ,Potential value ,Davies 2bouldin index
1 引言
聚类算法是数据挖掘的研究热点。传统的聚类算法都是将一个对象精确地划分到一个聚类簇中,聚类簇之间的界限是非常精确的。随着Web 挖掘技术的迅速发展,保持聚类簇之间界限的严格精确性面临着巨大的挑战,聚类簇之间出现了模糊的界限。Joshi 和Krishnapuram 认为在Web 挖掘中聚类簇之间存在交集,对象不是精确地划分到每个聚类簇中,而是以不同的程度隶属于每个类[1]。粗糙集理论正是处理这种不精确与不确定数据的有效工具。P.Lingras 等人首次将粗糙集理论引入到数据聚类中来,其主要思想是将聚类簇看成是一个不确定的集合,通过粗糙集的上近似和下近似的概念来描述聚类簇的轮廓。粗糙聚类(Rough Clustering ,简称RC )算法应用到多个领域,而且取得了非常好的效果[2,3]。但是,目前的RC 算法在对象归属划分时,考虑的都是基于点与点之间的欧氏距离[4,5],忽视了待划分对象与聚类簇内其他对象的作用关系。而数据场理论认为空间中的对象是受到场
源作用的,对象在场源作用下产生势值,拥有相同势值的对象形成等势面,等势面以局部最大势值形成抱团簇。
本文根据数据场理论的相关知识,将数据场理论应用到RC 中来,提出了一种新的RC 算法。这种算法依据待划分对象的势值大小来进行划分,划分到聚类簇下近似中的对象肯定属于这个类。划分到聚类簇上近似中的对象可能属于这个类,也有可能不属于这个类,这样从初次粗分到不断迭代细分,直至形成稳定的聚类簇。
本文结构组织如下:第2节介绍RC 算法研究背景,包括目前主要应用的粗糙K 2means 算法和粗糙K 2medoids 算法,并对二者进行比较;第3节首先简要介绍一下数据场理论相关知识,接着给出基于粗糙模型的数据场势函数定义,然后给出基于数据场的RC 算法(Rough Clustering Algorithm based on Data Field )具体步骤;第4节是聚类算法实验结果比较分析,将本文提出的算法与粗糙K 2means 算法和粗糙K 2me 2doids 算法进行比较,算法采用Rough Davies 2Bouldin (RDB )来度量聚类效果,同时也对3种RC 算法的收敛速度进行了
比较;最后是总结。
2 RC 算法的研究背景
聚类是一种常见的数学分析工具。传统的聚类算法都是将每个对象归属到一个确定的类别信息中,类别之间的界限是非常精确的。但是随着Web 挖掘技术的发展,这种聚类算法面临着巨大的挑战。鉴于粗糙集具有处理不精确和不确定数据的优点,P.Lingras 等人首次将粗糙集理论引入到数据聚类中来,而且取得了很好的应用效果。目前基于RC 的算法主要有两种:粗糙K 2means 算法和粗糙K 2medoids 算法。2.1 粗糙K 2means 算法
粗糙K 2means 算法将对象划分到聚类簇的下近似和上近似,通过下近似和上近似计算新的聚类中心,然后重新划分对象。此过程反复进行,直到形成稳定的聚类结果。整个过程主要包括对象划分和聚类中心调整两个步骤。
粗糙K 2means 算法利用点之间距离的差值将N 个对象划分到K 个聚类簇的上下近似中,粗糙K 2means 算法聚类中心调整公式表示为:
如果 A m i -Am i ≠
Φ,m i =w lower
∑v j ∈Am i
v j
|A m i |
+w upper
∑v j ∈ A m i -Am i
v j
| A m i -Am i |
否则:m i =
∑v j ∈Am i
v j
| A m i |
粗糙K 2means 算法存在明显的局限性,即粗糙K 2means 算法对聚类簇交界的对象不能很好地分类,同时在重新计算
聚类中心以后,所有对象要根据新的聚类中心重新进行划分,因而迭代时间长、收敛速度慢。鉴于粗糙K 2means 算法存在的不足,G.Peters 在处理噪声数据方面对粗糙K 2means 方法进行了改进[6,7],S.Mitra 采用遗传算法优化粗糙K 2means 算法的参数[8]。在文献[9]中,K.Vogts 等人也采用遗传算法对粗糙K 2means 算法进行了改进。
2.2 粗糙K 2medoids 算法
K 2medoids 算法是Kaufman 提出的[10]。与传统K 2means 算法不同的是,K 2medoids 是用真实存在的对象来代表
聚类的质心。K 2medoids 算法以CPC (Compactness of the
clustering )作为算法迭代终止的度量准则。
C PC =∑K
k =1C PC (C k )
其中C PC (C k )=∑x n ∈C k
d (x n ,m k )
Peters 等人在粗糙K 2means 算法和经典K 2medoids 算法
的基础上提出了粗糙K 2medoids 算法。粗糙K 2medoids 就是引入粗糙集理论上下近似的概念,对经典K 2medoids 算法的
度量准则CPC 进行重新定义,即RCPC (Rough Compactness of the Clustering ):
RC PC =∑K
k =1RC PC (C k )
其中RC PC (C K )=w l ∑x n ∈C k
d (x n ,m k )+w b
∑x n ∈C k -C k
d (x n ,m k )
2.3 二者比较
粗糙K 2medoids 算法相对于粗糙K 2means 算法来说,它
的优点是采用真实存在的数据对象作为聚类的代表点,因此对离群数据比较敏感,同时引入RCPC 作为判定聚类算法终止的条件,因此用户可以根据自身需求制定评判准则;它的缺
点是高质量代表点的选择相对较为困难,数据分布的细微变
化会对聚类结果产生很大影响。而粗糙K 2means 算法采用均值作为聚类簇的代表点,更能反映聚类簇的基本分布情况,两者算法各有利弊。但是,不论是粗糙K 2means 算法还是粗糙K 2medoids 算法,其迭代次数较多,收敛速度较慢;对象划分的依赖准则是基于点与点的欧氏距离,忽视待划分对象与聚类簇内其他数据对象的关系。针对粗糙K 2means 算法和粗糙K 2medoids 算法存在的以上问题,我们提出一种新的RC 算法,该RC 算法在聚类代表选择上既考虑了对象均值,也考虑了真实存在的对象,同时收敛速度较快。
3 基于数据场的RC 算法
3.1 数据场的介绍
场的概念是1837年英国物理学家法拉第提出的,是用于描述物质间粒子的非接触相互作用。随着认知物理学的发展,人们将其抽象为一个数学概念,用来描述某个物理量或者数学函数在空间中的分布。李德毅院士在传统物理场的基础上,提出了基于数据对象的数据场理论[11]。数据场理论是把
N 维空间中的对象看成是有相互作用的,就是在没有外力的
作用下,对象也能相互吸引而相向运动。数据场理论的引入
是数据挖掘领域中的一个突破,因为传统的数据挖掘算法中只考虑对象之间一对一的映射关系,忽视了一对多或者多对一关系。而数据场理论克服了这样的问题,因为它把空间中某点的状态看成是其他对象共同作用的结果。
数据场理论采用势函数来表示对象间的相互关系,通过计算空间中任意对象的势值来判定对象的归属情况,不像粗糙K 2means 算法和粗糙K 2medoids 算法那样只计算任意对象到聚类中心或质心的欧氏距离来判定对象的归属。根据数据场理论,处于一个等势面上的所有对象具有相同的势值,最终归属一个类别中的对象以局部最大势值形成抱团簇。
考虑到短程场作用更有利于数据分布的聚簇特性,本文采用具有良好性质的高斯函数来定义数据场的标量势。鉴于数据场理论具有很好的离群检测功能,其在图像处理和入侵检测领域都取得了很好的应用[12]。
3.2 势函数相关概念
势函数是数据场理论的核心概念。下面我们结合粗糙模
型给出势函数的相关定义。
定义1 设U 是一个论域,X ={X 1,X 2,…,X K }是论域
U 上的一个划分,则任意对象x ∈X i 的势函数定义如下:
p (x ,X i )=
∑x j ∈X i
exp (-
||x -x j ||2
2
σ2
)其中σ用于控制对象间的相互作用,称为影响因子;||x -x j ||表示对象x 与对象x j 的距离。
定义2 设U 是一个论域,X ={X 1,X 2,…X K }是论域U 上的一个覆盖,对任意给定的X i ∈X ,则任意对象x ∈X i 的势函数定义成如下的分段函数形式:(1)当 B (X i )-B (X i )≠<∧B (X i )≠Φ,p (x ,X i )=p low (x ,X i )+p up (x ,X i )其中p low (x ,X i )=w low
∑x j ∈B (X i )
exp (-||x -x j ||2
2
σ2
)p up (x ,X i )=w up
∑
x j ∈B (X i )-B (X i )
exp (-
||x -x j ||2
2
σ2
)(2)当 B (X i )-B (X i )=Φ,
p(x,X i)=∑
x j∈B(X i)exp(-
||x-x j||2
2σ2
)
(3)否则,当B(X i)≠Φ∧B(X i)=Φ,
p(x,X i)=∑
x j∈B(X i)exp(-
||x-x j||2
2σ2
)
其中w low,w up分别表示下近似和上近似中数据对象对x对象势值的权重,并且满足w low+w up=1。
性质1 设U是一个论域,X={X1,X2,…,X k}是论域U上的一个覆盖,对于任意给定的X i∈X,则X i的上近似 B (X i)与下近似B(X i)具有如下性质:
(1)ΦΑB(X i)Α B(X i)ΑU;
(2)B(X i)∩B(X j)=Φ,i≠j;
(3)B(X i)∩ B(X j)=Φ,i≠j;
(4)如果x i∈U不属于任意集合的下近似,那它至少属于2个集合的上近似。
3.3 基于数据场的RC算法
根据上面介绍的数据场理论势函数概念和粗糙集理论上下近似所具有的特性,下面我们给出基于数据场的RC算法步骤。
输入:数据集U,影响因子σ,w low,K;
输出:数据的聚类结果:{X1,X2,…,X K};
算法步骤:
Step1 选取K个聚类簇的均值作为初始场源;
Step2 对x∈U,计算p(x,X i),i∈1,2,…,K,设p(x, X l)=max{p(x,X1),p(x,X2),…,p(x,X K)};
Step3 计算p(x,X l)-p(x,X j),j=1,2,…,K,如果p (x,X l)-p(x,X j)≥α,则x∈B(X l),否则x∈ B(X l)∧ B (X j);
Step4 对Πi∈1,2,…,K,如果B(X i)基本保持不变,转Step5;否则,如果?i,t∈1,2,…,K,对Πx∈( B(X i)-B (X i))∩( B(X t)-B(X t)),计算p(x,X i)与p(x,X t),其中设p(x,X l)=max{p(x,X i),p(x,X t)},p(x,X j)=min{p(x, X i),p(x,X t)},转Step3;
Step5 算法结束,输出聚类结果。
4 实验分析
4.1 聚类有效性度量指标
基于划分的聚类算法,正如本文中所给出的基于数据场的RC算法、粗糙K2means算法和K2medoids算法,聚类个数K值预先是要设定的。在聚类簇个数K已知的情况下,目前已存在很多度量聚类效果的指标函数,如文献[13]中采用的SICV(Sum of intra2cluster variation)度量指标。SICV依赖于K值的选取。
Mitra采用遗传算法来优化基于Davies2Bouldin聚类有效性度量指标函数[14]。由于Davies2Bouldin指标函数独立于聚类簇初始个数K的设定,因此不同的聚类划分算法都可以采用它来进行比较。
Davies2Bouldin指标函数就是聚类簇内部的距离与聚类簇之间的距离之比的平均值。好的聚类效果就是使得类内距达到最小,类间距达到最大。Davies2Bouldin指标函数定义如下:
DB=1
K
∑
K
k=1
max
k≠l
{
S(X k)+S(X l)
d(X k,X l)
}
然而,在RC算法中,处于聚类X i上近似中的对象和处
于下近似中的对象对类内距的贡献不一样,因此Mitra等人
在文献[15]中对Davies2Bouldin指标函数进行了改进。改进
之后的Davies2Bouldin指标函数定义为RDB:
RDB=
1
K
∑
K
k=1
max
k≠l
{
RS(X k)+RS(X l)
d(X k,X l)
}
在下面的实验分析中,我们采用基于改进的Davies2Boul2
din指标函数(RDB)来对文中涉及的3种RC算法进行对比
分析。实验分析数据包括Synthetic数据、UCI标准数据库中
的IRIS数据集、ZOO数据和Colon Cancer数据。
4.2 Synthetic数据
Synthetic数据是一个二维分布数据,由10个取值在[0,
1]上的数值型数据对象构成。在文献[16]中,G eorg Peters
等人分别采用粗糙K2means算法和粗糙K2medoids算法对
Synthetic数据进行聚类分析,初始聚类个数K=2,聚类结果
分别如图
1和图2所示。
从图1中我们可以看出,采用粗糙K2means算法聚类分
析之后,两类对象之间的交界处是不容易区分的,采用粗糙
K2medoids算法对之聚类分析之后得到的结果却和粗糙K2
means算法有很大的差别,所有对象被精确地划分到两个类
的下近似中,处于聚类簇边界的集合为空集。
同时我们利用本文提出的算法也对Synthetic数据进行
了聚类分析,初始聚类个数K=2,势值函数的影响因子σ=
0.20,w low=0.9,聚类结果如图3所列。
从图3中我们可以看出,对象划分结果采用粗糙K2me2
doids算法相同,即图3所示的左边的3个对象属于一个类,
右边的7个对象属于另外一个类。下面我们采用RDB指标
来度量这3种RC算法的效果,结果如表1所列。
表1 Synt hetic数据的RDB指标
Algorithm Rough Davies2Bouldin index
Rough K2means0.638
Rough K2medoids0.654
RCDF0.654
4.3 IRIS数据
UCI数据库中的IRIS是模式识别中的一个经典数据集,
记录的是一些植物特征数据。共有5个属性,其中包括4个
数值型条件属性、1个分类型决策属性。共有150条数据对
象和3种决策值,我们把这些数据样本简记为1,2, (150)
其中1～50,51～100,101～150分别对应一种决策。我们去
掉决策属性后,分别采用粗糙K2means算法、粗糙K2medoids
算法和本文提出的RCDF算法对数据进行聚类分析。对粗
糙K2means算法和粗糙K2medoids算法我们设初始聚类个数
K=3,距离阈值ξ∈[0.05,0.1],w low=0.9;我们用本文提出
的RCDF算法也对IRIS数据集做了聚类分析,势值阈α∈
[0.15,0.18],σ=1.4,w low=0.9,K=3,采用RDB指标来度
量这3种RC 算法的效果,如表2所列。
表2 IRIS 数据的RDB 指标
Algorithm Rough Davies 2Bouldin index
Rough K 2means 0.630Rough K 2medoids
0.627RCDF
0.622
由于IRIS 数据集的分布特性,即第二类与第三类数据对象具有较强的难分性,因此实验得到的RDB 指标相差不大。但是,我们对3种RC 算法的收敛速度进行了比较。从图4中我们可以看出,本文提出的RCDF
算法具有更快的收敛速度。
4.4 Z OO 数据
UCI 数据库中的ZOO 也是模式识别中的一个经典数据
集,记录的是一些动物的特征数据。共有101条记录,每个对象有18个特征属性。我们分别采用基于粗糙K 2means 算法和粗糙K 2medoids 算法对其进行RC 聚类分析,设K =7,距离阈值ξ∈[0.08,0.15],w low =0.9;我们采用本文提出的算法也对其进行了聚类分析,势值阈值α∈[0.20,0.25],σ=
0.7,w low =0.9,K =7,采用RDB 来度量这3种RC 算法的效
果,如表3所列。
表3 ZOO 数据的RDB 指标
Algorithm Rough Davies 2Bouldin index
Rough K 2means 0.805Rough K 2medoids
0.819RCDF
0.782
从表3中我们可以容易看出,本文提出的算法具有较小的RDB 值,具有比粗糙K 2means 算法和粗糙K 2medoids 算法更好的聚类效果。
下面我们从实验算法的收敛速度来对3种RC 算法加以比较,比较结果如图5所示。
4.5 Colon C ancer 数据
Colon Cancer 数据是基因表达数据,其中包括62条基因
表达数据。每个基因表达数据共有2000个特征属性,有2个类别信息,即正常基因和癌症基因。由于基因各个特征属性之间具有极强的相关性,在文献[16]中,Peters 等人对Colon
Cancer 数据首先进行了约简,然后采用Davies 2Bouldin 指标
度量了粗糙K 2means 算法和粗糙K 2medoids 算法的效果。而本文我们采用原始数据进行实验分析,改用RDB 指标重新度量3种RC 算法的效果,设K =2,势值域值α∈[0.05,0.10],σ=1.2,w low =0.9,结果如表4所列。
表4 Colon Cancer 数据的RDB 指标
Algorithm Rough Davies 2Bouldin index
Rough K 2means 0.561Rough K 2medoids
0.528RCDF
0.503
从表4中我们可以看出RCDF 算法具有更好的聚类效果,同时我们也对算法的收敛速度进行了比较,结果如图6所示
。
结束语 本文将经典数据场理论引入到RC 算法中来,提出了一种新的RC 算法。传统的RC 算法是根据对象到聚类中心或质心距离来划分对象的归属。本文提出的RC 算法不是根据计算点与点的欧氏距离,而是采用数据场势值的思想将对象划分到不同的聚类簇中;对象划分通过粗分再到细分,直至形成稳定的聚类效果。实验分析阶段通过引入改进的Davies 2Bouldin 指标来度量聚类算法的效果,分别对Syn 2thetic 数据、IRIS 数据、ZOO 数据集和Colon Cancer 数据集进行了实验分析比较,结果表明,在具有交叉的数据集上本文提出的算法较粗糙K 2means 算法和粗糙K 2medoids 算法具有更好的聚类效果;同时本文提出的算法还具有迭代次数较少、收敛速度较快的优点。算法的缺点就是处理的数据必须是数值型的,对非数值型数据对象不能很好的处理,且初始聚类个数K 需要预先给出,这些都是有待进一步研究的工作。
参考文献
[1]
Joshi A ,Krishnapuram R .Robust Fuzzy Clustering Met hods to Support Web Mining ∥Proceedings of t he Workshop on Data Mining and Knowledge Discovery.SIGMOD ’98.Seattle ,1998:15/1215/8[2]
Lingras P ,Yao Y Y.Time Complexity of Rough Clustering :GAs versus K 2means ∥Proceedings of t he Third International Con 2ference of Rough Set s and Current Trends in Computing 2002.Berlin ,Germany :Springer Verlag ,2002:2632270[3]
Ozyer T ,Alhajj R ,Barker K.Utilizing Rough Set s and Multi 2ob 2jective Genetic Algorit hms for Automated Clustering ∥t he 4th International Conference ,TSCTC 2004.Heidelberg Germany :Springer Verlag ,2004:5672572[4]
Lingras P ,West C.Interval Set Clustering of Web Users wit h Rough K 2means.Journal of Intelligent Informmation Systems ,2004,23(1):5216[5]
Fahim A M ,Salem A M ,Torkey F A.An efficient enhanced k 2means clustering algorit hm.Journal of Zhengjiang University 2Science A ,2006,7(10):162621633[6]
Peters G.Outliers in rough k 2means clustering ∥Proc.First In 2ternational Conference on Pattern Recognition and Machine In 2telligence.Volume 377of LNCS.K ilkata :Springer Verlag ,2005:7022707[7]Peters G.Some refinement s of t he rough k 2means.Pattern Rec 2ognition ,2006,20:148121491
[8]
Mitra S.An Evolutionary Rough partitive clustring Pattern Re 2cognition letters ,2004,25(12):143921449
(下转第244页)
离,短暂停留后继续执行航班t6,到达机场p1。在到达p1之后由同一飞机机组执行航班t7,到达机场p7,至此结束当天任务。
图1所示的t m,t n为两类特殊变迁,表示标识的资源结束当天任务,并将于以后执行飞行任务,目的地暂时未知,用p m,p n保存托肯。航班的执行顺序和使用资源如图所示,每架航班的执行都需要使用前一架航班的某一资源,前一架航班的延误,必然使后续航班的执行受到影响。图中展现了初始航班t1的机组和飞机两种资源对后续航班的影响范围,而(p1)t1(p2)t3(p4)t5(p6)则反映了飞机a1在单机执行多航班时产生的链式波及延误情况。
图1 基于CPN的航班延误波及链模型
4.2 有色出现网的应用模型
为观察航班执行的先后顺序和并发情况,以及某架航班的延误对后续航班的影响,我们对上述模型进行动态行为的描述,以出现网的形式反映由一架航班的延误带来的影响。
以t1作为初始变迁为例,得到图2所示的一个有色出现网,该出现网反映了一天内t1所使用的资源对后续航班的全部影响。其中(p1)t1(p2)t3(p4)t5(p6)则反映了初始飞机a1在单机执行多航班的情况下其延误将对下游航班产生的影响。
图2 航班延误波及链模型的一个有色出现网
我们把有向弧的方向看作时间流动方向,该出现网给出的是偏序时间。网中没有顺序关系的两架航班是并发的。这种有色出现网直观地反映了机组和飞机资源的分配和流动情况,航班执行的顺序和并发关系,以及一架航班的延误对其他航班的影响,客观地反映了航班执行过程中的相互关系和延误波及情况。
这种有色出现网不仅保留了有色Petri网的优点,清楚地反映了飞机和机组资源的出处、流动情况和航班的执行细况,也遵循了网论在时间系统上的观点,使航班执行的先后和并发顺序一目了然,避免了因大量库所和变迁给Petri网模型的描述和理解带来的复杂性。
结束语 有色Petri网作为描述异步并发系统的一种高级网系统,图形简洁但函数关系复杂。用出现网对其动态行为进行刻画,可以清楚地展现各种资源的分布和流动情况,以及各个变迁的顺序和并发关系。鉴于基本出现网在描述高级网系统时带来的图形复杂性,本文在基本出现网的基础上提出了一种有色出现网,对库所容量和托肯、变迁的颜色进行扩充,使之更适合直观简洁地记录有色Petri网这种高级网系统的客观行为。本文利用有色Petri网对航班延误的链式波及情况进行建模,并构造了它的一个有色出现网,简洁而清晰地展现了各航班执行时所需的资源在机场的分布和流动情况,以及一架航班的执行情况对后续航班的链式影响,同时,出现网提供的偏序时间关系也使得各航班执行的顺序和并发关系一目了然。可见,这种有色出现网能够对基于有色Petri网的模型进行更加简洁和直观的行为记录。
参考文献
[1]蒋昌俊.Petri网的行为理论及其应用.第一版.北京:高等教育
出版社,2003:19221
[2]袁崇义.Petri网原理与应用.第一版.北京:电子工业出版社,
2005:972103
[3]Lomazova I.On Occurrence Net Semantics for Petri Net s wit h
Contact s.Fundamentals of Computation Theory,1997,1279: 3172328
[4]Kurt J.Colored Petri Net s and The Invariant2met hod.Theoreti2
cal Computer Science,1981,14:3172336
[5]唐培和.着色网到基本网的等价变换.广西工学院学报,1995,6
(3):53257
[6]郝克刚,葛玮.论高级Petri网系统的等价谱系.计算机学报,
1993,16(7):5532558
[7]Schaefer L,Wojcik L.Flight Connections and Their Impact s on
Delay Propagation∥Digital Avionics Systems Conference.2003, 1:5.B.425.129
[8]Ahmad B S,Cphn A,Guan Y ihan.Analysis of t he Potential for
Delay Propagation in Passenger Aviation Flight Networks.Sloan Industry Studies Working Papers,WP22007211.2007
(上接第206页)
[9]Vogt s K,Pope N.Generating compact rough cluster descriptions
using an evolutionary algorit hm∥Proceedings of t he6th Annual Genetic and Evolutionary Computation Conference.Heidelberg, Germany:Springer Verlag,2004:133221333
[10]Voges K E,Pope N K,Brown M R.Heuristics and Optimization
for Knowledge Discovery.chapter Cluster Analysis of Marketing Data Examining On2Line Shipping Orientation:A Comparison of k2Means and Rough Clustering Approaches.Hershey PA:Idea Group Publishing,2002:2072224
[11]淦文燕,李德毅.一种基于数据场的层次聚类方法.电子学报,
2006(2):68272
[12]Xie Feng,Bai Shou.Dectecting Novel Network Attacks wit h a
Data Field.Springer Berlin,Heidelberg,Volume3917.2006:662 72
[13]Sheng Weiguo,Liu Xiaohui.A genetic k2medoids clustering al2
gorit hm.Journal of Heuristics,2006,12:4472466
[14]Davies D L,Bouldin D W.A cluster separation measure.IEEE
Transactions on Pattern Analysis and Machine Intelligence, 1979,1:2242227
[15]Mitra S,Banka H,Pedrycz W.Collaborative Rough Clustering.
Rough Set s,Case2Based Reasoning and Knowledge Discoery, 2005,3776:7682773
[16]Peters G,Lampart M.A Partitive Rough Clustering Algorit hm.
Rough Set s and Current Trends in Computing,2006,4259:6572 666
数据挖掘聚类算法课程设计报告
数据挖掘聚类问题(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科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集
聚类分析K-means算法综述
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
模糊聚类分析方法
模糊聚类分析方法 对所研究的事物按一定标准进行分类的数学方法称为聚类分析，它是多元统计“物以类聚”的一种分类方法。载科学技术、经济管理中常常要按一定的标准（相似程度或亲疏关系）进行分类。例如，根据生物的某些性状可对生物分类，根据土壤的性质可对土壤分类等。由于科学技术、经济管理中的分类界限往往不分明，因此采用模糊聚类方法通常比较符合实际。 一、模糊聚类分析的一般步骤 1、第一步：数据标准化[9] （1） 数据矩阵 设论域12{,,,}n U x x x =为被分类对象， 每个对象又有m 个指标表示其性状，即 12{,, ,}i i i im x x x x = (1,2,,) i n =， 于是，得到原始数据矩阵为 1112 1 21222 12 m m n n nm x x x x x x x x x ?? ? ? ? ??? 。 其中nm x 表示第n 个分类对象的第m 个指标的原始数据。 （2） 数据标准化 在实际问题中，不同的数据一般有不同的量纲，为了使不同的量纲也能进行比较，通常需要对数据做适当的变换。但是，即使这样，得到的数据也不一定在区间[0,1]上。因此，这里说的数据标准化，就是要根据模糊矩阵的要求，将数据压缩到区间[0,1]上。通常有以下几种变换： ① 平移·标准差变换
i k k ik k x x x s -'= (1,2,,;1,2,i n k m == 其中 11n k i k i x x n ==∑， k s =。 经过变换后，每个变量的均值为0，标准差为1，且消除了量纲的影响。但 是，再用得到的ik x '还不一定在区间[0,1]上。 ② 平移·极差变换 111m i n { }m a x {}m i n {}i k i k i n ik ik ik i n i n x x x x x ≤≤≤≤≤≤''-''=''- ，(1,2, ,)k m = 显然有01ik x ''≤≤，而且也消除了量纲的影响。 ③ 对数变换 lg ik ik x x '= (1,2,,;1,2,i n k m == 取对数以缩小变量间的数量级。 2、第二步：标定（建立模糊相似矩阵） 设论域12{,, ,}n U x x x =，12{,,,}i i i im x x x x =，依照传统聚类方法确定相似 系数，建立模糊相似矩阵，i x 与j x 的相似程度(,)ij i j r R x x =。确定(,)ij i j r R x x =的方法主要借用传统聚类的相似系数法、距离法以及其他方法。具体用什么方法，可根据问题的性质，选取下列公式之一计算。 （1） 相似系数法 ① 夹角余弦法 2 2m ik jk ij m ik jk x x r x = ∑∑ ② 最大最小法 11() () m ik jk k ij m ik jk k x x r x x ==∧= ∨∑∑。 ③ 算术平均最小法
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
K - M e a n s 聚 类 算 法
基于K-means聚类算法的入侵检测系统的设计 基于K-means聚类算法的入侵检测系统的设计 今天给大家讲述的是K-means聚类算法在入侵检测系统中的应用首先，介绍一下 聚类算法 将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的研究，就形成了历史学，有关世界空间地域的研究，则形成了地理学。 又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不同的界、门、纲、目、科、属、种之中。 事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。 通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analysis）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。 （聚类分析我们说得朴实一点叫做多元统计分析，说得时髦一点叫做数据挖掘算法，因为这个算法可以在一堆数据中获取很有用的信息，这就不就是数据挖掘吗，所以大家平时也不要被那些高大上的名词给吓到了，它背后的核心原理大多数我们都是可以略懂一二的，再
比如说现在AI这么火，如果大家还有印象的话，以前我们在大二上学习概率论的时候，我也和大家分享过自然语言处理的数学原理，就是如何让机器人理解我们人类的自然语言，比如说，苹果手机上的Siri系统，当时还让杨帆同学帮我在黑板上写了三句话，其实就是贝叶斯公式+隐含马尔可夫链。估计大家不记得了，扯得有点远了接下来还是回归我们的正题，今天要讨论的聚类算法。） K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，结果稳定，聚类的效果也还不错, 相异度计算 在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。 要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个特征变量来刻画，就比如说我们举一个例证，就有一项比较神奇的技术叫面部识别技术，其实听起来很高大上，它是如何做到的，提取一个人的面部特征，比如说嘴巴的长度，鼻梁的高度，眼睛中心到鼻子的距离，鼻子到嘴巴的距离，这些指标对应得数值可以组成一个向量作为每一个个体的一个标度变量（）,或者说叫做每一个人的一个特征向量。 如果对于一群有待分类的样本点需用p 个特征变量值描述，则每
蚁群聚类算法综述
计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x
大数据时代的空间数据挖掘综述
第37卷第7期测绘与空间地理信息 GEOMATICS ＆SPATIAL INFOＲMATION TECHNOLOGY Vol．37，No．7收稿日期：2014－01－22 作者简介：马宏斌（1982－），男，甘肃天水人，作战环境学专业博士研究生，主要研究方向为地理空间信息服务。 大数据时代的空间数据挖掘综述 马宏斌1 ，王 柯1，马团学 2（1．信息工程大学地理空间信息学院，河南郑州450000；2．空降兵研究所，湖北孝感432000） 摘 要：随着大数据时代的到来，数据挖掘技术再度受到人们关注。本文回顾了传统空间数据挖掘面临的问题， 介绍了国内外研究中利用大数据处理工具和云计算技术，在空间数据的存储、管理和挖掘算法等方面的做法，并指出了该类研究存在的不足。最后，探讨了空间数据挖掘的发展趋势。关键词：大数据；空间数据挖掘；云计算中图分类号：P208 文献标识码：B 文章编号：1672－5867（2014）07－0019－04 Spatial Data Mining Big Data Era Ｒeview MA Hong －bin 1，WANG Ke 1，MA Tuan －xue 2 （1．Geospatial Information Institute ，Information Engineering University ，Zhengzhou 450000，China ； 2．Airborne Institute ，Xiaogan 432000，China ） Abstract ：In the era of Big Data ，more and more researchers begin to show interest in data mining techniques again．The paper review most unresolved problems left by traditional spatial data mining at first．And ，some progress made by researches using Big Data and Cloud Computing technology is introduced．Also ，their drawbacks are mentioned．Finally ，future trend of spatial data mining is dis-cussed． Key words ：big data ；spatial data mining ；cloud computing 0引言 随着地理空间信息技术的飞速发展，获取数据的手 段和途径都得到极大丰富，传感器的精度得到提高和时空覆盖范围得以扩大，数据量也随之激增。用于采集空间数据的可能是雷达、红外、光电、卫星、多光谱仪、数码相机、成像光谱仪、全站仪、天文望远镜、电视摄像、电子 显微镜、CT 成像等各种宏观与微观传感器或设备，也可能是常规的野外测量、人口普查、土地资源调查、地图扫描、 地图数字化、统计图表等空间数据获取手段，还可能是来自计算机、 网络、GPS ，ＲS 和GIS 等技术应用和分析空间数据。特别是近些年来，个人使用的、携带的各种传感器（重力感应器、电子罗盘、三轴陀螺仪、光线距离感应器、温度传感器、红外线传感器等），具备定位功能电子设备的普及，如智能手机、平板电脑、可穿戴设备（GOOGLE GLASS 和智能手表等），使人们在日常生活中产生了大量具有位置信息的数据。随着志愿者地理信息（Volunteer Geographic Information ）的出现，使这些普通民众也加入到了提供数据者的行列。 以上各种获取手段和途径的汇集，就使每天获取的 数据增长量达到GB 级、 TB 级乃至PB 级。如中国遥感卫星地面站现在保存的对地观测卫星数据资料达260TB ，并以每年15TB 的数据量增长。比如2011年退役的Landsat5卫星在其29年的在轨工作期间，平均每年获取8．6万景影像，每天获取67GB 的观测数据。而2012年发射的资源三号（ZY3）卫星，每天的观测数据获取量可以达到10TB 以上。类似的传感器现在已经大量部署在卫 星、 飞机等飞行平台上，未来10年，全球天空、地空间部署的百万计传感器每天获取的观测数据将超过10PB 。这预示着一个时代的到来，那就是大数据时代。大数据具有 “4V ”特性，即数据体量大（Volume ）、数据来源和类型繁多（Variety ）、数据的真实性难以保证（Veracity ）、数据增加和变化的速度快（Velocity ）。对地观测的系统如图1所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将
各种聚类算法及改进算法的研究
论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 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)每个对
数据流聚类算法D-Stream
Density-Based Clustering for Real-Time Stream Data 基于密度的实时数据流聚类(D-Stream) 翻译by muyefei E-mail: muyefei@https://www.wendangku.net/doc/be11587134.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的数据流算法。它有两项主要的技术挑战： 首先，我们不大愿意将数据流视为静态数据很长的一个序列，因为我们对数据流演化的时间特征更加感兴趣。为了捕获簇的动态变化，我们提出了一个新颖的方案，它可以将衰减
数据挖掘中的聚类分析方法
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
Matlab学习系列23. 模糊聚类分析原理及实现
23. 模糊聚类分析原理及实现 聚类分析，就是用数学方法研究和处理所给定对象，按照事物间的相似性进行区分和分类的过程。 传统的聚类分析是一种硬划分，它把每个待识别的对象严格地划分到某个类中，具有非此即彼的性质，这种分类的类别界限是分明的。 随着模糊理论的建立，人们开始用模糊的方法来处理聚类问题，称为模糊聚类分析。由于模糊聚类得到了样本数与各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界。 本篇先介绍传统的两种（适合数据量较小情形，及理解模糊聚类原理）：基于择近原则、模糊等价关系的模糊聚类方法。 （一）预备知识 一、模糊等价矩阵 定义1 设R=(r ij )n ×n 为模糊矩阵，I 为n 阶单位矩阵，若R 满足 i) 自反性：I ≤R （等价于r ii =1）； ii) 对称性：R T =R; 则称R 为模糊相似矩阵，若再满足 iii) 传递性：R 2 ≤R （等价于1 ()n ik kj ij k r r r =∨∧≤） 则称R 为模糊等价矩阵。 定理1 设R 为n 阶模糊相似矩阵，则存在一个最小的自然数k
（k K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然K-means-聚类算法研究综述