《Data Mining》学习——度量数据的相似性和相异性

1.标称属性的邻近性度量

设一个标称属性的状态数目是M。这些状态可以用字母，或者一组数字来表示，并且这些数字只代表数据标号，并没有特定的顺序。
如何计算标称属性所刻画的对象之间额相异性？
两个对象i和j之间的相异性可以跟据不匹配率来计算：

$$d(i,j)=\frac{p-m}{p}$$
其中，m是匹配数目（i和j取值相同的属性数目），p是指总的属性数目。可得相似性计算如下：
$$sim(i,j)=1-d(i,j)=\frac{m}{p}$$

2.二元属性的邻近性度量

对于对称的二元属性，每个状态都要一样重要，对于二元属性的相异性称为对称的二元相异性。对于对象i，j用二元属性刻画，则i和j的相似性为：

$$d(i,j)=\frac{r+s}{q+r+s+t}$$
对于字母所代表的的意义，我们得出一个两行两列的列行表：

状态	1	0	sum
1	q	r	q+r
0	s	t	s+t
sum	q+s	r+t	p

其中q是对象i，j都取1的属性数，r是在对象i中为1，在对象j中为0的属性数，依次类推…
由互补原理可以得出对称的二元相似性为：

$$sim(i,j)=1-d(i,j)$$
对于 非对称的二元相似性可在图上表格中加入权志计算，也就是出现相同的数目乘以他的权计算。

3.数值属性的相异性：闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）是欧几里得距离和曼哈顿距离的推广，定义如下：

$$d(i,j)=\sqrt[h]{|x_{i1}-x_{j1}|^h+|x_{i2}-x_{j2}|^h+...+|x_{ih}-x_{j h}|^h}$$
其中，h是实数，h $\geq$1（这种距离也被称为 $L_{p}$范数），其中p就是指h。当p=1时，它表示 曼哈顿距离（ $L_{1}$范数）;当p=2时表示 欧几里得距离（ $L_{2}$范数）。
特别的当h趋近无穷时(h-> $\infty$)，称为 上确界距离（ $L_{max}$范数，$L_{\infty}$范数或者 切比雪夫距离）：
$$d(i,j)=\lim_{n \rightarrow \infty} (\sum_{f=1}^p |x_{if}-x_{jf}|^h)^\frac{1}{h}=max|x_{if}-x_{jf}|$$
$L_{\infty}$范数又称 一致范数。

4.序数属性的邻近距离

序数属性的值之间具有有意义的排位或者顺序。序数属性也可以通过把数值属性的值域划分为有限各类别，对数值属性离散化得到。
如何处理有序数属性？在计算数值相异性时，序数属性的处理与数值相似。假如f是用于描述n个对象的一组序数属性之一。关于f的相异性计算涉及如下步骤：

1. 第i个对象的f值为$x_{if}$,属性f有$M_{f}$个有序的状态，表示排位1，…，$M_{f}$。对应的排位$r_{if}\in\{ 1,..M_{f}\}$取代$x_{if}$。
2. 由于每个序数属性都可以有不同的状态数，所以通常要映射的[0.0，1.0]上，以便每个属性都有相同的权重。
   $$z_{if}=\frac{r_{if}-1}{M_{f}-1}$$
3. 相异性则与数值属性算法相似。

5.混合类型属性的相异性

复杂公式不写了！
理解出来大体就是：

1. 数值属性：$\frac{x_{if}-x_{if}}{max_{h}x_{hf}-min_{h}x_{hf}}$
2. 标称或二元属性：相等为0，否则为1
3. 序数属性：计算排位，映射之后，当做数值属性计算

求得所有属性的相异性之后，对所有对象的相异性求平均。

6.余弦相似性

余弦相似性是一种度量，它可以用来比较文档，或者针对给定的查询词向量对文档进行排序。
令x，y为比较向量：

$$sim(x,y)=\frac{x.y}{||x||*||y||}$$

||x||代表了欧氏距离，x.y为向量点乘。
当属性是二元属性时，余弦相似性的一个简单变种：

$$sim(x,y)=\frac{x.y}{x.x+y.y-x.y}$$

x.y是x和y共同具有的属性数，而|x| |y|是x具有的属性数与y具有的属性数的几何平均。于是，sim（x，y）是公共属性相对拥有的已中度量。
这样得出x和y所共有属性个数与x或y所具有的的属性个数之间的比率，这个函数被称为Tanimoto系数或者距离。

7.总结

1. 相似度与相异度的度量在不同类型的属性中方法有差异，主要来源于数据意义的象征。
2. 对于混合属性的相似度度量要统一权值。
3. 相似度或者相异度测量提供了事物分类的手段。