常见面试算法：PCA、简化数据

降维技术

场景

我们正通过电视观看体育比赛，在电视的显示器上有一个球。
显示器大概包含了100万像素点，而球则可能是由较少的像素点组成，例如说一千个像素点。
人们实时的将显示器上的百万像素转换成为一个三维图像，该图像就给出运动场上球的位置。
在这个过程中，人们已经将百万像素点的数据，降至为三维。这个过程就称为降维(dimensionality reduction)

数据显示并非大规模特征下的唯一难题，对数据进行简化还有如下一系列的原因：

1. 使得数据集更容易使用
1. 降低很多算法的计算开销
1. 去除噪音
1. 使得结果易懂

适用范围:

在已标注与未标注的数据上都有降维技术。
这里我们将主要关注未标注数据上的降维技术，将技术同样也可以应用于已标注的数据。

在以下3种降维技术中， PCA的应用目前最为广泛，因此本章主要关注PCA。

- 通俗理解：就是找出一个最主要的特征，然后进行分析。
- 例如：考察一个人的智力情况，就直接看数学成绩就行(存在：数学、语文、英语成绩)
1. 主成分分析(Principal Component Analysis, PCA)
- 假设观察数据的成分中有一些观察不到的隐变量(latent variable)。
- 假设观察数据是这些隐变量和某些噪音的线性组合。
- 那么隐变量的数据可能比观察数据的数目少，也就说通过找到隐变量就可以实现数据的降维。
- 通俗理解：将多个实测变量转换为少数几个综合指标。它反映一种降维的思想，通过降维将相关性高的变量聚在一起,从而减少需要分析的变量的数量,而减少问题分析的复杂性
- 例如：考察一个人的整体情况，就直接组合3样成绩(隐变量)，看平均成绩就行(存在：数学、语文、英语成绩)
- 应用的领域：社会科学、金融和其他领域
- 在因子分析中，我们
1. 因子分析(Factor Analysis)
- 通俗理解：ICA 认为观测信号是若干个独立信号的线性组合，ICA 要做的是一个解混过程。
- 例如：我们去ktv唱歌，想辨别唱的是什么歌曲？ICA 是观察发现是原唱唱的一首歌【2个独立的声音（原唱／主唱）】。
- ICA 是假设数据是从 N 个数据源混合组成的，这一点和因子分析有些类似，这些数据源之间在统计上是相互独立的，而在 PCA 中只假设数据是不相关（线性关系）的。
- 同因子分析一样，如果数据源的数目少于观察数据的数目，则可以实现降维过程。
1. 独立成分分析(Independ Component Analysis, ICA)

PCA

PCA 概述

主成分分析(Principal Component Analysis, PCA)：通俗理解：就是找出一个最主要的特征，然后进行分析。

PCA 场景

例如：考察一个人的智力情况，就直接看数学成绩就行(存在：数学、语文、英语成绩)

PCA 原理

PCA 工作原理

找出第一个主成分的方向，也就是数据 方差最大 的方向。
找出第二个主成分的方向，也就是数据 方差次大 的方向，并且该方向与第一个主成分方向 正交(orthogonal 如果是二维空间就叫垂直)。
通过这种方式计算出所有的主成分方向。
通过数据集的协方差矩阵及其特征值分析，我们就可以得到这些主成分的值。
一旦得到了协方差矩阵的特征值和特征向量，我们就可以保留最大的 N 个特征。这些特征向量也给出了 N 个最重要特征的真实结构，我们就可以通过将数据乘上这 N 个特征向量从而将它转换到新的空间上。

为什么正交？

正交是为了数据有效性损失最小
正交的一个原因是特征值的特征向量是正交的

例如下图：

PCA 优缺点

代码语言：javascript复制

优点：降低数据的复杂性，识别最重要的多个特征。
缺点：不一定需要，且可能损失有用信息。
适用数据类型：数值型数据。

项目案例: 对半导体数据进行降维处理

项目概述

代码语言：javascript复制

半导体是在一些极为先进的工厂中制造出来的。设备的生命早期有限，并且花费极其巨大。
虽然通过早期测试和频繁测试来发现有瑕疵的产品，但仍有一些存在瑕疵的产品通过测试。
如果我们通过机器学习技术用于发现瑕疵产品，那么它就会为制造商节省大量的资金。具体来讲，它拥有590个特征。我们看看能否对这些特征进行降维处理。对于数据的缺失值的问题，我们有一些处理方法(参考第5章)
目前该章节处理的方案是：将缺失值NaN(Not a Number缩写)，全部用平均值来替代
(如果用0来处理的策略就太差劲了)。

开发流程

收集数据：提供文本文件

文件名：secom.data

文本文件数据格式如下：

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/13.PCA/pca.py

要点补充

代码语言：javascript复制

降维技术使得数据变的更易使用，并且它们往往能够去除数据中的噪音，使得其他机器学习任务
更加精确。
降维往往作为预处理步骤，在数据应用到其他算法之前清洗数据。
比较流行的降维技术： 独立成分分析、因子分析 和 主成分分析， 其中又以主成分分析应用
最广泛。本章中的PCA将所有的数据集都调入了内存，如果无法做到，就需要其他的方法来寻找其特征值。
如果使用在线PCA分析的方法，你可以参考一篇优秀的论文 "Incremental Eigenanalysis for Classification"。
下一章要讨论的奇异值分解方法也可以用于特征值分析。

利用SVD简化数据

SVD 概述

代码语言：javascript复制

奇异值分解（SVD, Singular Value Decomposition）:
   提取信息的一种方法，可以把 SVD 看成是从噪声数据中抽取相关特征。从生物信息学到
金融学，SVD 是提取信息的强大工具。

SVD 场景

信息检索-隐性语义检索（Lstent Semantic Indexing, LSI）或隐形语义分析（Latent Semantic Analysis, LSA）

隐性语义索引：矩阵 = 文档词语

是最早的 SVD 应用之一，我们称利用 SVD 的方法为隐性语义索引（LSI）或隐性语义分析（LSA）。

推荐系统

利用 SVD 从数据中构建一个主题空间。
再在该空间下计算其相似度。(从高维-低维空间的转化，在低维空间来计算相似度，SVD 提升了推荐系统的效率。)

上图右边标注的为一组共同特征，表示美式 BBQ 空间；另一组在上图右边未标注的为日式食品空间。

图像压缩

例如：32*32=1024 => 32*2 2*1 32*2=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

SVD 工作原理

矩阵分解

矩阵分解是将数据矩阵分解为多个独立部分的过程。
矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新形式是两个或多个矩阵的乘积。（类似代数中的因数分解）
举例：如何将12分解成两个数的乘积？（1，12）、（2，6）、（3，4）都是合理的答案。

SVD 是矩阵分解的一种类型，也是矩阵分解最常见的技术

SVD 将原始的数据集矩阵 Data 分解成三个矩阵 U、∑、V
举例：如果原始矩阵 (Data_{m*n}) 是m行n列，
- (U_{m * k}) 表示m行k列
- (∑_{k * k}) 表示k行k列
- (V_{k * n}) 表示k行n列。

(Data_{m*n} = U_{m*k} * ∑_{k*k} * V_{k*n})

具体的案例：（大家可以试着推导一下：https://wenku.baidu.com/view/b7641217866fb84ae45c8d17.html ）

欧氏距离：指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。二维或三维中的欧氏距离就是两点之间的实际距离。
- 相似度= 1/(1 欧式距离)
- 相似度= 1.0/(1.0 la.norm(inA - inB))
- 物品对越相似，它们的相似度值就越大。
皮尔逊相关系数：度量的是两个向量之间的相似度。
- 相似度= 0.5 0.5*corrcoef() 【皮尔逊相关系数的取值范围从 -1 到 1，通过函数0.5 0.5*corrcoef()这个函数计算，把值归一化到0到1之间】
- 相似度= 0.5 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
- 相对欧氏距离的优势：它对用户评级的量级并不敏感。
余弦相似度：计算的是两个向量夹角的余弦值。
- 余弦值 = (A·B)/(||A||·||B||) 【余弦值的取值范围也在-1到 1之间】
- 相似度= 0.5 0.5*余弦值
- 相似度= 0.5 0.5*( float(inA.T*inB) / la.norm(inA)*la.norm(inB))
- 如果夹角为90度，则相似度为0；如果两个向量的方向相同，则相似度为1.0。

推荐系统的评价

采用交叉测试的方法。【拆分数据为训练集和测试集】
推荐引擎评价的指标：最小均方根误差(Root mean squared error, RMSE)，也称标准误差(Standard error)，就是计算均方误差的平均值然后取其平方根。
- 如果RMSE=1, 表示相差1个星级；如果RMSE=2.5, 表示相差2.5个星级。

推荐系统原理

推荐系统的工作过程：给定一个用户，系统会为此用户返回N个最好的推荐菜。
实现流程大致如下：
1. 寻找用户没有评级的菜肴，即在用户-物品矩阵中的0值。
2. 在用户没有评级的所有物品中，对每个物品预计一个可能的评级分数。这就是说：我们认为用户可能会对物品的打分（这就是相似度计算的初衷）。
3. 对这些物品的评分从高到低进行排序，返回前N个物品。