参考点k近邻分类算法的改进及其MPI并行化

发布时间：2024-05-12 23:06

　　k近邻算法(k-Nearest Neighbors,kNN)是一种基于统计的经典分类方法,具有算法简洁、分类准确性较高和无需先验统计知识等特点,目前已成为数据挖掘领域中广泛研究与应用的算法之一。本文在分析现有k近邻算法的基础上,主要开展对k近邻算法的改进与并行化研究。传统k近邻分类算法具有二次方时间复杂度,为了提高分类速度,一类方法通过构造树型索引结构以加快k近邻查找,但是基于树型k近邻算法随着数据集维度增加其分类性能会变差;另一类方法则通过查找近似近邻而避免精确近邻的大量计算,其中基于参考点k近邻算法对各类数据集均具有较高的分类效率,但分类精度相对于传统k近邻算法仍有较大损失,针对该问题,本文提出一种改进的参考点k近邻分类算法,其时间复杂度为O(nlogn)。本文考虑到训练样本的空间分布特征,根据到样本距离的方差改善参考点的选取,并在查找近邻样本时依据参考点所起不同作用而赋予参考点自适应权重。通过在公开与人工数据集上实验,验证了本文算法具有较高的分类效率,相比于现有参考点k近邻算法获得了更好的分类精度。为了解决单机环境下大规模数据分类存在计算性能弱、内存消耗高与扩展性差等问题,提出了...

【文章页数】：70 页

【学位级别】：硕士

【部分图文】：

图3.2两个参考点根据样本与数据集的分布情况获取自适应权重

考点找到x的近邻样本均具有相同标签，此时说明x可能处于相同标签的数据集中，可给该参考点设置较小权重。从欧式空间来看，参考点的权重越大，由该参考点所找到的近邻样本子序列的长度越大。如图3.2所示，x1和x2是待分类样本，由参考点O1所找到x1的一定数量（如2k个）近邻样本均具有相同....

图4.4DPkNN算法的示意图

士学位论文第4章改进算法的各个分类任务之间在计算顺序上并不存在相关性，因此可采待分类数据集及相应的分类操作平均分配给多个计算节点并DPkNN算法。....

图4.5PkN同样的，由于没有涉及到具体何种算法适用于所有k近邻算法的并行化

重庆邮电大学硕士学位论文到的k个距离和标签，按照距离较小的并将更新后的k个距离及标签传递给下类操作。待分类集未知样本x

图5.3数字8的训练样本

(b)系统的整体类框图图5.2UML类图统中各k近邻算法的类图，由于一个名为Classifier的抽象父类MainFrame是用于展示图形界面er类用于载入训练集，Drawing用户所输入字符的数组表示。一个行列均为32的文本文件，使8的文本表示，....

本文编号：3972025