（计算机软件与理论专业论文）半监督聚类算法及应用的研究.pdf

摘要 摘要 题名：半监督聚类算法及应用的研究 研究生：罗晓清 导师：王士同 专业：计算机软件与理论 聚类是人类一项最基本的认识活动，也是处理数据的重要工具，在许多领域中被广 泛地应用。该文主要侧重于半监督聚类分析的研究，针对现有方法存在的问题，提出一 些新方法和观点。 该文首先对聚类分析做了深入的研究，详细介绍了聚类的发展、研究现状，并在此 基础上对具有代表意义的不同聚类方法进行了总结、比较；定义了与论文研究有着密切 关系的信息论相关知识点以及数据分布和优化理论等概念。接着重点探讨了基于辅助空 问的半监督聚类算法并分析算法的相关性质。 然后将极大熵原理引入半监督聚类方法中实现聚类。提出基于辅助空间与极大熵的 半监督聚类算法a m e s c ，针对该算法中的代价函数进行迭代优化，给出了一个新的聚 类算法。a m e s c 的优势在于它依据模拟退火过程，使算法避开局部极小而得到全局极 小，提高算法性能。 一般来说，无监督聚类仅仅基于主空间。当辅助空间被引入聚类过程时，无监督聚类 成为半监督聚类。在这篇论文中，代价函数的设计既考虑到主空间又考虑到辅助空间，从 而一个新颖的基于辅助空间与主空间合作的的半监督聚类方法a p m s c 被提出。该算法通 过迭代优化，使得相应的代价函数最小化，最终得到有效的聚类结果。 最后，对上述算法做了设计和实现，通过大量实验测试验证了该文提出的算法具有 有效性和优越性。 关键字：聚类分析；半监督聚类；辅助空间；极大熵；模拟退火；主空问 江南大学硕士学位论文 a b s t r a c t t i t l e ：r e s e a r c ho ns e m i s u p e r v i s ec i u s t e ri n ga i g o ri t h m a n di t sa p p ii c a t i o n g r a d u a t es t u d e n t ：l u ox i a o q i n g t u t o r ： w a n gs h i t o n g s u b j e c t ：c o m p u t e rs o f t w a r ea n dt h e o r y c l u s t e r i n gi sab a s i sa c t i v i t yf o rh u m a nb e i n gt ou n d e r s t a n dt h ew o r l da sw e l la sa n i m p o r t a n tt o o lt od e a lw i t hd a t ai no u re v e r y d a yl i f e i th a sw i d ea p p l i c a t i o n si nal o to ff i e l d s i nt h i sa r t i c l ew ef o c u so nc l u s t e r i n ga n a l y s i si nt h es e m i - s u p e r v i s ec l u s t e r i n ga l g o r i t h ma n d p r o p o s ean e wm e t h o do fc l u s t e r i n gi ns e m i - s u p e r v i s eb a s e do nac a r e f u l l ya n a l y s i so f e x i s t i n gm e t h o d si nl i t e r a t u r e i nt h i sp a p e r , f i r s th a sd o n et h et h o r o u 【g hr e s e a r c ht ot h ec l u s t e ra n a l y s i s ，i n t r o d u c e dt h e c l u s t e rd e v e l o p m e n ta n dt h er e s e a r c hp r e s e n ts i t u a t i o ni nd e t a i l ，a n di nt h i sf o u n d a t i o nh a v e c a r r i e do nt h es u m m a r y ，t h ec o m p a r i s o no fc l u s t e rm e t h o dp o s s e s so ft h ed i f f e r e n t s i g n i f i c a n c e ；t h ei n f o r m a t i o nt h e o r yc o r r e l a t i o nk n o w l e d g ea n dc o n c e p t ss u c ha s d a t a d i s t r i b u t i o na n do p t i m i z e dt h e o r yt h a th a st h ec l o s er e l a t i o nw i t ht h ep a p e rr e s e a r c hw a s d e f i n e d t h e nw i t he m p h a s i sh a sd i s c u s s e dc l u s t e ra l g o r i t h mt h a t c l u s t e r i n gb a s e do n c o n d i t i o n a ld i s t r i b u t i o n si na na u x i l i a r ys p a c e a n da n a l y z e dt h i sa l g o r i t h mr e l a t e dn a t u r e ； t h e nt h em a x i m u m e n t r o p ya p p r o a c hi si n t r o d u c e dt os e m i - s u p e r v i s e dc l u s t e r i n g a n da n o v e ls e m i - s u p e r v i s e dc l u s t e r i n ga l g o r i t h ma m e s cb a s e do na u x i l i a r ys p a c e ，m a x i m u m e n t r o p ya n ds i m u l a t e da n n e a l i n g i sp r o p o s e d an e wc l u s t e ra l g o r i t h mi sg i v e n t h i sa l g o r i t h m r e a l i z e st h ee f f i c i e n tc l u s t e r i n gb ym i n i m i z i n gt h ec o s tf u n c t i o ni t e r a t i v e l y o u re x p e r i m e n t a l r e s u l t sd e m o n s t r a t ei t sv a l i d i t ya n ds u p e r i o r i t y i ng e n e r a l ，u n s u p e r v i s e dc l u s t e r i n gi so n l yb a s e do np r i m a r ys p a c e i fa u x i l i a r ys p a c ei s c o n s i d e r e dt o i n c o r p o r a t ew i t hp r i m a r ys p a c e ，u n s u p e r v i s e dc l u s t e r i n g w i l lb e c o m e s e m i s u p e r v i s e dc l u s t e r i n g i nt h i sp a p e r , a u x i l i a r ys p a c ec o m b i n e dw i t hp r i m a r ys p a c ei s i n t r o d u c e dt ot h ed e s i g no ft h ec o r r e s p o n d i n gc o s tf u n c t i o n a n da c c o r d i n g l yan o v e l s e m i s u p e r v i s e dc l u s t e r i n ga l g o r i t h ma p m s cb a s e do nb o t ha u x i l i a r ys p a c ea n dp r i m a r y s p a c ei sp r o p o s e d t h i sa l g o r i t h m r e a l i z e st h ee f f i c i e n tc l u s t e r i n g b ym i n i m i z i n g t h e c o r r e s p o n d i n gc o s tf u n c t i o ni t e r a t i v e l y f i n a l l y , t h i sa l g o r i t h mi sd e s i g n e da n di m p l e m e n t e d t h r o u i g ho u re x p e r i m e n t a lr e s u l t s d e m o n s t r a t ei t sv a l i d i t ya n ds u p e r i o r i t y k e yw o r d s ：c l u s t e r i n ga n a l y s i s ：s e m i s u p e r v i s ec l u s t e r i n g ：a u x i l i a r ys p a c e ： m a x i m u m e n t r o p y ；s i m u l a t e da n n e a l i n g ；p r i m a r ys p a c e h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：、罗盹请日期：渺 7 年 月- 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：翌生亟导师签名： 日期：妒7 年；月伽日 第一章引言 第一章引言 1 1 聚类分析概念 将一组物理的或抽象的对象，根据它们之间的相似程度，分为若干组；其中相似的 对象构成一组，这一过程就称为聚类过程。一个聚类i l 】就是由彼此相似的一组对象所构 成的集合；不同聚类中对象是不相似的。在许多应用中，同类中所有对象常常被当作一 个对象来进行处理或分析。 聚类分析是人类活动中的一个重要内容。人类就是通过不断完善潜意识中的分类模 式，来学会识别不同物体。聚类分析已被应用到许多领域，其中包括：模式识别、数据 分析、图像处理和市场分析等。通过聚类，可以发现整个的分布模式，以及数据属性之 间所存在的有价值的相关关系。 1 2 聚类的研究意义 在日常生活、生产、科研工作中，经常要对研究对象进行聚类。随着计算机技术的 不断发展和计算机应用的深入，聚类分析成为了一种数据划分或分组处理的重要手段和 方法，聚类分析也是数据挖掘中非常重要的研究领域和应用技术之一，它可以对数据进 行无需指导的分类，从而辅助我们的决策。进入九十年代以后，计算机技术和信息网络 技术的发展将人们推入信息社会，社会信息量急剧增加，数据库的规模日益扩大，数据 库的数据总量及容量也急剧膨胀。这些广阔的领域为聚类分析方法的应用以及聚类分析 的研究提供了宽广的舞台。 聚类分析的典型应用主要包括：在商业方面，聚类分析可以帮助市场人员发现顾客群 中所存在的不同特征的组群；并可以利用购买模式来描述这些不同特征的顾客组群。在 生物方面，聚类分析可以用来获取动物或植物所存在的层次结构，以及根据基因功能对 其进行分类以获得更深入的了解。聚类还可以从地球观测数据库中帮助识别具有相似的 土地使用情况的区域。此外还可以帮助分类识别互联网上的文档以便进行信息发现。作 为数据挖掘的一项功能，聚类分析还可以作为一个单独使用的工具，来帮助分析数据的 分布、了解各类数据的特征、确定所感兴趣的数据类以便作进一步分析。当然聚类分析 也可以作为其它算法( 诸如：分类和定性归纳算法) 的预处理步骤。 数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数据挖掘、 统计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用数据库所包含的 数据量越来越大，聚类分析已成为数据挖掘研究中一个非常活跃的研究课题。 聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识 世界就必须区别不同的事物并认识事物间的相似性，而每个概念的最初形成无不借助于 事物的聚类分析。因此，聚类分析的研究不仅具有重要的理论意义，也具有重要的工程 应用和人文价值。 1 3 本文的主要研究内容 聚类分析在发展过程中己经取得了丰硕的成果，然而它距离完美的境界还很远现 有的聚类分析方法尚存在许多问题。 半监督学习是近年来在机器学习领域新发展的一种学习方法，本文主要侧重于对半 监督聚类算法及应用的研究。国外半监督聚类的研列2 】f 3 】1 4 1 1 5 胴开始的比较早，取得了一 江南大学硕士学位论文 定的成果。j a n n es i n k k o n e n 和s a m u lk a s k i 等人在2 0 0 0 年及以后提出了相关的算法 研究，并初步应用与基因、文本等领域，取得了很大的进步。国内也有部分学者正在研 究半监督聚类算法及其应用，相对来说研究工作还比较少。针对现有方法存在的问题， 本文提出一系列新方法和新观点。其研究成果克服了一些现有方法的缺陷，丰富了聚类 分析的理论，具有一定的理论意义与应用价值。 具体的研究内容如下： 一、 首先对聚类算法的原理，基本类型进行了总结，然后重点探索半监督聚类的 算法理论，分析了这种聚类算法的相关性质和特性。 二、研究基于辅助空间的半监督聚类。根据数据特征选取辅助空间，运用相应 的算法进行聚类。 三、 在基于辅助空间的半监督聚类算法中，引入模拟退火思想，将研究得出的 结论应用在某些实验中，并与基于辅助空间的半监督聚类算法比较，从而在实践中证实 本文结论的正确性以及优越性。 四、研究主空间和辅助空间相结合的半监督聚类，将算法应用到实践中，证实 该算法的优越性与有效性。 五、最后对研究成果进行分析、总结。 1 4 论文结构 按照研究的内容，本文共分6 章，安排如下： 第l 章：绪论。首先从选题意义和背景的角度介绍了聚类以及聚类分析算法的发展 状况，然后阐明本文的研究成果和内容安排。 第2 章：聚类算法中的基本知识。概述了聚类的发展状况，目前研究的成果，不同 聚类的算法比较，叙述了部分聚类算法的内容。 第3 章：基于辅助空间与极大熵的半监督聚类算法研究。描述了基于辅助空间的半 监督聚类算法，说明了模拟退火的基本思想，并提出了基于辅助空间与极大熵的半监督 聚类算法，而且在理论研究的基础上制定了该聚类分析的步骤，给出目标函数。制定聚 类评价标准，通过实验验证了该算法的合理性。 第4 章： 基于辅助空间与主空间合作的半监督聚类方法研究。一般来说，无监督聚 类仅仅基于主空间。当辅助空间被引入聚类过程时，无监督聚类成为半监督聚类。在基 于辅助空间与主空间合作的半监督聚类方法研究中，代价函数的设计既考虑到主空间又 考虑到辅助空间，从而一个新颖的基于辅助空间与主空间合作的的半监督聚类方法被提 出。陔算法通过迭代优化，使得相应的代价函数最小化，最终得到有效的聚类结果。通 过实验证实了基于辅助空间与主空间合作的的半监督聚类方法的有效性和优越性。 第5 章：结束语。对本文存在的问题和研究不足加以说明。总结研究成果并对下一 步需要完成的工作进行了展望。 2 第三章基于辅助空间与极大熵的半监督聚类算法 第二章聚类分类算法介绍 聚类分类是人类认识未知世界的一种重要的认知手段。在生产和生活中，人们往 往面对非常复杂的事和物，如果能够把相似的东西归为一类，有明显区别的事物分属在 不同的类别中，处理起来就大为简便。所谓“物以类聚，人以群分”，说的就是这个道 理。譬如人们将生物分为动物和植物，又根据不同的生理特点将生物分为不同的门、纲、 目、科、属、种；在化学理论中，人们根据不同的化学性质将各种元素划分为不同的类 别，比如卤族元素、惰性气体等等，进而总结出元素周期率；在社会学中，人们还根据 不同的信仰划分出不同的党派、宗教等。 在机器学习中，聚类分析属于一种无( 教师) 监督的学习方法。与分类学习不同， 无( 教师) 监督学习不依靠事先确定的数据类别，以及标有数据类别的学习训练样本集 合。正因为如此，聚类分析又是一种通过观察学习方法( 1 e a r n i n gb yo b s e r v a t i o n ) ， 而不是示例学习( 1 e a r n i n gb ye x a m p l e ) 。在概念聚类方法中，仅当一组对象可以由 一个概念所描述时，这些对象方才能构成一个类。这与基于几何距离表示相似程度并进 行聚类的传统聚类方法有所不同。概念聚类方法主要包含两部分内容：( 1 ) 发现适当 的类；( 2 ) 根据每个类形成相应的特征描述，与在分类学习中的方法类似。无论如何 最大程度地实现类中对象相似度最大，类间对象相似度最小是聚类分析的基本指导思 想。 在研究论文中有许多聚类算法。需要根据应用所涉及的数据类型、聚类的目的以及 具体应用要求来选择合适的聚类算法。如果利用聚类分析作为描述性或探索性的工具， 那么就可以使用若干聚类算法对同一个数据集进行处理以观察可能获得的有关( 数据特 征) 描述。 通常聚类分析算法可以划分为以下几大类：u i 8 】【9 】 2 1 划分方法 算法：根据聚类中的均值进行聚类划分的k m e a n s 算法。 输入：聚类个数k ，以及包含n 个数据对象的数据库。 输出：满足方差最小标准的k 个聚类。 处理流程： ( 1 ) 从n 个数据对象任意选择k 个对象作为初始聚类中心； ( 2 ) 循环( 3 ) 到( 4 ) 直到每个聚类不再发生变化为止； ( 3 ) 根据每个聚类对象的均值( 中心对象) ，计算每个对象与这些中心对象的距离； 并根据最小距离重新对相应对象进行划分； ( 4 ) 重新计算每个( 有变化) 聚类的均值( 中心对象) ； 如上述算法所示，k - m e a n s 算法接受输入量k ：然后将n 个数据对象划分为k 个聚 类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相 似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”( 引力中心) 来进行计算的。 k - m e a n s 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为初始 聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度( 距离) ，分 3 江南大学硕士学位论文 别将它们分配给与其最相似的( 聚类中心所代表的) 聚类；然后再计算每个所获新聚类 的聚类中心( 该聚类中所有对象的均值) ；不断重复这一过程直到标准测度函数开始收 敛为止。一般都采用均方差作为标准测度函数，具体定义如下： e - ：，隅p m ；1 2 ( 2 1 ) 其中e 为数据库中所有对象的均方差之和；p 为代表对象的空间中的一个点；慨为聚 类c 的均值( p 和肌。均是多维的) 。公式( 2 1 ) 所示聚类标准旨在使所获得的t 个聚 类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。k m e a n s 算 法的计算复杂度为d ( n 幻) ，因而它在处理大数据库时也是相对有效的( 具有可扩展性) ； 这里n 为对象个数；七为聚类个数；而f 为循环次数。通常有| | 厅和f 0 ，则有b a y e s 公式： 椰) 一揣 眨e ， 设有两个总体g 1 和g 2 ，从使得误判概率最小的角度，我们可以使用如下的判别规则： z g 1 ，若p i g l i 爿g ，i x i z g ：，若尸( g ：阻) p ( g ，i x ) ( 2 7 ) 待判，若p i g l 防 一p l g ，i xj b a y e s 公式的特点是利用以往对研究对象的认识一先验概率来辅助判断，以期得到更 精确的分析结论。它在使误判概率或风险最小的意义上是最佳的，但是b a y e s 分类器需 要已知条件概率，而且其决策面往往是超曲面，形状复杂，难以计算和构造。 线性判别函数法 实际问题往往遇到决策面是线性的( 直线或者超平面) ，计算和构造都很简单，因 此即使遇到决策面不是线性时，我们也宁可牺牲错误率最小这个最优原则，努力构成线 性函数。 对于图2 - 4 所示的两类分类问题，线性分类法的目标就是寻找一条直线： g ( x ) t w 7 x + ，这条直线能够能够尽可能地将两类样本分开。f i s h e r 线性判别函 数是一个经典的判别方法。它的核心思想是进行坐标变换，寻找能将样本尽可能分开的 方向。考虑把，l 维空间的样本投影到一条直线上，形成一维空间，为了避免投影后不 同样本混杂在一起，不易区分，可以将直线转动，寻找一个方向使样本的投影尽量分开， 也就是说，使得类间差异尽可能大，类内差异尽可能小。 在有些情况下，比如多峰分布，每类是由几个相距较远的团组成，直接采用线性分 类函数来进行分类，错判率就会很大，可以考虑采用分段线性分类法降低错判率。形象 地看，在多峰分布下，分类决策面是一个超曲面，可以采用类似折线的分段线性函数来 逼近超曲面。c h a n g 法就是实现分段线性分类的一种手段，但是它需要事先根据先验知 识确定线性判别函数的数目，这一点常常不容易满足。 图2 - 4 两类分类问题 距离函数法和最近邻判别法 模式分类中最简单直观的方法就是基于距离函数的分类法。它的核心思想是使用一 8 第三章基于辅助空间与极大熵的半监督聚类算法 类的重心来代表这个类，计算待分类样本到各类重心的距离，归入距离最近的类。在判 别分析中常采用马氏距离，因为马氏距离既考虑了类的均值，又包含了类内方差的信息， 对训练样本中蕴涵的信息利用得比较充分。采用马氏距离的基本假设是各类均为正态总 体。 如果允许类中全部样本点都可有资格作为类的代表的话，这就是最近邻法。最近 邻法不是仅仅比较与各类均值的距离，而是计算和所有样本点之间的距离，只要有距离 最近者就归入所属类。 为了克服最近邻法错判率较高的缺陷，k 一近邻法不是仅选取一个最近邻进行分类， 而是选取k 个近邻，然后检查它们的类别，归入比重最大的那一类。 支持向量机 传统统计学理论是在样本数目趋于无穷大时的渐进理论，在训练样本数有限的情况 下效果不是很好。1 9 9 5 年，v y a p n i k 对小样本统计学习理论进行系统化，并在此基础上 发展了一种通用的学习方法一支持向量机( s ：s u p p o r tv e c t o rm a c h i n e ) 。 s y m 的基本思想是使用简单的线性分类器划分样本空间。对于在当前特征空间中线性不 可分的模式，则使用一个事先选择的非线性映射把样本映射到一个高维空间中，在这个 空间中构造最优分类超平面。 势函数法 势函数法采用“拟物”的思路，将特征空间中的点视为物理空间中的点。每个样本 点都看作一个能量源，在该点上电位达到峰值，而随着与该点距离的增大，电位分布迅 速减小，换句话说，把样本空间中的电位分布看作一个势函数p ( x ) 。构造合适的势函数， 使得在一类样本点周围形成“高地”，在另一类样本点周围形成“低谷”，在两类电位 分布中问选择合适的等位线，作为分类的判别函数。势函数法在一些实验样例中取得很 好的结果。 9 江南大学硕士学位论文 第三章基于辅助空间与极大熵的半监督聚类算法 根据学习的不同可将聚类算法分为2 大类：有监督学习和无监督学习。有监督学习 必须对所有的学习样本做类别标记，通常需要大量的学习样本。无监督学习是一种自动 学习方式，并不需要对学习样本做类别标记，但在不提供监督信息的情况下，学习得到 的模型是不够精确的。而半监督学习是介于两者之间的学习方式，兼顾两者的优点，能 够同时处理标签数据和非标签数据，从大量的混合数据中发现规律。它为现代数据集的 分析提供了很好的途径，丰富了聚类算法，能够对许多新的领域提出一些新的观点。 在半监督聚类算法研究中提出了一种基于辅助空间条件分布的半监督聚类方法 a m s c l 。该算法中数据符合v m f 分布。每个样本事先不知道分类。经研究表明同类样本 具有相似的相关信息。比如说：同类基因具有相似的功能，同类文本具有相似的关键字。 因此引入辅助空间对数据进行监督和限制，提高聚类的准确性。使用这种聚类方法，有 一个前提，那就是样本必须具备对应的辅助信息，只有满足这个条件才能使用辅助空间 半监督算法。在聚类的过程中主空间( 即样本空间) 的拓扑结构并没有被破坏。在算法中 样本是一对主空间和辅助空间组成的数据集0 。，c a ) ，通过数据集构造代价函数，迭代优 化使得代价函数达到最小，实现聚类。 3 1 基于辅助空间的半监督聚类算法 3 1 1 信息熵 信息与信息科学是两个常见的名词，它们的内容十分广泛，尤其在当今的信息社会 中，有着十分重要的意义与丰富的含义。哲学家把信息与物质、能量并列，作为构成世 界的三大要素之一，并成为推动当今社会文明与发展的主要因素。没有信息，世界将变 得杂乱无章。但是，什么是信息? 信息的数学本质是什么? 信息如何度量等问题一直是 人们所关心的。人们迫切需要信息的理论基础。 信息论1 8 1 1 1 0 l 的产生以1 9 4 8 年香农的奠基性论文为标志，至今已有5 0 多年的历史。在 这5 0 多年中，以信息论为理论基础，电子、通信与计算机技术经历了大规模的发展，造 就了无处不在的信息社会。同时，信息论也得到发展和广泛的应用。信息论以数学方法 度量并研究信息，通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量 的大小，它包括一系列重要的概念。 假设一个信源工为一个一维随机变量，工可能出现的符号为集合 如，4 ：，吼，口， 的元素，其中，表示符号的个数。 ( 1 ) 信息量 在收到a ；之前，收信者对信源发出口；的不确定性定义信息符号口；的自t 言, g ：1 1 ( a ；) 。 即，q 。) 1 0 9 p ( a ，) ，其中p 0 。) 为信源发出口；的概率。 ( 2 ) 信息熵 自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源x 整体的不确 定性，关于一个随机变量取值的概率分布的函数。其定义如下： 1 0 第三章基于辅助空间与极大熵的半监督聚类算法 日( x ) = p ( a ，) ，妇。) + p ( 口：) ，仁：) + + p 0 ，) ，仁，) 一一v ( a 。) l o g p ( a ；) ( 3 1 ) w 用信源每发一个符号所提供的平均信息量来定义信息熵。 ( 3 ) 条件熵 在通信中由于干扰的存在，经常出现差错。由于干扰的随机性，收信者收到的信息 含有随机量。如果信源为x ，收信者受到信息为随机变量l ，x 与y 相关。那么，用条件 熵日( 石y ) 来度量收信者在收到随机变量y 之后，对随机变量z 仍然存在的不确定程度。 设x 对应的信源符号吒，y 对应的信源符号岛，几) 为当y 为包时x 为q 的概率， 则有 n ( x l y ) 。蓦套币；6 a o g p g ；户，) ( 3 2 ) ( 4 ) 互信息 假设有两个不同变量的概率分布p ( 4 ；) ，p 够，j 。互信息是指在获得一个变量的知识 时，对另一个变量的不确定性减少的量。也表示对j ，y 之间统计依存程度的信息度量。 ，( z ，y ) 。p ( 4 z ，6 ，) 1 。g j i p ：( 丽a i , b i ) ( 3 3 ) 比如说今天随机事件北京下雨和随机变量空气湿度的相关性就很大，但是和姚明所 在的休斯敦火箭队是否能赢公牛队几乎无关。互信息就是用来量化度量这种相关性的。 上面的公式显示：互信息就是联合概率分布p k ，6 ，) 与各自概率分布乘积 尸仁；) p 够，j 之间的相对熵。刻划两个事件之间的相互依赖的程度。 1 如果，0 ，) ，) o 则x f f 町y 是高度相关的。 2 如果，b ，y ) 一0 ，则x 和y 是独立的。 3 如果，0 ，y x ( o , 则x 和y 是互补分布的。 x f f 于c l ( x ，y ) - o ，的情形，很难判断x ，y 之间的关系。 ( 5 ) 平均互信息量 用它来表示信号l ，所能提供的关于x 的信息量的大小，用，( ，l ，) 表示 i ( x ，y ) 一日( 盖) 一h ( x y ) 。 1 1 江南大学硕士学位论文 3 1 2k u l l b a c k - l e i b l e r 距离 k u l l b a c k l e i b l e r 距离【8 】【9 】【1 川：用于衡量两个分布之间的距离( 亦称相对信息 r e l a t i v ei n f o r m a t i o n 在有些文献中它被称为成“相对熵”、“交叉熵”。) 。是以它的两 个提出者库尔贝克和莱伯勒的名字命名的。广泛地应用在信息理论、统计物理学、经济、 统计分析、形态分析、模式识别、语音识别等领域。 对于两个离散随机变量x 和y 来说，如果要度量它们之问有多大的相似程度，可以 使用s h a n n o n 信息论中的互信息函数，其定义为 ，僻，m p g l o g 。p o t , 1f ( 3 4 ) r i ri 式中只是x 的概率分布，弓是】，的概率分布，弓是x 和y 的联合概率分布值，只弓 是工和l ，相互独立时的联合概率分布值，满足只弓- 1 ，f 一1 ，2 ，n ；j - 1 ，2 ，m 。 互信息给出了两个随机变量x 和y 相互包含对方的信息量，即两个随机变量中所包含的 共有信息。当1 ( x ，l r ) = o 时，意味着x ，y 相互独立，i ( x ，y ) 值越大，表明两个变量之 间的相似性程度越高。 两个概率分布p 一协唐一1 ，以 和q = q , i i 。1 ，n 的k u l l b a c k k i b l e “k l ) 距离定 义为 d 豇) 。；p 山g 詈 ( 3 _ 5 ) 当用弓和弓分别替换只和吼，有，( z ，y ) 一d 。( ( p ，q ) l k p q ) ) 。可见s h a n n o n 的互 信息表达式度量是关于x 和1 ，的联合概率分布只，和边缘概率分布的积只p j 之间的k l 距 离。从严格的数学意义上讲，k l 距离不是真正的距离，因为它不满足于距离定义的对称 性和三角不等式关系，因此从概念上讲，它是一种广义的距离。k l 距离在信息理论、信 号处理、模式识别等方面有着广泛的应用。 在信息论中，有一个与s h a n n o n 熵相关的著名的不等式，称作s h a n n o n 不等式 罗p f l o g p l 罗p i l o g q j ( 3 6 ) 77 当且仅当p = q 时等式成立，p ，q 的意义与上式中相同。从s h a n n o n 不等式中可以看 出，k l 距离是s h a n n o n 不等式左右两项之差，即 d n 陋) 。；n - 鸭詈p ll o g p i - ；p j l o g 吼 ( 3 7 ) 第三章基于辅助空间与极大熵的半监督聚类算法 3 1 3 优化算法 所谓最优化问题8 l 【9 1 ，就是在满足一定的约束条件下，寻找一组参数值，以使某 些最优性度量得到满足，即使系统的某些性能指标达到晟大或最小。最优化问题的应用 可以说涉及工业、社会、经济、管理等各个领域，其重要性是不言而喻的。 最优化问题根据其目标函数、约束函数的性质以及优化变量的取值等可以分成许多 类型，每一种类型的最优化问题根据其性质的不同都有其特定的求解方法。 不失一般性，设所考虑的最优化问题为 m j n 盯一，( r )s 1 x e s - i x i g f ( x ) 0 ，一1 ，m ( 3 8 ) 其中，口- ，何) 为目标函数，g j 僻) 为约束函数，s 为约束域，z 为玎为优化变量。 通常最大化问题很容易转换为最小化问题o - 一，( x ) ) ，对于g ；( 工) 之0 的约束和等式约 束也可转换为一g ，( 工) s 0 的约束，所以式( 3 8 ) 所描述的最优化问题不失一般性。 当，( z ) 、g ，( x ) 为线性函数，且彳苫0 时，上述最优化问题即为线性规划问题， 其求解方法有成熟的单纯形法和k a m a r c 方法。 当f ( x ) 、g ，( x ) 中至少有一个函数为非线性函数时，上述问题即为非线性规划问 题。非线性规划问题相当复杂，其求解方法多种多样，但到目前仍然没有一种有效的适 合所有问题的方法。 当优化变量x 仅取整数值时，上述问题即为整数规划问题，特别是当x 仅能取0 或l 时，上述问题即为0 - 1 整数规划问题。由于整数规划问题属于组合优化范畴，其计 算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。 当g ，( x ) s 0 ( ，一1 ，m ) 所限制的约束空间为整个n 维欧式空间，即掣时，上述最 优化问题为无约束优化问题，即 m i n o 一，暖) s t z e s c r 。( 3 9 ) 非线性规划问题( 包括无约束优化问题和约束优化问题) ，由于函数的非线性，使 得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解 非线性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或 无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。 局部优化算法 定义：如果存在x ；b ，使得对惯口有 f ( x ；) ，( x ) ，x 口 ( 3 1 0 ) 成立，其中b c s r 4 ，s 为由约束函数限定的搜索空间，则称x ；为，俾) 在b 内的局 部极小点，i ( x ；) 为局部极小值。 江南大学硕士学位论文 常见的优化方法大多为局部优化方法，都是从一个给定的初始点x 。s 开始，依据 一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止准则。 成熟的局部优化方法很多，如n e w t o n r a p h s o n 法、共轭梯度法、 d a v i d o n f l e t c h e r p o w e r ( d f p ) 法、b r o y d e n f l e t c h e r g o l d f a r b s h a n n ( b f g s ) 方法等， 还有专门为求解最小二乘问题而发展的l e v e n b e r g m a r q u a r d t ( l m ) 算法。所有这些局 部优化算法都是针对无约束优化问题而提出的，而且对目标函数均有一定饿解析性质要 求，如n e w t o n r a p h s o n 法要求目标函数连续可微，同时要求其一阶导数连续。 对于约束非线性优化问题，除了根据一阶最优化必要条件直接将最优化问题转换为 非线性代数方程组，然后采用非线性代数方程组的数值解法进行求解外，还有序列线性 规划法、可行方向法、拉格朗日乘子法等。最常用的方法是将约束问题通过罚函数法转 换为无约束优化问题，然后再采用无约束优化方法进行求解。 全局优化算法 定义：如果存在x e s ，使得对镪e s 有 ( x ) ( x ) ，x e s ( 3 1 1 ) 成立，其中s r “为由约束条件限定的搜索空间，则称x 为( x ) 在s 内的全局极小点， f ( x ) 为其全局极小值。 已发展成熟的最优化方法大多为局部优化方法，其求解结果与初始值相关。对于目 标函数为凸函数、约束域为凸域的所谓凸规划问题，局部最优与全局最优等效。而对于 非凸问题，由于在约束域内目标函数存在多峰值，因而其全局最优与局部最优相差甚远。 全局优化问题已存在了许多算法，如填充函数法等。真正有效且具有普遍适应性的 随机全局优化算法，是近十多年来人们模拟自然界的一些自然现象而发展起来的一系列 仿生型智能优化算法，如模拟退火方法、进化类算法、群体智能算法等。 3 1 4v u f ( y o nu i s e s f i s h e r ) 数据分布 由于算法以数据满足v m f 分布设计，所以首先介绍v m f 分布的相关知识。 t h ev o nm i s e s f i s h e r ( v m f ) 3 1 1 1 1 1 1 1 2 1 分布是最常见的方向性数据分布。它类似与 在超球面上多维的高斯分布。n 维v m f 分布的概率密度函数如下： v m f ( x ；o ) - 赤唧七寄 1 2 ) 该函数中，参数向量0 代表平均方向向量，v m f 分布中心位置由它确定。分布的宽度 由参数k 确定。因此称0 为位置参数，k 为尺度参数。正则化系数是： z 。 ) t ( 2 x ) 一2i 。 ) 。1 ( 3 i s ) 7 1 ， ) 为第一类b e s s e l 函数。 1 4 第三章基于辅助空问与极大熵的半监督聚类算法 下图为0 = o ， k e o ，o 3 , 1 , 4 ，2 0 ) 时的v o nm i s e s f i s 脏r 分布密度图 i 。 妻 舣 ，t 一+ 4 、 -4a- zlolz3 图3 - 1 不同k 值对应的v o nm i s e s f i s h e r 分布密度图 从上图可以看出，v o nm i s e s - f i s h e r 分布中心位置由参数0 确定，分布的宽度由参 数k 为尺度参数。明显地可以得出当k = o 时v o n m i s e s - f i s h e r 分布收敛于均匀分布，而 v m f 分布收敛于s “1 球面的均匀分布，当七一m 时v o nm i s e s f i s h e r 和w f 分布都退化为 0 处的单点分布。 在本文的聚类算法中，我们使用v m f 核函数， ， ；岛) 一o c 7 0 1 l l o , i i ( 3 1 4 ) 设k 为常量，那么 掣嘶俐i i o , 1 1 2 ) i i o , i i ( 3 1 5 ) 模慨并不影响，在我们归一化b 后，上述求导可变为： o f ( i x ；o o k ( x - x 7 0 , o d ( 3 1 6 ) a 口， 3 1 5a m s c 算法描述 向量量化( v o ) t 7 l t 8 l 或者k - m e a n s 聚类，都是分类的方法。在v q 中，目标是使数据和原 型或码书( 向量m j ) 之间的平均失真最小化。定义如下： e 。p j ( x ) d ( x ，m d p ( x ) a ， ( 3 1 7 ) j 上式中，x 表示样本，根据某种相似性度量，样本被分为k 个子类，用( v 。，v ：，h ) 表示各类中一1 5 , ，v ，e r 。( j = 1 ，2 ，k ) 。样本d o ，m ，) 指工* a m 之间的距离度量， y ， ) 是聚类隶属度函数，满足o y j g ) 1 ，y ，o ) 1 1 。 在典型的硬向量量化中 j 该函数是二进制值：) ，o ) = 1 如果d o ，r a ，) to ( x ，m i ) ，否则y o ) 2 0 该函数把空间划 分为离散单元，也就是v o r o n o i 区域，学习的目的是找到使平均失真最小的划分方式。 江南大学硕士学位论文 如果隶属度函数) ，( d 能够取0 1 之间的任意值，我们把这种情况称为软向量量化。 在a m s c 算法中，距离度量采用的是k u l l b a c k - - l c i b l e r 距离，定义两个离散分布的 事件概率为 以) 和 识。k - l 距离的形式为： ，矿) ；p tl 。彤；) ( 3 1 8 ) 在a m s c 中，d 是指p ( c i 力和模型分布之间的不同第一个分布是x 对应的辅助 空间多项式分布。也就是毋- p ( c ；i x ) ，它表示样本z 出现c ；这个信息的概率。第二 个分布就是中心或称原型，我们标记第j 个原型为乃，- p ( c f l v ，) ，表示聚类v ，出现 q 这个信息的概率。 当把k u l l b a c k - - l e i b l e r 失真度量方式插入到v q 代价函数( 3 1 7 ) 中，公式变为如下 形式： 五k - p ，o ) d n o ( ci 石