算法改变人生 2019-06-30
KNN算法是一种数据分类算法,以距离样本k个最邻近数据的类别代表样本的类别,因此也叫作k-近邻算法。KNN算法是数据挖掘中最简单的方法之一,大致可分为以下几个步骤:
我们得到的测试数据,通常和训练数据是不同维的,这时候就需要我们将测试数据升维到和训练数据相同,python的numpy中自带了一个tile()函数可以帮助我们将测试数据升维。
测试数据升维后,我们为了计算距离样本点的距离,此时需要将数据向量化,所谓的向量化就很简单了,即将两个同维数据相减。
欧式距离,即欧几里得距离,运用勾股定理即可求出,将升维后的测试数据和训练数据相减获得的向量组的每一个向量的平方和开方即可得到由距离组成的向量组。
选择k个距离样本点距离最小的数据,统计在这k个数据中哪类数据类别出现的频率最高,样本点的数据类别即可确定。
算法实现:
1.首先我们需要引入numpy以及operator,输入from numpy import *
和import operator
。
2.接下来我们需要定义一个knn函数,在knn函数中我们需要引入四个参数,分别为k、训练数据、测试数据和数据类别。
3.接下来我们需要先对数据进行升维操作,需要用到numpy下的tile(a,(b,c))函数,a为要进行升维操作的数据,也就是测试数据,b为要对测试数据升维的行数据,c为要对测试数据升维的列数据。
4.在上一操作中,我们一般需要获得训练数据的行数和列数,这时需要用到shape()函数,shape()函数返回的是由训练数据的行和列组成的元组,我们想要知道训练数据的行数或列数只需通过数组元素下标的方式引用。
5.数据的维度相同后,我们要将两数据相减得到一个向量,再计算这个向量每个值的平方和的开方即得测试数据到训练数据的距离,再调用argsort()函数将距离按照升序排列,不过该函数返回的是数组元素的下标。
6.接下来我们为了直观的看到不同数据类别的出现次数,需要设置一个空字典来存放这些数据,在得到字典后,我们需要将字典按照不同数据类别的出现次数降序排列,进而返回字典的第一个值即得到测试数据的数据类别。
7.算法代码如下:
from numpy import * import operator def knn(k, test_data, train_data, labels): train_size = train_data.shape[0] #获取训练数据的行数 test_size = tile(test_data, (train_size, 1)) #将测试数据的行升维 minus = test_size-train_data #得到向量 sq_minus = minus**2 sum_sq_minus = sq_minus.sum(axis=1) #得到平方后的每个数组内元素的和 distc = sum_sq_minus**0.5 sort_distc = distc.argsort() #将距离按升序排列 static = {} for i in range(0, k): vote = labels[sort_distc[i]] #获取数据类型 static[vote] = static.get(vote, 0)+1 #统计每个数据类型的出现次数 sort_static = sorted(static.items(), key=operator.itemgetter(1), reverse=True) #将字典中的元素按出现次数降序排列 return sort_static[0][0] #返回出现次数最多的数据类型
8.算法中需要对字典进行排序,因此需要用到sorted()函数,sorted()函数共有三个参数,分别为items(),operator.itemgetter(),reverse,默认的排序为升序,我们要想按照降序排列需要令第三个参数为True,在这里我们是按照字典的values进行排序的,因此我们需要输入sorted(static.items(), key=operator.itemgetter(1), reverse=True)
,operator.itemgetter()函数中的值为1时,是按照字典的values进行排序,值为0时,是按照字典的key进行排序。
9.排序后访问元素的方式与访问二维数组元素的方式一致