For the validation of ontologies, test cases can be applied. In order to ease the acquisition of such test cases, automatic methods can be used. This paper introduces such an approach to unit testing of ontologies using subgroup discovery methods. The tests are given by small ontologies, which will be compared to an existing ontology. The generation of the test ontologies uses subgroup discovery methods to derive concepts and relations from real data which refers to the ontology. For each concept of the ontology, we apply subgroup discovery in order to identify subgroup patterns consisting of concepts that are (un-)correlated with the target concept. Then, subgroups with very high (or low) confidence will be selected for the testing ontology. We exemplify the approach using real-world data from the ophthalmology domain, and present first results and experiences of a case study demonstrating the test case generation process.
Not only ontology learning [
One prominent method for the validation of knowledge systems considers the
utilization of test cases, e. g., [
Intuitively, we identify candidates for derivable axioms using patterns that have a
high share of a certain target concept, i. e., the concepts making up the description of
the pattern show a (strong) correlation with the target concept. Likewise, we obtain
candidates for non-derivable axioms by constructing relations for which we are sure
that they are not observed in the data. That is, for the validation of an ontology O, we
apply two test ontologies as in [
Below, we first introduce some background before we sketch our novel approach for the generation of automatic test cases. After that, we provide a case study using realworld data from the ophthalmology domain. The data is extracted from anonymized surgery sheets which are filled in by the eye specialist itself. These sheets include structured data like which eye was medicated or which medicine was used. We demonstrate the test case generation process, and discuss first experiences and implications. 2
In this section, we briefly summarize necessary notation and basic concepts on subgroup discovery and the proposed approach for ontology validation using test ontologies. 2.1
Formally, a database DB = (I; A) is given by a set of individuals I and a set of attributes A. A selector or basic pattern sel ai=vj is a Boolean function I ! f0; 1g that is true if the value of attribute ai 2 A is equal to vj for the respective individual. The set of all basic patterns is denoted by S. For a numeric attribute anum selectors sel anum2[minj;maxj] can be defined analogously for each interval [minj ; maxj ] in the domain of anum. The Boolean function is then set to true if the value of attribute anum is within the respective range.
Definition 1. A subgroup description or (complex) pattern sd is given by a set of basic patterns sd = fsel 1; : : : ; sellg ; where sel i 2 S, which is interpreted as a conjunction, i.e., sd (I) = sel 1 ^ : : : ^ sel l, with length(sd ) = l.
Without loss of generality, we focus on a conjunctive pattern language using nominal attribute–value pairs as defined above in this paper; internal disjunctions can also be generated by appropriate attribute–value construction methods, if necessary. Definition 2. A subgroup (extension)
sg sd := ext (sd ) := fi 2 Ijsd (i) = trueg is the set of all individuals which are covered by the pattern sd .
As search space for subgroup discovery the set of all possible patterns 2S is used,
that is, all combinations of the basic patterns contained in S. For the practical
implementation, we utilize the VIKAMINE platform [
The interestingness of a pattern is determined by a quality function, that is selected according to the analysis task.
Definition 3. A quality function q : 2S ! R maps every pattern in the search space to a real number that reflects the interestingness of a pattern (or the extension of the pattern, respectively).
While a large number of quality functions has been proposed in literature, many
quality functions for a single target concept, e. g., in the binary or numerical case,
tradeoff the size n = jext(sd )j of a subgroup and the deviation tsd t0, where tsd is the
average value of a given target concept in the subgroup identified by the pattern sd and
t0 the average value of the target concept in the general population. In the binary case,
the averages relate to the share of the target concept. Then, this is equivalent to the
concept of confidence commonly used in the field of association rule mining, e. g., [
For subgroup discovery, typical quality functions are of the form qa(sd ) = na (tsd t0); a 2 [0; 1] : For binary target concepts, this includes, for example, the weighted relative accuracy for the size parameter a = 1 or a simplified binomial function, for a = 0:5. An extension to a target concept defined by a set of variables can be defined similarly, by extending common statistical tests.
The result of a subgroup discovery task is then the set of k (subgroup) patterns sd 1; : : : ; sd k ; where sd i 2 2S with the highest interestingness according to the quality function. For our experiments in test ontology generation, we applied the simplified binomial function q0:5 described above that conventiently balances the size of the subgroup with a high target share of the target concept. 2.3
For the unit testing of ontologies, we adopt the approach proposed by Vrandecic and
Gangemi [
i 8Ai+ 2 T + ; O j= Ai 8Ai 2 T
:
In this framework, the specific axioms themselves can be considered as atomic test cases for the ontology that need to be formalized accordingly. In the next section, we describe our approach for generating these axioms in an automatic fashion. 3
In the following, we first provide an overview on the proposed approach, before we discuss the test ontology generation in detail and present an algorithm for this task. 3.1
The basic idea of test ontology generation using subgroup discovery is the following: We start with all relevant test concepts contained in ontology O and map these to our test instances contained in the dataset. Then, for each target concept t 2 S, we discover subgroups according to the total selector set S using a specific quality function (we used q0:5 in our experiments). After that, we map these subgroup patterns to axioms that are integrated in the testing ontologies T + and T , respectively. For that step, we create complex classes for each selected subgroup pattern. 3.2
For generating test ontologies from the subgroup discovery results, we map (un-)correlated patterns to the axioms of T + and T , respectively. Intuitively, when generating the according axioms using the discovered subgroup patterns, there must be a value which decides which subgroup is used and which not. There are several strategies for selecting the respective subgroup patterns used for creating the axioms. Below, we consider two variants: A confidence-based approach, and a test-coverage-based one. 1. A simple variant is a confidence-based approach. According to the share of the target concept in the subgroup, i. e., its confidence, we use the respective confidence of a subgroup to decide whether it should be used for the test ontology or not. If the confidence is higher than a specific threshold, it is used as for the T + ontology. If the confidence is below a specific other threshold, it is used for the T ontology. The threshold for T has to be very low or zero, because otherwise the test will also fail for the same dataset. Therefore it is also possible to define that not all of the test cases in the T ontology have to pass. It would be suitable if for example eight out of ten test cases pass to let the whole test pass. 2. An alternative approach is test-coverage-based and will be described using an example. For a specific target value two subgroups were detected. These subgroups only contain three different selectors. Subgroup one, for example, contains selector A and B and subgroup two contains selector A and C. In our example we add the two subgroups to the test ontology. In reality we would use a quality function to rate them and only add for example the five best subgroups to the test ontology. Back to our example with the two subgroups: If an ontology contains the target value and is connected with two out of three selectors it would be a coverage of 23 . With this approach we also need a threshold which decides if the test will pass or not. If this threshold would be 13 , our test in the example would have passed.
In our algorithm presented below, we use the described confidence-based approach, because it is easier to implement in this initial stage. In the future, we also plan a testcoverage-based approach to compare the results. 3.3
For the automatic generation of the described test ontologies we developed the algorithm shown in Listing 1.1. It uses subgroup discovery to derive interesting correlations and transforms them to small test ontologies consisting of complex classes.
Listing 1.1: Algorithm in pseudo code 1 for each attribute{ 2 subgroupset = findSubgroups(attribute) 3 candidatesTplus = [], candidatesTminus = [] 4 for each subgroup in subgroupset{ 5 if subgroup.confidence >= thresholdPlus 6 candidatesTplus.add(subgroup) 7 if subgroup.confidence <= thresholdMinus 8 candidatesTminus.add(subgroup) 9 10 11 } } makeComplexClasses(candidatesTplus, candidatesTminus) In the first step, subgroup discovery is performed for each attribute of the dataset. Therefore, the current attribute t 2 S is used as target value. For each target variable a set of subgroups is calculated. Each set contains all subgroups with the appropriate target variable.
Each subgroup in the set that exceeds a certain confidence threshold is added as a test candidate to the positive test candidate set (candidatesTplus). If the confidence is under a specific different threshold. In this case the subgroup is added to the negative candidate set (candidatesTminus). Thus each attribute has its own two test candidate sets, which contain all test cases for the specific attribute. A test candidate consists of any number of selectors that are associated by the AND function. This combination of selectors is characteristic for the target variable related to a high confidence and therefore will be added to the positive test candidate set. If we consider the exemplary “vehicle”-domain, for example, then the target variable “vehicle type = tricycle” has the significant describing combination of the selectors “number of wheels = 3” and “engine = false”.
For the generation, we use the confidence as a threshold. From the test candidate set a complex class is created for each attribute. This set is composed of the individual test candidates concatenated by the OR function. Thus generated complex classes will be compared or tested against an existing ontology in the next step. This section demonstrates the proposed approach using real-world data and presents first results. It covers the ontology structure and the working on the generation of T + ontologies. 4.1
In order to verify our approach we used anonymised operative reports from the cataract
surgery domain to set up a dataset for testing. We have extracted the structured data
from the data sheets. All records were reduced, encoded, typed and converted to a
suitable format. Finally, after the data wrangling the latest version of the test dataset for this
work contained more than 500 instances described by 80 attributes. As output format
“ARFF”(Attribute-Relation File Format) was used, which is an input format for data
mining tools like WEKA or VIKAMINE. For subgroup discovery, the VIKAMINE
platform was used, because WEKA does not support subgroup discovery out of the box.
The VIKAMINE system offers a rich-client environment for subgroup discovery and
analytics [
The output ontology follows a specific order. A cataract ontology[
The attribute value is stored in the instances of the specific attribute. A visualisation
of the the instances of the attribute “Pupille” (German for pupil) is shown in Figure 2.
This attribute has three possible values: “weit”, “eng” and “mittel”. For each value there
is a corresponding instance of the attribute with the matching data property. For the data
property the relation “hasValue” is used. As an example the instance “PupilleMittel” of
type “Pupille” has a data property “hasValue” with the value “mittel”.
Below, we describe first exemplary results of our proof-of-concept implementation of
the proposed approach. In the basic setting for subgroup discovery we applied the BSD
algorithm [
After performing subgroup discovery and constraining the subgroup description length to one concept for each attribute of our dataset we pick up exemplary the target value “Patient_unruhig = true” which means that the patient is nervous and in a state of agitation during the surgery. One of the subgroups from the derived amount of subgroups which fulfill the quality limit in this case is “Sedativum = true”. That is no surprise because one of possible logical consequences for the operating surgeon could be to sedate the patient. The resulting subgroup from the corresponding dataset confirms this practice. The identified pattern can now be used to generate a test case for the cataract ontology because we know there is a correlation with a certain quality limit between the above mentioned items. Incrementing the description length to two concepts yields further patterns, for example, “Diabetes = true” is described among other descriptions by the combination of concepts “Infusion_Lidocain = false” and “Gerinnungshemmer = true”. In this way further test cases can be created to extend our test ontology by mapping the identified patterns to a complex class.
Our first results and experiences in the case study demonstrate, that the proposed
approach is working well. It is a very transparent process for test ontology generation
since the subgroup patterns can be directly inspected, cf. [
In this paper, we have presented a novel approach for the automatic generation of test
ontologies. Using subgroup discovery, we identify patterns that are mapped to axioms
in our testing ontology. In particular, these are formalized using complex classes which
can then be directly implemented in unit testing manner. We demonstrated the basic
concepts in a case study using a real-world dataset. Currently, our proof-of-concept
implementation focuses on a confidence-based strategy for test ontology generation.
We aim to investigate the approach further for generating more complex testing
ontologies (T + and T ) and to apply a test-coverage-based approach in order to have
fine-grained control when a testing ontology passes or fails. Furthermore, the presented
basic approach can then also be extended using semi-automatic strategies, e. g., cf. [