k-临近算法

算法步骤

k 临近算法的伪代码，对位置类别属性的数据集中的每个点依次执行以下操作：

  1. 计算已知类别数据集中的每个点与当前点之间的距离；
  2. 按照距离递增次序排序；
  3. 选取与当前点距离最小的k个点；
  4. 确定前k个点所在类别的出现频率；
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类。

Python 代码为 kNN.py 的 classify0方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def classify0(inX, dataSet, label, k):
    '''
    kNN 算法实现函数
    输入参数解释如下
    inX: 输入数据
    dataSet: 已有的数据集, array 类型
    labels: 已有数据集的已知标签, list 类型
    k: k临近算法中的k值(通常， k < 20)
    '''
    dataSetSize = dataSet.shape[0] # 获取数据集中的数据条数
    diffMat = np.tile(inX, (dataSetSize, 1) ) - dataSet # 获取差值
    sqDiffMat = diffMat ** 2 # 矩阵中的每个元素 ^2
    sqDistances = sqDiffMat.sum(axis = 1) # 对每行进行求和
    distances = sqDistances ** (0.5) # 开平方，得到真正的距离
    sortedDistIndicies = distance.argsort() # 得到脚标的排序，排在越前面，距离越近
    classCount = {}
    for i in range(k):
        # 选择距离最小的k个点进行投票
        voteIlabel = labels[sortedDisIndicies[i]] # 得到label
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
        # get 的第二个参数 default -- 如果指定键的值不存在时，返回该默认值值。
        pass
    # 下面进行最后排序
    sortedClassCount = sorted(classCount.iteritems(),
                              key = operator.itemgetter(1),
                              reverse = True) # 结果为列表
    return sortedClassCount[0][0]
    pass

另：算法中的几个方法的例子

因为算法中用到了numpy中的一些方法，这些方法以前没接触过，放一些截图在这里可以直观的理解这些方法：

np.shape

返回 array 的“形状”， 长宽：

np.tile

把数据进行某种“平铺”操作。

**运算符

array 中每个元素 ^2

sum 方法

对array 可以使用 sum 方法进行求和操作，但是sum 方法可以有参数：

axis = 1代表了对每行分别进行求和

sorted 方法

测试

代码为： kNN.py

python kNN.py

可以看到输出，这里使用[0,0] 作为输入数据，输出结果应该是B。

虽然这个代码实际意义不大，但是可以作为学习kNN入门的一个不错的示例。