The ExSTraCS Algorithm

Following along with the figure given above, ExSTraCS begins with a data pre-processing stage (A). The algorithm takes as input, a configuration file and a finite training dataset that includes attributes and a single class endpoint variable. Adaptive data management determines and stores key characteristics of the dataset for later use. Next, expert knowledge (EK) attribute weights may be loaded or generated from the training data using one of the four included attribute weighting algorithms. Weights are utilized by the discovery mechanisms to favor the exploration of rules that specify attributes with higher weights. Attributes with higher weights should be more likely to be useful in discriminating between class/endpoints.

After pre-processing, the core iterative learning cycle (B) repeats through the following 10 steps until a maximum number of learning iterations is reached. (1) A single training instance is taken from the dataset without replacement. (2) The training instance is passed to a population [P] of classifiers that is initially empty. A classifier is a simple IF:THEN rule comprised of a condition (i.e. specified attribute states), and what is traditionally referred to as an action(i.e. the class phenotype). (3) A match set [M] is formed that includes any classifier in [P] that has a condition matching the training instance. (4) [M] is divided into a correct set [C] and an incorrect set [I] based on whether each classifier specified the correct or incorrect class phenotype. (5) If after steps 3 and 4, [C] is empty, covering applies expert knowledge to intelligently generate a matching and 'correct' classifier that is added to [M] and [C]. (6) For every classifier in [P], a number of parameters are maintained and updated throughout the learning process. Classifier parameters (e.g. fitness) are updated for classifiers within [C] and [I]. (7) Subsumption provides a direct generalization pressure that can merge overlapping rules in [C]. A similar subsumption mechanism is also applied to new classifiers generated by the genetic algorithm (GA). (8) Classifiers in [C] are used to update attribute tracking scores for the current training instance. These scores can be fed back into the GA to bias discovery toward useful attribute combinations. (9) The GA uses tournament selection to pick two parent classifiers from [C] based on fitness (i.e. a niche GA) and generates two offspring classifiers which are added to [P]. The GA includes two discovery operators; uniform crossover and mutation. (10) Lastly, whenever the size of [P] is greater than the specified maximum, a deletion mechanism selects a rule and either decrements the numerosity of the rule (if there are multiple copies), or removes it from [P] entirely if it is the only copy.

After all learning iterations have completed, rule compaction is applied as a post-processing step (C) to remove poor and/or redundant rules from [P] to yield a [Pc]. After completion, the ExSTraCS output may be used to make class predictions or evaluated and visulatized to facilitate knowledge discovery.