（计算机软件与理论专业论文）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 数据预处 理等相关知识进行了阐述；然后研究了关联规则基本理论及关联规则经典算 法：最后为了解决现实数据库中每个项目的分配不均匀性和重要性差异，重 点研究了加权关联规则挖掘算法。 深入分析了著名的加权关联规则挖掘算法删e w a p r i o r i 算法，发现了 该算法中存在的问题。其一，n e k v a p r i o r i 算法进行项集连接有不合理之处； 其二，需要重复扫描数据库来计算候选项集的支持计数，从而严重影响了算 法的运行效率；其三，n e w a p f i o f i 算法没有对候选项集进行剪枝，这样会保 留许多无用的候选项集。针对上述三方面问题，本文给出了一种改进的算法 w a r d m ( w e i g h t e da s s o c i a t i o nr u l e s d a t am i n i n g ) 算法。该算法对候选 i 项集、候选2 项集及候选k 项集( k 2 ) 地生成分别讨论，避免漏掉加权频 繁项集；利用事务标识号集合来计算候选项集的支持计数，这样只需扫描一 遍事务数据库，减少了数据库的扫描次数；根据加权关联规则的性质，在计 算候选项目集时进行两次减枝，减少了候选项目集的数量。实验结果表明， 新算法在时间上地消耗明显少于n e w a p f i o f i 算法，有效提高了算法的效率； 同时，新算法能有效减小候选顶集的规模。 关键词：w e b 数据挖掘；关联规则；加权关联规则；n e w - a p r i o r i 算法 哈尔滨工程大学硕士学位论文 ii a b s t r a c t d a t am i n i n gr e f e r st oap r o c e d u r ew h e r es o m ei m p l i c i t , u n d i s c o v e r e d ，u s e f u l k n o w l e d g e i se x t r a c t e df r o ml a r g ea m o u n t so fd a t a b e c a u s eo ft h ef a s t d e v e l o p m e n to fi n t e r n e t ，m o r ea n dm o r ed a t ah a sb e e ng e n e r a t e do nt h ew e b b y a p p l y i n gt h ea p p r o a c h e so fd a 嗍i n i n gi n t ow e bt os o l v es o m ep r o b l e m s ，an e w f i e l dw e bd a t am i n i n gi sp r e s e n t e d w e bd a t am i n i n gh a sm a n yr e s e a r c hp o i n t s m i n i n ga s s o c i a t i o nr u l e si so n e o ft h ei m p o r t a n th o t s p o t s a tf i r s t ，t h i st h e s i se x p a t i a t e so nd a t am i n i n g ，w e bd a t a m i n i n g ，w e bd a t ap r e p r o c e s s i n ga n ds o m er e l a t i v ek n o w l e d g e t h e n ，t h eb a s i c t h e o r ya n dc l a s s i c a la l g o r i t h mi na s s o c i a t i o nr u l em i n i n ga r er e s e a r c h e d f i n a l l y , t os o l v et h eu n b a l a n c e a n dd i f f e r e n ti m p o r t a n c eo fi n d i v i d u a li t e mi nd a t a b a s e ，t h e t h e s i sp u t st h ee m p h a s i so nw e i g h t e da s s o c i a t i o nr u l e sa l g o r i t h m t h ef a m o u sa l g o r i t h mn e w - a p r i o r ia l g o r i t h mi s t h o r o u g h l yr e s e a r c h e d s o m ep r o b l e m si nt h i sa l g o r i t h ma r ep o i n t e do u t f i r s t ，t h e r ei sas h o r t c o m i n gi n i t e m s e t sc o n n e c t i o n s e c o n d ，m u l t i p l ed a t a b a s es c a ni sn e e d e dt oa d du pt h ec o u n t o fc a n d i d a t e i t e m s e t s ，w h i c h h a ，s s e v e r e l yi n f l u e n c e d i t s e f f i c i e n c y t h i r d ， n e w a p r i o r ia l g o r i t h md o e s n tp r u n ec a n d i d a t ei t e m s e t s ，w h i c hc a l lk e 印d o w n a l o to fu s e l e s sc a n d i d a t ei t e m s e t s a ni m p r o v e da l g o r i t h m w a r d m ( w e i g h t e d a s s o c i a t i o nr u l e sd a t am i n i n g ) ，i sp u tf o r w a r di nt h i st h e s i s ，w h i c hc a nm a k eu p t h ea b o v e m e n t i o n e df l a w so fn e w a p r i o r iv e r yw e l l t h i sa l g o r i t h md i s c u s s e s g e n e r a t i o n so fc a n d i d a t e 一1s e t s ，c a n d i d a t e - 2s e t sa n dc a n d i d a t e - ks e t s ( k 2 ) ，w h i c h c a r ta v o i d m i s s i n gw e i g h t e df r e q u e n t i t e m s e t s ；t h es e t so ft r a n s a c t i o n i d e n t i f i c a t i o nn u m b e ra r eu s e dt oa d du pt h ec o u n to fc a n d i d a t ei t e m s e t s ，w h i c h c a r ls c a i lt r a n s a c t i o nd a t a b a s ef o ro n l yo n et i m e ，t h e r e f o r e ，i tr e d u c e st h es c a n n i n g t i m e s ；o nt h eb a s i so ft h ec h a r a c t e ro fw e i g h t e da s s o c i a t i o nr u l e s ，c a n d i d a t e i t e m s e t sa r ep r u n e dt w i c e ，w h i c hc a nr e d u c et h ea m o u n to fc a n d i d a t ei t e m s e t s e x p e 订m e n t a lr e s u l t ss h o wm a t ：c 矗鲁e wa l g o r i t 如g e t sl e s st i m ec o i l s u m p t i o nt i 姗 哈尔滨工程大学硕士学位论文 n e w - a p r i o r id o e s ，g r e a t l ye n h a n c e st h ee f f i c i e n c y m e a n w h i l e ，t h en e wa l g o r i t h m c a nd e c r e a s et h es c a l eo fc a n d i d o g ej t e m s e t s k e y w o r d s ：w e bd a t am i n i n g ；a s s o c i a t i o nr u l e s ；w e i g h t e da s s o c i a t i o nr u l e s ； n e w - a p r i o r ia l g o r i t h m 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：释瞿 日期：2 0 0 年3 月i o 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：翟星 日期：2 0 胡年3 月io 日；写罱擀 2 k 7 年弓月日 哈尔渎卫程大学硕士学位论文 1 1 研究背景 第1 章绪论 当今数据库技术和数据库管理系统得到了广泛应用，全球范围内数据库 中存储的数据量急剧增大，有些公司的商业数据目前已经超过几百万条记录。 有些面向科学研究数据库的数据量也非常惊人。庞大的数据对人工处理来说 是非常困难的，人们需要对数据进行处理，从中找出并发现规律，以帮助人 们更好地进行决策和研究。数据挖掘是从大量的、不完全的、有噪声的、模 糊的、随机的数据中提取隐含在其中的、人们事先不知到的、但又是潜在有 用的信息和知识的处理过程。数据挖掘是一个多学科交叉研究领域，它融合 了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、 信息检索、高性能计算以及数据可视化等最新技术的研究成果。 在w w w 迅猛发展的同时，人们也面临着“信息爆炸而知识贫乏”的问 题。在信息量极大丰富的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 r 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 em i n i n g ) 、w e b 日志挖掘( w e b l o gm i n i n g ) 。目前，w e b 数据挖掘已经成功应用到很多领域。诸如银行、交 通、电信、保险、电子商务、客户关系管理、网络广告分析领域。 w e b 数据挖掘的主要任务包括预测建模、关联分析、聚类分析、异常检 测等。其中关联规则( a s s o c i a t i o nr u l e s ) 作为w e b 数据挖掘中最为热门的研 究课题之一，其挖掘目标是从异构的数据库中找出数据项之间的关联关系， 哈尔滨工程大学硕士学位论文 誓量宣审_ i i i r i i i 暑宣| 暑| 宣胃嗣冒譬 它实际上是一种知识表示形式。关联规则是由a g m w a l 等人在对市场购物篮 问题( m a r k e tb a s k e t a n a l y s i s ) 进行分析时首次提出，用于发现销售事务数据 库中的顾客购买模式。关联规则可以应用于顾客购物分析、目录设计、商品 广告、邮寄分析、追加销售、- 商品货架设计、仓储规划、网络故障分析以及 用购买模式对用户进行分类等。目前，国际国内有大批学者对关联规则进行 着研究。 1 2 研究现状 关联规则挖掘是数据挖掘的一个重要问题，由于符合人类认知世界的思 维模式，关联规则挖掘广泛应用于商业、保险等行业。当前对关联规则的研 究集中在对挖掘算法的改进上，其中有许多研究热点，如在处理大量数据时 如何提高算法的效率、当数据迅速更新时如何改进算法、数值型变量的处理 问题、项目集在加权情况下的关联规则挖掘方法等。 关联规则挖掘首先由a g 矗w 甜，i m i e l i n s k i 和s w a m i 提出。a p r i o r i 算法 由a o r a w a l 和s r i k a n t 提出“! ，后来人们又在此基础上对a p r i o r i 算法进行了一 系列的改进，比较著名的包括使用哈希表提高关联规则挖掘效率，采用事务 压缩技术对所扫描的事务集进行压缩，采用划分技术对事务集进行分割，采 用选样技术来进行挖掘以及采用动态项集计数的方法等。针对a p r i o r i 算法出 现了一些改进的挖掘算法，如d h p ( d i r e c th a s h i n ga n dp r u n e ) 算法，p a r t i t i o n 算法等等，这些算法需要多次扫描数据库，产生多个候选数据项集，使得算 法执行效率低，针对这些问题，有关学者提出了一些新的频繁项集产生方法， 如f p g r o w t h ( f r e q u e n tp a t t e mg r o w t ha l g o r i t h m ) 算法等等。 关联规则挖掘有许多扩展，包括多层关联规则挖掘，多维关联规则挖掘， 基于约束的关联规则挖掘，周期关联规则挖掘，加权关联规则挖掘等，目前 已经有一些学者对这些算法进行相关研究。 此外，关联规则挖掘技术不仅可直接作为一种决策支持的手段，还可以 应用到其它数据挖掘技术中，如关联规则挖掘技术可用于决策树归纳以及时 间序列数据分析、分类等数据挖掘技术中。另外，数据分割下的关联规则问 题研究和算法分析，以及利用时间约束关联规则提高数据挖掘质量的研究也 2 哈尔滨工程大学硕士学位论文 i l l_； i ii _ 暑宣薯；罩宣目置嗣；置一 都是目前数据挖掘的研究重点。 带有项权重的关联规则挖掘称为加权关联规则挖掘。自1 9 9 8 年以来，加 权关联规则挖掘得到了广泛的重视和研究，对加权关联规则挖掘算法的研究 国内外已有了很多成果。加权关联规则挖掘算法总结起来主要分为两类：一 类以a p r i o r i 算法思想为基础；一类以f p - g r o w t h 算法思想为基础。对前一类 算法的研究国内外都做了大量的工作，其典型的算法有1 9 9 8 年香港中文大学 的c h c a i 等人提出的m i n w a l ( o ) 算法和m i n w a l ( w ) 算法，2 0 0 3 年张智 军等人提出的n e w - a p r i o r i 算法，此外还有w a r 算法和m w q a r 算法等。 这类算法的一个共同缺点就是需荽多次的扫描数据库，严重的影响了算法的 挖掘速度。对后一类算法的研究成果尽管还很少，但是这类算法的缺点是当 条件模式树( c o n d i t i o n a lp a u e mt r e e ) 的深度很深或者是最小支持度计数很 小时，递归的产生条件模式树将耗费很大的内存资源，阻碍了算法挖掘速度 的提高。 与国外相比，国内对数据挖掘的研究稍微晚一些。1 9 9 3 年国家自然科学 基金首次支持该领域的研究项目。国内从事数据挖掘研究的人员有的在大学 院校，有的在研究所或公司。所涉及的研究领域很多，一般集中于算法的研 究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究。目前进行的大 多数研究项目是由政府资助进行的，如：8 6 3 计划、国家自然科学基金等。 可以看出，数据挖掘的研究和应用得到了学术界、产业界和政府部门的大量 重视。 目前国内对关联规则挖掘所涉及的研究领域很多，一般集中于算法的研 究、关联规则挖掘的实际应用以及关联规则挖掘理论方面的研究。主要算法 有：a p r i o r i 算法的改进算法、基于f p 树的挖掘算法、并行关联规则挖掘算 法、关联规则增量式更新挖掘算法、量化关联规则挖掘算法、加权关联规则 挖掘算法、基于约束的关联规则挖掘算法、基于兴趣度的关联规则挖掘算法 及基于参考度的关联规则挖掘算法。 1 3 研究意义 当前，i n t e r n e t 已发展成为个巨大的、蕴涵着具有潜在价值知识的分布 3 哈尔滨工程大学硕士学位论文 l mh i l li i m 置墨昌i 宣；| 置昌奄_ 式信息空间。w e b 中包含了w e b 页面的内容信息、丰富的超链接信息，以及 用户访问的日志信息，为数据挖掘提供了丰富的资源。各种形式的信息大量 地产生和收集导致了信息爆炸o 如何快速、准确地获得有价值的网络信息， 如何从这些海量异构数据中发现知识，导致了w e b 数据挖掘领域的出现。它 不仅被许多研究人员看作是数据库系统和机器学习方面一个重要的研究课 题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。 w e b 数据挖掘源于数据挖掘技术和i n t e m e t 技术的结合，辅以计算机语 言学、图形学、信息学等多个领域的知识。w e b 数据挖掘的困难在于w 曲上 的数据是无序的、非结构化或半结构化的，并且存在大量的冗余和噪声n - 。近 年来数据挖掘理论技术越来越成熟，应用也越来越广。如何结合已有的数据 挖掘理论技术应用于w 曲数据挖掘中成为当前人们研究的热点。随着知识经 济的发展，w e b 数据挖掘在企业销售，客户关系管理等众多领域发挥着越来 越重的作用。为此对w e b 数据挖掘尤其是在w e b 日志挖掘上如何优化企业 门户网站结构的研究具有重要意义。 目前对数据挖掘的研究主要集中在分类、聚类、关联规则挖掘、序列模 式发现、异常和趋势发现等方面，其中关联规则挖掘在商业等领域中的成功 应用使它成为数据挖掘中最活跃、最成熟的研究方向。关联规则挖掘算法是 数据挖掘中最重要的技术之一，是数据挖掘中的一个重要课题。关联规则挖 掘技术有很多，如多维关联规则挖掘、多层关联规则挖掘、加权关联规则挖 掘、关联规则增量式更新算法和关联规则并行发现算法等。加权关联规则挖 掘是目前重点研究的方向。 针对现有加权关联规则挖掘算法的不足，本文在深入研究加权关联规则 挖掘算法的基础上，给出了种新的加权关联规则挖掘算法。这项研究是面 向应用的，研究的结果可以为诀策者提供重要的、极有价值的信息或知识， 从而产生较大的经济效益。 1 4 研究内容与论文组织结构 本论文的主要研究内容有以下几点： ( 1 ) 对w e b 数据挖掘理论、方法和技术进行研究，对w e b 数据挖掘中 4 哈尔滨工程大学硕士学位论文 | m , u 一l _ i ln lli- lm m i 宣审 的关联规则和加权关联规则理论进行深入的研究。 ( 2 ) 对各种加权关联规则算法进行了深入的研究。重点分析了张智军等 人提出的n e w - a p r i o r i 算法。 ( 3 ) 针对n e w a p r i o r i 算法时间复杂度过高和候选项集数量过大的不足， 给出基于两次剪枝的w a r d m 算法，给出与其相关的定理及其证明过程。 w a r d m 算法在挖掘事务数据库时，只需要扫描一次数据库便可产生所有的 加权频繁项目集，能减少对数据库的访问次数，提高整个挖掘的效率。通过 两次剪枝可有效减少候选项集的数量。 ( 4 ) 用合成数据集t 1 0 1 4 d 1 0 0 k 和t 4 0 1 1 0 d 1 0 0 k 进行实验，并分析实 验结果。 本论文内容组织如下： 第l 章叙述研究背景、研究现状和研究意义，给出本文研究的主要内容。 第2 章介绍数据挖掘、w e b 数据挖掘和关联规则。首先介绍数据挖掘定 义、过程、分类和应用。然后介绍w e b 数据挖掘的定义、分类和发掘的主要 过程，接着阐述w e b 数据挖掘前期工作数据预处理的整个过程。然后介 绍关联观则的基本概念、性质、挖掘的过程和分类。接着讨论关联规则的应 角和主要研究方向，重点讨论关联规则挖掘的经典算法a p r i o r i 算法，最后对 a p r i o r i 算法进行分析。 第3 章详细介绍加权关联规则，重点讨论加权关联规则模型和 n e w a p r i o r i 算法，对n e w - a p d o f f 算法进行了剖析，并且对其进行改进，给 出n e w a p r i o r i 算法的改进算法w a r d m 算法，然后用实例进行验证，说明 w a r d m 算法与n e w - a p r i o r i 算法相比所具有的优势。 第4 章使用t 1 0 1 4 d 1 0 0 k 和t 4 0 1 10 d 10 0 k 数据集，对w a r d m 算法和 n e w - a p r i o r i 算法进行性能测试，并将二者的测试结果进行对比评估，并对实 验结果进行了详细的分析。 5 哈尔滨工程大学硕士学位论文 第2 章w e b 数据挖掘及相关技术概述 2 1 数据挖掘 2 1 1 数据挖掘的定义 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 ) 等形式1 。与数据挖掘相近似的术语还有很 多，如数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 、数据 融合( d a t af u s i o n ) 、数据分析以及决策支持等。数据挖掘中的原始数据既可 以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图 片、图像数据，甚至是分布在网络上的异构型数据。 数据挖掘也可以被描述为试图创建一个数据库中描述的复杂世界的简单 模型，因而可以说数据挖掘是处理大量信息的方法，并且它可以比人更快的 速度发现有用的信息。由于数据挖掘与知识发现有很大的重合度，大部分学 者认为数据挖掘与知识发现是筹价的概念“。也有一些学者把数据挖掘看作知 识发现过程的一部分m “，认为知识发现是指从数据库中发现知识的全部过程， 而数据挖掘就是这个处理过程中的一个最为重要的步骤。 2 商业角度的定义 数据挖掘从本质上说是一种新的商业信息处理技术。数据挖掘技术把人 们对数据的应用从低层次的搜索查询，提高到分析预测和决策支持等更高级 应用上。它通过对这些数据进行微观、中观乃至宏观的统计、分析、推理和 综合，发现数据之间的关联性、未来趋势以及一般性的概括知识等，商务活 动可以通过这些知识性的信息被进行指导。 6 哈尔滨工程大学硕士学位论文 从分析、决策和预测等高级商业目的来看，原始数据只是未被开采的矿 山，需要通过挖掘和提炼才能获得对商业目的有价值的规律性知识。这正是 数据挖掘这个名词的由来。所以，从商业角度来看，数据挖掘就是按照企业 的既定业务目标，对大量的企业数据进行深层次的分析以揭示隐藏的、未知 的规律性并将其模型化，从面支持商业决策活动川。从商业应用角度对数据挖 掘进行说明，能够更全面地了解数据挖掘的真正含义。它有别于人工智能等 其它研究领域，它是在具有很强的商业目的情况下提出的。同时，数据挖掘 技术只有面向特定的商业领域才有应用价值。数据挖掘所有发现的知识都是 相对的，并且对特定的商业行为才有指导意义。 2 1 2 数据挖掘的分类 根据挖掘对象、挖掘方法、挖掘任务和挖掘发现的知识类型分为以下四 类： 1 根据挖掘对象分类 根据挖掘的对象可分为关蒹类型数据库、演绎数据库、面向对象数据库、 事物数据库、时态数据库、多媒体数据库、空间数据库、异质数据库、i n t e m e t 信息库等数据挖掘以及新兴的数据仓库等。 2 根据挖掘方法分类 根据挖掘的方法可分为数据库方法、聚类分析方法、近似推理和不确定 性推理方法、机器学习方法、统计方法、探索性分析方法、神经网络方法、 遗传算法、现代数学分析方法、粗糙集方法、基于证据理论和元模式的方法、 集成方法等。 3 根据挖掘任务分类 根据挖掘的任务可分为关联规则发现、分类或预测模型发现、数据总结 与聚类发现、序列模式发现、混沌模式发现、相似模式发现、依赖关系或依 赖模型发现、异常和趋势发现等： 4 根据数据挖掘发现的知识类型分类 根据挖掘的知识类型可分为关联规则、特征规则、聚类规则、区分规则、 分类规则、总结规则、偏差规则、模式分析和趋势分析等。 7 哈尔滨工程大学硕士学位论文 2 1 3 数据挖掘的过程 数据挖掘目前还没有统一的模型，比较有代表性的一种过程模型是 u s a m a m f a y y a d 等人提出的多处理阶段模型”，数据挖掘整个过程包括九个 阶段： 1 数据准备 数据准备主要是熟悉相关背景知识，了解数据挖掘的相关情况，弄清楚 用户的要求。 2 数据选择 数据挖掘通常并不需要使用全部数据，有些数据对象和数据属性不会影 响到建立模型获得的模式，这些数据的加入会极大降低挖掘效率，甚至还可 能引起挖掘结果的偏差。因此，按照用户的要求从数据中提取出与数据挖掘 有关的数据，数据挖掘算法将主要从这些数据中提取有用的知识。在此过程 中，将会利用一些数据库操作对数据进行操作处理，其目的是为了对数据挖 掘对象的集合进行辨别，从而缩小处理范围有效提高效率。 3 数据预处理 为了进一步的分析做准备，需要研究数据的质量，并确定将要进行挖掘 操作的类型。主要包括消除重复记录、消除噪声、推导计算缺值数据、完成 数据类型转换等。 4 数据缩减 数据缩减是在数据预处理基础上对挖掘数据的进一步缩减，数据缩减将 辨别出需要挖掘的数据集合，缩小处理范围。数据缩减针对经过预处理的数 据，根据数据挖掘的任务进行再处理，减少数据量。包括选择、转换、创建 数据挖掘所需变量，合理选择记录。数据缩减就是将初始数据集转换到某种 更加紧凑的形式而不会丢失有意义的语义信息的过程。数据缩减通常包括更 复杂数据缩减处理：数据聚集、属性值缩减、维缩减和数据压缩。 5 确定数据挖掘目标 数据挖掘的目标是根据用户的需求来确定的，即确定用户所需要的知识 类型，因数据挖掘的不同类型会影响到算法的选取。 8 哈尔滨工程大学硕士学位论文 6 确定数据挖掘的算法 根据上一步骤得出的数据挖掘目标，选取合适的算法，包括合适的模型 和参数，以达到选取的数据挖掘算法匹配整个数据挖掘的评价标准。数据挖 掘常用的方法有：关联规则、统针分析、遗传算法、聚类分析、模糊推理、 粗糙集方法、人工神经网络、决策树与决策规则、近邻搜索方法、公式发现 世q 1 寸o 7 数据挖掘 利用数据挖掘算法提取出用户所需的知识，并用一种特定的方式表示这 些知识。 8 模式解释 对发现的模式进行解释，转换成有用知识。 9 知识评价 包含外推、解释和模型调整。并以用户能理解的方式表示发现的知识， 根据需要对知识发现过程中的菜些处理阶段进行优化，直至满足要求。 2 2w e b 数据挖掘 2 2 1w e b 数据挖掘的定义 w 曲数据挖掘定义为：针对包括w e b 页面内容、页面之间的结构、用户 访问信息、电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以发现 有用知识来帮助人们从中提取知识，改进站点设计，更好地开展电子商务“。 简单地说，w e b 数据挖掘是指从w e b 服务器上的数据文件中提取人们感兴趣 的知识的过程。这里采用一食公式的定义：w 曲数据挖掘是指从大量的与 w 曲相关的文档集合c 中发现隐含的模式p 。如果将c 看作输入，p 看作输 出，那么w e b 数据挖掘的过程就是从输入到输出的一个映射：c - - p ，。w e b 数据挖掘可以在很多领域发挥作用，如w e b 日志挖掘、w e b 文档分类、对搜 索引擎的结构进行挖掘、确定权威w e b 页面和智能查询等领域。 w e b 数据挖掘是，夭数据挖掘发展而来的，是数据挖掘技术在i n t e m e t 上 9 哈尔滨工程大学硕士学位论文 z i|i ii i i i i i i i 宣昌宣盲i 暑薯宣i 瞄宣置_ 的应用。可以说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 2 2w e b 数据挖掘的分类 根据对w e b 数据的感兴趣程度不同，r k o s l a 和h b l o c k e e l 将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 b s t r u c t u r em i n i n g ) 、w e b 日志挖掘( w e bl o gm i n i n g ) 。图2 1 表示的是w e b 数据挖掘的分类。 图2 1w e b 数据挖掘的分类 1 w e b 内容挖掘 w 曲内容挖掘是指对w 如页面内容进行挖掘，从w 曲文档的内容信息 中抽取知识。w e b 的内容是丰富的、巨大的，而且构成成分是半结构的或非 1 0 哈尔滨工程大学硕士学位论文 结构的。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 页面内容直接进行挖掘，对页面中的文本进行文本挖掘，对页面中 多媒体信息进行多媒体信息挖掘“3 。 2 w e b 结构挖掘 w e b 结构挖掘的对象是w e b 本身的超链接，即对w e b 文档的结构进行 挖掘，从而获得所需信息。超文本间的超链接反映了文档间的某种联系，如 包含、从属、继承和引用等关系，利用超文本之间的链接，可以对页面进行 排序、分类和聚类，发现重要权威页面。这方面工作的典型代表是p a g er a n k 算法和c l e v e r 算法，。 对于搜索引擎的搜索结果来说，p a g er a n k 是一个很有用的方法，它可以 对结果进行有效的评价，查询的结果可以按照p a g er a n k 从大n d , 依次排列 输出，c l e v e r 方法本质上和p a g er a n k 是一致的。 3 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 日志记录的数据量是非常巨大的，完整的，这些数据包括 服务器的目志记录、注册信息、浏览器端日志、代理服务器日志、用户查询、 c o o k i e 中的信息、用户会话信息和交易信息等。 w e b 日志挖掘的研究方法可以分为两类：基于w e b 事务的方法和基于数 据立方体的方法。前者是将用户会话划分成事务序列，然后采用数据挖掘的 方法进行模式挖掘。后者则将w e b 日志数据直接组织成数据立方体用于数据 挖掘和o l a p i ”。 1 1 哈尔滨工程大学硕士学位论文 ；i td i a ltmi i a l | a ；i i 一 根据对数据源的不同处理方法，w e b 日志挖掘可以分为两类：一类是将 w e b 日志记录的数据经预处理转换成结构化的数据，再传递进传统的关系表 里，使用数据挖掘算法对关系表中的数据进行常规挖掘；另一类是将w e b 日 志记录的数据直接预处理再进行挖掘“。 2 2 3w e b 数据挖掘的过程 相对于传统数据库中的数据，w e b 上的数据是丰富的、巨大的、动态的、 半结构化或非结构化的。因此，很难用传统的数据挖掘技术对w e b 数据进行 挖掘，而必须要经过数据的预处理这一步骤。典型的w e b 数据挖掘主要包括 以下几个步骤“： ( 1 ) 查找资源：从目标龇巷文档中获得数据。 ( 2 ) 信息选择和预处理：在第一步骤中获得的数据进行必要的剔除和相 应的整理。 ( 3 ) 模式发现：在同一个站点内部或在多个站点之间自动进行模式发现。 f4 ) 模式分析：解释、验证模式发现步骤产生的模式。可以是与分析人 员进行沟通来完成，也可以是机器自动完成。 2 2 4w e b 数据挖掘的数据预处理 w e b 数据挖掘首先对w e b 数据进行预处理，提高数据的质量。w e b 数据 预处理主要包括五个阶段：数据清理、用户识别、会话识别、路径补充和事 务识别。 1 数据清理 数据清理是指根据需求，处理w e b 日志文件，删除w e b 服务器日志中 有噪声的、无关的和不一致的数据。数据清理就是对w e b 日志中些不能反 映用户行为的记录进行过滤，w e b 日志挖掘的目的是获得用户的行为模式， 那些用户没有直接请求的文件对w e b 日志挖掘的结果没有影响。只有当服务 器日志的数据经过数据清理后才能够准确的反映用户访问w e b 站点的情况 时，经过挖掘得到的模式规则才是有用的和准确的。 1 2 哈尔滨工程大学硕士学位论文 i i i i _1 1 1 i ii i ii i 当用户向服务器请求w 曲页面时，w e b 服务器对用户的请求进行响应， 将该页面对应的h t m l 文件传送给用户，同时将这次请求记录在服务器日志 中。h t t p 协议是一个无连接协议，用户每下载一个文件，w e b 服务器中的 日志相应增加一条记录。通常，用户的一个w e b 页面请求一般会产生几条日 志记录，这是因为w e b 页面中有时包含了其它文件，如图片、声音、视频以 及广告等文件，然而用户对这些附属文件一般不会显式地请求，它们通常是 浏览器根据h t m l 的超文本引用标记自动下载的，因此w e b 服务器日志文 件中就会包含许多与访问页面的内容没有联系的无关项或冗余项。通常，用 户的真正意图是用户请求的h t m l 页面，应该用于用户访问的统计。由于 w e b 日志挖掘的目的是获得用户的访问行为规律，并不关心那些用户没有显 式请求的文件，所以通过检查u r l 的后缀删除认为不相关的数据。例如：将 日志中文件的后缀名为c s s 、s w f , g i f , j p e g 、m a p 和j p g 的项删除，另外，后 缀名为c g i 和i s 的脚本文件也应该被删除。当然也有例外的，例如一个主要 包含图片的在线相册网站不应该把所有后缀为j p g 、b m p 和g i f 的日志文件全 部清除。因为图片这时候正是用户所明确请求的内容，需要被保留以用于分 析用户访问行为规律。 2 用户识别 数据清理完成以后，下一个步骤就要进行用户识别，目的是明确的区分 开每一个用户。用户识别是将用户和请求的页面相关联的过程，由于本地缓 存、防火墙和代理服务器的存在，使得识别用户这一步变得很复杂。以下四 点是遇到的典型问题： ( 1 ) 同一个用户在不同的机器上访问w e b 服务器。 ( 2 ) 同一个用户在同一台机器上使用不同的浏览器访问w | e b 服务器。 ( 3 ) 不同的用户在同一时间通过同一个代理服务器访问w 曲服务器。 ( 4 ) 不同的用户使用同一台机器访问w e b 服务器。 c o o k i e s 是站点根据用户浏览器写入其本地的一个唯一标识，可以使用 c o o k i e s 来辨识用户，但是需要如下两个条件：c o o k i e s 没有被用户删除和用 户允许浏览器使用c o o k i e s 。还可以通过用户注册时的注册信息来标记用户， 但用户往往担心注册的信息泄漏给网站或其它用户，把注册看成是一种对隐 私的侵犯，因此用户往往不愿填写真实注册信息，而且不愿意登录需要注册 1 3 哈尔滨工程大学硕士学位论文 ；置暑鲁置置；昌置暑；昌宣薯昌罱i薯盲宣暑宣宣昌；宣葺暑宣ii暑宣宣皇宣宣；暑宣罩毒眚宣葺i1i 1 皇皇_ 的w e b 站点。这些依赖用户的合作，辨识用户的方法虽然简单，但因为涉及 隐私问题，所以实现起来不太乐观。这时，只能通过一些启发式规则来识别 用户，用户识别的启发式规则核心思想：不同的i p 代表不同的用户；若i p 地址相同时就可以根据用户端操作系统或浏览器软件是否相同来辨别是否是 新用户；还要借助站点拓扑来辨别，若发现用户正请求的页面不能从已经访 问的任何页面到达，则认定用户为新用户。 当然，这些规则并不能非常准确的识别出每一个用户。例如，两个使用 一样机器型号，一样操作系统，一样浏览器，一样i p 地址访问同一组网页的 用户会被认为是一个用户；一个用户使用多种浏览器或者直接在地址栏中输 入u r l 信息，此时会被认为是多个用户。 3 会话识别 会话识别是将一个用户在一段时间内所有的请求页面分解得到用户会 话。用户会话( u s e rs e s s i o n ) u 是指用户对服务器的一次有效访问，可表示 为一个二元组 ，其中u s e r i d 是用户标识，s p 是用户在一段时间内 请求的w e b 页面和时间对( u r l ，t i m e ) 的集合，通过其连续请求的页面可以 获得他在网站中的浏览兴趣和访问行为。用户会话u 可以表示为式( 2 i ) 所 示的元组。 u - - ( 2 一1 ) 通常采用超时方法识别用户会话，即当对页面之间的请求时间间隔超出 所给定值时，就可以认为用户已经开始