Linked Open Data has been recognized as a valuable source for background information in data mining. However, most data mining tools require features in propositional form, i.e., binary, nominal or numerical features associated with an instance, while Linked Open Data sources are usually graphs by nature. In this paper, we compare di erent strategies for creating propositional features from Linked Open Data (a process called propositionalization), and present experiments on di erent tasks, i.e., classi cation, regression, and outlier detection. We show that the choice of the strategy can have a strong in uence on the results.
Linked Open Data [
Most data mining algorithms work with a propositional feature vector representation of the data, i.e., each instance is represented as a vector of features hf1; f2; :::; fni, where the features are either binary (i.e., fi 2 ftrue; f alseg), numerical (i.e., fi 2 R), or nominal (i.e., fi 2 S, where S is a nite set of symbols). Linked Open Data, however, comes in the form of graphs, connecting resources with types and relations, backed by a schema or ontology.
Thus, for accessing Linked Open Data with existing data mining tools,
transformations have to be performed, which create propositional features from the
graphs in Linked Open Data, i.e., a process called propositionalization [
Our hypothesis in this paper is that the strategy of creating propositional features from Linked Open Data may have an in uence on the data mining result. For example, promiximity-based algorithms like k-NN will behave di erently depending on the strategy used to create numerical features, as that strategy has a direct in uence on most distance functions.
In this paper, we compare a set of di erent strategies for creating features from types and relations in Linked Open Data. We compare those strategies on a number of di erent datasets and across di erent tasks, i.e., classi cation, regression, and outlier detection.
The rest of this paper is structured as follows. Section 2 gives a brief overview on related work. In section 3, we discuss a number of strategies used for the generation of propositional features. Section 4 introduces the datasets and tasks used for evaluation, and provides a discussion of results. We conclude with a review of our ndings, and an outlook on future work. 2
In the recent past, a few approaches for propositionalizing Linked Open Data
for data mining purposes have been proposed. Many of those approaches are
supervised, i.e., they let the user formulate SPARQL queries, which means that
they leave the propositionalization strategy up to the user, and a fully automatic
feature generation is not possible. Usually, the resulting features are binary, or
numerical aggregates using SPARQL COUNT constructs [
A similar problem is handled by Kernel functions, which compute the
distance between two data instances. They are used in kernel-based data mining and
machine learning algorithms, most commonly support vector machines (SVMs),
but can also be exploited for tasks such as clustering.. Several kernel functions
suitable for Linked Open Data have been proposed [
When creating features for a resource, we take into account the relation to other resources. We distinguish strategies that use the object of speci c relations, and strategies that only take into account the presence of relations as such. 3.1
Some relations in Linked Open Data sources play a speci c role. One example are rdf:type relations assigning a direct type to a resource. A statement r +64 other relations
dbpedia:Industrial_rock dbpedia:New_Wave_music +7 more
rdfs:subclassOf rdfs:subclassOf dbpedia-owl:genre
rdfs:subclassOf rdfs:subclassOf
owl:Thing dbpedia:Artist dbpedia:Person dbpedia:Artist dbpedia:MusicArtist rdf:type
dbpedia:Trent_Reznor
dbpedia-owl:instrument
dbpedia:Piano
dbpedia:Guitar
+19 more
rdf:type C is typically translated into description logics as C(r), i.e., rdf:type
is treated di erently from any other predicate. For some datasets, similar
relations exist, e.g., the dcterms:subject relations in DBpedia [
For such relations, we propose three strategies: { Creating a binary feature indicating presence or absence of the relation's object. { Creating a relative count feature indicating the relative count of the relation's object. For a resource that has a relation to n objects, each feature value is n1 . N { Creating a TF-IDF feature, whose value is n1 log jfrjC(r)gj , where N is the total number of resources in the dataset, and jfrjC(r)gj denotes the number of resources that have the respective relation r to C.
The rationale for using relative counts is that if there are only a few relations of a particular kind, each individual related object may be more important. For example, for a general book which has a hundred topics, each of those topics is less characteristic for the book than a speci c book with only a few topics. Thus, that strategy takes into account both the existence and the importance of a certain relation.
The rationale for using TF-IDF is to further reduce the in uence of too general features, in particular when using a distance-based mining algorithm. Table 1 shows the features generated for the example depicted in Fig.1. It can be observed that using TF-IDF implicitly gives a higher weight to more speci c features, which can be important in distance-based mining algorithms (i.e., it increases the similarity of two objects more if they share a more speci c type than a more abstract one). Generic relations describe how resources are related to other resources. For example, a writer is connected to her birthplace, her alma mater, and the books she has written. Such relations between a resource r and a resource r0 are expressed in description logics as p(r; r0) (for an outgoing relation) or p(r0; r) (for an incoming relation), where p can be any relation.
In general, we treat incoming (rel in) and outgoing (rel out) relations. For such generic relations, we propose four strategies: { Creating a binary feature for each relation. { Creating a count feature for each relation, specifying the number of resources connected by this relation. { Creating a relative count feature for each relation, specifying the fraction of resources connected by this relation. For a resource that has total number of P outgoing relations, the relative count value for a relation p(r; r0) is de ned as nPp , where np is the number of outgoing relations of type p. The feature is de ned accordingly for incoming relations { Creating a TF-IDF feature for each relation, whose value is nPp log jfrj9r0:p(r;r0)gj , N where N is the overall number of resources, and jfrj9r0 : p(r; r0)gj denotes the number of resources for which the relation p(r; r0) exists. The feature is de ned accordingly for incoming relations.
The rationale of using relative counts is that resources may have multiple types of connections to other entities, but not all of them are equally important. For example, a person who is mainly a musician may also have written one book, but recorded many records, so that the relations get di erent weights. In that case, he will be more similar to other musicians than to other authors { which is not the case if binary features are used.
The rationale of using TF-IDF again is to reduce the in uence of too general relations. For example, two persons will be more similar if both of them have recorded records, rather than if both have a last name. The IDF factor accounts for that weighting. Table 1 shows the features generated from the example in Fig. 1.
We evaluated the strategies outlined above on six di erent datasets, two for each task of classi cation, regression, and outlier detection. 4.1
The following datasets were used in the evaluation:
{ The Auto MPG data set1, a dataset that captures di erent characteristics
of cars (such as cyclinders, transmission horsepower), and the target is to
predict the fuel consumption in Miles per Gallon (MPG) as a regression
task [
For the classi cation and regression tasks, we use direct types (i.e., rdf:type) and DBpedia categories (i.e., dcterms:subject), as well as all strategies for generic relations. For the outlier detection tasks, we only use direct types and generic relations, since categories do not exist in the other LOD sources involved. An overview of the datasets, as well as the size of each feature set, is given in Table 2.
For classi cation tasks, we use Nave Bayes, k-Nearest Neighbors (with k=3), and C4.5 decision tree. For regression, we use Linear Regression, M5Rules, and k-Nearest Neighbors (with k=3). For outlier detection, we use Global Anomaly Score (GAS, with k=25), Local Outlier Factor (LOF), and Local Outlier Probabilities (LoOP, with k=25). We measure accuracy for classi cation tasks, rootmean-square error (RMSE) for regression tasks, and area under the ROC curve (AUC) for outlier detection tasks. 1 http://archive.ics.uci.edu/ml/datasets/Auto+MPG 2 https://github.com/vinaykola/twitter-topic-classifier/blob/master/ training.txt
The evaluations are performed in RapidMiner, using the Linked Open Data
extension [
For each of the three tasks we report the results for each of the feature sets, generated using di erent propositionalization strategies. The classi cation and regression results are calculated using strati ed 10-fold cross validation, while for the outlier detection the evaluations were made on the partial gold standard of 100 links for each of the datasets.6
Table 3 shows the classi cation accuracy for the Cities and Sports Tweets datasets. We can observe that the results are not consistent, but the best results for each classi er and for each feature set are achieved using di erent representation strategy. Only for the incoming relations feature set, the best results for the Cities dataset for each classi er are achieved when using the Binary strategy, while for the Sports Tweets dataset the best results are achieved when using Count strategy. We can observe that for most of the generic relation feature sets using TF-IDF strategy leads to poor results. That can be explained with the fact that TF-IDF tends to give higher weights to relations that appear rarely in the dataset, which also might be a result of erroneous data. Also, on the Cities dataset it can be noticed that when using k-NN on the incoming relations feature set, the di erence in the results using di erent strategies is rather high. 3 https://marketplace.rapid-i.com/UpdateServer/faces/product_details.
xhtml?productId=rmx_weka 4 http://data.dws.informatik.uni-mannheim.de/propositionalization_ strategies/ 5 http://dws.informatik.uni-mannheim.de/en/research/
rapidminer-lod-extension 6 Note that we measure the capability of nding errors by outlier detection, not of outlier detection as such, i.e., natural outliers may be counted as false positives.
Table 4 shows the results of the regression task for the Auto MPG and Cities datasets. For the Auto MPG dataset, for M5Rules and k-NN classi ers the best results are achieved when using Relative Count and TF-IDF for all feature sets, while the results for LR are mixed. For the Cities dataset we can observe that the results are mixed for the types and categories feature set, but for the generic relations feature sets, the best results are achieved when using Binary representation. Also, it can be noticed that when using linear regression, there is a drastic di erence in the results between the strategies.
Table 5 shows the results of the outlier detection task for the
DBpediaPeel and DBpedia-DBTropes datasets. In this task we can observe much higher
di erence in performances when using di erent propositionalization strategies.
We can observe that the best results are achieved when using relative count
features. The explanation is that in this task, we look at the implicit types
of entities linked when searching for errors (e.g., a book linked to a movie of
the same name), and those types are best characterized by the distribution of
relations, as also reported in [
By analyzing the results on each task, we can conclude that the chosen propositionalization strategy has major impact on the overall results. Also, in some cases there is a drastic performance di erences between the strategies that are used. Therefore, in order to achieve the best performances, it is important to choose the most suitable propositionalization strategy, which mainly depends on the given dataset, the given data mining task, and the data mining algorithm to be used.
When looking at aggregated results, we can see that for the classi cation and regression tasks, binary and count features work best in most cases. Furthermore, we can observe that algorithms that rely on the concept of distance, such as k-NN, linear regression, and most outlier detection methods, show a stronger variation of the results across the di erent strategies than algorithms that do not use distances (such as decision trees). 5
Until now, the problem of nding the most suitable propositionalization strategy for creating features from Linked Open Data has not been tackled, as previous researches focused only on binary, or in some cases numerical representation of features. In this paper, we have compared di erent strategies for creating propositional features from types and relations in Linked Open Data. We have implemented three propositionalization strategies for speci c relations, like rdf:type and dcterms:subject, and four strategies for generic relations. We conducted experiments on six di erent datasets, across three di erent data mining tasks, i.e. classi cation, regression and outlier detection. The experiments show that the chosen propositionalization strategy might have a major impact on the overall results. However, it is di cult to come up with a general recommendation for a strategy, as it depends on the given data mining task, the given dataset, and the data mining algorithm to be used.
For future work, additional experiments can be performed on more feature sets. For example, a feature sets of quali ed incoming and outgoing relation can be generated, where quali ed relations attributes beside the type of the relation take the type of the related resource into account. The evaluation can be extended on more datasets, using and combining attributes from multiple Linked Open Data sources. Also, it may be interesting to examine the impact of the propositionalization strategies on even more data mining tasks, such as clustering and recommender systems.
So far, we have considered only statistical measures for feature representation without exploiting the semantics of the data. More sophisticated strategies that combine statistical measures with the semantics of the data can be developed. For example, we can represent the connection between di erent resources in the graph by using some of the standard properties of the graph, such as the depth of the hierarchy level of the resources, the fan-in and fan-out values of the resources, etc.
The problem of propositionalization and feature weighting has been
extensively studied in the area of text categorization [
Furthermore, some of the statistical measures can be used as feature
selection metrics when extracting data mining features from Linked Open Data. For
example, considering the semantics of the resources, the IDF value can be
computed upfront for all feature candidates, and can be used for selecting the most
valuable features before the costly feature generation. Thus, intertwining
propositionalization and feature selection strategies for Linked Open Data [
In summary, this paper has revealed some insights in a problem largely overlooked so far, i.e., choosing di erent propositionalization for mining Linked Open Data. We hope that these insights help researchers and practicioners in designing methods and systems for mining Linked Open Data.
The work presented in this paper has been partly funded by the German Research Foundation (DFG) under grant number PA 2373/1-1 (Mine@LOD).