FEMA: flexible evolutionary multi-faceted analysis for dynamic behavioral pattern discovery

ABSTRACT

Behavioral pattern discovery is increasingly being studied to understand human behavior and the discovered patterns can be used in many real world applications such as web search, recommender system and advertisement targeting. Traditional methods usually consider the behaviors as simple user and item connections, or represent them with a static model. In real world, however, human behaviors are actually complex and dynamic: they include correlations between user and multiple types of objects and also continuously evolve along time. These characteristics cause severe data sparsity and computational complexity problem, which pose great challenge to human behavioral analysis and prediction. In this paper, we propose a Flexible Evolutionary Multi-faceted Analysis (FEMA) framework for both behavior prediction and pattern mining. FEMA utilizes a flexible and dynamic factorization scheme for analyzing human behavioral data sequences, which can incorporate various knowledge embedded in different object domains to alleviate the sparsity problem. We give approximation algorithms for efficiency, where the bound of approximation loss is theoretically proved. We extensively evaluate the proposed method in two real datasets. For the prediction of human behaviors, the proposed FEMA significantly outperforms other state-of-the-art baseline methods by 17.4%. Moreover, FEMA is able to discover quite a number of interesting multi-faceted temporal patterns on human behaviors with good interpretability. More importantly, it can reduce the run time from hours to minutes, which is significant for industry to serve real-time applications.

References

1. E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mørup. Scalable tensor factorizations for incomplete data. Chemometrics and Intelligent Laboratory Systems, 106(1):41--56, 2011.
2. W. Chen, W. Hsu, and M. L. Lee. Making recommendations from multiple domains. In KDD'13, pages 892--900.
3. W. Chen, W. Hsu, and M. L. Lee. Modeling user's receptiveness over time for recommendation. In SIGIR'13, pages 373--382.
4. A. Cichocki and R. Zdunek. Regularized alternating least squares algorithms for non-negative matrix/tensor factorization. In Advances in Neural Networks--ISNN 2007, pages 793--802.
5. P. Cui, S. Jin, L. Yu, F. Wang, W. Zhu, and S. Yang. Cascading outbreak prediction in networks: a data-driven approach. In KDD'13, pages 901--909.
6. P. Cui, F. Wang, S. Liu, M. Ou, S. Yang, and L. Sun. Who should share what? item-level social influence prediction for users and posts ranking. In SIGIR'11, pages 185--194.
7. J. Davis and M. Goadrich. The relationship between precision-recall and roc curves. In ICML'06, pages 233--240.
8. L. De Lathauwer, B. De Moor, and J. Vandewalle. A multilinear singular value decomposition. SIAM journal on Matrix Analysis and Applications, 21(4):1253--1278, 2000.
9. D. M. Dunlavy, T. G. Kolda, and E. Acar. Temporal link prediction using matrix and tensor factorizations. TKDD, 5(2):10, 2011.
10. L. Hu, J. Cao, G. Xu, L. Cao, Z. Gu, and C. Zhu. Personalized recommendation via cross-domain triadic factorization. In WWW'13, pages 595--606.
11. M. Jiang, P. Cui, R. Liu, Q. Yang, F. Wang, W. Zhu, and S. Yang. Social contextual recommendation. In CIKM'12, pages 45--54.
12. M. Jiang, P. Cui, F. Wang, Q. Yang, W. Zhu, and S. Yang. Social recommendation across multiple relational domains. In CIKM'12, pages 1422--1431.
13. U. Kang, E. Papalexakis, A. Harpale, and C. Faloutsos. Gigatensor: scaling tensor analysis up by 100 times-algorithms and discoveries. In KDD'12, pages 316--324.
14. G. Karypis. Evaluation of item-based top-n recommendation algorithms. In CIKM'01, pages 247--254.
15. T. G. Kolda. Orthogonal tensor decompositions. SIAM Journal on Matrix Analysis and Applications, 23(1):243--255, 2001.
16. T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM review, 51(3):455--500, 2009.
17. T. G. Kolda and J. Sun. Scalable tensor decompositions for multi-aspect data mining. In ICDM'08, pages 363--372.
18. Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30--37, 2009.
19. L. Liu, J. Tang, J. Han, M. Jiang, and S. Yang. Mining topic-level influence in heterogeneous networks. In CIKM'10, pages 199--208.
20. K. Narang, S. Nagar, S. Mehta, L. Subramaniam, and K. Dey. Discovery and analysis of evolving topical social discussions on unstructured microblogs. In Advances in Information Retrieval, pages 545--556. 2013.
21. H. Rachlin. The value of temporal patterns in behavior. Current Directions in Psychological Science, 1995.
22. K. Radinsky, K. M. Svore, S. T. Dumais, M. Shokouhi, J. Teevan, A. Bocharov, and E. Horvitz. Behavioral dynamics on the web: Learning, modeling, and prediction. TOIS, 31(3):16, 2013.
23. S. Rendle and L. Schmidt-Thieme. Pairwise interaction tensor factorization for personalized tag recommendation. In WSDM'10, pages 81--90.
24. S. B. Roy, M. De Cock, V. Mandava, S. Savanna, B. Dalessandro, C. Perlich, W. Cukierski, and B. Hamner. The microsoft academic search dataset and kdd cup 2013. In Proceedings of the KDD Cup 2013 Workshop.
25. G. W. Stewart and J.-g. Sun. Matrix perturbation theory.
26. J. Sun, D. Tao, S. Papadimitriou, P. S. Yu, and C. Faloutsos. Incremental tensor analysis: Theory and applications. TKDD, 2(3):11, 2008.
27. J.-T. Sun, H.-J. Zeng, H. Liu, Y. Lu, and Z. Chen. Cubesvd: a novel approach to personalized web search. In WWW'05, pages 382--390.
28. Y. Sun, J. Tang, J. Han, C. Chen, and M. Gupta. Co-evolution of multi-typed objects in dynamic star networks. TKDE, 2013.
29. P. Symeonidis, A. Nanopoulos, and Y. Manolopoulos. Tag recommendations based on tensor dimensionality reduction. In RecSys'08, pages 43--50.
30. F. Wang, J. Sun, J. Hu, and S. Ebadollahi. imet: interactive metric learning in healthcare applications. In SDM'11, pages 944--955.
31. F. Wang, H. Tong, and C.-Y. Lin. Towards evolutionary nonnegative matrix factorization. In AAAI'11, pages 501--506.
32. X. Wang, C. Zhai, and D. Roth. Understanding evolution of research themes: a probabilistic generative model for citations. In KDD'13, pages 1115--1123.
33. L. Xiang, Q. Yuan, S. Zhao, L. Chen, X. Zhang, Q. Yang, and J. Sun. Temporal recommendation on graphs via long-and short-term preference fusion. In KDD'10, pages 723--732.
34. Q. Yuan, G. Cong, Z. Ma, A. Sun, and N. M. Thalmann. Who, where, when and what: Discover spatio-temporal topics for twitter users. In KDD'13, pages 605--613.
35. X. Zheng, H. Ding, H. Mamitsuka, and S. Zhu. Collaborative matrix factorization with multiple similarities for predicting drug-target interactions. In KDD'13, pages 1025--1033.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Cluster analysis