高维数据聚类技术中的若干算法研究

论文摘要

数据挖掘是一种可以在数据库上挖掘有用信息的技术,这些信息被称为知识,所以数据挖掘又称知识发现。从大量数据中挖掘出的知识可用于决策支持、数据分析等领域,随着数据库的发展,数据挖掘已显得越来越重要。随着数据规模的不断增大,传统聚类分析方法难以发挥作用。聚类操作实际上是数据对象之间相似性的度量,相似度高的对象被归为一类。在低维空间中经常使用欧氏距离等函数来度量相似性,但在高维情况下由于相似性没有传递性,距离函数不再发挥作用,而高维数据的距离函数难于定义,因此必须重新考虑新的度量数据对象相似性的标准或准则。另外,由于维数很高,传统聚类算法的计算复杂度会很高,其应用也受到了很大的局限性。针对高维数据引起的“维度灾难”问题,本文研究了高维数据的特点,充分利用单维与多维的关系,提出了用单维来分割高维数据,并将数据进行整合,按维序逐次聚类的HDCASDP算法。在单个维上进行聚类时,采用索引转换技术来预处理数据,从而简化高维数据处理问题。该算法每次处理只针对一个维层次,经过层层处理,最终就能得到完整数据空间上的聚类。在HDCASDP算法的基础上,分析并整合了传统数据聚类算法K-means算法的几种改进算法,提出了适用于更高维空间的聚类算法DFBC。DFBC算法首先在高维数据空间上,将维划分为比较低的维组合,在这些维组合的数据空间上运用改进的K-means算法进行聚类,以维组合为层次,聚类过程是逐层进行的,这实际上跟单维分割聚类技术是相似的,所有层处理完之后就得到了最终的聚类结果。相比于单维分割聚类技术,使用维分组的聚类技术更适用于大型更高维的数据空间。该算法按照维组层次的增长,计算时间也是呈线性变化的,但是就算法的思想来说,它是低维聚类与高维聚类技术的一种折衷。本文还对网格的聚类技术进行了研究,分析了固定网格划分聚类与自适应网格划分聚类存在的缺陷,针对GCOD算法存在的缺陷,提出了一种改进的方法。GCOD算法主要采用了相交网格划分的措施,对固定网格划分与自适应网格划分技术采取了一种折衷的处理策略。但是GCOD算法未对相交网格的大小进行限制,使得这其中会存在许多不合理化聚类。我们针对这个问题提出了对网格大小进行限制的方法,并且提出了更加合理的密度计算方法。研究了子空间聚类的一些算法,针对经典算法CLIQUE存在的缺陷,提出了基于半相交网格划分的HIGSC算法。它首先利用半相交网格划分方法在单个维上进行聚类,然后利用类Apriori规则来形成子空间,在子空间形成的过程中运用类HDCASDP方法产生子空间上的聚类。算法的性能较CLIQUE算法有了提升,在聚类结果的精度方面提升明显。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究背景
• 1.1.1 数据挖掘的产生与发展
• 1.1.2 聚类分析
• 1.2 课题的引出
• 1.3 论文的主要工作
• 1.4 本文创新点
• 1.5 论文组织
• 第二章 基本理论
• 2.1 数据挖掘简介
• 2.1.1 数据挖掘定义
• 2.1.2 数据挖掘分类
• 2.1.3 数据挖掘系统功能
• 2.2 聚类技术
• 2.2.1 聚类问题的描述
• 2.2.2 相似度度量
• 2.2.3 聚类技术分类
• 2.3 高维数据聚类
• 2.3.1 高维数据聚类概念
• 2.3.2 维度灾难
• 2.3.3 高维数据聚类技术分类
• 2.4 本章小结
• 第三章 基于单维分割的高维数据聚类算法
• 3.1 相关技术
• 3.1.1 转换索引
• 3.1.2 单维聚类
• SDP 聚类算法'>3.2 HDCA_SDP 聚类算法
• 3.3 实验结果与分析
• 3.4 本章小结
• 第四章 高维数据的维分组聚类技术
• 4.1 相关技术
• 4.1.1 K-平均算法
• 4.1.2 K 值优化
• 4.1.3 中心点选取优化
• 4.1.4 K 平均算法的完全优化算法TK-MEANS
• 4.2 维分组技术
• 4.3 基于维分组技术的聚类算法DFBC
• 4.3.1 相关定理
• 4.3.2 DFBC 算法描述
• 4.4 实验结果分析
• 4.5 本章小结
• 第五章 基于相交网格划分的算法IGCOD
• 5.1 相关工作
• 5.2 相关概念
• 5.3 IGCOD 算法
• 5.4 实验结果与分析
• 5.5 本章小结
• 第六章 基于半相交网格的子空间聚类HIGSC 算法
• 6.1 相关工作
• 6.2 问题描述
• 6.3 单维半相交网格聚类
• 6.4 HIGSC 算法
• 6.5 实验分析
• 6.6 本章小结
• 第七章 总结与展望
• 7.1 总结
• 7.2 下一步的研究工作
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文
• 攻读学位期间参加的研究工作