Concept description är en data mining-uppgift som strävar efter en begripligbeskrivning av koncept och klasser, inte exakta prediceringar. Syftet medstudien är att visa hur prototypbaserad klustring kan skapa förståelse för endatamängds underliggande domän, enligt concept description. Experimenthar utförts med data från pokerdomänen. Datamängden samlades in från ettlow-limit, shorthanded bord, hos en av de stora Internetsiterna för onlinepokerspel. De två experimenten utfördes med samma datamängd, men däruppsättningen attribut skiljde sig åt. Klustringen utfördes med denprototypbaserade klustringsalgoritmen K-means. För att data mining–uppgiften skulle lösas på tillfredställande vis, presenterades experimentensresultat i diagram och tabeller som var möjliga att analysera. Klustren somexperimenten resulterade i visar sig vara väl separerade. Den doldainformationen, som lyftes fram av klustringsexperimenten, kunde verifierasav domänens teori. Analysen av resultatet visade att klustring med denprototypbaserade klustringsalgoritmen K-means är en metod som går bra attanvända för att skapa förståelse i en datamängds underliggande domän. / Uppsatsnivå: D

Action formalisms based on description logics (DLs) have recently been introduced as decidable fragments of well-established action theories such as the Situation Calculus and the Fluent Calculus. However, existing DL action formalisms fail to include general TBoxes, which are the standard tool for formalising ontologies in modern description logics. We define a DL action formalism that admits general TBoxes, propose an approach to addressing the ramification problem that is introduced in this way, and perform a detailed investigation of the decidability and computational complexity of reasoning in our formalism.

Aus der Einleitung: „In this paper, we reuse the representation formalism `description graph' in order to characterize subsumption of ALN-concepts. The description logic ALN allows for conjunction, valuerestrictions, number restrictions, and primitive negation. Since Classic allows for more constructors than ALN, e.g., equality restrictions an attribute chains by the constructor SAME-AS,we can confine the notion of description graphs from [BP94]. On the other hand, ALN explicitly allows for primitive negation which yields another possibility { besides conflicting number restrictions { to express inconsistency. Thus, we have to modify the notion of canonical description graphs in order to cope with inconsistent concepts in the structural characterization of subsumption. It turns out that the description graphs obtained from ALN-concepts are in fact trees. A canonical graph is a deterministic tree. The conditions required by the structural characterization of subsumption on these trees can be tested by an eficient algorithm, i.e., we obtain an algorithm deciding subsumption of C and D in time polynomial in the size of C and D. The report is structured as follows. In the preliminaries, we define syntax and semantics of the description logic ALN as well as the inference problem of subsumption. In Section 3, we introduce description graphs, the data structure our structural subsumption algorithm is working on. Besides syntax and semantics also an algorithm for translating ALN-concepts into description graphs is given. Thereafter, we present the main result of this report in Section 6, a characterization of subsumption of ALN-concepts by a structural comparison of corresponding description graphs. Furthermore, a structural subsumption algorithm can be found in Section 6.2. In the last section we summarize our results and give an outlook to further applications of structural subsumption in terminological knowledge representation systems.

Aus der Einleitung: „Equational unification is a generalization of syntactic unification in which semantic properties of function symbols are taken into account. For example, assume that the function symbol '+' is known to be commutative. Given the unication problem x + y ≐ a + b (where x and y are variables, and a and b are constants), an algorithm for syntactic unification would return the substitution {x ↦ a; y ↦ b} as the only (and most general) unifier: to make x + y and a + b syntactically equal, one must replace the variable x by a and y by b. However, commutativity of '+' implies that {x ↦ b; y ↦ b} also is a unifier in the sense that the terms obtained by its application, namely b + a and a + b, are equal modulo commutativity of '+'. More generally, equational unification is concerned with the problem of how to make terms equal modulo a given equational theory, which specifies semantic properties of the function symbols that occur in the terms to be unified.”

Unification of concept terms is a new kind of inference problem for Description Logics, which extends the equivalence problem by allowing to replace certain concept names by concept terms before testing for equivalence. We show that this inference problem is of interest for applications, and present first decidability and complexity results for a small concept description language.

Computing the least common subsumer (lcs) in description logics is an inference task first introduced for sublanguages of CLASSIC. Roughly speaking, the lcs of a set of concept descriptions is the most specific concept description that subsumes all of the input descriptions. As such, the lcs allows to extract the commonalities from given concept descriptions, a task essential for several applications like, e.g., inductive learning, information retrieval, or the bottom-up construction of KR-knowledge bases. Previous work on the lcs has concentrated on description logics that either allow for number restrictions or for existential restrictions. Many applications, however, require to combine these constructors. In this work, we present an lcs algorithm for the description logic ALEN, which allows for both constructors (as well as concept conjunction, primitive negation, and value restrictions). The proof of correctness of our lcs algorithm is based on an appropriate structural characterization of subsumption in ALEN also introduced in this paper. / This research was carried out while the second author was still at the LuFG Theoretical Computer Science, RWTH Aachen.

Non-standard inferences are particularly useful in the bottom-up construction of ontologies in description logics. One of the more common non-standard reasoning tasks is the most specific concept (msc) for an ABox-individual. In this paper we present similar non-standard reasoning task: most specific concepts for models (model-mscs). We show that, although they look similar to ABox-mscs their computational behaviour can be different. We present constructions for model-mscs in FL₀ and FLE with cyclic TBoxes and for ALC∪∗ with acyclic TBoxes. Since subsumption in FLE with cyclic TBoxes has not been examined previously, we present a characterization of subsumption and give a construction for the least common subsumer in this setting.

Whereas matching in Description Logics is now relatively well investigated, there are only very few formal results on matching under additional side conditions, though these side conditions were already present in the original paper by Borgida and McGuinness introducing matching in DLs. The present report closes this gap for the DL ALN and its sublanguages.

Approximation is a new inference service in Description Logics first mentioned by Baader, Küsters, and Molitor. Approximating a concept, defined in one Description Logic, means to translate this concept to another concept, defined in a second typically less expressive Description Logic, such that both concepts are as closely related as possible with respect to subsumption. The present paper provides the first in-depth investigation of this inference task. We prove that approximations from the Description Logic ALC to ALE always exist and propose an algorithm computing them. As a measure for the accuracy of the approximation, we introduce a syntax-oriented difference operator, which yields a concept description that contains all aspects of the approximated concept that are not present in the approximation. It is also argued that a purely semantical difference operator, as introduced by Teege, is less suited for this purpose. Finally, for the logics under consideration, we propose an algorithm computing the difference.

Recently, the Description Logic (DL) SHIQ has found a large number of applications. This success is due to the fact that SHIQ combines a rich expressivity with efficient reasoning, as is demonstrated by its implementation in DL systems such as FaCT and RACER. One weakness of SHIQ, however, limits its usability in several application areas: numerical knowledge such as knowledge about the age, weight, or temperature of real-world entities cannot be adequately represented. In this paper, we propose an extension of SHIQ that aims at closing this gap. The new Description Logic Q-SHIQ, which augments SHIQ by additional, 'concrete domain' style concept constructors, allows to refer to rational numbers in concept descriptions, and also to define concepts based on the comparison of numbers via predicates such as < or =. We argue that this kind of expressivity is needed in many application areas such as reasoning about the semantic web. We prove reasoning with Q-SHIQ to be EXPTIME-complete (thus not harder than reasoning with SHIQ) by devising an automata-based decision procedure.