k-近邻算法(KNN)
KNN的思路
KNN是通过测量不同特征值之间的距离进行分类。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别，其中K通常是不大于20的整数。可以思考画圈，就是类似画圈的思路，由此也说明了KNN算法的结果很大程度取决于K的选择。
在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：
$$d(x,y)=\sqrt{\sum_{k=1}^{n}\left (x_{k}-y_{k} \right )^{2}}$$
$$d(x,y)=\sqrt{\sum_{k=1}^{n}\left |x_{k}-y_{k} \right |}$$
KNN的注意
- 数据要归一化：因为计算距离时某些数字差值过大的数值会主导结果，所以要对数值进行归一化处理，即$data=\frac{data-min}{max-min}$，这样就使数据处在0-1之间，方便处理
- K值选取会产生过拟合，正如把圆的半径增大后，圈进去的会更多，尽管训练准确率增加，但是测试准确率不会增加
KNN的代码
部分重要代码
# 返回k范围内与测试值最近的类别
def KNNtest(testdata, testgroup, testlables, k):
distance = np.array([])
for i in range(testgroup.shape[0]):
distance = np.append(distance, (np.linalg.norm(testdata - testgroup[i, :])))
sort = distance.argsort()
counttable = {}
for i in range(k):
if testlables[sort[i]] in counttable:
counttable[testlables[sort[i]]] += 1
else:
counttable[testlables[sort[i]]] = 1
return max(counttable.items(), key=lambda x: x[1])[0]
# 归一化处理
def autonorm(data):
for i in range(data.shape[1]):
min = np.min(data[:, i])
max = np.max(data[:, i])
data[:, i] = (data[:, i] - min) / (max - min)
pass
全部代码
# KNNtest.py
import numpy as np
def startKNNtest():
testgroup = np.array([[1, 1, 2], [1, 1.1, 4], [0, 0.1, 1], [0, 0, 5]])
testlables = ['a', 'b', 'a', 'b']
return testgroup, testlables
def KNNtest(testdata, testgroup, testlables, k):
distance = np.array([])
for i in range(testgroup.shape[0]):
distance = np.append(distance, (np.linalg.norm(testdata - testgroup[i, :])))
sort = distance.argsort()
counttable = {}
for i in range(k):
if testlables[sort[i]] in counttable:
counttable[testlables[sort[i]]] += 1
else:
counttable[testlables[sort[i]]] = 1
return max(counttable.items(), key=lambda x: x[1])[0]
if __name__ == "__main__":
group, lables = startKNNtest()
print(KNNtest(np.array([5, 5, 5]), group, lables, 2))
# date.py
# -*- coding:utf-8 -*-
import KNN.KNNtest as KNN
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.pyplot import MultipleLocator
def readfile():
filename = 'datingTestSet2.txt' # txt文件和当前脚本在同一目录下，所以不用写具体路径
pos = []
Efield = []
with open(filename, 'r') as file_to_read:
while True:
lines = file_to_read.readline() # 整行读取数据
if not lines:
break
pass
p1_tmp, p2_tmp, p3_tmp, E_tmp = [float(i) for i in
lines.split()] # 将整行数据分割处理，如果分割符是空格，括号里就不用传入参数，如果是逗号， 则传入‘，'字符。
pos.append([p1_tmp, p2_tmp, p3_tmp]) # 添加新读取的数据
Efield.append(E_tmp)
pass
pos = np.array(pos) # 将数据从list类型转换为array类型。
Efield = np.array(Efield)
return pos, Efield
def autonorm(data):
for i in range(data.shape[1]):
min = np.min(data[:, i])
max = np.max(data[:, i])
data[:, i] = (data[:, i] - min) / (max - min)
pass
def startKNN(data, lables):
pltx = []
plty = []
autonorm(data)
k = int(0.7 * (data.shape[0]))
traindata = data[0:k, :]
trainlables = lables[0:k]
testdata = data[k:, :]
testlables = lables[k:]
testfalse = testdata.shape[0]
besttest = 1
for test in range(1, 20):
false = 0
for i in range(testdata.shape[0]):
if testlables[i] != KNN.KNNtest(testdata[i, :], traindata, trainlables, test):
false += 1
pltx.append(test)
plty.append(false / testdata.shape[0])
if false <= testfalse:
testfalse = false
besttest = test
plt.plot(pltx, plty, 'g-') # 绿色折线
ax = plt.gca()
# ax为两条坐标轴的实例
ax.xaxis.set_major_locator(MultipleLocator(1))
plt.show()
return testfalse / testdata.shape[0], besttest
data, lables = readfile()
print(startKNN(data, lables))
#数据集以txt形式存储
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
72993 10.141740 1.032955 1
35948 6.830792 1.213192 3
42666 13.276369 0.543880 3
67497 8.631577 0.749278 1
35483 12.273169 1.508053 3
50242 3.723498 0.831917 1
代码说明
因为自己没有按照书给的代码抄，都是按照自己的理解然后重新写的代码，所以可能会有出入或者性能问题，还希望谅解
总结
因为KNN比较简单而且好理解，所以作为我第一个上手的机器学习的算法，其实它是懒惰学习的代表，它并没有进行迭代等其他算法有的步骤，其唯一可能就是探索最佳的k或者交叉验证的比值而已，而且缺点很明显，因为都需要计算距离，当点数过多时候会很慢，所以决策树算法解决了这个问题，也是下一篇的内容
Comments | NOTHING