海量数据相似性度量与聚类： LHS-MinHash

2024-01-20 17:58
文章标签 数据 聚类 海量 度量 相似性 lhs minhash

本文主要是介绍海量数据相似性度量与聚类： LHS-MinHash，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

海量数据相似性度量与聚类： LHS-MinHash

  写本文的原因是近期在涉猎用户画像相关的无监督学习理论，刚好看到一篇运用LHS-MinHash做用户聚类的文章，却讲得过于笼统，对我这样的萌新（菜鸡）不太友好。于是我去搜索了关于LHS-MinHash和simhash的相关博客，有的写得非常不负责，甚至误导了我，有的写的比较详细，但部分细节总感觉有点断片，好像漏掉了什么。同时，这些博客的内容比较相似，原以为是互相借鉴的，后来发现它们都是复述Stanford的大数据课程，又没写清楚。因此我也来总结一篇，只求我自己搞清楚LHS-MinHash的原理和用途。因此，本篇文章的大部分内容将源于Stanford课程（下称课程）Mining of Massive Datasets的第三章，有兴趣的同学可以自行查阅。
  对待社交网络中每天都在更新的千亿级别的无标签数据，传统的聚类方法效率太低了，比方说Kmeans，每个样本都必须与所有候选中心计算相似度，才能进行归类，因此算法的时间复杂度是 O(NK) O ( N K ) ，其中 K K 是聚类数，N是样本数（上千亿），太奢侈了，根本无法实现日均多次滚动，无法上线或产品化。聚类的核心是“发现相似物品”，这与其他的一些问题是异曲同工的，比如社区检测（Community Detection），海量数据查重等等。Stanford课程中举的例子就是海量网页的查重，为了高效地解决这个问题，课程依次提出了“Shingling”和“MinHash”算法，而针对数据量过大的问题，提出了“LSH hashing”，本文也将挑取其中的“MinHash”和“LSH hashing”进行总结。

预备知识：Jaccard 相似度

Jaccard(X,Y)=|X∩Y||X∪Y| J a c c a r d ( X , Y ) = | X ∩ Y | | X ∪ Y |


MinHash

  对于一个网页（或文章），我们可以用Word2vec、用BOW、用k-shingle来表达，这些方法无一例外地占用非常大的空间，使得文章本身的存储就是一个问题，更不要提文章之间的相似度运算了。如果将word看成特征，那么文章就是在一个高维词空间中的向量，对于这样一种数据表达，很容易想到对它进行降维，minhash正是这么一个思路。为了讲清楚minhash，首先要定义一种集合的矩阵表达。
  假设全集为 {a,b,c,d,e} { a , b , c , d , e } ，四个子集分别是 S1={a,d} S 1 = { a , d } ， S2={c} S 2 = { c } ， S3={b,d,e} S 3 = { b , d , e } ， S4={a,c,d} S 4 = { a , c , d } 。则可以定义一个叫“characteristic matrix”的矩阵 C(r,c) C ( r , c ) ，矩阵的列对应一个子集，矩阵的行对应全集里的一个元素，若第 c c 个子集中包含元素r，则 C(r,c)=1 C ( r , c ) = 1 ，否则 C(r,c)=0 C ( r , c ) = 0 ，如下图所示。为了方便理解，可以将characteristic matrix的行看成物品（product），列看成用户（customer），该矩阵的意义即用户的购买历史列表。显然，characteristic matrix是一个极度稀疏的高维矩阵。


Minhashing

  为了方便解释，下面都把子集称为“用户”，把元素称为“商品”好了。所谓“MinHash”（最小哈希），就是指将上面的characteristic matrix的行随机打乱，然后取每一列中第一个非零元素的行号作为该用户的“MinHash Value”（最小哈希值），进行 d d 次打乱产生d个“MinHash Value”，构成该用户的“MinHash Signature”（最小哈希签名）向量，由于签名向量的维度通常远低于商品个数，因此相当于做了降维。使用降维的特征向量来衡量用户之间的相似度。
  以上是MinHash的综述，光这么讲很难理解，下面给出一个例子。假设随机打乱函数 h h ，将矩阵的行顺序变成了beadc，如下图所示， S1 S 1 列的首个非零元素是 a a ，则用a作为 S1 S 1 的签名，即 h(S1)=a h ( S 1 ) = a 。同理，可以得到 h(S2)=c h ( S 2 ) = c ， h(S3)=b h ( S 3 ) = b ， h(S4)=a h ( S 4 ) = a 。


  之所以称之为“MinHash”，我认为，characteristic matrix的每一列都可以看作是对一个用户的哈希化，不同的行排列方式能获得不一样的哈希串，如果两个用户的购买列表足够相似，那么两个哈希串也将是很相似的。而“最小”体现在取“第一个非零元素的所在行”。为什么要费尽心思定义这样一个奇怪的哈希值呢？
  是由于一个神奇的定理：两个集合的MinHash值相等的概率，等于这两个集合的Jaccard相似度。
  首先证明该定理。现在我们拿 S1 S 1 和 S2 S 2 为例，为它们的characteristic matrix行的构成定义三种情况： X X ，Y和 Z Z 。

  • X：该行两列都是1

    • Y Y ：该行只有一列是1，另一列是0
    • Z：该行两列都是0

    •   由于矩阵极其稀疏，可见大部分情况都是 Z Z ，但它对我们的计算没有贡献，不用管。假设X情况的行数为 x x ，Y情况的行数为 y y ，则两个用户的相似性为Jaccard(S1,S2)=x/(x+y)，如果想不明白可以对照上面的韦恩图看看。
        然后考虑 h(S1)=h(S2) h ( S 1 ) = h ( S 2 ) 的概率。假设矩阵随机排列过，我们从头遍历矩阵，那么 X X 在Y前面的概率是 x/(x+y) x / ( x + y ) 。如果最上面的行是 X X 情况（更上面是Z），那么显然 h(S1)=h(S2) h ( S 1 ) = h ( S 2 ) 。如果最上面的行是 Y Y ，则其中一个集合的MinHash Value就是1（第一行），另一个集合的MinHash Value不可能是1，于是h(S1)≠h(S2)。因此一旦我们发现最上面的行是 X X ，才有h(S1)=h(S2)，因此它的概率就是 X X 在Y前面的概率，即 x/(x+y) x / ( x + y ) ，而它与两个用户的Jaccard相似度相等。

      Minhash 签名

        上面说了要对矩阵进行若干次随机重排，但是对于一个可能有上亿行的矩阵随机重排，是一件相当耗时的事情。课程提出了使用 n n 个哈希函数处理“行号”，构造出一个n行的签名矩阵 SIG(i,c) S I G ( i , c ) 。具体算法如下，简单来说，在初始化 SIG S I G 矩阵之后，遍历原矩阵的每一行（商品行），找到非零的列（用户列），将 SIG S I G 矩阵的对应列用 h h 哈希计算的行号进行替换，替换规则是保留较小值。


        例如哈希函数h1(i)=(i+1)%5和 h2(i)=(3i+1)%5 h 2 ( i ) = ( 3 i + 1 ) % 5 ，此处的 i i 表示行号Row，例如行号 Row=2 R o w = 2 ， h1(2)=(2+1)%5=3 h 1 ( 2 ) = ( 2 + 1 ) % 5 = 3 ， h2(2)=(3⋅2+1)%5=2 h 2 ( 2 ) = ( 3 ⋅ 2 + 1 ) % 5 = 2 。


        我们根据算法一步一步来，首先将 SIG S I G 矩阵全部初始化为无穷。


        然后我们看原矩阵的第0行， S1 S 1 和 S4 S 4 列非零，进行替换。第一行 h1=1 h 1 = 1 ， h2=1 h 2 = 1 ，而1比无穷小，因此全部替换为1。


        然后我们看原矩阵的第1行，只有 S3 S 3 列非零，继续替换。


        然后我们看原矩阵的第2行， S2 S 2 和 S4 S 4 列非零， S2 S 2 列显然是全替换，而 S4 S 4 列由于 SIG S I G 矩阵上原有的值都较小，所以进行保留，不做替换。


        然后我们看原矩阵的第3行， S1 S 1 、 S3 S 3 和 S4 S 4 列非零，继续上面的规则替换，可以看到由于 h2=0 h 2 = 0 较小，所以 SIG S I G 矩阵的 S1 S 1 、 S3 S 3 和 S4 S 4 列的 h2 h 2 行都变成了0。


        终于来到了最后一行， S3 S 3 列非零， h1 h 1 行变成了0。


        上面这个矩阵就是最终的 SIG S I G 矩阵，我们可以初步判定 S1 S 1 和 S4 S 4 的相似度为1，但实际上两个用户的Jaccard相似度是2/3，这是由于这个例子使用的哈希函数太少了，如果取的个数足够多，由签名矩阵计算的相似度会接近于真实的Jaccard相似度。

      LSH

        铺垫了那么久终于来到LSH（Locality-Sensitive Hashing）了。MinHash从商品维度上进行了降维，但我们想要计算用户相似度还是很困难，原因是用户也很多，某个著名的社交软件日活跃用户就有十亿，这样的用户pair还是太多了。举个例子，我们有一百万用户（这不过分吧），那么就要计算 C21000000 C 1000000 2 总共上万亿个pair的相似度，那么十亿用户呢？（手动滑稽）一天是跑不完的。
        如果我们的目的就是“计算任意两个用户之间的相似度”，那我们只能做并行，用一个集群计算相似度。但一般情况下，我们只想要知道“某些很相似的pair的相似度”，我们只需要关注那些“比较可能相似的pair”，而忽略剩下的pair。这就是LSH的核心思想。一般地，对一个用户（比如字符串）进行hash，它会被分到某个桶（bucket）中，经过hash而被分到同一个bucket的用户，我们有较大把握认为它们是相似的，称为“candidate pair”，只需要计算candidate pair的相似度就好了，其他的pair可以忽略。
        MinHash签名矩阵的每一列实际上正是用户的hash，一种高效的做法是把签名矩阵分成若干个条状块，每一块有 r r 行。对每一块都配一hash函数，按照用户的这r行数值进行hash，从而分桶。可以让每一快使用同一个hash函数，但它们使用的桶是不一样的，所以不用担心不同的块里面因为 r r 行数值相同而被分到同一个bucket里。
      一脸懵逼吗？不要紧，来看例子。假设我们使用了12个hash函数构造了一个签名矩阵，现在把它切成4块，每块3行，如下图所示。第一块里的第2和4列都是[0,2,1]，所以即使在其他的band里面这两列（用户）的MinHash Value完全不同，他们也还是会被这个band的hash函数分到同一个bucket里面，成为“candidate pair”。然后看第1和第2列，[1,3,0]和[0,2,1]，它们是不同的，但还是有可能在其他band里面相同。另外，假如第3列（[0,1,3]）在band2中是[0,2,1]，而band2与band1使用了同一个hash函数，但它们的bucket是不一样的，所以第三列（用户）并不会被分到band1中第2和第4列所在的那个bucket中。
      这个分桶的操作就等价于聚类，用户的每一行哈希值都是一个特征，我们可以认为band1有着某种隐藏属性，例如“肥宅属性”，而用户2和用户4在肥宅范围内是很相似的，这就是LSH的物理意义。关于聚类的个数，就等于我们分得的桶的个数，这个数值并不是固定的，它与我们的训练数据有关，比如刚才举的这个例子，在band1里就能分出4个桶[1,3,0]、[0,2,1]、[0,1,3]、[2,2,1]。
      当我们构建好签名矩阵之后，我们的模型就是这个签名矩阵，而构造它所选取的哈希函数是固定的，相当于选择了固定的特征，那么，以后新进来一个用户（的列表）query，我们就可以按部就班地对它计算MinHash签名矩阵（向量），然后在各个band中，使用band相应的哈希函数将该用户分到b个不同的群体（bucket）之中，从而达到聚类的效果。值得注意的是，这种聚类是有Overlap的，也就是说同一个用户，可能会被同时分到多个桶之中。


      概率分析

        现在我们来分析一下LSH的一些概率，从而进一步探究LSH的意义。假设上面的 n n 行签名矩阵被分成了b个band，每个band有 r r 行（即满足br=n），现在考虑一个candidate pair（比如假设 S1 S 1 和 S2 S 2 是一对），已知它们的Jaccard相似度为 p p 。

      1. 某一个band中，S1和 S2 S 2 的签名完全一样的概率： pr p r

      2. 某一个band中， S1 S 1 和 S2 S 2 的签名至少有一行不一样的概率： 1−pr 1 − p r
      3. 在所有band中，都有 S1 S 1 和 S2 S 2 的签名至少有一行不一样的概率： (1−pr)b ( 1 − p r ) b
      4. 至少有一个band， S1 S 1 和 S2 S 2 的签名完全一样的概率： 1−(1−pr)b 1 − ( 1 − p r ) b

      5.   我们主要关注最后两个概率，第三个概率描述了一种特殊情况， S1 S 1 和 S2 S 2 不论在哪个band里，都没有完全一样，即使他们的Jaccard相似度很高。最后一个概率曲线如下图所示，横轴是 p p ，纵轴是至少有一个band，S1和 S2 S 2 的签名完全一样的概率。举个例子， S1 S 1 和 S2 S 2 的Jaccard相似度是0.8， r r =5，b=20, 则 0.85=0.33 0.8 5 = 0.33 ， 1−(1−0.85)20=0.9997 1 − ( 1 − 0.8 5 ) 20 = 0.9997 。也就是说如果两个用户有80%的相似性，虽然他们只有33%的可能性哈希签名完全一样，但签名矩阵被分成了20块，它们还是有20次机会成为一组candidate pair，只有 1−0.9997=1/3000 1 − 0.9997 = 1 / 3000 的概率无法成为一组candidate pair（这种情况被称为“false negative”），因此必须指出的是，该算法有一定概率产生假反例，即两个相似用户被判定为非相似。
          这堆概率说明了什么呢？如果两个用户的Jaccard相似度很高，那么LSH将他们分到同一个bucket的概率就会很高，反过来说，如果两个用户被LSH分到了同一个bucket中，那么他们的真实购买历史也有很高的概率非常相似。这就是为什么LSH具有聚类的功能，它实现了聚类的核心：寻找相似的用户并将他们放在一起。然而，必须指出，LSH所聚出的类别，只是“比较高概率”是相似的用户群，我们最终还是要老老实实地用购买列表来计算相似度，只不过，从原来的“对所有用户pair都计算相似度”变成了“仅在较可能相似用户群体中计算相似度”，大大地减少了时间复杂度。


        LSH算法步骤

          总结一下我们在做的事情：寻找candidate pair作为候选相似用户，从而计算它们之间的相似性，进而判断出真正的相似用户。

        1. 对用户属性列表做分词或k-shingles，构造原矩阵（行是词，列是用户）
        2. 选择一个维度 n n （哈希函数个数），对原矩阵计算n行MinHash，构造MinHash签名矩阵
        3. 选择分块数 b b ，块行数r（ br=n b r = n ），设定一个阈值 t≈(1/b)1/r t ≈ ( 1 / b ) 1 / r
        4. 对签名矩阵使用LSH，将用户分桶，构造出candidate pair
        5. 检查每一个candidate pair是不是false negative/postive
        6. 对于签名相似的candidate pair，检查用户购买列表是否真的相似

        LSH时间复杂度分析

          MinHash首先要对所有商品行（ N N 个商品）分别做n次行号哈希变换（ n n 个哈希函数），因此复杂度是O(nN)，接着需要遍历商品行并用哈希过的行号进行替换，复杂度是 O(nN) O ( n N ) ，因此整个签名矩阵的构建复杂度是 O(nN) O ( n N ) 。接着就是LSH分桶，对于每个band（ b b 个）都遍历一次用户列（有M个用户），将用户哈希到对应的桶，因此复杂度是 O(bM) O ( b M ) 。因此整个LSH的复杂度应该是 O(nN)+O(bM) O ( n N ) + O ( b M ) 。
          如果不使用LSH，对所有用户进行聚类，并用用户在商品张成的基的投影计算余弦相似度，那么时间复杂度是 O(M2N) O ( M 2 N ) ，可见LSH不仅降低了空间复杂度，还降低了时间复杂度。

        LSH总结

        1. LSH的思想是，我们并不需要对所有的用户pair计算相似度。
        2. LSH算法被用于相似性检测，它对用户-商品矩阵计算MinHash签名，然后分band进行分桶，从而达到聚类的效果，在空间复杂度和时间复杂度上都要优于暴力聚类。
        3. LSH的聚类结果是有Overlap的。
        4. LSH的聚类是“比较有可能相似的物品集合”，最好用于初步筛选，还需进一步验证相似性
        5. LSH的聚类结果有一定概率有误：相似物品没有被聚在一起，非相似物品被聚在一起。

        SimHash

          MinHash签名有一个问题，它无法处理带权数据。也就是说它平等地对待每一个物品（行），假如我们具备一定的先验知识，得到了每个物品的重要性，或者某个权重，MinHash就无法处理了。这里介绍一种能处理带权物品的hash，SimHash。它的提出是基于普通hash函数的缺陷：即使两个字符串之间只有一点不同，hash过后的串也大不相同。换句话说，无法将相似性度量扩散到hash之后的串。SimHash的提出正是为了能够在hash过后的串上衡量两个原串的相似性，它能使得两个比较相似的串在hash过后的串也能具有较强的相似性（汉明距离），甚至完全一样。

        1. 将文章分词
        2. 计算每个词的权重（例如TF-IDF）和普通hash串
        3. 根据hash串的取值将词Embedding为正负权值交替的向量
        4. 将向量求和，并按照向量的正负得到最终的SimHash

          下面举个例子。我们先将文章分词，将它当成一个Bag-of-Words模型，然后为每个词计算一个重要性，比如计算TF-IDF值，作为它的权值 w w ，同时把词本身进行hash，取后6位。接着，按照hash传embedding，串取1的位置赋w，串取0的位置赋 −w − w ，比如串“001011”，则第1、2、4位取 −w − w ，第3、5、6位取 w w ，得到该单词的Embedding −w,w,−w,−w,w,w。所有单词都计算完Embedding之后，做向量加法，然后根据正负，再二值化成01串。比如 [102,57,-40,-32,66,-7] 的第1、2、5位是正数，则取1，第3、4、6为是负数，则取0，最终得到“110010”，即该文档的Simhash。


          SimHash与MinHash一样，都是将文档从词向量空间进行降维，最终的效果都是得到“文章-哈希签名”这样一个对应关系。只是SimHash支持带权基，MinHash不支持。

        参考资料

        • 【阿里云】Simhash 的解释及实现
        • 【simhash库】A Python Implementation of Simhash Algorithm
        • 【博客】使用SimHash进行海量文本去重
        • 【csdn】LSH︱python实现MinHash-LSH及MinHash LSH Forest——datasketch（四）
        • 【博客】聚类之minhash
        • 【Paper】ch3 : Finding Similar Items
        • 【csdn】海量文档查同或聚类问题 – Locality Sensitive Hash 算法
        • 【博客】我的数学之美系列二 —— simhash与重复信息识别

这篇关于海量数据相似性度量与聚类： LHS-MinHash的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/626831。

相关文章

javaScript在表单提交时获取表单数据的示例代码

javaScript在表单提交时获取表单数据的示例代码

《javaScript在表单提交时获取表单数据的示例代码》本文介绍了五种在JavaScript中获取表单数据的方法：使用FormData对象、手动提取表单数据、使用querySelector获取单个字... 方法 1：使用 FormData 对象FormData 是一个方便的内置对象，用于获取表单中的键值
阅读更多...
Rust中的BoxT之堆上的数据与递归类型详解

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2
阅读更多...
Python使用Pandas对比两列数据取最大值的五种方法

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数
阅读更多...
Redis的数据过期策略和数据淘汰策略

Redis的数据过期策略和数据淘汰策略

《Redis的数据过期策略和数据淘汰策略》本文主要介绍了Redis的数据过期策略和数据淘汰策略,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录一、数据过期策略1、惰性删除2、定期删除二、数据淘汰策略1、数据淘汰策略概念2、8种数据淘汰策略
阅读更多...
轻松上手MYSQL之JSON函数实现高效数据查询与操作

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》：本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE
阅读更多...
Python给Excel写入数据的四种方法小结

Python给Excel写入数据的四种方法小结

《Python给Excel写入数据的四种方法小结》本文主要介绍了Python给Excel写入数据的四种方法小结,包含openpyxl库、xlsxwriter库、pandas库和win32com库,具有... 目录1. 使用 openpyxl 库2. 使用 xlsxwriter 库3. 使用 pandas 库
阅读更多...
SpringBoot定制JSON响应数据的实现

SpringBoot定制JSON响应数据的实现

《SpringBoot定制JSON响应数据的实现》本文主要介绍了SpringBoot定制JSON响应数据的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录前言一、如何使用@jsonView这个注解？二、应用场景三、实战案例注解方式编程方式总结 前言
阅读更多...
使用Python在Excel中创建和取消数据分组

使用Python在Excel中创建和取消数据分组

《使用Python在Excel中创建和取消数据分组》Excel中的分组是一种通过添加层级结构将相邻行或列组织在一起的功能,当分组完成后,用户可以通过折叠或展开数据组来简化数据视图,这篇博客将介绍如何使... 目录引言使用工具python在Excel中创建行和列分组Python在Excel中创建嵌套分组Pyt
阅读更多...
在Rust中要用Struct和Enum组织数据的原因解析

在Rust中要用Struct和Enum组织数据的原因解析

《在Rust中要用Struct和Enum组织数据的原因解析》在Rust中,Struct和Enum是组织数据的核心工具,Struct用于将相关字段封装为单一实体,便于管理和扩展,Enum用于明确定义所有... 目录为什么在Rust中要用Struct和Enum组织数据？一、使用struct组织数据：将相关字段绑
阅读更多...
在Mysql环境下对数据进行增删改查的操作方法

在Mysql环境下对数据进行增删改查的操作方法

《在Mysql环境下对数据进行增删改查的操作方法》本文介绍了在MySQL环境下对数据进行增删改查的基本操作,包括插入数据、修改数据、删除数据、数据查询（基本查询、连接查询、聚合函数查询、子查询）等,并... 目录一、插入数据：二、修改数据：三、删除数据：1、delete from 表名;2、truncate
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2