面向申威架构的KNN并行算法实现与优化

K近邻(KNN)是人工智能中最常用的分类算法,其性能提升对于海量数据的整理分析、大数据分类等任务具有重要意义。目前新一代神威超级计算机正处于应用发展的初始阶段,结合新一代申威异构众核处理器的结构特性,充分利用庞大的计算资源实现高效的KNN算法是海量数据分析整理的现实需求。根据SW26010pro处理器的结构特性,采用主从加速编程模型实现一种基础版本的KNN并行算法,其将计算核心传输到从核上,实现了线程级并行。分析影响基础并行算法性能的关键因素并提出优化算法SWKNN,不同于基础并行KNN算法的任务划分方式,SWKNN采用任务重划分策略,以避免冗余计算开销。通过数据流水优化、从核间通信优化、二次负载均衡优化等步骤减少不必要的通信开销,从而有效缓解访存压力并进一步提升算法性能。实验结果表明,与串行KNN算法相比,面向申威架构的基础并行KNN算法在SW26010pro处理器的单核组上可以获得最高48倍的加速效果,在同等数据规模下,SWKNN算法较基础并行KNN算法又可以获得最高399倍的加速效果。

基于改进K-means聚类和遗传算法的混合算法求解异构车辆路径问题

由于目前单一车型配送存在资源浪费和效率低下等问题,选取确定数量的不同车型对各客户点进行配送服务往往可以得到更优的配送路径方案。针对这一点,描述了一种异构车辆路径问题,并建立了具有固定车辆数且考虑固定成本、可变成本以及时间窗惩罚成本的混合整数规划模型。同时,提出了一种基于改进K-means聚类和遗传算法的混合算法对模型进行求解。实验仿真先求解不考虑时间窗的问题初步证明混合算法的有效性,再在带时间窗的问题中求解不同规模算例的单一及异构车型结果,以证明异构车型配送更优。最后,对该混合算法的求解结果与其他混合算法的求解结果进行对比分析,证明了混合算法的优越性。研究结果表明:该混合算法求解的异构车型结果优于单一车型,并且比其他混合算法求解的异构车型结果更优,异构车辆配送使用的配送车辆数更少,总成本也更低,该混合算法具有更好的效率和性能。

基于K-means聚类与集成学习算法的小流域山洪灾害易发性评估

为了更好地分析空间异质性对山洪灾害易发性评估的影响,建立了基于K-means聚类与集成学习算法的小流域山洪灾害易发性评估模型。首先,选取中国江西省12338个小流域为研究区,对各时段不同频率降雨量指标进行K-means聚类。其次,以误差平方和与平均轮廓系数为聚类效果评价指标,将小流域分为2个类内聚集、类外分散的子集。最后,针对不同子集,从几何特征、环境特征以及降水特征3个方面选取平均坡度、形心高程、形状系数、最长汇流路径比降、地形湿度指数、归一化植被指数、距离河流最近距离、降雨量、洪峰模数以及汇流时间10个山洪影响因素,应用自适应增强算法与极致梯度提升算法进行山洪灾害易发性评估。研究发现,降水是导致山洪灾害的重要因素,江西省高降水区域山洪灾害易发程度普遍高于低降水区,同时省内高风险区分布较为分散,主要分布在东北区域与西北边缘区域。对聚类后两类相似小流域分别进行山洪易发性评估,接受者操作特征曲线下面积值均在0.90以上,精度较聚类前有所提高。聚类策略作为易发性评估模型的前驱过程,可以有效解决小流域异质性问题。

基于k-NN模型的钢坯入炉温度预测

在中厚板生产中,加热工序是决定后续轧制过程是否稳定的重要环节。同时为了提高经济效益,实现节能减排,加热工序往往会根据原料本身的温度情况来制定相应的加热工艺。换热系数是建立钢坯温降计算模型的核心参数,由于其影响因素繁多且复杂,很难有一个固定的模型来计算。本文提出一种简单有效的基于k-NN算法的温度预测模型,寻找目标钢坯与样本钢坯之间的相似度,然后通过IDW加权平均算法,预估出目标钢坯的入炉温度。实际应用表明,模型预测温度与实测温度绝对误差控制在30℃以内的占比达95%以上。

一种新的证据K-NN数据分类算法

K近邻分类算法已被广泛应用于模式识别中。为了有效处理识别问题中的不确定信息并提高数据分类精度,提出了一种新的证据K-NN(NEK-NN)分类算法。首先从总的训练集中随机重复采样来构造多个训练样本子集。在每个训练子集中,利用目标数据与其各个近邻的距离分别构造基本置信指派,并根据K个近邻数据在每个类别中的数目来对构造的置信指派进行加权。然后,利用DS规则对加权证据融合。根据每个训练子集下融合结果的算术平均值来判断目标的类别属性。通过模拟数据集和真实数据集的实验,将NEK-NN算法与其他几种常见的方法做了对比分析,结果表明NEK-NN算法能够有效地提高分类的精度。

基于N次K-NN分类算法的管道机器人定位技术研究

分析了低频电磁波在均匀介质中的磁场分布,其分布与介质的介电常数、磁导率密切相关.根据管道机器人定位的实际工程需要,给出了三传感器低频电磁波定位模型.为了减小传输介质介电常数、磁导率参数对管道机器人定位的影响,提出了N次K-NN分类算法.实验结果表明,该算法分类的正确率可达97.5%,定位精度可达±10 cm,在传输介质介电常数、磁导率等参数不确定条件下,可有效地求解低频电磁波发射源的位置参数.

基于k-NN和Landsat数据的小面积统计单元森林蓄积估测方法

基于吉林省一个试验区的森林资源一类清查固定样地数据、Landsat TM数据和土地利用数据,采用精度交叉评价方法研究了k-最近邻(k-NN)法用于小面积统计单元森林蓄积估计的有效性。结果表明:k-NN方法对样地覆盖区影像像元单位面积蓄积量的估测平均误差在1.5 m3.hm2之内,相对均方根误差(RMSE′)低于传统的基于绿度指数的线性方程估测方法;采用k-NN方法可以实现县市级统计单元的参数估计,估测效果优于只利用固定样地数据的传统成数估计方法。

基于KNN离群点检测和随机森林的多层入侵检测方法

入侵检测系统能够有效地检测网络中异常的攻击行为,对网络安全至关重要.目前,许多入侵检测方法对攻击行为Probe(probing),U2R(user to root),R2L(remote to local)的检测率比较低.基于这一问题,提出一种新的混合多层次入侵检测模型,检测正常和异常的网络行为.该模型首先应用KNN(K nearest neighbors)离群点检测算法来检测并删除离群数据,从而得到一个小规模和高质量的训练数据集;接下来,结合网络流量的相似性,提出一种类别检测划分方法,该方法避免了异常行为在检测过程中的相互干扰,尤其是对小流量攻击行为的检测;结合这种划分方法,构建多层次的随机森林模型来检测网络异常行为,提高了网络攻击行为的检测效果.流行的数据集KDD(knowledge discovery and data mining) Cup 1999被用来评估所提出的模型.通过与其他算法进行对比,该方法的准确率和检测率要明显优于其他算法,并且能有效地检测Probe,U2R,R2L这3种攻击类型.

用于大数据分类的KNN算法研究

针对KNN算法在处理大数据时的两个不足对其进行了研究,提出多层差分KNN算法。算法对已知样本根据类域进行分层,既避免了传统改进算法中剪辑样本带来的判别误差,又大大降低了无效的计算量;同时在最后一层采用差分的方法进行决策,而不是直接根据最近邻进行分类,大大提高了分类的准确性。实验结果表明,该算法在对样本容量大、涉及邻域多的大数据样本进行分类时能取得较好的分类效果。

一种基于k-NN的案例相似度权重调整算法

对于CBR中的案例检索问题,结合经典案例相似度计算方法,对目前在各实际系统中应用最为广泛的k-NN算法进行改进。经过特征约简,在假设时间因素对历史案例可采纳程度有显著影响基础上,提出了一种小规模的基于时序的案例特征权重多阶段调整算法。该算法适用于数值型特征项相似度计算。

一种模糊-证据kNN分类方法

已有的以k-最近邻(kNearest Neighbor,kNN)规则为核心的分类算法,如模糊kNN(FuzzykNN,FkNN)和证据kNN(EvidentialkNN,EkNN)等,存在着两个问题:无法区别出样本特征的差异以及忽略了邻居距训练样本类中心距离的不同所带来的影响.为此,本文提出一种模糊-证据kNN算法.首先,利用特征的模糊熵值确定每个特征的权重,基于加权欧氏距离选取k个邻居;然后,利用邻居的信息熵区别对待邻居并结合FkNN在表示信息和EkNN在融合决策方面的优势,采取先模糊化再融合的方法确定待分类样本的类别.本文的方法在UCI标准数据集上进行了测试,结果表明该方法优于已有算法.

PSO/KNN算法及其在模拟故障诊断中的应用研究

提出了一种基于粒子群优化(particle swarm optimization,PSO)的特征提取算法,该算法以K-NN(nearest neighbor)分类正确率为评价准则,应用粒子群优化算法寻找使提取特征的K-NN分类正确率最大的转换矩阵,从而实现特征的提取。算法的特点是结构简单灵活,对数据的分布特征不敏感,适合于对模拟电路的故障特征进行提取。电路故障诊断示例证明了该特征提取算法在模拟电路故障诊断中的有效性。

一种基于信息增益的K-NN改进算法

针对传统K-NN算法易受单个属性干扰和时间效率较低的问题,提出了利用信息增益和可拓关联度对其进行改进。通过计算属性的信息增益来确定属性的权重系数,根据权重系数将属性划分为关键属性、次要属性和无关属性,在计算欧氏距离时引入权重系数,使各个属性的作用受其重要性的约束,有效地提高了K-NN算法的抗干扰能力和精确性。将属性空间划分为若干个子空间,利用可拓关联度将待测样本映射到某个子空间中,由这个子空间组成搜索空间,减少计算量,提高时间效率;测试结果表明,改进后的算法可行有效。

一种无线传感器网络中的多维K-NN查询优化算法(英文)

提出了一种基于过滤器的无线传感器网络多维K-NN查询优化算法PREDICTOR.过滤器是设置在节点端的取值分布区间,用来屏蔽节点发送属于区间内的数据,从而节省节点能耗.在服务器端保存有各节点的历史样本数据,根据K-NN查询请求和样本数据的分布范围为节点定义过滤器.提出了3种优化策略:(1)过滤器覆盖区间大小分配策略的动态调整方法,使得进入最终查询结果可能性小的节点拥有较大的覆盖区间;(2)节点间过滤器共享方法,使得历史样本数据相近的节点使用相同的过滤器;(3)过滤器压缩传输方法,减少为不同K-NN查询更新过滤器的代价.通过实验评价,验证了PREDICTOR算法的能量有效性,与朴素算法相比,极大地降低了数据传输量.

一种k-NN文本分类器的改进方法

自动文本分类是提高信息利用效率和质量的有效方法。训练文本分布的不均匀会对分类的效果产生负面影响，而在实际中，很难使训练文本的分布达到均匀。针对这一问题，提出了一种改进的k-NN文本分类方法。通过在英文和中文两个文本集的实验表明，改进后的方法不仅分类的准确性有了提高，而且表现出较好的稳定性。

k-nn方法在热带气旋路径预报中的应用

引入k nn方法 ,结合经过预报实践检验、应用证明效果较好的预报因子 ,制作热带气旋路径预报系统 ,运行效果良好 ,可以应用到日常预报业务中。

基于MPI的ML-kNN算法并行

基于MPI将ML-kNN算法并行化,以解决多标签学习领域中的大规模分类问题,控制计算的时间开销,这也是首次将MPI应用到多标签学习领域.通过与传统的串行ML-kNN的对比实验,验证了所提方法的可行性和有效性.另外,允许数据集以特征为单位划分,这使得该方法在处理高维数据时具有更大的优势.

基于k-NN和SCATS交通数据的路段行程时间估计方法

为了改善利用SCATS交通数据估计路段行程时间的效果,通过分析SCATS实际交通数据获取时间间隔不一致的特征,构建了SCATS交通数据虚拟时间序列,将利用因子分析法提取的累计贡献率在85%以上的主因子作为交通模式特征向量的构成要素,用欧氏距离作为当前交通模式特征向量和历史交通模式特征向量相似性的测度指标,以路段行程时间估计误差最小为目标选取当前交通模式的近邻数,对交通模式之间距离的倒数进行归一化处理,确定了相似交通模式的行程时间权重,设计了基于SCATS交通数据的路段行程时间估计方法.实例结果表明:与多元线性回归方法相比,本文方法估计的路段行程时间平均绝对误差、平均绝对百分比误差和均方根误差分别平均减少了9.68 s、8.07%和4.5 s.

一种优化的k-NN文本分类算法

k-NN是经典的文本分类算法之一,在解决概念漂移问题上尤其具有优势,但其运行速度低下的缺点也非常严重,为此它通常借助特征选择降维方法来避免维度灾难、提高运行效率。但特征选择又会引起信息丢失等问题,不利于分类系统整体性能的提高。从文本向量的稀疏性特点出发,对传统的k-NN算法进行了诸多优化。优化算法简化了欧氏距离分类模型,大大降低了系统的运算开销,使运行效率有了质的提高。此外,优化算法还舍弃了特征选择预处理过程,从而可以完全避免因特征选择而引起的诸多不利问题,其分类性能也远远超出了普通k-NN。实验显示,优化算法在性能与效率双方面都有非常优秀的表现,它为传统的k-NN算法注入了新的活力,并可以在解决概念漂移等问题上发挥更大的作用。

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索,进行这些查询用到的算法与位置和范围查询的算法不同,需要专门进行研究。介绍了一种分支界限遍历R树算法,并将该算法概括为k-NN算法。文中讨论了两种方法,对R树进行结点内MBR的排序以及剪枝过程,以减少搜索空间中需访问结点的数量,有效地进行k-NN搜索。