【正文】 對你所面臨的問題來說是最好的，因此很多情況下，需要建立用不同的方法（參數(shù)或算法）幾個(gè)模型，從中選擇最好的。13. 6. 評價(jià)和解釋。c. a. 模型驗(yàn)證。模型建立好之后，必須評價(jià)他的結(jié)果、解釋他的價(jià)值。記住從測試集中得到的準(zhǔn)確率只對用于建立模型的數(shù)據(jù)有意義。在實(shí)際應(yīng)用中，隨著應(yīng)用數(shù)據(jù)的不同，模型的準(zhǔn)確率肯定會(huì)變化。更重要的是，準(zhǔn)確度自身并不一定是選擇最好模型的正確評價(jià)方法。你需要進(jìn)一步了解錯(cuò)誤的類型和由此帶來的相關(guān)費(fèi)用的多少。無序矩陣。對分類問題來說，無序矩陣是理解結(jié)果的非常好的工具。如圖9所示，無序矩陣把預(yù)測的結(jié)果與實(shí)際的情況進(jìn)行對比。它不僅說明了模型預(yù)測的準(zhǔn)確情況，也把模型究竟在哪里出了問題也展示了出來。下表是一個(gè)簡單的無序矩陣，其中的列代表數(shù)據(jù)的實(shí)際分類情況，行是預(yù)測的結(jié)果。在這張表值中，可以看到此模型在總共46個(gè)B類數(shù)據(jù)中成功預(yù)測了38個(gè)，8個(gè)出了問題：2個(gè)預(yù)測成了A，6個(gè)成了C。顯然這比簡單的說模型總體準(zhǔn)確度是82%要更詳細(xì)的多（123個(gè)成功預(yù)測除以總共150）。預(yù)測實(shí)際類別A類別B類別C類別A4523類別B10382類別C4640圖9：無序矩陣在實(shí)際應(yīng)用中，如果每種不同的預(yù)測錯(cuò)誤所需付出的代價(jià)（金錢）也不同的話，那么代價(jià)最小的模型（而不一定是錯(cuò)誤率最小的模型）就是我們所要選擇的。例如，上面的無序矩陣中，如果每個(gè)準(zhǔn)確的預(yù)測會(huì)帶來￥10的收益，錯(cuò)誤的預(yù)測A要付出￥5的代價(jià)，B是￥10，C是￥20，那么整個(gè)模型的純價(jià)值是：(123*￥10)（5*￥5）（12*￥10）（10*￥20）=￥885然而考察下面的無序矩陣（圖10），雖然準(zhǔn)確度降低到79%（118/150），但純價(jià)值卻升高了：（118*￥10）（22*￥5）（7*￥10）（3*￥20）=￥940預(yù)測實(shí)際類別A類別B類別C類別A401210類別B6381類別C2140圖10：另一個(gè)無序矩陣收益表（圖11）也是一種描述模型價(jià)值的方法。它顯示了通過應(yīng)用模型響應(yīng)（如直接郵件推銷）的變化情況。變化的比率稱為lift。例如，如果用隨機(jī)抽取的方法選擇10%的客戶響應(yīng)率是10%，而通過模型選取10%的用戶響應(yīng)率是30%，則lift值為3。模型解釋的另一個(gè)重要組成部分是確定模型的價(jià)值。一個(gè)模型可能看起來很有意義，但要實(shí)施它的話很有可能花的錢比賺的錢多。圖12是一個(gè)描述模型投資回報(bào)率（ROI）的圖表（這里定義 ROI為利潤與開銷的比值）。注意圖中當(dāng)選取比例超過80%時(shí)，ROI變成了負(fù)數(shù)，ROI最高是在橫坐標(biāo)為2時(shí)。當(dāng)然，也可以直接看利潤的變化情況（利潤為收入與花費(fèi)的差值），如圖13所示：注意到我們上面的例子中，最大lift在第一個(gè)1/10處（10%），最大ROI在第2個(gè)1/10（20%），而最大利潤在第4個(gè)1/10處。理想情況下，應(yīng)該按照利潤表行事，但很多情況下利潤表并不能很容易的計(jì)算出來。d. b. 外部驗(yàn)證。如前面指出的，無論我們用模擬的方法計(jì)算出來的模型的準(zhǔn)確率有多高，都不能保證此模型在面對現(xiàn)實(shí)世界中真實(shí)的數(shù)據(jù)時(shí)能取得好的效果。經(jīng)驗(yàn)證有效的模型并不一定是正確的模型。造成這一點(diǎn)的直接原因就是模型建立中隱含的各種假定。例如，在建立用戶購買模式的模型時(shí)，可能沒有考慮通貨膨脹的影響，但實(shí)施模型時(shí)通貨膨脹率突然由3%增加為17%，這顯然會(huì)對人們的購買意向產(chǎn)生重大影響，因此再用原來的模型來預(yù)測客戶購買情況必然會(huì)出現(xiàn)重大失誤。因此直接在現(xiàn)實(shí)世界中測試模型很重要。先在小范圍內(nèi)應(yīng)用，取得測試數(shù)據(jù)，覺得滿意之后再向大范圍推廣。14. 7. 實(shí)施。模型建立并經(jīng)驗(yàn)證之后，可以有兩種主要的使用方法。第一種是提供給分析人員做參考，由他通過察看和分析這個(gè)模型之后提出行動(dòng)方案建議。比如可以把模型檢測到的聚集、模型中蘊(yùn)含的規(guī)則、或表明模型效果的ROI圖表拿給分析人員看。另一種是把此模型應(yīng)用到不同的數(shù)據(jù)集上。模型可以用來標(biāo)示一個(gè)事例的類別，給一項(xiàng)申請打分等。還可以用模型在數(shù)據(jù)庫中選擇符合特定要求的記錄，以用OLAP工具做進(jìn)一步的分析。通常情況下，模型是某個(gè)商業(yè)過程的組成部分，如風(fēng)險(xiǎn)分析，信用授權(quán)，或欺詐檢測。在這些情況下，模型一般都合并到應(yīng)用程序的內(nèi)部。例如，在抵押貸款應(yīng)用程序內(nèi)部可能集成了一個(gè)預(yù)測模型，來向貸款官員提供一項(xiàng)貸款申請風(fēng)險(xiǎn)大小的建議?；蛟诙ㄙ徬到y(tǒng)中，當(dāng)預(yù)測到庫存有可能降低到一個(gè)最低限度時(shí)自動(dòng)發(fā)出購買訂單。數(shù)據(jù)挖掘模型通常一次只能處理一個(gè)事件或一個(gè)事務(wù)。每個(gè)事務(wù)的處理時(shí)間和事務(wù)到達(dá)的速度，決定了模型運(yùn)行所需的計(jì)算能力，和是否要用并行技術(shù)來加快速度。比如，貸款申請程序可能PC機(jī)上就運(yùn)行的很好，而用于信用卡欺詐的模型則需要在服務(wù)器上用并行算法才能應(yīng)付每天的大量事務(wù)。當(dāng)提交一個(gè)復(fù)雜的應(yīng)用時(shí)，數(shù)據(jù)挖掘可能只是整個(gè)產(chǎn)品的一小部分，雖然可能是最關(guān)鍵的一部分。例如，常常把數(shù)據(jù)挖掘得到的知識與領(lǐng)域?qū)＜业闹R結(jié)合起來，然后應(yīng)用到數(shù)據(jù)庫中的數(shù)據(jù)。在欺詐檢測系統(tǒng)中可能既包含了數(shù)據(jù)挖掘發(fā)現(xiàn)的規(guī)律，也有人們在實(shí)踐中早已總結(jié)出的規(guī)律。模型監(jiān)控。在應(yīng)用了模型之后，當(dāng)然還要不斷監(jiān)控他的效果。即使你在開始使用這個(gè)模型之后覺得他非常成功，也不能放棄監(jiān)控，因?yàn)槭挛镌诓粩喟l(fā)展變化，很可能過一段時(shí)間之后，模型就不再起作用。銷售人員都知道，人們的購買方式隨著社會(huì)的發(fā)展而變化。因此隨著使用時(shí)間的增加，要不斷的對模型做重新測試，有時(shí)甚者需要重新建立模型。數(shù)據(jù)挖掘入門 一 數(shù)據(jù)挖掘入門 二 關(guān)聯(lián)規(guī)則挖掘綜述1(蔡偉杰 caiweijie528@)蔡偉杰 張曉輝 朱建秋 朱揚(yáng)勇2（復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)系 上海 200433）摘要 本文介紹了關(guān)聯(lián)規(guī)則挖掘的研究情況，提出了關(guān)聯(lián)規(guī)則的分類方法，對一些典型算法進(jìn)行了分析和評 本文的工作獲國家863計(jì)劃支持,項(xiàng)目編號863306ZT020512 蔡偉杰，碩士研究生，研究興趣數(shù)據(jù)倉庫和數(shù)據(jù)挖掘；張曉輝，碩士研究生，研究興趣為數(shù)據(jù)倉庫與數(shù)據(jù)采掘；朱建秋，博士研究生，研究興趣為知識庫，數(shù)據(jù)倉庫和數(shù)據(jù)挖掘；朱揚(yáng)勇，博士生導(dǎo)師，研究興趣為數(shù)據(jù)倉庫與數(shù)據(jù)采掘，多媒體技術(shù) 價(jià)，指出傳統(tǒng)關(guān)聯(lián)規(guī)則衡量標(biāo)準(zhǔn)的不足，歸納出關(guān)聯(lián)規(guī)則的價(jià)值衡量方法，展望了關(guān)聯(lián)規(guī)則挖掘的未來研究方向。關(guān)鍵詞 數(shù)據(jù)挖掘，關(guān)聯(lián)規(guī)則，頻集，OLAP1引言數(shù)據(jù)挖掘（Data Mining），又稱數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discovery in Database），在最近幾年里已被數(shù)據(jù)庫界所廣泛研究，其中關(guān)聯(lián)規(guī)則（Association Rules）的挖掘是一個(gè)重要的問題。關(guān)聯(lián)規(guī)則是發(fā)現(xiàn)交易數(shù)據(jù)庫中不同商品（項(xiàng)）之間的聯(lián)系，這些規(guī)則找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。發(fā)現(xiàn)這樣的規(guī)則可以應(yīng)用于商品貨架設(shè)計(jì)、貨存安排以及根據(jù)購買模式對用戶進(jìn)行分類。Agrawal等于1993年[1]首先提出了挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則問題，以后諸多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。他們的工作包括對原有的算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想等，以提高算法挖掘規(guī)則的效率；對關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣。最近也有獨(dú)立于Agrawal的頻集方法的工作[18,19]，以避免頻集方法的一些缺陷，探索挖掘關(guān)聯(lián)規(guī)則的新方法。同時(shí)隨著OLAP技術(shù)的成熟和應(yīng)用，將OLAP和關(guān)聯(lián)規(guī)則結(jié)合[20,21]也成了一個(gè)重要的方向。也有一些工作[6]注重于對挖掘到的模式的價(jià)值進(jìn)行評估，他們提出的模型建議了一些值得考慮的研究方向。本文第二部分是對關(guān)聯(lián)規(guī)則基本概念的介紹，提出了關(guān)聯(lián)規(guī)則的分類方法；第三部分是對挖掘算法的介紹，從經(jīng)典的apriori開始，然后描述了對該算法的優(yōu)化拓展，接著講述脫離apriori算法的方法，最后是多層、多維的關(guān)聯(lián)規(guī)則挖掘；第四部分歸納出關(guān)聯(lián)規(guī)則價(jià)值衡量方法，主要從兩個(gè)方面進(jìn)行考慮：系統(tǒng)客觀層面和用戶主觀層面；最后展望了關(guān)聯(lián)規(guī)則挖掘的未來研究方向。2關(guān)聯(lián)規(guī)則的基本概念設(shè)I={i1, i2,…, im}是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(item)。記D為交易(transaction)T的集合，這里交易T是項(xiàng)的集合，并且T205。I 。對應(yīng)每一個(gè)交易有唯一的標(biāo)識，如交易號，記作TID。設(shè)X是一個(gè)I中項(xiàng)的集合，如果X205。T，那么稱交易T包含X。一個(gè)關(guān)聯(lián)規(guī)則是形如X222。Y的蘊(yùn)涵式，這里X204。I, Y204。I，并且X199。Y=F。規(guī)則X222。Y在交易數(shù)據(jù)庫D中的支持度（support）是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(X222。Y)，即support(X222。Y)=|{T:X200。Y205。T，T206。D}|/|D|規(guī)則X222。Y在交易集中的可信度（confidence）是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(X222。Y)，即confidence(X222。Y)=|{T: X200。Y205。T，T206。D}|/|{T:X205。T，T206。D}|給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則。 關(guān)聯(lián)規(guī)則的種類我們將關(guān)聯(lián)規(guī)則按不同的情況進(jìn)行分類：1. 基于規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系；而數(shù)值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來，對數(shù)值型字段進(jìn)行處理，將其進(jìn)行動(dòng)態(tài)的分割，或者直接對原始的數(shù)據(jù)進(jìn)行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量。例如：性別=“女”=職業(yè)=“秘書” ，是布爾型關(guān)聯(lián)規(guī)則；性別=“女”=avg（收入）=2300，涉及的收入是數(shù)值類型，所以是一個(gè)數(shù)值型關(guān)聯(lián)規(guī)則。2. 基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。在單層的關(guān)聯(lián)規(guī)則中，所有的變量都沒有考慮到現(xiàn)實(shí)的數(shù)據(jù)是具有多個(gè)不同的層次的；而在多層的關(guān)聯(lián)規(guī)則中，對數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。例如：IBM臺(tái)式機(jī)=Sony打印機(jī)，是一個(gè)細(xì)節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則；臺(tái)式機(jī)=Sony打印機(jī)，是一個(gè)較高層次和細(xì)節(jié)層次之間的多層關(guān)聯(lián)規(guī)則。3. 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。在單維的關(guān)聯(lián)規(guī)則中，我們只涉及到數(shù)據(jù)的一個(gè)維，如用戶購買的物品；而在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會(huì)涉及多個(gè)維。換成另一句話，單維關(guān)聯(lián)規(guī)則是處理單個(gè)屬性中的一些關(guān)系；多維關(guān)聯(lián)規(guī)則是處理各個(gè)屬性之間的某些關(guān)系。例如：啤酒=尿布，這條規(guī)則只涉及到用戶的購買的物品；性別=“女”=職業(yè)=“秘書”，這條規(guī)則就涉及到兩個(gè)字段的信息，是兩個(gè)維上的一條關(guān)聯(lián)規(guī)則。給出了關(guān)聯(lián)規(guī)則的分類之后，在下面的分析過程中，我們就可以考慮某個(gè)具體的方法適用于哪一類規(guī)則的挖掘，某類規(guī)則又可以用哪些不同的方法進(jìn)行處理。Agrawal等于1993年[1]首先提出了挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻集理論的遞推方法。以后諸多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。他們的工作包括對原有的算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想等，以提高算法挖掘規(guī)則的效率；提出各種變體，如泛化的關(guān)聯(lián)規(guī)則、周期關(guān)聯(lián)規(guī)則等，對關(guān)聯(lián)規(guī)則的應(yīng)用進(jìn)行推廣。Agrawal等[1]在1993年設(shè)計(jì)了一個(gè)基本算法，提出了挖掘關(guān)聯(lián)規(guī)則的一個(gè)重要方法 — 這是一個(gè)基于兩階段頻集思想的方法，將關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計(jì)可以分解為兩個(gè)子問題：1) 找到所有支持度大于最小支持度的項(xiàng)集（Itemset），這些項(xiàng)集稱為頻集（Frequent Itemset)。2) 使用第1步找到的頻集產(chǎn)生期望的規(guī)則。這里的第2步相對簡單一點(diǎn)。如給定了一個(gè)頻集Y=I1I2...Ik，k179。2，Ij∈I，產(chǎn)生只包含集合{I1，I2，...，Ik}中的項(xiàng)的所有規(guī)則(最多k條)，其中每一條規(guī)則的右部只有一項(xiàng)，(即形如[YIi]222。Ii，1163。i163。k)，這里采用的是[4]中規(guī)則的定義。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。對于規(guī)則右部含兩個(gè)以上項(xiàng)的規(guī)則，在其以后的工作中進(jìn)行了研究，本文后面考慮的是這種情況。為了生成所有頻集，使用了遞推的方法。其核心思想如下：(1) L1 = {large 1itemsets}。(2) for (k=2。 Lk1185。F。 k++) do begin(3) Ck=apriorigen(Lk1)。 //新的候選集(4) for all transactions t206。D do begin(5) Ct=subset(Ck,t)。 //事務(wù)t中包含的候選集(6) for all candidates c206。 Ct do(7) ++。(8) end(9) Lk={c206。 Ck |179。minsup}(10) end(11) Answer=200。kLk。首先產(chǎn)生頻繁1項(xiàng)集L1，然后是頻繁2項(xiàng)集L2，直到有某個(gè)r值使得Lr為空，這時(shí)算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k項(xiàng)集的集合Ck，Ck中的每一個(gè)項(xiàng)集是對兩個(gè)只有一個(gè)項(xiàng)不同的屬于Lk1的頻集做一個(gè)(k2)連接來產(chǎn)生的。Ck中的項(xiàng)集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個(gè)子集。Ck中的每個(gè)元素需在交易數(shù)據(jù)庫中進(jìn)行驗(yàn)證來決定其是否加入Lk，這里的驗(yàn)證過程是算法性能的一個(gè)瓶頸。這個(gè)方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個(gè)項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負(fù)載。在論文[6]中，Agrawal等引入了修剪技術(shù)（Pruning）來減小候選集Ck的大小，由此可以顯著地改進(jìn)生成所有頻集算法的性能。算法中引入的修剪策略基于這樣一個(gè)性質(zhì)：一個(gè)項(xiàng)集是頻集當(dāng)且僅當(dāng)它的所有子集都是頻集。那么，如果Ck中某個(gè)候選項(xiàng)集有一個(gè)(k1)子集不屬于Lk1，則這個(gè)項(xiàng)集可以被修剪掉不再被考慮，這個(gè)修剪過程可以降低計(jì)算所有的候選集的支持度的代價(jià)。文[6]中，還引入雜湊樹（Hash Tree）方法來有效地計(jì)算每個(gè)項(xiàng)集的支持度。雖然Apriori算法自身已經(jīng)進(jìn)行了一定的優(yōu)化，但是在實(shí)際的應(yīng)用中，還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化的方法。1. 基于劃分的方法。Savasere等[14]設(shè)計(jì)了一個(gè)基于劃分(partition)的算法，這個(gè)算法先把數(shù)據(jù)庫從