浅谈互信息熵在最优化方法中的应用.docx

浅谈互信息熵在最优化方法中的应用.docx

《浅谈互信息熵在最优化方法中的应用.docx》由会员分享，可在线阅读，更多相关《浅谈互信息熵在最优化方法中的应用.docx（12页珍藏版）》请在冰点文库上搜索。

浅谈互信息熵在最优化方法中的应用

青岛农业大学

本科生课程论文

论文题目浅谈互信息熵在最优化方法中的应用

学生专业班级信息与计算科学专业2009级2班

学生姓名（学号）（20094819）

指导教师吴慧

完成时间2012年6月28日

课程论文任务书

学生姓名指导教师吴慧

论文题目浅谈互信息熵在最优化方法中的应用

论文内容（需明确列出研究的问题）：

在量化关联规则挖掘中存在量化属性及其取值区间的组合爆炸问题，影响算法效率，提出算法BMIQAR，通过考察量化属性间互信息熵，找到具有强信息关系的属性集，从中得到频繁项集以产生规则。

简单介绍了最优化方法，并从分割图像与原图像的内在联系出发,提出了一种基于高斯混合模型与互信息熵差结合的分割算法，利用期望极值化方法确定高斯混合模型的各分量参数,以互信息熵差为模型选择准则,计算前分割图像与当前分割图像的互信息熵差,互信息熵差达到最小时即为最优解。

资料、数据、技术水平等方面的要求：

论文要符合一般学术论文的写作规范，具备学术性、科学性和一定的创造性。

文字要流畅、语言要准确、论点要清楚、论据要准确、论证要完整、严密，有独立的观点和见解。

内容要理论联系实际，计算数据要求准确，涉及到他人的观点、统计数据或计算公式等要标明出处，结论要写的概括简短。

参考文献的书写按论文中引用的先后顺序连续编码。

发出任务书日期2011.06.17完成论文（设计）日期2011.06.29

学科组或教研室意见（签字）

院、系（系）主任意见（签字）

浅谈互信息熵在最优化方法中的应用

信息与计算科学专业

指导教师吴慧

【摘要】在量化关联规则挖掘中存在量化属性及其取值区间的组合爆炸问题，会影响算法效率，提出算法BMIQAR，通过考察量化属性间互信息熵，找到具有强信息关系的属性集，实验表明能提高算法的性能，且能得到绝大多数置信度较高的规则。

最优化方法主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据，在科技迅猛发展的今天，它和计算机、经济管理、工程建设等的有机结合，俨然已经使其成为一门应用非常广泛而且非常经济实用的的一门学科。

本文从分割图像与原图像的内在联系出发,提出了一种基于高斯混合模型与互信息熵结合的分割算法，利用期望极值化方法确定高斯混合模型的各分量参数,计算前分割图像与当前分割图像的互信息熵,互信息熵达到最小时即为最优解。

【关键词】量化关联规则；互信息熵；图像分割；高斯混合模型；最优化方法

Themutualinformationentropyusinginoptimizationmethod

StudentmajoringinInformationandComputingScienceWangJia

TutorWuHui

【Abstract】TherearecombinatorialexplosionproblemsbetweenMiningQuantitativeAssociationRulesinquantitativeattributesandtheirvalues​​,whichaffectingtheefficiencyofthealgorithm.CreatingthealgorithmBMIQARbyexaminingthemutualinformationamongthequantizationproperties,findingthatthesetofattributeswithstrongrelationship.Meanwhile,experimentsshowthatitcanimprovetheperformanceofthealgorithm,andalsocangettherulesofthevastmajorityofthedegreeofconfidencehigher.Optimizationmethodsusemathematicalmethodstoachieveoptimizeandmakingprogramsforpolicy-makersinscientificbasis.Withtherapiddevelopofthescience,whichisusedinthecomputer,economics,engineering,construction,seemingthatitisaverypracticalandeconomicalsubject.Inaddition,proposingasegmentationalgorithmbasedonGaussianmixturemodelandmutualinformationentropydifferencecombinationintheintrinsiclinkstartingfromthesegmentedimagewiththeoriginalpictures.UsingtheexpectedextremevaluemethodtodeterminethevariouscomponentsoftheGaussianmixturemodelparameters,thecalculationofimagesegmentationsegmentedimagewiththecurrentdifferenceofmutualinformation.Whenthedifferenceofmutualinformationreachestheleast,whichistheoptimalsolution.

【Keywords】quantitativeassociationrulesofmutualinformationMutualinformationentropyimagesegmentationGaussianmixturemodelOptimizationmethods

前言

最优化方法从数学意义上说就是为了达到最优化目的所提出的求解方法，其实质是一种求极值的方法。

从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。

数据挖掘中关联规则的研究是应用驱动的，量化关联规则挖掘问题就是对于给定的数据库，找到满足预先设定的最小支持度与置信度阈值的规则的过程。

图像分割是一个根据区域间的相似或不同把图像分割成若干区域的过程,在众多的图像分割方法中,基于特征空间聚类的混合模型方法常常能获得较稳定的分割结果。

本文将利用最优化方法中的算法原理，并结合计算机中的编程算法,直到最后得到的互信息熵达到最小时即达到了最优的图像分割。

1.基于属性互信息熵的量化关联规则挖掘

1.1概述

最优化方法中的最优化一般可以分为最优设计、最优计划、最优管理和最优控制四方面。

本文主要应用了最优设计，利用计算机编程设计算法使得互信息熵最小时达到最优。

数据挖掘中关联规则的研究是应用驱动的,针对布尔属性的关联规则提取提出了很多的高效算法,而量化关联规则挖掘的数据库中不再是布尔属性，而是取值范围较广的数值属性与类别属性[1]，在实际挖掘过程中，由于属性数和与之对应的区间数较多，在对来自不同属性的区间进行连接后，项集数急剧增加，大大降低了算法的挖掘效率[2]。

本文利用信息论的相关理论，通过考察属性间的互信息熵，先在属性层进行剪枝，找到相互之间具有强信息关系的属性集，再利用最优化方法设计算法对得到的项集进行剪枝以得到满足条件的频繁项集[3]。

1.2相关概念

互信息熵：

描述了某个变量取值对另一个变量取值的确定的能力，其值越大2个变量间的确定能力越强。

最优化方法：

也称做运筹学方法，它主要运用数学的思维和方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。

1.3基于属性互信息熵的量化关联规则挖掘算法

对于一个给定的量化关联规则挖掘问题p（

）=sup（x[

]）,p（

）=sup（x[

]y[

]）,p（

|

）=conf（x[

]=>y[

]）且有H（x）≥0,H（y|x）≥0。

由于I（x；y）≤min（H（x）,H（y）），不同属性的熵值变化较大。

另外，互信息熵为非负值，越大表明一个属性对另一属性取值的确定的信息越强。

但是对于给定的问题，没有统一的衡量标准，较难设定一个阈值来真正反映这样一个信息量，以说明到底2个属性的关系有多强。

于是，重新定义互信息熵为

（x；y）=I（x；y）/I（x；x）（I（y；x）=I（x；y）/I（y；y））,这表明新定义后的互信息熵为已知变量y（x）的取值信息的条件下对变量x（y）的不确定性降低的百分比。

将

（x；y）作为评价2个属性关系强弱的度量，若2个属性的

（x；y）值大于某个设定的阈值μ，称它们具有强信息关系。

对于给定的数据库D，基于属性互信息熵的量化关联规则挖掘算法（BMIQAR）按下述步骤进行量化关联规则挖掘。

1.3.1量化属性的离散化

采用等深划分的方法将数值属性的定义域划分成基本区间，并用一组连续整数来标记这些区间，为了获得足够的支持度，连续的基本区间可以进行合并，但为了避免合并区间过于泛化而缺乏意义，需设定最大支持度阈值msmax[4]。

1.3.2基于强信息关系属性集挖掘频繁项集

对于上一步得到的离散化后的数据库

，计算所有属性两两间的互信息熵，并基于此构建一个互信息熵图：

GMI=（VMI,EMI）。

其中，顶点集VMI∈I，有向边集EMI={（

）|

（

；

）≥μ,

∈I}，GMI图表达了属性间的强信息关系。

因为项集中的属性间没有方向，忽略GMI图中边的方向，考虑得到的无向图

，可以证明形成规则的属性在

中形成环。

而

图中的边所连接的属性间具有强信息关系，能通过找到所有的环来得到能形成频繁项集的属性。

利用一种前缀树结构来找到所有的环，并从中得到频繁项集[5]，执行算法FrequentItemsetMine（），其具体描述如下：

AlgorithmFrequentItemsetMine（n）

{if（|RightBrother（n）|>0）

foreachnodev∈RightBrother（n）do

if（（n,v）∈GMI’）

Addanewnodew,asn’schild,labelasv;

Jointhesetsoffrequentitemsetsassociatedwithnandv;

foreachitemsetXobtaineddo

if（sup（X）≥ms）

AttachXtothenodew;

Outputthesetoffrequentitemsetsassociatedwithn;

if（|Child（n）|>0）

foreachnodew∈Child（n）do

ChildMine（w）;

Else

Outputthesetoffrequentitemsetsassociatedwithn;}[6]

1.4实验结果与分析

为验证本文算法的有效性，利用C++语言实现了本文算法。

采用UCI机器学习数据集为数据源进行实验测试，2个测试数据库文件D1和D2包含的记录数、数量属性数、类别属性数分别为20000,16,1和181012,10,45。

对数据集D1，设定最小支持度阈值ms为0.1~0.3，对应的msmax比ms值大0.3，最小互信息熵阈值μ分别取0.1和0.2。

实践证明对于2个μ值，算法BMIQAR时间复杂度有较大降低，分析由于D1中的量化属性的取值范围较小，不同的ms值对于划分区间的个数影响小，该算法运行时间的影响主要来自msmax[7]。

从实验结果来看，算法BMIQAR通过具有强信息关系的属性集来挖掘频繁项集，有效地减少了已有算法在挖掘过程中产生的庞大的项集数，显著地提高了算法的性能，并且能得到绝大部分置信度较高的规则。

2.结合互信息熵测度的高斯混合模型图像分割

图像分割是一个根据区域间的相似或不同把图像分割成若干区域的过程，在众多的图像分割方法中,基于特征空间聚类的混合模型方法常常能获得较稳定的分割结果。

期望最大化（EM）算法[8]为模型参数提供了一种简单有效的极大似然估计解，传统的高斯混合模型只考虑到图像像素的个体信息,而忽略了像素的空间分布以及分割图像与原图像的内在联系，当有突发噪声和边界灰度相溶时,得到的区域不能代表原图像区域的形状。

本文根据图像配准领域的研究成果,从分割图像与原图像的内在联系出发,提出了基于高斯混合模型与互信息熵相结合的方法，利用最大极值化方法确定高斯混合模型的各分量参数,以互信息熵为模型选择准则,当互信息熵达到最小时即为最优分割法。

2.1GMM-DMI算法

2.1.1GMM—DMI模型及其参数估计

设图像的像素集为

其中

为像素个数,每个像素是维数为

（即

=[

…

]T）。

X服从有限高斯混合分布,采用EM算法来对混合参数进行估计。

EM算法由E步骤和M步骤的迭代组成,设第t次迭代后获得的参数估计值,则在第t+1次迭代时,E步骤计算完全数据对数似然函数的期望；M步骤求取模型参数的极大似然估计值,并实现对参数的更新。

但是,该方法依然存在一些不足,由于传统的高斯混合模型在参数估计过程中仅考虑了像素的个体信息,未利用图像的空间信息，若待分割区域之间灰度差异不明显,或者有一定噪声时,则可能出现过分割或误分割,丢失图像中部分区域的信息。

当估计到混合模型参数后,可以用信息理论准则去确定要分割的区域数目,这些准则把系统似然函数的极大值与参数数目结合起来去确定模型选择，但是这些准则都受到前面提到的模型存在的缺陷的影响,常常会导致分割区域数目的不确定性。

2.1.2算法描述

给定原图像I和分割图像S,它们的熵和联合熵定义为:

，

。

其中:

FI（I）、FS（S）、FI,S（I,S）分别为I和S的概率分布和联合概率分布。

互信息量MI定义为MI（I,S）=H（I）+H（S）-H（I,S）互信息熵DMI定义如下:

DMIK（I）=MI（I,SK）-MI（I,SK-1）其中I为原图像,SK和SK-1均为图像的分割图像,且混合模型的分量个数分别为K和K-1。

为了便于对不同的图像进行比较,将DMI进行归一化处理,有KDMIK（I）=MI（I,SK）-MI（I,SK-1）MI（I,I），在对基于高斯混合模型的算法的研究中发现,原图像I及其分割图像S之间的互信息量,随着图像S中分量个数的增加而增加,并收敛于其最大值MI（I,I）；随着分割图像S分量个数的增加,归一化互信息熵KDMI随之递减或振荡下降,并收敛于0。

在这里将分割视为图像的一种退化，当分割后的图像与原图像的空间位置一致,求出的区域与原图像的形状相吻合时互信息熵达到最小值,即认为所获得的最优分割结果包含有原图像的信息量最多。

GMM-DMI算法：

首先利用期望极值化方法确定高斯混合模型的各分量参数,以互信息熵为模型选择准则,并将其准则定义为:

其主要步骤描述如下:

1）给定原图像；令初始分量个数K=2,MI（I,S1）=0；

2）建立高斯混合模型；

3）初始化参数；

4）用EM算法得到参数估计；

5）根据模型分割I为SK；

6）计算准则

如果

小于无穷大，则转步骤7；否则K=K+1,转步骤2；

7）K-1即为所求分量个数,SK-1即为分割结果。

2.2实验结果与分析

应用GMM-DMI算法对医学图像进行了分割实验,图像大小为355×383,如图1所示,分析如下：

图1脑图像分割结果

其中图1a为原图像，从图1b中到图1,f原图像I及其分割图像S之间的互信息量值MI,随着S中模型的分量个数K的增加而递增；而KDMI递减,并在K=7时收敛于最小值。

从图1f和图1g可以发现：

FCM算法的处理结果中丢失原图像的目标信息比较严重,过分割现象也较突出,GMM-DMI算法较好的分割出灰质、白质、脑髓液等组织的同时,对病灶也获得了较为正确的分割。

2.3结论

从实验结果来看，BMIQAR算法通过具有强信息关系的属性集来挖掘频繁项集，能得到绝大部分置信度较高的规则。

文章给出了一个基于高斯混合模型与互信息熵差结合的分割方法GMM–DMI算法，能充分考虑了图像中像素的个体信息和空间信息,以及分割后图像与原图像的内在联系,使得分割后的图像具有目标区域形状完好、位置信息准确等优点,分割图像质量得到改善。

由此可以看出，最优化的思想在医学及各种高科技领域的应用是非常广泛的。

参考文献

[1]张朝晖,陆玉昌,张钹.发掘多值属性的关联规则[J].软件学报,1998,9（11）:

801-805.

[2]范森淼,程晓青.数量关联规则发现中的聚类方法研究[J].计算机学报,2000,23（8）:

866-871.

[3]AgrawalR,SrikantR.FastAlgorithmsforMiningAssociationRules[C]//Proc.ofthe20thInternationalConferenceonVeryLargeDataBases.Santiago,Chile:

[s.n.],1994:

487-499.

[4]AgrawalR,SrikantR.MiningQuantitativeAssociationRulesinLargeRelationalTables[C]//Proc.ofthe15thACMSIGMODSymposiumonPrinciplesofDatabaseSystems.Montreal,Canada:

[s.n.],1996:

1-12.

[5]FukudaT,MorimotoY.MiningOptimizedAssociationRulesforNumericAttributes[C]//Proc.ofthe15thACMSIGMODSymposiumonPrinciplesofDatabaseSystems.Montreal,Canada:

[s.n.],1996:

182-191.

[6]RigauJ,FeixasM,SbertMetalMedicalImageSegmentationBasedonMutualInformationMaximization[C]//LectureNotesinComputerScience,2004:

135-142.

[7]ChienBeen-chian,LinZin-long,HongTzung-pei.AnEfficientClusteringAlgorithmforMiningFuzzyQuantitativeAssociationRules[C]//Proc.ofIFSAWorldCongressandNAFIPSInternationalConference.Vancouver,Canada:

[s.n.],2001:

1306-1310.

[8]CoverTM,ThomasJA.ElementsofInformationTheory[M].[S.l.]:

JohnWiley&Sons,Inc.,1991.

课程论文成绩评定表

学生姓名

王甲

专业班级

信息与计算科学2009级2班

论文题目

浅谈互信息熵在最优化方法中的应用

指导教师评语及意见：

指导教师评阅成绩：

指导教师签字

年月日

评阅人评语及意见：

评阅人评阅成绩：

评阅人签字

年月日

总评成绩（以百分记）：

年月日