# Context Prediction of Mobile Users Based on Time-Inferred Pattern Networks: A Probabilistic Approach

Authors: Yong-Hyuk Kim; Yourim Yoon
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We present a probabilistic method of predicting context of mobile users based on their historic context data. The presented method predicts general context based on probability theory through a novel graphical data structure, which is a kind of weighted directed multigraphs. User context data are transformed into the new graphical structure, in which each node represents a context or a combined context and each directed edge indicates a context transfer with the time weight inferred from corresponding time data. We also consider the periodic property of context data, and we devise a good solution to context data with such property. Through test, we could show the merits of the presented method.


---

## Body

## 1. Introduction

In recent years, the function of mobile device has been largely extended. Besides call and message service, mobile users usually play games, listen to music, and watch TV, just with their devices. So soon many people cannot get along without their mobile devices [1]. Moreover, mobile device can detect its location and sense the status of the device and current weather such as temperature, humidity, and atmospheric pressure [2]. As such historic context data of mobile users increase cumulatively, now it becomes quite important to provide users with advanced services based on their expected context.Advertisers want to know mobile users that will do something or locate in some places within a specific time period [3]. Assume that as a result of context prediction a mobile user U is expected to reach a location L in near future. Then, as an example service, stores near the location L can send ads to him or her. In other words, an owner of a restaurant near the location L can send ads to whom will reach nearby his/her restaurant (see Figure 1(a)). Also, mobile users can get some information in advance about, for example, what to do, where to go, or who to call/message [4]. The user U may want to get some new information near the location L. For example, the user U can get the parking information regarding a resort, where he/she will go probably soon, while staying at the restaurant (see Figure 1(b)). Context prediction of mobile users can provide advertisers and mobile users with useful information services.Example illustrations of intelligent services based on historic context data of mobile users. (a) An example service for advertisers (Ad of a restaurant in the above small box). (b) An example service for users (Parking info of a resort in the above small box).
(a)
(b)For the advanced services, we should predict user's context correctly using his/her previous historic context data. Any context data gathered by mobile device or its sensors are available. Then user contexts are composed of user activities, user locations, weather information, and so on. All of them are time-stamped. In this paper, we present a probabilistic method providing context prediction based on user historic context data. In recent years, there have been many studies to predict context of mobile users. However most of them focused only on location prediction and many of them were based on just machine learning and rule-based techniques. When we compare our method with them, the most distinguishable feature of the proposed method is that it predicts general context based on probability theory through a novel graphical structure with time-based edge weights.The remainder of the paper is organized as follows. In Section2, we introduce recent related work about context prediction in mobile environments. In Section 3, we present our prediction scenarios. We propose our probabilistic method using a new graphical structure called time-inferred pattern network in Section 4. In Section 5, we provide some test results. Finally we give our conclusions in Section 6.


## 2. Related Work

In recent years, there have been many studies to predict context of mobile users. However most of them focused only on location prediction and many of them were based on just machine learning techniques [5–7]. Also, some of them were based on simple rule-based methods [8, 9].In this study, we need user's historic context data, but there have been approaches without user's historic data. Karmouch and Samaan [10] predicted the traveling trajectory and destination using knowledge of user's preferences and analyzed spatial information without user's historic data. Ying et al. [11] predicted the next location of a user's movement based on both the geographic and semantic features of users' trajectories. Their prediction model is based on a cluster-based strategy which evaluates the next location of a mobile user based on the frequent behaviors of similar users in the same cluster. Voigtmann et al. [12] also presented a collaborative context prediction technique to overcome the gap of missing context information in the user's context history.As similar approaches to ours, there have been studies that are probability based, graph based, or using time concept. Liu and Karimi [7] proposed trajectory prediction methods by a probability-based model and a learning-based model. Wang and Cheng [13] devised an approach for mining periodic maximal promising movement patterns based on a graph structure and a random sampling technique. Chen et al. [14] introduced graph-matching algorithms for mining user movement behavior patterns. Laasonen [15] used other context variables such as time to predict mobile user routes. Bradley and Rashad [16] introduced a time-based location prediction technique by mining mobile sequential patterns. However, all of them are quite simple approaches. Here we present a unified approach using probability theory on a new time-inferred graph structure.Predicting the location of mobile users was a frequently tackled subtask of mobile context prediction in recent researches. There have also been a few studies for predicting general context beyond location, but many of them were also based on just machine learning techniques from user behavior [17, 18]. Tseng and Lin [19] mined and predicted user behavior patterns based on the assumption that the location and the service are inherently coexistent. Hassani and Seidl [20] introduced a method for predicting a next health context of mobile users using multiple contextual streams that influence the health context. In this study, we also consider multiple contexts for predicting any type of context.


## 3. Prediction Scenarios

### 3.1. Used Context Types

In mobile computing, location is usually used to approximate context and to implement context-aware applications [6, 7, 9]. However there is more to context than location as illustrated in Figure 2 [21]. We used two types of context data: sensing data and log data. Sensing data consist of location, device status (e.g., idle or calling), activity (e.g., exercising, listening to music, watching TV, or playing games), and weather such as weather type, temperature, humidity, and wind direction/speed. Used log data are as follows: call log, SMS log, played music log, Email log, chatting log, and visited Web log. The above data of each mobile user is periodically transferred to a server. The server analyzes the historic context data and predicts the next context of each user. The next subsections give our prediction scenarios.Figure 2
An example illustration of various context types.


### 3.2. Prediction on Multiple Context

From multiple types of historic context data, we predict the context that belongs to the given target context type and will occur the most probably within the given time period. The motivation of using multiple types of context data is from the assumption that heterogeneous context as well as homogeneous context probably affects the next context considerably. Figure3 illustrates the context prediction based on multiple types of context data. In the figure, given context data of location and weather for three days in time order, we want to predict the third context of the fourth day.Figure 3
An example illustration of context prediction based on multiple types of context data.


### 3.3. Prediction on Periodic Context

This prediction scenario is an extension of that given in Section3.2. We assume that users may show different patterns according to some period. For example, the patterns of a typical user on weekday will be quite different from those on weekend. Figure 4 illustrates the context prediction based on periodic context data classified by “a day of the week.” This user may show different patterns on Monday and Saturday. If we ignore this data type of “a day of the week,” even with a good prediction algorithm, inaccurate prediction results may be obtained.Figure 4
An example illustration of context prediction based on periodic context data classified by days of the week.


## 3.1. Used Context Types

In mobile computing, location is usually used to approximate context and to implement context-aware applications [6, 7, 9]. However there is more to context than location as illustrated in Figure 2 [21]. We used two types of context data: sensing data and log data. Sensing data consist of location, device status (e.g., idle or calling), activity (e.g., exercising, listening to music, watching TV, or playing games), and weather such as weather type, temperature, humidity, and wind direction/speed. Used log data are as follows: call log, SMS log, played music log, Email log, chatting log, and visited Web log. The above data of each mobile user is periodically transferred to a server. The server analyzes the historic context data and predicts the next context of each user. The next subsections give our prediction scenarios.Figure 2
An example illustration of various context types.


## 3.2. Prediction on Multiple Context

From multiple types of historic context data, we predict the context that belongs to the given target context type and will occur the most probably within the given time period. The motivation of using multiple types of context data is from the assumption that heterogeneous context as well as homogeneous context probably affects the next context considerably. Figure3 illustrates the context prediction based on multiple types of context data. In the figure, given context data of location and weather for three days in time order, we want to predict the third context of the fourth day.Figure 3
An example illustration of context prediction based on multiple types of context data.


## 3.3. Prediction on Periodic Context

This prediction scenario is an extension of that given in Section3.2. We assume that users may show different patterns according to some period. For example, the patterns of a typical user on weekday will be quite different from those on weekend. Figure 4 illustrates the context prediction based on periodic context data classified by “a day of the week.” This user may show different patterns on Monday and Saturday. If we ignore this data type of “a day of the week,” even with a good prediction algorithm, inaccurate prediction results may be obtained.Figure 4
An example illustration of context prediction based on periodic context data classified by days of the week.


## 4. Proposed Method

### 4.1. Input Context Data

Input data are given in the following form. First, the target context typeT to predict is given. The maximum prediction time is also provided. Historic context data of a user are given in a series of 〈starting time, ending time, context type, context element〉, which are sorted by starting time in nondecreasing order. An example of historic context data can be shown as follows: 〈12:00, 13:00, location, restaurant〉, 〈13:10, 13:30, activity, listening to music〉, 〈13:20, 17:50, weather, rainy〉,   〈13:20, 18:00, location, resort〉, and so on.


### 4.2. Time-Inferred Pattern Network

Context history can be represented as a graph. For context prediction, we use a new data structure calledtime-inferred pattern network (TIPN). We can consider TIPN as a kind of directed weighted multi-graph. Each node means context or its combination. There are three types of nodes. Type-I nodes represent given context elements (e.g., restaurant, listening to music, rainy, resort). Each type-I node has the information of the average and the standard deviation of stay times, where stay time means the difference between starting time and ending time (i.e., stay time = ending time − starting time). Type-II nodes deal with ordered pairs of context elements belonging to different context types (e.g., (restaurant, listening to music), (restaurant, rainy), (listening to music, rainy), (listening to music, resort), (rainy, resort)). Each type-II node has the information of the average, the standard deviation, and the frequency of time gaps, where time gap means the difference between starting times of the two context elements (i.e., time gap = starting time of the second context element − that of the first). Each type-III node is for a series of context elements that are frequently appeared. Here the number of context elements of a type-III node is not limited. Each type-III node has the same information as type-II node, but time gap becomes the difference between starting times of the first context element and the last one. Each directed edge contains movement information from some (combined) context to a target context element. The information contains the average, the standard deviation, and the frequency of time gaps, where time gap is the difference between starting times of starting node and ending one. Each edge also has its weight. The edge weight presents the magnitude of possibility from context to context. The same patterns increase the weight.


#### 4.2.1. Information of Nodes and Edges

In this subsection, we note some information of nodes and edges to be used in TIPN. First, we assume that there arek context types. We have three types of nodes. Information for each type of nodes are given in the following. For a type-I node u for each context type, we maintain the average of stay times (μu), the standard deviation of stay times (σu), and the frequency (cu). Similarly for a type-II node u for context pair of different context types, we have ordered context pair (γ1u,γ2u), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Considering a type-III node u coming from frequently appearing context sequence, we maintain common context sequence (γ1u,γ2u,…,γluu), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Finally, we consider multiple edges between context type S and target context type T. Edge set E=⋃u∈S,v∈TEu,v, where Eu,v={eu,v,1,eu,v,2,…,eu,v,k,…}. The following is information about the kth edge between node u and node v: the average of time gaps (μu,v,k), the standard deviation of time gaps (σu,v,k), the frequency (cu,v,k), and the weight (wu,v,k). Figure 5 shows multiple directed edges between nodes in TIPN.Figure 5
Multiple directed edges between nodes in TIPN.


#### 4.2.2. Preprocessing

To make type-III nodes, we find frequent subpatterns from context log. For each context elementτ in target context type T, we extract subsequences ending with τ within time window. (Since the maximum prediction time is given, we do not use the context data beyond the maximum prediction time when we generate a TIPN.) Let nτ be the number of extracted subsequences and let γ1τ,γ2τ,…,γnττ be the extracted subsequences. For each pair of subsequences, we find its longest common subsequence (LCS) [22]. Then we have nτ(nτ+1)/2 LCSes. Using Levenshtein distance [23] and k-means clustering [24] upon them, we obtain the optimal k and k clusters. For each cluster, we find a central sequence so that its length is as short as possible. We add these central sequences to the type-III node set. If the length of a central sequence is just one, we discard the corresponding node.


#### 4.2.3. Construction

We construct a TIPN after the preprocessing of creating type-III nodes. Starting with an empty TIPN composed of isolated nodes, we iteratively construct nodes and edges as reading input context data one by one. Algorithm1 shows the detailed pseudocode for constructing a TIPN.Algorithm 1:Pseudocode for constructing a TIPN after preprocessing.
Start with an empty TIPN composed of isolated nodes;
For  i←1to  inputdatasize-1 // read input context data
// constructing type-I nodes and their edges
for  k←1to  i′swindowsize-1
Update info of type-I nodeni;
if type-I node ni+k belongs to Tthen
Update edge(ni,ni+k);
// constructing type-II nodes and their edges
for  k←1 to i′swindowsize-2
if context type of ni+k≠ context type of nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-II noden′=(ni,ni+k);
Update edge(n′,ni+t);
// constructing type-III nodes and their edges
for  k←1to  i′swindowsize-2
if  ∃ a type-III node n′′ starting with the node nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-III noden′′;
Update edge(n′′,ni+t);When we update each edge, we test a normal distribution against accumulated time-gaps for the edge. In the case that they do not follow normal distributions, we divide the edge into two or more edges. So there may be multiple edges between each pair of nodes. The weightwu,v,k of each edge eu,v,k is determined in proportion to its frequency fu,v,k and the magnitudes of its corresponding time gaps.


#### 4.2.4. Maintenance

It is clear that recent context data is more important than old ones. So we devise an aging strategy of edges to give more weights to recent data than old ones. We periodically apply it to only the edge weights per a unit time, for example, a day, a week, a month, or a year. That is, all edge weights are periodically updated as follows:wu,v,k=α×wu,v,k for all edge eu,v,k, where α<1. (We set α to be 0.9 in our experiments.) Also, we remove weakly connected edges. Given threshold t for removing edges, we remove edge eu,v,k when its weight wu,v,k is less than t.In the case that a TIPN has already been constructed and we have added context data, we do the same procedure of Algorithm1 starting with the previously constructed TIPN instead of an empty TIPN.


### 4.3. Prediction Algorithm

#### 4.3.1. Assumptions

In general, we assume that time-gap data for each edge and stay-time data for each node follow a normal distribution. If the collected data is sufficient, our assumption is reasonable bythe law of large numbers in probability theory [25]. However, in the case that the collected data is sparse, the assumption is not good. In such cases, we assume the data follow a uniform distribution. In more detail, we assume that the data follow U[μ-3σ,μ+3σ], where μ and σ mean the average and the standard deviations of sampled time data, respectively. The following fact supports our assumption.Fact 1.
The average and the variance ofU[μ-3σ,μ+3σ] are μ and σ2, respectively.Proof.
Let a random variableX follow U[μ-3σ,μ+3σ], and let f(t) be the probability density function of X. Then,
(1)f(t)={123σifμ-3σ≤t≤μ+3σ0otherwise,E(X)=∫-∞∞‍tf(t)dt=∫μ-3σμ+3σ‍t23σdt=(μ+3σ)2-(μ-3σ)243σ=μ,Var(X)=E(X2)-E(x)2=∫-∞∞‍t2f(t)dt-μ2=∫μ-3σμ+3σ‍t223σdt-μ2=(μ+3σ)3-(μ-3σ)363σ-μ2=σ2.


#### 4.3.2. Sum of Edge Distribution and Node One

First we consider the sum of normal distributions. It is well known in probability theory, for example, [25]. If N1 and N2 are independent random variables that are normally distributed, then their sum is also normally distributed. That is, if N1~N(μ1,σ12),N2~N(μ2,σ22), and N1 and N2 are independent, then N1+N2~N(μ1+μ2,σ12+σ22). This means that the sum of two independent normally distributed random variables is normal, with its mean being the sum of the two means, and its variance being the sum of the two variances (i.e., the square of the standard deviation is the sum of the squares of the standard deviations).Next we consider the sum of uniform distributions. We assume thatU1 and U2 are independent random variables that are uniformly distributed, that is, U1~U[l1,u1] and U2~U[l2,u2]. Let U1* be the uniform random variable obtained by shifting the ranges of U1 by -l1; that is, U1*=U1-l1~U[0,u1-l1]. Let U2* be the uniform random variable obtained by shifting the ranges of U2 by -l2; that is, U2*=U2-l2~U[0,u2-l2]. Assuming that u1-l1≤u2-l2 without loss of generality, the sum of U1* and U2* is U1+U2-(l1+l2). Then, U1+U2=U1*+U2*+(l1+l2). The cumulative distribution function of U1*+U2* is
(2)P(U1*+U2*≤t)=∫0t‍P(U1*=x)P(U2*≤t-x)dx=∫0t‍P(U2*≤t-x)u1-l1dx,
where t>0. Then,
(3)P(U1*+U2*≤t)={0ift≤0∫0tt-x(u1-l1)(u2-l2)dxif0<t≤u1-l1∫0u1-l1t-x(u1-l1)(u2-l2)dxifu1-l1<t≤u2-l2∫0t-(u2-l2)1u1-l1dx+∫t-(u2-l2)u1-l1t-x(u1-l1)(u2-l2)dxifu2-l2<t≤(u1+u2)-(l1+l2)∫0u1-l11u1-l1dxift>(u1+u2)-(l1+l2),P(U1*+U2*≤t)={0ift≤0t22(u1-l1)(u2-l2)if0<t≤u1-l12t-(u1-l1)2(u2-l2)ifu1-l1<t≤u2-l2(-t2+2((u1-l1)+(u2-l2))t11-(u1-l1)2-(u2-l2)2)×(2(u1-l1)(u2-l2))-1ifu2-l2<t≤(u1+u2)-(l1+l2)1ift>(u1+u2)-(l1+l2).By differentiating the function byt and then shifting the range of U1*+U2* by l1+l2 to the right, we obtain the following probability density function of U1+U2 (see Figure 6):
(4)ddtP(U1+U2≤t)={0ift≤l1+l2t-(l1+l2)(u1-l1)(u2-l2)ifl1+l2<t≤u1+l21u2-l2ifu1+l2<t≤u2+l1(u1+u2)-t(u1-l1)(u2-l2)ifu2+l1<t≤u1+u20ift>u1+u2.Figure 6
Sum of two uniform distributionsU[l1,u1] and U[l2,u2].Finally we consider the sum of normal distribution and uniform one. LetN be a random variable that is normally distributed; that is, N~N(μ,σ2). Let U be a random variable that is uniformly distributed; that is, U~U[l,u]. We assume that N and U are independent random variables. We cannot obtain the closed form of the probability density function of N+U, but fortunately the following cumulative distribution function is available:
(5)P(U+N≤t)=∫-∞∞‍P(N=x)P(U≤t-x)dx=∫-∞∞‍f(x)P(U≤t-x)dx=∫-∞t-u‍f(x)dx+∫t-ut-l‍f(x)t-x-lu-ldx+∫t-l∞‍0dx=P(z≤t-u-μσ)+t-l-μu-l×∫t-ut-l‍f(x)dx-σ2u-l∫t-ut-l‍x-μσ2f(x)dx=P(z≤t-u-μσ)·u-t+μu-l+P(z≤t-l-μσ)·t-l-μu-l+σ2u-l·(f(t-l)-f(t-u)),
where f(x)=(1/2π·σ)e-(x-μ)2/2σ2.


#### 4.3.3. Algorithm

When the current time ist and recent context data are given, we are to list all possible context elements and their possibilities of a specific user within the given time period [ts,te], where t<ts<te. To predict context, we use a TIPN that is already constructed. The possibility pv of each target node v is computed by the following three factors: (i) probability from each node u to the target node v based on the edge eu,v,k, (ii) the context predictability of each node u, and (iii) the degree of importance of the edge eu,v,k to the target node v.Now we define each factor and give the formula to computepv. (i) First, we calculate the probability P(u,v,k) from each node u to the target node v in relation to the edge eu,v,k. We assume that time-gap data for each edge and stay-time data for each node follow a normal or uniform distribution. To compute P(u,v,k) precisely, we need to make good use of the conditional probability and normal sum distribution. Let fu,v,k and gu,v,k be the probability density functions of edge eu,v,k and sum of edge eu,v,k and node v, respectively. Let αu be t − (the starting time of the latest context related to node u). Then P(u,v,k) becomes 1 − (probability to arrive at node v after time te − (probability to depart from node v before time ts). Hence,
(6)P(u,v,k)=1-∫te-t+αu∞‍fu,v,k∫αu∞‍fu,v,k-∫αuts-t+αu‍gu,v,k∫αu∞‍gu,v,k.
(ii) Context predictability means the easiness degree of prediction for target context type. It can be derived from a similarity measure between each node u and target context type T. We use the variance measure as follows:
(7)S(u,T)=|T|×Vart∈T(pu,t),wherepu,t=∑kwu,t,k∑t∈T,kwu,t,k.
It ranges from 0 to 1-1/k.(iii) The degree of importance of the edgeeu,v,k from node u to node v can be simply defined based on edge weights as follows:
(8)D(u,v,k)=wu,v,k∑t∈T,kwu,t,k.
Now we can define the possibility pv of each target node v as the following weighted sum:
(9)pv=∑u‍(S(u,T)×∑k‍D(u,v,k)×P(u,v,k)).


### 4.4. Managing Periodic Data

To manage periodic context data, we define basic periodic elements, for example, the set of “days of the week.” First, we construct a TIPN per each basic periodic element. Some group of basic elements may have similar patterns. If so, we should merge such TIPNs into one before applying the prediction algorithm given in Section4.3. Similarity s(GA,GB) between any two TIPNs, GA=(NA,EA) and GB=(NA,EB), can be obtained from the normalized summation of similarities s(eA,eB)s between distributions of edges (see the next subsections). That is,
(10)s(GA,GB)=∑i‍s(eiA,eiB)|EA∪EB|.If the similarity between two TIPNs is close to one, we merge the two TIPNs. This process is continued until there is no similar TIPNs. Now we present how to merge two TIPNs. We just merge nodes and edges in the TIPNs. Nodes and edges have the information of their statistical distribution. So we have to consider the sum of distributions. We assume that each node and each edge follow normal or uniform distributions. Since the sum of normal or uniform distributions is given in Section4.3.2, we have only to obtain its related statistics. Assuming that we have two statistics of the average, the standard deviation, and the frequency, that is, (μ,σ,c) and (μ′,σ′,c′), their sum becomes
(11)(c(σ2+μ2)+c′(σ′2+μ′2)c+c′-(cμ+c′μ′c+c′)2cμ+c′μ′c+c′,c(σ2+μ2)+c′(σ′2+μ′2)c+c′-(cμ+c′μ′c+c′)2,c+c′).


#### 4.4.1. Similarity between Normal Distributions

Let edgese1 and e2 follow normal distributions, N(μ1,σ1) and N(μ2,σ2), respectively. As shown in Figure 7, there are three cases to consider. The first case is that e1 and e2 follow the same distribution, that is, μ1=μ2 and σ1=σ2. In this case, it is obvious that s(e1,e2)=1. The second case is that the probability density functions of e1 and e2 have only one intersection. Then μ1≠μ2 and σ1=σ2. We assume that μ1<μ2 without loss of generality. Since the intersection point t is (μ1+μ2)/2,s(e1,e2)=2·P(z≤(μ1-μ2)/2σ). The third case is that the probability density functions of e1 and e2 have two intersections. In this case, σ1≠σ2. Assume that σ1<σ2 without loss of generality. Then s(e1,e2)=P(z≤(t1-μ1)/σ1)+P((t1-μ2)/σ2≤z≤(t2-μ2)/σ2)+P(z≥(t2-μ1)/σ1), where t1=(b-b2-ac)/a,t2=(b+b2-ac)/a,a=σ22-σ12,b=μ1σ22-μ2σ12, and c=μ12σ22-μ22σ12+2σ12σ22ln(σ1/σ2). We can get t1 and t2 by solving the equation (1/2π·σ1)e-(x-μ1)2/2σ12=(1/2π·σ2)e-(x-μ2)2/2σ22.Figure 7
Similarity between normal distributions.


#### 4.4.2. Similarity between Uniform Distributions

Let edgese1 and e2 follow uniform distributions, U[l1,u1] and U[l2,u2], respectively. We assume that l1≤l2 without loss of generality. As shown in Figure 8, there are two cases to consider. For both cases, s(e1,e2) becomes min(h1,h2)×(min(u1,u2)-max(l1,l2)), where h1=1/(u1-l1) and h2=1/(u2-l2).Figure 8
Similarity between uniform distributions.


#### 4.4.3. Similarity between Normal Distribution and Uniform One

Let edgese1 and e2 follow normal distribution N(μ,σ) and uniform distribution U[l,u], respectively. As shown in Figure 9, there are four cases to consider. We have one case for h≥1/2π·σ and three cases for h<1/2π·σ, where h=1/(u-l). In the case of h≥1/2π·σ,s(e1,e2) becomes P((l-μ)/σ≤z≤(u-μ)/σ). When h<1/2π·σ, the probability density function of e1 has two intersection points t1 and t2 with the line y=h. Here the points t2 and t1, which are roots of the equation h=(1/2π·σ)e-(x-μ)2/2σ2, become μ±σ-2ln(2π·σh), respectively. The latter three cases can be classified in the following. When t1≤l≤t2≤u,s(e1,e2)=h×(t2-l)+P((t2-μ)/σ≤z≤(u-μ)/σ). When l≤t1≤u≤t2,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(u-t1). When l≤t1≤t2≤u,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(t2-t1)+P((t2-μ)/σ≤z≤(u-μ)/σ).Figure 9
Similarity between normal distribution and uniform one.


## 4.1. Input Context Data

Input data are given in the following form. First, the target context typeT to predict is given. The maximum prediction time is also provided. Historic context data of a user are given in a series of 〈starting time, ending time, context type, context element〉, which are sorted by starting time in nondecreasing order. An example of historic context data can be shown as follows: 〈12:00, 13:00, location, restaurant〉, 〈13:10, 13:30, activity, listening to music〉, 〈13:20, 17:50, weather, rainy〉,   〈13:20, 18:00, location, resort〉, and so on.


## 4.2. Time-Inferred Pattern Network

Context history can be represented as a graph. For context prediction, we use a new data structure calledtime-inferred pattern network (TIPN). We can consider TIPN as a kind of directed weighted multi-graph. Each node means context or its combination. There are three types of nodes. Type-I nodes represent given context elements (e.g., restaurant, listening to music, rainy, resort). Each type-I node has the information of the average and the standard deviation of stay times, where stay time means the difference between starting time and ending time (i.e., stay time = ending time − starting time). Type-II nodes deal with ordered pairs of context elements belonging to different context types (e.g., (restaurant, listening to music), (restaurant, rainy), (listening to music, rainy), (listening to music, resort), (rainy, resort)). Each type-II node has the information of the average, the standard deviation, and the frequency of time gaps, where time gap means the difference between starting times of the two context elements (i.e., time gap = starting time of the second context element − that of the first). Each type-III node is for a series of context elements that are frequently appeared. Here the number of context elements of a type-III node is not limited. Each type-III node has the same information as type-II node, but time gap becomes the difference between starting times of the first context element and the last one. Each directed edge contains movement information from some (combined) context to a target context element. The information contains the average, the standard deviation, and the frequency of time gaps, where time gap is the difference between starting times of starting node and ending one. Each edge also has its weight. The edge weight presents the magnitude of possibility from context to context. The same patterns increase the weight.


### 4.2.1. Information of Nodes and Edges

In this subsection, we note some information of nodes and edges to be used in TIPN. First, we assume that there arek context types. We have three types of nodes. Information for each type of nodes are given in the following. For a type-I node u for each context type, we maintain the average of stay times (μu), the standard deviation of stay times (σu), and the frequency (cu). Similarly for a type-II node u for context pair of different context types, we have ordered context pair (γ1u,γ2u), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Considering a type-III node u coming from frequently appearing context sequence, we maintain common context sequence (γ1u,γ2u,…,γluu), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Finally, we consider multiple edges between context type S and target context type T. Edge set E=⋃u∈S,v∈TEu,v, where Eu,v={eu,v,1,eu,v,2,…,eu,v,k,…}. The following is information about the kth edge between node u and node v: the average of time gaps (μu,v,k), the standard deviation of time gaps (σu,v,k), the frequency (cu,v,k), and the weight (wu,v,k). Figure 5 shows multiple directed edges between nodes in TIPN.Figure 5
Multiple directed edges between nodes in TIPN.


### 4.2.2. Preprocessing

To make type-III nodes, we find frequent subpatterns from context log. For each context elementτ in target context type T, we extract subsequences ending with τ within time window. (Since the maximum prediction time is given, we do not use the context data beyond the maximum prediction time when we generate a TIPN.) Let nτ be the number of extracted subsequences and let γ1τ,γ2τ,…,γnττ be the extracted subsequences. For each pair of subsequences, we find its longest common subsequence (LCS) [22]. Then we have nτ(nτ+1)/2 LCSes. Using Levenshtein distance [23] and k-means clustering [24] upon them, we obtain the optimal k and k clusters. For each cluster, we find a central sequence so that its length is as short as possible. We add these central sequences to the type-III node set. If the length of a central sequence is just one, we discard the corresponding node.


### 4.2.3. Construction

We construct a TIPN after the preprocessing of creating type-III nodes. Starting with an empty TIPN composed of isolated nodes, we iteratively construct nodes and edges as reading input context data one by one. Algorithm1 shows the detailed pseudocode for constructing a TIPN.Algorithm 1:Pseudocode for constructing a TIPN after preprocessing.
Start with an empty TIPN composed of isolated nodes;
For  i←1to  inputdatasize-1 // read input context data
// constructing type-I nodes and their edges
for  k←1to  i′swindowsize-1
Update info of type-I nodeni;
if type-I node ni+k belongs to Tthen
Update edge(ni,ni+k);
// constructing type-II nodes and their edges
for  k←1 to i′swindowsize-2
if context type of ni+k≠ context type of nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-II noden′=(ni,ni+k);
Update edge(n′,ni+t);
// constructing type-III nodes and their edges
for  k←1to  i′swindowsize-2
if  ∃ a type-III node n′′ starting with the node nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-III noden′′;
Update edge(n′′,ni+t);When we update each edge, we test a normal distribution against accumulated time-gaps for the edge. In the case that they do not follow normal distributions, we divide the edge into two or more edges. So there may be multiple edges between each pair of nodes. The weightwu,v,k of each edge eu,v,k is determined in proportion to its frequency fu,v,k and the magnitudes of its corresponding time gaps.


### 4.2.4. Maintenance

It is clear that recent context data is more important than old ones. So we devise an aging strategy of edges to give more weights to recent data than old ones. We periodically apply it to only the edge weights per a unit time, for example, a day, a week, a month, or a year. That is, all edge weights are periodically updated as follows:wu,v,k=α×wu,v,k for all edge eu,v,k, where α<1. (We set α to be 0.9 in our experiments.) Also, we remove weakly connected edges. Given threshold t for removing edges, we remove edge eu,v,k when its weight wu,v,k is less than t.In the case that a TIPN has already been constructed and we have added context data, we do the same procedure of Algorithm1 starting with the previously constructed TIPN instead of an empty TIPN.


## 4.2.1. Information of Nodes and Edges

In this subsection, we note some information of nodes and edges to be used in TIPN. First, we assume that there arek context types. We have three types of nodes. Information for each type of nodes are given in the following. For a type-I node u for each context type, we maintain the average of stay times (μu), the standard deviation of stay times (σu), and the frequency (cu). Similarly for a type-II node u for context pair of different context types, we have ordered context pair (γ1u,γ2u), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Considering a type-III node u coming from frequently appearing context sequence, we maintain common context sequence (γ1u,γ2u,…,γluu), the average of time gaps (μu), the standard deviation of time gaps (σu), and the frequency (cu). Finally, we consider multiple edges between context type S and target context type T. Edge set E=⋃u∈S,v∈TEu,v, where Eu,v={eu,v,1,eu,v,2,…,eu,v,k,…}. The following is information about the kth edge between node u and node v: the average of time gaps (μu,v,k), the standard deviation of time gaps (σu,v,k), the frequency (cu,v,k), and the weight (wu,v,k). Figure 5 shows multiple directed edges between nodes in TIPN.Figure 5
Multiple directed edges between nodes in TIPN.


## 4.2.2. Preprocessing

To make type-III nodes, we find frequent subpatterns from context log. For each context elementτ in target context type T, we extract subsequences ending with τ within time window. (Since the maximum prediction time is given, we do not use the context data beyond the maximum prediction time when we generate a TIPN.) Let nτ be the number of extracted subsequences and let γ1τ,γ2τ,…,γnττ be the extracted subsequences. For each pair of subsequences, we find its longest common subsequence (LCS) [22]. Then we have nτ(nτ+1)/2 LCSes. Using Levenshtein distance [23] and k-means clustering [24] upon them, we obtain the optimal k and k clusters. For each cluster, we find a central sequence so that its length is as short as possible. We add these central sequences to the type-III node set. If the length of a central sequence is just one, we discard the corresponding node.


## 4.2.3. Construction

We construct a TIPN after the preprocessing of creating type-III nodes. Starting with an empty TIPN composed of isolated nodes, we iteratively construct nodes and edges as reading input context data one by one. Algorithm1 shows the detailed pseudocode for constructing a TIPN.Algorithm 1:Pseudocode for constructing a TIPN after preprocessing.
Start with an empty TIPN composed of isolated nodes;
For  i←1to  inputdatasize-1 // read input context data
// constructing type-I nodes and their edges
for  k←1to  i′swindowsize-1
Update info of type-I nodeni;
if type-I node ni+k belongs to Tthen
Update edge(ni,ni+k);
// constructing type-II nodes and their edges
for  k←1 to i′swindowsize-2
if context type of ni+k≠ context type of nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-II noden′=(ni,ni+k);
Update edge(n′,ni+t);
// constructing type-III nodes and their edges
for  k←1to  i′swindowsize-2
if  ∃ a type-III node n′′ starting with the node nithen
for  t←k+1to  i′swindowsize-1
if type-I node ni+t belongs to Tthen
Update info of type-III noden′′;
Update edge(n′′,ni+t);When we update each edge, we test a normal distribution against accumulated time-gaps for the edge. In the case that they do not follow normal distributions, we divide the edge into two or more edges. So there may be multiple edges between each pair of nodes. The weightwu,v,k of each edge eu,v,k is determined in proportion to its frequency fu,v,k and the magnitudes of its corresponding time gaps.


## 4.2.4. Maintenance

It is clear that recent context data is more important than old ones. So we devise an aging strategy of edges to give more weights to recent data than old ones. We periodically apply it to only the edge weights per a unit time, for example, a day, a week, a month, or a year. That is, all edge weights are periodically updated as follows:wu,v,k=α×wu,v,k for all edge eu,v,k, where α<1. (We set α to be 0.9 in our experiments.) Also, we remove weakly connected edges. Given threshold t for removing edges, we remove edge eu,v,k when its weight wu,v,k is less than t.In the case that a TIPN has already been constructed and we have added context data, we do the same procedure of Algorithm1 starting with the previously constructed TIPN instead of an empty TIPN.


## 4.3. Prediction Algorithm

### 4.3.1. Assumptions

In general, we assume that time-gap data for each edge and stay-time data for each node follow a normal distribution. If the collected data is sufficient, our assumption is reasonable bythe law of large numbers in probability theory [25]. However, in the case that the collected data is sparse, the assumption is not good. In such cases, we assume the data follow a uniform distribution. In more detail, we assume that the data follow U[μ-3σ,μ+3σ], where μ and σ mean the average and the standard deviations of sampled time data, respectively. The following fact supports our assumption.Fact 1.
The average and the variance ofU[μ-3σ,μ+3σ] are μ and σ2, respectively.Proof.
Let a random variableX follow U[μ-3σ,μ+3σ], and let f(t) be the probability density function of X. Then,
(1)f(t)={123σifμ-3σ≤t≤μ+3σ0otherwise,E(X)=∫-∞∞‍tf(t)dt=∫μ-3σμ+3σ‍t23σdt=(μ+3σ)2-(μ-3σ)243σ=μ,Var(X)=E(X2)-E(x)2=∫-∞∞‍t2f(t)dt-μ2=∫μ-3σμ+3σ‍t223σdt-μ2=(μ+3σ)3-(μ-3σ)363σ-μ2=σ2.


### 4.3.2. Sum of Edge Distribution and Node One

First we consider the sum of normal distributions. It is well known in probability theory, for example, [25]. If N1 and N2 are independent random variables that are normally distributed, then their sum is also normally distributed. That is, if N1~N(μ1,σ12),N2~N(μ2,σ22), and N1 and N2 are independent, then N1+N2~N(μ1+μ2,σ12+σ22). This means that the sum of two independent normally distributed random variables is normal, with its mean being the sum of the two means, and its variance being the sum of the two variances (i.e., the square of the standard deviation is the sum of the squares of the standard deviations).Next we consider the sum of uniform distributions. We assume thatU1 and U2 are independent random variables that are uniformly distributed, that is, U1~U[l1,u1] and U2~U[l2,u2]. Let U1* be the uniform random variable obtained by shifting the ranges of U1 by -l1; that is, U1*=U1-l1~U[0,u1-l1]. Let U2* be the uniform random variable obtained by shifting the ranges of U2 by -l2; that is, U2*=U2-l2~U[0,u2-l2]. Assuming that u1-l1≤u2-l2 without loss of generality, the sum of U1* and U2* is U1+U2-(l1+l2). Then, U1+U2=U1*+U2*+(l1+l2). The cumulative distribution function of U1*+U2* is
(2)P(U1*+U2*≤t)=∫0t‍P(U1*=x)P(U2*≤t-x)dx=∫0t‍P(U2*≤t-x)u1-l1dx,
where t>0. Then,
(3)P(U1*+U2*≤t)={0ift≤0∫0tt-x(u1-l1)(u2-l2)dxif0<t≤u1-l1∫0u1-l1t-x(u1-l1)(u2-l2)dxifu1-l1<t≤u2-l2∫0t-(u2-l2)1u1-l1dx+∫t-(u2-l2)u1-l1t-x(u1-l1)(u2-l2)dxifu2-l2<t≤(u1+u2)-(l1+l2)∫0u1-l11u1-l1dxift>(u1+u2)-(l1+l2),P(U1*+U2*≤t)={0ift≤0t22(u1-l1)(u2-l2)if0<t≤u1-l12t-(u1-l1)2(u2-l2)ifu1-l1<t≤u2-l2(-t2+2((u1-l1)+(u2-l2))t11-(u1-l1)2-(u2-l2)2)×(2(u1-l1)(u2-l2))-1ifu2-l2<t≤(u1+u2)-(l1+l2)1ift>(u1+u2)-(l1+l2).By differentiating the function byt and then shifting the range of U1*+U2* by l1+l2 to the right, we obtain the following probability density function of U1+U2 (see Figure 6):
(4)ddtP(U1+U2≤t)={0ift≤l1+l2t-(l1+l2)(u1-l1)(u2-l2)ifl1+l2<t≤u1+l21u2-l2ifu1+l2<t≤u2+l1(u1+u2)-t(u1-l1)(u2-l2)ifu2+l1<t≤u1+u20ift>u1+u2.Figure 6
Sum of two uniform distributionsU[l1,u1] and U[l2,u2].Finally we consider the sum of normal distribution and uniform one. LetN be a random variable that is normally distributed; that is, N~N(μ,σ2). Let U be a random variable that is uniformly distributed; that is, U~U[l,u]. We assume that N and U are independent random variables. We cannot obtain the closed form of the probability density function of N+U, but fortunately the following cumulative distribution function is available:
(5)P(U+N≤t)=∫-∞∞‍P(N=x)P(U≤t-x)dx=∫-∞∞‍f(x)P(U≤t-x)dx=∫-∞t-u‍f(x)dx+∫t-ut-l‍f(x)t-x-lu-ldx+∫t-l∞‍0dx=P(z≤t-u-μσ)+t-l-μu-l×∫t-ut-l‍f(x)dx-σ2u-l∫t-ut-l‍x-μσ2f(x)dx=P(z≤t-u-μσ)·u-t+μu-l+P(z≤t-l-μσ)·t-l-μu-l+σ2u-l·(f(t-l)-f(t-u)),
where f(x)=(1/2π·σ)e-(x-μ)2/2σ2.


### 4.3.3. Algorithm

When the current time ist and recent context data are given, we are to list all possible context elements and their possibilities of a specific user within the given time period [ts,te], where t<ts<te. To predict context, we use a TIPN that is already constructed. The possibility pv of each target node v is computed by the following three factors: (i) probability from each node u to the target node v based on the edge eu,v,k, (ii) the context predictability of each node u, and (iii) the degree of importance of the edge eu,v,k to the target node v.Now we define each factor and give the formula to computepv. (i) First, we calculate the probability P(u,v,k) from each node u to the target node v in relation to the edge eu,v,k. We assume that time-gap data for each edge and stay-time data for each node follow a normal or uniform distribution. To compute P(u,v,k) precisely, we need to make good use of the conditional probability and normal sum distribution. Let fu,v,k and gu,v,k be the probability density functions of edge eu,v,k and sum of edge eu,v,k and node v, respectively. Let αu be t − (the starting time of the latest context related to node u). Then P(u,v,k) becomes 1 − (probability to arrive at node v after time te − (probability to depart from node v before time ts). Hence,
(6)P(u,v,k)=1-∫te-t+αu∞‍fu,v,k∫αu∞‍fu,v,k-∫αuts-t+αu‍gu,v,k∫αu∞‍gu,v,k.
(ii) Context predictability means the easiness degree of prediction for target context type. It can be derived from a similarity measure between each node u and target context type T. We use the variance measure as follows:
(7)S(u,T)=|T|×Vart∈T(pu,t),wherepu,t=∑kwu,t,k∑t∈T,kwu,t,k.
It ranges from 0 to 1-1/k.(iii) The degree of importance of the edgeeu,v,k from node u to node v can be simply defined based on edge weights as follows:
(8)D(u,v,k)=wu,v,k∑t∈T,kwu,t,k.
Now we can define the possibility pv of each target node v as the following weighted sum:
(9)pv=∑u‍(S(u,T)×∑k‍D(u,v,k)×P(u,v,k)).


## 4.3.1. Assumptions

In general, we assume that time-gap data for each edge and stay-time data for each node follow a normal distribution. If the collected data is sufficient, our assumption is reasonable bythe law of large numbers in probability theory [25]. However, in the case that the collected data is sparse, the assumption is not good. In such cases, we assume the data follow a uniform distribution. In more detail, we assume that the data follow U[μ-3σ,μ+3σ], where μ and σ mean the average and the standard deviations of sampled time data, respectively. The following fact supports our assumption.Fact 1.
The average and the variance ofU[μ-3σ,μ+3σ] are μ and σ2, respectively.Proof.
Let a random variableX follow U[μ-3σ,μ+3σ], and let f(t) be the probability density function of X. Then,
(1)f(t)={123σifμ-3σ≤t≤μ+3σ0otherwise,E(X)=∫-∞∞‍tf(t)dt=∫μ-3σμ+3σ‍t23σdt=(μ+3σ)2-(μ-3σ)243σ=μ,Var(X)=E(X2)-E(x)2=∫-∞∞‍t2f(t)dt-μ2=∫μ-3σμ+3σ‍t223σdt-μ2=(μ+3σ)3-(μ-3σ)363σ-μ2=σ2.


## 4.3.2. Sum of Edge Distribution and Node One

First we consider the sum of normal distributions. It is well known in probability theory, for example, [25]. If N1 and N2 are independent random variables that are normally distributed, then their sum is also normally distributed. That is, if N1~N(μ1,σ12),N2~N(μ2,σ22), and N1 and N2 are independent, then N1+N2~N(μ1+μ2,σ12+σ22). This means that the sum of two independent normally distributed random variables is normal, with its mean being the sum of the two means, and its variance being the sum of the two variances (i.e., the square of the standard deviation is the sum of the squares of the standard deviations).Next we consider the sum of uniform distributions. We assume thatU1 and U2 are independent random variables that are uniformly distributed, that is, U1~U[l1,u1] and U2~U[l2,u2]. Let U1* be the uniform random variable obtained by shifting the ranges of U1 by -l1; that is, U1*=U1-l1~U[0,u1-l1]. Let U2* be the uniform random variable obtained by shifting the ranges of U2 by -l2; that is, U2*=U2-l2~U[0,u2-l2]. Assuming that u1-l1≤u2-l2 without loss of generality, the sum of U1* and U2* is U1+U2-(l1+l2). Then, U1+U2=U1*+U2*+(l1+l2). The cumulative distribution function of U1*+U2* is
(2)P(U1*+U2*≤t)=∫0t‍P(U1*=x)P(U2*≤t-x)dx=∫0t‍P(U2*≤t-x)u1-l1dx,
where t>0. Then,
(3)P(U1*+U2*≤t)={0ift≤0∫0tt-x(u1-l1)(u2-l2)dxif0<t≤u1-l1∫0u1-l1t-x(u1-l1)(u2-l2)dxifu1-l1<t≤u2-l2∫0t-(u2-l2)1u1-l1dx+∫t-(u2-l2)u1-l1t-x(u1-l1)(u2-l2)dxifu2-l2<t≤(u1+u2)-(l1+l2)∫0u1-l11u1-l1dxift>(u1+u2)-(l1+l2),P(U1*+U2*≤t)={0ift≤0t22(u1-l1)(u2-l2)if0<t≤u1-l12t-(u1-l1)2(u2-l2)ifu1-l1<t≤u2-l2(-t2+2((u1-l1)+(u2-l2))t11-(u1-l1)2-(u2-l2)2)×(2(u1-l1)(u2-l2))-1ifu2-l2<t≤(u1+u2)-(l1+l2)1ift>(u1+u2)-(l1+l2).By differentiating the function byt and then shifting the range of U1*+U2* by l1+l2 to the right, we obtain the following probability density function of U1+U2 (see Figure 6):
(4)ddtP(U1+U2≤t)={0ift≤l1+l2t-(l1+l2)(u1-l1)(u2-l2)ifl1+l2<t≤u1+l21u2-l2ifu1+l2<t≤u2+l1(u1+u2)-t(u1-l1)(u2-l2)ifu2+l1<t≤u1+u20ift>u1+u2.Figure 6
Sum of two uniform distributionsU[l1,u1] and U[l2,u2].Finally we consider the sum of normal distribution and uniform one. LetN be a random variable that is normally distributed; that is, N~N(μ,σ2). Let U be a random variable that is uniformly distributed; that is, U~U[l,u]. We assume that N and U are independent random variables. We cannot obtain the closed form of the probability density function of N+U, but fortunately the following cumulative distribution function is available:
(5)P(U+N≤t)=∫-∞∞‍P(N=x)P(U≤t-x)dx=∫-∞∞‍f(x)P(U≤t-x)dx=∫-∞t-u‍f(x)dx+∫t-ut-l‍f(x)t-x-lu-ldx+∫t-l∞‍0dx=P(z≤t-u-μσ)+t-l-μu-l×∫t-ut-l‍f(x)dx-σ2u-l∫t-ut-l‍x-μσ2f(x)dx=P(z≤t-u-μσ)·u-t+μu-l+P(z≤t-l-μσ)·t-l-μu-l+σ2u-l·(f(t-l)-f(t-u)),
where f(x)=(1/2π·σ)e-(x-μ)2/2σ2.


## 4.3.3. Algorithm

When the current time ist and recent context data are given, we are to list all possible context elements and their possibilities of a specific user within the given time period [ts,te], where t<ts<te. To predict context, we use a TIPN that is already constructed. The possibility pv of each target node v is computed by the following three factors: (i) probability from each node u to the target node v based on the edge eu,v,k, (ii) the context predictability of each node u, and (iii) the degree of importance of the edge eu,v,k to the target node v.Now we define each factor and give the formula to computepv. (i) First, we calculate the probability P(u,v,k) from each node u to the target node v in relation to the edge eu,v,k. We assume that time-gap data for each edge and stay-time data for each node follow a normal or uniform distribution. To compute P(u,v,k) precisely, we need to make good use of the conditional probability and normal sum distribution. Let fu,v,k and gu,v,k be the probability density functions of edge eu,v,k and sum of edge eu,v,k and node v, respectively. Let αu be t − (the starting time of the latest context related to node u). Then P(u,v,k) becomes 1 − (probability to arrive at node v after time te − (probability to depart from node v before time ts). Hence,
(6)P(u,v,k)=1-∫te-t+αu∞‍fu,v,k∫αu∞‍fu,v,k-∫αuts-t+αu‍gu,v,k∫αu∞‍gu,v,k.
(ii) Context predictability means the easiness degree of prediction for target context type. It can be derived from a similarity measure between each node u and target context type T. We use the variance measure as follows:
(7)S(u,T)=|T|×Vart∈T(pu,t),wherepu,t=∑kwu,t,k∑t∈T,kwu,t,k.
It ranges from 0 to 1-1/k.(iii) The degree of importance of the edgeeu,v,k from node u to node v can be simply defined based on edge weights as follows:
(8)D(u,v,k)=wu,v,k∑t∈T,kwu,t,k.
Now we can define the possibility pv of each target node v as the following weighted sum:
(9)pv=∑u‍(S(u,T)×∑k‍D(u,v,k)×P(u,v,k)).


## 4.4. Managing Periodic Data

To manage periodic context data, we define basic periodic elements, for example, the set of “days of the week.” First, we construct a TIPN per each basic periodic element. Some group of basic elements may have similar patterns. If so, we should merge such TIPNs into one before applying the prediction algorithm given in Section4.3. Similarity s(GA,GB) between any two TIPNs, GA=(NA,EA) and GB=(NA,EB), can be obtained from the normalized summation of similarities s(eA,eB)s between distributions of edges (see the next subsections). That is,
(10)s(GA,GB)=∑i‍s(eiA,eiB)|EA∪EB|.If the similarity between two TIPNs is close to one, we merge the two TIPNs. This process is continued until there is no similar TIPNs. Now we present how to merge two TIPNs. We just merge nodes and edges in the TIPNs. Nodes and edges have the information of their statistical distribution. So we have to consider the sum of distributions. We assume that each node and each edge follow normal or uniform distributions. Since the sum of normal or uniform distributions is given in Section4.3.2, we have only to obtain its related statistics. Assuming that we have two statistics of the average, the standard deviation, and the frequency, that is, (μ,σ,c) and (μ′,σ′,c′), their sum becomes
(11)(c(σ2+μ2)+c′(σ′2+μ′2)c+c′-(cμ+c′μ′c+c′)2cμ+c′μ′c+c′,c(σ2+μ2)+c′(σ′2+μ′2)c+c′-(cμ+c′μ′c+c′)2,c+c′).


### 4.4.1. Similarity between Normal Distributions

Let edgese1 and e2 follow normal distributions, N(μ1,σ1) and N(μ2,σ2), respectively. As shown in Figure 7, there are three cases to consider. The first case is that e1 and e2 follow the same distribution, that is, μ1=μ2 and σ1=σ2. In this case, it is obvious that s(e1,e2)=1. The second case is that the probability density functions of e1 and e2 have only one intersection. Then μ1≠μ2 and σ1=σ2. We assume that μ1<μ2 without loss of generality. Since the intersection point t is (μ1+μ2)/2,s(e1,e2)=2·P(z≤(μ1-μ2)/2σ). The third case is that the probability density functions of e1 and e2 have two intersections. In this case, σ1≠σ2. Assume that σ1<σ2 without loss of generality. Then s(e1,e2)=P(z≤(t1-μ1)/σ1)+P((t1-μ2)/σ2≤z≤(t2-μ2)/σ2)+P(z≥(t2-μ1)/σ1), where t1=(b-b2-ac)/a,t2=(b+b2-ac)/a,a=σ22-σ12,b=μ1σ22-μ2σ12, and c=μ12σ22-μ22σ12+2σ12σ22ln(σ1/σ2). We can get t1 and t2 by solving the equation (1/2π·σ1)e-(x-μ1)2/2σ12=(1/2π·σ2)e-(x-μ2)2/2σ22.Figure 7
Similarity between normal distributions.


### 4.4.2. Similarity between Uniform Distributions

Let edgese1 and e2 follow uniform distributions, U[l1,u1] and U[l2,u2], respectively. We assume that l1≤l2 without loss of generality. As shown in Figure 8, there are two cases to consider. For both cases, s(e1,e2) becomes min(h1,h2)×(min(u1,u2)-max(l1,l2)), where h1=1/(u1-l1) and h2=1/(u2-l2).Figure 8
Similarity between uniform distributions.


### 4.4.3. Similarity between Normal Distribution and Uniform One

Let edgese1 and e2 follow normal distribution N(μ,σ) and uniform distribution U[l,u], respectively. As shown in Figure 9, there are four cases to consider. We have one case for h≥1/2π·σ and three cases for h<1/2π·σ, where h=1/(u-l). In the case of h≥1/2π·σ,s(e1,e2) becomes P((l-μ)/σ≤z≤(u-μ)/σ). When h<1/2π·σ, the probability density function of e1 has two intersection points t1 and t2 with the line y=h. Here the points t2 and t1, which are roots of the equation h=(1/2π·σ)e-(x-μ)2/2σ2, become μ±σ-2ln(2π·σh), respectively. The latter three cases can be classified in the following. When t1≤l≤t2≤u,s(e1,e2)=h×(t2-l)+P((t2-μ)/σ≤z≤(u-μ)/σ). When l≤t1≤u≤t2,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(u-t1). When l≤t1≤t2≤u,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(t2-t1)+P((t2-μ)/σ≤z≤(u-μ)/σ).Figure 9
Similarity between normal distribution and uniform one.


## 4.4.1. Similarity between Normal Distributions

Let edgese1 and e2 follow normal distributions, N(μ1,σ1) and N(μ2,σ2), respectively. As shown in Figure 7, there are three cases to consider. The first case is that e1 and e2 follow the same distribution, that is, μ1=μ2 and σ1=σ2. In this case, it is obvious that s(e1,e2)=1. The second case is that the probability density functions of e1 and e2 have only one intersection. Then μ1≠μ2 and σ1=σ2. We assume that μ1<μ2 without loss of generality. Since the intersection point t is (μ1+μ2)/2,s(e1,e2)=2·P(z≤(μ1-μ2)/2σ). The third case is that the probability density functions of e1 and e2 have two intersections. In this case, σ1≠σ2. Assume that σ1<σ2 without loss of generality. Then s(e1,e2)=P(z≤(t1-μ1)/σ1)+P((t1-μ2)/σ2≤z≤(t2-μ2)/σ2)+P(z≥(t2-μ1)/σ1), where t1=(b-b2-ac)/a,t2=(b+b2-ac)/a,a=σ22-σ12,b=μ1σ22-μ2σ12, and c=μ12σ22-μ22σ12+2σ12σ22ln(σ1/σ2). We can get t1 and t2 by solving the equation (1/2π·σ1)e-(x-μ1)2/2σ12=(1/2π·σ2)e-(x-μ2)2/2σ22.Figure 7
Similarity between normal distributions.


## 4.4.2. Similarity between Uniform Distributions

Let edgese1 and e2 follow uniform distributions, U[l1,u1] and U[l2,u2], respectively. We assume that l1≤l2 without loss of generality. As shown in Figure 8, there are two cases to consider. For both cases, s(e1,e2) becomes min(h1,h2)×(min(u1,u2)-max(l1,l2)), where h1=1/(u1-l1) and h2=1/(u2-l2).Figure 8
Similarity between uniform distributions.


## 4.4.3. Similarity between Normal Distribution and Uniform One

Let edgese1 and e2 follow normal distribution N(μ,σ) and uniform distribution U[l,u], respectively. As shown in Figure 9, there are four cases to consider. We have one case for h≥1/2π·σ and three cases for h<1/2π·σ, where h=1/(u-l). In the case of h≥1/2π·σ,s(e1,e2) becomes P((l-μ)/σ≤z≤(u-μ)/σ). When h<1/2π·σ, the probability density function of e1 has two intersection points t1 and t2 with the line y=h. Here the points t2 and t1, which are roots of the equation h=(1/2π·σ)e-(x-μ)2/2σ2, become μ±σ-2ln(2π·σh), respectively. The latter three cases can be classified in the following. When t1≤l≤t2≤u,s(e1,e2)=h×(t2-l)+P((t2-μ)/σ≤z≤(u-μ)/σ). When l≤t1≤u≤t2,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(u-t1). When l≤t1≤t2≤u,s(e1,e2)=P((l-μ)/σ≤z≤(t1-μ)/σ)+h×(t2-t1)+P((t2-μ)/σ≤z≤(u-μ)/σ).Figure 9
Similarity between normal distribution and uniform one.


## 5. Test Results

We tested the proposed method using real context data of a mobile user. There were four types of context in our test: location, call, SMS, and activity. They had 5, 6, 2, 2 context elements, respectively. We set location to be target context to predict. The maximum prediction time is 6 hours. Time period to predict ists=30 to te=90 minutes after current time t. As training data to construct a TIPN, we used data for 160 hours (about 7 days). As test data to apply the prediction algorithm of Section 4.3, we used data for 6 hours before current time t. The resultant TIPN had 15 type-I nodes, 13 type-II nodes, and 4 type-III nodes. The average number of the context elements of obtained type-III nodes was 2.25. We made two tests. One is the context prediction on nonperiodic weekday data. Table 1 shows the results. To see the effect of node extension (of introducing type-II nodes and type-III ones), we used three TIPNs: TIPN with only type-I nodes, that with type-I nodes and type-II ones, and that with all types of nodes. All the methods successfully predicted context with high probability. We could also see that type-II nodes and type-III nodes help predict context more accurately.Table 1
Effect of node extension.
Targetcontext type(location)
Probability
Type-Inodes
Type-{I,II} nodes
Type-{I,II,III} nodes
L1
0.72
0.85
0.86
L2
0.21
0.11
0.11
L3
0.05
0.03
0.03
L4
0.02
0.01
0.01
L5
0.01
0.00
0.00
Total sum
1.00
1.00
1.00
Values in each column are normalized for their sum to be 1.
Location L1 is the answer of our test case.The other test is the context prediction on periodic data. As basic periodic elements, we used days of the week. The test user had two patterns: weekday pattern and weekend one. We made tests for both cases. Table2 shows the results. “All” means the prediction on the whole context data. “Periodic” means the prediction applying the method of Section 4.4. We could see that “Periodic” was better than “All.” In weekend test case, “All” even produced a wrong answer.Table 2
Effect of managing periodic data.
Targetcontext type(location)
Probability
Weekday case
Weekend case
All
Periodic
All
Periodic
L1
0.18
0.16
0.06
0.04
L2
0.80
0.84
0.49
0.00
L3
0.00
0.00
0.00
0.00
L4
0.01
0.00
0.45
0.96
L5
0.00
0.00
0.00
0.00
Total sum
1.00
1.00
1.00
1.00
Values in each column are normalized for their sum to be 1.
Location L2 is the answer of our weekday test case.
Location L4 is the answer of our weekend test case.


## 6. Conclusions

We proposed a novel probabilistic approach for context prediction of mobile users based on their historic context data. The proposed method predicts general context based on probability theory through a new graphical structure calledtime-inferred pattern network (TIPN).The accumulated context data of a user are transformed into the TIPN, in which each type-I node represents a single context, each type-II node is from a pair of contexts, each type-III node is made from a series of contexts the most generally, and each directed edge indicates a context transfer with the time weight inferred from corresponding time data. With the constructed TIPN, assuming nodes and edges follow normal or uniform distributions, we apply a scoring method derived from probability theory to predict the next context.Unlike traditional approaches using only location, we used other types of context such as call, SMS, and activity, together with location. We also considered context data with periodic property, providing a good solution for context prediction of mobile users with such patterns. Some empirical studies could show the goodness of the proposed prediction algorithms. Nodes corresponding to more complex context patterns could help predict the next contexts more accurately. So could the classification and clustering of daily context data patterns with periodic property. Although the proposed method showed some merits through a simple comparison from our experiments on small data set, we did not make comparison of the proposed method with other state-of-the-art ones. Such comparison on large-scale data will be a good direction for future work.



---

*Source: 106139-2013-08-22.xml*