Article and method for finding a compact representation to visualize complex decision trees
First Claim
1. A computer implemented method for transforming a decision tree having a plurality of variables, a root node, intermediate nodes, and leaf nodes into an optimized compact graphical representation for display to a user, comprising:
- inputting the decision tree;
converting the leveled, read-once decision tree into a collection of independent decision chains, each of the independent decision chains having one level for each variable and wherein the variables are arranged in the same order, thereby creating a decision chain set structure;
normalizing the decision chain structure and merging the leaf nodes;
constructing an ordered power set from the plurality of variables to form elements comprising one or more variables;
computing an optimal model graph for each element of the ordered power set having cardinality of one;
computing an optimal model graph for each element of the power set having cardinality greater than one;
selecting an optimal model graph for an element of the power set containing all variables;
transforming the selected optimal model graph to an optimal model graph having a single root node;
selecting a global exception from the optimal model graph having a single root node; and
,creating an exception-based directed acyclic graph from the optimal model having a single root node graph wherein the exception-based directed acyclic graph is comprised of the least number of nodes and the root node is associated with the global exception, thereby creating an optimized and compact representation of the original input decision tree for display to a user;
wherein computing an optimal model graph for all element sets having a cardinality greater than one further comprises;
selecting and removing a variable from each element to form a complimentary corresponding subset comprised of remaining variables of the element;
retrieving a previously computed optimal model graph for the complementary subset from storage and making a copy of the optimal model graph of the complementary subset;
moving all nodes for the selected variable in the copied optimal model graph downward in each decision chain until all nodes corresponding to remaining variables in the complementary subset are below nodes for the selected variable and all nodes for variables not in the element are above nodes for the selected variable;
simplifying a nodal structure of the of the copied optimal model graph by merging redundant nodes of the selected variable to create a merged model;
computing the number of nodes on levels corresponding to variables from the element;
checking storage for an available model for the element;
if an available model does not exist in storage, placing the merged model in memory storage;
if a stored model does exist, determining if the stored model has more nodes than the current model on the levels corresponding to variables from the element;
if the stored model has more nodes, replacing the existing model in storage with the current model.
1 Assignment
0 Petitions
Accused Products
Abstract
The invention comprises an article and method for transforming a complex or large decision tree having multiple variables; multiple values for each variable; and, multiple outcomes for each combination of variables and their associated values, into a compact, efficient graphical representation to provided enhanced ease of use and interaction by a human user. More particularly, the invention comprises a computationally efficient method for transforming an input decision tree into an optimal compact representation by computing a particular ordering of variables in the decision tree that first leads to a Directed Acyclic Graph, or “DAG,” with a minimum number of nodes. The method then converts the DAG into an exception-based DAG, or “EDAG,” with exactly one exception, having an optimal, minimum number of nodes with increased comprehensibility for a user.
97 Citations
15 Claims
-
1. A computer implemented method for transforming a decision tree having a plurality of variables, a root node, intermediate nodes, and leaf nodes into an optimized compact graphical representation for display to a user, comprising:
-
inputting the decision tree; converting the leveled, read-once decision tree into a collection of independent decision chains, each of the independent decision chains having one level for each variable and wherein the variables are arranged in the same order, thereby creating a decision chain set structure; normalizing the decision chain structure and merging the leaf nodes; constructing an ordered power set from the plurality of variables to form elements comprising one or more variables; computing an optimal model graph for each element of the ordered power set having cardinality of one; computing an optimal model graph for each element of the power set having cardinality greater than one; selecting an optimal model graph for an element of the power set containing all variables; transforming the selected optimal model graph to an optimal model graph having a single root node; selecting a global exception from the optimal model graph having a single root node; and
,creating an exception-based directed acyclic graph from the optimal model having a single root node graph wherein the exception-based directed acyclic graph is comprised of the least number of nodes and the root node is associated with the global exception, thereby creating an optimized and compact representation of the original input decision tree for display to a user; wherein computing an optimal model graph for all element sets having a cardinality greater than one further comprises;
selecting and removing a variable from each element to form a complimentary corresponding subset comprised of remaining variables of the element;retrieving a previously computed optimal model graph for the complementary subset from storage and making a copy of the optimal model graph of the complementary subset; moving all nodes for the selected variable in the copied optimal model graph downward in each decision chain until all nodes corresponding to remaining variables in the complementary subset are below nodes for the selected variable and all nodes for variables not in the element are above nodes for the selected variable; simplifying a nodal structure of the of the copied optimal model graph by merging redundant nodes of the selected variable to create a merged model; computing the number of nodes on levels corresponding to variables from the element; checking storage for an available model for the element; if an available model does not exist in storage, placing the merged model in memory storage; if a stored model does exist, determining if the stored model has more nodes than the current model on the levels corresponding to variables from the element; if the stored model has more nodes, replacing the existing model in storage with the current model. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A computer implemented method for transforming a knowledge structure organized as a decision tree having a plurality of variables into a compact exception-based directed acyclic graph for display to a user, comprising:
-
transforming the decision tree into a collection of leveled read-once decision chains; transforming the leveled read-once decision chains into a directed acyclic graph wherein the directed acyclic graph has the least number of nodes; and
,transforming the directed acyclic graph with the least number of nodes into an exception-based directed acyclic graph, providing the simplest graphical representation of the decision logic embodied in the tree for display to a user; wherein transforming the decision tree, transforming the leveled read-once decision chains into a directed acyclic graph and transforming the directed acyclic graph with the last number of nodes into an exception-based directed acyclic graph further comprises; moving each variable of the directed acyclic graph in turn to the bottom of the directed acyclic graph and memorizing the corresponding directed acyclic graph for each variable; for each of the corresponding directed acyclic graphs, moving another variable not at the bottom level to a level immediately above the bottom level; from a set of directed acyclic graphs having a specific subset of variables, selecting and memorizing the directed acyclic graph having the least number of nodes for those variables; repeating the transforming until a directed acyclic graph having the least number of nodes is selected and memorized; converting the directed acyclic graph having the least number of nodes to an exception-based directed acyclic graph; selecting a conclusion of the exception-based directed acyclic graph having a greatest number of incoming edges and removing the conclusion from the exception-based directed acyclic graph; removing all nodes leading exclusively to the removed conclusion; removing all edges leading to the removed conclusion or the removed nodes; and
,establishing the removed conclusion as a global exception of the exception-based directed acyclic graph;
thereby creating a compact graphic representation for presentation to a user.
-
-
8. A computer implemented method for transforming an input decision tree having a plurality of variables, a root node, intermediate nodes, and leaf nodes into an optimal exception-based directed acyclic graph for output and display to a user, comprising:
-
inputting a decision tree; converting the decision tree to a collection of leveled, read-once decision chains, creating a decision chain structure; normalizing the decision chain structure and merging the leaf nodes; creating a power set of the plurality of variables consisting of elements comprised of one or more variables; ordering the elements of the power set according to increasing cardinality of the elements; choosing an element from the ordered power set having a cardinality of 1; choosing a variable from the chosen element; copying the decision chains structure and moving the nodes of the variable selected in step g to the level immediately above the leaf nodes; merging the nodes for a level corresponding to the selected variable and then merging the leaf nodes level to obtain a merged structure having a minimum number of nodes for those two levels; storing the merged structure into memory storage; determining whether all of the elements from the ordered power set having cardinality 1 have been considered; if all elements of the power set having cardinality 1 have not been considered, returning ordering the elements of the power set and choosing a next element in the power set having cardinality 1; if all elements of the power set having cardinality 1 have been considered, determining whether all of the elements from the ordered power set having cardinality greater than 1 have been considered; if all elements of the ordered power set having cardinality greater than 1 have not been considered, choosing a first element of the remaining elements of the power set according to order of cardinality; choosing a first variable from the first element and designating the set of remaining variables as a second element; retrieving from memory storage an optimal directed acyclic graph for the second element and copying the optimal directed acyclic graph to working memory; manipulating the copied optimal directed acyclic graph by moving nodes for the chosen first variable down such that all variables in the second element are below the nodes for the first variable and all of the nodes for those variables not in the first element are above the nodes for the first variable; merging the nodes at the level of the first variable to obtain a minimum number of nodes for the first variable and to create a merged directed acyclic graph; determining if there exists a directed acyclic graph in memory storage for the first element and if not, placing the merged directed acyclic graph into memory storage; determining if there exists a directed acyclic graph in memory storage for the first element, and if so, comparing the merged directed acyclic graph with the stored directed acyclic graph; where the merged directed acyclic graph is comprised of a lesser number of nodes than the stored directed acyclic graph, storing the merged directed acyclic graph in memory storage while erasing the previously stored directed acyclic graph; determining whether all variables in the first element have been considered; if all variables in the first element have not been considered, repeating from the choosing of the first variable for the next variable in the first element; where all variables in the first element have been considered, establishing the last directed acyclic graph stored for the first element as the optimal directed acyclic graph for the first element; determining whether all elements of the optimally ordered power set have been considered;
if all elements of the power set have not been considered, returning to determining whether all of the elements from the ordered power set having cardinality greater than 1 have been considered and choosing a next element in the power set according to order of cardinality;if all elements of the power set have been considered, establishing the directed acyclic graph for the element with all variables as the optimal directed acyclic graph for the input decision tree; converting the optimal directed acyclic graph to a single root graph; designating a conclusion node of the single root graph having the maximum number of parents nodes as a global exception; converting the single root graph with the global exception to create an optimal exception-based directed acyclic graph; and outputting the optimal exception-based directed acyclic graph to a display for presentation to a user.
-
-
9. An article comprising a tangibly embodied machine-readable storage medium operable to cause one or more machines to result in operations comprising:
-
inputting a decision tree having a plurality of variables, a root node, intermediate nodes and leaf nodes wherein each node is associated with at least one or more variables; converting the decision tree into a collection of leveled, read-once independent decision chains having an equal number of levels to create a decision chain set structure; normalizing the decision chain structure and merging the leaf nodes; constructing an ordered power set from the plurality of variables to form elements comprising one or more variables; computing an optimal model graph for each element of the ordered power set having cardinality of one; computing an optimal model graph for each element of the power set having cardinality greater than one; selecting an optimal model graph for an element containing all variables having the least number of nodes; transforming the selected optimal model graph to one with a single root node; selecting a global exception from the optimal model graph having a single root node; and
,creating an exception-based directed acyclic graph from the optimal model single root node graph wherein the exception-based directed acyclic graph is comprised of the least number of nodes and the root node is associated with a global exception, thereby creating an optimized and compact representation of the original input decision tree for display to a user; wherein the operation of computing an optimal model for all element sets having a cardinality greater than one further comprises; selecting and removing a variable from each element to form a complimentary corresponding subset comprised of remaining variables of the element; retrieving a previously computed optimal model graph for the complementary subset from storage and making a copy of the optimal model graph of the complementary subset; moving all nodes for the selected variable in the copied optimal model graph downward in each decision chain until all nodes corresponding to variables in the complementary subset are below nodes for the selected variable and all nodes for variables not in the element are above nodes for the selected variable; simplifying a nodal structure of the of the copied optimal model graph by merging redundant nodes of the selected variable to create a merged model; computing the number of nodes on levels corresponding to variables from the element; checking storage for an available model for the element; if an available model does not exist in storage, placing the merged model in memory storage; if a stored model does exist, determining if the stored model has more nodes than the current model on the levels corresponding to variables from the element; if the stored model has more nodes, replacing the existing model in storage with the current model. - View Dependent Claims (10, 11, 12, 13, 14)
-
-
15. An article comprising a tangibly embodied machine-readable storage medium operable to cause one or more machines to result in operations comprising:
-
inputting a decision tree; converting the decision tree to a collection of leveled, read-once decision chains, creating a decision chains structure; normalizing the decision chain structure and merging the leaf nodes; creating a power set of the plurality of variables consisting of elements comprised of one or more variables; ordering the elements of the power set according to increasing cardinality of the elements; choosing an element from the ordered power set having a cardinality of 1; choosing a variable from the chosen element; copying the decision chains structure computed in step b and moving the nodes of the variable selected in step g to the level immediately above the leaf nodes; merging the nodes for a level corresponding to the chosen variable and then merging the leaf nodes level to obtain a merged structure having a minimum number of nodes for those two levels; storing the merged structure computed in step i into memory storage; determining whether all of the elements from the ordered power set having cardinality 1 have been considered; if all elements of the power set having cardinality 1 have not been considered, returning to choosing an element from the ordered power set having a cardinality of 1 and choosing a next element in the power set having cardinality 1; if all elements of the power set having cardinality 1 have been considered, determining whether all of the elements from the ordered power set having cardinality greater than 1 have been considered; if all elements of the ordered power set having cardinality greater than 1 have not been considered, choosing a first element of the remaining elements of the power set according to order of cardinality; choosing a first variable from the first element and designating the set of remaining variables as a second element; retrieving from memory storage an optimal directed acyclic graph for the second element and copying the optimal directed acyclic graph to working memory; manipulating the copied optimal directed acyclic graph by moving nodes for the chosen first variable down such that all variables in the second element are below the nodes for the first variable and all of the nodes for those variables not in the first element are above the nodes for the first variable; merging the nodes at the level of the first variable to obtain a minimum number of nodes for the first variable and to create a merged directed acyclic graph; determining if there exists a directed acyclic graph in memory storage for the first element and if not, placing the merged directed acyclic graph into memory storage; determining if there exists a directed acyclic graph in memory storage for the first element, and if so, comparing the merged directed acyclic graph with the stored directed acyclic graph; where the merged directed acyclic graph is comprised of a lesser number of nodes than the stored directed acyclic graph, storing the merged directed acyclic graph in memory storage while erasing the previously stored directed acyclic graph; determining whether all variables in the first element have been considered; if all variables in the first element have not been considered, repeating from choosing the first variable from the first element for the next variable in the first element; where all variables in the first element have been considered, establishing the last directed acyclic graph stored for the first element as the optimal directed acyclic graph for the first element; determining whether all elements of the optimally ordered power set have been considered; if all elements of the power set have not been considered, returning to determining whether all of the elements from the ordered power set having cardinality greater than 1 have been considered and choosing a next element in the power set according to order of cardinality; if all elements of the power set have been considered, establishing the directed acyclic graph for the element with all variables as the optimal directed acyclic graph for the input decision tree; converting the optimal directed acyclic graph to a single root graph; designating a conclusion node of the single root graph having the maximum number of parents nodes as a global exception; converting the single root graph with the global exception to create an optimal exception-based directed acyclic graph; and outputting the optimal exception-based directed acyclic graph to a display for presentation to a user.
-
Specification