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

kNN 是一種簡單的機器學習分類演算法, 又名 k - 近鄰演算法; 缺點比較明顯, 在計算複雜度和空間複雜度較高, 但是也有精確度高,無數據輸入假定等優點;

主要用到的公式:

1. 收集準備數據 ??

2. 準備演算法

用 Python3 和 numpy 實現的一個簡單 kNN 演算法:

from numpy import *import operatordef createDataSet(): group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) labels = [A, A, B, B] return group, labelsgroup,labels = createDataSet()# inX: 向量, dataSet: 數據集, labels: 標籤, k: 取近鄰個數def classify0(inX, dataSet, labels, k): # 求出列數 shape函數 dataSetSize = dataSet.shape[0] # 計算距離 歐拉公式, tile函數生成矩陣, 第一個參數為向量值, 第二個為 clo,row diffMat = tile(inX, (dataSetSize, 1)) - dataSet # 取2次方 sqDiffMat = diffMat**2 # ++ sqDistances = sqDiffMat.sum(axis=1) # 開方 distances = sqDistances**0.5 # argsort函數返回排列好的索引 0,1,2 sortedDistIndicies = distances.argsort() classCount = {} # 迭代器賦值 for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] # 統計label出現次數 classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 # 排序 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]print(classify0([0,0], group, labels, 3))

大概分如下幾個步驟

• 利用歐拉公式求出距離
• 根據距離對索引進行排序
• 在 k 個近鄰中統計所有 tag 出現頻率
• 接著根據出現頻率對數據進行排序
• 返回前 k 個近鄰中出現頻率最高的元素

到現在為止, kNN 演算法已經初現;

3. 轉化數據, 分析數據

現在有 1000 個訓練集, 包含三個特徵: 飛行公里數, 玩遊戲耗時百分比, 每周消費冰淇淋公斤數, 用戶等級;

我們的任務是: 利用前三個特徵, 預測用戶等級

從文件中導入數據轉化成矩陣, 文件鏈接 : https://github.com/jiakeqi/MachineLearning/blob/master/dataSet/datingDataSet.txt

文件概覽:

def file2matrix(filename): fr = open(filename) #打開文件 arrayOfLine = fr.readlines() #讀取每行 length = len(arrayOfLine) #獲取長度 returnMat = zeros((length, 3)) #生成n個[0,0,0]矩陣 labels = [] #標籤集合 index = 0 #索引 for line in arrayOfLine: line = line.strip() #修剪字元串 lineArray = line.split( ) #去除訓練集中每行間的空格 returnMat[index,:] = lineArray[0:3] #轉矩陣 labels.append(int(lineArray[-1])) #訓練集中每行最後一個元素是標籤 index += 1 #更新索引 return returnMat, labels

接下來用 Matplotlib 創建散點圖, 假定已經安裝完畢

import matplotlibimport matplotlib.pyplot as pltreturnMat, classLabelVector = file2matrix(datingDataSet.txt) #調用上述函數fig = plt.figure() #創建畫布ax = fig.add_subplot(111) #創建子畫布ax.scatter(returnMat[:, 0], returnMat[:, 1]) #添加部分plt.show()

這裡推薦一篇 Matplotlib 教程

4. 數據歸一化

訓練集已轉換完畢, 演算法也準備完畢, 好像可以開始了?

別著急, 如果你仔細看訓練集的話, 應該會發現特徵之間差別很大, 可能分別是 40000, 1, 2, 1 ;

這就帶來一個問題, 我們在用本文第一個計算時, 特徵一的對計算結果的影響最大,

所以需要進行數據歸一化, 公式為:

對等 ng week2 的課程上講的 特徵收縮(Feature Scaling), 這個公式可以將特徵值收縮到 0 ~ 1 之間, 便於計算

def autoNorm(dataSet): minVals = dataSet.min(0) #取第一列特徵最小值 maxVals = dataSet.max(0) #取第一列特徵最大值 ranges = maxVals - minVals #範圍 normDataSet = zeros(shape(dataSet)) #0佔位矩陣 m = dataSet.shape[0] #訓練集長度 normDataSet = dataSet - tile(minVals, (m, 1)) #計算 normDataSet = normDataSet / tile(ranges, (m, 1)) #計算 return normDataSet, ranges, minValsnormDataSet, ranges, minVals = autoNorm(returnMat)

5. 測試演算法

通常使用 90% 作為訓練樣本, 10% 去測試分類器正確性, 需要注意的是, 這 10% 應該是隨機數據;

調用上面寫好的四個函數:

def datingClassTest (): hoRatio = 0.10 datingDataSet, datingLabels = file2matrix(datingDataSet.txt) normMat, ranges, minVals = autoNorm(datingDataSet) m = normMat.shape[0] numTestVecs = m * hoRatio errorCount = 0.0 numTestVecs = int(numTestVecs) for i in range(numTestVecs): classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3) print("分類器返回", classifierResult, ", 正確答案是", datingLabels[i]) if(classifierResult != datingLabels[i]): errorCount += 1.0 print(總錯誤率是, (errorCount / float(numTestVecs)))# ============= output =================分類器返回 3 , 正確答案是 3分類器返回 1 , 正確答案是 1分類器返回 2 , 正確答案是 2分類器返回 2 , 正確答案是 2分類器返回 1 , 正確答案是 1分類器返回 1 , 正確答案是 1分類器返回 3 , 正確答案是 3分類器返回 2 , 正確答案是 3分類器返回 1 , 正確答案是 1分類器返回 2 , 正確答案是 2分類器返回 1 , 正確答案是 1分類器返回 3 , 正確答案是 3分類器返回 3 , 正確答案是 3分類器返回 3 , 正確答案是 2分類器返回 2 , 正確答案是 1分類器返回 3 , 正確答案是 1總錯誤率是 0.12

6. 總結

路漫漫其修遠兮, 接下來需要學習的還有很多, 本來跟著 ng 的課程, 但是發現課上能聽懂, 但是 ex 階段經常寫不出 octave 代碼 (科學計算代碼不熟悉), 所以買了 機器學習實戰 這本書, 鍛煉下公式到代碼的轉化能力和基礎知識 ??

kNN 的例子還有另外一個手寫識別例子, 待我鞏固一下, 再更新其他的 Demo, 下一篇應該是 決策樹, 持續更新, 敬請期待~ ??

本文的代碼在 jiakeqi/MachineLearning