An Empirical Study on Property Clustering in Linked Data?

Abstract

Properties are used to describe entities, a part of which are likely to be clustered together to constitute an aspect. However, existing automated approaches to property clustering remain far from satisfactory for an open domain like Linked Data. In this paper, we rstly investigated the relatedness between properties using ve di erent measures. Then, we employed three clustering algorithms and two combination methods for property clustering. We empirically studied the property clustering on a moderate-sized sample of Linked Data and found that a proper combination of di erent measures gave rise to the best result.

Introduction

Property Relatedness Measures

To achieve property clustering, we measure the relatedness between properties from the following ve perspectives.

{ Lexical similarity between property names, denoted by RI , is based on the common characters of property names. For example, both mouth position and mouth elevation describe the mouth information of a river. We calculated RI using the I-Sub string similarity [ 3 ]. { Semantic relatedness between property names, denoted by RW , leverages WordNet to measure the semantic relatedness between properties. We used the average Lin's WordNet relatedness [ 2 ] of word pairs in property names to calculate RW . { Distributional relatedness between properties, referred to as RU , is based on the property co-occurrence in the context of an entity's RDF description, i.e. both properties are used together to describe the entity. Symmetrical uncertainty coe cient was used to compute the distributional relatedness. To estimate the probabilities of co-occurrence, the Billion Triples Challenge (BTC) 2011 dataset1 was used, in which the descriptions of coreferent URIs were merged. { Range relatedness between properties, referred to as RT , is based on the class relatedness of property ranges. For example, if two properties have the ranges delicious food and handicraft respectively, both of them deliver the tourist information of a tourist city. The range relatedness is calculated using the maximum WordNet-based relatedness RW of class pairs in property ranges. { Overlap of property values, denoted by RO, leverages the common values of two properties to compute the relatedness. The text of each property value is rstly collected, e.g. local names of URIs and lexical forms of literals after normalization, and all the terms in the text are used to construct a term frequency vector. RO is then computed using the cosine similarity of the corresponding vectors. 3

Clustering Algorithms and Combination Methods

We employed the following three well-known clustering algorithms: DBSCAN (denoted by CD), Single linkage clustering (CL) and Spectral clustering (CS ). Combining various relatedness measures helps obtain a better clustering. We employed two typical combination methods. The rst one is to rst compute property relatedness using a linear combination of di erent measures for each property pair and then carry out clustering. The second one is to rst conduct clustering based on individual measures and then aggregate these individual results using ensemble clustering. We selected consensus clustering to realize ensemble clustering and calculated it using CC-Pivot [ 1 ]. 1 http://km.aifb.kit.edu/projects/btc-2011/ We report our study of the relatedness measures, clustering algorithms and combination methods. Their clustering performance w.r.t. the golden standard was evaluated using the following ve metrics: Precision, Recall, F-Score, Rand Index and Normalized Mutual Information (NMI). All the parameters were set as the ones achieving the highest harmonic mean of F-Score.

We sampled 20 entities of di erent types in Linked Data, each of which was integrated from a DBpedia URI with its coreferent ones from 12 di erent sources2. Every entity has at least 51 properties while the maximum number is 574. The golden standard was built based on Freebase. Freebase divides properties describing similar aspects into types and groups similar types into domains. We invited three PhD candidates in the eld of Linked Data to assign each property to the most relevant /domain/type. The properties that were assigned to the same /domain/type were clustered together to form the golden standard. The Fleiss' inter-rater agreement score is 0.895, showing the strong agreement.

Table 1 depicts the average performance achieved w.r.t. di erent measures using clustering algorithms. Overall, no measure achieves the highest values for every clustering algorithm on all the measures. RI and RU generally generate better clusterings in terms of F-Score. Besides, from the third column of each table, we saw that CD is similar to CL and CS is greatly di erent from them. CD and CL usually generate better clustering results in terms of Rand Index and NMI. Table 2 shows the harmonic means of Precision, Recall, F-Score, Rand Index and NMI achieved by using single measures, linear measure combinations 2 These sources are DBpedia, DBTune, Freebase, GeoNames, LinkedGeoData, LinkedMDB, New York Times, OpenCyc, Project Gutenberg, RDF Book Mashup, The World Factbook and YAGO Clustering algorithm: CD RI RW RU RT RO :3RI + :7RU :5RI + :5RO :6RU + :4RO :3RI + :5RU + :2RO :3RI + :5RU + :1RT + :1RO :2RI + :1RW + :2RU + :5RO :2RI + :1RW + :15RU + :1RT + :45RO RI ; RU RI ; RO RU ; RO RI ; RU ; RO RI ; RU ; RT ; RO RI ; RW ; RU ; RO RI ; RW ; RU ; RT ; RO

Precision Recall F-Score Rand Index NMI .235 .273 .253 .549 .387 .215 .266 .238 .672 .441 .242 .433 .310 .644 .507 .170 .381 .235 .547 .364 .247 .137 .176 .709 .520 .218 .757 .339 .471 .379 .209 .619 .313 .411 .265 .214 .716 .330 .477 .375 .211 .883 .341 .398 .318 .205 .878 .333 .372 .277 .216 .790 .339 .438 .344 .207 .899 .337 .364 .268 .287 .148 .196 .732 .563 .331 .051 .089 .744 .566 .290 .066 .108 .755 .575 .273 .210 .237 .706 .513 .292 .102 .151 .744 .560 .290 .115 .165 .726 .548 .256 .213 .232 .677 .493 and ensemble clustering (the 13th to 19th rows). The results indicate that the linear combination of relatedness measures tends to generate a clustering that features a higher Recall compared to single measures, while ensemble clustering is recommended to use if a higher Precision is preferred. 5

Conclusion

In this paper, we studied the property clustering in Linked Data and evaluated di erent property relatedness measures, clustering algorithms and combination methods. Our experimental results demonstrated the feasibility of the automated property clustering. In future work, we will improve the quality of property clustering by leveraging user feedback and active learning.

References

1. Ailon , N. , Charikar , M. , Newman , A. : Aggregating Inconsistent Information: Ranking and Clustering . Journal of the ACM , 55 ( 5 ): 23 ( 2008 )

2. Lin , D.: An Information-Theoretic De nition of Similarity. In: ICML 1998 . pp. 296 { 304 . Morgan Kaufmann, San Francisco ( 1998 )

3. Stoilos , G. , Stamou , G. , Kollias , S.: A String Metric for Ontology Alignment . In: Gil, Y. , et al. (eds.) ISWC 2005 . LNCS , vol. 3729 , pp. 624 { 637 . Springer, Heidelberg ( 2005 )