首页 > 代码库 > 六、降维

六、降维

降维[Dimensionality Reduction]:
降维 是减少变量数量的过程。它可以用来从含有噪声的未加工特征中提取潜在特征,或者在维持原来结构的情况下压缩数据。MLlib提供了类RowMatrix 上的降维支持。
 
奇异值分解 (SVD):
奇异值分解(SVD)将一个矩阵分解为三个矩阵:U, Σ, 和V ,三个矩阵满足条件:
A=UΣVT,A=UΣVT,
U是正交矩阵,该矩阵的列称为左奇异向量。
Σ 是对角矩阵,对角线上的元素降序排列,对角线上的每个值称为奇异值。
V是正交矩阵,该矩阵的列称为右奇异向量。
对于大型举证,我们通常不需要完全分解,而是求解最大的几个奇异值以及对应的奇异向量即可。这样做可以节省存储空间、降噪以及恢复矩阵的低秩结构。
 
如果我们保留top k 个奇异值,那么结果中的低秩矩阵的维度如下:
 
UU: m×km×k,
ΣΣ: k×kk×k,
VV: n×kn×k.

 

性能:
假设n小于m。奇异值和右奇异向量来自Gramian矩阵(ATA)的特征值和特征向量。存储左奇异矩阵的向量是U,通过矩阵乘法U = A(VS-1)得到(指定ComputeU参数)。实际使用的方法基于计算开销自动选择。
 
  如果n比较小(n < 100)或者k相对于n比较大(k > n/2),我们先计算Grimian矩阵,然后在本地驱动程序中计算最大的特征值和特征向量。这需要一趟遍历,在执行器和驱动程序上的空间复杂度O(n2),在驱动程序上的时间复杂度O(n2k)。
 
否则,我们分布式计算 (ATA)v 并交给ARPACK(大规模特征值计算程序包)去计算最大的特征值以及特征向量。这需要O(k)次遍历,执行器上O(n)的存储空间以及驱动程序上O(nk)存储空间。
 
import java.util.LinkedList;

import org.apache.spark.api.java.*;
import org.apache.spark.mllib.linalg.distributed.RowMatrix;
import org.apache.spark.mllib.linalg.Matrix;
import org.apache.spark.mllib.linalg.SingularValueDecomposition;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;
import org.apache.spark.rdd.RDD;
import org.apache.spark.SparkConf;
import org.apache.spark.SparkContext;

public class SVD {
  public static void main(String[] args) {
    SparkConf conf = new SparkConf().setAppName("SVD Example");
    SparkContext sc = new SparkContext(conf);
     
    double[][] array = ...
    LinkedList<Vector> rowsList = new LinkedList<Vector>();
    for (int i = 0; i < array.length; i++) {
      Vector currentRow = Vectors.dense(array[i]);
      rowsList.add(currentRow);
    }
    JavaRDD<Vector> rows = JavaSparkContext.fromSparkContext(sc).parallelize(rowsList);

    // Create a RowMatrix from JavaRDD<Vector>.
    RowMatrix mat = new RowMatrix(rows.rdd());

    // Compute the top 4 singular values and corresponding singular vectors.
    SingularValueDecomposition<RowMatrix, Matrix> svd = mat.computeSVD(4, true, 1.0E-9d);
    RowMatrix U = svd.U();
    Vector s = svd.s();
    Matrix V = svd.V();
  }
}

 

主成分分析(PCA):
 
主成分分析 (PCA)是寻找坐标旋转的一种统计方法,该方法可以使得:样本点在第一个坐标上拥有最大的方差,后续坐标依次拥有次大的方差。其中用到的旋转矩阵的列称为主成分。PCA在降维中有广泛应用。
 
补充:
 
主成分分析的一般计算步骤:
 
1.  数据标准化:设样本数为m,每个样本特征维度为n, 在每个维度上计算均值u和方差δ2(。然后令归一化特征值:  x’ = (x – u)/δ
 
2. 求协方差矩阵(也有的地方计算相关系数矩阵)。
 
3. 求协方差矩阵的特征值和特征向量。
 
4. 将特征值从大到小排序,取最大的k个特征值,然后将对应的k个特征向量的作为列向量组成矩阵。k 值的确定参考当前累计特征值的和占特征值总和的比例,一般要求在85%以上。
 
5. 投影:将归一化之后的样本点投影到选取的特征向量上。ResultDataMatrix(m, k)  = NormalizedDataMatrix(m, n) * EigenVectorsMatix(n * k)
 
import java.util.LinkedList;

import org.apache.spark.api.java.*;
import org.apache.spark.mllib.linalg.distributed.RowMatrix;
import org.apache.spark.mllib.linalg.Matrix;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;
import org.apache.spark.rdd.RDD;
import org.apache.spark.SparkConf;
import org.apache.spark.SparkContext;

public class PCA {
  public static void main(String[] args) {
    SparkConf conf = new SparkConf().setAppName("PCA Example");
    SparkContext sc = new SparkContext(conf);
     
    double[][] array = ...
    LinkedList<Vector> rowsList = new LinkedList<Vector>();
    for (int i = 0; i < array.length; i++) {
      Vector currentRow = Vectors.dense(array[i]);
      rowsList.add(currentRow);
    }
    JavaRDD<Vector> rows = JavaSparkContext.fromSparkContext(sc).parallelize(rowsList);

    // Create a RowMatrix from JavaRDD<Vector>.
    RowMatrix mat = new RowMatrix(rows.rdd());

    // Compute the top 3 principal components.
    Matrix pc = mat.computePrincipalComponents(3);
    RowMatrix projected = mat.multiply(pc);
  }
}

 

 

六、降维