Search

• The existing methods may lead to a contradictory in the transitivity. • A novel neighborhood geometric similarity was firstly defined. • Four new kinds of neighborhood similarities were proposed. • A new VPNRS model is constructed, and a novel decision tree algorithm is proposed. The decision tree algorithm has been widely used in data mining and machine learning due to its high accuracy, low computational cost and high interpretability. However, when dealing with the continuous data, the classical decision tree algorithm needs to replace continuous attributes with discretized attributes by the strategy of discretization. Discretization may cause a loss of information structure, which will affect the performance of classification. To tackle this problem, many researchers have proposed different decision tree methods based on variable precision neighborhood rough sets. However, these methods do not consider the geometric structure of neighborhood systems, which may lead to a contradiction in the transitivity of the equivalence relation. In this paper, we first define a novel neighborhood geometric similarity in a neighborhood system from the perspective of geometry. Second, by combining the neighborhood geometric similarity and the neighborhood algebraic similarity, we propose four new kinds of neighborhood similarities, which can solve the contradictory transitivity of the equivalence relation. Third, a variable precision neighborhood rough set model is constructed using the new similarities, and a novel decision tree algorithm is proposed based on this model, where the degree of attribute dependence is used as the partition measure. Experimental results on 14 selected datasets from the UCI Machine Learning Repository show that our algorithm is effective. The average accuracy of our algorithm is over 90%, which is 10% higher than the classical decision tree algorithms, and the number of leaf nodes increases slightly. [ABSTRACT FROM AUTHOR]

Clustering, as an essential technique in unsupervised learning, plays a pivotal role in the fields of data mining and machine learning. However, the classic K -means clustering algorithm has intrinsic drawbacks such as sensitivity to initial cluster centers, susceptibility to a local optimal solution, and challenges in handling data uncertainty. To address these problems, this paper proposes an artificial hummingbird algorithm (AHA)-based three-way K -means clustering algorithm, called AHA-3WKM. First, AHA is introduced to address the problems of sensitivity to initial cluster centers and local optima. Second, a fitness function of AHA is specifically constructed to find the best initial clustering centers so that the hummingbirds can search for high-quality food sources, i.e., the global optimum cluster centers. Third, a three-way clustering approach is utilized to capture information about data uncertainty. In this way, the results of clustering are divided into three distinct regions based on the relationship between objects and clusters. The experimental results demonstrate that AHA-3WKM has good performance, and enhances the stability and the accuracy of clustering results. • AHA is introduced to address the problems of the sensitivity to initial cluster centers and the proneness to local optima. Hummingbirds are treated as data points, which dynamically update their strategies and effectively find the optimal cluster centers during multiple iterations. • A fitness function is designed based on the clustering principle of "birds of a feather flock together", with the aim of simplifying calculations, which enhances the specificity and practicality of K-means algorithm. • An AHA-based three-way K-means clustering algorithm (i.e., AHA-3WKM) is proposed. The clustering process is initialized with cluster centers optimized by AHA, and the results are represented in three regions, which can capture the uncertainty within the datasets. [ABSTRACT FROM AUTHOR]

K-nearest neighbors search (K-NNS) is a fundamental problem in many areas of machine learning and data mining. In an attempt to solve NNS problems by locality-sensitive hashing (LSH)-based algorithms and avoid the F1-trap, in this paper, we theoretically prove the necessity of maintaining close edges of each dimension, the independence of the partition location and the precision of retrieval. Based on the theories, a new method is proposed for constructing the hash function family. Then, a volume-balancing locality-sensitive hashing (VBLSH) algorithm is implemented. In this algorithm, the problem of constructing the hash function family is transformed into an optimization problem under a fixed number of hypercubes. By solving the optimization problem, different hyperplane intervals are set for each dimension to ensure that the hash functions can evenly segment the data space, where each segmented hypercube has a close volume and close side lengths. Finally, the analysis of the algorithm shows that the VBLSH algorithm has a high index coding efficiency and hash code calculation efficiency. The experimental results show that the VBLSH algorithm can simultaneously take into account the efficiency, precision and recall rate, and avoid the F1-trap; it shows excellent effectiveness on 4 datasets. [ABSTRACT FROM AUTHOR]

Often, machine learning applications have to cope with dynamic environments where data are collected in the form of continuous data streams with potentially infinite length and transient behavior. Compared to traditional (batch) data mining, stream processing algorithms have additional requirements regarding computational resources and adaptability to data evolution. They must process instances incrementally because the data's continuous flow prohibits storing data for multiple passes. Ensemble learning achieved remarkable predictive performance in this scenario. Implemented as a set of (several) individual classifiers, ensembles are naturally amendable for task parallelism. However, the incremental learning and dynamic data structures used to capture the concept drift increase the cache misses and hinder the benefit of parallelism. This paper proposes a mini-batching strategy that can improve memory access locality and performance of several ensemble algorithms for stream mining in multi-core environments. With the aid of a formal framework, we demonstrate that mini-batching can significantly decrease the reuse distance (and the number of cache misses). Experiments on six different state-of-the-art ensemble algorithms applying four benchmark datasets with varied characteristics show speedups of up to 5X on 8-core processors. These benefits come at the expense of a small reduction in predictive performance. [ABSTRACT FROM AUTHOR]

• Micro-MetaStream selects the best learning algorithm for each example of data streams. • This method relates data characteristics and the performance of regression models over time. • It combines characteristics from training data and raw features from the predictive attributes of each test example. • Predictive performance was improved when compared with two other meta-learning methods. Data stream mining needs to deal with scenarios where data distribution can change over time. As a result, different learning algorithms can be more suitable in different time periods. This paper proposes micro-MetaStream, a meta-learning based method to recommend the most suitable learning algorithm for each new example arriving in a data stream. It is an evolution of MetaStream, which recommends learning algorithms for batches of examples. By using a unitary granularity, micro-MetaStream is able to respond more efficiently to changes in data distribution than its predecessor. The meta-data combines meta-features, characteristics describing recent data, with base-level features, the original variables of the new example. In experiments on real-world regression data streams, micro-metaStream outperformed MetaStream and a baseline method at the meta-level and frequently improved the predictive performance at the base-level. [ABSTRACT FROM AUTHOR]

Agglomerative clustering is a mainstream clustering method that can produce an informative hierarchical structure of clusters. Existing similarities in agglomerative clustering are typically based on the pairwise distance. Although this type of similarity captures the local structure of data well, it is sensitive to noise and outliers because it considers only the distance between data points. In this paper, we propose a new similarity called RCPD by combining the reconstruction coefficient, which is robust to noise and outliers, with the pairwise distance for agglomerative clustering. Our new similarity takes advantage of both the distance between data points and the linear representation among data points. Thus, RCPD not only captures the local structure of data well but is also robust to noise and outliers. The experimental results on 11 real-world benchmark datasets show that our new clustering method consistently outperforms many state-of-the-art clustering approaches. [ABSTRACT FROM AUTHOR]

As an important preprocessing step for data mining, attribute reduction has become a hot research topic in rough set theory. In practice, many real data may vary dynamically with time, therefore, reduct will change dynamically under the variation of objects and attributes in decision systems. The classical attribute reduction methods need to recompute from scratch, which are ineffective to deal with dynamic decision systems. How to implement updating reducts by utilizing previous results is vital for improving the efficiency of attribute reduction approaches. In the paper, we firstly introduce incremental mechanisms of computing reduct when objects and attributes of the decision system change dynamically. Then, incremental methods are developed to update reduct when attributes and objects increase simultaneously. Finally, a series of experiments are conducted to validate the proposed incremental attribute reduction methods. Experimental results show that they are effective to update reduct with change of attributes and objects in the decision systems. [ABSTRACT FROM AUTHOR]

Active learning, one of large and important branches in machine learning and data mining, aims to build an accurate learning model with a relatively small number of labeled points which are chosen actively by the constructed learning model. Active learning algorithms can play an important role when the cost of obtaining labels of data points is expensive. However, the active learning algorithms for the relevance vector machine regression, one of the famous kernel methods for the regression due to its sparseness, Bayesian characteristics, and kernel properties, have not been established yet, whilst those for other kernel methods are extensively developed. In this paper, we propose a transductive relevance vector machine to construct the active learning algorithm for relevance vector machine based a sparse Bayesian kernel regression model. The proposed method obtains its basis vectors from the unlabeled data set as well as the labeled one. Then, we also suggest three querying strategies which uses only the relevance vectors automatically selected by the developed model for active selection for data points to be labeled. Applied to several artificial and real data sets, the proposed method show significantly more accurate results than the benchmark, the random selection, while maintaining the sparse characteristic of the traditional relevance vector machines. [ABSTRACT FROM AUTHOR]

Graphics Processing Units (GPUs) are effective tools for improving the efficiency of many computationally demanding algorithms. GPUs have been particularly effective at speeding up the evaluation stage of evolutionary machine learning systems. The speedups obtained in these tasks, depend on many factors: dataset characteristics, the parallel strategy of the GPU code and the fit of the GPU code within the rest of the learning system. A solid understanding of all these factors is required to choose and adjust the most suitable GPU strategy in different scenarios. In this paper we present a large-scale performance evaluation of two GPU strategies for speeding up the evaluation of evolutionary machine learning systems. We use highly-tuneable synthetic problems to exhaustively explore the space of problem characteristics and determine the type of problems where each strategy performs best. The lessons learnt from this extensive evaluation are further confirmed by running experiments on a broad range of real-world datasets. Through this thorough evaluation we obtain a solid understanding of the capabilities and limitations of the evaluated GPU strategies for boosting the efficiency of evolutionary machine learning systems. [ABSTRACT FROM AUTHOR]

Attribute reduction is an important preprocessing step in pattern recognition, machine learning and data mining. As an effective method for attribute reduction, rough set theory offers a useful and formal methodology. It retains the discernibility power of the original datasets; thus, attribute reduction has been extensively studied in rough set theory. However, the inefficiency of the existing attribute reduction algorithms limits the application of rough sets. In this paper, we first analyse the limitations of existing attribute reduction algorithms. Then, a novel measure of attribute quality, called the relative discernibility degree, is proposed based on the discernibility. Theoretical analysis shows that this measure can find relative dispensable attributes and remain unchanged after removing the relative dispensable attributes and redundant objects in the process of selecting attributes. This property can be used to reduce the search space and accelerate the heuristic process of attribute reduction. Consequently, a new attribute reduction algorithm is proposed from the viewpoint of discernibility. Further- more, the relationships among the reduction definitions of the algebra view, information view and discernibility view are derived. Some non-equivalent relationships among these views of rough set theory in inconsistent decision tables are discovered. A set of numerical experiments was conducted on UCI datasets. Experimental results show that the proposed algorithm is effective and efficient and is applicable to the case of large-scale datasets. [ABSTRACT FROM AUTHOR]

Data clustering aims to segment a database into groups of objects based on the similarity among these objects. Due to its unsupervised nature, the search for a good-quality solution can become a complex process. There is currently a wide range of clustering algorithms, and selecting the best one for a given problem can be a slow and costly process. In 1976, Rice formulated the Algorithm Selection Problem (ASP), which postulates that the algorithm performance can be predicted based on the structural characteristics of the problem. Meta-learning brings the concept of learning about learning; that is, the meta-knowledge obtained from the algorithm learning process allows the improvement of the algorithm performance. Meta-learning has a major intersection with data mining in classification problems, in which it is normally used to recommend algorithms. The present paper proposes new ways to obtain meta-knowledge for clustering tasks. Specifically, two contributions are explored here: (1) a new approach to characterize clustering problems based on the similarity among objects; and (2) new methods to combine internal indices for ranking algorithms based on their performance on the problems. Experiments were conducted to evaluate the recommendation quality. The results show that the new meta-knowledge provides high-quality algorithm selection for clustering tasks. [ABSTRACT FROM AUTHOR]

Abstract: Clustering is a popular non-directed learning data mining technique for partitioning a dataset into a set of clusters (i.e. a segmentation). Although there are many clustering algorithms, none is superior on all datasets, and so it is never clear which algorithm and which parameter settings are the most appropriate for a given dataset. This suggests that an appropriate approach to clustering should involve the application of multiple clustering algorithms with different parameter settings and a non-taxing approach for comparing the various segmentations that would be generated by these algorithms. In this paper we are concerned with the situation where a domain expert has to evaluate several segmentations in order to determine the most appropriate segmentation (set of clusters) based on his/her specified objective(s). We illustrate how a data mining process model could be applied to address this problem. [Copyright &y& Elsevier]