[機器學習實戰]k-近鄰演算法

最近這段時間學習了《機器學習實戰》這本書，該書在演算法的理論分析、python代碼實現、以及實例應用方面設計的十分得當，層層遞進，非常適合機器學習初學者。

今天就通過鳶尾花分類的例子（後附下載鏈接）簡單的介紹一種分類演算法——k-近鄰演算法，我們知道分類演算法的本質就是通過已知分類的數據集（即訓練集）來建立一個分類的模型，再利用該模型來預測測試集（真實分類已知）的類別，通過比較預測類別與真實類別，得出模型的準確率，當準確率達到一定值後即可用於實際生活中的預測工作。

本文k-近鄰演算法的核心思想是採用測量不同特徵值之間的歐式距離來進行分類，偽代碼如下：

1. 計算已知類別數據集中的點與當前點之間的距離
2. 按照距離遞增順序排序
3. 選取與當前點距離最小的k個點
4. 確定前k個點所在類別的出現概率
5. 返回前k個點出現頻率最高的類別作為當前點的預測分類

數據集下載鏈接：https://pan.baidu.com/s/1ggfw6Oz 密碼：g03q

第一步：數據結構化

對於所有的分類演算法，處理的都是結構化的數據集（即特徵屬性和目標變數的規則排序），例如下圖中的sepal_length（花萼長度）、sepal_width（花萼寬度）、petal_length（花瓣長度）、petal_width（花瓣寬度）就是四個特徵屬性，species（種類）就是不同特徵屬性值所對應的鳶尾花的類別。而在現實生活中，我們拿到的一手數據往往都是非結構化數據，這就需要人為轉化為結構化數據。我們今天所用到的數據已經是結構化數據，該步驟可省略。

前面提到k-近鄰演算法的核心思想是採用測量不同特徵值之間的歐式距離來進行分類，因此我們需要將上述數據集拆分為特徵數據集和類別集兩部分，代碼如下：

from numpy import *nimport operatornimport randomnndef file2matrix(filename):n fr = open(filename)n arrayOlines = fr.readlines() #按行讀取原始數據n random.shuffle(arrayOlines) #打亂順序（所給數據集同一分類聚在一起，不方便後面測試）n numberOfLines = len(arrayOlines)n returnMat = zeros((numberOfLines,4)) #使用了numpy庫里的函數n classLabelVector = []n index =0n #解析文件數據到列表n for line in arrayOlines:n line = line.strip() #移除字元串頭尾指定的字元（默認為空格）n listFromLine = line.split(t) #通過指定分隔符對字元串進行切片n returnMat[index, :] = listFromLine[0:4] #提取某一行所有特徵列數據n classLabelVector.append(listFromLine[-1]) #提取最後一列標籤數據n index += 1n return returnMat, classLabelVectorn

通過file2matrix()函數返回returnMat和classLabelVector兩個矩陣，分別對應特徵數據集和類別集，需要注意的是我們讀取的是文本數據，故需要將xlsx表格數據先轉為文本，保存在當前工作目錄下。

第二步：歸一化特徵值

在計算當前點與已知點之間的歐氏距離時，某些屬性值過大或過小會對距離造成極大影響，導致判斷不準確。通常在處理這種不同範圍的特徵值時，我們會將數值歸一化，使得取值範圍在0到1或者-1到1之間。使用的公式為：

newValue = (oldValue - min) / (max - min)

def autoNorm(dataset):n minVals = dataset.min(0) #找出每列最小的，是一個數組n maxVals = dataset.max(0) #找出每列最大的，是一個數組n ranges = maxVals - minValsn m = dataset.shape[0] #取行數n normDataSet = dataset - tile(minVals, (m, 1))n normDataSet = normDataSet/tile(ranges, (m, 1))n return normDataSet, ranges, minValsn

通過autoNorm()函數我們得到歸一化後的特徵數據集、每列最小集以及每列極差集。

第三步：求當前點的分類

def classify(inX,dataSet,labels,k):n dataSetSize = dataSet.shape[0] #讀取矩陣第一維度的長度（行數）n #距離計算（歐氏距離）n diffMat = tile(inX, (dataSetSize, 1)) - dataSetn sqDiffMat = diffMat**2n sqDistances = sqDiffMat.sum(axis=1)n distances = sqDistances**0.5n sortedDistIndicies = distances.argsort()n classCount = {}n #選擇距離最小的k個點n for i in range(k):n votellabel = labels[sortedDistIndicies[i]]n classCount[votellabel] = classCount.get(votellabel,0) + 1n #sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse= True) #用到operator庫n sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse= True)n return sortedClassCount[0][0]n

classify()函數有4個輸入參數，inX表示用於分類的輸入向量，dataSet為特徵數據集，labels為類別集，k表示用於選擇最近鄰居的數目，函數最終返回待分類項的分類。

第四步：利用測試集測試分類器的正確率

ClassTest()函數調用之前所寫的三個函數，集成為一個可直接運行的API，函數最終返回測試集的錯誤分類率。

def ClassTest():n hoRatio = 0.20 #所給數據集中抽取作為測試集的比例n DataMat, Labels = file2matrix(iris.txt) #調用第一個函數n normMat, ranges, minVals = autoNorm(DataMat) #調用第二個函數n m = normMat.shape[0]n numTestVecs = int(m*hoRatio) #測試集的數量n errorCount = 0.0n for i in range(numTestVecs):n classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], Labels[numTestVecs:m], 10) #調用第三個函數n print("the classifier came back with: %s, the real answer is: %s" % (classifierResult, Labels[i]))n if classifierResult != Labels[i]:n errorCount += 1.0n print("the correct rate is: %f" % (1 - errorCount/float(numTestVecs)))nnClassTest()n

第五步：利用分類器進行預測

對於任意給定sepal_length（花萼長度）、sepal_width（花萼寬度）、petal_length（花瓣長度）、petal_width（花瓣寬度）的待分類數據項，可以預測其類別。

def classifyPridict():n resultList = [Iris-setosa, Iris-versicolor, Iris-virginica]n sepal_length = float(input("the length of sepal?"))n sepal_width = float(input("the width of sepal?"))n petal_length = float(input("the length of petal?"))n petal_width = float(input("the width of petal?"))n DataMat, Labels = file2matrix(iris.txt)n normMat, ranges, minVals = autoNorm(DataMat)n inArr = array([sepal_length, sepal_width, petal_length, petal_width])n classifierResult = classify((inArr - minVals)/ranges, normMat, Labels, 10)n print("the kind of the iris is: %s" % classifierResult)nnclassifyPridict()n

第六步：可視化

在進行可視化時，如果不利用標籤的顏色和大小進行區分，無法分辨出各個點所表示的類別，所以在此之前要將數據的目標變數那一列轉化為整型，否則會當作字元來處理。

具體操作file2matrix函數：

#classLabelVector.append(listFromLine[-1]) #提取最後一列標籤數據nclassLabelVector.append(int(listFromLine[-1]))n

下面選取花萼長度和花瓣長度兩個屬性畫出的散點圖，從圖中可以很明確的看到數據點的區域輪廓，展示效果很好，也可以根據其他屬性來進行展示。

import matplotlib.pyplot as pltnnreturnMat, classLabelVector = file2matrix(iris2.txt)nfig = plt.figure()nax = fig.add_subplot(111)n# ax.scatter(returnMat[:, 0], returnMat[:, 1])nax.scatter(returnMat[:, 0], returnMat[:, 2], 15.0*array(classLabelVector), 15.0*array(classLabelVector))nplt.xlabel(u花萼長度)nplt.ylabel(u花瓣長度)nplt.show()n

未經允許，不得轉載！