Lattice-based similarity measures between ordered trees

Abstract

A clustering algorithm has recently been developed by Reitman and Rueter to express both the structure of chunking in multi-trial free recall and the order of chunk production. The resulting ordered trees differ from ordinary rooted trees in that the elements of a chunk, at any level, may be restricted to a specific ordering. In order to make comparisons of long-term memory structures between subjects, a measure of the similarity between trees is needed. Previously developed similarity measures are shown to be inadequate for ordered trees. Lattice theory is used to generate new similarity measures suited to these richer structures. First, ordered trees are shown to form a nonmodular, graded lattice. Then, moves through this lattice are defined and used to produce several distance measures. These new measures are compared both to each other, and to existing measures, by examining the properties of each measure, and through application to hypothetical trees. The lattice-based measures prove to be theoretically superior, but lack computational ease. The general problem of describing paths in a nonmodular lattice is discussed.