面向移动对象的不确定组模式挖掘算法

摘要

随着移动电话，车载GPS，LBS应用等技术的飞速发展，生成了海量的移动数据，这些移动数据与人类本身息息相关，所以对轨迹数据的分析有着重要的研究和商业意义。此外，由于设备采集精度、网络传输延迟等原因，使得不确定数据在现实中普遍存在，因此面向不确定数据的挖掘算法成为当前研究的热点问题。由于车流分析，移动电子商务，基于位置的服务以及野生动物研究等方面之中的重要意义，本文解决不确定数据的组模式挖掘算法，这种模式挖掘对于了解不确定轨迹数据是很重要的。轨迹数据的组模式挖掘主要包括两方面的内容:其一是聚类分析，它研究的是在某一时刻移动对象聚类的问题;其二是组模式的挖掘，它挖掘的是在多个时刻都属于同一聚类的对象。
　　对于本文提出的算法需要解决以下几个问题:(1)选择合适聚类算法为组模式挖掘提供正确的不确定数据作为输入;(2)如何将可能世界模型加入到面向确定数据的组模式挖掘算法之中;(3)算法的搜索空间十分的巨大，如何进行裁剪优化。(4)对原始算法和优化算法进行了对比实验，对两种算法的运行时间和挖掘结果进行比对，验证优化算法是否能够在保证挖掘结果的同时提高算法的效率。
　　本文将聚类算法作为组模式挖掘的预处理操为组模式挖掘提供相关的不确定数据，聚类常用的算法包括了DBS CAN和C均值聚类等等，本文使用模糊的C均值聚类将确定的轨迹数据转换成不确定的聚类数据，再提出面向不确定数据的组模式挖掘算法对其进行操作得到最终的结果。本文依据这种研究思路将轨迹数据的组模式挖掘应用到不确定数据之中，改进了面向确定数据的ObjectGrowth算法，使其能够对不确定数据进行同样的挖掘操作。并且结合已有的裁剪规则提出新的优化方法对搜索进行优化。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 研究现状

1．3 本文的主要研究内容

1．4 组织结构

1．5 本章小结

第2章 相关基础理论及工作

2．1 相关数学基础

2．1．1 概率论

2．1．2 拉格朗日乘数法

2．1．3 模糊集

2．2 不确定数据

2．2．1 不确定数据的分类

2．2．2 不确定数据的模型

2．3 不确定数据的聚类算法

2．3．1 经典的聚类算法

2．3．2 不确定数据聚类与确定数据聚类的区别

2．3．3 不确定数据聚类算法

2．4 不确定数据的组模式挖掘算法

2．4．1 确定轨迹数据的移动对象挖掘

2．4．2 不确定数据的频率模式挖掘

2．5 本章小结

第3章 组模式挖掘的预处理

3．1 问题的提出

3．2 基本思路

3．3 面向不确定数据的聚类

3．3．1 不确定instant距离度量

3．3．2 隶属度的计算

3．3．3 算法设计

3．4 本章小结

第4章 面向不确定数据的移动对象组模式挖掘

4．1 问题描述

4．1．1 问题提出

4．1．2 形式化定义

4．2 组模式挖掘算法

4．2．1 组模式的概率计算

4．2．2 剪枝规则

4．2．3 基本算法

4．2．4 优化算法

4．3 本章小结

第5章 实验与分析

5．1 实验环境

5．2 实验数据集

5．3 实验结果与分析

5．4 本章小结

第6章 总结与展望

参考文献

致谢