版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
大型數(shù)據庫中的關聯(lián)規(guī)則挖掘什么是關聯(lián)規(guī)則挖掘?關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據中項集之間有趣的關聯(lián)或相關聯(lián)系。隨著大量數(shù)據不停地收集和存儲,許多業(yè)界人士對于從他們的數(shù)據庫中挖掘關聯(lián)規(guī)則越來越感興趣。從大量商務事務記錄中發(fā)現(xiàn)有趣的關聯(lián)關系,可以幫助許多商務決策的制定,如分類設計、交叉購物和賤賣分析。關聯(lián)規(guī)則挖掘的一個典型例子是購物籃分析。該過程通過發(fā)現(xiàn)顧客放入其購物籃中不同商品(圖6.1)之間聯(lián)系,分析顧客的購買習慣。通過了解哪些商品頻繁地被顧客同時購買,這種關聯(lián)的發(fā)現(xiàn)可以幫助零售商制定營銷策略。例如,在同一次去超級市場,如果顧客購買牛奶,他也購買面包(和什么類型的面包)的可能性有多大?通過幫助零售商有選擇地經銷和安排貨架,這種信息可以引導銷售。例如,將牛奶和面包盡可能放近一些,可以進一步刺激一次去商店同時購買這些商品?!澳虿寂c啤酒”——典型關聯(lián)分析案例采用關聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。在美國,一些年輕的父親下班后經常要到超市去買嬰兒尿布,超市也因此發(fā)現(xiàn)了一個規(guī)律,在購買嬰兒尿布的年輕父親們中,有30%~40%的人同時要買一些啤酒。超市隨后調整了貨架的擺放,把尿布和啤酒放在一起,明顯增加了銷售額。同樣的,我們還可以根據關聯(lián)規(guī)則在商品銷售方面做各種促銷活動。購物籃分析假定作為AllElectronics
的分店經理,你想更加了解你的顧客的購物習慣。例如,你想知道“什么商品組或集合顧客多半會在一次購物時同時購買?”為回答你的問題,你可以在你的商店顧客事務零售數(shù)據上運行購物籃分析。分析結果可以用于市場規(guī)劃、廣告策劃、分類設計。例如,購物籃分析可以幫助經理設計不同的商店布局。一種策略是:經常一塊購買的商品可以放近一些,以便進一步刺激這些商品一起銷售。例如,如果顧客購買計算機也傾向于同時購買財務軟件,將硬件擺放離軟件陳列近一點,可能有助于增加二者的銷售。另一種策略是:將硬件和軟件放在商店的兩端,可能誘發(fā)買這些商品的顧客一路挑選其它商品。例如,在決定購買一臺很貴的計算機之后,去看軟件陳列,購買財務軟件,路上可能看到安全系統(tǒng),可能會決定也買家庭安全系統(tǒng)。購物籃分析也可以幫助零售商規(guī)劃什么商品降價出售。如果顧客趨向于同時購買計算機和打印機,打印機降價出售可能既促使購買打印機,又促使購買計算機。購物籃分析如果問題的全域是商店中所有商品的集合,則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買,則每個購物籃都可以用一個布爾向量表示;而通過分析布爾向量則可以得到商品被頻繁關聯(lián)或被同時購買的模式,這些模式就可以用關聯(lián)規(guī)則表示關聯(lián)規(guī)則的兩個興趣度度量支持度置信度6.1.2基本概念設I={i1,i2,...,im
}是項的集合。設任務相關的數(shù)據D是數(shù)據庫事務的集合,其中每個事務T是項的集合,使得T?I。每一個事務有一個標識符,稱作TID。設A是一個項集,事務T包含A當且僅當A?T。關聯(lián)規(guī)則是形如A?B的蘊涵式,其中A?I,B?I,并且A∩B=?。規(guī)則A?B在事務集D中成立,具有支持度s,其中s是D中事務包含A∪B(即,A和B二者)的百分比。6.1.2基本概念它是概率P(A∪B)。規(guī)則A?B在事務集D中具有置信度c,如果D中包含A的事務同時也包含B的百分比是c。這是條件概率P(B|A)。support(A?B)=P(A∪B)(6.2)confidence(A?B)=P(B|A)(6.3)6.1.2基本概念同時滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱作強規(guī)則。為方便計,我們用0%和100%之間的值,而不是用0到1之間的值表示支持度和置信度。項的集合稱為項集。包含k個項的項集稱為k-項集。集合{computer,financial_management_software}是一個2-項集。項集的出現(xiàn)頻率是包含項集的事務數(shù),簡稱為項集的頻率、支持計數(shù)或計數(shù)。項集滿足最小支持度min_sup,如果項集的出現(xiàn)頻率大于或等于min_sup
與D中事務總數(shù)的乘積。如果項集滿足最小支持度,則稱它為頻繁項集。頻繁k-項集的集合通常記作Lk?;靖拍睢纠椀募螴={A,B,C,D,E,F}每個事務T由事務標識符TID標識,它是項的集合比如:TID(2000)={A,B,C}任務相關數(shù)據D是數(shù)據庫事務的集合D規(guī)則度量:支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer對所有滿足最小支持度和置信度的關聯(lián)規(guī)則支持度s是指事務集D中包含的百分比置信度c是指D中包含A的事務同時也包含B的百分比假設最小支持度為50%,最小置信度為50%,則有如下關聯(lián)規(guī)則AC(50%,66.6%)CA(50%,100%)大型數(shù)據庫關聯(lián)規(guī)則挖掘(1)基本概念k-項集:包含k個項的集合{牛奶,面包,黃油}是個3-項集項集的頻率是指包含項集的事務數(shù)如果項集的頻率大于(最小支持度×D中的事務總數(shù)),則稱該項集為頻繁項集大型數(shù)據庫關聯(lián)規(guī)則挖掘(2)大型數(shù)據庫中的關聯(lián)規(guī)則挖掘包含兩個過程:找出所有頻繁項集大部分的計算都集中在這一步由頻繁項集產生強關聯(lián)規(guī)則即滿足最小支持度和最小置信度的規(guī)則關聯(lián)規(guī)則挖掘分類(1)關聯(lián)規(guī)則有多種分類:根據規(guī)則中所處理的值類型布爾關聯(lián)規(guī)則量化關聯(lián)規(guī)則(規(guī)則描述的是量化的項或屬性間的關聯(lián)性)根據規(guī)則中涉及的數(shù)據維單維關聯(lián)規(guī)則(僅涉及buys這個維)多維關聯(lián)規(guī)則關聯(lián)規(guī)則挖掘分類(2)根據規(guī)則集所涉及的抽象層單層關聯(lián)規(guī)則多層關聯(lián)規(guī)則(在不同的抽象層發(fā)現(xiàn)關聯(lián)規(guī)則)根據關聯(lián)挖掘的各種擴充挖掘最大的頻繁模式(該模式的任何真超模式都是非頻繁的)挖掘頻繁閉項集(一個項集c是頻繁閉項集,如果不存在其真超集c’,使得每個包含c的事務也包含c’)(最大的頻繁模式和頻繁閉項集可以用來減少挖掘中產生的頻繁項集)由事務數(shù)據庫挖掘單維布爾關聯(lián)規(guī)則最簡單的關聯(lián)規(guī)則挖掘,即單維、單層、布爾關聯(lián)規(guī)則的挖掘。最小支持度50%最小置信度50%對規(guī)則A
C,其支持度=50%置信度Apriori算法(1)Apriori算法是挖掘布爾關聯(lián)規(guī)則頻繁項集的算法Apriori算法利用的是Apriori性質:頻繁項集的所有非空子集也必須是頻繁的。模式不可能比A更頻繁的出現(xiàn)Apriori算法是反單調的,即一個集合如果不能通過測試,則該集合的所有超集也不能通過相同的測試。Apriori性質通過減少搜索空間,來提高頻繁項集逐層產生的效率Apriori算法(2)Apriori算法利用頻繁項集性質的先驗知識(priorknowledge),通過逐層搜索的迭代方法,即將k-項集用于探察(k+1)-項集,來窮盡數(shù)據集中的所有頻繁項集。先找到頻繁1-項集集合L1,然后用L1找到頻繁2-項集集合L2,接著用L2找L3,直到找不到頻繁k-項集,找每個Lk需要一次數(shù)據庫掃描。Apriori算法步驟Apriori算法由連接和剪枝兩個步驟組成。連接步:為找Lk,通過Lk-1
與自己連接產生候選k-項集的集合。該候選項集的集合記作Ck。設l1
和l2
是Lk-1
中的項集。記號li[j]表示li
的第j項(例如,l1[k-2]表示l1
的倒數(shù)第3項)。為方便計,假定事務或項集中的項按字典次序排序。執(zhí)行連接;其中,Lk-1
的元素是可連接的,如果它們前(k-2)個項相同;即,Lk-1
的元素l1
和l2
是可連接的,如果(l1
[1]=l2
[1])∧(l1[2]=l2
[2])∧...∧(l1[k-2]=l2
[k-2])∧(l1
[k-1]<l2
[k-1])。條件(l1[k-1]<l2
[k-1])是簡單地保證不產生重復。連接l1
和l2
產生的結果項集是l1[1]l1
[2]...l1
[k-1]l2
[k-1]。剪枝步:Ck
是Lk
的超集;即,它的成員可以是,也可以不是頻繁的,但所有的頻繁k-項集都包含在Ck
中。掃描數(shù)據庫,確定Ck
中每個候選的計數(shù),從而確定Lk(即,根據定義,計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的,從而屬于Lk)。然而,Ck
可能很大,這樣所涉及的計算量就很大。為壓縮Ck,可以用以下辦法使用Apriori
性質:任何非頻繁的(k-1)-項集都不是可能是頻繁k-項集的子集。因此,如果一個候選k-項集的(k-1)-子集不在Lk-1中,則該候選也不可能是頻繁的,從而可以由Ck
中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。例6.1讓我們看一個Apriori
的具體例子。該例基于圖6.2的AllElectronics
的事務數(shù)據庫。數(shù)據庫中有9個事務,即|D|=9。Apriori
假定事務中的項按字典次序存放。我們使用圖6.3解釋Apriori算法發(fā)現(xiàn)D中的頻繁項集。Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持計數(shù):2使用Apiori性質由L2產生C31.連接:C3=L2
L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,E}}={{A,B,C},{A,C,E},{B,C,E}}2.使用Apriori性質剪枝:頻繁項集的所有子集必須是頻繁的,對候選項C3,我們可以刪除其子集為非頻繁的選項:{A,B,C}的2項子集是{A,B},{A,C},{B,C},其中{A,B}不是L2的元素,所以刪除這個選項;{A,C,E}的2項子集是{A,C},{A,E},{C,E},其中{A,E}
不是L2的元素,所以刪除這個選項;{B,C,E}的2項子集是{B,C},{B,E},{C,E},它的所有2-項子集都是L2的元素,因此保留這個選項。3.這樣,剪枝后得到C3={{B,C,E}}由頻繁項集產生關聯(lián)規(guī)則同時滿足最小支持度和最小置信度的才是強關聯(lián)規(guī)則,從頻繁項集產生的規(guī)則都滿足支持度要求,而其置信度則可由一下公式計算:每個關聯(lián)規(guī)則可由如下過程產生:對于每個頻繁項集l,產生l的所有非空子集;對于每個非空子集s,如果 則輸出規(guī)則“ ”6.2.3提高Apriori的有效性(1)基于散列的技術(散列項集計數(shù)):一種基于散列的技術可以用于壓縮候選k-項集Ck(k>1)。例如,當掃描數(shù)據庫中每個事務,由C1中的候選1-項集產生頻繁1-項集L1時,我們可以對每個事務產生所有的2-項集,將它們散列(即,映射)到散列表結構的不同桶中,并增加對應的桶計數(shù)(圖6.6)。在散列表中對應的桶計數(shù)低于支持度閾值的2-項集不可能是頻繁2-項集,因而應當由候選項集中刪除。這種基于散列的技術可以大大壓縮要考察的k-項集(特別是當k=2時)。6.2.3提高Apriori的有效性6.2.3提高Apriori的有效性(2)事務壓縮(壓縮進一步迭代掃描的事務數(shù)):不包含任何k-項集的事務不可能包含任何(k+1)-項集。這樣,這種事務在其后的考慮時,可以加上標記或刪除,因為為產生j-項集(j>k),掃描數(shù)據庫時不再需要它們。6.2.3提高Apriori的有效性劃分(為找候選項集劃分數(shù)據):可以使用劃分技術,它只需要兩次數(shù)據庫掃描,以挖掘頻繁項集(圖6.7)。它包含兩遍。在第I遍,算法將D中的事務劃分成n個非重疊的部分。如果D中事務的最小支持度閾值為min_sup,則每個部分的最小支持度計數(shù)為min_sup×該部分中事務數(shù)。對每一部分,找出該部分內的頻繁項集。這些稱作局部頻繁項集。該過程使用一種特殊的數(shù)據結構,對于每個項集,記錄包含項集中項的事務的TID。這使得對于k=1,2,..,找出所有的局部頻繁k-項集只需要掃描一次數(shù)據庫。6.2.3提高Apriori的有效性局部頻繁項集可能不是整個數(shù)據庫D的頻繁項集。D的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。這樣,所有的局部頻繁項集作為D的候選項集。所有部分的頻繁項集的集合形成D的全局候選項集。在第II遍,第二次掃描D,評估每個候選的實際支持度,以確定全局頻繁項集。每一部分的大小和劃分的數(shù)目這樣確定,使得每一部分能夠放入內存,這樣每遍只需要讀一次。6.2.3提高Apriori的有效性(4)選樣(在給定數(shù)據的一個子集挖掘):選樣方法的基本思想是:選取給定數(shù)據庫D的隨機樣本S,然后,在S而不是在D中搜索頻繁項集。用這種方法,我們犧牲了一些精度換取了有效性。樣本S的大小這樣選取,使得可以在內存搜索S中頻繁項集;這樣,總共只需要掃描一次S中的事務。由于我們搜索S中而不是D中的頻繁項集,我們可能丟失一些全局頻繁項集。為減少這種可能性,我們使用比最小支持度低的支持度閾值來找出局部于S的頻繁項集(記作LS)。6.2.3提高Apriori的有效性然后,數(shù)據庫的其余部分用于計算LS中每個項集的實際頻繁度。有一種機制可以用來確定是否所有的頻繁項集都包含在LS中。如果LS實際包含了D中的所有頻繁項集,只需要掃描一次D。否則,可以做第二次掃描,以找出在第一次掃描時遺漏的頻繁項集。當效率最為重要時,如計算密集的應用必須在不同的數(shù)據上運行時,選樣方法特別合適。6.2.3提高Apriori的有效性(5)動態(tài)項集計數(shù)(在掃描的不同點添加候選項集):動態(tài)項集計數(shù)技術將數(shù)據庫劃分為標記開始點的塊。不象Apriori
僅在每次完整的數(shù)據庫掃描之前確定新的候選,在這種變形中,可以在任何開始點添加新的候選項集。該技術動態(tài)地評估已被計數(shù)的所有項集的支持度,如果一個項集的所有子集已被確定為頻繁的,則添加它作為新的候選。結果算法需要的數(shù)據庫掃描比Apriori
少。其它變形涉及多層和多維關聯(lián)規(guī)則挖掘,在本章的其余部分討論。涉及空間數(shù)據、時間序列數(shù)據和多媒體數(shù)據的關聯(lián)挖掘在第9章討論。6.2.4不產生候選挖掘頻繁項集正如我們已經看到的,在許多情況下,Apriori
的候選產生-檢查方法大幅度壓縮了候選項集的大小,并導致很好的性能。然而,它有兩種開銷可能并非微不足道的。6.2.4不產生候選挖掘頻繁項集它可能需要產生大量候選項集。例如,如果有104個頻繁1-項集,則Apriori
算法需要產生多達107個候選2-項集,累計并檢查它們的頻繁性。此外,為發(fā)現(xiàn)長度為100的頻繁模式,如{a1,...,a100},它必須產生多達2100≈1030
個候選。它可能需要重復地掃描數(shù)據庫,通過模式匹配檢查一個很大的候選集合。對于挖掘長模式尤其如此。6.2.4不產生候選挖掘頻繁項集“可以設計一種方法,挖掘全部頻繁項集,而不產生候選嗎?”一種有趣的方法稱作頻繁模式增長,或簡單地,F(xiàn)P-增長,它采取如下分治策略:將提供頻繁項集的數(shù)據庫壓縮到一棵頻繁模式樹(或FP-樹),但仍保留項集關聯(lián)信息;然后,將這種壓縮后的數(shù)據庫分成一組條件數(shù)據庫(一種特殊類型的投影數(shù)據庫),每個關聯(lián)一個頻繁項,并分別挖掘每個數(shù)據庫。讓我們看一個例子。6.2.4不產生候選挖掘頻繁項集例6.3使用頻繁模式增長方法,我們重新考察例6.1中圖6.2事務數(shù)據庫D的挖掘。數(shù)據庫的第一次掃描與Apriori
相同,它導出頻繁項(1-項集)的集合,并得到它們的支持度計數(shù)(頻繁性)。設最小支持度計數(shù)為2。頻繁項的集合按支持度計數(shù)的遞減序排序。結果集或表記作L。這樣,我們有L=[I2:7,I1:6,I3:6,I4:2,I5:2]。6.2.4不產生候選挖掘頻繁項集然后,F(xiàn)P-樹構造如下:首先,創(chuàng)建樹的根結點,用“null”標記。二次掃描數(shù)據庫D。每個事務中的項按L中的次序處理(即,根據遞減支持度計數(shù)排序)并對每個事務創(chuàng)建一個分枝。例如,第一個事務“T100:I1,I2,I5”按L的次序包含三個項{I2,I1,I5},導致構造樹的第一個分枝<(I2:1),(I1:1),(I5:1)>。該分枝具有三個結點,其中,I2作為根的子女鏈接,I1鏈接到I2,I5鏈接到I1。6.2.4不產生候選挖掘頻繁項集第二個事務T200按L的次序包含項I2和I4,它導致一個分枝,其中,I2鏈接到根,I4鏈接到I2。然而,該分枝應當與T100已存在的路徑共享前綴<I2>。這樣,我們將結點I2的計數(shù)增加1,并創(chuàng)建一個新結點(I4:1),它作為(I2:2)的子女鏈接。一般地,當為一個事務考慮增加分枝時,沿共同前綴上的每個結點的計數(shù)增加1,為隨在前綴之后的項創(chuàng)建結點并鏈接。6.2.4不產生候選挖掘頻繁項集為方便樹遍歷,創(chuàng)建一個項頭表,使得每個項通過一個結點鏈指向它在樹中的出現(xiàn)。掃描所有的事務之后得到的樹展示在圖6.8中,附上相關的結點鏈。這樣,數(shù)據庫頻繁模式的挖掘問題就轉換成挖掘FP-樹問題。6.2.4不產生候選挖掘頻繁項集6.2.4不產生候選挖掘頻繁項集FP-樹挖掘處理如下。由長度為1的頻繁模式(初始后綴模式)開始,構造它的條件模式基(一個“子數(shù)據庫”,由FP-樹中與后綴模式一起出現(xiàn)的前綴路徑集組成)。然后,構造它的(條件)FP-樹,并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與由條件FP-樹產生的頻繁模式連接實現(xiàn)。6.2.4不產生候選挖掘頻繁項集FP-樹的挖掘總結在表6.1中,讓我們首先考慮I5,它是L中的最后一個項,而不是第一個。其原因隨著我們解釋FP-樹挖掘過程就會清楚。I5出現(xiàn)在圖6.8的FP-樹的兩個分枝。(I5的出現(xiàn)容易通過沿它的結點鏈找到。)這些路徑由分枝<(I2I1I5:1)>和<(I2I1I3I5:1)>形成。這樣,考慮I5為后綴,它的兩個對應前綴路徑是<(I2I1:1)>和<(I2I1I3:1)>,它們形成I5的條件模式基。它的條件FP-樹只包含單個路徑<(I2:2I1:2)>;不包含I3,因為它的支持度計數(shù)為1,小于最小支持度計數(shù)。該單個路徑產生頻繁模式的所有組合:I2I5:2,I1I5:2,I2I1I5:2。6.2.4不產生候選挖掘頻繁項集6.2.4不產生候選挖掘頻繁項集對于I4,它的兩個前綴形成條件模式基{(I2I1:1),(I2:1),產生一個單結點的條件FP-樹<I2:2>,并導出一個頻繁模式I2I4:2。注意,盡管I5跟在第一個分枝中的I4之后,也沒有必要在此分析中包含I5,因為涉及I5的頻繁模式在I5的考察時已經分析過。這就是我們?yōu)槭裁从珊竺?,而不是由前面開始處理的原因。6.2.4不產生候選挖掘頻繁項集與以上分析類似,I3的條件模式基是{(I2I1:2),(I2:2),(I1:2)}。它的條件FP-樹有兩個分枝<I2:4,I1:2>和<I1:2>,如圖6.9所示,它產生模式集:{I2I3:4,I1I3:2,I2I1I3:2}。最后,I1的條件模式基是{(I2,4)},它的FP-樹只包含一個結點<I2:4>,產生一個頻繁模式I2I1:4。挖掘過程總結在圖不產生候選挖掘頻繁項集算法:FP-增長。使用FP-樹,通過模式段增長,挖掘頻繁模式。輸入:事務數(shù)據庫D;最小支持度閾值min_sup。輸出:頻繁模式的完全集。方法:1.按以下步驟構造FP-樹:(a)掃描事務數(shù)據庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序,結果為頻繁項表L。6.2.4不產生候選挖掘頻繁項集(b)創(chuàng)建FP-樹的根結點,以“null”標記它。對于D中每個事務Trans,執(zhí)行:選擇Trans中的頻繁項,并按L中的次序排序。設排序后的頻繁項表為[p|P],其中,p是第一個元素,而P是剩余元素的表。調用insert_tree([p
|P],T)。該過程執(zhí)行情況如下。如果T有子女N使得N.item-name=p.item-name,則N的計數(shù)增加1;否則創(chuàng)建一個新結點N,將其計數(shù)設置為1,鏈接到它的父結點T,并且通過結點鏈結構將其鏈接到具有相同item-name的結點。如果P非空,遞歸地調用insert_tree(P,N)。6.2.4不產生候選挖掘頻繁項集6.2.4不產生候選挖掘頻繁項集FP-增長方法將發(fā)現(xiàn)長頻繁模式的問題轉換成遞歸地發(fā)現(xiàn)一些短模式,然后與后綴連接。它使用最不頻繁的項作后綴,提供了好的選擇性。該方法大大降低了搜索開銷。當數(shù)據庫很大時,構造基于內存的FP-樹是不現(xiàn)實的。一種有趣的替換是首先將數(shù)據庫劃分成投影數(shù)據庫的集合,然后在每個投影數(shù)據庫上構造FP-樹并挖掘它。該過程可以遞歸地用于投影數(shù)據庫,如果它的FP-樹還不能放進內存。對FP-樹方法的性能研究表明:對于挖掘長的和短的頻繁模式,它都是有效的和可規(guī)模化的,并且大約比Apriori
算法快一個數(shù)量級。它也比樹-投影算法快。樹-投影算法遞歸地將數(shù)據庫投影為投影數(shù)據庫樹。6.2.5冰山查詢Apriori
算法可以用來提高回答冰山查詢的效率。冰山查詢在數(shù)據挖掘中經常用,特別是對購物籃分析。冰山查詢在一個屬性或屬性集上計算一個聚集函數(shù),以找出大于某個指定閾值的聚集值。給定關系R,它具有屬性a_1,a_2,...,a_n
和b,一個聚集函數(shù)agg_f,冰山查詢形如:6.2.5冰山查詢給定大量輸入數(shù)據元組,滿足having子句中的閾值的輸出元組數(shù)量相對很少。輸出結果看作“冰山頂”,而“冰山”是輸入數(shù)據集。例6.4一個冰山查詢:假定給定銷售數(shù)據,你想產生這樣的一個顧客-商品對的列表,這些顧客購買商品的數(shù)量達到3件或更多。這可以用下面的冰山查詢表示:6.2.5冰山查詢SelectP.cust_ID,P.Item_ID,SUM(P.qty)FromPurchasesPgroupbyP.cust_ID,Pitem_IDHavingSUM(P.qty)>=36.2.5冰山查詢“如何回答例6.4的查詢?”一個常用的策略是使用散列或排序,對所有顧客-商品分組,計算聚集函數(shù)SUM的值,然后刪除被給定的顧客購買的商品數(shù)量少于3的那些。相對于處理的元組總數(shù),滿足該條件的元組多半很少,為改進性能留下了空間。我們可以使用Apriori
性質的變形,裁減需要考慮的顧客-商品對。即,不是考查每個顧客購買的每種商品的數(shù)量,我們可以:6.2.5冰山查詢6.2.5冰山查詢由先驗知識,我們可以刪除許多被散列/排序方法產生的顧客-商品對:僅對cust_list
中的顧客和在item_list
中的商品產生候選顧客-商品對。對每個這樣的對,維持一個計數(shù)。盡管該方法通過預先裁減許多對或分組提高了性能,所產生的顧客-商品對數(shù)量可能依然很大,不能放進內存??梢詫⑸⒘泻瓦x樣策略集成到該過程,幫助提高該查詢回答技術的總體性能。6.2.5冰山查詢6.2.5冰山查詢6.2.5冰山查詢多層關聯(lián)規(guī)則(1)數(shù)據項中經常會形成概念分層底層的數(shù)據項,其支持度往往也較低這意味著挖掘底層數(shù)據項之間的關聯(lián)規(guī)則必須定義不同的支持度AllComputeraccessorysoftwarelaptopfinancialmousecolorprintercomputerdesktopIBMedu.Microsoftb/wHPSonywristpadLogitechTIDItemsT1{IBMD/C,Sonyb/w}T2{M.Sw.,Ms.fin.Sw.}T3{Logi.mouse,Ergowaywristpad}T4{IBMD/C,Ms.Fin.Sw.}T5{IBMD/C}Ergoway多層關聯(lián)規(guī)則(2)在適當?shù)牡燃壨诰虺鰜淼臄?shù)據項間的關聯(lián)規(guī)則可能是非常有用的通常,事務數(shù)據庫中的數(shù)據也是根據維和概念分層來進行儲存的這為從事務數(shù)據庫中挖掘不同層次的關聯(lián)規(guī)則提供了可能。在多個抽象層挖掘關聯(lián)規(guī)則,并在不同的抽象層進行轉化,是數(shù)據挖掘系統(tǒng)應該提供的能力挖掘多層關聯(lián)規(guī)則的方法通常,多層關聯(lián)規(guī)則的挖掘還是使用置信度-支持度框架,可以采用自頂向下策略請注意:概念分層中,一個節(jié)點的支持度肯定不小于該節(jié)點的任何子節(jié)點的支持度由概念層1開始向下,到較低的更特定的概念層,對每個概念層的頻繁項計算累加計數(shù)每一層的關聯(lián)規(guī)則挖掘可以使用Apriori等多種方法例如:先找高層的關聯(lián)規(guī)則:computer->printer[20%,60%]再找較低層的關聯(lián)規(guī)則:laptop->colorprinter[10%,50%]多層關聯(lián)——一致支持度一致支持度:對所有層都使用一致的最小支持度優(yōu)點:搜索時容易采用優(yōu)化策略,即一個項如果不滿足最小支持度,它的所有子項都可以不用搜索缺點:最小支持度值設置困難太高:將丟掉出現(xiàn)在較低抽象層中有意義的關聯(lián)規(guī)則太低:會在較高層產生太多的無興趣的規(guī)則多層關聯(lián)——遞減支持度使用遞減支持度,可以解決使用一致支持度時在最小支持度值上設定的困難遞減支持度:在較低層使用遞減的最小支持度每一層都有自己的一個獨立的最小支持度抽象層越低,對應的最小支持度越小min_sup=5%min_sup=5%min_sup=3%多層關聯(lián)——搜索策略(1)具有遞減支持度的多層關聯(lián)規(guī)則的搜索策略逐層獨立:完全的寬度搜索,沒有頻繁項集的背景知識用于剪枝層交叉單項過濾:一個第i層的項被考察,當且僅當它在第(i-1)層的父節(jié)點是頻繁的(P165,圖6-14)(computer)(laptopcomputer,desktopcomputer)層交叉k項集過濾:一個第i層的k項集被考察,當且僅當它在第(i-1)層的對應父節(jié)點k-項集是頻繁的(P165,圖6-15)(computer,printer)((laptopcomputer,colorprinter),(desktopcomputer,b/wprinter)…)多層關聯(lián)——搜索策略(2)搜索策略比較逐層獨立策略條件松,可能導致底層考察大量非頻繁項層交叉k項集過濾策略限制太強,僅允許考察頻繁k-項集的子女層交叉單項過濾策略是上述兩者的折中,但仍可能丟失低層頻繁項(圖6-14)受控的層交叉單項過濾策略層交叉單項過濾策略的改進版本設置一個層傳遞臨界值,用于向較低層傳遞相對頻繁的項。即如果滿足層傳遞臨界值,則允許考察不滿足最小支持度臨界值的項的子女用戶對進一步控制多概念層上的挖掘過程有了更多的靈活性,同時減少無意義關聯(lián)的考察和產生min_sup=12%level_passage_support=8%min_sup=3%檢查冗余的多層關聯(lián)規(guī)則挖掘多層關聯(lián)規(guī)則時,由于項間的“祖先”關系,有些發(fā)現(xiàn)的規(guī)則將是冗余的例如:desktopcomputer=>b/wprinter[sup=8%,con=70%] (1)IBMdesktopcomputer=>b/wprinter[sup=2%,con=72%](2)上例中,我們說第一個規(guī)則是第二個規(guī)則的“祖先”如果規(guī)則(2)中的項用它在概念分層中的“祖先”代替,能得到(1),而且(1)的支持度和置信度都接近“期望”值,則(1)是冗余的。多維關聯(lián)規(guī)則——概念單維關聯(lián)規(guī)則:buys(X,“milk”)=buys(X,“bread”)多維關聯(lián)規(guī)則:涉及兩個或多個維或謂詞的關聯(lián)規(guī)則維間關聯(lián)規(guī)則:不包含重復的謂詞age(X,”19-25”)∧occupation(X,“student”)=>buys(X,“coke”)混合維關聯(lián)規(guī)則:包含某些謂詞的多次出現(xiàn)age(X,”19-25”)∧buys(X,“popcorn”)=>buys(X,“coke”)在多維關聯(lián)規(guī)則挖掘中,我們搜索的不是頻繁項集,而是頻繁謂詞集。k-謂詞集是包含k個合取謂詞的集合。例如:{age,occupation,buys}是一個3-謂詞集挖掘多維關聯(lián)規(guī)則的技術數(shù)據屬性可以分為分類屬性和量化屬性分類屬性具有有限個不同值,值之間無序量化屬性數(shù)值類型的值,并且值之間有一個隱含的序挖掘多維關聯(lián)規(guī)則的技術可以根據量化屬性的處理分為三種基本方法:1.量化屬性的靜態(tài)離散化使用預定義的概念分層對量化屬性進行靜態(tài)地離散化2.量化關聯(lián)規(guī)則根據數(shù)據的分布,將量化屬性離散化到“箱”3.基于距離的關聯(lián)規(guī)則考慮數(shù)據點之間的距離,動態(tài)地離散化量化屬性多維關聯(lián)規(guī)則挖掘——使用量化屬性的靜態(tài)離散化量化屬性使用預定義的概念分層,在挖掘前進行離散化數(shù)值屬性的值用區(qū)間代替如果任務相關數(shù)據存在關系數(shù)據庫中,則找出所有頻繁的k-謂詞集將需要k或k+1次表掃描數(shù)據立方體技術非常適合挖掘多維關聯(lián)規(guī)則n-維方體的單元用于存放對應n-謂詞集的計數(shù)或支持度,0-D方體用于存放任務相關數(shù)據的事務總數(shù)如果包含感興趣的維的數(shù)據立方體已經存在并物化,挖掘將會很快,同時可以利用Apriori性質:頻繁謂詞集的每個子集也必須是頻繁的(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)挖掘量化關聯(lián)規(guī)則(1)量化關聯(lián)規(guī)則中,數(shù)值屬性將根據某種挖掘標準,進行動態(tài)的離散化例如:最大化挖掘規(guī)則的置信度和緊湊性為了簡化量化關聯(lián)規(guī)則挖掘的討論,我們將聚焦于類似以下形式的2-維量化關聯(lián)規(guī)則:Aquan1
Aquan2Acat(兩個量化屬性和一個分類屬性間的關聯(lián))例如:age(X,”30-39”)income(X,”42K-48K
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 六年級第一學期教學計劃范文合集三篇
- 九年級化學教學計劃范文錦集7篇
- 銷售部年度工作計劃
- 師德師風的教師演講稿模板5篇
- 人壽保險公司實習報告合集六篇
- 關于年會策劃方案范文合集6篇
- 大學生頂崗實習周記錦集六篇
- 政府績效評估 課件 蔡立輝 第6-10章 政府績效評估的結果應用與改進 -政府績效評估在當代中國的推進
- 2010年高考一輪復習教案:必修1 第四章 非金屬及其化合物 全程教學案
- 2025年農林牧漁專用儀器儀表項目發(fā)展計劃
- 年高考新課標I卷語文試題講評課件
- 《三 采用合理的論證方法》教學設計統(tǒng)編版高中語文選擇性必修上冊
- 2024-2025學年語文二年級上冊 部編版期末測試卷 (含答案)
- 2024-2025學年八年級上冊物理 第五章 透鏡以及其應用 測試卷(含答案)
- 《自理理論orem》課件
- 職業(yè)技術學院無人機應用技術專業(yè)人才培養(yǎng)方案
- 神經病學第九版腦梗死
- 2024年浙江省杭州市下城區(qū)教育局所屬事業(yè)單位招聘學科拔尖人才10人歷年管理單位遴選500模擬題附帶答案詳解
- 研發(fā)項目管理培訓課件講解
- 2024-2030年中國膏劑(膏方)行業(yè)競爭狀況及營銷前景預測報告版
- 2023虛擬電廠新型電力系統(tǒng)
評論
0/150
提交評論