nach oben

Knowledge and Information Systems

Erschienen in:

06.10.2017 | Regular Paper

Mining exceptional closed patterns in attributed graphs

verfasst von: Anes Bendimerad, Marc Plantevit, Céline Robardet

Erschienen in: Knowledge and Information Systems | Ausgabe 1/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Geo-located social media provide a large amount of information describing urban areas based on user descriptions and comments. Such data make possible to identify meaningful city neighborhoods on the basis of the footprints left by a large and diverse population that uses this type of media. In this paper, we present some methods to exhibit the predominant activities and their associated urban areas to automatically describe a whole city. Based on a suitably attributed graph model, our approach identifies neighborhoods with homogeneous and exceptional characteristics. We introduce the novel problem of exceptional subgraph mining in attributed graphs and propose a complete algorithm that takes benefits from closure operators, new upper bounds and pruning properties. We also define an approach to sample the space of closed exceptional subgraphs within a given time budget. Experiments performed on ten real datasets are reported and demonstrated the relevancy of both approaches, and also showed their limits.

Nächster Artikel Estimating effectiveness of twitter messages with a personalized machine learning approach

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

EXCESS stands for EXceptional ClosEd Subgraph Sampler.

https://github.com/AnesBendimerad/ClosedExceptionalSubgraphMining.

https://developer.foursquare.com/categorytree.

https://www.kaggle.com/c/sf-crime.

Atzmüeller M, Doerfel S, Mitzlaff F (2016) Description-oriented community detection using exhaustive subgroup discovery. Inf Sci 329:965–984CrossRef

Bendimerad AA, Plantevit M, Robardet C (2016) Unsupervised exceptional attributed sub-graph mining in urban data. In: IEEE 16th international conference on data mining, ICDM 2016, Barcelona, Spain, 12–15 Dec 2016, pp 21–30

Boley M, Lucchese C, Paurat D, Gärtner T (2011) Direct local pattern sampling by efficient two-step random procedures. In: ACM SIGKDD 2011, pp 582–590

Boulicaut J, Plantevit M, Robardet C (2016) Local pattern detection in attributed graphs. In: Solving large scale learning tasks. Challenges and algorithms—essays dedicated to Katharina Morik on the occasion of her 60th birthday, pp 168–183

Duivesteijn W, Feelders A, Knobbe AJ (2016) Exceptional model mining—supervised descriptive local pattern mining with complex target concepts. Data Min Knowl Discov 30(1):47–98MathSciNetCrossRef

Duivesteijn W, Knobbe AJ, Feelders A, van Leeuwen M (2010) Subgroup discovery meets bayesian networks—an exceptional model mining approach. In: ICDM 2010, pp 158–167

Dzyuba V, van Leeuwen M, Raedt LD (2017) Flexible constrained sampling with guarantees for pattern mining. Data Min Knowl Discov 31(5):1266–1293MathSciNetCrossRef

Falher GL, Gionis A, Mathioudakis M (2015) Where is the soho of rome? Measures and algorithms for finding similar neighborhoods in cities. In: ICWSM 2015, pp 228–237

Giacometti A, Soulet A (2016) Frequent pattern outlier detection without exhaustive mining. In: PAKDD 2016, pp 196–207

10.

Günnemann S, Färber I, Boden B, Seidl T (2010) Subspace clustering meets dense subgraph mining. In: ICDM 2010, pp 845–850

11.

Hasan MA, Zaki MJ (2009) Output space sampling for graph patterns. PVLDB 2(1):730–741

12.

Kaytoue M, Plantevit M, Zimmermann A, Bendimerad A, Robardet C (2017) Exceptional contextual subgraph mining. Mach Learn 106(8):1171–1211MathSciNetCrossRefMATH

13.

Kuznetsov SO (1999) Learning of simple conceptual graphs from positive and negative examples. In: Principles of data mining and knowledge discovery, third european conference, PKDD ’99, Prague, Czech Republic, Proceedings, 15–18 Sep 1999, pp 384–391

14.

Lavrac N, Kavsek B, Flach PA, Todorovski L (2004) Subgroup discovery with CN2-SD. J Mach Learn Res 5:153–188MathSciNet

15.

Leman D, Feelders A, Knobbe AJ (2008) Exceptional model mining. In: ECMLPKDD 2008, pp 1–16

16.

Lemmerich F, Becker M, Singer P, Helic D, Hotho A, Strohmaier M (2016) Mining subgroups with exceptional transition behavior. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, CA, USA, 13–17 Aug 2016, pp 965–974

17.

Li G, Zaki MJ (2016) Sampling frequent and minimal boolean patterns. Data Min Knowl Discov 30(1):181–225MathSciNetCrossRef

18.

Moens S, Boley M (2014) Instant exceptional model mining using weighted controlled pattern sampling. In: IDA, pp 203–214

19.

Moens S, Goethals B (2013) Randomly sampling maximal itemsets. In: ACM SIGKDD workshop on interactive data exploration and analytics, pp 79–86

20.

Moser F, Colak R, Rafiey A, Ester M (2009) Mining cohesive patterns from graphs with feature vectors. In: SDM 2009, pp 593–604

21.

Mougel P, Rigotti C, Plantevit M, Gandrillon O (2014) Finding maximal homogeneous clique sets. Knowl Inf Syst 39(3):579–608CrossRef

22.

Novak PK, Lavrac N, Webb GI (2009) Supervised descriptive rule discovery: a unifying survey of contrast set, emerging pattern and subgroup mining. J Mach Learn Res 10:377–403MATH

23.

Park S, Bourqui M, Frías-Martínez E (2016) Mobinsight: understanding urban mobility with crowd-powered neighborhood characterizations. In: IEEE international conference on data mining workshops, ICDM (demo) 2016, Barcelona, Spain, 12–15 Dec 2016, pp 1312–1315

24.

Prado A, Plantevit M, Robardet C, Boulicaut J (2013) Mining graph topological patterns: finding covariations among vertex descriptors. IEEE TKDE 25(9):2090–2104

25.

Rozenshtein P, Anagnostopoulos A, Gionis A, Tatti N (2014) Event detection in activity networks. In: KDD, pp 1176–1185

26.

Saha TK, Hasan MA (2015) A sampling based method for top-k frequent subgraph mining. Stat Anal DM 8(4):245–261MathSciNetCrossRef

27.

Silva A, Meira W Jr, Zaki MJ (2012) Mining attribute-structure correlated patterns in large attributed graphs. PVLDB 5(5):466–477

28.

Spielman SE, Thill J (2008) Social area analysis, data mining, and GIS. Comput Environ Urban Syst 32(2):110–122CrossRef

29.

van Leeuwen M (2010) Maximal exceptions with minimal descriptions. Data Min Knowl Discov 21(2):259–276MathSciNetCrossRef

30.

van Leeuwen M, Knobbe AJ (2012) Diverse subgroup set discovery. Data Min Knowl Discov 25(2):208–242MathSciNetCrossRef

31.

Yang G (2004) The complexity of mining maximal frequent itemsets and maximal frequent patterns. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining, seattle, Washington, USA, 22–25 Aug 2004, pp 344–353

Titel: Mining exceptional closed patterns in attributed graphs
verfasst von: Anes Bendimerad
Marc Plantevit
Céline Robardet
Publikationsdatum: 06.10.2017
Verlag: Springer London
Erschienen in: Knowledge and Information Systems / Ausgabe 1/2018
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-017-1109-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2018

Dynamic affinity-based classification of multi-class imbalanced data with one-versus-one decomposition: a fuzzy rough set approach

Exploiting highly qualified pattern with frequency and weight occupancy

Tractable queries on big data via preprocessing with logarithmic-size output

OntoILPER: an ontology- and inductive logic programming-based system to extract entities and relations from text

Automatic feature selection for supervised learning in link prediction applications: a comparative study

Estimating effectiveness of twitter messages with a personalized machine learning approach