一、基础概念
1. 相似度(similarity): 两个对象相似程度的数值度量，通常相似度是非负的，在[0,1]之间取值
相异度(disimilarity): 两个对象差异程度的数值度量，通常也是非负的，在[0,1]之间取值，0到$\infty$也很常见
我们使用邻近度(proximity)表示相似度或者相异度: 常见的邻近度有：相关，欧几里得距离，Jaccard相似性，余弦相似性. 前两者适用于时间序列这样的稠密数据，后两者适用于文本这样的稀疏数据.
2. 区间变换: d' = (d-dmin_d)/(max_d - min_d)
3. 具有以下三个性质的测度称为度量(metric)
(1) 非负性
(2) 对称性
(3) 三角不等式
二、常见相异度和相似性度量函数
1. 距离Minkowski distance
$$d(x,y) = (\sum_{k=1}^N| x_k - y_k |^r)^{1/r}$$
1-normal distance/Manhattan distance: $\sum_{i=1}^n|x_i - y_i|$
2-normal distance/Euclidean distance: $(\sum_{i=1}^n|x_i - y_i|^2)^{1/2}$
p-normal distance: $d(x,y) = (\sum_{k=1}^N| x_k - y_k |^p)^{1/p}$
$\infty$-nromal distance/Chebyshev distance: $lim_{p \rightarrow \infty} (\sum_{k=1}^N| x_k - y_k |^p)^{1/p}$
2. 简单匹配系数(Simple Matching Coefficient): SMC = 值匹配属性个数/属性个数 = $ \frac{f_{11} + f_{00}}{f_{01} + f_{10} + f_{11} + f_{00}} $
3. Jaccard系数 J = 匹配个数/属性个数 = $\frac{f_{11}}{f_{01} + f_{10} + f_{11}} $
4. 余弦相似度 $cos(x,y) = \frac{x \cdot y}{||x|| ||y||}$(文档相似度中最常用的度量)
5. 广义Jaccard系数/Tanimoto系数
6. 相关性
Pearson's correlation: $corr(x,y) = \frac{cov(x,y)}{std(x)*std(y)} = \frac{s_xy}{s_x s_y}$
7. Bregman散度
$D(x,y) = \phi(x) - \phi(y) <\Delta \phi(y),(x-y)> $