之前写过一篇距离与相似性度量的blog，这里添加两个少见的相似性度量方法，并且再扩展一些东西。

之前的blog： http://blog.csdn.net/ice110956/article/details/14143991

Tanimoto 系数

Tanimoto系数由Jaccard系数扩展而来。首先引入Jaccard系数。

Jaccard系数

两个特征向量A,B，如果其值都是0,1的二值数据，那么有一个简单的判定相似性的方法：

F00 = A中为0并且B中也为0的个数

F10 = A1 B0的个数

F01 = A0 B1的个数

F11 = A1 B1 的个数

那么可以定义这么一个similarity：

这叫做（simplematch coefficient）SMC，简单匹配系数。

很多情况下，两个向量中，0的个数会大大多于1的个数，也就很稀疏，类不平衡。这时候不同向量之间的SMC会因为过多出现的0而没有效果。

那么我们可以只考虑F11，得到：

这也就是Jaccard距离。

如果把两个向量看作两个集合，0为此元素不存在，1为此元素存在，那么Jaccard距离就是很好地比较两个集合相似性的度量方法。在集合的相似度计算中，Jaccard距离可以写成：

扩张Jaccard

如果这个时候，还是很稀疏，但是值是非二值的，该怎么办？

一种简单的方法就是用cosine距离：

cosine距离是处理稀疏非二值特征的很好的选择。

但是，我们还想以Jaccard距离的思维来做又要如何？如下：

如果我们的x,y都是二值向量，那么如上公式就会得到Jaccard距离。

分子项，只有两个均非0才会有非0的有用结果，类似于F11，不过这里不是简单的计数，而是用数乘来表示。

分母项，2范数表示大小，也只有非0的项才有贡献，再减去xy即共同的，这个类似

以上是通过观察得出的结论，具体推导不知。

SMC距离在一般的非不平衡二值问题上计算应该比较方便。

Jaccard在文本分类等不平衡二值问题上有所作为

Tanimoto的话，没用过，效果不知道有没有cosine好。应该会得到一个类似cosine的结果。

Bregman 散度距离

（BregmanDivergence）

形式如下：

其中为某个凸函数，表示函数对y求导，<>表示点乘。

我们把y=x^2作为，得到：

即得到欧式距离。

Bregman距离的数学性质及推导不知，wiki上说，其为许多常见距离的一个通式。

wiki http://en.wikipedia.org/wiki/Bregman_divergence

其中包括欧式距离，曼哈顿距离，KL距离等等。水平有限，只能引用到此。

mahalanobis距离

马氏距离：

首先考虑欧式距离，欧式距离有两点明显的缺点：

1.把不同量纲级别的属性同等看待

比如一个特征向量包含人的年龄，收入，那么收入得到的点乘会远远大于年龄，使得年龄没有作用。

一般的做法是归一化属性值。

2.属性间相关性

一个人的体重很多时候正比于身高。如果作为特征中的两个属性，就会重复计算这个值，得到冗余信息。

一种做法是做去相关，降维，特征选择等等。

不同与欧式距离，马氏距离考虑了量纲即属性间相关性。如下：

M(x,y)=(x-y)sigm(x-y)T

其中sigm表示整体特征向量的协方差矩阵。

马氏距离的最大缺点就是计算复杂度要高出很多，具体运用时要考虑这个因素。

补充

补充之前距离没写到的一些信息：

转换 transformation

有时候，我们得到了距离，进而可以用这个距离求相似性。如：

s表示相关性，d表示距离，则有：

s = -d

s=1/(1+d) 这种方法把距离映射到（0-1）的相似性空间中

s=e^-d      这种方法为非线性映射

s = 1-(d-mind)/(maxd-mind)  也是一种把距离映射到（0-1）上的方法，不过这种是线性的。

小结：任意一种递减的函数都可以把d映射为s度量

归一化normalization

像cosine这种，本身就是（-1,1）的数据，可以直接使用。不过很多情况下，如欧式距离，range都无从控制。归一化是必须的。

度量（metric）

满足以下几种性质的量，可以成为度量（metric）：

非负性

（a）d(x,y)>=0  

（b）d(x,y)=0 if x==y 

对称性

d(x,y) = d(y,x) for all x,y

三角性

d（x,z）<= d(x,y) + d(y,z)

metrics对于许多算法是必须的，不过很多情况下，不必满足metrics也可以作为距离度量。

有再看到类似的再更新。