Random projections and Hotelling’s  T2 statistics for change detection in high-dimensional data streams

Ewa Skubalska-Rafajłowicz

doi:10.2478/amcs-2013-0034

.blurhash-client-img { display: none !important; }

Random projections and Hotelling’s T2 statistics for change detection in high-dimensional data streams

International Journal of Applied Mathematics and Computer Science

Volume 23 (2013): Issue 2 (June 2013)

By: Ewa Skubalska-Rafajłowicz

Open Access

|Jun 2013

Abstract

The method of change (or anomaly) detection in high-dimensional discrete-time processes using a multivariate Hotelling chart is presented. We use normal random projections as a method of dimensionality reduction. We indicate diagnostic properties of the Hotelling control chart applied to data projected onto a random subspace of Rn. We examine the random projection method using artificial noisy image sequences as examples.

References

Achlioptas, D. (2001 ). Database friendly random projections, Proceedings of the 20th ACM SIGMOD-SIGACT-SIGARTSymposium on Principles of Database Systems, Santa Barbara,CA, USA, pp. 274-281.10.1145/375551.375608
Search in Google Scholar
Ailon, N. and Chazelle, B. (2006). Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the 38th Annual ACM Symposium on Theoryof Computing, Seattle, WA, USA, pp. 557-563.
Search in Google Scholar
Arriaga, R. and Vempala, S.(1999). An algorithmic theory of learning: Robust concepts and random projection, Proceedings of the 40th Annual IEEE Symposium on theFoundations of Computer Science, New York, NY, USA, pp. 616-623.
Search in Google Scholar
Biau, G. and Devroye, L. and Lugosi, G. (2008). On the performance of clustering in Hilbert spaces IEEE Transactionson Information Theory 54(2): 781-790.10.1109/TIT.2007.913516
Search in Google Scholar
Bodnar, O. and Schmid, W. (2005). Multivariate control charts based on a projection approach Allgemeines StatistischesArchiv 89(1): 75-93.10.1007/s101820500193
Search in Google Scholar
Chandola, V., Banerjee, A. and Kumar, V. (2009). Anomaly detection: A survey, ACM Computing Surveys41(3): 15:1-15:58.10.1145/1541880.1541882
Search in Google Scholar
Cramer, H. and Wold, H.(1936). Some theorems on distribution functions, Journal of the London Mathematical Society11(2): 290-295.10.1112/jlms/s1-11.4.290
Search in Google Scholar
Cuesta-Albertos, J.A., del Barrio, E., Fraiman, R. and Matran, C. (2007). The random projection method in goodness of fit for functional data, Computational Statistics and DataAnalysis 51(10): 4814-4831.10.1016/j.csda.2006.09.007
Search in Google Scholar
Cuturi, M., Vert, J-P. and dAspremont, A. (2009). White functionals for anomaly detection in dynamical systems, in Y. Bengio, D. Schuurmans, J. Lafferty, C.K.I. Williams and A. Culotta (Eds.), Advances in Neural InformationProcessing Systems, Vol. 22, MIT Press, Vancouver, pp. 432-440.
Search in Google Scholar
Dasgupta, S. and Gupta, A. (2003). An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structuresand Algorithms 22(1): 60-65.10.1002/rsa.10073
Search in Google Scholar
Donoho D.L. (2000 ). High-dimensional data analysis: The curses and blessings of dimensionality, Technical report, Department of Statistics, Stanford University, Stanford, CA.
Search in Google Scholar
Frankl, P. and Maehara, H. (1987). The Johnson-Lindenstrauss lemma and the sphericity of some graphs, Journal of CombinatorialTheory A 44(3): 355-362.10.1016/0095-8956(88)90043-3
Search in Google Scholar
Forbes, C., Evans, M. and Hastings, N. and Peacock, B. (2011). Statistical Distributions, 4th Edn., John Wiley and Sons, Inc., Hoboken, NJ.
Search in Google Scholar
Hyv¨arinen, A., Karhunen, J. and Oja, E. (2001). IndependentComponent Analysis, Wiley, New York, NY.10.1002/0471221317
Search in Google Scholar
Hotelling, H. (1931). The generalization of Student’s ratio TheAnnals of Mathematical Statistics 2(3): 360-378.10.1214/aoms/1177732979
Search in Google Scholar
Indyk, P. and Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality, Proceedings of the 30th Annual ACM Symposium on theTheory of Computing, Dallas, TX, USA, pp. 604-613.
Search in Google Scholar
Indyk, P. and Naor, A.(2007). Nearest neighbor preserving embeddings, ACM Transactions on Algorithms 3(3): 31:1-31:12.10.1145/1273340.1273347
Search in Google Scholar
Jolliffe, I.T. (1986). Principal Component Analysis, Springer-Verlag, New York, NY.10.1007/978-1-4757-1904-8
Search in Google Scholar
Johnson, W.B. and Lindenstrauss, J.(1984). Extensions of Lipschitz mapping into Hilbert space, ContemporaryMathematics 26: 189-206.10.1090/conm/026/737400
Search in Google Scholar
Korbicz, J., Ko´scielny, J.M., Kowalczuk, Z. and Cholewa, W. (Eds.) (2004). Fault Diagnosis. Models, ArtificialIntelligence, Applications. Springer Verlag, Berlin/Heidelberg/New York, NY.10.1007/978-3-642-18615-8
Search in Google Scholar
Lee, J.A. and Verleysen, M. (2007). Nonlinear DimensionalityReduction, Springer, New York, NY.10.1007/978-0-387-39351-3
Search in Google Scholar
Li, P., Hastie, T.J. and Church, K.W. (2006a). Nonlinear estimators and tail bounds for dimension reduction in L1 using Cauchy random projections, Technical report, Department of Statistics, Stanford University, Stanford, CA.
Search in Google Scholar
Li, P., Hastie, T.J. and Church, K.W. (2006b). Sub-Gaussian random projections, Technical report, Department of Statistics, Stanford University, Stanford, CA.
Search in Google Scholar
Mason, R.L., Tracy, N.D. and Young, J.C., (1992). Multivariate control charts for individual observations, Journal ofQuality Technology 24(2): 88-95.10.1080/00224065.1992.12015232
Search in Google Scholar
Mason, R.L. and Young, J.C. (2002). Multivariate StatisticalProcess Control with Industrial Application, SIAM, Philadelphia, PA.10.1137/1.9780898718461
Search in Google Scholar
Mathai, A.M. and Provost, S.B. (1992). Quadratic Formsin Random Variables: Theory and Applications, Marcel Dekker, New York, NY.
Search in Google Scholar
Matouˆsek, J.(2008). On variants of the Johnson-Lindenstrauss lemma, Random Structures and Algorithms 33(2): 142-156.10.1002/rsa.20218
Search in Google Scholar
Milman, V.(1971). A new proof of the theorem of A. Dvoretzky on sections of convex bodies, Functional Analysis and ItsApplications 5(4): 28-37, (English translation).
Search in Google Scholar
Montgomery, D.C. (1996 ). Introduction to Statistical QualityControl, 3rd Edn., John Wiley and Sons, New York, NY.
Search in Google Scholar
Qin, S.J.(2003). Statistical process monitoring: Basics and beyond Journal of Chemometrics 17(8-9): 480-502.10.1002/cem.800
Search in Google Scholar
Rao, C.R. (1973). Linear Statistical Inference andIts Applications, John Wiley and Sons, New York, NY/London/Sydney/Toronto.
Search in Google Scholar
Runger, G.C. (1996). Projections and the U-squared multivariate control chart, Journal of Quality Technology28(3): 313-319.10.1080/00224065.1996.11979681
Search in Google Scholar
Runger, G., Barton, R., Del Castillo, E. and Woodall, W.H. (2007). Optimal monitoring of multivariate data for fault patterns, Journal of Quality Technology 39(2): 159-172.10.1080/00224065.2007.11917683
Search in Google Scholar
Skubalska-Rafajłowicz, E. (2006). RBF neural network for probability density function estimation and detecting changes in multivariate processes, in L. Rutkowski, R. Tadeusiewicz, L.A. Zadeh and J. ˙Zurada (Eds.), Artificial Intelligence and Soft Computing, Lecture Notes in Computer Science, Vol. 4029, Springer-Verlag, Berlin/Heidelberg, pp. 133-141.10.1007/11785231_15
Search in Google Scholar
Skubalska-Rafajłowicz, E. (2008). Random projection RBF nets for multidimensional density estimation, InternationalJournal of Applied Mathematics and Computer Science18(4): 455-464, DOI: 10.2478/v10006-008-0040-9. 10.2478/v10006-008-0040-9
Search in Google Scholar
Skubalska-Rafajłowicz, E. (2009). Neural networks with sigmoidal activation functions dimension reduction using normal random projection, Nonlinear Analysis 71(12): e1255-e1263.10.1016/j.na.2009.01.124
Search in Google Scholar
Skubalska-Rafajłowicz, E. (2011). Fast and efficient method of change detection in statistically monitored high-dimensional data streams, Proceedings of the 10thInternational Science and Technology Conference on Diagnosticsof Processes and Systems, Zamo´s´c, Poland, pp. 256-260.
Search in Google Scholar
Srivastava,M.S. (2009). A review of multivariate theory for high dimensional data with fewer observations, in A. SenGupta (Ed.), Advances in Multivariate Statistical Methods, Vol. 9, World Scientific, Singapore, pp. 25-52.10.1142/9789812838247_0002
Search in Google Scholar
Sulliva, J.H. and Woodall, W.H. (2000). Change-point detection of mean vector or covariance matrix shifts using multivariate individual observations, IIE Transactions32(6): 537-549.10.1080/07408170008963929
Search in Google Scholar
Tsung F. and Wang K. (2010). Adaptive charting techniques: Literature review and extensions, in H.-J. Lenz, P.-T. Wilrich and W. Schmid (Eds.), Frontiers in StatisticalQuality Control, Vol. 9, Springer-Verlag, Berlin/Heidelberg, pp. 19-35.10.1007/978-3-7908-2380-6_2
Search in Google Scholar
Vempala, S. (2004). The Random Projection Method, American Mathematical Society, Providence, RI.10.1090/dimacs/065/01
Search in Google Scholar
Wang, K. and Jiang, W. (2009). High-dimensional process monitoring and fault isolation via variable selection, Journalof Quality Technology 41(3): 247-258.10.1080/00224065.2009.11917780
Search in Google Scholar
Wang, J. (2012). Geometric Structure of High-DimensionalData and Dimensionality Reduction, Higher Education Press, Beijing/Springer-Verlag, Berlin/Heidelberg.10.1007/978-3-642-27497-8_3
Search in Google Scholar
Wold, H. (1966). Estimation of principal components and related models by iterative least squares in P. Krishnaiaah (Ed.), Multivariate Analysis, Academic Press, New York, NY, pp. 391-420.
Search in Google Scholar
Zorriassatine, F., Tannock, J.D.T. and O‘Brien, C. (2003). Using novelty detection to identify abnormalities caused by mean shifts in bivariate processes, Computers and Industrial Engineering44(3): 385-408.10.1016/S0360-8352(02)00215-2
Search in Google Scholar