第三章：寻找相似的项目
2020/07/21 -
引言
这个章节的内容如下：
- 将相似度比较问题转化为集合论的问题，找到相似对也就是找到两个相交集非常大的集合
- 文章相似度的比较过程中，可以利用shingling的方式，就是n-gram来形成集合
- minhash技术来将大量的数据集合压缩
- LSH哈希算法，来解决在数据量较大的时候，两两相比过程中计算复杂度过后高的问题
- 解析相似度比较框架，将LSH方法应用于其他场景
其实我对这个minhash、LSH、ssdeep这些概念都比较混乱，我一直以为他们是相似的，这里就借助这个机会好好理解理解。
而且，我记得这部分的应用时，并不是说就要按照两两相比的方式来求出所有的样本之间的对比。他们的经典应用是，找到这个样本的topk相似样本，或者找到topk的相似样本对。而且他们这种相似度比较方法，也都是暗中大约式的比较，并不是精确的得到某种相似度。不过，我是有点感觉不对，就是好像还有别的应用，我有点淡忘了。
通过指纹来代表一个文章
虽然利用n-gram这种方式可以将数据进行转化为集合的形式，但是如果将集合中所有的项目都进行哈希，然后进行存储，在大数据量的情况下，这个存储空间的要求也是非常巨大的。那么这种情况下，就需要压缩这个数据，通过指纹的形式来代表这个数据。我这里来简单描述一下这个思想，就是说， 在大数据的情况下，如果能够有一个压缩的方式将一个数据简化，得到一个指纹这个指纹在某个空间上，还能代表着原来的数据。。。。。卧槽，我怎么就感觉这个说法，这么熟悉。
将数据进行降维，降维之后还能保证数据能保证原来的一些特性，卧槽。
这里需要保持的特性就是，将这个集合在集合在进行压缩之后，利用这个指纹，依然能够求这两个集合的杰西卡相似度。
但是这里需要注意的是，这种方式并不能得到非常准确的杰西卡系数，但是能够大致逼近这个数据，apporiate这种。
首先来说明一下如果来代表集合（这里还真是让我想起了，什么数据结构能够代表集合呢。。。哈希表？）
特征矩阵
通过代表这个元素是否在集合中出现过。（通过这种方式就转化为了矩阵的方式）
那么如果是要计算相似度的话，只需要用列向量就好了。
（但实际情况中，经常不使用这种方式作为存储集合的方式，因为这种矩阵的方式会导致整个矩阵非常的稀疏；而是利用零哇哇i一种就是，就是只记录某个数据不为0，只记录位置数值）
Minhashing(p99)
这里想要的集合的指纹，由大量的计算组成，每一个都是一个前面提到的特征矩阵的minhash。
第一个介绍的一种minhashing的方式是，通过选择一种特征矩阵的列的排列方式，然后hash函数结果将是第一次出现的数值。
一种排列方式
h(s1)=a h(s2)=c h(s3)=b h(s4)=a
他这里说出了一个非常有意的事情，就是集合的杰西卡系数和minhashing数值是有联系的。
（对于某种随机排列的列结果）minhash函数生成相同数值的概率是等于这些集合的杰西卡系数。（这个是绝对等于还是大约等于呢？这里没说。 从后面的即使来看， 他是有一个强的假设，那就是这个生成的元素排列一定要是随机的）
image.png
来看一下原理解释：
首先，将某两个集合取出来，然后随机排列元素，这种情况下。每行的元素只有三种情况，1.X类型，S1和S2都好看，这行为1
- Y类型，S1和S2中只有一个为1，3. Z类型，S1和S2都不为1，都不包含
矩阵经常性是稀疏的，很多行都是Z类型；但是具体决定杰西卡系数sim(s1,s2)的是X和Y类型的位置，同时他也决定了h(s1)和h(s2)。令x为X的行数目，y为Y的行数目，那么sim(s1,s2)=x/(x+y)，这个内容无可厚非。
下面来分析h(s1)=h(s2)的概率，假设这个（列的）排列组合是完全随机的，我们首先遇到x，比我们首先遇到y的概率应该是x/(x+y)，这个公式一开始不容易理解，可以想象成是一种随机取东西的场景，随机出一个，先是这种的那就是x个，然后除以总数。所以在这种情况下，那就是说h(s1)=h(s2)的概率是等于杰西卡系数的。所以他们就通了。（注意，这是假设这个随机概率场景下）
接下来说明一下minhash指纹。
还是按照特征矩阵来说明，随机从元素的排列中抽取n个，然后分别按照这个n作为minhash函数来进行计算，那么这个时候就得到了一个长度为n的向量，然后还是按照列为集合名的方式，那么这种方式就又得到了一个矩阵，这个矩阵就是指纹矩阵。
计算哈希指纹
这里来说明一下， 当手里的元素非常多的时候，比如成千上万个，那么你这个时候怎么计算他的排列组合。。（我他妈感觉，这不就是算法里面学习的东西吗。。。哎）这里需要这种计算的方式，就是因为仅仅在元素数量比较多的时候，无法进行完全随机的进行排列。
但是这个东西的计算过程，我感觉这个算法有点玄乎，我没太看懂。
我看明白了，实际上它是利用一个哈希函数（这个哈希函数尽量实现这些0-k-1的数值能够不发生冲突）来实现一个伪序列。首先将元素名转化为整数，然后计算这些整数的哈希值。
↑上面这句话不是很准确， 因为我通过他书上的例子，其生成的两个伪序列，并不能得到一个杰西卡系数的估计；但是他给出的这个算法却可以这样计算，因为他是持续更新的。我不知道是什么原理。
我觉得这里应该是我理解错误了。前面也提到了，使用这种minhash的方式，随机生成的排列（生成相同的minhash的概率）是等用户杰西卡系数的。但是这里仅仅说的是概率。
那么如果是这样的话，他后面又使用了指纹矩阵是什么意思呢？
我总感觉这里差了一步，就是我已经直到minhash能够在概率上等于杰西卡系数，但是要生成这个minhash是比较困难的。
那为什么还要生成一个指纹矩阵呢？
首先还是回到这个minhash和杰西卡系数联系的地方，他说的是如果是随机生成的序列，他们minhash函数相等的概率是等于杰西卡系数的。
但从这个整体的内容安排上来看，在介绍了这个概率相等的内容之后，就出现了指纹的事情，也就是最开始所提到的。
这里的指纹采用的是minhash指纹。
其实我也挺纳闷的，既然已经事这种情况了，那么为什么还要有这种方式呢？是说利用整个指纹来模拟这个概率吗，这里不是很懂。
这个需要进一步再进行学习。
这里同时提到了一个问题，就是说，这种计算方式的mapreduce的实现框架，这个也值得思考，但我更关系的，其实是这个矩阵式怎么存储的。
使用minhash指纹来进行LSH
首先，书本上提到，如果是想得到两两相比的结果，那么这种方式必然是没有捷径的，肯定是要通过真实地比较每个对来得到结果，当然在当前大数据的框架下，可以通过利用并行来计算结果的方式得到结果；然后，LSH在这种需求下就有了用武之地，其主要做法就是，既然得到全部的比较对非常耗时，那么可以通过LSH的方式，获取其中最相近的对，所以LSH也被称为近邻搜索。
一种通用的方式来实现LSH就是将某个数据hash很多次，这种如果相似的项目会以比较大的概率被分配到同一个桶中，这样可以考虑如果是哈希到同一个桶中的数据对为相似的，然后为了检测相似度的话，就只检测这部分数据。
这里有一个问题，就是哈希多次，那么hash算法是什么呢？如果都是某个数值取模，好像是有这么个效果（数值情况下）。
上面的方式其实是基于这种假设，那就是大部分非相似的数据不会被hash到同一个桶中，这些数据也永远不会被检查。如果某两个实际上非相似的数值对被hash到了同一个位置，那么这种情况算是一种假阳性。
然后，LSH的做法，书上的介绍就是，通过将这个minhash指纹矩阵进行分割（在行的角度），然后分割之后，对每个里面的列向量进行哈希，如果他们哈希结果是相等的，他们就是相似的备选。然后相似的个数越多，就越大程度相似。
这里他有一个理论计算，我没太看懂。后面要具体分析一下再。
这里来整理一下她的整体流程：（p109)
1）利用k-shingles来代表文档，并进行相应的hash，进行排序再
2）选择minhash指纹的n，然后计算minhash指纹
3）选择一个阈值t作为lsh的
4）进行计算
5）然后最好是进行一下，所谓的相似度高的对
但是说实话， 我没有看到她到底是怎么计算的，就是为什么这种方式就提高了呢？还是不是要先两两相比吗？
还是说，如果确定了阈值，就可以不计算某些呢？
常用的距离测量函数
- 欧式距离
- 杰西卡距离
- consin距离
- 编辑距离
- 汉明距离
后面的内容就更多了，感觉好像都看不完了。。。。太刺激了。。
