数据挖掘2015最新精品课程完整课件(第5讲)---关联规则挖掘的其它问题

关联规则挖掘的其它问题主要内容基于多最小支持度的关联规则关联规则的评价支持度的分布大多数数据集中支持度的分布都不平衡一个零售数据集中支持度的分布支持度的分布如何合理设置最小支持度阈值minsup?minsup过高,可能会丢失稀有的、令人感兴趣的项目(如，贵重商品或耐用品)。minsup过低,则计算开销过大，结果项集过多。使用单一的最小支持度效果不佳。多最小支持度模型每个项目都有一个最小支持度(MinimumItemSupports,MIS)。通过为不同的项目提供不同的MIS值，用户可以表达对不同规则的不同支持度的需求。规则的最小支持度设MIS(i)代表项目i的MIS.规则R的最小支持度阈值minsup是规则所包含项目的最小MIS。规则R:a1,a2,…,akak+1,…,ar满足最小支持度阈值，若其实际的支持度min(MIS(a1),MIS(a2),…,MIS(ar)).多最小支持度举例MIS(Milk)=5%,MIS(Coke)=3%,MIS(Broccoli)=0.1%,MIS(Salmon)=0.5%MIS({Milk,Broccoli})=min(MIS(Milk),MIS(Broccoli))=0.1%支持度不再满足反单调性假设:Support(Milk,Coke)=1.5%且Support(Milk,Coke,Broccoli)=0.5%{Milk,Coke}不频繁，但{Milk,Coke,Broccoli}频繁MSapriori算法按支持度升序排列项目e.g.:MIS(1)=10%MIS(2)=20%MIS(3)=5%MIS(4)=6%顺序:3,4,1,2对Apriori进行修改:L1:1-频繁项集（支持度minMIS(i)）F1:{i|sup(i)MIS(i)}C2:2-候选项集从F1，而不是L1中连接得到举例假设数据集包含100条事务，第一次扫描数据库得到如下项目的支持度:{3}.count=6,{4}.count=3,{1}.count=9,{2}.count=25.则L1={3,1,2},andF1={3,2}由于4.count/nMIS(3)(=5%)，故L1中不包含4。由于1.count/nMIS(1)(=10%)，故F1中不包含1。MIS(1)=10%MIS(2)=20%MIS(3)=5%MIS(4)=6%多最小支持度—Apriori性质AItemMIS(I)Sup(I)A0.10%0.25%B0.20%0.26%C0.30%0.39%D0.50%0.05%E3%4.20%BCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDE多最小支持度—Apriori性质ABCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDEItemMIS(I)Sup(I)A0.10%0.25%B0.20%0.26%C0.30%0.39%D0.50%0.05%E3%4.20%主要内容基于多最小支持度的关联规则关联规则的评价挖掘各种关联规则支持度-置信度框架的局限性支持度的缺点在于许多潜在有意义的模式由于包含支持度小的项而被删去。置信度的缺陷在于忽略了规则后件中项集的支持度。如咖啡和茶的问题。置信度和支持度的失效Example(Aggarwal&Yu,PODS98)5000名学生中3000打蓝球3750吃稻米2000既打篮球又吃稻米打篮球吃稻米[40%,66.7%]被误导了，因为吃稻米的学生总数为75%，高于66.7%.打篮球不吃稻米[20%,33.3%]则更为精确,尽管其支持度和置信度更低basketballnotbasketballsum(row)cereal200017503750notcereal10002501250sum(col.)300020005000感兴趣度的应用InterestingnessMeasuresLift作为相关度量2000/5000(,)0.893000/5000*3750/5000liftBasketballCereal)()()(BPAPBAPlift1000/5000(,)1.333000/5000*1250/5000liftBasketballCerealbasketballnotbasketballsum(row)cereal200017503750notcereal10002501250sum(col.)300020005000称规则A－B的提升度大于1，A和B正相关，A的出现意味着B的出现等于1，A和B独立小于1，A和B负相关，A的出现以往着B的减少感兴趣度的类型很多针对不同的应用，不同感兴趣度的效果不一样兴趣度的度量列表合适的感兴趣度Piatetsky-Shapiro:一个合适的感兴趣度应具备3个特性:若A和B是统计独立的，则M(A,B)=0当P(A)和P(B)保持不变时，M(A,B)随着P(A,B)单调递增当P(A,B)和P(B)(或P(A))保持不变时，M(A,B)随着P(A)(或P(B))单调递减感兴趣度的性质BBApqArsAABprBqsM(A,B)=M(B,A)?对称的感兴趣度:support,lift,collectivestrength,cosine,Jaccard,etc非对称的感兴趣度:confidence,conviction,Laplace,J-measure,etc扩展不变性MaleFemaleHigh235Low1453710MaleFemaleHigh43034Low2404267076Grade-GenderExample评价结果与样本数量的成倍增长无关2x10x置换不变性:-CoefficientYYX601070X1020307030100YYX201030X10607030701005238.03.07.03.07.07.07.06.0两张表中，-Coefficient的值相同5238.03.07.03.07.03.03.02.0将列联表中f11与f00交换、f10与f01交换后评价结果不变无关添加不变性BBApqArsBBApqArs+kf00值的变化对评价结果没有影响对称感兴趣度的性质主观感兴趣度客观感兴趣度:根据数据中的统计结果对模式排序e.g.,21measuresofassociation(support,confidence,Laplace,Gini,mutualinformation,Jaccard,etc).主观感兴趣度:根据用户的解释对模式排序Apatternissubjectivelyinterestingifitcontradictstheexpectationofauser(Silberschatz&Tuzhilin)Apatternissubjectivelyinterestingifitisactionable(Silberschatz&Tuzhilin)基于意外的感兴趣度需要对用户的期望建模(领域知识)将用户的期望与从数据中实际发现的结果结合起来+Patternexpectedtobefrequent-PatternexpectedtobeinfrequentPatternfoundtobefrequentPatternfoundtobeinfrequent+-ExpectedPatterns-+UnexpectedPatterns兴趣度度量的特性兴趣度度量的比较MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c~m,~c~cSum(col.)m~mNull-(transaction)零不变是相关分析的关键因素Lift和2非零不变存在5个零不变度量Null-transactionsw.r.t.mandcNull-invariantSubtle:TheydisagreeKulczynskimeasure(1927)