精华内容
下载资源
问答
  • 机器学习中常用范数与距离

    千次阅读 2019-06-22 19:06:36
    机器学习中常用范数与距离前言范数向量范数矩阵范数距离曼哈顿距离欧氏距离切比雪夫距离闵可夫斯基距离标准化欧氏距离马氏距离余弦距离 前言 在机器学习中经常会涉及到范数和距离的概念,有时候优化的目标函数就是...

    前言

    在机器学习中经常会涉及到范数和距离的概念,有时候优化的目标函数就是常用范数和距离的变化。关于范数和距离其实已经有很多人写过文章了,我之所以还要再写一遍,是因为读别人的文章我老是记不住,干脆好记性不如烂键盘,自己敲一遍吧。


    范数

    向量范数

    向量范数表示向量空间中向量的大小。
    n n n维实空间 R n R^n Rn中的向量 X = ( x 1 , x 2 , . . . , x n ) T \mathbf X = (x_1, x_2, ..., x_n)^T X=(x1,x2,...,xn)T的范数记作 ∥ X ∥ \Vert \mathbf X \Vert X,该范数是一个实数,且满足以下三条性质:
    (1) 非负性: ∥ X ∥ ≥ 0 \Vert \mathbf X \Vert \geq 0 X0,当且仅当 X = 0 \mathbf X = \mathbf 0 X=0 ∥ X ∥ = 0 \Vert \mathbf X \Vert = 0 X=0
    (2) 齐次性:对任意实数 λ \lambda λ ∥ λ X ∥ \Vert \lambda \mathbf X\Vert λX = ∣ λ ∣ ∥ X ∥ |\lambda| \Vert \mathbf X \Vert λX
    (3) 三角不等式:对任意向量 Y ∈ R n \mathbf Y \in R^n YRn ∥ X + Y ∥ ≤ ∥ X ∥ + ∥ Y ∥ \Vert \mathbf X + \mathbf Y \Vert \leq \Vert \mathbf X \Vert + \Vert \mathbf Y \Vert X+YX+Y

    • 1范数
      ∥ X ∥ 1 = ∑ i = 1 n ∣ x i ∣ = ∣ x 1 ∣ + ∣ x 2 ∣ + . . . + ∣ x n ∣ {\Vert \mathbf X \Vert}_1 = \sum_{i=1}^n {|x_i|} = |x_1| + |x_2| + ... +|x_n| X1=i=1nxi=x1+x2+...+xn
    • 2范数
      ∥ X ∥ 2 = ∑ i = 1 n x i 2 = x 1 2 + x 2 2 + . . . + x n 2 {\Vert \mathbf X \Vert}_2 = \sqrt {\sum_{i=1}^n {x_i}^2} = \sqrt {{x_1}^2 + {x_2}^2 + ... +{x_n}^2} X2=i=1nxi2 =x12+x22+...+xn2
    • ∞ 范 数 \infty范数
      ∥ X ∥ ∞ = max ⁡ 1 ≤ i ≤ n ∣ x i ∣ {\Vert \mathbf X \Vert}_\infty = \max_{1\leq i \leq n} |x_i| X=1inmaxxi
    • p p p范数
      ∥ X ∥ p = ∑ i = 1 n ∣ x i ∣ p p {\Vert \mathbf X \Vert}_p = \sqrt[p] {\sum_{i=1}^n |x_i|^p} Xp=pi=1nxip
      其中,前三种范数都是 p p p范数的特殊情况,或者可以说 p p p范数不是一个单纯的范数,而是一组范数的表示。
      需要注意的是,当 p ≥ 1 p \geq 1 p1时,各个范数是满足三角不等式的,而当 0 ≤ p &lt; 1 0 \leq p \lt 1 0p<1时,范数是不满足三角不等式的,此时的范数只是一种概念表示。
      比如0范数用 p p p范数的计算公式表示为如下形式:
      ∥ X ∥ 0 = ∑ i = 1 n ∣ x i ∣ 0 0 {\Vert \mathbf X \Vert}_0 = \sqrt[0] {\sum_{i=1}^n |x_i|^0} X0=0i=1nxi0
      这样表示的问题在于,当 x i = 0 x_i = 0 xi=0时, 0 0 0^0 00 是没有意义的,同样开零次方也是没有意义的。一般我们实际使用的0范数指向量中的非零元素个数。
      另外,对于 ∞ \infty 范数,它实际是通过以下公式计算得来的:
      ∥ X ∥ ∞ = lim ⁡ p → ∞ ∥ X ∥ p {\Vert \mathbf X \Vert}_\infty = \lim_{p \rightarrow \infty} {\Vert \mathbf X \Vert}_p X=plimXp
      在实际应用中,1范数可以实现特征的稀疏,去掉一些无用信息;2范数通常用作目标函数的正则化项,防止过拟合,提高模型的泛化能力。1范数和2范数可以度量两个向量之间的差异,而 ∞ \infty 范数用来度量向量元素的最大值。

    矩阵范数

    矩阵范数表示矩阵变换引起的变化大小。
    若有 n × n n \times n n×n的矩阵 A \mathbf A A A ∈ R n × n \mathbf A \in R^{n \times n} ARn×n)以及 n n n维实空间 R n R^n Rn中的向量 X \mathbf X X,称
    ∥ A ∥ = max ⁡ X ∈ R n , ∥ X ∥ = ̸ 0 ∥ A X ∥ ∥ X ∥ = max ⁡ ∥ X ∥ = 1 , X ∈ R n ∥ A X ∥ \Vert \mathbf A \Vert = \max_{\mathbf X \in R^n, {\Vert \mathbf X \Vert} = \not 0} \frac{\Vert \mathbf {AX} \Vert}{\Vert \mathbf X \Vert} = \max_{\Vert \mathbf X \Vert = 1, \mathbf X \in R^n} \Vert \mathbf {AX} \Vert A=XRn,X≠0maxXAX=X=1,XRnmaxAX
    为矩阵 A \mathbf A A的从属于该向量范数的范数,即矩阵 A \mathbf A A的范数。
    常用的矩阵范数如下所示:

    • 1范数
      ∥ A ∥ 1 = max ⁡ X ∈ R n , ∥ X ∥ = ̸ 0 ∥ A X ∥ 1 ∥ X ∥ 1 = max ⁡ 1 ≤ j ≤ n ∑ i = 1 n ∣ a i j ∣ {\Vert \mathbf A \Vert}_1 = \max_{\mathbf X \in R^n, {\Vert \mathbf X \Vert} = \not 0} \frac{{\Vert \mathbf {AX} \Vert}_1} {{\Vert \mathbf X \Vert}_1} = \max_{1 \leq j \leq n} \sum_{i=1}^n |a_{ij}| A1=XRn,X≠0maxX1AX1=1jnmaxi=1naij
      A \mathbf A A的列元素绝对值之和的最大值,又称为 A \mathbf A A的列范数。
    • 2范数
      ∥ A ∥ 2 = max ⁡ X ∈ R n , ∥ X ∥ = ̸ 0 ∥ A X ∥ 2 ∥ X ∥ 2 = λ m a x {\Vert \mathbf A \Vert}_2 = \max_{\mathbf X \in R^n, {\Vert \mathbf X \Vert} = \not 0} \frac{{\Vert \mathbf {AX} \Vert}_2} {{\Vert \mathbf X \Vert}_2} = \sqrt {\lambda_{max}} A2=XRn,X≠0maxX2AX2=λmax
      其中 λ m a x \lambda_{max} λmax A T A \mathbf A^T \mathbf A ATA的特征值中绝对值最大者的绝对值。
    • ∞ \infty 范数
      ∥ A ∥ ∞ = max ⁡ X ∈ R n , ∥ X ∥ = ̸ 0 ∥ A X ∥ ∞ ∥ X ∥ ∞ = max ⁡ 1 ≤ i ≤ n ∑ j = 1 n ∣ a i j ∣ {\Vert \mathbf A \Vert}_\infty = \max_{\mathbf X \in R^n, {\Vert \mathbf X \Vert} = \not 0} \frac{{\Vert \mathbf {AX} \Vert}_\infty} {{\Vert \mathbf X \Vert}_\infty} = \max_{1 \leq i \leq n} \sum_{j=1}^n |a_{ij}| A=XRn,X≠0maxXAX=1inmaxj=1naij
      A \mathbf A A的行元素绝对值之和的最大值,又称为 A \mathbf A A的行范数。
    • F F F范数
      ∥ A ∥ F = ∑ i = 1 n ∑ j = 1 n a i j 2 {\Vert \mathbf A \Vert}_F = \sqrt {\sum_{i=1}^n \sum_{j=1}^n {a_{ij}}^2} AF=i=1nj=1naij2
      F F F范数的全称为 F r o b e n i u s Frobenius Frobenius范数或者弗罗贝尼乌斯范数。
      关于矩阵范数,我们还需要了解的一个概念是谱半径。因为矩阵 A \mathbf A A的每一个特征值的绝对值,都不超过矩阵 A \mathbf A A的范数 ∥ A ∥ \Vert \mathbf A \Vert A,即 ∣ λ i ∣ ≤ ∥ A ∥ |\lambda_i| \leq \Vert \mathbf A \Vert λiA
      而谱半径表示的是矩阵 A \mathbf A A的所有特征值绝对值的最大值,即 ρ ( A ) = max ⁡ 1 ≤ i ≤ n ∣ λ i ∣ \rho(\mathbf A) = \max_{1 \leq i \leq n} |\lambda_i| ρ(A)=max1inλi,则有结论 ρ ( A ) ≤ ∥ A ∥ \rho(\mathbf A) \leq \Vert \mathbf A \Vert ρ(A)A

    距离

    距离一般用来度量样本之间的相似性,下面我们以向量 a = ( x 11 , x 12 , . . . , x 1 n ) T \mathbf a = (x_{11}, x_{12}, ..., x_{1n})^T a=(x11,x12,...,x1n)T b = ( x 21 , x 22 , . . . , x 2 n ) T \mathbf b = (x_{21}, x_{22}, ..., x_{2n})^T b=(x21,x22,...,x2n)T为例,一起看一下几个常用的距离。

    曼哈顿距离

    曼哈顿距离又称作城市街区距离(City Block distance)。这样称呼的原因在于曼哈顿距离的计算方式和从城市的一个十字路口到另外一个十字路口的距离的计算方式是一样的。
    假设 a \mathbf a a b \mathbf b b是二维向量,那么它们之间的距离就可以表示成:
    D M a n h a t t a n = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ D_{Manhattan} = |x_1 - x_2| + |y_1 - y_2| DManhattan=x1x2+y1y2
    将其扩展到 n n n维则可以表示为:
    D M a n h a t t a n = ∑ i = 1 n ∣ x 1 i − x 2 i ∣ D_{Manhattan} = \sum_{i=1}^n |x_{1i} - x_{2i}| DManhattan=i=1nx1ix2i
    细心的朋友可能已经发现了,曼哈顿距离其实就是上面提到的1范数,有时它也叫做最小绝对误差。

    欧氏距离

    欧氏距离其实就是我们平时说的两点间的距离:
    D E u c l i d = ∑ i = 1 n ( x 1 i − x 2 i ) 2 D_{Euclid} = \sqrt {\sum_{i=1}^n {(x_{1i} - x_{2i})}^2} DEuclid=i=1n(x1ix2i)2
    或者可以用向量的形式表示如下:
    D E u c l i d = ( a − b ) ( a − b ) T D_{Euclid} = \sqrt {{(\mathbf a - \mathbf b)} {(\mathbf a - \mathbf b)}^T} DEuclid=(ab)(ab)T
    欧氏距离其实就是一种2范数。

    切比雪夫距离

    切比雪夫距离的计算方式类似于国际象棋中的国王的走法,国王从棋盘上格子 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) ( x 2 , y 2 ) (x_2, y_2) (x2,y2)走的最少步数总是 max ⁡ ( ∣ x 2 − x 1 ∣ , ∣ y 2 − y 1 ∣ ) \max(|x_2 - x_1|, |y_2 - y_1|) max(x2x1,y2y1)步,具体的计算公式为:
    D C h e b y s h e v = max ⁡ i ∣ x 1 i − x 2 i ∣ D_{Chebyshev} = \max_{i} |x_{1i} - x_{2i}| DChebyshev=imaxx1ix2i

    闵可夫斯基距离

    闵可夫斯基距离类似于 p p p范数,它表示的是一组距离的定义,上面提到的几种距离其实都是闵可夫斯基距离的特殊形式。它的计算公式为:
    D M i n k o w s k i = ∑ i = 1 n ∣ x 1 i − x 2 i ∣ p p D_{Minkowski} = \sqrt[p] {\sum_{i=1}^n {|x_{1i} - x_{2i}|}^p} DMinkowski=pi=1nx1ix2ip
    当上式的 p = 1 p=1 p=1时,就是曼哈顿距离;当 p = 2 p=2 p=2时,就是欧氏距离;当 p = ∞ p=\infty p=时,就是切比雪夫距离。
    闵可夫斯基距离的缺点在于:
    (1) 将向量各个维度(样本点各个特征)的量纲当做相同的去计算,比如第一个特征为身高,第二个特征为体重,闵可夫斯基距离计算的时候是无法考虑上它们的单位的,只是把它们当做统一的数值,这难免就会差生偏差;
    (2) 没有考虑各个维度的分布(期望、方差等)。

    标准化欧氏距离

    标准化欧氏距离是针对欧氏距离的缺点(即闵可夫斯基距离的缺点)做出的一种改进方案。
    标准化欧氏距离利用数据的期望( m e a n mean mean)和标准差( s t a n d a r d standard standard d e v i a t i o n deviation deviation)对数据进行标准化,比如向量 X \mathbf X X就可以被标准化为 X − m s \frac{\mathbf X - m} {s} sXm
    标准化后的数据的期望为0,方差为1。
    经过标准化后的欧氏距离可以表示为:
    D s t d _ e u c = ∑ i = 1 n ( x 1 i − x 2 i s i ) 2 D_{std\_euc} = \sqrt {\sum_{i=1}^n ({\frac{x_{1i} - x_{2i}} {s_i})}^2} Dstd_euc=i=1n(six1ix2i)2

    马氏距离

    假设有 m m m个样本,每个样本有 n n n个特征,协方差矩阵为 C o v Cov Cov,均值为 μ \mu μ,那么其中一个样本向量 X \mathbf X X到均值 μ \mu μ的马氏距离为:
    D M a h a l a n o b i s = ( X − μ ) T C o v − 1 ( X − μ ) D_{Mahalanobis} = \sqrt {{(\mathbf X - \mu)}^TCov^{-1}(\mathbf X - \mu)} DMahalanobis=(Xμ)TCov1(Xμ)
    如果是其中的两个向量 X i \mathbf X_i Xi X j \mathbf X_j Xj,它们的距离计算方式就为:
    D M a h a l a n o b i s = ( X i − X j ) T C o v − 1 ( X i − X j ) D_{Mahalanobis} = \sqrt {{(\mathbf X_i - \mathbf X_j)}^TCov^{-1}(\mathbf X_i - \mathbf X_j)} DMahalanobis=(XiXj)TCov1(XiXj)
    若协方差矩阵是单位矩阵(各个样本之间独立同分布),那么计算公式就变为:
    D M a h a l a n o b i s = ( X i − X j ) T ( X i − X j ) D_{Mahalanobis} = \sqrt {{(\mathbf X_i - \mathbf X_j)}^T(\mathbf X_i - \mathbf X_j)} DMahalanobis=(XiXj)T(XiXj)
    如果协方差矩阵是对角矩阵,那么公式就变为了标准化欧氏距离。
    马氏距离与量纲是无关的,能够排除变量之间的相关性干扰。

    余弦距离

    首先,两个向量的余弦相似度可以表示为:
    c o s ( θ ) = a ⋅ b ∥ a ∥ 2 ∥ b ∥ 2 cos(\theta) = \frac{\mathbf a \cdot \mathbf b} {{\Vert \mathbf a\Vert}_2 {\Vert \mathbf b \Vert}_2} cos(θ)=a2b2ab
    余弦相似度就是两个特征向量夹角的余弦,关注的是向量之间的角度关系,并不关心它们的绝对大小,其取值范围是[-1, 1]。
    余弦距离是用1减去余弦相似度得来的,其取值范围为[0, 2],相同的两个向量余弦距离为0。
    需要注意的是,余弦距离并不是严格定义的距离,它不满足距离公理(正定性,对称性,三角不等式)中的三角不等式。
    三条距离公理和范数的三条性质是类似的,这里给出具体定义:
    假设有任意的三个向量 X = ( x 1 , x 2 , . . . , x n ) T \mathbf X = (x_1, x_2, ..., x_n)^T X=(x1,x2,...,xn)T Y = ( y 1 , y 2 , . . . . , y n ) T \mathbf Y = (y_1, y_2, ...., y_n)^T Y=(y1,y2,....,yn)T Z = ( z 1 , z 2 , . . . , z n ) T \mathbf Z = (z_1, z_2, ..., z_n)^T Z=(z1,z2,...,zn)T
    (1)正定性: D ( X , Y ) ≥ 0 D(\mathbf X, \mathbf Y) \ge 0 D(X,Y)0,当且仅当 X = Y \mathbf X = \mathbf Y X=Y时, D ( X , Y ) = 0 D(\mathbf X, \mathbf Y) = 0 D(X,Y)=0
    (2)对称性: D ( X , Y ) = D ( Y , X ) D(\mathbf X, \mathbf Y) = D(\mathbf Y, \mathbf X) D(X,Y)=D(Y,X)
    (3)三角不等式: D ( X , Z ) ≤ D ( X , Y ) + D ( Y , Z ) D(\mathbf X, \mathbf Z) \le D(\mathbf X, \mathbf Y) + D(\mathbf Y, \mathbf Z) D(X,Z)D(X,Y)+D(Y,Z)
    针对余弦距离,我们给出三条距离公理的证明:
    (1)正定性
    D ( X , Y ) = 1 − c o s ( θ ) = 1 − X ⋅ Y ∥ X ∥ 2 ∥ Y ∥ 2 = ∥ X ∥ 2 ∥ Y ∥ 2 − X ⋅ Y ∥ X ∥ 2 ∥ Y ∥ 2 D(\mathbf X, \mathbf Y) = 1 - cos(\theta) = 1 - \frac{\mathbf X \cdot \mathbf Y} {{\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2} = \frac{{\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 -\mathbf X \cdot \mathbf Y} {{\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2} D(X,Y)=1cos(θ)=1X2Y2XY=X2Y2X2Y2XY
    因为 ∥ X ∥ 2 ∥ Y ∥ 2 − X ⋅ Y = ∥ X ∥ 2 ∥ Y ∥ 2 − ∥ X ∥ 2 ∥ Y ∥ 2 c o s ( θ ) ≥ 0 {\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 -\mathbf X \cdot \mathbf Y = {\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 - {\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 cos(\theta) \ge 0 X2Y2XY=X2Y2X2Y2cos(θ)0,则 D ( X , Y ) ≥ 0 D(\mathbf X, \mathbf Y) \ge 0 D(X,Y)0
    当且仅当 X = Y \mathbf X = \mathbf Y X=Y时, ∥ X ∥ 2 ∥ Y ∥ 2 = X ⋅ Y {\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 = \mathbf X \cdot \mathbf Y X2Y2=XY,即 D ( X , Y ) = 0 D(\mathbf X, \mathbf Y) = 0 D(X,Y)=0
    (2)对称性
    D ( X , Y ) = ∥ X ∥ 2 ∥ Y ∥ 2 − X ⋅ Y ∥ X ∥ 2 ∥ Y ∥ 2 = ∥ Y ∥ 2 ∥ X ∥ 2 − Y ⋅ X ∥ Y ∥ 2 ∥ X ∥ 2 = D ( Y , X ) D(\mathbf X, \mathbf Y) = \frac{{\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2 -\mathbf X \cdot \mathbf Y} {{\Vert \mathbf X \Vert}_2 {\Vert \mathbf Y \Vert}_2} = \frac{{\Vert \mathbf Y \Vert}_2 {\Vert \mathbf X \Vert}_2 -\mathbf Y \cdot \mathbf X} {{\Vert \mathbf Y \Vert}_2 {\Vert \mathbf X \Vert}_2} = D(\mathbf Y, \mathbf X) D(X,Y)=X2Y2X2Y2XY=Y2X2Y2X2YX=D(Y,X)
    (3)三角不等式
    本条我们直接使用反例证明,假设 X = ( 1 , 0 ) T \mathbf X = (1, 0)^T X=(1,0)T Y = ( 1 , 1 ) T \mathbf Y = (1, 1)^T Y=(1,1)T Z = ( 0 , 1 ) T \mathbf Z = (0, 1)^T Z=(0,1)T,则 D ( X , Y ) = 1 − 2 2 D(\mathbf X, \mathbf Y) = 1 - \frac {\sqrt 2} {2} D(X,Y)=122 D ( Y , Z ) = 1 − 2 2 D(\mathbf Y, \mathbf Z) = 1 - \frac {\sqrt 2} {2} D(Y,Z)=122 D ( X , Z ) = 1 D(\mathbf X, \mathbf Z) = 1 D(X,Z)=1
    D ( X , Z ) &gt; D ( X , Y ) + D ( Y , Z ) D(\mathbf X, \mathbf Z) \gt D(\mathbf X, \mathbf Y) + D(\mathbf Y, \mathbf Z) D(X,Z)>D(X,Y)+D(Y,Z)
    综上,余弦距离满足正定性、对称性,但是不满足三角不等式。
    关于余弦距离还需要提的是,它与欧氏距离的关系。
    首先,欧氏距离体现数值上的绝对差异,而余弦距离体现方向上的相对差异。比如,当一对文本长度差距很大、但内容相近时,如果使用词频或词向量作为特征,它们在特征空间中的欧氏距离通常很大;而如果使用余弦相似度的话,它们之间的夹角可能很小,因而相似度高。此外,在文本、图像、视频等领域,研究对象的特征维度往往很高,余弦相似度在高维情况下依然保持“相同时为1, 正交时为0,相反时为-1”的性质,而欧氏距离的数值则受维度的影响,范围不固定,并且含义也比较模糊。
    在一些场景下,例如Word2Vec中,其向量的模长是经过归一化的,此时欧氏距离与余弦距离有着单调的关系,即 ∥ X − Y ∥ 2 = 2 ( 1 − c o s ( X , Y ) {\Vert \mathbf X - \mathbf Y \Vert}_2 = \sqrt {2 (1 - cos(\mathbf X, \mathbf Y)} XY2=2(1cos(X,Y) 。其中 ∥ X − Y ∥ 2 {\Vert \mathbf X - \mathbf Y \Vert}_2 XY2表示欧氏距离, c o s ( X , Y ) cos(\mathbf X, \mathbf Y) cos(X,Y)表示余弦相似度, 1 − c o s ( X , Y ) 1 - cos(\mathbf X, \mathbf Y) 1cos(X,Y)表示余弦距离。在此场景下,如果选择距离最小(相似度最大)的近邻,那么使用余弦相似度和欧氏距离的结果是相同的。
    最后,再看几个例子。当统计两部剧的用户观看行为,用户A的观看向量为(0, 1),用户B为(1, 0);此时二者的余弦距离很大,而欧氏距离很小。我们分析两个用户对于不同视频的偏好,更关注相对差异,显然应当使用余弦距离。而当我们分析用户活跃度,以登录次数(单位:次)和平均观看时长(单位:分钟)作为特征时,余弦距离认为(1, 10)、(10, 100)两个用户距离很近,但显然这两个用户活跃度是有着极大差异的,此时我们更关注数值绝对差异,应当使用欧氏距离。

    相关系数与相关距离

    假设有两个变量X和Y,那么它们的相关系数可以表示为:
    r ( X , Y ) = C o v ( X , Y ) V a r ( X ) V a r ( Y ) = E ( ( X − E X ) ( Y − E Y ) ) V a r ( X ) V a r ( Y ) r(X, Y) = \frac {Cov(X, Y)} {\sqrt {Var(X) Var(Y)}} = \frac {E((X - EX)(Y - EY))} {\sqrt {Var(X) Var(Y)}} r(X,Y)=Var(X)Var(Y) Cov(X,Y)=Var(X)Var(Y) E((XEX)(YEY))
    其中, C o v ( X , Y ) Cov(X, Y) Cov(X,Y)为X与Y的协方差, V a r ( X ) Var(X) Var(X)为X的方差, V a r ( Y ) Var(Y) Var(Y)为Y的方差。
    相关系数是衡量随机变量X与Y的相关程度的一种方法,相关系数的取值范围是[-1, 1]。相关系数的绝对值越大,则表示X与Y相关度越高。
    当X与Y正线性相关时,相关系数取值为1;当X与Y负线性相关时,相关系数取值为-1。
    相关距离定义为 D C o r r e l a t i o n = 1 − r ( X , Y ) D_{Correlation} = 1 - r(X, Y) DCorrelation=1r(X,Y)

    汉明距离

    两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要做的最小替换次数。比如字符串"1100"与"1111"之间的汉明距离为2。
    汉明距离在信息编码方面应用的比较多,比如为了增强容错性,应使得编码间的最小汉明距离尽可能大。

    杰卡德类似系数

    两个集合A和B中的交集元素在A和B的并集中所占的比例,称为两个集合的杰卡德类似系数。用符号 J ( A , B ) J(A, B) J(A,B)表示。
    J ( A , B ) = ∣ A ⋂ B ∣ ∣ A ⋃ B ∣ J(A, B) = \frac {|A \bigcap B|} {|A \bigcup B|} J(A,B)=ABAB
    杰卡德类似系数是衡量两个集合的类似度的一种指标。
    杰卡德距离是与杰卡德类似系数相反的概念,它的计算公式为:
    D J a c c a r d = 1 − J ( A , B ) = ∣ A ⋃ B ∣ − ∣ A ⋂ B ∣ ∣ A ⋃ B ∣ D_{Jaccard} = 1 - J(A, B) = \frac {|A \bigcup B| - |A \bigcap B|} {|A \bigcup B|} DJaccard=1J(A,B)=ABABAB
    杰卡德距离用两个集合中不同元素占全部元素的比例来衡量两个集合的区分度。


    参考文章

    [1] 范数
    [2] 范数(norm) 几种范数的简单介绍
    [3] 范数_百度百科
    [4] 向量与矩阵的范数
    [5] 数学中几种经常使用的距离
    [6] 相关系数_百度百科
    [7] 《百面机器学习 算法工程师带你去面试》(诸葛越主编). 第二章 模型评估 . 03 余弦距离的应用

    展开全文
  • 常用范数及其意义

    2021-10-08 17:38:03
  • 机器学习之常用范数

    千次阅读 2018-10-31 09:54:55
    范数是一个描述向量或矩阵的变化程度的非负数值。数学上,范数可以分为...下列我们讨论机器学习领域常用的若干范数。 1. 向量范数 定义: x⃗\vec{x}x在线性空间中,若给定函数fff同时满足如下三个性质 [2], 正定...

    范数是一个描述向量或矩阵的变化程度的非负数值。数学上,范数可以分为向量范数和矩阵范数。向量范数表示向量空间中向量引起的变化的大小,矩阵范数表示矩阵在矩阵空间中引起的变化的大小。范数在数值方法的收敛性,稳定性,误差计算等方面有着重要意义 [1]。下列我们讨论机器学习领域常用的若干范数。


    1. 向量范数

    定义: x ⃗ \vec{x} x 在线性空间中,若给定函数 f f f同时满足如下三个性质 [2],

    1. 正定性: f ( x ⃗ ) ≥ 0 f(\vec{x})\geq 0 f(x )0 f ( x ⃗ ) = 0 f(\vec{x})=0 f(x )=0 ⇒ x ⃗ = 0 \Rightarrow \vec{x}=0 x =0
    2. 齐次性: f ( α x ⃗ ) = ∣ α ∣ f ( x ⃗ ) f(\alpha \vec{x})=\left | \alpha \right | f(\vec{x}) f(αx )=αf(x )
    3. 三角不等性: f ( x ⃗ + y ⃗ ) ≤ f ( x ⃗ ) + f ( y ⃗ ) f(\vec{x}+\vec{y}) \leq f(\vec{x})+f(\vec{y}) f(x +y )f(x )+f(y )

    则称 f f f为向量 x ⃗ \vec{x} x 上的范数。


    L p L_p Lp范数定义: 给定向量 x ⃗ \vec{x} x ,对于任意的数 p ⩾ 1 p\geqslant 1 p1,称 L p = ∑ i = 1 n x ⃗ i p n L_p=\sqrt[n]{\sum_{i=1}^{n}\vec{x}_i^p} Lp=ni=1nx ip 为向量 x ⃗ i \vec{x}_i x i p p p范数。


    L 0 L_0 L0范数: L 0 = ∑ i = 1 n x ⃗ i 0 0 L_0=\sqrt[0]{\sum_{i=1}^{n}\vec{x}_i^0} L0=0i=1nx i0 。严格来说, L 0 L_0 L0范数并不是一个真正意义上的范数, L 0 L_0 L0范数并不满足范数定义。通常,人们默认使用 L 0 L_0 L0范数来统计非零元素的个数。 L 0 L_0 L0范数的Matlab代码如下,

    fprintf('Source vector x');
    x=[-3 -2 -1 0 1 2]
    sum( x(:) ~= 0 )
    

    L 1 L_1 L1范数: L 1 = ∑ i = 1 n ∣ x ⃗ i ∣ L_1=\sum_{i=1}^{n}\left | \vec{x}_i \right | L1=i=1nx i L 1 L_1 L1范数是我们常见的一种范数, L 1 L_1 L1范数表示向量 x ⃗ \vec{x} x 的绝对值之和。 L 1 L_1 L1范数Matlab代码如下,

    fprintf('Source vector x');
    x=[-3 -2 -1 0 1 2]
    norm(x, 1)
    

    L 2 L_2 L2范数: L 2 = ∑ i = 1 n x i 2 2 L_2=\sqrt[2]{\sum_{i=1}^{n}x_i^2} L2=2i=1nxi2 L 2 L_2 L2范数是我们最常见的范数,欧式距离就是一种 L 2 L_2 L2范数, L 2 L_2 L2范数表示向量元素的平方和的开平方。 L 2 L_2 L2范数Matlab代码如下,

    fprintf('Source vector x');
    x=[-3 -2 -1 0 1 2]
    norm(x, 2)
    

    L ∞ L_\infty L范数: L ∞ = ∑ i = 1 n x i ∞ ∞ L_\infty=\sqrt[\infty]{\sum_{i=1}^{n}x_i^\infty} L=i=1nxi 。大家通常用 L ∞ L_\infty L范数表示向量元素绝对值中的最大绝对值, L − ∞ L_{-\infty} L范数表示向量元素绝对值中的最小绝对值。 L ∞ L_\infty L L − ∞ L_{-\infty} L范数Matlab代码如下,

    fprintf('Source vector x');
    x=[-3 -2 -1 0 1 2]
    norm(x, inf)
    norm(x, -inf)
    


    2. 矩阵范数

    定义: 矩阵 A A A在线性空间中,给定函数 f f f,若函数 f f f同时满足如下四个性质 [3],

    1. 正定性: f ( A ) ≥ 0 f(A)\geq 0 f(A)0 f ( A ) = 0 f(A)=0 f(A)=0 ⇒ A = 0 \Rightarrow A=0 A=0
    2. 齐次性: f ( α A ) = ∣ α ∣ f ( A ) f(\alpha A)=\left | \alpha \right | f(A) f(αA)=αf(A)
    3. 三角不等性: f ( A + B ) ≤ f ( A ) + f ( B ) f(A+B) \leq f(A)+f(B) f(A+B)f(A)+f(B)
    4. 相容性: f ( A B ) ≤ f ( A ) f ( B ) f(AB) \leq f(A)f(B) f(AB)f(A)f(B)

    则称 f f f为矩阵 A A A上的范数。


    Frobenious范数 [4]: f F ( A ) = ∑ i , j A i , j 2 f_{F}(A)=\sqrt{\sum_{i,j}A_{i,j}^{2}} fF(A)=i,jAi,j2 。Frobenious范数的Matlab代码如下,

    fprintf('Source matrix A');
    A=[2 2 3
       -4 -2 0];
    norm(A, 'fro')
    

    矩阵 L 1 L_1 L1列和范数: f 1 ( A ) = max ⁡ j ( ∑ i = 1 m ∣ a i , j ∣ ) f_{1}(A) = \max \limits_{j}\left ( \sum_{i=1}^{m}\left | a_{i,j} \right | \right ) f1(A)=jmax(i=1mai,j)。矩阵 L 1 L_1 L1列和范数表示所有矩阵列向量绝对值之和的最大值。 矩阵 L 1 L_1 L1列和范数的Matlab代码如下,

    fprintf('Source matrix A');
    A=[2 2 3
       -4 -2 0];
    norm(A,1)
    

    矩阵 L 2 L_2 L2范数: f 2 ( A ) = max ⁡ i ( λ i ( A T A ) ) f_{2}(A) = \max \limits_{i}\left ( \sqrt{\lambda _i\left ( A^TA \right )} \right ) f2(A)=imax(λi(ATA) ),其中 λ i ( A T A ) \lambda _i\left ( A^TA \right ) λi(ATA)表示矩阵 A T A A^TA ATA的第 i i i个特征值,我们也称该范数为矩阵 A A A的谱范数。矩阵 L 2 L_2 L2范数表示 A T A A^TA ATA的最大特征值的开方。矩阵 L 2 L_2 L2范数的Matlab代码如下,

    fprintf('Source matrix A');
    A=[2 2 3
       -4 -2 0];
    norm(A,2)
    

    矩阵 L ∞ L_\infty L行和范数: f ∞ ( A ) = max ⁡ i ( ∑ j = 1 m ∣ a i , j ∣ ) f_{\infty}(A) = \max \limits_{i}\left ( \sum_{j=1}^{m}\left | a_{i,j} \right | \right ) f(A)=imax(j=1mai,j)。矩阵 L ∞ L_\infty L行和范数表示所有矩阵行向量绝对值之和的最大值。矩阵 L ∞ L_\infty L行和范数的Matlab代码如下,

    fprintf('Source matrix A');
    A=[2 2 3
       -4 -2 0];
    norm(A,inf)
    


    3. 向量范数和矩阵范数的相容性

    不仅矩阵之间有乘法运算,矩阵与向量之间也会有乘法运算,为了范数概念使用上的可拓展性,往往需要验证向量范数和矩阵范数的相容性 [5]。


    定义: f ( A ) f(A) f(A)为 矩阵 A A A空间上的矩阵范数, f ( x ⃗ ) f(\vec{x}) f(x )为向量 x ⃗ \vec{x} x 空间上的向量范数,如果对于任意的 A A A x ⃗ \vec{x} x 都有,

    f ( A x ⃗ ) ⩽ f ( A ) f ( x ⃗ ) f(A\vec{x})\leqslant f(A)f(\vec{x}) f(Ax )f(A)f(x )

    称矩阵范数 f ( A ) f(A) f(A)与向量范数 f ( x ⃗ ) f(\vec{x}) f(x )是相容的。


    举例: 证明矩阵范数 f ( A ) = ∑ i = 1 n ∑ j = 1 n ∣ a i , j ∣ f(A)={\sum_{i=1}^{n}}{\sum_{j=1}^{n}\left | a_{i,j} \right |} f(A)=i=1nj=1nai,j与向量范数 f ( x ⃗ ) = ∑ i = 1 n ∣ x i ∣ f(\vec{x})=\sum_{i=1}^{n}\left | x_i \right | f(x )=i=1nxi是相容的。

    f ( A x ⃗ ) = ∑ i = 1 n ∣ ∑ k = 1 n a i , k x k ∣ f(A\vec{x})=\sum_{i=1}^{n}\left | \sum_{k=1}^{n}a_{i,k}x_{k} \right | f(Ax )=i=1nk=1nai,kxk

    ⩽ ∑ i = 1 n ( ∑ k = 1 n ∣ a i , k ∣ ∣ x k ∣ ) \leqslant \sum_{i=1}^{n} \left ( \sum_{k=1}^{n} \left | a_{i,k} \right | \left | x_{k} \right | \right ) i=1n(k=1nai,kxk)

    = ∑ i = 1 n ( ∑ k = 1 n ∣ a i , k ∣ ∑ k = 1 n ∣ x k ∣ ) =\sum_{i=1}^{n}\left ( {\sum_{k=1}^{n}\left | a_{i,k} \right |}{\sum_{k=1}^{n}\left | x_{k} \right |} \right ) =i=1n(k=1nai,kk=1nxk)

    = ∑ i = 1 n ∑ k = 1 n ∣ a i , k ∣ ⋅ ∑ i = 1 n ∑ k = 1 n ∣ x k ∣ =\sum_{i=1}^{n}\sum_{k=1}^{n}\left | a_{i,k} \right | \cdot \sum_{i=1}^{n}\sum_{k=1}^{n}\left | x_{k} \right | =i=1nk=1nai,ki=1nk=1nxk

    = ∑ i = 1 n ∑ k = 1 n ∣ a i , k ∣ ⋅ ∑ k = 1 n ∣ x k ∣ =\sum_{i=1}^{n}\sum_{k=1}^{n}\left | a_{i,k} \right | \cdot \sum_{k=1}^{n}\left | x_{k} \right | =i=1nk=1nai,kk=1nxk

    = f ( A ) f ( x ⃗ ) =f(A)f(\vec{x}) =f(A)f(x )


    举例: 证明矩阵的Frobenius范数和向量的 L 2 L_2 L2范数是相容的。

    因为 f F ( A ) = ∑ i , j A i , j 2 f_{F}(A)=\sqrt{\sum_{i,j}A_{i,j}^{2}} fF(A)=i,jAi,j2 L 2 = ∑ i = 1 n x i 2 2 L_2=\sqrt[2]{\sum_{i=1}^{n}x_i^2} L2=2i=1nxi2

    f F ( A x ⃗ ) = ∑ i , j ( a i , j x j ) 2 f_{F}(A\vec{x})=\sqrt{\sum_{i,j}(a_{i,j}x_j)^{2}} fF(Ax )=i,j(ai,jxj)2

    ⩽ ∑ i , j ( a i , j ) 2 ⋅ ∑ i , j ( x j ) 2 \leqslant \sqrt{\sum_{i,j}(a_{i,j})^{2}\cdot \sum_{i,j}(x_{j})^{2}} i,j(ai,j)2i,j(xj)2

    = ∑ i , j ( a i , j ) 2 ∑ i , j ( x j ) 2 =\sqrt{\sum_{i,j}(a_{i,j})^{2}}\sqrt{\sum_{i,j}(x_{j})^{2}} =i,j(ai,j)2 i,j(xj)2

    = ∑ i , j ( a i , j ) 2 ∑ j ( x j ) 2 =\sqrt{\sum_{i,j}(a_{i,j})^{2}}\sqrt{\sum_{j}(x_{j})^{2}} =i,j(ai,j)2 j(xj)2

    = f F ( A ) f F ( x ⃗ ) =f_{F}(A)f_{F}(\vec{x}) =fF(A)fF(x )


    参考资料

    [1] 向量/矩阵范数 https://wenku.baidu.com/view/2c1f918608a1284ac950430c.html

    [2] 向量范数 https://wenku.baidu.com/view/36f5809a1b37f111f18583d049649b6648d709ed.html

    [3] 矩阵范数 https://baike.baidu.com/item/矩阵范数/5296169?fr=aladdin

    [4] Frobenious范数 http://mathworld.wolfram.com/FrobeniusNorm.html

    [5] 相容性 https://baike.baidu.com/item/范数

    展开全文
  • 几种常用范数与距离的关系

    万次阅读 2017-10-14 15:51:38
    1 范数 向量的范数可以简单形象的理解为向量的长度,或者向量到零点的距离,或者相应的两个点之间的距离。...常用的向量的范数: L1范数: ||x|| 为x向量各个元素绝对值之和。 L2范数: ||x||为x向量各

    1 范数

    向量的范数可以简单形象的理解为向量的长度,或者向量到零点的距离,或者相应的两个点之间的距离。

    向量的范数定义:向量的范数是一个函数||x||,满足非负性||x|| >= 0,齐次性||cx|| = |c| ||x|| ,三角不等式||x+y|| <= ||x|| + ||y||。

    常用的向量的范数:
    L1范数:  ||x|| 为x向量各个元素绝对值之和。
    L2范数:  ||x||为x向量各个元素平方和的1/2次方,L2范数又称Euclidean范数或者Frobenius范数
    Lp范数:  ||x||为x向量各个元素绝对值p次方和的1/p次方

    L∞范数:  ||x||为x向量各个元素绝对值最大那个元素的绝对值,如下:


    椭球向量范数: ||x||A  = sqrt[T(x)Ax], T(x)代表x的转置。定义矩阵C 为M个模式向量的协方差矩阵, 设C’是其逆矩阵,则Mahalanobis距离定义为||x||C’  = sqrt[T(x)C’x], 这是一个关于C’的椭球向量范数。

    2 距离

    欧式距离(对应L2范数):最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中。n维空间中两个点x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)间的欧氏距离:

    也可以用表示成向量运算的形式:

    曼哈顿距离:曼哈顿距离对应L1-范数,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。

    切比雪夫距离,若二个向量或二个点x1和x2,其坐标分别为(x11, x12, x13, … , x1n)和(x21, x22, x23, … , x2n),则二者的切比雪夫距离为:d = max(|x1i - x2i|),i从1到n。对应L∞范数。

    闵可夫斯基距离(Minkowski Distance)闵氏距离不是一种距离,而是一组距离的定义。对应Lp范数,p为参数。

    闵氏距离的定义:两个n维变量(或者两个n维空间点)x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)间的闵可夫斯基距离定义为: 

    其中p是一个变参数。

    当p=1时,就是曼哈顿距离,

    当p=2时,就是欧氏距离,

    当p→∞时,就是切比雪夫距离,       

    根据变参数的不同,闵氏距离可以表示一类的距离。 

    Mahalanobis距离:也称作马氏距离。在近邻分类法中,常采用欧式距离和马氏距离。


    3 在机器学习中的应用

    L1范数和L2范数,用于机器学习的L1正则化、L2正则化。对于线性回归模型,使用L1正则化的模型建叫做Lasso回归,使用L2正则化的模型叫做Ridge回归(岭回归)。

    其作用是:

    L1正则化是指权值向量w中各个元素的绝对值之和,可以产生稀疏权值矩阵(稀疏矩阵指的是很多元素为0,只有少数元素是非零值的矩阵,即得到的线性回归模型的大部分系数都是0. ),即产生一个稀疏模型,可以用于特征选择;

    L2正则化是指权值向量w中各个元素的平方和然后再求平方根,可以防止模型过拟合(overfitting);一定程度上,L1也可以防止过拟合。

    至于为什么L1正则化能增加稀疏性,L2正则化能防止过拟合,原理可查看参考资料。


    参考资料:

    http://blog.csdn.net/v_july_v/article/details/8203674

    http://blog.csdn.net/jinping_shi/article/details/52433975

    展开全文
  • 常用范数公式【转载】

    千次阅读 2019-03-31 09:35:00
    转自:https://wenku.baidu.com/view/11b07d293169a4517723a3f4.html 转载于:https://www.cnblogs.com/BlueBlueSea/p/10630262.html
  • 1、范数简介 范数是具有“长度”概念的函数。在向量空间内,为所有的向量的赋予非零的增长度或者大小。不同的范数,所求的向量的长度或者大小是不同的。 1.1 范数分类 向量范数 矩阵范数: 1.2 向量范数的定义 ...
  • 1范数 把R2空间中向量长度的概念推广到更一般的线性空间中,可以得到更一般的具有长度的概念,需要满足下列公理: p范数 以n维空间向量为例,x=(ξ1,ξ2,…,ξn)∈Rn,通常定义如下范数 ∣∣x∣∣p=(∑k=1n∣ξi∣p)...
  • 常用矩阵范数

    千次阅读 2018-12-04 17:02:32
    (1)矩阵的核范数:矩阵的奇异值(将矩阵svd分解)之和,这个范数可以用来低秩表示(因为最小化核范数,相当于最小化矩阵的秩——低秩);   (2)矩阵的L0范数:矩阵的非0元素的个数,通常用它来表示稀疏,L0...
  • 范数

    2019-11-01 19:56:30
    范数范数定义常用范数对偶范数 范数定义 范数(norm)是数学中的一种基本概念。在泛函分析中,它定义在赋范线性空间中,并满足一定的条件,即①非负性;②齐次性;③三角不等式。它常常被用来度量某个向量空间(或矩阵...
  • 二、常用范数有哪些?1、向量范数1-范数: 向量元素绝对值之和∣∣x∣∣1=∑i=1N∣xi∣ ||x||_1 = \sum_{i=1}^N|x_i| ∣∣x∣∣1​=i=1∑N​∣xi​∣2-范数:向量元素绝对值的平方和再开方∣∣x∣∣2=∑i=1Nxi2||\...
  • 常用范数求导

    万次阅读 多人点赞 2016-12-14 11:01:44
    矢量范数的偏导数 L1范数不可微。但是存在次梯度,即是次微分的,这里先不写。 L2 范数: ∂∂x||x−a||2=x−a||x−a||2\begin{equation} \frac{\partial }{\partial \mathbf x }||\mathbf x- \mathbf a||_2 =\frac...
  • 文章目录为何引入向量范数一、向量范数向量加权范数向量范数的等价性定理常用范数的等价关系二、矩阵范数m1m_{1}m1​ -范数 和F -范数谱三、矩阵范数与向量范数的相容算子范数矩阵范数具有向量范数的一切性质...
  • 向量范数、矩阵范数

    千次阅读 2016-10-18 20:21:27
    本篇文章主要是对常用范数进行一个系统的总结。内容主要来自于矩阵论这本书和知乎上’魏通‘的回答,本文进行了补充和总结。知乎’魏通‘关于范数的回答 范数是内积空间中长度概念的推广。 注意:如果V是...
  • 学生,程序员
  • 常用向量和矩阵的范数

    千次阅读 2016-03-24 10:49:42
    向量的范数任意x∈Cnx \in C^n,设x=(ξ1,ξ12,...... , \xi _{n})^{T},常用范数有 1. 2-范数∥x∥2=(∑i=1n|ξi|2)12\|x\|_{2}=(\sum _{i=1}^{n}|\xi _i|^2)^{\frac{1}{2}} 2. 1-范数∥x∥1=∑i=1n|ξi|\|x\|_{1}

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,367
精华内容 5,746
关键字:

常用范数