机器学习（MATLAB版）-习题及答案 ch05

第五章K近邻算法K近邻算法的定义及流程定义：K近邻算法是一种常用的监督学习方法，它的基本思想是：要确定一个样本的类别，可以计算它与所有训练样本的某种距离（例如欧氏距离），然后找出与该样本最接近的K个样本，统计这些样本的类别并进行“投票”，得票最多的那个类就是分类结果。流程：当先=1时，k近邻算法退化为最近邻算法。更通俗地说，先近邻算法是按照一定规则将相似的样本数据进行归类的，类似于现实生活中的“物以类聚，人以群分”。首先，计算待分类数据特征与训练数据特征之间的距离并排序，取出距离最近的k个训练数据特征；然后，根据这个相近训练数据特征所属的类别来判定新样本的类别：如果它们都属于同一类，那么新样本也属于这一类；否则，对每个候选类别进行评分，按照某种规则确定新样本的类别。一般釆用投票规则，即少数服从多数，期望的先值是一个奇数。精确的投票方法是计算每一个测试样本与k个样本之间的距离。容易发现，k近邻算法实现十分简单，只需计算待测样本与每一个训练样本的距离即可，这是它的优点；其缺点是当训练样本容量大、特征向量维数高时，计算复杂度将变得十分可观。因为每次预测时都要计算待测样本与每一个训练样本的距离，而且需要对距离进行排序找到最近的k个样本。此外，一个不容忽视的问题是参数k的取值，除了必须是一个奇数外，还需要根据问题和数据的特点来确定。在算法实现时还可以考虑样本的权重，即每个样本有不同的投票权重，这种方法称为加权为近邻算法。另外，化近邻算法也可以用于回归问题。在得到待处理数据的必个最相似训练数据后,求取这些训练数据特征的平均值，并将该平均值作为待处理数据的特征值。也就是说，假设距离待测试样本最近的k个训练样本的标签值为饥，则对该样本的回归预测值为：K近邻算法的距离函数都有哪些在样本数有限的情况下，&近邻算法的误判概率和距离的具体测度有直接关系。因此,在选择近邻样本数时利用适当的距离函数能够提高分类的正确率。通常，北近邻算法可釆用欧氏距离(EuclideanDistance)、曼氏距离(ManhattanDistance)、马氏距离(Mahalan-obisDistance)等距离函数。1.欧氏距离(EuclideanDistance)：2.曼氏距离(ManhattanDistance又叫街区距离)：3.马氏距离(MahalanobisDistance)：欧氏距离，曼氏距离，马氏距离的区别欧氏距离是最常用也是我们最熟知的距离。但在使用欧氏距离时，要注意将特征向量的分量归一化，以减少因特征值的尺度范围差异所带来的干扰，否则数值小的特征分量会被数值大的特征分量所淹没。也就是说，欧氏距离只是将特征向量看作空间中的点，并未考虑这些样本特征向量的概率分布规律。与欧氏距离不同，马氏距离则是一种概率意义上的距离，它与数据的尺度无关。马氏距离更为一般的定义是：其中，S是对称正定矩阵。这种距离度量的是两个随机向量的相似度。显然，当S为单位阵时，马氏距离即退化为欧氏距离。矩阵S可以通过计算训练样本的协方差矩阵得到，也可以通过对样本的“距离度量学习”得到。另外还有一种巴氏距离(BhattacharyyaDistance),它定义了两个离散型或连续型随机向量概率分布的相似性。对于在同一域X的两个离散型分布p(x)，q(x),其定义为：对于连续型分布，其定义为：显然，两个随机向量越相似，这个距离值越小。注意,巴氏距离不满足三角不等式。k近邻算法的判别函数和判别准则（1）初始化距离值为最大值，便于在搜索过程中迭代掉。（2）计算待分类样本和每个训练样本的距离disto（3）得到目前k个最近邻样本中的最大距离maxdisto（4）如果dist小于maxdist,则将该训练样本作为k近邻样本。（5）重复步骤（2）、（3）、（4）,直到未知样本和所有训练样本的距离都计算完。（6）统计存近邻样本中每个类标号出现的次数。（7）选择出现频率最高的类标号作为未知样本的类标号。简述类的属性（1）W与Y的长度相同的非负数值向量，用于表示对应样本观测值的权值。（2）Sigma数值向量，长度等于特征变量的个数，表示对应特征变量做归一化时的标准差。（3）PredictorNames特征变量的变量名。（4）ResponseName标签变量的变量名。（5）ClassNames标签的种类，存放每种标签的名字。（6）Prior数值向量。每一类标签的先验概率，也就是每种类别在X中的占比。向量中的元素对应ClassNames中的元素。（7）NumNeighbors正数，表示k近邻的个数。（8）NumObservations用于训练分类器的样本数，小于或者等于X的行数，因为如果X中存在NaN,这些数据无效，会导致训练数据小于X的行数。或者说，即使X中有些数据错误，也不会导致程序报错，i玄个库函数是具有容错性的。（9）Mu数值向量，长度等于特征变量的个数，表示每个特征变量的均值，用于归一化。（10）Distance字符向量或者函数句柄，表示A;近邻所选择的距离标准，比如是欧氏距离还是其他距离等，可用helpfitcknn查看。选择不同的距离标准还受到搜索方法的限制，搜索方法由NsMethod参数决定。（11）ModelParameters训练分类器用到的参数。NsMethod就在其中。NsMethod参数有"exhaustive"和“kdtree”两种，分别是穷举搜索和基于树的搜索。（12）DistanceWeight字符向量或者函数句柄，可选参数有'equal11inverse5'squareinverses分别表示无权重、与距离的一次方成反比、与距离的二次方成反比。（13）DistParameter距离标准的额外参数，可选参数^ahalanobis5'minkowski'七euclidean，，分别表示正定相关矩阵C、闵可夫斯基距离指数(一个正的标量)、元素为正的向量且长度等于X的列数。（14）ExpandedPredictorNames如果模型使用了编码以后的特征变量，那么这个参数用于