Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$28,000.00

Theoretical foundations of statistical clustering

EF 2008-09

Résumé
Clustering is one of the most widely used techniques for exploratory data analysis. Across all disciplines, from social sciences to biology to computer science, people try to get a first understanding of their data by identifying meaningful groups among data points. There has been extensive work on algorithms for clustering over the last several decades. However, the vast majority of that work is heuristic in nature. Despite the large number of algorithms and applications, the goal of clustering and its proper interpretation remain fuzzy and vague. While there exists a significant amount of work on the computational complexity of clustering tasks, the theoretical foundations of clustering, especially in statistical settings, seem to be distressingly meager. Common analysis of clustering algorithms does not tackle the problem of clustering in a principled way. While the question 'What clustering is' is difficult to answer in such generality, we believe that there are important sub-questions which are well defined and can and should be investigated in a general statistical framework. The objective of this work is to formulate and analyze general principles, in the form of necessary as well as sufficient conditions, for successful/meaningful clustering. In this project we address clustering in a statistical setting. Namely, a setting in which the input data to a clustering algorithm is a sample from some unknown underlying domain distribution, and the goal of the algorithm is to output meaningful information about that underlying distribution. Apart from the apparent theoretical importance of developing a theory for statistical clustering, our work has the potential of yielding useful model-selection methods for clustering. The principles we propose to develop may provide measures for the fit between different clustering algorithmic approaches and a given clustering task. This will enable the choice of appropriate algorithms and parameters (such as the number of clusters in center-based clustering, or the stopping point for agglomerative algorithms) to be based on soundly defined methodology (as opposed to the currently used ad hoc approaches).
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
312393-2006
Name nom
BenDavid, Shai
Department département
Computer Science, School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2006
Award amount
28000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Partie
3
Nb partie
3
Application title
Theoretical foundations of statistical clustering
Keyword
NA
Application summary
Clustering is one of the most widely used techniques for exploratory data analysis. Across all disciplines, from social sciences to biology to computer science, people try to get a first understanding of their data by identifying meaningful groups among data points. There has been extensive work on algorithms for clustering over the last several decades. However, the vast majority of that work is heuristic in nature. Despite the large number of algorithms and applications, the goal of clustering and its proper interpretation remain fuzzy and vague. While there exists a significant amount of work on the computational complexity of clustering tasks, the theoretical foundations of clustering, especially in statistical settings, seem to be distressingly meager. Common analysis of clustering algorithms does not tackle the problem of clustering in a principled way. While the question 'What clustering is' is difficult to answer in such generality, we believe that there are important sub-questions which are well defined and can and should be investigated in a general statistical framework. The objective of this work is to formulate and analyze general principles, in the form of necessary as well as sufficient conditions, for successful/meaningful clustering. In this project we address clustering in a statistical setting. Namely, a setting in which the input data to a clustering algorithm is a sample from some unknown underlying domain distribution, and the goal of the algorithm is to output meaningful information about that underlying distribution. Apart from the apparent theoretical importance of developing a theory for statistical clustering, our work has the potential of yielding useful model-selection methods for clustering. The principles we propose to develop may provide measures for the fit between different clustering algorithmic approaches and a given clustering task. This will enable the choice of appropriate algorithms and parameters (such as the number of clusters in center-based clustering, or the stopping point for agglomerative algorithms) to be based on soundly defined methodology (as opposed to the currently used ad hoc approaches).