A probabilistic approach to mining mobile phone data sequences

Abstract

We present a new approach to address the problem of large sequence mining from big data. The particular problem of interest is the effective mining of long sequences from large-scale location data to be practical for Reality Mining applications, which suffer from large amounts of noise and lack of ground truth. To address this complex data, we propose an unsupervised probabilistic topic model called the distant n-gram topic model (DNTM). The DNTM is based on latent Dirichlet allocation (LDA), which is extended to integrate sequential information. We define the generative process for the model, derive the inference procedure, and evaluate our model on both synthetic data and real mobile phone data. We consider two different mobile phone datasets containing natural human mobility patterns obtained by location sensing, the first considering GPS/wi-fi locations and the second considering cell tower connections. The DNTM discovers meaningful topics on the synthetic data as well as the two mobile phone datasets. Finally, the DNTM is compared to LDA by considering log-likelihood performance on unseen data, showing the predictive power of the model. The results show that the DNTM consistently outperforms LDA as the sequence length increases.

Appendix: Derivation of the distant n-gram topic model

From the graphical model in Fig. 1, we can determine the following relationship:

$$ \begin{aligned} p({\bf z, q}|\alpha,\beta) &= p({\bf z}, \user2{w}_{\bf 1}, \ldots, \user2{w}_{\user2{N}}|\alpha, \beta) \\ &= p(\user2{w}_{\bf 1}, \ldots, \user2{w}_{\user2{n}}|{\bf z}, \alpha, \beta)\cdot p({\bf z}|\alpha, \beta) \\ &= p( \user2{w}_{\bf 2}, \ldots,\user2{w}_{\user2{n}}|\user2{w}_{\bf 1}, {\bf z}, \alpha, \beta) \cdot p(\user2{w}_{\bf 1}|{\bf z}, \alpha, \beta) \cdot p({\bf z}|\alpha, \beta) \\ &= p({\bf z}|\alpha)p(\user2{w}_{\bf 1}|{\bf z},\beta_1)\prod_{j=2}^N p(\user2{w}_{\user2{j}}|{\bf z}, \user2{w}_{\bf 1},\beta_j)\\ &= \int\limits_{\varvec{\Uptheta}} p({\bf z}|\varvec{\Uptheta})p(\varvec{\Uptheta}|\alpha)d\varvec{\Uptheta} \cdot \int\limits_{\varvec{\Upphi}_{\bf 1}} p(\user2{w}_{\bf 1}|{\bf z},\varvec{\Upphi}_{\bf 1})p(\varvec{\Upphi}_{\bf 1}|\beta_1)d\varvec{\Upphi}_{\bf 1}\\ & \quad \cdot \prod_{j=2}^n \int\limits_{\varvec{\Upphi}_{\bf j}} p(\user2{w}_{\user2{j}}|\user2{w}_{\bf 1}, {\bf z},\varvec{\Upphi}_{\bf j})p(\varvec{\Upphi}_{\bf j}|\beta_j)d\varvec{\Upphi}_{\bf j}\\ &= \prod_{m=1}^M \left(\frac{1}{B(\alpha)} \int \prod_{k=1}^T \varvec{\theta}_{m,k}^{n_m^{k}+\alpha-1} d\varvec{\theta}\right) \cdot \prod_{k=1}^T \left( \frac{1}{B(\beta_1)} \int \prod_{t=1}^V \varvec{\phi}_{1_{k,t}}^{n_k^t + \beta_1 - 1} d\varvec{\phi}_1\right) \\ & \quad\cdot \prod_{j=2}^n \prod_{k=1}^T \frac{1}{B(\beta_j)} \left( \int \prod_{t_1=1}^V \prod_{t_2=1}^V \varvec{\phi}_{j_{k, t_1, t_2}}^{n_{k_i^{\prime}}^{(t_1, t_2)_j} + \beta_j - 1} d\phi_j \right) \\ &= \prod_{m=1}^M \frac{B(n_m + \alpha)}{B(\alpha)}\cdot \prod_{k=1}^T \left(\frac{B(n_k + \beta_1)}{B(\beta_1)}\cdot \prod_{j=2}^n\frac{B(n_{k_j^{\prime}} + \beta_j)}{B(\beta_j)} \right) \end{aligned} $$

The joint probability of observations and latent topics can be obtained by marginalizing over the hidden parameters $\varvec{\Uptheta}$ and $\varvec{\Upphi}$. These relations are then used for inference and parameter estimation where $p({\bf z}|\alpha), p(\user2{w}_{\bf 1}|{\bf z}, \beta_1)$, and $p(\user2{w}_{\user2{j}}|\user2{w}_{\bf 1}, \beta_j)$ are derived in [8] resulting in the following.

$$ p({\bf z}|\alpha) = \prod_{m=1}^M \frac{B(n_m + \alpha)}{B(\alpha)} $$

(11)

$$ p(\user2{w}_{\bf 1}|{\bf z},\beta_1) = \prod_{k=1}^T \frac{B(n_k + \beta_1)}{B(\beta_1)} $$

(12)

$$ p(\user2{w}_{\user2{j}}|\user2{w}_{\bf 1}, {\bf z},\beta_j) = \prod_{k=1}^T \frac{B(n_{k_j^{\prime}} + \beta_j)}{B(\beta_j)}, \quad 1<j\leqq n $$

(13)

We then derive the model parameters based on the MCMC approach of Gibbs sampling [14].

$$ p(z_i = k|{\bf z}_{-i},{\bf q},\alpha,\beta) = \frac{p({\bf z},{\bf q}|\alpha,\beta)}{p({\bf z}_{-i},{\bf q}|\alpha ,\beta)} $$

(14)

using the knowledge z _−i , or ${\bf w}_{x_{-i}}$ indicate that token i is excluded from the topic or label w _x

$$ \propto \frac{B(n_m + \alpha)}{B(n_{m_{-i}} + \alpha)} \cdot \frac{B(n_k + \beta_1)}{B(n_{k_{-i}} + \beta_1)} \cdot \prod_{j=2}^n \frac{B(n_{k_j^{'}} + \beta_j)}{B(n_{k_{j,-i}^{'}} + \beta_j)} $$

(15)

Note the proportionality stems from the terms $\user2{w}_{1_i}$ and $\user2{w}_{j_i}$

$$ \begin{aligned} &\propto (n_{m,-i}^k + \alpha) \cdot \frac{n_{k,-i}^{w_1} + \beta_1}{\sum_{w_1=1}^V n_{k,-i}^t + \beta_1}\\ & \quad \cdot \prod_{j=2}^n \frac{n_{k,-i}^{(w_1, w_2)_j} + \beta_j}{\sum_{w_1=1}^V \sum_{w_2=1}^V n_{k,-i}^{(w_1, w_2)_j} + \beta_j}\nonumber \end{aligned} $$

(16)

where $n_{x}^{(y)} = n_{x,-i}^{(y)} + 1$ if x = x _i and y = y _i and $n_{x}^{(y)} = n_{x,-i}^{(y)}$ in other cases.

Where $n_k = \{n_k^{w_1}\}_{w_{1}=1}^V$ and $n_{k_j^{'}} = \{n_{k^{'}}^{(w_1,w_2)_j}\}_{w_1=1, w_2=1}^{w_1=V, w_2=V}$.

We use the properties $B(x) = \frac{\prod_{k=1}^{dim x} \Upgamma(x_k)}{\Upgamma(\sum_{k=1}^{dim x} x_k)}$, and $\Upgamma(y) = (y-1)!$

The model parameters can then be estimated as follows:

$$ \varvec{\theta}_m^k = \frac{n_m^k + \alpha}{\sum_{k=1}^T(n_m^k + \alpha)} $$

(17)

$$ \varvec{\phi}_{1, k}^t = \frac{n_k^t + \beta_1}{\sum_{w_1=1}^V(n_k^{w_1} + \beta_1)} $$

(18)

$$ \varvec{\phi}_{j, k}^{(w_1, w_2)_j} = \frac{n_k^{(w_1, w_2)_j} + \beta_j}{\sum_{w_1=1}^V \sum_{w_2=1}^V (n_k^{(w_1, w_2)_j} + \beta_j)}. $$

(19)