单分类算法中的数据可视化技术
第23卷第5期2008年9月数据采集与处理Jou rnal of D ata A cqu isiti on &P rocessing V o l . 23N o. 5Sep.
2008
文章编号:100429037(2008) 0520600204
单分类算法中的数据可视化技术
丁 力 缪志敏 潘志松 倪桂强 胡谷雨
(解放军理工大学指挥自动化学院, 南京, 210007)
摘要:通过对可视化技术的分析, 设计了单类分类器的可视化方法, 将单分类异常检测算法过程在二维空间表述出来。通过对国际标准数据集进行试验, 可视化过程显示了分类算法的核参数对分类面的影响。将单类分类器的可视化方法应用于主机系统调用序列的异常检测中, 可以将入侵检测过程呈现给用户, 能够有效地发现入侵行为, 有助于更好地理解单类分类器在对用户的系统调用执行序列分析的效果。关键词:单类分类器; 数据可视化; 异常检测中图分类号:T P 391 文献标识码:A
Da ta V isua l iza tion for One -Cla Cla ica D ing L i , M iao Z h i m in , P an Z , i , u
(In stitu te of Comm and A u tom ati on , PLA U logy , N an jing , 210007, Ch ina )
Abstract :T he one 2class on on algo rithm is exp ressed in the tw o 2di 2m en si onal sp logy analysis and a visualizati on m ethod is designed . T u sers of the one 2class classificati on system call on the i m 2. B y testing the in ternati onal standard data sets , the visualiza 2p lem analysis
ti on on algo rithm dem on strates the effect of key p am ram eters of the classificati on al 2go rithm on the classificati on su rface . B y i m p lem en ting the visualizati on m ethod of the one 2class classificati on in the calling sequence fo r the m ainfram e system anom aly detecti on , the p rocess of in tru si m detecti on system s (I D Ss ) can be p resen ted to u sers , the in tru ti on can be detected . T hu s , it is u sefu l fo r understanding the one 2class classificati on on the system calling analysis . Key words :one 2class classifier ; data visualizati on ; anom aly detecti on
目前, 大部分的分类算法通常将注意力集中在
引 言
可视化技术的最早提出源于科学计算可视化(V isualizati on in scien tific com p u ting , V ISC ) 的提
如何提高算法的分类能力上. 由于数据挖掘技术和机器学习方法只需要用户简单的输入数据, 数据预处理、特征选择和分类聚类过程对于用户来讲都是“黑箱”操作的, 很少涉及用户可视化, 忽略了数据可视化和分类结果的可理解性方面的研究。可视化技术能够充分利用人的认知能力, 将人的认知能力与计算机的计算能力结合起来, 从图形显示中发现大规模数据中存在的其他学习方法难以识别的未知的特征和模式, 并从中提取出隐含的知识并加以理解。因此, 可视化技术作为机器学习和数据挖掘算法的合理补充, 将能在分类结果的可理解性、交互性、学习过程中的动态特性等方面发挥出特殊的作用。
本文通过可视化技术将单分类异常检测算法
出。它是发达国家在20世纪80年代后期提出并发展起来的一个新的研究领域。所谓“科学计算可视化”, 就是应用计算机图形学和图像处理技术, 将科学计算过程中产生的数据及结果, 转换为人们容易理解的图形图像格式, 在屏幕上显示出来。这些图像可以将大量的抽象信息有机地组织在一起, 并形象生动地显示数据所表示的内容及其之间的关系, 从而使许多抽象的、难于理解的原理和规律变得直观简单, 许多繁杂而枯燥的数据变得生动有趣。
基金项目:国家自然科学基金(60603029) 资助项目; 江苏自然科学基金(BK 2005009) 资助项目。 收稿日期:2007204204; 修订日期:2007206211
第5期丁 力, 等:单分类算法中的数据可视化技术601
过程在二维空间表述出来, 有助于更好地理解单类分类器在对用户的系统调用执行序列分析的效果。试验部分首先对国际标准数据集进行试验, 可视化过程显示了分类算法的核参数是如何影响分类面的形成的。然后, 将可视化技术应用于主机系统调用序列的异常检测中, 不但可以将入侵检测过程呈现给用户, 使用户可以通过直观的感觉来指导算法参数的调整, 使其能够有效地发现入侵行为, 而且能够增进用户对检测结果的理解。
表达式为
M j =
N
N
∑x
i =1
ij N
i =1, 2, …, N j =1, 2, …, 41(1)
ij
C j =
N -1
∑(x
i =1
-M j )
2
2
i =1, 2, …, N
(2) (3)
j =1, 2, …, 41
i =1, 2, …, N j =1, 2, …, 41X ij =
C j
1 单类分类器的可视化模型
111 基本思想
在现实生活中, 经常遇到只知道一类事物的情
况, 并利用这一类事物的知识识别自己和非己。单类问题即是假定只有目标类的信息可以被获得, 而没有其他类信息可用。对于这种情况, 。
(rt vecto r data de 2
[1]
scri p ti on ) 作为生成可视化的分类面的工具。由于样本通常具有高维特性, 如果要想在二维或三维空间可视化就必须要降维。由于可视化需要在低维空间上显示数据点的结构, 而现实世界中的数据往往具有高维的特点, 因此很多维数约简技术被提出来以解决降维问题, 使得用户能够更好地分析与显示复杂的数据集。维数约简问题可以形式化地表示为:给定p 维随机变量x =(x 1, …, x p ) T , 根据某些准则发现其低维表示s =(s 1, …, s k ) T , 其中k ≤p , 使得s 能够正确描述原始数据的信息。
常用的维数约简技术包括SOM (Self 2o rgan iz 2
[2]
ing m ap ) , PCA (P rinci p al com ponen t
[3][4]
analysis ) , M D S (M u ltidi m en si onal scaling ) ,
[5]
CCA (Cu rvilinear com ponen t analysis ) , I CA (In 2
[6][7]
dep enden t com ponen t analysis ) , Isom ap 以及LL E
式(123) 中:M j 为j 列的均值; C j 为j 列的方差; X ij 为归一化后的新数值。
可视化步骤:
(1) 输入:根据输入数据集D 生成归一化矩阵
M ;
(2) M , 形成M ′;
M ′进行训练生成分类和半径R ;
(4) 根据用户要求, 将网格点细分, 生成m ×n 的二维点阵G ;
(5) 令G ij =z , 利用公式
‖z -a ‖2=K (z z ) -2∑Αi K (z x i ) +
i
2 ∑Αi Αj K (x i x j ) ≤R
i , j
(4)
式中:a 为球中心; Αi , Αj 为拉格朗日乘子; 核函数采用RB F 核, 即
K (x , y ) =exp -256Ρ2
(6) 对所有网格点进行判断, 得到判别矩阵L
L (i , j ) =
0 ‖z -a ‖2≤R 21 ‖z -a ‖≥R
2
2
(5)
(7) 通过等高线函数对判别矩阵绘制分类面;
(8) 检测新的样本:在可视化图中, 在分类面之内的样本为正常类,
在分类面之外的样本为异常, 从而实现基于可视化的异常检测。
2 数据可视化结果
211 数据集描述
实验中首先通过对一个标准数据集实现单类分类问题的可视化。然后采用了安全审计中的6切分条件下的系统调用执行迹数据集实现可视化, 并选择其中具有代表性的512个正常与13个攻击数据。
等。PCA 算法由于能够在映射过程中尽可能地保留原数中点的结构信息, 本文选择PCA 作为由高维空间向低维空间映射的工具。
[8]
112 二维空间的单类分类可视化
为了能够在二维空间实现单类分类面的构成, 就必须要构成一个判别矩阵, 对所有二维网格中的点进行分类, 形成的判别矩阵后, 就可以绘制分类面了。然而由于网络数据特征中某些维较大, 在对其进行主分量投影之前, 需要对数据进行归一化,
212 可视化的实验与分析
2. 2. 1 香蕉型数据集
香蕉型数据是二维空间典型的线性不可分的人工数据集。
602数据采集与处理第23
卷
图1是在C =011不变的情况下, 调整Ρ=1~6的可视化结果。图中“3”号代表正常数据; “+”号代表异常样本; 黑色的边界代表分类面, 该分类面是利用“3”号代表的正常样本训练的单类分类器产生的。由图1可得:当Ρ=1时, 分类面没有形成, 分类器主要关注的是当前训练样本的分类精度; 当
Ρ逐渐增大时, 分类器在包括所有的正常样本的基础上, 逐步提高了泛化性能; 当Ρ=6时, 分类器包含了一些异常样本, 这说明RB F 核参数调整过大; 通过可视化的结果可以得到Ρ合适的值为5。在Ρ=5的情况下, 再次调整C 值结果如图2所示。由图2可得, 当C =1 25时,
分类面和支持向量
图1
单类分类器分类面可视化
图2 C 不断调整的单类分类器分类面可视化
第5期丁 力, 等:
单分类算法中的数据可视化技术603
的个数达到了最优。通过对香蕉型数据集进行实验, 可以看出利用可视化结果可以动态地分析出异常检测分类面随着参数变化而改变的情况, 可以通过更加直观的视角来分析多个参数变化的试验结果。2. 2. 2 安全审计中的系统调用执行序列数据
采用安全审计中的系统调用执行序列数据, 本文得到了6切分条件下的512个频繁发生的正常样本, 按照112节中的可视化方案进行数据可视化, 可以得到二维空间的分类面, 如图3所示。
由图3可以看到分类面基本包括了所有频繁发生的用户系统调用的短序列, 对异常样本也有较高的检测率。虽然不能包含所有的正常样本, 短序列个数在整个系列个数中占的比例的调整, 可以进一步修正单类分类器的分类精度
。
法, 介绍了可视化技术在网络异常检测中的应用, 并设计了基于单类分类算法的可视化方法。该方法利用O ne 2class 方法映射到二维可视空间中, 将高维空间降维后的分类面直观地呈现给用户, 使用户能够从中发现有价值的可视信息。利用基于单类的可视化方法, 还可以在不预先知道攻击数据特性的情况下, 通过样本在二维空间的投影, 简单地通过和可视化分类界面的比较发现对网络的攻击行为。另外, 可视化结果还可以动态地显示分类器的参数对分类面的影响。实验结果表明, 可视化技术可以更清晰地发现网络数据中的聚类特性, 从而为用户提供更加直观的可视化信息, 使用户能够对正常样。
:
[1]D J T . classificati on [D ]. N ether 2
D n iversity of T echno logy , 1999. [T . T he self 2o rgan izing m ap [J ]. P roceed 2
ings of the IEEE , 1990, 78(9) :146421480. [3] Jo sh i M , Kum ar V , A garw al R . Evaluating boo st 2
ing algo rithm s to classify rare classes :comparison
and i m p rovem en ts [C ] P roceedings of the 1st IEEE
In ternati onal Conference on D ata M in ing . W ash ing 2ton DC :IEEE Compu ter Society , 2001:2572264. [4] To rgerson W S . M u ltidi m en si onal scaling I :theo ry
and m ethod [J ]. P sychom etrika , 1952, 17:4012419. [5] D em artines P , H erau lt J .
Cu rvilinear componen t
analysis :a self 2o rgan izing neu ral netw o rk fo r non lin 2ear m app ing of data set [J ]. IEEE T ran sacti on s on
N eu ral N etw o rk s , 1997, 8(1) :1482154. [6] H yvarinen A .
942128.
[7] T enenbaum J B , V in de Silva , L angfo rd J C . A
global geom etric fram ew o rk fo r non linear di m en si on 2ality reducti on [J ]. Science , 2000, 290(12) :231922323.
[8] Row eis S T , Sau l L K . N on linear di m en si onality
analysis by locally linear em bedding [J ].
2000, 290(12) :232322326.
Science ,
Su rvey on independen t componen t
analysis [J ]. N eu ral Compu ting Su rveys , 1999, 2:
图3 单类分类器对安全审计中系统调用短系列分类
面可视化
需要指出的是, 在单类分类器的异常入侵检测中运用可视化技术的目的是增进用户对单类分类器工作情况的了解, 使得用户能够根据具体的情况选择不同的分类器参数, 并对检测过程提供指导, 以及充分理解异常检测的结果。同时提供了直观的对异常样本的检测能力, 即当样本落在分类面之外时, 样本被认为是异常; 如果落在分类面之内, 则被认为是正常。可视化方法在网络管理和网络安全上的应用并不能完全取代现有的检测算法, 只是对当前基于数据挖掘的异常入侵检测算法[9]的有力补充, 使不熟悉模式识别和数据挖掘的网络管理和网络安全专家能够通过可视化技术实现对分类结果的理解, 并在数据挖掘过程中实现人工干预, 提高系统的精度。
[9] 俞研. 基于数据挖掘的网络入侵检测技术研究[D ].
南京:南京大学计算机科学与技术系, 2006.
作者简介:丁力(19772) , 男, 博士研究生, 研究方向:网络管理、模式分类, E 2. com ; 缪志敏m ail :Pzsho t @ho tm ail
(19782) , 女, 博士研究生, 研究方向:网络安全、模式识别;
3 结束语
数据可视化技术是一类辅助方法, 它采用直观
的图形方式将挖掘出来的数据模式展现出来, 扩展了数据的表达和理解力, 在机器学习和数据挖掘中起着越来越重要的作用, 正受到日益广泛的重视。本文简要描述了可视化技术与可视化数据挖掘方
潘志松(19732) , 男, 副教授, 研究方向:网络安全、模式识别; 倪桂强(19662) , 男, 教授, 研究方向:网络管理、网络安全; 胡谷雨(19632) , 男, 教授, 博士生导师, 研究方向:网络管理、网络安全。