关键词： CS4挑战 MIT-6.0002
0. 前言
这是我CS4挑战计划的第二门课程，Github上显示的commit记录是从11月23日开始，到12月16日完成所有编程练习，前前后后大概花费了不到一个月的时间。中间穿插着MIT18.01课程的学习，所以进度还是可以接受的。6.0002课程是6.0001课程的后续，主要围绕着数据科学这个主题来推进课程，本文就是对MIT 6.0002课程的回顾与总结。
1. 课程介绍
1.1 课程介绍
MIT 6.0002 Introduction to Computational Thinking and Data Science是6.0001课程的后续，适用于编程初学者和编程经验不足者（说得还不是我嘛😭）。这门课程设计的目的同6.0001相似，但引入了更多深入的计算问题，诸如最优化问题、随机化思想和机器学习的入门知识等。同6.0001一样，课程使用的语言是Python3.5，当然大于3.5的Python版本问题应该也不大。
1.2 课程资源
课程的官网在这里。同6.0001一样，课程官网基本提供了课程所需要的所有材料，包括视频、讲义和课程作业。同样，MIT的OpenCourseWare也在油管上传了视频，地址在这里。同样，科学上网是必要的。B站也有up主上传了课程视频，搜索关键词就可以找到。课程用书是这本，书本内容相较于课程视频更充实一些，但没有课程设计的编程练习，所以可以当作辅助参考资料。
同6.0001一样，课程并没有给出编程作业的官方Solution。我自己的Solution在这儿，同样欢迎志同道合的朋友批评指正提issue。
2. 课程总结
2.1 课程概述
本课程进一步地带领学生培养编程的计算思维，其核心思想在于帮助学生在面对实际问题时建立建模的思想来解决问题。从最优化问题入手，通过0-1背包问题引入了贪心算法和动态规划算法，通过图论问题引入了深度优先搜索算法（DFS）和广度优先搜算算法（BFS）。然后着重说明了随机化思想，通过统计学建模对现实世界进行模拟仿真。最后介绍了机器学习的入门知识，包括常规的聚类算法和分类算法。同时，在本课程的课程案例代码中，也进一步介绍了Python的相关高阶语法知识，包括列表推导式、生成器的使用等。可以说，完成了6.0002课程，就算是真正的Python编程入门了。
2.2 课程详述
Lecture1：引入了计算模型里的最优化模型的概念。最优化模型，简而言之就是在一系列条件的限制下，对设定的目标函数求得最大值或最小值的解，这个解也就是问题的最优化模型。然后引入了背包问题来具体说明最优化模型的求解过程。通常背包问题指的是0-1背包问题，0-1背包问题要解决的就是在背包重量一定的情况下，装取物品的总价值最大化。暴力求解0-1背包问题的方案并不可取，因为背包问题本身的时间复杂度就是指数级的。在这讲中，采用贪心算法来求解0-1背包问题，算法明确且效率高，但缺点是贪心算法求得的是局部最优解，并非全局最优解。同时在这讲中，介绍了lambda匿名函数的使用。
Lecture2：介绍了求解最优化问题的动态规划算法。贪心算法虽然能够对最优化问题求解，但求得的解并非总是最优解。由此设计了搜索树（Search Tree）来求解，但搜索树实现的时间复杂度也是指数型，就引入了动态规划算法。利用动态规划算法求解的最优化问题需要满足两个条件：具备最优子结构（Optimal substructure）和具有重叠子问题（Overlapping subproblems）。动态规划算法通过在求解子问题中将结果记录在备忘录（memoization）的方式，用计算空间来换取计算时间。最后通过动态规划算法，对原先的搜索树的实现代码进行改进，程序运行得出结论的速度大大提高。
Lecture3：介绍了最优化问题的图论问题。首先明确了图的概念，图是由多个节点（node）和多条连接两个节点的边（edge）组成的图形。图分为有向图和无向图。然后说明了用Python类构建有向图和无向图的代码。借由几个城市的案例，引入了深度优先搜索算法（Depth First Search）和广度优先搜索算法（Breadth First Search）的介绍，并给出了具体的Python代码的实现。
Lecture4：引入了随机思想和随机游走的概念。从理解概率的三个事实出发，引入仿真模型的概念。使用仿真模型需要注意的是，需要把样本概率和实际概率两个概念区分开。然后借由生日问题，本讲通过具体的Python代码，用仿真模型来模拟生日问题的结果，来给以仿真模型的直观感受。
Lecture5：深入介绍了随机游走的概念。通过醉汉行走这个例子，构建具体的代码来阐述随机游走的效果。需要注意的是，在随机游走的代码构建中，我们应当对结果进行可用性测试（sanity check）。在本讲中，还引入了Python关于画图所涉及的第三方库，诸如NumPy、SciPy和MatPlotLib等。通过Plot函数将之前醉汉行走的结果用图的方式展现出来。
Lecture6：介绍了蒙特卡洛方法（Monto Carlo Simulation）。通过掷硬币的例子来说明置信度（confidence）取决于样本大小（size of sample）和样本方差（variance of sample）。然后引入了大数定律，大数定律指的是在实验条件不变的情况下，重复多次实验，随机事件的频率近似于其概率。借由轮盘赌博的例子，引入置信水平（confidence level）和置信区间（confidence interval）的概念。随机事件发生在某一区间内的概率，这一区间可以理解为置信区间，这一概率可以理解为置信水平。最后引入了经验法则（empirical rule）和概率密度函数（probability density function）的概念，并介绍了正则分布。
Lecture7：深入介绍了置信区间的用途。经验法则的使用有两个预设条件：预估的误差均值为0，预估的误差分布是正态分布。但在轮盘赌博的实验中，每个数字的概率是均等的，不符合经验法则。这里就引入了中心极限定理。中心极限定理包含三个方面：1.不同样本集的样本均值的分布接近于正态分布。2.上述的正态分布的均值接近于总数据的均值。3.样本数据的方差接近于总数据的方差除以总数据的大小。由此，我们由中心极限定理可知，我们可使用经验法则来使用样本数据计算置信区间。随后通过求$\pi$的具体代码来进一步阐述置信区间的用途。
Lecture8：介绍了取样和标准差的概念。先回忆了推论统计的概念，即从总数据中随机抽取单个或多个样本数据，由样本数据推断总数据的相关特性。然后说明了取样的两种分类：简单随机取样（simple random sampling）和分层取样（stratified sampling）。然后借助于美国国家气象局的温度数据，用代码说明了取样的数据特性和总数据的数据特性的差异，并在其中插入了标准差的概念。同时，利用之前的中心极限定理的第三条，当样本数据的规模足够大时，可用样本数据的标准差近似地替代总数据的标准差，最后可用样本的均值标准差作为样本均值的置信区间。
Lecture9：引入了实验数据的概念。通过求解弹簧系数的例子，引入了目标函数（objective function）的概念，再由目标函数引申到最小二乘法（least squares）。在编程中，通过调用pylab库中的pylab.polyfit()函数可求得最小二乘法的最优解。求得的最优解可通过pylab.polyval()函数求得估计的值。pylab.polyfit()函数中有三个参数，分别是observedX, observedY和n。前两个参数是原始数据的横纵坐标，n表示的是所选取的模型的多项式的最高项值。最后引入$R^2$决定系数来判断n值不同模型的好坏。$R^2$系数表明的是所预测的数据对原始数据数据离散程度的拟合程度，$R^2$的范围是0~1，$R^2$值越高，表明模型对数据的拟合效果越好。
Lecture10：进一步阐述实验数据的用途。通过random.gauss()函数人为构建两个数据集，通过对两个数据集的实验表明，由训练数据得到的高$R^2$值的高阶模型在测试数据上不一定表现得最好，由此引入了交叉验证（cross validation）的概念。通过交叉验证的实验，明白了训练得到的复杂模型往往会在测试数据上出现过拟合（overfitting）的现象。要想避免过拟合现象的发生，我们就需要对训练好的模型进行交叉验证实验。常见的交叉验证方法有两种：弃一法交叉验证（leave-one-out cross validation）和重复随机取样法（repeated random sampling cross validation）。最后结合之前的气象数据用代码做进一步的说明。
Lecture11：引入了机器学习的话题。首先说明了机器学习的概念，然后介绍了机器学习的基本套路：训练数据–>得到模型–>测试模型。根据套路类型的不同，机器学习又分为监督学习（supervised learning）和非监督学习（unsupervised learning）。两者的区别在于原始数据集是否有标签（label）。所有的机器学习都有一套方法，本讲中着重介绍了前两个步骤：特征表示（representation of features）和特征向量的距离矩阵（distance metric for feature vectors）。然后通过判断动物是否为爬行动物的代码来阐述这两个话题。同时，也引入了除了准确率（accuracy）评判模型好坏的其它统计方法，包括灵敏度（sensitivity）和特异度（specificity）。灵敏度表示的是数据被正确预测为正类占实际为正类的数据的比例，其计算公式为$$\frac{TP}{TP+FN}$$。特异度表示的是数据被正确预测为负类占实际为负类的数据的比例，其计算公式为$$\frac{TN}{TN+FP}$$。在上述两个公式中，TP表示的是true positive，含义是数据实际为正类，预测的结果也是正类；FN表示的是false negative，含义是数据实际为正类，预测误判为负类。TN表示的是true negative，含义是数据实际为负类，预测的结果也是负类；FP表示的是false negative，含义是数据实际为负类，预测误判为正类。需要注意的是，上述的统计方法都是应用在二元分类法中的。
Lecture12：介绍了聚类算法的实现。聚类算法（clustering）的本质也是最优化问题。本讲介绍了两种最流行的聚类算法：层次聚类算法（hierachical clustering）和k-means聚类算法。层次聚类算法的实现思想是，初始时把每个待聚类的数据看作是一个集群（cluster），每次合并两个距离最近的集群，直到最后合并成一个集群为止。这里的距离的评价方式可以有多种选择。层次聚类算法得出的结果是确定的，但是速度太慢，由此引入k-means聚类算法。k-means算法在之前的博客已经实现过，这里就不再赘述。k-means算法速度很快，但得到的结果是局部最优解，并非全局最优解，而且最终的结果取决于初始点和k值的选择。本讲最后通过心脏病的具体代码实例来说明k-means算法的应用。
Lecture13：介绍了分类算法的实现。首先引入了k最近邻算法（k-nearest neighbors），其思想在于找到与新数据最近的原始数据，并将此原始数据的标签分配给新数据。k最近邻算法的实现非常直接，且不需要对数据进行训练，但算法的时间复杂度太大，我们也没法理解数据的内在规律。由此引入了逻辑回归（logistic regression）的概念。逻辑回归的思想在于为每个数据的特征向量寻找合适的权值（weights），在实际Python代码的编写中，我们通过引入sklearn.linear_model模块来实现逻辑回归模型的训练。本讲在此处的实例代码中引入了列表推导式（list comprehension）的用法，这也在之前的博客做过详细的介绍。最后引入ROC曲线（receiver operating characteristic）和AUC值（area under roc curve）来度量我们所训练出的模型的好坏。
Lecture14：对机器学习中使用统计学可能出现的一些坑进行总结。对数据的统计学判断并不意味着数据本身，由此常常对数据进行绘图等直观表达的方式来识别数据的内在规律。在用图表示数据时，要清楚图的横纵坐标所表示的具体内容以及它们取值范围。没有价值的数据往往导致不可靠的结论。在数据收集的过程中，我们应该知晓数据收集的方式，由此来判断我们采用的方法是否满足相应的假设条件。
Lecture15：继续对统计学在机器学习应用中可能出现的坑进行总结。可以通过截断Y轴的值来去除数据的不变性，凸显数据的变化性。在探讨实际问题的趋势（trend）倾向时，要注意所选X轴区间的合理性，以及区别波动（fluctuation）和趋势走向的区别。同时，在观察百分率变化时，需要了解分母的具体含义。然后以癌症集群为案例，说明在选取数据得出结论是要避免选择性偏向有利方（cherry picking）的陷阱。所有所有的一切，要对从数据中得到的结论保持怀疑（skepticism）。
2.3 编程练习
Assignment1：通过外星人运输奶牛和鸡蛋的情景设计，动手实现了利用with open加载文件数据，并自己动手实现了贪心算法、暴力破解算法以及动态规划算法。我在实际的编程过程中，对动态规划算法中的备忘录（memoization）的构建和使用有了非常直接的体验和感受。可以说，动态规划算法的精髓在于如何恰当的找到计算过程中子问题的最优值并将其保存在记录表中。
Assignment2：通过找寻MIT两栋建筑的最短距离的情景，来动手实现图论中的相关最优化问题，也就是实现深度优先算法。首先要在理解图的基本构成的基础下，实现图的数据结构的代码。同练习1一样，也要完成加载地图数据的代码实现。最后通过构建相应的递归函数，来实现利用深度优先算法，求出MIT两栋建筑之间在满足不超过设定的室外行走距离的条件下的最短路径。
Assignment3：通过模拟扫地机器人的扫地行为，来动手实现随机化思想和仿真思想。首先是完成相应的类的实现，在此过程中我对接口和类的差别有了一定的认识。在类的实现的过程中，也运用到了类的初始化和类的继承等知识。同时，因为在代码中需要用到随机量，所以也了解了Python的random模块。练习比较了问题机器人和正常机器人的运行情况，这里在结合课程仿真实验知识的同时，也运用到了Python的相关绘图知识。
Assignment4：通过模拟细菌繁殖和疾病传播速度的情景，来动手实现并验证课程中关于置信区间等统计学知识。同样，练习要求动手实现相关的类。我对此练习的理解不在于代码层面上的锻炼，我认为此练习通过比较无抗生素治疗和有抗生素治疗两种情境下细菌总量数目的变化，锻炼我由图表来得出相关统计学的结论的能力。
Assignment5：通过对气温数据的建模，来动手实现探索全球气候是否变暖的问题（开头还黑了一把特朗普😄）。同课程案例代码一样，我通过调用pylab.polyfit()函数来生成模型，然后动手实现$R^2$系数和模型可视化。练习处理的数据也由一个城市某一天的气温，再到一个城市一年的平均气温，再到21个城市一年的平均气温，再到21个城市循环五年的平均气温，每组数据都对应生成一组模型，再由这各组模型预测未来的气温数据，最后动手实现了对极端天气的建模，然后由生成的各组图像得出相应的结论及改进方法。
3. 课程评价
真心地感受到了MIT作为北美计算机专业牛逼学校的教学质量。每个课程视频可以说把PPT上的内容都讲得非常透彻，每个课程练习又与课程内容紧紧联系。可以说，这门课程的学习，让我消除了对数据结构和面向对象思想相关概念的恐惧，而且更重要的是，让我觉得，通过编程解决未知的问题，可真是酷毙了:)。
课程评价：😀😀😀😀😀
课程作业：😀😀😀😀😀
自我评价：😀😀😀😀
最后献上一张Prof Guttag弯弓射大雕的搞笑截图😄
