Intelligent Data Analysis: An International Journal

Uncertainty measurement is one of the important issues in rough sets. Although some uncertainty measures to evaluate the uncertainty of ordered information systems have been investigated, the definitions of existing uncertainty measures in ordered information systems are mainly based on information theory approach, and few studies is based on pure rough set approach. In this paper, the concepts of six different upper and lower approximations and corresponding uncertainty measurement including accuracy, roughness and approximation accuracy are provided. Some properties and relationships among six different uncertainty measures are investigated. Theoretical analysis indicates that these measures can be used to measure the uncertainty in ordered information systems, and some illustrative examples are employed to demonstrate our conclusions.

This paper explores the idea of closed world specialisation (CWS). While traditional CWS is performed as a postprocessing step, we propose two different approaches to incorporating it into the induction process of a bottom-up inductive logic programming system. The motivation comes from the fact that using CWS as a postprocessing step is incapable of solving problems in which the negated part of the hypothesis is crucial. We apply the proposed approaches to the ProGolem bottom-up ILP system. We give examples of problems, where classical CWS fails to find a complete and consistent solution, whereas the proposed approaches succeed. Tests on real-world datasets show that the proposed approaches perform at least as well as regular CWS, while being better in terms of predictive accuracy in some cases. We also point out some weaknesses of different CWS approaches.

This paper presents a new decision tree learning algorithm, fuzzy min-max decision tree (FMMDT) based on fuzzy min-max neural networks. In contrast with traditional decision trees in which a single attribute is selected as the splitting test, the internal nodes of the proposed algorithm contain a fuzzy min-max neural network. In the proposed learning algorithm, the flexibility inherent in the fuzzy logic and the computational efficiency of the min-max neural networks are combined in the decision tree learning framework. FMMDT splits the feature space non-linearly based on multiple attributes which provides not only conceptually more insightful splits but also decision trees with smaller size and depth. The decision trees resulted from the FMMDT learning algorithm have a non-traditional architecture, which enables determining the class label of the instances as early as possible. Moreover, FMMDT creates decision trees which are interpretable by the domain expert. It is shown experimentally that the decision trees resulted from the proposed FMMDT learning algorithm achieve the highest accuracy and the lowest size and depth in comparison with C4.5, BFTree, SimpleCart and NBTree on the most commonly used UCI data sets. Moreover, the experiments reveal that FMMDT creates decision trees with stable structure.

Rank K Binary Matrix Factorization (BMF) approximates a binary matrix by the product of two binary matrices of lower rank, K. Several researchers have addressed this problem, focusing on either approximations of rank 1 or higher, using either the L_1 or L_2-norms for measuring the quality of the approximation. The rank 1 problem (for which the L_1 and L_2-norms are equivalent) has been shown to be related to the Integer Linear Programming (ILP) problem. We first show here that the alternating strategy with the L_2-norm, at the core of several methods used to solve BMF, can be reformulated as an Unconstrained Binary Quadratic Programming (UBQP) problem. This reformulation allows us to use local search procedures designed for UBQP in order to improve the solutions of BMF. We then introduce a new local search dedicated to the BMF problem. We show in particular that this solution is in average faster than the previously proposed ones. We then assess its behavior on several collections and methods and show that it significantly improves methods targeting the L_2-norms on all the datasets considered; for the L_1-norm, the improvement is also significant for real, structured datasets and for the BMF problem without the binary reconstruction constraint.

Link prediction is a fundamental problem in network data analysis, which has attracted increasing attention from many fields, with many new advances. In particular, many structure similarity-based algorithms that only use network topology information have been applied because of their simple framework. The prediction accuracy of these methods depends on the compatibility between the algorithm definition and the structural characteristics of the target network, so the stability of structure similarity-based algorithms is low. Thus, these algorithms may obtain good results with some networks but fail with others. Given the ambiguous relationships between these algorithms, we propose a Choquet fuzzy integral-based link prediction method, which integrates structure similarity-based algorithms via the Choquet fuzzy integral to improve the prediction accuracy and achieve more stable prediction performance. Empirical experiments using six real networks demonstrated that the proposed method outperformed the mainstream link prediction baseline methods.

With the emergence of networked data, graph classification has received considerable interest during the past years. Most approaches to graph classification focus on designing effective kernels to compute similarities for static graphs. However, they become computationally intractable in terms of time and space when a graph is presented in an incremental fashion with continuous updates, i.e., insertions of nodes and edges. In this paper, we examine the problem of classification in large-scale and incrementally changing graphs. We propose a framework combining an incremental support vector machine (SVM) with the Weisfeiler-Lehman (W-L) graph kernel. By retaining the support vectors from each learning step, the classification model is incrementally updated whenever new changes are made to the graph. We design an entropy-based subgraph extraction strategy, that selects informative neighbor nodes and discards those with less discriminative power, to facilitate the classification of nodes in a dynamic network. We validate the advantages of our learning techniques by conducting an empirical evaluation on several large-scale real-world graph datasets in comparison with other graph classification methods. The experimental results also validate the benefits of our subgraph extraction method when combined with the incremental learning techniques.

This study discusses and compares grid proximity measures that use representative data points in grid cells and the average distance between the data points in grid cells. Basic theorems for the grid distance measure are formulated and proved. The grid distance measure is applied to the grid-based clustering problem where the number of clusters is dynamically determined by using a threshold value and by maximizing intra-similarity in a cluster and inter-dissimilarity between the clusters.

In this study, the grid-based clustering problem is illustrated and formulated using a 0-1 integer programming approach. We perform numerical experiments on randomly generated problems and also for a clustering problem concerning microarray data of human fibroblasts in varying serum concentrations, with the latter data having been taken from a prior study. The theorems are applicable to the grid-based clustering of any data set.

With the increasing volume of data, the best approach for learning from this data is to exploit an online learning algorithm. Online ensemble methods take advantage of an ensemble of classifiers to predict labels of data. Prediction with expert advice is a well-studied problem in the online ensemble learning literature. The weighted majority and the randomized weighted majority (RWM) algorithms are two well-known solutions to this problem, aiming to converge to the best expert. Since among some expert, the best one does not necessarily have the minimum error in all regions of data space, defining specific regions and converging to the best expert in each of these regions will lead to a better result. In this paper, we aim to resolve this problem by proposing a novel online ensemble algorithm to the problem of prediction with expert advice. We propose a cascading version of RWM to achieve not only better experimental results but also a better error bound for sufficiently large datasets.

High-utility itemset mining (HUIM) has been recently studied to mine high-utility itemsets (HUIs) from the transactional database by considering more factors such as profit and quantity. Many approaches have been proposed for HUIM from a static database. Fewer studies have been developed to maintain the discovered HUIs in dynamic environment whether transaction insertion or transaction deletion. In the past, the FUP-HUI-DEL and PRE-HUI-DEL algorithms were respectively proposed to effectively maintain the discovered high transaction-weighted utilization itemsets(HTWUIs) and high-utility itemsets (HUIs) when the transactions are consequentially deleted from the original database. The original database is still, however, required to be rescanned when small transaction-weighted utilization itemsets in the original database are necessary to be maintained. In this paper, an efficient algorithm namely HUI-list-DEL is presented to discover HUIs by maintaining the built utility-list structure for transaction deletion in dynamic databases. Based on the designed algorithm, the HUIs can be directly produced without candidate generation or the numerous database scans. Two pruning strategies are also designed to speed up the maintenance approach of HUIs. Substantial experiments show that the proposed maintenance approach for transaction deletion significantly outperforms the previous approaches in terms of execution time, memory consumption and scalability.

High utility itemset mining has recently emerged to address the limitations of frequent itemset mining. It entails relevance measures to reflect both statistical significance and user expectations. Whether breadth-first or depth-first search algorithms are employed, most methods generate new candidates by 1-extension of existing itemsets (i.e., by adding only one item to verified itemsets to generate new potential candidates). As an alternative to 1-extension, we introduce an expansion method based on binary partition. We then define the transaction utility list and key support count and discuss a new pruning strategy. Based on the new itemset expansion method and pruning strategy, we propose an efficient high utility itemset mining algorithm called BPHUI-Mine (Binary Partition-based High Utility Itemsets Mine). Tests on publicly available datasets show that the proposed algorithm outperforms other state-of-the-art algorithms.

The use of graphical probabilistic models in the field of education has been considered for this research. First, classical learning algorithms, as PC or K2 are reviewed. But the problem with these general learning procedures comes from the presence of a high number of variables that measure different aspects of the same concept, as it can be the case of socio-economic indicators in a population. In this case, we have that all the variables have some degree of dependence among them, without a true causal structure. So, a new procedure is presented which makes a hierarchical clustering of the data while learning a joint probability distribution. It generalizes AutoClass EM clustering allowing more complex models. Hierarchical clustering is compared in the experiments with classical learning algorithms showing a similar performance when considering the estimation of a joint probability distribution for all the variables, but with a clear advantage: the simplicity and easiness of the interpretation of the model. The method is applied to the analysis of two datasets of the educational data: socio-economic, academic achievement and drop outs at the Engineering Faculty of Quevedo State Technical University, and student evaluation of teachers from Gazi University in Ankara (Turkey).

Feature selection is an important machine learning field which can provide a key role for the challenging problem of classifying high-dimensional data. This problem is finding effective features among the set of all features in such that the final feature set can improve accuracy and reduce complexity. Since feature selection is an NP-Hard problem, many heuristic algorithms have been studied so far to solve this problem.

In this paper, we propose a novel method based on hyper-heuristic approach to find an efficient proper feature subset which is named Hyper-Heuristic Feature Selection (HHFS). In the proposed method, Low level heuristics are categorized into two groups: the first group contains exploiters which cause to exploit the search space efficiently by improving the quality of the candidate solution at hand; the second one includes explorer heuristics which explore the solution space by dwelling on random perturbations. Since each region of the solution space can have its own characteristics, an appropriate low level heuristic should be selected and applied to the current solution. We propose Genetic Algorithm to select among the set of low level heuristic and balance between exploitation and exploration. It chooses the low level heuristic based on the existing functional history of low level heuristic. We aim to investigate the role of cooperation between low level heuristics within a hyper-heuristic framework to find the best feature subset. Since different low level heuristics have different strengths and weaknesses, we believe that cooperation can allow the strengths of one low level heuristic to compensate for the weaknesses of another. In this study, we also propose Adaptive Hyper-Heuristic Feature Selection (AHHFS) which is an extension of HHFS. Empirical study of the proposed method on several commonly used data sets from UCI repository indicates that it outperforms recent methods in the literature for feature selection.