（计算机应用技术专业论文）基于数组的关联规则挖掘算法的改进研究.pdf

太原理工大学硕士研究生学位论文 基于数组的关联规则挖掘算法的改进研究 摘要 数据挖掘技术从一开始就是面向应用的，使用数据挖掘工具进行数据 分析可以方便地获得重要的数据模式并应用于决策。关联规则挖掘作为数 据挖掘的重要技术广泛应用于各大领域，特别是商业领域。随着数据集的 大小和复杂度的增长，研究高效的关联规则挖掘算法，并增强其对不同数 据集的适应性显得十分重要。 关联规则挖掘是发现存在于数据集中的项目或属性间的关联关系。关 联规则挖掘算法分两步实现，首先挖掘得到频繁项目集集合，然后根据频 繁项目集集合得到强关联规则。a p r i o r i 算法是经典的生成频繁项目集的关 联规则挖掘算法。随后，在基于a p r i o r i 算法的基础上提出了很多变体，不 同的变体侧重于不同的改进方向。基于数组的关联规则挖掘算法，就是利 用数组的结构特性提高了算法的挖掘效率。 针对关联规则挖掘中，模式计数代价太高、i o 效率低下等问题，本文 在详细分析a p r i o r i 算法的基础上，研究了基于数组的关联规则挖掘算法， 针对算法中存在的问题：数组中存在大量的无价值元素、大量候选项集的 产生，提出一种新的改进算法，该算法通过数据约束，仅生成用户感兴趣 的频繁模式，有效地减少了模式计数代价，提高了挖掘质量，同时通过对 算法采用数组压缩、改进连接步等方法进行改进，使得在每次数组扫描过 程中都能生成不同长度的频繁模式集，能够在较少的数组扫描次数中挖掘 出全部的频繁模式集，这对于提高关联规则挖掘的效率和质量，具有重要的 理论和实际意义。 在上述研究成果的基础上，以d e l p h l 7 0 和s o ls e r v e r 2 0 0 0 作为开 发工具，设计与实现了基于数组的关联规则挖掘算法和改进算法的挖掘系 统，系统使用的数据集为i b m 数据生成器生成的5 0 0 0 条试验数据。论文中 给出了该系统的流程图，详细介绍了系统的运行过程，系统运行结果表明， 改进后的算法是可行的、有价值的。最后，分析了有待继续深入研究的问 题和进一步拓展的方向。 太原理工大学硕士研究生学位论文 关键词：关联规则，数据挖掘，a p r i o r i 算法，频繁项集，数组 太原理工大学硕士研究生学位论文 t h ei m p r o v e m e n ta n dr e s e a r c hf o r a r ra y - b a s e da s s o c r 1 0 nr u l em i n i n g a l g o r i t h m a b s l r a c t d a t am i n i n ge s s e n t i a l l ya i m sa ta p p l i c a t i o n sf r o mt h eb e g i n n i n g d a t a m i n i n gt o o l sp e r f o r md a t aa n a l y s i sa n dm a yu n c o v e ri m p o r t a n td a t ap a t t e r n s ， c o n t r i b u t i n gg r e a t l yt os t r a t e g i e s a s a ni m p o r t a n tt e c h n o l o g yo fd a t am i n i n g ， a s s o c i a t i o nr u l em i n i n gh a sb e e na p p l i e dg r e a t l yt ov a r i o u sf i e l d s ，e s p e c i a l l y b u s i n e s sf i e l d a st h eg r o w t ho ft h ed a t as e t s s i z ea n dc o m p l e x i t y , i ti sc r u c i a l f o ru st os t u d yt h ea s s o c i a t i o nr u l e m i n i n ga l g o r i t h m t oe n s u r es y s t e m s h i g h - p e r f o r m a n c ea n ds t r o n ga p p l i c a b i l i t yt od a t as e t s a s s o c i a t i o nr u l em i n i n gf i n d st h er e l a t i o na m o n ga l lt h ei t e m so rt h e a t t r i b u t e si nt h ed a t a s e t a s s o c i a t i o nr u l em i n i n gi sat w o s t e pp r o c e s s f i n da l l f r e q u e n t i t e m s e t sa tf i r s t t h e ng e n e r a t es t r o n ga s s o c i a t i o nr u l e sf r o mt h e f r e q u e n ti t e m s e t s t h ef a m o u sa l g o r i t h mt of i n dt h ef r e q u e n ti t e m s e t si sa p r i o r i l a t e r , m a n yv a r i a t i o n so ft h e s ea l g o r i t h m sh a v eb e e np r o p s e dt h a tf o c u so n i m p r o v i n gv a r i o u sq u e s t i o n s t h em i n i n ga l g o r i t h mo fa s s o c i a t i o nr u l eb a s e do n a r r a ya d o p t s t h ep r o p e r t yo fa r r a yt oe n h a n c et h ee f f i c i e n c yo ft h em i n i n g a l g o r i t h m c o n c e r n i n gw i t hs o m ew e a k n e s si na s s o c i a t i o nr u l e sm i n i n g ，s u c ha sh i g h c o s to fm o d ec o u n t i n ga n di n e f f i c i e n ti 0 ，t h i sp a p e rh a sa n a l y z e da p r i o r i a l g o r i t h m i nd e t a i la n dm a d eal o tr e s e a r c ho nt h em i n i n ga l g o r i t h mo f a s s o c i a t i o nr u l eb a s e do na r r a y f o rt h ep r o b l e m so ft h ea l g o r i t h m ：ag r e a td e a lo f u s e l e s se l e m e n t si nt h ea r r a ya n dm a n yc a n d i d a t ei t e m s e t s ，t h ea u t h o rp r o p o s e s o n ei m p r o v e da l g o r i t h m t h ea l g o r i t h mu s e sd a t ac o n s t r a i n ta n db u i l d so n l yt h e f r e q u e n t i t e m s e t sw h i c hu s e ri si n t e r e s t e di n t h ea l g o r i t h m c a nr e d u c e m o d e c o u n t i n gc o s ta n di m p r o v em i n i n gq u a l i t y i nf a c tt h ea u t h o rm a k e ss o m e l ii i m p r o v e m e n ti ns o m ew a y sa b o u tr e d u c i n gt h en u m b e ro ft r a n s a c t i o n si na r r a y a n dt h ei m p r o v e m e n to fi o i nt om a k ec a n d i d a t ei t e m s e t sw i t hd i f f e r e n tl e n g t hi n e v e r ya r r a ys c a n n i n gt i m e t h e n ，t h ee n t i r ef r e q u e n ti t e m s e t sa r ed i g g e do u ti n l e s ss c a n n i n gt i m e s i ti si m p o r t a n ta n ds i g n i f i c a n tt oe n h a n c et h ee f f i c i e n c ya n d q u a l i t yo fa s s o c i a t i o nr u l e sm i n i n g w i t ht h eb a s eo fa l lt h er e s e a r c h ，t h ea u t h o rd e s i g n st h em i n i n ga l g o r i t h mo f a s s o c i a t i o nr u l eb a s e do na r r a ya n dt h ei m p r o v e da l g o r i t h ms y s t e mw i t h d e l p h l 7 0a n ds o ls e r v e r 2 0 0 0a sd e v e l o p i n gt o o l s i ta d o p t s5 0 0 0t e s td a t a s w h i c hi b md a t ag e n e r a t o rp r o d u c e s i nt h et h e s i s ，t h ea u t h o rg i v e st h ef l o w c h a r ta n dd e s c r i b e st h er u n n i n gp r o c e s so ft h es y s t e mi nd e t a i l ，f u r t h e rm o r e ，t h e e x p e r i m e n tr e s u l t s s h o wt h a ti t sf e a s i b l ea n dv a l u a b l eo ft h ei m p r o v e d a l g o r i t h m f i n a l l y , t h ea u t h o ra n a l y z e st h ep r o b l e m st ob ec o n t i n u e dt or e s e a r c h a n dt h en e x td e v e l o p i n gd i r e c t i o ni nt h i sf i e l d k e yw o r d s ：a s s o c i a t i o nr u l e ，d a t am i n i n g ，a p r i o r ia l g o r i t h m ，f r e q u e n ti t e m s e t ， a r r a y i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：戤二毖 日期： 塑! 窒! 篁! 篮 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签 名- ：! e 墅邀二毖 日期：型坠篁：丛 导师繇避 嗽幽墨丛 太原理工大学硕士研究生学位论文 1 1 数据挖掘简介 第一章绪论 随着计算机硬件技术稳定的进步，高性能的计算机，数据采集设备和存储介质变得 越来越容易获得。在此基础上，数据库、数据仓库技术迅速发展，并广泛应用于各领域， 大批量数据的存储成为可能。数据的丰富带来了对强有力的数据分析工具的需求，人们 已不满足于使用这些数据完成简单的日常事务处理，决策层希望能从这些数据获得更有 价值的信息。因此，研究数据内部特征成为一门新的课题，数据挖掘就是在这样的背景 下成为一门新兴的学科。 1 1 i 数据挖掘的定义及过程 数据挖掘，顾名思义就是从大量的数据中挖掘出有用的信息，即从大量的、不完全 的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律性的、人们事先未知 的，但是又潜在有用的并且最终可理解的信息和知识的非平凡过程【1 1 。原始数据可以是 结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚 至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的； 可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策 支持、过程控制等，还可以用于数据自身的维护。发现的知识可以表示为概念、规则、 规律、模式等形式，是当今数据库和人工智能相互结合的最前沿和极富应用前景的研究 领域，已引起了国内外众多学者和业界的高度重视，尤其是数据库、人工智能、数理统 计、可视化、并行计算等方面的学者和工程技术人员，他们对数据挖掘的方法论、理论 和工具开展了广泛深入的研究工作。数据挖掘的实施过程分为：问题理解和提出、数据 准备、数据整理、建立模型、评价和解释。 典型的数据挖掘系统的体系结构如图1 1 所示。下面详细介绍数据挖掘系统的执行 步骤【2 】： 1 整理待挖掘数据。如果数据源为数据库，先要进行数据清理工作，即消除噪声或 不一致数据，然后将多种数据源组合在一起。如果数据源为数据仓库，则不需要进行前 面的数据清理和集成工作。由此得到的数据有时可以直接用于数据挖掘。大多数情况下， 需要针对特定任务，选择与分析任务相关的数据，并通过汇总等操作将数据统一成可挖 太原理工大学硕士研究生学位论文 掘数据。 2 用户通过图形用户界面录入数据挖掘查询语句或者指定特定任务。 3 用户指定兴趣度限制( 如关联分析的支持度、置信度) ，并存入知识库。 4 根据用户录入选择相应的数据挖掘功能模块，使用知识库信息( 如关联分析的支 持度) 指导挖掘过程，在挖掘过程中，用户可以针对挖掘得到的中间结果，由图形用户 界面录入改进的兴趣度限制，重新存入知识库，使用知识库中的新信息重新指导挖掘过 程。数据挖掘功能模块使用数据库服务器或者数据仓库服务器提取整理后的待挖掘数 据。 5 挖掘过程结束后，模式评估模块根据从知识库读取的用户指定的兴趣度限制( 如 关联规则的置信度) 确定有趣模式。 6 将得到的有趣模式以各种可视化方式返回给用户。 数 数 图1 - 1 数据挖掘系统图 f i g u r e1 - 1t h es y s t e mo fd a t am i n i n g 根据数据挖掘系统与数据库或数据仓库的藕合程度，可以将数据挖掘系统分为不藕 合、松散藕合、半紧密藕合和紧密藕合4 种结构。 不藕合是指数据挖掘系统不利用数据库或数据仓库系统的任何功能。它可能由特定 的源( 如文件系统) 提取数据，使用某些数据挖掘算法处理数据，然后将挖掘结果存放到 另个义件中。这种系统虽然结构简单，但有不少缺点。因此，不藕合是一种很糟糕的 设计。 太原理工大学硕士研究生学位论文 松散藕合是指数据挖掘系统将使用数据库或数据仓库系统中的某些工具进行数据 挖掘，然后将挖掘的结果存放到文件、数据库或数据仓库中。松散藕合比不藕合好，然 而，许多松散藕合的系统是基于内存的，挖掘本身不使用数据库或数据仓库提供的数据 结构或查询优化方法，对于海量数据集，该系统很难获得可伸缩性和良好的性能。 半紧密藕合是指除了将数据挖掘系统连接到一个数据库或数据仓库系统之外，一些 基本数据挖掘原语还可以在数据库或数据仓库系统中实现。在该系统中，中间挖掘结果 要么预计算，要么可以有效地计算，这种设计将提高数据挖掘系统的性能。 紧密藕合系统是指数据挖掘系统平滑地集成到数据库或数据仓库系统中。数据挖掘 子系统被视为信息系统的一个部分。这种结构是高度期望的，但其实现并非易事，许多 问题还有待于进一步研究。 1 1 2 数据挖掘的分类 数据挖掘可以从很多不同的角度进行分类【3 j ： 1 根据挖掘的数据库类型分为：关系( r e l a t i o n a l ) 数据库挖掘、空间( s p a t i a l ) 数据库 挖掘、时态( t e m p o r a l ) 数据库挖掘、面向对象( o b j e c t i v e o r i e n t e d ) 数据库挖掘、事务 ( t r a n s a c t i o n a l ) 数据库挖掘、演绎( d e d u c t i v e ) 数据库挖掘、异质( h e t e r o g e n e o u s ) 数据库 挖掘、多媒体( m u l t i m e d i a ) 数据库挖掘和i n t e m e t 信息库挖掘。 2 根据发现知识的种类不同可分为：分类( c l a s s i f i c a t i o n ) 规则挖掘、聚类( c l u s t e r i n g ) 规则挖掘、关联( a s s o c i a t i o n ) 规则挖掘、特征( c h a r a c t e r i z a t i o n ) 规则挖掘、区分 ( d i s c r i m i n a t i o n ) 规则挖掘、总结( s u m m a r i z a t i o n ) 规则挖掘、偏差( d e v i a t i o n ) 规则挖掘、 模式分析( p a u e ma n a l y s i s ) 及趋势分析( t e n da n a l y s i s ) 挖掘。而按知识的抽象层次可分为 原始级( p r i m i t i v el e v e l ) 知识、高层次( 碰g hl e v e l ) 知识、多层次( m u l t i p l el e v e l ) 知识， 一个灵活的规则挖掘系统能在多个层次上发现知识。 3 根据挖掘使用技术的不同可分为：决策树、贝叶斯网络( b a y e s i a nb e l i e f n e t w o r k s ) 、模糊集、粗糙集、遗传算法和概念格。 4 根据应用分为：电信、金融、d n a 、股票和超市等。 5 根据挖掘途径分为基于归纳的挖掘、基于模式的挖掘、基于统计和数字理论的挖 掘及集成挖掘等。根据挖掘方法的驱动类型分为自发知识挖掘、数据驱动挖掘、查询驱 动挖掘和交互式数据挖掘。 3 太原理工大学硕士研究生学位论文 1 1 3 数据挖掘的应用 数据挖掘技术从一开始就是面向应用的。目前，在很多领域，数据挖掘( d a t am i n i n g ) 都是一个很时髦的词，尤其是在如银行、电信、保险、交通、零售( 如超级市场) 等商业 领域。数据挖掘所能解决的典型商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户 群体划分( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) ，背景分析( p r o f i l ea n a l y s i s ) 、交叉销 售( c r o s s s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u r na n a l y s i s ) 、客户信用记 分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等等，它在网络中的应用也已成为一个 热点。在电子商务方面，从服务器以及浏览器端的日志记录中自动发现隐藏在数据中的 模式信息，了解系统的访问模式以及用户的行为模式，作出预测性分析；在网站设计方 面，通过对网站内容的挖掘，可以有效地组织网站信息，例如采用自动归类技术实现网站 信息的层次性组织，通过对用户访问日志记录信息的挖掘，把握用户的兴趣，有助于开展 网站信息推送服务以及个人信息的定制服务；在搜索引擎的使用方面，其数据挖掘的最 大特色体现在网页内容挖掘，可以实现对网页的聚类、分类，实现网络信息的分类浏览 与检索；通过用户所使用的提问式的历史记录的分析，可以有效地进行提问扩展，提高 用户的检索效果；运用网络内容挖掘技术改进关键词加权算法，提高网络信息的标引准 确度，从而改善检索效果。 下面列出几个具体应用实例【4 l ： 1 欺诈侦测 a t & t 使用根据数据挖掘开发的系统来侦测盗打国际长途的行为( b r a c h m a n 等， 1 9 9 6 ) 。由h n c 公司开发的f a l c o n 欺诈评估系统用于提示可能存在的盗用信用卡的 交易( b r a c h m a n 等，1 9 9 6 ) 。 个人通讯高级安全( a d v a n c e ds e c u r i t yf o rp e r s o n a lc o m m u n i c a t i o n s ) 欧洲研究组织 已经利用无指导聚类侦测移动电话网络中的欺诈行为。对每个用户，系统储存用户的历 史和使用特征文件，在当前使用与用户的历史情况有明显区别时，怀疑为欺诈行为。 2 商业和金融 美国a u t o t r a d e r c o m 是世界上最大的汽车销售站点，每天都会有大量的用户对网站 上的信息点击，寻求信息，其运用了s a s 软件进行数据挖掘，每天对数掘进行分析， 找出用户的访问模式，对产品的喜欢程度进行判断，并设特定服务，取得了成功。 r e u t e r e s 是世界著名的金融信息服务公司，其利用的数据大都是外部的数据，这样 4 太原理工大学硕士研究生学位论文 数据的质量就是公司生存的关键所在，必须从数据中检测出错误的成分。r e u t e r e s 用 s p s s 的数据挖掘工具s p s s c l e m e n t i n e ，建立数据挖掘模型，极大地提高了错误的检测， 保证了信息的正确性和权威性。 b a s se x p o r t 是世界最大的啤酒进出e 1 商之一，在海外8 0 多个市场从事交易，每个 星期传送2 3 0 0 0 份定单，这就需要了解每个客户的习惯，如品牌的喜好等，b a s se x p o r t 用i b m 的i n e e l l i g e n tm i n e r 很好的解决了上述问题。 4 科学应用 ，射线爆是短暂的伽马射线反射，它来源于我们太阳系之外。有关事件的记录己经 超过1 0 0 0 次。科学界普遍认为存在两种y 射线爆。m u k h e r j e e 等( 1 9 9 8 ) 使用统计聚类分 析法发现了第三类，射线爆。 1 1 4 数据挖掘的发展状况 数据挖掘是一门交叉学科，融合了数据库、人工智能、机器学习、统计学等多个领 域的理论和技术。数据挖掘是利用各种分析工具在海量数据中发现模型和数据间关系的 过程，使用这些模型和关系可以进行预测，它帮助决策者寻找数据间潜在的关联，发现 被忽略的因素，因而被认为是解决当今时代所面临的数据爆炸而信息贫乏问题的一种有 效方法。自i b m 公司发布了基于标准的数据挖掘技术i b md b 2 智能挖掘器积分服务， 可用于个性化的解决方案后，两大统计软件公司s a s 和s p s s 也推出了各自的数据挖掘 工具e n t e r p r i s em i n e r l 5 l 和c l e m e n t i n e l 6 1 。自由论坛d me m a i lc l u b 可以通过电子邮件讨 论数据挖掘和知识发现的热点问题。 目前对数据挖掘的研究围绕理论、技术和应用三个方面展开。 理论方面的研究包括：数据和知识的表示，如元数据的表达；文本数据和多媒体数 据的模型构造；知识发现不确定性管理；挖掘结果的评价；数据挖掘的算法复杂性和效 率分析；海量数据集的统计学研究等。 技术方面的研究主要包括数据挖掘方法、数据挖掘算法和数据挖掘过程的研究。目 标是建立完整的数据挖掘理论体系，建立通用、有效的处理模型，用科学的方法论指导 发现知识，使之成为一种主流技术。数据挖掘是从人工智能发展而来，因此人工智能中 的许多技术成果都可以移植到数据挖掘中来。挖掘方法包括分类、聚类、预测和评估、 相关性分析、检索和优化等。数据挖掘算法包括空问数据、文本数据和多媒体数据的数 b 太原理工大学硕士研究生学位论文 据挖掘算法、并行和分布式数据挖掘算法等。数据挖掘过程包括数据预处理技术，如数 据去噪、有效样本选取、数据缩减等，此外还有知识的评估和解释、数据挖掘的可视化 世 号手。 应用研究包括开发各种数据挖掘系统和工具及其在各个行业中的应用。如股票价格 分析与预测，金融风险分析，信用卡欺诈分析，气象预报，生物工程等。 在我国，数据挖掘技术已应用在医学 7 1 、公共安全【8 1 、w e b l 9 1 等不同领域，并取得了 突破性的进展，同时国内研究人员在数据挖掘算法的改进方面也做出了杰出的贡献。 1 1 5 数据挖掘面临的主要问题 目前，数据挖掘面临的主要问题有如下几个方面【1 0 】： 1 挖掘方法和用户交互问题，这反映所挖掘的知识类型、在多粒度上挖掘知识的能 力、领域知识的使用、特定的挖掘和知识显示。由于不同的用户可能对不同类型的知识 感兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，使用背景知识指 导发现过程。并且用户可以和数据挖掘系统交互，以不同的粒度和从不同的角度观察数 据和发现模式，发现的知识应易于理解，能够直接被人们使用。数据挖据中操作者的适 当参与能加速数据挖掘过程。方面，交互界面接收用户的检索、查询要求和数据挖掘 策略，为用户表达要求和策略提供方便；另一方面，交互界面又把生成的结果传递给用 户，由于生成的结果可以是多种多样，所以挖掘系统应该能够准确而直观地描述挖掘结 果和提供友好而高效的用户界面。 2 性能问题，这包括数据挖掘算法的有效性、可伸缩性和并行处理。目前，数据库 的规模呈指数增长。m b 规模的数据库已经很普遍。在商业数据库中，g b 和t b 规模的 数据库也已经在使用，当把w w w 包括进来的时候，p b 规模的数据库正在出现，因此 海量数据挖掘的最大挑战不仅仅在于数据库的绝对规模，还在于数据挖掘系统能够处理 这些持续增长的数据集合。为了有效地从海量数据库中提取信息，数据挖掘算法必须是 有效的和可伸缩的，即对于大型数据库，数据挖掘算法的运行时间必须是可预计的和可 接受的，这是促使开发并行和分布式数据挖掘算法的因素。此外，当数据库更新时不必 重新挖掘全部数据，只要进行知识更新，修正和加强已经发现的知识即可。 3 关于数据库类型的多样性问题，这包括关系的、复杂的数据库处理和异种数据库 之问挖掘信息。目前数据挖掘系统处理的数据库大多是关系数据库。随着数据库应用范 围的同益扩大和规模、功能的同益完善，数据库中将包含大量复杂的数据类型，如复杂 6 太原理工大学硕士研究生学位论文 的数据对象，混合文本，多媒体数据，时空数据，事务数据等，甚至出现新的数据库模 型。由于数据类型的多样性和数据挖掘的目标不同，指望一个系统挖掘所有类型的数据 是不现实的。从具有不同数据语义的结构化的、半结构化的和非结构化的数据源来发现 知识，对数据挖掘提出了巨大挑战。 4 数据挖掘中的隐私保护与信息安全问题。数据挖掘从不同的角度、不同的抽象上 看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网络的日益普及，研究 数据挖掘可能导致的非法数据入侵是实际应用中丞待解决的问题之一。 5 数据挖掘语言的标准化问题。标准的数据挖掘语言或有关方面的标准化工作将有 助于数据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。 6 数据挖掘结果的可用性、确定性、及可表达性问题。所发现的知识需精确地描述 数据库的内容，并对已明确的应用是有用的。非精确的结果需借助于不确定性来表达， 以相似的规则或多个规则来描述。噪声及应去除的数据在数据挖据系统中应仔细处理。 对发现的知识如何表达是一个系统性的研究项目。 以上问题是数据挖掘技术未来发展的主要需求和挑战。在近来的数据挖掘研究和开 发中，一些挑战业已受到一定程度的关注，并考虑到了各种需求，而另一些仍处于研究 阶段。 1 2 问题的提出 关联规则挖掘是数据挖掘研究的一个重要方面。目前，存在大量数据信息，而且正 在迅猛增长，在数字化的时代，如何将这些信息利用起来，使其对今后的生产实践活动 发挥一定的指导意义成为人们越来越关注的问题。面对巨量数据，效率成为数据挖掘的 关键问题所在，所以关联规则的研究也以效率为中心展开了多角度多层面的讨论研究。 最经典的关联规则挖掘算法是a p r i o r i 算法，而且有许多算法都是在a p r i o r i 算法基础上 的变种，如a p r i o r i t i d 算法、a p r i o r i h y b r i d 算法；更新算法是出于交易数据、最小支持 度等挖掘条件的改变而产生的。虽然，a p r i o r i 算法本身已进行了一定的优化，但还是存 在不足，人们为了提高a p r i o r i 算法的效率，对它作了大量的改进。例如，基于散列的方 法、基于事务压缩的方法、基于选样的方法、基于数组的关联规则挖掘算法等，都是对 a p r i o r i 算法的改进，但是改进后的算法依然存在一定的不足。本文针对基于数组的关联 规则挖掘算法存在的缺点：数组中存在大量的无价值元素、大量候选项集的产生，做了 7 太原理工大学硕士研究生学位论文 进一步的优化改进。 1 3 研究背景及意义 随着信息技术的迅猛发展，近年来数据挖掘引起了信息产业界的极大关注，其主要 原因是随着数据库技术的成熟和数据应用的普及，各个领域所积累的数据量正在以指数 速度增长。人们正面临着“数据丰富而知识贫乏”的问题，所以迫切需要一种新的技术 从海量数据中自动、高效地提取所需要的有用知识。数据挖掘技术就是适应这要求迅 速发展起来的种处理数据的新技术，它可以从大型数据库中的海量原始数据中提取人 们感兴趣的、隐含的、尚未被发现的有用的信息和知识。它的发展不仅可以为商务管理、 科学研究、查询优化、过程控制等领域提供决策支持，而且为相关的计算机学科注入新 的活力，从而推进计算机科学向纵深方向发展。毫无疑问，对数据挖掘的深入研究在计 算机理论和应用两个方面都具有十分重大的意义。 关联规则的挖掘是目前数据挖掘领域中研究最为广泛的课题之一。目前己经有许多 学者提出解决挖掘关联规则问题的算法。该问题是1 9 9 3 年i 主t a g r a w a l 等人在对市场购物 篮1 1 1 】问题进行分析时首次提出，用以发现商品销售中的顾客购买模式。自从1 9 9 3 年以来， 数据挖掘领域的研究者在挖掘关联规则上做了大量工作，使之成为一个具有普遍意义和 实用意义的数据挖掘技术。关联规则挖掘可以发现存在于数据库中的项目或属性间的有 趣关系，这些关系是预先未知的和被隐藏的。所发现的关联规则可以辅助人们进行市场 运作、决策支持及商业管理，网站设计等。由于关联规则形式简洁、易于解释和理解并 可以有效的捕捉数据间的重要关系，因此从大型数据库中挖掘关联规则的问题已经成为 近年来数据挖掘研究领域中的一个热点，而且关联规则挖掘可以发现用传统的人工智能 和统计方法所无法发现的规则或规律，因而关联规则挖掘具有重要的研究价值。 1 9 9 3 年a g r a w a l 等人提出的a i s 算法，1 9 9 4 年又提出- t a p r i o r i 算法。a p r i o r i 算法虽然 l 匕a i s 算法产生较少的非相关侯选项目集，但是却耗费了许多搜索数据库的时间。之后 有许多以a p r i o r i 算法为基础的改进算法被陆续提出，女 i s a v a s e r e 等人在1 9 9 5 年提出的 p a r t i t i o n 算法、p a r k 等人在1 9 9 5 年提出的使用哈希技术的d h p 算法、2 0 0 0 年h a n 等人提出 的f p t r e e 算法等都是对a p r i o r i 算法的改进。在上述的这些研究中，为了增加挖掘关联规 则的执行效率，其方法不外是减少非相关项目集的产生，或者是降低搜索数据库的次数， 但相对地增加了在其他方向的时间成本。本课题的研究是在关联规则挖掘算法改进的基 8 太原理工大学硕士研究生学位论文 础上作了进一步的优化，对提高关联规则挖掘算法的效率有着重要的应用价值，推动了 数据挖掘研究工作的进一步发展。 1 4 研究内容 数据挖掘的目标是采用有效的算法，从大量的现有的数据集合中发现并找出最初未 知的，但最终可理解的有用的信息和知识，并用简明的方式表示出来。数据挖掘的目的 是否能够达到，在很大程度上与数据挖掘系统所采用的挖掘算法有关，因此，算法在数 据挖掘中起了至关重要的作用。本文主要是研究数据挖掘中的关联规则挖掘算法的改进 算法，主要工作如下： 1 对数据挖掘和关联规则挖掘技术进行系统研究，包括数据挖掘和关联规则挖掘的 相关术语、定义、分类、应用等，以经典的关联规则挖掘算法呻r i o r i 算法为研究基础， 分析了a p r i o r i 算法的瓶颈问题，详细讨论提高a p r i o r i 算法效率的各种改进算法，客观 分析各种改进算法的优缺点，其中着重分析基于数组的关联规则挖掘算法，详细介绍了 算法的基本思想，算法的运行过程，并通过事例说明算法的运行过程和结果。 2 针对基于数组的关联规则挖掘算法的不足或缺点：数组中存在大量的无价值元 素和大量候选项集的产生，提出四点改进，对改进后的算法作了详细介绍，并通过事例 说明算法的基本思想和算法的运行过程，同时对改进前后算法的运行结果作出比较，证 明改进后的算法是可行的、有价值的。 3 运用基于数组的关联规则挖掘算法和改进后的算法进行实验( 实验使用的数据 源为i b m 数据生成器生成的试验数据) ，得出结论。 1 5 论文组织与安排 论文总共分为五章，具体安排如下： 第一章绪论。介绍数据挖掘的定义、分类、应用以及数据挖掘面临的问题；提出 本文所要研究的问题。 第二章介绍关联规则的相关知识。包括关联规则挖掘的基本概念和基本框架；关 联规则的分类和应用领域，并对关联规则挖掘典型算法进行介绍、分析，其中重点分析 了经典的关联规则挖掘算法一a p r i o “算法。 第三章介绍了几种a p r i o r i 算法的改进算法：基于散列的方法、基于划分的方法、 9 太原理工大学硕士研究生学位论文 基于选样的方法、基于数组的关联规则挖掘算法等，详细介绍和分析了基于数组的关联 规则挖掘算法，并用事例作了说明。 第四章针对基于数组的关联规则挖掘算法的不足，提出改进算法。为了验证改进 后算法的可行性，设计与实现了改进前后两种算法的挖掘系统，并给出系统软件的流程 图，详细介绍了系统的运行过程，最后对实验结果进行对比、分析。 第五章总结已有的研究成果，并分析有待继续深入研究的问题和进一步拓展的方 向。 l0 太原理工大学硕士研究生学位论文 第二章关联规则挖掘弟早大驮舭火i j ，乞村出 数据挖掘已经被认为是数据研究中一个极富应用前景的领域。推动数据挖掘迅速发 展的动力是大型零售组织所面临的决策支持问题，条形码技术的发展使得零售市场能够 收集和存储巨大的零售数据。在事务数据库中挖掘关联规则则是数据挖掘领域中一个非 常重要的研究课题，它是由a g r a w a l 等人首先提出的，关联规则的一个典型例子就是： “9 0 的客户在购买面包的同时也会购买牛奶 ，其直观意义为顾客在购买某些商品的 时候有多大的倾向会购买另外一些商品。 关联规则是数据挖掘的众多知识类型中最为典型的一种。关联规则挖掘可以发现存 在于数据库中的项目( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣关系，这些关系是预先未知的和 被隐藏的，也就是说不能通过数据库的逻辑操作( 如：表的联接) 或统计的方法得出。这 说明它们不是基于数据自身的固有属性( 例如函数依赖关系) ，而是基于数据项目的同时 出现特征，所发现的关联规则可以辅助人们进行市场运作，决策支持及商业管理，网站 设计等。目前，对关联规则的研究主要有以下几个方面：从研究对象上讲有：布尔型数 据挖掘、数值型数据挖掘和模糊数据挖掘。从研究技术上讲有：概念格、云模型、粗糙 集等技术，或将这些技术相结合以有利于提高挖掘效率。从研究内容上讲有：挖掘算法、 更新算法、分布式挖掘、抽样挖掘等几个方面。挖掘算法以支持度、置信度框架为考虑 因素，称为支持度一置信度框架。 2 1 基本概念 2 1 1 项目集的定义及性质 在定义关联规则以前首先介绍频繁项目集( f r e q u e n ti t e m s e t ) 的定义，频繁项目集是 产生关联规则的基础。 1 项目集的定义【1 2 1 设l 为一个由m 个项目组成的集合l = i 1 ，i 2 ，i m ) ，称为项集( i t e m s e t ) 。 则 事务t 为由i 中的项组成的l 的子集，即t i 。项集中所包含的项目数称为项集的长 度。包含k 个项的项集称为k 项集。项集的出现频率是包含项集的事务数，简称为项 集的频率、支持计数和计数，即项集的支持度。 11 太原理工大学硕士研究生学位论文 2 项集的支持度 设x c i 为数据项集，m 为数据库d b 中包含x 的事务的数量，n 为数据库d b h h 包含 的所有事务的数量，则数据项集x 的支持度定义为： s u p p o r t ( x ) = i m ( 2 - 1 ) 项集x 的支持度s u p p o r t ( x ) 描述了项集x 的重要性。如果项集满足最小支持度，则称 它为频繁项集。频繁k 项集的集合通常记做h 。 3 项集的性质 频繁项集具有以下三个性质【1 3 】，性质1 及3 是所有关联规则算法的基础。 性质1 ：子集支持。 设x 和y 是两个不同的项集，如果x c y ，则s u p p o a ( x ) z s u p p o r t ( y ) 。因为d b 中所有支持y 的事务也定支持x 。 性质2 ：非频繁项集的超集也一定是非频繁的。 如果x 在数据库d b 中不满足最小支持度条件，即s u p p o r t ( x ) m i n s u p ，则x 的每 个超集y 也不是频繁的。由性质1 可得s u p p o n ( y ) ss u p p o a ( x ) m i n c o n f 的所有关联规则x j y 。 关联规则中的支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 是两个规则兴趣度的度量，它 们分别反应了所发现规则的有用性( u t i l i t y ) 、确定性( c e r t a i n t y ) 、新颖性( n o v e l t y ) 和简 洁性( s i m p l i c i t y ) 【1 5 1 。 有用性：是定义模式兴趣度的一个重要因素。用一个实用函数( 如支持度) 来评估， 关联模式的支持度是模式为真的任务相关的元组( 或事务) 所占的百分比。同时满足最小 置信度阂值和最小支持度阈值的关联规则，即强关联规则( s t r o n g a s s o c i a t i o nr u l e ) ，认 为是有趣的。具有较低支持度的规则多半是噪声的、少见的或异常的。 确定性：每个发现的模式都应有一个表示其有效性或“值得信赖性”的确定性度量， 这个确定性度量是事务的置信度。 新颖性：新颖的模式是那些提供新信息或提高给定模式集性能的模式。检测新颖性 的另一策略是删除冗余模式。若发现的规则被已在知识库中导出的规则集中的另一规则 所蕴涵，则两个规则都要重新审查，以便去掉潜在的冗余。 简洁性：模式的简洁性的客观度量可以看作为模式结构的函数，用模式的二进位位 数或属性数、或模式中出现的操作符数来定义。 1 3 太原理工大学硕士研究生学位论文 规则长度是一种简洁性的度量，对于用合取范式( 即合取谓词的集合) 表达的规则， 规则的长度也可简单地定义为规则中合取符的个数。关联判别或分类规则的长度超过用 户定义的阈值时，则被认为是不感兴趣的。 2 2 关联规则的问题描述及应注意的问题 关联规则的挖掘问题就是在事务数据库d b 中找出具有用户给定的最小支持度和最 小置信度的关联规则，因此该问题可以分解为如下两个子问题： 1 找出事务数据库d b 中所有大于等于用户指定最小支持度的项目集，即频繁项目 集。 2 由频繁项集产生强关联规则。对每一个