×

A list-based compact representation for large decision tables management. (English) Zbl 1061.90057

Summary: Due to the huge size of the tables we manage when dealing with real decision-making problems under uncertainty, we propose turning them into minimum storage space multidimensional matrices. The process involves searching for the best order of the matrix dimensions, which is a NP-hard problem. Moreover, during the search, the computation of the new storage space that each order requires and copying the table with respect to the new order may be too time consuming or even intractable if we want a process to work in a reasonable time on an ordinary PC. In this paper, we provide efficient heuristics to solve all these problems. The optimal table includes the same knowledge as the original table, but it is compacted, which is very valuable for knowledge retrieval, learning and expert reasoning explanation purposes.

MSC:

90B50 Management decision making, including multiple objectives
90C27 Combinatorial optimization

Software:

C4.5
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alander, J. T., On optimal population size of genetic algorithms, (Dewilde, P.; Vandewalle, J., CompEuro 1992 Proceedings, Computer Systems and Software Engineering, 6th Annual European Computer Conference (1992), IEEE Computer Society Press), 65-70
[2] Bielza, C.; Gómez, M.; Rı́os-Insua, S.; Fernández del Pozo, J. A., Structural, elicitation and computational issues faced when solving complex decision making problems with influence diagrams, Computers & Operations Research, 27, 7-8, 725-740 (2000) · Zbl 0972.90040
[3] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (Horvitz, E.; Jensen, F., Uncertainty in Artificial Intelligence: Proceedings of the 12th Conference (1996), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 115-123
[4] Breiman, L.; Friedman, J. H.; Olshen, R. A.; Stone, C. J., Classification and Regression Trees (1993), Chapman & Hall: Chapman & Hall New York
[5] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification (2001), Wiley: Wiley New York · Zbl 0968.68140
[6] Ezawa, K., Evidence propagation and value of evidence on influence diagrams, Operations Research, 46, 1, 73-83 (1998) · Zbl 0993.91500
[7] Fagiuoli, E.; Zaffalon, M., A note about redundancy in influence diagrams, International Journal of Approximate Reasoning, 19, 3-4, 351-365 (1998) · Zbl 0947.68141
[8] Fayyad, U. M.; Piatetsky-Shapiro, G.; Smyth, P., From data mining to knowledge discovery: An overview, (Fayyad, U. M.; Piatetsky-Shapiro, G.; Smyth, P.; Uthurusami, R., Advances in Knowledge Discovery and Data Mining (1996), AAAI Press), 1-34
[9] Fernández del Pozo, J. A.; Bielza, C., An interactive framework for open queries in decision support systems, (Garijo, F. J.; Riquelme, J. C.; Toro, M., Advances in Artificial Intelligence. Advances in Artificial Intelligence, Lecture Notes in Artificial Intelligence, vol. 2527 (2002), Springer: Springer Berlin), 254-264 · Zbl 1036.68580
[10] Fernández del Pozo, J. A.; Bielza, C.; Gómez, M., Knowledge organisation in a neonatal jaundice decision support system, (Crespo, J.; Maojo, V.; Martı́n, F., Medical Data Analysis. Medical Data Analysis, Lecture Notes in Computer Science, vol. 2199 (2001), Springer: Springer Berlin), 88-94 · Zbl 1030.68662
[11] Hand, D.; Mannila, M.; Smyth, P., Principles of Data Mining (2001), The MIT Press: The MIT Press Cambridge, Mass
[12] Hansen, P.; Mladenović, N., Variable neighbourhood search: Principles and applications, European Journal of Operational Research, 130, 449-467 (2001) · Zbl 0981.90063
[13] Hastie, T.; Tibshirani, R.; Friedman, J., The Elements of Statistical Learning (2001), Springer: Springer New York
[14] Henrion, M.; Breese, J. S.; Horvitz, E. J., Decision analysis and expert systems, Artificial Intelligence Magazine, 12, 4, 64-91 (1991)
[15] Keeney, R. L.; Raiffa, H., Decisions with Multiple Objectives: Preferences and Value Tradeoffs (1993), Cambridge University Press: Cambridge University Press Cambridge, GB · Zbl 0488.90001
[16] Kirkpatrick, S.; Gelett, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 621-630 (1983) · Zbl 1225.90162
[17] Knuth, D. E., (The Art of Computer Programming: Fundamental Algorithms, vol. 1 (1968), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[18] Lauritzen, S.; Nilsson, D., Representing and solving decision problems with limited information, Management Science, 47, 9, 1235-1251 (2001) · Zbl 1232.90343
[19] Mannila, H., Theoretical frameworks for data mining, SIGKDD Explorations, 1, 2, 30-32 (2000)
[20] Mitchell, M., An Introduction to Genetic Algorithms (1998), MIT Press: MIT Press Cambridge, MA · Zbl 0906.68113
[21] Nielsen, T. D.; Jensen, F. V., Welldefined decision scenarios, (Laskey, K. B.; Prade, H., Uncertainty in Artificial Intelligence: Proceedings of the 15th Conference (1999), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 502-511
[22] Pawlak, Z., Rough Sets. Theoretical Aspects of Reasoning about Data (1991), Kluwer: Kluwer Dordrecht · Zbl 0758.68054
[23] Pawlak, Z., Rough set approach to knowledge-based decision support, European Journal of Operational Research, 99, 48-57 (1997) · Zbl 0923.90004
[24] Quinlan, J. R., Induction of decision trees, Machine Learning, 1, 81-106 (1986)
[25] Quinlan, J. R., C4.5: Programs for Machine Learning (1993), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA
[26] Raiffa, H., Decision Analysis (1968), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0181.21802
[27] Shachter, R. D., Evaluating influence diagrams, Operations Research, 34, 6, 871-882 (1986)
[28] Vomvelová, M., Jensen, F.V., 2002. An extension of lazy evaluation for influence diagrams avoiding redundant variables in the potentials. In: Gámez, J.A., Salmerón, A. (Eds.), Proceedings of the First European Workshop on Probabilistic Graphical Models -PGM’02-, University of Castilla-LaMancha, Spain, pp. 186-193; Vomvelová, M., Jensen, F.V., 2002. An extension of lazy evaluation for influence diagrams avoiding redundant variables in the potentials. In: Gámez, J.A., Salmerón, A. (Eds.), Proceedings of the First European Workshop on Probabilistic Graphical Models -PGM’02-, University of Castilla-LaMancha, Spain, pp. 186-193
[29] Wong, S. K.; Ziarko, W.; Li Ye, R., Comparison of rough set and statistical methods in inductive learning, International Journal of Man-Machine Studies, 24, 53-72 (1986) · Zbl 0634.68088
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.