Data processing: artificial intelligence – Machine learning
Reexamination Certificate
1998-02-19
2002-01-01
Chaki, Kakali (Department: 2762)
Data processing: artificial intelligence
Machine learning
C704S224000, C342S064000, C342S383000
Reexamination Certificate
active
06336106
ABSTRACT:
BACKGROUND OF THE INVENTION
a) Technical Field
The present invention relates generally to a system and method for partitioning a real-value attribute having values associated with a first class and a second class into ranges, and more specifically to a system and method for partitioning an attribute into at least three ranges, wherein the values within a lower range and an upper range generally correspond to a first class of results and the values within a middle range generally correspond to a second class of results.
b) Background Art
Expert systems are used to mimic the tasks of an expert within a particular field of knowledge or domain, or to generate a set of rules applicable within the domain. In these applications, expert systems must operate on objects associated with the domain, which may be physical entities, processes or even abstract ideas. Objects are defined by a set of attributes or features, the values of which uniquely characterize the object. Object attributes may be discrete or continuous.
Typically, each object within a domain also belongs to or is associated with one of a number of mutually exclusive classes having particular importance within the context of the domain. Expert systems that classify objects from the values of the attributes for those objects must either develop or be provided with a set of classification rules that guide the system in the classification task. Some expert systems use classification rules that are directly ascertained from a domain expert. These systems require a “knowledge engineer” to interact directly with a domain expert in an attempt to extract rules used by the expert in the performance of his or her classification task.
Unfortunately, this technique usually requires a lengthy interview process that can span many man-hours of the expert's time. Furthermore, experts are not generally good at articulating classification rules, that is, expressing knowledge at the right level of abstraction and degree of precision, organizing knowledge and ensuring the consistency and completeness of the expressed knowledge. As a result, rules which are identified may be incomplete while important rules may be overlooked.
Still further, this technique assumes that an expert actually exists in the particular field of interest. Furthermore, even if an expert does exist, the expert is usually one of a few and is, therefore, in high demand. As a result, the expert's time and, consequently, the rule extraction process can be quite expensive.
It is known to use artificial intelligence within expert systems for the purpose of generating classification rules applicable to a domain. For example, an article by Bruce W. Porter et al.,
Concept Learning and Heuristic Classification in Weak
-
Theory Domains
, 45 Artificial Intelligence 229-263 (1990), describes an exemplar-based expert system for use in medical diagnosis that removes the knowledge engineer from the rule extraction process and, in effect, interviews the expert directly to determine relevant classification rules.
In this system, training examples (data sets which include values for each of a plurality of attributes generally relevant to medical diagnosis) are presented to the system for classification within one of a predetermined number of classes. The system compares a training example with one or more exemplars stored for each of the classes and uses a set of classification rules developed by the system to determine the class to which the training example most likely belongs. A domain expert, such as a doctor, either verifies the classification choice or instructs the system that the chosen classification is incorrect. In the latter case, the expert identifies the correct classification choice and the relevant attributes, or values thereof, which distinguish the training example from the class initially chosen by the system. The system builds the classification rules from this information, or, if no rules can be identified, stores the misclassified training example as an exemplar of the correct class. This process is repeated for training examples until the system is capable of correctly classifying a predetermined percentage of new examples using the stored exemplars and the developed classification rules.
Other artificial intelligence methods that have been used in expert systems rely on machine induction in which a set of induction rules are developed or induced directly from a set of records, each of which includes values for a number of attributes of an object and an indication of the class of the object. An expert then reviews the induced rules to identify which rules are most useful or applicable to the classification task being performed. This method has the advantage of using the expert in a way that the expert is accustomed to working, that is, identifying whether particular rules are relevant or useful in the classification task. It should be noted, however, that all of the relevant attributes of the objects being classified must be identified and data for those attributes must be provided within the records in order for the system to induce accurate and complete classification rules.
A book chapter written by W. Buntine, D. Stirling, Interactive Induction, in
Machine Intelligence
, Vol. 12, pp. 121-137 (Hayes-Michie et al. eds., 1990), discloses that expert systems which use machine induction can be operated with greater accuracy if a domain expert interacts with the system by supplying additional subjective knowledge before classification rules are induced or by incrementally evaluating and validating the rules that are induced. Specifically, the domain expert can develop domain grammar which can be used to elicit relevant classification rules, suggest potential rules and identify whether particular induced rules are strong or weak in the domain context.
A classic example of a pure machine induction technique is described in an article by J. R. Quinlan,
Induction of Decision Trees
, 1 Machine Learning 81-106 (1986), the disclosure of which is hereby incorporated by reference herein. This technique searches through relations between combinations of attribute values and classes of objects to build an induction tree which is then used to generate precise classification rules. Referring to
FIG. 1
herein, an exemplary Quinlan-type induction tree is constructed for a set of 100 records, each associated with an object having one of two classes C
1
or C
2
and attribute values A_
1
or A_
2
, B_
1
or B_
2
, and C_
1
or C_
2
for three attributes A, B and C, respectively.
During operation, the Quinlan method calculates a statistical measurement, referred to as an information gain value, for each of the attributes A, B and C and chooses the attribute with the highest information gain value at a root of the tree. The attribute values associated with chosen attribute are then identified as nodes of the tree and are examined. If all of the data records associated with a node are all of the same class, the node is labeled as a leaf or endpoint of the induction tree. Otherwise, the node is labeled as a branching point of the induction tree. The method then chooses a branching point, calculates the information gain value for each of the remaining attributes based on the data from the records associated with chosen branching point, chooses the attribute with the highest information gain value and identifies the attribute values of the chosen attribute as nodes which are examined for leaves and branching points. This process is repeated until only leaves remain within the induction tree or until, at any existing branching point, there are no attributes remaining upon which to branch.
Referring to
FIG. 1
, the attribute A is chosen at the root of the induction tree and the attribute values A_
1
and A_
2
, which are nodes of the induction tree, are then examined. Attribute value A_
1
is a leaf of the induction tree because all of the records associated therewith are associated with the class C
1
. The attribute value A_
2
is a branching point BP
1
and the attribute B b
Chaki Kakali
Marshall O'Toole Gerstein Murray & Borun
R.R. Donnelley & Sons Company
Starks Wilbert
LandOfFree
System and method for partitioning a real-valued attribute... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for partitioning a real-valued attribute..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for partitioning a real-valued attribute... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2820010