A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion

Vitali Herrera-Semenets; Lázaro Bustio-Martínez; Raudel Hernández-León; Jan van den Berg

doi:10.1007/978-3-031-47765-2_18

A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion

Vitali Herrera-Semenets, Lázaro Bustio-Martínez^*, Raudel Hernández-León, Jan van den Berg

^*Corresponding author for this work

Cyber Security

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

Abstract

Decision trees are one of the most popular structures for decision-making and the representation of a set of rules. However, when a rule set is represented as a decision tree, some quirks in its structure may negatively affect its performance. For example, duplicate sub-trees and rule filters, that need to be evaluated more than once, could negatively affect the efficiency. This paper presents a novel algorithm based on Shannon’s expansion, which guarantees that the same rule filter is not evaluated more than once, even if repeated in other rules. This fact increases efficiency during the evaluation process using the induced decision tree. Experiments demonstrated the viability of the proposed algorithm in processing-intensive scenarios, such as in intrusion detection and data stream analysis.

Original language	English
Title of host publication	Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings
Subtitle of host publication	22nd Mexican International Conference on Artificial Intelligence, MICAI 2023
Editors	H. Calvo, L. Martínez-Villaseñor, H. Ponce
Place of Publication	Cham
Publisher	Springer
Pages	241-252
Number of pages	12
Edition	Part I
ISBN (Electronic)	978-3-031-47765-2
ISBN (Print)	978-3-031-47764-5
DOIs	https://doi.org/10.1007/978-3-031-47765-2_18
Publication status	Published - 2023
Event	22nd Mexican International Conference on Artificial Intelligence, MICAI 2023 - Yucatán, Mexico Duration: 13 Nov 2023 → 18 Nov 2023 Conference number: 22nd

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14391 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd Mexican International Conference on Artificial Intelligence, MICAI 2023
Country/Territory	Mexico
City	Yucatán
Period	13/11/23 → 18/11/23

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Decision Tree
Rule-Based Systems
Data Processing

Access to Document

10.1007/978-3-031-47765-2_18

Cite this

Herrera-Semenets, V., Bustio-Martínez, L., Hernández-León, R., & van den Berg, J. (2023). A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion. In H. Calvo, L. Martínez-Villaseñor, & H. Ponce (Eds.), Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings: 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023 (Part I ed., pp. 241-252). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14391 LNAI). Springer. https://doi.org/10.1007/978-3-031-47765-2_18

Herrera-Semenets, Vitali ; Bustio-Martínez, Lázaro ; Hernández-León, Raudel et al. / A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion. Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings: 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023. editor / H. Calvo ; L. Martínez-Villaseñor ; H. Ponce. Part I. ed. Cham : Springer, 2023. pp. 241-252 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{facca5f9d1ea47109b905afb880b8d05,

title = "A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon{\textquoteright}s Expansion",

abstract = "Decision trees are one of the most popular structures for decision-making and the representation of a set of rules. However, when a rule set is represented as a decision tree, some quirks in its structure may negatively affect its performance. For example, duplicate sub-trees and rule filters, that need to be evaluated more than once, could negatively affect the efficiency. This paper presents a novel algorithm based on Shannon{\textquoteright}s expansion, which guarantees that the same rule filter is not evaluated more than once, even if repeated in other rules. This fact increases efficiency during the evaluation process using the induced decision tree. Experiments demonstrated the viability of the proposed algorithm in processing-intensive scenarios, such as in intrusion detection and data stream analysis.",

keywords = "Decision Tree, Rule-Based Systems, Data Processing",

author = "Vitali Herrera-Semenets and L{\'a}zaro Bustio-Mart{\'i}nez and Raudel Hern{\'a}ndez-Le{\'o}n and {van den Berg}, Jan",

note = "Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023 ; Conference date: 13-11-2023 Through 18-11-2023",

year = "2023",

doi = "10.1007/978-3-031-47765-2_18",

language = "English",

isbn = "978-3-031-47764-5",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "241--252",

editor = "H. Calvo and Mart{\'i}nez-Villase{\~n}or, {L. } and H. Ponce",

booktitle = "Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings",

edition = "Part I",

}

Herrera-Semenets, V, Bustio-Martínez, L, Hernández-León, R & van den Berg, J 2023, A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion. in H Calvo, L Martínez-Villaseñor & H Ponce (eds), Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings: 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023. Part I edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14391 LNAI, Springer, Cham, pp. 241-252, 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Yucatán, Mexico, 13/11/23. https://doi.org/10.1007/978-3-031-47765-2_18

A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion. / Herrera-Semenets, Vitali; Bustio-Martínez, Lázaro; Hernández-León, Raudel et al.
Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings: 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023. ed. / H. Calvo; L. Martínez-Villaseñor; H. Ponce. Part I. ed. Cham: Springer, 2023. p. 241-252 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14391 LNAI).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion

AU - Herrera-Semenets, Vitali

AU - Bustio-Martínez, Lázaro

AU - Hernández-León, Raudel

AU - van den Berg, Jan

N1 - Conference code: 22nd

PY - 2023

Y1 - 2023

N2 - Decision trees are one of the most popular structures for decision-making and the representation of a set of rules. However, when a rule set is represented as a decision tree, some quirks in its structure may negatively affect its performance. For example, duplicate sub-trees and rule filters, that need to be evaluated more than once, could negatively affect the efficiency. This paper presents a novel algorithm based on Shannon’s expansion, which guarantees that the same rule filter is not evaluated more than once, even if repeated in other rules. This fact increases efficiency during the evaluation process using the induced decision tree. Experiments demonstrated the viability of the proposed algorithm in processing-intensive scenarios, such as in intrusion detection and data stream analysis.

AB - Decision trees are one of the most popular structures for decision-making and the representation of a set of rules. However, when a rule set is represented as a decision tree, some quirks in its structure may negatively affect its performance. For example, duplicate sub-trees and rule filters, that need to be evaluated more than once, could negatively affect the efficiency. This paper presents a novel algorithm based on Shannon’s expansion, which guarantees that the same rule filter is not evaluated more than once, even if repeated in other rules. This fact increases efficiency during the evaluation process using the induced decision tree. Experiments demonstrated the viability of the proposed algorithm in processing-intensive scenarios, such as in intrusion detection and data stream analysis.

KW - Decision Tree

KW - Rule-Based Systems

KW - Data Processing

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

U2 - 10.1007/978-3-031-47765-2_18

DO - 10.1007/978-3-031-47765-2_18

M3 - Conference contribution

SN - 978-3-031-47764-5

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 241

EP - 252

BT - Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings

A2 - Calvo, H.

A2 - Martínez-Villaseñor, L.

A2 - Ponce, H.

PB - Springer

CY - Cham

T2 - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023

Y2 - 13 November 2023 through 18 November 2023

ER -

Herrera-Semenets V, Bustio-Martínez L, Hernández-León R, van den Berg J. A Decision Tree Induction Algorithm for Efficient Rule Evaluation Using Shannon’s Expansion. In Calvo H, Martínez-Villaseñor L, Ponce H, editors, Advances in Computational Intelligence - 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023, Proceedings: 22nd Mexican International Conference on Artificial Intelligence, MICAI 2023. Part I ed. Cham: Springer. 2023. p. 241-252. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-47765-2_18