Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings

摘要

In this study, we address the problem of clustering string data in anunsupervised manner by developing a theory of a mixture model and an EMalgorithm for string data based on probability theory on a topological monoidof strings developed in our previous studies. We first construct a parametricdistribution on a set of strings in the motif of the Laplace distribution on aset of real numbers and reveal its basic properties. This Laplace-likedistribution has two parameters: a string that represents the location of thedistribution and a positive real number that represents the dispersion. It isdifficult to explicitly write maximum likelihood estimators of the parametersbecause their log likelihood function is a complex function, the variables ofwhich include a string; however, we construct estimators that almost surelyconverge to the maximum likelihood estimators as the number of observed stringsincreases and demonstrate that the estimators strongly consistently estimatethe parameters. Next, we develop an iteration algorithm for estimating theparameters of the mixture model of the Laplace-like distributions anddemonstrate that the algorithm almost surely converges to the EM algorithm forthe Laplace-like mixture and strongly consistently estimates its parameters asthe numbers of observed strings and iterations increase. Finally, we derive aprocedure for unsupervised string clustering from the Laplace-like mixture thatis asymptotically optimal in the sense that the posterior probability of makingcorrect classifications is maximized.