（计算机应用技术专业论文）web挖掘中超文本分类的研究与实现.pdf

摘要 随着i n t e m e t 的飞速发展，w e b 已经成为一个海量的、动态的、异构的信息 资源库。这使得一方面出现“信息爆炸”，而另一方面，人们迫切需要从w e b 上 快速、有效的获取信息和知识。w e b 挖掘就是近来逐步兴起的针对w e b 上异质、 非结构化信息进行知识发现的研究领域。 本文先是从数据挖掘理论引出w e b 挖掘的概念，并讨论了w e b 挖掘的流程 和分类等，接着阐述了w e b 挖掘中的文本挖掘，并详细论述了文本分类、超文 本分类。最后重点介绍了基于l e e 模型的n a i v eb a y e s 文本分类方法和基于规则 的超文本分类方法。 在文本分类领域，d a v i dl e e 从心理学的角度提出l e e 模型，s a n b a n 用该模 型定义特征词的影响度，但特征词的影响度在训练数据集上表现出倾斜性。我们 根据l e e 模型和贝叶斯概率重新定义了影响度，消除了倾斜性对分类的影响，研 究了两种读取测试文档的策略下文本分类精度的变化情况，结果表明启发式的读 取策略链以较小的时间代价极大地改善n a i v eb a y e s 的分类性能。 相对于普通文本，超文本含有更丰富的信息，y i m i n gy a n g 在此基础上提出 了五种超文本规则。我们基于其中的三种规则，将四种超文本表示方法应用到超 文本分类中，为了便于试验，利用两种典型的文本分类方法，并在分类精度以及 其中两种表示方法的运行时间上和未应用超文本规则的分类方法进行对比，试验 结果也显示了在选定的数据集上基于统计理论的n a y v eb a y e s 分类器的分类性能 要优于基于向量空间模型的t f i d f 分类器。 关键词：w e b 挖掘，文本分类，超文本分类，l e e 模型，朴素贝叶斯，影响度 超文本规则，超文本表示方法 a b s t r a c t w i t l lt h ef a s td e v e l o p m e n to fi n t e m e t ，w e bh a sb c c o m eag r e a t ，d y n a m i ca n d i s o m e r o u si n f o r m a t i o na n dr e s o u r c eb a s e o n er e s u l to ft h i si st h e “i n f o r m a t i o n e x p o s u r e ”，a n dt h eo t h e rr e s u l ti st h ep e o p l e su r g e n tn e e dt oq u i c k l yg e tv a l i d k n o w l e d g ea n di n f o r m a t i o nf r o mt h ew e b w e bm i n i n gi sj u s tt h er e c e n t l ye m e r g i n g r e s e a r c hf i e l dt os o l v et h i sp r o b l e m t l l i sp a p e rf i r s t l yi n t r o d u c e st h ec o n c e p t i o no fw e bm i n i n gb a s e do nd a t am i n i n g t h e o r i e sa n dd i s c u s s e st h ef l o wa n dc a t e g o r i z a t i o no fw e bm i n i n g t h e ni te l a b o r a t e s t h et e x tm i n i n g ，t h et e x ta n dh y p e r t e x tc l a s s i f i c a t i o n f i n a l l yi tf o c u s e so nt h e i n t r o d u c t i o no fn a i v eb a y e st e x tc l a s s i f i c a t i o nb a s e do nl e em o d e la n dh y p e r t e x t c l a s s i f i c a t i o nb a s e do nr u l e s i nt h ef i e l do ft e x tc l a s s i f i c a t i o n ，d a v i dl e ec a m eu pam o d e lw i t ha p s y c h o l o g i c a l l ya p p r o a c hc o n s i d e r i n gt e x tc l a s s i f i c a t i o n s a n b a nu t i l i z e dt h em o d e lt o d e f i n et h ei n f l u e n c eo ft h ew o r d ，b u tt h e r ea r eas k e w n e s sl i e si nt h e 订a i l 血gs e t a c c o r d i n gt ol e e sm o d e la n db a y e sp r o b a b i l i t y , t h ei n f l u e n c eo ft h ew o r di s r e d e f i n e da n dt h es k e w n e s si se l i m i n a t e d t w om e t h o d st or e a dt e s td o c u m e n t sa r e p r e s e n t e d i nt h ee n d ，e x p e r i m e n t ss h o wt h a th e u r i s t i cm e t h o dc a ni m p r o v en a i v e b a y e sg r e a t l yb ym u c hl o w e rt i m ec o s t c o m p a r e dw i t ht h ep l a i nt e x t ，h ) ，p e r t e x ti sr i c hi ni n f o r m a t i o n o nt h i sb a s i s ， y i m i n gy a n gb r i n g sf o r w a r df i v ek i n d so fh y p e r t e x tr u l e s b a s e do nt h r e eo ft h e s e r u l e s ，t h i sp 印e rp r e s e n t sf o u rk i n d so fh y p e r t e x tr e p r e s e n t a t i o na n da p p l i e st h e mt o h y p e r t e x tc l a s s i f i c a t i o n n l ec o n t r a s to np r e c i s i o na n dr u nt i m ei sa l s om a d eb e t w e e n r e p r e s e n t a t i o n 谢t ht h ea p p l i c a t i o no ft h ev i n a i n gy a n gh y p e r t e x tr u l e sa n dt h eo n e w i t h o u t e x p e r i m e n tr e s u l t ss h o wt h a tt h ef o r m e ro n eg e t sh i g h e rp r e c i s i o nw i t hl e s s t i m ec o s ta n d p r e f e r a b l eo v e r a l lp e r f o r m a n c e k e y w o r d s ：w e bm i i l i n g ，t e x tc l a s s i f i c a t i o n ，h y p e r t e x tc l a s s i f i c a t i o n ，l e em o d e l ， n a i v eb a y e s ，i n f l u e n c e ，h y p e r t e x tr u l e s ，h y p e r t e x tr e p r e s e n t a t i o n 西北工业大学硕士学位论文 第一章绪论 1 1 选题背景 第一章绪论 随着i n t e m e t 的飞速发展，w w w ( w o r l dw i d cw 曲) 己经成为一个遍及全球 的信息宝库，使得人类全部的信息资源以前所未有的方式和程度在全球内互联互 通，w e b 上的信息量也随之呈几何指数增长。 同时，企业信息化程度的提高，文本信息的快速积累使企业、政府、科研机 构等面临前所未有的挑战。一方面，互联网和企业信息系统每天都不断产生大量 文本数据，这些文本资源中蕴含着许多有用信息；而另一方面由于技术手段的落 后，用户从w e b 上海量、动态、异构的丰富信息资源中快速、有效地查找自己 感兴趣的信息从而获取潜在的有价值的知识十分困难，即人们面临着“信息爆 炸”而“知识贫乏”。 因此，人们迫切需要研究出有效的方法和手段从大规模文本信息资源中提取 符合需要的简洁、耩炼、可理解的知识。搜索引擎只解决了信息查询的问题，传 统k d d 技术所涉及的主要是结构化的数据库，而网上资源却没有统一的管理和 结构，数据往往是经常变动和不规则的。w e b 中的知识发现，即w e b 挖掘就是 为解决这个问题而产生的研究方向。 1 2 研究意义 1 2 1w e b 挖掘和w e b 文本分类 传统的网络信息服务由于缺少机器智能己经逐渐不能满足人们的需求，人们 迫切需要更强大的智能化、个性化信息服务，也即w w w 智能信息服务。 面向w w w 的w e b 信息挖掘研究已成为当前i n t e r n e t 领域的一个新的研究 热点，它利用数据挖掘、机器学习、统计理论、模式识别等相关理论技术的研究 成果，从w w w 的海量数据中进行知识发现，提高传统i n t e m e t 信息服务的智能 西北工业大学硕士学位论文第章绪论 化水平，它可以帮助用户：查询相关信息；从w e b 数据发现潜在的未知信 息；了解自己的兴趣爱好；信息个性化。 w e b 挖掘的研究内容包括基于w e b 页面内容实现内容识别分类、进行内容 过滤和个性化信息投递服务等。其中基于内容的w e b 文本自动分类技术又是实 现i n t e m e t 智能信息检索，信息内容过滤和个性化信息推荐等智能信息服务的核 心。 w e b 文本数据是最普遍的和应用性最广的，因此对w e b 文本信息的挖掘是 很有意义和价值的。w e b 文本分类技术是w e b 文本信息挖掘中_ 个重要的方面， 它同时也是数据挖掘、智能信息检索和处理领域的个新兴和重要的研究方向， 也是一门交叉学科，融合了信息网络、人工智能等多领域学科知识，涉及面较广。 自动文本分类是大规模信息处理重要的应用技术之一，它同时也是快速、有 效组织w e b 上海量信息的一个重要技术。随着信息存储技术和通信技术的迅猛 发展，大量的文本信息以计算机可读的形式存储，并且其数量与日俱增。这些文 本信息的内容包罗万象，但用户往往只需要其中很少的一部分。因此就需要对这 些信息进行组织和整理。 从分类的准确性来看，人工分类要优予自动分类，但是自动分类在效率上要 优于人工分类，它能使用户从繁琐的文本信息处理工作中解放出来，并能极大地 提高信息的利用率。对于w e b 上的海量信息而言，使用人工分类代价高昂而且 是不现实的。自动分类具有以下优点： ( 1 ) 效率高：自动分类系统的效率要高于人工分类，特别是在针对发展如 此迅速的w e b 时，自动分类系统可以大量的节约人力和时间； ( 2 ) 保证一定准确度：避免了人为错误出现的可能性； ( 3 ) 背景无关性：通过采用不同的训练平台，系统可用于不同的分类任务， 从而快速适应不同的分类需要。 1 2 2 文本分类的应用 在信息时代，文本分类技术越来越紧密地与其他信息技术相结合，它作为信 息过滤、信息检索、搜索引擎、文本数据库、数字化图书馆等领域的技术基础， 有着广泛的应用前景： 2 西北工业大学硕士学位论文 第一章绪论 ( 1 ) 信息推送服务 文本分类技术可以参与到主动的信息推送服务中。在传统的获取信息的技术 中用户是主动方，由用户向信息服务系统提出要求，启动信息服务工具，从信息 库中查找信息，并向用户返回信息，在这种模式中，用户可以说是主动地“拉动” 信息；而与之相反的另一种形式是“推送”信息，在这种模式中，用户是被动的， 随着信息的增长，信息服务系统可以主动地将最新的信息推送给用户。要想有效 地做到这一点，信息服务系统必须具有将新信息分门别类的能力，然后根据用户 的要求分发出去。 ( 2 ) 信息的存取与管理 文本分类被应用于信息存取与管理( i n f o r m a t i o na c c e s s & m a n a g e m e n t ) ，与 信息检索系统的自动索引问题有关。 为方便用户快速查找自己所需的信息，信息检索系统中的每一份文本都对应 着一个或一组关键词或短语用以描述该文本的内容。文本所对应的这些关键词或 短语称为索引词或索引项，它们来自一个事先精心确定的通常具有层次结构的专 用词汇表，建立索引项即标注关键词或短语的工作通常需要人工完成，因而极其 耗时耗力。 如果将具有相同关键词或短语的所有文本看成是来自同一文本类别，则对文 本进行索引( 即根据文本内容用关键词或短语对其进行标注) ，实际上就是对文本 进行分类。自动文本分类技术在信息检索系统的成功运用，可以使人们从繁重的 手工编制索引的劳动中解脱出来，从而大大提高信息检索系统研制的效率和效 益。由于同一篇文本可能对应多个不同的检索项，自动文本索引属于多类分类问 题。 ( 3 ) 文档组织 搜索引擎是重要的网络信息查找工具，但是传统的搜索引擎检索效果往往不 尽如人意，使用者输入一些关键词，一般都会得到成千上万的检索结果，而且其 中大部分页面都是不需要的无关信息。虽然有一些方法试图给那些有较多关键词 或者罕见关键词的页面赋予更大的权重，却仍然不能保证和用户意图最相关的页 面一定被排在最前面，因此用户只能把检索到的页面逐一再筛选一遍。 而文本分类技术可以弥补传统搜索引擎的不足，可以过滤用户并不需要的某 些文章，并且试图更合理的组织检索结果，将检索结果分门别类，按照页面彼此 西北工业大学硕士学位论文第一章绪论 之间的相似程度分为若干组，每组都有一个比较明确的主题，用户可以迅速地扫 描每一组并选择那些和它的目标最相关的组。 一般来说，同文档组织( d o c u m e n to r g a n i z a t i o n ) 相关的任何事务，都可以用 自动文本分类技术来处理。例如，自动广告分类系统，新闻稿件自动分栏系统( 将 新闻稿件自动区分为时事、财经、体育、文艺等不同类别以刊登到合适的栏目中 去) 。文档组织属于典型的单类分类问题。 ( 4 ) 文档过滤 文档过滤( d o c u m e n tf i l t e r i n g ) 一般指根据用户的需要，对文本信息进行动态 地分类、筛选，从而保留相关信息、屏蔽无关信息的活动。 网站搜索引擎就是一个典型的文档过滤系统。一个好的搜索引擎可以根据用 户的具体需求，将w e b 上所有与用户需求密切相关的网页提供给用户，而将所 有其它网页统统屏蔽掉。类似的应用还有电子邮件过滤系统，其作用是将广告等 垃圾邮件过滤掉，仅仅保留用户感兴趣的普通邮件。 文档过滤属于单标号文本分类问题，它将所有文档区分成“相关文档”和“无 关文档”两大类。 ( 5 ) 词义辨析 词义辨析( w o r ds e n s ed i s a m b i g u a t i o n ) 通常指根据多义词所处的上下文环境 确定出该词此时的具体含义的活动，是计算语言学需要解决的众多自然语言歧 义性问题中最重要的一个，在自然语言理解、机器翻译等领域有着重要的应用。 如果将包含多义词的上下文看成文本，将多义词各个含义看成是不同的类 别，则词义辨析就变成了文本分类问题，而且是一个单类分类问题。 除了上述五个方面以外，自动文本分类技术还在自动文章批改等方面得到了 广泛应用。 1 3 研究现状 1 3 1 文献综述 1 9 9 8 年，m a r k c r a v e n 等【1 1 提出了用有向图来描述超文本间的结构，并把网 页相应的描述成图的节点，网页间的超链接对应图的边，使用基于文本单词的统 4 西北工业大学硕士学位论文 第一章绪论 计分类器和考虑了超文本之间存在链接特性的一阶逻辑规则对网页进行分类。 h i s a om a s e 2 1 针对信息检索系统中的超文本分类任务，考虑了网页的两大特性所 带来的问题：每个网页的文本长度不一，使得用统计特性如单词频率计算特征 词权重非常困难；不同的单词的数目很大，致使知识库变得很大，导致分类时 的处理速度降低。并提出了五种单词频率正规化的方法和三种从知识库中过滤非 重要单词的方法，来相应解决上述的分类精度和速度问题。s o u m e nc h a k r a b a r t i 等1 3 】研究利用相邻网页的类别信息去改善分类的潜力，并且通过多次考虑已知和 未知类别的相链接的相邻网页，分类精度被迭代的得到提高。 2 0 0 1 年，a r u lp r a k a s ha s i r v a t h a m 等【4 j 认为已经存在的分类算法只利用了网 页中的文本内容信息，但是，有很多其它的信息，如结构、图形、视频等也包含 在网页中，因此，提出了基于网页结构和图形描述的网页自动分类算法。l i s e g e t o o r 等【5 l 从相关类别的网页通常相互之间存在超链接的事实出发，为文本内容 和文档集内的链接结构建立了种基于p r m s ( 概率关系模型) 的统一概率模型。 2 0 0 2 年，y i m i n gy a n g 等【6 l 提出了五种对分类器有重要影响的超文本规则， 他们还发现，将链接所指向的相邻的网页的单词加到链接所在的网页对分类的作 用随数据集不同而呈现有益或有害性，而从相关的网站中提取出m e t a 标记信 息对于改善分类精度非常有用。d a n i e l er i b o n i 7 1 认为网页分类和传统文本分类的 重要不同之处在于网页中的h t m l 结构和超链接提供了更多的信息，基于此， 提出了一种面向网页结构加权技术和一种新的利用当前网页的本地信息来表示 被链接网页的方法，使得超文本分类的实时应用是可能的。a i x i ns u n 等【8 l 认为 超文本不仅仅是简单文本，还具有一些上下文( 如超链接和h t m l 标记) 特征， 并使用支持向量机分类器对超文本( 网页) 进行分类，通过实验证明了利用上下 文特征能显著地改善分类性能。w i l l i a mw c o h e n l v l 指出，通过挖掘( 或探索) 一 个站点内的超链接结构和集中页本身的网页结构能够提高在一个新的，未见过的 站点的网页上定义的分类器的性能，并且在实际的测试例子中，这种技术能显著 的和充分的提高基于单词的统计分类器的精度，平均而言降低一半的错误率。 2 0 0 4 年，j i u z h e nl i a n g 等j lo 】为了减少基于文本内容的中文网页分类的特征 向量维度，过虑冗余的特征词，提出了w o r d f r e q u e n c y c o v e r i n g r a t e ( 词频覆盖 率) 的概念。 在国内研究超文本分类方面，张俐等 h 1 通过分析中文和中文网页的特点，提 西北工业大学硕士学位论文 第一章绪论 出r 一种新的根据中文字间的相关性等信息提取中文网页的关键词，并对词频和 网页描述信息进行加权的中文网页的自动分类算法。 范焱等【1 动针对超文本结构中的结构特征，提出了用n a i v eb a y e s 方法协调分 别利用超文本页面中的文本信息和结构信息的综合分类方法。秦兵等【l 3 】在贝叶 斯分类的基础上，通过对区分性好的词增加权重，对分类性差的词降低权值，提 出了利用类别密度函数似然比来增加特征词的可分性信息的改进的基于统计的 中文网页的分类算法。 李亮等【1 4 j 针对中文网页分类提出了一种基于支持向量机的专业中文网页分 类器，其主要思想是先运用s v m 进行二类分类，再应用v s m ( v e c t o rs p a c em o d e l ， 向量空间模型) 进行多类分类。但是该文献只是利用网页的文本信息，而没有考 虑到网页所固有的特点一超链按。李粤等【1 5 1 在分析和比较常用的文本网页分类 的特征选择方法基础上，提出一种结合x 2 统计方法和互信息方法的联合特征选 择方法。 基于机器学习、数据挖掘的文本分类领域的经典方法不断被引入到超文本分 类当中，如：k n n ( k n e a r e s t n e i g h b o r ，k 最近邻分类) 、n b ( n a i v e b a y e s ， 朴素贝叶斯) 和f o i l ( f i r s to r d e ri n d u c t i v el e a r n 。】 ，一阶逻辑规则学习) 1 6 1 , 最 近的研究集中于在传统文本分类算法基础之上怎样充分利用超文本不同于普通 文本的特点，为分类提供更多的信息。 y ap e n g 等【1 叼认为超链接、m e t a 标记等为超文本分类提供了丰富的信息， 仅仅单独利用某一【6 】中列出的超文本规则，不能集成所有的信息，因此，通过考 虑综合利用多个不同的规则，提出了基于c o - w e i g h t i n g 和m u l t i - i n f o r m a t i o n 的超 文本分类算法。其思想是：在分类之前，解析出超文本文档中的标题、超链接以 及标记等信息，在分类过程中，对这些信息进行c o w e i g h t i n g ( 联合加权) 处理。 刘红l r 7 在以往一些分类方法的基础上，通过分析网页自身的结构，提出了一种 利用扩展锚点文本来对网页进行自动分类的方法，从而解决了怎样通过网页自身 信息以外的信息来反映网页主题的问题。孙建涛等【1 8 】总结了该领域的几个主要 研究方法的优缺点。基于概率模型的计算量大，同时要求纯文本分类器计算的初 始概率不能与实际相差太多，否则可能收敛速度很慢；关系学习方法学习的结果 可解释性好，但归纳学习的速度比较慢，并且用学习到的规则进行分类时，会出 现查准率高、查全率低的特点；支持向量机方法利用组合核函数避免组合多个分 西北工业大学硕士学位论文 第一章绪论 类器。分类准确率高，缺点是s v m 在样本集较大时训练时间长，并且构造核函 数通常要依据经验。 1 3 2 潜在的研究方向 本文主要研究w e b 挖掘中的w e b 信息分类，即文本信息分类和超文本信息 分类。由于网页，邮件等各种格式的文档经过预处理等步骤都可以转化为纯文本， 而纯文本较为容易分析和处理。因此，w e b 信息分类的研究起初只是针对纯文本 信息，超文本分类是在研究文本分类的基础上，结合超文本的结构特性，来提高 超文本信息分类效率的。通过综合以上文献，以及对最新文献的分析，我们认为 有以下潜在的研究方向可供研究； ( 1 ) 要综合各种表示方法，使用纯文本技术不能满足要求。超文本中含有 大量除文本内容之外的对分类有贡献的信息，能否选取合理的表示方式，综合利 用这些信息设计分类方法。 ( 2 ) 超文本是否存在【6 l 所列出的规则，以及能否利用这些规则进行分类，并 且怎样消除单独使用某一规则所带来的随数据集的不同而表现的分类的不稳定 性。 1 4 论文内容安排 第二章从数据挖掘的角度引入了w e b 挖掘的概念，并简要介绍了w e b 挖掘 流程，详细讨论了w e b 挖掘的分类，即w e b 内容挖掘、w e b 结构挖掘和w e b 使 用挖掘的概念、方法等，并对w e b 挖掘分类作了总结。 第三章系统的论述了w e b 文本挖掘中的文本分类的概念、文本分类方法的 分类、文本表示方法、向量空间模型的相关概念、文本分类的特征抽取、文本分 类的特征选择及其常用方法( d f ，i g , m i ，c h i ，t s ) 、文本分类的典型方法( k n n ， t f i df n a v eb a y e s ) 、文本分类的评价标准以及文本分类试验方法的步骤。最后 重点介绍了基于l e e 模型的n a i v eb a y e s 文本分类方法。 第四章从超文本的结构性特点及其组成开始，简要讨论了当前常用的超文本 分类方法。然后重点论述了基于规则的超文本分类方法：我们在超文本不同于普 西北工业大学硕士学位论文第一章绪论 通文本的基础上引入y i m i n gy a n g 五种超文本规则，并基于其中的三种规则，分 别用四种方法表示超文本，利用典型的文本分类方法t f i d f 和n a i v eb a y e s ，在 选定的超文本数据集进行分类试验，并对应用和未应用超文本规则时的分类精度 和运行时间作了比较，同时也对两个分类器的性能作亍对比。 第五章对全文作了总结，分析了有待改进的地方，并预测了进一步的研究方 向。 函北工业大学硕士学位论文 第二章w e b 挖掘概述 2 1 引言 第二章w e b 挖掘概述 i n t e m e t 的飞速发展与广泛应用，使得w e b 上的信息量以惊人的速度增长， 也为数据挖掘提供了丰富的数据源和新的研究课题。当前数据挖掘处理的对象主 要是结构化的数据，即关系数据库中的数据，将数据挖掘技术应用到半结构化的 w e b 数据上，使其能够针对w e b 数据的特点进行知识发现，将为数据挖掘开辟 一个新的研究领域，即w e b 挖掘。 2 2 数据挖掘 2 2 1 数据挖掘的概念 知识发现( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ，即数据库中的知识发现) 是从大 量数据中提取出可信的、新颖的并能被人们所理解的模式的高级处理过程。 数据挖掘一般指数据库中的知识发现，它是伴随着数据库技术的发展，数据 库中存储的数据量急剧增长而出现的。简单的说，数据挖掘就是从大量数据中“挖 掘”知识，利用隐藏在大量数据背后的知识为人们提供更加有价值的信息服务。 随着i n t e r n e t 的高速发展，数据挖掘不仅局限于数据库和数据仓库中的结构化数 据，而且包括空间数据、时序数据、文本、多媒体等复杂数据类型。 2 2 2 数据挖掘的分类 数据挖掘涉及的学科领域和方法很多，并有多种分类法： ( 1 ) 根据挖掘对象分：面向关系的数据库、面向对象的数据库、面向事务 的数据库、面向空间的数据库、面向时间序列的数据库、面向文本的或者多媒体 等复杂数据类型的数据库、面向w e b 等，本文主要研究最后一种也是最复杂的 西北工业大学硕士学位论文 第二章w e b 挖掘概述 面向w w w 的数据挖掘； ( 2 ) 根据挖掘方法分：机器学习方法、统计方法、神经网络方法等； a 机器学习方法可细分为：归纳学习方法( 决策树、规则归纳等) 、基于范 例学习、遗传算法等。 b 统计方法可细分为：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯 判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索 性分析( 主元分析、相关分析法等) 等。 c 神经网络方法可细分为：前向神经网络( b p 算法等) 、自组织神经网络( 自 组织特征映射、竞争学习等) 等。 ( 3 ) 根据挖掘任务分：可分为关联规则、分类、聚类、时间序列模式预测和 相似模式发现。 a 关联规则：典型的关联规则发现算法是a p r i o r i 算法，该算法也称广度优 先算法。它是目前除a i s 算法、面向s q l 的s e t m 算法外几乎所有频繁项集发 现算法的核心，其基本思想是：如果一个项集不是频繁集，则其父集也不是频繁 集，由此大大地减少了需要验证的项集的数目，在实际运行中它明显优于a i s 算法。 b 分类：数据挖掘的一个重要任务是对海量数据进行分类。数据分类是基 于一组数据的某些属性的值进行的。数据分类的方法很多，包括决策树方法、统 计学方法、神经网络方法等，本文就是研究数据分类的。 c 聚类：其基本思想是对数据进行分析的过程中，在考虑数据间的“距离” 的同时，更侧重考虑某些数据间具有类的共同内涵。数据聚类是对一组数据进行 分组，这种分组基于最大的组内相似性与最小的组问相似性。 d 时间序列模式预测：一次事件的发生会导致某些事物的相继发生的事件 模式，称为时序模式。 e 相似模式发现：在时态或空间时态数据库( 如股票价格指数的金融数据 库、医疗数据库、多媒体数据库等) 中搜索相似模式的目的是发现和预测风险、 因果关系及关联于特定模式的趋势。 上述数据挖掘任务分类可总结为表2 - 1 ： 1 0 西北工业大学硕士学位论文第二章w e b 挖掘概述 表2 1 数据挖掘任务分类总结 挖掘任务挖掘算法典型应用 关联规则统计学、集合理论市场货篮分析 分类决策树、神经网络、粗糙集产品行销、定量控制、危险评估 聚类神经网络、统计学 市场分析 时间序列预测 统计学、a r m a 模型、神经网络 销售预测、利预测、存货控制 相似模式发现 统计学、集合理论市场货篮分析 2 3w o b 挖掘 2 3 1 w e b 数据的特点 要进行数据挖掘，前提是要有丰富的数据，而w w w 就是一个巨大的、分 布广泛的全球性信息资源库，它包括新闻、广告、消费、金融管理、教育、政府、 电子商务、电子政务等各个领域的信息，为数据挖掘提供了丰富的资源。然而， 作为数据挖掘数据源的w 曲数据有着自身明显的特点，如包含着动态变化的超 链接信息以及对于w e b 页面的访问和使用的信息等，对基于w e b 的数据控制方 法也提出了新的要求。与传统的数据库数据相比，w e b 数据的特点可概括为以下 几点： ( 1 ) 超大的数据规模 w e b 的数据量目前以兆兆字节( t e r a b y t e ) 计算。而且，随着i n t e r n e t 技术的 不断发展，许多机构和社团都在把各自大量的可访问信息置于网上，从而使其数 据量仍在以极为迅猛的速度快速增长，不仅网页数量在猛增，页面内容、网页链 接和访问记录也经常更新，如：新闻、股票市场、服务中心和企业网站。这使得 传统的数据挖掘模式受到挑战，构造一个数据仓库来复制、存储或集成w e b 上 的所有数据，相对比较困难。 ( 2 ) 复杂的数据结构 i n t e m e t 的开放性导致了w e b 数据在逻辑结构上的极端复杂性( 如图2 - 1 ) 。 传统的数据库数据大多来自同构系统，或者是来自异构平台但经过了同构处理的 同构数据，而w e b 数据由于其来源的多元性，因而使得其结构具有显著的异构 特征。另外就w e b 页面本身而言，它的复杂性要远高于任何传统的文本文档， 西北工业大学硕士学位论文 第二章 w e b 挖掘概述 图2 - iw e b 数据的逻辑结构 它的页面不是统一的格式结构，包含了远比任何其它文本文档多得多的风格和内 容。 ( 3 ) 无序的数据 从数据规模来看，w e b 无疑可以看作是一个巨大的数字图书馆，然而它却不 具备普通图书馆的有序性和组织性，而是零散和无序存放的。因此，用户感兴趣 的极少相关或有用信息就被大量的无用数据淹没。 2 3 2w 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 挖掘是对数据挖掘的一种新的发展和应用，但又不同于传统的数据挖掘。 其区别在于： ( 1 ) 对象不同，w e b 挖掘的是海量、分布、动态、异质的w e b 文档，其信 息存储不同于结构化的数据库； ( 2 ) 挖掘的模式不同，w e b 在逻辑上是一个由文档节点和超链接构成的图， 1 2 西北工业大学硕十学位论文 第二章w e b 挖掘概述 因此w e b 挖掘所得到的可能是关于w e b 内容的，也可能是关于w e b 结构的； ( 3 ) w e b 数据的半结构化或非结构化特征，使得这些信息数据难以清楚地 用数据模型加以表示，且缺乏机器可理解的语义，而数据挖掘的对象局限于数据 库中的结丰句r 化数据，并利用关系表等存储结构来发现知识； ( 4 ) 挖掘技术不同，有些数据挖掘技术并不适用于w e b 挖掘，即使可用也 需要建立在对w e b 文档进行预处理的基础上，因此w e b 挖掘需要用到更多的有 别于传统数据挖掘的技术。 2 3 3w e b 挖掘流程 与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、动态 的、并且是容易造成混淆的，所以很难直接以w e b 上的数据进行数据挖掘，而 必须经过必要的数据处理。典型w e b 挖掘的处理流程如图2 2 所示： 析 图2 - 2 典型w e b 挖掘的处理流程 ( 1 ) 资源发现 任务是用c r a w l e r 或s p i d e r 在线收集w e b 文档，并从目标w e b 文档中得到 数据，值得注意的是信息资源不仅限于在线w e b 文档，还包括电子邮件、电子 文档、新闻组，或者网站的日志数据甚至是通过w e b 形成的交易数据库中的数 据。 ( 2 ) 信息选择和预处理 任务是从取得的w e b 资源中剔除无用信息和将信息进行必要的整理，对检索 到的w 曲资源的任何变换都属于此过程，如w e b 文档中自动去除广告连接、去 除多余格式标记、自动识别段落或者字段并将数据组织成规整的逻辑形式甚至是 关系表、英文单词的词干提取、高额低频词的过滤、汉语词的切分、索引库的建 西北工业大学硕士学位论文 第二章w e b 挖掘概述 立甚至把w e b 数据变换成关系。 需要说明的是，w e b 挖掘与i r ( i n f o r m a t i o nr e t r i e v a l ，信息检索) 、 i e ( i n f o r m a t i o ne x t r a c t i o n ，信息抽取) 是有所区别的，瓜是根据用户的需求描述 从受档集中自动地检索与用户需求相关的文档，同时使不相关的尽量少。它是目 标驱动，查询触发的过程，主要任务是对于给定的文档怎样建索引和怎样检索。 而i e 的目的在于从文档中找到需要的数据项目，它对文档的结构表达的含义感 兴趣，它的一个重要任务就是对数据进行组织整理并适当建立索引。 ( 3 ) 模式发现 自动进行模式发现。可以在同一个站点内部或多个站点之间进行，以自动发 现w e b 站点的共有模式。 ( 4 ) 模式分析 验证、解释上一步骤产生的模式，并进行可视化。可以是机器自动完成，也 可以是与分析人员进行交互来完成。 2 3 4w 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 bs t r u c t u r ei v t h 血) 和w e b 使用( 或w e b 日 志) 挖掘( w e b u s a g e m i n i n g ) ，如图2 3 所示。 2 3 4 1w e b 内容挖掘( w e bc o n t e n tm i n i n g ) w e b 内容挖掘是指从w e b 上文档的内容及其描述信息中获取潜在的、有价 值的知识或模式的过程。 w e b 内容挖掘分为两大类： ( 1 ) 对于文本文档( 包括t e x t ，p o s t s c r i p t , p d f , h t m l 等) 的挖掘称为文本挖 掘。大多数基于数据库的数据挖掘方法经过相应的改进处理后均可应用于w e b 文本挖掘，如数据归纳、分类、聚类、关联规则挖掘等。w e b 文本挖掘的数据对 象既可以是结构化的也可以是非结构化的、半结构化的。w e b 文本挖掘的结果 既可以是对某个文本内容的概括，也可以是对整个文本集合的分类结果或聚类结 果。 目前w e b 文本挖掘的主要研究内容是对w e b 上大量文档集合的内容进行总 1 4 诬北工业大学硕士学位论文 第二章w e b 挖掘概述 图2 - 3w e b 挖掘分类 结、分类、聚类、关联分析、科学文献资料浏览导航，以及利用w 曲文档进行 趋势预测等。其一般处理过程如图2 - 4 所示。 图2 - 4w e b 文本数据挖掘的一股处理过程 ( 2 ) 对于多媒体文档( 包括图像、音频、视频等) 的挖掘称为多媒体挖掘， 主要是指通过对w e b 上的图像、音频和视频等数据进行预处理，应用存储和搜 索技术与标准的数据挖掘方法集成，对其中潜在的、有意义的信息和模式进行发 掘的过程。 多媒体数据挖掘的方法主要有：多媒体数据中的相似检索，主要有基于描 述的检索系统和基于内容的检索系统两种多媒体标引和检索技术；多媒体数据 的多维分析，可以按传统的从关系数据中构造数据立方体的方法，设计和构造多 媒体数据立方体；分类和预测分析，主要应用于天文学、地震学和地理科学的 研究，决策树分类是最常用的方法。 多媒体数据的关联规则挖掘主要包括以下三类规则：图像内容和非图像内 容之间的关联；与空间关系无关的图像内容的关联；与空间关系有关的图像 内容的关联。 对于w e b 内容挖掘，一般从两个不同的观点来进行研究： ( 1 ) i r 的观点 w e b 内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助用户过 西北工业大学硕士学位论文 第二章w e b 挖掘概述 滤信息。 a 对于非结构化文档：非结构化文档主要指w e b 上的自由文本，包括小说、 新闻等。大部分研究都是建立在向量空间模型( v e c t o rs p a c em o d e l ) 的基础上， 将单个的词汇看成文档集鲁中的属性，只从统计的角度将词汇孤立地看待而忽略 该词汇出现的位置和上下文环境。属性可以是布尔型，根据词汇是否在文档中出 现而确定其值，也可以是频度，即该词汇在文档中的出现频率。这种方法可以扩 展为选择终结符、标点符号、不常用词汇的属性作为考察集合。缺点是自由文本 中词汇量非常大，处理起来开销较大，为解决这个问题人们采取了不同技术，如 信息增益，交叉熵、差异比等，其目的都是为了选择更有价值的属性。另外，一 个比较有意义的方法是潜在语义索引( l a t e n ts e m a n t i ci n d e x i n g ) ，它通过分析不 同文档中相同主题的共享词汇，找到他们共同的根，用这个公共的根代替所有词 汇，例如：“i n f o r m i n g ”，“i n f o r m a t i o n ”，“i n f o r m e d 可蛆用他们的根 i n f o r m ”来表示， 这样可以减少属性集合的规模。其他的属性表示法还有词汇在文档中的出现位 置、层次关系、使用短语、使用术语、命名实体等。 b 对于半结构化文档：与非结构化数据相比，w e b 上的半结构化文档挖掘 指在加入了h t m l 、超链接等附加结构的信息上进行挖掘，其应用包括超链接文 本的分类、聚类、发现文档之间的关系、提出半结构化文档中的模式和规则等。 ( 2 ) d 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 内容挖掘相关研究主要是基于半结构化数据进行 的。利用o e m ( o b j e c te x c h a n g em o d e l ) 模型将半结构化数据表示成标识图。o e m 中的每个对象都有o l d ( 对象标识) 和值，值可以是原子类型，如整型、字符串 型、g i f 、h t m l 等，也可以是一个复合类型，以对象引用集合的形式表示。由 于w e b 数据量非常庞大，从应用的角度考虑，很多研究只处理半结构化数据的 一个常用子集。些有意义的应用是建立多层数据库( m l d b ) ，每一层是它下 西北工业大学硕士学位论文 第二章w e b 挖掘概述 面层次的概化，这样就可以进行一些特殊的查询和信息处理。 由于在d b 观点下数据的表示方法比较特殊，其中包含了关系层次和图形化 的数据，所以大部分建立在扁平数据集合之上的数据挖掘方法不能直接使用，目 前已经有人针对多层数据库挖掘算法进行研究。 2 3 4 2 骶b 结构挖掘( w e bs t r u c t u