Search

Minimax Algorithm, is a solution to reduce the burden on hardware in chess engine. However, a more in-depth method is needed to further increase the search algorithm. One of those solutions is called Alpha-Beta Pruning algorithm. The idea is to eliminate the unnecessary nodes in the search tree.

Data mining is a knowledge discovery process that analyzes data and generate useful pattern from it. Classification is the technique that uses pre-classified examples to classify the required results. Decision tree is used to model classification process. Using feature values of instances, Decision trees classify those instances. Each node in a decision tree represents a feature in an instance to be classified. In this research work ID3, C4.5 and C5.0 Compare with each other. Among all these classifiers C5.0 gives more accurate and efficient result. This research work used C5.0 as the base classifier so proposed system will classify the result set with high accuracy and low memory usage. The classification process generates fewer rules compare to other techniques so the proposed system has low memory usage. Error rate is low so accuracy in result set is high and pruned tree is generated so the system generates fast results as compare with other technique. In this research work proposed system use C5.0 classifier that Performs feature selection and reduced error pruning techniques which are described in this paper. Feature selection technique assumes that the data contains many redundant features. so remove that features which provides no useful information in any context. Select relevant features which are useful in model construction. Crossvalidation method gives more reliable estimate of predictive. Over fitting problem of the decision tree is solved by using reduced error pruning technique. With the proposed system achieve 1 to 3% of accuracy, reduced error rate and decision tree is construed within less time.

Ensemble learning is a method of combining learners to obtain more reliable and accurate predictions in supervised and unsupervised learning. However, the ensemble sizes are sometimes unnecessarily large which leads to additional memory usage, computational overhead and decreased effectiveness. To overcome such side effects, pruning algorithms have been developed; since this is a combinatorial problem, finding the exact subset of ensembles is computationally infeasible. Different types of heuristic algorithms have developed to obtain an approximate solution but they lack a theoretical guarantee. Error Correcting Output Code (ECOC) is one of the well-known ensemble techniques for multiclass classification which combines the outputs of binary base learners to predict the classes for multiclass data. In this paper, we propose a novel approach for pruning the ECOC matrix by utilizing accuracy and diversity information simultaneously. All existing pruning methods need the size of the ensemble as a parameter, so the performance of the pruning methods depends on the size of the ensemble. Our unparametrized pruning method is novel as being independent of the size of ensemble. Experimental results show that our pruning method is mostly better than other existing approaches.

As is well known, the Greedy Ensemble Pruning (GEP) algorithm, also called the Directed Hill Climbing Ensemble Pruning (DHCEP) algorithm, possesses relatively good performance and high speed. However, because the algorithm only explores a relatively small subspace within the whole solution space, it often produces suboptimal solutions of the ensemble pruning problem. Aiming to address this drawback, in this work, we propose a novel Randomized GEP (RandomGEP) algorithm, also called the Randomized DHCEP (RandomDHCEP) algorithm, that effectively enlarges the search space of the classical DHCEP while maintaining the same level of time complexity with the help of a randomization technique. The randomization of the classical DHCEP algorithm achieves a good tradeoff between the effectiveness and efficiency of ensemble pruning. Besides, the RandomDHCEP algorithm naturally inherits the two intrinsic advantages that a randomized algorithm usually possesses. First, in most cases, its running time or space requirements are smaller than well-behaved deterministic ensemble pruning algorithms. Second, it is easy to comprehend and implement. Experimental results on three benchmark classification datasets verify the practicality and effectiveness of the RandomGEP algorithm.

Ensemble pruning is substantial for the successful application of an ensemble system. A novel method for Ensemble Pruning via BackTracking algorithm (EnPBT) was proposed by us in our previous work. Backtracking algorithm can systematically search for the solutions of a problem in a depth-first and jumping manner, suitable for solving all those large-scale combinatorial problems. The validity of EnPBT algorithm has been verified in our previous work. However, the relatively slow pruning speed might be a drawback of EnPBT. Aiming at this problem, an efficient and novel ensemble pruning algorithm is proposed in this paper, i.e. One-Path and Two-Trips (OPTT) ensemble pruning algorithm. It is very fast in pruning speed, while its classification performance has no significant difference with EnPBT, as demonstrated in the experimental results of this work. In short, OPTT achieves a proper trade-off between pruning effectiveness and efficiency.

The minimax algorithm, also called the negamax algorithm, remains today the most widely used search technique for two-player perfect-information games. However, minimaxing has been shown to be susceptible to game tree pathology, a paradoxical situation in which the accuracy of the search can decrease as the height of the tree increases. Althöfer’s alternative minimax algorithm has been proven to be invulnerable to pathology. However, it has not been clear whether alpha-beta pruning, a crucial component of practical game programs, could be applied in the context of Alhöfer’s algorithm. In this brief paper, we show how alpha-beta pruning can be adapted to Althöfer’s algorithm.

The efficiency of three forward-pruning techniques, i.e., futility pruning, null-move pruning, and LMR, is analyzed in shogi, a Japanese chess variant. It is shown that the techniques with the α – β pruning reduce the effective branching factor of shogi endgames to 2.8 without sacrificing much accuracy of the search results. Because the average number of the raw branching factor in shogi is around 80, the pruning techniques reduce the search space more effectively than in chess.

Highlights? Bottom-up pruning is extended to multiple tree context. ? Suitable pruning criteria are proposed. ? Method is tested on a number of UCI datasets. ? Method produces single trees with good performance/compactness. ? Applied to a churn prediction problem, interpretable trees were produced. A generalisation of bottom-up pruning is proposed as a model level combination method for a decision tree ensemble. Bottom up pruning on a single tree involves choosing between a subtree rooted at a node, and a leaf, dependant on a pruning criterion. A natural extension to an ensemble of trees is to allow subtrees from other ensemble trees to be grafted onto a node in addition to the operations of pruning to a leaf and leaving the existing subtree intact. Suitable pruning criteria are proposed and tested for this multi-tree pruning context. Gains in both performance and in particular compactness over individually pruned trees are observed in tests performed on a number of datasets from the UCI database. The method is further illustrated on a churn prediction problem in the telecommunications domain.

Classification is an important data mining task that discovers hidden knowledge from the labeled datasets. Most approaches to pruning assume that all dataset are equally uniform and equally important, so they apply equal pruning to all the datasets. However, in real-world classification problems, all the datasets are not equal and considering equal pruning rate during pruning tends to generate a decision tree with large size and high misclassification rate. We approach the problem by first investigating the properties of each dataset and then deriving data-specific pruning value using expert knowledge which is used to design pruning techniques to prune decision trees close to perfection. An efficient pruning algorithm dubbed EKBP is proposed and is very general as we are free to use any learning algorithm as the base classifier. We have implemented our proposed solution and experimentally verified its effectiveness with forty real world benchmark dataset from UCI machine learning repository. In all these experiments, the proposed approach shows it can dramatically reduce the tree size while enhancing or retaining the level of accuracy.

Association rule mining is one of the most exploited areas in data mining, which includes applications from business to data classification and summarization. Thus, several association rule-based c...

Ensemble pruning deals with the reduction of base classifiers prior to combination in order to improve generalization and prediction efficiency. Existing ensemble pruning algorithms require much pruning time. This paper presents a fast pruning approach: pattern mining based ensemble pruning (PMEP). In this algorithm, the prediction results of all base classifiers are organized as a transaction database, and FP-Tree structure is used to compact the prediction results. Then a greedy pattern mining method is explored to find the ensemble of size k. After obtaining the ensembles of all possible sizes, the one with the best accuracy is outputted. Compared with Bagging, GASEN, and Forward Selection, experimental results show that PMEP achieves the best prediction accuracy and keeps the size of the final ensemble small, more importantly, its pruning time is much less than other ensemble pruning algorithms.

When learning is based on noisy data, the induced rule sets have a tendency to overfit the training data, and this degrades the performance of the resulting classifier. Consequently, the ability to tolerate noise is a necessity for robust, practical learning methods. Pruning is a common way of handling noisy data. This paper presents a new pruning technique built on the sound foundation of the minimum description length principle. The proposed pruning technique has the advantage that it does not require the set of examples employed for pruning to be distinct from the set used to build the rule set. The new technique is designed to improve the performance of the RULe Extraction System (RULES) family of inductive learning algorithms, but can be used for pruning rule sets created by other learning algorithms. It was tested in RULES-6, the latest algorithm in the family, and showed significant performance improvements.

Decision trees are well-known and established models for classification and regression. In this paper, we focus on the estimation and the minimization of the misclassification rate of decision tree classifiers. We apply Lidstone's Law of Succession for the estimation of the class probabilities and error rates. In our work, we take into account not only the expected values of the error rate, which has been the norm in existing research, but also the corresponding reliability (measured by standard deviations) of the error rate. Based on this estimation, we propose an efficient pruning algorithm, called k-norm pruning, that has a clear theoretical interpretation, is easily implemented, and does not require a validation set. Our experiments show that our proposed pruning algorithm produces accurate trees quickly, and compares very favorably with two other well-known pruning algorithms, CCP of CART and EBP of C4.5.

Cost-sensitive decision trees have a great success in building models for classification tasks in data mining and machine learning. Decision tree pruning technique is regarded as an important component of the optimization of decision tree. However, many previous cost-sensitive decision trees researches focus on minimizing the misclassification rate and removing nodes when the cost of the pruned tree is less than the original one. In this paper, we propose an effective method for building cost-sensitive decision tree and a probabilistic pruning mechanism for the decision tree. There are two major contributions of this paper. Firstly, the cost-sensitive decision tree is built to make predictions to minimize the total cost of test costs and different costs associated with different types of misclassification. Compared with existing models, leaves are labeled by minimizing the total cost instead of the majority class. Secondly, we design a probabilistic pruning mechanism where the pruning probability is related to the change of costs around pruning. The pruning results yield worse performance on the training set, but better performance on the testing set. Therefore, the probabilistic pruning mechanism improves the performance of the cost-sensitive decision tree. Experimental results show the efficiency of the probabilistic pruning mechanism for cost-sensitive decision tree.

The cost-complexity pruning generates nested subtrees and selects the best one. However, its computational cost is large since it uses holdout sample or cross-validation. On the other hand, the pruning algorithms based on posterior calculations such as BIC (MDL) and MEP are faster, but they sometimes produce too big or small trees to yield poor generalization errors. In this paper, we propose an alternative pruning procedure which combines the ideas of the cost-complexity pruning and posterior calculation. The proposed algorithm uses only training samples, so that its computational cost is almost same as the other posterior-based algorithms, and at the same time yields similar accuracies as the cost-complexity pruning. Moreover it can be used for comparing non-nested trees, which is necessary for the BUMPing procedure. The empirical results show that the proposed algorithm performs similarly as the cost-complexity pruning in standard situations and works better for BUMPing.

A non-preference based pruning algorithm is proposed to rank the Pareto-optimal solutions according to the cost and reliability trade-off for solving multi-objective redundancy allocation problem. The proposed method demonstrates on multi-objective redundancy allocation problem with mixing of non-identical component types in each subsystem. The objectives of system design are to maximize system reliability and minimize system cost simultaneously while satisfying system requirement constraints. Non-dominated sorting genetic algorithm-II (NSGA-II) finds an approximation of Paretooptimal solutions. After obtaining the approximation of Pareto-optimal solutions by NSGA-II, K-means clustering is used to cluster the approximation of Pareto-optimal solutions into some trade-off regions. Thereafter, the Paretooptimal solutions are ranked based on the cost and reliability trade-off compare to the centroid solution of each cluster. The results show that the proposed method is able to identify the most-compromised solution.

Move pruning is a technique used in game tree search which incorporates heuristic knowledge to reduce the number of moves under consideration from a particular game state. This paper investigates Heuristic Move Pruning on the strategic card game Lords of War. We use heuristics to guide our pruning and experiment with different techniques of applying pruning and their relative effectiveness. We also present a technique of artificially rolling forward a game state in an attempt to more accurately determine which moves are appropriate to prune from the decision tree. We demonstrate that heuristic move pruning is effective in Lords of War, and also that artificially rolling forward the game state can increase the effectiveness of heuristic move pruning.

Trained radial basis function networks are well-suited for use in extracting rules and explanations because they contain a set of locally tuned units. However, for rule extraction to be useful, these networks must first be pruned to eliminate unnecessary weights. The pruning algorithm cannot search the network exhaustively because of the computational effort involved. It is shown that using multiple pruning methods with smart ordering of the pruning candidates, the number of weights in a radial basis function network can be reduced to a small fraction of the original number. The complexity of the pruning algorithm is quadratic (instead of exponential) in the number of network weights. Pruning performance is shown using a variety of benchmark problems from the University of California, Irvine machine learning database.

In the half century since minimax was first suggested as a strategy for adversary game search, various search algorithms have been developed. The standard approach has been to use improvements to the Alpha–Beta ( α – β ) algorithm. Some of the more powerful improvements examine continuations beyond the nominal search depth if they are of special interest, while others terminate the search early. The latter case is referred to as forward pruning. In this paper we discuss some important aspects of forward pruning, especially regarding risk-management, and propose ways of making risk-assessment. Finally, we introduce two new pruning methods based on some of the principles discussed here, and present experimental results from application of the methods in an established chess program.

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.

The article presents an algorithm that combines Minimax's alpha-beta pruning with IDA*'s depth-first iteration and forward pruning. We prove that the algorithm, which we call Two - agent IDA* (TIDA*), is correct and is guaranteed to terminate—provided its heuristic is consistent. Minimax search has been applied with other ‘forward’ pruning or selective search techniques, but none of these techniques is guaranteed to compute the correct minimax result. We also prove that TIDA*'s accuracy monotonically increases with search depth, thus avoiding certain pathologies. Empirical results with 3×3, 4×4 and 5×5 Tic-Tac-Tff grids show that TIDA* outperforms MAB, provided both algorithms use the same consistent heuristic. However, results on a more complex search space—the 3D version of Tic-Tac-Tff—show that MAB with a good inconsistent heuristic can outperform TIDA* with a consistent heuristic even though TIDA* searches 1 to 1·5 levels deeper. This result and other empirical results suggest that an algorithm that s...

Evolutionary multi-objective optimization algorithms have been developed to find a representative set of Pareto-optimal solutions in the past decades. However, researchers have pointed out that finding a representative set of Pareto-optimal solutions is not sufficient; the task of choosing a single preferred Pareto-optimal solution is also another important task which has received a widespread attention so far. In this paper, we propose an algorithm to help the decision maker (DM) choose the final preferred solution based on his/her preferred objectives. Our algorithm is called an adaptive angle based pruning algorithm with independent bias intensity tuning parameter (ADA-τ). The method begins by calculating the angle between a pair of solutions by using a simple arctangent function. The bias intensity parameter of each objective is introduced independently in order to approximate the portions of desirable solutions based on the DM’s preferred objectives. We consider several benchmark problems including two and three-objective problems. The experimental results have shown that our pruning algorithm provides a robust sub-set of Pareto-optimal solutions for the benchmark problems.

As a query processing optimization technique over inverted index, static index pruning can significantly reduce index size and query processing time. A fast static index pruning algorithm is presented, which is a term-centric method and adopts BM25 weighting as the pruning measure. The algorithm scans through documents set with one pass and directly builds pruned index, and therefore avoids the construction of original index. The correctness of the algorithm is proved and the theoretical analysis reveals that its IO performance takes precedence over other algorithms. The experiments based on TREC data set also show that the fast static index pruning algorithm requires less time to build pruned index, and the pruning effectiveness outperforms the baseline method.

In this paper, we recast static index pruning as a model induction problem under the framework of Kullback's principle of minimum cross-entropy. We show that static index pruning has an approximate analytical solution in the form of convex integer program. Further analysis on computation feasibility suggests that one of its surrogate model can be solved efficiently. This result has led to the rediscovery of \emph{uniform pruning}, a simple yet powerful pruning method proposed in 2001 and later easily ignored by many of us. To empirically verify this result, we conducted experiments under a new design in which prune ratio is strictly controlled. Our result on standard ad-hoc retrieval benchmarks has confirmed that uniform pruning is robust to high prune ratio and its performance is currently state of the art.

Empirical studies have shown that the performance of decision tree induction usually improves when the trees are pruned. Whether these results hold in general and to what extent pruning improves the accuracy of a concept have not been investigated theoretically. This paper provides a theoretical study of pruning. We focus on a particular type of pruning and determine a bound on the error due to pruning. This is combined with PAC (probably approximately correct) learning theory to determine a sample size sufficient to guarantee a probabilistic bound on the concept error. We also discuss additional pruning rules and give an analysis for the pruning error.

We compare the most important pruning methods which are common in different LVCSR decoding architectures and lead them back to a theoretical motivation. Based on this motivation, we propose a new pruning method which fades the word end pruning over a large part of the search network. We analyze the methods regarding their relationship between search-space and word error rate, and regarding their mutual dependence. We show that the different pruning methods are mutually dependent and difficult to combine, and that our new pruning method is the most effective method regarding both the search space and runtime efficiency.

Publisher Summary This chapter discusses learning approaches to prune the successor set(s). It studies the exclusion of forbidden states or move sequences and localizing the search using the notion of relevance. The chapter distinguishes between on-the-fly and offline learning. One of the most effective approaches to tackle large problem spaces is to prune (i.e., cutoff branches from) the search tree. There are multiple reasons for pruning. Some branches might not lead to a goal state, others lead to inferior solutions; some result in positions already reached on different paths, and others are redundant; though these might lead to a solution, there are still alternatives that also lead to a solution. All state space pruning techniques reduce the node-branching factor of the search tree such that fewer successor nodes have to be analyzed. Since a smaller part of the state space is generated, pruning saves both search time and space. However, there might be a trade-off between the two. Some techniques require rather complex data structures, such that the maintenance of pruning information may be involved. Static pruning techniques detect pruning knowledge prior to the main search routine. Other pruning rules may not be known to the search algorithm at its start and have to be inferred during the execution of the program. This leads to layered search algorithms. In the top-level search, the search algorithms search for problem solutions, and in frequently invoked lower-level searches, pruning knowledge is refined.

Many traditional pruning methods assume that all the datasets are equally probable and equally important. Thus, they apply equal pruning to all the datasets. However, in real-world classification problems, all the datasets are not equal. Consequently, considering equal pruning rate tends to generate inefficient and large size decision trees. Therefore, we propose a practical algorithm to deal with the data specific classification problem when there are datasets with different properties. In this paper, First, we computed the data specific pruning values for each dataset. Then, we used expert knowledge to find inexact pruning value. Finally, we integrated those values in a well established pruning technique to form Expert Knowledge based Pruning (EKBP). We empirically validated the analysis with publicly available 40 datasets from UCI on four existing techniques. Both the analytical and experimental results have shown that our proposed method achieves reduction of tree size and retains equal or better accuracy.

A fast OBS pruning algorithm based on pseudo-entropy of weights is proposed to resolve the problems of the number of hidden neurons is difficult to be determined in neural networks and low pruning speed in conventional OBS (Optimal Brain Surgeon) pruning algorithm. The algorithm makes the network constrain the distribution of weight automatically during the training process, obtain a simpler structure of network, and improve the speed of pruning. The result of experimental shows that the structure of network has been simplified; the generalization capability of network and the speed of pruning have been improved greatly by using the algorithm mentioned above.

The game playing is an import domain of heuristic search, and its procedure is represented by a special and/or tree. Alpha-beta pruning is always used for problem solving by searching the game-playing-tree. In this paper, the plan which child nodes are inserted into game-playing-tree from large value of estimation function to small one when the node of no receiving fixed ply depth is expand is proposed based on alpha-beta pruning. It improves effect of search

In this paper we develop a new post-pruning algorithm. This new pruning algorithm uses two or more post-pruning algorithms to prune a decision tree that has been built on training set by different orders, and the “best” tree is selected based either on separate test set accuracy or cross-validations from trees coming from result of the above step. The algorithm is theoretically based on occam's razor that is a simpler model is chosen if two models have the same performance on the training set. An experiment is implemented on three databases in UCI machine learning repository and the new algorithm is employed to compares with two well-known post-pruning algorithms. The results show that the hybrid pruning algorithm effectively reduces the complexity of decision trees without sacrificing accuracy.

Ensemble pruning deals with the reduction of base classifiers prior to combination in order to improve generalization and prediction efficiency. Existing ensemble pruning algorithms require much pruning time. This paper presents a fast pruning approach: PMEP (Pattern Mining based Ensemble Pruning). In this algorithm, the prediction results of all base classifiers are organized as a transaction database, and FP-Tree structure is used to compact the prediction results. Then a greedy pattern mining method is explored to find the ensemble of size k . After obtaining the ensembles of all possible sizes, the one with the best accuracy is outputted. Compared with Bagging, GASEN, and Forward Selection, experimental results show that PMEP achieves the best prediction accuracy and keeps the size of the final ensemble small, more importantly, its pruning time is much less than other ensemble pruning algorithms.

Genetic algorithm is one of the commonly used approaches on machine learning. In this paper, we put forward a genetic algorithm approach for pruning decision tree. Binary coding is adopted in which an individual in a population consists of a fixed number of weight that stand for a solution candidate. The evaluation function considers error rate of decision tree over the test set. Three common operators for genetic algorithm such as random mutation and single-point crossover is applied for the population. Finally the algorithm returns an individual with the highest fitness as a local optimal weight. Based on four databases from UCI, we compared our approach with several other traditional decision tree pruning techniques including cost-complexity pruning, Pessimistic Error Pruning and Reduced error pruning. The results show that our approach has an better or equal effect with other pruning method.

Korf, R.E., Multi-player alpha-beta pruning (Research Note), Artificial Intelligence 48 (1991) 99-111. We consider the generalization of minimax search with alpha-beta pruning to non-cooperative, perfect-information games with more than two players. The minimax algorithm was generalized in [2] to the maxn algorithm applied to vectors of n-tuples representing the evaluations for each of the players. If we assume an upper bound on the sum of the evaluations for each player, and a lower bound on each individual evaluation, then shallow alpha-beta pruning is possible, but not deep pruning. In the best case, the asymptotic branching factor is reduced to (1 + 4bv'~b-"s~-3)/2. In the average case, however, pruning does not reduce the asymptotic branching factor. Thus, alpha-beta pruning is found to be effective only in the special case of two-player games. In addition, we show that it is an optimal directional algorithm for two players.

Pruning is one of the key procedures in training decision tree classifiers. It removes trivial rules from the raw knowledge base built from training examples, in order to avoid over-using noisy, conflicting, or fuzzy inputs, so that the refined model can generalize better with unseen cases. In this paper, we present a number of properties of k-norm pruning, a recently proposed pruning algorithm, which has clear theoretical interpretation. In an earlier paper it was shown that k-norm pruning compares very favorably in terms of accuracy and size with minimal cost-complexity pruning and error based pruning, two of the most cited decision tree pruning methods; it was also shown that k-norm pruning is more efficient, at times orders of magnitude more efficient than minimal cost-complexity pruning and error based pruning. In this paper, we demonstrate the validity of the k-norm properties through a series of theorems, and explain their practical significance.

In optimizing the neural network structure, there are two methods: the pruning scheme and the constructive scheme. This paper uses the pruning scheme to optimize neural network structure. The genetic algorithm is used to find out the optimum node pruning. In the conventional researches, the input and hidden layers were optimized separately. On the contrary we attempted to optimize the two layers simultaneously by encoding two layers in a chromosome. The offspring networks inherit the weights from the parent. For learning, we used the existing error back-propagation algorithm. In our experiment with various databases from UCI Machine Learning Repository, we could get the peak performance when the network size was reduced by about 8~25%. As a result of t-test the proposed method was shown to have a better performance, compared with other pruning or construction methods.

In this article we review standard null-move pruning and introduce our extended version of it, which we call verified null-move pruning. In verified null-move pruning, whenever the shallow null-move search indicates a fail-high, instead of cutting off the search from the current node, the search is continued with reduced depth. Our experiments with verified null-move pruning show that on average, it constructs a smaller search tree with greater tactical strength in comparison to standard null-move pruning. Moreover, unlike standard null-move pruning, which fails badly in zugzwang positions, verified null-move pruning manages to detect most zugzwangs and in such cases conducts a re-search to obtain the correct result. In addition, verified null-move pruning is very easy to implement, and any standard null-move pruning program can use verified null-move pruning by modifying only a few lines of code., Comment: 9 pages

We propose depth-limited heuristic search as a general paradigm for real-time problem solving in a dynamic environment. When combined with iterative-deepening, it provides the ability to commit to an action almost instantaneously, but allows the quality of that decision to improve as long as time is available. Once a deadline is reached, the best decision arrived at is executed. We illustrate the paradigm in three different settings, corresponding to single-agent search, two-player games, and multi-agent problem solving. First we review two-player minimax search with alpha-beta pruning. Minimax can be extended to themaxn algorithm for more than two players, which admits a much weaker form of alpha-beta pruning. Finally, we explore real-time search algorithms for single-agent problems. Minimax is specialized tominimin, which allows a very powerfulalpha pruning algorithm. In addition,real-time-A * allows backtracking while still guaranteeing a solution and making locally optimal decisions.

Maximal frequent itemsets (MFIs) mining is important for many applications. To improve the performance of the MFI algorithms, the key is to use appropriate pruning techniques which can maximally reduce the searching space of the algorithm. In this paper, we present a novel pruning technique, subset equivalence pruning. To mining MFIs in data streams, we reconstruct the FPmax* algorithm to a single-pass algorithm, named FPmax*-DS. Subset equivalence pruning technique is added in FPmax*-DS. The experiments show that the pruning technique can efficiently reduce the searching space. Especially for some dense datasets, the size of searching space can be trimmed off by about 40%.

Pruning decision trees is an effective way to overwhelm over-fitting in practice. Various pruning methods have been proposed in many literatures. Though these methods prune decision trees in the light of the principle of 'Minimum Description Length', they fail to explicitly take into account the impacts of tree scales in the pruning process. This paper proposes a simple decision tree pruning method based on RST (Rough Set Theory). Depth-fitting ratio is introduced for pruning a constructed decision tree, which involves both the depth and the explicit degrees of the sub-trees under evaluation. Experiments on some open data sets shows the feasibility of the new pruning method.

In this paper an algorithm for pruning a set of non-dominated solutions is proposed. The algorithm is based on the crowding distance calculation used in the elitist non-dominated sorting genetic algorithm (NSGA-II). The time complexity class of the new algorithm is estimated and in most cases it is the same as for the original pruning algorithm. Numerical results also support this estimate. For used bi-objective test problems, the proposed pruning algorithm is demonstrated to provide better distribution compared to the original pruning algorithm of NSGA-II. However, with tri-objective test problems there is no improvement and this study reveals that crowding distance does not estimate crowdedness well in this case and presumably also in cases of more objectives.

Most speech recognition systems search through large finite state machines to find the most likely path, or hypothesis. Efficient search in these large spaces requires pruning of some hypotheses. Popular pruning techniques include probability pruning which keeps only hypotheses whose probability falls within a prescribed factor from the most likely one, and rank pruning which keeps only a prescribed number of the most probable hypotheses. Rank pruning provides better control over memory use and search complexity, but it requires sorting of the hypotheses, a time consuming task that may slow the recognition process. We propose a pruning technique which combines the advantages of probability and rank pruning. Its time complexity is similar to that of probability pruning and its search-space size, memory consumption, and recognition accuracy are comparable to those of rank pruning. We also describe a research-motivated Java-based speech recognition system that is being built at UCSD.

We propose a computationally efficient detection algorithm with near ML performance for space-time communications systems. Our algorithm is based on pruning (excluding) branches from the search tree arising in the sphere decoding (SD) algorithm. The choice of the branches to be pruned relies on intuitive geometrical reasoning which is in turn based on a simplified channel model designed to capture the effect of badly conditioned channel realizations. The remaining search tree after pruning can be processed by the conventional SD algorithm with strongly reduced complexity as against scanning the complete tree. Simulation results show that despite the pruning near ML results can be obtained.

In this paper we investigate the relationship between closed itemset mining, the complete pruning technique and item ordering in the Apriori algorithm. We claim, that when proper item order is used, complete pruning does not necessarily speed up Apriori, and in databases with certain characteristics, pruning increases run time significantly. We also show that if complete pruning is applied, then an intersection-based technique not only results in a faster algorithm, but we get free closed-itemset selection concerning both memory consumption and run-time.

The min-max modular neural network with Gaussian zero-crossing function (M3-GZC) has locally tuned response characteristic and emergent incremental learning ability, but it suffers from quadratic complexity in storage space and response time. Redundant Sample pruning and redundant structure pruning can be considered to overcome these weaknesses. This paper aims at the latter; it analyzes the properties of receptive field in M3-GZC network, and then proposes a strategy for pruning redundant modules. Experiments on both structure pruning and integrated with sample pruning are performed. The results show that our algorithm reduces both the size of the network and the response time notably while not changing the decision boundaries.

We implemented a pruning algorithm for a self-organizing tree (S-TREE) using cluster validity. The S-TREE algorithm need to set the limit of the number of nodes U to prune extra nodes beforehand. However, the implemented algorithm is not necessary to set U for pruning. Setting U in advance is difficult because the value of U depends on the problem. Moreover, U might be an obstacle to self-organization and prevent the formation of natural clusters. The usefulness of the algorithm was examined by experiments on vector quantization (VQ). In the experiments, performance of an S-TREE with the new pruning algorithm was compared with that of an S-TREE without pruning. The results of experiments showed that the implemented algorithm not only greatly reduces the number of leaf nodes but also maintains the quality of decoded images to a level approximately equivalent to that of images decoded by the S-TREE without a pruning algorithm. The results therefore indicate that the implemented algorithm also contributes the formation of the natural clusters.

The paper presents an algorithm to solve the problem of classification for data mining applications. This is a decision tree classifier which uses modified gini index as the partitioning criteria. A pre-sorting technique is used to overcome the problem of sorting at each node of the tree. This technique is integrated with a breadth first tree growth strategy which enables us to calculate the best partition for each of the leaf nodes in a single scan of a database. We have implemented this algorithm using depth first tree growth strategy also. The algorithm uses a dynamic pruning approach which reduces the number of scans of the database and does away with a separate tree pruning phase. The proof of correctness, analysis and performance study are also presented.

Many researchers have shown that ensemble methods such as Boosting and Bagging improve the accuracy of classification. Boosting and Bagging perform well with unstable learning algorithms such as neural networks or decision trees. Pruning decision tree classifiers is intended to make trees simpler and more comprehensible and avoid over-fitting. However it is known that pruning individual classifiers of an ensemble does not necessarily lead to improved generalisation. Examples of individual tree pruning methods are Minimum Error Pruning (MEP), Error-based Pruning (EBP), Reduced-Error Pruning(REP), Critical Value Pruning (CVP) and Cost-Complexity Pruning (CCP). In this paper, we report the results of applying Boosting and Bagging with these five pruning methods to eleven datasets.

We present a new algorithm for selective search by iterative expansion of leaf nodes. The algorithm reasons with leaf evaluations in a way that leads to high confidence in the choice of move at the root. Performance of the algorithm is measured under a variety of conditions, as compared to minimax with α/β pruning, and to best-first minimax.