2.2　基于k近邻算法的实现

kNN属于非参数估计算法，为了将数据进行分类，需要先得到类条件概率密度，然后根据概率密度大小对样本进行分类。下面我们对给出的鱼类数据，分别利用直方图估计、Parzen矩形窗估计和Parzen正态核估计实现kNN分类。

给出的鱼类数据存储在文件fish.xls中，包含一维数据和二维数据两种类型，各2000条，一维数据的前6条数据如表2-1所示。

二维数据的前6条数据如表2-2所示。

2.2.1　利用直方图估计概率密度、分类

读取文件中的数据，将数据分成训练集和测试集之后，利用直方图估计法对数据进行分类的算法实现可分为以下步骤：

步骤01　根据数据的最小值和最大值及窗口大小确定将数据划分为多少区间。

步骤02　根据测试集样本newData确定该样本所在的窗口。

步骤03　统计测试样本所在窗口中不同类别的训练样本数量k0和k1。

步骤04　求出每类样本的概率密度并进行比较，将该测试样本newData划为概率密度较大的一类。

步骤05　重复执行步骤步骤01～步骤04，直到所有测试样本都完成分类。

步骤06　统计预测的分类与真实的类别，求出分类的准确率。

1.数据预处理

从fish.xls中读取数据，分别取出类别0和类别1的500条数据作为训练集，第500～1000之间的500条和1500条以后的500条数据作为测试集。

2.直方图概率密度估计

设置窗口大小v，求出训练集中样本的最大值max0和最小值min0，计算训练集被划分为多少个区间bin。对每一条测试数据newData，先以newData为中心确定其所处的区间bin0，然后统计训练集中各个类别有多少样本点落在bin0中，估计概率密度值。

3.对测试样本分类

比较窗口内分别属于类别0和类别1的概率大小，将测试样本newData划分为概率值较大的一类，并计算分类的准确率。

对每一个测试样本分类完成后，在窗口大小为0.5时，统计分类正确性为：0.972和0.970，可作为kNN算法的准确率。

4.数据可视化

在实现分类之前，可以通过将数据可视化观察两类数据的分布情况。

这两类数据的分布情况如图2-3所示。

为了将直方图概率密度可视化，就是将每个区域间的数据概率以直方图形式显示出来，因此，需要首先统计出训练集中每个区域内的样本数，并计算出概率值。我们分别设置窗口为v=0.3和v=1.0，以对比不同窗口大小情况下的概率密度显示效果和分类准确率。

窗口大小为0.3和1.0时，直方图概率密度如图2-4所示。

2.2.2　利用Parzen矩形窗估计概率密度、分类

与直方图密度估计类似，利用Parzen矩形窗公式可以实现对概率密度的估计及分类，以下是核心代码：

Parzen矩形窗概率密度估计可视化算法实现如下：

两类数据的概率密度如图2-5所示。

当窗口大小为3.0时，两类数据分类的正确率分别是0.972和0.968。

2.2.3　利用Parzen正态核估计概率密度、分类

如前所述，将核函数 K （ x , x _i ）设为标准正态分布，即：

修改2.2.2节代码，可分别得到测试样本属于两类数据的概率，其核心代码如下：

当窗口大小为1.0时，Parzen正态核估计概率密度如图2-6所示。

窗口大小为1.0时，两类数据分类正确率分别为0.972和0.968。