数据挖掘技术关联性分析课件

1、第8章 知识类数据挖掘技术8.1 知识发现系统的结构8.2 关联规则的数据挖掘技术8.3 神经网络的数据挖掘技术8.4 遗传算法的数据挖掘技术8.1 知识发现系统的结构知识发现系统管理器：控制并管理整个知识发现过程，包括数据选择过程、抽取算法的选择及使用过程、发现的评价过程。知识库和商业分析员数据仓库的数据库接口数据选择知识发现引擎：分类、聚类、偏差分析、模糊推理等发现评价发现描述8.2 关联规则的数据挖掘技术自然界中某种事物发生时其他事物也会发生的这样一种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）关联规则挖掘就是从大量的数据中挖掘出有价值描述数据项之间相互联系

2、的有关知识 关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。交易号（TID） 项集合（Itemsets） T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 For rule A C:support = support(A &C) = 50%confidence = support(A &C)/support(A) = 66.6%定义：关联规则挖掘的交易数据集记为D（一般为交易数据库），DT1，T2，Tk，,Tn，Tk（k1,2,，n）称为交易，对应

3、每一个交易有唯一的标识，记作TID。元素im（m1,2,，p）称为项。设I=i1，i2，im是D中全体项组成的集合，且TkI。设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。若X,Y为项集，XI, YI，并且XY=，则形如X = Y的表达式称为关联规则。 关联规则形式化定义规则XY在交易数据集D中的置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为confidence(XY)。计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(XY) = P(YX) = |T: XYT，TD|/|T:XT，

4、TD|100%规则XY在交易数据集D中的支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(XY)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY) = P(XY) = |T: XYT，TD|/|D|100%（其中|D|是交易数据集D中的所有交易数）可信度（置信度）支持度 关联规则度量交易号（TID） 项集合（Itemsets） T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 求

5、I2 I4的置信度和支持度最小置信度阈值最小支持度阈值同时满足最小置信度阈值和最小支持度阈值的关联规则为强关联规则，是有意义有价值。 在给定一个交易数据集D，挖掘关联规则问题就是产生支持度和置信度分别大于用户给定的最小支持度阈值和最小置信度阈值的关联规则。项集的出现频度（项集的支持度）：整个交易数据集D中包含该项集的交易记录数最小支持频度：满足最小支持阈值所对应的交易记录数频繁k项集：满足最小支持阈值的项集挖掘交易数据库D中所有关联规则的问题可以被划分为两个子问题：找出所有具有最小支持度的项集(频繁项集) 。用Apriori、FP-Growth等算法来找出频繁项集。使用频繁项集生成期望的关联规

6、则。对于每一个频繁项集l，找出其中所有的非空子集；然后，对于每一个这样的子集a，如果support(l)与support(a)的比值大于最小可信度，则存在规则a=(l-a)。交易号项集合T100 I1，I2，I5 T200 I2，I4 T300 I2，I3 T400 I1，I2，I4 T500 I1，I3 T600 I2，I3 T700 I1，I3 T800 I1，I2，I3，I5 T900 I1，I2，I3 表1 交易数据库D 例：找出频繁项集Apriori算法项集支持度计数I16I27I36I42I52项集支持度计数I16I27I36I42I52C1L1扫描D，对每个候选计数比较候选支持度

7、计数与最小支持度计数找出频繁1项集的集合L1例：最小支持度阈值 为2项集支持度计数I16I27I36I42I52项集I1，I2I1，I3I1，I4I1，I5I2，I3I2，I4I2，I5I3，I4I3，I5I4，I5L1C2由L1产生候选C2Lk-1用于产生候选Ck 连接&剪枝项集支持度计数I1，I24I1，I34I1，I41I1，I52I2，I34I2，I42I2，I52I3，I40I3，I51I4，I50项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数项集支持度计数I1，I24I1，I34

8、I1，I52I2，I34I2，I42I2，I52L2项集I1，I2，I3I1，I2，I5由L2产生候选C3C3连接&剪枝连接：C3L2 L2I1,I2, I1,I3, I1,I5, I2,I3, I2,I4, I2,I5 I1,I2, I1,I3, I1,I5, I2,I3, I2,I4, I2,I5 =I1,I2,I3, I1,I2,I5, I1,I3,I5, I2,I3,I4, I2,I3,I4, I2,I3,I5 ,I2,I4,I5项集支持度计数I1，I24I1，I34I1，I52I2，I34I2，I42I2，I52L2项集支持度计数I1，I2，I32I1，I2，I52C3扫描D，对每个

9、候选计数比较候选支持度计数与最小支持度计数项集支持度计数I1，I2，I32I1，I2，I52L3对每个交易，使用subset函数找出交易中是候选的所有子集，并对每个这样的候选累加计数，所有满足最小支持度的候选形成频繁项集L。 输入：交易数据库D；最小支持度阈值min_sup。输出：D中的频繁项集L。方法：(1) L1find_frequent_1_itemset（D）；找频繁项集1-项集;(2) for （ k=2; Lk-1 ; min_sup） apriori_gen(Lk-1,min_sup) 连接和剪枝。用于在 第k-1次遍历中生成的Lk-1生成Ck for each t D 扫描数据

10、库，确定每个候选项集的支持频度 Ctsubset（Ck ，t）获得t所包含的候选项集 for each cCt c.count； (3) Lk c Ck | c.count min_sup 由Ck生成Lk(4) return LL1 L2 . Lk Apriori算法procedure has_infrequent_itemset （c，Lk-1）for each（k1） subset s of cif s Lk-1 return true ；else return false ；The Apriori Algorithm ExampleDatabase DScan DC1L1L2C2C2Sc

11、an DC3L3Scan DLet the minimum supportIs 50%, i.e. minimumsupport count is 4 x 50%= 2.Example of Generating CandidatesL3=abc, abd, acd, ace, bcdSelf-joining: L3*L3abcd from abc and abdacde from acd and acePruning:acde is removed because ade is not in L3C4=abcd关联规则的生成使用频繁项集生成期望的关联规则对于每一个频繁项集l，找出其中所有的非空子集；然后，对于每一个这样的子集a，如果support(l)与support(a)的比值大于最小可信度，则存在规则a=(l-a)。confidence