REDUS: finding reducible subspaces in high dimensional data

ABSTRACT

Finding latent patterns in high dimensional data is an important research problem with numerous applications. The most well known approaches for high dimensional data analysis are feature selection and dimensionality reduction. Being widely used in many applications, these methods aim to capture global patterns and are typically performed in the full feature space. In many emerging applications, however, scientists are interested in the local latent patterns held by feature subspaces, which may be invisible via any global transformation.

In this paper, we investigate the problem of finding strong linear and nonlinear correlations hidden in feature subspaces of high dimensional data. We formalize this problem as identifying reducible subspaces in the full dimensional space. Intuitively, a reducible subspace is a feature subspace whose intrinsic dimensionality is smaller than the number of features. We present an effective algorithm, REDUS, for finding the reducible subspaces. Two key components of our algorithm are finding the overall reducible subspace, and uncovering the individual reducible subspaces from the overall reducible subspace. A broad experimental evaluation demonstrates the effectiveness of our algorithm.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, ACM SIGMOD Record, v.29 n.2, p.70-81, June 2000
• 2: A. Alizadeh and et al. Distinct types of diffuse large b-cell lymphoma identified by gene expression profiling. Nature, 403:503--11, 2000.
• 3: Daniel Barbará , Ping Chen, Using the fractal dimension to cluster datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.260-264, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347145]
• 4: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 5: Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998 [doi>10.1145/279339.279342]
• 6: Avrim L. Blum , Pat Langley, Selection of relevant features and examples in machine learning, Artificial Intelligence, v.97 n.1-2, p.245-271, Dec. 1997 [doi>10.1016/S0004-3702(97)00063-5]
• 7: Christian Böhm , Karin Kailing , Peer Kröger , Arthur Zimek, Computing Clusters of Correlation Connected objects, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007620]
• 8: I. Borg and P. Groenen. Modern multidimensional scaling. New York: Springer, 1997.
• 9: Francesco Camastra , Alessandro Vinciarelli, Estimating the Intrinsic Dimension of Data with a Fractal-Based Method, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.10, p.1404-1407, October 2002 [doi>10.1109/TPAMI.2002.1039212]
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: M. Eisen, P. Spellman, P. Brown, and D. Botstein. Cluster analysis and display of genome-wide expression patterns. Proc. Natl. Acad. Sci. USA, 95:14863--68, 1998.
• 12: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 13: K. Fukunaga. Intrinsic dimensionality extraction. Classification, Pattern recongnition and Reduction of Dimensionality, Volume 2 of Handbook of Statistics, pages 347--360, P. R. Krishnaiah and L. N. Kanal eds., Amsterdam, North Holland, 1982.
• 14: K. Fukunaga , D. R. Olsen, An Algorithm for Finding Intrinsic Dimensionality of Data, IEEE Transactions on Computers, v.20 n.2, p.176-183, February 1971 [doi>10.1109/T-C.1971.223208]
• 15: Aristides Gionis , Alexander Hinneburg , Spiros Papadimitriou , Panayiotis Tsaparas, Dimension induced clustering, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081880]
• 16: G. Golub and A. Loan. Matrix computations. Johns Hopkins University Press, Baltimore, Maryland, 1996.
• 17: V. Iyer and et. al. The transcriptional program in the response of human fibroblasts to serum. Science, 283:83--87, 1999.
• 18: I. Jolliffe. Principal component analysis. New York: Springer, 1986.
• 19: M. Kendall and J. D. Gibbons. Rank Correlation Methods. New York: Oxford University Press, 1990.
• 20: D. C. Lay. Linear Algebra and Its Applications. Addison Wesley, 2005.
• 21: E. Levina and P. J. Bickel. Maximum likelihood estimation of intrinsic dimension. Advances in Neural Information Processing Systems, 2005.
• 22: Huan Liu , Hiroshi Motoda, Feature Selection for Knowledge Discovery and Data Mining, Kluwer Academic Publishers, Norwell, MA, 1998
• 23: B.-U. Pagel, F. Korn, and C. Faloutsos. De ating the dimensionality curse using multiple fractal dimensions. ICDE, 2000.
• 24: S. Papadimitriou, H. Kitawaga, P. B. Gibbons, and C. Faloutsos. Loci: Fast outlier detection using the local correlation integral. ICDE, 2003.
• 25: S. N. Rasband. Chaotic Dynamics of Nonlinear Systems. Wiley-Interscience, 1990.
• 26: H. T. Reynolds. The analysis of cross-classifications. The Free Press, New York, 1977.
• 27: S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290 (5500):2323--2326, 2000.
• 28: M. Schroeder. Fractals, Chaos, Power Lawers: Minutes from an Infinite Paradise. W. H. Freeman, New York, 1991.
• 29: J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290 (5500):2319--2323, 2000.
• 30: Anthony K. H. Tung , Xin Xu , Beng Chin Ooi, CURLER: finding and visualizing nonlinear correlation clusters, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066211]
• 31: L. Yu and H. Liu. Feature selection for high-dimensional data: a fast correlation-based filter solution. ICML, 2003.
• 32: X. Zhang, F. Pan, and W. Wang. Care: Finding local linear correlations in high dimensional data. ICDE, 2008.
• 33: Z. Zhao and H. Liu. Searching for interacting features. IJCAI, 2007.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
high dimensional data, reducible subspace