Search

• In this paper, an object-based clustering validity index with densities referred to as OCVD is proposed. This index uses densities of clusters to capture the exclusive contribution of each data object in both separation and compactness of clusters. • OCVD is superior to many existing clustering validity indices that capture the properties of clusters by using representative statistics such as mean, variance, diameter, etc. The reason is that those indices might not perform well in capturing the whole characteristics of clusters with arbitrary shapes but OCVD is well capable of doing so. • Although there are some existing density-based validity indices, studies show that they have problems such as poor performance on clusters with arbitrary shapes which are not necessarily perfectly separated and poor performance due to relying only on some representative data objects in clusters. Clustering validity indices are typically used as tools to find the correct number of clusters in a data set and/or to evaluate the quality of the clusters formed by clustering algorithms. Clustering validity indices measure separation and compactness of clusters. Typically, when applying a clustering algorithm, the input includes the number of clusters. After applying the algorithm with several different numbers of clusters, we determine the number of clusters to be the one with the best validity index. There are two types of clustering validity indices: external indices that are supervised, and internal indices that are unsupervised. The focus of this paper is on internal validity indices. Some existing internal validity indices capture the properties of the clusters by using representative statistics such as mean, variance, diameter, etc., however, these do not perform well when clusters have arbitrary shapes. One approach to overcome this issue is to use the density of the data objects in each cluster. That provides the advantage of capturing the full characteristics of the cluster which is most beneficial when there are clusters with arbitrary shapes. In the literature, a few density-based clustering validity indices have been proposed. However, some of them show poor performance when the clusters are not perfectly separated. Some others perform poorly because they use only representative objects from each cluster instead of all objects. The contribution of this paper is an internal validity index named the object-based clustering validity index with densities (OCVD). OCVD is a single number that averages the density-based contribution of individual data objects to both separation and compactness of clusters. The methodology behind calculating the density-based contributions of the objects is kernel density estimation. We show through several experiments that OCVD performs well in detecting the correct number of clusters in data sets with different cluster shapes including arbitrary shapes. [ABSTRACT FROM AUTHOR]

Abstract: In cluster analysis, one of the most challenging and difficult problems is the determination of the number of clusters in a data set, which is a basic input parameter for most clustering algorithms. To solve this problem, many algorithms have been proposed for either numerical or categorical data sets. However, these algorithms are not very effective for a mixed data set containing both numerical attributes and categorical attributes. To overcome this deficiency, a generalized mechanism is presented in this paper by integrating Rényi entropy and complement entropy together. The mechanism is able to uniformly characterize within-cluster entropy and between-cluster entropy and to identify the worst cluster in a mixed data set. In order to evaluate the clustering results for mixed data, an effective cluster validity index is also defined in this paper. Furthermore, by introducing a new dissimilarity measure into the k-prototypes algorithm, we develop an algorithm to determine the number of clusters in a mixed data set. The performance of the algorithm has been studied on several synthetic and real world data sets. The comparisons with other clustering algorithms show that the proposed algorithm is more effective in detecting the optimal number of clusters and generates better clustering results. [Copyright &y& Elsevier]

Abstract: In the current paper we present a method for assessing cluster stability. This method, combined with a clustering algorithm, yields an estimate of the data partition, namely, the number of clusters. We adopt the cluster stability standpoint where clusters are imagined as islands of “high” density in a sea of “low” density. Explicitly, a cluster is associated with its high density core. Our approach offers to evaluate the goodness of a cluster by the similarity amongst the entire cluster and its core. We propose to measure this resemblance by two-sample tests or by probability distances between appropriate probability distributions. The distances are calculated on clustered samples drawn from the source population according to two different distributions. The first law is the underlying set distribution. The second law is constructed so that it represents the clusters’ cores. Here, a variant of the k-nearest neighbor density estimation is applied, so that items belonging to cores have a much higher chance to be selected. As the sample distribution is unknown a distribution-free two-sample test is required to examine the mentioned correspondence. For constructing such a test, we use distance functions built on negative definite kernels. In practice, outliers in the samples and limitations of the clustering algorithm heavily contribute to the noise level. As a result of this shortcoming the distance values have to be determined for many pairs of samples and therefore an empirical distance''s distribution is obtained. The distribution is dependent on the examined number of clusters. To prevent this property for biasing the results we normalize the distances. It is conjectured that the true number of clusters yields the most concentrated normalized distribution. To measure the concentration we use the sample mean and the sample 25th percentile. The paper exhibits the good performance of the proposed method on synthetic and real-world data. [Copyright &y& Elsevier]

• Possibilistic c-means (PCM) clustering by incorporating the sparsity idea with feature weights is further studied. • We propose two approaches that make the PCM clustering with the least absolute shrinkage and selection operator (Lasso), called S-PCM1 and S-PCM2. • Synthetic and real data sets are used to compare the proposed S-PCM1 and S-PCM2 with some existing algorithms. • Experimental results and comparisons demonstrate the good effectiveness and usefulness of the proposed S-PCM1 and S-PCM2 algorithms. Krishnapuram and Keller first proposed possibilistic c-means (PCM) clustering in 1993. Afterward, PCM was widely studied with various extensions. The PCM algorithm and its extensions always treat feature components under equal importance, but, in real applications, different features may better have different weights. Recently, Yang and Benjamin in 2021 proposed a feature-weighted PCM clustering with feature reduction. Although Yang and Benjamin (2021) can reduce feature dimensions, it still encounters the curse of dimensionality for high dimensional data. One possible way to address this problem is to conduct a sparse clustering technique. In this paper, we further study the PCM clustering by incorporating the idea of sparsity with different feature weights. We propose two approaches that use the PCM clustering with the least absolute shrinkage and selection operator (Lasso). The first one is the sparse PCM subject to a Lasso constraint of feature weights, called S-PCM1. The second is the sparse PCM by adding a Lasso penalty term of feature weights in the objective function, called S-PCM2. We show that S-PCM1 and S-PCM2 are theoretically the same, and both can induce sparsity in features, but they use different procedures in algorithms. Synthetic and real data sets are used to compare S-PCM1 and S-PCM2 with some existing sparsity clustering algorithms. Experimental results and comparisons demonstrate the effectiveness and usefulness of the proposed S-PCM1 and S-PCM2 clustering algorithms. [ABSTRACT FROM AUTHOR]

• A novel density peaks clustering algorithm called BC-DPC is proposed based on mutual nearest neighbor and connectivity, which can quickly find the correct cluster centers and obtain satisfactory clustering results. • A new definition of density is proposed, which can elimilate the density difference among different clusters and accurately estimate the density of the data points. • This algorithm fully considers the density change and connectivity between data points when calculating the relative distance. This makes the domino effect can be avoided in the clustering process. • The algorithm proposes a novel fast search strategy, which is used to calculate relative distance of data points. This strategy makes the efficiency of the proposed algorithm greatly improved. • The performance of the proposed algorithm is compared to DPC and five improved DPC in synthetic, UCI, and image datasets. • The experimental results show the effectiveness and the efficiency of the proposed algorithm. Density peaks clustering (DPC) algorithm regards the density peaks as the potential cluster centers, and assigns the non-center point into the cluster of its nearest higher-density neighbor. Although DPC can discover clusters with arbitrary shapes, it has some limitations. On the one hand, the density measure of DPC fails to eliminate the density difference among different clusters, which affects the accuracy of recognizing cluster center. On the other hand, the nearest higher-density point is determined without considering connectivity, which leads to continuously clustering errors. Therefore, DPC fails to obtain satisfactory clustering results on datasets with great density difference among clusters. In order to eliminate these limitations, a novel DPC algorithm based on balance density and connectivity (BC-DPC) is proposed. First, the balance density is proposed to eliminate the density difference among different clusters to accurately recognize cluster centers. Second, the connectivity between a data point and its nearest higher-density point is guaranteed by mutual nearest neighbor relationship to avoid continuously clustering errors. Finally, a fast search strategy is proposed to find the nearest higher-density point. The experimental results on synthetic, UCI, and image datasets demonstrate the efficiency and effectiveness of the proposed algorithm in this paper. [ABSTRACT FROM AUTHOR]

In this paper, a dynamic niching clustering algorithm based on individual-connectedness (DNIC) is proposed for unsupervised classification with no prior knowledge. It aims to automatically evolve the optimal number of clusters as well as the cluster centers of the data set based on the proposed adaptive compact k -distance neighborhood algorithm. More specifically, with the adaptive selection of the number of the nearest neighbor and the individual-connectedness algorithm, DNIC often achieves several sets of connecting individuals and each set composes an independent niche. In practice, each set of connecting individuals corresponds to a homogeneous cluster and this ensures the separability of an arbitrary data set theoretically. An application of the DNIC clustering algorithm in color image segmentation is also provided. Experimental results demonstrate that the DNIC clustering algorithm has high performance and flexibility. [ABSTRACT FROM AUTHOR]

• Efficient kNN search based on feature learning, clustering, and adaptive k values. • Several proposals to automatically optimize the search parameters. • Comprehensive experimentation with 10 datasets of different typology and size. • Results demonstrate that the proposal outperforms state-of-the-art methods. The k -Nearest Neighbor (k NN) algorithm is widely used in the supervised learning field and, particularly, in search and classification tasks, owing to its simplicity, competitive performance, and good statistical properties. However, its inherent inefficiency prevents its use in most modern applications due to the vast amount of data that the current technological evolution generates, being thus the optimization of k NN-based search strategies of particular interest. This paper introduces the caKD+ algorithm, which tackles this limitation by combining the use of feature learning techniques, clustering methods, adaptive search parameters per cluster, and the use of pre-calculated K-Dimensional Tree structures, and results in a highly efficient search method. This proposal has been evaluated using 10 datasets and the results show that caKD+ significantly outperforms 16 state-of-the-art efficient search methods while still depicting such an accurate performance as the one by the exhaustive k NN search. [ABSTRACT FROM AUTHOR]

• A novel non-parametric clustering algorithm based on the concept of divide-and-merge. • Ability to discover both convex and non-convex shaped clusters. • Ability to discover clusters different in densities. • Ability to detect and remove outliers/noise in the data. • Usability for high dimensional data and easily tunable or fixed hyperparameters. In this paper, a novel non-parametric clustering algorithm which is based on the concept of divide-and-merge is proposed. The proposed algorithm is based on two primary phases, after data cleaning: (i) the Division phase and (ii) the Merging phase. In the initial phase of division, the data is divided into an optimized number of small sub-clusters utilizing all the dimensions of the data. In the second phase of merging, the small sub-clusters obtained as a result of division are merged according to an advanced statistical metric to form the actual clusters in the data. The proposed algorithm has the following merits: (i) ability to discover both convex and non-convex shaped clusters, (ii) ability to discover clusters different in densities, (iii) ability to detect and remove outliers/noise in the data (iv) easily tunable or fixed hyperparameters (v) and its usability for high dimensional data. The proposed algorithm is extensively tested on 20 benchmark datasets including both, the synthetic and the real datasets and is found better/competing to the existing state-of-the-art parametric and non-parametric clustering algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Most of the existing clustering approaches are applicable to purely numerical or categorical data only, but not the both. In general, it is a nontrivial task to perform clustering on mixed data composed of numerical and categorical attributes because there exists an awkward gap between the similarity metrics for categorical and numerical data. This paper therefore presents a general clustering framework based on the concept of object-cluster similarity and gives a unified similarity metric which can be simply applied to the data with categorical, numerical, and mixed attributes. Accordingly, an iterative clustering algorithm is developed, whose outstanding performance is experimentally demonstrated on different benchmark data sets. Moreover, to circumvent the difficult selection problem of cluster number, we further develop a penalized competitive learning algorithm within the proposed clustering framework. The embedded competition and penalization mechanisms enable this improved algorithm to determine the number of clusters automatically by gradually eliminating the redundant clusters. The experimental results show the efficacy of the proposed approach. [Copyright &y& Elsevier]

• Properties that help solve the clustering users dilemma. • Weighted properties formally differentiate clustering methods. • A formal classification highlights advantages of center-based clustering techniques. This paper makes a major step towards addressing a long-standing challenge in cluster analysis, known as the user's dilemma , which is the problem of selecting an appropriate clustering algorithm for a specific task. A formal approach for addressing this challenge relies on the identification of succinct, user-friendly properties that capture formal differences amongst clustering techniques. While helpful for gaining insight into the nature of clustering paradigms, there is a theory-practice gap that has so far limited the utility of this approach: Formal properties typically highlight advantages of classical linkage-based algorithms, while practical experience shows that center-based methods are preferable for many applications. We present simple new properties that delineate core differences between common clustering paradigms and overcome this theory-practice gap. The properties we present give a formal understanding of the advantages of center-based approaches for some applications and insight into when different clustering paradigms should be used. These properties address how sensitive algorithms are to changes in element frequencies, which we capture in a generalized setting where every element is associated with a real-valued weight. To complement extensive formal analysis, we discuss how these properties can be applied in practice. [ABSTRACT FROM AUTHOR]

• Fuzzy c-means (FCM) clustering had been extended for handling multi-view data. • We propose a novel multi-view FCM (MVFCM) clustering algorithm with view and feature weights based on collaborative learning, called Co-FW-MVFCM. • The proposed Co-FW-MVFCM contains a two-step schema that includes a local step and a collaborative step. • The Co-FW-MVFCM can give feature reduction to exclude redundant feature components during clustering processes. • Comparisons among Co-FW-MVFCM and existing MVFCM algorithms actually demonstrate the effectiveness and usefulness of Co-FW-MVFCM. Fuzzy c-means (FCM) clustering had been extended for handling multi-view data with collaborative idea. However, these collaborative multi-view FCM treats multi-view data under equal importance of feature components. In general, different features should take different weights for clustering real multi-view data. In this paper, we propose a novel multi-view FCM (MVFCM) clustering algorithm with view and feature weights based on collaborative learning, called collaborative feature-weighted MVFCM (Co-FW-MVFCM). The Co-FW-MVFCM contains a two-step schema that includes a local step and a collaborative step. The local step is a single-view partition process to produce local partition clustering in each view, and the collaborative step is sharing information of their memberships between different views. These two steps are then continuing by an aggregation way to get a global result after collaboration. Furthermore, the embedded feature-weighted procedure in Co-FW-MVFCM can give feature reduction to exclude redundant/irrelevant feature components during clustering processes. Experiments with several data sets demonstrate that the proposed Co-FW-MVFCM algorithm can completely identify irrelevant feature components in each view and that, additionally, it can improve the performance of the algorithm. Comparisons of Co-FW-MVFCM with some existing MVFCM algorithms are made and also demonstrated the effectiveness and usefulness of the proposed Co-FW-MVFCM clustering algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Fuzzy data clustering plays an important role in practical use and has become a prerequisite step for decision-making in fuzzy environment. In this paper we propose a new algorithm, called FuzzyGES for unsupervised fuzzy clustering based on adaptation of the recently proposed Grouping Evolution Strategy (GES). To adapt GES for fuzzy clustering we devise a fuzzy counterpart of the grouping mutation operator typically used in GES, and employ it in a two phase procedure to generate a new clustering solution. Unlike conventional clustering algorithms which should get the number of clusters as an input, FuzzyGES tries to determine the true number of clusters as well as providing the optimal cluster centroids after several iterations. The proposed approach is validated through using several data sets and results are compared with those of fuzzy c-means algorithm, particle swarm optimization algorithm (PSO), differential evolution (DE) and league championship algorithm (LCA). We also investigate the performance of FuzzyGES through using different cluster validity indices. Our results indicate that FuzzyGES is fast and provides acceptable results in terms of both determining the correct number of clusters and the accurate cluster centroids. [Copyright &y& Elsevier]

Abstract: The attributes describing a data set may often be arranged in meaningful subsets, each of which corresponds to a different aspect of the data. An unsupervised algorithm (SCAD) that simultaneously performs fuzzy clustering and aspects weighting was proposed in the literature. However, SCAD may fail and halt given certain conditions. To fix this problem, its steps are modified and then reordered to reduce the number of parameters required to be set by the user. In this paper we prove that each step of the resulting algorithm, named ASCAD, globally minimizes its cost-function with respect to the argument being optimized. The asymptotic analysis of ASCAD leads to a time complexity which is the same as that of fuzzy c-means. A hard version of the algorithm and a novel validity criterion that considers aspect weights in order to estimate the number of clusters are also described. The proposed method is assessed over several artificial and real data sets. [Copyright &y& Elsevier]

Abstract: In this paper, we present a novel way of analyzing and summarizing a collection of curves, based on piecewise constant density estimation. The curves are partitioned into clusters, and the dimensions of the curves points are discretized into intervals. The cross-product of these univariate partitions forms a data grid of cells, which represents a nonparametric estimator of the joint density of the curves and point dimensions. The best model is selected using a Bayesian model selection approach and retrieved using combinatorial optimization algorithms. The proposed method requires no parameter setting and makes no assumption regarding the curves; beyond functional data, it can be applied to distributional data. The practical interest of the approach for functional data and distributional data exploratory analysis is presented on two real world datasets. [Copyright &y& Elsevier]

Abstract: Recently, the Student''s t-factor mixture analyzer (tFMA) has been proposed. Compared with the mixture of Student''s t-factor analyzers (MtFA), the tFMA has better performance when processing high-dimensional data. Moreover, the factors estimated by the tFMA can be visualized in a low-dimensional latent space, which is not shared by the MtFA. However, as the tFMA belongs to finite mixtures and the related parameter estimation method is based on the maximum likelihood criterion, it could not automatically determine the appropriate model complexity according to the observed data, leading to overfitting. In this paper, we propose an infinite Student''s t-factor mixture analyzer (itFMA) to handle this issue. The itFMA is based on the nonparametric Bayesian statistics which assumes infinite number of mixing components in advance, and automatically determines the proper number of components after observing the high-dimensional data. Moreover, we derive an efficient variational inference algorithm for the itFMA. The proposed itFMA and the related variational inference algorithm are used to cluster and classify high-dimensional data. Experimental results of some applications show that the itFMA has good generalization capacity, offering a more robust and powerful performance than other competing approaches. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a novel Fast Affinity Propagation clustering approach (FAP). FAP simultaneously considers both local and global structure information contained in datasets, and is a high-quality multilevel graph partitioning method that can implement both vector-based and graph-based clustering. First, a new Fast Sampling algorithm (FS) is proposed to coarsen the input sparse graph and choose a small number of final representative exemplars. Then a density-weighted spectral clustering method is presented to partition those exemplars on the global underlying structure of data manifold. Finally, the cluster assignments of all data points can be achieved through their corresponding representative exemplars. Experimental results on two synthetic datasets and many real-world datasets show that our algorithm outperforms the state-of-the-art original affinity propagation and spectral clustering algorithms in terms of speed, memory usage, and quality on both vector-based and graph-based clustering. [Copyright &y& Elsevier]

Abstract: This paper presents an online learning approach to video-based face recognition that does not make any assumptions about the pose, expressions or prior localization of facial landmarks. Learning is performed online while the subject is imaged and gives near realtime feedback on the learning status. Face images are automatically clustered based on the similarity of their local features. The learning process continues until the clusters have a required minimum number of faces and the distance of the farthest face from its cluster mean is below a threshold. A voting algorithm is employed to pick the representative features of each cluster. Local features are extracted from arbitrary keypoints on faces as opposed to pre-defined landmarks and the algorithm is inherently robust to large scale pose variations and occlusions. During recognition, video frames of a probe are sequentially matched to the clusters of all individuals in the gallery and its identity is decided on the basis of best temporally cohesive cluster matches. Online experiments (using live video) were performed on a database of 50 enrolled subjects and another 22 unseen impostors. The proposed algorithm achieved a recognition rate of 97.8% and a verification rate of 100% at a false accept rate of 0.0014. For comparison, experiments were also performed using the Honda/UCSD database and 99.5% recognition rate was achieved. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a supervised feature selection approach is presented, which is based on metric applied on continuous and discrete data representations. This method builds a dissimilarity space using information theoretic measures, in particular conditional mutual information between features with respect to a relevant variable that represents the class labels. Applying a hierarchical clustering, the algorithm searches for a compression of the information contained in the original set of features. The proposed technique is compared with other state of art methods also based on information measures. Eventually, several experiments are presented to show the effectiveness of the features selected from the point of view of classification accuracy. [Copyright &y& Elsevier]

Abstract: Voting-based consensus clustering refers to a distinct class of consensus methods in which the cluster label mismatch problem is explicitly addressed. The voting problem is defined as the problem of finding the optimal relabeling of a given partition with respect to a reference partition. It is commonly formulated as a weighted bipartite matching problem. In this paper, we present a more general formulation of the voting problem as a regression problem with multiple-response and multiple-input variables. We show that a recently introduced cumulative voting scheme is a special case corresponding to a linear regression method. We use a randomized ensemble generation technique, where an overproduced number of clusters is randomly selected for each ensemble partition. We apply an information theoretic algorithm for extracting the consensus clustering from the aggregated ensemble representation and for estimating the number of clusters. We apply it in conjunction with bipartite matching and cumulative voting. We present empirical evidence showing substantial improvements in clustering accuracy, stability, and estimation of the true number of clusters based on cumulative voting. The improvements are achieved in comparison to consensus algorithms based on bipartite matching, which perform very poorly with the chosen ensemble generation technique, and also to other recent consensus algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, a new algorithm named polar self-organizing map (PolSOM) is proposed. PolSOM is constructed on a 2-D polar map with two variables, radius and angle, which represent data weight and feature, respectively. Compared with the traditional algorithms projecting data on a Cartesian map by using the Euclidian distance as the only variable, PolSOM not only preserves the data topology and the inter-neuron distance, it also visualizes the differences among clusters in terms of weight and feature. In PolSOM, the visualization map is divided into tori and circular sectors by radial and angular coordinates, and neurons are set on the boundary intersections of circular sectors and tori as benchmarks to attract the data with the similar attributes. Every datum is projected on the map with the polar coordinates which are trained towards the winning neuron. As a result, similar data group together, and data characteristics are reflected by their positions on the map. The simulations and comparisons with Sammon''s mapping, SOM and ViSOM are provided based on four data sets. The results demonstrate the effectiveness of the PolSOM algorithm for multidimensional data visualization. [Copyright &y& Elsevier]

Abstract: In this paper, a genetic clustering algorithm based on dynamic niching with niche migration (DNNM-clustering) is proposed. It is an effective and robust approach to clustering on the basis of a similarity function relating to the approximate density shape estimation. In the new algorithm, a dynamic identification of the niches with niche migration is performed at each generation to automatically evolve the optimal number of clusters as well as the cluster centers of the data set without invoking cluster validity functions. The niches can move slowly under the migration operator which makes the dynamic niching method independent of the radius of the niches. Compared to other existing methods, the proposed clustering method exhibits the following robust characteristics: (1) robust to the initialization, (2) robust to clusters volumes (ability to detect different volumes of clusters), and (3) robust to noise. Moreover, it is free of the radius of the niches and does not need to pre-specify the number of clusters. Several data sets with widely varying characteristics are used to demonstrate its superiority. An application of the DNNM-clustering algorithm in unsupervised classification of the multispectral remote sensing image is also provided. [Copyright &y& Elsevier]

Abstract: Separating text lines in unconstrained handwritten documents remains a challenge because the handwritten text lines are often un-uniformly skewed and curved, and the space between lines is not obvious. In this paper, we propose a novel text line segmentation algorithm based on minimal spanning tree (MST) clustering with distance metric learning. Given a distance metric, the connected components (CCs) of document image are grouped into a tree structure, from which text lines are extracted by dynamically cutting the edges using a new hypervolume reduction criterion and a straightness measure. By learning the distance metric in supervised learning on a dataset of pairs of CCs, the proposed algorithm is made robust to handle various documents with multi-skewed and curved text lines. In experiments on a database with 803 unconstrained handwritten Chinese document images containing a total of 8,169 lines, the proposed algorithm achieved a correct rate 98.02% of line detection, and compared favorably to other competitive algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, a new clustering algorithm based on genetic algorithm (GA) with gene rearrangement (GAGR) is proposed, which in application may effectively remove the degeneracy for the purpose of a more efficient search. A new crossover operator that exploits a measure of similarity between chromosomes in a population is also presented. Adaptive probabilities of crossover and mutation are employed to prevent the convergence of the GAGR to a local optimum. Using the real-world data sets, we compare the performance of our GAGR clustering algorithm with K-means algorithm and other GA methods. An application of the GAGR clustering algorithm in unsupervised classification of multispectral remote sensing images is also provided. Experiment results demonstrate that the GAGR clustering algorithm has high performance, effectiveness and flexibility. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: In this paper, we present a fast codebook re-quantization algorithm (FCRA) using codewords of a codebook being re-quantized as the training vectors to generate the re-quantized codebook. Our method is different from the available approach, which uses the original training set to generate a re-quantized codebook. Compared to the traditional approach, our method can reduce the computing time dramatically, since the number of codewords of a codebook being re-quantized is usually much smaller than the number of original training vectors. Our method first classifies codewords of a re-quantized codebook into static and active groups. This approach uses the information of codeword displacements between successive partitions to reject impossible candidates in the partition process of codebook re-quantization. By implementing a fast search algorithm used for vector quantization encoding (MFAUPI) in the partition step of FCRA, the computational complexity of codebook re-quantization can be further reduced significantly. Using MFAUPI, the computing time of FCRA can be reduced by a factor of 1.55–3.78. Compared with the available approach OARC (optimization algorithm for re-quantization codebook), our proposed method can reduce the codebook re-quantization time by a factor of about 8005 using a training set of six real images. This reduction factor is increased when the re-quantized codebook size and/or training set size are increased. It is noted that our proposed algorithm can generate the same re-quantized codebook as that produced by the OARC. [Copyright &y& Elsevier]

Abstract: In this paper, we present a fast codebook generation algorithm called CGAUCD (Codebook Generation Algorithm Using Codeword Displacement) by making use of the codeword displacement between successive partition processes. By implementing a fast search algorithm named MFAUPI (Modified Fast Algorithm Using Projection and Inequality) for VQ encoding in the partition step of CGAUCD, the codebook generation time can be further reduced significantly. Using MFAUPI, the computing time of CGAUCD can be reduced by a factor of 4.7–7.6. Compared to Generalized Lloyd Algorithm (GLA), our proposed method can reduce the codebook generation time by a factor of 35.9–121.2. Compared to the best codebook generation algorithm to our knowledge, our approach can further reduce the corresponding computing time by 26.0–32.8%. It is noted that our proposed algorithm can generate the same codebook as that produced by the GLA. The superiority of our method is more remarkable when a larger codebook is generated. [Copyright &y& Elsevier]

Abstract: Classical clustering algorithms are based on the concept that a cluster center is a single point. Clusters which are not compact around a single point are not candidates for classical clustering approaches. In this paper we present a new clustering paradigm in which the cluster center is a linear manifold. Clusters are groups of points compact around a linear manifold. A linear manifold of dimension 0 is a point. So clustering around a center point is a special case of linear manifold clustering. Linear manifold clustering (LMCLUS) identifies subsets of the data which are embedded in arbitrary oriented lower dimensional linear manifolds. Minimal subsets of points are repeatedly sampled to construct trial linear manifolds of various dimensions. Histograms of the distances of the points to each trial manifold are computed. The sampling corresponding to the histogram having the best separation between a mode near zero and the rest is selected and the data points are partitioned on the basis of the best separation. The repeated sampling then continues recursively on each block of the partitioned data. A broad evaluation of some 100 experiments over real and synthetic data sets demonstrates the general superiority of this algorithm over any of the competing algorithms in terms of accuracy and computation time. Its expected computational time is linearly proportional to the data set dimension and data set size. Its accuracy ranges from near 0.90 to 0.99 depending on the experiment and is generally much higher than the accuracy of the competing clustering algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we develop a semi-supervised regression algorithm to analyze data sets which contain both categorical and numerical attributes. This algorithm partitions the data sets into several clusters and at the same time fits a multivariate regression model to each cluster. This framework allows one to incorporate both multivariate regression models for numerical variables (supervised learning methods) and k-mode clustering algorithms for categorical variables (unsupervised learning methods). The estimates of regression models and k-mode parameters can be obtained simultaneously by minimizing a function which is the weighted sum of the least-square errors in the multivariate regression models and the dissimilarity measures among the categorical variables. Both synthetic and real data sets are presented to demonstrate the effectiveness of the proposed method. [Copyright &y& Elsevier]

Abstract: Erich Novak and Klaus Ritter developed in 1996 a global optimization algorithm that uses hyperbolic cross points (HCPs). In this paper we develop a hybrid algorithm for clustering called CMHCP that uses a modified version of this HCP algorithm for global search and the alternating optimization for local search. The program has been tested extensively with very promising results and high efficiency. This provides a nice addition to the arsenal of global optimization in clustering. In the process, we also analyze the smoothness of some reformulated objective functions. [Copyright &y& Elsevier]

Abstract: Based on the recently published point symmetry distance (PSD) measure, this paper presents a novel PSD measure, namely symmetry similarity level (SSL) operator for K-means algorithm. Our proposed modified point symmetry-based K-means (MPSK) algorithm is more robust than the previous PSK algorithm by Su and Chou. Not only the proposed MPSK algorithm is suitable for the symmetrical intra-clusters as the PSK algorithm does, the proposed MPSK algorithm is also suitable for the symmetrical inter-clusters. In addition, two speedup strategies are presented to reduce the time required in the proposed MPSK algorithm. Experimental results demonstrate the significant execution-time improvement and the extension to the symmetrical inter-clusters of the proposed MPSK algorithm when compared to the previous PSK algorithm. [Copyright &y& Elsevier]

Abstract: Though most approaches to protein comparison are based on their structure, several studies produced evidence of a strict correlation between the surface characteristics of proteins and the way they interact. Surface-based techniques for protein comparison typically require applying clustering algorithms to the punctual 3D description of the surface in order to produce a compact surface representation, capable of effectively condensing its description. In this paper, we propose a formalization of the requirements for surface clustering in the biochemical context and present two different clustering techniques that meet them, based, respectively, on region-growing and on an original template matching algorithm. We discuss the validity of these techniques with the support of tests performed on a set of about one hundred protein models generated by punctual mutations of four structurally characterized proteins. Finally, an analysis is made of how different factors impact on the effectiveness of clustering in capturing surface similarities. [Copyright &y& Elsevier]

Abstract: This paper presents a multi-ant colonies approach for clustering data that consists of some parallel and independent ant colonies and a queen ant agent. Each ant colony process takes different types of ants moving speed and different versions of the probability conversion function to generate various clustering results with an ant-based clustering algorithm. These results are sent to the queen ant agent and combined by a hypergraph model to calculate a new similarity matrix. The new similarity matrix is returned back to each ant colony process to re-cluster the data using the new information. Experimental evaluation shows that the average performance of the aggregated multi-ant colonies algorithms outperforms that of the single ant-based clustering algorithm and the popular K-means algorithm. The result also shows that the lowest outliers strategy for selecting the current data set has the best performance quality. [Copyright &y& Elsevier]

Abstract: In this paper, we offer a simple and accurate clustering algorithm which was derived as a closed-form analytical solution to a cluster fit function minimization problem. As a result, the algorithm finds the global minimum of the fit function, and combines exceptional efficiency with optimal clustering results. [Copyright &y& Elsevier]

Abstract: In this paper we propose a clustering algorithm to cluster data with arbitrary shapes without knowing the number of clusters in advance. The proposed algorithm is a two-stage algorithm. In the first stage, a neural network incorporated with an ART-like training algorithm is used to cluster data into a set of multi-dimensional hyperellipsoids. At the second stage, a dendrogram is built to complement the neural network. We then use dendrograms and so-called tables of relative frequency counts to help analysts to pick some trustable clustering results from a lot of different clustering results. Several data sets were tested to demonstrate the performance of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, the conventional k-modes-type algorithms for clustering categorical data are extended by representing the clusters of categorical data with k-populations instead of the hard-type centroids used in the conventional algorithms. Use of a population-based centroid representation makes it possible to preserve the uncertainty inherent in data sets as long as possible before actual decisions are made. The k-populations algorithm was found to give markedly better clustering results through various experiments. [Copyright &y& Elsevier]

Clustering is an important research topic that has practical applications in many fields. It has been demonstrated that fuzzy clustering, using algorithms such as the fuzzy C-means (FCM), has clear advantages over crisp and probabilistic clustering methods. Like most clustering algorithms, however, FCM and its derivatives need the number of clusters in the given data set as one of their initializing parameters. The main goal of this paper is to develop an effective fuzzy algorithm for automatically determining the number of clusters. After a brief review of the relevant literature, we present a new algorithm for determining the number of clusters in a given data set and a new validity index for measuring the “goodness” of clustering. Experimental results and comparisons are given to illustrate the performance of the new algorithm. [Copyright &y& Elsevier]

Traditional intrusion detection methods lack extensibility in face of changing network configurations as well as adaptability in face of unknown attack types. Meanwhile, current machine-learning algorithms need labeled data for training first, so they are computational expensive and sometimes misled by artificial data. In this paper, a new detection algorithm, the Intrusion Detection Based on Genetic Clustering (IDBGC) algorithm, is proposed. It can automatically establish clusters and detect intruders by labeling normal and abnormal groups. Computer simulations show that this algorithm is effective for intrusion detection. [Copyright &y& Elsevier]

Data clustering is typically considered a subjective process, which makes it problematic. For instance, how does one make statistical inferences based on clustering? The matter is different with pattern classification, for which two fundamental characteristics can be stated: (1) the error of a classifier can be estimated using “test data,” and (2) a classifier can be learned using “training data.” This paper presents a probabilistic theory of clustering, including both learning (training) and error estimation (testing). The theory is based on operators on random labeled point processes. It includes an error criterion in the context of random point sets and representation of the Bayes (optimal) cluster operator for a given random labeled point process. Training is illustrated using a nearest-neighbor approach, and trained cluster operators are compared to several classical clustering algorithms. [Copyright &y& Elsevier]

In this paper, we present a novel competitive EM (CEM) algorithm for finite mixture models to overcome the two main drawbacks of the EM algorithm: often getting trapped at local maxima and sometimes converging to the boundary of the parameter space. The proposed algorithm is capable of automatically choosing the clustering number and selecting the “split” or “merge” operations efficiently based on the new competitive mechanism we propose. It is insensitive to the initial configuration of the mixture component number and model parameters.Experiments on synthetic data show that our algorithm has very promising performance for the parameter estimation of mixture models. The algorithm is also applied to the structure analysis of complicated Chinese characters. The results show that the proposed algorithm performs much better than previous methods with slightly heavier computation burden. [Copyright &y& Elsevier]

This paper presents new robust clustering algorithms, which significantly improve upon the noise and initialization sensitivity of traditional mixture decomposition algorithms, and simplify the determination of the optimal number of clusters in the data set. The algorithms implement maximum likelihood mixture decomposition of multivariate t-distributions, a robust parametric extension of gaussian mixture decomposition. We achieve improved convergence capability relative to the expectation–maximization (EM) approach by deriving deterministic annealing EM (DAEM) algorithms for this mixture model and turning them into agglomerative algorithms (going through a monotonically decreasing number of components), an approach we term deterministic agglomeration EM (DAGEM). Two versions are derived, based on two variants of DAEM for mixture models. Simulation studies demonstrate the algorithms’ performance for mixtures with isotropic and non-isotropic covariances in two and 10 dimensions with known or unknown levels of outlier contamination. [Copyright &y& Elsevier]

• A graph-based learning using multiple kernels and multiple views. • A self-weighted algorithm where each kernel of each view gets an appropriate weight automatically. • Robustness of the algorithm to reduce the effect of data outliers and noises present in the data set. • A unified framework for graph construction, kernel learning and label learning. The studies of hidden complex structures in data have popularized the use of graph-based learning methods in semi-supervised and unsupervised learning tasks. Kernelized graph-based methods are proven to perform better, but these methods suffer from the issue of appropriate kernel selection. Instead of using multiple views, these methods generally use a single view. But multi-view methods need a proper weight assignment technique to each view in proportion to their contribution to the learning task. To solve this, a novel Self-weighted Multi-view Multiple Kernel Learning (SMVMKL) framework is proposed using multiple kernels on multiple views that automatically assigns appropriate weight to each kernel of each view without introducing an additional parameter. But the real-world data that is either noisy or corrupt with outliers which may effect the performance of the proposed SMVMKL method. To deal with this, a Robust Self-weighted Multi-view Multiple Kernel Learning (RSMVMKL) framework using the l 2,1 -norm has also been proposed that reduces the effect of outliers present in the data set. Both the proposed methods have been evaluated on multiple benchmark data sets and result in a performance comparable with the other state-of-the-art multi-view methods considered in this paper. [ABSTRACT FROM AUTHOR]

Bipartite spectral graph partition (BSGP) is a school of the most well-known algorithms designed for the bipartite graph partition problem. It is also a fundamental mathematical model widely used in the tasks of co-clustering and fast spectral clustering. In BSGP, the key is to find the minimal normalized cuts (Ncuts) of bipartite graph. However, the convolutional BSGP algorithms usually need to use the singular value decomposition (SVD) to find the minimal Ncuts, which is computational prohibitive. Under this circumstance, the application range of those methods would be limited when the volume of the dataset is huge or the dimension of features is high. To overcome this problem, this paper proposes a novel weighted bilateral k -means (WBKM) algorithm and applies it for co-clustering and fast spectral clustering. Specifically, WBKM is a relaxation of the problem of finding the minimal Ncuts of bipartite graph, so it can be seen as a new solution for the minimal-Ncuts problem in bipartite graph. Different from the conventional relaxation ways, WBKM relaxes the minimal-Ncuts problem to a Non-negative decomposition problem which can be solved by an efficient iterative method. Therefore, the running speed of the proposed method is much faster. Besides, as our model can directly output the clustering results without any help of post-procedures, its solution tends to be more close to the ideal solution of the minimal-Ncuts problem than that of the conventional BSGP algorithms. To demonstrate the effectiveness and efficiency of the proposed method, extensive experiments on various types of datasets are conducted. Compared with other state-of-the-art methods, the proposed WBKM not only has faster computational speed, but also achieves more promising clustering results. [ABSTRACT FROM AUTHOR]