數(shù)據(jù)挖掘第五章分類和預測

分類和預測1什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)分類

vs.預測ECUST--JingZhang2分類:

預測分類標號在分類屬性中的訓練樣本集和值(類標號)的基礎上分類數(shù)據(jù)(建立模型)并使用它分類新數(shù)據(jù)預測:為連續(xù)值函數(shù)建模,預測未知的或缺省值典型應用信譽證實目標市場醫(yī)學診斷性能預測分類—兩步驟處理ECUST--JingZhang3模型構(gòu)造（Modelconstruction）:

描述預先定義好的類別每個元組/樣本被假定為從屬于一個預定義的類別，即類標號屬性（classlabelattribute）用于構(gòu)造模型的元組集合被稱之為訓練集合（trainingset）模型可以有多種表示方法，諸如分類規(guī)則，決策樹，或者數(shù)學公式等分類—兩步驟處理使用模型進行分類:在將來對未知對象進行分類估算模型的準確度各元組的已知分類標簽和從模型中獲得的標簽進行比較準確度即樣本集合中能夠被該模型正確分類的元組的百分比測試集合（Testset）和訓練集合（trainingset）獨立,否則無法正確衡量模型的準確度如果準確度是可接受的，則可以使用該模型對未被分類的數(shù)據(jù)元組進行分類ECUST--JingZhang4分類過程：構(gòu)造模型ECUST--JingZhang5訓練數(shù)據(jù)分類算法IFrank=‘professor’ORyears>6THENBonus=‘yes’分類規(guī)則分類過程：使用模型進行預測ECUST--JingZhang6分類規(guī)則測試數(shù)據(jù)新數(shù)據(jù)(Jeff,Professor,4)Bonus?有監(jiān)督學習vs無監(jiān)督學習

Supervisedvs.UnsupervisedLearningECUST--JingZhang7有監(jiān)督學習（Supervisedlearning(classification)）有監(jiān)督（Supervision）:訓練數(shù)據(jù)均含有一個字段，該字段用于表明各個元組所屬的類別新數(shù)據(jù)在訓練集的基礎上進行分類無監(jiān)督學習（Unsupervisedlearning(clustering)）訓練數(shù)據(jù)集合中并不含有一個表征各個元組類別的字段（訓練集的類標號未知）給定一個度量或者觀測值集，意在確定數(shù)據(jù)中類或聚類的存在分類和預測8什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)關(guān)于分類和預測的問題：數(shù)據(jù)準備ECUST--JingZhang9數(shù)據(jù)清理消除噪聲，處理空缺值相關(guān)性分析（特征選擇）刪除不相關(guān)的或者多余的屬性數(shù)據(jù)變換與歸約概化和/或規(guī)格化數(shù)據(jù)分類和預測的問題：評估分類模型ECUST--JingZhang10準確率速度構(gòu)造模型的時間使用模型的時間魯棒性處理噪聲和缺失值的能力可伸縮性涉及給定大量數(shù)據(jù)，有效地構(gòu)造模型的能力可解釋性涉及到學習模型提供的理解和洞察的水平分類和預測11什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)用決策樹歸納分類12決策樹一個類似于流程圖的樹結(jié)構(gòu)內(nèi)部節(jié)點表示一個屬性上的測試每個分支代表一個測試的輸出葉結(jié)點代表類或類分布決策樹生成決策樹的生成包括兩個過程樹的構(gòu)建首先所有的訓練樣本都在根結(jié)點基于所選的屬性循環(huán)的劃分樣本樹剪枝識別和刪除那些反應映噪聲或離群點的分支決策樹的使用:為一個未知的樣本分類在決策樹上測試樣本的屬性值ECUST--JingZhang13訓練數(shù)據(jù)集合ECUST--JingZhang14其中：Buys_computer是類別標簽輸出：一個針對“buys_computer”的決策樹ECUST--JingZhang15age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40決策樹歸納算法ECUST--JingZhang16基本算法

(貪心算法)按照自頂向下遞歸劃分的方法構(gòu)造決策樹（top-downrecursivedivide-and-conquermanner）最開始，所有的訓練樣本均在根結(jié)點樣本基于被選擇的屬性被遞歸劃分(所有屬性都是分類的,若屬性值連續(xù)，則首先要進行離散化處理)測試屬性的選擇基于啟發(fā)式規(guī)則或者統(tǒng)計度量（例如信息增益（informationgain）)終止劃分的條件給定結(jié)點的所有樣本屬于同一類沒有更多的屬性用于再次劃分沒有剩余的樣本決策樹歸納算法17ID3算法樹以代表訓練樣本的單個結(jié)點開始，如果所有樣本都屬于同一個類，則該結(jié)點成為樹葉，并用該類標號。否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息，選擇能夠最好地將樣本分類的屬性，使該屬性成為該結(jié)點的“測試”或“判定”屬性。對測試屬性的每個已知值，創(chuàng)建一個分枝，并據(jù)此劃分樣本。算法使用同樣的過程，遞歸地形成每個劃分上的樣本決策樹。一旦一個屬性出現(xiàn)在一個結(jié)點上，該結(jié)點的任何后代均不該考慮該屬性。遞歸劃分步驟僅當滿足下列條件之一時停止：給定結(jié)點的所有樣本屬于同一類。沒有剩余屬性可以用來進一步劃分樣本。在此情況下，使用多數(shù)表決。這涉及將給定的結(jié)點轉(zhuǎn)換成樹葉，并用樣本中多數(shù)所在的類標記它。分枝測試屬性的某一值下沒有樣本。則以樣本中的多數(shù)類創(chuàng)建一個樹葉。

屬性選擇度量ECUST--JingZhang18屬性選擇度量是一種選擇分裂準則，將給定的類標記的訓練元組的數(shù)據(jù)劃分D“最好”地分成個體類的啟發(fā)式方法。三種流行的屬性選擇度量信息增益增益率Gini指標信息增益信息增益選擇具有最高信息增益（或最大熵壓縮）的屬性作為當前節(jié)點的測試屬性該方法使得對一個對象分類所需的信息量最小，并確保找到一棵簡單的（但不必是最簡單）樹。所有的屬性值被假定為分類的修正后可以用于連續(xù)屬性ECUST--JingZhang19熵（Entropy）和信息增益ECUST--JingZhang20選擇具有最大信息增益的屬性。設S是s個數(shù)據(jù)樣本的集合。假定類標號屬性具有m個不同的值，定義m個不同類Ci(i=1,...,m)。設si

是類Ci中的樣本數(shù)。對一個給定的樣本分類所需的期望信息如下：其中，pi

是任意樣本屬于Ci的概率，并用si/s估計。熵（Entropy）和信息增益設屬性A共有v個不同值{a1,a2,…,av}，可以用屬性A將S劃分為v個子集{S1,...,Sv}；其中，Sj

包含S中在屬性A上具有值aj的那些樣本。如果A被選作測試屬性，則這些子集對應于由包含集合S的結(jié)點生長出來的分枝。設sij是子集Sj中類Ci的樣本數(shù)，根據(jù)A劃分子集的熵或期望信息由下式給出。

項為第j個子集的權(quán)，并且等于子集（即，A值為aj的樣本集合）中的樣本個數(shù)除以S中的樣本總數(shù)。熵值越小，子集劃分的純度越高。對于給定的子集Sj，其中，是Sj中的樣本屬于Ci的概率。屬性A的信息增益（Informationgain）可如下計算：21通過計算信息增益來選擇屬性ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:

means“age<=30”has5outof14samples,with2yes’esand3no’s.HenceSimilarly,2223為連續(xù)值屬性計算信息增益假定屬性A為連續(xù)值屬性確定A的最佳分裂點將A的值按遞增序排序典型地，每對相鄰值的中點看做可能的分裂點(ai+ai+1)/2是ai

和ai+1之間的中點A具有最小期望信息需求的點選作A的分裂點分裂:D1是滿足A≤split-point的元組集合,而D2是滿足A>split-point的元組的集合增益率信息增益度量偏向于選擇具有大量值的屬性C4.5(ID3的改進)采用增益率來克服這個問題(信息增益的規(guī)范化)GainRatio(A)=Gain(A)/SplitInfo(A)Ex.

gain_ratio(income)=0.029/1.557=0.019具有最大增益率的屬性被選作分裂屬性Gini指標（GiniIndex）數(shù)據(jù)集合D包含來自n類的樣例，gini指標度量數(shù)據(jù)劃分或訓練元組集D的不純度,gini(D)定義如下，

其中pj

是D中元素屬于類

j的概率如果數(shù)據(jù)集合D

被屬性A分裂成兩個子集D1

和

D2,gini

指標

gini(D)定義為不純度降低:具有最小ginisplit(D)(或最大不純度降低)的屬性被選作分裂結(jié)點(需要為每一個屬性列舉所有的分裂結(jié)點)Gini指標Ex.D中有9個元組屬于類buys_computer=“yes”，5個元組屬于類“no”假定屬性income從D中劃分10個元組到D1中:{low,medium}，其余4個元組分到D2中

同理可得，Gini{low,high}is0.458;Gini{medium,high}is0.450.因此,屬性income的最好二元劃分在{low,medium}(and{high})上，因為它有最小化的Gini指標27屬性選擇度量的比較三種度量一般情況下都能夠得到較好的結(jié)果，但是Informationgain:偏向多值屬性Gainratio:傾向于不平衡分裂，其中一個劃分比其他劃分小得多Giniindex:偏向于多值屬性當類的數(shù)量很大時會有困難傾向于導致相等大小的劃分和純度過適應（Overfitting）和樹剪枝ECUST--JingZhang28過適應（Overfitting）:產(chǎn)生的決策樹過分適應訓練數(shù)據(jù)由于噪聲或者離群點，使得很多分支反映的是訓練數(shù)據(jù)中的異常。太依賴于訓練數(shù)據(jù)集合，對于未使用的例子預測結(jié)果精度很差。避免Overfitting的兩種方法先剪枝:通過提早停止樹的構(gòu)造而對樹“剪枝”難以選擇一個合適的閾值后剪枝:

它由完全生長的樹剪去分支。后剪枝所需的計算比先剪枝多，但是通?？梢援a(chǎn)生更優(yōu)的樹基本決策樹歸納的加強ECUST--JingZhang29允許屬性具有連續(xù)值通過把連續(xù)屬性值劃分為離散的區(qū)間集來動態(tài)定義新的離散值屬性處理缺省屬性值賦予屬性最常見的值給每個可能的值賦予概率屬性構(gòu)造基于存在的稀疏表示的屬性創(chuàng)建新的屬性這將減少碎片，重復和復制問題數(shù)據(jù)挖掘?qū)W習中可伸縮決策樹歸納方法ECUST--JingZhang30SLIQ(EDBT’96—Mehtaetal.)為每個屬性創(chuàng)建索引并只將類列表和目前的屬性列表放入內(nèi)存SPRINT(VLDB’96—J.Shaferetal.)構(gòu)造一個“屬性列表”數(shù)據(jù)結(jié)構(gòu)存放類和RID信息PUBLIC(VLDB’98—Rastogi&Shim)把樹分裂和樹剪枝集成起來：早點停止樹的增長RainForest(VLDB’98—Gehrke,Ramakrishnan&Ganti)把“可伸縮”從決定樹質(zhì)量的標準中分離出來創(chuàng)建AVC-集(屬性－值和類標號)分類和預測31什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)貝葉斯分類ECUST--JingZhang32貝葉斯分類統(tǒng)計學習分類方法預測類成員關(guān)系的可能性樸素貝葉斯分類類條件獨立假定一個屬性值對給定類的影響獨立于其他屬性的值。貝葉斯信念網(wǎng)絡可以表示屬性子集間的依賴33貝葉斯定理給定訓練數(shù)據(jù)X,假設H的后驗概率,P(H|X),遵循貝葉斯定理

上述公式可以被非正式地表示為

posteriori=likelihoodxprior/evidence預測X屬于Ci，當且僅當對于所有的k個類，概率P(Ci|X)的值在所有P(Ck|X)當中最大實踐的困難：需要一些概率的初始化知識，大的計算開銷樸素貝葉斯分類ECUST--JingZhang34樸素假設:屬性獨立P(x1,…,xk|C)=P(x1|C)·…·P(xk|C)如果第i個屬性是分類屬性:P(xi|C)被評估為類C中第i個屬性的值為xi的樣本的相對頻率如果第i個屬性是連續(xù)屬性:P(xi|C)通過一個高斯密度函數(shù)來評估樸素貝葉斯分類器令D是元組和它們相關(guān)類標號的訓練數(shù)據(jù)集合,每一個元組用一個n-D屬性矢量X=(x1,x2,…,xn)表示假定有m

個類C1,C2,…,Cm.分類就是得到最大后驗概率，即,最大P(Ci|X)可以從貝葉斯定理得到因為P(X)對于所有類是常量,所以僅有

需要被最大化。一個樸素貝葉斯分類的例子

訓練集如下36Class:C1:buys_computer=‘yes’C2:buys_computer=‘no’DatasampleX=(age<=30,Income=medium,Student=yesCredit_rating=Fair)37P(Ci):P(buys_computer=“yes”)=9/14=0.643P(buys_computer=“no”)=5/14=0.357ComputeP(X|Ci)foreachclass P(age=“<30”|buys_computer=“yes”)=2/9=0.222P(age=“<30”|buys_computer=“no”)=3/5=0.6P(income=“medium”|buys_computer=“yes”)=4/9=0.444P(income=“medium”|buys_computer=“no”)=2/5=0.4P(student=“yes”|buys_computer=“yes)=6/9=0.667P(student=“yes”|buys_computer=“no”)=1/5=0.2P(credit_rating=“fair”|buys_computer=“yes”)=6/9=0.667P(credit_rating=“fair”|buys_computer=“no”)=2/5=0.4X=(age<=30,income=medium,student=yes,credit_rating=fair)P(X|Ci):P(X|buys_computer=“yes”)=0.222x0.444x0.667x0.0.667=0.044P(X|buys_computer=“no”)=0.6x0.4x0.2x0.4=0.019P(X|Ci)*P(Ci):P(X|buys_computer=“yes”)*P(buys_computer=“yes”)=0.028

P(X|buys_computer=“no”)*P(buys_computer=“no”)=0.007

Therefore,Xbelongstoclass“buys_computer=yes” 避免零概率值問題樸素貝葉斯分類需要每一個條件概率都必須非零.否則預測的概率將為零

例如：

假定數(shù)據(jù)集合有1000個元組,income=low(0),income=medium(990),andincome=high(10),用拉普拉斯校準（Laplaciancorrection）(or拉普拉斯估值法)為每一類增加1個元組Prob(income=low)=1/1003Prob(income=medium)=991/1003Prob(income=high)=11/1003這些校準過的概率估計與對應的未校準的估計很接近，但是避免了零概率值。有關(guān)獨立性假設ECUST--JingZhang39獨立性假設使得樸素貝葉斯分類成為可能當獨立性假設滿足時生成最優(yōu)分類器但是實踐中很少滿足，因為屬性（變量）通常時相關(guān)的試著克服這些限制:貝葉斯信念網(wǎng)絡,聯(lián)合屬性的貝葉斯推理和因果關(guān)系決策樹,在一個時刻只推理一個屬性，首先考慮最重要的屬性貝葉斯信念網(wǎng)絡ECUST--JingZhang40貝葉斯信念網(wǎng)絡（貝葉斯網(wǎng)絡，信念網(wǎng)絡，概率網(wǎng)絡）表示一組變量的聯(lián)合概率分布，它通過一組條件概率來指定一組條件獨立性假定可表述變量的一個子集上的條件獨立性假定比樸素貝葉斯分類在限制條件上更為寬松也更為實用，同時又比在所有變量中計算條件依賴更可行。提供一種因果關(guān)系的圖形，可以在其上進行學習，表示變量之間的因果關(guān)系條件獨立性假設是貝葉斯網(wǎng)絡進行定量推理的理論基礎貝葉斯信念網(wǎng)絡的組成有向無環(huán)圖條件概率表貝葉斯信念網(wǎng)絡:一個例子ECUST--JingZhang41FamilyHistoryLungCancerPositiveXRaySmokerEmphysemaDyspneaLC~LC(FH,S)(FH,~S)(~FH,S)(~FH,~S)0.80.20.50.50.70.30.10.9貝葉斯信念網(wǎng)絡BayesianBeliefNetworks變量LungCancer的條件概率表:表明了該變量父結(jié)點可能組合的條件概率貝葉斯信念網(wǎng)絡貝葉斯信念網(wǎng)允許變量的子集間定義類條件獨立性提供因果關(guān)系的圖形貝葉斯信念網(wǎng)絡的學習結(jié)構(gòu)學習網(wǎng)絡拓撲結(jié)構(gòu)的學習參數(shù)學習已知網(wǎng)絡結(jié)構(gòu)對網(wǎng)絡中每個分量的局部條件概率分布的學習網(wǎng)絡結(jié)構(gòu)已知網(wǎng)絡結(jié)構(gòu)未知數(shù)據(jù)完備概率參數(shù)學習：簡單統(tǒng)計估計，MLE方法，貝葉斯方法找最優(yōu)網(wǎng)絡結(jié)構(gòu)：MDL、BDe等評分標準，啟發(fā)式搜索、模擬退火搜索等數(shù)據(jù)不完備找最優(yōu)概率參數(shù)：EM算法、基于梯度的方法、高斯算法等既要找最佳結(jié)構(gòu)，又要找最優(yōu)參數(shù)：有結(jié)構(gòu)EM算法，混合模型等ECUST--JingZhang42分類和預測43什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)44使用IF-THEN規(guī)則分類用IF-THEN

規(guī)則的形式表示知識例如:IFage=youthANDstudent=yesTHENbuys_computer=yesIF部分稱作規(guī)則前件或前提；then部分是規(guī)則的結(jié)論規(guī)則的評價:覆蓋率和準確率ncovers=規(guī)則R覆蓋的元組數(shù)ncorrect=R正確分類的元組數(shù)coverage(R)=ncovers/|D|/*D:訓練數(shù)據(jù)集*/accuracy(R)=ncorrect/ncovers使用IF-THEN規(guī)則分類如果多個規(guī)則被觸發(fā)，則需要沖突解決策略規(guī)模序（Sizeordering）:將最高優(yōu)先權(quán)賦予具有“最苛刻”要求的觸發(fā)規(guī)則(即,具有最多屬性測試的觸發(fā)規(guī)則)規(guī)則序（Ruleordering）：預先確定規(guī)則的優(yōu)先次序基于規(guī)則排序（Rule-basedordering）(decisionlist):根據(jù)規(guī)則質(zhì)量的度量（準確率、覆蓋率等）或領域?qū)＜医ㄗh將規(guī)則組織成一個優(yōu)先權(quán)列表基于類排序（Class-basedordering）:類按“重要性”遞減排序或誤分類代價排序ECUST--JingZhang45從決策樹中抽取分類規(guī)則ECUST--JingZhang46以IF-THEN的形式表示知識每條從根到葉的路徑均為一個獨立的規(guī)則沿著給定路徑上的每個屬性－值對形成規(guī)則前件的一個合取項葉節(jié)點保留分類預測規(guī)則易于為人們所理解例子IFage=“<=30”AND

student=“no”THENbuys_computer=“no”IFage=“<=30”AND

student=“yes”THENbuys_computer=“yes”IFage=“31…40” THENbuys_computer=“yes”IFage=“>40”AND

credit_rating=“excellent”THENbuys_computer=“yes”IFage=“<=30”AND

credit_rating=“fair”THENbuys_computer=“no”47使用順序覆蓋算法的規(guī)則歸納順序覆蓋算法：直接從訓練數(shù)據(jù)抽取規(guī)則典型的順序覆蓋算法:FOIL,AQ,CN2,RIPPER順序地學習規(guī)則，給定類Ci的每個規(guī)則理想地覆蓋該類的許多元組，并且希望不覆蓋其他類的元組步驟:一次學習一個規(guī)則每當學習一個規(guī)則，就刪除該規(guī)則覆蓋的元組對剩下的元組重復該過程直到滿足終止條件，即沒有更多的訓練樣本或者當返回規(guī)則的質(zhì)量低于用戶設定的閾值。決策樹歸納:同時學習一組規(guī)則ECUST--JingZhang48順序覆蓋算法

while(enoughtargettuplesleft) generatearule removepositivetargettuplessatisfyingthisruleExamplescoveredbyRule3ExamplescoveredbyRule2ExamplescoveredbyRule1PositiveexamplesECUST--JingZhang如何學習規(guī)則束搜索（beamsearch）從空規(guī)則開始，然后逐漸地向它添加屬性測試選擇屬性的方法—貪心的深度優(yōu)先策略每當面臨添加一個新的屬性測試到當前規(guī)則時，它根據(jù)訓練樣本選擇最能提高規(guī)則質(zhì)量屬性的測試規(guī)則質(zhì)量度量熵：對數(shù)據(jù)集D的元組分類所需要的期望信息偏向于覆蓋單個類大量元組和少量其他類的元組的條件信息增益：偏向于具有高準確率并且覆蓋許多正元組的規(guī)則考慮覆蓋率的統(tǒng)計檢驗：將規(guī)則覆蓋的元組的觀測類分布與規(guī)則做隨機預測產(chǎn)生的期望類分布進行比較有助于識別具有顯著覆蓋率的規(guī)則規(guī)則剪枝使用上述方法產(chǎn)生的規(guī)則，可能過分擬合訓練數(shù)據(jù)，而對于測試數(shù)據(jù)集可能效果沒有那么好，為此可以對規(guī)則進行適當?shù)募糁OIL使用的剪枝法其中pos和neg分別為規(guī)則R覆蓋的正元組和負元組數(shù)。這個值將隨R在剪枝集上的準確率增加。如果R剪枝后的FOIL_Prune值較高，則對R剪枝。剪枝從最近添加的合取項開始，只要剪枝導致改進，則一次減去一個合取項分類和預測51什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)52分類的數(shù)學模型分類:

預測類標號E.g.,Personalhomepageclassificationxi=(x1,x2,x3,…),yi=+1or–1x1:#ofword“homepage”x2:#ofword“welcome”MathematicallyxX=n,yY={+1,–1}Wewantafunctionf:XY

53通過后向傳播分類后向傳播（Backpropagation）:一種神經(jīng)網(wǎng)絡學習方法由心理學家和神經(jīng)學家開發(fā)和測試神經(jīng)的計算模擬神經(jīng)網(wǎng)絡:連接輸入/輸出單元的集合，其中每一個連接都有一個權(quán)重與之相關(guān)聯(lián)在學習階段，通過調(diào)整權(quán)重使得能夠正確地預測輸入元組的類標號來學習網(wǎng)絡。由于單元之間的連接，神經(jīng)網(wǎng)絡學習又稱連接者學習（connectionistlearning）。54神經(jīng)網(wǎng)絡作為分類器缺點訓練時間過長

需要大量的參數(shù)，且這些參數(shù)的值大部分依靠經(jīng)驗獲得,如網(wǎng)絡拓撲或結(jié)構(gòu)可解釋性差:很難解釋網(wǎng)絡中學習的權(quán)重和“隱藏單元”的符號含義優(yōu)點對噪音數(shù)據(jù)的高承受能力對未經(jīng)訓練的數(shù)據(jù)的模式分類能力適合連續(xù)值的輸入和輸出已經(jīng)成功地用于廣泛的現(xiàn)實世界數(shù)據(jù)算法是固有并行的，可使用并行技術(shù)加快計算過程最近已經(jīng)開發(fā)了一些從訓練過的神經(jīng)網(wǎng)絡提取規(guī)則的技術(shù)神經(jīng)網(wǎng)絡Then-dimensionalinputvectorxismappedintovariableybymeansofthescalarproductandanonlinearfunctionmappingmk-fweightedsumInputvectorxoutputyActivationfunctionweightvectorw?w0w1wnx0x1xnbias56多層前向反饋神經(jīng)網(wǎng)絡OutputlayerInputlayerHiddenlayerOutputvectorwij57多層神經(jīng)網(wǎng)絡是如何工作的神經(jīng)網(wǎng)絡的輸入對應于每個訓練元組測量的屬性輸入同時提供給稱作“輸入層”的單元這些輸入通過輸入層，然后加權(quán)同時提供給稱作隱藏層的“類神經(jīng)元”第二層。隱藏層的數(shù)目是任意的，盡管通常只有一層

最后一個隱藏層的加權(quán)輸出作為構(gòu)成輸出層的單元的輸入。輸出層發(fā)布給定給定元組的網(wǎng)絡預測。如果其權(quán)重都不回送到輸入單元，或前一層的輸出單元，則該網(wǎng)絡是前向反饋的。從統(tǒng)計觀點來看，神經(jīng)網(wǎng)絡實現(xiàn)的是非線性回歸：給定足夠多的隱藏單元和足夠多的訓練樣本，多層前饋網(wǎng)絡可以逼近任何函數(shù)58定義網(wǎng)絡拓撲確定網(wǎng)絡拓撲結(jié)構(gòu):輸入層的單元數(shù),隱藏層的層數(shù)(if>1),每個隱藏層的單元數(shù),以及輸出層的單元數(shù)對訓練元組中每個屬性的測量輸入值進行規(guī)范化，使之落入[0.0—1.0]之間每個域值一個輸入單元,每個單元初始化為0輸出：

對于分類，并且超過兩個類，每個類一個輸出單元一旦網(wǎng)絡經(jīng)過訓練且準確率不能接受，通常用不同的網(wǎng)絡拓撲或不同的初始權(quán)重集合，重復訓練過程59后向傳播后向傳播迭代地處理訓練元組數(shù)據(jù)集，將每個元組的網(wǎng)絡預測與實際已知的目標值比較。對每個訓練樣本，修改權(quán)重使網(wǎng)絡預測和實際目標值之間均方誤差最小。修改“后向”進行:由輸出層，經(jīng)由每個隱藏層，到第一個隱藏層，因此稱作“后向傳播”步驟初始化網(wǎng)絡的所有權(quán)重（為很小的隨機數(shù)）和偏倚向前傳播輸入(通過激勵函數(shù))向后傳播誤差(通過更新權(quán)重和誤差)終止條件(當錯誤非常小等)60后向傳播和可解釋性知識的表示提取隱藏在訓練后的神經(jīng)網(wǎng)絡中的知識，并用符號解釋這些知識的研究從網(wǎng)絡提取規(guī)則:網(wǎng)絡剪枝通過剪去對訓練后的網(wǎng)絡影響最小的加權(quán)鏈簡化網(wǎng)絡結(jié)構(gòu)一旦訓練后的網(wǎng)絡已剪枝，某些方法將進行鏈、單元或活躍值聚類研究輸入值和活躍值的集合，導出描述輸入和隱藏單元層聯(lián)系的規(guī)則。靈敏度分析:用于評估一個給定的輸入變量對網(wǎng)絡輸出的影響。從這種分析得到的知識是形如“IFX減少5%THENY增加8%”的歸責。分類和預測61什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)62SVM—支持向量機一種線性和非線性數(shù)據(jù)的有前途的新分類方法它使用一種非線性映射將原有訓練數(shù)據(jù)映射到高維在新的維上，它搜索線性最佳分離超平面（即決策邊界）使用一個適當?shù)膶ψ銐蚋呔S的非線性映射，兩類的數(shù)據(jù)總可以被超平面分開。SVM使用支持向量（“基本”訓練元組）和邊緣（由支持向量定義）發(fā)現(xiàn)該超平面63SVM—歷史和應用Vapnik和他的同事(1992)—基礎理論來自于Vapnik&Chervonenkis’在六十年代關(guān)于統(tǒng)計學習理論的研究特征:雖然訓練時間長，但對復雜的非線性決策邊界的建模能力是高度準確的，且不容易過分擬合。用于:分類和數(shù)值預測應用:手寫數(shù)字識別，對象識別，語音識別，以及基準時間序列預測檢驗

64SVM—邊界和支持向量SupportVectorsSmallMarginLargeMargin65SVM—當數(shù)據(jù)是線性可分的mLetdataDbe(X1,y1),…,(X|D|,y|D|),whereXiisthesetoftrainingtuplesassociatedwiththeclasslabelsyiThereareinfinitelines(hyperplanes)separatingthetwoclassesbutwewanttofindthebestone(theonethatminimizesclassificationerroronunseendata)SVMsearchesforthehyperplanewiththelargestmargin,i.e.,maximummarginalhyperplane(MMH)66SVM—線性可分分離超平面可以記作W●X+b=0其中W={w1,w2,…,wn}是權(quán)重向量，b是一個標量（偏倚）對于2-D的訓練元組，分離超平面可以寫作w0+w1x1+w2x2=0分離超平面定義邊界的兩邊:H1:w0+w1x1+w2x2≥1foryi=+1,andH2:w0+w1x1+w2x2≤–1foryi=–1落在超平面H1

或H2(即定義邊緣的兩側(cè))上的訓練元組稱為支持向量67為什么SVM對高維數(shù)據(jù)有效?學習后的分類器的復雜度由支持向量數(shù)而不是由數(shù)據(jù)的維數(shù)刻畫支持向量是基本或臨界的訓練元組它們離決策邊界(MMH)最近如果刪除所有其他元組并重復訓練，則將發(fā)現(xiàn)相同的分離超平面找到的支持向量數(shù)可以用來計算SVM分類器的期望誤差率的上界，這獨立于數(shù)據(jù)的維數(shù)。具有少量支持向量的SVM可以具有很好的推廣性能，即使數(shù)據(jù)的維度很高時也如此68SVM—線性不可分轉(zhuǎn)換原始輸入數(shù)據(jù)到一個更高維的空間在新的空間搜索一個線性分割超平面分類和預測69什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測評估分類器或預測器的準確率小結(jié)其它的分類方法ECUST--JingZhang70惰性學習法k-最近鄰分類基于案例的推理遺傳算法粗糙集方法模糊集方法71惰性學習法vs.急切學習法惰性vs.急切學習惰性學習(基于實例的學習):簡單存儲訓練數(shù)據(jù)(或只是稍加處理)并且一直等到給定一個檢驗元組。急切學習(前面我們講過的所有方法):給定訓練元組的集合，在收到新的測試數(shù)據(jù)進行分類之前先構(gòu)造一個分類器模型惰性學習:花費極少的時間用來訓練，更多的時間用來預測。準確性惰性學習法具有豐富的假設空間，因為它用很多的局部線性函數(shù)去構(gòu)造目標函數(shù)內(nèi)在的全局近似急切學習:必須用單個假設覆蓋所有的實例空間惰性學習法ECUST--JingZhang72惰性學習法

存放所有的訓練樣本,并且直到新的樣本需要分類時才建立分類典型的方法k-最近鄰分類把訓練樣本作為歐氏空間的點存放基于案例的推理使用符號描述和基于知識的推論k-最近鄰分類ECUST--JingZhang73基于類比學習所有樣本用n維數(shù)值屬性描述，對應于n維空間的點最近的鄰居是用歐幾里德距離定義的兩個點X=(x1,x2,...,xn)和Y=(y1,y2,...,yn)的歐幾里德距離定義如下：k-最近鄰分類ECUST--JingZhang74K-最近鄰分類法搜索模式空間，找出最接近未知樣本的k個訓練樣本。這k個訓練樣本是未知樣本的k個“近鄰”未知樣本被分類到k個最近鄰者中最公共的類。75有關(guān)KNN算法的討論最近鄰分類可以用于預測，返回給定未知樣本的實數(shù)值預測分類返回未知樣本的k個最臨近者實數(shù)值的平均值距離權(quán)重的最近鄰算法根據(jù)其與查詢點xq之間的距離，給k個近鄰分配不同的權(quán)重給更近的鄰居以更大的權(quán)重通過求最近鄰的平均值可以平滑噪音不相關(guān)屬性可能會影響最近鄰分類法的準確率

為此，需要對最近不相關(guān)數(shù)據(jù)進行剪枝基于案例的推理(CBR)ECUST--JingZhang76CBR:使用一個問題解的數(shù)據(jù)庫來求解新問題與kNN的相同點：消極評估+分析相似實例與kNN的不同點：實例不是“歐氏空間中的點”，而是復雜的符號描述方法實例可以用豐富的符號描述表示（例如，功能圖）檢索到的多個相似案例可以被合并案例檢索、基于知識的推理和問題求解間是緊密耦合在一起的研究課題找到好的相似度度量為索引訓練案例，選擇顯著的特征和開發(fā)有效的索引技術(shù)基于句法相似性度量的索引，失敗時，回溯搜索另外的實例以適應現(xiàn)有的案例遺傳算法ECUST--JingZhang77遺傳算法:基于類似于生物進化的思想遺傳學習創(chuàng)建一個由隨機產(chǎn)生的規(guī)則組成的初始群體每個規(guī)則用一個二進位串表示例如：IFA1andNotA2thenC2可以用“100”編碼其中最左邊的兩個二進位分別表示屬性A1和A2，而最右邊的二進位表示類。如果一個屬性具有k（k>2）個值，則可以用k個二進位對該屬性值編碼。類可用類似的形式編碼。根據(jù)適者生存的原則,形成由當前群體中最合適的規(guī)則組成的新的群體,以及這些規(guī)則的后代規(guī)則的擬合度（fitness）用它對訓練本集的分類準確率評估通過交叉和變異來產(chǎn)生后代交叉：來自規(guī)則對的子串交換，形成新的規(guī)則對變異：規(guī)則串中隨機選擇的位被反轉(zhuǎn)78粗糙集方法粗糙集用于近似地或“粗糙地”定義等價類。給定類C的粗糙集通過兩個集合近似：C的下近似（一定屬于C）和C的上近似（不可能認為不屬于C）找到可以描述給定數(shù)據(jù)集中所有概念的最小屬性子集（歸約集）問題是NP困難的。但是可以用識別矩陣discernibilitymatrix（存放每對數(shù)據(jù)元組的屬性值之間的差別）來降低計算強度。模糊集方法79基于規(guī)則的分類的缺點對于連續(xù)屬性，有陡峭的截斷。例如：IF(years_employed>=2)and(income>=50k)thencredit=“approved”模糊邏輯使用0.0到1.0之間的真值表示一個特定的值是一個給定類成員的隸屬程度模糊邏輯的使用真值被轉(zhuǎn)換成模糊值e.g.收入被映射到一個離散的分類{low,medium,high}，然后使用模糊邏輯，允許對每個類定義“模糊”閾值或邊界。對于給定的新樣本，可以使用多個模糊規(guī)則。每個可用的規(guī)則為分類的成員關(guān)系貢獻一票。通常，對每個預測分類的真值進行求和，并組合這些和。分類和預測80什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)什么是預測？ECUST--JingZhang81預測與分類相似首先,建立一個模型其次,使用模型預測未知值預測的主要方法是回歸線性回歸和多元回歸非線性回歸預測與分類不同分類是指預測分類的類標號預測為連續(xù)值函數(shù)建模線性回歸82線性回歸是最簡單的回歸形式，采用直線建模。雙變量回歸將一個隨機變量Y（稱作響應變量）視為另一個隨機變量X（稱為預測變量）的線性函數(shù)，即Y=α+βX

其中，Y的方差為常數(shù)，α和β是回歸系數(shù)，分別表示直線在Y軸的截斷和斜率。這些系數(shù)可以用最小二乘法求解，這使得實際數(shù)據(jù)與該直線的估計之間誤差最小。給定s個樣本或形如(x1,y1),(x2,y2),..,(xs,ys)的數(shù)據(jù)點，回歸系數(shù)α和β可以用下列公式計算。是x1,x2,..,xs

的均值，而

是y1,y2,..,ys的均值多元線性回歸與非線性回歸ECUST--JingZhang83多元線性回歸是線性回歸的擴展，涉及多個預測變量。響應變量Y

可以是一個多維特征向量的線性函數(shù)。基于兩個預測屬性或變量X1

和X2

的多元線性回歸模型可以表示為：Y=α+β1X1+β2X2

α，β1和β2可以用最小二乘法求解非線性回歸在基本線性模型上添加多項式項建模，通過對變量進行變換，將非線性模型轉(zhuǎn)換成線性的，然后用最小二乘方法求解。例：轉(zhuǎn)換成：廣義線性模型廣義線性模型提供了將線性回歸用于分類響應變量的理論基礎。廣義線性模型中，響應變量Y的方差是Y的平均值的函數(shù)。廣義線性模型的常見形式包括對數(shù)回歸和泊松回歸。對數(shù)回歸將某些事件發(fā)生的概率看作預測變量集的線性函數(shù)。計數(shù)數(shù)據(jù)常常呈現(xiàn)泊松分布，可使用泊松回歸建模。ECUST--JingZhang84分類和預測85什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)分類器評估度量:準確率和誤差率ECUST--JingZhang86Actualclass\PredictedclassC1~C1C1TruePositives(TP)FalseNegatives(FN)~C1FalsePositives(FP)TrueNegatives(TN)分類器的正確率或識別率：被正確分類的測試元組占測試元組總數(shù)的百分比

混淆矩陣:錯誤率:

1–

accuracy,orECUST--JingZhang87分類器評估度量:混淆矩陣的例子Actualclass\Predictedclassbuy_computer=yesbuy_computer=noTotalRecognition(%)buy_computer=yes695446700099.34buy_computer=no4122588300086.27Total736626341000095.42給定m

個類,混淆矩陣至少是m*m的表，CMi,j

表示類i用分類器分到類j的元組數(shù)。附加的行或列，可以提供每個類的合計或識別率ECUST--JingZhang88分類器評估度量:靈敏性和特效性類不平衡問題:某一個類可能比較稀少,比如：詐騙檢測顯著多數(shù)的負類和少數(shù)的正類

靈敏性:真正（識別）率,特效性:真負（識別）率,ECUST--JingZhang89分類器評估度量:準確率和召回率Precision:正確性

–what%oftuplesthattheclassifierlabeledaspositiveareactuallypositive?Recall:完整性–what%ofpositivetuplesdidtheclassifierlabelaspositive?

Perfectscoreis1.0precision&recall之間是相反的關(guān)系

ECUST--JingZhang90分類器評估度量:例子Actualclass\Predictedclasscancer=yescancer=noTotalRecognition(%)cancer=yes9021030030.00sensitivitycancer=no1409560970098.56specificityTotal23097701000096.40accuracyPrecision=90/230=39.13%;Recall=90/300=30.00%分類和預測91什么是分類？什么是預測？關(guān)于分類和預測的問題用決策樹歸納分類貝葉斯分類基于規(guī)則的分類用后向傳播分類支持向量機其它分類方法預測準確率和誤差的度量評估分類器或預測器的準確率小結(jié)評估分類法的準確率92保持(holdout)使用兩個獨立的數(shù)據(jù)集,例如,訓練集(2/3),測試集(1/3)估計是悲觀的，因為只用一部分初始數(shù)據(jù)導出模型用于具有大數(shù)量樣本的數(shù)據(jù)集隨機子抽樣（randomsubsampling）：保持方法的變形，把保持方法重復k次。交叉確認（cross-validation）把數(shù)據(jù)集分成k個互不相交的子樣本集訓練和檢驗進行k次使用k-1子樣本集作為訓練數(shù)據(jù),一個子樣本作為測試數(shù)據(jù)k-折交叉確認適用于具有