VFP数据库中混沌加密算法设计与实现

作为主要密码技术之一的序列密码，它的安全强度完全取决于其所产生的伪随机序列的好坏。而混沌系统具有对初始条件敏感性、随机性、相关性等优良的密码学性能，能够产生性能良好的伪随机序列，所以很适合于序列加密。文中分析了基于Logistic混沌映射的加密算法原理；给出了一个基于该算法的具体加密／解密算法；利用VFP工具具体实现了加密／解密算法，并用该算法对一个具体实例进行了加密。实验结果表明混沌加密算法完全可以满足VFP数据库应用系统保密的要求。     

VFP数据库中混沌加密算法设计与实现

作为主要密码技术之一的序列密码,它的安全强度完全取决于其所产生的伪随机序列的好坏。而混沌系统具有对初始条件敏感性、随机性、相关性等优良的密码学性能,能够产生性能良好的伪随机序列,所以很适合于序列加密。文中分析了基于Logistic混沌映射的加密算法原理;给出了一个基于该算法的具体加密/解密算法;利用VFP工具具体实现了加密/解密算法,并用该算法对一个具体实例进行了加密。实验结果表明混沌加密算法完全可以满足VFP数据库应用系统保密的要求。     

有新类的动态数据流分类算法研究

针对有新类的动态数据流分类算法检测新类性能不高的问题,提出一种基于k近邻的完全随机森林算法(KCRForest)。该算法利用动态数据流中已知类样本构建完全随机森林的完全随机树,并根据叶节点平均路径长度将样本空间分成正常区域与异常区域。通过落入异常区域中样本的k近邻计算该样本离群值。若样本离群值大于设定阈值,则判断样本为新类,否则为已知类。落入异常区域的已知类样本由该样本的k近邻得到样本标签分布,否则取该区域中原训练样本标签分布,投票得到样本标签。当新类样本检测达到一定数量时,利用新类样本信息更新模型,便于检测其他新类。为了验证KCRForest算法检测新类的有效性,分别在4个UCI数据集上进行实验,并与已有算法进行比较。结果表明该算法的新类检测性能优于或与iForest+SVM算法、LOF+SVM算法相当,分类准确率明显高于SENCForest算法。     

基于PRDT的16节点NoC路由算法

网络结构对于片上网络系统的性能和功耗发挥着重要作用，PRDT(2,1)有着较低的网络直径和平均距离、常数的节点度以及良好的可扩展性，这些特点使其非常适于NoC。为了提高小规模PRDT的路由性能，该文提出了一种binary路由算法，当网络规模不大于16时，该算法无须使用虚拟通道即可实现无死锁路由，通过增加少量虚拟通道，可改进为完全自适应路由算法。对所提出的路由算法与原有的向量路由算法进行仿真比较，结果显示binary算法在硬件成本较低的同时，性能更为优异，完全可以应用于基于PRDT的小规模NoC网络。     

冒泡排序算法的改进

通过对传统冒泡排序算法的讨论，指出其效率不高的缺陷，提出了局部冒泡排序算法，并编程予以实现，其效率及性能较传统的冒泡排序算法有一定程度的提高。同时采用随机及特殊数据在计算机上对传统冒泡排序和局部冒泡排序算法进行了分析和性能对比测试，对局部冒泡排序算法的时间性能作出了评价，指出了局部冒泡排序算法的特点及优势。通过实验证明了局部冒泡排序算法较传统冒泡排序算法在时同性能上有了一定的改进。     

基于CMAES集成学习方法的地表水质分类

为了提高人民生活质量,政府部门不断加强水质管理,然而人工分类方法无法满足实时处理的需求,传统机器学习方法的分类准确率又不够高。集成学习使用多种学习算法来获得比单一学习算法更好的预测性能。首先,对集成学习进行概述,简要介绍了Bagging和Boosting算法,并提出基于协方差自适应调整的进化策略算法(CMAES)的集成学习方法。接着,介绍了数据处理方式、模型评估方法和评价指标。最后,用CMAES集成学习方法对逻辑回归、线性判别分析、支持向量机、决策树、完全随机树、朴素贝叶斯、K-邻近算法、随机森林、完全随机树林、深度级联森林十种模型进行集成。实验结果表明,CMAES集成学习方法优于所有其他模型,该方法将继续被应用到未来的研究之中。     

地图中点状要素标注算法设计

介绍了一种时间复杂度为O（nlogn）的点状要索标注算法。该算法从美学角度出发设计了优先级标注，并且能实现完全无重叠的点状要素标注，标注性能比较好。该算法编程实现比较简单，可以应用于GIS二次开发当中。     

随机摄动粒子群优化算法

基于粒子群优化算法种群结构相对独立的特点，提出了一种改进的粒子群优化算法一随机摄动粒子群优化算法。该算法通过对每一次进化计算后记忆中的最优粒子进行随机摄动操作来提高解的精度和算法的搜索效率，同时通过对种群中的最差粒子重新进行初始化来保持种群的多样性以避免陷入局部最优解。通过典型复杂函数测试表明，随机摄动粒子群优化算法的优化性能和效率远远超过基本粒子群优化算法。     

复杂网络中随机图模型研究

随着复杂网络研究的兴起，随机图成为一种重要复杂网络模型。基于完全图的生成子图的思想，得到了生成随机图的一种新算法，即用去边的方法生成随机图的算法，并用数值实验验证了加边和去边生成的随机图的统计特性（最大度、最小度、聚集系数、平均最短路径和平均度）是相近的，用去边的方法得到的图的度分布曲线在其平均度处达到峰值，随后呈指数下降，这与随机图的度分布是相同的。为了得到稀疏连通的随机图，又提出了一个不去割边的近似随机图生成算法，并从理论上说明了该算法生成的图是连通的，同时通过数值实验验证了图的连通性，并与加边随机图的统计特性进行了比较。     

一种改进的多模式匹配算法在Snort中的应用

模式匹配算法是入侵检测系统的重要组成部分。为进一步提高入侵检测系统的性能和效率,提出一种新的多模式匹配算法——完全自动机匹配算法(CA-AC算法),并将其应用于入侵检测系统Snort中。该算法是对Aho-Corasick算法的改进,根据新算法进行状态转换使得自动机状态减少,相应节约了存储空间。分析了算法的复杂度。实验表明,完全自动机算法在Snort中的应用改进了算法的性能,提高了Snort系统的规则检测效率。     

Online Ensemble Learning: An Empirical Study

We study resource-limited online learning, motivated by the problem of conditional-branch outcome prediction in computer architecture. In particular, we consider (parallel) time and space-efficient ensemble learners for online settings, empirically demonstrating benefits similar to those shown previously for offline ensembles. Our learning algorithms are inspired by the previously published boosting by filtering framework as well as the offline Arc-x4 boosting-style algorithm. We train ensembles of online decision trees using a novel variant of the ID4 online decision-tree algorithm as the base learner, and show empirical results for both boosting and bagging-style online ensemble methods. Our results evaluate these methods on both our branch prediction domain and online variants of three familiar machine-learning benchmarks. Our data justifies three key claims. First, we show empirically that our extensions to ID4 significantly improve performance for single trees and additionally are critical to achieving performance gains in tree ensembles. Second, our results indicate significant improvements in predictive accuracy with ensemble size for the boosting-style algorithm. The bagging algorithms we tried showed poor performance relative to the boosting-style algorithm (but still improve upon individual base learners). Third, we show that ensembles of small trees are often able to outperform large single trees with the same number of nodes (and similarly outperform smaller ensembles of larger trees that use the same total number of nodes). This makes online boosting particularly useful in domains such as branch prediction with tight space restrictions (i.e., the available real-estate on a microprocessor chip).     

First order random forests: Learning relational classifiers with complex aggregates

In relational learning, predictions for an individual are based not only on its own properties but also on the properties of a set of related individuals. Relational classifiers differ with respect to how they handle these sets: some use properties of the set as a whole (using aggregation), some refer to properties of specific individuals of the set, however, most classifiers do not combine both. This imposes an undesirable bias on these learners. This article describes a learning approach that avoids this bias, using first order random forests. Essentially, an ensemble of decision trees is constructed in which tests are first order logic queries. These queries may contain aggregate functions, the argument of which may again be a first order logic query. The introduction of aggregate functions in first order logic, as well as upgrading the forest’s uniform feature sampling procedure to the space of first order logic, generates a number of complications. We address these and propose a solution for them. The resulting first order random forest induction algorithm has been implemented and integrated in the ACE-ilProlog system, and experimentally evaluated on a variety of datasets. The results indicate that first order random forests with complex aggregates are an efficient and effective approach towards learning relational classifiers that involve aggregates over complex selections. Editor: Rui Camacho     

Learning decision trees from decision rules: A method and initial results from a comparative study

A standard approach to determining decision trees is to learn them from examples. A disadvantage of this approach is that once a decision tree is learned, it is difficult to modify it to suit different decision making situations. Such problems arise, for example, when an attribute assigned to some node cannot be measured, or there is a significant change in the costs of measuring attributes or in the frequency distribution of events from different decision classes. An attractive approach to resolving this problem is to learn and store knowledge in the form of decision rules, and to generate from them, whenever needed, a decision tree that is most suitable in a given situation. An additional advantage of such an approach is that it facilitates buildingcompact decision trees, which can be much simpler than the logically equivalent conventional decision trees (by compact trees are meant decision trees that may contain branches assigned aset of values, and nodes assignedderived attributes, i.e., attributes that are logical or mathematical functions of the original ones). The paper describes an efficient method, AQDT-1, that takes decision rules generated by an AQ-type learning system (AQ15 or AQ17), and builds from them a decision tree optimizing a given optimality criterion. The method can work in two modes: thestandard mode, which produces conventional decision trees, andcompact mode, which produces compact decision trees. The preliminary experiments with AQDT-1 have shown that the decision trees generated by it from decision rules (conventional and compact) have outperformed those generated from examples by the well-known C4.5 program both in terms of their simplicity and their predictive accuracy.     

Decomposition-Fusion for Label Distribution Learning

Label Distribution Learning (LDL) is a general learning framework that assigns an instance to a distribution over a set of labels rather than to a single label or multiple labels. Current LDL methods have proven their effectiveness in many real-life machine learning applications. However, LDL is a generalization of the classification task and as such it is exposed to the same problems as standard classification algorithms, including class-imbalanced, noise, overlapping or irregularities. The purpose of this paper is to mitigate these effects by using decomposition strategies. The technique devised, called Decomposition-Fusion for LDL (DF-LDL), is based on one of the most renowned strategy in decomposition: the One-vs-One scheme, which we adapt to be able to deal with LDL datasets. In addition, we propose a competent fusion method that allows us to discard non-competent classifiers when their output is probably not of interest. The effectiveness of the proposed DF-LDL method is verified on several real-world LDL datasets on which we have carried out two types of experiments. First, comparing our proposal with the base learners and, second, comparing our proposal with the state-of-the-art LDL algorithms. DF-LDL shows significant improvements in both experiments.     

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.     

Stacking-based ensemble learning of decision trees for interpretable prostate cancer detection

Prostate cancer is a highly incident malignant cancer among men. Early detection of prostate cancer is necessary for deciding whether a patient should receive costly and invasive biopsy with possible serious complications. However, existing cancer diagnosis methods based on data mining only focus on diagnostic accuracy, while neglecting the interpretability of the diagnosis model that is necessary for helping doctors make clinical decisions. To take both accuracy and interpretability into consideration, we propose a stacking-based ensemble learning method that simultaneously constructs the diagnostic model and extracts interpretable diagnostic rules. For this purpose, a multi-objective optimization algorithm is devised to maximize the classification accuracy and minimize the ensemble complexity for model selection. As for model combination, a random forest classifier-based stacking technique is explored for the integration of base learners, i.e., decision trees. Empirical results on real-world data from the General Hospital of PLA demonstrate that the classification performance of the proposed method outperforms that of several state-of-the-art methods in terms of the classification accuracy, sensitivity and specificity. Moreover, the results reveal that several diagnostic rules extracted from the constructed ensemble learning model are accurate and interpretable.     

支持在线学习的增量式极端随机森林分类器

提出了一种增量式极端随机森林分类器(incremental extremely random forest,简称IERF),用于处理数据流,特别是小样本数据流的在线学习问题.IERF算法中新到达的样本将被存储到相应的叶节点,并通过Gini系数来确定是否对当前叶节点进行分裂扩展,在给定有限数量,甚至是少量样本的情况下,I...     

Structural diversity for decision tree ensemble learning

Decision trees are a kind of off-the-shelf predictive models, and they have been successfully used as the base learners in ensemble learning. To construct a strong classifier ensemble, the individual classifiers should be accurate and diverse. However, diversity measure remains a mystery although there were many attempts. We conjecture that a deficiency of previous diversity measures lies in the fact that they consider only behavioral diversity, i.e., how the classifiers behave when making predictions, neglecting the fact that classifiers may be potentially different even when they make the same predictions. Based on this recognition, in this paper, we advocate to consider structural diversity in addition to behavioral diversity, and propose the TMD (tree matching diversity) measure for decision trees. To investigate the usefulness of TMD, we empirically evaluate performances of selective ensemble approaches with decision forests by incorporating different diversity measures. Our results validate that by considering structural and behavioral diversities together, stronger ensembles can be constructed. This may raise a new direction to design better diversity measures and ensemble methods.     

Machine Learning for Intelligent Processing of Printed Documents

A paper document processing system is an information system component which transforms information on printed or handwritten documents into a computer-revisable form. In intelligent systems for paper document processing this information capture process is based on knowledge of the specific layout and logical structures of the documents. This article proposes the application of machine learning techniques to acquire the specific knowledge required by an intelligent document processing system, named WISDOM++, that manages printed documents, such as letters and journals. Knowledge is represented by means of decision trees and first-order rules automatically generated from a set of training documents. In particular, an incremental decision tree learning system is applied for the acquisition of decision trees used for the classification of segmented blocks, while a first-order learning system is applied for the induction of rules used for the layout-based classification and understanding of documents. Issues concerning the incremental induction of decision trees and the handling of both numeric and symbolic data in first-order rule learning are discussed, and the validity of the proposed solutions is empirically evaluated by processing a set of real printed documents.