无参数网格聚类算法的研究

论文摘要

数据挖掘技术可以从大量数据中发现潜在的、有价值的知识,它给人们在信息时代所积累的海量数据赋予了新的意义。聚类分析作为其重要的组成部分,当前,在模式识别,数据处理,图形图像以及市场分析等方面越来越受到人们的青睐。在众多研究领域当中,聚簇分析是专家学者研究的焦点。本文对聚类算法进行了深入地分析研究,指出该类算法存在着对参数敏感、不能有效地对多密度数据集聚类等问题。针对这些问题,本文利用网格熵和网格信息度的概念来自动计算出网格聚类中的密度阈值,在此基础上提出了一种有效的无参数网格聚类算法NaRic;针对传统的反向K-近邻边界点检测算法BORDER存在着时间复杂度较高、参数难以确定以及该算法不能去除孤立点影响等问题,本文利用网格中数据点方差的概念来确定聚类中的边界点,在此基础上提出了基于统计信息的边界点检测算法BPSF。针对上述提出的两种算法NaRic和BPSF,本文中都进行了较为详细的描述,给出了算法实现的具体步骤。本文使用Visual C++6.0实现了无参数网格聚类算法NaRic、共享近邻SNN算法、基于统计信息的边界点检测算法BPSF、反向K-近邻边界点检测算法BORDER算法,做了大量的对比实验,包括有效性、效率对比实验,所使用的数据集包括综合数据集和真实数据集。实验结果表明,无参数网格聚类算法在不需要任何输入参数的情况下可以处理任意形状、任意大小的聚类,并且可以对多密度数据集进行正确聚类,和传统的多密度聚类算法SNN相比,该算法具有较高的聚类精度和效率;基于统计信息的边界点检测算法BPSF可以去除噪声点的影响,较为准确的找到聚类的边界,算法的时间复杂度小于传统的边界点检测算法BORDER。总之,无参数网格聚类算法在一定程度上解决了网格聚类算法对参数敏感的问题,而基于统计信息的边界点检测算法也能够准确、有效的发现聚类的边界点,并且在执行效率、检测效果等方面有一定的优越性。

论文目录

• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 研究背景与意义
• 1.2 研究内容与思路
• 1.3 论文组织结构
• 第2章 聚类算法分析
• 2.1 数据挖掘概述
• 2.2 聚类分析
• 2.2.1 聚类分析概述
• 2.2.2 聚类算法介绍
• 2.3 多密度聚类算法
• 2.4 参数自动化聚类算法
• 2.5 聚类的边界点检测算法
• 2.5.1 DBSCAN算法中的边界点
• 2.5.2 边界点检测算法BORDER
• 2.6 本章小结
• 第3章 无参数网格聚类算法
• 3.1 基本概念
• 3.2 参数自动化技术
• 3.2.1 参数k的处理
• 3.2.2 密度阈值处理算法
• 3.3 聚类的边界点提取技术
• 3.4 NaRic聚类算法
• 3.4.1 数据结构
• 3.4.2 NaRic算法的实现
• 3.5 算法复杂度分析
• 3.6 实验结果与分析
• 3.6.1 NaRic算法正确性验证
• 3.6.2 综合数据集
• 3.6.3 真实数据集
• 3.7 本章小结
• 第4章 基于统计信息的边界点检测算法
• 4.1 对BORDER算法的分析
• 4.2 基本概念
• 4.3 基于统计信息的边界点检测算法BPSF
• 4.4 实验结果
• 4.5 时间复杂度和效率分析
• 4.6 参数讨论
• 4.7 本章小结
• 第5章 总结及进一步工作展望
• 致谢
• 参考文献
• 附:硕士学位攻读期间的科研成果及奖励