（计算机软件与理论专业论文）web使用挖掘中事务间关联规则方法研究.pdfVIP

辽宁师范大学硕士学位论文 | l i i iiii ii iii i i ii i i iiii y 18 9 0 0 4 3 摘要 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 使用挖掘中事务间关联规则方法研究 t h em e t h o do f m i n i n gi n t e r - t r a n s a c t i o na s s o c i a t i o nr u l ef o rw e b u s a g em i n i n g a b s t r a c t w e bd a t am i n i n gi st h e p r o c e s so fe x t r a c t i n g v a l u a b l ei n f o r m a t i o ni nt h ew e b e n v i r o n m e n ta c c o r d i n gt ot h eu s e r sb r o w s i n gb e h a v i o r w e bu s a g em i n i n gi sa ni m p o r t a n t c o m p o n e n to f d a t am i n i n ga n dt h eu s e ri st h ec o r eo f 朊6u s a g em i n i n g 腑6u s a g em i n i n g e x t r a c t st h em e a n i n g f u la n dd e s c r i p t i v em o d e l so fu s e rb e h a v i o rb yt h ea l g o r i t h mo f a s s o c i a t i o nr u l e s ，e n h a n c e st h ee m c i e n c yo fs e a r c h i n gi n f o r m a t i o na n dp r o v i d e su s e r s 晰t h i n s t r u c t i o n a lf o r e c a s te x p e r i e n c e b ya n a l y z i n ga n ds u m m a r i z i n gt h ep r e v i o u sm i n i n ga l g o r i t h mo fi n t e r - t r a n s a c t i o n a s s o c i a t i o nr u l e s ，t w on e wi n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e sa r ep r o p o s e d ： ( 1 ) m i n i n ga l g o r i t h mo fi n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e sb a s e do nc l u s t e r i n ga n a l y s i s a c c o r d i n gt h ea l g o r i t h m ，i n i t i a la n dc o m p l e xd a t a s e t sa r er e d u c e db yc l u s t e r i n ga n a l y s i s ， f i r s t l y , w h i c ha v o i dm u l t i s c a n so fd a t a b a s ea n dp l e n t i f u lf a l s er u l e sg e n e r a t i o n 1 1 1 i ss t e p g e n e r a t e sm a n ys m a l ld a t as e t sw h i c ha r et r e a t e db yi n t e r t r a n s a c t i o n a s s o c i a t i o nr u l e s e x p e r i m e n t a lr e s u l t ss h o wt h em e t h o df o r e c a s t su s e r s i n t e r e s tm o r ee m c i e n ta n da c c u r a t e t h a nt h o s em e t h o d sw h i c ho n l yu s ei n t e r t r a n s a c t i o na s s o c i a t i o nr u l e s ( 2 ) m i n i n ga l g o r i t h mb a s e do nc l u s t e r i n ga n a l y s i s i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e sa n d d u a l s t r a t e g yi n t e r e s t - a n a l y s i sm o d e t h ep r o p o s e da l g o r i t h mu s e dt h ed u a l s t r a t e g ya n a l y s i s m o d e lt oi u d g et h ei n t e g r i t yo fi n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e sa n dd i v i d e di n i t i a ld a t a b a s e i n t oa s s o c i a t i o nd a t a b a s ea n dm a r k o vd a t a b a s e ，w h i c ha v o i d e dt h ef a l s er u l e s a f t e rt h a t ，t h e c l u s t e r i n ga n a l y s i si sa d o p t e dt or e m o v ep l e n t yo fr e d u n d a n td a t aa ta s s o c i a t i o nd a t a b a s ea n d m a r k o vd a t a b a s e ，w h i c h i m p r o v e sa l g o r i t h m se f f i c i e n c y f i n a l l y , t h ep r e d i c t i o n o f a s s o c i a t i o nr u l ea n dm a r k o vm o d e la r er e s p e c t i v e l ya d d e dt oe a c hs u b - d a t a b a s e e x p e r i m e n t a l r e s u l t ss h o wt h i sa l g o r i t h mi ss u p e r i o rt ot h et r a d i t i o n a lb u s i n e s sa s s o c i a t i o nr u l e si n a c c u r a c y a n de 伍c i e n c y w i t ht h ed e v e l o p m e n to ft h ew 曲t e c h n o l o g y , t h ed a t e si nt h ew 曲- s e r v e ra r eg o i n gm o r e a n dm o r eh u g ea n dc o m p l e x h o wt os o l v et h ec o n t r a d i c t i o nb e t w e e ne f f i c i e n c ya n da c c u r a c y o fd a t am i n i n gi san e wc h a l l e n g e t h u s ，t h i sp a p e ru s e st h ei n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e s t o i m p r o v ea c c u r a c yo fd a t am i n i n g ，a n de m p l o y st h et e c h n o l o g yo fc l u s t e ra n a l y s i st o i m p r o v ee f f i c i e n c y , w h i c hp r o v i d e sn e w i d e af o rw e b u s a g em i n i n g k e y w o r d ：w e bu s a g em i n i n g ；i n t e r - t r a n s a c t i o n a s s o c i a t i o nr u l e ；c l u s t e r i n g a n a l y s i s ； d u a l s t r a t e g ya n a l y s i sm o d e l ；m a r k o vm o d e l s u 辽宁师范大学硕士学位论文 目录 摘要i a b s t r a c t i i ll 者论1 1 1 研究背景与意义1 1 2 国内外研究现状2 1 3 现有算法存在的问题3 1 4 本文研究工作及结构安排3 2 关联规则及聚类分析的相关概念5 2 1 关联规则的相关知识5 2 1 1 传统关联规则的基本概念6 2 1 2 事务间关联规则的基本概念7 2 2 关联规则算法7 2 2 1 传统关联规则算法7 2 2 2 事务间关联规则算法8 2 3 聚类分析的相关概念8 2 4 聚类分析算法1 2 2 5 本章小结1 3 3 基于聚类分析的事务间关联规则挖掘算法1 4 3 1 相关定义1 4 3 2 基本原理1 5 3 3 聚间关联规则挖掘1 6 3 3 1 聚类分析1 6 3 3 2 事务内到事务间关联规则的转换1 7 3 3 3 大数据集事务间关联规则的生成18 3 4 实验测试与结果分析1 9 3 5 本章小结2 3 4 基于聚类的事务间关联规则双策略分析模型2 4 4 1 相关定义2 4 4 2 基本原理2 5 4 3 双策略分析模型d a m 2 5 4 3 1 双策略兴趣预测分析2 5 4 3 2 聚类预处理2 6 4 3 3 事务间关联规则预测2 7 4 3 4 马尔可夫模型预测2 8 4 4 实验测试结果分析2 9 4 5 本章小结3 2 结论3 3 参考文献3 4 攻读硕士学位期间发表的论文3 6 攻读硕士学位期间参与的科研项目3 6 j $ 【谢3 7 i i i 辽宁师范大学硕士学位论文 1 绪论 1 1 研究背景与意义 近年来，随着i n t e m e t 、c o m p u t e r 及s t o r a g e 技术的发展，大量的数据被迅速积累 在企业、科研机构、政府等部门的计算机中。庞大的数据量使许多部门出现了数据丰富 和信息匮乏的局面。但信息系统被广泛的使用之后，人们能够充分的利用这些数据，从 中挖掘出有用的信息，帮助企业做出决策，提高用户的满意程度、优化工作流程、降低 企业的库存量等。在此背景下，受数据分析、人工智能、数据库、统计学等相关技术的 影响，产生了数据库知识发现( k d d ) 这门学科，人们形象的称它为“数据挖掘i l 】，。数 据挖掘是一门交叉学科，它包括关联规则、聚类、分类、时间序列、模式序列等方面。 数据挖掘的系统结构组成，如图1 1 所示。 数 图1 1 数据挖掘系统结构 f i g 1 1 d a t am i n i n gs y s t e ms t r u c t u r e w e b 使用挖掘中事务间关联规则方法研究 数据挖掘历史较短，在1 9 9 5 年，第一届数据挖掘国际会议才在美国召开，并标志 着数据挖掘技术进入了一个新的阶段。随后，数据挖掘研究【2 】受到了全球的关注，各大 学院均设置了数据挖掘的相关专业或方向。数据挖掘从上世纪9 0 年代得到了蓬勃发展， 用于从大量的数据中挖掘出有价值的信息。可被用于金融、保险、科研、电信等行业。 同时，也可被用于信息管理、查询优化、过程控制、决策支持等方面。 随着互联网的不断发展与完善，互联网的各种应用业务也同雨后春笋般的迅速发展 起来，例如远程医疗、网上订票、远程教育、网上银行等商业形式。互联网在给我们带 来机会的同时也带来了挑战。随着互联网应用业务的广泛使用( 例如电子商务，w e b 站点的设计等) ，越来越多的数据出现在w w w 中。这就需要我们能够从用户的访问频 度、访问时间、访问兴趣等方面进行动态的调整，改进业务，开展有针对性的电子商务， 为用户提供更加满意的服务。w e b 数据挖掘就是解决这一需求的有利工具。 w e b 数据挖掘【3 l 是数据挖掘在网络环境下的应用。w e b 数据挖掘包括w e b 使用挖 掘、w e b 结构挖掘、w e b 内容挖掘。其中，w e b 使用挖掘【4 】是从浏览器、服务器端的用 户个人信息和日志记录中搜索出潜藏在数据中的模式信息，以便获取那些有意义的，描 述用户行为的模型，并为改进w e b 站点的性能和结构，提高信息的查找效率和质量， 做出指导性的预测分析。 w e b 使用挖掘1 5 】通过数据预处理、模式挖掘、模式分析完成用户兴趣的预测。数据 预处理可以去掉数据中图像、视频、网页日志、声音等无关噪声。模式挖掘运用相关算 法挖掘出经过预处理之后的数据所存在的隐含关系。模式分析是对模式挖掘得到的结果 进行预测分析，并能够向用户推荐感兴趣的内容。 1 2 国内外研究现状 对于事务间关联规则目前已存在多种研究算法，不单单只有聚类、关联规则、分类 等传统的方法，近几年又出现了将聚类与事务间关联规则相结合的方法，分类与事务间 关联规则相结合的方法，马尔可夫过程1 6 j 与事务间关联规则相结合的方法。以上方法都 是以提高算法的执行效率为目的。大部分方法都是按照归类的思想对可能存在相似兴趣 的用户行为进行归类，并从这些用户中寻找出数据间的相关联系。当有新成员加入时， 可利用此模型来进行判断，分析该用户应属于哪一个类，并对同类的用户做出相应的推 荐。 数据挖掘技术引入国内的时间很晚，w e b 个性化服务的迅猛发展推动了数据挖掘在 本国的研究与应用。1 9 9 3 年国家自然科学基金对数据挖掘领域的研究项目首次给予支 持。随后，中科院、清华大学、大连理工大学、浙江大学等多家科研机构都对数据挖掘 进行了深入与广泛的研究。 2 辽宁师范大学硕士学位论文 1 3 现有算法存在的问题 对于用户兴趣行为的预测方法有好多种，本文提出了基于聚类分析的事务间关联规 则挖掘和基于聚类的事务间关联规则双策略分析两种算法。 事务间关联规则是对多维空间进行跨事务的处理方式，因此提高数据的挖掘效率变 得十分必要。而目前已有的事务间关联规则算法中数据的处理方式普遍存在以下几个问 题： ( 1 ) 传统算法不易表达用户的兴趣需求。将网页作为事务，网页的每次访问行为 作为项目，这样所得到的结果只是网页间的相互联系。而用户才是一切网络活动的中心； 因此，这种以网页为中心的传统算法不利于表达用户的兴趣行为。 ( 2 ) 传统算法往往需要通过冗繁的计算才能确定事务间关联规则。这主要是由于， 事务问转换规则不能通过最大频繁项目集来直接获得，常常由事务内关联规则转换而 来，这种转换需要极其繁琐的工作量。 ( 3 ) 事务间关联规则对于数据集的覆盖度较低。虽然事务间关联规则相对于传统 的关联规则预测效率更高，结果更准确。但是，事务问关联规则无法从支持度小于用户 指定最小支持度的数据中挖掘出用户的兴趣需求。所以说，事务间关联规则不能覆盖到 所有的数据集。 针对上述问题，在论文中都给出了相应的解决办法，从而弥补了现有算法的不足i 1 4 本文研究工作及结构安排 本论文的主要工作及创新点是： ： ( 1 ) 用户是网络服务的对象，因此本文提出用户的定义。将数据集中用户的一次 访问行为定义为事务，并将用户每次所浏览的网页定义为项目。改变了传统关联规则将 网页作为事务，网页的每次访问行为作为项目的做法。这种新的定义更容易表达用户的 兴趣需求。 ( 2 ) 提出了基于聚类分析与双策略兴趣模型的w r e b 使用挖掘方法。聚类分析1 7 】去 掉了数据库中大量的无关冗余数据，提高了算法的挖掘效率，但同时也降低了算法的准 确性，遗漏掉用户可能关心的数据。因此本文将聚类分析与双策略兴趣模型相结合，即 利用双策略兴趣分析模型提取出事务间关联规则所能覆盖到的数据，而对那些无法覆盖 到的数据则利用马尔科夫模型进行预测。从而使得初始的大数据库被分成关联库和马尔 库两类库，并利用聚类分析去掉两类库中的无关冗余数据，减小数据集的应用范围，该 方法既改善了算法的准确度又提高了算法的执行效率，达到双赢的效果。 论文共分成五章，结构安排如下： ( 1 ) 第一章绪论，讲述了关联规则的研究背景、国内外的研究现状和现有算法存 在的问题。 、5 每- 番 ”1 *一 w e b 使用挖掘中事务间关联规则方法研究 ( 2 ) 第二章阐述了传统关联规则、事务间关联规则以及聚类分析的相关知识。 进的事务间关联 一章算法的基础 j 关联规则方法。 辽宁师范大学硕士学位论文 2 关联规则及聚类分析的相关概念 2 1 关联规则的相关知识 关联规则【8 】是数据库中发现数据项间相互联系的相关知识。对两个以上变量间存在 的规律，称为关联性。关联规则包括简单关联、因果关联、时序关联等。关联规则的主 要任务是寻找数据库中潜藏的关联网。关联规则挖掘的目的是发现大数据集中频繁项集 之间存在的相关联系。关联规则挖掘具有一定的可信度，可以确定数据库中的关联函数。 关联规则于1 9 9 3 年被a g r a w a l 提出，用于挖掘客户购买数据集中的项集间的关联问题。 目前关联规则挖掘【9 】已经成为诸多学者的研究热点，使得关联规则在原有算法的基础上 进行了改进，极大的提高了算法的挖掘效率。促进了关联规则应用的推广。随后事务间 关联规则挖掘算法于1 9 9 8 年被提出，并成为业界人士的重要研究课题。 给定一个事务数据库d ，关联规则挖掘问题【l o 】实际上是利用用户指定的最小支持度 ( m i ns u p ) 和最小信任度( m i nc o n f ) 发现数据集中有意义的关联规则过程。一般的， 关联规则挖掘问题包括以下两个方面： ( 1 ) 挖掘频繁项目集。利用用户指定的最小支持度挖掘出数据集中所有的频繁项 目集，条件为： s u p p o r t 大于用户指定的最小支持度的项目集。往往这些频繁项目中都 会存在包含关系，但我们只保留那些不被其他频繁项目集所包含的关系，即所谓的频繁 大项目集( f r e q u e n tl a r g ei t e m s e t ) ，频繁大项目集是挖掘关联规则的基础。 ( 2 ) 产生关联规则。计算每个最大频繁项目集的信任度( c o n f i d e n c e ) ，并将之与 用户指定的最小信任度进行比较。若满足信任度大于用户指定的最小信任度时，则产生 关联规则。 关联规则挖掘具有如下特性： ( 1 ) 关联规则中的项目集如果是频繁项目集，则该项目集的所有非空子集都是频 繁项目集。 ( 2 ) 关联规则中的项目集如果是非频繁项目集，则该项目集的所有超集都是非频 繁项目集。 按照不同的情况，关联规则可分为以下几类，如图2 1 所示： w e b 使用挖掘中事务间关联规则方法研究 图2 i 关联规则类型 f i g 2 1 a s s o c i a t i o nr o l et y p e 2 1 1 传统关联规则的基本概念 传统的关联规则通常指的是事务内关联规则( i n t r a - t r a n s a c t i o na s s o c i a t i o nr u l e s ) ，该 规则的定义为：假设卢 乃，厶， 是项的集合。设任务相关的数据d 是数据库事务的集 合，其中每个事务丁是项的集合，使得t 1 。每一个事务有一个标识符，称作t i d 。 设彳是一个项集，事务r 包含彳当且仅当彳丁。关联规则是形如a b 的蕴涵式，其 中ac i ，b c i 且彳f 7b = 矽。规则a 曰在事务集d 中成立，具有支持度s ，其中s 是_ d 中事务包含彳u b ( 即集合彳和b 的并或彳和b 二者) 的百分比。它是概率p ( a u b ) 。 规则aj b 在事务集d 中具有置信度c ，其中c 是d 中包含a 的事务同时也包含b 的 百分比。这是条件概率p ( b i a ) 。即 s u p p o r t ( ajb ) = p ( a u b )( 2 1 ) c o n f i d e n c e ( ajb ) = p ( b i )( 2 2 ) 对同时满足最小支持度( m i n) 和最小信任度 的阈值的关联规则称s u p ( m i n c o n f ) 为强规则( s t r o n g ) 。这些阈值通常由用户或者专家设定。 项集( i t e m s e t ) 为数据项的集合，则驴项集被定义为包含k 个数据项的项集。一个 事务数据库d 中包含项集的事务记录数为该项集的出现频度，也称为该项集的支持度 ( s u p p o r tc o u n t ) 。当一个项集的出现频度大于用户给定的最小支持度与事务数据库d 中记录数的乘积时，该项集为满足最小支持度阈值；而满足最小支持度阈值的记录数称 为最小支持频度( m i n i m u ms u p p o r tc o u n t ) 。同时满足最小支持度阈值的项集称为频繁 卜项集i l l l ( f r e q u e n ti t e m s e t ) 。 关联规则挖掘方法主要通过以下步骤实现： ( 1 ) 挖掘事务数据库d 中的所有频繁项集，根据定义可知，这些项集的频度不小 6 冒雷垦雷蚕雪 i 时，计算机a 一( 丹= 1 ，2 ，f ) 按照第m j 次扫描得到的频繁 项集三珈，和a p r i o r i o e n 函数来生成候选频繁项集g ；当m = - i 时，计算机彳n 先扫描 d b ( a p r i o r i 算法在并行环境下，存储于某台计算机的数据库) 获得频繁l 项集，然 后将三，与其它计算机的频繁l 项集群进行数据交换和合并，生成候选频繁1 项集c 1 ； 扫描d 玩，计算g 在d b n 中的支持数，计算q 一在c m 中的支持数，并连接从其它计 算机q x ( x 胛) 中巳的支持数，累计这些支持数，得到c 肼全局支持数据。计算频繁 m 项集厶，当三朋中元素个数为1 时截止。c d 算法易于实现且速度较快，但产生的候 选频繁项集非常大。 5 f p g r o w t h 算法【1 6 j f p g r o w t h 算法利用分而治之的方法，在数据库第一次扫描时，将数据库中的频繁 项集压缩到频繁模式树( f p t r e e ) 中，然后将f p t r e e 分解成条件库，每个条件库与一 个长度为i 的频繁项集相关，最后对所得到的条件库分别进行挖掘。 2 2 2 事务间关联规则算法 1 e h a p r i o r i 算澍1 7 】 e h a p r i o r i 算法是对a p r i o r i 算法的进一步改进。它利用a p r i o r i 算法挖掘事务间的 频繁项集，并使用哈希技术来提高算法的挖掘效率。该算法的基本思想是：首先利用浏 览数据库计算出事务间候选l 项集，然后将事务问候选2 项集归并到候选1 项集中，并 用所有2 项集构成一个哈希表。哈希表中每个桶的个数代表该桶含有的项集数。当哈希 表中对应的桶值小于m i ns u p 时，就取消一个候选2 项集，因此哈希表可以减少事务问 候选2 项集的数目。 2 f i t i 算法【1 8 1 f i t i 算法是挖掘事务间频繁项集的一个重要算法。该算法所具有的特性为t 令p 是频繁事务间项集，a 。= p ，1 m ，e 。( 刀) p ) ，0 甩( w 一1 ) ，从而对所有的门， 0 翻w ，) 和彳玎均是频繁事务内的项集。f i t i 算法包括以下步骤： ( 1 ) 挖掘和存储初始数据集中的频繁事务内项目集。 ( 2 ) 转换数据集，得到新的数据集。 ( 3 ) 挖掘转换后数据集中的频繁事务间项目集。 2 3 聚类分析的相关概念 聚类【l9 】是人们日常生活中很常见的一种行为方式。在很久以前，人们就会下意识的 利用聚类模式来区分桌子和椅子，苹果和桃子。在这里我们以扑克牌为例，介绍聚类的 基本原理。 辽宁师范大学硕士学位论文 假设有1 6 张扑克牌，将其分成一组一组的过程( 如图2 2 至图2 6 所示) 。 3 o k a 口口口口 口口口口 口口口口 口口口口 图2 2 初始扑克牌牌 f i g 2 2p l a y i n g c a r d s ( 1 ) 分成4 组，每组里花色相同，组与组之间花色相异。 j o k a 图2 3 花色相同的牌为一组 f i g 2 3 i n d i v i d u a ls u i t s 9 w e b 使用挖掘中事务间关联规则方法研究 分成4 组，符合相同的牌为一组。 3 o k 4 图2 4 符号相同的牌为一组 f i g 2 4 l i k ef a c ec a r d s 分成2 组，颜色相同的牌为一组。 3 o k a 图2 5 颜色相同的配对 f i g 2 5 b l a c ka n dr e ds u i t s l o 辽宁师范大学硕士学位论文 ( 4 ) 分成两组，大小程度相近的牌分到一组。 3 o k a 图2 6 大配对和小配对 f i g 2 6m a j o ra n dm i n o r s u i t s 聚类是数据挖掘中一个重要的研究内容，主要用于在潜在的数据中挖掘出有意义的 数据分布。随着信息的飞速发展，聚类已经成为数据挖掘中一个不可缺少的应用技术。 例如，在因特网上，常利用聚类来进行文档的归类和信息的修复；在电子商务上，利用 聚类【2 0 j 提取相似特征的用户，为用户提供更加满意的服务。在生物上，利用聚类对动物 基因和植物基因进行分组，获取种群固有结构的认识和探究。 聚类的主要任务【2 1 1 是通过数据的相似性，将数据分配给不同的数据簇( 类) ，使得 同一个簇的对象之间距离比较近，具有很高的相似性；而不同簇对象之间的距离比较远， 具有很低的相似性。因此，聚类【2 2 】被用作数据挖掘中一种独立工具来获取数据的分布， 也被用作数据挖掘算法中的预处理步骤。 聚类通常用有序对( 彳，s ) 或( 彳，d ) 表示输入，用庐 曰 既：玩 输出数据的分 类结果，并满足以下条件： b | ub 2 u ub k = a ； b ，n b z = 函，f 布。( 2 3 ) 其中a 表示一组样本，s ，d 分别表示样本间的相似度和相异度。历( 卢j ，2 ：七) 是a 的 子集。每一个类召，b 2 ，瞰利用类的中心或类的边界点表示。 聚类分析【2 3 】( c l u s t e r i n ga n a l y s i s ) 的核心是聚类。它应具有以下特性： ( 1 ) 对大型数据集的伸缩能力1 2 4 1 。 聚类算法不但可对在数据集( 少于2 0 0 个数据对象) 中的数据进行聚类分析，也可 以在一个包含数以百万计的大数据库中取得良好的聚类效果。 ( 2 ) 对不同类型属性的处理能力。 聚类算法不但可对数值型的数据进行聚类，也可以对混合型数据，二元型数据以及 1 1 w e b 使用挖掘中事务间关联规则方法研究 其他类型的数据进行聚类。 ( 3 ) 发现任意形状簇的聚类能力。 许多聚类算法是基于欧氏距离来度量数据间的相异性的，此种算法往往倾向于生成 尺度或密度相近的簇。但是，数据集中存在的簇形状可能是任意的，利用聚类算法发现 任意形状簇是十分重要的。 ( 4 ) 对孤立点或噪声的处理能力。 现实生活中的大型数据库中往往会存在一些异常数据，例如不明确数据和噪声数据 等，对无法处理这类数据的聚类算法可能会产生较差的聚类结果。因此，加强聚类算法 对孤立点和噪声的探测和分析能力是数据挖掘中一个具有实际意义的任务。 ( 5 ) 对高维数据的处理能力。 在大型的数据库中可能会含有若干个维或属性的数据。以往的聚类算法都是处理低 维的数据。针对高维数据的聚类算法已经被提出，但是，在高维数据空间中计算算法的 复杂度会很大，而且也存在非常稀疏的数据，使得聚类结果很难保证。研究高维数据空 间的聚类算法具有一定的挑战性。 ( 6 ) 对参数输入顺序的不敏感性。 聚类结果与参数的输入顺序密切相关。同一组参数按不同的输入顺序提交给同一个 算法时，聚类结果差别往往很大。为提高聚类结果的稳定性，设计对参数的输入顺序具 有一定不敏感性的聚类算法是十分必要。 ( 7 ) 可解释性和可实用性。 在许多实际应用中，用户通常希望聚类结果具有可理解性、可解释性以及可实用性。 ( 8 ) 对自定义参数的依赖性。 聚类算法在聚类过程中一般都要求用户输入某些特定的参数，例如产生的聚类簇的 数目等。由于聚类结果与输入的参数具有一定的依赖性；因此，这些参数的选择往往依 赖于经验，参数的细微变化可能会产生不同的聚类结果。因此，参数设置不仅加重了用 户的负担，也降低了聚类结果的稳定性与可靠性。 ( 9 ) 基于一定约束条件的聚类。 在实际应用中，可能需要在某种约束条件之下对数据进行聚类分析。这要求聚类算 法能够在满足某种特定的约束条件，产生良好的聚类结果。 2 4 聚类分析算法 在数据挖掘中，聚类分析是一个十分活跃的应用领域。目前，已经出现了许多有效 的聚类算法，主要的聚类算法可分为划分方法、层次方法、基于模型的方法、基于网络 的方法，基于密度的方法等。 1 划分方法( p a r t i t i o n i n gm e t h o d s ) 2 5 1 1 2 辽宁师范大学硕士学位论文 给定一个包含m 个对象或记录的数据集，划分方法【2 0 】将构造k 个子集。其中每一 个子集就代表一个聚类，足弛而且这k 个子集满足以下条件：每个子集至少包含 一个数据记录；每一个数据记录仅属于一个子集。对于给定的k ，算法创建一个初始 划分，然后利用反复迭代的方法改变划分内容，使得每一次划分都优于前一次。而所谓 的评价准则就是同一个子集中对象彼此相关；不同子集中的对象彼此相异。 2 层次方法( h i e r a r c h i c a lm e t h o d s ) 1 2 6 1 层次方法是对给定的数据对象集按照层次进行分解，直到满足某一终止条件为止。 层次方法可分为“自上而下 和“自下而上 两种类型。自上而下就是从每个对象作为 单独的子集开始，逐步将相邻的子集进行合并，直到所有子集被归并成一个集合或满足 某个终止条件为止。同理，自下而上就是从所有对象构成的一个子集开始，每一次迭代 将其分解为更小的子集，直到每一个子集均由一个对象构成或满足某个终止条件为止。 3 基于模型的方法( m o d e l b a s e dm e t h o d s ) 基于模型的方法给每个聚类假设一个模型，再去寻找符合这个模型的数据集。基于 该模型的聚类算法是由数据点在空间中的密度分布函数来确定的。它具有很强的鲁棒 性，可以自动确定聚类个数。 4 基于网络的方法( g r i d b a s e dm e t h o d s ) 基于网络的方法就是将数据空间分解为有限个单元所组成的网络结构。所有的聚类 操作均是以单个的单元为对象。该方法的优点在于处理速度快，处理时间与数据对象的 个数无关，只与数据空间的网络数相关。 5 基于密度的方法( d e n s i t y b a s e dm e t h o d s ) 1 2 7 1 鼍一一 基于密度的方法就是通过不断扩充聚类的范围直到某个区域中的点的密度小于所 给定的阈值为止。这种方法消除了数据集中大量的无关冗余噪声，以及有利于发现具有 任意形状的聚类。 2 5 本章小结 本章对关联规则和聚类分析中的主要技术以及相关算法进行了概述，并作为整个论 文的核心基础。下面的第三章和第四章，主要针对当前事务间关联规则所存在的不足进 行了改进，提出了两种新的事务间关联规则挖掘算法。 w e b 使用挖掘中事务间关联规则方法研究 3 基于聚类分析的事务间关联规则挖掘算法 近年来，随着用户对w e b 使用挖掘方法精度与准确度要求的提高，大量的挖掘方 法不断涌现。其中关联规则是w e b 使用挖掘中的挖掘方法之一。它包含事务内关联规 则和事务间关联规则【2 8 】。传统的关联规则挖掘方法都是基于事务内的关联规则，只是从 用户访问的网页出发，寻找网页间的关联关系，没有充分的考虑到用户。事务问关联规 则打破了事务的限制，在不同事务各个项目之间发现用户的关联规则【2 9 1 。合理的预测了 用户感兴趣的网页，对用户想要浏览的网页能够给予范围更广、准确性更高的预测。 但对于大型事务数据库进行分析时，单一的采用事务间的关联规则挖掘方法会比较 复杂。由于数据项集巨大，进行一次数据挖掘的时间会很长，规则会很多，从而使挖掘 的效率大大降低。实际上，用户所关心的数据具有某些相似性。可根据这些数据的相似 性将用户进行分类，使得同一类内的用户具有相似的行为特征，不同类间的用户具有相 异的行为特征【3 0 】。本文深入的研究了以往直接利用最大频繁项目集挖掘事务间的关联规 则方法，在数据挖掘时，传统的事务间关联规则方法是在原数据库的基础上进行关联分 析，当数据库中数据较大或支持度、信任度阈值较低时需要耗费很长的时间寻找用户之 间的关联关系，导致算法的效率不高。因此针对上述算法的不足，本文提出了基于聚类 分析的事务间关联规则挖掘算法，简称聚间关联规则( c a i a r ) 。该方法缩小了事务间 关联分析过程中所涉及到的数据量，节省了数据库的扫描时间，进而改善了数据库的挖 掘质量。 3 1 相关定义 定义1 聚类( c l u s t e r i n g ) 给定一个有刀个对象的数据集，聚类分析方法将数据集构造为k 个划分，每一个划 分代表一个簇，七翻。使得同一个簇内的数据对象彼此相似，而不同簇中的数据对象 彼此相异。也就是说，它将数据划分为k 个簇，而且这k 个划分满足如下条件： ( 1 ) 每一个簇至少包含一个对象。 ( 2 ) 每一个对象属于且仅属于一个簇。 定义2 欧式距离( e u c l i d e a nd i s t a n c e ) r 一 d = 2 ( f 雎一f 业) 2 ( 3 1 ) yk = l 欧氏距离是聚类中一种最常用的统计度量，由原始数据计算得到。聚类时，将比较 相似的项目归为一类，不太相似的项目归属于不同的类。 定义3 标准测度函数( s t a n d a r dm e a s u r ef u n c t i o n ) 1 4 辽宁师范大学硕士学位论文 e = 艺卜刁 扣“， ( 3 2 ) 即e 是数据库所有对象的平方误差的总和。其中f 是数据库中给定的数据对象，f 是簇c ， 的平均值。这个准则可以保证生成的结果簇尽可能的紧凑和独立。 定义4 事务间关联规则( i n t e r t r a n s a c t i o na s s o c i a t i o nr u l e s ) 如果一个关联规则满足： ( 1 ) a ，b ，彳n b 矿 ( 2 ) 存在e 。( 0 ) 彳，l f “ ( 3 ) 存在q ( ) b ，1 f “，_ ，0 ( 4 ) 口= 盯( 彳ub ) 仃( 彳) m i n c o n f ( 3 3 ) 则称此关联规则为事务间关联规则。 定义5 共有用户集( c u i ) 共有用户集是通过事务间关联规则方法得到的最大频繁项目集中各项目在数据库 中都出现过的事务t i d 集合。 。 定义6 滑动窗口( s l i d i n gw i n d o w ) 滑动窗口w 由k 个连续的基本窗i = l 构成，肛 w ，w ：，w 。 ，k 值固定。随着数据流 的不断到达，不断有新的基本窗口进入滑动窗口，同时最旧的基本窗口退出滑动窗口。 即滑动窗口总是由最新的k 个基本窗口构成。 3 2 基本原理 在对数据集进行事务间的关联分析之前，先对规模庞大的初始数据集进行聚类分 析，使得数据集按照相似程度进行划分，将最有可能产生关联规则的项目指派到一个簇 中，从而同一类簇中的项目之间尽可能的“接近 或相关，不同类簇中的项目之间尽可 能的“远离或不同。通过以上步骤可将初始数据集划分为若干个较小的数据集，然 后对聚类分析得到各个小数据集所对应的数据库，分别进行事务间的关联分析。聚间关 联规则极大的改进了以往的事务间关联规则方法，有效的提高了数据的挖掘质量。聚间 关联规则算法的基本流程，如图3 1 所示。 w e b 使用挖掘中事务间关联规则方法研究 辽宁师范大学硕士学位论文 算法的运行效率。 算法一：聚类预处理 用户