【BitTiger读书会】· 第二十三期《大数据：互联网大规模数
【BitTiger读书会简介】
BitTiger读书会，以书会友。以报告方式，加强组织表达力；以讨论方式，激荡思考判断力，期能扩充知识领域，养成读书习惯。
每周一本好书，一年阅读50本书，集众智，挑好书，留精华内容，创优质社群。
BitTiger读书会，欢迎您的加入！
在第二十二期里，Benjamin结合自己和作者对于人工智能和终极算法的看法，和大家分享了《The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World》（终极算法： 机器学习和人工智能如何重塑世界）这本书。在即将到来的第二十三期中，木易将会带领我们一起阅读《大数据：互联网大规模数据挖掘与分布式处理》（Mining of Massive Datasets），从大数据的视角来理解和探讨数据挖掘的理论基础以及发展愿景。
【分享书籍】
【BitTiger读书会】· 第二十三期《大数据：互联网大规模数据挖掘与分布式处理》
《大数据：互联网大规模数据挖掘与分布式处理》（Mining of Massive Datasets）
【书籍介绍】
本书作者Anand Rajaraman, 是数据库和Web技术领域权威，创业投资基金Cambrian联合创始人，斯坦福大学计算机科学系教授。另一个Jeffrey David Ullman, 是美国国家工程院院士，计算机科学家，斯坦福大学教授。
本书以大数据环境下的数据挖掘和机器学习为重点，全面介绍了实践中行之有效的数据处理算法。简单来说，本书从算法的角度来看待数据挖掘，即数据挖掘是将算法应用于数据，而不是使用数据来“训练”某种类型的机器学习引擎。这本书偏向理论方向，从实例出发来介绍相关挖掘技术的理论基础以及发展愿景。
【嘉宾介绍】
木易，TAMU纯数学PHD，统计讲师，研究大数据分析的张量方法。
【加入读书会】
获取BitTiger读书会系列读书分享信息，请添加微信ID: saraincs，备注“读书”加入BitTiger读书会活动群
【BitTiger读书会】· 第二十三期《大数据：互联网大规模数据挖掘与分布式处理》
【分享文稿】
本书主要内容包括：
分布式文件系统以及MapReduce工具；
相似性搜索；
数据流处理以及针对易丢失数据等特殊情况的专用处理算法；
搜索引擎技术，如谷歌的PageRank；
频繁项集挖掘；
大规模高维数据集的聚类算法；
Web应用中的关键问题——广告管理和推荐系统；
社会网络图挖掘；
降维处理，如SVD分解和CUR分解；
大规模机器学习。
依照我的个人兴趣，我主要分享：
数据挖掘概念；MapReduce工具；谷歌的PageRank；大规模高维数据集的聚类算法；Web应用中的关键问题—推荐系统；降维处理；大规模机器学习。
第一章为全书的导论部分，首先阐述数据挖掘的本质，并讨论其在多个相关学科中的不同理解。数据挖掘（data mining）是数据“模型”的发现过程。统计学家认为数据挖掘就是统计模型（statistical model）的构建过程，而这个统计模型指的就是可见数据所遵从的总体概率分布。有些人将数据挖掘看成是机器学习的同义词。机器学习的实践者将数据当成训练集来训练某类算法，比如贝叶斯网络、支持向量机、决策树、隐马尔可夫模型等。某些场景下上述的数据利用方式是合理的。机器学习擅长的典型场景是人们对数据中的寻找目标几乎一无所知。比如， Netflix竞赛要求设计一个算法来预测观众对影片的评分时，基于已有评分样本的机器学习算法获得了巨大成功。
其他的大部分数据建模方法可以描述为下列两种做法之一：
(1) 对数据进行简洁的近似汇总描述；
(2) 从数据中抽取出最突出的特征来代替数据并将剩余内容忽略。
第二章介绍相似性搜索：Map Reduce。 由于输入的数据量巨大，要想在可接受的时间内完成运算，只有将这些计算分布在成百上千的主机上。为了处理并行计算、分发数据，Jeff Dean的团队设计一个新的抽象模型：在输入数据的“逻辑”记录上应用Map操作得出一个中间key/value pair集合，然后在所有具有相同key值的value值上应用Reduce操作，从而达到合并中间的数据，得到一个想要的结果的目的。
使用MapReduce模型，再结合用户实现的Map和Reduce函数，我们就可以非常容易的实现大规模并行化计算。
这个工作通过简单的接口来实现自动的并行化和大规模的分布式计算，通过使用MapReduce模型接口实现在大量普通的PC机上高性能计算。
第五章介绍了一种最有趣的数据汇总形式谷歌的PageRank。在这种形式的Web挖掘当中，Web的整个复杂结构可由每个页面所对应的一个数字归纳而成。
这种数字就是网页的PageRank值，即一个Web结构上的随机游走者在任意给定时刻处于该页的概率（这是极其简化的一种说法）。
PageRank的一个非常好的特性就是它能够很好地反映网页的重要性，即典型用户在搜索时期望返回某个页面的程度。
第七章介绍了另一种重要的数据汇总形式是聚类。
【聚类】：将训练集中的瓜分为若干组。
eg：将训练决策树时所用的100000个西瓜分为：本地瓜、北方瓜、南方瓜、进口瓜等。
【簇】：每组称为一个簇。
eg：本地瓜、北方瓜、南方瓜、进口瓜，是四个簇。
注意：这些簇，并非主动划分，而是自动划分。也就是说，无监督学习只负责分类，不负责解释每个类是什么。意思是，这100000个瓜，被无监督学习分为了四类。分好之后，我一看，发现它分的第一类是本地瓜，第二类是北方瓜，第三类是南方瓜，第四类是进口瓜。
但是，还有可能分的这四类是：深色瓜、较深色瓜、较浅色瓜、浅色瓜。
簇的含义是在分类后得知的。
当然，我当然可以说我就要让它按地域给我分出这四类来。
只不过结果却有可能是按颜色分了四类。
那么无监督学习如何分出好瓜和坏瓜？
理论上就需要调整一系列参数，让聚类算法可以刚好将好瓜和坏瓜通过聚类区分为两类。
第九章讲推荐系统。推荐系统用于预测用户对物品的“评分”或“偏好”。推荐系统近年来非常流行，应用于各行各业。推荐的对象包括：电影、音乐、新闻、书籍、学术论文、搜索查询、分众分类、以及其他产品。要做推荐系统，最基本的一个数据就是，用户-物品的评分矩阵，如下图所示
D1 D2 D3 D4
U1 5 3 - 1
U2 4 - - 1
U3 1 1 - 5
U4 1 - - 4
U5 - 1 5 4
矩阵中，描述了5个用户(U1,U2,U3,U4 ,U5)对4个物品(D1,D2,D3,D4)的评分(1-5分)，- 表示没有评分，现在目的是把没有评分的 给预测出来，然后按预测的分数高低，给用户进行推荐。我们采用矩阵分解的办法，定义R是评分矩阵，设为NM维(N表示行数，M表示列数)，可以分解为P跟Q矩阵，其中P矩阵维度NK，P矩阵维度K*M。
P矩阵是N个用户对K个概念的关系，Q矩阵是K个概念跟M个物品的关系，K是一个参数。
我们定义损失函数为平方损失，就是最小化每一个元素(非缺失值)的e(i,j)的平方和
基于梯度下降的优化算法，矩阵P和Q里面的每个元素的更新方式
为了避免过拟合我们可以加一个正则项，目标函数变成
相应的P和Q矩阵各个元素的更新为
采用随机梯度下降，我们有
至此，P,Q矩阵元素求出来了之后，某个用户i对某个物品j的评分就是p(i,1)*q(1,j)+p(i,2)*q(2,j)+…+p(i,k)*q(k,j)。
第十一章讲降维方法。很多不同来源的数据可以表示为大矩阵。我们希望用行数列数少一些的小矩阵来逼近大矩阵，以利于高效处理数据。这个过程叫做降维。
我们可以将矩阵想象为两类实体的表示，比如观众对电影的评级。只存在少量概念（科学类，浪漫类等等）解释为什么观众喜欢某个电影。我们可以将矩阵分解为几个矩阵的乘积，矩阵分别表示实体和概念的关联。其中的关键点在于利用矩阵的奇异值分解，如下：
根据SVD求取特征值和特征向量：[U,S,V] = SVD（Σ）， S是一个与A同大小的对角矩阵S（由Σ的特征值组成），两个酉矩阵U和V，满足Σ = USV’。若A为m×n阵，则U为m×m阵，V为n×n阵。奇异值在S的对角线上，非负且按降序排列。那么对于方阵Σ呢，有
Σ = USV’。由于方阵的SVD相当于特征值分解，所以事实上U = V, 即Σ = USU’, U是特征向量组成的正交矩阵。从n维降维到k维，也就是选出特征值最大的k个。 按特征值从大到小排列，重新组织U。我们得到了一个n×n的矩阵Σ和U，这时，我们就需要从U中选出k个最重要的分量；即选择前k个特征向量，即为U_reduce, 该矩阵大小为n×k
这样对于一个n维向量x，就可以降维到k维向量z了：
第十二章介绍大规模学习算法：机器学习所研究的主要内容，是关于在计算机上从数据中产生“模型”的算法，即“学习算法”。学习算法的作用：1.基于提供的经验数据产生模型；2.面对新情况时，模型可提供相应的判断。“没有免费的午餐”定理（NFL定理）：总误差与学习算法无关。
书中首先介绍了感知机，就是二类分类的线性分类模型，其输入为样本的特征向量，输出为样本的类别，取+1和-1二值，即通过某样本的特征，就可以准确判断该样本属于哪一类。顾名思义，感知机能够解决的问题首先要求特征空间是线性可分的，再者是二类分类，即将样本分为{+1, -1}两类。
作为监督学习的一种方法，感知机学习由训练集求得感知机模型，即求得模型参数w，这里x和y分别是特征向量和类别（也称为目标）。基于此，感知机模型可以对新的输入样本进行分类。
接下来介绍了支持向量机，支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个（等价于感知机)，但是几何间隔最大的分离超平面是唯一的。
这里的间隔最大化又称为硬间隔最大化（与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。
支持向量机（support vector machines，SVM)是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
支持向量机学习方法包含构建由简至繁的模型：通过硬间隔最大化（hard margin maximization)，学习一个线性的分类器，即线性可 分支持向量机，又称为硬间隔支持向量机；当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization)，也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；当训练数据线性不可分时，通过使用核技巧 (kernel trick)及软间隔最大化，学习非线性支持向量机。
本书以大数据环境下的数据挖掘和机器学习为重点，全面介绍了实践中行之有效的数据处理算法。简单来说，本书从算法的角度来看待数据挖掘，即数据挖掘是将算法应用于数据，而不是使用数据来“训练”某种类型的机器学习引擎。这本书偏向理论方向，从实例出发来介绍相关挖掘技术的理论基础以及发展愿景。另一方面，本书的缺点是废话比较多，概念阐述不清晰，数学推导也不够精简，所以建议大家配合周志华的机器学习书和其他资料一起阅读。
