Transcript CIClassCh08Ch09

Chapter 8
Fuzzy Systems Implementations
Introduction
We consider fuzzy rule systems and evolutionary fuzzy rule systems.
We first look at implementation issues, then describe the
implementations.
Code provided in class is to be used as shareware.
Implementation Issues
•Representation of fuzzy rules
•Evolutionary design of fuzzy rule systems
•The programming language used to implement fuzzy systems
Evolving a Fuzzy Rule System
Often, human expertise is not available.
One approach is to cluster data, then use centroids of clusters as
rules. (May then need to adjust membership functions, and
defuzzification)
We will evolve a fuzzy rule system using a GA.
Need to consider:
•What will be evolved (what parts of the fuzzy system)
•How system elements are represented
•Population initialization
•Fitness evaluations
•Operators used
Representing Fuzzy Rules
Our system will use Mamdani-type fuzzy rules, for example:
if input_1 is not Low, and input_2 is High, then the
output is Medium
if input_2 is Low, then the output is High
...but computers generally can’t handle this kind of input (yet)
Assuming each variable has three fuzzy sets, these two rules can be
numerically represented as:
-1 3 2
and
0 1 3 (0 means “don’t care”)
Fuzzy Rule System Implementation
(Example is for classification)
FuzzyRuleSet
FuzzyRule
FuzzyVariable
Vector<int>
FuzzyMember
Class tree in the implementation of the fuzzy rule system.
Examples: FuzzyMember hot
FuzzyVariable temperature
Vector Int1, Int2, Int3, Int4 (Can also be floats)
FuzzyRule If Int1 and Int2 and Int3 then Int4
FuzzyRuleSet Collection of FuzzyRules
Representing System Elements
The fuzzy rule: if input one is Low or High, and input
two is High, then the output is Low can be represented by:
101 001 100
Note the inclusion of OR.
If we restrict the rules to be Mamdani-like (AND only) then we can
represent the presence of a rule by ones and zeros.
A more natural way, and the way we use, is integer representation.
Assume four inputs and one output with three fuzzy sets each.
1 0 2 3 2 means: if input one is low, and we don’t care about input
two, and input three is medium and input four is high, then the output
is medium.
What do we evolve?
Candidate features for evolution: fuzzy rules, membership
functions, fuzzification and defuzzification methods.
Can evolve any or all. We evolve fuzzy rules and membership
functions.
How do we initialize the population?
Random initialization is usually best.
Can include knowledge, but beware…same problems as doing this
in GAs.
Fitness Evaluation
Percent correct and mean-square error are often used.
Additional components of fitness may include the number of rules
(minimize).
Genetic Operators
Usually use traditional operators for binary representations.
For real-valued and integer representations, different operators
may be best, such as position-based mutation.
An Object-Oriented Language: C++
Used for implementations in Chapters 8 and 9.
Is an extension of the C language.
Makes source code more re-usable.
(Note that choice of a programming language is almost like the choice
of a religion.)
Fuzzy Membership Functions
f left _ triangle
f right _ triangle
1

 x2  x

 x2 x1
0
if x  x1
if x1 x x2
if x  x2
0
if x  x1

 x  x1

if x1  x  x2
 x2  x1
1
if x  x2
Fuzzy Membership Functions, Cont’d.
if x  x1
0
 xx
x2  x1
1
2
if x1  x 
2
 x2  x1
f triangle( x)  
2 x2  x if x2  x1  x  x
2
 x2  x1
2

if x  x2
0
Fuzzy Membership Functions, Cont’d.
f Gaussian ( x)  e
f sigmoid ( x) 
0.5 y 2
1
1  e (  y  6)
8( x  x1 )
where y 
4
x2  x1
12( x  x1 )
where y 
x2  x1
f reverse _ sigmoid ( x)  1  f sigmoid ( x)
Fuzzy Rule System Implementation
Implementation is on book’s Internet site.
Dr. Yuhui Shi developed implementation, and application to the
Fisher Iris Data Set classification.
Focus is on classification, which can be more challenging than
control due to lack of feedback.
The fuzzy expert system implementation, and its application to
classifying the Iris Data Set, are discussed.
Fuzzy Rule System Implementation
•Usable for a wide variety of classification and diagnosis problems
•Has both linear and non-linear membership functions available
•Has special features, in addition to “standard” fuzzy rule system
features
Note: Membership functions are user-defined.
Fuzzy Rule System Implementation
To run the system: fl filename.run
Contents of iris.run:
iris.rul
(rules file)
iris.dat
(data file)
rules.out
(output rules in text)
minimum
results.out
(lists results)
1
(averaging flag: 0=normal 1=average)
1
(defuzz param: 0, 1, 2)
0
(summation flag: 1=max, 0=sum)
(defuzz: 0 centroid with highest value used
1 no overlap method used
2 overlap of different mem fnctns used)
(In summation flag, max is max value caused by any one rule.)
Input Parameters
Averaging flag: 0 or 1
0: AND statements are treated as usual in fuzzy systems
in that minimum is output
1: Average value of ANDed memberships is output
Defuzzification parameter: 0, 1, or 2
0: Centroid of membership function with highest value is
used for defuzzified scalar output
1: “No-overlap” method of defuzzification used
2: Overlap of different membership functions used
Summation flag: 0 or 1 (takes effect prior to defuzzification param.)
0: Sum of all values caused by all rules that fire (<=1) passed
on to defuzzification
1: Max. value caused by one rule passed on to defuzzification
Note: Underlined choices are used in example.
Format for iris.dat
413
0.637500
0.437500
0.875000
0.400000
0.787500
0.412500
…….and so on
4 is number of inputs
1 is number of outputs
3 is number of classes
0.175000
0.587500
0.750000
0.025000
0.175000
0.312500
0
1
2
The Rules File
Contains fuzzy rules and definitions for fuzzy membership functions
for input and output variables.
Is of central importance to fuzzy expert system.
Format is:
No._of_rules
No._of_inputs No._of_outputs
Definitions of input fuzzy sets
Definition(s) of output fuzzy set(s)
First rule
Second rule
…
Last rule
Rules File, Cont’d.
Each rule has an integer entry for each input and output variable
Maximum absolute value of integer for any rule variable is the
number of fuzzy sets defined over domain of that variable
Zeros and negative integers are allowed as rule variables
Fuzzy variable names are selected by user; after name is number of
fuzzy sets defined over domain, and range of domain. For example,
sepalLength 3 0.4 1.0
defines the first input variable to e called sepalLength, with three
fuzzy sets over the domain of 0.4 – 1.0, which is the range of data
(min, max) in the data set.
Fuzzy Membership Functions
Membership function definitions are of the form:
Function_name
left_limit right_limit
Allowed linear membership functions:
leftTriangle
Triangle
Allowed non-linear membership functions:
reverseSigmoid Gaussian
Example: leftTriangle
0.0 0.3
rightTriangle
Sigmoid
Format for iris.rul
16
41
sepalLength 3 0.4 1.0
leftTriangle 0.4 0.8
Triangle 0.5 0.9
rightTriangle 0.6 1.0
sepalWidth 3 0.0 0.6
leftTriangle 0.0 0.3
Triangle 0.15 0.45
rightTriangle 0.3 0.6
petalLength 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.2 0.7
rightTriangle 0.4 1.0
petalWidth 3 0.0 0.4
leftTriangle 0.0 0.2
Triangle 0.1 0.3
rightTriangle 0.2 0.4
output 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.3 0.7
rightTriangle 0.5 1.0
21221
33333
13111
11223
21333
13111
22332
31333
13111
32322
21222
12111
22333
32333
11111
11222
(Note that in sepalLength and output: the leftTriangle could have been a
reverse sigmoid and the Triangle could be a Gaussian. )
Membership Function Definitions
FUNCTION
leftTriangle
Decreases from 1 at left limit to 0 at right limit
Triangle
Gaussian
VALUE
0 at left limit, 1 peak midway, 0 at right limit
x2

e 2
, where x = – 4 at left limit, x = 4 at right limit
1
Sigmoid
 x , where x = – 6 at left limit, x = 6 at right limit
1 e
Six Membership Functions
Removing Rule Redundancy
Duplicate listings of rules can be eliminated (three cases of 1 3 1 1 1
can be reduced to 1, eliminating two rules).
Rules can be collapsed:
1 3 1 1 1, 1 2 1 1 1, and 1 1 1 1 1 can be collapsed to form 1 0 1 1 1,
eliminating two rules.
3 1 3 3 3, 3 2 3 3 3, and 3 3 3 3 3 can be collapsed to form 3 0 3 3 3,
eliminating two more rules.
Do NOT assume you can collapse 1 1 1 1 1 and 1 1 1 1 2 to 1 1 1 1 –3
because defuzzification is quite different!
Final Rule Set
The original 16 rules can thus be collapsed to 10 with the same results:
21221
30333
10111
11223
21333
22332
32322
21222
22333
11222
Output Files
Rule output file rules_out contains a list of rules in words, such as:
if_sepalLength_is_medium_and_sepalWidth_is_Low_and_
…etc., which facilitates accuracy checking.
Results file results.out is listing of correct classifications for input
patterns with classifications made by the system with errors identified
and the error total listed.
Iris Data Set Application
Fuzzy domains were scaled to input variable ranges
Domain limits and membership functions can be adjusted
during system development.
LVQ was used to cluster the Iris data, then centroids obtained were
used to formulate fuzzy rules.
(No. of clusters in LVQ sets number of rules.)
Averaging flag = 1 so average of fuzzy membership values was
used for defuzzification on output domain.
Summation flag = 0 so contributions were summed (max. = 1).
Iris Data Set Application, Cont’d.
Output set used for each cluster: the dominant output class for that
cluster.
Membership types and locations were fine-tuned by a human (Dr. Shi).
(Non-linear for classes 1 and 2; triangular for class 3.)
Performance: 143 out of 150 patterns were correctly classified.
(Can get this result with all triangular membership functions, and
summation flag set to zero.)
Evolving Fuzzy Rule Systems
Integer version of GA is used to evolve fuzzy rule system (since
integers are used to represent rules and membership function
types).
The representation and the fitness are the links between the GA
and the fuzzy rule system.
• The GA sees the population as something to evolve;
then to pass evolved population to fuzzy system.
• The fuzzy system sees the individual as something to
decode into membership functions, rules, etc.; then to
evaluate the given data and pass fitness to GA
Evolutionary Fuzzy Rule System
Design
Evolve (adapt) membership functions and rules to achieve
desired system performance.
The first important consideration is the representation strategy:
all needed information about the rule set and membership
functions must be encoded.
Fuzzy system encoded into string of integers:
number of rules used
rule set
membership function types, shapes, and ranges
Representation of Rule Set
for Evolutionary Fuzzy Rule System
Assume 4 input variables and 1 output variable
Assume 5 fuzzy sets per variable; then, integers 1–5 represent the
fuzzy sets, 0 represents absence of a variable (don’t care).
Example:
if input_1 is low, input_2 is medium, and input_4 is high,
then output is very_high
is encoded as 2 3 0 4 5
Representation of Membership Function
Types, Shapes and Ranges
For each membership function, represent the type (and shape) as an
integer from 1 to 6.
Represent range as two integers from 0 to 10; low and high ends of
range.
The range values represent offsets from nominal positions (0–4
negative shift, 5 no shift, 6–10 positive shift).
Example: 6 9 3
(start point, end point, type)
So, for 5 variables, each with 3 membership functions, there will be a
total of 5x3x3 = 45 integers that represent the membership function
types, shapes, and ranges.
Range Values
The dynamic range is [a, b] and there are n fuzzy sets.
The center point ci (i = 1, ..., n) of the i th membership
function is located at
ba
ci  a  i * step i  1,, n,where step 
.
n 1
Constrain the start_point xi1 of the ith membership function
to vary only between ci-1 and ci, and the end_point xi2 of the
ith membership function can vary only between ci and ci+1.
Assume an integer s (s=0,...,10) is used to "tune" xi1 and
xi2 .
step * (10  s i1 )
x 1  i * step 
a
2 *10
step * (10  s i 2 )
i
x 2  i * step 
a
2 *10
i
i  1,  , n
Uniformly Distributed Membership
Functions
Chromosome Representation
Iris Data Set Problem
Chromosome example:
#rules, start_point1, end_point1, type1, … start_point15, end_point15,
type15, rule1, … , rule_maxno
where there are 15 membership functions total (5 variables, 3
membership functions per variable), and maxno is maximum number of
rules allowed.
So, if maxno is 20, there are 1 + 45 + (20*5) = 146 integers in each
chromosome.
Rule Feasibility Check
Rules are checked for feasibility:
Each rule must have a non-zero antecedent, and a non-zero
consequent.
A rule such as 2 3 1 1 0 is thus non feasible, and is not included in
the rule set.
If no rules are feasible (may happen at beginning of run), the
fitness of population is set very small, maybe .0001.
Running the Evolutionary Fuzzy Rule
System
In the working DOS directory, type: flga
flga.run
The main run file has only two items, which are run files for the
GA and the fuzzy rule system:
ga.run
fl.run
The system is thus run in two stages.
evolve the rules
classify the patterns
When FLGA runs, you have the choice of:
evolving rules
classifying the input data set
modifying the run file
Example of a GA Run File
iris.dat
base.rul
result_4.rul
1
2
0.75
0.01
2
300
50
20
10
150
0.965
1
1
1
same as fuzzy rule system
rule specification file
output rule file (this is the main product)
fitness shift (1 = shift min. to 0.1, 0 = no shift)
two-point crossover
crossover rate
mutation rate
what’s being evolved (0=fuz. rules, 1=0+strt-end, 2=1+types)
max no. of generations
population size
maximum number of rules allowed
number of divisions for start and end points
number of patterns
acceptable correct portion (5 errors max for 150 patterns)
averaging flag (1 = average)
defuzz flag (1 = no overlap)
summation flag (1 = max value from one rule firing is used)
Example of Rule Specification File
41
sepalLength 3 0.4 1.0
leftTriangle 0.4 0.8
Triangle 0.5 0.9
rightTriangle 0.6 1.0
sepalWidth 3 0.0 0.6
leftTriangle 0.0 0.3
Triangle 0.15 0.45
rightTriangle 0.3 0.6
petalLength 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.2 0.7
rightTriangle 0.4 1.0
petalWidth 3 0.0 0.4
leftTriangle 0.0 0.2
Triangle 0.1 0.3
rightTriangle 0.2 0.4
output 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.3 0.7
rightTriangle 0.5 1.0
11111
template for rule (may be any five digits)
4
<-number of rules
4 1
sepalLength 3 0.4 1.0
leftTriangle 0.4 0.8
Triangle 0.5 0.9
rightTriangle 0.6 1.0
sepalWidth 3 0.0 0.6
leftTriangle 0.0 0.3
Triangle 0.15 0.45
rightTriangle 0.3 0.6
petalLength 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.2 0.7
rightTriangle 0.4 1.0
petalWidth 3 0.0 0.4
leftTriangle 0.0 0.2
Triangle 0.1 0.3
rightTriangle 0.2 0.4
output 3 0.0 1.0
leftTriangle 0.0 0.4
Triangle 0.3 0.7
rightTriangle 0.5 1.0
1 0 -1 -1 -1
-2 -1 -1 -1 -2
-3 -2 2 0 2
3 0 3 -3 -3
generation: 42
fitness=0.973333
Example of Output Rule File
(Evolved rule set only)
<-rules
Comments on previous output file
Negative numbers in rule file outputs are OK; complement is taken.
Only four rules were needed to get 146 out of 150 correct. (This is
from the fitness value. We don’t know which ones are wrong until we
run classification.)
Only 42 generations of the GA were used.
After generating rules, run the classification phase.
Fuzzy Logic Run File for
Classification
Type c at the prompt to run classification.
Uses the run file fl.run:
result.rul
output rule file from GA phase used to classify
iris.dat
data file as before
iris.out
the rules in words
result_4.out
detailed results, with mistakes indicated
1
averaging flag
1
defuzzification parameter
1
summation flag
Chapter 9
Computational Intelligence
Implementations
Fuzzy Evolutionary Fuzzy Rule
System
Implementation issues:
Which components to use
How to combine core components to best solve the problem
The fuzzy evolutionary fuzzy rule system (FEFRS) is formed by adding
fuzzy rules to the evolutionary fuzzy rule system that guide the GA’s
adaptation process.
Relationships between GA and FS in
EFRS (previous chapter)
Adaptation of Genetic Algorithms
GA used previously is static GA” parameters are fixed for all of run.
Goal is to balance (adapt) exploration versus exploitation over the
course of the GA run.
The four levels of GA adaptation:
environment, population, individual, and component levels
Varying the environment varies the fitness; this was discussed when
we talked about tracking dynamic systems.
We implement most adaptation at the population level; the crossover
or mutation rate is valid for the entire population.
Can also adapt at the individual or element level; is more complex.
Relationship between FS and GA in
FEFRS
Fuzzy Adaptation of GAs
Based on experience and understanding of GAs, we can write fuzzy
rules.
Inputs are performance measures of search process; outputs are GA
parameters.
Inputs can be things such as diversity, fitness variance, best fitness,
etc.
Outputs can be parameters, or changes in parameters. We focus on
crossover and mutation rates at the population level.
Should be used when computation cost of fitness evaluations is
higher than that of a fuzzy rule system.
Knowledge Elicitation






Authors’ experience with GAs allowed them to develop heuristics
such as “use high crossover rate at beginning when fitness is low.”
Knowledge elicitation: Process of extracting knowledge from human
experts for use in expert systems.
It is difficult, time consuming, complex and expensive.
Evolving major features of fuzzy expert systems generally makes
knowledge elicitation unnecessary.
Still need to identify input parameters needed to determine outputs.
Not needing knowledge elicitation can make CI applications less
expensive and faster to develop.
Fuzzy Evolutionary Fuzzy Rule System Implementation
Pre-designed fuzzy rule system added to the EFRS, based on experience with GAs;
it fine-tunes crossover and mutation rates.
Three input variables and two output variables are used, eight rules:
If Fitness is Low, then Mrate is Low and Crate is High
If Fitness is Medium, and Number is Low, then Mrate is Low and
Crate is High
If Fitness is Medium, and Number is Medium, then Mrate is
Medium, and Crate is Medium
If Number is High, and Variance is Medium, then Mrate is High,
and Crate is Low
If Fitness is High, and Number is Low, then Mrate is Low, and
Crate is High
If Fitness is High, and Number is Medium, then Mrate is
Medium, and Crate is Medium
If Number is High, and Variance is Low, then Mrate is High,
and Crate is Low
If Number is High, and Variance is High, then Mrate is Low,
and Crate is Low
On Previous Slide:



Fitness is best fitness of current generation
Number is number of generations that best fitness has
not improved
Variance is the variance of all fitnesses in population
Running the Fuzzy Evolutionary Fuzzy
Rule System
To run the system, type: flgafs flgafs.run
The main run file flgafs.run contains only two items:
ga.run
fl.run
The FL run file is the same as for the previous system.
The GA run file has two lines added.
GA Run File for FEFRS
iris.dat
base.rul
result.rul
ga_adapt.rul filename for fuzzy rule system
1
2
0.75
0.01
1
flag = 1 means fuzzy adaptation is to be used
2
1000
50
20
10
100
0.99
1
1
1
Fuzzy Rule System for GA Adaptation in FEFRS
ga_adapt.rul
8
3 2
Fitness 3 0.0 1.0
leftTriangle 0.0 0.7
Triangle 0.5 0.9
rightTriangle 0.7 1.0
Number 3 0 20
leftTriangle 0 6
Triangle 3 9
rightTriangle 6 12
Variance 3 0.0 0.2
leftTriangle 0.0 0.12
Triangle 0.1 0.14
rightTriangle 0.12 0.2
Mrate 3 0.005 0.1
leftTriangle 0.005 0.015
Triangle 0.01 0.02
rightTriangle 0.015 0.1
Crate 3 0.4 0.9
leftTriangle 0.48 0.65
Triangle 0.55 0.75
rightTriangle 0.65 0.83
1 0 0 1 3
2 1 0 1 3
2 2 0 2 2
0 3 2 3 1
3 1 0 1 3
3 2 0 2 2
0 3 1 3 1
0 3 3 1 3
FEFRS Conclusions





Entire system evolves simultaneously
Scales well for large and complex problems
Fuzzy system adapts crossover and mutation rates of GA
System evolves solution more quickly with all features
implemented
Method is applicable to a wide range of problems
Choosing the Best Tools
We will look at:
Strengths and weaknesses of various approaches
Modeling and optimization
Practical issues
Strengths and Weaknesses
How do we choose a particular tool?
A neural network might be favored if:
Large quantities of data
Evolutionary algorithms are often preferred if:
Optimization is being done
You might choose a fuzzy system if:
Small quantities of data
Linguistic and/or imprecise data (mainly) available
We believe that CI hybrids are generally built on a foundation of EC.
Modeling and Optimization
Many applications, such as control systems, involve modeling and
optimization.
Neural networks and fuzzy systems are good for modeling.
Evolutionary algorithms are often used for optimization.
NNs and EAs don’t need domain knowledge; FL does.
FL systems have a built-in explanation facility; NNs and EAs don’t.
Practical Issues
Because of resource constraints, you will usually have to develop
“sufficient” solutions (good enough, fast enough, and cheap enough).
Sometimes your project sponsor will tell you what to do!
Applying CI to Data Mining



Illustrates application of various methodologies of CI
Data Mining Definition: The process of using computational
algorithms to process large databases to find useful patterns and
relationships. (It is often referred to as knowledge discovery in
databases, or KDD.)
Must find previously unrecognized patterns or relationships



Reduce cost
Improve performance
Predict behavior or trends
Data Mining System Example


Work with huge stream of textual data
Discover and display related entities and patterns as they appear
over time

Establish associations across textual reports from multiple sources

Discover linked activities over time

Fitness could be dynamic, and knowledge driven
Diagram of CI Data Mining System
Data Mining System Example





Incorporates all three constituent methodologies of CI
At the core are clustering and classification methods, e.g., evolved
neural networks
Fuzzy logic shell is wrapped around core, with fuzzy attributes also
evolved
System adapts to users over time
Capable of providing explanations, and indicating confidence levels,
also evolved
Summary

Fuzzy evolutionary fuzzy rule systems discussed




GA used to design (evolve) fuzzy rule system
Fuzzy rule system used to adapt GA parameters
Optimal depth of evolution and fuzzification is problem
dependent
Relationships among components appear on next slide

Issues related to picking best tool for the job discussed

Example of CI approach to data mining presented
Relationships among fuzzy systems and
GAs in the FEFRS