大數(shù)據(jù)十大經(jīng)典算法kNN講解

1、KNN:K最近鄰分類算法K-Nearest Neighbor ClassificationKNN算法怎么來的？KNN算法是怎么來的電影名稱打斗次數(shù)接吻次數(shù)電影類型California Man 3104RomanceHes Not Really into Dudes 2100RomanceBeautiful Woman 181RomanceKevin Longblade 10110ActionRobo Slayer 3000 995ActionAmped II 982Action未知1890Unknown猜猜看：最后一行未知電影屬于什么類型的電影。KNN算法是怎么來的點(diǎn)X坐標(biāo)Y坐標(biāo)點(diǎn)類型A點(diǎn) 3

2、104RomanceB點(diǎn) 2100RomanceC點(diǎn) 181RomanceD點(diǎn) 10110ActionE點(diǎn) 995ActionF點(diǎn) 982ActionG點(diǎn)1890Unknown猜猜看：最后一行未知點(diǎn)屬于什么類型的點(diǎn)。KNN算法是怎么來的想一想：下面圖片中只有三種豆，有三個豆是未知的種類，如何判定他們的種類？1968年，Cover和Hart提出了最初的近鄰法。最近鄰算法提供一種思路，即：未知的豆離哪種豆最近就認(rèn)為未知豆和該豆是同一種類。由此，我們引出最近鄰算法的定義：為了判定未知樣本的類別，以全部訓(xùn)練樣本作為代表點(diǎn)，計算未知樣本與所有訓(xùn)練樣本的距離，并以最近鄰者的類別作為決策未知樣本類別的唯一依

3、據(jù)。但是，最近鄰算法明顯是存在缺陷的，我們來看一個例子。KNN算法是怎么來的問題：有一個未知形狀X(圖中綠色的圓點(diǎn))，如何判斷X是什么形狀?K-最近鄰算法顯然，通過上面的例子我們可以明顯發(fā)現(xiàn)最近鄰算法的缺陷對噪聲數(shù)據(jù)過于敏感，為了解決這個問題，我們可以可以把位置樣本周邊的多個最近樣本計算在內(nèi)，擴(kuò)大參與決策的樣本量，以避免個別數(shù)據(jù)直接決定決策結(jié)果。由此，我們引進(jìn)K-最近鄰算法。KNN算法是用來干什么的 K-最近鄰算法是最近鄰算法的一個延伸?；舅悸肥牵哼x擇未知樣本一定范圍內(nèi)確定個數(shù)的K個樣本，該K個樣本大多數(shù)屬于某一類型，則未知樣本判定為該類型。 下面借助圖形解釋一下。KNN算法的實現(xiàn)步驟算法步

4、驟：算法步驟：step.1-初始化距離為最大值初始化距離為最大值step.2-計算未知樣本和每個訓(xùn)練樣本的距離計算未知樣本和每個訓(xùn)練樣本的距離diststep.3-得到目前得到目前K個最臨近樣本中的最大距離個最臨近樣本中的最大距離maxdiststep.4-如果如果dist小于小于maxdist，則將該訓(xùn)練樣本作為，則將該訓(xùn)練樣本作為K-最近最近鄰樣本鄰樣本step.5-重復(fù)步驟重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的，直到未知樣本和所有訓(xùn)練樣本的距離都算完距離都算完step.6-統(tǒng)計統(tǒng)計K個最近鄰樣本中每個類別出現(xiàn)的次數(shù)個最近鄰樣本中每個類別出現(xiàn)的次數(shù)step.7-選擇出現(xiàn)頻率最大的

5、類別作為未知樣本的類別選擇出現(xiàn)頻率最大的類別作為未知樣本的類別KNN算法的缺陷觀察下面的例子，我們看到，對于位置樣本X，通過KNN算法，我們顯然可以得到X應(yīng)屬于紅點(diǎn)，但對于位置樣本Y，通過KNN算法我們似乎得到了Y應(yīng)屬于藍(lán)點(diǎn)的結(jié)論，而這個結(jié)論直觀來看并沒有說服力。KNN算法的具體實現(xiàn)由上面的例子可見：該算法在分類時有個重要的不足是，當(dāng)樣本不平衡時，即：一個類的樣本容量很大，而其他類樣本數(shù)量很小時，很有可能導(dǎo)致當(dāng)輸入一個未知樣本時，該樣本的K個鄰居中大數(shù)量類的樣本占多數(shù)。 但是這類樣本并不接近目標(biāo)樣本，而數(shù)量小的這類樣本很靠近目標(biāo)樣本。這個時候，我們有理由認(rèn)為該位置樣本屬于數(shù)量小的樣本所屬的一類

6、，但是，KNN卻不關(guān)心這個問題，它只關(guān)心哪類樣本的數(shù)量最多，而不去把距離遠(yuǎn)近考慮在內(nèi)，因此，我們可以采用權(quán)值的方法來改進(jìn)。和該樣本距離小的鄰居權(quán)值大，和該樣本距離大的和該樣本距離小的鄰居權(quán)值大，和該樣本距離大的鄰居權(quán)值則相對較小，由此，將距離遠(yuǎn)近的因素也考慮鄰居權(quán)值則相對較小，由此，將距離遠(yuǎn)近的因素也考慮在內(nèi)，避免因一個樣本過大導(dǎo)致誤判的情況。在內(nèi)，避免因一個樣本過大導(dǎo)致誤判的情況。KNN算法的缺陷從算法實現(xiàn)的過程大家可以發(fā)現(xiàn)，該算法存兩個嚴(yán)重的問題，第一個是需要存儲全部的訓(xùn)練樣本，第二個是需要進(jìn)行繁重的距離計算量。對此，提出以下應(yīng)對策略。KNN算法的改進(jìn)：分組快速搜索近鄰法其基本思想是：將樣

7、本集按近鄰關(guān)系分解成組，給出每組質(zhì)心的位置，以質(zhì)心作為代表點(diǎn)，和未知樣本計算距離，選出距離最近的一個或若干個組，再在組的范圍內(nèi)應(yīng)用一般的knn算法。由于并不是將未知樣本與所有樣本計算距離，故該改進(jìn)算法可以減少計算量，但并不能減少存儲量。KNN算法的改進(jìn)：壓縮近鄰算法利用現(xiàn)在的樣本集，采取一定的算法產(chǎn)生一個新的樣本集，該樣本集擁有比原樣本集少的多的樣本數(shù)量，但仍然保持有對未知樣本進(jìn)行分類的能力?；舅悸罚憾x兩個存儲器，一個用來存放生成的樣本集，稱為output樣本集；另一個用來存放原來的樣本集，稱為original樣本集。 1.初始化：output樣本集為空集，原樣本集存入original樣本集，從original樣本集中任意選擇一個樣本移動到output樣本集中； 2.在original樣本集中選擇第i個樣本，并使用output樣本集中的樣本對其進(jìn)行最近鄰算法分類，若分