数据挖掘基础知识

相似性和不相似性

• 相似性：数值越大越相似，取值在 [0, 1] 之间。
• 不相似性：越小越相似，最小的不相似性取值为 0。
• 接近性：相似性或不相似性。

对于 p 和 q 两个对象的属性值，有：

属性类型	不相似性	相似性
Nominal	$d = \left\{ \begin{array}{lr}0 & if\space p = q\\1 & if\space p \neq q\end{array}\right.$	$s = \left\{ \begin{array}{lr}1 & if\space p = q\\0 & if\space p \neq q\end{array}\right.$
Ordinal	$d=\frac{\vert p-q \vert}{n-1}$	$s=1-\frac{\vert p-q \vert}{n-1}$
Interval/Radio	$d=\vert p-q \vert$	$s=-d,s=\frac{1}{1+d},s=1-\frac{d-min_d}{max_d-min_d}$

欧几里得距离

$dist = \sqrt{\sum_{k=1}^n(p_k-q_K)^2}$

如果尺度不同需要标准化。

契诃夫距离

$dist = (\sum_{k=1}^n|p_k-q_K|^r)^\frac1{r}$

r 不同的含义不同：

• $r = 1$, 曼哈顿距离
• $r = 2$, 欧几里得距离
• $r \rightarrow \infty$, 上确界距离

马氏距离

$s(p,q)=(p-q)\Sigma^{-1}(p-q)^T$

其中 $\Sigma$ 是数据的协方差矩阵。

余弦相似度

$cos(d_1,d_2) = \frac{d_1 \cdot d_2}{||d_1||\space||d_2||}$

扩展的杰卡德系数(Tanimoto)

$T(p,q)=\frac{p\cdot q}{\|p\|^2+\|q\|^2-p\cdot q}$

当属性为二元属性时退化为杰卡德系数

相关性

$p_k^{'}=\frac{(p_k-mean(p))}{std(p)}$

$q_k^{'}=\frac{(q_k-mean(q))}{std(q)}$

$correlation(p, q) = p^{'}\cdot q^{'}$

组合相似性

$\delta_k=\left\{ \begin{array}{lr} 0 \\ 1 & otherwise \end{array} \right.$

当第 k 个属性是二元非对称属性且取值都为 0 时、或值缺失时 $\delta_k$ 为 0 否则为 1.

$similarity(p,q)=\frac{\sum^n_{k=1}\delta_ks_k}{\sum^n_{k=1}\delta_k}$

也可以考虑不同的权重

$similarity(p,q)=\frac{\sum^n_{k=1}w_k\delta_ks_k}{\sum^n_{k=1}\delta_k}$

$distance(p,q)=\left(\sum_{k=1}^nw_k\vert p_k-q_k\vert^r\right)^\frac{1}{r}$

欧几里得密度

基于 cell 的方法直接计算每个格子当中的点的个数：

基于中心的方法计算一个点周围一个具体半径中的点的个数。

---

• ← Previous Post
• Next Post →