.png){kind=icon}
.png){kind=icon}
Return
Outlier detection using default reasoning
.png){kind=icon}
PRE
AI
DOI：10.1016/j.artint.2008.07.004.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems. (c) 2008 Elsevier B.V. All rights reserved.
Keywords:
Default logic
Disjunctive logic programming
Knowledge representation
Nonmonotonic reasoning
Computational complexity
Data mining
Outlier detection
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W