本文讲解的概念： 范数
赋范线性空间
向量的范数，矩阵的范数
测度
拓扑等价
几种机器学习常用的距离

范数

范数(norm)是一个类似“长度”概念的函数

范数的严格定义如下：

赋范线性空间

若X是数域上的线性空间，泛函$\mid \mid \cdot \mid \mid \to R$ 满足：
(1)正定性：$|x|\ge 0$，且$|x|=0\Leftrightarrow x=0$；
(2)正齐次性：$|cx|=|c||x|$ ；
(3)次可加性（三角不等式）：$|x+y|\le|x|+|y|$ 。
那么，$|\cdot|$称为X上的一个范数。

向量的p-范数

p-范数是范数的一种，是比较常用的一类距离的度量方法。
需要注意的是，矩阵的p-范数与向量的p-范数是不同的

• p-norm $\mid \mid X \mid \mid_p = (\sum\limits_{i=1}^N \mid x_i \mid^p)^{1/p}$

从p-norm可以推导出一些常用的范数(norm)

• 0-norm $\mid \mid X \mid \mid_0 =N$，也就是向量的维度
• 1-norm $\mid \mid X \mid \mid_1 = (\sum\limits_{i=1}^N \mid x_i \mid)$，也就是X的各个元素绝对值之和
• 2-norm $\mid \mid x \mid \mid_2 = (\sum\limits_{i=1}^N \mid x_i \mid^2)^{1/2}$，我们常见的Euclidean范数，或Frobenius范数
• $\infty$-norm , p-norm中的p求极限，结果是X各个元素绝对值中的中的最大值$\mid \mid x \mid \mid_\infty = \max \mid x_i \mid$
• $- \infty$-norm ,p-norm中的p求极限，结果是X各个元素绝对值中的最小值$\mid \mid x \mid \mid_{-\infty} = \min \mid x_i \mid$

矩阵的范数

• 1-norm $\mid \mid A \mid \mid_1 =\max\limits_j \sum\limits_{i=1}^m \mid a_{ij}\mid $，列和范数，是矩阵列向量绝对值之和的最大值。
• 2-norm $\mid \mid A \mid \mid_2 =\max\sqrt{\lambda_1} $，$\lambda_1$是$A^T A$的最大特征值。谱范数
• $\infty$-norm , $\mid \mid A \mid \mid_\infty =\max\limits_i \sum\limits_{j=1}^m \mid a_{ij}\mid $，列和范数，是矩阵列向量绝对值之和的最大值。
• F-范数$\mid \mid X \mid \mid_F = (\sum\limits_{i=1}^m \sum\limits_{i=1}^n \mid a_{ij} \mid^2)^{1/2}$Frobenius范数

测度

metric,有些书翻译成度量，有些书翻译成测度。翻译为度量更准确，但这里沿用测度这一不准确的说法

测度的定义

测度(metric)是定义在$X * X$上的函数，记为$d(x,y)$其中$x,y \in X$,并且满足:

1. $d(x,x)=0$
2. $x \neq y$时，$d(x,y)>0$
3. $d(x,y)=d(y,x)$
4. $d(x,y) \leq d(x,y)+d(y,z)$(三角不等式)

特殊的测度

如果X是$\mathscr{F}$上的一个向量空间，
translation invariant(平移不变量):
测度函数附加条件：$\forall z \in X,d(x,y)=d(x+z)+d(y+z)$

齐次性
测度函数附加条件$\forall a \in \mathscr{F},d(ax,ay)=\mid a\mid d(x,y)$

测度空间的定义

对任意点集X，定义一个测度$(X,d)$是一个测度空间

测度的性质

如果$d(x,y)$是一个测度，那么：

1. $\lambda>0,d’(x,y)=\lambda d(x,y)$也是一个测度
2. $d’(x,y)=\dfrac{d(x,y)}{1+d(x,y)}$也是一个测度

测度与范数的区别

• 测度对应的集合可以是一般的集合，范数对应的集合必须有算术结构
• 如果$d(x,y)$是向量空间X上的测度，并且满足平移不变性和齐次性，那么这个$d(x,0)$就是某种范数
• 反之，如果$\mid \mid x \mid \mid$是范数，那么$d(x,y)=\mid \mid x-y \mid \mid$一定是测度

测度的等价

在集合X上可以定义很多种测度，其中一些测度$d_1,d_2$有些相似性。
例如，对于物理距离来说，单位为米或千米，虽然数值不一样，但有很大的相似性，引入测度定价这一概念。

Lipschiz equvalent（李普希斯等价） 定义：
测度空间X上两个测度$d_1,d_2$李普希斯等价，如果存在正实数$\lambda_1,\lambda_2$，使得$\forall x,y \in X$ ,有：
$\lambda_1 d_1(x,y) \leq d_2(x,y) \leq \lambda_2 d_1(x,y)$

测度的等价，是数学意义上的等价（反身性，对称性，传递性）

定理 ：$R^n$上的各种$l_p$范数都是Lipschiz等价的

收敛性

可以在测度上可以定义收敛性 $d(x_n,y) \to 0$

拓扑等价

测度球

有一个测度$(X,d_1)$，定义测度球为\(\{ x \in X \mid d(x,0) \leq r \}\) ,记为$B_r^{d_1}$

p取不同值的时候，画出的图很有意思
P>1时，测度球是一个凸集

拓扑等价

(topologically equivalent)
空间X上有两种测度$d_1,d_2$，
如果$\exists r_1,r_2 \in R$,两者都是r,x的函数，
使得$B_{r_1}^{d_1} \subset B_r^{d_2} \subset B_{r_2}^{d_1}$
那么$d_1,d_2$也是拓扑等价的

命题 如果$d_1,d_2$是Lipschiz 等价的，那么也是拓扑等价的。
反之未必，因为拓扑等价中的$r_1,r_2$，可以是x的函数，而Lipschiz等价必须是固定的值

距离

闵可夫斯基距离(Minkowski Distance)
欧氏距离(Euclidean Distance)
曼哈顿距离(Manhattan Distance)
切比雪夫距离(Chebyshev Distance)
余弦夹角(Cosine)
汉明距离(Hamming Distance)
杰拉德距离(Jaccard Similarity Coefficient)

闵可夫斯基距离

两个n维变量$A=(a_1,a_2,…,a_n),B=(b_1,b_2,…b_n)$
d=$\mid \mid A-B \mid\mid_p$(就是上文所写的向量的p-norm)

• 当p=1，就是曼哈顿距离
• 当p=2，就是欧式距离
• 当p=$\infty$，就是切比雪夫距离

• 欧式距离
  是我们最易于理解的一种距离

• 曼哈顿距离
  想象从在曼哈顿市区的一个地方到另一个地方，只能走南北或东西的道路，那么所走的实际距离就是曼哈顿距离

代码实现：

import numpy as np
a1=np.linalg.norm([1,2,3],ord=-np.inf)
a2=np.linalg.norm([1,2,3],ord=np.inf)
a3=np.linalg.norm([1,2,3],ord=2)
a4=np.linalg.norm([1,2,3,1],ord=0)
a1,a2,a3,a4

夹角余弦

几何上夹角的余弦，特点是与量无关，与方向有关，机器学习也有用途。

$cos\theta=\dfrac{AB}{\mid A \mid \mid B \mid}$

numpy中没找到直接能实现的函数，所以这么做：

a=np.array([1,2,3])
b=np.array([4,5,6])
np.dot(a,b)/np.linalg.norm(a)/np.linalg.norm(b)

汉明距离

定义：
两个等长度字符串s1和s2之间的汉明距离，定义为s1变成s2所需要的最小替换次数。例如1111,1001的汉明距离为2
用途：
信息编码，为了增强容错性，所用编码的最小汉明距离要尽可能大
代码实现：

a=np.random.randint(low=0,high=2,size=(1,10))
b=np.random.randint(low=0,high=2,size=(1,10))
d=np.sum((a-b!=0))

杰卡德相似系数

杰卡德相似系数，定义为两个集合的交集在并集中所占比例
\(J(A,B)=\dfrac{\mid A \cap B \mid}{\mid A \cup B \mid}\)

杰卡德距离是一个类似的概念
$J_\delta (A,B) = 1-J(A,B)$

Python实现：

a=np.array([1,1,0,1,0])
b=np.array([0,1,1,0,0])
1-np.sum(a&b)/np.sum(a|b)

计算代码

上面给出了一些计算的代码，除此之外，还可以用scipy

import scipy.spatial.distance as dist
d=dist.pdist(m,metric='jaccard')
#'euclidean'
#'minkowski'
#'cityblock'
#...