《浅析互信息熵在某些学科中的应用》由会员分享，可在线阅读，更多相关《浅析互信息熵在某些学科中的应用（13页珍藏版）》请在金锄头文库上搜索。
1、.本科生课程论文 浅析互信息熵在某些学科中的应用 -.目 录摘要1引言1一、基于属性互信息熵的量化关联规则挖掘1（一）相关概念2（二）基于属性互信息熵的量化关联规则挖掘算法21.量化属性的离散化32.基于强信息关系属性集挖掘频繁项集43. 频繁项集产生规则的利用5（三）算法BMIQAR 的正确性分析5（四）实验结果与分析6（五）结束语6二、结合互信息熵差测度的高斯混合模型图像分割6（一）GMM - DM I算法71.GMM 模型及其参数估计72.互信息熵差83 算法描述8（二）实验结果与分析9（三）结论9总结9参考文献10浅析互信息熵在某些学科的应用信息与计算科学专业 宋海罗指导教师 吴慧【摘
2、要】在量化关联规则挖掘中存在量化属性及其取值区间的组合爆炸问题，影响算法效率。提出算法BMIQAR，通过考察量化属性间互信息熵，找到具有强信息关系的属性集。实验表明，能提高算法的性能，且能得到绝大多数置信度较高的规则。另外从分割图像与原图像的内在联系出发, 提出了一种基于高斯混合模型与互信息熵差结合的分割算法. 利用期望极值化方法确定高斯混合模型的各分量参数, 计算前分割图像与当前分割图像的互信息熵差, 互信息熵差达到最小时即为最优解. 实验表明, 本算法所得到的目标图像的区域保持形状且定位性能好.【关键词】量化关联规则 互信息熵 图像分割 高斯混合模型 互信息熵差Analysis of mu
3、tual information entropy in the application and comparison of some subjectStudent majoring in Information and Computing Science: Hailuo SongTutor Hui WuAbstract:On the research of quantitative association rules mining in database which contains quantitative attributes, the combination of the quantit
4、ative attributes and the intervals associated leads to an unmanageably highly sized itemsets and association rule sets which constitute a hamper toward the efficiency of the mining algorithm. The mutual information entropy of the attributes is studied here, and algorithm BMIQAR which can find the fr
5、equent itemsets and association rules from the attributes sets with strong information relationship is designed. The experiments show that due to the prune on the attributes, the research space decreases sharply, so the mining efficiency is improved greatly, and the acquired association rules are hi
6、gh confidence ones. According to the internal relations between original image and segmented image, the gauss miture model is combined with the difference of mutual information ( DM I).The parameters of GMM can be obtained by using Expectation Maximization method, and initeration process, an optima
7、l component number will be determined by minimizing the DM I between the previous and current segmented images. The experimental results indicate that the proposed method has not only visually better segmentation effect but also better localization property.Key words:quantitative association rules;
8、mutual information entropy；image segmentation; GMM; DM I 引言 数据挖掘中关联规则的研究是应用驱动的，最常见的是对大型超市的事务数据库进行购物数据分析。量化关联在股市分析、银行存款分析等众多方面都有重要应用价值，因此在国际上引起了重视。量化关联规则挖掘问题就是对于给定的数据库，找到满足预先设定的最小支持度与置信度阈值的规则的过程。图像分割是一个根据区域间的相似或不同把图像分割成若干区域的过程. 在众多的图像分割方法中, 基于特征空间聚类的混合模型方法常常能获得较稳定的分割结果. 一、概述基于属性互信息熵的量化关联规则挖掘数据挖掘中关联规则
9、的研究是应用驱动的，最常见的是对大型超市的事务数据库进行购物数据分析。文献1针对布尔属性的关联规则提取提出了很多的高效算法。而量化关联规则挖掘2的数据库中不再是布尔属性，而是取值范围较广的数值属性与类别属性。量化关联在股市分析、银行存款分析等众多方面都有重要应用价值，因此在国际上引起了重视。一个典型的量化关联规则如下：age20,35,sexfemalesalary1 800,3000(sup=5%,conf= 85%)，其中，sup, conf分别为规则的支持度和置信度。量化关联规则挖掘问题就是对于给定的数据库，找到满足预先设定的最小支持度与置信度阈值的规则的过程。量化关联规则挖掘的一般做法
10、是将其转化为布尔型的关联规则挖掘问题。即对属性定义域进行划分，将形成的(属性，区间)或(属性，取值)对作为新的属性，再将这些新的属性映射为布尔属性进行处理。文献2提出了基于支持度的部分k完全的算法SA。文献3提出了将定义域划分交叉区间的实现方法。其他的文献也提出了相应的属性定义域划分方法及量化关联规则的挖掘算法4-7。然而，量化关联规则的挖掘过程需要面对来自2 个方面的组合爆炸问题，首先在属性层，若有N 个属性，那么属性集的非空子集为2N-1。再者，若每个量化属性的定义域被划分为n 个区间，那么在对连续的区间合并后区间数将趋于O(n2)。在实际挖掘过程中，由于属性数和与之对应的区间数较多，在对
11、来自不同属性的区间进行连接后，项集数急剧增加，大大降低了算法的挖掘效率。本文利用信息论的相关理论，通过考察属性间的互信息熵，先在属性层进行剪枝，找到相互之间具有强信息关系的属性集，只对这些属性集的区间进行连接，此时再利用Apriori 性质对得到的项集进行剪枝以得到满足条件的频繁项集。（一）相关概念熵：是信息论8的中心概念，简单地说是变量的不确定性的度量。互信息熵：描述了某个变量取值对另一个变量取值的确定的能力。其值越大2 个变量间的确定能力越强。对于一个给定的量化关联规则挖掘问题， p(vx)=sup(xvx,vx),p(vx,vy)=sup(xvx,vxyvy,vy),p(vy|vx)=c
12、onf(xvx,vx=yvy,vy)，且有H(x)0, H(y|x)0。由于I(x;y)min(H(x),H(y)，互信息熵上限为熵，但不同属性的熵值变化较大。另外，互信息熵为非负值，越大表明一个属性对另一属性取值的确定的信息越强。但是对于给定的问题，没有统一的衡量标准，较难设定一个阈值来真正反映这样一个信息量，以说明到底2 个属性的关系有多强。于是，重新定义互信息熵为I(x;y)=I(x;y)/I(x;x)(I(y;x)=I(x;y)/I(y;y)这表明新定义后的互信息熵为已知变量y(x)的取值信息的条件下对变量x(y) 的不确定性降低的百分比。将I(x;y)(I(y;x)作为评价2 个属性
13、关系强弱的度量，若2 个属性的I(x;y) (I(y;x)值大于某个设定的阈值 ，称它们具有强信息关系。（二）基于属性互信息熵的量化关联规则挖掘算法对于给定的数据库D，基于属性互信息熵的量化关联规则挖掘算法(BMIQAR)按下述步骤进行量化关联规则挖掘。1.量化属性的离散化首先，采用等深划分的方法将数值属性的定义域划分成基本区间，并用一组连续整数来标记这些区间。为了获得足够的支持度，连续的基本区间可以进行合并，但为了避免合并区间过于泛化而缺乏意义，需设定最大支持度阈值msmax。对于类别属性，对其中的每个取值同样以一组连续整数来标记。这里的处理方法与算法SA 相同，也便于笔者在后面的实验中与之
14、比较。2.基于强信息关系属性集挖掘频繁项集对于上一步得到的离散化后的数据库D，计算所有属性两两间的互信息熵，并基于此构建一个互信息熵图：GMI=(VMI,EMI)。其中，顶点集VMII，有向边集EMI=(xi,xj)|I(xi; xj) ,xi,xjI。因此，GMI 图表达了属性间的强信息关系。因为项集中的属性间没有方向，忽略GMI 图中边的方向，考虑得到的无向图GMI，可以证明形成规则的属性在GMI中形成环。而GMI图中的边所连接的属性间具有强信息关系，能通过找到所有的环来得到能形成频繁项集的属性。利用一种前缀树结构来找到所有的环，并从中得到频繁项集。首先，在第0 层创建一个根节点。在第1
15、层为每个属性创建一个节点作为根节点的子节点，并以相应的属性名标记，且该节点附有支持度不小于最小支持度阈值ms 的区间集及支持度不大于msmax 的合并区间。对每个在第1 层的节点n，执行算法FrequentItemsetMine()，其具体描述如下：Algorithm FrequentItemsetMine(n) if(|RightBrother(n)|0)for each node vRightBrother(n) doif(n,v)GMI)Add a new node w, as ns child, label as v;Join the sets of frequent itemsets associated with n and v;for each itemset X obtained doif(sup(X)ms)Attach X to the node w;Output the set of frequent itemsets associated with n;if(|Child(n)|0)for each node wChild(n)
