As more and more applications produce streaming data, clustering data streams has become an important technique for data and knowledge engineering. A typical approach is to summarize the data stream ...in real-time with an online process into a large number of so called micro-clusters. Micro-clusters represent local density estimates by aggregating the information of many data points in a defined area. On demand, a (modified) conventional clustering algorithm is used in a second offline step to recluster the micro-clusters into larger final clusters. For reclustering, the centers of the micro-clusters are used as pseudo points with the density estimates used as their weights. However, information about density in the area between micro-clusters is not preserved in the online process and reclustering is based on possibly inaccurate assumptions about the distribution of data within and between micro-clusters (e.g., uniform or Gaussian). This paper describes DBSTREAM, the first micro-cluster-based online clustering component that explicitly captures the density between micro-clusters via a shared density graph. The density information in this graph is then exploited for reclustering based on actual density between adjacent micro-clusters. We discuss the space and time complexity of maintaining the shared density graph. Experiments on a wide range of synthetic and real data sets highlight that using shared density improves clustering quality over other popular data stream clustering methods which require the creation of a larger number of smaller micro-clusters to achieve comparable results.
Subspace clustering refers to the problem of segmenting data drawn from a union of subspaces. State-of-the-art approaches for solving this problem follow a two-stage approach. In the first step, an ...affinity matrix is learned from the data using sparse or low-rank minimization techniques. In the second step, the segmentation is found by applying spectral clustering to this affinity. While this approach has led to the state-of-the-art results in many applications, it is suboptimal, because it does not exploit the fact that the affinity and the segmentation depend on each other. In this paper, we propose a joint optimization framework - Structured Sparse Subspace Clustering (S 3 C) - for learning both the affinity and the segmentation. The proposed S 3 C framework is based on expressing each data point as a structured sparse linear combination of all other data points, where the structure is induced by a norm that depends on the unknown segmentation. Moreover, we extend the proposed S 3 C framework into Constrained S 3 C (CS 3 C) in which available partial side-information is incorporated into the stage of learning the affinity. We show that both the structured sparse representation and the segmentation can be found via a combination of an alternating direction method of multipliers with spectral clustering. Experiments on a synthetic data set, the Extended Yale B face data set, the Hopkins 155 motion segmentation database, and three cancer data sets demonstrate the effectiveness of our approach.
End-to-end deep clustering method utilizes deep neural networks to jointly learn representation features and clustering assignments. Although many k-means-friendly deep clustering models have been ...explored, the existing division-based methods tend to directly implement clustering with a specific number of clusters, which suffers from poor performance resulted from indistinguishable clusters, and contributes to bad local optimum. At the same time, the representation learning of fuzzy <inline-formula><tex-math notation="LaTeX">c</tex-math></inline-formula>-means clustering in the feature space still needs more research. In this article, a deep fuzzy curriculum clustering method with the learning strategy of clustering from easy to complex automatically is proposed to tackle the above issues. First, considering the soft flexible allocation of fuzzy <inline-formula><tex-math notation="LaTeX">c</tex-math></inline-formula>-means and the preservation of local structure of original data, the fuzzy clustering loss and the autoencoder's reconstruction loss are constructed to learn the embedded features and clustering centers simultaneously. Second, curriculum loss is introduced into the constraint to make clusters successively merge in line with implementing clustering from easy to complex, and realize the bottom-up deep aggregative clustering automatically. In addition, novel curriculum information is proposed as constraint to guide the merging of clusters belonging to the same class. Experimental results on four real-world datasets show the superiority of the proposal.
Deep Self-Evolution Clustering Chang, Jianlong; Meng, Gaofeng; Wang, Lingfeng ...
IEEE transactions on pattern analysis and machine intelligence,
2020-April-1, 2020-Apr, 2020-4-1, 20200401, Volume:
42, Issue:
4
Journal Article
Peer reviewed
Clustering is a crucial but challenging task in pattern analysis and machine learning. Existing methods often ignore the combination between representation learning and clustering. To tackle this ...problem, we reconsider the clustering task from its definition to develop Deep Self-Evolution Clustering (DSEC) to jointly learn representations and cluster data. For this purpose, the clustering task is recast as a binary pairwise-classification problem to estimate whether pairwise patterns are similar. Specifically, similarities between pairwise patterns are defined by the dot product between indicator features which are generated by a deep neural network (DNN). To learn informative representations for clustering, clustering constraints are imposed on the indicator features to represent specific concepts with specific representations. Since the ground-truth similarities are unavailable in clustering, an alternating iterative algorithm called Self-Evolution Clustering Training (SECT) is presented to select similar and dissimilar pairwise patterns and to train the DNN alternately. Consequently, the indicator features tend to be one-hot vectors and the patterns can be clustered by locating the largest response of the learned indicator features. Extensive experiments strongly evidence that DSEC outperforms current models on twelve popular image, text and audio datasets consistently.
A Survey on Multiview Clustering Chao, Guoqing; Sun, Shiliang; Bi, Jinbo
IEEE transactions on artificial intelligence,
2021-April, 2021-4-00, Volume:
2, Issue:
2
Journal Article
Peer reviewed
Open access
Clustering is a machine learning paradigm of dividing sample subjects into a number of groups such that subjects in the same groups are more similar to those in other groups. With advances in ...information acquisition technologies, samples can frequently be viewed from different angles or in different modalities, generating multiview data. Multiview clustering (MVC), that clusters subjects into subgroups using multiview data, has attracted more and more attentions. Although MVC methods have been developed rapidly, there has not been enough survey to summarize and analyze the current progress. Therefore, we propose a novel taxonomy of the MVC approaches. Similar to other machine learning methods, we categorize them into generative and discriminative classes. In the discriminative class, based on the way of view integration, we split it further into five groups-common eigenvector matrix, common coefficient matrix, common indicator matrix, direct combination, and combination after projection. Furthermore, we relate MVC to other topics: multiview representation, ensemble clustering, multitask clustering, multiview supervised, and semisupervised learning. Several representative real-world applications are elaborated for practitioners. Some benchmark multiview datasets are introduced and representative MVC algorithms from each group are empirically evaluated to analyze how they perform on benchmark datasets. To promote future development of MVC approaches, we point out several open problems that may require further investigation and thorough examination.
Impact Statement- Multiview clustering has gained the success in a variety of applications in the past decade. In order to obtain a comprehensive picture of the MVC development, we provide a new categorization of existing MVC methods and introduce the representative algorithms in each category. At last, we point out open problems that are worth investigating to advance the MVC study. More promising MVC methods to solve these open problems may appear following this review paper from which a large number of applications can benefit.
Most existing graph-based clustering methods need a predefined graph and their clustering performance highly depends on the quality of the graph. Aiming to improve the multiview clustering ...performance, a graph learning-based method is proposed to improve the quality of the graph. Initial graphs are learned from data points of different views, and the initial graphs are further optimized with a rank constraint on the Laplacian matrix. Then, these optimized graphs are integrated into a global graph with a well-designed optimization procedure. The global graph is learned by the optimization procedure with the same rank constraint on its Laplacian matrix. Because of the rank constraint, the cluster indicators are obtained directly by the global graph without performing any graph cut technique and the <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-means clustering. Experiments are conducted on several benchmark datasets to verify the effectiveness and superiority of the proposed graph learning-based multiview clustering algorithm comparing to the state-of-the-art methods.
We consider the following problem: given a set of clusterings, find a single clustering that agrees as much as possible with the input clusterings. This problem,
clustering aggregation
, appears ...naturally in various contexts. For example, clustering categorical data is an instance of the clustering aggregation problem; each categorical attribute can be viewed as a clustering of the input rows where rows are grouped together if they take the same value on that attribute. Clustering aggregation can also be used as a metaclustering method to improve the robustness of clustering by combining the output of multiple algorithms. Furthermore, the problem formulation does not require a priori information about the number of clusters; it is naturally determined by the optimization function.
In this article, we give a formal statement of the clustering aggregation problem, and we propose a number of algorithms. Our algorithms make use of the connection between clustering aggregation and the problem of
correlation clustering
. Although the problems we consider are NP-hard, for several of our methods, we provide theoretical guarantees on the quality of the solutions. Our work provides the best deterministic approximation algorithm for the variation of the correlation clustering problem we consider. We also show how sampling can be used to scale the algorithms for large datasets. We give an extensive empirical evaluation demonstrating the usefulness of the problem and of the solutions.
Multi-view subspace clustering has been applied to applications such as image processing and video surveillance, and has attracted increasing attention. Most existing methods learn view-specific ...self-representation matrices, and construct a combined affinity matrix from multiple views. The affinity construction process is time-consuming, and the combined affinity matrix is not guaranteed to reflect the whole true subspace structure. To overcome these issues, the Latent Complete Row Space Recovery (LCRSR) method is proposed. Concretely, LCRSR is based on the assumption that the multi-view observations are generated from an underlying latent representation, which is further assumed to collect the authentic samples drawn exactly from multiple subspaces. LCRSR is able to recover the row space of the latent representation, which not only carries complete information from multiple views but also determines the subspace membership under certain conditions. LCRSR does not involve the graph construction procedure and is solved with an efficient and convergent algorithm, thereby being more scalable to large-scale datasets. The effectiveness and efficiency of LCRSR are validated by clustering various kinds of multi-view data and illustrated in the background subtraction task.
Exploiting consistent structure from multiple graphs is vital for multi-view graph clustering. To achieve this goal, we propose an Efficient Balanced Multi-view Graph Clustering via Good Neighbor ...Fusion (EBMGC-GNF) model which comprehensively extracts credible consistent neighbor information from multiple views by designing a Cross-view Good Neighbors Voting module. Moreover, a novel balanced regularization term based on <inline-formula><tex-math notation="LaTeX">p</tex-math></inline-formula>-power function is introduced to adjust the balance property of clusters, which helps the model adapt to data with different distributions. To solve the optimization problem of EBMGC-GNF, we transform EBMGC-GNF into an efficient form with graph coarsening method and optimize it based on accelareted coordinate descent algorithm. In experiments, extensive results demonstrate that, in the majority of scenarios, our proposals outperform state-of-the-art methods in terms of both effectiveness and efficiency.
Traditional prototype-based clustering methods, such as the well-known fuzzy c-means (FCM) algorithm, usually need sufficient data to find a good clustering partition. If available data are limited ...or scarce, most of them are no longer effective. While the data for the current clustering task may be scarce, there is usually some useful knowledge available in the related scenes/domains. In this study, the concept of transfer learning is applied to prototype-based fuzzy clustering (PFC). Specifically, the idea of leveraging knowledge from the source domain is exploited to develop a set of transfer PFC algorithms. First, two representative PFC algorithms, namely, FCM and fuzzy subspace clustering, have been chosen to incorporate with knowledge leveraging mechanisms to develop the corresponding transfer clustering algorithms based on an assumption that there are the same number of clusters between the target domain (current scene) and the source domain (related scene). Furthermore, two extended versions are also proposed to implement the transfer learning for the situation that there are different numbers of clusters between two domains. The novel objective functions are proposed to integrate the knowledge from the source domain with the data in the target domain for the clustering in the target domain. The proposed algorithms have been validated on different synthetic and real-world datasets. Experimental results demonstrate their effectiveness in comparison with both the original PFC algorithms and the related clustering algorithms like multitask clustering and coclustering.
PDF
