CODEWITHSUNDEEP
algorithmdecision-tree
Corvinus
Corvinus

Reputation: 169

Decision tree and algorithm choice

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?)

Upvotes: 0

Views: 745

Answers (1)

Ari Hietanen
Ari Hietanen

Reputation: 1769

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.

Upvotes: 2

Related Questions