（计算机软件与理论专业论文）基于关联规则挖掘的钻井地质设计系统研究.pdf

摘要 2 0 0 2 年钻井地质设计系统在胜利油田地质录井公司投入使用，该系统提供了数据管 理、数据查询、报告生成等功能，极大地方便了设计人员的地质设计工作。但是，该系 统缺乏决策支持功能，未能很好的利用系统数据库中积累的大量数据。在此次系统升级 中，我们在其中加入数据挖掘功能，对系统中存储的油井复杂情况数据进行关联规则挖 掘。 本课题将关联规则挖掘技术引入油井复杂情况问题的分析中，本文的主要内容如 下： ( 1 ) 介绍了数据挖掘的相关技术，着重研究关联规则挖掘问题，分析了以a p n o f i 算法为代表的逐层迭代算法及其改进算法。 ( 2 ) 介绍了钻井地质设计系统的体系结构、主要功能以及关联规则挖掘功能相关的 数据库结构设计；针对复杂情况数据特点，提出了一种基于向量的a p f i o f i 算法改进， 通过数据集测试，证实了算法改进的正确性和有效性。 ( 3 ) 为系统提供了挖掘各复杂情况之间的关联关系和复杂情况与其发生因素之间的 关联关系两种功能。按照两种挖掘功能的不同要求，对相关数据进行预处理，采用改进 算法对预处理后数据进行关联规则挖掘。实验结果表明，挖掘得到的规则可以为油井设 计工作提供有益的决策支持。 关键词： 数据挖掘关联规则挖掘a p r i o f i 算法复杂情况 a b s t r a c t t h es y s t e mo fd r i l l i n g - g e o l o g yd e s i g nh a sb e e nu s e di ns h e n g l if i e l dg e o l o g i c a ll o g c o m p a n yf r o m2 0 0 2 t h es y s t e mp r o v i d e dp o w e r f u lf u n c t i o n s ，s u c ha sd a t am a n a g e m e n t ，d a t a q u e r ya n dr e p o r tg e n e r a t i n g ，e t c b u tt h es y s t e mh a sn o td e c i s i o ns u p p o r tf u n c t i o n , t h ed a t a a c c u m u l a t ei nd a t a b a s eh a sn o tb e e nf u l l yt a k e na d v a n t a g eo f i nt h es y s t e mu p g r a d e ，w ew i l l a d di nd a t am i n i n gf u n c t i o n ，w h i c hi sa s s o c i a t i o nr u l e sm i n i n gi no i lw e l lc o m p l e xs i t u a t i o n s d a t a t h ep r o j e c ti st oa n a l y s eo i lw e l lc o m p l e xs i t u a t i o n sp r o b l e mb ya s s o c i a t i o nr u l e sm i n i n g ， t h et h e s i sc o n s i s t so ft h r e ep a r t s f i r s t l y , t h i sp a p e ri n t r o d u c e st h er e l a t e dt e c h o n o l o g y , t h et h e o r e t i cb a s i so fd a t am i n i n g a n dt h ee m p h a s i z ea t t a c h e dt oa s s o c i a t i o nr u l e sm i n i n gp r o b l e m ，t h e na p r i o r ia l g o r i t h ma n di t s i m p r o m e n ta l g o r i t h ma r ea n a l y z e ds p e c i f i c a l l y s e c o n d l y , t h i sp a p e ri n t r o d u c e sa r c h i t e c t u r e ，m a j o rf u n c t i o na n dd a t a b a s ep h y s i c a l s t r u c t u r ed e s i g nr e l a t e dt oa s s o c i a t i o nm i n i n gf u n c t i o n a i m i n ga tt h ed a t ac h a r a c t e r i s t i co r c o m p l e xs i t u a t i o n s ，aa p r i o r ia l g o r i t h mi m p r o v e m e n tb a s e do n v e c t o rh a sb e e np r o v i d e ，w h i c h h a sb e e np r o v e dc o r r e c t n e s sa n dv a l i d i t yb yd a t as e tt e s t s f i n a l l y ，t w of u n c t i o n sa r ea d d e dt os y s t e m ，w h i c hi sm i n i n ga s s o c i a t i o n s o fe a c h c o m p l e xs i t u a t i o n sa n da s s o c i a t i o n so fc o m p l e xs i t u a t i o n sw i t ht h e i rf a c t o r s a c c o r d i n gt o v a r i o u sr e q u i r e m e n to ft w of u n c t i o n s ，m ed a t ai ss e p a r a t l yp r e t r e a t m e n t e d t h ei m p r o v e d a l g o r i t h mi su s e dt om i n i n gt h ed a t aa r e rp r e t r e a t m e n t e d ，t h er e s u l ti n d i c a t e st h a ta s s o c i a t i o n r u l eb e e nm i n e dc a np r o v i d eg o o dd e c i s i o ns u p p o r tf o ro i lw e l l sd e s i g n k e y w o r d s ：d 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 g ，a p r i o r ia l g o r i t h m ，c o m p l e xs i t u a t i o n s 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：日期：卯7 年年月e l 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：垂1 醯基： 指导教师签名： 甄变量： 指导教师签名：强叉篡： 日期：筇口7 年4 月石 e 1 日期：矽吖年千月舌e l 中国石油大学( 华东) 硕士学位论文 1 1 研究背景及意义 第一章前言 地质设计是地质录井、编制钻井工程设计、测算钻井工程费用等项工作的基础和依 据，是降低油气勘探开发成本，保护油气层，提高投资效益的基础和关键环节。地质设 计的准确性和及时性与否，将直接影响油气勘探开发的效果和进程。 胜利油田地质录井公司每年承担着近2 0 0 0 多口井的地质设计任务，为了减少设计 人员的重复劳动，提高钻井设计的效率和准确性，开发了钻井地质设计系统。通过几年 使用，系统数据库中积累了大量数据。在原系统中，对这些重要的数据只是做了一些简 单的统计、分析工作，难以取得更加有价值的信息。由此在此次系统的升级中增加数据 挖掘功能，以取得对今后油井设计工作具有重要参考作用的知识。 数据挖掘技术经过十几年的研究与发展，吸收其它许多学科最新研究成果逐渐形成 了自己独特的研究分支，取得了一些发展。但大部分学者仍然认为数据挖掘仍然处于探 索阶段，数据挖据的技术要得到广泛应用还有许多难点亟待解决。目前商家所推出的一 些数据挖掘系统还都是一些通用的辅助开发工具，只能给那些熟悉数据挖掘技术的专家 或高级技术人员使用。 关联规则挖掘是数据挖掘中最活跃的研究方法之一，最早由a g r a w a l 等人针对购物 篮分析( b a s k e ta n a l y s i s ) 问题提出【l 】，其目的是为了发现交易数据库( t r a n s a c t i o n d a t a b a s e ) 中不同商品之间的的联系规则。目前，关联规则挖掘被广泛应用于顾客购物 模式分析、目录设计、商品广告邮寄分析、网络故障点分析、入侵检测、d n a 分析和保 险理赔分析中。 油井复杂情况是石油钻井行业的专业术语，是指在钻井生产活动中，产生的意外的 麻烦或事故【4 3 1 。如果处理方法不当，将造成严重的损失，如何及早发现和预防复杂情况 的产生，是油井设计工作中的一项重要课题。将关联规则挖掘应用于油井复杂情况数据 的分析中，不但可以发现不同复杂情况之间的联系，还可以发现复杂情况与一些其它油 井属性数据之间的关联关系，从而掌握复杂情况的发生规律，及时做出应对，避免或减 小由此造成的损失。将数据挖掘技术引入地质设计系统中，是对数据挖掘应用领域的新 的扩展。 第一章前言 综上所述，将关联规则挖掘应用于钻井地质设计系统的研究具有重要意义。 1 2 国内外研究现状 1 2 1 钻井地质设计系统研究现状 目前胜利油田使用的钻井地质设计系统主要有以下功能：日常测井数据管理，钻井 地质设计数据的自动计算，设计书文本自动编制和排版，坐标井位图、地质预告图、井 身轨迹示意图等的自动绘制等。通过该系统的使用，钻井地质设计已由过去传统的w o r d 文档存储、人工对比和编制设计发展成为拥有地质工作站和大型数据库的计算机网络系 统，具有较高的专业化和自动化的设计体系。 辽河油田的地质设计系统采用的是文本管理的方式，缺少图件绘制、报告自动生成 功能。这样在生成相关报告时，很多表格、图件需要人工绘制后再加入报告中，费时费 力。 但这两地油田地质系统都缺少决策支持功能。库中积累的大量各种类型的数据中蕴 含着丰富的地质信息，是油井设计的主要依据，但由于在大量数据中寻找有用信息的困 难性，这些数据都没有得到很好的利用，造成了数据丰富，而信息匮乏的现象。 1 2 2 关联规则挖掘研究现状 1 9 9 3 年a g r a w a l 等人首先提出了关联规则的问题，并于1 9 9 4 年提出了挖掘关联规则 的经典算法a 面o r i 算法【l 】。a p f i o r i 算法需要多次重复扫描数据库，而且可能产生大量的 侯选项集。为了提高算法挖掘规则的效率，不少学者进行了大量的研究，并对原有的 a p r i o r i 算法进行了优化，如引入了散列方法 2 1 、事务压缩【2 ，3 ，4 】、划分的思想【5 1 、随机采样 【6 】和动态集计数【7 】等。 基于散列的优化方法的基本思想是当扫描数据库中事务，由候选k 一项集产生频繁k 一 项集时，同时产生每个事务的( k 十1 ) 项集，并通过散列函数将它们散列到散列表的不同 桶中，并增加相应桶的计数，对于散列表中对应桶计数小于最小支持度的将它们从候选 k 项集中删除，这样就大大压缩了候选k 一项集( 特别是k = 2 时) 。 事务压缩方法的基本原理就是当一个事务不包含任何长度为k 的频繁项集时，必然 不包含长度为k + 1 的频繁项集。从而就可以将这些事务移去，这样在下一遍的扫描中就 可以减少进行扫描的事务集的个数以提高挖掘的效率。 基于划分的优化方法是先把数据库从逻辑上分成几个互不相交的块，每次单独考虑 一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集， 2 中国石油大学( 华东) 硕士学位论文 最后计算这些项集的支持度。该算法可以高度并行，可以把每一分块分别分配给某一个 处理器生成频集。这样就提供了开发并行数据挖掘程序的良好机制。产生频集的每一个 循环结束后，处理器之间进行通信来产生全局的候选k 项集。 基于采样的优化方法的基本思想是选取给定数据库的随机样本，然后在样本而不是 在原有数据库中搜索频繁项集。这种方法是用牺牲精度的代价来换取有效性，样本的大 小由是否能够把它放入内存来确定。由于搜索的是样本中的频繁项集，所以可能丢失一 些全局的频繁项集，为此使用比事务数据库最小支持度低的支持度值来搜索样本中的频 繁项集，然后通过数据库的其余部分计算它的实际频繁度。这种方法比较适合在效率优 先的情况下使用。 动态集计数的方法将数据库划分为标记开始点的块，它不像a p r i o r i 算法仅在每次完 整扫描数据库之前确定新的候选，而是在任何开始点添加新的候选项集。该技术动态地 评估己被计数的所有项集的支持度。如果一个项集的所有子集已被确定为频繁的，则添 加它作为新的候选项集。该方法扫描数据库的次数l l a p r i o r i 算法要少。 另外，针对a p r i o r i 算法的固有缺陷，产生了一些高性能的频繁集挖掘算法。如 t r e e p r o j e c t i o n 算法【8 】、f p 伊o w 吐1 算法【9 1 、o p p o r t u n e p r o j e c t 算法【1 0 1 、c t - p r o 算法【1 1 1 。其 中，由j i a w e ih a n 等提出的不产生候选挖掘频繁项集的f p 。g r o w t h 算法对不同长度的规则 都有很好的适应性，同时在效率上较之a p r i o r i 算法有较大的提高。另外，一些专家也提 出了挖掘频繁闭合模式和最大频繁模式来减少冗余模式，频繁闭合模式是指不被任何其 他具有相同支持度的频繁模式所包含的频繁模式，而最大频繁模式是指不被任何其他频 繁模式所包含的频繁模式。挖掘频繁闭合模式主要有以下算法：a c l o s e 算法【l 引、 a l t m a x c l o s u r e 算法【1 3 1 、c l o s e t 算法【1 4 1 。还有一些扩展的关联规则问题，如：带约束的 关联规则问题【1 5 】，时序关联规则问题 1 6 】，空间关联规则问题【1 7 】，负关联规则【1 8 】等。 近几年，国内的部分学者对关联规则挖掘进行了大量的研究。中科院计算所的欧阳 为民首先引入国外关联规则挖掘的概念和思想，并在基于a p r i o r i 算法的基础上提出了 时态约束的关联规则【4 l 】。冯玉才、冯剑琳在1 9 9 8 年给出了种关联规则的增量式更新 算法u 9 】，朱明、王俊普、蔡庆生等在2 0 0 0 年给出一种基于s e t r e e 的关联规则挖掘算法 【2 0 1 ，杨学兵、高俊波、蔡庆生等2 0 0 0 年给出一种可增量更新的关联规则挖掘算法口， 左万利、刘居红提出了任意多表间关联规则的并行挖掘方法【2 2 】，周斌、吴泉源、高洪奎 在2 0 0 0 年给出了序列模式挖掘的增量算法的设计原则【2 3 1 。2 0 0 1 年，朱绍文等提出了一 种多概念层数值关联规则挖掘方法【2 4 1 。2 0 0 2 年李学明、张伟等研究关联规则的冗余特 第一章前言 性，给出了改进型关联规则生成算法【2 5 】。2 0 0 3 年黄伟明等提出了基于散列技术和事务 压缩的关联规则挖掘算法1 2 6 ，2 0 0 4 年哀红春、熊范纶提出元规则指导下的逐步求精多 层空间关联规则挖掘算法【2 7 】，2 0 0 5 年陆建江等提出了模糊关联规则的并行挖掘算法【2 引， 2 0 0 6 年刘义安提出了基于向量内积的关联规则挖掘算法【4 2 】等等。 1 3 论文章节安排 全文共分五章节，各个章节的内容安排如下： 第一章介绍了本课题的研究背景和意义，详细介绍了关联规则挖掘的国内外研究现 状。 第二章介绍了论文相关知识。包括：数据挖掘的概念、步骤以及常用技术，详细介 绍了关联规则挖掘相关知识及其经典算法a p r i o r i 算法。 第三章简要介绍了钻井地质设计系统的体系结构及主要功能，详细介绍了关联规则 挖掘相关的数据库结构设计。 第四章探讨了关联规则子系统的结构和主要模块，针对复杂情况数据特点提出了基 于向量的a p r i o r i 算法的改进，通过测试，证实了算法改进的正确性和有效性。 第五章将改进算法应用于油井复杂情况问题的分析中，实现了关联规则挖掘子系统 的两种功能。通过系统应用，挖掘出了具有实际意义的关联规则，并对部分规则进行了 解释。 本章最后总结了论文的主要工作和创新点，并对下一步工作进行了展望。 4 中国石油大学( 华东) 硕士学位论文 2 1 数据挖掘技术 第二章数据挖掘技术 2 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ，d m ) ，就是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的，人们事先不知的，但又是潜在有用的信息和知识的过 程【2 9 - 3 0 】。 数据挖掘是一门来自各种不同领域的研究者共同关注的交叉性学科，受到多个学科 的影响，最主要的学科包括：数据库技术、统计学、人工智能、机器学习、模式识别、 高性能计算、可视化技术、信息科学等。 2 1 2 数据挖掘的步骤 清理与 选择与 数据 觥，r 融，曰三7 lj7 lj 数据库 数据仓库特定数据集模式 知识 图2 - l数据挖掘步骤不恿图 f i 9 2 1 d a t am i n i n gs t e p ss k e t c h 数据挖掘的全过程描述如图2 1 所示，整个数据挖掘过程是由若干挖掘步骤组成的， 主要步骤有【3 1 】： ( 1 ) 数据清洗( d a t ac l e a m i n g ) ，清除数据噪声和与挖掘主题明显无关的数据。 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) ，将来自多数据源中的相关数据组合到一起。 ( 3 ) 数据转换( d a t at r a n s f o r m a t i o n ) ，将数据转换为易于进行数据挖掘的数据存 储形式。 ( 4 ) 数据挖掘( d a t am i n i n g ) ，是知识挖掘的一个基本步骤，其作用是利用智能方 法挖掘数据模式或规律知识。 ( 5 ) 模式评估( p a t t e me v a l u a t i o n ) ，根据一定评估标准从挖掘结果筛选出有意义 的模式知识。 第二章数据挖掘技术 ( 6 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，利用可视化和知识表达技术，向用户展 示所挖掘出的相关知识。 2 1 3 数据挖掘的功能 利用数据挖掘技术可以帮助用户获得决策所需的多种知识。在许多情况下，用户并 不知道数据存在哪些有价值的信息知识，因此对于个数据挖掘系统而言，它应该能够 同时搜索发现多种模式的知识，以满足用户的期望和实际需要。此外数据挖掘系统还应 能够挖掘出多种层次( 抽象水平) 的模式知识。数据挖掘功能以及所能够挖掘的知识类 型如下所述【3 2 刁3 】： ( 1 ) 关联分析 关联分析用于发现大量数据中项集之间有意义的关联或相互关系，寻找给定数据集 中项之间的有趣联系。关联规则的支持度和置信度是两个规则兴趣度度量，他们分别反 映发现规则的有用性和确定性。数据库中的数据一般都存在着关联关系。关联分析模型 的一个典型例子是购物篮分析，通过对顾客购买偏好的分析，确定商品促销的目标客户， 以此来设计各种商品促销的方案，并通过商品购买关联分析的结果，采用交叉销售和向 上销售的方法，挖掘客户的购买力，实现准确的商品促销。 ( 2 ) 分类和回归 分类是在已有数据集的基础上学会一个分类函数或构造一个分类模型，该函数或模 型能够把训练集中的数据记录映射到给定类别中的某一个，从而可以应用于数据预测。 回归则是通过具有已知值的变量来预测其他变量的值。和分类方法不同的是，分类输出 的是离散的类别值，而回归输出的则是连续数值。 ( 3 ) 聚类 聚类就是将数据对象分组成为多个类或簇，划分的原则是在同一个簇中的对象之间 具有较高的相似度，而不同簇中的对象差别较大。聚类增强了人们对客观现实的认识， 是概念描述和偏差分析的先决条件。与分类不同，聚类操作中要划分的类是事先未知的， 类的形成完全是数据驱动的，属于一种无指导的学习方法。 ( 4 ) 孤立点分析 数据库中可能包含一些数据对象与大部分的一般行为或模式不一致，我们称之为孤 立点。大部分数据挖掘方法将孤立点视为噪声或例外丢掉，然而在一些应用如欺诈检测 中，罕见的事件可能比正常出现的事件更有趣，针对孤立点的数据分析称为孤立点挖掘。 ( 5 ) 概念描述 6 中国石油大学( 华东) 硕士学位论文 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述 分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之 间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描 述的方法很多，如决策树方法、遗传算法等。 2 1 4 数据挖掘的常用技术 数据挖掘有如下常用技术 3 4 】【3 9 1 ： ( 1 ) 规则归纳 即通过统计方法归纳、提取有价值的i f - t h e n 规则，规则归纳技术在数据挖掘中被广 泛使用，其中关联规则挖掘的研究开展得较为积极和深入。 ( 2 ) 决策树 该方法用树形结构表示决策集合，由决策集合通过对数据集的分类产生规则。决策 树方法是利用信息熵寻找数据库中具有最大信息量的字段，建立决策树的一个结点。再 根据字段的不同取值建立树的分支：在每个分支子集中，重复建立树的下层结点和分支， 最终形成决策树。典型算法是由q u i u l a n 提出的i d 3 方法，典型的应用是对分类规则的挖 掘。 ( 3 ) 神经网络 神经网络是一种新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建 立的一种计算模型。其特点是利用大量简单的计算单元连成网络，来实现大规模并行计 算。神经网络建立在自学习的数学模型基础之上，它可以对大量复杂的数据进行分析， 并可以完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。 神经网络近来越来越受到人们的关注，因为它为解决大复杂度问题提供了一种相对 来说比较有效的简单方法。神经网络常用于两类问题：分类和回归。 ( 4 ) 遗传算法 这是一种模拟生物进化过程的算法。它是基于群体的、具有随机和定向搜索特征的 迭代过程，这些过程有基因组合、交叉、变异和自然选择四种典型操作。如何把数据挖 掘任务表达为一种搜索问题是遗传算法的应用关键。 ( 5 ) 模糊技术 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分 析。模糊性是客观存在的，系统的复杂性越高，模糊性越强。模糊集理论用隶属度来刻 画模糊事物的亦此亦彼性，而李德毅教授在传统模糊集理论和概率统计的基础上提出了 7 第二章数据挖掘技术 定性定量不确定性转换模型云模型，并形成了云理论。云模型用期望值、熵和超熵 表达定性概念。将概念的模糊性和随机性结合在一起。为数据挖掘提供了概念和知识表 达、定性定量转换、概念的综合和分解等新方法。 ( 6 ) 粗集方法 这是一种全新的数据分析方法，近年来在机器学习和i 是有r r l 个项目组成的集合。给定一个事务数据库d ，其中每个 事务t 是i 中一组项目的集合，最 1 t c _ i ，每一个事务有一个标识符，称作t i d 。设a ，b 是 项集，关联规则挖掘是形女t l a = b 的蕴涵式，其中a _ c l ，b _ e l ，并且a n b = o 。 一般用支持度和置信度两个参数来描述关联规则的属性3 2 】： ( 1 ) 支持度( s u p p o r t ) 设d 中有的s 事务同时支持项集a 和b ，s 称为关联规贝i j a = b 的支持度，记为 s u p p o r t ( a = b ) 。支持度描述了a 和b 这两个项集的并集在所有的事务中出现的概率 p ( a u b ) ，即 s u p p o r t ( a = b ) 2p ( a ub ) ( 2 ) 置信度( c o n f i d e n c e ) 设d 中支持项集a m 事务中，有c 的事务同时也支持项集b ，c 称为关联规贝i j a = b 的置信度。简单地说，置信度就是指在出现了a 的事务t 中， b 也同时出现的概率有多 大，这是条件概率p ( b i a ) 。它反映了关联规则的最低可靠度，- 记3 - , j c o n i i d e n c e ( a = b ) ， 即 c o n f i d e n c e ( a = b ) 2p ( bi a ) 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数 据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说只有置信度和可信 度都较高的关联规则才可能是用户感兴趣、有用的关联规则。支持度和置信度能比较直 9 第二章数据挖掘技术 接地形容关联规则的性质。 ( 3 ) 包含k 个项的项集称为k - 项集。 ( 4 ) 项集的出现频率是包含项集的事务数，简称为项集的频率或支持度计数，记作 s u p p o r tc o u n t ( a ) 。 ( 5 ) 如果项目集在事务数据库中的支持度不小于用户给定的最小支持度阈值，那么 称项集为大项目集或频繁项集，反之称为小项目集或非频繁项目集。 ( 6 ) 在频繁项目集中所有不被其他元素包含的频繁项目集称为最大频繁项目集或最 大大项目集。 ( 7 ) 强关联规则。同时满足最小支持度阈值( m i n s u p p o r t ) 和最小置信度阈值( m i n c o n f i d e n c e ) 的关联规则称为强关联规则。最小支持度表示了一组事务集在统计意义上的需满 足的最低程度，它说明了规则的普遍性。最小置信度反映了关联规则的最低可靠度，它 说明了规则的有效性。给定一个事物数据库，挖掘关联规则的问题就是产生支持度和置 信度分别大于用户给定的最小支持度和最小置信度的关联规则。 2 2 2 关联规则的分类 根据不同的分类原则，可以将关联规则进行如下分类【3 0 】【3 5 】。 ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间关系；而数值型关联 规则可以和多维关联或多层关联规则结合起来，对数值字段进行处理，将其进行动态的 分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如：该井出现h 2 s 复杂情况= 该井出现s 0 2 复杂情况，是布尔型关联规则； 水温 1 0 0 0 _ 水沸腾，是数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同层次的；在多层 的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= l e g e n d 打印机，是个单层关联规则； 台式机= l e g e n d 打印机，是一个在较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维的关联规则中，只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中， 要处理的数据将会涉及多个维。换句话说，单维关联规则是处理单个属性中的关系；多 维关联规则是处理多个属性之间的关系。 1 0 中国石油大学( 华东) 硕士学位论文 例如：井涌_ 井喷，这条规则只涉及到油井发生的复杂情况属性，是单维关联规则； 地层压力= “高 _ 复杂情况= “井涌 ，这条规则就涉及到两个字段的信息，是两 个维度上的关联规则。 ( 4 ) 基于规则中涉及的数据的确定性，关联规则可以分为确定的和模糊的。在确 定的关联规则中，涉及的数据是确定的。例如：年龄= 2 0 ，月收入= 5 0 0 0 。然而，这种确 定型的数据在描述客观事务时却有机械性的缺陷；另一方面，也不符合人类认识事物由 粗及细，由表至里的认识规律。于是可以采用模糊概念来表述关联规则的模糊关联。 例如：a v g ( 收入) 4 8 0 0 _ b u y ( 购买) 单价为4 0 0 0 的房屋，涉及的收入是确定的数值， 因此这是一个确定型关联规则； a v g ( 收入) 高收入_ b u y ( 购买) 单价较高的房屋，涉及的收入和房屋单价为模糊值， 是一个模糊关联规则。 2 2 3 关联规则挖掘步骤 给定数据库d ，关联规则的挖掘就是找出所有存在于数据库中的强关联规则。因此， 整个关联规则挖掘过程可以分解为以下几步： ( 1 ) 选择要挖掘的数据，对原始数据按具体要求进行预处理。 ( 2 ) 找出频繁项目集。 通过用户指定的最小支持度，寻找所有频繁项目集，即满足s u p p o r t 不小于m i n s u p p o r t 的所有项目集。发现所有频繁项目集是形成关联规则的基础，是关联规则挖掘的中心问 题。 ( 3 ) 由频繁项集生成关联规则。 在得到的频繁项集中，找出c o n f i d e n c e 不小于m i n c o n f i d e n c e 的关联规则，形成规则 集。 ( 4 ) 用自然语言解释并输出规则集。 这里的第三步由频繁项集生成关联规则步比较简单，而且在内存、i o 以及算法 效率上改进余地不大。因此，寻找频繁项集一步是关联规则挖掘算法研究的重点。 关联规则的基本流程如图2 2 所示 第二章数据挖掘技术 日i 寻找频繁项集1 日i 生成强规则1 日l 规则集ri l _ _ _ jl _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ j - 。o 。一 0 最小支持度但小置信度o 图2 - 2 关联规则挖掘流程图 f i 醇一2 a s o c i a t i o nr u l em i n i n gf l o wc h a r t 2 2 4 a p r i o r i 算法 a g r a w a l 等人提出了经典的频繁项目集生成算法一a p r i o r i 算法，其核心思想至今 仍被很多算法采用，本节将对该算法做详细介绍。 ( 1 ) a p r i o r i 算法 a p r i o r i 算法使用逐层搜索的迭代方法，k 项集用于探索( k + 1 ) - 项集，k - 项集记做l k ， 由l k 自己连接产生候选k 项集，记做c k 。其算法流程如图2 - 3 所示： 1 2 中国石油大学( 华东) 硕士学位论文 获得最小支持度 上 获得l l i ik = 1 0 臣囝 上 图2 - 3a p r i o r i 算法流程图 f i 9 2 3a p r i o r ia l g o r i t h mf l o wc h a r t a p r i o r i 算法利用a p r i o r i 性质减小生成频繁项集时的搜索空间，提高挖掘算法的效 率。a p r i o r i 性质【3 7 】如下： 性质1 如果项目集x 是频繁项目集，那么它的所有非空子集都是频繁项目集。 性质2 如果项目集x 不是频繁项目集，那么它的所有超集都不是频繁项目集。 如图2 3 所示，在由l k 生成l k + l 过程中，需要用到连接和剪枝【3 6 】。 第一步，连接步。 长度为k 的频繁项目集集合l k 做自连接生成候选( k + 1 ) 项集的集合，该候选项集的集 合记作c k + l 。设1 1 和1 2 是l k d p 的项集。记号l i d 标示l j 的第j 项，假定项集中的项按字典次 序排放。如果l l 和1 2 的前k 1 项相同，就说l l 和1 2 是可连接的。连接后的结果项集是 9 中 第二章数据挖掘技术 l l 1 l l 2 l l k 】1 2 k 】。 第二步，剪枝步。 对c k + 。中的任一候选项集c ，扫描数据库，确定它的计数，若该值小于最小支持度计 数，那么就从c 中删除该候选集c ，最后确定l k + l 。 然而c “。可能会很大，这样涉及的计算量就会很大。在此，可以使用a p r i o d 性质： 如果项目集x 不是频繁项目集，那么它的所有超集都不是频繁项目集。因此，如果一个 候选( k + 1 ) 项集的k 子集不在l k 中，则该候选项集也不是频繁的，从而可以在c n 。中删除。 由于在生成长度为时1 ) 的候选项目集时己经知道了所有长度为k 的频繁项目集，这让我 们能很好的利用a p r i o d 属性来为候选项目集剪枝，即减少生成的候选项目集从而缩小搜 索空间。 ( 2 ) 算法实例 下面通过一个例子来说明利用a p r i 耐算法挖掘频繁模式的过程。表2 1 中记录的是 某超市的交易数据集d ，共有9 条交易记录，每条记录中包含识别号t i d 和一些商品代 码，如1 1 ，1 2 ，1 3 ，1 4 ，1 5 。在本例中设定最小支持度计数为2 ，即如果某个记录在数据 库中出现的次数大于或等于2 ，即为频繁项集。 表2 1 某商场的交易记录 t a b l e 2 1t r a n s a c t i o nr e c o r do f am a r k e t 数据扫描 t i d项i d 的列表 1 1 1 ，1 2 ，1 5 21 2 1 4 3 1 2 1 3 4 1 1 ，1 2 ，1 4 51 1 1 3 61 2 1 3 7i l - 1 3 8il ，1 2 ，1 3 ，1 4 ，1 5 9 i l ，1 2 ，1 3 ，找出频繁1 项集，结果得到 l = 1 1 ：6 ，1 2 ：7 ，1 3 ：6 ，1 4 ：2 ，1 5 ：2 ，每个项目后的数字是其支持度计数。 为发现频繁项集l 2 ，有l l 自连接产生c 2 。扫描数据库，计算每个候选项集的支持 数，确定l 2 。 1 4 中国石油大学( 华东) 硕士学位论文 为发现l 3 ，首先有l 2 自连接得到c 3 = 1 1 ，1 2 ，1 3 ) ， i i ，1 2 ，1 5 ， i i ，1 3 ，1 5 ) ， 1 2 ，1 3 ，1 4 ) ， 1 2 ，1 3 ，1 5 ) ， 1 2 ，1 4 ，1 5 ) ) 。根据a p r i o r i 性质，其中4 个不可能是频繁的，可以在c 3 中直接 删除。 由l 3 自连接产生c 4 ，产生 1 1 ，1 2 ，1 3 ，1 5 ) ，根据a p r i o r i 性质不可能是频繁的。所 以l 4 为空。算法结束，找到了所有频繁项集。其过程如图2 4 所示 项集s u p p o r f _ c o u n t 1 1 ) 6 1 2 ) 7 1 3 ) 6 1 4 ) 2 1 5 ) 2 确定l 2 - + 由l 1 产生c 2 - - - - - - - - - - - - - - 项集 s u p p o n _ c o u n t 1 1 ，1 2 4 1 1 ，1 3 4 1 1 ，1 5 2 1 2 ，1 3 4 1 2 ，1 4 2 1 2 ，1 5 2 项集 1 1 ，1 2 1 1 ，1 3 1 1 ，1 4 1 1 ，1 5 1 2 ，1 3 i 2 ，1 4 ) 1 2 ，1 5 1 3 ，1 4 1 3 ，1 5 1 4 ，1 5 产生 c 3 ，扫描 数据痊z - 得到支 持度计 数 扫描数 鬻到支持 度计数 项集 s u p p o r t c o u n t 1 1 ，1 2 4 1 1 ，1 3 4 1 1 ，1 4 1 1 1 ，1 5 2 1 2 ，1 3 4 1 2 ，1 4 2 1 2 ，1 5 2 1 3 ，1 4 o 1 3 ，1 5 1 i 4 ，1 5 0 项集s u p p o r t _ c o u n t 1 1 ，1 2 ，1 3 2 1 1 ，1 2 ，1 5 2 确剧i - , 3 ， l 3 项集s u p p o r t _ c o u n t 1 1 ，1 2 ，1 3 2 1 1 ，1 2 ，1 5 2 图2 4 生成频繁项集 f i 9 2 - 4g e n e r a t i n ga n dt e s t i n gf r e q u e n ti t e m s e t s 第二章数据挖掘技术 ( 3 ) 算法存在问题 大量的实验都显示a p r i o r i 算法具有可伸缩性和良好的性能，尤其是在处理稀疏数 据时表现优异。所谓稀疏数据就是事务的长度相对全体项目的个数来说非常少。a p r i o r i 算法存在着以下问题： 1 ) 对数据库的扫描次数过多。在a p f i o f i 算法的描述中，每生成一个候选项集，都 要对数据库进行一次全面的搜索。当数据库中存放大量的事务数据时，在有限 的内存容量下，系统i o 负载相当大，每次扫描数据库的时间就很长，效率非常 低。 2 ) 可能产生大量的候选项集。尤其是在产生二阶项集时，如频繁1 项集的数量为 1 0 0 0 0 时，长度为2 的候选项集的数量将达到5 1 0 7 。如果要生成一个很长的规则 的时候，要产生的中间元素的数量也是巨大的。 2 2 5 频繁项集生成关联规则 从数据集d 中找出的频繁项集已经满足最小支持度，只需再进行最小置信度判定即 可产生强关联规则。关联规则的产生如下： 对于每个频繁项集l ，产生l 的所有非空子集。 对于l 的每个非空子集s ，如果型班坚些型型婴m i n e o n f i d e n c e ，则输出“s = ( 1 s ) ”。 s u p p o r t _ c o u n t ( s ) 对于表2 1 中的例子，其中的一条1 = 1 1 ，1 2 ，1 5 ) 。其非空子集有 1 1 ，1 2 ) ， i l ，1 5 ) ， 1 2 ，1 5 ) ， 1 1 ) ，( 1 2 ) ， 1 5 。产生的关联规则如下： 1 1a 1 2 = 1 5 c o n f i d e n c e = 5 0 ；1 1 八1 5 = 1 2 ，c o n f i d e n c e = 1 0 0 ； 1 2 八1 5 = 1 1 ，c o n f i d e n c e = 1 0 0 ；i l = 1 2 八1 5 ，c o n f i d e n c e = 3 3 ； 1 2 = i1 八1 5 c o n f i d e n c e = 2 9 ；1 5 = 1 21 八1 2 ，c o n f i d e n c e = 10 0 ； 如果最小置信度设定为7 0 ，则只能输出三条强关联规则。 2 3 本章小结 本章首先介绍了数据挖掘的概念、步骤、功能、常用技术及其今后的研究方向，重 点介绍了关联规则挖掘问题，描述了关联规则的基本概念、分类，然后分析了关联规则 的挖掘步骤及其关键所在，并全面介绍了关联规则的经典算法a p r i o r i 算法。 1 6 中国i 油大学( 华东) 硕学位论文 第三章基于关联规则挖掘的钻井地质设计系统 钻井地质设计是一项复杂、细致的工作钻井地质设计系统的开发及应用，极大地 方便了设计人员的工作，减少了设计环节中的重复劳动，并为地质设计提供大量的参考 数据，有助于设计人员集中精力分析研究、精细设计，设计的质量和及时率均得到了明 显提高。 3 1 系统体系结构选择 目前常用的体系结构主要有c s ( 客户机，服务器) 结构和b s ( 浏览器朋务器) 结构。 该系统采用c s 结构，主要是基于下面的考虑： ( 1 ) 该系统的使用仅限于录井公司内部设计人员，c s 结构有利于保护数据的安 全。 ( 2 ) c s 结构的设计具有较快的相应速度，服务器运行数据负荷较轻，这对于数 据量庞大的钻井设计系统是很有利的。 ( 3 ) d s 结构可以保证即使在外部网络不通的情况下，也可以进行设计工作