純python實現(xiàn)機(jī)器學(xué)習(xí)之kNN算法示例

2020-01-04 15:46:50

字體：大中小

供稿：網(wǎng)友

前面文章分別簡單介紹了線性回歸，邏輯回歸，貝葉斯分類，并且用python/300465.html">python簡單實現(xiàn)。這篇文章介紹更簡單的 knn， k-近鄰算法（kNN，k-NearestNeighbor）。

k-近鄰算法（kNN，k-NearestNeighbor），是最簡單的機(jī)器學(xué)習(xí)分類算法之一，其核心思想在于用距離目標(biāo)最近的k個樣本數(shù)據(jù)的分類來代表目標(biāo)的分類（這k個樣本數(shù)據(jù)和目標(biāo)數(shù)據(jù)最為相似）。

原理

kNN算法的核心思想是用距離最近(多種衡量距離的方式)的k個樣本數(shù)據(jù)來代表目標(biāo)數(shù)據(jù)的分類。

具體講，存在訓(xùn)練樣本集，每個樣本都包含數(shù)據(jù)特征和所屬分類值。

輸入新的數(shù)據(jù)，將該數(shù)據(jù)和訓(xùn)練樣本集匯中每一個樣本比較，找到距離最近的k個，在k個數(shù)據(jù)中，出現(xiàn)次數(shù)做多的那個分類，即可作為新數(shù)據(jù)的分類。

python,kNN算法,kNN

如上圖：

需要判斷綠色是什么形狀。當(dāng)k等于3時，屬于三角。當(dāng)k等于5是，屬于方形。

因此該方法具有一下特點：

監(jiān)督學(xué)習(xí)：訓(xùn)練樣本集中含有分類信息
算法簡單，易于理解實現(xiàn)
結(jié)果收到k值的影響，k一般不超過20.
計算量大，需要計算與樣本集中每個樣本的距離。
訓(xùn)練樣本集不平衡導(dǎo)致結(jié)果不準(zhǔn)確問題

接下來用oython 做個簡單實現(xiàn)，并且嘗試用于約會網(wǎng)站配對。

python簡單實現(xiàn)

def classify(inX, dataSet, labels, k):  """  定義knn算法分類器函數(shù)  :param inX: 測試數(shù)據(jù)  :param dataSet: 訓(xùn)練數(shù)據(jù)  :param labels: 分類類別  :param k: k值  :return: 所屬分類  """  dataSetSize = dataSet.shape[0] #shape（m, n）m列n個特征  diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  sqDiffMat = diffMat ** 2  sqDistances = sqDiffMat.sum(axis=1)  distances = sqDistances ** 0.5 #歐式距離  sortedDistIndicies = distances.argsort() #排序并返回index  classCount = {}  for i in range(k):    voteIlabel = labels[sortedDistIndicies[i]]    classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #default 0  sortedClassCount = sorted(classCount.items(), key=lambda d:d[1], reverse=True)  return sortedClassCount[0][0]

算法的步驟上面有詳細(xì)的介紹，上面的計算是矩陣運算，下面一個函數(shù)是代數(shù)運算，做個比較理解。

def classify_two(inX, dataSet, labels, k):  m, n = dataSet.shape  # shape（m, n）m列n個特征  # 計算測試數(shù)據(jù)到每個點的歐式距離  distances = []  for i in range(m):    sum = 0    for j in range(n):      sum += (inX[j] - dataSet[i][j]) ** 2    distances.append(sum ** 0.5)  sortDist = sorted(distances)  # k 個最近的值所屬的類別  classCount = {}  for i in range(k):    voteLabel = labels[ distances.index(sortDist[i])]    classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 # 0:map default  sortedClass = sorted(classCount.items(), key=lambda d:d[1], reverse=True)  return sortedClass[0][0]

有了上面的分類器，下面進(jìn)行最簡單的實驗來預(yù)測一下：

def createDataSet():  group = np.array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])  labels = ['A', 'A', 'B', 'B']  return group, labels

上面是一個簡單的訓(xùn)練樣本集。

if __name__ == '__main__':  dataSet, labels = createDataSet()  r = classify_two([0, 0.2], dataSet, labels, 3)  print(r)

執(zhí)行上述函數(shù)：可以看到輸出B， [0 ,0.2]應(yīng)該歸入b類。

上面就是一個最簡單的kNN分類器，下面有個例子。

kNN用于判斷婚戀網(wǎng)站中人的受歡迎程度

訓(xùn)練樣本集中部分?jǐn)?shù)據(jù)如下：

40920 8.326976 0.953952 314488 7.153469 1.673904 226052 1.441871 0.805124 175136 13.147394 0.428964 138344 1.669788 0.134296 1

第一列表示每年獲得的飛行常客里程數(shù)，第二列表示玩視頻游戲所耗時間百分比，第三類表示每周消費的冰淇淋公升數(shù)。第四列表示分類結(jié)果，1， 2， 3 分別是不喜歡，魅力一般，極具魅力。

將數(shù)據(jù)轉(zhuǎn)換成numpy。

# 文本轉(zhuǎn)換成numpydef file2matrix(filepath="datingSet.csv"):  dataSet = np.loadtxt(filepath)  returnMat = dataSet[:, 0:-1]  classlabelVector = dataSet[:, -1:]  return returnMat, classlabelVector

首先對數(shù)據(jù)有個感知，知道是哪些特征影響分類，進(jìn)行可視化數(shù)據(jù)分析。

# 2， 3列數(shù)據(jù)進(jìn)行分析def show_2_3_fig():  data, cls = file2matrix()  fig = plt.figure()  ax = fig.add_subplot(111)  ax.scatter(data[:, 1], data[: ,2], c=cls)  plt.xlabel("playing game")  plt.ylabel("Icm Cream")  plt.show()

python,kNN算法,kNN

如上圖可以看到并無明顯的分類。

python,kNN算法,kNN

可以看到不同的人根據(jù)特征有明顯的區(qū)分。因此可以使用kNN算法來進(jìn)行分類和預(yù)測。

由于后面要用到距離比較，因此數(shù)據(jù)之前的影響較大，比如飛機(jī)里程和冰淇淋數(shù)目之間的差距太大。因此需要對數(shù)據(jù)進(jìn)行歸一化處理。

# 數(shù)據(jù)歸一化def autoNorm(dataSet):  minVal = dataSet.min(0)  maxVal = dataSet.max(0)  ranges = maxVal - minVal  normDataSet = np.zeros(dataSet.shape)  m, n = dataSet.shape # 行， 特征  normDataSet = dataSet - minVal  normDataSet = normDataSet / ranges  return normDataSet, ranges, minVal

衡量算法的準(zhǔn)確性

knn算法可以用正確率或者錯誤率來衡量。錯誤率為0，表示分類很好。

因此可以將訓(xùn)練樣本中的10%用于測試，90%用于訓(xùn)練。

# 定義測試算法的函數(shù)def datingClassTest(h=0.1):  hoRatio = h  datingDataMat, datingLabels = file2matrix()  normMat, ranges, minVals = autoNorm(datingDataMat)  m, n = normMat.shape  numTestVecs = int(m * hoRatio) #測試數(shù)據(jù)行數(shù)  errorCount = 0 # 錯誤分類數(shù)  # 用前10%的數(shù)據(jù)做測試  for i in range(numTestVecs):    classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)    # print('the classifier came back with: %d,the real answer is: %d' % (int(classifierResult), int(datingLabels[i])))    if classifierResult != datingLabels[i]:      errorCount += 1  print("the total error rate is: %f" % (errorCount / float(numTestVecs)))

調(diào)整不同的測試比例，對比結(jié)果。

使用knn進(jìn)行預(yù)測。

有了訓(xùn)練樣本和分類器，對新數(shù)據(jù)可以進(jìn)行預(yù)測。模擬數(shù)據(jù)并進(jìn)行預(yù)測如下：

# 簡單進(jìn)行預(yù)測def classifypersion():  resultList = ["none", 'not at all','in small doses','in large doses']  # 模擬數(shù)據(jù)  ffmiles = 15360  playing_game = 8.545204  ice_name = 1.340429  datingDataMat, datingLabels = file2matrix()  normMat, ranges, minVals = autoNorm(datingDataMat)  inArr = np.array([ffmiles, playing_game, ice_name])  # 預(yù)測數(shù)據(jù)歸一化  inArr = (inArr - minVals) / ranges  classifierResult = classify(inArr, normMat, datingLabels, 3)  print(resultList[int(classifierResult)])

可以看到基本的得到所屬的分類。

完成代碼和數(shù)據(jù)請參考：

github:kNN

總結(jié)