3333333
范数（“长度”）
定义1：设$||\cdot||$为向量空间$R_{n}$ 的实值函数满足：
$1^o,$ 非负性:
$$ ||x|| \geq 0 $$
其中，$||x||=0 \iff x = 0$
$2^o,$ 齐次性：
$$\forall k\in R,||kx|| = |k| ||x||$$
$3^o,$ 三角不等式：
$$||x+y||\leq ||x|| + ||y||$$
则把$||\cdot||$称为向量范数。
常用的向量范数
$x=(x_{1},x_2,\cdots,x_n)^T$
$1^o,$ 0-范数:
$${||x||}0 = n$$
其中n为x中非零元素的个数。
$2^o,$ 1-范数:
$${||x||}1 = \sum{i=1}^n|x_i|$$
$3^o,$ 2-范数:
$$||x||2 = \sqrt{\sum{i=1}^nx_i^2}$$
$4^o,$ $\infty$-范数:
$$
||x||\infty = \max_{1 \leq i \leq n}|x_i|
$$
定理 (范数的等价性)
$$
\begin{array}{ccccc}
m||\cdot||{P_2} & \leq & || \cdot ||{P_{1}} & \leq & M||\cdot||{P_2} \
||x||\infty & \leq & ||x||1 & \leq & n||x||\infty \
||x||\infty & \leq & ||x||2 & \leq & \sqrt{n}||x||\infty
\end{array}
$$
定义2（矩阵范数) $A = (a{ij})m*n$
满足定义1的三个条件且 $||AB|| \leq ||A||\cdot||B||$
常用的矩阵范数
1-范数(列) $||A|| = \max_{1 \leq j \leq n}\sum_{i=1}^{m}|a_{ij}|$
$\infty$-范数(行) $||A|| = \max_{1 \leq i \leq m}\sum_{i=1}^n|a_{ij}|$
2-范数(谱) $||A|| = \max|A_TA的本征值|$
F-范数 $||A||F = (\sum{j=1}^n\sum_{i=1}^m|a_{ij}^2)^{\frac{1}{2}}$
矩阵常数可由向量范数诱导而得(相容性)
范数诱导的距离
注:距离满足定义1的三个条件且满足对称性(A到B的距离等于B到A的距离)。
定义3（闵可夫斯基距离）有$x = (x_1,x_2,\cdots,x_n)T,y=(y_1,y_2,\cdots,y_n)T$
$$
{\alpha}P(x,y) = (\sum{i=1}^n|x_i-y_i|^P)^{\frac{1}{p}}
$$
$1^o,$ P = 2 \ 欧几里得距离
$2^o,$ P = 1 \ 曼哈顿距离 正南正北”导航”距离。
$3^o,$ $P = \infty$ 切比雪夫距离 ：
$$\alpha_P(x,y) = \max{1 \leq i \leq n}|x_i-y_i|$$
老师举了个例子即：国际象棋king移动到其他位置的最快路径长度。
如图：
曼哈顿距离为7，切比雪夫距离为7。
$4^o,$ p = 0 \ 汉明重量(即$x_i = y_i$)：
$$\alpha_0(x,y) = \sum{i=1}^n(x_i-y_i)^0$$
定义(莱文斯坦/字符串距离) 从一个字符串变为另一个字符串的步数。
e.g. $safe -> security$ 使用了7步。
**定义(推土机距离)**从一个概率分布变为另一个概率分布的最快步
**定义(堪培拉距离)**加权的曼哈顿
$$\alpha_{can}(x,y) = \sum_{i=1}^n\frac{|x_i-y_i|}{|x_i+y_i|}$$
相似度
不是距离，定义1的前两个条件。
定义(余弦相似度) $\Sim_\cos(x,y) = \frac{x\cdot y}{||x||\cdot ||y||}
定义(皮尔逊相关系数) $x = (x_1,\cdots,x_n)^T,y = (y_1,\cdots,y_n)^T$
$$\rho_{x,y} = \frac{Cov(x,y)}{\sigma_x\sigma_y} = \frac{E[(x-\mu_x)(y-\mu_y)]}{\sigma_x\sigma_y}$$
e.g.
Alice 给Bob发送序列 第一次为$x = (80,85,90,75,95)^T$ ,第二次为$y = (70,75,85,60,90)^T$
计算得到$\mu_x=85,\mu_y = 76,Cov(x,y) = 75,\sigma_x=7.07,\sigma_y=10.68,\rho_{x,y} = 0.997$。
$\rho_{x,y}$接近于1，说明具有强线性正相关。
定义（斯皮尔曼相关系数）
$$\rho_{x,y} = \frac{\sum_{i=1}^n(R(x_i)-\overline{R(x)})(R(y_i)-\overline{R(y)})}{\sqrt{(\frac{1}{n}\sum_{i=1}^{n}(R(x_i)-\overline{R(x)}))(\frac{1}{n}\sum_{i=1}^n(R(y_i)-\overline{R(y)}))}}$$
R表示位次,简化版如下：
$$\rho_{x,y} = 1-\frac{6\cdot\sum_{i=1}^nd_i^2}{n(n^2-1)}$$
定义(杰拉德定理)
$X = {x_1,\cdots,x_n}, Y = {y_1,\cdots,y_n}$ 二进制字符串
$$\rho_j(X,Y) = \frac{|X\cap Y|}{|X\cup Y|}$$
定义(Sorensen-Dice指数) 文本分类和图像处理
$$\rho_s(X,Y) = \frac{2\cdot |X\cap Y|}{|X|+|Y|}$$