Incremental tensor analysis: Theory and applications

ABSTRACT

How do we find patterns in author-keyword associations, evolving over time? Or in data cubes (tensors), with product-branchcustomer sales information? And more generally, how to summarize high-order data cubes (tensors)? How to incrementally update these patterns over time? Matrix decompositions, like principal component analysis (PCA) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks, and many more settings. However, they have only two orders (i.e., matrices, like author and keyword in the previous example).

We propose to envision such higher-order data as tensors, and tap the vast literature on the topic. However, these methods do not necessarily scale up, let alone operate on semi-infinite streams. Thus, we introduce a general framework, incremental tensor analysis (ITA), which efficiently computes a compact summary for high-order and high-dimensional data, and also reveals the hidden correlations. Three variants of ITA are presented: (1) dynamic tensor analysis (DTA); (2) streaming tensor analysis (STA); and (3) window-based tensor analysis (WTA). In paricular, we explore several fundamental design trade-offs such as space efficiency, computational cost, approximation accuracy, time dependency, and model complexity.

We implement all our methods and apply them in several real settings, such as network anomaly detection, multiway latent semantic indexing on citation networks, and correlation study on sensor measurements. Our empirical studies show that the proposed methods are fast and accurate and that they find interesting patterns and outliers on the real datasets.

REFERENCES

• 1: Charu C. Aggarwal , Jiawei Han , Jianyong Wang , Philip S. Yu, A framework for clustering evolving data streams, Proceedings of the 29th international conference on Very large data bases, p.81-92, September 09-12, 2003, Berlin, Germany
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 4: Ding, C. and Ye, J. 2005. Two-Dimensional singular value decomposition (2dsvd) for 2d maps and images. In SDM.
• 5: Pedro Domingos , Geoff Hulten, Mining high-speed data streams, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.71-80, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347107]
• 6: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 7: Drineas, P. and Mahoney, M. W. 2005. A randomized algorithm for a tensor-based generalization of the SVD. Tech. Rep. YALEU/DCS/TR-1327, Yale University.
• 8: Enron Dataset. 2004. U.C. Berkeley Enron email analysis. http://bailando.sims.berkeley.edu/enron_email.html.
• 9: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 10: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507517]
• 11: Sudipto Guha , D. Gunopulos , Nick Koudas, Correlating synchronous and asynchronous data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956814]
• 12: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 13: Simon Haykin, Adaptive filter theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 14: He, X., Cai, D., and Niyogi, P. 2005. Tensor subspace analysis. In Proceeding of the Conference on Advance, in Neural Information Processing Systems (NIPS).
• 15: Piotr Indyk , Nick Koudas , S. Muthukrishnan, Identifying Representative Trends in Massive Time Series Data Sets Using Sketches, Proceedings of the 26th International Conference on Very Large Data Bases, p.363-372, September 10-14, 2000
• 16: Jolliffe, I. 2002. Principal Component Analysis. Springer.
• 17: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 18: George Karypis , Vipin Kumar, Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs, SIAM Review, v.41 n.2, p.278-300, June 1999 [doi>10.1137/S0036144598334138]
• 19: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 20: Kolda, T. G. 2006. Multilinear operators for higher-order decompositions. Tech. Rep. SAND2006-2081, Sandia National Laboratory/April.
• 21: Kolda, T. G. and Bader, B. W. 2008 Tensor decompositions and applications. SIAM Rev. (in revision). http://csmr.ca.sandia.gov/~tgkolda/pubs/bibtgkfiles/SAND2007-6702.pdf.
• 22: Tamara G. Kolda , Brett W. Bader , Joseph P. Kenny, Higher-Order Web Link Analysis Using Multilinear Algebra, Proceedings of the Fifth IEEE International Conference on Data Mining, p.242-249, November 27-30, 2005 [doi>10.1109/ICDM.2005.77]
• 23: Flip Korn , Alexandros Labrinidis , Yannis Kotidis , Christos Faloutsos, Quantifiable data mining using ratio rules, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.254-266, February 2000 [doi>10.1007/s007780050007]
• 24: Kroonenberg, P. and Leeuw, J. D. 1980. Principal component analysis of three-mode data by means of alternating least square algorithms. Psychometrika 45.
• 25: Kroonenberg, P. M. 1983. Three-Mode Principal Component Analysis. Theory and Applications. DWO Press.
• 26: Lathauwer, L. D., Moor, B. D., and Vandewalle, J. 2006. On the best rank-1 and rank-(r1,r2,. . .,rn) approximation of higher-order tensors. SIAM. Matrix Anal. Appl. 21.
• 27: Michael W. Mahoney , Mauro Maggioni , Petros Drineas, Tensor-CUR decompositions for tensor-based data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150440]
• 28: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 29: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, hands-off stream mining, Proceedings of the 29th international conference on Very large data bases, p.560-571, September 09-12, 2003, Berlin, Germany
• 30: Spiros Papadimitriou , Jimeng Sun , Christos Faloutsos, Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 31: Yasushi Sakurai , Spiros Papadimitriou , Christos Faloutsos, BRAID: stream mining through group lag correlations, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066226]
• 32: Parinya Sanguansat , Widhyakorn Asdornwised , Somchai Jitapunkul , Sanparith Marukatat, Two-Dimensional Linear Discriminant Analysis of Principle Component Vectors for Face Recognition, IEICE - Transactions on Information and Systems, v.E89-D n.7, p.2164-2170, July 2006 [doi>10.1093/ietisy/e89-d.7.2164]
• 33: Shashua, A. and Levin, A. 2001. Linear image coding for regression and classification using the tensor-rank principle. In Proceedings of the IEEE Conference on Computer vision and Patteroo Recongnistion CVPR (1). IEEE Computer Society, 42--49.
• 34: Smilde, A., Bro, R., and Geladi, P. 2004. Multi-Way Analysis: Applications in the Chemical Sciences. Wiley, West Sussex, UK.
• 35: Jimeng Sun , Spiros Papadimitriou , Philip S. Yu, Window-based Tensor Analysis on High-dimensional and Multi-aspect Streams, Proceedings of the Sixth International Conference on Data Mining, p.1076-1080, December 18-22, 2006 [doi>10.1109/ICDM.2006.169]
• 36: Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150445]
• 37: Dacheng Tao , Xuelong Li , Xindong Wu , Stephen J. Maybank, General Tensor Discriminant Analysis and Gabor Features for Gait Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.10, p.1700-1715, October 2007 [doi>10.1109/TPAMI.2007.1096]
• 38: Tucker, L. R. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika 31, 279--311.
• 39: Universität Trier. 2008. http://www.informatik.uni-trier.de/~ley/db/.
• 40: Charles F. van Loan, The ubiquitous Kronecker product, Journal of Computational and Applied Mathematics, v.123 n.1-2, p.85-100, Nov. 2000 [doi>10.1016/S0377-0427(00)00393-9]
• 41: M. A. O. Vasilescu , Demetri Terzopoulos, Multilinear Analysis of Image Ensembles: TensorFaces, Proceedings of the 7th European Conference on Computer Vision-Part I, p.447-460, May 28-31, 2002
• 42: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 43: Dong Xu , Shuicheng Yan , Lei Zhang , Hong-Jiang Zhang , Zhengkai Liu , Heung-Yeung Shum, Concurrent Subspaces Analysis, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.203-208, June 20-26, 2005 [doi>10.1109/CVPR.2005.107]
• 44: Jieping Ye, Generalized Low Rank Approximations of Matrices, Machine Learning, v.61 n.1-3, p.167-191, November 2005 [doi>10.1007/s10994-005-3561-6]
• 45: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000
• 46: Lizhuang Zhao , Mohammed J. Zaki, TRICLUSTER: an effective algorithm for mining coherent clusters in 3D microarray data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066236]
• 47: Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
        G.1.10 Applications

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Performance, Theory

Keywords:
Tensor, multilinear algebra, stream mining