机器学习笔记-2.kNN

本系列是笔者在贪心科技-机器学习教程的学习笔记, 补充有python相关的知识.初学机器学习, 还请多多指教.

一句话描述kNN算法, 就是找最像目标元素的前k个元素, 以这些元素的多数类别为目标的类别.

换成几何的表述方式,就是在若干维度上, 找到跟目标元素距离最近的k个元素, 以他们的多数分类为目标分类.

kNN的实施流程

  1. 把一个物体表示成向量
  2. 标记号每个物体的标签
  3. 计算两个物体之间的距离/相似度
  4. 选择合适的K, 统计标签得出结果

在《机器学习实战》中有一个简单的示例, 摘抄标注在下方. 这个案例中一共四个已知的点, 共AB两个分类, 我们通过计算与目标点(0.3,0.3)最近的点的分类(这里很显然最近的点依次是:B类,B类,A类,A类)来判断目标点的分类. 如果k取3, 则B类数量2, 大于A类数量1, 则判断目标点分类为B.

import numpy as np
import operator
import matplotlib.pyplot as plt


def createDataSet():
    """
    定义数据集, 可以看下面的图示, 一共4个点, 两种分类
    """
    group = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


def classify0(inX, dataSet, labels, k):
    """
    这里实现了一个kNN算法, 也可以使用sklearn的KNeighborsClassifier模型快速完成
    """
    # shape是ndarray的结构定义, 是一个tuple, 其中每个元素是一个维度上
    # 数据的长度,这里取0即第一个维度长度
    dataSetSize = dataSet.shape[0]
    # tile意为瓷砖,瓦片,或者平铺瓷砖的动作.
    # tile(a,(x,y))指的是复制a为x*y的"矩阵".关于tile方法可
    # 参考https://www.jianshu.com/p/9519f1984c70
    # 所以本行的意义是复制inX数组构造成跟dataSet相同的数据格式
    inXArray = np.tile(inX, (dataSetSize, 1))
    # 数组相减求差值
    diffMat = inXArray - dataSet
    # ** 操作符是幂运算符, 这里是求数组内所有的数字取自身平方
    sqDiffMat = diffMat ** 2
    # 数组内所有数字取和,axis参数指定降维到指定维度, 这里axis=1即
    # 降维到剩下一个一维数组
    sqDiffDistances = sqDiffMat.sum(axis=1)
    # 开方操作
    distances = sqDiffDistances ** 0.5
    # 获取排序下标(从小到大元素的索引值)
    sortedDistanceIndicies = distances.argsort()

    classCount = {}
    # 遍历前k个近邻
    for i in range(k):
        # 获取第i近的近邻的类型label
        voteLabel = labels[sortedDistanceIndicies[i]]
        # 统计每个类型的数量
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    # 对类型统计排序
    sortedClassCount = sorted(classCount.items(),
                              key=operator.itemgetter(1),
                              reverse=True)
    # 获取第一个元素的,第一个维度的值(即距离最近的一个近邻label)
    return sortedClassCount[0][0]


dataSet, labels = createDataSet()

# 使用分类器计算[0.3, 0.3]这个点的类别
labelX = classify0([0.3, 0.3], dataSet, labels, 3)
print(labelX)
figure = plt.figure()
ax = figure.add_subplot(111)
# 根据数据集的定义, 我们把A类数据画成orange点, B类数据画成black点
ax.scatter(dataSet[[0, 1], 0], dataSet[[0, 1], 1], c='orange')
ax.scatter(dataSet[[2, 3], 0], dataSet[[2, 3], 1], c='black')
ax.scatter([0.3], [0.3], c='red')  # 测试scatter方法
plt.show()

exit(0)
黑色=A类; 橙色=B类; 红色=待分类

kNN的k值选择

1. k值对算法有什么影响? 影响准确率, 影响决策边界的平滑度.

2. 什么是算法的决策边界? 简而言之就是分类边界, 越平滑越好.

决策边界

决策边界

决策边界举例

决策边界决定线性分类器 和 非线性分类器.

  • 模型的准确率
  • 模型的稳定性

决策边界的绘制

TODO 略过

交叉验证 aka 调参

千万不能使用测试数据来调参!
千万不能使用测试数据来调参!
千万不能使用测试数据来调参!

k-fold Cross Validation k折交叉验证

因为重复三遍的重要原因, 所以我们使用训练数据中的部分抽样来交叉验证模型, 注意这里说的验证跟最终使用测试数据来测试模型是两码事. 这里介绍了一种从训练数据中抽样的方法: k折交叉验证.

从训练数据中k等分数据, 每次从中抽取一份数据作为验证数据验证模型准确性, 最终使用k次准确性的期望作为整体模型的准确性
import pandas as pd
import numpy as np
from collections import Counter
import matplotlib.pyplot as plt
from sklearn.model_selection import KFold

for k in krange:
    # k折交叉验证
    kf = KFold(n_splits=kFoldSplits)
    accTotal = 0
    for train, test in kf.split(trainSet):
        """
        对每个(交叉验证)测试集计算准确率, 最终计算出均值
        """
        trainX = trainSet[train][:, [0, 1, 2]]
        trainy = trainSet[train][:, 3]
        testX = trainSet[test][:, [0, 1, 2]]
        testy = trainSet[test][:, 3]  # 实际值

        # 构造模型来计算
        kClassify = KNeighborsClassifier(n_neighbors=k).fit(trainX, trainy)
        knn = kClassify.predict(testX)  # knn计算出的预测值

        falseCnt = 0
        for i in range(len(knn)):
            if testy[i] != knn[i]:
                falseCnt = falseCnt + 1

        accTotal = accTotal + falseCnt / len(knn)
    accAve = accTotal / kFoldSplits
    print("k:", k + 1, ", accAve:", accAve)

kNN在回归场景的应用

预测二手车价格案例

回归场景跟分类场景很相似, 不同的是我们不再使用top k来多数投票, 而是使用top k计算加权平均值, 作为最终的数值结果.

kNN的拓展&优化

如何做大数据量的优化?

1. K-D Tree
2. Locality Sensitivity Hashing(LSH)

如何处理特征之间的关系?

Mahalanobis Distance

如何处理样本的重要性?

weighted kNN

能不能利用Kernel Trick?

kernelized kNN

大类吞小类问题

smote方法

发表评论

电子邮件地址不会被公开。

÷ 1 = 7