Creating a Decision Tree in Prolog
Published: 2020-12-04 10:36:16

---
title: Creating a Decision Tree in Prolog
published: true
description: In a->b and a->c choose a then b.
tags: 
cover_image: https://user-images.githubusercontent.com/15845542/101152612-6fd26680-3677-11eb-8d14-a26059d3bb64.jpg
---

#What Decision Trees Are

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

The following algorithm takes a set of options and converts them into a decision tree.  Following the algorithm are some examples.

#Some Prolog Code

make_mind_reading_tree4(Options0,Options3) :-
	sort(Options0,Options1),
	string_to_list1(Options1,1,_,[],Options2),
	maplist(append,[Options2],[Options2a]),
	make_mind_reading_tree4_a(Options2a,Options3).

make_mind_reading_tree4_a(Options2a,Options3) :-
	merge_lists_a([1],Options2a,[],
	Options3a),
	sort(Options3a,Options3),!.
	
string_to_list1([],N,N,Options,Options) :- !.
string_to_list1(Options1,N1,N2,Options2a,Options2b) :-
	Options1=[B|Rest],
	string_to_list2(B,B,N1,N3,Options2a,Options2c),
	[Options2c]=Options2d,
	string_to_list1(Rest,N3,N2,[],Options2e),
	Options2d=[[[_,D1,D2]|D3]],
	Options2f=[[[1,D1,D2]|D3]],
	append(Options2f,Options2e,Options2b).

string_to_list2(B,B1,N1,N2,A1,A2) :- 
	string_concat(D,"",B),
	string_length(D,1),
	append(A1,[[N1,D,[-,B1]]],A2),
	N2 is N1 + 1,!.
string_to_list2(A,B1,N1,N2,B,C) :-
	string_concat(D,E,A),
	string_length(D,1),
	N3 is N1 + 1,
	append(B,[[N1,D,N3]],F),
	string_to_list2(E,B1,N3,N2,F,C).


merge_lists_a([],Options1,Options2,Options3) :- 
	append(Options1,Options2,Options3),!. 
merge_lists_a(N1,Options1,Options2,
Options3) :-
	N1=[M1|Ms],
	% If all As lead to the same letter then merge them
	findall(A,(member([M1,A,_N2],Options1)),A1),
	sort(A1,A11),
	merge_lists_a1(M1,A11,Options1,[],Options31,[],N21),
	append(Options2,Options31,Options32),
	append(Ms,N21,M21),
	sort(M21,M2),
	merge_lists_a(M2,Options32,[],Options3).

merge_lists_a1(_,[],Options1,Options2,Options3,N,N) :- 
	append(Options1,Options2,Options3),!. 
merge_lists_a1(N1,A1,Options1,Options2,Options3,NA61,NA7) :-
	A1=[A2|A3],
	findall([N2,A5,N3],(member([N1,A2,N2],Options1),
	member([N2,A5,N3],Options1)),A4),
	findall([N1,A2,N2],(member([N1,A2,N2],Options1)),A6),
	((merge_lists_a2(A4))->
	(%% merge N1 A2 N..., change N... in other states
	merge_lists_a3(A6,Options1,Options4),
	findall(N2,(member([N1,A2,N2],Options4)),NA6));
	(merge_lists_a3(A6,Options1,Options4),
	findall(N2,(member([N1,A2,N2],Options4)),NA6)
	)),
	append(Options2,Options4,Options5),
	append(NA61,NA6,NA62),
	merge_lists_a1(N1,A3,Options5,[],Options3,NA62,NA7).

merge_lists_a2(A4)	:-
	A4=[[_N1,A,_N2]|A5],
	merge_lists_a22(A,A5).
merge_lists_a22(_A,[]) :- !.
merge_lists_a22(A,A5) :-
	A5=[[_N1,A,_N2]|A6],
	merge_lists_a22(A,A6).

merge_lists_a3(A6,Options1,Options3) :-
	A6=[[N1,A,N2]|A8],
	delete(Options1,[N1,A,_],Options1a),
	(append(Options1a,[[N1,A,N2]],Options1aa)),
	merge_lists_a4(N2,A8,Options1aa,[],Options3).

% delete transition to be merged
merge_lists_a4(_N2,[],Options1,Options2,Options3
) :- 
	append(Options1,Options2,Options3),!.
merge_lists_a4(N2,A8,Options1,Options2,Options3) :-
	A8=[[N1,A,N3]|A9],
	delete(Options1,[N1,A,N3],Options2aa),
	merge_lists_a5(N2,N3,Options2aa,[],Options4,[],Options5),
	findall(N4,(member([N4,_,_],Options4)),N41),
	subtract1(Options5,N41,[],Options45),
	append(Options2,Options45,Options245),
	merge_lists_a4(N2,A9,Options245,[],
	Options31),
	append(Options31,Options4,Options3).

% point second in pair to changed first state
merge_lists_a5(_N2,_N3,[],Options1,Options1,Options2,Options2) :- !.
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
	Options1=[[N3,A,N4]|A9],
	delete(Options2,[N3,A,N4],Options2aa),
	append(Options2aa,[[N2,A,N4]],Options2a),
	merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
	Options1=[[N2,A,N4]|A9],
	delete(Options2,[N3,A,N4],Options2aa),
	append(Options2aa,[[N2,A,N4]],Options2a),
	merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
	Options1=[[N31,A,N4]|A9],
	not(N2=N31),
	append(Options5,[[N31,A,N4]],Options5a),
	merge_lists_a5(N2,N3,A9,Options2,Options4,Options5a,Options6).

subtract1([],_N41,Options45,Options45) :- !.
subtract1(Options5,N41,Options451,Options45) :-
	Options5=[[N42,_,_]|Options51],
	member(N42,N41),
	subtract1(Options51,N41,Options451,Options45).
subtract1(Options5,N41,Options451,Options45) :-
	Options5=[[N42,A,B]|Options51],
	not(member(N42,N41)),
	append(Options451,[[N42,A,B]],Options452),
	subtract1(Options51,N41,Options452,Options45).

#Examples

1. make_mind_reading_tree4(["abc","abd"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[1,"a",5],[5,"b",6],[6,"d",[-,"abd"]]]

DT2=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[3,"d",[-,"abd"]]]

This is self-explanatory.

2. make_mind_reading_tree4(["aaa","aab","acc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"a",3],[3,"a",[-,"aaa"]],[1,"a",5],[5,"a",6],[6,"b",[-,"aab"]],[1,"a",8],[8,"c",9],[9,"c",[-,"acc"]]]

DT2=[[1,"a",2],[2,"a",3],[2,"c",9],[3,"a",[-,"aaa"]],[3,"b",[-,"aab"]],[9,"c",[-,"acc"]]]

3. make_mind_reading_tree4(["cca","ccb"],DT2).

(Intermediate) DT1=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[1,"c",5],[5,"c",6],[6,"b",[-,"ccb"]]]

DT2=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[3,"b",[-,"ccb"]]]

4. make_mind_reading_tree4(["acc","bcc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"c",3],[3,"c",[-,"acc"]],[1,"b",5],[5,"c",6],[6,"c",[-,"bcc"]]]

DT2=[[1,"a",2],[1,"b",5],[2,"c",3],[3,"c",[-,"acc"]],[5,"c",6],[6,"c",[-,"bcc"]]]

The c's stay separate here, although can't be merged because the terminal strings are different.

5. make_mind_reading_tree4(["ac","bc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"c",[-,"ac"]],[1,"b",4],[4,"c",[-,"bc"]]]

DT2=[[1,"a",2],[1,"b",4],[2,"c",[-,"ac"]],[4,"c",[-,"bc"]]]

6. make_mind_reading_tree4(["aqa","awx","awy"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"q",3],[3,"a",[-,"aqa"]],[1,"a",5],[5,"w",6],[6,"x",[-,"awx"]],[1,"a",8],[8,"w",9],[9,"y",[-,"awy"]]]

DT2=[[1,"a",2],[2,"q",3],[2,"w",9],[3,"a",[-,"aqa"]],[9,"x",[-,"awx"]],[9,"y",[-,"awy"]]]

7. make_mind_reading_tree4(["ca","cb"],DT2).

(Intermediate) DT1=[[1,"c",2],[2,"a",[-,"ca"]],[1,"c",4],[4,"b",[-,"cb"]]]

DT2=[[1,"c",2],[2,"a",[-,"ca"]],[2,"b",[-,"cb"]]]

You can read more about how this algorithm is used by my [Mind Reader repository](https://github.com/luciangreen/mindreader) on GitHub in my [Essay Helper repository](https://github.com/luciangreen/Essay-Helper) and my [Music Composer repository](https://github.com/luciangreen/Music-Composer).

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