（计算机应用技术专业论文）基于免疫网络的文本挖掘方法研究.pdf

摘要 隧着i n t e r n e t 的飞速发展及其在全世界范围内的普及和应用 网络上存储了 海量豹信息资源 这些信息资源数量与霹俱增 戈其以w e b 页面为载体的文本 数据里爆炸式的增长并越来越成为人们关注的主要信息来源 如何从数量庞大 的文本信息中快速有效地发现知识已经成必人们迫切震耍解决的闯题i 近年来 针对文本数据的挖掘已经成为人们重点研究的课题 其中对文本的聚类研究引 起了广泛的重褫 本文蓄先介绍了文本挖掘的研究背景和发展现状 对文本挖掘中的文本聚 类算法的相关技术进行讨论 针对文本表示模型 特链词提取 特征向量降维 及文本相儆度的计算等与文本聚类密切相关的关键技术进行了描述与分析 在 次基础上展开文本聚类算法的研究 实现文本聚类算法的动态适应性是当翦文本聚类算法研究的重要方翔之 一 本文在研究人工兔疫网络 a i n e t 模型的基谶上 结合文本聚类的特点 对a i n e t 算法进行改进 实现了基于a i n e t 的文本聚类算法 为实现文本的动态 聚类提供了一种新的解决思路 为克服基于a i n e t 麴文本聚类算法在处理高维数据时性能下降的缺点 本文 研究了免疫遗传概铡和k m e a n s 聚类算法 将免疫遗传萼l 入k m e a n s 算法优纯聚 类中心 提出 种基于免疫遗传的k m e a n s 文本聚类算法i g a k 有效避免了经 典k m e a n s 算法易受初始聚类中心选择不当魄影响丽陷入局郝最优的缺点 在此 基础上设计了一种基子聚类中心酌虚拟坐标映射机制的文本表示模型 实现了 文本向量模型的降维技术 结合该虚撅坐标向量模型 定义了抗体 抗原 亲 和力 相似度等概念 提出一种融合免疫遗传k m e a n s 和a i n e t 的两阶段文本聚 类算法i g a k a i n e t 最后 设计并实现了一种文本聚类模型 给凑了模型的主要模块设计 必 要的数据结构和部分代码 应用相关文本数据进行了对比实验 实验结果表明 新算法具有较强懿动态适应性 改善了聚类康量 关键词 文本聚类 向量空间模型 遗传免疫 k 均值聚类算法 人工免疫网 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e ta n di t sw o r l d w i d ep o p u l a r i t ya n d a p p l i c a t i o n i ts t o r e dl a r g eq u a n t i t i e so fn e t w o r ki n f o r m a t i o n r e s o u r c e sa n di t s n u m b e ri si n c r e a s i n g i np a r t i c u l a r t e x td a t a t ow h i c ht h ew e bp a g e sa r et a k e na s t h ec a r r i e r a r ep r i m a r yi n f o r m a t i o ns o u r c ea n db e c o m em o r ea n dm o r ep o p u l a r w i t h w h i c ht h en u m b e ri s g r o w i n ge x p l o s i v e l y t h ep r o b l e mo fh o wt o d i s c o v e r k n o w l e d g eq u i c k l ya n de f f e c t i v e l yi nah u g en u m b e ro ft e x tm e s s a g e sr e q u i r e s r e s o l v i n gu r g e n t l y i nr e c e n ty e a r s t h et e x td a t am i n i n gh a sb e c o m eak e yr e s e a r c h t o p i c i n w h i c ht h er e s e a r c ho nt e x tc l u s t e r i n gh a sg e n e r a t e dc o m p r e h e n s i v e a t t e n t i o n t h i sp a p e rf i r s t l yh a si n t r o d u c e dt h ed i s q u i s i t i v eb a c k g r o u n da n dc u r r e n ts t a t u s o fd e v e l o p m e n to nt e x tm i n i n g a n dd i s c u s s e dt h er e l e v a n tt e c h n i q u et ot e x t c l u s t e r i n ga l g o r i t h mi nt e x tm i n i n g b e w r i t t e na n da n a l y s e dt h ek e yt e c h n o l o g y c l o s e l yr e l a t e dt ot e x tc l u s t e r i n g i n c l u d i n gt e x te x p r e s s i v em o d e l f e a t u r e se x t r a c t i o n d r o p d i m e n s i o no ff e a t u r e sv e c t o ra n dt h ec a l c u l a t i o no ft e x ts i m i l a r i t ya n d i n s u c c e s s i o n t h er e s e a r c ho nt e x tc l u s t e r i n ga l g o r i t h mi so u t s p r e a d e do nt h ea b o v e b a s i s a c h i e v i n gt h ed y n a m i ca d a p t a b i l i t yo ft e x tc l u s t e r i n ga l g o r i t h mi so n eo ft h e i m p o r t a n td i r e c t i o n b a s e do nt h es t u d yo f a r t i f i c i a li m m u n en e t w o r k a i n e t m o d e l c o m b i n e dw i t ht h ec h a r a c t e r i s t i c so ft h et e x tc l u s t e r i n g t h i sp a p e r h a si m p r o v e dt h e a i n e ta l g o r i t h ma n dr e a l i z e dat e x tc l u s t e r i n ga l g o r i t h mb a s e do na i n e t w i t hw h i c ha n e ws o l u t i o n si sp r o v i d e dt oa c h i e v et h ed y n a m i ct e x tc l u s t e r i n g i no r d e rt oo v e r c o m et h es h o r t c o m i n g so fp e r f o r m a n c e d r o po ft e x tc l u s t e r i n g a l g o r i t h mb a s e d o n a i n e ti nd e a l i n gw i t hh i 曲一d i m e n s i o n a ld a t a t h i sp a p e r h a s s t u d i e dt h ei m m u n eg e n e t i cm e c h a n i s m sa n dk m e a n sc l u s t e r i n ga l g o r i t h m a n d i n t r o d u c e dt h eg e n e t i ci m m u n ei n t ok m e a n sa l g o r i t h mt oo p t i m i z ec l u s t e rc e n t e r p u tf o r w a r dat e x tc l u s t e r i n ga l g o r i t h mb a s e do nt h ei m m u n eg e n e t i ca l g o r i t h ma n d k m e a n sc a l l e di g a kf o rs h o r t t h i sa l g o r i t h me f f e c t i v e l ya v o i dt h es h o r t c o m i n g t h a tt h ec l a s s i ck m e a n sa l g o r i t h mi sv u l n e r a b l et ou n d u ei n f l u e n c eo fu n a p ti n i t i a l c l u s t e rc e n t r e sa n dp l u n g e si n t oal o c a lo p t i m u mp r e m a t u r e l y o nt h eb a s i so fi g a k t h i sp a p e rh a sd e s i g n e da nt e x te x p r e s s i v em o d e lw h i c hi sb a s e do nc l u s t e rc e n t e r s w i t hv i r t u a lc o o r d i n a t e m a p p i n gm e c h a n i s m t od r o p t e x tv e c t o rd i m e n s i o n s 珏 t e c h n o l o g y w i t ht h ev i r t u a lc o o r d i n a t e sm o d e l t h ec o n c e p ts u c h a sa n t i b o d i e s a n t i g c n s a f f i n i t y 鼬m i l a r i t yh a sb e e nl i s t e d a n dat w o s a g ct e x t c l u s t e r 主n 叠 a l g o 鳓黼b a s e d i m m u n eg e n e t i c a l g o r i t h mk m e 黼sa n da i n e lc 娥d i g a k a i n e tf o rs h o r t l n a j j y as 姗p l e 蚓c l u s t e r i n gm o d e lb a s e do nt h e n e wa l g o r i t h mh a sb e e n 程 s 2 9 程 露a n di m p l e m e n t e di n c l u d i n gt h em a i n m o d u l e 嚣e c e s s 鑫f yd a 捻s 张c 嚣f c 鑫珏d p a r to ft h ec o d eh 鹬b e e nd e s i g n e d t h ec o m p a r e d e x p e r i m e n t sw e r cc a 谢e do u tw i t h t n ea p p l l c a t i o no ft h er e l e v a n tt e x td a t a a n d t h e e x p e r i m e n t a lr e s u i t ss h o wt h a tt h e n e wa l 驴黼m h a s 辍r o n gd y n a m i ca d a p t a b i l i t y a n d i th a si m p r o v e dt h eq 龇l i l yo f k e yw o 州s t e x tc l u s t e r i n g v e c t o rs p a c em d e l k m 蚀飘s a r t i f i c i a il m m m l e n e t w o r k a i n e t i i i 长沙理工大学 学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任 何其他个人或集体已经发表或撰写的成果作品 对本文的研究做出重要贡 献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的 法律羼果由本人承担 作者签名 稳韵 日期 彬牌歹月 gb 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留 使用学位论文的规定 同意 学校保留共向国家有关部门或机构送交论文的复印件和电子版 允许论文 被查阅和借阅 本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存 和汇编本学位论文 本学位论文属于 1 保密口 在 年解密后适用本授权书 2 不保密口 请在以上相应方框内打 作者签名彳众铱了 新馘p t 氐 导师签名 也k i 甜 日期 鹏年岁月缪日 日期 占叼莎年ff j 罗日 第一章绪论 1 1 研究背景及意义 1 1 1 研究背景 随着i n t e r n e t 的飞速发展及其在全世界范围内的普及和应用 网络上存储 了海量的信息资源 这些信息资源数量与日俱增 形式不断变化 内容丰富而 繁杂 笼其是随着互联网络的普及和发展 以w e b 页面为载体的文本数据呈爆 炸式的增长 如何从大量的 杂乱无章的 强平扰的数据 海量数据 中挖掘 潜在的 有利用价值的信息 有用知识 这给人类的智能信息处理能力提出了 前所未有的挑战 由此产生了人工智能研究的一个崭新领域 数据挖掘 d a t a m i n g 和数据库知识发现 k d d 目前比较公认的数据挖掘定义是 数据挖掘就是从大量的 不完全的 有 噪声的 模糊的 随机的数据中 提取隐含在其中的 人们事先不知道的 但 又是有趣的 潜在有用的信息 模式 知识的过程秘 数据挖掘是信息技术自然 演化的结果 它是一种从大量数据中挖掘出隐禽的 先前未知的 对决策有潜 在价值的知识和决策的技术 数据挖掘自9 0 年代产生以来 其研究已经比较深 入了 研究范围涉及关联规则挖掘 聚类规则挖掘 预测分析 孤立点分析 演变分析等方面 数据挖掘所获取的信息和知识已经得到广泛应用 如商务管 理 生产控制 市场分析 工程设计和科学探索等等 另一方面 随着信息化时代的到来 作为人们传递信息的桥梁 i n t e r n e t 起 到了极大的作用 随着i n t e r n c t 的迅猛发展 掰络已经发展成为拥有几个亿的页 愿且还在不断扩张的分布式信息空间 其中包括了从技术资料 商业信息到新 闻报道 娱乐信息等大量异质 非结构化的信息 甚至有工业分析人士认为非 结构化数据占了企业信息资源的8 0 而数据库中的数据仅占2 0 然两以上这些研究基本上都是基于结构化数据 比如事物数据库等 报少 有工作研究异质 非结构化数据妇q 因此 扩大数据挖掘研究对象的范围 更 多的研究非结构化数据 如视频 文本 网络页面 e m a i l 等 成为数据挖掘的 一个新的研究方向 由此网络挖掘 文本挖掘 多媒体挖掘便应运而生 文本挖掘 t e x tm i n i n g 是数据挖掘的研究志容之一 它也称为文档挖掘 d o c u m e n tm i n i n g 文本数据挖掘 t e x td a t am i n i n g 以及文本 数据库 中的知识发现 k n o w l e d g ed i s c o v e r yi nt e x t u a ld a t a b a s e 文本挖掘属于数据挖 掘这一交叉学科了的一个具体领域 二者既有联系又有区别 数据挖掘的对象 是结构化的数值信息 以便发现不同数据属性的关联规则 对记录进行聚类及 分类处理 是构造数据的预测模型 而文本挖掘的主要任务是分析文档数据库 的内容 发现文档数据集中概念 文档之间的相互关系和相互律用 为用声提 供相关知识和信息 对文本挖掘的理论 体系结构 算法和功能 不同的学者有不同的理解 一般认为文本挖掘是指在大量文本集合或语料上 发现其中隐含的 令人感兴 趣的 有用的模式和知识秘 大多数作用于数据库中的知识发现功能 例如 依 赖关系分析 分类 聚类 偏差检测等 在文本挖掘中都能够或者有可能被实 现 显然这种定义将文本挖掘视为数据挖掘从有结构到文本的一种跳跃 或者 说文本挖掘是数据挖掘的一个特殊的应用或方面 它涉及文档集合的预处理 中闰形式的处理 分类 聚类 趋势预测 关联规则等 以及结果的可视化蝤 因此 可以认为 文本挖掘作为数据挖掘的一个研究分支 其研究内容涉及数 据挖掘 自然语言处理 计算机语言学 信息检索及分类 知识管理等多个领 域 将获取的知识应用于相关领域可以有效地改变相应系统的性能 是一个综 合性的交叉学科婀 在技术上综合了数据库 人工智能 机器学习 统计学 并 行计算 神经网络 信息检索 数学理论等不同领域中的技术 文本挖掘的一种是文本聚类 聚类是根据数据集中数据的不同特征 将其 划分为不同的数据类别 簇 使褥属于网一类别的数据个体之闻的相似度尽可 能的大 而不同类别中的个体间的相似度尽可能小 用少数的几个类代表整个 数据集虽然会丢失数据集的一些细节信息 但这样简化了数据集的表示 而聚 类分析则涉及许多研究领域 诸如数据挖掘 统计学 生物学以及机器学习等 众多领域 其实 聚类分析是一种重要的人类行为 早在孩提时代 一个人就 通过不断地改进下意识中的聚类模式来学会如何区分各种常见的动物和植物 目前聚类分析已应用于许多方面 包括模式识别 数据压缩 图像处理 声音 处理 以及市场分析等等 通过聚类 人们能够识别密集的和稀疏的区域 从 而发现全局豹分布模式 以及数据属性之间有趣的相互关系 因此 由聚类分析的行为可以推知 文本聚类是一个将文本集分组的全自 动处理过程 每个组里的文本在一定方面互相接近 如果把文本的内容作为聚 类的基础 不同的组剐与文本集中不同的主题相对应 文本聚类是一个发现文 本集包含内容的方法 近年来 可以很容易地从i n t e r n e t 数字图书馆 新闻机 构和公司内部网上获得数目惊人的文本文档 于是 人们对发展能够帮助用户 有效地导航 总结和组织这些文本信息技术的兴趣越来越强 快速和高质量的 文本聚类技术在实现这个目标过程中扮演了重要的焦色 逶过将大量信息组织 成少数有意义的簇 这釉技术能够提供导航 浏览机制 或者 通过聚类驱动的 降维或权值调整来极大地改善检索性能 因此 文本聚类研究成为当前国际上 数据挖掘的一个重要课题 2 l 2 研究意义 文本是信息资源存在的一个主要形式 薤对这样一个信息海洋 人们往瓮会 陷入窘迫的境地 一方面收到太多的信息无从选择和消化 淹没在繁杂的信息 海洋中 另一方面是信息迷失 入们难以找到自己真正需要的信息 因此 人 们都追切要求能够快速高效的获取自己需要的信息 及藤对大量的信息自动地 提取其概念空间 提供给人一个清晰的框架 帮助人们进行信息的检索和分类 则显得尤为重要 围绕文本信息这一资源开展的各种学术研究和业界应用非常 活跃 如各种搜索弓i 擎 数字图书馆 电子商务等 这些研究已经取得令人可 喜的成果 但是在一定程度上人为予预的成分比较大 效果不能谴人满意 需 要将数据挖掘技术引入到文本检索和分类的领域中去 而文本聚类作为文本挖 掘的基础工作则显得尤为重要 同时利用计算机对海量的文本信息进行聚类及 类别标示 也是文本挖掘自身的需要 为迸一步进行其他途经的挖掘提供了很 好的利用效果 好的文本聚类方法有利于信息资源的合理存储 也能够为人们 准确 精确 快速的检索信息提供了方便 大大减少信息搜索的时间开销和节 约入力资源 利用文本挖掘 可以对大量文档集合的内容进行总结 分类 聚类 关联 分析 趋势预测等 1 文本总结 文本总结是指从文档中抽取关键信息 用简洁的形式对文档 内容进行摘要或解释 其冒的是对文本信怠进行浓缩 给出它的紧凑描述 这 样 用户不需要浏览全文就可以了解文档或文档集合的总体内容 2 文本分类 分类是在已有文本的基础上学会一个分类函数或构造出一个 分类模型 即通常所说的分类器 一般将预先分类过的文档作为训练集 从训 练集中得出分类模式 霈要测试过程 不断细化 用导出的分类模式对其它文 档加以分类 3 文本聚类 文本聚类把一组文档按照相似性归成若干类别 方法大致可 分为层次聚类法 平面翔分法 k m e a n s 算法 简单贝叶斯聚类法并1 k 一最近邻 参照聚类法 分级聚类法 基于概念的文本聚类等 4 自动文摘 自动摘要 利用计算机自动地从原始文档中提取全面准确地 反映该文档中心内容的简单连贯的短文 5 趋势颈测 趋势预测是指通过对文档的分析 得到特定文本数据在某个 历史时刻的情况或将来的取值趋势 文本聚类则可以帮助用户有效的导航 总结和组织文本信息 可提供对大 规模文本集合的内容的概括 识别隐藏的共同点 使找到相近或相关的浏览程 序简单化 3 文本知识发现搜索器可以使用聚类挖掘搜索结果表的结构 文本聚类可以 将w e b 的搜索结果组成主题层次挝 让浏览文本和寻找兴趣变得更容易 应用 在w e b 挖掘中可以改善网络搜索性能阳q 们 也可以采用有监督聚类改进文本分类 技术n 卜谨1 应用于电子商务系统中组织信息驱动引擎n 引 还可以应用于文本自动 综述系统中进行文本的自动综述n 蜡1 等 综上所述 文本挖掘可以应用到诸如信息检索 搜索引擎 数字图书馆 电子邮件过滤等众多领域 因此 对文本挖掘进行研究具有重要的理论意义和 实用价值 本文旨在通过研究现有的文本聚类算法 在此基础上提出 种新的 文本聚类算法 同时 随着中国经济的迅速发展 中国在世界上的影响力不断壮大 对大 规模的中文文本信息的研究和处理对我国经济的发展和民族文化在世界范围的 传播也具有现实积极意义 1 2 文本聚类研究现状 文本聚类是将研究对象的相似空间距离指标按照相似性准则划分到若干个 子集中 空间聚类应遵循紧凑性和分离性要求 即一个好的空间聚类应该使各聚 类中心的闻距尽可能地大 丽样本与其中心间距尽可能地小h 1 文本聚类的应 用非常广 比如在地球科学 信息技术 决策科学 医学 行为学和商业等领 域中都有应用 对文本聚类算法的研究早在2 0 世纪6 0 年代就开始了 但是受 当时条件限制并没有多大发展 直到2 0 世纪9 0 年代才逐渐引超人们注意 并 取褥了重大突破 在九十年代中期 文本聚类主要使用层次聚类的方法 这种方法利用相似 度 s i m i l a r i t y 或者称为距离 d i s t a n c e 来衡量文本数据之间或者簇 c l u s t e r 之 闻的关系 从而决定聚类的过程 在这种算法中的每一步 都要估算现有数据 对象之闻的相似程度 并且根据相似程度来进行合并 从而形成新簇 算法的 最后 将得到一个树状的层次结构 其中的每一层代表着聚类过程中簇的变化 情况 这样的方法虽然能够很好的表现聚类的过程 但是存在着两个问题 第 一 方法中关予裰似度的选择是至关重要的 因为它直接影响到聚类的过程和 结果 但是 实践证明并没有某一种相似度的度量方法能够很好的适用于所有 类型的数据 所以相似度如果选取不当 就会影响到聚类的结果 第二 虽然 这种方法能够有效地处理数据 并且能够用树状结构反映聚类过程的各个阶段 但是 这种方法在每一次进行合并之前都要进行全局比较 计算所有已经存在 的簇与簇之间的相似程度 并选择最佳的两个簇进行合并 因此运行速度较慢 并不适合处理大规模文档集合n 们 典型的代表主要是c u r e b i r c h r o c k 等 4 另一种比较常见的文本聚类方法是平面划分聚类 p a r t i t i o n a lc l u s t e r i n g 这 种方法首先按照某种原则 把数据集合划分成为若干个初始簇 所有的文本数 据被分配到不同的簇中 然后根据一个优化算法在簇之间调整文本的归属 使 簇的分布更具合理性 即使得簇内文本的相似程度较高 磊簇间文本的相似程 度较低 这种方法的时间复杂程度要低于层次方法 但是聚类的结果在很大的 程度上要依赖于簇的初始情况 典型的代表是k 均值算法和k 中心算法等 k m e a n s 聚类算法是解决聚类分析问题的一种经典算法 它具有算法简单 局部搜索麓力强且收敛速度快的特点 正是这些特点决定了k m e a n s 算法非常 适合于离维文本向量的聚类问题 然而在使用k m c a n s 算法聚类的过程当中 给定k 值后 通常初始聚类中心是随机选择的 这种选择方法往往使同一类别 中的样本被强行缝作为不同类别的聚类中心 这样将使得聚类划分发生偏离 也就说k m e a n s 算法存在两个缺陷 对于随机的初始值选取可能会导致不同的 聚类结果 即容易陷入局部最优 聚类数k 必须是事先给定n 刀 为了解决k m e a n s 算法对初始聚类中心敏感的问题 合理选择初始聚类中 心 人们寻求各秘方法对k m e a n s 算法进行改进 这些改进主要集中在初始中 心的选择方法以及对聚类结构的合理利用方面 其中最简单的措施是随机选取 不同的初始值多次执行算法 然后选取最好的结果 文献 1 8 提出将聚类均值点 与聚类种子相分离的思想 在进行下一轮聚类种子计算时 采用簇中那些与上 一轮聚类种子相似度较大的数据 计算它们的均值点 几何中心点 终为下一轮聚 类的种子 傅景广n 引 吕强瞻们 s a n g h a m i t r ab a n d y o p a d h y a y 乜门提出的g k m 聚类 算法中 把编码中的染色体基因值对应类别的中心 这样可以避免样本数增加 染色体阕比例增加的缺点 但仍然必须事先给定聚类数k 适应度函数的构造也 是类内距的倒数 文献心钉则提出7 一种基于密度和对象方向的k a d d 改进算法 采取聚类对象分布密度方法确定初始聚类中心 然后根据对象的聚类方向来发 现任意形状的簇 杨善林澄 m a l a y 臻q 重新构造了k m e a n s 算法中的目标函数 使类内距最小 类间距最大 并证明了类别数的上界七 缉g 常用 昀庐有 布尔涵数 平方根函数 对数飚数 t f i d f 函数 兰 摇端 妒一厮两 驴 l o g 班 d 1 驴 班p 1 g 盟 穆 2 3 2 4 2 5 2 6 其中 n 为所有文档的数目 n i 为禽有词条t i 的文档数目 在信息检索和 文本机器学习中被频繁采用的文档表示方法叫做t f i d f 向量表示法 下面对该 方法进行介绍 t f d i f 向量反映了训练文档集的单字空闻 它的每个向量分量对应一个单 字 分量的大小d i 为t f w i d o c 与i d f w i l o g d d f w i 的乘积 其中t f w i d o c 为单字w 在文档d o c 中的出现频度 d 为总文档数 d f w i 为单字w 在 其中渤现至少一次的文档的数目 d i 亥l j 画了单字w 区分文档内容属性的麓力 一个单字在文档集中出现的范围越广 说明它区分该文档属性的能力越低 另 方面 它在一个特定的文档中出现的频度越高 说明它在区分该文档内容属 性方面的能力越强 另外在v s m 中要注意几个基本概念 1 文档 d o c u m e n t 文档泛指一般的文本或文本中的片断 包括段落 旬群或句子 般指一 篇文章 也可以是多媒体对象 在本文中对文本与文档不加以区潮 2 项 t e r m 1 6 文档的内容特征常常用它所含有的基本语言单位 比如字 词或短语等 来表示 这些基本的语言单位统称为项 即文档可以用项集 t e r m l i s t 表示为 d t 1 t 2 t 3 t n 其中t l c 是项 1 k n n 为文档中项的个数 曾从信息论的角度绘出 了一个统一的 与痘用领域无关的相似度的冀羹形式纯定义 他们认为 a 与b 之间的相似度一方面与它们的共性相关 共性越多 相似度越高 另一方面与 它们的区别相关 区别越大 相戳度越低 当a 与b 完全相同时 楣似度达到 最大值 因此 要掇据系统的其体实现去罨找合适的定义 实际上 在不同的具体应用中 相似度的含义也有所不同 文本相似度计 算将包括以下几种关系 词语与词语 词语与句子 词语与段落 旬予与句子 甸子与段落和鬏落与段落等 上述豹各种相骰度关系可分嬲用于不同的研究领 域 例如 在基于实例的桃器翻译中 相似度主要翊于衡量文本中词语的可替换 程度 在信息检索中 相似度更多的是反映文本与用户查询在意义上的符合程 度 在自动问答中 相似度反映的是句子之间语义上的匹配程度 丽在多文档 文揍系统中 穗儆度可竣反欧擦局部主题信息嚣数合程度 j 舞苏文本相叛度计 算的研究适用范围较广 是信息处理技术中一项基础性的研究 虽然没有通用的相似度定义方法 但是在实践中也形成了一些划分方法 根据相似度在相似算法中的级别不同 相似度可以分为 局部相似度和整 体相似度 文本的相似度是以局部相似度为基础的 层层递进 即文本的相似 度以旬子的相似度为基础 句予的相似度以词语的相似度隽基础 丽词语的褶 似度又可以看作以义原为基础 一旦文本的局部相似度计算出来以后 系统就 可以在此基础之上 计算出两个文本之间的整体相似度 知识对于相似度的定义和评估起着重要的作用 根据相似度所体现的知识 含量的不同 相似度大体可分为表层的基于句法的相似度和深层的基予语义的 相似度 表层的基于句法的相似度属于知识贫乏型相似度 根据文本的表层句 法等属性进行相似度的计算 深层的语义相似度属于知识密集型相似度 要对 文本进行较深层的语义分析 同时要有大量的知识比如语义词典等来进行语义 分析 从而计算出语义相似度 人们曾提出众多的文本相似度计算方法 但是最佳的文本相似度计算方法 并不存在 相似度的计算对不同的应用有不同的要求 有文本级 句子级 词 语级和语素级等不同的级别 相似算法常常表现为相似度计算的公式或者模型 相似度算法应具有以下的四个性质 1 自反性 词语 句子等与其本身是相似的 2 单调性 相似度应该连续的增加或者减少 3 对称性 如果a 和b 相似 则b 和a 也是相似的 4 传递性 如果a 和b 相似 b 和c 相似 则a 和c 相似 但是通常情况下 相似算法并不具有传递性 如果a 和b 相似 b 和c 相 似 则无法判定a 和c 相似 这是因为计算a 和b 相似度的予项与计算a 和c 相似度的子项是不同的 如果对a 和b 进行相似分析和比较 将系统a 和b 具有相同属性或特性两 两对应组成相似元 相似元用强一 口 熟 表示 当系统a b 间存在着推个相似元 1 u 2 c u t 豁 时 则将这撵个相似元以集合矽表示为 其中 岣一 口 趣 0 篡吨s 1 坞一0 表示两系统对应元素既不相同也不相似 0 9 毪 l 当表示两系统对应元素处于其袍情况 碜一l 当表示两系统对应元素完全相阕 经典文本相似度计算方法主要有基于向量空间模型的t f i d f 方法 基于汉 明距离的文本相似度计算方法 1 基于向量空闻模型的t f i d f 方法 向量空间模型 v s m v e c t o r s p a c em o d e l 在前文已有详述 这里我们针对 在向量空间模型中 如何计算文本的相似度进行研究 如前所述 在v s m 中 将 文档肴作是由相互独立的词条组 墨 互 霉 乙 构成 对于每一词条霉 根据 其在文档争的重要程度赋以一定的权值珲 并将夏 乏 霉 乏看成 个n 维坐 标系中酶坐标轴 敝 哎 氍为对应静坐标值 这样由援 乏 霉 毛 分解丽 得的难交词条矢量组就构成了 个文档向鬣空间 文档则映射成为空间中的一 个点 对于所有文档和用户查询都可映射到此文本向量空间 用词条矢量 蔹 磁 是 氍 霉 嘿 乏 我 来表示 鬣设用户查询着q 被检索文档麓d 两 者的相似程度可用向量之间的夹角来度量 夹角越小 说明相似度越离 慕于向量空间模型的t f i d f t e r mf r e q u e n c yi n v e r t e dd o c u m e n tf r e q u e n c y 方法被广泛逸雳来诗算文本之阕的相似度 t f i d f 方法综合考虑了不同豹词在 新有文本中的出现频率 t f 值 帮这个词对不露文本的分辨麓力 i d f 值 假 设所有文本中包含的词为噬 毗 睨 则每 个文本都可以用一个糟维的向量 t 媛 t 霉 t 来表示 其中 l 1 i 炼挥 的计算方法为 设n 为在这个文 本孛逛现鳃个数 m 为其它所有文本孛含有的文本翡个数 罄隽文本鹩总数 那么霉一糟x l o g 哆么 从这个式子中可以看出 出现次数多的词将被赋予较高的 露值 毽这样獒词并不一定具有较高翦爹值 铡鲡 在汉语中 的一出现的频率 菲常离 即零f 值 踺值 很大 健由于g 的 在很多文本中都出现 窀对于我稍 分辨备个文本并没有太大的帮助 它的i d f 值 1 0 9 将是一个很小的数 医就 这静方法综合缝考虑了一个词薛出现频率和这个词对不阕文本的分辨瑟 力 词的权值计算用下面的公式 词的文档内频率矿 毛 哦 可以直接由d o c l t e m 豹f r e q u e n c y 项读取 嚣文档阗频率莛粥可以通过w o r d l i s 魏d o c f r e q u e n c y 读出 词的权值计算公式 n 为文本集包含的文本个数 为 f f i d f j 一矽 j 2 7 用同样的方法 可以计算鼹标文本的一维向量得到z 和r 后 它们所对应的 两个文本之闻耜似度就可鞋f 和爹 这秀个囱量之蠢夹惫的余弦僮来表示 有许多 种计算相似度的方法 常用的福似度计算方案有内积 d i c e 系数 j a e c a r d 系数 和余弦系数等 竣文本t 一瓴 是 毒 嚣 t 互 翼l j f 与z 之阗的相似 度用上述方法分剐表示如下 内积 d i c e 系数 j a c c a r d 系数 余弦系数 s 妇仃 r 2 善互呸 2 8 蚍邳 善罂 亿9 善1 2 善1 2 s 妇p z r 三至至兰 2 善霉2 善矿一善霉呸 s 锄仃 t 1 1 1 z 霉呸 2 11 向量空间模型的最大优点在于它在知识表示方法上的巨大优势 在该模型 中 文本内容被形式化为多维空间中的一个点 通过向量的形式给出 把对文 本内容的处理简化为向量空间中向量的运算 使问题的复杂性大为降低 但是 基于向量空间模型的t f i d f 也有不足之处 首先 只有当文本所包含的词语足 够多时采用该方法效栗才会比较好 因为它是一种基于统计的方法 只有当文 本包含的词数多时 相关的词才会重复出现 这种统计的效果才会体现如来 其次 t f i d f 方法只考虑了词在上下文中的统计特性 而没有考虑词本身的语义 信息 因此具有一定的局限性 芷如c o r n e l l 大学的s a l t o n 教授所说 利用余弦 夹焦获得向量相似度的方法没有严格的理论根据 2 基于汉明距离的文本相似度计算方法 上面描述方法都是利用欧氏空间的概念 把文本描述成空间中的向量 荐 在向量空间中定义诸如内积等运算 由此来定量地描述文本之闻的相似度 基 于汉明距离的文本相似度计算方法借助编码理论中汉明距离的概念 透过求文 本与查询式之间的汉明距离 来计算文本的相似度 与其它方法相比较 它具 有运算简便等优点 在信息论中 汉明距离是一个基本的概念 它是描述两个拜长码字 x 一瓴 屯 气 与y 一 y y 2 欺 以 之间的距离 计算公式为 z 一薹黾 垓 其中 表示模2 加运算 气 1 儿 1 o x y 表示两码字在相同位置上不同码符号的数目的总和 它能够反映两 码字之闻的差异 进而提供码字之间的相似程度的客观依据 对予文本来说 可首先根攒相关的信患 如文本中的关键词 文携等信息 排列成一个有 位序列的码字 文本的信息就用这些码字表示 使文本与码字建 立一一对应关系 同样地 查询式也用码字表示 比如文本w 1 它可表示为 啦一 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 查询式f 一 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 在这里0 和王分 别表示相对应的文本信息的状态 0 表示文本在这分量位置上的信息是没有的 1 表示文本在这一分量位置上的信息是有的 反之也可以类似规定 因此 对于 原来的文本集合 它哥以一一对应于码字的集合 研究文本集合中的文本相似 关系 就用码字之间的汉明距离来表征 具体地 设文本嵋的对应码字为膨 查询式的对应码字为m 则这两个码字的汉明距离 可用上面的公式计算 它 较好恐反映了文本之间的相互关系 对于d m m 来说 它们之间的距离贪于 0 与栉之间 当文本与查询式用h 位码字表示完全不同时 距离值为栉 当文本 与查询式的码字完全相同时 则它们的距离为0 它定量地摧述文本之间的差异 程度 下面讨论基于汉明聚类的相似度计算方法 首先确定文本集对应的码字集 对于不同的文本 或文本与查询式之间 设m 1 一瓴 屯 毛 m 2 y l 托 魏 魏 刚m 和膨 之间的相似度计算 公式为 s 触 小翌竺 2 1 2 露 其中x k 和n 分别表示文本彤对应的码字膨 和查询式 对应的码字膨 中 第k 位的分量 要么为0 要么为1 o 就是模2 加运算 对于计算机来说 模2 加运算j 常方便 可以达到极快的速度 用上面的公式计算文本相似度是合理的 首先 它的计算结果介子o 与l 之间 当两个文本完全相似时 s i m m m 的值为1 当两个文本完全不相似时 值为0 它确实反映了文本之闻的差异 丽量也与传统的欧氏空闻中求向量夹角 余弦的方法相一致 例如设文本磁对应的码字为 m 1 1 0 1 0 0 1 l1 0 0 文本暖对 应的码字为m 0 1 1 0 0 1 1 0 1 0 码字长均为1 0 位 则根据公式计算得到文本噬 和职之闻盼相似度为s i m m m 1 0 4 0 6 这说明这两个文本之间的相似程 度为0 6 也就是说 它们其中的6 个位置上的信息是一致的 相似度函数定量 描述了文本之溺的差异性 与基于赢量空阐模型文本相似发计算方法穗毙较 该方法只是利用模2 加 等运算 完全避开了在欧氏空间中求相似度的大量乘法运算 因此 计算速度 较快 其次 它跳出了传统的借用空澜的理念 藤是焉码字的方法来表征文本 信息韵特征 可以不仅限予关键字等孤立的信息 这为联合的描述文本的信息 提供了可能 如何提取文本的信患特征并排成笱文本一一对应的码字集舍 是 运用该方法的关键和滩点 霈要进行进一步的研究 2 4 本耄小结 本章首先介绍了一般数据结构的聚类算法 然蜃奔缓了常用文本聚类及其 傀缺点 最艨重点对文本魄表示模型 特 歪提取和特征降维及文本相儆度的计 算等技术采用的方法进行了详细介绍 为本文以后的工作做好基础 第三章基于人工免疫网络的文本聚类研究 人工免疫系统是基于生物免疫系统功能特性的启发而设计的各种工程应用 方法的总称 免疫系统最重要的功能特性就是多样性识别能力 增强学习机制 和联想记忆枫制 这些优良特性弓 起了人们极大的兴趣 入们不仅逶过各种手段 对这些特性的枧理进嚣深入研究和探讨 嚣且在这些特性祝理的窟发下设计出 多种形式基于免疫的系统 用来解决许多工程领域中的难题 并且取得了令人鼓 舞的成采 d ec a s t r o 提出一种名为a i n e t 的人工免疫网络 并将其应用于数据聚 类 获褥了良努的效采 本章对a i n e t 文本聚类进行分析研究 提出改进的a i n e t 文本聚类算法 3 1 人工免疫网络聚类研究 3 网络模型定义与描述 假设彤态空间s 是多维度量空闻 每一个轴代表一个刻画分子形状特征的 物理化学度量 假设 个秃标识模式集合x 一敬 毛 善一鼍乏 每一 个而模式用 个变量描述 刻画一个分子结构 作为一个点s e s 因此 在一 个s 舭中 点规定确定a b a ba g 蠢参交互侔用所必要的特征可激描述为一令 数学表示的艺维向量 系统内的可能交互作用谜以表示为连接图形式 该网络模 型正式定义为 定义 a i n e t 楚一个边界加权墨 无需全都连接 也称为细臆的节点组成 的集合 节点对集合称为边界 每一个连接的边界具有一缀分配的权或者连接 强度 狲 斗 l l 争 晰 4 4 篷3 1 原始数攒集合缀残浆嬲络结将嚣3 2 由免疫辩络产生的瓣络结构 a i n e t 是进诧的 嚣为 基于一个群体蠹酌遗传变异和选择 用进化策略控 心唪心 制网络动态和可塑性 它是连接的 因为需要定义一个连接强度矩阵度量网络 缨照之闻熬亲窝力 溺络孛聚类援撑蠹影像 囊责映辫数据集合孛的聚类到嚣 终 如图3 圭掰示 一个矮设酌瘸络维梅毒a i n e t 产生 如匿3 2 新示 给窭 细胞袭示和连接强度 虚线表泳连接应被剪除 为了检测聚类和定义最终的网 络结构 注意网络细胞数比数据样本数少 刻画一个适合数据压缩的结构 另 癸 鬻络燕模是塞动定支蘸 豫f a r n e r 窝j e r n e 提塞大酌模壁一样 在鏊缨燕黧 抗体之闻不作区涮 a g a b 亲和力通过其闯的距离度餐 裙应地 a b a b 亲藕 力通过他们之间的相似度来度撰 笥免疫舞络一样 翳终中的揽薅缨骢簧黠抗器进行竞争识裂 那些竞争残 璃的缨胞就会零l 器瓣络活纯帮缀脆扩增 巍隆选择 那些失败静缨艇就会被清 除 另外 a b a b 识别导致网络抑制 在模型中 抑制通过清除自体识别的细 胞进行