To leverage on KDD architectures designed for business databases, original unbounded RDF data has to be transformed. We report on a use case consisting in adaptation of linked data, around a nucleus of public procurement data, for a data mining challenge event. The generic problems addressed are: linked data sampling; (generalised) concise bounded description extraction; propositionalisation to CSV using SPARQL SELECT; and aggregation behaviour assigned by checking conformance to eligibility criteria formulated as SPARQL queries.
The discipline of Knowledge Discovery in Databases (hereafter KDD) emerged
in early 1990s, and was characterized, among other, as a \non-trivial process of
identifying valid, novel, potentially useful and ultimately understandable patterns
from data" [
In order to leverage on the power of scalable KDD architectures originally designed for business (or, e.g., public sector) databases, original `unbounded' RDF data has to be transformed to a suitable shape and format. We report on an ongoing process of such transformation, aiming at designing a benchmark for mainstream KDD technologies that could bene t from available LD. We speci cally elaborate on two aspects of the transformation: data sampling (extraction of a manageable RDF graph from the large set of interconnected data) and data propositionalization (which brings the data within the reach of tools that cannot handle multiple interlinked tables at a time), which includes data regularization (making it expressible in a concise form in a conventional format such as CSV). The transformation attempts to explore some new paths, such as a generalized form of the so-called concise bounded description in RDF extraction; it should be however noted that this kind of technological contribution is so far unproven to overcome pre-existing research; therefore, an (at least) equally important aspect of the research contribution is the nature of the core dataset used: public procurement data being substantially di erent from traditional, mostly encyclopaedic, linked data sources addressed in semantic data mining projects.
The paper is structured as follows. Section 2 explains the nature of the core dataset. Section 3 and 4 are devoted to the two crucial phases of the construction of the benchmark dataset: sampling and propositionalization. Finally, Section 5 surveys some related research and Section 6 wraps up the paper. 2
The public procurement domain is fraught with numerous opportunities to corruption, while also o ering a great potential for cost savings through increased e ciency. For example, it is estimated that the public procurement market accounts for 17,3 % of EU's GDP (as of 2008) [12], hence optimization in this area, including detection of fraud and manipulative practices, truly matters.
For this reason we started to build a benchmark dataset, primarily for the sake of a prospective rst edition of a Linked Data Mining Challenge (LDMC) to take place this year.1 The challenge will feature 1. A descriptive task, aiming at hypotheses to be further investigated by domain experts; 2. Two predictive tasks, speci cally, { prediction of the number of tenders submitted for a particular call { classi cation of a public contract as multi-contract (conjoining goods/services of dissimilar nature).
The datasets prepared for the tasks of LDMC will consist of UK+US public procurement data, interlinked to data from the Linked Open Data Cloud2 such as DBpedia.3 3
The rst part of preparation of a benchmark dataset for data mining on LD consists in extracting a sample. A key question that arises when sampling linked 1 As part of the DMoLD'13 workshop, see http://keg.vse.cz/dmold2013/. 2 http://lod-cloud.net/ 3 http://dbpedia.org/ data is the de nition of resource representation. Due to the unbounded nature of LD resources, there is no single or straightforward solution for determining the boundaries of resource representation that would t all purposes. For example, representations meant for user interfaces commonly include resource labels. Our goal however was to provide a resource representation suited for KDD. For this purpose of which we came up with a generalised version of the established notion of concise bounded description (CBD). CBD [13] de nes the scope of resource representation as including the outbound triples, i.e., those having the resource in the subject position, while for every such triple having either a blank node or an instance of rdf:Statement in its object position the CBD of its object is included recursively. There are several CBD variations such as the symmetric concise bounded description (SCBD) that adds inbound triples for which the described resource is used in the object position. The speci cation of CBD acknowledges that the description may span over multiple resources, however it does so in a rudimentary way by overloading the semantics of blank nodes and rei ed triples to delimit the boundaries of the description.
For many practical tasks a higher-level view of `entities', rather than that
of individual resources an entity may be composed of, is more appropriate.
Hausenblas [
To re ect this intuition we propose the generalised concise bounded description (GCBD), which extends the scope of CBD to cover all resources that are marked up as `dependent' on the described resource (entity). GCBD is a representation of a resource that includes both outbound triples and inbound triples, but adds such triples recursively for all dependent resources, i.e., resources that carry data speci c to an entity. This includes both resources identi ed with blank nodes and instances of classes a priori annotated as dependent. The dependency can be detected either at syntactical level, e.g., for triples rei ed using rdf:Statement, or at semantic level, e.g., for rei ed n-ary relationships identi ed in a manual or semi-automatic manner, for example, using the PURO ontological backrgound model [14] (where the annotation is assumed to be carried out at the level of vocabulary using a Protege plugin). The choice of classes to annotate as dependent thus proceeds from a particular use case; it may include a common core, such as classes from the RDF namespace, and a use-case-speci c part containing annotations of domain ontologies and vocabularies.
GCBD can be implemented as a SPARQL CONSTRUCT query with a transitive subquery that expands the description through dependent resources. Such class annotations are loaded into a separate named graph that is then referenced in the sampling queries. A straightforward way would be to attach annotations directly to RDF classes; however, since the type of instances may not be present described resource dependent resource literal blank node resource generalised concise bounded description resource dependent resource literal filtered domain resource
resource literal resource
GCBD boundary resource literal external linked data in source data (and we do not want to materialize it via rdfs:range inference) we opted in for attaching the annotations through properties.
Sampling the resource representations for the benchmark dataset is then straightforward. The sampler is given a SPARQL endpoint URL, a SPARQL SELECT query template to retrieve the resources of interest, a list of URIs of named graphs to sample data from, a target named graph URI, access credentials to allow SPARQL Update operations, the sample size and the preferred language tag to be used for sampling the labels. After checking if any data matches the provided requirements, the sampler extracts a randomly selected subset of resources. Consequently, for each resource in the subset its entity description is inserted into the target named graph via a SPARQL Update request.
Since we are dealing with linked data, the sample data retrieved via a SPARQL endpoint may be combined with data available through resolving linked URIs of resources from external datasets. In the course of sampling, we only collect links already present in linksets created by executing Silk4 linkage rules inside the ODCleanStore framework.5 We issue a SPARQL query that computes an intersection of the sample data with relevant linksets and produces a list of external URIs, which may be optionally narrowed down to include only URIs from domains of interest. Linked resources on the list are harvested using LDSpider,6 performing a breadth- rst crawl, and loaded into the sample named graph. The extent of GCBD and associated linked data is depicted in gure 1.
Propositionalization in KDD means transforming relational data into a single
table with a set of propositions in the form of attribute-value pairs [7]; some
structural information is thus lost in aggregations and some relationships in data
discarded. Owing to the malleable nature of RDF and exibility of SPARQL,
linked data can be propositionalized via the SPARQL SELECT query form,
allowing to transform graph-shaped data into the tabular format [
The conformance of a property with the criteria is schema-agnostic: rather than from the property de nition in its vocabulary, it is empirically inferred from the way the property is used in the processed dataset, primarily from its cardinality (assuming it is higher than one). Basic aggregations may be accomplished with in-built SPARQL aggregates, including COUNT, SUM, MIN, MAX, AVG and GROUP CONCAT. SPARQL SAMPLE selects a random binding in a nondeterministic fashion, which makes it inappropriate for our purposes. With the exception of COUNT and GROUP CONCAT, SPARQL aggregations are intended to be applied primarily on numeric values, therefore the eligibility criterion for such aggregations contains a FILTER with the isNumeric function. A simple measure to fold multiple values into one is to choose a `default' or `preferred' value (with the SPARQL IF functional form or COALESCE function). For example, in multilingual datasets such approach may be used to pick a literal value with a preferred language tag, in the case of labels.
While the rich structure of LD makes automation of aggregation di cult, it can be, on the other hand, exploited for `smart' aggregations. For instance, generalization to a common broader concept may be applied if the property range values come from hierarchically structured taxonomies or partonomies (e.g., skos:ConceptSchemes) [8]. Resource descriptions can also be expanded through the linked resources' URI references, since if a property has a non-literal range, the aggregation behaviour may be recursively applied to its object values; for example, n-ary relationships can be decomposed into multiple columns. A question is then how the graph traversal depth should be set, especially when it comes to traversing linked external resources. In our case, the traversal boundaries are established by the scope of the sample (as de ned using GCBD) or can be set arbitrarily when crawling the linked resources. Properties could also be equipped with manually selected aggregation behaviour expressed in the SPIN SPARQL syntax,8 which supports basic SPARQL aggregations and allows to express arbitrary queries.This approach opens an opportunity for further research
on the use of machine learning to assign the aggregation behaviour automatically. Another challenge requiring further research is to specify how to handle properties with heterogenous ranges (e.g., mixing literal and URI references). 5
The related research can be divided into data mining approaches applied to public procurement data on the (semantic) web and data mining on semantic web data in general.
Even though there seems to be much to gain by applying data mining methods in the procurement domain in connection with LD, relatively few projects explored it. One such undertaking is the Linked Open Tenders Electronic (LOTED) project [15]. LOTED tripli ed data from RSS feeds published by Tenders Electronic Daily, an European Commission portal aggregating public procurement data from the EU member states. After converting the data to RDF and linking it, LOTED was able to apply lightweight data analysis methods and showcase interactive visualizations. Furthermore, Monteiro [9] applied data mining for outlier detection to spot fraud in Portuguese public procurement. However, in this case the data used were structured in XML and it took into account only a limited subset of data including contract description and award price.
In terms of applying semantic data in data mining, Liu [8] provided a
general outline for incorporating semantic technologies in data mining, such as with
semantic annotation. Kiefer et al. [
In general, there are two ways to facilitate data mining on linked data. First, transform data to a form more familiar to the existing data mining tools, thus lowering the barrier to applying established data mining methods. Second, to move the KDD tools closer to linked data, so that they can work with it natively. Although we presume that a more attractive opportunity lies, in long term, with data mining tools exploiting the rich structures of graph-shaped data (e.g., RDF) directly, we selected to explore the rst approach. While the transformation of linked data to tabular format entails serious information loss, this approach has at least two positive aspects: 1) e cient processing of data that is already regularly structured (such as the core LDMC dataset harvested from the centralized public contract servers) is preserved, and, 2) business analysts can interact with familiar tools and thus fully exploit their competence.
In the above-described work we experimented with transforming highlyrelational linked data into a propositional dataset. Such transformation is, necessarily, a lossy process that `downgrades' RDF into a tabular format, while giving up some of the structural information and materialized relationships. This approach is a subject to trade-o between the extent of data loss and ease of use with existing data mining software. Consequently, our further work needs to validate whether such approach yields data that is easily amenable to data mining tools or if it produces data crippled to such an extent that few insights may be discovered in it. We also plan to compare the added value of GCBD compared to CBD, applied in the extraction phase, in terms of the mining result quality. Acknowledgment The research has been partially supported by the EU ICT FP7 under No. 257943, LOD2 project. 7. Lachiche, N. (2013): Propositionalization. In Encyclopedia of Machine Learning.
Springer. 8. Liu, H. (2010): Towards Semantic Data Mining. In ISWC'2010. Online: http://ix.
cs.uoregon.edu/~ahoyleo/research/paper/iswc2010.pdf. 9. Monteiro, J. A. (2011): The Guardian of the Republic: A conceptual system to detect outliers on Public Contracts. In Proceedings of the 6th Doctoral Symposium on Informatics Engineering. Online: http://paginas.fe.up.pt/~prodei/dsie11/ images/pdfs/s1-2.pdf. 10. Paulheim, H., Fuernkranz, J. (2012): Unsupervised generation of data mining features from linked open data. In: International Conference on Web Intelligence, Mining, and Semantics (WIMS12). 11. Potoniec, J, Lawrynowicz, A. (2011): RMonto: Ontological extension to RapidMiner. In: Poster and Demo Session of the ISWC 2011 { 10th International Semantic Web Conference, Bonn, Germany. 12. Study on the evaluation of the Action Plan for the implementation of the legal framework for electronic procurement (Phase II): Analysis, assessment and recommendations. Version 3.2. 9 July 2010. Online: http://ec.europa.eu/internal_ market/consultations/docs/2010/e-procurement/siemens-study_en.pdf. 13. Stickler, P.: CBD - Concise Bounded Description. W3C Member Submission 3
June 2005. Online: http://www.w3.org/Submission/CBD/. 14. Svatek V., Homola M., Kluka J., Vacura M. (2013): Metamodeling-Based Coherence Checking of OWL Vocabulary Background Models. In: Proc. OWLED'13, Montpellier, to appear. 15. Valle, F., d'Aquin, M., Di Noia, T., Motta, E. (2010): LOTED: Exploiting Linked Data in Analyzing European Procurement Notices. In KIELD'2010. Online: http: //ceur-ws.org/Vol-631/paper6.pdf.