第28卷第6期V ol.28No.6
控制与决策
Control and Decision
2013年6月
Jun.2013一种基于信息熵的异常数据挖掘算法
文章编号:1001-0920(2013)06-0867-06
陈玉明1,吴克寿1,李向军1,2
(1.厦门理工学院计算机科学与技术系，福建厦门361024；2.南昌大学计算机科学与技术系，南昌330031)
摘要:信息熵是粒计算理论中度量不确定信息的重要工具之一,已有的异常数据挖掘算法主要针对确定性的异常数据挖掘,采用信息熵度量不确定性数据进行异常数据挖掘的研究报道较少.鉴于此,在引入信息熵概念的基础上,定义基于信息熵的异常度来度量数据之间的异常程度,并提出基于信息熵的异常数据挖掘算法,该算法可有效进行异常数据的挖掘.理论分析与实验结果表明,所提出算法是有效可行的.
关键词:粗糙集；粒计算；异常数据挖掘；信息熵
中图分类号:TP181文献标志码:A
A kind of outlier mining algorithm based on information entropy
CHEN Yu-ming1,WU Ke-shou1,LI Xiang-jun1,2
(1.Department of Computer Science and Technology，Xiamen University of Technology，Xiamen361024，China;
2.Department of Computer Science and Technology，Nanchang University，Nanchang330031，China．Correspondent: CHEN Yu-ming，E-mail：cym0620@16
https://www.doczj.com/doc/2c8479443.html,)
Abstract:Information entropy is one of the important tool to measure the uncertainty information in the information theory. Many existing algorithms of outlier mining mainly aim at certainty data,and little work has been done for the uncertainty data aiming to outlier mining based on the information entropy.Therefore,after introducing information entropy concept, outlier degree based on information entropy is de?ned for measuring the outlier data.Furthermore,an algorithm for outlier mining based on information entropy is proposed,which can effectively obtain outliers from data set.Finally,theoretical analysis and experimental results show that the algorithm is ef?cient and feasible.
Key words:rough sets；granular computing；outlier data mining；information entropy
0引言
异常数据是数据集中偏离大部分对象的数据,其表现与大多数常规对象有明显的差异,甚至使人怀疑它们可能由另外一种完全不同的机制所产生[1].随着数据挖掘技术的飞速发展,异常数据挖掘受到国内外学者的广泛关注,成为数据挖掘领域的一个重要分支.近年来,异常数据挖掘在网络入侵检测、地质灾害预报、疾病诊断、故障检测、恐怖活动防范、信用卡欺诈检测等诸多领域得到广泛应用[2-3].现有的异常数据挖掘方法主要有基于距离的方法[4]、基于统计的方法[5]、基于密度的方法[6]和基于聚类的方法[7].国内外众多学者对这些方法进行了深入研究,并取得丰硕成果,但仍存在一些不足和缺陷.基于距离的方法中,距离函数与参数的选择存在一定困难;基于统计的方法中,要求预先知道数据的分布情况,但数据的分布函数难以预先获得;基于密度的方法中时间复杂度较大;基于聚类的方法主要侧重于聚类问题.这些问题极大地限制了异常数据挖掘方法的发展与应用,且主要处理确定性数据,对于不确定性的信息处理缺乏有效的理论模型和方法.
粒计算是人工智能领域新兴起的一个研究方向,是信息处理的一种新的概念和计算范式[8],主要用于处理不确定的、模糊的、不精确的、部分真的和海量的信息,其基本思想是利用不同粒度上的信息进行问题求解.粒计算模型主要包括模糊集模型[9]、粗糙集模型[10]和商空间模型[11].近年来,该理论在知识获取、机器学习、数据挖掘、智能控制和模式识别等多个领域得到了广泛应用[8,12].在基于粒计算的不确定性理论研究中,不确定性数据的度量是重要的研究内容之一,也是知识获取的关键步骤.国内学者提出的
收稿日期:2012-02-13；修回日期:2012-05-19.
基金项目:国家自然科学青年基金项目(61103246).
作者简介:陈玉明(1977?),男,博士,从事粗糙集、粒计算的研究；吴克寿(1975?),男,副教授,博士,从事粗糙集、数据挖掘与加密算法等研究.
868
控制与决策
第28卷
不确定性数据度量工具包括信息熵[13]、粗糙熵[14]和知识粒度[15-17].目前,这些度量工具受到国内外学者的极大关注,取得了一定成果,但主要侧重于理论上的研究和探讨,具体应用实例较为少见.
鉴于此,本文引入不确定性数据的度量工具信息熵,并将其应用于异常数据挖掘领域,提出基于信息熵的异常数据挖掘理论和方法,为异常数据挖掘处理不确定性数据提供一条新的途径,拓展不确定性度量理论在数据挖掘领域的应用范围,为不确定性理论开辟新的应用空间.在此基础上,进一步提出了基于信息熵的异常数据挖掘算法,该算法不需要任何先验知识,采用信息熵度量对象间的距离和异常度,能够有效挖掘出异常程度较高的数据.UCI 数据集测试表明,所提出方法具有较好的准确率.
1信息熵概念
信息熵是数学上的一个抽象概念,表示特定信息的出现概率,在信息系统中可以表示信息的不确定性.一个信息系统越是确定性的,其信息熵越低;反之,信息熵越高.信息熵也可以说是信息系统不确定性程度的一个度量.
定义1设IS =(U,A,V,f )为信息系统[12].其中:U 为非空有限集,称为论域;A 为有限属性集;V =
∪
a ∈A
V a ,V a 为属性a 的值域;f :U ×A →V 为信息函数,即对于?x ∈U,a ∈A ,有f (x,a )∈V a .任意属性子集B ?A 决定一个二元不可区分关系IND(B ),有
IND(B )=
{(x,y )∈U ×U ∣?a ∈B,f (x,a )=f (y,a )}.
(1)
U/IND(B )构成了U 的一个划分,称为U 上的一
个知识,其中每个等价类称为一个知识粒.为了方便计算,将U/IND(B )简记为U/B .特别地,若
U/B =ω={[x ]B ∣[x ]B ={x },x ∈U },
则称为恒等关系;若
U/B =δ={[x ]B ∣[x ]B =U,x ∈U },
则称为全域关系.
定义2设IS =(U,A,V,f )为信息系统,U/A =
{X 1,X 2,???,X m },则A 的信息熵[8]定义为
H (A )=?m ∑
i =1
p (X i )log p (X i ).
(2)
其中:p (X i )=∣X i ∣/∣U ∣,i =1,2,???,m ,∣E ∣为集合E 的基数.
性质1?B ?A ,有0?H (B )?ln ∣U ∣.当U/B 为恒等关系,即U/B =ω时,B 的信息熵达到最大值ln ∣U ∣;当U/B 为全域关系,即U/B =
δ时,B 的信息熵达到最小值0.
定义3设IS =(U,A,V,f )是一个信息系统,
B,C ?A ,U/B ={X 1,X 2,???,X m },U/C ={Y 1,Y 2,???,Y n },若?X i ∈U/B ,?Y j ∈U/C (X i ?Y j ),则称B 比C 更细,记为B ?C .
定义4设IS =(U,A,V,f )是一个信息系统,
B,C ?A ,U/B ={X 1,X 2,???,X m },U/C ={Y 1,Y 2,???,Y n },若?X i ∈U/B ,?Y j ∈U/C (X i ?Y j ),则称B 比C 严格细,记为B ?C .
定理1设IS =(U,A,V,f )是一个信息系统,
B,C ?A ,U/B ={X 1,X 2,???,X m },U/C ={Y 1,Y 2,???,Y n },若B ?C ,则H (B )?H (C ).
证明1)由B ?C 可知,?X i ∈U/B ,?Y j ∈
U/C (X i ?Y j );反之,对于任意Y j ,存在s 个X i ,满足
∣Y j ∣∣U ∣=∣X 1∣∣U ∣+∣X 2∣∣U ∣+???+∣X s ∣
∣U ∣
.且有
∣X 1∣∣U ∣log ∣X 1∣∣U ∣+∣X 2∣∣U ∣log ∣X 2∣
∣U ∣
+???+∣X s ∣∣U ∣log ∣X s ∣
∣U ∣<∣Y j ∣∣U ∣log ∣Y j ∣∣U ∣,?(∣X 1∣∣U ∣log ∣X 1∣∣U ∣+∣X 2∣∣U ∣log ∣X 2∣∣U ∣
+???
+∣X s ∣∣U ∣log ∣X s ∣∣U ∣)
>?∣Y j ∣∣U ∣log ∣Y j ∣∣U ∣,?m ∑i =1
∣X i ∣∣U ∣log ∣X i ∣∣U ∣>?n ∑i =1
∣Y i ∣∣U ∣log ∣Y i ∣∣U ∣
,
因此有H (B )>H (C ).
2)由B =C 可知∣X i ∣/∣U ∣=∣Y j ∣/∣U ∣,因此有H (B )=H (C ). 定理2设IS =(U,A,V,f )是一个信息系统,B,C ?A ,有:
1)若B ?C ,则H (B )?H (C );2)若B ?C ,则H (B )?H (C ).由定理1可得证,此略.
定理1反映了知识的粗细与信息熵的关系:知识
越粗,信息熵越小,不确定性越小;知识越细,信息熵越大,不确定性越大.定理2反映了属性与信息熵的变化:属性增加,划分更细,信息熵变大,不确定性增大;属性减少,划分更粗,信息熵变小,不确定性减少.
由此可见,信息系统中属性的增减使得系统的粒度发生变化(粗细程度),同时信息熵和不确定性也相应变化.因此,信息熵能够度量信息系统的不确定性.
2基于信息熵的异常数据挖掘
信息熵可以度量知识的不确定性,近年来,在数据挖掘等领域获得了广泛应用.然而,采用信息熵进行异常数据挖掘的研究并不多见,下面结合信息熵的定义,进一步定义对象相对于等价类的相对信息熵概
第6期陈玉明等:一种基于信息熵的异常数据挖掘算法869念,并给出异常度概念来度量数据的异常.
2.1基于信息熵的异常数据挖掘方法
在数据挖掘系统中,数据集一般采用决策表或信
息系统的方式来表示和处理.本文基于信息系统讨论
异常的定义和检测问题,遵循Hawkins关于异常的定
义[1],对异常数据进行如下定义.
定义5设IS=(U,A,V,f)是一个信息系统,
?x∈U,若对象x与所有非异常对象的距离较远,
且与所有异常对象的距离较近,则称对象x为异常对
象(异常点或异常数据).
为了计算对象间的距离,定义相对信息熵来表示
距离函数,对象与其他对象的距离之和表示该对象的
异常程度,异常程度高的对象即为异常对象.
定义6设IS=(U,A,V,f)是一个信息系统,
U/A={X1,X2,???,X m},若
?x∈U,{U?{x}}/A={X′1,X′2,???,X′m},
H x(A)=?
m
∑
i=1
p(X′i)log p(X′i),
则对象x相对于A的对象相对信息熵定义为
RH A(x)=H x(A)/H(A).(3)其中:H(A)为A的信息熵,H x(A)为删除对象x后A 的信息熵.信息熵可以表示不确定性信息的程度,因此,对象相对信息熵可以度量x的不确定性程度.如果删去对象x后信息熵变化较小,则x的不确定性程度较小;反之,x的不确定性程度较大.
定义7设IS=(U,A,V,f)是一个信息系统,A ={a1,a2,???,a k},按信息熵从小到大排序,形成序列S=?a′1,a′2,???,a′k?,其中H({a′i})?H({a′i+1}),称S为信息系统中单属性按信息熵递增序列.
定义8设IS=(U,A,V,f)是一个信息系统,S =?a′1,a′2,???,a′k?为单属性按信息熵递增序列,给定序列AS=?A′1,A′2,???,A′k?,其中A′1=A,A′k={a′1}, A′i+1=A′i?{a′i},称AS为信息系统中属性子集序列.
为了刻画数据集中每个对象的异常程度,在对象相对信息熵的基础上引入异常度的概念来表示信息系统中每个对象的异常程度.
定义9设IS=(U,A,V,f)是一个信息系统,S =?a′1,a′2,???,a′k?为单属性按信息熵递增序列,AS=?A′1,A′2,???,A′k?为属性子集序列,?B?A,W B(x)=∣[x]B∣/∣U∣表示x的权重,对象x的异常度定义为
EOF(x)=1?
(k∑
i=1RH{a
i}
(x)W{a
i}
(x)+
k
∑i=1RH{A
i}
(x)W{A
i}
(x)
)/
∣U∣.(4)
定义10设IS=(U,A,V,f)是一个信息系统,
令v为给定的阈值,对于任意x∈U,如果EOF(x)>
v,则称x为信息系统IS中一个基于信息熵的异常对
象,其中EOF(x)为对象x的异常度.
2.2基于信息熵的异常数据挖掘算法
依据信息熵异常度的定义,基于信息熵的异常数
据挖掘算法描述如下.
算法1IEOM(information entropy based outlier
mining).
输入:信息系统IS=(U,A,V,f)(A={a1,a2,
???,a m},m=∣A∣,n=∣U∣),阈值v;
输出:异常对象的集合O.
Step1:初始化m=∣A∣,n=∣U∣,O=?.
Step2:对于信息系统IS中的每个属性a i(1?
i?m),循环执行如下操作:
Step2.1:根据U中对象在属性a i上的取值,进行
基数排序;
Step2.2:求出划分U/IND({a i});
Step2.3:计算信息熵H({a i}).
Step3:根据定义7构造单属性按信息熵递增序
列S=?a1,a2,???,a m?.
Step4:根据定义8构造属性子集序列AS=?A1,
A2,???,A m?.
Step5:对于属性子集序列AS中的每个属性子
集A i(1?i?m),循环执行如下操作:
Step5.1:根据U中对象在属性子集A i上的取值
进行基数排序;
Step5.2:求出划分U/IND({A i});
Step5.3:计算信息熵H({A i}).
Step6:对于U中的每个对象x i(1?i?n),循环
执行如下操作:
Step6.1:for j=1to m,循环执行如下操作:
Step6.1.1:计算对象x i对于单个属性的相对信
息熵RH{a
j}
(x i);
Step6.1.2:计算对象x i对于属性子集的相对信
息熵RH{A
j}
(x i);
Step6.1.3:计算权值W{a
j}
(x i)和W{A
j}
(x i).
Step6.2:计算对象x i的异常度EOF(x i).
Step6.3:若EOF(x i)>v,则O=O
∪
x i.
Step7:输出异常对象的集合O.
算法IEOM主要涉及信息熵的计算,而信息熵来
源于等价类的计算.本文采用文献[18]中基数排序的
思想计算等价类,时间复杂度降为线性.因此,最坏情
况下IEOM算法的时间复杂度为O(mn).其中:m为
870
控制与决策
第28卷
属性的个数,n 为对象的个数.2.3示例说明
给定一个信息系统IS =(U,A,V,f ).其中:U =
{x 1,x 2,x 3,x 4,x 5,x 6},A ={a,b,c }.系统如表1所示,
设异常阈值v =0.75.
表1
信息系统
U a
b
c
x 1000x 2121x 3022x 4220x 5021x 6
1
1
2
计算属性集A 中每个属性的划分为
U/IND(a )={{x 1,x 3,x 5},{x 2,x 6},{x 4}},U/IND(b )={{x 1},{x 2,x 3,x 4,x 5},{x 6}},U/IND(c )={{x 1,x 4},{x 2,x 5},{x 3,x 6}}.
根据信息熵的定义,单属性的信息熵分别为
H ({a })=?3∑
i =1
p (X i )log p (X i )=?(12log (12)
+13log (13)+16log (16
))=0.4392,
H ({b })=?3∑
i =1
p (X i )log p (X i )=?(16log (16)
+23log (23)+16log (16
))=0.3768,
H ({c })=?3∑
i =1
p (X i )log p (X i )=?(1
3log (13)
+1
3log (13)+13log (13))=0.4771.去除某个对象后的信息熵为
H x 1({a })=H x 3({a })=H x 5({a })=
?(25log (25)+25log (25)+15log (15))=0.4582,H x 2({a })=H x 6({a })=
?(35log (35)+15log (15)+15log (15
))=0.4127,H x 4({a })=?(35log (35)+25log (25))
=0.2923,
H x 1({b })=H x 6({b })=
?(45log (45)+15log (15
))=0.2173,H x 2({b })=H x 3({b })=H x 4({b })=H x 5({b })=
?(15log (15)+35log (35)+15log (15))=0.4127,H x 1({c })=H x 4({c })=
?(15log (15)+25log (25)+25log (25
))=0.4582,H x 2({c })=H x 5({c })=?(15log (15)+25log (25)+25log (25))=0.4582,
H x 3({c })=H x 6({c })=?(15log (15)+25log (25)+25log (25))=0.4582.根据相对信息熵的定义有
RH {a }(x 1)=RH {a }(x 3)=RH {a }(x 5)=
0.4582/0.4392=1.0433,RH {a }(x 2)=RH {a }(x 6)=0.4127/0.4392=0.9397,
RH {a }(x 4)=0.2923/0.4392=0.6655,RH {b }(x 1)=RH {b }(x 6)=0.2173/0.3768=0.5767,
RH {b }(x 2)=RH {b }(x 3)=RH {b }(x 4)=RH {b }(x 5)=0.4127/0.3768=1.0953,RH {c }(x 1)=RH {c }(x 4)=0.4582/0.4771=0.9604,RH {c }(x 2)=RH {c }(x 5)=0.4582/0.4771=0.9604,RH {c }(x 3)=RH {c }(x 6)=0.4582/0.4771=0.9604.
根据信息熵大小,得到单属性按信息熵递增序列S =?b,a,c ?和属性子集序列AS =?A 1,A 2,A 3?=
?{a,b,c },{a,c },{c }?.针对属性子集序列求其对象相
对信息熵为
RH {A 1}(x 1)=RH {A 1}(x 2)=RH {A 1}(x 3)=RH {A 1}(x 4)=RH {A 1}(x 5)=RH {A 1}(x 6)=0.8982,RH {A 2}(x 1)=RH {A 2}(x 2)=RH {A 2}(x 3)=RH {A 2}(x 4)=RH {A 2}(x 5)=RH {A 2}(x 6)=0.8982,RH {A 3}(x 1)=RH {A 3}(x 2)=RH {A 3}(x 3)=RH {A 3}(x 4)=RH {A 3}(x 5)=RH {A 3}(x 6)=0.9604.
对象x 的权重为
W {a }(x 1)=W {a }(x 3)=W {a }(x 5)=1/2,W {a }(x 2)=W {a }(x 6)=1/3,W {a }(x 4)=1/6,W {b }(x 1)=W {b }(x 6)=1/6,W {b }(x 2)=W {b }(x 3)=W {b }(x 4)=W {b }(x 5)=2/3,
第6期陈玉明等:一种基于信息熵的异常数据挖掘算法871
W{c}(x1)=W{c}(x2)=W{c}(x3)=
W{c}(x4)=W{c}(x5)=W{c}(x6)=1/3,
W{A1}(x1)=W{A1}(x2)=W{A1}(x3)=
W{A1}(x4)=W{A1}(x5)=W{A1}(x6)=1/6,
W{A2}(x1)=W{A2}(x2)=W{A2}(x3)=
W{A2}(x4)=W{A2}(x5)=W{A2}(x6)=1/6,
W{A3}(x1)=W{A3}(x2)=W{A3}(x3)=
W{A3}(x4)=W{A3}(x5)=W{A3}(x6)=1/3.
由计算得出对象x1～x6的异常度分别为
EOF(x1)≈0.740 EOF(x3)≈0.660 EOF(x5)≈0.635 对象x6的异常度大于异常阈值,判断为异常对象. 3实验分析 为了考察本文算法的有效性,采用UCI数据集中的Lymphography数据集和Wisconsin Breast Cancer数据集进行测试.在此基础上,将本文算法IEOM与DIS 算法[5]、FindCBLOF算法[16]和KNN算法[20]进行性能比较. 3.1Lymphography数据集 首先对Lymphography数据集进行实验.该数据集包括148个对象,18个条件属性,1个决策属性.148个对象分为normal?nd(1.35%),metastases(54.73%), malign lymph(41.22%)和?brosis(2.7%)四类.normal ?nd和?brosis两个类别所占比例小,是稀少类,可以看作异常对象.实验结果如表2所示. 表2Lymphography数据集实验结果 异常度前k%属于稀少类的对象个数/属于稀少类的比例 的对象/对象个数 IEOM DIS FindCBLOF KNN 5%/76/100%5/83%4/67%5/83% 6%/96/100%6/100%4/67%5/83% 8%/126/100%6/100%4/67%6/100% 20%/306/100%6/100%6/100%6/100% 表2中,对于U中每个对象x,分别采用IEOM算法、DIS算法、FindCBLOF算法和KNN算法计算对象x的异常度,并根据异常度由高到低对U中的对象进行排序;然后统计异常度前k%的对象覆盖了多少稀少类对象.“异常度前k%的对象/对象个数”表示在采用某种算法计算U中对象的异常程度并排序后,异常度排在前k%的对象和这些对象的个数,“属于稀少类的对象个数”是指在由该算法所计算出的异常度排在前k%的对象中,属于稀少类的对象个数.稀少类可以作为异常数据,因此,属于稀少类对象的个数即为属于异常对象的个数. 由表2可见,对于Lymphography数据集,IEOM 算法的性能明显好于其他方法.在计算由各类方法所找出的异常对象中真正的异常对象所占的比例方面, IEOM算法得到的结果均高于其他算法.例如,在各类方法所找出的异常度排在前5%的对象中(共计7个对象),IEOM算法检测出的真正的异常对象为6个(占所有异常对象比例为100%),DIS和KNN算法检测出5个异常对象,FindCBLOF算法检测出4个异常对象,比例均低于IEOM算法. 3.2Wisconsin Breast Cancer数据集 Wisconsin Breast Cancer数据集包含699个对象, 8个条件属性,1个决策属性.为了形成不均匀的分布,参照文献[21],从数据集中移去一些属于“malignant”类的对象.最终数据集包括483个对象,其中39个属于“malignant”类,444个属于“benign”类.Wisconsin Breast Cancer数据集中,“malignant”属于稀少类,看作异常数据,实验结果如表3所示. 表3Wisconsin Breast Cancer数据集实验结果异常度前k%属于稀少类的对象个数/属于稀少类的比例 的对象/对象个数 IEOM DIS FindCBLOF KNN 1%/44/10%4/10%4/10%4/10% 2%/87/18%5/13%7/18%8/21% 4%/1614/36%11/28%14/36%16/41% 6%/2421/54%18/46%21/54%20/51% 8%/3228/72%24/62%27/69%27/69% 10%/4032/82%29/74%32/82%32/82% 12%/4838/97%36/92%35/90%37/95% 14%/5639/100%39/100%38/97%39/100% 16%/6439/100%39/100%39/100%39/100% 18%/7239/100%39/100%39/100%39/100% 20%/8039/100%39/100%39/100%39/100% 28%/11239/100%39/100%39/100%39/100% 由表3可见,对于Wisconsin Breast Cancer数据集,DIS算法、FindCBLOF算法和KNN算法的性能非常接近,IEOM算法的性能好于这3种算法. 4结论 本文将信息论中的信息熵概念应用于异常数据挖掘领域,在粒计算的框架中提出基于信息熵的异常数据挖掘方法,并给出了一种基于信息熵的异常数据挖掘算法.该算法充分利用信息熵度量不确定性数据方面的优势,可以在不确定性数据中高效地挖掘出异常对象.目前,采用信息熵的方法进行异常数据挖掘的研究还较为少见,本文的研究拓展了信息论和粒计算理论研究的应用范围,为异常数据挖掘研究提供了一条新的途径.理论分析和实验表明,本文所提出的算法是有效可行的. 872控制与决策第28卷 参考文献(References) [1]Hawkins D.Identi?cations of outliers[M].London: Chapman and Hall,1980:1-2. [2]Han J W.Data mining:Concepts and technologies[M].San Francisco:Morgan Kaufmann,2001:381-394. [3]江峰,杜军威,眭跃飞,等.基于边界和距离的离群点检 测[J].电子学报,2010,38(3):700-705. (Jiang F,Du J W,Sui Y F,et al.Outlier detection based on boundary and distance[J].Acta Electronica Sinica,2010, 38(3):700-705.) [4]Knorr E,Ng R,Tucakov V.Distance-based outliers: Algorithms and applications[J].J of Very Large Databases, 2000,8(3/4):237-253. [5]Rousseeuw P J,Leroy A M.Robust regression and outlier detection[M].New York:John Wiley&Sons,1987:1-18. [6]Johnson T,Kwok I,Ng R T.Fast computation of2- dimensional depth contours[C].Proc of the4th Int Conf on Knowledge Discovery and Data Mining.New York:AAAI Press,1998:224-228. [7]Jain A K,Murty M N,Flynn P J.Data clustering:A review[J].ACM Computing Surveys,1999,31(3):264-323. [8]苗夺谦,王国胤,刘清,等.粒计算:过去、现在与展 望[M].北京:科学出版社,2007:121-136. (Miao D Q,Wang G Y,Liu Q,et al.Granular computing: Past,present and prospects[M].Beijing:Science Press, 2007:121-136.) [9]Zadeh L A.Fuzzy sets and information granularity[C]. Advances in Fuzzy Set Theory and Applications. Amsterdam:North-Holland,1979:3-18. [10]Pawlak Z.Rough sets[J].Int J of Computer and Information Science,1982,11(5):341-356. [11]Zhang B,Zhang L.Theory and applications of problem solving[M].New York:Elsevier Science Publishers,1992: 86-99. [12]Wang G Y.Granular computing based data mining in the views of rough set and fuzzy set[C].Novel Developments in Granular Computing:Applications for Advanced Human Reasoning and Soft Computation.Hershey:IGI Global,2010:401-416.[13]苗夺谦,王珏.粗糙集理论中概念与运算的信息表示[J]. 软件学报,1999,10(2):113-116. (Miao D Q,Wang J.An information representation of the concepts and operations in rough set theory[J].J of Software,1999,10(2):113-116.) [14]Pal Sankar K,Uma Shankar B,Pabitra M.Granular computing,rough entropy and object extraction[J].Pattern Recognition Letters,2005,26(16):2509-2517. [15]苗夺谦,范世栋.知识的粒度计算及其应用[J].系统工程 理论与实践,2002,22(1):48-56. (Miao D Q,Fan S D.The calculation of knowledge granulation and its application[J].Systems Engineering Theory&Practice,2002,22(1):48-56.) [16]Qian Y H,Liang J Y,Wu W Z,et al.Partial orderings of information granulations:A further investigation[J]. Expert Systems,2012,29(1):3-24. [17]陈玉明,苗夺谦.基于幂图的属性约简搜索式算法[J].计 算机学报,2009,32(8):1486-1492. (Chen Y M,Miao D Q.Searching algorithm for attribute reduction based on power graph[J].Chinese J of Computers,2009,32(8):1486-1492.) [18]徐章艳,刘作鹏,杨炳儒,等.一个复杂度为 max{O(∣C∣∣U∣),O(∣C∣2∣U∣/∣C∣)}的快速属性约简算法[J]. 计算机学报,2006,29(3):391-399. (Xu Z Y,Liu Z P,Yang B R,et al.A quick attribute reduction algorithm with complexity of max{O(∣C∣∣U∣), O(∣C∣2∣U∣/∣C∣)}[J].Chinese J of Computers,2006,29(3): 391-399.) [19]He Z Y,Deng S C,Xu X F.Discovering cluster based local outliers[J].Pattern Recognition Letters,2003,24(9- 10):1651-1660. [20]Ramaswamy S,Rastogi R,Shim K.Ef?cient algorithms for mining outliers from large datasets[C].Proc of the2000 ACM SIGMOD Int Conf on Management of Data.New York:ACM,2000:427-438. [21]Harkins S,He H X,Willams G J,et al.Outlier detection using replicator neural networks[C].Proc of the4th Int Conf on Data Warehousing and Knowledge Discovery. France:Springer Berlin Heidelberg,2002:170-180. (19)中华人民共和国国家知识产权局 (12)发明专利申请 (10)申请公布号 (43)申请公布日 (21)申请号 201910372132.X (22)申请日 2019.05.06 (71)申请人 安徽工业大学 地址 243002 安徽省马鞍山市湖东路59号 (72)发明人 董治麟 郑近德 潘海洋 童靳于 刘庆运 张义方 (74)专利代理机构 合肥顺超知识产权代理事务 所(特殊普通合伙) 34120 代理人 周发军 (51)Int.Cl. G06K 9/62(2006.01) G06K 9/00(2006.01) G06N 3/00(2006.01) (54)发明名称 一种基于精细时移多尺度排列熵与萤火虫 算法优化支持向量机的故障诊断方法 (57)摘要 本发明公开了故障诊断技术领域的一种基 于精细时移多尺度排列熵与支持向量机的故障 诊断方法，本发明的步骤为：采集待诊断物体的 原始故障振动信号；提取原始故障振动信号的精 细时移多尺度排列熵值；将故障样本分为多个训 练样本和测试样本；采用多个训练样本对基于萤 火虫优化的支持向量机多故障分类器进行训练； 采用已训练完成的多故障分类器(萤火虫算法优 化的支持向量机)对测试样本进行分类；根据分 类结果识别故障物体的工作状态和故障类型。本 发明提出的故障诊断方法在特征提取的过程中 有较高的创新性，在故障识别过程中具有较高的 识别度。权利要求书3页 说明书7页 附图4页CN 110084316 A 2019.08.02 C N 110084316 A 1.一种基于精细时移多尺度排列熵与萤火虫算法优化的支持向量机的故障诊断方法，其特征在于：包括步骤： 步骤1-1：采集待诊断物体的原始故障振动信号； 步骤1-2：提取原始故障振动信号的精细时移多尺度排列熵值； 步骤1-3：将故障特征样本分为多个训练样本和测试样本； 步骤1-4：采用多个训练样本对基于萤火虫算法优化的支持向量机的多故障特征分类器进行训练； 步骤1-5：采用已训练完成的多故障特征分类器对测试样本进行分类； 步骤1-6：根据分类结果识别物体的工作状态和故障类型。 2.根据权利要求1所述的一种基于精细时移多尺度排列熵与萤火虫算法优化的支持向量机的故障诊断方法，其特征在于：步骤1-2中所测取原始故障信息的精细时移多尺度排列熵值的过程包括： 步骤2-1：对获取的原始故障振动信号进行时移粗粒化； 步骤2-2：计算同一尺度因子τ下生成的τ个符号序列的概率； 步骤2-3：对同一尺度下的所有符号概率求平均，通过信息熵的定义得到原始故障振动信号的精细时移多尺度排列熵值； 步骤2-4:对所有的尺度因子重复步骤2-2到2-3的操作，得到振动信号在所有尺度因子下的精细时移多尺度排列熵值。 3.根据权利要求1所述的一种基于精细时移多尺度排列熵与萤火虫算法优化的支持向量机的故障诊断方法，其特征在于：步骤1-5中所述萤火虫算法优化的支持向量机用于对故障特征样本中各样本的工作状态和故障类型进行分类，并分别根据已经训练完成的多故障特征分类器中的每单一萤火虫算法优化的支持向量机的输出O(y)是否是+1进行判断；具体判断步骤包括： 步骤3-1：若输出是O(y)＝+1，则停止输入到下一个支持向量机，输出该测试样本集的分类； 步骤3-2：若输出是O(y)＝-1，则将该测试样本输入到下一个支持向量机，直到输出结果为+1时，输出测试样本的分类。 4.根据权利要求2所述的一种基于精细时移多尺度排列熵与萤火虫算法优化的支持向量机的故障诊断方法，其特征在于：步骤2-1中所述时移粗粒化过程包括: 步骤4-1：对于给定的尺度因子τ和时间序列X＝{x 1,x 2,...x N }，经过时移的处理，可以 得到新的时间序列： 其中，k(1≤k≤τ)和β(β＝τ)是正整数，分别表示时间序列的起点和间隔点数，i表示时间序列y的第i个点；Δ(k，β)＝(N - β)/k，是四舍五入的整数并表示上边界个数；步骤4-2：尺度因子为τ，对得到的y k ,β 中的每个序列依次进行粗粒化， 其表达式为如下：其中，j表示时间序列Z的第j个点。 权 利 要 求 书1/3页2CN 110084316 A 最大熵算法笔记 最大熵，就是要保留全部的不确定性，将风险降到最小，从信息论的角度讲，就是保留了最大的不确定性。 最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫"最大熵模型"。 匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式-- 指数函数。 我们已经知道所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。 最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS (generalized iterative scaling) 的迭代算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤： 1. 假定第零次迭代的初始模型为等概率的均匀分布。 2. 用第N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。 3. 重复步骤2 直到收敛。 GIS 最早是由Darroch 和Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨（Csiszar) 解释清楚的，因此，人们在谈到这个算法时，总是同时引用Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每 次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用GIS。大家只是通过它来了解最大熵模型的算法。 八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra) 在IBM 对GIS 算法进行了两方面的改进，提出了改进迭代算法IIS （improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有IBM 有条件是用最大熵模型。 由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。 收稿日期!"##$%&"%&’基金项目!国家自然科学基金重点资助项目()*+’$##&,作者简介!徐章艳-男-&*."年生-博士研究生-讲师-研究方向为模糊集-粗糙集-数据挖掘/杨炳儒-男-&*0’年生-教授-博士生导师-研究方向为人工智能-数据挖掘/郭燕萍-女-&*+"年生-硕士研究生-研究方向为粗糙集-数据挖掘/宋威-男-&*+#年生-博士研究生-研究方向为粗糙集-数据挖掘1 基于信息熵的快速求核算法 徐章艳&-"-杨炳儒"-郭燕萍&-宋威" &(广西师范大学 计算机系-广西桂林$0&##0,"( 北京科技大学 信息工程学院-北京&###+’, 2%3456!789:67.";84<==1>=31>? 摘 要!基于信息熵的求核算法的最好时间复杂度为@(A B A " A C A 6=D A C A ,1为降低算法的时间复杂度-本文首先给出了基于信息熵的简化差别矩阵及相应核的定义-并证明了该核与基于信息熵的属性约简的核是等价的1然后以基数排序的思想设计了一个新的求C E B 的算法-其时间复杂度为@(A B A A C A ,1在此基础上-设计了一个新求核算法-其时间复杂度被降为347F @(A B A A C E B A " ,-@(A B A A C A ,G 1最后用一个实例说明了新求核算法的高效性1关键词!H =I D 论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 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)每个对 ２００８，４４（２７） １前言 基因表达数据具有很高的基因维数和相对较少的样本数，通常是几千甚至上万个基因而只有几十个样本。在对组织样本聚类时，如果不对基因数据进行降维处理，而直接进行样本聚类，将不会得到有意义的结果。这是因为大多数的无关基因数据淹没了数量很小的对疾病分型有用的基因数据，所以在对组织样本聚类之前先要进行降维处理。目前对高维数据进行降维处理的方法较多，其中有主元分析，粗糙集属性约减，小波变换及特征提取［１］等。较为常用的主元分析法是一种无导师型线性分析方法，它将原始特征空间投影到新的特征空间，但新的特征只是原特征的线性组合，不再具有生物学意义。而特征提取是在原始的特征空间中挑选有助于样本分型的代表基因，因而保留了特征的生物学意义。 一般的特征提取都要有先验知识作指导，即在已知一定的样本分类情况下，挑选对分类贡献较大的特征，这对于临床医学中癌症的诊断有一定的局限性。由于大多数未知类型的疾病缺少相关知识，所以需要一种方法能够在无指导情况下挑选代表基因对组织样本进行判别。根据生物学知识可知，具有相同调控功能的基因可能有相似的表达模式，因此对基因聚类，将功能相关的基因按表达模式的相似性归类［２］，有助于对未知功能的基因进行研究。 本文采用双向聚类算法模型即先从特征／基因方向聚类，挑选出特征基因后再对样本聚类。根据代表熵的大小判断基因聚类质量的好坏，引入波动系数挑选类内代表基因。将该算法应用于基因表达数据集，实验结果表明，在缺乏先验知识的情况下本文的算法提高了样本分型的准确度。 ２双向聚类算法模型 本文采用的双向聚类算法是分别从基因和样本两个方向聚类。基因聚类可以挑选出特征基因，样本聚类用来对疾病分型。其算法流程如图１所示。首先是对基因数据集进行预处理，包括滤去在样本中无变化的基因及表达值的规一化处理。接着是采用ＳＯＭ网络从基因方向上聚类，将表达模式相近的基因归为一类。再从每一个簇中挑选该类的代表基因，构成总特征 基于代表熵的基因表达数据聚类分析方法 陆媛，杨慧中 ＬＵＹｕａｎ，ＹＡＮＧＨｕｉ－ｚｈｏｎｇ 江南大学通信与控制工程学院，江苏无锡２１４１２２ ＳｃｈｏｏｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ＆ＣｏｎｔｒｏｌＥｎｇｉｎｅｅｒｉｎｇ，ＪｉａｎｇｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｗｕｘｉ，Ｊｉａｎｇｓｕ２１４１２２，Ｃｈｉｎａ Ｅ－ｍａｉｌ：ｌｙ１９８３．ｃｎ＠１６３．ｃｏｍ ＬＵＹｕａｎ，ＹＡＮＧＨｕｉ－ｚｈｏｎｇ．Ｃｌｕｓｔｅｒｉｎｇａｎａｌｙｓｉｓｍｅｔｈｏｄｓｏｆｇｅｎｅｅｘｐｒｅｓｓｉｏｎｄａｔａｂａｓｅｄｏｎｒｅｐｒｅｓｅｎｔａｔｉｖｅｅｎｔｒｏｐｙ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００８，４４（２７）：１５１－１５３． Ａｂｓｔｒａｃｔ：Ｂｅｃａｕｓｅｇｅｎｅｅｘｐｒｅｓｓｉｏｎｄａｔａｉｓｈｉｇｈｄｉｍｅｎｓｉｏｎｓａｎｄｓｍａｌｌｓａｍｐｌｅｓ，ｅｓｐｅｃｉａｌｌｙｔｈｅｌｅｓｓｐｒｉｏｒｉｋｎｏｗｌｅｄｇｅ，ａｔｗｏ－ｗａｙｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｖｅｅｎｔｒｏｐｙｉｓｐｒｏｐｏｓｅｄ，ｗｈｉｃｈｉｓｃｏｍｂｉｎｅｄｗｉｔｈｔｈｅａｄｖａｎｔａｇｅｓｏｆＳｅｌｆＯｒｇａｎｉｚｉｎｇｆｅａｔｕｒｅＭａｐ（ＳＯＭ）ｎｅｕｒａｌｎｅｔｗｏｒｋ．Ｆｉｒｓｔ，ｔｈｅｃｌｕｓｔｅｒｉｎｇｏｆｇｅｎｅｓｉｓｒｅａｌｉｚｅｄｔｈｒｏｕｇｈｔｈｅＳＯＭｎｅｔｗｏｒｋ，ａｎｄｃｈａｒａｃｔｅｒｉｓｔｉｃｇｅｎｅｓａｒｅｓｅｌｅｃｔｅｄａｃｃｏｒｄｉｎｇｔｏｔｈｅｆｌｕｃｔｕａｔｉｏｎｃｏｅｆｆｉｃｉｅｎｔ．Ｔｈｅｎｔｈｅｑｕａｌｉｔｙｏｆｇｅｎｅｃｌｕｓｔｅｒｉｎｇｉｓｄｅｃｉｄｅｄｂｙｔｈｅｖａｌｕｅｏｆｒｅｐｒｅｓｅｎｔａｔｉｖｅｅｎ－ｔｒｏｐｙ．Ｆｉｎａｌｌｙ，ＳｅｌｆＯｒｇａｎｉｚｉｎｇＦｅａｔｕｒｅＭａｐａｌｇｏｒｉｔｈｍｉｓｅｍｐｌｏｙｅｄｔｏｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｓａｍｐｌｅｓ．Ｔｈｉｓｐｒｏｃｅｓｓｉｓａｐｐｌｉｅｄｔｏｔｗｏｐｕｂ－ｌｉｓｈｅｄｄａｔａｓｅｔｓｏｆｇｅｎｅｅｘｐｒｅｓｓｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｒｅｄｕｃｅｔｈｅｆｅａｔｕｒｅｓｐａｃｅｄｉｍｅｎｓｉｏｎｓａｎｄｉｍｐｒｏｖｅｔｈｅａｃｃｕｒａｃｙｏｆｃｌｕｓｔｅｒｉｎｇ． Ｋｅｙｗｏｒｄｓ：ｒｅｐｒｅｓｅｎｔａｔｉｖｅｅｎｔｒｏｐｙ；ｆｌｕｃｔｕａｔｉｏｎｃｏｅｆｆｉｃｉｅｎｔ；ＳｅｌｆＯｒｇａｎｉｚｉｎｇｆｅａｔｕｒｅＭａｐ（ＳＯＭ）ａｌｇｏｒｉｔｈｍ；ｇｅｎｅｅｘｐｒｅｓｓｉｏｎｄａｔａ 摘要：针对基因表达数据样本少，维数高的特点，尤其是在样本分型缺乏先验知识的情况下，结合自组织特征映射的优点提出了基于代表熵的双向聚类算法。该算法首先通过自组织特征映射网络（ＳＯＭ）对基因聚类，根据波动系数挑选特征基因。然后根据代表熵的大小判断基因聚类的好坏，并确定网络的神经元个数。最后采用ＦＣＭ（ＦｕｚｚｙＣＭｅａｎｓ）聚类算法对挑选出的特征基因集进行样本分型。将该算法用于两组公开的基因表达数据集，实验结果表明该算法在降低特征维数的同时，得出了较高的聚类准确率。关键词：代表熵；波动系数；自组织特征映射网络算法；基因表达数据 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２００８．２７．０４８文章编号：１００２－８３３１（２００８）２７－０１５１－０３文献标识码：Ａ中图分类号：ＴＰ３１１ 基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０６７４０２９）。 作者简介：陆媛（１９８３－），硕士生，主要研究方向：数据挖掘、聚类算法；杨慧中（１９５５－），教授，博士生导师，主要研究方向：工业过程建模与优化控制及相关理论与技术的研究。 收稿日期：２００７－１１－１３修回日期：２００８－０２－２９ ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用１５１ 计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。 ---------------------------------------------------------------最新资料推荐------------------------------------------------------ 一种利用信息熵的群体智能聚类算法 !#$%计算机工程与应用前言数据挖掘是一个多学科交叉的研究领域，涉及数据库技术、人工智能、机器学习、统计学、知识获取、生物计算等学科。 这些学科的发展为数据挖掘的研究提供了新的机遇与挑战。 聚类是数据挖掘的重要任务之一，目前主要的聚类算法可以划分为如下几类()： 划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法等。 这些方法大多数需要一些参数限制，设定聚的数目，而且聚类结果对初始状态及参数非常敏感。 近年来，一些学者开始应用群体智能（*+,-. /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 （)! 实验一信息熵与图像熵计算（2 学时） 一、实验目的 1.复习MATLAB的基本命令，熟悉MATLAB下的基本函数； 2.复习信息熵基本定义,能够自学图像熵定义和基本概念。 二、实验内容 1.能够写出MATLAB源代码，求信源的信息熵； 2.根据图像熵基本知识，综合设计出MATLAB程序，求出给定图像的图像熵。 三、实验仪器、设备 1.计算机－系统最低配置256M内存、P4 CPU； 2.MATLAB编程软件。 四实验流程图 五实验数据及结果分析 四、实验原理 1.MATLAB中数据类型、矩阵运算、图像文件输入与输出知识复习。 2.利用信息论中信息熵概念，求出任意一个离散信源的熵（平均自信息量）。自信息是一个随机变量,它是指某一信源发出某一消息所含有的信息量。所发出的消息不同，它们所含有的信息量也就不同。任何一个消息的自信息量都代表不了信源所包含的平均自信息量。不能作为整个信源的信息测度，因此定义自信息量的数学期望为信源的平均自信息量： 1( ) 1 ( ) [log ] ( ) log ( ) i n i i p a i H E p a p a X 信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。它是从平均意 义上来表征信源的总体特性的。对于某特定的信源，其信息熵只有一个。不同的信源因统计特性不同，其熵也不同。 3.学习图像熵基本概念，能够求出图像一维熵和二维熵。 图像熵是一种特征的统计形式，它反映了图像中平均信息量的多少。图像的一维熵表示图像中灰度分布的聚集特征所包含的信息量，令Pi表示图像中灰度值为i的像素所占的比例，则定义灰度图像的一元灰度熵为： 2550 log i i i p p H 图像的一维熵可以表示图像灰度分布的聚集特征，却不能反映图像灰度分布的空间特征，为了表征这种空间特征，可以在一维熵的基础上引入能够反映灰度分布空间特征的特征量来组成图像的二维熵。选择图像的邻域灰度均值作为灰度2 第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—means聚类算法的试卷成绩分析研 究 第39卷第4期 2009年7月 河南大学(自然科学版) JournalofHenanUniversity(NaturalScience) V o1.39NO.4 Ju1.2009 基于k—means聚类算法的试卷成绩分析研究 谭庆' (洛阳师范学院信息技术学院,河南洛阳471022) 摘要:研究_rk-means聚类算法,并将此算法应用于高校学生试卷成绩分析中.首先对数据进行了预处理,然后 使用k-means算法,对学生试卷成绩进行分类评价.用所获得的结果指导学生的学习和今后的教学工作. 关键词:数据挖掘;聚类;k-means算法;试卷成绩 中圈分类号:TP311文献标志码:A文章编号:1003—4978(2009)04—0412—04 AnalysisandResearchofGradesofExaminationPaper BasedonK—meansClusteringAlgorithm TANQing (Acaderny.l,InformationTechnologY,LuoyangNormalUniversity,LuoyangHenan47102 2,China) Abstract:Thispaperresearcheslhekmeansclusteringalgorithmandappliesittotheanalysiso fthegradedataof examinationpaperofhighereducationschoolSstudents.Firstly,itpreprocessesthedatabefor eminingThen,it usesthek— 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 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思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解【CN110084316A】一种基于精细时移多尺度排列熵与萤火虫算法优化支持向量机的故障诊断方法【专
最大熵算法笔记
基于信息熵的快速求核算法
各种聚类算法及改进算法的研究
基于代表熵的基因表达数据聚类分析方法
数据挖掘中的聚类分析方法
一种利用信息熵的群体智能聚类算法
实验一-信息熵与图像熵计算-正确
一种基于粒子群算法的聚类算法
基于k—means聚类算法的试卷成绩分析研究
各种聚类算法的比较
相关主题
文本预览