WWW.DISSERS.RU


...
    !

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 54 |

Results and Conclusions A radial basis function neural network has been trained with a few patterns in order to forecast the volume of wood in a given forest area. The network performs a clustering process of the trees using different input variables. A sensitive analysis can be computed observing the weight of unsupervised synapse. To achieve a valid forecasting stage a previous classification must be performed. Let xij data corresponding to the matrix in the training process, where i = number of input variables and j = number of hidden neurons, then the following constraint must be verified j i +1: it is needed that the number of hidden neurons must be greater than the number of input variables to perform a correct learning. A previous clustering process of input data permits a better forecasting process in the output variable, in our case the amount of volume of wood in a forest area.

These results improve commercial and classical forecasting methods in forest inventories, and proposed method can be applied to any tree specie or forest area without taking into account environment variables that appears in classical mathematical equations. As the number of classes that needs to be discriminated decreases, classifier accuracy increases; until obtain the real number of classes. Once the correct number of classes has been obtained using the RBF and with a supervised learning the volume of wood for a forest inventory can be estimated.

Bibliography [Fritzke 1994] Fritzke B. Supervised learning wiht growing cell structures. Advances in neural information processing system 6, Pp. 25. Morgan Kaufmann Publishers 1994.

[Hamilton, F. and Brack, C.L. 1999] Hamilton, F. and Brack, C.L. 1999. Stand volume estimates for modelling inventory data.

Australian Forestry 62(4): 360 - [Kphonen 1989] Kohonen T. Self organization and associative memory. Springer-Verlag [Moody and Darken, 1989] Moody J., Darken C. Fast learning in networks of locally-tunned processing units. Neural computation, vil1, pp 281-294. 1989.

[Poggio and Girosi, 1990] Poggio T. and Girossi F. Networks for approximation and learning. IN procceding of the IEEE, volume 78, pages 1481-1497.

[Schreuder, H.T., Gregoire, T.G. and Word, G.B. 1993] Schreuder, H.T., Gregoire, T.G. and Wood, G.B. 1993. Sampling Methods for Multiresource Forest Inventory. John Wiley and Sons, Inc. New York.

Authors' Information Angel Castellanos Dpto. de Ciencias Basicas aplicadas, a la Ingeniera Forestal. Escuela Univ. de Ingeniera Tcnica Forestal. Universidad Politcnica de Madrid, Avda. de Ramiro de Maeztu s/n Madrid 28040, Spain;

e-mail: acaste@forestales.upm.es Ana Martinez Blanco Dpto. de Ciencias Basicas aplicadas, a la Ingeniera Forestal. Escuela Univ. de Ingeniera Tcnica Forestal. Universidad Politcnica de Madrid, Avda. de Ramiro de Maeztu s/n Madrid 28040, Spain; e-mail: amartinez@forestales.upm.es Valentin Palencia Dpto. de Arquitectura y Tecnologa de Sistemas Informticos. Facultad de Informtica.

Universidad Politcnica de Madrid, Campus de Montegancedo. Madrid 28660, Spain;

e-mail: vpalencia@fi.upm.es Knowledge Engineering DECISION TREES FOR APPLICABILITY OF EVOLUTION RULES IN TRANSITION P SYSTEMS Luis Fernandez, Fernando Arroyo, Ivan Garcia, Gines Bravo Abstract: Transition P Systems are a parallel and distributed computational model based on the notion of the cellular membrane structure. Each membrane determines a region that encloses a multiset of objects and evolution rules. Transition P Systems evolve through transitions between two consecutive configurations that are determined by the membrane structure and multisets present inside membranes. Moreover, transitions between two consecutive configurations are provided by an exhaustive non-deterministic and parallel application of active evolution rules subset inside each membrane of the P system. But, to establish the active evolution rules subset, it is required the previous calculation of useful and applicable rules. Hence, computation of applicable evolution rules subset is critical for the whole evolution process efficiency, because it is performed in parallel inside each membrane in every evolution step. The work presented here shows advantages of incorporating decision trees in the evolution rules applicability algorithm. In order to it, necessary formalizations will be presented to consider this as a classification problem, the method to obtain the necessary decision tree automatically generated and the new algorithm for applicability based on it.

Keywords: Decision Tree, ID3, Evolution Rules, Applicability, Transition P System.

ACM Classification Keywords: I.2.6 Learning Decision Tree; D.1.m Miscellaneous Natural Computing Introduction Membrane computing is a new computational model based on the membrane structure of living cells [Pun, 1998]. This model has become, during last years, a powerful framework for developing new ideas in theoretical computation. Main idea was settled in the base of connecting the Biology with Computer Science in order to develop new computational paradigms.

An overview of membrane computing software can be found in literature, or tentative for hardware implementations [Fernndez, 2005], or even in local networks is enough to understand how difficult is to implement membrane systems on digital devices [Pun, 2005].

Transition P Systems evolve through transitions between two consecutive configurations that are determined by the membrane structure and multisets present inside membranes. Moreover, transitions between two consecutive configurations are provided by an exhaustive non-deterministic and parallel application of an evolution rules subset inside each membrane of the P system. Evolution rules subset we are studding here will be composed by applicable rules. Moreover, It exist algorithms of application for evolution rules [Fernndez, 2006] that, recurrently to its end, need the computation of applicable evolution rules subset. Hence, computing applicable evolution rules is critical for the whole evolution process efficiency, because it is performed in parallel inside each membrane in each one of the evolution steps.

At the present time, computation of applicable evolution rules subset falls on redundancies in a directly or indirectly way. Incorporating decision trees in this computation avoids these redundancies and improves global efficiency of P system evolution.

This work is structured as follows: firstly, evolution rules applicability over a multiset of objects problem is formalized together with its corresponding traditional algorithm. Following section, briefly describes essential elements of decision trees. Afterwards, they are presented new formalizations that permit considering applicability problem as a classification problem solvable through decision trees. In next section, it is presented the algorithm based on decision trees. Finally, efficiency between both algorithms is compared and we expose our conclusions.

Fourth International Conference I.TECH 2006 Applicability of Evolution Rules This section defines concepts about multisets, evolution rules and applicability which are needed to follow the developed work presented here. Moreover, it is presented the traditional algorithm, without decision trees, for applicability evolution rules on multisets and its complexity.

From now on, let U be a finite and not empty set of symbols with| U |= m.

Let be a multiset overU, where is a mapping from U to N. Hence, (u) = p /u U ! p N.

Let us present the set of all multisets as M(U) = { / is a multiset}.

Weight of a symbol u U is defined over a multiset M(U) as(u) and it is represented by | |u.

Inclusion of multiset is a binary relation defined as1 2 | 1 |u | 2 |u, u U 1,2 M(U).

Any M(U) can be represented as the m-tuple of natural number by the Parikh vector associated to the multiset w with respect to U. The problem is that the Parikh vector representation depends on the order of the elements of U. To avoid this problem, an order over the set U is defined as an ordered succession of symbols through a one to one mapping from {1..m} to U that is:

1. i {1,...,m} u U / (i) = u 2. u U i {1,...,m}/ (i) = u 3. i, j {1,...,m}/ (i) = ( j) i = j m This fact permits us to represent every M(U) as an element of N in a congruent manner. Hence, m = ( p1,..., pm) N / | |u = p(u) u U.

On the other hand, let T be a finite and non empty set of targets.

Evolution rule with symbols in U and targets in T is defined by r = (a,c, ) where a M(U), c M (U x T) and {dissolve, not dissolve}. The set of evolution rules is defined as R(U,T) = {r / r is a evolution rule}.

Antecedent of r = (a,c, ) R(U,T) is defined as input (r) = a.

Finally, it is said that r R(U,T) is applicable over M(U) if and only if input(r).

Applicability Algorithm. On the one hand, a set of useful evolution rules R and a multiset of objects, will be the input to the process. On the other hand, output of process will be RA, the evolution rules subset of R that are applicable over the multiset. Traditional algorithm [Fernndez, 2005] checks weights of each evolution rules antecedent symbol with the corresponding from multiset of objects.

(1) RA (2) FOR-EACH ri IN R DO BEGIN (3) j (4) WHILE j | | -1 AND | input(ri) | j | | j DO (5) j j +(6) IF | input(ri) | j | | j THEN (7) RA RA {ri } (8) END Algorithm 1. Evolution rules applicability (without decision trees).

Knowledge Engineering Complexity of algorithm 1 consider, in the worst case, situation in which every evolution rule are applicable over the multiset of objects: loop in (4) will reach as many iterations as symbols exists in U on each iteration of loop (2) to each evolution rule present in R. In the worst case, complexity order will be O(n) being n =| R | | U | Analysis of previous algorithm will reveal possible redundancies in checks: in a direct and indirect way. So, A redundant check in a direct way will occur when weight of a same symbol is equal in more than one evolution rule antecedent, executing several times the same comparison (for example, let be input(r1) = (3,1, 4,1), input(r2) = (3, 2, 4, 4), and = (7, 3, 5, 4) where comparisons for the fist and third symbol of input(r2) are redundant in a direct way with its respective symbols in input(r1) ).

A redundant check in an indirect way will occur when, after result of a checking which is false, it will be performed checks between greater weights of that symbol in others evolution rules antecedent (for instance, let it be input(r1) = (3,1, 3,1), input(r2) = (5, 2, 5,1), and = (1, 3, 5, 4) where comparison for first symbol of input(r2) is redundant in an indirect way with its respective symbol in input(r1) ).

Furthermore, any checking of the weight of a symbol from an evolution rule antecedent with 0 will be unnecessary because 0 n n N.

Decision Trees A decision tree is a tree that permits us to determine the class which one element belongs to, depending on the values that take some attributes of it. Every internal node represents one attribute and edges are possible values of that attribute. Every leaf node in the tree represents one class. So, one unknown element can be classified processing the tree: every internal node studies the value of one attribute for the element and takes the appropriate edge, depending on its value; it continues until a leaf node is reached and, therefore, to the element classification.

There are a lot of algorithms to generate decision trees [Rasoul, 1991]. In particular, ID3 algorithm is based on entropy information and it generates an optimum decision tree from a non incremental set of instances and without repetitions.

ID3 algorithm requires as input (Fig. 1): let E be a finite set of instances {e1,...,ep} ; let A be a finite set of attributes {a1,...,aq};let Vj be a finite set of values {v1 j,...,vrj} for each attribute aj, (where aj attribute value for instance ei fulfils vij Vj ); and finally, let C be a finite set of classes for the classification {c1,...,cs}.

On the other hand, ID3 algorithm outputs the optimum decision tree for any element classification (Fig. 2).

Figure 1. Example of values table Figure 2. Decision tree generated by IDfor ID3 algorithm input for values table from fig 1.

Fourth International Conference I.TECH 2006 Decision Trees for Applicability of Evolution Rules This section presents evolution rules applicability as a classification problem. This way, it will be posible to design a new algorithm that, being based on a decision tree, avoid direct and indirect redundancies of algorithm presented above.

In order to it, we invert evolution rules applicability problem terms: for a given multiset, we compute the applicable evolution rules subset. Hence, we consider:

Multisets of objects will be the elements to be classified: = ( p1,..., pm) M(U);

The set of attributes will be a settled as a set of checks between the objects weights from the multiset and the same object from the evolution rules antecedents having a non null weight. Hence, the finite set of attributes will be: A = {a | |u k / | input(r) |u = k k 0 r R u U } ;

Consequently, the finite set of values for every attribute will be true or false, result from comparison relationship between weights.

Finally, classes to consider will be the different applicable evolution rules subsets. Therefore, the finite set of classes will be: C = {c RA / RA R }.

To obtain automatic generation of decision tree from ID3 algorithm, it will be necessary a non incremental and without repetitions battery of finite instances. In order to it, domain is defined as a set of multisets having the same values for all of their attributes.

Consequently, each domain is characterized because every multiset responds to the same applicable evolution rules subset, that is, to the same class.

Finally, examples battery will be formed by a representative from each domain.

Fig. 3 shows an example with disjoint domains of Fig. 3. Disjoint domains of multisets of objects multisets of symbols for U = {x, y} and rules set:

for rules set and its corresponding applicable R = {r1, r2, r3, r4} where their antecedents are:

evolution rules.

r1 = ( y5), r2 = (x2, y2), r3 = (x6, y2), r4 = (x2, y3).

Next, they are presented necessary definitions for formalizing the finite set of representative domains that are needed for the generation of decision trees.

It is defined projection of u U over R P(R (U,T)) as:

Pages:     | 1 |   ...   | 15 | 16 || 18 | 19 |   ...   | 54 |



2011 www.dissers.ru -

, .
, , , , 1-2 .