Computable social patterns from sparse sensor data

ABSTRACT

We present a computational framework to automatically discover high-order temporal social patterns from very noisy and sparse location data. We introduce the concept of social footprint and present a method to construct a codebook, enabling the transformation of raw sensor data into a collection of social pages. Each page captures social activities of a user over regular time period, and represented as a sequence of encoded footprints. Computable patterns are then defined as repeated structures found in these sequences. To do so, we appeal to modeling tools in document analysis and propose a Latent Social theme Dirichlet Allocation (LSDA) model -- a version of the Ngram topic model in [6] with extra modeling of personal context. This model can be viewed as a Bayesian clustering method, jointly discovering temporal collocation of footprints and exploiting statistical strength across social pages, to automatically discovery high-order patterns. Alternatively, it can be viewed as a dimensionality reduction method where the reduced latent space can be interpreted as the hidden social 'theme' -- a more abstract perception of user's daily activities. Applying this framework to a real-world noisy dataset collected over 1.5 years, we show that many useful and interesting patterns can be computed. Interpretable social themes can also be deduced from the discovered patterns.

REFERENCES

• 1: B. Adams, D. Phung, and S. Venkatesh. Sensing and using social context. ACM Transaction on Multimedia Computing, Communications and Applications, 2008. to appear.
• 2: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 3: N. Eagle and A. Pentland. Eigenbehaviors: Identifying Structure in Routine, October 2005. Technical report, Human Dynamics Lab, Massachusetts Institute of Technology (MIT), 2005.
• 4: R. Hariharan and K. Toyama. Project lachesis: Parsing and modeling location histories. Lecture Notes in Computer Science, 3234:106--124, 2004.
• 5: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 6: Xuerui Wang, Andrew McCallum, and Xing Wei. Topical n-grams: Phrase and topic discovery, with an application to information retrieval. In Proceedings of the 7th IEEE International Conference on Data Mining, pages 697--702, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Experimentation, Human Factors, Measurement

Keywords:
latent Dirichlet allocation, social footprints, social pattern