第5章數(shù)據(jù)挖掘-1

1、數(shù)據(jù)挖掘數(shù)據(jù)挖掘的產(chǎn)生n隨著數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，人們積累的數(shù)據(jù)越來越多。目前的數(shù)據(jù)庫系統(tǒng)可以高效地實現(xiàn)數(shù)據(jù)的錄入、查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢。缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。數(shù)據(jù)挖掘的案例：“啤酒啤酒”和和“尿布尿布”n一則廣為流傳的案例：啤酒和尿布的故事n美國加州某個超市連鎖店發(fā)現(xiàn): 在下班后前來購買嬰兒尿布的顧客多數(shù)是男性，他們往往也同時購買啤酒。n處理：重新布置了貨架，啤酒類商品、嬰兒尿布、土豆片之類的佐酒小食品、男士們?nèi)粘Ｉ钣闷肪徒贾?。n結(jié)果：上述幾種商

2、品的銷量幾乎馬上成倍增長。什么是數(shù)據(jù)挖掘?n從數(shù)據(jù)集中識別出有效的、新穎的、潛在有用的，以及最終可理解的模式的非平凡過程。n非平凡（的過程）：有一定的智能性、自動性（僅僅給出所有數(shù)據(jù)之和不能算做一個發(fā)現(xiàn)過程）。n有效性：所發(fā)現(xiàn)的模式對新的數(shù)據(jù)仍保持一定的可信度。n新穎性：所發(fā)現(xiàn)的模式應(yīng)該是新的。n潛在有用性：所發(fā)現(xiàn)的模式將來有實際的效用。n最終可理解性：能被用戶理解，如：簡潔性n有趣性：有效性、新穎性、潛在有用性、最終可理解性的綜合。數(shù)據(jù)挖掘是多學(xué)科的交叉數(shù)據(jù)挖掘數(shù)據(jù)庫技術(shù)統(tǒng)計學(xué)其他學(xué)科信息科學(xué)機器學(xué)習(xí)可視化數(shù)據(jù)挖掘與數(shù)據(jù)倉庫的關(guān)系n數(shù)據(jù)挖掘是數(shù)據(jù)倉庫發(fā)展的必然結(jié)果n數(shù)據(jù)倉庫為數(shù)據(jù)挖掘提供應(yīng)用

3、基礎(chǔ)n數(shù)據(jù)挖掘也不必非得建立一個數(shù)據(jù)倉庫n從數(shù)據(jù)倉庫中直接進行數(shù)據(jù)挖掘有許多好處。數(shù)據(jù)挖掘和OLAPnOLAP分析過程在本質(zhì)上是一個演繹推理演繹推理的過程，是決策支持領(lǐng)域的一部分。傳統(tǒng)的查詢和報表工具是告訴你數(shù)據(jù)庫中都有什么（what happened），OLAP則更進一步告訴你下一步會怎么樣（What next）和如果采取這樣的措施又會怎么樣（What if）。用戶首先建立一個假設(shè)，然后用OLAP檢索數(shù)據(jù)庫來驗證這個假設(shè)是否正確。n數(shù)據(jù)挖掘在本質(zhì)上是一個歸納推理歸納推理的過程，與OLAP不同的地方是，數(shù)據(jù)挖掘不是用于驗證某個假定的模式（模型）的正確性，而是在數(shù)據(jù)庫中自己尋找模型。n數(shù)據(jù)挖掘和

4、OLAP具有一定的互補性互補性。在利用數(shù)據(jù)挖掘出來的結(jié)論采取行動之前，OLAP工具能起輔助決策作用。而且在知識發(fā)現(xiàn)的早期階段，OLAP工具用來探索數(shù)據(jù)，找到哪些是對一個問題比較重要的變量，發(fā)現(xiàn)異常數(shù)據(jù)和互相影響的變量。這都有助于更好地理解數(shù)據(jù)，加快知識發(fā)現(xiàn)的過程。數(shù)據(jù)挖掘的步驟n數(shù)據(jù)準(zhǔn)備 n數(shù)據(jù)選擇：目標(biāo)數(shù)據(jù)n數(shù)據(jù)預(yù)處理：消除噪聲、不一致、冗余等n數(shù)據(jù)變換：連續(xù)數(shù)據(jù)離散化、數(shù)據(jù)轉(zhuǎn)化n數(shù)據(jù)歸約：特征選擇或抽取n數(shù)據(jù)挖掘算法的選擇.n首先要明確任務(wù),如數(shù)據(jù)總結(jié)、分類、聚類、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、序列模式發(fā)現(xiàn)等。n考慮用戶的知識需求（得到描述性的知識、預(yù)測型的知識）。n根據(jù)具體的數(shù)據(jù)集合，選取有效的挖掘算法

5、。數(shù)據(jù)挖掘的步驟n結(jié)果的解釋評估（interpretation and evaluation）n對挖掘出來的結(jié)果（模式），經(jīng)用戶或機器評價，剔除冗余或無關(guān)的模式。n模式不滿足用戶需求時，返回到某一步，重新挖掘。如：重新選擇數(shù)據(jù)、采用新的變換方法、設(shè)定新的數(shù)據(jù)挖掘參數(shù)，或者換一種挖掘算法（如分類方法，不同的方法對不同的數(shù)據(jù)有不同的效果）。n挖掘的結(jié)果是面向用戶的，對挖掘結(jié)果進行可視化或者轉(zhuǎn)化為用戶易于理解的形式表示。n 評注n影響挖掘結(jié)果質(zhì)量的因素：采用的算法、數(shù)據(jù)本身的質(zhì)量與數(shù)量n數(shù)據(jù)挖掘的過程是一個不斷反饋的過程n可視化在數(shù)據(jù)挖掘過程的各個階段都扮演著重要角色，如用散點圖或直方圖等統(tǒng)計可視化

6、技術(shù)來顯示有關(guān)數(shù)據(jù)，以期對數(shù)據(jù)有一個初步的了解。常用的數(shù)據(jù)挖掘方法n目前一般常用的數(shù)據(jù)挖掘方法很多，它們大多屬于數(shù)學(xué)統(tǒng)計方法或人工智能中的機器學(xué)習(xí)算法，以及人工神經(jīng)網(wǎng)絡(luò)/遺傳算法。n概念概念/類描述類描述n關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘n序列模式分析序列模式分析n分類分析分類分析n聚類分析聚類分析n異常點檢測異常點檢測概念/類描述n概念描述概念描述(concept description)：對含有大量數(shù)據(jù)的數(shù)據(jù)集合進行概述性的總結(jié)并獲得簡明、準(zhǔn)確的描述。n如一個大學(xué)中講師、副教授的情況n講師：75% (papers3) and (teaching courses=3) and (teaching c

7、ourses=2)n概念描述與數(shù)據(jù)泛化密切相關(guān)概念描述與數(shù)據(jù)泛化密切相關(guān)n允許數(shù)據(jù)集在多個抽象層泛化，便于用戶考察數(shù)據(jù)的一般行為n方法:nOLAPOLAP方法方法n面向?qū)傩缘臍w納面向?qū)傩缘臍w納OLAPOLAP方法方法n在數(shù)據(jù)立方體上進行計算和存儲結(jié)果n優(yōu)點n效率高n能夠計算多種匯總n如：count,average,sum,min,maxn可以使用roll-down和roll-up操作n限制n只能處理非數(shù)值化數(shù)據(jù)和數(shù)值數(shù)據(jù)的簡單匯總。n只能分析，不能自動的選擇哪些字段和相應(yīng)的概念層次面向?qū)傩缘臍w納n不限制于種類字段和特定的匯總方法n方法介紹：n使用SQL等收集相關(guān)數(shù)據(jù)n通過數(shù)據(jù)屬性值刪除和屬性值

8、概化來實現(xiàn)概化n聚集通過合并相等的廣義元組，并累計他們對應(yīng)的計數(shù)值進行n和使用者之間交互式的呈現(xiàn)方式.示例示例nDMQL: use Big_University_DBmine characteristics as “Science_Students”in relevance to name, gender, major, birth_place, birth_date, residence, phone#, gpafrom studentwhere status in “graduate”n相應(yīng)的相應(yīng)的SQL:SQL:Select name, gender, major, birth_plac

9、e, birth_date, residence, phone#, gpafrom studentwhere status in “Msc”, “MBA”, “PhD” 關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。隨著大量數(shù)據(jù)不停地收集和存儲，人們對于從數(shù)據(jù)庫中挖掘關(guān)聯(lián)規(guī)則越來越感興趣。從大量商業(yè)事務(wù)記錄中發(fā)現(xiàn)有趣的關(guān)聯(lián)關(guān)系，可以幫助許多商務(wù)決策的制定，如分類設(shè)計、交叉購物和促銷分析等。2computer = financial _ management _ softwaresupport = 2%, confidence = 60%關(guān)聯(lián)規(guī)則的支持度(support)2

10、% 表示：分析中的全部事務(wù)的2% 同時購買計算機和財務(wù)管理軟件。關(guān)聯(lián)規(guī)則的置信度(confidence)60% 表示：購買計算機的顧客60% 也購買財務(wù)管理軟件。6事務(wù)數(shù)據(jù)庫 n設(shè)I= i1，i2，im 是一個項目集合，事務(wù)數(shù)據(jù)庫D= t1，t2，tn 是由一系列具有唯一標(biāo)識TID的事務(wù)組成，每個事務(wù)ti（i=1，2，n）都對應(yīng)I上的一個子集。n一個事務(wù)數(shù)據(jù)庫可以用來刻畫：n購物記錄： I是全部物品集合， D是購物清單，每個元組ti是一次購買物品的集合（它當(dāng)然是I的一個子集）。p項集：項的集合，包含k個項的項集稱為k-項集。p關(guān)聯(lián)規(guī)則： 形如 A = B 的蘊涵式，其中 A I , B I ,

11、 并且 A B =每個發(fā)現(xiàn)的模式都應(yīng)當(dāng)有一個表示其有效性的確定性度量，關(guān)聯(lián)規(guī)則的確定性度量為：8=置信度c:confidence ( A = B ) = P ( B | A)置信度為100% 或1，意味著數(shù)據(jù)分析時，該規(guī)則總是對的，這種規(guī)則稱為準(zhǔn)確的。9support _ count ( A U B )support_count ( A)【例】任務(wù)相關(guān)數(shù)據(jù)由某商店計算機部購買物品的事務(wù)數(shù)組成，一個置信度為80% 的關(guān)聯(lián)規(guī)則：buys ( X , “ computer ” ) = buys ( X , “ software ” )意味著買計算機的顧客80% 也買軟件。10一個模式潛在的有用性是定

12、義其興趣度的一個重要因素，可以用一個實用性函數(shù)(如支持度)來評估。關(guān)聯(lián)規(guī)則的支持度是模式為真的任務(wù)相關(guān)數(shù)據(jù)的事務(wù)所占的百分比。支持度s:support(A=B) =P ( A U B )support _ count(AU B) count (T)11 =【例2 】例1中一個支持度為30% 的關(guān)聯(lián)規(guī)則，意味著計算機部的所有顧客的30%,同時購買了計算機和軟件。支持度和置信度是兩個興趣度度量,分別反映發(fā)現(xiàn)規(guī)則的有用性和確定性。支持度?。阂?guī)則使用面窄置信度?。阂?guī)則無意義12滿足最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則被認(rèn)為是有趣的。閾值由用戶或?qū)＜以O(shè)定。強規(guī)則：同時滿足用戶定義的最小支持度閾值（m

13、in_sup）和最小置信度閾值(min_conf)的規(guī)則稱為強規(guī)則。為方便計，用0% 和100%之間的值表示支持度和置信度。13項集的頻率：即包含項集的事務(wù)數(shù)，也稱為項集的支持計數(shù)(support_count)。如果項集的出現(xiàn)頻率大于或等于min_sup與D中事務(wù)總數(shù)的乘積，就稱該項集滿足最小支持度min_sup 。頻繁項集：滿足最小支持度的項集稱為頻繁項集。頻繁k-項集的集合通常記作Lk。14關(guān)聯(lián)規(guī)則挖掘包含兩個步驟：1）找出所有頻繁項集：根據(jù)定義，這些項集的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。2）由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。15Aprior

14、i算法算法25Apriori 算法Apriori算法是根據(jù)有關(guān)頻繁項集性質(zhì)的先驗知識而命名的。該算法使用一種逐層搜索的迭代方法，利用k-項集探索(k+1)-項集。具體做法：首先找出頻繁1-項集的集合，記為L1 ；再用L1找頻繁2-項集的集合L2 ；再用L2找L3 如此下去，直到不能找到頻繁k-項集為止。找每個Lk需要一次數(shù)據(jù)庫掃描。26Apriori算法的有效性,在于它利用了一個非常重要的原理,即Apriori性質(zhì)。Apriori性質(zhì)：如果一個項集是頻繁的，則這個項集的任意一個非空子集都是頻繁的。它基于如下觀察：如果項集I不滿足最小支持度閾值min_sup，則I 不是頻繁的。如果增加項i到I，

15、則結(jié)果項集 I Ui不可能比I更頻繁出現(xiàn)。因此，也不是頻繁的。27整個過程由連接和剪枝兩步組成，即：連接步產(chǎn)生候選項集剪枝步確定頻繁項集(1)連接步為找Lk，可通過Lk-1與自己連接，產(chǎn)生一個候選k-項集的集合，該候選項集的集合記作Ck 。29設(shè)l1和l2是Lk-1中的項集，記號lij表示li的第j項。為方便計，假定事務(wù)或項集中的項按字典次序排序。執(zhí)行連接 Lk-1 Lk-1 ， 其中Lk-1的元素是可連接的，如果它們前(k-2 )個項相同。30即，Lk-1的元素l1和l2是可連接的，若：（ l11 = l21 l1 2 = l2 2 l1k-2 = l2k-2 l1k-1 l2k-1 ）而條件（l1k-1 B）=confidence（A=B）/support(B)=p(B|A)/p(B)=P( A U B )/ P(A) P(B)n如果提升度=1，表示A與B相互獨立，即規(guī)