`

海量文档查同或聚类问题 -- Locality Sensitive Hash 算法(转)

 
阅读更多

原文链接:http://blog.csdn.net/fxjtoday/article/details/6200257

考虑一下这个场景 使用网络爬虫高速爬取大量的网页内容 如果想把这些网页进行实时聚类 并从中提取每个网页聚类的主题 我们应该怎么样去做

对于普通或常见的聚类算法 比如 K-means,  Hierarchical 聚类 无法适用于这个常见 对于这些聚类算法无法进行 incremental 聚类 即在聚类开始前必须知道整个数据集 而这个场景中的数据集是随着爬虫不断增多的 而且这些聚类算法的 performance 不够高 比如对于 K-means 需要不断的partition 以达到比较好的聚类效果 所以向来聚类算法在我的印象中是低效的 而面对这样一个需要实时数据递增处理的场景 我们需要一种 one-shot 的高效算法 接收到网页内容 迅速判断其类别 ,而不用后面不断地 revisit  recluster.

首先介绍下面这个聚类方法 
Leader-Follower Clustering (LFC) 
The algorithm can be described as follows:
If distance between input and the nearest cluster above threshold, then create new cluster for the input.
Or else, add input to the cluster and update cluster center. 
其实这个聚类方法再简单不过了 我是先想到这个方法 然后才发现这个方法有这么个看上去蛮牛比的名字 
有了这个方法 当新网页来的时候 和所有老的网页形成的聚类算下相似度 相似就归到这类 不相似就创建新类

这个过程当中有个经典问题 KNN 问题 (K-Nearest Neighbor) 
 对海量数据 而且是高维数据 对于文本 feature 一般是选取文本中的 keywords, 文本中的keywords 一般是很多的 ), KNN 问题很难达到线性 search  即一般是比较低效的 这样也没办法达到我们的要求 我们需要新的方法来解决这个 KNN 问题

当然该牛人出场了 他提出了一种算法 
Locality Sensitive Hash(LSH) 
这个算法的效果是 你可以把高维向量 hash 成一串 n-bit 的数字 当两个向量 cosin 夹角越小的时候即他们越相似 ), 那么他们 hash 成的这两串数字就越相近 
比较常用的 LSH 算法是下面这个 
Charikar's simhash 
Moses S. Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC ’02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380–388, New York, NY, USA. ACM.

 LSH 算法怎么样来解决高维数据的 KNN 问题了 我们可以参考 Google  WWW2007 发表的一篇论文 “Detecting near-duplicates for web crawling”, 这篇文章中是要找到 duplicate 的网页 和我们的问题其实是同一个问题 都是怎样使用 LSH 解决 KNN 问题

分两步 
第一步 象我们上面说的那样 将文档这样的高维数据通过 Charikar's simhash 算法转化为一串比特位 对于 Google 的问题 
We experimentally validate that for a repository of 8 billion webpages, 64-bit simhash fingerprints and k = 3 are reasonable. 
就是对于 80 亿的文档 我们把每个文档转化为 64-bit  simhash fingerprints, 当两个 fingerprints k = 3 位不同时 我们就认为这两个文档不相同 .

Charikar's simhash is a dimensionality reduction technique . It maps high-dimensional vectors to small-sized fingerprints. 
其实 LSH 算法的基本原理就是 把一个多维空间上的点投影到一个平面上 当多维空间中的两个点在平面上的投影之间距离很近的时候 我们可以认为这两个在多维空间中的点之间的实际距离也很近 但是 你想象一下 你把一个三维球体中的两个点投影到一个随机平面上 当投影很靠近的时候其实那两个点不一定很靠近 也有可能离的很远 所以这儿可以把两个点投影到多个随机平面上 ,如果在多个随机平面上的投影都很靠近的话 我们就可以说这两个多维空间点之间实际距离很近的概率很大 这样就可以达到降维 大大的减少了计算量 .

算法过程如下 其实挺好理解的 
Computation: 
Given a set of features extracted from a document and their corresponding weights, we use simhash to generate an f-bit fingerprint as follows. 
We maintain an f-dimensional vector V, each of whose dimensions is initialized to zero. 
A feature is hashed into an f-bit hash value. 
These f bits (unique to the feature) increment/decrement the f components of the vector by the weight of that feature as follows: 
ü   if the i-th bit of the hash value is 1, the i-th component of V is incremented by the weight of that feature; 
ü   if the i-th bit of the hash value is 0, the i-th component of V is decremented by the weight of that feature. 
When all features have been processed, some components of V are positive while others are negative. The signs of components determine the corresponding bits of the final fingerprint. 
For our system, we used the original C++ implementation of simhash, done by Moses Charikar himself.

第二步 HAMMING DISTANCE PROBLEM

第一步把所有文档都变成 64-bit  fingerprints, 那么面对几十亿的 fingerprints, 怎么样能快速找到和目标 fingerprint 相差 位的所有 fingerprint  
其实这就是个对于 hamming distance  KNN 问题 
Definition: Given a collection of f-bit fingerprints and a query fingerprint F, identify whether an existing fingerprint differs from F in at most k bits.

汉明距离 (hamming distance) 
在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数 
可见 对于 hamming 距离 不是简单的通过排序索引就可以解决的

说两个简单的方法 虽然不可行 但也是一种思路 
耗费时间的方法 
Build a sorted table of all existing fingerprints 
对于给定的 F, 找出所有 Hamming distance from F is at most k  fingerprint 然后去 table 里面搜索 ,看有没有 
For 64-bit _ngerprints and k = 3, we need C64 3 = 41664 probes. 
这样查找时间太长了 .

耗费空间的方法 
还有个办法就是空间换时间 对现有的每个 fingerprints, 先事先算出所有和它 Hamming distance 小于 的情况 但这种方法预先计算量也太大了 如果现有  fingerprint, 就需要算 41664*n. 
可见用传统的方法是很难高效的解决这个问题的 .

那么怎么办 有什么办法能够在海量的 F bit 的向量中 迅速找到和查询向量 F ′ 只差 k bit 的向量集合了 
We now develop a practical algorithm that lies in between the two approaches outlined above: it is possible to solve the problem with a small number of probes and by duplicating the table of fingerprints by a small factor. 
我们需要一种介于上面两种比较极端的情况的方法 耗些时间 也耗些空间 但都不要太多 ......

设想一下对于 F bit, 可以表示 2F 个数值 如果这儿我们完全随机产生 2d  F bit 的数  d<<F  ,这些随机数值的高 位重复的应该不多 为什么 这些数值是完全随机产生的 所以应该相对均匀的分布在 2F 大小的空间里 如果完全平均生成 2d 个数 那么每个数的高 位都是不同 但是这儿是随机产生 所以会有些数的高 位是相同的 不过数量不会多 所以这边就可以把高 位作为计数器 ,或索引 这个假设是这个方法的核心 有了这个假设 不难想到下面怎么做 ...

首先对现有的所有 fingerprints 进行排序 生成有序的 fingerprints  
选择一个 d ′, 使得 |d ′-d| 的值很小 就是说你选择的这个 d’  只要差的不多 都可以 ), 因为表是有序的 一次检测就能够找出所有和 F ′ 在最高的 d ′ 位相同的指纹 因为 |d ′-d| 的值很小 所有符合要求的指纹数目也比较小 对于其中的每一个符合要求的指纹 我们可以轻易的判断出它是否和 F最多有 位不同 这些不同很自然的限定在低 f-d ′  

上面介绍的方法帮我们定位和  位不同的指纹 不过不同的位被限定在低 f-d ′ 位中。这对大部分情况来说是合适的 但你不能保证没有 位不同出现在高 位的情况 为了覆盖所有的情况 采用的方法就是使用一种排序算法 π, 把当前的 F bit 随机打乱 这样做的目的是使当前的高位 bit, 在打乱后出现在低位 bit, 然后我们再对打乱后的表排序 并把 F ′ 用相同的排序算法 π 打乱 
再重复我们上面的过程 来查找低 f-d ′ 位上 位不同的情况 
这样当我们多使用几种排序算法 π, 重复多次上面的过程 那么漏掉 ’k 位不同出现在高  ’ 的情况的概率就会相当的小 从而达到覆盖到所有情况

还有个问题 这儿的假设是 , 2d 个数是随机产生的 那么我们这儿的 fingerprints 是基于 hash 算法产生的 本身具有很大的随机性 所以是符合这个假设的 这点原文 4.2 Distribution of Fingerprints 有相应的实验数据 .

假设 f=64,k=3, 那么近似网页的指纹最多有 位不同。假设我们有 8B=234 的已有指纹  d=34  
我们可以生成 20 个有序排列表 即使用 20 种不同的排列算法打乱原 fingerprint, 并生成有序表 ), 方法如下 ,  
 64 位分成  分别是 11,11,11,11,10  10 位。共有 C(6,3)=20 种方法从 块中选择 块。对于每种选择 排列 π 使得选出的块中的位成为最高位 . d ′ 的值就是选出的块中的位数的总和。因此d ′=31,32, 或者 33 (  差的不多 ). 平均每次检测返回最多 234~31 个排列后的指纹。实际应该不会很多

你也可以用 16 个表 或更少 但使用的表越少 必须 的取值也越少 这样最后需要验证的fingerprint 就越多 这儿就有个时空的平衡 时间和空间不可兼得 .

说到这儿大家是不是已经被这个复杂的方法给搞晕 , Google 的这个方法是为了在几十亿篇文章中发现相同的文章 相对的精确性要求比较的高 如果为了我们的初衷 进行文本聚类的话 我们不需要用 64-bit 来进行 hash, 也许可以用 16bit, 这个可以通过实验来选择 为了避免复杂的汉明距离问题 ,只当两个文章的 fingerprint 完全一致时才认为他们属于一类 随着用更少的位数来进行 hash, 这个应该是可行的 不过需要具体的实验证明

分享到:
评论

相关推荐

    java笔试题算法-tlsh:特尔什

    java笔试题算法 TLSH - Trend Micro Locality Sensitive Hash TLSH 是一个模糊匹配库。 给定一个最小长度为 50 字节的字节流 TLSH 生成一个哈希值,可用于相似性比较。 相似的对象将具有相似的散列值,这允许通过...

    随机映射(Random Projection)算法

    本文将深入探讨随机映射算法的核心概念、工作原理以及其在不同场景下的应用,同时解析Charikar等人在其论文中提出的基于随机投影的局部敏感哈希(Locality Sensitive Hashing, LSH)方案。 #### 随机映射算法基本...

    面向近似近邻查询的分布式哈希学习方法.pdf

    哈希方法通常包括局部敏感哈希(Locality-Sensitive Hashing, LSH)等经典算法。 3. 分布式存储和计算:随着数据量的指数级增长,单个计算机系统已经无法有效处理如此庞大的数据。分布式系统通过将数据和计算任务...

    CBIR运行文档1

    5. **LSH (Locality Sensitive Hashing)**:一种近似最近邻搜索算法,通过哈希函数将高维数据映射到低维空间,以降低计算复杂度。 6. **SIFT (Scale-Invariant Feature Transform)**:尺度不变特征变换是一种强大的...

    基于Andorid的电子杂志应用系统设计.zip

    基于Andorid的电子杂志应用系统设计实现源码,主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。

    《网络传播技术与实务》第10章-握在手中的网络——移动通信与无线网络技术.ppt

    《网络传播技术与实务》第10章-握在手中的网络——移动通信与无线网络技术.ppt

    基于COMSOL的电磁传感器用于螺孔缺陷检测的建模与仿真

    内容概要:本文详细介绍了如何利用COMSOL Multiphysics进行螺孔缺陷检测的电磁传感器建模与仿真。首先,通过参数化建模创建带有螺纹孔的金属块,并在螺纹根部引入微小V型槽作为缺陷。接着,设置了材料属性,特别是针对缺陷区域的非线性磁导率变化进行了细致调整。然后,配置了物理场环境,包括激活AC/DC模块的电流和磁场接口,设定合适的边界条件和激励电流频率范围。网格划分采用了自适应策略,确保缺陷区域的高分辨率。求解器设置为频域稳态求解,并通过后处理展示了缺陷处的电磁场分布特性,如电场强度突变和涡流密度矢量图。此外,还讨论了实际应用中的注意事项和技术细节,如表面粗糙度的影响、频率选择以及结果验证方法。 适合人群:从事无损检测、电磁仿真研究的技术人员,以及有一定COMSOL使用经验的研发人员。 使用场景及目标:适用于工业生产中对螺孔内部微小裂纹的精确检测,旨在提高产品质量和安全性,防止因隐蔽缺陷导致的重大事故发生。 其他说明:文中提供了大量具体的MATLAB和COMSOL命令代码片段,帮助读者快速复现实验步骤并深入理解每个环节的设计意图。同时强调了实际操作中的常见陷阱及其应对措施,使读者能够更好地掌握这一复杂技术的应用要点。

    【ABB机器人】-IRB1600机器人维护信息.pdf

    【ABB机器人】-IRB1600机器人维护信息.pdf

    《计算机网络基础》第2章-数据通信.ppt

    《计算机网络基础》第2章-数据通信.ppt

    rubyinstaller-devkit-3.4.3-1-x64

    ruby-3.4.3-windows-x64安装包

    声子晶体中声表面波的光学特性及其应用研究

    内容概要:本文详细探讨了声子晶体中声表面波的光学特性。声子晶体作为一种人工复合材料,能够对弹性波(即声子)进行独特调控。文中介绍了声子晶体的基础原理,包括其周期性结构产生的带隙效应,以及声表面波与其相互作用时发生的折射、反射等光学类比现象。此外,还讨论了声子晶体在传感器、通信等领域的潜在应用,特别是在构建声表面波滤波器方面的重要意义。文章通过具体的Python和MATLAB代码展示了如何模拟声子晶体的结构和声表面波的传播特性,并解释了带隙形成的物理机制。同时,强调了几何对称性和材料参数对声波调控的影响,提出了优化仿真的方法和技术。 适合人群:从事材料科学、物理学及相关领域的研究人员,尤其是对声子晶体和声表面波感兴趣的学者和技术人员。 使用场景及目标:适用于希望深入了解声子晶体声表面波光学特性的科研工作者,旨在帮助他们掌握相关理论知识和数值模拟技能,从而应用于新型声学器件的设计和开发。 其他说明:文章提供了多个实例和代码片段,便于读者理解和实践。同时,指出了实验中常见的挑战和解决方案,如材料损耗建模、缺陷引入等,有助于提高仿真的准确性。

    机械工程电梯柔性提升系统横向-纵向耦合动力学建模与仿真:基于Galerkin法的振动控制分析及工程应用(含详细代码及解释)

    内容概要:本文详细介绍了电梯柔性提升系统横向-纵向耦合动力学建模与仿真的全过程。首先,基于能量法和Hamilton原理,建立了考虑平衡绳影响的横向-纵向耦合振动控制方程,并使用Galerkin法将其离散化为常微分方程。随后,通过Python代码实现并仿真了高速电梯参数下的振动响应,分析了平衡绳和导轨不平顺对系统振动的具体影响。研究结果显示,平衡绳能有效抑制横向振动(上行降低20%,下行降低5%),但对纵向振动有一定影响;而导轨不平顺会导致横向振动突变,对纵向振动影响较小。最终,通过数值仿真验证了论文中的主要结论,为电梯振动控制提供了理论依据和工程建议。 适合人群:具备一定力学和编程基础,对机械振动、电梯工程感兴趣的科研人员和工程师。 使用场景及目标:①理解电梯柔性提升系统的振动特性及其影响因素;②掌握基于能量法和Hamilton原理建立复杂系统动力学模型的方法;③学习如何使用Galerkin法离散化偏微分方程并进行数值仿真;④为电梯系统的设计优化提供参考,特别是平衡绳和导轨安装精度的控制。 其他说明:本文不仅提供了理论分析,还通过详细的Python代码展示了完整的仿真流程,便于读者动手实践。研究结果强调了平衡绳和导轨不平顺对电梯振动的重要影响,提出了具体的设计建议,如安装平衡绳以抑制横向振动、严格控制导轨安装精度等。此外,文中还验证了钢丝绳的安全系数,确保仿真条件符合工程实际。

    《网络规划与设计教程》第二章:网络互联技术概述.ppt

    《网络规划与设计教程》第二章:网络互联技术概述

    电力电子领域单相Boost PFC电路的双闭环控制仿真模型及其实现方法

    内容概要:本文详细介绍了单相Boost功率因数校正(PFC)电路及其双闭环控制仿真模型的设计与实现。首先阐述了单相PFC电路的基础概念,解释了Boost电路的工作原理,即通过控制开关管的导通与关断来提升输入电压并实现功率因数校正。接着讨论了在网侧220V/50Hz条件下,如何利用电压外环电流内环双闭环控制系统确保输出电压稳定性和高功率因数。文中还提供了基于Python和MATLAB/Simulink的具体代码示例,展示了如何模拟Boost电路的行为以及构建双闭环控制策略。此外,针对可能出现的问题如启动时电压超调、电流波形畸变等提出了相应的解决方案和技术细节。 适合人群:从事电力电子系统设计的研究人员、工程师和技术爱好者,尤其是那些希望深入了解PFC技术和掌握相关仿真技能的人群。 使用场景及目标:适用于需要优化电力电子设备性能的应用场合,例如工业自动化、家用电器等领域。通过学习本文的内容,读者可以更好地理解和应用单相Boost PFC电路及其双闭环控制机制,从而提高产品的效率和可靠性。 其他说明:文中不仅包含了理论性的介绍,还有大量的实战经验和技巧分享,帮助读者更快地掌握这一复杂的技术领域。同时强调了在实际工程实践中应注意的关键点,如参数选择、波形调试等方面的知识。

    黑马程序员ThreeJS 3D车展效果展示(含素材源码)

    源文件

    《计算机程序设计(C语言)》第7章-第6节-变量的存储类别.ppt

    《计算机程序设计(C语言)》第7章-第6节-变量的存储类别.ppt

    《计算机程序设计(C语言)》第4章-第2节-if语句.ppt

    《计算机程序设计(C语言)》第4章-第2节-if语句.ppt

    FPGA领域Verilog实现串口通信:兼容Xilinx与Altera的收发模块设计与应用

    内容概要:本文详细介绍了基于FPGA的串口通信模块的设计与实现,涵盖波特率生成、发送模块的状态机设计以及接收模块的抗干扰措施。特别针对Xilinx和Altera两种主流FPGA平台进行了优化,确保代码可以在不同平台上无缝运行。文中不仅提供了完整的Verilog代码片段,还分享了许多实用的调试技巧,如波特率分频系数的精确计算、采样点的选择、跨平台复位信号的处理等。此外,作者还强调了硬件连接和约束文件配置的重要性,为初学者提供了一套完整的解决方案。 适合人群:对FPGA有一定了解,希望深入掌握串口通信机制的工程师和技术爱好者。 使用场景及目标:适用于需要在FPGA平台上实现可靠串口通信的应用场合,如嵌入式系统开发、工业自动化控制等领域。通过本教程的学习,读者能够独立完成串口通信模块的设计与调试,掌握关键技术和常见问题的解决方法。 其他说明:文章附带了经过验证的实际案例和代码,便于读者进行实践操作。同时提醒开发者注意电压匹配等问题,以防止硬件损坏。

    基于FX3U PLC与RS485通信板的多品牌变频器控制方案详解

    内容概要:本文详细介绍了使用FX3U PLC配合FX3U-485BD通信板对西门子V20、台达VFD-M和三菱E700三种变频器进行通信控制的方法。涵盖了硬件配置、接线方法、参数设置、程序编写等方面的内容。文中不仅提供了具体的接线步骤,还针对不同品牌的变频器给出了详细的参数配置指导,并附有简单的梯形图程序示例,帮助读者理解和实施变频器的精确控制。此外,文章还分享了一些实用的经验技巧,如解决通信不稳定等问题的方法。 适合人群:从事工业自动化领域的工程师和技术人员,特别是那些需要集成多个品牌变频器控制系统的人群。 使用场景及目标:适用于需要通过PLC对多种品牌变频器进行集中控制的应用场合,如工厂生产线、自动化设备等。主要目标是提高系统的灵活性和可靠性,减少维护成本,提升生产效率。 其他说明:文中提供的信息和案例有助于读者快速掌握PLC与变频器之间的通信控制技术,同时也强调了实际操作过程中需要注意的一些细节问题,如接线规范、参数匹配等。

    《组态软件控制技术》第7章--报表系统.ppt

    《组态软件控制技术》第7章--报表系统.ppt

Global site tag (gtag.js) - Google Analytics