Minimizing size of decision trees for multi-label decision tables

Mohammad Azad; Mikhail Moshkov

doi:10.15439/2014F256

Minimizing size of decision trees for multi-label decision tables

Mohammad Azad, Mikhail Moshkov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy as well as dynamic programming algorithms to minimize the size of the decision trees. When we compare the optimal result from dynamic programming algorithm, we found some greedy algorithms produce results which are close to the optimal result for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference).

Original language	English (US)
Title of host publication	Proceedings of the 2014 Federated Conference on Computer Science and Information Systems
Publisher	Polish Information Processing Society PTI
Pages	67-74
Number of pages	8
ISBN (Print)	9788360810583
DOIs	https://doi.org/10.15439/2014F256
State	Published - Sep 29 2014

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

Access to Document

10.15439/2014F256

Cite this

@inproceedings{fb0da94713144d529155aac055ab685e,

title = "Minimizing size of decision trees for multi-label decision tables",

abstract = "We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy as well as dynamic programming algorithms to minimize the size of the decision trees. When we compare the optimal result from dynamic programming algorithm, we found some greedy algorithms produce results which are close to the optimal result for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference).",

author = "Mohammad Azad and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2014",

month = sep,

day = "29",

doi = "10.15439/2014F256",

language = "English (US)",

isbn = "9788360810583",

pages = "67--74",

booktitle = "Proceedings of the 2014 Federated Conference on Computer Science and Information Systems",

publisher = "Polish Information Processing Society PTI",

}

TY - GEN

T1 - Minimizing size of decision trees for multi-label decision tables

AU - Azad, Mohammad

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2014/9/29

Y1 - 2014/9/29

N2 - We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy as well as dynamic programming algorithms to minimize the size of the decision trees. When we compare the optimal result from dynamic programming algorithm, we found some greedy algorithms produce results which are close to the optimal result for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference).

AB - We used decision tree as a model to discover the knowledge from multi-label decision tables where each row has a set of decisions attached to it and our goal is to find out one arbitrary decision from the set of decisions attached to a row. The size of the decision tree can be small as well as very large. We study here different greedy as well as dynamic programming algorithms to minimize the size of the decision trees. When we compare the optimal result from dynamic programming algorithm, we found some greedy algorithms produce results which are close to the optimal result for the minimization of number of nodes (at most 18.92% difference), number of nonterminal nodes (at most 20.76% difference), and number of terminal nodes (at most 18.71% difference).

UR - http://hdl.handle.net/10754/564997

UR - https://fedcsis.org/proceedings/2014/drp/256.html

UR - http://www.scopus.com/inward/record.url?scp=84912058468&partnerID=8YFLogxK

U2 - 10.15439/2014F256

DO - 10.15439/2014F256

M3 - Conference contribution

SN - 9788360810583

SP - 67

EP - 74

BT - Proceedings of the 2014 Federated Conference on Computer Science and Information Systems

PB - Polish Information Processing Society PTI

ER -

Minimizing size of decision trees for multi-label decision tables

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this