Generation of synthetic data sets for evaluating the accuracy of knowledge discovery systems

ABSTRACT

Information Discovery and Analysis Systems (IDAS) are designed to correlate multiple sources of data and use data mining techniques to identify potential significant events. Application domains for IDAS are numerous and include the emerging area of homeland security.Developing test cases for an IDAS requires background data sets into which hypothetical future scenarios can be overlaid. The IDAS can then be measured in terms of false positive and false negative error rates. Obtaining the test data sets can be an obstacle due to both privacy issues and also the time and cost associated with collecting a diverse set of data sources.In this paper, we give an overview of the design and architecture of an IDAS Data Set Generator (IDSG) that enables a fast and comprehensive test of an IDAS. The IDSG generates data using statistical and rule-based algorithms and also semantic graphs that represent interdependencies between attributes. A credit card transaction application is used to illustrate the approach.

REFERENCES

• 1: Abowd, J.M. and Lane, J.I. Synthetic Data and Confidentiality Protection. U.S. Census Bureau, LEHD Program Technical Paper No. TP-2003-10, (2003).
• 2: Philip K. Chan , Wei Fan , Andreas L. Prodromidis , Salvatore J. Stolfo, Distributed Data Mining in Credit Card Fraud Detection, IEEE Intelligent Systems, v.14 n.6, p.67-74, November 1999 [doi>10.1109/5254.809570]
• 3: Department of Defense, Office of the Inspector General. Information Technology Management: Terrorism Information Awareness Program. Report No. D-2004-033. (2004).
• 4: General Accounting Office, Data Mining: Federal Efforts Cover a Wide Range of Uses. GAO-04-548. (2004).
• 5: Kusiak, A., Kernstine, K.H., Kern, J.A., McLaughlin, K.A., and Tseng, T.L. Data Mining: Medical and Engineering Case Studies. Proceedings of the Industrial Engineering Research 2000 Conference, Cleveland, Ohio, May 21-23, (2000), 1--7.
• 6: Leskovec, J. Grobelnik, M., and Millic-Frayling, N. Learning Sub-structures of Document Semantic Graphs for Document Summarization. LinkKDD 2004, August 2004, Seattle WA, USA. (2004).
• 7: Thomas Ormerod , Nicola Morley , Linden Ball , Charles Langley , Clive Spenser, Using ethnography to design a mass detection tool (MDT) for the early discovery of insurance fraud, CHI '03 extended abstracts on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/765891.765910]
• 8: Prince, E., and Nicholson, W.L. A Test of a Robust/Resistant Refinement Procedure on Synthetic Data. Acta Cryst., A39, (1983), 407--410.
• 9: Rogers, M. Graham, J., and Tonge, R.P. Using Statistical Image Models for Objective Evaluation of Spot Detection in Two-Dimensional Gels. Proteomics, June, 3(6) (2003), 879--886.
• 10: Tamás Varga , Horst Bunke, Generation of Synthetic Training Data for an HMM-based Handwriting Recognition System, Proceedings of the Seventh International Conference on Document Analysis and Recognition, p.618, August 03-06, 2003
• 11: Dominic Widdows , Beate Dorow, A graph model for unsupervised lexical acquisition, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072342]
• 12: Yun, W.T., Stefanova, L., Mitra, A.K., and Krishnamurti, T.N.. Multi-Model Synthetic Superensemble Prediction System. Acta Cryst., A39, (1983), 407--410.
• 13: Zhu, X., Aref, W.G., Fan, J., Catlin, A.C., and Elmagarmid, A.K. Medical Video Mining for Efficient Database Indexing, Management, and Access. IEEE Int. Conf. On Data Engineering (ICDE '03), Bangalore, India, March 5-March 8, (2003), 1--12.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods; Validation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Semantic networks

General Terms:
Algorithms, Design, Verification

Keywords:
data generation, data mining, information discovery