（计算机应用技术专业论文）web文本分类研究及应用.pdf

武汉理工大学硕士学位论文 摘要 伴随着i n t e r n e t 的飞速发展，w e b 上出现了海量的、异构的、半结构化的、 动态的信息资源，并且在这些w e b 信息中有8 0 以上的信息是以w e b 文本的形 式存在的。如何从这些浩如烟海的w e b 信息资源中寻找并获取有价值的信息和 知识模式，已经成为信息处理领域的一个亟待解决的问题。w e b 文本分类可以有 效的解决上述问题，它起源于 t c 技术( 自动文本分类技术) ，是w e b 文本挖掘 的关键组成部分；w e b 文本分类可以提高用户进行网上信息搜索的效率，可以对 搜索结果进行分门别类，帮助用户快速的对目标知识进行定位，并且能够从中 抽取有价值的知识。 本文在分析w e b 挖掘和w e b 文本挖掘的研究现状和存在问题的基础上，主 要研究了w e b 文本分类关键技术、常用文本分类方法和基于粗糙集和k n n 的混 合w e b 文本分类方法，主要研究工作包括： ( 1 ) 介绍w e b 挖掘和w e b 文本挖掘的基础理论和相关知识，分析w e b 文本 挖掘和w e b 文本分类的研究背景、现状和存在的问题。 ( 2 ) 对w e b 文本分类过程中的关键技术：文本预处理、分词技术、文本的 表示、权重的计算、特征提取和降维技术，进行详细的分析和讨论：分析和讨 论影响分类性能评价的五个因素和几种常用的分类方法质量评价方法。 ( 3 ) 讨论几种常用的文本分类方法：k n n 分类法、基于v s m 的向量距离分 类法、贝叶斯分类法、支持向量机分类法和决策树方法等，对这些方法的分类 理论进行介绍，分析和比较这些分类方法的优缺点。 ( 4 ) 提出一种基于粗糙集和k n n 的混合文本分类模型。利用粗糙集的属性 约简理论降低了文本分类过程中的向量维数，使用一种基于分明矩阵的属性约 简算法，特征选择过程采用互信息量计算方法并对该混合算法进行了实验， 同时结合传统的k n n 方法对该混合算法进行比较，验证该算法的可行性。 关键词：w e b 文本挖掘，w e b 文本分类，粗糙集，k n n ，属性约简 亟堡望至盔堂堡主堂垒鲨塞 一a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to fi n t e r a c t 。t h e r ea r ea 1 删a n t ，i s o m e r i c ， s e m i s t r u c t u r e da n dd y n a m i ci n f o r m a t i o nr e s o u r c e so nw 曲a m o n gt h e s ew e b i n f o r m a t i o n a b o v e8 0p e r c e n te x i s ti nt h ef o r mo fw 曲t e x t h o wt os e e ka n dg a i n t h ev a l u a b l ei n f o r m a t i o na n dk n o w l e d g em o d e lf r o mt h e s ev a s tw 曲i n f o r m a t i o n r e s o u r c e s ，h a v ea l r e a d yb e c o m et h eq u e s t i o nu r g e n t l ya w a i t e dt o b es o l v e di nt h e i n f o r m a t i o np r o c e s s i n gd o m a i n t h eq u e s t i o n sm e n t i o n e da b o v ec a nb er e s o l v e d e f f e c t i v e l yb yw e bt e x tc l a s s i f i c a t i o n ，w h i c ho r i g i n sf r o ma t c ( a u t o m a t i ct e x t c l a s s i f i c a t i o n ) ，a n di st h ek e yc o n s t i t u e n to fw e b t e x tm i n i n g i tc a nc l a s s i f ys e a r c h r e s u l t s ，w h i c hn o to n l ye i l l r l a n c e st h ee f f i c i e n c yo fs e a r c hf o rw e bu s e r s ，b u ta l s o i m p r o v e st h ea b i l i t yo fl o c a l i z a t i o nt og o a lk n o w l e d g e ，a n de x t r a c t st h ev a l u a b l e k n o w l e d g e o n b a s i s o f a u a l y z i n g t h e p r e s e n tr e s e a r c hs i t u a t i o n a n de x i s t i n g q u e s t i o n o f w e b m i n i n ga n dw e b t e x tm i n i n g ，t h i st h e s i sm a i n l ys t u d i e st h ee s s e n t i a lt e c h n o l o g i e so f w e bt e x tc l a s s i f i c a t i o n t h ec o m l n o nt e x tc l a s s i f i c a t i o nm e t h o d sa n dt h em i x e d m e t h o do fw e bt e x tc l a s s i f i c a t i o nb a s e do nr o u g hs e ta n dk n n n 圮m a i nr e s e a r c h w o r k sa r es h o w na sf o l l o w s ( 1 ) i n t r o d u c et h eb a s i ct h e o r ya n dt h er e l e v a n tk n o w l e d g eo fw e bh l i i l i n ga n d w e bt e x tm i n i n g ，a n da n a l y z et h er e s e a r c hb a c k g r o u n d , t h ep r e s e n ts i t u a t i o na n dt h e e x i s t i n gq u e s t i o n so ff 绐6t e x tm i n i n ga n df 恸t e x tc l a s s i f i c a t i o n ( 2 ) a n a i y z et h ee s s e n t i a lt e c h n o l o g i e sd e t a i l e d l yi nt h ep r o c e s so fw e bt e x t c l a s s i f i c a t i o n ，s u c ha sp r e p r o c e s s ，p a n i c i p l et e c h n o l o g y , t e x te x p r e s s i o n ，w e i g h t c o m p u t a t i o n , f e a t u r es e l e c t i o na n de x t r a c t i o n ，d i m e n s i o nd e s c e n d i n gt e c h n o l o g y f i v ei n f l u e n c ef a c t o r sf o re v a l u a t i n gc l a s s i f i c a t i o np e r f o r m a n c ea n ds e v e r a lc o m m o n l y a p p r a i s a lm e t h o d so f c l a s s i f i c a t i o nm e t h o d sa r ed i s c u s s e d ( 3 ) d i s c n s ss e v e r a lg e n e r a lt e x tc l a s s i f i c a t i o nm e t h o d s ：k n n ，v e c t o rd i s t a n c e m e t h o db a s e do nv s m ，b a y e sc l a s s i f i c a t i o n ，s u p p o r tv e c t o rm a c h i n ec l a s s i f i c a t i o n ， d e c i s i o nt r e ea n ds oo n ，a n a l y z ea n dc o m p a r et h ea d v a n t a g e sa n dd i s a d v a n t a g e so f t h e s ec l a s s i f i c a r l o nm e t h o d s i i 蓝堡堡三盔堂堡主堂垡堡塞 一一 ( 4 ) p r o p o s eo n ek i n do fm i x e dc l a s s i f i c a t i o nm o d e lo fw e b t e x tb a s e do nr o u g h s e ta n dk n n u s i n gt h et h e o r yo fa t t r i b u t e sr e d u c t i o no fr o u g hs e t ，d i m e n s i o no f v e c t o rc a nb er e d u c e di nt h ep m o e s so ft e x tc l a s s i f i c a t i o n , a n du s eo n ek i n do f s i m p l i f i e da l g o r i t h mf o ra t t r i b u t e sr e d u c t i o nb a s e do nd i s t i n c tm a t r i x i nt h ep r o c e s s o ff e a t u r es e l e c t i o n t h em e t h o do fm u t u a li n f o r m a t i o ni su s e d as e d e so f e x p e r i m e n t sh a v eb e e nd o n e ，a n d t h er e s u l t ss h o wt h a ts u c hm i x e da l g o r i t h mi s f e a s i b l ec o m p a r e dw i t ht r a d i t i o n a lk n nm e t h o d k e y w o r d s ：w e bt e x tm i n i n g ，w e bt e x tc l a s s i f i c a t i o n ，r o u g hs e t ，kn e a r e s t n e i g h b o r ，a t t i b u t e sr e d u c t i o n l l i 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究背景和意义 随着i n t e r n e t 及其相关技术的飞速发展，互联网上出现了海量的、异质的 w e b 信息资源，在这些庞大的信息资源中，蕴含着具有巨大潜在价值的知识。人 们迫切需要能够从w e b 上快速、有效地发现资源和知识的工剐”。于是功能强大 的搜索引擎问世了( 如g o o g l e 、a l t av i s t a 和b a i d u 等) ，这些搜索引擎可以 按照知识的种类进行分门别类建立索引，有效的减轻了人们从海量的信息资源 中寻找有价值信息的负担。但是，由于网络信息的爆炸式增长，搜索引擎的覆 盖率有限，其查全率低：同时，大多数搜索引擎都是基于全文的检索，不能达 到赋词标引的效果，也导致查准率较低。再者，绝大多数搜索引擎智能化水平 低，不能有效地提供个性化用户服务；加之最重要的一点是，搜索引擎的目的 在于定位w e b 上的资源，就w e b 上的知识发现而言，搜索引擎不能够胜任。 为了从海量数据中发现有效、新颖、潜在有用、可最终理解的模式，数据 库领域引入了数据挖掘( d a t am i n i n g ) 口】。但是，数据挖掘的主要对象是结构化 的数据仓库( d a t aw a r e h o u s e ) ，对于w e b 上的异质、非结构化信息，并不能直 接应用数据挖掘的技术。为了解决这个问题，人们将传统的数据挖掘技术跟w e b 技术相结合形成了现在的w e b 挖掘技术口】，w e b 挖掘作为一个具有挑战性的新课 题被提了出来。并得到了业界人士的广泛关注。另外研究发现，在海量的w e b 信息资源中，有8 0 以上的信息是以文本的形式存在的，因此隶属于w e b 内容 挖掘的w e b 文本挖掘显得尤为重要。 w e b 文本挖掘 4 1 就是从w e b 文档和w e b 活动中发现、抽取感兴趣的潜在的有 用模式和隐藏的信息的过程。w e b 文本挖掘和通常的平面文本挖掘有类似之处， 但是，w e b 文档中的标记给文档提供了额外的信息，可以借此提高w e b 文本挖掘 的性能，w e b 文本挖掘是文本挖掘的主要研究内容。w e b 文本挖掘对我们充分利 用w w w 资源很有帮助，可以使用户比较准确找到需要的资料；同时还可以帮助 用户节约搜索时间，提高w e b 文档的利用价值等。w e b 文本挖掘可以对w e b 文档 集合的内容进行总结、分类、聚类、关联分析以及趋势预测等。 武汉理工大学硕士学位论文 w e b 文本分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合中每个 文档归入一个预先定义的类别之中。这样，用户在浏览w e b 文档时，就不会因 为纵横交错的超链接而“迷路”，而是基于一种主题分类的指导。目前，y a h o o 还是基于人工手工来对w e b 上的文档进行分类，这种作法存在弊端：一是耗费 了大量的人力和物力，二是由于个人的主观因素导师分类结果存在不一致现象： 同时大大降低了索引数目。另外由于互联网的飞速发展，w e b 上大量的文本信息 急剧增加，这种超出想象的信息增长迫切需要更高效更智能化的文本分类技术 的产生，从而使得分类的正确率提高，保证检索结果的查全率和准确率。 随着w e b 文本分类技术在搜索引擎技术、数字图书馆技术、信息过滤、信 息检索、互联网信息监控等领域的广泛应用，w e b 文本分类的研究已经成为信息 处理的一个前沿课题，有着广泛的应用前景和重要的研究意义【4 】【5 l 【6 】川。 1 2 课题研究现状 1 2 1w e b 文本挖掘的研究现状 以w e b 文本为对象的文本挖掘被称为是w e b 文本挖掘。w e b 文本挖掘属于 w e b 内容挖掘的范畴，可以对w e b 上大量文档集合的内容进行文本检索、概括、 分类、聚类、关联分析、趋势预测和网络导航等。 ( 1 ) 文本检索主要研究对整个文档文本信息的表示、存诸、组织和访问， 即根据用户的检索要求，从数据摩中检索出相关的信息资料。目前存在三种检 索方法：布尔模型是简单常用的严格匹配模型，如清华大学的中国学术期刊( 光 盘版) 采用就是布尔模型；概率模型利用词条问和词条与文档问的概率相关性 进行信息检索，如美国马萨诸塞大学开发的i n q r e r y 文本检索系统【4 】；向量空间 模型在于将文档信息的匹配问题转化为向量空间中的矢量匹配问题处理，如美 国康乃尔大学基于向置空间模型开发了s m a r t 文本检索系统【5 1 。 ( 2 ) 文本概括是指从w e b 文档中抽取主要的信息，从而形成关于文本内容 的简洁摘要。又称为自动摘要翻。例如，搜索引擎在向用户返回查询结果时，通 常需要给出文档的摘要，使用户在浏览全文之前可以快速了解文档的主要内容。 目前，绝大部分搜索引擎采用的方法是截取文档中出现检索词频次最高的几行 武汉理工大学硕士学位论文 或者几句话作为摘要，并不考虑检索词位置和匹配长度问题，因此摘要的效果 很差。 ( 3 ) 文本分类是w e b 文本挖掘的一项重要技术，是指将w e b 文档集合中每 个文档归入一个预先定义的类别之中。近年来涌现出了大量的适合于不同应用 的分类算法，如：基于归纳学习的决策树( d t ，d e c i s i o nt r e e ) 【8 】、基于向量空 间模型的k 最近邻( k n n ，kn e a r e s tn e i g h b o r ) 1 9 1 1 1 0 】f l l 】、基于概率模型的b a y e s 分类器色) t o l l l l 】【13 1 、神经网络( n n ，n e u r a ln e t w o r k ) 【1 4 1 、基于统计学习理论的支 持向量机( s ，s u p p o r tv e c t o rm a c h i n e ) 方法) 【1 2 l 【1 5 】【1 6 1 等。 ( 4 ) 文本聚类与分类的不同之处在于，聚类没有预先定义好的主题类别， 它的目标是将文档集合分成若干个簇，要求同一簇内文档内容的相似度尽可能 地大而不同簇间的相似度尽可能地小。聚类方法主要有：划分方法、层次方 法、基于密度的方法、基于网格的方法和基于模型的方法等。 ( 5 ) 关联分析最早被应用于“货篮予”的研究，这里是指文档之间以及文 档集合中不同词语之问的关联关系，即不同的几个词语出现在同一篇文档中的 概率研究。例如，b r i n 提出了一种从大量文档中发现一对词语出现模式的算法。 并用来在w e b 上寻找作者和书名的出现模式，从而发现了数千本在a m a z o n 网站 上找不到的新书籍【1 7 t 。 ( 6 ) 趋势预测( 也称为分布分析) 是指通过对w e b 文档的分析，得到特定 数据在某个历史时刻的情况或将来的取值趋势。f e l d m a n 【l7 】等人使用多种分布模 型对路透杜的几万多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交 易之间的相对分布，揭示了一些有趣的趋势。还可以通过分析w e b 上出版的权 威性经济文章，对每天的股票市场指数进行预测，取得了良好的效果。 ( 7 ) 网络导航：文本挖掘技术可以通过分析用户的网络行为等，帮助用户 更好地寻找有用信息，一个典型的例子是c 删的w e bw a t c h e r 【1 8 】。这是一个在 线用户向导，可以根据用户的实际点击行为分析用户的兴趣，预测用户将要选 择的链接，从而为用户进行导航。 1 2 2w e b 文本分类的研究现状 ( 1 ) 文本分类方法的研究现状 武汉理工大学硕士学位论文 在w e b 出现之前，人们已经对文本自动分类问题进行了大量的研究，形成 了文档自动分类技术。随着w e b 上海量的文本信息的增加，文档自动分类技术 的处理对象从普通的文档扩展到了w e b 文本。很显然，文档自动分类技术也成 为w e b 文本分类技术的基础。 国外对于文本自动分类的研究开展较早，5 0 年代末，h p l u h n 在这个领域 进行了开创性的研究，提出了基于词频统计思想的文本自动分类方法。1 9 6 0 年， m a r o n 发表了关于自动分类算法的第一篇论文，随后以k s p a r k 、g s a l t o n 以及 k s j o n e s 等人为代表的众多学者也在这一领域进行了很有成效的研究工作【l ”。 目前国外的文本分类研究已经从实验性阶段进入到了实用化阶段，并在邮件分 类，电子会议等方法取得了广泛的应用，其中较为成功的有麻省理工学院为白 宫开发的邮件分类系统和卡内基集团为路透社开发的c o n s t r u e 系统【l ”。 国内对于文本自动分类的研究起步较晚，1 9 8 1 年，侯汉清教授对计算机在 文本分类工作中应用作了探讨和阐述【1 9 1 。此后，我国陆续研究产生了一些文本 分类系统【2 0 】，其中有具有代表性的有上海交通大学研制的基于神经网络算法的 中文自动分类系统，清华大学的自动分类系统等等。同时在不同的分类算法方 面也展开了广泛的研究和实现，中科院计算所的李晓黎、史忠植等人应用概念 推理网进行文本分类【2 l l ，召回率达到9 4 2 ，准确率达到9 9 4 。中国科技大 学的范焱等人在k n n 、贝叶斯和文档相似性研究的基础上提出了一个超文本协调 分类器【如】，正确率接近8 0 9 6 ，它的特点是适当的考虑了h t m l 文本中结构化信息。 复旦大学和富士通研究中心的黄营菁、吴立德等人研究了独立语种的文本分类 2 2 1 ，并以词汇和类别的互信息量为评分函数。考虑了单分类和多分类，最好的 召回率为8 8 8 7 。上海交通大学的刁倩、王永成等人结合词权重和分类算法进 行分类类1 2 0 l ，基于v s m 的封闭式测试实验中分类正确率达到9 7 。 目前，一些比较成熟的文本分类算法已经被应用到了w e b 文本分类中，其 中有基于v s m 的向量距离法、贝叶斯分类算法、k n n 分类算法、支持向量机分类 算法、决策树分类算法和神经网络分类算法等等1 2 0 1 1 2 3 ，近些年还出现了基于粗 糙集合理论的文本分类算法洲和一些结合多种方法的混合分类方法嘲【2 6 1 1 2 7 1 。 ( 2 ) 分类关键技术的研究现状 在对w e b 文本进行分类的过程中，包括几个关键步骤：文本预处理、分词、 权重计算、特征提取、降维技术，这些关键技术的研究和实现对最终的分类算 4 武汉理工大学硕士学位论文 法都有一定程度上的影响，下面将对分词、权重计算、特征提取和降维技术的 研究现状做简单介绍。 a ) 分词的研究现状 汉语分词是中文文本分类的一个基础环节。汉语不像英语那样，词与词之 间存在明显的分词标记，如空格、换行和标点符号：而汉语是一种无明显词间 间隔的语言。词与词之间没有分割标记和界限，因而存在一个如何分词的问题 就是分词技术。 汉语自动分词是机器翻译、文献标引、智能检索、自然语言理解与处理的 基础，也是中文文本分类的一个关键的环节。自从8 0 年代初自动分词被提出以 来，有众多的专家和学者为之付出了不懈的努力，涌现了许多成功的汉语分词 系统，主要有北京航空航天大学研制的c d w s 和c w s s 分词系统，分词速度为2 0 0 字每秒【2 们。清华大学黄昌宁、马晏等开发的s e 6 系统，分词速度为2 5 8 字每秒， 正确率为9 9 3 矧。东北大学姚天顺建立的基于规则的汉语分词系统：南京大 学王启祥等人实现的w s 蜊分词系统刚。中科院计算所研制出的汉语词法分析系 统i c t c l a s 等等阿j 。 汉语自动分词系统的实现及效果依赖于分词理论与方法。目前国内分词系 统所采用的或者正在研究的方法基本上分为三类：机械分词、基于理解的分词 和基于统计的分词。 权熏计算的研究现状 文本的基本元素是词、词组和短语，文本经预处理和分词后，抽取能表示 文本的特征项组成文本的特征向量形式，y ( d ) = ( 五，( d ) ，五，w 2 ( d ) ，瓦，w a d ) ) 其中彤表示对应特征项的权重。特征项的权熏综合反映了该特征项对标识 文本内容的贡献度和文本之间的区分能力。 常用的特征项权重计算函数有以下几种：布尔函数、开根号函数、w i d f 函 数、著名的t f i d f 公式法例；其中t f - - i d f 函数基本思路是使用频率因子t f ( t e r mf r e q u e n c y ) 进行特征项的赋权，同时还要考虑文档集因子i d f ( i n v e r s e d o c u m e n tf r e q u e n c y ) ，体现出查询内容与文档的相关度大小，一般采用使用出 现频率的倒数来计算， i d f = o g ( n n j ) ，其中n 为文档集合，n j 为查询内 容在文档中出现的次数。作为一种应用比较广泛的权重计算方法- - t f - - i d f 公式 法，也存在不足之处，一方面，传统的特征权重算法存在明显的不足。因为t f - - i d f 是将文档集作为整体来考虑的，特别是其中i d f 的计算，并没有考虑到特 武汉理工大学硕士学位论文 征项在类间和类内的分布情况。如果某一特征项在某个类别大量出现，而在其 它类别出现很少，这样的特征项的分类能力显然是很强的。但这在t f - - i d f 算 法中是无法体现的。另一方面，同样是集中分布于某一类别的不同特征项，类 内分布相对均匀的特征项的权重应该比分布不均匀的要高。因为如果某一特征 项只在某个类别的一两篇文档中大量出现，而在类内的其它文档中出现得很少， 那么不排除这一两篇文档是该类别中特例的情况。因此这样的特征项不具备代 表性。权重相对较低。对于这种情况，传统的t f i d f 算法也不能很好地处理。 于是，关于词权计算方法的研究也有了很多新的成果和方法，如文献【3 0 】中 提出的基于t f i d f 的改进方法，文献【3 l 】中提出了一种基于文本集密度的权重 计算方法，文献1 3 2 】提出一种对t f i d f 的改进方法t f - i d f - i g 文本表示方法， 在文献【3 3 】提出了一种基于s h a n n o n 信息熵的词权重算法，关于这些改进或新方 法的具体内容可以参考具体文献。权重的计算只能视具体情况而定，至今仍没 有普遍使用的“最优公式”，也需要我们在这个方面进行进一步的研究。 ( d 特征选择的研究现状 特征选择就是从特征集t = ， 中选择一个真子集t = ，f ? )。其 中，j 为原始特征集的大小， j 为选择后的特征集大小。选择的准则是经特征 选择后能有效提高文本准确率。选择没有改变原始特征空间的性质，只是从原 始特征空间中选择了一部分重要的特征，组成一个新的低维空间。 文本分类中，用于特征选择的统计量大致有：特征频度，文档频度，特征 熵，互信息，信息增益， x 2 统计量，特征权，期望交叉熵等【3 4 1 3 5 j f 3 6 1 1 3 7 1 。这些 统计量从不同的角度度量特征对分类所起的作用。 目前，也出来了一些新的特征选择方法，如低损降维方法、频率差方法、 b a y e s 准则法、f 1 值准则法和f i s h e r 简便量法等【3 8 】。 1 2 3 需要进一步研究的问题 目前园内对w e b 文本分类的研究还没有到达一个成熟的阶段，其中还存在 许多待解决和研究的问题，如： ( 1 ) 分词是影响文本分类的重要因素之一，分词的速度和准确率与最终的 分类结果密切相关。尤其是w e b 上不断出现新词汇。对分词理论的创新和词典 的构造都提出了较高的要求。 6 武汉理工大学硕士学位论文 ( 2 ) 目前还没有发现“最佳”的特征选择方法，针对中文w e b 文本分类的 组织特点，需要结合特定的特征选择，因此在使用不同分类算法时如何选择最 佳的特征选择方法也是我们需要深入研究的问题。 ( 3 ) 由于中文文本分类起步晚和中文不同于英文的特性，目前中文w e b 文 本分类还没有标准的开放的文本测试集，各研究者大多使用自己建立豹文本集 进行训练和测试，其分类结果没有可比性，不利于交流和提高。 ( 4 ) 目前存在多种成熟的文本分类算法，大部分分类系统都是应用某一种 分类算法，分类性能受到制约。针对这些算法的各自的优缺点，我们是否可以 找到更高效的混合分类方法，从而达到扬长避短，也是我们正在和今后研究工 作的重点。 1 3 本文研究工作和内容组织 1 3 1 本文研究工作 本文的主要研究工作有以下几点： ( 1 ) 分析w e b 文本挖掘和w e b 文本分类的研究现状和存在的问题。 ( 2 ) 对w e b 挖掘和w e b 文本挖掘的基本理论和相关知识进行概述和总结， 提出一个w e b 文本挖掘系统框架。 ( 3 ) 详细分析w e b 文本分类过程中的关键技术：文本预处理、分词技术、 文本的表示、权重的计算、特征提取和降维技术：讨论影响分类性能评价的五 个因素和几种常用的分类方法质量评价方法。 ( 4 ) 讨论几种常用的分类方法，对这些分类方法的优缺点进行总结和比较。 ( 5 ) 提出一种基于粗糙集和k n n 的混合文本分类模型，利用粗糙集的属性 约简理论降低了文本分类过程中的向量维数，使用一种基于分明矩阵的属性约 简算法，特征提取过程中使用互信息量方法，并对该混合算法进行了实验，并 结合传统的k n n 方法对该混合算法进行比较，验证该算法的可行性。 1 3 2 本文内容组织 本文有六章组成 武汉理工大学硕士学位论文 第1 章绪论本章说明课题的背景和研究意义，分析w e b 文本挖掘和w e b 文本分类的研究现状，其中在w e b 文本分类的研究现状中主要分析w e b 文本分 类方法和文本分类关键技术的研究现状，然后总结w e b 文本分类领域需要进一 步研究和解决的问题，最后给出论文的主要研究工作和组织结构。 第2 章w e b 文本挖掘本章首先对w e b 挖掘的定义、过程、难点和分类进 行详细的介绍，比较w e b 挖掘与信息检索的不同之处，对w e b 挖掘的应用领域 进行总结；然后对w e b 文本挖掘的定义、意义和主要研究内容进行概述。最后 还给出一个w e b 文本挖掘系统框架。 第3 章w e b 文本分类本章主要介绍三个方面的内容，在简单介绍文本分 类定义和分类过程之后，首先对文本分类过程中涉及到的关键技术作了详细的 介绍和研究分析，其中包括文本预处理、分词技术、文本的表示、权重的计算、 特征提取和降维技术：然后对分类方法质量评价进行分析，列出影响分类方法 质量的五个因素和几种常用的分类方法质量评估方法：准确度一召回率曲线。 分类准确率( p r e c i s i o n ) ，分类召回率( r e c a l l ) 以及f l 测试值等。 第4 章w e b 文本分类方法研究与实现本章首先讨论几种常用的文本分类 方法，最k 近邻分类法、基于v s m 的距离分类法、朴素贝叶斯分类法和支持向 量机法，对这些分类方法的分类原理进行了阐述，并对这些分类方法的优越性 和缺点也作出比较，还列出其他的一些分类方法，如决策树分类法、神经网络 分类法等。然后介绍粗糙集的理论知识，对粗糙集中的信息系统，决策表和属 性约简等相关知识作了概述；鉴于粗糙集的约简理论能够大大缩减文本分类过 程中的向量维数，从而降低了计算复杂度，提高了分类效率，提出了一种基于 粗糙集和k n n 的混合文本分类模型；并对每个关键步骤进行详细的介绍，其中， 分词部分使用基于统计的分词方法并出了分词过程的部分源代码；特征提取部 分采用了互信息最计算方法：在决策表的属性约简步骤中，使用一种基于分明 矩阵的属性约简算法；最后我们对该混合算法进行了实验，并结合传统的k n n 方法对混合算法进行了比较，实验证明基于粗糙集和k n n 的混合分类方法是具 有应用可行性的。 第5 章结论与展望本章是全文的总结，首先对本文的研究工作进行了总 结和回顾，然后说明了需要进一步研究的内容和亟待解决的问题，并探讨和展 望了本课题未来的研究方向。 武汉理工大学硕士学位论文 第2 章w e b 文本挖掘 随着i n t e r n e t 的飞速发展，w 厢上的页面以一种惊人的速度在增长。在这 些大量、异质的w e b 信息资源中，蕴含着具有巨大潜在价值的知识。为了帮助 人们有效地使用这些知识，陆续有一些功能强大的搜索引擎问世了。这些搜索 引擎在给人们带来很大便利的同时也暴露出搜索结果不能很好地满足用户需求 的问题。为此，需要开发比信息检索层次更高的新技术。解决这些问题的一个 途径就是将数据挖掘技术用于w e b 信息挖掘，从中抽取人们感兴趣的、潜在的 有用模式和隐藏的知识，我们称其为w e b 挖掘技术。在这些海量的w e b 信息资 源中，有8 0 以上的信息是以文本的形式存在的。目前，面向文本的w e b 挖掘 技术一w e b 文本挖掘也日益受到了更多人的关注。本章首先给出了w e b 挖掘的定 义和分类，并介绍了目前w e b 挖掘的应用领域；然后讲述了w e b 文本挖掘的有 关知识，包括定义、分类、方法和应用领域，其中对w e b 文本挖掘方法和应用 领域作了很详细的介绍 2 1w e b 挖掘 简言之，w e b 挖掘就是数据挖掘与w e b 技术相结合的一种技术，这里首先给 出其详细的定义和其分类。 2 1 1w e b 挖掘定义 数据挖掘是一个交叉学科领域，是人工智能、机器学习与数据库技术相结 合的产物，受数据库系统、统计学、机器学习、可视化和信息科学等多个学科 影响，它作为知识发现过程的一个特定步骤，是对数据及数据间关系进行考察 和建模的方法集，应用一序列技术从大量数据中提取人们感兴趣的、隐含的、 潜在有用的信息和知识，表示为概念( 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 r t e r n s ) 等形式。 w e b 挖掘是数据挖掘在w e b 上的应用，它也是- - i 1 综合性学科，涉及数据挖 掘、机器学习、模式识别、人工智能、统计学、自然语言处理、计算机网络技 术、信息检索等领域。 武汉理工大学硕士学位论文 w e b 挖掘是指从大量非结构化、异构的w e b 信息资源( 包括w e b 页面内容、 页面之间的结构、用户访问信息、电子商务信息等) 中应用数据挖掘方法以帮 助人们从www 中提取有效的、新颖的、潜在可用的及最终可理解的知识( 包 括概念、模式、规则、规律、约束及可视化等形式) 的非平凡过程。 这里需要提到的是，w e b 挖掘与传统的数据挖掘有许多相似之处。但相比之 下也有许多独特之处。首先，w e b 挖掘的对象是大量、异质、分布的w e b 文档。 其次，w e b 在逻辑上是一个由文档节点和超链构成的图，因此w e b 挖掘所得到的 模式可能是关于w e b 内容的，也可能是关于w e b 结构的。此外，由于w e b 文档 本身是半结构化或无结构的，缺乏机器可理解的语义，而数据挖掘的对象局限 于数据库中的结构化数据，并利用关系表格等存储结构来发现知识，因此有些 数据挖掘技术并不适用于w e b 挖掘，即使可用也需要建立在对w e b 文档进行预 处理的基础之上。这样，开发新的w e b 挖掘技术，以及对w e b 文档进行预处理 以褥到关于文档的特征表示，也成为w e b 挖掘的一个研究内容。 通过w e b 挖掘，最初的目的是用于提高用户在w e b 上信息的查询速度和精 度，提高搜索引擎的效率；另外还可以从大量w e b 页面提取出我们需要的有用 的知识，得到关于群体用户访问行为和方式的普遍知识，用以改进w e b 服务方 设计，还可以从用户访问行为、频度、内容中提取用户的特征，为用户定制个 性化的界面，从而展开有针对性的电子商务活动等等。 2 1 2 w e b 挖掘与数据挖掘、信息检索的关系 w e b 挖掘是对数据挖掘的一种新的发展和应用，但又不同于传统的数据挖掘 1 1 【4 】【2 们。其区别在于： ( 1 ) w e b 挖掘韵对象是海量、分布、动态、异质的w e b 文档，与传统的存 储于数据库中的结构化的数据不同； ( 2 ) w e b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 挖掘所 得到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的； ( 3 ) w e b 数据具有半结构化或非结构化特征，使得这些信息数据难以清晰 地用数据模型加以表示，且缺乏机器可理解的语义，而数据挖掘的对象局限于 数据库中的结构化数据。因此有一部分数据挖掘技术并不适用于w e b 挖掘，即 使可用也需要建立在对w e b 文档进行预处理的基础上。因此w e b 挖掘需要用到 l o 武汉理工大学硕士学位论文 更多的有别于传统数据挖掘的技术。 从原理上讲w e b 文本挖掘属于检索一类，但有别于信息检索”l 4 1 2 0 i 。w e b 数 据挖掘与w e b 信息检索是两种不同的技术。其区别主要表现在以下几个方面： ( 1 ) 方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求； 而挖掘是随机的，其结果独立于用户的信息需求，也是用户无法预知的。 ( 2 ) 目的不同。信息检索的目的在于帮助用户发现资源，即从大量文档中 找到满足其查询请求的文档子集：而挖掘是为了揭示文档中隐含的知识。 ( 3 ) 着眼点不同。信息检索着重于文档中显式存储的字词和链接；而挖掘 试图更多地理解其内容和结构。 ( 4 ) 评价方法不同? 信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 来 评价其性能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少。而 挖掘采用收益( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等来衡量所发 现知识的有效性、可用性和可理解性。 ( 5 ) 使用场合不同。有时信息检索系统返回太多的结果以致用户无法一一 测览，有时用户没有明确的信息需求，有时用户希望发现文档集合中所具有的 结构、趋势、含义，在这些场合下，就需要使用挖掘技术。尽管w e b 挖掘是比 信息检索层次更高的技术，但它并非用于取代信息检索技术，二者相辅相成， 各有所长，各有适用的场合。同时利用w e b 挖掘的研究成果可提高信息检索的 精度和效率，改善检索结果的组织，使信息检索系统发展到一个新的水平。 2 1 3w e b 挖掘的难点 w e b 上有海量的数据信息，怎样对这些数据进行复杂的应用成了现今数据 库技术的研究热点。数据挖掘就是从大量的数据中发现隐含的规律性的内容， 解决数据的应用质量问题。充分利用有用的数据，废弃虚伪无用的数据，是数 据挖掘技术的最重要的应用。相对于w e b 的数据而言，传统的数据库中的数据 结构性很强，即其中的数据为完全结构化的数据，而w e b 上的数据最大特点就 是半结构化。所谓半结构化是相对于完全结构化的传统数据库的数据而言。显 然，面向w e b 的数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。 ( 1 ) 异构数据库环境 武汉理工大学硕士学位论文 从数据库研究的角度出发，w e b 网站上的信息也可以看作一个数据库，一个 更大、更复杂的数据库。w e b 上的每一个站点就是一个数据源。每个数据源都是 异构的，因而每一站点之间的信息和组织都不一样，这就构成了一个巨大的异 构数据库环境。如果想要利用这些数据进行数据挖掘。首先，必须要研究站点 之间异构数据的集成问题，只有将这些站点的数据都集成起来。提供给用户一 个统一的视图，才有可能从巨大的数据资源中获取所需的东西。其次，还要解 决w e b 上的数据查询问题，因为如果所需的数据不能很有效地得到，对这些数 据进行分析、集成、处理就无从谈起。 ( 2 ) 半结构化的数据结构 w e b 上的数据与传统的数据库中的数据不同，传统的数据库都有一定的数据 模型，可以根据模型来具体描述特定的数据。而w e b 上的数据非常复杂，没有 特定的模型描述，每一站点的数据都各自独立设计。并且数据本身具有自述性 和动态可变性。因而，w e b 上的数据具有一定的结构性。但因自述层次的存在， 从而是一种非完全结构化的数据，这也被称之为半结构化数据。半结构化是w e b 上数据的最大特点。 ( 3 ) 解决半结构化的数据源问题 w e b 数据挖掘技术首要解决半结构化数据源模型和半结构化数据模型的查 询与集成问题。解决w e b 上的异构数据的集成与查询问题，就必须要有一个模 型来清晰地描述w e b 上的数据。针对w e b 上的数据半结构化的特点，寻找一个 半结构化的数据模型是解决问题的关键所在。除了要定义一个半结构化数据模 型外，还需要一种半结构化模型抽取技术，即自动地从现有数据中抽取半结构 化模型的技术。面向w e b 的数据挖掘必须以半结构化模型和半结构化数据模型 抽取技术为前提。 2 1 4 w e b 挖掘分类 w e b 上的数据主要包括以下几种： ( i ) w e b 页面 w e b 页面数据包含文本和多媒体信息( 图像、语音、图片) 。 ( 2 ) 服务器日志数据 用户浏览w e b 服务器时，产生三种类型的日志文件s e r v e r l o g s ，e r r o r l o g s 武汉理工大学硕士学位论文 和c o o k i e l o g s ，用于记录用户访问的基本情况。 ( 3 ) w e b 页面超链接数据 这类数据描述了文档之间的联系，同时为用户浏览w e b 站点提供了可用的路径。 ( 4 ) 在线信息 这是传统的关系数据库结构数据，如客户登记信息等，存储电子商务信息。 将它们和访问日志集成，有助于更好的提高w e b 挖掘的准确度。 当前根据处理对象的不同，w e b 挖掘一般分为三大类：w e b 内容挖掘( w e b c o n t e n tm i n i n g ) 、w e b 访问信息挖掘( w e bu s a g em i n i n g