第3期 顾成杰，等：结合粗糙集和禁忌搜索的网络流量特征选择 ·255· 而且不能识别出冗余特性.ⅵ等人利用遗传算法进 f(xi,a)eV 行特征属性选择，具有搜索能力强等优点，适合于大 定义1最小特征子集P设C、D分别是信息 规模复杂问题的求解，但容易过早收敛[8].文献[9] 系统S的条件特征属性集和决策特征属性集，特征 中将粒子群算法用于特征搜索，解决了遗传算法存 属性集P(PCC)是C的一个最小特征属性集，当且 在的计算量大的缺点：但算法中粒子被束缚在局部 仅当Y(P,D)=y(C,D),并且HP'CP,Y(P',D)≠ 最优点及整个种群全局最优点附近，导致其搜索区 y(C,D),则说明P是C的最小属性集，P具有和C 域有限，易于陷入局部最优.文献[10]中提出了一 同样的区分决策能力. 种基于免疫克隆算法的特征选择方法，该方法利用 定义2区分矩阵G信息系统S=(U,A,V, 免疫克隆算法能够快速收敛于全局最优的特性，加 )可以用一个1U川×IU川的对称矩阵来表示，并对矩 快了搜索到最优特征子集的收敛速度，但存在求解 阵的每一项定义为： 过程中亲和度的计算工作量较大的缺点. 「{a∈A|a()≠a(x)},D(x)≠D(x): Cy= 目前在网络流量特征选择研究方面，大多是采 【⑦，其他 用已成熟的方法进行网络流量特征选择，但由于真 本文采用基于区分矩阵的启发式粗糙集约简算 实环境中的网络流量存在大量噪声，根据网络流量 法，该算法利用特征属性在区分矩阵中出现的频率 统计特征分析得到的特征属性数目庞大，同时也存 f(a:)作为启发规则，寻找最小特征子集.特征属性 在大量冗余特征属性，所以使用现有算法进行网络 的出现频率定义为 流量特征选择还存在一定局限性.笔者在分析网络 流量特性的基础上，提出一种结合粗糙集和禁忌搜 fa,)=fa,)+k×B I C I 索的网络流量特征选择方法，通过粗糙集算法对特 式中：IC表示数据集中条件特征属性的个数；IB1 征属性进行约简，将得到的特征子集作为禁忌搜索 表示区分矩阵G中每项所包含的特征属性个数；k 的初始解，利用禁忌搜索能够得到更广的搜索空间， 是权重系数，本文默认k=1, 从而寻找到全局最优解，得到最优特征子集，该方法 若某个特征属性在区分矩阵中出现的次数越 能够较好地降低特征维度，提高分类性能 多，则该特征属性的重要性就越大：若某个特征属性 所出现的区分矩阵的项越短，则该特征属性的重要 1结合粗糙集和禁忌搜索的网络流量 程度就越大，算法描述如下. 1)初始化算法参数，候选最小特征属性子集 特征选择方法 R=⑦，每个条件特征属性在区分矩阵的出现频率 f(a:)=0. 1.1基于粗糙集的特征属性约简 2)计算区分矩阵G的每项m,同时计算各特征 粗糙集理论(rough set,.RS)是波兰数学家 属性的加权频率f代a:), Paulat提出的一种处理模糊和不确定知识的数学工 3)合并并按照特征属性的长度排序区分矩阵G 具，其中特征约简是粗糙集理论的核心问题之 4)对区分矩阵G的每项m执行： 一【2].特征约简的实质就是找到冗余特征属性。 如果m∩R==☑，选择m中f(a:)最大的特征 在特征集中去掉冗余特征后的特征集称为最小特征 属性a:,R=RU{a:. 子集，它具有与全部条件特征属性同样的区分决策 5)返回得到的最小特征子集R,算法结束， 能力 1.2禁忌搜索算法及相关参数设置 给定一个四元组的信息系统S=（U,A,V,f), 禁忌搜索(tabu search,TS)是Glover提出的一 其中：U是给定网络流量的数据样本集，为一个非空 种全局搜索算法.它模仿人类的记忆功能，在求解问 的有限集合；A=C∩D,C是网络流量样本中抽取的 题的过程中，采用禁忌技术对已经搜索过的局部最 n个条件特征属性集合，D={d}为决策属性集，即A 优解进行标记，并且在迭代中尽量避免重复的搜索， 表示网络流量样本的特征属性集合；V=UV,是特 从而获得更广的搜索区间来寻找到全局最优解4]， 征的取值范围构成的集合，其中V,是特征r的值 但是它对初始解有较强的依赖性，好的初始解可使 域：f是U×A→V的映射函数，它为每一个样本的每 禁忌搜索在解空间中搜索到最优解，并且收敛速度 个特征属性赋予一个属性值，即Ha∈A,x:∈U, 快51」