數(shù)據(jù)挖掘原理及實踐蔣盛益版期末復(fù)習(xí)

1、第一章數(shù)據(jù)挖掘定義技術(shù)層面：數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中，提取潛在有用的信息和知識的過程。商業(yè)層面：數(shù)據(jù)挖掘就是一種商業(yè)信息處理技術(shù)，其主要特點(diǎn)是對大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和建模處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。數(shù)據(jù)挖掘任務(wù)預(yù)測任務(wù)根據(jù)其它屬性的值預(yù)測特定屬性的值，如分類、回歸、離群點(diǎn)檢測。描述任務(wù)尋找概括數(shù)據(jù)中潛在聯(lián)系的模式，如聚類分析、關(guān)聯(lián)分析、演化分析、序列模式挖掘 。(1) 分類(Classification)分析分類分析，通過分析示例數(shù)據(jù)庫中的數(shù)據(jù)為每個類別做出準(zhǔn)確的描述或建立分析模型或挖掘出分類規(guī)則，然后用此分類規(guī)則對其它數(shù)據(jù)庫中的記錄進(jìn)行分類。 分類分析廣泛應(yīng)用于用戶行

2、為分析(受眾分析)、風(fēng)險分析、生物科學(xué)等。(2) 聚類(Clustering)分析“物以類聚，人以群分”。聚類分析技術(shù)試圖找出數(shù)據(jù)集中的共性和差異，并將具有共性的對象聚合在相應(yīng)的類中。聚類可以幫助決定哪些組合更有意義，廣泛應(yīng)用于客戶細(xì)分、定向營銷、信息檢索等等。(3) 回歸(Regression )分析回歸分析是確定兩種或兩種以上變數(shù)間相互依賴的定量關(guān)系的一種分析方法。其可應(yīng)用于風(fēng)險分析、作文自動評分等領(lǐng)域。(4) 關(guān)聯(lián)(Association)分析關(guān)聯(lián)分析，發(fā)現(xiàn)特征之間的相互依賴關(guān)系，通常是從給定的數(shù)據(jù)集中發(fā)現(xiàn)頻繁出現(xiàn)的模式知識(又稱為關(guān)聯(lián)規(guī)則)。關(guān)聯(lián)分析廣泛用于市場營銷、事務(wù)分析等領(lǐng)域。聚

3、類與分類的主要區(qū)別聚類與分類是容易混淆的兩個概念，聚類是一種無指導(dǎo)的觀察式學(xué)習(xí)，沒有預(yù)先定義的類。而分類問題是有指導(dǎo)的示例式學(xué)習(xí)，預(yù)先定義的類。數(shù)據(jù)挖掘過程數(shù)據(jù)挖掘和知識發(fā)現(xiàn)緊密相連。知識發(fā)現(xiàn)是從數(shù)據(jù)中發(fā)現(xiàn)有用知識的整個過程n 知識發(fā)現(xiàn)的主要步驟：n 數(shù)據(jù)清洗。其作用是清除數(shù)據(jù)噪聲和與挖掘主題明顯無關(guān)的數(shù)據(jù)。n 數(shù)據(jù)集成。其作用是將來自多數(shù)據(jù)源中的相關(guān)數(shù)據(jù)組合到一起。n 數(shù)據(jù)轉(zhuǎn)換。其作用是將數(shù)據(jù)轉(zhuǎn)換為易于進(jìn)行數(shù)據(jù)挖掘的數(shù)據(jù)存儲形式。n 數(shù)據(jù)挖掘。其作用是利用智能方法挖掘數(shù)據(jù)模式或規(guī)律知識。n 模式評估。其作用是根據(jù)一定評估標(biāo)準(zhǔn)從挖掘結(jié)果篩選出有意義的相關(guān)知識。n 知識表示。其作用是利用可視化和

4、知識表達(dá)技術(shù)，向用戶展示所挖掘的相關(guān)知識從商業(yè)的角度看，數(shù)據(jù)挖掘過程可分為三個階段 數(shù)據(jù)收集：數(shù)據(jù)收集容易且不引人注意，但卻是數(shù)據(jù)挖掘的基礎(chǔ)。知識是從海量數(shù)據(jù)里提取出來的，因此要挖掘知識必須得收集一定量的數(shù)據(jù)。收集到的原始數(shù)據(jù)一般存在缺失值、錯誤值等問題，不能直接用作知識提取的數(shù)據(jù)源，需要進(jìn)行數(shù)據(jù)預(yù)處理。 知識提取：基于經(jīng)過預(yù)處理的數(shù)據(jù)，使用各種數(shù)據(jù)挖掘方法(如分類、聚類、關(guān)聯(lián)分析等)進(jìn)行知識提取，這是數(shù)據(jù)挖掘的核心部分。知識輔助決策：數(shù)據(jù)挖掘技術(shù)已被廣泛地應(yīng)用于各領(lǐng)域，其提取出來的知識可以很好地輔助決策者做出良好的決策第二章數(shù)據(jù)統(tǒng)計特征數(shù)據(jù)的中心度量1數(shù)據(jù)集 “中心”的最常用、最有效的數(shù)值度

5、量是(算術(shù))均值(mean)。2設(shè)x1, x2, xN是N個值的集合，則該值集的均值定義為： 截斷均值：指定0和100間的百分位數(shù)p，丟棄高端和低端(p/2)%的數(shù)據(jù)，然后用常規(guī)方法計算均值，所得的結(jié)果即是截斷均值。中位數(shù)是p=100%時的截斷均值，而標(biāo)準(zhǔn)均值是對應(yīng)于p=0%的截斷均值。例：計算1,2,3,4,5,90值集的均值，中位數(shù)和p=40%的截斷均值.解：均值是17.5，中位數(shù)是3.5，p=40%時的截斷均值也是3.5 數(shù)據(jù)預(yù)處理n 數(shù)據(jù)清理n 數(shù)據(jù)集成n 數(shù)據(jù)變換n 數(shù)據(jù)歸約n 數(shù)據(jù)離散化數(shù)據(jù)清理噪聲數(shù)據(jù)的平滑方法n 目前噪聲數(shù)據(jù)的平滑方法包括：n 分箱：分箱方法通過考察“鄰居”(即

6、周圍的值)來平滑有序數(shù)據(jù)的值。n 聚類：聚類將類似的值組織成群或“簇”。n 回歸：讓數(shù)據(jù)適合一個函數(shù)來平滑數(shù)據(jù)。數(shù)據(jù)平滑實例n 一組排序后的數(shù)據(jù)(單位：元)：4，8，15，21，21，24，25，28，34n 劃分為等深的箱q 箱1：4，8，15q 箱2：21，21，24q 箱3：25，28，34n 用箱平均值進(jìn)行平滑q 箱1：9，9，9（下同）n 用箱的邊界進(jìn)行平滑q 箱1：4，4，15q 箱2：21，21，24q 箱3：25，25，34數(shù)據(jù)變換規(guī)范化n 最小-最大規(guī)范化：，優(yōu)點(diǎn)：計算簡單n Z-score規(guī)范化: , 是均值，為標(biāo)準(zhǔn)差n 小數(shù)定標(biāo)規(guī)范化: 離散屬性間的相關(guān)性計算q 離散型數(shù)

7、據(jù)間相關(guān)性計算（互信息）n 特征x的信息熵n 已知變量y后x的條件信息熵n 信息增益數(shù)據(jù)對象之間的相異度n 距離：q 歐幾里得距離其中，n的維數(shù)（總特征數(shù)），Xk和Yk分別表示X和Y的第k個分量q 閔可夫斯基(Minkowski )距離q x=1,城市塊（曼哈頓）距離q x=2,歐幾里得距離q x=,切比雪夫(Chebyshev)距離 二值屬性n 二元數(shù)據(jù)相似性度量M01 = x取0并且y取1的屬性的個數(shù)M10 = x取1并且y取0的屬性的個數(shù)M00 = x取0并且y取0的屬性的個數(shù)M11 = x取1并且y取1的屬性的個數(shù)n 簡單匹配系數(shù)(Simple Matching Coefficient

8、,SMC)： SMC = 值匹配的屬性個數(shù) /屬性個數(shù) = (M11 + M00) / (M01 + M10 + M11 + M00)n Jaccard系數(shù)J = 匹配的個數(shù) /不涉及0-0匹配的屬性個數(shù) = (M11) / (M01 + M10 + M11) 例子X = （1 0 0 0 0 0 0 0 0 0） Y= （ 0 0 0 0 0 0 1 0 0 1） M01 = 2 (x取0并且y取1的屬性的個數(shù)) M10 = 1 (x取1并且y取0的屬性的個數(shù)) M00 = 7 (x取0并且y取0的屬性的個數(shù)) M11 = 0 (x取1并且y取1的屬性的個數(shù)) SMC = (M11 + M0

9、0)/(M01 + M10 + M11 + M00) = (0+7) / (2+1+0+7) = 0.7 J = M11 / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0 2.18以下表格包含了屬性name，gender，trait-1，trait-2，trait-3，及trait-4，這里的name是對象的id，gender是一個對稱的屬性，剩余的trait屬性是不對稱的，描述了希望找到的筆友的個人特點(diǎn)。假設(shè)有一個服務(wù)是試圖發(fā)現(xiàn)合適的筆友。對 不對稱的屬性的值，值P被設(shè)為1，值N被設(shè)為0。假設(shè)對象(潛在的筆友)間的距離是基于不對稱變量來計算的。(a) 計算對

10、象間的簡單匹配系數(shù)；SMC(Keavn,Caroline)=(2+2)/(0+0+2+2)=1SMC(Keavn,Erik)=(0+0)/(2+2+0+0)=0SMC(Caroline,Erik)=(0+0)/(2+2+0+0)=0(b) 計算對象間的Jaccard系數(shù)；Jaccard(Keavn,Caroline)=2/(2+0+0)=1Jaccard(Keavn,Erik)=0/(0+2+2)=0Jaccard(Caroline,Erik)=0/(0+2+2)=0(c) 你認(rèn)為哪兩個人將成為最佳筆友？哪兩個會是最不能相容的？根據(jù)屬性的匹配程度，Keavn和Caroline將成為最佳筆友，C

11、aroline和Erik會是最不能相容的（d）假設(shè)我們將對稱變量gender包含在我們的分析中?；贘accard系數(shù)，誰將是最和諧的一對？為什么？若將對稱變量gender包含在分析中，設(shè)值M被設(shè)為1，值F被設(shè)為0，Jaccard(Keavn,Caroline)=2/(2+1+0)=2/3Jaccard(Keavn,Erik)=1/(1+2+2)=1/5Jaccard(Caroline,Erik)=0/(0+2+3)=0因為Jaccard(Keavn,Caroline)最大，因此，Keavn和Caroline是最和諧的一對。第三章分類的定義q 分類是數(shù)據(jù)挖掘中的一種主要分析手段q 分類的任務(wù)是

12、對數(shù)據(jù)集進(jìn)行學(xué)習(xí)并構(gòu)造一個擁有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類標(biāo)號，如：分類與回歸的區(qū)別q 分類和回歸都有預(yù)測的功能，但是：n 分類預(yù)測的輸出為離散或標(biāo)稱的屬性；n 回歸預(yù)測的輸出為連續(xù)屬性值；q 分類與回歸的例子：n 預(yù)測未來某銀行客戶會流失或不流失，這是分類任務(wù)；n 預(yù)測某商場未來一年的總營業(yè)額，這是回歸任務(wù)。分類與聚類的區(qū)別q 分類因為使用了類標(biāo)號屬性，屬于有監(jiān)督的學(xué)習(xí)方法q 聚類，事先沒有使用任何類標(biāo)號信息，屬于無監(jiān)督的學(xué)習(xí)方法決策樹的基本概念n 決策樹(Decision Tree)是一種樹型結(jié)構(gòu)，包括：決策節(jié)點(diǎn)(內(nèi)部節(jié)點(diǎn))、分支和葉節(jié)點(diǎn)三個部分。n 其中：q 決策節(jié)點(diǎn)代表某個

13、測試，通常對應(yīng)于待分類對象的某個屬性，在該屬性上的不同測試結(jié)果對應(yīng)一個分支。q 葉節(jié)點(diǎn)存放某個類標(biāo)號值，表示一種可能的分類結(jié)果。q 分支表示某個決策節(jié)點(diǎn)的不同取值。q 決策樹可以用來對未知樣本進(jìn)行分類，分類過程如下：從決策樹的根節(jié)點(diǎn)開始，從上往下沿著某個分支往下搜索，直到葉結(jié)點(diǎn)，以葉結(jié)點(diǎn)的類標(biāo)號值作為該未知樣本所屬類標(biāo)號。 決策樹的屬性選擇n 雖然可以采用任何一個屬性對數(shù)據(jù)集進(jìn)行劃分，但最后形成的決策樹會差異很大。需要尋找合適的屬性選擇方法。n 屬性選擇是決策樹算法中重要的步驟，常見的屬性選擇標(biāo)準(zhǔn)包括信息增益和Gini系數(shù)。q 信息增益是決策樹常用的分枝準(zhǔn)則,在樹的每個結(jié)點(diǎn)上選擇具有最高信息增

14、益的屬性作為當(dāng)前結(jié)點(diǎn)的劃分屬性。q Gini系數(shù)是一種不純度函數(shù)，用來度量數(shù)據(jù)集的數(shù)據(jù)關(guān)于類的純度。獲得大小合適的樹n 決策樹學(xué)習(xí)的目的是希望生成能夠揭示數(shù)據(jù)集結(jié)構(gòu)并且預(yù)測能力強(qiáng)的一棵樹，在樹完全生長的時候有可能預(yù)測能力反而降低，為此通常需要獲得大小合適的樹。n 一般來說有兩種獲取方法:q 一種為定義樹的停止生長條件,常見條件包括最小劃分實例數(shù)、劃分閾值和最大樹深度等。q 另一種方法是對完全生長決策樹進(jìn)行剪枝，方法是對決策樹的子樹進(jìn)行評估，若去掉該子樹后整個決策樹表現(xiàn)更好，則該子樹將被剪枝。ID3分類算法n 它使用信息增益(information gain)作為屬性的選擇標(biāo)準(zhǔn)。q 首先檢測所有

15、的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一個類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來對新的樣本進(jìn)行分類。n 與ID3分類算法相關(guān)的基本概念包括：q 信息熵：用來度量一個屬性的信息量。假定S為訓(xùn)練集，S的目標(biāo)屬性C具有m個可能的類標(biāo)號值，C=C1,C2,Cm，假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為 (i=1,2,3,m)，則該訓(xùn)練集S所包含的信息熵定義為：熵越小表示樣本對目標(biāo)屬性的分布越純，反之熵越大表示樣本對目標(biāo)屬性分布越混亂。 信息熵例題n 考慮數(shù)據(jù)集weather如下, 求

16、weather數(shù)據(jù)集關(guān)于目標(biāo)屬性play ball的熵。n 解答：令weather數(shù)據(jù)集為S，其中有14個樣本,目標(biāo)屬性play ball有2個值C1=yes, C2=no。14個樣本的分布為：q 9個樣本的類標(biāo)號取值為yes，5個樣本的類標(biāo)號取值為No。C1=yes在所有樣本S中出現(xiàn)的概率為9/14，C2=no在所有樣本S中出現(xiàn)的概率為5/14。q 因此數(shù)據(jù)集S的熵為：q信息增益信息增益是劃分前樣本數(shù)據(jù)集的不純程度(熵)和劃分后樣本數(shù)據(jù)集的不純程度(熵)的差值q 假設(shè)劃分前樣本數(shù)據(jù)集為S,并用屬性A來劃分樣本集S，則按屬性A劃分S的信息增益Gain(S,A)為樣本集S的熵減去按屬性A劃分S后

17、的樣本子集的熵：按屬性A劃分S后的樣本子集的熵定義如下：假定屬性A有k個不同的取值，從而將S劃分為k個樣本子集S1,S2,Sk，則按屬性A劃分S后的樣本子集的信息熵為:其中|Si|(i,=1,2,k)為樣本子集Si中包含的樣本數(shù)，|S|為樣本集S中包含的樣本數(shù)。信息增益越大，說明使用屬性A劃分后的樣本子集越純，越有利于分類。信息增益例題n 以數(shù)據(jù)集weather為例，設(shè)該數(shù)據(jù)集為S，假定用屬性wind來劃分S，求S對屬性wind的信息增益。 n 解答：q (1)首先由前例計算得到數(shù)據(jù)集S的熵值為0.94；q (2)屬性wind有2個可能的取值weak,strong，它將S劃分為2個子集：S1,

18、S2,S1為wind屬性取值為weak的樣本子集，共有8個樣本；S2為wind屬性取值為strong的樣本子集，共有6個樣本；下面分別計算樣本子集S1和S2的熵。對樣本子集S1，play ball=yes的有6個樣本，play ball=no的有2個樣本，則：對樣本子集S2，play ball=yes的有3個樣本，play ball=no的有3個樣本，則：n 利用屬性wind劃分S后的熵為：n 按屬性wind劃分?jǐn)?shù)據(jù)集S所得的信息增益值為：ID3建樹算法n 以weather數(shù)據(jù)集為例，講解ID3的建立過程。數(shù)據(jù)集的構(gòu)成n 數(shù)據(jù)集具有屬性：outlook, temperature, humidi

19、ty, wind. n outlook = sunny, overcast, rain n temperature = hot, mild, cool n humidity = high, normal n wind = weak, strong ID3建立決策樹n 首先計算總數(shù)據(jù)集S對所有屬性的信息增益，尋找根節(jié)點(diǎn)的最佳分裂屬性:n Gain(S, outlook) = 0.246n Gain(S, temperature) = 0.029n Gain(S, humidity) = 0.152n Gain(S, wind) = 0.049 n 顯然，這里outlook屬性具有最高信息增益值，

20、因此將它選為根結(jié)點(diǎn). n 以outlook做為根結(jié)點(diǎn)，繼續(xù)往下：n 思想是，以outlook的可能取值建立分支，對每個分支遞歸建立子樹。n 因為outlook有3個可能值,因此對根結(jié)點(diǎn)建立3個分支sunny, overcast, rain.n 首先對outlook的sunny分支建立子樹。q 找出數(shù)據(jù)集中outlook = sunny的樣本子集Soutlook=sunny，然后依次計算剩下三個屬性對該樣本子集Ssunny劃分后的信息增益：n Gain(Ssunny, humidity) = 0.971n Gain(Ssunny, temperature) = 0.571n Gain(Ssunn

21、y, wind) = 0.371顯然humidity具有最高信息增益值，因此它被選為outlook結(jié)點(diǎn)下sunny分支下的決策結(jié)點(diǎn)n 采用同樣的方法，依次對outlook的overcast分支、rain分支建立子樹，最后得到一棵可以預(yù)測類標(biāo)號未知的樣本的決策樹。ID3算法總結(jié)n ID3算法是所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。n ID3搜索的假設(shè)空間是可能的決策樹的集合，搜索目的是構(gòu)造與訓(xùn)練數(shù)據(jù)一致的一棵決策樹，搜索策略是爬山法，在構(gòu)造決策樹時從簡單到復(fù)雜，用信息熵作為爬山法的評價函數(shù)。n ID3算法的核心是在決策樹各級結(jié)點(diǎn)上選擇屬性，用信息增益作為屬性選擇的標(biāo)準(zhǔn)，使得在每個非

22、葉節(jié)點(diǎn)進(jìn)行測試時能獲得關(guān)于被測數(shù)據(jù)最大的類別信息，使得該屬性將數(shù)據(jù)集分成子集后，系統(tǒng)的熵值最小。C4.5分類算法n 基于ID3算法中存在的不足，Quinlan于1993年對其做出改進(jìn)，提出了改進(jìn)的決策樹分類算法C4.5，該算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾個方面對ID3算法進(jìn)行了改進(jìn)：q (1)能夠處理連續(xù)型屬性數(shù)據(jù)和離散型屬性數(shù)據(jù)；q (2)能夠處理具有缺失值的數(shù)據(jù)；q (3)使用信息增益率作為決策樹的屬性選擇標(biāo)準(zhǔn)；q (4)對生成的樹進(jìn)行剪枝處理，以獲取簡略的決策樹；q (5)從決策樹到規(guī)則的自動產(chǎn)生。C4.5算法的概念描述假定S為訓(xùn)練集，目標(biāo)屬性C具有m個可能的取值，C=C1,C2,

23、Cm，即訓(xùn)練集S的目標(biāo)屬性具有m個類標(biāo)號值C1,C2,Cm，C4.5算法所涉及的概念描述如下：n (1)假定訓(xùn)練集S中，Ci在所有樣本中出現(xiàn)的頻率為pi(i=1,2,3,m)，則該集合S所包含的信息熵為：n (2)設(shè)用屬性A來劃分S中的樣本,計算屬性A對集合S的劃分熵值EntropyA(S)定義如下:若屬性A為離散型數(shù)據(jù)，并具有k個不同的取值,則屬性A依據(jù)這k個不同取值將S劃分為k個子集S1,S2,Sk，屬性A劃分S的信息熵為其中|Si|和|S|分別是Si和S中包含的樣本個數(shù)。如果屬性A為連續(xù)型數(shù)據(jù)，則按屬性A的取值遞增排序，將每對相鄰值的中點(diǎn)看作可能的分裂點(diǎn)，對每個可能的分裂點(diǎn)，計算：其中S

24、L和SR分別對應(yīng)于該分裂點(diǎn)劃分的左右兩部分子集，選擇EntropyA(S)值最小的分裂點(diǎn)作為屬性A的最佳分裂點(diǎn)，并以該最佳分裂點(diǎn)按屬性A對集合S的劃分熵值作為屬性A劃分S的熵值。n (3) C4.5以信息增益率作為選擇標(biāo)準(zhǔn)，不僅考慮信息增益的大小程度，還兼顧為獲得信息增益所付出的“代價”：n C4.5通過引入屬性的分裂信息來調(diào)節(jié)信息增益，分裂信息定義為q 信息增益率定義為q 這樣如果某個屬性有較多的分類取值，則它的信息熵會偏大，但信息增益率由于考慮了分裂信息而降低，進(jìn)而消除了屬性取值數(shù)目所帶來的影響。 C4.5算法演示n 以weather數(shù)據(jù)集為例，演示C4.5算法對該數(shù)據(jù)集進(jìn)行訓(xùn)練，建立一棵

25、決策樹的過程，對未知樣本進(jìn)行預(yù)測。Step1:計算所有屬性劃分?jǐn)?shù)據(jù)集S所得的信息增益分別為(參考ID3例題演示):Step2:計算各個屬性的分裂信息和信息增益率q 以outlook屬性為例，取值為overcast的樣本有4條，取值為rain的樣本有5條，取值為sunny的樣本有5條：q 同理依次計算其它屬性的信息增益率分別如下：Step3:取值信息增益率最大的那個屬性作為分裂結(jié)點(diǎn)，因此最初選擇outlook屬性作為決策樹的根結(jié)點(diǎn)，產(chǎn)生3個分支，如下：Step4:對根結(jié)點(diǎn)的不同取值的分支，遞歸調(diào)用以上方法，求子樹，最后通過C4.5獲得的決策樹為貝葉斯分類方法q 貝葉斯分類方法是一種基于統(tǒng)計的學(xué)習(xí)

26、方法。q 是一種利用概率統(tǒng)計知識進(jìn)行學(xué)習(xí)分類的方法。n 如：預(yù)測一個數(shù)據(jù)對象屬于某個類別的概率。n 如：計算郵件是垃圾郵件或合法郵件的概率，取概率大的為預(yù)測結(jié)果q 主要算法有：n 樸素貝葉斯分類算法n 貝葉斯信念網(wǎng)絡(luò)分類算法等。貝葉斯定理n 假定X為類標(biāo)號未知的一個數(shù)據(jù)樣本，H為樣本X屬于類別C的一個假設(shè)q 分類問題就是計算概率P(H|X) 的問題，即給定觀察樣本X下假設(shè)H成立的概率有多大。q 這里：n P(H)表示假設(shè)H的先驗概率(prior probability)。n P(X)表示樣本數(shù)據(jù)X的先驗概率。n P(H|X)表示在條件X下，假設(shè)H的后驗概率(posterior probabil

27、ity)。n P(X|H)表示在給定假設(shè)H的前提條件下，樣本X的后驗概率例:n 假設(shè)數(shù)據(jù)集由三個屬性構(gòu)成：q 年齡、收入、是否購買計算機(jī)q 樣本X為：35, 4000, ?q 假設(shè)H為：顧客將購買計算機(jī)。q 則：n P(H)表示任意給定的顧客將購買計算機(jī)的概率，而不考慮年齡、收入其它信息。n P(X)表示數(shù)據(jù)集中，樣本年齡為35，工資為4000的概率。n P(H|X)表示已知顧客的年齡和收入分別為35和4000，顧客購買計算機(jī)的概率。n P(X|H)表示已知顧客購買計算機(jī)，顧客年齡和收入屬性值為35和4000的概率。 n 假設(shè)X,Y是一對隨機(jī)變量，它們的：q 聯(lián)合概率P（X=x,Y=y）是指X

28、取值x且Y取值y的概率q 條件概率是指一隨機(jī)變量在另一隨機(jī)變量取值已知的情況下取某一個特定值的概率。n 例如P(Y=y|X=x）是指在變量X取值x的情況下，變量Y取值y的概率)。n 貝葉斯定理是指X和Y的聯(lián)合概率和條件概率滿足如下關(guān)系：n 例：考慮A和B兩隊之間的足球比賽：假設(shè)過去的比賽中，65%的比賽A對取勝，35%的比賽B對取勝。A對勝的比賽中只有30%是在B對的主場，B對取勝的比賽中75%是在主場。n 如果下一場比賽在B對的主場進(jìn)行，請預(yù)測哪支球隊最有可能勝出？解答：根據(jù)貝葉斯定理,假定n 隨機(jī)變量X代表東道主，X取值范圍為A,Bn 隨機(jī)變量Y代表比賽的勝利者，取值范圍為A,B。n 已知

29、：n A對取勝的概率為0.65，表示為：P(Y=A)=0.65，n B對取勝的概率為0.35 ，表示為：P(Y=B)=0.35，n B對取勝時作為東道主的概率是0.75，表示為：P(X=B|Y=B) = 0.75,n A對取勝時B對作為東道主的概率是0.3,表示為:P(X=B|Y=A) = 0.3,n 計算：n 下一場比賽在B對主場，同時A對勝出的概率表示為：P(Y=A|X=B)q P(Y=A|X=B) = P(X=B|Y=A)*P(Y=A)/P(X=B) = (0.3*0.65)/0.4575=0.4262n 下一場比賽在B對主場，同時B對勝出的概率表示為：P(Y=B|X=B)q P(Y=B

30、|X=B)=P(X=B|Y=B)*P(Y=B)/P(X=B) =(0.75*0.35)/0.4575=0.5737根據(jù)計算結(jié)果，可以推斷出，下一場最有可能是B對勝出P(X=B)的計算 ：q P(X=B)= P(X=B,Y=A)+P(X=B,Y=B) = P(Y=A|X=B)*P(X=B) + P(Y=B|X=B)*P(X=B) = P(X=B|Y=A)*P(Y=A) + P(X=B|Y=B)*P(Y=B) = 0.3*0.65+0.75*0.35=0.195+0.2625 = 0.4575 樸素貝葉斯分類算法n 樸素貝葉斯分類算法利用貝葉斯定理來預(yù)測一個未知類別的樣本屬于各個類別的可能性，選擇

31、其中可能性最大的一個類別作為該樣本的最終類別。樸素貝葉斯分類算法演示例子：對weather數(shù)據(jù)集使用樸素貝葉斯算法預(yù)測未知樣本X=rainy,hot,normal,false,?的play ball類標(biāo)號屬性的值。n 該問題描述如下：n 樣本X=rainy, hot, normal, false, ?n 類標(biāo)號play ball有2個取值yes, non 題目即求:n 樣本X在play為yes的概率P(play=yes|X)n 和樣本在play為no的概率P(play=no|X)n 樣本X將被預(yù)測為概率值大的那個類。解：根據(jù)樸素貝葉斯定理：P(play=yes|X)=P(X|play=yes)

32、*P(play=yes) =P(x1|play=yes)*P(x2|play=yes)*P(x3|play=yes)*P(x4|play=yes)*P(play=yes)其中：P(x1|play=yes)=P(outlook=rainy|play=yes)=3/9P(x2|play=yes)=P(temperature=hot|play=yes)=2/9P(x3|play=yes)=P(humidity=normal|play=yes)=6/9P(x4|play=yes)=P(windy=false|play=yes)=6/9P(play=yes)=9/14因此：P(play=yes|X)=1

33、/32/92/32/39/14=0.0211 同樣方法計算：P(play=no|X)=P(X|play=no)*P(play=no) =P(x1|play=no)*P(x2|play=no)*P(x3|play=no)*P(x4|play=no)*P(play=no)其中：P(x1|play=no)=P(outlook=rainy|play=no)=2/5P(x2|play=no)=P(temperature=hot|play=no)=2/5P(x3|play=no)=P(humidity=normal|play=no)=1/5P(x4|play=no)=P(windy=false|play=

34、no)=2/5P(play=no)=9/14因此：P(play=no|X)=2/52/51/52/59/14=0.0082 n 根據(jù)計算結(jié)果：q P(play=yes|X) P(play=no|X)n 所以：q 樣本X=rainy,hot,normal,false,?的play類標(biāo)號值應(yīng)為yes.第四章基于劃分的聚類算法給定一個 n 個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個聚類，并且k=n。也就是說，它將數(shù)據(jù)劃分為k個組，同時滿足如下的要求： (1)每個組至少包含一個對象； (2)每個對象必須屬于且只屬于一個組。劃分式聚類算法需要預(yù)先指定簇數(shù)目或簇中心，通過反復(fù)迭

35、代運(yùn)算，逐步降低目標(biāo)函數(shù)的誤差值，當(dāng)目標(biāo)函數(shù)值收斂時，得到最終聚類結(jié)果。這類方法分為基于質(zhì)心的(Centroid-based)劃分方法和基于中心的(Medoid-based)劃分方法基本k-means聚類算法k-means聚類算法：(1)從數(shù)據(jù)集D中任意選擇k個對象作為初始簇中心；(2) repeat(3) for 數(shù)據(jù)集D中每個對象P do(4) 計算對象P到k個簇中心的距離(5) 將對象P指派到與其最近(距離最短)的簇；(6) end for(7) 計算每個簇中對象的均值，做為新的簇的中心；(8) until k個簇的簇中心不再發(fā)生變化 K-means算法采用來表示一個簇k-means聚類

36、算法示例n 例 4.1 對表4-1中二維數(shù)據(jù)，使用k-means算法將其劃分為2個簇，假設(shè)初始簇中心選為P7(4，5)，P10(5，5)。表4-1 k-means聚類過程示例數(shù)據(jù)集1n 解：圖4-2 顯示了對于給定的數(shù)據(jù)集k-means聚類算法的執(zhí)行過程。(1)根據(jù)題目，假設(shè)劃分的兩個簇分別為C1和C2，中心分別為(4，5)和(5，5)，下面計算10個樣本到這2個簇中心的距離，并將10個樣本指派到與其最近的簇：(2)第一輪迭代結(jié)果如下： 屬于簇C1的樣本有：P7，P1，P2，P4，P5，P8 屬于簇C2的樣本有：P10，P3，P6，P9重新計算新的簇的中心，有：C1的中心為(3.5，5.167

37、)，C2的中心為(6.75，4.25)（ 簇中心的計算方式是平均類中所有點(diǎn)）(3)繼續(xù)計算10個樣本到新的簇的中心的距離，重新分配到新的簇中，第二輪迭代結(jié)果如下： 屬于簇C1的樣本有： P1，P2，P4，P5，P7，P10 屬于簇C2的樣本有： P3，P6，P8，P9 重新計算新的簇的中心，有：C1的中心為(3.67，5.83)，C2的中心為(6.5，3.25)(4)繼續(xù)計算10個樣本到新的簇的中心的距離，重新分配到新的簇中，發(fā)現(xiàn)簇中心不再發(fā)生變化，算法終止。K-均值算法練習(xí)給出一個樣本數(shù)據(jù)庫，并對它實施k-均值算法設(shè)n=8,k=2，隨機(jī)選擇序號1和3作為初始點(diǎn)n 設(shè)n=8,k=2n 第一次迭

38、代：假定隨機(jī)選擇兩個對象，如序號1和序號3當(dāng)作初始點(diǎn)，分別找到離兩點(diǎn)最近的對象，并產(chǎn)生兩個簇1,2和3,4,5,6,7,8n 對于產(chǎn)生的簇計算平均值(1.5,1) (3.5,3)n 第二次迭代:根據(jù)平均值調(diào)整對象所在的簇，重新聚類，得到新的簇1,2,3,4和5,6,7,8。重新計算平均值(1.5,1.5) (4.5,3.5)第三次迭代：按平均值重新聚類，簇保持不變，程序結(jié)束K-均值算法應(yīng)用實例n 根據(jù)2005-2010年的戰(zhàn)績，分析中國男足的地位n 其中包括兩次世界杯和一次亞洲杯，提前對數(shù)據(jù)做如下預(yù)處理：對于世界杯，進(jìn)入決賽圈則取其最終排名，沒有進(jìn)入決賽圈的，打入預(yù)選賽十強(qiáng)賽賦予40，預(yù)選賽小

39、組未出現(xiàn)的賦予50。對于亞洲杯，前四名取其排名，八強(qiáng)賦予5，十六強(qiáng)賦予9，預(yù)選賽沒出現(xiàn)的賦予17。這樣做是為了使得所有數(shù)據(jù)變?yōu)闃?biāo)量，便于后續(xù)聚類。n 對數(shù)據(jù)進(jìn)行歸一化：n 用算法進(jìn)行聚類，設(shè)k=3，將15支球隊分為3個集團(tuán)具體步驟：1抽取日本，巴林和泰國的值作為三個簇的種子，即初始化三個簇中心為:A=0.3,0,0.19，B=0.7,0.76,0.5，C=1,1,0.52計算所有球隊分別對三個點(diǎn)的相異度(歐式距離)第一次聚類結(jié)果：A:日本，韓國，伊朗，沙特B:烏茲別克斯坦，巴林，朝鮮C:中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。3 根據(jù)第一次聚類結(jié)果，調(diào)整各個簇的中心點(diǎn)：A簇的中心

40、點(diǎn)為:(0.3+0+0.24+0.3)/4=0.21,(0+0.15+0.76+0.76)/4=0.4175,(0.19+0.13+0.25+0.06)/4=0.1575=0.21,0.4175,0.1575B0.7,0.7333,0.4167C1,0.94,0.40625用調(diào)整后的中心再次聚類，得到：第二次迭代后，結(jié)果無變化，說明結(jié)果已收斂。最終聚類結(jié)果：亞洲一流：日本，韓國，伊朗，沙特亞洲二流：烏茲別克斯坦，巴林，朝鮮亞洲三流：中國，伊拉克，卡塔爾，阿聯(lián)酋，泰國，越南，阿曼，印尼。第五章關(guān)聯(lián)分析的基本概念舉例TIDItems100Cola Egg Ham200Cola Diaper Beer300Cola Diaper Beer Ham400Diaper Beer，T為事務(wù)集合Apriori方法的優(yōu)化策略Apriori算法的例子1n 考慮下面的事務(wù)數(shù)據(jù)庫TIDItems100Cola Egg Ham200Cola Diaper