An Effective Method Based on Bi-Clustering and Association Rules for User Activity Analysis in Location-Based Social Network

As mentioned in the abstract section, these rules are easy to follow as long as you replace the "content" without changing the "form". It is very important to create a good recommender system with higher accuracy in business applications and ultimately attract other customers to partner companies. Today, location-based social networks (LBSN) have received considerable attention. The emerging progress of the mobile device industry makes smart phones widely used everywhere in daily life. Also, due to the advent of Internet technology, the mobile phone has become a necessary tool that allows users to get information in real time.

Your smart phone can manage various life activities, including searching for interesting information like online shopping, a travel plan with GPS sensors, online education, and job search.

This explosion in the use of LBSN services makes it possible to record a large amount of mobile data with various data resources. With these resources, you can help determine users' movement patterns, recognizing and tracking their behavior along the way. Numerous LBSNs have been created for this purpose, they can be divided into collaborative filtering-based and content-based [1]. LBSN enables the sharing of services and has received a lot of attention, e.g., Gowalla [2], which is examined in detail in this paper.

Recently, LBSN merged social networks and mobile trajectory data [3]. LBSNs have experienced a great evolution, spurring millions of mobile device users to share their favorite locations with location-based content. Due to the large amount of information in LBSN, it is very important to design an efficient scheme for analyzing users’ activities. However, compared to existing works, it suffers from low veracity and efficiency, which is why data mining techniques based on representation and data modeling have been very successful in the last decade [4, 5]. However, data mining techniques have been widely used in several fields, including the semantic web [6], computer vision [7], and LBSN analysis [8]. Data mining methods allow you to generate and build models based on existing data named training data. These models are valuable data representation, discovery, and predictive analysis tools [9]. In summary, we have proposed a new method for user activity analysis based on biclustering and association rules. First, the biclustering method is used before extracting rules to find sub-matrices of rows and columns that are as similar to each other and as different from the rest. In addition, the Apriori algorithm [10, 11] is applied to each sub-matrix to collectively describe users’ preferred locations and behaviors. In the designed framework, user comments and their movement from position (place) to position (place) complement each other. Therefore, the presented method is a powerful tool to describe and explain the heterogeneous data collected by LBSN.

In the generated model, we consider two factors of the association rules, including location and user feedback. The given model is (X→Y[support%, Confidence% and Lift]), where X and Y are the places visited by the user, while (support, trust, and lift) are measures used to evaluate an association rule.

The contributions provided in this paper are used to improve the customization of purpose recommender systems. By looking at a large number of places visited by users, we figured out how real users prefer their favorite places and should be able to make more realistic recommendations. In addition, the biclustering method reduces the study area, which improves the quality of the generated model and is used directly as a regional model within a location recommender system.

The rest of this paper is organized as follows. In Section 2, we present the relevant work. Section 3 explains the proposed methodology. The results of the experiment are given in Section 4. Finally, Section 5 is the conclusion.

Figure 1 presents the scheme of the proposed method of extraction association rules from LBSN dataset. Therefore, the process consists of four main steps. (i) The first one is for preprocessing of the dataset (thus some operations, including treatment of null value and preparing the data matrices (user_location /user_comment)). (ii) The second step is the application of the biclustering algorithm to select revealing sub- matrices showing a unique pattern. (iii)The third step is the application of the Apriori algorithm on the sub-matrices. However, the Apriori algorithm consists of two major steps: (1) extract overall frequents itemsets, then, step (2) extracts useful association rules from the frequents itemset that are provided by step (1). (iv) The fourth step consists of visualization and interpretation of the utile extracted rules.

1.png

Figure 1. Design scheme of user activity based biclustering and association rules in LBSN Model

3.1 Location based social network

LBSN systems aim to merge online social network features and permit users to share their urban data, which enclose spatiotemporal information and social aspects, including the user’s preferences and routines [26]. Besides this process is well-known as a participatory sensor network [27], One essential point is that users can manually determine when, how, where, and what to share.

2.png

Figure 2. Illustrate an example of LBSN architecture based on the GPS features

Formally, the concept of LBSNs [28, 29] corresponds to graph G the form of a 3-tuple where V is the set of nodes e.g. users, and E refers to the set of edges that describe the social connections between users, and C is the users' check-in dataset. In Figure 2, we illustrate an example of LBSN architecture [30]. This architecture is based on the GPS features, which locates users and permits them to share spatiotemporal data such as location and location-tagged media content, for instance, texts, photos and videos. The architecture includes two layers. In the Online Social Networks (OSNs) Layer, users form their social networks, according to interactions in LBSNs, and the Physical Location Layer (PLL): Permits to users by checking in and checking-out per location-based services applications.

3.2 Association rules

The extraction association rules model between items in huge dataset has been introduced by Agrawal et al. [10], which the first algorithm is named by Apriori [11]. The extraction of association rules consists of two major steps. Step 1 is to find all frequent itemset, which have support superior or equal than the minimum thresholds defined previously and denoted as Minsupp. Step 2 generates all the association rules from frequent itemset, that is generated in step one. These rules should have confidence superior or equal than to the minimum thresholds defined previously and denoted as Minconf. Thus, a number of rules are accepted, while others are rejected by Apriori.

Assume that the association rules defined as: $(X \rightarrow Y$ [support $\%$, Confidence $\%$ and Lift]) with $X \cap Y=\emptyset$. Where $\mathrm{X}$ and $\mathrm{Y}$ are frequent itemset $\mathrm{X}$ is named the left-hand-side (LHS). While $\mathrm{Y}$ is named the right-hand-side (RHS).; whereas the support $\%$, Confidence $\%$ and Lift are measures of quality of rule which indicate the reliability, precision and validity of rule respectively [31].

These measures are calculated as follow:

$\operatorname{support}(X \rightarrow Y)=\frac{\text { numberof }(X \text { and } Y)}{\text { Total number of transaction }}$      (1)

confidence $(X \rightarrow Y)=\frac{\operatorname{support}(X \rightarrow Y)}{\operatorname{support}(X)}$     (2)

$\operatorname{lift}(X \rightarrow Y)=\frac{\operatorname{support}(X \rightarrow Y)}{\operatorname{support}(X) \times \operatorname{support}(C Y)}$     (3)

To present the pseudo code of Apriori Algorithm we need to describe these variable s: C_k refer to Candidate itemset of size k, L_k: frequent itemset of size k, D: a set of transactions and t represent one transaction. minsup is threshold of min support.

Algorithm Apriori

Input: D: a set of transactions

Minsup: threshold of min support

Output:L: the frequents Itemsets.

1. L₁={1- frequents itemsets)
2.  k=2;
3.  while L_k-1 non vide Do
4.  C_k=Apriori-Gen (L_k); //C_k is generated by joining L_k-1with itself
5.        for eacht of D Do
6.          C_t=Subset (C_k, t); {the itemset candidatescontenus in Ck}
7.                    For each c of C_tDo
8.                   c.count++;
9.          end For
10.         end For
11.        L_k={c de C_t/c.count>= minsup};
12.         k++;
13.  End while
14.         Return ∪ L_k;

When we Apriori return frequent itemset it will be used by generation rules algorithm to generate a useful association rule which satisfy both minimum support and minimum confidence (minconf) the pseudo code of gen-rules Algorithms as follow:

Algorithm gen-rules:

1. For each frequent Itemset f_i Do
2.       generate all sub-itemsetsI_j of f_i
3. End For

4. For each sub-itemset I_joff_iDo
5.          Generate rule(I_j→(f_i - I_j )) if M in conf >= threshold minconf
6. End For

3.3 Data initialization and preparation

Here, we describe the step of initializing and preparing data, including user-location and user-comment matrices. Then, we apply the biclusteringalgorithm to select sub matrices with the same patterns. Finally, we apply the Apriori algorithm to extract association rules as Figure 3 illustrates the process.

6a.png

(a)

6b.png

(b)

Figure 3. Present the process of transformation matrices:(a) matrix for present users with location visited;(b) matrix for describe users comments

3.3.1 User-location data

Let U and L represent users and locations respectively. We define the function F_u,l for computing the frequency of a user that is to be found in location l. the F_u,l is:

$F_{u, l}=\left\{\begin{array}{l}f_{u, l} \text { number of user which } \\ \text { located in location } l \\ 0 \quad \text { otherwise }\end{array}\right.$      (4)

The biclustering algorithm provides sub matrices. Afterward, we transformed each cluster of the define user-location of binary data. Form such as sub-matrices $S M \in R^{U \times L}$:

$S M_{u, l}=\left\{\begin{array}{lc}1 & \text { if } f_{u, l} \geq 1 \\ 0 & \text { otherwise }\end{array}\right.$      (5)

where, the value SM_u,l=1 refers to that the users’ u visited the location l. Likewise, a value of 0 does not locate in location l.

3.3.2 User-comment data

Let U and C denote the number of users and comments respectively. First, we compute the frequency C_u,c of each user that is made comment about check-in spot. The representation of C_u,c as:

$C_{u, c}=\left\{\begin{array}{l}c_{u, c} \text { number of comment } c \\ 0 \quad \text { otherwise }\end{array}\right.$     (6)

Then, we define the user-comment based on binary data form such as interaction matrix $M C \in R^{U \times C}$ from users and the visited places as:

$M C_{u, c}=\left\{\begin{array}{l}1 \text { if } c_{u, c} \geq 1 \\ 0 \text { otherwise }\end{array}\right.$     (7)

At this point, a value of 1 for MC_u,c indicates that the user u put comment c.

3.3.3 Biclustering algorithm

Analyses of large scale LBSN data and notably spatiotemporal data need to focus on clustering algorithms. However, biclustering methods were introduced for revealing sub- matrices illustrating similar patterns. Thus, we investigate and study an algorithm named X motifs algorithm to biclustering for LBSN data. Then, the results of this method are used by the Apriori algorithm in order to provide a useful association rule with high performances.

The X motifs algorithm was introduced by Murali and Kasif [32]. Since it searches for conserved gene states, another step of pre-processing is required. Once the data matrix user location is generated, the algorithm chooses a random column noticed by (nl: refer to the number locations) then performs these steps:

Step 1. Choose an sd: Stand for subset of columns and nu: Represent a number of users. Followed by collecting all rows with equal state belongs in this subset, including the above column.

Step 2. Collect all columns where these rows (generated by step1) which have the same state.

Step 3. Return the bicluster if it has the most rows of all the bicluster found and if it is also larger than an alpha fraction of the data.

3.4 Dataset Gowalla

We have evaluated and tested the planned methodology on Gowalla datasets, which is a publicly available. Gowalla is an LBSN lunched on 2007 [33], permitting users to share their spatiotemporal information with friends through check-ins. This dataset has the largest social network of any public. Gowalla covers 30.367 geo-referenced spots of New York city and has information concerning 357,753 visits of 19,183 users. Thus, the Gowalla dataset contains the following files spots.txt, which contains information’s about spots, that have identified by ids, names, and geospatial coordinates. The users.txt file of Gowalla defines users, by ids, names, hometowns and geospatial coordinates. The highlights.txt file is a table contains the spots marked as highlights by Gowalla users, enclose spot and user ids, together with a textual description as well as the category of spot. Finally, the users-spots.txt file is a table enclosed the spots visited by Gowalla users, the spot and user ids, appear together with attribute a Boolean value that indicating if the user frequently visits the spot. Table 1 and Table 2 present the data type and categories of Gowalla respectively.

Table 1. The proprieties Gowalla dataset

Table 2. The categories offered by Gowalla