2. 中国科学院 计算技术研究所,北京 100080
2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China
粗糙集是处理不确定与不完备数据的有效工具, 尤其是属性约简获得了大量研究[1-6].近年来, 信息熵[7]被广泛应用于粗糙集, 并出现了粗糙熵、知识熵和条件熵等新概念[3-4, 8-9]. Qian等[1]提出组合熵, 用来度量不完备信息系统的不确定性; Miao等[3]基于知识熵提出一种启发式约简方法[3]; Wang等[4]利用条件信息熵进行决策表的约简; Liang等[9]提出了知识粗糙熵和粗糙集粗糙熵等新概念.
作为数据挖掘的一个重要研究方向, 离群点检测关注于数据集中的一小部分对象, 它们与其他对象存在显著的不同[10-12].目前, 已出现了多种基于不同内容的离群点检测方法, 如基于统计[10]、基于深度[11]、基于聚类[12]、基于密度[13]以及基于距离[14-15]的方法.
当前的离群点检测方法还存在一些问题, 例如, 不能有效处理不确定数据、计算开销大等.针对这些问题, 本文在粗糙集中定义一种新的粗糙熵, 提出一种基于粗糙熵的离群点检测(rough entropy-based outlier detection, REOD)算法, 并将REOD应用于无监督入侵检测.
近年来, 无监督入侵检测引起大量学者的关注[16-24].无监督方法可以直接处理未标记的样本. Portnoy等[19]最早提出无监督入侵检测的思想, 现有的无监督方法主要包括基于聚类的[19-21, 24]、基于支持向量机的[17]、基于离群点检测[18]的方法.离群点检测方法在入侵检测领域具有很大的应用潜力.入侵行为与离群点非常相似, 入侵行为相对于整个网络行为而言, 是其中一小部分具有特殊属性的数据.因此, 只要将入侵行为看作是偏离于正常行为的一类离群点, 就可以将离群点检测应用于无监督入侵检测[18].
现有的离群点检测方法不能有效处理不确定数据, 而入侵检测所面对的是一个复杂的网络环境, 具有高度的不确定性.因此, 将现有的离群点检测方法直接用于无监督入侵检测是不合适的, 需要专门设计特定的离群点检测方法.基于上述考虑, 本文提出基于粗糙熵的离群点检测算法REOD, 采取有效策略来处理不确定数据, 从而可以在未标记数据上直接检测入侵.实验表明, REOD的离群点检测性能要好于或等于已有方法, 且其对入侵的检测效果也要好于已有的同类方法.
1 粗糙集的基本知识在粗糙集中, 信息表是一个四元组IS=(U, A, V, f).其中: U和A分别是对象集和属性集;
给定信息表IS=(U, A, V, f), 对任意B ⊂eq A, 定义由B所决定的不可区分关系IND(B)为\vspace{-3pt}
IND(B)是U上的一个等价关系, 它将U划分成多个等价类, 所有等价类的集合构成U的一个划分, 记为U/IND(B). IND(B)可看作是论域U上的一条知识[25].对任意X⊂eq U, X在知识IND(B)下的粗糙度定义为
其中XB和XB分别表示X的B-下近似和B-上近似[25].
2 基于粗糙熵的离群点检测算法 2.1 离群点的定义本文使用粗糙集中粗糙熵[8-9]的概念来检测离群点.下面, 首先给出一种新的粗糙集粗糙熵的定义.
定义1 给定信息表IS=(U, A, V, f), 对任意X⊂eq U和B⊂eq A, 令X/IND(B)={B1, ..., Bm}.粗糙集X在IND(B)下的粗糙熵REB(X)被定义为
其中: ρB(X)为X在IND(B)下的粗糙度, REKX(B)=
粗糙集粗糙熵REB(X)只是度量了粗糙集X的不确定性.为了度量U中某个对象x对信息表IS不确定性的影响力, 引入对象重要性的概念.
定义2 (对象重要性) 给定信息表IS=(U, A, V, f), 对任意B⊂eq A和x ∈ U, 对象x在IND(B)下的重要性SIGB(x)被定义为
定义2的直观含义如下:当从U中去掉x后, 如果U-{x}的粗糙熵比U的粗糙熵明显增加了, 则表明U-{x}的粗糙度或知识IND(B)的粗糙熵也明显增加了.这样,就由x引发了IS不确定性的明显增加.由于不确定性的明显增加是x带来的, x在IND(B)下的重要性比较大.
接下来, 通过考察对象的重要性信息来检测离群点.离群点检测总是倾向于数据集中一小部分具有异常属性的对象[14], 因此除了重要性信息之外, 还将考虑对象的隶属信息.为了获得对象的隶属信息, 引入如下概念.
定义3 (相对比重) 给定信息表IS=(U, A, V, f), 对任意B⊂eq A, 令U/IND(B)={B1, ..., Bm}.对任意x∈ U, 等价类[x]B的相对比重RP([x]B)定义为
其中min和max分别表示集合{|B1|, ..., |Bm|}中取值最小和最大的元素.
RP([x]B)刻画的是x所在群体的相对规模, 即相对于其他群体规模而言, x所在群体的规模.
定义4 (属性序列) 给定信息表IS=(U, A, V, f), 其中A={a1, ..., ap}.对任意1≤ j≤ p, 令weight(aj)=REKU(A)-REKU(A-{aj})表示属性aj的权重.根据权重, 对A中属性进行升序排列, 从而得到属性序列S=\langle a1', ..., ap' \rangle, 其中, 对任意1≤ j≤ p, 有aj'∈ A, 并且对任意1≤ j < p, 有weight(aj')≤weight(aj+1').
定义4 (属性子集序列) 给定信息表IS=(U, A, V, f), 其中A={a1, ..., ap}.令S=\langle a1', ..., ap'\rangle为定义4中所给出的属性序列. AS= \langle A1, ..., Ap\rangle被称为IS中的一个属性子集序列, 其中, 对任意1≤ j≤ p, 有Aj⊂eq A, A1=A, Ap={ap'}, 并且对任意1≤ j <p, 有Aj+1=Aj-{aj'}.
为了度量对象的离群程度, 下面给出“粗糙熵离群因子”这一概念[14-15].
定义6 (粗糙熵离群因子) 给定信息表IS=(U, A, V, f).其中: |U|=n, A={a1, ..., ap}.令AS=\langle A1, ..., Ap \rangle为定义5中给出的属性子集序列, 对任意x∈ U, x的粗糙熵离群因子REOF(x)定义为
其中0 < λ≤1是一个给定的参数.
定义7 (基于粗糙熵的离群点) 给定信息表IS =(U, A, V, f)和阈值μ, 对于任意x ∈ U, 如果REOF(x)>μ, 则对象x被称为IS中的一个基于粗糙熵的离群点.
2.2 基于粗糙熵的离群点检测算法REOD算法1
输入:信息表IS=(U, A, V, f), |U|=n, A={a1, ..., ap}; 参数λ、阈值μ.
输出: U中的离群点以及每个对象的离群因子.
step 1:采用计数排序的方法, 计算划分U/ IND(A)[5].
step 2:根据U/IND(A), 计算知识粗糙熵REKU(A).
step 3:对任意ai ∈ A, 1≤ i≤ p, 循环执行:
step 3.1:采用计数排序方法, 计算U/IND(A-{ai});
step 3.2:计算知识粗糙熵REKU(A-{ai});
step 3.3:计算属性ai的权重weight(ai).
step 4:构建属性序列S和属性子集序列AS=\langle A1, ..., Ap \rangle.
step 5:对任意1≤ i≤ p, 循环执行:
step 5.1:计算划分U/IND({ai})和U/IND(Ai);
step 5.2:计算知识粗糙熵REKU({ai})和REKU(Ai);
step 5.3:计算粗糙集粗糙熵RE{ai}(U)和REAi(U).
step 6:对任意x ∈ U, 循环执行:
step 6.1:对任意1≤ i≤ p, 循环执行:
step 6.1.1:计算REKU– {x}({ai})、REKU – {x}(Ai);
step 6.1.2:计算RE{ai}(U–{x})、REAi(U–{x});
step 6.1.3:计算x的重要性SIG{ai}(x)、SIGAi(x);
step 6.1.4:计算相对比重RP([x]{ai})、RP([x]Ai).
step 6.2:计算对象x的粗糙熵离群因子REOF(x).
step 7:~根据离群因子, 对所有对象进行降序排列.
step 8:~选择离群因子大于μ的对象作为离群点.
step 9:~算法结束, 返回所有离群点及对象的离群因子.
对任意B ⊂eq A, 算法1采用了一种预先对U中对象进行计数排序, 然后再求划分U/IND(B)的方法[5].在最坏的情况下, 算法1的时间复杂度为O(|A|2×|U|), 空间复杂度为O(|A|× (|A|+|U|)).
2.3 实验结果下面, 通过实验来验证REOD的性能.首先, 在UCI数据集Lymphography[26]上比较REOD、KNN[27]和基于距离的离群点检测方法(简称DIS)[14]的性能; 其次, 在数据集Breast Cancer上[26], 比较REOD、KNN、RNN[28]和DIS这4种方法的性能, 其中RNN的实验结果可参见文献[28].
对于KNN, 设置参数k为5[27].对于DIS, 具体实验细节请参见文献[14].另外, 对于REOD, 通过多次实验尝试来确定参数λ的取值.具体而言, 首先为λ设置一个初始经验值, 并验证相应的离群点检测结果; 然后, 不断调整λ的值并验证调整后的实验结果, 直到得到满意的结果; 最终, λ被设置为0.55.
实验采用文献[29]中提出的评价指标体系来评测各个方法的性能.首先, 在Lymphography上进行实验.该数据集包含148个对象和19个属性, 共6个离群点.具体实验结果如表 1所示.
表 1中:“属于离群点的对象个数”是指在由某个方法所计算出的离群程度值排在前k %的对象中, 真正的离群点个数; “覆盖率”是指目前已检测出的离群点占整个离群点的比例[14-15].从表 1可以看出, REOD的性能明显要好于DIS和KNN.
其次, 在Breast Cancer上进行实验.该数据集包含699个对象和9个属性.为了获得一个不平衡的数据集, 删除了其中一些“malignant”对象(即属于恶性肿瘤的样本).最终的数据集包含39个“malignant”和444个“benign”对象(属于良性肿瘤的样本).另外, 对该数据集中的连续型属性进行了离散化处理[28].Breast Cancer上的实验结果如表 2所示.
本节将REOD算法应用于无监督入侵检测, 进而得到一种新的无监督入侵检测方法.该方法无需对入侵行为或正常行为建模, 而是通过检测离群点的方式直接检测入侵, 其基本流程如图 1所示.
如图 1所示, 本文提出的无监督入侵检测方法的基本流程可分为4个步骤: 1)采集网络数据包或日志文件, 并进行解码、过滤、统计、分析; 2)对数据进行预处理, 包括补齐、离散化、特征选择等; 3)采用REOD对预处理后的数据进行离群点检测; 4)将上一步检测出的离群点标记为入侵, 并响应入侵.
3.2 实~~验下面, 通过KDD Cup 99数据集来验证REOD的入侵检测性能.该数据集包含约490万条记录, 所有攻击类型被分成DOS、R2L、U2R和Probe四大类[26].该数据集过于庞大, 因此只选取了其中有代表性的一个子集“10 %-KDD” (包含494 021条记录)[26].
3.2.1 数据预处理10 %-KDD有41个属性, 其中包含了一些连续型属性[26].粗糙集更适合于处理离散型属性, 因此需要对连续型属性进行离散化[25], 采用文献[30]中提出的离散化算法SMDNS.在离散化时, 由于部分连续型属性的取值个数非常少, 没有必要进行离散化, 因此, 只针对其中的26个属性(即序号为1、5、6、10、13、16、17、23 ~ 41的属性)进行离散化.
另外, 不是所有属性对最终的入侵检测结果都有相同的影响, 对此, 本文进行了特征选择.最终, 选择17个属性(即序号为3、4、5、8、10、14、23 ~ 31、40、41的属性)用于入侵检测.
3.2.2 实验过程与结果实验过程分为如下两个阶段.
1)~针对DOS、R2L、U2R和Probe, 分别测试REOD对每类攻击的检测效果.从10 %-KDD中提取出全部97 278条正常记录, 构成数据集N.另外, 对每类攻击, 依据不同比例随机不放回地抽取出部分攻击记录, 构成数据集D、R、U、P, 其中D、R、U、P分别存放DOS、R2L、U2R和Probe类型的攻击.每类攻击的抽取比例与记录数见表 3.
对于每类攻击, 分别将N与相应的攻击数据集合并, 形成4个测试集: N∪ D、N∪ R、N∪ U和N∪ P.对于每个测试集, 先进行离散化与特征选择, 然后运行REOD, 以验证REOD对该类攻击的检测能力.为了避免随机性给实验结果带来的不稳定性, 上述实验重复100次, 最终结果取100次的平均.
2)~测试REOD对所有攻击的检测效果.从10 %-KDD中提取出全部97 278条正常记录, 构成数据集N.另外, 从396 743条攻击记录中(包含各种类型的攻击)依据一定的比例(0.504 %)随机不放回地抽取2 000条攻击记录, 构成数据集I.将N与I合并, 得到测试集N∪ I.对于N∪ I, 先进行离散化与特征选择, 然后运行REOD, 以验证REOD对混合攻击的检测能力.同样, 上述实验重复100次, 最终结果取100次的平均.
为了便于比较, 下面将狄利克雷混合模型[16]、遗传聚类[21]、度量学习[22]、遗传算法[23]、离群点检测[18]以及无监督聚类[24]共计6种入侵检测方法的实验结果与REOD的结果列在一起, 如表 4所示.
表 4中, DR(detection rate)表示检测率, FPR(false positive rate)表示误报率.从表 4可以看出, 当使用REOD检测入侵时, 对于大部分入侵网络连接, 其离群程度值明显高于正常的网络连接.因此, REOD可以有效区分正常行为与入侵行为.
通过对比各种方法的结果, 可以看出: REOD对于DOS和Probe攻击的检测效果非常好, 而对于R2L和U2R, REOD的检测效果也明显好于其他方法.无论是检测哪一种类型的攻击, REOD的检测效果明显要好于以下5种方法:狄利克雷混合模型、遗传聚类、遗传算法、无监督聚类以及离群点检测方法.与度量学习方法相比, REOD能够更好地检测出DOS、R2L和U2R这3类攻击, 只是对Probe的检测率稍低一些.另外, REOD在误报率上表现更好.因此, 总体而言, REOD的表现仍然是最优的.
3.2.3 计算性能分析为了评估REOD的计算性能, 在一台内存为8 GB、CPU为3.4 GHz的PC机上统计不同方法在前面生成的两个测试集上的运行时间.其中:测试集N∪ D包含98 495个对象和41个属性, 测试集N∪ I包含99 278个对象和41个属性.所有方法在这两个测试集上的运行时间(单位: s)如表 5所示.
进一步, 从完整的KDD Cup 99数据集中抽取全部972 781条正常记录, 并随机抽取2万条攻击记录, 从而得到第3个测试集(包含约一百万条记录).该测试集上各方法的运行时间见图 2.
从表 5以及图 2可以看出, REOD的计算性能明显优于其他方法.
4 结论本文利用粗糙集中的粗糙熵来进行离群点检测, 并提出离群点检测算法REOD.通过将入侵行为看作是离群点, 进一步将REOD应用于无监督入侵检测.该方法无需对入侵行为或正常行为建模, 而是采用离群点检测的策略直接在未标记的数据上检测入侵, 避免了有监督方法的问题.实验表明, REOD可以有效地检测出入侵行为, 特别是它的计算开销比较小, 这对于在实际环境中运行的入侵检测系统非常重要.
下一步工作将考虑结合其他机器学习算法来对本文方法进行改进, 进一步提高其对R2L和U2R攻击的检测率.另外, 计划利用扩展的粗糙集模型来改进本文方法, 例如利用邻域粗糙集[2, 31]来检测离群点, 从而不需要离散化就可以直接处理连续型属性.
[1] |
Qian Y H, Liang J Y, Wang F. A new method for measuring the uncertainty in incomplete information systems[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2009, 17(6): 855-880. DOI:10.1142/S0218488509006303 |
[2] |
Dai J H, Hu Q H, Hu H, et al. Neighbor inconsistent pair selection for attribute reduction by rough set approach[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(2): 937-950. DOI:10.1109/TFUZZ.2017.2698420 |
[3] |
Miao D Q, Hu G R. An heuristic algorithm of knowledge reduction[J]. Computer Research and Development, 1999, 36(6): 681-684. |
[4] |
Wang G Y, Yu H, Yang D C. Decision table reduction based on conditional information entropy[J]. Chinese Journal of Computers, 2002, 25(7): 759-766. |
[5] |
Xu Z Y, Liu Z P, Yang B R, et al. A quick attribute reduction algorithm with complexity of max(O(|C||U|), O(|C|2|U/C|))[J]. Chinese Journal of Computers, 2006, 29(3): 391-399. |
[6] |
陈迎春, 李鸥, 孙昱. 基于聚类离散化和变精度邻域熵的属性约简[J]. 控制与决策, 2018, 33(8): 1407-1414. (Chen Y C, Li O, Sun Y. Attribute reduction based on clustering discretization and variable precision neighborhood entropy[J]. Control and Decision, 2018, 33(8): 1407-1414.) |
[7] |
Shannon C E. The mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(3/4): 373-423. |
[8] |
Beaubouef T, Petry F E, Arora G. Information-theoretic measures of uncertainty for rough sets and rough relational databases[J]. Information Sciences, 1998, 109: 535-563. |
[9] |
Liang J Y, Shi Z Z, Li D Y, et al. Information entropy, rough entropy and knowledge granularity in incomplete information systems[J]. International Journal of General Systems, 2006, 35(6): 641-654. DOI:10.1080/03081070600687668 |
[10] |
Rousseeuw P J, Leroy A M. Robust regression and outlier detection[M]. New York: John Wiley & Sons, 1987.
|
[11] |
Johnson T, Kwok I, Ng R T. Fast computation of 2-dimensional depth contours[C]. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. New York: AAAI Press, 1998: 224-228.
|
[12] |
耿志强, 姬威, 韩永明, 等. 基于维度最大熵数据流聚类的异常检测方法[J]. 控制与决策, 2016, 31(2): 343-348. (Geng Z Q, Ji W, Han Y M, et al. Data stream clustering algorithm based on the maximum entropy of data dimension and its applications for anomaly detection[J]. Control and Decision, 2016, 31(2): 343-348.) |
[13] |
Breunig M M, Kriegel H-P, Ng R T, et al. LOF: Identifying density-based local outliers[C]. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. Dallas: ACM Press, 2000: 93-104.
|
[14] |
Jiang F, Sui Y F, Cao C G. A hybrid approach to outlier detection based on boundary region[J]. Pattern Recognition Letter, 2011, 32(14): 1860-1870. DOI:10.1016/j.patrec.2011.07.002 |
[15] |
江峰, 杜军威, 眭跃飞, 等. 基于边界和距离的离群点检测[J]. 电子学报, 2010, 38(3): 700-705. (Jiang F, Du J W, Sui Y F, et al. Outlier detection based on boundary and distance[J]. Chinese Journal of Electronics, 2010, 38(3): 700-705.) |
[16] |
Singh J P, Bouguila N. Intrusion detection using unsupervised approach[C]. Proceedings of the International EAI Conference on Emerging Technologies for Developing Countries. Morocco: Springer, 2017: 192-201.
|
[17] |
Nguyen B V. An application of support vector machines to anomaly detection[R]. Athens: Research in Computer Science-Support Vector Machine, 2002.
|
[18] |
Zhang J, Zulkernine M. Anomaly based network intrusion detection with unsupervised outlier detection[C]. IEEE International Conference on Communications. Istanbul: IEEE, 2006: 2388-2393.
|
[19] |
Portnoy L, Eskin E, Stolfo S J. Intrusion detection with unlabeled data using clustering[C]. Proceedings of the ACM Workshop on Data Mining Applied to Security. Philadelphia: ACM Press, 2001: 113-125.
|
[20] |
Eskin E, Arnold A, Prerau M, et al. A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data[C]. Applications of Data Mining in Computer Security. Boston: Springer, 2002: 78-99.
|
[21] |
Liu Y G, Chen K F, Liao X F, et al. A genetic clustering method for intrusion detection[J]. Pattern Recognition, 2004, 37(5): 927-942. DOI:10.1016/j.patcog.2003.09.011 |
[22] |
Aliakbarisani R, Ghasemi A, Felix Wu S. A data-driven metric learning-based scheme for unsupervised network anomaly detection[J]. Computers& Electrical Engineering, 2019, 73: 71-83. |
[23] |
张凤斌, 杨永田, 江子扬. 遗传算法在基于网络异常的入侵检测中的应用[J]. 电子学报, 2004, 32(5): 875-877. (Zhang F B, Yang Y T, Jiang Z Y. Genetic algorithms in intrusion detection based on network anomaly[J]. Chinese Journal of Electronics, 2004, 32(5): 875-877. DOI:10.3321/j.issn:0372-2112.2004.05.042) |
[24] |
罗敏, 王丽娜, 张焕国. 基于无监督聚类的入侵检测方法[J]. 电子学报, 2003, 31(11): 1713-1716. (Luo M, Wang L N, Zhang H G. An unsupervised clustering-based intrusion detection method[J]. Chinese Journal of Electronics, 2003, 31(11): 1713-1716. DOI:10.3321/j.issn:0372-2112.2003.11.028) |
[25] |
Pawlak Z. Rough sets[J]. International Journal of Computer and Information Sciences, 1982, 11: 341-356. DOI:10.1007/BF01001956 |
[26] |
Bache K, Lichman M. The UCI machine learning repository[EB/OL]. 2013-12-23)[2018-10-06]. http://archive.ics.uci.edu/ml.
|
[27] |
Ramaswamy S, Rastogi R, Shim K. Efficient algorithms for mining outliers from large datasets[C]. Proceedings of the ACM SIGMOD Conference on Management of Data. Dallas: ACM Press, 2000: 427-438.
|
[28] |
Harkins S, He H X, Williams G J, et al. Outlier detection using replicator neural networks[C]. Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery. Aix-en-Provence: Springer-Verlag, 2002: 170-180.
|
[29] |
Aggarwal C C, Yu P S. Outlier detection for high dimensional data[C]. Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. Santa Barbara: ACM Press, 2001: 37-46.
|
[30] |
Jiang F, Sui Y F. A novel approach for discretization of continuous attributes in rough set theory[J]. Knowledge-Based Systems, 2015, 73: 324-334. DOI:10.1016/j.knosys.2014.10.014 |
[31] |
黄恒秋, 曾玲, 黎利辉. 混合值不完备系统的双邻域粗糙集分类方法[J]. 控制与决策, 2018, 33(7): 1207-1214. (Huang H Q, Zeng L, Li L H. Double-neighborhood rough set classification method in incomplete decision system with hybrid value[J]. Control and Decision, 2018, 33(7): 1207-1214.) |