A hybrid EM approach to spatial clustering

Abstract

Spatial clustering requires consideration of spatial information and this makes expectation-maximization (EM) algorithm that maximizes likelihood alone inappropriate. Although neighborhood EM (NEM) algorithm incorporates a spatial penalty term, it needs much more iterations for E-step. To incorporate spatial information while avoiding much additional computation, we propose a hybrid EM (HEM) approach that combines EM and NEM. Early training is performed via a selective hard EM till the penalized likelihood criterion begins to decrease. Then training is turned to NEM, which runs only one iteration of E-step and plays a role of finer tuning. Thus spatial information is incorporated throughout HEM and the computational complexity is also comparable to EM. Empirical results show that a few more passes are needed in HEM to converge after switching to NEM and the final clustering quality is close to or slightly better than standard NEM. © 2005 Elsevier B.V. All rights reserved.