Error-based Clustering and Its Application to Sales Forecasting in Retail Merchandising

Most traditional clustering methods assume that there is no measurement error, or uncertainty, associated with data. Often, however, real world datasets have such errors. In the presence of measurement errors, well-known clustering methods like k-means and hierarchical clustering may not produce satisfactory results. The fundamental question addressed in this thesis is: "What is an appropriate clustering method in the presence of error associated with data?" In the first part of the thesis, we develop a statistical model and algorithms for clustering data in the presence of errors. We assume that the errors associated with data follow a multivariate Gaussian distribution and are independent between data points. The model uses the maximum likelihood principle and provides us with a new metric for clustering. This metric is used to develop two algorithms for error-based clustering, hError and kError, that are generalizations of Ward's hierarchical and k-means clustering algorithms, respectively. In the second part of the thesis, we characterize sets of clustering problems where error based clustering is likely to be superior to clustering methods that do not consider error information. We present three such problems: (1) clustering of data obtained from statistical models, (2) clustering of aggregated data, and (3) clustering under time and memory constraints. We present theoretical and empirical justifications for the use of error-based clustering on these problems