基于改进的CURE聚类的原型选择算法及其应用研究

摘要

在大数据时代，如何从海量数据集中挖掘出有用的知识已经成为各个领域都关注的一个重要问题。针对K最近邻分类器在大规模数据集中存在时间和空间复杂度过高的问题，本文采用CURE聚类方法进行原型选择，即通过CURE聚类算法挑选代表样例进行K最近邻分类且不降低其分类准确率，最后应用于不平衡数据集中。本文具体研究内容和研究结果如下： 1．改进了基于共享最近邻密度和最大最小距离的CURE聚类算法。针对CURE聚类算法存在的两个缺点：第一，噪声点的不易确定，提出了一种新的基于共享最近邻密度的去噪方法，该方法利用共享最近邻算法计算样例的相似度，进而求出每个样例的密度值，自适应得到密度阈值，判断噪声点进行剔除；第二，代表点分散性差，本文使用最大最小距离算法对原算法挑选代表点进行改进。将本文改进算法与传统的CURE算法、文献[72]算法、RTCURE算法在2个合成数据集和6个UCI数据集进行对比，结果表明：本文算法在平均准确率和运行效率上都有一定的提高。 2．提出了基于改进的CURE聚类的原型选择算法(PSCURE)。根据第一部分改进的CURE聚类算法对原始数据集进行聚类，从每个类中挑选出更具有代表性的样例添加到最终的原型子集再进行分类。首先利用PSCURE算法对合成数据集Pathbased和Flame people进行实验，结果表明：PSCURE算法可以选取出更具有代表性的边界点和部分内部点。其次，将PSCURE算法与传统的KNN、PSC算法和CNN、ENN、TRKNN、BNNT、2NMST算法在10个UCI数据集上进行实验，结果表明：PSCURE算法与传统的KNN算法有相同甚至更高的分类准确率，且能筛选出更少的样例，PSCURE算法与最新的几个算法相比不仅提高了平均准确率，而且减少了样例数。 3．利用PSCURE算法处理不平衡数据集。首先，使用PSCURE算法对不平衡数据集中的大多数样例进行欠抽样，使抽取的样例数与少数类的个数一样，从而得到均衡的原型集，再利用KNN算法进行分类。然后，通过5个UCI数据集进行实验，将PSCURE算法与KNN、EDSVM和ND-SVM算法进行对比分析，实验结果表明：PSCURE算法在F-measure和G-means两个指标上较其它算法有所提高。最后，将PSCURE算法应用到某市窃电用户数据集中，并与传统的KNN算法对比，实验结果表明：PSCURE算法在解决处理窃电用户数据集中具有一定的优势。

目录

声明

1. 绪论

1.1 研究背景与意义

1.1.1 研究背景

1.1.2 研究意义

1.2 国内外研究现状

1.2.1 原型选择算法的研究现状

1.2.2 CURE聚类算法研究现状

1.2.3 不平衡数据集研究现状

1.3 本文研究目的和内容安排

2. 预备知识

2.1 K最近邻分类器

2.2 原型选择

2.2.1 原型选择相关概念

2.2.2 原型选择的分类

2.2.3 原型选择的评价指标

2.3 聚类分析

2.3.1 聚类分析的基本概念

2.3.2 聚类分析的类型

2.3.3 聚类方法的评价指标

2.4 不平衡数据集

2.4.1 不平衡数据集的分类

2.4.2 不平衡数据集的评价指标

2.5 本章小结

3. 基于共享最近邻密度和最大最小距离的CURE聚类算法

3.1 基于共享最近邻密度的去噪方法

3.2 最大最小距离算法

3.3 CURE聚类算法

3.3.1 CURE聚类算法的基本思想

3.3.2 CURE聚类算法的优缺点

3.4 基于共享最近邻密度和最大最小距离的CURE聚类算法

3.5 实验结果及分析

3.5.1 合成数据集上算法性能验证

3.5.2 UCI数据集上算法性能验证

3.6 本章小结

4. 基于改进的CURE聚类的原型选择算法

4.1 算法思想

4.2 算法流程

4.3 实验结果及分析

4.3.1 实验目的

4.3.2 实验结果

4.4 本章小结

5. 原型选择在不平衡数据集中的应用

5.1 算法思想

5.2 算法流程

5.3 实验结果及分析

5.3.1 UCI数据集上的实验

5.3.2 窃电数据集上的实验

5.4 本章小结

6. 总结与展望

6.1 总结

6.2 展望

致谢

参考文献

攻读学位期间主要研究成果