（计算机软件与理论专业论文）基于密度相连的ib算法.pdf

郑州大学硕j ：学位论文 摘要 i b 理论起源于著名的香农率失真理论，它通过定义变量x 的相关 变量y 推导出一个合理的失真度量函数，从而有效地解决了率失真理 论存在的失真函数难以确定的问题，避免了失真度量函数的任意选择， 此外，该方法还具有许多率失真方法不具备的特殊性质。基于i b 理论 的a i b 算法，按照分析的数据对象与另一数据对象间的相关性进行合并， 进而使得最终的合并结果一个层次树状结构充分体现出源数 据对象内部的隐含结构。 a i b 算法在数据降维过程中仅考虑两个数据对象之间的相关信息， 忽略数据对象邻域内包含的与其它数据对象之间的相关信息。针对该问 题，本文引入密度相连链的概念，同时考虑两个数据对象之间的相关信 息以及它们邻域内包含的其它数据对象之间的相关信息，构建了一种基 于密度相连的i b 算法d a i b ，且使该算法中的参数取值具有一定普 遍适用性。d a i b 算法采用层次聚类结构，输出一个自下而上的剪枝树， 并且执行一次可得到多个不同的聚类结果。在i b 算法研究的公共数据 集上的实验结果表明，d a i b 算法得到的聚类结果比a i b 算法的结果具 有更高的精确度和更好的稳定性。 关键词i b 理论；a i b 算法；密度相连 郑州大学硕上学位论文 a b s t r a c t t h ei n f o r m a t i o nb o t t l e n e c k p r i n c i p l eo r i g i n a t e s f r o mt h er a t e d i s t o r t i o nt h e o r y b yd e f i n i n gar e l e v a n tv a r i a b l eya b o u t 五t h ei bm e t h o d d e r i v e sa na p p r o p r i a t ed i s t o r t i o nf u n c t i o n ，w h i c hc o p e sw i t ht h ed i f f i c u l t yo f c h o o s i n gt h ed i s t o r t i o nf u n c t i o ni nr a t ed i m o r t i o nt h e o r y , a n di th a ss o m e p r o p e r t i e sw h i c ha r en o ts h a r e dw i t ht h er a t ed i s t o r t i o nt h e o r yb a s e do na n y o t h e rd i s t o r t i o nm e a s u r e t h ea g g l o m e r a t i v ei n f o r m a t i o nb o t t l e n e c k ( a i b ) a l g o r i t h mm e r g e st h ee l e m e n t sa c c o r d i n gt o t h er e l e v a n ti n f o r m a t i o n b e t w e e nt h e m ，a n do u t p u t sah i e r a r c h i c a lc l u s t e r i n gt r e e - s t r u c t u r e ，w h i c h r e v e a l st h eh i d es t r u c t u r ei nt h eo r i g i n a ld a t as e t t h ea i ba l g o r i t h m o n t yc o n s i d e r st h ei n f o r m a t i o nb e t w e e n t w o e l e m e n t s ，a n di g n o r e st h e i n f o r m a t i o n a m o n gt h en e i g h b o r h o o d b y i n t r o d u c i n gt h ed e n s i t y - b a s e dc h a i n , t h ep r o p o s e da l g o r i t h mc a ne v a l u a t et h e i n f o r m a t i o nl o s sa m o n gt h e n e i g h b o r so fa l ld e m e n t ，r a t h e rt h a n t h e i n f o r m a t i o nl o s sb e t w e e np a i r so fe l e m e n t s b a s e do nt h i si d e a , w ep r o p o s e t h ed e n s i t y - b a s e da g g l o m e r a t i v ei n f o r m a t i o nb o t t l e n e c ka l g o r i t h m ，a n dh a v e d i s c u s s e dt h ev a l u eo ft h ep a r a m e t e ri nd a i b t h ep r o p o s e dd a l ba l g o r i t h m a p p l i e s ah i e r a r c h i c a l c l u s t e r i n gf r a m e w o r k , a n do u t p u t s ap r u n e d h i e r a r c h i c a lc l u s t e r i n gt r e e - s t r u c t u r e ，w h i c hc a ng e tas e r i a lo fs o l u t i o n si na r u n t h ee x p e r i m e n tr e s u l t so nt h eb e n c h m a r kd a t as e t ss h o wt h a tt h ed a l b a l g o r i t h mc a ng e tm o r er e l e v a n ti n f o r m a t i o n , h i g h e rp r e c i s i o na n dm o r e s t a b l er e s u l t st h a nt h ea l ba l g o r i t h m k e y w o r d si b t h e o r y , a l ba l g o r i t h m ，d e n s i t yc o n n e c t i v i t y , h i e r a r c h i c a l t r e e - s t r u c t u r e ，c l u s t e r i n g i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体己经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：侈乎孑rj 日期：7 年 月刁日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者：佟j c 利 日期：川年夕月日期：沙，7 年罗月 叩日 郑州人学硕_ j ：学位论文 第一章绪论 i b 理论通过定义变量x 的相关变量y 推导出一个合理的失真度量函数，从 而有效地解决了率失真理论中存在的失真函数难以确定的问题，且具有许多率失 真理论不具备的特殊性质。本章第一节主要介绍了本文工作的研究背景和现状， 第二节是对基于i b 理论的a l b 算法的分析及对本文工作的描述，第三节给出了 本文的整体组织和结构。 1 1 研究背景与现状 随着数据规模不断增长，出现了一系列的数据分析方法。其中的一类重要方 法是无指导的数据降维方法，其目的是发现复杂数据集内部的隐含结构。1 9 9 9 年， t i s h b y 、p e r e i r a 和b i a l e k 提出了一种源于率失真的数据分析方法一i b 方法( t h e i n f o r m a t i o nb o t t l e n e c km e t h o d ) 1 1 。该方法首先定义一个关于源变量x 的相关变量 l 然后推导出一个合理的失真度量函数，从而在将数据对象压缩到一个事先定 义好的“瓶颈 变量的过程中极大的保存与另一数据对象的相关性，该过程平衡 了对源信息的压缩和对相关信息的保存，有效地发现了数据内部的隐含结构。 2 0 0 2 年，s l o n i m 在其博士论文中阐述了i b 方法的起源，把已有的i b 算法和应用 进行了系统的归纳和总结，提出了i b 理论【2 】。2 0 0 7 年，h a r r e m o e s 和t i s h b y 在文 献 3 】中提出i b 方法具有许多率失真方法不具备的特殊性质，从而证明了m 方法 的有效性和独特性。 目前基于i b 理论的经典算法有：i l b ，d l b 2 1 ，a l b 4 1 ，s l b 5 1 。i i b 算法由t i s h b y 等人与1 9 9 9 年提出。该算法具有类似求解率失真函数的b l a h u t a r i m o t o 算法的迭 代过程，通过烈f 盼，烈力和p ( y l t ) z 个概率分布间的迭代计算，最终得到i b 函数的 形式化最优解。d l b 算法是一种确定的类似模拟退火的i b 算法。该算法试图通过 增加p 值来重构最优的相关压缩曲线。当= o 时，压缩代表中仅含有一个元素， 即i 刁= l 。在逐步增加夕值的情况下，需要对丁不断进行分裂以达到所需要的最小 互信息足乃】，) 该算法的思想可以概括为试图确定这些分裂点，最后得到一系列不 同夕值的结果。a l b 算法是一个自底向上的凝聚层次算法。该算法首先把每个数 郑州大学硕上学位论文 据对象x x 初始化为一个单独的簇t t ，然后合并在当前划分下使互信息 i ( 乃】，) 损失最小的两个簇，从而最大化地保存r 和】，之间的互信息，直到簇 的个数i 刁的值变为l 。该算法具有与d i b 相同的时间和空间复杂度，但是在最终 结果的每个簇中可以保持比d i b 算法多的互信息。s i b 算法由s l o n i m 于2 0 0 2 年 提出，是一个具有类似k m c a l a s 结构顺序划分算法。该算法随机地把x 划分到确 定大小的丁中。在此基础上迭代地将彳中的每个元素工从其当前所在的簇中取出， 作为单独的一个簇，然后将x 合并到使互信息损失最小的新簇中。反复执行该过 程，直到得到一个稳定的局部解。 由于i b 方法的理论基础好且具有实际应用价值，近几年来，更多的研究人 员被吸引到该领域的研究中，使得i b 方法得到不断的扩充和完善，相继出现了 i b s i 【6 、a s i b 8 1 、i s l b 【9 1 、g i b 1 0 , 1 1 】、m i b 1 2 - 1 4 等相关的研究成果。目前i b 方 法已经在有监督的和无监督的文本分类i s , 1 5 - 1 9 】、自然语言处理【2 0 1 、范畴类型数据 分析【”- 2 2 、图像数据聚类【2 3 之6 1 ，语音识别【2 7 1 、星光谱分析【2 引、神经代码分析【2 9 删、 基因数据分析、多媒体信息检索3 2 1 等多个领域得到了应用，且取得了令人满 意的效果。 在已有的i b 算法中，a i b 算法可以保持较多的互信息，且可以得到一个反映 数据内部结构的自底向上的层状树状结构，因此具有较为广泛的应用。a i b 算法 通过计算数据对象之间的相关性，合并使互信息损失最小的数据对象对，所得到 的层次树状结构能充分体现出源数据对象内部的隐含结构。2 0 0 2 年，j a c o b g o l d b e r g e r 等人，将a l b 方法应用于图像聚类【2 5 1 。2 0 0 3 年，s h i dg o r d o n 等人用 a i b 进行无指导的离散和连续图像的聚类【2 2 1 。2 0 0 6 年，j a c o bg o l d b e r g e r 、s h i r i g o r d o n 和h a y i tc r r e e n s p a n 将a i b 应用于无指导的图像集聚类，得到一个自下而 上的树状结构，并用该树状结构进行高效图像检索，取得了满意的效果【2 3 】。然而， a l b 算法存在下述两个问题： ( 1 ) a l b 算法具有较高的时间和空间复杂度。由于a l b 算法输出的是一棵完整 的反映数据内部模式的层次树状结构，所以其时间和空间复杂度相对较高。 ( 2 ) a l b 算法的次优解问题，即保持的互信息量相对较低：a i b 算法在每一步 合并中仅检查当前划分中每两个对象之间的合并代价。设乃为当前划分，死j 为 合并“最佳合并对象对”之后的划分。显然，吲= i 耳，| + l 。a i b 算法在每一步中通 2 郑州大学硕士学位论文 过最大化及正功得到一个局部最优的值。但是，这不能保证对每一个划分r 都得 到最优解，甚至对一个确定的丁也不能得到最优解。另外，通常情况下，很难通 过一个简单的合并就从一个最优的划分乃得到最优的划分死j 产生这种问题主 要基于两个原因：在当前划分乃中，算法仅对所有可能的划分死，中的一个小 的子集进行检查，不能保证检查的范围中包含有一个最优解。在许多情况下， 这种贪婪的决策存在不确定性，即可能存在多个信息损失最小的对象对，a i b 算 法随机地选择其中一对进行合并。如果要决定最优的对象对，需要检查由这个合 并引起的所有潜在合并，而这个过程在最坏情况下是呈指数级增长的【4 】。针对这 个问题，s g o r d o n 等人用a i b 算法的结果来初始化s i b 算法和k - m e a n s 算法，通 过s i b 算法和k - m e a n s 算法的进一步优化，得到具有较高精确度的结果。需要指 出，s g o r d o n 等人的方法不能产生一个层次树状结构输出。这在某种程度上偏离 了发现数据对象内部隐含结构的本质含义。 本文关注第二个问题，考虑两个数据对象之间的相关信息以及它们邻域内包 含的其它数据对象之间的相关信息，引入密度相连链的概念，并基于此提出了一 种基于密度相连的i b 算法，解决了a i b 算法保持的互信息量较低，精确度较差 的问题。 1 2 本文工作概述 本文首先对i b 理论进行了概述，并对基于i b 理论的若干经典算法进行了描 述。同时分析了a l b 算法的优点和缺点，并对导致问题的原因进行了详细的分析 和研究。最后，在对问题分析和理解的基础上提出了通过密度相连的概念来解决 a i b 存在的次优解问题，且提出了基于密度相连的i b 算法一一d a i b 算法。 本文旨在改进a i b 算法，使其在克服次优解问题的同时，保持一个层次树状 结构输出。聚类分析方法是数据挖掘中的一类重要方法，该方法可以用于发现复 杂数据集内部的隐含结构。m e s t e r 等人基于密度的思想，设计出了d b s c a n 算 法，用以发现数据集中任意形状的簇【3 3 l 。该算法定义了一个数据对象的g 邻域， 进而用它判断该数据对象的邻域是否足够稠密，然后应用密度可达的思想来发现 数据集中任意形状的簇。 a i b 算法在每一步中仅考虑两个数据对象之间的信息损失，忽略了周围其它 郑州大学硕：l 学位论文 邻居之间的环境信息，并且，如果同时存在多个信息损失最小的数据对象对，a i b 算法随机地选择其中一对进行合并，这最终导致了次优解的问题，不能保持尽可 能多的相关信息，从而降低了聚类结果的精确度。针对a i b 算法在数据降维过程 中仅考虑两个数据对象之间的相关信息，忽略它们邻域内包含的其它数据对象之 间的相关信息，本文将改进a i b 算法作为发现数据内部隐含结构问题，同时考虑 两个数据对象之间的相关信息以及它们附近区域内包含的其它数据对象之间的 相关信息，引入密度相连链的概念，进一步提出一种基于密度相连的i b 算法一 - d a i b ，并为该算法的参数确定了一个具有一定普遍适用性的取值。需要指出， d b s c a n 算法已经用密度的概念来发现任意形状的簇。但是，本文中的距离度量 方法，参数个数以及密度相连链的概念都不同于d b s c a n 中的相应部分。 d b s c a n 中的参数e p s 和m i n p t s 均取全局值【3 3 1 ，而d a i b 中所考虑的两个对象 之间的相关信息是局部值，这是有很大区别的。在i b 算法研究所用的公共数据 集上的实验结果表明，d a i b 算法的聚类结果比a i b 算法的结果具有更高的精确 度，有效地解决了a i b 算法存在的问题。 1 3 本文内容与结构 针对a i b 算法在实际应用中逐渐暴露出来的次优解问题，即所保存的互信息 及精确度较低的问题，本文按照以下结构重点研究以上问题。 第一章：绪论。 第二章：背景知识。本章首先介绍了信息论中的一些概念，包括：熵，互信 息，k l 距离，刀距离，m a r k o v 链等；然后介绍了率失真理论和相应的 b l a h u t - a r i m o t o 迭代算法。最后介绍了i b 理论：概述了m 理论和率失真的关系， 并且描述了从率失真到i b 理论的数学推导，同时给出了i b 目标函数和i b 形式 解的推导，并简要分析了i b 理论参数之间的关系；最后简要总结了若干i b 经典 算法及其各自的优缺点。 第三章：基于密度相连的m 算法。该章第一节详细介绍了密度相连链的概 念。然后介绍了基于密度相连的i b 算法一一d a m 算法。最后对d a i b 算法进行 了分析。 第四章：实验与结果分析。为了验证d a i b 算法的有效性，我们在研究i b 算 4 郑州大学硕上学位论文 法所用的公共数据集上，对d a l b 算法和a l b 算法的实验结果在所保存的互信息 量及其最终精度两个方面进行了比较。 第五章：总结与展望。 5 郑州人学硕七学位论文 第二章lb 理论与算法 1 9 9 9 年，t i s h b y 、p e r e i r a 和b i a l e k 提出了一种源于率失真的数据分析方法 i b 方法( t h ei n f o r m a t i o nb o t t l e n e c km e t h o d ) 1 1 。该方法避免了失真度量函数 的任意选择。i b 理论通过定义变量x 的相关变量y 推导出一个合理的失真度量 函数，有效地解决了率失真理论存在的失真函数难以确定的问题，且具有许多率 失真方法不具备的特殊性质，从而可以有效地发现了数据内部的隐含结构。2 0 0 2 年，s l o n i m 在其博士论文中阐述i b 方法的起源，把已有的i b 算法和应用进行 了系统的归纳和总结，提出了m 理论【2 1 。2 0 0 7 年，h a r r e m o e s 和t i s h b y 在文献【3 】 中提出i b 方法具有许多率失真方法不具备的特殊性质，从而证明了i b 方法的有 效性和独特性。m 理论包括单变量i b 理论( s i n g l es i d e di n f o r m a t i o nb o t t l e n e c k ) 与多变量i b 理论( m u l t i v a r i a t ei n f o r m a t i o nb o t t l e n e c k ) 以及相应的若干经典i b 算 法。本文仅对单变量i b 理论及若干算法进行讨论。 本章主要阐述了单变量m 理论及其经典算法。首先，对本文用到的符号进 行了约定，然后给出了相关概念的定义。相关概念的描述源自文献【3 4 1 。2 2 节描 述了率失真理论，并描述了率失真函数的形式解的推导过程，然后介绍了实践中 广泛使用的求解率失真函数的b l a h u t a r i m o t o 算法。第3 节介绍i b 理论。第4 节描述了基于单变量i b 理论的四个经典算法，并简单讨论各个算法的特点。 2 1 相关概念 本节首先对本文中使用的数学符号进行约定，然后描述了与本文工作紧密相 关的一些基础概念。这些相关概念的描述源自文献 3 4 】。 2 1 1 符号约定 大写字母z ) 代表离散型随机变量，其单个特定取值用小写字母( 五男) 来表示。概率分布p 印，表示离散型随机变量x 取值为x 时的概率。约 定石节代表离散型随机变量彳服从概率分布刖。约定仪珍似五) ，) 代表随机变 量x 和】，服从联合概率分布俐，相应j 地p ( x ) = s y p ( x , y ) ，加) = 砒力代表其 边缘分布。约定p o 代表条件概率分布。阂，i 】，l ，l 刁分别代表随机变量五et 中 6 郑州人学硕士学位论文 元素值的个数。 2 1 2 熵 为了寻找可以度量满足一定分布的随机变鄞o ) 的不确定性，s h a n n o n 建议建 立一个满足一定条件的度量方法，该方法标记为月。这些条件可以反映出一个 合理的不确定性度量值的取值。在信息论中把熵归纳为满足以下三个条件的数学 函数【3 5 】。 首先，该度量方法的取值应该是连续的。概率分棚中极小的改变不能导 致日的急剧变化。所以第一个条件是： 条件1 月在p 上的取值应该是连续的。 如果该事件是等概率事件，那么增加事件的个数应该增加事件的不确定性。 所以第二个条件是： 条件2 ：芒e p ( x i ) = 1 i 的情况下，函数月相对于i 是单调递增的。 最后一个条件是关于月的一致性要求。 条件3 对于把】，= l 扰，y l y l ) 分组到r = ( “，乏，m ) 的所有可t 日、匕v - , 口j 旧况，函 骜t h ( r 3 满足如下一致性关系： 们 日( 】，) = 日( 丁) + 艺p ( ) 日( p ( yi ) ) i = l 如下的b o l t z m a n n - s h a n n o n 熵是唯一一个满足如上三个条件的函数丘 定义1 设离散随机变量朋艮从酬分布，则肭熵日i 定义为 日( x ) = h 【p ( x ) 】= 一p ( x ) l o g p ( x ) ( 2 1 ) 熵可以用来度量离散型随机变量的不确定性。公式中对数的底数决定了其结 果的单位。当底数是2 时，该单位是比特似t ) ；当底数等于e 时，单位为奈特( n a t ) ； 在实际工程应用上常以1 0 为底，此时得到的单位为笛特( d e t ) 。在本文的相应部 分，我们默认该对数底数是2 。 当考虑两个或多个变量时，熵的定义可以形式化地表示如下。 定义2 如果( 墨y ) - p ( x o , ) ，即随机变量功服从联合概率分布p o 哕) 时，那么 两个随机变量的联合熵脚陇d 可定义为 h ( x ，y ) = 一p ( x ，y ) l o g p ( x ，夕)( 2 2 ) ，e y 日 定义3 如果墨y ) - - - p ( x , v ) ，即随机变量c 墨y ) 服从联合概率分布烈_ 力时，那么y 7 郑州大学硕i ：学位论文 关俐条件熵坝】，可定义为 h ( yx ) = 一p ( x ，y ) l o g p ( yx ) ( 2 3 ) 其中，联合熵和条件熵具有如下关系：同y ) 爿双焖+ 同鄙i y ) 嘲y ) ，该等 式即为链式法则【3 4 1 。 2 1 3k l 距离 定义4 概率分布p 和g 之间的相对熵或k u l l b a c kl e i b l e r ( k l ) 距离定义 为【3 4 】 啪) 2 三m ) l o g 鬻 ( 2 4 ) 其中0 l o g ( o q ) = o ，p l o g ( p o ) = 0 0 。 k l 距离又称为相对熵，它度量了两个概率分布的“距离 。需要注意的是， 碰距离不具有对称性，即d ( p i i 口) d ( qi i p ) ，同时也不满足三角不等式。d k l ( p l i q ) 1 0 ，当且仅当眵似= g 俐时，两个概率分布的豇距离等于0 。随着他们的分布差异 度增加，甩距离也随之增加。 2 1 4 互信息 定义5 如果两个随机变量满足d - 一p ( x , y ) ，且存在x - p ( x ) 和y - p o ) ，那么互 信息心功定义为【划： 旭；y ) - ，p ( 五川l o g 州p ( x p , y 【万) x e x v e y ( 2 5 ) d 工l d v l 从定义可以看出互信息心功是联合分桃力和乘积分布p 僦) 之间的相 对熵。该信息可以得到随机变黠院问共有信息量的多少，从而表明他们相 互包含的程度，进而反映出两个变量的关联程度。当且仅当变黠啪互独立 时，即删彳，印，它们之间的互信息研矽= 0 。互信息满足对称性： 心功姐y 冯。互信息牺矽还可以表示为： ，c x ，y ，2 ；莓p c 五y ，- 。g ；乞s 击 = p ( 工，y ) l o g ( p ( x ，y ) - e z p ( x ，y ) l o g p ( x ) - z p ( x ，y ) l o g p ( y ) = 一日( x ，】，) + 日( x ) + 日( 】，) 郑州大学硕一卜学位论文 = 日( x ) + 日( y ) 一h ( x ，y ) 舭2 军莩加) l o g 器 ( 2 6 ) = 莓；p c 圳崦鬻 = p ( x , y ) l o g p ( yx ) 一p ( x ，y ) l o g p ( y ) = h ( y ) - h ( y lx )( 2 7 ) 式( 2 6 ) 表明互信鼢功意味棚y 的联合压缩和独立压缩之间相互比较时 的平均比特数( 此时l o g l 拘底数为2 ) 。从式( 2 7 ) 可以看出互信肌矽表示在给定 廊识的条件下珀勺不确定性的减小量。由于互信息具有对称性，所以还可以得 坝y ) 一顾y x ) = h ( j o - h ( a 口y ) 。 图2 i 描述t h ( x ) 、觑d 、h ( x , i o 、俄聊、月i y ) 和桶矽之间的关系【3 4 1 。x 和啪相交部分即为互信胍y ) 。 ht x ) ht y ) 图2 1 熵和互信息之间的关系 2 1 5j s 距离 定义6 概率分布p ，和助之间的j e n s e ns h a n n o n ( j s ) 距离定义为阁 刀兀( p li i p 2 ) = 乃d 碰( p li i p ) + 万2 d k ( p 2i i p ) ( 2 8 ) 其中，p = 万l p l + 死p 2 ，n = 以，万2 ) ，且满足o 万l ，万2 o ，且满足： 黑= - p 国 证明：首先对p ( tix ) 求导数。由k u h n t u c k e r 条件可得式( 2 1 1 ) 取得最小值的充 分必要条件是历篙= 。，记p ( f ) = 莓p ( x ) p ( f l 破则 丽5 f 叫抛等圳矿；m 删z ) 去m ) + 眦卅相= 。 其中；p ( x 伽i 工) 高p ( 曲叫x ) l o g z 舻篙，得 p ( 工) 【l 。g 三暑导手上+ d ( x ，r ) + l 。g z ( x ，) 】= 。 。洲垆器p 叫) ( 2 1 2 ) 需要注意的是以上过程得到的仅是一个形式解，实际上需要利用迭代算法来 求率失真函数的局部优解。 2 2 2b l a h u t - a ri e o t o 算法 考虑如下问题：4 与口为尺”中两个不相交的凸集，希望得到他们之间的最 小距离，如图2 3 所利划。可以用以下的交替迭代计算过程来计算：首先固定彳 中任取一点a ，酬，然后在曰中找出与它距离最近的一点b ，印。固定b ，再在 彳中找到距b ，最近的一点心重复执行上述过程，随着重复次数的增加，彳与曰 之间的距离将严格较小。然而，这个迭代过程是否收敛? 是可以得到两个集合间 的最小距离? c s i s z a r 和t u s u a d y 已经证明【3 7 1 ，在彳、曰均为凸集，且距离测度方 法满足适当条件的情况下，上述迭代计算过程确实可以收敛，并且达到最小值。 特别地，如果两个集合均为概率分布，且使用k l 距离作为距离度量方法，则以 上迭代过程将最终收敛到两个概率分布集合的最小相对熵。该算法即为 1 2 郑州大学硕上学位论文 b l a h u t a r i m o t o 算法【2 】o 图2 3 两个凸集上的距离 在使用以上迭代过程来求尺p ) 时，需要把尺) 进行转换，即把它作为两个 凸分布集合间k l 距离的最小值。为此引入如下引理【3 6 】： 引理1 设p ( x ) p ( t l x ) 是给定的联合分布，则使相对熵 d r a 【p ( x ) p ( flz ) l ip ( 石) p ( f ) 】最小的先验概率p ( f ) 恰好是相应于p ( x ) p ( t l x ) 的边缘分 布p 幸，即 p 。( f ) = p ( x ) p ( t 盼 ( 2 1 3 ) 通过该引理，可将率失真函数表示为如下形式： r ( d ) = m ，i n 。、毋；翌。d 碰 p ( x ) p ( f i x ) l l p ( x ) p o ) 】( 2 1 4 ) 、7 p ( f ) ，( f 恤i e ( d ( 工j ) ) ：d l 1 、7 、。 7”1、71、7。、7 如果a 为所有联合分布烈功的集合，且其边沿分布p 满足失真限制。并 且b 表示乘积分布m 掀d 构成的集合，其中烈力是经过规范化处理的。那么可 以得到： r ( d ) = m i 。n m i n 口0b 】(215)b e bd e 一 算法1 是b l a h u t - a r i m o t o 迭代计算过程2 1 。算法需要用户输入值。首先对 烈力进行随机初始化处理，然后利用这个初始化的值通过公式( 2 1 2 ) 计算p ( t l x ) 。然 后再通过公式( 2 1 3 ) 更新烈力。重复这个过程，直到收敛到一个极限值。c s i s z a r 已证明该极限为尺例【3 羽。 如上描述，该算法仅可以处理在压缩变量集合( 冲元素) 确定的情况下来 求最优划分( 描述为p ( 引力) 的问题。需要注意的是，这里失真度量函数是 需要预先确定的，而好的失真度量函数不是容易确定的。 郑州大学硕十学位论文 算法1b l a h u t a r i m o t o 算法 输入： 源分 平衡参数夕 收敛参数f 瑚压缩表示z 失真度量函数d ：x x 卜矿 输出： 函数r ( d ) 值，其斜率为一夕 初始化： 初始化r ( o ) 一；随机初始化p ( 力 删l et r u e ： p 川川加高e - # d ( x s ) , v t t , 坛“ 厶 ，j p “o ) = p ( x ) p ”+ 1 0ix ) ，v t t r 肿1 ( d ) = ( p ( 石) p 斛1 ( t ix ) 1 1p ( x ) p 斛1 ( 吵 i f ( r m ( d ) - r m + 7 ( d ) ) eb r e a k ； e n d 、 m i l e 2 3ib 理论 i b 理论是e h t i s h b y 、p e r e i r a 和b i a l e k 与1 9 9 9 年提出的一种数据挖掘方法。该 方法源于率失真理论，通过定义变剥相关变量l 推导出一个合理的失真度量 函数，有效地解决了率失真理论存在的失真函数难以确定的问题，且具有许多率 失真方法不具备的特殊性质。首先我们把率失真理论形式化表示为， r d 2 ：晚一x ；n ( 2 1 6 ) 烈f k ) ：e ( d ( j ，f ) ) 叠d ) ，16 、 其中，耳眠f ) ) 是姒f 盼为自变量的失真度量函数d ( x , 0 的数学期望。 i b 理论与率失真理论最大的不同是，避免了失真度量函数的任意选择【l 】。m 1 4 郑州大学硕卜学位论文 理论的思想可以概括如下：设玲甲吣) ，然后定义变粼压缩代表丁，使得 在压缩艇0 确过程中可以尽可能多的保撇于啪相关信息。这就好像在压缩x 到r 的过程中把秩于y 的相关信息也压缩进去，从而使得该信息得以最大化保 持。 i b 理论源于率失真理论，我们将通过如下过程看到他们的关系。 对式( 2 1 6 ) 中的m ，力赋值为下式： d ( x ，f ) = d 碰( p ( yi 功l ip ( yif ) ) 其中，d 甩( 厂l ig ) 是厂( ) 和g ( ) 之i n - l 拘k u l l b a c k l e i b l e r 距离。在i b m ! 论中，变量 五r 和】，满足i bm a r k o v 链，即 肘e从而可以得到 m ，钞) 印似咖k ，力印 ，枷( y 。可利用这一关系对式( 2 1 6 ) 中的耳妣力) 进行如下 推导： e ( d ( x ，f ) ) = 研d r 匝( p ( yix ) | ip ( yff ) ) 】 = ( 彬) y m l o g 黜 = 枷p 化例。g 船 = 枷p ( 砒她等一e x , t , y p ( 枷) l o g 锗 = j ( x ；】，) 一，( r ；】，) ( 2 1 7 ) 将式( 2 1 7 ) 代入率失真函数( 2 1 6 ) 中，可以得到： 尺( d ) = m i n p ( t 忙) j t x ；y ) t ( r ；r ) s d 舭川 ( 2 1 8 ) 一 ，) 1r 、 由于式( 2 1 7 ) 中心y ) 是一个常量，式( 2 1 8 ) 可以进一步写作， r d 2 似取船必拟；d ( 2 1 9 ) ，( f 协) 0 ( r ；y ) d ，1 0 、 式( 2 1 9 ) 良p 是m 理论的数学形式化表示。从该式可以看g s i b 理论是在确保相 关信息及乃d 不小于下确届d 的情况下，使压缩信息魍d 最小化。该式的求解可 采用拉格朗日乘数法，即最小化i b 目标函数， ( p ( fix ) = ，( r ；工) 一( 丁；】，) ( 2 2 0 ) 其中，拉格朗日因子是一个平衡参数，用以平衡源信息的压缩和相关信息的保 1 5 郑州大学硕：l 学位论文 存。在它两端同除以一，可得到等价的目标函数， k ( p ( f i x ) = 邶；y ) 一帼；x ) ( 2 2 1 ) t i s h b y 等人已经给出该函数的形式解为： p ( f l 加器p 饿小m m 玎z 其中z ( x ，) = p ( t ) e x p ( - f l d x z p ( y x ) 1 1p ( yf ) 】) 。当_ o o 时，i b 目标函数变 成最大化卿y 之间的互信息i ( r , 1 9 这时，p ( f 取0 或1 2 4 基于ib 理论的算法 2 4 1 ib 算法 首先来看夕确定的情况。此时采用一个迭代算法，即在第m 次迭代时得到 条件概率分布 ，o 盼) ，然后在m + 1 次迭代过程中算法采用如下步骤来更新 烈f ： 小) 卜芳斋p 如酬比朋1 ( 2 2 2 ) 其中矿( 力和p m ( y l o 可有提交概率分布 矿( f ) 和i bm a r k o v 链胯柑】，计算得 到，即： f p 研( f ) = 工p ( x ) p m ( tlx ) h 巾) 2 而1 ( f i 却( w ) 此算法即为i l b 算法。算法2 给出了i l b 算法的过程描趔。图2 4 显示了i l b 算 法的迭代过程。 1 6 郑州大学硕上学位论文 图2 4i i b 算法的迭代过程 算法2i l b 算法【2 1 输入： 联合分布p ( x ，y ) 平衡参数1 3 压缩变量参数i 叮l 和收敛参数p 输出： 一个旌0i 卅个簇的不确定的“软”( s o f t ) 划分z 初始化： 随机初始化p ( t l x ) 并由式( 2 2 9 ) 计算相应的p ( t ) 和p ( y l t ) p 川川功= ；p 慨( p f 删矿) ) ，v t “比x p 胂+ 1 ( f ) 2 莩p ( 石) p 斛1 ( t lx ) ，v f t p 川( y i 垆高莩p m + l ( i p ( 训) , v te t , 跏y i f v x x , j s i l i i p ”+ 1 ( fix ) ，mx ) 】占，b r e a k ； 该算法是b l a h u t - a r i m o t o 算法的自然推广。但是他们有一个重要的不同。 理论上b l a h u t a r i m o t o 算法可以收敛到相关压缩曲线上一个确定的点，这个相关 压缩曲线是由失真函数和确定的l 刁定义的。所以，b l a h u t - a r i m o t o 算法的迭代最 小化过程在集合仞( f i x ) ) ， 烈力) 上进行。然而，在i m 算法的迭代过程中，其相关 1 7 郑州大学硕十学位论文 压缩曲线不需要事先定义失真度量函数。i m 算法的迭代最小化过程在代表分布 集合仞( y i 力) 所以，通常情况下不能保证解得唯一性，而只是可以得到一个局部 最优解。 2 4 2d lb 算法 d i b 算法是一种确定的类似模拟退火的i b 算法。该算法试图通过增加值 来重构最优的相关压缩曲线。当夕= o 时，压缩代表中仅含有一个元素，即i 刁= l