机器学习_相似度度量页PPT文档

机器学习中的相似性度量⽅法在机器学习和数据挖掘中，我们经常需要知道个体间差异的⼤⼩，进⽽评价个体的相似性和类别。

最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。

不同距离度量的应⽤场景根据数据特性的不同，可以采⽤不同的度量⽅法。

which one to use depends on what type of data we have and what our notion of similar is.各种“距离”的应⽤场景简单概括为，空间：欧⽒距离，路径：曼哈顿距离，国际象棋国王：切⽐雪夫距离，以上三种的统⼀形式:闵可夫斯基距离，加权：标准化欧⽒距离，排除量纲和依存：马⽒距离，向量差距：夹⾓余弦，编码差别：汉明距离，集合近似度：杰卡德类似系数与距离，相关：相关系数与相关距离。

距离度量公理Axioms of Distance Measures⼀般⽽⾔，定义⼀个距离函数 d(x,y), 需要满⾜下⾯⼏个准则：(即距离度量需要满⾜的性质)1) d(x,y) = 0 iff x = y // 到⾃⼰的距离为02) d(x,y) >= 0 // 距离⾮负3) d(x,y) = d(y,x) // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a4) d(x,k)+ d(k,y) >= d(x,y) // 三⾓形法则triangle inequality: (两边之和⼤于第三边)Note: iff = if and only if基础知识：熵与互信息[]⽂本相似度量⽅法⼀览此处的“⽂本”⼀词涵盖以下两个对象:1. 字符串/序列2. 包含较多⽂本内容的⽂档相关的度量⽅法可以分为两⼤类，各类下⾯再有⼀些具体的分类，⽐较常⽤的⽅法如见下图Note: lz这⾥LCS也可以认为就是编辑距离吧。

总的来说，⽂本相似度量⽅法可以分为两⼤类:1. String Based，即基于待⽐较的⽂本本⾝中的信息，该类⽅法评估的是”词法“上的相似性，或说朴素的相似性2. Corpus Based，即基于⼀个较⼤的⽂本集合中的信息，该类⽅法评估的是“语义”上的相似性[]欧⽒距离度量欧拉距离，来⾃于欧式⼏何，在数学上也可以成为范数。

数据挖掘之相似性度量机器学习或数据挖掘，就是在数据中寻求答案的算法。

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

大部分的数据建模方法都属于这两种：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) 求和。

或者，可以说，熵越大，信息量越大，一个概率较低的词，可能就是系统信息比较关键的词。

互信息：两个随机变量的相关/依赖程度，可以用来解释一个变量已知时，另外一个变量的不确定的变化。

在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。

最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。

根据数据特性的不同，可以采用不同的度量方法。

一般而言，定义一个距离函数 d(x,y), 需要满足下面几个准则：1) d(x,x) = 0 // 到自己的距离为02) d(x,y) >= 0 // 距离非负3) d(x,y) = d(y,x) // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a4) d(x,k)+ d(k,y) >= d(x,y) // 三角形法则: (两边之和大于第三边)这篇博客主要介绍机器学习和数据挖掘中一些常见的距离公式，包括：1.闵可夫斯基距离2.欧几里得距离3.曼哈顿距离4.切比雪夫距离5.马氏距离6.余弦相似度7.皮尔逊相关系数8.汉明距离9.杰卡德相似系数10.编辑距离11.DTW 距离12.KL 散度1. 闵可夫斯基距离闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：那么，闵可夫斯基距离定义为：该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。

假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：绿色的斜线表示欧几里得距离，在现实中是不可能的。

其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。

当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢？注意，当 p < 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p < 1, (0,0) 到 (1,1) 的距离等于 (1+1)^{1/p} > 2, 而 (0,1) 到这两个点的距离都是 1。

机器学习中的相似性度量在做分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement)，这时通常采用的方法就是计算样本间的“距离”(Distance)。

采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。

本文的目的就是对常用的相似性度量作一个总结。

本文目录：1. 欧氏距离2. 曼哈顿距离3. 切比雪夫距离4. 闵可夫斯基距离5. 标准化欧氏距离6. 马氏距离7. 夹角余弦8. 汉明距离9. 杰卡德距离&杰卡德相似系数10. 相关系数&相关距离11. 信息熵12. hausdorff距离13. Bhattacharyya距离1.欧氏距离(Euclidean Distance)欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。

(1) 二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离(2) 三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离(3) 两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的欧氏距离也可以用表示成向量运算的形式(4) Matlab计算欧氏距离Matlab计算距离主要使用pdist函数。

若X是一个M×N的矩阵，则pdist(X)将X矩阵M 行的每一行作为一个N维向量，然后计算这M个向量两两间的距离。

例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离X=［0 0 ; 1 0 ; 0 2］D=pdist(X,′euclidean′)结果：D=1.00002.0000 2.23612. 曼哈顿距离(Manhattan Distance)从名字就可以猜出这种距离的计算方法了。

想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。

实际驾驶距离就是这个“曼哈顿距离”。

而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Block distance)。