基於k近鄰方法演算法的研究綜述

㈠ 什麼是k-最近鄰演算法

K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成正比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

㈡ k近鄰演算法特徵值非數字

k-近鄰演算法採用測量不同特徵值之間的距離來進行分類。
優點：精度高，對異常值不敏感，無數據輸入假定。缺點：計算復雜度高、空間復雜度高。適用數據范圍：數值型和分類型。原理：首先，我們必須得有一份含有分類標簽的數據集，為訓練數據集。比如我們要預測用戶是否會流失，那麼分類標簽就是流失和未流失。然後有一份新的數據集，這份數據集並沒有分類標簽，k-近鄰演算法就會將新的數據集和訓練數據集進行比較，從訓練數據集中選出與新數據集每個數據最相近的K個數據，查看這K個數據所屬標簽哪類最多，比如流失，就把新數據集中的那個數據分類為流失。怎麼判斷是否相近呢？K-近鄰是計算不同數據的距離。k-近鄰演算法的原理偽代碼。
對未知類別屬性的數據集中的每個數據點依次執行以下操作：(1)計算已知類別數據集中的點與當前點之間的距離。(2)按照距離遞增次序排序。(3)選出與當前距離最近的K個點。(4)統計出K個點所屬類別的頻率。(5)返回K個點出現頻率最高的的類別作為當前點的預測類別

㈢ k近鄰演算法的介紹

K最近鄰(k-Nearest Neighbour，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。

㈣ k近鄰演算法精確度的提高有什麼科學性，先進性和獨特之處

K近鄰(k-Nearest Neighbour，KNN)分類演算法，是一個理論上比較成熟的方法，也是最簡單的機器學習演算法之一。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。
K-近鄰法就是一種基於文本特徵向量空間模型表示的文本分類方法,有很多優點,演算法簡單,易於實現,分類精度較高。

㈤ k近鄰演算法的案例介紹

如 上圖所示，有兩類不同的樣本數據，分別用藍色的小正方形和紅色的小三角形表示，而圖正中間的那個綠色的圓所標示的數據則是待分類的數據。也就是說，現在， 我們不知道中間那個綠色的數據是從屬於哪一類（藍色小正方形or紅色小三角形），下面，我們就要解決這個問題：給這個綠色的圓分類。我們常說，物以類聚，人以群分，判別一個人是一個什麼樣品質特徵的人，常常可以從他/她身邊的朋友入手，所謂觀其友，而識其人。我們不是要判別上圖中那個綠色的圓是屬於哪一類數據么，好說，從它的鄰居下手。但一次性看多少個鄰居呢？從上圖中，你還能看到：
如果K=3，綠色圓點的最近的3個鄰居是2個紅色小三角形和1個藍色小正方形，少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於紅色的三角形一類。 如果K=5，綠色圓點的最近的5個鄰居是2個紅色三角形和3個藍色的正方形，還是少數從屬於多數，基於統計的方法，判定綠色的這個待分類點屬於藍色的正方形一類。 於此我們看到，當無法判定當前待分類點是從屬於已知分類中的哪一類時，我們可以依據統計學的理論看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為(或分配)到權重更大的那一類。這就是K近鄰演算法的核心思想。
KNN演算法中，所選擇的鄰居都是已經正確分類的對象。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。
KNN 演算法本身簡單有效，它是一種 lazy-learning 演算法，分類器不需要使用訓練集進行訓練，訓練時間復雜度為0。KNN 分類的計算復雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間復雜度為O(n)。
KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。由於KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。
K 近鄰演算法使用的模型實際上對應於對特徵空間的劃分。K 值的選擇，距離度量和分類決策規則是該演算法的三個基本要素： K 值的選擇會對演算法的結果產生重大影響。K值較小意味著只有與輸入實例較近的訓練實例才會對預測結果起作用，但容易發生過擬合；如果 K 值較大，優點是可以減少學習的估計誤差，但缺點是學習的近似誤差增大，這時與輸入實例較遠的訓練實例也會對預測起作用，是預測發生錯誤。在實際應用中，K 值一般選擇一個較小的數值，通常採用交叉驗證的方法來選擇最優的 K 值。隨著訓練實例數目趨向於無窮和 K=1 時，誤差率不會超過貝葉斯誤差率的2倍，如果K也趨向於無窮，則誤差率趨向於貝葉斯誤差率。 該演算法中的分類決策規則往往是多數表決，即由輸入實例的 K 個最臨近的訓練實例中的多數類決定輸入實例的類別 距離度量一般採用 Lp 距離，當p=2時，即為歐氏距離，在度量之前，應該將每個屬性的值規范化，這樣有助於防止具有較大初始值域的屬性比具有較小初始值域的屬性的權重過大。 KNN演算法不僅可以用於分類，還可以用於回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產生的影響給予不同的權值(weight)，如權值與距離成反比。該演算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本佔多數。 該演算法只計算「最近的」鄰居樣本，某一類的樣本數量很大，那麼或者這類樣本並不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數量並不能影響運行結果。可以採用權值的方法（和該樣本距離小的鄰居權值大）來改進。
該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。
實現 K 近鄰演算法時，主要考慮的問題是如何對訓練數據進行快速 K 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

㈥ KNN演算法，k近鄰

1' 然後直接看文檔實例即可。 2，一般均分; 根據k值截取鄰居裡面前k個 for (var i in this。留一法就是每次只留下一個樣本做測試集, k) { for (var i in this; var b = neighbor.i - this; 判斷鄰居里哪個樣本類型多 if(types['，這里是把剛生成的數據結構里的對象傳入,'.d.d - this.samples) { /;/ /，所以我們可以判斷未知樣本類型為紅色三角形;/ var c = neighbor; rCount.a，我們這里採用歐式距離.neighbors[i];/ 把所有鄰居按距離排序 this.log(err; } }.prototype; } else { this.sortByDistance = function() { this; sIdx++ ){ var sht = bk, e; //，如果k=3;.e - this.push( new Sample(this; var d = neighbor; }): 0 };data; 檢驗屬性是否屬於對象自身 if (object, this.random() - 0，諸如決策樹歸納;],'，有一個藍色的三正方形。 k倍驗證時定義了個方法先把數組打亂隨機擺放; rIdx 有兩種類別 1和-1 var types = { '，它被廣泛應用於模式識別;: 0.push(sample); var j = neighbor; } /types['.type) continue，而訓練我們識別的過程就對應於泛化這一概念; 猜測預測樣本類型 this..type = '.f; 初始化未知樣本的鄰居 this.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k),'.measureDistances = function(a.k).f; 把傳過來的對象上的屬性克隆到新創建的樣本上 for (var key in object) { //.open('。 3;/，最後猜測類型;/.j;/.determineUnknown = function() { for (var i in this.sortByDistance().type = ',cIdx),', '.e.samples; /.add = function(sample) { this;/，我們還是能認得出來它;/.measureDistances(this;/.samples[i];b' 最後分別計算10倍交叉驗證和留一法交叉驗證的精度;，生成一個新的樣本, b。knn基於類比學習.column，不只是顏色這一個標簽.g, this, this.h; types[neighbor; 生成鄰居集 for (var j in this; 將鄰居樣本根據與預測樣本間距離排序 Sample，貝葉斯分類等都是急切學習法的例子，當然也不能過度調教2333;.neighbors = [].samples = []; 判斷被預測樣本類別 Sample，過度調教它要把其他手機也認成iphone那就不好了;/，然後再來看上面的理論應該會明白很多;/ node;-1', cCount = sht。惰性學習法（lazy learner）正好與其相反;/,'e', d; for(var cIdx = 0，是不是某些同學想大喊一聲.sheets[sIdx].prototype.count，調用未知樣本原型上的方法來計算鄰居到它的距離;)。最後是樣本集的原型上定義一個方法; return; helper函數 將數組里的元素隨機擺放 function ruffle(array) { array;/, rCount = sht，把所有鄰居按距離排序.a;} var shtCount = bk，並對新的輸入給出合理的判斷.neighbors.samples[i].neighbors) { var neighbor = this，直到給定一個待接受分類的新元組之後.samples[j]，使用truetype和type來預測樣本類型和對比判斷是否分類成功;k'/ 計算歐式距離 neighbor; }.distance - b, this，才開始根據訓練元組構建分類模型;/ 將文件中的數據映射到樣本的屬性var map = [' } } } 再定義一個樣本集的構造函數 /。可以用這個最簡單的分類演算法來入高大上的ML的門，我們選取距離其最近的k個幾何圖形源於數據挖掘的一個作業，學習後的模型已經就緒。這k個訓練元祖就是待預測元組的k個最近鄰.sort(function (a;]>，樣本有1和-1兩種類型, g.push(item); /.prototype。主要是因為我們在腦海像給這個蘋果貼了很多標簽一樣。 / } 然後我們會在樣本的原型上定義很多方法.k - this; 如果碰到未知樣本 跳過 if ( ;， 這里用Node,'h' }) } 剩餘測試代碼好寫.k)，需要我們好好調教它; var k = neighbor;/ }).samples[i], j.k，多次被教後再看到的時候我們自己就能認出來這些事物了;/，其它樣本做訓練集，找出最接近未知元組的k個訓練元組,'/.f - this; 計算所有鄰居與預測樣本的距離 this，所以稱為急切學習法! this。 /.g;g'/.samples[i].b;，我們可以看到有兩個紅色的三角形.row; / SampleSet管理所有樣本 參數k表示KNN中的kvar SampleSet = function(k) { this; } } 注意到我這里的數據有a-k共11個屬性，訓練集大的話會很慢; } } }.distance。缺點就是進行分類時要掃描所有訓練樣本得到距離; Sample表示一個樣本 var Sample = function (object) { /，最後的平均測試結果可以衡量模型的性能.cell(rIdx, b) { return a.sort(function (a。本文的knn演算法就是一種惰性學習法。 / for(var rIdx = 0.j - this，惰性學習法在分類進行時做更多的工作;，可能還有蘋果的形狀大小等等, c，包含未知類型樣本 SampleSet。這些標簽讓我們看到蘋果的時候不會誤認為是橘子;/ for(var sIdx = 0.c;node-xlrd'.b, h; } data;1'.samples) { /，由於紅色三角形所佔比例高，這里的距離就是我們根據樣本的特徵所計算出來的數值, function(err。那麼求距離其實不同情況適合不同的方法。取一份作為測試樣本，在此之前只是存儲著訓練元組。這個過程重復K次; var a = neighbor, err! this.neighbors.message)，這k個幾何圖形就是未知類型樣本的鄰居.count;.slice(0;i'.c - this; shtCount。 K倍交叉驗證將所有樣本分成K份;a'.prototype,'，剩餘K-1份作為訓練樣本;-1'，這里的k即是knn中的k; cIdx++){ item[map[cIdx]] = sht; sIdx <，搜索模式空間，但蠢計算機就不知道怎麼做了; }。 /，但卻能在很多關鍵的地方發揮作用並且效果非常好.h - this，綠色的圓代表未知樣本。 k-nearest-neighbor-classifier 還是先嚴謹的介紹下; var e = neighbor，這樣每個樣本都可以用這些方法.k = k; 讀取文件 xls。所以特徵就是提取對象的信息.samples[i];/ var g = neighbor; 如果發現沒有類型的樣本 if ( ，把數據解析後插入到自己的數據結構里;! 還是來通俗的解釋下。綜上所述knn分類的關鍵點就是k的選取和距離的計算.samples[i].b - this。擴展到一般情況時，將未知的新元組與訓練元組進行對比; 等文件讀取完畢後 執行測試 run().g - this.distance = Math; var h = neighbor.prototype，這里就不貼了. 總結 knn演算法非常簡單;/.5, this.d, this;d'.neighbors.speak Chinese，即可預測樣本類型，並生成他們的鄰居集; 然後定義一個構造函數Sample表示一個樣本，這個紅的是蘋果等等。 /.xls', k)) { var neighbor = this; this, this.neighbors[i];1'j'.c; var i = neighbor;/ this; var f = neighbor.hasOwnProperty(key)) { this[key] = object[key].samples[j]) )，這是小鴨子。測試結果為用餘弦距離等計算方式可能精度會更高, b) { return Math;c'。其實這些標簽就對應於機器學習中的特徵這一重要概念.guessType(this。 var data = [];/, i.e,bk){ if(err) {console。 balabala了這么多。小時候媽媽會指著各種各樣的東西教我們，這對於我們人來說非常簡單，泛化就是學習到隱含在這些特徵背後的規律, this;;]){ this; } /.sheet; /。急切學習法（eager learner）是在接受待分類的新元組之前就構造了分類模型; rIdx++){ var item = {};/.name，再找出距離未知類型樣本最近的K個樣本.a - this.js用來讀取xls文件的包 var xls = require('-1'.h; / / 將樣本加入樣本數組 SampleSet. 實現我的數據是一個xls文件。一台iphone戴了一個殼或者屏幕上有一道劃痕，那麼我去npm搜了一下選了一個叫node-xlrd的包直接拿來用，該方法可以在整個樣本集里尋找未知類型的樣本; 計算樣本間距離 採用歐式距離 Sample; } } /.type) { / 構建總樣本數組.guessType = function(k) { /，其實這就叫過度泛化,'f'，那我們哼哧哼哧的看著應答著,', f，所以稱為惰性學習法.trueType] += 1; cIdx <，會有點小小的成就感; cCount。我們可以看上圖.js技術來實現一下這個機器學習中最簡單的演算法之一k-nearest-neighbor演算法(k最近鄰分類法)，急著對未知的元組進行分類.count.i

㈦ K近鄰聚類演算法

K近鄰聚類演算法就是利用k近鄰法來進行聚類操作的。

㈧ k近鄰演算法的概念介紹

用官方的話來說，所謂K近鄰演算法，即是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例（也就是上面所說的K個鄰居）， 這K個實例的多數屬於某個類，就把該輸入實例分類到這個類中。根據這個說法，咱們來看下引自維基網路上的一幅圖：