川制作官方网站,小程序下载,介绍网络营销,网页设计与制作方法目录
场景在搜索引擎和推荐引擎中#xff0c;对相似文章去重是一个非常重要的环节#xff0c;另外是拍照识花、摇一摇搜歌等场景都可以使用它快速检索。
基于敏感性哈希的检索更擅长处理字面上的相似而不是语义上的相似。
向量空间模型ANN检索加速思路 局部敏感哈希编码 随…目录
场景在搜索引擎和推荐引擎中对相似文章去重是一个非常重要的环节另外是拍照识花、摇一摇搜歌等场景都可以使用它快速检索。
基于敏感性哈希的检索更擅长处理字面上的相似而不是语义上的相似。
向量空间模型ANN检索加速思路 局部敏感哈希编码 随机超平面划分哈希编码思路Google的SimHash编码思路以及抽屉原理 聚类乘积量化
ANN与向量空间模型
对于高纬度数据近邻检索常见方式 将所有文档中的关键词都提取出来如果总共n个关键词那么就是一个n纬度的向量。具体到一篇文章假如文档包含关键词数量是k其中0kn如果文档包含的第k个关键词的权重为w那么权重向量k位置的元素就是w这个权重w一般是根据TF-IDF计算得出如果文档不包含第k个关键词那么权重w就是0。
关于TF-IDF词频-逆文档频率参考往期
ElasticSearch学习篇15_《检索技术核心20讲》进阶篇之TopK检索-CSDN博客
本质就转化为计算两个向量的相似度可用余弦相似度、欧式距离等计算另外n纬向量放入到空间中就是一个点也可理解为空间中的近邻检索ANN在十几维量级的低维空间中我们可以使用 k-d 树进行 k 维空间的近邻检索这种思路就是前面说的精确检索的思路它的性能还是不错的但是纬度上来之后因为基础k-d树特点当纬度大于20的时候可能出现线性灾难搜索大量的邻域导致性能很慢。
关于KD树、KDB、BKD树参考往期
ElasticSearch学习篇10_Lucene数据存储之BKD动态磁盘树论文Bkd-Tree: A Dynamic Scalable kd-Tree_bkd树-CSDN博客
向量空间模型可用来表示文字、图片等内容从而进行文本、图像近邻搜索ANN一些常见的ANN加速算法思想基本分为两类
缩小候选集压缩向量存储空间
ANN搜索加速技术思想
局部敏感哈希-缩小候选集数量
借助非精确检索的思路可以将高纬空间中的点进行区域划分然后给每个区域生成一个较短的编码查询的时候先根据规则定位区域达到缩小候选集的目的再从该区域高效近邻检索。
这个规则就类似哈希但是普通的哈希函数值不太可控文章中变化很少的关键词就会导致哈希值很大的变动。
因此必须找出一个特殊的哈希规则使得相似的数据哈希之后得到的哈希值也是相近的被称为局部敏感性哈希Locality-Sensitive Hashing
随机超平面划分哈希编码
以二维空间举例找出一条线将区域划分为两部分处在区域1的点编码为1处在另外区域的点编码为0这条线需要尽可能合理因此可以随机找出n条线一条线切分下会对点增加一位编码这样n条线就会给一个点产生n位的编码。 对于多维空间就需要找超平面如n个纬度就找n个超平面然后这些超平面将空间中的点切割位于超平面两侧的点通过超平面法向量的余弦相似度计算分别被编码0、1这样可以将高维空间的点映射为一纬的编码。
如果两个点的哈希值是一样的那么两个点大概率距离的非常近即使哈希值不一样只要他们在n个比特位中大大部分是相同的具体的计算算法如海明距离说明他们大概率相近。举个例子如果两篇文章内容是100%相同的那么他们的哈希值就是相同的也就相当于编码相同。
这种一般哈希编码有个缺点就是随着超线、超平面的划分编码会丢失某些纬度权重信息。
SimHash编码
谷歌提出的局部敏感哈希策略简化哈希函数保留多维数据点项的权重信息。
它使用一个普通的哈希函数代替了n次随机超平面划分这个哈希函数作用对象不是整体所有的高纬度数据项而是一个个处理高纬度数据项通过数据项哈希值编码与数据项权重计算的时候就能保留权重。 构造SimHash的具体过程以一篇文档进行局部敏感哈希编码来说明
文档分词关键词项带权重分词并计算每个关键词的权重w。生成Hash值使用一般的Hash函数针对每个关键词生成如64位的0、1哈希值编码。每个关键词哈希值变化将哈希值的0改为-1如10110 - 1 -1 1 1 -1每个关键词哈希值按位乘上词权重如词权重3变为 3 -3 3 3 -3。按位相加所有关键词的哈希值计算文档所有关键词哈希值按位加的结果。文档哈希值编码转换将编码转为0、1。
这样文档的最终哈希编码是收到权重比较大的词影响比较多的另外就是哈希函数比较简单代替了复杂的随机选取超平面方式。
抽屉原理
对于文章查重领域如果两个文章的SimHash编码的距离使用汉明距离计算小于k那么就认为它们是相似的。举个例子当k3的时候需要找出k小于3的文章然后遍历逐一计算对比效率比较低有没有加速方案
一个直观的想法使用SimHash编码某一位bit作为key使用文章内容作为value构建倒排索引以64位的SimHash编码为例key的数量为128个构造的倒排索引key如
1xxxxx、0xxxxxx1xxxx、x0xxxx…
查找的时候逐位查找64次将第n为比特位对应key对应的文章全部取出来然后计算对比。
这种方式效率不是很高因为即使两篇文章64位bit任意两个位置的bit相同的话就会被召回即使不太相似。
Google提出优化的抽屉原理将文章的SimHash编码分4段如果想找出和此文章bit位差异不超过3个的文章那么4个段其中一定至少有一个段的bit是完全一致的。因此查询就被转化为了4段中有一段完全相同的文章会被召回。 按照这个思路
分段构建倒排索引将每个文档的SimHash编码划分为四段每段的16位bit作为一个倒排索引分段查询查询的时候当前文档的SimHash编码也会被划分为四段如果找出汉明距离k3的文档只需召回四段中任一段完全相同的文档即可然后从四段倒排索引找回的结果合并。 通过使用 SimHash 函数和分段检索抽屉原理使得 Google 能在百亿级别的网页中快速完成过滤相似网页的功能从而保证搜索结果的数量。
思考1对于 SimHash如果将海明距离在 4 之内的文章都定义为相似的那我们应该将哈希值分为几段进行索引和查询呢分为5段因为4为不同的bit位最多能影响四段虽然除不尽每段可以是12或者13查询的时候也按照这种规则划分5段即可。
对比编辑距离、杰卡德算法计算文本相似性
对比杰卡德、莱文斯坦、SimHash三种计算文章相似度的效果总结特点以及适用场景。
SimHash的一种实现参考SimHash结合汉明距离判断文本相似性
下面选取一套初中语文的试卷试卷包含大概20道试题大概1w字符
手动创造不同的CASE以下是包含完整CASE描述的表格
CASE描述原文内容长度内容长度simHash相似度simHash耗时levenshtein相似度levenshtein耗时jaccard相似度jaccard耗时CASE1将21题和22题互相换位置85568556100.0274ms0.84298ms1.07msCASE2删除试卷中间的11题8556840196.88102ms0.98274ms1.01msCASE3删除10题之后的所有内容8556192165.6330ms0.2241ms1.02msCASE4完全打乱试题顺序85568560100.045ms0.45183ms1.01msCASE5删除11题之前的所有内容8556663592.1940ms0.77143ms1.01msCASE6前11道题内容不相同后面内容相同8556918489.0640ms0.74194ms0.90359712230215831msCASE7在11题后面中间加入一道试题8556874198.4437ms0.97186ms1.01ms
绘制成图表 在选取初中语文试卷内容1w字符文本相似度计算场景下综合CASE分析文本相似度计算效率以及严格程度
效率杰卡德 SimHash 莱文斯坦编辑距离严格程度莱文斯坦编辑距离 SimHash 杰卡德
针对CASE2、CASE3分析即使试卷内容1和试卷内容2相差了一道或者十多道试题但是杰卡德计算的文本相似度仍为100SimHash计算的文本相似度较为准确但是效率又要比莱文斯坦效率要高使用SimHash可以避免查重中将不是完全一致的试卷内容差别几道试题误查同时又兼顾相似度计算效率。
SimHash、杰卡德Jaccard和莱文斯坦Levenshtein是三种常用的文本相似度计算算法它们各有特点和适用场景
SimHash局部敏感性哈希 特点SimHash是一种局部敏感哈希算法主要用于快速计算大规模文本数据的相似性。它通过将文本转换为一个固定长度的二进制哈希值来表示文本特征。SimHash的优点是计算速度快适合处理大规模数据。适用场景SimHash常用于海量数据的去重、近似重复检测和相似文档查找等场景。由于其计算效率高特别适合需要快速处理和比较大量文本的应用。 杰卡德Jaccard相似系数 特点杰卡德相似系数用于衡量两个集合的相似度定义为两个集合交集的大小除以并集的大小。对于文本相似性通常将文本分割成词或字符的集合然后计算这些集合的杰卡德相似度。适用场景杰卡德相似度适合用于比较短文本或关键词集合的相似性如文档分类、标签推荐等。由于其计算简单适合用于需要快速评估文本相似性的场合。 莱文斯坦Levenshtein距离 特点莱文斯坦距离又称编辑距离表示将一个字符串转换为另一个字符串所需的最小编辑操作次数插入、删除、替换。它能够精确地衡量两个字符串之间的差异。适用场景莱文斯坦距离适合用于需要精确比较字符串差异的场合如拼写检查、DNA序列比对、文本纠错等。由于其计算复杂度较高通常用于较短文本的比较。
总结来说SimHash适合大规模文本的快速相似性检测杰卡德相似度适合集合间的相似性比较而莱文斯坦距离适合精确的字符串差异分析。选择合适的算法需要根据具体的应用场景和数据特征来决定。
汉明距离
主要是计算等长的两个二进制字符串之间差别的位数
def hamming_distance(str1, str2):if len(str1) ! len(str2):raise ValueError(Strings must be of the same length)distance 0for ch1, ch2 in zip(str1, str2):if ch1 ! ch2:distance 1return distance# 示例
str1 1101
str2 1001
print(hamming_distance(str1, str2)) # 输出: 1
聚类-缩小候选集数量
图片如何相似性检索检索图片和检索文章一样首先要先用向量空间模型将图片表示出来这样图像就变成了高纬度空间的一个点搜素图片转化为了高纬度空间的ANN。
如何从图片抽取向量空间模型如果把图像的每个像素看作一个纬度像素上的RGB值作为纬度值是一种思路但是一张图片的纬度大概是百万级别检索起来很复杂因此另外一种方式就是使用CNN等进行图像特征提取转为一个512或者1024纬度的向量空间模型。
如何加速ANN检索效率有了向量空间模型就可以使用ANN加速技术比如SimHash来加速检索比如将高纬空间的点划分到有限区域从而达到缩小候选集的目的。但是SimHash哈希函数比较简单更适合计算字面上的相似性而不是语义上的相似性同时SimHash是一种粒度很粗的非精确检索方案他能将上百万的纬度压缩为64位bit损失不少精度。因此一般使用聚类方案加速ANN检索常见的一种是K-MeansK-平均算法方案 K-Means聚类算法构建聚类计算步骤
初始聚类中心随机从数据中选取k个数据作为初始聚类中心计算距离计算其他数据与ki 的距离加入到最邻近的ki 聚类中根据距离均值重新选取聚类中心根据聚类中的点到聚类中心距离的均值重新选一个聚类中心
重复2-3步即重新计算其他还数据到聚类中心的距离然后将节点划分到最近的聚类中然后在更新聚类中心。
K-Means 聚类算法的优化目标是类内的点到类中心的距离均值总和最短。构建好之后以聚类中心数据ID作为key单个聚类的数据创建倒排索引。
K-Means查询的时候直接找出待查询数据距离最近的聚类中心ki 然后从倒排索引取出topK候选集
如果不足topK数量那么可以再查询邻近聚类的候选集。如果数量很多同时topK又取得非常大那么一个一个计算和待查询数据距离代价也很大可以采用层级子聚类来继续缩小候选集。
乘积量化-压缩向量模型存储空间
对于向量的相似检索除了检索算法本身优化向量存储空间也是一个优化方向因为向量的相似度计算需要加载进内存。
以一个1024纬度的向量距离每个向量纬度是一个浮点数占4 Bytes 32 bits那么一个向量占用1KB空间如果是上亿级的数据存储向量需要占几百个G。100 000 000 KB 100 GB
为了更好的将向量加载进去内存需要对向量存储空间优化一种思路是使用上面的聚类思想减少加载进内存的数量只把查询向量和聚类向量加载进内存而不是聚类下所有向量这样可能会损失结果粒度。另外一种思路就是使用向量量化-乘积量化来压缩。
乘积量化的概念
乘积高纬空间向量可以看作是多个低纬空间向量相乘的结果可以理解为笛卡尔集如数轴的x、y轴分别表示一纬空间数轴区域中的点(xi.yi)就是二维空间的点假如xi的值为1、2、3yi的值为5、6、7那么组合笛卡尔集的二纬空间的点个数为9个。量化将区域划分为子区域然后在编码这样就能将区域转为1纬编码上面聚类就是一种量化方式。
乘积量化就是将高纬空间划分为多个子空间然后对子空间编码针对子空间在进行聚类技术分为多个子区域然后给每个子区域编码即聚类ID。好处省空间二纬空间存储的点数量为9但是只存储一纬空间x、y的话只需要存储的数量为6个一纬点。
举例假设一组1024纬度的向量进行乘积量化
首先将1024纬度向量拆分为4个256纬度子向量在每一个256纬度子向量进行聚类找出1-256和聚类ID因此只使用8 bits就能表示1-256的聚类ID。 所以经过上述过程1024纬度的向量使用 4 * 8 bits 32 bit就能表示。 乘积量化PQ过程思想
乘积量化向量相似查询的时候涉及到三个向量
样本向量1024纬度乘积量化过程会被压缩为4段每段进行聚类每段会得到一个聚类中心ID范围为1-256最后所有样本处理完后大概会得到 256 * 4 个聚类中心向量。聚类中心向量每段都有256个聚类中心ID256 * 4 个聚类中心向量。查询向量1024纬度查询过程会被压缩4段。
构造的时候样本向量会被压缩为4段会得到256 * 4的聚类中心向量而样本向量也从1024纬度被压缩为32纬1024 4 * 256 4 * 2 ^ 8压缩含义就是以每段聚类中心ID的8为bit编码代替当前子向量段。
当计算查询向量和样本向量的距离时
向量切分子空间我们将查询向量和样本向量都分为 4 段子空间。子空间计算聚类ID计算查询向量切分的4段子空间的聚类ID生成压缩向量。然后预生成一个距离表该距离表纬度是256 * 4记录了查询子向量和 子空间各个中心向量的距离。遍历全部样本数量计算查询向量距离根据预处理阶段的距离表可以查询出查询向量每段到各个聚类ID的距离数据库中全部的样本向量属于哪个聚类ID也可以计算出然后就是求出每段距离d1、d2、d3、d4最终通过相关运算如欧式距离等计算两个向量的距离进而返回topK。
PQ主要是为了压缩空间计算距离算法不太关注。
其他参考理解 product quantization 算法
这样求查询子向量和样本子向量的距离就转换为求查询子向量和对应的聚类中心向量的距离。那我们只需要将样本子向量所属的聚类中心的聚类 ID 作为 key 去查距离表就能在 O(1) 的时间代价内知道这个距离了。 这里讲述的只是大致思想具体的如何计算找出紧邻的topK向量还有 基于倒排的乘积量化IVFPQ缩小遍历全部样本空间向量以及SDC、ADC向量相似检索算法还有很多小细节。
基于倒排索引的IVFPQ思想
上面说的计算查询向量和所有样本向量之间的距离是遍历全部的样本空间还有一种维护样本向量倒排索引的方式加速检索。
构建倒排索引的具体的思路
样本向量切分子空间1024纬切分为4段每段256纬度计算子空间聚类ID可以采用KMeans聚类算法最终每个子空间段聚类256个每个子空间使用聚类ID代表当前样本子空间特征最终每个子空间得到8位的聚类ID建立倒排索引得到的32位新向量为每个子空间创建一个倒排索引每个倒排索引的key可以设置为当前段的聚类IDvalue设置为在当前段被聚类到该ID的所有样本数量。
查询的时候查询向量进行切分子空间PQ然后逐段查倒排这样将四个段的样本数量就是最有可能相近的样本数量在进行距离计算找出TopK。
另外还有一种根据聚类ID向量残差创建倒排索引的做法这样做精度会高一些。
思考
如果二维空间中有 16 个点它们是由 x 轴的 1、2、3、4 四个点以及 y 轴的 1、2、3、4 四个点两两相乘组合成的。那么对于二维空间中的这 16 个样本点如果使用乘积量化的思路你会怎么进行压缩存储当我们新增了一个点 (17,17) 时它的查询过程又是怎么样的
主要的思想就是使用两纬位置代替真实的二维点值对于16个样本点首先是定义x、y轴两个集合然后将点的x、y轴的值压缩为对应x、y轴集合的索引值索引值数值相对于点的值是比较小的通过PQ可以节省存储空间。当新增了一个点(1717只需要向x、y轴集合添加17查询的时候先判断x、y轴集合是否有值17若都有的话索引为xi5,yi5索引对应的点就是要找的1717
