Description
The rapid e-commerce growth has made both business community and customers face a new situation.
Journal of Information & Knowledge Management, Vol. 2, No. 4 (2003) 375–390
c iKMS & World Scientific Publishing Co.
Business Intelligence from Web Usage Mining
Ajith Abraham
Department of Computer Science, Oklahoma State University,
700 N Greenwood Avenue, Tulsa,Oklahoma 74106-0700, USA
[email protected]http://ajith.softcomputing.net
Abstract. The rapid e-commerce growth has made both
business community and customers face a new situation. Due
to intense competition on the one hand and the customer’s
option to choose from several alternatives, the business community has realized the necessity of intelligent marketing
strategies and relationship management. Web usage mining
attempts to discover useful knowledge from the secondary data
obtained from the interactions of the users with the Web.
Web usage mining has become very critical for effective Web
site management, creating adaptive Web sites, business and
support services, personalization, network traffic flow analysis and so on. This paper presents the important concepts of
Web usage mining and its various practical applications. Further a novel approach called “intelligent-miner” (i-Miner ) is
presented. i-Miner could optimize the concurrent architecture
of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy inference system to analyze the Web site
visitor trends. A hybrid evolutionary fuzzy clustering algorithm is proposed to optimally segregate similar user interests. The clustered data is then used to analyze the trends
using a Takagi-Sugeno fuzzy inference system learned using
a combination of evolutionary algorithm and neural network
learning. Proposed approach is compared with self-organizing
maps (to discover patterns) and several function approximation techniques like neural networks, linear genetic programming and Takagi–Sugeno fuzzy inference system (to analyze
the clusters). The results are graphically illustrated and the
practical significance is discussed in detail. Empirical results
clearly show that the proposed Web usage-mining framework
is efficient.
mains: content , structure and usage mining (Chakrabarti,
2003; Chang et al., 2001). This paper is concerned with
Web usage mining. Web servers record and accumulate
data about user interactions whenever requests for resources are received. Analyzing the Web access logs can
help understand the user behaviour and the web structure. From the business and applications point of view,
knowledge obtained from the Web usage patterns could be
directly applied to efficiently manage activities related to
e-business, e-services, e-education and so on (Chen & Kuo,
2000; Cheung et al., 1997). Accurate Web usage information could help to attract new customers, retain current
customers, improve cross marketing/sales, effectiveness of
promotional campaigns, track leaving customers and find
the most effective logical structure for their Web space
(Heer & Chi, 2001; Jespersen et al., 2002). User profiles
could be built by combining users’ navigation paths with
other data features, such as page viewing time, hyperlink structure, and page content (Cho et al., 2003). What
makes the discovered knowledge interesting had been addressed by several works (Hay et al. 2003; Heinrichs &
Lim, 2003; Runkler & Bezdek, 2003). Results previously
known are very often considered as not interesting. So the
key concept to make the discovered knowledge interesting
will be its novelty or unexpected appearance (Aggarwal
et al., 1999; Agrawal & Srikant, 1994; Coenen et al., 2000;
Nanopoulos et al., 2002).
A typical Web log format is depicted in Fig. 1. Whenever a visitor accesses the server, it leaves the IP, authenticated user ID, time/date, request mode, status,
bytes, referrer, agent and so on. The available data fields
are specified by the HTTP protocol. There are several
commercial software that could provide Web usage statistics (Analog, 2003; ClickTracks, 2003; Hitbox, 2003;
LogRover, 2003; Website Tracker, 2003; WebStat, 2003).
These stats could be useful for Web administrators to get
a sense of the actual load on the server. However, the
Keywords: Web mining; knowledge discovery; business intelligence; hybrid soft computing; neuro-fuzzy-genetic system.
1. Introduction Related Research
The WWW continues to grow at an amazing rate as
an information gateway and as a medium for conducting business. Web mining is the extraction of interesting and useful knowledge and implicit information from
artefacts or activity related to the WWW (Cooley, 2000;
Kosala & Blockeel, 2000). Based on several reserch studies we can broadly classify Web mining into three do375
376
A. Abraham
Fig. 1.
Sample entries from a Web server access log.
Web structure/content
information
Business services
Pattern analysis
Pattern discovery
Raw Web log data
Business intelligence
Data pre-processing
Web server
and cleaning
Usage statistics
—
ISP
Sequential/association
rule mining
Customer / Client
Fig. 2.
Web usage mining framework.
statistical data available from the normal Web log data
files or even the information provided by Web trackers
could only provide the information explicitly because of
the nature and limitations of the methodology itself.
Generally, one could say that the analysis relies on three
general sets of information given a current focus of attention: (1) past usage patterns; (2) degree of shared content;
and (3) inter-memory associative link structures. After
browsing through some of the features of the best trackers
available it is easy to conclude that rather than generating statistical data and texts they really do not help to
find much meaningful information.
For small web servers, the usage statistics provided
by conventional Web site trackers may be adequate to
analyze the usage pattern and trends. However as the size
and complexity of the data increases, the statistics provided by existing Web log file analysis tools may prove
inadequate and more intelligent knowledge mining techniques will be necessary (Piramuthu, 2003; Roussinov &
Zhao, 2003; Yang & Zhang, 2003; Abraham, 2003; Zhang
& Dong, 2003).
A generic Web usage mining framework is depicted in
Fig. 2. In the case of Web mining, data could be collected
at the server level, client level, proxy level or some consolidated data. These data could differ in terms of content
and the way it is collected etc. The usage data collected
at different sources represent the navigation patterns of
different segments of the overall Web traffic, ranging from
Business Intelligence from Web Usage Mining
single user, single site browsing behaviour to multi-user,
multi-site access patterns. Web server log does not accurately contain sufficient information for infering the behaviour at the client side as they relate to the pages served
by the Web server. Pre-procesed and cleaned data could
be used for pattern discovery, pattern analysis, Web usage ststistics and generating association/ sequential rules
(Kitsuregawa et al., 2002; Masseglia et al., 1999; Pal et al.,
2002). Much work has been performed on extracting various pattern information from Web logs and the application of the discovered knowledge range from improving
the design and structure of a Web site to enabling business organizations to function more efficiently (Paliouras
et al., 2000; Pazzani & Billsus, 1997; Perkowitz & Etzioni,
1998; Pirolli et al., 1996; Spiliopoulou & Faulstich, 1999).
Jespersen et al. (2002) proposed an hybrid approach
for analyzing the visitor click sequences. A combination
377
of hypertext probabilistic grammar and click fact table
approach is used to mine Web logs which could be also
used for general sequence mining tasks. Mobasher et al.
(1999) proposed the Web personalization system which
consists of offline tasks related to the mining of usage
data and online process of automatic Web page customization based on the knowledge discovered. LOGSOM proposed by Smith et al. (2003), utilizes a self-organizing
map to organize web pages into a two-dimensional map
based solely on the users’ navigation behavior, rather
than the content of the web pages. LumberJack proposed
by Chi et al. (2002) builds up user profiles by combining both user session clustering and traditional statistical traffic analysis using K-means algorithm. Joshi et al.
(1999) used relational online analytical processing approach for creating a Web log warehouse using access
logs and mined logs (association rules and clusters). A
Fig. 3.
University’s daily Web traffic pattern for 5 weeks.
Fig. 4.
Average hourly Web traffic patterns for 5 weeks.
378
A. Abraham
comprehensive overview of Web usage mining research
is found in (Cooley, 2000; Kosala & Blockeel, 2000;
Srivastava et al., 2000).
To demonstrate the efficiency of the proposed frameworks, Web access log data at the Monash University’s
Web site (Monash, 2003) were used for experimentations.
The University’s central web server receives over 7 million hits in a week and therefore it is a real challenge
to find and extract hidden usage pattern information. To
illustrate the University’s Web usage patterns, average
daily and hourly access patterns for 5 weeks (11 August
’02–14 September ’02) are shown in Figs. 3 and 4 respectively. The average daily and hourly patterns nevertheless tend to follow a similar trend (as evident from
the figures) the differences tend to increase during high
traffic days (Monday–Friday) and during the peak hours
(11:00–17:00 Hrs). Due to the enormous traffic volume and
chaotic access behavior, the prediction of the user access
patterns becomes more difficult and complex.
Self organizing maps and fuzzy c-means algorithm
could be used to seggregate the user access records and
computational intelligence paradigms to analyze the user
access trends. Abraham (2003) and Wang et al. (2002)
have clearly shown the importance of the clustering
algorithm to analyze the user access trends.
In the subsequent section the i-Miner framework is
presented and some theoretical concepts of clustering algorithms and computational intelligence paradigms are
discussed. Experiment results are provided in Sec. 3 and
some conclusions are provided towards the end.
2. Mining Framework Using Intelligent
Miner (i-Miner)
The i-Miner hybrid framework optimizes a fuzzy clustering algorithm using an evolutionary algorithm and a
Takagi–Sugeno fuzzy inference system using a combination of evolutionary algorithm and neural network learning. The raw data from the log files are cleaned and
pre-processed and a fuzzy C means algorithm is used to
identify the number of clusters. The architecture is illustrated in Fig. 5. The developed clusters of data are fed to a
Takagi-Sugeno fuzzy inference system to analyze the trend
patterns. The if-then rule structures are learned using an
iterative learning procedure (Cord´
on et al., 2001) by an
evolutionary algorithm and the rule parameters are finetuned using a backpropagation algorithm.
The hierarchical distribution of the i-Miner is depicted in Fig. 6. The arrow direction depicts the
speed of the evolutionary search. The optimization of
K n ow led ge d isco ve ry an d tren d p atterns
Log files
D ata
prep ro c ess in g
Fu zzy
clus terin g
Evolutionary
learning
Fu zzy Infe re nc e
S ys te m
Evolutionary
learning
O p tim iza tio n alg orith m s
Fig. 5.
i-Miner framework.
Neural
learning
Business Intelligence from Web Usage Mining
Fig. 6.
Hierarchical architecture of i-Miner.
clustering algorithm progresses at a faster time scale in
an environment decided by the inference method and the
problem environment. More technical details are provided
in the subsequent sections.
2.1. Clustering algorithms
2.1.1. Fuzzy clustering algorithm
One of the widely used clustering methods is the fuzzy
c-means (FCM) algorithm developed by Bezdek (1981).
FCM partitions a collection of n vectors xi , i = 1, 2 . . . , n
into c fuzzy groups and finds a cluster center in each group
such that a cost function of dissimilarity measure is minimized. To accommodate the introduction of fuzzy partitioning, the membership matrix U is allowed to have elements with values between 0 and 1. The FCM objective
function takes the form
c
c X
n
X
X
2
J(U, c1 , . . . , cc ) =
Ji =
um
(1)
ij dij
i=1
379
i=1 j=1
where uij is a numerical value between [0, 1]; ci is the cluster center of fuzzy group i; dij = kci ?xj k is the Euclidian
distance between ith cluster center and jth data point;
and m is called the exponential weight which influences
the degree of fuzziness of the membership (partition)
matrix.
2.1.2. Optimization of fuzzy clustering
algorithm
Usually a number of cluster centers are randomly initialized and the FCM algorithm provides an iterative
approach to approximate the minimum of the objective
function starting from a given position and leads to any
of its local minima. No guarantee ensures that FCM converges to an optimum solution (can be trapped by local
extrema in the process of optimizing the clustering criterion). The performance is very sensitive to initialization
of the cluster centers. An evolutionary algorithm is used
to decide the optimal number of clusters and their cluster
centers. The algorithm is initialized by constraining the
initial values to be within the space defined by the vectors
to be clustered. A very similar approach is given in (Hall
et al., 2001). In the i-Miner approach, the fuzzy clustering
algorithm is optimized jointly with the trend analysis algorithm (fuzzy inference system) in a single global search.
2.1.3. Self organizing map (SOM )
A self organizing map was used to cluster the user access records. The SOM is an algorithm used to visualize
and interpret large high-dimensional data sets. The map
consists of a regular grid of processing units, “neurons”. A
model of some multidimensional observation, eventually a
vector consisting of features, is associated with each unit.
The map attempts to represent all the available observations with optimal accuracy using a restricted set of
models. At the same time the models become ordered on
the grid so that similar models are close to each other
and dissimilar models far from each other. Fitting of the
model vectors is usually carried out by a sequential regression process, where t = 1, 2, . . . is the step index: For
each sample x(t), first the winner index c (best match) is
identified by the condition
?i , kx(t) ? mc (t)k ? kx(t) ? mi (t)k .
(2)
After that, all model vectors or a subset of them that belong to nodes centered around node c = c(x) are updated
380
A. Abraham
as
mi (t + 1) = mi (t) + hc(x),i (x(t) ? mi (t)) .
(3)
Here hc(x),i is the neighborhood function, a decreasing
function of the distance between the ith and cth nodes
on the map grid. This regression is usually reiterated over
the available samples.
2.2. Computational intelligence (CI )
based algorithms for trend analysis
CI substitutes intensive computation for insight into how
complicated systems work. Artificial neural networks,
fuzzy inference systems, probabilistic computing, evolutionary computation etc are some of the main components
of CI. CI provides an excellent framework unifying them
and even by incorporating other revolutionary methods.
2.2.1. Artificial neural network (ANN )
ANNs were designed to mimic the characteristics of the
biological neurons in the human brain and nervous system. Learning typically occurs by example through training, where the training algorithm iteratively adjusts the
connection weights (synapses). Backpropagation (BP) is
one of the most famous training algorithms for multilayer
perceptrons. BP is a gradient descent technique to minimize the error E for a particular training pattern. For
adjusting the weight (wij ) from the ith input unit to the
jth output, in the batched mode variant the descent is
?E
) for the total training set
based on the gradient ?E( ?w
ij
?wij
= ???
?E
+ ?? ?wij (n ? 1) .
?wij
(4)
The gradient gives the direction of error E. The parameters ? and ? are the learning rate and momentum
respectively.
2.2.2. Linear genetic programming (LGP)
Linear genetic programming proposed by Banzhaf et al.
(1998) is a variant of the GP technique that acts on linear genomes. Its main characteristics in comparison to
tree-based GP lies in that the evolvable units are not
the expressions of a functional programming language
(like LISP), but the programs of an imperative language
(like c/c ++). An alternate approach is to evolve a computer program at the machine code level, using lower level
representations for the individuals. This can tremendously
hasten up the evolution process as, no matter how an individual is initially represented, finally it always has to be
represented as a piece of machine code, as fitness evaluation requires physical execution of the individuals.
The basic unit of evolution here is a native machine
code instruction that runs on the floating-point processor unit (FPU). Since different instructions may have different sizes, here instructions are clubbed up together to
form instruction blocks of 32 bits each. The instruction
blocks hold one or more native machine code instructions,
depending on the sizes of the instructions. A crossover
point can occur only between instructions and is prohibited from occurring within an instruction. However the
mutation operation does not have any such restriction.
2.2.3. Fuzzy inference systems (FIS )
Fuzzy logic provides a framework to model uncertainty,
human way of thinking, reasoning and the perception
process. Fuzzy if-then rules and fuzzy reasoning are the
backbone of fuzzy inference systems, which are the most
important modelling tools based on fuzzy set theory. A
Takagi Sugeno fuzzy inference scheme was made used of
in which the conclusion of a fuzzy rule is constituted by
a weighted linear combination of the crisp inputs rather
than a fuzzy set (Sugeno, 1985). The Adaptive Network
Based Fuzzy Inference System (ANFIS) proposed by Jang
(1992) was used in the simulation, which implements
a Takagi Sugeno fuzzy inference system learned using
neural network learning.
2.2.4. Optimization of fuzzy inference system
The EvoNF framework proposed by Abraham (2002) was
used to optimze the fuzzy inference method, which is
an integrated computational framework to optimize fuzzy
inference system using neural network learning and evolutionary computation. Solving multi-objective scientific
and engineering problems is, generally, a very difficult
goal. In these particular optimization problems, the objectives often conflict across a high- dimension problem
space and may also require extensive computational resources. The hierarchical evolutionary search framework
could adapt the membership functions (shape and quantity), rule base (architecture), fuzzy inference mechanism
(T-norm and T-conorm operators) and the learning parameters of neural network learning algorithm. In addition to the evolutionary learning (global search) neural
network learning could be considered as a local search
technique to optimize the parameters of the rule antecedent/consequent parameters and the parameterized
fuzzy operators. The hierarchical search could be formulated as follows:
For every fuzzy inference system, there exist a global
search of neural network learning algorithm parameters,
parameters of the fuzzy operators, if-then rules and
Business Intelligence from Web Usage Mining
Fig. 7.
Chromosome structure of the i-Miner.
input variables
1
Fig. 8.
0
381
1
1
output variable
1
0
1
1
0
1
Chromosome representing an individual fuzzy rule (3 input variables and 1 output variable).
membership functions in an environment decided by the
problem. The evolution of the fuzzy inference system will
evolve at the slowest time scale while the evolution of the
quantity and type of membership functions will evolve at
the fastest rate. The function of the other layers could
be derived similarly. Hierarchy of the different adaptation
layers (procedures) will rely on the prior knowledge (this
will also help to reduce the search space). For example,
if one knows certain fuzzy operators will work well for a
problem then it is better to implement the search of fuzzy
operators at a higher level. For fine-tuning the fuzzy inference system all the node functions are to be parameterized. For example, the Schweizer and Sklar’s T-norm
operator can be expressed as:
1
T (a, b, p) = [max{0, (a?p + b?p ? 1)}]? p .
(5)
It is observed that
lim T (a, b, p) = ab
p?0
lim T (a, b, p) = min{a, b}
(6)
p??
which correspond to two of the most frequently used Tnorms in combining the membership values on the premise
part of a fuzzy if-then rule.
2.2.5. i-Miner : Chromosome modeling and
representation
Hierarchical evolutionary search process has to be represented in a chromosome for successful modeling of the
i-Miner framework. A typical chromosome of the i-Miner
would appear as shown in Fig. 7 and the detailed modeling
process is as follows.
Layer 1. The optimal number of clusters and initial cluster centers is represented in this layer.
Layer 2. This layer is responsible for the optimization
of the rule base. This includes deciding the total number of rules, representation of the antecedent and consequent parts. The number of rules grows rapidly with an
increasing number of variables and fuzzy sets. The gridpartitioning algorithm was used to generate the initial set
of rules. An iterative learning method is then adopted to
optimize the rules. The existing rules are mutated and
new rules are introduced. The fitness of a rule is given
by its contribution (strength) to the actual output. To
represent a single rule a position dependent code with as
many elements as the number of variables of the system is
used. Each element is a binary string with a bit per fuzzy
set in the fuzzy partition of the variable, meaning the absence or presence of the corresponding linguistic label in
the rule. For a three input and one output variable, with
fuzzy partitions composed of 3, 2, 2 fuzzy sets for input
variables and 3 fuzzy sets for output variable, the fuzzy
rule will have a representation as shown in Fig. 8.
Layer 3. This layer is responsible for the selection of
optimal learning parameters. Performance of the gradient descent algorithm directly depends on the learning
rate according to the error surface. The optimal learning
382
A. Abraham
parameters decided by this layer will be used to tune
the parameterized rule antecedents/consequents and the
fuzzy operators.
The rule antecedent/consequent parameters and the fuzzy
operators are fine tuned using a gradient descent algorithm to minimize the output error
E=
N
X
(dk ? xk )2
(7)
k=1
where dk is the kth component of the rth desired output vector and xk is the kth component of the actual
output vector by presenting the rth input vector to the
network. All the gradients of the parameters to be opti?E
mized, namely the consequent parameters ?P
for all rules
n
?E
?E
Rn and the premise parameters ??i and ?ci for all fuzzy
sets Fi (? and c represents the MF width and center of a
Gaussian MF).
Once the three layers are represented in a chromosome C, and then the learning procedure could be
initiated as follows:
a. Generate an initial population of N numbers of C
chromosomes. Evaluate the fitness of each chromosome
depending on the output error.
b. Depending on the fitness and using suitable selection methods reproduce a number of children for each
individual in the current generation.
c. Apply genetic operators to each child individual
generated above and obtain the next generation.
d. Check whether the current model has achieved the required error rate or the specified number of generations
has been reached. Go to Step b.
e. End
3. Experiment Setup-Training and
Performance Evaluation
In this research, the statistical/text data generated by
the log file analyzer from 01 January 2002 to 07 July
2002 were used. Selecting useful data is an important task
Table 1.
in the data pre-processing block. After some preliminary
analysis, the statistical data comprising of domain byte
requests, hourly page requests and daily page requests
were selected as focus of the cluster models for finding
Web users’ usage patterns. It is also important to remove
irrelevant and noisy data in order to build a precise model.
The additional input “index number ” was also included to
distinguish the time sequence of the data. The most recently accessed data were indexed higher while the least
recently accessed data were placed at the bottom. Besides the inputs “volume of requests” and “volume of pages
(bytes)” and “index number ”, the “cluster information”
provided by the clustering algorithm was also used as an
additional input variable. The data was re-indexed based
on the cluster information. The task is to predict (few
time steps ahead) the Web traffic volume on a hourly and
daily basis. The data from 17 February 2002 to 30 June
2002 for training and the data from 01 July 2002 to 06
July 2002 were used for testing and validation purposes.
The initial populations were randomly created based
on the parameters shown in Table 1. A special mutation
operator was used, which decreases the mutation rate as
the algorithm greedily proceeds in the search space. If the
allelic value xi of the ith gene ranges over the domain ai
and bi the mutated gene x0i is drawn randomly uniformly
from the interval [ai , bi ].
(
xi + ?(t, bi ? xi ) , if ? = 0
0
(8)
xi =
xi + ?(t, xi ? ai ) , if ? = 1
where ? represents an unbiased coin flip p(? = 0) = p(? =
1) = 0.5, and
b
t
?(t, x) = x 1 ? ? (1? tmax )
(9)
defines the mutation step, where ? is the random number
from the interval [0, 1] and t is the current generation and
tmax is the maximum number of generations. The function ? computes a value in the range [0, x] such that the
probability of returning a number close to zero increases
as the algorithm proceeds with the search. The parameter b determines the impact of time on the probability
Parameter settings of i-Miner.
Population size
Maximum no of generations
Fuzzy inference system
Rule antecedent membership functions
Rule consequent parameters
Gradient descent learning
Ranked based selection
Elitism
Starting mutation rate
30
35
Takagi Sugeno
3 membership functions per input variable (parameterized Gaussian)
linear parameters
10 epochs
0.50
5%
0.50
Business Intelligence from Web Usage Mining
i - Miner
383
training performance
RMSE (training data)
0.12
0.1
0.08
0.06
0.04
0.02
0
1
6
11
One day ahead trends
Fig. 9.
16
21
26
31
Evolutionary learning (no. of generations)
average hourly trends
Meta-learning performance (training) of i-Miner.
i - Miner
test performance
0.12
RMSE (test data)
0.1
0.08
0.06
0.04
0.02
0
1
6
11
One day ahead trends
Fig. 10.
16
21
average hourly trends
26
31
Evolutionary learning (no. of generations)
Meta-learning performance (testing) of i-Miner.
distribution ? over [0, x]. Large values of b decrease the
likelihood of large mutations in a small number of generations. The parameters mentioned in Table 1 were decided
after a few trial and error approaches. Experiments were
repeated 3 times and the average performance measures
are reported. Figures 9 and 10 illustrate the meta-learning
approach combining evolutionary learning and gradient
descent technique during the 35 generations.
Table 2 summarizes the performance of the developed i-Miner for training and test data. Performance is
compared with the previous results reported by Wang
et al. (2002) wherein the trends were analyzed using a
Takagi-Sugeno Fuzzy Inference System (ANFIS), Artificial Neural Network (ANN) and Linear Genetic Programming (LGP). The Correlation Coefficient (CC) for the test
data set is also given in Table 2. The 35 generations of
meta-learning approach created 62 if-then Takagi–Sugeno
type fuzzy rules (daily traffic trends) and 64 rules (hourly
traffic trends) compared to the 81 rules reported by Wang
et al. (2002).
Figures 11 and 12 illustrate the actual and predicted
trends for the test data set. A trend line is also plotted
using a least squares fit (6th order polynomial). As evident, the trend prediction by i-Miner outperformed other
conventional function approximation techniques.
FCM approach created 7 data clusters (Figs. 13 and
14) for hourly traffic according to the input features compared to 9 data clusters (Figs. 15 and 16) for the daily requests. The dark dots represent the cluster centers formed
by the evolutionary fuzzy clustering algorithm. Several
384
A. Abraham
Table 2.
Performance of the different paradigms.
Period
Daily (1 day ahead)
RMSE
Daily (1 day ahead)
RMSE
Method
Train
Test
CC
Train
Test
CC
i-Miner
TKFIS
ANN
LGP
0.0044
0.0176
0.0345
0.0543
0.0053
0.0402
0.0481
0.0749
0.9967
0.9953
0.9292
0.9315
0.0012
0.0433
0.0546
0.0654
0.0041
0.0433
0.0639
0.0516
0.9981
0.9841
0.9493
0.9446
Volume of requests (Thousands)
Daily requests
1200
900
600
300
1
2
3
4
5
6
! ! ! ! ! ! ! ! !
Day of the week
i-Miner
Actual vol. of requests
FIS
ANN
" " " " " " " " "
LGP
Web traffic trends
Fig. 11.
Test results of the daily trends for 6 days.
Average hourly page requests
$'$$'$
Actual no of requests
u$u
?$?'?$?$?'?$?
i-Miner
140
[$[
,$D$, \'D \ ?'t ?
-'E$- E u$$u
v
w$w
?$?'?$?$?'?$?
`'`x$x
y'y
¡$ $¡' '¡$ $¡$ $¡' '¡$ ¡
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$w
+$C'+ [$C s'[ s ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 I y'y
z'z
*'B$* Z$B r'Z r
+$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ?
z'?$z ?
q$q *'B$* Z$B r'Z r
+$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
p'?$p ? )$A') Y$A q$Y q *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
{
R$j'R j
?'m ?$? %$>$% > n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
?${ ?
:'R$: j'R j
#$='# U= ?'m ?$? %$>$% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
?${ ?
#$='# U= ?'m ?$? %$>$% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ?
|$?$| ? 5$5
6$N$6 f'N f ?'? 7$O'7 O$gO ?$? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$? $% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ?
|$?$| ? 5$M'5 e$M e
6$N$6 f'N f ~$?'~ ? 7$O'7 O$gO ?$? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$? $% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ? 4'4L$d'L |$d ?$| ? 5$M'5 e$M e ?'} ? 6$N$6 f'N f ~$?'~ ? 7$O'7 O$gO ?$ ? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$?
The rapid e-commerce growth has made both business community and customers face a new situation.
Journal of Information & Knowledge Management, Vol. 2, No. 4 (2003) 375–390
c iKMS & World Scientific Publishing Co.
Business Intelligence from Web Usage Mining
Ajith Abraham
Department of Computer Science, Oklahoma State University,
700 N Greenwood Avenue, Tulsa,Oklahoma 74106-0700, USA
[email protected]http://ajith.softcomputing.net
Abstract. The rapid e-commerce growth has made both
business community and customers face a new situation. Due
to intense competition on the one hand and the customer’s
option to choose from several alternatives, the business community has realized the necessity of intelligent marketing
strategies and relationship management. Web usage mining
attempts to discover useful knowledge from the secondary data
obtained from the interactions of the users with the Web.
Web usage mining has become very critical for effective Web
site management, creating adaptive Web sites, business and
support services, personalization, network traffic flow analysis and so on. This paper presents the important concepts of
Web usage mining and its various practical applications. Further a novel approach called “intelligent-miner” (i-Miner ) is
presented. i-Miner could optimize the concurrent architecture
of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy inference system to analyze the Web site
visitor trends. A hybrid evolutionary fuzzy clustering algorithm is proposed to optimally segregate similar user interests. The clustered data is then used to analyze the trends
using a Takagi-Sugeno fuzzy inference system learned using
a combination of evolutionary algorithm and neural network
learning. Proposed approach is compared with self-organizing
maps (to discover patterns) and several function approximation techniques like neural networks, linear genetic programming and Takagi–Sugeno fuzzy inference system (to analyze
the clusters). The results are graphically illustrated and the
practical significance is discussed in detail. Empirical results
clearly show that the proposed Web usage-mining framework
is efficient.
mains: content , structure and usage mining (Chakrabarti,
2003; Chang et al., 2001). This paper is concerned with
Web usage mining. Web servers record and accumulate
data about user interactions whenever requests for resources are received. Analyzing the Web access logs can
help understand the user behaviour and the web structure. From the business and applications point of view,
knowledge obtained from the Web usage patterns could be
directly applied to efficiently manage activities related to
e-business, e-services, e-education and so on (Chen & Kuo,
2000; Cheung et al., 1997). Accurate Web usage information could help to attract new customers, retain current
customers, improve cross marketing/sales, effectiveness of
promotional campaigns, track leaving customers and find
the most effective logical structure for their Web space
(Heer & Chi, 2001; Jespersen et al., 2002). User profiles
could be built by combining users’ navigation paths with
other data features, such as page viewing time, hyperlink structure, and page content (Cho et al., 2003). What
makes the discovered knowledge interesting had been addressed by several works (Hay et al. 2003; Heinrichs &
Lim, 2003; Runkler & Bezdek, 2003). Results previously
known are very often considered as not interesting. So the
key concept to make the discovered knowledge interesting
will be its novelty or unexpected appearance (Aggarwal
et al., 1999; Agrawal & Srikant, 1994; Coenen et al., 2000;
Nanopoulos et al., 2002).
A typical Web log format is depicted in Fig. 1. Whenever a visitor accesses the server, it leaves the IP, authenticated user ID, time/date, request mode, status,
bytes, referrer, agent and so on. The available data fields
are specified by the HTTP protocol. There are several
commercial software that could provide Web usage statistics (Analog, 2003; ClickTracks, 2003; Hitbox, 2003;
LogRover, 2003; Website Tracker, 2003; WebStat, 2003).
These stats could be useful for Web administrators to get
a sense of the actual load on the server. However, the
Keywords: Web mining; knowledge discovery; business intelligence; hybrid soft computing; neuro-fuzzy-genetic system.
1. Introduction Related Research
The WWW continues to grow at an amazing rate as
an information gateway and as a medium for conducting business. Web mining is the extraction of interesting and useful knowledge and implicit information from
artefacts or activity related to the WWW (Cooley, 2000;
Kosala & Blockeel, 2000). Based on several reserch studies we can broadly classify Web mining into three do375
376
A. Abraham
Fig. 1.
Sample entries from a Web server access log.
Web structure/content
information
Business services
Pattern analysis
Pattern discovery
Raw Web log data
Business intelligence
Data pre-processing
Web server
and cleaning
Usage statistics
—
ISP
Sequential/association
rule mining
Customer / Client
Fig. 2.
Web usage mining framework.
statistical data available from the normal Web log data
files or even the information provided by Web trackers
could only provide the information explicitly because of
the nature and limitations of the methodology itself.
Generally, one could say that the analysis relies on three
general sets of information given a current focus of attention: (1) past usage patterns; (2) degree of shared content;
and (3) inter-memory associative link structures. After
browsing through some of the features of the best trackers
available it is easy to conclude that rather than generating statistical data and texts they really do not help to
find much meaningful information.
For small web servers, the usage statistics provided
by conventional Web site trackers may be adequate to
analyze the usage pattern and trends. However as the size
and complexity of the data increases, the statistics provided by existing Web log file analysis tools may prove
inadequate and more intelligent knowledge mining techniques will be necessary (Piramuthu, 2003; Roussinov &
Zhao, 2003; Yang & Zhang, 2003; Abraham, 2003; Zhang
& Dong, 2003).
A generic Web usage mining framework is depicted in
Fig. 2. In the case of Web mining, data could be collected
at the server level, client level, proxy level or some consolidated data. These data could differ in terms of content
and the way it is collected etc. The usage data collected
at different sources represent the navigation patterns of
different segments of the overall Web traffic, ranging from
Business Intelligence from Web Usage Mining
single user, single site browsing behaviour to multi-user,
multi-site access patterns. Web server log does not accurately contain sufficient information for infering the behaviour at the client side as they relate to the pages served
by the Web server. Pre-procesed and cleaned data could
be used for pattern discovery, pattern analysis, Web usage ststistics and generating association/ sequential rules
(Kitsuregawa et al., 2002; Masseglia et al., 1999; Pal et al.,
2002). Much work has been performed on extracting various pattern information from Web logs and the application of the discovered knowledge range from improving
the design and structure of a Web site to enabling business organizations to function more efficiently (Paliouras
et al., 2000; Pazzani & Billsus, 1997; Perkowitz & Etzioni,
1998; Pirolli et al., 1996; Spiliopoulou & Faulstich, 1999).
Jespersen et al. (2002) proposed an hybrid approach
for analyzing the visitor click sequences. A combination
377
of hypertext probabilistic grammar and click fact table
approach is used to mine Web logs which could be also
used for general sequence mining tasks. Mobasher et al.
(1999) proposed the Web personalization system which
consists of offline tasks related to the mining of usage
data and online process of automatic Web page customization based on the knowledge discovered. LOGSOM proposed by Smith et al. (2003), utilizes a self-organizing
map to organize web pages into a two-dimensional map
based solely on the users’ navigation behavior, rather
than the content of the web pages. LumberJack proposed
by Chi et al. (2002) builds up user profiles by combining both user session clustering and traditional statistical traffic analysis using K-means algorithm. Joshi et al.
(1999) used relational online analytical processing approach for creating a Web log warehouse using access
logs and mined logs (association rules and clusters). A
Fig. 3.
University’s daily Web traffic pattern for 5 weeks.
Fig. 4.
Average hourly Web traffic patterns for 5 weeks.
378
A. Abraham
comprehensive overview of Web usage mining research
is found in (Cooley, 2000; Kosala & Blockeel, 2000;
Srivastava et al., 2000).
To demonstrate the efficiency of the proposed frameworks, Web access log data at the Monash University’s
Web site (Monash, 2003) were used for experimentations.
The University’s central web server receives over 7 million hits in a week and therefore it is a real challenge
to find and extract hidden usage pattern information. To
illustrate the University’s Web usage patterns, average
daily and hourly access patterns for 5 weeks (11 August
’02–14 September ’02) are shown in Figs. 3 and 4 respectively. The average daily and hourly patterns nevertheless tend to follow a similar trend (as evident from
the figures) the differences tend to increase during high
traffic days (Monday–Friday) and during the peak hours
(11:00–17:00 Hrs). Due to the enormous traffic volume and
chaotic access behavior, the prediction of the user access
patterns becomes more difficult and complex.
Self organizing maps and fuzzy c-means algorithm
could be used to seggregate the user access records and
computational intelligence paradigms to analyze the user
access trends. Abraham (2003) and Wang et al. (2002)
have clearly shown the importance of the clustering
algorithm to analyze the user access trends.
In the subsequent section the i-Miner framework is
presented and some theoretical concepts of clustering algorithms and computational intelligence paradigms are
discussed. Experiment results are provided in Sec. 3 and
some conclusions are provided towards the end.
2. Mining Framework Using Intelligent
Miner (i-Miner)
The i-Miner hybrid framework optimizes a fuzzy clustering algorithm using an evolutionary algorithm and a
Takagi–Sugeno fuzzy inference system using a combination of evolutionary algorithm and neural network learning. The raw data from the log files are cleaned and
pre-processed and a fuzzy C means algorithm is used to
identify the number of clusters. The architecture is illustrated in Fig. 5. The developed clusters of data are fed to a
Takagi-Sugeno fuzzy inference system to analyze the trend
patterns. The if-then rule structures are learned using an
iterative learning procedure (Cord´
on et al., 2001) by an
evolutionary algorithm and the rule parameters are finetuned using a backpropagation algorithm.
The hierarchical distribution of the i-Miner is depicted in Fig. 6. The arrow direction depicts the
speed of the evolutionary search. The optimization of
K n ow led ge d isco ve ry an d tren d p atterns
Log files
D ata
prep ro c ess in g
Fu zzy
clus terin g
Evolutionary
learning
Fu zzy Infe re nc e
S ys te m
Evolutionary
learning
O p tim iza tio n alg orith m s
Fig. 5.
i-Miner framework.
Neural
learning
Business Intelligence from Web Usage Mining
Fig. 6.
Hierarchical architecture of i-Miner.
clustering algorithm progresses at a faster time scale in
an environment decided by the inference method and the
problem environment. More technical details are provided
in the subsequent sections.
2.1. Clustering algorithms
2.1.1. Fuzzy clustering algorithm
One of the widely used clustering methods is the fuzzy
c-means (FCM) algorithm developed by Bezdek (1981).
FCM partitions a collection of n vectors xi , i = 1, 2 . . . , n
into c fuzzy groups and finds a cluster center in each group
such that a cost function of dissimilarity measure is minimized. To accommodate the introduction of fuzzy partitioning, the membership matrix U is allowed to have elements with values between 0 and 1. The FCM objective
function takes the form
c
c X
n
X
X
2
J(U, c1 , . . . , cc ) =
Ji =
um
(1)
ij dij
i=1
379
i=1 j=1
where uij is a numerical value between [0, 1]; ci is the cluster center of fuzzy group i; dij = kci ?xj k is the Euclidian
distance between ith cluster center and jth data point;
and m is called the exponential weight which influences
the degree of fuzziness of the membership (partition)
matrix.
2.1.2. Optimization of fuzzy clustering
algorithm
Usually a number of cluster centers are randomly initialized and the FCM algorithm provides an iterative
approach to approximate the minimum of the objective
function starting from a given position and leads to any
of its local minima. No guarantee ensures that FCM converges to an optimum solution (can be trapped by local
extrema in the process of optimizing the clustering criterion). The performance is very sensitive to initialization
of the cluster centers. An evolutionary algorithm is used
to decide the optimal number of clusters and their cluster
centers. The algorithm is initialized by constraining the
initial values to be within the space defined by the vectors
to be clustered. A very similar approach is given in (Hall
et al., 2001). In the i-Miner approach, the fuzzy clustering
algorithm is optimized jointly with the trend analysis algorithm (fuzzy inference system) in a single global search.
2.1.3. Self organizing map (SOM )
A self organizing map was used to cluster the user access records. The SOM is an algorithm used to visualize
and interpret large high-dimensional data sets. The map
consists of a regular grid of processing units, “neurons”. A
model of some multidimensional observation, eventually a
vector consisting of features, is associated with each unit.
The map attempts to represent all the available observations with optimal accuracy using a restricted set of
models. At the same time the models become ordered on
the grid so that similar models are close to each other
and dissimilar models far from each other. Fitting of the
model vectors is usually carried out by a sequential regression process, where t = 1, 2, . . . is the step index: For
each sample x(t), first the winner index c (best match) is
identified by the condition
?i , kx(t) ? mc (t)k ? kx(t) ? mi (t)k .
(2)
After that, all model vectors or a subset of them that belong to nodes centered around node c = c(x) are updated
380
A. Abraham
as
mi (t + 1) = mi (t) + hc(x),i (x(t) ? mi (t)) .
(3)
Here hc(x),i is the neighborhood function, a decreasing
function of the distance between the ith and cth nodes
on the map grid. This regression is usually reiterated over
the available samples.
2.2. Computational intelligence (CI )
based algorithms for trend analysis
CI substitutes intensive computation for insight into how
complicated systems work. Artificial neural networks,
fuzzy inference systems, probabilistic computing, evolutionary computation etc are some of the main components
of CI. CI provides an excellent framework unifying them
and even by incorporating other revolutionary methods.
2.2.1. Artificial neural network (ANN )
ANNs were designed to mimic the characteristics of the
biological neurons in the human brain and nervous system. Learning typically occurs by example through training, where the training algorithm iteratively adjusts the
connection weights (synapses). Backpropagation (BP) is
one of the most famous training algorithms for multilayer
perceptrons. BP is a gradient descent technique to minimize the error E for a particular training pattern. For
adjusting the weight (wij ) from the ith input unit to the
jth output, in the batched mode variant the descent is
?E
) for the total training set
based on the gradient ?E( ?w
ij
?wij
= ????E
+ ?? ?wij (n ? 1) .
?wij
(4)
The gradient gives the direction of error E. The parameters ? and ? are the learning rate and momentum
respectively.
2.2.2. Linear genetic programming (LGP)
Linear genetic programming proposed by Banzhaf et al.
(1998) is a variant of the GP technique that acts on linear genomes. Its main characteristics in comparison to
tree-based GP lies in that the evolvable units are not
the expressions of a functional programming language
(like LISP), but the programs of an imperative language
(like c/c ++). An alternate approach is to evolve a computer program at the machine code level, using lower level
representations for the individuals. This can tremendously
hasten up the evolution process as, no matter how an individual is initially represented, finally it always has to be
represented as a piece of machine code, as fitness evaluation requires physical execution of the individuals.
The basic unit of evolution here is a native machine
code instruction that runs on the floating-point processor unit (FPU). Since different instructions may have different sizes, here instructions are clubbed up together to
form instruction blocks of 32 bits each. The instruction
blocks hold one or more native machine code instructions,
depending on the sizes of the instructions. A crossover
point can occur only between instructions and is prohibited from occurring within an instruction. However the
mutation operation does not have any such restriction.
2.2.3. Fuzzy inference systems (FIS )
Fuzzy logic provides a framework to model uncertainty,
human way of thinking, reasoning and the perception
process. Fuzzy if-then rules and fuzzy reasoning are the
backbone of fuzzy inference systems, which are the most
important modelling tools based on fuzzy set theory. A
Takagi Sugeno fuzzy inference scheme was made used of
in which the conclusion of a fuzzy rule is constituted by
a weighted linear combination of the crisp inputs rather
than a fuzzy set (Sugeno, 1985). The Adaptive Network
Based Fuzzy Inference System (ANFIS) proposed by Jang
(1992) was used in the simulation, which implements
a Takagi Sugeno fuzzy inference system learned using
neural network learning.
2.2.4. Optimization of fuzzy inference system
The EvoNF framework proposed by Abraham (2002) was
used to optimze the fuzzy inference method, which is
an integrated computational framework to optimize fuzzy
inference system using neural network learning and evolutionary computation. Solving multi-objective scientific
and engineering problems is, generally, a very difficult
goal. In these particular optimization problems, the objectives often conflict across a high- dimension problem
space and may also require extensive computational resources. The hierarchical evolutionary search framework
could adapt the membership functions (shape and quantity), rule base (architecture), fuzzy inference mechanism
(T-norm and T-conorm operators) and the learning parameters of neural network learning algorithm. In addition to the evolutionary learning (global search) neural
network learning could be considered as a local search
technique to optimize the parameters of the rule antecedent/consequent parameters and the parameterized
fuzzy operators. The hierarchical search could be formulated as follows:
For every fuzzy inference system, there exist a global
search of neural network learning algorithm parameters,
parameters of the fuzzy operators, if-then rules and
Business Intelligence from Web Usage Mining
Fig. 7.
Chromosome structure of the i-Miner.
input variables
1
Fig. 8.
0
381
1
1
output variable
1
0
1
1
0
1
Chromosome representing an individual fuzzy rule (3 input variables and 1 output variable).
membership functions in an environment decided by the
problem. The evolution of the fuzzy inference system will
evolve at the slowest time scale while the evolution of the
quantity and type of membership functions will evolve at
the fastest rate. The function of the other layers could
be derived similarly. Hierarchy of the different adaptation
layers (procedures) will rely on the prior knowledge (this
will also help to reduce the search space). For example,
if one knows certain fuzzy operators will work well for a
problem then it is better to implement the search of fuzzy
operators at a higher level. For fine-tuning the fuzzy inference system all the node functions are to be parameterized. For example, the Schweizer and Sklar’s T-norm
operator can be expressed as:
1
T (a, b, p) = [max{0, (a?p + b?p ? 1)}]? p .
(5)
It is observed that
lim T (a, b, p) = ab
p?0
lim T (a, b, p) = min{a, b}
(6)
p??
which correspond to two of the most frequently used Tnorms in combining the membership values on the premise
part of a fuzzy if-then rule.
2.2.5. i-Miner : Chromosome modeling and
representation
Hierarchical evolutionary search process has to be represented in a chromosome for successful modeling of the
i-Miner framework. A typical chromosome of the i-Miner
would appear as shown in Fig. 7 and the detailed modeling
process is as follows.
Layer 1. The optimal number of clusters and initial cluster centers is represented in this layer.
Layer 2. This layer is responsible for the optimization
of the rule base. This includes deciding the total number of rules, representation of the antecedent and consequent parts. The number of rules grows rapidly with an
increasing number of variables and fuzzy sets. The gridpartitioning algorithm was used to generate the initial set
of rules. An iterative learning method is then adopted to
optimize the rules. The existing rules are mutated and
new rules are introduced. The fitness of a rule is given
by its contribution (strength) to the actual output. To
represent a single rule a position dependent code with as
many elements as the number of variables of the system is
used. Each element is a binary string with a bit per fuzzy
set in the fuzzy partition of the variable, meaning the absence or presence of the corresponding linguistic label in
the rule. For a three input and one output variable, with
fuzzy partitions composed of 3, 2, 2 fuzzy sets for input
variables and 3 fuzzy sets for output variable, the fuzzy
rule will have a representation as shown in Fig. 8.
Layer 3. This layer is responsible for the selection of
optimal learning parameters. Performance of the gradient descent algorithm directly depends on the learning
rate according to the error surface. The optimal learning
382
A. Abraham
parameters decided by this layer will be used to tune
the parameterized rule antecedents/consequents and the
fuzzy operators.
The rule antecedent/consequent parameters and the fuzzy
operators are fine tuned using a gradient descent algorithm to minimize the output error
E=
N
X
(dk ? xk )2
(7)
k=1
where dk is the kth component of the rth desired output vector and xk is the kth component of the actual
output vector by presenting the rth input vector to the
network. All the gradients of the parameters to be opti?E
mized, namely the consequent parameters ?P
for all rules
n
?E
?E
Rn and the premise parameters ??i and ?ci for all fuzzy
sets Fi (? and c represents the MF width and center of a
Gaussian MF).
Once the three layers are represented in a chromosome C, and then the learning procedure could be
initiated as follows:
a. Generate an initial population of N numbers of C
chromosomes. Evaluate the fitness of each chromosome
depending on the output error.
b. Depending on the fitness and using suitable selection methods reproduce a number of children for each
individual in the current generation.
c. Apply genetic operators to each child individual
generated above and obtain the next generation.
d. Check whether the current model has achieved the required error rate or the specified number of generations
has been reached. Go to Step b.
e. End
3. Experiment Setup-Training and
Performance Evaluation
In this research, the statistical/text data generated by
the log file analyzer from 01 January 2002 to 07 July
2002 were used. Selecting useful data is an important task
Table 1.
in the data pre-processing block. After some preliminary
analysis, the statistical data comprising of domain byte
requests, hourly page requests and daily page requests
were selected as focus of the cluster models for finding
Web users’ usage patterns. It is also important to remove
irrelevant and noisy data in order to build a precise model.
The additional input “index number ” was also included to
distinguish the time sequence of the data. The most recently accessed data were indexed higher while the least
recently accessed data were placed at the bottom. Besides the inputs “volume of requests” and “volume of pages
(bytes)” and “index number ”, the “cluster information”
provided by the clustering algorithm was also used as an
additional input variable. The data was re-indexed based
on the cluster information. The task is to predict (few
time steps ahead) the Web traffic volume on a hourly and
daily basis. The data from 17 February 2002 to 30 June
2002 for training and the data from 01 July 2002 to 06
July 2002 were used for testing and validation purposes.
The initial populations were randomly created based
on the parameters shown in Table 1. A special mutation
operator was used, which decreases the mutation rate as
the algorithm greedily proceeds in the search space. If the
allelic value xi of the ith gene ranges over the domain ai
and bi the mutated gene x0i is drawn randomly uniformly
from the interval [ai , bi ].
(
xi + ?(t, bi ? xi ) , if ? = 0
0
(8)
xi =
xi + ?(t, xi ? ai ) , if ? = 1
where ? represents an unbiased coin flip p(? = 0) = p(? =
1) = 0.5, and
b
t
?(t, x) = x 1 ? ? (1? tmax )
(9)
defines the mutation step, where ? is the random number
from the interval [0, 1] and t is the current generation and
tmax is the maximum number of generations. The function ? computes a value in the range [0, x] such that the
probability of returning a number close to zero increases
as the algorithm proceeds with the search. The parameter b determines the impact of time on the probability
Parameter settings of i-Miner.
Population size
Maximum no of generations
Fuzzy inference system
Rule antecedent membership functions
Rule consequent parameters
Gradient descent learning
Ranked based selection
Elitism
Starting mutation rate
30
35
Takagi Sugeno
3 membership functions per input variable (parameterized Gaussian)
linear parameters
10 epochs
0.50
5%
0.50
Business Intelligence from Web Usage Mining
i - Miner
383
training performance
RMSE (training data)
0.12
0.1
0.08
0.06
0.04
0.02
0
1
6
11
One day ahead trends
Fig. 9.
16
21
26
31
Evolutionary learning (no. of generations)
average hourly trends
Meta-learning performance (training) of i-Miner.
i - Miner
test performance
0.12
RMSE (test data)
0.1
0.08
0.06
0.04
0.02
0
1
6
11
One day ahead trends
Fig. 10.
16
21
average hourly trends
26
31
Evolutionary learning (no. of generations)
Meta-learning performance (testing) of i-Miner.
distribution ? over [0, x]. Large values of b decrease the
likelihood of large mutations in a small number of generations. The parameters mentioned in Table 1 were decided
after a few trial and error approaches. Experiments were
repeated 3 times and the average performance measures
are reported. Figures 9 and 10 illustrate the meta-learning
approach combining evolutionary learning and gradient
descent technique during the 35 generations.
Table 2 summarizes the performance of the developed i-Miner for training and test data. Performance is
compared with the previous results reported by Wang
et al. (2002) wherein the trends were analyzed using a
Takagi-Sugeno Fuzzy Inference System (ANFIS), Artificial Neural Network (ANN) and Linear Genetic Programming (LGP). The Correlation Coefficient (CC) for the test
data set is also given in Table 2. The 35 generations of
meta-learning approach created 62 if-then Takagi–Sugeno
type fuzzy rules (daily traffic trends) and 64 rules (hourly
traffic trends) compared to the 81 rules reported by Wang
et al. (2002).
Figures 11 and 12 illustrate the actual and predicted
trends for the test data set. A trend line is also plotted
using a least squares fit (6th order polynomial). As evident, the trend prediction by i-Miner outperformed other
conventional function approximation techniques.
FCM approach created 7 data clusters (Figs. 13 and
14) for hourly traffic according to the input features compared to 9 data clusters (Figs. 15 and 16) for the daily requests. The dark dots represent the cluster centers formed
by the evolutionary fuzzy clustering algorithm. Several
384
A. Abraham
Table 2.
Performance of the different paradigms.
Period
Daily (1 day ahead)
RMSE
Daily (1 day ahead)
RMSE
Method
Train
Test
CC
Train
Test
CC
i-Miner
TKFIS
ANN
LGP
0.0044
0.0176
0.0345
0.0543
0.0053
0.0402
0.0481
0.0749
0.9967
0.9953
0.9292
0.9315
0.0012
0.0433
0.0546
0.0654
0.0041
0.0433
0.0639
0.0516
0.9981
0.9841
0.9493
0.9446
Volume of requests (Thousands)
Daily requests
1200
900
600
300
1
2
3
4
5
6
! ! ! ! ! ! ! ! !
Day of the week
i-Miner
Actual vol. of requests
FIS
ANN
" " " " " " " " "
LGP
Web traffic trends
Fig. 11.
Test results of the daily trends for 6 days.
Average hourly page requests
$'$$'$
Actual no of requests
u$u
?$?'?$?$?'?$?
i-Miner
140
[$[
,$D$, \'D \ ?'t ?
-'E$- E u$$u
v
w$w
?$?'?$?$?'?$?
`'`x$x
y'y
¡$ $¡' '¡$ $¡$ $¡' '¡$ ¡
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$w
+$C'+ [$C s'[ s ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 I y'y
z'z
*'B$* Z$B r'Z r
+$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ?
z'?$z ?
q$q *'B$* Z$B r'Z r
+$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
p'?$p ? )$A') Y$A q$Y q *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
{
R$j'R j
?'m ?$? %$>$% > n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
?${ ?
:'R$: j'R j
#$='# U= ?'m ?$? %$>$% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ?
?${ ?
#$='# U= ?'m ?$? %$>$% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ?
|$?$| ? 5$5
6$N$6 f'N f ?'? 7$O'7 O$gO ?$? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$? $% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ?
|$?$| ? 5$M'5 e$M e
6$N$6 f'N f ~$?'~ ? 7$O'7 O$gO ?$? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$? $% V'> V n$?'n ?
&'?$& W'? o$W ?$o ? ($@'( X$@ p'X ?$p ? )$A') Y$A q$Y ?'q ? *'B$* Z$B r'Z ?$r ? +$C'+ [$C s'[ ?$s ? ,$D$, \'D \ ?'t ?
-'E$- ]'E ] u$$u F'. F$. ^F ?$v ? /$G'/ G_$_ w$'w 0'0$H$0 `'H `x$'x 1$I'1 Ia$y'a ?$y ? 2$J'2 Jb$z'b ?$z ? 3'3K$c'K c ?${ ? 4'4L$d'L |$d ?$| ? 5$M'5 e$M e ?'} ? 6$N$6 f'N f ~$?'~ ? 7$O'7 O$gO ?$ ? 8$P'8 h$P h ?'?$? ? 9'Q$9 Q'iQ ?$ ? :'R$: j'R j?$?$? ? ;'S$; k$S ?'k ??$?