（计算机软件与理论专业论文）一种优化的顺序ib文本聚类算法.pdf

内容摘要 一种优化的面涛m 文本聚类算法 摘要 随着网络信息的飞速增长，对于文本聚类技术的研究显得更为重 要由于文本数据高维性和稀疏性，传统的文本聚类算法并不能让人 满意。m 方法是基于信息论的数据分析方法，该方法通过信息压缩与 信息保存之间的平衡处理，有效地解决了精度和效率之间的平衡问题。 m 方法的性质决定其适合解决文本聚类问题。在基于m 理论的算法 中，s m 是较好的算法，但仍存在运行效率低、优化不充分等问题。 本文针对s m 算法在文本聚类问题上存在的问题：易陷入局部优 解、效率较低，基于模拟退火方法，提出一种优化的顺序文本聚类算 法s a - i s m 该算法根据一个合理的退火序列，从基本s m 算法产生的 初始聚类结果中随机选取一定比例的文本，对其类标记进行随机修改 并重新对解进行优化，在经过退火过程后，s a - i s m 能够得到比s m 算 法精度更高的文本聚类结果。在研究m 的公共文本数据集上的实验结 果表明；与s m 算法相比，s a - i s m 不仅能有效提高文本聚类的精度， 还具有较高的运行效率；并通过实验可知，随着优化次数的增加， s a 血m 的聚类精度和运行效率优势更加显著，且s a i s m 的精度提高 幅度逐渐减小，这证明算法是收敛的。 由于m 方法已经成功应用于许多领域，s a i s m 算法亦可以应用 到其他实际问题中，该算法的研究具有广泛的实际意义。 关键词；文本聚类；m 理论；s m 算法；模拟退火；s a i s m 算法 a b s t r a c t 一种优化的顺序毋文本聚类算法 a b s t r a c t w i t ht o d a y s r a p i de x p l o s i o no ft e x t u a li n f o r m a t i o no v e rt h ei n t e r a c t ，t h e r e q u i r e m e n t o fo b t i a n i n gi n f o r m a t i o nf r o m h u g em o u n to ft e x t s i s r a p i d l y i n c r e a s i n g 猫w e l l r e s e a r c ho nt h et e x tc l u s t e r i n gt e c h n o l o g yh a sc o n s e q u e n t l y o b t a i n e dg r e a ta t t e n t i o n a st h et h eh i 【g h - d i m e n s i o n a ld a t aa n d s p a r s e ，t h et r a d i t i o n a l t e x tc l u s t e r i n ga l g o r i t h m sc a nn o tg e ts a t i s f y i n gd 0 0 3 m e n tc l u s t e r i n gs o l u t i o n s i b m e t h o d ，a sad a t aa n a l y s i sm e t h o db a s e do ni n f o r m a t i o nt h e o r y ，e f f e c t i v e l ys o l v e s t h et r a d e o f fb e t w e e nt h ea c c u r a c ya n dt h ee f f i c i e n c ye x i s t e di nc o m p l e xp r o b l e m s b yb a l a n c i n gi n f o r m a t i o nc o m p r e s s i o na n di n f o r m a t i o np r e s e r v a t i o n t h es e q u e n t i a l o p t i m i z a t i o na l g o r i t h m ( s l b ) i sab e t t e ra l g o r i t h mo fi ba l g o r i t h m s b u ts l ba l g o r i t h m h a ss o m ep r o b l e m si ne f f i c i e n c y ，a c e u r a f ya n ds oo i l t os o l v et h ep r o b l e m so fl o c a lo p t i m a la n dl o we f f i c i e n c yi ns i ba l g o r i t h mf o r d o c u m e n tc l u s t e r i n g ，t h i sp a p e rp r o p o s e sa ni m p r o v e ds e q u e n t i a li ba l g o r i t h m n a m e ds a - i s i b u s i n gas u i t a b l ea n n e a l i n gs e q u e n c e ，t h i sa l g o r i t h mr a n d o m l y s e l e c t sc e r t a i np r o p o r t i o n a ld o c u m e n t sf r o mt h ei n i t i a lc l u s t e r i n gs o l u t i o no fb a s i c s l ba l g o r i t l u n ，t h e nr e v i s e st h ec l u s t e r i n gl a b e l so fs e l e c t e dd o c u m e n t sa n do p t i m i z e s t h es o l u t i o ni t e r a t i v e l y a f t e rt h ep r o c e s so fs i m u l a t e da n n e a l i n g ，t h ea l g o r i t h mg e t sa h i g h e ra c c u r a c yd o c u m e n tc l u s t e r i n gs o l u t i o n s e x p e r i m e n tr e s u l t so nd o c u m e n t d a t a s e t ss h o wt h a ts a - i s i ba l g o r i t h mi se f f i c i e n ta n di m p r o v e st h ea c c u r a c yo fs i b a l g o r i t h mf o rd o c u m e n tc l u s t e r i n g i bm e t h o dh a sa p p l i e di nm a n yf i e l d se x c e p td o c u m e n tc l u s t e r i n g ，t h es a - i s i b a l g o r i t l u nc a nb eu s e di nt h e s ef i e l d s ，t o o t h er e s e a r c ho ft h ea l g o r i t h mh a s e x t e n s i v er e a l i s t i cm e a n i n g k e yw o r d s ：d o c u m e n tc l u s t e r i n g ；s i ba l g o r i t h m ；i bt h e o r y ；s i m u l a t e da n n e a l i n g ； s a - i s l ba l g o r i t h m 第一章绪论 一种优化的顺序m 文本聚类算法 第一章绪论 传统的文本分析方法忽略了原始文本数据的语义和记数值间的关系，往往 不能得到较好的分析结果。m 理论则较好地解决了这个问题。在现有的基于m 理论的算法中，连续优化算法s i b 是较好的一个文本聚类算法，但该算法存在 运行效率低、聚类结果优化不充分等问题。本文针对s i b 算法中存在的问题， 引入模拟退火思想，提出了s a - i s l b 算法，并通过在研究m 的公共文本数据集 上与s i b 算法的对比实验验证了该聚类算法的有效性。 1 1 研究背景 在当今社会，随着计算机网络通讯技术的高速进步，尤其是互联网的迅速 普及，使得信息量成几何数级增长，要从中获取所需的全部信息要花费大量的 时间和精力。因此，如何从海量的文本中快速取得所需要的信息，成为关注的 焦点。文本聚类技术使计算机处理大量的文本信息成为可能。 文本聚类是按照某种准则对文本集合进行组织或划分，使得相似的文本划 分到同一簇中，差异较大的文本划分到不同簇中。文本聚类技术在信息自动获 取，w e b 数据挖掘等很多领域有着广泛的应用。传统的文本聚类算法主要有基 于划分的方法( 如k - m e a n 等) ，层次化聚类方法等，但由于文本数据的高维性和 稀疏性，这些算法的结果并不能令人满意。1 9 9 9 年，t i s h b y 、p e r e i r a 和b i a l e k 开创性地提出一种基于信息论的数据分析方法m 方法1 1 l ( t h ei n f o r m a t i o n b o t t l e n e c km e t h o d ) 。i b 方法已经在多个领域得到了应用，包括有监督的和无监 督的文本分类【凋、图像聚类呻】、星系光谱分析 9 1 、基因表达分析l 埘、神经系统 编码分析【1 1 一、自然语言处理【1 3 1 、语音视频处理【排垧等等。2 0 0 2 年，s l o n i m 将m 的原理、算法与应用在其博士论文中进行了系统地整理与归纳，并将其命 名为m 理论 1 7 1 ( t h ei n f o r m a t i o nb o t t l e n e c kt h e o r y ) 。近几年来，m 理论不断 地得到发展，如i b s i 【1 8 1 9 、c i b 2 0 1 、c c i b 2 1 1 、m i b1 2 2 - 2 3 1 、g i b1 2 4 - 2 5 】、s d r 【2 咖、 双向聚类例、i b & s v m l 2 9 1 等相继出现由于m 理论的理论基础好且应用范围 广泛，使得更多的研究人员被吸引到该领域的研究中，使得理论得到不断的 扩充和完善 3 0 - 3 孤。 第一章绪论一种优化的顺序m 文本聚类算法 现有的m 算法有基于迭代的i m 算法【1 , 2 , 1 7 , 3 4 ，自下而上的凝聚 ( a g g l o m e r a t i v e ) 算法a i b ，自上而下的分裂算法( 1 i b 。以及连续的优化算法s i b 。 其中s i b 使用连续迭代过程对问题进行求解，相对于其他琚算法，s i b 算法具 有较低的时间和空间复杂度，且可以得到更精确的文本聚类结果【2 ，堋。 1 2 本文的工作 基于m 理论的顺序m 算法( s m 算法) 由s l o n i m 等人于2 0 0 2 年提出1 2 】， 该算法通过将数据对象压缩到一个事先定义好的“瓶颈”变量的过程中极大地保 持其与另一数据对象的相关性，从而有效地发现数据对象间隐含存在的模式。 s l b 算法的数据压缩和信息保存以数据对象间概率分布的相似性为度量准则， 这种数据分析方法在数据语义的自动获取方面有效，有益于克服文本数据的稀 疏性和语义表示的复杂性所存在的问题。 文献【2 1 通过实验证明，对于文本聚类，s i b 算法能够有效发现文本数据的 语义特征模式，其聚类精度不仅明显优于传统的文本聚类算法，而且和其他m 算法相比，其聚类精度和效率优势也较明显。但是，s l b 算法在文本聚类中存 在一些问题：第一，随机初始化对聚类结果有直接的影响，使其易陷入局部最 优；第二，优化不充分，效率较低。这使得算法的应用受到了限制。0 4 年p e l t o n e n 将m 目标函数改造为贝叶斯因子，提出一种类似于s i b 算法的f s i b 算法【3 “， 该算法在小规模稀疏数据集上效率较好。但这些改进仍然不能解决s i b 算法所 面临的问题。 基于以上的分析，如果能够克服s i b 算法所存在的对于初始解敏感，易限 于局部最优，运行效率较低等问题，那将有利于文本聚类。本文针对s m 算法 存在的问题，提出了一种适宜于文本聚类的优化顺序m 文本聚类算法。该算法 基于一个合理的退火序列，从基本s i b 算法产生的初始聚类结果中随机选取一 定比例的文本，对其类标记进行随机修改并重新用基本s i b 算法对解进行优化， 在经过一个退火过程后，最终得到比s i b 算法更高精度的文本聚类结果。在研 究m 算法的公共文本数据集上的实验结果表明，与s i b 算法相比，该算法不但 可以得到更优的文本聚类结果，并且算法效率也得到了明显的提高。 2 第一章绪论 一种优化的顺序i b 文本聚类算法 1 3 本文内容与结构 本文组织如下： 第一章绪论 介绍本文的研究背景与现状、研究意义以及具体的研究内容。 第二章相关知识 本章首先介绍了信息熵中的一些概念，包括熵、互信息、凰距 离、耶距离、m a r k o v 链等；然后是率失真理论和b l a h u t - a r i m o t o 迭代算法；m 理论以及其数学形式化描述，相应的m 目标函 数的推导过程；然后是基于该理论的l i b 算法，a i b 算法和d i b 算法以及其特点。 第三章一种优化的顺序m 文本聚类算法 这一章介绍s i b 算法和模拟退火思想，提出了一种优化的文本 聚类算法s a - i s i b ，并且对该算法进行了分析。 第四章实验 在研究m 的公共文本数据集上，通过实验得到了一个合理的退 火序列，并通过s a - i s i b 算法与s i b 算法进行文本聚类精度和 效率上的对比实验，证明了s a - i s l b 算法的有效性。 第五章总结与展望 对本文工作进行总结，并指出进一步的工作。 第二章相关知识 一种优化的顺序m 文本聚类算法 第二章相关知识 i b ( i n f o r m a t i o nb o u l e n e c k ) 方法起源于香农( s h a n n o n ) 著名的率失真方法，并 于1 9 9 9 年由t i s h b y ，b i a l e k 和p e r e r a 正式提出【1 】。i b 方法是一种基于信息论的 数据分析方法。该方法对源数据变量进行分析时，将其压缩到相应的“瓶颈”变 量中，从而找到源数据变量的有效压缩表示，该压缩表示应尽可能地保存目标 数据变量的信息，最终有效地平衡了信息的压缩与保存。2 0 0 2 年，s l o n i m 在其 博士论文中将b 方法进行了系统的论述，并称之为m 理论【1 7 1 本章在2 1 节 说明m 理论的相关概念；在2 2 节说明率失真理论；2 3 节介绍m 理论；2 4 节说明基于m 理论相关算法。 2 1 相关概念 2 1 1 熵 本文中用到的符号及其意义说明如下：大写字母而y ，z ，r 表示离散型 随机变量；小写字母工，y ，t 表示相应随机变量的某个取值，石嘭t 表示x ， y ，t 的取值集合，即x e x , y e 彳和t e 呸伍，y ) - p ( x ，力表示x 和y 服从概率 分布p ( x ，y ) ；p 0 ) 和p o ，) 表示p o ，) ，) 的边沿分布：p = 乏勿0 ，力，p o ) 屯妒0 ， ) ，) ，也可表示单个随机变量的概率分布，即x p o ) 和y - p ( y ) ip ( o 表示r 的概率 分布；p o 鼢，p ( r k ) 和p o ， 表示条件概率分布；陟i ，l 卅，i 彳1 分别表示石f 和t 取值的个数。 s h a 皿o n 通过定义一个随机变量必须满足的一些条件得出了熵的定义闭，这 些条件反应了“不确定性的合理度量方法是什么”的定性的概念。s h a n n o n 定义了 三个简单直观的条件，说明只有一个数学函数满足这些要求，这就是熵经典的起 源。 条件1 月奄p 上连续 即连续性的合理要求。也就是说对于一系列事件z = ，x 2 ，x m ) ， 4 第二章相关知识 一种优化的顺序m 文本聚类算法 每个事件的发生概率分别为p 纯) ，p 0 叻，删。p ( x i x l i 砌极 小的改变不应产生熵臌值上的急剧变化： 条件2 如果p o i ) = 1 闪，则商是闪上的单调递增函数。 - 当p 1 ) - p 蚴= = p o 曲= 1 删时，熵日是w 的单调递增函数。即更多的等 可能事件会增加事件发生的不确定性( 可选择性) 。 条件3 当把事件x 三仇，x 2 ，工l 舻划分为r = ( t l ，t 2 ，知i ) ( 闪 1 1 1 i ， t i n = m ，妫且1 i ，j l 哩：t l u t 2 1 j u 知l 哟时，函数卸满足： 仃i h ( z ) 一日仃) + p 色) 日( p o i ) ) i o l _ 即一致性条件。当一个选择事件被分为两个子选择事件时，父选择事件的 熵醍其子事件熵硎搀加权和。如果从3 个事件中进行取舍，事件概率分别 为p 仇) = 1 2 ，p ( x 2 ) = 1 3 ，p ( x 3 ) = l 6 。当把p 眈) 和p 事件看作一个子事件 并- 与v ( x o 事件分开考虑时，此时熵日并不发生变化，即顶1 2 ，1 3 ， u 6 ) = h ( u 2 + l 3 ，1 6 ) = h ( 5 6 ，1 ，国。 只有数学函数日满足上面三个条件，这就是著名的b o l t z m a n n - s h a n n o n 熵 嗣： 定义1 随机变量蹦熵阿定义为 日暖) zp ( x ) l o g p ( x ) ( 2 1 ) j 卧 熵是度量是在随机变量平均描述长度的要求下，信息量的一个度量标准。信 息熵的单位与公式中对数的底有关。通信信息中经常以2 为底，此时单位为比特 ( b i t ) 。理论推导中用以c 为底较方便，此时单位为奈特 a t ) ；工程上常以1 0 为底， 此时单位为笛特( d c l ) 。本文默认对数底数为2 ，从熵的定义知：熵是玢布的一 个函数，只依赖于概率，并不依赖于随机变量麒际的取值。由连续性假设知：扩o 时，x l o g x - - - , o ，则可约定m 0 9 0 = 0 ，这说明o 概率项并不能改变熵值。 图2 1 【1 7 】说明了此时的熵随着a 从0 到1 变化时相应的变化情况。从图中知：当 j 织有两种取值棚( 1 棚时，有川固= m o g “( 1 - g ) l o g ( 1 0 , ) ；并且熵对均衡分布 = o 5 ) 有唯一的最大值，并随a 变得不平衡而趋于下降。 5 兰三兰塑羞塑塑一一 二堂垡些箜墅堡兰查壅鲞苎鎏 图2 - 1 z 只取两个值时的熵h o d 在此基础上可得出更多熵的公式 定义2 ( 弘d - p ( x ，力，则其联合熵同功定义为 日伍，y ) - 三墨p ( x , y ) l o g p ( x , y ) ( 2 - 2 )硝荫 实际上，把( 矗的看作向量值形式的单一随机变量，就可得出联合熵的定义。 定义3 如果( 弘玢节力，则条件熵翻y 定义为 日o r i z ) 。奎p ( x ) h c i i x - 力 三p 三p ( y i x ) l o g p ( yi x ) 三磊p ( z , y ) l o g p o , i x ) 互茗p ) 1 0 9 紫 - 一互吾p ( x ，y ) l o g p ( x ，y ) + 奎荟p ( x ，y ) l o g p ( x ) 一奎茗p ( x ，y ) l o g p ( x ，y ) 一( 三p ( x ) l o g p ( x ) ) h ( x ，y ) 一h ( x ) ( 2 - 3 ) 上式可写作嘲蜀功矗+ 团田，这说明了联合熵和条件熵之间的联系： 一对随机变量的熵是单个变量的熵加上另一个变量的条件熵。 2 1 , 2 皿距离 定义4 p 和口之间的相对熵l 鲥v ee i l 仃叩y ) 或勋嬲胛豇工脚z 盯5 z ) 距离定义为 6 第二章相关知识一种优化的顺序m 文本聚类算法 d n ( p l l d 。互p l o g 鬻 ( 2 q 基于连续性假设，约定：o l 0 9 0 o , p l o g p g u k l 距离描述了两个概率分布的偏离程度，是两个分布之间距离的一个度量 标准：分布差异变大时，距离随之变大。皿距离是非负的，当且仅当p = q 时， 两者的距离为o 。皿距离既不满足对称性，即d 豇( p l k l ) # d j m ( q l b t ) ，也不满足 三角不等式。相对熵可看作是当实际分布为p ，而假定分布是q 时对信息偏离 程度的一个度量标准。 2 1 3 互信息 定义5 如果( lr y - v ( x ，) ，) 且存在石申和y 巾o ，) 。互信息j ( 配y ) 是联合 分布和乘积分布p 之间的相对熵： 鹏y ) 。磊三如y ) 1 0 9 器( 2 - 5 ) 互信息度量了z - q1 7 之间的关联性，它满足对称性。当z - qy 相互独立， 即p g ，y ) = v ( x ) v f y ) 时，晒d = 0 。 实事上，互信息，( x ；y ) 的定义可重写为 晒y ) 。互茗p ) l o g 器 一三吾舶y ) l o g 訾 _ 一至茗p o ，y ) l o g p ( x ) + 三吾v ( x ，y ) l o g p ( x ly ) h ( x ) - h 僻i 功。 ( 2 6 ) 上式说明互信息 玢就是x 由于知道y 其不确定性的降低。由互信息的对 称性得 陇z ) = n o o - n o w ) 。这说明肿含有y 的信息量和坤含有朋信息量相等 由于网蜀功- - - n ( 两+ n ( v p o ，则j 四：d = 蜀+ 同( d - 月( l 的。再令拈隋j ； 田= 脚+ h ( x i x ) = h ( j o 。这说明一个随机变量同它自身的互信息就是这个随机 7 第二章相关知识 一种优化的顺序m 文本聚类算法 变量的熵。 由以上分析可以得出如下的关系图( 2 - 2 ) 【1 7 】； 懈d 、- t 丑p 0 t 觑乃 图2 2 熵和互信息之间的关系 v e n n 目f 1 2 2 表示t h ( x ) ，e f t ) ，日d ，丑因d ，同( 哟和，功之间的关系。 其中，互信息 】，) 对应于舯信息和y 中信息的交集。 2 1 4 耶距离 定义6 p 和q o 。之间的妇淞e 万s h a n n o n ( j s ) 距离定义为p 9 1 j & 。0 1 1 日) 一 d 。0 i i r ) + 如d 。( 鼋l i r ) ( 2 - 7 ) 其中，而和呢是调节参数，满足o t 嘎，呢t 1 嘎+ 死- 1 ，r r - z d + z 2 q 。 胚距离是对k l 距离的一种修改，它是一个对称的距离度量方法但不满足 三角不等式。尽管如此，这两种度量方法在许多领域都得到很好的应用，相似 距离度量方法的对比请参考【4 0 】。 定义7 五y 和z ，当z 的条件分布依赖于e 独立于五即p 仁k ，y ) - p 0 叻 时，称五y 和z 形成m a r k o v 链1 4 l 】：墨_ y o z 。或者，若联合分布p g ，y ，力 满足于p 0 ，y ，力甲0 ，y l v ( z k ，y ) = p o 枷o ，k 驷0 b ，) 时，五y 和z 形成m a r k o v 链。 事实上，謦_ + y - + z 与x 和z 条件独立于】，是等价的： 8 第二章相关知识 一种优化的顺序m 文本聚类算法 p ( 工，zi y ) - 卫苎；三羔- 型2 铲- p ( 工i ) ，) p ( zip _ ) ，) ( 2 - 8 ) 【) ，jpl y j 而且，界一y - 铊暗示着z y z 则这个条件也可写作z y z 。 由m a r k o v 链可进一步推出数据处理不等式( d a t ap r o c e s s i n gi n e q u a l i t y ) ：如 果加y - + z ，则晒功硒2 ) 由m a r k o v 链的对称性得j ( y z ) j ( 配 历 2 2 率失真理论 率失真理论( r a t ed i s t o r t i o nt h e o r y ) 中的基本问题是：给定源( s o u r c e ) 分布及 失真度量方法，则在一个可达的特定码率下，最小期望失真该如何确定。也可等 价描述为：在某个特定失真的要求下，最短描述对应的码率是多少。 对于单个随机变量矗表示为r 。如果在r 中用r 个b i t 位来表示x ，则函数r 可取2 8 个值。基于定的误差要求，可在趿其表示t - y _ 间建立一个映射关系。 对集合x 中每个值与其表示z 之间方差e ( 弘砰的最小化，即平方误差度量法，是 常用的失真度量方法之一。对语音或图像进行编码时，需要其它更有效的度量方 法。 定义9 序列矿与严之间的失真定为 1h d ( 】，t “) 一二d ( 而，) 仃i 。1 从而， d - p ( 矿y ( 矿，t 4 ) 给定源随机变量趿失真度量方法d ，0 ，则其率失真函数r ( d ) 可表示为： r ( d ) 一p 仲i 墨勰，一如，j 曲，( z ；r ) ( 2 。9 ) 、。 p 仲i 如n ，o ) p 仲 一如，j 曲 。 率失真函数r ( d ) 是满足在全体x 上l p ( f 盼= 1 以及p ( f 协0 ) d g ，幻d 的所 有o k ) 0 凸集上的凸函数【4 1 1 。本文首先说明最小化问题求解的迭代方法，如图 2 4 所示，掣上的两个凸集4 和b 之间的最小距离为： d m 一七诧d ( 4 ，6 ) ( 2 。1 0 ) 其中d ( a ，6 1 是4 和6 之间的欧几里得距离。最直接的算法是任取点4 彳， 寻找与之最近点6 口，再固定b 寻找a 上的最近点。重复这个过程，在每一步 9 第二章相关知识 一种优化的顺序m 文本聚类算法 中距离( 2 1 0 ) 都在降低【4 1 1 。c s i s z , i r 和t u s n a d y 已经说明：在凸集上，且距离满 足某些条件时，这个迭代算法能够收敛到最小值；而且，在概率分布集合上， 距离是相对熵时，这个算法在两个分布能够收敛到最小相对熵嘲。 图2 - 3 两个凸集上的距离【1 7 1 该算法同样可应用于率失真函数的求解问题。此时率失真函数需要重写为两 个集合之间相对熵的双重最小化形式： 删一m 川i n 腑跏m i l l 。莩莩p ) l o g 号磐 。嘧，k 。品袅蛳扛肿【p ( , o p ( t i x ) l l p ( 工) p ( o 】 - m ，i l l r a i n ，仁；r ) ( 2 1 1 ) p ( i ) p 咖肛“o j d 其中，e ( d o ，f ) ) 一p o ) p o l x ) a ，t ) 。 这种条件极值问题的求解可采用拉格朗日乘数法【1 棚】，即 f 【p o i x ) 】一1 ( x ；r ) + p d ( x ；r ) + ，( 力y p ( t l z ) ( 2 - 1 2 ) 其中，d ( 配乃趣q o ，功。对p ( t l x ) 求导，可得 p c t l x ) - 嫠罱 ( 2 1 3 ) 再由p ( f 盼，采用下式更新p 以最小化互信息，刀： p o ) - p ( 】0 p ( f i 功( 2 - 1 4 ) 进而就可得出相应的最小化求解过程：首先选择一个拉格朗日乘娄够和一个初始 输出分布p ( f ) ，由( 2 1 3 ) 计算p o 盼。再由( 2 - 1 4 ) 更新输出分布p ( f ) ，并把该分布作为 1 0 第二章相关知识一种优化的顺序m 文本聚类算法 下一次迭代的起点迭代的每一步会不断降低等式( 2 1 1 ) 右边的值【4 1 1 。q i 配螽r 说 明这个过程的极限就是r ( d ) 【4 3 l 。其中，d 和r ( d ) 的值依赖于。这样，连续动态 地设置卢值就可以绘制出r ( d ) 曲线【1 7 1 。 图2 - 4r ( d ) 曲线 图2 5 说明了p 从0 到8 连续取值时r 和d 之间的相互制约关系。其中r ( d ) 是在 给定的失真度量方法下有限卢值对应的最小可达互信息晒d ，而曲线的斜率为 4 4 l 。 r ( d ) 的求解可采用b l a h u t - a f i m o t o 算法。该算法中输入参数卢确定压缩信息 晒d 和期望失真之间的平衡关系。算法收敛至忸( d ) 曲线上有限卢值对应的某一 点。其中，曲线依赖于z 值的选择及t - 与x z 间的失真度量方法。 该算法描述如下： 算法2 1b l a h u t a _ r i m o t o 算法 输入： 源分布p 平衡参娄够和收敛参数己 蹦表示r 失真度量函数d 输出： 尺( d ) 值，其中斜率为爹 方法： 1 m - - - 1 2 r ( o ) 一8 ，并随机初始化p 3 d 0 4 r e = m + 1 ： 1 1 第二章相关知识一种优化的顺序i b 文本聚类算法 2 3m 理论 5 p _ “( t l x ) 一螽e 州似，v t 日，坛x 6 p 。“o ) - p ( x ) p 。“ol 破v te t 7 r 。“( d ) - d h ( p ( x ) p 4 “oix ) i ip ( x ) p 。“o ) ) 8 w h i l e 积4 ( d ) 求”1 ( d ) ) 力 m 理论起源于香农著名的率失真理论，率失真理论是在给定的码率下寻求 源随机变量乃- p o 。到压缩变量r 的编码方案，并通过失真度量函数d ( x ，0 ，使 得这种编码所产生的期望失真小于指定的值d 。在公式( 2 9 ) 的基础上，该理论 可形式化表示为， 戳d ) - 卿 ! ! ，僻；d ( 2 - 1 5 ) 、，傩肛“扛舢l d 其中，e ( d ( x ，f ) ) 是以p 傩) 为自变量的d ( x ，力的数学期望【1 1 刀。 率失真理论存在的问题是失真函数的选取缺乏客观性，m 理论通过定义源 变量z 的相关变量y ，推导出了一个客观的失真函数。给定( 弘g ) - p ( x ，力，1 1 3 理论在将z 压缩到r 的同时，使得z 最大化地保存y 的信息；这如同在z 到r 的压缩过程中，z 所隐含的关于y 的信息经由r 得到显露。由于l 研远远小于闪， 这相当于形成了一个细细的“瓶颈”，当将瓶颈一侧的大量数据通过该瓶颈时， 该数据与其另一数据的相关信息得以提炼，这正是m 名称的由来。 该过程可以形象地表示如下【1 7 1 ： 曩暑力一j ；】，) 北j c 耳j f ) 量大化托r ) 图2 5 最小化晒d 与最大化j 仃；d 之间的平衡 其中，x 和t 之间形成映射石一r ，并由条件概率p o k ) 表示，而压缩信息 第二章相关知识一种优化的顺序m 文本聚类算法 j ( 配d 度量相应的压缩性能，相关信息，( 死蹦述压缩过程中保存的有用信息。 图2 - 5 说明：m 方法需要解决最小化晒d 的同时，最大化甄死的的问题。 在实际应用中，为了达到目标，就需要在这两个互信息间取得一个平衡， 也即是在保证相关信息不小于下确界的条件下，最小化压缩信息；或者，在保 证压缩信息不大于上确界的条件下，最大化相关信息。通过引入平衡因子p ， 与率失真问题解决方法一样，上述问题的解决可采用拉格朗日乘数法。 m 方法的形式化推导如下对式( 2 - 1 5 ) 中的d 0 ，0 进行重新赋值得， d 似f ) - d k 0 ( ) ，i 工) 0 p o ，l f ) ) ( 2 - 1 6 ) i b 理论中的变i x , r 和y 形成i bm a r k o v 链【1 1 7 1 ；z x o y ，即：p ( x ，t ， y ) - p ( x ，咖o ，k ，f ) 叩g ，t ) p o , k ) 对式( 2 - 1 6 ) 的期望失真e ( d ( x ，f ) ) 进行推导， e 似 ，f ) ) - e d 。( p ( ) ，i , o i i p o l f ) ) 】 - 磊p ) 茗p o , i x ) l o g 涨 - 稻三一啪) l o g 涨 趟三一p y ) l o g 訾一积三一p o y ，l o g 号尝 - ，暖；y ) - i ( r ；功( 2 - 1 0 用( 2 1 0 改写率失真函数得到， 足( d ) - p 似h m i l 1 f ( r 舢，僻；r ) ( 2 - 1 8 )、p 似n 怛；r ) 一f ( r 舢。 j ( 配的是一个常数，所以( 2 - 1 8 ) n - j 写作， r ( d ) - m i n z ( x ；r ) ( 2 1 9 ) ，似仃舯。 式( 2 - 1 9 ) 说明m 方法是在保证相关信息j ( 死d 不小于下确界d 的情况下， 最小化压缩信息j ( 配d ；该式的求解可采用拉格朗日乘数法，即最小化i b 目 标函数， f m ( p ( f i z ) ) - i ( x ；r ) - f u 口；y ) ( 2 2 0 ) 第二章相关知识一种优化的顺序m 文本聚类算法 其中，是平衡参数，用以平衡源信息的压缩和相关信息的保存。一般地， 0 p * 。在实际的应用中，基于不同的目的，声还可能取0 或设置为m 。 事实上，参数鼠r 和y 之间存在相互制约关系：t 对z 的压缩存在界限： 0 晒力豳。对于相关信息：0 足乃功j ( 孤d 。下限0 对应户加时， r 退化为一个值，并把所有z 值映射到该值的情况。此时，压缩程度最大：晒 d ：o ，但同时也失去了所有的相关信息：j ( 死的= o 两个上限朋国和j ( 配功 对应户一* 时，只保存相关信息的情况。当i 牵闪时，j 口；x ) f f i h ( x ) 和j 仃；y ) = i t x , d ，不存在信息压缩；而当i 水例时必然存在压缩，本文将在4 1 节说明此时m 目标函数的简化处理形式。在实际应用中，需要找到合适的，值，从而有效地 平衡源信息z 的压缩和相关信息y 的保存。 该目标函数的形式解为【1 l p ( tl x ) 一丽p ( oe 】【p ( 一p d , = ( p o , i x ) l lp ( ) ，i f ) ) ) 其中，z ( x ，卢) 墨p ( f ) c x p ( 一声d 碰( p ( ) ，i x ) l l p ( yi ) ) ) ， 归一化函数。 ( 2 - 2 1 ) 是一个概率 由z - 弘y 和相关的概翠公式- j 得， p 0 1 扣高羔p o , i 工) p ( t l 咖( 2 - 2 2 ) p o ) 。三p ( t i x ) p ( x ) ( 2 - 2 3 ) 对比式( 2 2 1 ) ，( 2 2 2 ) 和( 2 2 3 ) 氮i ，( 2 - 2 2 ) 和( 2 - 2 3 ) 是p o 鼢的函数，这样式( 2 - 2 1 ) 中等号右边的变量同样依赖于p ( t 盼，因此( 2 - 2 1 ) 只是一个形式解，问题的最终 求解需要采用上述3 个等式形成的迭代算法。 2 4i b 算法 目前最主要的m 算法有迭代算法l i b 、分裂算法a i b 、凝聚算法d i b 和连 续算法s i b ，本节我们主要介绍i i b 、a i b 和d i b ，s i b 算法放在下一章介绍。 1 4 第二章相关知识 一种优化的顺序m 文本聚类算法 2 4 1 l i b 算法 t i s h b y 等最初给出了解决i b 问题的迭代算法l i b ，并证明了其收敛性【l 】。 该算法的主要思想是：对于确定的值，式0 - 7 ) 、( 3 8 ) 和( 3 - 9 ) 给出了计算各未 知分布的方法。通过在3 个分布集合 p o ，盼 、仞姊坍和伽( f ) ) 之间的反复迭代， 可以得到m 函数的局部最优解假设第m 次迭代得到条件分布p “，则第 m + 1 次迭代时，算法可以进一步修正p ： 1 一南e - r e ) r e b , 删 ( 2 - 2 4 ) 其中，p 4 ( f ) 和矿o ， 的( 更新) 计算如下 、 仁：乏g ， 1 p _ ( yl 加；石( f i 咖“力 m “ 这样就得到了迭代算法i m 。算法伪代码如下， 算法2 - 2i m 算法 输入： 联合分布p o ，力 平衡参数卢 簇数m 和收敛参数己 输出： 一个嬲列肘个簇的不确定( 动的划分l 方法： 1 随机初始化p o 鼢并由等式( 3 - 1 1 ) 找到相应自q p ( f ) 和, 0 0 , 1 0 2 w h i l e ( 存在峨， ”1 ( f i x ) ，p “oi 砌，s ) 3 p “) - g 黯e - l l d a z ( e ( y k ) i l o 0 1 0 ) , v t e t , 忧x 4 p “o ) 1y p ( x ) p - “( fi x ) ，w t e t 5 p “( ) ，协南矿“o i 力p ) , v t e t , 坳乱 6 c n d l i b 算法过程i t 2 - 6 1 7 1 所示：- j - 以看出，l i b 算法实际上是b a 算法的一个扩 充。i l b 算法从其多次随机初始化的运行结果中选择最小化f d 血p o k ) ) = j ；玲 烈死的的解。该算法通过在三个分布的凸集上的反复迭代求解n 。每一步都 第二章相关知识 一种优化的顺序m 文本聚类算法 是在两个集合分布上计算第三个集合上的分布。由于m 函数在这三个集合的乘积 空闯上是非凸的，因此，不同的初始化会对解会有直接的影响【1 l 算法并不能保 证的到一个唯一的解，只能期望得到一个局部最优解。 图2 - 6l i b 算法 i l b 算法在执行时固定了参数户的取值。当，动态取值时，声值决定条件概 率p g 鼢的分布当p + 0 时，p o 鼢在【o ，l 】中取值，并满足概率归化条件， 即z 中每个工映射到r 中所有t 的概率之和都为1 当户一* 时，p ( f 忙) 只在 0 ， 1 中取值，即z 中每个x 以概率1 只映射到r 中某一个值f ，而对其它f 值的归 属概率都为o 。上述分析说明；对于有限的芦值， i l b 算法是不确定的( s o f t ) 聚 类算法。随着参数鼻取值的不断变大，该算法逐渐成为确定的( h a r d ) 聚类算法。 在l i b 算法设计中，簇数肼( = l 嘭可定义为参数芦的正相关函数，使得m 值 可随着声的变化而变化。但是求解过程中参数p 的取值固定不变，这不能动态 改变m 的取值。而且，i m 算法并不能保证解的唯一性，只能收敛到m 函数的 一个局部最优解，这些缺陷给i m 算法的使用带来了局限性。 由于i i b 算法存在的上述问题，s l o n i m 等人使用多种启发式策略对基本的 i i b 算法进行了改进，不仅有效地解决了求解m 函数时m 取值动态变化问题， 而且增强了m 方法的适用性。 2 4 2 d i b 算法 s l o n i m 在【1 7 】中提出了一种自顶向下的层次算法d i b 。该算法是基于模拟 退火思想的m 算法。在初始化时设置夕= 0 ，t 中只有一个值f 且p ) = 1 。d i b 第二章相关知识 一种优化的顺序m 文本聚类算法 算法把p j 看作系统的温度，增加参数，的值相当于对系统进行“降温”；通过 持续地增加参数户的取值，t 中的值不断分裂，该算法最终得到对应不同，值 的树状层次结构，这种结构记录了系统退火过程中得到的解树。 算法2 - 3d i b 算法 输入： 联合分彳砀o ，力 平衡参数口 簇数m 和收敛参数巴 参数4 、e 徊d m i a 输出： 艇0 m = 1 ，肘个簇不确定( s o f t ) 的划分l 方法： 1 声p o 2 和 f ，p ( t k ) = z 3 w h i l e d 栩 4 ，鼍，够，动 5 复制簇： 5 1 对于y t e t ，慨x 5 2 产生随机数r a n d ( x ，t ) 一u 【一 ，l 】，并定 义： 5 3p 瓴i 功一p oi x ) ( 专+ r a n d ( x ，f ) ) ， 5 4 p ( f 2 i 工) - e ( t l x x - r a n d ( x ，f ”， 6 利用复制的簇集合进行初