2024年数据挖掘实验报告.doc

数据挖掘试验汇报

——K-最临近分类算法

學号：姓名：汪文娟

数据源阐明

1.数据理解

选择第二包数据IrisDataSet，共有150组数据,考虑到训练数据集的随机性和多样性，选择rowNo模3不等于0的100组作為训练数据集，剩余的50组做测试数据集。

每组数据有5個属性，分别是：1.sepallengthincm

2.sepalwrowNothincm

3.petallengthincm

4.petalwrowNothincm

5.class:

--IrisSetosa

--IrisVersicolour

--IrisVirginica

為了操作以便，對各组数据添加rowNo属性,且第一组rowNo=1。

2.数据清理

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

缺失值：當数据中存在缺失值是，忽视该元组（注意：本文选用的第二组数据IrisDataSet的MissingAttributeValues:None）。

噪声数据：本文暂没考虑。

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）的欧几裏德距离是：

未知样本被分派到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

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