（计算机软件与理论专业论文）基于数据挖掘的分布式异常检测.pdf

、_g d i s t r i b u t e da n o m a l yd e t e c t i o nb a s e d o nd a t am i n i n g m a j o r ：q 磐卫坠兰皇! = 苎q ! ! 型垒! = 皇垒坠垡兰塾金q x a d v i s o r ： 里! = q 型望y 丛皇 a u t h o r ： 丕塾q 坚j 坠坠! i 望一 q 伊 0oi， ? ) l m ，单元中的对象都不是异常； 若c e l l + 2l a y e rc o t m t d k ( p ) 的点p 不超过n 1 个，那么称p 为d n k 异常。 如果对数据点根据它们的d k ( p ) g e 离进行排序，那么前n 个点就被看作异常。循环 嵌套算法( n e s t e d 1 0 0 p a l g o r i t h m ) 对每个点p ，计算它的第k 个最近邻的距离d k ( p ) ， 把具有极大d k 值前n 个点作为异常。上面的算法每次处理一个点p ，那么需要扫 描一遍数据库，总共需要扫描n 遍( n 为数据点数) 。基于索引的算法( i n d e x - b a s e d a l g o r i t h m ) 用如r 木树的空间索引结构存储。基于划分的算法( p a r t i t i o n b a s e d a l g o r i t h m ) 中，如果某个点的d k ( p ) 较小的话，那么不可能是d n k 异常，可以先 对数据集进行划分，然后估计每个划分的d k ( p ) 的上、下界，如果能判定某个划分 不可能包含异常的话，那么就可以直接把它删除掉；然后再用剩下的划分( 侯选 划分) 来计算异常。现有的许多聚类算法可以用来划分数据集，如b i r c h 。 基于距离的异常检测包含并拓展了基于统计的思想，即使数据集不满足任何 特定分布模型，它仍能有效地发现异常点，特别是当空间维数比较高时，算法的 效率很高。算法具体实现时，首先给出数据间距离的度量标准，常用的是绝对距 离( 曼哈顿距离) 、欧氏距离和马氏距离。 这种方法的缺点是对于所有的数据都采用统一的距离标准，而现实中数据很 可能会出现稀疏部分和稠密部分，他们之间应该采用不同的距离标准。其次，基 于距离的方法容易产生球形的聚类，而现实中聚类很可能有任意的形状。 2 2 6 基于密度( d e n s i t y b a s e d ) 的方法 基于距离的异常检测方法存在的问题是对所有的数据都采用同一标准进行判 断，而实际上，异常情况的判定在不同的局部情况下往往需要不同的标准。如图 2 2 中所示，c l 和c 2 两个聚类中的点就存在着不同的情况，如果采用一个较大的 距离标准认为c 1 中的所有点为正常，由于0 1 距离c 】和c 2 都大于距离标准，则被 识别成异常。但是，0 2 由于距离c 2 较近就会低于这个距离标准而当成正常数据来 处理。反之，如果采用一个较小的距离标准，把0 2 和0 l 都识别成异常，则由于c l 中的点十分稀疏将会有很大一部分数据也被识别成异常。因此，无论如何选择距 离标准，都无法适应全局需要。基于密度的异常检测算法一般都建立在距离的基 础上，某种意义上可以说基于密度的方法是基于距离的方法中的一种，但基于密 度的异常定义比基于距离的异常定义更贴近h a w k i n s 的定义，因此能够检测出基 于距离的异常算法所不能识别的一类异常数据局部异常。基于密度的方法主 电子科技大学博士学位论文 要思想是将数据之间的距离和某一给定范围内数据点个数这两个参数结合起来， 从而得到“密度”的概念，然后根据密度判定记录是否为异常点。 图2 2 不同密度数据中的局部异常 l o f ( l o c a lo u t l i e rf a c t o r ，对象的局部异常因子) 【3 9 j 算法是近年来最典型的 基于密度的异常检测算法。l o f 算法中，异常点被定义为相对于全局的局部异常 点，并给出异常程度对象的局部异常因子( l o c a lo u t l i e rf a c t o r ) ，局部异常的 性质对象p 的局部异常因子表示p 的异常程度，局部异常因子愈大，就认为它更 可能异常；反之则可能性小。簇内靠近核心点的对象的l o f 接近于l ，那么不应 该被认为是局部异常。而处于簇的边缘或是簇的外面的对象的l o f 相对较大。这 与传统异常定义不同，异常不再是一个二值属性( 要么是异常点，要么是正常点) ， 它摈弃了以前所有的异常定义中非此即彼的绝对异常观念，更加符合现实生活中 的应用。 鉴于l o f 的具有的优点，诸多学者在此基础上进行了研究和发展，并提出一 系列新颖的异常检测方法，如文献【4 0 、【4 1 、 4 2 、【4 3 】。其中，文献 4 0 提出了 三种l o f 的优化策略，分别称为l o f 。、l o f ”和g r i d l o f 。l o f 采用m i n p t s d i s t 代替本地可达密度，其中m i n _ p t s d i s t 表示数据点和m i n p t s 邻域( 与此数据点距离最 近的前m i n p t s 个点) 中所有点的距离，而本地可达密度代表数据点m i n p t s 邻域中 点的密度，替换后只需要一遍扫描就能够完成l o f 的计算，从而大大减少了l o f 算法需要两遍扫描的时间复杂度。l o f ”进一步对数据点的m i n p t s 值和数据点领域 中点的m i n p t s 分别赋值，能够更好的捕捉不同情况下的异常。g r i d l o f 引入了基 于网格的方法对非异常点进行剪枝，进而只需要计算剩余点的l o f 值，这样有助 于缩减数据点l o f 的计算时间。不过，由于剪枝后会影响剩余点l o f 值，可能会 1 6 第二 影响最终的检测结果。文献 4 1 】提出了一种有效的异常检测方法，能够检测出前n 个具有最大l o f 值的本地异常点，并大大缩减了l o f 值的计算时间。此方法既不 需要计算所有点的l o f 值，也不需要事先对数据点进行剪枝。在计算l o f 值之前， 首先进行聚类处理，将所有数据压缩成为微聚类( 聚类中点的距离很近) 的形式； 然后，计算每个微聚类中l o f 值的上界和下界，从具有最大l o f 值下界的微聚类 中检测最可能的r 1 个本地异常点。此方法的缺点是对于m i n p t s 值十分敏感。【4 2 】 提出了一种高效的异常检测方法c o f ( c o n n e c t i v i t y b a s e do u t l i e rf a c t o r ) ，且针对稀疏 数据集特别有效。此方法不仅考虑了数据点邻域中点的密度，同时还考虑了这个 点同其它点的连接程度。c o f 值由数据点和周围k 邻域中点的平均距离和所有k 领域点同他们的k 领域点平均距离的比值确定，具有最大c o f 值的点将被判定为 异常。为了去除m i n 地对检测结果的影响，【4 3 提出了一种快速检测算法l o c i ， 采用多粒度偏移因子( m d e f ) 来衡量数据的异常情况，其中数据点邻域不在是由 m i n p t s ( 与数据点距离最近的前m i n p t s 个点) 确定，而是由一个固定的距离半径 确定，所有与此数据点距离小于这个半径的点都属于它的领域。这样虽然能够去 除检测结果对m i n p t s 的依赖，但是引入了另外一个预设参数邻域距离半径， 这个参数的选择对于检测结果仍然存在很大的影响。 l o f 算法的缺点是需要事先定义最小邻域个数或邻域半径，这两个参数的选 取会极大的影响最终的检测结果，而正确的选取这些参数却是十分困难的。其次， 局部异常因子计算，对低维数据，可以利用网格( g r i d ) 来作k 小m 查询，整个计 算时间为o ( n ) ；对中维或中高维数据，必须采用索引结构如x 树等，使得作k - n n 查询的时间为o ( 1 0 9 n ) ，整个计算时间为o ( nl o g n ) ；对特高维数据，索引结构不 再有效，时间复杂度提高到o ( n 2 ) 。 2 2 7 基于神经网络( n e u r a ln e t w o r k b a s e d ) 的方法 神经网络常常应用于关键安全领域的回归预测和分类任务中，它能够自动对 底层数据的分布特征进行建模，同时区分正常和异常类别。近来，神经网络开始 广泛应用于异常检测领域m “5 1 。由于神经网络不需要对数据进行任何假设，只需 对正常数据进行学习后在输出层重构输入数据，如果重构误差较大则说明此数据 不符合建立的正常模型，将此类数据判定为异常。典型的方法包括文献 4 4 】、【4 5 ， 均采用回复式神经网络( r n n ) 构建重构模型，如图2 3 ，r n n 采用一个多层的 前馈式感知机神经网络学习数据的分布特征，然后再用一个相同的倒置网络重构 原来的学习模型，训练后大部分正常数据均只有较小的误差，少量存在较大误差 1 7 电子科技大学博士学位论文 的为异常数据。 1：345 图2 - 3 回复式神经网络结构 基于神经网络的异常检测方法严格上来说也是建立正常数据的分类模型，使 用神经网络模型不需要对数据进行任何的先期假设，而且能很好的发现数据中与 异常相关的关键属性，有效的发现数据中的异常。神经网络模型能较好地处理噪 声数据，能自动调节影响输出的各侧度的权重，而这在传统的异常检测方法中通 常是人为确定的。其不足之处在于对于神经网络模型参数的确定，如学习率、最 大迭代次数、收敛最小误差等，这些参数会对检测结果存在较大的影响。 2 2 8 基于支持向量机( s u p p o r tv e c t o rm a c h i n e b a s e d ) 的方法 基于支持向量机的方法在数据挖掘领域中常常用在回归问题和分类问题上。 近来，无监督支持向量机也开始应用在异常检测上m 瑚】，通过核函数它能有效的 发现数据中的异常。文献 4 6 使用径向基函数( r b f ) 将原始数据映射到一个特征空 间，在特征空间中的分布十分稀疏的点即异常点。文献 4 7 提出了一种基于无监督 学习的s v m 称为支持向量域描述( s v d d ) ，此方法采用高斯核函数对数据进行映 射，正常数据存在于特征空间中的一个超球体中，超球体边界上的点即支持向量， 而在此超球体之外的点都认为是异常点。文献【4 8 提出一种基于核函数和模糊集理 论的异常检测方法，其中使用模糊聚类代替超球体，将原始数据聚成多个类，再 使用一个连续的决策函数衡量每个点在各个聚类中的异常程度，当点的异常程度 超过某一阈值时，认为异常发生。 基于支持向量机的方法不需要对数据进行任何人为假设，也不需要任何预设 参数，但是核函数的计算通常需要耗费大量的计算，同时也难以确定合适的参数 来衡量特征空间中正常数据区域边界的大小。 总的来说，以上各异常检测算法，除基于统计的方法外，大多是基于数据挖 掘的思想，它们不需要对数据集的分布特征附加任何假设，而只需从数据集本身 第二章相关工作 出发对数据进行检测，发现其中包含的异常模式，这使得算法具有较大的可行性 和可移植性。上述的异常检测算法是以静态数据集为研究对象，并假定数据都集 中在同一位置，才能得到输出结果。在现实生活中，由于应用系统越来越庞大， 数据往往需要将海量的数据存放在不同的主机或地理位置，因此，对分布式的数 据集进行异常检测的需求更为迫切，基于数据挖掘的分布式异常检测正成为当前 的研究热点o 2 3 异常检测模型性能指标 异常检测算法的指标主要包括准确性指标和效率指标。准确性指标在很大程 度上取决于测试时采用的样本集和测试环境。样本集和测试环境不同，准确性也 不相同。效率指标主要是时间复杂度和空间复杂度指标。 大多数检测系统都以准确率作为性能指标，但是由于异常检测问题中异常通 常仅仅占到很小比例，而整个的样本空间常常超过上百万，因此，如果仅仅使用 准确率指标就会发生基率谬误( b a s er a t ef a l l a c y ) n 题。基率谬误也称为记录忽略 ( b a s er a t en e g l e c t ) ，指在统计中过分强调两个变量之间的依赖性而忽略了实际的样 本空间大小。举例来说，在入侵检测系统中，由于入侵仅仅占到各种网络连接流 量的0 1 ，因此一个将所有连接都判定为正常的检测器也能达到9 9 9 的准确率。 所以，对于异常检测系统而言，由于面对的应用中正常数据和异常数据数量十分 不平衡，因此采用的计算方法也不同。异常检测算法的准确性主要包括三个指标， 即精确率( p r e c i s i o n ) 、回召率( r e c a l l ) 和f v a l u e 。 精确率是指异常发生时，算法能够正确检查的概率，精确率的计算方法为： 精确率= 算法检测到的真正异常数量算法检测到的所有异常数量 回召率( 检测率、虚警率) 是指异常没有发生，而算法检查到发生异常的概 率，回召率计算方法为： 回召率= 算法检查到的虚假异常数量数据中实际异常数量 虽然准确率已经能够从一定程度上对检测结果进行评价，但是为了综合评价 系统性能将精确率和回召率结合后可得到f v a l u e 指标，其定义如下： 1 9 电子科技大学博士学位论文 表2 - 1 混淆矩阵( c o n f u s i o nm a t r i x ) 预测为正常预测为异常 实际上正常 t r u en e g a t i v e s ( t n )f a l s ep o s i t i v e s ( f p ) 实际上异常 f a l s en e g a t i v e s ( f n )t r u ep o s i t i v e s ( t p ) 精确率、回召率和f v a l u e 计算方法如下： 精确率( p r e c i s i o n ) = t p ( t p + f p ) 回召率( r e c a l l )= t p ( t p + f n ) f - v a l u e ：( 1 + , 8 2 ) r e c a l l p r e c i s i o n 8 。p r e c i s i o n 七r e c a l l ( 2 1 ) ( 2 2 ) ( 2 3 ) 其中为精确率和回召率的重要性参数，通常我们对二者公平衡量，因此，取值 为1 ，上式可变为： f - v a l u e 2 2 r e c a l l p r e c i s i o n ( 2 4 ) r e c a l l + p re c i s i o n f v a l u e 值越大说明系统的综合准确性能越好。 除了f v a l u e 之外，综合检测率和误报率还可以使用r o c 曲线和a u c ，图2 4 针对这两种指标进行了说明。a u c 是r o c 曲线和两坐标轴围成的区域面积，这个 面积越大检测准确性越高，r o c 理想情况下是图中沿坐标轴的红色曲线，此时a u c 也能获得最大值。 不同检测技术的r o c 曲线 检 测 塞 00 10 20 30 40 50 60 70 误检率 图2 - 4r o c 曲线和a u c 指标 第三章 3 1 研究动机 第三章 当前基于数据挖掘的异常检测方法主要针对集中式数据库的异常检测，并假 定数据存储在同一台主机中。由于现实中的应用系统越来越庞大，数据存储往往 需要在不同的主机，甚至不同的地理位置。在这种情况下使用集中式的异常检测 算法，需要首先对所有的数据进行集中采集。为了更清晰的说明分布式异常检测 和集中式异常检测的区别，我们可以利用图3 - 1 对二者的体系结构进行对比。 最终模型 ：牵 本地结果本地结果 本地结果 警警哼 【数据源】 数据源】【数据源 集中式异常检测 分布式异常检测 图3 - 1 集中式异常检测和分布式异常检测体系结构 为了更好的发展异常检测模型，需要大量的训练数据作为支持，常常需要多 个公司或组织之间进行合作。从图中可以看出，采用集中式异常检测时海量数据 的传输需要耗费大量的网络带宽和通信时间，往往是不能接受的。而采用分布式 异常检测技术直接共享由原始数据表示的本地结果，会侵犯各自的隐私权，通常 是不可行的。已有的分布式异常检测技术往往忽略了这一点，检测方法常常基于 原始数据的交换或共享。鉴于此，本论文致力于研究基于隐私保护的分布式异常 检测模型，以更好地满足分布式数据库中异常检测任务的需求。这样的需求来自 很多实际的应用领域中，举例说明如下。 例如，在网络安全中，入侵检测是对面向计算机资源和网络资源有恶意行为 2 1 电子科技大学博士学位论文 的识别和响应，对破坏资源完整性、机密性和可用性的行为进行检测，是主动地 进行安全防范。在网络信息中，那些入侵行为与正常行为相比往往存在异常，这 些异常就可能预示着入侵行为。违反安全策略的入侵信息相对于大量的正常通信 的信息来说，就是一些孤立的异常信息，是一些“小模式”，通过对这些异常信息的 分析，就能发现未经授权或恶意的网络攻击行为，大大增强网络的安全性。为了 能够从全局的角度考虑入侵检测问题，需要采集大量主机的网络连接数据进行分 析，然而，这些数据来源于不同的主机很可能属于不同组织，不同单位，不同地 区甚至不同国家，将所有数据进行采集后统一进行分析的可能性几乎没有，因此， 建立完善的入侵检测系统就成为一个难题，从基于隐私保护的分布式异常检测的 角度出发，就能很好解决这个问题。此时，各个主机之间的异常检测能够在本地 进行，而积累起来的知识能够以模型的方式相互共享，既安全又快速地完成了全 局异常检测的任务。 又如，在市场销售分析中，商家不仅关注中层收入客户的需求情况，将对这 部分消费人群作为研究的对象，根据分析结果制定相应的销售策略，更关注对众 多客户中的少数极低或极高收入客户韵消费行为进行分析，因为，往往这部分客 户包含更大的消费潜力或盈利空间，一个极高收入客户一次消费所带来的利润相 当于几位或几十位中层收入客户的利润。而挖掘这样的客户需要针对大量客户交 易数据进行分析后才能发现，由于大型销售商家之间存在着消费者资源的竞争， 共享这样的交易数据往往害怕商业机密的泄漏，而为了更好地增加销售收入，各 商家又希望能够相互合作。在此情况下，一方面要保证商家的数据私有性，另一 方面要将所有数据中蕴含的知识进行共享。 3 2 相关工作 为了解决海量分布式环境中的异常检测问题，很多学者对之进行了研究，他 们从传统异常检测方法出发，提出了一系列改进方案应用于分布式环境中【4 ”引。 而分布式异常检测技术仍然需要统计各站点的本地信息，直接共享或交换原始数 据会侵犯各自的隐私权，通常是不能接受的。存在的分布式异常检测技术往往忽 略了这一点，检测方法常常基于原始数据的交换或共享。近年来，随着数据挖掘 中的隐私问题越来越受到人们的重视，基于隐私保护的数据挖掘【5 4 j 成为一个新的 研究热点。针对分布式环境下的异常检测中的隐私保护问题也有了一些研究成果， 如文献 4 9 1 等提出了一种基于“安全和”方式的分布式异常检测方法，采用半信赖 第三章分布式异常检测 在此基础上文献【5 0 提出一种加入数据干扰的 的多方安全计算模式保护用户隐私。 分布式异常检测方法，仅仅交换那些超出局部阈值距离的数据信息，并随机加入 少量正常数据信息作为干扰。文献 5 1 也提出一种混合属性数据中基于属性独立性 和协方差矩阵的分布式异常检测方法，类似的工作还有基于核密度的方法1 52 1 ，基 于距离的方法【5 3 1 。这些方法虽然能够有效的检测分布式数据集中的异常点，但是 或多或少地需要对原始数据信息如距离、边界或相关性信息进行共享。这些信息 的共享增大了敏感数据被泄露的可能性，使得隐私保护的效果也逐渐减弱。 鉴于此，本论文提出一种基于模型共享的分布式异常检测方法，采用交换本 地数据挖掘模型的方式来实现数据的隐私保护。由于很多数据挖掘模型，如神经 网络、支持向量基等都以黑盒的形式存储数据中的模式信息，因此，能够更好地 保护原始数据的隐私性。 3 3 问题定义 令x ：锄，而，工。) c 表示d 维空间中的未知标签数据集，其中任意第i 个数 据x ，由一个d 维的特征向量k l ，x f ，2 ，x f 3 ，托胡表示。异常检测模型就是用来对数 据集中所有数据进行检测，得到任意第f 个数据的异常分( 异常程度) 么s ，并为 之分配一个标签乃 另旃踊。因此，异常检测模型也可形容为一个函数，_ 九，它将未知数据集x = 缸1 ，工2 ，) 映射到了一维的标签向量九 九l ，坨， k ) ，其中，五 异旃正扔，卢1 ，m 。 基于隐私保护的分布式异常检测框架如图3 - 2 所示： 2 3 电子科技大学博士学位论文 图3 - 2 基于隐私保护的分布式异常检测框架 本论文提出的基于隐私保护的分布式数据挖掘框架采用集成学习( e n s e m b l e l e a r n i n g ) 的方法，假设数据集分布于刀个不同的地理位置( 不同主机) ，其中任意 的第_ ，个位置存储的本地数据集s 包含小，个数据记录，j = l ，以。并且分布于各 地的数据集中的数据均含有相同的属性集，不过每个本地数据集含有的数据记录 个数可能不同，并且由于传输消耗和隐私等原因无法收集到一起进行集中式的异 第三章 常检测。在此情况下，本论文提出的分布式异常检测的策略是在任意的第，个位置 ( ，= 1 ，珂) ，都利用本地拥有的数据集s 建立一个异常检测的本地模型m ，并且 这些本地模型能够将本地数据集中的记录合理的映射为其检测后的异常分斛) 和 标签向量。所谓合理的映射，即映射的异常分和数据的异常程度能够吻合，标 签向量和事实吻合。然后，将得到的本地模型进行共享，使得在任何一个地方都 能够得到所有的本地模型。当一个新的需要进行预测的数据集r 出现时，在任意 位置对数据集丁应用共享的所有的本地异常检测模型，由于本地数据集之间的差 异性，这些模型将得到不同的检测结果。此时，采用集成学习的思想，对得到的 不同结果进行合成，就能够得到全局检测后的最终异常分a s f 和最终数据标签九。 下面将对基于集成学习的分布式异常检测模型融合技术进行详细介绍。 3 4 集成学习与异常检测 集成学习是近年来机器学习领域的研究热点之一，通过训练多个弱学习系统 并将其结果按一定方式进行组合，可以显著提高学习系统的泛化能力。早在1 9 9 7 年，国际机器学习界的权威t g d i e t t e r i c h 就将集成学习列为机器学习四大研究 方向之首【5 5 】( 机器学习的研究主要分为四个方向，即通过集成学习方法提高学习精 度、大规模学习、强化学习和学习复杂的随机模型) 。国际上很多研究者都投入到 集成学习的研究中，理论和应用成果不断涌现，如b a g g i n g 5 6 j 、b o o s t i n g 【5 川、 a r c i n g 5 8 1 、r a n d o mf o r e s t1 5 9 1 。 在机器学习领域，最早的集成学习方法是b a y e s i a na v e r a g i n g 。在此之后，集 成学习的研究才逐渐引起了人们的关注。然而，集成学习之所以能够迅速上升为 机器学习研究方向之首，要归功于下面一些入所做的重要工作。 首先，l k h a n s e n 和ps a l a m o n l 6 0 蝌对一组神经网络模型进行集成学习，除了 按常规的做法选择出最好的神经网络之外，他们还尝试通过投票法将所有的神经 网络的结果集成进行求解。直观上来看，一组神经网络中既有效果比较好的个体， 也有比较差的个体，那么将他们集成后，其总性能应该介于个体模型的最优性能 与最差性能之间。然而，他们的实验结果表明，集成后的神经网络比最好的个体 神经网络的性能还好。正是这一超乎人们直觉的结果，使得集成学习引起了很多 学者的重视，在2 0 世纪9 0 年代前半段，集成学习技术被用到很多应用领域中， 并取得了相当好的效果。 其次，s c h a p i r e 和f r e u n d 的工作。为了回答弱学习算法与强学习算法是否等 电子科技大学博士学位论文 价的问题，1 9 9 0 年s c h a p i r e 通过一个构造性方法证明了多个弱分类器可以集成为 一个强分类器，他的工作奠定了集成学习的理论基础。这个构造性方法就是 b o o s t i n g 算法的雏形。在1 9 9 5 年，f r e u n d 和s c h a p i r e 作了进一步工作，提出了 a d a b o o s t 算法，该算法不再要求事先知道泛化下界，可以非常容易地应用到实际 的问题中去。1 9 9 6 年，b r e i m a n 提出了与b o o s t i n g 相似的技术b a g g i n g ，进一步促 进了集成学习的发展。 集成学习是一个迅速发展中的研究领域，从其出现到目前为止，短短十几年 的时间，它已经广泛应用于语言识别、文本过滤、遥感信息处理、疾病诊断等众 多领域。但是，如何设计出更有效的集成学习实现方法，以提高集成学习的泛化 能力，并将集成学习应用到实际问题领域中取得很好的效果，仍然是集成学习研 究的热点问题。尤其是2 0 0 1 年z h o u t 6 1 】等人提出了“选择性集成概念后，在国 内外引起了很大的反响，把集成学习带入了一个崭新的发展阶段，使得人们从更 深的层次、更广大的领域对集成学习展开了进一步的研究。集成学习的基本思想 是用多个模型( 解决方案) 来解决同一个问题。它在异常检测中的作用主要体现在以 下四个方面。 ( 1 ) 提高检测结果的准确性 异常检测的一个重要目标就是对新的测试样本尽可能给出最精确的检测结 果。构造单个高精度的检测模型是一件相当困难的事情。然而产生若干个只比随 机猜想略好的检测模型却很容易。研究者们在应用研究中发现，将多个检测模型 进行集成后得到的检测精度明显高于单个检测模型的精度，甚至比单个最好的检 测模型的精度更高。 ( 2 ) 提高检测结果的稳定性 有些检测算法模型单一的检测结果时好时坏，不具有稳定性，不能一直保持 高精度的检测。例如，全球极端恶劣天气异常检测系统来说，一个模型对于某一 个地区的极端天气预测可能很好，但是对于其它地区来说，可能这个模型就不再 准确，而在别的地区使用另外的模型效果就会很好。通过这些检测模型的集成， 可以很好地在全球范围内以较高的准确率普遍取得很好的检测结果。 ( 3 ) 解决过适应问题 在对己知的数据集合进行异常检测模型训练的时候，我们常常选择适应度值 最好的一个检测模型作为最后的结果。因为选取的训练集永远都只是整个数据集 的一部分，也许我们选择的模型能够很好的解释训练数据集合，但是却不能很好 的解释不在训练集中的测试数据或者其他数据。也就是说，虽然这个检测模型精 第三章分布式异常检测 细的刻画了训练数据中的正常数据，但对于测试数据或者其他新的数据泛化能力 不强，这种现象就称为过适应。 为了解决过适应问题，按照集成学习的思想，可以采用多个检测模型在训练 集的不同子集上进行训练，并对每个模型赋予不同的权重，当新的数据集到来时， 根据权重合成所有模型的输出结果，这样大大提高了模型的泛化能力并提高了预 测精度。 ( 4 ) 改进参数选择 对于一些异常检测算法而言，如神经网络、遗传算法，在进行异常检测的时 候，需要选择操作参数。但是这些操作参数的选取没有确定性的规则可以依据， 只能凭借经验来选取，对于非专业的一般操作人员会有一定的难度。模型参数选 择不同，结果会有很大的差异。通过建立多个不同操作参数的检测模型，可以解 决选取参数的难题，同时将不同模型的结果按照一定的方式使用集成学习就可以 得到我们想要的结果。 ( 5 ) 提供数据隐私性 对于分布于多个物理位置的数据集来说，集中式的训练方式需要大量的数据 传输，同时需要将原始数据输入到统一的训练模型中。这样的做法不仅耗费大量 网络资源，同时耗费大量的计算时间，尤其严重的是当分布于各地的数据集属于 不同机构时，原始数据的搜集过程严重侵犯了各个数据提供商的数据内容私有性。 如果采用集成学习的方法，分别在各地由提供商自己训练各自的检测模型。然后， 将这些模型进行共享，在新的数据集上应用多个检测模型并采用集成学习的方法 合并最终检测结果，仍然能够从全局的角度出发精确的检测出异常情况。同时， 这样做不仅大大减少了数据传输量，而且由于检测模型本身的抽象性和高概括性 能有效的保护各数据提供商的数据隐私性。 当前对集成学习的研究主要包括两个方面：第一，如何设计出更有效的集成 学习实现方法，以提高集成的泛化能力，并将集成应用到实际问题域中取得很好 的效果；第二，对集成学习进行理论分析，以探明这种方法为何有效，在何种情 况下有效，从而为实现方法的设计提供指导。其中，对集成学习实现方法的研究 又主要集中在两个方面，即怎样将多个弱学习机的输出结论进行结合，以及如何 生成集成中的学习机。基于集成学习的异常检测可分为两个步骤，一个是弱检测 模型的构建，另一个是弱检测模型的合成。在分布式异常检测中，分别对应为本 地异常检测模型构建和最终异常检测结果的合成。由于弱检测模型的构建可分为 有监督学习和无监督学习两种，而各种学习方法具有不同的构建特性，因此，对 2 7 电子科技大学博士学位论文 应于不同的弱检测模型本论文分别采用了不同的集成方法。下面将针对各种不同 类型弱检测模型分别描述其分布式异常检测方法。 3 5 基于有监督学习的分布式异常检测 利用一组己知类别的训练样本调整弱检测模型的参数，使其达到正确识别训 练集中的异常和正常数据的过程，也称为基于监督训练或有教师学习的异常检测。 正如人们通过已知病例学习诊断技术那样，异常检测模型要通过学习才能具有识 别正常数据和异常数据的能力。用来进行学习的材料就是已经具有正确标签的训 练集中的有限数量样本。监督学习中在为弱检测模型提高学习样本的同时，还告 诉弱检测模型各个样本所属的正确类别。如果当前的弱检测模型识别错误，有监 督学习机制就自动调整弱检测模型的参数，直n t ) i l 练集中的所有样本能够正确识 别或识别错误率小于给定的范围时学习终止。基于半监督学习的异常检测也属于 有监督学习的一种，但是半监督学习提供的训练数据仅包含正常的训练样本，也 就是说训练集中的所有数据标签都是正常的，检测模型仅仅学习正常数据的特征， 凡是不满足这个特征的都被认为是异常数据。基于有监督学习的异常检测算法很 多，下面将介绍本工作中涉及到的各种有监督学习异常检测算法。 3 5 1 基于有监督学习的异常检测算法 本论文一共研究了八种基于有监督学习的异常检测算法，分别介绍如下： ( 1 ) m i n i m u mc o v a r i a n c ed e t e r m i n a n t 该算法【6 2 】提出一种具有高鲁棒性的快速多维数据协方差估计方法。通过选取 整个数据集中的子集对整个正常数据的协方差进行估计，当估计协方差行列式值 达到最小值时估计值就逼近了实际值，这种协方差估计方法，不仅速度快而且能 够去除m a h a l a n o b i sd i s t a n c e ( 马哈朗诺比斯距离) 对于多异常点的掩盖效果。欧 氏距离的计算中，多维数据各个维度对距离的贡献是相等的，然而在异常检测中 我们希望寻求这样一种距离，它的各个分量的作用程度是不同的。因为整体上的 异常与单一维度上的异常相比更能体现数据异常的程度，因此差别较大的分量应 该接受较小的权重。马哈朗诺比斯距离( 马氏距离) 的定义如下： m d ( x ) = ( x 一) 7 ( x 一) ( 3 1 ) 其中j 表示样本数据，为数据的中心点，表示数据的协方差。当数据中 仅有一个异常点时，基本能够代表整个正常数据的协方差，但是当异常点有多 个时， 遮盖效果 应用 点的马哈 ( 2 ) 该方 其中p 为混合的高斯函数数量，x 代表样本点，为数据的中心点，表示 数据的协方差。当数据的触) 值小于某一阈值时，认为此数据点发生的概率很小， 不符合己建立的正常数据分布规律，因此，将被判定为是异常。 ( 3 ) k - c e n t e r sa p p r o a c h 该方法眦1 和k - m e a n s 类似，采用簇的方式对正常数据建模，不同的是目标函 数的定义，k - c e n t e r s 的目标函数如下： m 。i n 。m ，a x m a x ( x 一以) 2o 一版) ( 3 - 3 ) o = i 乍l 其中，。为第七个簇中的点，虽然也称为中心，但是并不一定像k - m e a n s 那 样真正代表簇的中心，它可能为簇中任意的样本点。 ( 4 ) k - n e a r e s tn e i g h b o r 该方法【3 8 】在对正常数据进行簇的建模时采用的思路是：如果一个样本在特征 空间中的k 个最相似( 即特征空间中最邻近) 的样本中的大多数属于某一个簇，则该 样本也属于这个簇。州算法中，所选择的邻居都是己经确定簇的样本，该方法 在对样本点簇的划分上只依据最邻近的一个或者几个样本的所属的簇来决定待分 样本所属的簇。判定异常的方法和k m e a n s 还有k c e n t e r s 相同。 ( 5 ) a u t o e n c o d e rn e u r a ln e t w o r k s 此方法f 6 5 】也称为回复式神经网络，神经网络模型中具有相同数量的输入和输 出神经元。在对正常样本数据学习后，再使用相同的网络结构对样本进行重构。 当网络的重构误差达到较小的级别，训练终止。在进行异常检测时，将数据输入 训练好的网络中，如果重构误差大于预设的阈值，则认为异常发生。 ( 6 ) s u p p o r t v e c t o rd a t ad e s c r i p t i o n ( s v d d ) 基于支持向量机【6 3 】的异常检测根据数据的标签建立一个两类的分类器，支持 向量机的主要思想可以概括为两点：首先，它是针对线性可分情况进行分析，对 于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样 2 9 电子科技大学博士学位论文 本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样 本的非线性特征进行线性分析成为可能；其次，它基于结构风险最小化理论之上， 在特征空间中建构最优分割超平面，使得分类器得到全局最优化，并且在整个样 本空间的期望风险以某个概率满足一定上界。进行异常检测时，将测试数据输入 到已经训练好的分类器中，根据分类结果判定数据是否是异常。 ( 7 ) m i n i m u ms p a n n i n gt r e e ( m s t ) 该方法f 蛔利用最小生成树算法在训练数据上建立一个树形结构，边的权值由 数据之间的距离决定。由于正常数据之间的距离应该远远小于正常数据和异常数 据之间的距离，算法需要去除一条边，并尽量使得剩下的表示正常数据的最小生 成子树包含尽量多的正常点，同时，这颗子树的边权值总和具有较小的值。当新 的数据到来时，寻找与它距离最近的节点，如果这个节点属于正常数据表示的最 小生成树，则此数据为正常，反之为异常。 ( 8 ) m i n m a xp r o b a b i l i t ym a c h i n e 该方法【6 7 】在训练数据上建立一个线性分类器，最大程度的包容正常数据，同 时区分出异常数据。分类器拒绝率的设定可以通过分析数据的均值和协方差来估 计，但是对于大规模数据来讲这些参考值往往计算复杂而且易受到其它因素影响， 所以大部分情况仍需要多次实验来尝试。 第三章分布式异常检测 3 5 2 基于模型交换的有监督学习分布式异常检测技术 训练训练训练 本地异常检测模型本地异常检测模型 本地异常检测模型 审审审 00j 怿鬟一怿器怿纠 0 、 边界扩展 多数边界平均距离 v 投票扩展叠加加权 基于模型差异性的 集成学习 最终异常分a s r 髅鳓岁研4 图3 3 基于有监督学习的分布式异常检测框架 为了研究集成学习在分布式异常检测中的作用，基于提出的检测框架，本论 文采用了五种不同的集成学习方法，并提出一种基于模型差异性的集成学习方案 与其它四种进行对比，如图3 3 。 ( 1 ) 多数投票 电子科技大学博士学位论文 多数投票机制的应用十分广泛，例如在经济学中，表示的是股东运用手中的 股票数，每股代表一票，分别对每个候选董事进行购票，如果某股东拥有1 0 0 股， 则可以对每个候选董事投1 0 0 票。从而按得票数的高低依次选出新董事的选举制 度。 如果大股东拥有2 0 0 股，那么则可以对每个候选董事投2 0 0 票，这样大股东 会控制董事会的选举。因此多数投票制会排除少数股东的参与机会，这就是美国 许多州强制采用累计投票制的原因。 在人们的日常生活中也是如此，人们炒股时购买多只股票后盈利的概率往往 大于购买一只股票；生活在社区中的人们往往采用多数投票来决定一项制度的执 行与否，而不是某个人的独断专行。 在分布式异常检测的集成学习中，将每个本地异常检测模型当成是程序委员 会中的一员。由于本地数据集的差异性，训练出来的本地异常检测模型也不相同， 因此，他们的检测结果也不同。对这些检测器预测的数据标签进行投票，将占多 数的标签值作为最后的预测结果。需要说明的是在多数投票中，为了保证结果的 唯一性，本论文通常采用奇数个本地模型进行投票。 ( 2 ) 边界扩展 在基于有监督学习的异常检测模型中，大部分基于半监督学习的算法都只建 立正常数据的边界模型，如果数据处在这个边界之内就属于正常数据。鉴于此， 本论文采用边界扩张的方式，只要其中一个本地异常检测检测模型的输出确定此 数据为正常，就扩展整个正常区域的范围，认为此数据是正常的。这样能够大大 提高识别正常数据的准确率，但是从另一个角度来看，这样做同样也大大增加了 将异常点识别为正常的可能性，因此，也提高了误判率。 ( 3 ) 平均叠加 由于多数投票机制仅仅利用本地模型的预测标签，因此，检测结果只有0 或 者1 两种情况，而对于检测后输出的异常分来说，可能是o l 之间的任何实数。 故，异常分向量对异常情况的描述比异常标签更加精细。为了充分利用本地异常 检测模型的结果，本论文对本地异常检测模型输出的异常分和异常阈值采用平均 叠加的方法，如果叠加后所有本地模型输出的平均异常分大于平均异常阈值，则 判定为异常，反之，为正常数据。 ( 4 ) 距离加权 在平均叠加方法中，每个本地异常检测模型的权值是相同的，即地位是平等 的。在实际应用中，如果一个测试数据和某个本地数据集的数据比较接近，那么 3 2 第三章分布式异常检测 这个数据集就应该在最后的集成中具有较大的权重。为了判定数据和本地数据集 的接近程度，本论文采用本地模型输出的异常分作为依据。对于越接近的本地数 据集，对应模型的异常分应该越小，鉴于此，本论文利用异常分作为权重，对各 个本地模型的预测标签进行加权求和，如果最终的加权值接近于l 则为异常，反 之为正常。 ( 5 ) 基于模型差异性的集成学习 。 当收到全部的模型后，我们能够构建一个总体的集成学习模型，从全局的观 点出发检测全局的异常，同时降低检测误报率。集成学习的模型采用加权投票的 方式确定一个行为是否是真正的全局异常，由于每个共享模型给出的结果不同， 需要给每个模型分配恰当的权重才能获得准确的异常检测结果。模型合并的问题 考虑的主要因素是各个模型的差异性，通常认为差异性越大的一组模型给出的结 果越接近现实，衡量模型之间的差异性可以采用多个不同的标准，本文中定义了 四种不同的差异性标准，分别是m u t u a li n f o r m a t i o n ( m i ) 娜】、 a d j u s t e dr a n di n d e x ( a r ) 【6 9 1 、j a c c a r di n d e x ( j a ) 1 6 9 】和f o w l k e s m a l l o w si n d e x ( f m ) 【7 0 1 。 1 ) m u t u a li n f o r m a t i o n ( m i ) 。 如果一个混合模型能最大程度的获得各个模型提供的信息，那么这个混合模 型就具备了最好的权值分配策略。鉴于此，定义如下的互信息标准：a 和b 对应 于两个数据挖掘共享模型，对于一个当前发生的网络行为，它们判定的结果分别 记为九汹和九御。假定一共有n 个新的网络行为发生，模型a 预测其中有盯个正 常数据，和肜个攻击数据，而模型b 认为其中有的正常数据和攻击分别为彬和 膨个。同时有矽个数据被两个模型同时检测为攻击，那么模型a 和模型b 的互信 息定义如下 i ( a ，b ) = n 1 d l o g ( 器) + ( 卅肿。敷警+ ( 1 6 卅) 1 。甙帮) + 2 曲l o 喏磊) ( 3 4 ) 为了计算方便，将它规范化到 0 ，1 区间，以舢表示： n m ( 4 ，b ) ：声丝丝一 眵5 ) 挣