A novel member enhancement-based clustering ensemble algorithm

Clustering ensemble is a popular approach for identifying data clusters that combines the clustering results from multiple base clustering algorithms to produce more accurate and robust data clusters. However, the performance of clustering ensemble algorithms is highly dependent on the quality of clustering members. To address this problem, this paper proposes a member enhancement-based clustering ensemble (MECE) algorithm that selects the ensemble members by considering their distribution consistency. MECE has two main components, called heterocluster splitting and homocluster merging. The first component estimates two probability density functions (p.d.f.s) estimated on the sample points of an heterocluster and represents them using a Gaussian distribution and a Gaussian mixture model. If the random numbers generated by these two p.d.f.s have different probability distributions, the heterocluster is then split into smaller clusters. The second component merges the clusters that have high neighborhood densities into a homocluster, where the neighborhood density is measured using a novel evaluation criterion. In addition, a co-association matrix is presented, which serves as a summary for the ensemble of diverse clusters. A series of experiments were conducted to evaluate the feasibility and effectiveness of the proposed ensemble member generation algorithm. Results show that the proposed MECE algorithm can select high quality ensemble members and as a result yield the better clusterings than six state-of-the-art ensemble clustering algorithms, that is, cluster-based similarity partitioning algorithm (CSPA), meta-clustering algorithm (MCLA), hybrid bipartite graph formulation (HBGF), evidence accumulation clustering (EAC), locally weighted evidence accumulation (LWEA), and locally weighted graph partition (LWGP). Specifically, MECE algorithm has the nearly 23% higher average NMI, 27% higher average ARI, 15% higher average FMI, and 10% higher average purity than CSPA, MCLA, HBGF, EAC, LWEA, and LWGA algorithms. The experimental results demonstrate that MECE algorithm is a valid approach to deal with the clustering ensemble problems.     

A scalable framework for cluster ensembles

An ensemble of clustering solutions or partitions may be generated for a number of reasons. If the data set is very large, clustering may be done on tractable size disjoint subsets. The data may be distributed at different sites for which a distributed clustering solution with a final merging of partitions is a natural fit. In this paper, two new approaches to combining partitions, represented by sets of cluster centers, are introduced. The advantage of these approaches is that they provide a final partition of data that is comparable to the best existing approaches, yet scale to extremely large data sets. They can be 100,000 times faster while using much less memory. The new algorithms are compared against the best existing cluster ensemble merging approaches, clustering all the data at once and a clustering algorithm designed for very large data sets. The comparison is done for fuzzy and hard-k-means based clustering algorithms. It is shown that the centroid-based ensemble merging algorithms presented here generate partitions of quality comparable to the best label vector approach or clustering all the data at once, while providing very large speedups.     

Particle Swarm Clustering in clustering ensembles: Exploiting pruning and alignment free consensus

A clustering ensemble combines in a consensus function the partitions generated by a set of independent base clusterers. In this study both the employment of particle swarm clustering (PSC) and ensemble pruning (i.e., selective reduction of base partitions) using evolutionary techniques in the design of the consensus function is investigated. In the proposed ensemble, PSC plays two roles. First, it is used as a base clusterer. Second, it is employed in the consensus function; arguably the most challenging element of the ensemble. The proposed consensus function exploits a representation for the base partitions that makes cluster alignment unnecessary, allows for the combination of partitions with different number of clusters, and supports both disjoint and overlapping (fuzzy, probabilistic, and possibilistic) partitions. Results on both synthetic and real-world data sets show that the proposed ensemble can produce statistically significant better partitions, in terms of the validity indices used, than the best base partition available in the ensemble. In general, a small number of selected base partitions (below 20% of the total) yields the best results. Moreover, results produced by the proposed ensemble compare favorably to those of state-of-the-art clustering algorithms, and specially to swarm based clustering ensemble algorithms.     

Cumulative voting consensus method for partitions with variable number of clusters

Over the past few years, there has been a renewed interest in the consensus clustering problem. Several new methods have been proposed for finding a consensus partition for a set of n data objects that optimally summarizes an ensemble. In this paper, we propose new consensus clustering algorithms with linear computational complexity in n. We consider clusterings generated with random number of clusters, which we describe by categorical random variables. We introduce the idea of cumulative voting as a solution for the problem of cluster label alignment, where, unlike the common one-to-one voting scheme, a probabilistic mapping is computed. We seek a first summary of the ensemble that minimizes the average squared distance between the mapped partitions and the optimal representation of the ensemble, where the selection criterion of the reference clustering is defined based on maximizing the information content as measured by the entropy. We describe cumulative vote weighting schemes and corresponding algorithms to compute an empirical probability distribution summarizing the ensemble. Given the arbitrary number of clusters of the input partitions, we formulate the problem of extracting the optimal consensus as that of finding a compressed summary of the estimated distribution that preserves maximum relevant information. An efficient solution is obtained using an agglomerative algorithm that minimizes the average generalized Jensen-Shannon divergence within the cluster. The empirical study demonstrates significant gains in accuracy and superior performance compared to several recent consensus clustering algorithms.     

Hybrid strategy for selecting compact set of clustering partitions

The selection of the most appropriate clustering algorithm is not a straightforward task, given that there is no clustering algorithm capable of determining the actual groups present in any dataset. A potential solution is to use different clustering algorithms to produce a set of partitions (solutions) and then select the best partition produced according to a specified validation measure; these measures are generally biased toward one or more clustering algorithms. Nevertheless, in several real cases, it is important to have more than one solution as the output. To address these problems, we present a hybrid partition selection algorithm, HSS, which accepts as input a set of base partitions potentially generated from clustering algorithms with different biases and aims, to return a reduced and yet diverse set of partitions (solutions). HSS comprises three steps: (i) the application of a multiobjective algorithm to a set of base partitions to generate a Pareto Front (PF) approximation; (ii) the division of the solutions from the PF approximation into a certain number of regions; and (iii) the selection of a solution per region by applying the Adjusted Rand Index. We compare the results of our algorithm with those of another selection strategy, ASA. Furthermore, we test HSS as a post-processing tool for two clustering algorithms based on multiobjective evolutionary computing: MOCK and MOCLE. The experiments revealed the effectiveness of HSS in selecting a reduced number of partitions while maintaining their quality.     

Weighted association based methods for the combination of heterogeneous partitions

Co-association matrix has been a useful tool in many clustering ensemble techniques as a similarity measure between objects. In this paper, we introduce the weighted-association matrix, which is more expressive than the traditional co-association as a similarity measure, in the sense that it integrates information from the set of partitions in the clustering ensemble as well as from the original data of object representations. The weighted-association matrix is the core of the two main contributions of this paper: a natural extension of the well-known evidence accumulation cluster ensemble method by using the weighted-association matrix and a kernel based clustering ensemble method that uses a new data representation. These methods are compared with simple clustering algorithms as well as with other clustering ensemble algorithms on several datasets. The obtained results ratify the accuracy of the proposed algorithms.     

一种基于自适应最近邻的聚类融合方法

聚类融合通过把具有一定差异性的聚类成员进行组合,能够得到比单一算法更为优越的结果,是近年来聚类算法研究领域的热点问题之一。提出了一种基于自适应最近邻的聚类融合算法ANNCE,能够根据数据分布密度的不同,为每一个数据点自动选择合适的最近邻选取范围。该算法与已有的基于KNN的算法相比,不仅解决了KNN算法中存在的过多参数需要实验确定的问题,还进一步提高了聚类效果。     

云计算下基于改进遗传算法的聚类融合算法

针对无监督聚类缺少数据分类等先验信息、基聚类的准确性受聚类算法影响以及一般聚类融合算法空间复杂度高的问题,提出一种基于改进遗传算法的聚类融合算法（CEIGA）;同时针对传统聚类融合算法已经不能满足大规模数据处理对于时间的要求的问题,提出一种云计算下使用Hadoop平台的基于改进遗传算法的并行聚类融合算法（PCEIGA）。首先,基聚类生成机制产生的基聚类划分在完成簇标签转化后进行基因编码作为遗传算法的初始种群。其次,通过改进遗传算法的选择算子,保证基聚类的多样性;再根据改进的选择算子对染色体进行交叉和变异操作并使用精英策略得到下一代种群,保证基聚类的准确性。如此循环,使聚类融合最终结果达到全局最优,提高算法准确度。通过设计两个MapReduce过程并加入Combine过程减少节点通信,提高算法运行效率。最后,在UCI数据集上比较了CEIGA、PCEIGA和四个先进的聚类融合算法。实验结果表明,与先进的聚类融合算法相比,CEIGA性能最好;而PCEIGA能在不影响聚类结果准确度的前提下明显降低算法运行时间,提高算法效率。     

基于投票机制的融合聚类算法

以一趟聚类算法作为划分数据的基本算法,讨论聚类融合问题.通过重复使用一趟聚类算法划分数据,并随机选择阈值和数据输入顺序,得到不同的聚类结果,将这些聚类结果映射为模式间的关联矩阵,在关联矩阵上使用投票机制获得最终的数据划分.在真实数据集和人造数据集上检验了提出的聚类融合算法,并与相关聚类算法进行了对比,实验结果表明,文中提出的算法是有效可行的.     

Exploring the diversity in cluster ensemble generation: Random sampling and random projection

Cluster ensemble first generates a large library of different clustering solutions and then combines them into a more accurate consensus clustering. It is commonly accepted that for cluster ensemble to work well the member partitions should be different from each other, and meanwhile the quality of each partition should remain at an acceptable level. Many different strategies have been used to generate different base partitions for cluster ensemble. Similar to ensemble classification, many studies have been focusing on generating different partitions of the original dataset, i.e., clustering on different subsets (e.g., obtained using random sampling) or clustering in different feature spaces (e.g., obtained using random projection). However, little attention has been paid to the diversity and quality of the partitions generated using these two approaches. In this paper, we propose a novel cluster generation method based on random sampling, which uses the nearest neighbor method to fill the category information of the missing samples (abbreviated as RS-NN). We evaluate its performance in comparison with k-means ensemble, a typical random projection method (Random Feature Subset, abbreviated as FS), and another random sampling method (Random Sampling based on Nearest Centroid, abbreviated as RS-NC). Experimental results indicate that the FS method always generates more diverse partitions while RS-NC method generates high-quality partitions. Our proposed method, RS-NN, generates base partitions with a good balance between the quality and the diversity and achieves significant improvement over alternative methods. Furthermore, to introduce more diversity, we propose a dual random sampling method which combines RS-NN and FS methods. The proposed method can achieve higher diversity with good quality on most datasets.     

Evolving clusters in gene-expression data

Clustering is a useful exploratory tool for gene-expression data. Although successful applications of clustering techniques have been reported in the literature, there is no method of choice in the gene-expression analysis community. Moreover, there are only a few works that deal with the problem of automatically estimating the number of clusters in bioinformatics datasets. Most clustering methods require the number k of clusters to be either specified in advance or selected a posteriori from a set of clustering solutions over a range of k. In both cases, the user has to select the number of clusters. This paper proposes improvements to a clustering genetic algorithm that is capable of automatically discovering an optimal number of clusters and its corresponding optimal partition based upon numeric criteria. The proposed improvements are mainly designed to enhance the efficiency of the original clustering genetic algorithm, resulting in two new clustering genetic algorithms and an evolutionary algorithm for clustering (EAC). The original clustering genetic algorithm and its modified versions are evaluated in several runs using six gene-expression datasets in which the right clusters are known a priori. The results illustrate that all the proposed algorithms perform well in gene-expression data, although statistical comparisons in terms of the computational efficiency of each algorithm point out that EAC outperforms the others. Statistical evidence also shows that EAC is able to outperform a traditional method based on multiple runs of k-means over a range of k.     

基于划分自适应融合的多视角模糊聚类算法

针对多视角聚类任务如何更好地实现视角间的合作之挑战, 提出一种新的视角融合策略. 该策略首先为每个视角设置一个划分, 然后通过自适应学习获取一个融合权重矩阵对每个视角的划分进行自适应融合, 最终利用视角集成方法得到全局划分结果. 将上述策略应用到经典的FCM(Fuzzy ??-means) 模糊聚类框架, 提出相应的多视角模糊聚类算法. 在模拟数据集和UCI 数据集上的实验结果均显示, 所提出的算法较几种相关聚类算法在应对多视角聚类任务时具有更好的适应性和更好的聚类性能.

     

Weighted partition consensus via kernels

The combination of multiple clustering results (clustering ensemble) has emerged as an important procedure to improve the quality of clustering solutions. In this paper we propose a new cluster ensemble method based on kernel functions, which introduces the Partition Relevance Analysis step. This step has the goal of analyzing the set of partition in the cluster ensemble and extract valuable information that can improve the quality of the combination process. Besides, we propose a new similarity measure between partitions proving that it is a kernel function. A new consensus function is introduced using this similarity measure and based on the idea of finding the median partition. Related to this consensus function, some theoretical results that endorse the suitability of our methods are proven. Finally, we conduct a numerical experimentation to show the behavior of our method on several databases by making a comparison with simple clustering algorithms as well as to other cluster ensemble methods.     

Model-based evaluation of clustering validation measures

A cluster operator takes a set of data points and partitions the points into clusters (subsets). As with any scientific model, the scientific content of a cluster operator lies in its ability to predict results. This ability is measured by its error rate relative to cluster formation. To estimate the error of a cluster operator, a sample of point sets is generated, the algorithm is applied to each point set and the clusters evaluated relative to the known partition according to the distributions, and then the errors are averaged over the point sets composing the sample. Many validity measures have been proposed for evaluating clustering results based on a single realization of the random-point-set process. In this paper we consider a number of proposed validity measures and we examine how well they correlate with error rates across a number of clustering algorithms and random-point-set models. Validity measures fall broadly into three classes: internal validation is based on calculating properties of the resulting clusters; relative validation is based on comparisons of partitions generated by the same algorithm with different parameters or different subsets of the data; and external validation compares the partition generated by the clustering algorithm and a given partition of the data. To quantify the degree of similarity between the validation indices and the clustering errors, we use Kendall's rank correlation between their values. Our results indicate that, overall, the performance of validity indices is highly variable. For complex models or when a clustering algorithm yields complex clusters, both the internal and relative indices fail to predict the error of the algorithm. Some external indices appear to perform well, whereas others do not. We conclude that one should not put much faith in a validity score unless there is evidence, either in terms of sufficient data for model estimation or prior model knowledge, that a validity measure is well-correlated to the error rate of the clustering algorithm.     

一种基于投票策略的聚类融合算法

在分类算法和回归模型中,融合方法正得到越来越广泛的应用,但在非监督机器学习领域,由于缺乏数据集的先验知识,则不能直接用于聚类算法.提出并实现了一种基于投票策略的聚类融合算法,该算法利用k-means算法每次随机选取聚类中心而得到不同样本划分的特性,将多次运行得到的聚类结果通过投票的方式合并,从而得到最终的结果.通过一系列真实数据和合成数据集的实验证明,这种方法比单一的聚类算法能更有效地提高聚类的准确率.在此基础上,为了降低高维数据运算的复杂性,将随机划分属性子空间的方法应用到上述聚类融合算法中,实验证明,该方法同时也能够在一个属性子空间上获得好的聚类结果.     

一种基于聚类融合欠抽样的不平衡数据分类方法

在面对现实中广泛存在的不平衡数据分类问题时,大多数 传统分类算法假定数据集类分布是平衡的,分类结果偏向多数类,效果不理想。为此,提出了一种基于聚类融合欠抽样的改进AdaBoost分类算法。该算法首先进行聚类融合,根据样本权值从每个簇中抽取一定比例的多数类和全部的少数类组成平衡数据集。使用AdaBoost算法框架,对多数类和少数类的错分类给予不同的权重调整,选择性地集成分类效果较好的几个基分类器。实验结果表明,该算法在处理不平衡数据分类上具有一定的优势。     

选择性聚类融合新方法研究

针对传统选择性聚类融合算法不能消除劣质聚类成员的干扰以及聚类准确性不高等问题,提出了一种新的选择性加权聚类融合算法。算法中提出了基于聚类有效性评价方法的参照成员选择方法和联合聚类质量以及差异度的选择策略,然后还提出了基于容错关系信息熵的属性重要性加权方法。新算法有效地克服了传统选择性聚类融合算法的缺点,消除了劣质聚类成员的干扰,提高了聚类的准确性。大量的对比实验结果表明了算法的有效,且性能显著提高。     

Effects of resampling method and adaptation on clustering ensemble efficacy

Clustering ensembles combine multiple partitions of data into a single clustering solution of better quality. Inspired by the success of supervised bagging and boosting algorithms, we propose non-adaptive and adaptive resampling schemes for the integration of multiple independent and dependent clusterings. We investigate the effectiveness of bagging techniques, comparing the efficacy of sampling with and without replacement, in conjunction with several consensus algorithms. In our adaptive approach, individual partitions in the ensemble are sequentially generated by clustering specially selected subsamples of the given dataset. The sampling probability for each data point dynamically depends on the consistency of its previous assignments in the ensemble. New subsamples are then drawn to increasingly focus on the problematic regions of the input feature space. A measure of data point clustering consistency is therefore defined to guide this adaptation. Experimental results show improved stability and accuracy for clustering structures obtained via bootstrapping, subsampling, and adaptive techniques. A meaningful consensus partition for an entire set of data points emerges from multiple clusterings of bootstraps and subsamples. Subsamples of small size can reduce computational cost and measurement complexity for many unsupervised data mining tasks with distributed sources of data. This empirical study also compares the performance of adaptive and non-adaptive clustering ensembles using different consensus functions on a number of datasets. By focusing attention on the data points with the least consistent clustering assignments, whether one can better approximate the inter-cluster boundaries or can at least create diversity in boundaries and this results in improving clustering accuracy and convergence speed as a function of the number of partitions in the ensemble. The comparison of adaptive and non-adaptive approaches is a new avenue for research, and this study helps to pave the way for the useful application of distributed data mining methods.     

Fast Dimension-based Partitioning and Merging clustering algorithm

Clustering multi-dense large scale high dimensional numeric datasets is a challenging task duo to high time complexity of most clustering algorithms. Nowadays, data collection tools produce a large amount of data. So, fast algorithms are vital requirement for clustering such data. In this paper, a fast clustering algorithm, called Dimension-based Partitioning and Merging (DPM), is proposed. In DPM, first, data is partitioned into small dense volumes during the successive processing of dataset dimensions. Then, noise is filtered out using dimensional densities of the generated partitions. Finally, merging process is invoked to construct clusters based on partition boundary data samples. DPM algorithm automatically detects the number of data clusters based on three insensitive tuning parameters which decrease the burden of its usage. Performance evaluation of the proposed algorithm using different datasets shows its fastness and accuracy compared to other clustering competitors.     

Clustering aggregation by probability accumulation

Since a large number of clustering algorithms exist, aggregating different clustered partitions into a single consolidated one to obtain better results has become an important problem. In Fred and Jain's evidence accumulation algorithm, they construct a co-association matrix on original partition labels, and then apply minimum spanning tree to this matrix for the combined clustering. In this paper, we will propose a novel clustering aggregation scheme, probability accumulation. In this algorithm, the construction of correlation matrices takes the cluster sizes of original clusterings into consideration. An alternate improved algorithm with additional pre- and post-processing is also proposed. Experimental results on both synthetic and real data-sets show that the proposed algorithms perform better than evidence accumulation, as well as some other methods.