最近鄰演算法

Ⅰ 什麼叫做knn演算法

在模式識別領域中，最近鄰居法（KNN演算法，又譯K-近鄰演算法）是一種用於分類和回歸的非參數統計方法。

在這兩種情況下，輸入包含特徵空間（Feature Space）中的k個最接近的訓練樣本。

1、在k-NN分類中，輸出是一個分類族群。一個對象的分類是由其鄰居的「多數表決」確定的，k個最近鄰居（k為正整數，通常較小）中最常見的分類決定了賦予該對象的類別。若k=1，則該對象的類別直接由最近的一個節點賦予。

2、在k-NN回歸中，輸出是該對象的屬性值。該值是其k個最近鄰居的值的平均值。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一種基於實例的學習，或者是局部近似和將所有計算推遲到分類之後的惰性學習。k-近鄰演算法是所有的機器學習演算法中最簡單的之一。

無論是分類還是回歸，衡量鄰居的權重都非常有用，使較近鄰居的權重比較遠鄰居的權重大。例如，一種常見的加權方案是給每個鄰居權重賦值為1/ d，其中d是到鄰居的距離。

鄰居都取自一組已經正確分類（在回歸的情況下，指屬性值正確）的對象。雖然沒要求明確的訓練步驟，但這也可以當作是此演算法的一個訓練樣本集。

k-近鄰演算法的缺點是對數據的局部結構非常敏感。

K-均值演算法也是流行的機器學習技術，其名稱和k-近鄰演算法相近，但兩者沒有關系。數據標准化可以大大提高該演算法的准確性。

參數選擇

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一個較好的K值能通過各種啟發式技術（見超參數優化）來獲取。

雜訊和非相關性特徵的存在，或特徵尺度與它們的重要性不一致會使K近鄰演算法的准確性嚴重降低。對於選取和縮放特徵來改善分類已經作了很多研究。一個普遍的做法是利用進化演算法優化功能擴展，還有一種較普遍的方法是利用訓練樣本的互信息進行選擇特徵。

在二元（兩類）分類問題中，選取k為奇數有助於避免兩個分類平票的情形。在此問題下，選取最佳經驗k值的方法是自助法。

Ⅱ 急求最近鄰演算法的半監督學習演算法對vehicle數據分類的matlab程序

• 嗯嗯嗯
  

Ⅲ 使用Node.js如何實現K最近鄰分類演算法

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

for (var i in this.samples)
{
// 如果發現沒有類型的樣本
if ( ! this.samples[i].type)
{
// 初始化未知樣本的鄰居
this.samples[i].neighbors = [];
// 生成鄰居集
for (var j in this.samples)
{
// 如果碰到未知樣本 跳過
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 計算所有鄰居與預測樣本的距離
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有鄰居按距離排序
this.samples[i].sortByDistance();
// 猜測預測樣本類型
this.samples[i].guessType(this.k);
}
}
};
最後分別計算10倍交叉驗證和留一法交叉驗證的精度。
留一法就是每次只留下一個樣本做測試集，其它樣本做訓練集。
K倍交叉驗證將所有樣本分成K份，一般均分。取一份作為測試樣本，剩餘K-1份作為訓練樣本。這個過程重復K次，最後的平均測試結果可以衡量模型的性能。
k倍驗證時定義了個方法先把數組打亂隨機擺放。
// helper函數 將數組里的元素隨機擺放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩餘測試代碼好寫，這里就不貼了。
測試結果為
用餘弦距離等計算方式可能精度會更高。
3. 總結
knn演算法非常簡單，但卻能在很多關鍵的地方發揮作用並且效果非常好。缺點就是進行分類時要掃描所有訓練樣本得到距離，訓練集大的話會很慢。
可以用這個最簡單的分類演算法來入高大上的ML的門，會有點小小的成就感。

Ⅳ 機器學習中演算法的優缺點之最近鄰演算法

機器學習中有個演算法是十分重要的，那就是最近鄰演算法，這種演算法被大家稱為KNN。我們在學習機器學習知識的時候一定要學習這種演算法，其實不管是什麼演算法都是有自己的優缺點的，KNN演算法也不例外，在這篇文章中我們就詳細的給大家介紹一下KNN演算法的優缺點，大家一定要好好學起來喲。
說到KNN演算法我們有必要說一下KNN演算法的主要過程，KNN演算法的主要過程有四種，第一就是計算訓練樣本和測試樣本中每個樣本點的距離，第二個步驟就是對上面所有的距離值進行排序(升序)。第三個步驟就是選前k個最小距離的樣本。第四個步驟就是根據這k個樣本的標簽進行投票，得到最後的分類類別。
那麼大家是否知道如何選擇一個最佳的K值，這取決於數據。一般情況下，在分類時較大的K值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。一般來說，一個較好的K值可通過各種啟發式技術來獲取，比如說交叉驗證。另外雜訊和非相關性特徵向量的存在會使K近鄰演算法的准確性減小。近鄰演算法具有較強的一致性結果，隨著數據趨於無限，演算法保證錯誤率不會超過貝葉斯演算法錯誤率的兩倍。對於一些好的K值，K近鄰保證錯誤率不會超過貝葉斯理論誤差率。
那麼KNN演算法的優點是什麼呢？KNN演算法的優點具體體現在六點，第一就是對數據沒有假設，准確度高，對outlier不敏感。第二就是KNN是一種在線技術，新數據可以直接加入數據集而不必進行重新訓練。第三就是KNN理論簡單，容易實現。第四就是理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。第五就是可用於非線性分類。第六就是訓練時間復雜度為O(n)。由此可見，KNN演算法的優點是有很多的。
那麼KNN演算法的缺點是什麼呢？這種演算法的缺點具體體現在六點，第一就是樣本不平衡時，預測偏差比較大。第二就是KNN每一次分類都會重新進行一次全局運算。第三就是k值大小的選擇沒有理論選擇最優，往往是結合K-折交叉驗證得到最優k值選擇。第四就是樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）效果差。第五就是需要大量內存。第六就是對於樣本容量大的數據集計算量比較大。
正是由於這些優點和缺點，KNN演算法應用領域比較廣泛，在文本分類、模式識別、聚類分析，多分類領域中處處有KNN演算法的身影。
在這篇文章中我們給大家介紹了很多關於KNN演算法的相關知識，通過對這些知識的理解相信大家已經知道該演算法的特點了吧，希望這篇文章能夠幫助大家更好的理解KNN演算法。

Ⅳ 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 近鄰搜索，這在特徵空間維數大及訓練數據容量大時非常必要。

Ⅵ 最近鄰法的java實現

packageKNN;

importjava.io.BufferedReader;
importjava.io.File;
importjava.io.FileReader;
importjava.util.ArrayList;
importjava.util.List;

publicclassTestKNN{

	/**
	*@paramargs
	*/
	publicstaticvoidmain(String[]args){
		TestKNNt=newTestKNN();
		Stringdatafile="訓練數據1.txt";
		Stringtestfile="測試數據1.txt";
		try{
			List<List<Double>>datas=newArrayList<List<Double>>();
			List<List<Double>>testDatas=newArrayList<List<Double>>();
			t.read(datas,datafile);
			t.read(testDatas,testfile);
			KNNknn=newKNN();
			for(inti=0;i<testDatas.size();i++){
				List<Double>test=testDatas.get(i);
				System.out.print("測試元組:");
				for(intj=0;j<test.size();j++){
					System.out.print(test.get(j)+"");
				}
				System.out.print("類別為:");
				System.out.println(Math.round(Float.parseFloat((knn.knn(datas,
						test,4)))));//返回最接近參數的int
			}
		}catch(Exceptione){
			e.printStackTrace();
		}

	}

	publicvoidread(List<List<Double>>datas,Stringpath){
		try{
			BufferedReaderbr=newBufferedReader(newFileReader(
					newFile(path)));
			Stringdata=br.readLine();
			List<Double>l=null;
			while(data!=null){
				Stringt[]=data.split("");
				l=newArrayList<Double>();
				for(inti=0;i<t.length;i++){
					l.add(Double.parseDouble(t[i]));
				}
				datas.add(l);
				data=br.readLine();
			}
		}catch(Exceptione){
			e.printStackTrace();
		}
	}

}

packageKNN;

importjava.util.ArrayList;
importjava.util.Comparator;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;
importjava.util.PriorityQueue;

/**
*KNN演算法主體類
*/
publicclassKNN{
	/**
	*設置優先順序隊列的比較函數，距離越大，優先順序越高
	*/
	privateComparator<KNNNode>comparator=newComparator<KNNNode>(){
		publicintcompare(KNNNodeo1,KNNNodeo2){
			if(o1.getDistance()>=o2.getDistance()){
				return1;
			}else{
				return0;
			}
		}
	};

	/**
	*獲取K個不同的隨機數
	*
	*@paramk
	*隨機數的個數
	*@parammax
	*隨機數最大的范圍
	*@return生成的隨機數數組
	*/
	publicList<Integer>getRandKNum(intk,intmax){
		List<Integer>rand=newArrayList<Integer>(k);
		for(inti=0;i<k;i++){
			inttemp=(int)(Math.random()*max);
			if(!rand.contains(temp)){
				rand.add(temp);
			}else{
				i--;
			}
		}
		returnrand;
	}

	/**
	*計算測試元組與訓練元組之前的距離
	*
	*@paramd1
	*測試元組
	*@paramd2
	*訓練元組
	*@return距離值
	*/
	publicdoublecalDistance(List<Double>d1,List<Double>d2){
		doubledistance=0.00;
		for(inti=0;i<d1.size();i++){
			distance+=(d1.get(i)-d2.get(i))*(d1.get(i)-d2.get(i));
		}
		returnMath.sqrt(distance);
	}

	/**
	*執行KNN演算法，獲取測試元組的類別
	*
	*@paramdatas
	*訓練數據集
	*@paramtestData
	*測試元組
	*@paramk
	*設定的K值
	*@return測試元組的類別
	*/
	publicStringknn(List<List<Double>>datas,List<Double>testData,intk){
		ArrayList<KNNNode>alKN=newArrayList<KNNNode>();
		for(inti=0;i<k;i++){
			List<Double>currData=datas.get(i);
			Stringc=currData.get(currData.size()-1).toString();
			KNNNodenode=newKNNNode(i,calDistance(testData,currData),c);
			alKN.add(node);
		}
		for(inti=k;i<datas.size();i++){
			List<Double>t=datas.get(i);
			doubledistance=calDistance(testData,t);
			for(intj=0;j<alKN.size();j++){
				if((alKN.get(j).getDistance())>=distance){
					alKN.remove(j);
					alKN.add(newKNNNode(i,distance,t.get(t.size()-1)
							.toString()));
					break;
				}
			}

		}

		returngetMostClass(alKN);
	}

	/**
	*獲取所得到的k個最近鄰元組的多數類
	*
	*@parampq
	*存儲k個最近近鄰元組的優先順序隊列
	*@return多數類的名稱
	*/
	privateStringgetMostClass(ArrayList<KNNNode>alKN){
		Map<String,Integer>classCount=newHashMap<String,Integer>();
		for(inti=0;i<alKN.size();i++){
			KNNNodenode=alKN.remove(i);
			Stringc=node.getC();
			if(classCount.containsKey(c)){
				classCount.put(c,classCount.get(c)+1);
			}else{
				classCount.put(c,1);
			}
		}
		intmaxIndex=-1;
		intmaxCount=0;
		Object[]classes=classCount.keySet().toArray();
		for(inti=0;i<classes.length;i++){
			if(classCount.get(classes[i])>maxCount){
				maxIndex=i;
				maxCount=classCount.get(classes[i]);
			}
		}
		returnclasses[maxIndex].toString();
	}
}

packageKNN;

/**
*KNN結點類，用來存儲最近鄰的k個元組相關的信息
*/
publicclassKNNNode{
	privateintindex;//元組標號
	privatedoubledistance;//與測試元組的距離
	privateStringc;//所屬類別

	publicKNNNode(intindex,doubledistance,Stringc){
		super();
		this.index=index;
		this.distance=distance;
		this.c=c;
	}

	publicintgetIndex(){
		returnindex;
	}

	publicvoidsetIndex(intindex){
		this.index=index;
	}

	publicdoublegetDistance(){
		returndistance;
	}

	publicvoidsetDistance(doubledistance){
		this.distance=distance;
	}

	publicStringgetC(){
		returnc;
	}

	publicvoidsetC(Stringc){
		this.c=c;
	}

}

Ⅶ 鄰近演算法的演算法流程

1. 准備數據，對數據進行預處理
2. 選用合適的數據結構存儲訓練數據和測試元組
3. 設定參數，如k
4.維護一個大小為k的的按距離由大到小的優先順序隊列，用於存儲最近鄰訓練元組。隨機從訓練元組中選取k個元組作為初始的最近鄰元組，分別計算測試元組到這k個元組的距離，將訓練元組標號和距離存入優先順序隊列
5. 遍歷訓練元組集，計算當前訓練元組與測試元組的距離，將所得距離L 與優先順序隊列中的最大距離Lmax
6. 進行比較。若L>=Lmax，則舍棄該元組，遍歷下一個元組。若L < Lmax，刪除優先順序隊列中最大距離的元組，將當前訓練元組存入優先順序隊列。
7. 遍歷完畢，計算優先順序隊列中k 個元組的多數類，並將其作為測試元組的類別。
8. 測試元組集測試完畢後計算誤差率，繼續設定不同的k值重新進行訓練，最後取誤差率最小的k 值。

Ⅷ 鄰近演算法

k-Nearest Neighbor algorithm K最近鄰(k-Nearest Neighbor，KNN)分類演算法，是一個理論上比較成熟的方法。該方法的思路是：如果一個樣本在特徵空間中的k個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。該方法在定類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴於極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，採用這種方法可以較好地避免樣本的不平衡問題。另外，由於 KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該演算法比較適用於樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域採用這種演算法比較容易產生誤分。

Ⅸ 鄰近演算法的介紹

鄰近演算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類演算法是數據挖掘分類技術中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。kNN演算法的核心思想是如果一個樣本在特徵空間中的k個最相鄰的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別，並具有這個類別上樣本的特性。該方法在確定分類決策上只依據最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 kNN方法在類別決策時，只與極少量的相鄰樣本有關。由於kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對於類域的交叉或重疊較多的待分樣本集來說，kNN方法較其他方法更為適合。

Ⅹ 如何結合pca演算法和最近鄰法進行人臉識別

%一個修改後的PCA進行人臉識別的Matlab代碼
% calc xmean,sigma and its eigen decomposition
allsamples=[];%所有訓練圖像
for i=1:40
for j=1:5
a=imread(strcat('D:\rawdata\ORL\s',num2str(i),'\',num2str(j),'.pgm'));
% imshow(a);
b=a(1:112*92); % b是行矢量 1×N,其中N＝10304,提取順序是先列後行,即從上到下,從左到右
b=double(b);
allsamples=[allsamples; b]; % allsamples 是一個M * N 矩陣,allsamples 中每一行數據代表一張圖片,其中M＝200
end
end
samplemean=mean(allsamples); % 平均圖片,1 × N
for i=1:200 xmean(i,:)=allsamples(i,:)-samplemean; % xmean是一個M × N矩陣,xmean每一行保存的數據是「每個圖片數據-平均圖片」
end;
sigma=xmean*xmean'; % M * M 階矩陣
[v d]=eig(sigma);
d1=diag(d);
[d2 index]=sort(d1); %以升序排序
cols=size(v,2);% 特徵向量矩陣的列數
for i=1:cols
vsort(:,i) = v(:,index(cols-i+1) ); % vsort 是一個M*col(注:col一般等於M)階矩陣,保存的是按降序排列的特徵向量,每一列構成一個特徵向量
dsort(i) = d1( index(cols-i+1) ); % dsort 保存的是按降序排列的特徵值,是一維行向量
end %完成降序排列
%以下選擇90%的能量
dsum = sum(dsort);
dsum_extract = 0;
p = 0;
while( dsum_extract/dsum < 0.9)
p = p + 1;
dsum_extract = sum(dsort(1:p));
end
i=1;
% (訓練階段)計算特徵臉形成的坐標系
while (i0)
base(:,i) = dsort(i)^(-1/2) * xmean' * vsort(:,i); % base是N×p階矩陣,除以dsort(i)^(1/2)是對人臉圖像的標准化,詳見《基於PCA的人臉識別演算法研究》p31
i = i + 1;
end
% add by wolfsky 就是下面兩行代碼,將訓練樣本對坐標繫上進行投影,得到一個 M*p 階矩陣allcoor
allcoor = allsamples * base;
accu = 0;
%
for i=1:40
for j=6:10 %讀入40 x 5 副測試圖像
a=imread(strcat('D:\rawdata\ORL\s',num2str(i),'\',num2str(j),'.pgm'));
b=a(1:10304);
b=double(b);
tcoor= b * base; %計算坐標,是1×p階矩陣
for k=1:200
mdist(k)=norm(tcoor-allcoor(k,:));
end;
%三階近鄰
[dist,index2]=sort(mdist);
class1=floor( index2(1)/5 )+1;
class2=floor(index2(2)/5)+1;
class3=floor(index2(3)/5)+1;
if class1~=class2 && class2~=class3
class=class1;
elseif class1==class2
class=class1;
elseif class2==class3
class=class2;
end;
if class==i
accu=accu+1;
end;
end;
end;
accuracy=accu/200 %輸出識別率
函數調用是定義函數,然後用函數名進行調用就可以了