Methods and apparatus to improve decision tree execution

Methods, apparatus, systems and articles of manufacture are disclosed to improve decision tree execution. An example method includes retrieving, with a processor, a decision tree logic expression in a sum-of-products (SOP) form, the decision tree logic expression consuming a first duration to evaluate a dataset, eliminating, with the processor, redundant variables of the decision tree logic expression by transforming the decision tree logic expression into a product-of-sums (POS) form, and evaluating, with the processor, the data set with the decision tree logic expression in the POS form, the decision tree logic expression in the POS form consuming a second duration to evaluate the data set that is less than the first duration.

FIELD OF THE DISCLOSURE

This disclosure relates generally to data analysis, and, more particularly, to methods and apparatus to improve decision tree execution.

BACKGROUND

In recent years, social media applications and panelist media consumption behavior applications have grown to produce relatively large quantities of data. Attempts to analyze the data from such applications is aided by decision trees, which include test nodes that analyze a particular variable from the data for a conditional result. For example, if an analyst attempts to obtain a subset of the data related to males less than twenty-five years old, then a first node may analyze the data with a male/female test node to test an inequality expression.

When the male/female test node evaluation results in “TRUE,” then the corresponding data points are associated with male panelists. Additionally, the resulting subset of data associated with the male panelists may further proceed to an age test node that tests data points for an inequality of “Less Than 25.” When the age test node results in a true statement, then that resulting subset of data points is associated with individuals (e.g., panelists) that are both male and less than twenty-five years old.

DETAILED DESCRIPTION

Decision trees may be used with data analysis related to any number and/or type of application, such as set-top-box data analysis, online campaign ratings data analysis and/or social media data analysis. Decision trees include methodologies, techniques and/or algorithms to create nested binary splits on one variable at a time, in which such methodologies repeat for two or more branches until a stopping criterion is met. Decision trees include nodes that, when evaluated with test criteria, result in leaf nodes (sometimes referred to herein as leaves or sub-nodes). Tests at the decision nodes may include a comparison to a threshold value to determine a result of an inequality (e.g., greater than, less than, equal to, etc.). Each sub-node includes results in a tree split after the test, which reflects an associated quantity of data and/or subset of data points. For example, an originating data set having a first (originating) node to test for male or female individuals may split with approximately half of the original data points residing in each of two leaf nodes (e.g., one resulting leaf node for males and one resulting leaf node for females).

The data tested by decision trees may be associated with individuals, such as users of an application, members of a demographically designed panelist group, subscribers to a service, etc. In some examples, an individual user may be associated with any number of variables, such as an age, a gender, a marital status, a number of children, an income value, etc. As such, a decision tree may reference one or more variables when propagating from an originating node through one or more sub-nodes to develop conclusions associated with an originating data set. In some examples, the decision tree includes an objective, such as determining an age or average age of a group of people that have viewed an advertisement. Particular variables associated with each user are evaluated in the decision tree such that a final node reflects the average age of people who have viewed the advertisement. However, in some examples the originating data set includes missing data for one or more variables. In the event a decision tree cannot continue to propagate beyond missing data and/or data that cannot be tested as either greater than, less than or equal to a threshold value, then a regression towards a mean-value may occur, resulting in erroneous conclusions and/or results.

To avoid problems related to tree propagation when missing and/or non-testable variables occur in the originating data set, traditional decision tree techniques provide a surrogate splitting functionality. In circumstances where a splitting variable (e.g., a primary splitting variable) is not provided, not testable, NULL, and/or otherwise unavailable, a surrogate splitting variable is used to mimic a behavior of the primary splitting variable. During tree propagation, the traditional decision tree technique evaluates the surrogate splitting variable to determine a particular surrogate value to be used during propagation, thereby allowing one or more subsequent nodes to be tested during evaluation of an originating data set. The surrogate splitting variable used by the traditional decision tree technique provides an improved propagation robustness, but increases an amount of time required to propagate through the decision tree. In examples where a relatively large number of users is included in the originating data set (e.g., analyzing Facebook® users, analyzing Tencent® instant messaging service users, etc.), delays in tree propagation may become problematic when attempting to produce real-time or near real-time results/conclusions related to the originating data set. In other words, as each surrogate value is encountered by the decision tree, a corresponding processing burden occurs that can, in the aggregate, dramatically increase tree propagation time.

FIG. 1Ais a portion of example decision trees shown as a naïve code block100, sometimes referred to herein as an original code block100. In the illustrated example ofFIG. 1A, the original code block100includes a first decision tree102and a second decision tree104. The example first decision tree102and the example second decision tree104are shown as logical expressions in the illustrated example ofFIG. 1A, but decision trees may be expressed in one or more alternate forms. In some examples, decision trees may be expressed as graphical blocks of decision nodes in a hierarchical arrangement, and in some examples decision trees may be expressed as logical circuits, as described in further detail below in connection withFIGS. 1B and 3B. A decision tree engine creates the original code block100to determine a result using logical tests on originating data, in which each decision tree uses different variables during tree analysis/propagation. In the illustrated example ofFIG. 1A, the first decision tree102includes known variables A1, B1, C1and D1. The known variables are tested by one or more logical statements of the example first decision tree102to determine whether a corresponding branch is to be executed. Example branches may reflect an outcome of a corresponding decision tree, such as an average age or other metric of interest. However, the example decision tree102also includes surrogate variables, which are sometimes referred to herein as not-a-number (“NaN”) variables, and are shown in the illustrated example ofFIG. 1Awith a subscript “n” or “N.” In particular, the example first decision tree102includes NaN variables AN, BN, and CN.

As described above, traditional decision tree analysis/propagation techniques evaluate NaN variables at runtime as they occur in a decision tree sequence. As such, the NaN variable must be evaluated to determine a substitute value suitable to allow tree propagation to continue. However, even after a first NaN variable occurs during tree propagation, that same NaN variable may need to be re-computed in a separate and/or subsequent portion of the same or one or more different trees. To illustrate,FIG. 1Billustrates the example first decision tree102as a logic circuit110. In the illustrated example ofFIG. 1B, NaN variable ANmust be evaluated at three separate instances prior to determining whether branch_1 is true and/or otherwise should be executed. Additionally, the logical expression of the first decision tree102ofFIG. 1Aand the logic circuit110ofFIG. 1Bshow a disjunctive normal form format. In some examples, the disjunctive normal form is referred to herein as a sum-of-products (SOP) form. As such, the example first decision tree102and the example second decision tree104are referred to herein as the first SOP decision tree102and the second SOP decision tree104, respectively.

Examples disclosed herein increase a computation speed of a decision tree by modifying tree logic in a manner that reduces a number of computations while maintaining the truth outcome of the original tree. As described in further detail below, examples disclosed herein (a) simplify decision tree Boolean algebra, (b) precompute NaN variables to reduce in-line processing during tree propagation, (c) rearrange branch execution order, and (d) verify completeness of non-NaN varaibles.

FIG. 2is a schematic illustration of a segmentation optimization system200to facilitate methods and apparatus to improve decision tree execution. In the illustrated example ofFIG. 2, the segmentation optimization system200includes a segmentation optimizer202and a decision tree interface204communicatively connected to a market service220. The example market service220may include a media monitoring entity, a reporting system, and/or an Internet service, such as an e-mail service, social networking service (e.g., Facebook®, Tencent®), etc. The example market service220includes an example first pass tree engine222to generate one or more decision trees, and an example decision tree storage224to store the one or more decision trees and/or data to be evaluated by the decision trees. Decision trees generated by the example first pass tree engine222may include the example original code block100ofFIG. 1A, which includes the example first SOP decision tree102and the example second SOP decision tree104. The example segmentation optimizer202includes an example tree transformation engine206, an example tree factorization engine208, example variable evaluator210, and an example NaN computation engine212. The example segmentation optimizer202also includes an example branch rearrangement engine214, an example branch counter216, an example rank engine218and an example optimizer storage226.

In operation, the example decision tree interface204retrieves, receives and/or otherwise obtains one or more code blocks associated with decision tree logic, such as the example original code block100ofFIG. 1A. As described above, the example market service220may share and/or otherwise provide data having relatively large numbers of participants. For instance, the social media service Tencent® includes over eight hundred million subscribers, and decision trees are used to identify one or more types of information from those subscribers. For instance, in the event an advertisement is observed by a portion of subscribers, those subscribers may have an associated tag or variable to indicate their observation and/or consumption of the advertisement. If the example market service220also wants to know particular demographics associated with the subscribers that observed the advertisement, then a decision tree may be used to divide the subscriber data set into one or more subsets of data that are homogeneous amongst themselves, but heterogeneous with respect to other subsets of data generated at decision tree nodes. Two example subsets of data that are homogeneous amongst themselves and heterogeneous with each other is a first subgroup of subscribers that observed the advertisement, and a second subgroup of subscribers that did not observe the advertisement. Thus, these two example subgroups may represent the results of a first decision node of a decision tree used by the example market service220. In other examples, decision trees help correct for errors that are believed to reside in data sets. In the event a particular user is not truthful about his/her age, or in the event a particular user mistakenly chooses an incorrect age category (e.g., from a dropdown box), then examples disclosed herein may help correct such deficiencies. When an aspect of data is believed to be suspect (e.g., a stated age), decision trees may be used with other known properties of the users to derive a correct value for the suspect data.

Continuing the example above, in the event an analyst associated with the market service also wants to know an average age of only those subscribers that observed the advertisement, then further subsequent branches of decision tree logic may perform inequality tests for each subscriber to determine which resulting node they belong in. For instance, one test node may identify subgroups of subscribers based on a test of the age thirty-four, which splits the group into a subgroup of subscribers younger than thirty-four years of age, and a subgroup of subscribers equal to or older than thirty-four years of age. Additionally, for the subgroup younger than thirty-four years of age, a further subsequent test node may check for those subscribers younger than thirteen years of age, which results in one subgroup of subscribers younger than thirteen and one subgroup of subscribers older than or equal to thirteen (but less than thirty-four years of age because the source data for that respective branch only included subscribers less than thirty-four years of age).

As the example decision tree propagates, such as the trees associated with the example original code block100ofFIG. 1A, resulting nodes identify one or more subsets of subscribers at a relatively greater degree of specificity and/or granularity. However, in the event a variable associated with a subscriber to be tested is missing or cannot be reconciled with a truth test (e.g., the variable is text when the test requires a numeric value), then a corresponding tree node cannot continue to propagate. In some examples, where a surrogate (NaN) variable is not used by the decision tree, then a regression towards a mean value may result. While an occasional NaN variable may not influence a mean result, the aggregate of NaN variables in a context of tens of thousands, millions, etc. subscribers will skew a mean value to an unacceptable degree of accuracy. In some examples, younger subscriber subgroups may be estimated higher than a true value, while older subscriber subgroups may be estimated lower than the true value. Such effects may illustrate an erroneous convergence of the mean value that fails to reflect the truth.

While traditional decision trees and corresponding native code blocks (e.g., the example original code block100ofFIG. 1A) consider surrogate (NaN) variables when an original variable is missing or incapable of truth test(s), such NaN variables introduce substantial delay on the flow of the code block(s). When the example original code block100evaluates a data set, it will consume a corresponding duration of time and/or processor clock cycles. To reduce and/or otherwise minimize execution/propagation time associated with the decision tree code blocks, the example tree transformation engine206transforms the code blocks from a disjunctive normal form (sum of products—“SOP”) to a conjunctive normal form (product of sums—“POS”). For tree logic expressions in the SOP form, all variables within sub-terms must be true (e.g., a logical AND constraint), but any one of the groups of sub-terms could be true (e.g., a logical OR constraint). For instance, in the example original code block100ofFIG. 1A, the expressions (AN&& B1), (AN&& BN&& C1), (AN&& BN&& CN&& D1) must satisfy a logical AND test therein in which evaluation of some terms occur more than one time within each expression. Generally speaking, a disjunctive normal form may be converted and/or otherwise transformed into a conjunctive normal form by way of application of De Morgan's transformation theorems.FIG. 3Ais an example transformed code block300shown in conjunctive normal form, which is based on the original native code block100ofFIG. 1A. In the illustrated example ofFIG. 3A, a first POS decision tree302and a second POS decision tree304have been transformed via Boolean logic to reflect the product of sums. Note that the example first POS decision tree302only needs to evaluate the NaN variable ANonce, as compared to the first SOP decision tree102ofFIG. 1A, in which the NaN variable ANrequired evaluation three separate times. Note that, unlike the SOP form ofFIG. 1A, transformation into the POS form ofFIG. 3Apermits any one of the values within sub-terms to be true, effectively eliminating redundant computation of variables in the SOP expression. Additionally, the transformation yields computational improvements (reduces computation costs) during tree propagation while maintaining an identical truth outcome as compared to the original decision tree(s). When the example transformed code block300evaluates the data set, it will consume a corresponding duration of time and/or processor cycles less than that of the example original code block100.

To illustrate,FIG. 3Billustrates the example first POS decision tree302as a logic circuit310. In the illustrated example ofFIG. 3B, NaN variable ANis evaluated only once at a first logical OR gate312, as compared with the example first SOP decision tree102ofFIG. 1B, in which NaN variable ANis evaluated three separate times. Additionally, the NaN variables BNand CNare evaluated only once each in the example first POS decision tree302at a second logical OR gate314and a third logical OR gate316, respectively.

One benefit of expressing decision trees in the POS form is that terms can be Boolean factorized to yield a single evaluation of any inequality/test for one or more trees. Code blocks transformed into the POS form are retrieved and/or otherwise received by the example tree factorization engine208to identify one or more variables that can be factored out of respective decision trees. The example tree factorization engine208identifies, for example, a variable that is common to two or more sub-expressions of a POS transformed decision tree. Because the POS transformed decision tree includes sub-expressions that are logically ANDed with other sub-expressions, any common variables identified by the example tree factorization engine208may be factored out to simplify the overall decision tree expression. As such, the example tree factorization generates a simplified version of the expression.FIG. 4is an example code block400shown in POS form after factorization of the example code block300ofFIG. 3A. In the illustrated example ofFIG. 4, a first factorized POS decision tree402and a second factorized POS decision tree404have been factorized to simplify the associated expressions, which results in reduced computational resources when propagating/evaluating the respective trees. For instance, the variable A1in the example first factorized POS decision tree402has been factored out to occur once, as compared with the example first POS decision tree302ofFIG. 3A, in which variable A1occurred four times. Similarly, variable B1in the example first factorized POS decision tree402has been factored out to occur once, as compared with the example first POS decision tree202ofFIG. 2A, in which variable B1occurred three times. Similar to the transformations described above, the factorizations of the decision trees improves computational resource efficiency (reduces computation burdens) while maintaining an identical truth outcome as the original decision tree(s).

As described above, evaluation of NaN variables during tree propagation imposes a corresponding computational burden and slows a speed at which the tree can propagate. The example NaN computation engine212evaluates retrieved and/or otherwise received code blocks (e.g., code blocks that have been transformed from SOP to POS format, code blocks that have been factorized, original code blocks) prior to tree propagation to identify surrogate/NaN variables that could cause such computational burdens. If the example NaN computation engine212identifies a NaN variable, that NaN variable is corrected based on the context of the variable type. In some examples, a missing variable value is replaced with a default value, while in other examples a floating point value is rounded up or down when the variable type is integer (e.g., 12.3 is rounded down to 12).

Additionally, the example NaN computation engine212evaluates the context in which the NaN variable is used so that it can be converted into a binary value rather than a value to be used in a relatively more computationally demanding inequality test. For example, if the example NaN variable having a corresponding value of 12 (e.g., after rounding down from 12.3 to 12) is to be used in a decision node that tests for an age greater than twenty-one, the example NaN computation engine212converts the NaN variable to a Boolean FALSE value. As such, during tree propagation a Boolean test may occur, which is computationally faster than an inequality test on the value 12.

The example branch rearrangement engine214evaluates code blocks to identify an optimized order of decision tree propagation. In operation, the example branch rearrangement engine214invokes the example factorization engine208to select a code block of interest, such as a code block that has been transformed and factorized. The example branch counter216determines occurrence rates for each branch within the selected code block, and the example rank engine218ranks the branches (e.g., branch_1, branch_2, etc.) based on a frequency of occurrence. In some examples, decision tree propagation orders are prioritized based on corresponding rank values for branches containing NaN variables first, and then branches containing non-NaN variables (e.g., “regular” variables) thereafter. In other words, because the NaN variables have been converted into Boolean values, branches of decision trees that evaluate the NaN variables may execute relatively faster than regular variables that may require an inequality test. As such, overall code block execution speed may be improved by rearranging the branches associated with NaN variables first.

In some examples, NaN variable prioritization is not invoked and, instead, branches associated with the most frequently occurring variables (either NaN variables or regular variables) are prioritized to be evaluated prior to branches associated with relatively lower frequency of occurrence. For example, assuming that variable A2is identified to occur more frequently than variable A1, then rearranging/swapping decision tree execution to force branches having variable A2to be evaluated before branches having variable A1results in processing clock cycles overall.

While an original code block received and/or otherwise retrieved by the example decision tree interface204includes identified instances of NaN variables, in some examples the first pass tree engine222of the example market service220may not have identified all such instances of NaN variables. To verify variable completeness, the example tree factorization engine208selects a code block of interest, and the example variable evaluator210identifies a regular variable (e.g., not designated as NaN) to determine whether the variable contains a valid value. In some examples, a valid value is determined based on whether the variable value is missing or is NULL. In some examples, a valid value is determined by performing a type check of the variable, such as a variable parameter that identifies a type (e.g., text, integer, float, etc.), and checks the value to verify it is consistent with the variable type. For example if a variable type parameter reflects type INT and the value includes text (e.g., “green”), then the example variable evaluator210reclassifies the regular variable as a NaN. When one or more variables are reclassified as a NaN variable, the example NaN computation engine212applies a correction to the associated value, and redefines the variable as a Boolean type to improve execution speed during tree propagation, as described above.

While an example manner of implementing the segmentation optimizer202ofFIG. 2is illustrated inFIGS. 1A, 1B, 3A, 3B and 4, one or more of the elements, processes and/or devices illustrated inFIG. 2may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example decision tree interface204, the example tree transformation engine206, the example tree factorization engine208, the example variable evaluator210, the example NaN computation engine212, the example branch arrangement engine214, the example branch counter216, the example rank engine218, the example optimizer storage226and/or, more generally, the example segmentation optimizer202ofFIG. 2may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example decision tree interface204, the example tree transformation engine206, the example tree factorization engine208, the example variable evaluator210, the example NaN computation engine212, the example branch arrangement engine214, the example branch counter216, the example rank engine218, the example optimizer storage226and/or, more generally, the example segmentation optimizer202could be implemented by one or more analog or digital circuit(s), logic circuits, programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)). When reading any of the apparatus or system claims of this patent to cover a purely software and/or firmware implementation, at least one of the example decision tree interface204, the example tree transformation engine206, the example tree factorization engine208, the example variable evaluator210, the example NaN computation engine212, the example branch arrangement engine214, the example branch counter216, the example rank engine218, the example optimizer storage226and/or, more generally, the example segmentation optimizer202is/are hereby expressly defined to include a tangible computer readable storage device or storage disk such as a memory, a digital versatile disk (DVD), a compact disk (CD), a Blu-ray disk, etc. storing the software and/or firmware. Further still, the example segmentation optimizer202ofFIG. 2may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG. 2, and/or may include more than one of any or all of the illustrated elements, processes and devices.

Flowcharts representative of example machine readable instructions for implementing the segmentation optimizer202ofFIG. 2are shown inFIGS. 5-8. In these examples, the machine readable instructions comprise a program(s) for execution by a processor such as the processor912shown in the example processor platform900discussed below in connection withFIG. 9. The program may be embodied in software stored on a tangible computer readable storage medium such as a CD-ROM, a floppy disk, a hard drive, a digital versatile disk (DVD), a Blu-ray disk, or a memory associated with the processor912, but the entire program and/or parts thereof could alternatively be executed by a device other than the processor912and/or embodied in firmware or dedicated hardware. Further, although the example program(s) is/are described with reference to the flowcharts illustrated inFIGS. 5-8, many other methods of implementing the example segmentation optimizer202may alternatively be used. For example, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, or combined.

The program500ofFIG. 5begins at block502, where the example decision tree interface204retrieves code blocks associated with decision trees, such as code blocks generated by the example first pass tree engine222of the example market service220. In some examples, the market service220(e.g., a social media service) stores subscriber data in the example decision tree storage224with decision trees to derive information from the subscriber data. As described above, the decision trees from the example market service220are formed as sum of products (SOP) expressions, also referred to herein as disjunctive normal form expressions. The example tree transformation engine206transforms the retrieved code blocks from the SOP expression to a product of sums (POS) expression (block504), also referred to herein as conjunctive normal form expressions. The transformation(s) performed by the example tree transformation engine206simplifies the decision trees of the code blocks to reduce a number of occasions of variable evaluation during tree propagation, as shown by the comparison of the original code block100ofFIG. 1Aand the example transformed code block300ofFIG. 3A.

The example tree factorization engine208factorizes the example transformed code block to factor out duplicative variables that may be present in the decision tree expression (block506). Results of factorization performed by the example tree factorization engine208may be stored for later access in the example optimizer storage226. As described above, factoring out duplicative variables enables a corresponding reduction in computational operations that need to occur during propagation of the factorized expression. The example NaN computation engine212pre-computes NaN variables included in decision trees from the first pass tree engine222to enable further computational benefits and tree propagation speed improvements (block508). Additional tree propagation speed improvements result when the example branch arrangement engine214rearranges an order in which one or more trees is evaluated (block510). While the example first pass tree engine222included NaN variables present in the code blocks, the example variable evaluator210evaluates all remaining original variables to ensure that future tree propagation efforts are not slowed down and/or otherwise halted by an errant variable value (block512). Code blocks that (a) have been transformed, (b) have been factorized, (c) pre-computed the NaN variables, and (d) verified all original variables for completeness, are released back to the example market service220so that analysis of data to be used with the code blocks can be performed.

In some examples, the decision tree interface204transmits and/or otherwise makes available the optimized code blocks to the example decision tree storage224of the example market service220(block514). Because source data from the example market service220may be dynamic and/or otherwise frequently changing, the example segmentation optimizer202determines whether to re-analyze the code blocks and/or receives a request from the market service220to re-analyze the code blocks (block516). Control then returns to block502.

FIG. 6includes additional detail associated with pre-computing NaN variables of block508. In the illustrated example ofFIG. 6, the example decision tree interface204retrieves, extracts and/or otherwise receives a code block of interest from the example decision tree storage224of the example market service220(block602). The example NaN computation engine212evaluates the variables of the obtained code block of interest to identify NaN variables (block604). In some examples, NaN variables are identified by a subscript “n” or “N,” but any other type and manner of NaN variable indicator may be used. In the event the example NaN computation engine212does not identify any NaN variables from the obtained code block of interest (block604), then the example decision tree interface204determines if another code block of interest is to be evaluated (block606). If so, then control returns to block602where the example decision tree interface204retrieves, extracts and/or otherwise receives another code block of interest from the example decision tree storage224of the example market service220.

When the example NaN computation engine212identifies a NaN variable in the obtained code block of interest (block604), the NaN computation engine212evaluates a value associated with the NaN variable to apply a correction value (block608). As described above, the example NaN computation engine212evaluates the context in which the NaN variable is used to apply the correction value, which may include a rounding operation to a floating value when an integer is required. In other examples, a correction value may include a default value, while in still other examples the correction value may include a replacement of text data with an integer, or vice-versa. Additionally, to further increase a speed of decision tree propagation, the corrected NaN value is evaluated in its context of an associated decision tree node to convert the NaN variable value to a Boolean statement (e.g., TRUE or FALSE, 1 or 0). If the context of the associated decision tree node is, for example, to establish whether an age value is above or below a threshold value (e.g., twenty-one years old), then the example NaN computation engine212replaces the integer value of the NaN variable with the Boolean statement based on whether the previous NaN variable value satisfies that threshold (block610). Continuing with the example threshold value of twenty-one years of age, if the original NaN variable value was twelve, then the example NaN computation engine212assigns a Boolean statement of FALSE to the NaN variable. As such, when tree propagation occurs at a later time, fewer computational resources are required to resolve a truth test of that NaN variable because simple binary logic tests of TRUE or FALSE consume fewer computational resources as compared with logical tests of inequalities. In still other examples, in the event a decision tree does not include surrogate variables, optimization analysis can be avoided and the original decision trees may be used.

FIG. 7includes additional detail associated with rearranging branches of block510. In the illustrated example ofFIG. 7, the example factorization engine208selects a factorized code block of interest from the example optimizer storage226(block702). The example branch counter216determines occurrence rates for each branch within the selected factorized code block of interest (block704), and the example rank engine218ranks those branches by their associated occurrence rates (block706). Generally speaking, tree propagation speeds may be improved (e.g., reduced) by prioritizing the evaluation of decision trees (having an associated branch) having a relatively higher occurrence of particular variables prior to other decision trees having variables that do not occur as often within the selected code block. The example branch rearrangement engine214determines whether prioritization of decision trees having NaN variables over regular variables is to occur (block708). If so, then those decision trees having a relatively greater occurrence of NaN variables is arranged by the example branch rearrangement engine214to be evaluated prior to other decision trees that include regular variables (block710). On the other hand, if NaN variable prioritization is not to occur (block708), then the example branch rearrangement engine214arranges branch/decision tree evaluation order based on the raw occurrence values ranked by the example rank engine218(block712). In the event more factorized code blocks of interest are to be analyzed (block714), control returns to block702.

FIG. 8includes additional detail associated with verifying variable completeness of block512. In the illustrated example ofFIG. 8, the example tree factorization engine208selects a factorized code block of interest, such as a code block factorized by the example tree factorization engine208and stored in the example optimization storage226(block802). As described above, while NaN variables were provided in original code blocks from the example decision tree storage224of the example market service220, there is a possibility that the market service220missed one or more regular variables that may contain errant values capable of causing tree propagation to fail. The example variable evaluator210parses and/or otherwise extracts a regular variable (e.g., non-NaN variable) from the selected code block of interest (block804), and evaluates the variable value to determine whether it is valid and/or otherwise capable of logical testing (block806).

For example, if a regular variable includes a NULL value or a missing variable, then any future attempts to evaluate that variable during tree propagation will fail. If the example variable evaluator210identifies a variable value as invalid (block806), then the variable is reclassified as NaN, and control returns to block608ofFIG. 6to apply a correction to the value of the NaN variable. However, if the regular variable is valid (block806, then the example variable evaluator210determines whether the retrieved code block of interest includes an additional regular variable that has not yet been verified (block808). In the event the retrieved code block includes another regular variable to be verified (block808), control returns to block804to select that next variable. Otherwise, when all regular variables have been verified, the example variable evaluator210designates the retrieved code block of interest as validated and ready for tree propagation evaluation (block810). If the example variable evaluator210determines that there are additional code blocks of interest that have not yet been verified (block812), then control returns to block802.

FIG. 9is a block diagram of an example processor platform900capable of executing the instructions ofFIGS. 5-8to implement the segmentation optimization system200ofFIG. 2. The processor platform900can be, for example, a server, a personal computer, an Internet appliance, a set top box, or any other type of computing device.

The processor platform900of the illustrated example includes a processor912. The processor912of the illustrated example is hardware. For example, the processor912can be implemented by one or more integrated circuits, logic circuits, microprocessors or controllers from any desired family or manufacturer.

The processor platform900of the illustrated example also includes an interface circuit920. The interface circuit920may be implemented by any type of interface standard, such as an Ethernet interface, a universal serial bus (USB), and/or a PCI express interface.

In the illustrated example, one or more input devices922are connected to the interface circuit920. The input device(s)922permit(s) a user to enter data and commands into the processor1012. The input device(s) can be implemented by, for example, a keyboard, a button, a mouse, a touchscreen, a track-pad, a trackball, isopoint and/or a voice recognition system.

The processor platform900of the illustrated example also includes one or more mass storage devices928for storing software and/or data. Examples of such mass storage devices928include floppy disk drives, hard drive disks, compact disk drives, Blu-ray disk drives, RAID systems, and digital versatile disk (DVD) drives.

The coded instructions932ofFIGS. 5-8may be stored in the mass storage device928, in the volatile memory914, in the non-volatile memory916, and/or on a removable tangible computer readable storage medium such as a CD or DVD.

From the foregoing, it will be appreciated that the above disclosed methods, apparatus and articles of manufacture reduce computational burdens associated with decision tree evaluation, particularly when relatively large data sets are used with the decision trees. Examples disclosed herein identify decision tree expressions that lack an optimized form and, when identified, convert such expressions into a form that permits reduction of duplicative variable computation. Additionally, examples disclosed herein permit expression factorization to eliminate additional duplicative variables that may occur in a conjunctive normal form. While traditional decision trees may identify surrogate variables when values associated with those variables would, if uncorrected, halt further propagation of decision trees, examples disclosed herein further analyze the surrogate variables to increase tree propagation speed by converting them to binary true/false values. Moreover, examples disclosed herein apply such conversions to the surrogate variables prior to decision tree propagation so that propagation runtime is not halted and/or otherwise slowed down to process computationally intensive inequalities on the fly.