（计算机软件与理论专业论文）元启发式聚类算法及其在入侵检测的应用研究.pdf

摘要 摘要 本文研究聚类算法为目的，从元启发式算法角度探索合适的聚类结果，在已 知和未知聚类簇数目条件下给出多个元启发式聚类算法：同时考虑入侵检测中存 在的问题，给出两个基于遗传聚类的入侵检测算法。 本文的主要研究工作如下： 1 分别介绍聚类分析，元启发式算法和入侵检测的基本概念和主要方法，简 述本文的主要研究工作。 2 将噪声法引入聚类分析，提出两个聚类算法n m c 和k n m c ，详细讨论算 法参数的确定( 噪声幅度，终止噪声率，固定噪声率上的迭代次数和 k - m e a n s 操作) ，与已有的聚类算法比较，实验仿真表明该算法具有计算成 本低、效率高的特点，说明采用噪声法进行聚类分析是可行和有效的。 3 给出一个混合遗传聚类算法g t k c ，算法通过禁忌操作禁止具有高适应度 的少数个体侵占种群以提高种群多样性，同时通过k - m e a i l s 操作改进种群 个体以提高算法收敛速度，进而达到种群多样性和算法收敛速度的平衡， 论文详细讨论算法参数的选择，并与k - m e a n s 算法和g a c 算法进行详细 比较，仿真实验和复杂度分析表明算法能获得更优良的聚类结果。 4 通过引入多个迭代改进算法和邻域生成模型，给出一个禁忌聚类算法模 型，论文详细分析算法各功能模块的性能，通过组合不同的合并和拆分模 块为禁忌算法提供优良的相邻解集，论文进行大量的计算机仿真和对比实 验，结果表明算法复杂度低且计算性能高。 5 聚类分析面临的主要挑战之一是如何准确确定聚类簇数目，在多数情况 下，算法设计人员不能预知聚类簇数目，导致算法陷入局部最优解或者实 验人员必须逐一实验来确定聚类簇数目，本文给出一个基于禁忌搜索的聚 类簇数目估算算法，算法能同时处理具备紧凑球型分布或非紧凑球型对象 分布的对象集合，通过三个阶段逐步优化结果，最终估算出合适的聚类簇 数目，仿真实验表明该算法用于聚类簇数目估算是可行和有效的。 6 针对以聚类簇中心矢量代表聚类簇进行聚类分析的过程进行讨论，：并举例 分析；针对入侵检测研究，考虑到由于入侵行为分布未知，特别对于未知 入侵攻击行为，其分布方式不一定按超球面形式分布，因此给出一个遗传 聚类入侵检测算法，算法由最邻近聚类阶段和遗传优化阶段两部分组成， 能自动实现初始聚类簇集合建立、组合优化和入侵行为标识的整个检测过 上海交通大学1 尊士后研究 ：作报告 程；同时，考虑到遗传算法的变异算子作为局部搜索算子采用随机变异方 式的情况，未能有效解决遗传算法自身局部性能方面的问题。论文给出采 用禁忌搜索作为遗传算法的变异算子以改进随机变异的不足，并运用到入 侵检测，实验结果表明算法检测性能得到改进，检测精度得到提高。 关键词：聚类分析，元启发式算法，入侵检测，遗传算法，模拟退火算法，禁忌 搜索，噪声法 i i a b s t r a c t a b s t r a c t i no r d e rt od e a lw i t ht h ec l u s t e r i n gp r o b l e mu n d e rt h ec r i t e r i o no f m i n i m l n i ls u n lo f s q u a r e sc l u s t e r i n g ，s e v e r a lm e t a h e u r i s t i ca l g o r i t h m sa r ea d o p t e d t oe x p l o r et h ep r o p e r r e s u l t m e a n w h i l e ，am e t a h e u r i s t i ca l g o r i t h m i s a d o p t e dt o e s t i m a t et h en u m b e ro f c l u s t e r s m o r e o v e r , i no r d e rt o s o l v et h ep r o b l e mo fe f f e c t i v e n e s sa n de f f i c i e n c yo f i n t r u s i o nd e t e c t i o n ，t w o g e n e t i cc l u s t e r i n ga l g o r i t h m s a r ed e v e l o p e df o ri n t r u s i o n d e t e c t i o n t h em a i nc o n t r i b u t i o n so f t h i sr e p o r ta r es u m m a r i z e d a sf o l l o w s ： 1 c o n c e p t sa n dm a i nt e c h n i q u e si nc l u s t e r i n ga n a l y s i s ，m e t a h e u r i s t i ca l g o r i t h m s ， a n di n n l l s i o nd e t e c t i o n a l e i n t r o d u c e d ，r e s p e c t i v e l y m e a n w h i l e ，t h e m a i n c o n t r i b u t i o n so f t h i sr e p o r ta l ed e s c r i b e d 2 t h e n o i s i n gm e t h o d ，ar e c e n tm e t a h e u r i s t i ca l g o r i t h m ，i si n t r o d u c e dt od e a l 晰t h t h ec l u s t e r i n gp r o b l e mu n d e rc o n s i d e r a t i o n t w oc l u s t e r i n ga p p r o a c h e s ，n m c a n dk n m c ，a r e r e p o r t e d t h ec h o i c eo f t h ea l g o r i t h m p a r a m e t e r s ( n o i s er a n g e ， t e r m i n a ln o i s er a t e ，n u m b e ro fi t e r a t i o n sa tt h ef i x e dn o i s er a t e ，a n dk m e a n s o p e r a t i o n ) i se x t e n s i v e l yd i s c u s s e d ，a n dp e r f o r m a n c ec o m p a r i s o n sb e t w e e n t h e p r o p o s e dm e t h o d sa n d o t h e rt e c h n i q u e sa r ec o n d u c t e do ne x p e r i m e n t a ld a t as e t s e x t e n s i v ec o m p u t e rs i m u l a t i o n ss h o wt h a tt h ep r o p o s e da p p r o a c h e sw i t hl o w c o s ta n d l a j | g he f f i c i e n c ya r ef e a s i b l ea n d e f f e c t i v ef o r c l u s t e r i n ga n a l y s i s 3 a h y b r i dg e n e t i c b a s e dc l u s t e r i n ga l g o r i t h mc a l l e dg t k ci sd e v e l o p e d w i t ht h e c o o p e r a t i o no f t a b uo p e r a t i o na n dk - m e a n so p e r a t i o n ，g t k ca c h i e v e sh a r m o n y b e t w e e np o p u l a t i o nd i v e r s i t ya n dt h es p e e do fc o n v e r g e n c e t a b uo p e r a t i o ni s m a i n l y u s e dt o p r e v e n t t h e p o p u l a t i o n f r o m b e i n go c c u p i e db y s e v e r a l i n d i v i d u a l so f h i g h e rf i t n e s ss oa st ok e e par e l a t i v e l yh i g hl e v e lo fp o p u l a t i o n d i v e r s i t y m o r e o v e r , k - m e a n so p e r a t i o ni si n t e g r a t e dt o e n h a n c et h es p e e do f c o n v e r g e n c e t h ec h o i c eo f t h ea l g o r i t h mp a r a m e t e r si sd i s c u s s e d i ng r e a td e t a i l i t ss u p e r i o r i t yo v e rk m e a n sa l g o r i t h ma n dg a c i se x t e n s i v e l yd e m o n s t r a t e df o r e x p e r i m e n t a l d a t as e t s 4 b yi n t r o d u c i n gs e v e r a ll o c a l i t e r a t i o na l g o r i t h m sa n dm o d u l e sf o rc r e a t i n gt h e n e i g h b o r h o o d ，at a b uc l u s t e r i n ga l g o r i t h mi sd e v e l o p e d p e r f o r m a n c ee v a l u a t i o n o fe a c hc o m p o n e n ti sd i s c u s s e di nd e t a i l d i f f e r e n tm e r g e n c em o d u l e sa n d i l l s h a n g h a i 儿a o t o n gu n i v e r s i t y p o s t - d o c t o r a lr e s e a r c hr e p o i n l 5 6 p a r t i t i o nm o d u l e sa r ec o m b i n e da n de x c e l l e n tn e i g h b o r i n gs o l u t i o n sa r ep r o v i d e d f o rt a b us e a r c h e x t e n s i v e c o m p u t e rs i m u l a t i o n sa r ec o n d u c t e da n ds h o w t h a tt h e p r o p o s e da l g o r i t h mh a sl o wc o m p l e x i t ya n dh i g hp e r f o r m a n c e a c h a l l e n g ei nc l u s t e r i n ga n a l y s i si sh o w t o c o r r e c t l ye s t i m a t et h en u m b e ro f c l u s t e r s i nm o s tc a s e s ，t h ed e s i g n e ri sn o ta w a r eo ft h i si n f o r m a t i o ni na d v a n c e ， w h i c ho f t e nr e s u l t si nt h es u b o p t i m a lo u t c o m eo rt r y i n gt h en u m b e ro fc l u s t e r s o n eb yo n e i nt h i s r e p o r t , at a b us e a r c hb a s e da l g o r i t h mf o re s t i m a t i n gt h e n u m b e ro fc l u s t e r si sd e v e l o p e d t h i sa l g o r i t h mc a l ld e a lw i t hd a t as e t sw h o s e c l u s t e r sa r eo fe i t h e rs p h e r i c a lo rn o n - s p h e r i c a ls h a p ea n de x p l o r et h ep r o p e r n u m b e ro fc l u s t e r s b y t h r e e s t a g e s c o m p e e r s i m u l a t i o n ss h o wt h a tt h i s a l g o r i t h mi sf e a s i b l ea n d e f f e c t i v e c l u s t e r i n ga n a l y s i su s i n gt h e c l u s t e rc e n t r o i di sd i s c u s s e db ye x a m p l e s f o r i n t r u s i o nd e t e c t i o n ，t h e a c t i v i t y d i s t r i b u t i o ni su n k n o w na n dm a yb en o ti n s u p e r - s p h e r i c a ls l 姐p e s o ，a n i n t r u s i o nd e t e c t i o n a l g o r i t h m i s d e v e l o p e d c o n s i s t i n go f t h en e a r e s tn e i g h b o rc l u s t e r i n gs t a g ea n dt h eg e n e t i co p t i m i z a t i o n s t a g e ，w h i c hc a na u t o m a t i cs e tu pt h es e to fo r i g i n a lc l u s t e r s ，o p t i m i z et h e mb y c o m b i n a t i o na n dl a b e li n t r u s i o na c t i v i t i e s m e a n w h i l e ，s t o c h a s t i cs i n g l ep o i n t m u t a t i o no p e r a t o ra st h el o c a ls e a r c ho p e r a t o ro fg e n e t i ca l g o r i t h m sc a n n o t e x p l i c i t l yi m p r o v e l o c a ls e a r c hp e r f o r m a n c e an e wm u t a t i o no p e r a t o rb a s e do n t a b us e a r c hi sp r o p o s e dt os o l v et h i sp r o b l e ma n da p p l i e dt oi n t r u s i o nd e t e c t i o n e x p e r i m e n t a l r e s u l t ss h o wt h a tt h i sd e t e c t i o na l g o r i t h mc a na c q u i r eh i g h e r q u a l i t yr e s u l t st h a n b e f o r e k e y w o r d s ：c l u s t e r i n ga n a l y s i s ，m e t a h e u r i s t i ca l g o r i t h m ，i n t r u s i o nd e t e c t i o n ，g e n e t i c a l g o r i t h m s ，s i m u l a t e da n n e a l i n ga l g o r i t h m ，t a b us e a r c h ，n o i s i n g m e t h o d i v i n t r o d u c t i o n c h a p t e r 1 i n t r o d u c t i o n 1 1c l u s t e r i n g 【1 - 4 】 t h e v a r i e t y o ft e c h n i q u e sf o r r e p r e s e n t i n gd a t a ，m e a s u r i n gp r o x i m i t y ( s i m i l a r i t y ) b e t w e e nd a t ae l e m e n t s ，a n dg r o u p i n gd a t ae l e m e n t sh a sp r o d u c e dar i c ha n do f t e n c o n f u s i n ga s s o r t m e n to fc l u s t e r i n gm e t h o d s c l u s t e r i n gi su s e f u li ns e v e r a le x p l o r a t o r y p a t t e r na n a l y s i s ，g r o u p i n g ，d e c i s i o n - m a k i n g ，a n dm a c h i n el e a r n i n gs i t u a t i o n s ，i n c l u d i n g d a t a m i n i n g ，d o c u m e n tr e t r i e v a l ，i m a g es e g m e n t a t i o n , a n dp a t t e r n c l a s s i f i c a t i o n h o w e v e r , i nm a n ys u c hp r o b l e m s ，t h e r e i sl i t t l e p r i o ri n f o r m a t i o n ( e g ，s t a t i s t i c a l m o d e l s ) a v a i l a b l ea b o u t t h ed a t a ，a n dt h ed e c i s i o n m a k e rm u s tm a k ea sf e w a s s u m p t i o n s a b o u tt h ed a t aa sp o s s i b l e i ti su n d e rt h e s er e s t r i c t i o n st h a tc l u s t e r i n gm e t h o d o l o g yi s p a r t i c u l a r l ya p p r o p r i a t ef o rt h ee x p l o r a t i o no fi n t e r r e l a t i o n s h i p sa m o n gd a t ap o i n t st o m a k ea l la s s e s s m e n t ( p e r h a p sp r e l i m i n a r y ) o ft h e i rs t r u c t u r e c l u s t e ra n a l y s i si st h e o r g a n i z a t i o no f a c o l l e c t i o no f p a t t e m s ( u s u a l l y r e p r e s e n t e d a sav e c t o ro f m e a s u r e m e n t s ， o ra p o i n ti nam u l t i d i m e n s i o n a ls p a c e ) i n t oc l u s t e r sb a s e do ns i m i l a r i t y i n t u i t i v e l y , p a t t e r n sw i t h i na v a l i dc l u s t e ra r em o r es i m i l a rt oe a c ho t h e rt h a nt h e ya r et oap a t t e r n b e l o n g i n g t oad i f f e r e n tc l u s t e r 【1 】 1 1 1c o n e e p t s a t f i r s t ，s o m ed e f i n i t i o n sa r ed e s c r i b e da sf o l l o w s 1 ： a p a t t e r n ( o rf e a t u r ev e c t o r ，o b s e r v a t i o n ，o rd a t u m lxi sas i n g l ed a t ai t e mu s e db y t h e c l u s t e r i n ga l g o r i t h m i tt y p i c a l l yc o n s i s t so fav e c t o ro fmm e a s u r e m e n t s ： x = o l ，x 。) t h ei n d i v i d u a ls c a l a r c o m p o n e n t sto fap a t t e r n xa r ec a l l e df e a t u r e s ( o r a t t r i b u t e s ) 胁i st h ed i m e n s i o n a l i t yo f t h ep a t t e mo ro f t h e p a t t e r ns p a c e a p a t t e r n s e ti sd e n o t e da s x = ( x l ，x t h e i 4 p a t t e mi n xi sd e n o t e d x ，= ( x ，x 。) i nm a n yc a s e sap a t t e ms e t t ob ec l u s t e r e di sv i e w e da st h e nxmp a t t e r nm a t r i x t y p i c a lp a t t e r nc l u s t e r i n ga c t i v i t yi n v o l v e st h ef o l l o w i n gs t e p s 1 ，2 ： 1 p a t t e r nr e p r e s e n t a t i o n ( o p t i o n a l l yi n c l u d i n gf e a t u r ee x t r a c t i o na n d y o rs e l e c t i o n ) ， s h a n g h a ij i a o t o n gu n i v e r s i t yp o s t - d o c t o r a lr e s e a r c hr e p o r t 2 d e f i n i t i o no fap a t t e r n p r o x i m i t y m e a s u r ea p p r o p r i a t et ot h ed a t ad o m a i n ， 3 c l u s t e r i n g o rg r o u p i n g ， 4 d a t a a b s t r a c t i o n ( i f n e e d e d ) ，a n d 5 a s s e s s m e n to f o u t p u t ( i f n e e d e d ) i nf i g u r e1 1 ，t h eg e n e r a ld e s c r i p t i o no fc l u s t e r i n gi n c h i n gt h ef i r s tt h r e eo f t h e s e s t e p si sd e s c r i b e d f i g u r e1 1g e n e r a ld e s c r i p t i o no f c l u s t e r i n g p a t t e r n r e p r e s e n t a t i o nr e f e r st ot h en u m b e ro fc l a s s e s ，t h en u m b e r o fa v a i l a b l ep a t t e r n s ， a n dt h en u m b e r ，t y p e ，a n ds c a l eo ft h ef e a t u r e sa v a i l a b l et ot h ec l u s t e r i n ga l g o r i t h m f e a t u r es e l e c t i o ni st h ep r o c e s so f i d e n t i f y i n gt h em o s t e f f e c t i v es u b s e to ft h eo r i g i n a l f e a t u r e st ou s ei n c l u s t e r i n g f e a t u r e e x t r a c t i o ni st h eu s eo fo i l eo rm o r e t r a n s f o r m a t i o n so ft h ei n p u tf e a t u r e st op r o d u c en e ws a l i e n tf e a t u r e s e i t h e ro rb o t ho f t h e s e t e c h n i q u e sc a n b eu s e dt oo b t a i na n a p p r o p r i a t es e to f f e a t u r e st ou s ei nc l u s t e r i n g p a t t e r np r o x i m i t yi s u s u a l l ym e a s u r e db yad i s t a n c e f u n c t i o nd e f i n e do np a i r so f p a t t e r n s t h eg r o u p i n gs t e p c a nb ep e r f o r m e di nan u m b e ro fw a y s t h eo u t p u t c l u s t e r i n g ( o rc l u s t e r i n g s ) c a l lb eh a r d ( ap a r t i t i o no ft h ed a t ai n t og r o u p s ) o rf u z z y ( w h e r ee a c hp a r e m h a sav a r i a b l ed e g r e eo f m e m b e r s h i pi ne a c ho f t h eo u t p u tc l u s t e r s ) ， d a t aa b s t r a c t i o ni st h ep r o c e s so f e x t r a c t i n gas i m p l ea n dc o m p a c tr e p r e s e n t a t i o no f a d a t as e t i nt h ec l u s t e r i n gc o n t e x t ，at y p i c a ld a t aa b s t r a c t i o ni sa c o m p a c td e s c r i p t i o no f e a c h c l u s t e r ，u s u a l l yi n t e r m so fc l u s t e r p r o t o t y p e s o rr e p r e s e n t a t i v ep a t t e r n ss u c ha st h e c e n t r o i d c l u s t e rv a l i d i t ya n a l y s i si st h ea s s e s s m e n to fac l u s t e r i n gp r o c e d u r e so u t p u t o f t e nt h i sa n a l y s i su s e sas p e c i f i cc r i t e r i o no fo p t i m a l i t y ；h o w e v e r ，t h e s eo d t e r i aa r e u s u a l l ya r r i v e da ts u b j e c t i v e l y h e n c e ，l i t t l ei nt h ew a yo f g o l d s t a n d a r d s e x i s ti n c l u s t e r i n ge x c e p ti nw e l l - p r e s c r i b e ds u b d o m a i n s 1 1 2c l u s t e r i n g t e c h n i q u e s i nt h i ss e c t i o n ，w ed e s c r i b es o m e o f c l u s t e r i n g m e t h o d s m o r ed e t a i ld e s c r i p t i o n sc a l lb e f o u n d i n 1 - 4 2 i n t r o d u c t i o n 1 1 2 1h i e r a r c h i c a lc l u s t e r i n gm e t h o d 1 1 , 4 】 h i e r a r c h i c a lc l u s t e r i n gb u i l d sac l u s t e rh i e r a r c h yo r ，i no t h e rw o r d s ，at r e eo f c l u s t e r s ， a l s ok n o w na sa d e n d r o g r a r n e v e r y c l u s t e rn o d ec o n t a i n sc h i l d c l u s t e r s ；s i b l i n gc l u s t e r s p a r t i t i o nt h ep o i n t sc o v e r e db y t h e i rc o l n n l o n p a r e n t s u c ha i la p p r o a c ha l l o w se x p l o r i n g d a t ao nd i f f e r e n tl e v e l so f g r a n u l a r i t y h i e r a r c h i c a lc l u s t e r i n gm e t h o d sa r ec a t e g o r i z e d i n t o a g g l o m e r a t i v e ( b o t t o m - u p ) a n dd i v i s i v e ( t o p d o w n ) 2 ，3 a na g g l o m e r a t i v e c l u s t e r i n gs t a r t sw i t ho n e - p o i n tf s i n g l e t o n ) c l u s t e r sa n dr e c u r s i v e l ym e r g e st w o o rm o r e m o s ta p p r o p r i a t ec l u s t e r s ad i v i s i v ec l u s t e r i n gs t a r t sw i t ho n ec l u s t e ro fa l ld a t ap o i n t s a n dr e c u r s i v e l y s p l i t s t h em o s ta p p r o p r i a t ec l u s t e r t h ep r o c e s sc o n t i n u e su n t i l a s t o p p i n gc r i t e r i o n ( f r e q u e n t l y ，t h er e q u e s t e d n u m b e rk o f c l u s t e r s ) i sa c h i e v e d a d v a n t a g e so f h i e r a r c h i c a lc l u s t e r i n gi n c l u d e 4 】： e m b e d d e d f l e x i b i l i t yr e g a r d i n g t h el e v e lo f g r a n u l a r i t y e a s e o f h a n d l i n go f a n y f o r m so f s i m i l a r i t yo rd i s t a n c e c o n s e q u e n t l y , a p p l i c a b i l i t y t oa n ya 恤r i b u t et y p e s d i s a d v a n t a g e so f h i e r a r c h i c a lc l u s t e r i n ga r e r e l a t e dt o ： v a g u e n e s s o f t e r m i n a t i o nc r i t e r i a t h ef a c t 也a tm o s th i e r a r c h i c a l a l g o r i t h m s d on o tr e v i s i to n c ec o n s t r u c t e d ( i n t e r m e d i a t e 、c l u s t e r sw i t h t h e p u r p o s e o f t h e i r i m p r o v e m e n t m o s th i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m sa r ev a r i a n t so f t h es i n g l e - l i n k ，c o m p l e t e l i n k ， a n dm i n i m u m v a r i a n c e a l g o r i t h m s o ft h e s e ，t h es i n g l e l i n k a n d c o m p l e t e l i n k a l g o r i t h m sa r em o s tp o p u l a r 【1 】o t h e rp o p u l a r h i e r a r c h i c a lc l u s t e r i n gm e t h o d si n c l u d e c u r e 【5 】，c h a m e l e o n 【6 】，b i r c h 7 】，e t c 1 1 2 2p a r t i t i o n a lc l u s t e r i n g m e t h o d 【1 , 3 l a p a r t i t i o n a lc l u s t e r i n ga l g o r i t h mo b t a i n sas i n g l ep a r t i t i o no ft h ed a t ai n s t e a do fa c l u s t e r i n gs t r u c t u r e ，s u c ha st h ed e n d r o g r a mp r o d u c e db yah i e r a r c h i c a lt e c h n i q u e p a r t i t i o n a lm e t h o d sh a v ea d v a n t a g e si na p p l i c a t i o n si n v o l v i n g l a r g ed a t as e t sf o rw h i c h t h ec o n s t r u c t i o no fa d e n d r o g r a m i s c o m p u t a t i o n a l l y p r o h i b i t i v e ap r o b l e m a c c o m p a n y i n g t h eu s eo fa p a r t i t i o n a la l g o r i t h mi st h ec h o i c eo f t h en u m b e ro fd e s i r e d o u t p u tc l u s t e r s i n 8 ，t h eg u i d a n c ei sp r o v i d e do nt h i sk e yd e s i g nd e c i s i o n t h e p a r t i t i o n a lt e c h n i q u e su s u a l l yp r o d u c ec l u s t e r sb yo p t i m i z i n g ac r i t e r i o nf i m c t i o n d e f i n e de i t h e rl o c a l l y ( o nas u b s e to ft h ep a t t e r n s ) o rg l o b a l l y ( d e f i n e do v e ra l lo ft h e p a t t e r n s ) c o m b i n a t o r i a ls e a r c ho f t h es e to f p o s s i b l el a b e l i n g sf o ra no p t i m u mv a l u eo f ac r i t e r i o ni sc l e a r l yc o m p u t a t i o n a l l yp r o h i b i t i v e i np r a c t i c e ，t h e r e f o r e ，t h ea l g o r i t h mi s 3 s h a n g h a ij i a o t o n gu n i v e r s i t yp o s t - d o c t o r a l r e s e a r c hr e p o r t t y p