Explaining Clusters with Inductive Logic Programming and Linked Data

Abstract

Knowledge Discovery consists in discovering hidden regularities in large amounts of data using data mining techniques. The obtained patterns require an interpretation that is usually achieved using some background knowledge given by experts from several domains. On the other hand, the rise of Linked Data has increased the number of connected cross-disciplinary knowledge, in the form of RDF datasets, classes and relationships. Here we show how Linked Data can be used in an Inductive Logic Programming process, where they provide background knowledge for nding hypotheses regarding the unrevealed connections between items of a cluster. By using an example with clusters of books, we show how di erent Linked Data sources can be used to automatically generate rules giving an underlying explanation to such clusters.

Introduction

the ones of [ 4, 6, 8 ]), few works have considered Linked Data for results interpretation (some preliminary attempts are to be found in [ 1, 7 ]). However, the former uses Linked Data only to support the user's navigation, and the latter does not take into account the whole knowledge discovery process and focuses on the interpretation of statistical data. For this reason, we aim to exploit the interconnected knowledge from Linked Data to explain patterns resulting from a clustering process, by combining the existing semantic technologies with a Machine Learning technique, i.e. Inductive Logic Programming [ 3 ], to automatically produce underlying explanations for the formation of such patterns. 2

Approach

2.1 On Inductive Logic Programming

Inductive Logic Programming (ILP) is a research eld at the intersection of Machine Learning and Logic Programming, investigating the inductive construction of rst-order clausal theories starting from a set of examples E = E + [ E [ 3 ]. While E + represents the relation to be learnt, E are the facts where the relation does not hold. The distinguished feature of ILP is the use of some additional background knowledge B about the examples in E . Believing B, and faced with the facts in E , the induction process derives an hypotheses space H. The success of the induction requires that H covers all the positive examples (H is complete) and none of the negative ones (H is consistent ), with respect to B (i.e., there is no contradiction with the facts written in B).

2.2 Proposed approach

Assuming that we have retrieved some clusters, our approach is articulated as follows (see Fig. 1): 1. Linked Data Selection. We retrieve information about the data contained in each cluster from the Linked Data cloud, across several datasets. 2. Hypotheses Generation. We generate some hypotheses using ILP. A hypothesis is an explanation (\why those items are part of that particular cluster"). 3. Hypotheses Evaluation. We validate the hypotheses using two rules evaluation measures: the Weighted Relative Accuracy (WRacc, as described in [ 5 ]), providing a trade-o between coverage and relative accuracy, that we exploit to obtain explanations for small clusters, and the very well known and Information Retrieval F-measure (F ).

Experiments

We ran our experiments on the Hudders eld's books usage dataset introduced in the rst section. Our target problem is de ned as: considering some clustered books borrowed by students from the Humanities faculty, explain what those books have in common and why they belong to a particular cluster. The manual analysis of each cluster's centroid shows that each cluster represents the books borrowed by students from the same course, such as Music Technologies, Politics or English Literature.

For each book, we retrieve some information from the Linked Data cloud. We rst use bibo:isbn10 as an equivalence property to navigate from the Hudders eld dataset to the British National Bibliography one3. From there, we retrieve information about the book using the existing Linked Data vocabularies: Dublin Core4 for topic and author, the Event Ontology5 for the publication time, place and publisher. Finally, we exploit the owl:sameAs property to navigate to the Library of Congress Subject headings6 and retrieve the broader concepts of each topic using the skos:broader property.

Clusters and the Linked Data extracted knowledge are encoded as Prolog clauses as follows:

E E + clusters clMT (`bocolkM4T'()`.bocolkM1T'()`.book 5').

RDF predicates subject(`book 1',`electronic music').

B RDF is-a relations book(`book 1'). topic(`electronic music').

Here we search the hypothesis space H speci c to the Music Technologies cluster (clMT ). E+ is composed by books in clMT (as book 1), while books in other clusters (such as book 4 and book 5) form E . The process is repeated for each cluster. Both the RDF binary relations (hud:book 1 dc:subject `electronic music') and the unary ones (hud:book 1 a bibo:book) are also transformed into Prolog clauses and then added to B.

We ran several experiments combining di erent properties (in di erent Bs), in order to see the properties impact on the hypotheses generation. These are shown in Table 1. Other hypotheses demonstrated the relations between di erent predicates, such as the relation between a publisher and a speci c topic (see Table 2). 4

Conclusion and future work

We showed how ILP can be good in generating hypotheses to explain patterns, e.g. \books borrowed by students of Music Technologies are clustered together because they talk about music". Although it is a trivial example, the automation of such a process is not an easy task. We demonstrated how the use of Linked Data is important to generate such hypotheses, and how combining di erent sources 3 http://bnb.data.bl.uk/ 4 http://dublincore.org/documents/dcmi-terms/ 5 http://motools.sourceforge.net/event/event.html 6 http://id.loc.gov/authorities/subjects.html

cl(A):-broader(A,`psychology')^pubPlace(A,`oxford') English cl(A):-publisher(A,`routledge')^broader(A,`literature') Literature ^broader(A,`philology') Politics cl(A):-publisher(A,`macmillan')^broader(A,`political science') ^broader(A,`social sciences') F (%) WRacc 10.3 0.004 of background knowledge (i.e., di erent datasets) produces better explanations of patterns of data. The future work concerns the automatic selection of the datasets from Linked Data, the use of a more appropriate evaluation measure and the generalisation of the approach to other data mining techniques.

References

1. d'Aquin , M. , & Jay , N. ( 2013 ). Interpreting Data Mining Results with Linked Data for Learning Analytics: Motivation, Case Study and Directions . In Third Conference in Learning Analytics and Knowledge (LAK) , Leuven, Belgium.

2. Fayyad , U. , Piatetsky-Shapiro , G. , & Smyth , P. ( 1996 ). From data mining to knowledge discovery in databases . AI magazine , 17 ( 3 ), 37 .

3. Muggleton , S. , & De Raedt , L. ( 1994 ). Inductive logic programming: Theory and methods . The Journal of Logic Programming , 19 , 629 - 679 .

4. Narasimha , V. , Kappara , P. , Ichise , R. , & Vyas , O. P. ( 2011 ). LiDDM: A Data Mining System for Linked Data .

5. Lavrac N. , Flach P. , and Zupan B. ( 1999 ). Rule Evaluation Measures: A Unifying View . In Proceedings of the 9th International Workshop on Inductive Logic Programming (ILP '99) . Springer-Verlag, London, UK, 174 - 185 . .

6. Paulheim , H. , & Fumkranz, J. ( 2012 , June). Unsupervised generation of data mining features from linked open data . In Proceedings of the 2nd International Conference on Web Intelligence , Mining and Semantics (p. 31 ). ACM.

7. Paulheim , H. ( 2012 ). Generating possible interpretations for statistics from Linked Open Data . In The Semantic Web: Research and Applications . Springer, pp. 560574 .

8. Verborgh , R., Van Deursen , D. , Mannens , E. , & Van de Walle, R. ( 2010 ). Enabling advanced context-based multimedia interpretation using linked data.