機(jī)器學(xué)習(xí)實戰(zhàn)ByMatlab（1）：KNN算法

quasiceo 2016-01-16

展開全文

機(jī)器學(xué)習(xí)實戰(zhàn)ByMatlab（1）：KNN算法

2015/05/14 · IT技術(shù) · 機(jī)器學(xué)習(xí), 算法

分享到： 13

Oracle數(shù)據(jù)庫開發(fā)必備利器之SQL基礎(chǔ)
MongoDB復(fù)制集—認(rèn)識復(fù)制集
近距離探索memcache緩存
PHP實現(xiàn)微信公眾平臺開發(fā)—提升篇

原文出處： Liu_LongPo的專欄（@Liu_LongPo）歡迎分享原創(chuàng)到伯樂頭條

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

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

KNN算法的不足點：

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

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

適用性：

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

算法描述：

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

Python 實現(xiàn)

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，復(fù)制矩陣

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臨近點中出現(xiàn)的類別的頻率，以次數(shù)體現(xiàn)

classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1

# 對字典中的類別出現(xiàn)次數(shù)進(jìn)行排序，classCount中存儲的事 key-value，其中key就是label，value就是出現(xiàn)的次數(shù)

# 所以key=operator.itemgetter(1)選中的事value，也就是對次數(shù)進(jìn)行排序

sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)

#sortedClassCount[0][0]也就是排序后的次數(shù)最大的那個label

return sortedClassCount[0][0]

調(diào)用方式：

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 實現(xiàn)

這里以一個完整實例呈現(xiàn)，代碼如下：

function relustLabel = KNN(inx,data,labels,k)

%%

% inx 為輸入測試數(shù)據(jù)，data為樣本數(shù)據(jù)，labels為樣本標(biāo)簽

%%

[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成熟的矩陣計算和很多成熟的函數(shù)。

實際調(diào)用中，我們利用一個數(shù)據(jù)集進(jìn)行測試，該數(shù)據(jù)集是由1000個樣本的3維坐標(biāo)組成，共分為3個類

首先可視化我們的數(shù)據(jù)集，看看它的分布：

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

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

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

由于我們已經(jīng)編寫了KNN代碼，接下來我們只需調(diào)用就行。了解過機(jī)器學(xué)習(xí)的人都應(yīng)該知道，很多樣本數(shù)據(jù)在代入算法之前都應(yīng)該進(jìn)行歸一化，這里我們將數(shù)據(jù)歸一化在[0,1]的區(qū)間內(nèi)，歸一化方式如下：

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

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

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

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;

% 測試數(shù)據(jù)比例

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('測試結(jié)果為：%d 真實結(jié)果為：%d\n',[classifyresult labels(i)])

if(classifyresult~=labels(i))

error = error+1;

end

fprintf('準(zhǔn)確率為：%f\n',1-error/(numTest))

end

當(dāng)我們選擇K為4的時候，準(zhǔn)確率為：97%

KNN進(jìn)階

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