（计算机软件与理论专业论文）基于复杂网络理论的文本聚类和关键词提取方法研究.pdf

辽宁师范大学硕士学位论文 摘要 随着信息技术的高速发展，文本信息的数量正以几何速度飞速增加，如何在这些海 量的文本信息中快速的获得自己有用的信息，并且合理的管理和使用这些文本信息，已 经成为当今亟待解决的问题。合理的利用数据挖掘技术，能够有效的解决这一问题。 文本聚类和文本关键词提取是文本挖掘领域中重要的研究内容。文本聚类将文本集 分成若干个类，要求同一类中的文本之间相似度较大，而不同类的文本之间的相似度较 小。文本聚类作为一种无监督的机器学习方法，不需要训练集，不需要事先知道聚类个 数，因此具有一定的灵活性和现实性。文本关键词提取是处理文本信息的重要技术之一， 是文本自动分类、自动聚类、自动摘要生成等文本信息处理的前提和基础。 本文介绍了文本聚类和文本关键词提取的研究背景、研究意义、国内外研究现状和 相关的理论知识。本文在总结之前国内外经典的文本聚类和关键词提取研究的基础上， 分别提出了文本聚类和文本关键词提取的新方法，具体工作包括以下两个方面： 1 提出一种基于复杂网络社团划分的文本聚类方法，首先提出了一种加权复杂网络 社团划分的新算法，通过不断寻找复杂网络中的稠密集并对其进行适当操作，达到了划 分加权复杂网络的目的。其次将该算法应用于文本聚类，将文本用向量空间模型表示， 用余弦公式计算文本之间的相似度，根据邻居节点构造出加权复杂网络，用本文提出的 算法对加权复杂网络进行社团划分。最后，对r e u t e r s 一2 1 5 7 8 数据集中的部分样本进行 聚类，实验表明该方法具有良好的聚类效果。 2 提出一种基于加权复杂网络的文本关键词提取方法，通过分析已有的基于复杂网 络的关键词提取算法的特点和不足，提出了一种基于加权复杂网络的文本关键词提取新 算法。首先根据文本特征词之间的关系构建文本的加权复杂网络模型，其次通过节点的 加权聚类系数和节点的介数计算节点的综合特征值，最后根据综合特征值提取出文本关 键词。实验结果表明，该算法提取的关键词能够很好的体现文本主题，提取关键词的准 确率比已有算法要高。 关键字：文本聚类；关键词提取；加权复杂网络；稠密集；综合特征值 j 基于复杂网络理论的文本聚类和关键词提取方法研究 t h er e s e a r c ho ft e x tc l u s t e r i n ga n dk e y w o r d se x t r a c t i o nb a s e do n c o m p l e xn e t w o r kt h e o r y a b s 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 f o r m a t i o nt e c h n o l o g y ，t h en u m b e ro ft e x td a t ai s i n c r e a s i n ga m a z i n g l y h o wt oq u i c k l ya c c e s st h eu s e f u lt e x ti n f o r m a t i o ni nl a r g et e x td a t a ， p r o p e r l ym a n a g ea n du s et h e s et e x tm e s s a g e sh a sb e c o m et h eu r g e n tp r o b l e m g e t t i n gu s eo f t h ed a t am i n i n gt e c h n o l o g yr e a s o n a b l ec a ne f f i c i e n t l yh e l pt os o l v et h i sp r o b l e m t e x tc l u s t e r i n ga n dt e x tk e y w o r de x t r a c t i o ni sa ni m p o r t a n tf i e l di nt e x tm i n i n gr e s e a r c h t e x tc l u s t e r i n gd i v i d e st h et e x to fd o c u m e n ti n t os e v e r a lc l u s t e r s w h i c hr e q u i r e st h a tt h et e x t s a s s i g n e dt oe a c hc l u s t e ra r em o r es i m i l a rt oe a c ho t h e rt h a nt h et e x t sa s s i g n e dt od i f f e r e n t c l u s t e r s a sa nu n s u p e r v i s e dm a c h i n el e a r n i n gm e t h o d ，t e x tc l u s t e r i n gd o e s n tr e q u i r et h e t r a i n i n gs e to rn e e dt ok n o wt h en u m b e ro fc l u s t e r si na d v a n c e i th a sag r e a to ff l e x i b i l i t ya n d r e a l i t y t e x tk e y w o r de x t r a c t i o ni s o n eo ft h e i m p o r t a n tt e x t i n f o r m a t i o n p r o c e s s i n g t e c h n o l o g y i ti st h ep r e m i s ea n df o u n d a t i o no fi n f o r m a t i o np r o c e s s i n gi n c l u d i n ga u t o m a t i c c a t e g o r i z a t i o n ，a u t o m a t i cc l u s t e r i n g ，a u t o m a t i cs u m m a r yg e n e r a t i o na n ds oo n 。 t h i st h e s i si n t r o d u c e dt h eb a c k g r o u n do ft h et e x tm i n i n ga n dt e x tk e y w o r d se x t r a c t i o n ， r e s e a r c h s i g n i f i c a n c e ，r e s e a r c h s t a t u sa n dr e l e v a n tt h e o r e t i c a l k n o w l e d g e t h i st h e s i s s t m u n a r i z e dd o m e s t i ca n df o r e i g nc l a s s i c st h e o r e t i c a lk n o w l e d g e ，p r o p o s e dan e wt e x t c l u s t e r i n gm e t h o da n da n e wt e x tk e y w o r d se x t r a c t i o n m a i nw o r ki n c l u d e st h ef o l l o w i n gt w o a s p e c t s ： 1 b a s e do np a r t i t i o n i n gc o m m u n i t yi nc o m p l e xn e t w o r kat e x tc l u s t e r i n gm e t h o di s p r o p o s e d f i r s t l y ，an e wa l g o r i t h mf o rd e t e c t i n gc o m m u n i t ys t r u c t u r e si naw e i g h t e dc o m p l e x n e t w o r ki sp r o p o s e d t op a r t i t i o nt h ew e i g h t e dc o m p l e xn e t w o r ki n t og r o u p s ，t h ea l g o r i t h m l o o k sf o rt h ed e n s i t ys e t sc o n s t a n t l ya n ds o m ep r o p e ro p e r a t i o n sa r ee x e c u t e d s e c o n d l y ，t h e p r o p o s a li sa p p l i e dt oc l u s t e rt e x td o c u m e n t sw h i c ha r er e p r e s e n t e db yt h ev e c t o rs p a c em o d e l a w e i g h t e dc o m p l e xn e t w o r ki sc o n s t r u c t e di nt e r m so ft h es i m i l a r i t yb e t w e e nt w od o c u m e n t s c a l c u l a t e db yt h ec o s i n ef u n c t i o n a n dt h e nt h ec o m m u n i t ys t r u c t u r ei n t h i sn e t w o r ki s d e t e c t e db yt h ep r o p o s e da l g o r i t h m f i n a l l y ，t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h ep r o p o s e d a l g o r i t h mh a sag o o dc l u s t e r i n ge f f i c i e n c yb yc l u s t e r i n gs o m es a m p l e so fr e u t e r s 一215 7 8d a t a s e t s 2 a n a l y z e dt h ec h a r a c t e r i s t i ca n dd i s a d v a n t a g e so ft h ee x i s t i n gk e y w o r d se x t r a c t i o n a l g o r i t h mb a s e d o n c o m p l e xn e t w o r k ，an e wk e y w o r d se x t r a c t i o na l g o r i t h m sb a s e do n w e i g h t e dc o m p l e xn e t w o r ki sp r o p o s e d f i r s to fa l l ，aw e i g h t e dc o m p l e xn e t w o r km o d e li s i i c o n s t r u c t e da c c o r d i n gt ot h er e l a t i o n s h i pb e t w e e nt h ef e a t u r ew o r d so ft e x t s e c o n d l y ，t h e w e i g h t e dc l u s t e r i n gc o e 硒c i e n ta n db e t w e e n n e s sa r ei n t r o d u c e dt oc a l c u l a t e t h en o d e s m u l t i f e a t u r ev a l u e f i n a l l y ，t h ek e y w o r d sa r ee x t r a c t e db yt h em u l t i f e a t u r ev a l u e t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h ek e y w o r d se x t r a c t e di nt h i sa l g o r i t h mh a v eg r e a tc o n t r i b u t i o n t ot h et e x ts u b j e c t ，a n dt h ea c c u r a c yo fk e y w o r d se x t r a c t i o ni sb e t t e rt h a nt h e e x i s t i n g a l g o r i t h m s k e y w o r d s ：t e x tc l u s t e r i n g ；k e y w o r d se x t r a c t i o n ；w e i g h t e dc o m p l e xn e t w o r k ；d e n s i t ys e t ； m u l t i f e a t u r ev a l u e i i i 基于复杂网络理论的文本聚类和关键词提取方法研究 目录 摘要i a b s t r a c t i i l 绪 仑1 1 1 研究背景和意义1 1 1 1研究背景1 1 1 2研究意义1 1 2 国内外研究现状3 1 2 1文本聚类研究现状3 1 2 2文本关键词提取研究现状4 1 2 3本文主要的研究内容4 】3 本文的组织结构5 2 文本挖掘与复杂网络理论6 2 1 文本聚类6 2 2 文本关键词提取8 2 3 复杂网络9 3 基于复杂网络社团划分的文本聚类方法1 8 3 1 基于稠密集的加权复杂网络社团划分算法1 8 3 2 基于稠密集的加权复杂网络社团划分算法的文本聚类算法1 9 3 2 1构建文本复杂网络模型1 9 3 2 2基于复杂网络社团划分的文本聚类方法2 0 3 3 基于特征文本提取的文本聚类方法2 l 3 3 1构造复杂网络2 l 3 3 2基于特征文本提取的文本聚类算法2 l 3 4 实验2 2 3 4 1基于复杂网络社团划分的文本聚类方法2 4 3 4 2基于特征文本提取的文本聚类算法j 2 5 3 5 小结2 8 4 基于加权复杂网络的文本关键词提取3 0 4 1 加权复杂网络中节点的重要性度量3 0 4 1 1节点的加权聚类系数3 0 4 1 2节点的介数3l i v 辽宁师范大学硕士学位论文 4 2 基于加权复杂网络的文本关键词提取3 1 4 2 1加权复杂网络的构建3 l 4 2 2基于加权复杂网络的文本关键词提取算法3 1 4 3 实验3 2 4 4 ，j 、结3 4 5 总结与展望3 5 参考文献。3 6 攻读硕士学位期间发表学术论文情况4 0 垂| 【谢4 l v 辽宁师范大学硕士学位论文 1 绪论 1 1 研究背景和意义 1 1 1 研究背景 随着计算机技术的迅速发展和互联网的日益普及，各类信息正以指数速度飞速增 长。根据2 0 1 0 年1 月1 5 日中国互联网络信息中心发表的中国互联网络发展状况统计 报告【1j 显示，截至2 0 0 9 年1 2 月3 0 日，中国网民规模达到3 8 4 亿人，普及率达到2 8 9 。 网民规模较2 0 0 8 年底年增长8 6 0 0 万人，年增长率为2 8 9 。其中宽带网民规模达3 4 6 亿人，手机网民规模年增加1 2 亿，2 0 0 9 年底域名总数为1 6 8 2 万，网民每周上网时长 继续增加。2 0 0 9 年网络应用使用率排名前三甲分别是网络音乐( 8 3 5 ) ，网络新闻 ( 8 0 1 ) ，搜索引擎( 7 3 3 ) 。以上信息表明，越来越多的电子信息如电子出版物、电 子邮件、博客等以文本作为信息载体，文本数据库得到了迅速的发展。 信息数量的增多给人们带来方便的同时也带来了许多问题，一方面信息数量过大， 使人们淹没在浩瀚如海的信息中无法选择和消化；另一方面大量信息聚集在一起，人们 很难找到自己所需要的有用信息。因此，如何快速有效的从大量的电子信息中找到自己 所需的信息，已经成为当今一个亟待解决的问题。数据挖掘【2 】是在大型数据存储库中， 自动地发现有用信息的过程。数据挖掘技术用来探查大型数据库，发现先前未知的有用 模式。文本挖掘已成为当今数据挖掘和信息检索的重要研究方向，其主要内容是对文本 数据库进行分析，发现文本数据库中文本的重要性和文本之间潜在的相关性等问题。 为了在浩瀚的文本信息中找到自己感兴趣的文本必须进行文本挖掘，为了提高检索 文本的准确度和效率，其可行的方法是对文本数据集进行聚类和关键词提取。通过对文 本集进行聚类，使得同一类的文本聚成一类，这样使得用户可以在自己感兴趣的文本类 中浏览和检索文本。通过对文本集中的文本进行关键词提取，使得用户可以根据关键词 快速的获取文本的主题内容，可以帮助用户快速的从大量的文本信息中找到相关的文 本。 1 1 2 研究意义 文本聚类和文本关键词提取是文本挖掘的有效方法，其目的都是为了能提高文本信 息检索的效率和准确率，既是对文本集知识的获取，也是对文本集的处理。对文本集进 行聚类和关键词提取研究有重要的意义，其研究意义主要体现在以下几个方面： ( 1 ) 文本聚类和关键词提取是文本信息管理的基础 以文本作为信息的载体是i n t e r n e t 上信息资源的主要形式，在海量的文本信息中， 基于复杂网络理论的文本聚类和关键词提取方法研究 要快速准确的找到自己所需要的信息是相当困难的。因此，解决这个问题是人们迫切需 要的。对于大量的文本信息，构建一个清晰的框架结构和简要的文本内容说明对于文本 集的存储和管理是非常必要的。对于文本信息基本处理的学术研究和应用在近些年来非 常活跃，如数字图书馆、搜索引擎、电子商务和博客等，虽然文本挖掘技术在这些领域 中对取得了相当大的进展，但仍然存在一些问题有待于解决，如处理过程需要人为的帮 助，缺少对文本主题内容的描述，处理结果不是十分的令人满意等。所以，对文本进行 聚类和关键词提取作为文本挖掘的基础性工作就显得格外重要。 ( 2 ) 文本聚类和关键词提取是文本挖掘的自身需要 文本挖掘是以文本作为数据挖掘的处理单元，从大量杂乱无章的文本集中发现文本 之间的内在联系，找出有利用价值的文本的过程。在文本挖掘的过程中，需要将文本集 中大量的文本按照某种特定的方式进行存储，同时需要对文本进行标识，这些在文本挖 掘的过程中是必不可少的，可以成为文本索引等处理应用的预处理步骤，有了这些工作 可以有效的对文本进行更进一步的挖掘。其中比较典型的例子是哥伦比亚大学研发的多 文档自动文摘系统n e w s b l a s e r | 3 1 ，它将新闻文本数据集进行聚类处理，并按照主题进行 冗余消除、信息融合、文本生成等处理，最终生成一篇简明扼要的摘要文档。 ( 3 ) 文本聚类和关键词提取是对信息检索的有效手段 信息检索是指从海量的信息集合中寻找用户需要的相关信息的一种重要手段，现有 的信息检索形式有两种：图书馆文献情报系统和网络搜索引擎【4 1 。为了能使用户在最短 的时间内从海量的文本信息中找到真正有用的信息，就需要自动化的工具来提高信息检 索的效率。 对于大量杂乱无章的文本信息进行文本聚类归并，这不仅满足了文本信息资源的合 理存储，也为用户对文本信息的使用提供了便利。特别是文本检索方面，在指定的类别 中查找所需文本，检索范围有所减小，搜索的准确率相应会有所提高。对于搜索引擎返 回的结果按照主题进行聚类，推荐给用户比较感兴趣的相关文本，有助于用户更合理的 利用文本信息。这方面比较典型的文本聚类搜索引擎有v i v i s i m o s l 和c a r r o ts e a r c h 开发 的基于j a v a 的开源c a r r o t 2 搜索结果聚类引擎2 0 版1 6 j 。 信息检索主要是通过关键词进行检索，关键词能够反映文本的主要内容。用户根据 文本的关键词进行索引查找相关文本信息，可以快速筛选过滤掉大量无关文本，大大降 低了文本索引的工作量。对于文本搜索引擎技术，文本的关键词提取始终是基础性的关 键技术。 ( 4 ) 文本聚类和关键词提取可以减少文本处理的人为因素和工作量 文本聚类作为一种无监督的文本处理技术，不需要人为规定聚类个数，不需要人工 辽宁师范大学硕士学位论文 分类好的训练集，也就是说在进行文本聚类处理之前不需要任何的人为处理，减少了聚 类效果的人为主观因素干预之外，也降低了文本聚类的人为工作量和时间开销。 文本关键词是对文本主题的简要概括，有助于用户更快的了解文本信息，有助于文 本的自动摘要生成、文本聚类、文本分类、文本索引等文本处理工作。对于一些没有文 本关键词的文本信息，无法简单的表达文本的主题，而且在用户使用、信息检索等方面 都很不方便。自动生成文本的关键词，降低了手工选择关键词的人为主观因素，同时也 减少了人力的工作量，提高了工作效率。 1 2国内外研究现状 1 2 1 文本聚类研究现状 文本聚类是文本挖掘的重要方法，用来索引、总结、组织文本信息，使得文本之间 相似度较大的文本集聚成一类。对大量文本信息进行聚类处理，文本聚类的结果可以有 效的组织大量的文本信息，同时可以根据用户的需求对大量的文本进行索引和查找操 ： 作。 ； 早在2 0 世纪6 0 年代，聚类算法已经在国外开始研究，因此文本聚类技术在国外也 比较成熟。到了2 0 世纪9 0 年代，聚类算法的研究得到了快速的发展，成为数据挖掘研 究中的热点。文本聚类算法总体上分为以下几类：基于概率的聚类方法1 7 j 、凝聚的层次 聚类方法【8 】和平面划分方法( k m e a n s 、b i s e c t i n gk m e a n s ) 【9 】等。文献 1 0 】提出了一种 基于邻居的文本聚类算法，采用了复杂网络相关理论对文本集进行聚类；文献 1 1 1 提出 了一种k - m e a n s 算法的改进算法，用来解决传统k - m e a n s 算法对中心点的敏感问题；文 献 1 2 1 将关联规则中频繁项的概念引入到文本聚类中，降低了文本聚类的高维问题。文 献【1 3 】提出了一种基于频繁项集的文本聚类算法，有效降低了向量空间模型的维度，提 高聚类准确度。 相对于文本聚类算法在国外的快速发展，国内对该问题的起步比较晚。文献【1 4 】提 出了基于复杂网络社团划分的w e bs e r v i c e s 聚类，由单词聚类映射出服务聚类结果。文 献【1 5 】提出了基于遗传f c m 算法的文本聚类，很好解决了f c m 算法对初始聚类中心敏 感问题。文献【1 6 提出了基于单词相似度的文本聚类算法，利用单词类作为向量空间的 项表示文本降低向量的空间复杂度。文献【1 7 】提出了一种基于关联规则的文本聚类算法， 提高了简单的句子和内容较少的文档的聚类的准确性。文献【1 8 】提出了一种基于伺量空 间模型的文本聚类改进算法，该算法有效的提高了文本聚类的效率，增加了文本聚类的 灵活性和实用性。文献【1 9 】提出了一种新的文本对象层次式聚类方法和文本信息空间索 引方法，增加文本之间相似度的准确性。 基于复杂网络理论的文本聚类和关键词提取方法研究 1 2 2 文本关键词提取研究现状 文本关键词提取是文本信息处理的重要技术之一，它是文本分类、聚类、信息检索 和自动摘要生成等技术的基础。典型的文本关键词提取方法是将文本的特征词提取出来 后，根据某种规则计算各特征词的权重，按照特征词的权重确定能够反映文本主题内容 的关键词。 在文本关键词提取方面，国外起步较早，发展较快，取得的成果很多。文献【2 0 】提 出了基于遗传算法的关键词提取算法，系统e x t r a c t o r 目前发展稳步，取得可观的收益。 文献 2 1 】利用朴素贝叶斯技术训练特征值，通过预测模型对文本进行关键词提取。文献 【2 2 提出了一种利用复杂网络理论自动生成文本摘要的方法，能够很好的发现文本特征。 近年来随着复杂网络这一学科的迅速发展，基于复杂网络的文本关键词提取算法被 众多学者所研究，如张敏等1 2 3 l 提出了一种利用b c 方法的关键词自动提取算法，通过 计算网络中节点的中心度提取文本关键词；任克强等1 2 4 j 提出基于带权语言网络的网页关 键词抽取算法，结合了节点介数和紧密度指标提取网页中关键词；赵鹏等1 2 5 j 提出了一种 基于复杂网络特征的中文文档关键词抽取算法，综合考虑语言网络中节点的度和聚类系 数对文本的关键词进行抽取。总结以上三个算法，文献【2 3 】和文献【2 4 】的算法计算节点 的权值都与最短路径相关，只考虑节点在整个网络信息流动的影响，而忽略了节点在局 部小世界中的影响程度；而文献【2 5 】中节点的度和聚类系数都是考虑节点在局部小世界 中的重要程度，而忽略了节点在整个网络中的影响程度。 1 2 3 本文主要的研究内容 本文主要的研究内容是基于复杂网络社团划分的文本聚类方法和基于加权复杂网 络的文本关键词提取方法。通过对已有文本聚类算法和文本关键词提取算法的研究和总 结，提出了一种新的聚类算法，应用于文本聚类中，同时结合已有的文本关键词提取算 法，提出了一种改进的文本关键词提取算法。本文主要研究的内容包括以下两个方面： ( 1 ) 文本聚类是对文本信息的一种处理方法，通过分析、总结和概括，把大量未 知标注的数据集，按照数据内在相似性将其划分成若干个类，使得同类文本相似度较大 而类间文本相似度较小。复杂网络是近几年得到迅速发展的- i - j 学科，寻找复杂网络的 社团结构是其主要的研究内容之一。事实上，对复杂网络进行社团划分的过程就是聚类 的过程。如果两文本之间的相似度足够大，认为两文本对应的节点为邻居节点。把文本 作为网络中的节点，邻居节点之间的相似度作为边的权值，这样就可以构造一个加权的 复杂网络，从而将文本的聚类过程转化为加权复杂网络社团划分的过程。 本文提出了一种加权复杂网络社团划分的新方法，通过寻找稠密集，并对其进行标 辽宁师范大学硕士学位论文 记、合并等操作，对加权复杂网络进行社团划分。复杂网络能够完整和准确的反映文本 集之间的内在联系，如果两个文本之间的相似度足够大，认为该文本对应网络中的节点 为邻居节点，利用节点和邻居节点之间边的权值构造一个加权的复杂网络，用本文提出 的加权复杂网络社团划分的新方法对网络进行社团划分，从而实现了文本聚类。从实验 效果上看，本算法达到了文本聚类的目的，具有一定的聚类灵活性，并且在聚类效果上 有所提高。 ( 2 ) 文本关键词提取是文本挖掘领域中的重点之一，针对现有的利用复杂网络理 论对文本进行关键词提取方法的缺点和不足，本文提出了一种基于加权复杂网络的文本 关键词提取方法。该方法首先将文本用加权复杂网络模型表示，然后结合加权复杂网络 节点介数和聚类系数指标，提出了特征词综合特征值的计算方法，最后提取出综合特征 值较大的特征词为文本的关键词。该方法提取出的关键词不仅在整个语言网络中显示出 高度的连通性，同时在局部也体现出高度的聚集性，能够很好的反应文本主题。 1 3 本文的组织结构 本文一共分为五个章节，理论结合实验，具体各章节的内容和组织方式如下： 第一章：绪论。介绍了本课题的研究背景和研究意义，文本聚类和文本关键词提取 方法在国内外的研究现状，介绍了本文的主要研究内容和本文的组织结构。 第二章：文本挖掘与复杂网络理论。介绍了文本聚类、文本关键词提取和复杂网络 的理论及经典算法。 第三章：基于复杂网络社团划分的文本聚类方法。提出了一种加权复杂网络社团划 分的新算法，通过不断寻找复杂网络中的稠密集并对其进行适当操作，达到了划分加权 复杂网络的目的，并将该算法应用于文本聚类。通过对r e u t e r s 2 1 5 7 8 数据集样本进行 实验分析，证明该方法的可行性和高效性。 第四章：基于加权复杂网络的文本关键词提取。通过分析已有的基于复杂网络的关 键词提取算法的特点和不足，提出了一种新的计算复杂网络中节点综合特征值的方法， 根据综合特征值提取出文本关键词。实验结果表明，该算法提取的关键词能够很好的体 现文本主题，提取关键词的准确率比已有算法要高。 第五章：总结与展望。总结本文研究所做的主要内容，分析研究中现存在的问题， 并确定下一步需要改进的方向。 基于复杂网络理论的文本聚类和关键词提取方法研究 2 文本挖掘与复杂网络理论 2 1文本聚类 文本聚类是文本挖掘研究中的重要内容之一，所谓文本聚类，就是根据文本之间的 相似度，将文本集中文本划分成若干个类，使得同一类中的文本之间相似度较大，而不 同类中的文本之间相似度较小。文本聚类不需要训练集，不需要事前知道聚类个数，是 一种无监督的聚类方法。 常见的文本聚类方法有五种：基于划分的文本聚类方法、基于层次的文本聚类方法、 基于密度的文本聚类方法、基于网络的文本聚类方法和基于模型的文本聚类方法【2 6 1 ，具 体描述如下： ( 1 ) 基于划分的文本聚类方法 给定一个有个对象的文本集，要将该文本集构建k 个分组，每个分组就代表一 个类( 艮，) 。而且这k 个分组要同时满足下列两个条件： 每一个分组至少包含一个文本； 每一个文本纪录属于且仅属于一个分组。 对于给定的分组个数k ，算法首先给出k 个初始的质心，以后通过反复迭代的方法 改变质心，使得每一次改进之后的聚类效果都有所提升【2 7 】。基于划分的文本聚类算法主 要有k - m e a n s 算法【2 8 】、k - m e d o i d s 算法2 9 1 、c l a r a n s 算法等。 k - m e a n s 算法【2 8 】主要描述：输入文本集和聚类个数后，首先选择任意七个文本对象 作为初始的聚类中心，其次计算其它文本到各个聚类中心的相似度，选择最近的分配到 该类中，更新聚类中心，反复上一步骤，直到聚类中心不发生改变，输出聚类结果。 k m e a n s 算法具有如下重要特点：能有效地处理大数据集；它经常终止于一个最优 解；由于欧式距离的局限性，它仅能处理数值属性；聚类结果具有凸的外形；算法的执 行结果和例子的顺序有关。从应用情况来看，k - m e a n s 算法以其简单高效获得广泛的应 用【4 们。 k m c d o i d s 算法和k - m e a n s 算法相似，只是k m e d o i d s 算法利用簇中心来表示一个类， 而k m e a n s 算法利用文本簇中的所有文本集来表示一个类，具体聚类方法和k - m e a n s 算 法类似。 c l a r a n s 算法例是对p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 算法【3 l 】的改进，该算法的 聚类过程可以被描述为对一个图的搜索过程，在搜索的每一步动态地、随机地抽取一个 样本，在搜索过程中，如果一个邻居具有更小的平方误差值，就认为它是一个更好的邻 辽宁师范大学硕士学位论文 居，算法就移到该邻居结点，处理过程重新开始，否则，就认为当前的聚类达到了一个 局部最优。 基于划分的文本聚类方法优点是算法简单并且可以用于各种数据类型，当结果簇是 密集的，而簇与簇之间区别明显时，它的效果较好。该方法的缺点是算法要求事先给出 簇的数目k ；另外，胸值不能处理非球形簇、不同尺寸和不同密度的簇；它对于噪音 点和孤立点是敏感的。 ( 2 ) 基于层次的文本聚类方法 基于层次的文本聚类方法，对给定的文本集进行层次的分解，直到满足某种判定条 件为止。层级聚类方法具体分为两种方法：自底向上的凝聚层次聚类方法和自顶向下分 裂层级聚类方法i 引。 凝聚的层次聚类方法，起初把所有的文本看做是单独的类，按照某种方法迭代合并 类，直到最终聚成一个类或者达到某种判定条件聚类结束。分裂的层次聚类方法，起初 把整个文本集看做是类，按照某种方法迭代分裂类，知道每个文本单独为一类或者达 到某种判定条件时聚类结束。典型的基于层次的聚类算法有：b i r c h 算法、c u r e 算 法、c h a m e l e o n 算法等。 b i r c h 算法【3 2 】是一个综合的层次聚类方法，该方法将数据集用特征向量树表 示，再利用某个聚类算法对特征向量树中的叶节点进行聚类。 c u r e 算法【33 l 利用数据空间中某个代表点进行聚类，能够解决不同大小类型的 类，解决了孤立点的问题。c h a m e l e o n 算法【3 4 1 是一种动态的层级聚类方法，主要 乎 思想是通过一个图划分算法将文本集聚类为大量相对较小的子类，然后用一个凝聚 一j 的层次聚类算法通过反复的合并子类来找到真正的聚类结果。 基于层次的文本聚类方法优点是能够产生较高质量的聚类，其缺点是在每次分 裂或是合并时都需要对任意的两个簇进行比较，时间代价较大。 ( 3 ) 基于密度的文本聚类方法 传统的基于划分的文本聚类方法和基于层次的文本聚类方法都是基于距离的方法， 这些方法仅限于发现“类圆形”类的聚类结果。因此提出了一种基于密度的文本聚类方 法，它的基本思想是只要一个区域中的点的密度大过某个阀值，就把它加到与之相 近的聚类中去。典型的基于密度的聚类方法有：d b s c a n 算法、o p t i c s 算法等。 d b s c a n 算法【3 5 l 的原理为邻近区域的密度超过某个阈值，就继续聚类，该方法 可以在存在噪音点的任何形状的数据集中发现聚类。o p t i c s 算法【36 】能够产生一个 基于类别排序的聚类结构，该算法减少了参数设置的复杂度。 基于密度的文本聚类方法优点是它是相对抗噪的，并且能够处理任意形状和大 基于复杂网络理论的文本聚类和关键词提取方法研究 小的簇；其缺点是当簇的密度变换太大时，d b s c a n 就会有麻烦；对于高维数据， 它也有麻烦，因为对于这样的数据，密度定义更困难。 ( 4 ) 基于网络的文本聚类方法 基于网络的聚类方法首先将数据空间划分成为有限个单元的网格结构，所有的 聚类操作都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很 快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单 元有关。代表算法有：s t i n g 算法、c l i q u e 算法等。 s t i n g 算法【3j 是最典型的基于网络的聚类方法，该方法基于网络的分辨率，将 空间区域划分为矩形单元。c l i q u e 算法【3 9 】对于高维数据的聚类十分有效，该算法 结合了基于密度的聚类方法和基于网络的聚类方法。 基于网络的文本聚类方法优点是具有很快的处理速度；其缺点是只能发现边界 是水平或垂直的聚类，而不能检测到斜边界。聚类的精度取决于网格单元的大小。 ( 5 ) 基于模型的文本聚类方法 基于模型的方法给每一个聚类假定一个模型，然后去寻找一个能很好的满足这 个模型的数据集。基于模型的聚类方法主要有两类：统计学方法和神经网络方法。 基于模型的方法在很多领域如文本聚类等都得到了广泛的应用，并取得的一定 的效果。在文本聚类中也有很多的方法应用了这项技术：自组织特征映射 ( s e l f - o r g a n i z a t i o nf e a t u r em a p ，s o m ) ，从神经网络的角度出发进行文本聚类；在针 对向量数据的处理中较为流行的高斯混合模型( m i x t u r eo f g a u s s i a n s ) ；对于高维文 本聚类效果很好的混合多项式( m i x t u r eo f m u l t i n o m i a l ) 等等。这些方法都是通过为 簇对象建立某种模型，并且对模型进行优化来完成聚类【4 们。 这种方法也可以基于标准的统计数来自动决定聚类的数目，考虑噪声数据或孤 立点，从而产生健壮的聚类方法。 2 2 文本关键词提取 它是文本分类、聚类、信息检索和自动摘要生成等技术的基础。典型的文本关键词 提取方法是将文本的特征词提取出来后，根据某种规则计算各特征词的权重，按照特征 词的权重确定能够反映文本主题内容的关键词。现有的文本关键词提取方法具体描述如 下： ( 1 ) 基于语言分析的方法 基于语言分析方法的基本思想是：对文本进行取词、分词，结合语义词典衡量特征 词的重要程度。h u l t h 结合c h u n k 识别和短语识别等语法分析方法提取文本的关键词【4 2 1 。 辽宁师范大学硕士学位论文 该方法优点是比较简单，需要的基础资源少，实现简单，关键词提取准确。该方法 的缺点是对语义词典的依赖性较强，面临语义词典的建立和语义词典的维护问题1 4 引，同 时需要考虑词语的语义语法等，考虑词语数量的增大和更新，这些都会影响该方法提取 的准确一| 生 4 4 , 4 5 1 。 ( 2 ) 基于统计的方法 基于统计方法的基本思想是：利用统计的方法提取文本的关键词，需要考虑关键词 在文本中出现的位置，该方法是一种无监督的关键词提取方法，执行起来比较简单【4 6 1 。 基于统计的文本关键词提取方法主要包括基于词频的文本关键词提取方法1 47 ，基于 t f i d f 的文本关键词提取方法【4 8 1 ，基于词的同现信息的文本关键词提取方法【4 9 1 ，基于 p a t t r e e 的文本关键词提取方法【5 0 】，以及利用上述方法的结合方法等【5 。 基于统计的关键词提取方法的优点：能够高效地识别未登录词：无需人工构造词典； 需要的基础资源少，对语言资源的依赖性弱：不受语言类型与句型的限制。 基于动机的关键词提取方法的缺点：计算量大；提取结果会有意义不完整的字符串， 导致准确率不高；低频词不能被提取出来；需要大量的原始文本。 ( 3 ) 基于结构的方法 基于结构方法的基本思想是：根据关键词主要来源于文本的固定位置，因而从文本 的相应的位置和文本的标题中提取文本的关键词【5 2 1 ，从文本的摘要中提取文本的关键词 f 5 3 】，从h t m l 文件的标签处提取关键词1 5 4 】等。 ( 4 ) 基于机器学习的方法 2 0 世纪7 0 年代，s a l t o n 将机器学习的技术应用到文本关键词提取研究中【5 5 1 。该方 法的主要是将文本的关键词提取问题看为分类问题，通过训练文本集获得文本集模型， 对文本进行关键词提取。典型的模型有最大熵模型【5 6 】、贝叶斯模型【5 7 1 、s v n 模型1 5 8 1 、 决策树模型【5 9 1 等。还有将关键短语抽取问题转化为序列标记问题，并利用条件随机场 ( c o n d i t i o n a lr a n d o mf i e l d ，c i 强) 进行关键词提取。 ( 5 ) 基于复杂网络的方法 近几年来，基于复杂网络的文本关键词提取研究受到了广泛的关注，该方法根据特 征词之间的联系，构建一个复杂网络，通过验证复杂网络的小世界特征，根据复杂网络 相关理论衡量关键词的权重，提取文本的关键词【2 3 2 5 1 。但该方法存在没有解决网络连通 性问题，计算量大等问题。 2 3复杂网络 近年来，复杂网络理论的研究越来越受到广大学者的关注。复杂网络可以看成是由 基于复杂网络理论的文本聚类和关键词提取方法研究 一些节点和连接节点之间的边组成，在现实世界中复杂网络以各种形式存在，如人和人 之间的人际关系，生物学中研究的神经网络、蛋