（应用数学专业论文）基于特征词的文本聚类算法研究.pdf

河南大学研究生硕士学位论文笔i 页 摘要 随着计算机网络的高速发展，各种各样的文本信息如潮水般不断涌现，呈指数 级增长，导致人们对信息的搜寻、过滤和管理困难，因此对文本数据的管理和分析 就变得空前重要。快速高质量的文本聚类技术可以将海量的文本信息分成有意义的 若干簇，这种技术能够提供导航、浏览机制，改善检索性能。因此对文本聚类技术 的研究已经成为文本数据挖掘中一个非常重要的研究方向。 聚类技术作为文本数据挖掘的核心技术之一，其目标是将文本集合分成若干个 簇，要求同一簇内文本内容的相似度尽可能的大，而不同簇之间的相似度尽可能的 小。本文对文本聚类面临的“维度灾难”问题、聚类的初始优化问题和具体的文本 聚类算法进行了分析和研究。主要有以下几个方面的工作： 在分析文本聚类预处理关键技术的基础上，研究了特征项的权重计算方法并利 用特征项的位置权重信息对经典的t f i d f ( t e r mf r e q u e n e y - i n v e r s ed o c u m e n t f r e q u e n c y ，t f i d f ) 权重计算方法进行了改进，提出了p t f i d f ( p o s i t i o nt e r m f r e q u e n c y - i l l v e r s ed o c u m e n tf r e q u e n c y ，p t f i d f ) 权重计算方法。用k - m e a n s 等常 用文本聚类算法和f l - m e a s u r e 等聚类有效性评价指标验证了改进后的权重计算方 法p t f i d f 在提高聚类结果有效性上的作用。 针对文本聚类过程中面临的“维度灾难”问题，提出了一种特征降维处理方法 t o p n 方法，并从聚类效果评价角度验证了t o p n 方法对文本聚类的有效性。 最后结合权重计算方法p t f i d f 和t o p n 方法，本文在基于划分的聚类算法的 基础上提出了基于t o p n 特征词的文本聚类算法，通过测试数据对不同算法进行了 对比实验分析，本文算法显示出了较高的稳定性和准确率。 关键词：文本挖掘；文本聚类；特征降维；特征词 a b s t r a c t a sc o m p u t e rn e t w o r ki s d e v e l o p i n gr a p i d l y ，m a n a g e a n d a n a l y z e t h et e x t i n f o r m a t i o nh a st u r ni n t oc o n c e r ni s s u eb e c a u s eo ft h ei n c r e a s i n ge x p o n e n t i a lo ft e x t i n f o r m a t i o ni sc o n t i n u a l l ya p p e a r a n c ew i t hm u l t i f a r i o u sf o r m ，i tb r i n go nd i f f i c u l t yi n i n f o r m a t i o ns e a r c h i n g ，i n f o r m a t i o nf il t e r i n ga n dm a n a g e m e n t h i g hq u a li t ya n dh i g h s p e e dt e x tc l u s t e r i n gt e c h n o l o g yw i l ld i s t i n g u i s ht h el a r g en u m b e r so f t e x ti n f o r m a t i o n i n t os o m es i g n i f i c a t i v ec l u s t e r t h i st e c h n i q u ec a l lp r o v i d e n a v i g a t i o n ，b r o w s e a n d i m p r o v et h es e a r c h e sp e r f o r m a n c e h e n c et h er e s e a r c ho f t h et e x tc l u s t e r i n gt e c h n o l o g y h a v ea l r e a d yb e c a m eo n eo fa l l - i m p o r t a n tp a r ti nt e x td a t am i n i n g t e x tc l u s t e r i n gt e c h n o l o g ya m o n gt h ec o r et e c h n o l o g yo fd a t am i n i n g ，t h ea i ma t d i v i d et h et e x ta g g r e g a t ei ns o m ec l u s t e rm e a n w h i l er e q u i r et h ec o n t e n to fo n ec l u s t e r m u s tr e s e m b l eb ya l lm e a n sa n dt h ec o n t e n to fd i f f e rc l u s t e rm u s th i g h l y d i s s i m i l a r i t y t h ea i mo ft h i sr e s e a r c hp a p e rt h e r e f o r ef o c u so na n a l y z i n ga n dr e s e a r c ht h e c u r s e so f d i m e n s i o n ”，o p t i m i z eo fc l u s t e r i n gi n i t i a l i z a t i o na n dt e x tc l u s t e r i n ga l g o r i t h m i nt e x t c l u s t e r i n g t h er e p o r ti st h e r e f o r ep r o d u c e di n t os e v e r a lw a y s t oa d d r e s se a c hk e yt a s k ： a n a l y z i n gt h ec o r et e c h n i q u eo ft e x tc l u s t e r i n gp r o c e s s ，r e s e a r c h i n gt h e c h a r a c t e r i t e m sw e i g h tc a l c u l a t i o nm e t h o da n du s i n gt h ep o s i t i o nw e i g h ti n f o r m a t i o no f c h a r a c t e r i t e mt ob e t t e r m e n tt h ec l a s s i c a lt f - i d fw e i g h tc a l c u l a t i o n b r i n gf o r w a r dp - t f - i d f w e i g h tc a l c u l a t i o nm e t h o d k - m e a n sa l g o r i t h ma n df 1 一m e a s u r ee t c c l u s t e r i n gv a l i d i t y e v a l u a t eg u i d e l i n et ov a l i d a t et h ev a l i d i t ye f f e c t i n w e i g h t c a l c u l a t i o nm e t h o da t p - t f i d fa f t e ra m e l i o r a t e dd u et ot h ee x p e r i m e n t p u tf o r w a r das o r to fc h a r a c t e rd e c l i n ed i m e n s i o nm e t h o dc a l l e dt o p nm e t h o d si n a l l u s i o nt ob ef a c e dw i t h “c u r s e so fd i m e n s i o n ”i s s u ed u r i n gc l u s t e r i n gp r o c e s s m o r e o v e ru s ec l u s t e r i n gv a l i d i t yv a l i d a t et op r o v et h ev a l i d i t yf o rt e x tc l u s t e r i n gb yt o p n m e t h o d e v e n t u a l l y , c o m b i n ew e i g h tc a l c u l a t i o nm e t h o dp t f i d fa n dt o p nm e t h o dt h i s p a p e rb a s eo nd i v i s i o r yt e x tc l u s t e r i n gb r i n gf o r w a r dt h ea l g o r i t h mf o rt e x tc l u s t e r i n g b a s e do nf e a t u r ew o r d s a l s ov i ac o m p a r ee x p e r i m e n td a t at e s t i n ga n dv a r ya l g o r i t h m 河南大学研究生硕士学位论文第1 i i 页 a n a l y s i s ，t h ea l g o r i t h ms h o w sp r e f e r a b l ep e r f o r m a n c e k e yw o r d s ：t e x tm i n i n g ；t e x tc l u s t e r i n g ：f e a t u r ed i m e n s i o nr e d u c t i o n ：f e a t u r e w o r d s 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究旮勺课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究戍栗，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过备勺材料。与我一同工作的同事对本研究所做酌任何贡献均已在论文中作 了明确的说明并袁示了谢意。 尸 学位申请八，i 学位论变作者) 釜名：登壁 nf j 钧d 7 年d 月 目 关于学位论文著作权使用授权书 本人经河南大学审核 比准授子硕士学位。作为学位论文的作者，本人完全 了解并同意河南穴学有关保留、漩用，学往论盘桶要求。即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学住论文( 纸质文 本和电子文本) 以供公众检索、查阅本。人授权河南：大学出于宣扬、展览学校 学术发展和进行学术交流等静钠可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解奢后适用本授权书) l 学住获得者( 学住论文作者) 签名：屋垡 0 2 007 年勿月 日 学位论文指导教师釜名： 河南大学研究生硕士学位论文第1 页 第1 章绪论 本章首先阐明本文所选课题的研究背景及其所具有的研究价值，对文本数据 挖掘的含义、研究内容和面临的课题进行简要介绍，最后综述本文的主要研究工 作。 1 1 研究背景和选题意义 网络的发展，网络信息的膨胀，使得电子形式的信息量的飞速增长，如电子 出版物，电子邮件，w e b 页面( 它可被视为一个巨大的互联的动态文本数据库) 等， 文本数据库得到迅速的发展。传统的信息检索技术己不适应日益增加的大量文本 数据处理的需要。在如今这个信息激增的年代，网上的搜索引擎动辄返回成千上 万条相关的检索结果，由于大量的信息是按文本方式存在的，用户需要有关的工 具完成不同文档( 在本文中对文本与文档不加以区别) 的比较，以及文档重要性 和相关性排列，或找出多文档的模式和趋势。怎样在浩如烟海的信息中找出真正 自己感兴趣的话题就必须进行文本挖掘，文本挖掘( t e x tm i n i n g ，t m ) 成了数据挖 掘的一个很有前途的研究方向。而文本分类技术由于有训练集的监督，实现起来 准确率高而得到更多的发展，目前也有了很多成熟的理论和技术。但相对于文本 聚类技术来说，文本分类技术由于仍需要手工分类生成的训练集，而显得智能化 程度不高。因此，文本聚类技术具有很高的研究价值。 文本聚类是一种有效的文本挖掘方法，能从大量文本数据中发现潜在的知识 和规律，它既是一个知识获取技术，也是一种文本处理过程。对文本聚类进行研 究具有重要的意义，下面分几个方面来探讨一下文本聚类研究的意义。 1 、文本的聚类处理是文本有效管理的基础 文本在i n t e r n e t 上是信息资源的一个主要形式，面对这样一个信息海洋人们往 往会陷入窘迫的境地：一方面收到太多的信息无从选择和消化，淹没在繁杂的信息 中；另一方面是信息迷失，人们难于找到自己真正所需的信息。因此，能够快速 高效地获取所需要的信息是每个人的迫切要求。在这种情况下，对大量的信息自 动地提取其概念空间，提供给入一个清晰的框架，帮助人们进行信息的检索和分 第2 页河南大学研究生硕士学位论文 类则显得必不可少。围绕文本信息这一资源开展的各种学术研究和业界应用非常 活跃，如近些年来所出现的各种i n t e m e t 搜索引擎、数字图书馆、电子商务等，这 些领域的研究者在进行信息检索和分类的研究上取得了令人可喜的进展，但仍然 存在着许多堕待解决的问题，即处理效果不能令人满意。在一定程度上，人为地 干预成分占的比较大。需要将数据挖掘技术引入文本的检索和分类领域。而文本 聚类作为文本挖掘的基础工作将尤为显得重要。 2 、文本聚类是文本挖掘的自身需要 所谓的文本挖掘就是以文本作为数据的处理单元，从文本无序性、多样性、 广泛性中找出可以利用的、有一定关系的、作为信息指导性的潜在模式的过程。 而在这个过程中，必然要将纷繁冗杂的文本信息按照某种特定的方式有序地排列。 其中也不乏有一个体系结构存在，这个层次结构作为类别的合理展示必不可少。 而且，利用计算机对海量的文本聚类及类别标识，是文本挖掘自身的需要，为进 一步进行其他途径的挖掘提供了很好的利用效果。 3 、文本聚类的有效标识是海量i n t e m e t 信息检索的有效手段 信息检索是指从大量的文档集合中找到与查询请求相关的、恰当数目的文档 子集。要使检索的结果准确而且精确，就需要对检索的对象进行准确分析，在进 行抽象的过程中起到界定范围的作用；而目前的网上信息检索却远不能达到这种 效果，经常是搜索出成千上万条纪录，远没有达到准而精的效果。因此要对网页 做一个适当而全面的类归并，这不但为使用者提供了方便，而且还有利于信息资 源的合理存储。现在的网页大都是人工的进行归类，面临浩瀚的信息海洋，这样 下去必将耗费大量的人力资源。况且人不是机器，长期从事单一而冗杂的事件， 必将导致错误的出现。利用机器自动地从事这方面任务已经成为迫切的需要。 1 2 国内外研究现状 国外对文本挖掘的研究开展比较早【l 】，早期的信息抽取技术就是文本挖掘的雏 形。他们在文本挖掘中的文本分类技术、关键词的自动获取和半结构化信息提取 等相关的信息抽取领域进行了较为深入的研究，并取得了不少令人瞩目的研究成 果1 2 】【3 】【4 】。 近年来，国外的文本挖掘研究进展较快，许多技术已经进入实用化阶段，在 邮件分类、电子会议、信息过滤等方面取得了广泛的应用。一些研究机构的研究 河南大学研究生硕士学位论文第3 页 成果即各种文本挖掘应用软件也已经在商业领域得到了很好的应用，例如i b m 的 文本智能挖掘机、a u t o n o m y 公司的核心产品c o n c e p ta g e n t s 和m e g a p u t e r 的 t e x t a n a l y s t 等。 相对于国外，我国对文本挖掘的研究起步较晚，1 9 9 8 年，我国国家重点基础 研究发展规划首批实施项目中，将文本挖掘的研究列为“图象、语音、自然语言 理解与知识挖掘”中的重要内容。国内对文本挖掘技术的研究机构主要集中在高 等院校、科研院所和信息公司，并且也取得了不错的成果f 5 】，例如： 1 、中科院计算机语言信息工程中心所研究的汉语分词、自然语言接口、句法 分析、语义分析、音字转换等； 2 、清华大学电子工程系研究的手写汉字识别、汉字识别多分类器集成； 3 、上海交通大学计算机系研究的语句语义、自然语言模型、构造解释模型、 范例推理等； 4 、哈尔滨工业大学计算机系研究的自动文摘、手写汉字识别、自动分词等； 5 、东北大学的词性标注、中文信息自动抽取、汉语文本自动分类模型等。 国外在文本聚类方面的研究也取得了很多的成就【6 】。文献7 认为文本集中每个 单独的词对不同的簇并不具有完全相同的重要性，提出一种新的特征选择算法 t c ( t e r mc o n t r i b u t i o n ，t c ) 。文献8 - 9 认为在进行文本聚类时，常常会因为文本中 含有过多的“通用词”和过少具有区分度的“核心词 而导致聚类结果的精确度 不高，提出使用基于语义过滤模型的文本聚类算法。文献1 0 1 2 在进行文本聚类时 充分考虑用户对聚类的要求，提出在聚类过程中参考用户的先验知识，实现交互 式聚类，从而获得更好的聚类结果。文献1 3 提出c o c l u s t e r i n g 算法，主要从文本 的表示方式入手，通过提出新的文本表示方法进行聚类。文献1 3 提出的聚类方法 a s l ( a d a p t i v es u b s p a c ei t e r a t i o n ，a s l ) 主要使用了一种优化的迭代方法，对每个聚 类进行子空间建模和重新分配每个数据点到每个类中，同时对如何预测聚类的个 数进行了研究。文献1 4 将层次聚类算法和e m ( e x p e c t a t i o nm a x m i z a t i o n ，e m ) 算法 混合起来进行文本聚类。文献1 5 则使用高斯混合模型( g a u s s i a nm i x t u r em o d e l ， g m m ) 和e m 算法结合聚类。文献1 6 1 7 引入本体的概念，提出首先对本文集的词 构建本体，然后基于本体结构进行文本聚类。 国内在文本聚类方面的研究也有很多成绩，文献1 8 提出模糊概念图的模型来 描述词语间的关系，在聚类过程中引入概念知识，提出基于模糊概念图的文本聚 类算法。文献1 9 将群体智能聚类模型运用于文本聚类，提出了基于群体智能的 第4 页河南大学研究生硕士学位论文 w e b 文档聚类算法。文献2 0 针对文本数据高维度和稀疏空间的特点，提出一种基 于语义内积空间模型的文本聚类算法。文献2 1 通过在不同的聚类结果上使用有监 督特征选择的方法，然后从这些特征中选择出最为重要的- d , 部分特征进行聚类， 从而提高文本聚类的质量。 1 3 文本数据挖掘概述 文本挖掘是近几年来数据挖掘领域的一个新兴分支，也是当前一个非常活跃 的一个研究领域。从技术上层面上来讲，它可以说是数据挖掘和信息检索这两门 学科的交叉。文本挖掘与传统数据挖掘的差别主要两者所处理的数据之间的巨大 差异。传统数据挖掘所处理的数据是结构化的，如关系数据库中的数据、事务数 据、数据仓库的数据，这些数据的特征数目一般不会超过几百，而文本数据是没 有结构的或者是一种半结构化的，在转换为特征矢量后特征数通常都达到成千上 万甚至几十万。所以，文本挖掘在采用传统数据挖掘技术的同时，又有自己鲜明 的特性。 文本挖掘作为数据挖掘的一个分支，它把文本型信息源作为分析的对象，利 用定量计算和定性分析的方法，从中寻找信息的结构、模型、模式等各种隐含的 知识。文本挖掘又是一项综合技术，涉及数据挖掘、计算机语言学、信息检索、 自然语言管理知识管理等诸多领域。 1 3 1 文本挖掘的含义 文本挖掘是数据挖掘领域的一个新兴分支，它也被称为文本数据挖掘( t e x t d a t am i n i n g ) 旧j 、文档挖掘( d o c u m e n tm i n i n g ) 或文本知识发现( k n o w l e d g ed i s c o v e r y i nt e x t u a ld a t a b a s e ) t 2 3 1 。最早由r o n e nf e l d l n a n 等人提出【2 4 1 ，其含义为：文本挖掘 即文本数据库中的知识发现，是从大量文本的集合或语料中发现隐含的，令人感 兴趣的，有潜在使用价值的模式和知识。随着文本型信息源的迅速增加，特别是 互联网的发展，文本信息已经成为一种重要的知识来源。由于文本信息存贮量大、 变化快，从中获取知识十分困难，文本挖掘因此得到了越来越多的重视。 从技术上说，文本挖掘是一个交叉的研究领域，它涉及到信息检索、自然语 言处理、机器学习等多个领域的内容。文本挖掘与传统数据挖掘的差别在于文本 河南大学研究生硕士学位论文第5 页 数据与一般数据的巨大差异。传统数据挖掘所处理的数据是结构化的，如关系的、 事务的、数据仓库的数据，其特征数目通常不超过几百个。而文本数据可能是高 度非结构化的，如w w w 上的网页；也可能是半结构化的，如e m a i l 消息和一些 x m l 网页，转换为特征矢量后特征数将达到几万甚至几十万。 所以，文本挖掘既采用了很多传统数据挖掘的技术，又有自己的特性。不同 的研究者从各自的研究领域出发，对文本挖掘的含义有不同的理解，不同应用目 的文本挖掘项目也各有其侧重点。最常用的文本挖掘技术有： 1 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) ：它模仿了生物神经网络，是一 种通过训练来学习的非线性预测模型，可以完成分类、聚类、特征挖掘等多种挖 掘任务。 2 、决策树( d e c i s i o nt r e e ) ：它主要是用树形结构来表示决策集合这些决策 集合通过对数据集的分类产生规则典型的决策方法有分类回归树c a r t 一般用于 分类规则的挖掘 3 、遗传算法( g e n e t i ca l g o r i t h m ) ：通过基于生物进化概念而设计的一系列 过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了应 用遗传算法，需要把挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能 力。 4 、最近邻技术( n e a r e s t n e i g h b o r ) ：通过k 个最与之相近的历史记录的组 合来辨别新的记录，有时也称这种技术为k 最近邻方法，这种技术可以用作聚类、 偏差分析等挖掘任务。 5 、规则归纳( r u l ei n d u c t i o n ) ：通过统计方法归纳、提取有价值的i f t h e n 规则。规则归纳技术被广泛使用，例如关联规则的挖掘。 6 、可视化( v i s u a l i z a t i o n ) ：采用直观的图形方式将信息模式文本关联或趋 势呈现给决策者，决策者可以通过可视化技术直观地分析文本关系。 1 3 2 文本挖掘与数据挖掘 数据挖掘是指从“给定数据 中抽取出隐含的、以前未知的、潜在有用的知 识的过程。这里的“给定数据”可以是关系数据库、大型数据仓库、文件系统、 w e b 页面集合或其它任何数据集合，当然也包括文本集合。因此可以将文本挖掘 看作是数据挖掘的一种，或将文本挖掘定义为数据挖掘在文本数据中的应用。迄 第6 页河南大学研究生硕士学位论文 今为止，数据挖掘研究的大部分工作集中在结构化数据上，如存储在关系数据库 中的数据。而文本挖掘处理的是无结构自由文本，和处理相对“干净”与被良好 组织的数据相比，提出了许多新的挑战。作为数据挖掘的一种，文本挖掘的目标 与数据挖掘是类似的，它们均试图在大的数据集合中发现聚类、趋势、关联规则 等知识。文本挖掘还采用传统数据挖掘的技术和方法，如统计技术和机器学习方 法但从文本挖掘与传统数据挖掘的处理对象来看，文本挖掘可以看作是数据挖掘 从结构化数据到无结构数据的一次飞跃。文本数据的无结构性使得需要一个特殊 的预处理过程来抽取文本数据的主要特征。另外文本挖掘也有一些自己独特的挖 掘任务，如概念关系分析等。 1 3 3 文本挖掘研究的内容 文本挖掘不是去检索一篇文档，也不是从文档中找出一个人的名字，因为这 些信息至少对作者来说，是已经知道的信息。也就是说，文本挖掘不是大海捞针， 用英语说即为“an e e d l ei nh a y s t a c k 。文本挖掘是为了找出如：“去年发生了什 么新的事件，哪个创新导致了其他的发明? 我们所讨论的文档的主题是什么? ” 这一类问题的答案。文本挖掘主要的作用在于把信息转换成为知识。信息的含金 量很低，通过文本挖掘将非结构化资源进行重新组织、抽取、过滤和呈现。对于 最终的用户来说，就可以比较容易获取核心的概念和模式。文本挖掘包括的内容 主要包含以下几个方面。 1 、文本分类 文本分类指按照预先定义的主题类别，为文档集合中的每个文档确定一个类 别并将其归到该类别中。它是一种典型的有监督的机器学习问题，一般分为训练 和分类两个阶段。在训练阶段，先把一组预先分类过的文档作为训练集，然后对 训练集进行分析得出分类模式；在分类阶段，根据得到的分类模式将文本分到合 适的类别中。这样用户不但能够方便地浏览文档，而且可以通过限制搜索范围来 使查询文档更容易、快捷。目前，用于英文文档分类的分类方法比较多，用于中 文文本分类的方法较少，主要有基于统计学习理论的朴素贝叶斯分类，神经网络 算法等。 2 、文本聚类 文本分类是将文档归入到已经存在的类中，虽然文本聚类和文本分类的目标 河南大学研究生硕士学位论文第7 页 是一样的，但实现的方法不同。文本聚类是一种无监督的机器学习问题，聚类没 有预先定义好的主题类别，它是一个把一个文本集合分成若干簇的过程。聚类后， 同一簇内的文档在某种情况下的相似性极大，而簇间文档的相似性极小。如果文 本内容是文本聚类的基础，那么不同的组就对应文本集中的不同主题，可以通过 文本组中常用的术语或单词来描述该组的主题。当然聚类还可以用时间，文件的 长度等其他信息作为聚类的基础。目前常见的文本聚类算法主要有以g h a c 等算 法为代表的层次凝聚法和以k - m e a n s 等算法为代表的平面划分法。 3 、文本结构分析 为文本结构进行分析是为了更好地理解文本的主题思想，了解文本所表达的 内容以及采用的方式。最终结果是建立文本的逻辑结构，即文本结构树，根结点 是文本主题，依次为层次和段落。 4 、w 曲文本数据挖掘 在w e b 迅猛发展的同时，不能忽视信息爆炸的问题，即信息极大丰富而知识 相对匮乏。据估计，w 曲已经发展成为拥有3 亿个页面的分布式信息空间。在这 些大量、异质的w e b 信息资源中，蕴含着具有巨大潜在价值的知识。这样就需要 一种工具使人们能够从w e b 上快速、有效的发现资源和知识。 1 3 4 文本挖掘中的课题 文本挖掘目前面临的问题【5 7 】包含挖掘算法的效率和可扩展性、遗漏及噪声数 据的处理、私有数据的保护与数据安全性。文本挖掘中的许多问题并不是在该领 域内首先提出的，因此，文本挖掘与许多领域都有密不可分的关系，其中关系最 密切的包括：数据挖掘，统计学，机器学习，模式识别，神经网络，可视化，自然 语言处理等然而，许多其它领域提出的算法主要针对结构化数据，并且现在文本 挖掘要处理的文本集合可能非常大，因此要求处理速度快，随着i n t e m e t 的发展， 出现了大量的半结构化h t m l 文档，文本挖掘面临许多新的研究课题： 1 、文本的表示 由于文本挖掘处理的是自然语言表示的文本，即无结构或半结构化数据，缺 乏计算机可理解的语义，所以在进行文本聚类等文本挖掘之前，有必要对文本进 行预处理，把文本表示成为计算机可以理解的一种中间形式。虽然目前对自然语 言处理领域的研究已经取得了很大进展，但仍然没有一种中间形式能够完全表示 第8 页河南大学研究生硕士学位论文 文本语义。因此对于文本的表示是一个挑战性的问题。 2 、降维问题 通常文档的特征向量会达到数1 0 万维的大小，高维的特征可能会大大增加机 器学习时间，因此，降维是至关重要的 3 、跨语言问题 传统数据挖掘算法是以数据库中的结构化数据作为输入的，语言是独立的， 而文本挖掘是以自然语言文本作为输入的，依赖于自然语言。由于自然语言的多 样性，各种语言各有其特点，在一种语言中有效的文本挖掘功能却很可能不适用 于其他语言，待处理的文本集合中可能存在多种语言写成的文本，因此，文本挖 掘功能要考虑到找能够语言之间的语义转换，需要一个语言模型及系统的方法， 这将构成跨语言文本挖掘的重要部分。 4 、大规模文本集合 i n t e r n e t 的发展，电子商务和数字图书馆的兴起和广泛应用，永久存储设备价 格的不断降低，所以这些都使得各公司各机构储存的文本信息的规模越来越大， 电子文本库中文本数量达几十万，几百万篇之多对如此之大的文本集合进行处理， 必须有快速高效的文本挖掘算法。 5 、模式的理解和可视化显示 在许多应用中，发现的模式的可理解性对于用户来说是很重要的，提高可理 解性的解决方法通常包括以图形方式显示结果，提供相对少量的规则，或者生成 自然语言以及利用可视化技术等，提供更友好的用户界面。而目前的文本挖掘系 统主要针对有经验的专家，一般人很难使用。 6 、算法运行中参数的设定和调节 很多算法运行时需要用户设定许多参数，有些参数是很难理解的，因而也很 难正确设定，如何让算法自动选择相对较好的参数值，而且在算法运行的过程中 自动地选择相对较好的参数值，而且在算法运行的过程中自行调节参数的取值， 是很多算法能否被广泛使用的一个关键问题。 7 、算法的选择 面对多种多样的文本挖掘算法，各种算法各有其特点，如何从中选择一个适 合于具体应用的算法是一个尚待研究的问题。 8 、领域知识集成 目前的文本挖掘系统很多没有采用相关的领域知识，然而领域知识却很有用， 河南大学研究生硕士学位论文第9 页 可以帮助提高文本分析效率，所以应该考虑把领域知识集成到文本挖掘系统中。 9 、中文文本分词技术 在英语等书写中，词与词之间用空格作为固定分隔符，因而词与词之间的界 限在书面上是十分明显的，就比较容易进行分词，然而在中文文本中，词与词之 间没有明确的界限。相同的字可以出现在很不同的词中，这就给中文文本的分词 带来了很大的困难，使得中文分词是一项很难的工作，需要快速有效的技术。 1 4 主要内容及组织结构 文本聚类技术作为文本信息挖掘技术中的核心技术之一，越来越受到研究人 员的广泛关注。本文主要对文本聚类分析中所涉及的若干问题进行了比较深入地 研究。尤其对文本聚类面临的“维灾难 问题、聚类的初始化优化问题和文本聚 类算法进行了分析和研究。 本文具体内容的组织结构如下 第一章：为本文的绪论部分。首先介绍选题背景、选题意义和文本聚类的国 内外研究现状；然后阐述了文本挖掘的基本概念、研究的内容、面临的课题；最 后概述了本文的研究内容和文章的组织结构。 第二章：本章详细论述了文本聚类过程中的关键技术，包括对文本数据集进 行分词、特征选择和文本特征表示等处理，重点讨论了对特征项进行权重计算的 方法并在经典的t f i d f ( t e r mf r e q u e n c y - i n v e r s ed o c u m e n tf r e q u e n c y ，t f i d f ) 的 基础上加以改进，提出了考虑特征词的位置权重信息的权重计算方法。 第三章：本章分析和比较了文本聚类过程中常用的一些聚类方法，对每一类 聚类方法的典型算法实现过程进行了详细介绍，分析其性能和优缺点。最后还总 结了对文本聚类的结果评价常使用的评价指标。 第四章：本章主要对文本聚类过程中面临的“维度灾难”问题，提出了一种 特征降维处理方法t o p n 方法，并且结合权重计算方法p t f i d f ( p o s i t i o nt e r m f r e q u e n t y 血v e r s ed o c u m e n tf r e q u e n c y ，p - t f - i d f ) ，在基于划分的聚类算法的基础 上提出了基于t o p n 特征词的文本聚类算法，并且通过测试数据和不同的算法进行 了对比实验分析，算法显示出了较高的稳定性和准确率。 最后对本文的研究工作进行了总结，同时对研究工作中发现的一些问题和研 究不足加以说明，并对下一步需要完成的工作进行展望。 第10 页河南大学研究生硕士学位论文 第2 章文本聚类预处理关键技术的讨论 文本挖掘是近年来非常活跃的一个研究领域，而文本聚类是文本挖掘主要的 研究内容之一。文本聚类是一种无监督的机器学习。它通过对文本内容的分析， 将文本集中的文本划分成多个有意义的若干个类，使同一类中的文本的相似度尽 可能大，而不同类中的文本相似度尽可能小。在文本聚类的过程中，没有任何关 于类的先验知识，仅依靠文本集内容之间的相似性对文本进行类别划分。 文本聚类的过程主要由文本预处理、文本模型表示、文本相似度的计算、文 本聚类和对聚类结果的评价等等几个步骤组成。文本聚类过程如图2 1 所示。本文 将在第三章对一些常用的聚类方法进行介绍。 2 1 文本预处理 图2 - 1 文本聚类过程图 英l 交2 羹c 文本预处理是文本处理中最基本的过程。首先将文本按照一定的算法进行分 词，经过分词，文档变成离散的、无序的词条集合，然后对这样的词集进行停用 词处理、同义词归并等预处理。 2 1 。1 分词 中文自动分词是文本聚类的前提和基础。由于汉语句子构成的复杂性和多变 性，中文自动分词已经是目前中文信息自动处理的“瓶颈”。中文文字的处理与西 文相比，一个明显的不同就是汉语词与词之间没有明显的分隔标记。因此中文信 河南大学研究生硕士学位论文第11 页 息处理的首要问题就是要将句子中一个个词给分离出来，这就是中文分词问题。 中文分词技术属于自然语言处理技术范畴，人们对于一句话可以通过自己的 知识来明白哪些是词或者哪些不是词，但是怎么让计算机也能理解? 其处理过程 就是分词算法。 中文文本自动分词的研究从2 0 世纪8 0 年代初开始，人们对汉语的自动分词 技术研究做了很多工作，设计了许多实用、高效的算法。通常的方法主要分为机 械分词和知识分词两类。 1 、机械分词方法 这种方法又称为基于字符串匹配的分词方法，其思路是先查字典进行匹配， 然后再适当地利用部分词法规则进行歧义校正。这类方法，按扫描方向可分为正 向扫描、反向扫描、双向扫描三种；而按匹配原则又可分为最大( 最长) 匹配和 最小( 最短) 匹配；这两种匹配按增字或减字又可将其分为两种类型。 2 、知识分词法 这种方法又称为基于理解的分词法，它与机械分词方法的根本区别在于它不 仅仅只是通过词典匹配，而且还要利用词法、句法甚至语义等方面的知识。也就 是通过让计算机模拟人对句子的理解，达到识别词的效果。这种方法要比机械分 词方法更难于实现，因此目前还处在试验阶段。 目前研究中文分词的大多是科研院校，清华、北大、哈工大、中科院、北京 语言学院、东北大学等等都有自己的研究小组，而真正研究中文分词的商业公司 除了海量科技以外，几乎没有了。 目前国内比较成熟的分词系统有： ( 1 ) 北京航空航天大学c d w s _ 2 5 】( t h em o d e mw r i t t e nc h i n e s ed i s t i n g u i s h i n g w o r ds y s t e m ，c d w s ) 这是我国第一个实用性的自动分词系统，是北京航空航天 大学计算机科学与工程系于1 9 8 3 年设计实现的。 ( 2 ) 清华大学s e g 分词系统和s e g t a g 系统【2 6 】。 ( 3 ) 东北大学自然语言处理实验室n e u c s p 2 7 】 东北大学自然语言处理实验室研制的n e u c s p 具有中文分词与词性标注两项 功能。其词性分类特别详细，共分为3 0 类：普通名词、时间名词、方位名词、处 所名词、人名、地名、团体专名、机构专名、组织的专名、其它专名、动词、形 容词、区别词、副词、数词、量词、代词、介词、连词、叹词、拟声词、助词、 前接成分、后接成分、习用语、简称、语素字、非语素字、标点和字符串等。 第1 2 页河南大学研究生硕士学位论文 ( 4 ) 计算所汉语词法分析系统i c t c l a s l 2 8 1 。 中国科学院计算技术研究所在多年研究基础上，耗时一年研制出了基于多层 隐马尔可夫模型的汉语词法分析系统i c t c l a s ( 1 n s t i t u t eo f c o m p u t i n gt e c h n o l o g y ， c h i n e s el e x i c a la n a l y s i ss y s t e m ，i c t c l a s ) ，主要功能包括中文分词；词性标注； 命名实体识别；新词识别等。分词速度单机9 9 6 k b s ，分词精率高达9 7 5 8 ( 9 7 3 专家组评测结果。 计算所汉语词法分析系统i c t c l a s 同时还提供一套完整的动态连接库 i c t c l a s d l l 、c o m 组件和相应的概率词典，开发者可以完全忽略汉语词法分析， 直接在自己的系统中调用i c t c l a s ，i c t c l a s 可以根据需要输出多个高概率的结 果，输出格式也可以定制，开发者在分词和词性标注的基础上继续上层开发 本文所使用是计算所汉语词法分析系统l c t c l a s 。 2 1 2 停用词处理 停用词指的是那些出现频率很高但是对文本标识却没有太大作用的词。在文 本中包含很多停用词，但是它们对这个文本所表达的意思几乎没有任何贡献，更 多的作用在于语法上。比如中文中的：“得”、“地”、“的、“了”等；如果不对停 用词进行处理，则计算机将它们与一般的单词同等对待。由于停用词在每个文档 中几乎都具有很高的出现频率，因此在进行文本相似度计算过程中会引入很大的 误差，从而影响文本聚类的质量。所以非常有必要将这些停用词从原始的文本中 过滤出去，这个过程即称为停用词处理。停用词过滤还可以显著提高文本聚类的 效率，包括存储空间和时间。 2 1 3 同义词归并 同义词是指词义相同或相近的词，如“脚”和“足”、“计算机”和“电脑。 在文档当中，同义词往往描述的是同一个主题或者内容。在分词之后，同义词的 存在会增加文本聚类的时间复杂度，进而影响聚类学习算法的准确性。因此，应 该将同义词和近义词进行合并。预处理后将文本内容数据转换为便于计算机处理 的结构化数据的形式。 河南大学研究生硕士学位论文第1 3 页 2 2 文本特征表示 文本表示的模型常用的有：布尔逻辑模型b m ( b o o l e a nm o d e l ) ，向量空间模型 v s m ( v e c t o rs p a c em o d e l ) ，潜在语义索引l s i ( l a t e n ts e m a n t i ci n d e x i n g ) 和概率模型 p m ( p r o b a b i l i s t i cm o d e l ) 等 3 6 】【3 7 】【3 8 】。这些模型从不同的角度出发，使用不同的方法 处理特征加权、类别学习和相似计算等问题。 本文中采用的是向量空间模型v s m ，自从s a l t o n ”】等人于2 0 世纪6 0 年代末提出 v s m 并成功地应用于著名的s m a r t 系统之后，v s m 在文本分类、自动标引、信息 检索等许多领域的到了广泛的应用。近年来v s m 是在文本挖掘系统中应用较多且 效果较好的方法，它己经成为最简便、高效率的文本表示模型之一。向量空间模 型的最大优点是它在知识表示方法上的巨大优势。 2 2 1 布尔逻辑模型 布尔逻辑模型是基于集合理论和布尔代数的一种最常用的简单的检索模型， 每一个文档被表示成关键词的集合k = ( k l ，k 2 ，k t ) ，查询被表示为关键词的布尔 逻辑组合r ，用与、或、非逻辑演算符号连接起来，并用括弧指示优先次序，一个 文档当且仅当它能够满足布尔查询式时，才将其检索出来。布尔检索模型原理简 单易理解，容易在计算机上实现并且具有检索速度快的优点。但是最终给出的查 询结果没有相关性排序，不能全面反映用户的需求，功能不如其他的检索模型。 2 2 2 向量空间模型 在描述向量空间模型之前，先对以下几个概念加以说明。 1 、文档( d o c u m e n t ) 文档泛指一般的文本或文本中的片断( 包括段落、句群或句子) ，一般指一篇 文章，也可以是多媒体对象。 2 、项( t e r m ) 文档的内容特征常常用它所含有的基本语言单位( 比如字、词或短语等) 来表 示，这些基本的语言单位统称为项，即文档可以用项集( t e r m l i s t ) 表示为d ( t l , t 2 ， t 3 ，t n ) ，其中t 。是项，1 亚剑，n 为文