本文“发表于微博自媒体”，微博：@钻石草帽

Kaggle是一个举办数据科学竞赛的网站

本文为《Data Science from Scratch: First Principles with Python》的读书笔记

---

重要原则

• 充分理解数据，尽可能测试每一个属性，观察其对相关性的影响，避免辛普森悖论
• 相关不是因果
• 正确理解p-value的价值
• 贝叶斯推断不仅数学原理复杂，而且存在主观性缺陷
• 机器学习是完成对数据收集、理解、清理和整理后才做的工作

预备知识

预备知识的内容结构:

• 概念
• 数学

概念

概念的内容结构：

• 数据科学
• 模型
• 机器学习

数据科学

• 主要内容是把商业问题转换为数据问题，然后收集数据、理解数据、清理数据、整理数据格式，再执行机器学习

模型

• 针对存在于不同变量之间的数学或概率联系的一种规范

机器学习

• 概念
  • 创建并使用那些由学习数据而得出的模型，也可以称为预测建模或数据挖掘，目标是用已存在的数据来开发可用来对新数据预测多种可能结果的模型
• 模型分类
  • 可分为有监督的模型（有正确答案可供学习）
  • 无监督模型（没有正确答案）
  • 半监督模型（部分有正确答案）
  • 在线模型（根据新加入数据做持续调整）
• 拟合
  • 拟合的实质是模型构建及其参数估计
  • 过拟合（overfitting，一个训练数据上表现良好，但对任何新数据的泛化能力却很差的模型），明显复杂的模型会导致过拟合，解决方法是使用不同的数据来训练和测试模式，如用三分之二的数据训练，用剩余三分之一的数据测试
    • 出错类型1：如果划分训练数据集和测试数据集的目的是判断模型，训练和测试数据集中的共有模式可能无法泛化至大型数据集上；解决方案是，调整训练模型，或重新划分训练集和测试集
    • 出错类型2：如果划分训练集和测试集的目的不仅仅是判断模型，而是选择模型，并且以“在测试集上表现最好的模型”为选择依据，那么，测试集本质上是另一个训练集，无法达到划分训练集和测试集的目的，解决方案是，将数据划分为3部分，1个用来建模的训练集、1个为在训练好的模型上进行选择的验证集、1个用来判断最终模型的测试集
  • 欠拟合（underfitting，产生的模型在训练数据上没有好的表现）
• 正确性
  • 建立模型做二元判断
    • 有4类可能的结果，即将预测的真假和事实的真假表示为矩阵，：（预测真，事实真）、（预测真，事实假）、（预测假，事实真）、（预测假，事实假）
    • （预测真，事实假）为统计中的第1类错误，（预测假，事实真）为统计中的第2类错误
    • 为后续说明便利，假设4类结果的判断次数依次为pt、pf、npf、npt
  • 准确率（accuracy）是指在所有判断的次数中判断正确的比例，即（pt + npt）/（pt + pf + npf + npt）
  • 查准率（precision）是指“预测真”的判断准确率pt/（pt + pf）
  • 查全率（recall）是指“事实真”时作出“预测真”的判断比例pt/（pt + npf）
  • FI得分，是指查准率和查全率的调和平均值
  • 模型的选择通常是查准率和查全率之间的权衡，也是第1类错误和第2类错误之间的权衡
• 特征
  • 特征的严肃定义是，提供给模型的任何输入
  • 也可以这样理解，从数据中提取最少的因素来界定所要研究的问题
  • 还可以这样理解，数据如果没有足够特征，则可能欠拟合；如果特征太多，则容易过拟合
• 偏倚和方差
  • 偏倚是指测量值对真值的偏离；方差是指样本各个值对样本平均值的偏离
  • 如果低偏倚和高方差对应过拟合，高偏倚和低方差对应欠拟合
  • 如果模型有高偏倚，则加入更多的特征；如果有高方差，既可以移除特征，也可以获取更多数据
  • 偏倚和方差的权衡是思考过拟合和欠拟合的另一种角度
• 参考资料
  • Coursera的机器学习课程
  • 加州理工学院的机器学习课程
  • 《The Elements of Statistical Learning》这本数学化的教材

数学

• 随机性
• 向量及其运算
• 矩阵及其运算
• 相关分析
• 线性代数
  • 导数的理解与计算
• 概率论
  • 独立性
  • 条件概率
  • 贝叶斯定理
  • 随机变量
  • 连续分布
  • 离散分布
  • 正态分布
  • 密度函数
  • 分布函数
  • 中心极限定理
  • 贝叶斯推断
• 假设检验
  • 零假设与替代假设
    • 零假设H0：代表默认的立场
    • 替代假设H1：代表与零假设对比的立场
  • 显著性：犯第1类错误概率
    • 第1类错误：原假设正确，但拒绝了原假设
    • 第2类错误：原假设错误，但没有拒绝原假设
  • 置信区间：重复很多次实验，其中90%-99%的“真”参数会落在观测到的置信区间内
  • p-hacking
    • 本质是质疑统计学中p值的价值，The Extent and Consequences of P-Hacking in Science这篇文章中给出了p-hacking定义，即通过对数据、统计方法的选择，使统计分析结果从不显著变为显著；另一篇更早的关于p-hacking的文章Scientific method: Statistical errors发表于《Nature》上；《American Scientist》也有一篇讨论因p-hacking引起可能的统计危机的文章The Statistical Crisis in Science；美国统计学会也发表一篇名为Statement on Statistical Significance and P-Values的声明，确定了使用P值的6条原则
    • 解决方案：要在审查数据之前确定假设，要在做假设之前整理好数据，牢记p值不是靠直觉得出；替代方案是贝叶斯推断
  • 贝叶斯推断
    • 思路：将未知参数作为随机变量，从参数的先验分布出发，利用数据和贝叶斯定理计算更新后的后验分布，不再对检验本身给出概率推断，而是对参数本身给出概率推断
    • 这种检验方式有争议，部分源于复杂的数学原理，部分源于先验分布的主观性
• 梯度下降（gradient descent）
  • 解决最优化问题，如“最小化模型残差”，适用于从零开始逐步解决问题
  • 梯度理论
    • 梯度在微积分中表示偏导数向量，为计算最大或最小可能值提供方向，在这个方向上，函数增长或减少最快
    • 最大化函数的算法，首先从1个随机初始点开始计算梯度，既可以是最大化方向，也可以是最小化方向，当在梯度方向上跨越一小步后，再从1个新的初始点重复这个过程，直至梯度变得非常小
    • 该算法存在局限；当函数存在全局极值时，该方法可能找到它；但如果存在多个局部极值时，这种方法可能找不到，因为，计算会陷入死循环
  • 梯度实现
    • 以x变动t时，函数差商的极限来定义梯度
    • 初始值的选取可使用随机数
    • 确定移动的步长有3种常用方法：第1种，固定步长；第2种，随时间逐步减小的步长；第3种每一步都通过最小化目标函数的值来选择合适的步长；其中，第3种方法的计算代价最大
  • scikit-learn中有梯度计算模块
• 概率分布
  • 离散分布
    • 均匀分布
    • 二项分布（伯努利分布）
    • 几何分布
    • 超几何分布
    • 泊松分布
  • 连续分布
    • 连续均匀分布
    • 正态分布（高斯分布）
    • 指数分布
    • F分布
    • 学生t-分布
    • 卡方分布
    • 韦伯分布（Weibull Distribution）
    • 伽马分布
• 参考资料
  • Introduction to Probability

算法

K近邻算法

• 最近邻分类（nearset neighbors classification）思想：确定目标后，选择1个或多个维度，参照个体行为被这些维度影响或刻画的程度，观察最接近个体的邻居比观察所有的邻居会得到更好的预测结果
• 模型仅要求某种距离概念以及一种彼此接近的点具有相似性质的假设，没有多少数学假设和复杂处理，这种思想有意忽略大量信息，预测只依赖最接近它的点
• 最近邻算法不能帮助理解所观察到的任意现象的产生机制
• 出现并列结果时的处理方法
  • 随机选择获胜者
  • 根据距离加权并选择加权的获胜者
  • 减少k值直到找到唯一的获胜者
• 高维空间中，因为空间过于巨大，导致最邻近的2个点的距离并不比点和点的平均距离小，这意味着2个点邻近没有价值
• scikit-learn库中有许多邻近模型

朴素贝叶斯算法

• 利用贝叶斯定理计算条件概率
• 基本假设是，各条件之间相互独立（这是一个极端假设）
• 由于该算法涉及接近于0的浮点数计算，而计算机不擅长处理这类浮点数，也就是可能产生下溢（underflow）问题，因而经常使用$e^{log}$的等效形式
• 伪记数（pseudo count）
  • 当某个条件在训练集中不出现时，将会导致该条件的条件概率永远为0，使用伪记数作为平滑技术避免这种情况的发生
  • 通过$P(X_i|S) = \frac{(k + \text{含有某个条件的数量})}{(2k + \text{总数量})}$公式实现，$P(X_i|\lnot S)$采用类似的处理方法
• scikit-learn库提供了一个名为BernoulliNB的模型，可实现朴素贝叶斯算法以及基于该算法的变种

线性回归

• 简单线性回归
  • 其思想是，通过最小二乘法使参数估计的残差平方和尽可能小
  • 作用是了解变量间线性关系的性质
  • 使用决定系数或者$R^2$来评估模型对数据的拟合效果，表示纳入模型的自变量引起的变动占总变动的百分比
  • 使用最小二乘法的原因在于极大似然估计
• 多重回归分析
  • 多重回归是在简单线性回归基础上增加多个自变量的回归分析
  • 多重回归分析较简单线性回归分析增加以下假设：
    • $x$的各个列线性无关
    • $x$的各列与误差$\varepsilon$无关
• 回归实践
  • 回归分析中需要使用zip函数将数据$X$和$Y$放在一起，以确保对自变量和因变量一起进行采集
  • 线性回归通常需要处理很多变量，但涉及变量越多，越容易产生过拟合现象，并且，非零系数越多，越难以解释清楚它们的意义，所以，需要采用正则化的技术，给误差项添加一个会随着$\beta$增大而增大的惩罚项，如此，惩罚项越大就能防止系数过大，回归分析的目标也变更为将误差项和惩罚项的组合之最小化；应用这种方法前，必须调整数据规模，一种极端的情况是，将几年数据变成几百年的数据，最小二乘系数会骤增，惩罚也会骤增
• 参考资料
  • scikit-learn的linear_model模块提供了线性回归模型，也提供了Ridge回归、Lasso回归以及其他类型的正则化算法
  • Statsmodels库也包含了线性回归模型

逻辑回归

• 逻辑回归使用Logistic函数解决0和1的二元判断问题；简单的Logistic函数如$P(t)=\frac{1}{1 + e^{-t}}$
• Logistic函数模仿人口增长的$S$形曲线，起初阶段是指数增长；变得饱和后增长变慢；达到成熟时增长停止
• 0与1的分类方法
  • 方法1：用已估计参数和数据代入函数并使函数等于0的点就是分类边界线，该边界实际上是一个超平面（hyperplane），它将参数空间一分为二，一般对应预测为0的情况，另一半对应预测为1的情况
  • 方法2：寻找的超平面只要对训练数据的分类效果最佳即可，即直至向量机（support vector machine）思想，即寻找将距离每个类别中的最近点的距离最大化的超平面
    • 寻找超平面的过程是一个最优化过程
    • 超平面不一定存在
    • 可以考虑将数据映射到一个更高维的空间中来寻找超平面，这种方法成为核方法（kernel trick），它不需要真的把数据点映射到更高维空间，而是使用“核”函数来计算更高维空间中的点积，并用它们来寻找超平面
• 参考资料
  • scikit-learn库同时提供了逻辑回归和支持向量机的模块
  • scikit-learn库使用libsvm实现支持向量机

决策树

概念

• 决策树通过树结构表示各种可能的决策路径（decision path）以及每个路径的结果
• 优点
  • 提供建议
  • 易于理解和解释
  • 推断过程完全透明
  • 处理混合在一起的数值属性和条件属性
  • 可以对缺失属性的数据进行分类
• 缺点
  • 找出“最优”决策树需要巨大的计算量
  • 容易出现对训练数据的严重过拟合
• 分类
  • 输出判决结果的分类决策树（classification tree）
  • 输出数值结果的回归决策树（regression tree）

建立决策树

• 关键
  • 提出哪些问题
  • 提问顺序
• 熵
  • 熵（entropy）指代“信息含量”，也用来表示混乱程度，数据科学中用它来表示与数据相关的不确定性
  • 假设有数据集$S$，每个元素都标明了所属类别，即元素属于有限类别$C_1,...,C_n$中的一种，如果$p_i$表示$c_i$类别中的数据所占的比例，熵定义为$H(S) = -p_1\log_{2}p_1 -... -p_n\log_{2}p_n$，按照惯例，$0\log0=0$，其中，$-p_i\log_{2}p_i$都是非负，并且当$p_i$接近0或1时，熵的值也接近0
• 分割之熵
  • 熵计算单组标记数据的熵，但决策树每前进一步，都要提出一个问题，而每一个问题都会把数据分割为一个或多个子集
  • 分割之熵是表示对数据集的分割效果的熵，也就是说，如果划分方法得到子集的熵较低，就说这个划分方法的熵较低，反之则反
  • 如果把数据集$S$划分为数据子集$S_1, ... , S_m$，各个子集相应数据量所占比例为$q_1, ... , q_m$，那么可通过加权的形式来计算分割之熵，即$H = q_1H(S_1) + ... + q_mH(S_m)$
    • 问题：通过具有许多不同值的属性进行数据划分，往往会由于过度拟合而导致过低的熵
    • 方案：尽量避免使用有大量的可能取值的属性来创建决策树
• 节点
  • 决策节点：提出一个问题，并根据问题的答案指导下一步如何走
  • 叶节点：提供预测结果
• 贪婪算法
  • 假设条件
    • 标记过的数据，例如，将每条属性列表标记True或False
    • 用来选择下一个分支的属性列表，例如水平、语言、是否有博士学位这3条属性及其结果所组成的“属性-值”字典
  • 算法
    • 如果所有数据都有相同的标签，那么创建一个预测最终结果即为该标签所示的叶节点，然后停止
    • 如果属性列表是空的，即没有更多的问题可问了，就创建一个预测结果为最常见的标签的叶节点，然后停止
    • 否则，尝试用每个属性对数据进行划分
    • 选择具有最低划分熵的那次划分的结果
    • 根据选定的属性添加一个决策节点
    • 针对划分得到的每个子集，利用剩余属性重复上述过程
• 随机森林
  • 解决决策树“容易出现对训练数据的严重过拟合”的缺点
  • 基本思路是将过程确定的决策树转换为随机的决策树
    • 一种实现方法是使用Bootstrap抽样处理，即不是利用所有输入数据来训练决策树，而是使用随机取样结果训练决策树，该技术为Bootstrap集成法（Bootstrap aggregating），或者简称bagging方法
    • 另一种实现方法是不断变换选择最佳属性进行划分，即随机从全部剩余属性的子集中寻找最佳属性进行划分，这种技术称为集成学（ensemble learning），能够将多个较弱的模型（weak learner），通常是高偏差、低方差模型，组合成一个更加强大的模型
• 参考资料
  • scikit-learn库提供了许多决策树模型，此外还提供了名为ensemble的集成方法模块
  • Wikipedia提供了学习决策树的基础资料

神经网络

• 概念
  • 神经网络（artificial neural network）是受大脑启发而开发出的一种预测模型
  • 特征
    • 把大脑看做相互连接的神经元
    • 每个神经元都以其他神经元的输出为输入进行相应计算
    • 如果超过某个阈值，则该神经元进入激活状态，否则保持非激活状态
    • 大部分神经网络都是“黑盒子”，即使考察了其工作细节，也很难知道它是如何解决问题的
    • 大型神经网络的训练难度非常大
    • 深度学习作为数据科学的一个分支，大量应用神经网络
    • 初期的大多数数据问题都不适合使用神经网络处理，如果试图打造一个催生奇点的人工智能，或许神经网络是个不错的选择
• 感知器（perception）
  • 最简单的神经网络
  • 由具有$n$个二进制输入的单个神经元组成的神经网络，对输入值加权求和，如果加权和大于等于0，则激活神经元；通过正确选择权值，可解决简单问题
  • 本质是根据点$x$的超平面将问题空间分隔成2部分
• 前馈神经网络
  • 前馈（feed-forward）神经网络由多层构成，每层由众多神经元组成，然后逐层相连，一般情况下，有1个输入层（接收信号不做修改直接向前馈送）、1个或者多个隐藏层（每层都由神经元组成，并以前一层的输出为输入，进行计算后传递给下一层），以及1个输出层（提供最终输出结果）
  • 前馈神经网络与感知器相同之处在于，每个输入和偏移项都会有一个权重，并对输入加权求和；前馈神经网络与感知器不同之处在于，不是直接输出加权和，而是将其平滑处理后输出近似值，原因是，要训练神经网络就得使用微积分，要使用微积分就得使用连续函数，而阶梯函数无法确保处处连续，但sigmoid函数却是一个非常好的平滑近似函数；sigmoid函数是logistic函数的外形，logistic函数是sigmoid函数的特定形式
  • 有了平滑函数，可以将神经元简单表示成一个权重列表，列表长度等于神经元输入数量加1，即加上偏移项的权重；而神经网络是神经元组成，可将神经网络表示为各个层组成的列表，其中每一层就是该层中的神经元所组成的一个列表；这就是说，神经网络可以用（权重）列表的（神经元）列表的（层）列表来表示
• 反向传播训练算法
  • 通常不以手动方式建立神经网络，一部分原因在于神经网络解决的是比较大型的问题，另一部分原因是通常无法“通过推理得出”这些神经元的安排方式；但是，尽管神经网络的运行不是完全透明的，但可以通过检查隐藏层的权重了解它们的识别情况
  • 一般使用数据来训练神经网络，一种流行的训练算法是反向传播（backpropagation），它与梯度下降类似；假设有一个含有输入向量和相应目标输出向量的训练集，以及一组权重，使用以下算法调整权重
    • 在输入向量上运行前馈神经网络，从而得到网络所有神经元的输出
    • 每个输出神经元都会得到一个误差，即目标值与输出值之差
    • 计算作为神经元权重的函数的误差的梯度，然后根据误差降低最快的方向调整权重
    • 将这些输出误差反向传播给隐藏层以便计算相应误差
    • 计算这些误差的梯度，并利用同样的方式调整隐藏层的权重
    • 多次迭代直至网络收敛
• 参考资料
  • Coursera的机器学习的神经网络课程
  • Michael Nielsen编写的一本免费书籍《Neural Networks and Deep Learning》
  • PyBrain是一个简单的Python神经网络库
  • Pylearn2是一个更加高级同时也更难使用的神经网络库

聚类分析

• 聚类（cluster）分析是一种无监督学习方法，即利用完全未经标注的数据进行工作，其目标是对数据进行分类
• 原理
  • 数据源存在某种形式形成的聚类
  • 聚类问题没有“正确”的标准，对于每一种方案而言，都可以按照自设的“优良聚类”标准不断进行优化
  • 聚类本身无法对自己进行标注，如果要标注的话，必须考察每个聚类中的底层数据
• k-均值算法（k-means）
  • k-均值算法是一种最简单的聚类分析方法，对每个$d$维空间中任意向量的输入，识别其所组成的聚类，有时还要找出每个聚类的代表值
  • 通常首先选出聚类$k$的数目，然后把输入划分为集合$S_1, ... ,S_k$，并使得每个数据到其所在聚类的均值（中心对象）的距离的平方和最小化
  • $k$的选择方法：以误差（即每个数据点到所在聚类的中心的距离）的平方和作为$k$的函数，画出该函数的图像，并在其“弯曲”的地方寻找合适的取值
  • 由于将$n$个点分配到$k$个聚类的方法非常多，寻找最优聚类方法十分困难，使用迭代算法来寻找好的聚类方法，算法步骤如下
    • 首先从$d$维空间中选出选择$k$个数据点作为初始聚类的均值，即中心
    • 计算每个数据点到这些聚类的均值，即聚类中心的距离，然后把各个数据点分配给离它最近的那个聚类
    • 如果所有数据点都不再被重新分配，那么就停止并保持现有聚类
    • 如果仍有数据点被重新分配，则重新计算均值并返回第2步
• 分层聚类
  • 原理
    • 利用每个输入构成一个聚类，每个聚类只包含一个元素
    • 只要还剩余多个聚类，就找出最接近的2个，并将它们合二为一
    • 重复上一步直至合并成一个巨大的聚类，同时记录全部合并顺序
    • 依据记录下的合并顺序，通过拆分的方法重建任意数量的聚类
  • 合并聚类
    • 最小距离方法，即2个聚类的元素之间的最小距离
    • 最大距离方法，即使用最大距离将2个聚类塞进最小的球中，得到紧凑的球状聚类
  • 合并顺序
    • 使用合并次序踪迹（slot）跟踪合并的顺序
    • 数字越小表示合并的次序越靠后，这意味着可以根据合并次序的值，从最小到最大依次进行
    • 叶（leaf）聚类表示一元组，是聚类的开端且无法拆分，因此，将它们合并次序的值规定为无穷大
• 参考资料
  • scikit-learn库中提供了单独的聚类模块，包括KMeans和Ward分级聚类算法
  • Scipy库也有2个聚类模块，即scipy.cluster.vq（使用k-均值算法）和scipy.cluster.hierarchy（使用多种层级聚类算法）

自然语言处理

自然语言处理（Natural Language Processing，NLP）是指与语言有关的各种计算技术。

词云

• 词云的木包是使单词及其数量可视化，不仅能够以艺术化的形式展示单词，而且还能使单词的大小与其数量呈正比
• 词云的本质是利用很酷的字体把各个单词布置到页面上，比如用坐标传达词的位置
• 词云不是数据科学的重点，但可以利用词云形象地传达一些有价值的信息，比如词的出现频率的高低

n-grams模型

• 获取数据后的预处理
  • 将字符编码替换为自然语言
  • 分词、断句后生成单词序列
  • 清理多余文字以及标题、列表等其他格式
• 2-grams模型
  • 算法
    • 给定某个起始单词（在句点后的单词中随机选择）
    • 找出源文档中所有在它后面出现过的单词
    • 随机选择一个作为下一个单词
    • 然后重复这个过程，直到遇到一个句点为止
  • 该模型之所以称为二元模型（bigram model），因为这完全是由原始数据中2个词（一个词对）同时出现的频率决定
  • 由此产生的句子基本都是些无意义的数据
• 3-grams
  • 该模型之所以称为三元模型（Trigram model），因为第3个词由原始数据中前2个词决定
  • 该模型可降低句子的无意义程度
• n-grams
  • 该模型的第$n$个次由原始数据中的前$n-1$词决定

语法

利用语法规则（grammar）建模生成符合要求的句子。

• 预处理
  • 定义包含特殊标识符的规则名称列表
  • 定义规则与规则的递归关系
  • 定义终端符号
  • 定义句子的停止标识，即当列表元素全部变成终端符号时停止
• 句子生成
  • 如果找到一个非终端符号，那么就在其产物中随机选择一个
  • 如果选中终端符号，直接用它替换相应的标记
  • 如果选中的是一个由空格符分隔的非终端符标记，则进行拆分，并将其拼接到当前标记中
  • 不停重复上述过程直至满足句子的停止标识
• 其他
  • 采用语法规则生成句子，定义了语法规则，因此，不仅可以生成句子，而且可以用来解析句子
  • 更重要的是，还可以理解文本

主题建模

主题建模的目标是从不同的文本中寻找它们共同的主题，隐含狄利克雷分析（Latent Dirichlet Analysis，LDA）技术常用于确定一组文档的共同主题。

• 基本假设
  • 存在固定数目的主题，即$K$个
  • 有一个给每个主题在单词上的概率分布赋值的随机变量，可以把这个分布看作是单词$w$在给定主题$k$中出现的概率
  • 还有另一个随机变量来指出每个文档在主题下的概率分布，可以将这个分布看作是文档$d$中各主题所占比重
  • 文档中各个单词的生成方式为，首先根据文档的主题分布情况随机选择一个主题，然后根据主题下面单词的分布情况随机选择一个单词
• 吉布斯采样
  • 生成主题集合的抽样方法，即当只知道一些条件分布时，通过吉布斯采样技术根据多维分布生成样本
  • 思路
    • 从任意（有效）的$x$和$y$值入手
    • 不断用$y$条件下随机选择的$x$值替换原来的$x$，并用$x$条件下随机选择的$y$值替换原来的$y$
    • 重复一定次数后，得到的$x$值和$y$值就可以作为根据无条件的联合分布获取的样本
• 准备
  • 设定一个文档集合，其中每个文档都是一个单词的列表
  • 设定一个相应的主题集合，以便给每个文档中的每个单词都指定一个主题，但最初设定主题时，主题都是一些数字，需要使用吉布斯取样技术生成主题集合，即用权重最大的单词自行给它们取一个描述性的名称
• 建模步骤
  • 以完全随机的方式给所有文档中的每个单词赋予1个主题
  • 根据该文档中主题的分布情况以及相对于该主题各单词的分布情况，建立相应权重
    • 计算权重需要以下数据准备：每个文档1个计数列表，统计每个文档中每个主题出现的次数；每个主题1个计数列表，统计每个主题中每个单词出现的次数；每个主题1个数字的列表，统计每个主题中单词的总数；每个文档1个数字的列表，统计每个文档中单词总数；1个set，统计不同单词的数量；1个数字，统计文档的数量
    • 上述数据准备为定义条件概率函数做好了准备；例如，统计任意文档中与特定主题相关的单词数量，或者估算任意主题产生1个特定单词的可能性，即将该主题产生该单词的次数除以该主题产生任意单词的次数
    • 这里的每个主题和单词都需要有平滑项，以确保每个主题在任何文档中被选中的几率都不能为0，同时保证每个单词在任何主题中被选中的几率也都不能为0
  • 使用这些权重给这个单词选取新主题
  • 将该过程迭代多次，利用“主题-单词分布”和“文档-主题分布”完成联合取样
  • 自定义几个权重最大的单词，比如5个或4个，自行依据它们为主题取一个描述性的名称
• 参考资料
  • Natural Language Tookit是Python语言一个非常全面的NLP工具库，对其全面描述的书籍《Natural Language Processing with Python》可在线阅读
  • gensim是一个主题建模的库

网络分析

• 网络模型
  • 网络是由各种类型的节点（node）和连接它们的边（edge）构成
  • 边可以是无方向的（undirectd），例如朋友关系；也可以是有方向的（directed），例如超链接
• 中介中心度
  • 中介中心度(betweenness centrality)可以用来找出经常位于其他节点对之间的最短路径中的中介，具体而言，可以通过累加节点$j$和节点$k$之间经过节点$i$的最短路径所占比例，以及节点$j$和$k$之外所有的节点对中相应的比例来求出
  • 广度优先搜索
    • 目标是建立一个以节点为输入的函数，它能够找出达到其他每个节点的所有最短路径
    • 使用节点ID组成的列表表示路径，由于每条路径的第1个节点总是从节点输入，那么可以忽略输入节点的ID，也就是说，代表路径的列表的长度等于该路径本身的长度
    • 维护一个名为“最短路径”的字典，其键为节点ID，其值为以该节点ID结尾的路径构成的列表，如果最短路径唯一，则该列表只包含一个路径，如果有多条最短路径，该列表包含所有这些路径
    • 维护一个名为“待考察节点”的队列（队列是指“在后端进行插入”操作和“在前端进行删除”操作且经过优化的数据结构，在Python中，队列由collections.deque模块实现，实际上是一种双向队列），它们的存放顺序就是相应的考察顺序，即以(prev_node, node)的形式存储，以便了解如何达到每一个节点，这个队列通过输入节点的所有相邻节点进行初始化
    • 在图中进行探索时，每当发现新的邻居节点，只要还不知道通向它们的最短路径，就将它们添加到队尾，以供将来探索，并且以当前节点作为prev_node
    • 当把一个节点从队列中删除时，如果之前从未遇到过该节点，那么肯定是找到了1个或多个通向它的最短路径：沿着达到prev_node的每个最短路径再走一步即是
    • 当从队列中删除一个之前遇到过的节点时，不是找到了另一个最短路径（这种情况应该将其添加到队尾），就是找到了一个更长的路径（这种情况不用将其添加到队尾）
    • 当队列中已经没有节点时，说明已经搜遍了整个图（或者至少也是起始节点所能够达到的部分），这时可以停止
    • 经过搜索，已经知道从$i$到$j$有$n$条最短路径，只要给该路径中的每个节点的中心度加$\frac{1}{n}$即可
  • 由于计算最短路径过于繁琐，中介中心度很少用于大型网络
• 特征向量中心度
  • 其思想是，利用矩阵确定不同节点之间的关系，求解该矩阵的特征向量，那么任意一个节点的特征向量中心度就是该节点对应的矩阵特征向量中的元素
• PageRank
  • 有向性，即(A,B)表示A对B的投票
  • 权重，对于相互投票的节点，得票数较多的节点的投票分量应该重于得票数较少的节点的投票分量
  • 简化版本
    • 网络中PageRank的总分数为1
    • 最初的PageRank被均匀地分布到网络的各个节点中
    • 在每一步中，每个节点的PageRank很大一部分将均匀分布到其外部链接中
    • 在每个步骤中，每个节点的PageRank的其余部分被均匀地分布到所有节点上
• 参考资料
  • 常见的中心度指标见Wikipedia页面
  • NetworkX库用于网络分析，提供了许多函数来帮助计算中心度以及实现图的可视化
  • Gephi是一个基于图形用户界面的网络可视化工具

推荐系统

• 直接推荐流行事物，即对流行事物排序，无论节点输入了什么，都向其推荐一定数量、非重复的流行事物
• 其余用户的协同过滤方法，即利用用户的兴趣找到有类似爱好的人，然后在根据这些人的爱好推荐可能感兴趣的东西
  • 使用余弦相似度（cosine similarity）衡量2个用户之间的相似程度，数值越接近于1表示越相似，越接近于0表示越不相似
  • 当兴趣的数量很大或者处于高维向量空间时，该方法失效
• 基于物品的协同过滤算法，即直接计算2种兴趣之间的相似度，然后将与用户当前兴趣相似的兴趣放在一起，并从中为用户推荐感兴趣的东西
• 参考资料
  • Crab是一个打造推荐系统的Python框架
  • Graphlab提供了一个推荐工具包

数据库

数据库与SQL

• 概念
  • 数据库是用来有效存储和查询数据的系统
  • 数据库类型
    • 关系型（relational）数据库，绝大部分数据库属于关系型数据库，例如Oracle、MySQL与SQL Server，它们将数据存储在表中，并专门通过结构化查询语言（SQL）来查询
    • NoSQL则是非关系型数据库，MongoDB这种无结构数据库的元素是一些复杂的JSON文档，而不是行
    • 还有以列而非行的形式存储数据的列型数据库
  • 关系型数据库是表以及表之间的关系的集合，表是行的简单集合，但表有固定结构，包含列名与列的类型
  • SQL是一种用来处理数据的声明性语言
• 表的操作
  • 创建
  • 插入行
  • 修改或更新，其核心特征是
    • 哪些表需要更新
    • 哪些行需要更新
    • 哪些字段需要更新
    • 新值应该是什么
  • 删除行
  • SELECT查询
    • 子查询，即把查询结果当成表继续执行SELECT或Join操作
  • Group By分组，即将特定列有相同值的行进行分组，并求出特定的汇总值
  • Order By排序
  • Join关联，即将2个或更多的表，以行值为依据进行关联
  • 索引，数据库中每个表都有1个或多个索引，可以通过关键词快速查找行，有效并表以及对行或者行集合施加唯一约束
• 参考资料
  • MySQL和PostgreSQL都是免费的关系型数据库软件，并且有大量文档可参考
  • 非关系型数据库MongoDB也拥有非常友好的文档，Wikipedia上的文章也非常全面

MapReduce

• 概念
  • MapReduce是一个用来在大型数据库上执行并行处理的算法模型
• 意义
  • 假设有数以十亿计的文档要处理，非MapReduce方法要求机器在每一个文档上进行处理，意味着所有的文档要么存在机器上，要么在处理期间转移到机器上，更重要的是，这意味着机器一次只能处理一个文档，如果为多核，一次也只能处理几个文档
  • 如果将这数以十亿计的文档存储到100台，甚至更多的机器上，非MapReduce方法意味着不停地转移、处理、再转移，效率极低
  • 使用MapReduce方法却可以在所有的存储设备上同时完成这些工作
    • 让每一台机器在它的文档上运行map函数，产生大量的键值对
    • 把那些键值对分配到一些“reducing”的机器上，确保对应任何一个给定键的对在同一台机器上完成计算
    • 每一台reducing机器通过键分组这些对，然后对每个值的集合运行reduce函数
    • 返回每个键值对
• 算法步骤
  • 使用map函数把每个项目转换成零个或多个键值对
  • 用相同的键把所有的键值对收集起来
  • 在每一个分好组的值集合上使用reduce函数对每个对应的键生成输出值
• Hadoop
  • Hadoop是使用最为广泛的MapReduce系统，但Hadoop任务是典型的高延迟，不适用于实时分析，一些替代性框架，如Spark和Storm
  • Amazon.com提供Elastic MapReduce服务，仅根据使用该服务的时长收费
  • mrjob是Python的一个Hadoop或Elastic MapReduce接口包

实践提示

• 获取数据
  • 对于csv文件，必须使用二进制模式处理，具体见Stack Overflow的讨论
  • 从HTML中获取数据需要用到以下库
    • BeautifulSoup库
    • requests库
    • 为使用这2个库，可能需要安装第3方解析器html5lib，如需要，使用pip命令安装即可
    • Scrapy是网络抓取方面具有更全特性的库
    • 抓取网页信息时必须了解网站对网页抓取的政策，通常置于robots.txt文件中，必须认真阅读，特别是不允许抓取的项目以及抓取间隔和数量的限制
  • 语料库
    • SpamAssassin垃圾邮件公共语料库是一个关于垃圾邮件的语料库
  • 数据源
    • Data.gov是政府开放数据的门户网站
    • reddit上有r/datasets和r/data两个论坛，是请求数据和发现数据的地方
    • Amazon.com上有一些公用数据集
• 应用程序接口（Application Programming Interface，API）
  • 允许请求结构化数据
  • 通常需要验证，但也有不需要的，例如Github
  • 寻找API
    • 查阅特定网站的开发者部分或API部分，并以python__api搜索相应的库，例如Rotten Tomatoes库，以及针对Klout、Yelp、IMDB等多个API封装
    • 查阅有Python封装的API列，可参阅Python API和Python for Beginners
    • 查阅不一定有Python封装的API名录，可查阅Programmable Web
• HTTP
  • 因为HTTP是一种转换文本协议，通过API请求的数据需要串行化（serialized）地转换为字符串格式，需要使用JavaScript对象符号，即JavaScript Object Notation，JSON），它与字典很相似，通过引入Python的json模块，可以将JSON对象反串行化（deserialized）为Python的对象；如果通过API获取的数据是XML格式，则可以用BeautifulSoup从中获取数据
  • 网页文本中的字符可能使用Unicode等编码形式，在获取HTTP的文本内容后，可能需要对字符编码进行替换，例如，将Unicode字符u“\u2019”替换为正常的单引号
• 日期解析
  • 由于存在多种日期格式，并且Python自身的日期解析器并不强调，需要安装其他包，比如dateutil
• 研究问题的步骤
  • 明确需要研究的问题
  • 获取数据
  • 探索数据（作图、转换数据类型、查看变化）
  • 整理数据（分组或聚类、降维）
  • 建模求解
  • Pandas是Python清理、整理、处理和利用数据的主要工具，Python for Data Analysis是学习Pandas的最好途径