<figure><img src="image_1.png" /></figure>

HAL
open science

# Attribute Exploration Algorithms on Ontology Construction

Qin Ping, Zhang Zhongxiang, Gao Hualing, Wang Ju

► To cite this version:

Qin Ping, Zhang Zhongxiang, Gao Hualing, Wang Ju. Attribute Exploration Algorithms on Ontology Construction. 6th IFIP TC 12 International Conference on Intelligent Information Processing (IIP), Oct 2010, Manchester, United Kingdom. pp.234-244, 10.1007/978-3-642-16327-2_29 . hal-01055073

HAL Id: hal-01055073

https://inria.hal.science/hal-01055073

Submitted on 11 Aug 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Attribute Exploration Algorithms on Ontology
Construction *

Qin Ping¹,², Zhang Zhongxiang¹, Gao Hualing¹, Wang Ju¹

¹ Guangxi Normal University, College of Computer Science and Information Technology, Guilin, 541004, China

² Guangxi Arts Institute, Postgraduate Affairs Office, Nanning, 530022, China
qpapple_5716@163.com

**Abstract.** Attribute exploration in FCA is proposed by Baader etc. in the past decade and it is an effective tool applying to description logics to construct ontology on Semantic Web. The authors firstly introduce attribute exploration algorithm, then investigate different cases in which the redundant computation may occur. As new results, the improved attribute exploration algorithm is proposed in terms of relevancy. We also give the proof of the completeness of the improved algorithm, and show how the proposed algorithm avoids redundancy and simplifies computation in some certain cases. We finally present the method to construct an ontology based on attribute exploration algorithm(AEOCM) on the open formal context, and specify the implementation procedure of this method in terms of instantiation.

**Keywords:** Attribute Exploration Algorithms, Description Logics, Formal Concept Analysis, Pseudo Intent, Ontology Construction

# 1 Introduction

With the development of the semantic web, we have to confront the problem on searching useful information from the mass data. The way to acquire the information which we focus on is making good use of ontology to improve the veracity and validity on searching. An ontology, the backbone of the Semantic Web, is an explicit and formal specification of a conceptualization and is consisted of finite list of terms and the relationships between these terms. A well-defined ontology should be constructed by promising approaches and assures the soundness and completeness. Therefore, how to construct a well-defined ontology becomes a hotspot on the field of intelligent information processing.

Attribute exploration, a simple but useful knowledge acquisition technique, is an important tool from Formal Concept Analysis (FCA), a mathematical theory for concepts and conceptual hierarchies. It is used to acquire knowledge from a domain expert by asking successive questions, find implication between attributes which can

*Supported by The National Natural Science Foundation of China under Grant No.60573010, 60663001; The Innovation Project of Guangxi Graduate Education under Grant No.2008M025. express the knowledge on inclusion between object sets, and get all of the intent and stem base. After the method, applying formal concept analysis to description logics
presented by Franz Baader in 2004-2007, there are some preferable results to modify
the attribute exploration to determine a minimal set of implications [1], extend both the
terminological and the assertional part of a description logic knowledge base [2],
extend the definition on conceptual description on the least common subsumer (lcs) to
background terminology [3], and show the attribute exploration algorithm to compute
the subsumption hierarchy of all lcs as well as the hierarchy of all conjunctions of
subsets of description logic concepts [4].

Nowadays, many ontologies are constructed by manual or semi-automatic work.
Attribute exploration is an efficient and automatic way to generate concept lattice and
construct ontology, and makes its goal. With the help of it, we can improve the
ontology construction methods, specially on the open semantics by asking the domain
expert to get the hierarchical relationship between attributes and objects, and find out
all of the knowledge in the domain. It is possible to share and reuse knowledge after
the ontology has built and some new knowledge is added easily.

In this paper, we firstly introduce the attribute exploration algorithm, proposed
applying formal concept analysis to description logic by Baader,etc. during the past
decade. After studying on it, we find out some redundant computation. We propose an
improved attribute exploration algorithm in terms of revelancy simplify the compu-
ting, and prove its completeness, finally propose an ontology construction method
based on attribute exploration algorithm(AEOCM), and specify the implementation
procedure of this method in terms of instantiation.

## 2 Basic definitions in formal concept analysis

Formal concept analysis (FCA) is a field of applied mathematics that aims to formalize the notions of a concept and a conceptual hierarchy by means of mathematical tools. It facilitates the use of mathematical reasoning for conceptual data analysis and knowledge processing. There are some basic definitions and theorems used in the following.

**Definition 2.1**[4,6] (Formal context) A formal context is a triple ...=(‘..,||,∂), where ‘.. is a set of objects, || is a set of attributes, and ∂□‘..□|| is a relation that associates each object o with the attributes satisfied by o.

**Definition 2.2**[4,6] (Derivation operator) Let ...=(‘..,||,∂) be a formal context. For a set of objects A□‘., we define the intent A$^Z$ of A as follows: A$^Z$={ p□||□a□A.(a, p) □∂}.

Similarly, for a set of attributes B□||, we define the extent
B$^Z$ := {o□‘.. □b□B.(o,b) □∂}.

**Definition 2.3**[6] (Formal concept) Let ...=(‘..,||,∂) be a formal context. A formal concept of ... is a pair (A,B) where A□‘., B□|| such that A$^Z$=B and B$^Z$=A. We call A the extent, and B the intent of (A,B).

**Definition 2.4**[7] (Subconcept-superconcept-relation) The subconcept-superconcept-relation is mathematized by (A₁,B₁)C (A₂,B₂):□ A₁ □A₂(B₁□B₂).

The set of all formal concepts of K together with the defined order relation is
denoted by ≅(...).
**Definition 2.5**$^{[7]}$ (Concept lattices) Let $...=(^{\cdot}, \parallel, \prec)$ be a formal context. Then $\equiv (...) $ is a complete lattice, called the concept lattice of $(^{\cdot}, \parallel, \prec)$, for which infimum and supremum can be described as follows:

$$ \bigwedge_{i \in \mathcal{I}} (A_i, B_i) = \left( \bigwedge_{i \in \mathcal{I}} A_i, \left( \bigwedge_{i \in \mathcal{I}} B_i \right)' \right), \quad \bigvee_{i \in \mathcal{I}} (A_i, B_i) = \left( \bigvee_{i \in \mathcal{I}} A_i \right)', \quad \mathbf{I} \quad (A_i, B_i) $$

**Definition 2.6**$^{[6]}$ (Implication between attributes) An implication $L \parallel R$ holds in ... if every object of ... that has all of the attributes in L also has all of the attributes in R, i.e., if $L^Z \sqsubseteq R^Z$. We denote the set of all implication that hold in ... by $Imp(...)$.

**Definition 2.7**$^{[8]}$ (Pseudo-intent) $P \sqsubseteq M$ is called the pseudo-intent of $(^{\cdot}, \parallel, \prec)$ if and only if $P \sqsubseteq P^{ZZ}$ and $Q^{ZZ} \sqsubseteq P$ holds for every pseudo-intent $Q \sqsubseteq P, Q \sqsubseteq P$.

**Definition 2.8**$^{[8]}$ (Duquenne-Guigues-Base) The set of implications $\{P \parallel P^Z \rightleftharpoons P | P \text{ pseudo-intent}\}$. We call this the Duquenne-Guigues-Basis or simply the stem base of the attribute implications.

**Theorem 1**$^{[8]}$ The set of implications $\dots: = \{P \parallel P^Z \rightleftharpoons P | P \text{ pseudo-intent}\}$ is non-redundant and complete.

**Definition 2.9**$^{[4,8]}$ (Lectic order) Let an arbitrary linear order on the set of attributes $||=\{p_1, \dots, p_n\}$, say $p_1 < \dots < p_n$. For all $j$, $1 \le j \le n$, and $B_1, B_2 \sqsubseteq ||$ we define $B_1 < B_2$ iff $p_j \sqsubseteq B_2 \rightleftharpoons B_1$ and $B_1 \sqsubseteq \{p_1, \dots, p_{j-1}\} = B_2 \sqsubseteq \{p_1, \dots, p_{j-1}\}$.

**Theorem 2** For a given attribute set $||=\{p_1, p_2, \dots, p_n\}$, which basic order is $p_1 < p_2 < \dots < p_n$ and $B \sqsubseteq P$, we denote the first element after $B$ on lectic order by $B^+$. It satisfies:

(i) existing a positive $j$ is maximal such that $p_j \sqsubseteq B$;

(ii) $B^+ = B \sqsubseteq \{p_1, p_2, \dots, p_{j-1}\} \sqsubseteq \{p_j\}$.

**Definition 2.10**$^{[4]}$ (Implication Pseudo-hull) For a subset $B$ of $||$, the implication pseudo-hull of $B$ with respect to $\mathcal{U}$ is denoted by $\mathcal{U}^*(B)$. It is the smallest subset $H$ of $||$ such that

(i) $B \sqsubseteq H$;

(ii) $B_1 \parallel B_2 \sqsubseteq \mathcal{U}$ and $B_1 \sqsubseteq H$ (strict subset) imply $B_2 \sqsubseteq H$.

**Definition 2.11**$^{[8]}$ (respect) A subset $T \sqsubseteq M$ respects an implication $A \parallel B$ if $A \sqsubseteq T$ or $B \sqsubseteq T$. T respect a set $\dots$ of implication if T respect every single implication in $\dots$.

**Definition 2.12** In the concept lattice, the length of maximal chain from concept $(A, B)$ to maximum is $^{\cdot}$, $(A, B)$ is the $^{\cdot}$ level node of lattice.

# 3 Ontology and its construction by the way of FCA

Ontologies, often defined as an explicit specification of conceptualization, are necessary for knowledge representation and knowledge exchange. Generally ontology can be formally defined by $(C, P, I, S, E)$, where $C$ refers to Class; $P$ refers to property of Class; $I$ refers to instance of Class; $S$ refers to subsumption relation and $E$ refers to other Enriched relation. In the concept lattice, the concept can be mapped to class in the ontology definition; the elements of objects in each concept can be mapped to the instance of ontology; the element of attributes will be mapped to the property of ontology and finally subsuper concept relation is equivalent to subsumption relation in ontology.$^{[9]}$

A good design ontology means that they should adequately capture the modeled domain, be understandable for human user and provide good support for machine processing. By a good definition means not only the syntax, but also the semantics.
An automated reasoning over ontologies enables to support the ontology design, intergrating and sharing ontologies automatically, determining and establishing relationships among ontologies etc.[10]

Formal Concept Analysis (FCA) is adopted in the ontology construction process to establish the taxonomic hierarchy correctly and properly, because it yields the mathematization of concepts and component ontology are explained briefly. The way to applying the formal concept analysis to ontology construction, first of all, we should model context in a research domain by topical similarity and subsumption which should expand user's search context and improve the interactive capability of traditional search engines, and develop information context. In the concept lattice, a concept will be described by a set of attributes. In this case, we can get a formal context which is a crucial step. Then we use attribute exploration based on formal context and with the help of the domain expert to construct ontology on the concept lattice and get Duquenne-Guigues Base on knowledge inference.

**4 Attribute exploration algorithm**

Attribute exploration is a method of acquiring knowledge from a domain expert by asking successive questions to expand ABox and TBox. In many application fields where the formal context is not explicitly given, but only “known” to some domain expert, it has proved to be a successful method for efficiently capturing the expert's knowledge. The superiority of attribute exploration is not only computing intents, pseudo-intents and Duquenne-Guigues Base, but also expanding counterexamples to it by domain expert to acquire complete knowledge about the application domain instead of being restricted by the given formal context.

**4.1 Attribute exploration algorithm proposed by Baader etc.**

For a given formal context, implications between attributes can express the important knowledge of subsumption between object sets. In some cases, especially impossible to list all of the subsumption, we try to compute the base of these subsumption. Using it, we can compute all of intents and stem base, which can inference all of the subsumption. The attribution exploration algorithm proposed by Baader etc. is as follows:

**Algorithm 1(Attribution exploration)**[4]

**Initialization:** One starts with the empty set of implication, i.e., $\mathcal{U}_0:=\square$, the empty set of concept intents $\coprod_0:=\square$, and the empty subcontext $\dots_0$ of ..., i.e., $^{\cdot}_{0,:}:=\square$. The analytic smallest subset of $\|\|$ is $B_0:=\square$.

**Iteration:** Assume that $\dots, \mathcal{U}_i, \coprod_i$, and $B_i(i \ge 0)$ are already computed. Compute $B_i''$ with respect to the current subcontext $\dots, i$. Now the expert is asked whether the implication $B_i \| B_i'' \rightleftharpoons B_i$ holds in $\dots$.

If the answer is “no”, then let $o_i \square^{\cdot \cdot \cdot}$. be the counterexample provided by the expert. Let $B_{i+1} := B_i, \mathcal{U}_{i+1} := \mathcal{U}_i$, and let $\dots_{i+1}$ be the subcontext of $\dots$ with $^{\cdot \cdot \cdot}_{i+1} :=^{\cdot \cdot \cdot}_{i} \square\{o_i\}$. The iteration continues with $\dots_{i+1}, \mathcal{U}_{i+1}, \coprod_{i+1}$, and $B_{i+1}$.

If the answer is “yes”, then $\dots_{i+1} := \dots_i$ and

$$ \{ (\coprod_i, \mathcal{U}_i, \square\{B_i \| B_i'' \rightleftharpoons B_i\}) \text{ if } B_i'' \square B_i \} $$
$$ (\coprod_i \square\{B_i\}, \mathcal{U}_i) \quad \text{if } B_i'' = B_i $$

To find the new set $B_{i+1}$, we start with $j=n$, and test whether

$$ B_i <_j \mathcal{U}_{i+1}^* ((B_i \square \{p_1, \dots, p_{j-1}\}) \square \{p_j\}) \quad (*) $$

holds. The index $j$ is decreased until one of the following cases occurs:

(1) $j=0$: In this case, $\coprod_{i+1}$ is the set of all concept intents and $\mathcal{U}_{i+1}$ the Duquenne-Guigues base of ..., and the algorithm stops.

(2) (*) holds for $j>0$: In this case, $B_{i+1} := \mathcal{U}_{i+1}^* ((B_i \square \{p_1, \dots, p_{j-1}\}) \square \{p_j\})$, and the iteration is continued.

By computing on this algorithm, we find out that there are some redundancies in the iterative steps. This redundancy happens in computing formula(*). When computing $B_{i+1}$, we work out the implication pseudo-hull, i.e. $\mathcal{U}_{i+1}^* ((B_i \square \{p_1, \dots, p_{j-1}\}) \square \{p_j\})$ and lectic order $<_j$. It appear this case that the same set of implication pseudo-hull is computed repeatedly when $j$ don't satisfy formula(*) and then $j:=j-1$. For avoiding the complex computation repeatedly, we try to improve the efficiency on the following.

## 4.2 the improved attribute exploration algorithm( I )

It is evident that computation the implication pseudo-hull and lectic order is rather complex. In order to resolve this problem, we can modify the way to compute $B_{i+1}$ in terms of relevancy between attribute sets and implication sets, i.e. asking that does $B_i^+$ (the next element of $B_i$ on lectic order) respect an implication $\mathcal{U}_{i+1}$, if the answer is “Yes”, let $B_{i+1} := B_i^+$, the iteration is continued; if the answer is “No”, let $B_i := B_i^+$, continue to compute the next $B_i^+$. Modify the improved algorithm as follows:

<table><caption>Table 1 Improved Attribute Exploration Algorithm</caption><thead><tr><th colspan="2">Algorithm 2 Improved attribute exploration</th></tr></thead><tbody><tr><td>1</td><td>Input: A formal context ...=(‘.,||,«)</td></tr><tr><td>2</td><td>Initialization</td></tr><tr><td>3</td><td>B<sub>0</sub>:=□ {initial empty set of implications}</td></tr><tr><td>4</td><td>Π<sub>0</sub>:=□ {initial empty set of intents}</td></tr><tr><td>5</td><td>...<sub>i=0</sub>:=□ {initial formal context, possibly empty set of objects}</td></tr><tr><td>6</td><td>‘...:=□ {initial empty set of objects}</td></tr><tr><td>7</td><td>B<sub>0</sub>:=□ {initial empty set of lectic order}</td></tr><tr><td>8</td><td>while B<sub>i</sub>≠|| do {assume ..., U<sub>i</sub>, Π<sub>i</sub>, B<sub>i</sub> (i≥0) are already computed}</td></tr><tr><td>9</td><td>Compute B<sub>i</sub>'' w.r.t. ...<sub>i</sub></td></tr><tr><td>1</td><td>Ask the expert if B<sub>i</sub>→B<sub>i</sub>''\B<sub>i</sub> holds w.r.t...?</td></tr><tr><td>1</td><td>if no then the expert provides a counterexample o<sub>i</sub>∈‘.</td></tr><tr><td>1</td><td>‘...<sub>i+1</sub>:=‘...<sub>i</sub>∪{o<sub>i</sub>}</td></tr><tr><td>1</td><td>B<sub>i+1</sub>:=B<sub>i</sub></td></tr><tr><td>1</td><td>U<sub>i+1</sub>:=U<sub>i</sub></td></tr><tr><td>1</td><td>Π<sub>i+1</sub>:=Π<sub>i</sub></td></tr><tr><td>1</td><td>...<sub>i+1</sub> {...<sub>i</sub>=(‘...<sub>i</sub>||,«<sub>i</sub>) , ‘...<sub>i</sub>⊆‘...<sub>i</sub>||<sub>i</sub>=||,«<sub>i</sub>=«□(‘...<sub>i</sub>×||<sub>i</sub>); ...<sub>i+1</sub> is a subcontext of ...}</td></tr><tr><td>1</td><td>else {yes}</td></tr><tr><td>1</td><td>...<sub>i+1</sub>:=...<sub>i</sub></td></tr><tr><td>1</td><td>if B<sub>i</sub>''≠B<sub>i</sub> then {B<sub>i</sub> is a pseudo-intent}</td></tr></tbody></table>
$$ \begin{array}{l} \text{($\Pi_{i+1}, \mathcal{U}_{i+1}$):} \quad (\Pi_i, \mathcal{U}_i \cup \{B_i \to B_i'' \setminus B_i\}) \\ \text{else} \\ \quad \text{($\Pi_{i+1}, \mathcal{U}_{i+1}$):} \quad (\Pi_i \cup \{B_i\}, \mathcal{U}_i) \\ \text{end if} \\ \text{end} \\ \text{Compute } B_{i+1} \\ \text{while } B_i \neq \| \text{ then} \\ \quad \text{Does } B_i^+ \text{ respect an implication } \mathcal{U}_{i+1}? \\ \text{if yes then} \\ \quad \quad B_{i+1} := B_i^+ \\ \text{break} \\ \text{else} \\ \quad \quad B_i := B_i^+ \\ \text{end if} \\ \text{end while} \\ \text{end if} \\ \text{end while} \\ \text{Output: } \Pi_i \mathcal{U}_i \end{array} $$

**Theorem 3** The improved attribute exploration algorithm is complete.

**Proof:** According to the algorithm, we can obtain the set $\{B_0=\Box, B_1, B_2, \dots, B_m=\|\|\}$, and $B_0<B_1<B_2<\dots<B_m$.

(1) **Initialization:** Take $B_0=\Box$ as beginning, classified discussion as follows:

If $\Box''=A_0(A_0\Box\Box)$, then $\Box$ is a pesudo-intent, $\mathcal{U}_1=\{\Box\|\|A_0\}$. The first element respecting with $\mathcal{U}_1$ after $\Box$ is $A_0$, so $B_1=A_0$ is intent. On the other hand, as $\Box$ is a pesudo-intent, any non-empty pesudo-intent must include $A_0$, similarly, $A_0$ must be included in any non-empty intent. It's known that there is any element neither intent nor pesudo-intent.

If $\Box''=\Box$, $\Box$ is a intent ($B_0=\Box$), $\mathcal{U}_1=\Box$, the first element after $\Box$ is $\{p_n\}$, $\{p_n\}$ respects $\mathcal{U}_1$, $B_1=\{p_n\}$. As $\{p_n\}$ is the next element of $\Box$ on the lectic order, there is not any element between $B_0$ and $B_1$. Now we only have to prove $B_1$ is intent or pesudo-intent: if $\{p_n\}''=\{p_n\}$, $\{p_n\}$ is intent; if $\{p_n\}''=\{p_n\}$, $\{p_n\}$ is pesudo-intent.

Above all, $B_0$ and $B_1$ is intent or pesudo-intent. Moreover there is no other intent or pesudo-intent between $B_0$ and $B_1$.

(2) **Inductive argument:** On the assumption that all of the intents and pesudo-intents less than or up to $B_i$ on lectic order have been computed, denoting that $B_1, B_2, \dots, B_i$ and ensure there is no intent or pesudo-intent between adjacent elements. Now $\mathcal{U}_{i+1}=\{P\|\|P''\rightleftarrows P\|P\}$ is pesudo-intent, $P\le B_i$. According to the algorithm, testing from the first element after $B_i$ on lectic order one by one, until acquiring the first element $B$ respecting $\mathcal{U}_{i+1}$, let $B_{i+1}=B$, now we should prove that: (i) $B_{i+1}$ is intent or pesudo-intent; (ii) There is no intent or pesudo-intent between $B_i$ and $B_{i+1}$.

Case 1: If $B=B_i^+$, i.e. $B_i^+$, the first element after $B_i$ on lectic order, respects $\mathcal{U}_{i+1}$.

Considering pesudo-intent $Q$, satisfying $Q\Box B_i^+$, we know that $\mathcal{U}_{i+1}$ includes the implication $Q\|\|Q''\rightleftarrows Q$ according to the inductive assumption above, i.e. $Q=B_k$, $k\le i$, $B_i^+$ respects $\mathcal{U}_{i+1}$. It means that $Q\Box B_i^+$ imply $Q''\rightleftarrows Q\Box B_i^+$, i.e. $Q''\Box B_i^+$. Now if $(B_i^+)^{\prime\prime}=B_i^+$, $B_i^+$ is intent; if $(B_i^+)^{\prime\prime}\Box B_i^+$, $B_i^+$ is pesudo-intent. So (i) and (ii) hold.
Case 2: If $B \sqsubseteq_B^+ B_i^+$, $B_i^+$ doesn't respect $\mathcal{U}_{i+1}$ because $\mathcal{U}_{i+1}$ is neither intent nor pseudo-intent. Is it true?

We should prove $B_i^+$ is neither intent nor pesudo-intent. Using reduction to absoluteness, considering pesudo-intent $Q$, satisfying $Q \sqsubseteq_B^+ B_i^+$, we know that $\mathcal{U}_{i+1}$ includes the implication $Q \nvDash Q'' \rightarrow Q$ according to the inductive assumption above, i.e. $Q=B_k$, $k \le i$, $B_i^+$ respects $\mathcal{U}_{\text{Ontology}}$ is evident that it contradicts with the assumption that $B_i^+$ doesn't respect $\mathcal{U}_{i+1}$. So $B_{i+1}$ is neither intent nor pseudo-intent.

Now testing the next element of $B_i^+$, $B_i^+$ either doesn't respect $\mathcal{U}_{i+1}$, or is neither intent nor pesudo-intent. There is a minimal element $B$ on lectic order, respecting $\mathcal{U}_{i+1}$. Now let $B_{i+1}=B$, there is no intent or pesudo-intent between $B_i$ and $B_{i+1}$. We should prove $B_{i+1}$ is intent or pseudo-intent, considering pesudo-intent $A$, satisfying $A \sqsubseteq_B^+ B_{i+1}$, i.e. $A \le B_{i+1}$. We know that and $\mathcal{U}_{i+1}$ includes the implication $A \nvDash A'' \rightarrow A$ according to the inductive assumption above, i.e. $A=B_i A = B_i$, $l \le i$, $B_{i+1}$ respects $\mathcal{U}_{i+1}$. It means that $A \sqsubseteq_B^+ B_{i+1}$ imply $A'' \nvDash A \sqsubseteq_B^+ B_{i+1}$, i.e. $A'' \sqsubseteq_B^+ B_{i+1}$. Now if $(B_{i+1})''=B_{i+1}$, $B_{i+1}$ is intent; if $(B_{i+1})'' \sqsubseteq_B^+ B_{i+1}$, $B_{i+1}$ is pesudo-intent. So (i) and (ii) hold.

Therefore, the improved attribute exploration algorithm is complete. ☐

## 4.3 Analysis and comparison of the two attribute exploration algorithms

Comparing with the two different algorithms, we can make this conclusion that the improved attribute exploration algorithm neither needn't compute implication pesudo-hull, nor judge whether the computed pesudo-hull satisfy formula(*) based on the definition of lectic order, but judges the next attribute set on lectic order from the view of respect to acquire the next intent or pesudo-intent. The computation with respect, implementing on the way of subsumption between sets, effectively simplify the complexity. It also avoids redundancy computation the same set repeatedly, which sometimes happened in computing the next $B_{i+1}$ in the attribute exploration algorithm proposed by Baader etc. We also prove the improved one is complete.

# 5 Ontology construction based on attribute exploration algorithm

According to the results of research, we propose a model of the method of ontology construction based on attribute exploration algorithm (AEOCM). This model includes four modules: preprocessing module, attribute exploration module, generating concept lattice module, ontology construction module. The figure of this model is as following Fig. 1.

<figure><img src="image_3.png" /></figure>
<figure><img src="image_4.png" /></figure>

## 5.1 Preprocessing module

In practice, formal context is generally not given, but extracted from data sources. As a result, we need to analyze data resources and resort to respective strategies and algorithms for different data resources to extract formal context. The main processes of preprocessing module are extracting the multi-value formal context which contains attributes and objects from data source files including text files, relational databases, XML data types and so on, and transforming multi-value formal context to single one. The preprocessing module includes two submodules: the submodule of extracting formal context, the submodule of transforming formal context.

## 5.2 Attribute exploration module

The main processes of attribute exploration module are computing intent, pesudo-intent, Duquenne- Guigues base by the ways of the improved attribute exploration algorithm after asking the expert successive questions, in order to generate formal concept lattice. The way of this module to distinguish with other algorithms computing intent and pesudo-intent, is asking the expert whether the implication holds in the given context, if the answer is “yes”, then doing the next computing in the formal context ...; if the answer is “no”, then providing counterexample to ... . In this case, it ensures that the new objects are dynamically added to the formal context and what is never expressed explicitly but on the experts’ mind, making the experts expand the knowledge base easily.
## 5.3 Generating concept lattice module

This module is mainly to generate concept lattice by the structure concept lattice algorithm according to the computed intents and draw the respective hasse graph. The up to down structure concept lattice algorithm is as follows:

**Input:** All the formal concept $\div(...)$.

**Initialization:** $\square(X,Y)\square\div(...)$ access to the set $C_{|Y|}$ according to the size of $|Y|$, then we will get the sets, such as $C_0, C_1, \dots, C_{|P|}, C_0=(||,||Z)$ is maximum.

**Iteration:** Assume $C_k=(A_k,B_k)$ is already computed.

Start from the $k$ ($k \ge 0$) level, compute as following method:

$\square(X,Y)\square C_k$, if finding $(X_i,Y_i)$ in $C_{k+1}$, satisfy $Y \square Y_i$, connect $(X,Y)$ with $(X_i,Y_i)$; if finding $(X_2,Y_2)$ in $C_{k+1}$ ($1 \le i < k$), satisfy $Y_2 \square Y$ and $X_2 \prec X$, connect $(X,Y)$ with $(X_2,Y_2)$. The interaction is continued.

Until $k=|||\||$, the algorithm stops.

**Output:** Concept lattice $\prec(\dots), \prec>$.

## 5.4 Ontology construction module

This module mainly contains constructing an ontology from above concept lattice according to the ontology generating rules, and adding other properties and restrictions practically, finally generating the ultimate ontology.

The respective ontology generating rules are as follows:

<table><caption>Table 2: The respective ontology generating rules</caption><thead><tr><th>Lattice</th><th>Description Logic</th><th>Ontology</th></tr></thead><tbody><tr><td>Attributes</td><td>Concepts</td><td>Classes</td></tr><tr><td>Objects</td><td>Instances</td><td>Individuals</td></tr><tr><td>Hierarchy of lattice</td><td>Subsumptions and equivalences between concepts</td><td>Hierarchy between classes and individuals</td></tr><tr><td>Can't be gotten directly</td><td>Hierarchy among Roles</td><td>The relations among Object Properties</td></tr><tr><td>Can't be gotten directly</td><td>Number restriction operations</td><td>Data Properties define datatype</td></tr></tbody></table>

From the table1, we can make a conclusion that the classes, individuals and their hierarchy can be found in the lattice directly, however, object properties and data properties are added manually by the constructor.

# 6 Conclusion

In recent years, the automatic methods on ontology construction become a research hotspot. Attribute exploration in FCA is an efficient tool to generate concept lattice and construct ontology, and assure to share and reuse knowledge. Through asking a domain expert question, we can add new knowledge to generate the concept lattice structure on concept hierarchy to construct ontology. In this paper, we firstly have investigated the existing attribute exploration algorithm and find its redundancy computation, then have proposed an improved attribute exploration algorithm to simplify the complexity effectively. Applying this algorithm to ontology construction, we also have proposed a model of ontology construction based on attribute
exploration algorithm (AEOCM), and elaborate the whole implement procedures in
detail according to each module. Our experience in the research has convinced us that
the study in this direction is indeed significant and should have a good prospect
both in the application and the theory. We will continue our works to find more
efficient algorithms and try to implement it in practice to construct ontology and its
automatic inference.

References

1. Gerd Stumme. Attribute exploration with background implications and exceptions[C]//In Hans-Herrmann Bock, Wolfgang Polasek, editors, Data analysis and information systems. Proceedings of the 19th annual conference of Gesellschaft fur Klassifikation e.v. University of Basel, March 8-10,1995.Berlin, Heidelberg: Springer,1996:457-469.

2. Franz Baader, Bernhard Ganter, Ulrike Sattler, et al. Completing Description Logic Knowledge Bases using Formal Concept Analysis, LTCS-Report 06-02[R].Germany, Dresden University of Technology, 2006.

3. F. Baader, Baris Sertkaya, Anni-Yasmin Turhan. Computing the least common subsumer w.r.t. a background terminology[J]. Journal of Applied Logic, 5 (2007):392-420.

4. F. Baader, B. Sertkaya. Applying formal concept analysis to description logics[C]//In P. Eklund, editor. Computer Science. Proceedings of the 2nd International Conference on Formal Concept Analysis (ICFCA), Sydney, Berlin- Heidelberg:Springer-Verlag,2004, 2961: 261-286.

5. F. Baader.Computing a minimal representation of the subsumption lattice of all conjunctions of concepts defined in a terminology[J]. Proc. Intl. KRUSE Symposium,1995,168-178.

6. Baris Sertkaya. Formal Concept Analysis Methods for Description Logics(D)

7. Rudolf Wille. Formal Concept Analysis as Mathematical Theory of Concepts and Concept Hierarchies [J]. Berlin- Heidelberg: Springer-Verlag, 2005,3626:1-33.

8. B. Ganter, R. Wille. Formal Concept Analysis: Mathematical Foundations[M]. Berlin: Springer-Verlag, 1999:79-90.

9. Haibo Jia,Julian Newman,Huaglory Tianfield.A new Formal Concept Analysis based learning approach to Ontology building[J]. http://www.mtsr.ionio.gr/proceedings/haibo.pdf

10. Marek Obitko,Vaclav Snasel, Jan Smid. Ontology Design with Formal Concept Analysis[J].CLA 2004, 111-119,2004

11. Zhang wenxiu,Wei ling,Qi jianjun. The attribute reduction theory and approach of concept lattice[J].SCIENCE IN CHINA ser.E Information Sciences,2005,35 (6):628-639.