本文不對KNN算法做過多的理論上的解釋，主要是針對問題，進行算法的設計和代碼的注解。

KNN算法：

優點：精度高、對異常值不敏感、無數據輸入假定。

缺點：計算復雜度高、空間復雜度高。

適用數據范圍：數值型和標稱性。

工作原理：存在一個樣本數據集合，也稱作訓練樣本集，并且樣本集中每個數據都存在標簽（所屬分類），即我們知道樣本集中每一個數據與所屬分類的對應關系。輸入沒有標簽的新數據（testData）后，將新數據的每個特征與樣本集中數據對應的特征進行比較，然后算法提取樣本集中特征最相似數據（最近鄰）的分類標簽。一般來說，我們只選擇樣本數據及中前ｋ個最相似的數據，這就是k-近鄰算法中k的出處，通常k選擇不大于20的整數。最后，選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。

K-近鄰算法的一般流程：

（1）收集數據：可以使用任何方法

（2）準備數據：距離計算所需要的數值，最好是結構化的數據格式

（3）分析數據：可以使用任何方法

（4）訓練算法：此步驟不適用k-鄰近算法

（5）測試算法：計算錯誤率

（6）使用算法：首先需要輸入樣本數據和結構化的輸出結果，然后運行k-近鄰算法判定輸入數據分別屬于哪個分類，最后應用對計算出的分類執行后續的處理。

?

問題一：現在我們假設一個場景，就是要為坐標上的點進行分類，如下圖所示：

?

上圖一共12個左邊點，每個坐標點都有相應的坐標(x,y)以及它所屬的類別A/B，那么現在需要做的就是給定一個點坐標(x1,y1)，判斷它屬于的類別A或者B。

所有的坐標點在data.txt文件中：

0.0 1.1 A
1.0 1.0 A
2.0 1.0 B
0.5 0.5 A
2.5 0.5 B
0.0 0.0 A
1.0 0.0 A 
2.0 0.0 B
3.0 0.0 B
0.0 -1.0 A
1.0 -1.0 A
2.0 -1.0 B

step1：通過類的默認構造函數去初始化訓練數據集dataSet和測試數據testData。

step2：用get_distance()來計算測試數據testData和每一個訓練數據dataSet[index]的距離，用map_index_dis來保存鍵值對<index,distance>,其中index代表第幾個訓練數據，distance代表第index個訓練數據和測試數據的距離。

step3：將map_index_dis按照value值（即distance值）從小到大的順序排序，然后取前k個最小的value值，用map_label_freq來記錄每一個類標簽出現的頻率。

step4：遍歷map_label_freq中的value值，返回value最大的那個key值，就是測試數據屬于的類。

看一下代碼KNN_0.cc：

#include<iostream>
#include<map>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<fstream>using namespace std;typedef char tLabel;
typedef double tData;
typedef pair<int,double>  PAIR;
const int colLen = 2;
const int rowLen = 12;
ifstream fin;
ofstream fout;class KNN
{private:tData dataSet[rowLen][colLen];//dataSet[12][2]tLabel labels[rowLen];//labels[12]	保存樣本中每個數據的分類tData testData[colLen];//testData[2]int k;//只選擇樣本數據及中前ｋ個最相似的數據，這就是k-近鄰算法中k的出處，通常k選擇不大于20的整數map<int,double> map_index_dis;//map_index_dis來保存鍵值對<index,distance> index代表第幾個訓練數據，distance代表第index個訓練數據和測試數據的距離map<tLabel,int> map_label_freq;double get_distance(tData *d1,tData *d2);//get_distance()來計算測試數據 testData 和每一個訓練數據dataSet[index]的距離public:KNN(int k);void get_all_distance();void get_max_freq_label();struct CmpByValue{bool operator() (const PAIR& lhs,const PAIR& rhs){return lhs.second < rhs.second;}};	
};KNN::KNN(int k)
{this->k = k;fin.open("data.txt");if(!fin){cout<<"can not open the file data.txt"<<endl;exit(1);}/* input the dataSet */ for(int i=0;i<rowLen;i++)//rowLen = 12{for(int j=0;j<colLen;j++)//colLen=2{fin>>dataSet[i][j];}fin>>labels[i];}cout<<"please input the test data :"<<endl;/* inuput the test data */for(int i=0;i<colLen;i++)cin>>testData[i];}/** calculate the distance between test data and dataSet[i]*/
double KNN:: get_distance(tData *d1,tData *d2)
{double sum = 0;for(int i=0;i<colLen;i++){sum += pow( (d1[i]-d2[i]) , 2 );}//	cout<<"the sum is = "<<sum<<endl;return sqrt(sum);
}/** calculate all the distance between test data and each training data*/
void KNN:: get_all_distance()
{double distance;int i;for(i=0;i<rowLen;i++){distance = get_distance(dataSet[i],testData);//<key,value> => <i,distance>map_index_dis[i] = distance;//存放所有點dataSet 與 測試點 testData 之間的距離}//traverse the map to print the index and distancemap<int,double>::const_iterator it = map_index_dis.begin();while(it!=map_index_dis.end()){cout<<"index = "<<it->first<<" distance = "<<it->second<<endl;it++;}
}/** check which label the test data belongs to to classify the test data */
void KNN:: get_max_freq_label()
{//transform the map_index_dis to vec_index_disvector<PAIR> vec_index_dis( map_index_dis.begin(),map_index_dis.end() );//sort the vec_index_dis by distance from low to high to get the nearest data 將map_index_dis按照value值（即distance值）從小到大的順序排序sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());//測試點與所有點之間的距離排序//取前k個最小的value值，用 map_label_freq 來記錄每一個類標簽出現的頻率。for(int i=0;i<k;i++){cout<<"the index = "<<vec_index_dis[i].first<<" the distance = "<<vec_index_dis[i].second<<" the label = "<<labels[vec_index_dis[i].first]<<" the coordinate ( "<<dataSet[ vec_index_dis[i].first ][0]<<","<<dataSet[ vec_index_dis[i].first ][1]<<" )"<<endl;//calculate the count of each labelmap_label_freq[ labels[ vec_index_dis[i].first ]  ]++;}//遍歷 map_label_freq 中的value值，返回value最大的那個key值，就是測試數據屬于的類map<tLabel,int>::const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;//find the most frequent labelwhile( map_it != map_label_freq.end() ){if( map_it->second > max_freq ){max_freq = map_it->second;label = map_it->first;}map_it++;}cout<<"The test data belongs to the "<<label<<" label"<<endl;
}int main()
{int k ;cout<<"please input the k value : "<<endl;cin>>k;KNN knn(k);knn.get_all_distance();knn.get_max_freq_label();system("pause"); return 0;
}

我們來測試一下這個分類器(k=5)：

testData(5.0,5.0):

?

testData(-5.0,-5.0):

?

testData(1.6,0.5):

分類結果的正確性可以通過坐標系來判斷，可以看出結果都是正確的。

?

問題二：使用k-近鄰算法改進約會網站的匹配效果

情景如下：我的朋友海倫一直使用在線約會網站尋找合適自己的約會對象。盡管約會網站會推薦不同的人選，但她沒有從中找到喜歡的人。經過一番總結，她發現曾交往過三種類型的人：

>不喜歡的人

>魅力一般的人

>極具魅力的人

盡管發現了上述規律，但海倫依然無法將約會網站推薦的匹配對象歸入恰當的分類。她覺得可以在周一到周五約會哪些魅力一般的人，而周末則更喜歡與那些極具魅力的人為伴。海倫希望我們的分類軟件可以更好的幫助她將匹配對象劃分到確切的分類中。此外海倫還收集了一些約會網站未曾記錄的數據信息，她認為這些數據更有助于匹配對象的歸類。

海倫已經收集數據一段時間。她把這些數據存放在文本文件datingTestSet.txt（文件鏈接：http://yunpan.cn/QUL6SxtiJFPfN，提取碼：f246）中，每個樣本占據一行，總共有1000行。海倫的樣本主要包含3中特征：

>每年獲得的飛行常客里程數

>玩視頻游戲所耗時間的百分比

>每周消費的冰淇淋公升數

?

數據預處理：歸一化數據

我們可以看到，每年獲取的飛行常客里程數對于計算結果的影響將遠大于其他兩個特征。而產生這種現象的唯一原因，僅僅是因為飛行常客書遠大于其他特征值。但是這三種特征是同等重要的，因此作為三個等權重的特征之一，飛行常客數不應該如此嚴重地影響到計算結果。

處理這種不同取值范圍的特征值時，我們通常采用的方法是數值歸一化，如將取值范圍處理為0到1或者-1到1之間。

公式為：newValue = (oldValue - min) / (max - min)

其中min和max分別是數據集中的最小特征值和最大特征值。我們增加一個auto_norm_data函數來歸一化數據。

同事還要設計一個get_error_rate來計算分類的錯誤率，選總體數據的10%作為測試數據，90%作為訓練數據，當然也可以自己設定百分比。

其他的算法設計都與問題一類似。

?

代碼如下KNN_2.cc（k=7）：

?

/* add the get_error_rate function */#include<iostream>
#include<map>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<fstream>using namespace std;typedef string tLabel;
typedef double tData;
typedef pair<int,double>  PAIR;
const int MaxColLen = 10;
const int MaxRowLen = 10000;
ifstream fin;
ofstream fout;class KNN
{
private:tData dataSet[MaxRowLen][MaxColLen];tLabel labels[MaxRowLen];tData testData[MaxColLen];int rowLen;int colLen;int k;int test_data_num;map<int,double> map_index_dis;map<tLabel,int> map_label_freq;double get_distance(tData *d1,tData *d2);
public:KNN(int k , int rowLen , int colLen , char *filename);void get_all_distance();tLabel get_max_freq_label();void auto_norm_data();void get_error_rate();struct CmpByValue{bool operator() (const PAIR& lhs,const PAIR& rhs){return lhs.second < rhs.second;}};~KNN();	
};KNN::~KNN()
{fin.close();fout.close();map_index_dis.clear();map_label_freq.clear();
}KNN::KNN(int k , int row ,int col , char *filename)
{this->rowLen = row;this->colLen = col;this->k = k;test_data_num = 0;fin.open(filename);fout.open("result.txt");if( !fin || !fout ){cout<<"can not open the file"<<endl;exit(0);}for(int i=0;i<rowLen;i++){for(int j=0;j<colLen;j++){fin>>dataSet[i][j];fout<<dataSet[i][j]<<" ";}fin>>labels[i];fout<<labels[i]<<endl;}}void KNN:: get_error_rate()
{int i,j,count = 0;tLabel label;cout<<"please input the number of test data : "<<endl;cin>>test_data_num;for(i=0;i<test_data_num;i++){for(j=0;j<colLen;j++){testData[j] = dataSet[i][j];		}get_all_distance();label = get_max_freq_label();if( label!=labels[i] )count++;map_index_dis.clear();map_label_freq.clear();}cout<<"the error rate is = "<<(double)count/(double)test_data_num<<endl;
}double KNN:: get_distance(tData *d1,tData *d2)
{double sum = 0;for(int i=0;i<colLen;i++){sum += pow( (d1[i]-d2[i]) , 2 );}//cout<<"the sum is = "<<sum<<endl;return sqrt(sum);
}void KNN:: get_all_distance()
{double distance;int i;for(i=test_data_num;i<rowLen;i++){distance = get_distance(dataSet[i],testData);map_index_dis[i] = distance;}//	map<int,double>::const_iterator it = map_index_dis.begin();
//	while(it!=map_index_dis.end())
//	{
//		cout<<"index = "<<it->first<<" distance = "<<it->second<<endl;
//		it++;
//	}}tLabel KNN:: get_max_freq_label()
{vector<PAIR> vec_index_dis( map_index_dis.begin(),map_index_dis.end() );sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());for(int i=0;i<k;i++){cout<<"the index = "<<vec_index_dis[i].first<<" the distance = "<<vec_index_dis[i].second<<" the label = "<<labels[ vec_index_dis[i].first ]<<" the coordinate ( ";int j;for(j=0;j<colLen-1;j++){cout<<dataSet[ vec_index_dis[i].first ][j]<<",";}cout<<dataSet[ vec_index_dis[i].first ][j]<<" )"<<endl;map_label_freq[ labels[ vec_index_dis[i].first ]  ]++;}map<tLabel,int>::const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;while( map_it != map_label_freq.end() ){if( map_it->second > max_freq ){max_freq = map_it->second;label = map_it->first;}map_it++;}cout<<"The test data belongs to the "<<label<<" label"<<endl;return label;
}void KNN::auto_norm_data()
{tData maxa[colLen] ;tData mina[colLen] ;tData range[colLen] ;int i,j;for(i=0;i<colLen;i++){maxa[i] = max(dataSet[0][i],dataSet[1][i]);mina[i] = min(dataSet[0][i],dataSet[1][i]);}for(i=2;i<rowLen;i++){for(j=0;j<colLen;j++){if( dataSet[i][j]>maxa[j] ){maxa[j] = dataSet[i][j];}else if( dataSet[i][j]<mina[j] ){mina[j] = dataSet[i][j];}}}for(i=0;i<colLen;i++){range[i] = maxa[i] - mina[i] ; //normalize the test data settestData[i] = ( testData[i] - mina[i] )/range[i] ;}//normalize the training data setfor(i=0;i<rowLen;i++){for(j=0;j<colLen;j++){dataSet[i][j] = ( dataSet[i][j] - mina[j] )/range[j];}}
}int main(int argc , char** argv)
{int k,row,col;char *filename;if( argc!=5 ){cout<<"The input should be like this : ./a.out k row col filename"<<endl;exit(1);}k = atoi(argv[1]);row = atoi(argv[2]);col = atoi(argv[3]);filename = argv[4];KNN knn(k,row,col,filename);knn.auto_norm_data();knn.get_error_rate();
//	knn.get_all_distance();
//	knn.get_max_freq_label();return 0;
}

makefile:

target:g++ KNN_2.cc./a.out 7 1000 3 datingTestSet.txt

結果：

可以看到：在測試數據為10%和訓練數據90%的比例下，可以看到錯誤率為4%，相對來講還是很準確的。

?

構建完整可用系統：

已經通過使用數據對分類器進行了測試，現在可以使用分類器為海倫來對人進行分類。

代碼KNN_1.cc（k=7）：

/* add the auto_norm_data */#include<iostream>
#include<map>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<fstream>using namespace std;typedef string tLabel;
typedef double tData;
typedef pair<int,double>  PAIR;
const int MaxColLen = 10;
const int MaxRowLen = 10000;
ifstream fin;
ofstream fout;class KNN
{
private:tData dataSet[MaxRowLen][MaxColLen];tLabel labels[MaxRowLen];tData testData[MaxColLen];int rowLen;int colLen;int k;map<int,double> map_index_dis;map<tLabel,int> map_label_freq;double get_distance(tData *d1,tData *d2);
public:KNN(int k , int rowLen , int colLen , char *filename);void get_all_distance();tLabel get_max_freq_label();void auto_norm_data();struct CmpByValue{bool operator() (const PAIR& lhs,const PAIR& rhs){return lhs.second < rhs.second;}};~KNN();	
};KNN::~KNN()
{fin.close();fout.close();map_index_dis.clear();map_label_freq.clear();
}KNN::KNN(int k , int row ,int col , char *filename)
{this->rowLen = row;this->colLen = col;this->k = k;fin.open(filename);fout.open("result.txt");if( !fin || !fout ){cout<<"can not open the file"<<endl;exit(0);}//input the training data setfor(int i=0;i<rowLen;i++){for(int j=0;j<colLen;j++){fin>>dataSet[i][j];fout<<dataSet[i][j]<<" ";}fin>>labels[i];fout<<labels[i]<<endl;}//input the test datacout<<"frequent flier miles earned per year?";cin>>testData[0];cout<<"percentage of time spent playing video games?";cin>>testData[1];cout<<"liters of ice cream consumed per year?";cin>>testData[2];
}double KNN:: get_distance(tData *d1,tData *d2)
{double sum = 0;for(int i=0;i<colLen;i++){sum += pow( (d1[i]-d2[i]) , 2 );}return sqrt(sum);
}void KNN:: get_all_distance()
{double distance;int i;for(i=0;i<rowLen;i++){distance = get_distance(dataSet[i],testData);map_index_dis[i] = distance;}//	map<int,double>::const_iterator it = map_index_dis.begin();
//	while(it!=map_index_dis.end())
//	{
//		cout<<"index = "<<it->first<<" distance = "<<it->second<<endl;
//		it++;
//	}}tLabel KNN:: get_max_freq_label()
{vector<PAIR> vec_index_dis( map_index_dis.begin(),map_index_dis.end() );sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());for(int i=0;i<k;i++){/*    cout<<"the index = "<<vec_index_dis[i].first<<" the distance = "<<vec_index_dis[i].second<<" the label = "<<labels[ vec_index_dis[i].first ]<<" the coordinate ( ";int j;for(j=0;j<colLen-1;j++){cout<<dataSet[ vec_index_dis[i].first ][j]<<",";}cout<<dataSet[ vec_index_dis[i].first ][j]<<" )"<<endl;*/map_label_freq[ labels[ vec_index_dis[i].first ]  ]++;}map<tLabel,int>::const_iterator map_it = map_label_freq.begin();tLabel label;int max_freq = 0;/*traverse the map_label_freq to get the most frequent label*/while( map_it != map_label_freq.end() ){if( map_it->second > max_freq ){max_freq = map_it->second;label = map_it->first;}map_it++;}return label;
}/** normalize the training data set*/
void KNN::auto_norm_data()
{tData maxa[colLen] ;tData mina[colLen] ;tData range[colLen] ;int i,j;for(i=0;i<colLen;i++){maxa[i] = max(dataSet[0][i],dataSet[1][i]);mina[i] = min(dataSet[0][i],dataSet[1][i]);}for(i=2;i<rowLen;i++){for(j=0;j<colLen;j++){if( dataSet[i][j]>maxa[j] ){maxa[j] = dataSet[i][j];}else if( dataSet[i][j]<mina[j] ){mina[j] = dataSet[i][j];}}}for(i=0;i<colLen;i++){range[i] = maxa[i] - mina[i] ; //normalize the test data settestData[i] = ( testData[i] - mina[i] )/range[i] ;}//normalize the training data setfor(i=0;i<rowLen;i++){for(j=0;j<colLen;j++){dataSet[i][j] = ( dataSet[i][j] - mina[j] )/range[j];}}
}int main(int argc , char** argv)
{int k,row,col;char *filename;if( argc!=5 ){cout<<"The input should be like this : ./a.out k row col filename"<<endl;exit(1);}k = atoi(argv[1]);row = atoi(argv[2]);col = atoi(argv[3]);filename = argv[4];KNN knn(k,row,col,filename);knn.auto_norm_data();knn.get_all_distance();cout<<"You will probably like this person : "<<knn.get_max_freq_label()<<endl;return 0;
}

makefile：

target:g++ KNN_1.cc./a.out 7 1000 3 datingTestSet.txt

結果：

KNN_1.cc和KNN_2.cc的差別就在于后者對分類器的性能（即分類錯誤率）進行分析，而前者直接對具體實際的數據進行了分類。

注明出處：http://blog.csdn.net/lavorange/article/details/16924705