數(shù)據(jù)挖掘2015最新精品課程完整課件(第5講)-關(guān)聯(lián)規(guī)則挖掘的其它問題

關(guān)聯(lián)規(guī)則挖掘的其它問題主要內(nèi)容基于多最小支持度的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則的評價支持度的分布大多數(shù)數(shù)據(jù)集中支持度的分布都不平衡一個零售數(shù)據(jù)集中支持度的分布支持度的分布如何合理設(shè)置最小支持度閾值minsup?minsup過高,可能會丟失稀有的、令人感興趣的項目(如，貴重商品或耐用品)。minsup過低,則計算開銷過大，結(jié)果項集過多。使用單一的最小支持度效果不佳。多最小支持度模型每個項目都有一個最小支持度(MinimumItemSupports,MIS)。通過為不同的項目提供不同的MIS值，用戶可以表達(dá)對不同規(guī)則的不同支持度的需求。規(guī)則的最小支持度設(shè)MIS(i)代表項目i的MIS.規(guī)則R的最小支持度閾值minsup是規(guī)則所包含項目的最小MIS。規(guī)則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%支持度不再滿足反單調(diào)性假設(shè): 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進(jìn)行修改:L1:1-頻繁項集（支持度minMIS(i)）F1:{i|sup(i)MIS(i)}C2:2-候選項集從F1，而不是L1中連接得到舉例假設(shè)數(shù)據(jù)集包含100條事務(wù)，第一次掃描數(shù)據(jù)庫得到如下項目的支持度: {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性質(zhì)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性質(zhì)ABCDEABACADAEBCBDBECDCEDEABCABDABEACDACEADEBCDBCEBDECDEItemMIS(I)Sup(I)A0.10%0.25%B0.20%0.26%C0.30%0.39%D0.50%0.05%E3%4.20%主要內(nèi)容基于多最小支持度的關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則的評價挖掘各種關(guān)聯(lián)規(guī)則支持度-置信度框架的局限性支持度的缺點在于許多潛在有意義的模式由于包含支持度小的項而被刪去。置信度的缺陷在于忽略了規(guī)則后件中項集的支持度。如咖啡和茶的問題。置信度和支持度的失效Example(Aggarwal&Yu,PODS98)5000名學(xué)生中3000打藍(lán)球3750吃稻米2000既打籃球又吃稻米打籃球

吃稻米

[40%,66.7%]被誤導(dǎo)了，因為吃稻米的學(xué)生總數(shù)為75%，高于66.7%.打籃球

不吃稻米

[20%,33.3%]則更為精確,盡管其支持度和置信度更低感興趣度的應(yīng)用InterestingnessMeasuresLift作為相關(guān)度量稱規(guī)則A－>B的提升度大于1，A和B正相關(guān)，A的出現(xiàn)意味著B的出現(xiàn)等于1，A和B獨立小于1，A和B負(fù)相關(guān)，A的出現(xiàn)以往著B的減少感興趣度的類型很多針對不同的應(yīng)用，不同感興趣度的效果不一樣興趣度的

度量列表合適的感興趣度Piatetsky-Shapiro:一個合適的感興趣度應(yīng)具備3個特性:若A和B是統(tǒng)計獨立的，則M(A,B)=0當(dāng)P(A)和P(B)保持不變時，M(A,B)隨著P(A,B)單調(diào)遞增當(dāng)P(A,B)和P(B)(或P(A))保持不變時，M(A,B)隨著P(A)(或P(B))單調(diào)遞減感興趣度的性質(zhì)M(A,B)=M(B,A)?對稱的感興趣度:support,lift,collectivestrength,cosine,Jaccard,etc非對稱的感興趣度:confidence,conviction,Laplace,J-measure,etc擴(kuò)展不變性MaleFemaleHigh235Low1453710MaleFemaleHigh43034Low2404267076Grade-GenderExample評價結(jié)果與樣本數(shù)量的成倍增長無關(guān)2x10x置換不變性:-CoefficientYYX601070X1020307030100YYX201030X1060703070100兩張表中，-Coefficient的值相同將列聯(lián)表中f11與f00交換、f10與f01交換后評價結(jié)果不變無關(guān)添加不變性f00值的變化對評價結(jié)果沒有影響對稱感興趣度的性質(zhì)主觀感興趣度客觀感興趣度:根據(jù)數(shù)據(jù)中的統(tǒng)計結(jié)果對模式排序e.g.,21measuresofassociation(support,confidence,Laplace,Gini,mutualinformation,Jaccard,etc).主觀感興趣度:根據(jù)用戶的解釋對模式排序Apatternissubjectivelyinterestingifitcontradictsthe

expectationofauser(Silberschatz&Tuzhilin)Apatternissubjectivelyinterestingifitisactionable

(Silberschatz&Tuzhilin)基于意外的感興趣度需要對用戶的期望建模(領(lǐng)域知識)將用戶的期望與從數(shù)據(jù)中實際發(fā)現(xiàn)的結(jié)果結(jié)合起來+Patternexpectedtobefrequent-PatternexpectedtobeinfrequentPatternfoundtobefrequentPatternfoundtobeinfrequent+-ExpectedPatterns-+UnexpectedPatterns興趣度度量的特性興趣度度量的比較MilkNoMilkSum(row)Coffeem,c~m,ccNoCoffeem,~c