1. INTRODUCTION

Mobile devices are very popular for communication and accessing mobile services. Mobile services can be accessed anywhere via information service providers (Chen et al., 2012). By the development of wireless communication techniques and high feature mobile devices, mobile commerce has become easier and fast. Today most of the mobile devices have high features and support for internet and web services (Kiukkonen et al., 2010). These devices are capable of sending requests for some transactions and services (Perez et al., 2010; Gao et al., 2013). They are also capable of transferring information between multiple users. Services may include selling, purchasing, online information accessing, or using social networking sites, etc. These various kinds of services are accessed by mobile devices and accessed information is stored in the transaction log files (Kiukkonen et al., 2010). Transactions mainly store user information, location information, and time information during which the user accesses any service, and finally the details of services are stored. For fast response from the system for any requested service, data mining operations can be applied to this stored information. These operations may be the mining of similar kinds of services, finding similar habits of users, and preparing groups according to services, etc. By applying such kinds of data mining operations we can restructure the web service environment and take advantage of providing recommendations and predictions for interested users. These are also helpful for business peoples for enhancing their business strategies in web environments.

새창으로 보기

Fig. 1

Different users movement in various locations

Traditional mobile services are inadequate in handling user movement pattern analysis without the use of location, time of the service, and service request details (Lee, 2007). Over the past years some studies have employed various data mining techniques to provide interesting patterns in mobile service environments (Liu & Keselj, 2007; Pabarskaite & Raudys, 2007). Association rules are used to find unknown frequent patterns between parameters (Agrawal & Srikant, 1994). Apriori is the pioneer for mining frequent itemsets from transaction databases. FP-Growth, which is based on a pattern growth method was afterward proposed to achieve a better performance than Apriori-based methods. FP-Growth improves efficiency of frequent items because it only scans databases twice. Some studies have also focused on the uses of large databases (Cheng et al., 2004). Some recent studies are going to mine the moving path on service request log mines (Agrawal & Srikant, 1994). Researchers have also studied the problem of location tracking (Yavas et al., 2005; Tsai et al., 2007; Tseng & Lu, 2009) and resource allocation (Huang & Lin, 2008; Huang et al., 2003; Peng & Chen, 2005; Peng & Chen, 2003). Bipartite graph matching is also used to find mobile user movement behavior (Ilyas et al., 2004; Fayyazi et al., 2004; Monnot & Toulouse, 2007). Currently, different approaches are in progress to find interesting patterns of mobile users (Lee et al., 2007; Lancieri & Durand, 2006; Tseng et al., 2007; Terziyan & Vitko, 2003; Huang et al., 2003). In mobile e-commerce environments interesting user behaviors can also be predicted, based on accessed services sequences. In this paper, we analyze the behavior of the mobile user movement and find the interesting patterns. Here we have used an associated tree method for joining multiple parameters of mobile access environments. These generated patterns are helpful to business people for launching new services and for providing quick responses to existing ones. figure 1 shows the simple scenario in which different locations are randomly visited by users. Here l₁,l₂,l₃...l_n shows the different locations and u₁,u₂,u₃...u_n represents different mobile users. In this proposed associated tree based pattern mining approach we have used a predefined minimum support value using those interesting patterns which are extracted from the generated candidate records. An acsociated tree based record represents the relationship between four predefined parameters, and its numeric value represents the degree of matching relation of a particular record.

In this paper mobile users, visited locations, dwell time, and services are used to construct the associated tree. Associated trees are used to find the frequent patterns. A Maxflow database is used to represent the relation between these four parameters and joining operations performed between them. This proposed approach is compared with the Apriori candidate generation algorithm. The remainder of this paper is organized as follows. Section 2 defines the basics of the user movement on different locations. Section 3 shows the proposed approach for mobile user behavior analysis by joining associated trees. The experiments conducted and results obtained are explained in section 4. Finally the conclusion is presented in section 5.

2. PRELIMINARIES AND PROBLEM DEFINITION

Mobile e-commerce is an emerging field for recommendation and user behavior analysis. For predicting mobile user behavior, data mining techniques are used. Various parameters are responsible for user behavior prediction. The main parameters are user, visited locations, timestamp, and services (Chen et al., 2012; Mohbey & Thakur, 2013). By these parameters, we can mine various patterns for users. According to these generated patterns, prediction and recommendations are easier. In this paper, we have generated patterns using an associated tree method and the above discussed parameters. Based on generated patterns business people are entitled to launch new services, design appropriate strategies, and so on. The following terminologies are used in this paper.

Definition 1 (Mobile User). U={u₁, u₂, u₃,...u_n}is the set of mobile users. Each mobile user represents a physical person who carries a mobile device that has the capability of receiving services from the mobile environment (Chen et al., 2012; Mohbey & Thakur, 2013).

Definition 2 (Visited Location). L={l₁,l₂,l₃,...l_n}is the set of locations at which users visit and stay for some time (Mohbey & Thakur, 2013).

Definition 3 (Timestamp). T={T₁,T₂,T₃,...T_n} is the set of time durations where mobile users spend time for using requested services. The timestamp T_n, as defined in Table 2, is assumed to have an equal period and a uniform unit. The maximum duration is considered 30 minutes in general (Chen et al., 2012).

Definition 4 (Mobile Services). S={s₁,s₂,s₃,...sn} is the set of mobile services requested by the mobile users.

Definition 5 (Support of a Relation). The support of a relation r, such as user→location, user→time, user→ service, location→time etc, is denoted as sup(r) and defined as the number of tuples that contain r in the maxflow database. For example in Table 3, the support of the relation u₁→l₁ is 3.

Definition 6 (Matching Join). If M⊆U⋈L⋈T⋈S. this M is a match join of U,L,T,S (Chen et al., 2012; Mohbey & Thakur, 2013).

Table 1 shows the mobile user movement database in which (l_i,Time); l_i identifies the Location and Time in HH:MM:SS format. This table is derived from figure 1. Here 3 users visited different locations at different times.

새창으로 보기

Table 1.

Database for Mobile User Movement

Table 2 shows the predefined timeslots. Maximum duration taken is 30 minutes. According to this, we divide a whole day into 48 time slots of 30 minutes each. These time slots are identified as T₁,T₂,T₃...T₄₈. Each time slot indicates a particular time when a particular user accesses a service from some location.

새창으로 보기

Table 2.

Predefine Time Slots for a day

Table 3 shows the maxflow database in which each record represents the user-location-time-service relation. This relation is used to prepare frequent n-trees.

3. FREQUENT ASSOCIATED TREE PATTERN MINING

Associated trees are used to extract the interesting frequent patterns from the various relationships of the user-location-time-service values. Frequent tree patterns are extracted by applying loops. Then we get n-tree candidate patterns. To find the interesting frequent patterns, we firstly scan the maxflow database and generate frequent 1-tree candidate patterns. If the extracted candidate pattern is less than the predefined minimum support value then this pattern is pruned.

새창으로 보기

Table 3.

Maxflow Database of Mobile user-location-time-service relations

Now, a matching join operation is applied to generate a frequent 2-tree pattern. Again if the extracted candidate pattern support is less than the predefined minimum support then infrequent patterns are pruned. Similarly we extract the 3-tree candidate pattern and then the n+1 tree candidate frequent pattern. This process continues until the tree is empty or no more candidates are generated.

After getting each n-tree candidate frequent pattern set we prepare a associated sub tree of the relation record and count the nodes on it. Here maximum node count of a sub tree represents the strong frequent tree pattern. Algorithm 1 show the complete process of frequent associated tree pattern mining (Chen et al., 2012).

새창으로 보기

This whole process of finding frequent candidate patterns is illustrated in the example below.

4. ILLUSTRATIVE EXAMPLE

The complete procedure of associated tree pattern mining is shown here. For this illustration we have taken 15 records in the maxflow database which is shown in table 3. Matching join operation is performed between four parameters to generate candidate sets. These candidate sets are and frequent item sets are L₁, L₂, L₃, L₄... L_n.

4.1. Generating Candidate Set

The proposed approach firstly generates the candidate set for user, location, dwell time, and services. These generated candidate sets are shown in Table 4, Table 5, Table 6, and Table 7 respectively.

새창으로 보기

Table 4.

Candidate set for user

새창으로 보기

Table 5.

Candidate set for location

새창으로 보기

Table 6.

Candidate set for dwell time

새창으로 보기

Table 7.

Candidate set for service

4.2. Generating Candidate Set

Now we apply a matching join operation between and frequent itemset L₁, then we found candidate set and L₂. These sets are U_i⋈L_j, U_i⋈T_k, U_i⋈S_m, L_j⋈T_k, L_j⋈S_m and T_k⋈S_m. These matching joins are represented in Table 8 to Table 13 and corresponding frequent 2-tree candidate patterns in Figures 2 to 7 respectively.

Table 8 represents the matching join of U_i⋈L_j. It is prepared by counting the relation of U_i⋈L_j as

u₁→l₁=3,

u₁→l₂=1,

u₁→l₄=1,

u₂→l₁=0,

u₂→l₂=1,

u₂→l₄=2,

u₃→l₁=1,

u₃→l₂=3,

u₃→l₄=2

We prune the relations which have lesser count from the predefined minimum support. In this example we have set minimum count=2; so that the relation u₁→l₁, u₂→l₄, u₃→l₂, u₃→l₄ follows the matching join condition. These relations are denoted in Table 8 and the corresponding frequent 2-tree candidate pattern is shown in Figure 2. Associated Trees prepared by various cases of the matching join U_i⋈L_j, are presented in Table 8. By joining all these cases we find the final frequent candidate tree of 13 nodes.

새창으로 보기

Table 8.

Matching joins for U_i⋈L_j

새창으로 보기

Fig. 2

Associated tree for U_i⋈L_j of Table 8

Similarly, different 4 candidate sets are shown in Table 9, Table 10, Table 11, Table 12, and Table 13. Its frequent 2-Tree is shown in Figure 3, Figure 4, Figure 5, Figure 6, and Figure 7 respectively.

새창으로 보기

Table 9.

Matching joins for U_i⋈T_k

새창으로 보기

Fig. 3

Associated tree for U_i⋈T_k of Table 9

새창으로 보기

Table 10.

Matching joins for U_i⋈S_m

새창으로 보기

Fig. 4

Associated tree for U_i⋈S_m of Table 10

새창으로 보기

Table 11.

Matching joins for L_j⋈T_k

새창으로 보기

Fig. 5

Associated tree for L_j⋈T_k of Table 11

새창으로 보기

Table 12.

Matching joins for L_j⋈S_m

새창으로 보기

Fig. 6

Associated tree for L_j⋈S_m of Table 12

새창으로 보기

Table 13.

Matching joins for T_k⋈S_n

새창으로 보기

Fig. 7

Associated tree for T_k⋈S_m of Table 13

In all candidate sets of 4 we have counted nodes by associated tree as

No. of nodes in U_i⋈L_j = 13

No. of nodes in U_i⋈T_k = 14

No. of nodes in U_i⋈S_m = 10

No. of nodes in L_j⋈T_k = 11

No. of nodes in L_j⋈S_m = 8

No. of nodes in T_k⋈S_m = 13

By these matching joins we identified that the relation U_i⋈T_k has the maximum node from all candidate sets, which is depicted in Figure 3 Thus it is clear that the relation U_i⋈T_k is stronger than the other matching relations of the candidate sets of .

4.3. Generating Candidate Set

Now we find the candidate sets of and frequent itemset L₃. These are prepared by the relation U_i⋈L_j⋈ T_k, U_i⋈L_j⋈S_m, U_i⋈T_k⋈S_m and L_j⋈T_k⋈S_m. candidate sets are illustrated in Tables 14 to 17 and the correspondent associated 3-Tree is shown in Figures 8 to 11 respectively.

새창으로 보기

Table 14.

Matching joins for U_i⋈L_j⋈T_k

새창으로 보기

Fig. 8

Associated tree for U_i⋈L_j⋈T_k of Table 14

새창으로 보기

Table 15.

Matching joins for U_i⋈L_j⋈S_m

새창으로 보기

Fig. 9

Associated tree for U_i⋈L_j⋈S_m of Table 15

새창으로 보기

Table 16.

Matching joins for U_i⋈T_k⋈S_m

새창으로 보기

Fig. 10

Associated tree for U_i⋈T_k⋈S_m of Table 16

새창으로 보기

Table 17.

Matching joins for L_j⋈T_k⋈S_m

새창으로 보기

Fig. 11

Associated tree for L_j⋈T_k⋈S_m of Table 17

U_i⋈L_j⋈T_k are constructed by the counting of relations as

u₁→l₁→T₁₃=2,

u₁→l₁→T₃₈=1,

u₂→l₄→T₂₅=1,

u₂→l₄→T₃₈=1,

u₃→l₂→T₁₃=2,

u₃→l₂→T₂₅=1,

u₃→l₄→T₁₃=1,

u₃→l₄→T₂₅=1.

In all these counted relations we prune the relations which have less count (<2) from the predefined minimum support so that u₁→l₁→T₁₃=2 and u₃→l₂→T₁₃=2 satisfy the minimum support. These relations are denoted in Table 14 with the corresponding frequent 3-Tree in Figure 8. Similarly different candidate sets and associated trees are prepared. After preparing all associated sub trees the following nodes are counted:

No. of nodes in U_i⋈L_j⋈T_k =7

No. of nodes in U_i⋈L_j⋈S_m=2

No. of nodes in U_i⋈T_k⋈S_m=9

No. of nodes in L_j⋈T_k⋈S_m=8

It is observed that the relation U_i⋈T_k⋈S_m has the maximum node count, thus this relation is stronger than other relations of the candidate set .

4.4. Generating Candidate Set

In the next step we generate the candidate set for relation U_i⋈L_j⋈T_k⋈S_m. It is shown in Table 18. Here we observed that the count of this relation is less than the predefined minimum support (1<2). Thus the process is terminated and the frequent item set and 4-tree candidate pattern are not prepared. Hence this relation is neglected.

새창으로 보기

Table 18.

Matching joins for U_i⋈L_j⋈T_k⋈S_m

By the illustrated example we have found a strong associated tree among sets Here relation U_i⋈T_k and U_i⋈T_k⋈S_m are the stronger relations among all the relations. These relations show that these mobile accessing patterns are the most frequent relations. By these obtained relations one can predict that, if we know the user id and time, then services can be easily identified. According to this illustration the location parameter is less important for service prediction. These mined patterns are also helpful for future prediction and recommendation of services.

5. EXPERIMENTAL EVALUATION

We evaluate the performance of the proposed algorithm in this section. The experiments were performed on a 3.0 GHz processor with 2 GB of memory and the operating system Microsoft Windows 7. The algorithms are implemented in Java. The experiment was conducted on various parameters which are shown in Table 19.

새창으로 보기

Table 19.

Parameter settings

새창으로 보기

Fig. 12

No. of Nodes with different minimum support when maxflow Database=5000

새창으로 보기

Fig. 13

No. of Nodes with different minimum support when maxflow Database=10000

5.2. Analysis Case 2-Different Item Counts

In this experiment, the number of mobile access patterns was again set to 5,000 and 10,000. Figures 14 and 15 show the performance result with respect to different minimum support values. Figures 14 and 15 show that as the minimum support value varied from 0.1% to 1% the number of items decreases.

새창으로 보기

Fig. 14

No. of Items with different minimum support when maxflow Database=5000

새창으로 보기

Fig. 15

No. of Items with different minimum support when maxflow Database=10000

5.3. Analysis Case 3-Different Mobile Access Patterns

In this analysis, we have compared the number of nodes in associated tree patterns and the number of mobile access patterns with respect to different minimum support values. Figures 16 to18 show these comparison results. Figure 16 shows the number of nodes and mobile access patterns with respect to min support=0.2%. Figure 16 shows that the number of nodes increased, while the number of mobile access patterns increased. The variation also shows between number of nodes and mobile access patterns while minimum support is 0.5% and 0.8% respectively. This variation is shown in Figures 17 and 18 respectively.

새창으로 보기

Fig. 16

Nodes and mobile access patterns with respect to 0.2% minimum support

새창으로 보기

Fig. 17

Nodes and mobile access patterns with respect to 0.5% minimum support

새창으로 보기

Fig. 18

Nodes and mobile access patterns with respect to 0.8% minimum support

5.4. Discussion

In this subsection experimental inferences are discussed. By the above experiments, the proposed associated tree based approach is shown to outperform the state-of-the-art approach Apriori process. The experimental results show that the proposed approach takes less time as compared to a basic association rule generation Apriori process. Execution time comparisons are shown in Figure 19. Table 20 shows the number of generated patterns with both approaches. Thus, the performance of the associated tree based approach is the best among the compared approaches. The proposed approach is also better in comparison with memory utilization.

새창으로 보기

Table 20.

Number of patterns with compared approaches

새창으로 보기

Fig. 19

Execution time in response to change in different minimum support

6. CONCLUSIONS AND FUTURE WORK

In this paper, we proposed an approach to generate strong frequent patterns between different mobile accessing parameters including user, location, dwell time, and web services. These patterns are generated by the matching joins and presented as associated trees. The proposed approach generates a k-tree frequent pattern in the maxflow database according to defined support values. By the experimental results under the various simulated data, the proposed approach is valuable for recommending and predicting services for different users. The proposed approach is also helpful in business and e-commerce environments where web services are important. The comparison of this approach is done with standard Apriori algorithm, in which we find that the results of the proposed approach are excellent.

For future work, we plan to explore more efficient mobile pattern generation algorithms, and design more efficient frameworks to predict mobile services. In addition, we plan to apply some specific constraints in mining processes to achieve efficient behavior of mobile users. It is also planned to find service patterns according to utility or importance bases.