數(shù)據(jù)挖掘-分類方法(修改)

第四章分類方法小組成員：龐春霞萬凱明委佩濤彭朋內(nèi)容回顧基本概念貝葉斯分類規(guī)則歸納總結(jié)KDD的總體過程數(shù)據(jù)挖掘——知識挖掘的核心數(shù)據(jù)清理數(shù)據(jù)集成數(shù)據(jù)庫數(shù)據(jù)倉庫任務相關(guān)數(shù)據(jù)選擇數(shù)據(jù)挖掘模式評估分類為什么要進行分類？分類是數(shù)據(jù)挖掘中的重要任務之一很多數(shù)據(jù)挖掘問題都可以轉(zhuǎn)化為分類問題分類的目的在于用分類方法構(gòu)建一個分類函數(shù)或分類模型（分類器），該分類器可以將輸入數(shù)據(jù)（數(shù)據(jù)庫中的數(shù)據(jù)項）映射到給定類別中的一個類別。分類器的構(gòu)造依據(jù)統(tǒng)計方法：貝葉斯方法和非參數(shù)法等機器學習方法：決策樹法和規(guī)則歸納法神經(jīng)網(wǎng)絡(luò)方法其他：粗糙集等數(shù)據(jù)分類的兩步過程（1）第一步，建立一個模型，描述預定數(shù)據(jù)類集和概念集假定每個元組屬于一個預定義的類，由一個類標號屬性確定基本概念訓練數(shù)據(jù)集：由為建立模型而被分析的數(shù)據(jù)元組形成訓練樣本：訓練數(shù)據(jù)集中的單個樣本（元組）學習模型可以用分類規(guī)則、判定樹或數(shù)學公式的形式提供第一步——建立模型訓練數(shù)據(jù)集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規(guī)則數(shù)據(jù)分類的兩步過程（2）第二步，使用模型，對將來的或未知的對象進行分類首先評估模型的預測準確率對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比測試集要獨立于訓練樣本集，否則會出現(xiàn)“過分適應數(shù)據(jù)”的情況第二步——用模型進行分類分類規(guī)則測試集未知數(shù)據(jù)(Jeff,Professor,4)Tenured?內(nèi)容回顧基本概念貝葉斯分類規(guī)則歸納總結(jié)樸素貝葉斯分類簡介本質(zhì)是一個分類器（分類模型，分類算法均為一個意思）基礎(chǔ)是概率推理先驗概率：根據(jù)以往經(jīng)驗和分析得到的概率客觀先驗概率：由歷史資料得到主觀先驗概率：由主觀經(jīng)驗得到（水果，圓的，甜的，紅或綠的是蘋果）樸素貝葉斯分類特點：基于獨立假設(shè)需要知道先驗概率按照獲得的信息對先驗概率進行修正分類決策存在錯誤率樸素貝葉斯分類模型樣本域：水果X:紅的和圓的（顏色屬性取值為紅，形狀屬性取值為圓）H:是蘋果（蘋果是一個類別）P(H|X):反應了當知道水果是紅的并且是圓的，則它是蘋果的概率（置信程度）。這是后驗概率P(H):是先驗概率樸素貝葉斯分類過程實例：性別分類問題描述：通過一些測量的特征，包括身高、體重、腳的尺寸，判定一個人是男性還是女性。

樸素貝葉斯分類過程問題數(shù)學表示：類別:可以從C1到Cn，在我們的問題中即C1=男性C2=女性樣本表示：每個數(shù)據(jù)樣本（某元組）用一個n維特征向量X={x1，x2，……，xn}表示，分別描述對n個屬性A1，A2，……，An樣本的n個度量。比如樣本X={x1,x2,x3}={1米73,60千克，20厘米}（分別對應身高體重和腳長三個屬性的度量）分類模型：

第一步得到先驗概率訓練數(shù)據(jù)集：得到先驗概率，按照頻率來算。P(C1)=0.5P(C2)=0.5性別身高(英尺)體重(磅)腳的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第二步預測X屬于具有最高后驗概率的類樸素貝葉斯分類將未知的樣本分配給類Ci（1≤i≤m）當且僅當P(Ci|X)>P(Cj|X)，對任意的j=1，2，…，m，j≠i。這樣，最大化P(Ci|X)。其P(Ci|X)最大的類Ci稱為最大后驗假定。第二步預測X屬于具有最高后驗概率的類在這個性別分類問題中即：比較P(C1|X)和P(C2|X)的值(X={6,130,8})，

采用貝葉斯公式：P(C1|X)=P(X|C1)*P(C1)/P(X)其中

先驗概率P(C1)=0.5 P(X|C1)=?(還未知) P(X)對于所有類來說都是一樣的即P(X)=P(C1)*P(X|C1)+P(C2)*P(X|C2)（全概率公式）所以為了得到最大后驗假定，問題轉(zhuǎn)化為求P(X|C1)的最大值未分類的樣本：性別身高(英尺)體重(磅)腳的尺寸(英寸)Sample（？）61308第三步求P(X|C1)

問題就轉(zhuǎn)換為對P(X|Ci)的最大化（P(X|Ci)常被稱為給定Ci時數(shù)據(jù)X的似然度，而使P(X|Ci)最大的假設(shè)Ci稱為最大似然假設(shè)）。因為類的條件是相互獨立的所以可以用如下公式計算：在我們的問題里面比如X={6英尺，130磅，8英寸}P(X|C1)=P(x1|C1)*P(x2|C1)*P(x3|C1)表示C1時樣本X的似然度第三步求P(X|C1)

xK的值可能有兩種情況：（1）離散值則P(xk|Ci)=sik|si，其中sik是在屬性Ak上具有值xk的類Ci的訓練樣本數(shù)，而si是Ci中的訓練樣本數(shù)x1=6英尺即P(x1|C1)=訓練樣本中身高為6英尺并且屬于男性的樣本數(shù)/男性的樣本數(shù)=1/4；此處這么舉例，是假設(shè)身高的取值都是離散值數(shù)據(jù)性別身高(英尺)體重(磅)腳的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第三步求P(X|C1)

xK的值可能有兩種情況：（2）連續(xù)值如果Ak是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而，

是高斯分布函數(shù)，分別為平均值和標準差。性別身高(英尺)體重(磅)腳的尺寸(英寸)男618012男5.92(5'11")19011男5.58(5'7")17012男5.92(5'11")16510女51006女5.5(5'6")1508女5.42(5'5")1307女5.75(5'9")1509第三步求P(X|C1)

假設(shè)訓練集樣本的特征滿足高斯分布，得到下表：性別均值(身高)方差(身高)均值(體重)方差(體重)均值(腳的尺寸)方差(腳的尺寸)男性5.8553.5033e-02176.251.2292e+0211.259.1667e-01女性5.41759.7225e-02132.55.5833e+027.51.6667e+00性別身高(英尺)體重(磅)腳的尺寸(英寸)Sample（？）61308第三步求P(X|C1)

分別求得類別C1和C2的似然度男性似然度計算項：

女性似然度計算項：男性和女性的似然度：可以看到女性的似然度更大，更具貝葉斯分類模型我們顯然可以得到，女性的后驗概率更大，所以該樣本分類為女性。內(nèi)容回顧基本概念貝葉斯分類規(guī)則歸納總結(jié)常見的采用規(guī)則表示的分類器構(gòu)造方法利用規(guī)則歸納技術(shù)直接生成規(guī)則；利用決策樹方法先生成決策樹，然后再把決策樹轉(zhuǎn)換為規(guī)則；使用粗糙集方法生成規(guī)則；使用遺傳算法中的分類器技術(shù)生成規(guī)則等。規(guī)則歸納規(guī)則歸納有四種策略：減法、加法、先加后減、先減后加策略。減法策略：以具體例子為出發(fā)點，對例子進行推廣或泛化，推廣即減除條件（屬性值）或減除合取項（為了方便，我們不考慮增加析取項的推廣），使推廣后的例子或規(guī)則不覆蓋任何反例。加法策略：起始假設(shè)規(guī)則的條件部分為空（永真規(guī)則），如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項，直到該規(guī)則不再覆蓋反例。規(guī)則歸納先加后減策略：由于屬性間存在相關(guān)性，因此可能某個條件的加入會導致前面加入的條件沒什么作用，因此需要減除前面的條件。先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。典型的規(guī)則歸納算法有AQ、CN2和FOIL等。AQ算法利用覆蓋所有正例，排斥所有反例的思想來尋找規(guī)則。比較典型的有AQ11方法，AQ15方法以及AE5方法。AQR是一個基于最基本AQ算法的歸納算法。很多的算法都采用了基本AQ算法，如AQ11和GEM。但AQR更為簡單，AQ11使用了一種復雜的包括置信度的規(guī)則推導方法。AQ算法AQR為每一個分類推導出一條規(guī)則，每一條規(guī)則形式如下：if<cover>thenpredict<class>在一個屬性上的基本測試被稱為一個選擇值（Selector）。例子：<Cloudy=yes>

<Temp>60>AQR允許測試做{=，≤，≥，≠}AQR算法相關(guān)定義

選擇值（Selector）的合取被稱為復合（Complex），Complexes之間的析取被稱為覆蓋（Cover）。如果一個表達式對某個樣本為真，則我們稱其為對這個樣本的一個覆蓋。這樣，一個空Complex覆蓋所有的樣本，而一個空Cover不覆蓋任何樣本。AQR算法相關(guān)定義

在AQR中，一個新樣本被區(qū)分是看其由哪個規(guī)則推導出來的。

如果該樣本只滿足一條規(guī)則，則這個樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預測的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。AQR算法相關(guān)定義AQR算法描述

算法4-5AQR：輸入：正例樣本POS；反例樣本NEG輸出：覆蓋COVERAQR算法描述（1）COVER=Φ；//初始化COVER為空集Φ（2）WHILECOVERdoesnotcoverallpositiveexamplesinPOSDOBEGIN（3）SelectaSEED；//選取一個種子SEED，例如沒有被COVER覆蓋的一個正樣例（4）CallprocedureSTAR（SEED，NEG）；//產(chǎn)生一個能覆蓋種子而同時排除所有反例的星（5）SelectthebestComplexBESTfromtheSTARaccordingtouser-definedcriteria；//從星中選取一個最好的復合（6）AddBESTasanextradisjucttoCOVER；//把最好的復合與COVER合取，形成新的COVER（7）END（8）RETURNCOVER.AQR算法描述算法4-6STAR：輸入：種子SEED；反例NEG輸出：星STARAQR算法描述（1）初始化STAR為空Complex（2）WHILEoneormoreComplexesinSTARcoverssomenegativeexamplesinNEGBEGIN/*如果STAR中的一個或多個Complex覆蓋NEG中的負樣例*/（3）SelectanegativeexampleEnegcoveredbyaComplexinSTAR；/*選取一個被STAR中的Complex覆蓋的負樣例*/（4）LetEXTENSIONbeallSelectorsthatcoverSEEDbutnotENEG；/*令EXTENSION為那些覆蓋SEED但不覆蓋ENEG的Selectors；*/（5）LetSTARbetheset{x∧y|x∈STAR，y∈EXTENSION}；/*令STAR={x∧y|x∈STAR，y∈EXTENSION}；*/（6）RemoveallComplexesinSTARsubsumedbyotherComplexesinSTAR；/*從STAR中除去被其他Complexes所包含的Complexes；*/（7）RemovetheworstComplexesfromSTARUNTILsizeofSTARislessthanorequaltouser-definedmaximum（maxstar）/*刪除STAR中最壞的Complex直到STAR的大小等于或小于用戶定義的最大數(shù)目maxstar*/（8）END（9）RETURNSTAR./*返回一系列覆蓋SEED但不覆蓋NEG的規(guī)則*/AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機初始化COVER為{}，進入循環(huán)選取SEED={size=巨大型，type=自行車}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取STAR覆蓋的負樣例，如ENEG={size=小型，type=摩托車}EXTENSION為覆蓋SEED，不覆蓋ENEG的選擇EXTENSION包括size=巨大型和type=自行車STAR=STAR={x∧y|x∈STAR，y∈EXTENSION}STAR={size=巨大型∧type=自行車}查看STAR覆蓋的負樣例返回STAR={size=巨大型∧type=自行車}巨大型自行車小型摩托車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機巨大型自行車巨大型摩托車BEST={size=巨大型∧type=自行車}，COVER={size=巨大型∧type=自行車}COVER不能覆蓋到全部的正例選取另一個SEED={size=巨大型，type=摩托車}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取STAR覆蓋的負樣例，如ENEG={size=小型，type=摩托車}EXTENSION包括size=巨大型STAR={size=巨大型}查看STAR覆蓋的負樣例返回STAR={size=巨大型}小型摩托車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機巨大型摩托車BEST={size=巨大型}，將BEST添加到COVER中，COVER={size=巨大型∧type=自行車∨size=巨大型}={size=巨大型}COVER是否覆蓋到全部的正例，若是，算法結(jié)束。輸出規(guī)則：捷安特兩輪車

size=巨大型注意：這里僅生成了分類“捷安特兩輪車”的規(guī)則，需要繼續(xù)調(diào)用算法對其余分類生成相應規(guī)則。AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機初始化COVER為{}，進入循環(huán)選取SEED={size=小型，type=摩托車}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取STAR覆蓋的負樣例，如ENEG={size=巨大型，type=自行車}EXTENSION為覆蓋SEED，不覆蓋ENEG的選擇EXTENSION包含size=小型和type=摩托車

STAR=STAR={x∧y|x∈STAR，y∈EXTENSION}STAR={size=小型∧type=摩托車}查看STAR覆蓋的負樣例返回STAR={size=小型∧type=摩托車}SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通小型摩托車巨大型自行車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機BEST={size=小型∧type=摩托車}，COVER={size=小型∧type=摩托車}COVER不能覆蓋到全部的正例選取另一個SEED={size=小型，type=汽車}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取STAR覆蓋的負樣例，如ENEG={size=小型，type=噴氣式飛機}EXTENSION包括type=汽車STAR={type=汽車}查看STAR覆蓋的負樣例返回STAR={type=汽車}小型噴氣式飛機SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通小型摩托車小型汽車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機BEST={type=汽車}，將BEST添加到COVER中，COVER={size=小型∧type=摩托車∨type=汽車}COVER是否覆蓋到全部的正例，若是，算法結(jié)束。輸出規(guī)則：大眾交通

size=小型∧type=摩托車∨type=汽車SizeTypeClass小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通小型汽車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通初始化COVER為{}，進入循環(huán)選取SEED={size=微小型，type=噴氣式飛機}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取ENEG={size=巨大型，type=自行車}同理可得STAR={size=微小型∧type=噴氣式飛機}查看STAR覆蓋的負樣例返回STAR={size=微小型∧type=噴氣式飛機}SizeTypeClass微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機微小型噴氣式飛機巨大型自行車AQR算法舉例假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通BEST={size=微小型∧type=噴氣式飛機}，COVER={size=微小型∧type=噴氣式飛機}COVER不能覆蓋到全部的正例選取另一個SEED={size=小型，type=噴氣式飛機}調(diào)用STAR（SEED,NEG）初始化STAR為{}，進入循環(huán)選取ENEG={size=小型，type=摩托車}EXTENSION包括type=噴氣式飛機STAR={type=噴氣式飛機}查看STAR覆蓋的負樣例返回STAR={type=噴氣式飛機}SizeTypeClass微小型噴氣式飛機快速飛機小型噴氣式飛機快速飛機中型噴氣式飛機快速飛機微小型噴氣式飛機小型噴氣式飛機小型摩托車假設(shè)現(xiàn)有一個訓練集，其包含兩種屬性：size（屬性值：微小型，小型，中型，大型，巨大型，龐大型）type（屬性值：自行車，摩托車，汽車，噴氣式飛機，滑翔機）正例樣本：反例樣本：AQR算法舉例SizeTypeClass巨大型自行車捷安特兩輪車巨大型摩托車捷安特兩輪車小型摩托車大眾交通小型汽車大眾交通中型汽車大眾交通BEST={type=噴氣式飛機}，將BEST添加到COVER中，COVER={size=微小型∧type=噴氣式飛機∨