• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Spark机器学习库指南[Spark 1.3.1版]——降维(Dimensionality Reduction)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

下面是章节降维的内容(其他内容参见全文目录)

  • 奇异值分解 (SVD)
    • 性能
    • SVD示例
  • 主成分分析 (PCA)

降维 是减少变量数量的过程。它可以用来从含有噪声的未加工特征中提取潜在特征,或者在维持原来结构的情况下压缩数据。MLlib提供了类RowMatrix 上的降维支持。

奇异值分解 (SVD)

奇异值分解(SVD)将一个矩阵分解为三个矩阵:U, Σ, 和V ,三个矩阵满足条件:

A = U Σ VT

  • U是正交矩阵,该矩阵的列称为左奇异向量。
  • Σ 是对角矩阵,对角线上的元素降序排列,对角线上的每个值称为奇异值。
  • V是正交矩阵,该矩阵的列称为右奇异向量。

对于大型举证,我们通常不需要完全分解,而是求解最大的几个奇异值以及对应的奇异向量即可。这样做可以节省存储空间、降噪以及恢复矩阵的低秩结构。


 

补充:

1. 奇异值的另外一种定义:A*A的非负特征值得平方根,其中A*是A的共轭转置矩阵(当矩阵元素为实数,共轭转置矩阵就是转置矩阵)。

2.


 

如果我们保留top k 个奇异值,那么结果中的低秩矩阵的维度如下:

  • U: m×k,
  • Σ: k×k,
  • V: n×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)存储空间。

SVD 示例(Scala)

MLlib针对行矩阵提供了SVD功能,提供支持的类是RowMatrix 。

import org.apache.spark.mllib.linalg.Matrix
import org.apache.spark.mllib.linalg.distributed.RowMatrix
import org.apache.spark.mllib.linalg.SingularValueDecomposition

val mat: RowMatrix = ...

// Compute the top 20 singular values and corresponding singular vectors.
val svd: SingularValueDecomposition[RowMatrix, Matrix] = mat.computeSVD(20, computeU = true)
val U: RowMatrix = svd.U // The U factor is a RowMatrix.
val s: Vector = svd.s // The singular values are stored in a local dense vector.
val V: Matrix = svd.V // The V factor is a local dense matrix.

 

主成分分析 (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)


 

MLlib中使用行矩阵来支持PCA。

下面的代码(Scala)说明了怎样在RowMatrix上计算主成分并使用主成分将特征映射到低维空间。

import org.apache.spark.mllib.linalg.Matrix
import org.apache.spark.mllib.linalg.distributed.RowMatrix

val mat: RowMatrix = ...

// Compute the top 10 principal components.
val pc: Matrix = mat.computePrincipalComponents(10) // Principal components are stored in a local dense matrix.

// Project the rows to the linear space spanned by the top 10 principal components.
val projected: RowMatrix = mat.multiply(pc)

 

参考:

[1] http://www.cnblogs.com/jerrylead/archive/2011/04/18/2020209.html

[2] http://baike.baidu.com/picture/45376/45376/0/e850352ac65c1038ef0358deb0119313b07e89a9.html?fr=lemma&ct=single#aid=0&pic=e850352ac65c1038ef0358deb0119313b07e89a9


鲜花

握手

雷人

路过

鸡蛋
专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap