基于网格相邻关系的多密度聚类和离异点识别算法研究

摘要

聚类分析和离异点识别都是数据挖掘的重要分支。随着聚类分析和离异点识别技术在科学研究、市场分析以及生命科学等众多学科领域广泛的应用，它们在挖掘分析中的重要地位也日渐显现。通过对数据空间的网格单元的相邻关系深入研究，本文提出了利用数据空间中的网格单元间的关系，进行聚类和离异点识别。主要研究工作如下：
　　 在分析了网格划分与均匀分布数据投影相异数的关系基础上，提出了划分网格与投影相异数关系定理，并给出了相异数划分网格法。对网格划分数不是整数时，小数部分也提出了处理办法。该划分网格法考虑了数据分布的因素，减少了冗余网格数，简单易行。为了判断相邻单元的关系，定义了一种关于单元质心距离和相对密度的相异函数。
　　 按照离异点是在一定范围内偏离其它数据点，离异点所在单元的密度与相邻单元的密度相比可能偏高或偏低的思想，提出了一种基于网格相邻关系的离异点识别算法GAO。该算法用单元间的相对密度和单元质心距离来衡量单元间的离异度，根据离异度确定离异单元和离异点。实验结果表明，该算法能有效地识别出多密度数据集的离异点，算法的效率优于Cell-based算法，且适合大数掘集的离异点识别。
　　 利用单元的密度和质心能反映单元内数掘分布特征，提出了基于网格相邻关系的多密度聚类算法GAMD。该算法用相异函数来衡量单元间的相似度和离异度，用相似度确定边界单元的数据归属，并且聚类的同时进行离异点的识别，有较高的时间效率和精度。为检验聚类的有效性，提出了拟合度的概念。实验结果表明，该算法能发现任意形状的簇，并能有效地对多密度数据集进行聚类，聚类和离异点识别结果与数据输入顺序和单元顺序无关。

目录

文摘

英文文摘

声明

第1章 绪论

1.1研究背景与意义

1.2国内外研究现状

1.3本文的主要工作

1.4论文结构

第2章 数据挖掘中的聚类分析和离异点识别

2.1数据挖掘概念和研究内容

2.2聚类分析概述

2.3聚类算法

2.3.1基于划分的聚类方法(partitioning method)

2.3.2基于层次的聚类方法(hierarchical method)

2.3.3基于模型的聚类方法(model-based method)

2.3.4基于密度的聚类方法(density—based method)

2.3.5基于网格的聚类方法(grid—based method)

2.4离异点的描述

2.5离异点识别方法

2.5.1基于统计的离异点识别方法

2.5.2基于距离的离异点识别方法

2.5.3基于密度的离异点识别方法

2.5.4基于偏离的离异点识别方法

2.6本章小结

第3章 相异数划分网格法和相异函数

3.1基本数据类型及表示形式

3.2数据标准化与数据转化

3.3相异度

3.4网格空间

3.5划分网格方法分析

3.6相异数划分网格法描述

3.7相异函数

3.8本章小结

第4章 基于网格相邻关系的离异点识别算法

4.1问题分析

4.2离异点衡量标准

4.3 GAO算法描述

4.4算法复杂度分析

4.5实验分析

4.5.1算法性能比较

4.5.2算法有效性比较

4.6本章小结

第5章 基于网格相邻关系的多密度聚类算法

5.1研究背景

5.2相关概念

5.3基于网格相邻关系的多密度聚类算法(GAMD)

5.3.1基本思想

5.3.2边界单元的处理

5.3.3 GAMD算法描述

5.4算法复杂度分析

5.5实验分析

5.5.1算法性能实验

5.5.2算法有效性实验

5.6本章小结

结论

致 谢

参考文献

攻读学位期间发表的论文