Service similarity is crucial to service discovery, selection, composition, and even execution. Especially semantic service discovery aims to locate the best matched service, it mostly depends on the measurement of the similarity between an user's service requirements and the profiles of published services. Currently, the semantic Ontology languages for services, such as the OWL-S1 and the WSMO2 , are required to semantically represent service capabilities, including non-function information (including Qos of service), functional information (IOPE of services operations, denoting input, output, precondition and effect). The ser-vice discovery, therefore, focuses on the matchmaking of service capability [15] and QoS, while less work is done on ontology-based services selection.
Moreover, Ontology receives great attention in the progressively emerging Semantic Web [2] and Semantic Web Services [6], by formally defining the concepts and relationships in a machine understandable way and enabling knowledge sharing and reuse. As the elements of the representation of semantic services, the similarity of the ontologies used is crucial to service similarity, especially when considering the discovery and execution.
Ontology similarity which is related to Ontology mapping is a well known topic in information retrieval, database integration systems, and artificial intelligence fields. Also, there is a wealth of work on similarity measures of Ontology concepts and concept-related notions [19]. However, the measurement of similarity of ontologies and concepts itself is not easy, additionally many specific features (see section 2.2) in Semantic Web Service description environment.
After surveying the previous Ontology similarity measures and their application situations, in our SWS context two methods are combined to adapt to calculate the semantic distance of single formal Ontology concepts, e.g. code and zip in the examples of figure 1. The approaches are a fuzzy-weighted associative network (edge-based measure) and an information-theoretical approach (contentbased measure).
Also regarding the compound ontology concepts in semantic service context, for example, in figure 1 the concepts findZipCodeDistance and CalcDistTwoZipsKm, are not the formal single terms as the ones in WordNet 4 , in this case the traditional method (e.g. edit distance of strings) is not useful to measure their semantic similarity. Therefore, we refine the hierarchical clustering algorithm to calculate the distance of two compound concept terms, similar to [7,4].
In this paper we aim to solve the ontology similarity in a semantic service environment. First, we differentiate two cases of service ontology concepts: single and compound ontology concept to measure their similarity in service context. Then, a hybrid Ontology-similarity measurement is proposed by combining and refining three existing methods. Finally, we define our ontology similarity-based model as sim S = Σsim O ∈ [0, 1] to improve the service selection; This model fuzzily and quantitatively measures the service similarity basing on service ontology similarity.
This paper is structured as follows. In Section 2 we state the occurring problems of Ontology in Semantic Web Service description context, and investigate the specific name features of ontology concept. A Ontology concept distance definition and three refined ontology similarity algorithms are discussed with examples of single formal term and compound term in Section 3. The service similarity measurement is defined in Section 4. In Section 5 and 6 we respectively discuss related works, and give conclusion and indications for future work.
In order to illustrate the challenge of measuring the similarity of semantic Web services, we extract a set of zip code related services from the dataset of OWL-S annotated Web Services of the University College Dublin 3 . In Figure 1., there are snatch description of four services, which are used for looking up a zip code or calculating the distance between two places according to the given zip codes. The information shown is retrieved from the wsdl documents of the respective service.
Current service matchmaking algorithms normally focus on measuring the syntactic (as service name, service text description and so on) and semantic (as service capabilities) of service. Taking sws4 and sws5 of Figure 1 as examples, if we assume that zip and code have the similar meaning, intuitively, by comparing service name and operation name, service sws4 and sws5 are regarded as similar from the signature level; and by matching their operation, as both opera-tion2, they also have similar inputs and outputs, so that sws4 and sws5 are concluded as similar services. This means that 4 WordNet, an online lexical reference system, http : //wordnet.princeton.edu/ 3 The Semantic Web Services Repository at the Smart Media Institute in University College Dublin, http : //moguntia.ucd.ie/repository/. Further, if we assume that a machine can understand some similarity between {zip, ZipCode, Zip Code 1, code, code1} and {CaleDisT woZipsKm, f indZipCode Distance}, then intuitively and naively from the above example services of Figure 1, we know that sws1:operation1 is similar to sws5:operation1; sws2:operation1 is similar to sws3:operation2 and sws4:operatio2; and sws3:operation1 is similar to sws4:operation1.
Obviously, similarity, whether syntactic or semantic, the matching of ontology concepts used in service description is a critical challenge. If a machine can not understand the meaning of service concepts, it also cannot infer the imply relationships, then the automatic matching and discovery of services is impossible.
Intuitively and in ontology-related work, when ontology terminology is mentioned, it mostly means the terms in thesauri, e.g., Wordnet. On the other hand, the ontology terms defined in applications is very different from the formal words. Generally, the ontology concept used in service semantic descriptions are most compound terms, which are named depending on service developers by their ontology knowledge, experience and wonted. The situation is made worse by the following practices (parts of examples from Fig. 1.):
Abbreviations Names are not given in their correct forms, but shortened, e.g. CalcDistTwoZipsKm;
Associated words with capitalization or delimiters Words have the form of associations of several words parts (full word or abbreviation) with delimiters, normally a part's first letter capitalized, and sometimes also using underscore, dash or space, e.g., LogIn, AcctName, ArrivalAirport In.
Words with suffix and prefix Examples are hasFlavour, locatedIn.
Variations or misspelling Names may be variations of word often due to grammatical flexion, e.g., Booking, madeFromGrape; And defined words are in misspelling format for machine.
Free inventions Any other cases the traditional similarity measures (based, e.g., on WordNet) are prevented to work.
Considering the above compound concept terms, the existing ontology measure algorithms can not work. Moreover, the data clustering algorithm from data mining field can be borrowed to apply to this case. This paper enhances the clustering algorithm in [4] to measure the semantic closeness of composed terms.
3 Ontology Similarity
To semantically measure Ontology concept distance, we should consider both concept structure and concept content. Fortunately, both of these information are prolifically provided by service description. Here, we define the semantic distance dis of the assumed concepts C and D (which could be single formal term or compound term) as:
where Dis s is the distance basing on the structure of concept in service Ontology, the Dis i basing on the common contents shared by concepts, and the Dis c is only used to measure the compound concept terms by clustering concepts, basing on the concept elements co-occurrence. Formulae 1 not only considers the different concept naming features, but also make up the loss of any single approach, because the service description context is just a structure and a short piece of text, not a corpus or thesaurus.
In the following sections, we will present the detail explanation of every distance measurement.
Concepts in a hierarchical taxonomy are all related by certain relationships, based on which concepts can be represented in an associative network consisting of nodes and edges, where nodes denote concepts, edge denotes the binary relationship of the two linked concepts. Also for service description Ontology, such associative network with fuzzy-weighted value on each link can be constructed, in which the similarity of concepts can be measured by the shortest distance as [5] and [17], which is defined as Dis s in our context.
As the detailed explanation by [5] and correspondence to OWL-Lite, we define four concept relations as generalization (e.g., superclass), specification (e.g., subclass), negative association (e.g., disjoined) and positive association (e.g., equivalent).
Therefore, the distances of arbitrary two nodes in the network can be calculated based on Tables 1-3 [17]. In Table .1 s, g, p and n represent explicit relationships, that is, each two notes relationship can be evaluated basing on triangular norms. τ in Table 2. are the triangular norms (t-norms), which is defined in Table3, where α or β are fuzzy-weighted strength values of relations (0 ≤ α, β ≤ 1), n is the degree of dependence (−∞ ≤ n ≤ ∞) between the relationships, details please refer to [9]. In the tables those fields are marked with X for which there is no definition. Therefore, the relationship of two arbitrary concepts can easily be inferred by traveling through the associative network.
Table 3. T-norms function
The definition of similarity between the concepts C and D relates to the concepts' commonality and difference [11]:
where common(C, D) is a proposition that states the commonalities between C and D, I(common(C, D)) is the amount of information contained in this proposition and, similarly, I(description(C, D)) is a proposition describing what C and D are. In our service context, we refine the similarity expression as follows to calculate the distance Dis i :
where C and D are two Ontology concept classes of OWL-Lite, |C ∩ D| is the number of common elements of C and D, e.g., the number of shared attributes, instances and relational classes, γ and δ are weight values defining the relative importance of their non-common characteristics.
Given two single-form Ontology concept terms from two differen Web service description, as t 1 and t 2 , which are respectively described by a set of other class terms as their properties, instances and relational members (e.g., "g,s,n,p"). There are two cases:
• Two terms t 1 and t 2 are organized in one hierarchical structure, which is transformed to a fuzzy weighted associative network of Section 3.2.
Reconsidering the example in Fig. 1, it assumes that in the Zip service application domain, terms have the relationships (which are all experimental data, not the real value) cp.Fig. 2. For example, the distance of term State and Zip is examined, the shortest path is path = {State, P lace, Code, Zip} with State =⇒ g,0.9 P lace, P lace =⇒ p,0.9 Code and Code =⇒ s,0.9 Zip. So that it hold that τ 2 (τ 2 (0.9, 0.9)0.9) = 0.729), following Table 1 • Terms, t 1 and t 2 , are concept classes, respectively conof a set of properties and instances as ontology vocabulary according to Section 3.
Clustering is also a well known approach group data on the basis of a certain similarity criteria. We adapt this clustering mechanism here to group the compound Ontology concept terms, which are from different service description Ontologies, e.g. findZipCodeDistance and Cal-cDistTwoZipsKm, in order to calculate their similarity by the distance dis c .
In the clustering algorithm, the association rule of two terms t 1 and t 2 is defined as follows [4]:
where, the support s is the probability s = P (t 1 ) = Tt 1 T that t 1 occurs in T , T is the cardinality of the ontology terms' domain, T t 1 is the cardinality of the set which contains t 1 , the confidence c is the occurrence probability of t 2 in the case that t 1 occurred, i.e., c = P (t
, with T t 1 ,t 2 is the cardinality of the set containing both t 1 and t 2 . The distance of two terms is weighted by their conditional probability c. The center of a cluster is the term which has the highest occurrence probability of the cluster.
In detail, including the natural language term extraction the clustering algorithm is used by us as follows:
1. Read service description document .owl, move all OWL-Lite tags, extract names and parameters, and delete redundancies in the vocabularies. The result is a bag of unique words including composted concept terms, denoting T = {t 1 , t 2 , ...}.
2. Preprocess all composted terms in T as follows.
Suppose that t i ∈ T is a composite term, we split it up on the basis of its delimiters, such as capital letters, into several parts. Then, we deal with each part towards extracting the word stem by removing stop words, suffixes and prefixes, restituting abbreviations or correcting misspelling, deleting redundant vocabulary terms and so on, resulting in the set t i = {t i1 , t i2 ...}. Substituting t i by all t ij ∈ t i for all i, ultimately yields T .
3. Compute the values s and c for any two terms in T , store them into a table in descending order, cluster them on the basis of their confidence c ≥ τ c and support s ≥ τ s (τ s and τ c are thresholds either assigned or obtained experimentally), resulting in the set T = (X 1 , X 2 , ..., X k ) of k clusters.
Roughly speaking, X i , 1 ≤ i ≤ k is a cluster including those terms whose co-occurrence probabilities exceed the threshold τ c . In traditional agglomeration clustering algorithms, T is an intermediate result, while in our context we should improve it in order to find an optimal clustering for our computation. This is the rationale of the algorithm's further steps.
In each X i ⊆ T , remove the frequent and rare parameters to avoid the query expansion and over-fitting problems, which are discussed in the field of information retrieval [8].
5. Split and merge the clusters in T , in order to wipe off the noise terms and optimize clusters by agglomerating terms according to concentric circularities with different radii.
The inner circularity consists of those terms, which are, at least, close to half of the other terms. Similarly, the terms in the outer circularity are, at least, close to a quarter of the other ones. They are called them 1 2 radius [4]. And wiping off the terms, which are not in any circularity.
For example, to merge two cluster X 1 and X 2 , when ∀i ∈
Now, when calculating the distance between two random composite terms, here we used c 1 and c 2 distinctively, first, preprocess them using step (2) to obtain c 1 = {c 11 , c 12 , ...} and c 2 = {c 21 , c 22 , ...}, and then measure their similarity dis c by the probability of pairs of two terms to occur in the same cluster. As measure the maximum, minimum or or mean may be employed. Here we take the maximum as the optimistic way, the formula is as follows,
otherwise.
(
Obviously, such a formula implies as extreme case, that is, all of the sub-terms of c 1 and c 2 have been wiped off as the noise words, such case have no way to scale the distance of ontology concepts. This part of work is right what our experiment will analysis, to evaluate the frequency of its occurrence.
Similarity of ontologies has widely been researched, e.g., in the fields of information retrieval, artificial intelligence, databases, and especially in data mining and web mining. Many similarity measures are applied, e.g., Bernstein et al. in [3] use two ways to measure the semantic similarity of objects in an ontology, which are organized in a hierarchical ontology structure, viz., the edge-based [10] (a shorter path from one node to the other) and the node-based [14] (the notion of shared information content) approach. Actually, they present five different distance measures of ontologies, where ontology distance stands for the shortest path through a common ancestor in a directed acyclic graph. However, computational degree and weight of edge are not considered. The vector space approaches computing cosine or Euclidean distances of k-dimensional vectors [1,13] do not easily apply to nominal concepts, as it is difficult to represent them as vectors. The Full-text Retrieval Method (TF/IDF) is mostly used in information retrieval [1] to compare documents, which are considered as bags of words. However, it is inadequate for structure concepts as semantic relations between them are ignored.
The work most closely related to ours are the studies on ontologies in the semantic web or in semantic web services, such as [7,4] and [12]. While they consider to cluster the similar terms, and most recur to TF/IDF to measure concept similarity, we follow Dong's notion of name clustering agglomeration algorithms. Maedche et al. also propose an approach to cluster ontology-based data, using the hierarchical clustering algorithm to consider instances of concept similarity. Hau et al. elaborate a metric to measure the similarity of semantic services annotated with OWL ontologies. They mainly depend on the information-theoretic approach to match similar ontology instances. Doan et al. computes the common information content of ontologies to scale their similarity. We combine multiple approaches to adapt to SWS environments. Based on a study of definitions and features of ontologies expressed in OWL, and from a computational point of view, we calculate the distance of two ontologies.
Ontology similarity is unquestionable important for Semantic Web Service similarity when we consider the semantic service discovery, selection, composition, and even execution. This paper tries to propose a ontology similaritybased approach to measure service similarity and presents the primary work on it. The contributions of this paper are summarized as, 1) analysis the ontology similarity problem in semantic service context, and classify the ontology concept name features used by service description; 2) present a hybrid ontology concept distance method, and further to measure the service similarity.
As the complexity of ontology-based service similarity, under our model, there is still a lot left for our future work, including the set matching of the ontology-based concept and its type, also the detailed implementation and evaluation. However, fortunately the preliminary experiments show that this new methodology works well.