复习KNN并实现

今天复习了一下KNN算法，用两种方法手动实现，在iris数据集上训练及测试。
KNN理论很简单，略，这里直接上代码。

import numpy as np
import functools
from collections import Counter
from sklearn import datasets
from sklearn.model_selection import train_test_split


# 导入iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2003)


def euc_dis(instance1, instance2):
    """
    计算两个样本instance1和instance2之间的欧式距离

    :param instance1: 第一个样本， array型
    :param instance2: 第二个样本， array型
    :return 二者欧式距离
    """

    distance = np.sqrt(functools.reduce(lambda a, b: a ** 2 + b ** 2, instance1 - instance2))
    # 或者可以写作：
    # distance = np.sqrt(sum((instance1-instance2)**2))

    return distance


def knn_classify(X, y, testInstance, k):
    """
    给定一个测试数据testInstance, 通过KNN算法来预测它的标签。

    :param X: 训练数据的特征
    :param y: 训练数据的标签
    :param testInstance: 测试数据，这里假定一个测试数据 array型
    :param k: 选择多少个neighbors
    :return 返回testInstance的预测标签 = {0,1,2}
    """

    dist = []    # [(类别, 距离)]
    for i in range(len(X)):
        # 计算输入实例与每个样本的欧式距离
        distance = euc_dis(testInstance, X[i])
        category = y_train[i]
        dist.append((category, distance))
        # dist.append((distance, category))

    # dist按距离升序排序，取前k个样本
    dist_asc = sorted(dist, key=lambda x: x[1])[:k]
    print("前k个样本的dist_asc：", dist_asc)

    # 统计这k个样本的类别及数量
    cate_dict = {}    # {类别:数量}
    for item in dist_asc:
        if item[0] in cate_dict.keys():
            cate_dict[item[0]] += 1
        else:
            cate_dict[item[0]] = 1
    print("cate_dict：", cate_dict)
    # 按数量判定类别
    label = sorted(cate_dict.items(), key=lambda x: x[1], reverse=True)[0][0]
    print("类别：", label)
    return label

def knn_classify_simple(X, y, testInstance, k):
    """
    【简易版实现】
    给定一个测试数据testInstance, 通过KNN算法来预测它的标签。

    :param X: 训练数据的特征
    :param y: 训练数据的标签
    :param testInstance: 测试数据，这里假定一个测试数据 array型
    :param k: 选择多少个neighbors
    :return 返回testInstance的预测标签 = {0,1,2}
    """

    distances = [euc_dis(testInstance, x) for x in X]
    knn_index = np.argsort(distances)[:k]    # knn_index记录最近邻的下标
    count = Counter(y[knn_index])
    label = count.most_common()[0][0]
    return label

# 预测结果
predictions = [knn_classify(X_train, y_train, data, 3) for data in X_test]
# predictions = [knn_classify_simple(X_train, y_train, data, 3) for data in X_test]
print(predictions)
correct = np.count_nonzero((predictions == y_test) == True)
print("Accuracy is: %.3f" % (correct / len(X_test)))    # 0.921

决策边界

决策边界分成两大类，分别是线性决策边界和非线性决策边界。拥有线性决策边界的模型我们称为线性模型，反之非线性模型。

k值的选择

随着K值的增加，决策边界会变得更加平滑。决策边界的平滑也意味着模型的稳定性。这个其实很好理解，平时工作当中多个人共同决策要比一个人决策会大概率上减少犯错误。但稳定不代表，这个模型就会越准确。

平衡稳定性和准确率的方法：交叉验证