數(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ī)則的評(píng)價(jià)支持度的分布大多數(shù)數(shù)據(jù)集中支持度的分布都不平衡一個(gè)零售數(shù)據(jù)集中支持度的分布支持度的分布如何合理設(shè)置最小支持度閾值minsup?minsup過高,可能會(huì)丟失稀有的、令人感興趣的項(xiàng)目(如，貴重商品或耐用品)。minsup過低,則計(jì)算開銷過大，結(jié)果項(xiàng)集過多。使用單一的最小支持度效果不佳。多最小支持度模型每個(gè)項(xiàng)目都有一個(gè)最小支持度(MinimumItemSupports,MIS)。通過為不同的項(xiàng)目提供不同的MIS值，用戶可以表達(dá)對(duì)不同規(guī)則的不同支持度的需求。規(guī)則的最小支持度設(shè)MIS(i)代表項(xiàng)目i的MIS.規(guī)則R的最小支持度閾值minsup是規(guī)則所包含項(xiàng)目的最小MIS。規(guī)則R:a1,a2,…,ak

ak+1,…,ar

滿足最小支持度閾值，若其實(shí)際的支持度 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算法按支持度升序排列項(xiàng)目e.g.:MIS(1)=10%

MIS(2)=20%

MIS(3)=5%

MIS(4)=6%

順序:3,4,1,2對(duì)Apriori進(jìn)行修改:L1:1-頻繁項(xiàng)集（支持度minMIS(i)）F1:{i|sup(i)MIS(i)}C2:2-候選項(xiàng)集從F1，而不是L1中連接得到舉例假設(shè)數(shù)據(jù)集包含100條事務(wù)，第一次掃描數(shù)據(jù)庫得到如下項(xiàng)目的支持度: {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ī)則的評(píng)價(jià)挖掘各種關(guān)聯(lián)規(guī)則支持度-置信度框架的局限性支持度的缺點(diǎn)在于許多潛在有意義的模式由于包含支持度小的項(xiàng)而被刪去。置信度的缺陷在于忽略了規(guī)則后件中項(xiàng)集的支持度。如咖啡和茶的問題。置信度和支持度的失效Example(Aggarwal&Yu,PODS98)5000名學(xué)生中3000打藍(lán)球3750吃稻米2000既打籃球又吃稻米打籃球

吃稻米

[40%,66.7%]被誤導(dǎo)了，因?yàn)槌缘久椎膶W(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獨(dú)立小于1，A和B負(fù)相關(guān)，A的出現(xiàn)以往著B的減少感興趣度的類型很多針對(duì)不同的應(yīng)用，不同感興趣度的效果不一樣興趣度的

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

expectationofauser(Silberschatz&Tuzhilin)Apatternissubjectivelyinterestingifitisactionable

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