（产业经济学专业论文）Web日志中用户访问模式挖掘的研究及应用.pdf

对外经济贸易大学硕士论文 摘要 近年来，数据挖掘和万维网应用研究是信息时代两大活跃的研究领域，将数据挖 掘技术应用于万维网就称为w e b 数据挖掘。w e b 日志挖掘是w e b 数据挖掘的一种，就是 运用数据挖掘的思想来对服务器日志进行分析和处理，从网站的访问日志文件中挖掘 出用户访问模式，包括关联规则、序列模式等。 通过挖掘w e b 日志可以改善网站的组织结构，监控服务器的工作情况，改善w e b 应用的系统设计，为用户提供个性化服务。另外，w e b 日志挖掘中通过分析挖掘用户访 问路径的结果可以改善站点的设计，改进市场决策。 本文对关联规则及序列模式识别所用的算法进行了深入的研究，比较了不同算法 之间的联系与区别，以及各种算法的优势劣势。通过对中俄经贸合作网进行多次的浏 览与深入研究，发现了其网站架构、栏目设置及u r l 编号的特点，对网站的栏目设置状 况按照不同的级别进行了总结。此外，本文讨论了数据挖掘的预处理技术，并对现有 的中俄经贸合作网w e b 日志数据进行了相应的处理与转换。在深入研究了数据挖掘的相 关算法以及中俄经贸合作网现状的基础上，将理论与实践相结合，完成了对中俄经贸 合作网2 0 0 6 年1 月份的w e b 日志数据的挖掘工作。通过数据挖掘，发现了用户访问该网 站的高频页面、访问时间与栏目之间的关联、及用户访问栏目的先后顺序等的规律。 并结合中俄经贸合作网的具体情况，对挖掘结果进行分析，发现了网站设置中的不合 理之处，进一步针对存在的问题提出了合理化的改进建议。 关键词：数据挖掘w e b 日志关联规则序列模式 对外经济贸易大学硕士论文 a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n ga n da p p l i c a t i o nt ot h ew o r l dw i d ew e ba r ea c t i v er e s e a r c h f i e l d s t h ea p p l i c a t i o no fd a t am i n i n gt e c h n i q u e st ow 州i sr e f e r r e dt oa sw e bd a t am i n i n g w e b l o gm i n i n gi sak i n do fw e bd a t am i n i n g i tu s e st h ei d e ao fd a t am i n i n gt oa n a l y z ea n d d e a lw i t ht h ew e bl o g ，a n dd i s c o v e r su s e ra c c e s sp a t t e r n sf r o mt h ew e b s i t el o g s ，i n c l u d i n g a s s o c i a t i o nr u l e sa n ds e q u e n t i a lp a t t e r n s ，e t c w ec a l li m p r o v et h es t r u c t u r e so fw e b s i t e sa n dt h es y s t e md e s i g no fw e ba p p l i c a t i o n ， m o n i t o rt h es e r v e ra n dp r o v i d ei n d i v i d u a ls e r v i c et ou s e r s i na d d i t i o n ，w e bl o gm i n i n gc o u l d o p t i m i z et h ed e s i g no ft h ew e bs i t e sa n di m p r o v e st h ed e c i s i o n m a k i n go ft h em a r k e tb y a n a l y z i n ga c c e s sp a t ho ft h eu s e r sw h ou s et h ew e bm i n i n g t h em i n i n gt e c h n i q u e so fa s s o c i a t i o nr u l ea n ds e q u e n c ep a t t e r nr e c o g n i t i o nt e c h n i q u e sa r e d e e ps t u d i e di nt h i sp a p e r t h er e l a t i o no rd i f f e r e n c eb e t w e e na l g o r i t h m sa n dt h es t r e n g t ho r w e a k n e s so fe a c ha l g o r i t h mi sa n a l y z e d t h ew e b s i t eh t t p ：w w w c r c m o f c o m g o v c ai sd e e p s t u d i e da n dt h et r a i t so fi t ss t r u c t u r ea n dc o l u m na n du r ln u m b e r i n ga r ed i s c o v e r e da n d s u m m a r i z e d m o r eo v e r , t h et e c h n i q u e so fd a t ap r e t r e a t m e n ta r ed i s c u s s e di nt h i sp a p e r a n d c o r r e s p o n d i n gd a t am a n a g i n ga n dt r a n s f e r r i n gi si m p l e m e n t e di nt h ew e bl o g od a t a b a s e d u p o n t h e d e e ps t u d y o nr e l a t e d a l g o r i t h m s a n dt h e a c t u a l i t y o ft h ew e b s i t e h t t p ：w w w c r c m o f c o m g o v c n ，t h ep a p e rc o m b i n e t h e t h e o r y a n d p r a c t i c et o g e t h e r , c o m p l e t e t h ed a t a m i n i n gp r o c e s s o ft h ew e b l o g d a t ao fj a n2 0 0 6i n h t t p ：w w w c r c m o f c o m g o v c n t h r o u g ht h ep r o c e s so f d a t am i n i n g ，t h eu s e ra c c e s sp a t t e r n s a r ed i s c o v e r e d a n db a s e do nt h ea c t u a l i t yo ft h ew e b s i t e ，t h i sp a p e ra n a l y z et h er e s u l t so f d a t am i n i n g , f i n do u tt h ei m p r o p e rs e t t i n go ft h ew e b s i t e ，t h e np r o v i d er a t i o n a ls u g g e s t i o n s a i ma tt h ep r o b l e m st oi m p r o v et h ew e b s i t e k e y w o r d s ：d a t am i n i n g ：w e bl o g ：a s s o c i a t i o nr u l e ；s e q u e n t i a lp a t t e r n 对外经济贸易大学硕士论文 第一章绪论 近年来，随着i n t e r n e t w e b 技术的快速普及和迅猛发展，使各种信息可以以非常 低的成本在网络上获得，由于i n t e r n e t 互联网在全球互连互通，可以从中取得的数据 量难以计算，而且i n t e r n e t 互联网的发展趋势继续看好，特别是电子商务的蓬勃发展 为网络应用提供了强大支持，如何在互联网这个全球最大的数据集合中发现有用信息 无疑将成为数据挖掘研究的热点。本章将介绍w e b 日志挖掘的研究背景和意义，国内 外相关研究与应用的现状，以及论文的研究目的、主要研究内容与组织方式，为接下 来的研究奠定基础。 1 1 研究背景和意义 1 1 1 研究背景 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 。 目前市面上比较流行的w e b 服务器侧如i i s ，a p a c h e 等，通常都保存了对w e b 页面的每一次访问的日志项，这些记录项又叫做w e bl o g 项。它忠实地记录了访问该 w e b 服务器的数据流的信息。w e b 使用记录数据除了服务器的日志记录外还包括代理服 务器日志、浏览器端日志、注册信息、用户会话信息、交易信息、c o o k i e 中的信息， 用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见w e b 使用记录盼 数据量是非常巨大的，而且数据类型也相当丰富。 日益增长的网站访问信息和飞速发展的数据挖掘技术使得网站能够真正地为它的 在线顾客提供个性化服务，市场应该使网站施效于对它真正有利益的客户。在一个动 态的强竞争的网络环境中，电子商务网站必须通过较好地理解访问频繁的客户和最有 利可图的顾客的行为，才能取得它们的竞争优势。要想了解客户的访问行为就必须通 过日志挖掘去挖掘你的网站数据，使网站的努力集中在有利可图的顾客和前景上。 w e b 日志挖掘( w e bl o gm i n i n g ) 是从w e b 服务器中自动发现用户的访问模式3 。 1 宋敏青，数据挖掘在w e b 中的研究与应用【j 】现代情报，2 2 舯3 ：5 9 - 6 2 2 单红花w 曲数据挖掘探讨锕电脑知识与技术，2 0 0 6 2 3 同上 对外经济贸易大学硕士论文 在w e b 服务器e t 志中自动搜集并记录着用户的访问操作，还有通过c g i 记录的用户注 册信息。通过对这些用户信息的分析，可以找出用户的访问模式，确定产品的市场战 略，提高商业活动的效率，而且为站点的有效组织也提供了信息，还可以为特定的用 户提供个性化的网络服务。w e b 日志挖掘在新兴的电子商务领域有重要意义，它通过挖 掘相关的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析日志记录中的规 律，可以识别用户的忠实度、喜好、满意度，可以发现潜在用户，增强站点的服务竞 争力。 根据对数据源的不同处理方法，w e b 日志挖掘可以分为两类，一类是将w e b 使用 记录的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系表中的数据进 行常规挖掘；另一类是将w e b 使用记录的数据直接预处理再进行挖掘。 根据数据来源、数据类型、数据集合中的用户数量、数据集合中的服务器数量等 将乳b 日志挖掘分为五类： 1 、个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基本信息 分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供与众不同的个 性化服务 2 、系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量用户满 意度的关键指标，w e b 日志挖掘可以通过用户的拥塞记录发现站点的性能瓶颈，以提示 站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机制和数据的分布策略。 此外，可以通过分析网络的非法入侵数据找到系统弱点，提高站点安全性，这在电子 商务环境下尤为重要。 3 、站点修改；站点的结构和内容是吸引用户的关键。w e b 日志挖掘通过挖掘用户 的行为记录和反馈情况为站点设计者提供改进的依据，比如页面连接情况应如何组织、 那些页面应能够直接访问等。 4 、智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的重点， 用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 日志挖掘可以通 过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销售商合理安排销售 策略 5 、w e b 特征描述：这类研究主要通过用户对站点的访问情况统计各个用户在页面 上的交互情况，对用户访问情况进行特征描述。 w e b 日志挖掘系统的过程5 如图1 1 所示，挖掘过程主要分为四个阶段：数据预处 j i a w e ib a l m , m i c h e l i n ek a m b e r 数据挖掘概念与技术【m 】帆械工业出版社，2 0 0 1 ，8 c o o l e y , g m o b a s h e r , b ，a n ds r i v a s t a v a , j ，d a t a p r e p a r a t i o n f o r m i n i n g w o r l d w i d e w e b b r o w s i n g p a t t e r n ，k n o w l e d g e a n d i n f o r m a t i o n s y s t e m s ，1 9 9 9 ，1 ( 1 ) 5 - 3 2 2 对外经济贸易大学硕士论文 理、挖掘算法实施、模式分析、可视化。 原始日志文件用户会话文件规则和模式( 感兴趣的) 规则和模式 图1 1w e b 日志挖掘的典型过程 资料来源：管旭东基于w e b 日志挖掘技术的智能w e b 站点研究 w w w d m r e s e a r c h n e t2 0 0 6 4 1 7 第2 l 页 数据预处理：主要完成将原始的日志文件经过过滤、筛选以及重组后，将之转变 为适合挖掘的数据格式，通常以用户会话文件的形式保存到数据库中，后续的挖掘过 程可以直接在此基础上进行各种挖掘操作。 o 浏览模式挖掘：w e b 日志挖掘的核心，根据挖掘任务的不同，采用不同的挖掘算 法，从数据预处理阶段产生的用户会话中寻找用户的浏览模式。发现的模式一般有关 联规则、序列模式、用户聚类等。 模式分析：经过浏览模式挖掘阶段，可以得到一些从前未知的用户访问模式，但 是，并非所有的模式都是准确的和有使用价值的。这一阶段，我们要利用领域专家的 知识以及其它一些可用的标准来分析这些模式，并过滤掉那些没有利用价值以及有偏 差的模式。 可视化：将发现的有价值的用户浏览模式以各种形式显示，为决策层的领导提供 直观的显示显示的方式可以为表格、饼图、曲线图、趋势图、直方图或者其它特殊 表现形式 目前大部分的公司都有自己网站产生出来的巨大数量的用户信息，因而大型的电 子商务网站需要有适合大量数据的挖掘工具，希望能通过数据挖掘得到益处。 “中俄经贸合作网”是由中国商务部与俄罗斯经贸部共同主办的官方网站，其目 的是推动双边经贸合作发展，为两国政府、企业以及研究机构提供服务。经过不到两 年的运营，“中俄经贸合作网”在中俄两国工商企业界的影响力不断增强，已成为两 3 对外经济贸易大学硕士论文 国商界人士了解对方国情，特别是两国最新经济动态和寻求商机的得力助手。 1 1 2 研究的意义 网站的吸引力取决于其内容和组织结构的合理性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 日志数据除了服务器的日志记录外还包括代理服务器日志、浏览器端日志 注册信息、用户会话信息、交易信息、c o o k i e 中的信息、用户查询、鼠标点击流等一 切用户与站点之间可能的交互记录。可见w e b 日志的数据量是非常巨大的，而且数据 类型也相当丰富。根据对数据源的不同处理方法，w e b 日志挖掘可以分为两类，一类是 将w e b 日志的数据转换并传递进传统的关系表里，再使用数据挖掘算法对关系表中的 数据进行常规挖掘；另一类是将w e b 日志的数据直接预处理再进行挖掘。通常来讲， 经典的数据挖掘算法都可以直接用到w e b 日志挖掘上来，但为了提高挖掘质量，研究 人员在扩展算法上进行了努力，包括复合关联规则算法、改进的序列发现算法等。 近年来，国外在w e b 日志挖掘领域的研究工作取得了很大的进展。，这方面取得 了一定的成果。一些比较成功的w e b 日志挖掘系统相继推出，而国内在这方面的研究 h t t p ：h w w w c r c r o o f c o r n g o v c a c r w c b c r c d i n f o l g y w m j s p 7 宋敏青，数据挖掘在w e b 中的研究与应用【j 】现代情报，2 0 0 2 , n o 弱9 6 2 。b c h z a dm o r t a z a v i - a s l d i s c o v e r i n ga n dm i n i n gu s e rw c b - p a g et r a v e r s a lp a t t e r n b s c ，s i m o af r a s e ru l 西c b i 吼1 9 9 9 4 对外经济贸易大学硕士论文 还处于起步阶段。w e b 日志挖掘的主要日的是为了更好地了解访问电子商务网站的用户 的行为和动机。还有一些研究应用数据挖掘结果来改进w e b 站点的设计、分析系统性 能和网络通讯或者建立适应性站点 目前国内外基于w e b 服务器日志数据的用户访问模式挖掘研究工作大致可分为以 下3 类： l 、以分析w e b 站点性能为目标，主要从统计学的角度，对日志数据项进行统计， 得到用户频繁访问页、单位时间访问数、访问数据随时间分布图等。绝大多数商用及 免费的w e b 日志分析工具都属于此类。 2 、理解用户意图为目标。c h e 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 n ”等使用数据立方体方法，便是此类的典型代表。 3 、以改进w e b 站点设计为目标。通过挖掘用户的频繁访问路径和用户聚类，重沟 站点的页面之问的连接关系以更适应用户的访问习惯，同时为用户提供个性化的信息 服务。c o o l e yr “等人首次给出w e b 挖掘的定义，并且给出一个关于w e b 访问信息挖掘 的系统w e b m i n e r 。通过对w e b 站点的日志进行处理，将数据组织成传统的数据挖掘方 法能够处理的事务数据形式，然后利用传统的数据挖掘方法( 如关联规则发现算法) 进 行处理。 w e b 日志挖掘是一个较新的研究领域，具有广阔的发展和应用前景。面对日益增 加的商业需求，w e b 日志挖掘技术还有许多问题需要解决，有待于这一领域的深入研究。 例如： i 、如何针对不同类型站点的w e b 日志数据选择最高效、最符合需求的数据挖掘算 法： 2 、在大数据量的情况下，如何对包含大量冗余数据的w e b 日志记录进行数据清洗 与用户、会话的识别； 3 、在数据挖掘的过程中，如何根据数据的具体情况和特点采取有效的措旌保证挖 掘结果的准确性。 c - l a e n m s , p m - kj s p s e f f i c i e n t d a t a m i n i n g f o r p a t h t r a v e r s a l p a t t e r n j j e e e t n t m o a k n o w l e d g ea n d d a t a e “g m e e r i a g ，1 9 9 5 , 1 0 ( 2 ) ：2 0 9 - 2 2 1 加j i a w e ih a r t ，m i c h e l i n e - ( a n l b 盯数据挖掘概念与技术【m 】机械工业出版社2 0 0 1 ，8 “r c o o l e y , e n t a a , j s r i v a s t a v a d i s c o v e r y o f i n t e t s t f i n g u s a g e p a t t e r n f r o m w e b d a t a s p r i n g e r v e f l a g , 2 0 0 0 对外经济贸易大学硕上论文 1 3 研究内容和论文组织方式 1 3 1 研究内容 数据挖掘在传统的结构化的事务数据挖掘领域，已经取得了比较成功的应用，然 而，w e bl ：的信息不同于数据库，数据库有规范的数据结构，而w e b 上包括文本、图片、 v i d e o 等多种信息，它们是半结构化的。因此，w e b 上的挖掘需要不同于常规的数据挖 掘的很多技术；然而这些半结构化、异构的数据信息包含着丰富有价值的知识。基于 以上两点，本文进行研究的目的主要有： 1 、利用现有的中俄经贸合作网的访问日志的数据，在对数据进行一定的预处理的 情况下，寻求一种高效的算法，完成对用户的访问模式识别及分析等工作。 2 、以中俄经贸网站作为项目的应用平台，通过对该网站的w e b 日志记录进行挖掘， 发现用户的访问模式，对网站的结构及栏目等提出合理可行的改进方案。 w e b 日志挖掘中用户访问模式研究，主要用到关联规则和序列模式挖掘的相关知 识 在w e b 日志挖掘中，关联规则指：只要页面的支持度大于某个被给定的阈值，那 么这些页面就都被访问。关联规则能够有助于w e b 设计者重新组织站点的内容编排。 序列模式指在时序数据集中发现在时闻上具有先后顺序的数据项。在w e b 日志挖 掘领域中，序列模式识别指寻找用户会话中在时间上有先后关系的页面请求，利用发 现的序列模式可以预测用户即将可能请求的页面，也可以按照用户的浏览结构合理的 调整网站的页面结构。 基于以上研究目的，本文对以下内容进行了研究和分析。 1 、对数据挖掘的实现过程及实现技术进行分析和研究，关联规则和序列模式是研 究和发现事务数据库中数据项之间的相关性的方法，本文对关联规则及序列模式识别 所用的算法进行了深入的研究。 2 、讨论了日志预处理的过程及几种有效的数据预处理方法，包括数据清洗、用户 识别、会话识别等在预处理的基础上，对中俄经贸合作网的w e b 日志记录进行进一 步的格式转换，使之能够应用于关联规则和序列模式的算法。 3 、采用关联规则和序列模式识别算法，借助软件工具对中俄经贸合作网的w e b 日志记录进行挖掘，算法可以从w e b 服务器日志中挖掘出用户信息和数据信息，可有 效地识别用户访问模式。 4 、利用发现的关联规则和序列模式预测用户即将可能请求的页面，按照用户的浏 6 对外经济贸易大学硕七论文 览结构对调整网站的页面结构提出合理化建议。 1 3 2 论文组织方式 本论文主要分为五个章节进行论述。 第一章绪论，介绍了课题的背景、国内外研究发展概况和主要研究内容； 第二章关联规则和序列模式挖掘介绍，对基本的关联规则和序列模式挖掘算法进 行了详述和对比分析； 第三章w e b 日志挖掘过程的准备与实施，是本文的重点，主要论述对数据进行预 处理使之能够适应挖掘算法的要求以及利用处理之后的数据实现挖掘算法进行挖掘的 过程； 第四章分析及建议，对w e b e l 志挖掘的结果进行了详细的分析，并根据分析结果， 对中俄经贸合作网的网站架构及页面设置提出了部分改进建议； 第五章总结与展望，对全文的研究工作及成果的总结和对今后的进一步研究工作 的展望。 1 4 本章小结 本章是全文的绪论。主要介绍了w e b 日志挖掘的研究背景和意义，国内外相关研 究与应用的现状，以及论文的研究目的、主要研究内容与组织方式，为后续几章的研 究和分析做了充分的铺垫及准备。 对外经济贸易大学硕士论文 第二章关联规则和序列模式挖掘介绍 关联规则和序列模式挖掘是w e b 日志挖掘中很重要的两种挖掘方法。本章将对关 联规则和序列模式挖掘的相关概念进行介绍，对两种挖掘方法之间的联系与区别进行 对比；接下来，将对经典的关联规则和序列模式挖掘的算法进行详细的阐述，对各种 算法的优势和劣势进行分析，为进一步进行w e b 日志数据的挖掘打下理论基础。 2 i 概述 2 1 1 关联规则 关联规则挖掘能够发现大量数据中项集之间有趣的关联或相关联系。它在数据挖 掘中是一个重要的课题，最近几年己被业界所广泛研究。 2 1 1 1 基本概念： 关联是两个或多个变量取值之问存在的一类重要的可被发现的某种规律性关联 分析目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切 度。 给定一个交易数据集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用 户给定的最小支持度阈值和最小置信度阈值的关联规则。同时满足最小置信度阈值和 最小支持度阈值的关联规则为强关联规则，是有意义有价值的规则。 关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据 库中不同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买 其他商品的影响分析结果可以应用于商品货架布局、存货安排以及根据购买模式对 用户进行分类。 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题， 以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原 有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率； 对关联规则的应用进行推广。 2 1 1 2 符号化表示： 设i - - i l ，i 2 ，i m 是项集，其中i k ( k ：l ，2 ，m ) 可以是购物篮中的物品，也可 以是保险公司的顾客设任务相关的数据d 是事务集，其中每个事务t 是项集，使得 t _ c l 。设a 是一个项集，且a _ c t 。 8 对外经济贸易丈学硕士论文 关联规则是如下形式的逻辑蕴涵：a 4 b ， c i ，a c i ，且a n b = m 。关联规则具有 如下两个重要的属性： 支持度：p ( a ub ) ，即a 和b 这两个项集在事务集d 中同时出现的概率。 置信度：p ( bia ) ，即在出现项集a 的事务集d 中，项集b 也同时出现的概率 2 1 1 3 关联规则的种类： l 、基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。 数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理， 将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可 以包含种类变量。 2 、基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的。在多层关联规则中，对数据的多层性已经进行了充分的考虑。 3 、基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品。在多维关 联规则中，要处理的数据将会涉及多个维。 2 1 2 序列模式 2 1 2 1 基本概念： 现实生活中有许多按时间进行排序的事件序列，例如一位顾客对某超市的购买活 动序列；网络用户对w e b 站点的访问序列等等。网站为了吸引更多的用户，不仅需要分 析用户在访问过程中最喜欢看哪些内容，还需要分析用户在浏览某些内容之后，接下 来会访问哪些网页，分析用户每次访问的网页间的联系，这就导致了序列模式挖掘的 产生。由于很多商业交易、电传记录、天气数据、生产过程和疾病状态都是序列数据， 在针对目标市场、客户吸引、气象预报、疾病诊断等的数据分析中，序列模式挖掘是 很有用途的。 序列模式的概念最早是由a g r a w a l 和s r i k a n t 提出的。 序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素 按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈 值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不 低于用户指定的最小支持度阈值。 9 对外经济贸易大学硕士论文 例子i ：在两年前购买了f o r d 牌轿车的顾客，很有可能在今年采取贴旧换新的购 车行动 例予2 ：在购买了自行车和购物篮的所有客户中，有7 0 的客户会在两个月后购买 打气筒 2 1 2 2 符号化表示： 序列是不同项集的有序排列。 定义1 ( 序列) ”：i = i 1i 2 i m 是项集，i k ( 1 = k - - m ) 是一个项，序列s 记 为s = ，其中s j ( 1 - j = n ) 为项集( 也称序列s 的元素) ，即s j i 。每 个元素由不同项组成。序列的元素可表示为( i li 2 i k ) ，若一个序列只有一个项， 则括号可以省略 序列包含的所有项的个数称为序列的长度。长度为l 的序列记为l - 序列。 定义2 ( 子序列) ”：序列t = 是另一个序列s = 的 子序列，满足下面条件：对于每一个j ，l = j = m - - i ，有i j i j + l 且对于每一个j ，l = j - - m ， 存在l ：k = 5 ，则称序列s 为序列数据库d 中的一个( 频繁) 序 列模式。 长度为l 的序列模式称为l - 模式。 序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出 现频率超过最小支持度( 用户指定最小支持度阈值) 的子序列。 定义5 ：( 序列关联规则) ”；对于给定的项集i = ( i 1i 2 i m 以及序列s ，t ， 1 2 彭曙蓉等菩于马尔可夫链的w 曲访问序歹i i 挖掘算法m 计算机工程与设计，2 6 ，2 n 同上 同上 廿同上 “同上 对外经济贸易大学硕士论文 形如s t 的表达式称为序列关联规则。 序列关联规则s 甜的支持度是支持序列s 和t 的顾客数占总顾客数之比。 序列关联规则s = 钉的置信度记为( a ) ，是支持序列s 和t 的顾客数与仅支持s 的顾 客数之比 例子：设序列数据库如下图所示，并设用户指定的最小支持度m i n - s u p p o r t = 2 表2 1 序列数据库举例 s e q u e n c e _ i ds e q u e n c e 1 0 2 0 3 0 4 0 资料来源：w w d m g r o u p o r g c n p p t d o w n 0 5 0 3 2 2 根据上面的定义可知，序列 是序列( a ( a b c ) ( a c ) d ( c f ) 的子序列，序列 是长度为3 的序列模式。 2 1 3 序列模式挖掘与关联规则挖掘的比较 序列模式挖掘的许多概念和算法都是由关联规则挖掘的概念和算法延伸发展而来 的。它们之间有很多相似之处，然而在本质上它们是不同的，我们以顾客购买商品的 数据为例来说明它们之间的区别。 关联规则数据挖掘所要解决的问题是发现哪些商品是顾客喜欢一起购买的，顾客 在一次交易中购买某些商品后还会购买哪些商品，它是发现交易的“内部”规律的过 程，从而使得售货方能够按照顾客的购买兴趣来安捧货架上的商品，达到卖出更多商 品的目的；而序列模式挖掘所要解决的问题是顾客在完成一次交易后，在以后的满足 特定时间约束的交易中，他还会购买什么商品，是发现交易之间关系规律的过程，使 得售货方能够根据当前的商品买卖情况来预测以后的商品买卖情况，从而能够更好地 安排货架上商品的内容，防止顾客买不到想要购买的商品 对于同一交易数据库来说，序列模式挖掘所要挖掘的模式空间要比关联规则挖掘 的模式空间大得多，所要解决的问题也复杂得多；所以序列模式挖掘是一种复杂数据 类型的数据挖掘。 2 1 4 序歹q 模式挖掘和时间序列( t i m es e r i e s ) 模式挖掘的差别 序列模式挖掘和时间序列模式挖掘在概念上很容易被混淆，但是如果从挖掘的数 对外经济贸易大学硕士论文 据对象和挖掘的目的来看，就很容易区分二者了。时间序列模式挖掘最早是统计学上 的一个概念，后来被数据挖掘所采用，并增添了一些新的内容。时间序列模式挖掘根 据数据随时间变化的趋势，发现某一时间段内数据的相关处理模型，预测将来可能出 现值的分布。它可以被看成是一种特定的关联模型，它在关联模型中增加了时间属性。 时间序列模式挖掘的目标主要有趋势预测、相似性搜索和周期分析等；而序列模式挖 掘的目的是研究事件发生的先后关系，找出其中的规律，即不仅需要知道事件是否发 生，而且需要确定该事件与其它事件发生的先后顺序序列模式挖掘也有时间约束， 但它的目的是更好的约束事件之间的先后关系，而不是规定事件在时间上的变化。 2 2 关联规则和序列模式识别算法分析 2 2 1 经典关联规则算法分析 2 2 1 1a p r i o r i 算法 a p r i o r i 性质：频繁项集的所有非空子集也都必须是频繁的。 a p r i o r i 性质基于如下观察： 根据定义，如果项集i 不满足最小支持度阀值m i n _ s u p ，则i 不是频繁的，即p ( i ) ( m i n _ s u p 。如果项a 添加到i ，则结果项集( 即iu a ) 不可能比i 更频繁地出现。 因此，iu a 也不是频繁的，即p ( iu a ) m i n _ s u p ”。 将a p r i o r i 性质用于挖掘关联规则，就是关联分析中的经典算法一a p r i o r i 算法， 它是最有影响力的挖掘布尔关联规则的算法。 方法： 1 、找频繁项集卜项集 2 、a p r i o r i _ g e n ( k _ bm i ns u p ) 函数做两个动作：连接和剪枝。用于在第k _ 1 次遍 历中生成的k 一。生成c 。 3 、由g 生成k a p r i o r i 使用一种称作逐层搜索的迭代方法，k 一项集用于探索( k + 1 ) 一项集。首 先，根据预先设定的支持度，找出频繁卜项集的集合，该集合记作l 。l 用于找频繁2 一 项集的集合k ，而k 用于找k ，如此下去，直到找到频繁k 一项集。这个过程中，为了寻 找h ，首先通过h 一。与自己连接产生候选k 一项集的集合，该候选项集的集合记作c - ，c t 是l 。的超集。利用a p r i o r i 性质对c 进行压缩，即，如果一个候选k 一项集的( k 一1 ) 一予 1 7 陈敏，欧阳一鸣，刘红樱w e b 挖掘中基于r d a p d o r i 算法发现用户频繁访问模式们，徽电学与计算机，2 0 0 5 ，5 对外经济贸易大学硕士论文 集不在k 一。中，则该候选也不可能是频繁的，从而可以从c 。中删除。c 冲的每个元素需 在交易数据库中进行验证来决定其是否加入k ，这里的验证过程是算法性能的一个瓶 颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含1 0 个项，那 么就需要扫描交易数据库1 0 遍，这需要很大的i 0 负载。虽然每次寻找k 都需要一次数 据库扫描，但是，因为a p r i o r i 性质压缩了算法中每次迭代过程中的搜索空间，从而减 少的运行时间。 可能产生大量的候选集，以及可能需要重复扫描数据库，是a p r i o r i 算法的两大缺 点。 2 2 1 2c a r m a 算法： 已有的一些关联规则挖掘算法在运行之前要求用户输入最小置信度和最小支持 度。而对用户来讲，确定合适的最小置信度和最小支持度比较困难，需要运行算法多 次判断最小置信度和最小支持度是否过高或过低。c h r i s t i a nh i d b e r1 9 9 9 年提出了在 线挖掘关联规则的算法c a r m a ( c o n t i n u o u sa s s o c i a t i o nr u l em i n i n gh l g o r it h m ) ”， 此算法在运行过程中给用户以反馈，用户可根据反馈信息随时调整最小支持度，如用 户对输出结果已感到满意，可随时终止算法的运行。 在线挖掘关联规则算法c a r m a 简介：c a r m a 算法的目的是找出交易集合d 中的数 据项频集的集合 c a r m a 算法需要遍历整个交易集合两次，因此算法分为两步，第一次遍历称为 p h a s e i ，第二次遍历称为p h a s e i i 第一次遍历产生一个数据项频集的集合的超集，称为 潜在的数据项频集的集合( p o t e n t i a l l yl a r g ei t e ms e t s ) 第二次遍历把第一次遍历 产生的集合进行删减，得出最终的结果实际上，由于算法本身的特点，第二次遍历并不 一定需要进行完在第一次遍历的过程中，允许用户随时修改支持度，算法保证最后给 出的结果符合用户最后一次修改的支持度在两次遍历中，c a r m a 算法维护一个数据项 集的集合v ，逐个读入交易集合d 的每一条交易进行处理，向v 中增加元素或从数据项集 的集合中删除元素，当第二次遍历结束时，v 就是算法的结果，即数据项频集的集合具 体的c a r m a 算法参见参考文献( 1 5 ) 。 c a r m a 算法的特点： 所谓在线算法，是相对于批处理式算法而言，有以下特点： l 、算法执行过程中即能不断产生部分计算结果，供用户参考； 2 、在算法执行过程中，用户能根据产生的部分计算结果控制算法如何进行下去； ”h i d b c r c o n l i n e a s s o c i a t i o n r u l e m i n i n g j 1 p r o c e e d i n g s o f a c m s i g m o d i n t e r n a t i o n a lc o n f e r e n c e o n m a n a g e m e n t o f d a t a , 1 9 9 9 ：1 4 5 1 5 6 对外经济贸易人学顾 二论文 3 、算法给出的结果必须是精确的。 在线算法相对于离线的和批处理式的算法而言，可交互性较好。c a r m a 算法最多 需要遍历交易集合两次，因为第二次遍历不一定需要进行完，如满足某条件，算法可 能在第二次遍历未结束时就终止在第一次遍历过程中，算法逐步建立起一个潜在的 数据项频集的集合l ，对l 中的每一个数据项集，c a r m a 计算其支持度的上界和下界。 每处理一条交易之后，算法向用户输出根据当前集合l 计算出的关联规则以及每条关 联规则的支持度和置信度的上界和下界，用户可以根据输出信息调整最小支持度和最 小置信度的数值。注意这种调整是随时发生的。如用户对输出的中间结果满意，可提 前结