隨著社會的飛速發(fā)展以及數(shù)據(jù)采集設(shè)備的廣泛應(yīng)用,數(shù)據(jù)庫中存儲了大量數(shù)據(jù)。從數(shù)據(jù)中發(fā)現(xiàn)的知識能夠幫助理解過去以及預(yù)測未來,因而推動了大量的數(shù)據(jù)挖掘技術(shù)的研究。圖挖掘是一種重要的數(shù)據(jù)挖掘任務(wù)。在過去的數(shù)十年里,圖分析受到越來越多來自數(shù)據(jù)挖掘社區(qū)的廣泛關(guān)注。一個重要原因是圖能夠很好地捕獲很多領(lǐng)域里數(shù)據(jù)的結(jié)構(gòu)。特別是,在一些新興領(lǐng)域如社交網(wǎng)絡(luò),傳感器網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)里,越來越多的圖數(shù)據(jù)被大量采集。分析圖的需求催生了很多技術(shù),包括對社群、離群點、模式的發(fā)現(xiàn)。在圖中發(fā)現(xiàn)的模式可以幫助理解圖的結(jié)構(gòu),進而用于決策、預(yù)測任務(wù)。本論文研究的對象是動態(tài)屬性圖。“屬性”指一個頂點由多個屬性描述,“動態(tài)”指頂點的屬性值及頂點間的連接關(guān)系都會隨時間變化。以一個社交網(wǎng)絡(luò)圖為例,里面頂點表示用戶,邊表示用戶間的關(guān)聯(lián)關(guān)系,每一個用戶會由年齡、居住地、職業(yè)等多個屬性描述,用戶間的關(guān)聯(lián)、描述用戶的各個屬性值都會隨時間變化。動態(tài)屬性圖是動態(tài)圖更一般的表現(xiàn)形式,在許多場景下,它是對數(shù)據(jù)自然且有力的表達�？紤]動態(tài)性允許捕獲演化模式,同時考慮多個屬性則是使用先驗知識定義了一個更大的模式空間,因為模式涉及更多可能的屬性組合和屬性、結(jié)構(gòu)...

【文章頁數(shù)】：82 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
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