（计算机软件与理论专业论文）数据挖掘及其在web日志挖掘中的应用研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 随着网络的快速发展，人们尽情地享受到了网络带来的便利，网络已经成为人们日常 生活中必不可少的一部分。但是，由于网络上资料上过多，已经远远超过人们的处理能力。 不同的用户其使用兴趣和目的各不相同，人们都希望能够尽快地访问到出对自己有价值的 网页。网站管理者为了增加网站的吸引力，希望能够了解客户的访问行为，来优化网站结 构，提高响应速度，根据用户浏览行为，进行个性化页面推荐，从而更好地为客户提供优 质的服务。数据挖掘的应用非常广泛，随着互联网与w w w 的快速发展与使用，人们将数 据挖掘技术应用到了w e b 环境中，w e b 挖掘己成为一个热门的研究领域。由于随着网络的 发展，w e b 日志的数据量急速地增加，这些隐藏在w e b 日志文件中的信息，对于用户和网 站管理者都能带来极大的好处。w e b 挖掘主要区分为三类：内容挖掘、结构挖掘、以及使 用挖掘。其中，使用挖掘也叫日志挖掘，是利用使用者在浏览网页时所留下的网页存取记 录，来进行使用者行为特征模式的分析。以前在w e b 日志挖掘的研究，从基于a p r i o r i 有 候选集产生的使用模式挖掘算法和不产生候选集的前缀树类算法，都是希望以更有效率的 方式来挖掘用户访问模式。 本文研究了如何从w e b 日志中挖掘用户访问模式以及用户访问模式在个性化推荐中的 应用。首先，本文介绍了数据挖掘的相关概念和技术，以及w e b 挖掘的有关内容重点介绍 了日志数据预处理技术，说明了怎样将w e b 日志中的数据转换成用户访问序列。然后分析 了挖掘用户访问模式常用的算法，以及它们的缺点，在此基础上，提出了改进的用户访问 模式挖掘算法，利用树型结构来压缩用户访问序列和用户访问模式所需的全部信息，对该 树不断进行调整，最后对该树进行遍历，即可挖掘出所有的用户访问模式，无须生成候选 集。最后设计了一个由用户访问模式来进行页面个性化推荐的高效算法，将序列关联规则 的置信度和页面的访问可能性相结合作为规则的兴趣度，将规则按兴趣度进行排序后，存 放在树中，然后根据当前用户访问序列和访问模式的匹配情况，进行页面推荐。 关键词：数据挖掘，w e b 日志，用户访问模式，个性化推荐 南京邮电人学硕一l 研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn e t w o r k ，p e o p l eh a v ee n j o y e dc o n v e n i e n c eb r o u g h tb y n e t w o r k ，n e t w o r kh a sb e c o m ea ne s s e n t i a lp a r to fp e o p l e sd a i l yl i f e b u tp e o p l ei so v e r w h e l m e d b yt h el a r g em o u n to fo n l i n ei n f o r m a t i o n d i f f e r e n tp e o p l eh a v ed i f f e r e n ti n t e r e s ta n dg o a l s ，t h e y a l lw o u l dl i k et og e tv a l u a b l ew e b p a g et ot h e mq u i c k l y t h es t a f fo fw e b s i t eh o p et ou n d e r s t a n d t h ea c c e s sb e h a v i o ro ft h eu s e r st oo p t i m i z et h ew e b s i t e ss t r u c t u r e ，i n c r e a s et h er e s p o n s es p e e d a n dr e c o m m e n dp a g e s i n d i v i d u a l l y t h ea p p l i c a t i o no fd a t am i n i n gi sw i d e s p r e a d w i t ht h er a p i d p r o g r e s so ft h ei n t e r n e tt e c h n o l o g ya n dt h eg r o w i n gp o p u l a r i t yo ft h ew 彤w e bm i n i n g b e c o m e sah o tr e s e a r c hi s s u e t h ei n f o r m a t i o ne m b e d d e di nw e bl o gf i l e sw i l lb e n e f i tb o t hu s e r s a n dt h ew e b s i t eg r e a t l y t h e r ea r et h r e em a j o rk i n d so fw e b m i n i n g ：w e bc o n t e n tm i n i n g , w e b s t r u c t u r em i n i n ga n dw e bu s a g em i n i n g w e bu s a g em i n i n ga l s oc a l l e dw e bl o gm i n i n gu s e s w e ba c c e s sl o g st oa n a l y z eu s e rb e h a v i o rt h ep r e v i o u sr e s e a r c h e so nw e bu s a g em i n i n gf o c u s o np e r f o r m a n c ei m p r o v e m e n t f r o mt h ea p r i o r i l i k ea l g o r i t h m sw h i c hg e n e r a t ec a n d i d a t es e tt o t h ep o p u l a rp r e f i x - t r e ea l g o r i t h m sw h i c hd on o tg e n e r a t ec a n d i d a t es e td e d i c a t e dt op r o p o s i n g m o r ee f f i c i e n ta p p r o a c h e st od i s c o v e ru s e rw e ba c c e s sp a t t e r n s t h i sp a p e rs t u d i e sh o wt om i n eu s e ra c c e s sp a t t e r n sf r o mw e bl o g sa n dt h e i ra p p l i c a t i o ni n p e r s o n a lw e br e c o m m e n d a t i o n a tf i r s t ，t h i sp a p e ri n t r o d u c e sc o n c e p t sa n dt e c h n o l o g i e sr e l a t e d t od a t am i n i n g ，w e bm i n i n g ，t h ep r e t r e a t m e n to fw e b l o g , s h o w e dh o w t ot r a n s f o r mt h el o gd a t a t ou s e ra c c e s ss e q u e n c e s ，t h e ns t u d yg e n e r a lm i n i n ga l g o r i t h m si nu s e ra c c e s sp a t t e r n sa n dt h e i r d r a w b a c k s ，p u tf o r w a r da ni m p r o v e da l g o r i t h mt om i n e u s e ra c c e s sp a t t e r n s ，w eu s et r e es t r u c t u r e t oc o m p r e s su s e ra c c e s ss e q u e n c e sa n da l li n f o r m a t i o nn e e d e dt om i n eu s e ra c c e s sp a t t e r n s ， a d j u s tt h et r e ec o n t i n u a l l y , a n df i n a l l yt r a v e r s et h et r e et om i n ea c c e s sp a t t e r n s a tl a s t ，w ed e v i s e a l le f f i c i e n ta l g o r i t h mw h i c ha d o p tu s e ra c c e s sp a t t e r n st or e c o m m e n dp a g e si n d i v i d u a l l y ，t h e a l g o r i t h mc o m b i n et h ec o n f i d e n c eo ft h er u l ea n dp r o b a b i l i t yo fa c c e s sa st h ei n t e r e s to ft h er u l e ， o r d e rt h er u l e si nt r e eb yt h ei n t e r e s t ，t h e nr e c o m m e n dp a g e sb a s e do nt h ec i r c u m s t a n c et h a t c u r r e n tu s e ra c c e s ss e q u e n c em a t c h e su s e ra c c e s sp a t t e r n s k e yw o r d s ：d a t am i n i n g ，w e bl o g s ，a c c e s sp a t t e r n s ，p e r s o n a lr e c o m m e n d a t i o n 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研触虢奎薹塾嗽蝴 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：搬导师签 南京i l l g t l l 火学硕上研究生学位论文第一章绪论 1 1 研究背景 第一章绪论 随着计算机和通信技术迅速发展，以及相应费用的降低，互联网已经逐步渗透到人们 工作、生活的方方面面，并对人们生活、企业发展和社会进步产生了巨大影响，而作为互 联网技术中应用最为广泛的w w w 技术的影响最为显著。w w w 技术已经从当初的简单提 供文本信息发展成为今天的各种商业应用，诸如电子商务、电子政务、网上教育等等的具 体应用都发展的极为普及。b s 结构程序因为方便易用，维护量小等特点，得到了广大用 户的喜爱，也在一定程度上促进了w w w 技术的发展。w e b 站点作为交易和分发消息的媒 介，数量正以惊人的速度在增长，稍微有点规模的公司、单位都纷纷建立了自己的网站。 据统计，目前我国w e b 站点已接近2 0 0 万个，页面数目已快达到1 0 0 亿，网民2 亿多。 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 同志挖掘中的一个重要研究问题，用户访问模式具 有非常重要的应用价值。可以利用它和其它技术相结合来指导网站建设、辅助站点维护人 员优化站点设计计和拓扑结构、为用户提供个性化的页面推荐。 南京i i i g l g 大学顾l 研究生学位论文第一章绪论 1 2 研究意义 大部分w e b 站点在建立时由设计人员根据自身经验与观点进行分类组合，而没有考虑 到用户的浏览行为，没有从使用者的角度对站点进行优化和改进。不合理的站点设计在为 用户带来不便的同时，也会使自己在激烈的竞争中落败。同时，随着w e b 技术的发展，各 类电子商务网站迅速发展，规模和数量都与日俱增，追踪用户浏览行为到每一次鼠标点击， 迎合广大用户的使用要求，尽可能地增加网站的受欢迎程度，是网站运营的一个关键问题。 因此在当今这个信息社会，w e b 站点管理人员如何能够更加了解大多数用户的共同兴趣， 开展有针对性的服务就成为一项十分重要而紧迫的研究课题。w e b 站点服务器每天产生大 量的日志，其中蕴含了关于用户在网上行为的丰富数据，分析这些数据能够发现有意义的 隐藏访问模式，这对于分析和改善站点的使用情况、资源配置以及开展有针对性的营销具 有重要的意义。随之产生的w e b 使用挖掘的目的就在于此，它是通过研究w e b 服务器的 日志文件，以发现用户访问站点的行为。w e b 日志挖掘中最主流的研究方向，就是访问模 式挖掘，我们可以根据观察使用者浏览序列，了解使用者在网站上的行为模式，对企业或 网站管理者而言，了解顾客的行为模式，不仅可以帮助系统提升效能，更可以对市场营销 决策面提供优良的建议。在此基础上结合使用多种技术如页面缓冲、个性化推荐等可以为 客户提供更优质的服务。 1 3 国内外研究现状 近几年，国外学者非常关注w e b 日志的挖掘研究，早在1 9 9 6 年就有学者m s c h e n ， h m a n n i l a ，t y a n 提出了将数据挖掘方法用于w e b 研究领域，开始了w e b 数据挖掘技术 的研究。在他们的文章中，一个用户的访问页面的无序和加权向量被用来安排用户到现有 的用户聚类中。然后系统动态地推荐基于同一用户聚类中其他用户的访问页面的链接。国 内互联网是从1 9 9 7 年开始迅速蓬勃的发展起来的。直到1 9 9 9 年，国内互联网用户达到一 定数量以后，国内学者才开始关注w e b 数据挖掘，相比之下起步较晚。w e b 数据挖掘在国 内已经引起人们的关注，但是，大多数网站经营管理者对从访问r 志中发掘有用信息的重 要性认识不充分，网络管理人员还停留在关注服务器性能阶段，没有达到关注网站服务质 量的层次。结合查到的文献来看，国内这方面的研究还刚刚起步。 目前国内外基于w e b 服务器同志数据的用户访问模式挖掘研究工作大致可分为以下3 类【l 】：1 以分析w e b 站点性能为目标2 理解用户意图为目标3 以改进w e b 站点设计为目标。 有关访问模式方面的研究非常多，都是希望能找出一个快速又准确的算法，帮助我们 2 南京邮电火学硕：仁研究生学位论文第一章绪论 在最短的时间内挖掘出有意义的用户访问模式，c h e n 2 j 等最先提出了从日志文件中挖掘用 户访问模式，同时提出2 个多次扫描算法f s ( f u l ls c a n ) 和s s ( s e l e c t i v es c a n ) 。s p i l i o p o u l o u t 习 等提出了一个访问模式挖掘器w u m ( w e bu t i l i z a t i o nm i n e r ) ，并提出了从w e b 日志中构造 聚集树的算法，然后w u m 使用m i n t 挖掘语言来挖掘访问模式， b o r g e s 1 2 】等提出了一 个获取用户访问行为模式的超文本模型。p e i 和j i a w 西h 甜4 j 等提出了w a p ( w e ba c c e s s p a t t e r n ) 树来存储用户频繁访问序列，并提出了一个有效的模式增长算法从w a p 树中挖掘 访问模式。邢东山和沈钧毅等【1 6 】使用用户访问矩阵，基于用户选择偏爱度等概念来挖掘用 户偏爱访问模式。这些算法大致分为三类： 1 a p r i o r i 类算法，这一类的算法是继承关联分析的算法一a p r i o r i ，于1 9 9 5 年r a g r a w a l 将之延伸到浏览序列挖掘上，a p r i o f i 算法最大的优点是概念简单，以重复产生、 测试候选集的程序，找出满足所设定的阀值的所有序列，但它的缺点是候选集生成的数量 难以控制、且必须多次扫描数据库、以及难以处理长度较长的序列等等，所以a p r i o d 算 法其实还有不少改进的空间，有许多研究论文都是在讨论a p r i o r i 算法的改进，最著名的 几个有g s p 、h a s h - b a s e da p r i o r i 、 s e l e c t i v es c a n、c o n s t r a i n t - b a s e d a p r i o r i 等。 2 前缀树类算法，因为a p r i o r i 算法在速度上，有一些先天上无法克服的困难，开始有 一些学者尝试着以其它的方法来处理浏览序列挖掘，他们希望以较简便、快速的数据结构， 来取代原始的交易数据库，这一类的方法大多是采用类似前缀树的数据结构，因为前缀树 可以将浏览路径高度压缩，节省下许多存取磁盘所浪费的时间，再配合一个适合该数据结 构的挖掘算法以及查询方法，就可以有效率地解决浏览序列挖掘的问题，这一类的算法最 著名的有w a p t r e e 【4 1 、p r e f i x s p a n 8 1 等。 3 交集类算法，上述两类算法都是基于( 标识号，项集) 水平格式的，这类算法先扫描 一次数据库，将数据转换成( 项集，标识号) 的垂直格式，然后将相同项集的记录求交， 快速生成计数，有效的减少了数据库的扫描。这一类的算法最著名的有s p a d e 等。 除了改良挖掘算法、提高执行效率之外，另外一方面的研究就是如何让挖掘出来的频 繁序列更有意义、更具可分析性，根据以往的经验，挖掘出来的浏览序列与规则动则上千 条，若是以人工的方式很难将它们的真正特性一一分析、讨论出来，如何让算法在进行数 据挖掘的同时，也帮助我们整理杂乱的浏览序列，这也是一个十分有趣的研究方向，比较 著名的研究如最大向前引用【2 】等。 南京邮电火学硕1 ：研究生学位论文第一章绪论 1 4 本文研究内容和组织方式 1 4 1 本文研究内容 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 研究了挖掘用户访问模式的常用算法，分析了其缺点，针对用户访问模式的特殊性， 提出了一种改进的用户访问模式挖掘算法，并验证了算法的有效性。 3 研究了用户访问模式在个性化推荐方面的应用。将置信度和访问可能性相结合，设 计了一种优化的实现方法。 1 4 2 本文组织 本文共分六章，内容组织如下： 第一章首先介绍了w e b 日志挖掘以及用户访问模式的背景和意义，国内外研究现状， 最后介绍了论文的主要工作和组织结构。 第二章首先简要介绍数据挖掘技术起源、定义和分类，然后介绍w e b 挖掘及其分类。 第三章介绍w e b 日志、挖掘过程和日志数据预处理过程，其过程主要包括数据清理、 用户识别、会话识别、路径补充和事务识别五个部分。 第四章首先引出用户访问模式的问题，研究了常用的用户访问模式挖掘算法，根据用 户访问模式的特殊性，提出了一种改进的用户访问模式挖掘算法，利用树型结构来压缩用 户访问序列和挖掘用户访问模式所需的全部信息，对该树不断进行调整，最后对该树进行 遍历，即可挖掘出所有的用户访问模式，无须生成候选集。并验证了算法的有效性。 第五章讨论了用户访问模式的应用。重点设计了根据用户访问模式进行个性化推荐的 高效算法。将访问模式转换成序列关联规则，将规则存放在树中，根据当前用户访问序列 和访问模式的匹配情况，进行页面推荐。 4 南京邮电大学顾- j 二研究生学位论文第一章绪论 第六章对论文的主要贡献和创新作了总结，并对未来工作进行了展望。 南京邮i b 火学硕 ：研究生学位论文 第二章数据挖掘和w e b 挖掘概述 第二章数据挖掘和w e b 挖掘概述 2 1 数据挖掘概述 2 1 1 数据挖掘的产生 随着信息系统的广泛使用，人类现在处在一个信息爆炸的时代，激增的数据背后隐藏 着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。 然而，目前使用的信息系统基本都是建立在数据库技术基础上的，可以高效地实现数据的 录入、查询、统计等功能，这些功能都属于事务性的，它们无法发现数据中存在的关系和 规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段， 导致了“数据爆炸但知识贫乏”的现象。面对这些挑战，数据挖掘技术应运而生，并显示 出强大的生命力。 2 1 2 数据挖掘定义和过程 数据挖掘是近年来随着人工智能和数据库技术发展的一门新兴技术。它可从大量的数 据中，提取出隐含、过去不为人所知且可信与有效的知识。也可以说是依照使用者所设定 的参数，在一堆未经处理的数据中找到使用者感兴趣的信息，经过某些特殊的处理后，作 为使用者决策判断的参考依据。以下是常被引用的定义： ( 一) 【f a y y a d 的定义则严格区分数据挖掘与数据库中的知识发现( k d d ) 。其定义数据 库中的知识发现为从大量数据中选取合适数据，进行数据处理、转换、数据挖掘至结果评 估之一系列过程。而数据挖掘为其中一步骤( 图2 1 k d d 的过程) 。 ( 二) b e r r y 则认为数据挖掘是为挖掘有意义的特征或规则，而必须从大量数据之中 以自动或是半自动的方式来探索与分析数据。 ( 三) 【k l e i s s n e r 认为数据挖掘是一种新的且不断循环的决策支持分析过程，它能够 从数据中，发现出隐藏有价值的知识，以提供给企业专业人员参考。 在本文中，我们遵照f a y y a d 定义，将知识发现与数据挖掘分开看待，以免概念上有 所混乱。而知识发现可分为三个主要步骤，分别为前置阶段、数据挖掘阶段、规则诠释阶 段，而依照此三个阶段又可以将知识发现的过程又分为以下四项： ( 一) 数据的取得与净化阶段： 6 南京邮电人学颀一t ：_ i o f 究生学位论文 第二章致据挖掘和w e b 挖掘概述 在进行数据挖掘前，使用者必须确认需对何种领域的数据进行数据挖掘，例如零售业 在数据挖掘之前，必须确认挖掘的是客户数据或是交易数据；医院在对其内部数据库进行 挖掘时，也必需确认所要挖掘的数据是病人的病历数据，或是各种疾病之间的相关性数据 等。确认数据挖掘时所要挖掘的数据来源后，才能有效的将所需要的信息挖掘出来。在取 得数据的来源后，亦必须确认数据本身的数据类型以及数据是否为有效的数据。例如f 1 期 类型的数据域中存放的是同期格式，年龄类型的字段中存放的是数字，且数字的范围是在 年龄中是有效合理的范围。此过程即为数据的净化阶段。一般来说，以上的两个阶段是数 据挖掘的预处理工作，将数据取得与净化之后，就可以交给计算机系统进行所需的挖掘动 作，但此两个阶段所需要花费的人力与时间却是整个数据挖掘过程中最多的部分。 ( 二) 数据仓库阶段： 将数据取得与净化后，必须选择一个良好的数据库系统，作为数据存放的位置。在此 必须要考虑的是企业成本，数据库的大小及性能，以及数据库相关应用工具的种类与实用 性。对一般大型企业来说，可以选择大型的数据库工具搭配中型的数据挖掘的应用程序， 建构一个完整的数据挖掘的环境。而一般中小企业的使用者也可以利用各种数据库系统作 为数据仓储的工具，自行开发数据挖掘的应用程序，以达到数据挖掘的目的。 ( 三) 数据挖掘阶段： 在此一阶段中，首先确定数据仓储中哪些字段的数据是必要的。先将这些主要的字段 提出，再配合利用各种数据挖掘的算法，将使用者想要挖掘的数据从数据仓库中取出并执 行算法后，并将相关的信息从数据库中掘取出来，成为有用的知识。此阶段为数据挖掘阶 段，也是各种算法在改进性能时所着重的阶段。 ( 四) 规则诠释阶段： 以上的几个阶段中，由计算机程序中提取出来的规则或项目组合，或许仅是几个项目 的关联或是一些代码，对于非相关领域的人看来或许只是几组没有意义的代码或名词。数 据挖掘至此必须经过此一领域相关的学者加以诠释，并确认信息的可用性，将新奇有用且 让使用者感兴趣的信息取出，用一般大众都能了解的名词解释出来。此一阶段就是规则诠 释的阶段，而经过了一般化的信息或是规则，就是一般所说的知识或是规则。 从数据库系统中挖掘出有用的知识或是规则的整体过程，就是知识发现范畴了，整个 知识发现的过程示意图2 1 如下所示： 南京邮电人学硕：t 研究生学位论文第二章数据挖掘和w e b 挖掘概述 i i ： ： ： 。i j ； | 0 斋瑚了；选择喜转乡圃1 一l 2 1 3 数据挖掘技术 图2 1k d d 的过程 数据挖掘技术常见的主要有以下几类： 1 关联规则： 关联规则是数据挖掘研究的主要模式之一，侧重于确定数据中不同领域之间的关系， 找出满足给定条件下的多个域间的依赖关系。由数据库交易中找出项目之间的关联性，常 使用的参数为支持度和置信度，来衡量一条关联规则的发生频率和强度。例如某大卖场发 现购买面包的顾客同时会购买牛奶，则该大卖场在营销规划可将牛奶与面包放置同一架 上，以增加捆绑销售目的。在w e b 日志挖掘中，可以挖掘出被用户经常二起浏览的网页集， 网站管理者可以据此改变网站的结构，对网页集中的页面安排可以互相访问的超链接。而 关联规则依层次来区分，可分为单层次关联规则与多层次关联规则；若把交易时间顺序作 为关联规则的考虑因素，则为称为序列关联规则，在w e b 同志挖掘中，可以挖掘出用户浏 览序列关联规则模式最常见的算法有3 类：( 1 ) 需要产生候选项集，多次扫描数据库进行 候选项集计数的算法，这类算法称为a p r i o r i 类算法。( 2 ) 不需要产生候选项集，不需 要频繁扫描数据库的算法，这类算法称为模式增长类算法。( 3 ) 交集类算法，这类算法 先扫描一次数据库，将数据转换成( 项集，标识号) 的垂直格式，然后将相同项集的记录 求交，快速生成计数，有效的减少了数据库的扫描。 i-_i；， 一一一 一 一一 一 i。 一 一一 一 一 南京邮l b 火学硕j j 研究生学位论文第二章数据挖掘和w e b 挖掘概述 2 分类和预测 分类和预测是通过分析训练集中的数据，为每个类别做出，准确的描述或建立分析模 型或挖掘出分类规则，以便以后用这个分类规则对其它数据库中的记录进行分类的方法。 例如，从以往信用卡核卡历史审核数据中找出审核与否的特征，建立分类模式，此分类模 式便可依据新的客户数据( 年龄、职业、收入、教育程度、婚姻状况) 推论是否批准此新 客户的开卡申请。w e b 同志挖掘可以结合用户的登陆信息、会员信息、网上购物历史信息 等对用户进行分类，对不同的用户提供不同的推荐产品。最常见的技术下列几种： ( 1 ) 决策树 决策树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每 个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点， 由判定树可以很容易得n i f t h e n 形式的分类规则，根据选择属性进行分裂的标准不同可 以分为i d 3 、c 4 5 、c h a i d 等多种算法 ( 2 ) 贝叶斯分类 贝叶斯分类是统计学的分类方法，基于贝叶斯公式即后验概率公式。朴素贝叶斯分 类的分类过程是首先令每个数据样本用一个n 维特征向量x = x 1x 2 x n ) 表示。其中x k 是属性a k 的值。所有的样本分为m 类：c 1 、c 2 c m 。对于一个类别的标记未知的 数据记录而言，若p ( c iix ) p ( c jx ) l j m ，j i 。也就是说如果条件x 下数据记录属于c i 类的概率大于属于其他类的概率的话，贝叶斯分类将把这条记录归类 为c i 类。 ( 3 ) 神经网络 神经网络是一组连接的输入输出单元，其中每一个连接都与一个权值相联。在学习阶 段，通过调整神经网络的权，使得能够预测输入样本的正确类标号来学习。 ( 4 ) 遗传算法 遗传算法试图结合自然进化的思想。一般地，遗传学习开始如下：创建一个有随机产生 的规则组成的初始群体。根据适者生存的原则，形成由当前群体中最适和的规则组成新的 群体，以及这些规则的后代。遗传算法中，数据分类问题看成是在搜索问题，数据库看作 是搜索空间，分类算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随 机产生的组分类规则进行进化，直到数据库能被该组分类规则覆盖，从而挖掘出隐含在 数据库中的分类规则。 ( 5 ) 粗糙集 粗糙集理论是一种刻划不完整和不确定性数据的数学工具，不需要先验知识，能有效 地处理各种不完备信息，从中发现隐含的知识，并和各种分类技术相结合建立起能够对不 9 南京邮f 乜人学硕i ：研究生学位论文第二章数据挖掘和w e b 挖掘慨述 完备数据进行分类的算法。粗糙集理论将分类能力和知识联系在起，使用等价关系来形 式化地表示分类。 ( 6 ) 支持向量机 支持向量机是新一代的基于统计学习理论的学习系统，主要思想是建立一个分割两类 的超平面( 这也可以扩展到多类问题) ，在建立的过程中，支持向量机算法试图将两类之 间的隔离边缘被最大化。 3 聚类 聚类是将数据分类，目的是找出同类中数据的相似性，及各类之f a j 的差异性，使得同 类中数据相似度最大，而各类之数据差异度最大。例如，销售业者将客户依其年龄、收入、 居住地点、兴趣等的属性进行分类，这样市场区分能让营销人员了解最适合营销的客户群， 并提供最合适的产品及服务适当的顾客。在w e b 日志挖掘中，可以使用聚类算法对用户和 页面聚类，对用户提供个性化服务，协同过滤推荐技术就是其中的代表，目前使用较广聚 类方法常见的有下列几种： ( 1 ) 层次聚类： 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又 可以分为两类，即自底向上的聚合层次聚类和白顶向下的分裂层次聚类。主要代表算法 有b i r c h 、c u r e 、r o c k 、c h a m e l e o n 等。 ( 2 ) 划分的方法： 将一个有n 个样本的数据库，分为k 个划分( k n ) ，每个划分表示一个簇，并同时 满足以下两个条件的过程，称为划分算法。( 1 ) 每个簇至少包含一个样本：( 2 ) 每个样本 必须属于且仅属于一个簇。主要代表算法有p a m 算法、c l a r a 算法、c l a r a n s 算法等。 ( 3 ) 基于密度的聚类方法 提出基于密度的聚类方法是为了发现任意形状的聚类结果。其主要思想是：只要临近 区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤“噪声 孤立点数据， 发现任意形状的簇。主要代表算法有d b s c a n 、o p t i c s 算法等。 ( 4 ) 基于网格的算法 这种算法首先将数据空间划分成为有限个单元的网格结构，所有的处理都是以单个 的单元为对象的。处理速度通常与目标数据库中记录的个数无关，它只与单元的个数有 关，故这种算法的一个突出优点就是处理速度很快。主要代表算法有s t i n g 算法等。 ( 5 ) 基于模型的算法 基于模型的方法为每个簇都假定了一个模型，并寻找数据对给定模型的最佳拟合。该 l o 南京邮电大学硕士研究生学位论文 第二章数据挖掘和w e b 挖掘概述 算法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的 数据和某些数学模型之间的适应性。主要代表算法有c o b w e b 算法等。 2 2w e b 挖掘 进入2 0 世纪9 0 年代以来，随着网络技术的发展，尤其是i n t e r n e t 的广泛应用，使 得数据挖掘的对象从数据库中的数据延伸到网络上的数据。在这种情况下产生了一个新的 概念：w e b 数据挖掘。w e b 挖掘是将数据挖掘技术应用于大规模w e b 数据，以期发现有效 的、新颖的、潜在有用的，以及最终可理解的模式和规则的过程。相对于w e b 上的数据而 言，传统的数据库中的数据，其结构性很强，即其中的数据为完全结构化的数据，而w e b 上的数据最大特点就是半结构化。所谓半结构化是相对于完全结构化的传统数据库的数据 而言。显然，面向w e b 的数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。w e b 挖掘 在完成这种数据挖掘任务时，既需要使用一些与传统共同的数据挖掘技术，也使用了一些 特有的技术。w e b 挖掘是由e t z i o n i 1 9 9 6 首先提出的，e t z i o n i 给予w e b 挖掘的定义为“使 用数据挖掘技术由因特网的文件及服务中发现并提取出隐含的信息”。1 9 9 7 年有人提出将 w e bm i n i n g 分成两大类：w e b 内容挖掘与w e b 使用挖掘，k o s a l a 等根据网页间的连结组 织架构，在2 0 0 0 年提出第三类的w e b 结构挖掘。因此w 曲m i n i n g 的分类如图2 2 t i o 所 示。 图2 - 2 w e b 挖掘的分类图 在实际应用中，w e b 挖掘的三种方法不是孤立的，而是相辅相成的。尤其是w e b 内容 挖掘和结构挖掘之间关系更为紧密，因为w e b 文档中也包含链接。有的时候，w e b 内容挖 掘和使用挖掘相结合能够更好的完成某个应用任务。例如，w w w m n a z o n p x ) m 网站就综合 南京邮电人学硕i ：研究生学位论文第二章数据挖掘和w e b 挖掘概述 运用了上述方法对用户进行商品推荐。 2 2 1w e b 内容挖掘 网页内容挖掘，顾名思义就是对于网页的内容进行挖掘与分析的工作，与在数据库中 进行挖掘使用的技术大体相同。人们希望从网页文档中非结构化的数据中找出类似的知 识。网页数据非结构化的特性也迫使内容挖掘使用的技术有所变化。网页包含许多种类的 数据，如文本、图片、音频和视频。网页的原始数据是以h t m l 编码的，这种非结构化的数 据，使得计算机程序很难处理。为了先将网页转换成结构化格式，如关系数据库或x m l ， 人们常使用一个规则集，来抽取网页中重要的信息。对于网页内容挖掘，可以从信息检索 与数据库两个不同的观点来看，从信息检索的观点来看，是指从参考使用者的习惯及特性 来协助或增进信息探寻或过滤信息，而从数据库的观点是指将网站上的数据模块化及整合 其使之能更灵活的查询而不单只是以关键词为基础的查询。 w e b 内容挖掘的重点是页面分类和聚类。w e b 页面的分类是根据页面的不同特征，使 用监督学习的方法，将其划归为事先建立起来的不同的类。例如，根据网页的内容，一个 网页分类器可能学习到是把新网页归类到金融新闻类还是政治新闻类，或者其他的类。网 页分类也可以应用在信息检索中。w e b 页面的聚类是指在没有给定主题类别的情况下，将 w e b 页面集合聚成若干个簇，并且同一簇的页面内容相似性尽可能大，而簇间相似度尽可 能小。w e b 内容挖掘的主要方向在文本挖掘。 2 2 2w e b 结构挖掘 w e b 结构挖掘旨在产生网站和网页的结构汇总，它的焦点因此在于可以从h t m l 中抽取 的链接信息，链接信息是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 2 南京邮电人学硕上研究生学位论文第二二章数据挖掘和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 2 3w e b 日志挖掘 w e b 日志挖掘也叫w e b 使用挖掘，是用挖掘w e b 服务器日志获取的信息来预测用户浏 览行为的技术，指从用户的访问日志中挖掘用户的访问模式。w e b 内容挖掘，w e b 结构挖 掘的对象是网上的原始数据，而网络使用挖掘的数据来自于用户在使用网络的过程中，即 在用户和网络交互的过程中抽取出来的第二手数据，这些数据包括：w e b 服务器的访问记 录、代理服务器同志文件、浏览器同志记录、用户注册信息、用户对话或交易信息等其它 信息。现在研究较多的是对日志文件的挖掘。分析这些数据可以帮助理解用户的行为，从 而改进站点的结构，或为用户提供个性化的服务。这方面的研究主要有两个方向：一般的 访问模式追踪和个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录来了解用 户的访问模式和倾向，以改进站点的组织结构。而个性化的使用记录追踪则倾向于分析单 个用户的偏好，其目的