by dean
k-近鄰法其實是對最小距離法和最近鄰法的擴充套件而得到的較為簡單一種分類器。我們首先對距離分類器分類原理進行介紹,然後引出k-近鄰法。設需要對n類樣本進行分類,類別分別為,每一類標準樣本設為。
基於最小距離分類的方法是將待判斷的樣本x與所得到的標準樣本進行計算,然後根據所得的距離進行判別,如果樣本x與標準樣本i之間的距離最小,那麼就把樣本x判為。最小距離分類的原理可以表示為:
對任何,如果有, ,則將樣本x歸類為與同類,即。這裡的距離函式可以是歐氏距離、馬氏距離或其他距離函式,對於兩個樣本x和y,具體的距離函式表示式如下:
(1) 歐式距離(ehclideandistance)
(4-21)
其中,d為樣本x,y的維數,分別是樣本x,y的第i個分量。
(2) 明式距離(mahalanbisdistance)
4-22)
其中,m為樣本的均值樣本,∑為樣本的協方差矩陣。
(3) 明式距離(mahalanbisdistance)
(4-23)
其中,m為正整數。距離函式還有很多,可以根據實際的需要選擇不同的距離函式,具體的可以參考相關的書籍資料(汪增幅,2010)。
基於最小距離的分類方法其實已經假設了乙個理想的條件,就是每個標準樣本都能準確的表達每類樣本的模式。但在實際的情況下,每類樣本都有可能受到雜訊等其他干擾因素影響,導致同一類別的樣本分散在乙個較大的範圍空間上,這時最近距離分類器就無法準確完成分類的目標了。為了當樣本在較大空間上分別時仍然能保持乙個良好的分類效果,最近鄰分類方法被提出。
該方法是在所有訓練樣本集合中尋找到與待分類的樣本最鄰近的那個樣本類別。該方法首先要計算出各類別集合與待測樣本的最小距離,即:
, i=1,2,…,n(4-24)
其中,為第i類的樣本數。最近鄰法的分類準則如下: 當時,,,則將樣本x判別為類。
最近鄰法雖然簡單且比較實用,但是其計算量大、儲存代價較高,此外還受樣本雜訊汙染、畸變點影響較大,從而造成誤判的情況發生。鑑於上述問題,一種折中的方法是k-近鄰法,它是最近鄰法的一種拓展方法。該方法是先計算出待測樣本x到所有庫中每乙個訓練樣本的距離,並按照距離的大小將其進行排序。
然後從中選取k個與測試樣本x最近的訓練樣本,並他們進行類別數統計,將k個訓練樣本中同一類別得票數最多的類別即為測試樣本的類別。假設有n類,所得到的k個樣本中第i類有,判別規則可以表示為:
對於任何
其中,.
從上面的介紹我們不難看出,相對應於最近鄰法,k-近鄰法利用了更多的樣本資訊來判斷樣本類別。通常k要選取的大一些,這樣可以避免由於雜訊造成誤判的發生。圖4.3為近鄰法分類示意圖。
圖4.3k-近鄰法示意圖
從圖可以看出,待識別樣本被乙個類的畸變點干擾,如果採用最近鄰法的話就會產生誤分的情況的發生。採用k最近鄰法,選擇k=3,這是類得到2票,而僅僅得到1票,這時待測樣本歸類為。這樣可以避免雜訊樣本的干擾,使得能夠正確分類。
機器學習演算法總結K近鄰
k近鄰 k nearest neighbor,k nn 是一種基本的 有監督學習的分類方法,於1968年由cover和hart提出,其用於判斷某個物件的類別。k近鄰的輸入為物件特徵向量,對應於特徵空間上的點 輸出為物件的類別。k近鄰演算法例項引入 圖1.1 k近鄰例項 如上圖所示,有兩類不同的樣本資...
K201603《智財權法專》複習題
廈門大學網路教育2015 2016學年第二學期 智財權法 專科 課程複習題 智財權部分 一 智財權概念 二 智財權的性質 第一部分著作權 一 著作權的概念 二 著作權與相關民事權利的區別 一 著作權與所有權 二 著作權與專利權 三 著作權與商標權 三 著作權客體 不適用著作權法的作品 四 著作權主體...