（计算机科学与技术专业论文）web日志挖掘相关算法研究.pdf

国防科学技术大学研究生院学位论文 摘要 在互联网的强力推进下，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 日志中关联规则的挖掘算法和最大频繁访问 模式的挖掘算法。本文主要取得了以下研究成果： 1 、从w e b 日志的收集和预处理入手，深入分析和研究了w e b 日志的特点和 收集过程，深入阐述了其预处理过程，并针对传统的处理过程中存在的问题，提 出了相应的改进措施。 2 、在深入分析了用户访问w e b 行为特点的基础上，结合网站的拓扑结构图， 提出了概率关联图的概念，并将用户访问抽象为有向图，利用概率关联图的性质， 提出了一种关联规则挖掘算法，理论证明该算法的效率比现在的关联规则挖掘算 法高，其时间复杂度为o ( n 3 ) 。 3 、提出了唯一标号树的概念，并在树的深度优先遍历编码表示的基础上，提 出了一种基于模式增长的最大频繁子树挖掘算法u - t r e e m i n e r ，实验结果表明该算 法比一般标号树的挖掘算法效率要高。 4 、进一步简化了用户访问行为表示，将其表示成唯一标号树；针对不同页面 的不同属性，提出了内容页面优先的支持度计算方法，在此基础上利用唯一标号 树的挖掘算法u - t r e e m i n e r ，挖掘w e b 日志中的最大频繁访问模式，实验结果表 明在最小支持度阈值较小的情况下算法u - t r e e m i n e r 比算法t r e e m i n e r 要快。 主题词：w e b 日志，概率关联图，唯一标号树，最大频繁访问模式 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht 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 e o m et h em a i np l a t f o r mf o r i n f o r m a t i o n p r o d u c i n g , p u b l i c a t i o n , h a n d l i n g a n dp r o c e s s i n g h o w e v e r , w e b i n f o r m a t i o ni s r a p i d l ye x p a n d i n g , t h u si tc a u s e sas e r i o u sp r o b l e m - ”i n f o r m a t i o n e x p l o s i o n ”，i e i n f o r m a t i o ni sa b u n d a n t , b u tk n o w l e d g ei sr e l a t i v e l yp o o r j u s ti n t h i s c a s e ，w e bm i n i n ga r i s e sa tt h eh i s t o r i cm o m e n t a n di nw e bm i n i n g ，w e bu s a g em i n i n g , w h i c hm i n e sw e bl o g so nw e bs e r v e r , h a v ea t t r a c t e di n t e n s i v er e s e a r c hi n t e r e s t si n r e c e n ty e a r s w eh a v ed o n es o m ew o r k si nt h ew e b u s a g em i n i n g f i r s t l y ，w eh a v ei n t r o d u c e d t h eb a s i cc o n c e p ta n dm e t h o do fd a t am i n i n ga n dw e bm i n i n g t h e nw ea n a l y s i st h e c h a r a c t e r i s t i co fw e bl o g sa n ds t u d yt h o r o u g h l yt h et e c h n o l o g yo fp r c p r o c s so fw e b l o g s a n d 砒l a s t , w er e s e a r c ht h ea l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l eb a s e do n p r o b a b i l i t ya s s o c i a t i o ng r a p ha n dt h ea l g o r i t h mo fm i n i n gm a x i m a lf r e q u e n ta c c e s s p a t t e r n sf r o mw e bl o g s w eh a v eo b t a i n e dt h ef o l l o w i n gr e s e a r c hr e s u l t s ： l 、w e h a v e t h o r o u g h l ya n a l y z e da n dc a r e f u l l y r e s e a r c h e d t h ec h a r a c t e r i s t i c o f w e b l o g sa n di t sc o l l e c t i o np r o c e s s w eh a v ee l a b o r a t e dp r o c e s s o f p r e p r o c e s s i n gw e bl o g s , i no r d e rt or e m e d yt h ee x i s t i n gp r o b l e mi nc o n v e n t i o n a lp r e p r o c e s s i n gm e t h o d , w eh a v e m a d es o m ei m p r o v e m e n t ， 2 、c o m b i n i n gw i t ht o p o l o g i c a ls b u e t u r eg r a p ho f w e bs i t e , p r o b a b i l i t ya s s o c i a t i o n g r a p hi sp r e s e n t e db a s e d o nt h o r o u g ha n a l y s i so f u s e ra c s sw e bb e h a v i o r t h ep r o c e s s o fu s e ra c c e s si sr e p r e s e n t e da sad i r e c t e dg r a p h t h e nb a s e do np r o b a b i l i t ya s s o c i a t i o n g r a p han o v e la l g o r i t h mo f m i n i n ga s s o c i a t i o nr u l ei sp r o p o s e d a tl a s t , w ep r o v e dt h a t o u ra l g o r i t h mo u t f o r m se x i t i n ga l g o r i t h m si nt h e o r y ，t h er i mt i m eo fo u ra l g o r i t h m i s o ( n 3 ) 3 、a f t e ra n a l y z i n ge x i t i n ga l g o r i t h m so fm i n i n gl a b e l e dn e c i nv i e wo ft h e c o n c l e t ep r o b l e m ，an o v e lu - t r e e m i n e ra l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n ts u b t r e e f r o md a t a b a s eo fu n i q u el a b e l e dt r e e st h r o u g hp a t t e r n - g r o w t hi sp r o p o s e db a s e do n d e p t h - f i r s tt r a v e r s a le n c o d i n gs t r i n go fu n i q u el a b e l e dt r e e t h ee x p e r i m e n t ss h o wt h a t o u ra l g o r i t h mu - t r e e m i n e ri sm o r ee f f i c i e n tt h a no t h e r a l g o r i t h m s 4 、w es i m p l yu u n i q u el a b e l e dt r e et or e p r e s e n tt h eu s e rs e s s i o n a n dt a k i n gi n t o a c c o u n tp r o p e r t yo fd i f f e r e n tp a g e s , an e wm e t h o do fc a l c u l a t i n gs u p p o r ti sp r e s e n t e d b a s e do l lt h en e wm e t h o d , t h ea l g o r i t h mu - t r e e m i n e ri su s e dt om i n em a x i m a lf r e q u e n t a e c 7 , e $ sp a t t e r n sf r o mw e bl o g s a n de x p e r i m e n t ss h o wt h a tu t r e e m i n e ro u t p e r f o r m s t r e e m i n e rw h e nt h es u p p o r ti sl i t t l el o w k e yw o r d s ：w e bl o g s ，p r o b a b u i t ya s s o c i a t i o ng r a p h ，u n i q u el a b e l e d t r e e m a x i m a if r e q u e n ta c c e s sp a t t e m s 第n 页 国防科学技术大学研究生院学位论文 表2 1w e b 挖掘分类及比较 表目录 表3 1w e b 服务器访问日志举例 表3 2w e b 服务器代理日志举例 表3 3w e b 服务器引用日志举例 表6 1 两种支持度计算方法挖掘结果比较5 9 第页 国防科学技术大学研究生院学位论文 图目录 图1 1 论文结构图 图2 1w e b 日志挖掘过程 图3 1 数据预处理的形式 图3 2w w w 数据通讯结构 图3 3w e b 客户端，月务器互动过程。 图3 a 使用f r a m e 标记的两个多窗口页面 图3 5 多窗口页面示意图 图3 6w e b 日志预处理过程 图4 1 求图的概率关联图算法过程 图4 2 2 网站的拓扑结构图 图4 3 用户会话的有向图表示 图4 4 图叠加算法 。1 9 。2 3 2 3 2 9 3 4 3 7 图4 5 基于概率关联图的有趣关联规则发现算法3 9 图5 1 树的b f e s 和d f e s 的表示 图5 2 唯一标号树及其d f e s 、结点范围链、嵌入子树4 5 图5 3u - t r e e m i n e r 算法 图5 4 唯一标号树数据库d 的两种表示方法 图5 5 形成新的编码和活跃结点示意图 图5 6 函数g e n e r a t e - t e s t ( s u b t r e e ) 图5 7 算法在不同大小数据集下的运行时间 图5 8 在数据集f 5 d i o m 2 0 0 t 1 m 下的运行时间图 图5 9 在数据集f i o d l 0 m 2 0 0 t i m 下的运行时间图。 图5 1 0 在数据集f s d i o m 2 0 0 t 2 m 下的运行时间图5 l 图6 1 用户访问w e b 网站示例 图6 2 用户会话的标号树表示 图6 3 唯一标号树表示的用户会话 图6 4 网站层次结构图 图6 5 在不同大小的数据集上运行性能 图6 6 算法运行时间比较 5 5 5 6 5 8 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：坠旦盎整垣担差簋溘叠壅 学位论文作者签名：建至邀日期：乒。6 年，j 月，尹日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 坠女旦主撞攫担差簋洼班塞 学位论文作者签名：垒乏耋邀 作者指导教师签名 脚 i 1 日期：函一6 年f j 月，驴日 日期：沙，6 年f 月f 弘日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 研究背景 数据挖掘( d a t a m i n i n g ) 是且前数据库和信息决策领域的前沿研究方向之一，目 的是从大量数据中提取隐含的、事先未知的和潜在有用的知识。它是多个研究领 域的交汇点，其中包括数据库技术、统计分析、机器学习和可视化技术等。它又 是一项面向应用的研究，在商业领域内有很多潜在应用。因此数据挖掘技术得到 了学术界和工业界的广泛关注。从1 9 8 9 年数据挖掘概念提出直到现在，数据挖掘 技术得到了快速发展，涉及的应用领域日益广泛。 在互联网的强力推进下，w e b 已成为信息制造、发布、处理和加工的主要平 台，w e b 上承载的信息正在迅速膨胀。当前w w w 正在深度和广度方面迅速地发展 着，i n t e m e t 也正在前所未有地改变我们的生活。据中国互联网信息中心【1 】第1 8 次中国互联网络发展状况统计报告指出，截至2 0 0 6 年7 月中国大约有网站7 8 8 4 0 0 个，5 4 5 0 万台上网电脑，上网人数为1 2 3 0 0 万人。不容置疑，信息已成为发展经 济技术的一种重要资源。如何方便快捷的获取信息，存储信息一度成为信息技术 的研究热点。然而，随着信息技术，特别是w e b 技术的迅速发展，我们正面临着 更严重的问题一“信息爆炸”，即信息极大丰富，而知识相对贫乏。同时，w e b 站点设计、w e b 服务设计、w e b 站点的导航设计、电子商务等工作正变得越来越 复杂和繁重。如何从存放在w e b 上的海量信息中获取有效信息并从中发现新的知 识以及如何更有效地对网站进行管理，成为w e b 数据挖掘的任务。 另一方面，从站点经营方来说，他们需要好的自动辅助设计工具，可以根据 用户的访问兴趣、访问频度、访问时间动态地调整页面结构，改进服务，开展有 针对性的电子商务以更好地满足访问者的需要【4 8 捌；而从访问者来说，他们希望 看到的是个性化的网页，希望得到更好的满足自身需求的服务，这种需求从某种 意义上说，访问者本身未必清楚【4 堋。因此，解决这两方面需求的一个有利工具 就是w e b 数据挖掘。 目前无论是国际还是国内，对w e b 挖掘的研究还处在刚起步的阶段，还没有 形成比较统一的体系和比较成熟的理论。尤其是在w e b 挖掘的实际应用方面所作 的工作较少。然而，随着知识经济的发展，w e b 数据挖掘作为一种获取知识的有 效手段，必定在经济技术的发展中扮演着重要的角色，需要对w e b 挖掘的方法和 w 曲挖掘的应用进行更深更广的研究。 1 2 研究现状 第l 页 国防科学技术大学研究生院学位论文 w e b 上的数据分为三类：内容数据( c o n t e n td a t a ) 、结构数据( s t r u c t u r ed a t a ) 和 使用数据( u s a g ed a t a ) 。因此按照w c b 挖掘所使用的数据类型，w e b 挖掘可以分为 三类：w e b 内容挖掘、w e b 结构挖掘和w c b 使用挖掘【2 j 4 】。我们主要讨论w e b 使用挖掘，由于其挖掘对象主要是w e b 日志记录，所以又称为w e b 日志挖掘。在 后文中，我们统一表述为w e b 日志挖掘。 w e b 日志挖掘的目的是在海量的w e b 日志数据中自动、快速地发现用户的访 问模式，如频繁访问路径，频繁访问页组和用户聚类等刚，为站点管理员提供各 种利于站点改进或可以带来经济效益的信息( 如聚类分析可以把具有相似待征的用 户或数据项归类来帮助进行市场决策) 【2 j 1 。 w e b 日志也可以结合其它数据库( 如电子商务或银行数据库) 一同进行挖掘，以 获得更详细的信息。此外研究者也很早就认识到内容和结构数据对使用挖掘技术 有很好的辅助作用。所以w e b 日志挖掘可以利用数据的多样性，以获得更有价 值的潜在信息。 目前国内外基于w e b 服务器日志数据的用户访问信息挖掘研究工作大致可分 为以下3 类州： l 、以分析w e b 站点性能为且标 主要从统计学的角度，对日志数据进行简单的统计，得到用户频繁访问页面、 单位时间访问数、访问数量随时间分布图等。绝大多数商用及免费的w e b 日志分 析工具都属于此类。 2 、以理解用户意图为目标 c h c n 等提出的路径游历模式( p a t ht r a v e r s a lp a t t e r n ) 的发现算法，以及j i a w e i h a r t 等使用的数据立方体方法，便是此类的典型代表。 3 、以改进w e b 站点设计为目标 通过挖掘用户的频繁访问路径和用户聚类，重构站点的页面之间的链接关系， 以更适应用户的访问习惯，同时为用户提供个性化的信息服务。c o o l e yr 、m o b a s h e r b 1 5 习等人首次给出w e b 挖掘的定义，并且给出一个关于w e b 访问信息挖掘的系统 w e b m i n e r 。文献p 3 】中提到的思路是，通过对w e b 站点的日志进行处理，将数 据组织成传统的数据挖掘方法能够处理的事务数据形式，然后利用传统的数据挖 掘方法( 如关联规则发现算法) 进行处理，所得出的挖掘结果也是传统的数据挖掘结 果。 在挖掘算法的技术线路方面，主要有两种思路： 一是c h e n 1 0 】等提出的w c b 事务的方法，将数据挖掘技术应用于w e b 日志挖 掘，以发现用户的浏览模式。c h e n 提出最大前向引用( m f g ) 序列的概念【1 q ”】，将 用户会话分割成一系列的事务，然后采用与关联规则相似的方法挖掘频繁的浏览 第2 页 国防科学技术大学研究生院学位论文 路径。 二是h a r t 0 1 等人提出的基于数据立方体的方法，即根据w e b 日志建立数据立 方体，然后在其上执行挖掘和o l a p 的各种操作，如提升、钻取等，用于发现用 户的访问模式。 相比于国外，国内对d m k d 的研究起步较晚，没有形成整体力量，且多偏重 于理论研究。1 9 9 3 年国家自然科学基金首次支持对数据挖掘项目的研究。随后许 多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究西安交通大 学、四川大学、南京大学以及上海交通大学等也先后在w 曲日志挖掘方面开着了 研究，并取得丰富的成果。 沈均毅例等人提出：首先以w e b 站点的u r l 为行，以u s e r i d 为列，建立u r l u s e r l d 关联矩阵，元素值为用户的访问次数，然后，对列向量进行相似性分析得 到相似客户群体，对行向量进行相似性分析获得相关w e b 页面，对相关页面再进 行进一步处理，则可以发现频繁访问路径。并提出了w e b 页面和用户群体的模糊 聚类算法。 陆丽娜彤】等人采用基于事务的方法，研究w e b 日志挖掘预处理及用户访问序 列模式挖掘方法，提出了一种基于扩展有向树模型进行用户浏览模式识别的w e b 日志挖掘方法。 胡和平等人唧】提出了应用多维立方体挖掘w e b 日志的多维关联规则的方法。 王熙法【57 】等人提出基于神经网络的w e b 用户行为聚类分析方法，即首先对 w e b 服务器的日志文件进行分析，再进行会话分析，从会话向量中找出频繁数据 集，进行规一化处理后，生成模式向量，采用s o f m 模型进行聚类，最后生成用 户聚类 周龙镶巧卅等人分析了w e b 用户浏览活动规律，提出了有关w w w 浏览路径的 一些基本概念，设计了基于用户访问模式的浏览路径优化算法。 纵观现有的w e b 日志挖掘算法，都是围绕着预处理后的w e b 日志展开的。然 而w e b 日志的预处理本身是一个复杂的过程，涉及到用户识别和用户会话识别等 关系挖掘算法效率和质量的重要过程。由于w e b 日志收集机制的限制，w e b 日志 的预处理很难快速和准确的识别出用户，从而导致重构出来的用户会话不能很好 的刻画用户访问行为，进而导致在此基础上的挖掘算法挖掘出来的模式并不能很 好的反映用户的习惯和兴趣爱好等，对网站优化、性能分析和个性化服务参考价 值不大。 另外w e b 日志数据量大，加上其动态更新的速度极快，现有的关联规则的挖 掘算法主要是采用基于a 研鲥算法和f p - c - r o w t h 算法的思想，没有考虑w e b 日志 本身的特点，时间复杂度高、效率太低寻找高效的关联规则挖掘算法将是本文 第3 页 国防科学技术大学研究生院学位论文 的一个重要内容。 w e b 日志挖掘是一种技术，和其他技术一样，w e b 日志挖掘也需要时间和精 力来研究、开发、和逐步成熟，最终被人们接受。目前已经有了很多通用的w e b 日志挖掘系统，如d b m i n e r 、w u m 等，但是还不能达到期望的智能系统那样。 在近来的w e b 挖掘研究和开发中，随着m i c r o s o f i 、o r a c l e 和i e l m 等国际大公 司的介入，w 曲挖掘受到越来越多的关注，一些问题得到解决，而另一些尚处于 研究阶段，这些尚处于研究阶段的问题必将刺激人们进行进一步的研究和探索。 1 3 主要研究成果 w c b 挖掘是数据挖掘技术在w e b 上的应用。因此本文首先系统地介绍了数据 挖掘和w e b 数据挖掘的相关概念和基本方法，然后研究了w e b 日志的预处理技术， 最后重点研究了w e b 日志的关联规则挖掘算法和最大频繁访问模式的挖掘算法。 在研究过程中，本文主要取得了以下几个方面的成果： l 、从w e b 日志的收集和预处理入手，深入分析和研究了w e b 日志的特点和 收集过程，深入阐述了其预处理过程，并针对传统的处理过程中存在的问题，提 出了相应的改进措施。 2 、在深入分析了用户访问w e b 行为特点的基础上，结合网站的拓扑结构图， 提出了概率关联图的概念，并将用户访问抽象为有向图，利用概率关联图的性质， 提出了一种关联规则挖掘算法，理论证明该算法的效率比现在的关联规则挖掘算 法高，其时间复杂度为d ( 矿) 。 3 、提出了唯一标号树的概念，并在树的深度优先遍历编码表示的基础上，提 出了一种基于模式增长的最大频繁子树挖掘算法u - t r e c m i n e r ，实验结果表明该算 法比一般标号树的挖掘算法效率要高。 4 、进一步简化了用户访问行为表示，将其表示成唯一标号树；针对不同页面 的不同属性，提出了内容页面优先的支持度计算方法，在此基础上利用唯一标号 树的挖掘算法u - t r e e m i n c r ，挖掘w e b 日志中的最大频繁访问模式，实验结果表 明在最小支持度阈值较小的情况下算法u - t r e e m i n e r 比算法t r e e m i n e r 要快。 1 4 论文结构 本文共分六章。第一章是绪论；第二章是数据挖掘和w e b 挖掘，介绍了数据 挖掘和w e b 挖掘研究的基本内容和方法；第三章是w e b 日志预处理技术研究，分 析了w e b 日志的特点，以及其收集过程，重点深入分析了w e b 日志的预处理过程， 并针对传统的处理流程，提出了相应的改进措施；第四章是基于概率关联图挖掘 第4 页 国防科学技术大学研究生院学位论文 日志中关联规则，首先分析了用户访问w e b 的行为特点，然后结合网站的拓扑结 构图，将用户的访问行为表示为有向图，利用概率关联图，挖掘关联规则：第五 章是唯一标号树的最大频繁子树挖掘算法u - t r e e m i n e r ，首先分析了现有标号树挖 掘算法的不足，然后针对唯一标号树的特点，提出了一种新的子树挖掘算法 u t r e e m i n e r ；第六章是基于u - t r e e m i n e r 算法挖掘w e b 日志中最大频繁访问模式， 将用户访问会话表示为唯一标号树，提出了内容页面优先的支持度计算方法，利 用唯一标号树的u t r e e m i n e r 挖掘算法，挖掘w e b 日志中最大频繁访问模式；最 后是结束语，在总结本文工作的基础上对未来工作进行展望。全文结构如图1 1 所 刁i ； 图1 1 论文结构图 第5 页 国防科学技术大学研究生院学位论文 第二章数据挖掘和w e b 数据挖掘 随着计算机应用技术的发展，人们积累的数据越来越多，这直接导致了数据 挖掘技术的产生。而互联网的快速发展，使得w e b 成为信息制造、发布、处理和 加工的重要平台，w e b 上的信息迅速增长。于是w e b 挖掘技术应运而生，它是将 数据挖掘技术应用于w e b 数据的处理。本章2 1 节首先介绍数据挖掘的基本概念 和相关的技术；2 2 节介绍w e b 数据挖掘的特点、分类和基本方法；2 3 节介绍 w e b 日志挖掘的过程，应用和现有的w e b 日志挖掘系统。 2 1 1 数据挖掘的产生 2 1 数据挖掘 随着数据库技术的迅速发展和数据库管理系统的广泛应用，人们积累的数据 越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高 层次的分析，以便更好地利用这些数据。且前的数据库系统可以高效地实现数据 的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现 有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏知识的手段，导致了 “信息丰富但知识贫乏”的现象。 计算机技术的人工智能领域自1 9 5 6 年诞生后取得了重大进展。1 9 8 9 年在美国 底特律市召开的第1 l 届国际人工智能联合会议的专题讨论会上首次出现数据库中 知识发现( 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 s ) 这一专业名词，简称k d d 。它泛指所 有从源数据中发掘模式或联系的方法。目前大家公认的k d d 严格定义是在1 9 9 6 年知识发现国际会议上由f a y y a d 、p i a t e s t s k y 、s h a p i r o 和s m y t l l 提出的：数据库 中的知识发现是从数据集中提取出有效的、新颖的、有潜在作用的、可信的、并 能最终可被理解的模式的非平凡过程【6 】。 k d d 是- - i 1 涉及多领域的交叉学科，不同领域的专家对其有不同的定义。在 人工智能和数据库领域，另外一个广泛使用的概念是“数据挖掘”。数据挖掘是 从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则。 从k d d 和数据挖掘的定义中我们可以看出：二者之间具有紧密的联系，其中 的概念都是相互对应或隐含的。对于二者之间的关系，学术界也存在两种观点： 一种观点认为k d d 和数据挖掘的含义相同，只是名称不同；而另一种观点认为， 数据挖掘是k d d 中专门发现知识的核心环节，而k d d 是一个交互式、循环反复 的整体过程，除了包括数据挖掘外还包括数据准备和发现结构解释评估等诸多环 节。本文倾向于第二种观点，作为一个科学研究领域，数据挖掘和k d d 的确有一 第6 页 国防科学技术大学研究生院学位论文 定的重合度。但是数据挖掘也是一个多学科交叉的研究领域，它包括数据库技术、 人工智能、机器学习、神经网络、统计学、模式识别、知识工程、信息检索、高 性能计算和数据可视化等研究领域。 数据挖掘技术出现于2 0 世纪八十年代，在9 0 年代有了突飞猛进的发展。目 前，它所挖掘出来的知识可应用于金融、国防军事、医疗保健、市场营销、科学 研究等各个领域。 2 1 2 数据挖掘分类 根据挖掘数据类型的不同，数据挖掘包括以下几个方面研究：空间数据挖掘、 多媒体数据挖掘、时序数据和序列数据的挖掘、文本数据挖掘和w e b 数据挖掘m 。 2 1 2 1 空间数据库挖掘 空间数据库存储了大量与空间相关的的数据，例如地图，预处理之后的遥感 图像，气象数据或医学图象数据，以及v l s i 芯片设计数据等。空间数据库有许多 与关系数据库所不同的显著特征。空间数据库包含了拓扑和距离信息，通常按照 复杂的、多维空间索引结构组织数据，采用空间数据的访问方法，经常需要空间 推理、地理计算和空间知识技术。 空间数据挖掘是指对空间数据库中非显示存在的知识、空间关系或者其他有 意义的模式等的提取。空间数据库挖掘需要综合数据挖掘与空间数据库技术。它 可用于空问数据的理解，空间关系和空间与非空间数据间关系的发现，空间知识 库的构造，空间数据库的重组和空间查询的优化。空间数据挖掘在地理信息系统、 地理市场( g e m a r k e t i n g ) 、遥感、图像数据库探测、医学图象处理、导航、交通控制、 环境研究以及许多使用空间数据的领域中有广泛的应用。由于空间数据挖掘的大 数据量和空间数据类型和空间访问方法的复杂性，空间数据挖掘面临的主要挑战 研究高效的空间数据挖掘技术。 2 1 2 2 多媒体数据挖掘 多媒体数据的挖掘现在主要研究方向为图像数据挖掘。多媒体数据库是指存 储和管理大量多媒体对象的数据库，如音频数据、图像数据、视频数据等。由于 音频视频设备、c d - r o m 和因特网的流行和普及，多媒体数据库系统变得日益常 见。 2 1 2 3 时序数据与序列数据的挖掘 时序数据与序列数据的挖掘是以时序数据库和序列数据库为挖掘对象。它的 研究内容包括趋势分析、相似性搜索、与时间有关数据的序列挖掘和周期模式挖 掘。时序数据库是指有随时间变化的序列值或事件组成的数据库值通常是等时 第7 页 国防科学技术大学研究生院学位论文 间间隔的数据。时序数据库应用广泛，如股票市场的每日波动、动态产品加工过 程、科学实验和医疗等。时序数据库也是一种序列数据库。然而序列数据库是指 由序列组成的数据库，它可以有时间标记，也可以没有。例如，w e b 页面遍历序 列是一种序列数据，但不可能是时序数据。 2 124 文本数据挖掘 文本数据库( 或文档数据库) 由来自各种数据源( 如新闻文章、研究论文、书籍、 数字图书馆、电子邮件消息和w e b 页面) 的大量文档组成。由于电子形式的信息量 的飞速增长，如电子出版物，电子邮件，c d - r o m 和万维网( 它也可以被视为一个 巨大的、互联的动态文本数据库) 等，文本数据库迅速的膨胀。传统的信息检索技 术已经不能适应日益增长的大量文本数据处理的需要。大量数据文档中只有很少 一部分与某一个体或用户相关。如果用户不清楚文档的内容，则很难形成有效的 查询，从数据中分析和提取有用信息。因此用户需要有关的工具完成不同文档的 比较，以及文档重要性和相关性排列，或找出多文档的模式或趋势。于是文本挖 掘就成为数据挖掘中一个日益流行而重要的研究课题。 2 1 2 5w e b 挖掘 万维网是一个巨大的，分布广泛的和全球性的信息服务中心，它涉及大量新 闻、广告、消费信息、教育、政府、电子商务和许多其它信息服务。w e b 上还包 含了丰富的和动态的超链接信息，以及w e b 页面的访问和使用信息，“信息爆炸 和知识贫乏”在w e b 中表现得更为突出。同时海量的数据也为数据挖掘提供了丰 富的资源。 2 1 3 数据挖掘的功能 数据挖掘功能是用于指定数据挖掘任务重要的模式类型。按照功能来分，数 据挖掘任务可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一 般特性。预测性挖掘任务在当前数据上进行某些推断，以进行预测。一般来说数 据挖掘可以实现以下一些功能： l ，概勃类描述：特征化和区分 数据可以与类或概念相关联。用汇总的、简洁的、精确的语言描述每个类和 概念是有用的。这样类和概念的描述成为类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 。 这种描述可以通过以下几种方式得到：1 ) 数据特征化，一般地汇总所研究类( 通常 称为目标类( t a r g e tc l a s s ) ) 的数据；2 ) 数据区分，将目标类与一个或多个比较类( 通常 称为对比类( c o n t r a s t i n g c l a s s ) ) 进行比较；3 ) 数据特征化与比较。 2 、关联分析 第8 页 国防科学技术大学研究生院学位论文 关联分析( a s s o c i a t i o na n a l y s i s ) 用于发现关联规则，这些关联规则展示属性值 频繁的在给定数据集中一起出现的条件。关联分析广泛用于购物篮或事务数据分 析。 形式地，关联规则是形如并j y ，即“彳l a z a a 。等b i a b z a & ” 的规则，其中，a i ( i 1 ，2 ，m ) ) ，b j 0 1 ，n ，) 是属性值对。关联规则的x j y 的解释为“满足x 中条件的数据库元组也满足y 条件” 我们用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来作为关联规则兴趣度的客观度 量。关联规则工等y 的支持度表示满足规则的样本的百分比。用概率p ( x u n 表 示，其中，x w y 表示同时包含x 和y 的事务，即项集x 和y 的并。关联规则x jj r 的置信度用条件概率p i j 0 及包含x 的事务也包含y 的概率来表示。 3 、分类和预测 分类是找出描述并区分数据类或概念的模型( 或函数) ，以便能够使用模型预测 类标记未知的对象。导出模型是基于训练数据集的分析的。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望 预测某些空缺值或不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预测d i c t i o n ) 。尽管预测可以涉及数据值预测和类标记预测，通常预 测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 4 ，聚类分析 与分类和预测不同，聚类( c l u s t e r i n g ) 分析数据对象，而不考虑已知的类标记 一般情况下，训练数据中不提供类标记，因此不知道从何开始。聚类，可以用于 产生这种标记。对象根据最大化类内的相似性，最小化类问的相似性的原则进行 聚类或分组。即对象的簇( 聚类) 这样形成，使得在一个簇中的对象具有很高的相似 性，而与其它簇中的对象很不相似。所形成的每个簇可以看作一个对象类，由他 可以导出规则。聚类也可便于分类编制( t a x o n o m yf o r m a t i o n ) ，将观察到的内容组织 成类分层结构，把类似的事件组织到一起。 5 、孤立点分析 数据库中可能包含一些数据对象，他们与数据的一般行为或模型不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而丢 弃。然而在一些实际应用中( 如欺骗检测) ，罕见的事件可能比正常出现的事件更有 趣。孤立点分析称为孤立点挖掘( o u t l i e r m i n i n g ) 。 6 、演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋势，并 对其建模。尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类， 这类分析的不同特点包括时间按序列数据分析、序列或时间周期模式匹配和基于 第9 页 国防科学技术大学研究生院学位论文 类似性的数据分析。 2 1 4 数据挖掘常用技术 目前应用在数据挖掘上的技术有很多，比较流行的有人工神经网络、决策树、 遗传算法、信号分析方法等。 1 、人工神经网络 仿照生理神经网络结构的非线形预测模型，通过学习进行模式识别。人工神 经网络模拟人类部分形象思维的能力。是模拟人工智能的一条途径。特别是可以 利用人工神经网络解决人工智能研究中所遇到的一些难题。人工神经网络理论的 应用已经渗透到多个领域，在计算机视觉、模式识别、智能控制、非线性优化、 自适应滤波信息处理、机器人等方面都取得了可喜的进展。尽管神经网络的模型 很多，但在数据挖掘中最为广泛使用的是有导师学习的反向传播网络a c k p r o p a g a t i o n ) ，它通过重复在网络中前后传递样本记录的方式进行学习。 2 、决策树 是代表着决策集的树形结构。方法是利用信息论中的信息增益寻找数据库中 具有最大信息量的字段，建立决策树的一个结点，再根据字段的不同取值建立树 的分枝：在每个分枝子集中重复建树的下层结点和分枝的过程，即建立决策树。最 有影响和最早的决策树方法是q u i u l a n 研制的i d 3 方法，数据库越大，其处理效果 越好。在i d 3 方法的基础上，后入又发展了c 4 5 等决策树改进的方法。 3 、遗传算法 遗传算法是基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设 计方法的优化技术。生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然 变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化 思想而启发得出的一种全局优化算法。 4 、信号分析 利用信号分析的方法和原理，将数据看成是由多个通道采样组成的信号，对 数据进行信号分析。通常信号分析的方法有小波分析方法、傅立叶分析方法、加 窗的傅立叶分析方法等。这类方法的特点是将输入的数据经过变换并进行频率域 上的分析。由于在频率域上的信号通常表现为低频和高频信号的叠加，因此可以 对不同的频率信号进行处理，以达到特定的目的。 2 2w e b 数据挖掘 2 2 1w e b 挖掘的定义和挑战 第1 0 页 国防科学技术大学研究生院学位论文 w e b 挖掘是从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相 类似。文献 s l 将w c b 挖掘定义为：针对包括w e b 页面内容、页面之间的结构、用 户访问信息、电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以发现有 用的知识来帮助人们从中提取知识，改进站点设计，更好地开展电子商务这里 采用一个更一般的定义：w e b 挖掘是指从大量的与w e b 相关的文档集合c 中发现 隐含的模式p 。如果将c 看作输入，p 看作输出，那么w e b 挖掘的过程就是从输 入到输出的一个映射：c 斗p 。 传统的数据挖掘技术处理的数据对象主要是结构化数据，很少处理w e b 上的 异质的、非结构化的信息，因此，对w e b 上的数据进行挖掘具有极大的挑战性【7 ，9 l 1 对有效的数据仓库和数据挖掘而言，w e b 似乎过于庞大。w e b 的数据量 目前已百兆兆字节计算，而且仍在迅速的增长。 2 w e b 页面上的复杂性远比任何传统的文本文档要复杂的多。w e b 页面缺 乏统一的结构，它包含的远比任何一组书籍和其他文本文档要多得多的风格和内 容。 3 w e b 是一个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其 信息还在不断地发生更新。 4 w e b 页面面对的用户群体是多样性的。 5 w e b 上的信息只有一小部分对某一用户是相关的或者是有用的。 w e b 上的数据主要包括【2 习： 1 、w e b 页面；包含文本和多媒体信息( 包括图像、语音、图片) ，现有