Decision tree and algorithm choice

0
votes

I am given a homework that asks me to code (using only the functional paradigm) an Akinator-like game in which the computer asks me some questions about a person that I'm thinking of and has to guess who is it. I have a database of about twenty persons and each has about ten questions for which they either have answer "true" or "false".

I am asked to build the smallest (in depth) decision tree defined as :

<Tree> ::= leaf(<List[Atom]>) %list of persons | question(<Atom> true :<Tree> false :<Tree>).

I am proposed to do it with a simple algorithm in which the next node of the tree represents the question for which the number of true and false are the closest. I have to code an algorithm at least as efficient as this one. So I've looked up on the internet to find a better and I discovered a few algorithms like C4.5 and ID3.

My question is what algorithm could I use that is better than the one I'm proposed for my homework? (One that isn't too complicated for what I'm asked for?)

1
algorithmdecision-tree
You already stated a simple solution: Build a tree top-to-bottom while at each node asking question with the most entropy (most disambiguation). So the 1st question is the one that is closest to 50:50 split. Then, for each branch (there are two, true or false, under each question) repeat the process recursively. - Petr Vepřek
Yes sorry I wasn't clear, I'm searching for a better algorithm :) - Corvinus
Have you tried any of the algorithms you found? - m69 ''snarky and unwelcoming''
No, I haven't tried any yet - Corvinus

1 Answers

2
votes

The algorithms C4.5 and ID3 are both greedy algorithms, and for such simple true and false data they would end up constructing the same tree as the simple solution you explained. The greedy algorithms make locally optimal choices, but might not construct globally optimal trees. In general the construction of globally optimal trees is NP-Complete. There are algorithms which try to improve the greedy algorithms, but in general they are quite involved or/and do not work too well. See, e.g, chapter 5.4 of a survey article.