（计算机应用技术专业论文）利润约束关联规则算法及在故障检测中的应用.pdf

华中科技大学硕士学位论文 摘要 远程监测与故障诊断系统是企业信息化建设重要内容之一，自动控制数据库 满足数据挖掘要求，如何对该数据库进行挖掘从而获得传统自动控制理论以外的 知识，是目前研究的热点之一。 文中研究了关联规则在故障检测中的应用，把故障进行了分类，对现在故障 检测技术作了综述，对数据挖掘和关联规则现状作了综述分析了数据挖掘在故 障检测技术应用可行性，分析了关联规则在故障检测中应用的可行性 随着生产过程的演变，自动控制数据对不同时间、不同测量点产生的数据对 参数的贡献也是不同的，对故障的影响也是不同的。为解决该问题引入了利润约 束后多值数据库的数据关联问题，给出了具有利润约束的多值数据库的数据关联 规则问题的性质，并给出解决该问题的高效算法。为了解决自动控制故障的数据 不连续性问题，给出合并频繁利润项目集，最小合并频繁利润项目集，全合并频 繁利润项目集概念，这些概念利于解决不相邻的区问进行合并进行关联问题。 对关联规则特别是利润约束的数值型关联规则在故障检测中的应用，给出了 相对应的方案。对利润约束的数值型关联规则进行了仿真研究。利用关联规则， 利用利润约束，从而得到更多的故障数据关联，根据利润来诊断故障的原因，同 时合理设置利润约束值，当短期数据利润达到该值时进行故障预警。最后总结了 全文，指出了进一步研究的方向。 关键字；关联规则，故障检测，利润约束，合并频繁利润项目集 i 华中科技大学硕士学位论文 l l c - m o t cm o n i t o r i n ga n df a n l td i a g n o s i ss y s t e mi so n co ft l a ci m p o r t a n tc o n t e n t so f c n t e r p i i n f o r m a t i o n , t h cd a l ab a s eo fa u t oc o n t r o lm e e tt h er c q u i r c m c n t so fd a t a m i n i n g h o wt og a i nt h el m o w l c d g co fo u to ft r a d i t i o l l l t la u t oo o n t r o lt l a c o r yf l o m m i n i n gt h ed a t a b a s eo fa u t oc o n t r o li sb e c o m i n gah o ts p o to fr e s e a r c h t h ea u t h o rm a i n l yf o c u s 蛐t l a ca p p l i c a t i o no ff a i l u r ed c t e c t i o nb a s e do n a s s o e i a l i o nn l l c s ，a n dc a r r yt l a cc l a s s i f i c a t i o nt ot h ef t a i h t r e ，s m m a r i z ct h ep r e s e n to f f a i l u r cd e t e c t i o n , d a t am i n i n ga n da s s o c i a t i o nr u l e s ，a n da n a l y z e st h a tt l a cf e a s i b i l i t yo f t h ea l 印u e n t i o no f d a t am i n i n ga n da s s o c i a t i o nr t i l c si nf a i l u r ed c t c c t i o l l w i t ht h er a p i , ld e v e l o p m e n to fp r o a e t i v c 珥啊鹤s t h ed a t ao fa u t oc o n t r o lh a s d i l l e r e n tc o n m l n a i o n st ot h er c l a t e x lp a r a m e t c ra tt l a cd i f f e r e n ts t a g e sa n dm c a 懿l i e p l a e c , t h ei n t t u e n c co nt l a cf a u l ti sa l s od i f f c r c t t os o l v et h ep r o b l e m , t h i sp a p e r i n t l o d u e e st l a eq u a n t i t a t i v ea , 蟠o c i a l i o l lr u l e sw i t hp r o f i tc o m t r a m t , p r e s e t si t s e l a a m e t e r , a n d 肌c f l e e t l y ea l g o r i t l m l o ft l a c p r o b l e m i no r d e r t os o l v et l a c d i s c o n t i n u o u so ff a i l u r ed a t ao fa u t oc o n t r o l ，t l a ea u t h o rp u t sf o r w a r dt h e e o c e - p t i o so f u n i t ef z e a t u e a ti t e m s e t s , l l l j l m u mu n i t ef 蕾e q u c n ti t e m s e t sa n dc o m p l e t e 丘e q u e m i t e m s e t s t h e s ec o n c e p t i o n s 伽h e l pt ot h ep r o b l e mo fa s s o c i a t i o na n du n i o nt h e d i f f e t 伽ts i 地i o i o fq u a n t i t a t i v ea s s o c i a t i o nr u l e sm i n i n g t h ea u t h o rp r o p o s e sc o r r e s p o n dp l a nt ot l a ea p p l i c a t i o no fa s s o c i a t i o nn d e s 。 c s l x c i a l l yq u a n t i t a t i v ea 黜 i l i t i o l lr u l e sm i n i n gw i t hp r o f i te o m t r a i n ti nt h ef a i l u r e d e t e c t i o n , a n dd os i m u l a t i o nr e s e a r c h m a k eu s eo fa s s o c i a t i o l lr u l e so fp r o f i t c o n , s l r a i n l ，m 呲f a i l t t r ea s s o c i a t i o ni n f o r m a t i o nc a l lb c 弘缸c d 出e 髓u 鞯o ff a l t t r e h a p l 把l lb a s e do nt h ep r o f i tc a l lb ed i a g n o 蛾! s i m u l t a n e o u s l y , w ec a 丑e a r l yw a m f a i l u r eb ys c - t t i n _ _ g 叩p r o f i tc o n s t r a i n t f i n a l l yl a cm t t h o l rs u m n m l z 鹭t ol h e s i sa n dp o i t o u tt i l ef u t u r er c s c a t e hd i t e c t j o l l k , j e y r o r ( 1 s ：q u a n t i t a t i v ea s s o c i a t i o nr u l e s ， f r e q u e n ti t e m s e t s 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名舷i 盼 日期：伽石年f f 月f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在 年解密后适用本授权书。 本论文属于 不保密曰。 ( 请在以上方框内打“”) 学位论文作者签名二斋m 日期： 删年1 1 月f 日 指导教师签名：鸯荔静纵 日期；a 以年l1 月) 目 华中科技大学硕士学位论文 1 绪论 1 1 控制系统故障检测研究主要内容 故障诊断及仪表检畏i 技术迅速发展，促进了用先进技术手段进行故障诊断技 术、工业防爆技术、无损检测技术、机械故障诊断技术和智能网络监测管理等。 以故障诊断为主的现代设备维护和状态检测新技术已日益广泛应用于各制造厂家 的机械设备领域。技术发展，传统的事后维修变为故障预报，整机在线维修“1 及事 前损伤检涌国对在线工作状态的监测诩嘲，对常规故障机理的进行综合分析研究。 以便对其故障进行事先诊断分析，为现代工业降低生产成本提供重要途径工程 系统安全可靠韵运行对于保障人员生命和健康、环境保护和提高经济效益是非常 重要的。系统的正常运行对降低产品成本，提高产品质量也有很重要的影响早 期的故障诊断可避免造成人员伤害和设备的灾难性事故。耪确的诊断能帮助人们 做出正确的决策，进行紧急的修复和抢救同样，工业设备的容错设计在这方面 也起到重要作用，如何减轻故障所造成的影响，提供一个安全的运行环境是目前 在在这个领域研究的一个主要方向。 目前，故障检测和诊断( f d d ) 现在已发展成为自动控制领域的一个主要研究领 域，是一个交叉性的学科，涉及到了系统集成、控制工程、人工智能、应用数学 和统计学等学科领域。作为现代自动控制，系统复杂化后，造成故障点增多，故 障的表现形式也增多，主要有下列五类故障： 1 生产设备故障 2 传感器智能仪表故障 3 总线故障 4 电路故障 5 软件故障 在这五类故障中，由于系统的不同，出现不同的故障，这是系统复杂化故障 检测与诊断困难化的主要原因。下面对其特点具体描述： 1 华中科技大学硕士学位论文 1 生产设备放障 现代生产中主要生产设备是机械设备，机械设备由于其系统复杂，工作环境 恶劣，通常高负荷、长时间运行，因此系统常出现各种故障嘲由于机械设备本身 不产生检溺监控数据，故其故障的判断只能依靠传感器、后期产品检溺、机械检 修等所得的数据来反映随着传感技术和自动控利、计算机等技术的发展，现代 生产管理将机械设备的状况转换为控制数据，并通过控制技术反映系统状态。为 生产设备传统的事后维修变为故障预报，整机在线维修及事前损伤检测准备了充 足的资源由于机械设备在运行中的复杂性，包括了已经确定规律的运行和有不 确定规律的运行，为了找出相关的运行规律，对其在线工作状态的监测以及故障 机理的进行综合分析研究，以达到对故障的事先诊断分析，找出设备运行的相关 性，依据设备数据之间的关系，挖掘前期故障与后期检测之问的关系。实现故障 预警和故障检测。 2 传感器智能仪表故障 传感器是在一定精度下把被测量( 主要非电量) 转换为与之有确定关系( 主 要是电量) 的测量装置上，将生产设备上的量的变化，转化为电量和数字信号， 进一步转换为反馈信息、控制数据等信息反映生产设备情况转换中传感器的输 入和输出量之间有对应关系，具有一定的精度。传感器在使用过程中受各种各样 的因素影响：首先传感器本身的稳定性影响：传感器在使用中由于自身的特点( 应 变、老化、内应力等) 使传感器的输出量与输入量不对应，造成数据故障；传感 器受外界环境影响：传摩器在使用中不仅受输入量的影响，还受外界环境影响( 如 温度、气压等) 导致传感器的输入和输出特性变化，以致不能够很好反映生产设 备状况；传感器受支持电路的影响：传感器要将外界输入量转换为电量并进行采 集与反馈，必须有输入支持的电路( 调理电路) ，这个电路的品质一定程度上决定 了传感器的质量。由以上原因可以看出传感器故障嘲的主要影响是传黪器所传输信 号通过转换后是否能够真正反映生产设备现状。找出传感器与生产设备之间的量 关系，找出传感器滋生的变化规律，挖掘数据之间的联系，是解决传感嚣故障的 手段 2 华中科技大学硕士学位论文 3 总线故障 在现场总线出现之前，现场智能仪表及控制室智能仪表它们之间的联络主要 依赖传统的4 2 0 m a 模拟信号这种连接，使智能仪表的许多功能得不到有效的发 挥由于使用场合的不同，各大公司纷纷开发适用于传统应用领域的多种现场总 线制造业将会有更多的具有多种参数多种检测能力的现场总线仪表问世，有更 多的标准现场总线分线盒可供设计选择，低功耗仪表会得到很大的发展m 。以适应 危险区域的要求无论那种现场总线。在使用中均会受到生产环境干扰，参数匹 配等影响造成传输故障 4 电路故障 传摩器所得的电量往往需要经过电路转换进行放大、滤波、采样等进行处理， 将传感所得的电信号转换为可测信号，通过模数转换装置转换为数据信号在这 个过程中电路受到自身特性影响，具有不稳定性( 如：温度特性、幅频特性等) ， 受外界因素影响导致电路受到干扰呻( 如：电磁干扰，嗓音等) 导致传感器传输数 据不能反映生产设备量值造成电路故障。 5 软件故障 环境干扰不仅影响检测系统硬件嗍，而且对软件系统也会造成破坏如造成系 统的程序弹飞、进入死循环或死机状态使系统无法工作。外界对智能仪表中的单 片机系统产生干扰后，可能引起r a m 程序计数器获得到总线上的数字信号时发生 错乱，c p u 根据错误数据进行运算得到错误的操作数和结果，在没有任何纠错措施 的情况下，这个错误会一直传递下去c p u 读取错误的地址码后，会造成程序运行 偏离正常轨道引起程序失控。程序失控后，我们采用软件抗干扰措旌，可以使系 统回到正常运行状态，但已经造成一系列不良后果，造成数据误差、控制失灵、 某些部件工作状态改变等。 1 2 故障检测研究现状 故障检测和诊断( f d d ) 现在已发展成为自动控制领域的一个主要研究领域，是 一个交叉性的学科，涉及到了系统论、控制工程、人工智能、应用数学和统计学 3 华中科技大学硕士学位论文 等学科以及各种应用领域( 包括化学、电子学、机械学、航天航空等) 。虽然故障 检测技术在工业控错领域的研究已经涉及许多学科，但目前故障检测技术研究主 要基于以下原理： 1 采用统计学理论 根据生产过程中采样数据并结合工业过程查找错误源，利用统计控制洲对工 况进行监控，从现场数据中检测、判断异常采样点。使用较多的故障诊断方法是 贡献法，通过比较各变量对故障数据的贡献率分析找出异常变量，从而实现故障 分离。并且基于这个原理通过比较统计个变量之间的关系，利用统计学原理对各 故障原理进行分析处理，查找故障源 2 具体故障检测与处理 根据生产过程中设备( 包括生产设备和检测设备) 具体情况1 ，对涉及具体 问题进行分析由于设备的多样性，故障的复杂性，这一类解决方法具有具体性、 单一性、专用性，涉及了工业控制系统的基本原理，涉及学科门类较多，具体技 术实现比较复杂。 3 基于信号分析技术 在机械设备的在线检测和自动控制等领域，突变信号的检测与识别是十分重 要的蚴 i s o 突变信号往往隐藏在背景噪声里，包含突变信号及噪声信号常常表现 出非平稳性质，对此类信号的处理具有相当的难度。传统的分析适合于平稳信号， 对出现的非平稳信号分析却无能为力：小波分析由于具有时频域局部化特性，并 且时窗和频窗的宽度可调节，故可检测到突变信号但是，在小波分解方法分析 信号时存在着小波基的选择问题，不同的小波基具有不同的时频特性，因此，同 一信号经过不同的小波基进行分析往往表现出不同的结果。小波分解对信号的奇 异点检测和消噪具有广泛的用途，小波变换由于其时一频局部化特征，非常适合 故障信号的识别。小波分析对单一故障源的捡溅很有效，但对多故障源却无能为 力。 4 基于神经网络技术 多模态控制是一种基于控制对象的几个不同模态设计不同控制器的设计方 4 华中科技大学硕士学位论文 法，为了产生合适的控制输入，不同的环境条件和故障模态的辨识是很重要的系 统要依靠被控对象与不同模态问的误差来确定，非线性系统的辨识是多模态控制 系统的一个重要步骤。对此，神经网络町n 耐是比较理想的工具，系统的动态信 息就存储在网络中。 5 基于模型建模 随着系统复杂性的增加，控制系统的可靠性问题变得越来越重要，故障检溯 和诊断作为提高控制系统可靠性的主要手段，受到了广泛的重视。基于模型的解 析冗余方法，其中基于线性模型的故障诊断已有了较成熟的结果，方法主要包括： 等价空间法、检测滤波器法、参数估计法、奉献观测器法等。基于模型“州蚓的故 障检测方法依赖于系统的数学描述，但实际中很难获得精确的模型表示，不可避 免地存在未建模动态，同时还存在测量嗓声、外部扰动等不确定性另一方面， 实际系统通常是非线性系统，因而鲁棒及非线性故障检测与诊断受到了人们的日 益重视。 6 虚拟智能控制 在现代工业中，越来越多的系统需要进行周期性维护和故障检测，快速地对 系统故障情况和故障部位进行诊断，对于提高系统设备的利用率具有重要的意义 但是许多故障需要检测的信号繁杂，进行检测的步骤要求精确，对检测提出了很 高要求。将虚拟仪器技术“”嘲口1 1 和数据库技术相结合进行自动故障检测系统嘲， 利用仿人智能控制系统的对人的控制结构宏观模拟的基础上进一步研究，人的“身 体一动觉智能”，即人的控制行为功能并加以模拟，模拟人的控制行为，达到提高 控制品质的目的。 7 。多元逐步诊断理论”和“两种质量多元诊断理论” 张公绪教授的s p d m j ( s t a t i s t i c a lp r o c e s sd i a g n o s i s 即统计过程诊断) 采 用统计方法对统计过程所得的数据进行诊断分析，使用抽样韵方法，运用控制图 对测量结果进行分析，其实质还是统计学理论。s p d 是利用统计技术对过程中的各 个阶段进行监控与诊断，从而达到缩短诊断异常的时间、以便迅速采取纠正措施、 减少损失、降低成本、保证产品质量的目的。目前，我国依据上述诊断理论已开 5 华中科技大学硕士学位论文 发出两种诊断软件。一种是依据。两种质量诊断理论”开发的应用软件s p c d 2 0 0 0 ， 用于诊断多工序生产线中上工序对下工序的影响；另一种是依据“多元逐步诊断 理论”和“两种质量多元诊断理论”开发的多元诊断软件d t t q 2 0 0 0 ，用于多因素 相关条件下的诊断。而后者同时也考虑了上工序对下工序的影响。但其控制过程 比较复杂，计算量大，受抽样因素影响较大，其统计过程不合格原因诊断应用排 列图分析 8 数据挖掘的方法 工业数据处理产生的大规模数据，应用大量的数据库，具备了事务数据库特 点，具备有数据挖掘的基本要求。如何对该数据进行挖掘从而获得传统工业控制 理论以外的知识，采用数据挖掘的方法解决质量控制中自动控制故障诊断问题， 类似和相关的研究很多，例如：在销售领域，电学领域乜嘲计算机网络嘲鲫等都 有相关的数据挖掘内容，并且有一些研究成熟的软件，并且相当一部分研究与自 动控制和过程诊断有相似之处，这些都可以作为故障检测数据挖掘方法实现的借 鉴，本次毕业设计用关联规则的原理和方法去研究故障检测有关问题。 1 3 故障检测中的数据挖掘及本文的贡献 随着计算机技术、传感器技术、自动控制技术的发展，以及数据采集工具的 发展，工业数据处理产生了大规模的数据，应用了大量的的数据库嘲人们希望 能够提供更高层次的工业数据分析功能，自动和智能地将待处理的数据转化为有 用的信息和知识。数据挖掘是从大量数据中挖掘出隐含的、先前未知的、对决策 有潜在价值的知识和规则的高级处理过程。从工业数据库中找到各数据之问、数 据与实际应用之间的相互关系从而对生产过程之间的关系进行分析，从而找出生 产过程中各具体数据之间的关系，为工业控制故障诊断服务。 数据挖掘与知识发现咖是一个以数据库，人工智能、数理统计、可视化四大 支柱技术为基础，多学科交叉、渗透、融合形成的新的交叉学科，其研究内容十 分广泛，存在很多数据挖掘方法或算法。描述或说明一个算法涉及三个部分：输 入、输出和处理过程。数据挖掘算法的输入是数据库，算法的输出是要发现的知 华中科技大学硕士学位论文 识或模式，算法的处理过程则涉及具体的搜索方法 数据挖掘研究自诞生以来，先后应用了不同的术语和定义：d a t am i n i n g k n o w l e d g ed i s c o v e r y ，p a t t e r nd i s c o v e r y ，d a t ad r e d g i n g ，k n o w l e d g e ，d a t a a r c h e o l o g y 等。 k d d 的定义为：k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终可理 解的模式的过程 数据挖掘的定义为：数据挖掘是k d d 中通过特定的算法在可接受的计算效率 限制内生成特定模式的一个步骤由此可见，整个k d d 过程是一个以知识使用者 为中心、人机交互的探索过程。数据挖掘只是数据库中知识发现的一个步骤，但 又是最重要的一步数据挖掘研究主要有3 个技术支柱，即数据库、人工智能和 数理统计目前删曲的主要研究内容包括基础理论、发现算法、数据仓库、可视 化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构 化和非结构化数据中的知识发现以及网上数据挖掘等 存在很多数据挖掘方法或算法，因此有必要对这些方法进行分门别类。描述 或说明一个算法涉及三个部分：输入，输出和处理过程。从算法的输入、输出和 处理过程三个角度分可以确定这样几种分类标准：挖掘对象、挖掘任务，挖掘方 法。数据挖掘算法的输入是数据库，算法的输出是要发现的知识或模式，算法的 处理过程则涉及具体的搜索方法。人们把原始数据看作是形成知识的源泉，发现 的知识可以被用于信息管理、查询优化、决策支持、自动控制等，还可以用于数 据自身的维护。根据挖掘任务分，数据挖掘主要发现以下五类知识： 广义型知识( g e n e r a l i z a t i o n ) 根据数据的微观特性发现其表征的、带有普遍 性的、较高层次概念的、中观或宏观的知识。 分类型知识( 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 ) 反映一个事件和其它事件之间依赖或关联的知识， 又称依赖( d e p e n d e n c y ) 关系。这类知识可用于数据库中的归一化，查询优化等。 7 华中科技大学硕士学位论文 预测型知识( p r e d i c t i o n ) 通过时间序列型数据，由历史的和当前的数据去预 测未来的情况，它实际上是一种以时间为关键属性的关联知识。 偏差型知识( d e v i a t i o n ) 通过分析标准类以外的特例，数据聚类外的离群值， 实际观测值和系统预测值问的显著差别，来对差异和极端特例进行描述。 数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的简单检 索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计，分析、综合和 推理，以指导实际问题的求解，企图发现事件问的相互关联，甚至利用已有的数 据对未来的活动进行预测。把人们对数据的应用，从低层次的末端查询操作，提 高到为各级决策者提供决策支持。 从以上数据挖掘功能中可以看出，数据挖掘可以发现对故障检测有很重要意 义的知识。特别是后三种知识关联知识可以用来发掘生产故障与检测数据之间 内在联系，判断故障来源。预测型知识实际上是一种时间属性的关联，是关联知 识的时间序列化，可以根据已有历史数据进行数据预测，从而预测在现有生产状 况下，生产设备超出正常状态的可能性，从而可以进行故障预警偏差型知识可 以根据已有的数据知识库中观测值和系统预测值之间的显著差别来对极端特例进 行描述，在正常的关联知识下，超出正常关联规律所得到的偏差即可为故障检测 的主要任务一找出故障原因。从上述关系可以看出数据挖据特别是关联规则对 故障检测的重要意义 放障检测技术在工业控制领域的研究已经涉及许多学科。工业数据处理产生 的大规模数据，应用大量的数据库，具备了事务数据库特点，具备有数据挖掘的 基本要求，如何对该数据进行挖掘从而获得传统工业控制理论以外的知识，是解 决传统工业控制研究的一个新的领域。 本文应用数据挖掘于故障检测技术的研究主要包括以下几个方面： 1 对故障检测技术的现状进行了综述 2 数据挖掘在故障检测技术应用进行了分析 3 综述了数据挖掘和关联规则 4 关联规则在控制系统故障检测中应用进行分析 e 华中科技大学硕士学位论文 5 谚计了具有利润约束的数值型关联规则的挖掘方法 6 对有关联规则和利润约束关联规则在故障检测中的给出了方案 1 4 本章小节 本章对作为现代自动控制，系统复杂化后，造成故障点增多，故障的表现形 式也增多主要有下列：生产设备故障、传感器智能仪表故障、总线故障、电路 故障、软件故障，本章对这五类故障分掰进行了分祈。 对目前故障检测技术研究进行了研究，其主要基于以下原理；1 采用统计学 理论；2 具体故障检测与处理；3 基于信号分析技术；4 基于神经两络技术；5 基于模型建模；6 虚拟智能控制；7 。多元逐步诊断理论”和。两种质量多元诊 断理论”；8 数据挖掘的方法本节对上述故障检测的方法进行了简单分析。 9 华中科技大学硕士学位论文 2 关联规则研究 2 1 关联规刚及其研究的主要内容 关联分析是寻找数据库中值的相关性，两种常用的技术是关联规则和序列 模式，关联规则是寻找在同一个事件中出现的不同项的相关性。 关联规则可记为a 一 b ，a 称为前提和左部( l h s ) ，b 称为后续或右部( 妞s ) 。 如关联规则“买锤子的人也会买钉子”，左部是。买锤子”，右部是“买钉子气 某一特定关联( 。锤子和钉子”) 在数据库中出现的频率称为支持度。非常低 的支持度( 比如1 百万个事务中只有一个) 可能意味着此关联不是很重要，或出 现了错误数据。要找到有意义的规则，我们还要考察规则中项及其组合出现的相 对频率当已有a 时，b 发生的概率是多少? 也即概率论中的条件概率这个条件 概率在数据挖掘中也称为可信度，计算方法是求百分比：( a 与b 同时出现的频率) ( a 出现的频率) 。 挖掘关联规则问题( m i n i n ga s s o c i a t i o nr u l e s ) 是r a g r a w a l 等人在文献m 1 中蓄先引入的。顾客在购买菜些东西的时候有多大的倾向也会购买另外一些东西， 找出所有类似这样的规则，对于确定市场策略是很有价值的设计高效的算法来 挖掘关联规则，而且如何维护和更新这些规则。如何确认这些规则是否有价值， 如何在分布式数据库中进行关联规则的挖掘等等这些问题都必须得以解决。 闯题描述渊：下面我们给出关联规则挖掘问题的形式化描述： 假设i = i 。，i “，i 是个不同项目的一个集合，t = t ，t 。， t 。 是一个交易数据库，其中每一个交易t ，表示t 的第j 个交易，即它是i 中一 组项目的粜合，t ，g 。每一个交易都与一个唯一的标识符t i d 相联。如果对于i 中的一个子集x ，有x _ ct ，我们就说一个交易包含x ，一条关联规则就是一个形 如“x 4 y ”的蕴涵式，其中x c i ，y c i ，而且x n y ：中。 1 0 华中科技大学硕士学位论文 定义：如果t 中包含交易x y 的比例为s u p ，则关联规则x 辛y 在t 中具有 支持度( s u p p o r t ) s u p ， s u d ：s u p p o a ( xuy ) 1 0 0 其中，s u p p o r t ( x u y ) 为数据库中支持x u y 的交易数，r l 为数据库中的交易 总数。 。 定义；如果t 中包含x 的交易同时也包含y 的比例为c o n f ，则关联规则x 哮y 在t 中以信任度( c o n f i d e n c e ) c o n f 成立， c o n f ：s u p ( x 0y ) x1 0 0 跚p 其中s u p ( x u y ) 为x u y 的支持度，s u p ( x ) 为x 的支持度 关联规则的挖掘问题就是生成所有满足用户指定的最小支持度( m i n s u p ) 和最 小信任度( m i n c o n o 的关联规则，即这些关联规则的支持度和信任度分别不小于最 小支持度和最小信任度 定义：满足最小支持度和最小信任度的关联规则称为强关联规则( s t r o n g a s s o c i a t i o nr u l e s ) 。 定义 从交易数据库( 数据库中所有属性项的取值要么为0 ，要么为1 ) 中挖 掘得到的关联规则称为布尔型关联规则。 关联规则的挖掘问题可以分解成以下两个子问题： ，1 ) 找出交易数据库t 中所有满足用户指定最小支持度的项目集( i t e m s e t ，i 的一个非空子集) ，满足最小支持度的项目集称为频繁项目集( f r e q u e n ti t e m s e t s ) 或者大项目集( 1 a r g ei t e m s e t s ) ，反之就称为小项目集( s m a l li t e m s e t s ) 。 2 ) 利用频繁项目集生成所需的关联规则对于每一个频繁项目集a ， s u p p o r t ( a ) 找i i la 的所有非空子集a ，如果璺婴苎! ! 攀m i n c f ，就生成关联规 s u p p o m a ) 则a ( a - a ) 相对于第一个子问题而言，由于第2 个子闯题在内存，i o 以及算法效率上 n 华中科技大学硕士学位论文 较为容易与直观，且在嘲给出了算法，因此目前大量的研究工作主要都集中在第1 个子问题上 2 - 2 关联规则研究现状 在得到了频繁项目集l 后，按照下面的步骤就可以生成关联规则了：对于每 一个频繁项目集l ，生成其所有的非空子集。 对于1 的每一个非空子集】【，如果竺鲤! 壁熊z m i n c o n f ，则输出规则“x 辛 s u p e o r t ( x ) ( 1 - x ) 。0 可以看出，由于规则是从频繁项目集中生成的，因此所生成的每一个规则都 会自动地满足最小支持度的要求 a p r i o r i 算法洲 为了解决前面提到的第一个子问题，必须对数据库进行扫描以计算支持度和 信任度。而通常挖掘的数据库有很多属性，且数据量巨大，因此对数据库扫描的 次数、读取数据库的i o 次数就显得尤为重要。而更为重要的是。在求取频繁项 目集时，由于不同的项目集的数量可达到2 个( m 为项目的个数) ，若对所有的项目 集都进行支持度的计算，几乎是不可能的。目前有关关联规则的发现算法主要是 集中研究如何能快速有效地提取频繁项目集上，其焦点有二：一是能对项目集进 行充分地剪支，尽最大可能最小化有用项目集；二是最小次数地扫描交易数据库t ， 从而提高算法的效率。为此，h e 衄【im a m f i l a 等嘲提出了下面两个重要的定理： 定理1 ；如果项目集x 是频繁项目集，那么它的所有非空子集都是频繁项目 集。 定理2 ：如果项目集x 是小项目集，那么它的所有超集都是小项目集。 a g r a w a l 等人在嘲中提出关联规则概念的同时，也给出了相应的挖掘算法 a i s ，但性能较差。1 9 9 4 年，依据上述两个定理，r a g r a w a l 等人又提出了著名 的a p r i o r i 算法，其描述如下： 算法：发现频繁项目集( a p r i o r i ) 1 2 华中科技大学硕士学位论文 输入：交易数据库t ；最小支持度m i n s u p 输出：t 中的频繁项目集l b b g i n l , - - f i n d _ f r e q u e n t _ l i t e m s e t s ( t ) ： f o r ( k = 2 ：l h o ：k h ) c - = a p r i o r i _ g e n 吐i ；m i n s u p ) ： f o re a c ht r a n s a c t i o nt et c i = s u b s e t ( t ) ： f o re a c hc a n d i d a t ec e c i c c o u n t + + ： ) l f c g ic c o u n tz m i n s u p r e t u r nk u k ： e n d p r o c e d u r ea p r i o r i _ g e n ( l p l ：f r e q u e n t ( k _ 1 ) 一i t e m s e t s ；m i n s u p ：m i n i m u m s u p p o r t ) f o re a c hi t e m s e t1 l k f o re a c hi t e m s e t1 5 l k - 1 i f ( 1 。 1 = l ： 1 ) a ( 1 。 2 = l ： 2 ) a ( 1 。 k - 2 = i ： k - 2 ) a ( 1 。 k - i s p l i t ( x ) 映射为一个逻辑属性a ，进而将所有数 值属性及其值域区间映射为项目集； 3 产生支持度大于等于最小支持度m i n s u p 的频繁项集： 1 6 华中科技大学硕士学位论文 4 利用频繁项集产生置信度大于最小置信度m i n c o n f 的关联规则； 5 从所有产生的规则中确定出有趣的规则文献御介绍将数值数据映射到二 维空间，利用基于密度分布函数的聚类分析方法将数值属性区间分段，并在此基础 上挖掘容易理解并且具有概括性和有效的数值属性关联规则 处理数值型字段的方法基本上有以下几种： 1 数值字段被分成一些预定义的层次结构，这些区问都是由用户预先定义的， 得出的规则也叫做静态数量关联规则。 2 数值字段根据数据的分布分成了一些布尔字段每个布尔字段都表示一个 数值字段的区间落在其中则为1 ，反之为0 ，这种分法是动态的得出的规则叫布尔 数量关联规则 3 数值字段被分成一些能体现它含义的区间它考虑了数据之间的距离因素， 得出的规则称基于距离的关联规则 4 直接用数值字段中的原始数据进行分析使用一些统计的方法对数值字段的 值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较从而得出 一些有用的规则，得出的规则称为多层数量关联规则。 2 4 相关研究 除了以上列举的关联规则算法之外，还有一些研究方向p 田【3 2 j ，如：发现关联 规则的语言，图像的关联规则发现算法，加权关联规则算法，挖掘相关性和因果 关系，演变数据的动态的关联规则挖掘，生成关联规则不同的衡量标准的算法研 究，并行发现算法等等。具体来说工作主要集中在以下几个方面： 1 开发更高效的挖掘算法；随着数据库的尺寸不断增大，不仅增大了挖掘算 法的搜索空间，而且也增加了盲目发现的可能性。因此必须利用领域知识去提取 与发现任务有关的数据，删除无用的数据，有效地降低问题的维数，设计出更加 有效的挖掘算法。在这方面，基于约柬的关联规则挖掘具有广阔的前途。 2 可视化挖掘：设计一个灵活方便的用户界面，允许用户与挖掘系统进行交 互，并对所挖掘的结果进行很好的可视化表示，使非领域专家也能进行挖掘。 】7 华中科技大学硕士学位论文 3 各种非结构化数据的挖掘：目前大多数关联规则挖掘大多是基于关系数据 库或事务数据库的算法，设计应用于其他类型数据库( 如面向对象数据库、数据 仓库、文本数据、图形图像数据、多媒体数据等) 关联规则挖掘算法也将是十分 有意义的工作 4 并行关联规则数据挖掘：随着数据挖掘中数据量的高速增长以及大规模并 行计算在数据挖掘中的应用，由于挖掘系统本身的原因，并行数据挖掘过程更加 趋向粗粒度的挖掘，无法实现任意程度的并行。目前在并行数据挖掘中尚有一些 问题需要解决：数据量的不断增长，维数越来越高，数据定位问题，数据的不对 称性，动态负载平衡，多表数据库的数据分布和索引方案，增量的方法，并行的 数据库管理系统与文件系统 5 制定更为合理的关联规则衡量评价标准：目前的关联规则衡量标准可能会 发现一些冗余的、虚假的和非挖掘者关心的关联规则，因而有必要制定一些新的 衡量标准。用来衡量关联规则挖掘算法的优劣，但这些标准的制定可能要具体问 题具体分析 6 与其他系统的集成：这里的集成包括与其他挖掘方法的集成和与其他系统 ( 如专家系统、决策支持系统等) 的集成 7 研究在网络环境下的关联规则挖掘技术：特别是在i n t e r n e t 上建立叫服 务器，与数据库服务器配合，实现数据挖掘。 另外在关联规则的维护和扩展上有如下研究： 1 广义关联规则 广义关联规则的基本算法是将所有数据项的父类加入到事务t 中构成t ，t 支持数据项x 当且仅当t 包含x ，对t ，执行任何关联规则挖掘算法可得到广义 关联规则，但算法效率低；s r i k a n t 等人提出c u m u l a t e 算法、s t r a t i f y 算法、 e s t i m a t e 算法和e s t m e r g e 算法，其速度比基本算法快2 5 倍，随着数据量的增 大，e s t i m t e 算法链售臣优于c u m u l a t e 算法。 另外，也有相应优化技术提出，并主要在下面三个方面进行了研究与探讨： 一是每个层次的最小支持度是一致的；二是层次越低，分配的最小支持度越小： 1 8 华中科技大学硕士学位论文 三是根据需要为每一层分配不同的最小支持度 2 关联规则的维护 如何维护已发现的关联规则是很多学者研究的问题。关联规则的维护包括两 个方面：第一是当交易数据库中的交易不断增加时，如何维护在以前挖掘过程中 得到的关联规则，得到新的关联规则；第二是当最小支持度发生变化时，如何维 护在以前挖掘过程中得到的关联规则，产生满足要求的新的关联规则。 首先讨论了这方面的问题并提出了f u p 算法，此算法的基本思想是不对改变 后的数据库进行扫描重新寻找关联规则，而是利用上一次得到的关联规则，讨论 当有少量新的数据加入到数据库中时如何得到新的有用的关联规则，删除掉无效 的关联规则。 3 有价值关联规则的判别 对大型数据库而言，利用关联规则挖掘算法最终会得到上千个规则，但并不 是所有的规则都是有价值的，如果让决策人员人工的在这些规则中判别哪些有用， 哪些没有用是很困难的一件事情，因此判别规则是否有价值，并从中过滤掉“错 误”的或没有价值的规则就显得十分重要。 规则模板g 解决规则价值判别的一种方法就是使用相容模板“町用户可以利用 模板去定义哪类规则是有价值的，哪类规则是没有价值的，其形式如下： a l ， t = 争a h ， 其中a i 为属性名、类名或表达式c + 或西，c 是类名，而c + 及c 木则分别 表示一个或多个、零个或多个类c 。如果规则b l ，”，& 一艮。与模板匹配，则可 以认为此规则是有价值的。利用相同的原理，可以给出限制性模板，符合限制性 模板的规则可以被认为是没有价值的，从而被过滤掉。 这样，最终展现给用户的规则要么是有价值的( 即它与某一个相容模板匹配) ， 要么一定不是没有价值的( 即它不与任何一个限制性模板匹配) ，利用这种方法， 错误的、冗余的或相互矛盾的规则就可以被过滤掉。虽然关联规则“a 号b ”用这 种前因后果的形式进行表示，然而实际上，它们之间并不一定存在着因果关系， 即不一定a 是原因，b 是结果。出现这个问题的原因是因为在进行关联规则的挖 华中科技大学硕士学位论文 掘过程中，我们实际上并不知道数据库中各属性之间的相互关系，并且在挖掘过 程中没有将语义知识融入到挖掘算法中 使用项目限定：第二种发现有价值规则的方法是在挖掘关联规则的同时直接 对项目进行限定。实际上，用户经常只对某一类关联规则感兴趣。在这种情况下， 用户可以使用析取标准范式( d n f ) 来表达这些限制，并在挖掘算法中加入这些限 制。将限定直接融入到挖掘算法中可以极大地提高效率，因为这样在算法中只需 要发现那些满足限定的频繁项目集即可当然在这种情况下需要对算法进彳亍修改， 以便其能够理解d n f ，从而找到频繁项目集。 相关性：另一种评估关联规则价值的方法是。相关性”，它是基于数据统计的 一种客观测试方法我们知道，虽然一个关联规则可能有高支持度( 大于等于最小 支持度) 和高信任度( 大于等于最小信任度) ，但前