3.1. Discretization

Discretizing continuous parameters is inspired in part by the fact that experts usually describe parameters using linguistic terms instead of an exact value. There are several advantages of data discretization: it provides regularization because it is less prone to variance in estimation from small fragmented data, the amount of data can be greatly reduced because some redundant data can be identified and removed, and some rule extraction method such as decision trees can perform better if all of the continuous-valued attributes are discretized before rule induction.

Equal width is one of the most frequently used unsupervised data discretization methods. It is also the simplest one, which divides the range of observed values for a variable into N intervals of equal sized intervals. The range of each interval is calculated by

where the number of intervals should be determined by users.

This method applies to the situation where the distribution of sample data is quite uniform. However, it is vulnerable to outliers that may drastically skew the range (Catlett, 1991). A statistically justified heuristic method for supervised discretization is the chi-merge algorithm (Kerber, 1992). This algorithm begins by placing each observed real value into its own interval and proceeds by using the χ² test to determine when adjacent intervals should be merged. The extent of the merging process is controlled by the use of a χ² threshold α, indicating the maximum χ² value that warrants merging two intervals. The author reports that on random data, a very high threshold must be set to avoid creating too many intervals.

Chi2 (Liu & Setiono, 1997) is a variant of the chi-merge algorithm. It consists of two phases. In phase 1, a rough common α (significance level) for all variables is used. In phase 2, the intervals are further merged using a separate α for each variable. In general, Chi2 can form simpler terms, which leads to improved predictive accuracy. However, it is computationally complicated because it takes each different data point as an initial interval. In addition, it merges variables sequentially rather than trying to minimize the inconsistency resulting from merging. To overcome these drawbacks, we developed a greedy chi-merge algorithm for data discretization.

Greedy chi-merge also contains two phases: crude discretization and fine-tuning. Compared to the Chi2 algorithm, which takes the number of distinct values of a variable as the initial number of intervals, greedy chi-merge performs an initial partitioning based on the change in the output value, as illustrated in Figure 3. In this way, the number of intervals for each variable can be greatly reduced.

The initial partitioning of greedy chi-merge.

The next phase, fine tuning, is based on greedy search, which always chooses to merge the intervals of a variable that causes the least inconsistency rate among all mergeable variables. Although all the attributes are considered simultaneously, only the merging that causes the lowest inconsistency rate takes place. The pseudocodes of the greedy chi-merge are shown in Figure 4.

The pseudocodes for greedy chi-merge.

The problem of data inconsistency results when, after discretization, data samples exist in which the inputs are the same but the outputs are different. The inconsistency rate is calculated using the following expression, based upon the method proposed by Liu and Setiono (1997):

where N is the total number of cases, n_i is the number of cases with the same input (i = 1, 2,…, I), [sum ]_i n_i = N; c_{i, j} is the count of class j in n_i (j = 1, 2,…, J), [sum ]_i c_{i, j} = n_i; and

3.2. Rule extraction

Once all continuous variables are discretized, linguistic terms can be used to describe these variables. The original data samples are converted accordingly. As a result, all the inputs and outputs become discrete. A procedure, which utilizes the learning ability of a neural network, has been developed to extract rules for these converted data samples. The details of the procedure have been described in a previous publication (Huang et al., 2001). An outline of the five-step approach is provided in Figure 5. In summary, the converted data is represented using a binary scheme and used to train a neural network, which is specially structured according to the linguistic terms used. Linguistic IF–THEN rules are then extracted by analyzing the connections and weights of the trained neural network, using a dynamic depth-first search algorithm to reduce computation complexity.

Rule extraction using a neural network.

An alternative rule extraction approach is through the use of decision tree learning. Decision trees are currently a highly developed technique for partitioning data samples into a set of covering decision rules (Weiss & Kulikowski, 1991). Decision tree learning algorithms such as ID3 and C4.5 have been widely publicized by Quinlan. Readers interested in the details should refer to Quinlan (1986, 1993). Once the decision tree is constructed for a specific problem, rules can be extracted directly from left to right and from top to bottom of the decision tree. Usually the number of rules extracted equals the number of leaves existing in the decision tree. Decision tree induction algorithms scale up very well for large data sets.

The extracted rules, represented using a linguistic IF–THEN format, are easily understood. They can be used to enrich the knowledge engineer's understanding of the underlying domain. With this knowledge, the knowledge engineer can have a more intelligent interview with domain experts. Asking domain experts more detailed questions can result in more refined and comprehensive knowledge in that domain. The knowledge engineer can then transfer the unstructured knowledge acquired from domain experts into structured knowledge in IF–THEN format and combine these rules with rules automatically extracted from data samples.

3.3. Rule simplification and pruning

The performance of a KBS will be adversely affected when the KB increases in size and contains conflicting rules. In this sense, a compact KB is desirable. However, a trade-off always exists between completeness (covering the entire knowledge domain) and compactness (using as few rules as possible). In the manufacturing domain, shop floor operators prefer to have a small amount of highly intuitive rules by sacrificing a small loss in predictive accuracy. Therefore, we believe rule simplification and pruning are justified in manufacturing application. Two concepts, namely, PofM (Possibility of Merging) and AofP (Accuracy of Prediction), are introduced to reduce the size of a KB while maintaining an acceptable level of performance. Details of rule simplification and pruning are discussed as follows.

When rules are provided by domain experts, they may be in a compound format. A rule that contains OR and/or NOT is a compound rule, which brings potential and indetectable inconsistency and thus hinders the maintainability of rules (Higa, 1996). Automatically extracted rules are never in a compound format. Compound rules acquired manually should be transformed in order to maintenance consistency. For example, we have the following rule:

• IF (a₁ is LARGE OR a₂ is MEDIUM) AND (a₃ is NOT SMALL) THEN o₁ is MEDIUM

Assume that a₃ is described using three linguistic terms, SMALL, MEDIUM, and LARGE. The rule can be transformed into four noncompound rules:

• IF a₁ is LARGE AND a₃ is MEDIUM THEN o₁ is MEDIUM
• IF a₁ is LARGE AND a₃ is LARGE THEN o₁ is MEDIUM
• IF a₂ is MEDIUM AND a₃ is MEDIUM THEN o₁ is MEDIUM
• IF a₂ is MEDIUM AND a₃ is LARGE THEN o₁ is MEDIUM

A typical problem with automatically extracted rules is that the rules could overlap, which means these rules can be combined to form a simpler rule. For example, we have the following three rules:

• IF a₁ is SMALL AND a₂ is LARGE THEN o₁ is LARGE
• IF a₁ is MEDIUM AND a₂ is LARGE THEN o₁ is LARGE
• IF a₁ is LARGE AND a₂ is LARGE THEN o₁ is LARGE

Assume that a₁ is described using three linguistic terms, SMALL, MEDIUM, and LARGE. These three rules can be combined into one simpler rule:

• IF a₂ is LARGE THEN o₁ is LARGE

The Quine–McCluskey algorithm is known as an approach of Boolean functions simplification (McCluskey, 1956). In this paper, it is used to automatically combine overlapping rules that may exist in the automatically extracted rule set. When combining manually acquired rules with automatically extracted rules, especially when compounded rules are transformed, redundant rules may appear. Redundant rules means that rules having identical premises also have identical consequences. Removal of redundant rules is trivial because it can be realized through a simple search.

Rules are simplified once redundant rules are removed and overlapping rules are combined. A further step is to prune these rules to make the rule base more compact. The criterion used for pruning is the generalization ability (predictive accuracy). The user may provide a testing data set and define an acceptable level of predictive accuracy. Rules are pruned by merging similar rules and removal of insignificant rules, as long as these actions do not result in a predictive accuracy with an unacceptable low level. This is accomplished by using the concepts of PofM and AofP.

When a weight is associated with a rule, as in the case of rule extraction using dynamic depth-first search (the neural network approach), an insignificant rule means a rule that has a small weight. If a rule does not have a weight originally, as in the case of rule induction using ID3 or rule provided by a domain expert, an insignificant rule is one that applies to few data samples. In this case, we can assign a weight to each rule based on how many data samples they apply. Thus, weight is used as a unified measure for rule significance.

The rule simplification and pruning algorithm is shown in Figure 6 using the following definitions:

[bull ] SR (Similar Rules): rules that have identical output values and only one different input value.

[bull ] KI (Key Input): the input that distinguishes SR.

[bull ] SRG (Similar Rule Group): a rule group that holds all SR. Note that a rule can belong to different SRG.

[bull ] MSRG (Mergeable Similar Rule Group): a SRG where the KI values of all the rules have adjacent values and the number of the rules equals to the number of available values for the KI. For example, the following rules can be put into a MSRG:

• IF a₁ is LARGE AND a₂ is MEDIUM THEN o₁ is MEDIUM
• IF a₁ is SMALL AND a₂ is MEDIUM THEN o₁ is MEDIUM
• IF a₁ is MEDIUM AND a₂ is MEDIUM THEN o₁ is MEDIUM

[bull ] PofM: each MSRG has a PofM value

[bull ] DC (Don't Care): An input does not appear in a rule; its value can be ignored by the rule.

[bull ] AofP: In general, previous unseen cases are used to test the predictive accuracy of a rule base. AofP is defined as

Rule simplification and pruning and an algorithm.

Note that all rules are in digital format, for example, 2 0 4 −1 5. The first 3 digits stand for the input value, 5 is the output value, and −1 is for wherever the DC attribute exists. Each attribute is represented by a number, ranging from 0 to the number of intervals −1. Take the three rules listed above for MSRG as example. Two attributes are concerned, a₁ and a₂. Both have three intervals; so does the output. The three rules are represented as 2 1 1, 0 1 1, and 1 1 1.

4.1. Benchmark case

To illustrate how to use automatic knowledge acquisition to rapidly develop a KBS and to demonstrate its effectiveness, the popular iris flower classification problem is used as a benchmark case study. The problem is based on a data set first used by Fisher (1936) for illustrating discriminant analysis techniques. The classification problem then became a standard benchmark problem for testing different classification methods. The data set can be obtained from the University of California at Irvine ftp server (ftp://128.195.1.46/pub/machine-learning-databases/iris/). It contains 150 patterns: 50 of them belong to the class of Iris setosa, 50 belong to the class of Iris versicolor, and 50 belong to the class of Iris virginica. There are four input parameters to describe the three classes of flowers, namely, sepal length, sepal width, petal length, and petal width. They are all continuous-valued attributes.

A knowledge-based system is developed with the following steps. First, after discretization with greedy chi-merge, two parameters of sepal length and sepal width are removed because they have only one interval. Both petal length and petal width have three intervals after merging. The discretization result is shown in Table 1.

Data discretization for the Iris classification problem

Second, we used 75 data samples with odd index for training and the rest for testing. Using the dynamic depth-first search algorithm, four rules are extracted as follows. The weight attached to a rule shows its significance degree, as described in Section 4. The weights of rules have been normalized for easy handling, so weight 1.0 stands for the most significant and weight 0.0 for insignificant.

• IF petal length is SMALL AND petal width is SMALL, THEN iris class is Iris Setosa (weight 1.0)
• IF petal length is SMALL AND petal width is LARGE, THEN iris class is Iris Setosa (weight 0.035636)
• IF petal length is MEDIUM, THEN iris class is Iris Versicolour (weight 1.0)
• IF petal length is LARGE, THEN iris class is Iris Virginica (weight 1.0)

Third, after rule simplification and pruning, the following rules are obtained:

• IF petal length is SMALL AND petal width is SMALL, THEN iris class is Iris Setosa (weight 1.0)
• IF petal length is MEDIUM, THEN iris class is Iris Versicolour (weight 1.0)
• IF petal length is LARGE, THEN iris class is Iris Virginica (weight 1.0)

Fourth, these rules are used to develop a fuzzy inference system. Triangular membership functions are used for the input parameters and singleton spikes are used for output. Among the 75 testing data samples, 70 are correctly classified.

A comparison with prior results published in the literature is shown in Table 2. Although our approach did not achieve 100% accuracy, it yielded a more concise rule set (three rules) while still maintaining high accuracy (93.3%). Compared with the approach we proposed, REFuNN and RULES-3 Plus need many more rules to attain higher accuracy; REFuNN and Premises Learning use much larger training sets, which means higher computing cost. A trade-off exists here between conciseness and complexity. In a manufacturing environment, easy to understand and concise rules are preferred by operators to guide their daily operations. Therefore, a smaller rule set that has acceptable performance is desirable.

Comparison of the Iris classification problem

4.2. Industrial application

The integrated knowledge acquisition approach is also successfully applied to a real-world manufacturing process, drop hammer forming. Drop hammer forming is one of the most versatile processes for forming sheet metal parts, which is used extensively by B.F. Goodrich Aerospace/Aerostructures group in the production of aircraft engine nacelles. Basically, three process methods are used for drop hammer forming: bare punch, blow down, and blow up. Bare punch is the simplest procedure. Parts are produced using a single hammer strike and no forming aids are needed. Blow down and blow up procedures require the use of forming aids and multiple hammer strikes. The forming aids, usually rubbers, are placed on (blow down) or under (blow up) the part to form a pyramid. During the forming process, the pyramid causes the impact force to flow in the direction of the least rubber build up, thus preventing wrinkles and folding.

Operator skills play a critical role in assuring product quality in drop hammer forming. Experienced operators can produce high quality products by adjusting die configuration, using appropriate forming aids, and controlling punch blow. Their skills are accumulated through years of hands-on experience, and they have great difficulty explaining how and why they make a certain decision. Therefore, new operators have to learn through observation. This is very inefficient and it usually takes at least 6 months for a new operator to gain enough knowledge to be able to work independently. B.F. Goodrich engineers attempted to use traditional interview-based techniques to develop a KBS. They were not successful, mainly because the knowledge engineers have very little understanding of the drop hammer forming process, while experienced operators typically have no formal engineering education and were unable to explain the decisions they made.

Armed with the integrated knowledge acquisition method, a student was sent to B.F. Goodrich's drop hammer forming facility at Chula Vista, California. An initial interview with domain experts identified the following inputs: material type, maximum draw depth, presence of transitions and corners, and die type; while the outputs are identified as the forming process method, number and type of forming aids, and number of punch blows. For new operators, to decide which forming process method is the most challenging task. Therefore, we worked on rule extraction for process method determination first. We collected 73 historical cases, 35 of them are used for training and the remaining used for testing. Among all of the inputs, only maximum draw depth has continuous values. We used equal width as the discretization method and four intervals were formed. The following rules are obtained:

• IF maximum draw depth is LARGE AND material type is SOFT AND transitions and corners is YES, THEN forming process is BLOW UP (weight 1.0)
• IF maximum draw depth is LARGE AND material type is SOFT AND die type is MALE, THEN forming process is BLOW UP (weight 0.297073)
• IF maximum draw depth is LARGE AND material type is HARD AND transitions and corners is YES AND die type is MALE, THEN forming process is BLOW UP (weight 0.267993)
• IF transitions and corners is YES, THEN forming process is BLOW DOWN (weight 1.0)
• IF transitions and corners is NO, THEN forming process is BARE PUNCH (weight 1.0)

These rules achieved a 95% predictive accuracy when applied to the testing cases. With these rules, the student gained a good understanding of the drop hammer forming process. A final interview with domain experts was then conducted. The experts concluded that these rules are valid and were able to provide additional details. Specifically, part material can determine the selection of different types of rubber as forming aids. If part material is hard and heat treatment is required before the forming process is applied, then harder and more heat resistant rubbers are needed as forming aids. In addition, thinner rubber pads are used for harder parts. The material of a part, combined with its maximum draw depth, can be used to decide the number of punch blows needed to produce the part. Softer materials, such as Aluminum, can be drawn in one stage to around 1 in. However, hard materials, such as titanium, can only be drawn in one stage to a maximum of 0.5 in. When the thickness of forming aids is determined, denoted t, then the number of punch blows (denoted n) can be easily calculated as n = m/t + 1. One sheet of forming aids is removed after each punch blow. The last blow is applied when all the forming aids are removed. Combining the knowledge acquired, a software tool is then developed to assist operator decision making in drop hammer forming. Figure 7 shows a snapshot of the software tool.

The drop hammer forming digital assistant.

Some examples are used to illustrate how the acquired process knowledge is applied for drop hammer forming process planning. The tool shown in Figure 8a is used to produce an aluminum part. Its maximum draw depth is 3 in. Since it is a male tool and there are four corners, forming aids need to be placed under the part (see Fig. 8b). In other words, the blow up process method is used. Since aluminum is soft, rubber pads are used as the forming aid. Three 1-in. rubber pads are used since the maximum draw depth is 3 in. One sheet of rubber is removed after each punch blow. The last punch blow is applied when all three sheets of rubber are removed. Therefore, a total of four punch blows are needed.

A part that requires blow up: (a) tool and (b) configuration.

The tool shown in Figure 9a is also used to produce an aluminum part. Its maximum draw depth is 0.5 in. Since it is a female tool and there are transitions, the blow down process method is used. One sheet of 0.5-in. rubber pad approximately the size of the part is placed on top of the part (Fig. 9b). After one punch blow is applied, the rubber pad is removed. Another punch blow is then applied to obtain the final part.

A part that requires blow down: (a) part and tool and (b) forming aids placement.

Figure 10 shows a tool that is used to produce an aluminum part. The tool is essentially flat, with a maximum draw depth (the difference between the highest and the lowest point of the area enclosed by the bead) of 0.05 in. It has no transitions. Note that the bead is used to lock the part. Excess material will then be trimmed away to obtain the final part. Therefore, there are no corners either. In this care, bare punch is sufficient to produce the part. Care should be exercised when determining the presence of transitions.

A nearly flat part with no corners and transitions.

Figure 11 shows a not-so-flat part that clearly shows a transition, which needs to be produced using blow down rather than bare punch.

A not-so-flat part with a transition.