Tri-plots: scalable tools for multidimensional data mining

ABSTRACT

We focus on the problem of finding patterns across two large, multidimensional datasets. For example, given feature vectors of healthy and of non-healthy patients, we want to answer the following questions: Are the two clouds of points separable? What is the smallest/largest pair-wise distance across the two datasets? Which of the two clouds does a new point (feature vector) come from?We propose a new tool, the tri-plot, and its generalization, the pq-plot, which help us answer the above questions. We provide a set of rules on how to interpret a tri-plot, and we apply these rules on synthetic and real datasets. We also show how to use our tool for classification, when traditional methods (nearest neighbor, classification trees) may fail.

REFERENCES

• 1: R. Agrawal, J. Gherke, D. Gunopoulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications, 1998.
• 2: 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]
• 3: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 4: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 5: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 6: S. Chaudhuri. Data mining and database systems: Where is the intersection? Data Engineering Bulletin, 21(1):4-8, 1998.
• 7: Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155]
• 8: M. Ester, A. Frommelt, H.-P. Kriegel, and J. Sander. Algorithms for characterization and trend detection in spatial databases. In Proc. of the 4th International Conference on Knowledge Discovery and Data Mining (KDD-98), pages 44-50, 1998.
• 9: Martin Ester , Hans-Peter Kriegel , Jörg Sander, Spatial Data Mining: A Database Approach, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.47-66, July 15-18, 1997
• 10: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 11: U. M. Fayyad. Mining databases - towards algorithms for knowledge discovery. Data Engineering Bulletin, 21(1):39-48, 1998.
• 12: U. M. Fayyad, C. Reina, and P. S. Bradley. Initialization of iterative refinement clustering algorithms. In Proc. of the 4th International Conference on Knowledge Discovery and Data Mining (KDD-98), pages 194-198, 1998.
• 13: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining Very Large Databases, Computer, v.32 n.8, p.38-45, August 1999 [doi>10.1109/2.781633]
• 14: Jiawei Han , Laks V. S. Lakshmanan , Raymond T. Ng, Constraint-Based, Multidimensional Data Mining, Computer, v.32 n.8, p.46-50, August 1999 [doi>10.1109/2.781634]
• 15: C. Traina Jr., A. Traina, L. Wu, and C. Faloutsos. Fast feature selection using the fractal dimension. In XV Brazilian Symposium on Databases (SBBD), 2000.
• 16: Constraint-Based Rule Mining in Large, Dense Databases, Proceedings of the 15th International Conference on Data Engineering, p.188, March 23-26, 1999
• 17: D. A. Keim and H.-P. Kriegel. Possibilities and limits in visualizing large amounts of multidimensional data. In Perceptual Issues in Visualization. Springer, 1994.
• 18: Edwin M. Knorr , Raymond T. Ng, Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.884-897, December 1996 [doi>10.1109/69.553156]
• 19: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 20: Bureau of Census. Tiger/line preeensus files: 1990 technical documentation. Bureau of the Census. Washington, DC, 1989.
• 21: Deflating the Dimensionality Curse Using Multiple Fractal Dimensions, Proceedings of the 16th International Conference on Data Engineering, p.589, February 28-March 03, 2000
• 22: M. Schroeder. Fractals, Chaos, Power Laws. W.H. Freeman and Company, New York, 1991.
• 23: H. G. Schuster. Deterministic Chaos. VCH Publisher, Weinheim, Basel, Cambridge, New York, 1988.
• 24: Gholamhosein Sheikholeslami , Surojit Chatterjee , Aidong Zhang, WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases, Proceedings of the 24rd International Conference on Very Large Data Bases, p.428-439, August 24-27, 1998
• 25: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada
• 26: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Health

General Terms:
Algorithms, Design, Performance