基于RST的决策树生成与剪枝方法

基于粗糙集理论构建决策树的过程中,通过计算各条件属性相对某分类的边界,选取边界最小的属性作为当前分支的节点,但此方法在多值分类情况下不能直接应用。为此,本文利用明确区的概念作为选取属性的标准,对各候选条件属性,选取相对于整个结果属性的明确区最大的属性作为当前分支的节点。并且基于明确区的概念,提出了一种新
新的对决策树进行剪枝的方法,通过一个实例说明该剪枝方法是简洁有效的.     

基于决策强度的决策表连续属性离散化算法

决策表中连续属性离散化,即将一个连续属性分为若干属性区间并为每个区间确定一个离散型数值。该文提出一种新的决策表连续属性离散化算法。首先使用决策强度来度量条件属性的重要性,并据此对条件属性按照属性重要性从小到大排序,然后按排序后的顺序,考察每个条件属性的所有断点,将冗余的断点去掉,从而将条件属性离散化。该算法易于理解,计算简单,算法的时间复杂性为O(3kn2)。     

一种基于动态决策块的超启发式跨单元调度方法

对运输能力受限条件下的跨单元调度问题进行分析, 提出一种基于动态决策块和蚁群优化 (Ant colony optimization, ACO) 的超启发式方法, 同时解决跨单元生产调度和运输调度问题. 在传统超启发式方法的基础上, 采用动态决策块策略, 通过蚁群算法合理划分决策块, 并为决策块选择合适的规则. 实验表明, 采用动态决策块策略的超启发式方法比传统的超启发式方法具有更好的性能, 本文所提的方法在最小化加权延迟总和目标方面有较好的优化能力 并且具有较高的计算效率.     

一种连续属性离散化的新方法

提出了一种基于聚类方法、结合粗集理论的连续属性离散化方法。在粗集理论中有一个重要概念：属性重要度（Attribute significance)，它常用来作为生成好的约简所采用的启发式评价函数。受此启发，在连续属性离散化方法中可把它用于属性选择，即从已离散化的属性集中选择出属性重要度最高的属性，再把它和待离散化的连续属性一起进行聚类学习，得到该连续属性的离散区间。文中介绍了该方法的算法描述，并通过实验与其他算法进行了比较。实验结果表明，由于这种方法在离散化过程中结合了粗集理论的思想,考虑了属性间的相互影响，从而产生了比较合理的划分点，提高了规则的分类精度。     

多变量连续属性离散化方法

目前很多离散化方法仅考虑单个变量,不能得到最优的离散化方案。文中提出一种多属性关系的数据离散化方法。凭借概率的模型选择和最小描述长度原理,获得多变量离散化衡量标准,基于该标准提出一种有效的启发式算法来寻找最好的离散化方案。对UCI数据集进行分类预测,实验结果表明该方法提高Nave贝叶斯分类器的学习精度。     

C-Net: A Method for Generating Non-deterministic and Dynamic Multivariate Decision Trees

Despite the fact that artificial neural networks (ANNs) are universal function approximators, their black box nature (that is, their lack of direct interpretability or expressive power) limits their utility. In contrast, univariate decision trees (UDTs) have expressive power, although usually they are not as accurate as ANNs. We propose an improvement, C-Net, for both the expressiveness of ANNs and the accuracy of UDTs by consolidating both technologies for generating multivariate decision trees (MDTs). In addition, we introduce a new concept, recurrent decision trees, where C-Net uses recurrent neural networks to generate an MDT with a recurrent feature. That is, a memory is associated with each node in the tree with a recursive condition which replaces the conventional linear one. Furthermore, we show empirically that, in our test cases, our proposed method achieves a balance of comprehensibility and accuracy intermediate between ANNs and UDTs. MDTs are found to be intermediate since they are more expressive than ANNs and more accurate than UDTs. Moreover, in all cases MDTs are more compact (i.e., smaller tree size) than UDTs. Received 27 January 2000 / Revised 30 May 2000 / Accepted in revised form 30 October 2000     

Discretization of a Continuous Curve

We consider the problem of approximating a finite-length continuous curve by a piecewise linear one whose segments are assumed to be connected by 2 DOF joints. We solve the problem under the assumption that the endpoints of the line segments lie on the continuous curve. Analytical expressions for the relative orientations of each pair of line segments as a function of a single rotational DOF are found. This angle can be chosen arbitrarily or used to optimize a secondary task. The motivating application for this paper is the control of a snake-like robot using gaits designed from shape primitives.     

动态决策树算法研究

该文在增量决策树算法的基础上,提出一种能够处理变化数据集的减量决策树算法,提出并证明了减量决策树算法中的三个基本定理,保证了减量决策树算法的可靠性。同时将传统的增量决策树算法与该文所提出的减量决策树算法相结合,构造出一种动态决策树算法,该算法很好地解决了发生增减变化的动态数据集构造决策树的问题,另外动态决策树算法的提出也促进了在线规则提取的发展与完善。     

一种连续属性动态分类规则数据挖掘方法

连续属性的处理是当前分类规则中一个热点研究问题。以往的算法往往是建立在离散化过程的基础上进行的,然而,该类方法不但会破坏数据中信息的精度,同时也使得概念的转换十分困难。文章在分析了以往算法的基础上,提出了利用包含度和蕴含度的方法进行连续属性的分类规则学习,并对该种方法的属性约简问题进行了讨论。可以看出,通过该文的研究较好地解决了数据精度和动态概念挖掘的问题,利用包含度和蕴含度的方法是一个十分有价值的研究方向。     

基于神经网络的分类决策树构造

目前基于符号处理的方法是解决分类规则提取问题的主要方法,而基于神经网络的连接主义方法则用的不多,其主要原因在于虽然神经网络的分类精度高,但难于提取其所隐含的分类规则与知识.针对这个问题,结合神经网络的具体特点,该文提出了一种基于神经网络的构造分类决策树的新方法.该方法通过神经网络训练建立各属性与分类结果之间的关系,进而通过提取各属性与分类结果之间的导数关系来建立分类决策树.给出了具体的决策树构造算法.同时为了提高神经网络所隐含关系的提取效果,提出了关系强化约束的概念并建立了具体的模型.实际应用结果证明了算法的有效性.     

A Distributed Algorithm for Constructing Minimal Spanning Trees

Most algorithms for constructing minimal spanning trees are sequential in operation. Distributed algorithms for constructing these trees operate both concurrently and asynchronously, and are useful in store-and-forward packet-switching computer-communication networks where there is typically no single source of control. The difficulties in designing such algorithms arise from communication and synchronization problems. This paper discusses these problems and describes the first distributed algorithm for constructing minimal spanning trees. This algorithm and the principles and techniques underlying its design will find application in large communication networks and large multiprocessor computer systems.     

决策树的自动生成模板

用于知识发现的大部分数据挖掘工具均采用规则发现和决策树分类技术来发现数据模式和规则。该文通过采用基于仿真属性的离散化方法,基于概率统计的未知属性与噪声数据处理方法以及基于误差的剪枝算法,实现了用于自动生成决策树的通用算法模板。利用该模板,决策树算法的设计者可以快速验证为解决特定决策问题而设计的新算法。构造决策树的基本机制是算法的设计者利用其自己定义的公式来初始化通用算法模板。然后利用该系统提供的交互式图形环境,针对不同的决策问题测试该算法,从而找出适合特定问题的算法。     

一种多值决策属性的决策系统的离散化算法

决策系统中连续属性的离散化,即实型属性空问向整型属性空间的映射,它是对决策表中属性约简的第一步.针对多值决策属性的决策信息系统,提出一种新的属性离散化算法.首先根据决策属性的不同,将条件属性集划分为不同的序列,对每两个序列求取候选断点,最后,综合所有的候选断点即为所求的候选断点集合;然后在基于条件属性重要度和贪心算法的基础上提出一种确定结果断点子集的新启发式算法.实例验证了本文所提出的算法能够取得较理想的连续属性离散化结果.     

HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries

In data stream environments, the initial plan of a long-running query may gradually become inefficient due to changes of the data characteristics. In this case, the query optimizer generates a more efficient plan based on the current statistics. The online transition from the old to the new plan is called dynamic plan migration. In addition to correctness, an effective technique for dynamic plan migration should achieve the following objectives: 1) minimize the memory and CPU overhead of the migration, 2) reduce the duration of the transition, and 3) maintain a steady output rate. The only known solutions for this problem are the moving states (MS) and parallel track (PT) strategies, which have some serious shortcomings related to the above objectives. Motivated by these shortcomings, we first propose HybMig, which combines the merits of MS and PT and outperforms both in every aspect. As a second step, we extend PT, MS, and HybMig to the general problem of migration, where both the new and the old plans are treated as black boxes     

Development of a Cloud Trust Label: A Delphi Approach

The purpose of this research is to identify the potential information components of an online, real-time trust label, which is proposed as a communication mechanism to encourage trust in cloud service providers and cloud computing products. An online Delphi process was used with 28 cloud computing experts (including vendors, software providers, and legal and business representatives). The proposed label contains 81 information components, covering the cloud service provider (e.g. physical location, legal jurisdiction), the cloud service itself (e.g. data location, security, backup, certification), and a historical service-level summary (e.g. uptime data, support response times). The potential benefits of such a label to encourage trustworthiness perceptions and trust behaviors in the cloud computing environment are explored. Limitations of the study are highlighted, and further research studies are suggested to test the concept of the label and to refine the components of the label itself.     

一种连续条件属性值的决策表的归纳学习方法

对由连续条件属性值和离散决策属性值组成的决策表,提出了一种归纳学习方法。把决策表中的连续条件属性值看作一矩阵,进行矩阵的奇异值分解,以确定决策表条件属性的数目。用模糊C均值聚类的方法对连续条件属性值进行不同聚类数目的聚类,得到不同聚类数目下的离散决策表,对这些决策表进行条件属性简化,从而得到不同的条件属性数目。比较矩阵奇异值分解后决策表条件属性的数目和上述不同聚类数目下的离散决策表简化后的条件属性的数目,并考虑决策属性的数目,确定最终的聚类数目。在此基础上,给出了由连续条件属性值和离散决策属性值组成的决策表的归纳学习方法,并验证了其有效性。     

Combining Classifiers with Meta Decision Trees

The paper introduces meta decision trees (MDTs), a novel method for combining multiple classifiers. Instead of giving a prediction, MDT leaves specify which classifier should be used to obtain a prediction. We present an algorithm for learning MDTs based on the C4.5 algorithm for learning ordinary decision trees (ODTs). An extensive experimental evaluation of the new algorithm is performed on twenty-one data sets, combining classifiers generated by five learning algorithms: two algorithms for learning decision trees, a rule learning algorithm, a nearest neighbor algorithm and a naive Bayes algorithm. In terms of performance, stacking with MDTs combines classifiers better than voting and stacking with ODTs. In addition, the MDTs are much more concise than the ODTs and are thus a step towards comprehensible combination of multiple classifiers. MDTs also perform better than several other approaches to stacking.     

一种基于t相似分类的连续值域决策表的决策算法

首先给出t相似度的定义,并引入t相似类的概念.随后,借助研究对象的t相似类定义了相似划分算法和广义决策集,并研究它们的性质,给出基于相似划分的类对应规则提取方法.接着,给出类对应规则中各条件类的区间表达,得到了面向连续值域决策表的规则提取算法.最后,结合实例说明了决策规则提取算法的实现过程.     

Khiops: A Statistical Discretization Method of Continuous Attributes

In supervised machine learning, some algorithms are restricted to discrete data and have to discretize continuous attributes. Many discretization methods, based on statistical criteria, information content, or other specialized criteria, have been studied in the past. In this paper, we propose the discretization method Khiops,¹ based on the chi-square statistic. In contrast with related methods ChiMerge and ChiSplit, this method optimizes the chi-square criterion in a global manner on the whole discretization domain and does not require any stopping criterion. A theoretical study followed by experiments demonstrates the robustness and the good predictive performance of the method.