MachineLearning-KNN

今天呢,我们就要来接触稍微高级一点的东西了,我们所做的事情不仅仅局限于代码的层面上了,要基于某种算法解决问题,而此时的python则是我们完成问题的工具啦!

KNN,即K-近邻算法,一般是用来进行分类的算法。

它的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别,其中K

根据上面的说明,现在我们举个例子来说明KNN可以用来干啥:

现在我们图书馆有三种类别的书,分别是:教科书,小说书,漫画书,三种书都有各自的特征,那现在图书馆馆长给了我一本新书X,他让我去归类,把它归类到某个类别,我们可以取出三本书的特征,然后数据化,把新书X特征数据手机好,然后对比三种书的特征,与三条数据中的哪个数据最接近,那么新书X就应该是那个类别了!

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。(KNN算法的结果很大程度取决于K的选择)

那下面我们来看看KNN算法是怎样的一个过程吧:

1、计算距离(测试数据与训练数据之间的距离)

2、将距离排序

3、选出距离最小的K个点

4、确认K个点它所在类别出现的频率

5、出现次数最多的标签即为最终类别

了解我们要做什么之后,我们就来选择我们的工具python来完成我们想要做的事情吧!

首先我们得要有数据集和标签吧,如果这些都没有还谈什么标签分类啊

创建数据集和标签

defcreateDataSet():

group = array([[1.0,1.1], [1.0,1.0], [,], [,0.1]])

labels = ['A','A','B','B']

returngroup, labels

下面我们就来看分类方法了

要计算距离我们就得有计算距离的方法吧,我们选择计算欧式距离,这里我们有两种方法来计算距离:

先定义一个KNN算法函数:

defclassify0(inX,dataSet,labels,k):

参数:inX: 用于分类的输入向量

dataSet: 输入的训练样本集

labels: 标签向量

k: 选择最近邻居的数目

方法1:

1. 距离计算

dataSetSize = dataSet.shape[]

# tile生成和训练样本对应的矩阵,并与训练样本求差

diffMat = tile(inX, (dataSetSize,1)) - dataSet

# 取平方

sqDiffMat = diffMat **2

# 将矩阵的每一行相加

sqDistances = sqDiffMat.sum(axis=1)

# 开方

distances = sqDistances **0.5

# 根据距离排序从小到大的排序,返回对应的索引位置

# argsort() 是将x中的元素从小到大排列,提取其对应的index(索引),然后输出到y。

# 例如:y=array([3,0,2,1,4,5]) 则,x[3]=-1最小,所以y[0]=3,x[5]=9最大,所以y[5]=5。

sortedDistIndicies = distances.argsort()

2. 选择距离最小的k个点

classCount = {}

foriinrange(k):

# 找到该样本的类型

voteIlabel = labels[sortedDistIndicies[i]]

# 在字典中将该类型加一

# 字典的get方法

# 如:list.get(k,d) 其中 get相当于一条if...else...语句,参数k在字典中,字典将返回list[k];如果参数k不在字典中则返回参数d,如果K在字典中则返回k对应的value值

# l =

# print l.get(3,0)返回的值是4;

# Print l.get(1,0)返回值是0;

classCount[voteIlabel] = classCount.get(voteIlabel,) +1

3. 排序并返回出现最多的那个类型

# 字典的 items() 方法,以列表返回可遍历的(键,值)元组数组。

# sorted 中的第2个参数 key=operator.itemgetter(1) 这个参数的意思是先比较第几个元素

sortedClassCount =sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

returnsortedClassCount[][]

方法2:

1. 距离计算

# 欧氏距离: 点到点之间的距离

# 第一行: 同一个点 到 dataSet的第一个点的距离。

# 第二行: 同一个点 到 dataSet的第二个点的距离。

# ...

# 第N行: 同一个点 到 dataSet的第N个点的距离。

# [[1,2,3],[1,2,3]]-[[1,2,3],[1,2,0]]

# (A1-A2)^2+(B1-B2)^2+(c1-c2)^2

# inx - dataset 使用了numpy broadcasting

dist = np.sum((inx - dataset)**2, axis=1)**0.5

2. k个最近的标签

k_labels = [labels[index] for index in dist.argsort()[0 : k]]

#将这k个标签存在列表k_labels中

3. 出现次数最多的标签即为最终类别

label = Counter(k_labels).most_common(1)[][]

# 使用collections.Counter可以统计各个标签的出现次数,most_common返回出现次数最多的标签tuple,例如[('lable1', 2)],因此[0][0]可以取出标签值

returnlabel

ok,两种方法介绍完毕,我们现在来测试一下结果

print(classify0([0.1,0.1], group, labels,3))

输出:B

结果被分到了B类,目测看来还是挺准的!

下面我们用大量的数据做一个手写数字识别(这个网上有好多资料的,我这边就舍远求近了,就写一个大家都听说过的手写数字识别吧!)

导入训练数据

归一化特征值,消除属性之间量级不同导致的影响

参数:dataSet: 数据集

返回:归一化后的数据集normDataSet,ranges和minVals即最小值与范围,

归一化公式:

Y = (X-Xmin)/(Xmax-Xmin)

其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。

将图像数据转换为向量,我们的输入数据的图片格式是 32 * 32的,创建 1 * 1024 的NumPy数组,然后打开给定的文件,循环读出文件的前32行,并将每行的头32个字符值存储在NumPy数组中,最后返回数组。

最后我们开始分类了!

之后我们来运行一下代码看一看结果:

准确率还挺高!

大家也来动手试试吧!

资源地址:链接: https://pan.baidu.com/s/1YigcJWaz3gm6ZZixQfxB2A 密码: tiab

代码地址:https://www.bytelang.com/o/s/c/Z_KCdavDCyI=

我可能想强迫你关注这个公众号

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180718G1U2AQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券