15 Matching Annotations
  1. Mar 2023
  2. Jul 2019
    1. in clustering analyses, standardization may be especially crucial in order to compare similarities between features based on certain distance measures. Another prominent example is the Principal Component Analysis, where we usually prefer standardization over Min-Max scaling, since we are interested in the components that maximize the variance

      Use standardization, not min-max scaling, for clustering and PCA.

  3. Jun 2019
    1. PCA

      Principal component analysis (PCA) is a statistical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables (entities each of which takes on various numerical values) into a set of values of linearly uncorrelated variables called principal components.

    1. Variables that are correlated with PC1 (i.e., Dim.1) and PC2 (i.e., Dim.2) are the most important in explaining the variability in the data set.
    2. The cos2 values are used to estimate the quality of the representation The closer a variable is to the circle of correlations, the better its representation on the factor map (and the more important it is to interpret these components) Variables that are closed to the center of the plot are less important for the first components.
    3. Taken together, the main purpose of principal component analysis is to: identify hidden pattern in a data set, reduce the dimensionnality of the data by removing the noise and redundancy in the data, identify correlated variables
    4. the amount of variance retained by each principal component is measured by the so-called eigenvalue.
    5. These new variables correspond to a linear combination of the originals. The number of principal components is less than or equal to the number of original variables.
    6. Principal component analysis is used to extract the important information from a multivariate data table and to express this information as a set of few new variables called principal components.
    1. Thus, when we say that PCA can reduce dimen-sionality, we mean that PCA can compute princi-pal components and the user can choose the smallestnumberKof them that explain 0.95 of the variance.A subjectively satisfactory result would be whenKis small relative to the original number of featuresD.
  4. Mar 2019
  5. Sep 2018
    1. PCA - Another point of view

      Basic Component can ba analogy to sample after projection

      可以从比较形象的角度来理解 PCA,之前的角度是从x -> z , PCA 其本质就是一个线性函数,把 x 空间中一点,转换到 z 空间中一点。

      $$ img_{28*28} \rightarrow x = \begin{vmatrix} 204 \\ 102 \\ 0 \\ 1 \\ . \\ . \\ . \end{vmatrix}^{784*1} \rightarrow z = \begin{vmatrix} 1 \\ 0.5 \\ 0 \\ 1 \\ 0.3 \end{vmatrix} $$

      如果把 z 的每一位都看成是某种笔画的系数,那么我们就可以用另外一种方式来表示一张图片:

      $$ x - \bar{x} \approx c_1u_1 + c_2u_2 + ... + c_ku_k = \hat{x} $$

      • \(c_i\) is the component of x which is an image
      • \(u_i\) is factor of each component
      • \(x\) is img;
      • \(\bar{x}\) is average color degree of pixels;
      • \(\hat{x}\) is the combination of components of a digit.
      • \(x-\bar{x}\) is a normalization to make average degree of color of an image to be 0
      • \(||(x-\bar{x})-\hat{x}||_2\) is reconstruction error

      这就提供了另一种看待问题的视角:

      • 原始PCA 是通过找到一个方向 w,它能最大化投影之后的Variance
      • Components-PCA 是通过找到各个Components的系数,它能最小化 reconstruction error

      于是优化目标的函数也就改变了:

      • 原始 PCA:

      $$ argmax_{w_i} Var(x) = \sum_x(x-\bar{x})^2, with\ ||w_i||_2 = 1, and\ w_i \cdot \{w_j\}_{j=1}^{i-1} = 0 $$

      • Components-PCA:

      \(argmin_{u_1, ..., u_K}\sum||(x-\bar{x}) - (\sum_{k=1}^Kc_ku_k)||_2\)

      \(\sum_{k=1}^Kc_ku_k = \hat{x}\)

      可以证明的是:这个 \(\{u_k\}_{k=1}^K\) 就是我们要找的 \(\{w_k\}_{k=1}^K\)

      $$ \begin{vmatrix} z_1 \\ z_2 \\ . \\. \\. \\z_K \end{vmatrix} = \begin{vmatrix} w_1 \\ w_2 \\ . \\. \\. \\w_K \end{vmatrix} x = \begin{vmatrix} u_1 \\ u_2 \\ . \\. \\. \\u_K \end{vmatrix} x $$

      证明 u = w

      $$ x^1 - \bar{x} \approx c_1^1u^1 + c_2^1u^2 + ... $$

      $$ x^2 - \bar{x} \approx c_1^2u^1 + c_2^2u^2 + ... $$

      $$ x^3 - \bar{x} \approx c_1^3u^1 + c_2^3u^2 + ... $$

      • \(x^i\) : 第 i 个样本
      • \(c_k^i\) : 第 i 个样本的第 k 个 component 的系数(权重)
      • \(u^k\): 第 k 个 component

      【注意】component 对任意样本都是一样的,样本之间不同的是component的系数(权重)

      我们可以把上面 3 个式子组合成矩阵的形式:

      对于单个样本

      可以写成 向量 = 矩阵 * 向量

      $$ c_1^2u^1 + c_2^2u^2 + ... = \sum_{k=1}^Kc_k^1u^k = [u^1, u^2, ...] \cdot \begin{vmatrix}c_1^1\\c_2^1\\.\\.\\.]\end{vmatrix} $$

      把所有样本都组合起来

      可以写成 矩阵 = 矩阵 * 矩阵

      $$ \underbrace{[x^1 - \bar{x}, x^2-\bar{x}, x^3-\bar{x}, ...]}_{\text{dataset:X}} \approx \underbrace{[u^1, u^2, ...]}_{\text{components matrix}} \cdot \underbrace{ \begin{vmatrix} c_1^1 & c_1^2 & c_1^3\\ c_1^1 & c_1^2 & c_1^3\\ c_1^1 & c_1^2 & c_1^3\\ .&.&.\\ .&.&.\\ .&.&. \end{vmatrix}}_{\text{factor matrix}} \text{how to find the best u to make two side of approx as near as possible?} $$

      我们可以使用 SVD 矩阵分解,对 X 进行分解:

      X 可以分解成3个矩阵的乘积:

      \(X_{m*n} \approx U_{m*k} \Sigma_{k*k}V_{k*n}\)

      • m : the dimension of one sample
      • n : the size of dataset
      • k : number of components

      这里直接给出答案,具体过程见线性代数课程。

      K columns of U: a set of orthonormal eigen vectors corresponding to the k largest eigenvalues of \(XX^T\)

      这个 \(XX^T\) 就是 \(Cov(x)\) , 因为这里的 X 是由 \(x - \bar{x}\) 得到的。所以,u = w。

      再回忆下我们对于 u w 和 z 的定义:

      • u : components of x (eg, 数字的笔画)
      • w : 线性函数矩阵 W 用于做 \(z = W^Tx\) 投影
      • z : 投影之后的“新”的样本

      启示:PCA 找出的那些 w(转换矩阵 W 的 columns) 就是 components

    2. Dimension Reduction 为什么可能是有用的?

      一,例子1 为什么 Dimension Reduction 可能是有用的,如下图示:

      Manifold

      如果我们用 3 dimension 的样本维度去描述他其实是非常浪费的,因为很明显他是卷曲在一起的,如果我们有办法把他展平,不同类型(不同颜色代表不同类型)就很容易区隔开,而展平之后我们只需要 2 dimension 的样本维度。所以根本不需要把这个问题放在 3d 中去考虑,2d 就可以了。

      Manifold and dimension reduction by various methods

      二,例子2

      在手写数字辨识的任务中,你或许根本用不到 28*28 的维度,比如数字 3 他可能有很多形态,但其实大部分都是旋转一下角度而已,所以对于辨识 3 这件事可能需要的维度仅仅是一个旋转角度而已(1维度)

      如何做 dimension reduction 呢?

      对数据降维就是找一个function

      \(f(x) \rightarrow x', dim(x) >> dim(x')\)

      一,方法1: feature selection (略)

      二,方法2:PCA

      基本原理

      PCA 的本质就是通过一个一次线性函数 \(W^Tx\)把高维度的数据样本转换为低维度的数据样本。就像 \(w^Tx\) 如果\(W^T\)矩阵只有一行,这个函数就是两个向量的内积 --- 结果是一个(一维)数值,如果 \(W^T\) 是一个矩阵,那么 \(W^T\) 有多少行最终内积结果就有多少维

      $$ R_W^{1*N} \cdot R_x^{N*1} = R_{x'}^{1*1} R_W^{2*N} \cdot R_x^{N*1} = R_{x'}^{2*1} ... $$

      \(f(x) \rightarrow x', dim(x) >> dim(x')\)

      \(z = Wx, to\ find\ 'W'\)

      找到优化问题 --- projection has max variance

      该如何找到 W 呢,从最简单的开始,我们假设 :

      • reduce x to 1 D vector z, means that 'z' is a digit
      • 'W' matrix only have ONE row
      • this row's L2 norm is equal to 1: \(||w^1||_2=1\).

      如此一来,'z' 就可以看做是 'x' 在 'w' 方向上的投影(内积的几何意义)

      所有的 x: \(x^1, x^2, x^3,...\) 都在 w 方向上做投影就得到了 z: \(z^1, z^2, z^3,...\) , 而我们要做的就是从:

      如何找到 W 变成 找到一个 x 的更好的投影方向

      we want the variance of \(z_1\) as large as possible.

      variance 在图像上的表现就是,投影之后的 z 的取值范围(值域)取值范围越大variance越大

      对于投影到一维空间,找到最佳的 w('w' is a row vector) 使得 x('x' is N dimension) 投影到该方向得到的 z ('z' is a digit)的 variance 是最大的, 用公式表示就是:

      \(find\ a\ w\ to\ maximize:\)

      \(Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2)\)

      \(with\ constaint\ :\ ||w_1||_2=1\)

      对于投影到二维(甚至多维)空间,我们要给每个后面的w一个限制就是: 后面的 w(n+1 th row) 要跟前面的所有 w({1~n} rows) 相互垂直, \(w_{n+1} \cdot \{w_{i}\}_{i=1}^n = 0\).

      整体来看就是:

      the 1st row of W should be:

      \(w_1 = argmax(Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2)\)

      \(constraint:\ ||w_1||_2=1\)

      the 2nd row of W should be:

      \(w_2 = argmax(Var(z_2) = \sum_{z_2}(z_2 - \bar{z_2})^2)\)

      \(constraint:\ ||w_2||_2=1, w_2 \cdot w_1 = 0\)

      the 3rd row of W should be:

      \(w_3 = argmax(Var(z_3) = \sum_{z_3}(z_3 - \bar{z_3})^2)\)

      \(constraint:\ ||w_3||_2=1, w_3 \cdot w_1 = 0, w_3 \cdot w_2 = 0\)

      .......

      then the W should be:

      $$ W = \begin{vmatrix} (w_1)T \\ (w_2)T \\ . \\ . \\ . \end{vmatrix}\quad $$

      这里 W 会是一个 Orthogonal matrix, 因为每一行的 norm 都等于1,并且行行之间相互垂直。

      求解这个带限制条件优化问题 ---- 拉格朗日乘数法

      Lagrange multiplier 可以把带限制条件的优化问题转换>为无限制优化问题: target - a(zero_form of >constraint1) - b(zero_form of constraint2)

      无限制的优化问题,就可以通过偏微分=0来找到最优解

      如果 W 矩阵只有一行

      $$ one\ x\ one\ z_1 \bar{z_1} = \sum{z_1} = \sum{w_1 \cdot x} = w_1 \cdot \sum x = w_1 \cdot \bar{x} Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 $$

      对于 \(w \cdot (x - \bar{x})\), 他是两个向量的内积,对于这种内积的平方,要注意如下的惯用转换公式(值得记住)。

      $$ (a \cdot b)^2 = (a^Tb)^2 $$

      因为 \(a \cdot b\) 是内积,是一个数值,数值的平方无关乎顺序,所以可以写成:

      $$ (a^Tb)^2 = a^Tba^Tb $$

      因为 \(a \cdot b\) 是内积,是一个数值,数值的转置还是自身,所以可以写成:

      $$ (a^Tba^Tb = a^Tb(a^Tb)^T $$

      化简之后:

      $$ a^Tb(a^Tb)^T = a^Tbb^Ta $$

      所以之前 var 的式子可以化简为:

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 $$

      因为是对 x 来求和,所以 w 可以提出去:

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 = (w_1)^T(\sum_x(x-\bar{x})(x-\bar{x})^T)w_1 $$

      其中 \(\sum_x(x-\bar{x})(x-\bar{x})^T\) 是什么,这个是 x 向量(样本都是向量)的 covariance matrix. covariance 是对称且半正定对的, 也就是说所有的 eigenvalues 都是非负的

      $$ Var(z_1) = \sum_{z_1}(z_1 - \bar{z_1})^2 = \sum_x(w_1 \cdot x - w_1 \cdot \bar{x})^2 = \sum_x(w_1 \cdot (x-\bar{x}))^2 = \sum_x(w_1)^T(x-\bar{x})(x-\bar{x})^Tw_1 = (w_1)^T(\sum_x(x-\bar{x})(x-\bar{x})^T)w_1 = (w_1)^TCov(x)w_1 $$

      我们设 \(S = Cov(x)\) ,于是我们得到了一个新的优化问题:

      find w1 maximizing:

      \(w_1^T S w_1, with\ constraint\ ||w_1||_2 = 1, means\ w_1^Tw_1 = 1\)

      Lagrange multiplier is target - zero_form of constraints

      之前说明过 \(w_1\) 是 W 矩阵的第一个row,再次提醒下。

      \(g(w_1) =w_1^TSw_1 - \alpha(w_1^Tw_1 - 1)\)

      \(\frac{\partial g(w_1)}{\partial w_{11}} = 0\)

      \(\frac{\partial g(w_1)}{\partial w_{12}} = 0\)

      ....

      通过对 Lagrange 式子 \(g(w_1)\) 的微分为0来求最大最优的w,可以得到如下化简后的式子:

      \(Sw_1 - \alpha w_1 = 0\)

      \(Sw_1 = \alpha w_1\)

      这种形式我们就熟悉了,\(w_1\) 是 S 的 eigen vector

      但是这样的 w1 有很多,因为 S 的 eigen vector 有很多,所以 w1 的潜在选择也很多,哪一个是最好的选择呢?通过我们的优化目标来判断。

      \(w_1^TSw_1 = \alpha w_1^Tw_1 = \alpha\)

      而这里的 \(\alpha\) 是 eigen value,

      所以,因为我们要最大化的目标最后等于 alpha, 而 alpha 是 eigen value, 所以我们选择最大的 eigen value, 一个 eigen value 对应一个 eigen vector, 所以最优的 w1 就是最大的 eigen value 对应的那个 eigen vector.

      之前分析过, Find w2 的情况与 Find w1 略有不同,不同在优化问题的限制条件多出一个与之前所有的w都垂直,那么就是:

      \(Find\ w_2\ maximizing: w_2^TSw_2, w_2Tw_2=1, w_2^Tw_1=0\)

      按照 目标函数 - 系数*zero_form of 限制条件 的拉格朗日使用方法,可以得到如下无限制条件的优化问题:

      如果 W 矩阵有多行

      对于 W 矩阵有多行的情况,优化目标函数需要改变, 要增加限制条件,如果不加改变的话你得到的 wn 永远与 w1 一样,增加的这个限制条件是:后面的每个w都要与前面的所有w相互垂直 --- 内积为0

      \(Find\ w_2\ maximizing:\)

      $$ g(w_2) = w_2^TSw_2 - \alpha(w_2^Tw_2-1)-\beta(w_2^Tw_1-0) $$

      同样的通过微分等于0来求无限制条件的优化问题:

      \(\frac{\partial g(w_1)}{\partial w_{11}} = 0\)

      \(\frac{\partial g(w_1)}{\partial w_{12}} = 0\)

      化简上述结果可以得到:

      \(Sw_2 - \alpha w_2 - \beta w_1 = 0\)

      上述等式两边同时乘以 w1:

      \(w_1^TSw_2 - \alpha w_1^Tw_2 - \beta w_1^Tw_1 = 0\)

      \(w_1^TSw_2 - \alpha * 0 - \beta * 1 = 0\)

      因为 \(w_1^TSw_2\) 本身是一个 向量矩阵向量 的形式,他是一个数值,数值的转置还是自身:

      \(w_1^TSw_2 = (w_1STw_2)^T = w_2^TS^Tw_1\)

      因为 S 是 Covariance Matrix of x, 是对称的,所以 \(S^T=S\)

      \(w_2^TS^Tw_1= w_2^TSw_1\)

      使用 w1 的结论,\(Sw_1 = \lambda_1w_1\), 所以有

      \(w_2^TSw_1=\lambda_1w_2^Tw_1=0\)

      所以,综合起来看:

      \(w_1^TSw_2 - \alpha w_1^Tw_2 - \beta w_1^Tw_1 = 0\)

      \(w_1^TSw_2 - \alpha * 0 - \beta * 1 = 0\)

      \(0 - \alpha * 0 - \beta * 1 = 0\)

      所以:

      \(\beta=0\)

      所以:

      \(Sw_2 - \alpha w_2= 0\)

      \(Sw_2 = \alpha w_2\)

      由于 w2 也是 eigen vector, 同样有很多选择,与 w1 选择的依据一样,我们只能选择剩下最大的那个 eigenvalue of S 对应的 eigenvector

      so,结论是:

      $$ z = Wx $$

      $$ W = \begin{vmatrix} (w_1)T \\ (w_2)T \\ . \\ . \\ . \end{vmatrix}\quad $$

      $$ W = \begin{vmatrix} 1st\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ 2nd\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ 3rd\ largest\ eigenvalues'\ eigenvector\ of\ Cov(x) \\ ...\end{vmatrix} $$

      PCA 的副产品 --- 降维后数据点的各个维度互相垂直

      数据点的各个维度互相垂直

      用数学语言来表述就是

      数据点的协方差矩阵是一个 Diagonal matrix

      也就是

      数据点的各个维度之间没有 correlation

      这样有什么作用呢?

      一个很好的作用是,原来的 data 经过 PCA 之后输出的新的 data 可以接其他较为简单的(或是对数据点维度要求无 correlation 的)model ---> eg. Naive Bayes.

      如何证明呢?

      $$ Cov(z) = \sum(z - \bar{z})(z-\bar{z})^T $$

      这一项,可以可以展开合并后成为下面这种形式:

      $$ Cov(z) = \sum(z - \bar{z})(z-\bar{z})^T = WSW^T,\ \ S = Cov(x) $$

      $$ W^T=\begin{vmatrix} w_1 \\ .\\.\\.\\ w_k \end{vmatrix}^T= [w_1, ..., w_k] $$

      注意转置之前 w1 是 W矩阵的行向量,转置后,w1 是 W^T 的 列向量:

      $$ \begin{vmatrix} 1 & 2 & 3 & \rightarrow w_1\\ 4 & 5 & 6 & \rightarrow w_2 \\ 7 & 8 & 9 & \rightarrow w_3 \end{vmatrix}^T \rightarrow \begin{vmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \downarrow & \downarrow & \downarrow \\ w_1 & w_2 & w_3 \end{vmatrix} $$

      $$ WSW^T = WS[w_1, ..., w_k] = W[Sw_1, ..., Sw_k] $$

      利用之前的结论:

      \(Sw_1 = \lambda_1 w_1\)

      $$ W[Sw_1, ..., Sw_k] = W[\lambda_1 w_1, ..., \lambda_k w_k] = [\lambda_1Ww_1, ..., \lmabda_kWw_k] = [\lambda_1e_1, ..., \lambda_ke_k] $$

      其中 \(e_i\) 是指第 \(i\) 位为 1, 其余位都为 0 的列向量。

      所以 \(Cov(z)\) 就是一个 Diagonal matrix.

      总结

      PCA 关键词:

      • linear function, projection
      • maximize Variance of z
      • Covariance Matrix of x
      • eigenvector of Covariance Matrix

      一个重要的结论需要记住: Covariance Matrix is a symmetric, positive-semidefinite matrix, so it has non-negative eigenvalues

      一个重要的技术:

      带限制条件优化

      --- Lagrange multiplier ---> 无限制条件优化

      --- partial dirivitive = 0 --->

      求解。

      一个重要的机器学习常识:

      数据点的各个维度互相垂直

      用数学语言来表述就是

      数据点的协方差矩阵是一个 Diagonal matrix

      也就是

      数据点的各个维度之间没有 correlation

  6. Sep 2017
    1. The projection score - an evaluation criterion for variable subset selection in PCA visualization

      "variable" typically means gene or locus in the context of biological data.