机器学习基础-knn

本系列整理自《统计学习方法》与《机器学习实战》内容。

本章介绍knn算法及相关python代码实现。

knn算法

算法描述

输入:训练数据集$T={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$

输出:实例x所属类别

(1)在给定距离度量下,在训练集$T$中找出与实例x最近邻的k个点,涵盖这k个点的x的邻域记为$N_k(x)$;

(2)在$N_k(x)$中根据分类决策规则(如多数表决)决定x的类别
$$
y=arg \ \max_{c_j}\sum_{x\in N_k(x)}I(y_i=c_j)
$$

代码实现

采用线性扫描,即遍历所有样本点计算最近邻k个点,再进行投票。

几个特殊函数tile(a,rep),argsort(),sorted(iterable,cmp,key,reverse),operator.itemgetter()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from numpy import *
import operator

def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances**0.5
sortedDistIndicies = distances.argsort() #返回distances降序排列对应原始索引
classCount={}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #get(value,default=None)获
#取dict内元素,若不存在,则返回默认值
## sorted(iterable,cmp,key,reverse) 适用于所有可迭代对象
# key--用于比较的元素,表示iterable中对应哪一个元素
## b=operator.itemgetter(i)
## b(a)--返回多维数据a索引为i的元素
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
## 等效表达
# sortedClassCount = sorted(classCount.iteritems(),key=lambda x:x[1],reverse=True)
return sortedClassCount[0][0]

kd树

实现k近邻算法,主要考虑如何快速对训练数据扫描以确定最小距离点。普通的线性扫描在面对大规模数据显得尤为耗时。

构造kd树

输入:k维空间数据集$T={x_1,x_2,\dots,x_N}$,其中$x_i=(x_i^{(1)},x_i^{(2)},\dots,x_i^{(k)})^T$

输出:kd树

(1)开始:构造根节点,对应于包含T的k维空间的超矩形区域

​ 选择$x^{(1)}$为坐标轴,以T中所有实例的$x^{(1)}$坐标的中位数为切分点,将超巨星区域切分为两个子区域,切分由通过切分点且与坐标轴$x^{(1)}$垂直的超平面实现

​ 由根节点生成深度为1的左右子节点:左子节点对应坐标$x^{(1)}$小于切分点的子区域,左子节点对应坐标$x^{(1)}$大于切分点的子区域。

​ 将落在切分超平面的实例点保存在根节点

(2)重复:对深度为j的节点,选择$x^{(l)}$为切分坐标轴,$l=j(mod \ k)+1$,余下操作类似(1)

(3)直到两个子区域没有实例存在时停止

image.png

最近邻搜索

输入:已构造的kd树,目标点x

输出:x的最近邻

(1)确定包含x叶节点:从根节点出发,递归向下访问kd树,若目标点x当前维坐标小于切分点,移动到左子节点,否则相反。直到子节点为叶节点

(2)以此叶节点为“当前最近点“

(3)递归向上回退:

​ (a)若该节点距目标点x更小,则更新“当前最近点”

​ (b)当前最近点一定存在于该节点一个子节点对应区域。检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。具体的,检查另一个子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。如果相交,可能在另一个子结点对应的区域内存在距离目标更近的点,移动到另一个子结点。接着,递归的进行最近邻搜索。如果不相交,向上回退。

(4)当回退到根结点时,搜索结束。最后的“当前最近点”即为x的最近邻点。

本文标题:机器学习基础-knn

文章作者:Lumo Wang

发布时间:2018年03月23日 - 14:03

最后更新:2019年04月17日 - 20:04

原始链接:https://luameows.github.io/2018/03/23/学习笔记-机器学习基础-knn/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~