Towards systematic design of distance functions for data mining applications

ABSTRACT

Distance function computation is a key subtask in many data mining algorithms and applications. The most effective form of the distance function can only be expressed in the context of a particular data domain. It is also often a challenging and non-trivial task to find the most effective form of the distance function. For example, in the text domain, distance function design has been considered such an important and complex issue that it has been the focus of intensive research over three decades. The final design of distance functions in this domain has been reached only by detailed empirical testing and consensus over the quality of results provided by the different variations. With the increasing ability to collect data in an automated way, the number of new kinds of data continues to increase rapidly. This makes it increasingly difficult to undertake such efforts for each and every new data type. The most important aspect of distance function design is that since a human is the end-user for any application, the design must satisfy the user requirements with regard to effectiveness. This creates the need for a systematic framework to design distance functions which are sensitive to the particular characteristics of the data domain. In this paper, we discuss such a framework. The goal is to create distance functions in an automated waywhile minimizing the work required from the user. We will show that this framework creates distance functions which are significantly more effective than popularly used functions such as the Euclidean metric.

REFERENCES

• 1: Charu C. Aggarwal, Re-designing distance functions and distance-based applications for high dimensional data, ACM SIGMOD Record, v.30 n.1, p.13-18, March 2001 [doi>10.1145/373626.373638]
• 2: C. C. Aggarwal. Towards Meaningful High Dimensional Nearest Neighbor Search by Human-Computer Interaction. ICDE Conference, 2001.
• 3: C. C. Aggarwal, P. S. Yu. The IGrid Index: Reversing the Dimensionality Curse for Similarity Indexing in High Dimensional Space. KDD Conference, 2001.
• 4: Charu C. Aggarwal , Alexander Hinneburg , Daniel A. Keim, On the Surprising Behavior of Distance Metrics in High Dimensional Spaces, Proceedings of the 8th International Conference on Database Theory, p.420-434, January 04-06, 2001
• 5: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 6: D. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd Edition, 1999.
• 7: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 8: Gautam Das , Heikki Mannila, Context-Based Similarity Measures for Categorical Databases, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.201-210, September 13-16, 2000
• 9: J. Foote. A Similarity Measure for Automatic Audio Classification. AAI 1997 Spring Symposium on Intelligent Integration and Use of Text, Image, Video, and Audio Corpora, 1997.
• 10: Dimitrios Gunopulos , Gautam Das, Time series similarity measures and time series indexing (abstract only), Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.624, May 21-24, 2001, Santa Barbara, California, United States
• 11: Alexander Hinneburg , Charu C. Aggarwal , Daniel A. Keim, What Is the Nearest Neighbor in High Dimensional Spaces?, Proceedings of the 26th International Conference on Very Large Data Bases, p.506-515, September 10-14, 2000
• 12: S. Deerwester et al. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41(6): 391--407, 1990.
• 13: Norio Katayama , Shin'ichi Satoh, Distinctiveness-Sensitive Nearest Neighbor Search for Efficient Similarity Retrieval of Multimedia Information, Proceedings of the 17th International Conference on Data Engineering, p.493-502, April 02-06, 2001
• 14: Eamonn J. Keogh , Michael J. Pazzani, Scaling up Dynamic Time Warping to Massive Dataset, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.1-11, September 15-18, 1999
• 15: P. Moen. Attribute, Event Sequence, and Event Type Similarity Notions for Data Mining. ining. PhD Thesis, Report A-2000-1, Department of Computer Science, University of Helsinki, February 2000. http://www.cs.helsinki.fi/TR/A-2000/1/.
• 16: Alexander Hinneburg , Daniel A. Keim , Markus Wawryniuk, HD-Eye: Visual Mining of High-Dimensional Data, IEEE Computer Graphics and Applications, v.19 n.5, p.22-31, September 1999 [doi>10.1109/38.788795]
• 17: Mike James, Classification algorithms, Wiley-Interscience, New York, NY, 1985
• 18: M. M. Richter. On the notion of similarity in case-based reasoning. Mathematical and Statistical Methods in Artificial Intelligence (ed. G. della Riccia et al). Springer Verlag, 1995, p. 171--184.
• 19: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 20: Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
• 21: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 22: Leejay Wu , Christos Faloutsos , Katia P. Sycara , Terry R. Payne, FALCON: Feedback Adaptive Loop for Content-Based Retrieval, Proceedings of the 26th International Conference on Very Large Data Bases, p.297-306, September 10-14, 2000

INDEX TERMS

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

Keywords:
data mining, distance functions, user interaction