Search

We revisit the problem of fair clustering, first introduced by Chierichetti et al. (Fair clustering through fairlets, 2017), which requires each protected attribute to have approximately equal representation in every cluster, i.e., a Balance property. Existing solutions to fair clustering are either not scalable or do not achieve an optimal trade-off between clustering objectives and fairness. In this paper, we propose a new notion of fairness which we call τ -ratio fairness, that strictly generalizes the Balance property and enables a fine-grained efficiency vs. fairness trade-off. Furthermore, we show that a simple greedy round-robin-based algorithm achieves this trade-off efficiently. Under a more general setting of multi-valued protected attributes, we rigorously analyze the theoretical properties of the proposed algorithm, the Fair Round-Robin Algorithm for Clustering Over-End ( FRAC OE ). We also propose a heuristic algorithm, Fair Round-Robin Algorithm for Clustering (FRAC), that applies round-robin allocation at each iteration of a vanilla clustering algorithm. Our experimental results suggest that both FRAC and FRAC OE outperform all the state-of-the-art algorithms and work exceptionally well even for a large number of clusters. [ABSTRACT FROM AUTHOR]

Density-based clustering has received increasing attention for its ability to handle clusters of arbitrary shapes. However, it still has difficulties in mining clusters of arbitrary densities, especially the clusters of sparse regions in the presence of dense regions. To address this problem, this paper presents a new concept called density decreased chain on the mutual k-NN graph. It starts with the local density center whose density is the highest in the data points connected to this center. Based on the density decreased chain, the concept of the core point is redefined. The density of the core point is close to that of the local density center on the same density decreased chain as the core point. According to its definition, the core point in the data with arbitrary densities can be well identified because the local density centers exist in both sparse and dense regions. Further, intra-cluster density decreased chain is defined to mine subclusters in the core points. After forming the subclusters, the remaining data point is hierarchically assigned to one of these subclusters by the density decreased chains containing this remaining data point. The experiments illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Machine learning-based predictive modeling is to develop machine learning-based or data-driven models to predict failures before they occur and estimate the remaining useful life or time to failure (TTF) accurately. Accurate TTF estimation plays a vital role in predictive maintenance or PHM (Prognostic and Health Management). Despite the availability of large amounts of data and a variety of powerful data analysis methods, predictive models developed for PHM still fail to provide accurate and precise TTF estimations. This paper addresses this problem by integrating machine learning algorithms such as classification, regression and clustering. A classification system is used to determine the likelihood of component failures such that rough indications of TTF are provided. Clustering and SVM-based local regression are then introduced to refine the time to failure estimations provided by the classification system. The paper illustrates the applicability of the proposed approach through a real world aerospace application with details on data pre-processing requirements. The results demonstrate that the proposed method can reduce uncertainty in estimating time to failure, which in turn helps augment the usefulness of predictive maintenance. [ABSTRACT FROM AUTHOR]

In the context of computer experiments, metamodels are largely used to represent the output of computer codes. Among these models, Gaussian process regression (kriging) is very efficient see e.g Snelson (Flexible and efficient Gaussian process models for machine learning. ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)–University of London, University College London, London, 2008). In high dimension that is with a large number of input variables, but with few observations, the estimation of the parameters with a classical anisotropic kriging can be completely inaccurate. Because there are equal numbers of ranges and input variables the optimization space becomes too large compared to available information. One way to overcome this drawback is to use an isotropic kernel that only depends on one parameter. However this model is too restrictive. The aim of this paper is twofold. Our first objective is to propose a smooth kernel with as few parameters as warranted. We introduce a kernel which is a tensor product of few isotropic kernels built on well-chosen subgroup of variables. The main difficulty is to find the number and the composition of the groups. Our second objective is to propose algorithmic strategies to overcome this difficulty. Four forward strategies are proposed. They all start with the simplest isotropic kernel and stop when the best model according to BIC criterion is found. They all show very good accuracy results on simulation test cases. But one of them is more efficient. Tested on a real data set, our kernel shows very good prediction results. [ABSTRACT FROM AUTHOR]

The global k-means algorithm is an incremental approach to clustering that dynamically adds one cluster center at a time through a deterministic global search procedure from suitable initial positions, and employs k-means to minimize the sum of the intra-cluster variances. However the global k-means algorithm sometimes results singleton clusters and the initial positions sometimes are bad, after a bad initialization, poor local optimal can be easily obtained by k-means algorithm. In this paper, we modified the global k-means algorithm to eliminate the singleton clusters at first, and then we apply MinMax k-means clustering error method to global k-means algorithm to overcome the effect of bad initialization, proposed the global Minmax k-means algorithm. The proposed clustering method is tested on some popular data sets and compared to the k-means algorithm, the global k-means algorithm and the MinMax k-means algorithm. The experiment results show our proposed algorithm outperforms other algorithms mentioned in the paper. [ABSTRACT FROM AUTHOR]

Co-clustering is known to be a very powerful and efficient approach in unsupervised learning because of its ability to partition data based on both the observations and the variables of a given dataset. However, in high-dimensional context co-clustering methods may fail to provide a meaningful result due to the presence of noisy and/or irrelevant features. In this paper, we tackle this issue by proposing a novel co-clustering model which assumes the existence of a noise cluster, that contains all irrelevant features. A variational expectation-maximization-based algorithm is derived for this task, where the automatic variable selection as well as the joint clustering of objects and variables are achieved via a Bayesian framework. Experimental results on synthetic datasets show the efficiency of our model in the context of high-dimensional noisy data. Finally, we highlight the interest of the approach on two real datasets which goal is to study genetic diversity across the world. [ABSTRACT FROM AUTHOR]

Image segmentation of heterogeneous comparable objects lying beneath the earth's surface is a fundamental but challenging research area in remote sensing. Learning approaches are used in remote sensing image segmentation to improve segmentation accuracy at the expense of time and a large amount of data, but their performance need to be finely classified due to information diversity constraints. In this work, we proposed an novel feature based fuzzy C-means-extreme learning machine (FBFCM-ELM) algorithm for remote sensing image segmentation in which the classification based on entropy, intensity, and edge features is performed in such a way that it updates the intensity value to preserve the most local characteristics in the image while still being able to clearly distinguish the image's boundaries by assigning the pixel values of each cluster to the peak value of the cluster's sub-histogram. Using FBFCM, features are extracted and used as reliable samples for ELM training. Undetermined segmented pixels are obtained using the trained ELM classifier. Experiments performed over number of images that confirmed the proposed method yields a better segmented RGB image, as evidenced by observable details, edges, and improved appearance that resembles the ground truth image and outperforms state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Feature Selection (FS) is choosing a subcategory of features purposed to construct a machine learning model. Among the copious existing FS algorithms, Binary Particle Swarm Optimization Algorithm (BPSO) is prevalent with applications in several domains. However, BPSO suffers from premature convergence that affects exploration, resulting in dilapidation. In this current work, we boost the exploration of BPSO, incorporating the intelligence of crows to hide their food sources from other crows and predators and maintain diversity by implementing a clustering strategy. The clustering technique guarantees that the starting population is evenly distributed over the feature space while including more promising features. Additionally, suppose a crow realizes another crow or a predator is tracking it. In that case, the crow moves randomly to evict the stalker, leading to a better exploration of unexplored regions within the search space. We named the proposed method Hybrid Particle Swarm Optimization and Crow Search Algorithm with clustering initialization strategy (HPSOCSA-CIS). To evaluate the performance of HPSOCSA-CIS, 15 standard UCI datasets are utilized, and the outcomes are compared with recently proposed hybrid and standard optimization algorithms. From observation, HPSOCSA-CIS outperforms the comparing approaches for feature selection challenges on representative datasets that fall in the three-category based on dimensions. The HPSOCSA-CIS improves performance in terms of mean classification accuracy by 8.87%, 17.5%, and 21.90% on Low, medium, and high dimensional datasets, respectively. [ABSTRACT FROM AUTHOR]

Clustering, a traditional machine learning method, plays a significant role in data analysis. Most clustering algorithms depend on a predetermined exact number of clusters, whereas, in practice, clusters are usually unpredictable. Although the Elbow method is one of the most commonly used methods to discriminate the optimal cluster number, the discriminant of the number of clusters depends on the manual identification of the elbow points on the visualization curve. Thus, experienced analysts cannot clearly identify the elbow point from the plotted curve when the plotted curve is fairly smooth. To solve this problem, a new elbow point discriminant method is proposed to yield a statistical metric that estimates an optimal cluster number when clustering on a dataset. First, the average degree of distortion obtained by the Elbow method is normalized to the range of 0 to 10. Second, the normalized results are used to calculate the cosine of intersection angles between elbow points. Third, this calculated cosine of intersection angles and the arccosine theorem are used to compute the intersection angles between elbow points. Finally, the index of the above-computed minimal intersection angles between elbow points is used as the estimated potential optimal cluster number. The experimental results based on simulated datasets and a well-known public dataset (Iris Dataset) demonstrated that the estimated optimal cluster number obtained by our newly proposed method is better than the widely used Silhouette method. [ABSTRACT FROM AUTHOR]

Contraction Clustering (RASTER) is a single-pass algorithm for density-based clustering of 2D data. It can process arbitrary amounts of data in linear time and in constant memory, quickly identifying approximate clusters. It also exhibits good scalability in the presence of multiple CPU cores. RASTER exhibits very competitive performance compared to standard clustering algorithms, but at the cost of decreased precision. Yet, RASTER is limited to batch processing and unable to identify clusters that only exist temporarily. In contrast, S-RASTER is an adaptation of RASTER to the stream processing paradigm that is able to identify clusters in evolving data streams. This algorithm retains the main benefits of its parent algorithm, i.e. single-pass linear time cost and constant memory requirements for each discrete time step within a sliding window. The sliding window is efficiently pruned, and clustering is still performed in linear time. Like RASTER, S-RASTER trades off an often negligible amount of precision for speed. Our evaluation shows that competing algorithms are at least 50% slower. Furthermore, S-RASTER shows good qualitative results, based on standard metrics. It is very well suited to real-world scenarios where clustering does not happen continually but only periodically. [ABSTRACT FROM AUTHOR]

We consider the problem of clustering a set of points so as to minimize the maximum intra-cluster dissimilarity, which is strongly NP-hard. Exact algorithms for this problem can handle datasets containing up to a few thousand observations, largely insufficient for the nowadays needs. The most popular heuristic for this problem, the complete-linkage hierarchical algorithm, provides feasible solutions that are usually far from optimal. We introduce a sampling-based exact algorithm aimed at solving large-sized datasets. The algorithm alternates between the solution of an exact procedure on a small sample of points, and a heuristic procedure to prove the optimality of the current solution. Our computational experience shows that our algorithm is capable of solving to optimality problems containing more than 500,000 observations within moderate time limits, this is two orders of magnitude larger than the limits of previous exact methods. [ABSTRACT FROM AUTHOR]