机器学习基本算法总结4
机器学习基本算法总结
☞其他工具
代码在这，基于python3（原书代码是python2）
这里只是一个总结，原书已经讲解很清楚了，不清楚的直接看代码
目录
==========================
一、预测数值型数据：回归
1. PCA 相关描述
———————————————————————————————————-
优点：降低数据的复杂性，识别最重要的多个特征。
缺点：不一定需要, 且可能损失有用信息。
适用数据类型：数值型数据。
———————————————————————————————————-
1.1 降维
降维是对数据高维度特征的一种预处理方法。降维是将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的。在实际的生产和应用中，降维在一定的信息损失范围内，可以为我们节省大量的时间和成本。降维也成为了应用非常广泛的数据预处理方法。在降维中，我们对数据进行了预处理。之后，采用其他机器学习技术对其进行处理。
降维具有如下一些优点：
（1）使得数据集更易使用
（2）降低算法的计算开销
（3）去除噪声
（4）使得结果容易理解
1.2 PCA（主成分分析）
PCA(principal Component Analysis)，即主成分分析方法，是一种使用最广泛的数据压缩算法。在PCA中，数据从原来的坐标系转换到新的坐标系，由数据本身决定。转换坐标系时，以方差最大的方向作为坐标轴方向，因为数据的最大方差给出了数据的最重要的信息。第一个新坐标轴选择的是原始数据中方差最大的方法，第二个新坐标轴选择的是与第一个新坐标轴正交且方差次大的方向。重复该过程，重复次数为原始数据的特征维数。实上，这样也就相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，也就实现了对数据特征的降维处理。
那么，我们如何得到这些包含最大差异性的主成分方向呢？事实上，通过计算数据矩阵的协方差矩阵，然后得到协方差矩阵的特征值及特征向量，选择特征值最大（也即包含方差最大）的N个特征所对应的特征向量组成的矩阵，我们就可以将数据矩阵转换到新的空间当中，实现数据特征的降维（N维）。首先看一下均值，方差和协方差的计算公式：
由上面的公式，我们可以得到一下两点区别：
（1）方差的计算公式，我们知道方差的计算是针对一维特征，即针对同一特征不同样本的取值来进行计算得到；而协方差则必须要求至少满足二维特征。可以说方差就是协方差的特殊情况。
（2）方差和协方差的除数是n-1，这样是为了得到方差和协方差的无偏估计。具体推导过程可以参见博文。
1.3 PCA实现
PCA算法实现：
去除平均值
计算协方差矩阵
计算协方差矩阵的特征值和特征向量
将特征值排序
保留前N个最大的特征值对应的特征向量
将数据转换到上面得到的N个特征向量构建的新空间中（实现了特征压缩）
上述降维过程，首先根据数据矩阵的协方差的特征值和特征向量，得到最大的N个特征值对应的特征向量组成的矩阵，可以称之为压缩矩阵；得到了压缩矩阵之后，将去均值的数据矩阵乘以压缩矩阵，就实现了将原始数据特征转化为新的空间特征，进而使数据特征得到了压缩处理。当然，我们也可以根据压缩矩阵和特征均值，反构得到原始数据矩阵，通过这样的方式可以用于调试和验证。
2. PCA对半导体数据进行降维
- 数据缺失值的问题：
显然，数据集中可能会包含很多缺失值，这些缺失值是以NaN进行标识的。那么如何对待这些缺失值呢？如果存在大量的样本存在缺失值，显然选择将这些有缺失值得样本丢弃不可取；此外，由于并不知道这些值的意义，选择将缺失值替换为0也不是一个很好的决定。所以，这里我们选择将数据集中的特征缺失值，用数据集中该维度所有非NaN特征的均值进行替换。相比之下，采用均值替换的方法在这里是一个相对较好的选择。
PCA：如果确定需要保留哪些重要特征呢？PCA函数可以给出数据所包含的信息量，然后通过定量的计算数据中所包含的信息决定出保留特征的比例。
查看p249特征值结果，我们可以看到如下几个重要信息：
（1）里面有很多值都是0，这意味着这些特征都是其他特征的副本，都可以通过其他特征来表示，其本身没有提供额外的信息。
（2）可以看到最前面的15个特征值得数量级都大于105，而后面的特征值都变得非常小。这表明，所有特征中只有部分特征是重要特征。
下图示出了数据集前20个主成分占总方差的百分比：
可以看出，数据的绝大部分方差都包含在前面的几个主成分中，舍弃后面的主成分并不会损失太多的信息。如果只保留前面几个最重要的主成分，那么在保留了绝大部分信息的基础上，可以将数据集特征压缩到一个非常低的程度，显然大大提高了计算效率。
一旦通过特征值分析知道了需要保留的主成分个数，那么我们就可以通过pca函数，设定合适的N值，使得函数最终将数据特征降低到最佳的维度。
3. 总结
（1）降维是一种数据集预处理技术，往往在数据应用在其他算法之前使用，它可以去除掉数据的一些冗余信息和噪声，使数据变得更加简单高效，提高其他机器学习任务的计算效率。
（2）pca可以从数据中识别主要特征，通过将数据坐标轴旋转到数据角度上那些最重要的方向（方差最大）；然后通过特征值分析，确定出需要保留的主成分个数，舍弃其他主成分，从而实现数据的降维。
===============================================================
二、利用SVD来简化数据
1. SVD
———————————————————————————————————-
奇异值分解：
优点：简化数据，去除嗓声，提高算法的结果。
缺点：数据的转换可能难以理解。
适用数据类型：数值型数据。
———————————————————————————————————-
1.1 SVDh和推荐系统
我们知道，在实际生活中，采集到的数据大部分信息都是无用的噪声和冗余信息，那么，我们如何才能剔除掉这些噪声和无用的信息，只保留包含绝大部分重要信息的数据特征呢？除了上一章提到的PCA方法，本次介绍另外一种方法，即SVD。SVD可以用于简化数据，提取出数据的重要特征，而剔除掉数据中的噪声和冗余信息。SVD在现实中可以应用于推荐系统用于提升性能，也可以用于图像压缩，节省内存。
我们称利用SVD的方法为隐性语义索引（LatentSemantic Indexing, LSI) 或隐性语义分析（LatentSemanticAnalysis, LSA)。这些奇异值代表了文档中的概念或主题，这一特点可以用于更高效的文档搜索。两个不行：1.在词语拼写错误时，只基于词语存在与否的简单搜索方法会遇到问题。2.简单搜索的另一个问题就是同义词的使用。这就是说，当我们查找一个词时，其同义词所在的文档可能并不会匹配上。如果我们从上千篇相似的文档中抽取出概念，那么同义词就会映射为同一概念。
如何才能将原始数据变换到上述新空间中呢？下一节我们将会进一步详细地介绍SVD，届时将会了解到S V D是如何得到u和两个矩阵的。矩阵会将用户映射到BBQ/日式食品空间去。类似地，口矩阵会将餐馆的菜映射到BBQ/日式食品空间去。
1.2 矩阵分解
在很多情况下，数据中的一小段携带了数据集的大部分信息，其他信息则要么是噪声，要么是毫不相关的信息。而矩阵分解技术可以将原始矩阵表示成新的易于理解的形式，即将数据矩阵表示成两个或者多个矩阵相乘的形式。而我们这里要讲的SVD，就是最常用的一种矩阵分解技术，SVD将原始的数据矩阵D分解成三个矩阵,和。如果原始矩阵是m行n列，那么,和就分别是m行m列，m行n列，以及n行n列，即：
上述分解中会构建出一个矩阵该矩阵只有对角元素，其他元素均为0。另一个惯例就是，的对角元素是从大到小排列的。这些对角元素称为奇异值，它们对应了原始数据集矩阵Data的奇异值。回想上一章的PCA，我们得到的是矩阵的特征值，它们告诉我们数据集中的重要特征。中的奇异值也是如此。奇异值和特征值是有关系的。这里的奇异值就是矩阵特征值的平方根。另外：在某个奇异值的数目（r个）之后，其他的奇异值都置为0。这就意味着数据集中仅有r
个重要特征，而其余特征则都是噪声或冗余特征。
在python中的Numpy中有一个线性工具箱叫做linalg，它可以帮助我们实现矩阵的奇异值分解。
而在实际中，一个典型的做法是，保留矩阵中90%的能量信息。计算方法是，先求出所有奇异值的平方和，然后从第一个特征奇异值开始进行平方和累加，当达到总能量的90%以上时，这些特征奇异值就是要保留下来的奇异值，其余的奇异值全部舍弃。
2. 基于协同过滤的推荐引擎、相似度
协同过滤是通过将用户和其他用户的数据进行对比来实现推荐的。接下来，我们首先讨论物品之间的相似度计算，然后讨论在基于物品和基于用户的相似度计算之间的折中。最后，我们介绍推荐引擎成功的度量方法。
2.1 相似度的计算
推荐引擎是机器学习的一个重要应用，比如，Amazon会根据顾客的购买历史向他们推荐物品，Netflix会像其用户推荐电影，新闻网站会对用户推荐新闻报道等等。当然，有很多方法可以实现推荐功能，比如基于内容的推荐，基于协同过滤的推荐，或者多个推荐相组合的推荐等等。基于内容的推荐，是通过机器学习的方法，比如决策树，神经网络等从用户对于物品的评价的内容特征描述中得到用户感兴趣的资料，而不需要其他用户的数据。而基于协同过滤的推荐方法则是通过将用户与其他用户的数据进行比对，依据相似度的大小实现推荐。
首先，在进行协同过滤之前，我们需要将数据转化为合理的形式，即将数据转化为矩阵的形式，这样，便于我们处理和计算相似度。当我们计算出了用户或者物品之间的相似度，我们就可以利用已有的数据来预测未知的用户喜好。比如，我们试图对某个用户喜欢的电影进行预测，推荐引擎会发现有一部电影该用户没有看过。然后，就会计算该电影和用户看过电影之间的相似度，如果相似度很高，推荐算法就会认为用户喜欢这部电影。
这里，协同过滤的相似度计算，并不是计算两个物品的属性信息的相似程度，而是基于用户对这些物品的评价信息来计算相似度。这也是协同过滤所使用的方法，即不关心物品的描述属性，而只关心用户对于物品的评价观点来进行相似度计算。
相似度的计算方法有很多，比如欧氏距离，相关系数，余弦距离等。相关系数和余弦距离，是对两个向量之间的比较。这两种方法相对于欧氏距离的一个优势在于，它们对于用户的评级的量级并不敏感。为了将相似度归一化，我们需要对着三种方法计算得到的结果，进行归一化处理，使其最终的结果位于（0,1）内，即：
欧式距离相似度=1/(1+欧式距离)
相关系数相似度=0.5+0.5*corrcoef()
余弦距离相似度=0.5+0.5*（cosine距离）
上面有了，相似度的计算方法，那么接下来要考虑的问题就是，是计算用户的相似度还是计算物品的相似度呢？显然，数据的行代表的是基于用户，而列代表的则是基于物品。具体使用哪一种相似度计算，需要根据用户或者物品的数目。因为，不管是基于物品的相似度还是基于用户的相似度都会随着各自的数目的增加，计算的时间也相应增加。所以，为了节省计算时间，我们按照数目相对较少的那一个量去计算相似度。显然，对于一家固定的餐馆，其菜品的数目基本是固定的，变化不大，但其用户数目却可能会发生很大的变化，所以，一般情况下，协同过滤的推荐方法会偏向于计算基于物品的相似度。
2.2 推荐引擎的评价
那么如何对推荐引擎进行评价呢？此时，我们既没有预测的目标值，也没有用户来调查他们对于预测的满意程度。这么我们采用前面多次使用的交叉测试的方法。即，将某些已知的物品评分删掉，然后对这些物品的评分进行预测，然后比较预测值和真实值的差异。
通常用于推荐系统的评价的指标是最小均方根误差。即，首先计算平方误差的均值，然后再对平均值开根号。
2.3 餐馆菜菜肴引擎
首先我们构建一个基本的推荐引擎，它能够寻找用户没有尝过的菜肴。然后，通过SVD来减少特征空间并提高推荐效果。
基本的推荐系统基本流程如下：
（1）寻找用户没有评级的菜肴，即在用户-物品矩阵中的0值
（2）在用户没有评级的所有物品中，对每一个物品预测一个可能的评级分数。
（3）对这些物品的评分从高到低排序，返回前N个物品。
我们知道，推荐系统对于用户没有评分的菜肴，通过计算该用户与其他用户评分的菜肴的相似度，来预估出该用户对于该未评分菜肴的评分，从而选择出评分最高的前N个菜肴推荐给用户。
有了基本的协同过滤的推荐系统，我们接下来在推荐系统中引入SVD，将高维的数据矩阵映射到低维的矩阵中去，然后，在低纬空间中，利用前面的相似度计算方法来进行推荐。
相比于普通的推荐系统，增加了SVD的计算，即对数据矩阵进行奇异值分值，保留包含数据信息90%能量的m奇异值，组成的方阵。然后，利用矩阵U的前m列和的奇异值方阵，将数据矩阵映射到低纬的空间。
3. 推荐系统面临的挑战
（1）当数据集规模很大时，SVD分解会降低程序的速度，所以，在大型系统中，SVD运行的频率很低，并且需要离线运行。
（2）实际的数据矩阵中0的数目很多，显然会造成空间资源的浪费，如果有效的存储这些数据，可以帮助我们节省内存和计算开销。
（3）在程序中，每次需要计算一个得分时，都要计算多个物品的相似度得分。我们知道，这些得分记录的是物品的相似度。所以，我们可以离线计算相似度得分并保存，当需要的时候调用即可。
（4）冷启动问题，即如何在缺乏数据时给出好的推荐。这时，我们可以将推荐看成是搜索问题，这就要用到需要推荐物品的属性。在餐馆菜肴的推荐系统中，我们可以通过各种标签来标记菜肴，比如素食，美式BBQ,价格高低等。同时，我们也可以将这些属性作为相似度计算所需要的数据，即基内容的推荐。
4. 基于SVD的图像压缩
SVD除了应用在推荐系统中，还可以用来进行数据压缩，比如图像压缩。比如，对一个像素的图像，首先，我们采用矩阵的形式存储该图像；然后，对于图像中每个像素值，我们采用阈值函数，将像素值大于0.8像素设置为1，否则设置为0；接下来，我们对该图像进行奇异值分解，得到矩阵和，我们保留包含图像信息90%的奇异值；最后，我们只保留矩阵U的前m列，矩阵VT的前m行，以及m个奇异值，就可以完成原始矩阵的重构。假设：，那么需要保存的数值个数为，相比于原始矩阵的1024，获得了接近4倍的压缩比。
五，小结
SVD是一种类似于PCA的降维工具，我们可以利用SVD来提取矩阵的重要特征，选择保留数据90%的能量的情况下，剔除数据中的噪声和冗余信息。SVD的一个强大的应用是提高推荐系统的性能，通过将数据矩阵映射到低纬的空间进行计算相似度，从而提升推荐引擎的效果。SVD还可以用于数据的压缩等，从而达到节省内存的目的。