工作报告之数据挖掘试验报告

本文格式为Word版，下载可任意编辑——工作报告之数据挖掘试验报告数据挖掘试验报告

数据挖掘试验报告

——k-最邻近分类算法

学号：311062202姓名：汪文娟一、数据源说明1.数据理解

选择其次包数据irisdataset，共有150组数据,考虑到训练数据集的随机性和多样性，选择rowno模3不等于0的100组作为训练数据集，剩下的50组做测试数据集。

（1)每组数据有5个属性，分别是：1.sepallengthincm2.sepalwrownothincm3.petallengthincm

4.petalwrownothincm5.class:

--irissetosa

--irisversicolour--irisvirginica

（2)为了操作便利，对各组数据添加rowno属性,且第一组rowno=1。2.数据清理

现实世界的数据一般是不完整的、有噪声的和不一致的。数据清理例程试图填充缺失的值，光滑噪声并识别离群点，并改正数据中的不一致。

a)缺失值：当数据中存在缺失值是，忽略该元组（注意：本文选用的其次组数据iris

dataset的missingattributevalues:none）。b)噪声数据：本文暂没考虑。二、k-最邻近分类算法

knn(knearestneighbors)算法又叫k最邻近方法，假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，knn就是计算每个样本数据到待分类数据的距离，假使一个样本在特征空间中的k个最相像(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决

定待分样本所属的类别。knn方法虽然从原理上也依靠于极限定理，但在类别决策时，只与极少量的相邻样本

有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于knn方法主要靠周边有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交织或重叠较多的待分样本集来说，knn方法较其他方法更为适合。该方法的不足之处是计算量较大，由于对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的k个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较简单产生误分。（1）算法思路：

k-最邻近分类方法存放所有的训练样本，在接受待分类的新样本之前不需构造模型，并且直到新的（未标记的）样本需要分类时才建立分类。k-最邻近分类基于类比学习，其训练样本由n维数值属性描述，每个样本代表n维空间的一个点。这样，所有训练样本都存放在n维模式空间中。给定一个未知样本，k-最邻近分类法探寻模式空间，找出最接近未知样本的k个训练样本。这k个训练样本是未知样本的k个“近邻〞。“邻近性〞又称为相异度（dissimilarity），由欧几里德距离定义，其中两个点x（x1,x2,?xn）和y（y1,y2,?yn）的欧几里德距离是：

d(x,y)?(x1?y1)?(x2?y2)?...?(xn?yn)222

未知样本被分派到k个最邻近者中最公共的类。在最简单的状况下，也就是当k=1时，未知样本被指定到模式空间中与之最邻近的训练样本的类。

（2）算法步骤：

step.1初始化距离为最大值

step.2计算未知样本和每个训练样本的距离dist

step.3得到目前k个最邻近样本中的最大距离maxdist

step.4假使dist小于maxdist，则将该训练样本作为k-最近邻样本

step.5重复步骤2、3、4，直到未知样本和所有训练样本的距离都算完

step.6统计k-最近邻样本中每个类标号出现的次数

step.7选择出现频率最大的类标号作为未知样本的类标号

三、算法源代码

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//knn.cppk-最近邻分类算法//

////////////////////////////////////////////////////////////////////////////////////////////////////////#includestdlib.h#includestdio.h

#includememory.h#includestring.h

#includeiostream.h#includemath.h#includefstream.h

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//宏定义//

////////////////////////////////////////////////////////////////////////////////////////////////////////#defineattr_num4//属性数目

#definemax_size_of_training_set1000//训练数据集的最大大小#definemax_size_of_test_set100//测试数据集的最大大小#definemax_value10000.0//属性最大值#definek7//结构体

structdatavector{};

structdistancestruct{};

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//全局变量//

////////////////////////////////////////////////////////////////////////////////////////////////////////structdatavectorgtrainingset[max_size_of_training_set];//训练数据集structdatavectorgtestset[max_size_of_test_set];//测试数据集structdistancestructgnearestdistance[k];//k个最近邻距离intid;//id号doubledistance;//距离charclasslabel[15];//

分类标号intid;//id号charclasslabel[15];//分类标号doubleattributes[attr_num];//属性

intcurtrainingsetsize=0;//训练数据集的大小intcurtestsetsize=0;//测试数据集的大小

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//求vector1=(x1,x2,...,xn)和vector2=(y1,y2,...,yn)的欧几里德距离//

////////////////////////////////////////////////////////////////////////////////////////////////////////doubledistance(structdatavectorvector1,structdatavectorvector2){}

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//得到gnearestdistance中的最大距离，返回下标//

////////////////////////////////////////////////////////////////////////////////////////////////////////intgetmaxdistance(){}

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//对未知样本sample分类//

////////////////////////////////////////////////////////////////////////////////////////////////////////char*classify(structdatavectorsample){

doubledist=0;intmaxid=0,freq[k],i,tmpfreq=1;;char*curclasslable=gnearestdistance[0].classlabel;

memset(freq,1,sizeof(freq));//step.1初始化距离为最大值for(i=0;ik;i++)intmaxno=0;for(inti=1;ik;i++){}

if(gnearestdistance[i].distancegnearestdistance[maxno].distance)maxno=i;doubledist,sum=0.0;for(inti=0;iattr_num;i++){}dist=sqrt(sum);returndist;sum+=(vector1.attributes[i]-vector2.attributes[i])*(vector1.attributes[i]-vector2.attributes[i]);returnmaxno;

}{}//step.2计算k-最近邻距离for(i=0;icurtrainingsetsize;i++){}//step.3统计每个类出现的次数for(i=0;ik;i++){}//step.4选择出现频率最大的类标号for(i=0;ik;i++){}returncurclasslable;if(freq[i]tmpfreq){}tmpfreq=freq[i];

curclasslable=gnearestdistance[i].classlabel;for(intj=0;jk;j++){}

if((i!=j)(strcmp(gnearestdistance[i].classlabel,gnearestdistance[j].classlabel)==0)){}freq[i]+=1;//step.2.1计算未知样本和每个训练样本的距离dist=distance(gtrainingset[i],sample);//step.2.2得到gnearestdistance中的最大距离maxid=getmaxdistance();//step.2.3假使距离小于

gnearestdistance中的最大距离，则将该样本作为k-最近邻样本if(distgnearestdistance[maxid].distance){}gnearestdistance[maxid].id=gtrainingset[i].id;gnearestdistance[maxid].distance=dist;

strcpy(gnearestdistance[ma