數學建模的數據挖掘方法第1頁，共93頁，2023年，2月20日，星期五2、支持向量機(supportvectormachinesSVM)吳雄華第2頁，共93頁，2023年，2月20日，星期五

，

定義：設訓練數據集為：

可以被一個超平面

分開，如果這個向量集（即訓練數據集）被超平面沒有錯誤的分開，且離超平面最近的向量與超平面之間的距離之和最大，則稱此超平面為此向量集的最優（分類）超平面。如圖1所示：1最優分類超平面第3頁，共93頁，2023年，2月20日，星期五對超平面方程兩邊乘以相同系數仍表示該平面，因此可以做如下假設：這樣最優分類超平面應該滿足如下條件：可以統一寫為第4頁，共93頁，2023年，2月20日，星期五其中到平面

的距離為

為平面上任意一點。因此，

到平面

的最小距離為

第5頁，共93頁，2023年，2月20日，星期五要找到最優分類超平面，可以轉換為如下的一個二次規劃問題：引入Lagrange函數：

第6頁，共93頁，2023年，2月20日，星期五令相應的偏導數為即：代入原式，得到第7頁，共93頁，2023年，2月20日，星期五因此可以把上述二次規劃轉為它的對偶問題：解此二次規劃可得到

其中

對應的

支持向量機由此而名。稱為支持向量，第8頁，共93頁，2023年，2月20日，星期五由Kuhn-Tucker條件，最優超平面的系數b

可由

對應的方程

得到，這樣便得到了最優分類超平面方程，進而可以用該方程進行分類：若

，則

若

，則

第9頁，共93頁，2023年，2月20日，星期五2.若數據在輸入空間線性不可分，則出超平面的約束條件需引入松弛變量

，相應的得到如下的二次規劃：第10頁，共93頁，2023年，2月20日，星期五若

，則

若

，則

按如上方法同理可得到其對偶問題：同樣可以得到判別函數第11頁，共93頁，2023年，2月20日，星期五3.支持向量機支持向量機（Supportvectormachines，SVM）實現的是如下思想：通過某個非線性的映射將輸入向量映射到一個更高維的空間中，使得這些樣本在高維空間中線性可分，然后在該空間構造最優分類超平面。如圖所示：第12頁，共93頁，2023年，2月20日，星期五同時注意到，在原空間中構造最優分類超平面主要解決兩個問題：1、點積運算2、求解二次規劃可以證明，在高維空間中構造最優分類超平面，也只需知道其點積運算即可，而不需要知道映射

的具體形式。

第13頁，共93頁，2023年，2月20日，星期五考慮Hilbert空間中內積的一個一般表達式：其中

是輸入空間向量

空間在特征中的映像，根據Hilbert-Schmidt理論，

（CourantandHilbert，1953）可以是滿足如下定理的任意對稱函數定理（Mercer）

要保證L2下的對稱函數能以正的系數

展開成

（即描述了在某特征空間中的一個內積）充分必要條件是：對滿足的所有

條件

成立。第14頁，共93頁，2023年，2月20日，星期五在SVM中，滿足上面定理的通常稱為核函數空間中的點積運算。

,引入核函數的概念可以解決高維常用的核函數有：

多項式核函數:

高斯核函數:

這樣便可在高維空間中的解決點積運算：第15頁，共93頁，2023年，2月20日，星期五這樣只要把前面的點積運算用核函數代替，便可得到高維空間中相應的最優分類超平面。即例第16頁，共93頁，2023年，2月20日，星期五3、基于決策樹的分類方法例1.下表是用于構造分類模型的數據集，包括14個樣本和5個屬性:Outlook、Temperature、Humidity、Windy和Play，其中前4個屬性是天氣，最后一個屬性是根據前4個屬性的情況說明這樣的天氣狀況是否適合比賽。各屬性取值如下：Outlook：sunny(s),overcast(o),rain(r);Temperature:hot(h),mild(m),cool(c);Humidity:high(h),normal(n);Windy:false,truePlay:Yes(y),no(n)第17頁，共93頁，2023年，2月20日，星期五訓練樣本集如下OutlookTempHumiWindyPlaySHHFNSHHTNOHHFYRMHFYRCNFYRCNTNOCNTYSMHFNSCNFYRMNFYOMNTYOMHTYOHNFYRMHTN第18頁，共93頁，2023年，2月20日，星期五決策樹是類似如下的一棵樹OutlooksunnyrainovercastPlay=noPlay=yeswindyfalsePlay=yesTruePlay=no給定一個新的天氣象:“rain,hot,high,true”，則判別其類別第19頁，共93頁，2023年，2月20日，星期五決策樹的構造：分裂屬性的選擇四、基于信息增益的特征選擇策略1.相關概念設信息源X的取值為A=(a1,a2,…,an)，ai出現的概率為pi，稱I(ai)=log(1/pi)=-logpi為ai的信息量；稱為X的信息熵。第20頁，共93頁，2023年，2月20日，星期五決策樹分類方法利用信息量增加（信息增益）作為特征選擇的一種指標。信息增益衡量每個屬性對分裂后的數據子集的信息量的貢獻。假設訓練集T包含n個樣本，這些樣本分別屬于m個類，其中第i個類在T中出現的比例為pi，稱為集合T的信息熵。如果m=1，即T的樣本都屬于一個類，則I（T）=0，達到最小值，何時Ｉ（Ｔ）達到最大？第21頁，共93頁，2023年，2月20日，星期五假設屬性Ａ把集合Ｔ劃分為ｖ個子集{T1,T2,..,Tv},其中Ti所包含的樣本數為ni，那么劃分后的熵就是：分裂后的信息增益定義為基于信息理論的特征選擇方法就是逐一計算每種分裂的信息增益，選擇信息增益最大的屬性作為分裂屬性。下面以前面給出的數據集為例，利用信息增益方法構造決策樹。第22頁，共93頁，2023年，2月20日，星期五第一步：計算訓練樣本集Ｔ的信息量。分類屬性Play有兩個類，其樣本數統計如下：因此T的信息量為：第二步：計算每個屬性的信息增益，對于Outlook屬性，它有3個屬性值，把樣本集T分成3個子集，每個子集的類別統計如下：樣本集TPlay=yesPlay=no樣本數95第23頁，共93頁，2023年，2月20日，星期五Outlook的信息熵為：OutlookPlay=yesPlay=nototalSunny(T1)134Overcast(T2)505Rain(T3)32514第24頁，共93頁，2023年，2月20日，星期五Outlook的信息增益為：同理對于Temperature屬性，它也有3個屬性值，把樣本集T分成3個子集，每個子集的類別統計如下：TemperaturePlay=yesPlay=nototalhot(T1)224mild(T2)426cool(T3)31414第25頁，共93頁，2023年，2月20日，星期五Temperature的信息熵為：Temperature的信息增益為：第26頁，共93頁，2023年，2月20日，星期五對于Humidity屬性和Windy屬性，統計如下：HumidityPlay=yesPlay=nototalNormal(T1)347high(T2)61714WindyPlay=yesPlay=nototalTrue(T1)336False(T2)62814計算其信息增益值分別為0.1653和0.0481.第27頁，共93頁，2023年，2月20日，星期五第三步：比較四個屬性的信息增益，按大小順序排列為Gain(Outlook)>Gain(Humidity)>Gain(Windy)>Gain(Temperature)因此應該選Outlook作為首分裂結點，即決策樹的形狀為：OutlookSunnyRainOvercast第28頁，共93頁，2023年，2月20日，星期五第二層結點的選擇與首結點類似，具體選擇過程如下：1）對于“Sunny”的分支，從原數據集T中統計出Outlook屬性值為sunny的樣本作為新的數據集T。OutlookTempHumiWindyPlaySHHFNSHHTNSMHFNSCNFY作為新樣本集第29頁，共93頁，2023年，2月20日，星期五計算T的信息量為：對于Temperature屬性，簡單統計如下：TemperaturePlay=yesPlay=nototalhot(T1)022mild(T2)011cool(T3)101顯然第30頁，共93頁，2023年，2月20日，星期五對于Humidity屬性，簡單統計如下：顯然HumidityPlay=yesPlay=nototalNormal(T1)101high(T2)033WindyPlay=yesPlay=nototalF(T1)123T(T2)011第31頁，共93頁，2023年，2月20日，星期五因此Sunny分支下的分裂屬性可選Temperature或Humidity，若取Humidity，則其屬性H和N下的記錄都為相同的類，該分支算法結束。OutlookTempHumiWindyPlaySHHFNSHHTNSMHFNSCNFY其分支結構如下：HumiditySunnyHighNormalPlay=NoPlay=Yes第32頁，共93頁，2023年，2月20日，星期五若取Temperature，則重新確定記錄集如下：OutlookTempHumiWindyPlaySHHFNSHHTNSMHFNSCNFYTempSunnyHighMPlay=NoPlay=No可以看出其三個分支H，C和M下的所有記錄也屬于相同的類，此分支算法結束。其分支結構如右：CPlay=Yes第33頁，共93頁，2023年，2月20日，星期五2）同理，對于Rain分支，統計數據如下：WindyRainFalseTruePlay=YesPlay=NoOutlook=RTempHumiWindyPlayMHFYCNFYCNTNMNFYMHTN因此選Windy其分支結構如右：第34頁，共93頁，2023年，2月20日，星期五3）同理，對于Overcast分支，統計數據如下：Play=Yes該分支下所有記錄均為同一類，因此該分支算法結束，其結構如下右。Outlook=OvercastTempHumiWindyPlayHHFYCNTYMNTYMHTYHNFYOvercast第35頁，共93頁，2023年，2月20日，星期五綜合以上結果，最后得到決策樹如下：OutlookTempSunnyHighMPlay=NoPlay=NoCPlay=YesWindyFalsePlay=YesPlay=NoTrueRainPlay=YesOvercast第36頁，共93頁，2023年，2月20日，星期五決策樹構造好后，給出新的對象便可判別其類別，例如，新的天氣對象為：1)“Overcast,cool,high,False”2)“Rain,Mild,Normal,True”，其類別分別為：第37頁，共93頁，2023年，2月20日，星期五五、基于數據分布的特征選擇策略除了基于信息增益的特征選擇策略外，還可以根據結點的數據類別的分布來選擇最優分裂結點，稱之為GiniIndex方法。定義：假設訓練集T包含n個樣本，這些樣本分別屬于m個類，其中第i個類在T中出現的比例為pi，則T的GiniIndex定義為：假設屬性Ａ把集合Ｔ劃分為ｖ個子集{T1,T2,..,Tv},其中Ti所包含的樣本數為ni，那么這個劃分的GiniIndex為：第38頁，共93頁，2023年，2月20日，星期五GiniIndex的特征選擇方法就是逐一計算按每個屬性分裂后的GiniIndex值，選擇giniIndex值最小的屬性作為分裂屬性。下面以前面給出的數據集為例，利用GiniIndex選擇策略構造決策樹的過程。對總樣本進行統計如下：樣本集TPlay=yesPlay=no樣本數95樣本集T的giniIndex值為第39頁，共93頁，2023年，2月20日，星期五對于Outlook屬性，它有3個屬性值，把樣本集T分成3個子集，每個子集的類別統計如下：OutlookPlay=yesPlay=nototalSunny(T1)134Overcast(T2)505Rain(T3)325每個子集的GiniIndex值如下：因此屬性Outlook的GiniIndex值為：第40頁，共93頁，2023年，2月20日，星期五同理對于Temperature屬性，它也有3個屬性值，把樣本集T分成3個子集，每個子集的類別統計如下：TemperaturePlay=yesPlay=nototalhot(T1)224mild(T2)426cool(T3)314因此屬性Temperature的GiniIndex值為：第41頁，共93頁，2023年，2月20日，星期五對于Humidity屬性和Windy屬性，統計如下：HumidityPlay=yesPlay=nototalNormal(T1)347high(T2)61714WindyPlay=yesPlay=nototalTrue(T1)336False(T2)62814計算其GiniIndex值分別為0.3674和0.4357.第42頁，共93頁，2023年，2月20日，星期五第三步：比較四個屬性的GiniIndex值如下：因此應該選Outlook作為首分裂結點，即決策樹的形狀為：OutlookSunnyRainOvercast屬性OutLTempHumiWindyGiniIndex值0.27850.3750.36740.4357第43頁，共93頁，2023年，2月20日，星期五第二層結點的選擇與首結點類似，具體選擇過程如下：對于“Sunny”的分支，從原數據集T中統計出Outlook屬性值為sunny的樣本作為新的數據集T。Outlook=STempHumiWindyPlayTHHFNHHTNMHFNCNFY第44頁，共93頁，2023年，2月20日，星期五對于Temperature屬性，簡單統計如下：TemperaturePlay=yesPlay=nototalhot(T1)022mild(T2)011cool(T3)101第45頁，共93頁，2023年，2月20日，星期五對于Humidity屬性，簡單統計如下：顯然HumidityPlay=yesPlay=nototalNormal(T1)101high(T2)033WindyPlay=yesPlay=nototalF(T1)123T(T2)011第46頁，共93頁，2023年，2月20日，星期五因此Sunny分支下的分裂屬性可選Temperature或Humidity，若取Humidity，則其屬性H和N下的記錄都為相同的類，該分支算法結束。OutlookTempHumiWindyPlaySHHFNSHHTNSMHFNSCNFY其分支結構如下：HumiditySunnyHighNormalPlay=NoPlay=Yes第47頁，共93頁，2023年，2月20日，星期五剩下的計算類似，最后得到決策樹如下：OutlookTempSunnyHighMPlay=NoPlay=NoCPlay=YesWindyFalsePlay=YesPlay=NoTrueRainPlay=YesOvercast第48頁，共93頁，2023年，2月20日，星期五六、信息增益和GiniIndex值的另一個應用考慮如下問題：預測貸款申請者是否會按時歸還貸款，歷史數據如下：顧客Id有房婚姻狀況年收入拖欠貸款1是單身125K否2否已婚100K否3否單身70K否4是已婚120K否5否離異95K是6否已婚60K否7是離異220K否8否單身85K是9否已婚75K否10否單身90K是第49頁，共93頁，2023年，2月20日，星期五對于“年收入”屬性，它是連續型變量，按前面決策樹的構造方法，應該每個屬性都是離散型屬性。為此，應該把連續型屬性劃分成若干個區間，這樣把該屬性化為離散型屬性。簡單的，若劃分為兩個區間，如何劃分？可以用信息增益或GiniIndex值方法。步驟如下：把連續型屬性值由小到大排列，取每兩個值的中間值作為候選劃分點：類NNNYYYNNNN值607075859095100120125220候選劃分點657280879297110122172第50頁，共93頁，2023年，2月20日，星期五然后計算按各個候選劃分點劃分的信息增益或GiniIndex值，例如，用GiniIndex值方法如下：類NNNYYYNNNN值607075859095100120125220候選劃分點657280879297110122172對于候選點65，劃分后類別統計如下類=N類=Y<65(T1)10>=65(T2)63第51頁，共93頁，2023年，2月20日，星期五類NNNYYYNNNN值607075859095100120125220候選劃分點657280879297110122172對于候選點72，劃分后類別統計如下類=N類=Y<70(T1)20>=70(T2)53第52頁，共93頁，2023年，2月20日，星期五類NNNYYYNNNN值607075859095100120125220候選劃分點657280879297110122172對于候選點80，對于候選點87，對于候選點92，對于候選點97，對于候選點110，對于候選點122，對于候選點172，最佳候選點第53頁，共93頁，2023年，2月20日，星期五根據上面的分析，可把“年收入”屬性劃分成兩個區間（0,97）和[97,10000)分別設為屬性A1和A2，則原數據集變為：顧客Id有房婚姻狀況年收入拖欠貸款1是單身125K（A2）否2否已婚100K（A2）否3否單身70K（A1）否4是已婚120K（A2）否5否離異95K（A1）是6否已婚60K（A1）否7是離異220K（A2）否8否單身85K（A1）是9否已婚75K（A1）否10否單身90K（A1）是第54頁，共93頁，2023年，2月20日，星期五再按前面的方法構造決策樹，便可對類似的顧客：“否，單身，100K”進行分類判別。第55頁，共93頁，2023年，2月20日，星期五七、樸素貝葉斯分類法1.樸素貝葉斯分類方法描述

設樣本集T有n個屬性：A1，A2，…，An，可能的類別有m個：C1，C2，…，Cm，待分類的樣本為x={X1,X2，…Xn}，分別計算條件概率：則條件概率P(Ci|X）最大所對應的類Ci即為X所在的類。在公式（1）中，計算等式左邊的每個條件概率時，右邊的分母相同，因此只需要計算分子，然后比較大小即可。

第56頁，共93頁，2023年，2月20日，星期五各概率的計算如下：

另外，用樸素貝葉斯分類時還需假設各屬性之間相互獨立，此時有：2.條件概率

P(xj|Ci）的估計第57頁，共93頁，2023年，2月20日，星期五條件概率

P(xj|Ci）的估計值分兩種情況情形1.第j個屬性Aj為離散型

的情況此時，條件概率P(xj|Ci）可按如下公式計算：第58頁，共93頁，2023年，2月20日，星期五例1：給定訓練樣本集如下，請用貝葉斯方法判別對象：“rain，hot，high，true”的類別。OutlookTempHumiWindyPlaySHHFNSHHTNOHHFYRMHFYRCNFYRCNTNOCNTYSMHFNSCNFYRMNFYOMNTYOMHTYOHNFYRMHTN第59頁，共93頁，2023年，2月20日，星期五解：分類屬性Play有兩個類，Play=yes（C1）和其Play=no（C2），樣本數統計如下：于是P（C1）=9/14，P（C2）=5/14對于Outlook屬性，數據匯總如下表：樣本集TPlay=yes（C1）Play=no（C2）樣本數95第60頁，共93頁，2023年，2月20日，星期五于是各條件概率為：OutlookC1（Y）C2（N）Sunny13Overcast50Rain32Total95，，，第61頁，共93頁，2023年，2月20日，星期五同理對于Temperature屬性，它也有3個屬性值，把樣本集T分成3個子集，每個子集的類別統計如下：TemperaturePlay=yesPlay=nohot22mild42cool31total95于是各條件概率為：，，，第62頁，共93頁，2023年，2月20日，星期五對于Humidity屬性和Windy屬性，統計如下：HumidityPlay=yesPlay=noNormal34high61total95WindyPlay=yesPlay=noTrue33False62total95試計算其“條件概率”。第63頁，共93頁，2023年，2月20日，星期五對于待分類樣本:分別計算以下兩個概率：=0.333*0.22*0.33*0.3*0.643=0.0053=0.4*0.4*0.8*0.6*0.357=0.0274

，因此

為第二類，即不適合比賽。

第64頁，共93頁，2023年，2月20日，星期五情形2.第j個屬性Aj為連續型

的情況tid有房婚姻狀況年收入拖欠貸款1是單身125否2否已婚100否3否但是70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是考慮如下的訓練樣本集，如何判別樣本的類別？第65頁，共93頁，2023年，2月20日，星期五屬性“年收入”為連續型數據類型，此時如果再用公式

來估計條件概率已不合適，例如，若新樣本的“年收入”為110K，則類似的新樣本將無法判別。

有兩種策略可以用了估計連續型屬性的條件概率：1.把連續屬性離散化；2.用概率分布來估計條件概率第66頁，共93頁，2023年，2月20日，星期五1.把連續屬性離散化如前面構造決策樹的GiniIndex或信息增益方法，把連續屬性劃分成幾個區間，即連續屬性離散化。按前面所述，如果把“年收入”劃分成兩個區間，則最佳的候選劃分點為97K，對應區間為

（0,97）和[97,10000）。通過計算類Ci中屬性“年收入”落入對應區間的比例來估計條件概率即把訓練數據集修改為下表第67頁，共93頁，2023年，2月20日，星期五tid有房婚姻狀況年收入<97K拖欠貸款1是單身否否2否已婚否否3否但是是否4是已婚否否5否離婚是是6否已婚是否7是離婚否否8否單身是是9否已婚是否10否單身是是用Bayes方法估計每個條件概率后，對新給出的任何樣本都可以判別。第68頁，共93頁，2023年，2月20日，星期五2.用概率分布來估計條件概率假設連續型屬性服從某種概率分布（通常假設服從正態分布），然后用訓練數據估計出分布的參數，進而計算相應的條件概率。如上例中，假設“年收入”屬性為隨機變量

對于每個類

Ci，屬性值xj屬于類Ci的概率為

和分別為類Ci中隨機變量xj的期望和方差可分別用

Ci中xj的觀察值的樣本均值和標準差估計。第69頁，共93頁，2023年，2月20日，星期五如上表數據中“年收入”數據，分別屬于兩類，設類別C1=“否”，C2=“是”，對應的觀察值如下：類別

C1=“否”的兩個參數估計如下：

年收入125100701209560220857590拖欠貸款否否否否是否否是否是類別C1=“否”的兩個參數估計為：第70頁，共93頁，2023年，2月20日，星期五

同理，類別C2=“是”的兩個參數估計為：對于新樣本

可以估計“年收入”屬性相應的條件概率為：

第71頁，共93頁，2023年，2月20日，星期五

下面用上述方法來判別新樣本數據匯總如下：樣本集所屬的類別。

類別C1（No）C2（Yes）total73屬性“有房”C1（No）C2（Yes）是30否43Total73第72頁，共93頁，2023年，2月20日，星期五

屬性“婚姻狀況”C1（No）C2（Yes）離異11單身22已婚40Total73對于屬性“年輸入”，已估計相應的條件概率為：第73頁，共93頁，2023年，2月20日，星期五

由以上概率計算樣本

相應的條件概率為：

因此新樣本屬于第二類，即“是”拖欠貸款。問題1：有一個屬性的類條件概率為0，則整個類的后驗概率就等于0，如果樣本

的類條件概率X應該如何判別？第74頁，共93頁，2023年，2月20日，星期五

問題2：對于連續型屬性Xj，估計條件概率時把它視為連續型隨機變量，估計的條件概率為那么，這樣估計是否合理？內的類條件概率為問題2的解釋：但我們知道，對于連續型隨機變量，有假設Xj落在區間對于連續型屬性Xj的每個取值xj，都使用同一個小正數在比較時，

果，因此公式（5）仍可以用了估計相應的條件概率。成為一個常數乘法因此，不影響比較結第75頁，共93頁，2023年，2月20日，星期五

對于問題1，通常使用m值法來估計條件概率以解決這種情況。m值估計法：條件概率的估計值用下式進行估計其中，n為訓練樣本中類Ci的總實例數，nc為Ci類中取值為xj的實例數，m和p是用戶事先給定的參數。一般m為正整數，p是位于0與1之間的小數。例.設m=10，p=1/4，試對前面所給的數據重新估計離散型屬性的各條件概率。第76頁，共93頁，2023年，2月20日，星期五tid有房婚姻狀況年收入<97K拖欠貸款1是單身否否2否已婚否否3否但是是否4是已婚否否5否離婚是是6否已婚是否7是離婚否否8否單身是是9否已婚是否10否單身是是第77頁，共93頁，2023年，2月20日，星期五最臨近分類算法（K－臨近算法）數據挖掘分類算法之第78頁，共93頁，2023年，2月20日，星期五一、引例下圖給出了二分類訓練樣本，待判樣本當K=5時，可以找K個與待判樣本最臨近的樣本所在的類別作為參考。綠色圓將被賦予紅色三角形那個類；當K=3時，因此綠色圓被賦予藍色四方形類。綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？第79頁，共93頁，2023年，2月20日，星期五二、基本思想形象解釋：K最近鄰(k-NearestNeighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。該方法的思想是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別?！叭绻呦聒喿?，叫像鴨子，看起來還像鴨子，那么它就很可能是一只鴨子?！钡?0頁，共93頁，2023年，2月20日，星期五在KNN算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。樣本z的k－最臨近是指和z距離最小的k個數據點。最臨近分類器把每個樣本看成d維空間的一個數據點，其中d是屬性個數。給定一個測試樣本z，使用前面介紹的任意一種臨近性度量，計算該測試樣本與訓練集中其他數據點的臨近度。第81頁，共93頁，2023年，2月20日，星期五圖1－c圖1－b圖1－a下圖給出待判數據點的1－最臨近、2－最臨近和3－最臨近示意圖。判為負類隨機判別判為正類第82頁，共93頁，2023年，2月20日，星期五給定訓練樣本集D和最臨近數k計算待判樣本與D中每個樣本的距離選擇與z距離最小的k個樣本組成集合Dk待判樣本zK－最臨近算法流程圖根據Dk中樣本的類別，按少數服從多數的原則決定z的類別結束第83頁，共93頁，2023年，2月20日，星期五例1設訓練樣本集如下表，xi0.5

3.0

4.54.

64.9

5.2

5.3

5.5

7.0

9.5

y

－－

+

+

+

－

－

+

－

－

請根據1－最臨近、3－最臨近、5－最臨近及7－最臨近，分別對樣本x＝5.0進行分類判別。第84頁，共93頁，2023年，2月20日，星期五解：待判樣本x＝0.5與訓練樣本間的距離平方（歐氏距離）計算如下表：xi0.5

3.0

4.54.

64.9

5.2

5.3

5.5

7.0

9.5

d220.2540.2560.1640.0110.0420.0930.2554720.25y

－－

+

+

+

－

－

+

－

－

按7－最臨近，x應為+類。因此，按1－最臨近，x應為+類；按3－最臨近，x應為－類；按5－最臨近，x應為+類；第85頁，共93頁，2023年，2月20日，星期五思考：改進思路1：根據距離加權判別;改進思路2：選擇不同的k值判決后，再按少數服從多數的原則重新表決（二次表決法）;改進思路3：結合改進思路1和2進行改進（