在动态属性图中挖掘显著的趋势序列

发布时间：2025-06-21 01:27

　　随着社会的飞速发展以及数据采集设备的广泛应用,数据库中存储了大量数据。从数据中发现的知识能够帮助理解过去以及预测未来,因而推动了大量的数据挖掘技术的研究。图挖掘是一种重要的数据挖掘任务。在过去的数十年里,图分析受到越来越多来自数据挖掘社区的广泛关注。一个重要原因是图能够很好地捕获很多领域里数据的结构。特别是,在一些新兴领域如社交网络,传感器网络、生物信息网络里,越来越多的图数据被大量采集。分析图的需求催生了很多技术,包括对社群、离群点、模式的发现。在图中发现的模式可以帮助理解图的结构,进而用于决策、预测任务。本论文研究的对象是动态属性图。“属性”指一个顶点由多个属性描述,“动态”指顶点的属性值及顶点间的连接关系都会随时间变化。以一个社交网络图为例,里面顶点表示用户,边表示用户间的关联关系,每一个用户会由年龄、居住地、职业等多个属性描述,用户间的关联、描述用户的各个属性值都会随时间变化。动态属性图是动态图更一般的表现形式,在许多场景下,它是对数据自然且有力的表达。考虑动态性允许捕获演化模式,同时考虑多个属性则是使用先验知识定义了一个更大的模式空间,因为模式涉及更多可能的属性组合和属性、结构...

【文章页数】：82 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
ACKNOWLEDGEMENTS
Chapter 1 Introduction
    1.1 Background and Significance
    1.2 Related Work
        1.2.1 Simple Graph, Dynamic Graph and Attributed Graph
        1.2.2 Mining Trends in Dynamic Attributed Graphs
        1.2.3 Mining Emerging Patterns
        1.2.4 Spatio-temporal Data Mining
        1.2.5 Other Techniques for Capturing Changes in Dynamic Graphs
        1.2.6 Summary of Related Work
    1.3 Motivations and Research Content
        1.3.1 Motivations
        1.3.2 Reasearch Content
    1.4 Organization
Chapter 2 Preliminaries and Problem Definition
    2.1 Preliminaries
    2.2 Significance Measure
    2.3 Problem Statement
    2.4 Chapter Summary
Chapter 3 Pruning Strategies for Depth-First and Breadth-First Algorithms
    3.1 The Search Space
    3.2 Pruning Strategies
        3.2.1 Outer Level Pruning
        3.2.2 Inner Level Pruning
        3.2.3 Discussion of the Pruning Effects of the Three Thresholds
    3.3 Structures for Search Space Exploration
        3.3.1 Structure for a Breadth-First Search
        3.3.2 Structure for a Depth-First Search
    3.4 The TSeq Minerd f s-d f sAlgorithm
        3.4.1 Algorithm Description
        3.4.2 A Detailed Example of the Algorithm
        3.4.3 An Optimization: Medium-grained Pruning
        3.4.4 Complexity
    3.5 The TSeq Minerd f s-b f sAlgorithm
        3.5.1 Algorithm Description
        3.5.2 An Optimization: Pair-wise Pruning
        3.5.3 A Detailed Example of the Algorithm
        3.5.4 Complexity
    3.6 How to Set the Parameters
    3.7 Chapter Summary
Chapter 4 Experimental Evaluation
    4.1 Characteristics of the Datasets and Preprocessing
        4.1.1 Characteristics of the Datasets
        4.1.2 Preprocessing Methods
    4.2 Quantitative Experiment
        4.2.1 Influence of min Init Sup on Runtime and Number of Patterns
        4.2.2 Influence of Outer Level Pruning on Runtime and Number of Patterns
        4.2.3 Influence of min Sig on Runtime and Number of Patterns
        4.2.4 Influence of the Number of Timestamps, Attributes and Database Size
        4.2.5 Influence of min Init Sup and min Sig on Memory Consumption
    4.3 Pattern Analysis
        4.3.1 Patterns in DBLP Dataset
        4.3.2 Patterns in US Flight Dataset
    4.4 Chapter Summary
CONCLUSIONS
REFERENCES
PUBLICATIONS



本文编号：4051701