(A. Danylenko, J. Lundberg, W. Löwe) Decisions: Algebra, Implementation, and First Experiments

Abstract: Classification is a constitutive part in many different fields of Computer Science. There exist several approaches that capture and manipulate classification information in order to construct a specific classification model. These approaches are oftentightly coupled to certain learning strategies, special data structures for capturing the models, and to how common problems, e.g. fragmentation, replication and model over-fitting, are addressed.

In order to unify these different classification approaches, we define a Decision Algebrawhich defines models for classification as higher order decision functions abstracting from their implementations using decision trees (or similar), decision rules, decisiontables, etc. Decision Algebra defines operations for learning, applying, storing, merging, approximating, and manipulating models for classification, along with some generalalgebraic laws regardless of the implementation used.

The Decision Algebra abstraction has several advantages. First, several useful DecisionAlgebra operations (e.g., learning and deciding) can be derived based on the implementation of a few core operations (including merging and approximating). Second,applications using classification can be defined regardless of the different approaches.Third, certain properties of Decision Algebra operations can be proved regardless of the actual implementation. For instance, we show that the merger of a series of probablyaccurate decision functions is even more accurate, which can be exploited for efficientand general online learning.

As a proof of the Decision Algebra concept, we compare decision trees with decisiongraphs, an efficient implementation of the Decision Algebra core operations, which cap-ture classification models in a non-redundant way. Compared to classical decision tree implementations, decision graphs are 20% faster in learning and classification withoutaccuracy loss and reduce memory consumption by 44%. This is the result of experiments on a number of standard benchmark data sets comparing accuracy, access time, and sizeof decision graphs and trees as constructed by the standard C4.5 algorithm.

Finally, in order to test our hypothesis about increased accuracy when merging decisionfunctions, we merged a series of decision graphs constructed over the data sets. The result shows that on each step the accuracy of the merged decision graph increases withthe final accuracy growth of up to 16%.

Keywords: classification, decision algebra, decision function, decision graph, decision tree

Categories: D.3.1, I.2.4, I.2.6, I.2.m