关联分析(数据库)

时间：2022-12-23 04:30:01 | 来源：信息时代

时间：2022-12-23 04:30:01 来源：信息时代

    关联分析 : 寻找数据项之间感兴趣的关联关系,用关联规则的形式描述。
项(item): 元素i_m(m=1,2,…,p)称为项,如购买的物品“篮球”,“篮球服”等。
全项集(itemsets): 所有项的非空有限集合,记为∑,∑={i₁,i₂,…,i_m,…,i_p}。
项集(itemset): 全项集的子集,记为I,I={i₁,i₂, …,i_j}(j<=p),I∑。
项集长度(size): 项集中项的数目。一个长度为k的项集称为k-项集,如项集{篮球,篮球服}的长度为2,是一个2-项集。
交易(transaction): 形如(TID,I)的一条数据记录T_k(k=1,2,…,n)称为一个交易,其中,TID为交易标识,I为项集。设X也是一个项集,如果XI, 那么称交易T_k包含项集X, 或X被T_k包含,记为XT_k·I。
交易数据集(transaction data set):一系列交易组成的集合称为交易数据集,记为D,D={T₁,T₂,…,T_k,…,T_n},其中,T_k(k=1,2,…,n)为一个交易。
关联规则(association rule): 是形如X⇒Y的蕴涵式,X,Y为项集,X∑,Y∑,并且XY=Φ, X称为输入或左部,Y称为输出或右部。
关联规则用兴趣度度量评估。
兴趣度度量(interest measure):帮助用户评估得到的关联规则。与关联规则评估相关的兴趣度包括简洁性、正确性、实用性、新颖性。
简洁性度量是衡量一个规则结构的复杂程度,复杂结构的规则难以解释与理解,造成其兴趣度降低; 正确性度量用以判断规则令人信服的程度有多高,在关联规则中用置信度表示; 实用性度量用以判断该规则再次出现的可能性有多大,在关联规则中用支持度表示; 新颖性度量判断规则是否已被导出的规则集中的另一规则所蕴涵,用以去除冗余规则。
支持度(support):关联规则X⇒Y在交易数据集D中的支持度是指交易数据集中包含X和Y的交易数与所有交易数之比,表示在所有交易中同时含有X与Y的概率(P(X∪Y),其中P表示概率),记为support(X⇒Y)。 计算方法为: support(X⇒Y)=P(X∪Y)=|{T:X∪YT.I,T∈D}|/|D|×100%(其中|D|是数据集D中的所有交易数)。
支持度表示关联规则出现的概率是多少,是对关联规则重要性(或适用范围)的衡量,反映了这条规则在所有交易中的普遍程度。
置信度(confidence): 关联规则X⇒Y在交易数据集D中的置信度是指交易数据集中包含X和Y的交易数与包含X的交易数之比,表示在所有出现了X的交易中出现Y的概率(P(Y|X),其中P表示概率),记为confidence(X⇒Y)。计算方法为:confidence(X⇒Y)=P(Y|X)=|{T:X∪YT.I,T∈D}|/|{T:X T.I,T∈D}|×100%。
置信度表示关联规则正确的概率是多少。它是对关联规则准确度的衡量,反映了关联规则前提成立的条件下结果成立的概率。
为了发现符合特定应用和用户感兴趣的关联规则,需要给每个度量指定一个可以由用户控制的阈值。常用的是最小支持度阈值(min_sup)和最小置信度阈值(min_conf)。前者是用户规定的关联规则必须满足的最小支持度,它反映了关联规则的最低普遍程度;后者是用户规定的关联规则必须满足的最小置信度,它反映了关联规则的最低可靠度。最小支持度阈值、最小置信度阈值一般由用户和领域专家设定。
频繁项集(frequent itemset): 项集出现的频率表示包含项集的交易数,如果项集的出现频率大于或等于最小支持度阈值与交易数据集D中交易总数的乘积,即项集满足最小支持度阈值要求,则该项集是频繁项集; 其余称为非频繁项集。
强关联规则: 强关联规则是指同时满足用户定义的最小支持度阈值和最小置信度阈值的关联规则。相反,不满足用户定义的最小支持度阈值和最小置信度阈值的规则,是弱关联规则。
关联规则挖掘是在交易数据集中发现超过用户指定的最小支持度阈值和最小置信度阈值的强关联规则。其挖掘过程一般分为两个步骤:
第一步:所有频繁项集的生成(这个步骤需借助最小支持度阈值)。
第二步:由频繁项集到强关联规则的生成(这个步骤需要借助最小置信度阈值)。
典型的关联规则挖掘算法主要有:基于Apriori性质的生成候选项集的Apriori算法和不生成候选项集的模式增长的FP-Growth算法等。
根据不同的标准可将关联规则进行以下分类:
(1)基于规则中处理的数据的类型,分为布尔关联规则和量化关联规则。布尔关联规则描述离散(或类别)属性之间关系的关联规则; 量化关联规则描述量化(或数值型)属性之间的关系的关联规则。
(2)基于规则中数据的抽象层次,分为单层关联规则和多层关联规则。单层关联规则不涉及不同抽象层的项(或属性)的规则;多层关联规则涉及不同抽象层的项(或属性)的规则。
(3)基于规则中涉及到的数据的维数,分为单维关联规则和多维关联规则。单维关联规则处理同一个属性(或维)内的联系;多维关联规则处理多个属性(或维)之间的联系。