機器學習實戰ByMatlab（1）：KNN算法

原文出處： Liu_LongPo的專欄（@Liu_LongPo）   

KNN 算法其實簡單的說就是“物以類聚”，也就是將新的沒有被分類的點分類為周圍的點中大多數屬于的類。它采用測量不同特征值之間的距離方法進行分類，思想很簡單：如果一個樣本的特征空間中最為臨近（歐式距離進行判斷）的K個點大都屬于某一個類，那么該樣本就屬于這個類。這就是物以類聚的思想。

當然，實際中，不同的K取值會影響到分類效果，并且在K個臨近點的選擇中，都不加意外的認為這K個點都是已經分類好的了，否則該算法也就失去了物以類聚的意義了。

KNN算法的不足點：

1、當樣本不平衡時，比如一個類的樣本容量很大，其他類的樣本容量很小，輸入一個樣本的時候，K個臨近值中大多數都是大樣本容量的那個類，這時可能就會導致分類錯誤。改進方法是對K臨近點進行加權，也就是距離近的點的權值大，距離遠的點權值小。

2、計算量較大，每個待分類的樣本都要計算它到全部點的距離，根據距離排序才能求得K個臨近點，改進方法是：先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。

適用性：

適用于樣本容量比較大的類域的自動分類，而樣本容量較小的類域則容易誤分

算法描述：

1、計算已知類別數據集合匯總的點與當前點的距離
2、按照距離遞增次序排序
3、選取與當前點距離最近的K個點
4、確定距離最近的前K個點所在類別的出現頻率
5、返回距離最近的前K個點中頻率最高的類別作為當前點的預測分類

Python 實現

from numpy import *
import operator
def createDataSet():
 group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
 lables = ['A','A','B','B']
 return group,lables
# KNN 分類算法
def classify0(inx,dataSet,labels,k):
 dataSetSize = dataSet.shape[0] # shape[0]獲取行 shape[1] 獲取列
 # 第一步，計算歐式距離
 diffMat = tile(inx,(dataSetSize,1)) - dataSet #tile類似于matlab中的repmat，復制矩陣
 sqDiffMat = diffMat ** 2
 sqDistances = sqDiffMat.sum(axis=1)
 distance = sqDistances ** 0.5
 sortedDistIndecies = distance.argsort() # 增序排序
 classCount = {}
 for i in range(k):
 # 獲取類別 
 voteIlabel = labels[sortedDistIndecies[i]]
 #字典的get方法，查找classCount中是否包含voteIlabel，是則返回該值，不是則返回defValue，這里是0
 # 其實這也就是計算K臨近點中出現的類別的頻率，以次數體現
 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
 # 對字典中的類別出現次數進行排序，classCount中存儲的事 key-value，其中key就是label，value就是出現的次數
 # 所以key=operator.itemgetter(1)選中的事value，也就是對次數進行排序
 sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
 #sortedClassCount[0][0]也就是排序后的次數最大的那個label
 return sortedClassCount[0][0]

調用方式：

import sys;
sys.path.append("/home/llp/code/funcdef")
import KNN
group,labels = KNN.createDataSet();
relust = KNN.classify0([0,0],group,labels,3)
print 'the classify relust is :' , relust

Matlab 實現

這里以一個完整實例呈現，代碼如下：

function relustLabel = KNN(inx,data,labels,k)
%% 
% inx 為 輸入測試數據，data為樣本數據，labels為樣本標簽
%%
[datarow , datacol] = size(data);
diffMat = repmat(inx,[datarow,1]) - data ;
distanceMat = sqrt(sum(diffMat.^2,2));
[B , IX] = sort(distanceMat,'ascend');
len = min(k,length(B));
relustLabel = mode(labels(IX(1:len)));
end

可以看到，整個KNN算法的Matlab代碼也就只有6行，比Python少很多，這其中要得益于Matlab成熟的矩陣計算和很多成熟的函數。

實際調用中，我們利用一個數據集進行測試，該數據集是由1000個樣本的3維坐標組成，共分為3個類

首先可視化我們的數據集，看看它的分布：

第一維和第二維：可以清晰地看到數據大致上分為 3 類

第1維和第3維：從這個角度看，3類的分布就有點重疊了，這是因為我們的視角原因

畫出3維，看看它的廬山真面目：

由于我們已經編寫了KNN代碼，接下來我們只需調用就行。了解過機器學習的人都應該知道，很多樣本數據在代入算法之前都應該進行歸一化，這里我們將數據歸一化在[0,1]的區間內，歸一化方式如下：

newData = (oldData-minValue)/(maxValue-minValue)

其中，maxValue為oldData的最大值，minValue為 oldData 的最小值。

同時，我們對于1000個數據集，采取10%的數據進行測試，90%的數據進行訓練的方式，由于本測試數據之間完全獨立，可以隨機抽取10%的數據作為測試數據，代碼如下：

function KNNdatgingTest
%%
clc
clear
close all
%%
data = load('datingTestSet2.txt');
dataMat = data(:,1:3);
labels = data(:,4);
len = size(dataMat,1);
k = 4;
error = 0;
% 測試數據比例
Ratio = 0.1;
numTest = Ratio * len;
% 歸一化處理
maxV = max(dataMat);
minV = min(dataMat);
range = maxV-minV;
newdataMat = (dataMat-repmat(minV,[len,1]))./(repmat(range,[len,1]));
% 測試
for i = 1:numTest
 classifyresult = KNN(newdataMat(i,:),newdataMat(numTest:len,:),labels(numTest:len,:),k);
 fprintf('測試結果為：%d 真實結果為：%d\n',[classifyresult labels(i)])
 if(classifyresult~=labels(i))
 error = error+1;
 end
end
 fprintf('準確率為：%f\n',1-error/(numTest))
end

當我們選擇K為4的時候，準確率為：97%

KNN進階

接下來我們將運用KNN算法實現一個手寫識別系統，訓練數據集大約2000個樣本，每個數字大概有200個樣本
測試數據大概有900個樣本，由于每個樣本都是一個32×32的數字，我們將其轉換為1×1024的矩陣，方便我們利用KNN算法
數據如下：

由于數據量比較大，加載數據的時候回花一點時間，具體代碼如下：

function handWritingTest
%%
clc
clear
close all
%% 獲取目錄下的所有txt文件名稱
d = dir(['digits/trainingDigits/' '*.txt']); % struct 類型
dircell = struct2cell(d); %cell 類型
trainSetLen = size(dircell,2);
K = 4;
dataSize = 1024;
trainLabels = zeros(trainSetLen,1);
trainSet = [];
simpleTrainSet = zeros(1,dataSize);
simpleTestSet = zeros(1,dataSize);
%% 加載數據
fprintf('loading data...')
for i = 1:trainSetLen
 trainName = dircell(1,i);
 trainFilename = cell2mat(trainName);
 trainLabels(i) = str2num(trainFilename(1));
fid = fopen(['digits/trainingDigits/' trainFilename],'r');
 traindata = fscanf(fid,'%s');
 for j = 1:dataSize
 simpleTrainSet(j) = str2num(traindata(j));
 end
 trainSet = [trainSet ; simpleTrainSet];
 fclose(fid);
end
d = dir(['digits/testDigits/' '*.txt']); % struct 類型
dircell = struct2cell(d); %cell 類型
testSetLen = size(dircell,2);
error = 0;
%% 測試數據
for k = 1:testSetLen
 testName = dircell(1,k);
 testFilename = cell2mat(testName);
 testLabels = str2num(testFilename(1));
fid = fopen(['digits/testDigits/' testFilename],'r');
 testdata = fscanf(fid,'%s');
 for j = 1:dataSize
 simpleTestSet(j) = str2num(testdata(j));
 end
 classifyResult = KNN(simpleTestSet,trainSet,trainLabels,K);
 fprintf('識別數字為：%d 真實數字為：%d\n' , [classifyResult , testLabels])
 if(classifyResult~=testLabels)
 error = error+1;
 end
 fclose(fid);
end
fprintf('識別準確率為：%f\n',1-error/testSetLen)
end

不同的K識別準確率稍有不同，當K為4的時候，準確率為 98.31%