手写 knn 算法:
在看 knn 算法之前, 先去简单学习了一下 python 的使用, 简单了解了一下 python 相关知识, 发现 python 序列与 c++ 里的数组有一定的差别,
一, python 学习.
列表, 元组, 字符串支持双向索引, 第一个元素下标为 0, 第二个元素下标为 1, 以此类推; 最后一个元素下标为 - 1, 倒数第二个元素下标为 - 2, 以此类推.
字符串: 索引运算符 [ i ] 得到下标为 i 的字符, 切片运算符 [ i : j] 得到从下标 i 到下标 j-1 的子串第一个字符索引为 0, 最后一个字符索引为 - 1 加号 (+) 用于字符串连接运算, 星号 (*) 用于字符串复制.
列表: 索引运算符 [ i ] 得到下标为 i 的元素, 切片运算符 [ i : j] 得到从下标 i 到下标 j-1 的子集, 第一个元素索引为 0, 最后一个元素索引为 - 1.
列表常用方法:
二, 学习手写 knn 算法
首先:
- iris = datasets.load_iris()
- x = iris.data
- y = iris.target
- x_train,x_test,y_train,y_test = train_test_split(x,y,random_state=2003)
这里我们导入的数据集叫做 iris 数据集
x_train,x_test,y_train,y_test = train_test_split(x,y,random_state=2003)
X 存储的是数据的特征, y 存储的每一个样本的标签或者分类, train_test_split 来把数据分成了训练集和测试集.
插入欧式距离公式来计算任意两点之间的距离:
- def euc_dis(instance1, instance2):
- diff = instance1 - instantce2
- diff = diff ** 2
- dist = sum(diff) ** 0.5
- return dist
欧式距离也称欧几里得距离, 是最常见的距离度量, 衡量的是多维空间中两个点之间的绝对距离.
也可以理解为: m 维空间中两个点之间的真实距离, 或者向量的自然长度(即该点到原点的距离). 在二维和三维空间中的欧氏距离就是两点之间的实际距离
下面是具体的计算公式:
- def knn_classify(x, y, testInstance, k):
- dis = []
- for i in x
- dis.apend(euc_dis(i,testInstance))
- maxIndex = map(dis.index,heapq.nsmallest(k,dis))
- maxY = []
- for i in maxIndex
- maxY.append(y[i])
- return max(maxY,key = maxY.count)
knn 的算法实现, 求 testInstance 到每个 x 点的距离并存于列表 dis 中, heapq 该模块提供了堆排序算法的实现. 堆是二叉树, 最大堆中父节点大于或等于两个子节点, 最小堆父节点小于或等于两个子节点.
heapq.nsmallest(k,dis)求出最小的 k 个距离的下标, 使用堆来求最小的 k.map 模块 map() 会根据提供的函数对指定序列做映射. 第一个参数 function 以参数序列中的每一个元素调用 function
函数, 返回包含每次 function 函数返回值的新列表. 返回出现次数最多的标签值.
- prediction = [knn_classify(x_train, y_train, data, 3)for data in x_test]
- correct = np.count_nonzero((prections == y.test) == true)
比较手写 knn 算法及原本数据库, 算出准确率.
三, 心得体会
刚开始其实看 knn 手写算法时, 很多东西都不是很理解, 根据同学们给的资料, 自己简单的看看, 学习了一下, 再去看代码, 慢慢理解每一步的含义, 不懂得地方在百度查询相关代码, 一个个解决问题, 基本理解了 knn 算法代码的意思, 其实很简单, 就是根据它原本的数据库, 写一个预算代码, 对比预测目标与对应目标的相似度来判断是否正确, 自己对于 python 的用法还是比较陌生, 还需要多加练习才能更加理解, 多去学习才能进步.
来源: http://www.bubuko.com/infodetail-3304215.html