數(shù)據(jù)挖掘第六章

1、1 1Data Mining: Concepts and Techniques (3rd ed.) Chapter 6 挖掘頻繁模式挖掘頻繁模式, ,關(guān)聯(lián)和相關(guān)性：基本概念和方法關(guān)聯(lián)和相關(guān)性：基本概念和方法什么是頻繁模式分析？什么是頻繁模式分析？n頻繁模式(frequent pattern)是頻繁地出現(xiàn)在數(shù)據(jù)集中模式(如項集,子序列或子結(jié)構(gòu))。n頻繁項集是頻繁出現(xiàn)在交易數(shù)據(jù)集中的商品（如牛奶和面包，啤酒和尿布）的集合。n頻繁的序列模式是（PC-數(shù)碼相機-內(nèi)存卡）這種頻繁出現(xiàn)在購物的歷史數(shù)據(jù)庫中的序列。n頻繁的結(jié)構(gòu)模式是頻繁出現(xiàn)的子結(jié)構(gòu)。2什么是頻繁模式分析？什么是頻繁模式分析？n動機：尋找數(shù)據(jù)

2、的內(nèi)在規(guī)律n經(jīng)常購買的是什么產(chǎn)品都在一起 牛奶和面包，啤酒和尿布？n什么是購買一臺PC后，后續(xù)的購買?n應(yīng)用n挖掘數(shù)據(jù)之間的關(guān)聯(lián)、相關(guān)性、和其他有趣的聯(lián)系，及購物籃分析, 交差營銷, 價目表設(shè)置,銷售活動分析, 網(wǎng)絡(luò)點擊量分析。36.1 基本概念基本概念n頻繁模式(關(guān)聯(lián)規(guī)則)挖掘：n找出給定數(shù)據(jù)集中反復出現(xiàn)的聯(lián)系n從事務(wù)數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫和其他信息存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、項與項之間的關(guān)聯(lián)或相關(guān)性。n應(yīng)用：n購物籃分析：分類設(shè)計、捆綁銷售和虧本銷售分析6.1.1 購物籃分析：一個誘發(fā)例子購物籃分析：一個誘發(fā)例子 采用關(guān)聯(lián)模型比較典型的案例是“尿布與啤酒”的故事。 在

3、美國，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個規(guī)律，在購買嬰兒尿布的年輕父親們中，有30%40%的人同時要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。同樣的，我們還可以根據(jù)關(guān)聯(lián)規(guī)則在商品銷售方面做各種促銷活動。購物籃分析購物籃分析n利用頻繁模式可以制定營銷計劃來提高銷售量，具體如下： 1、對商店的顧客事務(wù)零售數(shù)據(jù)進行分析 2、根據(jù)得到的有趣的關(guān)聯(lián)設(shè)計營銷策略： a、經(jīng)常同時購買的商品擺放在一起，一遍刺激這些商品 同時銷售 b、將同時購買的商品放在商店的兩端，可以誘發(fā)顧客購 買沿途看到的商品（可以通過降價吸引顧客）購物籃分析購物籃分析n

4、如果問題的全域是商店中所有商品的集合，則對每種商品都可以用一個布爾量來表示該商品是否被顧客購買，則每個購物籃都可以用一個布爾向量表示（如形式0001001100）；而通過分析布爾向量則可以得到商品被頻繁關(guān)聯(lián)或被同時購買的模式，這些模式就可以用關(guān)聯(lián)規(guī)則表示n關(guān)聯(lián)規(guī)則的兩個興趣度度量computer=financial_management_softwaresupport=2%.confidence=60%n支持度：有用性；指兩者被同時購買的概率n置信度：確定性；指購買A的顧客也購買B產(chǎn)品的概率6.1.2 頻繁項集頻繁項集,閉項集和關(guān)聯(lián)規(guī)則閉項集和關(guān)聯(lián)規(guī)則n給定：給定：n項的集合：項的集合：I=

5、i1,i2,.,inn每個事務(wù)每個事務(wù)T 則是項的集合，使得則是項的集合，使得 ；每個事務(wù)由事務(wù)標；每個事務(wù)由事務(wù)標識符識符TID 標識；標識；n任務(wù)相關(guān)數(shù)據(jù)任務(wù)相關(guān)數(shù)據(jù)D 是數(shù)據(jù)庫事務(wù)的集合。是數(shù)據(jù)庫事務(wù)的集合。nA,B為兩個項集，事務(wù)為兩個項集，事務(wù)T包含包含A，當且僅當當且僅當 ；n則關(guān)聯(lián)規(guī)則是如下蘊涵式：則關(guān)聯(lián)規(guī)則是如下蘊涵式：n其中其中 并且并且 ，規(guī)則，規(guī)則 在事務(wù)在事務(wù)集集D 中成立，并且具有支持度中成立，并且具有支持度s 和置信度和置信度cIT TA , csBA IBIA , BABA 規(guī)則度量：支持度和置信度規(guī)則度量：支持度和置信度n對于A-B支持度支持度：P(A B)，既

6、有A又有B的概率置信度置信度：P(B|A)，在A發(fā)生的事件中同時發(fā)生B的概率p(AB)/P(A)n例如購物籃分析：牛奶面包例子：支持度：3%，置信度：40%支持度3%：意味著3%顧客同時購買牛奶和面包置信度40%：意味著購買牛奶的顧客40%也購買面包規(guī)則度量：支持度和置信度規(guī)則度量：支持度和置信度n對所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則n支持度s是指事務(wù)集D中包含 的百分比n置信度c是指D中包含A的事務(wù)同時也包含B的百分比n假設(shè)最小支持度為50%，最小置信度為50%，則有如下關(guān)聯(lián)規(guī)則nA C (50%, 66.6%)nC A (50%, 100%)Customerbuys diaperCust

7、omerbuys bothCustomerbuys beerBA)( )(supBAPBAport)(/ )()|( )( APBAPABPBAconfidence標識符標識符大型數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘過程大型數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘過程n基本概念nk k項集項集：包含k個項的集合n牛奶，面包，黃油是個3項集n項集的頻率項集的頻率 是指包含項集的事務(wù)數(shù)n如果項集的頻率大于（最小支持度D中的事務(wù)總數(shù)），則稱該項集為頻繁項集頻繁項集n大型數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘包含兩個過程：n找出所有頻繁項集n這些項集的出現(xiàn)次數(shù)至少與預定的最小支持計數(shù)min_sup一樣，大部分的計算都集中在這一步n由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則n

8、即滿足最小支持度和最小置信度的規(guī)則6.2 有效的和可伸縮的頻繁項集挖掘方法n最簡單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。n對規(guī)則AC，其支持度=50%n置信度:%6 .66)(sup/ )(sup)(/ )()|( )( AportCAportAPCAPACPCAconfidenceTransactionID ItemsBought2000A,B,C1000A,C4000A,D5000B,E,FFrequentItemset SupportA75%B50%C50%A,C50%最小支持度 50%最小置信度 50%)( )(supCAPCAport6.2Apriori算法算法n頻繁項集

9、兩個定理： 1）頻繁項子集定理：頻繁項集的子集都是頻繁 項集，而非頻繁項的超集都是非頻繁項集。 2）頻繁項集的合并/連接定理：由k-1項集，向k項集進行合并。當兩個k-1項集，擁有k-2個相同元素時，才能合并成k項集。n如果事件A中包含k個元素，那么稱這個事件A為k項集事件A滿足最小支持度閾值的事件稱為頻繁k項集。n同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強規(guī)則6.2.1 Apriori算法算法nApriori算法利用頻繁項集性質(zhì)的先驗知識（prior knowledge），通過逐層搜索的迭代方法，即將k-項集用于探察(k+1)-項集，來窮盡數(shù)據(jù)集中的所有頻繁項集。n先找到頻繁1-項集

10、集合L1,然后用L1找到頻繁2-項集集合L2，接著用L2找L3，直到找不到頻繁k-項集，找每個Lk需要一次數(shù)據(jù)庫掃描。nApriori性質(zhì)：根據(jù)項集I不滿足最小支持度閾值min_sup,則I不是頻繁的，即P(I)minn_sup 頻繁項集的所有非空子集也必須是頻繁的。（頻繁項集的所有非空子集也必須是頻繁的。（ 將項將項A添加到項集添加到項集I中，模式中，模式IA不可能比不可能比I更頻繁的出現(xiàn)）更頻繁的出現(xiàn)）nApriori算法是反單調(diào)的，即一個集合如果不能通過測試，則該集合的所有超集也不能通過相同的測試。Apriori算法步驟算法步驟nApriori算法由連接連接和剪枝剪枝兩個步驟組成。n連接

11、：連接：為了找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合，該候選候選k項集項集記為Ck。nLk-1中的兩個元素L1和L2可以執(zhí)行連接操作 的條件是nCk是Lk的超集，即它的成員可能不是頻繁的，但是所有頻繁的k-項集都在Ck中（為什么？）。因此可以通過掃描數(shù)據(jù)庫，通過計算每個k-項集的支持度來得到Lk 。n為了減少計算量，可以使用Apriori性質(zhì)，即如果一個k-項集的(k-1)-子集不在Lk-1中，則該候選不可能是頻繁的，可以直接從Ck刪除。)1 1()22(.)22()1 1 (21212121klklklklllll21ll Apriori算法步驟算法步驟n首先，找出頻繁“1項集”

12、的集合，該集合記作L1。L1用于找頻繁“2項集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K項集”。找每個Lk都需要一次數(shù)據(jù)庫掃描。n核心思想是：連接步和剪枝步。連接步是自連接，原則是保證前k-2項相同，并按照字典順序連接。剪枝步，是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某個候選的非空子集不是頻繁的，那么該候選肯定不是頻繁的，從而可以將其從CK中刪除。Apriori算法步驟算法步驟n簡單的講，1、發(fā)現(xiàn)頻繁項集，過程為（1）掃描（2）計數(shù)（3）比較（4）產(chǎn)生頻繁項集（5）連接、剪枝，產(chǎn)生候選項集，重復步驟（1）（5）直到不能發(fā)現(xiàn)更大的頻集。n2、產(chǎn)生關(guān)聯(lián)規(guī)則，過程為:

13、根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對于每個頻繁項集L，產(chǎn)生L的所有非空子集；（2）對于L的每個非空子集S，如果P（L）/P（S）min_conf則輸出規(guī)則“SL-S”注：L-S表示在項集L中除去S子集的項集Apriori算法例6.3Apriori算法示例Database TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA,BA,CA,EB,CB,EC,EItemsetsupA,B1

14、A,C2A,E1B,C2B,E3C,E2ItemsetsupA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E2使用Apiori性質(zhì)由L2產(chǎn)生C3n1 連接：連接：nC3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,En2使用使用Apriori性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對性質(zhì)剪枝：頻繁項集的所有子集必須是頻繁的，對候選項候選項C3，我們可以刪除其子集為非頻繁的選項：，我們可以刪除其子集為非頻繁的選項：nA,B,C的的2項子集是項子集是A,B,A,C,B,C，其中，其中A,B不是

15、不是L2的的元素，所以刪除這個選項；元素，所以刪除這個選項；nA,C,E的的2項子集是項子集是A,C,A,E,C,E，其中，其中A,E 不是不是L2的的元素，所以刪除這個選項；元素，所以刪除這個選項；nB,C,E的的2項子集是項子集是B,C,B,E,C,E，它的所有，它的所有2項子集項子集都是都是L2的元素，因此保留這個選項。的元素，因此保留這個選項。n3這樣，剪枝后得到這樣，剪枝后得到C3=B,C,E圖圖6-3 :由由L2產(chǎn)生和剪枝候選產(chǎn)生和剪枝候選3項集的集合項集的集合C3Pseudo-code:Ck:CandidateitemsetofsizekLk:frequentitemsetofs

16、izek L1=frequentitems;for (k=1;Lk!=;k+)do beginCk+1=candidatesgeneratedfromLk;for eachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_support endreturnkLk;圖圖6-4 Apriori算法算法6.2.2由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則n同時滿足最小支持度和最小置信度的才是強關(guān)聯(lián)規(guī)則，從頻繁項集產(chǎn)生的規(guī)則都滿足支

17、持度要求，而其置信度則可由一下公式計算：n每個關(guān)聯(lián)規(guī)則可由如下過程產(chǎn)生：n對于每個頻繁項集L，產(chǎn)生L的所有非空子集；n對于每個非空子集s，如果 則輸出規(guī)則 “ ”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls例例 :6.4 p164 6.2.3 提高提高Apriori算法的效率算法的效率(1)nApriori算法主要的挑戰(zhàn)算法主要的挑戰(zhàn)n要對數(shù)據(jù)進行多次掃描；n會產(chǎn)生大量的候選項集；n對候選項集的支持度計算非常繁瑣；n解決思路解決思路n減少對數(shù)據(jù)

18、的掃描次數(shù)；n縮小產(chǎn)生的候選項集；n改進對候選項集的支持度計算方法n方法方法1：基于：基于hash表的項集計數(shù)表的項集計數(shù)n將每個項集通過相應(yīng)的hash函數(shù)映射到hash表中的不同的桶中，這樣可以通過將桶中的項集技術(shù)跟最小支持計數(shù)相比較先淘汰一部分項集。提高提高Apriori算法的效率算法的效率(2)n方法方法2：事務(wù)壓縮：事務(wù)壓縮（壓縮進一步迭代的事務(wù)數(shù)）n不包含任何k-項集的事務(wù)不可能包含任何(k+1)-項集，這種事務(wù)在下一步的計算中可以加上標記或刪除。n方法方法3：劃分：劃分n挖掘頻繁項集只需要兩次數(shù)據(jù)掃描nD中的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。n第一次掃描：將數(shù)據(jù)

19、劃分為多個部分并找到局部頻繁項集n第二次掃描：評估每個候選項集的實際支持度，以確定全局頻繁項集提高Apriori算法的有效性(3)n方法方法4：選樣：選樣（在給定數(shù)據(jù)的一個子集挖掘）n基本思想：選擇原始數(shù)據(jù)的一個樣本，在這個樣本上用Apriori算法挖掘頻繁模式n通過犧牲精確度來減少算法開銷，為了提高效率，樣本大小應(yīng)該以可以放在內(nèi)存中為宜，可以適當降低最小支持度來減少遺漏的頻繁模式n可以通過一次全局掃描來驗證從樣本中發(fā)現(xiàn)的模式n可以通過第二此全局掃描來找到遺漏的模式n方法方法5：動態(tài)項集計數(shù)：動態(tài)項集計數(shù)n在掃描的不同點添加候選項集，這樣，如果一個候選項集已經(jīng)滿足最少支持度，則可以直接將它添加

20、到頻繁項集，而不必在這次掃描的以后對比中繼續(xù)計算6.2.4挖掘頻繁模式增長的方法挖掘頻繁模式增長的方法nApriori的候選-產(chǎn)生機制顯著壓縮了候選項集的大小，并導致的很好的性能，但是也有一些缺點，比如說當數(shù)據(jù)量很大的時候，候選集將會非常的大(劃分方法可以避免這一點)；并且需要多次掃描數(shù)據(jù)庫(劃分應(yīng)該是一個非常好的方法)。所以一種稱作“頻繁模式增長”或簡稱FP增長(FP Growth)的方法應(yīng)運而生了。它采用分治策略，將提供頻繁項的數(shù)據(jù)庫壓縮到一顆頻繁模式樹中，但仍保留項集的相關(guān)信息。然后將壓縮后的數(shù)據(jù)庫劃分成一組條一組條件數(shù)據(jù)庫件數(shù)據(jù)庫 ，每個關(guān)聯(lián)一個頻繁項或模式段，并分別挖掘每個條件數(shù)據(jù)庫

21、。6.2.4挖掘頻繁模式增長（挖掘頻繁模式增長（FP-增長）的方法增長）的方法特點：不產(chǎn)生侯選頻繁項集過程：1、產(chǎn)生頻繁1-項集L，并按照其支持度記數(shù)降序排列2、構(gòu)造FP-樹：掃描數(shù)據(jù)庫中的每個事務(wù)，對每個事務(wù)按照L中的次序構(gòu)造樹的分支3、對FP-樹進行挖掘：從L的底端開始，依次向上進行。 條件模式基：有路徑：,則,是I5的條件模式基。 條件FP-樹： 構(gòu)成的分支是I5的條件FP-樹6.2.5使用垂直數(shù)據(jù)格式挖掘頻繁項集使用垂直數(shù)據(jù)格式挖掘頻繁項集Apriori算法和FP-growth算法都是從TID項集格式（即TID:itemset）的事務(wù)集中挖掘頻繁模式，其中TID是事務(wù)標識符，這種數(shù)據(jù)格

22、式稱為水平數(shù)據(jù)格式。或者，數(shù)據(jù)可以采用項-TID集格式（即item：TID_set）表示，其中item是項的名稱，而TID_set是包含item的事務(wù)的標識符的集合。這種格式稱為垂直數(shù)據(jù)格式。6.2.5使用垂直數(shù)據(jù)格式挖掘頻繁項集使用垂直數(shù)據(jù)格式挖掘頻繁項集例6.6使用垂直格式挖掘頻繁項集 取每對頻繁項的取每對頻繁項的TID集的交集的交 一個給定的一個給定的3項集是候選項集是候選3項集，項集， 僅當它的每一個僅當它的每一個2項集子集都是頻繁的項集子集都是頻繁的 6.3 6.3 哪些模式是有趣的：模式評估方法哪些模式是有趣的：模式評估方法 大部分關(guān)聯(lián)規(guī)則挖掘算法都使用支持度-置信度框架，盡管最小

23、支持度和置信度閾值有助于排出大量的無趣規(guī)則，但仍會產(chǎn)生一些用戶不感興趣的規(guī)則，當使用低支持度閾值挖掘或挖掘長模式時，情況特別嚴重。這是關(guān)聯(lián)規(guī)則挖掘成功應(yīng)用的主要瓶頸之一。6.3.1 6.3.1 強規(guī)則不一定是有趣的強規(guī)則不一定是有趣的 強規(guī)則為何有可能是無趣的或是誤導呢？ 因為規(guī)則是否有趣可以主觀或客觀地評價。最終，只有用戶能夠評價一個給定的規(guī)則是否是有趣的，并且這種判斷是主觀的，可能因用戶而異，然后根據(jù)數(shù)據(jù)“背后”的統(tǒng)計量，客觀興趣度度量可以用來清除無趣的規(guī)則，而不向用戶提供。無趣規(guī)則。例例 6.7 6.7 一個誤導的一個誤導的“強強”關(guān)聯(lián)規(guī)則關(guān)聯(lián)規(guī)則 假設(shè)我們對分析設(shè)計購買計算機游戲和錄像

24、的AllElectronics的事務(wù)感興趣。設(shè)game表示包含計算機游戲的事務(wù)，video表示包含錄像的事務(wù)。在所分析的10000個事務(wù)中，數(shù)據(jù)顯示： 6000個顧客事務(wù)包含計算機游戲， 7500個事務(wù)包含錄像， 4000個事務(wù)同時包含計算機游戲和錄像。 假設(shè)發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘程序在該數(shù)據(jù)上運行，使用最小支持率30%，最小置信率60%。將發(fā)現(xiàn)下面的關(guān)聯(lián)規(guī)則：上述規(guī)則是強關(guān)聯(lián)規(guī)則，因為它的支持率為4000/10000=40%30%(最小支持率），置信度為4000/6000=66%60%（最小置信率）。然而這個規(guī)則是誤導，因為購買錄像的概率75%66%,而計算機游戲和錄像是負相關(guān)。 6.3.2

25、 6.3.2 從關(guān)聯(lián)分析到相關(guān)分析從關(guān)聯(lián)分析到相關(guān)分析 由于支持度和置信度度量不足以過濾掉無趣的關(guān)聯(lián)規(guī)則，因此可以由于支持度和置信度度量不足以過濾掉無趣的關(guān)聯(lián)規(guī)則，因此可以使用使用相關(guān)性度量相關(guān)性度量來擴充關(guān)聯(lián)規(guī)則的支持度來擴充關(guān)聯(lián)規(guī)則的支持度-置信度框架。產(chǎn)生如下相關(guān)置信度框架。產(chǎn)生如下相關(guān)規(guī)則規(guī)則相關(guān)規(guī)則不僅用到了支持度和置信度度量，而且還用項集相關(guān)規(guī)則不僅用到了支持度和置信度度量，而且還用項集A和和B之間之間的相關(guān)性度量。的相關(guān)性度量。 提升度（提升度（lift）是一種簡單的相關(guān)性度量。）是一種簡單的相關(guān)性度量。A 和和B的提升度可以通過下的提升度可以通過下式得到式得到 lift(A,B

26、)1,A和和B是正相關(guān)。是正相關(guān)。 lift(A,B)=1,A和和B是獨立的。是獨立的。 例例6.8 6.8 使用提升度的相關(guān)分析使用提升度的相關(guān)分析 設(shè)設(shè) 表示不包含計算機游戲的事務(wù)，表示不包含計算機游戲的事務(wù)， 表示不包含錄像的事務(wù)。表示不包含錄像的事務(wù)。它們之間的相依表如下它們之間的相依表如下:例例6.9 6.9 使用使用 進行相關(guān)分析進行相關(guān)分析 為了使用為了使用 分析計算相關(guān)性，需要相依每個位置上的觀測值和期望分析計算相關(guān)性，需要相依每個位置上的觀測值和期望值（顯示在括號內(nèi)），如表值（顯示在括號內(nèi)），如表6.7所示，所示，由該表計算由該表計算 值如下：值如下：由于由于 的值大于的值大

27、于1，且位置（，且位置（game，video）上的觀測值等于）上的觀測值等于4000，小，小于期望值于期望值4500，因此購買游戲與購買錄像是負相關(guān)。，因此購買游戲與購買錄像是負相關(guān)。6.3.3 6.3.3 模式評估度量比較模式評估度量比較 本節(jié)介紹本節(jié)介紹4種模式評估度量：全置信度、最大置信度、種模式評估度量：全置信度、最大置信度、Kulczynski和和余弦。然后比較它們的有效性，并與提升度和余弦。然后比較它們的有效性，并與提升度和 進行比較進行比較。 給定兩個項集給定兩個項集A和和B，A和和B的的全置信度全置信度定義為：定義為：其中，其中，maxsup(A),sup(B)是是A和和B的最

28、大支持度。因此，的最大支持度。因此，all-conf（A,B)又稱為兩個與又稱為兩個與A和和B相關(guān)的關(guān)聯(lián)規(guī)則相關(guān)的關(guān)聯(lián)規(guī)則 的最小置的最小置信度。信度。 給定兩個項集給定兩個項集A和和B，A和和B的的最大置信度最大置信度（max_confidence）定義）定義為：為：max_conf是兩個規(guī)則是兩個規(guī)則 的最大置信度。的最大置信度。 給定兩個項集給定兩個項集A和和B，A和和B的的Kulczynski度量定義為：度量定義為：該度量是波蘭數(shù)學家該度量是波蘭數(shù)學家S.Kulczynski于于1927年提出的。它可以看做兩個置信度年提出的。它可以看做兩個置信度的平均值。更確切地說，它是兩個條件概率的

29、平均值。的平均值。更確切地說，它是兩個條件概率的平均值。 給定兩個項集給定兩個項集A和和B，A和和B的余弦度量定義為的余弦度量定義為:余弦度量可以看做調(diào)和提升度度量：兩個公式類似，不同之處在于余弦對余弦度量可以看做調(diào)和提升度度量：兩個公式類似，不同之處在于余弦對A和和B的概率的乘積取平方根。然而，這是一個重要區(qū)別，因為通過取平方根，余的概率的乘積取平方根。然而，這是一個重要區(qū)別，因為通過取平方根，余弦值僅受弦值僅受A、B和和AUB的支持度的影響，而不受事務(wù)總個數(shù)的影響。的支持度的影響，而不受事務(wù)總個數(shù)的影響。 上面介紹的上面介紹的4種度量都具有如下性質(zhì)：度量值僅受種度量都具有如下性質(zhì)：度量值僅

30、受A、B和和AUB的支持度的的支持度的影響，更準確地說，僅受條件概率影響，更準確地說，僅受條件概率P(AlB）和）和P(BlA）的影響，而不受事務(wù)總）的影響，而不受事務(wù)總個數(shù)的影響。另一個共同的性質(zhì)是，每個度量值都遍取個數(shù)的影響。另一個共同的性質(zhì)是，每個度量值都遍取01，并且值越大，并且值越大，A和和B的聯(lián)系越緊密。的聯(lián)系越緊密。 例例6.10 6.10 在典型的數(shù)據(jù)集上比較在典型的數(shù)據(jù)集上比較6 6種模式評估度量種模式評估度量 牛奶和咖啡兩種商品購買之間的關(guān)系可以通過把它們的牛奶和咖啡兩種商品購買之間的關(guān)系可以通過把它們的購買歷史記錄匯總在表購買歷史記錄匯總在表6.86.8的的2 2* *2

31、 2相依表中來考察，其中像相依表中來考察，其中像mcmc這樣的表目表示包含牛奶和咖啡的事務(wù)個數(shù)。這樣的表目表示包含牛奶和咖啡的事務(wù)個數(shù)。 從該表可以看出，從該表可以看出，m m和和c c在數(shù)據(jù)集在數(shù)據(jù)集D1D1和和D2D2中是正關(guān)聯(lián)的，在中是正關(guān)聯(lián)的，在D3D3中是負關(guān)聯(lián)的，中是負關(guān)聯(lián)的，而在而在D4D4中是中性的。對于中是中性的。對于D1D1和和D2D2，m m和和c c是正關(guān)聯(lián)的，因為是正關(guān)聯(lián)的，因為mcmc（1000010000）顯著）顯著大于大于 直觀地，對于購買牛奶的人直觀地，對于購買牛奶的人（m=10000+1000=11000m=10000+1000=11000）而言，他們非常可

32、能也購買咖啡）而言，他們非常可能也購買咖啡（mc/m=10/11=91%mc/m=10/11=91%），反之亦然。），反之亦然。零事務(wù)是不包含任何考察項集的事務(wù)。零事務(wù)是不包含任何考察項集的事務(wù)。例例6.11 6.11 比較模式評估的零不變度量比較模式評估的零不變度量 考察表考察表6.9的數(shù)據(jù)集的數(shù)據(jù)集D5和和D6，其中兩個事件，其中兩個事件m和和c具有不平衡的條件概率。具有不平衡的條件概率。即即mc與與c的比大于的比大于0.9.這意味，知道這意味，知道c出現(xiàn)將強烈暗示出現(xiàn)將強烈暗示m也出現(xiàn)。也出現(xiàn)。Mc與與m的的比小于比小于0.1，表明，表明m蘊含蘊含c很可能不出現(xiàn)。全置信度和余弦度量把兩種

33、情況很可能不出現(xiàn)。全置信度和余弦度量把兩種情況都看做負關(guān)聯(lián)的，而都看做負關(guān)聯(lián)的，而Kluc度量把兩者都視為中性的。最大置信度度量聲稱度量把兩者都視為中性的。最大置信度度量聲稱這些情況都是強正關(guān)聯(lián)的。這些情況都是強正關(guān)聯(lián)的。 總之，僅使用支持度和置信度度量來挖掘關(guān)聯(lián)可能產(chǎn)生大量規(guī)則，其中總之，僅使用支持度和置信度度量來挖掘關(guān)聯(lián)可能產(chǎn)生大量規(guī)則，其中大部分規(guī)則用戶是不感興趣的?；蛘撸覀兛梢杂媚Ｊ脚d趣度度量來擴展大部分規(guī)則用戶是不感興趣的。或者，我們可以用模式興趣度度量來擴展支持度支持度-置信度框架，有助于把挖掘聚焦到具有強模式聯(lián)系的規(guī)則。附加的置信度框架，有助于把挖掘聚焦到具有強模式聯(lián)系的規(guī)則。

34、附加的度量顯著地減少了所產(chǎn)生規(guī)則的數(shù)量，并且導致更有意義規(guī)則的發(fā)現(xiàn)。除度量顯著地減少了所產(chǎn)生規(guī)則的數(shù)量，并且導致更有意義規(guī)則的發(fā)現(xiàn)。除了本書介紹的相關(guān)性度量外，文獻中還研究了許多其他興趣的度量。不幸了本書介紹的相關(guān)性度量外，文獻中還研究了許多其他興趣的度量。不幸的是，大部分度量都不具有零不變性，由于大型數(shù)據(jù)集常常具有許多零事的是，大部分度量都不具有零不變性，由于大型數(shù)據(jù)集常常具有許多零事務(wù)，因此在進行相關(guān)分析選擇合適的興趣度量時，考慮零不變性是重要的。務(wù)，因此在進行相關(guān)分析選擇合適的興趣度量時，考慮零不變性是重要的。這里研究的這里研究的4個零不變的度量（即，全置信度、最大置信度、個零不變的度量

35、（即，全置信度、最大置信度、Kulczynski和余弦）中，我們推薦和余弦）中，我們推薦Kluc與不平衡比配合使用。與不平衡比配合使用。6.4 6.4 小結(jié)小結(jié)l 大量數(shù)據(jù)中的頻繁模式、關(guān)聯(lián)和相關(guān)關(guān)系的發(fā)現(xiàn)在選擇性銷售、決策大量數(shù)據(jù)中的頻繁模式、關(guān)聯(lián)和相關(guān)關(guān)系的發(fā)現(xiàn)在選擇性銷售、決策分析和商務(wù)管理方面是有用的。一個流行的應(yīng)用領(lǐng)域是購物籃分析，通分析和商務(wù)管理方面是有用的。一個流行的應(yīng)用領(lǐng)域是購物籃分析，通過搜索經(jīng)常在一起購買的商品的集合，研究顧客的購買習慣。過搜索經(jīng)常在一起購買的商品的集合，研究顧客的購買習慣。l 關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項集（項的集合，如關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項集（項的集合

36、，如A A和和B B，滿足最小支持度，滿足最小支持度閾值，或任務(wù)相關(guān)組的百分比），然后，由它們產(chǎn)生形如閾值，或任務(wù)相關(guān)組的百分比），然后，由它們產(chǎn)生形如A BA B的強的強關(guān)聯(lián)規(guī)則。這些歸則還滿足最小置信度閾值。進一步分析關(guān)聯(lián)，發(fā)現(xiàn)項關(guān)聯(lián)規(guī)則。這些歸則還滿足最小置信度閾值。進一步分析關(guān)聯(lián)，發(fā)現(xiàn)項集集A A和和B B之間具有統(tǒng)計相關(guān)性的相關(guān)規(guī)則。之間具有統(tǒng)計相關(guān)性的相關(guān)規(guī)則。l 對于頻繁項集挖掘，已經(jīng)開發(fā)了許多有效的、可伸縮的算法，由它們可對于頻繁項集挖掘，已經(jīng)開發(fā)了許多有效的、可伸縮的算法，由它們可以導出關(guān)聯(lián)和相關(guān)規(guī)則，這些算法可分為三類以導出關(guān)聯(lián)和相關(guān)規(guī)則，這些算法可分為三類（1 1）類）類AprioriApriori算法；（算法；（2 2）基于頻繁模式增長的算法，如基于頻繁模式增長的算法，如FP-growthFP-growth；（；（3 3）使用垂直數(shù)據(jù)格式的算）使