A multicriterion approach for cluster validation

Cluster analysis is about finding groups in data. It has applications in various areas such as biology, medicine, marketing, computer science, psychology, archeology, sociology.

The aim of the proposed project is to address cluster validation, which is a fundamental problem in cluster analysis. Cluster validation refers to both the evaluation of the quality of a clustering and the determination of the number of clusters.

The main idea is to develop a systematic catalogue of cluster validity indexes and to explore their properties, so that a user can match the requirements of a given application of cluster analysis by an appropriate set or aggregation of criteria. This is original, because most existing literature on cluster validation advertises "one criterion fits it all"-approaches ignoring the specific aims of clustering.

Given such a catalogue, a number of clusters in a given application can be determined by specifying a set of minimum requirements or by aggregating criteria with weights depending on the clustering aim. The quality of these approaches will be investigated.

The methods will be generalised to clusterings where some data ("outliers") are not assigned to any cluster.

For benchmarking the quality of cluster analysis methods, the given criteria will be used to explain the performance of different clustering methods on benchmark data sets from the characteristics of the true known clusterings of the data sets.

The developed approaches to determine the number of clusters will be used for deciding about the number of biological species present in data sets with genetic information.

The results of this project are of interest to companies working on customer grouping and market segmentation. Cluster analysis is an important tool in market research, because it enables businesses to identify segments of customers to be addressed by new products and marketing strategies.

Currently there are three industrial collaborators who will use the results of this project, namely ecommera Limited, select Statistical Solutions and adam&eveDDB. These collaborators work for leading UK firms such as John Lewis, Pizza Express (adam&eveDDB), Asda, House of Fraser (ecommera) as well as the UK and local governments (select). The Swiss market research company GfK has recently also expressed interest.

Data sets in the IFCS cluster benchmarking repository, to which the current project contributes, will be openly available for teaching and learning, and for the choice of suitable algorithms in areas in which cluster analysis is needed.

Results regarding species delimitation will be used for advisory on efforts for conservation of biodiversity. Archaeological results will be disseminated in exhibitions. Results on musical styles will be used by the BBC and potentially further organisations.

The project focuses on general results that can be used in a wide variety of applications of cluster analysis, so that there is a scope for long term impact in clustering in medicine (e.g., classification of diseases), genetics (grouping of genes), neuroscience (image analysis), social sciences (social stratification, social network analysis), archaeology (classification of artifacts), biology (species delimitation), ecology (habitat classification), astronomy (object classification), chemistry (multiresolution analysis of spectra), psychology and education science (analysis of test and survey results), machine learning (object recognition), image segmentation, data base organisation and document clustering, and market segmentation.