Transcript Data mining
A brief introduction of Artificial Intelligence
Method and Fuzzy Logic Control
S. C. Chen
2009/07/17
Outline
Artificial Intelligence
Artificial Neural Network
Data Mining
Genetic Algorithm
Fuzzy Logic Control
Artificial intelligence
Thinking Machines
Agent
Robot
Artificial intelligence
AI (artificial intelligence) is a combination of computer
science, physiology, and philosophy.
AI is a broad topic, consisting of different fields, from
machine vision to expert systems. The element that the
fields of AI have in common is the creation of machines
that can "think".
In order to classify machines can thinking, it is necessary
to define intelligence for the machines.
Artificial intelligence
What does the degree of intelligence of machines to
consist of, for example, solving complex problems, or
making generalizations and relationships? And what
about perception and comprehension?
AI is also call machine intelligence that means people
who create a system to solve complex problems by
intelligence.
Research into the areas of learning, of language, and of
sensory perception have aided scientists in building
intelligent machines.
Artificial Intelligence---history
century
computer
Research of AI
Language of AI
1940~
1950~
1945
computer
(ENIAC)
1957 Fortran
1960~
1953 David
Chess
1956
Dartmouth
1980~
1990~
1977
1982
Fifth generation
computer
1991
Neural
computer
Universal
Declaration of
Knowledge
Engineering
1960
LISP
1973
PROLOG
1973
Production
system
1976
Theoretical
framework
Knowledge
representation
Expert System
1970~
1965
DENDRAL
1975
MYCIN
Artificial Intelligence---research areas
Natural Language Processing
Knowledge of performance
Intelligent Search
Reasoning
Perception problem
Pattern recognition
The management of imprecise and uncertain
Knowledge acquisition
Artificial Intelligence---research areas
Data mining
ANN (Artificial Neural Network)
Fuzzy Theory
Genetic Algorithm
Machine Learning
Artificial Neural Network
---Introduction
ANN (Artificial Neural Network) is also known as:
Parallel distributed processors
Adaptive systems
Self-organizing systems
Connectionism
Neurocomputers
NN (neural networks)
Artificial Neural Network
---Introduction
The definition of ANN:
ANN is a kind of computing system that is created by
hardware or software. ANN used a lot of artificial
neuron to simulate the ability of an organism neuron.
Artificial neuron is a simple simulation of an organism
neuron that gathered input data from external
environment or other artificial neuron. Afterward, to
obtain the result data by the procedure of complex
computing, than to output the result to external
environment or next artificial neuron.
Artificial Neural Network
---Neuron
a Inputs
W Weight
SUM Summation
f Activation function
t Output
Artificial Neural Network
---Neuron to Neural Network
Different problems have different combination method of network.
Using usage samples to train the network, and than changing the
weight of network foot by foot. Finally, making the value of output Y
to close to our purpose value.
Artificial Neural Network
---Neural Network Learning
Supervised Learning Network
Prediction, identify, classify
Unsupervised Learning Network
Clustering
Hybrid Learning Network
Associate Learning Network
Data acquisition, Noise filter
Optimization Application Network
Design, Scheduling
Artificial Neural Network
---Supervised Learning Network
According to the field of problem, providing the sample
include input and output data for training.
The network learning from input and output data to adjust
the weights of hidden layer to adaptive input and output.
This module just like mother to watch over children for
learning.
Back-propagation neural network is most representative in
the supervised learning network.
Artificial Neural Network
---Back-propagation neural network
The module of perceptron was be proposed in
1957. This module is lack for hidden layer of
neural network. So, the learning ability of NN is
much more restricted.
In 1985, P. Werbos, D. Parker, G. E. Hinton
proposed the learning algorithm of hidden layer.
The proposed learning algorithm makes BP-NN
to enter the new generation.
Artificial Neural Network
---Back-propagation neural network
Artificial Neural Network
---Back-propagation neural network
Examples:
Traveling Salesman Problem
3D Kohonen Feature Map
Data Mining
---Introduction
Data explosion problem
Automated data collection
tools and mature database
technology lead to
tremendous amounts of data
stored in databases, data
warehouses and other
information repositories
We are drowning in data,
but starving for knowledge!
Data Mining
---Introduction
Solution: Data warehousing and data mining
Data warehousing and on-line analytical processing
Extraction of interesting knowledge (rules, regularities, patterns,
constraints) from data in large databases
Data Mining
---Introduction, history of database
1960s:
Data collection, database creation, IMS (IP Multimedia Subsystem ) and
network DBMS (Database Manage System)
1970s:
Hierarchical and network database systems
Relational data model, relational DBMS implementation
1980s:
RDBMS, advanced data models (extended-relational, OO, deductive, etc.)
Application-oriented DBMS (spatial, temporal, engineering, etc.)
1990s:
Data mining, data warehousing, multimedia databases, and Web
databases
2000s
Stream data management and mining
Data mining and its applications
Web technology (XML, data integration) and global information systems
Data Mining
---Introduction
Data mining (knowledge discovery from data)
Extraction of interesting (non-trivial, implicit, previously unknown
and potentially useful) patterns or knowledge from huge amount
of data
Data mining: a misnomer?
Data mining is not only just data,but it can finding knowledge!!
Alternative names
Knowledge discovery (mining) in databases (KDD),
knowledge extraction, business intelligence, data/pattern
analysis, data archeology, data dredging, information harvesting,
etc.
Data Mining
---Introduction
Many people treat data mining as a synonym
for another popularly used term, Knowledge
Discovery from Data (KDD) — Generalized Data
mining
Alternatively, other view data mining as simply
an essential step in the process of knowledge
discovery — Narrowly Data mining
Data Mining
---Knowledge Discovery (KDD) Process
Evaluation and
Presentation
Data Mining
Patterns
Task-relevant
Data
Data Warehouse
Selection and
Transformation
Data Cleaning and
Data Integration
Databases
Data mining—core of
knowledge discovery
process
Data Mining
---KDD Process: Several Key Steps
1. Data cleaning
Remove noise and inconsistent data
may take 60% of effort!
2. Data integration
Where multiple data source may be combined
3. Data selection
Where data relevant to the analysis task are retrieved from the DB
4. Data transformation
Where data are transformed or consolidated into forms appropriate for mining by
performing summary or aggregation operations, for instance.
5. Data mining
Intelligent methods are applied in order to extract data patterns.
Choosing the mining algorithm(s) for searching patterns of interest
6. Pattern evaluation
To identify the truly interesting patterns representing knowledge based on some
interestingness measures.
7. Knowledge presentation
Where visualization and knowledge representation techniques are used to
present the mined knowledge to the user.
Data Mining
We adopt a broad view of data mining functionality:
Data mining is the process of discovering interesting
knowledge from large amounts of data stored in
databases, data warehouses, or other information
repositories.
Data Mining
--- Typical Data Mining System
Graphical User Interface
Pattern Evaluation
Knowledge
-Base
Data Mining Engine
Database or Data
Warehouse Server
OLAP:
On line analytical Processing
data cleaning, integration, and selection
Database
Data
Warehouse
World-Wide
Web
Other Info
Repositories
Data Mining and Business Intelligence
Increasing potential
to support
business decisions
Decision
Making
End User
Data Presentation
Business
Analyst
Visualization Techniques
Data Mining
Information Discovery
Data Exploration
Statistical Summary, Querying, and Reporting
Data
Analyst
Data Preprocessing/Integration, Data Warehouses
Data Sources
Paper, Files, Web documents, Scientific experiments, Database Systems
DBA
Data Mining
---What Kind of Data?
Relational databases
Data warehouses
Transactional databases
Advanced DB and information repositories
Object-oriented and object-relational databases
Spatial and Spatiotemporal Databases
Temporal, Sequence, and Time-Series Databases
Text databases and multimedia databases
Heterogeneous and legacy databases
Data Streams
WWW
Relational databases
Data warehouses
Transactional databases
Data Mining
---What kinds of patterns can be mined?
Data mining functionalities are used to specify the kinds of patterns
to be found in data mining tasks.
Data mining tasks can be classified into two categories:
Descriptive :
Characterize the general properties of the data in the database.
Predictive :
Perform inference on the current data in order to make predictions.
In some cases, users may have no idea regarding what kinds of
patterns in their data may be interesting, and hence may kind to
search for several different kinds of patterns in parallel.
Thus it is important to have a data mining system that can mine
multiple kinds of patterns to accommodate different user expectations
or applications.
Data Mining
---What kinds of patterns can be mined?
Data mining functionalities, and the kinds of
patterns they can discover, are described below:
Concept description: Characterization and discrimination
Association Analysis
Classification and Prediction
Cluster analysis
Outlier analysis
Trend and evolution analysis
Data Mining
---Association analysis
From transactional databases, RDBMS or other
large amounts of data item of storage systems.
Finding the interested pattern and frequent
pattern to analysis the associations and the
correlations between each data item.
this associations doesn’t present directly in data
The best example is to ensure association rules.
Data Mining
--- Data Cube Aggregation
Data cubes store multidimensional aggregated
information.
For example:
Data Mining
---Potential Applications
Data analysis and decision support
Market analysis and management
Target marketing, customer relationship management (CRM), market
basket analysis, cross selling, market segmentation
Risk analysis and management
Forecasting, customer retention, improved underwriting, quality
control, competitive analysis
Fraud detection and detection of unusual patterns (outliers)
Other Applications
Text mining (news group, email, documents)
Web mining
Bioinformatics and bio-data analysis
Genetic Algorithm
---Introduction
Genetic algorithms are a part of evolutionary
computing, which is a rapidly growing area of
artificial intelligence.
Based on Darwinian principles of biological
evolution.
First proposed by Prof. John Holland in 1975,
and his colleague at Univ. of Michigan.
Genetic Algorithm
---Introduction
Chromosomes are strings of DNA and serves as a
model for the whole organism.
A chromosome consists of genes.
Each gene encodes a trait.
Complete set of genetic material (all chromosomes) is
called genome.
Particular set of genes in genome is called genotype.
Genetic Algorithm
---Encoding
The chromosome should in some way contain information
about solution which it represents.
The most used way of encoding is a binary string.
Chromosome 1 1101100100110110
Chromosome 2 1101111000011110
Each bit in this string can represent some characteristic of the
solution.
One can encode directly integer or real numbers.
Genetic Algorithm
---Procedure
The initial population
generate randomly
Evaluating
the fitness function
YES
Optimal solution
Is reach
the condition?
NO
Reproduction
Crossover
Mutation
Genetic Algorithm
---Fitness function
Algorithm is started with a set of solutions
(represented by chromosomes) called population.
Solutions from one population are taken and used to
form a new population.
The new population (offspring) will be better than
the old one (parent).
Solutions which are selected to form new solutions
are selected according to their fitness - the more
suitable they are the more chances they have to
reproduce.
Genetic Algorithm
---Reproduction
Reproduction is a kind of computing process that
used to decide population elimination by the
fitness degree. Fitness degree is calculate by
fitness function.
Selection methods:
Roulette Wheel Selection
Competitive Selection
Genetic Algorithm
---Crossover
Crossover selects genes from parent chromosomes
and creates a new offspring.
Chromosome 111011 | 00100110110
Chromosome 211011 | 11000011110
Offspring 1
11011 | 11000011110
Offspring 2
11011 | 00100110110
“ | “ is the crossover point
Genetic Algorithm
---Crossover
Single point crossover: 11001011+11011111 = 11001111
Two point crossover: 11001011 + 11011111 = 11011111
Uniform crossover: 11001011 + 11011101 = 11011111
Arithmetic crossover: 11001011 + 11011111 = 11001001
Genetic Algorithm
---Mutation
Prevent falling all solutions in population into a local
optimum of solved problem
Mutation changes randomly the new offspring.
Original offspring 11101111000011110
Mutated offspring 11100111000011110
Original offspring 21101100100110110
Mutated offspring 21101101100110110
Genetic Algorithm
---Roulette Wheel Selection
Parents are selected according to their fitness.
The better the chromosomes are, the more chances to be
selected they have.
Fuzzy logic control
Introduction
Fuzzify
Rule-based
Inference
Defuzzification
Fuzzy logic control---Part1
---Introduction
1965 Fuzzy Set (Prof. Lotfi A.Zadeh,UCB)
1966 Fuzzy logic (Dr. Peter N.Marinos, Bell Lab)
1972 Fuzzy Measure
Fuzzy Set
(Prof.Michio Sugeno)
Fuzzy Event
Crisp
Element
Fuzzy logic control
---Introduction
Knowledge Representation
example: age (Man Old)
traditional
Membership Function
Age (Man Gt 60)
1
30
60
Ages
Fuzzy logic control
---Introduction
Fuzzy
Age (Man Old)
Membership Function
1
0.5
30
60
Ages
Fuzzy Logic
A( x) : membership of the element x in the fuzzy subset A
x : an element of the reference set E
A, B, Fuzzy subset of E
a A ( x), b B ( x), a, b[0,1]
a b MIN ( a, b)
a b MAX ( a, b)
a 1 a
a b ( a b) ( a b)
Fuzzy Logic Control
---Introduction
Commutativity a ()b b ()a
Associativ e (a b) c a (b c)
Distributi vity a (b c) (a b) (a c)
( a ) a
DeMorgan ' stheorems
(a b) a b
(a b) a b
Fuzzy Logic Control
---Introduction
二值理論推論形式
(事實) 麻雀是鳥
(規則) 鳥會飛
(結論) 麻雀會飛
AI Language as LISP,Prolog “Pattern Matching”
Fuzzy推論形式:
(事實) 這番茄很紅
(規則) 蕃茄若是紅了就熟了
(結論) 這蕃茄很熟了
Fuzzy Logic Control
---Introduction
(facts) X is A
(rule) if X is A then Y is B
希望得到的結論是
(result) Y is B
A
1
Mamdani 法
A
1
B
B
0
0
Fuzzy Logic Control---Part2
---Architecture
Fuzzy Logic Control
---Crisp set
Set A, whose elements are x1,…. xn , is always written as
A={x1,…,xn}
A={x | P(x) } ,x has the property P
Set A is defined by its characteristic function,
A ( x)
1
0
for
for
A
xA
xA
An example set A={1,2,3,4,5}, U={0,1,2,3,4,5,6,7,8,9}. z(x) is
a characteristic function of set A.
z(1)=1, z(2)=1, z(3)=1, z(4)=1, z(5)=1, z(6)=0, z(0)=0
z(7)=0, z(9)=0
Fuzzy Logic Control
---Definition
Membership function denoted as
, A 0 A 1
There are three stand type of membership
functions, triangle, trapezoid and Gaussian.
A fuzzy set F in X may be represented as
F ( x, F ( x)) | x X
When X is continuous:
F F ( x) / x
X
When X is discrete:
F F ( x) / x
X
Fuzzy Logic Control
---Basic characteristics of fuzzy sets
1.
2.
3.
Vertical dimension: height, normalization
(maximum form: at least one element with 1.0
membership and one element with
membership 0).
Horizontal dimension: universal discourse,
support sets, alpha cuts.
Representation schemes: membership function,
ordered set of pairs, polynomial-like (integrallike).
Fuzzy Logic Control
---BASIC CONCEPTS
1. Support : supp A {x X | μ A (x) 0}.
2. Height : the largest membership grade attained by any element
in that set.
3. Normalized fuzzy set : at least one of its elements attains the
maximum possible membership grade.
4. - cut : A {x X | A ( x ) }.
5. fuzzy number : a convex and normalized fuzzy set defined on
R whose membership function is piecewise continuous .
6. scalar cardinalit y : A
xX
A
( x ).
7. fuzzy cardinalit y : a fuzzy set (fuzzy number) defined on N
whose membership function is defined by
A~ ( A ) , for all in the level set of A
8. subset : A ( x ) B ( x ) ─ A B.
proper subset.
9. equivalenc e : A ( x ) B ( x ) ─ A B.
10. complement : A ( x ) 1 A ( x ).
11. union : AB ( x ) max[ A ( x ), B ( x )]
12. intersecti on : AB ( x ) min[ A ( x ), B ( x )]
13. extension principle :
A 1/ x1 2 / x2 n / xn ,
f(A) f( 1 / x1 2 / x2 n / xn )
1 / f(x 1 ) 2 / f(x 2 ) n / f(x n ).
Fuzzy Logic Control
---Types of Membership Functions
1.
2.
Linear type: linear/step functions.
Approximating an unknown or poorly
understood concept that is not a fuzzy number.
(often expressed as shouldered sets)
Triangular type:
often used to model process control systems.
Fuzzy Logic Control
---Types of Membership Functions
when you decompose a variable into fuzzy sets,
the amount of overlap must vary between 10%
to 50%.
In modeling dynamic systems, it can
approximate their behaviors to nearly any
degree of precision.
0
( x a ) /(b a )
Tri ( x; a, b, c)
(c x) /( c b)
0
xa
a xb
bxc
xc
Fuzzy Logic Control
---Types of Membership Functions
3. Trapezoidal Type:
0
( x a ) /( b a )
Tra ( x; a, b, c, d ) 1
( d x ) /( d c )
0
xa
a xb
b xc
c xd
xd
Fuzzy Logic Control
---Types of Membership Functions
4. Sigmoid/Logistic Type:
* modeling population dynamics where the sampling of
individual values approximates a continuous random
variable.
* frequency (proportional) representation: usually, most,
always.
0
2( x a) /( c a) 2
S ( x; a, b, c)
2
1
2
((
x
c
)
/(
c
a
))
1
xa
a xb
bxc
xc
Fuzzy Logic Control
1.
2.
3.
---Types of Membership Functions
Fuzzy numbers and around representation: around,
close to, few, some.
PI, Beta, Gaussian fuzzy sets (bell-shaped): the slope
and width of the bell curves indicate the degree of
compactness associated with the fuzzy number.
PI curves: is not asymptotic. Zero point is at a discrete
and specified point.
S ( x; c b, c b / 2, c)
( x; b, c)
1 S ( x; c, c b / 2, c b)
x
x
Fuzzy Logic Control
---Types of Membership Functions
4. Beta curves: more tightly compacted than PI.
5. Similar to beta curves, but the slope goes to zero very
quickly with a very short tail.
6. Irregularly shaped and arbitrary fuzzy sets: (domain
value, membership) pairs linear interpolation.
B ( x; c, b) (1 (( x c ) / b) )
2
G ( x; k , c ) e
k (c x )2
1
Fuzzy Logic Control
---Concept of membership function
Matching
degree μ
1
μ=1
0.8
μ
μ
1
1
Membership function 1
0
Matching
degree μ
Matching degree μ
gradually changing
between 0 and 1
a
b
c
(a) Triangular function
1
Membership function 2
0.3
0
a
b
c
(b) Trapezoid function
d
Fuzzy Logic Control
---An example of fuzzy set
A (x)
The temp is okay
The temp is cold
The temp is hot
1
0
18
23
32
Temperature 。C
There three linguistic variables are temp is cold, temp is okay and temp is hot.
Each of linguistic variable means a membership function.
the temp is okay Ab (x)
0 0.2 0.47 1 0.82 0.63 0.38 0.2 0
20
23 25
27
29
30 32
18 19
Ab (x)
Fuzzy Logic Control
---Extension principle
The extension principle was introduced by Zadeh in 1975
and is an important tool in fuzzy set theory
f x y f A B A xU A ( x) / x
B f ( A) f
xU
A ( x) / x
A ( x1 ) / y1 A ( x2 ) / y 2 A ( xn ) / y n B ( y)
B ( y) max A ( x)
x f 1 ( y )
y V
min A1 ( x1 ),...., Ar ( xr )
( x1... xrsup
1
f ( y ))
B ( y)
1
0 if
f ( y)
Fuzzy Logic Control
---Extension principle
y f ( x) x 4
U={-3,-2,-1,0,1,2}
x
A( x )
-3
-2
-1
0
1
2
0.5
0.6
1.0
0.9
0.4
0.1
0.9 1 0.6 0.5
B
0 1 16 81
y f ( x) x 4
81
16
1
0
1
16
B (y)
max{0.5}=0.5
max{0.6,0.1}=0.6
max{1,0.4}=1
max{0.9}=0.9
max={1,0.4}=1
max={0.6,0.1}=0.6
Fuzzy Logic Control
---Extension principle
A1 x1X 1 A1 ( x1) / x1
A2 x 2X 2 A2 ( x2) / x2
x1
A1 ( x1)
x2
A2 ( x2)
-1
-1
0
0
1
1
0.5
0.5
0.1
0.1
0.9
0.9
-2
2
-2
2
-2
2
0.4
1.0
0.4
1.0
0.4
1.0
y f ( x1, x 2)
x12 x 2
V={-2,-1,2,3}
f ( A1, A 2 ) ( y ) B ( y )
-1
3
-2
2
-1
3
max{0.4,0.4}=0.4
max{0.5,0.9}=0.9
max{0.1}=0.1
max{0.1}=0.1
max{0.4,0.4}=0.4
max{0.5,0.9}=0.9
B (1) max[min{ A1 (1), A2 (2)}, min{ A1 (1), A2 (2)}]
max[min( 0.5,0.4), min( 0.9,0.4)] 0.4
B
0.1 0.4 0.1 0.9
2 1 2
3
Fuzzy Logic Control
---Rules
There are two parts in a fuzzy rule: an IF part
(antecedent) and a THEN part (consequent). We present
an illustrative example to explain the procedure of fuzzy
inference. Consider an air conditioning system. The
intensity of cooling (fuzzy output) might be determined by
temperature (fuzzy input) by the following fuzzy rule:
IF the temperature is high THEN the intensity of cooling
is strong
Fuzzy Logic Control
---Rules
Again, we give a general express for fuzzy rules
with multi-dimensional inputs as follows:
p
q
u
IF X1 is A1 AND X2 is A2 AND ……Xn is An THEN Y is Bv
Fuzzy Logic Control
---Rules
IF Part
Fuzzy Inference
THEN Part
Temperature is moderate
Cooling is moderate
0.50.
5.5
18
22
26
30
28℃
(crisp input )
Temp (℃)
30
45
55 70
Intensity of
cooling (%)
Fuzzy output (gray area)
Figure 5’: An illustrative example of getting fuzzy output from a crisp input
THEN Part
IF Part
Temperature is high
28
35
Cooling is strong
Temp (℃)
75
90
Intensity of
cooling (%)
(a) Visual description of fuzzy rule: “IF temperature is high THEN cooling is strong”
Temperature is moderate
18
22 25 30
Temperature is low
Temp (℃)
12
28
Temp (℃)
(b) Fuzzy expressions of “Temperature is moderate” and “Temperature
is low” in temperature input dimension
Fuzzy Logic Control
---Inference
The antecedent of a fuzzy rule uses logic “AND”
manipulation (conjunction) to combine the fuzzy input
variables X1, X2, …, Xn.. Conceptually, we use
“minimum” operation to handle the conjunction of the
fuzzy input variables. Consider a fuzzy rule Ri. The
overall matching degree for this particular fuzzy rule is
obtained by the following formula
X , R min { X 1 , X 2 , , Xn }
i
1
Fuzzy Logic Control
---Inference
μ
μ
Clipped to
0.7
0.7
10
20
30
(a) The clipping method
μ
0.7
μ
Scaled to
0.7
(b) The scaling method
0.8
= 0.3
0.3
min
0.9
0.4
= 0.4
min
Input
Input
Fuzzy Logic Control
---Inference
•Trigger the fuzzy rules
•Using clip method
Fuzzy Logic Control
---Inference
μ
μ
Union
μ
IF Part
THEN Part
Fuzzy output of
Rule 1
Rule 1
min
The final overall fuzzy
output
Union
min
Rule 2
Defuzzification output
Fuzzy variable
1
Fuzzy variable
2
crisp input 1
crisp input 2
Fuzzy output of Rule
2
Figure 8: A conceptual diagram to illustrate the procedure of the fuzzy expert system
(taken from [/?ref]).
Fuzzy Logic Control
---Defuzzification
Two major defuzzification methods are often
used: the Mean of Maximum (MOM) method and
the Center of Area (COA) method. The MOM
computes the average of output values with
maximum matching degrees. The formula for the
MOM defuzzification is of the form.
y*
MOM ( A)
y*P
P
p y* | A ( y*) sup A ( y )
y
Fuzzy Logic Control
---Defuzzification
The COA method computes the weighted average of an
entire set, which is given by
y
A ( yi ) yi
i
A ( yi )
i
N
CA
i 1
N
xi A xi
i 1
A xi
Fuzzy Logic Control
---Defuzzification
μ
μ
Defuzzification output
Defuzzification output
(a) The COA method
(b) The MOM method
Homework
Implementation of Fuzzy Logic System using
java, c++, or matlab, and then using an example
to test the system.
Using source code from internet to create an
example. Afterwards, to explain the source code
more detail and the created example.