【正文】 下去直到找到他想要的結(jié)果或放棄。也可以這么說， OLAP 分析師是建立一系列的假設(shè)，然后通過 OLAP 驗(yàn)證或推翻這些假設(shè)來最終得到自己的結(jié)論。 OLAP 過程本質(zhì)上是一個演繹推理的過程。數(shù)據(jù)挖掘與OLAP 相比其不同之處在于數(shù)據(jù) 挖掘不是用來驗(yàn)證某個假設(shè)的模式 (模型 )的正確性，而是在數(shù)據(jù)庫中自己尋找模型。它在本質(zhì)上是一個歸納的過程。舉個例子，一個用數(shù)據(jù)挖掘工具的分析，想找到引起貸款拖欠的因素，數(shù)據(jù)挖掘可以幫他找到高負(fù)債和低收入是引起這個問題的因素，甚至還能發(fā)現(xiàn)一些分析師從沒想過或試過的其它因素。 概括說來，數(shù)據(jù)挖掘與傳統(tǒng)的數(shù)據(jù)分析 (如查詢、報(bào)表、聯(lián)機(jī)分析處理 )的本質(zhì)區(qū)別是數(shù)據(jù)挖掘是在沒有明確假設(shè)的前提下去挖掘信息、發(fā)現(xiàn)知識。數(shù)據(jù)挖掘所得到的信息應(yīng)具有原先未知、有效和實(shí)用三個特征。先前未知的信息是指該信息是預(yù)先未能預(yù)料北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 19 的。即數(shù)據(jù)挖掘是 要發(fā)現(xiàn)那些不能靠直覺發(fā)現(xiàn)的信息或知識，甚至是違背直覺的信息或知識，挖掘出的信息越是出乎意料，就可能越有價(jià)值。 數(shù)據(jù)挖掘是從現(xiàn)實(shí)世界中存在的一些具體的數(shù)據(jù)中提取知識，這些數(shù)據(jù)在數(shù)據(jù)挖掘出現(xiàn)之前早己存在；而機(jī)器學(xué)習(xí)所使用的數(shù)據(jù)是專門為機(jī)器學(xué)習(xí)而特別準(zhǔn)備的數(shù)據(jù)，這些數(shù)據(jù)在現(xiàn)實(shí)世界中也許毫無意義。由于數(shù)據(jù)挖掘使用的數(shù)據(jù)來自于實(shí)際的數(shù)據(jù)庫，所要處理的數(shù)據(jù)量可能很大，因此數(shù)據(jù)挖掘算法的效率和可擴(kuò)充性就顯得尤為重要；此外，數(shù)據(jù)挖掘所處理的數(shù)據(jù)由于來自于現(xiàn)實(shí)世界，數(shù)據(jù)的完整性、一致性和正確性都很難保證，如何將這些數(shù)據(jù)加工成 算法可以接收的數(shù)據(jù)也需要進(jìn)行深入的研究；再者，數(shù)據(jù)挖掘可以利用目前數(shù)據(jù)庫技術(shù)所取得的研究成果來加快挖掘過程，提高挖掘的效率。最后，由于數(shù)據(jù)挖掘處理的數(shù)據(jù)來自于實(shí)際的數(shù)據(jù)庫，而與這些數(shù)據(jù)庫數(shù)據(jù)有關(guān)的還有其他一些背景知識，這些背景知識的合理運(yùn)用也會提高算法的效率。 關(guān)聯(lián)規(guī)則 關(guān)聯(lián)規(guī)則介紹 數(shù)據(jù)挖掘所發(fā)現(xiàn)出的知識種類中關(guān)聯(lián)規(guī)則的應(yīng)用是目前數(shù)據(jù)挖掘領(lǐng)域中研究最為廣泛的課題之一。關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)之間潛在關(guān)系的規(guī)則。關(guān)聯(lián)規(guī)則挖掘的一般對象是事務(wù)數(shù)據(jù)庫，起初主要應(yīng)用于零售業(yè)，比如超級市 場的銷售管理。條形碼技術(shù)的發(fā)展使得數(shù)據(jù)的收集變得更容易更完整，從而存儲了大量交易資料，關(guān)聯(lián)規(guī)則是通過辨別這些交易資料，來分析顧客的購買模式。根據(jù)關(guān)聯(lián)規(guī)則提供的信息可以用做商品銷售目錄設(shè)計(jì)、商品布置、針對性的營銷等。 1993 年 Agrawal ，并于1994 年提出了挖掘關(guān)聯(lián)規(guī)則的經(jīng)典 Apriori 算法。后來有不少學(xué)者對關(guān)聯(lián)規(guī)則的挖掘問題進(jìn)行了大量的研究。他們的工作包括對原有 Aprior 算法進(jìn)行優(yōu)化，如引入隨機(jī)采樣、并行的思想、使用哈希方法等，以提高算法挖掘規(guī) 則的效率，有的為了避免頻繁集產(chǎn)生方法的一些缺陷，提出了獨(dú)立于 Apriori 算法的挖掘關(guān)聯(lián)規(guī)則的新方法，如 Jianwei Han北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 20 等人提出的不產(chǎn)生候選挖掘頻繁項(xiàng)集的 FPGrowth 方法、基于關(guān)聯(lián)圖的挖掘關(guān)聯(lián)規(guī)則的方法等。 關(guān)聯(lián)規(guī)則的有關(guān)定義 設(shè) ??12, , , nI i i i? ???? 是 n 個不同項(xiàng) (Item)的集合， (1 )ji i n?? 表示集合中的第 j 項(xiàng)。相同的事務(wù)的集合構(gòu)成事務(wù)集 D。一組項(xiàng)的集合構(gòu)成一個事務(wù) T，使得 TI? 每一個事物都與唯一的標(biāo)識符 TID 相聯(lián)。設(shè) A 是一個項(xiàng)集當(dāng)且僅當(dāng) AT? 時就稱事務(wù) T 包含 A。一條關(guān)聯(lián)規(guī)則就是一個形如 AB? 的蘊(yùn)涵式，其中 AT? ， BI? ， AB? ?? 。 關(guān)聯(lián)規(guī)則的實(shí)用性由支持度衡量。描述了 A 和 B 兩個項(xiàng)集同時出現(xiàn)的概率 .定義為 :support(A?B)=P(A? B)。關(guān)聯(lián)規(guī)則的準(zhǔn)確性由置信度衡量，描述了出現(xiàn) A 的前提下也出現(xiàn) B 的概率，定義為， ( ) ( ) / ( )C o n fid e n c e A B P A B P A? ? ?。 最小支持度表示項(xiàng)集的最低實(shí)用性，最小置信度表示關(guān)聯(lián)規(guī)則的最低可靠性。滿足最小支持度 minsup 的項(xiàng)集成為頻繁項(xiàng)集，同時滿足最小支持度 minsup 和最小可信度minconf 的規(guī)則成為強(qiáng)關(guān)聯(lián)規(guī)則。 Support ( ) ( )A B P A B? ? ? Confidence ()( ) 10 0% ( / )()P A BA B P B APA?? ? ? ? 關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的過程大體為兩步，如下圖所示，第一步是利用頻繁項(xiàng)集搜索算法從事物數(shù)據(jù)中找出所有大于或等于。 up 的頻繁項(xiàng)集的集合 :第二步是根據(jù)設(shè)定的 minconf 從頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則。第一步要從大量的事物數(shù)據(jù)中找出頻繁項(xiàng)集，每次執(zhí)行部要掃描一次數(shù)據(jù)庫，需要耗費(fèi)大量的時間和空間，所以對關(guān)聯(lián)規(guī)則算法的研究工作主要是對第一步算法的優(yōu)化或改進(jìn)。 描述關(guān)聯(lián)規(guī)則屬性常用的參數(shù)有 : 支持度 (Support) 支持度 S 是 D 中包含 AB? 的事務(wù)百分比，它是概率 ()PA B? ，即 北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 21 ? ? ? ?s u p p o r t A B P A B ? ? ?，它描述了 A 和 B 這兩個物品集的并集在所有的事務(wù)中出現(xiàn)的概率。例如，一事務(wù)數(shù)據(jù)庫中共有 1000 條記錄，其中同時包含 A 和 B 的 100條，則關(guān)聯(lián)規(guī)則 AFB 的支持度為 100/ 1000 100% =10%。支持度表示了規(guī)則的頻度。滿足最小支持度的項(xiàng)集稱之為頻繁項(xiàng)集。 置信度 (Confidence) 置信度 C 為 D 中包含 A 的事務(wù)中同時也包含 B 的百分比，它是概率 ( / )PB A ，即? ?c o n f id e n c e A B P ( B /A )??。在上例中，如果有 200 條記錄包含 A，則關(guān)聯(lián)規(guī)則AB? 的置信度為 100/200 100% =50%。置信度表示了規(guī)則的強(qiáng)度。 同時滿足最小支持度閾值和最小置信度閾 值的規(guī)則稱作強(qiáng)規(guī)則。 期望置信度 (Expected Confidence) 期望置信度 e 為 D 中包含 B 的事務(wù)百分比，即 P (B )。期 望置信度描述在沒有任何條件影響時，物品集 B 在所有事物中出現(xiàn)的概率有多大。在上例中如果有 150 條記錄包含 B，則關(guān)聯(lián)規(guī)則 AFB 的期望置信度為 150/ 1000 100% =15%。 作用度 (Lift) 作用度是置信度與期望置信度的比值，即 ? ?P (B/A) / P B。作用度描述了項(xiàng)集 A 的出現(xiàn)對項(xiàng)集 B 的出現(xiàn)有多大的影響，作用度越大，說明物品集 B 受物品集 A 的影響越大。因?yàn)轫?xiàng)集 B 在所有事務(wù)中出現(xiàn)的概率是期望置信度 ； 而項(xiàng)集 B 在所有項(xiàng)集 A 出現(xiàn)的概率是置信度，通過置信度與期望置信度的比值反映 了在加入“項(xiàng)集 A 出現(xiàn)”這個條件后，項(xiàng)集 B 的出現(xiàn)概率發(fā)生了多大的變化。在上例中，關(guān)聯(lián)規(guī)則 AB? 的作用度為 50%/15% ≈ 3. 3。一般情況，有用的關(guān)聯(lián)規(guī)則的作用度都應(yīng)該大于 1，只有關(guān)聯(lián)規(guī)則的可信度大于期望可信度，才說明 A 的出現(xiàn)對 B 的出現(xiàn)有促進(jìn)作用，也說明了它們之間某種程序的相關(guān)性，如果作用度不大于 1,則此關(guān)聯(lián)規(guī)則也就沒有意義了。 興趣度 (Interest measure) 在數(shù)據(jù)挖掘中，并不是所有的強(qiáng)關(guān)聯(lián)規(guī)則都是足夠的有趣而值得向用戶提供。例如一個學(xué)校的 5000 名學(xué)生進(jìn)行早晨參與活動與早餐的情況調(diào)查。數(shù)據(jù)顯示 ： 60%的學(xué)生(3000)晨練， 75%的學(xué)生 (3750)吃早餐， 40%的學(xué)生 (2020)即晨練又吃早餐。假設(shè)最小支北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 22 持度為 40%，最小置信度為 60%，則 ?晨 練 吃 早 餐 。是一強(qiáng)關(guān)聯(lián)規(guī)則，因?yàn)槠渲С侄葹?40%，置信度為 2020/3000 100% =66%，滿足最小支持?jǐn)?shù)和最小置信度的要求，然而以上規(guī)則是誤導(dǎo)，因?yàn)榭偟某栽绮偷膶W(xué)生占 75%，比 66%還要大，為了修剪一些無趣的規(guī)則，即避免生成錯覺的關(guān)聯(lián)規(guī)則，下面定義了興趣度 這個度量值。 基于差異思想的興趣度定義 ? ?()m ax , ( )RR RC S BI C S B??，分母上的 ? ?max , ( )RC S B 只是一個標(biāo)準(zhǔn)化因子，使得 1RI ? 。根據(jù)這個式子，一條規(guī)則的興趣度越大 (IR0)說明對這條規(guī)則越感興趣 (即其實(shí)際利用價(jià)值越大 )；一條規(guī)則的興趣度越小 (IR0) 說明對這條規(guī)則的反面規(guī)則越感興趣 (即其反面規(guī)則的實(shí)際利用價(jià)值越大 )。 基于概率論的興趣度定義： ()( ) ( )S A BI S A S B??。這樣整個關(guān)聯(lián)規(guī)則的評價(jià)體系就可以統(tǒng)一在概率論的范疇內(nèi)。即從概率論的角度說，興趣度 I 反映了關(guān)聯(lián)規(guī)則中 A 和 B 之間的關(guān)系究竟如何密切。通過定義可以說明，當(dāng) A 和 B 相互獨(dú)立時，他們同時發(fā)生就純屬偶然，他們同時發(fā)生的意義就不會被人們關(guān)注。即，當(dāng) ? ? ? ? ? ?S A B S A S B? 時，其所對應(yīng)的關(guān)聯(lián)規(guī)則是沒有意義的。相應(yīng)的，當(dāng)一條關(guān)聯(lián)規(guī)則的興趣度大于 1 說明對這條規(guī)則越感興趣 ；一 規(guī)則的興趣度越小于 1 說明對這條規(guī)則的反面規(guī)則越感興趣 。顯然，此種定義的興趣度不小于 0。 關(guān)聯(lián)規(guī)則描述了 A 的出現(xiàn)影響到 B 的出現(xiàn)。 現(xiàn)實(shí)中，這樣的例子很多。例如超級市場利用收款機(jī)收集存儲了大量的售貨數(shù)據(jù)，這些數(shù)據(jù)是一條條的購買事務(wù)記錄，每條記錄存貯了事務(wù)處理時間，顧客購買的物品，物品的數(shù)量及金額等。這些數(shù)據(jù)中常常隱含形式如下的關(guān)聯(lián)規(guī)則 :在購買牛奶的顧客當(dāng)中，有 70%的人同時購買了面包。這些關(guān)聯(lián)規(guī)則很有價(jià)值，商場管理人員可以根據(jù)這些關(guān)聯(lián)規(guī)則更好的規(guī)劃商場，如將面包和牛奶這樣的商品擺放在一起，能夠促進(jìn)銷售。一些數(shù)據(jù)不像售貨數(shù)據(jù)那樣很容易就能看出一個事務(wù)是許多物品的集合，但稍微轉(zhuǎn)換一下思考角度，仍然可以像售貨數(shù)據(jù)一樣處理。比如人壽保險(xiǎn)，一份保 單就是一個事務(wù)。保險(xiǎn)公司在接受保險(xiǎn)前，往往需要記錄投保人詳盡的信息，有時還要到醫(yī)院做身體檢查。保單上記錄有投保人的年齡、性別、健康狀況、工作單位、工作地址、工資水平等。這些投保人的個人住處就可以看作事務(wù)中北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 23 的樣品。通過分析這些數(shù)據(jù)，可以得到類似以下這樣的關(guān)聯(lián)規(guī)則 :年齡在 40 歲以上，區(qū)的投保人當(dāng)中歲以上是物品甲，有 45%的曾經(jīng)向保險(xiǎn)公司索賠過。在這條規(guī)則中。工作在年齡在，工作在 A 區(qū)是物品乙。向保險(xiǎn)公司索賠過則是物品丙?？梢钥吹贸鰜恚?A 區(qū)可能污染比較嚴(yán)重，環(huán)境比較差，導(dǎo)致工作在該區(qū)的人健康狀況不好，索賠率也相對比較高。 關(guān)聯(lián)規(guī)則的分類 我們將關(guān)聯(lián)規(guī)則按不同的情況進(jìn)行分類： 基于規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。 布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系；值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來，對數(shù)值型字段進(jìn)行處理，將其進(jìn)行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進(jìn)行處理，值型關(guān)聯(lián)規(guī)則中也可以包含種類變量。例如：性別 =“女” ? 職業(yè) =“秘書”，是布爾型關(guān)聯(lián)規(guī)則：性別 =“女” ? avg（收入） =1800，涉及的是數(shù)值類型，所以是一個數(shù)值型關(guān)聯(lián)規(guī)則。 基于規(guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。 在單層的關(guān)聯(lián)規(guī)則中，所有的變量都沒有考慮到現(xiàn)實(shí)的數(shù)據(jù)是具有多個不同的層次的 ：在多層的關(guān)聯(lián)規(guī)則中，對數(shù)據(jù)的多層性已經(jīng)進(jìn)行了充分的考慮。例如： I BM 臺式機(jī) ?Sony 打印機(jī)，是一個細(xì)節(jié)數(shù)據(jù)上的單層關(guān)聯(lián)規(guī)則；臺式機(jī) ? Sony 打印機(jī)，是一個較高 層次和細(xì)節(jié)層次之間的多層關(guān)聯(lián)規(guī)則。 基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分單維和多維的。 在單維的關(guān)聯(lián)規(guī)則中，我們只涉及到數(shù)據(jù)的一個維，如用戶購買的物品；而在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。換成另一句話，單維關(guān)聯(lián)規(guī)則是處理單個屬性中的一些關(guān)系 。多維關(guān)聯(lián)規(guī)則是處理各個屬性之間的某些關(guān)系。 北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 24 2． 3 挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法 介紹 為了描述算法，我們給出了原事務(wù)數(shù)據(jù)庫如表 23 所示，每個項(xiàng)目賦一個整數(shù)，Bread1, Coke2, Milk3, Beer4, Cake5，得整 數(shù)化后的數(shù)據(jù)庫如表 24 設(shè)最小支持度為22%，因?yàn)橐还灿?9 個事務(wù)， (9 22% 2) 2??次，給定一個事務(wù)數(shù)據(jù)庫 D，挖掘關(guān)聯(lián)規(guī)則的問題就是找出所有滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則，即挖出所有的強(qiáng)規(guī)則，該問題可分解為兩個子問題：①找出所有頻繁項(xiàng)目集， 即出現(xiàn)頻率至少和預(yù)定義的最小支持一樣的項(xiàng)目集。②由頻繁項(xiàng)目集產(chǎn)生關(guān)聯(lián)規(guī)則。一旦找出了頻繁項(xiàng)目集，則由它們產(chǎn)生強(qiáng)相關(guān)規(guī)則就簡單了，因?yàn)榭梢詓up _ ( )( ) ( / ) sup _ ( )port c ount A Bc onfi de nc e A B P A B port c ount A?? ? ?來計(jì)算置信度，其中s u p _ ( )port count A B?是包含 AB? 的事物集， sup _ ( )port count A是包含 A 的事物集。所以現(xiàn)在的研究都放在了第一步，即找到頻繁項(xiàng)目集。 表 23 原事物數(shù)據(jù)庫 表 24 整數(shù)化的