Decision Rules Derived from Optimal Decision Trees with Hypotheses

Conventional decision trees use queries each of which is based on one attribute. In this study, we also examine decision trees that handle additional queries based on hypotheses. This kind of query is similar to the equivalence queries considered in exact learning. Earlier, we designed dynamic programming algorithms for the computation of the minimum depth and the minimum number of internal nodes in decision trees that have hypotheses. Modification of these algorithms considered in the present paper permits us to build decision trees with hypotheses that are optimal relative to the depth or relative to the number of the internal nodes. We compare the length and coverage of decision rules extracted from optimal decision trees with hypotheses and decision rules extracted from optimal conventional decision trees to choose the ones that are preferable as a tool for the representation of information. To this end, we conduct computer experiments on various decision tables from the UCI Machine Learning Repository. In addition, we also consider decision tables for randomly generated Boolean functions. The collected results show that the decision rules derived from decision trees with hypotheses in many cases are better than the rules extracted from conventional decision trees.     

The Computational Complexity of Sandpiles

Journal of Statistical Physics - Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d≥3, we...     

Entropy-Based Greedy Algorithm for Decision Trees Using Hypotheses

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses of values of all attributes. Such decision trees are similar to those studied in exact learning, where membership and equivalence queries are allowed. We present greedy algorithm based on entropy for the construction of the above decision trees and discuss the results of computer experiments on various data sets and randomly generated Boolean functions.     

Computational Creativity and Aesthetics with Algorithmic Information Theory

We build an analysis based on the Algorithmic Information Theory of computational creativity and extend it to revisit computational aesthetics, thereby, improving on the existing efforts of its formulation. We discuss Kolmogorov complexity, models and randomness deficiency (which is a measure of how much a model falls short of capturing the regularities in an artifact) and show that the notions of typicality and novelty of a creative artifact follow naturally from such definitions. Other exciting formalizations of aesthetic measures include logical depth and sophistication with which we can define, respectively, the value and creator’s artistry present in a creative work. We then look at some related research that combines information theory and creativity and analyze them with the algorithmic tools that we develop throughout the paper. Finally, we assemble the ideas and their algorithmic counterparts to complete an algorithmic information theoretic recipe for computational creativity and aesthetics.     

Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity

The computational complexity of internal diffusion-limited aggregation (DLA) is examined from both a theoretical and a practical point of view. We show that for two or more dimensions, the problem of predicting the cluster from a given set of paths is complete for the complexity class CC, the subset of P characterized by circuits composed of comparator gates. CC-completeness is believed to imply that, in the worst case, growing a cluster of size n requires polynomial time in n even on a parallel computer. A parallel relaxation algorithm is presented that uses the fact that clusters are nearly spherical to guess the cluster from a given set of paths, and then corrects defects in the guessed cluster through a nonlocal annihilation process. The parallel running time of the relaxation algorithm for two-dimensional internal DLA is studied by simulating it on a serial computer. The numerical results are compatible with a running time that is either polylogarithmic in n or a small power of n. Thus the computational resources needed to grow large clusters are significantly less on average than the worst-case analysis would suggest. For a parallel machine with k processors, we show that random clusters in d dimensions can be generated in ((n/k+logk)n ^2/d ) steps. This is a significant speedup over explicit sequential simulation, which takes (n ^1+2/d ) time on average. Finally, we show that in one dimension internal DLA can be predicted in (logn) parallel time, and so is in the complexity class NC.     

Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis

Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists. The Kolmogorov complexity is known as one of the most important tools to measure the complexity of an object. We formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with O(1) Kolmogorov complexity, were identified. These graphs were then used to develop a method to estimate the complexity of a given graph. The proposed method utilizes the simple structures within a graph to capture its non-randomness. This method is able to capture features that make a network closer to the more non-random end of the spectrum. The resulting algorithm takes a graph as an input and outputs an upper bound to its Kolmogorov complexity. This could be applicable in, for example evaluating the performances of graph compression methods.     

二元决策图和故障树相融合的无线传感器网络可靠性分析

为了提高无线传感器分析网络可靠性,提出一种基于二元决策图和故障树相融合的无线传感器网络可靠分析方法;首先根据无线传感器网络拓扑结构建立了故障树模型,然后将无线传感器网络故障树转化为二元决策图结构,最后采用仿真实验分析了不同节点冗余度、不同跳数条件下无线传感器网络的可靠性;仿真结果表明,文章方法的分析结果可以帮助无线传感器网络性能的优化,可以提高无线传感器网络的可靠性。     

数字高速分幅相机中光学分幅系统的设计与分析

使用光学辅助设计软件ZEMAX设计了用于四通道数字高速分幅相机的光学分幅系统,并结合机械设计软件SOLIDWORKS,在ZEMAX的非序列模式下建立了光学分幅系统的三维立体仿真模型。成像质量达到了衍射极限,动态极限空间分辨率为16lp／mm。模拟分析结果表明成像质量理想,符合设计要求。     

双向分束角对称的偏光分束镜设计与性能分析

为了获得分束角对称的偏光分束棱镜,在双Wollaston棱镜结构的基础上,通过合理设计棱镜左右两端晶体光轴的取向,使棱镜整体呈中心切面对称;在保证对正向入射的光对称分束的同时,对反向入射光同样可以对称分束,达到了双向对称分束的目的;在此基础上给出了晶体光轴的旋转角δ与棱镜结构角S以及与波长的关系;并分析了对633 nm设计的棱镜用于其他波长时分束角的对称性.结果表明：在±300 nm的光谱范围内,分束角的不对称度均小于0.24°.     

基于区域分解和逐级光线分裂的杂散光分析

针对蒙特卡罗法运算量大的问题,通过引入区域分解和逐级光线分裂技术,减少杂散光线与表面交点求解时所涉及的表面数及跟踪光线数,降低计算量.区域分解时,考虑子区域与表面数的匹配关系;并基于杂散光传播过程的模拟信息,逐级确定光线分裂倍数.以大衰减比抑制结构和多传感器系统为例,进行杂散光分析.结果表明,对复杂系统杂散光传播的蒙特卡罗法模拟,应用区域分解和逐级光线分裂技术,可以在保持计算精度的前提下,有效地提高计算效率.     

多群辐射扩散方程组的分裂迭代算法收敛分析

分析了多群辐射扩散方程组的分裂迭代算法的收敛速度,证明其收敛特性,给出迭代矩阵谱半径的解析公式.对谱半径进行数值计算与分析,揭示算法的收敛速度与辐射系数之间的依赖关系,数值算例验证了理论结果,给出了该算法的适用条件.     

Multiscale Analysis of Runoff Complexity in the Yanhe Watershed

Runoff complexity is an important indicator reflecting the sustainability of a watershed ecosystem. In order to explore the multiscale characteristics of runoff complexity and analyze its variation and influencing factors in the Yanhe watershed in China during the period 1991–2020, we established a new analysis method for watershed runoff complexity based on the complete ensemble empirical mode decomposition with adaptive noise (CEEMDAN) method for the decomposition of multiscale characteristics and the refined composite multiscale entropy (RCMSE) method for the quantification of the system complexity. The results show that runoff and its components all present multiscale complexity characteristics that are different from random signals, and the intermediate frequency modes contribute the most to runoff complexity. The runoff complexity of the Yanhe watershed has decreased gradually since 1991, and 2010 was a turning point of runoff complexity, when it changed from a decline to an increase, indicating that the ecological sustainability of this basin has improved since 2010, which was mainly related to the ecological restoration measures of the Grain for Green Project. This study expands the research perspective for analyzing the variation characteristics of runoff at the multiscale, and provides a reference for the study of watershed ecological sustainability and ecological management.     

单模光纤中光脉冲对的聚合与分裂

对于双光脉冲在非线性单模光纤中传输问题,通过数值求解非线性Schrdinger方程,发现脉冲的分裂、聚合现象.讨论了不同入射光强度下,分裂、聚合的特点,以及产生分裂、聚合的物理机制.对聚合后光脉冲的频谱进行了分析,除了观察到与入射脉冲相同的中心频带外,还存在两个频带较宽的边带.     

New Classification Method for Independent Data Sources Using Pawlak Conflict Model and Decision Trees

The research concerns data collected in independent sets—more specifically, in local decision tables. A possible approach to managing these data is to build local classifiers based on each table individually. In the literature, many approaches toward combining the final prediction results of independent classifiers can be found, but insufficient efforts have been made on the study of tables’ cooperation and coalitions’ formation. The importance of such an approach was expected on two levels. First, the impact on the quality of classification—the ability to build combined classifiers for coalitions of tables should allow for the learning of more generalized concepts. In turn, this should have an impact on the quality of classification of new objects. Second, combining tables into coalitions will result in reduced computational complexity—a reduced number of classifiers will be built. The paper proposes a new method for creating coalitions of local tables and generating an aggregated classifier for each coalition. Coalitions are generated by determining certain characteristics of attribute values occurring in local tables and applying the Pawlak conflict analysis model. In the study, the classification and regression trees with Gini index are built based on the aggregated table for one coalition. The system bears a hierarchical structure, as in the next stage the decisions generated by the classifiers for coalitions are aggregated using majority voting. The classification quality of the proposed system was compared with an approach that does not use local data cooperation and coalition creation. The structure of the system is parallel and decision trees are built independently for local tables. In the paper, it was shown that the proposed approach provides a significant improvement in classification quality and execution time. The Wilcoxon test confirmed that differences in accuracy rate of the results obtained for the proposed method and results obtained without coalitions are significant, with a p level = 0.005. The average accuracy rate values obtained for the proposed approach and the approach without coalitions are, respectively: 0.847 and 0.812; so the difference is quite large. Moreover, the algorithm implementing the proposed approach performed up to 21-times faster than the algorithm implementing the approach without using coalitions.     

数据挖掘在肺结核疾病智能决策中的应用研究

针对单一数据挖掘方法对肺结核疾病诊断效率低、准确性不高的问题,本研究对北京市昌平区结核病防治所,北京市结核病控制研究所的1203例肺结核病人档案资料构建了电子档案,采用粗糙集和决策树结合方法建立肺结核疾病诊断模型,并对其准确性进行评估,在此基础上构建肺结核疾病诊断系统。在研究中,使用粗糙集和决策树相结合的方法进行属性约简,约简掉冗余属性57个,剩余属性22个,得到决策规则7条,模型准确率为83.46%。与未未约简的方法相比,决策规则减少128%,模型准确率基本保持不变。研究结果表明：使用该组合算法,在保证模型准确率的同时,降低了算法的时间和空间复杂性,提高了挖掘效率,为临床诊断提供了一定的借鉴。     

A Hyperspectral Image Classification Approach Based on Feature Fusion and Multi-Layered Gradient Boosting Decision Trees

At present, many Deep Neural Network (DNN) methods have been widely used for hyperspectral image classification. Promising classification results have been obtained by utilizing such models. However, due to the complexity and depth of the model, increasing the number of model parameters may lead to an overfitting of the model, especially when training data are insufficient. As the performance of the model mainly depends on sufficient data and a large network with reasonably optimized hyperparameters, using DNNs for classification requires better hardware conditions and sufficient training time. This paper proposes a feature fusion and multi-layered gradient boosting decision tree model (FF-DT) for hyperspectral image classification. First, we fuse extended morphology profiles (EMPs), linear multi-scale spatial characteristics, and nonlinear multi-scale spatial characteristics as final features to extract both special and spectral features. Furthermore, a multi-layered gradient boosting decision tree model is constructed for classification. We conduct experiments based on three datasets, which in this paper are referred to as the Pavia University, Indiana Pines, and Salinas datasets. It is shown that the proposed FF-DT achieves better performance in classification accuracy, training conditions, and time consumption than other current classical hyperspectral image classification methods.     

双沃拉斯顿棱镜光强分束比精确分析

利用折射定律,介质膜两侧折射率不同时多光束干涉理论和菲涅耳公式,精确推导了双沃拉斯顿棱镜的光强分束比的具体表达式。以公式为基础,通过Matlab软件数值模拟作图分析光强分束比随入射角、入射波长和结构角的变化关系曲线。结果表明:在棱镜为介质胶合型时,光强分束比随入射角和入射波长的变化很小,光强分束比基本为1;棱镜为空气胶合型时,光强分束比随入射角,结构角和波长的变化很大。两种情况下,光强分束比随各参量的变化基本呈周期性变化。