一、基础概念
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 ightarrow 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)> $