基于改进FP-树的最大频繁项目集的研究

基于改进FP-树的最大频繁项目集的研究 哈尔滨理工大学 硕士学位论文 基于改进FP-树的最大频繁项目集研究 姓名:朱孟杰 申请学位级别:硕士 专业:计算机应用技术 指导教师:谢志强 20090301 哈尔滨理工大学工学硕士学位论文 基于改进FP-树的最大频繁项目集研究 摘要 数据挖掘是当今人工智能和数据库研究方面最富活力的领域之一。数据 挖掘是指从大量的数据中发现潜在的、有用的知识的过程。关联规则挖掘则 是数据挖掘的一个最主要研究内容，而如何提高挖掘算法的效率是关联规则 数据挖掘的核心问。 Pattern，FP 挖掘 FP(growth算法是目前最有效的频繁模式 Frequent 算法之一，由于其在挖掘最大项目集时要递归的生成大量的条件FP(树，存 在时空效率不高的问题。本文通过研究，结合改进的FP(树，提出了一种快 速挖掘最大项目集的算法。该算法利用改进的FP(树是单向的且每个节点只 保留指向父节点的指针，可以节约了大量的存储空间:同时引入项目序列集 和它的基本操作，使挖掘最大频繁项目集时不生成含大量的候选项目的集合 或条件FP(树，可以快速的挖掘出所有的最大频繁项目集。实例分析算法是 可行和高效的。 敏感性关联规则的隐藏在当前数据挖掘领域中是一个重要的研究问题， 目标是在保证敏感规则不被挖掘出的条件下，最大程度地保持原始数据集的 其他特征。原有的基于对原始数据集中事务的修改，会产生大量的I,0 操作。为了提高对敏感数据的保护程度和挖掘结果的准确性，本文利用FP( 树存储了与事务数据库相关的全部信息，提出了一种快速隐藏敏感性关联规 则的方法:首先快速挖掘出最大频繁项目集，确定敏感性关联规则，然后删 去支持敏感性规则的频繁项目集，并对FP(树进行相应的更新，根据对更新 的FP(树反向挖掘生成新的不包含敏感关联规则的事务数据库。实例和理论 分析表明，该方法是正确和高效的。 关键词数据挖掘:关联规则;最大频繁项目集;频繁模式树;敏感关联规 则 哈尔滨理T大学工学硕十学位论文 ResearchonimumItemsetsBasedon Frequent FP―tree Improved Abstract Data isoneof most Mining the activeresearch inthefields fields，especially ofartificial and database(Dataisakindof whichCan intelligence Mining process discover useful frommassivedata(Theassociationrule potentialknowledge isamainresearchofdata the ofthe mining aspect mining，anddiscovery itemsetsisa oftheassociationrule frequent keyproblem mining( isoneof themostefficient FP―growthalgorithm frequent mining pattern must a numberof methods(However,FP-growthalgorithmgenerate huge conditionalFP-trees in of imum recursivelyprocessesmining frequent，SO the ofitis this efficientimum efficiencyunsatisfactory(Inpaper,allmining is unifiesthe FP―treeis frequentalgorithmproposed，it FP-tree，the improvement a treeandthereisno to its in childreneach it one-way pointers node， SO point cailsavethemassivememories setofitem and space，byintroducing sequences its the doesn’t conditionalFP―treeora number algorithm operators generate large ofnumberofcandidatesetsin can all miningprocess，whichconvenientlyget imumitemsets(The is andeffectiveness frequent exampleanalysisfeasibility the of algorithm( Thesensitiveassociationrule isa issueinthedata hidingveryimportant ofwhichistomaintainothercharacteristicsofthe domain，the mining goal datasetunderthe the rule not primitive conditionthat sensitiveshouldbe method discovered(The basedonthe of transactiondata original changesoriginal will massiveI,0 ordertoenhancethe extensions generate operations(In protect and the ofsensitivedata toensure ofthe theFP- accuracyminingresults，USeS treetostorealloftheinformationtotransaction related databaseandproposes ??II?? of mine of the associationrule:firstall， to aneffeetivemethod hidingsensitivity item of setdownthe imumof sets;secondall，to the frequent rapidly setswhich deletethe item support sensitiveassociationrules;then，to frequent ofassociation to FP―tree the rules，andupdate sensitivity is newtransactiondatabase the FP-tree，a generated，in miningupdated reversely arenotcontained(Theandthe associationrules examples whichsensitive thismethodiS andefficient( theoreticalshowthat right analysis data rule，imumfrequent mining，association Keywords associationrule tree，sensitive pattern (III 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明:此处所提交的硕士学位论文《基于改进FP(树的最大频繁 项目集研究》，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已 在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名:球立立 日期:z一7年三月(Z。日 哈尔滨理工大学硕士学位论文使用授权书 《基于改进FP(树的最大频繁项目集研究》系本人在哈尔滨理工大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨 理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解 哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门 提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以 采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在 年解密后适用授权书。 不保密彭 请在以上相应方框内打? 作者签名:珠童立 日期:文1年岁月加日 别磁轹带卅够 嗍。叩”肋日 哈尔滨理工大学T学硕:上学位论文 第1章绪论 1(1数据挖掘概述 随着信息技术特别是网络和通讯技术的飞速发展，人们产生、收集和传输 数据的能力迅速增长;成千上万的数据库被广泛应用到企业、银行、政府和科 研院校等各个领域。一方面，日益成熟的数据库管理系统为这些海量数据的存 储和管理提供了技术保证;另一方面，计算机网络技术的迅速发展和规模的不 断扩大，为数据的传输和远程交互提供了先进的技术手段，特别是国际互联网 更是将全球的信息资源纳入了一个共同的数据库系统之中。 在数据存储和管理能力得到不断提高的同时，人们处理与分析数据的能 力 却显得相当有限，互联网的迅速兴起更加剧了“数据爆炸’’而“知识匿乏’’的 趋势。人们无法用传统的数据分析手段来理解并有效地使用这些海量数据，由 此导致了越来越严重的数据灾难。由于快速的数据产生和收集技术与逐渐落伍 的数据分析方法之间形成的强烈对比，急需新的技术来自动地和智能地分析这 些海量数据，从而使这些宝贵的数据资源得以充分的利用。知识发现与数据挖 掘就在这一背景下应运而生并得到迅速发展，它的出现为自动和智能地把海量 的数据转化成有用的信息和知识提供了强有力的手段。 糊的、随机的数据中，提取隐含其中的、事先人们不知道的、具有潜在利用价 值的信息和知识的过程n一1。它是一门涉及面很广的交叉学科，包括了数据 库、机器学习、神经网络、数理统计、模式识别、粗糙集、模糊数学等相关技 术。 由于数据挖掘是-f]受到来自各种不同领域的研究者关注的交叉性学科， 因此演化出了很多不同的术语名称。其中，最常用的术语是“知识发现"和 “数据挖掘"。相对来讲，数据挖掘主要流行于统计界、数据分析、数据库和 管理信息系统界;而知识发现则主要流行于人工智能和机器学习界b1。 1(1(1数据挖掘的产生发展 1(1(1(1数据挖掘产生背景数据挖掘只所以吸引专家学者的研究兴趣和引起 商业的广泛关注，主要在于大型数据系统的广泛使用和把数据转换成有用知识 哈尔滨理工大学工学硕士学位论文 的迫切需要。20世纪60年代，为了适应适应信息的电子化要求，信息技术一 直从简单的文件处理系统向有效的数据库系统变革。70年代数据库系统的三个 主要模式:层次、网络和关系型数据库的研究和开发取得了重要进展。80年 代，关系型数据库及其相关的数据模型工具、数据索引及数据组织技术被广泛 采用，并且成为了整个数据库研究和开发的重要标志。因此，随着数据的膨胀 和技术环境的进步，对联机决策和分析等高级信息处理的要求越来越迫切。在 强大的商业需求的驱动下，商家开始注意到有效地解决大容量数据的利用问题 具有巨大的商机。学者开始研究从大容量数据集中获取有用信息和知识的方 法。因此，在20世纪80年代后期，产生了数据仓库和数据挖掘等信息处理思 想。归纳起来数据挖掘产生的技术背景，下列相关技术的发展起到了决定性的 作用:数据库、数据仓库和intemet等信息技术的发展。数据库技术从20世纪 80年代开始，已经得到广泛普及和应用，高性能关系型数据库引擎以及相关的 分布式查询、并发控制等技术的使用，已经提升了数据库的应用能力。丰富多 彩的数据存储、管理以及访问技术的发展，为数据挖掘技术的研究和应用提供 了丰富的土壤;计算机性能的提高和先进体系结构的发展，计算机性能的提高 和新近的体系结构的发展使数据挖掘技术的研究和应用成为可能;统计学和人 工智能等方法在数据分析的研究和应用，数据挖掘研究在继承已有的人工智能 相关领域的研究成果的集成上，摆脱了以前的研究模式，真正开始客观地从数 据集中发现蕴藏的知识。 1(1(1(2数据挖掘的发展趋势数据挖掘与知识发现方法又经过数年的研 究和实 践，数据挖掘技术已经吸收了许多学科的最新研究成果而形成了独具特色的研 究分支。数据挖掘的研究和应用具有很大的挑战性。分析目前的研究和应用现 状，数据挖掘在如下几个方面进行了重点展开H1: 1(数据挖掘技术与特定商业逻辑的平滑集成问题 数据挖掘和知识发现 技术的广阔应用前景，需要有效和显著的应用实例来证明。因此包括领域知识 对行业或企业知识挖掘的约束与指导、商业逻辑有机嵌入数据挖掘过程等关键 课题，将是数据挖掘与知识发现技术研究和应用的重要方向。 2(数据挖掘技术与特定数据存储类型的适应问题 不同的数据存储方式 会影响数据挖掘的具体实现机制、目标定位、技术有效性等。针对不同数据存 储类型的特点，进行针对性研究是目前流行而且也是将来一段时间必须面对的 问题。 3(大型数据的选择与规格化问题数据挖掘技术是面向大型数据集的， 而源数据库种的数据是动态变化的。数据存在噪声、不确定性、信息丢失、信 哈尔滨理工大学工学硕上学位论文 息冗余、数据分布稀疏等问题，数据挖掘前的预处理是必须的，同时它又是面 向特定商业目标的，大量的数据需要选择性的利用，因此，针对特定挖掘问题 进行数据选择、针对特定挖掘方法进行数据规格化是无法回避的问题。 4(数据挖掘系统的构架与交互式挖掘技术 数据挖掘是在大量的源数据 集中发现潜在的、事先并不知道的知识，因此和用户交互式进行探索性挖掘是 必然的。这种交互可能发生在数据挖掘的各个不同的阶段，从不同角度不同粒 度进行交互。所以良好的交互式挖掘也是数据挖掘系统成功的前提。 5(数据挖掘语言与系统的可视化研究对联机事务处理应用来说，结构 化的查询语言SQL已经得到充分的发展，并成为支持数据库应用的重要基石。 对数据挖掘技术来说，开发相应的数据挖掘语言仍然是一件极富挑战工作。可 视化要求已经成为目前信息处理系统的必不可少技术，推动了主动进行知识发 现的作用。 6(数据挖掘理论与算法研究数据挖掘已经在继承和发展相关基础学科 去得了可喜的进步，新的理论不断被探索也促进了新的挖掘算法的产生，同时 研究针对大容量的有效和高效的算法。数据挖掘是人们长期对数据库技术研究 和开发的结果，同时，也是信息技术自然演化的结果。数据挖掘与传统分析工 具不同的是数据挖掘使用的是基于发现的方法，运用模式匹配和其它算法决定 数据之间的重要联系。数据挖掘算法的好坏将直接影响到所发现知识的好坏。 目前大多数的研究都集中在数据挖掘算法和应用上。 1(1(2数据挖掘技术与应用 数据挖掘的研究领域涉及广泛，主要包括数据库系统、人工智能、机器学 习、统计学和数据可视化等领域，其采用的技术也较多。在数据挖掘中，我们 很少采用一种工具或技术。对于一个给定的问题，数据本身的特点会影响如何 选择技术，因此，为了发现可能最好的模型，我们应使用多种技术或工具。下 面将对数据挖掘中经常采用的技术做简单介绍和分析。 1(神经网络人工神经网络啼3是模拟人类的形象直觉思维，是在生物神经 网络的基础上，根据生物神经元和神经网络的特点，通过简化、归纳、提炼总 结出来的一类并行处理网络。神经网络对于规模大而复杂的问题，如包含几 百 个相互作用的独立变量，可以有效地建立模型，因此人们对神经网络非常感兴 趣。它可用于解决数据挖掘中的分类问题 输出变量是离散的 和回归问题 输出变量是连续的 。 哈尔滨理丁大学工学硕上学位论文 2(决策树 决策树的基本思想是以信息论原理为基础，利用信息论中互 信息 信息增益 寻找数据库中具有最大信息量的字段，建立决策树的一个结 点。然后再根据字段的不同取值建立树的分支，在每个分支集中重复建立树的 下层结点和分支。这种方法实际上是依循信息论原理对数据库中存在的大量数 据进行信息量分析，在计算数据特征的互信息或信道容量的基础上提取出反 映 类别的重要特征。例如，用决策树把贷款申请者分成好的和不好的信用。用于 解决这类问题的一棵简单的决策树，它包含决策树的所有组成:决策节点、分 支和叶子m1。决策树也能很好地处理非数值型的数据。它能接受分组的数据， 这能减少数据转变的数量，并能使神经网络固有的独立变量的组合爆炸最小 化。 3(遗传算法遗传算法‘71就其本身来说并不是用来发现模式，只是用来指 导其它数据挖掘算法的学习过程，遗传算法为在解空间里寻找好的模型作指 导。遗传算法之所以这么称呼，其基本原理是:类比生物进化过程，每一代同 时存在许多不同的种群个体 染色体 。这些染色体的适应性以适应性函数(删 表征，染色体的保留与淘汰取决于它们对环境的适应能力，优胜劣汰。适应性 函数fix 的构成与目标函数密切相关，往往是目标函数的变种。遗传算子主要 有3种:选择 复制 算子、交叉 重组 算子和变异 突变 算子。遗传算 法可起到产生优良后代的作用，经过若干代遗传，将会得到满足要求的后代 问题的解 。例如，在建一个神经网络时，遗传算法能替代反向传播的方法 来调整权值。在这种情况一下，基因包含权值。另外，遗传算法能用来找到最 佳构造，这时基因包含隐含层的数目和每一层的结点数。 4(粗糙集方法 其基本原理是:将数据库中的行元素看成对象，将列元 素看成属性。设尺为等价关系，定义为不同对象在某个 或几个 属性上取值 相同。那些满足等价关系的对象构成集合，称为该等价关系R的等价类。设E 为条件属性上的等价类，设l，为决策属性上的等价类，则E和y存在3种情 况:】，包含E称为下近似;Y与E的交非空，称为上近似;Y与五的交为空， 称为无关。对下近似建立确定性规则，对上近似建立不确定规则 含可信 度 ，对无关情况则不存在规则。 5(可视化技术 数据可视化技术经常和其它的数据挖掘技术结合起来使 用，它能够对数据进行有效分析，其重要性是不能低估的。可视化技术是一种 图形显示技术阳1。例如，把数据库中多维数据变成多种图形，这对于揭 示数据 中内在本质以及分布规律起到很大的作用。对数据挖掘过程可视化，并进行人 机交互可提高数据挖掘的效果。 哈尔滨理工火学工学硕七学位论文 6(统计方法 用于非线性数据和含噪声的数据时具有更大的优越性，比 较适合于市场数据库的分析和建模，通过对市场数据库中行业数据的精密分 析，为市场人员提供顾客、用户、市场状况和市场走势等方面的分析结果。 除了以上的几种技术外，还有回归分析、判别分析等技术。 DM工具和软件己在各个部门得到很好的应用，并收到明显的效益。 1(金融方面 银行信用卡和保险行业，预测存款趋势，优化存,贷款策 略，用DM将市场分成有意义的群组和部门，从而协助市场经理和业务执行 人 员更好地集中于有促进作用的活动和设计新的市场运动。 2(客户关系管理方面DM能找出产品使用模式或协助了解客户行为，( 从而可以改进通道管理 如银行分支和ATM等 。又如，正确时间销售就是基 于客生活周期模型来实施的。 3(零售业,市场营销方面零售业,市场营销是数据挖掘技术应用最早也是 最重要的领域，DM用于顾客购货篮饽1的分析可以协助货架布置，促销活动时 间，促销商品组合以及了解滞销和畅销商品状况等商业活动。通过对一种厂家 商品在各连锁店的市场共享分析，容户统计以及历史状况的分析，可以确定销 售和广告业务的有效性n们。 4(过程控制,质量监督保证方面DM协助管理大数量变量之间的相互作 用，DM能自动发现出某些不正常的数据分布，暴露制造和装配操作过程中变 化情况和各种因素，从而协助质量工程师很快地注意到问题发生范围和采取改 正。 5(远程通讯部门远程通讯部门基于DM的分析，协助组织策略变更以 适应外部世界的变化，确定市场变化模式以指导销售。在网络容量利用方 面，DM能提供对客户类服务使用的结构和模式的了解，从而指导容量计划人 员对网络设施作出最佳投资决策。 6(化学,制药行业化学,制药行业从各种文献资料中自动抽取有关化学反 应的信息，发现新的有用化学成分。在遥感领域，针对每天从卫星上及其它方 面来的巨额数据，对气象预报，臭氧层监测等能起很大作用。 7(军事方面使用DM进行军事信息系统中的目标特征提取、态势关联 规则挖掘„1等。 总之，DM可广泛应用于银行金融、零售与批发、制造、保险、公共设 施、政府、教育、远程通讯、软件开发、运输等各个企事业单位及国防科研 匕。 哈尔滨理工大学工学硕士学位论文 1。1(3数据挖掘的数据来源 数据挖掘所依赖的数据来源多种多样，可以是常用的关系数据库、事务数 据库、文本数据库、多媒体数据库等，主要取决于用户的目的及所处的领域。 目前，数据挖掘的数据主要来源于关系数据库与数据仓库等。 1(关系数据库 随着数据库技术的飞速发展，在现有的业务系统中拥有 大量的数据库，如超市的客户购物数据库，销售部门的进、销、存数据库等。 但是随着时间的推移以及相应的业务的变化，这些数据库的数据格式会发生变 化，因此在对其进行数据挖掘时需要进行必要的整理。关系型数据库是数据挖 掘的主要应用数据源。关系型数据库的数据挖掘已经积累了很多方法和成果， 其中包含多维知识挖掘问题、多表挖掘和数量数据挖掘问题、多层知识挖掘、 知识评价问题、约束数据挖掘问题等。 2(数据仓库 随着数据仓库技术n羽的发展，数据仓库成为数据挖掘的一 个重要的数据来源。数据仓库中的数据在导入数据仓库时己经进行了相应的清 理，数据的不一致性问题都已经解决了，这样在进行数据挖掘时就没必要再进 行清理了。通常数据挖掘都要事先把数据从数据仓库中取到数据挖掘库或数据 集市中。数据挖掘库可能是数据仓库的一个逻辑子集，也可以是一个单独建立 的数据挖掘库。数据仓库中的数据从历史的观点提供信息，因此是理想的数据 挖掘存储体。数据挖掘不仅伴随数据仓库而产生，而且随着应用深入产生了 许 多新的课题。 3(事物数据库 事务数据库中的数据挖掘:事务数据库挖掘不仅可以直 接应用到诸如采购、销售、市场调查等这些商业活动中，而且在Web安全性 和效益分析、金融活动跟踪等诸多方面得到应用。通过特定的技术对事务数据 库进行挖掘，可以获得动态行为所蕴藏的关联、分类以及预测规则。 4(高级数据库 随着数据库技术的发展，数据库在各个领域得到了广泛 的应用。由原来单一关系的数据库发展到面向对象数据库、事务数据库、空间 数据库、对象关系数据库、文本数据库、多媒体数据库。同样，数据挖掘的数 据来源也可以来源于这些类型的数据库系统。 1(1(4数据挖掘的主要过程 数据挖掘是一个多阶段数据处理过程，如图1-1所示n引，主要包括以下几 个步骤: 哈尔滨理工大学t学硕|j二学位论文 第一步:了解应用领域的知识。在开始知识发现之前首先进行的同时也是 最重要的就是了解你的数据和业务问题。 第二步:数据集成与数据清洁。数据集成将与研究问题相关的多文件或多 数据库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊性， 纠正不一致，处理数据中的遗漏和噪声等。 第三步:数据归约与预处理。数据归约将得到数据集的压缩表示，在归约 后的数据集上挖掘将更有效，并产生相同或几乎相同的分析结果，从而提高数 据挖掘的质量。预处理则是针对特定的算法对数据进行有序的组织和排列。 第四步:选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能， 例如分类、聚类或关联规则挖掘等。 第五步:选择适合的数据挖掘算法进行数据挖掘。 第六步:模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的 表达。 第七步:知识的应用。 (啊盐 1 数据集成 弋 ,J 1 一 数据库 图卜1数据挖掘的基本过程 the ofdata Fig(1-1basicallyprocess mining 1(2数据挖掘的热点与难点 随着研究的深入，数据挖掘和知识发现已经取得了很多成果，仍面临着许 多困难与挑战?引: -7- 哈尔滨理工大学工学硕上学位论文 1(改进数据挖掘算法 现有的数据挖掘算法由于历史原因存在种种缺 陷，为了提高数据挖掘系统的可用性、可扩展性、高效性、需要对一些数据挖 掘算法进行改进。需要探索新的挖掘算法，以适应新知识环境下的数据挖掘。 例如关联规则中的最大项目集挖掘，如何提高算法的时空效率;针对原有算法 不能很好的处理复杂的数据类型，研究复杂数据类型挖掘的新方法。 2(应用的探索 目前正探索扩大其应用范围，如生物医学、考古等领域。 3(数据挖掘语言的标准化 数据挖掘语言的发展经过了数据挖掘查询语 言、数据挖掘模型语言和通用数据挖掘语言或标准数据挖掘语言三个阶段。在 通用数据挖掘语言的研究上取得了很大的进展，但还远没达到像8QL查询语 言的那种通用程度。实用的业界统一的标准语言将是未来数据挖掘语言努力的 目标。 4(可视化数据挖掘可视化是数据挖掘的研究方向之一，是从大量数据中 发现知识的有效途径。挖掘出来的各种规则是否能以一种简单明了的、图形化 的方式表达给终端用户，将直接影响用户对数据挖掘技术的兴趣，也将直接影 响到这门技术的发展前景。多维数据的可视化、多维数据挖掘任务的可视化、 模式可视化、模式比较和趋势分析可视化是进一步的研究目标。 5(Web挖掘随着计算机硬件和软件的升级，Web数据的结构也将会发 生变化，数据量将会更多更复杂。有关Web内容挖掘、Web日志挖掘和因特 网上的数据挖掘服务，将成为数据挖掘中一个最为重要和繁荣的子领域。 6(数据挖掘中的隐私保护与信息安全任何事情都有其两面性，数据挖掘 领域也不例外，在挖掘数据产生财富的同时，随之产生的就是隐私泄露和信息 安全的问题。1995年隐私保护与信息安全成为了数据挖掘的一个研究主题， 经过十几年的发展，仍不成熟，是一个研究的热点方向。 1(3本文研究的内容和意义 1(3(1课题来源 No(1152hq08 。 哈尔滨理工大学工学硕士学位论文 1(3(2本文研究的内容 本文针对以上问题中的第1和6点进行研究，主要工作如下: 挖掘最大频繁项目集挑战性在于数量巨大，算法的时空效率是关键，研究 出更加高效的适合挖掘大规模数据库的挖掘算法是本文研究的重要内容。针对 传统的Apriori及其改进算法，要多遍扫描数据库并产生大量的候选项集， JIAWEI 库，把数据集中的频繁信息压缩存入FP(树中，同时保留其中的关联信息， 可 以大大减少I,O操作。FP(growth算法是目前最有效的频繁模式挖掘算法之 一，但其在挖掘最大项目集时要递归的生成大量的条件FP(树，存在时空效率 不高的问题，于是结合改进的FP(树，设计一种快速挖掘最大项目集的算法。 首先对改进的FP(树的相关性质进行深入的研究，利用其相关的性质定理来设 计的最大频繁项目集算法，使算法能够大大的提高挖掘的时空效率，给出算法 的实例分析和比较。 敏感性关联规则的隐藏在当前数据挖掘领域中是一个十分重要的研究问 题，其目标是保证敏感规则不被挖掘出的条件下，最大程度地保持原始数据集 的其他特征。原有的方法基于对原始数据集中事务的修改，会产生大量的I,O 操作，为了提高对敏感数据的保护程度和挖掘结果的准确性，利用FP(树存储 事务数据库相关的全部信息，提出了一种快速隐藏敏感性关联规则的方法:首 先快速挖掘出最大频繁项目集，确定敏感性关联规则，然后删去支持敏感性规 则的频繁项目集，并对FP(树进行相应的更新，根据对更新的FP(树反向挖掘 生成新的不包含敏感关联规则的事务数据库。实例和理论分析表明该方法是正 确和高效的。 1(3(3本文研究的意义 关联规则问题是数据挖掘领域十分活跃的热点，也是数据挖掘中最重要的 一个分支，已经引起了数据库、人工智能、统计学、信息检索、可视化等诸多 研究领域的专家和研究机构的广泛重视，并取得了很多重要成果，关联规则挖 掘问题可以划分成两个子问题:发现频繁项目集和生成关联规则。发现频繁项 目集是关联规则挖掘和数列模式等数据挖掘应用中的关键技术和步骤。因此许 多研究都集中在频繁模式挖掘上，Apriori算法是关联规则挖掘的一个经典算 法，在数据挖掘中具有里程碑的作用，许多早期的研究大都采用类似A研 ori 哈尔滨理T大学工学硕士学位论文 的先产生候选集后进行测试的方法但是随着研究的深入，它的缺点也暴露出 来，它需要多次扫描数据库，需要很大的I,O负载，可能产生庞大的候选集。 growth算法，该算法采用FP一树存放数据库的主要信息，算法只需要扫描数据 库两次，使关键信息以FP(树的形式存放在内存中，避免了因多次扫描数据库 而带来的大量的I,O负载，它不需要产生候选集，从而减少了产生和测试候选 集需要耗费的大量时间并且采用分而治之的思想，在挖掘过程中大大减少了搜 果大项集的数量很多，并且如果由原数据库得到的FP(树的分支很多且分 支长 度很长时，该算法需要构造出数量巨大的条件FP(树，不仅费时而且占用大量 的空间，挖掘效率不高而且递归算法本身效率也较低，所以在挖掘大型数据库 的时占用内存大，运行速度慢，挖掘关联规则的挑战性在于数量巨大算法的效 率是关键，因此在利用FP(树数据结构优势的基础上研究出更加高效的适合挖 掘大规模数据库的挖掘算法，是目前数据挖掘研究的重要内容之一。 虽然频繁模式算法对于一些非稠密数据库能够取得很好的性能，但对于稠 密数据库或者支持度比较小时，频繁模式的数量会以指数形式增长，使得找出 所有的频繁模式成为不可能的任务，为了减少频繁模式中的冗余，人们采用了 各种方法，其中最主要的有挖掘频繁闭项目集和最大频繁项目集。其中最大频 繁项目集的规模最小，而且通过最大频繁项目集可以导出频繁闭项集和频繁项 目集，所以可以把发现频繁项目集的问题转化为发现最大频繁项目集的问题， 另外某些数据挖掘的应用中仅需发现最大频繁项目集，而不必发现频繁项目 集，因而发现最大频繁项目集对数据挖掘具有重大的意义。综上所述基于FP( 树的最大频繁项目集挖掘算法具有重要的研究和应用价值;快速隐藏敏感关联 规则是目前的一个新的热点问题，本文利用改进的FP(树作为一个中间层，能 够快速挖掘出最大频繁项目集同时对FP(树进行更新，反向挖掘出不包含最大 频繁项目集的数据库，对快速隐藏敏感性关联规则具有很大的意义。 1(4论文结构 第1章首先论述数据挖掘技术基本概念、产生发展、技术应用和数据来 源，然后介绍数据挖掘的挖掘过程及相关热点和难点问题，最后论述课题的来 源及论文主要研究内容及意义。 第2章介绍作为数据挖掘主要方法之一的关联规则挖掘的理论体系，详细 哈尔滨理工大学工学硕( 学位论文 分析经典算法Apfiofi和FP(树算法以及他们的优缺点，并对关联规则挖掘的深 入问题进行了论述。 第3章首先介绍并分析了目前国内外现有的最大频繁项目集挖掘算法的优 缺点，介绍了项目序列集的相关性质与操作，并分析项目序列集挖掘算法的优 缺点，最后对比分析改进FP(树和FP(树在最大频繁项目集挖掘上的优越性。 第4章对改进的FP(树进行深入研究，利用改进FP(树的内在性质，提出 基于IFP(树的最大频繁项目集挖掘算法，并进行实例验证及对比分析其有效性 和优越性。 第5章在前一章深入研究改进FP(树的基础上，提出基于FP(树的敏感性 关联规则的隐藏算法，然后进行实例分析验证其优越性。 最后对本文进行总结，并对进一步的研究做出展望。 哈尔滨理工大学工学硕士学位论文 第2章关联规则挖掘理论与分析 2(1引言 关联规则挖掘是数据挖掘中最活跃的研究方法之一。本章将对关联规则的 基本概念、方法以及算法进行介绍及分析。 993年提出来的， 关联规则的概念和模型是首先由AGRAWAL等人n51在1 是对一个事物和其它事物的相互依存和相互关联的一种描述。针对数据而言 是 发现数据中项集之间潜在的关联或依赖联系。最初产生于零售业中，在传统的 零售商店中顾客通常是到一个柜台买完东西后再到另一个柜台去买另一样东 西，这样一来，商场经理虽然知道每一种商品的销售情况，但并不知道是哪些 顾客购买的，也不知道这个顾客同时还买了哪些东西。随着超级市场的出现， 顾客可以在超市一次购得所有自己需要的商品，而条型码的广泛应用，使商家 非常容易收集和存储数量巨大的销售数据。一条这样的数据通常都包括与 某个顾客相关的交易日期、交易中所购物品等等。通过对以往的大量交易数据 进行分析就能获得有关顾客购买模式的有用信息，从而提高商业决策的质量。 在交易数据项目之间挖掘关联规则的典型例子就是90,的顾客在购买面包 和黄油的同时也会购买牛奶，其直观的意义是，顾客在购买某些东西的时候有 多大的倾向也会购买另外一些东西，找出所有类似这样的规则，对于确定市场 策略是很有价值的。关联规则的其它应用还包括附加邮递、目录设计、追加销 售、仓储规划以及基于购买模式对顾客进行划分等。现在关联规则已广泛地应 用于其他领域，比如医学研究人员从已有的成千上万份病历中找出患某种疾病 的病人的共同特征，从而为治愈这种疾病提供一些帮助。警方通过对各种 线索 加以分析，找出其中与之关联，聚焦罪犯的主要特点，快速有效的进行侦破， 等等。这些应用中的数据库都是极其庞大的，因此，不仅需要设计高效的算法 来挖掘关联规则，而且如何维护和更新这些规则，如何确认这些规则是否有价 值，如何在挖掘过程中加入需求，如何快速有效地挖掘出有用的信息，如何将 挖掘出的信息以更好，更容易理解的形式进行展现等等是关联规则挖掘必须得 以解决的问题。 哈尔滨理工大学工学硕j:学位论文 2(2关联规则挖掘理论 IlcI，项目集Il在数据集D上的支持度是包含Il的事务在D中所占的百分 l 0。 Il?t lI,I|D 比，即support 11 0 t?D 一般称sup X 大于等于某个给定的最小支持度阈值的项目集X为频繁项 目集，反之称X为非频繁项目集;所有频繁项目集组成的集合为频繁集，长 度为k的频繁项目集为频繁k(项目集，频繁1(项目集包含的项目为频繁项目， 其在事务数据库中发生的次数为该项目的频度。对于项目集X?I，如果 项目集。一个定义在I和D上的形如Ilj12的关联规则通过满足一定的可信 度、置信度来给出。所谓的规则的可信度是指包含II和12的事务数与包含 Il 的事务数之比即:confidence II n j Il Y，满足X?I，Y?I，且有X?o，Y?a， 12 o。设关联规则X xfl Y o，对于给定的闭值minsup和minconf;如果Supp XY _minsup且 信度，则XjY为强关联规则;否则，XjY为弱关联规则。 给定一个数据库，关联规则挖掘问题就是通过用户指定最小支持度和最小 可信度来寻找强关联规则的过程。它分为以下两个子过程: 1(发现频繁项目集通过用户给定的最小支持度，寻找所有频繁项目集， 其他频繁项目集包含的最大频繁项目集的集合。发现所有的频繁项目集是形成 关联规则的基础。 2(生成关联规则通过用户给定的最小可信度，在每个最大频繁项目集 中，寻找Confidence不小于Minconfidence的关联规则。 关联规则挖掘的问题的主要特征是数据量巨大，因此算法的效率很关键。 目前研究的重点在第一步，即发现频繁项目集，因为第二步相对来是很容易 的。 当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪 些规则对于用户来说是有用的、有价值的。这里有两个层面:系统客观的层 面 和用户主管的层面n引。 哈尔滨理工大学丁学硕二卜学位论文 系统客观层面:很多的算法都使用“支持度(可信度"的框架，这样的结 构有时会产生一些错误的结果。,般规则的兴趣度是在基于统计独立性假设下 真正的强度与期望的强度之比，然而在许多应用中己发现，只要人们仍把支持 度作为最初的项集产生的主要决定因素，那么要么把支持度设得足够低以使得 不丢失任何有意义的规则，要么冒着丢失,些重要规则的风险;对前一种情形 计算效率是个问题，而后一种情形则有可能丢失从用户观点来看是有意义的 规 则的问题。除了把兴趣度作为修剪无价值规则的工具，也有其他的规则价值衡 量标准，比如提升度lift?引，如:li忙P XU Y ,P X P Y ，如果它的值小于l， 则X的出现和Y的出现是负相关的。如果结果值大于1，则X和Y是正相关 的，意味着每一个出现都蕴涵着另一个出现。如果结果值等于l，则X和Y独 立，他们之间没有相关性。 用户主观层面:上面讨论只是基于系统方面的考虑，但是一个规则的有用 与否最终取决于用户的感觉。只有用户可以决定规则的有效性、可行性。所以 8’191 我们应将用户的需求和系统更加紧密的结合起来。可以采用一种基于约束n 的挖掘，具体约束的内容可以有:数据约束，用户可以指定对哪些数据进行挖 掘，而不一定是全部的数据;指定挖掘的维和层次，用户可以指定对数据哪些 维以及这些维上的哪些层次进行挖掘;规则约束，可以指定需要的规则类型， 引入一个模板的概念，用户使用它来确定哪些规则是令人感兴趣的。如果一条 规则匹配一个包含的模板，则是令人感兴趣的，然而匹配一个限制的模板，则 被认为是缺乏兴趣的。 2(3关联规则算法及分析 实现方式不同，各有自己的优势与劣势，但是都具有优秀的算法思想，之后的 许多关联规则挖掘算法都是基于这两个算法所进行的优化和改进。 型，最有影响力的挖掘布尔型关联规则的算法，后来的许多算法都是基于该算 法的思想。其使用频繁项集性质的先验知识，用一种逐层搜索的迭代方法，用 k项集探索 k+1 项集。算法首先扫描一遍数据库计算各个1项集的支持 度，从而得到频繁l项集Ll:然后采用迭代的方式，逐步找出频繁2项集，3 项集，„，直至不再产生新的频繁项集为止。在计算频繁k项集Lk 哈尔滨理工大学工学硕士学位论文 Ck;再通过扫描数据库来计算候选集的出现频率，消除非频繁项，从而得到 Lk。Apfiofi算法提出了两个重要的定理来压缩搜索空间以提高频繁项集逐层产 生的效率。 AGRAWAL等人建立了用于事务数据库挖掘的项目集格空间理论。这个理 论的核心的原理是:频繁项目集的子集是频繁项目集;非频繁项目集的超集是 非频繁项目集。 算法2(1 A研ori 挖掘频繁项集 输入:交易数据库D:最小支持度minsup(count 输出:D中的频繁项目集L LI large1-itemsets ; For k 2;Lk(1?a;l【抖 do begin Ck apfiofi-gen Lk(I ; all Ddo For transactionste begin Ct subset Ck，t ; Forallcandidatesdo c?Ct C(count++; End LR c?CRI c(count minsup―count End L uLk; 选集。算法2-2描述了apfiofi-gen过程。 算法2-2 apfiofi―gen Lk(1 候选集产生 输入: 1【(1 (候选项目集Lk(I 输出:k(候选项目集Ck forall do itemsetpcLkq forallitemset do q?Lk(1 If then begin c pooq; If has―infrequent-subset c，Lk(1 then Delete c; Elseaddcto Ck; 哈尔滨理工大学工学硕士学位论文 End Return Ck; 候选集中。按着项目集格空间理论，含有非频繁项目子集的元素不可能是频 繁 项目集，因此应该及时裁剪掉那些含有非频繁项目子集的项目集，以提高效 有2(项子集都在L2中。算法2(3描述了这个过程。 算法2(3 has(infrequent(subset e，Lk(1 判断候选集的元素 输入:一个k(候选项目集c， k(1 (频繁项目集Lk(1 输入:c是否从候选集中删除的布尔判断 for Softdo all k-1 ??subset then ifs萑Lk(1 Return true; Return false; Apriori具备算法思想简单清晰且执行过程循序渐进的优点，应用了频 繁项 集的先验知识，即:一个频繁项集的任一非空子集必定是频繁项集;只要某一 项集是非频繁的，则其超集就无须再检验的两个重要性质对候选集进行有效地 过滤，尤其是对短模式的数据有很好的挖掘效果。 虽然Apriod算法能够有效地产生所有关联规则，但在效率上存在一些问 题:数据库扫描次数太多，对频繁k项集计算的每个k值，都需要扫描一次数 据库，当挖掘长模式时弊端更为显现。产生的候选集过大，例如，如果有104 7个候选2项集，累计并检查它 个频繁1项集，则Apriori算法需要产生多达10 们的频繁性。此外由于候选集的庞大，测试候选集是否为频繁项集需要花费大 的改进算法，主要有:采用哈希技术改进候选集生成过程的DHP Direct and HashingPruning 算法心引;采用分而治之的思想来解决内存不足问题的分 Itemset Dynamic Counting 船51等等。 patterntree，简称FP(树 的结构有效 growth算法提出一种称为FP(树 frequent 地将数据库中的每一条交易压缩在树状的结构上，其是在同一节点上共享相同 数据直到出现不同数据需要构建新节点时，才再构建新节点的一种有效率的存 哈尔滨理工大学工学硕士学位论文 储结构，在构建好FP(树后，就不须再对原先的数据库做扫描，因为原有数据 库中的所有数据信息都被储存在FP(树中，因此要找出频繁项目集，只需对 则。条件FP(树中的数据只与条件结点所代表的频繁项目集有关，其大小会比 原先构建出来的FP(树小很多，因此，对条件FP(树做挖掘，会节省许多时 生庞大候选项目集和反复扫描数据库的缺点。 算法2-4 FP(growth 挖掘频繁项集 输入:交易数据库T;最小支持度MinSup 输出:频繁模式的完全集 1(按以下步骤构造FP(树: 扫描交易数据库T一次。收集频繁项的集合F和它们的支持度。对F 按支持度降序排序，结果为频繁项表L;创建FP(树的根结点，以null标 的次序排序。设排序后的频繁项表为[pIP]，其中，P是第一个元素，而P是 一个新结点N，将其计数设置为1，链接到它的父结点Tr，并且通过结点 链结构将其链接到具有相同item(name的结点。如果P非空，递归地调用 insert-tree P,N 。 Procedure FP-growth Tree，0t ifTree含单个路径P，then for路径P中结点的每个组合 记作D 产生模式DU0t，其支持度Sup J3中结点的最小支持度: else forTree的头部的头表中的每个fli 产生一个模式p aiUfl，其支持度Sup ai(Sup(; 构造p的条件模式基，然后构造D的条件树TreeB; ifTree D?Othen 调用FP―growth Treea，p : 的集合，并把频繁项集中元素按各自的支持度计数递减排序。然后构造FP( 哈尔滨理工大学工学硕L学位论文 树:创建树的根结点，用null标记。第二次扫描数据库，每条交易中的项按递 减支持度计数排序，并对每条交易创建一个分枝。一般地，当为一条交易考虑 增加分枝时，沿共同前缀上的每个结点的计数增加l，为在前缀之后的项创建 结点并链接。为方便树的遍历，创建一个项头表，使得每个项通过一个结点链 指向它在树中的出现。扫描数据库中的所有交易后就创建了FP(树。因此，数 据库频繁模式的挖掘问题就转换成了挖掘FP(树的问题。FP(树的挖掘处理过 程，是一个采用分治方法递归挖掘的过程:由长度为1的频繁模式 初始后缀 模式 开始，构造它的条件模式基 一个“子数据库”由FP(tree中与后缀模 式一起出现的前缀路径集组成 ，然后，构造它的条件FP(tree。并递归地在该 树上进行挖掘。模式增长通过后缀模式与由条件FP(tree产生的频繁模式连接 实现。 FP(growth算法的优势:采用FP(树存放数据库的主要信息。算法只 需扫描 数据库两次，即对事务数据库仅需两次遍历，第1次遍历产生频繁l项集，第 2次遍历用于创建FP(树，将关键信息以FP(树的形式存放在内存中，避免了因 多次扫描数据库而带来的大量的I,o时间;不需要产生候选集，仅需要构造 FP(树和条件FP(树，通过递归地访问FP(树，产生频繁模式，从而减少了由于 产生和测试候选集所耗费的大量时间;采用分丽治之的方式对数据库进行挖 掘，从而在挖掘过程中，大大地减少了搜索空间。算法的劣势:需要占用大量 内存 与FP(树的深度和宽度成比例 。树的深度一般是单个事务中所含项目数 量的最大值;树的宽度是平均每层所含项目的数量。如果数据库中的频繁1(项 集的数量很大，且内存不能装入库中所有项目在FP(树的映射信息时，算法将 不能有效地工作。当数据库很大时，所构建的FP(树会变得很庞大，尤其是在 数据库中的数据过于松散，无法在FP(树上共享同一个节点时，FP(树将会变成 一个没有效率的结构，储存一个FP(树所占的空间将会变得比原先的数据库还 的时间用在了FP(树的遍历上，建立每棵条件FP(树需要遍历原树两次。因此 FP(树的构造和遍历是影响FP(growth算法效率的瓶颈。 优化。他们利用数组来存储条件模式库的频度数据，并采用了其它优化技术， 学者范明等心铂对FP-growth算法也做了很好的改进，提出了在FP(树挖掘中， 不生成条件FP(树的频繁模式挖掘算法。该算法减少了每一个结点的域的个 哈尔滨理工大学工学硕士学位论文 数，只保留指向父结点的指针。与FP(growth算法相比，改进算法的效率提高 了一倍，所需的存储空间也减少了一半。 多基于不同思想或数据表示法的关联规则挖掘方法。如:VIPER算法四，与前 Itemset ForE伍cientRule( 面的算法不同的是，VIPER VerticalPartitioning extraction 算法对数据库中的数据采用了纵向表示法。原来的横向表示法 是用 一个事务中的项集来表示数据，纵向表示法则是用包含某一项的事务集来表 频繁集的运算就变成了集合之间的交运算。VIPER算法采用了位向量来表示数 据，并采用了许多方法对位向量生成、数据的交运算、计数及存储等进行优 化;Tree Vrojection算法啪1，Treearojection算法采用字典树作为数据存储框架， 并将数据库事务投影到树中;Tree Projeetion算法主要采用了广度优先的策略 来建立树，并与深度优先的策略相结合进行事务投影和计数。在频繁项集的计 算过程中，还利用矩阵进行频度计算。基于Di凰et的挖掘方法九1，Di凰et是 Zaki等人提出的一种对数据的纵向表示法。Di凰et只保存候选模式与产生的频 繁模式在事务集 tids 上的差集，这样可以减少大量的存储空间;特别是对 数据密集的情形，效果更为明显。 前面所介绍的算法的主要研究方向均围绕的是关联规则挖掘的第一个子问 题，即:如何更快更优的挖掘出用于产生关联规则的频繁项集。由于关联规则 挖掘的第二个子问题:关联规则的产生，在内存、I,O以及算法效率上都较为 容易与直观，且具有一般性和通用性。 2(4关联规则的深入研究 前面介绍及分析的算法，都是主要针对最简单的单层单维的布尔型关联规 则挖掘的，然而对于许多实际应用来说，由于数据的多样性和复杂性，需要在 不同细节层次和不同维度间进行挖掘，因而出现了多种针对这种对象背景的挖 掘算法。 2(4(1多层次关联规则 对于很多的应用来说，由于数据分布的分散性，所以很难在数据细节的层 次上发现一些强关联规则。当我们引入概念层次后，就可以在较高的层次上进 哈尔滨理工大学丁学硕J:学位论文 行挖掘。虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户 来说是普通的信息，对于另一个用户却未必如此。所以数据挖掘应该提供这样 一种在多个层次上进行挖掘的功能根据规则中涉及到的层次，多层关联规则可 以分为同层关联规则和层间关联规则。多层关联规则的挖掘基本上可以沿用 “支持度(置信度”的框架。不过，在支持度设黄的问题上有一些要考虑的东 西。同层关联规则可以采用两种支持度策略: 统一的最小支持度阐值。即对不同层次频繁项集的挖掘均使用相同的最小 支持阐值。采用这种策略可以简化搜索过程，而且基于一个祖先结点是其子结 点的超集，可以用优化技术来避免搜索其祖先结点包含不满足最小支持度闽值 的项集。但采用统一的最小支持度阐值也存在一些问题:由于低层次项不可能 比相应高层次项出现的次数更多，所以，如果最小支持阐值设置过高，就可能 忽略掉一些低层次中有意义的关联关系，如果阀值设置过低，则可能产生过多 的高层次无意义的关联关系。 递减的最小支持度阐值。即每个层次都有不同的最小支持度，较低层次的 最小支持度相对较小。利用递减支持度阈值挖掘多层关联知识，可以选择若干 搜索策略。他们各有各的优缺点，在实际运用时应该根据不同的具体情况选择 不同的策略。 算法和EstMerge算法b?，其速度比基本算法快2,5倍，随着数据量的增大， Estimate算法性能优于Cumulate算法。 2(4(2多维关联规则 以上我们研究的基本上都是同一个字段的值之间的关系，比如用户购买的 物品。用多维数据库的语言表示就是叫单维或者维内的关联规则，这些规则一 般都是在事务数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关 联规则?别，在挖掘维间关联规则和混合维关联规则的时候，还要考虑不同的字 段种类:种类型和数值型。对于种类型的字段，原先的算法都可以处理。而对 于数值型的字段，需要先进行一定的处理，一般为连续属性离散化处理。基本 上有以一下几种方法:1(数值字段被分成一些预定义的层次结构。这些区间都 是由用户预先定义的。得出的规则也叫做静态数量关联规则。2(数值字段根据 数据的分布分成了一些布尔宇段。每个布尔字段都表示一个数值字段的区间， 落在其中则为1反之为O。这种分法是动态的，得出的规则叫布尔数量关联规 (20- 哈尔滨理丁大学工学硕士学位论文 则。3(数值字段被分成一些能体现它含义的区间。它考虑了数据之间的距离的 因素。得出的规则叫基于距离的关联规则。4(直接用数值字段中的原始数据进 行分析。使用一些统计的方法对数值字段的值进行分析，并且结合多层关联规 则的概念，在多个层次之间进行比较从而得出一些有用的规则。得出的规则叫 多层数量关联规则。上述方法有个共同的缺点就是边界划分太硬，这样有可能 会导致一些有用规则丢失。为了解决这个问题，人们提出通过定义在属性域上 的模糊集来软化边界，这是因为模糊集可以在集合元素和非集合元素之间提供 非常平滑的过渡。另外，还有些学者提出基于云模型进行区间划分的概念， 运 用云模型也可以较有效地解决硬划分带来的问题。 2(5本章小结 在数据挖掘中，关联规则挖掘一个活跃的研究领域。本章论述了关联规则 挖掘的基本理论，关联规则挖掘算法，其中详细研究了经典算法Apriori和FP― growth算法，并分析了其存在的优缺点，最后对最关联规则深入问题进行了简 单的研究分析，本章的分析为最大频繁项目集挖掘算法打好了基础。 哈尔滨理工大学工学硕士学位论文 第3章最大项目集算法与改进FP(树研究 3(1引言 关联规则挖掘是数据挖掘中最活跃的研究方法之一，最早是由AGRAWAL 等人于1993年提出的，它用于描述事务数据库中各交易项目之间的关系，即 频繁关系。关联规则挖掘问题可以划分成两个子问题，发现频繁项目集和生成 关联规则，发现频繁项目集是关联规则挖掘和数列模式等数据挖掘应用中的关 键技术和步骤。因此许多研究都集中在频繁模式挖掘上，Apriori算法是关联规 则挖掘的一个经典算法，在数据挖掘中具有里程碑的作用，许多早期的研究大 都采用类似于Apdori的先产生候选集后进行测试的方法，但是随着研究的深 入，它的缺点也暴露出来，它需要多次扫描数据库，需要很大的I,O负载， 可 能产生庞大的候选集。 法，该算法采用FP(树存放数据库的主要信息，算法只需要扫描数据库两次， 使关键信息以FP(树的形式存放在内存中，避免了因多次扫描数据库而带来的 大量的I,O负载，它不需要产生候选集，从而减少了产生和测试候选集需要耗 费的大量时间，并且采用分而治之的思想，在挖掘过程中大大减少了搜索空 模式算法对于一些非稠密数据库能够取得很好的性能，但对于稠密数据库或者 支持度比较小时，频繁模式的数量会以指数形式增长，使得找出所有的频繁模 式成为不可能的任务，为了减少频繁模式中的冗余，人们采用了各种方法， 其 closeditemset 中最主要的有挖掘频繁闭项目集九 frequent FCI 和最大频繁项 目集 MFI 。其中MFI的规模最小，而且通过最大频繁项目集可以导出频繁 闭项集和频繁项目集，所以可以把发现频繁项目集的问题转化为发现最大 频繁 项目集的问题，另外某些数据挖掘的应用中仅需发现最大频繁项目集，而不 必 发现频繁项目集，因而发现最大频繁项目集对数据挖掘具有重大的意义。本 章 将对现有的最大频繁项目集算法进行分析研究，并对改进IFP(树进行研究。 哈尔滨理丁大学工学硕一L学位论文 3(2最大项目集挖掘算法研究 由于现有的最大频繁项目集挖掘算法存在种种缺陷，为了提高数据挖掘系 统的可用性、可扩展性、高效性等， 国内外的专家对其进行了深入地分析研 究。 3(2(1最大项目集挖掘算法及分析 目前已有的最大频繁项目集挖掘算法可分为宽度优先搜索算法和深度优先 用了自底向上和自顶向下的双向搜索策略，但其第k次的MFCS 最大频繁候 选项目集 是由k(1次的MFCS中的非频繁项目集去掉一个元素来生成，产 生了过多的无用候选项目集，其Ck的生成采用类似于Apfiofi生成候选项目集 的方法，对海量数据库来讲，将陷于NP难度的陷阱。深度优先算法以 DepthProjieett强l,MAFIAt37 采用了水平二进位串和垂直二进位图表示挖掘过程中的投影数据子集。除了传 来做进一步的剪枝;Fp算法是基于FP-树挖掘最大频繁项目集的深度优 先算法。它使用FP(树来压缩表示事务数据库中与频繁项目集相关的信息，并 ItemsetWee 将最大频繁项目集保存在一棵称为MFI(tree imalFrequent 的树中，在一定程度上提高了最大频繁项目集的存取速度。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1993年国 家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位 和 高等院校竞