机器学习简明教程---基于Python语言实现 课件 第4章基于距离的算法.pptx

基于距离的算法《机器学习简明教程》高延增侯跃恩罗志坚机械工业出版社04

本章目标?掌握分类和聚类的区别?理解几种常用的距离度量方法?掌握K近邻算法?掌握K均值算法逻辑回归可以根据学生的作业成绩和平时表现预测学生期末总评是否能及格，也就是说逻辑回归算法将学生分成了“及格的”和“不及格的”两种类别，类似这样用已知标签的训练集训练一种机器学习算法给某个个体打上类别标签的过程称为分类。还有一类问题，比如需要设计一套算法将学生按其特点归类以制定个性化的人才培养方案，但算法事先并不知道训练样本中的学生具体的类标签，类似这类问题被称为聚类。分类是一种有监督学习任务，其训练样本有自变量及其对应的因变量，即根据一堆已经打上分类标签的训练数据寻找合适的分类算法；而聚类是一种无监督学习任务，无监督学习的处理对象是一堆无标签的数据，算法需要从数据集中发现和总结模式或者结构来完成聚类任务。本章的重点是属于有监督学习的K近邻算法、属于无监督学习的K均值算法。虽然K近邻和K均值分别属于有监督、无监督学习算法，但因其实现原理有一定相似性，本书将此两种算法放在同一章节介绍。

目录/Contents4.14.2分类与聚类的区别距离度量问题4.3K近邻4.4K均值聚类

4.1分类与聚类的区别所谓分类就是从已知类别样本组成的集合中训练出一种分类器，用这个分类器对未知类别的样本进行分类。分类算法的分类过程就是建立一种分类模型来描述预定的数据集或概念集，通过分析由属性描述的数据库元组来构造模型。分类的目的就是使用分类对新的数据集进行划分，其主要涉及分类规则的准确性、过拟合、矛盾划分的取舍等，分类问题示意如图：“物以类聚、人以群分”，在一个空间中，如果两个样本距离较近，那它们同属一个类别的可能性也较高。根据这一思想，在对一个新的、未知类别的样本进行分类时可以参考与它距离较近的一些样本的类别，据此来对新样本进行分类表决，这就是K近邻分类的基本思想。

4.1分类与聚类的区别聚类算法分为层次聚类、划分聚类两种。层次聚类初始阶段将每个样本点看成一类，然后再对这些类每次迭代的时候都进行两两合并，直到所有的类聚集完成；划分聚类首先指定类的个数K，然后将样本集随机分成K类，在每次迭代的时候对样本集进行重新优化组合成为新的K类，最后使得类内的相似度、类间的差异或迭代次数达到设定值。与分类类似，聚类任务的流程也可划分为数据准备、特征选择、特征提取、聚类、聚类结果评估等几个阶段。假设有一组样本如下图（a）所示，事先不知道这些样本的具体类别，如果指定要分为2类（K=2），分类结果如图（b），这就是划分聚类。各种划分聚类算法中，K均值是最著名的一种。

4.1分类与聚类的区别K均值聚类是一种迭代求解算法，首先，随机选取K个中心，计算样本点与K个中心的距离并将此样本点暂时归类为离它最近的那个中心，这样处理完每个样本点后就可以临时将样本空间分为K个类；然后，将这K个类的中心作为新的中心点，再重新按样本点与新的中心的距离来重新聚类一次；循环往复，直至达到循环结束条件。K近邻分类和K均值聚类算法的一个重要依据是距离。数据挖掘中的样本通常由一个多维度的向量表示，而样本的相似性大小的度量可以转化为对应向量之间的距离的求解。对于距离概念的深入理解，是掌握数据挖掘算法的必要前提。

目录/Contents4.14.2分类与聚类的区别距离度量问题4.3K近邻4.4K均值聚类

4.2距离度量问题距离是一个函数，将样本空间中的两个样本点映射为一个实数?机器学习中可能用到的距离函数有很多，包括欧式距离、曼哈顿距离、切比雪夫距离等。但一个距离函数又不是随意的将两个样本点映射为一个实数，此映射函数只有在满足一定前提条件后才能被当成距离函数使用。

4.2距离度量问题广义的距离函数???描述样本点的向量的维度值有两类变量，表示身高、体重这一类属性的数值型维度，以及表示性别、是否及格等的布尔型维度，根据向量的特点可以将距离函数分成数值向量距离和布尔向量距离两类。

4.2距离度量问题——数值向量距离数值向量距离函数有很多，常用的有欧式距离（Euclideandistance）、曼哈顿距离(Manhattandistance)、闵可夫斯基距离(Minkowskidistance)等。欧式距离(Euclideandistance)二维向量欧式距离示意图????

4.2距离度量问题——数值向量距离欧式距离简明易懂，但在数据挖掘算法中使用时存在明显缺陷。由欧式距离的计算公式知，它的结果与度量单位有关，这在应用时往往会与实际意愿相背离。例如，在教育数据挖掘项目中要计算两个学生的相似性，如果以米为单位他们的身高这一维度上可能有0.2的差距，但如果以厘米为单位，这一差距就变成20了，这样和其他维度比如体重