社区首页 >专栏 >k-近邻算法

k-近邻算法

卡尔曼和玻尔兹曼谁曼

发布于 2019-01-22 03:17:45

74800

代码可运行

文章被收录于专栏：给永远比拿愉快给永远比拿愉快

运行总次数：0

代码可运行

从今天开始，与大家分享我学习《Machine Learning In Action》这本书的笔记与心得。我会将源码加以详细的注释，这是我自己学习的一个过程，也是想通过这种方式帮助需要学习的童鞋的一种方式。

k-近邻算法定义

k-近邻(k-Nearest Neighbour，kNN)算法采用测量不同特征值之间的距离的方法进行分类。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

用官方的话来说，所谓k近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例（也就是上面所说的k个邻居），这k个实例的多数属于某个类，就把该输入实例分类到这个类中。

k-近邻算法优缺点

这里引用《Machine Learing In Action》原文： Pros: High accuracy, insensitive to outliers, no assumptions about data Cons: Computationally expensive, requires a lot of memory Works with: Numeric values, nominal values

k-近邻算法流程

对未知类别属性的数据集中的每个点依次执行如下操作： (1) 计算已知类别数据集中的点与当前点之间的距离； (2) 按照距离递增次序排序； (3) 选取与当前点距离最小的k个点； (4) 确定前k个点所在类别的出现频率 (5) 返回前k个点出现频率最高的类别作为当前点的预测分类

k-近邻算法实现

下面根据以上的算法流程实现kNN算法

Python预备知识

下面说说程序中用到的一些Numpy中的一些知识 1. tile tile(A, reps) Construct an array by repeating A the number of times given by reps. 即将数组A扩展reps倍。有点抽象我们来看实例：

>>> a = np.array([0, 1, 2])
>>> np.tile(a, 2)
array([0, 1, 2, 0, 1, 2])
>>> np.tile(a, (2, 2))
array([[0, 1, 2, 0, 1, 2],
       [0, 1, 2, 0, 1, 2]])
>>> np.tile(a, (2, 1, 2))
array([[[0, 1, 2, 0, 1, 2]],
       [[0, 1, 2, 0, 1, 2]]])

>>> b = np.array([[1, 2], [3, 4]])
>>> np.tile(b, 2)
array([[1, 2, 1, 2],
       [3, 4, 3, 4]])
>>> np.tile(b, (2, 1))
array([[1, 2],
       [3, 4],
       [1, 2],
       [3, 4]])

其实就是，你如果把A当成一个数的话，最后形成的数组类型是reps类型的，而且形成数组的元素都是A。 2. sum sum(a, axis=None, dtype=None, out=None, keepdims=False) Sum of array elements over a given axis.

Axis or axes along which a sum is performed. The default (axis = None) is perform a sum over all the dimensions of the input array. axis may be negative, in which case it counts from the last to the first axis.

>>> np.sum([0.5, 1.5])
2.0
>>> np.sum([0.5, 0.7, 0.2, 1.5], dtype=np.int32)
1
>>> np.sum([[0, 1], [0, 5]])
6
>>> np.sum([[0, 1], [0, 5]], axis=0)
array([0, 6])
>>> np.sum([[0, 1], [0, 5]], axis=1)
array([1, 5])

对于二维数组，axis=0就是列相加，aixs=1就是行相加 3. sort、sorted以及argsort的区别 sort 只是list类型的内建函数，对其他非列表型序列不适用。原地排序，并不返回排序后的对象。 sorted是所有类型的内建函数 ,返回排序后的对象，原对象不改变。 argsort，属于numpy中的函数返回排序后元素在原对象中的下标。例如：

>>> x = np.array([3, 6, 0, 1, 5])
>>> x.argsort()
array([2, 3, 0, 4, 1])

实验数据

《Machine Learning In Action》实验数据及源码下载这里的实验数据是一个文本文件，总共有1000行，每一行的四个项目含义是：1. 每年获得的飞行常客里程数 2.玩视频游戏所消耗的时间百分比 3.每周消费的冰淇淋公升书 4.对这个人的喜欢程度(包括：不喜欢的人、魅力一般的人、极具魅力的人) 数据大致如下：

40920   8.326976    0.953952    largeDoses
14488   7.153469    1.673904    smallDoses
26052   1.441871    0.805124    didntLike
75136   13.147394   0.428964    didntLike
38344   1.669788    0.134296    didntLike
72993   10.141740   1.032955    didntLike
35948   6.830792    1.213192    largeDoses
42666   13.276369   0.543880    largeDoses
67497   8.631577    0.749278    didntLike
35483   12.273169   1.508053    largeDoses
50242   3.723498    0.831917    didntLike
63275   8.385879    1.669485    didntLike
5569    4.875435    0.728658    smallDoses
......

Python源码

classify0函数是k-近邻算法的源码实现，file2matrix函数用于从文件转给你读取数据，然后交给classify0函数进行处理。

# @param inX 要进行分类的数据（一个一维数组）
# @param dataSet 已知类别的数据集（一个二维数组）
# @param labels 已知类型的数据集的分类标签(一个一维数组)
# @param k k-近邻算法中的参数k
# @return 
def classify0(inX, dataSet, labels, k):
    # ndarray.shape
    # the dimensions of the array.
    # This is a tuple of integers indicating the size of the array in each dimension.
    # For a matrix with n rows and m columns, shape will be (n, m).
    # The length of the shape tuple is therefore the rank, or number of dimensions, ndim.
    dataSetSize = dataSet.shape[0]# 获得dataSet的行数
    # numpy.tile = tile(A, reps)
    # Construct an array by repeating A the number of times given by reps
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet# 将inX扩展成dataSetSize行，然后减去dataSet，即就是扩展以后的二维数组和dataSet相同位置的数字的差组成的新的二维矩阵
    sqDiffmat = diffMat ** 2
    sqDistances = sqDiffmat.sum(axis = 1)# 计算矩阵行的和
    distances = sqDistances ** 0.5 #开方运算，这就是计算出来的距离
    sortedDistIndicies = distances.argsort()# 返回从小到大排序以后的下标位置
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]] #依次获得第k小的距离的数据所对应的标签
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1# get函数中的0是默认值，这里统计每个标签出现的次数
    # Both list.sort() and sorted() accept a reverse parameter with a boolean value. This is using to flag descending sorts
    # 这里sorted的第一个参数是要排序的集合，key是根据什么排序，这个是classCount字典类型的第二个字段即就是按照Label的个数排序
    sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse = True)# 按照标签出现的次数从大到小排列
    return sortedClassCount[0][0]# 返回出现次数最多的标签

# @param filename 保存数据的文件名称
# @return 返回数据集合和标签集合
def file2matrix(filename):
    fr = open(filename)
    contents = fr.readlines()
    numberOfLines = len(contents)
    returnMat = zeros((numberOfLines, 3))
    classLabelVector = []
    index = 0
    for line in contents:
        # Return a copy of the string with leading and trailing whitespace removed
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, : ] = listFromLine[0:3]
        classLabelVector.append(listFromLine[-1])
        index += 1
    return returnMat, classLabelVector