【文章內(nèi)容簡(jiǎn)介】 制生產(chǎn)過(guò)程的質(zhì)量。76異常探測(cè)n 異常探測(cè)是數(shù)據(jù)挖掘中一個(gè)重要方面，用來(lái)發(fā)現(xiàn) “ 小的模式 ”(相對(duì)于聚類 )，即數(shù)據(jù)集中顯著不同于其它數(shù)據(jù)的對(duì)象。n 異常探測(cè)應(yīng)用n 電信和信用卡欺騙n 貸款審批n 藥物研究n 氣象預(yù)報(bào)n 金融領(lǐng)域n 客戶分類n 網(wǎng)絡(luò)入侵檢測(cè)等 77什么是異常 （ outlier） ？n Hawkins(1980)給出了異常的本質(zhì)性的定義： 異常是 在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。n 聚類算法對(duì)異常的定義：異常是聚類嵌于其中的背景噪聲。異常探測(cè)算法對(duì)異常的定義：異常是既不屬于聚類也不屬于背景噪聲的點(diǎn)。他們的行為與正常的行為有很大不同。78關(guān)聯(lián)分析association analysis79關(guān)聯(lián)n 若兩個(gè)或多個(gè)變量的取值之間存在某種規(guī)律性，就稱為關(guān)聯(lián)。n 關(guān)聯(lián)規(guī)則是尋找在同一個(gè)事件中出現(xiàn)的不同項(xiàng)的相關(guān)性，比如在一次購(gòu)買活動(dòng)中所買不同商品的相關(guān)性。n 關(guān)聯(lián)分析即利用關(guān)聯(lián)規(guī)則進(jìn)行數(shù)據(jù)挖掘。n 關(guān)聯(lián)規(guī)則是形式如下的一種規(guī)則， “在購(gòu)買計(jì)算機(jī)的顧客中，有 30％的人也 同時(shí) 購(gòu)買了打印機(jī) ”。n 從大量的商務(wù)事務(wù)記錄中發(fā)現(xiàn)潛在的關(guān)聯(lián)關(guān)系，可以幫助人們作出正確的商務(wù)決策。80啤酒和尿布問(wèn)題n 反映一個(gè)事件和其他事件之間依賴或關(guān)聯(lián)的知識(shí)。如果兩項(xiàng)或多項(xiàng)屬性之間存在關(guān)聯(lián)，那么其中一項(xiàng)的屬性值就可以依據(jù)其他屬性值進(jìn)行預(yù)測(cè)。n 在美國(guó)，一些年輕的父親下班后經(jīng)常要到超市去買嬰兒尿布，超市也因此發(fā)現(xiàn)了一個(gè)規(guī)律，在購(gòu)買嬰兒尿布的年輕父親們中，有 30%～ 40%的人同時(shí)要買一些啤酒。超市隨后調(diào)整了貨架的擺放，把尿布和啤酒放在一起，明顯增加了銷售額。81購(gòu)物籃分析n 此類關(guān)聯(lián)分析在零售業(yè)，如超市等得到廣泛應(yīng)用，企業(yè)可以獲得注入產(chǎn)品間的關(guān)聯(lián)，或者產(chǎn)品類別和購(gòu)買這些類別的產(chǎn)品的顧客的統(tǒng)計(jì)信息之間的關(guān)聯(lián)規(guī)則。n 關(guān)聯(lián)分析又稱購(gòu)物籃分析，在銷售配貨、商店商品的陳列設(shè)計(jì)、超市購(gòu)物路線設(shè)計(jì)、產(chǎn)品定價(jià)和促銷等方面得到廣泛應(yīng)用。82Association Rule? The first association discovery algorithm was designed for basket analysis in to answer “How many customers who bought item X also bought Item Y?”Such algorithm has been found useful in other applications, ., associations of drugs.Association rule:Frozenmeal = Cannedveg amp。 Beer (167:%, )Support: Number or percentage of transactions which contain both Cannedveg and Beer in the database.Confidence: Number of transactions containing Frozenmeal amp。 Cannedveg amp。 Beer number of transactions containing Cannedveg amp。 Beer83什么是關(guān)聯(lián)挖掘 ?n 關(guān)聯(lián)規(guī)則挖掘：n 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項(xiàng)目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)結(jié)構(gòu)。n 應(yīng)用：n 購(gòu)物籃分析 、 交叉銷售、產(chǎn)品目錄設(shè)計(jì) 、 聚集和分類等。n 舉例： n 規(guī)則形式： “Body —Head [support, confidence]”.n buys(x, “diapers”) — buys(x, “beers”) [%, 60%]n major(x, “CS”) ^ takes(x, “DB”) — grade(x, “A”) [1%, 75%]84關(guān)聯(lián)規(guī)則問(wèn)題的形式化描述項(xiàng)目n 定義 1：集合 I={i1， i2， …,im}為標(biāo)識(shí)符的集合，其中 m為正整數(shù)， ik（ k=1， 2， …,m)稱為項(xiàng)目。n 項(xiàng)目是一個(gè)從具體問(wèn)題中抽象出的一個(gè)概念。在超市的關(guān)聯(lián)規(guī)則挖掘問(wèn)題中，項(xiàng)目表示各種商品，如旅游鞋等。由于在超市的關(guān)聯(lián)規(guī)則挖掘中并不關(guān)心顧客購(gòu)買的商品數(shù)量和價(jià)格等，因此顧客的一次購(gòu)物可以用該顧客所購(gòu)買的所有商品的名稱來(lái)表示，稱為事務(wù)，所有事務(wù)的集合構(gòu)成關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)集，稱為事務(wù)數(shù)據(jù)庫(kù)。85事務(wù)n 定義 2：關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)庫(kù)記為 D， 事務(wù)數(shù)據(jù)庫(kù) D中的每個(gè)元組稱為事務(wù)。一條事務(wù) T是 I中項(xiàng)目的集合。一條事務(wù)僅包含其涉及到的項(xiàng)目，而不包含項(xiàng)目的具體信息。在超級(jí)市場(chǎng)的關(guān)聯(lián)規(guī)則挖掘問(wèn)題中事務(wù)是顧客一次購(gòu)物所購(gòu)買的商品，但事務(wù)中并不包含這些商品的具體信息，如商品的數(shù)量、價(jià)格等。86項(xiàng)目集n 定義 3：項(xiàng)目集是由 I中項(xiàng)目構(gòu)成的集合。若項(xiàng)目集包含的項(xiàng)目數(shù)為 k， 則稱此項(xiàng)目集為 k項(xiàng)目集。n 定義 4：任意的項(xiàng)目集 X和事務(wù) T若滿足： T?X， 則稱事務(wù) T包含項(xiàng)目集 X。n 在超市的關(guān)聯(lián)規(guī)則挖掘問(wèn)題中項(xiàng)目集可以看成一個(gè)或多個(gè)商品的集合。若某顧客一次購(gòu)買所對(duì)應(yīng)的事務(wù) T包含項(xiàng)目集 X， 就說(shuō)該顧客在這次購(gòu)物中購(gòu)買了項(xiàng)目集 X中的所有商品。87頻繁項(xiàng)目集n 定義 5：對(duì)任意的項(xiàng)目集 X， 若事務(wù)數(shù)據(jù)庫(kù) D中?%的事務(wù)包含項(xiàng)目集 X， 則項(xiàng)目集的支持率為 ?，記為 support（ X） = ?， 其中包含項(xiàng)目集 X的事務(wù)數(shù)稱為項(xiàng)目集 X的頻度，記為 count（ X）。 若項(xiàng)目集 X的支持率大于或等于用戶指定的最小支持率（minsupport）， 則項(xiàng)目集 X稱為 頻繁項(xiàng)目集 （或大項(xiàng)目集），否則項(xiàng)目集 X為非頻繁項(xiàng)目集（或小項(xiàng)目集）。如果數(shù)據(jù)庫(kù) D中的事務(wù)數(shù)記為 |D|， 頻繁項(xiàng)目集是至少被 ?%x|D|條事務(wù)包含的項(xiàng)目集 .88支持度和置信度n 定義 6:關(guān)聯(lián)規(guī)則是形如 XY的規(guī)則，其中 X， Y為項(xiàng)目集且 X?Y=?。n 定義 7：在數(shù)據(jù)庫(kù) D中，若 s%的事務(wù)包含 X?Y，則關(guān)聯(lián)規(guī)則 XY的支持度為 s%； 在數(shù)據(jù)庫(kù) D中，若c%的包含項(xiàng)目集 X的事務(wù)也包含項(xiàng)目集 Y， 則關(guān)聯(lián)規(guī)則 XY的置信度為 c%:n p（ Y│X）＝ p（ XY） /p(X)。n 置信度反應(yīng)了關(guān)聯(lián)規(guī)則的可信度 —購(gòu)買了項(xiàng)目集X中的商品的顧客同時(shí)也購(gòu)買了 Y中商品的 可能性 有多大。89強(qiáng)關(guān)聯(lián)規(guī)則n 定義 8：若關(guān)聯(lián)規(guī)則 XY的支持度和置信度分別大于或等于用戶指定的最小支持率 minsupport和最小置信度 minconfidence， 則稱關(guān)聯(lián)規(guī)則 XY為強(qiáng)關(guān)聯(lián)規(guī)則 ，否則稱關(guān)聯(lián)規(guī)則 XY為弱關(guān)聯(lián)規(guī)則。n 關(guān)聯(lián)規(guī)則挖掘的核心就是要找出事務(wù)數(shù)據(jù)庫(kù) D中的所有強(qiáng)相關(guān)規(guī)則。90關(guān)聯(lián)規(guī)則挖掘問(wèn)題的分解n 給定數(shù)據(jù)庫(kù) D， 關(guān)聯(lián)規(guī)則的挖掘就是找出所有存在于數(shù)據(jù)庫(kù) D中的強(qiáng)關(guān)聯(lián)規(guī)則。因此整個(gè)關(guān)聯(lián)規(guī)則挖掘過(guò)程可以分解為以下兩個(gè)子問(wèn)題：n 找出所有的頻繁項(xiàng)目集；n 根據(jù)找到的頻繁項(xiàng)目集導(dǎo)出所有的強(qiáng)關(guān)聯(lián)規(guī)則。91強(qiáng)關(guān)聯(lián)規(guī)則的產(chǎn)生n 第一個(gè)子問(wèn)題的求解，需要多次掃描數(shù)據(jù)庫(kù) D， 這意味著關(guān)聯(lián)規(guī)則挖掘算法的效率將主要取決于數(shù)據(jù)庫(kù)掃描、 I/O操作和頻繁項(xiàng)目集的計(jì)算上。因此如何迅速、高效地找出所有的頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘的中心問(wèn)題n 第二個(gè)子問(wèn)題的求解比較容易， R. Agrawal等人已提出了有效的解決辦法，具體過(guò)程如下：n 對(duì)每個(gè)頻繁項(xiàng)目集 I， 產(chǎn)生所有的非空真子集：對(duì) I的任意非空真真子集 m， 若 support（ I） /Support（ m）?minconfidence， 則產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則 m(lm)。92規(guī)則度量：支持度與可信度n 查找所有的規(guī)則 X amp。 Y ? Z 具有最小支持度和可信度n 支持度 , s, 交易中包含 {X 、 Y 、 Z}的 可能性n 可信度 , c, 包含 {X 、 Y}的交易中也包含 Z的 條件概率設(shè)最小支持度為 50%, 最小可信度為 50%, 則可得到A ? C (50%, %)C ? A (50%, 100%)買尿布的客戶二者都買的客戶買啤酒的客戶93關(guān)聯(lián)規(guī)則挖掘：路線圖n 布爾 vs. 定量 關(guān)聯(lián) (基于處理數(shù)據(jù)的類型 )n buys(x, “SQLServer”) ^ buys(x, “DMBook”) 174。 buys(x, “DBMiner”) [%, 60%]n age(x, “30..39”) ^ ine(x, “42..48K”) 174。 buys(x, “PC”) [1%, 75%]n 單維 vs. 多關(guān)聯(lián) (例子同上 )n 單層 vs. 多層分析n 哪個(gè)品牌的啤酒與那個(gè)牌子的尿布有關(guān)系 ?n 各種擴(kuò)展n 相關(guān)性、因果分析n 關(guān)聯(lián)并不一定意味著相關(guān)或因果n 添加約束n 如哪些 “小東西 ”的銷售促發(fā)了 “大家伙 ”的買賣？ 94關(guān)聯(lián)規(guī)則挖掘例子對(duì)于 A ? C：support = support({A 、 C}) = 50%confidence = support({A 、 C})/support({A}) = %Apriori的基本思想 :頻繁項(xiàng)集的任何子集也一定是頻繁的最小支持度 50%最小置信度 50%95Apriori算法n 連接 : 用 Lk1自連接得到 Ckn 修剪 : 一個(gè) k項(xiàng)集，如果它的一個(gè) k1項(xiàng)集（它的子集 ）不是頻繁的，那它本身也不可能是頻繁的。n 偽代碼 :Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = {frequent items}。for (k = 1。 Lk !=?。 k++) do begin Ck+1 = candidates generated from Lk。 for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Lk+1 = candidates in Ck+1 with min_support endreturn ?k Lk。96如何生成候選集n 假定 Lk1 中的項(xiàng)按順序排列n 第一步 : 自連接 Lk1 insert into Ckselect , , …, k1, from Lk1 p, Lk1 qwhere =, …, k2=, n 第二步 : 修剪forall itemsets c in Ck doforall (k1)subsets s of c doif (s is not in Lk1) then delete c from Ck97生成候選集的例子n L3={abc, abd, acd, ace, bcd}n 自連接 : L3*L3n abc 和 abd 得到 abcd n acd 和 ace 得到 acden 修剪 :n ade 不在 L3中，刪除 acden C4={abcd}98Apriori算法例子數(shù)據(jù)庫(kù) D掃描 DC1 L1L2C2掃描 DC3 L3掃描 D {2,3}{5}99Apriori 夠快了嗎 ? — 性能瓶頸n Apriori算法的核心 :n 用頻繁的 (k – 1)項(xiàng)集生成候選的頻繁 k項(xiàng)集n 用數(shù)據(jù)庫(kù)掃描和模式匹配計(jì)算候選集的支持度n Apriori 的瓶頸 : 候選集生成n 巨大的候選集 :n 多次掃描數(shù)據(jù)庫(kù) ： n 如果最長(zhǎng)的模式是 n的話，則需要 n +1次數(shù)據(jù)庫(kù)掃描100多層關(guān)聯(lián)規(guī)則n 項(xiàng)通常具有層次。n 底層的項(xiàng)通常支持度也低。n 某些特定層的規(guī)則可能更有意義。n 交易數(shù)據(jù)庫(kù)可以按照維或?qū)泳幋a。n 可以進(jìn)行共享的多維挖掘。食品面包牛奶脫脂奶光明統(tǒng)一酸奶 白黃101挖掘多層關(guān)聯(lián)規(guī)則n 自上而下，深度優(yōu)先的方法：n 先找高層的 “強(qiáng) ”規(guī)則：牛奶 174。 面包 [20%, 60%].n 再找他們底層的 “弱 ”規(guī)則：酸奶 174。 黃面包 [6%,