Quantitative Analysis of Grouping Processes

Abstract

This paper presents a quantitative approach to grouping. A generic grouping method, which may be applied to many domains, is given, and an analysis of its expected grouping quality is done. The grouping method is divided into two parts: Constructing a graph representation of the geometric relations in the data set, and then finding the “best” partition of the graph into groups. Both stages are implemented using known statistical tools such as Wald's SPRT algorithm and the Maximum Likelihood criterion. The accompanying quantitative analysis shows some relations between the data quality, the reliability of the grouping cues and the computational efforts, to the expected grouping quality. To our best knowledge, such an analysis of a grouping process is given here for the first time. The synthesis of specific grouping algorithms is demonstrated for three different grouping tasks and domains. Experimental results show the ability of this generic approach to provide successful algorithm in specific domains.