1、Part7_0 Classification共二十八頁分類是數(shù)據(jù)挖掘的基本功能之一。分類問題是一個普遍存在的問題，有許多不同的應(yīng)用：根據(jù)Email的標題和內(nèi)容過濾垃圾郵件根據(jù)核磁共振掃描的結(jié)果區(qū)分腫瘤是良性或惡性信用分級、市場調(diào)查(dio ch)、圖像模式識別 一、分類(fn li)概述共二十八頁1、分類(fn li)的任務(wù)與目的分類的任務(wù)是通過分析由已知類別數(shù)據(jù)對象組成的訓練數(shù)據(jù)集，建立描述并區(qū)分數(shù)據(jù)對象類別的分類函數(shù)或分類模型（也常常(chngchng)稱作分類器）。分類的目的是利用分類模型把未知類別數(shù)據(jù)對象映射到各定的類別中。共二十八頁AgeSalaryClass30highc125hi

2、ghc221lowc243highc118lowc233lowc1描述(mio sh)屬性類別(libi)屬性分類問題使用的數(shù)據(jù)集格式：描述屬性可以是連續(xù)型屬性，也可以是離散型屬性；而類別屬性必須是離散型屬性。 共二十八頁共二十八頁分類可用于預(yù)測。從歷史數(shù)據(jù)記錄(jl)中自動推導(dǎo)出對給定數(shù)據(jù)的推廣描述，從而能對未來數(shù)據(jù)進行類預(yù)測。數(shù)據(jù)分類與數(shù)值預(yù)測都是預(yù)測問題，都是首先通過分析訓練數(shù)據(jù)集建立模型，然后利用模型預(yù)測數(shù)據(jù)對象。2、分類(fn li)與預(yù)測共二十八頁2、分類(fn li)與預(yù)測的區(qū)別在數(shù)據(jù)挖掘中，如果預(yù)測目標(mbio)是數(shù)據(jù)對象在類別屬性（離散屬性）上的取值（類別），則稱為分類；如

3、果預(yù)測目標(mbio)是數(shù)據(jù)對象在預(yù)測屬性（連續(xù)屬性）上的取值或取值區(qū)間，則稱為預(yù)測。 例如，對100名男女進行體檢，測量了身高和體重，但是事后發(fā)現(xiàn)，a和b兩人忘了填寫性別，c和d兩人漏了記錄體重?，F(xiàn)在根據(jù)其他96人的情況，推斷a和b兩人的性別是分類，而估計c和d兩人的體重是預(yù)測。共二十八頁3、分類(fn li)定義 給定一個數(shù)據(jù)庫 D=t1，t2，tn和一組類 C=C1，Cm，分類問題是去確定一個映射(yngsh) f: DC，使得每個元組ti被分配到一個類中。一個類Cj 包含映射到該類中的所有元組，即Cj = ti | f(ti) = Cj，1 i n， 而且ti D。例如，把學生的百分制

4、分數(shù)分成A、B、C、D、E五類，就是一個分類問題： D是包含百分制分數(shù)在內(nèi)的學生信息， C=A、B、C、D、E。解決分類問題的關(guān)鍵是構(gòu)造一個合適的分類器：從數(shù)據(jù)庫到一組類別集的映射。一般地，這些類是被預(yù)先定義的、非交疊的。共二十八頁1建立一個模型，描述預(yù)定的數(shù)據(jù)(shj)類集或概念集4、分類(fn li)的過程2使用模型進行分類首先評估模型（分類法）的預(yù)測準確率。如果認為模型的準確率可以接受，就可以用它對類標號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。共二十八頁Step1： 模型(mxng)的構(gòu)建4、分類(fn li)的過程共二十八頁Step2：利用模型(mxng)分類4、分類(fn li)的過程共二十八

5、頁 有指導(dǎo)(zhdo) vs.無指導(dǎo)的學習有指導(dǎo)的學習 (分類)指導(dǎo): 訓練數(shù)據(jù)是已經(jīng)被標注好類標號的數(shù)據(jù)，用來(yn li)進行有指導(dǎo)的分類。新數(shù)據(jù)是基于訓練集進行分類的。無指導(dǎo)的學習 (聚類)訓練數(shù)據(jù)的類標號不可知是觀察式學習共二十八頁分類器的構(gòu)造依據(jù)的方法很廣泛：近鄰分類機器學習方法：包括(boku)決策樹法和規(guī)則歸納法統(tǒng)計方法：包括貝葉斯法和非參數(shù)法等神經(jīng)網(wǎng)絡(luò)方法遺傳算法SVM粗糙集 5、分類(fn li)的方法共二十八頁6、分類模型(mxng)的評價準則給定測試集Xtest=(xi,yi)|i=1,2,NN表示測試集中的樣本個數(shù)xi表示測試集中的數(shù)據(jù)樣本yi表示數(shù)據(jù)樣本xi的類標號對

6、于(duy)測試集的第j個類別，假設(shè)被正確分類的樣本數(shù)量為TPj被錯誤分類的樣本數(shù)量為FNj其他類別被錯誤分類為該類的樣本數(shù)據(jù)量為FPj共二十八頁精確度：代表測試集中被正確(zhngqu)分類的數(shù)據(jù)樣本所占的比例 6、常用的評價(pngji)準則精確度/準確率共二十八頁混淆矩陣(j zhn)是另外一種表示分類準確率的方法。顯然，最好解決方案是對角線以外的值全為零。預(yù)測的類類=1類=2實 際 的 類類=1TP1FN1/FP2類=2FN2/FP1TP2共二十八頁6、常用(chn yn)的評價準則查全率和查準率查全率：表示(biosh)在本類樣本中被正確分類的樣本所占的比例 查準率：表示被分類為該類

7、的樣本中，真正屬于該類的樣本所占的比例 共二十八頁6、常用的評價(pngji)準則F-measureF-measure：是查全率和查準率的組合(zh)表達式是可以調(diào)節(jié)的，通常取值為1 共二十八頁6、常用(chn yn)的評價準則G-mean（幾何均值）幾何均值(jn zh) ：是各個類別的查全率的平方根 共二十八頁 分類器性能(xngnng)的表示分類器性能的表示方法類似信息檢索系統(tǒng)的評價方法，可以采用(ciyng)OC曲線和ROC曲線、混淆矩陣等。定義 給定一個類Cj和一個數(shù)據(jù)庫元組ti，ti可能被分類器判定為屬于Cj或不屬于Cj，其實ti本身可能屬于Cj或不屬于Cj，這樣就會產(chǎn)生如下一些情

8、況：真正: 判定ti在Cj中，實際上的確在其中。假正: 判定ti在Cj中，實際上不在其中。真負: 判定ti不在Cj中，實際上不在其中。假負: 判定ti不在Cj中，實際上的確在其中。在上述定義的基礎(chǔ)上，人們經(jīng)常使用OC曲線和ROC曲線表示“假正”和“真正”的關(guān)系。OC曲線通常用于通信領(lǐng)域來測試誤報率。OC曲線的水平軸一般表示“假正”的百分比，另外一個軸表示“真正”的百分比。共二十八頁預(yù)測的準確率這涉及模型正確地預(yù)測新的或先前未見過的數(shù)據(jù)的類標號的能力速度構(gòu)造模型的速度、利用模型進行分類的速度強壯(qingzhung)性給定噪聲或具有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力可伸縮性當給定大量數(shù)據(jù)時，有效地

9、構(gòu)造模型的能力可解釋性 涉及學習模型提供的理解和洞察的層次7、如何對分類算法進行(jnxng)比較與評估？共二十八頁8、評估(pn )分類模型準確率的方法保持方法（holdout）將已知類別的樣本隨機地劃分為訓練數(shù)據(jù)(shj)集與測試數(shù)據(jù)(shj)集兩個集合，一般，訓練數(shù)據(jù)(shj)集占2/3，測試數(shù)據(jù)(shj)集占1/3。分類模型的建立在訓練數(shù)據(jù)(shj)集上進行，分類模型準確率的評估在測試數(shù)據(jù)(shj)集上進行。k-折交叉確認方法將已知類別的樣本隨機地劃分為大小大致相等的k個子集S1, , Sk，并進行k次訓練與測試。第i次，子集Si作為測試數(shù)據(jù)集，其余子集的并集作為訓練數(shù)據(jù)集。進行k次訓

10、練得到k個分類模型，當利用分類模型對測試樣本或者新樣本進行分類時，可以綜合考慮k個分類模型的分類結(jié)果，將出現(xiàn)次數(shù)最多的分類結(jié)果作為最終的分類結(jié)果。共二十八頁二、基于距離(jl)的分類與一個類中的成員和另一個類中的成員之間的相似性相比，被映射到同一個類中的成員彼此之間被認為是更加相似的。相似性（往往用距離來表征）度量可以用來識別數(shù)據(jù)庫中不同成員之間的“相似程度” ，距離越近，相似性越大，距離越遠，相似性越小。定義 給定一個數(shù)據(jù)庫 D=t1，t2，tn和一組類C=C1，Cm。假定每個元組包括(boku)一些數(shù)值型的屬性值：ti=ti1，ti2，tik，每個類也包含數(shù)值性屬性值：Cj=Cj1，Cj2

11、，Cjk，則分類問題是要分配每個ti到滿足如下條件的類Cj： sim(ti，Cj)=sim(ti，Cl) ，ClC，ClCj共二十八頁 K最近鄰居(ln j)算法（KNN）K Nearest neighbor(KNN)訓練樣本用n維數(shù)值屬性(shxng)描述。每個樣本代表n維空間的一個點。所有的訓練樣本都放在n維模式空間中。給定一個樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的k個訓練樣本。通過計算每個訓練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個訓練數(shù)據(jù)，K個數(shù)據(jù)中哪個類別的訓練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個類別。共二十八頁計算兩個點之間的距離如：Euclidean

12、distance從最近鄰居列表中決定分類的結(jié)果選出k個最近的鄰居中的多數(shù)票的類標號可以根據(jù)距離為每一個投票增加(zngji)權(quán)重共二十八頁算法 K-近鄰分類算法輸入： 訓練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。 輸出(shch)： 輸出(shch)類別c。 （1）N=；（2）FOR each d T DO BEGIN（3） IF |N|K THEN（4） N=Nd； （5） ELSE（6） IF uN such that sim(t，u)sim(t，d) THEN BEGIN （7） N=N-u；（8） N=Nd；（9） END（10）END（11）c=class to which the most uN. 共二十八頁下表中給定了二維數(shù)據(jù)集，屬性“x1”和“x2”用于計算距離(jl)，根據(jù)3-近鄰對數(shù)據(jù)點x1=4，x2=1進行分類。x1x2y15-23+31-34+51-42+12-24-43+55+共二十八頁內(nèi)容摘要Part7_0。一般地，這些類是被預(yù)先定義的、非交疊(jio di)的。如果認為模型的準確率可以接受，就可以用它對類標號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。有指導(dǎo) vs.無指導(dǎo)的學習。其他類別被錯誤分類為該類的樣本