（计算机应用技术专业论文）基于som的文本聚类及其在搜索结果中的应用.pdf

摘要 随着信息技术的发展，以电子形式存在的文本信息已经成为人们主要的信息来 源。人们迫切需要能够从w e b 上快速、有效地发现资源和知识的工具。近年来针 对文本数据的文本挖掘已逐渐成为人们研究的新课题。其中，对于文本聚类的研 究已经引起了广泛的重视，并取得了良好的成果。 本文首先对数据挖掘流程以及数据挖掘分类和各自的研究现状及发展进行了 概括的介绍；然后结合汉语自身的相关特点详细的分析了中文文本自动聚类中所 涉及到的关键问题及其技术：接着介绍了人工神经网络技术的发展的现状和特点 及其在聚类中的应用。 人工神经网络由大量简单的基本元件一神经元相互联结，模拟人的大脑神经处 理信息的方式，迸行信息并行处理和非线性转换的复杂网络系统。本文将人工神 经网络技术和文本挖掘技术结合，并应用于搜索引擎中的结果分析中。在此基础 上提出了基于s o m 神经网络的文本挖掘模型。 关键词：文本挖掘聚类分析文本聚类特征向量s o m 神经网络 a b s t r a c r a b s tr a c t w i t ht h ed 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 , e l e c t r o n i ct e x t sh a v eb e c o m e m o r ea n dm o r ep o p u l a ra ss o u r c eo fi n f o r m a t i o n p e o p l en e e ds o m et o o lt of i n d r e s o u r c ea n dk n o w l e d g ef r o mt h ew e bu r g e n t l y t e x tm i n i n gh a db e c o m ean e w p r o m i s i n gr e s e a r c hs u b j e c t ，e s p e c i a l l yi nt e x tc l u s t e r i n g , i nr e c e n ty e a r s i nt h i sp a p e r , w ef i r s t l ym a k eag e n e r a li n t r o d u c t i o na b o u tt h ed m p r o c e s s e s ，d m c l a s s i f i c a t i o na n d i c s e a m h ，d e v e l o p i n gb a s e d o i lt h a t a f t e rt h a t ，w i t hs o r t i e c h a r a c t e r i s t i co fc h i n e s e ，w ed i s c u s ss e v e r a lp i v o t a lt o p i c so nc h i n e s et e x tc l a s s i f y i n g i nd a t a t h e n ，w ei n t r o d u c e da r t i f i c i a ln e u r a ln e t w o r ka n d a p p l y i tt ot e x tc l u s t e r i n g a r t i f i c i a ln e u r a ln e t w o r kc o m p r i s e sag r e a td e a lo fb a s i ce l e m e n t s ，n e u r a lu n i t c o n n e c t e do n ea n o t h e r i tc a ns i m u l a t eh u m a nb e i n g sb r a i nn e u r a lt od e a lw i t h i n f o r m a t i o na n di m p l e m e n t p a r a l l e lt r e a t i n ga n dn o n l i n e a rc o n v e r s i o n i nt h i sp a p e r , w e c o m p a n i e sa r t i f i c i a ln e u r a ln e t w o r ka n dt e x tm i n i n g , t h e na p p l i e di nt h ef i e l d so ft e x t m i n i n g o nt h eb a s eo fs t u d y i n g , p u tf o r w a r ds o mn e u r a ln e t w o r kb a s e dc o m p a n i e s t e x tm i n i n gs y s t e m k e y w o r d ：t e x tm i n i n g c l u s t e r i n g t e x tc l u s t e r i n gf e a t u r ev e c t o rs o m n e u r a ln e t w o r k 独创性( 或创新性) 声踢 本人声明所送交的论文尽我所知，除了文中特别加以标注和致谢中所罗列的 内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获褥 西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解 密后遵守此规定) 本人签名： 导师签名： 日期回立! 了 日期回主s 霉 第一章绪论 第一章绪论 1 1 课题背景 1 1 1 搜索引擎中的信息挖掘技术 由于目前网络搜索引擎的智能化程度未达到实用水平，人们在对网上海量信 息进行搜索，查询所需要的信息时，还无法实现对信息的准确分类，致使检索的 结果不尽人意。例如，某一用户利用“西电”进行检索时，其本意是想得到有关 西安电子科技大学的资料，但搜索引擎返回的结果大多是大量关于西电东输，西 电公司的相关信息。造成这种情况的主要原因是：现有的搜索引擎大多是基于简 单的关键词匹配。这种匹配有很大的局限性，并不麓真正理解用户的捡索意图。 因此，近年来为了实现个性化的主动信息服务，数据挖掘技术在网络信息处理中 的应用研究( 即对网络信息挖掘技术的研究) 己为人们所关注。 网络信息挖掘是指在大量训练样本的基础上，得到数据对象间的内在特征， 并以此为依据进行有目的的信息提取。例如，当信息挖掘系统发现用户感兴趣问 题是“西电”时，它就会根据用户的意图，自动过滤掉与其无关的信息，如西电 东输等，对已有的信息进行分类，以减少用户的检索时间和成本，提高效率。网 络信息挖掘与网络信息检索所采用的技术有很多相似之处，但也有本质的区别。 网络信息挖掘技术沿用了r o b o t 、全文检索等网络信息检索中的优秀成果，同时 综合运用了人工智能、模式识别、神经网络等领域的各种技术。网络信息挖掘系 统与网络信息检索的最大不同在于：它能够根据目标特征信息在网络上或者信息 库中进行有目的的信息搜寻，以获取用户个性化的信息需求。 l 、网络信息挖掘中的关键技术 目标样本的特征提取： 网络信息挖掘系统采用向量空间模型v s m ( v e c t o rs p a c em o d a l ) ，用特征词条 ( 互r 2 工) 及其权值代表目标信息。在进行信息匹配时，使用这些特征项评价 未知文本与目标样本的相关程度。特征词条及其权值的选取，称为目标样本的特 征提取，其算法的优劣将直接影响到系统的实际运行效果。 ( 矽中文分词处理： 英文句子中以空格作为固定的分隔符，而在中文句子中则没有，这就给中文 信息处理带来很大障碍。因而在进行词频统计等处理前，必须先要进行词条切分 处理。基于大型词库的机器分词法，是比较简单、有效的分词方法。在进行中文 分词处理中，充分利用已有的包含特征项的、常用词汇的通用词库，然后根据挖 掘目标建立专业的分词表，可以在保证特征提取准确性的前提下，显著提高系统 2 基于搜索；i 擎的文本聚类 的运行效率。进行词条切分时，先根据标点进行粗切分，然后再分别使用正向和 逆向最大匹配法进行细切分。在进行词频统计时，考虑到自然语言的多样性，建 立并使用相应的同义词、相关词等辅助词典，以提高信息匹配的准确度。 2 、搜索引擎使用的信息检索技术及其不足“1 目前搜索引擎使用的信息检索技术主要有：r o b o t 技术、索引技术、翻译技术、 转换技术、过滤技术、数据库技术、结果处理技术等。搜索引擎的最大优点是： 信息的覆盖面较大，信息新颖，而且在对搜索结果的相关性排列上，搜索引擎将 其认为相关性高的检索结果排列在前。但由于搜索引擎使用的信息检索技术智能 水平的限制，以及对自然语言理解的制约，因此在对网络信息的检索方面还存在 许多不足，主要由以下四个深层次的问题引起的。这四个问题都与中文词汇紧密 相关 表达的准确性：很多情况下，用户很难简单地用关键词或关键词串来准确地 表达他所真正需要检索的内容，表达困难导致了检索困难。检索出来的有用的信 息往往被海量的信息所淹没或者得到令人啼笑皆非的结果。 表达的差异性：人类的自然语言中，随着时间、地域或领域的改变，同一 概念可以用不同的语言表现形式来表达因此，对同一概念的检索，不同的用户可 能使用不同的关键词来查询，例如：“西军电”和“西电科大”。表达差异问题导 致查询结果严重不全。 词汇的孤立性：人的大脑中，概念并不是孤立存在的，它总是与其它概念 之闻存在各种各样的联系。在信息检索中，用户在捡索一个词( 表达一个概念) 时， 除了希望得到含有该概念的文档之外，总是还想得到与此概念相关的其他信息。 在传统的全文检索技术中，用户的这种愿望是实现不了的，因为检索返回的结果 都是含用户检索词的文档，而不会涉及其他相关信息。在这种检索模式下，用户 的检索词得不到概念扩展，被系统作为一个孤立的词来处理。如果用户要查询相 关的信息，那么他必须再次输入相关词汇。面我们正是要集中解决这个问题，通 过对搜索结果的再次挖掘，得到信息之间的关联，使我们的搜索不再孤立，通过 智能分析，可以得到我们想要的结果。例如当我们搜索“西电”的时候，同时会 将“西军电”，“西安电子科技大学”，“西电科大”“西北电讯工程学院”等绑定到 一起进行索引。使搜索结果不再仅仅包含用户的检索词，而进行了智能扩充。 机械匹配：这是传统搜索引擎的症结所在，“机械匹配”只是从字形上来标 识关键字，却不能从字( 词) 意上来标识关键字，比如：我要查找有关“华人”这关 键字，搜索结果中有“外籍华人”、“华人社团”、“中华人民共和国”。从常理上来 说，“外籍华人”、“华人社团”是与此相关的，但是“中华人民共和国”中的“华 人”却并不与此相关。通过这种方式匹配出来的结果往往和我们想要的差距甚远， 也不符合服务用户的需要。 第一章绪论 3 3 、论文所要研究的主要内容 通过中文分词和特征向量的建立，实现基于s o m 的文本聚类，并从聚类结果 中发现相关联的信息，实现索引结果的二次挖掘，减少不相关的结果和不准确的 结果，使搜索引擎返回的结果尽可能的接近用户的搜索要求。以便节省用户的时 间和提高搜索的效率。 1 1 2 文本挖掘的定义 文本挖掘是指从大数据集中发现有效、创新、潜在有用和最终可理解的模式 的非平凡过程，同时运用这些知识更好地组织信息以便将来参考。直观的说，当 数据挖掘的对象完全由文本这种数据类型组成时，这个过程就称为文本挖掘。 文本挖掘也称为文本数据挖掘或文本知识发现，是人工智能、机器学习、自 然语言处理、数据挖掘及相关自动文本处理如信息抽取、信息检索、文本分类等 理论和技术相结合的产物。文本挖掘的主要目的是从非结构化文本文档中提取有 用的、重要的模式和知识。可以看成是基于数据库的数据挖掘或知识发现的扩展。 文本挖掘是从数据挖掘中发展而来，因此其定义与我们熟知的数据挖掘定义相类 似。但与传统的数据挖掘相比，文本挖掘有其独特之处，主要表现在：文档本身是 半结构化或非结构化的，无确定形式并且缺乏机器可理解的语义：而数据挖掘的 对象以数据库中的结构化数据为主，并利用关系表等存储结构来发现知识。因此， 有些数据挖掘技术并不适用于文本挖掘，即使可用，也需要建立在对文本集预处 理的基础之上。 1 1 3 文本挖掘的过程 文本挖掘所要处理的文档集是非结构化或半结构化的信息，因此，我们要建 立文本特征向量，用结构化的数据来表示文档集，但是目前所存在的文档表示方 法中，存在一个共同的、难以解决的问题是文档向量具有惊人的维数，所以，特 征集的缩减在文本挖掘的过程中是一个必不可少的环节，文档向量维数缩减后， 便可以利用机器学习的各种方法来提取面向各种应用目的的知识模式。最后对获 得的知识模式进行评价，若评价结果满足一定的要求，则存储该模式：否则，重 新返回到以前的某个环节改进后进行新一轮的挖掘工作。在文本挖掘过程中，文 本的特征的建立是文本挖掘工作的基础，而文本分类和聚类是两种最基本的挖掘 方法。 4 基于搜索引擎的文本聚类 图1 1 文本挖掘的一般流程 文本预处理： 选取任务相关的文本并将其转化成文本挖掘工具可以处理的中间形式。通常 包括以下主要步骤： 1 ) 文本预处理：预处理过程针对数据集的特点和挖掘目标过滤不相关的信息， 并对文本的结构作初步处理，如中文分词，去除x m l 文档无关标记字段的数据 内容、选择h t m l 文档的相关目标字段、选择适当的特征表示( 如词语、关键词、 类别标记、术语或语法依赖树) 或必要的浅层自然语言处理、特征抽取选取等。 预处理是完成文本特征模型化之前所进行的与特征相关的必要步骤。通过预处理 来建立文档集的特征表示，将文本转化成一种类似关系数据且能表现文本内容的 结构化形式，如信息检索领域经常采用的向量空间模型就是这样一种结构化模型。 2 ) 特征集的缩减：采用一定的文本预处理表示方法对文本进行建模后，还需 根据不同的目标采用特征选取或抽取方法来降低维度( 对于基于向量空间的文本 表示模型) 或去除一些嗓音数据，只保留对表达文本内容作用较大的一些特征。具 体的特征选取方法一般都以词汇分析为基础，特征选取方法在机器学习中有过滤 和包裹器两种常用的方法。信息检索中多种特征抽取方法也可以用于特征模型的 简化过程。模型化的反馈过程是指基于专家对知识发现结果的评价和产生的知识 对模型化过程的特征甚至建模方法进行改进，以更好更快地发现预期知识。 3 ) 文本挖掘：在完成文本预处理后，可以利用机器学习、数据挖掘以及模式 识别等方法提取面向特定应用目标的知识或模式。本文主要是采用神经网络聚类 方法来进行文本挖掘。 4 ) 模式质量的评价：最后一个环节是利用已经定义好的评估指标对获取的知 识或模式进行评价。主要通过查准率和查全率进行评价，如果评价结果符合要求， 就存储该模式以备用户使用；否则返回到前面的某个环节重新调整和改进，然后 再进行新一轮的发现。 1 1 4 课题研究背景 中文信息挖掘是近年来基于传统数据挖掘应用发展出的一种结合中文分词技 第一章绪论 5 术的新兴应用技术。到目前为止，中文信息挖掘应用还未成熟，针对搜索结果优 化的研究也很少，而且也没有经过广泛的评测分析。本项目研究围绕搜索结果优 化的应用问题，从基于中文分词的处理技术入手，利用s o m 神经网络聚类的信息 获取能力，以搜索引擎的应用为主导方向，从几个方面加强了中文搜索引擎的研 究和深化。可以使我们更充分利用w w w 资源，可以使用户比较准确找到需要的 资料，节约用户检索时间，提高资源的利用价值等。 搜索引擎的检索结果却并不尽如人意，使用者输入一些关键词，一般都会得 到成千上万的检索结果，而且其中大部分页面都是不需要的无关资料。虽然有一 些技巧试图给那些有较多关键词或者罕见关键词的页面赋予更大的权重，却仍然 不能保证和用户意图最相关的页面一定被排在最前面。因此用户别无选择，只能 把检索到的页面一个一个再筛选一遍。而且关键词索引仅仅是关键词的简单匹配， 稍有不同，就查询不到了。通过我们系统的二次聚类，可以更合理的组织检索结 果，按照页面彼此之间的相似程度分为若干个类别，并通过关键词的形式反馈给 用户，用户可以迅速地扫描关键词，并选择那些和他的目标最相关的类别。通过 这种方法，可以将用户的精力主要集中到相关的知识中去。 ， 1 2 国内外研究动态 系统介绍对于搜索结果聚类的国内外的研究情况，重点突出西文应用的特点 和中文应用的特点，目前存在的具有类似结果的搜索引擎，并分析其特点和不足 之处。 国外在文本挖掘中的文本分类技术以及相关的信息抽取等领域进行了较为深 入的研究，取得了不少令人瞩目的研究成果，产生了一些可用的文本挖掘系统。 例如，自动分类新闻稿件的文本分类器。埘：自动分类w e b 页的文本分类器“3 ：自动 跟踪用户阅读兴趣的分类分析器”3 等等。这些系统大多数都建立在向量空间模型 ( v e c t o rs p a c em o d e l ) 的基础上，着重解决特征项的选择和权重、机器学习算法等 问题，以提高系统的性能和效率。至今，在以下方面取得了不错的成果： 1 、向量空间模型的研究日益成熟 s a l t o n 等人在6 0 年代末提出的向量空间模型在文本分类、自动索引、信息检 索等许多领域得到了广泛的应用，己成为最简便高效的文本表示模型之一砌。通 过不同文本挖掘系统的运行和比较表明，向量空间模型是文本分类领域大规模语 料库较好的表示模型。 2 、对特征项的选择进行了较深入的研究 对于英法德等语种，文本可以由w o r d s ，c l u s t e r so fw o r d s ，p h r a s e s ，c l u s t e r so f p h r a s e s 或其他特征项来表示，a n d r e w 和l e w i s 等学者对这些特征项进行了仔细 6 基于搜索g i 擎的文本聚类 地分析，并且在r e u t e r s 2 1 5 7 8 等标准语料库上进行试验，做出了较一致的结论： 使用优化合并后的w o r d 、作为特征项在文本分类应用中效果最佳“1 。此外，也有 不少学者正在努力突破以上特征项的选择空间，定义自己的文本表示空间，例如， s a ms c o n c 定义了一套符号系统，利用w o r d s 和附加的符号信息表示文本，也取 得了一定的成果m ，。 3 、较完整的分类算法的研究和比较 国外对于文本分类算法的研究开展得较早，也较完整。例如，对b a y e s 、k n n 、 s v m 、神经网络等算法，都有比较详细地研究和性能比较阱o ”，但是各位学者都 没有得到统一的结论，总体而言，这些算法在分类性能上差别不大，以k n n 和 s o m 稍好。 4 、存在比较标准的语料库 例如，n e w s g r o u p s i 吾料库( 约2 0 0 0 0 多篇文章2 0 个类别) ，w e b k b 语料库( 4 1 9 9 篇文章7 个类别) ，r e u t e r s 2 1 5 7 8 语料库( 2 1 5 7 8 篇文章1 3 5 个类别) 都在一定时期 较为广泛地使用。而t r e c 也提供了较为标准的语料库。 5 、较为规范的测试方法 国外学者在标准的测试语料库上也定义了较为规范的测试方法，除了传统的 测试指标外，还有一些更为细致的测试指标，例如，l e w i s 给出了一套较完整的 分析方法，不但测试系统的整体性能，而且可以较科学地分析多训练文本类和少 训练文本类的分类性能“”。 6 、己经开始研究未标记文本对文本分类系统的影响 国外学者在整理语料库的过程中发现收集及分类训练文本是极其费时、费力 的过程，因此提出在训练文本不充足的情况下如何利用未标记文本提高文本分类 系统的性能并且开展了一定的研究。 7 、逐渐将文本分类技术应用到某些特定的信息服务中 例如，将文本分类技术应用到事件跟踪系统中，为用户( 主要是新闻媒体用户) 收集与事件相关的文章，制作事件专题节目。另外，将文本分类技术应用于用户 个性化服务系统中，跟踪用户感兴趣的文章，进行类别判断，为用户提供方便地 信息服务。 国内互联网是从1 9 9 7 年开始迅速蓬勃发展起来的。国内学者从1 9 9 9 年才开 始关注网络数据挖掘，与国外相比起步较晚。北京科技大学的唐管等人，构建了 一个适用于现代远程教育的文本挖掘系统。它能充分利用w e b 站点( 远程教育站 点) 上积累的丰富文本信息，更好地服务于远程教育。该系统采用的分类挖掘算法 是向量空间的距离测度分类法，该算法与朴素贝叶斯分类算法、k 邻近分类算法 相比而言，主要是分类的算法容易实现，分类速度也比较迅速。该系统的查准率 和查全率都比较高，表现出来的算法性能比较好。中科院软件研究所、北京邮电 第一章绪论 7 大学模式识别与智能实验、微软亚洲研究院等多家研究机构也都进行着相关的理 论研究。可见，w e b 数据挖掘在国内已经逐渐引起人们的关注。但是，目前国内 在w e b 数据挖掘方面的研究还处于起步阶段。另外在中文信息挖掘上，国内也已 开展了文本挖掘方面的研究，吴军、吴立德、黄首警都进行了汉语语料自动分类 的研究，他们以字或词为特征项构成特征向量，以频率作为词的权重，利用一些 分类算法构造分类器，取得了一定的效果。但是，总的来说，在文本分类方向上 的研究相对落后，主要存在着以下一些问题： 1 、缺少统一的中文语料库 不存在标准的用于文本分类的中文语料库，各个学者分头收集自己的训练文 本集，并在此基础上开展研究，因此，系统的性能可比性不强。同时，出于财力 人力有限，中文语料库的规模普遍不大。 2 、向量空间模型的研究还不十分成熟 国内的学者，例如吴立德和黄置著也提出了如何选择特征项的问题，他们提 出可以使用字、词、概念作为特征项构建向量空间模型，并对以此为基础的文本 分类系统进行了初步的性能比较，但是在这方面的研究还没有深入的开展，尤其 是对于概念的定义不清楚，没有全面的比较和测试系统。另外，在特征项抽取算 法方面也缺少系统而深入的研究成果。 3 、测试标准不统一 在国内，由于缺少标准的用于分类的中文语料库，所以文本分类系统的性能 测试可比性较差，测试方法也比较简单，通常仅给出整个系统的准确率，很少分 析测试文档数量和质量对文本分类系统性能的影响。 4 、文本分类技术与其他信息技术尚未很好结合 国内的文本分类系统主要应用于图书馆等专业信息处理机构，在信息服务领 域，除了与搜索引擎有所结合外，文本分类技术与其它信息技术还没有很好的结 合，还没有得到充分的应用。 总之，目前国内对文本挖掘技术，特别是文本分类技术已经进行了很多韵研 究，也取得了不少的成果，但是仍然存在很多尚待解决的问题。本文主要针对搜 索结果的特点，利用除关键词外的类信息进行聚类，提高文本分类系统的性能。 作者相信通过不断地努力，所做的工作可以对文本挖掘技术的应用有一定的价值。 1 3 本文主要研究内容 本研究的主要目标是搜索引擎搜索结果的二次挖掘与信息优化，侧重于中文 分词与数据挖掘的聚类分析两方面的问题。本研究的主要内容包括三个方面： l 、研究中文分词技术，研究其适用性与性能分析。 8 基于搜索引擎的文本聚类 2 、分析当前应用的建立空间向量的方法，并根据中文分词结果建立关键词特 征向量矩阵。并进行合并和缩减。减小其维数。 3 、研究s o m 神经网络聚类方法，完成预定义的聚类挖掘任务并验证其适用 性。 1 4 本文的组织结构 根据系统的特点，分为三大部分：文本分词，特征关键词提取，s o m 聚类。系 统介绍文本挖掘在搜索结果中的应用。 第二章数据挖掘及其聚类算法综述 9 第二章数据挖掘及其聚类算法综述 2 1 1 数据挖掘的定义 2 1 数据挖掘 数据挖掘( d a t am i n i n g ) ，是一个多学科交叉研究领域，它融合了数据库技术、 人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计 算以及数据可视化等最新技术的研究成果。经过十几年的研究，至今已有多种定 义，其中得到业界公认的是：从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中的信息和知识的过程，是提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。提取的知识表示为概念( c o n c e p t s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。这种定义主要针对的是结构数 据，如关系的，事务的，数据仓库的数据。随着数据处理工具，先进数据库技术 以及网络技术迅速发展，大量的形式各异的复杂类型的数据( 如结构化与半结构 化的数据，超文本与多媒体数据) 的不断涌现。因此数据挖掘面临的一个重要课 题就是针对复杂数据类型的挖掘，这包括复杂对象：空间数据，多媒体数据，文 本数据和w e b 数据等。 数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历 史，只不过在过去数据收集和分析的目的是用于科学研究，另外，由于当时计算 能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限制。现在，由 于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是 为了分析的目的而收集的，而是由于纯机会的( o p p o r t u n i s t i c ) 商业运作而产生。 分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价 值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大， 而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利 于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得 名。 2 1 2 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要寻找的模式类型，主要功能有：概 念描述、关联分析、分类分析和预测、聚类分析、孤立点分析、演变分析。 l 、概念描述：是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描 述不是同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对 基于搜索引擎的文本聚类 象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 2 、关联分析：数据关联是数据库中存在的一类重要的可被发现的知识。若两 个或多个变量的取值之间存在某种规律性，则称为关联。关联可分为简单关联、 时序关联、因果关联。关联分析的目的是从数据库中发现关联规则。这些关联规 则展示了给定数据集中数据项之间的潜在的联系。关联分析广泛应用于购物篮或 事务数据分析。 3 、分类分析和预测：分类找出描述并区分数据类或概念的模型，以便能够使 用模型预测类、标记未知的类。例如，建立分类模型对银行贷款的安全风险进行 分类。预测是构造和使用模型评估无标号样本类，或评估给定的样本可能具有的 属性值或值区间，预测未来的数据趋势。例如，建立预测模型对商品的销售量、 股票价格、产品合格率等进行预测。 4 、聚类分析：聚类就是将数据对象分组成为若干个类或簇，在同一族中的对 象之间具有较高的相似度，而不同的族中的对象之间差别很大。与分类不同的是， 聚类要划分的类是未知的。聚类增强了人们对客观现实的认识，是概念描述和偏 差分析的先决条件。 5 、孤立点分析：孤立点可能是度量或执行错误所导致的，也可能是固有的数 据变异性的结果。许多挖掘算法试图使孤立点的影响最小化或者排除他们，但这 可能导致重要信息的丢失，因为孤立点本身可能是很重要的。 6 、演变分析：数据演变分析描述行为随时间变化的对象的规律或趋势，并对其 建模。它包括时闻序列数据分析、序列或周期模式匹配和数据分析。 2 l3 数据挖掘过程 过程中各步骤的大体内容如下： 1 、确定数据对象 清晰地定义出要解决的问题，认清数据挖掘的目的是数据挖掘的重要一步。挖 掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数 据挖掘则带有盲目性，是不会成功的。 2 、数据准备 1 ) 数据的选择 搜索所有与需求有关的内部和外部数据信息，整理并从中选择出适用于数据挖 掘应用的数据。 2 ) 数据的预处理 研究数据的质量，为迸一步的分析做准备并确定将要进行的挖掘操作的类型。 3 ) 数据的转换 第二章数据挖掘及其聚类算法综述 得到的数据往往是半结构化的数据，并不适合直接拿来进行分析，我们需要将 数据转换成一个分析模型这个分析模型是针对挖掘算法建立的建立一个真正适 合挖掘算法的分析模型是数据挖掘成功的关键 3 、数据挖掘 对所得到的经过转换的数据进行挖掘，除了完善合适的挖掘算法外，其余一切 工作都能自动地完成。 4 、结果分析 解释并评估结果。其使用的分析方法一般根据数据挖掘操作而定，通常会用到 可视化技术。 2 2 文本数据挖掘 2 2 1 文本数据挖掘技术的定义 在实际应用中，人们所接触到的大多数信息是以文本形式存储在文本数据库中 的，由大量的文档组成，如新闻文档、研究论文、书籍、数字图书馆、电子邮件 和w e b 页面。由于电子形式的文本信息飞速增涨，文本挖掘已经成为信息领域的 研究热点。 文本数据库中存储的数据可能是高度非结构化的，如w w w 上的网页；也可 能是半结构化的，如e m a i l 消息和一些x m l 网页；而其它的则可能是良结构化的。 良结构化文本数据的典型代表是图书馆数据库中的文档，这些文档可能包含结构 字段，如标题、作者、出版日期、长度、分类等等，也可能包含大量非结构化文 本成分，如摘要和内容。通常，具有较好结构的文本数据库可以使用关系数据库 系统实现，而对非结构化的文本成分需要采用特殊的处理方法对其进行转化。 文本挖掘是个交叉的研究领域，它涉及到数据挖掘、信息检索、自然语言处 理、机器学习等多个领域的内容，不同的研究者从各自的研究领域出发，对文本 挖摇的含义有不同的理解，不同应用目的文本挖掘项目也各有其侧重点。因此， 对文本挖掘的定义也有多种，其中被普遍认可的文本挖掘定义如下： 文本挖掘是指从大量文本数据中抽取事先未知的、可理解的、最终可用的信息 或知识的过程。直观地说，当数据挖掘的对象完全由文本这种数据类型组成时， 这个过程就称为文本挖掘。文本挖掘可以对w e b 上大量文档集合的内容进行关联 分析、总结、分类、聚类、以及利用w e b 文档进行趋势预测，还可对搜索结果进行 进一步的挖掘。文本数据挖掘的一般过程：文档表示一特征提出一分类或聚类一分 析输出。 文本挖掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相类 似。但与传统的数据挖掘相比，文本挖掘有其独特之处，主要表现在：文档本身 基于搜索引擎的文本聚类 是半结构化或非结构化的，无确定形式并且缺乏机器可理解的语义；而数据挖掘 的对象以数据库中的结构化数据为主，并利用关系表等存储结构来发现知识。因 此，有些数据挖掘技术并不适用于文本挖掘，即使可用，也需要建立在对文本集 预处理的基础之上。 按照文本挖掘的对象可把文本挖掘分类为：基于单文档的数据挖掘和基于文档 集的数据挖掘： 1 、基于单文档的数据挖掘：基于单文档的数据挖掘中对文档的分析并不涉及其 它文档。主要挖掘技术有：文本摘要( t e x ts u m m a r i z a t i o n ) 、信息提取( i n f o r m a t i o n e x t r a c t i o n ) 。其中信息提取包括：名字提取( n a m e so fp e o p l e 、o r g a n i z a t i o n sa n d p l a c e s ) 、短语提取( m u l t i w o r dt e r m s ) 、关系提取等。 2 、基于文档集的数据挖掘：基于文档集的数据挖掘对大规模的文档数据进行模 式抽取。主要挖掘技术有：文本分类( t e x tc a t e g o r i z a t i o n ) 、文本聚类( d o c u m e n t c l u s t e r i n g ) 、个性化文本过滤( p e r s o n a l i z e dc o n t e n tf i l t e r i n g ) 、文档作者归属 ( a u t h o r s h i p a t t r i b u t i o n ) 、因素分析( f a c t o r a n a l y s i s ) 等。 2 2 2 文本数据挖掘分类 常用的文本挖掘分析技术有文本的特征表示、文本摘要、文本分类、文本聚类、 文本关联分析等。 1 、文本的特征表示 传统数据挖掘所处理的数据是结构化的，其特征通常不超过几百个；而非结构 化或半结构化的文本数据转换成特征向量后，特征数可能高达几万甚至几十万。 所以，文本挖掘面临的首要问题是如何在计算机中合理的表示文本。这种表示法 既要包含足够的信息以反映文本的特征，又不至于太过庞大使学习算法无法处理。 这就涉及到文本特征的抽取和选择。 2 、文本摘要 文本摘要是指从文档中抽取关键信息，并进行解释和概括。使用户不需要浏览 全文就可以了解文档或文档集合的总体内容。任何一篇文章总有一些主题句，大部 分位于整篇文章的开头或末尾部分，而且往往是在段首或段尾，因此文本摘要自动 生成算法主要考察文本的开头、末尾，而且在构造句子的权值函数时，相应的给标 题、子标题、段首和段尾的句子较大的权值，按权值大小选择句子组成相应的摘要。 文献“。1 5 3 进行了基于概念统计和语义层次分析的英文自动文摘和自动标引研究。文 献“”提出了使用中心文档来代表文档集合，使用中心词汇来表示文档的方法，并给 出了求取中心文档和中心词汇的算法。 3 、文本分类 第二章数据挖掘及其聚类算法综述 文本分类是文本挖掘中一项非常重要的任务，也是国内外研究较多的一种挖掘 技术。文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一个 类别。这样用户不仅可以方便地阅读文档，而且可以通过限制搜索范围来使文档查 找更容易。在机器学习中分类称作有监督学习或有教师归纳，其目的是提出一个 分类函数或分类模型( 也称作分类器) ，该模型能把数据库中的数据项映射到给定 类别中的一个。 一般来讲，文本分类需要四个步骤： 1 ) 获取训练文本集：训练文本集由一组经过预处理的文本特征向量组成，每个 训练文本( 或称训练样本) 有一个类别标号； 2 ) 选择分类方法并训练分类模型：文本分类方法有统计方法、机器学习方法、 神经网络方法等等。在对待分类样本进行分类前，要根据所选择的分类方法，利 用训练集进行训练并得出分类模型； 3 ) 用导出的分类模型对其它待分类文本进行分类； 4 ) 根据分类结果评估分类模型。 近年来涌现出了大量的适合于不同应用的分类算法，如：基于归纳学习的决策 树( 叨、基于向量空间模型的k 2 最近邻( - n ) 、基于概率模型的b a y e s 分类器、 神经网络( n n ) 、基于统计学习理论的支持向量机( s v m ) 方法等“”。 4 、文本聚类 文本聚类是根据文本数据的不同特征，将一个数据对象的集合分组成为多个类 或簇的过程。其目的是要使同一类别的文本问的距离尽可能小，而不同类别的文 本间的距离尽可能的大。它的分析并不依赖于已知的类标记的数据对象，通常情况 下，聚类的训练数据样本无类标记，它要划分的类是未知的，通过聚类可以产生这 种类标记。文本聚类是对给定的文本根据文本相似度进行聚类的方法。主要的聚 类方法有统计方法、机器学习方法、神经网络方法和面向数据库的方法。在统计 方法中，聚类也称聚类分析，主要研究基于几何距离的聚类。在机器学习中聚类 称作无监督学习或无教师归纳。 -， 一 文本聚类是一种典型的无教师机器学习问题，它与文本分类的不同之处在于， 聚类没有预先定义好的主题类别，它的目标是将文档集合分成若干个簇，要求同一 簇内文档内容的相似度尽可能大，而不同簇问的相似度尽可能小。 一般来讲，文本聚类包括以下几个步骤： l 、获取结构化的文本数据集：结构化的文本数据集由一组经过预处理的文本 特征向量组成。从文本集中选取的特征好坏直接影响到聚类的质量。如果选取的 特征与聚类目标无关，那么就难以得到良好的聚类结果。选取的方法应是使同类 文本在特征空间中相距较近，异类文本相距较远。 2 、根据数据的特点，选择聚类算法，得到聚类结果图。聚类的目的是获取能 1 4 基子搜索引擎的文本聚类 够反映特征空间样本点之间的相关性质。 3 、选取合适的聚类阈值。在得到聚类结果图后，领域专家凭借经验，并结合 具体的应用场合确定阈值。阈值确定后，就可以直接从结果图中得到聚类结果。 按照聚类的原理和方法，主要的聚类算法可以分为以下几类：基于划分的聚类 算法，如k - m e a n s 、e a m 、c l a ra 、c i a r a n s 、e m 等；基于层次的聚类算法， 如b i r c h 、c u b e 、r o c k 、c h e m a l o e n 、a g n e s 等；基于密度的聚类d b s c a n 、 o p t i c s 、d e n c l u e 、d b c l a s d 、g d b s c a n 等。另外还有基于网格的聚类，基 于模型的聚类等。 2 3 聚类分析 2 3 1 聚类算法简介 聚类是一种特殊的分类，聚类是分类的逆向分法，聚类把没有分类的记录，在不 知道应分成几类的情况下，按照数据内在的差异性大小，合理地划分成几类，并确 定每个记录所属类别。聚类的目的是根据类内相似性最大化，类间相似性最小化原 则合理划分数据集合，并用显式或隐式的方法描述不同的类别，聚类的意义在于把 类似的事物组织在一起。通过聚类，人们能够识别密集和稀疏的区域，因而发现全 局的分布模式，以及数据属性间的有趣关系“”“”。它采用的分类规则是按统计学的 聚类分析方法决定的。比如。面对数据库中“消费额”、“购买频率”、“收入水平” 等多个评价指标，没有办法按一个指标分类，就可以通过聚类按照数据问的自然联 系把分散的记录“聚”成几“堆”，然后再对每堆进行深入分析。 2 3 2 文本聚类算法及判断标准 传统的聚类研究主要针对的是结构数据，如关系的、事务的、和数据仓库中的 数据。然而随着信息的不断膨胀，在实际应用可获取的大部分信息是存储在文本 数据库中的，由各种数据源( 如新闻文章、研究论文、书籍、数字图书馆、电子邮 件消息和w e b 页面) 的大量文档组成。大量的有用信息淹没在文本数据的海洋之 中。传统的信息检索技术己经不能适应日益增加的大量文本数据处理的需要。典 型的大量文档中只有很少一部分与某一个体或用户相关。如果不清楚文档中的内 容，就很难快速的查询需要的信息。因此，文本挖掘就成为数据挖掘中一个日益 流行而重要的研究课题。 文本聚类的目的是为了将大规模的文本数据集分组成为多个类，并使同一类中 的文本信息之间具有较高的相似度，而不同的类之间的文本相似度低，从而方便 人们对文本信息的利用。因此文本聚类算法的好坏的判断标准应基于以下几个方 第二章数据挖掘及其聚类算法综述 面： 算法应有较高的可伸缩性，不仅在样本数据集上，而且在大规模的现实文本 数据集上都要有较好的效果。 能处理高维数据，用v s m 表示的文本数据集通常有数千维甚至上万维，因 此用于文本聚类的算法要能处理高维数据。 能发现任意形状的聚类，由于学科发展的交叉性与综合性，类与类之间的界 线越来越模糊，类的形状不局限于球状或其它凸状，这就要求文本聚类的算法能 发现任意形状的类。 输入参数与领域知识的依赖性低很多算法都需要事先给出一些参数，而在没 有先验知识的情况下，这些参数是很难确定的，且聚类结果对这些参数非常敏感， 因此要尽量避免。 对数据的输入顺序不敏感，用v s m 表示的文本中是用词汇作为特征项单位， 以词汇的词频处理值作为特征项的数值，这样，要求文本数据的输入顺序应对最 终的聚类结果无影响。 算法要有较好的处理噪声数据的能力，绝大多数现实世界中的数据库都包含 孤立点、未知数据等噪声数据，若算法对这样的数据敏感，则会降低聚类结果的 质量洲。 2 3 3 常用文本聚类算法的分析与比较 目前文献中存在着大量的聚类算法，主要的可分为基于划分的算法 ( p a r t i t i o n i n gm e t h o d ) 、基于层次的算法( h i e r a r c h i c a lm e t h o d ) 、基于密度的算法 ( d e n s i t y - b a s e dm e t h o d ) 、基于网格的方法( g r i d b a s e dm e t h o d ) 和基于模型的方法 ( m o d e l - b a s e dm e t h o d ) 五大类，每一大类有一些代表性的算法。实际应用中算法 的选择取决于数据的类型、聚类的目的和应用等。下面就文本挖掘中常用的有代 表性的聚类方法迸行分析与比较。 1 、k - m e a n s 法： 此算法以n 为参数，把n 个对象分为k 个簇，使簇内具有较高的相似度，簇 间的相似度较低。相似度为簇中对象的平均值( 被看作簇的重心) 。k - m e a n s 法的 流程如下：首先随机地选择n 个对象，每个对象初始代表一个簇的平均值或中心； 将剩余的对象分别归到与簇中心距离最近的簇。然后重新计算每个簇的平均值； 这个过程不断重复，直到准则函数收敛。这种聚类算法比较简单，且当结果簇是 密集的，而簇与簇之间区别明显时，它的效果较好；它的时间复杂度是o ( k n t ) ，其 中n 是所有对象的数目，k 是簇的数目，t 是迭代的次数，在处理大数据集时，有 相对高的可伸缩性和高效率。但它要求用户必须事先给出n ( 要生成的簇的数目) ， 基于搜索引擎的文本聚类 而大规模文本集中，要事先确定类别数n 值是很难的。另外，此算法也不适合于 发现非凸面形状的簇或者大小差别很大的簇，对于“噪声”和孤立点数据很敏感， 少量的这类数据就会对平均值产生极大的影响o “。 2 、c u r e 法 它不用质心或对象来代表个簇，而是选择数据空间中