社会网络中的时空周期行为模式挖掘算法研究

摘要

随着计算机、互联网和通信技术的迅猛发展，社会内部活动和联系日益紧密和频繁，其日趋复杂的网络化结构必然要求人类对各种复杂社会行为及其潜在模式有更为深入的研究。社会网络中的时空维度下的行为模式挖掘问题仍然是一个开放性的研究方向，存在大量的研究课题。
　　本文基于社会网络行为数据特性，重点研究时空维度下的周期行为模式挖掘算法，主要工作包括以下几个方面：
　　1.首先，本文提出了一种基于层次二部图模型的时空周期行为模式挖掘算法，能够挖掘社会中人们的周期行为习惯、移动轨迹。通过对动态社会网络数据进行时间片切片，算法可将整个社会网络转化为一个模式二叉树，高效的完成挖掘任务，克服以往算法的子集漏选问题，获取代表时空周期行为模式的闭合周期地点子集。
　　2.在此基础上，研究了最小周期地点控制子集算法，可以近似获取最小的地点控制子集，通过少量地点覆盖大部分个体行为模式；同时还提出了类周期行为模式挖掘算法，可挖掘出近似周期行为模式，该算法的挖掘结果更加接近现实社会中人们的行为习惯。然后，本文设计实验来验证了所提算法的有效性，采用微软亚洲研究院的GPS位置数据集和学生运动轨迹资料集进行测试，实验结果表明本文提出的算法具有良好的准确性与性能。
　　3.最后，基于Microsoft Visual Studio2008开发环境，本文设计并实现了一个社会网络时空周期行为模式挖掘算法的原型系统，能够对输入的数据集进行解析处理，可直观的输出周期行为的相关参数和统计资料，有助于研究人员对挖掘结果的分析与研究。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 研究背景及意义

1.2 社会网络挖掘国内外研究现状

1.2.1 国外研究现状

1.2.2 国内研究现状

1.3 本文的主要工作

1.4 文章结构安排

第2章 背景知识

2.1 数据挖掘与社会网络概述

2.2 频繁模式挖掘概述

2.2.1 Apriori算法

2.2.2 FP-growth算法

2.3 周期模式挖掘概述

2.4 小结

第3章 时空周期行为模式分析模型与挖掘算法研究

3.1 前言

3.2 基本定义

3.3 层次二部图模型

3.4 行为模式挖掘算法

3.4.1 SPBMA算法

3.4.2 周期最小地点控制子集近似算法

3.5 类周期行为模式挖掘算法

3.6 时空复杂度分析

3.7 算法评估与实验

3.8 小结

第4章 时空行为模式挖掘原型系统设计与实现

4.1 前言

4.2 原型系统设计与实现

4.2.1 数据规约

4.2.2 开发环境

4.2.3 系统设计

4.2.4 UI设计

4.2.5 系统实现

4.3 系统功能与应用

4.3.1 周期模式挖掘

4.3.2 类周期模式挖掘与最小地点控制子集

4.3.3 统计资料与保存结果

4.4 小结

结 论

参考文献

附录A 攻读学位期间完成的学术论文

附录B 攻读硕士期间参与的项目列表

附录C 攻读硕士学位期间获得的专利著作

致谢