Structural Editing by a Point Density Function

A new algorithm is presented for pattern recognition by clustering. The algorithm is called structural editing by a point density function, or STEP. STEP uses a minimum spanning tree to retain the interpoint structure among the elements of an unclassified training set. The tree is pruned or edited to form clusters based on information provided by a point density function (PDF) estimate. STEP has the capability of detecting clusters of arbitrary shape in the presence of intercluster stray points or outliers. A cluster is not required to correspond to a unimodal PDF estimate. Monte Carlo simulations indicate that STEP performs as well as, or better than, a nearest neighbor classifier which requires a classified training set. A new algorithm for recursively constructing the minimum spanning tree is presented which is computationally simpler than conventional algorithms in many practical applications. Results from applying STEP to the mass screening of breast thermograms are discussed.