论文部分内容阅读
摘 要：KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
关键词：KNN；数据挖掘；模型建立
一、实验选择模型
（一）实验模型选择
基于KNN算法——重量距离的权衡。
（二）实验背景
该数据集是基于西格勒的天平问题实验，主要目的是为了考察儿童解决问题的年龄差异。该数据集仅列举了判断的事物：物体的重力，左力臂，右力臂，以及结果是最该实验中的规则一：如果两边重量相等，将预测天平保持平衡。如果重量不同，预测重的那边会下降。规则二：如果天平边较重，将预测这一边会下降；如果两边重量相等，距离支点较远的那一一边会下降。规则三：如果两边重量和距离相等，预测天平将保反应：持平衡；如果一边更重或更远，而在另一个维度上两边则三，相等，将预测更重或更远的那一边会下降；如果一边更言语指重面另一边更远，儿童就会糊涂，或者只是猜测。规则四：是规则3的进一步发展，即一边更重，而者的5另一边更远的情况下，通过计算重量乘以距离算出每一使用了边的力矩，并预测力矩大的那一边会下降。
二、实验内容
（一）数据分析
数据集内容解释：此数据集是为了建立心理模型而生成的实验结果。每一行数据结果都被分类为天平向右倾斜，向左倾斜，或者保持平衡。划分类别的方法是（左距*左重量）和（右距*右重量）。如果它们相等，它就是平衡的，否则那边大就偏向哪边。
数据清洗：第一行数据：1，，1，1，R为空缺值，根据同类样本（r2-r5）推测为1。
r2：1，1，1，2，R r3：1，1，1，3，r4 ：1，1，1，4，R r5 ：1，1，1，5，R。
第179行数据：6 3，1，4，L，超出范围为噪声，直接删除其他的数据没有空缺值，数据都平滑，都是离散的点，没有孤立点。
算法分析：a.因为KNN算法所依据的是计算出的距离，所以需要方法来计算距離，我们所选用的是欧式距离。
设原始数据为：
欧式距离：
b.先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。
（二）数据的属性数据属性分析及选择
属性：左重量、左距离、右重量和右距离。
属性数量：4（数字）+类名=5。
属性信息：
（1）类名：3（L（偏左），B（平衡），R（偏右））。
（2）左重：5（1、2、3、4、5）。
（3）左距离：5（1、2、3、4、5）。
（4）右重量：5（1、2、3、4、5）。
（5）右距离：5（1、2、3、4、5）。
D.选择原则及结果：所选择属性都有明确的属性名，属性值。都为唯一属性，都不可忽略，没有重复属性。
三、模型建立及代码实现
（一）选择模型
通过对大量已知数据分类和调整以及对数据集的清理与填充后整合的数据集后，我们采用KNN算法模型进行模型建立。KNN又称为K-临近算法是一种有指导（监督）的学习。
（二）工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据及中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
（三）算法实现
（1）通过类的默认构造函数去初始化训练数据集dataSet和测试数据testData。
（2）用get_distance（ ）来计算测试数据testData和每一个训练数据dataSet[index]的距离，用map_index_dis来保存键值对，其中index代表第几个训练数据，distance代表第index个训练数据和测试数据的距离。
（3）将map_index_dis按照value值（即distance值）从小到大的顺序排序，然后取前k个最小的value值，用map_label_freq来记录每一个类标签出现的频率。
（4）遍历map_label_freq中的value值，返回value最大的那个key值，就是测试数据属于的类。
四、模型评估及参数调整
（一）模型评估对象
（1）数据：选取了200行清洗过的数据。
（2）数据挖掘模型：KNN。
（3）检验：使用另外提供的检验集实例进行检验，即按照分类的属性来选取测试数据进行检验与测试。
（二）评估方法
评估分类类型输出模型 ，检验集分类正确率。
（三）参数调整
选取一个K值，然后输入不同类型的测试数据进行测试依次检验测试的结果是否与本身所属的类别一致。进行多次检验增加实验的精准度与准确率。
（四）测试代码检验正确率
选取合适的K值：一般来说，我们只选择样本数据及中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。本次测试是以k=5为例进行的。
输入分类器的value值K=5。
test data1：4 5 2 1。
因为需要计算每一个数据集与测试数据之间的距离，有200行因此不过多显示，只截取一部分，下图为本次测试数据的结果截图，其分类结果为L（向左倾斜）分类正确。
五、小结
从上面的例子就可以看出，分类结果的正确性可以通过本身归类来判断，可以看出结果都是正确的。数据集事先已有了分类和特征值，待收到新样本后直接进行处理。
KNN的时间复杂度为O（n），因此KNN一般适用于样本数较少的数据集k取不同值时，当k取不同的值时，分类结果可能会有显著不同。
经过分析实验和测试后可以大致对KNN模型的优缺点进行了一些分析：
（一）优点
（1）思想简单，理论成熟，既可以用来做分类也可以用来做回归；
（2）可用于非线性分类；
（3）训练时间复杂度为O（n）；
（4）准确度高，对数据没有假设。
（二）缺点
（1）计算量大；
（2）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
（3）需要大量的内存；
（三）改进
对距离加权，可以降低k值设定的影响。
参考文献：
[1]陈安，陈宁，周龙骧等.数据挖掘技术及应用[M].北京：科学出版社，2006：9-12，146-156.
[2]谈恒贵，王文杰，李游华.数据挖掘分类算法综述[J].微机型与应用，2005：2.
作者简介：王新宇（1997—），男，汉族，河南信阳人，2015级本科生，主要研究方向：计算机科学与技术。
关键词：KNN；数据挖掘；模型建立
一、实验选择模型
（一）实验模型选择
基于KNN算法——重量距离的权衡。
（二）实验背景
该数据集是基于西格勒的天平问题实验，主要目的是为了考察儿童解决问题的年龄差异。该数据集仅列举了判断的事物：物体的重力，左力臂，右力臂，以及结果是最该实验中的规则一：如果两边重量相等，将预测天平保持平衡。如果重量不同，预测重的那边会下降。规则二：如果天平边较重，将预测这一边会下降；如果两边重量相等，距离支点较远的那一一边会下降。规则三：如果两边重量和距离相等，预测天平将保反应：持平衡；如果一边更重或更远，而在另一个维度上两边则三，相等，将预测更重或更远的那一边会下降；如果一边更言语指重面另一边更远，儿童就会糊涂，或者只是猜测。规则四：是规则3的进一步发展，即一边更重，而者的5另一边更远的情况下，通过计算重量乘以距离算出每一使用了边的力矩，并预测力矩大的那一边会下降。
二、实验内容
（一）数据分析
数据集内容解释：此数据集是为了建立心理模型而生成的实验结果。每一行数据结果都被分类为天平向右倾斜，向左倾斜，或者保持平衡。划分类别的方法是（左距*左重量）和（右距*右重量）。如果它们相等，它就是平衡的，否则那边大就偏向哪边。
数据清洗：第一行数据：1，，1，1，R为空缺值，根据同类样本（r2-r5）推测为1。
r2：1，1，1，2，R r3：1，1，1，3，r4 ：1，1，1，4，R r5 ：1，1，1，5，R。
第179行数据：6 3，1，4，L，超出范围为噪声，直接删除其他的数据没有空缺值，数据都平滑，都是离散的点，没有孤立点。
算法分析：a.因为KNN算法所依据的是计算出的距离，所以需要方法来计算距離，我们所选用的是欧式距离。
设原始数据为：
欧式距离：
b.先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。
（二）数据的属性数据属性分析及选择
属性：左重量、左距离、右重量和右距离。
属性数量：4（数字）+类名=5。
属性信息：
（1）类名：3（L（偏左），B（平衡），R（偏右））。
（2）左重：5（1、2、3、4、5）。
（3）左距离：5（1、2、3、4、5）。
（4）右重量：5（1、2、3、4、5）。
（5）右距离：5（1、2、3、4、5）。
D.选择原则及结果：所选择属性都有明确的属性名，属性值。都为唯一属性，都不可忽略，没有重复属性。
三、模型建立及代码实现
（一）选择模型
通过对大量已知数据分类和调整以及对数据集的清理与填充后整合的数据集后，我们采用KNN算法模型进行模型建立。KNN又称为K-临近算法是一种有指导（监督）的学习。
（二）工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据及中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
（三）算法实现
（1）通过类的默认构造函数去初始化训练数据集dataSet和测试数据testData。
（2）用get_distance（ ）来计算测试数据testData和每一个训练数据dataSet[index]的距离，用map_index_dis来保存键值对
（3）将map_index_dis按照value值（即distance值）从小到大的顺序排序，然后取前k个最小的value值，用map_label_freq来记录每一个类标签出现的频率。
（4）遍历map_label_freq中的value值，返回value最大的那个key值，就是测试数据属于的类。
四、模型评估及参数调整
（一）模型评估对象
（1）数据：选取了200行清洗过的数据。
（2）数据挖掘模型：KNN。
（3）检验：使用另外提供的检验集实例进行检验，即按照分类的属性来选取测试数据进行检验与测试。
（二）评估方法
评估分类类型输出模型 ，检验集分类正确率。
（三）参数调整
选取一个K值，然后输入不同类型的测试数据进行测试依次检验测试的结果是否与本身所属的类别一致。进行多次检验增加实验的精准度与准确率。
（四）测试代码检验正确率
选取合适的K值：一般来说，我们只选择样本数据及中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k选择不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。本次测试是以k=5为例进行的。
输入分类器的value值K=5。
test data1：4 5 2 1。
因为需要计算每一个数据集与测试数据之间的距离，有200行因此不过多显示，只截取一部分，下图为本次测试数据的结果截图，其分类结果为L（向左倾斜）分类正确。
五、小结
从上面的例子就可以看出，分类结果的正确性可以通过本身归类来判断，可以看出结果都是正确的。数据集事先已有了分类和特征值，待收到新样本后直接进行处理。
KNN的时间复杂度为O（n），因此KNN一般适用于样本数较少的数据集k取不同值时，当k取不同的值时，分类结果可能会有显著不同。
经过分析实验和测试后可以大致对KNN模型的优缺点进行了一些分析：
（一）优点
（1）思想简单，理论成熟，既可以用来做分类也可以用来做回归；
（2）可用于非线性分类；
（3）训练时间复杂度为O（n）；
（4）准确度高，对数据没有假设。
（二）缺点
（1）计算量大；
（2）样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
（3）需要大量的内存；
（三）改进
对距离加权，可以降低k值设定的影响。
参考文献：
[1]陈安，陈宁，周龙骧等.数据挖掘技术及应用[M].北京：科学出版社，2006：9-12，146-156.
[2]谈恒贵，王文杰，李游华.数据挖掘分类算法综述[J].微机型与应用，2005：2.
作者简介：王新宇（1997—），男，汉族，河南信阳人，2015级本科生，主要研究方向：计算机科学与技术。