最近在看《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書(shū)，因?yàn)樽约罕旧砗芟肷钊氲牧私鈾C(jī)器學(xué)習(xí)算法，加之想學(xué)python，就在朋友的推薦之下選擇了這本書(shū)進(jìn)行學(xué)習(xí)。
一 . K-近鄰算法（KNN）概述
最簡(jiǎn)單最初級(jí)的分類器是將全部的訓(xùn)練數(shù)據(jù)所對(duì)應(yīng)的類別都記錄下來(lái)，當(dāng)測(cè)試對(duì)象的屬性和某個(gè)訓(xùn)練對(duì)象的屬性完全匹配時(shí)，便可以對(duì)其進(jìn)行分類。但是怎么可能所有測(cè)試對(duì)象都會(huì)找到與之完全匹配的訓(xùn)練對(duì)象呢，其次就是存在一個(gè)測(cè)試對(duì)象同時(shí)與多個(gè)訓(xùn)練對(duì)象匹配，導(dǎo)致一個(gè)訓(xùn)練對(duì)象被分到了多個(gè)類的問(wèn)題，基于這些問(wèn)題呢，就產(chǎn)生了KNN。
KNN是通過(guò)測(cè)量不同特征值之間的距離進(jìn)行分類。它的的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。K通常是不大于20的整數(shù)。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。
下面通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明一下：如下圖，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。
由此也說(shuō)明了KNN算法的結(jié)果很大程度取決于K的選擇。
在KNN中，通過(guò)計(jì)算對(duì)象間距離來(lái)作為各個(gè)對(duì)象之間的非相似性指標(biāo)，避免了對(duì)象之間的匹配問(wèn)題，在這里距離一般使用歐氏距離或曼哈頓距離：
同時(shí)，KNN通過(guò)依據(jù)k個(gè)對(duì)象中占優(yōu)的類別進(jìn)行決策，而不是單一的對(duì)象類別決策。這兩點(diǎn)就是KNN算法的優(yōu)勢(shì)。
接下來(lái)對(duì)KNN算法的思想總結(jié)一下：就是在訓(xùn)練集中數(shù)據(jù)和標(biāo)簽已知的情況下，輸入測(cè)試數(shù)據(jù)，將測(cè)試數(shù)據(jù)的特征與訓(xùn)練集中對(duì)應(yīng)的特征進(jìn)行相互比較，找到訓(xùn)練集中與之最為相似的前K個(gè)數(shù)據(jù)，則該測(cè)試數(shù)據(jù)對(duì)應(yīng)的類別就是K個(gè)數(shù)據(jù)中出現(xiàn)次數(shù)最多的那個(gè)分類，其算法的描述為：
1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。
二 .python實(shí)現(xiàn)
首先呢，需要說(shuō)明的是我用的是python3.4.3，里面有一些用法與2.7還是有些出入。
建立一個(gè)KNN.py文件對(duì)算法的可行性進(jìn)行驗(yàn)證，如下：
#coding:utf-8from numpy import *import operator##給出訓(xùn)練數(shù)據(jù)以及對(duì)應(yīng)的類別def createDataSet(): group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]]) labels = ['A','A','B','B'] return group,labels###通過(guò)KNN進(jìn)行分類def classify(input,dataSe t,label,k): dataSize = dataSet.shape[0] ####計(jì)算歐式距離 diff = tile(input,(dataSize,1)) - dataSet sqdiff = diff ** 2 squareDist = sum(sqdiff,axis = 1)###行向量分別相加，從而得到新的一個(gè)行向量 dist = squareDist ** 0.5 ##對(duì)距離進(jìn)行排序 sortedDistIndex = argsort(dist)##argsort()根據(jù)元素的值從大到小對(duì)元素進(jìn)行排序，返回下標(biāo) classCount={} for i in range(k): voteLabel = label[sortedDistIndex[i]] ###對(duì)選取的K個(gè)樣本所屬的類別個(gè)數(shù)進(jìn)行統(tǒng)計(jì) classCount[voteLabel] = classCount.get(voteLabel,0) + 1 ###選取出現(xiàn)的類別次數(shù)最多的類別 maxCount = 0 for key,value in classCount.items(): if value > maxCount: maxCount = value classes = key return classes
接下來(lái)，在命令行窗口輸入如下代碼：
#-*-coding:utf-8 -*-import syssys.path.append("...文件路徑...")import KNNfrom numpy import *dataSet,labels = KNN.createDataSet()input = array([1.1,0.3])K = 3output = KNN.classify(input,dataSet,labels,K)print("測(cè)試數(shù)據(jù)為:",input,"分類結(jié)果為：",output)
回車之后的結(jié)果為：
測(cè)試數(shù)據(jù)為： [ 1.1 0.3] 分類為： A
答案符合我們的預(yù)期，要證明算法的準(zhǔn)確性，勢(shì)必還需要通過(guò)處理復(fù)雜問(wèn)題進(jìn)行驗(yàn)證，之后另行說(shuō)明。
這是第一次用python編的一個(gè)小程序，勢(shì)必會(huì)遇到各種問(wèn)題，在此次編程調(diào)試過(guò)程中遇到了如下問(wèn)題：
1 導(dǎo)入.py文件路徑有問(wèn)題，因此需要在最開(kāi)始加如下代碼：
sys.path.append("文件路徑")，這樣就不會(huì)存在路徑有誤的問(wèn)題了；
2 在python提示代碼存在問(wèn)題時(shí)，一定要及時(shí)改正，改正之后保存之后再執(zhí)行命令行，這一點(diǎn)跟MATLAB是不一樣的，所以在python中最好是敲代碼的同時(shí)在命令行中一段一段的驗(yàn)證；
3 在調(diào)用文件時(shí)函數(shù)名一定要寫(xiě)正確，否則會(huì)出現(xiàn)：'module' object has no attribute 'creatDataSet'；
4 'int' object has no attribute 'kclassify'，這個(gè)問(wèn)題出現(xiàn)的原因是之前我講文件保存名為k.py,在執(zhí)行
output = K.classify(input,dataSet,labels,K)這一句就會(huì)出錯(cuò)。根據(jù)函數(shù)式編程的思想，每個(gè)函數(shù)都可以看為是一個(gè)變量而將K賦值后，調(diào)用k.py時(shí)就會(huì)出現(xiàn)問(wèn)題。
三 MATLAB實(shí)現(xiàn)
之前一直在用MATLAB做聚類算法的一些優(yōu)化，其次就是數(shù)模的一些常用算法，對(duì)于別的算法，還真是沒(méi)有上手編過(guò)，基礎(chǔ)還在，思想還在，當(dāng)然要?jiǎng)邮志幰幌?，也是不希望在學(xué)python的同時(shí)對(duì)MATLAB逐漸陌生吧，走走停停，停很重要。
首先，建立KNN.m文件，如下：
%% KNNclear allclc%% datatrainData = [1.0,2.0;1.2,0.1;0.1,1.4;0.3,3.5];trainClass = [1,1,2,2];testData = [0.5,2.3];k = 3;%% distancerow = size(trainData,1);col = size(trainData,2);test = repmat(testData,row,1);dis = zeros(1,row);for i = 1:row diff = 0; for j = 1:col diff = diff + (test(i,j) - trainData(i,j)).^2; end dis(1,i) = diff.^0.5;end%% sortjointDis = [dis;trainClass];sortDis= sortrows(jointDis');sortDisClass = sortDis';%% findclass = sort(2:1:k);member = unique(class);num = size(member);max = 0;for i = 1:num count = find(class == member(i)); if count > max max = count; label = member(i); endenddisp('最終的分類結(jié)果為：');fprintf('%d\n',label) 運(yùn)行之后的結(jié)果是，最終的分類結(jié)果為：2。和預(yù)期結(jié)果一樣。
總而言之，用MATLAB的時(shí)間相對(duì)長(zhǎng)點(diǎn)，自然也就得心應(yīng)手點(diǎn)，不過(guò)還是希望早點(diǎn)能將python運(yùn)用自如吧！
三 實(shí)戰(zhàn)
之前，對(duì)KNN進(jìn)行了一個(gè)簡(jiǎn)單的驗(yàn)證，今天我們使用KNN改進(jìn)約會(huì)網(wǎng)站的效果，個(gè)人理解，這個(gè)問(wèn)題也可以轉(zhuǎn)化為其它的比如各個(gè)網(wǎng)站迎合客戶的喜好所作出的推薦之類的，當(dāng)然，今天的這個(gè)例子功能也實(shí)在有限。
在這里根據(jù)一個(gè)人收集的約會(huì)數(shù)據(jù)，根據(jù)主要的樣本特征以及得到的分類，對(duì)一些未知類別的數(shù)據(jù)進(jìn)行分類，大致就是這樣。
我使用的是python 3.4.3,首先建立一個(gè)文件，例如date.py,具體的代碼如下：
#coding:utf-8from numpy import *import operatorfrom collections import Counterimport matplotlibimport matplotlib.pyplot as plt###導(dǎo)入特征數(shù)據(jù)def file2matrix(filename): fr = open(filename) contain = fr.readlines()###讀取文件的所有內(nèi)容 count = len(contain) returnMat = zeros((count,3)) classLabelVector = [] index = 0 for line in contain: line = line.strip() ###截取所有的回車字符 listFromLine = line.split('\t') returnMat[index,:] = listFromLine[0:3]###選取前三個(gè)元素，存儲(chǔ)在特征矩陣中 classLabelVector.append(listFromLine[-1])###將列表的最后一列存儲(chǔ)到向量classLabelVector中 index += 1 ##將列表的最后一列由字符串轉(zhuǎn)化為數(shù)字，便于以后的計(jì)算 dictClassLabel = Counter(classLabelVector) classLabel = [] kind = list(dictClassLabel) for item in classLabelVector: if item == kind[0]: item = 1 elif item == kind[1]: item = 2 else: item = 3 classLabel.append(item) return returnMat,classLabel#####將文本中的數(shù)據(jù)導(dǎo)入到列表##繪圖（可以直觀的表示出各特征對(duì)分類結(jié)果的影響程度）datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt')fig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0],datingDataMat[:,1],15.0*array(datingLabels),15.0*array(datingLabels))plt.show()## 歸一化數(shù)據(jù),保證特征等權(quán)重def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = zeros(shape(dataSet))##建立與dataSet結(jié)構(gòu)一樣的矩陣 m = dataSet.shape[0] for i in range(1,m): normDataSet[i,:] = (dataSet[i,:] - minVals) / ranges return normDataSet,ranges,minVals##KNN算法def classify(input,dataSet,label,k): dataSize = dataSet.shape[0] ####計(jì)算歐式距離 diff = tile(input,(dataSize,1)) - dataSet sqdiff = diff ** 2 squareDist = sum(sqdiff,axis = 1)###行向量分別相加，從而得到新的一個(gè)行向量 dist = squareDist ** 0.5 ##對(duì)距離進(jìn)行排序 sortedDistIndex = argsort(dist)##argsort()根據(jù)元素的值從大到小對(duì)元素進(jìn)行排序，返回下標(biāo) classCount={} for i in range(k): voteLabel = label[sortedDistIndex[i]] ###對(duì)選取的K個(gè)樣本所屬的類別個(gè)數(shù)進(jìn)行統(tǒng)計(jì) classCount[voteLabel] = classCount.get(voteLabel,0) + 1 ###選取出現(xiàn)的類別次數(shù)最多的類別 maxCount = 0 for key,value in classCount.items(): if value > maxCount: maxCount = value classes = key return classes##測(cè)試(選取10%測(cè)試）def datingTest(): rate = 0.10 datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet.txt') normMat,ranges,minVals = autoNorm(datingDataMat) m = normMat.shape[0] testNum = int(m * rate) errorCount = 0.0 for i in range(1,testNum): classifyResult = classify(normMat[i,:],normMat[testNum:m,:],datingLabels[testNum:m],3) print("分類后的結(jié)果為:,", classifyResult) print("原結(jié)果為：",datingLabels[i]) if(classifyResult != datingLabels[i]): errorCount += 1.0 print("誤分率為:",(errorCount/float(testNum))) ###預(yù)測(cè)函數(shù)def classifyPerson(): resultList = ['一點(diǎn)也不喜歡','有一丟丟喜歡','灰常喜歡'] percentTats = float(input("玩視頻所占的時(shí)間比?")) miles = float(input("每年獲得的飛行?？屠锍虜?shù)?")) iceCream = float(input("每周所消費(fèi)的冰淇淋公升數(shù)?")) datingDataMat,datingLabels = file2matrix('D:\python\Mechine learing in Action\KNN\datingTestSet2.txt') normMat,ranges,minVals = autoNorm(datingDataMat) inArr = array([miles,percentTats,iceCream]) classifierResult = classify((inArr-minVals)/ranges,normMat,datingLabels,3) print("你對(duì)這個(gè)人的喜歡程度:",resultList[classifierResult - 1])
新建test.py文件了解程序的運(yùn)行結(jié)果，代碼：
#coding:utf-8from numpy import *import operatorfrom collections import Counterimport matplotlibimport matplotlib.pyplot as pltimport syssys.path.append("D:\python\Mechine learing in Action\KNN")import datedate.classifyPerson()
運(yùn)行結(jié)果如下圖：
這樣就算是成功了吧，當(dāng)然，在這其中也遇到了很多的問(wèn)題，我看的《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》這本書(shū)主要還是針對(duì)于python2.7的，理所應(yīng)當(dāng)?shù)奈矣龅搅瞬簧賳?wèn)題。有在學(xué)習(xí)這本書(shū)的朋友咱們可以交流下哈~
好困了，想著早點(diǎn)寫(xiě)完這篇，也就吃完飯沒(méi)睡覺(jué)，完工了！
還希望大家能多提寶貴意見(jiàn)~
聯(lián)系客服
