KNN方法附.pptx

多元多元线性回性回归模型模型（附：（附：knn算法算法代码）代码）9.3多元线性回归多元线性回归在实际问题中，常常需要研究一个被解释变量，多个解释变量的线性回归模型例 位于南加州的巴特勒运输公司的管理人员为制定最佳的工作计划，希望估计他们的司机每天行驶的时间。起初，公司管理人员认为，司机每天行驶的时间与每天运送货物行驶的里程密切相关，通过观察散点图，管理人员假设，能利用一元线性回归模型来描述行驶的小时数（Y）与行驶的英里数（X）之间的关系。对公司的实际数据，采用普通最小二乘法估计出回归方程为通过对方程的分析，公司的管理人员发现，虽然这一结果不错，但方程只能解释每天行驶时间的变异性的66.4%。因此希望增加第二个解释变量去解释剩下的变异性。管理人员在研究其它影响行驶时间的因素时，觉得运送货物的次数也会影响行驶的时间。因此在增加了一个解释变量运送货物的次数，以及相应的数据后，再进行回归分析，得到的回归方程具有形式管理人员现在发现，这一方程能解释行驶时间变异性的90.4%。这已是相当好的结果了。多元线性回归模型的基本假设（高斯假设）多元线性回归模型的基本假设（高斯假设）多元线性回归模型的矩阵表示多元线性回归模型应该对所有的样本数据都成立，因此有这是n个表达式。回归分析的目的就是利用由样本数据产生的这n个表达式估计模型的参数，得到模型的参数估计值 使得回归方程最好地拟合了所有样本数据。为便于讨论，对多元线性回归模型，常使用矩阵形式其中最小二乘估计式最小二乘估计式现在仍采用矩阵的记法，多元线性回归模型为若得到了参数的估计量 则相应的回归方程为于是残差向量为普通最小二乘法就是要确定参数的估计值 使残差平方和达到最小。由于残差的平方和可以表示为而要使残差的平方和最小就必须 ，即这就是所谓的正规方程组，其解就是要求的估计量。一般的矩阵 可逆。因此正规方程组的解为这就是要求的最小二乘(OLS)估计量。9.5 K-最近邻分类分类思想分类思想基于距离的分类算法的思路定定义：给定一个数据定一个数据库 D=x1，x2，xn和一和一组类C=C1，Cm。假定每个元。假定每个元组包括一些数包括一些数值型的属性型的属性值：xi=xi1，xi2，xik，每个，每个类也包含数也包含数值性属性性属性值：Cj=Cj1，Cj2，Cjk，则分分类问题是要分配每个是要分配每个xi到到满足如下条件的足如下条件的类Cj：sim(xi，Cj)=sim(xi，Cl)，ClC，ClCj，其中其中sim(xi，Cj)被称被称为相似性。相似性。在在实际的的计算中往往用算中往往用距离距离来表征，距离越近，相似性越大，距来表征，距离越近，相似性越大，距离越离越远，相似性越小。，相似性越小。距离的距离的计算方法有多种，最常用的是通算方法有多种，最常用的是通过计算每个算每个类的中心来完的中心来完成。成。基于距离的分基于距离的分类算法的一般性描述算法的一般性描述算法：通过对每个元组和各个类的中心来比较，从而可以找出他的最近的类中心，得到确定的类别标记。算法算法 基于距离的分类算法输入：每个类的中心C1，Cm；待分类的元组x。输出：输出类别c。（1）dist=；/距离初始化（2）FOR i:=1 to m DO（3）IF dis(ci，x)dist THEN BEGIN（4）c i；（5）distdist(ci，x)；（6）END.基于距离的分类方法的直观解释基于距离的分类方法的直观解释（a）类定义（b）待分类样例（c）分类结果K-近近邻分分类算法算法K-近邻分类算法（K Nearest Neighbors，简称KNN）通过计算每个训练数据到待分类元组的距离，取和待分类元组距离最近的K个训练数据，K个数据中哪个类别的训练数据占多数，则待分类元组就属于哪个类别。算法算法 K-近邻分类算法近邻分类算法输入：输入：训练数据训练数据X；近邻数目；近邻数目K；待分类的元组；待分类的元组t。输出：输出：输出类别输出类别c。（1）N=；（2）FOR each d X DO BEGIN（3）IF|N|K THEN（4）N=N d；（5）ELSE（6）IF u N such that sim(t，u)sim(t，d)THEN BEGIN（7）N=N-u；（8）N=N d；（9）END（10）END（11）c=class to which the most u N.KNN的例子（的例子（1）“高度”用于计算距离，K=5，对对分类分类。对T前K=5个记录，N=、和。对第6个记录d=，得到N=、和。对第7个记录d=，得到N=、和。序号姓名性别 身高类别1Kristina女 1.6矮2Jim男 2高3Maggie女 1.9中等4Martha女 1.88中等5Stephanie女 1.7矮6Bob男 1.85中等7Kathy女 1.6矮8Dave男 1.7矮9Worth男 2.2高10Steven男 2.1高11Debbie女 1.8中等12Todd男 1.95中等13Kim女 1.9中等14Amy女 1.8中等15Wynette女 1.75中等KNN的例子的例子“高度”用于计算距离，K=5，对对分类分类。对第7个记录d=，得到N=、和。对第8个记录d=，得到N=、和。对第9和10个记录，没变化。对第11个记录d=，得到N=、和。对第12到14个记录，没变化。序号姓名性别 身高类别1Kristina女 1.6矮2Jim男 2高3Maggie女 1.9中等4Martha女 1.88中等5Stephanie女 1.7矮6Bob男 1.85中等7Kathy女 1.6矮8Dave男 1.7矮9Worth男 2.2高10Steven男 2.1高11Debbie女 1.8中等12Todd男 1.95中等13Kim女 1.9中等14Amy女 1.8中等15Wynette女 1.75中等KNN的例子的例子“高度”用于计算距离，K=5，对对分类分类。N=、和。对第15个记录d=，得到N=、和。最后的输出元组是、和。在这五项中，四个属于矮个、一个属于中等。最终KNN方法认为Pat为矮个。序号姓名性别 身高类别1Kristina女 1.6矮2Jim男 2高3Maggie女 1.9中等4Martha女 1.88中等5Stephanie女 1.7矮6Bob男 1.85中等7Kathy女 1.6矮8Dave男 1.7矮9Worth男 2.2高10Steven男 2.1高11Debbie女 1.8中等12Todd男 1.95中等13Kim女 1.9中等14Amy女 1.8中等15Wynette女 1.75中等KNN的直的直观解解释1、定义的直观形式：找出与目标最接近的K个样本；将目标划分到找出的K个样本中出现最频繁的类。2、K的直观形式：以目标样本为中心；划出一个刚好包含K个样本的圆；当K增大时，圆半径增大。KNN的直的直观解解释3、直观的例子、直观的例子手写识别记录手写体特征；计算手写体与标准汉字的相似度；根据相似度（距离），找出K个备选集；人工选择一个正确汉字人种识别欧洲人的鼻子、亚洲人的眼睛非洲人的肤色、亚洲人的头发形象的例子KNN的分类思想如果它走路像鸭子,叫声也像鸭子,那么他可能就是只鸭子Training RecordsTest RecordCompute DistanceChoose k of the“nearest”recordsKNN的特点的特点1、非参数统计方法不需引入参数回归分析是参数统计方法2、k的选择K=1时，将待分类样本划入与其最接近的样本的类；K=|X|时，仅根据训练样本进行频率统计，将待分类样本划入最多的类；K需要合理选择，太小容易受干扰、太大增加计算复杂性3、算法的复杂度维数灾难：当维数增加时，所需的训练样本数急剧增加一般采用降维处理（一）欧几里得距离欧式距离由对应元素间差值平方和的平方根所表示，即（二）曼哈坦距离对应元素间差值绝对值的和表示，即欧几里得距离与曼哈坦距离的共同点(1)即距离是一个非负的数值 (2)自身的距离为0 (3)即距离函数具有对称性 (4)即距离函数满足三角不等式 距离计算方法距离计算方法(三三)明考斯基距离明考斯基距离是欧几里得距离和曼哈坦距离的概化其中p是一个正整数，当p=1时，它表示曼哈坦距离；当p=2时，它表示欧几里得距离。(四四)加权的明斯基距离加权的明斯基距离如果对每一个变量根据其重要性赋予一个权重，就得到加权的明考斯基距离。如果描述特征的不是数值，距离如何计算，相似性如何计算，还可做进一步研究。参考Q.X Wu,T.M McGinnity,D.A Bell,G Prasad,“A Self-Organising Computing Network for Decision-Making in Data Sets with Diversity of Data Types,”IEEE Transaction on Knowledge and Data Engineering,vol.18(7),2006,pp.941-953.k近近邻法法K近邻近邻设有N个样本分布到c个类为1，,i，c，每类有Ni个样本，i=1c。在全部 样本找出k个最近距离的近邻。k个近邻分布于c个类中数目用ki表示。k近邻的判断函数为：决策规则决策规则 如果 那么决策为 如图所示例子中k1=4，k2=0，k3=1，所以 j=1，。本例的k1=4，k2=0，k3=1k近近邻算法算法例子例子1、9.5中割草机的例子（中割草机的例子（P163）距离：以“收入”作为距离的度量将第24条记录作为测试样本集，前23条作为训练样本集K=3作作 业业1、用、用matlab实现实现KNN算法算法函数形式：函数形式：c=knn(X,t,k)，X中属性值为连续型中属性值为连续型其中：其中：uX是训练样本集，每行为一个样本是训练样本集，每行为一个样本ut:是新样本是新样本uc:是用是用KNN方法对新样本方法对新样本t的分类的分类uk:是近邻数目是近邻数目u函数中距离采用欧氏距离函数中距离采用欧氏距离2、利用以上函数，对、利用以上函数，对P163页表页表9-11问题进行计算，其中问题进行计算，其中u以前以前23个样本为训练样本，第个样本为训练样本，第24个样本为测试样本个样本为测试样本u分别计算分别计算k=1,2,3,23的情况下各个分类结果的情况下各个分类结果KNN-算法function c=silentian(X,t,k)Row_sum=size(X,1)%-行数-%Col_sum=size(X,2)%-列数-%Class=X(:,Col_sum)%-X最后一列-%Classtype=unique(Class)%-类别-%L=length(Classtype)%-最大维数-%N=size(t,1)%-测试数据行数-%XX=X(1:Row_sum,1:Col_sum-1)%-X中除去类别属性-%for i=1:N cnt=Classtype*0;dist=sum(XX-ones(Row_sum,1)*t(i,:).2,2);d,index=sort(dist);%按升序排列距离 for j=1:k ind=find(Classtype=Class(index(j);cnt(ind)=cnt(ind)+1;end m,ind=max(cnt);c(i)=Classtype(ind);end