基于自然邻居的谱聚类和离群检测算法研究

摘要

随着互联网的快速发展，各行各业都有源源不断的数据产生，从这些数据中发现有价值的信息并为相关人员提供决策支持，是当前数据挖掘的主要任务。聚类分析和离群检测是数据挖掘任务中的重要组成部分，已被广泛应用在模式识别、人工智能、信用卡欺诈行为检测、视频监控等领域，并推动了社会的进步和行业的发展。聚类分析是利用数据之间的相似性分析它们的潜在关系，其中谱聚类具有坚实的理论基础和良好的聚类性能，引起了越来越多研究者的关注。谱聚类算法无需对数据的全局结构做任何假设就可以收敛到全局最优，但该类算法存在尺度参数选择、相似度度量以及聚类数目确定等问题。离群检测主要用于发现一些异常数据或者存在偏离常规行为的模式，其中基于密度的离群检测算法是目前常用的策略，但该类算法通常存在近邻参数选择以及密度差异数据集中离群点易被误检等问题。　　因此，为了解决谱聚类和离群检测中存在的邻域参数选择问题，本文引入了一种不需要人为设定参数的邻域搜索方法——自然邻居搜索算法。该算法通过不断扩大邻域的搜索范围，以自动适应数据集中数据点之间的分布。此外，针对上文提到的其他问题，本文结合自然邻居搜索算法提出了两种改进算法，具体如下：　　① 提出了一种基于共享自然近邻的自适应谱聚类算法。针对谱聚类算法中邻域尺度参数选择问题，本文首先通过自然邻居搜索算法得到自适应邻域参数。然后，对于一些流行数据集上会存在数据点之间误识别为同一簇的情况，结合得到的自适应邻域参数，使用共享近邻的方式重新定义数据点的相似性，以便能够有效描述数据之间的内在联系。最后，利用特征间隙的思想在特征向量中获得聚类数目以完成整个算法聚类。本文在人工和真实数据集上进行了对比实验。实验结果表明，相对于已有算法输入合适参数的情况，本文提出的算法在对流行聚类方面聚类效果较为理想，更具有优势。　　② 提出了一种基于自然邻居的离群检测算法。针对离群检测算法中邻域参数选择问题，本文首先对自然邻居搜索算法进行了改进，以便得到自然特征值并构造出自然特征邻域图。然后，使用自然特征邻域图中的信息来反应数据的紧密程度，以解决数据集中的密度差异问题，同时得到全局离群点。接着，重新定义新的离群因子并对其进行排序，选取较高离群因子的对象作为离群点。最后，通过在人工和真实数据集上的实验，验证了该算法在离群检测中的有效性。

目录

1 绪 论

1.1 研究背景与意义

1.2.1 聚类算法研究

1.2.2 离群检测研究

1.3 论文主要研究内容

1.4 论文组织结构

2 理论基础

2.1 谱聚类

2.1.1 谱聚类基础

2.1.2 典型谱聚类算法

2.1.3 聚类结果评价指标

2.2 离群检测

2.2.1 离群检测算法

2.2.2 离群检测评价指标

2.3 本章小结

3 自然邻居搜索算法

3.1 自然邻居搜索算法概述

3.2 自然邻居搜索算法改进

3.3 本章小结

4 基于共享自然近邻的自适应谱聚类算法

4.1 引言

4.2 基于共享自然近邻的自适应谱聚类算法

4.2.1 改进相似度度量

4.2.2 利用特征间隙确定聚类数目

4.2.3 算法概述

4.3 实验与分析

4.3.1 人工数据集实验分析

4.3.2 真实数据集实验分析

4.4 本章小结

5 基于自然邻居的离群检测算法

5.1 引言

5.2 基于自然邻居的离群检测算法

5.2.1 自然特征邻域图

5.2.2 改进离群因子

5.2.3 算法概述

5.3 实验与分析

5.3.1 人工数据集实验分析

5.3.2 真实数据集实验分析

5.4 本章小结

6 总结与展望

6.1 总结

6.2 展望

参考文献

附录

A. 作者在攻读学位期间发表的论文目录

B. 学位论文数据集

致谢