关联分析
- 格式:doc
- 大小:22.00 KB
- 文档页数:4
数据关联分析在当今数字化的时代,数据如同海洋一般浩瀚无垠。
而从这海量的数据中挖掘出有价值的信息,就如同在大海中寻找珍贵的宝藏。
数据关联分析,便是我们手中那把能够开启宝藏之门的关键钥匙。
首先,让我们来理解一下什么是数据关联分析。
简单来说,它是一种通过寻找数据之间的内在联系和相互关系,从而揭示隐藏在数据背后的规律和模式的方法。
想象一下,你有一堆关于销售的数据,包括产品类别、销售地区、销售时间和销售额等等。
通过数据关联分析,你可能会发现某些产品在特定地区、特定时间段内的销售额有着显著的增长趋势。
这就是数据关联分析的魅力所在,它能帮助我们从看似杂乱无章的数据中发现有意义的信息。
那么,为什么数据关联分析如此重要呢?对于企业来说,它是制定有效营销策略的重要依据。
通过分析客户的购买行为数据,企业可以了解哪些产品常常被一起购买,从而进行捆绑销售或者推荐相关产品,提高销售额。
比如,一家超市发现购买面包的顾客经常同时购买牛奶,那么在摆放商品时,就可以把面包和牛奶放在相邻的位置,或者在促销活动中推出面包和牛奶的组合套餐。
在医疗领域,数据关联分析也发挥着巨大的作用。
医生可以通过分析患者的病历数据,发现疾病之间的关联,为诊断和治疗提供更准确的依据。
例如,研究发现患有高血压的患者往往更容易患上糖尿病,这一关联发现有助于医生提前采取预防措施,降低患者的患病风险。
在金融行业,数据关联分析能够帮助识别欺诈行为。
通过分析交易数据中的异常模式和关联关系,金融机构可以及时发现可疑的交易活动,保护客户的资金安全和金融系统的稳定。
要进行有效的数据关联分析,我们需要一些方法和技术。
关联规则挖掘是其中一种常见的方法。
它通过设定一些支持度和置信度的阈值,来发现数据中频繁出现的项集和关联规则。
比如说,我们设定支持度为10%,置信度为70%,那么如果在我们的销售数据中,购买 A 产品的同时购买 B 产品的情况超过了 10%,并且购买了 A 产品的顾客中有超过 70%的人会购买 B 产品,那么就可以认为存在“A 产品> B 产品”这样的关联规则。
大数据分析中关联分析技术的使用教程大数据分析已经成为当今信息时代的重中之重,企业和组织通过对数据进行深入分析,能够获得有价值的洞察,为业务决策提供有力支持。
而在大数据分析中,关联分析技术被广泛用于揭示数据之间的关联关系,发现隐藏在数据背后的规律和潜在的相关性。
在本篇文章中,我们将为您介绍关联分析技术的基本概念、常用算法以及实际应用。
一、关联分析概述关联分析是一种从大规模数据集中寻找有趣关系、相互依赖的任务。
它通过发现项目集中的频繁模式来完成,频繁模式指的是在数据集中经常出现的物品组合。
关联分析被广泛应用于市场篮子分析、商品推荐、交叉销售等领域。
二、关联分析算法1. Apriori算法Apriori算法是关联分析中最常用的算法之一,它基于频繁模式的性质。
Apriori算法通过扫描数据集多次来找到频繁项集,利用逐层递加的方式来发现频繁项集的超集,直到无法找到更多频繁项集为止。
Apriori算法的核心思想是:如果一个物品组合是频繁的,那么它的子集也一定是频繁的。
2. FP-Growth算法FP-Growth算法是一种高效的关联分析算法,通过构造FP树(频繁模式树)来实现快速的频繁模式挖掘。
与Apriori算法相比,FP-Growth算法避免了多次扫描事务数据库的操作,通过构造FP树和利用后缀路径来发现频繁模式。
FP-Growth算法适合处理包含大量事务和高维度特征的数据集。
3. Eclat算法Eclat算法也是一种经典的关联分析算法,它通过交集来计算频繁模式。
Eclat算法首先构建一个频繁项集的垂直格式数据结构,然后利用递归的方式来生成频繁项集。
与Apriori算法和FP-Growth算法相比,Eclat算法更适用于处理稀疏数据集。
三、关联分析的实际应用1. 市场篮子分析市场篮子分析是关联分析的经典应用之一,它通过挖掘购物篮中的频繁模式,从而揭示商品之间的关联关系。
利用市场篮子分析,商户可以了解消费者购买习惯,进行商品陈列、促销策略的优化,提高销售额和客户满意度。
关联分析方法关联分析是一种数据挖掘技术,用于发现数据集中项之间的关联规则。
在商业领域,关联分析被广泛应用于市场篮分析、交叉销售分析、购物篮分析等领域。
它可以帮助企业发现产品之间的关联性,从而制定更有效的营销策略,提高销售额和客户满意度。
关联分析的核心思想是寻找项集之间的频繁关联规则。
在一个项集中,如果某些项经常出现在一起,就可以认为它们之间存在关联性。
关联分析的常见算法包括Apriori算法和FP-growth算法,它们能够高效地发现频繁项集和关联规则。
Apriori算法是一种经典的关联分析算法,它通过逐层搜索的方式发现频繁项集。
该算法首先扫描数据集,统计每个项的支持度,然后根据最小支持度阈值生成候选项集。
接下来,通过连接和剪枝操作,逐渐生成更大的候选项集,直到不能再生成新的频繁项集为止。
最后,根据频繁项集生成关联规则,并计算它们的置信度。
FP-growth算法是一种基于前缀树的关联分析算法,它通过构建FP树来高效地发现频繁项集。
该算法首先构建FP树,然后通过递归方式挖掘频繁项集。
相比于Apriori算法,FP-growth算法不需要生成候选项集,因此在处理大规模数据集时具有更高的效率。
在实际应用中,关联分析方法需要注意以下几点:首先,选择合适的支持度和置信度阈值。
支持度和置信度是衡量关联规则重要性的指标,合理设置阈值可以过滤掉不重要的规则,提高关联分析的效率和准确性。
其次,处理大规模数据集时需要考虑算法的效率。
针对不同规模的数据集,可以选择合适的关联分析算法,以提高计算效率。
最后,关联分析结果需要结合业务实际进行解释和应用。
在发现了关联规则之后,需要进一步分析规则的意义,结合实际情况进行解释,并制定相应的营销策略或业务决策。
总之,关联分析方法是一种重要的数据挖掘技术,能够帮助企业发现数据集中的关联规则,从而指导营销策略和业务决策。
通过合理选择算法、设置阈值,并结合业务实际进行解释和应用,可以充分发挥关联分析的作用,提升企业的竞争力和盈利能力。
企业关联状况分析报告范文1. 简介本报告旨在对一家企业的关联状况进行分析,通过研究企业之间的关系以及对外的关联情况来了解企业的发展现状和未来趋势。
2. 总览2.1 企业概述被分析的企业是一家制造业公司,专注于生产和销售电子产品。
成立于2005年,总部设在中国,在国内有多个生产基地,产品销往全球各地。
2.2 关联企业概述通过对企业的财务报表和公开信息的研究,我们确定了与被分析企业关联的公司,主要包括以下几个方面:1. 子公司:被分析企业拥有多家全资子公司,这些子公司在中国各地和国外设有生产基地和销售网络。
子公司与母公司存在财务和管理上的关联。
2. 合作伙伴:被分析企业与其他制造业公司建立了合作关系,共同进行生产、研发和市场营销活动。
3. 上下游企业:被分析企业与供应商和分销商有紧密的合作关系,形成了完整的供应链和销售网络。
4. 股东:被分析企业的股东构成复杂多样,包括个人投资者、机构投资者和关联公司。
3. 关联分析3.1 子公司被分析企业的全资子公司在中国各地和国外设有生产基地和销售网络。
子公司与母公司共享品牌、技术和市场资源,通过集中管理和资源整合,实现了规模效益和协同效应。
通过研究子公司的财务报表,可以看出它们对母公司业绩的贡献比较大,占整个企业利润的70%以上。
这表明子公司的发展和经营情况对整个企业的发展具有重要影响。
3.2 合作伙伴被分析企业与其他制造业公司建立了合作关系,共同进行生产、研发和市场营销活动。
通过与合作伙伴的合作,被分析企业可以共享技术、资源和市场渠道,降低研发成本和市场推广成本。
合作伙伴关系的稳定性对企业的发展有重要影响。
通过研究合作伙伴的财务状况和合作关系的历史,可以评估合作伙伴对企业的战略意义和风险。
3.3 上下游企业被分析企业与供应商和分销商有紧密的合作关系,形成了完整的供应链和销售网络。
供应商提供原材料和零部件,分销商负责产品的销售和售后服务。
供应链的稳定性和效率对企业的供应和生产具有关键影响。
关联分析基本概念与算法关联分析(Association Analysis)是一种在大规模数据集中寻找项集之间有意义关联关系的数据挖掘技术。
它的基本任务是发现数据集中的项目之间的频繁关联模式(Frequent Pattern)和关联规则(Association Rule)。
1.频繁关联模式频繁关联模式是指在数据集中经常同时出现的项集。
如果一个项集的支持度大于等于用户事先设定的最小支持度阈值,则称该项集为频繁项集。
频繁关联模式的发现是关联分析的核心任务。
2.关联规则关联规则是指一个集合中的一个子集在给定另一个集合的条件下出现的概率。
关联规则可以表示为X->Y,其中X和Y分别为项集。
关联规则呈现了一个条件和结论之间的关系。
根据关联规则中的置信度(Confidence)和支持度(Support)等指标,可以对规则进行排序和筛选。
3.支持度与置信度支持度(Support)是指一个项集在数据集中出现的频次。
在关联分析中,项集的支持度是指该项集在数据集中出现的概率。
置信度(Confidence)是指一个关联规则的可信程度。
在关联分析中,置信度表示当一个项集出现时,另一项集也会同时出现的概率。
为了发现频繁关联模式和关联规则,关联分析算法中常用的两种方法是Apriori算法和FP-Growth算法。
1. Apriori算法Apriori算法是一种基于候选生成和剪枝的算法。
该算法的基本思想是通过迭代计算递增长度的候选项集,然后按照最小支持度筛选出频繁项集,从而生成频繁关联模式。
Apriori算法的过程如下:(1)初始化,生成所有的单个项集;(2)通过计算支持度筛选出频繁一项集;(3)进一步生成候选二项集,并利用剪枝策略和支持度进行筛选,得到频繁二项集;(4)迭代生成更高阶的候选项集,并以频繁(k-1)项集为基础进行筛选,直到没有更高阶的频繁项集为止。
2. FP-Growth算法FP-Growth算法是一种基于频繁模式树(FP-Tree)的算法。
关联度分析一 、关联度分析的意义关联度是表征两个事物的关联程度。
从思路上看,关联分析是属于几何处理范畴的。
设有参考序列和比较序列})(..........),2(),1({)()0(1)0(1)0(1)0(1n x x x t x =x )}(...),........2(),1({)()0(2)0(2)0(2)0(2n x x x t = x )}(....),........2(),1({)()0(3)0(3)0(3)0(3n x x x t = x )}(.....),........2(),1({)()0(4)0(4)0(4)0(4n x x x t =四个时间数据序列如图所示:则关联度为r12>r13>r14关联度分析是一种曲线间n 何形状的分析比较,即n 何形状越接近,则关联程度越大,反之则小。
二、面积关联度分析法关联度应用关联系数来表示,我们用曲线间的差值大小作为一种衡量关联度的尺度。
设母因素时间数列和子因素时间数列分别是:x )}(..,),........(),({)(221n i i k i f x f x f x f =x )}(),.......,(),({)(21n j j j k j f x f x f x f =记fk 时刻xj 对xi 的关联系数为§ij (fk ),其绝对差值为: ︱x )()(k j k i f x f -︱=)(k ij f ∆ k=1,2,……,n 这是对两个方列 各时刻的最小绝对差为:min ∆=kmin ︳x )()(k j k i f x f -︳ 各时刻的最大绝对差为:max max k∆=︳x )()(k j k i f x f -︳则母因素为子因素两曲线在各时刻的相对差值用下式表示:K ∆+∆∆+∆=max )(max min )(k ij k ij f f ξ 式中)(k ij f ξ称为xj 对xi 在K 时刻的关联系数关联系数的上界值)(k ij f ξ=1关联系数的下界值)(k ij f ξ=kk +1 K ∈(0,1),称为分辨系数,减少极值对计算的影响,提高分辨率。
一,关联分析定义关联分析,就是从大规模数据中,发现对象之间隐含关系与规律的过程,也称为关联规则学习。
例如:购物篮分析,最早是为了发现超市销售数据库中不同的商品之间的关联关系。
用于寻找数据集中各项之间的关联关系。
根据所挖掘的关联关系,可以从一个属性的信息来推断另一个属性的信息。
当置信度达到某一阈值时,可以认为规则成立。
常用的关联分析算法二,关联规则概念1.项与项集项,指我们分析数据中的一个对象;项集,就是若干项的项构成的集合,如集合{牛奶、麦片、糖}是一个3项集2.支持度某项集在数据集中出现的概率。
即项集在记录中出现的次数,除以数据集中所有记录的数量。
支持度体现的是某项集的频繁程度,只有某项集的支持度达到一定程度,我们才有研究该项集的必要。
support(A)=count(A)/count(dataset)=P(A)3.置信度项集A发生,则项集B发生的概率。
关联规则{A->B}中,A与B同时出现的次数,除以A出现的次数。
置信度体现的是关联规则的可靠程度,如果关联规则{A->B}的置信度较高,则说明当A发生时,B有很大概率也会发生,这样就可能会带来研究价值。
4.提升度关联规则{A->B}中,提升度是指{A->B}的置信度,除以B的支持度提升度体现的是组合(应用关联规则)相对不组合(不应用关联规则)的比值,如果提升度大于1,则说明应用该关联规则是有价值的。
如果提升度小于1,说明应用该关联规则起到了负面影响。
因此,我们应该尽可能让关联规则的提升度大于1,提升度越大,则应用关联规则的效果越好。
(注:如果两个事件相互独立,P(AB)=p(A)*P(B),提升度为1).5.频繁项集如果项集I的支持度满足预定义的最小支持度阈值,则I是频繁项集。
通常情况下,我们只会对频繁出现的项集进行研究。
如果一个频繁项集含有K个元素,我们称之为频繁K项集。
6.最小支持度用户或专家定义的衡量支持度的一个阈值,表示项集在统计意义上的最低重要性。
关联分析报告概述关联分析(Association Analysis)是一种常用的数据挖掘技术,用于发现数据集中的频繁项集和关联规则。
通过关联分析,可以揭示不同项之间的关联性,帮助决策者了解产品的销售情况、购物篮分析、用户行为等。
本报告将介绍关联分析的基本概念、算法和应用,并通过一个实际案例进行分析。
关联规则与支持度、置信度关联规则表示属性项或属性集之间的关系。
在关联分析中,关联规则通常以“IF-THEN”格式表示:“如果项集X出现,则项集Y也可能出现”。
支持度(Support)是指某个项集在数据集中出现的频率。
支持度能够反映项集的普遍程度,即项集在数据中出现的频率越高,其支持度越大。
置信度(Confidence)是指包含某个项集X的事务中,同时也包含另一个项集Y的概率。
置信度可以用来度量关联规则的可信度,即当项集X出现时,出现项集Y的可能性有多大。
Apriori 算法Apriori 算法是一种经典的关联规则挖掘算法,通过逐层搜索频繁项集进行关联规则的发现。
Apriori 算法的基本思想是利用Apriori 原理,即如果一个项集是频繁的,则它的所有子集也一定是频繁的。
算法的流程如下:1.初始化候选项集,包括所有单个项。
2.计算候选项集的支持度,删除低于最小支持度阈值的候选项集。
3.根据频繁项集生成候选项集,通过连接生成候选项集的新项。
4.重复步骤2和步骤3,直到没有更多的候选项集产生。
通过 Apriori 算法,可以高效地找到频繁项集和关联规则,从而帮助决策者发现数据集中的潜在关联关系。
实际案例分析假设我们有一个销售数据集,包含了顾客购买的商品信息。
现在我们要分析这些购买数据,找出频繁项集和关联规则,从而帮助商家了解商品之间的关联关系。
首先,我们需要进行数据预处理,将原始数据转化为适合进行关联分析的形式。
在这个案例中,我们将商品信息转化为二进制编码的形式,将每个商品作为一个属性,1表示购买,0表示未购买。
第1篇一、实验背景随着信息技术的飞速发展,大数据时代已经到来。
如何从海量数据中挖掘出有价值的信息,成为了当前研究的热点。
关联分析算法作为一种重要的数据挖掘技术,在商业、医疗、金融等领域有着广泛的应用。
本实验旨在通过实践操作,加深对关联分析算法的理解,并掌握其应用方法。
二、实验目的1. 理解关联分析算法的基本原理和步骤。
2. 掌握Apriori算法和FP-growth算法的实现方法。
3. 能够运用关联分析算法解决实际问题。
三、实验环境1. 操作系统:Windows 102. 编程语言:Python3.83. 数据库:SQLite4. 数据集:Market Basket Data四、实验内容1. Apriori算法Apriori算法是一种经典的关联分析算法,通过迭代搜索频繁项集,进而生成关联规则。
(1)数据预处理首先,我们需要对Market Basket Data进行预处理,包括:- 删除缺失值- 处理异常值- 标准化数据(2)计算频繁项集使用Apriori算法计算频繁项集,设置支持度阈值为0.5,置信度阈值为0.7。
(3)生成关联规则根据频繁项集,生成满足置信度阈值的关联规则。
2. FP-growth算法FP-growth算法是一种高效关联分析算法,通过构建FP树来表示频繁项集。
(1)数据预处理与Apriori算法类似,对Market Basket Data进行预处理。
(2)构建FP树使用FP-growth算法构建FP树,设置支持度阈值为0.5,置信度阈值为0.7。
(3)生成关联规则根据FP树,生成满足置信度阈值的关联规则。
五、实验结果与分析1. Apriori算法通过Apriori算法,我们得到了以下频繁项集和关联规则:- 频繁项集:{牛奶,面包},支持度:0.7- 关联规则:牛奶→ 面包,置信度:0.82. FP-growth算法通过FP-growth算法,我们得到了以下频繁项集和关联规则:- 频繁项集:{牛奶,面包},支持度:0.7- 关联规则:牛奶→ 面包,置信度:0.8两种算法得到的频繁项集和关联规则一致,说明FP-growth算法在处理Market Basket Data时具有较高的效率。
品牌关联度分析的主要方法与应用品牌关联度分析是一种重要的市场研究方法,通过评估消费者对品牌的感知和关联程度,帮助企业了解其品牌在市场中的地位,并制定相应的品牌策略。
本文将介绍品牌关联度分析的主要方法和应用。
一、主要方法1. 双因素分析法双因素分析法是最常用的品牌关联度分析方法之一。
它基于消费者的品牌知识以及对品牌的态度来评估品牌关联度。
研究者可以通过问卷调查等方式收集消费者对品牌的观点和感受,并根据这些数据进行分析。
同时,研究者可以将品牌与一些特定的属性进行关联,进一步评估品牌在消费者心目中的关联度。
2. 品牌购买决策模型品牌购买决策模型是另一种常用的品牌关联度分析方法。
该模型主要关注消费者在购买决策过程中对品牌的考虑程度。
研究者可以通过调查消费者在购买决策中的偏好和权重,进而分析品牌在消费者心目中的关联度。
3. 关联网络分析法关联网络分析法是一种以网络图形的方式显示品牌关联度的分析方法。
该方法通过收集大量的消费者对品牌的评价和意见,并将其构建成网络图形。
通过分析网络图形的拓扑结构和节点间的连接情况,可以评估品牌之间的关联度。
二、应用案例1. 品牌定位与创新通过品牌关联度分析,企业可以了解其品牌在消费者心目中的地位和形象。
基于这些分析结果,企业可以调整品牌定位策略,重新设计品牌形象,并进行品牌创新。
例如,如果分析结果显示消费者对品牌的关联度较低,企业可以通过改进产品质量、提升服务水平等方式,提高品牌关联度。
2. 市场竞争分析品牌关联度分析也可以帮助企业了解市场上其他竞争品牌的关联度。
通过与竞争对手的品牌形象进行比较,企业可以发现自身的优势和劣势,并制定相应的市场竞争策略。
3. 广告效果评估品牌关联度分析还可以用于评估广告的效果。
通过比较广告前后消费者对品牌的关联度,企业可以了解广告对品牌认知和形象的影响程度,并调整广告策略。
4. 品牌合作与联名推广品牌关联度分析还为企业合作与联名推广提供了依据。
关于关联分析的研究综述
引言
从信息处理的角度,人们更希望计算机帮助我们分析数据、理解数据,帮助我们基于丰富的数据作出决策,做人力所不能及的事情。
于是,数据挖掘——从大量数据中用非平凡的方法发现有用的知识——就成了一种自然的需求,它的主要目的便是从庞大的数据库中寻找出有价值的隐藏事件,找出其中的知识,并根据不同的问题建立不同的模型,以提供决策时的依据,数据挖掘对组织及决策行为将有相当大的帮助。
数据挖掘又称数据库中的知识发现(Knowledge Discovery in Databases),知识发现的一般步骤为:数据抽取,数据清理,数据设计,算法设计,算法运行,结果分析。
1.数据挖掘
数据挖掘的核心步骤是算法的设计阶段,一个好的算法(速度快、伸缩性好、结果容易使用且符合用户的特定需求)是影响数据挖掘效率的最重要因素。
数据挖掘是一个循环过程,如果用户对结果不满意,可对数据库进行重新挖掘。
从数据库中发掘的规则可以有以下几种:特征规则、区分规则、聚类规则、关联规则和进化规则等。
关联规则是比较新的一种,它的形式简洁,易于解释和理解并可有效捕捉数据间的重要关系。
2.关联规则
关联规则挖掘最相关的三个重要的研究领域是:统计学(Statistics),机器学习(Machine Learning)(或称人工智能,Artificial Intelligent)及数据库(Database)。
关联规则挖掘与统计学和机器学习的共同特点是:都是从数据集中发现知识。
2.1基本概念
Agrawal等人于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,是数据挖掘的一个重要研究领域。
它反映出一个事物与其它事物之间的相互依存性和关联性。
如果两个或者多个事物之间存在一定的关联关系,那么,其中一个事物就能够通过其它事物预测到。
具体描述为:设I={i1,i2,…,im}是二进制文字的集合,其中的元素称为项(item)。
记任务相关的数据D为交易T(transaction)的集合,这里交易T是项的集合,并且T⊆I。
每个交易都有一个唯一的标识,如交易号,记作TID。
设X是一个I中项的集合,如果X⊆T,
那么称交易T包含X。
2.2关联规则挖掘的算法
Agrawal等人在1993年设计了一个基本算法,提出了挖掘关联规则的一个重要方法—这是一个基于两阶段频繁项集思想的方法,将关联规则挖掘算法的设计可以分解为两个子问题:
1)找到所有支持度大于最小支持度的项集(Itemset),这些项集称为频繁项集(Frequent Itemset)。
2)使用第1步找到的频繁项集产生期望的规则。
第一个问题是算法设计的核心问题,它的效率高低是影响算法的关键,从庞大的数据库中找出所有符合大于或等于最小支持度的频繁项集,往往是相当艰巨且耗时的过程,但频繁项集被确定以后,要产生相对应的关联规则就容易且直接了,第2步只在生成的频繁项集中创建相应规则的枚举过程,无需复杂的计算,目前所谓的算法设计问题主要是围绕如何生成频繁集展开的。
2.2.1经典频集方法
为了生成所有频繁项集,Agrawal等人在1993年设计了Apriori算法,使用了递推的方法。
首先产生频繁1-项集L1,然后是频繁2-项集L2,直到有某个r值使得Lr为空,这时算法停止。
这里在第k次循环中,过程先产生候选k-项集的集合Ck,Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频繁项集做一个(k-2)-连接来产生的。
Ck中的项集是用来产生频繁项集的候选集,最后的频繁项集Lk必须是Ck的一个子集。
Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk,这里的验证过程是算法性能的一个瓶颈。
这个方法要求多次扫描可能很大的交易数据库,即如果频繁项集最多包含10个项,那么就需要扫描交易数据库10遍,这需要很大的I/O负载。
2.2.2 FP-tree算法
Han等人提出FP-tree算法,此算法是不产生候选项集作法的代表,因为不用产生候选项集,只需扫描数据库两次,因此节省了大量I/O的时间,整体的效能大幅提升,而且已运用在实际的产品中。
FP-tree算法和上述算法最主要的差别在于:FP-tree算法不用产生候选项集,且将数据库压缩在FP-tree的结构中,改进了扫描多次数据库的高成本。
我们利用例子来说明FP -tree算法。
它的最小支持度设为2,其作法可分为两个阶段。
第一个阶段为构建FP-tree结构,需扫描数据库两次,第一次扫描数据库将每个支持度大于或等于最小支持度的项目(频繁1-项集)找出,并根据其支持度值大小和在数据库出现的先后次序作排序。
并使得每一项通过一个节点链指向它在树中的出现。
第二次扫描过滤掉数据库中不足最小支持度的项目并依据排序表的频繁1-项集的次序得到每笔记录中包含频繁项的模式,同时构建FP-tree结构。
FP-tree构造如下:首先,创建树的根节点,用“root”标记,读入经过排序处理的每笔记录的第一个项时,检查root下的子树是否存在此项目节点,若此项目不存在,则在root 下新增此项目节点(Ni);如果此项目存在,则将此节Nj支持度加l。
之后的项目读入时,检查Nk(Nk为Ni或Nj)下的子树是否存在此项目节点,如果不存在,就在Nk下新增一个项目节点,如果存在,则将此节点支持度加1,以此类推做完每笔频繁项集中的所有项目。
2.2.3 FPL算法
E C.Tseng及Hsu Tseng提出FPL(Frequent Pattern List)算法以改进FP-tree算法,FPL 主要是将数据库中的交易数据做适当的处理后储存在一线性串行数据结构中,并在此线性串行结构上执行简单的运算,即可有效找出所有频繁项集模式,因为FPL算法利用简单的线性串行数据结构,不需产生候选项集,只需扫描数据库两次,且不管是稀疏数据库或是密集数据库均能有效找出所有的频繁项集模式,因此克服了FP-tree的缺点。
FPL算法扫描数据库两次,第一次扫描数据库将每个支持度值大于或等于最小支持度的频繁1-项集找出,并依照支持度大小和在数据库出现的先后次序作排序,第二次扫描以过滤掉记录中不足最小支持度的项目并根据己排序好的项目次序得到每笔记录的包含频繁项的模式,这一步与FP-tree算法一致。
此后FPL执行以下两个阶段。
第一个阶段是构建频繁项目线性串行。
根据表2-5将频繁项依支持大小建立成FPL串行,并将表2-3中的每笔记录建构成0、1二元数据表(DB-BIT),作法是根据FPL串行节点顺序与表2-3的数据做比较即可得到每笔记录,记录Ti之某位数据若为0(1)表示相对的频繁数据项目未出现(出现)在此记录中,最后将DB-BIT 中的所有记录挂至适当的FPL串行节点上。
第二个阶段是从此串行结构中挖掘所有的频繁项集模式。
首先检查串行最右边节点(Ni),这也与FP-tree算法相似,从支持度最小的项开始挖掘。
在此要找出所有包含Ni项目的频繁项集模式,计算出现在Ni节点上的其它各项出现次数(Bit count),接着忽略Ni以及所有Bit count小于最小支持度的项产生Ni项目的频繁1-项集模式:I5:2(代表项目I5在数据库中出现二次),接下来处理Bit count值大于或等于最小支持度的节点(Nb(b=l,2,…
n)),产生频繁模式为Nb和Ni组合,其出现次数皆为Nb支持度值(I2,I5:2),(I1,I5:2),再将Nb重新建立一子串行,并且将Ni所属的所有记录挂至适当的节点上,依据上面的方法,再挖掘新的频繁模式:(I2,I1,I5:2),直到串行中只剩下一个节点I2。
接着考虑移走Ni所属的记录及DB-BIT最后一位,找出下一个Ni=1的所有记录并挂至此串行下。
重复上述方法寻找频繁项集模式,直至串形结构上只有一个最大节点存在为止。
3.总结
总之,Apriori、FP-tree等现有关联规则挖掘算法都是在单维、单层、布尔关联规则下讨论的,是最简单形式的关联规则,它是解决其它问题的基础。