Prefix trees with frequencies for data analysis and machine learning

Anton Antonov

Accendo Data LLC
antononcube@gmail.com

WTC-2017
October XX, Champaign, IL

Join the Conversation #WolframTechConf

Abstract

In this talk we are going see the applications of a particular data structure -- Prefix trees with frequencies -- in different data analysis and machine learning tasks.

First we give a brief definition and motivation. Then we proceed with examples of basic operations and performance of implementations. The main part of the talk is the applications of Prefix-trees-with-frequencies to data analysis, natural language modeling, classification, and sequences prediction and emulation.

Comparisons with Naive Bayesian Classifiers and Recurrent Neural Networks are made. Several implementations in WL, R, and Java are discussed and compared.

The main goal of this talk is to show Prefix trees with frequencies as a complimentary or alternative method for doing data analysis and Machine learning tasks -- a method that (i) has a great performance, (ii) has great knowledge representation abilities, and (iii) provides results that are easy to interpret and explain.

Talk outline

Definitions

Packages

Basic operations examples

Computational complexity / performance

Data analysis applications

Contingency tables

Mosaic plots

Natural language mining and emulation

Sequence predictions

Route destinations

Patient critical conditions

Time series predictions

Comparison with RNNs

Implementations

Comparison using different languages: WL, R, Java

Summary and conclusions

Prefix trees

See the data structure explanations in Wikipedia’s entry Trie,  [Wk1], and a dedicated discussion in Mathematica StackExchange.

Import["https://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/400px-Trie_example.svg.png"]

A trie for keys “A”,”to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”.

Prefix trees with frequencies packages

Packages

I am going to use two packages in this talk “TriesWithFrequencies.m” and “JavaTriesWithFrequencies.m”. See [AAA1] and [AAA2].

Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/TriesWithFrequencies.m"]
Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/JavaTriesWithFrequencies.m"]

Using JavaTriesWithFrequencies.m requires additional setup of Java code.

Java setup

$JavaTriesWithFrequenciesPath="~/MathematicaForPrediction/Java/TriesWithFrequencies";
FileExistsQ[FileNameJoin[{$JavaTriesWithFrequenciesPath,"TriesWithFrequencies.jar"}]]

dirName="~/MathematicaForPrediction";
FileExistsQ[FileNameJoin[{dirName,"JavaTriesWithFrequencies.m"}]]

AppendTo[$Path,dirName];
Needs["JavaTriesWithFrequencies`"]

JavaTrieInstall[$JavaTriesWithFrequenciesPath]

Prefix trees with frequencies -- basic operations

Here we demonstrate Prefix trees with frequencies.

For a full list of features and explanations see the Markdown document “Tries with frequencies in Java”.

Creation

Consider this list of words:

words={"bar","bars","barks","barkeep","barn","balm","car","cars","care","caress","card","cold","colder"};

We make tries with the lists of their characters. Here is an example:

JavaTrieForm[JavaTrieCreateBySplit[words]](*//Magnify[#,1.2]&*)
AutoCollapse[]

The nodes of the created trie -- a tree structure -- are pairs of keys and values. Given a node, node’s value says how many times node’s key appears after the sequence of keys made from the root to the node.

Let us create a trie with the list:

jTr=JavaTrieCreate[Characters/@words]

If we have a large list of words the function JavaTrieCreate will be slow since that list is converted to even larger list of lists of characters. For better performance it is better to send the list of words to a Java function that then will do the word splitting (on the Java side). This is done with the function JavaTrieCreateBySplit.

jTr1=JavaTrieCreateBySplit[words]

We can convince ourselves that the two Java objects are the same trie:

JavaTrieEqualQ[jTr,jTr1]

The function JavaTrieCreateBySplit takes a second argument for the splitting string. For the list of words:

t=StringRiffle[Characters[#],"~"]&/@words

we can make the following trie with the splitting symbol “~”:

jTr1a=JavaTrieCreateBySplit[t,"~"]

Again we get a trie equivalent to the first one:

JavaTrieEqualQ[jTr,jTr1a]

From frequencies to probabilities

JavaTrieComparisonGrid[{jTr,JavaTrieNodeProbabilities[jTr]},ImageSize->350]

Retrieval

JavaTrieComparisonGrid[{JavaTrieRetrieve[jTr,Characters@"ba"]}]

Shrinking

JavaTrieComparisonGrid[{jTr,JavaTrieShrink[jTr]},ImageSize->350]

Prefix trees with frequencies -- performance

Computational complexity

Here we are going to discuss why prefix trees perform so well.

Prefix trees with frequencies -- implementations

Several different implementations to discuss: WL, R, Java, WL with Java .

Find most common word in-fixes

Consider the problem of finding the most common word in-fixes in a given collection of words. (See this MSE answer/discussion.)

allWords=DictionaryLookup["*"];
allWords//Length

Trie creation and shrinking:

AbsoluteTiming[
jDTrie=JavaTrieCreateBySplit[allWords];
jDShTrie=JavaTrieShrink[jDTrie];
]

JSON form extraction:

AbsoluteTiming[
jsonRes=JavaTrieToJSON[jDShTrie];
]

(The data transfer from Java to Mathematica takes time...)

Here are the node statistics of the original and shrunk tries:

JavaTrieNodeCounts[jDTrie]

JavaTrieNodeCounts[jDShTrie]

Find the infixes that have more than three characters and appear more than 10 times:

Multicolumn[#,4]&@Select[SortBy[Tally[Cases[jsonRes,("key"->v_):>v,Infinity]],-#[[-1]]&],StringLength[#[[1]]]>3&&#[[2]]>10&]

Find most common word prefixes

Consider the problem of finding the most common prefixes in a given text corpus. (See this MSE answer/discussion.)

This gets the words from “Hamlet” and converts to lower case:

tWords=TextWords[ExampleData[{"Text", "Hamlet"}]];
tWords=ToLowerCase[tWords];
Length[tWords]

This creates the trie and converts the frequencies to probabilities:

AbsoluteTiming[
pTr=TrieNodeProbabilities[TrieCreate[tWords]];
]

Trie nodes counts:

TrieNodeCounts[pTr]

The following code prunes the trie in correspondence to a given prefix length and then finds the corresponding probabilities for each prefix. The result is given as an Association.

maxPrefixLength=3;
paths=Rest/@TrieRootToLeafPaths[TriePrune[pTr,maxPrefixLength]];
aPaths=Map[<|"path"->Apply[StringJoin,#[[All,1]]],"probability"->Apply[Times,#[[All,2]]]|>&,paths];

From this Pareto principle adherence plot we can see that 20% of the 3-letter prefixes are correspond to 80% of the words in “Hamlet”:

ParetoLawPlot[Through[aPaths["probability"]]]

This finds quantile values within the 10% of the most popular prefixes:

Quantile[Through[aPaths["probability"]],Range[0.9,1,0.025]]

This selects the most popular prefixes for a given probability:

Select[aPaths,#["probability"]≥%[[-2]]&]

Tally[Flatten@StringCases[tWords,"kin"~~__]]

Contingency tables

Let us demonstrate the making of contingency tables with Tries-with-frequencies.

First we get some data.

ds=ResourceData["Stack Overflow Survey 2016"];
Magnify[ds[1;;6],0.8]

Here is the summary:

Magnify[RecordsSummary[ds[All,Map[If[ListQ[#],ToString[#],#]&,#]&]],0.6]

This is not implemented with Prefix trees but it can be. (Using Tally / SparseArray is fast, and I did not want to introduce a dependency on another package.)

MatrixForm[CrossTabulate[ds[All,{"Gender","DesktopOS"}]]]

MatrixPlot[CrossTabulate[ds[All,{"Gender","DesktopOS"}]]]

Let us make a trie:

tr=TrieCreate[Normal[ds[All,{"Gender","DesktopOS"}][All,Values]]]

And let us do it after deleting the missing values (just to make the visualizations easier):

tr=TrieCreate[Normal[DeleteMissing[ds[All,{"Gender","DesktopOS"}],1,2][All,Values]]]

And visualize it:

TrieForm[tr,AspectRatio->1/4]

Here is the contingency matrix:

Short@TrieRootToLeafPaths[tr]

df=Map[{#[[2,1]],Sequence@@#[[3]]}&,TrieRootToLeafPaths[tr]]

sp=SparseArray[Map[Most[#]->Last[#]&,df]/.Catenate[Map[Thread[Union[#]->Range[Length@Union[#]]]&,Transpose[df][[1;;2]]]]]

MatrixForm[sp,TableHeadings->{Union[df[[All,1]]],Union[df[[All,2]]]}]

Mosaic plots

Mosaic plots are “just” graphical representation of contingency tables if two variables are shown. Otherwise, mosaic plots are graphical representations of tries with frequencies.

MosaicPlot[ds[All,{"Gender","DesktopOS"}],"LabelRotation"->{1,1}]

MosaicPlot[DeleteMissing[ds[All,{"SORegion","DesktopOS"}],1,2],"LabelRotation"->{1,1},ColorRules->{2->ColorData[7,"ColorList"]}]

Sequence ends classification

Let us compare Tries-with-frequencies with Recursive Neural Networks (RNNs).

Route destinations predictions

Tries-with-frequencies can be used to both predict destinations and compress the trip data.

Generation of sequences (words, genes, route segments)

Motivation

Very often in Operations Research (OR) we have to simulate sequences of events or items in order to play out and evaluate different scenarios.

Comparison with Markov chains

Applications

Natural language sentences

Here we are going to discuss the simulation of (learned) sentence generation.

Hospital units sequences

Weather data sequences / time series

Image classification

Let us consider an example of classifying the MNIST digits with Tries-with-frequencies.

The results are not that great -- this example is mostly didactic.

A natural extension is to use this kind of predictions when the paths of writing is known.

Similar extension is for (frequent) routes of drivers. The paths are combined with, say, Decision Trees. 
(Visual aid, Spatial Access Methods WTC-2012.)

Entity name recognition

One way to do Entity Name Recognition (ENR) is with a ensemble of prefix trees with frequencies.

Here we are going to show an algorithm outline and then some examples.

Training data samples

ENR examples

N-gram models

Standard application. Good example for comparing different implementations. (With high dimensional sparse arrays, with association to random choice, with Tries-with-frequencies.)

Not in focus for the talk, but good to have around.

References

General

[Wk1] Wikipedia entry, Trie, URL: https://en.wikipedia.org/wiki/Trie .

GitHub

[AA1] Anton Antonov, Tries with frequencies Mathematica package, (2013), source code at MathematicaForPrediction at GitHub, package TriesWithFrequencies.m .

[AA2] Anton Antonov, Java tries with frequencies Mathematica package, (2017), source code at MathematicaForPrediction at GitHub, package JavaTriesWithFrequencies.m .

[AA3] Anton Antonov, Tries with frequencies in Java, (2017), source code at MathematicaForPrediction at GitHub, project Java/TriesWithFrequencies.

[AA4] Anton Antonov, Java tries with frequencies Mathematica unit tests, (2017), source code at MathematicaForPrediction at GitHub, unit tests file JavaTriesWithFrequencies-Unit-Tests.wlt .

[AA5] Anton Antonov, Mosaic plot for data visualization implementation in Mathematica, (2014), MathematicaForPrediction at GitHub, package MosaicPlot.m.

WordPress

[AA6] Anton Antonov, “Tries with frequencies for data mining”, (2013), MathematicaForPrediction at WordPress blog. URL: https://mathematicaforprediction.wordpress.com/2013/12/06/tries-with-frequencies-for-data-mining/ .

[AA7] Anton Antonov, “Tries with frequencies in Java”, (2017), MathematicaForPrediction at WordPress blog. URL: https://mathematicaforprediction.wordpress.com/2017/01/31/tries-with-frequencies-in-java/ .