2
$\begingroup$

First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy.

the following is an example of optimization:

|  D1   |   D2   | Outcome |
| true  |  false |   Yes   |
| false |  false |   No    |
| true  |  true  |   Yes   |
| false |  true  |   No    |

when optimized gives: 

|  D1   |   D2   | Outcome |
| true  |   -    |   Yes   |
| false |   -    |   No    |

I need to program this optimization. My decision tree will be different from the one that is shown here. I will have a string outcome, that is in no way a function of the input, and my input will contain 5 different possible inputs. boolean, string, int, double and datetime data types will also be present. Data in the input fields will be expressed using FEEL format.

What I want to know is if there already is a known algorithm for optimizing decision tables like these, or should can I expect to work this out by myself. I don't want to reinvent the wheel here, since this is quite a challenging project. An answer from the stackexchange forum suggested that I post here. He suggested that I start with the Quine–McCluskey algorithm. I looked into this, but it seems like that it's calibrated for boolen based decision tables.

Currently I am considering an approach like the flowing:

  1. If there are no duplicate outcomes, stop process
  2. Select rules with duplicate outcomes
  3. See which decisions are redundant by grouping/merging them
  4. etc

I am to write the code in C#

EDIT: Most inputs will be comparable to a degree. For instance, a string input will be one from a set of strings, and number values will fall in a certain range. But there is no guarantee they always will be.

$\endgroup$
  • $\begingroup$ Welcome to the Computer Science! Are strings comparable in any way? Are ints comparable? The implementation details are out of the scope here (so using C# is not relevant). $\endgroup$ – Evil Jan 11 '17 at 19:58
  • $\begingroup$ Thanks. Yes most input fields will be comparable to a degree. However not always. $\endgroup$ – martijn Jan 11 '17 at 20:19
2
$\begingroup$

The ID3 algorithm is one standard way to construct a decision tree. You can also look at successors like C4.5 and others. These aren't guaranteed to give the smallest possible decision tree (that is known to be NP-hard) but the decision tree it outputs is often fairly reasonable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.