（计算机应用技术专业论文）基于正负关联规则的web文档分类研究.pdf

t at h e s i ss u b m i t t e df o r t h ea p p l i c a t i o no f t h em a s t e r sd e g r e eo fe n g i n e e r i n g r e s e a r c ho fw e bd o c u m e n tc i a s s i f i c a t i o n b a s e do np o s i t i v ea n d c a n d i d a t e ： n e g a t i v ea s s o c i a t i o n r u l e s s h if u f u s p e c i a l t y ：t h ec o m p u t e ra p p l i c a t i o n s u p e r v i s o r ：p r o f e s s o rd o n gx i a n g j u n s h a n d o n gi n s t i t u t eo fl i g h ti n d u s t r y , j i n a n ，c h i n a m a y , 2 0 1 0 m 4洲7 川ly k i 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。文 中引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或 成果，与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 兑 明并表示谢意。 论文作者签名：盈筵苤 学位论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属山东轻工 业学院。山东轻工业学院享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名 单位仍然为山东轻工业学院。 论文作者签名： l 导师签名： h 期：2 止年月篮r f t , 苴7 1 ：坦年月鲨同 山东轻t 业学院颂l j 学位论文 目录 摘要i a b s t r a c t i 第1 章绪论1 1 1 数据挖掘概述1 1 2w e b 文档分类概述6 1 3 本文的研究背景及意义7 第2 章w e b 文档分类的相关技术9 2 1w e b 挖掘9 2 1 1w e b 挖掘的概念9 2 1 2w e b 挖掘的分类9 2 2w e b 文本挖掘1 2 2 3w e b 文档分类l4 2 3 1w e b 文档分类的步骤1 4 2 3 2w e b 文档分类的关键技术1 5 2 3 3w e b 文档分类的算法18 2 3 4w e b 文档分类的方法的评价2 0 第3 章基于正关联规则的w e b 文档分类技术2 1 3 1 关联规则挖掘21 3 1 1 关联规则的概念2l 3 1 2 关联规贝0 挖掘算法2 2 3 2 正关联规则w e b 文档分类技术2 7 3 2 1 正关联规则w e b 文档分类的现状2 7 3 2 1 正关联规则w 曲文档分类技术2 9 第4 章负关联规则的相关技术3 l 4 1 负关联规则挖掘产生3 l 4 2 负关联舰则的定义3 2 4 3 负关联规则的算法3 2 第5 章基于正负关联规则w e b 文档分类3 7 5 1 w e b 文档预处理3 7 5 2 基于萨负关联规则w e b 文档分类3 8 5 3 实验及结果分析3 9 第6 章结论与下一步的工作4 1 参考文献4 3 致 谢：4 7 攻读硕士学位期间取得的科研成果4 9 2 ， 0 山东轻t 业学院硕i j 学位论义 摘要 关联规则挖掘是数据挖掘中重要内容之，旨在发现大龟数据中项集之问的 关联或相关关系。将关联规则挖掘技术应用于w e b 文档分类，可以更有效地组织 和管理海量的w e b 信息，更快地查找网络上的信息。然而，目前- 火多研究者在 w e b 文档分类中仅仅涉及到了正关联规则挖掘，而较少涉及负关联规则。负关联 规则可以发现项集之间的负关联火系，是对证关联规则挖掘技术的补充，将负关 联规则挖掘技术应用于w e b 文档分类，就可以发现那些负相火的w e b 文档，从而 提高w e b 文档分类的j 下确度。然而，如何把负关联规则应用j 二w e b 文档分类还是 一个新问题，为此，本文对这一问题进行了讨论，并提f 了一种基于正负关联规 则的w e b 文档分类方法。 本文介绍了目前w e b 文档分类所涉及的分类方法，并对闺内外正负关联舰则 的研究现状进行了总结，提出了一种基于正负关联规则的w e b 文档分类方法。该 方法巾首先对w e b 文档进行预处理，将非结构化的数据变成结构化数据，从而建 立起新的事务集合；然后利用a p r i o r i 算法求出频繁2 项集后，用修改后的p n a r c 模型进行规则选择，删除矛盾的关联规则，得到i f 确的正负关联规则，从而区分 出文档之问的相关性，以此来确定文档是否真正属于问一类别，并通过实验对这 个方法进行验证，证明该算法可以对w e b 文档进行i f 确的分类。 关键词：数据挖掘；负关联规则；w e b 文档分类 a s s o c i a t i o nr u l ei sa ni m p o r t a n tp a r to fd a t am i n i n g ，i si no r d e rt of i n dt h el i n k s b e t w e e ni t e m s t h e m i n i n ga s s o c i a t i o nr u l et e c h n i q u ei su s e di nw e bd o c u m e n t c l a s s i f i c a t i o n ，c o u l dm o r ee f f e c t i v e l yo r g a n i z ea n dm a n a g et h ev a s ta m o u n t so fw e b i n f o r m a t i o n ，a n dm o r eq u i c k l yf i n dt h ei n f o r m a t i o no nt h en e t w o r k h o w e v e r , t h e m a j o r i t yo fr e s e a r c h e r so n l yu s ep o s i t i v ea s s o c i a t i o nr u l ei nt h ew e bd o c u m e n t c l a s s i f i c a t i o n ，a n dl e s si n v o l v e dn e g a t i v ea s s o c i a t i o nr u l e si ni t n e g a t i v ea s s o c i a t i o n r u l e sc o u l df i n dt h en e g a t i v ea s s o c i a t i o n sb e t w e e ni t e m s e t s ，a n da l s oa t o m p l e m e n t a r v f o rp o s i t i v ea s s o c i a t i o nr u l e m i n i n g u s en e g a t i v ea s s o c i a t i o n si nw e bd o c u m e n t c l a s s i f i c a t i o nc a nf i n dt h en e g a t i v ea s s o c i a t i o n sa m o n gw e b d o c u m e n t s ，a n da l s ot o e n h a n c ew e bd o c u m e n tc l a s s i f i c a t i o na c c u r a c y h o wt oa p p l y n e g a t i v ea s s o c i a t i o nr u l e s t ow e bd o c u m e n tc l a s s i f i c a t i o ni san e w p r o b l e m ，t h i sp a p e rd i s c u s s e di t ，a n dp r e s e n t sa m e t h o do fw e bd o c u m e n t sc l a s s i f i c a t i o nb a s e do np o s i t i v ea n dn e g a t i v ea s s o c i a t i o n r u l e s t h i sa r t i c l ed e s c r i b e st h e a l g o r i t h m o fw e bd o c u m e n tc l a s s if i c a t i o n ，a n d s u m m a r i z e st h ec u r r e n ta c t u a l i t yo f p o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e si nd o m e s t i c a n do v e r s e a s ，a n dp r e s e n t sam e t h o do fw e bd o c u m e n t sc l a s s i f i c a t i o nb a s e do np o s i t i v e a n dn e g a t i v ea s s o c i a t i o nr u l e s f i r s t l y , w e bd o c u m e n t si s p r e p r o c e s s e dt oc h a n g et h e u n s t r u c t u r e dd a t ai n t os t r u c t u r e dd a t a ，i no r d e rt oe s t a b l i s han e ws e to fi t e m s ；t h e nu s e a p r i o r ia l g o r i t h mt of o r mt h ef r e q u e n t2 - i t e ms e t s ，a n du s et h em o d i f i e dp n a r cm o d e l t os e l e c tr u l e s ，a n dt h e nr e m o v e sc o n t r a d i c t o r ya s s o c i a t i o nr u l e st o g e tt h ef i g h tp o s i t i v e a n dn e g a t i v ea s s o c i a t i o nr u l e s ，s ot h er e l a t i v i t yo fd o c u m e n tc o u l db ed i s t i n g u i s h e d ，a n d c o u l dd e t e r m i n et h a tw h e t h e rt h ed o c u m e n t sa r ec o m p a r t m e n t a l i z e dt ot h es a m ec l a s s ， f i n a l l yt h r o u g he x p e r i m e n t st ov a l i d a t et h em e t h o d ，s h o wt h a tt h ea l g o r i t h mc a ni m p r o v e t h ea c c u r a c yo f w e bd o c u m e n tc l a s s i f i c a t i o n k e yw o r d s ：d a t am i n i n g ，n e g a t i v ea s s o c i a t i o nr u l e s ，w e bd o c u m e n tc l a s s i f i c a t i o n l 山东轻一i ：业学院硕卜孚位论文 1 1 数据挖掘概述 第1 章绪论 一般来说，1 t 界上任何一项发明的产生都是由需求马区动的，它是产生新事物 的动力。在实际的工作中，人们都希望这嵝海量的数据能被计算机自动地进行分 析，可以得出他们想要的结果信息，所以挖掘工具就由此产生和发展了。 从计算机的应用角度来看，经过这些年的迅速发展，计算机无论从硬件还是 网络方面的性能都得到了大幅度的提高，其次软件的技术与功能也有了飞速提 高，这样就需要软件有综合的分析功能，而不足只具备原先单纯的管理功能。现 在各个公司都想压缩自己的生产成本，可是所需要的人力资源费用这几年却一直 处于逐年增加的事念，而持续下降的是产品价格和服务，面对这样猛烈的市场竞 争，公司决策者不得不寻求减小成本的方法，采用的就是对产品与服务扩大销售 总量柬增加自己的竞争实力。另一一方面，因为过去的数据同样也会给决策者带来 参考性的意见，大量的信息每天都在充斥着我们的视野，并且数据的速度增长惊 人，如何对大量的数据进行处理，对现有众多知识技术是一个非常大的挑战。 但是现今怎样把这些数据进行处理的实用工具却涉及比较少。以前的系统只 是涉及到数掘库罩已经存在的数据，并且对它进行一些查询和简单的操作，人们 采用这个方法所能获取的信息，只是在全部数据库中占有很少一部分，然而涉及 到那些数据的整体特征描述以及对其末来变化推测的信息是藏在这些数据之后， 并且领导者们在制定未来规划的时候会起到重要的参考作用。 炒股票的人往往研究以自订股票i = | 了场取的数据，想从中发现某一股票的情况， 期望发现出一定的规律，为未来的投资做准备；书店的经理希望能从顾客的购书 清单中分析出各个年龄段顾客的阅读偏好和行为，以便能够及时变换销售策略， 进行有针对性的进货、销售；研究地质的科学家们一般都是分析各种：卫星采集的 大量信息，希望那个能找到为丌发的资源等。 数据挖掘( d a t am i n i n g ) 就足为了迎合这种要求而产生并迅速发展起来的， 可以用于丌发信息资源的一种新的数据处理技术。数据挖掘它可以从数掘库、数 据仓库或其他各种信息中，自动的抽取或者发现各种类型的大量数据，以此来获 取新颖的、潜在有用的、有效的、最终可理解的模式的非平凡过程。从学科基础 上看，数据挖掘是一门多领域交叉的研究与应用领域，它跨越了数据库、人工智 能、机器学习、统计分析等多个学科，使决策支持系统跨进了一个崭新的阶段。 数掘挖掘可以在领导者制定决策时，为他们提供一些有价值的资料信息作为 第1 幸绪论 参考。现在，掘我们所知数据挖掘所涉及到的好多产品并没有完善，可是它的影 响范围逐步扩大，很多的企业已经注意到了数据挖掘，对公司的各个部门的数掘 进行分析处理，常常把结果作为参考，来帮助制定决策。 ( 1 ) 数铤挖掘的功能 它的功能主要是为了从数据库海量的数据中寻找出对以后研究有用的信息， 大概包括以下血种作用： 进行相关性分析 数据之i 、日j 的相关性在数据库中是非常重要的，它可以寻找出那些隐藏在大量 数据背后的信息。相关性就是几个变量取值之l 、日j 存在的某一种规律性的信息。很 多的情况下人们并不清楚数据库中的数据，使用了什么样的关联分析，或即便是 知道也不是很肯定，因此就用相关性进行分析生成的规则。 自动预测趋势和行为 以前人们对信息的处理方式大都是用手工来完成的，这就需要进行大鼍的操 作，但是自从数掘挖掘产生以后，就从手工操作变成了自动的寻找未束预测件的 信息，就可以直接由数据自身的信息得出最后的结论。市场预测问题是一个典型 的例二f ，它运用了过去相关的历史数据，末寻找最大的客户以期望在未来投资中 获得l 司报，还可以预测效益不好的企业有无破产前兆，或找出某一人群对某一种 事物是否特别敏感。 聚类分析 将数据库中的记录划分为一系列有意义的子集，就是聚类。聚类是概念描述 ， 和偏差分析的先决条件j 有效的增强了人们对客观现实的认识。聚类技术属于无 监督教师学习方法，这个方法是8 0 年代研究者m c h a l s k i 最先提出。包含传统意 义上的模式识别以及数学分类两方面，它的特点是在划分对象阶段，为了避免以 前技术的片面性，不仅将两个对象之问的距离考虑了进去，而且还保证被划分的 每个类具有相仁- j 的意义。 偏差检测 任何事情都有可能会出现偏差，当然数据库当中的数据也不例外，通常会包 含一些异样的数据，那么如何检测出来是一件很值得研究的事情。但是这些偏差 罩含有很多我们所不易发现到的信息，例如在分类当中会有一些特殊的不满足条 件的规则或者足异样的例子它所采用的方法就是寻找出所得结果和参照值之i 日j 的差别。 概念性描述 它描述的是某一类事务的内在含义，并且把这类事务的性质进行了总结。一 般人们把它分为两类：关于特征的描述( 针对某一类的共同性质进行描述) 和区 2 山东轻丁业学院硕l j 学位论义 别性的描述( 钏对不同类对象之问的差别) 这两类。前断体现的是所有对象的共 同性质，后面主要体现了差别，在现在的研究中大都主要采用的方法是决策树和 遗传算法等等。 ( 2 ) 数据挖掘的步骤 数据挖掘的环境 数据挖掘足一个完整的流程，先是从大型的数据库所包含的数据中挖掘出那 些以自仃不知道的、有实用价值的信息，随后用这些信息束帮助用户作出决定。数 据挖掘的环境可表示为图1 1 ： 数据可视 挖掘化l ： 争 l ：具具 图1 1 数据挖掘的环境 数据挖掘过程图 在海鞋的数据中发现有用的数据就是数据挖掘的任务，但是仅仅为了发现数 掘还是不够的，仍然需要对这种模型做出反应并实施定的行动，最后再将这些 有用的数据转换成信息，把信息变成行动，最后把行动转换成价值。以上就是数 据挖掘的一个完整的流程。图1 2 描述了数据挖掘的基本步骤。 之 第l 章绪论 佘 门 八 八 土 预 被 被 n 被 篓 鬟 抽 是 r 凳 r 后 r 的 r 取 的 冀 矍 萎 的 u 信 据 据 u 息 u u r 。 1r 1r1 rr 田圈圈曰、园 图1 2 数掘挖掘的基本步骤 ( 3 ) 数据挖掘的支撑技术 数据挖掘的基础理沦 模式发现( p a t t e r nd i s c o v e r y ) ：在此理论下，它被看做是从原始的数掘集合 当中发现知识模式的过程，这个技术将机器学习所采用的方法进行了传承和发 展，就日d 玎来说在数据挖掘的研究和系统开发方面是一种比较通用的构架f 2 】。 规则发现( r u l ed i s c o v e r y ) ：a g r a w a l 等研究者们将机器学习和挖掘的目标 进行综合考感，给出了统一的挖掘模式和几个基本的运算 引。 微观经济学理论( m i c r o e c o n o m i cv i e w ) ：主要涉及到企业方面，把数据挖 掘看成是对某介问题的优化过程。它所采取的观点就是在企业中，如果某一模 式对其有效，就表明此模式是有趣的【4 】。 ：j 概率和统计理论：主要是寻找出随机变量的概率分布情况。到目前为止，已 经取得了很好的效果，近十年晕，统计学的基本知识在数据仓库和数据挖掘技术 的中已经占有了很蓖要的地位j 已经成为他们的基础理论。 数据压缩( d a t ac o m p r e s s i o n ) 理论：基于这个理论，数据挖掘所涉及的算 法都是对大型数据库中的数据进行概念化或抽象化的压缩过程【5 1 。 数j | l ：库归纳( i n d u c t i v ed a t a b a s e ) 理论：数掘挖掘系统包含原始数掘库和模 式库，所以就被认为是对数据进行归纳以及查询的过程【6 1 。 可视化数据挖掘( v i s u a ld a t am i n i n g ) ：就是为了以可视化的方式对挖掘出 来的结果呈现给人们，实现人和机器之间进行更人性化的交互【刀。 数据挖掘研究的支撑技术 ： 4 _ _ _ 一 山东轻t 业学院颂i ：学位论文 数掘挖掘领域提出了多种实现方式与算法，这里仅讨论几种常见的典型的实 现方法。 决策树：决策树在知- i ，1 - 1 - 1 程领域中是一种简单的知谚 表示方法【8 】，它把事务 逐步分成代表不同的类别。因为分类的规则比较直观，所以比较容易理解。这种 方法一般只用在分类任务中。在美困的i d i s ，法国的s i p i n a 。英湖的c l e m e n t i n c 和澳大利亚的c 5 0 中系统中就采用了这种方法。常用的决策树方法有c 4 5 1 9 j 0 1 ， c h a i d 1 1 1 c a r t l l 2 】及i d 3 t 1 3 , 1 4 】。 人工神经网络法【1 5 】：人工神经网络则是建立在可以自学习的数学模型的基础 之上，它可以对大量复杂的数掘进行分析，并可以完成对人脑或其他计算机来说 极其复杂的模式抽取和趋势预测分析。其中比较典型是问溯法。它通过把输出结 果和一些已经知道的值进行一系列比较，加杖值小断调整，得到一个新的输出值， 再经过不断的学习过程，最后得到一个稳定的结果。 粗糙集( r o u g hs e t ) 方法【1 6 】：在数据库当中，每一行的元素被定义为对象， 列元素代表其属性值。若存在着不同的对象在某一个( 几个) 属性上面的数值相 同就定义为等价关系r ，相应的那些达到等价关系的对象形成的集合就叫r 上的 等价类。 ( 4 ) 数据挖掘的分类 数掂挖掘所涉及的学科领域和方法很多，从各个不同的角度，就有与之十h 对 应的不嗣分类方法，这些方法都从不同的方面描绘出了进行数掘挖掘研究的方法 和范围，它们既存在互相交叉而且又存在互相补充的关系。 ” 从挖捌任务方面考虑主要分关联规则和依赖关系、分类和聚类、序列模式和 预测模型、相似模式异样和趋势等等几个方面。 从挖掘对象这个方面考虑分为：面向对象的；关系型数据库挖掘；时念数据 库挖掘；空j 日j 数据库挖掘；多媒体数据库挖掘；文本数据源挖掘；异质数据库挖 掘；w e b 数据挖掘；遗产数掂库挖掘等。 根掘挖掘方法可以分为：统计方法；机器学习方法：神经网络方法：聚类分 析方法；遗传算法方法；数据库方法；基于证据理论和元模式的方法；近似推理 和不确定性推理方法；粗糙集或模糊集方法；现代数学分析方法；集成方法等。 日前，数掘挖掘的研究乘1 应用已经非常热门，总结一下主要集中在以下几个 领域中： ( 1 ) 金融业 数掘挖掘在银行业当中被得到了广泛的应用，它可以对贷款人的信用进行评 定，以及对不同收入层次的人进行分类等等。现在在银行系统中，每天需要面对 大量的数据信息，若是采用传统的小型的软件进行测试处理是非常困难的。但是 第1 章绪论 通过数据挖掘首先是对已有的数掘进行分析处理，从而把那些数据的特性和关系 发掘出来，最后再运用所得的信息进行较为合理的推测，就可以成功的预测到以 后的趋势，以此束发现不同层次的客户消费需求和感兴趣的商业信息等。 ( 2 ) 市场业 主要用数掘挖掘方法对经营的项目进行定位，并对消费人群进行消费水平分 析，帮助卖家制定出市场决策。例如现在的电信企业，借助数据挖掘技术，可以 帮助企业分析出用户所用电信业务的情况、对客户的行为进行评估、优化广告的 投入。电信公司在运营过程中会积累大量的数据，包括客户的基本信息、消费记 录、销售信用、销售状念、产品种类、价格等。这些信息用于提升企业客户的洞 察能力，发觉客户的各种需求，提升了客户的满意度和忠诚度，从而利用客户的 消费趋势和规律发掘出新客户具有非常重要的价值。 ( 3 ) 王程与科学研究 +， 一 各种工程与科学数据的分析也可以利月】数据挖掘技术。伴随着大量先进科学 数据收集工具的使用，例如观测卫星、遥感器和d n a 分子技术等，面对如此庞 大的数据，以自订传统的数据分析工具已经是无能为力了。数据挖掘技术依靠它强 大的智能性和自动性，在工程和科学研究领域中得到了广泛的应用。 ( 4 ) 产品制造业 ，。主要应用于零部件的故障诊断、资源优化以及生产过程的分析等制造过程， 发现出影响生产率的因素，通过发现某些不币常的数据分布，暴露出制造和装配 操作过程中变化情况和其它因素，从而使质量工程师很快地注意到问题发，i 三的范 围和并采取修改的措施j 中国最大的钢铁生产企业一上海宝钢，为了更好的实现 对运输流程的有效管理，他们丌发了运输优化系统，使用了s a s 所提供的数据 访问、建模和决策软件，可以根据要运输的产品类型、运输线路、运输类型，以 及仓库容量和库存管理等因素束确定最佳的运输流程，从而最大化利用资源，进 而确保整个运输流程尽可能高效的运行。 ( 5 ) 司法 数据挖掘技术还可应用于在司法当 - b ；利用它进行诈骗监测、案件调奄、犯 罪组织分析等。公安局通过分析以往的罪犯记录，推断哪些人可能会犯恐怖罪或 者大的谋杀罪。例如，美国的财政部利用数据挖掘技术识别出非法的金融事务， 提交了4 0 0 。个调查报告涉及金额1 亿美元，有效的减少了国家的损失。 1 2w e b 文档分类概述 伴随着信息时代的发展，人们获取信息的重要方式，从原先的读报等方式发 展到了从网络上获取数字化信息。但是网络1 f ：的信息就像是浩瀚的海洋，那么面 6 山东轻t ：业学院硕 j 学位沦义 对如此多的信息，人们若怂要找到关注的信息，这往往就得需要投入大量的时问， 并对这些信息进行组织和整理。所以为了帮助人们非常有效地组织、管理这些海 量的w e b 信息，w e b 文档分类技术就冈此而产生了，它是w e b 数据挖掘的主要 内容，而且是在文本分类的基础上产生出末的。主要是指按照事先定义好的类别， 给待分文档中的每个文档分配一个类别。通过这个方法，用户浏览文档的时候速 度得到了很大的提高，而且可以容易的找到自己想要的信息。 w e b 文档分类不仅在一定的程度上解决了网上信息杂乱无章的现象，并且方 便了用户准确的定位所需要的信息以及分流信息，而且现在逐渐地把信息过滤技 术、搜索引擎和文本数据库等各种信息处理技术相结合，更为有效地提高了信息 服务的质量。 目d 订对w e b 文档进行分类的技术主要可以分为两类，包括基于文档内容的 分类方法以及基于文档性质的分类方法。其中基于内容分类足指按照预先定义的 基于内容的主题类别c ( c = ( c i ，c 2 ，c 。 ) ，在这晕的c 。的组织方法可以是并 列的，或者足以分层次的，为文档集合中的任意一个文档d i ( i = l ，m ) 确定它 所属的类别。基二fw e b 文档性质的分类方法就是把文档按照它的自身性质来进 行分类，它和基于内容的分类一样，都是将一个文档分到已有的类别中，唯一不 同的是基于性质分类是按照文档的性质来划分，将它分为新闻页、军事页、广告 页等等，可以更好的管理、利 j 网络上不断增长的信息资源，使用，、能够从性质 层面上处理文档，更方便地对资源进行查找。 目前，有的网站还是基于人工来对w e b 上的文档进行分类，这种作法存在 一定的缺点：方面是会耗费人量的人力以及物力，另一方面是个人的：e 观因素 导致分了类结果可能存在不一致的现象是不可避免的；同时大大降低了索引的数 目。另外由于互联网迅速的发展，w 曲上的大量文本信息也随着急剧地增加，这 种信息增长的速度超出了想象的，迫切地需要更加高效、更加智能化的文本分类 技术的产生，从而使得分类的正确率得到很大的提高，保证了检索结果的查全率 和准确率。 伴随着w e b 文本分类技术在互联网信息监控、数字图书馆技术、搜索引擎 技术、信息检索、信息过滤等在众多领域的广泛应用，w e b 文本分类的研究己经 成为信息处理的一个前沿课题，有着广泛的应用日订景和重要的研究意义。 1 3 本文的研究背景及意义 现在国内外对w e b 文本分类的研究已经成为一门热点话题，其中还存在许 多待解决和研究的问题。目d 仃大多研究者在w e b 文档分类中仅仅涉及到了j f 关 联规则挖掘，而较少涉及负关联规则。负关联规则可以发现项集之间的负关联关 第l 奄绪论 系，是对证关联规则挖掘技术的补充，将负关联规则挖掘技术应用于w e b 文档 分类，就可以发现那些负相关的w e b 文档，从而提高w e b 文档分类的正确度。 所以本文提出了基于币负关联规则的w e b 文档分类技术。 基于正负关联规则的w e b 文档分类策略，是在基于关联规则w e b 文档分类 的基础上，为了更加有效地体现现实事件中那些隐藏的直接关联，而采取的分类 策略。这样的分类方法和币关联规则分类相结合，能够更加有效的和准确的进行 分类，可以更加全面地分析各个因素之删所隐藏的内在联系。加入了负关联的研 究方法来完善文档集产生关联规则的讵确度，从而提高了w e b 文档分类的精确 度。 本文研究的主要内容及内容组织如下： ( 1 ) 第l 章是绪论，对数掘挖掘以及w e b 文档分类进行了综述，提出了本 文研究的： 三要内容一基于正负关联规则的w e b 文档分类。 ( 2 ) 第2 章讨论了现在w e b 分类的技术。涉及到了w e b 挖掘、w e b 文本挖 掘的相关内容。 ( 3 ) 第3 章研究了基于正关联规则的w e b 文档分类方法。介绍了正关联规 则的相关内容，分析了目前提出的基于币关联规则的w e b 文档分类的算法。 ( 4 ) 第4 章介绍了负关联规则的基本概念和主要的挖掘算法。 ( 5 ) 第5 章对基于正负关联规则的w e b 文档分类方法进行了详细的介绍。 ( 6 ) 第6 章对全文进行了总结，并提出了进一步的 i 作。 山东轻t 业学院倾i j 学化论文 第2 章w e b 文档分类的相关技术 2 1w e b 挖掘 2 1 1w e b 挖掘的概念 i n t e m e t 技术的发展和广泛的普及，使得人们获取和发布信息的方式发生了 巨大的和本质性的变化，w o r l dw i d ew e b ( 简称w w w ) 已经成为信息传播的主 要载体之一。可以发觉到，w e b 的容量增长十分的迅速，互联网上每天流通的信 息也在飞速的增长。面对这样浩如烟海的w e b 信息，按理说应该能够满足人们 对信息的需求，但是经过研究实际的情况是：对9 9 的广大用户来说，w e b 上9 9 以上的信息对他们想要找的信息来说是毫无用处的。随着时问的不断推移，人们 越来越感觉到这个快捷的数字化图书馆，并不像真萨的图书馆那样可以支持人们 有组织的进行信息管理和检索。 数据挖掘和知识工程研究领域所面临的新课题就是怎样从这些巨量的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 动画( 如f l a s h 广告、视频 信息) 等。 2 1 2w e b 挖掘的分类 按照对w e b 数据的感兴趣程度不同，人们一般的将w e b 挖掘可以分为三类： w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 、 w e b 用法挖掘( w e bu s a g em i n i n g ) 。具体的分类如图2 1 所示。 9 第2 章w e b 殳档分类的卡h 关技术 图2 1w 曲挖掘的分类 ( 1 ) w e b 内容挖掘 w e b 内容挖掘是指从w e b 的内容、数据中发现出有用信息。当前w e b 的迅 速发展，必然要求系统能从各种类型的资源中自动抽取关键信息，从而减少或避 免手工编码。 从内容方面讲，w e b 内容挖掘可以分为对w e b 文本文档和多媒体文档的挖 掘。从方法上来讲，可以分为对数据库的方法和信息抽取方法两种，它们都采用 了数据转换技术，将非结构化的w e b 内容信息转化或者是映射为更高层的结构 化数据，最后利用数据挖掘技术进行数据挖掘，以便能进行更好的信息查询和管 理。 一般来说，信息抽耿方法主要应用于信息抽取技术，评估和改进搜索信息的 质量，也可以处理无结构化数据和h t m l 标记的半结构化数据。人们习惯把针 对无结构化的文本进行w e b 挖掘，放到了基于文本的知识发现( k d t ) 领域， w e b 内容挖掘的基本技术是文本挖掘，是w e b 挖掘中比较重要的一个技术领域， 也引起了许多研究者的关注。下面图2 2 给出了文本挖掘的过程描述。 1 0 山东轻t 业学院硕i ：学位论文 图2 2 文本挖掘的过程描述 ( 2 ) w 曲使用模式挖掘 w e b 用户在r 常的活动中会产生大量的信息，而w e b 服务器会自动的将这 些信息收集起来并存储在访问同志中。对于用户的每次访问，w e br 志中都记录 了用户的访问的时问、网络的地址、目的信息的网络地址和传输的信息量等。 w e b 使j j 模式挖掘研究的目的就足从这些大量的w e b 历史访问同志中获取用户 访问w e b 的规律，并预测出用户的网上行为。 w e b 使用模式挖掘的过程一般包括以下三个步骤【i ：第一步：数据预处理 阶段。把从数据源当中收集而来的原始数据，经过处理后才能有效地进行下一步 的数据挖掘算法，数据预处理质鼍的好坏，直接关系到了使用模式挖掘的效率和 结果。第二步：模式识别阶段。把第一步预处理之后的数据进行处理，得到相应 的事务数据库。第三步：模式分析阶段。模式分析的目标足依据实际的应用需求， 通过观察以及进行选择，把发现的统计结论、规则和模型转换为自己的知识。 w e b 使用模式挖掘可以分为两类，种是将w e b 使用记录当中的数掘直接 进行预处理之后，就用数据挖掘方法进行挖掘。w e b 使用模式挖掘中有一个有趣 的问题，就是当同一个代理服务器的环境被多个用户使用的时候，怎样4 能把某 个用户识别出来，以及怎样把属于这个用户的会话和使用记录都识别出来，这个 问题看似很简单，但是却对挖掘的质量好坏有很大程度的影响，所以现在已经有 人专门针对这一方面进行了研究。另一种是首先把w e b 使用汜录中的数据进行 转换之后再传递到传统的关系表罩，然后将关系表当中的数据再利用一般的数据 挖掘算法进行常规的挖掘。 ( 3 ) w 曲结构挖掘 第2 章w e b 文档分类的栩关技术 w e b 结构挖掘的目的足调整w e b 各个页面之l 、日j 的链接结构。在整个w e b 信 息数据空问垠，研究者发现一些很有 j 的知识不仅仅在w e b 页面内容之中，而 且也包含在各个页面的链接结构当中。例如，我们如果发现一个页面经常被点击， 那么，这个页面一定非常有用。通过对w 曲站点的结构进行一系列的变形、分 析和归纳，最后把w e b 页面进行分类，分析出个网页的链接网页以及它被链 接的数量和对象，可以被用来建立w e b 自身的链接结构模式，找到各个不同页 面之问的相似程度以及关联程度的信息，这些发现出来的知识就可以被人们用来 改进搜索引擎。 通过对引用分析和社会嘲络进行研究，使得w e b 结构挖掘在一定程度上得 益。他们把嘲页之间的联系分为i n c o m i n g 连接和o u t g o i n g 连接两种，采用了引 用分析的方法，以此来寻找同一个网站内部和不同网站之间所产生的连接关系。 到目前为止研究w e b 结构挖掘的算法有很多种，但其中最著名的两种算法是 h i t s 算法和p a g e r a n k 算法，它们都运用了一定的方法把w e b 页丽之l 、日j 超连接 的质量计算出来，然后得出了页面之| h j 的权重。现在我们所知道的比较著名的搜 索引擎c l e v e r 以及g o o g t e 就是采用了该类算法。 另外，现在还有的人对w e b 结构挖掘开始了另一个新的尝试，就是在w e b 数掘仓库的环境中进行挖掘，包含着对同一台服务器上的本地连接进行捡肖，用 这个方法就可以衡量出w e b 站点上的完全性，另一个就是在不同的w e b 数据仓 库中捡查出副本，以此为定位镜像站点提供帮助，通过发现出某一个特定领域当 中的超连接层次的属性，来寻找出信息流动性对w e b 站点的设计影响。 ， 2 2w e b 文本挖掘 随着w e b 上信息量的不断增涨，怎样使用户在信息的海洋中找到自己真f 所需要的内容，目前已经成了该领域专家学者关注的焦点，w e b 挖掘就是一个可 以很好的解决这个问题，同样也是w e b 技术当中一个重要的研究领域。w e b 挖 掘中的重要代表是w e b 文本挖掘，可以帮助用户大量的节约搜索查询的时间， 使用户比较准确的找到自己想要的资料，此外它还可以对用户提供w e b 文档的 利用价值等，并且它能够充分利用w e b 大量的有价值的信息，为智能化的运用 w e b 资源奠定了基础i 博j 。 w e b 内容挖掘其中的一个蘑要方面足基于w e b 的文本信息的挖掘，因为现 在w e b 上的信息在很大的程度上都是以文本的形式存在，因此说w 曲文本挖掘 是w 曲内容挖掘的最主要、也是最重要的部分，而且现在也普遍被认为是具有 更高的商业潜力，事实上，当数据挖掘的对象完全变成由文本这一类型的数据组 成的时侯，这个数掘挖掘的过程就是文本数据挖掘。 1 2 l _ 一一一一 一一 1 东轻丁业学院顺 ：学位论文 w e b 文本挖掘就是指从大量的非结构化的、异构的w e b 文档集合当中发现 出那些具有新颖的、有效的和潜在可用的、还得是最终可以被理解的知识k 的 过程。这其中的k 包含了概念( c o n c e p t s ) 、模式( p a t t e r n s ) 、约束( c o n s t r a i n t s ) 、 可视化( v i s u a l i z a t i o n ) 和规律( r e g u l a r t i e s ) 等形式。总的来说，w e b 文本挖掘的过 程主要包括：进行文本预处理、文本特征的提取、文本分类及聚类等这几个方面。 w e b 文本挖掘最主要的是采用了计算语言学的原理，用此原理束对w e b 上 的文本信息进行抽耿的研究和实践。它可以对w e b 文档集合当中的内容进行分 类、聚类、关联分析以及未来趋势预测等等。w e b 文本挖掘和通常的文本挖掘( 就 是指从大量的文本集合d 中，发现出所隐含的模式p 。假设把输入定义为d ，将 p 看成输出，那么文本的挖掘过程就可以看成是从输入到输出的一个过程鼍：d p 。) 有着相似之处。但是，w e b 文本挖掘仍然也：仃很多自己独特的特点。 第一方面w e b 文本挖掘的主要对象足大量的、不同的分散型 w e b 文件类型， 而且是没有办法进行集中存储的。 第二方面w e b 文本信息从逻辑上考虑是由文件节点和超链接两方面构成的 图形；所以w e b 文本挖掘所得出的模式相应的也可以分为两种，一种是关于w e b 内容的，另一种也可能