增量决策树算法研究

文中主要解决传统的ID3算法不能处理增量数据集构造决策树的问题。在传统ID3决策树算法和原有增量算法的基础上,利用信息论中熵变原理的特点,对与增量决策树算法相关的三个定理进行相应的改进,在理论上证明了改进的增量决策树算法的有效性和可靠性。同时对增量决策树算法和ID3算法的复杂度进行了对比分析,得出增量决策树算法的实例费用和信息熵费用都高于ID3算法的结论。最后通过一个实验证明,改进的增量决策树算法能够构造出与ID3算法形态基本相同的决策树。     

增量决策树算法研究

文中主要解决传统的ID3算法不能处理增量数据集构造决策树的问题.在传统ID3决策树算法和原有增量算法的基础上,利用信息论中熵变原理的特点,对与增量决策树算法相关的三个定理进行相应的改进,在理论上证明了改进的增量决策树算法的有效性和可靠性.同时对增量决策树算法和ID3算法的复杂度进行了对比分析,得出增量决策树算法的实例费用和信息熵费用都高于ID3算法的结论.最后通过一个实验证明,改进的增量决策树算法能够构造出与ID3算法形态基本相同的决策树.     

流计算模式下概率粗糙集三支决策的快速计算

概率粗糙集三支决策是不确定问题求解的一种重要理论,流计算模式是一种新型的动态内存计算形式,实施流计算模式下三支决策的快速动态计算是一项具有挑战性的新议题。本研究以流计算模式中的两个核心计算步骤即动态增量与动态减量作为研究对象,提出了一种流计算模式下概率粗糙集三支决策域的快速动态学习方法。首先对流计算模式中三支决策动态增量和动态减量的不同变化情况进行了数据建模。然后基于不同数据变化情况分别讨论了数据增量与数据减量时三支决策域的变化推理,并且基于上述理论给出了流计算模式下的三支决策动态增减学习算法。该算法能够以更低的时间复杂度获得与经典三支决策算法相同决策效果。最后通过八种UCI数据集的实验证明了流计算模式下三支决策动态增减学习算法在时间消耗上明显优于经典概率粗糙集三支决策算法,并且在不同阈值下具有稳定的决策效率。本研究表明了流计算模式下三支决策快速计算是可行的。     

动态粗集理论在决策树算法中的应用研究

基于动态粗集理论,提出一种改进的动态粗集决策树算法。改进后的算法对每一属性计算数据对象迁移系数的和,值最大的属性成为决策树的根;在对决策树分叉时,给每一决策类别的数据对象集合计算从根到分叉属性所构成的属性集的膨胀度,值大的属性构成分支结点。算法在UCI机器学习数据库原始数据集及其噪音数据集上的实验结果表明,该算法构造的决策树在规模与分类准确率上均优于ID3算法及C4.5算法。     

粗决策树动态规则提取算法研究及应用

针对静态算法对大数据和增量数据处理不足的问题,构造了基于粗决策树的动态规则提取算法,并将其应用于旋转机械故障诊断中.将粗集与决策树结合,用增量方式实现样本抽取;经过动态约简、决策树构造、规则提取与选择、匹配4个步骤的循环迭代过程,实现了数据的动态规则提取,使得提取的规则具有更高的可信度;同时,将算法应用于旋转机械故障诊断这一动态问题中,验证了算法的有效性;最后,将所提算法分别与静态算法和增量式动态算法进行了效率对比分析,实验结果表明,所提算法能够以最精简的规则获得更多数据隐含信息.     

增量式的多变量决策树构造算法研究

针对增量数据集,结合粗糙集理论和多变量决策树的优点,给出了增量式的多变量决策树构造算法。该算法针对新增样本与已有规则集产生矛盾,即条件属性相匹配,而决策属性不匹配的情况,计算条件属性相对于决策属性的核,如果核不为空,则计算核相对于决策属性的相对泛化,根据不同的结果形成不同的子集,最终形成不同的决策树分支。该算法很好地避免了在处理增量数据集时,不断重构决策树。实例证明该算法的正确性,对处理小增量数据集具有良好的性能。     

一种新的增量决策树算法

对于数据增加迅速的客户行为分析、Web日志分析、网络入侵检测等在线分类系统来说,如何快速适应新增样本是确保其分类正确和可持续运行的关键。该文提出了一种新的适应数据增量的决策树算法,该算法同贝叶斯方法相结合,在原有决策树的基础上利用新增样本迅速训练出新的决策树。实验结果表明,提出的算法可以较好的解决该问题,与重新构造决策树相比,它的时间开销更少,且具有更高的分类准确率,更适用于在线分类系统。     

增量式的多变量决策树构造算法研究

针对增量数据集,结合粗糙集理论和多变量决策树的优点,给出了增量式的多变量决策树构造算法.该算法针对新增样本与已有规则集产生矛盾,即条件属性相匹配,而决策属性不匹配的情况,计算条件属性相对于决策属性的核,如果核不为空,则计算核相对于决策属性的相对泛化,根据不同的结果形成不同的子集,最终形成不同的决策树分支.该算法很好地避免了在处理增量数据集时,不断重构决策树.实例证明该算法的正确性,对处理小增量数据集具有良好的性能.     

属性约简中的范式转换算法研究

通过研究属性约简中合取范式到析取范式的转换过程,发现减少冗余项和重复计算可以适当提高转换效率。同时考虑到范式的动态变化,设计一种边转换边化简的增量转换算法,可以利用已有结果直接进行计算。对于减量情况,抽象出范式转换的数学模型,给出相应转换的构造形式和分析过程,并提出一种近似减量转换算法,从而实现了不同变化情况下生成析取范式的动态计算。最后通过仿真实验验证了算法的可行性和高效性。     

一种多变量决策树的构造与研究

单变量决策树算法造成树的规模庞大、规则复杂、不易理解,而多变量决策树是一种有效用于分类的数据挖掘方法,构造的关键是根据属性之间的相关性选择合适的属性组合构成一个新的属性作为节点。结合粗糙集原理中的知识依赖性度量和信息系统中条件属性集的离散度概念,提出了一种多变量决策树的构造算法（RD）。在UCI上部分数据集的实验结果表明,提出的多变量决策树算法的分类效果与传统的ID3算法以及基于核方法的多变量决策树的分类效果相比,有一定的提高。     

Very Fast C4.5 Decision Tree Algorithm

This paper presents a novel algorithm so-called VFC4.5 for building decision trees. It proposes an adaptation of the way C4.5 finds the threshold of a continuous attribute. Instead of finding the threshold that maximizes gain ratio, the paper proposes to simply reduce the number of candidate cut points by using arithmetic mean and median to improve a reported weakness of the C4.5 algorithm when it deals with continuous attributes. This paper will focus primarily on the theoretical aspects of the VFC4.5 algorithm. An empirical trials, using 49 datasets, show that, in most times, the VFC4.5 algorithm leads to smaller decision trees with better accuracy compared to the C4.5 algorithm. VFC4.5 gives excellent accuracy results as C4.5 and it is much faster than the VFDT algorithm.     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

An incremental decision tree algorithm based on rough sets and its application in intrusion detection

As we know, learning in real world is interactive, incremental and dynamical in multiple dimensions, where new data could be appeared at anytime from anywhere and of any type. Therefore, incremental learning is of more and more importance in real world data mining scenarios. Decision trees, due to their characteristics, have been widely used for incremental learning. In this paper, we propose a novel incremental decision tree algorithm based on rough set theory. To improve the computation efficiency of our algorithm, when a new instance arrives, according to the given decision tree adaptation strategies, the algorithm will only modify some existing leaf node in the currently active decision tree or add a new leaf node to the tree, which can avoid the high time complexity of the traditional incremental methods for rebuilding decision trees too many times. Moreover, the rough set based attribute reduction method is used to filter out the redundant attributes from the original set of attributes. And we adopt the two basic notions of rough sets: significance of attributes and dependency of attributes, as the heuristic information for the selection of splitting attributes. Finally, we apply the proposed algorithm to intrusion detection. The experimental results demonstrate that our algorithm can provide competitive solutions to incremental learning.     

Learning rules of a card game from video

This paper presents a framework for automatically learning rules of a simple game of cards using data from a vision system observing the game being played. Incremental learning of object and protocol models from video, for use by an artificial cognitive agent, is presented. iLearn??a novel algorithm for inducing univariate decision trees for symbolic datasets is introduced. iLearn builds the decision tree in an incremental way allowing automatic learning of rules of the game.     

不同通信模型下的全光树环网波长分配算法

研究了波分复用全光树环网在不同通信模型下的波长分配算法及其最坏性能分析.对于静态模型,证明了5L/2是树环网所需波长数的紧界.对于动态模型,提出了一种近似比为∑_i=1^hmax_r∈Ri[log|V(r)|]+h的波长分配算法,其中h为树环网的基树的层数,R_i为树环网中处于第i层的环的集合,|V(r)|为环r上的节点数.对于增量模型,提出了一种近似度为O[log₂(t+1)]的波长分配算法,其中t为树环网中的环数.     

Decision tree induction using a fast splitting attribute selection for large datasets

Several algorithms have been proposed in the literature for building decision trees (DT) for large datasets, however almost all of them have memory restrictions because they need to keep in main memory the whole training set, or a big amount of it, and such algorithms that do not have memory restrictions, because they choose a subset of the training set, need extra time for doing this selection or have parameters that could be very difficult to determine. In this paper, we introduce a new algorithm that builds decision trees using a fast splitting attribute selection (DTFS) for large datasets. The proposed algorithm builds a DT without storing the whole training set in main memory and having only one parameter but being very stable regarding to it. Experimental results on both real and synthetic datasets show that our algorithm is faster than three of the most recent algorithms for building decision trees for large datasets, getting a competitive accuracy.     

A constraint satisfaction problem algorithm for large-scale multi-panel composite structures

Structural and Multidisciplinary Optimization - This paper proposes a constraint satisfaction problem algorithm based on implicit decision trees and dynamic programming for the design of multiple...     

决策表属性约简集的增量式更新算法

针对动态变化的决策表,研究了属性约简集的动态更新问题。在详细分析新增对象的所有可能情况的基础上,提出一种基于分辨矩阵元素集的属性约简集增量式更新算法。该算法根据新增对象的不同情况快速更新分辨矩阵元素集,依据分辨矩阵元素集中增加和减少的元素有效地更新原属性约简集,快速得到新的最小属性约简。最后,通过5个UCI的数据集验证了算法的有效性。     

Logistic model tree extraction from artificial neural networks.

Artificial neural networks (ANNs) are a powerful and widely used pattern recognition technique. However, they remain "black boxes" giving no explanation for the decisions they make. This paper presents a new algorithm for extracting a logistic model tree (LMT) from a neural network, which gives a symbolic representation of the knowledge hidden within the ANN. Landwehr's LMTs are based on standard decision trees, but the terminal nodes are replaced with logistic regression functions. This paper reports the results of an empirical evaluation that compares the new decision tree extraction algorithm with Quinlan's C4.5 and ExTree. The evaluation used 12 standard benchmark datasets from the University of California, Irvine machine-learning repository. The results of this evaluation demonstrate that the new algorithm produces decision trees that have higher accuracy and higher fidelity than decision trees created by both C4.5 and ExTree.