MachineLearning

part 1 监督学习 已知输入样本集学习结果，建立预测模型，推演目标变量可能结果 目标变量一般有两种类型：标称型和数值型。

分类： 一 K-近邻算法 kNN 对未知类别属性数据集中的每个点依次执行以下操作： 1）计算已知类别数据集中的每个点到当前点的距离, 需要归一化特征值，防止不同数量级的属性对分类影响，newvalue = (oldvalue-min)）/(max-min) 2）按照距离递增排序 3）选取与当前点最近的k个点 4）确定前k个点的类别出现频率 5）选择其中出现频率最高的点作为当前点的类别预测分类

二 决策树 decision tree 检测数据集中的每个子项是否属于同一个分类： 如果是，则返回标签类 否则 寻找划分数据集的最好特征，（划分之后的信息增益最大，熵：信息的期望值,描述状态的不确定性，信息增益即熵减） 创建分支节点 对每个划分的子集 递归调用创建决策树过程 返回 分支节点 根据生成的决策树，对待预测数据按照各个节点进行分类

三 朴素贝叶斯 naive bayes 贝叶斯准则：已知特征求分类概率 p(c|x) = p(x|c)*p(c)/p(x), p(ci|x,y) = p(x,y|ci)*p(ci)/p(x,y) 根据已有样本数据计算已知分类结果，到属性的条件概率；已知分类结果的概率；可以计算出已知属性，属于某个分类的概率，选择其中概率最大的作为预测分类

四 Logistic回归 LR 根据现有数据对分类边界线建立回归公式。训练分类器时的做法就是寻找最佳拟合参数，使用的是最优化算法。 sigmoid函数：𝝈(z) = 1/(1+e^(-z)) 将阶跃函数平滑化 z = W0 * X0 + W1 * X1 + ... + Wn * Xn，(包含常量因子，令X0=1)即z = WT * X；sigmoid函数计算结果小于0.5，归入0类；大于0.5归入1类, WTx=0 即为分类边界线方程。 最优化算法： 1）梯度上升法 函数f(x,y)的梯度，∇f(x,y) = ⦗∂f(x,y)/∂x, ∂f(x,y)/∂y⦘，函数对各个变量的偏导数构成的向量，沿各个坐标轴的函数增长率，梯度算子始终指向函数值增长最快的方向。 误差e(w) = (y - sigmoid(wx)).T * (y - sigmoid(wx)), 利用梯度下降求误差最小值或梯度上升算法求-e(w)最大值，得到如下公式： w := w + 𝜶∇f(w), 𝜶为迭代步长，w为回归系数，用来求函数最大值,weights = weights + alpha * dataMatrix.transpose() * (y-sigmoid(wx)) 梯度下降算法：w := w - 𝜶∇f(w)，用来求函数最小值, gradient descent 步骤： 每个回归系数初始化为1，（可以随机选择防止算法收敛到局部最优解） 重复R次： 计算整个数据集的梯度（数据乘以权重） 使用alpha*gradient更新回归系数的向量: w = w + 𝜶 * dataMatrix.transpose()error,error为列向量，包含每个样本的误差 返回回归系数 缺点：每次更新回归系数需要遍历整个数据集，计算量比较大 2）随机梯度上升算法 所有回归系数初始化为1 对数据集中每个样本 计算该样本的梯度 使用alphagradient更新回归系数，相对于梯度上升算法，这里每次只使用一个样本数据进行更新 返回回归系数 缺点：定长的步长导致数据来回波动，异常样本数据导致回归系数异常变化 3）改进随机梯度上升算法 根据迭代次数减少步长， 随机选择样本值进行回归系数更新

五 支持向量机 SVM 将数据集分割开来的“直线”称为分隔超平面，表述形式：W.T * X + b 支持向量：离分隔超平面最近的那些点 点A到超平面的距离：|W.T * A + b|/||W||，目标求支持向量到分隔平面的最大距离 arg MAXw,b{MINn(label*(W.TX + b))1/||W||}，找出到分隔超平面最近的点即支持向量，选择合适的超平面使得支持向量到超平面距离最大化 给定约束条件：label(W.TX + b) >= 1.0 拉格朗日乘子法优化目标函数 SMO算法(Sequential Minimal Optimization)将大优化问题分解为多个小优化问题,每次只优化2个alpha来加速SVM的训练速度。 SMO算法的目标是求出一系列alpha和b，一旦求出这些alpha就很容易计算权重向量w并得到分隔超平面。 SMO算法原理：每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha，那么就增大其中一个同时减小另一个。这里所谓的"合适"就是指两个alpha必须要符合一定的条件， 条件之一就是这两个alpha必须要在间隔边界之外，第二个条件是这两个alpha还没有进行过区间化处理或者不在边界上。 SMO伪码： 创建一个alpha向量并将其初始化为0向量 当迭代次数小于最大迭代次数时(外循环) 对数据集中对每个数据向量(内循环)： 如果该数据向量可以被优化： 随机选择另外一个数据向量 同时优化这两个向量 如果两个向量都不能被优化，退出内循环 如果所有向量都没有被优化，增加迭代数目，继续下一次循环 利用核函数将非线性可分的数据映射成线性可分的数据点，常用的核函数有：径向基函数。 将数据从一个特征空间映射到另一个特征空间，通常情况将低维特征空间映射到高维特征空间。这种映射是通过核函数实现的。 径向基函数的高斯版本，将数据从其特征空间映射到更高维的空间，实际上是一个无穷维的空间： k(x,y) = exp{-||x-y||^2/(2𝝈^2)}, 𝝈是达到率，或者说函数值跌落到0的速度参数，y是一个选择的用于求样本到其距离的向量，比如（0，0...）向量。

六 AdaBoost元算法 元算法是对其他算法进行组合的一种方式，可以不同算法组合，也可以同一算法的不同设置下组合；有人认为AdaBoost是最好的监督学习方法 自举汇聚法(bootstrap aggregating)，也称为bagging方法，是在从原始数据集选择S次后得到S个新数据集的一种技术。新数据集和原数据集大小相等。每个数据集都是通过在原始数据集中随机选择一个样本进行替换得到。意味着新数据集可以有重复值。 在S个数据集建好之后，可以将某个学习算法分别作用于每个数据集得到S个分类器，使用S个分类器对新数据进行分类。更先进的bagging方法有 随机森林(random forest) boosting是一种与bagging很类似的技术，使用的多个分类器的类型是一致的。不同的是boosting的不同的分类器是通过串行训练获得的，每个新的分类器都根据已训练出来的分类器的性能来进行训练。Boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。 Boosting分类的结果是基于所有分类器的加权求和结果的，每个权重代表其对应分类器在上一轮迭代中的成功度，而bagging中的分类器权重是相等的。 boosting方法中最流行的一个版本AdaBoost(adaptive boosting) 算法如下： 训练数据中的每个样本，并赋予其一个权重，这些权重向量构成了向量D。一开始这些权重都初始化成相等值。 首先在训练数据上训练出一个弱分类器(可以使用任意分类器作为弱分类器，简单分类器效果更好)并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。 在分类器的第二次训练当中，将会重新调整每个样本的权重，上一次分对的样本权重降低，分错的样本权重提高； 为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha是基于每个弱分类器的错误率进行计算的。其定义如下： ℇ = 未正确分类的样本数/所有样本数 alpha计算公式：错误率越小权重越大，针对分类器的权重 𝜶 = 1/2 * ln((1-ℇ)/ℇ) 计算出alpha值后，可以对权重向量D进行更新，以使正确分类的样本权重降低，错误分类样本的权重增加，以便于后续分类器对错误样本有更强的作用力。D计算方法如下： 正确分类样本权重更新：Di(t+1) = Di(t) * e^-𝜶 / Sum(D t+1)，被分正确的样本在下一轮训练中权重降低，被错分的样本权重增加，权重之和为1 错分样本权重更新： Di(t+1) = Di(t) * e^𝜶 / Sum(D t+1) 在计算出D之后，AdaBoost又开始进行下一轮迭代。算法会不断地重复训练和调整权重过程，直到训练错误率为0或者弱分类器的数目达到用户指定值为止。

基于单层决策树（decision stump）构建弱分类器：只有1，-1两个分类
将最小错误率minError设为+∞
对数据集中的每一个特征（第一层循环）：
    对每个步长（第二层循环按步长遍历某个特征的所有值）：
        对每个不等号（第三层循环，根据与比较值的大小进行分类）：
            建立一颗单层决策树并利用加权数据集对它进行测试
            如果错误率低于minError，则将当前单层决策树设为最佳单层决策树
返回最佳单层决策树

AdaBoost算法实现：
对每次迭代：
    利用上述单层决策树构建方法找到最佳的单层决策树
    将最佳单层决策树加入到单层决策树组
    计算alpha（分类器的权重）
    计算新的权重向量D（样本的权重）
    更新累计类别估计值
    如果错误率为0.0，则退出循环

利用AdaBoost算法进行分类：
将待分类数据应用到训练出来的多个弱分类器上进行简单分类，分类估计值乘以每个分类器的权重alpha，再求和，根据求和结果的符号确定预测分类是+1，或者-1类。

分类器评价指标： 非均衡分类问题： 对马的死亡预测会导致马的安乐死，且预测的准确率不是100%； 对垃圾邮件的过滤准确率也非100%，会导致正常邮件接收不到 不同类别的分类代价不一样，需要根据分类结果的代价来调整分类的权重。 其他的分类性能度量指标： 预测结果 +1 -1 真实结果： +1 真正例（TP） 伪反例（FN） -1 伪正例（FP） 真反例（TN） 正确率：TP/(TP+FP)，预测为正例的样本中真实正例的比例。针对的是预测正例。 召回率：TP/(TP+FN)，所有真实正例样本中被预测为正例的比例。针对的是实际正例。 分类器很难同时保证高正确率和高召回率。分类器总是有一种"倾向"，要么容易把反例判为正例即FP较高，要么容易把正例判为反例即FN较高； 因此FP和FN很难同时减小，所以正确率和召回率很难同时较高。

预测强度：
朴素贝叶斯提供了一个预测的概率，Logistic回归中输入到Sigmoid函数是一个数值，在AdaBoost和SVM中，都会计算出一个数值然后输入到sign函数中。
所有的这些值都可以拥有衡量给定分类器的预测强度。

ROC（receiver operating characteristic）曲线，ROC代表接收者操作特征，横轴为伪正例比例FP/(FP+TN)，纵轴是真正例的比例TP/(TP+FN).
在理想情况下，最佳的分类器应该尽可能处于左上角，意味着分类器在假阳率很低的同时获取了很高的真阳率。
对不同的ROC曲线进行比较的一个指标是曲线下面积AUC，反映了分类器的平均性能值。
为了创建ROC曲线，首先要将分类样例按照预测强度排序。先从排名最低的样例开始，所有排名更低的样例都被判为反例，而所有排名更高的样例都被判为正例。该情况对应
点<1.0, 1.0>。然后以次低的样本为分界线重新计算ROC点坐标，依次计算所有的点。

处理分均衡问题的数据抽样方法：
欠抽样或者过抽样，解决在分类器训练时正例数目和反例数目相差较大时的情况。
欠抽样删除正例较多的样本，选择删除那些离决策边界较远的样例，过抽样则复制反例较少的样本，或者加入与已有样例相似的点，但是这种做法可能会导致过拟合。

在分类过程中引入代价信息，不同分类结果代价不一样。在AdaBoost中，可以基于代价函数来调整错误权重向量D；在朴素贝叶斯中，可以选择具有最小期望代价
而不是最大概率的类别作为最后结果；在SVM中，可以在代价函数中对于不同的类别选择不同的参数C。上述做法就会给较小类更多的权重，即在训练时，小类
当中只允许更少的错误。

开发机器学习程序的基本步骤： 1）收集数据 2）准备输入数据，准备合适的格式便于处理 3）分析输入数据，除异补漏 4）训练算法，根据输入样本训练算法，从中抽取知识或信息，建立模型 对于无监督学习，因为没有目标变量，所以不需要训练算法 5）测试算法，取出适当的样本对建立的模型验证成功率，对于无监督学习要找其他方法验证 6）使用算法，利用建立的模型运用在实际环境，看能否正常工作

各种算法对比： 概述： | 算法 | 优点 | 缺点 | 适用数据范围 | 适用场景 | | k-近邻算法 | 精度高，对异常值不敏感，无数据输入假定 | 计算复杂度高，空间复杂度高 | 数值型和标称型 | 手写识别 | | 决策树 | 计算复杂度不高，输出结果容易理解，对中间值的缺失不敏感，可以处理不相关特征数据 | 可能会产生过度匹配问题 | 数值型和标称型 | 预测患者佩戴何种隐形眼镜 | | 朴素贝叶斯 | 在数据较少情况下有效，可以处理多类别问题 | 对输入数据的准备方式较为敏感 | 标称型数据 | 过滤垃圾邮件 | | Logistic回归 | 计算代价不高，易于理解和实现 | 容易欠拟合 | 数值型和标称型 | 疝气病预测马的死亡率 | | 支持向量机 | 泛化错误率低，计算开销不大，结果易解释 | 对参数选择和核函数的选择敏感，原始分类器不加修改仅适用于二类问题 | 数值型和标称型 | 手写识别问题 | | AdaBoost | 泛化错误率低，易编码，可以应用在大部分分类器上，无参数调整 | 对离群点敏感 | 数值型和标称型 | 各种分类问题 |

1 LR 与 linear SVM对比，摘自知乎https://www.zhihu.com/question/26768865 使用场景： 1 如果Feature的数量很大（相比于样本数，下同），这时候选用LR或者是Linear Kernel的SVM 2 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel 3 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况 相同点： 1 都是线性分类器，监督学习算法 不同点： 1 linear SVM不直接依赖数据分布, 只考虑局部的边界线附近的点; LR受所有数据点影响，如果不同类数据强烈不平衡，需要先平衡处理 2 linear SVM依赖数据表达的距离测度，因此需要先做归一化normalization，LR不受此影响 3 loss function损失函数不一样，LR的损失函数是 cross entropy loss， adaboost的损失函数是 expotional loss , SVM是hinge loss，常见的回归模型通常用均方误差 4 LR可以给出每个点属于每一类的概率，因为输出是连续值（0，1）越靠近分类值概率越高，LR 可以看成一种概率估计，而SVM是非概率的

2 Adaboost与随机森林 随机森林：random forest 1 数据集有放回取样，随机数据 2 每个分类器选择若干个特征，一般取总特征数的平方根， 随机特征 3 对选取的样本和特征构建决策树，最后对多个决策树做表决获取分类结果 相同点： 1 随机抽样构造样本集 2 对多个分类器进行聚合 不同点： 1 随机森林是用完全长成的树,每个分类器是强分类器,训练错误很小但是是过拟合的.采用平均的方法来克服过拟合 2 AdaBoost Decision Tree是用弱分类器,每个决策树都是’浅’的树,在生成这些树的时候一般是要限制树的高度. 单个分类器一般都是欠拟合的. 3 AdaBoost 对各个分类器加权求结果，随机森林是平均权重 4 AdaBoost是多个分类器串行训练，随机森林的各个分类器相互独立。

part 2 回归 | 方法 | 优点 | 缺点 | 适用数据类型 | 应用场景 | | 线性回归（或局部加权) | 结果易于理解，计算不复杂 | 对非线性数据拟合不好 | 数值型和标称型 | 预测鲍鱼的年龄 | | 树回归 | 可以对复杂和非线性数据建模 | 结果不易于理解 | 数值型和标称型 | 回归与分类的区别是其预测的值是连续数值型。 回归的一般方法： 1) 收集数据 2）准备回归需要数值型数据，标称型数据将被转换成二值型数据 3）分析数据：绘出数据的可视化二维图将有助于对数据做出理解和分析，在采用缩减法求得新回归系数之后，可以将新拟合线绘在图上作为对比 4）训练算法：找到回归系数 5）测试算法：使用R2或者预测值和数据的拟合度，来分析模型的效果 6）使用算法：使用回归，可以在给定输入的时候预测出一个数值，这是对分类方法的提升，因为这样可以预测连续型数据而不仅仅是离散的类别标签。

一 线性回归 回归的目的是预测数值型的目标值。最直接的办法是写出一个目标值计算公式，即回归方程。求这些回归系数的过程就是回归。 平方误差：(y-Xw).T * (y-Xw)，对w求导，得到X.T(y-Xw)，令其等于零，解出w如下： w^ = (X.TX)^-1 * X.T * y， 坐标w上的‘帽’符号表示这是当前可以估计出的w的最优解，需要求解矩阵的逆，而矩阵逆可能不存在，因此需要在代码中做出判断。 上述w求解可以调用NumPy库里的矩阵方法，即OLS方法，普通最小二乘法。

预测值序列yHat和真实值y序列的匹配程度，用两个序列的相关系数定义。利用NumPy库中corrcoef(yEstimate, yActual)来计算预测值和真实值的相关性。
预测值 yHat = xMat * ws， 相关系数：corrcoef(yHat.T, yMat)，为协方差的一种特殊情况，即2个变量单位值的变化量的同步性。

局部加权线性回归(LWLR)，给待预测点附近的每个点赋予一定的权重，在这个子集上基于最小均方差进行普通的回归。与KNN一样，这种算法每次预测均需要事先取出对应的数据子集。
解出回归系数： w^ = (X.T * W * X)^-1 * X.T * W * y， 其中w是矩阵，用来给每个数据点赋予权重。
LWLR使用“核”对越近的点赋予越高的权重。核类型可以自由选择，常用的是高斯核，对应的权重如下：
w(i,i) = exp{|xi - x|/(-2*k^2)}, 构建一个只含对角元素的权重矩阵w，并且点x与x(i)越近，w(i,i)越大，用户指定的k决定了对附近的点赋予多大的权重，是唯一需要考虑的参数。
k控制远离预测点的权重的衰减速度，k越大，附近用于训练的数据越多

岭回归
如果特征比样本点还多，也就是说输入数据的矩阵X不是（列）满秩矩阵，非满秩矩阵X.T*X在求逆时会出现问题。
岭回归就是在矩阵X.T*X上加一个𝛌I从而使得矩阵非奇异，从而能对X.T*X+𝛌I求逆。回归系数计算公式为：
W^ = (X.T*X + 𝛌I)^-1 * X.T * y
岭回归最先用来处理特征数多于样本数的情况，也用于在估计中加入偏差，从而得到更好的估计。这里通过引入𝛌来限制了所有w之和，通过引入该惩罚项，能够减少不重要的参数，这个技术在统计学中也叫做缩减(shrinkage)。
加入对角线元素强化数据点对自身训练的权重。通过选取不同的𝛌来训练和测试误差，最终得到一个是预测误差最小的𝛌。
还有一些其他的缩减方法，如lasso，LAR，PCA回归以及子集选择等。

lasso
在增加如下约束时，普通的最小二乘法回归会得到与岭回归一样的公式：
∑w^2 <= 𝛌， 上式限定了所有回归系数的平方和不能大于𝛌，使用普通的最小二乘法回归在当两个或更多个特征相关时，可能会得到一个很大的正系数和一个很大的负系数，正因为上述限制，使用岭回归可以避免这个问题。
与岭回归类似，lasso也对回归系数做了限定：
∑|w| <= 𝛌，在𝛌足够小时，一些系数会因此被迫缩减到0，这个特性可以帮助我们更好的理解数据。同时增加了计算复杂度，需要使用二次规划算法。

前向逐步回归
前向逐步回归可以得到与lasso差不多的效果，但更加简单。它属于一种贪心算法，每一步都尽可能减少误差。他可以帮助人们理解现有模型并作出改进。当构建一个模型后，可以运行该算法找出重要的特征，这样就有可能及时停止对那些不重要特征的收集。
当应用缩减法（逐步线性回归或岭回归）时，模型增加了偏差(bias)，与此同时却减小了模型的方差

权衡偏差与方差
偏差：模型预测值和数据之间的差异，反应的是准确性，模型越复杂，预测越精确。
方差：模型之间的差异，反应的是模型的稳定性，模型越简单，方差越低，偏差越大。随机取出一个样本集，并用线性模型拟合，得到一组回归系数，同理，取出另一组随机样本集得到另一组系数，这些系数之前的差异反映了模型的方差。

与分类一样，回归也是预测目标值的过程。回归与分类的不同点在于，前者预测连续型变量，而后者预测离散型变量。在回归方程里，求得特征对应的最佳回归系数的方法是最小化误差的平方和。可以使用预测值和原始值的相关性来度量回归方程的好坏。
缩减法可以看成是对一个模型增加偏差的同时减少方差。寻找合适的模型即是在方差和偏差之间寻找平衡点，折中处理。

二 树回归 线性回归创建的模型需要拟合所有样本点(局部加权线性回归除外)，当数据拥有众多特征并且特征之间关系复杂时，构建全局模型就比较困难。实际生活中有很多问题是非线性的，一种可行的方法是将数据集切分成很多容易建模的数据，然后利用线性回归技术建模。 CART(Classification And Regression Trees，分类回归树)算法既可以用于分类还可以用于回归。 ID3算法选取当前最佳特征(信息增益最大)来分隔数据，按照该特征的所有可能取值来划分，一旦按某特征切分后，该特征在之后的算法执行中就不会再起作用，切分方式过于迅速，不能直接处理连续型特征，需要事先将连续型特征转换成离散型才能使用，但这种转换会破坏连续型变量的内在性质。 另外一种方法是二元切分法，每次把数据集切分成两份。如果特征值大于给定值就走左子树，否则就走右子树。同时节约了树的构建时间，这点不是很重要，因为树一般是离线构建。

将CART算法用于回归
回归树假设叶节点是常数值，这种策略认为数据中的复杂关系可以用树结构来概括。
连续型数据的混乱度定义：计算每条数据到均值的差值。一般使用绝对值或者平方值。这里使用平方误差的总值。寻找数据集最佳切分位置如下：
对每个特征：
	对每个特征值：
		将数据集切分成两份
		计算切分的误差
		如果当前的误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差
返回最佳切分特征和特征值
切分迭代有2个终止条件：切分后误差减少量不大TolS，切分出来的数据集TolNumPy很小。

树剪枝
一棵树如果节点过多，表明该模型可能对数据进行了“过拟合”。使用测试集上某种交叉验证技术来发现过拟合。在给定的样本空间中，拿出大部分样本作为训练集来训练模型，
剩余的小部分样本使用刚建立的模型进行预测，并求这小部分样本的预测误差或者预测精度，同时记录它们的加和平均值。例如10折交叉验证(10-fold cross validation)，
将数据集分成十份，轮流将其中9份做训练1份做验证，10次的结果的均值作为对算法精度的估计，一般还需要进行多次10折交叉验证求均值，例如：10次10折交叉验证，以求更精确一点。
交叉验证有时也称为交叉比对，如：10折交叉比对。
K-fold cross-validation
K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，
最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。
通过降低决策树的复杂度来避免过拟合的过程称为剪枝(pruning)。在训练过程中防止过拟合被称为预剪枝，使用测试集和训练集防止过拟合称为后剪枝。
预剪枝需要寻找适当的停止条件（比如误差减少量，数据拆分量），通过不断修改停止条件来找到合理结果不是很好的办法。而后剪枝不需要用户指定参数。

后剪枝
首先指定参数，构建出的树足够大，足够复杂，便于剪枝。接下来从上而下找到叶节点，用测试集来判断将这些叶节点合并是否能降低误差。如果是的话就合并。后剪枝可能不如预剪枝有效。
prune代码如下
基于已有的树切分测试数据：
	如果存在任一子集是一棵树,则在该子集递归剪枝过程
	计算将当前两个叶节点合并后的误差
	计算不合并的误差
	如果合并会降低误差就将叶节点合并

模型树
用树来对数据建模，除了把叶节点简单地设定为常数值外，还有一种方法是把叶节点设为分段线性函数。
计算相关系数来衡量哪种模型更好

数据集中经常包含一些复杂的相互关系，使得输入数据和目标变量之间呈现非线性关系。对这些复杂关系建模，一种可行的方式是使用树来对预测值分段，
包括分段常数或分段直线。若叶节点使用的模型是分段常数则称为回归树，若叶节点使用的模型是线性回归方程则称为模型树。

part 3 无监督学习 聚类是一种无监督学习，它将相似的对象归到同一个簇中。

| 聚类算法 | 优点 | 缺点 | 适用数据类型 | | K-均值聚类 | 容易实现 | 可能收敛到局部最小值，在大规模数据集上收敛较慢 | 数值型数据 | | Apriori算法 | 易编码实现 | 在大数据集上可能较慢 | 数值型或者标称型 | | FP-growth | 一般快于Apriori | 实现比较困难，在某些数据集上性能会下降 | 标称型数据 |

K-均值聚类算法
创建k个点作为起始质心(一般随机选择)
当任意一个点的簇分配结果发生改变时
	对数据集中的每个数据点
		对每个质心
			计算质心与数据点之间的距离
		将数据点分配到距其最近的簇
	对每一个簇，计算簇中所有点的均值并将均值作为质心

使用后处理来提高聚类性能
一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和).
一种后处理方法是将具有最大SSE值的簇划分成两个簇。具体实现可以将最大簇包含的点过滤出来，并在其上运行K-均值聚类算法，K取2.
为了保持簇数量不变，可以将两个簇进行合并。有两种可以量化的方法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。

二分K-均值聚类算法
为了克服K-均值聚类算法收敛于局部最小问题，提出了二分K-均值(bisecting K-means)的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二。
之后选择其中一个簇进行划分，选择哪一个簇取决于对齐划分是否可以最大程度降低SSE的值，另一组做法是选择SSE最大的簇进行划分，直到簇数目达到用户指定数目为止。
将所有点看成一个簇
当簇数目小于k时
对于每一个簇
	计算总误差
	在给定的簇上面进行K-均值聚类(k=2)
	计算将该簇一分为二之后的总误差
选择使得误差最小的那个簇进行划分操作

Apriori算法进行关联分析
从大规模数据集中寻找物品间的隐含关系称作关联分析或者关联规则学习。关联关系可以有两种形式：频繁项集或者关联规则。
频繁项集是经常出现在一块的物品的集合，关联规则暗示两种物品之间可能存在很强的关系。
一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。
针对{X}-->{Y}的可信度或置信度定义为：支持度({X,Y})/支持度({X})。在出现X的项中有多大概率出现Y。

Apriori原理
如果某个项集是频繁的，那么它的所有子集也是频繁的；如果一个项集是非频繁集，那么它的所有超集也是非频繁集。
Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表，去掉那些不满足最小支持度的集合，然后对剩下的集合进行组合以生成包含两个元素的项集。
接下来重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。
生成候选项集算法：
对数据集中的每条交易记录tran
	对每个候选项集can：
		检查一下can是否是tran的子集：
		如果是，则增加can的计数值
对每个候选项集：
如果其支持度不低于最小值，则保留该项集
返回所有频繁项集列表

Apriori算法伪码：
当集合中项的个数大于0时（未合并完）
	构建一个k个项组成的候选项的列表
	检查数据以确认每个项集是频繁的
	保留频繁项集并构建k+1项组成的候选项集的列表

从频繁项集中挖掘关联规则
如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。

FP-growth算法发现频繁项集
FP-growth算法只需要对数据进行两次扫描，而Apriori算法对于每个潜在的频繁项集会扫描数据集判定给定模式是否频繁，因此FP-growth算法的速度要比Apriori算法快，通常性能要好两个数量级以上。
它发现频繁项集的过程如下：
1）构建FP树
2）从FP树中挖掘频繁项集
构建FP树
第一次遍历数据集获取每个元素项的出现频率，去掉不满足最小支持度的元素项。
对每个集合进行排序，使其中的元素按照出现频率降序排列
将排序后的每个集合项添加到一条已经存在的路径中，不存在则创建新路径，如果树中已存在现有元素则增加现有元素的计数值。
同时对每个元素都有一个对应的头指针指向链表开头，不同分支的相同元素通过单链表链接。
从树根到叶节点是按照元素集合的降序排列的项，同时从头指针开始可以把所有项中的相同元素链接起来。
条件模式基
条件模式基是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径，是介于所查找元素项与树根节点之间的所有内容。前缀路径用于构造条件FP树。

part 4 数据预处理 降维的目标就是对输入的数目进行削减，由此剔除数据中的噪声并提高机器学习方法的性能。 数据简化的原因： 使得数据集更易用；降低很多算法开销；取出噪声；使得结果易懂。 | 方法 | 优点 | 缺点 | 适用数据类型 | | PCA | 降低数据的复杂性，识别最重要的多个特征 | 不一定需要，且可能损失有用信息 | 数值型数据 | | SVD | 简化数据，去除噪声，提高算法的结果 | 数据的转换可能难以理解 | 数值型数据 |

三种降维方法：
主成分分析(Principal Component Analysis,PCA)
在PCA中，数据从原来的坐标系转换到了新的坐标系，新坐标系的选择是由数据本身决定的。第一个新坐标轴选择的是原始数据中方差最大的方向(信息含量最丰富)，第二个新坐标轴选择和第一个坐标轴正交且具有最大方差的方向。该过程一直重复，重复次数为原始数据中特征的数目。
大部分方差都包含在最前面几个新坐标中，因此，我们可以忽略余下的坐标轴，即对数据进行了降维处理。
因子分析(Factor Analysis)
在因子分析中，我们假设在观察数据的生成中有一些观察不到的隐变量(latent variable)。假设观察数据是这些隐变量和某些噪声的线性组合。那么隐变量的数据可能比观察数据的数目少，也就是说通过找到隐变量就可以实现数据降维。
独立成分分析(Independent Component Analysis,ICA)
ICA假设数据是从N个数据源生成的。假设数据为多个数据源的混合观察结果，这些数据源之间在统计上是相互独立的，而在PCA中只假设数据是不相关的。同因子分析一样，如果数据源的数目少于观察数据的数目，则可以实现降维。
在上述三种降维技术中，PCA的应用目前最为广泛。

PCA
通过PCA进行降维处理，我们可以同时获得SVM和决策树的优点：一方面得到了和决策树一样简单的分类器，同时分类间隔和SVM一样好。
通过数据集的协方差矩阵及其特征值分析，我们可以求得这些正交的主成分的值。一旦得到协方差矩阵和特征向量，我们就可以保留最大的N个值。这些特征向量也给出了N个最重要特征的真实结构。我们可以将数据乘以这N个特征向量转换到新的空间。
对于协方差矩阵A，如果：
A*v = 𝛌v，v是特征向量，𝛌是特征值。假设数据矩阵为m*n,则协方差矩阵A为n*n，v为n*1，𝛌为标量，即特征向量在转换矩阵A的左乘下，与原向量保持在同一直线上，但方向和长度可能会变，由𝛌的大小和符号反应拉伸和方向。
PCA伪码：
去除平均值
计算协方差矩阵
计算协方差矩阵的特征值和特征向量(根据主成分方差占比确定主成分数量)
将特征值从大到小排序
保留最上面的N个特征向量
将数据转换到上述N个特征向量构建的新空间中
如果主成分数量过多，可以使用能包含90%(累积方差占比？)信息量的主成分数量，或者前20个主成分。具体数目需要在实验中取不同的值来确定，取决于数据集和具体应用。

SVD(Singular Value Decomposition, SVD)奇异值分解
SVD是矩阵分解的一种类型，而矩阵分解是将数据矩阵分解为多个独立部分的过程。SVD是一种强大的降维工具。
Data(m,n) = Umm * ∑mn * V.Tnn
矩阵∑只有对角元素，其他均为0，∑的对角元素是从大到小排列的。这些对角元素称为奇异值。奇异值是矩阵Data * Data.T特征值的平方根。
在科学和工程中，一直存在这样一个普遍事实：在某个奇异值的数目(r个)之后，其他的奇异值都置为0（因为值的量级相对于前r个太小），这意味着数据集中仅有r个重要特征，其他特征都是噪声或冗余特征。
如何选择前r个奇异值了？一个典型的做法是保留矩阵中90%的能量信息。另一个启发策略就是当矩阵中有上万个奇异值时，保留前2000或3000个。

SVD与PCA的关系
PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，
第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，
但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。

还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m * n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。
Amn * Pnn = A~mn

而将一个m * n的矩阵A变换成一个m * r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r < n)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。用数学语言表示就是：
Amn * Pnr = A~mr

SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量等等。SVD式子：
Amn ~= Umr * ∑rr * V.Trn
在矩阵的两边同时乘上一个矩阵V，由于V是一个正交的矩阵，所以V转置乘以V得到单位阵I，所以可以化成后面的式子
Amn * Vnr ~= Umr * ∑rr * V.Trn * Vnr
Amn * Vnr ~= Umr * ∑rr

将后面的式子与A * P那个m * n的矩阵变换为m * r的矩阵的式子对照看，其实V就是P，也就是一个变化的向量。这里是将一个m * n 的矩阵压缩到一个m * r的矩阵，
也就是对列进行压缩，如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的sample合并在一起，或者将一些没有太大价值的sample去掉）类似的变化如下：
Prm * Amn = A~rn

这样就从一个m行的矩阵压缩到一个r行的矩阵了，对SVD来说也是一样的，我们对SVD分解的式子两边乘以U的转置U'
U.Trm * Amn ~= ∑rr * V.Trn

这样我们就得到了对行进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，
有了SVD，我们就可以得到两个方向的PCA，如果我们对A’A进行特征值的分解，只能得到一个方向的PCA。

协同过滤
相似度计算
1 相似度 = 1/(1+距离)，  相似度介于0，1之间
2 皮尔逊相关系数，他度量2个向量之间的相似度，对用户评级的量级不敏感。在NumPy中有corrcoef函数计算，取值范围-1，1，通过0.5+0.5*corrcoef()把范围归一化到0，1之间。
3 余弦相似度 向量A，B夹角的余弦相似度定义 cos𝛩 = A⋅B / ||A||*||B||, ||A||表示A的2范数，可以定义向量的任一范数，不指定则都假设为2范数。

collaborative filtering 是通过将用户和其他用户的数据进行对比来实现推荐的。
若要计算给用户user推荐某个物品，需要估计user对物品的评分，根据待推荐物品与已评价物品a之间的相似度（很多用户对这2个物品评分之间的距离），
以及用户对已经评分过的物品a的评分作为权重，两者相乘即为对待推荐物品的一次评分估计，将所有物品(∑a)对待推荐物品的加权评分即为待推荐物品的最终评分估计。取评分最高的前N个待评价物品作为推荐结果。
推荐可以基于物品的相似度或者基于用户的相似度。如果用户数量少则使用基于用户相似度，否则基于物品相似度，减少计算量。对于大部分产品导向的推荐引擎而言，用户的数量往往大于物品的数量。
推荐引擎评价的指标是称为最小均方根误差的指标，使用交叉验证求误差，即将某些已知的评分去掉，然后对他们进行预测，最后计算预测值和真实值之间的差异。
利用SVD可以将数据矩阵简化为一个低维矩阵，在低维矩阵上计算相似度，SVD提高了推荐引擎的效果。
可能的问题：
在大规模数据集上，SVD分解会降低程序的速度。可以在程序调入时运行一次，在大型系统中，SVD每天运行一次或者频率更低，并且要离线运行。
在缺少数据上给出好的推荐，称为冷启动。为了将推荐问题看成是搜索问题，我们可能需要推荐物品的属性。将这些属性作为相似度计算所需的数据，这被称为基于内容的推荐。

#部分内容来源于网络，如有侵权请联系作者删除