1997 AutonomousDiscovOfRelExceptRules

• (Susuki, 1997) ⇒ Einoshin Suzuki. (1997). “Autonomous Discovery of Reliable Exception Rules.” In: Proceedings of KDD Conference (KDD 1997)

Subject Headings: Exception Rule.

Quotes

Abstract

• This paper presents an autonomous algorithm for discovering exception rules from data sets. An exception rule, which is defined as a deviational pattern to a well-known fact, exhibits unexpectedness and is sometimes extremely useful in spite of its obscurity. Previous discovery approaches for this type of knowledge have neglected the problem of evaluating the reliability of the rules extracted from a data set. It is clear, however, that this question is mandatory in distinguishing knowledge from unreliable patterns without annoying the users. In order to circumvent these difficulties we propose a probabilistic estimation approach in which we obtain an exception rule associated with a common sense rule in the form of a rule pair. Our approach discovers, based on the normal approximations of the multinomial distributions, rule pairs which satisfy, with high confidence, all the specified conditions. The time efficiency of the discovery process is improved by the newly-derived stopping criteria. PEDRE, which is a data mining system based on our approach, has been validated nsing the benchmark data sets in the machine learning community.

1. Introduction

• In data mining, an association rule (Agrawal et al. 199G), which is a statement of a regularity in the form of a production rule, represents one of the most important … to its generality. An association rule can be classified into two categories: a common sense rule, which is a description of a regularity for numerous objects, and an exception rule, which represents, for a relatively small number of objects, a different, regularity from a common sense rule (Suzuki Sr. Shimura 1996) (Suzuki 1996). An exception rule exhibits unexpectedness and is often useful. For instance, the rule “using a seat belt is risky for a child”, which represents exceptions to the well known fact “using a seat belt is safe”, exhibited unexpectedness when it was discovered from car accident data several years ago, and is still useful. Moreover, an exception rule is often beneficial since it differs from a common sense rule which is often a basis for people’s daily activity. For instance, suppose a species of poisonous mushrooms some of which are exceptionally … beneficial since it enables the exclusive possession of the edible mushrooms.
• Since an exception rule holds for a relatively small number of examples, the distinction of a reliable rule from a coincidental pattern is one of the most important issues in discovering this type of knowledge. However, such distinction was left to the users in the previous discovery systems (Piatetsky-Shapiro 8~ Matheus 1994) (Klosgen 1996) (Suzuki & Shimura 1996) (Suzuki 1996). The evaluation of confidence by the users, depending on their subjective judgment, is unreliable and uncertain in case the discovered rules are numerous. In order to circumvent these difficulties we propose a novel approach in which exception rules are discovered according to their confidence level based on the normal approximations of the multinomial distributions. This approach can be called as autonomous, since an exception rule is discovered using neither users’ confidence evaluation nor domain knowledge.

Discovery Algorithm

• In our algorithm, a discovery task is viewed as a search problem, in which a node of a search tree represents a rule pair …

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1997 AutonomousDiscovOfRelExceptRules	Einoshin Suzuki			Autonomous Discovery of Reliable Exception Rules		Proceedings of KDD Conference	https://www.aaai.org/Papers/KDD/1997/KDD97-054.pdf			1997