Clustered subset selection and its applications on it service metrics

ABSTRACT

Motivated by the enormous amounts of data collected in a large IT service provider organization, this paper presents a method for quickly and automatically summarizing and extracting meaningful insights from the data. Termed Clustered Subset Selection (CSS), our method enables program-guided data explorations of high-dimensional data matrices. CSS combines clustering and subset selection into a coherent and intuitive method for data analysis. In addition to a general framework, we introduce a family of CSS algorithms with different clustering components such as k-means and Close-to-Rank-One (CRO) clustering, and Subset Selection components such as best rank-one approximation and Rank-Revealing QR (RRQR) decomposition.

From an empirical perspective, we illustrate that CSS is achieving significant improvements over existing Subset Selection methods in terms of approximation errors. Compared to existing Subset Selection techniques, CSS is also able to provide additional insight about clusters and cluster representatives. Finally, we present a case-study of program-guided data explorations using CSS on a large amount of IT service delivery data collection.

REFERENCES

• 1: http://finance.yahoo.com/q/hp?s=%5egspc.
• 2: M. Berry, S. Pulatova, and G. Stewart. Computing sparse reduced-rank approximations to sparse matrices. Technical Report UMIACS TR-2004-32 CMSC TR-4589, University of Maryland, College Park, MD, 2004.
• 3: C. H. Bischof , G. Quintana-Ortí, Algorithm 782: codes for rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.254-257, June 1998 [doi>10.1145/290200.287638]
• 4: Christian H. Bischof , G. Quintana-Ortí, Computing rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.226-253, June 1998 [doi>10.1145/290200.287637]
• 5: Christos Boutsidis , Michael W. Mahoney , Petros Drineas, Unsupervised feature selection for principal components analysis, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401903]
• 6: 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
• 7: T. F. Chan. Rank revealing QR factorizations. Linear Algebra and Its Applications, 88/89:67--82, 1987.
• 8: Tony F. Chan , Per Christian Hansen, Some applications of the rank revealing QR factorization, SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.727-741, May 1992 [doi>10.1137/0913043]
• 9: T. F. Chan and P. C. Hansen. Low-rank revealing QR factorizations. Numerical Linear Algebra with Applications, 1:33--44, 1994.
• 10: Shivkumar Chandrasekaran , Ilse C. F. Ipsen, On Rank-Revealing Factorisations, SIAM Journal on Matrix Analysis and Applications, v.15 n.2, p.592-622, April 1994 [doi>10.1137/S0895479891223781]
• 11: S. J. Cho and M. A. Hermsmeier. Genetic algorithm guided selection: Variable selection and subset selection. Journal of Chemical Information and Computer Sciences, 42(4):927--936, 2002.
• 12: Christophe Couvreur , Yoram Bresler, On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem, SIAM Journal on Matrix Analysis and Applications, v.21 n.3, p.797-808, Feb.-March 2000 [doi>10.1137/S0895479898332928]
• 13: Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109681]
• 14: A. Deshpande and S. Vempala. Adaptive sampling and fast low-rank matrix approximation. In RANDOM - APPROX, 2006.
• 15: Inderjit S. Dhillon , Dharmendra S. Modha, Concept decompositions for large sparse text data using clustering, Machine Learning, v.42 n.1/2, p.143-175, Jan. 2001 [doi>10.1023/A:1007612920971]
• 16: P. Drineas. Randomized Algorithms for Matrix Operations. PhD thesis, Yale University, 2002.
• 17: Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 18: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix, SIAM Journal on Computing, v.36 n.1, p.158-183, 2006 [doi>10.1137/S0097539704442696]
• 19: 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]
• 20: L. V. Foster. Rank and null space calculations using matrix decomposition without column interchanges. Linear Algebra Appl., 74:47--71, 1986.
• 21: L. V. Foster and X. Liu. Comparison of rank revealing algorithms applied to matrices with well defined numerical ranks. submitted, 2006.
• 22: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 23: E. Gallopoulos and D. Zeimpekis. CLSI: A flexible approximation scheme from clustered term-document matrices. In SDM, 2005.
• 24: G. Golub and C. V. Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
• 25: G. H. Golub. Numerical methods for solving linear least squares problems. Numer. Math., 7:206--216, 1965.
• 26: Gene H. Golub , Virginia C. Klema , Gilbert W. Stewart, Rank degeneracy and least squares problems, Stanford University, Stanford, CA, 1976
• 27: Ming Gu , Stanley C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM Journal on Scientific Computing, v.17 n.4, p.848-869, July 1996 [doi>10.1137/0917055]
• 28: Y. P. Hong and C. T. Pan. Rank-revealing QR factorizations and the singular value decomposition. Mathematics of Computation, 58:213--232, 1992.
• 29: 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]
• 30: 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
• 31: 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
• 32: 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]
• 33: Y.-D. Kim and S. Choi. A method of initialization for nonnegative matrix factorization. In Acoustics, Speech and Signal Processing (ICASSP), 2007.
• 34: 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
• 35: C. T. Pan. On the existence and computation of rank-revealing LU factorizations. Linear Algebra Appl., 316:199--222, 2000.
• 36: C. T. Pan and P. T. P. Tang. Bounds on singular values revealed by QR factorizations. BIT Numerical Mathematics, 39:740--756, 1999.
• 37: 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]
• 38: 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
• 39: Kirk Pruhs , Gerhard J. Woeginger, Approximation schemes for a class of subset selection problems, Theoretical Computer Science, v.382 n.2, p.151-156, August, 2007 [doi>10.1016/j.tcs.2007.03.006]
• 40: G. Stewart. Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix. Numerische Mathematik, 83:313--323, 1999.
• 41: G. Stewart and J. Sun. Matrix Perturbation Theory. Academic Press, New York, 1990.
• 42: Dimitrios Zeimpekis , Efstratios Gallopoulos, Linear and Non-Linear Dimensional Reduction via Class Representatives for Text Classification, Proceedings of the Sixth International Conference on Data Mining, p.1172-1177, December 18-22, 2006 [doi>10.1109/ICDM.2006.98]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

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

General Terms:
Algorithms, Management

Keywords:
clustering, low rank matrix approximation, service delivery, service provider, subset selection