華南理工大學(xué)數(shù)據(jù)挖掘第五章

第五章關(guān)聯(lián)規(guī)則□關(guān)聯(lián)規(guī)則挖掘一相關(guān)概念頻繁模式：頻繁地出現(xiàn)在數(shù)據(jù)集中的模式(如項(xiàng)集、子序列或子結(jié)構(gòu))為什么頻繁模式挖掘重要？?揭示數(shù)據(jù)集中內(nèi)在和重要模式?為許多挖掘人物提供基礎(chǔ)所有形如X=Y蘊(yùn)涵式的稱為關(guān)聯(lián)規(guī)則，這里XU|,YU|,并且xnv=(D支持度S：—個(gè)爭務(wù)中包含X0W勺可能性L.g：support(X=>Y):在所有事件中既購買了X又購買了Y的概率置信度c：一個(gè)事務(wù)中包含X也包含Y的條件概率L.g：confidence"今Y):購買了X的情況下購買Y的概率Support(X=^Y))=support({X}<j{/})confidence%今Y)=山(⑴⑷)support(pc})□使用Apriori方法挖掘關(guān)聯(lián)規(guī)則頻繁項(xiàng)集：如果項(xiàng)集滿足最小支持度，則稱之為頻繁項(xiàng)集頻繁項(xiàng)集的基本特征：任何頻繁項(xiàng)集的非空子集均為頻繁項(xiàng)集Apriori方法:圖6.3 候選項(xiàng)集和傾緊境集的產(chǎn)生，皺小支持訂數(shù)為2連援更C尸匸2 L尸{{II功爐型何1.12}?{11工}?{110}?{1213},{12』4},{12砂2{{HJ2J3},{II,12J5}.{I1J3^5>412^4},{12,5J5},{DJ4J5}}使用Apnonft??枝：按緊頂樂的所右千集必?fù)Q楚孩緊的.存在候選項(xiàng)集?其于集不是荻繁的叫？?{I1J2J3}的2■項(xiàng)子集￡{IH2}?{1113}和{I2J3}?{II衛(wèi),13}的曲有2?頂子集都是D的元蹇.Wit*保留{I1JXI3}在G中.?{I1I2Q}的2■煩子集是(11衛(wèi)}?{1115}和{1215}-{1112J5》的斯有2?煩子集都楚匚的元素.例此?保留{I1QI5}在G中.■{HJ3Q)的2■項(xiàng)于集是(1卩3〉?和{13尸}?{BJ5}不足L：的元素?內(nèi)而不是療驚的.這樣.由U中朗除{I1J3J5}.-{I2J3I4}的厶項(xiàng)子集是{I2J3},{12.14}和{I3J4}?{BJ4}不是匚的元素，內(nèi)而不是傾驚的.這樣.山Cj中制除{I2J3J4}.-{I2J3I5}的2■項(xiàng)子集是{I2J3},{12.15}和{13耳}?{BJ5}不是L：的元素，內(nèi)而不是頻鷲的.這樣.山G中刪除{I2J3Q}.■連接步：通過連接產(chǎn)生G■剪枝步：如果一個(gè)候選k?項(xiàng)集的(k?l)?子集不在(k?：l)?的頻繁項(xiàng)集中，則該侯選集也不可能是頻繁的,從而由G刪除■Pseudo-code:G大小為k的候選集大小為k的頻繁項(xiàng)集L,={頻繁項(xiàng)集片for(Ar=1;￡f!=0;Ar++)dobegin

j=從一中產(chǎn)生的磁樂；

foreachtransactionfeDdo

對丁包含在t中的展丁?C歎"的所有候選集的計(jì)數(shù)加一—=中具有最小支持度的候選集endreturnwSDatak1stscanItemset1□m4-{C}3<D}1｛曰356iTPmwTtATcytB7c>~E}6(Ar62232I?7e?TbTFTcTeT?~23}7b}Sil

p

Q

B{&刁

{C^}Ifpmsptis提高Aproori效率的方法：Is基于hash的項(xiàng)集計(jì)數(shù)2、 較少交易記錄3、 劃分4、 抽樣5、 動(dòng)態(tài)項(xiàng)集計(jì)數(shù)：在添加一個(gè)新的候選集之前，先估計(jì)一下是不是他的所有子集都是頻繁的?！跬诰蚨鄬雨P(guān)聯(lián)規(guī)則自上而下，深度優(yōu)先的方法：■先找高層的“強(qiáng)"規(guī)則：牛奶亠面包[20%,60%].■再找他們底層的“弱"規(guī)則：酸奶刁黃面包[6%,50%].支持度遞減：隨著層次的降低支持度遞減■層與層獨(dú)立：■完全的寬度搜索■層交叉單項(xiàng)過濾■層交叉k—項(xiàng)集過濾■受控的層交叉單項(xiàng)過濾為什么要逐步精化挖掘操作的代價(jià)町能高或低，結(jié)呆可能過細(xì)致或粗糙在速度和質(zhì)量之間折衷：逐步精化口多維關(guān)聯(lián)規(guī)則挖掘單維關(guān)聯(lián)規(guī)則（維內(nèi)關(guān)聯(lián)規(guī)則）關(guān)聯(lián)規(guī)則中僅包含單個(gè)謂詞（維）通常針對的是爭務(wù)數(shù)據(jù)庫L.g:buys（X,"milk"）=>buys（X,"bread"）多維關(guān)聯(lián)規(guī)則：規(guī)則內(nèi)包含2個(gè)以上維/謂詞■維間關(guān)聯(lián)規(guī)則（不重復(fù)謂詞）■混合維關(guān)聯(lián)規(guī)則[存在重復(fù)謂詞)L.g:age(X/19-25n)Abuys(X,“computer1')=>buys[X,“printer")分類屬性(CategoricalAttribute)又稱標(biāo)稱屬性(NominalAttribute)屬性值中包含有限個(gè)確定的不同值，值之間無順序關(guān)系例如：性別、民族、職業(yè)、顏色等量化屬性(QuantitativeAttribute)■屬性值是數(shù)字類型的，值之間隱含了順序知■例如：年齡、收入、銷售量、價(jià)格、銷售額等□關(guān)聯(lián)挖掘與相關(guān)分析興趣度的度量客觀度量■兩個(gè)最為流行的度量：支持度和置信度(supportandconfidence)(該規(guī)則具有一定的欺騙性)主觀度量(Silberschatz&Tuzhilin,KDD95)■一個(gè)規(guī)則(模式)是感興趣的，如果□沒有想到的(用戶感到驚訝的)；□可操作的(用戶在得到結(jié)果后，可以在此之上做些什么)提升：P(AUB)=P(B)*P(A),A和B是獨(dú)立事件5)人 尸U滬(方)■取值小于1,AandB負(fù)相關(guān)■取值大于1,AandB正相關(guān)□基于約束的關(guān)聯(lián)挖掘使用約束的必要性：產(chǎn)生的多數(shù)規(guī)則是用戶不感興趣的，應(yīng)在用戶提供的各種約束的指導(dǎo)下進(jìn)行挖掘在數(shù)據(jù)挖掘中常使用的幾種約束：知識(shí)類型限制：指定要挖掘的知識(shí)類型，如關(guān)聯(lián)規(guī)則。數(shù)據(jù)限制：指定任務(wù)相關(guān)的數(shù)據(jù)集。維/層限制：指定所用的維或概念分層結(jié)構(gòu)的層。興趣度限制：指定規(guī)則興趣度閾值或統(tǒng)計(jì)度量，如支持度和置信度。規(guī)則限制：指定要挖掘的規(guī)則形式。這種限制可以用元規(guī)則(規(guī)則模板)表示，如可以出現(xiàn)在規(guī)則前件或后件中謂詞的最人或最小個(gè)數(shù)，或?qū)傩浴傩灾岛?或聚集之間的聯(lián)系?？偨Y(jié)□人量數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系的發(fā)現(xiàn)在選擇購物、決策分析和商務(wù)管理方面是有用的。一個(gè)流行的應(yīng)用領(lǐng)域是購物籃分析，通過搜索經(jīng)常一塊購買的商品的集合（或序列），研究顧客的購買習(xí)慣。關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項(xiàng)集（項(xiàng)的集合，如A和B,滿足最小支持度閾值,或任務(wù)相關(guān)元組的百分比），然后，由它們產(chǎn)生形如AnB的強(qiáng)關(guān)聯(lián)規(guī)則。這些規(guī)則也滿足最小置信度閾值（預(yù)定義的、在滿足A的條件下滿足B的概率）?！醺鶕?jù)不同的標(biāo)準(zhǔn)，關(guān)聯(lián)規(guī)則可以分成若干類型，如：（1） 根據(jù)規(guī)則所處理的值的類型，關(guān)聯(lián)規(guī)則可以分為布爾的利量化的。布爾關(guān)聯(lián)規(guī)則表現(xiàn)離散（分類）對彖之間的聯(lián)系。量化關(guān)聯(lián)規(guī)則是多維關(guān)聯(lián)規(guī)則，涉及動(dòng)態(tài)離散化的數(shù)值屬性。它也可能涉及分類屬性。（2） 根據(jù)規(guī)則中數(shù)據(jù)涉及的維，關(guān)聯(lián)規(guī)則可以分成單維和多維的’單維關(guān)聯(lián)規(guī)則涉及單個(gè)謂詞或維，如buys；而多維關(guān)聯(lián)規(guī)則涉及多個(gè)（不同的）謂詞或維。單維關(guān)聯(lián)規(guī)則展示的是維內(nèi)聯(lián)系（即，同一個(gè)屬性或維內(nèi)的關(guān)聯(lián)）；而多維關(guān)聯(lián)規(guī)則展示的是維間聯(lián)系（即，屬性/維之間的關(guān)聯(lián)）。（3） 根據(jù)規(guī)則涉及的抽象層，關(guān)聯(lián)規(guī)則可以分為單層和多層的。在單層關(guān)聯(lián)規(guī)則中，項(xiàng)或謂詞的挖掘不考慮不同的抽象層；而多層關(guān)聯(lián)規(guī)則考慮多個(gè)抽彖層。（4） 根據(jù)對關(guān)聯(lián)挖掘的不同擴(kuò)充，關(guān)聯(lián)挖掘町以擴(kuò)充為相關(guān)分析和最大頻繁模式（“最大模式”）與頻繁閉項(xiàng)集挖掘，相關(guān)分析指出相關(guān)項(xiàng)的存在與否。最人模式是一個(gè)頻繁模式P，使得P的任何真超集都不是頻繁的。頻繁閉項(xiàng)集是指：項(xiàng)集c是閉的，如果不存在c的真超集使得包含c的子模式的每個(gè)爭務(wù)也包含□Apriori算法是一種有效的關(guān)聯(lián)規(guī)則挖掘算法，它逐級探查，進(jìn)行挖掘。Apriori性質(zhì)：頻繁項(xiàng)集的所有非空子集都必須是頻繁的。在第k次迭代，它根據(jù)頻繁k-項(xiàng)集，形成頻繁（k+1）-項(xiàng)集候選，并打描數(shù)據(jù)庫一次，找出完整的頻繁（k+1）-項(xiàng)集Lh“涉及散列和爭務(wù)壓縮的變形可以用來使得過程更有效。其它變形涉及劃分?jǐn)?shù)據(jù)（在每一部分上挖掘，然后合并結(jié)呆）和數(shù)據(jù)選樣（在數(shù)據(jù)子集上挖掘）。這些變形可以將數(shù)據(jù)掃描次數(shù)減少到一或兩次。□頻繁模式增長（FP-增長）是一種不產(chǎn)生候選的挖掘頻繁項(xiàng)集方法。它構(gòu)造一個(gè)高度壓縮的數(shù)據(jù)結(jié)構(gòu)（FP-樹），壓縮原來的事務(wù)數(shù)據(jù)庫。不是使用priori方法的產(chǎn)生-測試策略，它聚焦于頻繁模式（段）增長，避免了高代價(jià)的候選產(chǎn)生，獲得更好的效率?！醵鄬雨P(guān)聯(lián)規(guī)則町以根據(jù)每個(gè)抽彖層上的最小支持度閾值如何定義，使用多種策略挖掘。當(dāng)在較低層使用遞減的支持度時(shí)，剪枝方法包括層交叉按單項(xiàng)過濾，層交叉按k-項(xiàng)集過濾。冗余的（后代）關(guān)聯(lián)規(guī)則可以刪除，不向用戶提供，如呆根據(jù)其對應(yīng)的祖先規(guī)則，它們的支持度和置信度接近于期望值的話。□挖掘多維關(guān)聯(lián)規(guī)則可以根據(jù)對量化屬性處理分為若干類。第一，量化屬性可以根據(jù)預(yù)定義的概念分層靜態(tài)離散化。數(shù)據(jù)方非常適合這種方法，因?yàn)閿?shù)據(jù)方和量化屬性都可以利用概念分層。第二，可以挖掘量化關(guān)聯(lián)規(guī)則，其量化屬性根據(jù)分箱動(dòng)態(tài)離散化，“臨近的”關(guān)聯(lián)規(guī)則可以用聚類組合。第三，町以挖掘基于距離的關(guān)聯(lián)規(guī)則，其中區(qū)間根據(jù)聚類定義。□并非所有的強(qiáng)關(guān)聯(lián)規(guī)則都是有趣的。對于統(tǒng)計(jì)相關(guān)的項(xiàng)，可以挖掘相關(guān)規(guī)則，□基于限制的挖掘允許用戶聚焦，按提供的元規(guī)則（即，模式模板）和其它挖掘限