一种面向间隙核函数的快速算法  

A Fast Algorithm for Gapped Kernels

作　　者：尹传环[1] 田盛丰[1] 牟少敏[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《电子学报》2007年第5期875-881,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60442002);北京交通大学科技基金(No.2004SM010)

摘　　要：间隙核是一种应用非常广泛的字符串核,在文本分类和蛋白质分类中都取得了很好的效果.本文提出了一种应用在入侵检测领域的间隙核,称为长度加权核.并且提出了一种基于后缀核的动态规划算法,能够有效计算变长度加权核.另外,本文提出了一种位并行算法,能够加速定长度加权核的计算.实验表明在满足位并行的条件下这种快速算法比现有的几种计算间隙核的算法更为快速,而且应用在入侵检测中能够取得较好的效果.So far the gapped kemels are used in many fields,such as text classification and protein classification.In this paper,a new kind of gapped kernel is presented, which is called length-weighted kernel, including p-length-weighted and all-length-weighted kemels. Length-weighted kernels can be used to detect intrusion process. Furthermore, a dynamic programming algorithm based on suffix kernel is proposed to compute the length-weighted kemels.Moreover, a bit-parallel technique is used to reduce the complexity of p-length-weighted kernel. The empirical results suggest that this bit-parallel technique algorithm outperforms the other approaches in some cases where the necessary condition of using bit-parallel technique can be satisfied, and that the new kernels can achieve better performance than others gapped kernels.

关 键 词：核方法 字符串核 间隙核 位并行 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]