基于KNN算法的改进研究及其在数据分类中的应用

摘要

最近邻K(KNN，K-Ncarest Neighbor)分类算法是数据挖掘分类技术中最简单的方法之一，由于其实现的简单性，在很多领域得到了广泛的应用。但是，当样本容量较大以及特征属性较多时，KNN算法分类的效率就将大大降低。本文提出了一种改进的KNN算法，并将其与传统的KNN算法进行了比较。此算法不是直接预测响应变量的值，而是缩小响应变量发生的最大可能性的范围，然后插值以给出输出。在预处理步骤中对数据进行分层划分，运行时搜索响应具有发生最大可能性的分区。它采用单个参数k，与传统KNN算法相同，并且超过了目前实验研究所示的各种数据集上的常规技术方法。
　　本文提出了一种新颖，高效和具有离群抗性的基于聚类的KNN回归算法，CLUEKR算法首先找到查询点，而不是直接在整个数据集中搜索最近数据，然后找到在哪个集群。此算法首先在预处理步骤中对数据进行分层聚类，然后执行从层次结构的根节点开始的递归搜索，在层次结构的当前搜索节点中，子节点之间选择一个簇，然后应用递归搜索。最后，找到该簇中的查询点的k个最近邻，并返回其响应变量的加权平均值。本文还提出了使CLUEKR算法能够应用于分类任务的修改。
　　另外本文提出了基于类的加权K最近邻算法，根据其实例，在常规K-最近邻分类器的查询实例邻域中的分类，将权重分配给每个类。该算法考虑了查询实例附近的类分布，确保所分配的权重不会对异常值产生不利的影响。对几种现实世界数据集中所提出的方法进行彻底的实验研究证实，仿真证明研究的方法比目前最先进的方法更好。
　　最后，本文将基于类的加权K-最近邻算法与CLUEKR算法相结合，并提出了一种考虑到数据性质的高效准确的基于KNN的分类器。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 分类框架

1．2．2 数据选择

1．2．3 数据归一化

1．2．4 数据估算

1．2．5 降低纬度方法

1．3 论文的研究内容与目标

1．4 论文组织结构

第2章 相关工作

2．1 回归算法

2．1．1 传统统计方法

2．1．2 广义投射追求回归

2．1．3 神经网络和支持向量机

2．1．4 决策树

2．1．5 基于索引的方法

2．1．6 分段或分段回归

2．2 不平衡数据的学习

2．2．1 决策树

2．2．2 支持向量机

2．2．3 K最近邻分类算法

2．3 结论

第3章 BINER算法：基于二进制搜索的有效回归

3．1 BINER算法的直觉和方法

3．2 BINER算法

3．2．1 成分分析

3．3 实验研究

3．3．1 性能模型

3．2．2 结论

3．3．3 讨论

3．4 结论

第4章 CLUEKR算法：高效的基于KNN算法的回归聚类

4．1 CLUEKR算法

4．1．1 预处理

4．1．2 实际算法

4．1．3 复杂度分析

4．2 实验性研究

4．2．1 模型仿真运算

4．3 CLUEKR算法分类任务

4．3．1 算法

4．3．2 实验性研究

4．4 结论

第5章 基于类的加权K最近邻算法

5．1 关于加权因子设计的实验研究

5．1．1 KNN分类器基于类的加权因子的设计

5．1．2 KNN分类器的改进设计

5．1．3 只考虑查询实例附近区域的设计

5．1．4 模拟仿真

5．1．5 改进KNN算法模拟实施步骤

5．1．6 实验性研究

5．1．7 结论

5．2 作者提出的算法

5．2．1 权重因子的性质

5．2．2 成分分析

5．3 实验性研究

5．3．1 性能模型

5．4 结论

第6章 基于类的加权KNN算法与CLUEKR算法集成

6．1 研究基础

6．2 整合步骤

6．3 实验性研究

第7章 结论

7．1 成果

7．2 未来的工作

参考文献

致谢

作者简介及读研期间主要科研成果