UNIT II SEARCH METHODS AND VISUALIZATION
Search by simulated Annealing – Stochastic, Adaptive search by Evaluation – Evaluation
Strategies – Genetic Algorithm – Genetic Programming – Visualization – Classification
of Visual Data Analysis Techniques – Data Types – Visualization Techniques –
Interaction techniques – Specific Visual data analysis Techniques
SEARCH BY SIMULATED ANNEALING
Simulated annealing (SA) is a probabilistic technique for approximating the global
optimum of a given function. Specifically, it is a metaheuristic to approximate global
optimization in a large search space for an optimization problem. For large numbers of
local optima, SA can find the global optima. It is often used when the search space is
discrete (for example the traveling salesman problem, the boolean satisfiability problem,
protein structure prediction, and job-shop scheduling). For problems where finding an
approximate global optimum is more important than finding a precise local optimum in a
fixed amount of time, simulated annealing may be preferable to exact algorithms such as
gradient descent or branch and bound.
The name of the algorithm comes from annealing in metallurgy, a technique
involving heating and controlled cooling of a material to alter its physical properties.
Both are attributes of the material that depend on their thermodynamic free energy.
Heating and cooling the material affects both the temperature and the thermodynamic
free energy or Gibbs energy. Simulated annealing can be used for very hard
computational optimization problems where exact algorithms fail; even though it usually
achieves an approximate solution to the global minimum, it could be enough for many
practical problems.
The problems solved by SA are currently formulated by an objective function of
many variables, subject to several mathematical constraints. In practice, the constraint
can be penalized as part of the objective function.
SIMULATED ANNEALING PROCESS
The state s of some physical systems, and the function E(s) to be minimized, is
analogous to the internal energy of the system in that state. The goal is to bring the
system, from an arbitrary initial state, to a state with the minimum possible energy.
The basic iteration
At each step, the simulated annealing heuristic considers some neighboring state
s* of the current state s, and probabilistically decides between moving the system to state
s* or staying in state s. These probabilities ultimately lead the system to move to states of
lower energy. Typically this step is repeated until the system reaches a state that is good
enough for the application, or until a given computation budget has been exhausted.
The neighbors of a state
Optimization of a solution involves evaluating the neighbors of a state of the
problem, which are new states produced through conservatively altering a given state. For
example, in the traveling salesman problem each state is typically defined as a
permutation of the cities to be visited, and the neighbors of any state are the set of
permutations produced by swapping any two of these cities. The well-defined way in
which the states are altered to produce neighboring states is called a "move", and
different moves give different sets of neighboring states. These moves usually result in
minimal alterations of the last state, in an attempt to progressively improve the solution
through iteratively improving its parts (such as the city connections in the traveling
salesman problem).
Simple heuristics like hill climbing, which move by finding better neighbor after
better neighbor and stop when they have reached a solution which has no neighbors that
are better solutions, cannot guarantee to lead to any of the existing better solutions – their
outcome may easily be just a local optimum, while the actual best solution would be a
global optimum that could be different. Metaheuristics use the neighbors of a solution as
a way to explore the solution space, and although they prefer better neighbors, they also
accept worse neighbors in order to avoid getting stuck in local optima; they can find the
global optimum if run for a long enough amount of time.
Acceptance probabilities
The probability of making the transition from the current state s to a candidate new
state snew is specified by an acceptance probability function P(e, enew, T), that depends on
the energies e = E(s) and enew = E(snew) of the two states, and on a global time-varying
parameter T called the temperature. States with a smaller energy are better than those
with a greater energy. The probability function P must be positive even when enew is
greater than e. This feature prevents the method from becoming stuck at a local minimum
that is worse than the global one.
When T tends to zero, the probability P(e, enew, T) must tend to zero if enew > e and
to a positive value otherwise. For sufficiently small values of T, the system will then
increasingly favor moves that go "downhill" (i.e., to lower energy values), and avoid
those that go "uphill." With T=0 the procedure reduces to the greedy algorithm, which
makes only the downhill transitions.
In the original description of simulated annealing, the probability P(e, enew, T) was
equal to 1 when enew < e i.e., the procedure always moved downhill when it found a way
to do so, irrespective of the temperature. Many descriptions and implementations of
simulated annealing still take this condition as part of the method's definition. However,
this condition is not essential for the method to work.
The P function is usually chosen so that the probability of accepting a move
decreases when the difference enew - e increases—that is, small uphill moves are more
likely than large ones. However, this requirement is not strictly necessary, provided that
the above requirements are met.
Given these properties, the temperature T plays a crucial role in controlling the
evolution of the state s of the system with regard to its sensitivity to the variations of
system energies. To be precise, for a large T, the evolution of s is sensitive to coarser
energy variations, while it is sensitive to finer energy variations when T is small.
The annealing schedule
The name and inspiration of the algorithm demand an interesting feature related to
the temperature variation to be embedded in the operational characteristics of the
algorithm. This necessitates a gradual reduction of the temperature as the simulation
proceeds. The algorithm starts initially with T set to a high value (or infinity), and then it
is decreased at each step following some annealing schedule—which may be specified by
the user but must end with T=0 towards the end of the allotted time budget. In this way,
the system is expected to wander initially towards a broad region of the search space
containing good solutions, ignoring small features of the energy function; then drift
towards low-energy regions that become narrower and narrower, and finally move
downhill according to the steepest descent heuristic.
For any given finite problem, the probability that the simulated annealing
algorithm terminates with a global optimal solution approaches 1 as the annealing
schedule is extended. This theoretical result, however, is not particularly helpful, since
the time required to ensure a significant probability of success will usually exceed the
time required for a complete search of the solution space.
Pseudocode
The following pseudocode presents the simulated annealing heuristic as described
above. It starts from a state s0 and continues until a maximum of kmax steps have been
taken. In the process, the call neighbour(s) should generate a randomly chosen neighbour
of a given state s; the call random(0, 1) should pick and return a value in the range [0, 1],
uniformly at random. The annealing schedule is defined by the call temperature(r),
which should yield the temperature to use, given the fraction r of the time budget that has
been expended so far.
● Let s = s0
● For k = 0 through kmax (exclusive):
● T ← temperature( 1 - (k+1)/kmax )
● Pick a random neighbour, snew ← neighbour(s)
● If P(E(s), E(snew), T) ≥ random(0, 1):
● s ← snew
● Output: the final state s
Example: Traveling Salesman Problem:
The dataset used in this exercise is a symmetric TSP which means that the distance
from city i to city j is the same distance from city j to city i for all cities in the route. The
dataset can be found here, along with other TSP datasets.
Each node in the Traveling Salesman problem dataset represents a city. The TSP
comes with the following constraints:
● The starting node must be the end node.
● Each node must be visited once and only once.
These nodes are connected to form routes. Each route represents a possible
solution/candidate/individual. The fitness of these individuals is taken to be the inverse of
the total distance traveled taking that route. The distance traveled between node i and
node j is given by:
where i ≠ j. We take fitness to be the inverse of the distance traveled in the entire
route (Fij = 1/dij) because we want to maximize fitness when our algorithm selects a
candidate. An example of an individual representation of a route with 10 cities is
“1–4–3–2–5–6–7–8–9–10”.
Simulated Annealing
This method has been commonly referred to as one of the oldest metaheuristic
models². It has great performance in avoiding local minima. In order to do this, the
algorithm accepts worse candidates with a probability dependent on the temperature (a
control variable) and the fitness difference given by the formula below:
p — the probability of accepting the new solution candidate, y.
x — initial solution candidate (In this case, that is a route)
y — new solution candidate
f(x) — is the function that measures the performance of the solution candidate
(Fitness function)
T — the temperature which is the control parameter.
The Algorithm implemented can be summarized by the flowchart below:
The code below shows how to calculate the fitness:
def get_cost(state):
"""Calculates cost/fitness for the solution/route."""
distance = 0
for i in range(len(state)):
from_city = state[i]
to_city = None
if i+1 < len(state):
to_city = state[i+1]
else:
to_city = state[0]
distance += data.get_weight(from_city, to_city)
fitness = 1/float(distance)
return fitness
Because our probability of accepting worse new candidates is dependent on the
temperature, as the temperature cools, eventually we will only accept candidates that are
better than the present one.
Generating Candidate Solutions
Because the simulated annealing algorithm compares different candidate solutions
and decides which one is taken at each iteration, it is necessary to be able to generate
these solutions. In this article, four methods were used, three of which were inspired
from:
● Inverse operator (x): This changes the order of routes between two randomly
selected nodes i and j. Where i,j ≤ 0 ≤ n such that x¹[i] = x[j], x¹[i+1] = x[j-1], etc.
Hopefully, an example makes it clearer. Let’s say the initial route is
‘1–2–3–4–5–6’, this operator could produce ‘1–4–3–2–5–6’. The random
positions selected in this example are city 2 and city 5. The minimum integer
between i and j will be ‘i’ and the maximum would be taken as ‘j’.
def inverse(state):
"Inverses the order of cities in a route between node one and node two"
node_one = [Link](state)
new_list = list(filter(lambda city: city != node_one, state))
node_two = [Link](new_list)
state[min(node_one,node_two):max(node_one,node_two)]=
state[min(node_one,node_two):max(node_one,node_two)][::-1]
return state
● Swap operator (x): This exchanges the position of two cities in a route. Two
positions, i and j are selected at random and the cities in these positions are
swapped with each other. ‘1–2–3–4–5–6’ could become ‘1–5–3–4–2–6’.
def swap(state):
"Swap cities at positions i and j with each other"
pos_one = [Link](range(len(state)))
pos_two = [Link](range(len(state)))
state[pos_one], state[pos_two] = state[pos_two], state[pos_one]
return state
● Insert operator(x): · This operator selects a city at random position ‘i’ and moves
it to a random position ‘j’ elsewhere in the route.
def insert(state):
"Insert city at node j before node i"
node_j = [Link](state)
[Link](node_j)
node_i = [Link](state)
index = [Link](node_i)
[Link](index, node_j)
return state
● Insert subroutes(x): This is similar to the swap route operator but rather than
inserting a city in a different position, a range of cities are selected as a sub route
and inserted at a random position.
def swap_routes(state):
"Select a subroute from a to b and insert it at another position in the route"
subroute_a = [Link](range(len(state)))
subroute_b = [Link](range(len(state)))
subroute = state[min(subroute_a,subroute_b):max(subroute_a, subroute_b)]
del state[min(subroute_a,subroute_b):max(subroute_a, subroute_b)]
insert_pos = [Link](range(len(state)))
for i in subroute:
[Link](insert_pos, i)
return state
Termination Condition
While several simulated annealing algorithms terminate once the temperature
reaches 0. To have a very large search space, this algorithm only terminates once a
candidate has been selected 1500 times and the same fitness score has occurred 150000
times.
STOCHASTIC, ADAPTIVE SEARCH BY EVOLUTION
Computer algorithms modeling the search processes of natural evolution are crude
simplifications of biological reality. However, during nearly three decades of research
and application, they have turned out to yield robust, flexible and efficient algorithms for
solving a wide range of optimization problems.
Variation and Selection:
An Evolutionary Algorithm Scheme Evolutionary algorithms (EAs) simulate a
collective learning process within a population of individuals. More advanced EAs even
rely on competition, cooperation and learning among several populations. Each
individual represents a point (structure) in the search space of potential solutions to a
specific machine learning problem. After arbitrary initialization of the population, the set
of individuals evolves toward better and better regions of the search space by means of
partly stochastic processes while the environment provides feedback information (quality,
fitness) about the search points:
● Selection: It is deterministic in some algorithms, favors those individuals of better
fitness to reproduce more often than those of lower fitness.
● Mutation: introduces innovation by random variation of the individual structures.
● Recombination: which is omitted in some EA realizations, allows the mixing of
parental genetic information while passing it to their descendants.
Figure shows the basic scheme of an evolutionary algorithm. Let G denote the
search space and let η : G —> K be the fitness function that assigns a real value η(σi) to
each individual structure encoded by a "genome" gi ∈ G. A population G(t) = {g1{t),...
,gμ(t)} at generation t is described by a (multi) set of μ individuals. From a parent
population of size μ > 1 an offspring population of size λ > 1 is created by means of
recombination and mutation at each generation.
A recombination operator ωrec : Gμ → Gλ, controlled by additional parameters
Θ(ωrec), generates λ structures as a result of combining the genetic information of μ
individuals.
A mutation operator ωmut : Gλ → Gλ modifies a subpopulation of λ individuals,
again being controlled by parameters Θ(ωmut)- All the newly created solutions of the
population set G" are evaluated. The selection operator σ chooses the parent population
for the next generation. The selection pool consists of the λ generated offspring. In some
cases, the parents are also part of the selection pool, denoted by the extension set Q =
G(t). Otherwise, the extended selection set Q is empty, Q = Ø. Therefore, the selection
operator is defined as σ : Gλ x Kλ → Gμ or σ : Gλ+μ x Kλ+μ → Gμ. The termination criterion
τ either makes the evolution loop stop after a predefined number of generations, or when
an individual exceeding a maximum fitness value has been found.
The Role of Randomness in Evolutionary Learning
The principle dynamic elements that evolutionary algorithms simulate are
innovation caused by mutation combined with natural selection. Driving a search process
by randomness is, in some way, the most general procedure that can be designed.
Increasing order among the population of solutions and causing learning by randomly
changing the solution encoding structures may look counterintuitive. However, random
changes in combination with fitness-based selection make a formidable and more flexible
search paradigm as demonstrated by nature's optimization methods. On average, it is
better to explore a search space non-deterministically. This is independent of whether the
search space is small enough to allow exhaustive search or whether it is so large that only
sampling can reasonably cover it. At each location in a non-deterministic search, the
algorithm has the choice of where to go next. Meaning that stochastic search — in
combination with a selection procedure which might also be non-deterministic, at least to
some degree — is used as a major tool not only to explore but also to exploit the search
space. In simulated annealing the Metropolis algorithm also relies on the stochastic
search of the Perturb procedure which generates a new solution that competes with the
current (best) solution. Evolutionary algorithms use operators like mutation and
recombination (in some EA variants even more "genetic" operators are used) to produce
new variants of already achieved solutions. These operators rely heavily on randomness:
mutation may randomly change parameter settings of a solution encoding vector, and also
the mixing of genes by recombination of two solutions is totally non-deterministic.
EA-based search algorithms rely on evolution's "creative potential" which is largely due
to a controlled degree of randomness.
EVOLUTION STRATEGIES
Evolution Strategies (ES) were invented during the 60s and 70s as a technique of
evolutionary experimentation for solving complex optimization problems, mainly within
engineering domains. The preferred ES data structures are vectors of real numbers.
Specifically tailored mutation operators are used to produce slight variations on the
vector elements by adding normally distributed numbers (with mean zero) to each of the
components. Recombination operators have been designed for the interchange or mixing
of "genes" between two or more vectors. These recombinations range from simply
swapping respective components among two vectors to component-wise computation of
means. Evolution Strategies have developed sophisticated methods of selection, which
are especially important when the evolution scheme involves several subpopulations.
Representation of Individuals
The basic data structures today's Evolution Strategies deal with, and around which
most of the ES theory is built, are vectors of real numbers representing a set of
parameters to be optimized. Therefore, an ES chromosome g, can be simply defined as
follows:
g = (p1,p2, .... ,pn) with pi ∈ K
Usually the pi are referred to as the object parameters. In the most elementary
versions of Evolution Strategies only these parameter vectors are subject to evolution.
However, in order to be able to solve more complex optimization tasks it turns out to be
advantageous to keep a second vector of strategy parameters, which are used as variances
to control the range of mutations on the object parameters. Thus we can extend our
definition for an ES chromosome g the following way:
g = (p,s) = (p1,p2, .... ,pn), (s1,s2, .... ,sn) with pi , si ∈ K
Now the ES chromosome vector is two-fold, with each Sj representing the mutation
variance for the corresponding ft. The additional control parameters s may be considered
as an internal model of the optimization environment
ES Mutations
We start our journey at some distance from the top plateau with one individual,
depicted as a gray spot. From the genotype, an ES chromosome containing the x- and
y-coordinates of this individual, we generate five mutated offspring(black spot), the
locations of which are somewhat close to the parent individual. This set of points
comprises our initial population on which we will perform a selection-mutation
procedure as follows. We choose the individual currently with the highest location, from
which we generate another five children, and continue the same way by selecting the
best, generating mutants, etc.
Repeatedly choosing the best individual and generating mutated offspring,
gradually makes the population move upwards, like following a gradient to the top
plateau. A closer look at Figure reveals that smaller mutations are prevalent, i.e. the
majority of mutants (children) are located near to the wildtype (parent).
Not only the object parameters, the coordinates in our example, but also the
strategy parameters, controlling the mutation step sizes, are subject to change. This effect
is also visible in the figure. Each strategy parameter controls the mutation step size, hence
the distance of the children from their parents.
Mutating the Object Parameters
Mutation is considered the major ES operator for variations on the chromosomes.
Mutations of the object and strategy parameters are accomplished in different ways.
Basically, ES mutation on a chromosome g = (p, s) can be described as follows:
gmut = (pmut ,smut) = (p +Ν0(s), α(s)).
Here Ν0(s) denotes normal distribution with mean zero and the vector of variances
s. α defines a function for adapting the strategy parameters. The variations on the object
parameters are to be applied to each vector element separately:
pmut = (pl +Ν0(s1)),......,pn +Ν0(sn))
The strategy parameters are adjusted in an analogous way as
smut = (α(s1), α(s2), …… , α(sn))
Let us assume that strategy parameters remain unchanged, i.e., we use the identity
mapping α(x) = x.
Figure graphically depicts this basic mutation scheme. Each strategy parameter
controls the mutation range for its respective object parameter. In order to have
mutations, prefer smaller changes to larger ones. Evolution Strategies use normal
(Gaussian) distributed random numbers that are added to the object parameters. The
characteristics of Gauss distributions, Νm(d) with mean m and standard deviation √d,
are their preference for numbers around mean m. Thus, in the case of m = 0, smaller
values close to zero are selected more often than values with greater distance to m.
Mutating the Strategy Parameters
There are two methods generally used for adapting the strategy parameters s of an
ES chromosome g = (p,s):
gmut = (pmut ,smut) = (p +Ν0(s), α(s)).
Here α defines a function for adapting the strategy parameters:
smut = (α(s1), α(s2), …… , α(sn))
Each strategy parameter controls the mutation range of its respective object
parameter, defining the variance for the normal distributed random values added to the
object parameters.
There are several methods for defining α which work fairly well in changing the
strategy parameters; this adaptation is usually referred to as Mutative Step size
Adaptation (MSA).
Here χ denotes a uniformly distributed random variable from the interval [0,1].
For n < 100 parameters, β values will be between 1.3 and 1.5. For β = 1.3 means that half
of the strategy parameters are multiplied by 1.3, the rest is multiplied by 0.77 = 1/1.3.
ES Recombinations
Recombination operators create new chromosomes by composing corresponding
parts of two or more chromosomes. For the binary case, where two ES chromosomes,
ga = (pa ,sa) and gb = (pb ,sb)
are to be recombined by an operator ωrec and describe the composition of a new
chromosome as follows:
Each element of the object and strategy parameter vector is a combination of the
respective entries of ga and gb, by two functions ρp and ρs :
Here the functions ρp and ρs define the component-wise recombination mapping
for the object and strategy parameters, respectively. In order to keep the formulas simpler,
we will assume an identical recombination mapping for both the object and strategy
parameters, ρ = ρp = ρs
Two recombination mappings in Evolution Strategies are discrete ρ = ρdis and
intermediate ρ = ρint recombination.
Discrete Recombination:
With a discrete recombination function, ρdis one of the two vector components is
chosen at random and declared to be the new vector entry. For the case of binary
recombination this means:
Here χ computes a uniformly distributed random number from the interval [0,1].
Each component xa or xb is selected with a 50-percent probability. In general, for μ
values x1 , x2 , …. xμ to be recombined in discrete manner, ρdis(x1 , x2 , …. xμ), the
probability to choose parameter xi is l/μ.
The above figure illustrates discrete recombination of three ES chromosomes
(p1,s1), (p3,s3) and (p6,s6) into a new chromosome (p′,s′). In Evolution Strategies
discrete recombinations are mainly used for interchanging strategy parameters, i.e.,
usually ρ = ρdis
Intermediate Recombination:
For many ES application domains dealing with real numbers that represent some
control parameter settings, taking the mean value of corresponding elements turns out to
be a sensible and natural operator. This is exactly what intermediate recombination does.
Recombining μ chromosomes intermediately means that the following mapping, ρint, is
applied to each set of corresponding vector components:
In Evolution Strategies intermediate recombination is inter-chromosomal operator
used for object parameters, i.e., usually ρ = ρint
Local and Global Recombinations:
Local recombinations work on a subpopulation of chromosomes, whereas for
global recombinations each component can be selected from the set of corresponding
entries among all chromosomes in a population. This results in an increased mixing of
genotypic information. The multi recombination on a (sub-)population G = (xi,... ,Xn) of
n ES chromosomes, each being of the form
A multi-recombination operator Wrec working on r chromosomes will be for-
malized as:
Local intermediate and discrete recombinations , i.e., for r recombinants the
new chromosome is computed as follows:
We define a global recombination operator, that combines elements "per
column" as follows:
Evolution Scheme
ES schemes are known as comma and plus strategies. Initial scheme is started
with one parent producing one or more mutated offspring and extends with μ
parents producing λ mutated offspring .
Evolution Schemes:
The most simple and original ES scheme is known as a (1 + λ) Evolution Strategy.
In Figure, a single parent individual produces λ offspring by mutation.
The parent genotype is duplicated λ times and all copies are subsequently mutated.
The offspring's phenotypes are evaluated and both sets of individuals, the parent and
offspring, find themselves in a selection pool. Only the best of these individuals will
survive and serve as the parent for the next generation loop. The abbreviated notation for
this kind of reproduction process is (1 + λ)-ES, where the 1 refers to the number of
parents and λ is the number of offspring. The '+' sign is used to describe the composition
of the final selection pool which contains the parent as well as its children. With a
(1+λ)-ES the single parent survives into the following generation if all its offsprings'
fitnesses are worse. Thus the parent can only be replaced by a superior offspring
individual, which means that the fitness of the best-so-far individual either remains the
same or increases.
A simple remedy for this is to exclude the parent individual from the final
selection pool using a (1, λ)-strategy. By excluding the parent from the selection pool, the
best individual among the offspring becomes the new parent individual for the next
generation. This selection scheme is referred to as a (1, λ)-ES, the comma symbolizing
the parent's exclusion from the selection pool.
Evolution Schemes:
Taking into account that several μ parents produce a population of (λ) offspring,
we arrive at a (μ + λ)-ES or a (μ , λ)-ES, respectively. Instead of selecting a single
individual from the selection pool as the designated parent, now the μ best individuals
among the selection pool of λ individuals will survive into the next generation. In the
case of a (μ , λ)-ES strategy, we must ensure that there are enough individuals from
which to select, that is, λ ≥ μ
GENETIC ALGORITHM
Genetic Algorithms (GAs), originally introduced by John Holland have been
popularized as universal optimization algorithms based on evolutionary methods. The
most remarkable difference between Evolution Strategies and Genetic Algorithms is that
GAs use a string-based, usually binary parameter encoding, resembling the discrete
nucleotide coding scheme on cellular chromosomes. Therefore, GA genotypes can be
defined as bit-vectors (bit-strings), on which point mutations are defined by switching
bits with a certain probability. A recombinational operator of crossover, models the
breaking of two chromosomes and subsequent crosswise restituation. Each individual is
assigned a fitness value depending on the optimization task to be solved. Selection within
the population is performed in a fitness-proportionate way: The more fit an individual,
the more likely it is to be chosen for reproduction into the following generation.
Representation of Genotypes:
Nature encodes "growth programs", which describe the development of organisms,
on the basis of a four-element alphabet, called the nucleotide bases A, C, G, and T on the
DNA (deoxyribo nucleic acid) or A, C, G, and U on the RNA (ribonucleic acid) strands
comprising the cellular genome. Binary alphabets are the preferred encoding used for
Genetic Algorithm chromosomes.
Haploid GA Chromosomes
In its simplest form, a GA chromosome can be described as a haploid string, i.e., a
single strand with alleles(one of two or more alternative forms of a gene that arise by
mutation and are found at the same place on a chromosome.) over a k-element alphabet A
= {ai,... ,ak}- Therefore, we define a single GA chromosome of length n as a vector g of
the form
g = (g1 ,... , gn) with gi ∈ A for 1 ≤ i ≤ n
Such a GA chromosome can be interpreted as a sequence of genes. Each gene is
represented by its allele which exhibits a specific value from a discrete pool of possible
settings A. Each gene locus i does not have its own alphabet Ai. Instead, all genes take
their values from the same allele pool A.
Diploid and m-ploid GA Chromosomes
The notion of a single chromosome strand is easily extended to a polyploid
chromosome with several strands. a diploid pair of chromosomes is represented as g1 =
(g11,... , g1n) and g2 = (g21,... , g2n) by the following structure.
For each locus i the pair (i, (g1i , g2i)) contains the locus index as its first
component, the list of respective alleles of two chromosome strands gi and g2, each with
n components as second. Polyploid or m-ploid chromosomes with m homologous strands,
i.e., strands of equal length n, as follows:
Mutations on GA Chromosomes:
Mutations in combination with recombinations are the driving forces of evolution.
We first consider simple point-mutations on a GA chromosome g = (g1 ,... , gn) as taken
from a discrete alphabet A = {a1,..., ak}. Point mutations change the settings of genes at
randomly selected gene locations. For each gene, its allele is replaced by a new value
from A with mutation probability pm. The mutation operator ωmut :=GA → GA, with GA
denoting the set of all GA chromosomes over alphabet A, generates a new chromosome
g' = ωmut (g) = ωmut ((g1 ,... , gn))= (g1′ ,... , gn′) as follows:
Here χ is a uniformly distributed random variable from the interval [0,1]. The
probability for a mutation per gene locus is denoted by pm
Mutations on a polyploid set of single-strand chromosomes is defined as,
consisting of m homologous single chromosome strands of the form
gi = (gi1,... , gin) with 1 ≤ i ≤ n
Recombinations among GA Chromosomes
GA chromosomes are mostly defined over a discrete allele alphabet, all the
discrete variants of recombination operators for Evolution Strategies can be used here as
well. For m homologous, haploid GA chromosomes g1 = (g11,... , g1n) , .... , gm = (gm1,...
, gmn) a recombined GA chromosome ^rec can be composed with the help of a
recombination mask μ = (μ1, μ2 ,.... , μn )
The i-th component of grec is therefore the μi-th element from the set of "genes"
{g11,... , g1n}
The GA recombination operator - binary GA crossover plays an important role in the
early for mutations and implementations of Genetic Algorithms.
One-Point crossover:
If the recombination mask μ has the special property which contains only two
different elements, i1 and i2, from the index set {1 , …. , m} and there is exactly one index
k ∈ {1,... ,n - 1} such that (μ1, μ2 ,.... , μk) = i1 and (μk+1, μk+2 ,.... , μn) = i2.
Different types of cross over are:
Single-point and two-point crossover
Parametrized uniform crossover operators - similar to global ES recombination
schemes.
Segmented and shuffle crossover work in a way similar to multi-point crossover.
Punctuated crossover is one of the very few attempts to introduce self-adaptive strategy
parameters into Genetic Algorithms
GA Operators
The two major GA operators, recombination as the primary and mutation as the
secondary operator. Some more operators such as inversion, duplication, and deletion are
also used.
We assume a haploid GA chromosome of the form
Inversion
On natural genomes, an inversion occurs when a chromosome is split twice, after locus i1
- 1 and before i2 + 1, and the resulting middle section (gi1,... , gi2) is reinserted into the
strand in reverse order:
Duplication
A side effect of crosswise recombination of two homologous chromosomes is the
duplication and deletion of subsections on the genome. Formally, the insertion of a copy
of a gene sequence (gi1,... , gi2) can be defined as follows:
Deletion
The duplication operator is mainly applied in conjunction with its counterpart, the
deletion operator. Here a chromosome loses a gene sequence (gi1,... , gi2):
Selection Functions
The selection functions define the "who shall live and who shall die" filters that all
individuals pass through from one generation to the next. The Evolution Strategy's
traditional selection procedure is done for survival of the best, but Genetic Algorithms
apply a more "natural" selection scheme. In nature, an individual's probability of survival
is influenced by an abundance of factors. However, it is not at all the case that only "the
most fit" individuals survive. In fact, even less adapted, hence less fit, individuals have a
chance to reproduce and transfer their genes to their progeny. Their genes survive into the
next generations with certain probability.
Fitness Proportionate Selection:
For a population G = {g1,... ,gμ} of size μ with each individual gi assigned a
non-negative fitness value η(gi) ∈ Kj, the probability Psel(σprop, gi) for an individual to
be selected fitness-proportionately is defined as
Here η∑(G) denotes the sum of all fitnesses of the population. The probability of
an individual to be reproduced into the next generation is directly proportional to its
fitness, hence it is fitness proportionate selection.
Rank-Based Selection
If the population size is small (much less than 100 individuals), with only these few
super-individuals. Thus the gene pool loses its heterogeneity and is reduced to only a
small set of search points. One remedy for this situation is to reduce the fitness
differences among the individuals by assigning ranks to the individuals instead of using
their actual fitness values. Just as in a tournament of μ competitors, the winner receives
rank 1, the second best is assigned rank 2, etc., until the least fit individual ranks at μ.
The μ individuals are sorted in increasing fitness order such that η(gi) ≤ η(gj) for all 1 ≤
i < j ≤ μ. If ρ(g) denotes the rank of individual g ∈ G within this sorted sequence, its
fitness ηrank(g) is defined by
so that the rank-based selection probability is
Elitist Selection
The elitist selection scheme is the one used for selection with Evolution Strategies
and can be used for Genetic Algorithms, too. For the (μ, λ) or (μ + λ) strategies, the best
μ individuals from the set of mutants in the pool of λ or μ + λ individuals are selected as
the parents of the next generation. The GA elitist selection scheme implements exactly
this selection method.
The best δ individuals (usually δ ≪ μ) are selected, each is assigned the same
fitness of 1/δ, and fitness proportionate selection is performed, which results in a random
selection among these δ individuals.
Random Selection
Sometimes, individuals g ∈ G are selected by pure random choice,
Here μ denotes the number of individuals in generation G.
GA Evolution Scheme
GA evolution starts with a randomly generated initial population of μ genotypic
structures. After interpretation and evaluation, the population enters a selection-variation
cycle which is iterated for either a maximum number of generations or until some
termination criterion (τ) is met.
The canonical Genetic Algorithm performs a (μ/2, μ) strategy. From the pool of μ
parents λ = μ pairs of individuals are selected for recombination (crossover) and
subsequent mutation. The resulting individuals represent the parents of the next
generation. The individuals are not selected at random from the parent pool but according
to one of the GA selection functions σ.
GENETIC PROGRAMMING
Genetic Programming (GP) is certainly one of the major steps towards automatic
programming using evolutionary principles. The term genetic programming was coined
by John Koza, who initially introduced his evolutionary programming approach as a
"hierarchical genetic algorithm" and later on switched to a symbolic representation for
evolving LISP programs. The main contribution of Koza's research group is documented
by a three-volume treatise, demonstrating that Genetic Programming can successfully be
applied to induce computer programs in a wide range of areas, such as symbolic
regression or learning boolean parity functions, the evolution of emergent behavior, the
evolution of robot control programs, the evolution of classifiers for prediction of
transmembrane domains and omega loops in proteins, or the recent work on evolution of
analog electrical circuits. The successful use of tree structures to represent data and
program instructions has led to an immediate association of Genetic Programming with
symbolic expressions, although many more encoding schemes can be used and actually
are used for automatic programming by evolution. The following items characterize the
field of Genetic Programming in a broader sense:
Program Induction: Genetic Programming deals with the induction of computer
programs using evolutionary principles. The programs can be either directly executable
(machine) code or expressions — data and/or instructions — of any programming
language.
Learning Algorithms: Not all learning algorithms are explicitly represented as programs
in a strict sense, such as neural networks and learning fuzzy systems. Algorithms for
adapting these data structures (neuron weights, activation functions, fuzzy rule
parameters, etc.) are also in the domain of Genetic Programming.
Representation: There are many different ways of representing programs, for example,
by linear, string-based structures, by tree-like symbolic expressions, by growth grammars,
or by graphs.
Operators: Selection operators are used to designate the survivors among the population
of competing programs. Reproduction operators are used in conjunction with
recombination operators, generating new variants by, primarily, mutation and crossover,
or further operators, such as permutation, deletion, duplication, or encapsulation.
Representation of Computer Programs by Symbolic Expressions
Programs evolved by a tree-based GP system are typically composed from a finite
set F of building blocks, the functions
where ሀ(F) denotes the arities of the function symbols, and the terminals
T={t1, t2, ….. , tM}
Considering the terminals as function symbols of arity zero, both sets can be merged into
a single set of elementary building blocks:
S=FUT
The set GPterms of program trees, representing the GP search space, can be defined as
follows:
1. Each terminal t ∈ S with ሀ(t) = 0 is an element of GPterms
2. For each f ∈ S with ሀ(f) = n and g1,...,gn ∈ GPterms , the term f(g1,.. . ,gn) is also an
element of GPterms
The GP encoding of the structures to be evolved has an important impact on whether the
evolutionary approach will succeed or not. The choice of functions and terminals also
influences the potential of the genetic operators to create innovative and optimized
program structures.
Given the set of building blocks
S = {Mult2, Add2,If-Then-Else3,Equal2,Ao,Bo,Co,Do}
Where indices in S denote the arities of the symbols.
The above Figure illustrates the recursive, step-by-step construction of a random
program term, an element of GPterms- A symbol from S is randomly selected
(If-Then-Else) as the root of the expression tree. At each of the branches, further
subterms have to be composed by further random selection from S. This procedure is
repeated until all leaf nodes are labeled with terminals.
The depth of the generated expression tree is not constrained, although one usually
defines a maximum tree depth and width in order to reduce memory requirements for
storage and evaluation time of the program term. Furthermore, the symbol set S has to be
closed with respect to composition. Each symbol must be combinable with any other
symbol, so that the final expression is always syntactically correct and can be interpreted
as a proper program or data structure.
S = {Mult(int,int)→ int , If-Then-Else(bool,int,int) → int , Equal(int,int)→ bool , . . .} .
Mutations on Symbolic Expressions
The GP mutation operators come in a great number of varieties. Basically,
subterms or leaves of a tree structure are substituted by either newly generated or
duplicated terms or terminals.
The above figure gives a brief overview of mutation operators on tree structured
expressions.
● Point Mutation A point mutation (b) exchanges a single node by a random node
of the same class. In the simplest case this means that terminals are substituted by
terminals, and function symbols are substituted by function symbols with the same
arity (and types, if applicable).
● Permutation A permutation (c) merely permutes the sequence of arguments of a
node. The hoist operator (d) substitutes the whole tree by a randomly selected
proper subtree (terminals are not in the scope of selection).
● Collapse Subtree Mutation With the collapse subtree mutation (e) a subtree is
replaced by a random terminal.
● Expansion Mutation The inverse operation is the expansion mutation (f) where a
terminal is exchanged against a random, newly generated subtree.
● Duplication The duplication operator (g) replaces a terminal node with a copy of a
proper subtree.
● Subtree Mutation The most general mutation operator is defined by subtree
mutation (h), where a subtree is substituted with a newly generated subtree.
Crossover of Symbolic Expressions
Another important operator used in GP for generating new term structures is a
variant of the one-point crossover known from Genetic Algorithms. By crossing two
linear GA chromosomes, substrings are exchanged between the chromosomes. An
analogous recombination operator for GP terms is defined by interchanging (sub)trees
between two GP terms.
The above figure shows the simplest crossover version known as subtree exchange
crossover, which is performed as follows: For each term a node is chosen at random.
Inner nodes (including the root) as well as leaves are selectable. In Figure, the selected
subtrees are marked by triangular shapes. The two recombined terms result from a mutual
exchange of the selected sub-expressions.
In comparison to the crossover or recombination operators of Genetic Algorithms
or Evolution Strategies, an interesting aspect of GP crossover is the following. Even for a
recombination among two identical trees, the GP crossover (self crossover) results in a
pair of new structures whenever the two crossover nodes differ.
GA crossover for identical chromosomes is reduced to a simple reproduction
operator without changing the structures. As the GA crossover operator enhances the
similarity among the strings, mutation operators are essentially needed to introduce new
allele settings into the genepool.
Several variants for GP crossover have been developed, such as context
preserving crossover (CPC), where subtrees are exchanged only if either their node
coordinates match exactly (strong CPC) or match approximately (weak CPC). With
module crossover, parametrized sub-trees are exchanged between two individual
structures. The modules are comparable to parameterized macros in programming
languages like C. One variant of module crossover is known as encapsulation and
decapsulation. An extension of this approach denoted as macro extraction.
G P Evolution Scheme
For canonical Genetic Programming a slightly modified GA evolution scheme is
used. The scheme depicted in the below figure is a slight modification of the basic GP
algorithm and is better compared to the GA and ES schemes. The comma as well as the
plus reproduction scheme can be used.
The above figure depicts the comma scheme where parents are not part of the selection
pool. A notable extension of the GP evolution scheme is the operator pool, which
contains a set of genetic operators, each attributed by a selection probability.
One reproduction cycle works as follows:
● First, a genetic operator is selected from the operator pool.
● Secondly, depending on the arity n of the operator, n individuals are chosen by a
fitness-proportionate selection function (n = 1 for reproduction and mutation, n > 2 for
crossover).
● After applying the operators, the new program structures are evaluated and constitute
the selection pool for the parents of the following generation.
VISUALIZATION
Information visualization and visual data analysis can help to deal with the flood
of information. The advantage of visual data exploration is that the user is directly
involved in the data analysis process. There are a large number of information
visualization techniques that have been developed over the last two decades to support
the exploration of large data sets.
Benefits of Visual Data Exploration
Visual data mining aims at integrating the human in the data analysis process,
applying human perceptual abilities to the analysis of large data sets available in today's
computer systems. The basic idea of visual data mining is to present the data in some
visual form, allowing the user to gain insight into the data, draw conclusions, and directly
interact with the data.
Visual data analysis techniques have proven to be of high value in exploratory data
analysis. Visual data mining is especially useful when little is known about the data and
the exploration goals are vague. Since the user is directly involved in the exploration
process, shifting and adjusting the exploration goals can be done in a continuous fashion
as needed.
The visualizations of the data allow the user to gain insight into the data and come
up with new hypotheses. The verification of the hypotheses can also be done via data
visualization, but may also be accomplished by automatic techniques from statistics,
pattern recognition, or machine learning. In addition to the direct involvement of the user,
the main advantages of visual data exploration over automatic data analysis techniques
are:
● Visual data exploration can easily deal with highly non-homogeneous and noisy
data.
● Visual data exploration is intuitive and requires no understanding of complex
mathematical or statistical algorithms or parameters.
● Visualization can provide a qualitative overview of the data, allowing data
phenomena to be isolated for further quantitative analysis.
Visual Exploration Paradigm
Visual Data Exploration usually follows a three step process: Overview, zoom and
filter, and then details-on-demand. In analyzing large data sets, the user first needs to get
an overview of the data.
In the overview, the user identifies interesting patterns or groups in the data and
focuses on one or more of them. For analyzing the patterns, the user needs to drill-down
and access details of the data. Visualization techniques are useful for showing an
overview of the data, allowing the user to identify interesting subsets. In this step, it is
important to keep the overview visualization while focusing on the subset using another
visualization technique. An alternative is to distort the overview visualization in order to
focus on the interesting subsets. This can be performed by dedicating a larger percentage
of the display to the interesting subsets while decreasing screen utilization for currently
uninteresting data. To further explore the interesting subsets, the user needs a drill-down
capability in order to observe the details about the data.
CLASSIFICATION OF VISUAL DATA ANALYSIS TECHNIQUES
There are a number of well known techniques for visualizing such data sets, such
as x-y plots, line plots, and histograms. These techniques are useful for data exploration
but are limited to relatively small and low dimensional data sets. The techniques can be
classified based on three criteria
● Data type
● Visualization Technique
● Interaction Technique
The data type to be visualized may be:
● One-dimensional data, such as temporal (time-series) data
● Two-dimensional data, such as geographical maps
● Multi-dimensional data, such as relational tables
● Text and hypertext, such as news articles and Web documents
● Hierarchies and graphs, such as telephone caUs and Web documents
● Algorithms and software, such as debugging operations
The visualization technique used may be classified as:
● Standard 2D/3D displays, such as bar charts and x-y plots
● Geometrically-transformed displays, such as landscapes and parallel coordinates
● Icon-based displays, such as needle icons and star icons
● Dense pixel displays, such as recursive patterns and circle segments
● Stacked displays, such as treemaps and dimensional stacking
Interaction techniques allow users to directly navigate and modify the visualizations, as
well as select subsets of the data for further operations.
● Dynamic Projection, that allows smooth navigations through the data space
● Interactive Filtering, to enable users to isolate subsets of data for focussed analysis
● Zooming, to enlarge data for detailed analysis
● Distortion, to increase the screen space allocated to areas of interest while
preserving the context of the entire data set
● Linking and Brushing, to enable users to select data of interest in one view and see
it highlighted in other views
DATA TYPE TO BE VISUALIZED
In information visualization, the data usually consists of a large number of records,
each consisting of a number of variables or dimensions. Each record corresponds to an
observation, measurement, or transaction. Examples are customer properties, e-commerce
transactions, and sensor output from physical experiments. The number of attributes can
differ from data set to data set; The number of variables can be said as the dimensionality
of the data set. Data sets may be one-dimensional, two-dimensional, multi-dimensional or
may have more complex data types such as text/hypertext or hierarchies/graphs.
Depending on the number of dimensions with arbitrary values the data are sometimes
also called univariate, bivariate, or multivariate.
One-dimensional data
One-dimensional data usually have one dense dimension. A typical example of
one-dimensional data is temporal data. One or multiple data values may be associated
with each point in time. An example are time series of stock prices or time series of news
data.
Two-dimensional data
A typical example of two-dimensional data is geographical data, where the two
distinct dimensions are longitude and latitude. A standard method for visualizing
two-dimensional data are x-y plots and maps are a special type of x-y plots for presenting
two-dimensional geographical data. Examples are geographical maps. If the number of
records to be visualized is large, temporal axes and maps get quickly cluttered - and may
not help to understand the data.
Multi-dimensional data
Many data sets consist of more than three dimensions and therefore do not allow a
simple visualization as 2-dimensional or 3-dimensional plots. Examples of
multi-dimensional (or multivariate) data are tables from relational databases, which often
have tens to hundreds of columns (or dimensions). Since there is no simple mapping of
the data dimensions to the two dimensions of the screen, more sophisticated visualization
techniques are needed. An example of a technique that allows the visualization of
multi-dimensional data is the Parallel Coordinates Technique. Parallel Coordinates
display each multidimensional data item as a set of line segments that intersect each of
the parallel axes at the position corresponding to the data value for that dimension.
Text and Hypertext
In the age of the World Wide Web, important data types are text and hypertext, as
well as multimedia web page contents. These data types differ in that they cannot be
easily described by numbers, and therefore most of the standard visualization techniques
cannot be applied. In most cases, a transformation of the data into description vectors is
necessary before visualization techniques can be used. An example of a simple
transformation is word counting which is often combined with principal component
analysis or multidimensional scaling to reduce the dimensionality to two or three.
Hierarchies and Graphs
Data records often have some relationship to other pieces of information. These
relationships may be ordered, hierarchical, or arbitrary networks of relations. Graphs are
widely used to represent such interdependencies. A graph consists of a set of objects,
called nodes, and connections between these objects, called edges or links. Examples are
the e-mail interrelationships among people, their shopping behavior, the file structure of
the hard disk, or the hyperlinks in the World Wide Web. There are a number of specific
visualization techniques that deal with hierarchical and graphical data.
Algorithms & Software
Another class of data are algorithms and software. Coping with large software
projects is a challenge. The goal of software visualization is to support software
development by helping to understand algorithms (e.g., by showing the flow of
information in a program), to enhance the understanding of written code (e.g., by
representing the structure of thousands of source code lines as graphs), and to support the
programmer in debugging the code (e.g., by visualizing errors). There are a large number
of tools and systems that support these tasks.
VISUALIZATION TECHNIQUES
There are a large number of visualization techniques that can be used for
visualizing data. In addition to standard 2D/3D-techniques such as x-y (x-y-z) plots, bar
charts, line graphs, and maps, there are a number of more sophisticated classes of
visualization techniques. The classes correspond to basic visualization principles that
may be combined in order to implement a specific visualization system.
Geometrically-Transformed Displays
Geometrically-transformed display techniques aim at finding "interesting"
transformations of multi-dimensional data sets. The class of geometric display methods
includes techniques from exploratory statistics such as scatterplot matrices and
techniques such as projection, a class of techniques that attempt to locate projections.
Other geometric projection techniques include Prosection Views, where only
user-selected slices of the data are projected.
The Parallel Coordinate Technique maps the k-dimensional space onto the two
display dimensions by using k axes that are parallel to each other (either horizontally or
vertically oriented) and are evenly spaced across the display. The axes corresponding to
the dimensions are linearly scaled from the minimum to the maximum value of the
corresponding dimension. Each data item is presented as a chain of connected line
segments, intersecting each of the axes at the location corresponding to the value of the
dimension considered.
Iconic Displays
Another class of visual data exploration techniques are the iconic display methods.
The idea is to map the attribute values of a multi-dimensional data item to the features of
an icon. Icons may be defined arbitrarily - as little faces , needle icons, star icons, stick
figure icons, color icons, or TileBars. The visualization is generated by mapping the
attribute values of each data record to the features of the icons. In the case of the stick
figure technique, two dimensions are mapped to the display dimensions and the
remaining dimensions are mapped to the angles and limb length of the stick figure icon.
If the data items are relatively dense with respect to the two display dimensions, the
resulting visualization presents texture patterns that vary according to the characteristics
of the data. Each data point is represented by a star icon/symbol, where each data
dimension controls the length of a ray emanating from the center of the icon.
Dense Pixel Displays
The basic idea of dense pixel techniques is to map each dimension value to a
colored pixel and group the pixels belonging to each dimension into adjacent areas.
Dense pixel displays use one pixel per data value, so, the techniques allow the
visualization of the largest amount of data possible on current displays. Dense pixel
displays use different arrangements to provide detailed information on local correlations,
dependencies, and hot spots. Example: The recursive pattern technique and The circle
segments technique.
The recursive pattern technique is based on a generic recursive back-and-forth
arrangement of the pixels and is particularly aimed at representing data sets with a natural
order according to one attribute (e.g. time-series data). The basic element on each
recursion level is a pattern of height hi and width Wi as specified by the user. First, the
elements correspond to single pixels that are arranged within a rectangle of height hi and
width wi from left to right, then below backwards from right to left, then again forward
from left to right, and so on.
The circle segments technique is to represent the data in a circle that is divided
into segments, one for each attribute. Within the segments each attribute value is again
visualized by a single colored pixel. The arrangement of the pixels starts at the center of
the circle and continues to the outside by plotting on a line orthogonal to the segment
halving line in a back and forth manner. The rationale of this approach is that close to the
center all attributes are close to each other enhancing the visual comparison of their
values.
Stacked Displays
Stacked display techniques are tailored to present data partitioned in a
hierarchical fashion. In the case of multi-dimensional data, the data dimensions to be
used for partitioning the data and building the hierarchy have to be selected appropriately.
An example of a stacked display technique is Dimensional Stacking. The basic idea is to
embed one coordinate system inside another coordinate system. The display is generated
by dividing the outermost level coordinate system into rectangular cells. Within the
cells, the next two attributes are used to span the second level coordinate system. This
process may be repeated multiple times. The usefulness of the resulting visualization
largely depends on the data distribution of the outer coordinates and therefore the
dimensions that are used for defining the outer coordinate system have to be selected
carefully. A Dimensional Stacking visualization of mining data with longitude and
latitude mapped to the outer x and y axes, as well as one grade and depth mapped to the
inner x and y axes. Other examples of stacked display techniques include
Worlds-within-Worlds, Treemap, and Cone Trees.
INTERACTION TECHNIQUES
Interaction techniques allow the data analyst to directly interact with the
visualizations and dynamically change the visualizations according to the exploration
objectives. In addition, they also make it possible to relate and combine multiple
independent visualizations.
Interaction techniques can be categorized based on the effects they have on the
display. Navigation techniques focus on modifying the projection of the data onto the
screen, using either manual or automated methods. View enhancement methods allow
users to adjust the level of detail on part or all of the visualization, or modify the mapping
to emphasize some subset of the data. Selection techniques provide users with the ability
to isolate a subset of the displayed data for operations such as highlighting, filtering, and
quantitative analysis. Selection can be done directly on the visualization (direct
manipulation) or via dialog boxes and other query mechanisms (indirect
manipulation). Some examples of interaction techniques are described below.
Dynamic Projection
Dynamic projection is an automated navigation operation. The basic idea is to
dynamically change the projections in order to explore a multi-dimensional dataset. An
example is the GrandTour system which tries to show properties such as well-separated
clusters - two-dimensional projections of a multi-dimensional data set as a series of
scatterplots. The number of possible projections is exponential to the number of
dimensions. The sequence of projections shown can be random, manual, precomputed, or
data driven. Systems supporting dynamic projection techniques include XGobi,
XLispStat, and ExplorN.
Interactive Filtering
Interactive filtering is a combination of selection and view enhancement. In
exploring large data sets, it is important to interactively partition the data set into
segments and focus on interesting subsets. This can be done by a direct selection of the
desired subset (browsing) or by a specification of properties of the desired subset
(querying). Browsing is difficult for very large data sets and querying often does not
produce the desired results. Therefore, a number of interactive selection techniques have
been developed to improve interactive filtering in data exploration. An example of a tool
that can be used for interactive filtering is the Magic Lens. The basic idea of Magic
Lenses is to use a tool similar to a magnifying glass to filter the data directly in the
visualization. The data under the magnifying glass is processed by the filter and displayed
in a different way than the remaining data set. Magic Lenses show a modified view of the
selected region, while the rest of the visualization remains unaffected. Other examples of
interactive filtering techniques and tools are InfoCrystal, Dynamic Queries, and Polaris.
Zooming
Zooming is a well known view modification technique that is widely used in a
number of applications. In dealing with large amounts of data, it is important to present
the data in a highly compressed form to provide an overview of the data. Zooming does
not only mean displaying the data objects larger, but also that the data representation may
automatically change to present more details on higher zoom levels. The objects may be
represented as single pixels at a low zoom level, as icons at an intermediate zoom
level, and as labeled objects at a high resolution. An interesting example is TableLens.
The basic idea of Table Lens is to represent each numerical value by a small bar. All
bars have a one-pixel height and the lengths are determined by the attribute values. This
means that the number of rows on the display can be nearly as large as the vertical
resolution and the number of columns depends on the maximum width of the bars for
each attribute. The initial view allows the user to detect patterns, correlations, and outliers
in the data set. In order to explore a region of interest the user can zoom in, with the
result that the affected rows (or columns) are displayed in more detail, possibly even in
textual form. Other examples of techniques and systems that use interactive zooming
include PAD+ +, IVEE/Spotfire, and DataSpace.
Distortion
Distortion is a view modification technique that supports the data exploration
process by preserving an overview of the data during drill-down operations. The basic
idea is to show portions of the data with a high level of detail while others are shown with
a lower level of detail. Popular distortion techniques are hyperbolic and spherical These
are often used on hierarchies or graphs but may also be applied to any other visualization
technique. Examples of distortion techniques include Bifocal Displays, Perspective Wall ,
Graphical Fisheye Views, Hyperbolic Visualization, and Hyperbox.
The above figure shows the effect of distorting part of a scatterplot matrix to display
more detail from one of the plots while preserving context from the rest of the display.
Brushing and Linking
Brushing is an interactive selection process that is often, but not always,
combined with linking, a process for communicating the selected data to other views of
the data set. There are many possibilities to visualize multidimensional data, each with
their own strengths and weaknesses. The idea of linking and brushing is to combine
different visualization methods to overcome the shortcomings of individual techniques.
Scatterplots of different projections, may be combined by coloring and linking subsets of
points in all projections. In a similar fashion, linking and brushing can be applied to
visualizations generated by all visualization techniques described above. As a result, the
brushed points are highlighted in all visualizations, making it possible to detect
dependencies and correlations. Interactive changes made in one visualization are
automatically reflected in the other visualizations. Connecting multiple visualizations
through interactive linking and brushing provides more information than considering the
component visualizations independently. Typical examples of visualization techniques
that have been combined by linking and brushing are multiple scatterplots, bar charts,
parallel coordinates, pixel displays, and maps. Most interactive data exploration
systems allow some form of linking and brushing.
SPECIFIC VISUAL DATA ANALYSIS TECHNIQUES
There are a number of visualization techniques that have been developed to
support specific data mining tasks such as association rule generation, classification, and
clustering.
Association Rule Generation
The goal of association rule generation is to find interesting patterns and trends
in transaction databases. Association rules are statistical relations between two or more
items in the data set. In a supermarket basket application, associations express the
relations between items that are bought together. It is for example interesting if we find
out that in 70% of the cases when people buy bread, they also buy milk. Association rules
tell us that the presence of some items in a transaction imply the presence of other items
in the same transaction with a certain probability, called confidence.
A second important parameter is the support of an association rule, which is
defined as the percentage of transactions in which the items co-occur. Let I = {i1, ...in} be
a set of items and let D be a set of transactions, where each transaction T is a set of items
such that T ⊆ I. An association rule is an implication of the form X ⇒ Y, where X⊆ I,
Y⊆I, X,Y ≠ Ø. The confidence c is defined as the percentage of transactions that
contain Y, given X. The support is the percentage of transactions that contain both X
and Y. For a given support and confidence level, there are efficient algorithms to
determine all association rules.
The resulting set of association rules is usually very large, especially for low
support and confidence levels.. Visualization techniques have been used to allow an
interactive selection of good support and confidence levels.
The above figure shows SGI MineSets Rule Visualizer which maps the left and
right hand sides of the rules to the x- and y-axes of the plot, respectively, and shows the
confidence as the height of the bars and the support as the height of the discs. The color
of the bars shows the interestingness of the rule. Using the visualization, the user is able
to see groups of related rules and the impact of different confidence and support levels.
The number of rules that can be visualized is limited and the visualization does not
support combinations of items on the left or right hand side of the association rules.
The above figure shows two alternative visualizations called mosaic and double
decker plots.
Mosaic plots use the height of the bars instead of their width to show the
parameter value. Then each resulting area is split in the same way according to a second
attribute. The coloring reflects the percentage of data items that fulfill a third attribute.
The visualization shows the support and confidence values of all rules of the form X1, X2
⇒ Y. Mosaic plots are restricted to two attributes on the left side of the association rule.
Double decker plots can be used to show more than two attributes on the left side.
The idea is to display a hierarchy of attributes on the bottom corresponding to the left
hand side of the association rules. The bars on the top correspond to the number of
items in the considered subset of the database and therefore visualize the support of the
rule. The colored areas in the bars correspond to the percentage of data transactions
that contain an additional item and therefore represent the support. Other approaches to
association rule visualization include graphs with nodes corresponding to items and
arrows corresponding to implications and association matrix visualizations to cluster
related rules.
Classification
Classification is the process of developing a classification model based on a
training data set with known class labels. To construct the classification model, the
attributes of the training data set are analyzed and an accurate description or model of
the classes based on the attributes available in the data set is developed. The class
descriptions are used to classify data for which the class labels are unknown.
Classification is sometimes also called supervised learning because the training
set is used to teach the system how to classify the data. There are a large number of
algorithms for solving classification tasks. A popular class of approaches are algorithms
that inductively construct decision trees. Examples are IDS, CART, ID5, C4.5, SLIQ ,
and SPRINT. In addition, there are approaches such as neural networks, genetic
algorithms, or Bayesian networks that are used to solve the classification problem.
Since most algorithms work as black box approaches, it is often difficult to understand
and optimize the decision model. Problems such as overfitting or tree pruning are
difficult to tackle. Visualization techniques can help to overcome these problems.
The decision tree visualizer in SGIs MineSet system shows an overview of the
decision tree together with important parameters such as the attribute value distributions
The system allows an interactive selection of the attributes shown and helps the user to
understand the decision tree.
Visual classification is another sophisticated approach, which also helps in
decision tree construction. The basic idea is to show each attribute value by a colored
pixel and arrange them in bars - similar to the Dense Pixel Displays. The pixels of each
attribute bar are sorted separately and the attribute with the purest value distribution is
selected as the split attribute of the decision tree. The procedure is repeated until all
leaves correspond to pure classes.
An exemplary decision tree resulting from this process is shown in the above
figure. Compared to a standard visualization of a decision tree, additional information is
provided that is helpful for explaining and analyzing the decision tree, namely
● size of the nodes (number of training records corresponding to the node)
● quality of the split (purity of the resulting partitions)
● class distribution (frequency and location of the training instances of all classes).
In general, visualizations can provide a better understanding of the classification
models and they can help to interact more easily with the classification algorithms in
order to optimize the model generation and classification process.
Clustering
Clustering is the process of finding a partitioning of the data set into
homogeneous subsets called clusters Unlike classification, clustering is often
implemented as a form of unsupervised learning. This means that the classes are
unknown and no training set with class labels is available. A wide range of clustering
algorithms are density-based methods such as KDE and linkage-based methods. Most
algorithms use assumptions about the properties of the clusters that are either used as
defaults or have to be given as input parameters. Depending on the parameter values, the
user obtains different clustering results.
In two- or three-dimensional space, the impact of different algorithms and
parameter settings can be explored easily using simple visualizations of the resulting
clusters (for example, x-y plots), but in higher dimensional space the impact is much
more difficult to understand. Some higher-dimensional techniques try to determine two-
or three-dimensional projections of the data that retain the properties of the
high-dimensional clusters as much as possible.
The above shows a three-dimensional projection of a data set consisting of five
Clusters. While this approach works well with low- to medium-dimensional data sets, it
is difficult to apply it to large high-dimensional data sets, especially if the clusters are not
clearly separated and the data set also contains noise. In this case, more sophisticated
visualization techniques are needed to guide the clustering process, select the right
clustering model, and adjust the parameter values appropriately.
The visualization techniques help in high-dimensional clustering is OPTICS
(Ordering Points To Identify the Clustering Structure). The idea of OPTICS is to
create a one-dimensional ordering of the database representing its density-based
clustering structure.
The figure shows a two-dimensional data set together with its reachability distance
plot. Intuitively, points within a cluster are close in the generated one-dimensional
ordering and their reachability distance is similar. Jumping to another cluster results in
higher reachability distances. The idea works for data of arbitrary dimension. The
reachability plot provides a visualization of the inherent clustering structure and is
therefore valuable for understanding the clustering and guiding the clustering process.
Another interesting approach is the HD-Eye system. The HD-Eye system
considers the clustering problem as a partitioning problem and supports a tight integration
of advanced clustering algorithms and state-of-the-art visualization techniques, allowing
the user to directly interact in the crucial steps of the clustering process. The crucial
steps are the selection of dimensions to be considered, the selection of the clustering
paradigm, and the partitioning of the data set.
Novel visualization techniques are employed to help the user identify the most
interesting projections and subsets as well as the best separators for partitioning the data.
The figure shows an example of the HD-Eye system with its basic visual components for
cluster separation.
The separator tree represents the clustering model produced so far in the
clustering process. The abstract iconic displays (top right and bottom middle in figure)
visualize the partitioning potential of a large number of projections. The properties are
based on histogram information of the point density in the projected space. The
number of icons corresponds to the number of peaks in the projection and their color
to the number of data points belonging to the maximum. The color follows a given color
table ranging from dark colors for large maxima to bright colors for small maxima.
The measure of how well a maximum is separated from the others is reflected by the
shape of the icon and the degree of separation varies from sharp spikes for well-separated
maxima to blunt spikes for weak-separated maxima. The color- and curve-based point
density displays present the density of the data and allow a better understanding of the
data distribution, which is crucial for an effective partitioning of the data. The
visualizations are used to decide which dimensions are taken for the partitioning. In
addition, the partitioning can be specified interactively directly within the visualizations,
allowing the user to define non-linear partitionings.