KD树和LSH局部敏感哈希

文档结构

文档表示

  • 词袋模型:有一些词,比如“的”,“吧”出现的频率很高,但是这些词意义不大。
  • tf-idf:在该文档局部出现的频率高,在全部文档全局出现的频率低。

距离度量

常见的距离度量有:

  • 欧氏距离:d=∑Kk=1(x1k−x2k)2−−−−−−−−−−−−−−√d=\sqrt{\sum_{k=1}^K(x_{1k}-x_{2k})^2}
  • 曼哈顿距离:d=∑Kk=1|x1k−x2k|d=\sum_{k=1}^K|x_{1k}-x_{2k}|
  • 切比雪夫距离:d=maxk|x1k−x2k|d=\max_k |x_{1k}-x_{2k}|
  • 汉明距离:两个等长的字符串将一个变成另外一个所需的最小替换数
  • 余弦相似性:d=1−x1⋅x2|x1||x2|d = 1-\frac{x_1 \cdot x_2 }{|x_1| |x_2|}
  • 内积:d=x1⋅x2d = x_1 \cdot x_2
  • 核函数:d=K(x1,x2)d = K(x_1,x_2)
  • 相关系数:d=Cov(x1,x2)σx1σx2d = \frac{Cov(x_1,x_2)}{\sigma_{x_1}\sigma_{x_2}}

不同的特征分布范围不同,对于变化范围很大的特征计算距离的时候要乘以相对较小的系数,对于变化范围小的特征计算距离的时候要乘以相对较大的系数。否则距离就会被变化范围较大的特征统治。另一种做法是先对源数据做归一化。

一般的欧式距离如下:

d(x,y)=||(x−y)T(x−y)||

d(x,y) =|| (x-y)^T(x-y) ||

考虑权重后的欧式距离如下,AA是对角阵,对角线上的元素代表该特征上的距离乘数:

d(x,y)=||(x−y)TA(x−y)||

d(x,y) =|| (x-y)^TA(x-y) ||

对于余弦相似性,需要注意几点:

  • 不是合适的距离度量,不符合三角不等式(两边之和大于第三边)
  • 计算稀疏向量的内积很有效率

对于是否需要scale向量,需要考虑下面几点:

  • 如果不scale的话,那么对同样的两篇文章,重复其内容会导致相似性变大,这与常理不符合。
  • scale的话,会忽视文章的长度,比如一篇科技论文的相似性和一篇微博的相似性会很高,但是建议阅读科技论文的读者去阅读微博是不大符合常理的。
  • 通常的做法是,cap maximum word counts,也就是设置最大的单词数
  • 以文档为例,对于文档的内容可以scale以忽略文档长度的影响,对于文档的读者数不可以scale因为它是具有切实意义的特征。

KD树

brute-force搜索的KNN复杂度太高,单次1NN的复杂度是O(N)O(N),单次KNN的复杂度是O(NlogK)O(N\log K )。如果N很大,查询次数很多的话,那么效率很低。

原理

KD树通过不断划分样本到不同的子空间,构建二叉树的结构,通过剪枝实现了效率更高的查询,在低维空间表现较好。

构建

  1. 确定split特征(更宽更广的特征;alternating)
  2. 确定split的特征值(median;center point of box)
  3. split数据到两部分
  4. 对分支的数据递归构建KD树直到到达停止条件(min leaf nodes; min box width)

每个node上需要记录以下信息:

  • split的特征
  • split的特征值
  • 该node以下包含的节点区域

查询

  1. 由根节点从上到下找到对应包含查询点的叶节点
  2. 计算该区域内的点到查询点的最小距离
  3. 回溯(backtrack)其他分支,如果该分支区域与到查询点最小距离构成的圆相交,那么进一步深入该区域查询;如果不相交,那么对该分支剪枝继续回溯,直到到达根节点。

复杂度

  • 构建的复杂度:O(NlogN)O(N\log N)
  • 单次查询的复杂度:O(logN)→O(N)O(\log N) \rightarrow O(N),复杂度与维度是指数关系。

KD树的KNN

保留距离的时候,只需要把1NN中的离查询点最小的距离改成离查询点最小的第K个距离即可。

KD树的逼近KNN

实际计算的时候,假设已获得的离查询点最近的距离是rr,那么剪枝的标准由d>rd>r变成d>r/α(α>1)d>r/\alpha(\alpha>1),相当于更容易剪枝。

这样做,虽然可能找不到最近的NN,但是可以保证一旦我们找到的NN距离是rr,那么没有其他点的距离小于r/αr/\alpha。实际中,我们定义的向量表示、距离度量都不一定是百分百地反映其本质的,所以逼近KNN通常可以取得很好的结果,关键更容易剪枝,实现了更高的查询效率。

不适用高维数据

  • 查询的复杂度随维度上升指数增长,通常要求N>>2dN>>2^d。
  • 距离对不相关的特征很敏感,高维空间中每个点都分离很远,最短距离构成的圆和很多点都相交。
  • 需要特征选择,判断哪个特征更优。

LSH

KD树实现检索有以下缺点:

  • 实现起来没那么有效
  • 复杂度随特征维度指数增加,不适合高维情况
  • 高维情况下,一旦发现了最近的点,那么以到最近的点距离为半径的超球体几乎与大多超多面体相交,导致剪枝效率不高。

LSH通过建立hash表,将数据分散到不同的部分,检索的时候只需要检索hash到的那部分的点即可。该方法提供了大概率上发现NN的方法。进一步提高NN概率的方向有两个:在当前hash表内,不仅检索当前的部分还检索周围的部分;建立多个hash表。

如下图所示,根据点在直线上下进行hash,将数据分为两部分,检索的时候只需要检索对应hash后的那部分的数据即可。

LSH潜在的问题

LSH潜在的问题如下:

  • 怎么找到好的直线(好的hash函数)
  • 最坏的情况怎么样
  • hash后的部分可能包含很多点,这样进一步检索的复杂度仍然很大

针对第一个问题,随机划分即可。在随机划分下,针对第二个问题,用一条直线划分,最坏情况的概率是θπ\frac{\theta}{\pi}。θ\theta代表NN点距离样本点的夹角。

针对第三个问题,那我多用几条直线划分,每个bin中的点就小了。

如果想进一步提高精度的话,在计算能力范围内在bin的周围多检索几个bin就可以了。

LSH算法

复杂度

LSH构建hash表的复杂度为:hash表的个数*超平面的个数*数据的维度*训练数据

LSH构建hash表后检索的复杂度为:hash表的个数*表中检索bin的个数*每个bin的数据

概率逼近

多表

如果检测三个bin,有两种方法:

  1. 建立一个表,找到检索点对应的bin后,在其周围找到两个bin。
  2. 建立三个表, 每个表各找一个bin。

一般来说,当hash表中的直线(位数)越多时,第二种方法概率保证上效果更好,缺点是需要计算多个表,计算复杂度比较高。

实际中,我们一般固定bits的位数(一个hash表中划分超平面的个数,然后增大hash表的个数。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张耀琦的专栏

【机器学习入门系列】简介

本文深入浅出地介绍了什么是机器学习以及机器学习所研究的内容与机器学习的三大步骤;并举例深度学习、有监督学习、半监督学习、迁移学习、无监督学习、结构化学习、增强学...

1.2K0
来自专栏专知

网络节点表示学习论文笔记02—CIKM2015GraRep: 基于全局结构信息的图结点表示学习

【导读】这次论文笔记介绍了介绍一种具有代表性的网络节点表示学习(NRL)方法:GraRep。以LINE为代表的一系列NRL算法一些网络上具有很好地学习效果,但它...

4487
来自专栏帮你学MatLab

MATLAB智能算法30个案例分析(3-1)

遗传算法部分 ? clc clear close all %% 加载神经网络的训练样本 测试样本每列一个样本 输入P 输出T %样本数据就是前面问题描述中列...

2688
来自专栏趣学算法

动态规划算法秘籍

动态规划是1957年理查德·贝尔曼在《Dynamic Programming》一书中提出来的,八卦一下,这个人可能有同学不知道,但他的一个算法你可能听说过,他和...

782
来自专栏人工智能

从零学习:详解基于树形结构的ML建模——决策树篇

来源:Analytics Vidhya 编译:Bot 编者按:通常,我们会把基于树形结构的学习算法认为是最好的、最常用的监督学习方法之一。树能使我们的预测模型集...

2149
来自专栏红色石头的机器学习之路

台湾大学林轩田机器学习技法课程学习笔记4 -- Soft-Margin Support Vector Machine

上节课我们主要介绍了Kernel SVM。先将特征转换和计算内积这两个步骤合并起来,简化计算、提高计算速度,再用Dual SVM的求解方法来解决。Kernel ...

1980
来自专栏机器之心

教程 | 基础入门:深度学习矩阵运算的概念和代码实现

选自Medium 机器之心编译 参与:蒋思源 本文从向量的概念与运算扩展到矩阵运算的概念与代码实现,对机器学习或者是深度学习的入门者提供最基础,也是最实用的教...

40413
来自专栏MelonTeam专栏

机器学习入门系列01,Introduction

引用课程:http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML16.html 先看这里,可能由于你正在查看这个平...

1878
来自专栏数据派THU

手把手教你用Python进行回归(附代码、学习资料)

作者: GURCHETAN SINGH 翻译:张逸 校对:丁楠雅 本文共5800字,建议阅读8分钟。 本文从线性回归、多项式回归出发,带你用Python实现样...

3065
来自专栏机器之心

专栏 | 阿里IJCAI 2017 Workshop论文:使用深度强化学习方法求解一类新型三维装箱问题

机器之心专栏 阿里菜鸟物流人工智能部 据机器之心了解,阿里巴巴有 11 篇论文入选如今正在墨尔本进行的 IJCAI 2017 大会,其中 6 篇来自阿里巴巴-浙...

3896

扫码关注云+社区