A Novel Frequent Pattern Mining Technique for Prediction of User Behavior on Web Stream Data

Over the last two decades in India due to rapid growth of E-Commerce, penetration of mobile phones has changed the way to communicate and do business through an Internet [1]. The main reasons for accessing the internet are entertainment, online communication and Social Networking. As per the information revealed by Google India in 2016 hundred million people are going online to purchase because of increasing of internet penetration.

One of the example for E-Commerce is Online shopping. Now a days over the internet most of the customers are directly buying the products. 

Popular E-Commerce sites in India are:

Flipkart

Amazon

Snapdeal

To tack any communication and to record each transaction of the HTTP Protocol we need one file which is called as Web log file [2]. A weblog file is a file which records all user activities occurred over a period of time [3].

It also contains effective usage of web data. There are 4 types of Server logs: Transfer, Agent, Error and referrer log. If the number of customers increased from million to billion the size of log data also increases due to more transactions on online data [4]. Generally web usage data contains the information about IP Address of the user, the

type of file he accessed, which browser he is accessing, how many bytes he accessed [5].

This log file is also used to analyze the customer behavior like number of people who have visited the web site in how many sessions, Total time spent on a web site, how many times he accessed the same webpage [6].

Analyzing the customer behavior is the key factor to optimize the any E-commerce sites, to know the kinds of goods and problems they are facing during online shopping. Usage of internet based applications increases due to increased number of customers which will lead to increasing of event access log size produced on web servers [7]. The size of the access logs varies from Tera bytes to Peta Bytes.

For Periodic analysis of access logs software companies spent a large budget on development of these applications [8]. To handle event access logs efficiently in offline mode a traditional data analytic method called Hadoop provide the capabilities using Map Reduce Algorithm.

Hadoop is not an efficient Technique to handle the Unbounded and Streaming of log data as they produced in real world applications. The main drawback of offline processing is that some context and information collected from event log becomes useless and irrelevant [9].

A modified framework is designed to perform Parallel Processing of Big data than the Hadoop is called Spark. It permits both batch and stream Processing while Hadoop mostly for batch processing [10]. Even though Spark uses Hadoop Distributed File System (HDFS) in some circumstances Spark runs hundred times faster than Hadoop.

In addition to handling the static data when it is available Spark also process Real time data Applications within a short time [11]. Spark support various applications like Graph Computation, Processing of streaming data and in Machine Learning and it Perform analytics on these applications is very simple way and fast [12].

Even though Spark uses Hadoop Distributed File System (HDFS) in some circumstances Spark runs hundred times faster than Hadoop [24]. In addition to handling the static data when it is available Spark also process Real time data Applications within a short time.

Spark support various applications like Graph Computation, Processing of streaming data and in Machine Learning and it Perform analytics on these applications is very simple way and fast.

Spark is well suited one which is shown in Figure 1. The two important sub-components of the spark framework are:

Spark Streaming Core: It is responsible for providing core APIs, which are required to setup the streaming context, so that the processing of stream of logs (or any data streams) is done more effectively. We have set these two intervals in Scala language as follows:

scalaval WINDOW_LENGTH = new Duration(100)

scalaval SLIDE_INTERVAL = new Duration(20)

It is clear that, at a particular moment, the streams over the recent past 100 ms will be observed for the processing (WINDOW_INTERVAL) and the observation window will move forward after each 20 ms.

Spark Engine Core: Apache Spark core functionalities are provided by Spark Engine core, which is responsible for establishing spark environment generating and transforming of RDDs is considered.

figure_1.jpg

Figure 1. Spark based data collection and user behaviour analysis on large stream data

Spark based data extraction and user behavior analysis is achieved by implementing 3steps or algorithms. First establish the real time streaming server connection for streaming data second Preprocess the large streaming data by creating 3 cluster instances and in third analyzing the user behavior by using Predicting the future navigation pattern mining using historical behaviour and user patterns, and generate the user correlated patterns using min threshold in 1 or more sessions.

Algorithm 1: Real-time Streaming Server Connection for streaming data

Input: Amazon EC2, Streaming log data.

Output: Streaming data fields in cluster instances.

Procedure:

Step 1:

Connection con=Amazon EC2(Instances[]);

Step 2: for each instance in instance list

Do

Setup(Instance[i])

Setup(Spark(Instance[i])

done

Step 3: for each instance in Instancelist

Do

If(instance[i]!==start)

Then

Start instance[i];

Streamer s=getConnection(URL);

if(S.connection==NULL)

return NULL;

Else

Start spark in the instance[i].

LogList[]=getLogData(S);

End if

Done

Step 4: Partition the LogList[] into m number of clusters.

Let logList[]={LogList[0],LogList[1]….LogList[m]};

For each cluster instance

Do

Assign FilteringJob(LogList[i],instance[i]);

Done

In this algorithm, amazon AWS server is used to run the proposed model on the real-time e-commerce streaming dataset. In the step 1, Amazon AWS servers are configured with specified number of cluster instances. In the step 2, for each cluster instance spark framework is installed to perform map reduce operations. In the step 3, each cluster instance is started with the specific data configurations. In this step, streaming log data is captured and stored in the file using the realtime e-commerce websites. In the step 4, each cluster instance is started and data is ready to apply Mapper phase for data filtering. Here, in this step, data is filtered to find the relevant fields and its partitioned data to each cluster instance of Amazon AWS server.

Algorithm 2: FilteringJob(LogList[],instance[])

Input: Streaming Logdata, cluster instances CI.

Ouput: Log streamining fields with filtering

Procedure:

For each cluster instance CI[i]

Do

Fields F[]=LogList[i]

For each field in F[]

Do

If(F[j]==Null &&F[j]==Numerical)

Then

Find Max probability of occurrence in Streaming data at time t.

$F[j]=Max\{|\frac{X-F[i]}{\Pr ob(F[c])}|;log(|{{\mu }_{F[i]}}-{{\sigma }_{F[i]}}|).MinMaxNormalization(F[i])\}c=1..\#classes$ (1)

End if

If(F[j]==Null &&F[j]==Nominal)

Then

$F[j]=Max\Pr ob\{\frac{Log(\Pr ob(F[i]/F[c]))}{\Pr ob(F[c])};log(F[c])*Prob(F[i]\cup F[c])\}c=1..\#classes,$ (2)

End if

Done

For each mapper m in M[]

Do

Partition streaming fields to each mapper

M[i]=Partition(F[],k);// K partitions to each mapper

// Finding frequent patterns on each mapper using the FPtree[10] algorithm as initial candidate frequent patterns.

M_Patterns[]=FPtree(M[i],m);//m=1,2,..|M[i]| itemset candidate sets

Done

Done

Streaming data is pre-processed using the algorithm 2. In this algorithm, each cluster instance is processed to extract the streaming web log fields. If the field is numerical type then Eq. (1) is used to find the most possible occurrence of streaming field. Similarly for nominal streaming type, eq (2) is used to find the most possible steaming field using the probabilistic measure. As shown in Figure 1, proposed model is implemented on realtime server with high dimensional streaming e-commerce data. Here, user specified cluster instances are created and configured in Amazon AWS environment to run the proposed model on streaming data. Spark framework is used to partition the data and to integrate the data using the Mapper and Reducer phases. In each cluster instance, a series of operations such as field extraction process, data filtering process and web user navigation behaviour are analyzed using the proposed model.In this model, each mapper is partitioned using the filtered fields of the streaming data. To each partition, frequent patterns on the subset of fields are computed by using the FPtree algorithm. Here, FPtree algorithm is used to construct the initial candidate patterns for the mathematical user behavior analysis in the next model.

Algorithm 3: Web user behavior using feature selection process on streaming data

Input: Cluster instances CI[],Cluster instance filtered data CIFD[], user navigation paths NP, user query.

Ouput: Predicting the user’s navigation paths using streaming pattern mining model.

Procedure:

// Predicting the future navigation pattern mining using historical behaviour and user patterns

For each user in the userslist UList[]

Do

For each filtered data CIFD[]

Do

// Predicting the future navigation behaviour using the following prediction formula

Rank[]=

$\max \{\frac{\prod{\Pr ob(q/CIFD[j])}}{\Pr ob(q\cap NP[j]},linear\_regression(q,NP[])\}$ (3)

Mapper(Rank[],CI[]); 

Done

Done

//Generate user correlated patterns using η_min threshold in 1 or more sessions

FPRules ← ∅;

Find 1-Dimension frequents of user navigations as (It₁) in each session S[]

For each session S[k]

do

for (i=2, It_i-1 !=∅, i ++)

do

(CorrSet_i,S[k])ßProb(It_i-1,It₁)=

$\frac{\Pr ob(I{{t}_{i-1}}\cup I{{t}_{1}})}{Correlation(I{{t}_{i-1}},I{{t}_{1}})}\Pr ob(\{I{{t}_{i-1}}\cap I{{t}_{1}}\}/NP[])$ (4)

done

For each K-Set $I{{t}_{i}}$∈(CorrSet_i,S[k])

do

w_i=ProbVals(Rank[], It_i)

if w_i≥ η_min then

FPRules[]ßMapper(fps_m∪{It_i, w_i})

end if

done

for each frequent patterns FPRules[]

do

for each cluster instance CI[]

Reduce(FPRules[],Rank[])

Done

Done

In this algorithm, Cluster instances CI[],Cluster instance filtered data CIFD[], user navigation paths NP, user query are taken as input for each spark cluster instance. Initially, this algorithm will predict the future navigation patterns using the ranking measure of eq (3). This ranking measure is used to find the maximization of the navigation pattern related to each user in the Mapper phase. After the future navigation patterns, user based correlated patterns are extracted using the eq (4). Here, each user historical navigation pattern is compared with the streaming data to find the most relevant correlated navigation patterns. These frequent patterns are integrated using the Reducer phase of spark.

Now a days there is a more value to real time or streaming data than the data stored in darabases. We also discussed the processing of real time and batch data analysis using Spark tool. Analyzation of this real time data is useful for prediction of user behavior in single or multiple websites. In this paper a novel dynamic model is introduced to discover the required knowledge from the large databases. A new filter based user navigation pattern mining model is also designed and implemented on the large online steaming databases. The proposed filtered based frequent pattern mining model efficiently predicts the user navigation patterns with high accuracy and less runtime.