第35卷第4期 2012年4月 计 算 机 学 报 Vo1.35 No.4 Apr.2012 CHINESE J OURNAL OF COMPUTERS 基于熵的模糊信息测度研究 丁世飞” 朱 红” 许 新征” 史忠植 ”(中国矿业大学计算机科学与技术学院江苏徐州221l16) 北京100190) 。 (中国科学院计算技术研究所智能信息处理重点实验室摘 要模糊信息测度(Fuzzy Information Measures,FIM)是度量两个模糊集之间相似性大小的一种量度,在模式 识别、机器学习、聚类分析等研究中,起着重要的作用.文中对模糊测度进行了分析,研究了基于熵的模糊信息测度 理论:首先,概述了模糊测度理论,指出了其优缺点;其次,基于信息熵理论,研究了模糊熵理论,建立了模糊熵公理 化体系,讨论了各种模糊熵,在此基础上,提出了模糊绝对熵测度、模糊相对熵测度等模糊熵测度;最后,基于交互 熵理论,建立了模糊交互熵理论,进而提出了模糊交互熵测度.这些测度理论,不仅丰富与发展了FIM理论,而且为 模式识别、机器学习、聚类分析等理论与应用研究提供了新的研究方法. 关键词模糊熵;模糊交互熵;模糊绝对熵测度;模糊相对熵测度;模糊交互熵测度 TP18 DOI号:10.3724/SP.J.1016.2012.00796 中图法分类号Entropy—Based Fuzzy Information Measures DING Shi—Fei , ZHU Hong ’ XU Xin—Zheng ’ SHI Zhong—Zhi ’ ”(School of Computer Science and Technology。China University of Mining and Technology,Xuzhou,Jiangsu 22l116) (Key Laboratory of Intelligent Information Processing,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190) Abstract Fuzzy Information Measures(FIM)are to be used to measure similarity between two fuzzy sets and plays an important part in pattern recognition,machine learning,clustering analy— sis.In this paper,FIM theory is studied based on information entropy.Firstly,the existing FIM theories are introduced and some advantages and disadvantages are pointed out.Secondly,based on information entropy,the fuzzy information entropy is studied,four axioms about fuzzy entro— PY are set up,and all kinds of definitions of fuzzy entropy are discussed.Based on fuzzy entropy, two new fuzzy entropy measures,fuzzy absolute information measure(FAIM)and fuzzy relative information measure(FRIM)are proposed.At last,based on cross entropy,the fuzzy cross en— tropy is discussed,and fuzzy cross entropy measure(FCEM)is set up.All these measures,not only enrich and develop FIM theory,but also provide a new research approach for studies on pat— tern recognition,machine learning,clustering analysis et al in theory and application. Keywords fuzzy entropy;fuzzy cross entropy;fuzzy absolute entropy measure(FAEM);fuzzy relative entropy measure(FREM);fuzzy cross entropy measure(FCEM) 收稿日期:2008—01-03;最终修改稿收到日期:201卜10一O9.本课题得到国家自然科学基金项目(41074003,60975039)、国家“九七三”重点 基础研究发展规划项目基金(2007CB311004)、江苏省基础研究计划(自然科学基金)(BK2009093)和中国科学院智能信息处理重点实验 室开放基金项目(IIP2010—1)资助.丁世飞,男,1963年生,博士,教授,博士生导师,主要研究领域为智能信息处理、模式识别与人工智能、 机器学习及数据挖掘理论与应用研究.E—mail:dingsf@cumt.edu.cn;dingshifei@sina.corn.朱红,女,1970年生,博士研究生,副教授, 中国计算机学会(CCF)会员,主要研究方向为智能信息处理、机器学习以及粒度计算等.许新征,男。1980年生,博士研究生,讲师,中国 计算机学会(CCF)会员,主要研究方向为智能信息处理、模式识别、机器学习以及粒度计算等.史忠植,男,1941年生,教授,博:上生导师, 主要研究领域包括智能科学、图像处理、认知计算、机器学习、Agent等. 4期 丁世飞等:基于熵的模糊信息测度研究 引 言 模式识别(Pattern Recognition,PR)是智能信 息处理中的一个重要学科领域,不是一门简单的分 类学,它包括对系统的描述、理解与综合,它要通过 大量信息对复杂过程进行学习、判断和寻找规律.模 式识别诞生于20世纪2O年代,随着4o年代计算机 的出现,50年代人工智能的兴起,模式识别在60年 代初迅速发展成一门学科,它所研究的理论和方法 在很多科学和技术领域中得到了广泛的重视,推动 了人工智能系统的迅速发展【。’ .从本质上说,PR方 法就是将观测模式向量与已知模式类相比较,而归 根结底是测试模式与已知模式类中的模式向量相比 较,如果测试模式与模式类最相似,则就将其归入该 模式类中,以实现模式的分类识别.因此研究如何度 量两个模式之间的相似性测度问题是PR研究中的 核心问题之一. 为了能划分模式的类别,必须首先定义模式相 似性测度,用来刻画各模式之间的相似程度.常用的 主要有距离测度(差值测度),它是以两个模式向量 矢端的距离为基础,是两个向量各对应分量之差 的函数,两个模式越相似,其距离测度值越小.常 见的距离测度有欧氏(Euclidean)距离、绝对值距 离(或Manhattan距离)、切氏(Chebyshev)距离、明 氏(Minkowski)距离及马氏(Mahalanobis)距离 等【 ;相似测度,它是以两个模式向量的方向是否 相近作为考虑的基础,向量的大小并不重要,两个模 式向量越相似,其相似性测度值越大.常用的几种相 似性测度有夹角余弦(也称为角度相似系数)、相关 系数、指数相似系数等;匹配测度,这种测度多用于 医学和植物的分类之中.在有些情况下,特征只有两 个状态,对象或具有此特征或不具有此特征.此时,若 对象有此特征,则相应分量定义为1;若对象无此特 征,则相应分量定义为0,这就是所谓的二值特征.对 于二值n维模式向量,常用的匹配测度有Tanimoto 测度、Rao测度、简单匹配系数、Dice系数、Kulzinsky 系数等.这些测度理论与方法,在模式识别与分类、 图像处理以及无监督学习理论中发挥了重要的作 用,但本质上他们都是利用了确定环境下两模式的 相似性度量.而在实际工作中,人们经常遇到随机环 境、模糊环境等不确定性环境,研究不确定性环境下 两模式的相似性度量具有重要的理论意义与实践 意义. 美国控制论专家扎德(Zadeh I A)于1965年在 《Information and Control》杂志上发表了题为 “Fuzzy sets”的著名论文,这标志着模糊理论的产 生 ].该理论引起了数学界和科技工程界的极大兴 趣并对其进行了深入广泛的研究,理论成果和应用 成果不断出现,从而创建了一门新的学科——模糊 数学 ].有关模糊信息处理的理论和应用取得了重 大进展,并由此产生了模糊模式识别(Fuzzy Pattern Recognition,FPR)方法,在FPR理论与应用研究 中,模糊贴近度作为两个模糊集之间彼此接近的程 度的一种度量,起到了关键作用 ].但这种模糊贴近 度是建立在模糊贴近度公理化基础之上,计算复杂 度较高.本文将研究基于距离测度公理化理论基础 上的模糊信息测度l8。¨,这样一方面弱化了模糊贴 近度公理化条件,从而增大了模糊测度的应用领域, 另一方面,不仅进一步丰富与发展了FIM理论,而 且为模式识别、机器学习、聚类分析等理论与应用研 究提供了新的研究方法. 2模糊熵测度 2.1 信息熵 设有一离散型随机变量x,其,z个可能的取值 为a ,a ,…,a ,每一结果出现的概率分别是 , P ,…,P ,X的概率空间可表示为 [x.P]:J lP以”…加” (1) : 1, 2,…, 其中 一1,o<p 1. i=l 由于Ex・P]完整地描述了由X所代表的离散 信源的特性,故称为信源x的信源空间.我们称 I(a )一一logp ,i一1,2,…, (2) 为信息函数,在事件{X===a }发生之前,表示事件的 不确定性;在事件{X—a }发生以后,表示事件所含 有的信息量,又称为。 的自信息.Shannon把信息函 数在信源空间Ix・P]中的统计平均值 H(x)一H(pl, 2,…,P )一一 logp (3) i—l 作为信源x的不确定性程度的度量,称为信息熵、 Shannon熵或概率熵_j ¨]. 2.2模糊熵 模糊熵(Fuzzy Entropy)是模糊信息处理的基 本函数,用以度量模糊集合的模糊程度,在模式识 别、图像处理、语言分析等许多领域有着广泛的应 用[1 5 1 6]. 一般来说,关于模糊集A的信息熵,即模糊熵 798 计 算 机 学 报 2012住 是下列一个映射: H: (X)一R … A[-- ̄H(A) 4 这里假定 (x)是离散论域X:=:{-z ,z。,…,Iz }上所 有模糊子集的集合,AE (X).通常H满足Deluca- Termini 4条公理,即 (1)H(A)一0∞ A(z)一0或1,Vx∈X; (2)H(A)取最大值甘 A(z)一1/2,VxE x; (3)如果A<B,则H(A)三三三H(B),其中“A<B” 表示A比B峰化,即 fO<_/2A(z)三三三 口(z)三三三1/2,o三三三 B(x) ̄l/2 l1/2 B(z)三三三 (z) 1,1/2_<_zB(z)三三三1。 (4)H(A)一H(A),其中A是A的补集. 模糊熵刻画一个模糊集的整体模糊程度,上面 4条公理是容易理解的:分明集显然是不模糊的,即 模糊熵等于零;(2)和(3)表明,从总体上讲各元素隶 属度越接近于1或0,越不模糊,越接近于0.5,越模 糊;(4)表明A与它的补集A具有相同的模糊程度. 2.3模糊熵测度 我们知道,在Shannon信息理论中,平均互信息 量 (X;y)度量了两个随机变量X与y之间的公共 信息,又称为公共信息量(Mutual Information,MI), 借用Shannon信息理论的有关提法,研究两个模糊 集之间的模糊公共信息量.下面虽然我们借用了 Shannon信息熵的提法,但从概念上是完全不同的. 定义1. 设x为离散论域,A,BE (X),记 X 一{z l z∈X,/2A(z)三三三 B(z)}, X一一{z1.22∈X,/2A(1z)< B(z)}, 则有 (1)模糊熵 H(A)一一 ∑[~zE-X (x)log2/A(1z)+ (1一 A(z))log(1--/2A(z))] (5) H(B)一一 ∑E2/ (x)log2/ (z)+ z∈X (1--/2B(z))log(1~ B(z))] (6) (2)模糊联合熵 H(AUB)一 寺∑{~ ∈X L (x)V2/ (x) ̄logE2/A(x)V2/ ( )]+ [1一 A(x)V/2B(x) ̄logE1--/2A(x)V/2B(z)]}一 ∑{ (x)log2/A(z)一[1- ̄A(X)]logEl-2/A(X)]}一 ∈x 寺∑ (x)log2/ (z) 1 (x)31ogE1-/2 (z)]) ∈ (7) (3)模糊条件熵 H(A/B)=一 1∑{/2A(z)l。g/2A(z) B(z)l。g/2B(z)+ .E1--ZA(X)]logE1-- ̄A(z)]一[1 B(x)]log[-1--/2B( )]} (8) H(B/A):一吉∑{ (z)l。即e(z)_ (z)l。即A(z)+ [1— B(x)]logE1-/2 ( )]一[1— A(1z)]log[1一,“(z)]} (9) 它们具有下列性质. 定理1. 设X为离散论域,A,B∈ (X),则 H(A/B) H(A) (10) H(B/A) H(B) (11) 证明. 首先证明式(10). H(A)一H(A/B)一 ~l ̄xE2/f(z)log2/A(z)+(1 (z))log(1— A(z))]+ ∑{ A(训。g/2A(1z)一 B(训。g/2B(z)+ .[1--2/A(X)]Iog[-1 A(x)J-E1 B(x) ̄logV1 B )]} 一一去∑ e(z)l。g2/e(z)+ (1—— B(Iz))log(1一 B(z))]一 ∑[2/A(x)1。g2/A(X)@(I ̄A(X))10g(1 ( ] 三三=O, 所以H(A/B) H(A)成立. 同理可证式(11)成立,即H(B/A) H(B). 由定理1的证明,不难看出下列结论成立. 定理2. 设X为离散论域,A,B∈ (X),则 H(A)一H(A/B)一H(B)一H(B/A) (12) 借助于Shannon信息理论中公共信息量的概 念,我们得到下列定义. 定义2. 设X为离散论域,A,B∈ (X),则称 绝对差值H(A)一H(A/B)为A与B的模糊公共 信息量(Fuzzy Mutual Information,FMI),记作 H(AnB),即 H(AnB)一H(A)一H(A/B)一 去∑[ (z)l。g2/e(z)+(1 e(z))log(1-2/。 ))]一 ∈X ∑[2/A(X)1。g2/A(X)-]-(1一/2A(X))1Og(1一 ))] z∈X (13) 类似地可定义H(BnA),即 4期 丁世飞等:基于熵的模糊信息测度研究 799 H(BnA)一H(B)一H(B/A)一 一在实际测量数据处理中,信息并非必然具有概率性 ∑[ (x)log/ ̄B( )+(1— (x))log(1- ̄ ( ))]一 3-EX+ 质,在某些非概率情况下,一样存在信息,就是说存 在着所谓的“非概率信息”. 寺∑ ̄/AA(X)1og,uA(x)@(1一/AA(521))log(1一 A(z))] ~ 根据式(18),当 一2时,令P一(p,1一 ),Q一 ∈ (14) 根据定理2及定义2,容易看出FMI满足非负 性、对称性等基本性质,所以FMI是一种广义的、绝 对的模糊性测度,称之为模糊绝对熵测度(Fuzzy Absolute Entropy Measure,FAEM),它在某种程 度上度量了两个模糊集A与B之间的相似性程度. 对模糊集A与B之间的相似性程度,除了用 FAEM度量之外,在实际应用中,我们有时会用到 相对的模糊性度量,下面我们给出一种相对的模糊 性度量. 定义3. 设X为离散论域,A,B∈ (X),则称 R(A,B)一 旦 口旦 一旦 H(A)H(A) 二旦 旦 (15) 为B对A的模糊相对公息(Fuzzy Relative Mutual Information,FRMI). 同样地 R(B,A)-- 一 (16) 称为A对B的模糊相对公息(FRMI). 由于R(A,B)≠R(B,A),即FRMI不满足对称 性,为此我们对FRMI改进如下. 定义4. 设X为离散论域,A,B∈ (X),则称 s(A,B)一R ,B)+R( )一 + (17) 为A与B的模糊相对熵测度(Fuzzy Relative Entropy Measure。FREM) FREM表示在模糊信息方面模糊集A与B之 间的模糊相似性度量,可用于聚类分析、图像处理等 方面. 3模糊交互熵测度 3.1模糊交互熵 对于x的两个概率分布向量P一(P ,Pz,…, P ),Q一(q ,q ,…,q ),P对Q的交互熵为 H(P l lQ)一∑Pilog (18) i一1 交互熵概念在Shannon信息理论中占有非常重要 的地位,用于度量两个概率分布间的差异性信息.但 (q,1一q),则 H(Pll Q)一pl。g予 卜p)l。g (19) 由于模糊集合的隶属度函数与其补集的隶属度 函数间的关系与式(19)是类似的,因而仿此可定义 一种类似的熵,称之为模糊交互熵,用以度量一个可 能性分布与另一个可能性分布之间的信息差异程度. 定义5. 设 A一( A(x1), A(x2),…, A(z )), B一( B(x1), B(x2),…, B( )) 为两个模糊向量,对于某个z ,定义 (z )对 (1z )的交互熵为 -厂[ A(z )l l(z )]一 lOg +(1--/AA(x ̄))log (20) 因此,两个模糊集A对B的模糊交互熵(Fuzzy Cross Entropy,FCE)可定义为 F(A l lB)一 骞{PA cx ̄)log c 1-/2A (xi)) (21) 式(21)有个缺点,即当 (z )-+0(或1)时,其 值趋向于无穷大,为此仿照FCE的定义,改进的模 糊交互熵(Improved FCE,IFCE)定义如下: F(A l1B)一娄 Xi)log 2 I ̄A(X i) F (1- ̄A(2Ci)log 2(1 - ,UA (Xi )) ) (22) 这样对于所有的 (z )和 (z )该公式都有定义. 3.2模糊交互熵测度 可以证明,F(A l lB)只满足非负性,而不满足 对称性,为此我们构造对称型的模糊交互熵. 定义6. 设 A一( A(x1), A(x2),…, A(z )), B一(/1B(x1), B(x2),…, B( )) 为两个模糊向量,F(A 1l B)与F(B i lA)分别为A 对B和B对A的模糊交互熵,则 D(A,B)==:F(A Il B)+F(B l lA) (23) 称为对称模糊交互熵(Symmetric Fuzzy Cross 800 计 算 机 学 报 2O12年 Entropy,SFCE). 下面给出并证明SFCE的性质. 定理3. 对称模糊交互熵(SFCE),即D(A,B) 具有下列性质: (1)非负性.D(A,B) 0; (2)规范性.D(A,B)一O㈢A—B; (3)与模糊熵的关系. D(A,A)一(一2nlog2) (A)+2nlog2, 其中 A)一 log )+ (1一 A(Lz ))log(1一 A(z z))} (24)为模糊熵. 证明. 性质(1)、(2)是显然的,下面证明性 质(3): 根据式(22)与式(23),我们有 D(A,B)一F(A l lB)+F(B} lA) 一 ̄i 11 {2/A(x;)logpA~t, f^B+ 、一l (1-2/A c log )+ 耋 = 1 。g 2A、~丽2/z, B(。XP1 )、~z + (1一 log 2 (1- 2/8 (x/))) (25) 设B—A一,则有 B(xi)一 (z )一1--/2a(z ) (26) 将式(26)代人式(25),得到 D(A, )一∑{2/A(z )1og[22/A(z )]+ i=1 (1--/2A(z )log[2(1--/2A( ))])+ ∑{(1一 A(z ))log[2(1一 A(z ))]+ i=1 A(z )logE2/2A(1z )]} 一2∑{i=1 (z )log2/A( )+ (1一 A(z )log(1一 A( ))+log2) (一l0g2 l(一 ) 唧 ] (1一 A(z ))log(1--12A(z )))J+2nlog2 .J :(一2nlog2)d(A)+2nlog2. 因此有 D(A,A)一(一2nlog2)d(A)+2nlog2. 性质(3)得证. 对于任意有限的模糊集合A,有O d(A) 1, 因此得0 D(A,A) 2n log2,所以当A—A时, D(A,A)一0达到最小值;当A是普通集合时, D(A,A)一2nlog2达到最大值,所以A与A相差越 大,D(A,A)也越大,反之亦然. D(A,B)是一种广义的距离测度,用以度量两 个模糊集A与B之间的差异程度,作为两个模糊集 之间的一种信息度量准则,我们称之为模糊交互熵 测度(Fuzzy Cross Entropy Measure,FCEM). 4结论 在现有模糊信息测度理论研究基础上,基于 Shannon信息理论,给出了模糊熵公理化理论,讨论 了模糊熵的各种定义.在此基础上,建立了模糊绝对 熵测度(FAEM)、模糊相对熵测度(FREM);在交互 熵理论研究的基础上,给出了模糊交互熵的定义,以 此为基础,建立了模糊交互熵测度(FCEM).这些理 论与方法,拓宽了模糊信息测度理论研究领域,为进 一步开展模式识别、机器学习、聚类分析等理论与应 用研究提供了理论基础. 参 考 文 献 [1]Duda R O,Hart P E.Pattern Classification and Scene Anal— ysis.New York:John Wiley and Sons,1973 [23 Bian Zhao—Qi,Zhang Xue—Gong.Pattern Recognition. Beijing:Tsinghua University Press,2000(in Chinese) (边肇祺,张学工.模式识别.北京:清华大学出版社,2000) [3]Sun Ji—Xiang.Modern Pattern Recognition.Changsha:The Defence University of Science and Technology Press,2002(in Chinese) (孙即祥.现代模式识别.长沙:国防科技大学出版社, 2002) [4]Tou J T,Gonzalez R C.Pattern Recognition Principles. London:Addison—Wesley Publishing Company,1974 [5]Zadeh L A.Fuzzy sets.Information and Control,1965, 8(4):338—353 [6]He Zhong—Xiong.Fuzzy Mathematics and Applications. Tianjin:Tianjin Press of Science and Technology,1983(in Chinese) (贺仲雄.模糊数学及其应用.天津:天津科学技术出版社, 1983) [7]Kandel A.Fuzzy Techniques in Pattern Recognition.New York:John Wiley&Sons,1982 [8]Shannon C E.A mathematical theory of communication.Bell System Technique Journal,1948,27(4):379—423;623 656 4期 丁世飞等:基于熵的模糊信息测度研究 8O1 [9] Ding Shi Fei,Shi Zhong-Zhi,Xia Shi Xiong,Jin Feng— Xiang. Studies on fuzzy information measures//Proceedings of the 4th International Conference on Fuzzy System and Knowledge Discovery.Haikou,Hainan,China,2007,3: 376—380 [10] Ding Shi Fei.Studies on information pattern measures and feature compression algorithms based on cognition[Post— doctor dissertation].Institute of Computing Technology, Chinese Academy of Sciences,Beijing,2006(in Chinese) (丁世飞.基于认知的信息模式测度与特征压缩算法研究 [博士后论文].中国科学院计算技术研究所,北京,2006) [I1] Shang Xiu—Gang.Information entropy,pattern classification and fuzzy number operation[Ph.D.dissertation].East China Polytechnic University,Shanghai,1997(in Chinese) (尚修刚.信息熵、模式分类及模糊数运算的研究[博士学位 DING Shi-Fei,born in 1963,Ph.D., professor,Ph.D.supervisor.His re— search interests include artificial intelli— gence,pattern recognition, machine learning,data mining,and granular computing etc. ZHU Hong,born in 1970,Ph.D.candidate,associate professor.Her research interests include intelligent informa— Background Pattern Recognition(PR)is the scientific discipline whose goal is the classification of obj ects into a number of categories or classes.In essence,how to measure the simi— larity between the two patterns is one of the core issues in the study of PR.Commonly,the measures include distance measure,similarity measure,and match measure et a1. These measures play an important role in pattern recognition and classification,image processing,but they are used in certainty environments.In practice,people often encounter uncertainty environment,such as random environment,fuzzy environment et al,the research of similarity measures under uncertainty environment has important theoretical signifi— cance and practical significance.In this paper,the entropy- based fuzzy information measure(FIM)is studied.Firstly, the existing FIM theories are introduced and some advantages and disadvantages are pointed OUt.Secondly,the fuzzy en一 论文].华东理工大学,上海,1997) [1 2]Cover T M,Thomas J A.Elements of Information Theory New York:John Wiley and Sons,1991 [13] Ding S F,Shi Z Z.Studies on incidence pattern recognition based on information entropy. Journal of Information Science,2005,31(6):497~502 [14] Kosko B.Fuzzy entropy and conditioning.Information Sciences,1986,40(2):l65—174 [15] De Luca A,Termini S. A definition of nonDr0ba bjhstic entropy in the setting of fuzzy sets theory.Information and Control,1972,2O(3):301 312 [16] Zadeh I A.Probability measures of fuzzy events.Journal of Mathematical Analysis and Applications,1968,23(10): 421—427 tion processing,machine learning,and granular computing etc. XU Xin‘Zheng,born in 1980,Ph.D.candidate,lecturer. His research interests include intelligent information process— ing,pattern recognition,machine learning,and granular computing etc. SHI Zhong‘Zhi,born in 1941,professor,Ph.D.super— visor.His research interests include intelligence science,im age processing and cognitive computing,machine learning, multiagent systems. tropy is studied,four axioms about fuzzy entropy are set up, and all kinds of definitions of fuzzy entropy are discussed. Based on fuzzy entropy,the new fuzzy entropy measures, such as fuzzy absolute information measure(FAIM),fuzzy relative information measure(FRIM),and fuzzy cross entro— PY measure(FCEM),are set up.A1l these measures。not only enrich and develop FIM theory,but also provide a new research approach for studies on pattern recognition,machine learning,clustering analysis et a1. This work is supported by the National Natural Science Foundation of China under Grant Nos.41074003 and 60975039,the National Basic Research Program(973 Pro— gram)of China under Grant No.2007CB31 1004,and the Opening Foundation of Key Laboratory of Intelligent Information Processing of Chinese Academy of Sciences (No.IIP2010—1).