论文部分内容阅读
摘要：针对现行数据集分割方法中的不足，从信息学的角度出发，引用信息熵理论，提出了一种简单可行的数据集分割方法，即选择使数据子集的总体熵较小的分割方式，实验结果证明了这种方法的有效性。
关键词：信息熵；数据集分割；入侵检测
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)05-11193-02
1 引言
对于异常检测，或更一般的，对于一个模式识别问题来说，任何一个检测模型或分类算法都有一定的时间和空间复杂度，如表1所示[1]：
表1 分类算法与时间复杂度关系举例
大部分算法在样本数(数据集数据)达到一定的规模之后，其时间复杂度都会达到一个相当高的水平，以至于令人无法接受。对空间复杂度的考察也有相似的结论。
本文主要讨论如何通过数据集分割减少复杂度的问题。
2 问题的提出
所谓数据集分割，即在尽可能不影响分类效果的情况下，将一个具有较大规模的数据集通过某种分割规则分割为数个具有较小规模的不相交的子集。假设原数据集为?专，各个数据子集为θi，即：
从目前来看，对于入侵检测这个特定问题来说，数据分割方法中的核心问题——分割规则的选择方法有：
(1)随机分割法。从一个原始大数据集中随机选择一部分数据组成一个小数据集，重复该过程，直到全部数据被分割出来。
(2)顺序分割法。从一个有n个数据的大数据集，按顺序将前m(m (3)属性值分割法。将原始大数据集按某个(组)属性的取值进行分割。例如，数据集中某个属性的取值范围是1-10，那么就可以将数据集按照该属性的每种取值分割为十个子集。但选择哪个(组)属性进行分割最为合理，大都依据特定分类问题和个人经验。
应该指出，由于没有理论上和具体方法上的指导，目前在数据集分割这个问题上，大家的处理较为混乱。从目前有关异常检测的文献资料所提供的数据来看，无论是采用随机分割法、顺序分割法还是简单的属性值分割法，数据集分割后往往或是使数据过于分散导致检测模型的检测效果不理想，或是由于对特定问题人为的介入过多导致分类模型的泛化性能不好。
3 熵的引入
熵[2]这个术语首次由Clausius于1864年首次引入热力学领域中，香农于1948年把这个概念引入信息理论中，因此又称为香农熵，它是信息的一种度量，其核心是把信息的度量看作是对事物不肯定性的度量。香农熵是与概率分布相联系的，但并不能通过它就可以确定信息的全部度量，事实上它仅仅是从“不确定性”(uncertainty)这个角度而作为度量基础的一个新的概念和度量被提出的。
“不确定性”的另一种表述就是规律性(regularity)，而信息熵就是度量数据集的“不确定性”的函数，它当然也可以度量数据集的规律性。在建立检测模型时，我们可将整个训练数据集看作是信源，将每条记录看作是信源发出的信号，对信源规律性的度量就是对整个训练数据集的规律性的度量。对于异常检测来说，为了得到较好的检测率和较低的误报率，我们总是希望数据集应尽可能的有规律性，因为规律性强的数据集中含有较多的冗余信息并对将来的数据的分类提供更多的帮助。可想而知，若当前数据集的规律很强，其中的许多样本点是以大概率事件出现，那么在这个数据集上建立起来的检测模型的检测效果也应该很好；相反，在一个非常混乱的数据集上建立起来的检测模型，它的检测效果就不一定会理想。我们利用“信息熵”这个度量来考察待检测数据集的规律性。熵值越小，数据越集中，我们就可以称该数据集越规律，相反，熵值越大，我们就称该数据子集的规律性越弱。因此，在可以选择数据集分割的方式时，我们应选择使数据子集的总体熵较小(即各个数据子集的规律性较强)的分割方式。
另外，在小熵值的数据集上建立起来的检测模型较使用大熵值的数据集建立起来的检测模型会更简单和高效。举例来说，直观上我们知道，如果一个训练数据集中的所有记录都相同(即这个数据记录出现的概率为1)，此时熵值为零。对于这样一个训练集，我们只需要一个分类规则就可以对待检测数据进行分类，且此时的分类效果为最优。相反，若训练数据集中含有较多不同的记录数据，此时熵值将较大，这时建立的检测模型也会较前者复杂，检测效果较前者也会有所下降。
由此，我们根据信息熵来进行数据集分割的方法是：将训练数据集按某个属性的不同取值进行分割，并按下列公式计算分割后的总体信息熵Hs：
其中，n为原始大数据集分割后的数据子集个数，ci是第i个数据子集中的数据个数，C是原始大数据集中的数据总数，Hi是第i个数据子集的熵值。我们的目标是使分割后的Hs较小。
4 实验
4.1 实验目的、环境、工具
目的：利用信息熵值作为判据，将原始的大数据集分割为较小的互不相交的数据子集。
环境：内存256M、CPU P4 2.4GHz。
开发工具：VisualC++6.0。
4.2 实验方法
KDD’99[5](KDD’99数据集是一个典型的数据挖掘数据库，是一个被广泛用来评价入侵检测算法和开展入侵检测研究的数据集)的所有属性中共有四个离散字符型属性，如表2所示。
表2 KDD’99中的三个离散字符型属性
我们按照离散字符型数据类型属性的取值进行分割，因为无法直接按照连续数值型或是离散数值型属性对数据集进行分割，而必须对其进行某种离散化的处理。我们按照表1四个属性的取值做了四次不同的数据分割，并分别计算分割后的总体信息熵。
算法伪代码如下：
基于总体平均熵最小化的原始数据集分割算法
输入：任意空间上的数据集Ds_In，分割依据属性名A，属性A的n个不同取值S={s1,s2,….,sn}
输出：分割后的数据子集集合X
4.3 实验结果
利用以上方法得到实验结果如表3所示：
表3 实验结果
4.4 实验分析
从表3中可以看到，将原始数据集按照服务类型(service)属性进行分割后，得到的总体平均信息熵值最小(20.78)，这也就意味着，将原始数据集按照服务类型(service)属性进行分割后，总体上各个数据子集的规律性最强。
同时，我们还对分割后的数据集做进一步的分割进行了尝试，我们按照服务类型(service)属性进行分割后，再进一步按照协议类型(protocol_type)属性进行分割。但我们发现，尽管其总体信息熵值会进一步降低，但降低的幅度并不明显，却使数据集规模过小，由于得不到数量上的保证，使检测模型的泛化性能降低，影响了检测效果，因此我们决定使用服务类型(service)属性作为最后的数据集分割依据，不再进行进一步的分割。
5 小结
文章首先讨论了对原始大数据集进行分割的必要性和现有的分割方法，接着对利用信息熵对数据集分割的理论基础和实施方法进行了阐述，给出了算法描述，最后以该算法为基础进行了实验并确定了进行分割的属性。使用这种方法进行数据分割后的数据子集，不仅其规律性增强，同时可以减少一维特征。
参考文献：
[1]边肇祺,张学工.等.模式识别(第2版)[M].北京:清华大学出版社,2003．
[2]沈世镒,陈鲁生.等.信息论与编码理论[M].北京:科学技术出版社,2001.
[3]杨智君,田地.等.入侵检测技术研究综述[J].计算机工程与设计,2006(6).
[4]Brain Caswell,Jay Beale,James C.Foster et al.Snort2.0 Instrusion Detection[J].Syngress Publishing,Inc,2003.
[5]http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：信息熵；数据集分割；入侵检测
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)05-11193-02
1 引言
对于异常检测，或更一般的，对于一个模式识别问题来说，任何一个检测模型或分类算法都有一定的时间和空间复杂度，如表1所示[1]：
表1 分类算法与时间复杂度关系举例
大部分算法在样本数(数据集数据)达到一定的规模之后，其时间复杂度都会达到一个相当高的水平，以至于令人无法接受。对空间复杂度的考察也有相似的结论。
本文主要讨论如何通过数据集分割减少复杂度的问题。
2 问题的提出
所谓数据集分割，即在尽可能不影响分类效果的情况下，将一个具有较大规模的数据集通过某种分割规则分割为数个具有较小规模的不相交的子集。假设原数据集为?专，各个数据子集为θi，即：
从目前来看，对于入侵检测这个特定问题来说，数据分割方法中的核心问题——分割规则的选择方法有：
(1)随机分割法。从一个原始大数据集中随机选择一部分数据组成一个小数据集，重复该过程，直到全部数据被分割出来。
(2)顺序分割法。从一个有n个数据的大数据集，按顺序将前m(m
应该指出，由于没有理论上和具体方法上的指导，目前在数据集分割这个问题上，大家的处理较为混乱。从目前有关异常检测的文献资料所提供的数据来看，无论是采用随机分割法、顺序分割法还是简单的属性值分割法，数据集分割后往往或是使数据过于分散导致检测模型的检测效果不理想，或是由于对特定问题人为的介入过多导致分类模型的泛化性能不好。
3 熵的引入
熵[2]这个术语首次由Clausius于1864年首次引入热力学领域中，香农于1948年把这个概念引入信息理论中，因此又称为香农熵，它是信息的一种度量，其核心是把信息的度量看作是对事物不肯定性的度量。香农熵是与概率分布相联系的，但并不能通过它就可以确定信息的全部度量，事实上它仅仅是从“不确定性”(uncertainty)这个角度而作为度量基础的一个新的概念和度量被提出的。
“不确定性”的另一种表述就是规律性(regularity)，而信息熵就是度量数据集的“不确定性”的函数，它当然也可以度量数据集的规律性。在建立检测模型时，我们可将整个训练数据集看作是信源，将每条记录看作是信源发出的信号，对信源规律性的度量就是对整个训练数据集的规律性的度量。对于异常检测来说，为了得到较好的检测率和较低的误报率，我们总是希望数据集应尽可能的有规律性，因为规律性强的数据集中含有较多的冗余信息并对将来的数据的分类提供更多的帮助。可想而知，若当前数据集的规律很强，其中的许多样本点是以大概率事件出现，那么在这个数据集上建立起来的检测模型的检测效果也应该很好；相反，在一个非常混乱的数据集上建立起来的检测模型，它的检测效果就不一定会理想。我们利用“信息熵”这个度量来考察待检测数据集的规律性。熵值越小，数据越集中，我们就可以称该数据集越规律，相反，熵值越大，我们就称该数据子集的规律性越弱。因此，在可以选择数据集分割的方式时，我们应选择使数据子集的总体熵较小(即各个数据子集的规律性较强)的分割方式。
另外，在小熵值的数据集上建立起来的检测模型较使用大熵值的数据集建立起来的检测模型会更简单和高效。举例来说，直观上我们知道，如果一个训练数据集中的所有记录都相同(即这个数据记录出现的概率为1)，此时熵值为零。对于这样一个训练集，我们只需要一个分类规则就可以对待检测数据进行分类，且此时的分类效果为最优。相反，若训练数据集中含有较多不同的记录数据，此时熵值将较大，这时建立的检测模型也会较前者复杂，检测效果较前者也会有所下降。
由此，我们根据信息熵来进行数据集分割的方法是：将训练数据集按某个属性的不同取值进行分割，并按下列公式计算分割后的总体信息熵Hs：
其中，n为原始大数据集分割后的数据子集个数，ci是第i个数据子集中的数据个数，C是原始大数据集中的数据总数，Hi是第i个数据子集的熵值。我们的目标是使分割后的Hs较小。
4 实验
4.1 实验目的、环境、工具
目的：利用信息熵值作为判据，将原始的大数据集分割为较小的互不相交的数据子集。
环境：内存256M、CPU P4 2.4GHz。
开发工具：VisualC++6.0。
4.2 实验方法
KDD’99[5](KDD’99数据集是一个典型的数据挖掘数据库，是一个被广泛用来评价入侵检测算法和开展入侵检测研究的数据集)的所有属性中共有四个离散字符型属性，如表2所示。
表2 KDD’99中的三个离散字符型属性
我们按照离散字符型数据类型属性的取值进行分割，因为无法直接按照连续数值型或是离散数值型属性对数据集进行分割，而必须对其进行某种离散化的处理。我们按照表1四个属性的取值做了四次不同的数据分割，并分别计算分割后的总体信息熵。
算法伪代码如下：
基于总体平均熵最小化的原始数据集分割算法
输入：任意空间上的数据集Ds_In，分割依据属性名A，属性A的n个不同取值S={s1,s2,….,sn}
输出：分割后的数据子集集合X
4.3 实验结果
利用以上方法得到实验结果如表3所示：
表3 实验结果
4.4 实验分析
从表3中可以看到，将原始数据集按照服务类型(service)属性进行分割后，得到的总体平均信息熵值最小(20.78)，这也就意味着，将原始数据集按照服务类型(service)属性进行分割后，总体上各个数据子集的规律性最强。
同时，我们还对分割后的数据集做进一步的分割进行了尝试，我们按照服务类型(service)属性进行分割后，再进一步按照协议类型(protocol_type)属性进行分割。但我们发现，尽管其总体信息熵值会进一步降低，但降低的幅度并不明显，却使数据集规模过小，由于得不到数量上的保证，使检测模型的泛化性能降低，影响了检测效果，因此我们决定使用服务类型(service)属性作为最后的数据集分割依据，不再进行进一步的分割。
5 小结
文章首先讨论了对原始大数据集进行分割的必要性和现有的分割方法，接着对利用信息熵对数据集分割的理论基础和实施方法进行了阐述，给出了算法描述，最后以该算法为基础进行了实验并确定了进行分割的属性。使用这种方法进行数据分割后的数据子集，不仅其规律性增强，同时可以减少一维特征。
参考文献：
[1]边肇祺,张学工.等.模式识别(第2版)[M].北京:清华大学出版社,2003．
[2]沈世镒,陈鲁生.等.信息论与编码理论[M].北京:科学技术出版社,2001.
[3]杨智君,田地.等.入侵检测技术研究综述[J].计算机工程与设计,2006(6).
[4]Brain Caswell,Jay Beale,James C.Foster et al.Snort2.0 Instrusion Detection[J].Syngress Publishing,Inc,2003.
[5]http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。