Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining | springerprofessional.de

Springer Professional

nach oben

2019 | Buch

Kapitel lesen Erstes Kapitel lesen

Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining

verfasst von: Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Verlag: Springer International Publishing

Buchreihe : Intelligent Systems Reference Library

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Dynamic programming is an efficient technique for solving optimization problems. It is based on breaking the initial problem down into simpler ones and solving these sub-problems, beginning with the simplest ones. A conventional dynamic programming algorithm returns an optimal object from a given set of objects. This book develops extensions of dynamic programming, enabling us to (i) describe the set of objects under consideration; (ii) perform a multi-stage optimization of objects relative to different criteria; (iii) count the number of optimal objects; (iv) find the set of Pareto optimal points for bi-criteria optimization problems; and (v) to study relationships between two criteria. It considers various applications, including optimization of decision trees and decision rule systems as algorithms for problem solving, as ways for knowledge representation, and as classifiers; optimization of element partition trees for rectangular meshes, which are used in finite element methods for solving PDEs; and multi-stage optimization for such classic combinatorial optimization problems as matrix chain multiplication, binary search trees, global sequence alignment, and shortest paths. The results presented are useful for researchers in combinatorial optimization, data mining, knowledge discovery, machine learning, and finite element methods, especially those working in rough set theory, test theory, logical analysis of data, and PDE solvers. This book can be used as the basis for graduate courses.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

This chapter discusses the extensions of dynamic programming developed in the book, four main directions of the study, applications, and the structure of the book.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Common Tools: Pareto Optimal Points and Decision Tables

Frontmatter

Chapter 2. Tools for Study of Pareto Optimal Points

Abstract

In this chapter, we consider tools (statements and algorithms) which are used for the study of Pareto optimal points for bi-criteria optimization problems related to decision trees, decision rules, decision rule systems, and element partition trees.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 3. Some Tools for Decision Tables

Abstract

In this chapter, we describe main notions related to decision tables, consider the structure of subtables of a given decision table represented as a directed acyclic graph (DAG), and discuss time complexity of algorithms on DAGs. We also consider classes of decision tables over restricted information systems for which these algorithms have polynomial time complexity depending on the number of conditional attributes in the input decision table.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Decision Trees

Frontmatter

Chapter 4. Different Kinds of Decision Trees

Abstract

In this chapter, we consider different kinds of decision trees, including approximate decision trees and decision trees irredundant relative to two types of decision tree uncertainty. We describe the set of decision trees corresponding to a subgraph of a directed acyclic graph constructed for a decision table, and show how to compute the cardinality of this set. We discuss also the notion of a cost function for decision trees.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 5. Multi-stage Optimization of Decision Trees with Some Applications

Abstract

In this chapter, we consider multi-stage optimization technique for decision trees and two of its applications: study of totally optimal (simultaneously optimal relative to a number of cost functions) decision trees for Boolean functions, and improvement of bounds on depth of decision trees for diagnosis of circuits.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 6. More Applications of Multi-stage Optimization of Decision Trees

Abstract

This chapter considers applications of algorithms for decision tree optimization in the area of complexity analysis. We present decision trees as models of computation for adaptive algorithms. In addition, we suggest the usage of decision tests as models of computation for non-adaptive algorithms. We show results on the complexity of two problems: problem of eight element sorting and a modified majority problem. Finally, the chapter concludes with an algorithm for optimizing decision tests for decision tables.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 7. Bi-criteria Optimization Problem for Decision Trees: Cost Versus Cost

Abstract

In this chapter, we consider an algorithm which constructs the sets of Pareto optimal points for bi-criteria optimization problems for decision trees relative to two cost functions. We also show how the constructed set of Pareto optimal points can be transformed into the graphs of functions which describe the relationships between the considered cost functions. We discuss three applications of bi-criteria optimization for two cost functions: comparison of different greedy algorithms for construction of decision trees, analysis of trade-offs for decision trees for corner point detection, and study of derivation of decision rules from decision trees.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 8. Bi-criteria Optimization Problem for Decision Trees: Cost Versus Uncertainty

Abstract

This chapter is connected with the bi-criteria optimization problem for decision trees relative to a cost function and an uncertainty measure. We explain how to construct the set of Pareto optimal points and graphs of functions which describe the relationships between the considered cost function and uncertainty measure. We end this chapter with some illustrative examples and a discussion of multi-pruning of decision trees with applications from knowledge representation and classification. The classifiers constructed by multi-pruning process often have better accuracy than the classifiers constructed by CART.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Decision Rules and Systems of Decision Rules

Frontmatter

Chapter 9. Different Kinds of Rules and Systems of Rules

Abstract

Decision rules are mappings from a set of conditions to an outcome. There are many uses for decision rules and even more methods for construction of decision rules. Decision rules are most commonly used in sets. Such sets can be referred to as systems of decision rules. Both decision rules and systems of decision rules can be analyzed with regards to different criteria (cost functions). In this chapter, we provide definitions and basic concepts with regards to decision rules and systems of decision rules.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 10. Multi-stage Optimization of Decision Rules

Abstract

Decision rules can be characterized by many parameters. This chapter presents a dynamic programming algorithm that can sequentially optimize decision rules with respect to multiple criteria. In some cases, we can find decision rules that are simultaneously optimal with respect to multiple criteria. We consider this phenomenon when dealing with length and coverage. This chapter also contains a simulation of a greedy algorithm for the construction of relatively small sets of decision rules. The work of this algorithm can be used to adapt a nontrivial lower bound on the minimum cardinality for partial covers to the construction of systems of decision rules.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 11. Bi-criteria Optimization Problem for Decision Rules and Systems of Rules: Cost Versus Cost

Abstract

In this chapter, we consider algorithms which construct the sets of Pareto optimal points for bi-criteria optimization problems for decision rules and decision rule systems relative two cost functions. We also show how the constructed set of Pareto optimal points can be transformed into the graphs of functions which describe the relationships between the considered cost functions. Further, we use the set of Pareto optimal points to measure the viability of multiple heuristic methods for the construction of systems of decision rules.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 12. Bi-criteria Optimization Problem for Decision Rules and Systems of Rules: Cost Versus Uncertainty

Abstract

In this chapter, we consider algorithms which construct the sets of Pareto optimal points for bi-criteria optimization problems for decision rules and decision rule systems relative to cost and uncertainty. We also show how the constructed set of Pareto optimal points can be transformed into the graphs of functions which describe the relationships between the considered cost function and uncertainty measure. Finally, we present experiments displaying the existence of trade-offs in various decision tables.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Element Partition Trees

Frontmatter

Chapter 13. Element Partition Trees: Main Notions

Abstract

This chapter starts by formally defining the class of meshes under study. We describe the notion of element partition tree and present an abstract way of defining optimization criteria of element partition trees in terms of cost functions. A definition of a cost function is provided in addition to a few examples of cost functions under study along with some of their properties.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 14. Multi-stage Optimization of Element Partition Trees

Abstract

This chapter presents tools and applications of multi-stage optimization of element partition trees. It starts by describing how the set of element partition trees can be represented compactly in the form of a directed acyclic graph (DAG). It then suggests algorithms to count the number of element partition trees represented by a DAG and to optimize the corresponding set of element partition trees with respect to some criterion. The latter algorithm can be used for multi-stage optimization of element partition trees relative to a sequence of cost functions and for the study of totally optimal element partition trees that are optimal with respect to multiple criteria simultaneously. Finally, we present results of experiments on three different classes of adaptive meshes.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 15. Bi-criteria Optimization of Element Partition Trees

Abstract

This chapter presents algorithm for finding Pareto optimal points corresponding to Pareto optimal element partition trees, and it suggests different applications of this algorithm.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Combinatorial Optimization Problems

Frontmatter

Chapter 16. Matrix Chain Multiplication

Abstract

This chapter is devoted to the study of matrix chain multiplication problem. For this problem, we consider different cost functions and present a multi-stage optimization procedure relative to a sequence of such functions.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 17. Binary Search Trees

Abstract

In this chapter, we present a procedure of multi-stage optimization of binary search trees relative to the weighted average depth and weighted depth. The considered procedure is based on the representation of all possible binary search trees by a directed acyclic graph.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 18. Global Sequence Alignment

Abstract

In this chapter, we study the global sequence alignment problem based on an extension of dynamic programming. We provide a method to model this problem using a directed acyclic graph which allows us to describe all optimal solutions specific to a certain cost function. Furthermore, we can optimize sequence alignments successively relative to different optimization criteria.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Chapter 19. Optimal Paths in Directed Graphs

Abstract

In this chapter, we present an algorithm for multi-stage optimization of paths in a directed graph relative to different cost functions. We consider two types of cost functions: for a given path, a function of the first type is equal to the sum of weights of edges in the path, and a function of the second type is equal to the minimum weight of some edge in the path. Weights of edges for different cost functions can be different. We study the problem of minimization for functions of the first type, and the problem of maximization for functions of the second type.

Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Backmatter

Titel: Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining
verfasst von: Hassan AbouEisha
Talha Amin
Igor Chikalov
Shahid Hussain
Mikhail Moshkov
Copyright-Jahr: 2019
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-91839-6
Print ISBN: 978-3-319-91838-9
DOI: https://doi.org/10.1007/978-3-319-91839-6

Premium Partner