机器学习(基于python 3.8)

机器学习就是把无序的数据转换成有用的信息

k-1. 近邻算法：采用测量不同特征值之间的距离方法进行分类

工作原理：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。

输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。

一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

k-近邻算法步骤如下：

计算已知类别数据集中的点与当前点之间的距离；

按照距离递增次序排序；

选取与当前点距离最小的k个点；

确定前k个点所在类别的出现频率；

返回前k个点所出现频率最高的类别作为当前点的预测分类。

一般流程：

(1) 收集数据

(2) 准备数据

(3) 分析数据

(4) 训练算法

(5) 测试算法

(6) 使用算法

kNN算法的优缺点

优点:

简单好用，容易理解，精度高，理论成熟，既可以用来做分类也可以用来做回归；

可用于数值型数据和离散型数据；

训练时间复杂度为O(n)；无数据输入假定；

对异常值不敏感。

缺点:

计算复杂性高；空间复杂性高；

样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。

最大的缺点是无法给出数据的内在含义。

2. 决策树(Decision Tree）:

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。

决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。

信息定义：l(xi) = - log2p(xi)

其中p(xi)是选择该分类的概率。

熵定义：H = -sum(p(xi)log2p(xi))

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

H(Y|X) = sum(PiH(Y|X=xi))

ID 年龄 有工作 房子 信贷情况 类别(是否个给贷款)

1 青年 否 否 一般 否

2 青年 否 否 好 否

3 青年 是 否 好 是

4 青年 是 是 一般 是

5 青年 否 否 一般 否

6 中年 否 否 一般 否

7 中年 否 否 好 否

8 中年 是 是 好 是

9 中年 否 是 非常好 是

10 中年 否 是 非常好 是

11 老年 否 是 非常好 是

12 老年 否 是 好 是

13 老年 是 否 好 是

14 老年 是 否 非常好 是

15 老年 否 否 一般 否

构造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。

然而用创建好的决策树解决分类问题，则可以很快完成。因此，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。

为了解决这个问题，需要使用Python模块pickle序列化对象。序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。

决策树的一些优点：

易于理解和解释，决策树可以可视化。

几乎不需要数据预处理。其他方法经常需要数据标准化，创建虚拟变量和删除缺失值。决策树还不支持缺失值。

使用树的花费（例如预测数据）是训练数据点(data points)数量的对数。

可以同时处理数值变量和分类变量。其他方法大都适用于分析一种变量的集合。

可以处理多值输出变量问题。

使用白盒模型。如果一个情况被观察到，使用逻辑判断容易表示这种规则。相反，如果是黑盒模型（例如人工神经网络），结果会非常难解释。

即使对真实模型来说，假设无效的情况下，也可以较好的适用。

决策树的一些缺点：

决策树学习可能创建一个过于复杂的树，并不能很好的预测数据。也就是过拟合。修剪机制（现在不支持），设置一个叶子节点需要的最小样本数量，或者数的最大深度，可以避免过拟合。

决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树。这个问题通过decision trees with an ensemble来缓解。

学习一颗最优的决策树是一个NP-完全问题under several aspects of optimality and even for simple concepts。因此，传统决策树算法基于启发式算法，例如贪婪算法，即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。

概念难以学习，因为决策树没有很好的解释他们，例如，XOR, parity or multiplexer problems.

如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在训练之前，先抽样使样本均衡。

3. 朴素贝叶斯算法

朴素贝叶斯算法是有监督的学习算法，解决的是分类问题，如客户是否流失、是否值得投资、信用等级评定等多分类问题。

该算法的优点在于简单易懂、学习效率高、在某些领域的分类问题中能够与决策树、神经网络相媲美。

但由于该算法以自变量之间的独立（条件特征独立）性和连续变量的正态性假设为前提，就会导致算法精度在某种程度上受影响。

贝叶斯决策理论:选择具有最高概率的决策。

条件概率(Condittional probability)，就是指在事件B发生的情况下，事件A发生的概率，用P(A|B)来表示。

条件概率：P(A|B) = P(B|A)P(A)/P(B)

全概率 ：P(B) = P(B|A)P(A) + P(B|A')P(A')

现分别有 A，B 两个容器：

在容器 A 里分别有 7 个红球和 3 个白球，

在容器 B 里有 1 个红球和 9 个白球，

现已知从这两个容器里任意抽出了一个球，且是红球，问这个红球是来自容器 A 的概率是多少?

P(X) = 1/2 * 7/10 + 1/2 * 1/10 = 8/20 #任意取出红色球的概率

P(X|A) = 7/10

P(A|X) = P(X|A) * P(A) / P(X) = (7/10) * (1/2) / (8/20) = 7/8

A:2红2白；B:1红2白；这个红球是来自容器B的概率是多少?

P(X) = 1/2 * 1/2 + 1/2 * 1/3 = 5/12 #任意取出红色球的概率

P(X|B) = 1/3

P(B|X) = P(X|B) * P(B) / P(X) = (1/3) * (1/2) / (5/12) = 2/5

事件T1为抽出的球来自A桶，题中只有两个桶，显然P(T1)=1/2

事件T2为抽出的球来自B桶，P(T2)=1/2

事件H1为从A桶中抽出红球，则P(H1)=7/10

事件H2为从B桶中抽出红球，则P(H2)=1/10

事件A为抽出红球，则抽出红球的概率为P(A)=P(H1)*P(T1)+P(H2)*P(T2)=8/20

那么，抽出任意的球为红球且来自A桶的概率P(T1|A)=P(A|T1)*P(T1)/P(A)

P(A|T1)为从A桶中抽出红球的概率，从上面得知P(A|T1)=P(H1),于是P(T1|A)=P(H1)*P(T1)/P(A)=(7/10*1/2)/(8/20)=7/8

我们把P(A)称为"先验概率"（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。

    P(A|B)称为"后验概率"（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。

    P(B|A)/P(B)称为"可能性函数"（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

后验概率　＝　先验概率 ｘ 调整因子

这就是贝叶斯推断的含义。我们先预估一个"先验概率"，然后加入实验结果，看这个实验到底是增强还是削弱了"先验概率"，由此得到更接近事实的"后验概率"。

这就是贝叶斯分类器的基本方法：在统计资料的基础上，依据某些特征，计算各个类别的概率，从而实现分类。

朴素贝叶斯推断的一些优点：

生成式模型，通过计算概率来进行分类，可以用来处理多分类问题。

对小规模的数据表现很好，适合多分类任务，适合增量式训练，算法也比较简单。

朴素贝叶斯推断的一些缺点：

对输入数据的表达形式很敏感。

由于朴素贝叶斯的“朴素”特点，所以会带来一些准确率上的损失。

需要计算先验概率，分类决策存在错误率。

4. Logistic回归（目前不太理解，运算规则）

优点：计算代价不高，易于理解和实现。

缺点：容易欠拟合，分类精度可能不高。

适用数据类型：数值型和标称型数据

假设现在有一些数据点，我们利用一条直线对这些点进行拟合(该线称为最佳拟合直线)，这个拟合过程就称作为回归，

Logistic回归进行分类的主要思想是：根据现有数据对分类边界线建立回归公式，以此进行分类。其实，Logistic本质上是一个基于条件概率的判别模型(Discriminative Model)。

hθ(x) = g(θᵀx) = 1 / (1 + e^(-θᵀx))

其中X是变量，θ是参数，由于是多维，所以写成了向量的形式，也可以看作矩阵。θT表示矩阵θ的转置，即行向量变成列向量。θTX是矩阵乘法。（高数结合线性代数的知识）

梯度上升算法：

我们每次更新回归系数(最优参数)的时候，能不能不用所有样本呢？一次只用一个样本点去更新回归系数(最优参数)？这样就可以有效减少计算量了，这种方法就叫做随机梯度上升算法。

5. SVM

SVM的英文全称是Support Vector Machines，我们叫它支持向量机。

优点：泛化错误率低，计算开销不大，结果易解释。

缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。

适用数据类型：数值型和标称型数据。

分界线，术语称为“决策面”

求解这个”决策面”的过程，就是最优化。一个最优化问题通常有两个基本的因素：1）目标函数，也就是你希望什么东西的什么指标达到最好；2）优化对象，你期望通过改变哪些因素来使你的目标函数达到最优。

y = ax + b

x2 = ax1 + b

ax1 - x2 + b = 0

[a,-1][x1,x2]ᵀ + b = 0

SMO表示序列最小化(Sequential Minimal Optimizaion)。

SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到了一对合适的alpha，那么就增大其中一个同时减小另一个。

这里所谓的”合适”就是指两个alpha必须符合以下两个条件，条件之一就是两个alpha必须要在间隔边界之外，而且第二个条件则是这两个alpha还没有进进行过区间化处理或者不在边界上。

非线性SVM

在线性不可分的情况下，SVM通过某种事先选择的非线性映射（核函数）将输入变量映到一个高维特征空间，将其变成在高维空间线性可分，在这个高维空间中构造最优分类超平面。

f(x) = ∑aiyi(xᵀix) + b

f(x) = ∑aiyi<ϕ(x_i),ϕ(x)> + b

核函数公式： k(x1,x2) = (<x1,x2> + 1)^2

径向基核函数是SVM中常用的一个核函数。径向基核函数采用向量作为自变量的函数，能够基于向量举例运算输出一个标量。径向基核函数的高斯版本的公式如下：

k(x1,x2) = exp{ -(||x1-x2||^2 / (2σ^2) }

σ是用户自定义的用于确定到达率(reach)或者说函数值跌落到0的速度参数。

6. adaboost(参考：https://blog.csdn.net/c406495762/article/details/78212124)

我们可以很自然地将不同的分类器组合起来，而这种组合结果则被成为集成方法(ensemble method)或者元算法(meta-algorithm)。

集成方法（ensemble method）通过组合多个学习器来完成学习任务，颇有点“三个臭皮匠顶个诸葛亮”的意味。基分类器一般采用的是弱可学习（weakly learnable）分类器，通过集成方法，组合成一个强可学习（strongly learnable）分类器。所谓弱可学习，是指学习的正确率仅略优于随机猜测的多项式学习算法；强可学习指正确率较高的多项式学习算法。集成学习的泛化能力一般比单一的基分类器要好，这是因为大部分基分类器都分类错误的概率远低于单一基分类器的。

自举汇聚法（bootstrap aggregating），也称为bagging方法。主要思想：

a 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）

b 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

c 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

Boosting的思路则是采用重赋权（re-weighting）法迭代地训练基分类器，主要思想：

a 每一轮的训练数据样本赋予一个权重，并且每一轮样本的权值分布依赖上一轮的分类结果。

b 基分类器之间采用序列式的线性加权方式进行组合。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

Bagging + 决策树 = 随机森林

AdaBoost + 决策树 = 提升树

Gradient Boosting + 决策树 = GBDT

1、计算样本权重

训练数据中的每个样本，赋予其权重，即样本权重，用向量D表示，这些权重都初始化成相等值。假设有n个样本的训练集：

{(x1,y1),(x2,y2),...,(xn,yn)}

设定每个样本的权重都是相等的，即1/n。

2、计算错误率

利用第一个弱学习算法h1对其进行学习，学习完成后进行错误率ε的统计：

ε = 未正确分类的样本数 / 所有样本数

3、计算弱学习算法权重

α = 1/2 ln ((1-ε)/ε)

4、更新样本权重

5、AdaBoost算法

H(x) = sign(∑αt * ht(x))

ROC曲线不但可以用于比较分类器，还可以基于成本效益（cost-versus-benefit）分析来做出决策。由于在不同的阈值下，不用的分类器的表现情况是可能各不相同，因此以某种方式将它们组合起来或许更有意义。如果只是简单地观察分类器的错误率，那么我们就难以得到这种更深入的洞察效果了。

你会发现，ROC曲线往左上角更靠拢了，并且AUC值增加了。也就表明，分类器效果更佳。

这就是ROC和AUC对与分类器评价指标，ROC越靠拢于左上角，分类器性能越好。同理AUC越接近于1，分类器性能越好.

分类器性能评价:

（True Positive，TP，也称真阳）

（True Negative，TN，也称真阴）

（False Negative，FN，为称假阴）

（False Positive，FP，也称假阳）

1. 模型的精度: accuracy = (TP+TN) / (TP+FN+FP+TN)

一般情况下，模型的精度越高，说明模型的效果越好。

2.正确率: Positive predictive value（PPV，Precision） precision = TP / (TP+EP)

一般情况下，正确率越高，说明模型的效果越好。

3.错误发现率:False discovery rate（FDR） FDR = EP / (TP+EP)

一般情况下，错误发现率越小，说明模型的效果越好。

4.错误遗漏率:False omission rate（FOR） FOR = FN / (FN+TN)

5.阴性预测值:Negative predictive value（NPV） NPV = TN / (FN+TN)

一般情况下，NPV越高，说明的模型的效果越好。

6.召回率:True positive rate（Recall） recall = TP / (TP+FN)

一般情况下，Recall越高，说明有更多的正类样本被模型预测正确，模型的效果越好。

7.假正率:False positive rate（FPR），Fall-out FPR = FP / (FP+TN)

一般情况下，假正类率越低，说明模型的效果越好。

8.缺失率:False negative rate（FNR），Miss rate FNR = FN / (FN+TN)

缺失值越小，说明模型的效果越好。

7、线性回归

优点：结果易于理解，计算上不复杂

缺点：对非线性的数据拟合不好

适用数据类型：数值型和标称型数据

回归的目的是预测数值型的目标值。

HorsePower = 0.0015 * annualSalary - 0.99 * hoursListeningToPublicRadio

这就是所谓的回归方程（regression equation），其中的0.0015和-0.99称为回归系数（regression weights）

说到回归，一般都是指线性回归（linear regression），所以本文里的回归和线性回归代表同一个意思。线性回归意味着可以将输入项分别乘以一些常量，再将结果加起来得到输出。

需要说明的是，存在另一种成为非线性回归的回归模型，该模型不认同上面的做法，比如认为输出可能是输入的乘积。

HorsePower = 0.0015 * annualSalary / hoursListeningToPublicRadio

平方误差公式：w=(XᵀX)⁻¹Xᵀy 其中X必须为方阵，求逆

局部加权线性回归（Locally Weighted Linear Regression，LWLR）：w=(XᵀWX)⁻¹XᵀWy 其中W是一个矩阵，这个公式跟我们上面推导的公式的区别就在于W，它用来给每个点赋予权重。

岭回归：w=(XᵀX + αI)⁻¹Xᵀy

所有特征都减去各自的均值并除以方差。

8、树回归(Tree Regression)

优点：可以对复杂和非线性的数据建模

缺点：结果不易理解

适用数据类型：数值型和标称型数据

将CART（Classification And Regression Trees）算法用于回归

CART算法有两步：

决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。不同的算法使用不同的指标来定义"最好"：

决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。

树剪枝

预剪枝：停止条件tolS对误差的数量级十分敏感。

后剪枝：使用后剪枝方法需要将数据集分成测试集和训练集。首先指定参数，使得构建出的树足够大、足够复杂，便于剪枝。接下来从上而下找到叶结点，用测试集来判断这些叶结点合并是否能降低测试集误差。如果是的话就合并。

模型树：

tkinter 使用

9、K-均值聚类算法

优点：容易实现

缺点：可能收敛到局部最小值，在大规模数据集上收敛较慢

适用的数据类型：数值型数据

优点：

　　一种经典算法，简单，快速的聚类算法。

　　对于大数据集，该算法保持可伸缩性和高效率。

　　当簇近似为高斯分布时，它的效果较好。

缺点：

　　在簇的平均值可被定义的情况下才能使用，可能不适用某些情况。

　　必须实现给出K(聚类的簇数目)，而且是初值敏感的，对于不同的初始值，可能会导致不同的结果。

　　不适合于发现非凸型的簇或者大小差别很大的簇。

对噪声和孤立点数据敏感。

在很多情况下，可以作为其他聚类的基础算法，比如谱聚类。

聚类是指将数据集划分为若干类，使得各个类之内的数据最为相似，而各个类之间的数据相似度差别尽可能的大。聚类分析就是以相似性为基础，在一个聚类中的模式之间比不在同一个聚类中的模式之间具有更多的相似性。对数据集进行聚类划分，属于无监督学习。

K-Means算法是一种简单的迭代型聚类算法，采用距离作为相似性指标，从而发现给定数据集中的K个类，且每个类的中心是根据类中所有数值的均值得到的，

每个类的中心用聚类中心来描述。对于给定的一个（包含n个一维以及一维以上的数据点的）数据集X以及要得到的类别数量K，选取欧式距离作为相似度指标，

聚类目标实施的个类的聚类平反和最小，即最小化。

结合最小二乘法和拉格朗日原理，聚类中心为对应类别中各数据点的平均值，同时为了使算法收敛，在迭代的过程中，应使得最终的聚类中心尽可能的不变。

欧式距离计算公式：d(x,y) = √((x1-y1)^2+(x2-y2)^2+...+(xn-yn)^2) = √(∑(xi - yi) ^ 2)

10、apriori (关联分析算法)

优点：易编码实现。

缺点：在大数据集上可能较慢

适用数据类型：数值型数据或者标称型数据

频繁项集：频繁项集是指那些经常出现在一起的物品

支持度（Support）：一个项集的支持度被定义为数据集中包含该项集的记录所占的比例

置信度（Confidence）：针对关联规则来定义的。置信度是指如果购买物品A，有较大可能购买物品B。

提升度（Lift）：提升度指当销售一个物品时，另一个物品销售率会增加多少。

当提升度(A->B)的值大于1的时候，说明物品A卖得越多，B也会卖得越多。而提升度等于1则意味着产品A和B之间没有关联。最后，提升度小于1那么意味着购买A反而会减少B的销量。

支持度 = （包含物品A的记录数量） / （总的记录数量）

置信度( A -> B) = （包含物品A和B的记录数量） / （包含 A 的记录数量）

提升度( A -> B) = 置信度( A -> B) / (支持度 A)

Apriori 的原理：【如果某个项集是频繁项集，那么它所有的子集也是频繁的】。即如果 {0,1} 是频繁的，那么 {0}, {1} 也一定是频繁的。

这个原理直观上没有什么用，但是反过来看就有用了，也就是说【如果一个项集是非频繁的，那么它的所有超集也是非频繁的】。

关联规则：

如果一个关联结果的置信度低，那么它的所有超集的置信度也低。

11、FP树

优点：一般要快于 apriori

缺点：实现比较困难，在某些数据集上性能会下降

适用数据类型：标称型数据

FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中。FP代表频繁模式（Frequent Pattern）。

FP-growth算法的工作流程如下：

首先构建FP树，然后利用它来挖掘频繁项集。为构建FP树，需要对原始数据集扫描两遍。

第一遍对所有元素项的出现次数进行计数。数据库的第一遍扫描用来统计出现的频率，而第二遍扫描中只考虑那些频繁元素。

从FP树中抽取频繁项集的三个基本步骤如下：

从FP树中获得条件模式基；

利用条件模式基，构建一个条件FP树；

迭代重复步骤1步骤2，直到树包含一个元素项为止。

12、

降维技术：

主成分分析（Principal Component Analysis, PCA）。

数据从原来的坐标系转化到了新的坐标系，新坐标系的选择是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向，第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向。重复选择新坐标轴，最终大部分方差都包含在最前面的几个新坐标轴中。因此，忽略余下的坐标轴，达到降维的目的。

因子分析（Factor Analysis）。

在因子分析中，我们假定在观察数据的生成中有一些观察不到的隐变量（latent variable）。假设观察数据时这些隐变量和某些噪声的线性组合。通过找到隐变量就可以实现数据的降维。

独立主成分分析（Independent Component Analysis, ICA）。

ICA假设数据是从N个数据源生成的。假设数据位多个数据源的混合观察结果，这些数据源之间在统计上是相互独立的，而在PCA中假设数据是不相关的。同因子分析一样，如果数据源的数目少于观察数据的数目，则可以实现降维过程。

均值：V = ∑(X) / n (V均值，n 个样本，求和∑(X))

方差：VAR = (∑(X-V)^2) / (n - 1)

标准差：cov(x,y) = (∑(Xi-Vx)(Yi-Vy)) / (n - 1)

可见，协方差是一个对称的矩阵，且对角线是各维度上的方差。正是由于协方差矩阵为对称矩阵所以矩阵分解后特征值所对应的特征向量一定无线性关系，且相互之间一定正交，即内积为零。

对协方差矩阵的特征向量最直观的解释之一是它总是指向数据方差最大的方向（上面的u、v）。

PCA

优点：降低数据的复杂性，识别最重要的多个特征

缺点：不一定需要，且可能损失有用信息

适用数据类型：数值型数据

dimen_reduce

将数据转换为只保留前N个主成分的特征空间的伪代码如下所示：

去除平均值

计算协方差矩阵

计算协方差矩阵的特征值和特征向量

将特征值排序

保留前N个最大的特征值对应的特征向量

将数据转换到上面得到的N个特征向量构建的新空间中（实现了特征压缩）

13、SVD 奇异值分解（Singular Value Decomposition）

优点：简化数据，去除噪声，提高算法的结果。

缺点：数据的转换可能难以理解。

使用数据类型：数值型数据。

将利用SVD的方法称为隐性语义索引（Latent Semantic Indexing，LSI）或隐性语义分析（Latent Semantic Analysis，LSA）。

SVD的另一个应用是推荐系统

最常见的一种矩阵分解技术就是SVD。SVD将原始的数据集矩阵Data分解成三个矩阵U、Σ、VT。如果原始矩阵Data是m行n列，则有如下等式：

DATAm×n=Um×mΣm×nVᵀn×n

确定要保留的奇异值的数目有很多启发式的策略，其中一个典型的做法是保留矩阵中90%的能量信息。为计算总能量信息，将所有的奇异值求其平方和。于是可将奇异值的平方和累加到总值的90%为止。另一个启发式策略是，当矩阵上有上万的奇异值时，那么就保留前面的2000或3000个。在任何数据集上，都不能保证前3000个奇异值能够包含90%的能量信息，但在实际中更容易实施。

范数，是具有“长度”概念的函数。在线性代数、泛函分析及相关的数学领域，范数是一个函数，是矢量空间内的所有矢量赋予非零的正长度或大小。半范数可以为非零的矢量赋予零长度。

注：在二维的欧氏几何空间 R中定义欧氏范数，在该矢量空间中，元素被画成一个从原点出发的带有箭头的有向线段，每一个矢量的有向线段的长度即为该矢量的欧氏范数。

用途：推荐引擎、协同过滤

14、MapReduce 分布式计算框架

优点: 使程序以并行的方式执行，可在短时间内完成大量工作。

缺点: 算法必须经过重写，需要对系统工程有一定的理解。

适用数据类型: 数值型和标称型数据。

MapRedece 工作原理

主节点控制 MapReduce 的作业流程

MapReduce 的作业可以分成map任务和reduce任务

map 任务之间不做数据交流，reduce 任务也一样

在 map 和 reduce 阶段中间，有一个 sort 和 combine 阶段

数据被重复存放在不同的机器上，以防止某个机器失效

mapper 和 reducer 传输的数据形式为 key/value对