信息熵的计算及实现

认知实习报告认知实习报告 题 目 信息熵的计算及实现 院 系 数理系 专业 信息与计算科学 班级 学号 20081001 学生姓名 导师姓名 完成日期 2011 年 12 月 23 日 信息熵的计算及实现 信息与计算科学专业 指 导 教 师 摘要 信息的销毁是一个不可逆过程 一般而言 当一种信息出现概 率更高的时候 表明它被传播得更广泛 或者说 被引用的程度更高 我们可以认为 从信息传播的角度来看 信息熵可以表示信息的价值 这样我们就有一个衡量信息价值高低的标准 可以做出关于知识流通 问题的更多推论 本文讨论了一维几种熵的计算方法 离散信源的熵 图像熵的一维熵和二维熵 基于信息熵的 Web 页面主题信息计算方法 并给出一定的理论分析和数值实验以及数值实验结果 关键字 离散信源的熵 图像熵 Web 页面主题信息 1 引言引言 信息论之父 C E Shannon 在 1948 年发表的论文 通信的数学理论 A Mathematical Theory of Communication 中 Shannon 指出 任何信息 都存在冗余 冗余大小与信息中每个符号 数字 字母或单词 的出现概率或 者说不确定性有关 Shannon 借鉴了热力学的概念 把信息中排除了冗余后的 平均信息量称为 信息熵 并给出了计算信息熵的数学表达式 2 2 问题提出问题提出 信源的平均不定度 在信息论中信源输出是随机量 因而其不定度可以用 概率分布来度量 记 H X H P1 P2 Pn P xi logP xi 这里 P xi i 1 2 n 为信源取第 i 个符号的概率 P xi 1 H X 称为信源的信息 熵 2 12 1 离散信源的熵 利用信息论中信息熵概念 求出任意一个离散信源的熵 平均自信息量 自信息是一个随机变量 它是指某一信源发出某一消息所含有的信息量 所发出 的消息不同 它们所含有的信息量也就不同 任何一个消息的自信息量都代表 不了信源所包含的平均自信息量 不能作为整个信源的信息测度 因此定义自 信息量的数学期望为信源的平均自信息量 n i aipaip aip ExH 1 log 1 log 信源的信息熵 H 是从整个信源的统计特性来考虑的 它是从平均意义上来 表征信源的总体特性的 对于某特定的信源 其信息熵只有一个 不同的信源 因统计特性不同 其熵也不同 2 22 2 图像熵 通过理解图像熵基本概念 能够求出图像一维熵和二维熵 图像熵是一种 特征的统计形式 它反映了图像中平均信息量的多少 图像的一维熵表示图像 中灰度分布的聚集特征所包含的信息量 令 Pi 表示图像中灰度值为 i 的像素 所占的比例 则定义灰度图像的一元灰度熵为 255 0 log i pipiH 图像的一维熵可以表示图像灰度分布的聚集特征 却不能反映图像灰度分布的 空间 特征 为了表征这种空间特征 可以在一维熵的基础上引入能够反映灰度 分布空间特征的特征量来组成图像的二维熵 选择图像的邻域灰度均值作为灰 度分布的空间特征量 与图像的像素灰度组成特征二元组 记为 i j 其 中 i 表示像素的灰度值 0 i 255 j 表示邻域灰度 0 j 00001 error Probablities don t sum to 1 end Remove any zero probabilities zeroProbs find array eps if isempty zeroProbs array zeroProbs disp Removed zero or negative probabilities End Compute the entropy H sum array log2 array 单位 bit symbol 附 2 图像熵计算源代码 函数源程序 ImgEntropy m Image Entropy calculation jma 22 08 2007 img input image data H1 H2 Output 1 img rgb2gray I imview I imview img ix iy size img compute probs for each scale level in image P1 imhist img ix iy temp double img for the index of image piexl temp temp temp 1 correlation prob matrix between 0 255 gray levels CoefficientMat zeros 256 256 for x 1 ix for y 1 iy i temp x y j temp x y 1 CoefficientMat i 1 j 1 CoefficientMat i 1 j 1 1 end end compute the prob of matrix P2 CoefficientMat ix iy H1 0 H2 0 for i 1 256 calculate 1 ord image entropy if P1 i 0 H1 H1 P1 i log2 P1 i end compute 2 ord image entropy for j 1 256 if P2 i j 0 H2 H2 P2 i j log2 P2 i j end end end H2 H2 2 mean entropy symbol sprintf 1 ord image entropy is d H1 sprintf 2 ord image entropy is d H2 函数调用实例 test m Information Theory experiment testing file jma 22 08 2007 testing Discrete Shannon Entropy discrete probabilities set probSet 0 1 0 2 0 3 0 15 0 25 call CalEntropy function H CalEntropy probSet sprintf Shannon Entropy is d H calculate the Image entropy H1 H2 ImgEntropy lena jpg 附录二 图片 附录三 信息熵的 Web 页面主题信息计算方法 为了检验文中提出抽取方法的有效性 对新浪网站的Web页面 http tech sina tom cn s s 2005 01 3I 0922518912 shtml进行抽取实 验 用简化的STU DOM树来说明实验过程 通过HTML解析器 过滤器和关键词抽取器的工 作 得到以下STU DOM树 省略了部分内容且以文字表述 关键词后数字表示该词在此结点 出现次数 R 微软 3 SQL 2005 2 安全 6 功能 3 数据库 2 工具 1 代码 3 实 验室 1 漏洞 1 内存 1 欧洲 1 顾问 1 平台 1 开发者 1 步骤 1 加密 协议 1 领域 1 医疗系统 l 用户 1 使用权限 1 电话 1 号码 1 彩信 l 铃声 1 漫画 1 C 38 N1 f微软 1 SQL 2005 2 数据库 1 安全 1 功能 1 N2 f微软 1 工具 1 代码 3 实验室 1 漏洞 1 内存 1 N3 f微软 1 欧洲 l 安全 4 顾问 1 平台 1 开发者 1 步骤 1 N4 安全 1 功能 2 加密协议 l 领域 1 数据库 1 医疗 系统 1 用户 1 使用权限 1 N5 电话 1 号码 1 N6 彩信 1 铃声 1 漫画 1 计算各结点平均信息熵为 R 1 97 N1 1 05 N2 208 N3 1 98 N4 240 N5 3 64 N6 3 64 结点N1 N4是需要保留的包含主题信息的结点 N5 N6是需要剪枝的结点 如果选取 K I 5 则根据剪枝规则 会将N5和N6两个与主题不相关结点剪枝掉 从而实现了从Web页 面中抽取主题信息的目的 由于HTML页面本身的多样性 将本方法应用在