海量数据挖掘 - 相似度比较问题 - 阅读文章的思考

（文章写于20200725 08:50）

引言

关于海量数据场景下，对于相似度的比较问题，我一直比较关注。最近也重新看了《massive dataset minning》的第三章节，其主要内容是通过minhash+LSH来实现相似度的比较；然后看到了另外的几篇博客，在这里来记录一下我的思考。

思考

相似度比较的问题应用非常广泛，比如文章的去重，文章是否是抄袭等。特别是我对恶意软件进行研究，需要进行相似度的比较，采用的指纹生成方式是ssdeep，但是为了找到相似的对，就必须对整个数据集对自身做笛卡尔积，然后分别求解每个对的相似度，这种两两相比的过程是非常耗时的。当时的解决方案是通过开启多个线程进行计算，然后另外一个线程进行写数据库。这种方法，从使用的角度来讲是比较low的。对于这种两两相比的问题，如果确实需要全部数据对的相似度，基本上没有什么优化的捷径，只能是从多线程的角度让速度提升来，但是进行比较的数据对的数量，是完全没有减少的。这种场景对于我这种数据量比较小的情况，还能接受，但是如果数据量大了怎么办。

一般来说，对于相似度的比较，我们比较关心的是什么呢？

• 从海量数据中，找到相似度最高的 t o p − k top-k top−k对
• 从海量数据中，找到与某个项最相似的 t o p − k top-k top−k对

我在恶意软件比较的问题中，当前关注的是全部的数据的相似度对的排序，也就是上述中第一个；如果后期研究过程中，增加了检测过程，需要的对一个新的数据进行检测，查看其最相近的，那么就是第二个问题。本质上，有点像离线批处理和在线处理一样。

minhash+LSH的文章阅读

本篇文章暂时不讲述为什么这两个内容的原理（后续文章会有更多的内容），主要记录一下看到的几篇比较有用的文章，同时记录一下自己的感受。

1.海量数据相似查找系列1 – Minhashing & LSH & Simhash 技术汇总

这篇文章[1]中，其介绍了minhash+lsh的原理，因为之前有一定基础，所以阅读起来就轻车熟路。不过，他这里提到了一个问题，也让我比较苦难：这种方法是适用于高维稀疏矩阵的。同时在文章[2]中也提到了在高维稀疏矩阵的情况下，这种方法比较适用。

但是我在书[1]中，并没有看到这种描述（可能我漏掉了？如果是这么个情况，后续订正）。但是我可以思考思考，为什么这种方式可能不适用于高维稠密数据。在书[1]中，相似度比较的方式是通过模拟元素的排列，然后查看两个集合中最先出现某个元素共有的情况的概率。那么如果是高维稠密数据，是不是说，他们碰撞的概率会更高呢？也就是说，如果是他们碰撞的机率比较高的情况下，那么利用这种计算的方式，并不能有效减少两两相比的次数。（个人理解，后续继续关注）

海量数据相似查找系列2 – Annoy算法

这篇文章就是针对高维稠密的数据来进行相似度比较，利用了Annoy算法。

参考文章

1. Mining of Massive Datasets
2. 海量数据相似查找系列1 – Minhashing & LSH & Simhash 技术汇总
3. 局部敏感哈希LSH（Locality-Sensitive Hashing）——海量数据相似性查找技术
4. 海量数据相似查找系列2 – Annoy算法