kNN填充算法的分析和改进研究

论文摘要

数据挖掘是一个热门的新兴领域,在经历了近10几年的高速发展之后,现已开发出了很多成熟的算法用于有效的处理海量数据,并且这些算法和技术在数据挖掘领域都有良好的表现。但是由于应用催生的数据挖掘技术绝大部分处理的都是现实生活中的问题,而对于算法需要使用的数据而言,现实生活中产生和搜集的数据通常都是充满各种各样的噪声、不一致和缺失等情况。因此数据预处理技术在数据挖掘过程中占有越来越重要地位。通常面临的各种现实数据的问题中,数据缺失是最常见的。在已经开发出的大部分经典算法中,处理带有缺失的数据是非常困难的。因为数据缺失产生的原因比较复杂,不同的应用中数据生成的过程迥异,所以算法开发和设计的时候通常假设数据是按照理想状态收集的。但是使用含有缺失的数据进行挖掘,会对挖掘过程和结果都产生严重的影响,甚至导致得出错误的模型和结论。因此数据挖掘算法和实际可用的数据之间存在一条巨大的鸿沟。针对数据缺失的预防、避免和处理等问题,国内外已经有很多学者进行了相关的研究,这些相关的研究吸收了统计、机器学习、概率等学科的成果,他们在缺失值填充领域开发出来的很多算法被实验和工业应用证明是非常成功的。在通常意义下,即使填充效果一般的填充算法,对挖掘算法的执行和挖掘效果的提高的作用都是明显的。本文主要是对应用最为广泛、可扩展性和适应性最好的算法之一——KNN算法的分析和改进。KNN算法是NN算法的推广形式。NN算法（最近邻算法）最早由Cover和Hart在1967年提出,最早用于分类的研究。其基本思想是使用距离待分类的事例最近的类标签来分类未知事例。由于该算法易于理解和编程,并且适用范围广泛,在提出之后被广泛用于分类、聚类、信息检索和查询、缺失值填充等领域,其中KNN算法就是NN算法在缺失值填充方面的改进版本。KNN算法使用缺失点附近的数据点对缺失值进行估计并进行填充。传统的KNN算法有很多的不足,例如计算量比较大等。已经有很多针对KNN的改进算法,这些算法通常专注于距离度量、距离计算、填充值的计算和计算结果存贮索引等方面的改进。在目前所参阅过的文献中,所有的补值算法均是使用某一特定算法或者使用某几种算法依次对整个数据集进行填充,而本文提出的缺失点分类思想指出,即使对于同一个数据集来说,不同的缺失点其适合的补值方法也是不同的,算法特别是基于密度和近邻等的局部算法,应该考虑对待填充的点进行分类,分别使用合适的方法进行填充,而不是简单的使用一种算法一视同仁的处理所有的数据。本文主要的工作是在分类填充的框架下,提出K-1NN算法和进一步的基于几何中心的CNN算法,并结合部分填充策略,提出两类不适合进行填充的缺失点,并将这两类点分离出来,在此基础上提出两个部分填充算法：PKNN和PCNN,通过实验证实分类填充思想和部分填充策略能够有效的提高KNN算法的填充准确率。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 前言
• 1.1 数据挖掘介绍
• 1.2 数据预处理
• 1.3 数据缺失和处理相关问题综述
• 1.3.1 缺失数据简介
• 1.3.2 缺失数据产生的原因
• 1.3.3 处理缺失数据的必要性
• 1.3.4 数据缺失的类型和机制
• 1.3.5 处理缺失数据的现有方法
• 1.4 本文的主要工作
• 1.5 本文结构
• 第2章 KNN算法等相关概念和工作、本文实验设计
• 2.1 KNN算法
• 2.1.1 KNN算法介绍
• 2.1.2 距离度量
• 2.1.3 填充值的计算
• 2.2 分类填充
• 2.3 部分填充
• 2.4 本文实验的相关设计和介绍
• 2.4.1 实验所使用的数据集介绍
• 2.4.2 数据的缺失处理
• 2.4.3 实验设计
• 2.4.4 算法实现
• 2.4.5 填充效果的评价
• 第3章 改进的KNN算法:分类完全填充
• 3.1 KNN存在的问题（Ⅰ）
• 3.2 KNN算法的改进（Ⅰ）:简单分类的K-1NN算法
• 3.3 实验结果和分析
• 3.4 KNN存在的问题（Ⅱ）
• 3.5 KNN算法的改进（Ⅱ）:基于几何中心的NN填充算法:CNN（Center-based NN）
• 3.6 实验结果和分析
• 第4章 部分填充的PKNN和PCNN算法
• 4.1 引入部分填充的原因
• 4.2 不适合填充的缺失点类型:以KNN为例
• 4.3 KNN的部分填充算法:PKNN
• 4.4 实验结果和分析
• 4.5 CNN的部分填充算法:PCNN
• 4.6 实验结果和分析
• 第5章 总结和将来的工作
• 参考文献
• 读研期间发表的论文
• 读研期间参与的项目
• 致谢