数据挖掘技术关联性分析

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

关联规则发觉主要对象是交易型数据库，一种交易一般由交易处理时间，一组顾客购买物品，有时也有顾客标识号(如信用卡号)组成。交易号（TID）项集合（Itemsets）T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I35/31例：以零售业为例，体育用具商场通过对销售数据进行关联分析一般能够发觉这些数据中经常隐含形式如下规律——“购买篮球顾客中有70%人同步购买篮球运动服，所有交易中有40%人同步购买篮球和篮球运动服”等等。篮球篮球运动服support＝40％，confidence＝60％6/31ForruleA

C:support=support({A&C})=50%confidence=support({A&C})/support({A})=66.6%7/31定义：关联规则挖掘交易数据集记为D（一般为交易数据库），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）称为交易，对应每一种交易有唯一标识，记作TID。元素im（m＝1,2,…，p）称为项。设I={i1，i2，…，im}是D中全体项组成集合，且Tk

I。设X是一种I中项集合，假如X

Tk，那么称交易Tk包括项集X。若X,Y为项集，X

I,Y

I，并且X

Y=

，则形如X==>Y体现式称为关联规则。关联规则形式化定义8/31交易号（TID）项集合（Itemsets）T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3项集：一种数据项集合k项集：包括k个数据项项集9/31规则X

Y在交易数据集D中置信度是对关联规则精确度衡量。度量关联规则强度。即在所有出现了X活动中出现Y频率，即规则X

Y必然性有多大。记为confidence(X

Y)。计算办法：包括X和Y交易数与包括X交易数之比：confidence(X

Y)=P(Y∣X)=|{T:X

Y

T，T

D}|/|{T:X

T，T

D}|×100%规则X

Y在交易数据集D中支持度是对关联规则主要性衡量，反应关联是否是普遍存在规律，说明这条规则在所有交易中有多大代表性。即在所有交易中X与Y同步出现频率记为：support(X

Y)。计算办法：交易数据集中同步包括X和Y交易数与所有交易数之比：support(X

Y)=P(X∪Y)=|{T:X

Y

T，T

D}|/|D|×100%（其中|D|是交易数据集D中所有交易数）可信度（置信度）支持度关联规则度量10/31交易号（TID）项集合（Itemsets）T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3求I2

I4置信度和支持度11/31最小置信度阈值最小支持度阈值同步满足最小置信度阈值和最小支持度阈值关联规则为强关联规则，是故意义有价值。12/31交易号（TID）项集合（Itemsets）T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3设：最小置信度阈值为2最小支持度阈值为2请问I1

I4，I2

I4是强规则吗？13/31在给定一种交易数据集D，挖掘关联规则问题就是产生支持度和置信度分别大于顾客给定最小支持度阈值和最小置信度阈值关联规则。项集出现频度（项集支持度）：整个交易数据集D中包括该项集交易统计数最小支持频度：满足最小支持阈值所对应交易统计数频繁k－项集：满足最小支持阈值项集14/31挖掘交易数据库D中所有关联规则问题能够被划分为两个子问题：找出所有具有最小支持度项集(频繁项集)。用Apriori、FP-Growth等算法来找出频繁项集。使用频繁项集生成盼望关联规则。对于每一种频繁项集l，找出其中所有非空子集；然后，对于每一种这样子集a，假如support(l)与support(a)比值大于最小可信度，则存在规则a==>(l-a)。15/31找出频繁项集－－Apriori算法Apriori性质：一种频繁项集中任一子集也应是频繁项集Apriori算法基本思想：首先找出频繁1－项集，记为L1，然后利用L1来挖掘L2，即频繁2－项集，每挖掘一层Lk需扫描整个数据集一遍16/31交易号项集合T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3表1交易数据库D例：找出频繁项集－－Apriori算法17/31项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2C1L1扫描D，对每个候选计数比较候选支持度计数与最小支持度计数找出频繁1－项集集合L1例：最小支持度阈值为218/31项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝L1C2由L1产生候选C2Lk-1用于产生候选Ck

连接&剪枝19/31项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I4｝1｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2｛I3，I4｝0｛I3，I5｝1｛I4，I5｝0项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2C2L2比较候选支持度计数与最小支持度计数扫描D，对每个候选计数20/31项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L2项集｛I1，I2，I3｝｛I1，I2，I5｝由L2产生候选C3C3连接&剪枝21/31连接：C3＝L2∞L2＝{{I1,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，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2L222/31剪枝：{I1,I2,I3}2-项子集是{I1,I2},{I1,I3}和{I2,I3}。{I1,I2,I3}所有2-项子集都是L2元素。因此，保存{I1,I2,I3}在C3中。{I2,I3,I5}2-项子集是{I2,I3},{I2,I5}和{I3,I5}。{I3,I5}不是L2元素，因而不是频繁。因此，由C3中删除{I2,I3,I5}。剪枝后C3＝{{I1,I2,I3},{I1,I2,I5}}。23/31项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2C3扫描D，对每个候选计数比较候选支持度计数与最小支持度计数项集支持度计数｛I1，I2，I3｝2｛I1，I2，I5｝2L3对每个交易，使用subset函数找出交易中是候选所有子集，并对每个这样候选累加计数，所有满足最小支持度候选形成频繁项集L。24/31

输入：交易数据库D；最小支持度阈值min_sup。输出：D中频繁项集L。办法：(1)L1＝find_frequent_1_itemset（D）；找频繁项集1-项集;(2)for（k=2;Lk-1

;min_sup）{apriori_gen(Lk-1,min_sup)连接和剪枝。用于在第k-1次遍历中生成Lk-1生成Ck

foreachtD扫描数据库，确定每个候选项集支持频度 ｛Ct＝subset（Ck，t）取得t所包括候选项集 foreachc

Ctc.count＋＋； ｝ ｝(3)Lk＝｛c

Ck|c.count>min_sup｝由Ck生成Lk(4)returnL＝L1

∪L2….∪LkApriori算法25/31procedureapriori_gen(Lk-1,min_sup){foreachl1

Lk-1 foreachl2

Lk-1 ｛if（l1[1]=l2[1]∧…∧l1[k-2]=l2[k-2]∧

l1[k-1]<l2[k-1]） c=l1

l2；将两个项集连接在一起 ifnothas_infrequent_itemset（c，Lk-1） Ck=Ck

∪{c}； }reutrnCk

}26/31procedurehas_infrequent_itemset（c，Lk-1）{ foreach（k－1）subsetsofc ifs

Lk-1

returntrue； else returnfalse；}27/31TheAprioriAlgorithm—ExampleDatabaseDScanDC1L1L2C2C2ScanDC3L3ScanDLettheminimumsupportIs50%,i.e.minimumsupportcountis4x50%=2.28/31ExampleofGeneratingCandidatesL3={abc,abd,acd,ace,bcd}Self-joining:L3*L3abcdfromabcandabdacdefromacdandacePruning:acdeisremovedbecauseadeisnotinL3C4={abcd}29/31关联规则生成使用频繁项集生成盼望关联规则对于每一种频繁项集l，找出其中所有非空子集；然后，对于每一种这样子集a，假如support(l)与support(a)比值大于最小可信度，则存在规则a==>(l-a)。confidence（A

B）＝P(B|A)＝support_c