近乎复制检测——SpotSig算法详解(转）
近似复制检测——SpotSig算法详解(转）
（1）
原帖地址：http://blog.sina.com.cn/s/blog_67914f2901019xdt.html
一、算法思想
对文档集合进行预处理，根据比较粗的一种划分方式将文档集合进行分类。只比较同一类中的文档，从而缩短比较时间，减少运算次数。
二、算法流程
对于一篇文档，先对其进行预处理，获得其spot signature集，该集合是一个多重集合。根据集合长度将所有文档映射到划分好的分隔中去，该映射满足相似度高的文档映射在同一分隔或相邻分隔中，相 似度低的文档映射在不同的分隔中，并且划分要在满足条件的情况下尽量细。进行文档相似度比较时，只需比较在同一分隔或相邻分隔中的文档，利用多重集合的 Jaccard相似度公式，将Jaccard相似度大于某个阈值的两篇文档视为相似文档。文档最后返回相似文档对的集合。
三、具体方法
（注：算法中|di|和pk都是大于1的整数，在第（三）部划分中可以将pk和|di|放在直线上进行可视化，会更容易理解。）
（一）文档预处理（提取每篇文档的spot signature集）
定义一个先行词集合（先行词即为在文章中频繁出现的词，一般为停用词：is,the等），对一篇文档从头开始检查，每遇到一个定义在先行词集合中的词a， 便从该先行词后面的第一个词开始取相对距离为d的一个词，直到取到规定个数c。比如is(2,3)即为从a后面第一个词开始，取相对距离为2的词，一共取 3个。若在取词过程中遇到另一个先行词，则跳过该先行词从后面第一个非先行词为开始继续取词。举个例子，现有一句话为At a rally to kick off a weeklong campaign for the South Carolina primary.先行词集为{a,is,the,to}，取d=2,c=2，则a(2,2)={off,weeklong},to(2,2)={off,weeklong}等等。如此执行便可得到对应该文档的一个spot signature集合。对同一篇文档，还可以取不同的d和c，以得到更大的spot signature集，但其他文档也必须对应的取不同的d和c。比如文档1取d=1,c=3和d=2,c=4两种，则其他文档也必须取这两种，而不能只取一种。
（二）文档相似度匹配（Jaccard相似度公式）
普通集合的Jaccard相似度公式定义如下所示：
显然的，会有如下不等式成立：
因此，会有如下不等式成立：
（2）
在上面不等式中，d1和d2分别设定如下：
对于|d1|<=|d2|的情形来说，不等式（2）中分子=|d1|，分母=|d2|。
可以看到对于两个文档d1和d2，若|d1|/|d2|<
， 为定义的阈值，则d1与d2的Jaccard相似度会小于阈值， 则d1和d2不满足相似的条件，可以不予比较。所以，在使用Jaccard相似度公式进行相似度计算之前，可以先比较文档向量的长度，长度之比小于阈值的 两文档不予比较。注意，此处定义的文档距离便是向量长度意义上的距离。相应的，在哈希映射中，这样的文档不应该映射到同一个分隔中。实际上，最优化的分隔 应该满足以下三个条件：
以上集合A和B为普通集合，而上一步生成的spot signature集是多重集合，即集合中会有重复元素。因此，定义对应的多重集合的Jaccard相似度如下：
注意此处的集合A和B均为多重集合，因此A和B中元素会有对应的出现次数。而freqA(sj)即为元素sj在集合A中出现的次数。因此，上式分子表示A和B中相同的spot signature的较小个数之和，即A交B的元素个数。假如A和B*有的一个s，若s在A中出现3次，在B中出现5次，则分子加和中的对应s的加项就是3。分母表示A和B中所有spot signature中较大个数之和，即A并B的元素个数。对于A和B中独有的元素s1，s1 的个数即为分母中一个加项，对于A和B*有的元素s2，取s2在A和B中出现次数较多的次数为分母中的一个加项。比如A= {1,1,2,2,2,3},B={2,2,3,3,4,4}，则A交B={2,2,3}，分子为2+1=3，A并B= {1,1,2,2,2,3,3,4,4}，分母为2+3+2+2=9。
由上可知，多重集合和普通集合的Jaccard相似度本质上是一样的。
这里有一个距离成为Jaccard相似意义上的距离，与下面要讲的向量长度意义上的距离不同。详见下文。
由上可知会有下面不等式成立：
该不等式可参考不等式（1）及其说明，两者本质上是一样的。
以及下面不等式成立：
在上面不等式中，d1和d2分别设定如下：
对于|d1|<=|d2|的情形来说，不等式（2）中分子=|d1|，分母=|d2|。
（三）最优划分（将文档向量映射到分隔中）
根据上节中定义的Jaccard相似度公式，有如下不等式：
可以看到对于两个文档d1和d2，若|d1|/|d2|<
（1）对于所有的两两文档对<di,dj>，如果满足|di|<=|dj|且|di|/|dj|>=，则应该将文档di和dj映射到 同一个分隔或者相邻的分隔中。
（2）对于文档对|di|和|dj|，如果满足|di|<=|dj|且|di|/|dj|<，则文档di和dj不能映射到同一个分隔 中。
（3）在满足（1）和（2）的基础上，分隔应该尽可能的小，即分隔数应该尽可能的大。
具体划分方法如下：
设
=max(|di|)，则待分隔的区域为[1,]，文章提出的分隔方法是：将区域分隔成区间[pk,pk+1)的形式，从p0=1开始，对于任何得到的pk，选取pk+1为满足以下两个条件的最小整数：
（1） > pk+1 > pk
（2）pk+1 - pk < （1-）pk+1，即pk/pk+1 >
下面验证这种划分方法满足上述三个条件：
先看条件（1），若文档di映射在pk上，对于文档di'，|di|<=|di'|且|di|/|di'|>=，有|di'|-|di|<(1-)|di'|，而(pk+1 - pk) < (1-)pk+1，因此有|di'| < pk+1，故|di'|在区间[pk,pk+1)中。若文档di映射在区间[pk,pk+1)内，因为(pk+2 - pk+1) < (1-)pk+2，所以对满足上面条件的di'一定有|di'| < pk+1。对于小于|di|的文档di'，同理可证。因此，条件（1）满足。
再看条件2，若两文档di和di'满足：|di| <= |di'|且|di'|-|di| > (1-)|di'|，若|di|=pk，即文档di映射在pk上，因为pk+1 - pk < (1-)pk+1，则|di'| > pk+1，故di与di'映射到不同的区间内。故条件（2）满足。
再看条件3，这种方法并不能严格的满足条件3的要求，因为条件3提出的是一种最优化，而这种最优化是不能用解析式来表示的（not in closed-form），这是种近似的方法。从这种分隔方法中可以看到，分隔端点的计算只与有关，因此只要给定了， 从p0=1开始，就可以计算出后面的端点。因此，在得知文档数据信息之前，就可以预先进行区间的划分。最优的方法是使划分的分隔在满足条件（1）和（2） 的情况下尽可能小，而在条件（1）的限定下，分隔不能无限的小。该划分方法距离最优化方法有多远是由数据集的属性决定的。当文档向量的长度|di|密集到 遍布在[1,]的每一个整数值，即对|di|=1,2,…,，都能找到对应长度的文档向量。此时，该划分方法达到最优，因为如果再细分，就会发生违背（1）的情形。会这样的原因是，这种划分的过程中就是以阈值为导向的，对每个区间[pk,pk+1)，都有pk/pk+1 > ，若文档足够密集以至于文档向量长度值填满了整个区域[1,]， 则在任何位置插入新的端点以细化分隔的操作都会违背条件（1）。举例说明，按上述方法进行划分后有两个区间为[20,30)和[30,45)，则按假设， 文档向量长度值填满了整个区域，则在这个区间内有长度为20,21,22,23,24,25,26,27,28,29的向量。若细化该分隔，插入了端点 25，将[20,30)划分为[20,25)和[25,30)，根据条件（1），区间[30,45)中可能存在需要与区间[20,30)中文档进行比较的 文档，而插入端点25后，区间[20,25)即被视为与[30,45)无关的区间，则违背了条件（1）。所以，此时（文档向量长度值布满整个区域[1,]）上述划分方法为最优方法。
（四）建立倒排索引（通过筛选进一步减少需要进行Jaccard相似度计算的文档数）
建立倒排索引的方法是这样的：对每个分隔，不妨设为[pk,pk+1)，对该分隔中的每个文档，不妨设为di，对该文档对应文档向量中的每个spot signature，不妨设为s[i][j]，将指向分隔中所有包含s[i][j]的文档的指针存入一个集合中，即生成倒排索引集。具体使用方法见（五）算法。
（五）算法（SpotSigs Deduplication Algorithm）
具体算法及其详细解释请在百度文库中搜索：SpotSig算法（含详细注释）。
（六）两种意义上的距离
1、文档向量长度意义上的距离：距离D(di,dj)=|di|-|dj|，for |di| >= |dj|
这种距离在算法中主要用在将文档映射到具体分隔上。具体参见（三）最优划分
2、Jaccard相似度意义上的距离。这种距离主要用在（五）算法中，用于设置筛选条件。
因为每个文档向量都是个spot signature集，这是个多重集合，因此每个元素存在个数，这种意义的距 离下，如果文档di的向量中有spot signature s，对应个数为
，文档di'的向量中没有spot signature s,在文档di和di'在这种意义上的距离至少是，虽然从向量长度意义上的距离来讲，两者有可能很接近甚至 相同。
这种距离之所以成为Jaccard相似度意义上的距离，是因为这种距离影响着文档的Jaccard相似度。 Jaccard相似度描述的是两篇文档对应的文档向量中相同的spot signature个数与所有spot signature个数之 比，比如di={s1:3,s2:4,s4:2}，di'={s1:2,s3:3,s4:1}，则di与di'的Jaccard相似度为sim(di,di')= (2+1)/(3+4+3+2)=25%。而其向量长度上的距离为|di| - |di'| = 2，与Jaccard相似度计算的相似性相比， 由向量长度意义上反应的相似性要更强一些。这就是为什么落在同一分隔内的文档仍然要进行Jaccard相似性 计算的原因。
另外，如果di中含有个s，而di'中不含s，则di与di'在Jaccard相似度意义上的距离至少为，假设di和 di'其余的spot signature及其个数都相同，此时计算出来的Jaccard相似度最大，为 sim(di,di')=|di'|/|di|=|di'|/(+|dj|)，若令sim(di,di')<，则得到 > (1/ - 1)|dj|（3），即当 满足这个不等式时，di与di'的Jaccard相似度小于，即若两篇文档的Jaccard相似度意义上的距离至少为 时，一定不满足相似度要求，即可不比进行Jaccard相似度计算。在文章内提出的算法中，用该条件来筛选候 选文档（原文中为 > (1 -)|dj|，由于有 > (1/ - 1)|dj| > (1 -)|dj|，原文可能进一步进行了缩 放以增加速度，不过这只是个人理解，至于其他有说服力的理由实在想不到，文中的不等式会筛选掉更多 的文本，有Jaccard相似度大于的文本也会被筛选掉）。上面讨论的用在算法的第24到第26行，第15行到第 18行也用到了Jaccard相似度意义下距离的有关知识。