【机器学习】监督学习之KNN

一、kNN算法分析

K最近邻(k-Nearest Neighbor,KNN)分类算法可以说是最简单的机器学习算法了。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。

比如上面这个图,我们有两类数据,分别是蓝色方块和红色三角形,他们分布在一个上图的二维中间中。那么假如我们有一个绿色圆圈这个数据,需要判断这个数据是属于蓝色方块这一类,还是与红色三角形同类。怎么做呢?我们先把离这个绿色圆圈最近的几个点找到,因为我们觉得离绿色圆圈最近的才对它的类别有判断的帮助。那到底要用多少个来判断呢?这个个数就是k了。如果k=3,就表示我们选择离绿色圆圈最近的3个点来判断,由于红色三角形所占比例为2/3,所以我们认为绿色圆是和红色三角形同类。如果k=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。从这里可以看到,k的值还是很重要的。

KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分[参考机器学习十大算法]。

总的来说就是我们已经存在了一个带标签的数据库,然后输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似(最近邻)的分类标签。一般来说,只选择样本数据库中前k个最相似的数据。最后,选择k个最相似数据中出现次数最多的分类。其算法描述如下:

1)计算已知类别数据集中的点与当前点之间的距离;

2)按照距离递增次序排序;

3)选取与当前点距离最小的k个点;

4)确定前k个点所在类别的出现频率;

5)返回前k个点出现频率最高的类别作为当前点的预测分类。

二、Python实现

对于机器学习而已,Python需要额外安装三件宝,分别是Numpy,scipy和Matplotlib。前两者用于数值计算,后者用于画图。安装很简单,直接到各自的官网下载回来安装即可。安装程序会自动搜索我们的python版本和目录,然后安装到python支持的搜索路径下。反正就python和这三个插件都默认安装就没问题了。

另外,如果我们需要添加我们的脚本目录进Python的目录(这样Python的命令行就可以直接import),可以在系统环境变量中添加:PYTHONPATH环境变量,值为我们的路径,例如:E:\Python\Machine Learning in Action

2.1、kNN基础实践

一般实现一个算法后,我们需要先用一个很小的数据库来测试它的正确性,否则一下子给个大数据给它,它也很难消化,而且还不利于我们分析代码的有效性。

首先,我们新建一个kNN.py脚本文件,文件里面包含两个函数,一个用来生成小数据库,一个实现kNN分类算法。代码如下:

[python]

  1. #########################################
  2. # kNN: k Nearest Neighbors
  3. # Input: newInput: vector to compare to existing dataset (1xN)
  4. # dataSet: size m data set of known vectors (NxM)
  5. # labels: data set labels (1xM vector)
  6. # k: number of neighbors to use for comparison
  7. # Output: the most popular class label
  8. #########################################
  9. from numpy import *
  10. import operator
  11. # create a dataset which contains 4 samples with 2 classes
  12. def createDataSet():
  13. # create a matrix: each row as a sample
  14. group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]])
  15. labels = ['A', 'A', 'B', 'B'] # four samples and two classes
  16. return group, labels
  17. # classify using kNN
  18. def kNNClassify(newInput, dataSet, labels, k):
  19. numSamples = dataSet.shape[0] # shape[0] stands for the num of row
  20. ## step 1: calculate Euclidean distance
  21. # tile(A, reps): Construct an array by repeating A reps times
  22. # the following copy numSamples rows for dataSet
  23. diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise
  24. squaredDiff = diff ** 2 # squared for the subtract
  25. squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row
  26. distance = squaredDist ** 0.5
  27. ## step 2: sort the distance
  28. # argsort() returns the indices that would sort an array in a ascending order
  29. sortedDistIndices = argsort(distance)
  30. classCount = {} # define a dictionary (can be append element)
  31. for i in xrange(k):
  32. ## step 3: choose the min k distance
  33. voteLabel = labels[sortedDistIndices[i]]
  34. ## step 4: count the times labels occur
  35. # when the key voteLabel is not in dictionary classCount, get()
  36. # will return 0
  37. classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
  38. ## step 5: the max voted class will return
  39. maxCount = 0
  40. for key, value in classCount.items():
  41. if value > maxCount:
  42. maxCount = value
  43. maxIndex = key
  44. return maxIndex

然后我们在命令行中这样测试即可:

[python]

  1. import kNN
  2. from numpy import *
  3. dataSet, labels = kNN.createDataSet()
  4. testX = array([1.2, 1.0])
  5. k = 3
  6. outputLabel = kNN.kNNClassify(testX, dataSet, labels, 3)
  7. print "Your input is:", testX, "and classified to class: ", outputLabel
  8. testX = array([0.1, 0.3])
  9. outputLabel = kNN.kNNClassify(testX, dataSet, labels, 3)
  10. print "Your input is:", testX, "and classified to class: ", outputLabel

这时候会输出:

[python]

  1. Your input is: [ 1.2 1.0] and classified to class: A
  2. Your input is: [ 0.1 0.3] and classified to class: B

2.2、kNN进阶

这里我们用kNN来分类一个大点的数据库,包括数据维度比较大和样本数比较多的数据库。这里我们用到一个手写数字的数据库,可以到这里下载。这个数据库包括数字0-9的手写体。每个数字大约有200个样本。每个样本保持在一个txt文件中。手写体图像本身的大小是32x32的二值图,转换到txt文件保存后,内容也是32x32个数字,0或者1,如下:

数据库解压后有两个目录:目录trainingDigits存放的是大约2000个训练数据,testDigits存放大约900个测试数据。

这里我们还是新建一个kNN.py脚本文件,文件里面包含四个函数,一个用来生成将每个样本的txt文件转换为对应的一个向量,一个用来加载整个数据库,一个实现kNN分类算法。最后就是实现这个加载,测试的函数。

[python]

  1. #########################################
  2. # kNN: k Nearest Neighbors
  3. # Input: inX: vector to compare to existing dataset (1xN)
  4. # dataSet: size m data set of known vectors (NxM)
  5. # labels: data set labels (1xM vector)
  6. # k: number of neighbors to use for comparison
  7. # Output: the most popular class label
  8. #########################################
  9. from numpy import *
  10. import operator
  11. import os
  12. # classify using kNN
  13. def kNNClassify(newInput, dataSet, labels, k):
  14. numSamples = dataSet.shape[0] # shape[0] stands for the num of row
  15. ## step 1: calculate Euclidean distance
  16. # tile(A, reps): Construct an array by repeating A reps times
  17. # the following copy numSamples rows for dataSet
  18. diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise
  19. squaredDiff = diff ** 2 # squared for the subtract
  20. squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row
  21. distance = squaredDist ** 0.5
  22. ## step 2: sort the distance
  23. # argsort() returns the indices that would sort an array in a ascending order
  24. sortedDistIndices = argsort(distance)
  25. classCount = {} # define a dictionary (can be append element)
  26. for i in xrange(k):
  27. ## step 3: choose the min k distance
  28. voteLabel = labels[sortedDistIndices[i]]
  29. ## step 4: count the times labels occur
  30. # when the key voteLabel is not in dictionary classCount, get()
  31. # will return 0
  32. classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
  33. ## step 5: the max voted class will return
  34. maxCount = 0
  35. for key, value in classCount.items():
  36. if value > maxCount:
  37. maxCount = value
  38. maxIndex = key
  39. return maxIndex
  40. # convert image to vector
  41. def img2vector(filename):
  42. rows = 32
  43. cols = 32
  44. imgVector = zeros((1, rows * cols))
  45. fileIn = open(filename)
  46. for row in xrange(rows):
  47. lineStr = fileIn.readline()
  48. for col in xrange(cols):
  49. imgVector[0, row * 32 + col] = int(lineStr[col])
  50. return imgVector
  51. # load dataSet
  52. def loadDataSet():
  53. ## step 1: Getting training set
  54. print "---Getting training set..."
  55. dataSetDir = 'E:/Python/Machine Learning in Action/'
  56. trainingFileList = os.listdir(dataSetDir + 'trainingDigits') # load the training set
  57. numSamples = len(trainingFileList)
  58. train_x = zeros((numSamples, 1024))
  59. train_y = []
  60. for i in xrange(numSamples):
  61. filename = trainingFileList[i]
  62. # get train_x
  63. train_x[i, :] = img2vector(dataSetDir + 'trainingDigits/%s' % filename)
  64. # get label from file name such as "1_18.txt"
  65. label = int(filename.split('_')[0]) # return 1
  66. train_y.append(label)
  67. ## step 2: Getting testing set
  68. print "---Getting testing set..."
  69. testingFileList = os.listdir(dataSetDir + 'testDigits') # load the testing set
  70. numSamples = len(testingFileList)
  71. test_x = zeros((numSamples, 1024))
  72. test_y = []
  73. for i in xrange(numSamples):
  74. filename = testingFileList[i]
  75. # get train_x
  76. test_x[i, :] = img2vector(dataSetDir + 'testDigits/%s' % filename)
  77. # get label from file name such as "1_18.txt"
  78. label = int(filename.split('_')[0]) # return 1
  79. test_y.append(label)
  80. return train_x, train_y, test_x, test_y
  81. # test hand writing class
  82. def testHandWritingClass():
  83. ## step 1: load data
  84. print "step 1: load data..."
  85. train_x, train_y, test_x, test_y = loadDataSet()
  86. ## step 2: training...
  87. print "step 2: training..."
  88. pass
  89. ## step 3: testing
  90. print "step 3: testing..."
  91. numTestSamples = test_x.shape[0]
  92. matchCount = 0
  93. for i in xrange(numTestSamples):
  94. predict = kNNClassify(test_x[i], train_x, train_y, 3)
  95. if predict == test_y[i]:
  96. matchCount += 1
  97. accuracy = float(matchCount) / numTestSamples
  98. ## step 4: show the result
  99. print "step 4: show the result..."
  100. print 'The classify accuracy is: %.2f%%' % (accuracy * 100)

测试非常简单,只需要在命令行中输入:

[python]

  1. import kNN
  2. kNN.testHandWritingClass()

输出结果如下:

[python]

  1. step 1: load data...
  2. ---Getting training set...
  3. ---Getting testing set...
  4. step 2: training...
  5. step 3: testing...
  6. step 4: show the result...
  7. The classify accuracy is: 98.84%

原文发布于微信公众号 - 数据科学与人工智能(DS_AI_shujuren)

原文发表时间:2015-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

tensorflow

3311
来自专栏Deep Learning 笔记

图像识别(三)cifar10.py

tf.app.flags.DEFINE_integer()等函数是添加了命令行的可选参数

3094
来自专栏锦小年的博客

MNIST数据集的格式转换

以前直接用的是sklearn或者TensorFlow提供的mnist数据集,已经转换为矩阵形式的数据格式。但是sklearn体用的数据集合并不全,一共只有300...

4155
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

图像处理中任意核卷积(matlab中conv2函数)的快速实现。

     卷积其实是图像处理中最基本的操作,我们常见的一些算法比如:均值模糊、高斯模糊、锐化、Sobel、拉普拉斯、prewitt边缘检测等等一些和领域相关的算...

8478
来自专栏人工智能

深度学习框架之一:Theano

正文共7163个字,1张图,预计阅读时间18分钟。 参考Lasagne官网(http://lasagne.readthedocs.io/en/latest/)t...

1996
来自专栏1039778的专栏

Python 数据分析学习笔记

一、基本语法 [1507772432114_7239_1507772402948.jpg] 资料地址:http://www.icoolxue.com/albu...

4166
来自专栏小樱的经验随笔

51Nod 1289 大鱼吃小鱼(模拟,经典好题)

1289 大鱼吃小鱼            题目来源:             Codility 基准时间限制:1 秒 空间限制:131072 KB 分值: ...

3207
来自专栏有趣的Python

15- 深度学习之神经网络核心原理与算法-多gpu实现CNN图片分类

4993
来自专栏AI研习社

博客 | MNIST 数据集载入线性模型

这节开始我们使用知名的图片数据库 「THE MNIST DATABASE」 作为我们的图片来源,它的数据内容是一共七a万张 28×28 像素的手写数字图片,并被...

1525
来自专栏Deep Learning 笔记

CNN+MNIST+INPUT_DATA数字识别

TALK IS CHEAP,SHOW ME THE CODE,先从MNIST数据集下载脚本Input_data开始

3663

扫码关注云+社区

领取腾讯云代金券