机器学习或数据挖掘，就是在数据中寻求答案的算法。

而寻求的答案就是训练完成的数据模型。

大部分的数据建模方法都属于这两种：

1） 数据汇总，对数据进行 简洁的近似描述

如pagerank、聚类

2） 特征抽取

如频繁项集（同时频繁出现的元素子集）、相似项（共同元素比例较高的集合对）

在机器学习或数据挖掘之前，还需要概率，或信息论的一些相关知识，现实世界的对象需要转换为计算机的度量方式。

1. TF.IDF

2. 熵的相关概念

3. 相似度的度量及计算

4. 对文本相似度的分析

5. 局部敏感Hash的分析LSH

6. 查找相似项的处理流程

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）<<0，则两个事件X，Y 互补分布。

交叉熵： 随机变量X的分布p（x）未知，则通过统计手段估计出X的近似分布q（x），则随机变量的交叉熵为H（x, q） = -求和p * log（2，q），H(X,q) >= 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集合的相似度时，普通的遍历算法复杂度为N^2, 而采用排序的遍历算法，最优的复杂度也为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个连续字符，集合空间的大小为27^k，集合空间要保证足够大，这样每个字符串的出现概率比较低，信息熵就比较大。所以k的大小与文本的类型相关，若是邮件类，5个连续字符比较合适，若是论文类大文档，9个连续字符比较合适。另外，还有基于词的shingle，在停用词加上后续的两个连续词，形成一个有用的shingle。

字符串shingle的压缩： 将一个k-shingle字符串，通过hash函数，映射到一个4字节整型数，或者说，这个整数就是这个字符串的索引。整数空间的大小为2^32 - 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 - s^r) ^ p，不相似的文档，被选为候选对的概率，任何行条内，至少有一个行条内，一对签名列 相等的概率

伪反例 概率： (1 - s^r) ^ 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 - s^r) ^ p

t 就成为了分类的阈值，这个函数跟 逻辑回归函数logistic regression function很相像。sigmoid（或tanh）函数。
最小hash函数族，就是LSH的一个具体的函数族，这些函数组合在一起，如条行化技术，来区分不同相似度文档的归类。

若定义Jaccard的距离 为 = 1 - Jaccard相似度。则上图的横轴度量方式，就会左右反转。

横轴是 Jaccard距离d，而竖轴是分配到一个位置/桶内的概率。

局部敏感函数族每个函数都需满足以下的条件是：

1). 如果d(x,y) < d1，那么哈希家族H中的哈希函数h满足h(x) = h(y)的概率至少是p1.

2). 如果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）检查每个候选对的签名，确定他们的相似度是否大于阈值t

7）若大于阈值t，直接检查文档本身，看它们是否真的相似。

7. 几种距离度量方式

1）几何距离 d(x, y)，范式的定义：

L2 : d(x,y) 是平方和的开方，又称欧式距离

L1 : d(x,y) 是每个维度的距离之和 ，又称曼哈顿距离

L∞ : d(x,y) 是x和y在每个维度上距离的最大值

2）非几何距离

Jaccard距离：1 - jaccard度量

余弦距离：两个向量的夹角

编辑距离：LCS，最大公共子串相关，由一个串转变为另一个串，所需变换次数

海明距离：两个向量中不同分类的个数，这个常用二进制度量