机器学习之knn

机器学习

机器学习很简单的入门——KNN近邻算法，这是一个用于将未知事物分类到已经事物分类中的算法。这个算法的原理其实很简单的，就是求两点之间的距离，通过距离大小的判断最为主要依据来判断得出未知事物与k个最相近的已知事物，在通过每个已知事物出现的标签次数，来决策出未知事物的最终分类结果。

再深入理解下knn，其实就是计算两事物的相似性程度，这其实是knn算法的本质——通过相似度来实现分类的功能；既然我们已经知道了knn算法的本质是计算相似性程度，那么我们就可以采用很多种方式来计算两者的相似程度了，比如我前文说的计算两个点之间的距离来计算相似度，就是计算欧式距离；我们还可以计算两个向量之间的余弦值来计算相似度，等等还有很多，具体的请点击链接 相似度计算 。我最熟悉的就是一个欧拉距离，还有就是余弦相似度计算。

knn算法的具体步骤如下

  • 人工先进行分类，得出一个标准分类
  • 对事物特征进行 one-hot编码，也就是向量化
  • 对未知事物进行编码操作
  • 计算未知事物与所有已知事物的空间距离
  • 对距离从小到大排序，取出前k个距离最小的事物分类
  • 计算这k个事物中所有便签的出现次数，标签出现次数最多的，为该未知事物的最终分类

knn算法的python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np
import operator

def classify(input_data, dataSet, lables, k):
  dataSetSize = dataSet.shape[0]
  diffMat = np.tile(input_data, (dataSetSize, 1)) - dataSet
  diffMat = diffMat ** 2
  sqDistance = diffMat.sum(axis = 1)
  distance = sqDistance ** 0.5
  distance = distance.argsort()
  classCount = {}
  for i in range(k):
    voteLabel = lable[distance[i]]
    classCount[voteLable] = classCount.get(voteLable, 0) + 1
  classCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
  return classCount[0][0]

其中一些api的解释

  • np.tile(a, b)：a是待处理的对象，b是一个元组；假设有np.tile(1, (3, 2))，表示在行的方向上重复3次，列的方向上重复2次；最后结果如下
    np.tile()

  • argsort()：argsort()函数返回的是数组值从小到大的索引值

  • sorted(iterable, cmp, key, reverse)：iterable是一个list对象或者是iterator；cmp是带两个参数的比较函数；key是带一个参数的比较函数；reverse是是否逆序；

  • operator.itemgetter()：是获取对象某个域值的函数，这个不是返回指，而是定义了一个函数

knn算法的实际演示

1
2
3
4
5
6
7
8
9
10
def createDataSet():
  group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
  lables = ['A', 'A', 'B', 'B']
  return group, lables

def test():
  group, lables = createDataSet()
  input_data = [[1.1, 0.9], [0.012, 0.01], [0.989, 0.996], [0.997, 1.003]]
  for i in input_data:
    print classify(i, group, lables, 3)

输出结果

output_data_answer