DEV Community

Cover image for Creating a Decision Tree in Prolog
Lucian Green
Lucian Green

Posted on • Edited on

5 1

Creating a Decision Tree in Prolog

What Decision Trees Are

A decision tree is a tree data structure that allows selecting from a list of options and then from more options until reaching a terminal node, preventing the need to painstakingly check each whole set of possibilities.

The following algorithm takes a set of options and converts them into a decision tree.

Some Prolog Code


/*
decision_tree([[a,a],[a,b],[b,b]],A).
A = [[a, 2, [[a, 1, []], [b, 1, []]]], [b, 1, [[b, 1, []]]]].
*/

decision_tree([],[]) :- !.
decision_tree(A,B) :-
    findall(C,(member([C|_D],A)),E),
    frequency_list2(E,L),
    findall([G,K1,P],(member([G,K1],L),
    findall(D,member([G|D],A),D2),
    decision_tree(D2,P)),B).

frequency_list2(E,L) :-
    msort(E, Sorted),
    clumped(Sorted, Freq1),
    findall([B,A],member(B-A,Freq1),L),!.
Enter fullscreen mode Exit fullscreen mode

The following variant is faster:

decision_tree([],[]) :- !.
decision_tree(A,B) :-
    findall(C,(member([C|_D],A)),E),
    frequency_list2(E,L),
    decision_tree1(A,L,[],B).
    decision_tree1(_,[],B,B) :- !.

decision_tree1(A,L,B1,B2) :-
    L=[[G,K1]|Ls],
    decision_tree2(A,G,[],B3),
    decision_tree(B3,P),
    append(B1,[[G,K1,P]],B4),
    decision_tree1(A,Ls,B4,B2),!.

decision_tree2([],_,B,B) :- !.
decision_tree2(A,G,B1,B2) :-
    A=[[G1|D]|As],
    (G1=G->append(B1,[D],B3);
    B1=B3),
    decision_tree2(As,G,B3,B2).

decision_tree2(A,G,B1,B2) :-
    A=[[]|As],
    decision_tree2(As,G,B1,B2).

frequency_list2(E,L) :-
    msort(E, Sorted),
    clumped(Sorted, Freq1),
    findall([B,A],member(B-A,Freq1),L),!.
Enter fullscreen mode Exit fullscreen mode

The decision tree uses the frequency list algorithm, a variant that sorts by frequency in descending order.

/*
frequency_list([a,a,b],A).
A = [[2, a], [1, b]].
*/


frequency_list(A,B) :-

frequency_list1(A,C),sort(C,D),reverse(D,B),!.

frequency_list1(E,L) :-

msort(E, Sorted),
clumped(Sorted, Freq1), findall([A,B],member(B-A,Freq1),L),!.
Enter fullscreen mode Exit fullscreen mode

You can read more about how this algorithm is used on GitHub by my Mind Reader repository, my Essay Helper repository, my Text to Breasonings repository, Strings to Grammar and Spec to Algorithm and my Music Composer repository.

Cover image by Svilen Milev (svilen001-32617, FreeImages).

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay