Search

Unsupervised feature selection (UFS) aims to reduce the time complexity and storage burden, improve the generalization ability of learning machines by removing the redundant, irrelevant and noisy features. Due to the lack of training labels, most existing UFS methods generate the pseudo labels by spectral clustering, matrix factorization or dictionary learning, and convert UFS to a supervised problem. The learned clustering labels reflect the data distribution with respect to classes and therefore are vital to the UFS performance. In this paper, we proposed a novel subspace clustering guided unsupervised feature selection (SCUFS) method. The clustering labels of the training samples are learned by representation based subspace clustering, and features that can well preserve the cluster labels are selected. SCUFS can well learn the data distribution in that it uncovers the underlying multi-subspace structure of the data and iteratively learns the similarity matrix and clustering labels. Experimental results on benchmark datasets for unsupervised feature selection show that SCUFS outperforms the state-of-the-art UFS methods. HighlightsA novel subspace clustering guided unsupervised feature selection (SCUFS) model is proposed.SCUFS learns a similarity graph by self-representation of samples and can uncover the underlying multi-subspace structure of data.The iterative updating of similarity graph and pseudo label matrix can learn a more accurate data distribution.

Clustering learning and classification learning are two major tasks in pattern recognition. The traditional hybrid clustering and classification algorithms handle them in a sequential way rather than a simultaneous way. Fortunately, multiobjective optimization provides a way to solve this problem. In this paper, an algorithm that learns simultaneous clustering and classification adaptively via multiobjective evolutionary algorithm is proposed. The main idea of this paper is to optimize two objective functions which represent fuzzy cluster connectedness and classification error rate to achieve the goal of simultaneous learning. Firstly, we adopt a graph based representation scheme to encode so that it can generate a set of solutions with different number of clusters in a single run. Then the relationship between clustering and classification is built via the Bayesian theory during the optimization process. The quality of clustering and classification is measured by the objective functions and the feedback drawn from both aspects is used to guide the mutation. At last, a set of nondominated solutions are generated, from which the final Pareto optimal solution is selected by using Adjusted Rand Index. The results on synthetic datasets and real-life datasets demonstrate the rationality and effectiveness of the proposed algorithm. Furthermore, we apply the proposed algorithm to image segmentation including texture images and synthetic aperture radar images, the experimental results show the superiority of the proposed algorithm compared with other five algorithms. HighlightsA simultaneous adaptive clustering and classification learning via MOEA is proposed.New clustering objective function is designed, and two objective functions complement with each other.The number of clusters can be determined adaptively during the learning process.The drawback from clustering/classification learning is used to guide the search.We extend it to texture image and SAR image segmentation to show its effectiveness.

In recent years, combining multiple sources or views of datasets for data clustering has been a popular practice for improving clustering accuracy. As different views are different representations of the same set of instances, we can simultaneously use information from multiple views to improve the clustering results generated by the limited information from a single view. Previous studies mainly focus on the relationships between distinct data views, which would get some improvement over the single-view clustering. However, in the case of high-dimensional data, where each view of data is of high dimensionality, feature selection is also a necessity for further improving the clustering results. To overcome this problem, this paper proposes a novel algorithm termed Weighted Multi-view Clustering with Feature Selection (WMCFS) that can simultaneously perform multi-view data clustering and feature selection. Two weighting schemes are designed that respectively weight the views of data points and feature representations in each view, such that the best view and the most representative feature space in each view can be selected for clustering. Experimental results conducted on real-world datasets have validated the effectiveness of the proposed method. HighlightsThis paper proposes a new multi-view data clustering algorithm.The new method considers both view weighting and feature weighting.An EM-like method is designed to get the local optimum solution.Extensive experiments have been conducted to show the effectiveness.

Cluster ensemble approaches make use of a set of clustering solutions which are derived from different data sources to gain a more comprehensive and significant clustering result over conventional single clustering approaches. Unfortunately, not all the clustering solutions in the ensemble contribute to the final result. In this paper, we focus on the clustering solution selection strategy in the cluster ensemble, and propose to view clustering solutions as features such that suitable feature selection techniques can be used to perform clustering solution selection. Furthermore, a hybrid clustering solution selection strategy (HCSS) is designed based on a proposed weighting function, which combines several feature selection techniques for the refinement of clustering solutions in the ensemble. Finally, a new measure is designed to evaluate the effectiveness of clustering solution selection strategies. The experimental results on both UCI machine learning datasets and cancer gene expression profiles demonstrate that HCSS works well on most of the datasets, obtains more desirable final results, and outperforms most of the state-of-the-art clustering solution selection strategies.

Most clustering algorithms organize a collection of objects into a set of disjoint clusters. Although this approach has been successfully applied in unsupervised learning, there are several applications where objects could belong to more than one cluster. Overlapping clustering is an alternative in those contexts like social network analysis, information retrieval and bioinformatics, among other problems where non-disjoint clusters appear. In addition, there are environments where the collection changes frequently and the clustering must be updated; however, most of the existing overlapping clustering algorithms are not able to efficiently update the clustering. In this paper, we introduce a new overlapping clustering algorithm, called DClustR, which is based on the graph theory approach and it introduces a new strategy for building more accurate overlapping clusters than those built by state-of-the-art algorithms. Moreover, our algorithm introduces a new strategy for efficiently updating the clustering when the collection changes. The experimentation conducted over several standard collections shows the good performance of the proposed algorithm, wrt. accuracy and efficiency.

The question of finding generic concepts and properties common to the different clustering approaches is a current problem. This inquire is addressed most thoroughly in Kleinberg's paper on the Impossibility Theorem (see [1]). Kleinberg introduced the notion of clustering function - a function that takes a dissimilarity measure defined on a data set S and returns a partition of S; and a set of simple properties for the study of such functions - Scale Invariance, Richness and Consistency. The main result of [1] is the Impossibility Theorem: there is no clustering method satisfying all these properties. This study has been accepted as a rigorous proof of the difficulty in finding a unified framework for different clustering approaches. Our goal in this paper is to provide primary concepts and results for the formal study of the various clustering approaches. To accomplish this, we discuss and expand on the ideas introduced by Kleinberg. Our guiding philosophy is to incorporate a crucial fact overlooked in the study conducted in [1] - clustering methods not only depend on the dissimilarity measure but also on other parameters such as dissimilarity thresholds, centroids, stop criteria, among others. This paper gives a formal definition of clustering method and reformulates the afore-mentioned properties, even it introduces some new. Contrary to the result obtained in [1], many of the methods discussed here satisfy all of our properties. With all these grounds in hand we glimpse a clue of unification among the different clustering approaches.

Identifying the optimal cluster number and generating reliable clustering results are necessary but challenging tasks in cluster analysis. The effectiveness of clustering analysis relies not only on the assumption of cluster number but also on the clustering algorithm employed. This paper proposes a new clustering analysis method that identifies the desired cluster number and produces, at the same time, reliable clustering solutions. It first obtains many clustering results from a specific algorithm, such as Fuzzy C-Means (FCM), and then integrates these different results as a judgement matrix. An iterative graph-partitioning process is implemented to identify the desired cluster number and the final result. The proposed method is a robust approach as it is demonstrated its effectiveness in clustering 2D data sets and multi-dimensional real-world data sets of different shapes. The method is compared with cluster validity analysis and other methods such as spectral clustering and cluster ensemble methods. The method is also shown efficient in mesh segmentation applications. The proposed method is also adaptive because it not only works with the FCM algorithm but also other clustering methods like the k-means algorithm.

In this article, a proximity fuzzy framework for clustering relational data is presented, where the relationships between the entities of the data are given in terms of proximity values. We offer a comprehensive and in-depth comparison of our clustering framework with proximity relational knowledge to clustering with distance relational knowledge, such as the well known relational Fuzzy C-Means (FCM). We conclude that proximity can provide a richer description of the relationships among the data and this offers a significant advantage when realizing clustering. We further motivate clustering relational proximity data and provide both synthetic and real-world experiments to demonstrate both the usefulness and advantage offered by clustering proximity data. Finally, a case study of relational clustering is introduced where we apply proximity fuzzy clustering to the problem of clustering a set of trees derived from software requirements engineering. The relationships between trees are based on the degree of closeness in both the location of the nodes in the trees and the semantics associated with the type of connections between the nodes.

Two main tasks in pattern recognition area are clustering and classification. Owing to their different goals, traditionally these two tasks are treated separately. However, when label information is available, such separate treatment can not fully explore data information. First, classification is not favored by the data cluster structure. Second, clustering is not guided by valuable label information. Third, the relationship of clusters and classes is not revealed. Contrary to this separate learning treatment, simultaneous learning clustering and classification could benefit each other and overcomes these problems. Recently, a simultaneous learning framework SCC was proposed. Through modeling p(class|cluster) classification and clustering mechanism in SCC depend only on cluster centroids. However, it produces severely nonlinear objective, thus has to use a heuristic searching method, modified Particle Swarm Optimization, to find the optimal solution. But it is very slow. Further, modeling p(class|cluster) makes SCC hard to incorporate semi-supervised settings. In this paper, we propose an alternative framework SC^3SR for simultaneous learning. Besides a classifier derived on the original data, another classifier on the newly-formed cluster structure representation is derived as well. Through this classifier, the clustering learning is guided by the label and classification learning is also favored by cluster structure of data. The final objective is continuously differentiable for which some principled optimization algorithms with convergence guaranteed exist. As a result, our algorithm is much faster than SCC. Further, we generalize this framework to semisupervised situation with the idea of manifold regularization and propose SemiSC^3SR algorithm. Our experiments demonstrate the effectiveness of both SC^3SR and SemiSC^3SR.

Clustering is a fundamental topic in pattern recognition and machine learning research. Traditional clustering methods deal with a single clustering task on a single data set. However, in many real applications, multiple similar clustering tasks are involved simultaneously, e.g., clustering clients of different shopping websites, in which data of different subjects are collected for each task. These tasks are cross-domains but closely related. It is proved that we can improve the individual performance of each clustering task by appropriately utilizing the underling relation. In this paper, we will propose a new approach, which performs multiple related clustering tasks simultaneously through domain adaptation. A shared subspace will be learned through domain adaptation, where the gap of distributions among tasks is reduced, and the shared knowledge will be transferred through all tasks by exploiting the strengthened relation in the learned subspace. Then the object is set as the best clustering in both the original and learned spaces. An alternating optimization method is introduced and its convergence is theoretically guaranteed. Experiments on both synthetic and real data sets demonstrate the effectiveness of the proposed approach.

Traditional pattern recognition generally involves two tasks: unsupervised clustering and supervised classification. When class information is available, fusing the advantages of both clustering learning and classification learning into a single framework is an important problem worthy of study. To date, most algorithms generally treat clustering learning and classification learning in a sequential or two-step manner, i.e., first execute clustering learning to explore structures in data, and then perform classification learning on top of the obtained structural information. However, such sequential algorithms cannot always guarantee the simultaneous optimality for both clustering and classification learning. In fact, the clustering learning in these algorithms just aids the subsequent classification learning and does not benefit from the latter. To overcome this problem, a simultaneous learning framework for clustering and classification (SCC) is presented in this paper. SCC aims to achieve three goals: (1) acquiring the robust classification and clustering simultaneously; (2) designing an effective and transparent classification mechanism; (3) revealing the underlying relationship between clusters and classes. To this end, with the Bayesian theory and the cluster posterior probabilities of classes, we define a single objective function to which the clustering process is directly embedded. By optimizing this objective function, the effective and robust clustering and classification results are achieved simultaneously. Experimental results on both synthetic and real-life datasets show that SCC achieves promising classification and clustering results at one time.

This paper describes a novel feature selection algorithm for unsupervised clustering, that combines the clustering ensembles method and the population based incremental learning algorithm. The main idea of the proposed unsupervised feature selection algorithm is to search for a subset of all features such that the clustering algorithm trained on this feature subset can achieve the most similar clustering solution to the one obtained by an ensemble learning algorithm. In particular, a clustering solution is firstly achieved by a clustering ensembles method, then the population based incremental learning algorithm is adopted to find the feature subset that best fits the obtained clustering solution. One advantage of the proposed unsupervised feature selection algorithm is that it is dimensionality-unbiased. In addition, the proposed unsupervised feature selection algorithm leverages the consensus across multiple clustering solutions. Experimental results on several real data sets demonstrate that the proposed unsupervised feature selection algorithm is often able to obtain a better feature subset when compared with other existing unsupervised feature selection algorithms.

Clustering algorithms are increasingly employed for the categorization of image databases, in order to provide users with database overviews and make their access more effective. By including information provided by the user, the categorization process can produce results that come closer to user's expectations. To make such a semi-supervised categorization approach acceptable for the user, this information must be of a very simple nature and the amount of information the user is required to provide must be minimized. We propose here an effective semi-supervised clustering algorithm, active fuzzy constrained clustering (AFCC), that minimizes a competitive agglomeration cost function with fuzzy terms corresponding to pairwise constraints provided by the user. In order to minimize the amount of constraints required, we define an active mechanism for the selection of candidate constraints. The comparisons performed on a simple benchmark and on a ground truth image database show that with AFCC the results of clustering can be significantly improved with few constraints, making this semi-supervised approach an attractive alternative in the categorization of image databases.

Unsupervised clustering is an important tool to analyze video data. Selection of an appropriate clustering scheme is governed by the suitability of the clusters it produces. It is difficult to formulate cluster suitability criteria for a domain where different feature attributes have different meanings. We propose a novel clustering strategy, tailored towards the specific requirements of clustering in video data. Our clustering methodology decouples clustering along different feature components. Our scheme chooses the clustering model so as to meet the requirements of clustering in video data. The clusters obtained from our scheme reasonably model the homogeneous color regions in a video scene in both space and time. The space-time clusters obtained by our clustering methodology can be subsequently grouped together to compose meaningful objects. Experimental comparison of our results with existing clustering techniques clearly show that our scheme takes care of many of the problems with traditional clustering schemes applied to the heterogeneous feature space of video.

As the sizes of many contemporary databases continue to grow rapidly, incremental clustering has emerged as an essential issue for conducting data analysis on contemporary databases. An incremental clustering algorithm refers to an abstraction of the distribution of the data instances generated by the previous run of the algorithm and therefore is able to cope well with the ever-growing contemporary databases. There are two main challenges in the design of incremental clustering algorithms. The first challenge is how to reduce information loss due to the data abstraction (or summarization) operations. The second challenge is that the clustering result should not be sensitive to the order of input data. This paper presents the GRIN algorithm, an incremental hierarchical clustering algorithm for numerical datasets based on the gravity theory in physics. In the design of GRIN, a statistical test aimed at reducing information loss and distortion is employed to control formation of subclusters as well as to monitor the evolution of the dataset. Due to the statistical test-based summarization approach, GRIN is able to achieve near linear scalability and is not sensitive to input ordering.

Time series clustering has been shown effective in providing useful information in various domains. There seems to be an increased interest in time series clustering as part of the effort in temporal data mining research. To provide an overview, this paper surveys and summarizes previous works that investigated the clustering of time series data in various application domains. The basics of time series clustering are presented, including general-purpose clustering algorithms commonly used in time series clustering studies, the criteria for evaluating the performance of the clustering results, and the measures to determine the similarity/dissimilarity between two time series being compared, either in the forms of raw data, extracted features, or some model parameters. The past researchs are organized into three groups depending upon whether they work directly with the raw data either in the time or frequency domain, indirectly with features extracted from the raw data, or indirectly with models built from the raw data. The uniqueness and limitation of previous research are discussed and several possible topics for future research are identified. Moreover, the areas that time series clustering have been applied to are also summarized, including the sources of data used. It is hoped that this review will serve as the steppingstone for those interested in advancing this area of research.

We formalize clustering as a partitioning problem with a user-defined internal clustering criterion and present SINICC, an unbiased, empirical method for comparing internal clustering criteria. An application to multi-sensor fusion is described, where the data set is composed of inexact sensor “reports” pertaining to “objects” in an environment. Given these reports, the objective is to produce a representation of the environment, where each entity in the representation is the result of “fusing” sensor reports. Before one can perform fusion, however, the reports must be “associated” into homogeneous clusters. Simulated annealing is used to find a near-optimal partitioning with respect to each of several clustering criteria for a variety of simulated data sets. This method can then be used to determine the “best” clustering criterion for the multi-sensor fusion problem with a given fusion operator.

A new dissimilarity measure, based on “position”, “span” and “content” of symbolic objects is proposed for symbolic clustering. The dissimilarity measure is new in the sense that it is not just another aspect of a similarity measure. In the proposed hierarchical agglomerative clustering methodology, composite symbolic objects are formed using a Cartesian join operator whenever a mutual pair of symbolic objects is selected for agglomeration based on minimum dissimilarity. The minimum dissimilarity values of different merging levels are used to compute the cluster indicator values and hence to determine the number of clusters in the data. The results of the application of the algorithm on numeric data of known number of classes are described first so as to show the efficacy of the method. Subsequently, the results of the experiments on two data sets of Assertion type of symbolic objects drawn from the domains of fat-oil and microcomputers are presented.

This paper discusses new approaches to unsupervised fuzzy classification of multidimensional data. In the developed clustering models, patterns are considered to belong to some but not necessarily all clusters. Accordingly, such algorithms are called ‘semi-fuzzy’ or ‘soft’ clustering techniques. Several models to achieve this goal are investigated and corresponding implementation algorithms are developed. Experimental results are reported.

Obvious approaches to reducing the cost (in computer resources) of applying current clustering techniques to the problem of remote sensing are discussed. The use of spatial information in finding fields and in classifying mixture pixels is examined, and the AMOEBA clustering program is described. Internally, a pattern recognition program, from without, AMOEBA appears to be an unsupervised clustering program. It is fast and automatic. No choices (such as arbitrary thresholds to set split/combine sequences) need be made. The problem of finding the number of clusters is solved automatically. At the conclusion of the program, all points in the scene are classified; however, a provision is included for a reject classification of some points which, within the theoretical framework, cannot rationally be assigned to any cluster.

Numerous papers on clustering techniques and their applications in engineering, medical, and biological areas have appeared in pattern recognition literature during the past decade. This paper attempts to set some guidelines for a potential user of a clustering technique. We examine eight clustering programs which are representative of the various available techniques and compare their performances from several points of view. A formal comparative analysis is also performed with a portion of Munson's handprinted character data set. We believe that an understanding of the intrinsic characteristics of a clustering technique is essential to the intelligent application of the technique. Further, the output of a clustering program, along with whatever information a user may have about the data set, should be used together to form hypotheses about the structure of the data set.

In this paper the hierarchical agglomerative clustering procedure with the dissimilarity coefficient D [HACP, D ] and the definite hierarchical clustering procedure [DHACP, D ] including some of the published hierarchical clustering methods are introduced. The formal definitions of both of them are given, by means of which the properties of these procedures can be investigated. An example of applying the procedure concerns the classification in paleobiology.

This paper presents a formalization of the concept of cluster analysis. It begins with an intuitive description of clustering, and discusses the separation of the measurement problem from the clustering problem. It develops the nature of the elements to be clustered, the nature of the possible clusters, and the nature of the clustering results. Particularly significant is the introduction of the attribute of mass of an element. The paper defines a class of functions, called clustering functions, having a certain domain and range and satisfying a certain set of properties, called axioms. It discusses some properties which are inadequate to serve as axioms. Finally, it presents a function which is in the class of clustering functions.