基于划分方法的大规模数据高效聚类算法的研究

摘要

在基于划分方法的聚类算法中，k-means算法因为简单易实现的特点而得到广泛的应用。然而它存在诸多的缺点特别是对于大规模数据不能进行有效的聚类分析。本文主要研究了如何在k-means算法中应用网格的思想，如何改进网格方法中存在的问题，以及如何改进k-modes聚类算法并如何将其应用到软件安全检测的问题。这些问题的研究在模式识别、数据分析、市场研究以及其它与聚类相关处理过程的分析中具有重要的意义。
　　首先，本文提出了一种基于网格密度的改进聚类算法 CABGD。在CABGD中，提出了网格中心密集度概念，通过计算网格中心密集度的值来识别网格内数据的分布，解决了传统网格算法中由于人为划分网格不当而导致聚类精度降低的问题。这种算法在聚类精度上优于传统基于网格的聚类算法。
　　其次，提出了一种基于网格的改进的k-means聚类算法IKMG。将单个网格作为基本的处理单元，同时应用并进一步改进了中心密集度概念，并设计了一种新的数据结构—聚类树。通过聚类树来组织和调整聚类簇，树的生成合并过程就是聚类过程。最终生成k个聚类树即聚类结果。在聚类大规模数据时，IKMG较传统的k-means算法有更高的时间效率，能发现任意形状大小的簇，无需人为指定k值的优点。
　　最后，设计了一种相似特征树的数据结构SFT，SFT作为一种软件故障检测的工具，主要用来提高软件安全检测的效率。为了构建SFT，提出了一种改进的k-modes聚类算法IKMD。在算法IKMD中，初始众数的选择进行于聚类的整个过程中。聚类结果以k棵树的形式给出。最后将包含这k棵树的森林转化为一个二叉树即SFT。SFT根据Apriori性质按照先左后右的原则对软件程序进行故障检测。分析结果显示该算法是可行有效的。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 聚类分析

1.2 课题研究的内容

1.3 本文的结构安排

第2章 基于网格的改进算法

2.1 引言

2.2 问题定义及描述

2.3 CABGD算法

2.4 算法分析与实例说明

2.5 本章小结

第3章 基于网格的改进的K-Means聚类算法

3.1 引言

3.2 问题定义及描述

3.3 树型搜索结构的设计

3.4 偏单元格处理策略

3.5 IKMG算法设计与分析

3.6 本章小结

第4章 面向软件安全检测的聚类算法研究

4.1 引言

4.2 相关概念与问题定义

4.3 IKMD算法设计与分析

4.4 相似特征树

4.5 本章小结

第5章 算法实现及实验分析

5.1 引言

5.2 CABGD算法实现及分析

5.3 IKMG算法实验结果

5.4 改进的K-Modes聚类算法实验

5.5 本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介