基于动态点切分的多决策树包分类算法  

Multiple Decision Tree Algorithm for Packet Classification Based on Dynamic Point Split

作　　者：韩伟涛[1] 伊鹏[1] 扈红超[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《电子与信息学报》2013年第12期2985-2991,共7页Journal of Electronics & Information Technology

基　　金：国家重点基础研究发展计划(2012CB315901);国家高技术研究发展计划(2011AA01A103);国家科技支撑计划(2011BAH19B01)资助课题

摘　　要：针对传统的包分类算法存在较多规则冗余问题,该文在分析规则集特征的基础上,提出一种基于动态点切分的多决策树包分类算法(Clustered Dynamic Point Split,CDPS)。该算法首先通过聚类具有相似空间交叉关系的规则,划分规则集为若干子集,然后在每个子集中动态地选取规则投影点完成空间分解并建立决策树。仿真结果表明,在保证算法的时间性能前提下,CDPS算法的内存占用较HyperSplit和EffiCuts分别减少了95%和50%。Traditional packet classification algorithms often have many redundant rules. To solve this issue, a packet classification algorithm called Clustered Dynamic Point Split （CDPS） is proposed based on the analysis of the characteristics of rule sets. CDPS divides the rule set by clustering the rules with similar cross-space relationship, then, it dynamically selects the rule projection points to complete the space decomposition and to build the decision tree. Simulation results show that, without reducing the time performance, the memory cost of CDPS is 95%and 50%less than HyperSplit and EffiCuts, respectively.

关 键 词：包分类 决策树 内存优化 动态点切分 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]