Beyond streams and graphs: dynamic tensor analysis

ABSTRACT

How do we find patterns in author-keyword associations, evolving over time? Or in Data Cubes, with product-branch-customer sales information? 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. However, they have only two orders, like author and keyword, in the above 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 the dynamic tensor analysis (DTA) method, and its variants. DTA provides a compact summary for high-order and high-dimensional data, and it also reveals the hidden correlations. Algorithmically, we designed DTA very carefully so that it is (a) scalable, (b) space efficient (it does not need to store the past) and (c) fully automatic with no need for user defined parameters. Moreover, we propose STA, a streaming tensor analysis method, which provides a fast, streaming approximation to DTA.We implemented all our methods, and applied them in two real settings, namely, anomaly detection and multi-way latent semantic indexing. We used two real, large datasets, one on network flow data (100GB over 1 month) and one from DBLP (200MB over 25 years). Our experiments show that our methods are fast, accurate and that they find interesting patterns and outliers on the real datasets.

REFERENCES

• 1: http://www.informatik.uni-trier.de/ ley/db/.
• 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, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: J. D. Carroll and J. Chang. Analysis of individual differences in multi dimensional scaling via an n-way generalization of 'eckart-young' decomposition. Psychometrika, 35(3), 1970.
• 5: L. de Lathauwer. Signal Processing Based on Multilinear Algebra. PhD thesis, Katholieke University of Leuven, Belgium, 1997.
• 6: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, 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.956764]
• 7: Chris Ding and Jieping Ye. Two-dimensional singular value decomposition (2dsvd) for 2d maps and images. In SDM, 2005.
• 8: Petros Drineas and Michael W. Mahoney. A randomized algorithm for a tensor-based generalization of the svd. technical report.
• 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: R. A. Harshman. Foundations of the parafac procedure:model and conditions for an explanatory multi-mode factor analysis. UCLA working papers in phonetics, 16, 1970.
• 11: Simon Haykin, Adaptive filter theory (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 12: Xiaofei He, Deng Cai, and Partha Niyogi. Tensor subspace analysis. In NIPS, 2005.
• 13: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 14: 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
• 15: I. T. Jolliffe. Principal Component Analysis. Springer, 2002.
• 16: 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
• 17: A. Kapteyn, H. Neudecker, and T. Wansbeek. An approach to n-mode component analysis. Psychometrika, 51(2), 1986.
• 18: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 19: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 20: 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]
• 21: 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]
• 22: P. Kroonenberg and J. D. Leeuw. Principal component analysis of three-mode data by means of alternating least square algorithms. Psychometrika, 45, 1980.
• 23: S. Muthukrishnan. Data streams: algorithms and applications, volume 1. Foundations and Trends. in Theoretical Computer Science, 2005.
• 24: 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]
• 25: 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
• 26: Amnon Shashua and Anat Levin. Linear image coding for regression and classification using the tensor-rank principle. In CVPR, number 1, 2001.
• 27: L. R. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3), 1966.
• 28: 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
• 29: N. Viereck, M. Dyrby, and S. B. Engelsen. Monitoring Thermal Processes by NMR Technology. Elsevier Academic Press, 2006.
• 30: 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]
• 31: 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]
• 32: 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]

INDEX TERMS

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

General Terms:
Algorithms