首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

局部敏感哈希(Locality-Sensitive Hashing, LSH)

局部敏感哈希示意图(from: Piotr Indyk) LSH的基本思想是:将原始数据空间中的两个相邻数据点通过相同的映射或投影变换(projection)后,这两个数据点在新的数据空间中仍然相邻的概率很大,而不相邻的数据点被映射到同一个桶的概率很小。也就是说,如果我们对原始数据进行一些hash映射后,我们希望原先相邻的两个数据能够被hash到相同的桶内,具有相同的桶号。对原始数据集合中所有的数据都进行hash映射后,我们就得到了一个hash table,这些原始数据集被分散到了hash table的桶内,每个桶会落入一些原始数据,属于同一个桶内的数据就有很大可能是相邻的,当然也存在不相邻的数据被hash到了同一个桶内。因此,如果我们能够找到这样一些hash functions,使得经过它们的哈希映射变换后,原始空间中相邻的数据落入相同的桶内的话,那么我们在该数据集合中进行近邻查找就变得容易了,我们只需要将查询数据进行哈希映射得到其桶号,然后取出该桶号对应桶内的所有数据,再进行线性匹配即可查找到与查询数据相邻的数据。换句话说,我们通过hash function映射变换操作,将原始数据集合分成了多个子集合,而每个子集合中的数据间是相邻的且该子集合中的元素个数较小,因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题,显然计算量下降了很多。 那具有怎样特点的hash functions才能够使得原本相邻的两个数据点经过hash变换后会落入相同的桶内?这些hash function需要满足以下两个条件: 1)如果d(x,y) ≤ d1, 则h(x) = h(y)的概率至少为p1; 2)如果d(x,y) ≥ d2, 则h(x) = h(y)的概率至多为p2; 其中d(x,y)表示x和y之间的距离,d1 < d2, h(x)和h(y)分别表示对x和y进行hash变换。 满足以上两个条件的hash functions称为(d1,d2,p1,p2)-sensitive。而通过一个或多个(d1,d2,p1,p2)-sensitive的hash function对原始数据集合进行hashing生成一个或多个hash table的过程称为Locality-sensitive Hashing。 使用LSH进行对海量数据建立索引(Hash table)并通过索引来进行近似最近邻查找的过程如下: 1. 离线建立索引 (1)选取满足(d1,d2,p1,p2)-sensitive的LSH hash functions; (2)根据对查找结果的准确率(即相邻的数据被查找到的概率)确定hash table的个数L,每个table内的hash functions的个数K,以及跟LSH hash function自身有关的参数; (3)将所有数据经过LSH hash function哈希到相应的桶内,构成了一个或多个hash table; 2. 在线查找 (1)将查询数据经过LSH hash function哈希得到相应的桶号; (2)将桶号中对应的数据取出;(为了保证查找速度,通常只需要取出前2L个数据即可); (3)计算查询数据与这2L个数据之间的相似度或距离,返回最近邻的数据; LSH在线查找时间由两个部分组成: (1)通过LSH hash functions计算hash值(桶号)的时间;(2)将查询数据与桶内的数据进行比较计算的时间。因此,LSH的查找时间至少是一个sublinear时间。为什么是“至少”?因为我们可以通过对桶内的属于建立索引来加快匹配速度,这时第(2)部分的耗时就从O(N)变成了O(logN)或O(1)(取决于采用的索引方法)。 LSH为我们提供了一种在海量的高维数据集中查找与查询数据点(query data point)近似最相邻的某个或某些数据点。需要注意的是,LSH并不能保证一定能够查找到与query data point最相邻的数据,而是减少需要匹配的数据点个数的同时保证查找到最近邻的数据点的概率很大。 二、LSH的应用 LSH的应用场景很多,凡是需要进行大量数据之间的相似度(或距离)计算的地方都可以使用LSH来加快查找匹配速度,下面列举一些应用: (1)查找网络上的重复网页 互联网上由于各式各样的原因(例如转载、抄袭等)会存在很多重复的网页,因此为了提高搜索引擎的检索质量或避免重复建立索引,需要查找出重复的网页,以便进行一些处理。其大致的过程如下:将互联网的文档用一个集合或词袋向量来表征,然后通过一些hash运算来判断两篇文档之间的相似度,常用的有minhash+LSH、simhash。 (2)查找相似新闻网页或文章 与查找重复网页类似,可以通过hash的方法来判断两篇新闻网页或文章是否相

03

EmguCV 常用函数功能说明「建议收藏」

大家好,又见面了,我是你们的朋友全栈君。AbsDiff,计算两个数组之间的绝对差。 dst(I)c = abs(src1(I)c-src2(I)c)。所有数组必须具有相同的数据类型和相同的大小(或ROI大小)。 累加,将整个图像或其所选区域添加到累加器和。 累积产品,将2张图像或其选定区域的产品添加到累加器中。 AccumulateSquare,将输入src或其选定的区域,增加到功率2,添加到累加器sqsum。 累积权重,计算输入src和累加器的加权和,以使acc成为帧序列的运行平均值:acc(x,y)=(1-alpha)* acc(x,y)+ alpha * image(x,y )如果mask(x,y)!= 0,其中alpha调节更新速度(累加器对于先前帧的多少速度).. 自适应阈值,将灰度图像转换为二进制图像。每个像素单独计算的阈值。对于方法CV_ADAPTIVE_THRESH_MEAN_C,它是blockSize x blockSize像素邻域的平均值,由param1减去。对于方法CV_ADAPTIVE_THRESH_GAUSSIAN_C,它是blockSize x blockSize像素邻域的加权和(高斯),由param1减去。 添加,将一个数组添加到另一个数组:dst(I)= src1(I)+ src2(I)if mask(I)!= 0所有数组必须具有相同的类型,除了掩码和大小(或ROI)尺寸)。 AddWeighted,计算的两个数组的加权和如下:dst(I)= src1(I)* alpha + src2(I)* beta + gamma所有的数组必须具有相同的类型和相同的大小(或ROI大小)。 ApplyColorMap,将颜色映射应用于图像。 ApproxPolyDP,近似具有指定精度的多边形曲线。 ArcLength,计算轮廓周长或曲线长度。 ArrowedLine,绘制从第一个点指向第二个点的箭头段。 BilateralFilter,将双边滤镜应用于图像。 BitwiseAnd,并计算两个数组的每元素的逐位逻辑连接:dst(I)= src1(I)&src2(I)if mask(I)!= 0在浮点数组的情况下,使用它们的位表示为了操作。所有阵列必须具有相同的类型,除了掩码和大小相同。 BitwiseNot,反转每个数组元素的每一位:。 BitwiseOr,计算两个数组的每元素逐位分离:dst(I)= src1(I)| src2(I)在浮点数组的情况下,它们的位表示用于操作。所有阵列必须具有相同的类型,除了掩码和大小相同。 BitwiseXor,计算两个数组的每元素的逐位逻辑连接:dst(I)= src1(I)^ src2(I)if mask(I)!= 0在浮点数组的情况下,使用它们的位表示为了操作。所有阵列必须具有相同的类型,除了掩码和大小相同。 模糊,使用归一化的盒式过滤器模糊图像。 BoundingRectangle,返回2d点集的右上角矩形。 BoxFilter,使用框过滤器模糊图像 BoxPoints(RotatedRect),计算输入2d框的顶点。 BoxPoints(RotatedRect,IOutputArray),计算输入2d框的顶点。 CalcBackProject,计算直方图的反投影。 CalcCovar矩阵,计算一组向量的协方差矩阵。 CalcGlobalOrientation,计算所选区域中的一般运动方向,并返回0到360之间的角度。首先,函数构建方向直方图,并将基本方向作为直方图最大值的坐标。之后,该函数计算相对于基本方向的移位,作为所有方向向量的加权和:运动越近,权重越大。得到的角度是基本方向和偏移的圆和。 CalcHist,计算一组数组的直方图 CalcMotionGradient,计算mhi的导数Dx和Dy,然后计算梯度取向为:方向(x,y)= arctan(Dy(x,y)/ Dx(x,y)),其中Dx(x,y)考虑Dy(x,y)“符号(如cvCartToPolar函数)。填写面罩后,指出方向有效(见delta1和delta2说明).. CalcOpticalFlowFarneback(IInputArray,IInputArray,IInputOutputArray,Double,Int32,Int32,Int32,Int32,Double,OpticalflowFarnebackFlag),使用Gunnar Farneback算法计算密集的光流。 CalcOpticalFlowFarneback(Image <Gray,Byte>,Image <Gray,Byte>,Image <Gray,Single>,Image <Gray,Single>,Double

02

降维

PCA的主要思想是将n维特征映射到k维上,这k维是全新的正交特征也被称为主成分,是在原有n维特征的基础上重新构造出来的k维特征。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴,新的坐标轴的选择与数据本身是密切相关的。其中,第一个新坐标轴选择是原始数据中方差最大的方向,第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的,第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推,可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴,我们发现,大部分方差都包含在前面k个坐标轴中,后面的坐标轴所含的方差几乎为0。于是,我们可以忽略余下的坐标轴,只保留前面k个含有绝大部分方差的坐标轴。事实上,这相当于只保留包含绝大部分方差的维度特征,而忽略包含方差几乎为0的特征维度,实现对数据特征的降维处理。

00

相似文档查找算法之 simHash 简介及其 java 实现

传统的 hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。产生的两个签名,如果相等,说明原始内容在一定概 率 下是相等的;如果不相等,除了说明原始内容不相等外,不再提供任何信息,因为即使原始内容只相差一个字节,所产生的签名也很可能差别极大。从这个意义 上来 说,要设计一个 hash 算法,对相似的内容产生的签名也相近,是更为艰难的任务,因为它的签名值除了提供原始内容是否相等的信息外,还能额外提供不相等的 原始内容的差异程度的信息。 而 Google 的 simhash 算法产生的签名,可以满足上述要求。出人意料,这个算法并不深奥,其思想是非常清澈美妙的。

010

PaperReading-用能力感知神经网络提高人岗匹配效果

抛开这篇论文,我们先谈一谈人岗匹配这件事到底在做什么,做哪些难点。 一家大公司,一旦发布了某招聘需求,往往每天会有成千上万封简历飞来应聘。HR需要从这成千上万封简历中筛选符合要求的、跟岗位匹配的一批简历,进入面试环节。而这个筛选过程是十分痛苦的,一天看上百封简历可能还看得过来,一天看一千封、一万封,你就根本没法应付了。这个时候,我们就希望借助于机器帮我们筛选。所以最初,我们会设定一些规则,让电脑去判断一封简历是否满足了某些要求,比如毕业学校、学历、年龄等等这些硬性要求。但是,对简历的要求远远不止这些,还有对技能(软技能、硬技能)的要求,对工作经历项目经历的要求,这些很难通过人工设定规则来判断。另外,语言的表达形式多种多样,你定义了一个要求,简历实际上也满足这个要求,但是表达方式、用词用语不一样怎么办?而且,不光是筛选掉不合格的简历,合格的简历也不是全部都要,这个数量依然太大了,我们还需要优中选优,对所有合格的简历进行一个匹配度的排序,最终可以选出前N个最符合要求的简历来。

01
领券