数据相似性的度量方法
现实中，我们需要处理的数据具有着不同的形式和特征。而对数据相似性的度量又是数据挖掘分析中非常重要的环节。针对这些不同形式的数据，不可能找到一种具备普遍意义的相似性度量算法，甚至可以说，每种类型的数据都有它对应的相似度度量标准。
数据属性分类
现实世界，任何事物其实都可以描述成一个对象。这个概念其实跟面向对象编程中对象的含义是一致的。对象有很多属性，属性的类型当然也有所不同。打个比方说，如果把我看做一个对象，那我就基本拥有“姓名”、“性别”、“年龄”、“籍贯”等等，这些都是我的属性，和起来就是一条数据，也就是户籍部门拿到的关于我这个对象的数据。同理，如果把一张图片看做一个对象，那么“像素值”，“亮度”、“对比度”，“饱和度”等等就是图片的属性。处理图像数据，当然要从这些属性入手。
所以，看到这里，我们大概能总结出来2点：
- 一般情况下的数据挖掘工作，其实就是针对1个或多个对象及其属性做的运算，而数据一般就被表示为：object: attributes的形式。
- 不同对象（甚至相同对象在不同的应用场景下）的属性类型不同。需要分类讨论。
标称属性
属性值一般是一些符号或事物的名称。比如说，对相亲网站的注册用户，系统可会记录如下信息：性别，年龄，职业，地点，学历等等。这些数据都是通过名称来描述的。
二元属性
这个好理解了，所有属性都可以通过最简单的0，1描述。一般常用来表示存在性。比如说，一个感冒患者一般会用是否存在“发烧”、“流涕”、“咽痛”等症状来做记录，存在这些状况，记录为1，不存在，记录为0。当一个患者来看病时，当然就可以通过这些属性值是否为1来做出诊断的结果。
序数属性
属性值是由有意义的排序数决定的。例如，对一部电影评价，可以分为“剧情”、“演员”、“音乐”、“特技”等几个方面评价，而每个方面都有“好”、“中”、“差”3个选项供选择。而这些有排序意义的选择之间我们是无法说明具体差距的。也就是说，是定性，而非定量。
到此为止，上面的3种属性都是定性的，而非定量的。
数值属性
那么对于属性可以定量的这种属性类型，只怕也是我们生活中遇到情况最多的了，这种属性，就叫“数值属性”，有关于这些属性值的分析可以说是最多的，常见的平均数，众数、中位数等等，就是处理这些属性的。后面我们还可以看到，对于拥有数值属性的对象相似度的度量，也有着相应的方法。
相似性度量
我们分别就刚才所说的4种属性，看看当一个对象拥有不同类型的属性时，应该用什么方法度量。其实，没有人能告诉你一种对象到底该用什么样的方法度量其相似性，因为现实中，可能很多情况下你所需要测量的数据是非常复杂的，所以这里也只是给出一些常见的处理方法，具体问题还要具体分析。
标称属性相似度度量
二元属性相似度度量
总的来说，和标称属性是类似的，但是情况稍微复杂一点。要分成对称和非对称2种形式。
(1)对称二元属性
先看对称的情况，所谓对称，是说对象的所有属性都是一样重要的。这就和标称属性类似了，用所有具有相同属性值的属性个数除总的属性数。公式和标称属性一致：
(2)非对称二元属性
所谓非对称，是说我们只关心“正匹配”的情况，也就是只关心两个对象属性中，都是1的情况。公式如下：
数值属性相似度度量
当然，我们还有序数属性的相似度没讲。但是序数属性的相似性测量与数值属性确是有一定联系的，所以，先看数值属性对象如何度量其相似度。
对于数值属性的相似度度量有一套完整的方法，那就是大名鼎鼎的“闵可夫斯基”距离，也叫Lp范数。
(1) 欧氏距离
因为数值属性一般都是以数值向量表示的。所以，当然也要从数值向量上下功夫。最常见的判断两个向量距离的方法就是我们熟知的欧氏距离，公式如下：
(2) 曼哈顿距离
除了欧氏距离，还有一种方法叫曼哈顿距离，起名的由来是计量由方块形构成的曼哈顿街区的距离，因为街区不能横穿，只能按照方格走到。所以，这种距离的度量方式也就很清晰了，就是两个向量之间各个维度的差的绝对值之和，公式如下：
(3) 闵可夫斯基距离
将曼哈顿距离与欧氏距离推广，可以得到闵可夫斯基距离，也叫Lp范数。公式如下：
序数属性相似度度量
序数属性的每个属性值都代表了一种次序，所以，不论使用数字表示的，还是用文字性的叙述，都可以表示成数字的形式。例如，一个对象的某个属性有“大”、“中”、“小”3个可能的属性值，我们当然可以用相应的1、2、3来替代这种文字性的叙述。
当转换成对应的整数之后，为了使每个属性都有相同的权重（这个很容易理解，有些属性只有“大”、“中”、“小”3中选项，有些却有“下”、“中下”、“中”、“中上”、“上”5个属性，这样，不同属性之间的权重当然没有可比性了），将通过以下公式将每个整数型的属性值映射到[0.0, 1.0]的区间上。
混合类型属性相似度度量
上面说的这几种情况都是数据库中的数据相对类型比较统一，但是很多时候，实际工作中遇到的情况却并非如此。我们遇到的一组数据可能拥有多种类型的属性，也就是混合类型属性。
碰到这种情况，一种一般的处理办法是按照如下公式：
余弦相似性
余弦相似性是一种针对文档数据的，特殊的相似度测量方法。
在处理文档的时候，我们一般采用文档所拥有的关键词来刻画一个文档的特征。容易想象，如果能定义一个字典，（所谓字典，就是包含了所处理的文档集的所有可能的关键词的一个有序的关键词集合。从这个角度讲，好像叫词典更为合适，但是字典的叫法已经是惯例了），那么就能通过字典为每个文档生成一个bool型的向量，这个向量与字典等长，每个位置用0、1表示字典中对应的关键词在该文档的存在性。
这么看，好像和前面说的二元属性没有什么不同。但是如果为了实现一种更准确的度量，再给这个二元向量加个权重，比如每个词的词频，那么用上面讲的任何度量方法就都不是特别合适了。例如，如果用欧氏距离判断相似度的话，因为这种向量很多位都是0，就是说很稀疏，这就导致大部分词是两个文档所不共有的，从而判断结果是2个文档很不相似。
对于这种文档-关键词的特殊情形，我们一般采用余弦相似度。
其中，x,y是2个文档解析出来的词频向量。当然，有关于文档的相似度判断是整个信息检索领域的基础问题，也是核心问题。这里面内容相当丰富，以后再详谈，这里只是将余弦相似度做个简略的介绍。
LSH简介
LSH(Locality Sensitive Hashing)翻译成中文，叫做“局部敏感哈希”，它是一种针对海量高维数据的快速最近邻查找算法。
在信息检索，数据挖掘以及推荐系统等应用中，我们经常会遇到的一个问题就是面临着海量的高维数据，查找最近邻。如果使用线性查找，那么对于低维数据效率尚可，而对于高维数据，就显得非常耗时了。为了解决这样的问题，人们设计了一种特殊的hash函数，使得2个相似度很高的数据以较高的概率映射成同一个hash值，而令2个相似度很低的数据以极低的概率映射成同一个hash值。我们把这样的函数，叫做LSH（局部敏感哈希）。LSH最根本的作用，就是能高效处理海量高维数据的最近邻问题。
定义
相似度的定义根据实际情况自己决定，后面我们可以看到，针对不同的相似度测量方法，局部敏感哈希的算法设计也不同，当然，无论是哪种LSH，其实说白了，都是将高维数据降维到低维数据，同时，还能在一定程度上，保持原始数据的相似度不变。LSH不是确定性的，而是概率性的，也就是说有一定的概率导致原本很相似的数据映射成2个不同的hash值，或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的（因为降维势必会造成某种程度上数据的失真），不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率，这也是LSH为什么被广泛应用的原因。
分类
- Min-Hash：使用Jaccard系数度量数据相似度
- P-stable Hash：使用欧氏距离度量数据相似度
- E2LSH：P-stable LSH在欧氏空间的一种随机化实现方法
- PM_LSH
- LSB-tree
- C2LSH
- SimHash
Min-Hash
hash函数的选择
了解min-hash之前，首先需要了解一下Jaccard系数的概念。Jaccard系数主要用来解决的是非对称二元属性相似度的度量问题，常用的场景是度量2个集合之间的相似度，公式这里我不写了，就是2个集合的交比2个集合的并。
首先，我们现在将上面这个word-document的矩阵按行置换，比如可以置换成以下的形式：
可以确定的是，这没有改变文档与词项的关系。现在做这样一件事：对这个矩阵按行进行多次置换，每次置换之后，统计每一列（其实对应的就是每个文档）第一个不为0的位置（行号），这样每次统计的结果能构成一个与文档数等大的向量，这个向量，我们称之为签名向量。
比如，如果对最上面的矩阵做这样的统计，得到[1,2,1,2]，对于下面的矩阵做统计，得到[1,1,2,1].
简单来想这个问题，就拿上面的文档来说，如果两个文档足够相似，那也就是说这两个文档中有很多元素是共有的，换句话说，这样置换之后统计出来的签名向量，如果其中有一些文档的相似度很高，那么这些文档所对应的签名向量的相应的元素，值相同的概率就很高。
我们把最初始时的矩阵叫做input matrix，由m个文档，n个词项组成。而把由t次置换后得到的一个t×m的矩阵叫做signature matrix.
图中，4个文档，做了3次置换，得到了一个3 x 4的签名矩阵。
需要注意的是，置换矩阵的行，在代码实现的时候，可以用这样的算法实现：
在当下剩余的行中（初始时，剩余的行为全部行），随机选取任意一行，看看这一行哪些位置（这里的位置其实是列号）的元素是1，如果签名向量中这个位置的元素还未被写入，则在这个位置写入随机选取的这个行的行号。并将这一行排除。
持续进行1步的工作，直到签名向量全部被写满为止。
以上2步的意义跟对整个矩阵置换、再统计，结果是一样的。这么说可能有点抽象，我把函数放在下面：
def sigGen(matrix):
"""
* generate the signature vector
:param matrix: a ndarray var
:return a signature vector: a list var
"""
# the row sequence set
seqSet = [i for i in range(matrix.shape[0])]
# initialize the sig vector as [-1, -1, ..., -1]
result = [-1 for i in range(matrix.shape[1])]
count = 0
while len(seqSet) > 0:
# choose a row of matrix randomly
randomSeq = random.choice(seqSet)
for i in range(matrix.shape[1]):
if matrix[randomSeq][i] != 0 and result[i] == -1:
result[i] = randomSeq
count += 1
if count == matrix.shape[1]:
break
seqSet.remove(randomSeq)
# return a list
return result
构造LSH函数族
为了能实现前面LSH定义中的2个条件的要求，我们通过多次置换，求取向量，构建了一组hash函数。也就是最终得到了一个signature matrix. 为了控制相似度与映射概率之间的关系，我们需要按下面的操作进行，一共三步。
(1) 将signature matrix水平分割成一些区块（记为band），每个band包含了signature matrix中的r行。需要注意的是，同一列的每个band都是属于同一个文档的。如下图所示。
(2) 对每个band计算hash值，这里的hash算法没有特殊要求，MD5，SHA1等等均可。一般情况下，我们需要将这些hash值做处理，使之成为事先设定好的hash桶的tag，然后把这些band“扔”进hash桶中。如下图所示。但是这里，我们只是关注算法原理，不考虑实际操作的效率问题。所以，省略处理hash值得这一项，得到每个band的hash值就OK了，这个hash值也就作为每个hash bucket的tag。
(3) 如果某两个文档的，同一水平方向上的band，映射成了同一hash值（如果你选的hash函数比较安全，抗碰撞性好，那这基本说明这两个band是一样的），我们就将这两个文档映射到同一个hash bucket中，也就是认为这两个文档是足够相近的。
好了，既然执行的是上面三步的操作，那不难计算出两个文档被映射到同一个hash bucket中的概率：
不难看出，这样的设计通过调节参数值，达到了“越相似，越容易在一个哈希桶；越不相似，越不容易在一个哈希桶”的效果。这也就能实现我们上边说的LSH的两个性质。
画出了在r=5,b=20参数环境下的概率图:
当相似度高于某个值的时候，概率会变得非常大，并且快速靠近1，而当相似度低于某个值的时候，概率会变得非常小，并且快速靠近0.
另外， 需要注意的是，每一层的band只能和同一层的band相比，若hash值相同，则放入同一个哈希桶中。
代码实现：MinHash
P-stable Hash
最开始的时候，我们已经说过，不同的相似度判别方法，对应着不同的LSH，那对于最常见的Lp范数下的欧几里得空间，应该用怎样的LSH呢？这就要介绍P-stable hash了。
P-stable distribution
在了解P-stable hash之前，先了解一下p稳定分布的概念。
P-stable 分布构造LSH函数族
hash函数族：
当r的值取定的时候，这个公式可以看做是一个仅与c的取值相关的函数。c越大，函数值越小（碰撞的概率越低）；c越小，函数值越大（碰撞的概率越高）。
选取合适的r值，能够使得尽可能地小。
P-stable 分布LSH相似性搜索算法
上面完成了对p-stable 分布LSH函数族构造。那么接下来的问题是怎样具体实现hash table的构造以及查询最近邻。
我们构建hash table的过程就是要用这个函数族的每一个函数对每一个向量执行hash运算。为了减少漏报率False Negative（就是本来很相近的两条数据被认为是不相似的），一种解决方案是用多个hash函数对向量执行hash运算。
但是，现在有一个问题，那就是上面这种做法的结果，确实减少了漏报率，但与此同时，也增加了误报率（本来不很相近的两条数据被认为是相近的）。所以，需要在上面方法的基础上，再增加一个措施。我们从LSH函数族中，随机选取L组这样的函数组，每个函数组都由k个随机选取的函数构成，当然L个函数组之间不一定是一样的。现在这L组函数分别对数据处理，只要有一组完全相等，就认为两条数据是相近的。
通过这两个新建的函数，我们可以将hash table的构建步骤作以下详细说明：
代码实现：E2LSH
E2LSH
欧氏局部敏感哈希(E2LSH，Exact Euclidean locality sensitive Hashing)是 P-stable LSH在欧氏空间的一种随机化实现方法，其基本原理是：利用基于p-稳定分布的位置敏感函数对高维数据进行降维映射，使原始空间中距离很近的两个点经映射操作后依然很近。
一组哈希函数的情况
为拉大距离近的点与距离远的点经映射后碰撞概率之间的差距，E2LSH 常将 k 个 p-stable LSH 哈希函数联合使用。
对每个形式为 k 元组的桶标号 a，使用如下两个哈希函数 H1 和 H2 计算得到两个值：
- 其中 H1 的值是数组中的位置，数组的大小也就相当于是哈希表的大小。
- 其中 H2 的值作为 k 元组的代表，链接到对应 H1 数组位置的链表中。
H1 和H2 的具体形式如下：
索引构建过程：
查询过程如下：
多组哈希函数的情况
在构建索引时，对数据集中的每个数据点 v，计算其 L个哈希函数的值，并将其存在 L个哈希表对应的哈希桶内。
SimHash
simhash是google于2007年发布的一篇论文《Detecting Near-duplicates for web crawling》中提出的算法，初衷是用于解决亿万级别的网页去重任务，simhash通常用于长文本，通过降维处理，将长文本压缩至几个关键词来代表一篇文章，然后再将这些关键词编码成一个固定长度的二进制字符串（一般为32位或是64位），这样即用一个固定长度的编码来表示一整篇文章，我们想要对比多篇文章，只需要对比这些固定长度的编码就可以了。
simhash作为locality sensitive hash（局部敏感哈希）的一种：
- 其主要思想是降维，将高维的特征向量映射成低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。
- 其中，Hamming Distance，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。也就是说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2。至于我们常说的字符串编辑距离则是一般形式的汉明距离。
如此，通过比较多个文档的simHash值的海明距离，可以获取它们的相似度。
算法流程
simhash算法分为5个步骤：分词、hash、加权、合并、降维，具体过程如下所述：
分词
- 给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。
hash
加权
在hash值的基础上，给所有特征向量进行加权，即W = Hash weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 1001014 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。权值的来源采用tf-idf：
合并
- 将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。
降维
- 对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。
应用
- 每篇文档得到SimHash签名值后，接着计算两个签名的海明距离即可。根据经验值，对64位的 SimHash值，海明距离在3以内的可认为相似度比较高。
- 海明距离的求法：异或时，只有在两个比较的位不同时其结果是1 ，否则结果为0，两个二进制“异或”后得到1的个数即为海明距离的大小。
举个例子，上面我们计算到的“CSDN博客”的simhash签名值为“1 0 1 0 1 1”，假定我们计算出另外一个短语的签名值为“1 0 1 0 0 0”，那么根据异或规则，我们可以计算出这两个签名的海明距离为2，从而判定这两个短语的相似度是比较高的。
换言之，现在问题转换为：对于64位的SimHash值，我们只要找到海明距离在3以内的所有签名，即可找出所有相似的短语。
但关键是，如何将其扩展到海量数据呢？譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢？
- 一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
- 大约需要四万多次的查询。
- 另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
- 大约需要占据4万多倍的原始空间。
这两种方案，要么时间复杂度高，要么空间复杂度复杂，能否有一种方案可以达到时空复杂度的绝佳平衡呢？答案是肯定的：
- 我们可以把 64 位的二进制simhash签名均分成4块，每块16位。根据鸽巢原理（也称抽屉原理），如果两个签名的海明距离在 3 以内，它们必有一块完全相同。如下图所示：
- 然后把分成的4 块中的每一个块分别作为前16位来进行查找，建倒排索引。
具体如下图所示：
如此，如果样本库中存有2^34（差不多10亿）的simhash签名，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本。
- 假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ，四个块返回的总结果数为 4* 262144 （大概 100 万）。
- 这样，原本需要比较10亿次，经过索引后，大概只需要处理100万次。
代码实现1： SimHash
代码实现2： SimHash_py
LSH with Cosine Distance
Source code
Here is the code for LSH based on cosine distance:
from __future__ import division
import numpy as np
import math
def signature_bit(data, planes):
"""
LSH signature generation using random projection
Returns the signature bits for two data points.
The signature bits of the two points are different
only for the plane that divides the two points.
"""
sig = 0
for p in planes:
sig <<= 1
if np.dot(data, p) >= 0:
sig |= 1
return sig
def bitcount(n):
"""
gets the number of bits set to 1
"""
count = 0
while n:
count += 1
n = n & (n-1)
return count
def length(v):
"""returns the length of a vector"""
return math.sqrt(np.dot(v, v))
if __name__ == '__main__':
dim = 20 # dimension of data points (# of features)
bits = 1024 # number of bits (planes) per signature
run = 10 # number of runs
avg = 0
for r in xrange(run):
# Generate two data points p1, p2
pt1 = np.random.randn(dim)
pt2 = np.random.randn(dim)
# reference planes as many as bits (= signature bits)
ref_planes = np.random.randn(bits, dim)
# signature bits for two data points
sig1 = signature_bit(pt1, ref_planes)
sig2 = signature_bit(pt2, ref_planes)
# Calculates exact angle difference
cosine = np.dot(pt1,pt2)/length(pt1)/length(pt2)
exact = 1 - math.acos(cosine)/math.pi
# Calculates angle difference using LSH based on cosine distance
# It's using signature bits' count
cosine_hash = 1 - bitcount(sig1^sig2)/bits
# Difference between exact and LSH
diff = abs(cosine_hash-exact)/exact
avg += diff
print('exact %.3f, hash %.3f, diff %.3f') %(exact, cosine_hash, diff)
print('avg diff = %.3f') %(avg/run)Output:
exact 0.477, hash 0.447, diff 0.062
exact 0.439, hash 0.454, diff 0.035
exact 0.433, hash 0.467, diff 0.077
exact 0.503, hash 0.522, diff 0.040
exact 0.583, hash 0.613, diff 0.052
exact 0.490, hash 0.494, diff 0.009
exact 0.563, hash 0.570, diff 0.014
exact 0.482, hash 0.479, diff 0.006
exact 0.506, hash 0.521, diff 0.029
exact 0.485, hash 0.479, diff 0.010
avg diff = 0.033The code has two important parameters:
dim - This is the dimension of data points which are the features. These are generated using NumPy’s random function:
pt1 = np.random.randn(dim) pt2 = np.random.randn(dim)We created two points to test the similarity.
bits - This is the number of bits (planes) per signature. The reference planes are generated as many as bits.
ref_planes = np.random.randn(bits, dim)These bits are used as signature bits for the points we are interested in their similarity. These signature bits of the two points are different only for the plane that divides the two points. as we can see from the function signature_bit():
sig = 0 for p in planes: sig <<= 1 if np.dot(data, p) >= 0: sig |= 1 return sig
We run the code several times to get averaged difference, and it’s because for each we’re testing with different points and different features.
时间复杂度