《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第3章 k邻近邻法

《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第3章 k邻近邻法
《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第1章 统计学习方法概论
《统计学习方法：李航》笔记 从原理到实现（基于python）-- 第 2章感知机

我算是有点基础的（有过深度学习和机器学的项目经验），但也是半路出家，无论是学Python还是深度学习，都是从问题出发，边查边做，没有系统的学过相关的知识，这样的好处是入门快（如果想快速入门，大家也可以试试，直接上手项目，从小项目开始），但也存在一个严重的问题就是，很多东西一知半解，容易走进死胡同出不来（感觉有点像陷入局部最优解，找不到出路），所以打算系统的学习几本口碑比较不错的书籍。
??书籍选择： 当然，机器学习相关的书籍有很多，很多英文版的神书，据说读英文版的书会更好，奈何英文不太好，比较难啃。国内也有很多书，周志华老师的“西瓜书”我也有了解过，看了前几章，个人感觉他肯能对初学者更友好一点，讲述的非常清楚，有很多描述性的内容。对比下来，更喜欢《统计学习方法》，毕竟能坚持看完才最重要。
??笔记内容： 笔记内容尽量省去了公式推导的部分，一方面latex编辑太费时间了，另一方面，我觉得公式一定要自己推到一边才有用（最好是手写）。尽量保留所有标题，但内容会有删减，通过标黑和列表的形式突出重点内容，要特意说一下，标灰的部分大家最好读一下（这部分是我觉得比较繁琐，但又不想删掉的部分）。
??代码实现： 最后是本章内容的实践，如果想要对应的.ipynb文件，可以留言

第3章 k邻近邻法

??k近邻法（k-nearest neighbor，k-NN） 是一种基本分类与回归方法。

??k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

??k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。

??因此，k近邻法不具有显式的学习过程。k近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

??k值的选择、距离度量及分类决策规则是k近邻法的三个基本要素。

3.1 k近邻算法

??k近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

k近邻算法：

输入： 训练数据集

$$T=((x_1,y_1),(x_2,y_2),......(x_N,y_N))$$

??其中，$x_i\in R^n$为实例的特征向量，$y_i\in Y＝(c_1，c_2,\dots ,c_K)$为实例的类别

输出： 实例x所属的类y。

??（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作$N_k(x)$；
??（2）在$N_k(x)$中根据分类决策规则（如多数表决）决定x的类别y：

$$y=argmax\sum _{x_i\in N_k(x)}I(t_i=c_j),i=1,\mathrm{2....}N;j=1,\mathrm{2....}K$$

??其中，I为指示函数，即当$y_i＝c_j$时I为1，否则I为0。

3.2 k近邻模型

??k近邻法使用的模型实际上对应于对特征空间的划分。

??模型由三个基本要素——距离度量、k值的选择和分类决策规则决定。

3.2.1 模型

??特征空间中，对每个训练实例点$x_i$，距离该点比其他点更近的所有点组成一个区域，叫作单元（cell）。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分。

??最近邻法将实例$x_i$的类$y_i$作为其单元中所有点的类标记（class label）。这样，每个单元的实例点的类别是确定的。

3.2.2 距离度量

??特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是 n维实数向量空间$R^n$。 使用的距离是欧氏距离，但也可以是其他距离。

??设特征空间X是n维实数向量空间$R^n$$,x_i,x_i\in X$，$x_i=(x_i^{(1)},x_i^{(2)}\dots x_i^{(T)}{)}^T$，$x_j=(x_j^{(1)},x_j^{(2)}\dots x_j^{(n)}{)}^T$**

??$x_i,x_i$的距离$L_p$定义为：

$$L_p(x_i,x_j)=(\sum _{l=1}^n|x_i^{(l)}?x_j^{(l)}{|}^p{)}^{\frac{1}{p}}$$

• 当p≥1。当p＝2时，称为欧氏距离(Euclidean distance);
• 当p＝1时，称为曼哈顿距离（Manhattan distance）
• 当p＝∞ 时，它是各个坐标距离的最大值

下面的例子说明，由不同的距离度量所确定的最近邻点是不同的。

3.2.3 k值的选择

??k值的选择会对k近邻法的结果产生重大影响。

• 如果选择较小的k值： 就相当于用较小的邻域中的训练实例进行预测
  • “学习”的近似误差（approximation error）会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。
  • 但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感[2]。（如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合。）
• 如果选择较大的k值： 就相当于用较大邻域中的训练实例进行预测。
  • 其优点是可以减少学习的估计误差。
  • 但缺点是学习的近似误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。（k值的增大就意味着整体的模型变得简单。）

??在应用中，k值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。

3.2.4 分类决策规则

??k近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则（majority voting rule）：

??对给定的实例$x\in X$，其最近邻的k个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是：

$$\frac{1}{k}\sum _{x_i\in N_x(x)}I(y_i\ne c_j)=1?\frac{1}{k}\sum _{x_i\in N_x(x)}I(y_i=c_j)$$

??要使误分类率最小即经验风险最小，就要使${\sum }_{x_i\in N_x(x)}I(y_i=c_j)$最大，所以多数表决规则等价于经验风险最小化。

3.3 k近邻法的实现：kd树

??实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。
k近邻法最简单的实现方法是线性扫描（linear scan）。这时要计算输入实例与每一个训练实例的距离。
??为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。

3.3.1 构造kd树

??kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

??kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

构造kd树的方法如下：

• 构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；
• 通过下面的递归方法，不断地对k维空间进行切分，生成子结点。
• 在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；
• 这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。

3.3.2 搜索kd树

??下面介绍如何利用kd树进行k近邻搜索。可以看到，利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

??这里以最近邻为例加以叙述，同样的方法可以应用到k近邻。

• 给定一个目标点，搜索其最近邻。
• 首先找到包含目标点的叶结点；
• 然后从该叶结点出发，依次回退到父结点；
• 不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。

??这样搜索就被限制在空间的局部区域上，效率大为提高。

??包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部（参阅图3.5）。

??然后返回当前结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法转到更上一级的父结点，继续上述过程。如果父结点的另一子结点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。

算法实现

import math
from itertools import combinations

def L(x, y, p=2):
	# x1 = [1, 1], x2 = [5,1]
	if len(x) == len(y) and len(x) > 1:
		sum = 0
		for i in range(len(x)):
			sum += math.pow(abs(x[i] - y[i]), p)
		return math.pow(sum, 1 / p)
	else:
	return 0

课本例3.1

x1 = [1, 1]
x2 = [5, 1]
x3 = [4, 4]

# x1, x2
for i in range(1, 5):
	r = {'1-{}'.format(c): L(x1, c, p=i) for c in [x2, x3]}
	print(min(zip(r.values(), r.keys())))
==============================
(4.0, '1-[5, 1]')
(4.0, '1-[5, 1]')
(3.7797631496846193, '1-[4, 4]')
(3.5676213450081633, '1-[4, 4]')

iris数据集

python实现，遍历所有数据点，找出n个距离最近的点的分类情况，少数服从多数

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter

# data
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']
# data = np.array(df.iloc[:100, [0, 1, -1]])

sepal length	sepal width	petal length	petal width	label
0	5.1	3.5	1.4	0.2
1	4.9	3.0	1.4	0.2
2	4.7	3.2	1.3	0.2
3	4.6	3.1	1.5	0.2
4	5.0	3.6	1.4	0.2
5	5.4	3.9	1.7	0.4
6	4.6	3.4	1.4	0.3
7	5.0	3.4	1.5	0.2
8	4.4	2.9	1.4	0.2
9	4.9	3.1	1.5	0.1
10	5.4	3.7	1.5	0.2
11	4.8	3.4	1.6	0.2
12	4.8	3.0	1.4	0.1
13	4.3	3.0	1.1	0.1
14	5.8	4.0	1.2	0.2
15	5.7	4.4	1.5	0.4
16	5.4	3.9	1.3	0.4
17	5.1	3.5	1.4	0.3
18	5.7	3.8	1.7	0.3
19	5.1	3.8	1.5	0.3
20	5.4	3.4	1.7	0.2
21	5.1	3.7	1.5	0.4
22	4.6	3.6	1.0	0.2
23	5.1	3.3	1.7	0.5
24	4.8	3.4	1.9	0.2
25	5.0	3.0	1.6	0.2
26	5.0	3.4	1.6	0.4
27	5.2	3.5	1.5	0.2
28	5.2	3.4	1.4	0.2
29	4.7	3.2	1.6	0.2
…	…	…	…	…
120	6.9	3.2	5.7	2.3
121	5.6	2.8	4.9	2.0
122	7.7	2.8	6.7	2.0
123	6.3	2.7	4.9	1.8
124	6.7	3.3	5.7	2.1
125	7.2	3.2	6.0	1.8
126	6.2	2.8	4.8	1.8
127	6.1	3.0	4.9	1.8
128	6.4	2.8	5.6	2.1
129	7.2	3.0	5.8	1.6
130	7.4	2.8	6.1	1.9
131	7.9	3.8	6.4	2.0
132	6.4	2.8	5.6	2.2
133	6.3	2.8	5.1	1.5
134	6.1	2.6	5.6	1.4
135	7.7	3.0	6.1	2.3
136	6.3	3.4	5.6	2.4
137	6.4	3.1	5.5	1.8
138	6.0	3.0	4.8	1.8
139	6.9	3.1	5.4	2.1
140	6.7	3.1	5.6	2.4
141	6.9	3.1	5.1	2.3
142	5.8	2.7	5.1	1.9
143	6.8	3.2	5.9	2.3
144	6.7	3.3	5.7	2.5
145	6.7	3.0	5.2	2.3
146	6.3	2.5	5.0	1.9
147	6.5	3.0	5.2	2.0
148	6.2	3.4	5.4	2.3
149	5.9	3.0	5.1	1.8

150 rows × 5 columns

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

class KNN:
    def __init__(self, X_train, y_train, n_neighbors=3, p=2):
        """
        parameter: n_neighbors 临近点个数
        parameter: p 距离度量
        """
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train

    def predict(self, X):
        # 取出n个点
        knn_list = []
        for i in range(self.n):
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            knn_list.append((dist, self.y_train[i]))

        for i in range(self.n, len(self.X_train)):
            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            if knn_list[max_index][0] > dist:
                knn_list[max_index] = (dist, self.y_train[i])

        # 统计
        knn = [k[-1] for k in knn_list]
        count_pairs = Counter(knn)
#         max_count = sorted(count_pairs, key=lambda x: x)[-1]
        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]
        return max_count

    def score(self, X_test, y_test):
        right_count = 0
        n = 10
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            if label == y:
                right_count += 1
        return right_count / len(X_test)

clf = KNN(X_train, y_train)
clf.score(X_test, y_test)
==============================
0.95

test_point = [6.0, 3.0]
print('Test Point: {}'.format(clf.predict(test_point)))
=================================
Test Point: 1.0

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.plot(test_point[0], test_point[1], 'bo', label='test_point')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

scikit-learn实例

from sklearn.neighbors import KNeighborsClassifier
clf_sk = KNeighborsClassifier()
clf_sk.fit(X_train, y_train)
======================================
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=None, n_neighbors=5, p=2,
           weights='uniform')


clf_sk.score(X_test, y_test)
========================================
0.95

kd树:构造平衡kd树算法

# kd-tree每个结点中主要包含的数据结构如下
class KdNode(object):
    def __init__(self, dom_elt, split, left, right):
        self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)
        self.split = split  # 整数（进行分割维度的序号）
        self.left = left  # 该结点分割超平面左子空间构成的kd-tree
        self.right = right  # 该结点分割超平面右子空间构成的kd-tree


class KdTree(object):
    def __init__(self, data):
        k = len(data[0])  # 数据维度

        def CreateNode(split, data_set):  # 按第split维划分数据集exset创建KdNode
            if not data_set:  # 数据集为空
                return None
            # key参数的值为一个函数，此函数只有一个参数且返回一个值用来进行比较
            # operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为需要获取的数据在对象中的序号
            #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
            data_set.sort(key=lambda x: x[split])
            split_pos = len(data_set) // 2  # //为Python中的整数除法
            median = data_set[split_pos]  # 中位数分割点
            split_next = (split + 1) % k  # cycle coordinates

            # 递归的创建kd树
            return KdNode(
                median,
                split,
                CreateNode(split_next, data_set[:split_pos]),  # 创建左子树
                CreateNode(split_next, data_set[split_pos + 1:]))  # 创建右子树

        self.root = CreateNode(0, data)  # 从第0维分量开始构建kd树,返回根节点


# KDTree的前序遍历
def preorder(root):
    print(root.dom_elt)
    if root.left:  # 节点不为空
        preorder(root.left)
    if root.right:
        preorder(root.right)

# 对构建好的kd树进行搜索，寻找与目标点最近的样本点：
from math import sqrt
from collections import namedtuple

# 定义一个namedtuple,分别存放最近坐标点、最近距离和访问过的节点数
result = namedtuple("Result_tuple",
                    "nearest_point  nearest_dist  nodes_visited")


def find_nearest(tree, point):
    k = len(point)  # 数据维度

    def travel(kd_node, target, max_dist):
        if kd_node is None:
            return result([0] * k, float("inf"),
                          0)  # python中用float("inf")和float("-inf")表示正负无穷

        nodes_visited = 1

        s = kd_node.split  # 进行分割的维度
        pivot = kd_node.dom_elt  # 进行分割的“轴”

        if target[s] <= pivot[s]:  # 如果目标点第s维小于分割轴的对应值(目标离左子树更近)
            nearer_node = kd_node.left  # 下一个访问节点为左子树根节点
            further_node = kd_node.right  # 同时记录下右子树
        else:  # 目标离右子树更近
            nearer_node = kd_node.right  # 下一个访问节点为右子树根节点
            further_node = kd_node.left

        temp1 = travel(nearer_node, target, max_dist)  # 进行遍历找到包含目标点的区域

        nearest = temp1.nearest_point  # 以此叶结点作为“当前最近点”
        dist = temp1.nearest_dist  # 更新最近距离

        nodes_visited += temp1.nodes_visited

        if dist < max_dist:
            max_dist = dist  # 最近点将在以目标点为球心，max_dist为半径的超球体内

        temp_dist = abs(pivot[s] - target[s])  # 第s维上目标点与分割超平面的距离
        if max_dist < temp_dist:  # 判断超球体是否与超平面相交
            return result(nearest, dist, nodes_visited)  # 不相交则可以直接返回，不用继续判断

        #----------------------------------------------------------------------
        # 计算目标点与分割点的欧氏距离
        temp_dist = sqrt(sum((p1 - p2)**2 for p1, p2 in zip(pivot, target)))

        if temp_dist < dist:  # 如果“更近”
            nearest = pivot  # 更新最近点
            dist = temp_dist  # 更新最近距离
            max_dist = dist  # 更新超球体半径

        # 检查另一个子结点对应的区域是否有更近的点
        temp2 = travel(further_node, target, max_dist)

        nodes_visited += temp2.nodes_visited
        if temp2.nearest_dist < dist:  # 如果另一个子结点内存在更近距离
            nearest = temp2.nearest_point  # 更新最近点
            dist = temp2.nearest_dist  # 更新最近距离

        return result(nearest, dist, nodes_visited)

    return travel(tree.root, point, float("inf"))  # 从根节点开始递归

例3.2

data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
kd = KdTree(data)
preorder(kd.root)
==================================
[7, 2]
[5, 4]
[2, 3]
[4, 7]
[9, 6]
[8, 1]

from time import clock
from random import random

# 产生一个k维随机向量，每维分量值在0~1之间
def random_point(k):
    return [random() for _ in range(k)]
 
# 产生n个k维随机向量 
def random_points(k, n):
    return [random_point(k) for _ in range(n)]

ret = find_nearest(kd, [3,4.5])
print (ret)
=========================================
Result_tuple(nearest_point=[2, 3], nearest_dist=1.8027756377319946, nodes_visited=4)

N = 400000
t0 = clock()
kd2 = KdTree(random_points(3, N))            # 构建包含四十万个3维空间样本点的kd树
ret2 = find_nearest(kd2, [0.1,0.5,0.8])      # 四十万个样本点中寻找离目标最近的点
t1 = clock()
print ("time: ",t1-t0, "s")
print (ret2)
=========================================
time:  5.4623788 s
Result_tuple(nearest_point=[0.09929288205798159, 0.4954936771850429, 0.8005722800665575], nearest_dist=0.004597223680778027, nodes_visited=42)