数据挖掘之相似性度量

数据挖掘之相似性度量机器学习或数据挖掘，就是在数据中寻求答案的算法。而寻求的答案就是训练完成的数据模型。大部分的数据建模方法都属于这两种：1） 数据汇总，对数据进行 简洁的近似描述如pagerank、聚类2） 特征抽取如频繁项集（同时频繁出现的元素子集）、相似项（共同元素比例较高的集合对）在机器学习或数据挖掘之前，还需要概率，或信息论的一些相关知识，现实世界的对象需要转换为计算机的度量方式。1. TF.IDF2. 熵的相关概念3. 相似度的度量及计算4. 对文本相似度的分析5. 局部敏感Hash的分析LSH6. 查找相似项的处理流程7. 几种距离度量方式相关知识：1. TF.IDF文本分类时，一个重要指标：TF.IDF，分为两个阶段： 同一文档中的统计；以文档为粒度，所有文档的统计。TF： term frequency 词项频率，同一篇文档中，所有词项出现频率的归一化IDF：inverse document frequency 逆文档频率，所有文档数目，与某一词出现的文档的数目的比率关系其中的关系：不仅仅是一个公式，里面包含了信息论中熵的概念。IDF就是一个特定条件下关键词的概率分布的交叉熵。应用了对数运算。2. 熵的相关概念熵，表示信息量的大小，与概率相关。随机 变量的不确定性越大，即概率小，其熵也就越大，将其搞清楚，所需的信息量也就越大。 -Pi * log(2, Pi) 求和。一个系统越混乱，则每个变量的概率越小，其熵也就越大。信息论在通信编码的表示也是一样的，一个变量，在系统中的概率越小，其编码也就越长，因为短的编码要留给概率大的变量。即熵越大，其编码也就越长，这样压缩的效率就比较高。发送一段信息，其需要的编码长度（二进制），也就是 -Pi * log(2, Pi) 求和。或者，可以说，熵越大，信息量越大，一个概率较低的词，可能就是系统信息比较关键的词。互信息：两个随机 变量的相关/依赖程度，可以用来解释一个变量已知时，另外一个变量的不确定的变化。即不确定信息的减少量。自信息：一个随机变量（信源）发出的信息，这个信息所带来的信息量的度量。一次事件发生的提供的信息量-log(2, Pi)，有时与熵的含义相同（当事件只发生一次时）。而熵是平均信息量，所有自信息的期望。当信息确定时，确定场（无随机性）的熵最小。 等概场的熵最大。熵率：又称字符熵、词熵。信息量的大小随着消息长度的增加而增加。-（1/n）（求和Pi*log(2, Pi)）联合熵：同联合分布函数的形式类似，联合随机变量所表示的平均信息量（期望）。H(x, y) = -求和P(x,y) log(2, P(x, y)条件熵：H(y|x) = -求和P(x,y) log(2, P(y|x)联合熵 = 条件熵 + 单变量熵, H(x, y) = H(y|x) + H(x)互信息的熵 I (x; y) = H(x) - H(y | x) = H(y) - H(y|x), 描述了X中 包含有多少Y的信息量，或者是Y中包含了多少X的信息量。当X, Y相互独立，则其互信息为0. 当I(x; y) 0，则两个事件X,Y高度相关；当I（x; y）= H(X)相对熵：Kullback-Leibler divergence，K-L发散度，K-L距离D(p | q) = H(p, q) - H(p)。用来描述 当概率密度函数估计有偏差错误时，增加的信息量有多少。因为概率分布的类型，可能会估计错误，如均匀分布，被估计成高斯/正态分布。两个分布的差异，带来的信息量差别。3. 相似度的度量和计算Jaccard 度量：A, B两个集合，其相似性为： (A交B) / (A并B), 其值域为0, 1而直接求解A，B集合的相似度时，普通的遍历算法复杂度为N2, 而采用排序的遍历算法，最优的复杂度也为N*(logN).如何获取更好的性能计算那？可以采用minHash的方法。其定义为：已知一个hash函数h(x)，具有良好的均匀性，一个集合S, 集合内所有元素，经过hash之后，得到最小hash值的那个元素。hash函数，A、B相同的元素，必定都会hash散列到一个位置/桶内。若minHash(A) = minHash(B)，则说明A, B同时包含最小hash值的那个元素，即这个元素必定是A，B共同的集合。而P (minHash(A) = minHash(B): 两个minHash值相等的概率 等于 A, B的相似度 Jaccard度量。从统计上来讲，二者是无偏估计的关系，但若只选取一个值，方差就显得过高，可以选取多个值，即多个样本。过程推导？ .而计算概率P (minHash(A) = minHash(B) ，可以采用采样的方法，对样本进行统计，然后近似估计。这样利用统计的方式进行理解minHash，后面就简单多了。如何生成minHash的样本？有两种方式：1. 选取多个hash函数，而且hash函数之间尽量相互独立，如k个，每个集合就会有k个minHash的样本；2. 选取一个hash函数，而对每个集合只需选取k个 最小hash值的元素。 第一种方法的计算复杂度相对较高，若集合元素有N个，则需要k*N次运算，而第二种只需对集合遍历一次。利用抽样的数据，估计P (minHash(A) = minHash(B) ，若minHash后，由A计算的新集合为A1, B计算出的新集合为B1，其相似度 （A1交B1） / （A1并B1）。而且，由统计学的大数定律，此时估计的期望误差上界为O(1/k)。最小hash的应用场景： web文档中的聚类，消除 重复近似；或者侦测web网页欺诈；电子文档剽窃检测方法；关联规则的学习工具。4. 文本的相似度分析文本的分割shingle: 将长的文本分割成小的、连续的字符串集合，如连续k个字符。可以做些预处理，去掉空字符，或将连续空字符替换为一个空字符。另外，k大小的选择，k个连续字符，集合空间的大小为27k，集合空间要保证足够大，这样每个字符串的出现概率比较低，信息熵就比较大。所以k的大小与文本的类型相关，若是邮件类，5个连续字符比较合适，若是论文类大文档，9个连续字符比较合适。另外，还有基于词的shingle，在停用词加上后续的两个连续词，形成一个有用的shingle。字符串shingle的压缩： 将一个k-shingle字符串，通过hash函数，映射到一个4字节整型数，或者说，这个整数就是这个字符串的索引。整数空间的大小为232 - 1，当有9个连续字符shingle，其数目就比整数的表示空间大了。特征矩阵：列是集合空间的全集，行是各个文本集合。矩阵中各个元素，就是每个集合是否在指定文本中出现。 这些个矩阵，往往非常稀疏，大部分元素都为0.排列转换：对特征矩阵的行号重新排列。与最小hash的关系？ 重新排列后，指定的hash函数是，由上到下依次扫描，第一个非零的元素对应的集合值。重新排列，需要大量运算来改变原矩阵，若不改变原矩阵，也可以计算每列的minHash值。最小hash签名：应用多个排列转换，然后在每个排列转换下计算每列集合的最小哈希值，这些最小哈希值序列就可以构成集合的最小哈希签名。如何证明 两个集合 之间的 minhash签名 就是 Jaccard相似度 的无偏估计。由于不可能进行排列转换，所以采用另外一个方法来模拟，即minHash的方式，选取一个随机hash函数，对所有的数据进行hash散列操作，并选取最小hash值，看做是集合的最小hash值。5. 文档的局部敏感hash算法LSH：问题描述： minHash签名解决一个文档的表示，而当文档的数目巨大时，如文档有500万个，如何解决两两比较的问题？做法1：将每个文档进行多次hash，然后将hash到同一位置(桶)的文档看做具有相似性的候选对，这样只对比 候选对的文档，对于其他的，无需检查。为什么要多次hash？因为一次的hash，不一定能把相似的文档映射到一个位置/桶中去。做法2：若目标有minhash签名，就将签名矩阵行条化。 首先将签名矩阵按行划分为b个行条，每个行条由r行组成，这样每个行条每列就有r个整数组成列向量，当任一行条内，两个文档的hash签名向量相等，就认为这个两个文档相似。若两文档相似度为s（即一行内，两个hash签名相同的概率为s）时，则：伪正例 概率： 1 - (1 - sr) p，不相似的文档，被选为候选对的概率，任何行条内，至少有一个行条内，一对签名列 相等的概率伪反例 概率： (1 - sr) p, 相似的文档，没有被选为候选对，即任何行条内，一对签名列都不相等的概率，如r=4，b=20，s=80时，3000个文档中会出现一个伪反例（相似的文档没有选为候选对）极限情况：b = 1 时，即两个集合的hash签名都必须相等，阈值t为1，对相似度的要求非常严格，但可能会造成伪反例的增多。r = 1 时，即只需两个集合中任一对签名相等即可，阈值t为1/b，对相似度的要求很宽松，但可能会造成伪正例的增多。阈值t的作用是什么？阈值应该就是代表相似度，相似度大于t的，则这个文档应该是同类，小于t的，则这篇文档应该不是同类。S函数的斜度，对hash的影响是什么？斜率越高，对文档里有中间相似度的区分能力就越好，否则，相似度不好不坏的文档就没发归类或者hash，伪正例，或伪反例就会增多。如何选取好的S函数？横轴为相似度s，竖轴为分配到一个桶内的概率，如1 - (1 - sr) pt 就成为了分类的阈值，这个函数跟 逻辑回归函数logistic regression function很相像。sigmoid（或tanh）函数。最小hash函数族，就是LSH的一个具体的函数族，这些函数组合在一起，如条行化技术，来区分不同相似度文档的归类。若定义Jaccard的距离 为 = 1 - Jaccard相似度。则上图的横轴度量方式，就会左右反转。横轴是 Jaccard距离d，而竖轴是分配到一个位置/桶内的概率。局部敏感函数族每个函数都需满足以下的条件是：1). 如果d(x,y) d2，那么哈希家族H中的哈希函数h满足h(x) = h(y)的概率至多是p2.且d2 d1。是一个递减的过程。为了增加区分度，应该尽量增大p1，p2之间的距离（d1,d2固定时），及d1，d2之间的空间（p1,p2固定时）。行条化，其实也可以看做是一个hash函数族进行 串联 加 并联的结果。一个行条内，是串联形式。而每个行条的结果，再形成并联的形式。6. 查找相似项的处理流程1）对每篇文档进行分解，构建k-shingle集合，并将k-shingle字符串集合映射到 整数空间内，或者更短的桶内2）将文档-shingle对 按照shingle排序3）选择 minHas签名的长度n，计算2中所有文档的minHash签名4）选择阈值t，定义要配对的相似度，然后选择行条数和行条内行数。b*r = n，t = (1/b)(1/r)5）计算候选对6）检查每个候选对的签名，确定他们的相似度是否大于阈值t7）若大于阈值t