此外，我们还讨论了人工智能、机器学习和深度学习之间的关系。机器学习作为人工智能的一个子领域出现，深度学习是机器学习的一个子领域。深度学习特别关注多层神经网络并超越它们。深度学习可以被认为是神经网络的品牌重塑。人工智能系统是通过规则展现智能的非生物系统，例如自动驾驶汽车或下棋程序。机器学习不是 AI 的必要条件，因为可以在不使用机器学习技术的情况下开发 AI 系统。
当使用 k 大于 1 的 k 最近邻方法时，决策边界变得更平滑。当我们考虑更多的相邻点时，单个训练数据点的影响会减弱，从而产生更广义的边界。决策边界由 k 个最近邻居的多数投票决定，从而导致类之间更平滑和更连续的分离。
理解决策边界的概念对于评估 k 最近邻算法的性能和局限性至关重要。决策边界的形状和复杂性会影响算法准确分类或预测新数据点的能力。
除了讨论 k 最近邻算法，我们还会涉及到算法效率这个话题。大 O 表示法是分析和比较不同算法效率的常用方法。它提供了算法时间复杂度的度量，指示执行时间如何随着输入大小的增加而增加。
分析 k 最近邻算法的运行时复杂度有助于我们了解其计算效率。我们将简要探讨该主题并讨论算法的效率如何影响其在大型数据集上的性能。
在本讲座的最后，我们将深入探讨使用 Python 实现 k 最近邻算法的实际示例。我们将演示如何使用该算法进行分类和回归任务，展示其在现实场景中的应用。然而，在开始实施之前，必须掌握 k 最近邻的基本概念和原则。
回顾一下，在第二讲中，我们将一个最近邻方法作为最近邻算法的一个简单案例进行了介绍。我们探讨了该算法如何确定最接近查询点的数据点，以及它如何使用最近点的标签进行预测。我们还在最近邻方法中介绍了决策边界的概念及其形状。此外，我们还讨论了 k 最近邻算法，该算法考虑多个最近邻而不是一个。我们提到了预测标签是如何通过分类问题中的多数表决和回归问题中的平均值或中值来确定的。此外，我们简要介绍了大 O 表示法及其在分析算法效率方面的应用，包括 k 最近邻算法。
在下一讲，也就是第 3 讲中，我们将深入研究使用 Python 实现 k 最近邻算法。我们将介绍有效利用该算法的必要步骤、库和技术。所以，一定要和我一起参加下一堂课！
该数据集由五个用蓝点表示的数据点组成。让我们放大点 A 和 B 并探索它们之间的决策边界。决策边界是分隔点 A 和 B 的一条线或边界。如果我们将一个最近邻模型拟合到数据集，这个决策边界会是什么样子？
要回答这个问题，我们需要了解等距离的概念。位于决策边界上的任何点都应与点 A 和 B 等距。花点时间暂停视频，想一想决策边界会是什么样子。点 A 和 B 的决策边界将是使用欧氏距离度量绘制的一条线。这条直线上的任何一点到A点和B点的距离都相等，这意味着直线上的点与A点和B点之间的距离在直线上的任何地方都相同。现在让我们转到点 A 和 C 并确定它们的决策边界。点 A 和 C 的决策边界将是一条垂直于连接 A 和 C 的线的线。这条线上的每个点都与点 A 和 C 等距。
我们可以对数据集中的所有点对（例如 C 和 D）继续这个练习，以确定它们各自的决策边界。通过为每对点组装所有这些决策边界，我们获得了一个最近邻分类器的决策边界，如右下角所示。
k 值的选择是 k 最近邻算法中的一个重要考虑因素。较小的 k 值可能会导致过度拟合，即算法对数据的局部波动过于敏感。另一方面，较大的 k 值可能会导致欠拟合，此时决策边界变得过于平滑，无法捕获更精细的细节。与任何算法一样，需要权衡取舍，k 的选择取决于数据集和手头的问题。试验不同的 k 值并使用交叉验证等技术来找到最佳值是很常见的。
k近邻算法通过考虑k个最近点扩展了一个最近邻算法。决策边界由基于 k 个最近邻居的类标签的投票机制确定。 k的选择是一个超参数，需要仔细选择以平衡过拟合和欠拟合。
在上一个视频中，我提到并非前面讨论的所有距离度量都是指标。例如，余弦相似度不被认为是合适的度量，因为它不满足三角不等式。三角不等式指出两个数据点之间的距离，表示为 A 和 C，应该小于或等于 A 和 B 以及 B 和 C 之间的距离之和。然而，尽管不是一个合适的度量，余弦在特定情况下，相似性在实践中仍然非常有用。
现在，让我们深入研究 k 最近邻 (k-NN) 方法，它是我们之前讨论的最近邻方法的扩展。 k-NN 模型相对简单，因为它通过考虑多个最近邻居而不是一个最近邻居来推广一个最近邻居方法。
使用贪心交叉验证快速识别最佳机器学习模型
使用贪心交叉验证快速识别最佳机器学习模型
大家好。我是 Soper 博士，今天我想讨论一种我一直在开发的技术，称为“贪心交叉验证”。该技术是有效识别最佳或接近最佳机器学习模型的基础。
让我们从简要介绍和解释为什么这个问题非常重要开始。在开发机器学习解决方案时，通常会测试各种模型以确定哪个模型表现最好。在这里，术语“模型”指的是机器学习算法及其可调参数的选定值的特定组合。
在确定分析或数据科学项目的最终选择之前，机器学习从业者经常面临测试数百甚至数千个模型的挑战。此过程可能非常耗时、计算量大且成本高。一些高级机器学习模型需要数小时甚至数天的时间来训练。
鉴于测试大量模型的资源密集型性质，研究人员已设法尽快确定性能最佳的模型。现有方法包括贝叶斯方法、梯度下降方法、进化方法和基于人群的训练等。这些方法通常旨在识别模型参数和性能指标之间的关系，使他们能够探索搜索空间的有希望的区域。
与现有方法相比，贪婪交叉验证采用一种独特的方法来加快识别最佳性能模型。 Greedy Cross Validation 不是专注于在搜索空间中寻找有希望的区域，而是围绕测量模型性能本身作为快速识别最佳机器学习模型的基础。
模型包括结构参数和算法参数，统称为超参数。结构参数包括神经网络中隐藏层或节点的数量等因素，而算法参数控制学习过程，例如小批量大小或学习率。为特定机器学习问题寻找超参数设置的最佳组合的任务称为超参数优化。
为了掌握贪心交叉验证的概念，让我们考虑一个通过超参数优化搜索最优模型的简单示例。在这种情况下，我们有两个超参数表示在水平轴和垂直轴上。每个橙色方块代表一个特定模型及其超参数值的独特组合。评估每个模型的性能使我们能够确定最佳模型，为此目的的一种常用方法称为“网格搜索”。
现在，我们如何评估模型在现实世界中的表现？最常见的解决方案是使用训练期间未遇到的数据来测试每个模型，这一过程称为“k 折交叉验证”。它是这样工作的：
然后将模型的整体性能计算为从每次折叠评估中获得的性能值的平均值。这确保了对模型性能的可靠估计。
现在我们了解了标准交叉验证的工作原理，我们可以探索它在整个超参数优化过程中的作用。在使用标准交叉验证评估多个候选模型时，特定模型的每次折叠都会更新我们对其性能的估计。一旦我们评估了模型的所有折叠，我们就获得了对其整体性能的最终估计。通过对所有模型重复此过程，我们可以确定最佳候选者。
相比之下，贪心交叉验证采用不同的方法。它不是按顺序评估每个模型的所有折叠，而是迭代评估不同模型的折叠。根据每个候选模型的当前平均性能动态选择接下来要评估的特定折叠。最初，为每个模型评估一次折叠，然后根据迄今为止评估的模型的性能选择后续折叠。
贪婪交叉验证背后的关键思想是优先评估早期显示出前景的模型。通过这样做，我们可以快速识别可能表现良好的模型并为它们分配更多的计算资源。这种方法消除了为每个模型评估所有折叠的需要，从而节省了大量时间和计算资源。
要实现贪心交叉验证，我们遵循以下步骤：
通过根据模型的当前平均性能动态选择下一个折叠进行评估，Greedy Cross Validation 可以快速识别性能最佳的模型。这种方法使我们能够将计算资源集中在最有前途的模型上，而忽略不太可能表现良好的模型。
Greedy Cross Validation 的优势之一是它能够有效地处理大量候选模型。 Greedy Cross Validation 不是在所有折叠上详尽地评估所有模型，而是根据模型的性能自适应地确定优先级和评估模型，从而显着降低总体计算要求。
重要的是要注意，贪心交叉验证并不是找到绝对最佳模型的保证方法。与其他超参数优化技术一样，它依赖于启发式方法，可能并不总能确定全局最优值。但是，它提供了一种实用且有效的方法来快速识别高性能模型，尤其是在处理大量候选模型时。
贪心交叉验证是一种在机器学习中加速超参数优化的技术。通过根据性能自适应地选择和评估模型，它可以有效地识别性能最佳的模型。虽然它可能不能保证找到绝对最佳的模型，但它提供了一种实用的解决方案，可以有效地导航超参数搜索空间。
1.1 课程概览（L01：什么是机器学习）
1.1 课程概览（L01：什么是机器学习）
大家好！
欢迎回到新学期。我希望你们都度过了一个愉快的暑假。在这段视频中，我想花点时间回顾一下课程材料并讨论我们将如何在这门课程中一起工作，因为它与通常的面对面课程有点不同。
对于这门课程，我的计划是异步录制讲座。这意味着我将预先录制讲座并在每周初与您分享。这样，您就可以在方便的时候观看最适合您的材料。这种方法允许您在需要时灵活地多次观看视频。此外，如果您的互联网连接速度较慢，您可以将视频下载到您的计算机上，以避免在观看时出现流媒体问题。
为了更轻松地浏览讲座，我将根据不同的主题将每个讲座分成多个视频。例如，在第 1 讲中，我将有单独的视频讨论课程的一般性、机器学习介绍、机器学习类别、符号和机器学习应用程序。此细分将帮助您专注于特定主题并轻松查看内容。
虽然异步学习有它的优点，但我明白它也有它的缺点，比如不能在讲座中提问。为了解决这个问题，我将主持现场办公时间，我们可以在其中进行实时讨论。我将很快提供有关办公时间的更多详细信息。
现在，让我们开始第 1 讲。在本讲中，我们将介绍课程概述、教学大纲以及我们将在整个学期涵盖的主题。我将浏览我的幻灯片并提供有关课程和其他机器学习相关主题的更多详细信息。
说到课程内容，我把这个学期分为七个部分或模块。这个部门将帮助我们构建我们的学习之旅。在第一部分中，我们将从机器学习的介绍开始，我将在其中解释基本概念并提供一个称为 K 最近邻的机器学习算法的简单示例。
介绍之后，我们将继续介绍计算基础，其中包括对 Python 及其与机器学习的相关性的简要介绍。虽然之前使用 Python 的经验不是强制性的，但有基本的了解将是有益的，因为我们将在本课程中广泛使用 Python。我们将专注于特定的库，例如用于线性代数的 NumPy 和主要的机器学习库 scikit-learn。
在接下来的部分中，我们将介绍基于树的方法、模型评估、降维、无监督学习和贝叶斯学习。这些主题对于理解各种机器学习算法及其应用至关重要。如果时间允许，我们将深入研究贝叶斯学习，其中包括基于贝叶斯定理的方法。
在学期末，我们将进行课堂项目展示。随着学期的进展，我将提供更多关于班级项目的信息。
有关每个讲座及其内容的详细信息，我在 Canvas 上创建了一个课程网站。您将在此平台上找到所有资源，包括讲座视频、幻灯片、讲义和作业。我建议在观看视频之前下载幻灯片，以便您可以做笔记并更有效地参与材料。
随着课程的进行，我将每周在 Canvas 上发布模块，您可以在其中访问讲座、幻灯片和其他相关资源。此外，我会在 Canvas 上发布公告，让您了解与课程相关的任何更新或重要信息。请确保您已启用公告通知，我鼓励您定期查看电子邮件以了解最新信息。
所以我可能不得不重新上传视频并检查它们是否正确加载。对于给您带来的不便，我深表歉意，感谢您在我们解决这些技术问题时的耐心等待。
除了讲座视频，我还会在 GitHub 上提供代码示例和家庭作业等补充材料。您将在 Canvas 上相应周的模块中找到这些资源的链接。 GitHub 在机器学习社区中广泛用于共享代码和项目协作，因此熟悉该平台将对您有所帮助。
我想强调定期查看 Canvas 上的公告的重要性。虽然我会发送重要更新的电子邮件通知，但必须启用公告通知以确保您收到所有信息。我将使用 Canvas 公告功能来传达与课程相关的任何更改、提醒或其他资源。
现在，让我们更详细地讨论课程结构。如前所述，本学期分为七个部分或模块，每个部分涵盖与机器学习相关的特定主题。这些模块旨在提供渐进式学习体验，以以前的概念为基础并引入新概念。
在第一部分中，我们将从机器学习的介绍开始，我将在其中解释该领域的基础知识并提供一个名为 K 最近邻的机器学习算法的简单示例。这将使您了解机器学习的工作原理，并为即将到来的模块奠定基础。
第二部分侧重于计算基础，我们将涵盖基本的 Python 编程和机器学习中使用的基本库，例如用于线性代数的 NumPy 和用于实现机器学习算法的 scikit-learn。虽然之前的 Python 经验不是强制性的，但我建议完成我将在 Canvas 上提供的交互式练习，以便在需要时熟悉 Python。
在后续部分中，我们将深入探讨机器学习中的特定主题。第三部分将介绍基于树的方法，包括决策树、随机森林和梯度提升。这些方法广泛用于各种机器学习应用程序中，将为您提供构建预测模型的宝贵工具。
第四部分将以模型评估为中心，这是机器学习的一个重要方面。我们将讨论比较和评估不同机器学习算法和模型的技术，使您能够在实际场景中选择和部署模型时做出明智的决策。
第五部分将探讨降维和无监督学习。不要被“无监督学习”这个术语吓倒；我们将在讲座中详细解释。这部分重点介绍了在没有明确标签的情况下从数据中分析和提取模式的方法，为数据探索和分析开辟了新的可能性。
如果时间允许，在第六部分中，我们将深入研究贝叶斯学习，其中涉及基于贝叶斯定理的方法。我们将讨论贝叶斯分类器、朴素贝叶斯分类器和潜在的贝叶斯网络。贝叶斯学习为理解和建模机器学习中的不确定性提供了一个概率框架。
最后，在学期末，我们将进行课堂项目展示。随着学期的进展，我将提供更多关于课堂项目的信息，但这将是您将知识和技能应用于特定问题或感兴趣的数据集的机会。这将是一个展示您对课程材料的理解并展示您实施机器学习技术的能力的机会。
在整个学期中，我将举行现场办公时间，我们可以就课程材料或您可能遇到的任何问题进行实时讨论。这些办公时间的详细信息将在适当的时候提供，我鼓励您利用这个机会与我和您的同学互动。
为了促进交流和协作，我们还将利用在线平台 Piazza，您可以在该平台上发布问题、参与讨论并及时收到我或您的同行的回复。我鼓励你积极参与 Piazza，因为它不仅对你有益，而且有助于班级的集体学习体验。
最后，我概述了课程的结构和可供您使用的各种资源。我希望这篇概述能让你清楚地了解我们将如何在整个学期中进行。如果您有任何问题或疑虑，请随时在办公时间内与我联系或在 Piazza 上发帖。我来这里是为了支持你的学习之旅，我很高兴能和大家一起踏上这场机器学习之旅。
谢谢，让我们开始第 1 讲的课程概述和教学大纲。
1.2 什么是机器学习（L01：什么是机器学习）
1.2 什么是机器学习（L01：什么是机器学习）
在新学期开始之际，我想对大家表示热烈的欢迎。我希望你们都度过了一个愉快的暑假。
在这段视频中，我想花点时间讨论课程的一些重要方面以及我们将如何合作。本课程与传统形式的面对面课程略有不同。我们将利用异步学习，这意味着我将预先录制讲座并在每周初与您分享。这使您可以在最适合自己的时间方便地观看资料。此外，您可以根据需要多次观看视频，对于网络速度较慢的用户，您还可以下载视频以供离线观看。
为了更轻松地浏览讲座，我将根据不同的主题将每个讲座分成多个视频。例如，在第一堂课中，我将涵盖各种主题，例如课程概述、教学大纲和机器学习的不同类别。本次讲座将分为六个视频。
虽然异步学习的缺点之一是您不能在讲座期间提问，但我将主持现场办公时间，我们可以讨论您可能遇到的任何问题或疑虑。我稍后会提供有关办公时间的更多详细信息。
现在，让我们深入了解课程内容。本学期将分为七个部分或模块。在第一部分中，我们将从机器学习的介绍和一个称为 K 最近邻的机器学习算法的简单示例开始。之后，我们将介绍计算基础，包括对 Python 的简要介绍，以及线性代数和主要的机器学习库 scikit-learn。如果您以前没有使用 Python 的经验，请不要担心。它易于学习，我将在 Canvas 上提供可选的交互式练习，以帮助您快速上手。
在计算基础之后，我们将探索基于树的方法，例如决策树、随机森林和梯度提升。然后，我们将深入研究模型评估，这是一个使我们能够比较不同机器学习算法和模型的基本主题。本课程的这一部分将使您具备评估和选择适合实际应用的最佳模型的技能。
接下来，我们将介绍降维和无监督学习。降维技术对于处理复杂的数据集至关重要，无监督学习将向您介绍我们没有标记数据来训练模型的方法。
如果时间允许，我们还将涉及贝叶斯学习，其中包括朴素贝叶斯分类器和贝叶斯网络等技术。本主题提供对基于贝叶斯定理的分类方法的理解。
在学期末，我们将进行课堂项目展示。我将在本学期晚些时候提供有关课程项目的更多信息。您可以在我已上传到 Canvas 的课程网站上找到更多详细信息和资源。我鼓励您浏览该网站并通读所提供的信息。
关于交流和资源，我们将主要使用 Canvas 进行所有与课程相关的活动。讲座视频、幻灯片和其他材料将在 Canvas 上提供。我还将使用 Canvas 公告来分享重要的更新和信息。请确保您的通知设置已启用，以便通过电子邮件接收这些公告。
为了增强您的学习体验，我建议您在观看视频之前下载幻灯片，以便您可以直接在上面做笔记。做笔记有助于更好地理解和记住材料。
如果您在访问课程资料时遇到任何技术困难，我建议您使用 Firefox 或 Chrome 作为浏览器，因为它们往往与 Canvas 配合使用效果最佳。
1.3 机器学习的分类（L01：什么是机器学习）
1.3 机器学习的分类（L01：什么是机器学习）
让我们进一步深入研究机器学习的不同类别或类型。最广泛的类别是监督学习，它处理标记数据。在监督学习中，我们的目标是根据给定的输入数据预测输出。例如，在垃圾邮件分类中，标签将是“垃圾邮件”和“非垃圾邮件”。目标是为未来的电子邮件预测电子邮件是否为垃圾邮件。此类别涉及一个反馈回路，其中使用正确或不正确的预测来改进算法并提高分类准确性。
在监督学习中，一个子类别是分类。分类侧重于分配类别标签，例如垃圾邮件和非垃圾邮件。例如，我们可以使用“减号”和“加号”等类别标签，旨在根据 X1 和 X2 表示的输入信息来区分这两个类别。机器学习算法检查测量结果并做出预测，不断学习分配正确的标签。通过在包含大量示例的数据集上训练算法，它可以学习绘制决策边界，即分隔类别的线。落在决策边界一侧的新数据点可能被归类为特定类别。
另一种类型的监督学习是回归，它处理分配一个连续的目标或输出值。回归分析侧重于根据输入特征预测连续结果。例如，线性回归是一种具有一个输入变量的简单模型，旨在通过拟合一条穿过数据点的直线来预测输出值 (Y) 以最大限度地减少误差。
继续进行无监督学习，该类别涉及分析未标记的数据以发现隐藏的模式或结构。在没有标签或反馈的情况下，无监督学习旨在在数据集中找到有意义的见解。聚类是无监督学习的一个例子，其中相似的数据点根据模式或密度分组在一起。可以利用各种聚类算法，如 k-means、DBSCAN 或层次聚类来识别和分组相似的数据点。
降维是无监督学习的另一个例子。它涉及减少数据集中的特征或维度的数量。特征提取和特征选择是降维中常用的技术。这些方法有助于压缩或转换特征以捕获最相关的信息，同时降低复杂性。
机器学习的最后一类是强化学习。在强化学习中，代理学习一系列动作以在给定环境中实现特定目标或最大化奖励。这种类型的学习涉及奖励系统，在该系统中，代理会根据其行为的结果接收反馈。通过反复试验，代理学会做出更好的决策并优化其性能。强化学习通常应用于机器人、游戏和复杂的决策场景。
请务必注意，虽然强化学习是一个重要主题，但本课程不会对其进行广泛介绍。但是，有专门的资源可供那些有兴趣进一步探索强化学习的人使用。
这些不同类别的机器学习为理解和应用各种技术和算法来解决不同类型的问题提供了广泛的框架。
现在，让我们深入研究机器学习的另一个方面，称为半监督学习。顾名思义，它介于有监督和无监督学习之间。在半监督学习中，我们混合了标记和未标记的数据。标记数据类似于我们在监督学习中讨论的内容，我们有输入和相应的类标签。然而，在半监督学习中，我们也有大量没有类别标签的未标记数据。
半监督学习的目标是利用额外的未标记数据来改进学习过程。通过结合标记数据和未标记数据，该算法可以发现数据中仅使用标记数据可能不明显的模式和关系。这可以导致更准确的预测和更好的泛化。
半监督学习在获取标记数据昂贵或耗时的情况下特别有用。我们可以使用较小的标记数据集和较大的未标记数据集来获得良好的结果，而不是手动标记大量数据。
半监督学习的一种方法是使用自我训练或共同训练等技术。在自我训练中，该算法最初对标记数据进行训练，然后使用其预测为未标记数据生成伪标签。然后将这些伪标签与原始标记数据组合以重新训练模型。此过程会重复多次，从而改进模型的预测并利用未标记的数据来提高性能。
在协同训练中，算法从数据的多个视图中学习。多个分类器在不同的特征子集或数据的不同表示上进行训练。最初，每个分类器都在标记数据上进行训练。然后，他们交换对未标记数据的预测，让每个分类器都能从对方的预测中学习。这个迭代过程继续进行，每个分类器根据其他分类器的共识改进其预测。
半监督学习是一个不断发展的研究领域，有多种算法和技术可用于应对有效利用未标记数据的挑战。这是一个令人兴奋的领域，它为在标记数据有限时提高机器学习性能提供了有希望的机会。
我们已经讨论了机器学习的不同类别，包括监督学习、无监督学习、强化学习和半监督学习。每个类别都有自己的特点和应用。监督学习处理标记数据并专注于做出预测或分配类别标签。无监督学习旨在寻找未标记数据中隐藏的结构或模式。强化学习涉及通过奖励系统学习一系列动作。最后，半监督学习结合标记和未标记数据来提高学习性能。
1.4 符号（L01：什么是机器学习）
1.4 符号（L01：什么是机器学习）
现在我们已经讨论了机器学习的概念和机器学习的主要类别，让我们更深入地研究监督学习。正如我们前面提到的，监督学习是机器学习中最大的一类。在本节中，我们将探讨与监督学习相关的符号、术语和概念。
监督学习遵循特定的工作流程。我们从一个包含输入特征示例及其相应目标信息或标签的训练数据集开始。输入特征也可以称为观察值。然后将数据集提供给机器学习算法。我们将在本课程的后面探讨各种类型的机器学习算法。该算法从训练数据中学习并生成预测模型。
该模型表示从训练数据中学到的知识，可用于对新的、未见过的数据进行预测。如果新数据与训练数据具有相同的格式，包括相同的特征，则可以使用经过训练的模型进行预测。这是监督学习的主要工作流程。
现在，让我们深入研究监督学习符号的形式方面。我们将训练数据集表示为 D，它由 N 个训练示例组成。每个训练示例包括一个特征向量 (X) 和一个相应的标签 (Y)。上标'i'代表训练点的索引，表示它在数据集中的位置。这里使用上标，是为了区别于我们后面要介绍的下标。
训练数据集是基于一个潜在的、通常是未知的函数生成的，该函数将标签分配给特征。此功能通常没有明确定义，可以是自然现象或人类标记过程。在机器学习中，我们的目标是使用模型或假设来近似这个函数 (F(X))。该模型应该以类似于未知函数的方式捕获输入特征 (X) 和标签 (Y) 之间的映射。
传统上，机器学习算法学习的假设或模型称为 H。该模型采用特征向量 (X) 并生成预测标签 (Y hat)。在回归问题中，预测标签是一个连续值，而在分类问题中，预测标签属于一组可能值。在分类中，可能的标签集通常使用整数表示，但也可以使用其他符号或字母表示。
在模型评估期间，使用单独的数据集来评估模型的性能。将模型做出的预测与真实标签进行比较，以衡量模型的准确性。在回归中，评估预测与真实标签的接近程度，而在分类中，检查预测标签与真实标签之间的一致性。
为了说明这些概念，让我们考虑一个真实的数据集示例，Iris 数据集。该数据集包含对鸢尾花不同特征的测量，例如萼片和花瓣尺寸。目标是根据这些测量结果预测花的种类。共有三种：setosa、versicolor 和 virginica。
在鸢尾花数据集中，每个训练样例对应一个花的测量值，特征代表维度，标签代表花的种类。该数据集包含 150 个训练示例，表示为 N=150，以及四个特征，表示为 M=4。
监督学习涉及使用训练数据集来学习近似未知基础函数的模型。该模型接受输入特征并生成预测。使用单独的数据评估模型的准确性。本节中讨论的符号和术语为理解和使用监督学习算法提供了基础。
1.5 ML应用（L01：什么是机器学习）
1.5 ML应用（L01：什么是机器学习）
在讨论了监督学习的符号和形式之后，让我们重新审视监督学习管道并探索我们如何在实践中处理机器学习问题。我们还将检查我们通常在此过程中考虑的各个组件。
我们之前检查过的简化图描述了监督学习的工作流程。在此工作流程中，我们从一个带标签的训练数据集开始，其中我们有特征标签。然后，我们应用一种机器学习算法，学习如何使模型适合训练数据。生成的模型可用于对新的、看不见的数据进行预测。请务必注意，此过程假设新数据来自与训练数据相同的分布。
现在，让我们深入研究一个更详细的流程图，该流程图说明了实际机器学习中涉及的各个组件。基本组件与上图相同：训练数据集、学习算法和结果模型。但是，还有其他细节需要考虑。
在实践中，在获得训练数据之前，我们通常会执行一些预处理步骤。除非我们获得预先准备好的数据集，否则我们需要确定要从数据中提取的特征。这在传统机器学习中尤为重要。例如，在根据测量对鸢尾花进行分类的情况下，我们可能拥有来自真实场景的图像数据或观察数据。无论哪种情况，我们都需要提取相关特征以提供给机器学习算法。与使用图像的原始像素不同，使用预处理或提取的特征通常更有效。对于鸢尾花示例，这些特征可能包括萼片长度、萼片宽度等。涉及具有问题知识的领域专家是很常见的，例如植物学家对花卉进行分类。他们的专业知识可以帮助选择有用的特征进行分类。
假设我们已经从原始数据中提取了特征，我们得到了一个由样本长度、样本宽度、花瓣长度和花瓣宽度组成的训练集。可能涉及额外的预处理步骤，例如特征缩放、特征选择（选择要包含的特征）和降维。这些预处理步骤还可能包括对数据集进行子采样等。在本课程中，我们将更详细地探讨这些预处理步骤的选择。
预处理完成后，我们为学习算法提供数据并拟合模型。然而，在将模型用于新数据之前，通常会将数据集分为两部分：训练集和测试集。训练集用于训练算法并得到模型，而测试集作为一个独立的数据集来评估模型的性能。此评估步骤可帮助我们评估模型在将其应用于真实世界、看不见的数据之前的性能。需要注意的是，在训练过程中，还涉及评估步骤，例如模型选择和交叉验证，这些步骤有助于调整超参数。我们将在本课程中广泛涵盖这些主题。
获得最终模型后，我们使用测试集评估其性能。此评估涉及使用模型预测测试集的标签并将这些预测与真实标签进行比较。在分类实例中，评价往往围绕分类准确率或错误率，表示正确分类实例的百分比。例如，我们可能会在正确分类花朵时达到 95% 的准确率。一旦对模型进行了评估，就可以将其用于新数据，以便在实际应用中进行预测。
尽管这张幻灯片似乎包含了大量的信息，但请放心，我们将在整个课程中更详细地研究这些步骤中的每一个。
实际上，在开发机器学习应用程序时，通常涉及五个主要步骤。首先，我们需要定义我们要解决的问题。
在定义了我们要解决的问题之后，下一步就是收集和准备数据。这涉及获取包含我们试图解决的问题示例的数据集。数据集应包括输入特征及其对应的标签。一旦我们有了数据集，下一步就是预处理和清理数据。这可能涉及处理缺失值、处理异常值、规范化或缩放特征，以及执行任何必要的转换或编码。数据预处理对于确保数据集的质量和可靠性以及为学习算法做好准备至关重要。
对数据进行预处理后，我们进入第三步，即选择合适的机器学习算法。算法的选择取决于问题的性质、数据类型和可用资源。有多种类型的算法可供选择，包括决策树、支持向量机、神经网络等等。每种算法都有自己的优点和缺点，选择最适合手头问题的算法至关重要。
一旦选择了算法，下一步就是使用准备好的数据集训练模型。在训练过程中，模型学习从输入数据及其相应标签中进行概括。这涉及调整模型的内部参数以最小化预测误差。训练过程通常涉及优化算法，例如梯度下降，它根据观察到的误差迭代更新模型参数。
模型训练好后，下一步就是评估其性能。这是使用单独的评估数据集完成的，通常称为验证集或保留集。使用的评估指标取决于问题的类型。对于分类任务，通常使用准确度、精确度、召回率和 F1 分数等指标。对于回归任务，使用均方误差 (MSE) 或平均绝对误差 (MAE) 等指标。评估有助于我们评估模型对未见数据的泛化能力，并提供对其优缺点的洞察。
如果模型的性能令人满意，最后一步是部署模型并使用它对新的、看不见的数据进行预测。这可能涉及将模型集成到更大的系统或应用程序中，以自动制定决策或帮助解决手头的问题。
值得注意的是，机器学习过程是迭代的，并且通常涉及在步骤之间来回切换。例如，如果模型的性能不理想，我们可能需要重新审视数据预处理步骤，尝试不同的算法，调整超参数，或者收集更多的数据来提高模型的性能。
本概述提供了对实际机器学习中涉及的典型步骤的高级理解。随着我们学习本课程，我们将更深入地研究每个步骤，探索不同的算法和技术，并获得将机器学习应用于现实世界问题的实践经验。
1.6 ML动机（L01：什么是机器学习）
1.6 ML动机（L01：什么是机器学习）
之前，我们讨论了解决机器学习问题的方法。该过程包括几个步骤，从定义手头的问题开始。我们强调了收集或寻找合适的数据集以供使用的重要性。一旦我们有了数据集，我们就会选择一个算法或算法类来解决这个问题。接下来，我们需要定义一个优化指标来有效地训练模型。训练后，我们将使用评估指标评估模型的性能。
展望未来，我们简要探讨了不同的机器学习方法和使用机器学习背后的动机。华盛顿大学的佩德罗·多明戈斯教授将这些方法分为五个部落：符号主义者、联结主义者、进化论者、贝叶斯主义者和类比主义者。每个部落代表为模型选择的不同表示、评估部分（目标函数）和优化方法。
例如，连接主义者部落使用神经网络作为他们选择的模型表示。他们优化平方误差或交叉熵作为目标函数，并采用梯度下降或反向传播作为优化方法。同样，进化部落利用遗传搜索进行优化，以遗传程序作为他们的模型表示。贝叶斯部落使用图形模型和概率推理来最大化后验概率。
这些示例概述了机器学习的不同方法。请务必注意，这些类别并不详尽，仅代表每个部落的几个示例。
Leo Breiman 提出了机器学习动机的另一种观点，他是一位有影响力的统计学家，以其在决策树和随机森林方面的工作而闻名。他介绍了两种文化的概念：预测和信息。预测文化侧重于使用机器学习做出准确的预测，而不必了解输入和输出变量之间的潜在关系。另一方面，信息文化旨在提取知识和理解变量之间关系的本质。
布雷曼表示，所有模型都是错误的，但有些是有用的。这突出了模型可解释性和性能之间的权衡。更简单的模型更容易解释但可能无法实现高性能，而更复杂的模型可能表现更好但更难解释。
此外，学习机器学习有不同的动机。工程师通常专注于应用机器学习来解决现实世界的问题，而数学家、计算机科学家和统计学家可能对发展机器学习理论更感兴趣。神经科学家可能会研究机器学习以更好地了解人脑，并开发受其功能启发的算法。
此外，我们还讨论了人工智能、机器学习和深度学习之间的关系。机器学习作为人工智能的一个子领域出现，深度学习是机器学习的一个子领域。深度学习特别关注多层神经网络并超越它们。深度学习可以被认为是神经网络的品牌重塑。人工智能系统是通过规则展现智能的非生物系统，例如自动驾驶汽车或下棋程序。机器学习不是 AI 的必要条件，因为可以在不使用机器学习技术的情况下开发 AI 系统。
最后，我们提到本课程将主要涵盖机器学习，而人工智能和深度学习属于不同的背景，可能会在其他课程中进行探讨。
在机器学习领域，有几种流行的编程语言和库被广泛用于实现和使用机器学习模型。这些工具提供了一系列功能，旨在让研究人员和从业者更轻松地开发、训练和评估机器学习模型。
机器学习领域最常用的编程语言之一是 Python。 Python 是一种多用途且易于学习的语言，提供了专门为机器学习量身定制的丰富的库生态系统。这些库提供各种机器学习算法的高效实现，以及用于数据操作、可视化和评估的工具。
一些用于机器学习的流行 Python 库包括：
NumPy：NumPy 是 Python 科学计算的基础库。它提供对大型多维数组和矩阵的支持，以及一组数学函数以有效地对这些数组进行操作。 NumPy 是许多其他机器学习库的基础。
Pandas：Pandas 是一个强大的数据操作和分析库。它提供数据结构和函数来有效地处理结构化数据，例如表格数据。在将数据输入机器学习模型之前，Pandas 对于预处理和清理数据特别有用。
Scikit-learn：Scikit-learn 是一个综合性的机器学习库，提供范围广泛的算法和工具，用于分类、回归、聚类、降维等。它提供统一的接口并遵循一致的 API，可以轻松地对不同的算法进行实验并比较它们的性能。
TensorFlow：TensorFlow 是谷歌开发的用于数值计算和机器学习的开源库。它提供了一个灵活的架构，用于构建和训练各种类型的机器学习模型，尤其侧重于深度学习。 TensorFlow 提供了一个名为 Keras 的高级 API，它简化了构建和训练神经网络的过程。
PyTorch：PyTorch 是另一个流行的深度学习库，它提供动态计算图并与 Python 无缝集成。它以其灵活性和易用性而著称，使其成为从事深度学习项目的研究人员和从业者的首选。 PyTorch 还提供了丰富的预训练模型生态系统和模型部署工具。
这些只是 Python 中可用于机器学习的众多工具中的几个示例。根据项目的具体要求，您可以探索满足您需求的其他库和框架。了解该领域的最新发展并选择最适合您的目标和偏好的工具非常重要。
除了 Python，其他编程语言如 R 和 Julia 也有专门的机器学习库和生态系统。特别是 R，广泛用于统计分析，并拥有丰富的机器学习包集合。另一方面，Julia 是一种专门为数值计算设计的语言，并为机器学习提供高性能库。
在整个课程中，我们将主要关注使用 Python 及其相关库，因为它们为探索和实施机器学习算法提供了一个强大而灵活的环境。但是，本课程中涵盖的概念和原则也可以应用于其他编程语言和工具。
我希望这能让您大致了解我们将使用的工具及其在机器学习领域的重要性。如果您有任何进一步的问题或需要澄清，请随时提出。
2.1 NN简介（L02：最近邻法）
2.1 NN简介（L02：最近邻法）
大家好，欢迎回来！我希望你第一周过得愉快。让我们简要回顾一下我们所涵盖的内容。在第 1 讲中，我们介绍了机器学习的概念，并讨论了最常见的问题，即关于课堂项目的问题。我将很快提供有关该项目的单独公告。我想提一提的是，我在 Piazza 上启用了一个功能，可以让你找到项目的团队成员。更多细节将在单独的公告中分享。
现在，让我们继续第 2 讲。今天，我们将主要关注 k 最近邻 (KNN) 算法，这是一种经典的机器学习算法，至今仍在广泛使用。我认为这是对机器学习最温和、最直接的介绍，因为它使我们能够理解机器学习算法的工作原理。尽管 KNN 可能不再是最流行的算法，但我强烈建议将其包含在您的项目中。它作为分类任务甚至预测连续输出的性能基准。 KNN 可以提供有关预测准确性和计算效率的见解。
谈到计算方面，除了解释 KNN 的工作原理外，我们还将涉及大 O 表示法的概念。这种表示法在计算机科学中常用来分析不同算法的效率。尽管听起来很技术性，但了解大 O 符号不仅对机器学习有用，而且对一般编程也很有用。
在本讲座的最后，我将用 Python 演示一些示例，向您展示如何使用 KNN。但是，请注意，这将是一个简短的概述，我们将在第 3 讲中更深入地研究 Python，包括安装和主要库，如 NumPy 和 scikit-learn。
那么，让我们开始第 2 讲吧！我们将主要关注最近邻方法，包括对 KNN 的介绍。我将讲座分为六个部分，以使其更易于理解：
最近邻方法的应用：我们将探索 KNN 的实际应用，例如网络使用数据挖掘、生物识别、图像分类和蛋白质分析。这些例子将有助于激发主题。
一个最近邻法：在深入 KNN 之前，我们将讨论最简单的情况，即一个最近邻法。此方法涉及找到与查询点最相似的数据点，并使用其标签作为预测。
最近邻法的决策边界：我们将研究最近邻法如何确定决策边界，以便更好地理解其内部工作原理。
K 最近邻方法简介：我们将过渡到 KNN，其中我们考虑多个最近邻而不是一个。我们将介绍 K 最近邻分类器和回归器。
K 最近邻算法的 Big O 运行时复杂度：我们将使用 Big O 表示法探索 KNN 的计算效率。该主题对于分析算法的性能至关重要。
改进 K 最近邻算法：在这一部分中，我将提出提高 KNN 性能的想法和技巧。本节着重于优化算法。
在涵盖了这些概念部分之后，我们将继续介绍 KNN 在 Python 中的应用。虽然这对某些人来说可能是最有趣的部分，但在深入实际实施之前首先掌握这些概念非常重要。
在下一讲，即第 3 讲中，我们将深入研究 Python 安装并涵盖主要库，包括 NumPy 和 scikit-learn。所以，一定要保持关注！让我们从第 2 讲开始，我们将探索最近邻方法和 K-最近邻算法，并对训练集中的所有数据点继续这个过程。在循环结束时，我们将确定离查询点最近的数据点。
找到最近点后，我们使用它的标签作为查询点的预测标签。在分类问题中，标签通常是表示类或类别的分类值。在回归问题中，标签是一个连续值。
总结最近邻算法的预测步骤：
现在我们已经讨论了一个最近邻方法，让我们继续讨论更一般的 k 个最近邻方法。 k最近邻算法将寻找最近数据点的概念扩展为寻找k个最近数据点。我们不是只考虑最近邻，而是考虑训练集中最接近查询点的 k 个数据点。
在分类的情况下，预测标签由 k 个最近邻居中的多数投票决定。每个邻居的投票权重相等，得票数最高的类别成为预测标签。
对于回归问题，预测的标签通常是 k 个最近邻标签的平均值或中值。组合标签的具体方法取决于问题的性质和期望的结果。
为了说明最近邻方法的决策边界，让我们考虑一个二维特征空间。我们有两个类，类 0 和类 1，用不同的符号表示（例如，三角形和正方形）。决策边界是分隔不同类别区域的直线或曲线。
在一个最近邻方法的情况下，决策边界遵循训练数据点的轮廓。特征空间中的每个点都根据最近的训练数据点的标签进行分类。决策边界不是平滑曲线，而是每个训练点周围的小区域集合。
当使用 k 大于 1 的 k 最近邻方法时，决策边界变得更平滑。当我们考虑更多的相邻点时，单个训练数据点的影响会减弱，从而产生更广义的边界。决策边界由 k 个最近邻居的多数投票决定，从而导致类之间更平滑和更连续的分离。
理解决策边界的概念对于评估 k 最近邻算法的性能和局限性至关重要。决策边界的形状和复杂性会影响算法准确分类或预测新数据点的能力。
除了讨论 k 最近邻算法，我们还会涉及到算法效率这个话题。大 O 表示法是分析和比较不同算法效率的常用方法。它提供了算法时间复杂度的度量，指示执行时间如何随着输入大小的增加而增加。
分析 k 最近邻算法的运行时复杂度有助于我们了解其计算效率。我们将简要探讨该主题并讨论算法的效率如何影响其在大型数据集上的性能。
在本讲座的最后，我们将深入探讨使用 Python 实现 k 最近邻算法的实际示例。我们将演示如何使用该算法进行分类和回归任务，展示其在现实场景中的应用。然而，在开始实施之前，必须掌握 k 最近邻的基本概念和原则。
回顾一下，在第二讲中，我们将一个最近邻方法作为最近邻算法的一个简单案例进行了介绍。我们探讨了该算法如何确定最接近查询点的数据点，以及它如何使用最近点的标签进行预测。我们还在最近邻方法中介绍了决策边界的概念及其形状。此外，我们还讨论了 k 最近邻算法，该算法考虑多个最近邻而不是一个。我们提到了预测标签是如何通过分类问题中的多数表决和回归问题中的平均值或中值来确定的。此外，我们简要介绍了大 O 表示法及其在分析算法效率方面的应用，包括 k 最近邻算法。
在下一讲，也就是第 3 讲中，我们将深入研究使用 Python 实现 k 最近邻算法。我们将介绍有效利用该算法的必要步骤、库和技术。所以，一定要和我一起参加下一堂课！
2.2 最近邻决策边界（L02：Nearest Neighbor Methods）
2.2 最近邻决策边界（L02：Nearest Neighbor Methods）
在第二个视频中，我们将研究最近邻算法的决策边界，特别关注最近邻分类器。我们将使用二维数据集进行说明，因为它更易于人类可视化。
该数据集由五个用蓝点表示的数据点组成。让我们放大点 A 和 B 并探索它们之间的决策边界。决策边界是分隔点 A 和 B 的一条线或边界。如果我们将一个最近邻模型拟合到数据集，这个决策边界会是什么样子？
要回答这个问题，我们需要了解等距离的概念。位于决策边界上的任何点都应与点 A 和 B 等距。花点时间暂停视频，想一想决策边界会是什么样子。点 A 和 B 的决策边界将是使用欧氏距离度量绘制的一条线。这条直线上的任何一点到A点和B点的距离都相等，这意味着直线上的点与A点和B点之间的距离在直线上的任何地方都相同。现在让我们转到点 A 和 C 并确定它们的决策边界。点 A 和 C 的决策边界将是一条垂直于连接 A 和 C 的线的线。这条线上的每个点都与点 A 和 C 等距。
我们可以对数据集中的所有点对（例如 C 和 D）继续这个练习，以确定它们各自的决策边界。通过为每对点组装所有这些决策边界，我们获得了一个最近邻分类器的决策边界，如右下角所示。
如果我们仔细观察该图，我们可能会注意到它类似于 Voronoi 图或 Voronoi 镶嵌。该图将数据集划分为区域，每个区域对应于一对点之间的决策边界。边界线上的每个点都与两个相邻点等距。
然而，我们还没有完成。在上一张幻灯片中，我们只显示了决策区域，没有考虑实际的类标签。现在让我们将类标签重新引入数据集。三角形代表第 1 类，正方形代表第 0 类。
为了获得一个最近邻算法将用于分类的决策区域，我们需要采用属于同一类标签的区域的并集。例如，红色三角形有一个由与红色三角形最近点对应的边界包围的决策区域。同样，蓝色方块也有自己的决策区域。通过用各自的颜色填充这些区域，我们得到了一个最近邻分类器的决策边界。
为了测试您的理解，让我们提出一个简单的问题。给定数据集中的五个数据点，哪个点离问号点最近？暂停视频片刻，思考你的答案。回答这个问题需要了解用于确定接近度的距离度量。在这种情况下，我们使用欧氏距离，但也可以使用其他距离度量。根据所选的距离度量，离问号点最近的点可能会有所不同。
在视频中，演示了两种距离度量：欧氏距离和曼哈顿距离。欧几里德距离衡量的是两点之间的直线距离，而曼哈顿距离是通过求和坐标之间的绝对差来衡量距离。
此外，该视频还简要提到了马氏距离，它考虑了特征的分布。它根据标准差考虑数据点与其分布的距离。测量两个向量之间的角度的余弦相似度也被称为距离测量。
在实践中，距离度量的选择取决于具体问题和数据集的特征。它可以被认为是最近邻算法的一个超参数，需要根据手头的问题仔细选择。
现在让我们讨论 k 最近邻算法，它是一个最近邻算法的扩展。在k近邻算法中，我们不是只考虑最近的点，而是考虑距离查询点最近的k个点。 k-最近邻算法的决策边界由投票机制决定。特定类别的决策区域内的每个点都有助于对该类别的投票。 k 个最近邻中得票最多的类被指定为查询点的预测类。
例如，假设我们有一个用绿星表示的查询点。如果我们使用 3 最近邻算法，我们会查看距离查询点最近的三个点。如果这些点中有两个属于 0 类，一个属于 1 类，则多数投票会将查询点分配给 0 类。类似地，如果我们将 k 的值增加到 5，我们将考虑距离查询最近的五个点观点。如果其中三个点属于 1 类，两个属于 0 类，则多数投票会将查询点分配给 1 类。
k 值的选择是 k 最近邻算法中的一个重要考虑因素。较小的 k 值可能会导致过度拟合，即算法对数据的局部波动过于敏感。另一方面，较大的 k 值可能会导致欠拟合，此时决策边界变得过于平滑，无法捕获更精细的细节。与任何算法一样，需要权衡取舍，k 的选择取决于数据集和手头的问题。试验不同的 k 值并使用交叉验证等技术来找到最佳值是很常见的。
k近邻算法通过考虑k个最近点扩展了一个最近邻算法。决策边界由基于 k 个最近邻居的类标签的投票机制确定。 k的选择是一个超参数，需要仔细选择以平衡过拟合和欠拟合。
2.3 K近邻（L02: Nearest Neighbor Methods）
2.3 K近邻（L02: Nearest Neighbor Methods）
在上一个视频中，我提到并非前面讨论的所有距离度量都是指标。例如，余弦相似度不被认为是合适的度量，因为它不满足三角不等式。三角不等式指出两个数据点之间的距离，表示为 A 和 C，应该小于或等于 A 和 B 以及 B 和 C 之间的距离之和。然而，尽管不是一个合适的度量，余弦在特定情况下，相似性在实践中仍然非常有用。
现在，让我们深入研究 k 最近邻 (k-NN) 方法，它是我们之前讨论的最近邻方法的扩展。 k-NN 模型相对简单，因为它通过考虑多个最近邻居而不是一个最近邻居来推广一个最近邻居方法。
在本视频中，我展示了一个 k-NN 模型示例。我们有两个特征，x1 和 x2，以及一个玩具数据集，其中包含用十字、圆形和三角形表示的不同类别。我们的目标是对中心问号表示的数据点进行分类。为了进行预测，我们使用欧几里得距离度量来考虑问号周围一定半径内的数据点。
现在的问题是：对于给定的示例，在这种 k-NN 方法中，k 的值是多少？如果您花点时间思考一下，您会发现 k 为 5，因为我们正在考虑离我们要分类的点最近的五个数据点。
考虑到五个最近的邻居，我们计算每个类的出现次数。例如，如果我们找到一个三角形、一个圆圈和三个十字，多数票会将预测的类标签分配给查询点。在这种情况下，预测的类标签将是一个三角形，因为它在五个最近的邻居中出现最多。
尽管我们在 k-NN 中技术上有“多数票”，但在实践中通常称为“多数票”。当投票过程出现平局时，即多个类别的计数相同时，软件包通常会随机选择一个标签或选择具有较低类别标签索引的标签。
为了提供多数表决的更正式定义，让我们考虑子集 D sub k，它表示 k 个最近的邻居。我们将多数表决定义为最大化 delta 函数之和的类标签 (y)。如果 a 等于 b（匹配标签），则 delta 函数返回 1，否则返回 0。通过对每个邻居的增量值求和，我们可以找到最常出现的类别标签。
对于使用 k-NN 的回归分析，过程更简单。我们处理连续的目标值而不是类标签。 k-NN 回归的预测 (h) 是 k 个最近邻居的目标值的平均值。
在下一个视频中，我们将深入探讨大 O 分析的主题，其中涉及分析 k 最近邻算法的运行时复杂度。了解算法的效率对于评估其性能和可扩展性至关重要。大 O 分析提供了一种方法来估计算法的执行时间将如何随着输入大小的增加而增长。这种分析有助于我们做出有关算法选择和优化的明智决策。要对k近邻算法进行Big O分析，我们需要考虑两个主要因素：训练实例的数量（n）和特征的数量（d）。这些因素决定了为给定查询点查找 k 个最近邻居的计算成本。
在 k 最近邻的最简单实现中，我们将计算查询点与每个训练实例之间的距离，从而导致时间复杂度为 O(nd)。这意味着算法的运行时间随着训练实例的数量和特征的数量线性增长。
但是，有一些方法可以优化 k 最近邻算法并降低其计算成本。一种常见的方法是使用加速最近邻居搜索的数据结构，例如 kd 树或 ball 树。这些数据结构以分层方式划分训练实例，允许更有效的邻居搜索。
使用这些数据结构，我们可以在某些情况下将搜索时间缩短为 O(log n) 甚至 O(1)。这种改进显着加快了算法的速度，尤其是对于大型数据集。
重要的是要注意距离度量的选择也会影响算法的运行时复杂性。可以有效地计算一些距离度量，例如欧几里得距离，而其他距离度量，例如曼哈顿距离，可能需要更多的计算资源。
k近邻算法除了时间复杂度外，还要考虑空间复杂度。空间复杂度是指存储训练实例和用于有效邻居搜索的任何附加数据结构所需的内存量。对于优化实现，空间复杂度通常为 O(nd) 或 O(n)。
总体而言，了解 k 最近邻算法的运行时和空间复杂性有助于我们评估其可扩展性并在处理大型数据集或实时应用程序时做出明智的决策。
在下一个视频中，我们将进一步探讨这些概念，并对算法的效率进行更详细的分析。请继续关注有关 k 最近邻的 Big O 分析的深入讨论。