PCMIgr: a fast packet classification method based on information gain ratio

To solve the problem of ambiguous attribute selection in existing decision tree classification algorithms, a decision tree construction method based on information entropy, PCMIgr, is proposed. PCMIgr is a heuristic method based on greedy strategy. At each decision tree node, when it is necessary to...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2023-05, Vol.79 (7), p.7414-7437
Main Authors: Cheng, Yuzhu, Shi, Qiuying
Format: Article
Language:English
Subjects:
Algorithms
Classification
Compilers
Computer Science
Decision trees
Entropy (Information theory)
Feature selection
Heuristic methods
Interpreters
Optimization
Processor Architectures
Programming Languages
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:To solve the problem of ambiguous attribute selection in existing decision tree classification algorithms, a decision tree construction method based on information entropy, PCMIgr, is proposed. PCMIgr is a heuristic method based on greedy strategy. At each decision tree node, when it is necessary to select classification attributes for division, the attribute with the highest information gain ratio is selected. The main innovation of this method is that the attribute selection in the traditional classification method based on decision tree is optimized, and the classification efficiency of the constructed decision tree is improved compared with that before optimization. At the same time, the decision tree ensures that each leaf node is only associated with one rule, which avoids the common problem of "rule replication" in the process of traditional decision tree construction, and effectively saves memory and calculation time. The experimental results show that the application of this method to the construction of classification decision tree can further improve the efficiency of packet classification method based on decision tree, and can be applied to high-speed real-time packet classification.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-022-04951-0