前面文章分別簡(jiǎn)單介紹了線性回歸，邏輯回歸紫岩，貝葉斯分類(lèi)，并且用python簡(jiǎn)單實(shí)現(xiàn)睬塌。這篇文章介紹更簡(jiǎn)單的 knn泉蝌， k-近鄰算法（kNN，k-NearestNeighbor）揩晴。
k-近鄰算法（kNN勋陪，k-NearestNeighbor），是最簡(jiǎn)單的機(jī)器學(xué)習(xí)分類(lèi)算法之一硫兰，其核心思想在于用距離目標(biāo)最近的k個(gè)樣本數(shù)據(jù)的分類(lèi)來(lái)代表目標(biāo)的分類(lèi)（這k個(gè)樣本數(shù)據(jù)和目標(biāo)數(shù)據(jù)最為相似）诅愚。
原理
kNN算法的核心思想是用距離最近(多種衡量距離的方式)的k個(gè)樣本數(shù)據(jù)來(lái)代表目標(biāo)數(shù)據(jù)的分類(lèi)。
具體講瞄崇，存在訓(xùn)練樣本集呻粹， 每個(gè)樣本都包含數(shù)據(jù)特征和所屬分類(lèi)值。
輸入新的數(shù)據(jù)苏研，將該數(shù)據(jù)和訓(xùn)練樣本集匯中每一個(gè)樣本比較等浊，找到距離最近的k個(gè)，在k個(gè)數(shù)據(jù)中摹蘑，出現(xiàn)次數(shù)做多的那個(gè)分類(lèi)筹燕，即可作為新數(shù)據(jù)的分類(lèi)。
如上圖：
需要判斷綠色是什么形狀衅鹿。當(dāng)k等于3時(shí)撒踪，屬于三角。當(dāng)k等于5是大渤，屬于方形制妄。
因此該方法具有一下特點(diǎn)：
- 監(jiān)督學(xué)習(xí)：訓(xùn)練樣本集中含有分類(lèi)信息
- 算法簡(jiǎn)單， 易于理解實(shí)現(xiàn)
- 結(jié)果收到k值的影響泵三，k一般不超過(guò)20.
- 計(jì)算量大耕捞，需要計(jì)算與樣本集中每個(gè)樣本的距離衔掸。
- 訓(xùn)練樣本集不平衡導(dǎo)致結(jié)果不準(zhǔn)確問(wèn)題
接下來(lái)用oython 做個(gè)簡(jiǎn)單實(shí)現(xiàn)， 并且嘗試用于約會(huì)網(wǎng)站配對(duì)俺抽。
python簡(jiǎn)單實(shí)現(xiàn)
def classify(inX, dataSet, labels, k):
"""
定義knn算法分類(lèi)器函數(shù)
:param inX: 測(cè)試數(shù)據(jù)
:param dataSet: 訓(xùn)練數(shù)據(jù)
:param labels: 分類(lèi)類(lèi)別
:param k: k值
:return: 所屬分類(lèi)
"""
dataSetSize = dataSet.shape[0] #shape（m, n）m列n個(gè)特征
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ì)的介紹敞映，上面的計(jì)算是矩陣運(yùn)算，下面一個(gè)函數(shù)是代數(shù)運(yùn)算磷斧，做個(gè)比較理解振愿。
def classify_two(inX, dataSet, labels, k):
m, n = dataSet.shape # shape（m, n）m列n個(gè)特征
# 計(jì)算測(cè)試數(shù)據(jù)到每個(gè)點(diǎn)的歐式距離
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 個(gè)最近的值所屬的類(lèi)別
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]
有了上面的分類(lèi)器，下面進(jìn)行最簡(jiǎn)單的實(shí)驗(yàn)來(lái)預(yù)測(cè)一下：
def createDataSet():
group = np.array([[1, 1.1], [1, 1], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
上面是一個(gè)簡(jiǎn)單的訓(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類(lèi)。
上面就是一個(gè)最簡(jiǎn)單的kNN分類(lèi)器侣颂，下面有個(gè)例子栓霜。
kNN用于判斷婚戀網(wǎng)站中人的受歡迎程度
訓(xùn)練樣本集中部分?jǐn)?shù)據(jù)如下：
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
第一列表示每年獲得的飛行常客里程數(shù)横蜒， 第二列表示玩視頻游戲所耗時(shí)間百分比， 第三類(lèi)表示每周消費(fèi)的冰淇淋公升數(shù)销凑。第四列表示分類(lèi)結(jié)果丛晌，1， 2斗幼， 3 分別是 不喜歡澎蛛，魅力一般，極具魅力蜕窿。
- 將數(shù)據(jù)轉(zhuǎn)換成numpy谋逻。
# 文本轉(zhuǎn)換成numpy
def file2matrix(filepath="datingSet.csv"):
dataSet = np.loadtxt(filepath)
returnMat = dataSet[:, 0:-1]
classlabelVector = dataSet[:, -1:]
return returnMat, classlabelVector
- 首先對(duì)數(shù)據(jù)有個(gè)感知，知道是哪些特征影響分類(lèi)桐经，進(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()
如上圖可以看到并無(wú)明顯的分類(lèi)阴挣。
可以看到不同的人根據(jù)特征有明顯的區(qū)分气堕。因此可以使用kNN算法來(lái)進(jìn)行分類(lèi)和預(yù)測(cè)。
- 由于后面要用到距離比較畔咧，因此數(shù)據(jù)之前的影響較大茎芭， 比如飛機(jī)里程和冰淇淋數(shù)目之間的差距太大。因此需要對(duì)數(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算法可以用正確率或者錯(cuò)誤率來(lái)衡量。錯(cuò)誤率為0拜隧，表示分類(lèi)很好宿百。
因此可以將訓(xùn)練樣本中的10%用于測(cè)試趁仙，90%用于訓(xùn)練。
# 定義測(cè)試算法的函數(shù)
def datingClassTest(h=0.1):
hoRatio = h
datingDataMat, datingLabels = file2matrix()
normMat, ranges, minVals = autoNorm(datingDataMat)
m, n = normMat.shape
numTestVecs = int(m * hoRatio) #測(cè)試數(shù)據(jù)行數(shù)
errorCount = 0 # 錯(cuò)誤分類(lèi)數(shù)
# 用前10%的數(shù)據(jù)做測(cè)試
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)整不同的測(cè)試比例犀呼，對(duì)比結(jié)果幸撕。
- 使用knn進(jìn)行預(yù)測(cè)。
有了訓(xùn)練樣本和分類(lèi)器外臂，對(duì)新數(shù)據(jù)可以進(jìn)行預(yù)測(cè)坐儿。模擬數(shù)據(jù)并進(jìn)行預(yù)測(cè)如下：
# 簡(jiǎn)單進(jìn)行預(yù)測(cè)
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ù)測(cè)數(shù)據(jù)歸一化
inArr = (inArr - minVals) / ranges
classifierResult = classify(inArr, normMat, datingLabels, 3)
print(resultList[int(classifierResult)])
可以看到基本的得到所屬的分類(lèi)。
完成代碼和數(shù)據(jù)請(qǐng)參考：
github:kNN
總結(jié)
- kNN
- 監(jiān)督學(xué)習(xí)
- 數(shù)據(jù)可視化
- 數(shù)據(jù)歸一化宋光，不影響計(jì)算
