數(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ù)集中模式(如項(xiàng)集,子序列或子結(jié)構(gòu))。n頻繁項(xiàng)集是頻繁出現(xiàn)在交易數(shù)據(jù)集中的商品（如牛奶和面包，啤酒和尿布）的集合。n頻繁的序列模式是（PC-數(shù)碼相機(jī)-內(nèi)存卡）這種頻繁出現(xiàn)在購(gòu)物的歷史數(shù)據(jù)庫(kù)中的序列。n頻繁的結(jié)構(gòu)模式是頻繁出現(xiàn)的子結(jié)構(gòu)。2什么是頻繁模式分析？什么是頻繁模式分析？n動(dòng)機(jī)：尋找數(shù)據(jù)

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

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

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

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

6、有A又有B的概率置信度置信度：P(B|A)，在A發(fā)生的事件中同時(shí)發(fā)生B的概率p(AB)/P(A)n例如購(gòu)物籃分析：牛奶面包例子：支持度：3%，置信度：40%支持度3%：意味著3%顧客同時(shí)購(gòu)買牛奶和面包置信度40%：意味著購(gòu)買牛奶的顧客40%也購(gòu)買面包規(guī)則度量：支持度和置信度規(guī)則度量：支持度和置信度n對(duì)所有滿足最小支持度和置信度的關(guān)聯(lián)規(guī)則n支持度s是指事務(wù)集D中包含 的百分比n置信度c是指D中包含A的事務(wù)同時(shí)也包含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標(biāo)識(shí)符標(biāo)識(shí)符大型數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘過(guò)程大型數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘過(guò)程n基本概念nk k項(xiàng)集項(xiàng)集：包含k個(gè)項(xiàng)的集合n牛奶，面包，黃油是個(gè)3項(xiàng)集n項(xiàng)集的頻率項(xiàng)集的頻率 是指包含項(xiàng)集的事務(wù)數(shù)n如果項(xiàng)集的頻率大于（最小支持度D中的事務(wù)總數(shù)），則稱該項(xiàng)集為頻繁項(xiàng)集頻繁項(xiàng)集n大型數(shù)據(jù)庫(kù)中的關(guān)聯(lián)規(guī)則挖掘包含兩個(gè)過(guò)程：n找出所有頻繁項(xiàng)集n這些項(xiàng)集的出現(xiàn)次數(shù)至少與預(yù)定的最小支持計(jì)數(shù)min_sup一樣，大部分的計(jì)算都集中在這一步n由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則n

8、即滿足最小支持度和最小置信度的規(guī)則6.2 有效的和可伸縮的頻繁項(xiàng)集挖掘方法n最簡(jiǎn)單的關(guān)聯(lián)規(guī)則挖掘，即單維、單層、布爾關(guān)聯(lián)規(guī)則的挖掘。n對(duì)規(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頻繁項(xiàng)集

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

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

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

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

13、根據(jù)前面提到的置信度的定義，關(guān)聯(lián)規(guī)則的產(chǎn)生如下：（1）對(duì)于每個(gè)頻繁項(xiàng)集L，產(chǎn)生L的所有非空子集；（2）對(duì)于L的每個(gè)非空子集S，如果P（L）/P（S）min_conf則輸出規(guī)則“SL-S”注：L-S表示在項(xiàng)集L中除去S子集的項(xiàng)集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ì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)性質(zhì)剪枝：頻繁項(xiàng)集的所有子集必須是頻繁的，對(duì)候選項(xiàng)候選項(xiàng)C3，我們可以刪除其子集為非頻繁的選項(xiàng)：，我們可以刪除其子集為非頻繁的選項(xiàng)：nA,B,C的的2項(xiàng)子集是項(xiàng)子集是A,B,A,C,B,C，其中，其中A,B不是

15、不是L2的的元素，所以刪除這個(gè)選項(xiàng)；元素，所以刪除這個(gè)選項(xiàng)；nA,C,E的的2項(xiàng)子集是項(xiàng)子集是A,C,A,E,C,E，其中，其中A,E 不是不是L2的的元素，所以刪除這個(gè)選項(xiàng)；元素，所以刪除這個(gè)選項(xiàng)；nB,C,E的的2項(xiàng)子集是項(xiàng)子集是B,C,B,E,C,E，它的所有，它的所有2項(xiàng)子集項(xiàng)子集都是都是L2的元素，因此保留這個(gè)選項(xiàng)。的元素，因此保留這個(gè)選項(xiàng)。n3這樣，剪枝后得到這樣，剪枝后得到C3=B,C,E圖圖6-3 :由由L2產(chǎn)生和剪枝候選產(chǎn)生和剪枝候選3項(xiàng)集的集合項(xiàng)集的集合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由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則n同時(shí)滿足最小支持度和最小置信度的才是強(qiáng)關(guān)聯(lián)規(guī)則，從頻繁項(xiàng)集產(chǎn)生的規(guī)則都滿足支

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、 2相依表中來(lái)考察，其中像相依表中來(lái)考察，其中像mcmc這樣的表目表示包含牛奶和咖啡的事務(wù)個(gè)數(shù)。這樣的表目表示包含牛奶和咖啡的事務(wù)個(gè)數(shù)。 從該表可以看出，從該表可以看出，m m和和c c在數(shù)據(jù)集在數(shù)據(jù)集D1D1和和D2D2中是正關(guān)聯(lián)的，在中是正關(guān)聯(lián)的，在D3D3中是負(fù)關(guān)聯(lián)的，中是負(fù)關(guān)聯(lián)的，而在而在D4D4中是中性的。對(duì)于中是中性的。對(duì)于D1D1和和D2D2，m m和和c c是正關(guān)聯(lián)的，因?yàn)槭钦P(guān)聯(lián)的，因?yàn)閙cmc（1000010000）顯著）顯著大于大于 直觀地，對(duì)于購(gòu)買牛奶的人直觀地，對(duì)于購(gòu)買牛奶的人（m=10000+1000=11000m=10000+1000=11000）而言，他們非?？?/p>

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

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

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

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ù)管理方面是有用的。一個(gè)流行的應(yīng)用領(lǐng)域是購(gòu)物籃分析，通分析和商務(wù)管理方面是有用的。一個(gè)流行的應(yīng)用領(lǐng)域是購(gòu)物籃分析，通過(guò)搜索經(jīng)常在一起購(gòu)買的商品的集合，研究顧客的購(gòu)買習(xí)慣。過(guò)搜索經(jīng)常在一起購(gòu)買的商品的集合，研究顧客的購(gòu)買習(xí)慣。l 關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項(xiàng)集（項(xiàng)的集合，如關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項(xiàng)集（項(xiàng)的集合

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