统计学习方法笔记 第三章 K近邻算法

---

1. k近邻算法

算法1：k近邻算法

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

$y=arg\max_{c_j}\sum_{x_i\in{N_k(x)}}I(y_i=c_j),i=1,2,...,N: j=1,2,...,K$y=argcj​max​xi​∈Nk​(x)∑​I(yi​=cj​),i=1,2,...,N:j=1,2,...,K

---

2. k近邻模型

k近邻模型的三个基本要素是:

• 距离度量
• k值的选择
• 分类决策规则

2.1 模型

k近邻模型中，当训练集，距离度量，k值及分类决策规则确定后，对于任何一个新的输入实例，所属的类唯一决定。特征空间中每一个训练点控制的区域叫做单元，在特征空间中，通过单元的标记确定划分。

2.2 距离度量

• $L_p$Lp​距离 $L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}$Lp​(xi​,xj​)=(l=1∑n​∣xi(l)​−xj(l)​∣p)p1​
• 欧氏距离(p=2) $L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}}$L2​(xi​,xj​)=(l=1∑n​∣xi(l)​−xj(l)​∣2)21​
• 曼哈顿距离(p=1) $L_1(x_i,x_j)=\sum_{l=1}^{n}|x_i^{(l)}-x_j^{(l)}|$L1​(xi​,xj​)=l=1∑n​∣xi(l)​−xj(l)​∣
• (p=$\infty$∞) $L_{\infty}(x_i,x_j)=\max_l|x_i^{(l)}-x_j^{(l)}|$L∞​(xi​,xj​)=lmax​∣xi(l)​−xj(l)​∣

由不同的距离度量所确定的最近邻点是不同的。

2.3 k值选择

k值的选择会对k近邻的结果起到重大影响，选择小k值会使得模型变得过于复杂，过拟合于训练数据，选择较大的k值会使得模型变得过于简单，近似误差会变的很大，在实际中k值一般不超过20。

2.4 分类决策规则

分类决策规则一般是多数表决，多数表决规则等价于经验风险最小化。

---

3. kd树

实现k近邻算法时，需要考虑如何完成快速搜索，可以考虑以空间换取时间的方法，采用kd树进行存储，使用kd树的时间复杂度是$O(\log{N})$O(logN)

3.1 构造kd树

kd树代表的是对k维空间的一种划分，构造kd树相当于不断用垂直于坐标轴的超平面将k维空间进行切分。每一个结点对应于一个超矩形区域。

算法2：构造平衡kd树

1. 开始构造根节点，对应于包含$T$T的$k$k维空间的超矩形区域。选择$x^(1)$x(1)为坐标轴，以所有实例点的$x^(1)$x(1)坐标的中位数作为切分点，将根节点对应的超矩形区域切分成俩个区域，切分线是通过切分点并且和$x^(1)$x(1)垂直的超平面。将落在切分线的点保存到根节点。
2. 对左右子节点重复这个过程，对深度为$j$j的节点，选择$x^{(l)}$x(l)为切分的坐标轴，$l=j(\mod{k})+1$l=j(modk)+1。
3. 直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

kd树的实现相当于一个训练过程，对于空间进行不断切割。

3.2 搜索kd树

算法3：最近邻搜索

1. 在kd树中寻找包含目标点的叶结点。

2. 以此叶结点作为当前最近点

3. 递归的向上回退，在每个结点进行以下操作：
   a. 如果当前结点保存的实例点更近，则更新当前最近点
   b.检查另一子结点对应的区域是否是以目标点为球心，以目标点和当前最近点的距离为半径的球体相交。

4. 当退回根结点时，搜索结束，当前最近点即为$x$x的最近邻点。

kd树搜索适合训练实例远大于空间维数的k近邻算法。

---

4. Python代码

4.1 基本KNN

import numpy as np
import operator
import collections

"""
函数说明:创建数据集
Parameters:
	无
Returns:
	group - 数据集
	labels - 分类标签
Modify:
	2017-07-13
"""
def createDataSet():
	#四组二维特征
	group = np.array([[1,101],[5,89],[108,5],[115,8]])
	#四组特征的标签
	labels = ['爱情片','爱情片','动作片','动作片']
	return group, labels

"""
函数说明:kNN算法,分类器
Parameters:
	inX - 用于分类的数据(测试集)
	dataSet - 用于训练的数据(训练集)
	labes - 分类标签
	k - kNN算法参数,选择距离最小的k个点
Returns:
	sortedClassCount[0][0] - 分类结果
Modify:
	2017-11-09 by Cugtyt 
		* GitHub(https://github.com/Cugtyt) 
		* Email([email protected])
		Use list comprehension and Counter to simplify code
	2017-07-13
"""
def classify0(inx, dataset, labels, k):
	# 计算距离
	dist = np.sum((inx - dataset)**2, axis=1)**0.5
	# k个最近的标签
	k_labels = [labels[index] for index in dist.argsort()[0 : k]]
	# 出现次数最多的标签即为最终类别
	label = collections.Counter(k_labels).most_common(1)[0][0]
	return label

if __name__ == '__main__':
	#创建数据集
	group, labels = createDataSet()
	#测试集
	test = [101,20]
	#kNN分类
	test_class = classify0(test, group, labels, 3)
	#打印分类结果
	print(test_class)

4.2 kd Tree

import numpy as np
class Node:
    def __init__(self, data, lchild = None, rchild = None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild

class KdTree:
    def __init__(self):
        self.kdTree = None

    def create(self, dataSet, depth):   #创建kd树，返回根结点
        if (len(dataSet) > 0):
            m, n = np.shape(dataSet)    #求出样本行，列
            midIndex = int(m / 2) #中间数的索引位置
            axis = depth % n    #判断以哪个轴划分数据
            sortedDataSet = self.sort(dataSet, axis) #进行排序
            node = Node(sortedDataSet[midIndex]) #将节点数据域设置为中位数，具体参考下书本
            leftDataSet = sortedDataSet[: midIndex] #将中位数的左边创建2改副本
            rightDataSet = sortedDataSet[midIndex+1 :]
            node.lchild = self.create(leftDataSet, depth+1) #将中位数左边样本传入来递归创建树
            node.rchild = self.create(rightDataSet, depth+1)
            return node
        else:
            return None

    def sort(self, dataSet, axis):  #采用冒泡排序，利用aixs作为轴进行划分
        sortDataSet = dataSet[:]    #由于不能破坏原样本，此处建立一个副本
        m, n = np.shape(sortDataSet)
        for i in range(m):
            for j in range(0, m - i - 1):
                if (sortDataSet[j][axis] > sortDataSet[j+1][axis]):
                    temp = sortDataSet[j]
                    sortDataSet[j] = sortDataSet[j+1]
                    sortDataSet[j+1] = temp
        return sortDataSet

    def preOrder(self, node):
        if node != None:
            print("tttt->%s" % node.data)
            self.preOrder(node.lchild)
            self.preOrder(node.rchild)

    def search(self, tree, x):
        self.nearestPoint = None    #保存最近的点
        self.nearestValue = 0   #保存最近的值
        def travel(node, depth = 0):    #递归搜索
            if node != None:    #递归终止条件
                n = len(x)  #特征数
                axis = depth % n    #计算轴
                if x[axis] < node.data[axis]:   #如果数据小于结点，则往左结点找
                    travel(node.lchild, depth+1)
                else:
                    travel(node.rchild, depth+1)

                #以下是递归完毕后，往父结点方向回朔
                distNodeAndX = self.dist(x, node.data)  #目标和节点的距离判断
                if (self.nearestPoint == None): #确定当前点，更新最近的点和最近的值
                    self.nearestPoint = node.data
                    self.nearestValue = distNodeAndX
                elif (self.nearestValue > distNodeAndX):
                    self.nearestPoint = node.data
                    self.nearestValue = distNodeAndX

                print(node.data, depth, self.nearestValue, node.data[axis], x[axis])
                if (abs(x[axis] - node.data[axis]) <= self.nearestValue):  #确定是否需要去子节点的区域去找（圆的判断）
                    if x[axis] < node.data[axis]:
                        travel(node.rchild, depth+1)
                    else:
                        travel(node.lchild, depth + 1)
        travel(tree)
        return self.nearestPoint

    def dist(self, x1, x2): #欧式距离的计算
        return ((np.array(x1) - np.array(x2)) ** 2).sum() ** 0.5

dataSet = [[2, 3],
           [5, 4],
           [9, 6],
           [4, 7],
           [8, 1],
           [7, 2]]
x = [5, 3]
kdtree = KdTree()
tree = kdtree.create(dataSet, 0)
kdtree.preOrder(tree)
print(kdtree.search(tree, x))

---

5. 参考资料

• KNN实现
• kd树实现
• Cover T,Hart P.Nearest neighbor pattern classification

---