k-临近算法

算法步骤

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

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

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

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入门的一个不错的示例。