## Abstract

We investigate infinite information systems. Such systems are widely used in pattern recognition, data mining, discrete optimization, computational geometry. An information system is called compressible relatively to a given weight function if for each problem over the information system with sufficiently large weight (i.e., total weight of attributes in the problem description) there exists a decision tree (i) solving this problem and (ii) having the weighted depth less than the problem weight. In the paper all pairs (information system, weight function) such that the information system is compressible relatively to the weight function are described. For each such pair the behavior of Shannon type function is investigated characterizing the growth in the worst case of the minimal weighted depth of decision trees with the growth of problem weight.

Original language | English (US) |
---|---|

Pages (from-to) | 51-61 |

Number of pages | 11 |

Journal | Fundamenta Informaticae |

Volume | 55 |

Issue number | 1 |

State | Published - Apr 2003 |

Externally published | Yes |

## Keywords

- Decision tree
- Information system
- Weighted depth

## ASJC Scopus subject areas

- Theoretical Computer Science
- Algebra and Number Theory
- Information Systems
- Computational Theory and Mathematics