Over the past few years, there has been a renewed interest in the consensusproblem for ensembles of partitions. Recent work is primarily motivated by thedevelopments in the area of combining multiple supervised learners. Unlike theconsensus of supervised classifications, the consensus of data partitions is achallenging problem due to the lack of globally defined cluster labels and tothe inherent difficulty of data clustering as an unsupervised learning problem.Moreover, the true number of clusters may be unknown.A fundamental goal ofconsensus methods for partitions is to obtain an optimal summary of an ensembleand to discover a cluster structure with accuracy and robustness exceeding thoseof the individual ensemble partitions.The quality of the consensus partitions highly depends on the ensemblegeneration mechanism and on the suitability of the consensus method forcombining the generated ensemble.Typically, consensus methods derive anensemble representation that is used as the basis for extracting the consensuspartition. Most ensemble representations circumvent the labeling problem.Onthe other hand, voting-based methods establish direct parallels with consensusmethods for supervised classifications, by seeking an optimal relabeling of theensemble partitions and deriving an ensemble representation consisting of acentral aggregated partition. An important element of the voting-basedaggregation problem is the pairwise relabeling of an ensemble partition withrespect to a representative partition of the ensemble, which is refered to hereas the voting problem.The voting problem is commonly formulated as a weightedbipartite matching problem.In this dissertation, a general theoretical framework for the voting problem asa multi-response regression problem is proposed. The problem is formulated asseeking to estimate the uncertainties associated with the assignments of theobjects to the representative clusters, given their assignments to the clustersof an ensemble partition. A new voting scheme, referred to as cumulative voting,is derived as a special instance of the proposed regression formulationcorresponding to fitting a linear model by least squares estimation. Theproposed formulation reveals the close relationships between the underlying lossfunctions of the cumulative voting and bipartite matching schemes. A usefulfeature of the proposed framework is that it can be applied to model substantialvariability between partitions, such as a variable number of clusters.A general aggregation algorithm with variants corresponding tocumulative voting and bipartite matching is applied and a simulation-basedanalysis is presented to compare the suitability of each scheme to differentensemble generation mechanisms. The bipartite matching is found to be moresuitable than cumulative voting for a particular generation model, whereby eachensemble partition is generated as a noisy permutation of an underlyinglabeling, according to a probability of error. For ensembles with a variablenumber of clusters, it is proposed that the aggregated partition be viewed as anestimated distributional representation of the ensemble, on the basis of which,a criterion may be defined to seek an optimally compressed consensus partition.The properties and features of the proposed cumulative voting scheme arestudied.In particular, the relationship between cumulative voting and thewell-known co-association matrix is highlighted. Furthermore,an adaptiveaggregation algorithm that is suited for the cumulative voting scheme isproposed. The algorithm aims at selecting the initial reference partition andthe aggregation sequence of the ensemble partitions the loss of mutualinformation associated with the aggregated partition is minimized.In order tosubsequently extract the final consensus partition, an efficient agglomerativealgorithm is developed.The algorithm merges the aggregated clusters such thatthe maximum amount of information is preserved. Furthermore, it allows theoptimal number of consensus clusters to be estimated. An empirical study using several artificial and real-world datasets demonstratesthat the proposed cumulative voting scheme leads to discovering substantiallymore accurate consensus partitions compared to bipartite matching, in the caseof ensembles with a relatively large or a variable number of clusters. Comparedto other recent consensus methods, the proposed method is found to be comparablewith or better than the best performing methods. Moreover, accurate estimates ofthe true number of clusters are often achieved using cumulative voting, whereasconsistently poor estimates are achieved based on bipartite matching. Theempirical evidence demonstrates that the bipartite matching scheme is notsuitable for these types of ensembles.
PDF
download
878987797
028-85220240
