Trees, Lattices, and Graphs on Methods of Inferenc
Sabtu, 2011-11-19, 11:23:03

Oleh : Administrator

A tree is a hierarchical data structure consisting of nodes, which store information or knowledge, and branches, which connect the nodes. Branches are sometimes called links or edges and nodes are sometimes called vertices. Figure 3.1 shows a general binary tree, which has zero, one, or two branches per node. In an oriented tree the root node is the highest node in the hierarchy and the leaves are the lowest. A tree can be considered a special type of semantic net in which every node except the root has exactly one parent and zero or more child nodes. For the usual type of binary tree there is a maximum of two children per node, and the right child nodes are distinguished from the left.



Figure 3.1 Binary Tree

If a node has more than one parent it is in a network In Figure 3.1, notice that there is only one sequence of edges or path from the root to any node because it is not possible to move against an arrow. In oriented trees the arrows all point downward.

Trees are a special case of a general mathematical structure called a graph. The terms network or simply net are often used synonymously with graph when describing a particular example of a graph such as a telephone network. A graph can have zero or more links between nodes and no distinction between parents and children. A simple example of a graph is a map, in which the cities are the nodes and the links are the roads. The links may have arrows or directions associated with them and a weight to characterize some aspect of the link. An analogy is one-way streets with weight limits on how much trucks can carry through the streets. The weights in a graph can be any type of information. If the graph represents an airline route, the weights can be miles between cities, cost of flying, fuel conŽsumption, and so forth.

An artificial neural system is another example of a graph with cycles; because during training there is feedback of information from one layer of the net to another, which modifies the weights. A simple graph has no links that come immediately back on the node itself, as shown in Figure 3.2 (a). A circuit or cycle is a path through a graph that begins and ends on the same node, as does the path ABCA in Figure 3.2 (a). An acyclic graph has no cycles. A connected graph has links to all its nodes. A graph with directed links, called a digraph, and a self-loop are shown in Fig. 3.2 (c). A directed acyclic graph is a lattice, and an example is shown in Figure 3.2 (d). A tree with only a single path from the root to its one leaf is a degenerate tree. The degenerate binary trees of three nodes are shown in Figure 3.2 (e). Generally in a tree, the arrows are not explicitly shown because they are assumed to be pointing down.

Trees and lattices are useful for classifying objects because of their hierarchical nature, with parents above children. An example is a family tree, which shows the relationships and ancestry of related people. Another application of trees and lattices is making decisions; these are called decision trees or decision lattices. We will use the term structure to refer to both trees and lattices. A decision structure is both a knowledge representation scheme and a method of reasoning about its knowledge. An example of a decision tree for classifying animals is shown in Figure 3.3. This example is for the classic game of twenty questions. The nodes contain questions, the branches "yes" or "no" responses to the questions, and the leaves contain the guesses of what the animal is.

A small portion of a decision tree to classify raspberries is shown in Figure 3.4. Unlike Computer Science trees, classification trees may be drawn with the root down. Not shown is the mot, which has a branch to the "Leaves Simple" node and another branch to the "Leaves Compound" node. The decision process starts at the bottom by identifying gross features, such as whether the leaves are simple or compound. More specific details requiring closer observation are used as we travel up the tree. That is, larger sets of alternatives are examined first and then the decision process starts narrowing down the possibilities to smaller sets. This is a good way of organizing the decisions in terms of the time and effort to carry out more detailed observations.

If the decisions are binary, then a binary decision tree is both easy to construct and very efficient. Every question goes down one level in the tree. One question can decide one of two possible answers. Two questions can decide one of four possible answers. Three questions can decide one of eight possible answers and so on. If a binary tree is constructed such that all the leaves are answers and all the nodes leading down are questions, there can be a maximum of 2^N answers for N questions.

For example, ten questions can classify one of 1,024 animals whereas twenty questions can classify one of 1,048,576 possible answers.



Figure 3.2 Simple Graphs



Figure 3.3 Decision Tree Showing Knowledge about Animals

Another useful feature of decision trees is that they can be made self-learning If the guess is wrong, a procedure can be called to query the user for a new, correct classification question and the answers to the "yes" and "no" responses. A new node, branches, and leaves can then be dynamically created and added to the tree. In the original Animals program written in BASIC, knowledge was stored in DATA statements. When the user taught the program a new animal, automatic /earning took place as the program generated new DATA statements containing information about the new animal. In Pascal and other languages with pointer capability, the animal knowledge can be stored in trees.

Using the expert system tool CLIPS new rules can be built automatically as the program learns new knowledge (Giarratano 92). This automated knowledge acquisition is very useful because it can circumvent the knowledge acquisition bottleneck described in Chapter 1.

Decision structures can be mechanically translated into production rules. This can easily be done by a breadth-first searching of the structure and by generating IF.. .THEN rules at every node. For example, the decision tree in Figure 3.3 could be translated into rules as follows

IF QUESTION = "IS IT VERY BIG?" AND RESPONSE = 'NO"
     THEN QUESTION := "DOES IT SQUEAK?"
IF QUESTION = IS IT VERY BIG?" AND RESPONSE = "YES"
     THEN QUESTION := "DOES IT HAVE A LONG NECK?"


and so forth for the other nodes. A leaf node would generate an ANSWER response rather than a question. Appropriate procedures would also query the user for input and would then construct new nodes if wrong. Although decision structures are powerful classification tools, they are limited because they cannot deal with variables, as an expert system can. Expert systems are general purpose tools rather than simply classifiers.

Source : Giarratano, Joseph. 1998. Expert Systems Priciples and Programming, Third Edition. PWS Publishing: USA