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]

• 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]

• 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]

• 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]