Data mining, p.54
Data Mining, page 54
then the extension principle states that the image of fuzzy set A under the mapping f can be expressed as a fuzzy set B:
where yi = f(xi), i = 1, … , n. In other words, the fuzzy set B can be defined through the mapped values xi using the function f.
Let us analyze the extension principle using one example. Suppose that X = {1, 2, 3, 4} and Y = {1, 2, 3, 4, 5, 6} are two universes of discourse, and the function for transformation is y = x + 2. For a given fuzzy set A = 0.1/1 + 0.2/2 + 0.7/3 + 1.0/4 in X, it is necessary to find a corresponding fuzzy set B(y) in Y using the extension principle through function B = f(A). In this case, the process of computation is straightforward and a final, transformed fuzzy set is B = 0.1/3 + 0.2/4 + 0.7/5 + 1.0/6.
Another problem will show that the computational process is not always a one-step process. Suppose that A is given as
and the function f is
Upon applying the extension principle, we have
where ∨ represents the max function. For a fuzzy set with a continuous universe of discourse X, an analogous procedure applies.
Besides being useful in the application of the extension principle, some of the unary and binary fuzzy relations are also very important in a fuzzy-reasoning process. Binary fuzzy relations are fuzzy sets in X × Y that map each element in X × Y to a membership grade between 0 and 1. Let X and Y be two universes of discourse. Then
is a binary fuzzy relation in X × Y. Note that μR(x, y) is in fact a two-dimensional (2-D) MF. For example, let X = Y = R+ (the positive real axis); the fuzzy relation is given as R = “y is much greater than x.” The MF of the fuzzy relation can be subjectively defined as
If X and Y are a finite set of discrete values such as X {3, 4, 5} and Y = {3, 4, 5, 6, 7}, then it is convenient to express the fuzzy relation R as a relation matrix:
where the element at row i and column j is equal to the membership grade between the ith element of X and the jth element of Y.
Common examples of binary fuzzy relations are as follows:
1. x is close to y (x and y are numbers).
2. x depends on y (x and y are categorical data).
3. x and y look alike.
4. If x is large, then y is small.
Fuzzy relations in different product spaces can be combined through a composition operation. Different composition operations have been suggested for fuzzy relations; the best known is the max–min composition proposed by Zadeh. Let R1 and R2 be two fuzzy relations defined on X × Y and Y × Z, respectively. The max–min composition of R1 and R2 is a fuzzy set defined by
or equivalently,
with the understanding that ∨ and ∧ represent max and min, respectively.
When R1 and R2 are expressed as relation matrices, the calculation of R1 ° R2 is similar to the matrix-multiplication process, except that × and + operations are replaced by ∨ and ∧, respectively.
The following example demonstrates how to apply the max–min composition on two relations and how to interpret the resulting fuzzy relation R1 ° R2. Let R1 = “x is relevant to y” and R2 = “y is relevant to z” be two fuzzy relations defined on X × Y and Y × Z, where X = {1, 2, 3}, Y = {α, β, γ, δ}, and Z = {a, b}. Assume that R1 and R2 can be expressed as the following relation matrices of μ values:
Fuzzy relation R1 ° R2 can be interpreted as a derived relation “x is relevant to z” based on relations R1 and R2. We will make a detailed max–min composition only for one element in a resulting fuzzy relation: (x, z) = (2, a).
Analogously, we can compute the other elements, and the final fuzzy matrix R1 ° R2 will be
14.4 FUZZY LOGIC AND FUZZY INFERENCE SYSTEMS
Fuzzy logic enables us to handle uncertainty in a very intuitive and natural manner. In addition to making it possible to formalize imprecise data, it also enables us to do arithmetic and Boolean operations using fuzzy sets. Finally, it describes the inference systems based on fuzzy rules. Fuzzy rules and fuzzy-reasoning processes, which are the most important modeling tools based on the fuzzy-set theory, are the backbone of any fuzzy inference system. Typically, a fuzzy rule has the general format of a conditional proposition. A fuzzy If-then rule, also known as fuzzy implication, assumes the form
If x is A, then y is B
where A and B are linguistic values defined by fuzzy sets on the universes of discourse X and Y, respectively. Often, “x is A” is called the antecedent or premise, while “y is B” is called the consequence or conclusion. Examples of fuzzy if-then rules are widespread in our daily linguistic expressions, such as the following:
1. If pressure is high, then volume is small.
2. If the road is slippery, then driving is dangerous.
3. If a tomato is red, then it is ripe.
4. If the speed is high, then apply the brake a little.
Before we can employ fuzzy if-then rules to model and analyze a fuzzy reasoning-process, we have to formalize the meaning of the expression “if x is A then y is B,” sometimes abbreviated in a formal presentation as A → B. In essence, the expression describes a relation between two variables x and y; this suggests that a fuzzy if-then rule be defined as a binary fuzzy relation R on the product space X × Y. R can be viewed as a fuzzy set with a 2-D MF:
If we interpret A → B as A entails B, still it can be formalized in several different ways. One formula that could be applied based on a standard logical interpretation, is
Note that this is only one of several possible interpretations for fuzzy implication. The accepted meaning of A → B represents the basis for an explanation of the fuzzy-reasoning process using if-then fuzzy rules.
Fuzzy reasoning, also known as approximate reasoning, is an inference procedure that derives its conclusions from a set of fuzzy rules and known facts (they also can be fuzzy sets). The basic rule of inference in a traditional two-valued logic is modus ponens, according to which we can infer the truth of a proposition B from the truth of A and the implication A → B. However, in much of human reasoning, modus ponens is employed in an approximate manner. For example, if we have the rule “if the tomato is red, then it is ripe” and we know that “the tomato is more or less red,” then we may infer that “the tomato is more or less ripe.” This type of approximate reasoning can be formalized as
Fact: x is A′
Rule: If x is A then y is B
Conclusion: y is B′
where A′ is close to A and B′ is close to B. When A, A′, B, and B′ are fuzzy sets of an approximate universe, the foregoing inference procedure is called approximate reasoning or fuzzy reasoning; it is also called generalized modus ponens, since it has modus ponens as a special case.
Using the composition rule of inference, we can formulate the inference procedure of fuzzy reasoning. Let A, A′, and B be fuzzy sets on X, X, and Y domains, respectively. Assume that the fuzzy implication A → B is expressed as a fuzzy relation R on X × Y. Then the fuzzy set B′ induced by A′ and A → B is defined by
Some typical characteristics of the fuzzy-reasoning process and some conclusions useful for this type of reasoning are
1. ∀A, ∀ A′ → B′ ⊇ B ( or μ B′(y) ≥ μ B(y))
2. If A′ ⊆ A (or μ A(x) ≥ μ A′(x)) → B′ = B
Let us analyze the computational steps of a fuzzy-reasoning process for one simple example. Given the fact A′ = “x is above average height” and the fuzzy rule “if x is high, then his/her weight is also high,” we can formalize this as a fuzzy implication A → B. We can use a discrete representation of the initially given fuzzy sets A, A′, and B (based on subjective heuristics):
μR(x, y) can be computed in several different ways, such as
or as the Lukasiewicz norm:
Both definitions lead to a very different interpretation of fuzzy implication. Applying the first relation for μR(x, y) on the numeric representation for our sets A and B, the 2-D MF will be
Now, using the basic relation for inference procedure, we obtain
The resulting fuzzy set B′ can be represented in the form of a table:
B′: y μ(y)
120 0.3
150 1.0
180 1.0
210 1.0
or interpreted approximately in linguistic terms: “x’s weight is more-or-less high.” A graphical comparison of MFs for fuzzy sets A, A′, B, and B′ is given in Figure 14.11.
Figure 14.11. Comparison of approximate reasoning result B’ with initially given fuzzy sets A’, A, and B and the fuzzy rule A → B. (a) Fuzzy sets A and A’; (b) fuzzy sets B and B’ (conclusion).
To use fuzzy sets in approximate reasoning (a set of linguistic values with numeric representations of MFs), the main tasks for the designer of a system are
1. represent any fuzzy datum, given as a linguistic value, in terms of the codebook A;
2. use these coded values for different communication and processing steps; and
3. at the end of approximate reasoning, transform the computed results back into its original (linguistic) format using the same codebook A.
These three fundamental tasks are commonly referred to as encoding, transmission and processing, and decoding (the terms have been borrowed from communication theory). The encoding activities occur at the transmitter while the decoding take place at the receiver. Figure 14.12 illustrates encoding and decoding with the use of the codebook A. The channel functions as follows. Any input information, whatever its nature, is encoded (represented) in terms of the elements of the codebook. In this internal format, encoded information is sent with or without processing across the channel. Using the same codebook, the output message is decoded at the receiver.
Figure 14.12. Fuzzy-communication channel with fuzzy encoding and decoding.
Fuzzy-set literature has traditionally used the terms fuzzification and defuzzification to denote encoding and decoding, respectively. These are, unfortunately, quite misleading and meaningless terms because they mask the very nature of the processing that takes place in fuzzy reasoning. They neither address any design criteria nor introduce any measures aimed at characterizing the quality of encoding and decoding information completed by the fuzzy channel.
The next two sections are examples of the application of fuzzy logic and fuzzy reasoning to decision-making processes, where the available data sets are ambiguous. These applications include multifactorial evaluation and extraction of fuzzy rules-based models from large numeric data sets.
14.5 MULTIFACTORIAL EVALUATION
Multifactorial evaluation is a good example of the application of the fuzzy-set theory to decision-making processes. Its purpose is to provide a synthetic evaluation of an object relative to an objective in a fuzzy-decision environment that has many factors. Let U = {u1, u2, … , un} be a set of objects for evaluation, let F = {f1, f2, … , fm} be the set of basic factors in the evaluation process, and let E = {e1, e2, … , ep} be a set of descriptive grades or qualitative classes used in the evaluation. For every object u ∈ U, there is a single-factor evaluation matrix R(u) with dimensions m × p, which is usually the result of a survey. This matrix may be interpreted and used as a 2-D MF for fuzzy relation F × E.
With the preceding three elements, F, E, and R, the evaluation result D(u) for a given object u ∈ U can be derived using the basic fuzzy-processing procedure: the product of fuzzy relations through max–min composition. This has been shown in Figure 14.13. An additional input to the process is the weight vector W(u) for evaluation factors, which can be viewed as a fuzzy set for a given input u. A detailed explanation of the computational steps in the multifactorial-evaluation process will be given through two examples.
Figure 14.13. Multifactorial-evaluation model.
14.5.1 A Cloth-Selection Problem
Assume that the basic factors of interest in the selection of cloth consist of f1 = style, f2 = quality, and f3 = price, that is, F = {f1, f2, f3}. The verbal grades used for the selection are e1 = best, e2 = good, e3 = fair, and e4 = poor, that is, E = {e1, e2, e3, e4}. For a particular piece of cloth u, the single-factor evaluation may be carried out by professionals or customers by a survey. For example, if the survey results of the “style” factor f1 are 60% for the best, 20% for the good, 10% for the fair, and 10% for the poor, then the single-factor evaluation vector R1(u) is
Similarly, we can obtain the following single-factor evaluation vectors for f2 and f3:
Based on single-factor evaluations, we can build the following evaluation matrix:
If a customer’s weight vector with respect to the three factors is
then it is possible to apply the multifactorial-evaluation model to compute the evaluation for a piece of cloth u. “Multiplication” of matrices W(u) and R(u) is based on the max–min composition of fuzzy relations, where the resulting evaluation is in the form of a fuzzy set D(u) = [d1, d2, d3, d4]:
where, for example, d1 is calculated through the following steps:
The values for d2, d3, and d4 are found similarly, where ∧ and ∨ represent the operations min and max, respectively. Because the largest components of D(u) are d1 = 0.4 and d2 = 0.4 at the same time, the analyzed piece of cloth receives a rating somewhere between “best” and “good.”
14.5.2 A Problem of Evaluating Teaching
Assume that the basic factors that influence students’ evaluation of teaching are f1 = clarity and understandability, f2 = proficiency in teaching, f3 = liveliness and stimulation, and f4 = writing neatness or clarity, that is, F = {f1, f2, f3, f4}. Let E = {e1, e2, e3, e4} = {excellent, very good, good, poor} be the verbal grade set. We evaluate a teacher u. By selecting an appropriate group of students and faculty, we can have them respond with their ratings on each factor and then obtain the single-factor evaluation. As in the previous example, we can combine the single-factor evaluation into an evaluation matrix. Suppose that the final matrix R(u) is
For a specific weight vector W(u) = {0.2, 0.3, 0.4, 0.1}, describing the importance of the teaching-evaluation factor fi and using the multifactorial-evaluation model, it is easy to find
Analyzing the evaluation results D(u), because d2 = 0.4 is a maximum, we may conclude that teacher u should be rated as “very good.”
14.6 EXTRACTING FUZZY MODELS FROM DATA
In the context of different data-mining analyses, it is of great interest to see how fuzzy models can automatically be derived from a data set. Besides prediction, classification, and all other data-mining tasks, understandability is of prime concern, because the resulting fuzzy model should offer an insight into the underlying system. To achieve this goal, different approaches exist. Let us explain a common technique that constructs grid-based rule sets using a global granulation of the input and output spaces.
Grid-based rule sets model each input variable usually through a small set of linguistic values. The resulting rule base uses all or a subset of all possible combinations of these linguistic values for each variable resulting in a global granulation of the feature space into rectangular regions. Figure 14.14 illustrates this approach in two dimensions: with three linguistic values (low, medium, high) for the first dimension x1 and two linguistic values for the second dimension x2 (young, old).
Figure 14.14. A global granulation for a two-dimensional space using three membership functions for x1 and two for x2.
Extracting grid-based fuzzy models from data is straightforward when the input granulation is fixed, that is, the antecedents of all rules are predefined. Then, only a matching consequent for each rule needs to be found. This approach, with fixed grids, is usually called the Mamdani model. After predefinition of the granulation of all input variables and also the output variable, one sweeps through the entire data set and determines the closest example to the geometrical center of each rule, assigning the closest fuzzy value output to the corresponding rule. Using graphical interpretation in a 2-D space, the global steps of the procedure are illustrated through an example in which only one input x and one output dimension y exist. The formal analytical specification, even with more than one input/output dimension, is very easy to establish.
1. Granulate the Input and Output Space. Divide each variable xi into ni equidistant, triangular, MFs. In our example, both input x and output y are granulated using the same four linguistic values: low, below average, above average, and high. A representation of the input–output granulated space is given in Figure 14.15.
2. Analyze the Entire Data Set in the Granulated Space. First, enter a data set in the granulated space and then find the points that lie closest to the centers of the granulated regions. Mark these points and the centers of the region. In our example, after entering all discrete data, the selected center points (closest to the data) are additionally marked with x, as in Figure 14.16.
3. Generate Fuzzy Rules from Given Data. Data representative directly selects the regions in a granulated space. These regions may be described with the corresponding fuzzy rules. In our example, four regions are selected, one for each fuzzy input linguistic value, and they are represented in Figure 14.17 with a corresponding crisp approximation (a thick line through the middle of the regions). These regions are the graphical representation of fuzzy rules. The same rules may be expressed linguistically as a set of IF-THEN constructions:
R1: IF x is small, THEN y is above average.
R2: IF x is below average, THEN y is above average.
