Learning missing values from summary constraints

ABSTRACT

Real-world data sets often contain errors and inconsistency. Even though this is a very important problem it has received relatively little attention in the research community. In this paper we examine the problem of learning missing values when some summary information is available. We use linear algebra and constraint programming techniques to learn the missing values using apriori-known summary information and that derived from the raw data. We reconstruct the missing values by different methods in three scenarios: ideal-constrained, under-constrained, and over-constrained. Furthermore, for a range query involving missing values, we also give the lower bound and upper bound for the values using constraint programming techniques. We believe that theory of linear algebra and constraint programming constitutes a sound basis for learning missing values when summary information is available.

REFERENCES

• 1: Bulletin of the Technical Committee on Data Engineering, 23(4), 2000.
• 2: M. Berry. Large scale sparse singular value computations. The International Journal of Supercomputer Applications, 6(1):13-49, 1992.
• 3: M. Berry and A. Sameh. An overview of parallel algorithms for the singular value and dense symmetric eigenvalue problems. Journal of Computational and Applied Mathematics, 27:191-213, 1989.
• 4: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and regression trees. Wadsworth, Belmont, CA, 1984.
• 5: N. Chakravarti. Some results concerning post-infeasibility analysis. European Journal of Operation Research, 73:139-143, 1994.
• 6: Francis Y. L. Chin , Peter Kossowski, Efficient inference control for range SUM queries on statistical data bases, Proceedings of the 1st LBL Workshop on Statistical database management, p.239-248, December 02-04, 1981, Melno Park, California
• 7: J. W. Chinneck and E. W. Dravnieks. Locating minimal infeasible constraint sets in linear programs. ORSA Journal on Computing, 3(2):157-168, 1991.
• 8: J. Darroch and D. Ratcliff. Generalized iterative scaling for log-linear models. Annals of Mathematical Statistics, 43:1470-1480, 1972.
• 9: Christos Faloutsos , H. V. Jagadish , Nikolaos Sidiropoulos, Recovering Information from Summary Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.36-45, August 25-29, 1997
• 10: J. Friedman. Multivariate adaptive regression splines. The Annals of Statistics, 19(1):1-141, 1991.
• 11: Helena Galhardas , Daniela Florescu , Dennis Shasha , Eric Simon , Cristian-Augustin Saita, Declarative Data Cleaning: Language, Model, and Algorithms, Proceedings of the 27th International Conference on Very Large Data Bases, p.371-380, September 11-14, 2001
• 12: A. Golan, G. Judge, and D. Miller. Maximum entropy econometrics: robust estimation with limited data. John Wiley, New York, 1996.
• 13: C. Golub and C. V. Loan. Matrix computations. Johns Hopkins University Press, 1989.
• 14: G. Golub and W. Kahan. Calculating the singular values and pseudoinverse of a matrix. SIAM Journal of Numerical Analysis, 2(3):205-224, 1965.
• 15: I. Good. Maximum entropy for hypothesis formulation, especially for multidimensional contingency tables. Annals of Mathematical Statistics, 34:911-934, 1963.
• 16: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 17: Jerzy W. Grzymala-Busse, On the Unknown Attribute Values in Learning from Examples, Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, p.368-377, October 16-19, 1991
• 18: Jerzy W. Grzymala-Busse , Ming Hu, A Comparison of Several Approaches to Missing Attribute Values in Data Mining, Revised Papers from the Second International Conference on Rough Sets and Current Trends in Computing, p.378-385, October 16-19, 2000
• 19: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States
• 20: Hiroshi Hosobe, A Scalable Linear Constraint Solver for User Interface Construction, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.218-232, September 18-21, 2000
• 21: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 22: Vipul Kashyap , Amit Sheth, Semantic and schematic similarities between database objects: a context-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.276-304, December 1996 [doi>10.1007/s007780050029]
• 23: J. Kullback. Information theory and statistics. John Wiley, New York, 1959.
• 24: Mong Li Lee , Tok Wang Ling , Wai Lup Low, IntelliClean: a knowledge-based intelligent data cleaner, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.290-294, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347154]
• 25: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 26: R. Lynch. An assessment of the RAS method for updating input-output Tables. In I. Sohn, editor, Readings in Input-Output Analysis, pages 271-284. Oxford University Press, 1986.
• 27: R. Myers. Classical and modern regression with applications. Duxbury, Boston, MA, 1986.
• 28: R. Neal. Probabilistic inference using markov chain monte carlo methods. Technical Report CRG-TR-93-1, Dept. of Computer Science, University of Toronto, 1993.
• 29: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes in C: the art of scientific computing, Cambridge University Press, New York, NY, 1988
• 30: A. L. Prodromidis and S. Stolfo. Mining databases with different schemas: integrating incompatible classifiers. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, 1998.
• 31: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 32: J. R. Quinlan, Unknown attribute values in induction, Proceedings of the sixth international workshop on Machine learning, p.164-168, December 1989, Ithaca, New York, United States
• 33: Vijayshankar Raman , Joseph M. Hellerstein, Potter's Wheel: An Interactive Data Cleaning System, Proceedings of the 27th International Conference on Very Large Data Bases, p.381-390, September 11-14, 2001
• 34: J. L. Schafer. Analysis of incomplete multivariate data. Chapman and Hall, London, 1997.
• 35: Michael H. Schneider , Stavros A. Zenios, A comparative study of algorithms for matrix balancing, Operations Research, v.38 n.3, p.439-455, May/June 1990 [doi>10.1287/opre.38.3.439]
• 36: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 37: C. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379-423, 1948.
• 38: M. Wagner, J. Meller, and R. Elber. Large-scale linear programming techniques for he design of protein folding potentials. Technical Report 2002-02, Old Dominion University, 2002.
• 39: Xintao Wu , Daniel Barbará, Modeling and Imputation of Large Incomplete Multidimensional Datasets, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.286-295, September 04-06, 2002

INDEX TERMS

Keywords:
constraint programming, cross entropy, data cleaning, linear algebra, maximum entropy