【统计数据挖掘 经典教程 PPT版式】卡耐基梅隆大学计算机学院院长 Andrew W. Moore30余基础教程，包括概率基础、统计数据分析基础以及大多数经典机器学习和数据挖掘算法

作者

Andrew W. Moore是卡耐基梅隆大学计算机科学学院的院长。研究方向是统计机器学习、人工智能、机器人技术和大量数据的统计计算。曾在机器人控制、制造、强化学习、天体物理学算法、恐怖威胁检测和监视算法、互联网广告、互联网点击率预测、电子商务和当日送达物流等领域工作。热衷于技术（算法、云架构、统计学、机器人技术、语言技术、机器学习、计算生物学、人工智能和软件开发过程）对社会未来的影响。

个人主页 http://www.cs.cmu.edu/~awm/index.html

教程介绍

本教程包括一组关于统计数据挖掘许多方面的教程：包括分类算法，例如决策树、神经网络、贝叶斯分类器、支持向量机和基于案例的（也称为非参数）学习。包括回归算法，例如多元多项式回归、MARS、局部加权回归、GMDH 和神经网络。包括其他数据挖掘操​​作，例如聚类（混合模型、k-means 和分层）、贝叶斯网络和强化学习。

• 决策树。决策树是目前在数据挖掘和机器学习中最流行的分类算法之一。本教程可作为数据挖掘的风味和术语的独立介绍，而不需要回顾许多统计或概率的先决条件。如果你是数据挖掘的新手，你会喜欢它，但你的眉毛会因为这一切是如此简单而竖起来 在定义了分类的工作之后，我们解释了如何利用信息增益（接下来是安德鲁教程）来寻找预测性输入属性。我们展示了如何递归地应用这个程序，使我们能够建立一个决策树来预测未来的事件。然后，我们仔细研究了一个非常基本的问题，它是所有统计学和机器学习理论的基础：你如何在一个非常适合数据的复杂模型和一个简洁但不太适合数据的 "奥卡姆剃刀 "模型之间做出选择（这个话题将在以后的安德鲁讲座中重新讨论，包括 "交叉验证 "和 "VC-维度"）。我们还讨论了对基本决策树想法进行改进和调整的非常广泛的世界。

• 信息增益。本教程通过信息论的思想，最终导致了信息增益......目前在数据挖掘中使用的最流行的关联度量之一。我们沿途参观了熵和条件熵的概念。关于连续概率密度函数情况下的熵的讨论，请看高斯的讲座。

• 数据挖掘者的概率。本教程从基础开始回顾概率论。可以说，在涉足数据挖掘、机器学习或应用统计的高级算法之前，对概率论完全满意是一项有益的投资。除了为在其余教程中反复使用的技术奠定基础外，本教程还介绍了密度估计这一重要操作的概念，然后介绍了贝叶斯分类器，如容易发生过度拟合的联合密度贝叶斯分类器，以及抗过度拟合的奈何贝叶斯分类器。

• 概率密度函数。回顾一下你以前可能遇到过的世界：实值随机变量、概率密度函数，以及如何处理多变量（即高维）概率密度的问题。在这里，你可以回顾一下诸如期望值、协方差矩阵、独立性、边际分布和条件分布等内容。一旦你对这些东西感到满意，你将不会成为一个数据挖掘者，但你将拥有很快成为一个数据挖掘者的工具。

• 高斯（Gaussians）。高斯，无论是友好的单变量类型，还是稍显迟钝但当你了解它们时却又不太在意的多变量类型，在统计数据挖掘的许多方面都非常有用，包括许多数据挖掘模型，其中的基础数据假设是高度非高斯的。你需要成为多变量高斯的朋友。

• 最大似然估计。MLE是学习数据挖掘模型参数的可靠工具。它是一种方法，试图做两件事。首先，它是一种合理的原则性方法，当你想从数据中学习某些类型的模型时，你应该做什么计算。第二，它通常在计算上是相当可行的。在任何情况下，重要的是，为了理解像多项式回归、神经网络、混合模型、隐马尔科夫模型和其他许多东西，如果你对MLE感到满意，那将会非常有帮助。

• 高斯贝叶斯分类器。一旦你成为高斯的朋友，就很容易将它们作为贝叶斯分类器的子组件使用。本教程告诉你如何使用。

• 交叉验证。交叉验证是估算你刚从一些训练数据中学到的模型在未来尚未看到的数据上的表现如何的几种方法之一。我们将回顾测试集验证、留出交叉验证（LOOCV）和k-fold交叉验证，我们将讨论这些技术可以使用的各种地方。我们还将讨论过度拟合......CV应该呈现的可怕现象。最后，我们的头发会竖起来，因为我们意识到，即使使用CV，你仍然可以任意地严重过拟合。

• 神经网络。我们首先讨论了线性回归......神经网络的祖先。我们看看线性回归是如何使用简单的矩阵运算来学习数据的。当我们看到为什么一个最初的假设不可避免地导致了尝试最小化平方误差的决定时，我们会高兴地流口水。然后我们探索另一种计算线性参数的方法--梯度下降。然后，我们利用梯度下降来允许分类器和回归器，最后允许高度非线性模型--完整的神经网络的所有荣耀。

• 基于实例的学习（又称基于案例或基于记忆或非参数）。这种形式的数据挖掘已经有一个多世纪的历史了，现在仍然被统计学家和机器学习者们大量使用。我们探讨了近邻学习、K-近邻、核方法和局部加权多项式回归。本教程中的算法的软件和数据可从http://www.cs.cmu.edu/~awm/vizier 。本幻灯片中的示例图是用相同的软件和数据创建的。

• 八种回归算法。你得等着看安德鲁对它们的排序，但根据你到目前为止所学的所有基础，我们很快就能跑完。回归树、级联相关、分组方法数据处理（GMDH）、多变量自适应回归样条曲线（MARS）、多线性插值、径向基函数、稳健回归、级联相关+投影追求

• 预测实值输出。回归的介绍。本讲座完全由神经网络讲座开始时的材料和 "最喜欢的回归算法 "讲座中的一个子集组成。我们先谈线性回归，然后再谈这些主题。变化的噪声、非线性回归（非常简短）、多项式回归、径向基函数、稳健回归、回归树、多线性插值和MARS。

• 贝叶斯网络。该教程首先回顾了概率的基本原理（但要正确地做到这一点，请参见早期的Andrew关于数据挖掘概率的讲座）。然后，它讨论了使用联合分布来表示和推理不确定的知识。在讨论了联合分布作为一般工具的明显缺点（维度的诅咒）之后，我们参观了涉及独立性和条件独立性的巧妙技巧的世界，这些技巧使我们能够更简洁地表达我们的不确定知识。然后我们欣喜地发现，我们已经掌握了理解和欣赏贝叶斯网络所需的大部分知识。本教程的其余部分介绍了如何用贝叶斯网络进行推理这一重要问题（也请参见下一个安德鲁讲座）。

• 贝叶斯网络的推理（作者：Scott Davies和Andrew Moore）。这些幻灯片大部分是由Scott Davies构思和制作的。一旦你掌握了贝叶斯网络，剩下的问题就是你如何用它进行推理。推理是一种操作，其中一些属性的子集以已知的值提供给我们，而我们必须使用贝叶斯网络来估计一个或多个剩余属性的概率分布。推理的一个典型用法是："我的体温是101，我是一个37岁的男性，我的舌头感觉有点怪，但我没有头痛。我得鼠疫的可能性有多大？"。

• 学习贝叶斯网络。这个简短的教程概述了从数据中学习贝叶斯网络的问题，以及所使用的方法。这是一个由许多研究小组积极研究的领域，包括安德鲁和他的学生（更多细节见Auton实验室网站）。

• 朴素贝叶斯分类器的简短介绍。我建议使用Probability For Data Mining来更深入地介绍密度估计和贝叶斯分类器的一般使用，天真贝叶斯分类器是一个特殊的案例。但是，如果你只是想了解在分类属性上学习和使用天真贝叶斯分类器的执行摘要底线，那么这些幻灯片就很适合你。

• 贝叶斯网的简短概述。这是对贝叶斯网络背后的直觉和洞察力的一个非常简短的5分钟 "执行概述"。阅读完整的贝叶斯网络教程以获得更多信息。

• 高斯混合模型。高斯混合模型（GMMs）是统计学上最成熟的聚类方法之一（尽管它们也被大量用于密度估计）。在本教程中，我们将介绍聚类的概念，并看看聚类的一种形式......在这种形式中，我们假设单个数据点是通过首先从一组多元高斯中选择一个，然后从中取样产生的......可以是一种定义明确的计算操作。然后我们看看如何从数据中学习这样的东西，我们发现以前的《安德鲁教程》中没有使用过的一种优化方法在这里有很大的帮助。这种优化方法被称为期望最大化（EM）。我们将花一些时间对EM做一些高水平的解释和演示，事实证明它对高斯混合模型以外的许多其他算法都很有价值（我们将在后面的《安德鲁教程》中再次见到EM，即隐马尔可夫模型）。文中提到的疯狂的代数可以在这里找到（手写的）。

• K-means和分层聚类。K-means是最著名的聚类算法。在本教程中，我们回顾了聚类所要达到的目的，并展示了K-means方法正在巧妙地优化一些非常有意义的东西的详细原因。哦，对了，我们还将告诉你（并向你展示）K-means算法的实际作用。你还会了解到另一类著名的聚类方法：分层方法（在生命科学领域备受喜爱）。像 "分层聚合聚类 "和 "单一联系聚类 "这样的短语将被广泛使用。

• 隐马尔可夫模型。在本教程中，我们将首先回顾马尔可夫模型（又称马尔可夫链），然后......我们将把它们隐藏起来！这是很常见的现象。这模拟了一个非常常见的现象......有一些潜在的动态系统按照简单和不确定的动力学运行，但我们看不到它。我们所能看到的是一些来自底层系统的嘈杂信号。从这些嘈杂的观察中，我们想做的事情是预测最可能的底层系统状态，或状态的时间历史，或下一次观察的可能性。这在故障诊断、机器人定位、计算生物学、语音理解和许多其他领域都有应用。在本教程中，我们将描述如何愉快地玩弄围绕着HMM的大部分无害的数学，以及如何使用一种令人心动的、简单易行的、称为动态编程（DP）的方法来有效地完成你可能想要做的大部分HMM计算。这些操作包括状态估计，估计基础状态的最可能路径，以及作为一个盛大的（和充满EM的）压轴戏，从数据中学习HMMs。

• VC维度。本教程涉及机器学习理论的一个著名部分。如果你一手拿着学习算法，一手拿着数据集，你能在多大程度上决定学习算法是否有过拟合或欠拟合的危险？如果你想对过拟合如何发生这个迷人的问题进行一些正式的分析，那么这就是为你准备的教程。除了对过拟合现象有很好的理解外，你还会得到一种估计算法在未来数据上表现如何的方法，这种方法完全基于其训练集误差和学习算法的一个属性（VC维度）。因此，VC维度给出了一个替代交叉验证的方法，称为结构风险最小化（SRM），用于选择分类器。我们将讨论这个问题。我们还将非常简要地将CV和SRM与其他两种模型选择方法进行比较。AIC和BIC。

• 支持向量机。我们回顾一下分类器的边际概念，以及为什么这可能是衡量一个分类器可取性的好标准。然后我们考虑寻找最大边际线性分类器的计算问题。在这一点上，我们尴尬地看着自己的脚趾，并指出我们只做了适用于无噪声数据的工作。但我们振作起来，展示了如何创建一个抗噪分类器，然后是一个非线性分类器。然后，我们在显微镜下观察了SVM的两个著名之处--将数据投射到一万亿维度的计算能力，以及在乍看之下像是典型的过拟合陷阱的统计能力。

• PAC学习。PAC是 "大概正确 "的意思，它是一个很好的形式主义，用于决定你需要收集多少数据，以便让一个给定的分类器在未来的测试数据中达到一定的正确预测概率。由此产生的估计有些保守，但仍然代表了一种有趣的途径，计算机科学试图通过这种途径来加强对这种分析性的预测。

• 马尔科夫决策过程。如果你的行动的结果是不确定的，你如何有效地计划？有一些非常好的消息，以及一些重大的计算困难。我们首先讨论了马尔科夫系统（没有行动）和有奖励的马尔科夫系统的概念。然后，我们激励并解释了无限地平线贴现的未来奖励的概念。然后，我们看一下处理以下计算问题的两种相互竞争的方法：给定一个有奖励的马尔科夫系统，计算预期的长期折现奖励。这两种方法，通常坐在环形的两个角落，相互咆哮，是直接线性代数和动态编程。然后我们跃升到马尔科夫决策过程，发现我们已经完成了82%的工作，不仅计算了每个MDP状态的长期回报，还计算了每个状态下的最佳行动。

  • 除了这些幻灯片之外，关于强化学习的调查，请看这篇论文或萨顿和巴托的书。
  • Rohit Kelkar和Vivek Mehta的马尔科夫决策过程和强化学习算法的可视化模拟。

• 强化学习。在涉足强化学习之前，你需要对马尔科夫决策过程（之前的安德鲁教程）感到满意。它涉及到一个迷人的问题，即你是否可以训练一个控制器在一个可能需要吸收一些短期惩罚以实现长期回报的世界中发挥最佳作用。我们将讨论确定性等价的RL，时差（TD）学习，以及最后的Q-learning。维度的诅咒将不断地在我们的肩膀上学习，垂涎欲滴，咯咯作响。

  • 除了这些幻灯片之外，关于强化学习的调查，请看这篇论文或Sutton和Barto的书。
  • Rohit Kelkar和Vivek Mehta的马尔可夫决策过程和强化学习算法的视觉模拟。

• 生物监视。一个例子。我们回顾了其他生物监测幻灯片中描述的方法，这些方法被应用于2000年Walkerton隐孢子虫爆发的入院数据中。这是作为ECADS项目的一部分进行的工作。

• 基本概率和朴素贝叶斯分类器。这张幻灯片重复了安德鲁教程系列中主要的概率幻灯片的大部分材料，但这套幻灯片侧重于疾病监测的例子，并包括一个非常详细的描述，供非专业人士了解贝叶斯规则如何在实践中使用，关于贝叶斯分类器，以及如何从数据中学习朴素贝叶斯分类器。

• 空间监控。本教程讨论了扫描统计，这是一种著名的流行病学方法，用于发现疾病病例的过度密集性。 时间序列方法。本教程回顾了一些基本的单变量时间序列方法，重点是当一连串的观察值开始表现得很奇怪时，利用时间序列来发出警告。

• 博弈树搜索算法，包括Alpha-Beta搜索。介绍计算机博弈的算法。我们描述了关于完全信息的双人零和离散有限决定性博弈的假设。我们还练习一口气说出那个名词短语。在恢复小组完成工作后，我们谈论用最小化和然后阿尔法-贝塔搜索来解决这种博弈。我们还讨论了动态规划方法，它最常用于终结博弈。我们还辩论了博弈中启发式评价函数的理论和实践。

• 零和博弈论。想知道在扑克中如何以及为什么要诈骗吗？博弈如何能被编译成矩阵形式？想了解隐藏信息博弈的基础知识吗？那么这些幻灯片就是为你准备的。从阅读关于博弈树搜索的幻灯片开始，可能对你有所帮助。

• 非零和博弈论。拍卖和电子谈判是一个迷人的话题。这些幻灯片带你了解非零和博弈理论背后的假设、形式主义和数学的大部分基本故事。从阅读关于博弈树搜索和零和博弈论的幻灯片开始，也许会对你有所帮助，因为这套教程中的隐藏信息也是可用的。在本教程中，我们涵盖了多人非零和博弈的定义、策略的支配性、纳什均衡。我们处理离散博弈，也处理策略包括实数的博弈，如你在双人拍卖谈判中的出价。我们涵盖囚徒困境、公地悲剧、双重拍卖和多人拍卖，如第一价格密封拍卖和第二价格拍卖。双重拍卖分析的数学知识可以在http://www.cs.cmu.edu/~awm/double_auction_math.pdf 找到。

• 基于时间序列的异常检测算法的介绍性概述。这个简单的教程概述了在生物监测时间序列中检测异常的一些方法。幻灯片是不完整的：演讲中的口头评论还没有作为解释性文本框包括在内。如果你对这些幻灯片的更多细节和/或访问实现各种单变量方法并绘制图表的软件感兴趣，请让我（ awm@cs.cmu.edu ）知道。如果我收到足够多的请求，我将尝试提供上述两项服务。

• AI课介绍。关于不同种类的人工智能研究动机的一个非常快速的非正式讨论。

• 搜索算法。什么是搜索算法？它做什么工作，在哪里可以应用？我们介绍各种类型的广度优先搜索和深度优先搜索，然后看看替代方案和改进，包括迭代深化和双向搜索。然后，我们皱着眉头看一个叫做最佳优先搜索的想法。这将是我们对一种能够利用启发式功能的搜索算法的第一次看法。

• A-star启发式搜索。给定一个可接受的启发式算法，寻找最短路径的经典算法。我们将处理可接受性的概念（总结：可接受=乐观）。我们将展示如何证明A-star的属性。我们还将简要地讨论IDA（迭代深化A-star）。

• 约束满足算法，在计算机视觉和调度中的应用。该教程讲授人工智能文献中关于约束满足的概念。随之而来的动画在 http://www.cs.cmu.edu/~awm/animations/constraint 。这是无信息搜索的一个特例，我们想为某些变量集找到一个满足一组约束条件的解决方案配置。例子问题包括图形着色、8-queens、魔方、解释线图的Waltz算法、许多种调度以及最重要的扫雷的推理阶段。我们将研究的算法包括回溯搜索、前向检查搜索和约束传播搜索。我们还将研究用于额外搜索加速的通用启发式算法。

• 机器人运动规划。我们将回顾一些算法，以便在我们到达实值连续空间，而不是到目前为止我们一直躲在的安全和温暖的离散空间时，进行巧妙的路径规划。我们研究了配置空间、可见性图、单元分解、基于Voronoi的规划和势场方法。不幸的是，PDF版本中缺少一些数字。

• 爬山算法、模拟退火法和遗传算法。一些非常有用的算法，只在紧急情况下使用。