（计算机科学与技术专业论文）基于非结构化数据的多类型网络构建研究.pdf

1 独创性( 或创新性) 声明 本人声明所警交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：毒锺日期：2 玉：主晕 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文注释：本 学位论文不属于保密范围，适用本授权书。 本人签名：幽： 日期： 导师签名：二弘迳兰扛日期： 2 厘：主：2 沁 f 母 声 络构建技术相结合，采用中文信息处理技术抽取非结构化数据中包含 的信息，并构建网络进行分析，进一步挖掘其潜在信息。 分析复杂网络在不同领域的应用，其主要包括两个阶段：网络构 建与网络分析。网络构建是指从实际应用数据中，建立个体之间相互 联系，构建关系网络。这是复杂网络应用的基础与关键。因此本文将 以非结构化数据为对象，研究利用中文信息抽取技术构建多类型网 络。 首先，本文对文本聚类进行研究，并将其应用到数据集划分中， 将数据集划分不同领域或主题的子数据集。通过对传统文本聚类的实 现与分析，将复杂网络中的社区划分算法应用文本聚类中，实现基于 社区划分算法的文本聚类，并取得一定的效果。 其次，本文采用中文信息抽取技术抽取非结构化数据包含的实体 相关信息。由于网络构建中边的重要性，本文主要对实体关系抽取进 行研究。对传统的无监督聚类实体关系抽取算法中的实体对上下文信 息收集以及实体对聚类两阶段进行改进，更快、更好的抽取非结构化 数据中包含的实体关系。同时针对单文档以及稀疏文档集，本文实现 了基于事件框架的实体关系抽取，以抽取用户指定的特殊实体关系。 再者，通过比较复杂网络在不同领域的应用，分析与总结出常用 的网络类型，即同质、异质、动态网络。根据非结构化数据的信息元 素的多维性，从不同的视角与维度出发，构建了文档一文档关系网络、 文档一实体关系网络、实体一实体关系网络以及动态网络。 最后，设计并实现多类型网络构建原型系统，将本文中的研究内 容融入其中。分别对各研究内容与原型系统进行实验，以验证其有效 性。 关键词：复杂网络网络构建实体关系抽取文本聚类 一 h f ；纠， d 一 t h er e s e a r c ho fm o d e l i n gm u i j i n e t w o r k s b a s e do nu n s t r u c t u r e dd a i a a b s i r a c i w i t ht h ed e v e l o p m e n to fe n t e r p r i s ei n f o r m a t i z a t i o na n dt h ei n t e r n e t ， t h ea m o u n to fu n s t r u c t u r e da n ds e m i s t r u c t u r e dd a t ai n c r e a s e i nr e c e n t y e a r s ，t h er e s e a r c ha b o u tt h ed a t am i n i n gb a s e do nt h eu n s t r u c t u r e da n d s e m i s t r u c t u r e dd a t ab e c o m eo n eo fr e s e a r c hf o c u s e s t h el a t e s tr e s e a r c h r e s u l t si nc o m p l e xn e t w o r ka n dc h i n e s ei n f o r m a t i o np r o c e s s i n gp r o v i d e u san e wp e r s p e c t i v et om i n ei n f o r m a t i o nf r o mt h eu n s t r u c t u r e da n d s e m i s t r u c t u r e dd a t a ，w h i c hi sm e r g i n gt h ec o m p l e xn e t w o r ka n dc h i n e s e p r o c e s s i n g i n f o r m a t i o n t e c h n o l o g y f i r s t l y t h ec h i n e s ei n f o r m a t i o n p r o c e s s i n gt e c h n o l o g y i su s e dt oe x t r a c ti n f o r m a t i o nf r o mt h e u n s t r u c t u r e da n ds e m i - s t r u c t u r e dd a t a ，t h e nm o d e lt h en e t w o r k sb a s e d t h o s ei n f o r m a t i o na n da n a l y z et h e m t h r o u g ha n a l y z i n ga n dc o m p a r i n gt h ec o m p l e xn e t w o r ka p p l i c a t i o n i nd i f f e r e n tf i e l d s ，i tm a i n l yc o n t a i n st w op a r t s ：n e t w o r km o d e l i n ga n d n e t w o r ka n a l y s i s n e t w o r km o d e l i n ga n a l y z et h ed a t aa n df i n dt h e c o n n e c t i o na m o n gt h ei n d i v i d u a l st om o d e lan e t w o r k ，w h i c hi st h eb a s i s a n dt h ek e y i nt h i sp a p e r , w ew i l lr e s e a r c ha n du s ec h i n e s ei n f o r m a t i o n p r o c e s s i n gt om o d e lm u l t i n e t w o r k sb a s e do nt h eu n s t r u c t u r e dd a t a f i r s t l y , i nt h i sp a p e r , w e w i l lr e s e a r c ht e x tc l u s t e r i n ga n da d o p ti tt o d i v i d et h ed a t a s e tt os o m es u bd a t a s e t sw h i c hb e l o n g st od i f f e r e n tf i e l d s t h r o u g ha n a l y z i n ga b o u tt r a d i t i o n a lc l u s t e r i n gm e t h o d s ，w ep r e s e n tt h e t e x tc l u s t e r i n gb a s e do nt h ec o m m u n i t yd e t e c t i n ga l g o r i t h m s ，a d o p ti tt o c l u s t e rt h et e x td a t a sa n dh a v eg o o de f f e c t s e c o n d l y , i nt h i sp a p e r , w ew i l lr e s e a r c ht h ec h i n e s ei n f o r m a t i o n e x t r a c t i o nt e c h n o l o g yt oe x t r a c tt h ee n t i t i e sf r o mt h eu n s t r u c t u r e dd a t a o w i n gt ot h ei m p o r t a n to fe d g e si nt h en e t w o r km o d e l i n g ，w em a i n l y r e s e a r c ht h ee n t i t yr e l a t i o ne x t r a c t i o n w ec h a n g et h et w os t e p so ft h e u n s u p e r v i s e dr e l a t i o ne x t r a c t i o nm e t h o dt oe x t r a c tt h ei n f o r m a t i o nf a s t e r a n db e t t e r , t h a ta r ec o l l e c t i n gt h ec o n t e x t sa b o u tt h ee n t i t i e sc o - o c c u ra n d n c l u s t e r i n gt h e s ec o n t e x t s m e a n w h i l e ，t oa n a l y z i n gs p a r s ed a t a s e t ，w e i m p l e m e n tt h er e l a t i o ne x t r a c tm e t h o db a s e do ne v e n tf r a m et oe x t r a c tt h e s p e c i a lr e l a t i o n sw h i c h u s e r ss e t t h r o u g hc o m p a r i n gt h ea p p l i c a t i o no fc o m p l e xn e t w o r ki nd i f f e r e n t f i e l d s ，w ef i n dt h ec o m m o nn e t w o r k si n c l u d eh o m o g e n e o u sn e t w o r k ， h e t e r o g e n e o u sn e t w o r ka n dd y n a m i cn e t w o r k s ow e 。w i l l b u i l dt h e n e t w o r k sf r o mt h ed i f f e r e n t p e r s p e c t i v e s a n dd i m e n s i o n so ft h e u n s t r u c t u r e dd a t a t h o s en e t w o r k sc o n t a i nd o c u m e n t d o c u m e n tr e l a t i o n n e t w o r k ，d o c u m e n t e n t i t yr e l a t i o nn e t w o r k ，e n t i t y e n t i t yr e l a t i o nn e t w o r k a n dd y n a m i cn e t w o r k f i n a l l y , w ed e s i g na n di m p l e m e n tap r o t o t y p es y s t e mt om e r g et h e r e s e a r c hf o c u s e so ft h i sp a p e r , t h e ne x p e r i m e n ti tt ov e r i f yt h ev a l i d i t y k e y w o r d s ：c o m p l e xn e t w o r k ，n e t w o r km o d e l i n g ，e n t i t y r e l a t i o n e x t r a c t i o n ，t e x tc l u s t e r i n g 1 1 1 e 一 ， 目录 摘要1 第l 章绪论_ 1 1 1课题背景及意义1 1 2国内外研究现状2 1 3论文内容与研究点。3 1 3 1数据处理3 1 3 2网络信息抽取。4 1 3 3多类型网络构建。4 1 4 论文结构5 第2 章信息处理相关技术介绍6 2 1中文信息处理基本概念6 2 2 文本聚类7 2 2 1文本聚类基本概念。7 2 2 2 文本聚类算法综述8 2 3 信息抽取1 4 2 3 1 信息抽取基本概念1 4 2 3 2 信息抽取发展历史与现状1 4 2 3 3信息抽取研究内容1 5 2 4本章小结1 8 第3 章网络信息抽取研究与实现1 9 3 1数据集划分1 9 3 1 1划分基本过程1 9 3 1 2 传统聚类的缺点分析2 0 3 1 3 对聚类算法的改进2 l 3 2 网络点与边信息抽取2 2 3 2 1网络点信息抽取2 2 3 2 2网络边信息抽取。2 3 3 3实验结果及分析2 8 3 3 1实验数据集2 8 3 3 2 评价指标2 8 3 3 3 实验与分析。2 9 3 4 本章小结。3 2 第4 章多类型网络构建实现 4 1 网络类型概述 4 1 1 复杂网络实际应用3 3 4 1 2 常用网络类型3 4 4 2 网络构建设计与实现。3 5 4 2 1 数据模型3 5 4 2 2 网络构建3 6 4 2 3网络转换与关系精简3 8 4 3本章小结4 0 第5 章原型系统设计与实现。4 l i v 5 1 原璎系统目标4 1 5 2原型系统设计4 1 5 3 原型系统的实现4 3 5 4实验结果与分析4 5 5 4 1实验数据集4 5 5 4 2 实磬 釜4 5 5 4 3 实验结果分析5 1 5 5 本章小结5 2 第6 章结束语。5 3 6 1总结5 3 6 2展望5 4 参考文献5 5 1 i ! i ：谢：；9 v 1 1 课题背景及意义 随着企业信息化与互联网的发展，信息以爆炸性速度飞速增长，其中包括了 大量的非结构化与半结构化数据。非结构化与半结构化数据，主要是文本型数据， 阐述5 w 问题，即w h o ，w h e n ，w h e r e ，w h a t ，w h y 。如何充分利用非结构化数据 与半结构化数据，分析其包含的潜在信息，拥有支持决策，成为了众多企业与研 究者关注的重点。复杂网络研究的深入，为我们提供了一个新视角、新方法。 “复杂网络 是近年来，获得众多研究者关注的热点领域。1 9 9 8 年美国康 奈尔大学的w a t t s 和s t r o g a t z 在n a t u r e 杂志上发表了( c o l l e c t i v ed y n a m i c so f “s m a l l - w o r l d n e t w o r k s ) n 1 ，引入了小世界网络模型，以描述从规则网络到 随机网络的转变，揭示了即具有与规则网络类似的聚类特性，同时又具有与随机 网络类似的较小平均路径长度的性质。1 9 9 9 年n o t r ed a m e 大学的b a r a b a s i 和 a l b e r t 在s c i e n c e 上发表了( e m e r g e n c eo fs c a li n gi nr a n d o mn e t w o r k s ) 坦， 指出复杂网络的连接度分布具有某种幂指数形式，由于幂律没有明显的特征长 度，该类网络被称为无尺度网络。这两篇论文揭示了现实网络普遍存在的小世界 效应与无标度特性。自此在不同领域，关于复杂网络的研究不断的出现热潮。 特别最近十年，复杂网络研究，特别是对网络分析算法的研究不断深入。例 如众多研究者将一些经典的统计算法方法d 1 以及传统数据挖掘算法应用到复杂 网络分析中。通过对网络特征值的计算，如度分布特征，聚类系统，平均路径长 度，网络直径，点或边的中介度，来反映网络中某些重要特性。基于网络拓扑结 构，提出不同的社区划分算法h 钔，划分不同社区群体。对网络动态性的研究与 网络之间的比较与综合，分析数据中包含的潜在信息。随着复杂网络分析算法的 不断完善，集成众多分析算法的网络分析工具与系统相继出现，如面向科研评价 领域的a r n e t m i n e r 口】，面向全领域的n w b ( t h en e t w o r kw o r k b e n c h ) 嘲，以及面 向新闻分析领域的j i g s a w 睛3 等。 通过对复杂网络研究内容以及复杂网络分析工具与系统进行比较与分析，不 难发现，在复杂网络分析过程中，采用的分析算法是大同小异，而应用数据类型 与所构建的网络类型的不同是其区别所在。即：分析与挖掘出来的实际信息的不 同，主要取决于在所构建网络节点与边的包含信息以及构建的数据类型。同时随 着信息处理技术的发展，特别是中文信息抽取技术的不断成熟。从非结构化与半 结构化数据中抽取出实体信息，以及它们之间的关系，成为了可能。 鉴于此，将中文信息抽取技术与复杂网络技术相结合，基于非结构化与半结 构化的数据类型，构建不同类型网络，然后采用复杂网络分析算法进行挖掘，成 为了充分利用非结构化数据与半结构化数据的一种全新的方法与模式，同时成为 了理论研究与应用领域新热点之一。 因此，本文将以非结构化数据为对象，主要是针对新闻文本数据，研究中文 信息处理的相关技术，同时将其融入复杂网络构建中，研究如何构建多类型网络， 来充分利用非结构化数据。 1 2 国内外研究现状 在复杂网络发展初期，网络构建主要基于结构化数据，通过其潜在的联系来 构建网络，例如科研合作网阳1 。学术论文的相应属性以结构化形式存储于数据库 等存储体中，通过论文作者之间的联系( 既数据库中表之间的相互关系) 构建科 研合作网络，其节点表示研究者，边表示其是否共同合作撰写论文。基于结构化 数据可以轻易构建网络。基于非结构化数据的网络构建有别于基于结构化数据的 网络构建，需要将信息抽取技术融入网络构建中，将两者结合一起。近年来，信 息处理与复杂网络的结合逐渐成为研究者关注的重点，相应的研究和应用也在迅 速增加。 非结构化数据包含的信息主要由三种元素组成l1 数据本身，即非结构化 数据全文；2 字或者词语，即组成非结构化数据全文的最小单元；3 实体信 息，即非结构化数据中包含的人名、地名、机构以及专业术语等信息。在国内外 研究中，针对非结构化数据的复杂网络主要是基于上述三种元素进行构建 a t o m k i n s n 州3 等基于博文中的时间信息，构建博文关系网络，研究了博客 的时间演化与突发点；w a n x j 【1 2 1 等研究了一个特定话题的网络新闻传播过程， 建立了一个简单的新闻关系网络；王友忠“阳等基于网络新闻媒体之间的转载关系 构建了新闻转载网络，应用复杂网络理论分别研究了其无向无权网络、无向加权 网络以及有向网络的拓扑结构，发现权值和方向对网络新闻研究的重要意义。博 文关系网络、新闻关系网络其节点是博文与新闻，反映的是非结构化数据本身之 间的相互关系。 f e r r e r i c a n c h o n 们与w e il u o x i a u 明基于非结构化数据，构建词语共现网络， 通过分析发现英语词语共现网络与中文词语共现网络均具有小世界特性，而且3 度分隔，即从一个节点出发平均三步可以搜索到目标节点；赵鹏等人口5 1 通过构建 词语网络，提出基于词语网络特征的中文文档关键词抽取算法。 基于数据本身与基于字或词语构建复杂网络其对信息抽取技术的要求比较 弱化，在早期研究中被普遍常用。而基于实体信息构建网络，需要涉及众多中文 2 信息抽取技术。近年来，随着实体识别研究的深入，基于非结构化数据中包含的 实体信息构建的网络，并对其进行分析成为了一种趋势。 例如：x i nl in 钉等通过信息抽取技术，抽取命名实体构建网络，再通过社 区发现在w e b 上挖掘出知识来；d e n n i sm w i l k i n s o nn 砌等提出了通过信息抽取 技术，提取出与某一疾病相关的共现基因，而后构建成网络，划分一些相关基因 的社区，从而能够帮助专家们发现出基因间的相互作用和它们之间的一些潜在联 系等等；以及董献洲啪1 等针对新闻报道中所涉及的政治人物，基于政治人物在新 闻报道中的共现共现，构建人物关系网络，研究并发现该人物关系具有无标度性。 同时针对非结构化数据的复杂网络构建与分析工具相继出现，其中较为重要 的是c o n t e x t e rn 引、j i g s a w 瞪1 与微软人立方。c o n t e x t e r 旨在帮助专家级或者 半专家级的专业人士( 如分析师，社会科学家，记者等) 快速与有效地获取新闻 语料在不同层次中应用。j i g s a w 以多维的角度观察文献数据，构建并展示不同 类型的网络，实现网络之间的转换与联动。微软人立方从海量的非结构化数据中 抽取实体( 主要是人物) ，构建人物关系网络，以便于用户查询人物及其关系。 上述三种工具，均通过采用基于非结构化数据构建网络来进行分析与展示。其网。 络构建主要是基于简单的共现模型进行构建，例如文献关系网络基于其是否拥有 相同实体进行构建、人物关系网络基于人物是否在同一篇文献中共现进行构建 世 号于0 通过上述对国内外研究的分析，基于非结构化数据的网络构建越来越受到关 注，其研究和应用正在迅速增加。但其网络构建仍然存在问题：l 网络构建较 多采用简单共现模型来构建，无法充分利用非结构化数据中包含的实体关系信 息；2 网络分析多数基于单一网络进行，多类型网络间的转换与递进式构建研 究较少。鉴于此，本文将集中研究基于非结构化数据的多类型网络构建，从非结 构化数据中抽取实体关系信息，充分利用其构建网络，同时实现多类型网络的递 进式构建与相互转换。 1 3 论文内容与研究点 本文研究点主要分布在数据处理，网络信息抽取与网络构建三个阶段，具体 的研究内容如下： 1 3 1 数据处理 在海量非结构化数据中，包含着众多领域与不同主题的数据信息，各个领域 之间的数据信息相关度较低。基于海量非结构化数据的分析更多是针对某一领域 或者主题的分析，如若对整体数据进行处理，将会处理许多不相关数据，在时间 3 与空间上造成巨大的浪费，同时带来大量的噪音，影响分析结果，使结果出现误 差。 数据处理其目标主要是分析整体数据包含的不同主题，将其划分为不同子集 合。相同集合内的非结构化数据相似度较高，不同集合内的非结构化数据相似度 较低，每个集合包含阐述类似主题的非结构化数据。通过将原始的非结构化数据 划分为不同集合，以便于基于更为精确的非结构化数据构建与分析网络，以提高 网络构建速度与精确度。 鉴于此，本文将对文本聚类技术进行研究与提高，采用文本聚类技术将原始 非结构化数据划分为不同的簇类，每个簇类包含描述相似主题与同一领域的非结 构化数据。 1 3 2 网络信息抽取 在复杂网络，网络信息抽取旨在抽取网络中节点与边的相关信息。本文中的 网络信息抽取是指抽取非结构化数据中包含的命名实体信息以及实体关系信息， 以此构建复杂网络。 命名实体是非结构化中基本的信息元素，是正确理解非结构化数据的基础。 主要的命名实体包括：人名、地名、机构名以及时间实体。实体关系是指非结构 化数据中命名实体间的语义关系。命名实体信息及其实体关系信息抽取涉及到中 文信息抽取的相关技术，主要包括，中文分词、词性标注、实体识别、实体关系 抽取。 在网络信息抽取阶段，本文将主要对实体关系抽取相关技术进行研究，同时 将研究时间实体归一化技术，以便于多类型的网络构建。 1 3 3 多类型网络构建 复杂网络是基于网络分析的一种数据挖掘技术。挖掘出信息的实际意义取决 于网络节点信息与网络类型。通过不同网络类型的分析与相互转化、比较，可以 获得不同的信息。常用的网络类型包括。同质网络、异质网络、正反网络、动态 网络。 同质网络展示相同类型实体之闾的关系。通过同质网络分析，可以挖掘出非 结构化数据中包含的相同实体之间的潜在的信息。如分析科研合作者之间的关系 网络，可以获得核心人物以及所带领的团队。异质网络展示不同类型实体之间的 关系。通过异质网络分析，可以挖掘出不同实体之间关系。如分析疾病与基因网 络能够帮助专家们发现出疾病与基因之间相互作用。正反网络是同质网络或异质 网络的深化，其将关系划分为正反两种，展示网络节点之间正反关系。通过正反 4 网络的分析，可以挖掘出不同的社团以及社团之间的正反关系。态网络有别于上 述静态网络，展示网络时序性，以此挖掘网络的发展与变化规律。 鉴于此，本文将主要研究同质网络、异质网络、j 下反网络、动态网络的构建 模型，自动构建不同类型网络。 1 4 论文结构 本论文按以下章节进行组织： 第一章是绪论部分。简要介绍了本论文的相关背景和意义、国内外研究现状、 论文内容与研究点以及论文结构。 第二章将主要介绍针对非结构化数据的信息处理相关技术。包括对信息处理 技术的基本概念、研究内容以及本文中涉及的相关处理技术的研究现状进行介 绍。 第三章将对非结构化数据的信息抽取进行研究与实现。其中主要是对非结构 化数据集划分以及网络构建所需的实体信息以及实体关系信息的抽取进行研究。 第四章将研究多类型网络构建模型。对同质网络、异质网络、正反网络、动 态网络构建进行相应研究，以便于自动构建不同网络。 第五章主要介绍多类型网络构建原型系统的搭建及相关的试验。 第六章是总结与展望，针对全文做出总结，提出了进一步的研究方向。 文章的最后是参考文献，致谢及攻读学位期间发表的学术论文。 5 第2 章信息处理相关技术介绍 近十几年来，信息处理一直历来都是众多研究者关注的研究重点之一。其中 涉及到信息抽取、自动聚类和分类、自动摘要、主题识别以及文本生成等技术。 本章将对中文信息处理的基本概念、理论和本文涉及到的相关技术进行阐述。 2 1 中文信息处理基本概念 随着计算机的普及以及互联网的迅猛发展，各种类型的信息不断增加。为了 应对信息爆炸带来的挑战，如何从海量信息中迅速找到用户所需的信息，成为迫 切的需要。在这一大背景下，信息处理技术的相关研究不断的产生与发展。在 广义上，信息处理技术是针对各类数据的自动化处理技术，包括文本型数据、图 形数据、语音数据等。在本文中，信息处理技术主要是针对文本型数据的自动化 处理技术。 中文信息处理是以中文信息为对象的信息处理技术，具体而言，即用计算机 对中文信息进行转换、传输、存贮、分析等加工的科学。它是- - f l 与语言学、计 算机科学、心理学、数学、控制论、信息论、声学、自动化技术等多种学科相联 系的边缘交叉性学科，是自然语言信息处理的一个分支，是依据语言知识、背景 知识，对中文信息的人脑处理过程进行的模拟。主要包括中文分词、信息抽取、 自然语言理解、文本聚类和分类、自动标引与主题识别、自动检索等相关技术。 中文分词旨在基于汉语字段，找出其潜在分割信息，将字段分成词语链由 于中文的特殊性：词语之间没有空格、没有词形变化等等，使得中文分词成为中 文信息处理首要与基础的工作，这也是中文处理与英文处理最大的区别之一。 文本分类是一个基于训练样本集、寻找一组模型( 或函数) 韵过程，这些模型 ( 或函数) 用于描述和区分数据类别和概念，也就是将大量样本划分为一个个样本 类( 或组) ，使得各样本类代表不同的概念主题，以便预测未知样本所属的类别。 与文本分类不同，文本聚类没有学习过程，而且类别没有明确的标签。文本聚类 依据“类内相似度最大、类间相似度最小一的原则，将样本划分成样本簇。 自动标引是根据拟存贮、检索的档案文献( 题名、文摘、正文) 用计算机自动 选定标引词( 即检索标识) 的标引技术，其中研究最多、应用最广的是主题标引( 或 主题识别) 。主题标引是指通过文献主题分析，给文献以主题词作为检索标识的 过程，是文献控制的基本方法之一，具有直观、专指、灵活等优点。 6 文本聚类是信息处理与分析的基础技术之一，揭示文本集合的结构特征和文 本之间的联系。其基于著名的聚类假设啪1 ：同类的文本相似度较大，而不同类的 文本相似度较小。将文本集合分组成多个类或簇，使得在同一个簇中的文本内容 具有较高的相似度，而不同簇中的文本内容差别较大。 文本聚类用数学描述为：对文本集合x1 仇，x 2 。 进行划分，分成 c 一 glc c x ，f 。1 j ，l ，uc 鼻x ) ，c ：f 即为_ 二个簇。 文本聚类是一种无监督酌机器学习方法，由于不需要训练过程，以及不需要 预先对文本数据手工标注类别，具有较高的灵活性和自动化处理能力，被加以广 泛应用。例如： 1 ) 可以作为多文档自动文摘等自然语言处理应用的预处理步骤，例如将每 天发生的重要新闻文本进行聚类处理，并对同主题返回的结果进行聚类，使用户 迅速定位到所需要的信息。 2 ) 对搜索引擎键入关键词，而后对检索到的文档进行聚类处理，并输出各 个不同类别的简要描述，对搜索结果集合按照其相关主题进行划分，生成不同主 题的簇，从而可以缩小检索的范围，用户只需关注比较感兴趣的主题。 3 ) 作为文本分类的预处理步骤，指导文本分类或改善分类结果。例如通过 文本聚类来生成w e b 文本的分类规则，用文本聚类来帮助用户管理和组织个人 e - m a i l 等2 。 在本文中，文本聚类被应用于复杂网络构建的数据处理步骤，将文本数据集 进行聚类处理，划分包含的不同主题信息的子数据集，以便于用户定位相应的数 据集，进行进一步的处理与分析。 7 2 2 2 文本聚类算法综述 本小节将首先介绍文本聚类领域在文本表示、文本相似度衡量等方面的知 识，然后介绍几种常见的文本聚类算法。 2 2 2 1 文本表示模型 文本表示模型也称为文本特征的表示。文本特征是指关于文本的元数据，分 为描述性特征( 如文本的名称、日期、大小、类型等) 和语义性特征( 如文本的作 者、机构、标题、内容等) 。特征表示是指以一定特征项( 如词条或描述) 来代表 文本数据，在文本挖掘时只需对这些特征项进行处理，从而实现对非结构化的文 本进行处理，这是一个非结构化向结构化转换的处理步骤。 典型的文本表示模型有：1 ) 布尔模型、2 ) 向量空间模型、3 ) 概率检索模 型、4 ) 语言模型。 一、布尔模型 布尔模型是基于集合论与布尔代数的一种简单模型嘲1 。在布尔模型中，文本 岛中索引特征五的权重彤，j 是二值得，即彬，e o , q ，即可以讲单个文本表示成 为特征空间上的一个向量，向量中的每个分量权重为0 或者l ，这种模型称为布 尔模型。由于权重的二值性，所以布尔模型只能用于信息检索中计算用户查询与 文本的相关性，而无法利用该模型计算两个文本更深层面的相似度。在经典布尔 模型基础上，研究人员又提出了扩展布尔模型，使相关性可以成为 0 ，1 之间的 数。布尔模型是基于集合论与布尔代数之上的一种表示模型，其表示与计算可以 转化为向量来等价实现，是一种类向量的模型。 二、向量空间模型 向量空间模型v s m ( v e t o r 跏c em o d e l ) 1 是信息检索领域中经典的检索模 型。该模型的主要思想是z 将每一个文本都映射为一组规范化正交词条矢量组成 的向量空间中的一个点。 在用向量表示文本时，需要对文本集进行切分、停用词处理等步骤。在经过 这些步骤后，基本上就可以得到一系列词或词素，将这些词或词素作为文本的特 征。此时，所有的这些词就构成了一个“空间 ，每个词对应着空间中的一维。 表2 - 1v s m 模型中文本与空间的映射表 ；。? 、。一n 一：! 。二 一一? 十，jj，一。? i ii ，i ，。? 、? 。- 乞。i 文本视角：，二o j ：纛曩曼磊主麓菇藏乏羡；j 向量空间模型视角、 1 0 j 文本向量空间中的点 词或词素空间中的一维 文本集合分布在空间中的一组点集 词的权重空间中点的坐标 8 对于每个文本d ；，都可以用文本中的词来表示，这些词及其对应的权重就 构成了“空间”中的一个向量：似，睨，j ) ， 其中，彬，为q 中词条f 的权重。 权重的经典定义是： 彬，= t f , ，幸佃晖式( 2 一1 ) t f ( t e r mf r e q u e n c y ) 表示词条f 在文本d ；中出现的次数，称为词频； i d f ( i n v e r s ed o c u m e n tf r e q u e n c y ) 定义为： e l o g ( n n ，) 式( 2 2 ) 表示文本集合中所有的文本数目，绝表示整个文本集合中出现过词条i 的 文本的总数，称为特征的文本频度。 三、概率检索模型 概率检索模型矧是信息检索领域另一比较成熟的模型，并在很多系统中 应用取得不错的效果。概率模型是一系列模型的简称，它综合考虑了词频、文档 频率和文档长度等因素，把文档和用户兴趣( 查询) 按照一定的概率关系融合， 并在概率测度空间上通过概率来衡量两个文本的语义相似度。在信息检索中，主 要计算用溉i 眈删，酬，并利用概率排序原则原哪州撇喇 来判断不同文档与同一个查询相关的程度。 耳概i 肪删，酬表示对于查询q u e r y ，文档d o c u m e n t 与该查询相关 的概率。根据不同的假设得到的求脚曲撇砌r 咖r 姊蚴的计算公式，可 以衍生出不同的概率检索模型。概率检索模型包括脚雕轨叫尻劫舭酬e v a o ， i n q u e r y 等。 四、语言模型 语言模型本质上也是一种基于概率和统计的模型。在语言模型中，每个文档、 整个语料库、相关查询都被看作是语言模型，通过计算语言模型之间的距离来衡 量查询与文档的相关性及文档与文档之间的相关性。语言模型就其研究方向而 言，一般分为两类。一类是基于语言学知识的规则文法，另一类是基于统计的语 言模型。目前，以语料库为基础的统计语言建模方法成为潮流。这种方法通过对 语料库进行深层加工、统计和学习，来获取大规模真实语料中的语言知识。统计 语言模型认为语言就是字母表上的一种概率分布，通过概率分布计算任何一个字 母序列成为该语言一个语言单元( 句子、段落、文章等) 的可能性。特征集合在 某个文档d ；中形成一个分布，这个概率分布就称为一个语言模型。 2 2 2 2 文本相似度 文本相似度是用来衡量两个文本之间相似程度的度量。在文本聚类分析中， 主要有三种相似度度量：1 ) 文档与文档之间的相似度度量、2 ) 文档与文档集合 9 之间的相似度度量、3 ) 文档集合与文档集合之问的相似度度量。 一、文档与文档之间的相似度度量 为了衡量以向量形式表示的文档x 与y 之间的距离，最常用的方法就是采用 明氏距离： s i m ( x ，y ) 一( “一咒) 叮) 1 细 式( 2 3 ) 7 其中q 一2 时，即为欧几里德距离。 除此之外，还可以采用文档表示向量之间的余弦夹角来衡量x 与y 之间的相 似度， s f 朋( x ，y ) c 。s ( z ，y ) 。；工， 二、文档与文档集合之间的相似度度量 为了衡量文档集合之间的相似度，常见的方法有：最小距离、最大距离、平 均距离、质心法等。以下是各个相似度定义的数学描述，其中，c 与g 分别表 示两个文档集合。 1 ) 最小距离： d ( c l ，c 2 ) 一m i n d ( x ，y ) i x e c ，y e c z 式( 2 5 ) 2 ) 最大距离： d ( c l ，c 2 ) - m a x n , 伍，y ) i x c l ，y e c 2 式( 2 6 ) 3 ) 平均距离l 粥岛) 。尼l 荟磊叫，y ) 4 ) 质心法：使用集合中所有文档向量的算术平均作为集合的中心向量，这 之后，使用计算文档与文档相似度的方法来计算文档集合之间的相似度。 三、文档集合与文档集合之间的相似度度量 对于文档与文档集合之间相似度度量的问题，可以将文档看作是只含有一个 文档的文档集合，套用上面介绍的文档集合与文档集合之间相似度度量的办法来 衡量。 2 2 2 3 聚类算法 聚类算法的研究早在2 0 世纪6 0 年代就开始了，但是受当时各方面条件的限 制并没有太大的发展，直到2 0 世纪9 0 年代才引起广泛的关注，并取得重大的突 破。大体上，聚类算法可以分为划分聚类算法、层次聚类算法、基于密度的聚类 1 0 ， 算 其 图2 - 1 聚类方法 2 2 2 3 1 划分聚类 划分聚类( p a r t i t i o n i n gm e t h o d ) 的基本思想是：将数据集合d 中的n 个元素 进行划分，形成一个平面的类结构，同时满足如下要求： 1 ) 每个组至少包含一个对象； 2 ) 每个对象必须属于且只属于一个组。 3 ) 指定一个相异函数f 来计算元素之间的差异，使得在同一个簇中的对象 之间尽可能的相近或相关，而不同簇中的对象之间尽可能远离或不同。 划分聚类的典型算法代表有k 一均值算法k 一黼、肛中心点算法 ( k - m n a d s ) 、最近邻聚类岬蛳) 、最大距离聚类( m a x - d i s t a n c ec l u s t e r i n g ) 等。 ( 1 ) k m e a n s 算法的具体流程如下： a ) 确认要生成簇的数目k ： b ) 按照某种原则生成k 个聚类中心作为聚类的种子s 一( & ，是，s ，瓯) ； c ) 对d 中的每个文件q ，依次计算它与各个种子s f 的相似度鼢( 皿，s f ) ； d ) 选取具有最大相似度的种子，将4 归入以s ；为聚类中心的簇c ，； e ) 重新计算k 的簇中心，中心为该簇内所有点的算术平均； f