Generating binary trees lexicographically /

Bibliography: p. 26.

Two upper bounds for the weighted path length of binary trees.

Thesis (M.S.)--University of Illinois at Urbana-Champaign.

Differential Balanced Trees and (0,1) Matrices

* The research was supported by INTAS 00-397 and 00-626 Projects.

Bounding right-arm rotation distances

Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

Evaluating genetic algorithms with different population structures on a lot sizing and scheduling problem

This paper studies the use of different population structures in a Genetic Algorithm (GA) applied to lot sizing and scheduling problems. The population approaches are divided into two types: single-population and multi-population. The first type has a non-structured single population. The multi-population type presents non-structured and structured populations organized in binary and ternary trees. Each population approach is tested on lot sizing and scheduling problems found in soft drink companies. These problems have two interdependent levels with decisions concerning raw material storage and soft drink bottling. The challenge is to simultaneously determine the lot sizing and scheduling of raw materials in tanks and products in lines. Computational results are reported allowing determining the better population structure for the set of problem instances evaluated. Copyright 2008 ACM.

Irreducibility of Random Hilbert Schemes

We prove that a random Hilbert scheme that parametrizes the closed subschemes with a fixed Hilbert polynomial in some projective space is irreducible and nonsingular with probability greater than $0.5$. To consider the set of nonempty Hilbert schemes as a probability space, we transform this set into a disjoint union of infinite binary trees, reinterpreting Macaulay's classification of admissible Hilbert polynomials. Choosing discrete probability distributions with infinite support on the trees establishes our notion of random Hilbert schemes. To bound the probability that random Hilbert schemes are irreducible and nonsingular, we show that at least half of the vertices in the binary trees correspond to Hilbert schemes with unique Borel-fixed points.

Using Sensitivity as a Method for Ranking the Test Cases Classified by Binary Decision Trees

Usually, data mining projects that are based on decision trees for classifying test cases will use the probabilities provided by these decision trees for ranking classified test cases. We have a need for a better method for ranking test cases that have already been classified by a binary decision tree because these probabilities are not always accurate and reliable enough. A reason for this is that the probability estimates computed by existing decision tree algorithms are always the same for all the different cases in a particular leaf of the decision tree. This is only one reason why the probability estimates given by decision tree algorithms can not be used as an accurate means of deciding if a test case has been correctly classified. Isabelle Alvarez has proposed a new method that could be used to rank the test cases that were classified by a binary decision tree [Alvarez, 2004]. In this paper we will give the results of a comparison of different ranking methods that are based on the probability estimate, the sensitivity of a particular case or both.

Spatial pattern of black spot incidence within citrus trees related to disease severity and pathogen dispersal

Guignardia citricarpa, the causal agent of citrus black spot, forms airborne ascospores on decomposing citrus leaves and water-spread conidia on fruits, leaves and twigs. The spatial pattern of diseased fruit in citrus tree canopies was used to assess the importance of ascospores and conidia in citrus black spot epidemics in Sao Paulo State, Brazil. The aggregation of diseased fruit in the citrus tree canopy was quantified by the binomial dispersion index (D) and the binary form of Taylor`s Power Law for 303 trees in six groves. D was significantly greater than 1 in 251 trees. The intercept of the regression line of Taylor`s Power Law was significantly greater than 0 and the slope was not different from 1, implying that diseased fruit was aggregated in the canopy independent of disease incidence. Disease incidence (p) and severity (S) were assessed in 2875 citrus trees. The incidence-severity relationship was described (R-2 = 88.7%) by the model ln(S) = ln(a) + bCLL(p) where CLL = complementary log-log transformation. The high severity at low incidence observed in many cases is also indicative of low distance spread of G. citricarpa spores. For the same level of disease incidence, some trees had most of the diseased fruit with many lesions and high disease severity, whereas other trees had most of the fruit with few lesions and low disease severity. Aggregation of diseased fruit in the trees suggests that splash-dispersed conidia have an important role in increasing the disease in citrus trees in Brazil.

Binary classification of dyslipidemia from the waist-to-hip ratio and body mass index: a comparison of linear, logistic, and CART models.

BACKGROUND: We sought to improve upon previously published statistical modeling strategies for binary classification of dyslipidemia for general population screening purposes based on the waist-to-hip circumference ratio and body mass index anthropometric measurements. METHODS: Study subjects were participants in WHO-MONICA population-based surveys conducted in two Swiss regions. Outcome variables were based on the total serum cholesterol to high density lipoprotein cholesterol ratio. The other potential predictor variables were gender, age, current cigarette smoking, and hypertension. The models investigated were: (i) linear regression; (ii) logistic classification; (iii) regression trees; (iv) classification trees (iii and iv are collectively known as "CART"). Binary classification performance of the region-specific models was externally validated by classifying the subjects from the other region. RESULTS: Waist-to-hip circumference ratio and body mass index remained modest predictors of dyslipidemia. Correct classification rates for all models were 60-80%, with marked gender differences. Gender-specific models provided only small gains in classification. The external validations provided assurance about the stability of the models. CONCLUSIONS: There were no striking differences between either the algebraic (i, ii) vs. non-algebraic (iii, iv), or the regression (i, iii) vs. classification (ii, iv) modeling approaches. Anticipated advantages of the CART vs. simple additive linear and logistic models were less than expected in this particular application with a relatively small set of predictor variables. CART models may be more useful when considering main effects and interactions between larger sets of predictor variables.

Fiedler trees for multiscale surface analysis

In this work we introduce a new hierarchical surface decomposition method for multiscale analysis of surface meshes. In contrast to other multiresolution methods, our approach relies on spectral properties of the surface to build a binary hierarchical decomposition. Namely, we utilize the first nontrivial eigenfunction of the Laplace-Beltrami operator to recursively decompose the surface. For this reason we coin our surface decomposition the Fiedler tree. Using the Fiedler tree ensures a number of attractive properties, including: mesh-independent decomposition, well-formed and nearly equi-areal surface patches, and noise robustness. We show how the evenly distributed patches can be exploited for generating multiresolution high quality uniform meshes. Additionally, our decomposition permits a natural means for carrying out wavelet methods, resulting in an intuitive method for producing feature-sensitive meshes at multiple scales. Published by Elsevier Ltd.

Predictive models for chronic renal disease using decision trees, naïve bayes and case-based methods

Data mining can be used in healthcare industry to “mine” clinical data to discover hidden information for intelligent and affective decision making. Discovery of hidden patterns and relationships often goes intact, yet advanced data mining techniques can be helpful as remedy to this scenario. This thesis mainly deals with Intelligent Prediction of Chronic Renal Disease (IPCRD). Data covers blood, urine test, and external symptoms applied to predict chronic renal disease. Data from the database is initially transformed to Weka (3.6) and Chi-Square method is used for features section. After normalizing data, three classifiers were applied and efficiency of output is evaluated. Mainly, three classifiers are analyzed: Decision Tree, Naïve Bayes, K-Nearest Neighbour algorithm. Results show that each technique has its unique strength in realizing the objectives of the defined mining goals. Efficiency of Decision Tree and KNN was almost same but Naïve Bayes proved a comparative edge over others. Further sensitivity and specificity tests are used as statistical measures to examine the performance of a binary classification. Sensitivity (also called recall rate in some fields) measures the proportion of actual positives which are correctly identified while Specificity measures the proportion of negatives which are correctly identified. CRISP-DM methodology is applied to build the mining models. It consists of six major phases: business understanding, data understanding, data preparation, modeling, evaluation, and deployment.

Incorporating label dependency into the binary relevance framework for multi-label classification

In multi-label classification, examples can be associated with multiple labels simultaneously. The task of learning from multi-label data can be addressed by methods that transform the multi-label classification problem into several single-label classification problems. The binary relevance approach is one of these methods, where the multi-label learning task is decomposed into several independent binary classification problems, one for each label in the set of labels, and the final labels for each example are determined by aggregating the predictions from all binary classifiers. However, this approach fails to consider any dependency among the labels. Aiming to accurately predict label combinations, in this paper we propose a simple approach that enables the binary classifiers to discover existing label dependency by themselves. An experimental study using decision trees, a kernel method as well as Naive Bayes as base-learning techniques shows the potential of the proposed approach to improve the multi-label classification performance.

Reliability measures for local nodes assessment in classification trees

Most of the modem developments with classification trees are aimed at improving their predictive capacity. This article considers a curiously neglected aspect of classification trees, namely the reliability of predictions that come from a given classification tree. In the sense that a node of a tree represents a point in the predictor space in the limit, the aim of this article is the development of localized assessment of the reliability of prediction rules. A classification tree may be used either to provide a probability forecast, where for each node the membership probabilities for each class constitutes the prediction, or a true classification where each new observation is predictively assigned to a unique class. Correspondingly, two types of reliability measure will be derived-namely, prediction reliability and classification reliability. We use bootstrapping methods as the main tool to construct these measures. We also provide a suite of graphical displays by which they may be easily appreciated. In addition to providing some estimate of the reliability of specific forecasts of each type, these measures can also be used to guide future data collection to improve the effectiveness of the tree model. The motivating example we give has a binary response, namely the presence or absence of a species of Eucalypt, Eucalyptus cloeziana, at a given sampling location in response to a suite of environmental covariates, (although the methods are not restricted to binary response data).

Modelling predicts positive and negative interactions between three Australian tropical tree species in monoculture and binary mixture

Computer modelling promises to. be an important tool for analysing and predicting interactions between trees within mixed species forest plantations. This study explored the use of an individual-based mechanistic model as a predictive tool for designing mixed species plantations of Australian tropical trees. The 'spatially explicit individually based-forest simulator' (SeXI-FS) modelling system was used to describe the spatial interaction of individual tree crowns within a binary mixed-species experiment. The three-dimensional model was developed and verified with field data from three forest tree species grown in tropical Australia. The model predicted the interactions within monocultures and binary mixtures of Flindersia brayleyana, Eucalyptus pellita and Elaeocarpus grandis, accounting for an average of 42% of the growth variation exhibited by species in different treatments. The model requires only structural dimensions and shade tolerance as species parameters. By modelling interactions in existing tree mixtures, the model predicted both increases and reductions in the growth of mixtures (up to +/- 50% of stem volume at 7 years) compared to monocultures. This modelling approach may be useful for designing mixed tree plantations. (c) 2006 Published by Elsevier B.V.

Pulsar binary systems in a nonsymmetric theory of gravitation II. Dipole radiation

This paper deals with the emission of gravitational radiation in the context of a previously studied metric nonsymmetric theory of gravitation. The part coming from the symmetric part of the metric coincides with the mass quadrupole moment result of general relativity. The one associated to the antisymmetric part of the metric involves the dipole moment of the fermionic charge of the system. The results are applied to binary star systems and the decrease of the period of the elliptical motion is calculated.