A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> In the application of clustering methods to real world data sets, two problems frequently arise: (a) how can the various contributory variables in a specific battery be weighted so as to enhance some cluster structure that may be present, and (b) how can various alternative batteries be combined to produce a single clustering that "best" incorporates each contributory set. A new method is proposed (SYNCLUS, SYNthesized CLUStering) for dealing with these two problems. <s> BIB001 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> A method is developed which for a given objects by variables data matrix estimates weighted inter-object distances that are optimally suited for either an ultrametric or an additive tree representation. The effectiveness of the method is demonstrated on two synthetic data sets having a known tree structure and on one real data set. In the final section, some possible extensions of the present method are discussed. <s> BIB002 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Data mining applications place special requirements on clustering algorithms including: the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records. We present CLIQUE, a clustering algorithm that satisfies each of these requirements. CLIQUE identifies dense clusters in subspaces of maximum dimensionality. It generates cluster descriptions in the form of DNF expressions that are minimized for ease of comprehension. It produces identical results irrespective of the order in which input records are presented and does not presume any specific mathematical form for data distribution. Through experiments, we show that CLIQUE efficiently finds accurate cluster in large high dimensional datasets. <s> BIB003 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> The clustering problem is well known in the database literature for its numerous applications in problems such as customer segmentation, classification and trend analysis. Unfortunately, all known algorithms tend to break down in high dimensional spaces because of the inherent sparsity of the points. In such high dimensional spaces not all dimensions may be relevant to a given cluster. One way of handling this is to pick the closely correlated dimensions and find clusters in the corresponding subspace. Traditional feature selection algorithms attempt to achieve this. The weakness of this approach is that in typical high dimensional data mining applications different sets of points may cluster better for different subsets of dimensions. The number of dimensions in each such cluster-specific subspace may also vary. Hence, it may be impossible to find a single small subset of dimensions for all the clusters. We therefore discuss a generalization of the clustering problem, referred to as the projected clustering problem , in which the subsets of dimensions selected are specific to the clusters themselves. We develop an algorithmic framework for solving the projected clustering problem, and test its performance on synthetic data. <s> BIB004 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely ta tradeoff with better accuracy. <s> BIB005 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Many emerging application domains require database systems to support efficient access over highly multidimensional datasets. The current state-of-the-art technique to indexing high dimensional data is to first reduce the dimensionality of the data using Principal Component Analysis and then indexing the reduceddimensionality space using a multidimensional index structure. The above technique, referred to as global dimensionality reduction (GDR), works well when the data set is globally correlated, i.e. most of the variation in the data can be captured by a few dimensions. In practice, datasets are often not globally correlated. In such cases, reducing the data dimensionality using GDR causes significant loss of distance information resulting in a large number of false positives and hence a high query cost. Even when a global correlation does not exist, there may exist subsets of data that are locally correlated. In this paper, we propose a technique called Local Dimensionality Reduction (LDR) that tries to find local correlations in the data and performs dimensionality reduction on the locally correlated clusters of data individually. We develop an index structure that exploits the correlated clusters to efficiently support point, range and k-nearest neighbor queries over high dimensional datasets. Our experiments on synthetic as well as real-life datasets show that our technique (1) reduces the dimensionality of the data with significantly lower loss in distance information compared to GDR and (2) significantly outperforms the GDR, original space indexing and linear scan techniques in terms of the query cost for both synthetic and real-life datasets. This work was supported by NSF CAREER award IIS-9734300, and in part by the Army Research Laboratory under Cooperative Agreement No. DAAL01-96-2-0003. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the 26th VLDB Conference, Cairo, Egypt, 2000. <s> BIB006 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> -means partitioning. We also describe some new features and improvements to the algorithm proposed by De Soete. Monte Carlo simulations have been conducted using different error conditions. In all cases (i.e., ultrametric or additive trees, or K-means partitioning), the simulation results indicate that the optimal weighting procedure should be used for analyzing data containing noisy variables that do not contribute relevant information to the classification structure. However, if the data involve error-perturbed variables that are relevant to the classification or outliers, it seems better to cluster or partition the entities by using variables with equal weights. A new computer program, OVW, which is available to researchers as freeware, implements improved algorithms for optimal variable weighting for ultrametric and additive tree clustering, and includes a new algorithm for optimal variable weighting for K-means partitioning. <s> BIB007 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Abstract The aim of this paper is to present a novel subspace clustering method named FINDIT. Clustering is the process of finding interesting patterns residing in the dataset by grouping similar data objects from dissimilar ones based on their dimensional values. Subspace clustering is a new area of clustering which achieves the clustering goal in high dimension by allowing clusters to be formed with their own correlated dimensions. In subspace clustering, selecting correct dimensions is very important because the distance between points is easily changed according to the selected dimensions. However, to select dimensions correctly is difficult, because data grouping and dimension selecting should be performed simultaneously. FINDIT determines the correlated dimensions for each cluster based on two key ideas: dimension-oriented distance measure which fully utilizes dimensional difference information, and dimension voting policy which determines important dimensions in a probabilistic way based on V nearest neighbors' information. Through various experiments on synthetic data, FINDIT is shown to be very successful in the high dimensional clustering problem. FINDIT satisfies most requirements for good clustering methods such as accuracy of results, robustness to the noise and the cluster density, and scalability to the dataset size and the dimensionality. Moreover, it is gracefully scalable to full dimension without any modification to algorithm. <s> BIB008 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> We propose a mathematical formulation for the notion of optimal projective cluster, starting from natural requirements on the density of points in subspaces. This allows us to develop a Monte Carlo algorithm for iteratively computing projective clusters. We prove that the computed clusters are good with high probability. We implemented a modified version of the algorithm, using heuristics to speed up computation. Our extensive experiments show that our method is significantly more accurate than previous approaches. In particular, we use our techniques to build a classifier for detecting rotated human faces in cluttered images. <s> BIB009 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Subspace clustering is an extension of traditional clustering that seeks to find clusters in different subspaces within a dataset. Often in high dimensional data, many dimensions are irrelevant and can mask existing clusters in noisy data. Feature selection removes irrelevant and redundant dimensions by analyzing the entire dataset. Subspace clustering algorithms localize the search for relevant dimensions allowing them to find clusters that exist in multiple, possibly overlapping subspaces. There are two major branches of subspace clustering based on their search strategy. Top-down algorithms find an initial clustering in the full set of dimensions and evaluate the subspaces of each cluster, iteratively improving the results. Bottom-up approaches find dense regions in low dimensional spaces and combine them to form clusters. This paper presents a survey of the various subspace clustering algorithms along with a hierarchy organizing the algorithms by their defining characteristics. We then compare the two main approaches to subspace clustering using empirical scalability and accuracy tests and discuss some potential applications where subspace clustering could be particularly useful. <s> BIB010 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> In high-dimensional data, clusters can exist in subspaces that hide themselves from traditional clustering methods. A number of algorithms have been proposed to identify such projected clusters, but most of them rely on some user parameters to guide the clustering process. The clustering accuracy can be seriously degraded if incorrect values are used. Unfortunately, in real situations, it is rarely possible for users to supply the parameter values accurately, which causes practical difficulties in applying these algorithms to real data. In this paper, we analyze the major challenges of projected clustering and suggest why these algorithms need to depend heavily on user parameters. Based on the analysis, we propose a new algorithm that exploits the clustering status to adjust the internal thresholds dynamically without the assistance of user parameters. According to the results of extensive experiments on real and synthetic data, the new method has excellent accuracy and usability. It outperformed the other algorithms even when correct parameter values were artificially supplied to them. The encouraging results suggest that projected clustering can be a practical tool for various kinds of real applications. <s> BIB011 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Data sets with multiple, heterogeneous feature spaces occur frequently. We present an abstract framework for integrating multiple feature spaces in the k-means clustering algorithm. Our main ideas are (i) to represent each data object as a tuple of multiple feature vectors, (ii) to assign a suitable (and possibly different) distortion measure to each feature space, (iii) to combine distortions on different feature spaces, in a convex fashion, by assigning (possibly) different relative weights to each, (iv) for a fixed weighting, to cluster using the proposed convex k-means algorithm, and (v) to determine the optimal feature weighting to be the one that yields the clustering that simultaneously minimizes the average within-cluster dispersion and maximizes the average between-cluster dispersion along all the feature spaces. Using precision/recall evaluations and known ground truth classifications, we empirically demonstrate the effectiveness of feature weighting in clustering on several different application domains. <s> BIB012 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Feature-weight assignment can be regarded as a generalization of feature selection. That is, if all values of featureweights are either 1 or 0, feature-weight assignment degenerates to the special case of feature selection. Generally speaking, a number in [0,1] can be assigned to a feature for indicating the importance of the feature. This paper shows that an appropriate assignment of feature-weight can improve the performance of fuzzy c-means clustering. The weight assignment is given by learning according to the gradient descent technique. Experiments on some UCI databases demonstrate the improvement of performance of fuzzy c-means clustering. <s> BIB013 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> This paper proposes a k-means type clustering algorithm that can automatically calculate variable weights. A new step is introduced to the k-means clustering process to iteratively update variable weights based on the current partition of data and a formula for weight calculation is proposed. The convergency theorem of the new clustering process is given. The variable weights produced by the algorithm measure the importance of variables in clustering and can be used in variable selection in data mining applications where large and complex real data are often involved. Experimental results on both synthetic and real data have shown that the new algorithm outperformed the standard k-means type algorithms in recovering clusters in data. <s> BIB014 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> This paper is to identify the clustering structure and the relevant features automatically and simultaneously in the context of Gaussian mixture model. We perform this task by introducing two sets of weight functions under the recently proposed Maximum Weighted Likelihood (MWL) learning framework. One set is to reward the significance of each component in the mixture, and the other one is to discriminate the relevance of each feature to the cluster structure. The experiments on both the synthetic and real-world data show the efficacy of the proposed algorithm. <s> BIB015 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> K-means is one of the most popular and widespread partitioning clustering algorithms due to its superior scalability and efficiency. Typically, the K-means algorithm treats all features fairly and sets weights of all features equally when evaluating dissimilarity. However, a meaningful clustering phenomenon often occurs in a subspace defined by a specific subset of all features. To address this issue, this paper proposes a novel feature weight self-adjustment (FWSA) mechanism embedded into K-means in order to improve the clustering quality of K-means. In the FWSA mechanism, finding feature weights is modeled as an optimization problem to simultaneously minimize the separations within clusters and maximize the separations between clusters. With this objective, the adjustment margin of a feature weight can be derived based on the importance of the feature to the clustering quality. At each iteration in K-means, all feature weights are adaptively updated by adding their respective adjustment margins. A number of synthetic and real data are experimented on to show the benefits of the proposed FWAS mechanism. In addition, when compared to a recent similar feature weighting work, the proposed mechanism illustrates several advantages in both the theoretical and experimental results. <s> BIB016 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> As a prolific research area in data mining, subspace clustering and related problems induced a vast quantity of proposed solutions. However, many publications compare a new proposition—if at all—with one or two competitors, or even with a so-called “naive” ad hoc solution, but fail to clarify the exact problem definition. As a consequence, even if two solutions are thoroughly compared experimentally, it will often remain unclear whether both solutions tackle the same problem or, if they do, whether they agree in certain tacit assumptions and how such assumptions may influence the outcome of an algorithm. In this survey, we try to clarify: (i) the different problem definitions related to subspace clustering in general; (ii) the specific difficulties encountered in this field of research; (iii) the varying assumptions, heuristics, and intuitions forming the basis of different approaches; and (iv) how several prominent solutions tackle different problems. <s> BIB017 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> In this paper, we consider the problem of unsupervised discrete feature selection/weighting. Indeed, discrete data are an important component in many data mining, machine learning, image processing, and computer vision applications. However, much of the published work on unsupervised feature selection has concentrated on continuous data. We propose a probabilistic approach that assigns relevance weights to discrete features that are considered as random variables modeled by finite discrete mixtures. The choice of finite mixture models is justified by its flexibility which has led to its widespread application in different domains. For the learning of the model, we consider both Bayesian and information-theoretic approaches through stochastic complexity. Experimental results are presented to illustrate the feasibility and merits of our approach on a difficult problem which is clustering and recognizing visual concepts in different image data. The proposed approach is successfully applied also for text clustering. <s> BIB018 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Organizing data into sensible groupings is one of the most fundamental modes of understanding and learning. As an example, a common scheme of scientific classification puts organisms into a system of ranked taxa: domain, kingdom, phylum, class, etc. Cluster analysis is the formal study of methods and algorithms for grouping, or clustering, objects according to measured or perceived intrinsic characteristics or similarity. Cluster analysis does not use category labels that tag objects with prior identifiers, i.e., class labels. The absence of category information distinguishes data clustering (unsupervised learning) from classification or discriminant analysis (supervised learning). The aim of clustering is to find structure in data and is therefore exploratory in nature. Clustering has a long and rich history in a variety of scientific fields. One of the most popular and simple clustering algorithms, K-means, was first published in 1955. In spite of the fact that K-means was proposed over 50 years ago and thousands of clustering algorithms have been published since then, K-means is still widely used. This speaks to the difficulty in designing a general purpose clustering algorithm and the ill-posed problem of clustering. We provide a brief overview of clustering, summarize well known clustering methods, discuss the major challenges and key issues in designing clustering algorithms, and point out some of the emerging and useful research directions, including semi-supervised clustering, ensemble clustering, simultaneous feature selection during data clustering, and large scale data clustering. <s> BIB019 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Subspace clustering finds sets of objects that are homogeneous in subspaces of high-dimensional datasets, and has been successfully applied in many domains. In recent years, a new breed of subspace clustering algorithms, which we denote as enhanced subspace clustering algorithms, have been proposed to (1) handle the increasing abundance and complexity of data and to (2) improve the clustering results. In this survey, we present these enhanced approaches to subspace clustering by discussing the problems they are solving, their cluster definitions and algorithms. Besides enhanced subspace clustering, we also present the basic subspace clustering and the related works in high-dimensional clustering. <s> BIB020 </s> A Survey on Soft Subspace Clustering <s> Recent years have witnessed proliferating development of subspace clustering (SC) techniques <s> Subspace clustering refers to the task of identifying clusters of similar objects or data records (vectors) where the similarity is defined with respect to a subset of the attributes (i.e., a subspace of the data space). The subspace is not necessarily (and actually is usually not) the same for different clusters within one clustering solution. In this article, the problems motivating subspace clustering are sketched, different definitions and usages of subspaces for clustering are described, and exemplary algorithmic solutions are discussed. Finally, we sketch current research directions. © 2012 Wiley Periodicals, Inc. © 2012 Wiley Periodicals, Inc. <s> BIB021
to overcome this challenge. The goal of SC is to locate clusters in different subspaces or a certain subspace of the original data space. The two main schools of SC algorithms are Hard Subspace Clustering (HSC) and Soft Subspace Clustering (SSC). Research in SC begins with in depth study of HSC methods for clustering high dimensional data. This category of SC algorithms attempts to identify the exact subspaces for different clusters, which can be further divided into bottom-up and top-down subspace search methods BIB010 . Examples of the former include CLIQUE BIB003 , ENCLUS  and MAFIA  ; and that of the latter are ORCLUS BIB005 , FINDIT BIB008 , DOC BIB009 ,  -Clusters  , and PROCLUS BIB004 . Other common HSC algorithms also include HARP BIB011 and LDR BIB006 . A detailed review of HSC algorithms can be found in BIB010 BIB020 BIB017 BIB021 . While the goal of HSC is to identify exact subspaces, SSC algorithms performs clustering in high dimensional spaces by assigning a weight to each dimension to measure the contribution of individual dimensions to the formation of a particular cluster. SSC can be considered as an extension of the conventional feature weighting clustering BIB002 BIB007 BIB012 BIB013 BIB001  BIB014 BIB015 BIB016 BIB018 . In this paper, SSC algorithms are hierarchically classified into three main categories, namely, (1) conventional SSC (CSSC), BIB019 independent SSC (ISSC), and extended SSC (ESSC). Here, CSSC refers to conventional feature weighting clustering algorithms, i.e., all clusters share the same subspace and a common weight vector. On the contrary, the weight vectors in ISSC are different for different clusters. In other words, each cluster has an independent subspace. Thus, ISSC may also be referred to as multiple features weighting clustering. XSSC represents a category of algorithms developed by extending the CSSC or ISSC algorithms with the introduction of new mechanisms to enhance clustering performance. The definitions of these three types of SSC are given in Table 1 . A detailed review of the characteristics of the algorithms will be discussed. The rest of this paper is organized as follows. The classification of the existing SSC algorithms is given in Section 2. The CSSC, ISSC and ESSC algorithms are comprehensively reviewed in Sections 3, 4 and 5 respectively. The perspectives and prospects of SSC are discussed in Section 6 and conclusions are given in Section 7. For clarity, the notations used in this paper are defined in Table 2 .