集成学习中基于离散化方法的基分类器构造研究

为构造集成学习中具有差异性的基分类器,提出基于数据离散化的基分类器构造方法,并用于支持向量机集成。该方法采用粗糙集和布尔推理离散化算法处理训练样本集,能有效删除不相关和冗余的属性,提高基分类器的准确性和差异性。实验结果表明,所提方法能取得比传统集成学习算法Bagging和Adaboost更好的性能。     

MODL: A Bayes optimal discretization method for continuous attributes

While real data often comes in mixed format, discrete and continuous, many supervised induction algorithms require discrete data. Efficient discretization of continuous attributes is an important problem that has effects on speed, accuracy and understandability of the induction models. In this paper, we propose a new discretization method MODL¹, founded on a Bayesian approach. We introduce a space of discretization models and a prior distribution defined on this model space. This results in the definition of a Bayes optimal evaluation criterion of discretizations. We then propose a new super-linear optimization algorithm that manages to find near-optimal discretizations. Extensive comparative experiments both on real and synthetic data demonstrate the high inductive performances obtained by the new discretization method. Editor: Tom Fawcett ¹French patent No. 04 00179.     

PRIE: a system for generating rulelists to maximize ROC performance

Rules are commonly used for classification because they are modular, intelligible and easy to learn. Existing work in classification rule learning assumes the goal is to produce categorical classifications to maximize classification accuracy. Recent work in machine learning has pointed out the limitations of classification accuracy: when class distributions are skewed, or error costs are unequal, an accuracy maximizing classifier can perform poorly. This paper presents a method for learning rules directly from ROC space when the goal is to maximize the area under the ROC curve (AUC). Basic principles from rule learning and computational geometry are used to focus the search for promising rule combinations. The result is a system that can learn intelligible rulelists with good ROC performance.     

A novel discretization scheme for the close enough traveling salesman problem

This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.     

Norm invariant discretization for sampled-data fault detection

In this paper, the problem of fault detection in sampled-data systems is studied. It is shown that norms of a sampled system are equal to the corresponding norms of a certain discrete time system. Based on this discretization, the sampled-data fault detection problem can be converted to an equivalent discrete-time problem. A framework that unifies the H₂ and H_∞ optimal residual generators in sampled-data systems is then proposed.     

Instance weighting versus threshold adjusting for cost-sensitive classification

In real-world classification problems, different types of misclassification errors often have asymmetric costs, thus demanding cost-sensitive learning methods that attempt to minimize average misclassification cost rather than plain error rate. Instance weighting and post hoc threshold adjusting are two major approaches to cost-sensitive classifier learning. This paper compares the effects of these two approaches on several standard, off-the-shelf classification methods. The comparison indicates that the two approaches lead to similar results for some classification methods, such as Naïve Bayes, logistic regression, and backpropagation neural network, but very different results for other methods, such as decision tree, decision table, and decision rule learners. The findings from this research have important implications on the selection of the cost-sensitive classifier learning approach as well as on the interpretation of a recently published finding about the relative performance of Naïve Bayes and decision trees.     

Implications of discretization on dissipativity and economic model predictive control

Economic model predictive control, where a generic cost is employed as the objective function to be minimized, has recently gained much attention in model predictive control literature. Stability proof of the resulting closed-loop system is often based on strict dissipativity of the system with respect to the objective function. In this paper, starting with a continuous-time setup, we consider the ‘discretize then optimize’ approach to solving continuous-time optimal control problems and investigate the effect of the discretization process on the closed-loop system. We show that while the continuous-time system may be strictly dissipative with respect to the objective function, it is possible that the resulting closed-loop system is unstable if the discrete-approximation of the continuous-time optimal control problem is not properly set up. We use a popular example from the economic MPC literature to illustrate our results.     

Handling over-fitting in test cost-sensitive decision tree learning by feature selection, smoothing and pruning

Cost-sensitive learning algorithms are typically designed for minimizing the total cost when multiple costs are taken into account. Like other learning algorithms, cost-sensitive learning algorithms must face a significant challenge, over-fitting, in an applied context of cost-sensitive learning. Specifically speaking, they can generate good results on training data but normally do not produce an optimal model when applied to unseen data in real world applications. It is called data over-fitting. This paper deals with the issue of data over-fitting by designing three simple and efficient strategies, feature selection, smoothing and threshold pruning, against the TCSDT (test cost-sensitive decision tree) method. The feature selection approach is used to pre-process the data set before applying the TCSDT algorithm. The smoothing and threshold pruning are used in a TCSDT algorithm before calculating the class probability estimate for each decision tree leaf. To evaluate our approaches, we conduct extensive experiments on the selected UCI data sets across different cost ratios, and on a real world data set, KDD-98 with real misclassification cost. The experimental results show that our algorithms outperform both the original TCSDT and other competing algorithms on reducing data over-fitting.     

On the enhancement of computation and exploration of discretization approaches for meshless shape design sensitivity analysis

A new implementation of Reproducing Kernel Particle Method (RKPM) is proposed to enhance the process of shape design sensitivity analysis (DSA). The acceleration process is accomplished by expressing RKPM shape functions and their derivatives explicitly in terms of kernel function moments. In addition, two different discretization approaches are explored elaborately, which emanate from discretizing design sensitivity equation using the direct differentiation method. Comparison of these two approaches is made, and the equivalence of these two superficially different approaches is demonstrated through two elastostatics problems. The effectiveness of the enhanced RKPM is also verified by comparison of consumption of computer time between the classical method and the improved method.     

Automatically countering imbalance and its empirical relationship to cost

Learning from imbalanced data sets presents a convoluted problem both from the modeling and cost standpoints. In particular, when a class is of great interest but occurs relatively rarely such as in cases of fraud, instances of disease, and regions of interest in large-scale simulations, there is a correspondingly high cost for the misclassification of rare events. Under such circumstances, the data set is often re-sampled to generate models with high minority class accuracy. However, the sampling methods face a common, but important, criticism: how to automatically discover the proper amount and type of sampling? To address this problem, we propose a wrapper paradigm that discovers the amount of re-sampling for a data set based on optimizing evaluation functions like the f-measure, Area Under the ROC Curve (AUROC), cost, cost-curves, and the cost dependent f-measure. Our analysis of the wrapper is twofold. First, we report the interaction between different evaluation and wrapper optimization functions. Second, we present a set of results in a cost- sensitive environment, including scenarios of unknown or changing cost matrices. We also compared the performance of the wrapper approach versus cost-sensitive learning methods—MetaCost and the Cost-Sensitive Classifiers—and found the wrapper to outperform the cost-sensitive classifiers in a cost-sensitive environment. Lastly, we obtained the lowest cost per test example compared to any result we are aware of for the KDD-99 Cup intrusion detection data set.     

Large margin cost-sensitive learning of conditional random fields

We tackle the structured output classification problem using the Conditional Random Fields (CRFs). Unlike the standard 0/1 loss case, we consider a cost-sensitive learning setting where we are given a non-0/1 misclassification cost matrix at the individual output level. Although the task of cost-sensitive classification has many interesting practical applications that retain domain-specific scales in the output space (e.g., hierarchical or ordinal scale), most CRF learning algorithms are unable to effectively deal with the cost-sensitive scenarios as they merely assume a nominal scale (hence 0/1 loss) in the output space. In this paper, we incorporate the cost-sensitive loss into the large margin learning framework. By large margin learning, the proposed algorithm inherits most benefits from the SVM-like margin-based classifiers, such as the provable generalization error bounds. Moreover, the soft-max approximation employed in our approach yields a convex optimization similar to the standard CRF learning with only slight modification in the potential functions. We also provide the theoretical cost-sensitive generalization error bound. We demonstrate the improved prediction performance of the proposed method over the existing approaches in a diverse set of sequence/image structured prediction problems that often arise in pattern recognition and computer vision domains.     

Comparative analysis of discretization methods in Bayesian networks

A key step in implementing Bayesian networks (BNs) is the discretization of continuous variables. There are several mathematical methods for constructing discrete distributions, the implications of which on the resulting model has not been discussed in literature. Discretization invariably results in loss of information, and both the discretization method and the number of intervals determines the level of such loss. We designed an experiment to evaluate the impact of commonly used discretization methods and number of intervals on the developed BNs. The conditional probability tables, model predictions, and management recommendations were compared and shown to be different among models. However, none of the models did uniformly well in all comparison criteria. As we cannot justify using one discretization method against others, we recommend caution when discretization is used, and a verification process that includes evaluating alternative methods to ensure that the conclusions are not an artifact of the discretization approach.     

A closed-form reduction of multi-class cost-sensitive learning to weighted multi-class learning

In cost-sensitive learning, misclassification costs can vary for different classes. This paper investigates an approach reducing a multi-class cost-sensitive learning to a standard classification task based on the data space expansion technique developed by Abe et al., which coincides with Elkan's reduction with respect to binary classification tasks. Using this proposed reduction approach, a cost-sensitive learning problem can be solved by considering a standard 0/1 loss classification problem on a new distribution determined by the cost matrix. We also propose a new weighting mechanism to solve the reduced standard classification problem, based on a theorem stating that the empirical loss on independently identically distributed samples from the new distribution is essentially the same as the loss on the expanded weighted training set. Experimental results on several synthetic and benchmark datasets show that our weighting approach is more effective than existing representative approaches for cost-sensitive learning.     

A discretization method for nonlinear delayed non-affine systems

The input time delay is always existent in the practical systems. Analysis of the delay phenomenon in a continuous-time domain is sophisticated. It is appropriate to obtain its corresponding discrete-time model for implementation via digital computer. This paper proposes a new discretization method for calculating a sampled-data representation of nonlinear time-delayed non-affine systems. The proposed scheme provides a finite-dimensional representation for nonlinear systems with non-affine time-delayed input enabling existing nonlinear controller design techniques to be applied to them. The performance of the proposed discretization procedure is evaluated by using a nonlinear system with non-affine time-delayed input. For this nonlinear system, various time delay values are considered.     

样本自适应的不平衡分类器

大数据时代,不平衡数据分类在实际应用场景中频繁出现。以二分类为例,传统分类器由于较难学习少数类数据集内部的本质结构,容易将少数类样本错误分类。针对这一问题,一种有效的解决方法是在传统的方法中引入代价敏感机制,为少数类样本赋予更高的误分代价以提升其预测精度。这类方法同等对待了同类样本集中的数据,然而同一类内的不同样本可能对训练过程有不同程度的贡献。为了提升代价敏感机制的有效性,样本自适应的代价敏感策略为不同的样本赋予不同的权重。首先,通过考察样本局部的类分布情况,判断其距离两类样本边界的远近;然后,根据边界分布理论,即距离决策面越近的样本对决策面位置的影响越大,为距离两类样本边界越近的样本赋予越高的权重。实验过程中,通过将样本自适应代价敏感策略应用于LDM,并在标准数据集上进行一系列对比实验,验证了样本自适应代价敏感策略在处理不平衡数据分类问题上的有效性。     

Multiresolution state-space discretization for Q-Learning with pseudorandomized discretization

A multiresolution state-space discretization method with pseudorandom gridding is developed for the episodic unsupervised learning method of Q-learning.It is used as the learning agent for closed-loop control of morphing or highly reconfigurable systems.This paper develops a method whereby a state-space is adaptively discretized by progressively finer pseudorandom grids around the regions of interest within the state or learning space in an effort to break the Curse of Dimensionality.Utility of the method is demonstrated with application to the problem of a morphing airfoil,which is simulated by a computationally intensive computational fiuid dynamics model.By setting the multiresolution method to define the region of interest by the goal the agent seeks,it is shown that this method with the pseudorandom grid can learn a specific goal within ±0.001 while reducing the total number of state-action pairs needed to achieve this level of specificity to less than 3000.     

Minimizing fuel cost in gas transmission networks by dynamic programming and adaptive discretization

In this paper, the problem of computing optimal transportation plans for natural gas by means of compressor stations in pipeline networks is addressed. The non-linear (non-convex) mathematical model considers two types of continuous decision variables: mass flow rate along each arc, and gas pressure level at each node. The problem arises due to the presence of costs incurred when running compressors in order to keep the gas flowing through the system. Hence, the assignment of optimal values to flow and pressure variables such that the total fuel cost is minimized turns out to be essential to the gas industry. The first contribution from the paper is a solution method based on dynamic programming applied to a discretized version of the problem. By utilizing the concept of a tree decomposition, our approach can handle transmission networks of arbitrary structure, which makes it distinguished from previously suggested methods. The second contribution is a discretization scheme that keeps the computational effort low, even in instances where the running time is sensitive to the size of the mesh. Several computational experiments demonstrate that our methods are superior to a commercially available local optimizer.     

Worst case bounds on the point-wise discretization error in boundary element method for the elasticity problem

In this work, point-wise discretization error is bounded via interval approach for the elasticity problem using interval boundary element formulation. The formulation allows for computation of the worst case bounds on the boundary values for the elasticity problem. From these bounds the worst case bounds on the true solution at any point in the domain of the system can be computed. Examples are presented to demonstrate the effectiveness of the treatment of local discretization error in elasticity problem via interval methods.     

Classification cost: An empirical comparison among traditional classifier, Cost-Sensitive Classifier, and MetaCost

Loan fraud is a critical factor in the insolvency of financial institutions, so companies make an effort to reduce the loss from fraud by building a model for proactive fraud prediction. However, there are still two critical problems to be resolved for the fraud detection: (1) the lack of cost sensitivity between type I error and type II error in most prediction models, and (2) highly skewed distribution of class in the dataset used for fraud detection because of sparse fraud-related data. The objective of this paper is to examine whether classification cost is affected both by the cost-sensitive approach and by skewed distribution of class. To that end, we compare the classification cost incurred by a traditional cost-insensitive classification approach and two cost-sensitive classification approaches, Cost-Sensitive Classifier (CSC) and MetaCost. Experiments were conducted with a credit loan dataset from a major financial institution in Korea, while varying the distribution of class in the dataset and the number of input variables. The experiments showed that the lowest classification cost was incurred when the MetaCost approach was used and when non-fraud data and fraud data were balanced. In addition, the dataset that includes all delinquency variables was shown to be most effective on reducing the classification cost.