数据挖掘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

/n<MIS(3)(=5%)，故L1

中不包含4。由于1.count

/n<MIS(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%]则更为精确,尽管其支持度和置信度更低感兴趣度的应用InterestingnessMeasuresLift作为相关度量称规则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))单调递减感兴趣度的性质M(A,B)=M(B,A)?对称的感兴趣度:support,lift,collectivestrength,cosine,Jaccard,etc非对称的感兴趣度:confidence,conviction,Laplace,J-measure,etc扩展不变性MaleFemaleHigh235Low1453710MaleFemaleHigh43034Low2404267076Grade-GenderExample评价结果与样本数量的成倍增长无关2x10x置换不变性:-CoefficientYYX601070X1020307030100YYX201030X1060703070100两张表中，-Coefficient的值相同将列联表中f11与f00交换、f10与f01交换后评价结果不变无关添加不变性f00值的变化对评价结果没有影响对称感兴趣度的性质主观感兴趣度客观感兴趣度:根据数据中的统计结果对模式排序e.g.,21measuresofassociation(support,confidence,Laplace,Gini,mutualinformation,Jaccard,etc).主观感兴趣度:根据用户的解释对模式排序Apatternissubjectivelyinterestingifitcontradictsthe

expectationofauser(Silberschatz&Tuzhilin)Apatternissubjectivelyinterestingifitisactionable

(Silberschatz&Tuzhilin)基于意外的感兴趣度需要对用户的期望建模(领域知识)将用户的期望与从数据中实际发现的结果结合起来+Patternexpectedtobefrequent-PatternexpectedtobeinfrequentPatternfoundtobefrequentPatternfoundtobeinfrequent+-ExpectedPatterns-+UnexpectedPatterns兴趣度度量的特性兴趣度度量的比较MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c