01-最近邻算法KNN

AI悦创原创
  • 数据分析
  • 机器学习
  • 数据挖掘
  • 机器学习算法
  • 数据分析
  • 机器学习
  • 数据挖掘
  • 机器学习算法
大约 8 分钟

在学习机器学习的时候,接触的第一个算法大都是 KNN。不过在介绍之前,请先允许我讲一下个别名词:

  • 交叉验证:将原始数据 随机 分成两组,一组作为训练集,一组作为验证集。训练集训练分类器,验证集验证分类器的效果,并将最后的准确率作为分类器的性能指标。
  • 特征缩放:将特征的取值控制在某一范围内,保证每个特征占据的权重一致。常用的是归一化和标准化。

原理介绍

简言之,KNN 算法计算不同特征值之间的距离对样本进行分类。

OK,说完结论,懂的可以直接看代码部分了,如果不能理解的请听我娓娓道来~现在有这么一组数据

电影名称打斗镜头拥抱镜头电影类型
谍影重重「A」572动作片
叶问3「B」652动作片
我的特工爷爷「C」214动作片
奔爱「D」446爱情片
夜孔雀「E」839爱情片
代理情人「F」238爱情片
这个杀手不太冷「G」496

上面6个样本(电影)分别给出其特征(打斗镜头、拥抱镜头)和标签(电影类型)信息,现在给定一个新的样本,我们想知道这部电影的类型。由于是2维数据,我们可以用平面直角坐标系表示。

绿色的点是未知的,红色的黄色的点是已知的。kNN要做的就是计算未知的点到所有已知点的距离,根据距离进行排序。

DA=(4957)2+(62)28.94 D_{A} = \sqrt{(49-57)^{2} + (6-2)^{2}} \approx 8.94

DB=(4965)2+(62)216.49 D_{B} = \sqrt{(49-65)^{2} + (6-2)^{2}} \approx 16.49

DC=(4921)2+(64)228.07 D_{C} = \sqrt{(49-21)^{2} + (6-4)^{2}} \approx 28.07

DD=(494)2+(646)260.21 D_{D} = \sqrt{(49-4)^{2} + (6-46)^{2}} \approx 60.21

DE=(498)2+(639)252.63 D_{E} = \sqrt{(49-8)^{2} + (6-39)^{2}} \approx 52.63

DF=(492)2+(638)256.86 D_{F} = \sqrt{(49-2)^{2} + (6-38)^{2}} \approx 56.86

排序后的数据如下,

电影名称与未知电影距离
谍影重重8.94
叶问316.49
我的特工爷爷28.07
夜孔雀52.63
代理情人56.86
奔爱60.21

我们在 KNN 算法中经常会听到说当 k=3 时、当 k=5 时......

这里的 k 指的就是样本数。在这个例子中,当 k=3 时,前三个样本出现最多的电影类型是动作片,因此《这个杀手不太冷》样本也应该归为动作片。同样的,当 k=5 时,前 5 个样本出现最多的电影类型也是动作片(35>25\frac{3}{5} > \frac{2}{5}),因此样本也属于动作片。

上面提到的是 2 维数据,但是我们现实中处理的样本可能有 3 个甚至更多特征,我们无法用视觉来抽象这些特征,但是计算方法还是一样的,只不过根号里做差的数变多了而已。

代码实现——Numpy

机器学习算法的一般流程可以归为三步。

  • 数据预处理
    1. 加载数据
    2. 交叉验证
    3. 归一化
  • 模型训练
  • 模型验证
Column 1Column 2Column 3
TextTextText

机器学习的任务就是从海量数据中找到有价值的信息, 所以在使用算法之前,我们要对数据进行预处理。

# 1. 加载莺尾花数据集
from sklearn import datasets

iris = datasets.load_iris()
X = iris.data
y = iris.target

如果我们查看 y 标签信息会发现,它的前 50 个值为 051—100 的值为 1,后 50 个值为 2。

如果直接交叉验证,取到的测试集数据可能都是 label 值为 2 的样本,这并不是我们想要的。「PS:有时候我们会选择十折交叉验证,也就是分为十组,然后每次会有一组当作验证集,其余做训练集」

所以在这之前,我们需要先对样本打乱顺序。zip() 能将可迭代的对象打包成元组,利用 * 操作符可以将元组解压为列表。

# 2. 实现交叉验证
import numpy as np


def train_test_split(X, y, ratio=0.3):
    # 乱序
    data = list(zip(X, y))
    np.random.shuffle(data)
    X, y = zip(*data)
    # 切割
    boundary_X = int((1 - ratio) * len(X))
    boundary_y = int((1 - ratio) * len(y))
    # 将 boundary_X 和 boundary_y 之前的作为训练集
    x_train = np.array(X[:boundary_X])
    x_test = np.array(X[boundary_X:])
    y_train = np.array(y[:boundary_y])
    y_test = np.array(y[boundary_y:])
    return x_train, x_test, y_train, y_test


x_train, x_test, y_train, y_test = train_test_split(X, y)
  • ratio: 比率,比例
  • boundary: 分界线,边界;界限,范围;
  • train: 培训,训练;
  • 一般来说,我们做训练集,的比例要大一些,占整体的 70%~60%,剩下的 30%~40%可以用来做验证。
  • 标签对应数据「label: 数据」
  1. 归一化主要有两种形式:0-1 均匀分布和标准正态分布。
# 3. 归一化
def normalization(data):
    """0-1 均匀分布"""
    return (data - data.min()) / (data.max() - data.min()) 


def standardization(data):
    """标准正态分布"""
    return (data - data.mean()) / data.std()


x_train = standardization(x_train)
x_test = standardization(x_test)

KNN 的“模型训练”有点不同于一般的模型训练过程,它们可能需要求一些参数,而 kNN 是计算未知点到已知点的距离。从严格意义上来说,这并不算是训练。

# 4. 距离计算
from collections import Counter


class KNNClassifier:
    """KNN 分类器"""
    def __init__(self, k):
        self._k = k
        self._X_train = None
        self._y_train = None

    def fit(self, X_train, y_train):
        self._X_train = X_train
        self._y_train = y_train

    # 预测X_predict样本的分类结果,这里的X_predict用的是交叉验证中的测试集
    def predict(self, X_predict):
        return np.array([self._predict(x) for x in X_predict])

    def _predict(self, x):
        # 计算输入样本_X_train到所有已知数据的距离
        distances = np.sqrt(np.sum((self._X_train - x)**2, axis=1))
        # 记录distances中前k个小的数对应的类别的出现次数
        votes = Counter(self._y_train[np.argpartition(distances, self._k)[: self._k]])
        # most_common(n)可以打印n个出现最多次元素的值和次数
        predict_y = votes.most_common(1)[0][0]
        return predict_y

    # 计算准确率
    def score(self, X_test, label):
        y_predict = self.predict(X_test)
        n_sample = len(label)
        right_sample = 0
        for i, e in enumerate(label):
            if y_predict[i] == e:
                right_sample += 1
        return right_sample / n_sample


knn = KNNClassifier(k=3)
knn.fit(x_train, y_train)
knn.score(x_test, y_test)

输出:

0.9555555555555556

超参数搜索函数

KNN 的参数不止是 k,距离模式 distype 也是它的参数。对于 k 和 distype 这两种参数的组合,可能会有很多不同的结果,不妨设计一个超参数搜索函数来优化 k 和 distype。

class KNNClassifierSuper(KNNClassifier):
    def __init__(self, k, distype):
        super().__init__(k)
        self.distype = distype

    def _predict(self, x):
        assert self.distype in ["1", "2", "3"], "Error distance type!"
        if self.distype == "1":
            distances = np.sum(abs(self._X_train - x), axis=1)
        elif self.distype == "2":
            distances = np.sqrt(np.sum((self._X_train - x)**2, axis=1))
        else:
            distances = np.max(abs(self._X_train - x), axis=1)
        votes = Counter(self._y_train[np.argpartition(distances, self._k)[: self._k]])
        predict_y = votes.most_common(1)[0][0]
        return predict_y


# ManhattanDistance —— "1"
# EuclideanDistance —— "2"
# ChebyshevDistance —— "3"
for k in range(3, 15, 2):
    for distype in range(1, 4):
        knn = KNNClassifierSuper(k, str(distype))
        knn.fit(x_train, y_train)
        print("k = {}\tdistype = {}\tscore = {}".format(
            k, distype, knn.score(x_test, y_test)))

输出:

k = 3	distype = 1	score = 0.9555555555555556
k = 3	distype = 2	score = 0.9555555555555556
k = 3	distype = 3	score = 0.9555555555555556
k = 5	distype = 1	score = 0.9777777777777777
k = 5	distype = 2	score = 0.9555555555555556
k = 5	distype = 3	score = 0.9555555555555556
k = 7	distype = 1	score = 0.9555555555555556
k = 7	distype = 2	score = 0.9555555555555556
k = 7	distype = 3	score = 0.9777777777777777
k = 9	distype = 1	score = 0.9777777777777777
k = 9	distype = 2	score = 0.9777777777777777
k = 9	distype = 3	score = 0.9777777777777777
k = 11	distype = 1	score = 0.9777777777777777
k = 11	distype = 2	score = 0.9777777777777777
k = 11	distype = 3	score = 0.9777777777777777
k = 13	distype = 1	score = 0.9777777777777777
k = 13	distype = 2	score = 0.9777777777777777
k = 13	distype = 3	score = 0.9555555555555556

代码实现——sklearn

上面我们用 Numpy 实现了交叉验证、归一化、距离计算等方法,这些在 sklearn 中都已经为我们封装好了。

from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn import preprocessing
from sklearn.neighbors import KNeighborsClassifier

# 加载莺尾花数据
iris = datasets.load_iris()
X, y = iris.data, iris.target

# 交叉验证
x_train, x_test, y_train, y_test = train_test_split(X, y, test_size=0.4)

# 归一化
x_train = preprocessing.scale(x_train)
x_test = preprocessing.scale(x_test)

# 距离计算 + 超参数搜索函数
# p = 1 manhattan_distance 
# p = 2 euclidean_distance
# arbitrary p minkowski_distance 
for k in range(3, 14, 2):
    for p in range(1, 5):
        knn = KNeighborsClassifier(n_neighbors=k, p=p)
        knn.fit(x_train, y_train)
        print("k = {}\tp = {}\tscore = {}".format(
            k, p, knn.score(x_test, y_test)))

笔记

  1. ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

ndarray 计算的时候尽量用 np 的属性(np.sum() 而不是 sum)


  1. ValueError: kth(=3) out of bounds (1)

计算距离的时候 np.sum() 需要指定 axis=1,不然会直接对多维数组进行 sum 得到一个数值,在 np.argpartition 会出错。


  1. np.sum() 如果不指定 axis 是无法广播的,会直接返回数值

  1. axis 一种较好的理解方式是把他看成消除器。对于 shape 为 (2L, 3L, 4L) 的数组 arr,np.sum(arr, axis=0)会返回 shape 为 (3L, 4L) 的数组,np.sum(arr, axis=1) 会返回 shape 为 (2L, 4L) 的数组,np.sum(arr, axis=0)会返回 shape 为 (2L, 3L) 的数组。

欢迎关注我公众号:AI悦创,有更多更好玩的等你发现!

公众号:AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQopen in new window

方法二:微信:Jiabcdefh

上次编辑于:
贡献者: AndersonHJB

你认为这篇文章怎么样?

  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度