Search

The k-means algorithm is a prevalent clustering method due to its simplicity, effectiveness, and speed. However, its main disadvantage is its high sensitivity to the initial positions of the cluster centers. The global k-means is a deterministic algorithm proposed to tackle the random initialization problem of k-means but its well-known that requires high computational cost. It partitions the data to K clusters by solving all k-means sub-problems incrementally for all k = 1 , ... , K . For each k cluster problem, the method executes the k-means algorithm N times, where N is the number of datapoints. In this paper, we propose the globalk-means++ clustering algorithm, which is an effective way of acquiring quality clustering solutions akin to those of global k-means with a reduced computational load. This is achieved by exploiting the center selection probability that is effectively used in the k-means++ algorithm. The proposed method has been tested and compared in various benchmark datasets yielding very satisfactory results in terms of clustering quality and execution speed. [ABSTRACT FROM AUTHOR]

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]

Learning Management Systems (LMS) is now an emergent technology where massive data are collected and requires handling. This data comes from different sources with multiple features which represents another complex paradigm. However, as part of business intelligence and decision support, this data needs to be classified and analyzed for the management, teachers, as well as students to make the appropriate decisions. Thus, one of the effective data analysis methods is clustering. However, LMS data encompasses multi-features, which are not sufficient to make appropriate decisions. Therefore, single feature clustering algorithms would not help LMS decision-makers. Consequently, multifeatured/multiobjective clustering algorithms could be one of the proposed solutions. Thus, looking at different multiobjective clustering algorithms as compared to the LMS nature of data, those algorithms do not satisfy the clustering purpose. In addition, the LMS data could be huge, complex, and sequential algorithms would not help as well. Thus, this paper is a step forward towards clustering LMS data for better decision making. The paper proposes a new clustering framework based upon distributed systems and a new multiobjective algorithm for the purpose of LMS clustering. The algorithm has been examined experimentally in order to answer some of the questions that help taking decision based upon LMS collected data. [ABSTRACT FROM AUTHOR]

Fitness landscape analysis is a tool that can help us gain insight into a problem, determine how hard it is to solve a problem using a given algorithm, choose an algorithm for solving a given problem, or choose good algorithm parameters for solving the problem. In this paper, fitness landscape analysis of hyperheuristics is used for clustering instances of three scheduling problems. After that, good parameters for tree-based genetic programming that can solve a given scheduling problem are calculated automatically for every cluster. Additionally, we introduce tree editing operators which help in the calculation of fitness landscape features in tree based genetic programming. A heuristic is proposed based on introduced operators, and it calculates the distance between any two trees. The results show that the proposed approach can obtain parameters that offer better performance compared to manual parameter selection. [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]

The variety of pricing models offered by cloud service providers and the availability of a wide diversity of computing resources has increased the popularity of this paradigm for scientific applications. Such a scalable platform can be an ideal option for the execution of loosely coupled parallel applications, such as scientific workflows. Scientific workflows are regarded as one of the most important elements in different scientific fields in which a complex application may be divided into several dependent tasks. Given that the cost of leasing multicore VMs on the cloud will rise with an increase in the number of processing cores, an efficient scheduling algorithm focusing on utilizing multicore resources can significantly reduce execution costs. As an extension of its authors' previous research, the current paper proposes a heuristic scheduling algorithm, the Cluster Dividing Algorithm that concentrates on expanding the utilization of multicore resources to reduce execution costs while also meeting the user-defined deadline. To increase resource utilization, the proposed scheduling employs different techniques, such as task clustering, directed graph leveling, and task duplicating. The experimental results reveal that the presented algorithm leads to lower execution costs while complying with the deadline. [ABSTRACT FROM AUTHOR]

QSAR models capable of predicting biological, toxicity, and pharmacokinetic properties were widely used to search lead bioactive molecules in chemical databases. The dataset's preparation to build these models has a strong influence on the quality of the generated models, and sampling requires that the original dataset be divided into training (for model training) and test (for statistical evaluation) sets. This sampling can be done randomly or rationally, but the rational division is superior. In this paper, we present MASSA, a Python tool that can be used to automatically sample datasets by exploring the biological, physicochemical, and structural spaces of molecules using PCA, HCA, and K-modes. The proposed algorithm is very useful when the variables used for QSAR are not available or to construct multiple QSAR models with the same training and test sets, producing models with lower variability and better values for validation metrics. These results were obtained even when the descriptors used in the QSAR/QSPR were different from those used in the separation of training and test sets, indicating that this tool can be used to build models for more than one QSAR/QSPR technique. Finally, this tool also generates useful graphical representations that can provide insights into the data. [ABSTRACT FROM AUTHOR]

One of the crucial research areas in the analysis of complex social networks is the identification of communities. Since community detection is an NP-complete problem, numerous meta-heuristic approaches have been used for this problem, mostly taking "modularity" as the objective function. However, modularity-based optimization methods suffer from resolution limit. In this paper, a novel community detection algorithm is proposed that aims to optimize a newly introduced fitness function "balanced modularity." The proposed method, called grey wolf balanced modularity (GWBM), uses fast label propagation algorithm to form the initial population, relatively novel grey wolf algorithm as the main optimizer, and a problem-specific variant of simulated annealing algorithm for local search. The experiments on synthetic and known real-world networks, including Karate, American Football, and Facebook, have shown that GWBM is accurate and comparable with the state-of-the-art community detection methods. [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]

Multi-view clustering has gained importance in recent times due to the large-scale generation of data, often from multiple sources. Multi-view clustering refers to clustering a set of objects which are expressed by multiple set of features, known as views, such as movies being expressed by the list of actors or by a textual summary of its plot. Co-clustering, on the other hand, refers to the simultaneous grouping of data samples and features under the assumption that samples exhibit a pattern only under a subset of features. This paper combines multi-view clustering with co-clustering and proposes a new Weighted Multi-View Co-Clustering (WMVCC) algorithm. The motivation behind the approach is to use the diversity of features provided by multiple sources of information while exploiting the power of co-clustering. The proposed method expands the clustering objective function to a unified co-clustering objective function across all the multiple views. The algorithm follows the k-means strategy and iteratively optimizes the clustering by updating cluster labels, features, and view weights. A local search is also employed to optimize the clustering result using weighted multi-step paths in a graph. Experiments are conducted on several benchmark datasets. The results show that the proposed approach converges quickly, and the clustering performance significantly outperforms other recent and state-of-the-art algorithms on sparse datasets. [ABSTRACT FROM AUTHOR]

The data preprocessing stage is crucial in clustering. Features may describe entities using different scales. To rectify this, one usually applies feature normalisation aiming at rescaling features so that none of them overpowers the others in the objective function of the selected clustering algorithm. In this paper, we argue that the rescaling procedure should not treat all features identically. Instead, it should favour the features that are more meaningful for clustering. With this in mind, we introduce a feature rescaling method that takes into account the within-cluster degree of relevance of each feature. Our comprehensive simulation study, carried out on real and synthetic data, with and without noise features, clearly demonstrates that clustering methods that use the proposed data normalization strategy clearly outperform those that use traditional data normalization. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of the stock closing price forecasting for the stock market. Based on existing two-stage fusion models in the literature, two new prediction models based on clustering have been proposed, where k-means clustering method is adopted to cluster several common technical indicators. In addition, ensemble learning has also been applied to improve the prediction accuracy. Finally, a hybrid prediction model, which combines both the k-means clustering and ensemble learning, has been proposed. The experimental results on a number of Chinese stocks demonstrate that the hybrid prediction model obtains the best predicting accuracy of the stock price. The k-means clustering on the stock technical indicators can further enhance the prediction accuracy of the ensemble learning. [ABSTRACT FROM AUTHOR]

Community detection in complex networks is a difficult problem. Up to now, there is no very effective method to solve it. Recently, many community detection algorithms based on edge removal have been proposed. However, these edge removal methods often delete many key connections within communities and weaken (or destroy) the community structure of the network. This will make the network communities more difficult to be identified and reduce the accuracy and stability of the algorithm. This paper proposed a boundary connection deletion based community detection algorithm. Different from other algorithms, our algorithm focuses on identifying and removing the boundary connections between network modules. This can enhance the network community structure and get high quality network modules. With high performance, our algorithm can detect the optimal and hierarchical community structure in weighted networks simultaneously. In order to verify the effectiveness of our algorithm, the stability and robustness of our algorithm were firstly analyzed. Then a series of experiments had been done on the real-world and synthetic networks. The real-world networks include Zachary's karate club network, dolphin social network, American college foot-ball network, PolBooks network, Les Misérables character network, and the coauthorship network of scientists; The synthetic networks include GN benchmark and LFR benckmark. Two indices NMI and ModularityQ were used to compare our algorithm with the recently proposed algorithms, including meta-LPAm+, Srinivas and Rajendran's model, IDPM, CFCDs, EDCD, CNM, and CDASS. Experimental results show that our algorithm has better performance than these algorithms. [ABSTRACT FROM AUTHOR]

This paper presents an Effective Synchronization Clustering (ESynC) algorithm using a linear version of Vicsek model. The development of ESynC algorithm is inspired by Synchronization Clustering (SynC) algorithm and Vicsek model. After some analysis and experimental comparison, we observe that ESynC algorithm based on the linear version of Vicsek model can get better local synchronization effect than SynC algorithm based on an extensive Kuramoto model and a similar synchronization clustering algorithm based on the original version of Vicsek model. By some simulated experiments of some artificial data sets, eight UCI data sets, and three picture data sets, we observe that ESynC algorithm not only gets better local synchronization effect but also needs less iterative times and time cost than SynC algorithm. We also introduce an Improved ESynC algorithm (IESynC algorithm) in time cost by combining multidimensional grid partitioning method and Red-Black tree structure. By some simulated experiments, we observe that IESynC algorithm can get some improvement of time cost than ESynC algorithm in some data sets. Extensive comparison experiments with some class clustering algorithms demonstrate that our two algorithms can often get acceptable clustering results in many cases. At last, it gives several solid and insightful future research suggestions. [ABSTRACT FROM AUTHOR]

Because of its unsupervised nature, clustering is one of the most challenging problems, considered as a NP-hard grouping problem. Recently, several evolutionary algorithms (EAs) for clustering problems have been presented because of their efficiency for solving the NP-hard problems with high degree of complexity. Most previous EA-based algorithms, however, have dealt with the clustering problems given the number of clusters ( K) in advance. Although some researchers have suggested the EA-based algorithms for unknown K clustering, they still have some drawbacks to search efficiently due to their huge search space. This paper proposes the two-leveled symbiotic evolutionary clustering algorithm (TSECA), which is a variant of coevolutionary algorithm for unknown K clustering problems. The clustering problems considered in this paper can be divided into two sub-problems: finding the number of clusters and grouping the data into these clusters. The two-leveled framework of TSECA and genetic elements suitable for each sub-problem are proposed. In addition, a neighborhood-based evolutionary strategy is employed to maintain the population diversity. The performance of the proposed algorithm is compared with some popular evolutionary algorithms using the real-life and simulated synthetic data sets. Experimental results show that TSECA produces more compact clusters as well as the accurate number of clusters. [ABSTRACT FROM AUTHOR]

Spectral clustering is a hot topic and many spectral clustering algorithms have been proposed. These algorithms usually solve the discrete cluster indicator matrix by relaxing the original problems, obtaining the continuous solution and finally obtaining a discrete solution that is close to the continuous solution. However, such methods often result in a non-optimal solution to the original problem since the different steps solve different problems. In this paper, we propose a novel spectral clustering method, named as Enhanced Balanced Min Cut (EBMC). In the new method, a new normalized cut model is proposed, in which a set of balance parameters are learned to capture the differences among different clusters. An iterative method with proved convergence is used to effectively solve the new model without eigendecomposition. Theoretical analysis reveals the connection between EBMC and the classical normalized cut. Extensive experimental results show the effectiveness and efficiency of our approach in comparison with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Minimum spanning tree (MST)-based clustering is one of the most important clustering techniques in the field of data mining. Although traditional MST-based clustering algorithm has been researched for decades, it still has some limitations for data sets with different density distribution. After analyzing the advantages and disadvantages of the traditional MST-based clustering algorithm, this paper presents two new methods to improve the traditional clustering algorithm. There are two steps of our first method: compute a scaled-MST with scaled distance to find the longest edges between different density clusters and clustering based on the MST. To improve the performance, our second scaled-MST-clustering works by merging the MST construction and inconsistent edges' detection into one step. To verify the effectiveness and practicability of the proposed method, we apply our algorithm on image segmentation and integration. The encouraging performance demonstrates the superiority of the proposed method on both small data sets and high dimensional data sets. [ABSTRACT FROM AUTHOR]

Ensemble learning can achieve stronger generalization ability by training multiple weak classifier models and fusing the prediction results of these weak classifiers. However, with the increase in the number of weak classifier models, the complexity and training time of the model are also increasing. This paper introduces a heuristic parallel selective ensemble algorithm based on clustering and improved simulated annealing. First, the method uses selective clustering to remove similar weak classifiers, so as to reduce the number of weak models, and select the weak classifiers with large differences as candidate sets. Then, the optimal classifier sequence set is selected based on the improved simulated annealing heuristic selective ensemble algorithm, which improves the classification performance of the model. Moreover, the parallel integration strategy is adopted to improve the efficiency of selecting optimal subset of classifiers, thus effectively reducing the training time of the model. Experimental results show that the proposed algorithm exhibits better performance compared with traditional methods. [ABSTRACT FROM AUTHOR]

The second generation of World Wide Web, supplied with the platforms of Social Networks, proves to be a revealing source of knowledge. It has led to the emergence of online communities of interest. In fact, the interactions of users through web usages allow the exchange of information and the dissemination of innovation; thereby the formation of cohesive groups of individuals sharing goals, interests, semantics and services. Reflection on the evolution of those groups and their detection is a fundamental topic of interest in the field of Social Network Analysis. This problem is very challenging and hard to solve despite the huge interdisciplinary research over the past years. In this paper, we will attempt an indepth comparative review of the proposed approaches for clustering Social Network actors into communities of interests and propose a new classification of these approaches. [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]

Cloud is a multi-tenant paradigm providing resources as a service. With its easily available computing infrastructure, researchers are adopting cloud for experimental purposes. However, using the platform efficiently for parallel and distributed simulations comes with new challenges. One such challenge is that the simulations comprise logical processes executing on distributed nodes, traditionally, organized in a sequential pattern. This placement strategy leads to delays as frequently communicating processes might get placed farther from one another. In this paper, we proposed a framework to facilitate implementation and evaluation of process placement algorithms inside a three-tier cloud data center. Furthermore, we used the framework to test different process placement strategies based on classical clustering techniques, as well as, our proposed efficient locality-aware placement algorithm. Our evaluation results show a performance gain of 14.5 % for the algorithm in comparison with sequential process placement used in practice. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm to evaluate the tradeoff between conflicting objectives in process plan selection and cell formation is developed. Consideration of the minimisation of intercell material movement in cellular manufacturing is necessary but not in itself sufficient to produce a system for which the total work content is minimised. Solving the process plan selection and the cell formation problem for all possible alternative process plans is a time-consuming task, and therefore not economically justifiable. The algorithm is illustrated through the use of a sample problem that shows how it is possible to create a cell using the algorithm presented in this paper. [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]

The dimensional and geometric inspection of non-rigid mechanical parts still presents a real challenge to the automotive and aerospace industry. Much research has been devoted to automating the inspection of these parts in order to eliminate the cost of specialized fixtures that cause productivity problems for manufacturers. A registration step between the part'31s nominal CAD model and its corresponding scan is required for an automatic inspection. The coherent point drift (CPD) is one of the existing algorithms for registration and is widely used in imaging applications. It has been recently adapted with regard to the mechanical field for the fixtureless dimensional inspection problems of deformable bodies, notably the IDB-ACPD algorithm. In this paper, an improvement of the optimization phase by reformulating the objective function of the algorithm is put forward. A correction matrix associated with the importance of each measurement point, and therefore with the local rigidity of the part during the registration operation, was introduced and incorporated. In addition, the measurement points representing the same rigidity have been clustered based on mechanical metrics using a fuzzy c-mean algorithm. The effectiveness of the proposed approach is demonstrated on different case studies from the transport industry and the results provide an improved registration of non-rigid parts leading to better dimensional and geometric errors detection. [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]

We revisit in this paper the problem of inferring a diffusion network from information cascades. In our study, we make no assumptions on the underlying diffusion model, in this way obtaining a generic method with broader practical applicability. Our approach exploits the pairwise adoption-time intervals from cascades. Starting from the observation that different kinds of information spread differently, these time intervals are interpreted as samples drawn from unknown (conditional) distributions. In order to statistically distinguish them, we propose a novel method using Reproducing Kernel Hilbert Space embeddings. Experiments on both synthetic and real-world data from Twitter and Flixster show that our method significantly outperforms the state-of-the-art methods. We argue that our algorithm can be implemented by parallel batch processing, in this way meeting the needs in terms of efficiency and scalability of real-world applications. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new kernel-based fuzzy clustering algorithm which tries to find the best clustering results using optimal parameters of each kernel in each cluster. It is known that data with nonlinear relationships can be separated using one of the kernel-based fuzzy clustering methods. Two common fuzzy clustering approaches are: clustering with a single kernel and clustering with multiple kernels. While clustering with a single kernel doesn’t work well with “multiple-density” clusters, multiple kernel-based fuzzy clustering tries to find an optimal linear weighted combination of kernels with initial fixed (not necessarily the best) parameters. Our algorithm is an extension of the single kernel-based fuzzy c-means and the multiple kernel-based fuzzy clustering algorithms. In this algorithm, there is no need to give “good” parameters of each kernel and no need to give an initial “good” number of kernels. Every cluster will be characterized by a Gaussian kernel with optimal parameters. In order to show its effective clustering performance, we have compared it to other similar clustering algorithms using different databases and different clustering validity measures. [ABSTRACT FROM AUTHOR]

Random swap algorithm aims at solving clustering by a sequence of prototype swaps, and by fine-tuning their exact location by k-means. This randomized search strategy is simple to implement and efficient. It reaches good quality clustering relatively fast, and if iterated longer, it finds the correct clustering with high probability. In this paper, we analyze the expected number of iterations needed to find the correct clustering. Using this result, we derive the expected time complexity of the random swap algorithm. The main results are that the expected time complexity has (1) linear dependency on the number of data vectors, (2) quadratic dependency on the number of clusters, and (3) inverse dependency on the size of neighborhood. Experiments also show that the algorithm is clearly more efficient than k-means and almost never get stuck in inferior local minimum. [ABSTRACT FROM AUTHOR]

Recently, kernel-based clustering in feature space has shown to perform better than conventional clustering methods in unsupervised classification. In this paper, a partitioning clustering method in kernel-induce feature space for symbolic interval-valued data is introduced. The distance between an item and its prototype in feature space is expanded using a two-component mixture kernel to handle intervals. Moreover, tools for the partition and cluster interpretation of interval-valued data in feature space are also presented. To show the effectiveness of the proposed method, experiments with real and synthetic interval data sets were performed and a study comparing the proposed method with different clustering algorithms of the literature is also presented. The clustering quality furnished by the methods is measured by an external cluster validity index (corrected Rand index). These experiments showed the usefulness of the kernel K-means method for interval-valued data and the merit of the partition and cluster interpretation tools. [ABSTRACT FROM AUTHOR]

Several protocols have been proposed to deal with the group key management problem in mobile ad hoc networks (MANETs). Most of these protocols organize the network into clusters to reduce the cost of key refresh or rekeying. Rekeying constitutes a challenging issue in group key management because it must be launched whenever the constitution of the group is altered following a leave or a join operation. However, cluster maintenance may also generate significative communication overhead. So, the clustering algorithm is an important factor in the performance of any key management solution. A clustering algorithm that ensures stable clusters in spite of mobility is very appreciable in mobile ad hoc networks. In fact, all the overhead due to the traffic generated by cluster adjustments and the related rekeying procedures will be saved. As far as we know, no existing clustering algorithm takes into account self-stabilization while relying on the mobility resilience of graph alliances. In this paper, we propose a fully distributed and self-stabilizing clustering algorithm for key management in MANETs where each cluster is an alliance. [ABSTRACT FROM AUTHOR]

In this paper, we propose a word sense learning algorithm which is capable of unsupervised feature selection and cluster number identification. Feature selection for word sense learning is built on an entropy-based filter and formalized as a constraint optimization problem, the output of which is a set of important features. Cluster number identification is built on a Gaussian mixture model with a MDL-based criterion, and the optimal model order is inferred by minimizing the criterion. To evaluate closeness between the learned sense clusters with the ground-truth classes, we introduce a kind of weighted F-measure to model the effort needed to reconstruct the classes from the clusters. Experiments show that the algorithm can retrieve important features, roughly estimate the class numbers automatically and outperforms other algorithms in terms of the weighted F-measure. In addition, we also try to apply the algorithm to a specific task of adding new words into a Chinese thesaurus. [ABSTRACT FROM AUTHOR]

Energy efficiency is one of the main issues that will drive the design of fog-supported wireless sensor networks (WSNs). Indeed, the behavior of such networks becomes very unstable in node's heterogeneity and/or node's failure. In WSNs, clusters are dynamically built up by neighbor nodes, to save energy and prolong the network lifetime. One of the nodes plays the role of Cluster Head (CH) that is responsible for transferring data among the neighboring sensors. Due to pervasive use of WSNs, finding an energy-efficient policy to opt CHs in the WSNs has become increasingly important. Due to this motivations, in this paper, a modified Stable Election Protocol (SEP), named Prolong-SEP (P-SEP) is presented to prolong the stable period of Fog-supported sensor networks by maintaining balanced energy consumption. P-SEP enables uniform nodes distribution, new CH selecting policy, and prolong the time interval of the system, especially before the failure of the first node. P-SEP considers two-level nodes' heterogeneities: advanced and normal nodes. In P-SEP, the advanced and normal nodes have the opportunity to become CHs. The performance of the proposed approach is evaluated by varying the various parameters of the network in comparison with other state-of-the-art cluster-based routing protocols. The simulation results point out that, by varying the initial energy and node heterogeneity parameters, the network lifetime of P-SEP improved by 31, 29, 20 and 40 % in comparison with SEP, Low-Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection (LEACH-DCHS), Modified SEP (M-SEP) and an efficient modified SEP (EM-SEP), respectively. [ABSTRACT FROM AUTHOR]

Big data storage and processing are among the most important challenges now. Among data mining algorithms, DBSCAN is a common clustering method. One of the most important drawbacks of this algorithm is its low execution speed. This study aims to accelerate the DBSCAN execution speed so that the algorithm can respond to big datasets in an acceptable period of time. To overcome the problem, an initial grouping was applied to the data in this article through the K-means++ algorithm. DBSCAN was then employed to perform clustering in each group separately. As a result, the computational burden of DBSCAN execution reduced and the clustering execution speed increased significantly. Finally, border clusters were merged if necessary. According to the results of executing the proposed algorithm, it managed to greatly reduce the DBSCAN execution time (98% in the best-case scenario) with no significant changes in the qualitative evaluation criteria for clustering. [ABSTRACT FROM AUTHOR]

In evolutionary multi-objective optimization, maintaining a well balance of convergence and diversity is particularly important for the performance of evolutionary algorithms. Considering the convergence and diversity at the same time, a many-objective optimization algorithm combining angle-based selection strategy and clustering strategy is proposed. In the former strategy, the whole population is divided into several partitions to ensure the diversity of the population, and superior individuals are selected to ensure the convergence of the population. The latter strategy, the individual vector angle is used to reflect the similarity and the individuals are divided into some clusters, which helps to describe the population distribution. The performance of this algorithm is compared with five state-of-the-art evolutionary many-objective optimization algorithms on a variety of benchmark test problems with 5, 10 and 15 objectives. The results suggest that the algorithm can slightly better competitive performance. [ABSTRACT FROM AUTHOR]

Breast cancer is one of the leading causes of mortality in the world and it occurs in high frequency among women that carries away many lives. To detect cancer, extraction or segmentation of lesions/tumors is required. Segmentation process is very crucial if the mammogram images are blurred or low contrast. This paper suggests a novel clustering approach for segmenting lesions/tumors in the mammogram images using Atanassov's intuitionistic fuzzy set theory. The algorithm initially converts an image to an intuitionistic fuzzy image using a novel intuitionistic fuzzy generator. From the intuitionistic fuzzy image, two membership intervals are computed. Then, using Zadeh's min t-conorm, a new membership function is computed. Using the new membership function, an interval type 2 fuzzy image is constructed. Two types of distance functions are used in clustering—intuitionistic fuzzy divergence and a fuzzy exponential type distance function. Further, in each iteration, membership matrix is updated using a hesitation degree and a clustered image is obtained. Tumors/lesions are then segmented from the clustered image. The proposed method is compared with existing methods both quantitatively and qualitatively and it is observed that the proposed method performs better than the existing methods. [ABSTRACT FROM AUTHOR]

Collaborative filtering is one of widely used recommendation approaches to make recommendation services for users. The core of this approach is to improve capability for finding accurate and reliable neighbors of active users. However, collected data is extremely sparse in the user-item rating matrix, meanwhile many existing similarity measure methods using in collaborative filtering are not much effective, which result in the poor performance. In this paper, a novel effective collaborative filtering algorithm based on user preference clustering is proposed to reduce the impact of the data sparsity. First, user groups are introduced to distinguish users with different preferences. Then, considering the preference of the active user, we obtain the nearest neighbor set from corresponding user group/user groups. Besides, a new similarity measure method is proposed to preferably calculate the similarity between users, which considers user preference in the local and global perspectives, respectively. Finally, experimental results on two benchmark data sets show that the proposed algorithm is effective to improve the performance of recommender systems. [ABSTRACT FROM AUTHOR]

A recommender system suggests items to users by predicting what might be interesting for them. The prediction task has been highlighted in the literature as the most important one computed by a recommender system. Its role becomes even more central when a system works with groups, since the predictions might be built for each user or for the whole group. This paper presents a deep evaluation of three approaches, used for the prediction of the ratings in a group recommendation scenario in which groups are detected by clustering the users. Experimental results confirm that the approach to predict the ratings strongly influences the performance of a system and show that building predictions for each user, with respect to building predictions for a group, leads to great improvements in the accuracy of the recommendations. [ABSTRACT FROM AUTHOR]

Due to enormous growth in both volume and variety of data, clustering a very large database is a time-consuming process. To speed up clustering process, sampling has been recognized as a very utilitarian approach to reduce the dataset size in which a collection of data points are taken as a sample and then a clustering algorithm is applied to partitioning the data points in that sample into clusters. In this approach, the data points, that are not sampled, do not get their cluster labels. The process of allocating unlabeled data points into proper clusters has been well explored purely in numerical or categorical domain only, but not the both. In this paper, we propose a hybrid similarity coefficient to find the resemblance between an unlabeled data point and a cluster, based on the importance of categorical attribute values and the mean values of numerical attributes. Furthermore, we propose a Hybrid Data Labeling Algorithm (HDLA), based on this similarity coefficient to designate an appropriate cluster label to each unlabeled data point. We analyze its time complexity and perform various experiments using synthetic and real world datasets to demonstrate the efficacy of HDLA. [ABSTRACT FROM AUTHOR]

In the case of real-world data streams, the underlying data distribution will not be static; it is subject to variation over time, which is known as the primary reason for concept drift. Concept drift poses severe problems to the accuracy of a model in online learning scenarios. The recurring concept is a particular case of concept drift where the concepts already seen in the past reappear as the stream evolves. This problem is not yet studied in the context of stream clustering. This paper proposes a novel algorithm for identifying the recurring concepts in data stream clustering. During concept recurrence, the most matching model is retrieved from the repository and reused. The algorithm has minimum memory requirements and works online with the stream. Some of the concepts and definitions, already familiar in concept recurrence studies of stream classification have been redefined for clustering. The experiments conducted on real and synthetic data streams reveal that the proposed algorithm has the potential to identify recurring concepts. [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]

Color image segmentation is an important technique in image processing, pattern recognition and computer vision. Many segmentation algorithms have been proposed. However, it is still a complex task especially when there are noises in the images, which have not been studied in much detail. Neutrosophic set (NS) studies the origin, nature, and scope of neutralities. In this paper, we apply NS in the color image and define some new concepts. A directional α-mean operation is proposed to reduce the set indeterminacy. The fuzzy c-means clustering method is improved by integrating with NS and employed for the color image segmentation. The computation of membership and the clustering termination criterion are redefined accordingly. Moreover, a validity criterion is employed to determine the optimal clustering number. Numerical experiments serve to illustrate the effectiveness and reliability of the proposed approach. Experimental results demonstrate that our approach can segment color images automatically and effectively, produce good results as favorably compared to some existing algorithms. The optimal clustering number is determined automatically and no prior knowledge is required. Especially, it can segment both images with the simple and distinct objects and the images with complex and noisy objects, which is the most difficult task for color image segmentation. [ABSTRACT FROM AUTHOR]

Recent development in Graphics Processing Units (GPUs) has enabled inexpensive high performance computing for general-purpose applications. Compute Unified Device Architecture (CUDA) programming model provides the programmers adequate C language like APIs to better exploit the parallel power of the GPU. Data mining is widely used and has significant applications in various domains. However, current data mining toolkits cannot meet the requirement of applications with large-scale databases in terms of speed. In this paper, we propose three techniques to speedup fundamental problems in data mining algorithms on the CUDA platform: s calable thread scheduling scheme for irregular pattern, parallel distributed top-k scheme, and parallel high dimension reduction scheme. They play a key role in our CUDA-based implementation of three representative data mining algorithms, CU-Apriori, CU-KNN, and CU-K-means. These parallel implementations outperform the other state-of-the-art implementations significantly on a HP xw8600 workstation with a Tesla C1060 GPU and a Core-quad Intel Xeon CPU. Our results have shown that GPU + CUDA parallel architecture is feasible and promising for data mining applications. [ABSTRACT FROM AUTHOR]

Many clustering schemes are defined by optimizing an objective function defined on the partitions of the underlying set of a finite metric space. In this paper, we construct a framework for studying what happens when we instead impose various structural conditions on the clustering schemes, under the general heading of functoriality. Functoriality refers to the idea that one should be able to compare the results of clustering algorithms as one varies the dataset, for example by adding points or by applying functions to it. We show that, within this framework, one can prove a theorem analogous to one of Kleinberg (Becker et al. (eds.), NIPS, pp. 446-453, MIT Press, Cambridge, ), in which, for example, one obtains an existence and uniqueness theorem instead of a nonexistence result. We obtain a full classification of all clustering schemes satisfying a condition we refer to as excisiveness. The classification can be changed by varying the notion of maps of finite metric spaces. The conditions occur naturally when one considers clustering as the statistical version of the geometric notion of connected components. By varying the degree of functoriality that one requires from the schemes, it is possible to construct richer families of clustering schemes that exhibit sensitivity to density. [ABSTRACT FROM AUTHOR]

When encountering too many records, each of which has several attributes, clustering of the data is an important issue on mining and classification. Recently many advances on clustering algorithms have been made such that clustering of data is done precisely and quickly. Clustering algorithms use optimization algorithms which simultaneously provide the number of clusters as default. These algorithms cluster the data so that those which belong to a cluster have maximum similarity and those in different clusters have minimum similarity. The k-means algorithm is a traditional algorithm for clustering problems. One of the most important difficulties of clustering algorithms is determining the number of clusters before starting the algorithm. In other words, by having knowledge on distribution of data, the number of clusters should be estimated and then imported to the problem as an input. In this paper, the data collected on quality control of mechanized tunneling are analyzed. They consist of measurements of 16 characteristics for 200 initial installed rings of segments on the tunnel walls inspected by the quality control team. A dynamic validity index is used and combined to the k-means algorithm for clustering the data so that the optimal number of clusters can be determined simultaneously. The application of the algorithm shows that the total installed rings can be clustered into four clusters. These four classes of quality can best describe the total installed rings on the tunnel in comparison of other number of classes (or clusters). Furthermore, this approach helps the quality team to determine the most effective or best performance executive team whom their installed rings have best class and minimum variations. [ABSTRACT FROM AUTHOR]

This paper presents an alternative to cluster mixed databases. The main idea is to propose a general method to cluster mixed data sets, which is not very complex and still can reach similar levels of performance of some good algorithms. The proposed approach is based on codifying the categorical attributes and use a numerical clustering algorithm on the resulting database. The codification proposed is based on polar or spherical coordinates, it is easy to understand and to apply, the increment in the length of the input matrix is not excessively large, and the codification error can be determined for each case. The proposed codification combined with the well known k-means algorithm showed a very good performance in different benchmarks and has been compared with both, other codifications and other mixed clustering algorithms, showing a better or comparable performance in all cases. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of how to reliably compute neighborhoods on affinity graphs. The k-nearest neighbors ( kNN) is one of the most fundamental and simple methods widely used in many tasks, such as classification and graph construction. Previous research focused on how to efficiently compute kNN on vectorial data. However, most real-world data have no vectorial representations, and only have affinity graphs which may contain unreliable affinities. Since the kNN of an object o is a set of k objects with the highest affinities to o, it is easily disturbed by errors in pairwise affinities between o and other objects, and also it cannot well preserve the structure underlying the data. To reliably analyze the neighborhood on affinity graphs, we define the k-dense neighborhood ( kDN), which considers all pairwise affinities within the neighborhood, i.e., not only the affinities between o and its neighbors but also between the neighbors. For an object o, its kDN is a set kDN( o) of k objects which maximizes the sum of all pairwise affinities of objects in the set { o}∪ kDN( o). We analyze the properties of kDN, and propose an efficient algorithm to compute it. Both theoretic analysis and experimental results on shape retrieval, semi-supervised learning, point set matching and data clustering show that kDN significantly outperforms kNN on affinity graphs, especially when many pairwise affinities are unreliable. [ABSTRACT FROM AUTHOR]

The segmentation of acoustic emission data collected during mechanical tests is one of the current challenges to allow further analysis of damaged materials. Among the existing clustering methods, one of the most widely used is the k-means algorithm. In this paper, a genetic algorithm-based approach is presented. Data sets derived from experimental AE data are processed to highlight the contributions of the new algorithm. Its superiority over the k-means algorithm is demonstrated for several data sets, and especially when a cluster is significantly smaller than the others, or very far and thus behaves as a group of outliers or if the clusters have very different sizes. This method allows the better clustering of AE data even on complex data sets. [ABSTRACT FROM AUTHOR]

Bridging rules take the antecedent and action from different conceptual clusters. They are distinguished from association rules (frequent itemsets) because (1) they can be generated by the infrequent itemsets that are pruned in association rule mining, and (2) they are measured by their importance including the distance between two conceptual clusters, whereas frequent itemsets are measured only by their support. In this paper, we first design two algorithms for mining bridging rules between clusters, and then propose two non-linear metrics to measure their interestingness. We evaluate these algorithms experimentally and demonstrate that our approach is promising. [ABSTRACT FROM AUTHOR]

Maximal margin based frameworks have emerged as a powerful tool for supervised learning. The extension of these ideas to the unsupervised case, however, is problematic since the underlying optimization entails a discrete component. In this paper, we first study the computational complexity of maximal hard margin clustering and show that the hard margin clustering problem can be precisely solved in O( n) time where n is the number of the data points and d is the dimensionality of the input data. However, since it is well known that many datasets commonly 'express' themselves primarily in far fewer dimensions, our interest is in evaluating if a careful use of dimensionality reduction can lead to practical and effective algorithms. We build upon these observations and propose a new algorithm that gradually increases the number of features used in the separation model in each iteration, and analyze the convergence properties of this scheme. We report on promising numerical experiments based on a 'truncated' version of this approach. Our experiments indicate that for a variety of datasets, good solutions equivalent to those from other existing techniques can be obtained in significantly less time. [ABSTRACT FROM AUTHOR]

While spectral clustering can produce high-quality clusterings on small data sets, computational cost makes it infeasible for large data sets. Affinity Propagation (AP) has a limitation that it is hard to determine the value of parameter 'preference' which can lead to an optimal clustering solution. These problems limit the scope of application of the two methods. In this paper, we develop a novel fast two-stage spectral clustering framework with local and global consistency. Under this framework, we propose a Fast density- Weighted low-rank Approximation Spectral Clustering (FWASC) algorithm to address the above issues. The proposed algorithm is a high-quality graph partitioning method, and simultaneously considers both the local and global structure information contained in the data sets. Specifically, we first present a new Fast Two- Stage AP (FTSAP) algorithm to coarsen the input sparse graph and produce a small number of final representative exemplars, which is a simple and efficient sampling scheme. Then we present a density-weighted low-rank approximation spectral clustering algorithm to operate those representative exemplars on the global underlying structure of data manifold. Experimental results show that our algorithm outperforms the state-of-the-art spectral clustering and original AP algorithms in terms of speed, memory usage, and quality. [ABSTRACT FROM AUTHOR]