KNN分类算法研究

KNN算法是应用最广泛的分类技术之一。文章简要介绍了KNN算法的基本原理,重点论述了研究人员针对KNN算法的不足所做的各种改进。主要从距离计算的改进、降低计算复杂度、K值的选择、与其它方法集成几个方面进行分析研究。     

公路网移动终端的KNN查询技术

公路网中移动兴趣点(POIs)的查询处理是一个难点,目前的研究多基于欧氏距离对静态POIs进行处理,不能很好地适应移动环境下终端弱连接和频繁移动的需要.文中在公路网移动计算场景下,设计了一种存储分区数据对象的结构来表示公路网图形模型,提出适用于移动终端的连续KNN查询(CQ-KNN)算法.该算法改进了Wang等提出的MKNN算法,将逐层渐近探测和检索边列表结合起来进行近邻查询,避免了MKNN算法在限定层数不够却不得不执行范围查询时所带来的开销;同时使用缓存策略来支持移动终端提交的连续查询请求,并给出基于广播位置失效报告的缓存一致性维护策略.仿真结果表明,CQ-KNN算法较MKNN算法有更快的CPU处理速度和更短的网络响应延时,并且能支持移动终端的离线KNN近似查询.     

分布式数据库系统中的查询优化

分布式数据库系统由于数据的分布和冗余使得分布式查询处理增加了许多新的内容和复杂性,因此分布式查询处理的优化显得尤为重要.本文简要介绍分布式查询优化的特点和目标,并针对分布式数据库系统的查询优化,讲述三个典型的算法:INGRES算法、System R*算法、SDD-1算法,并对SDD-1算法进行改进.     

一种采用过滤技术的Twig查询算法

提出一种采用过滤技术的Twig查询算法TwigFilter:通过设计一种过滤算法,过滤掉所有与查询结果无关的元素;给出一种查询算法,实现对过滤后剩余元素的快速查询.在不同数据集上实验证明,提出的算法对于提高Twig查询处理性能是有效的.     

KNN算法综述

KNN（K最近邻）分类算法是应用最为广泛的分类算法。本文介绍传统的KNN方法的基础上,根据其不足,从降低计算复杂度提高算法的执行效率,相似度度量方法,决策规则等几方面综述KNN改进算法。     

逃避攻击下恶意PDF文件检测技术

KNN(K近邻)算法以其操作简单、分类效果明显的优点被广泛应用于网络入侵检测、垃圾邮件识别和图像识别等领域。KNN算法通过计算测试集与训练集之间的相似度进行分类。传统的机器学习分类模型通常只考虑分类的精度,没有考虑到攻击者的攻击问题,导致当存在非法攻击时,分类模型的鲁棒性降低。对此首先通过使用逃避攻击方法实现对KNN算法在恶意PDF文件分类上的攻击,然后将攻击产生的对抗样本添加到训练集中训练出新的分类器,最后模拟两种不同攻击方式在不同攻击强度下对改进前后KNN分类器分类效果的影响。实验结果表明,通过将对抗样本添加到训练集中能够有效提高KNN分类器的鲁棒性。     

一种基于贪婪算法的KNN参数选择策略

K近邻算法是基于向量空间模型的最好的文本分类算法之一。使用KNN算法时通常要用贪婪算法进行参数选择，最终的参数不仅取决于每个参数的初始值及候选值，而且和参数选择的顺序密切相关。不同的参数选择策略间存在较大差异，通过实验，指出了KNN算法进行文本分类时一个较好的参数选择策略。     

基于XML Schema的Deep Web查询接口分类研究

Deep Web在线数据库蕴含大量的信息,但由于这些信息检索困难,利用率不高,本文提出一种基于XML Schema的查询接口分类方法,建立数据查询接口的XML Schema文档,通过各数据源名的语言学相似度实现查询接口的初次分类;根据查询接口标签属性,建立特征-接口向量空间模型实现查询接口向量化,再采用KNN算法进行二次分类,减少KNN算法分类带来的计算开销,提高Deep Web数据检索的效率。     

KNN认知诊断法及其应用

将机器学习中的KNN算法迁移至认知诊断评估中,提出了KNN认知诊断法,并通过模拟和实证研究考察了KNN认知诊断法的效果和特征.结果表明:KNN认知诊断法具有较高的判准率,与PNN和MDD-R诊断法不相上下,甚至在某些情境下更高;KNN认知诊断法不受样本容量和被试知识状态分布形态的影响,体现了KNN算法作为非参数方法的特征;KNN认知诊断法具有较好的实证信效度.     

基于BP改进的KNN算法在北京密云土地覆盖分类中的应用

针对k近邻(k-nearest neighbor,KNN)算法在土地覆盖分类中存在将山体阴影覆盖下植被误分成水体的问题,提出改进的KNN算法。改进算法充分利用神经网络能有效区分山体阴影覆盖下植被和水体的特性,实现BP神经网络与KNN算法的融合,整体提高了北京市密云区土地覆盖分类精度。实验结果表明:相对于支持向量机(support vector machine,SVM)、随机森林、BP神经网络和KNN算法,改进算法分类精度最高,达到了95.20%,分类精度比未改进KNN算法提高了6.43%。改进算法的Kappa系数在对比算法中也是最高的,达到0.93。此外,实验结果也表明改进算法可应用于中分辨率遥感图像分类中。     

分布式数据库中数据查询优化算法研究进展

分布式数据库中，数据的分散存放和冗余给故障恢复带来了方便，同时也使得分布式查询处理变得更加复杂，因此如何快速准确的查询用户想要的数据成了分布式数据库系统中的一个重要问题。介绍了分布式数据库的特点，详细阐述了常用的查询优化算法的思想，分析了优缺点，给出了算法选择的方法。     

面向不平衡数据集的一种改进的k-近邻分类器

心脏心律失常数据集的心电图(ECG)数据往往存在各心律失常类型下样本数量不平衡问题.针对此问题,提出了一种新的模式识别分类方法,即改进的基于核的差重建的加权k-近邻分类器(modified kernel difference-weighted k-nearest neighbor classifier, MKDF-WKNN),通过引入修正因子对含样本数较多的类别进行权值抑制,对含样本数较少的类别进行权值的加大,并使用UCI心脏心律失常数据集对ECG数据进行分类.实验结果表明,提出的算法和其他一些基于KNN的算法如KNN,DS-WKNN,DF-WKNN和KDF-WKNN相比,对于不平衡的心律失常数据集的分类有更好的效果.     

移动数据库中一种缓存策略

基于失效报告的广播技术在支持长时间断接操作中比较有效,但是对于两个失效报告间隔中提出的查询请求,需要等到下一失效报告广播后才能对其进行回复,造成查询的长时间延迟和不必要的带宽浪费.为解决这个问题,对经典的缓存算法进行改进,提出一种改进算法——低查询延迟缓存失效报告算法,并进行模拟试验,证明其在增加缓存命中率、减小查询延迟和增大系统吞吐量等方面的优越性.     

基于启发函数的网格数据库查询算法

查询处理技术是网格数据库研究的核心,但是传统的查询处理技术无法适应动态变化的网格环境,导致网格资源利用率低、查询效率不高。给出了基于副本的网格数据库查询处理代价模型和两种查询处理算法,利用不同的数据集和网格环境参数进行实验验证。实验结果表明,基于启发函数的网格数据库查询算法在一定程度上提高了查询处理效率,生成子查询时间代价为O(n),消耗时间比采用穷举策略下降10%左右。     

基于最大熵的文本分类算法的改进

基于最大熵模型的文本分类算法对不同测试文档的训练结果相差较大.利用Boosting机制改进基于最大熵模型的分类算法,以提高该分类算法的稳定性.实验结果表明,该改进方法可以有效改善基于最大熵模型分类算法的稳定性,且分类精度也有一定的提高.     

WEB日志中基于KNN算法的注入式攻击行为检测方法研究

阐述了注入式攻击及KNN算法的相关概念并探讨了注入式攻击行为检测与文本分类技术的关系.结合KNN算法的优点及注入式攻击行为检测与文本分类的相似性,提出了Web日志中基于KNN算法的注入式攻击检测方法,给出了其计算模型,并进行了检测对此.结果表明,该方法具有良好的检测准确度.     

Processing Constrained K Closest Pairs Query in Spatial Databases

In this paper, constrained K closest pairs query is introduced, wbich retrieves the K closest pairs satisfying the given spatial constraint from two datasets. For data sets indexed by R trees in spatial databases, three algorithms are presented for answering this kind of query. Among of them, two-phase Range＋Join and Join＋Range algorithms adopt the strategy that changes the execution order of range and closest pairs queries, and constrained heap-based algorithm utilizes extended distance functions to prune search space and minimize the pruning distance. Experimental results show that constrained heap-base algorithm has better applicability and performance than two-phase algorithms.     

一种基于XML分析的Deep Web查询接口分类研究

Deep Web查询接口分类是实现Deep Web在线数据库分类访问的主要方法,本文在研究查询接口特征数据抽取和表示的基础上,通过对查询接口所在Web页的位置来构建对应的接口特征XML文档,根据XML文档中的节点位置不同,分别为不同的查询接口特征赋予不同的分类权重因子,以提高有效特征的分类能力,并采用信息增益算法实现最终分类特征的选择,然后采用KNN分类算法实现查询接口分类,实验结果表明此方法的实际可行性.     

MapReduce框架下k-支配轮廓查询算法

随着维度和数据量的不断增长,已有的轮廓查询方法已无法为用户提供更好的查询支持.本文采用并行处理框架MapReduce 结合k-支配轮廓查询算法来解决此类查询问题.在对输入的数据集进行预排序的基础上,提出了基于MapReduce 的单轮扫描算法和双轮扫描算法,通过在不同维度、数据分布、节点个数等方面的实验测试及对比,验证了算法的有效性.