基于参考点的演化聚类算法研究

摘要

随着互联网的蓬勃发展和人们采集数据能力的增强，实际生活中出现了越来越多的随时间变化的数据，我们称这类数据为演化数据(Evolutionary Data)。近年来，演化数据的聚类问题引起了很多研究者的兴趣。一般地，演化聚类的要求有两个方面:1）每个时刻发现的聚类结构要尽可能好地划分当前时刻的快照数据;2）每个时刻发现的聚类结构要尽可能保持时间平滑性，即和上个时刻相比，当前时刻发现的聚类结构尽量不发生太大的变化。演化数据聚类有很广泛的应用背景，其研究有着很重要的意义。
　　本文从核心节点和参考点的角度来研究演化聚类。本文的主要内容包括三个方面。
　　1)受静态社区发现算法Top Leaders启发，我们提出一个基于核心节点(LeaderNodes)的演化社区发现算法(EvoLeaders)。首先，我们基于结合时间信息的更新策略来得到每个时刻的初始核心节点。通过保持发现的初始核心节点集合与上个时刻核心节点集合的时间平滑性，来保证由这些核心节点发现的社区跟以前的结构尽量保持平滑。然后，通过一组分裂合并操作提高社区质量。在两个实际数据集上的实验结果表明，EvoLeaders算法比Top Leaders算法效果更好。该工作表明了从核心节点的角度进行演化社区发现的可行性。
　　2) Top Leaders算法的主要缺点是需要人工输入社区数目。基于网络中每个节点与其邻居节点之间度的关系，以及节点之间共同邻居的重叠程度，我们改进了Top Leaders算法，并提出了能够自动发现社区数目的AutoLeaders算法。在三个经典数据集上的实验结果表明，AutoLeaders算法不仅能够发现合理的社区数目，还能够发现合理的社区结构。进一步，基于两种时间平滑性策略，我们提出了在动态网络中发现社区的新的解决方案，即EvoAutoLeaders算法。在两个实际数据集上的结果表明EvoAutoLeaders算法的效果比较好。
　　3)我们从参考点的角度来处理演化聚类问题。首先，我们引入了三种不同的参考点，以及相应的计算个体到参考点距离的策略。然后，基于r-dominance关系和多目标演化算法，提出了一个演化聚类算法（即rEvoC算法）。实验结果证明，与经典算法相比，rEvoC算法更适合聚类演化数据，而且能够取得更好的效果。
　　总的来说，我们从核心节点和参考点的角度来处理演化数据聚类问题，并且通过实验证明了其有效性，而且效果比经典算法更优。本文的工作对演化社区发现和演化数据聚类方法研究方面具有一定的参考价值。

目录

声明

摘要

插图目录

表格目录

第1章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 传统聚类算法

1．2．2 演化聚类

1．2．3 与演化聚类相似的研究问题

1．3 本文的主要内容

1．4 本文的章节安排

第2章 基于核心节点的演化社区发现算法

2．1 概述

2．2 相关定义

2．3 相关工作

2．3．1 社区发现算法

2．3．1 Top Leader算法

2．3．2 模块度Q和社区合并算法

2．4 算法框架

2．4．1 获得初始核心节点

2．4．2 分裂社区

2．4．3 EvoLeaders的两个版本

2．5 实验结果

2．5．1 评价指标和实验设置

2．5．2 Enron邮件数据集

2．5．3 Catalano社会网络

2．6 本章小结

第3章 Top Leaders算法改进和演化社区发现

3．1 概述

3．2 AutoLeaders算法及实验

3．2．1 AutoLeaders算法描述

3．2．2 AutoLeaders算法相关实验

3．3 EvoAutoLeaders算法及实验

3．3．1 EvoAutoLeaders算法描述

3．3．2 EvoAutoLeaders算法相关实验

3．4 本章小结

第4章 基于参考点和r-Dominance关系的演化聚类算法

4．1 概述

4．2 背景知识

4．2．1 多目标优化

4．2．2 基于多目标演化算法进行聚类

4．2．3 基于多目标演化算法进行演化数据聚类

4．2．4 基于r-dominance关系的多目标演化算法

4．3 算法描述

4．3．1 染色体表示和算子

4．3．2 两个目标函数

4．3．3 参考点

4．3．4 算法框架描述

4．4 实验

4．4．1 人工数据集

4．4．1 实际数据集

4．5 本章小结

第5章 总结与展望

5．1 全文工作总结

5．2 展望

参考文献

致谢

读硕士期间发表的学术论文

作者简历