基于非均匀切割的HiCuts分类算法  

HiCuts classification algorithm based on non-uniform cutting

作　　者：汪文勇[1] 任春梅[1] 黄鹂声[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机应用》2013年第2期357-360,共4页journal of Computer Applications

基　　金：国家973计划项目(G1999032707);国家863计划项目(2008AA01A303);国家科技支撑计划项目(2008BAH37B03)

摘　　要：数据包分类技术广泛应用于许多网络服务当中,HiCuts算法是多维包分类中最具有代表性的数据包分类算法。但由于规则集分布不均匀,通过简单地随机等分某个域很难将规则划分到不同的节点去,从而导致决策树树深度急剧增加,使算法查找的时间效率和空间效率大大降低。通过大量统计分析发现,规则集中的规则域并非均匀分布在其取值范围内,为此,在HiCuts算法的基础上提出了一种利用非均匀切割技术的N-HiCuts算法来构建决策树。算法对于分布不均匀的域依据统计规则进行非均匀切割,对规则集中分布均匀的某些域采用等分函数来进行切割,从而提高每次对规则集进行切割的效率。实验证明,该算法的整体性能得到较大的提高。Packet classification technology has been widely used in many network services, and Hierarchical Intelligent Cuttings （HiCuts） algorithm is the most representative multi-dimensional packet classification algorithm. However, due to the uneven distribution of rules, it is difficult to divide rules into different nodes by dividing each domain equally, thus causing the depth of the decision tree increase dramatically, and the time efficiency and space efficiency of the algorithm reduced greatly. By massive statistical analysis, it is found that the rules of rule set are not uniformly distributed within their range. A non- uniform cutting technique named N-HiCuts algorithm was proposed to build decision tree algorithm on the basis of HiCuts. For the uneven distribution domain, non-uniform cutting was adopted on the basis of statistical rules. For the even distribution domain, the equal dividing function was adopted to cut, therefore the efficiency of cutting the rule set is improved. The experimental results show that the overall performance of the proposed algorithm is greatly improved.

关 键 词：包分类 智能层次分割算法 非均匀切割 决策树 

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