机器学习——k近邻判别法(KNN)

1.什么是KNN

KNN，K Nearest Neighbor(k近邻判别法),是一个常用的分类器（或用于聚类），我们通过选取K个邻近的点，来判断某个点的类别。

测试样本（绿色圆形）应归入要么是第一类的蓝色方形或是第二类的红色三角形。如果k=3（实线圆圈）它被分配给第二类，因为有2个三角形和只有1个正方形在内侧圆圈之内。如果k=5（虚线圆圈）它被分配到第一类（3个正方形与2个三角形在外侧圆圈之内）

KNN算法为分类算法。一句老话来描述KNN算法：“近朱者赤，近墨者黑”。

2.欧氏距离

两个数据：$dist=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

多个数据：$dist=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}$

3.基本实现方式

• 数据处理

  归一化、数据补全、数据降维

• 数据训练及识别

  计算欧拉距离→取距离最短的前k个标签→统计各类标签个数

4.部分代码

from numpy import *

# 给出训练数据以及对应的类别
def createDataSet():
    group = array([[1.0, 2.0], [1.2, 0.1], [0.1, 1.4], [0.3, 3.5]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

# 通过KNN进行分类
def classify(inputs, dataSet, label, k):
    """
    :param inputs 需要识别的序列
    :param dataSet 训练的数据
    :param label 训练的类别
    :param k 基准个数
    """
    dataSize = dataSet.shape[0]
    print("dataSize = %d" % dataSize)

    # 计算欧式距离
    diff = tile(input, (dataSize, 1)) - dataSet
    sqdiff = diff ** 2
    print(diff)
    print(sqdiff)
    squareDist = sum(sqdiff, axis=1)  # 行向量分别相加，从而得到新的一个行向量
    dist = squareDist ** 0.5
    print(dist)

    # 对距离进行排序
    sortedDistIndex = argsort(dist)  # argsort()根据元素的值从小到大对元素进行排序，返回下标
    print(sortedDistIndex)

    classCount = {}
    for i in range(k):
        print("i = %d"% i)
        voteLabel = label[sortedDistIndex[i]]
        print("voteLabel = %s" % voteLabel)
        # 对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

    # 选取出现的类别次数最多的类别
    maxCount = 0
    for key, value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes