A Hidden Markov Model-Based Approach for Lightweight Ontology Modularization Using K-Means Clustering

Ontologies are considered as the heart of the architecture of the semantic web and among the use of ontologies we have resource annotations (documents, images, videos, etc.). Formally, Gruber defined ontology as "Ontology is an explicit specification of a conceptualization" [1]. This definition was completed by Borst as “Ontology is an explicit and a formal specification of a shared conceptualization” [2]. With these definitions, we can outline that ontology is a set of concepts and axioms which describe certain domain knowledge. Hence, ontology contents are: classes or concepts, relationships (properties), instances (individuals) and axioms. Concepts represent a set of entity classes within the domain. Relationships specify the interaction among classes. Instances indicate the concrete examples of classes within the domain and axioms denote statements which are always true [3]. The construction of these ontologies follows a life cycle whose essential points are specification, conception, implementation, validation and maintenance. Validation step requires reasoning on the knowledge represented and maintenance step needs a probable evolution. Most of ontologies thus built are monolithic, that is to say, the concepts of these ontologies are in a single block and one concept can be linked to any concept. With this type of ontologies, especially if they contain several concepts (large) or are complex in their organization, it is sometimes difficult to ensure scalability or to conduct efficient reasoning. With a plethora of ontologies for the same domain, the authors opt for a reuse of part of ontology to keep persistent definitions of the concepts, which is not easy with monolithic ontologies, if so it is necessary to reuse all the ontology. To deal with these difficulties on monolithic ontologies, the authors opt for modular ontologies either by composition (building small independent partitions of ontologies and merging them) or by decomposition (partitioning monolithic ontologies into coherent modules) [4]. Regardless of the axis chosen, it must follow the goals concerning scalability for querying data and efficient reasoning on ontologies, scalability for evolution and maintenance, complexity management, understandability, context-awareness, personalization and reuse. These goals are more described in studies [4-6] and maintain by evaluation criteria outlined in the study of d’Aquin et al. [7], such as correctness, completeness, connectedness, module cohesion, richness of representation, which are applied for technique validation.

In the literature, we distinguish five categories of ontology modularization techniques subdivided into two groups according to the chosen axis. The axis of composition of ontology modules includes Distributed Description Logics, ε-Connexions, Package-based Descriptive Logics and the Conservative Extensions and for the axis of decomposition we have Graph-based Ontology Segmentation [4]. In the field of Graph-based Ontology Segmentation, five approaches [8-12] have been illustrated and the best known are PATO [8] and OAPT [11] which are interested in the partitioning of hierarchically organized concepts. However, these ontology segmentation approaches come up against limits, in particular the redundancy of ontology concepts in the modules, the manual assignation of isolated concepts to the modules, the merging of modules whose number of elements does not reach the fixed threshold and sometimes lack of semantics.

Since managing knowledge represented by ontologies using machine learning tools becomes increase, authors introduced possibility to capture ontology characteristics through hidden Markov Model (HMM) [13] and proposed in the study of Warda et al. [14] an approach to turn ontology into HMM based on ontology triples produced by SPARQL queries on it.

As a result, this study aims to propose a method to modularize lightweight ontologies using machine learning technique more precisely the hidden Markov model. Ontology axioms are avoided in this approach and then heavy ontologies are not considered because they are characterized with axioms. However, if heavy ontologies are used, axioms are not handled. Ontology triples are extracted within ontology through SPARQL queries and are used to initialize a HMM parameters such as states transition probabilities distribution matrix, symbols observation probabilities distribution matrix and initial states probabilities distribution vector via some equations. Ontology concepts are considered as HMM states and ontology relationships as HMM symbols. Since partitioning ontology consists in dividing its concepts into partitions, only the state transition probability distribution matrix of the HMM will be used as input for the K-Means algorithm to compute ontology modules. The rest of this paper is organized as follow: state of the art regarding HMM definition and related works are described in Section 2. The proposed method is detailed in Section 3. Section 4 focuses on experimental findings and discussion. The last Section is devoted to the conclusion and potential future trends and challenges.

The Figure 1 describes the steps of this approach.

1.png

Figure 1. HMM-based process of ontology partitioning

3.1 Step 1: Transformation of ontology into HMM

Ontology can be seen as a set of triples. A triple is a (subject, predicate, object) set where subject and object are classes; predicate denotes the relationship between subject and object. Various methods for learning ontology properties using HMMs have been discussed in the study by Warda et al. [14]. The following step is adapted from their findings [14]:

(1) Firstly, they extracted ontology triples. These triples derived from SPARQL queries. Triples can be filter according to the type of predicate.

(2) Secondly, they labelled obtained triples to replace concepts and predicates names (string type) by numbers to facilitate manipulations.

(3) Thirdly, they initiated HMM parameters with the labelled triples using Eqs. (1)-(3).

$a_{i j}=\frac{\text { number of triples }(\mathrm{i}=\text { subject and } \mathrm{j}=\text { object })}{\text { number of triples }(\mathrm{i}=\text { subject })+\varepsilon}$           (1)

In Eq. (1), $a_{i j}$ is the ratio of the number of ontology triples where concept i is the subject and concept j is the object by the number of ontology triples having concept i as the subject. This ratio corresponds to the probability that there are relations between the concepts numbered respectively with i and j consequently it is the probability that there is transition moving from the states i to j of the HMM.

$b_j(k)=\frac{\text { number of triples }(\mathrm{j}=\text { subject and } \mathrm{k}=\text { predicate })}{\text { number of triples }(\mathrm{k}=\text { predicate })+\varepsilon}$               (2)

Similarly, in Eq. (2), $b_j(k)$ corresponds to the ratio of the number of ontology triples where concept j is the subject and relationship k is the predicate. This ratio is the probability that there are relations resulting from the concept numbered by j consequently it is the probability of observing the symbol k in state i of the HMM.

$\pi_i=\frac{\text { number of triples }(\mathrm{i}=\text { subject })}{\text { total number of triples }+\varepsilon}$            (3)

In the same manner, in Eq. (3), $\boldsymbol{\pi}_i$ corresponds to the ratio of the number of ontology triples where concept i is the subject by the total number of ontology triples. This ratio is the probability that the concept numbered with i is the subject of the triples and consequently it is the probability that i is an initial state of the HMM.

Since $a_{i j}, b_j(k)$ and $\pi_i$ are probabilities distributions, by adding ε to the denominator of Eqs. (1)-(3), probabilities laws are not satisfied. Hence the rest value to reach 1 is equitably redistributed to each of them.

All these steps are more detailed in the study of Warda et al. [14] and this approach has been used here to turn ontology into HMM.

3.2 Step 2: Clustering

In this step, states transition matrix (A) of obtained HMM is used as a set of vectors in which the clustering algorithm should be applied. The following configurations are considered:

(1) The transition matrix (A) of the obtained HMM is divided into set of vectors: $A=\left[A_j\right], 1 \leq j \leq N$, where $A_j=$ $\left[a_{i j}\right], 1 \leq i \leq N$, is a vector.

(2) The set of states, $S=\left\{S_1, S_2, \ldots, S_N\right\}$, is equivalent to the set of ontology concepts coming from the SPARQL queries. States are independent because associate concepts are different.

(3) For each $S_j, 1 \leq j \leq N$, component of $S$, we can obtain all the transition probabilities to other states. These probabilities correspond to the vector $A_j$ of transition matrix. Hence $\left\langle S_1, S_2, \ldots, S_N\right\rangle$ is considered as a basis where each vector $A_j$ can be expressed.

(4) Clustering algorithm is then applied and vectors to be partitioned are $A=\left[A_j\right], 1 \leq j \leq N$. Appropriate distance measures and number of clusters can be defined.

Among the clustering algorithms described by Xu et al. [28, 29], K-Means is the most widely used in the literature for ontology segmentation. The organization of the data (concepts) to be partitioned represented by the different vectors from the HMM incidence matrix (A) conforms to the K-Means input. We could not apply the hierarchical grouping because in addition to the hierarchical organization, the ontology concepts are linked by other relations like object Property type. So our focus was on K-Means and distance measures can be changed to analyse the behaviour of the results. Several distance measures can be applied: Euclidean, Cosine Similarity, Dice, etc. The optimal number of clusters is obtained by the Elbow method integrated to the K-Means algorithm [30].

3.3 Step 3: Validation

This step consists to validate the proposed approach. Several criteria come from software engineering and are outlined in d’Aquin et al. [7] and some of them can be applied:

Independence: the proposed approach partitions a set of concepts generated by ontology triples. The resultant clusters are independent according to K-Means algorithm.

Local correctness and local completeness: all concepts inside each module and its signature generated by this approach belonged to the huge used ontology because the triples were generated within this ontology.

Size: Since Elbow method is used to determine the number of clusters, the size of each module is consequently related to the organization of target ontology.

Intra-module distance and connectedness: since the components $\mathrm{a}_{\mathrm{xy}}$ of vectors are probabilities distributions, if this value rich 1, it means that class represented by x and class represented by y are strongly linked with a certain predicate (hierarchical link or object property). To ensure this validation metric, we defined a value of module distance:

$W_M=\frac{1}{m} \sum_{x, y \in M} a_{x y}$           (4)

In this formula, M is the module which the intra-module is computed and m is the number of elements in module M. If $W_M$ reach 1 then the module is coherent. At the end, for all modules, we defined a weight W which refers to the average of their intra-module distances:

$W=\sum_{k=1}^K W_k$             (5)

where, K is the number of modules obtained by the Elbow method before partitioning huge ontology. This value gives the degree of the modules quality.

Non-redundancy: intrinsically, this criterion is ensured by the proposed approach. All modules are disjoined according to the description of this methodology.