數學系研二渣碩一枚，最早接觸機器學習還是在研究生一年級的模式識別課程上，發現大部分機器學習的書籍都是采用Python語言，當然Python在數據分析和矩陣計算方面確實會有很大的優勢，對于缺乏編程基礎又想要快速入門的同學，Python確實是首選。而從本系列開始，我將主要用C++將《機器學習實戰》這本書刷一遍，旨在加深對算法理解的同時提高編程能力，也希望能夠為想入坑機器學習，同時又熱愛C++的人提供一些參考。

    每一篇的開始會有一個簡單的算法描述，不會將原書的Python的代碼照搬過來，想了解具體的可以參考《機器學習實戰》原著，CSDN上也有電子版可供下載。

        現學現賣，希望我能夠堅持得下去。

算法概述：kNN算法采用測量不同特征值之間的距離方法進行分類。kNN算法在能夠工作之前需要先獲取大量樣本數據進行訓練，每一個樣本數據事先都存在標簽。輸入沒有標簽的數據后，將新數據的每個特征與樣本集中的特征進行比較，然后提取樣本集中最相似數據的分類標簽。一般來說，我們只選擇樣本數據集中前k個最相似的數據標簽，這就是kNN算法中k的出處，通常k是不大于20的整數。最后，我們選擇k個最相似數據中出現次數最多的分類，作為新數據的分類。

現在我們嘗試一個簡單的范例，對二維坐標系中的點進行分類，定義一個4×2二維數組group代表坐標系中4個點的坐標，相應的標簽labels為一個字符串數組，labels索引對應group中每一行的索引。

double group[4][2] = { { 1.0, 1.1 }, { 1.0, 1.0 }, { 0, 0 }, { 0, 0.1 } };

string labels[4] = { "A", "A", "B", "B" };

在C++中，將樣本集定義為一個結構體似乎是更為合理的選擇，不過原書中都是矩陣計算，為描述方便，還是采用類似矩陣的數組。

在獲得樣本集后，需要采用kNN對無標簽的數據進行分類，具體步驟如下：

（1）計算樣本集中的點與當前點的距離；

（2）按照距離遞增次序排序；

（3）選取與當前點距離最小k個點；

（4）確定前k個點所在類別的出現頻率；

（5）返回前k個點出現頻率最高的類別作為當前點的分類。

     相應的代碼清單如下：

string classify(double* inX,double* dataSet,string labels[],int k,int size,int dataSetSize)

//kNN分類算法

//inX：未分類的輸入數據，dataSet：樣本集，labels：標簽，k:k值，size：數據的特征數量，dataSetSize:樣本集數量 

{

double sum = 0;

double* diff_array = new double[size];

double* diff_all = new double[dataSetSize];

int* sorted_index = new int[dataSetSize];

string label;

map<string, int> label_count;

for (int i = 0; i < dataSetSize; i++)

//計算當前點與各樣本點的歐式距離，并存入數組diff_array

{

sum = 0;

for (int j = 0; j < size; j++)

{

diff_array[j] = *(inX + j) - *(dataSet + i*size + j);

sum += (diff_array[j] * diff_array[j]);

}

diff_all[i] = sqrt(sum);

}

//排序，并返回排序后的原數組索引

sortIndex(diff_all, sorted_index, dataSetSize);

for (int i = 0; i < k; i++)

//計算前k個索引對應標簽的出現次數，存入關聯容器label_count

{

label = labels[sorted_index[i]];

++label_count[label];

}

//找出出現次數最多的標簽，返回

auto map_it = label_count.begin();

label = map_it->first;

int max_count = map_it->second;

for (; map_it != label_count.end(); map_it++)

{

if (max_count < map_it->second)

{

max_count = map_it->second;

label = map_it->first;

}

}

delete diff_array;

delete diff_all;

delete sorted_index;

return label;

}

以上程序使用歐氏距離公式，計算兩個點xA和xB之間的距離：

計算當前點與所有樣本點的距離后，將距離由小到大進行排序，找到最近的k個點，然后返回k個點中出現頻率最高的標簽，這是基本思路。

在對距離進行排序并按原數組的索引返回的時候出現了一些小麻煩，在python中只要一個命令就能解決的問題，我不知道在C++中是否有同樣方便好用的排序函數，不過以提高編程能力為目標，我本人倒不介意重復造車輪子的過程，排序代碼如下：

void sortIndex(double* data, int* sorted_index2, int n)

//排序，并返回排序后的原數組索引

//data：原始數組，sorted_index2：排序后的原數組索引，n：數組大小

{

int index = 0;

int* sorted_index = new int[n];

for (int i = 0; i < n; i++)

{

index = 0;

for (int j = 0; j < n; j++)

{

if (data[i] > data[j])

index++;

else if (data[i] == data[j] && i > j)

index++;

}

sorted_index[i] = index;

}

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (i == sorted_index[j])

sorted_index2[i] = j;

}

}

delete sorted_index;

}

代碼完成后，在main函數中進行調用測試：

int main()

{

string result;

string line;

double point[2];

cout << "Please input the coodinate of the pixel" << endl;

while (getline(cin, line))

{

istringstream record(line);

record >> point[0];

record >> point[1];

result = classify(point, &group[0][0], labels, 3, 2, 4);

cout << "The result is: " << result << endl;

cout << "Please input the coodinate of the pixel" << endl;

}

return 0;

}

運行結果：

使用kNN算法改進約會網站的配對效果

海倫在使用約會網站尋找約會對象的過程中，經過總結可以把交往過的人分為三種類型：

不喜歡的人

魅力一般的人

極具魅力的人

海倫希望我們的算法可以幫助她將匹配對象分到確切的分類中，為此她收集了一批約會對象的用戶數據，每一個約會對象包含3個特征：每年的飛行里程數

玩游戲所耗時間百分比

每周消費的冰淇淋公升數

每一條樣本數據都已經做好了標簽，樣本數據如下：

為了應用已經實現的kNN算法幫助海倫進行分類，我們先要讀取文本數據并轉化為程序所需要的類型。然后應用以上的classify函數進行分類。

數據文件里共有1000條數據，選取前100條數據為測試集對算法進行測試，發現當k=3時，錯誤率為5%

利用全體數據作為樣本集對當個數據進行分類：

查看完整代碼：

http://blog.csdn.net/u014080185/article/details/60467308