k近邻&kd树

1、k近邻

k近邻算法是懒惰学习的代表算法。之所以说k近邻懒惰,是因为它没有显示的训练过程。它的思路很简单,手头有一些带标签的样本,现在给定一个新的样本,找出已有样本中距离新样本最近的k个样本点,然后取这k个样本点标签的投票结果。

k近邻算法本身并不复杂,但有几个细节需要注意:

(1)距离度量

不同的距离度量可能产生不同的k近邻,从而直接影响预测结果。至于度量的选取要结合应用场景,关键在于我们需要知道在特定场景中如何量化两样本之间的相似度。

(2)k值选择

k值的选择没有经验性的方法,一般只能通过交叉验证来选取合适的k值。

如果k值选择较小,就相当于用较小的邻域中的训练实例进行预测,“学习”的近似误差会减小,只有与输入实例较近的训练实例才会对预测起作用,但估计误差会增大,预测结果会对近邻的实例点非常敏感,如果近邻的实例点恰巧是噪声,预测就会出错。相反如果k值选择较大,就相当于用较大的领域中的训练实例进行预测,近似误差会增大,但估计误差会减小。

对于k近邻法来说,k越大模型越简单,这一点乍一看不容易理解,但其实我们可以考虑极端情况k=N(N为样本数),此时任何新样本都会被归入当前样本集中实例最多的类别,从而丢失大量信息。反之,k越小模型越复杂,模型将面临过拟合风险。

(3)投票法

k近邻使用多数表决的投票法看起来十分自然,但我们也可以从最小化经验误差的角度来理解,如果分类的损失函数为0-1损失函数,则误分类概率为:

P(Y\neq f(X))=1-P(Y=f(X))

对于给定实例x\in X,其最近邻的k个训练实例构成集合N_k(x),若涵盖N_k(x)的区域的类别是c_j,则误分类概率为:

\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j)

要使误分类率最小即经验风险最小,就要使\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j)最大,这正是投票法(多数表决)所做的事情。

2、kd树

kd树是一种对k维空间中的实例点进行储存以便对其进行快速检索的树形数据结构。kd树是二叉树,表示对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分,构成一系列k维超矩形区域。

构造平衡kd树的流程如下:

输入:k维空间数据集T=\{x_1,x_2,\dots,x_N\}

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

(2)对深度为j的结点,选择x^{(l)}为切分的坐标轴(l=j(mod\ k)+1),以该结点区域中所有实例的x^{(l)}坐标的中位数为切分点,将该结点对应的超矩形区域划分为两个子区域,切分由通过切分点并与坐标轴x^{(l)}垂直的超平面实现。

(3)重复(2)直至划分得到的两个子区域中没有实例存在为止。

用kd树进行最近邻搜索的流程如下:

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

(1)在kd树中找到包含目标节点x的叶结点:从根结点出发,递归地向下访问kd树。若目标x当前维的坐标小于切分点坐标则移动到左子结点,否则移动到右子结点,直至子结点为叶结点为止。

(2)以此叶结点为“当前最近点”。

(3)递归地向上回退:

  • 若该结点保存的实例点比当前最近点距离目标更近,则以该点为“当前最近点”。
  • 当前最近点一定存在于该结点的一个子结点对应的区域。检查该子结点的父节点的另一个子结点对应的区域是否有更近的点,即检查另一子结点对应的区域是否与以目标节点为球心,以目标点到“当前最近点”的距离为半径的超球体相交。若相交,可能在另一个子结点对应区域中存在距离目标更近的点,移动到另一个子结点,继续递归地进行搜索。若不相交,向上回退。

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

以上就是利用kd树进行最近邻搜索的过程,同样的方法可以推广到k近邻。现在我们来思考一下这个算法的本质。

其实我个人理解的是,kd树的构造就是二分法在k维的应用。但是不太相同的是,kd树算法并不是选定一个轴后不断二分直至结束,而是做一次二分换一个轴,这是因为如果我们只选定一个轴做二分得到的结果并不能反映各样本之间距离的远近,而兼顾各个轴则能一定程度上度量样本之间的距离。

我们可以想象3维的情况,kd树最终会形成一系列的小正方体,我们要想找距离一个新样本点最近的样本点,只需要找到新样本点所在的小正方体,然后check这个小正方体中的样本以及和这个小正方体相邻的小正方体中的样本哪个距离新样本最近即可(相邻这个概念是很重要的,为便于理解,考虑在一维的情况下,此过程为找到新样本所在区间,然后检查此区间以及左右相邻区间中的样本点即可)。而相邻这个概念刚好和kd树的构造过程相符,我们不断回退的过程其实就是检查各个不同方向上的相邻超矩形的过程。这个过程十分高效,不难看出,平衡kd树寻找最近邻的复杂度是O( \log N)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 218,451评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,172评论 3 394
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,782评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,709评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,733评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,578评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,320评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,241评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,686评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,878评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,992评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,715评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,336评论 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,912评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,040评论 1 270
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,173评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,947评论 2 355

推荐阅读更多精彩内容

  • k 近邻法 k 近邻算法 k 近邻模型 k 近邻法的实现:kd 树 搜索 kd 树 k 近邻模型实现 k 近邻模型...
    千与千与阅读 568评论 0 3
  • k-近邻算法(kNN):采用测量不同特征值之间的距离方法进行分类 优点:简单好用,容易理解,精度高,理论成熟,既可...
    山雾幻华阅读 672评论 0 2
  • 一.朴素贝叶斯 1.分类理论 朴素贝叶斯是一种基于贝叶斯定理和特征条件独立性假设的多分类的机器学习方法,所...
    wlj1107阅读 3,088评论 0 5
  • “近朱者赤,近墨者黑” 简介 k近邻法(k-nearest neighbor,k-NN)是一种基本 分类 与 回归...
    sumpig阅读 474评论 0 0
  • Kd-Tree,即K-dimensional tree,是一种高维索引树形数据结构,常用于在大规模的高维数据空间进...
    婉妃阅读 5,995评论 2 4