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

• Published in: Journal of computer and system sciences 2019-12, Vol.106, p.94-128
• Main Authors: Koyano, Hitoshi, Hayashida, Morihiro, Akutsu, Tatsuya
• Format: Article
• Language: English
• Subjects: Convergence of a sequence of algorithms; Probability theory; Statistical asymptotics; Topological monoid of strings; Unsupervised string clustering
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2019.07.003

In this study, we address the problem of clustering string data in an unsupervised manner by developing a theory of a mixture model and an EM algorithm for strings based on probability theory on a topological monoid of strings developed in our previous studies. We begin with introducing a parametric probability distribution on a set of strings, which has location and dispersion parameters of a string and positive real number. We develop an iteration algorithm for estimating the parameters of the mixture model of the distributions introduced and demonstrate that our algorithm converges to the EM algorithm, which cannot be explicitly written for this mixture model, with probability one and strongly consistently estimates its parameters as the numbers of observed strings and iterations increase. We finally derive a procedure for unsupervised string clustering that is asymptotically optimal in the sense that the posterior probability of making correct classifications is maximized.