Mining Periodic Traces of an Entity on Web
Keywords:
Event, Periodic Trace, PatternAbstract
A trace of an entity is a behavior trajectory of the entity. Periodicity is a frequent phenomenon for the traces of an entity. Finding periodic traces for an entity is essential to understanding the entity behaviors. However, mining periodic traces is of complexity procedure, involving the unfixed period of a trace, the existence of multiple periodic traces, the large-scale events of an entity and the complexity of the model to represent all the events. However, the existing methods can’t offer the desirable efficiency for periodic traces mining. In this paper, Firstly, a graph model(an event relationship graph) is adopted to represent all the events about an entity, then a novel and efficient algorithm, TracesMining, is proposed to mine all the periodic traces. In our algorithm, firstly, the cluster analysis method is adopted according to the similarity of the activity attribute of an event and each cluster gets a different label, and secondly a novel method is proposed to mine all the Star patterns from the event relationship graph. Finally, an efficient method is proposed to merge all the Stars to get all the periodic traces. High efficiency is achieved by our algorithm through deviating from the existing edge-by-edge pattern-growth framework and reducing the heavy cost of the calculation of the support of a pattern and avoiding the production of lots of redundant patterns. In addition, our algorithm could mine all the large periodic traces and most small periodic traces. Extensive experimental studies on synthetic data sets demonstrate the effectiveness of our method.
References
Z. Zhong, Z. Liu, Z. Wen(2009), The Model of Event Relation Representation, Journal Of Chinese Information Processing, 23(6): 56-60.
Z. Zhong, C. Li (2013), Web News Oriented Event Multi-Elements Retrieval, Journal of Software, 24(10):2366-2378. http://dx.doi.org/10.3724/SP.J.1001.2013.04382
Z. Liu, M. Huang, W. Zhou(2009), Research on Event-oriented Ontology Model, Computer Science, 36(11): 191-195.
C.C. Yang, X. Shi, C.P. Wei (2009), Discovering event evolution graphs from news corpora, Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 39(4): 850-863.
H. Ji, R. Grishman, Z. Chen et al (2009), Cross-document Event Extraction and Tracking: Task, Evaluation, Techniques and Challenges, RANLP, 166-172.
W. Liu, D. Wang, W. Xu et al (2012), A Sub-topic Partition Method based on Event Network, The Seventh International Conference on Internet and Web Applications and Services, 194-199.
F. Zhu, Q. Qu, D. Lo et al(2011), Mining top-k large structural patterns in a massive network, Proc. of the VLDB Endowment, 4(11): 807-818.
Z. Li, J. Han, B. Ding et al (2012), Mining periodic behaviors of object movements for animal and biological sustainability studies, Data Mining and Knowledge Discovery, 24(2): 355-386. http://dx.doi.org/10.1007/s10618-011-0227-9
S. Bethard, J.H. Martin (2008), Learning semantic links from a corpus of parallel temporal and causal relations, Proc. ACL-HLT, 177-180. http://dx.doi.org/10.3115/1557690.1557740
Z. Li, J. Han, M. Ji et al (2011), Movemine: Mining moving object data for discovery of animal movement patterns, ACM Transactions on Intelligent Systems and Technology (TIST), 2(4): 37. http://dx.doi.org/10.1145/1989734.1989741
Z. Guan, X. Yan, L.M. Kaplan (2012), Measuring two-event structural correlations on graphs, Proceedings of the VLDB Endowment, 5(11): 1400-1411. http://dx.doi.org/10.14778/2350229.2350256
L. Gao, G.-M. Qin Gui, X.-F. Zhou (2008), An Overview of Algorithms for Mining Frequent Patterns in Graph Data, Acta Electronica Sinica, 36(8): 1603-1609.
J. Yang, W. Wang, S.Y. Philip (2008), Mining surprising periodic patterns, Data Mining and Knowledge Discovery, 9(2): 189-216. http://dx.doi.org/10.1023/B:DAMI.0000031631.84034.af
M. Wörlein, T. Meinl, I. Fischer et al(2005), A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston, Springer Berlin Heidelberg.
L.B. Holder, D.J. Cook, S. Djoko (1994), Substucture Discovery in the SUBDUE System, KDD workshop, 169-180.
S. Ghazizadeh, S.S. Chawathe (2002), SEuS: Structure extraction using summaries, Discovery science, Springer Berlin Heidelberg, 71-85.
M. Fiedler, C. Borgelt (2007), Support Computation for Mining Frequent Subgraphs in a Single Graph, MLG.
M. Al Hasan, V. Chaoji, S. Salem et al(2007), Origami: Mining representative orthogonal graph patterns, ICDM, 153-162.
Z. Li, F. Wu, M.C. Crofoot (2013), Mining Following Relationships in Movement Data, ICDM, 458-467.
I.C. Resceanu, G.C. Călugăru, C.F. Resceanu et al(2012), Cooperative Robot Structures Modeled After Whale Behavior and Social Structure, International Journal of Computers Communications & Control, 7(5): 945-956. http://dx.doi.org/10.15837/ijccc.2012.5.1354
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
