基于支持向量机与反K近邻的分类算法研究

针对支持向量机在对样本进行分类时,决策超平面附近的点较易错分的问题,首先将反K近邻法引入分类问题,提出了反K近邻分类算法;然后,将支持向量机(SVM)与反K近邻分类算法(RKNN)相结合,提出了基于支持向量机与反K近邻的分类算法(SVM-RKNN);最后,为了避免单一分类器可能存在的片面性问题,提出了基于SVM-RKNN的多特征融合分类方法。实验结果表明:SVM-RKNN分类算法的分类准确率比SVM方法平均提高了2.13%,而基于SVM-RKNN的多特征融合分类算法的分类准确率分别比SVM和SVM-RKNN算法平均提高了2.54%和0.41%。

基于反向K近邻的孤立点检测算法

提出了基于反向K近邻(RKNN)的孤立点检测算法ODRKNN。ODRKNN算法用每个数据点的反向K近邻个数来衡量该数据点的偏离程度,在综合数据集和真实数据集上的实验结果表明,该算法能有效地检测出孤立点,且算法的效率高于算法LOF和LSC的效率。

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.

高维主存的反向K最近邻查询及连接

对高维主存的反向K最近邻(KNN)查询进行研究,提出一种△-RdKNN-tree索引结构。通过在该索引结构上进行主存KNN自连接,预处理数据集中点的KNN距离信息。将这些距离扩展到索引的各层节点中,基于该索引设计高维主存的反向KNN查询算法以及反向KNN连接算法。分析结果表明,该算法在高维空间中是有效的。

路网中连续反向k近邻查询处理

现存的反向k近邻查询方案中,比较高效地研究大多集中在欧式空间,对于路网中的反向k近邻查询的研究相对较少。针对这一问题,考虑路网中移动查询点和移动数据对象的移动性,选用PMR四叉树来索引路网,基于安全区的概念提出一种反向k近邻(RkNN)查询算法,通过监控查询点和移动对象的安全区来处理路网更新。基于"初始化-维护更新"框架,采用Dijkstra搜索策略,设置验证监控区域来判定候选对象解的真假性。为了减少网络搜寻的工作量,提出了一系列剪枝规则来削减搜索空间。实验结果表明,该算法适用于路网中k值不固定的连续RkNN查询。

基于局部密度的快速离群点检测算法

已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测,INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题,但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题。针对该问题,提出局部密度离群点检测算法——LDBO,引入强k近邻点和弱k近邻点概念,通过分析邻近数据点的离群相关性,对数据点区别对待;并提出数据点离群性预判断策略,尽可能避免不必要的反向k近邻分析,有效提高数据分布异常情况离群点检测算法的效率。理论分析和实验结果表明,LDBO算法效率优于INFLO,算法是有效可行的。

基于反向k近邻过滤异常的群数据异常检测

针对无数据标签的群数据异常检测问题,提出在无监督模式下利用k最近邻(kNN)算法检测群数据异常.为减少由于异常值与正常值之间相互干扰而产生的漏报和误报,提出用反向k近邻(RkNN)算法对异常群数据进行反向过滤.反向k近邻算法首先将统计距离作为不同群数据间的相似性度量,再用kNN算法求得每个集群的异常得分,并获得初始异常,最后使用RkNN算法对初始异常进行过滤.实验结果证明,所提算法能有效减少漏报和误报,且具有较高的异常检测率和良好的稳定性.

障碍环境中可视反向视域K最近邻查询

在障碍环境下的空间应用中,用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题,将视域可视性引入到反向K最近邻查询中,提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q,可视反向视域K最近邻查询检索P中数据点,并将q作为可视视域K最近邻。应用查询点进行障碍过滤,得到障碍过滤算法,利用数据对象的视域进行剪枝,使用查询点与数据对象的关系剪枝,形成有效的障碍剪枝规则,并根据剪枝规则得到视域可视性判断算法。在此基础上,分别基于R^(*)-树和VFR-树提出可视反向视域K最近邻查询算法R^(*)-V2-RKNN和VFR-V2-RKNN,并分别通过对R^(*)-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明,VFR-V2-RKNN算法的查询性能明显优于R^(*)-V2-RKNN算法。