The emergence of high-dimensional data in various areas has brought new challenges to the ensemble clustering research. To deal with the curse of dimensionality, considerable efforts in ensemble clustering have been made by incorporating various subspace-based techniques. Besides the emphasis on subspaces, rather limited attention has been paid to the potential diversity in similarity dissimilarity metrics. It remains a surprisingly open problem in ensemble clustering how to create and aggregate a large number of diversified metrics, and furthermore, how to jointly exploit the multi-level diversity in the large number of metrics, subspaces, and clusters, in a unified framework. To tackle this problem, this paper proposes a novel multi-diversified ensemble clustering approach. In particular, we create a large number of diversified metrics by randomizing a scaled exponential similarity kernel, which are then coupled with random subspaces to form a large set of metric-subspace pairs. Based on the similarity matrices derived from these metric-subspace pairs, an ensemble of diversified base clusterings can thereby be constructed. Further, an entropy-based criterion is adopted to explore the cluster-wise diversity in ensembles, based on which the consensus function is therefore presented. Experimental results on twenty high-dimensional datasets have confirmed the superiority of our approach over the state-of-the-art.
The median partition based methods @cite_15 @cite_4 @cite_34 typically formulate the ensemble clustering problem into an optimization problem which aims to find the median partition such that the similarity between the base partitions (i.e., base clusterings) and the median partition is maximized. The median partition problem is NP-hard @cite_4 . To find an approximate solution, @cite_4 cast the median partition problem into a maximum likelihood problem and solved it by the EM algorithm. Franek and Jiang @cite_34 reduced the ensemble clustering problem to an Euclidean median problem and solved it by the Weiszfeld algorithm @cite_40 . @cite_15 formulated the ensemble clustering problem into a binary linear programming problem and obtained an approximate solution based on the factor graph model and the max-product belief propagation @cite_0 .
@cite_4 @cite_0 @cite_40 @cite_15 @cite_34
2115346774 2137813581 2161669108 1648123822 2025549250
Ensemble clustering is a recently evolving research direction in cluster analysis and has found several different application domains. In this work the complex ensemble clustering problem is reduced to the well-known Euclidean median problem by clustering embedding in vector spaces. The Euclidean median problem is solved by the Weiszfeld algorithm and an inverse transformation maps the Euclidean median back into the clustering domain. In the experiment study different evaluation strategies are considered. The proposed embedding strategy is compared to several state-of-art ensemble clustering algorithms and demonstrates superior performance. HighlightsThis paper presents a novel approach to solving the ensemble clustering problem.An embedding method successful for strings and graphs is adapted to clusterings.An extensive experiment study is presented.The proposed method is superior to several state-of-the-art related algorithms. We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most well-studied clustering problems, i.e., those problems in which the aim is to partition a given set of points into clusters so that the points within a cluster are relatively close with respect to some measure. For the metric k-median problem, we are given n points in a metric space. We select k of these to be cluster centers and then assign each point to its closest selected center. If point j is assigned to a center i, the cost incurred is proportional to the distance between i and j. The goal is to select the k centers that minimize the sum of the assignment costs. We give a 62 3-approximation algorithm for this problem. This improves upon the best previously known result of O(log k log log k), which was obtained by refining and derandomizing a randomized O(log n log log n)-approximation algorithm of Bartal. Clustering ensembles have emerged as a powerful method for improving both the robustness as well as the stability of unsupervised classification solutions. However, finding a consensus clustering from multiple partitions is a difficult problem that can be approached from graph-based, combinatorial, or statistical perspectives. This study extends previous research on clustering ensembles in several respects. First, we introduce a unified representation for multiple clusterings and formulate the corresponding categorical clustering problem. Second, we propose a probabilistic model of consensus using a finite mixture of multinomial distributions in a space of clusterings. A combined partition is found as a solution to the corresponding maximum-likelihood problem using the EM algorithm. Third, we define a new consensus function that is related to the classical intraclass variance criterion using the generalized mutual information definition. Finally, we demonstrate the efficacy of combining partitions generated by weak clustering algorithms that use data projections and random data splits. A simple explanatory model is offered for the behavior of combinations of such weak clustering components. Combination accuracy is analyzed as a function of several parameters that control the power and resolution of component partitions as well as the number of partitions. We also analyze clustering ensembles with incomplete information and the effect of missing cluster labels on the quality of overall consensus. Experimental results demonstrate the effectiveness of the proposed methods on several real-world data sets. A critical problem in cluster ensemble research is how to combine multiple clusterings to yield a final superior clustering result. Leveraging advanced graph partitioning techniques, we solve this problem by reducing it to a graph partitioning problem. We introduce a new reduction method that constructs a bipartite graph from a given cluster ensemble. The resulting graph models both instances and clusters of the ensemble simultaneously as vertices in the graph. Our approach retains all of the information provided by a given ensemble, allowing the similarity among instances and the similarity among clusters to be considered collectively in forming the final clustering. Further, the resulting graph partitioning problem can be solved efficiently. We empirically evaluate the proposed approach against two commonly used graph formulations and show that it is more robust and achieves comparable or better performance in comparison to its competitors. In this paper, we propose a new ensemble clustering approach termed ensemble clustering using factor graph (ECFG). Compared to the existing approaches, our approach has three main advantages: (1) the cluster number is obtained automatically and need not to be specified in advance; (2) the reliability of each base clustering can be estimated in an unsupervised manner and exploited in the consensus process; (3) our approach is efficient for processing ensembles with large data sizes and large ensemble sizes. In this paper, we introduce the concept of super-object, which serves as a compact and adaptive representation for the ensemble data and significantly facilitates the computation. Through the probabilistic formulation, we cast the ensemble clustering problem into a binary linear programming (BLP) problem. The BLP problem is NP-hard. To solve this optimization problem, we propose an efficient solver based on factor graph. The constrained objective function is represented as a factor graph and the max-product belief propagation is utilized to generate the solution insensitive to initialization and converged to the neighborhood maximum. Extensive experiments are conducted on multiple real-world datasets, which demonstrate the effectiveness and efficiency of our approach against the state-of-the-art approaches. HighlightsIntroduce the super-object representation to facilitate the consensus process.Probabilistically formulate the ensemble clustering problem into a BLP problem.Propose an efficient solver for the BLP problem based on factor graph.The cluster number of the consensus clustering is estimated automatically.Our method achieves the state-of-the-art performance in effectiveness an