手动实现KNN算法
计算距离
取k个邻近排序
距离(欧氏)
预习
import numpy as np
# 数组运算是面向元素级别的
arr1 = np.array([1,2,3])
arr2 = np.array([4,5,6])
arr1 - arr2
array([-3, -3, -3])
(arr1-arr2)**2
array([9, 9, 9], dtype=int32)
sum(arr1-arr2)
-9
# 计算a(1,2,3) 和点b(4,5,6)的距离
# 1. 计算'差'向量
(arr1-arr2) ** 2
array([9, 9, 9], dtype=int32)
# 2. 平方求和再开根号, 即可np.sqrt(9+9+9)
np.sqrt(sum((arr1-arr2)**2))
5.196152422706632
实现欧式距离
def euc_distance(arr1, arr2):
"""
计算两个样本(向量或数组)的欧氏距离
arr1: 样本点1, array类型
arr2: 样本点2, array类型
"""
return np.sqrt(sum((arr1 - arr2)**2))
# test
dis = euc_distance(np.array([1,2,3]), np.array([4,5,6]))
print('(1,2,3)与(4,5,6)的欧氏距离为:', round(dis,3))
(1,2,3)与(4,5,6)的欧氏距离为: 5.196
KNN
计算输入样本点,到每个样本的距离 -> 距离值向量
将距离值向量降序取前k个值
投票
预习
# 计算点(1,2) 到 (3,4), (5,6), (7,8), (9,10) 的距离
X = [np.array([3,4]), np.array([5,6]), np.array([7,8]), np.array([9,10])]
# 逐个计算该点到其他点的距离
dis_arr = [euc_distance(np.array([1,2]), x) for x in X]
dis_arr
[2.8284271247461903, 5.656854249492381, 8.48528137423857, 11.313708498984761]
# 按值升序排列, 取出前k个值的下标
np.argsort(np.array([1,4,2,3]))[:2]
array([0, 2], dtype=int64)
# 按值降序排列, 取出前k个值的下标
arr = np.array([1,4,2,3])
np.argsort(-arr)[:2]
array([1, 3], dtype=int64)
Counter类(计数器)
Counter (计数器): 用于追踪值出现的次数
Counter 类继承dict类, 能顺颂dict类的方法
# 1. 创建一个Counter类
from collections import Counter
obj = Counter('aabbccdde')
print(obj)
Counter({'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 1})
# 2. elements()
# 按元素降序输出
for elem in sorted(obj.elements(), reverse=True):
print(elem, end=' ')
e d d c c b b a a
# 3. most_common(n): 列出频次最高的n个元素, 不指定则列所有
print(obj.most_common(2))
[('a', 2), ('b', 2)]
# test
obj2 = Counter('abcccccddddddeeefff')
obj2.most_common(2)
[('d', 6), ('c', 5)]
# 4. items() 继承dict的方法
for k, v in obj.items():
print(k,v)
a 2
b 2
c 2
d 2
e 1
# 5. update() 增加元素
obj.update('cj')
print(obj)
Counter({'c': 3, 'a': 2, 'b': 2, 'd': 2, 'e': 1, 'j': 1})
# 6. subtract() 减去新传入的元素, 变负数了都
obj.subtract('j')
print(obj)
Counter({'c': 3, 'a': 2, 'b': 2, 'd': 2, 'e': 1, 'j': -3})
实现
def knn_classify(X, y, testInstance, k):
"""
给定一个测试数据(向量)testInstance, 通过knn算法来预测其标签
X: 训练数据特征
y: 训练数据标签
testInstance: 测试数据,一个点(向量), array类型
k: 选择多少个neighbors
"""
# todo: 返回testInstance的预测标签=> {0,1,2}
# 1. 计算输入的点instance 到每个训练点的距离
distances = [euc_distance(testInstance, x) for x in X]
# 2. 按距离值升序,选取前k个值的下标, 注意是下标哦
neighbors = np.argsort(distances)[:k]
# 3. 取到对应的 训练数据标签, 计数投票
count = Counter(y[neighbors]) # key:value
# {a:2, b:3, c:1} -> 只取出3这个值
return count.most_common()[0][0]
案例-iris的KNN实现
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from collections import Counter
def euc_distance(arr1, arr2):
"""计算两个向量的欧式距离"""
return np.sqrt(sum((arr1-arr2)**2))
def knn_classify(X, y, testVector, k):
"""给定一个测试样本(向量), 通过knn计算其在训练y中的标签值"""
distance_list = [euc_distance(testVector, x) for x in X]
# 按距离值升序,选取前k个值的下标
neighbors = np.argsort(distance_list)[:k]
count = Counter(y[neighbors]) # vote
return count.most_common()[0][0]
if __name__ == '__main__':
# 1. 导入iris数据 {'data':[[]], 'target':[], 'target...':xxx}
iris = datasets.load_iris()
X = iris.data
y = iris.target
# 2. 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y)
# 3. 特征工程: 特征选取, 标准化, OneHot编码...
# 4. 训练模型: 遍历每个点(行向量)
predictions = [knn_classify(X_train, y_train, row, 3) for row in X_test]
# 5. 计算准确率
correct_num = np.count_nonzero((predictions == y_test) == True)
print('y_test', y_test, end='')
print('y_pre',predictions, end='')
print("\n准确率为:", round(correct_num / len(y_test), 3))
y_test [0 2 2 2 2 0 1 0 1 2 2 2 0 0 1 1 1 2 1 1 1 1 0 0 2 2 2 1 0 0 1 2 1 1 2 2 0
1]y_pre [0, 2, 2, 2, 2, 0, 1, 0, 1, 2, 2, 2, 0, 0, 1, 2, 1, 2, 1, 1, 1, 1, 0, 0, 2, 2, 2, 1, 0, 0, 1, 2, 1, 1, 2, 2, 0, 1]
准确率为: 0.974
