Parallel rule induction with information theoretic pre-pruning

In a world where data is captured on a large scale the major challenge for data mining algorithms is to be able to scale up to large datasets. There are two main approaches to inducing classification rules, one is the divide and conquer approach, also known as the top down induction of decision trees; the other approach is called the separate and conquer approach. A considerable amount of work has been done on scaling up the divide and conquer approach. However, very little work has been conducted on scaling up the separate and conquer approach.In this work we describe a parallel framework that allows the parallelisation of a certain family of separate and conquer algorithms, the Prism family. Parallelisation helps the Prism family of algorithms to harvest additional computer resources in a network of computers in order to make the induction of classification rules scale better on large datasets. Our framework also incorporates a pre-pruning facility for parallel Prism algorithms.

Induction of modular classification rules: using Jmax-pruning

The Prism family of algorithms induces modular classification rules which, in contrast to decision tree induction algorithms, do not necessarily fit together into a decision tree structure. Classifiers induced by Prism algorithms achieve a comparable accuracy compared with decision trees and in some cases even outperform decision trees. Both kinds of algorithms tend to overfit on large and noisy datasets and this has led to the development of pruning methods. Pruning methods use various metrics to truncate decision trees or to eliminate whole rules or single rule terms from a Prism rule set. For decision trees many pre-pruning and postpruning methods exist, however for Prism algorithms only one pre-pruning method has been developed, J-pruning. Recent work with Prism algorithms examined J-pruning in the context of very large datasets and found that the current method does not use its full potential. This paper revisits the J-pruning method for the Prism family of algorithms and develops a new pruning method Jmax-pruning, discusses it in theoretical terms and evaluates it empirically.

Jmax-pruning: a facility for the information theoretic pruning of modular classification rules

The Prism family of algorithms induces modular classification rules in contrast to the Top Down Induction of Decision Trees (TDIDT) approach which induces classification rules in the intermediate form of a tree structure. Both approaches achieve a comparable classification accuracy. However in some cases Prism outperforms TDIDT. For both approaches pre-pruning facilities have been developed in order to prevent the induced classifiers from overfitting on noisy datasets, by cutting rule terms or whole rules or by truncating decision trees according to certain metrics. There have been many pre-pruning mechanisms developed for the TDIDT approach, but for the Prism family the only existing pre-pruning facility is J-pruning. J-pruning not only works on Prism algorithms but also on TDIDT. Although it has been shown that J-pruning produces good results, this work points out that J-pruning does not use its full potential. The original J-pruning facility is examined and the use of a new pre-pruning facility, called Jmax-pruning, is proposed and evaluated empirically. A possible pre-pruning facility for TDIDT based on Jmax-pruning is also discussed.

J-measure based hybrid pruning for complexity reduction in classification rules

Prism is a modular classification rule generation method based on the ‘separate and conquer’ approach that is alternative to the rule induction approach using decision trees also known as ‘divide and conquer’. Prism often achieves a similar level of classification accuracy compared with decision trees, but tends to produce a more compact noise tolerant set of classification rules. As with other classification rule generation methods, a principle problem arising with Prism is that of overfitting due to over-specialised rules. In addition, over-specialised rules increase the associated computational complexity. These problems can be solved by pruning methods. For the Prism method, two pruning algorithms have been introduced recently for reducing overfitting of classification rules - J-pruning and Jmax-pruning. Both algorithms are based on the J-measure, an information theoretic means for quantifying the theoretical information content of a rule. Jmax-pruning attempts to exploit the J-measure to its full potential because J-pruning does not actually achieve this and may even lead to underfitting. A series of experiments have proved that Jmax-pruning may outperform J-pruning in reducing overfitting. However, Jmax-pruning is computationally relatively expensive and may also lead to underfitting. This paper reviews the Prism method and the two existing pruning algorithms above. It also proposes a novel pruning algorithm called Jmid-pruning. The latter is based on the J-measure and it reduces overfitting to a similar level as the other two algorithms but is better in avoiding underfitting and unnecessary computational effort. The authors conduct an experimental study on the performance of the Jmid-pruning algorithm in terms of classification accuracy and computational efficiency. The algorithm is also evaluated comparatively with the J-pruning and Jmax-pruning algorithms.

Ineffectiveness of pruning to control citrus huanglongbing caused by Candidatus Liberibacter americanus

The huanglongbing (HLB) disease of citrus trees, caused by Candidatus Liberibacter asiaticus and Ca. Liberibacter americanus, was first reported in Brazil in March, 2004. The presence of the disease has caused serious concerns among growers. Pruning experiments were conducted to determine if removal of symptomatic branches or the entire canopy (decapitation) would eliminate infected tissues and save HLB-affected trees. Pruning was done in five blocks on a total of 592 3- to 16 year-old 'Valencia', 'Hamlin' or 'Pera' sweet orange trees showing no symptoms or with two levels of symptom severity. Ten decapitated trees per block were caged and all trees were treated with insecticides to control the psyllid vector, Diaphorina citri. Mottled leaves reappeared on most symptomatic (69.2%) as well on some asymptomatic (7.6%) pruned trees, regardless of age, variety, and pruning procedure. Presence of the pathogen (Ca. Liberibacter americanus) in all symptomatic trees was confirmed by PCR. In general, the greater the symptom severity before pruning the lower the percentage of trees that remained asymptomatic after pruning.

Prospects for the use of municipal tree pruning wastes in particleboard production

The purpose of this study was to evaluate the physical and mechanical properties of particleboard made with pruning wastes from Ipê (Tabebuia serratifolia) and Chapéu-de-Sol (Terminalia catappa) trees. Particleboards were prepared with both wood species, using all the material produced by grinding the pruning wastes. The particleboards had dimensions of 45×45 cm, a thickness of approximately 11.5 mm and an average density of 664 kg/m3. A urea-formaldehyde adhesive was used in the proportion of 12% of the dry particle mass. The particleboards were pressed at a temperature of 130 C for 10 mins. The physical and mechanical properties analyzed were density, moisture content, thickness swelling, percentage of lignin and cellulose, modulus of resilience, modulus of elasticity and tensile strength parallel to the grain, accordingly to the standards NBR 14810 and CS 236-66 (1968). The particleboards were considered to be of medium density. The particle size significantly affected the static bending strength and tensile strength parallel to the grain. Ipê presented better results, demonstrating a potential for the production and use of particleboard made from this species. © The Author(s) 2013.

Agronomic performance of peach trees grown in subtropical region

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

EC78-1737 Broadleaf Trees for Nebraska

This extension circular shows and describes broadleaf trees that will grow in Nebraska. It should prove valuable when selecting a tree best suited for a specific area and purpose. Most of this publication is devoted to detailed descriptions of tree species. In addition, the main points of tree placement, tree planting and tree care are discussed.

Recognition on Finite Set of Events: Bayesian Analysis of Generalization Ability and Classification Tree Pruning

The problem of recognition on finite set of events is considered. The generalization ability of classifiers for this problem is studied within the Bayesian approach. The method for non-uniform prior distribution specification on recognition tasks is suggested. It takes into account the assumed degree of intersection between classes. The results of the analysis are applied for pruning of classification trees.

A model of macadamia with application to pruning in orchards

A self-organising model of macadamia, expressed using L-Systems, was used to explore aspects of canopy management. A small set of parameters control the basic architecture of the model, with a high degree of self-organisation occurring to determine the fate and growth of buds. Light was sensed at the leaf level and used to represent vigour and accumulated basipetally. Buds also sensed light so as to provide demand in the subsequent redistribution of the vigour. Empirical relationships were derived from a set of 24 completely digitised trees after conversion to multiscale tree graphs (MTG) and analysis with the OpenAlea software library. The ability to write MTG files was embedded within the model so that various tree statistics could be exported for each run of the model. To explore the parameter space a series of runs was completed using a high-throughput computing platform. When combined with MTG generation and analysis with OpenAlea it provided a convenient way in which thousands of simulations could be explored. We allowed the model trees to develop using self-organisation and simulated cultural practices such as hedging, topping, removal of the leader and limb removal within a small representation of an orchard. The model provides insight into the impact of these practices on potential for growth and the light distribution within the canopy and to the orchard floor by coupling the model with a path-tracing program to simulate the light environment. The lessons learnt from this will be applied to other evergreen, tropical fruit and nut trees.

WOOD DENSITY VARIATION AND TREE RING DEMARCATION IN Gmelina arborea TREES USING X-RAY DENSITOMETRY

Due to its relationship with other properties, wood density is the main wood quality parameter. Modern, accurate methods - such as X-ray densitometry - are applied to determine the spatial distribution of density in wood sections and to evaluate wood quality. The objectives of this study were to determinate the influence of growing conditions on wood density variation and tree ring demarcation of gmelina trees from fast growing plantations in Costa Rica. The wood density was determined by X-ray densitometry method. Wood samples were cut from gmelina trees and were exposed to low X-rays. The radiographic films were developed and scanned using a 256 gray scale with 1000 dpi resolution and the wood density was determined by CRAD and CERD software. The results showed tree-ring boundaries were distinctly delimited in trees growing in site with rainfall lower than 25 10 mm/year. It was demonstrated that tree age, climatic conditions and management of plantation affects wood density and its variability. The specific effect of variables on wood density was quantified by for multiple regression method. It was determined that tree year explained 25.8% of the total variation of density and 19.9% were caused by climatic condition where the tree growing. Wood density was less affected by the intensity of forest management with 5.9% of total variation.

Variation in the wood anatomical structure of Gmelina arborea (Verbenaceae) trees at different ecological conditions in Costa Rica

The tree Gmelina arborea has been widely introduced in Costa Rica for commercial purposes. This new conditions for melina cause variations on anatomy in secondary xylem of the trees growing in plantations. The objective of the present research was to determine the variation in the anatomy of xylem caused by the ecological conduction variation. Dimensions of fiber, axial parenchyma percentage of cross sections, parameters of vessels and the ray were measured. The results showed that some anatomical characteristics remained stable despite variations of ecological conditions, especially radial parenchyma and anatomical features which were less affected by the altitude. On the other hand, the vessels, axial parenchyma and fiber were less stable because they were affected significantly by the longitude, latitude, altitude and precipitation. Latitude significantly affected vessel percentage, length and diameter of the fiber and lumen. Longitude affected vessel percentage and fiber diameter. Altitude had a significant correlation with the amount of cells at my height. Annual average precipitation affected vessel percentage and diameter, not only of the fiber, but also of the lumen. These results suggest that the new growth conditions of G. arborea trees in Costa Rica have produced an anatomic adaptation.

INFLUENCE OF ALTITUDE, AGE AND DIAMETER ON YIELD AND ALPHA-BISABOLOL CONTENT OF CANDEIA TREES (Eremanthus erythropappus)

The heartwood of candeia tree is a source of essential oil rich in alpha-bisabolol, a substance widely used in the cosmetic and pharmaceutical industry. Bearing in mind the economic importance of alpha-bisabolol, this work aimed to evaluate the influence of tree age on the yield and content of alpha-bisabolol present in essential oil from candeia, considering two distinct reliefs and three diameter classes, in Aiuruoca region, south Minas Gerais state. The two distinct reliefs correspond respectively to one section of the stand growing at 1,000m of altitude (Area 1) and another section growing at 1,100m of altitude (Area 2). In each section, 15 trees were felled from among 3 different diameter classes. Discs were removed from the base of each tree to estimate their age by doing growth ring count. Soil samples were taken and Subjected to physical and chemical analysis. The logs were reduced into chips and random samples were taken for distillation to extract essential oil. The method used was steam distillation at a pressure of 2 kgf/cm(2)/2.5 h. The chemical analysis was performed in a gas chromatograph (GC) based on the alpha-bisabolol standard reference. The yield of essential oil from trees in Area I was higher than that from trees in Area 2, with the same pattern of influence for older trees. In Area 2, the alpha-bisabolol content was higher in younger trees. No differences were found between the relevant parameters in relation to diameter classes.

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

The Lobel-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k is an element of N, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars. Our result implies a bound on the Ramsey number r( T, T') of trees T, T' from the above classes.