（应用数学专业论文）基于模糊集理论的量化关联规则挖掘.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据挖掘是丑前信息科学领域最前沿豹研究课题之一，在许多领域均有成功 的应用范例。它可以发现一些隐藏在大量数据背后潜在的信息来预测事物发展趋 势。关联规则挖掘是数据挖掘领域中一个重要研究方向。为解决量化关联规则挖 掘过程中的“尖锐边界”问题，已有研究者将模糊集的有关概念引入到关联规则 挖掘中，提出了“模糊关联规则。模糊集理论能够实现数据的平滑过渡，使得挖 掘出的关联规则具有高度的易理解性。但仍存在支持度定义不合理、主观地确定 隶属函数等问题。本文就上述问题，给出了一些解决方案，主要工作如下： i 、提出了一种新的支持度计算方法，并在此基础上，结合a 研面算法，提 出了一种挖掘模糊关联规则算法。实验表明，该算法是有效的。 2 、模糊关联规则挖掘中需确定隶属函数，提出了一种基于托m 的自动确定 样本隶属度函数的方法。该方法克服了人为确定隶属函数、带有主观性豹缺陷。 该方法在认知尚未成熟、缺乏先验知识的领域中具有应用前景。 3 、系统地分析了乒模算子对挖掘结果豹影响，并通过实验研究乒模算子对挖 掘算法性能韵影响。 关键词：数据挖掘；关联规则；模糊集理论；聚类 第页河南大学研究生硕士学位论文 a l b s t r a c t d 渤m i 王i 【i i l ga 瑚删yi s & r e 鸵砌缸跏m e rw i 蛐n 赫f 0 啊嘶s c _ i e n c e6 d d i t 飘a d s u c c e s s 印p l 渤埴。略i l lm 釉ya 陀邪i 蕾伽缸dm ep o t e n t i a lh o 胡e d g ew 量i i c h 虹d e s b e 越n d 也el 鹕e 触t o 内忧c a s 乏薯量l e 卸朗d1 0 fl b j n g s 出猢吨) p m ：e n t a s s o c i a 主i o n 棚e m 醯n gi s 蚰eo fm ek e yp o i n t si nm e 犯s e a r c h6 e l do fd 戤tn l i n i l 喀t od 嗣w i mt h e p r o b i e mo fs t 班pb o 岫d a 巧i nm i n i 薹l gq u 棚t a t i v e 私s o c i a ：t i o nr m e s ，f e s 把h 稻h a v e i n 纽d d u c e df 啦巧s c tt 量i e 0 黟蕾0d 啦m i n i n g s u c hk i n do f 私s o c i a ：t i o n 枷e si sc a l l e d 如z 珂懿s o c i a 主i o n 耐e s u s i n gf u z 巧s e tc o n c e p t 缸i ed i s c 0 v e df u l e s a r em o r e u n d e r s 协n d 乏i b l e 蕾0ah l m l a l l h o w e v e r ，抽e r ea r es o m ep r o m e n l si nm i n i n gm o d e l ， 抽c l u d i n g 咖豫墩，彻悦es u ；p p o nd c 6 i l i t i o n 锄ds “坳e c t i v e l yd e 棚脚谢融gm 咖b e 撼h i p 鼬商o n 0 阻c 酬y ，m em a i l lw o 出i n c l 玑扯s ： i 陆鲥y ，b a s e d0 nm e v ds u p p o r tm 涨a n d 舢疆i 商姆尉h n l ，a n e wa 1 9 0 r i t b 董n 断m i i l i n g 缸巧嬲s o c i 撕蚰枷e si s 脚o s e d e x p 耐m c n l 斌陀s m t si 玎u s 扛a 主e 龇 a l 鲥也li sm o r ee 麟i v e 2 s e o o n d l y ，am e t h o do fd 芒艇棚血l i 芏l gt | l em 朗西e r s m p 如n ：t i j o no fs a m p l e 纰b a s e d o nm ef - u z 巧c _ i n 咖si sp f e s e b 艇d t h em e m o do v e 】广c 锄e sn l ed e f b c to f d e i c 锄i n i n g m e m b e 础卸缸l c 曲璐s i t b j e c t i v e l y t km 幽d i sm o r e 删c a le s p e c i a l l y 谢l c n “ i sd i 伍c 眦t 0k n o wa 砸o r i 砌c h 缸巧s e t 、) l ，i l 王b em em o s ts u 呦l e 3 r n 血d l y ，e x a m i n et h er e la 重：i o n s h i p sb c 炳旧e nm i n e dr e 鲫l t 孤d 也em i r i i 妇m ms u p p o r t v 对u ew h e nu s i n gd i 在i e 瑚l 如z 巧t - n o 加够，锄d 卸a l y s i sm ei n _ f l u e 玳跫o fd i 丘b r e i l t t n o 脚帱o n 伍ea l g o r i 幽m sp t 羽融m 旃n k 猡啪r d s ：d a t am i i i i n g ；嬲s o c i a t i o nr u l e s ；缸蜀，s e tt l 瑚哆；c l u s t e r 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，酴 文串特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 侠月过的材 了明确的说 本人经 了解并同意 中作 完全 国家 图书馆、科研信息槐构、数据收集丰几构和本校图书馆等提供学位论文( 纸质文 本和电子文本) 以筷瑟焱捡索、查两荔姒授枳河赢文学出于宣扬、展览学校 学术发展和进行学术交流霉1 曾，黼乏曩翰j 采：零每翥槲：矽菇印、扫描争拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保窑内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：血刍奎遗 学位论文指导教师签名：二酷墨叁 2 0 暗年6 月。目 2 0d f 年6 月r d 目 河南大学研究生硕士学位论文第 页 第l 章绪论 近年来，髓着信息产业的快速发展，人们积累的数据越来越多。激增的数据 背后隐藏着许多重要信息，人们希望能够对其进行更高层次的分析，以便更好地 利用这些数据。传统的数据管理方法可以高效地实现数据的录入、查询、统计等 功能，但无法发现数据中存在的关系和规则，无法根据现有数据预测未来的发展 趋势，这就直接导致了“数据爆炸但知识贫乏 的现象。于是，人们不得不去寻 找一种新的方法和技术，使之能够智能地、自动地将这些数据转化处理为有用的 信息和知识。数据挖掘在这种背景下应运而生了。目前，它已成为计算机科学研 究中一个十分活跃的前沿领域，并在市场分析、金融投资、医疗卫生、环境保护、 产品制造和科学研究等许多领域获得了广泛的成功应用，取得了十分可观的社会 效益和经济效益。同时，数据挖掘的研究和应用对于人工智能这门前沿学科的发 展注入了新的活力，有力地促进了计算机科学朝着纵深方向顺利发展。 1 i 数据挖掘概述 1 1 1 数据挖掘的定义 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术。因 为与数据库密切相关，又称为数据库知识发现( k n o w l e d g ed i s c o v e f yi i ld l a t a b 硒e s ， k d d ) 。数据挖掘不但能够学习已有的知识，而且能够发现未知的知识；得到的知 识是“显式 的，既能为人所理解，又便于存储和应用，因此一出现就受到广泛 的重视。 从一开始到现在，人们给数据挖掘下过很多定义。随着数据挖掘研究的不断 深入，人们对数据挖掘的理解越来越全面，数据挖掘的定义也不断得到修改，其 中得到公认的是下述定义i l 】： 数据挖掘指的是从大量数据中提取出有效的、新颖的、潜在有用的，以及最 终可理解的模式的高级过程。 其中：数据是指一个有关事实，的集合( 如员工档案数据库中有关员工基本 情况的各条记录) ，它是用来描述事物有关方面的信息，是我们进一步发现知识的 原材料。 “新颖 指的是经过数据挖掘提取出的模式必须是新颖的，至少对系统来说 应该如此。模式是否新颖可以通过两个途径来衡量：其一是得到的数据，通过对 比当前得到的数据和以前的数据或期望得到的数据之间的比较来判断该模式的新 第2 页河南大学研究生硕士学位论文 颖程度；其二是通过其内部所包含的知识，通过对比发现的模式与已有的模式的 关系来判断。通常我们可以用一个函数来表示模式的新颖程度朋匮日，该函数的 返回值是逻辑值或是对模式五的新颖程度的一个判断数值。 “潜在有用指的是提取出的模式应该是有意义的，这可以通过某些函数的 值来衡量。通常，用“来表示模式互的有用程度，铲淝d 。 “可被人理解”指的是数据库中隐含的模式通过数据挖掘过程要以容易被人 理解的形式表现出来，帮助人们更好地了解数据库中所包含的信息。数据挖掘不 同于以往知识获取技术的一个特点是发现的知识是人们( 至少是领域专家) 可以理 解的，如“i f 1 h e n 韵形式，因此挖掘过程也是一个人机交互、螺旋上升的过 程。而以往的方法，如人工神经网络，不论是知识发现过程还是知识应用过程， 内部都是一个近“黑箱 过程。 模式：对于集合，中的数据，可以用语言三来描述其中数据的特性。表达式 艇，所描述的数据是集合f 的一个子集兄。只有当表达式比列举所有咒中 元素的描述方法更为简单时，我们才可称之为模式。如：“如果成绩在8 5 - 9 5 之间， 则成绩优秀可称为一个模式，而“如果成绩为8 5 、8 6 、8 7 、8 8 、8 9 、9 0 、9 l 、 9 2 、9 3 、9 4 或9 5 ，则成绩优秀”就不能称之为一个模式。 高级过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形 成一种螺旋式上升过程。数据挖掘是对数据进行更深层处理的过程，而不是仅仅 对数据进行加减求和等简单运算或查询，因此说它是一个高级的过程1 2 叫。 1 1 2 数据挖掘的技术与应用 数据挖掘涉及多个学科方向，主要包括：数据库、统计学和机器学习等。机 器学习的很多方法都已转变为数据挖掘方法【4 j 。 数据挖掘的研究对象主要是：关系数据库，这是典型的结构化数据。随着技 术的发展，数据挖掘对象逐步扩大到半结构化和非结构化数据，这主要是指文本 数据、图象和视频数据，以及w 曲数据等1 5 j 。 数据挖掘的任务主要有：关联分析、时序模式、聚类、偏差检测、预测1 6 j 。 数据挖掘的方法和技术主要有：归纳学习类( 基于信息论方法和基于集合论 方法，如粗糙集方法) 、仿生物技术类( 神经网络和遗传算法) 、公式发现类、统 计分析类、模糊数学类和可视化技术类1 6 j 。 数据挖掘的知识表现形式主要有：规则( 基于集合论得到的知识形式) 、决策 树( 基于信息论方法得到的知识) 、知识基( 浓缩数据) 、网络权值( 神经网络的 到的知识形式) 和公式嶂j 。 目前，数据挖掘技术应用最集中的领域包括金融、医疗保健、零售业、制造 河南大学研究生硕士学位论文第3 页 业、司法、工程与科学等。但每个领域又有其特定的应用问题和应用背景。例如， 股票经济人需要从大量股票行情变化的历史记录中发现其变化规律，以供预测其 趋势；超市的经理人员希望能从过去几年的销售记录中分析出顾客的购买习惯和 行为，以便及时变换营销策略；地质学家想通过分析地球资源卫星发回的大量数 据和照片来发现有开采价值的矿物资源等【7 j 。 1 2 数据挖掘的研究现状与发展趋势 近年来，数据挖掘引起研究者的极大关注，纷纷展开对数据挖掘技术的研究 和探索工作。下面，将分别从国外、国内两个方面对数据挖掘技术的研究现状进 行阐述，并对发展趋势进行探讨。 1 2 1 数据挖掘的研究现状 数据挖掘就是从大量数据中发现隐含的知识和规律。它既是一种知识获取技 术，又是一个数据处理过程。经过十几年的发展，对数据挖掘的研究从最初表面 豹、孤立的问题向系统的、全面的方向发展糊。目前，对数据挖掘的研究主要集中 在以下3 个方面： 1 数据挖掘的理论研究。目标是建立完整的数据挖掘理论体系，建立通用、 有效的处理模型，用科学的方法论指导发现知识的过程，使之成为一种主流技术。 近年来在这方面涌现了许多处理模型【9 】、系统框架l l 川舯e w o 呔) 和原型系统 1 1 b 蛳) 。 2 挖掘技术和算法韵研究翻。这也是目前最集中的研究领域( 从最近的数据 挖掘会议文献就可以看出这一点) 。这一方面的文献、资料也最丰富。由于数据挖 掘是应用需求推动下跨学科发展的产物，所以各个学科中的许多技术成果都可以 移植到数据挖掘中来。传统的统计方法【1 2 】【1 3 】、决策树f 1 4 1 、聚判15 1 、集合论，近年 来十分活跃的关联规则【1 6 。2 2 】、粗糙集理论口3 1 、人工神经网络【2 羽、遗传算法和进化 计算【2 9 】等在数据挖掘中都有应用。但是由于数据挖掘面对的是大量数据，因此这 些领域中的许多技术不能照搬照用。如遗传算法，当优化属性在上百个以后，计 算速度难以忍受。又如人工神经网络，由于获取的知识是以权值形式表示的隐含 形式，因此一般不适合单独应用于数据挖掘，往往需要与其它方法相结合。 3 应用研究。应用研究的划分一种是按照处理的数据类型分，产生了时间序 列数据挖掘【17 】【3 0 1 、空间数据挖掘f 3 1 】【3 2 】、文本数据挖掘例等。应用研究的另一种划 分是按照应用领域，如股票价格分析与预测，金融风险分析i 蚓，信用卡欺诈分析， 气象预报，生物工程【3 5 】【3 q 等。随着h l ：t e m e t 的普及与发展，w 曲挖掘【3 7 1 、通信分析 警告、网络入侵检测1 3 8 】等已成十分活跃的应用领域研究方向。 第4 页河南大学研究生硕士学位论文 自1 9 9 3 年r 舢删等首次提出挖掘交易数据库中项目集间的关联规则【1 6 】问 题以来，许多研究人员对关联规则问题进行了大量的研究，代表性的工作有：数 量关联规则【3 9 1 ，周期性关联规则( c y d i ca s s o c i 撕蚰m d e s ) 【4 2 】，负关联规则【4 3 】，比 例规则( r 越i or - u l e s ) 即l 【4 5 1 ，弱比例规则( w 宅a kr 面or 柚e s 严6 l 【4 7 1 ，序规则( o r d i n 面 缸s o c i 撕o nr u l e s ) o 删、模糊关联规则【4 9 侧等，其它类型的模式还包括闭项集( c l o s e d e m s e t ) 【5 7 6 1 1 、最大项集o a x i m a l c l u e n ti t c m s e t ) 1 6 1 缶5 1 、显露模式【碉等。 目前国内有许多高校和科研单位正在从事数据挖掘的基础理论和应用研究， 如清华大学利用概念格对数据挖掘的研究、北京大学对数据立方体的研究、中国 科技大学对序列模式的研究以及系统工程研究所、上海交通大学、华中理工大学、 复旦大学、浙江大学等对关联规则的研究等。 1 2 2 数据挖掘的发展趋势 当前，数据挖掘和知识发现的研究方兴未艾，其研究与开发的总体水平相当 于数据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询语言等理论和方法的指导。鉴于数据、数据挖掘任务和数据挖掘方法的多样 性，给数据挖掘技术提出了许多挑战性的课题，这些课题包括： l 、数据挖掘应用的探索； 2 、可伸缩的方法； 3 、交互式发现； 4 、 与数据库系统、数据仓库系统和w 曲数据库系统的集成： 5 、数据挖掘语言的标准化； 6 、可视化数据挖掘； 7 、复杂数据类型挖掘； 8 、w 曲挖掘，隐私保护和信息安全等。 1 3 课题来源与本文的研究内容 本课题来源于河南省高校杰出科研人才创新工程项目“量化关联规则及其在 医疗数据分析中的应用。该项目的研究目标：根据医疗数据的特点，对传统的量 化关联规则模型适当改造，设计并实现医疗数据挖掘系统。 自s r i k a n t 和r a g 跚a 了提出量化关联规则1 3 9 j 以来，许多研究人员对该问 题进行了大量研究。如何划分区间是实现量化关联规则挖掘问题到布尔关联规则 挖掘问题转化的关键。当区间的范围太窄对，则可能使每个区间对应的属性的支 持度很低，而出现“最小支持度 问题。而区间的范围太宽时，则可能使每个区 间对应的属性的置信度很低，而出现“最小置信度问题”。 河南大学研究生硕士学位论文第5 页 医疗信息主要包括体征参数、化验结果等纯数据，脑电、心电等信号，b 超、 c t 等图像，病人的身份记录、症状描述等文字，以及用于科普教育的动画、语音 和视频信息，具有信息容量大、数据类型复杂、冗余空缺值多、内容关联繁琐等 特点。医疗信息所具有的这些特点，使得医疗数据挖掘与普通的数据挖掘存在较 大差异，决定了医疗数据挖掘的特殊性。医疗数据还具有模糊性、不完整性和带 有噪声性，挖掘前必须对这些信息进行清理和过滤。 模糊关联规则【4 9 巧6 j 可以认为是对区间划分的一种改进，适于处理具有模糊的、 不完整的、具有噪声的医疗数据。然而，现有模糊关联规则模型中，多数存在如 下不完善之处： l 、挖掘出的模糊关联规则数目巨大，且挖掘结果中包含很多“常识”，因而， 需要构建新的模糊关联规则兴趣性度量框架，进行“过滤 。 2 、属性值域上的模糊划分或模糊集常利用专家知识人为定义。对于缺乏先验 知识的测试数据，该方法将无法给出有意义的模糊划分或模糊集。 本文主要针对以上两个问题进行研究，内容如下： l 、针对模糊关联规则数量问题，提出了一种新的支持度定义形式，建立了规 则兴趣性度量框架，构造了一个新的模糊关联规则挖掘模型，并设计了基于a p r i 丽 框架的宽度优先算法，有效地解决了模糊关联规则挖掘中产生大量规则的问题。 2 、针对模糊关联规则中确定隶属函数的问题，借鉴f c m 算法，提出了一种构 造隶属函数的新方法。该方法构造出的隶属函数能够体现数据的分布。当模糊数 据挖掘技术应用于缺乏先验知识的领域时，该方法将发挥重要作用。 1 4 全文的组织结构 正文共分为四章，各章节内容安排如下： 第一章为绪论，探讨了数据挖掘的的定义、研究意义、研究现状、课题来源 和研究内容，并给出论文的整体组织结构。 第二章为关联规则挖掘。首先引出了关联规则，并介绍了关联规则的基本概 念、性质，接着分析了关联规则的挖掘算法。 第三章为模糊关联规则。介绍了模糊理论的基本概念、基本运算与性质、模 糊关联规则的基本概念、系统分析了现有模糊关联规则模型。 第四章，针对已有模型尚未完善之处，提出了一种新的模糊关联规则模型， 设计了挖掘模糊关联规则的f f p 算法，实验表明该算法是有效的。 在总结与展望中，总结了取得的研究成果并指出后续工作的方向。 第6 页河南大学研究生硕士学位论文 第2 章关联规则挖掘 关联规则挖掘是数据挖掘的研究热点之一，用于发现隐藏在大型数据集中令 人感兴趣的联系，它是由舢辩w 面等人1 1 6 】于1 9 9 3 年在a c ms i g m o d 上首次提出的。 一个典型的关联规则的例子是：“9 0 的客户在购买牛奶和黄油的同时也购买了面 包。它的直观含义就是顾客在购买某些商品时有多大的倾向会购买另外韵一些商 品，这有助于指导商场货架的组织、布局和配套穿行路线的设计等。如今关联规 则的应用十分广泛，主要有：顾客购物模式分析、目录设计、商品广告邮寄分析、 追加销售、仓储规划、网络故障分析、站点访问模式分析、d n a 分析和保险理赔 分析等。 2 1 关联规则理论基础 2 置1 基本概念与问题描述 设，= 研，f ：，如 是聊个不同项目的集合，称为项集( i t e l i l s e t ) 。与任务相关的数 据d 是事务的集合，其中每个事务绳冲一些项目的集合，即丁c ，。每个事务t 都有一个唯一的标识符，称为t d 。如果对于，中的一个子集墨有xcr ，那么称 事务咆含k 项集所包含元素的个数称为项集长度，长度为鼬勺项集称为撇项集 承i t i 咖_ s e t ) 。假定把项按字典排列，七阶项集舸以表示为凰l 1 2 j x 嘲。对于项集 c = x u l ，若y 为聊阶项集，那么称y 是瑚聊阶扩展。 定义2 1 关联规则是描述数据库中数据项之间存在的潜在关系的规则，形式为 z y ，其中xc ，yc ，且x n y = 彩，脯为规则前件( a l i t e c e ( 1 e n t ) ，琢为规 则后件( c o n s e q 眦l t ) 。项集之间的关联表示：如果础现在一条交易中，那么琏这 条交易中同时出现的可能性比较高。 关联规则描述数据项同时出现的可能性，如何给这种可能性一个量化的标准 是一个需要明确的问题，这种可能性达到什么程度才能被认为是合理的。引入支 持度、置信度这两个概念，来定义关联规则在统计上的意义。 定义2 2 项集x 在事务集合d 中的支持数( s u p p o r tc o u n t ) 是d 中包含x 的 事务数，记作x 甜耐。x 在d 中的支持度就是x 的支持数与d 的总事务数之比， 即彳在d 中出现的概率，用符号p 心表示，x 的支持度记作s u p ) 。支持度阈值 表示项目在统计意义上的最低重要性，用符号脚表示。 定义2 3 事先给定一个懈，如果项集。椭支持度即g p 嬲，则称肋大项集 他r g ei t c n l s e t ) 或者频繁项集( 五嘲u e n ti t 锄s e t ) 。 河南大学研究生硕士学位论文第7 页 定义2 4 规则xjy 韵强度可以用它的支持度和置信度度量，这两种度量的 形式定义如下： 脚( x j 功= 脚( x u 玢 ( 2 疆) 仍纡“z j n ：竺坚! 翌 ( 2 2 ) 。 印( 爿) 规则x jy 的支持度表示瓜y 同时出现的可能性，而置信度确定y 在包含x 韵事务中出现的频繁程度。该值等于在x 出现的条件下y 也出现的概率，因此， 规则的置信度也可以用条件概率符号p y 表示。置信阈值表示规则在统计意义 上应满足的最低置信度，用符号珑c 表示。给定事务集合d ，关联规则发现是指找 出支持度大于等于嬲并且置信度大于等于m c 的所有规则。 应小心解释关联分析的结果，由于关联分析作出的推理并不必然蕴涵因果关 系。它只表示规则前件和后件中的项明显地同时出现。另一方面，因果关系需要 关于数据中原因和结果属性中的知识，且通常涉及长期出现的联系。 2 1 2 关联规则的性质及证明 性质1 设u = “， 为项集，且us ，u o ，q u ，对于给定的数 据库事务集d 和最小支持度嬲，如果u 为频繁项集，则q 也是频繁项集。 证明： 项集u 为频繁项集，且满足s 印( u ) 螂， 设数据库中包含项集u 的事务集d n 又q u 则数据库中包含u 的事务集d 0 一定包含q s 印( q ) s 印( u ) 嬲 必为频繁项集 性质2 设u = 缸1 ，“2 ，吆 为项集，且u 日j ，u g ，对于给定的数据库 事务集d 和最小支持度朋s ，如果u 为非频繁项集，则日也一定是非频繁项集。 证明：使用反证法，假设h 是频繁项集 ：u 呈h i ，u 仍 由性质1 可知项集【，为频繁项集( 与题设矛盾) 日是非频繁项集 性质3 设关联规则x j y ，满足x j ，】，冬，且x 彩，】，o ，x n y o ， 对于给定的最小支持度嬲和最小置信度掰c ，彳】，为强关联规则；如果】厂互】， 那么x jj ，也为强关联规则。 证明：( 1 ) 首先证明s 印( x j y - ) 榔 第8 页河南大学研究生硕士学位论文 x y 为强关联规则 卿( xj 玢= hz u l 厂船 ? p 冬蕾， 工x u p x u y y 由性质重知卿( x u y ，2 卿( x u 幻嬲 唧( x y m s ( 2 证明删x j y 脱 ? 一硝) = 笔署舢。 由( 1 ) 知苫妒( x u y 鼬烈x u d 塑! 墨! 翌l o o ! 翌坚! 塑l o s 印( x 、s 印x 、 删彳j y ) 叭x j y ) ? x j y 为强关联规则且砍x j 功朋c 训x j y ) 删x jy ) 批 综合以上( 1 ) ，( 2 ) 知xjy 也为强关联规则 性质4 设关联规则x l ，满足，= x uy 且x g ，y 圆，x n y ：g ， 对于给定的最小支持度，嬲和最小置信度批的强关联规则；如果x 刀，满足 ，= f u y 且x 彩，y o ，x n 】，= o ，那么x j y 也为满足给定条件的强 关联规则。 证明：z j y 是强关联规则 印( x j y ) 芝嬲 且 矿( x 】厂) 朋c 。z j 且，= x u y 且x a ，矿彩，x 厂、】，= a 卿( 幻s 妒( x ) ：l = xu y ，= xu y 卿( x u d = 卿( x ? u 】，) 河南大学研究生硕士学位论文第9 页 - 婴( 茎：兰2 1 0 0 丝! 茎! 塑1 0 0 s 妒( 彳)印( 叉) 工删x j 歪，之矾x n 嬲 工x j 王，也为满足给定条件的强关联规则 2 2 关联规则挖掘算法 关联规则挖掘问题是指从数据库中挖掘出支持度和置信度都大于等于给定嬲 和撇的关联规则。常分为两个子问题来解决： 找出支持度大于等于艄的项集( i t i 潍s 哟，这些项集称为频繁项集_ ( f 喇m l t c m s e t ) ， 从频繁项集中提取所有置信度大于等于历c 的规则。 第一个子问题的工作最艰巨，因为它需要大量的i o 操作，第二个子司题相对 容易。目前大多数的研究均集中在第一个子问题上。 2 2 1 宽度优先算法 邱r i o r i 【1 8 l 算法是由a g 跚 ，甜等人在1 9 9 4 年提出，采用广度优先搜索思想上的 算法。它具有很大的影响力，大多数算法都是以a p r i 耐算法为基础的。 该算法的基本思想是通过对数据库d 的多次扫描来发现所有的频繁项集。在 第七次扫描中只考虑具有同一长度七的所有项集。在后续的扫描中，首先以前一次 所发现的所有频繁项集为基础，生成所有新的候选项集( c 锄d i d a ! t ef t i 弧s e 招) 。然 后扫描数据库d ，计算这些候选项集的支持度，最后确定候选项集中哪些可成为 频繁项集。重复上述过程直到再也产生不出新的频繁项集。 下面给出一个样本事务数据库( 见表2 1 ) ，并对它实施a 两o r i 算法。 设朋鳓5 ，首先遍历d 一次，统计每个项目出现的次数，得到1 候选项集c 1 ， 根据给定的朋s 得到1 频繁集1 = 八b ，c ，e ) ，按字典顺序连接上l 的所有元素对形 成2 一候选集c 2 = a b ，a c ，a e ，b c ，b e ，c e ) 。再次遍历d ，计算出c 2 中每一 个元素在d 中出现的次数，并根据嬲- 确定三2 = “牛奶”是单维关联规则，因为它只涉及一个维b u y s 。 如果关联规则涉及两个或多个谓词或维，如维加筘，翩p 矽舭珊蝴以和 硼s 细凇r 黝嘲弦供则它是多维关联规则。如规则： 秽e 瓦“3 0 - 4 0 ”) 八f 聆朋口k 4 2 五“8 跫) 6 删“确咖陀舳砌f ：f ：d k 形，) 是一个多维关联规则，因为它涉及三个维q 纷觑聊p 和6 m 声。 单维关联规则展示的是维内联系；而多维关联规则展示的是维间联系。 3 、根据规则集所涉及的抽象层，关联规则可以分为单层的和多层的。 有些挖掘关联规则的方法可以在不同的抽象层发现规则。例如，假定挖掘的 关联规则集包含下面规则： 孵( 墨“3 0 3 4 ”) j6 别咿“鲫矽印彬髀妇一 孵伐“3 0 3 4 ”) j6 缈“删砒，) 在上面的两个规则中，购买的商品涉及不同的抽象层( 即“硎豫纪广在比 妞p 玉叩啤，锄矿高的抽象层) 。我们称所挖掘的规则集由多层关联规则组成。反 之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含 单层关联规则。 2 4 小结 本章首先给出了关联规则的基本概念及性质，接着讨论了关联规则的各种挖 掘算法：宽度优先算法、深度优先算法、抽样算法、增量式更新算法，并对各种 方法进行了详细分析，最后介绍了关联规则的分类。 河南大学研究生硕士学位论文第13 页 3 重引言 第3 章模糊关联规则 作为数据挖掘一个重要研究领域，关联规则挖掘自1 9 9 3 年由趣删6 j 等提出 以后，就引起广泛关注。关联规则的发现任务就是在给定的事务集中，挖掘出满足 用户指定的嬲和肌c 的关联规则。传统的关联规则挖掘算法局限于处理非对称二元 属性，挖掘的结果是布尔关联规则，典型算法有a p r i o r i l 捌，和f p 一印w t h l 2 2 j 等。然而 科学计算和商业领域的数据库有着丰富的数据类型，如数值型、枚举型等，文献p 刿 提出了挖掘量化关联规则的算法，思路是将连续属性划分为区间，然后用a p r i o d 算法进行处理。该方法很容易出现“c a t i m 2 2 ”问题： l 、最小支持度问题：如果区间划分过小，即区间划分的个数过多时，会造成 每一个单个区间的支持率都很低，相应地也会使包含此区间的规则的支持率很低， 从而造成规则产生数量过少。 2 、最小置信度问题：将值划分成区间时，总会有一些信息丢失。一些规则可 能当前件中的一个数量属性是由单个值构成就具有最小信任度，这样信息丢失会 随着区间变大而增加。 区间划分方法有两种，一种方法是将属性的定义域划分成离散的、互不重叠 的区间。区间划分会将边界附近的潜在元素排斥在外，从而使有价值的关联规则 却因区间的划分不合理而无法得到。例如，在图3 1 中，如果属性“年龄”按照等 距划分，得到区间【0 ，1 0 】，【1 1 ，2 0 】，【2 1 ，3 0 】，【3 l ，4 0 】，【4 l ，5 0 】。由于属性集中在【1 9 ，2 1 】， 王3 1 ，3 3 】附近，虽然区间的边界周围的值出现的频率很高，但f 2 1 ，3 0 】仍然没有足够的 支持度。 图3 1 等区间划分 另外一种方法是将属性定义域划分成重叠的区间，则处于边界附近的元素就 同时处于两个区间，由于这些元素同时对两个区间做贡献，就有可能造成过分强 ， j 6 4 2 ， 眈 。 薯圣 第14 页河南大学研究生硕士学位论文 豹区间交叉元素，从而会导致过分强调某些区间的意义。 区间划分方法存在边界过硬缺陷主要是由经典集合理论造成的，一个元素只 能属于或不属于给定韵集合。而在模糊集理论中，允许一个元素以一定的值隶属 于给定的集合，模糊集能在集合元素和非集合元素之间提供平滑的变迁，并较好 地实现连续量和离散量之间的转换。 3 2 模糊集理论概论 3 2 要基本概念 考虑到现实世界中很多事物的分类边界是不分明的，而这种不分明的划分在 人们的识别、判断和认知过程中起着重要作用，为了用数学的方法来处理这种问 题，扎德( l a z a d e h ) 于1 9 6 5 年提出了模糊集合的概念。用隶属函数( m e n l b e r s h i p 删o n ) 来刻画处于中介过渡的事物对差异双方所具有的倾向性。可以认为隶属 函数是普通集合中特征集合中特征函数的推广。当将特征函数的值域由 o ，l 二值 扩展到f 0 ，1 】区间时，就描述了一个模糊集合，本节内容主要取自f 6 7 】。 定义3 2 1 设a 是论域x 到f o ，l 】的一个映射，即： a ：x 专砷l j ，xha ( x ) 称a 是x 上的f u z 巧集，a o ) 称为f u z 巧集天的隶属函数 x 的全体f u z z y 集所构成的集合记为伊 o k e 纠皇 x i x x ，彳x = l 分别成s u p 凹、k e 叫为a 的支集( s u p p o r t ) 与核( k 锄e 1 ) 。跚p p a l 【e r a 分别称为a 的 边界( b 0 1 m d a 巧) 。当k 刚= g 时，称a 为正规f u z 巧集( n o m a l 如z 巧s e t ) 。 定义3 2 3 对于有限集x 上的f u z z y 集a ，a 的势( c a r d i 枷i 哆) 阻i 定义为： 1 4 l - 彳( z ) “； j i i i _ 罢成为模糊集a 的相对势。 陋l 定义3 2 4 若彳歹( x ，而口砷，1 】，记 4 = 缸x l 彳( 功田 称4 为f u z 巧集a 的a - 截氧口c ms 哟，或称为a 的口一水平氧口i e v e ls e t ) 。而 河南大学研究生硕士学位论文第15 页 称 硅= x x f 彳( 习 口 为呦集a 的强口戡氧s t c i r 0 i 塔岔c 哦s 哟，或称为a 的强口- 水平集或a 一开截 集( 姗口删s 哟；口称为闽值m 嘴s h o m dv m u c ) 或置信水l i e fl e v d 。也是 经典集合。 3 2 2 基本运算及性质 定义3 2 5 设五曰夕( z ，分别称呦集彳u 致爿n 曰为a 与b 的并( u n i o n ) 与交( i n t 删o n ) ，而称f u z 巧集彳。为a 的补集或余集( c o m p l e m 删。其中1 坛工， ( 彳u 召) ( x ) = m a x 4 ( x ) ，b ( x ) ) = 4 ( x ) vb ( x ) ( 彳n 丑) ( x ) = 瑚i n 彳( x ) ，8 ( x ) = 么( x ) 人b ( x ( 4 。) ( x ) = l 一月( x ) 定理3 2 1 设彳，& c 歹( x ) ，则夕( x ) 上的运算具有下列运算规律： ( 1 ) 幂等律u 爿= 4 ，么n4 = 彳； ( 2 ) 交换律彳u 口= 曰u 彳，彳n 曰= 曰厂、彳； ( 3 ) 结合律4 u ( 8 u c ) = 彳u 艿) u c ，4 厂、( 召n c ) = ( 爿r 、艿) n c ； ( 4 ) 分配律彳u ( 艿厂、c ) = ( 彳u 艿) n ( 4 u c ) ， 彳r 、( 曰u c ) = ( 4 n 动u ( 彳n c ) ； _ ( 5 ) 吸收律彳u ( 彳n b ) = 爿，彳n ( 彳u 县) = 么； ( 6 ) 复原律( 彳。) 。= 彳； ( 7 ) 对偶律( 么u 曰) 。= 彳。n 萨，( 彳r 、砂= u ； 3 2 3 乒模与扣余模 定义3 2 6 映射r ：【o ，1 】【o ，1 卜争砷，l 】，如果比，6 ，c ，d 【o ，1 】满足条件： ( 1 ) 交换律r ( 口，6 ) = 丁( 6 ，口) ； ( 2 ) 结合律丁( 丁( 口，6 ) ，c ) = 丁( 口，2 ( 6 ，f ) ) ； ( 3 ) 单调性口c ，6 d j r ( 口，6 ) 丁( c ，d ) ； ( 4 ) 边界条件r ( 1 ，口) = 口； 则称，为扣模( 扣n o m ) ，r ( 口，6 ) 也可写成口乃。 定义3 2 7 映射s ：，1 】【o ，l 】p ，l 】，如果v 口，6 ，c ，d 【o ，1 】满足条件： ( 重) 交换律s ( 臼，6 ) = s ( 6 ，a ) ； ( 2 ) 结合律s _ ( s ( 口，6 ) ，c ) = s ( 口，s p ，c ) ) ； ( 3 ) 单调性口c ，6 d = ，s ( 口，6 ) s ( c ，d ) ； 第16 页河南大学研究生硕士学位论文 ( 4 ) 边界条件l ，口) = 口； 则称s 为卜余模( 砌珊) 或争模( s - n o 瑚) ，s ，6 ) 也可写成口硒。 驷，l 】上的二元运算称为f 把巧算子( 娩巧o p e 斌。玲，t - 模与t - 余模是t 0 ，l i 上 豹呦算子。对任意口，易他1 1 ，令口 6 = m i l l ( 口，易) ，口v 6 = m a ) 【口，6 。易证 ，v 分别是f 0 ，玎上得扣模与乒余模，人，v 常称为躺算子，因此，扣模与扣余模也可 视为2 射e h 算子的推广。 下面是常用到的一些t 模算子： 1 ) 代数积口6 = 幻 ( 2 ) 有界积口0 6 = n 翰x ( o ，口+ 6 一l ( 3 ) 喇c 积 = 譬 口= l 6 = l 口l 且6 l 4 ) e i n s t e i n 积 动 口占6 = 二= _ 一 l + ( 1 一口) ( 1 6 ) 3 2 4 模糊集理论与关联规则的整合 关联规则通常应用于购物篮数据分析，但数据库中常包含数值信息，如一个 顾客的购买记录通常包含了其所买商品的品名及相应的数量、单价等。传统的关 联规则挖掘模型常只考虑记录中的离散型信息，而忽略与其相关的数值信息。 关联规则挖掘连续型数据集的方法是将其转化成布尔型。该方法常产生“尖 锐边界”问题，不能很好地吻合现实中的模糊现象。引入模糊集概念，文献【5 2 】利 把连续属性划分为若干个模糊子集。关联规则将不在局限于挖掘布尔型和离散型 的数据集，拓宽了关联规则的挖掘范围。 3 3 模糊关联规则 在传统的关联规则挖掘中，事务丁对模式p 要么支持，要么不支持，项集x 支持度的定义为事务数据库中包含项集x 的事务在整个数据库中所占的比例( 即 项集x 在数据库中出现的频率) 。然而在一些情况下，这种事务对模式支持的简单 形式不再适用。如在规则“花眼j 老人”中，规则的后件是一个模糊的概念，具 有明显的不确定性。不能定量地用某个具体的年龄来描述老人这个对象。因而， 记录对模式的支持也应具有模糊性，在进行这种关联规则挖掘时，这种模糊性必 河南大学研究生硕士学位论文第17 页 须考虑在内。 3 3 1 基本溉念 下面为模糊关联规则挖掘中的一些基本概念，具体内容参见文献【5 6 】。 若，= 五，毛，厶 是数据库d 韵属性集，每一个属性，( 1 i 朋) ，有9 ，个模 糊隶属函数与之相关。原数据库d 可以转化为模糊数据库d ，它的属性集为 ，= 霹，砰，帮，乏，毋，艺，毋 ，所有新属性的值域为【o ，1 】。 定义3 3 1 模糊项集x = “，恐， ct ，第1 条记录对模糊项集x 的支持 度定义如下： 慨( = 五，人黾人 或蹶= 毪吆靠 其中，x 是模糊项目x ，在第f 条记录的值，x 【o ，1 】，j = l ，2 ，托， 歹= l ，2 ，p 。 定义3 3 2 模糊项集x = 而，屯， c ，整个数据集对x 的支持度定义如 下： 慨( 幻 姒幻2 苛 其中，1d ，i 模糊事务数据库的大小。 给定最小支持度嬲，若模糊项集的支持度大于等于膦，称x 为频繁模糊项集。 定义3 3 3 模糊关联规则是形式为xjy 的蕴涵式，x 被称作模糊关联规则的 前件，y 被称作模糊关联规则的后件。其中，彳，】，sj r 且x a ，】，g ， x 厂、】，o ，z = x uy 中不包括来自同一属性的相关项， 定义3 3 4 模糊关联规则xjl ，的支持度却( xjy ) 和置信度 c ：d 旷( x j l ，) 分别定义为： 跏( x y = 脚( x u y 鲥( 精班鬻 其中，x j r ，y 量j r 且x o ，y o ，x r 、y f 2 j ，j = x uy 中不包括来 自同一属性的相关项。 为挖掘有效的模糊关联规则，用户必须预先给定最小支持度脚和最小置信 度掰c 。模糊关联规则的挖掘问题就是对给定的数据库d 和量化属性域上定义的模 糊项目集7 ，发现支持度和置信度分别大于等于，雕和历c 的所有模糊关联规则。 第 8 页河南大学研究生硕士学位论文 3 3 2 模糊关联规则现有模型 现有的模糊关联规则的模型可以分为以下三类： 1 、对经典关联规则中的支持度和置信度的定义进行扩展，将之用于模糊关联 规则嗍【5 0 j 【5 2 j 。对于一条模糊关联规则xjl ，其支持度和置信度为： 脚( x j 的= 脚( x u d ( 3 1 ) 州( 柏班鼍筹 限2 ) 其中，x ，l ，s ，r 且x a ，l ，a ，x 厂、y o ，= 并u y 中不包括来 自同一属性的相关项。l 驯为模糊数据库的大小，选用的扣模算子为“取小”或“直 积”。这是最常用的一种方法。 文献【4 9 】中运用模糊运算和截集的概念，重新定义了支持度和置信度，并给出 了模糊关联规则挖掘算法。可等价地表示为，项集x = 辆，恐，苫p cz r ，第j 条 记录对项集彳的支持度