Among ensemble clustering methods, Evidence Accumulation Clustering is one of
the simplest technics. In this approach, a co-association (CA) matrix
representing the co-clustering frequency is built and then clustered to extract
consensus clusters. Compared to other approaches, this one is simple as there
is no need to find matches between clusters obtained from two different
partitionings. Nevertheless, this method suffers from computational issues, as
it requires to compute and store a matrix of size n x n, where n is the number
of items. Due to the quadratic cost, this approach is reserved for small
datasets. This work describes a trick which mimic the behavior of average
linkage clustering. We found a way of computing efficiently the density of a
partitioning, reducing the cost from a quadratic to linear complexity.
Additionally, we proved that the k-means maximizes naturally the density. We
performed experiments on several benchmark datasets where we compared the
k-means and the bisecting version to other state-of-the-art consensus
algorithms. The k-means results are comparable to the best state of the art in
terms of NMI while keeping the computational cost low. Additionally, the
k-means led to the best results in terms of density. These results provide
evidence that consensus clustering can be solved with simple algorithms.

通过实验和比较，本研究证明了集成聚类方法中的证据累积聚类和 k-means 算法在共识聚类中取得了较好的结果和较低的计算成本。

线性时间的 Evidence Accumulation 聚类方法与 KMeans

Linear time Evidence Accumulation Clustering with KMeans

Subspace clustering is the unsupervised grouping of points lying near a union
of low-dimensional linear subspaces. Algorithms based directly on geometric
properties of such data tend to either provide poor empirical performance, lack
theoretical guarantees, or depend heavily on their initialization. We present a
novel geometric approach to the subspace clustering problem that leverages
ensembles of the K-subspaces (KSS) algorithm via the evidence accumulation
clustering framework. Our algorithm, referred to as ensemble K-subspaces
(EKSS), forms a co-association matrix whose (i,j)th entry is the number of
times points i and j are clustered together by several runs of KSS with random
initializations. We prove general recovery guarantees for any algorithm that
forms an affinity matrix with entries close to a monotonic transformation of
pairwise absolute inner products. We then show that a specific instance of EKSS
results in an affinity matrix with entries of this form, and hence our proposed
algorithm can provably recover subspaces under similar conditions to
state-of-the-art algorithms. The finding is, to the best of our knowledge, the
first recovery guarantee for evidence accumulation clustering and for KSS
variants. We show on synthetic data that our method performs well in the
traditionally challenging settings of subspaces with large intersection,
subspaces with small principal angles, and noisy data. Finally, we evaluate our
algorithm on six common benchmark datasets and show that unlike existing
methods, EKSS achieves excellent empirical performance when there are both a
small and large number of points per subspace.

我们提出了一种基于集合 K 子空间 (EKSS) 的几何方法，该算法通过证据积累聚类框架，形成一个共同关联矩阵，该矩阵的 (i，j) th 项是由多次运行具有随机初始化的 KSS 聚类算法将点 i 和 j 配对在一起的次数。我们表明，当一个算法形成的亲和力矩阵的具有和绝对内积的单调变换接近的条目时，该算法可以提供恢复保证。