（计算机应用技术专业论文）分布式聚类及其在入侵检测中的应用研究.pdf

豢塞烬葱大学矮士学位论文分东式聚类及其禚入侵捻测申的应用研究 摘要 聚类分析是数据挖掘领域的项重要研究内容，它在金融、电信、保险业、市场营销、 异常检测、网络安全、科学决策等方面具有十分重要的_ 应用价值，因此受到研究人员的高 度重视。已有魄聚类舞法大多只逶耀予集孛式数据鲍聚类。由于弱络带宽、站点存德量、 信息安全及隐私保护等限制，把不同站点的数据全部集中到某一个中心站点进行全局聚类 几乎是不可能的。所有站点数据集中在一起，数据量会非常庞大，聚类效率会驻著降低。 本文对分布式聚类方法作了一些较深入的研究，取得了如下成果： 1 提出了赫效的分布式k 均值聚类方法d k m e a n s 。该方法在站点间只传送少量聚簇 信息，有效降低了分布式聚类过程中的数据逶信繁，并畿达到与k 均值算法等效豹聚类质 量。理论分析及实验结果表明，d k - m e a n s 是一种有效可行的分布式聚类算法，对于高维数 据集同样有效。 2 针对聚类数弱难以确定的润题，提出了分带式聚类方法程d k - m e a n s ，通过分割和 合并聚簇将训练数据集划分成适当数目的聚簇而不必预设聚簇半径。实验结果表明，该方 法是有效可行的 3 。针对基予密度的分布式聚类算法d b d c 通信量大、效率低的缺点，提出了一种基 于密度的分布式聚类方法d b d c * 。有效降低了分布式聚类过程中的数据通信鬣，全局聚 类时综合考虑了各站点数据麓分蠢情况，襞够对任意形状分布的数据进行聚类。实验结果 表明，该方法是有效可行的，对于高维数据集同样有效。 4 提出了一种适用于入侵检溯的数据预处理方法，定义了类别型属憔各取值之闻的差 异度，使得在对训练集进行无监督学习生成检测模型过程中，髓够阕时有效地处理数值型 属性和类别型属性。理论分析表明，我们所定义的类别型属性值差异度既保留了类别型属 性各取僮之问的本质特征，同时也没有改交数据集的原始维数。实验结粜表嚷，采用该数 据预处理方法进行聚类所建立的入侵检测模型能更有效的检测攻击。 5 提出了一种基于分布式聚类的异常入侵检测方法i d - d c ，该方法建立在一种无中 心的多a g e n t 分布式体系结构之上，通过对训练集进行分布式聚类产生聚簇挨型，采用基 于双参考点的标识算法标记异常簇，不需要具有类别标签的训练集且可自动确定聚簇模型 的个数。实验结果表明，通过该方法所建立的分布式入侵检灏模鍪l 可有效检测攻击。 6 在j a v a 平螽下设计并实现了基于a g e n t 的分布式入侵检测系统原型，在该系统中 实现了基于分布式聚类的入侵检测方法，利用分布式聚类方法建立入侵检测模型。实验测 试结果表瞬，该方法能有效检溺各种攻击并且具有对未知攻赉盼增量学习能力。 关键词：数据挖掘；分布式数据挖撅；聚类；分布式聚类；入侵检测：分布式入侵检测 南京师范大学硕士学位论文分布式聚类及其在入侵检测中的应用研究 a b s t r a c t c l u s t e r i n gi sa ni m p o r t a n tt a s ko f d a t am i n i n ga n dh a sa t t r a c t e dt r e m e n d o u si n t e r e s ta m o n g r e s e a r c h e r s i ti sp r a c t i c a lf o ru s ei nm a n yf i e l d ss u c ha sf i n a n c e , t e l e c o m m u n i c a t i o n ，i n s u r a n c e b u s i n e s s ，m a r k e ta n a l y s i s ，a n o m a l yd e t e c t i o n ，n e t w o r ks e c u r i t y , s c i e n c ed e c i s i o n , a n ds oo n e x i s t i n gc l u s t e r i n ga l g o r i t h m sa r en o ts u i t a b l ef o rd i s t r i b u t e de n v i r o n m e n t d i s t r i b u t e dc l u s t e r i n g i sac h a l l e n g er e s e a r c ht o p i cd u et ov a r i e t yo fr e a l - l i f ec o n s t r a i n si n c l u d i n gb a n d w i d t h ，t h e s t o r a g eo ft h es i t em e m o r y , e t c i td e c r e a s e sc l u s t e r i n ge f f i c i e n c yi ne v i d e n c ea n dr e s u l t si n h u g e n e s sd a t a s e tw h i l ec e n t r a l i z ea l i t h el o c a ld a t a d i s t r i b u t e dc l u s t e r i n ga n di t a p p l i e di n i n t r u s i o nd e t e c t i o na r es t u d i e d ，a n di n n o v a t i v ec o n t r i b u t i o n sa r ea c h i e v e da sf o l l o w s ： 1 a ne f f e c t i v ed i s t r i b u t e dk - m e a n sc l u s t e r i n ga l g o r i t h md k m e a n si s p r o p o s e dt o i m p r o v ee f f i c i e n c yo ft h ed i s t r i b u t e dc l u s t e r i n ga l g o r i t h mk - d m e a n s d k m e a n s ，w h i c ho n l y b r o a d c a s t sc l u s t e r si n f o r m a t i o no fe a c hs i t ei nt h ed i s t r i b u t e de n v i r o n m e n t , e f f e c t i v e l yd e c r e a s e n e t w o r ko v e r l o a d b o t ht h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h ee f f i c i e n c yo f d k - m e a n si ss u p e r i o rt ok - d m e a n sa n di tc a nr e a c ht h es a m ec l u s t e r i n gq u a l i t ya sk - m e a n s 2 i n t r o d u c ead i s t r i b u t e dc l u s t e r i n ga l g o r i t h m 仅一d k - m e a n s i ta u t o m a t i c a l l yp a r t i t i o n s t h ed a t as e ti n t oar e a s o n a b l en u m b e ro fc l u s t e r sb yd i v i d i n ga n dc o m b i n gc l u s t e r s 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 ee f f i c i e n c yo f0 【一d k - m e a n si ss u p e r i o rt oo t h e r s 3 a ne f f e c t i v ed e n s i t yb a s e dd i s t r i b u t e dc l u s t e r i n ga l g o r i t h md b d c 幸i sp r o p o s e dt o i m p r o v ee f f i c i e n c yo ft h ed i s t r i b u t e dc l u s t e r i n ga l g o r i t h md b d c i te f f e c t i v e l yd e c r e a s en e t w o r k o v e r l o a d ，d i s c o v e rc l u s t e r sw i t ha r b i t r a r ys h a p ea n di m p r o v et h eq u a l i t yo fg l o b a lc l u s t e r i n g e x p e r i m e n t a lr e s u l t ss h o w t h a tt h ee f f i c i e n c yo fd b d c 宰i ss u p e r i o rt od b d c 4 a ne f f e c t i v ea n o m a l yd e t e c t i o na l g o r i t h mb a s e do nc l u s t e r i n gi sp r o p o s e dt od e a lw i t h m i x e da t t r i b u t e s t h i sa l g o r i t h m ，w h i c hg e t sc l u s t e rm o d e l sb yu s i n gt h ec l u s t e r i n ga l g o r i t h mo n u n l a b e l e dt r a i n i n gd a t a , d e f i n e st h ed i s t a n c eb e t w e e ne a c hp a i ro fv a l u e si no n ec a t e g o r i c a l a t t r i b u t e ，c o u l dd e a lw i t hb o t ht h en u m e r i c a la n dc a t e g o r i c a la t t r i b u t ee f f i c i e n t l y t h e o r e t i c a l a n a l y s i ss h o w st h a ti th o l d sn o to n l yt h ee s s e n c eb e t w e e nd i f f e r e n tv a l u e si no n ec a t e g o r i c a l a t t r i b u t e ，b u ta l s ot h eo r i g i n a l i t yd i m e n s i o n so ft h ed a t a s e t a tl a s t , e x p e r i m e n t sr e s u l t ss h o wt h a t o u rm e t h o dc a nd e t e c ti n t r u s i o n sm o r ee f f i c i e n t l yw h i l em a i n t a i n i n gal o wf a l s ep o s i t i v er a t e 5 an o v e le f f e c t i v ed i s t r i b u t e da n o m a l yd e t e c t i o na l g o r i t h mi d d cb a s e do nc l u s t e r i n gi s p r o p o s e dt or e a l i z et h ed i d s a l g o r i t h mi d - d c ，w h i c hf i r s tg e t sc l u s t e rm o d e l sb yu s i n gt h e d i s t r i b u t e dc l u s t e r i n ga l g o r i t h mo nu n l a b e l e dt r a i n i n gd a t aa n dt h e nl a b e l st h e s em o d e l st h r o u g h a l g o r i t h md o u b l e r e f e r e n c e ，o v e r c o m e st h ed r a w b a c k so fr e l y i n go nl a b e l e dt r a i n i n gd a t aw h i c h m o s tc u r r e n ta n o m a l y b a s e di n t r u s i o nd e t e c t i o nd e p e n do na n de x p e c t st oa u t o m a t i c a l l yp a r t i t i o n t h ed a t as e ti n t oar e a s o n a b l en u m b e ro fc l u s t e r s e x p e r i m e n t sr e s u l t ss h o wt h a to u rm e t h o dc a n d e t e c ti n t r u s i o n se f f i c i e n t l yw h i l em a i n t a i n i n gal o wf a l s ep o s i t i v er a t e 6 a na c t u a li n t r u s i o nd e t e c t i o ns y s t e mi si m p l e m e n t e dw i t hj a v al a n g u a g e d i s t r i b u t e d c l u s t e r i n ga l g o r i t h m sa r eu s e df o rt r a i n i n gi n t r u s i o nd e t e c t i o nm o d e l s e x p e r i m e n t a lr e s u l t so n t h es y s t e ms h o wt h a tt h ep r e s e n t e da l g o r i t h m sa r ee f f e c t i v ea n de 伍c i e n ti nd e t e c t i n ga t t a c k s k e y w o r d s ：d a t a m i n i n g ；d i s t r i b u t e dd a t a m i n i n g ；c l u s t e r i n g ；d i s t r i b u t e dc l u s t e r i n g ；i n t r u s i o n d e t e c t i o n ；d i s t r i b u t e di n t r u s i o nd e t e c t i o n i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新 的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除弓l 文井，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容舞，不包含其他人或其它机构 已经发表或撰写过的研究成采。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名圣丘! ! 日期：塑节：堑! 圣 学位论文使用授权声明 本人完全了解南京师范大学有关傺留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用予非赢利爵的的少量复制并允许 论文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据 库进行检索；有权将学位论文的标题和摘要汇编出版。保密的学位 论文在解密后适用本规定。 。 作者签名：丕# 蔓! 日期：挝堡：! 至 南京好范大学硕士学位论文分帮式聚类及其农入侵检测中的应用研究 第1 章绪论 1 1 研究背景与课题意义 数据挖掘( d a t am i n i n g ) ，也称数据库率的知识发现( k d d ，k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，是指从大型数据瘁或数据仓库中提取人们感兴趣的知识，这些知识是隐食的、 事先未知的、潜在有用的信息，提取的知识般可表示为概念( c o n c e p t s ) 、规贝l j ( r u l e s ) 、规 律( r e g u l a r i t i e s ) 、模式0 a t t e m s ) 等形式l 。髑数据瘴管理系统米存铸数据，矮枫器学习的方 法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据挖掘技术的产生。数据 挖掘是一门交叉性学科，涉及到机器学习、模式识别、翔纳推理、统计学、数据库、数据可 视化、高性能计算等多个领域。 由于数据挖掘任务面向的是大规模的数据库或数据仓库，霞此要处理的数据鼙通常非常 大，往往达到g b 甚至t b 字节数量级；在现实环境中，业务的跨地域分布通常导致数据库跨 地域分布，多个数据库通常通过网络连接在一起，数据挖掘的任务有时要同时针对这多个数 据库；憝羞w w w 疲用的毽趋普及，i n t e r n e t 已成为当今世界最大熊分糍数据源， i n t e r n e t 中的数据难以几何级数增长，而腻i n t e r n e t 本身就是一个巨大的分布式系统。 躲讶应胡i n t e r n e t 巾的庞大数据资源，发现霹获取其中有徐值鳃知识，已经成为入 ：l 必须 正视的问题。而分布式数据挖掘起在i n t e r n e t 中发现和获取有用知识的最佳方法之一。分 布式数据挖掘为从“海洋数据”中开采有用的知识提供了有效途径，它将在金融投资、电信、 市场营销、气象和灾难预报、科学决策、i n t e r n e t 信息浏览等方面发挥巨大的作用，具有 广阔的应用前景。分布式数据挖掘的研究是近几年提出的一个新的研究领域，从广义上讲。 分布式环境下豹数据挖掘，都可称为分布式数据挖掘 2 1 。迄今必止，人们对分布式关联规则 分析1 3 , 4 1 ，分布式分类分析1 5 6 1 以及分布式聚类分析1 7 j 等都已经展开研究并取得了些成绩。 聚类分耩 8 1 是数据挖撼领域的一顼重要疆究内容，其目标是在没有任鹰先验知识的前提 下，根据数据的相似性将数据聚合成不同的簇，使得相同簇中的元素尽可能相似，不同簇中 的元素差别尽可能的大。聚类分析作为数据挖掘系统中的一个模块，既可以作药一个攀独的 工具以发现数据库中数据分布深层信息，也可以作为其他数据挖掘分析算法的一个预处理步 骤。聚类分析的应用相当广泛，在商务上，聚类能帮助市场分析人员从消赞者信息库中发现 不阉的群体，势且用购买模式来刻画不同的消费群体的特征。在生物学上，聚类可以被用来 辅助研究动植物的分类，可以用来分类具有相同功能的基因，还可以用来发现人群中的一些 潜在鳇缩构。聚类还可戳用来从空阌数据库中识别出具有楣似特征的空闻对象；可以从保险 公闭的数据库中发现汽车保险中具有较高索赔概率的群体：还可以用来分类万维网上不同类 壁的文档、或分析w e b 磊恚豉发现特殊的访阀模式等。 传统的聚类算法只适用于集中式数据的聚类。随着网络的广泛应用，大量的数据将分布 存在。由于网络带宽、站点存储量、信息安全及隐私保护等限制，把不同站点的数据全部集 中到某一个中心站点进行全局聚类几乎是不可能的。所有站点数据集中在起，数据鬟会非 常庞大，聚类效率会显著降低。已有的聚类算法大多基乎内存，可扩展性较差1 9 1 ，不能有效 应用予大数据集。 分布式聚类是传统聚类方法在网络环境下的扩展与改进，能够有效的处理分散的犬规模 数据集。即在分散的结点上进行局部聚类分析，逶过各个绩点闻聚类信息的遥信、分析处理 得到最终聚类结果。目前，分布式聚类研究较少，现有的分布式聚类算法大多是传统聚类算 毒裘帮蔻大学矮女学位论文分蠢式聚类及其鑫入侵梭溅孛的应用研究 法在分布式环境下的扩展与改进。这些方法在性施秘耩发上不两足都存在缺黧。这裁促使 了我们进一步研究效率更好，精度更高的分布式聚类算法。 入侵检测u q 从诞生到现在己经有2 0 多年的历史了，在其发展变上有儿个里程碑。1 9 8 0 年4 月，j a m e sp a n d e r s o n 为美国空军做了一份题为 c o m p u t e rs e c u r i t yt h r e a tm o n i t o r i n ga n d s u r v e i l l a n c e ) i t t l 的技术报告，第一次详细阐述了入侵检测的概念。他提出了一种对计算机 系统风险和威胁的分类方法，_ 并将威胁分为外部渗透、内部渗透和不法行为三种，还提出了 利用审计跟踪数据监视入侵活动的思想。这份报告被公认为是入侵检测的开山乏作。 从1 9 8 4 年掰1 9 8 6 年，彝治敦大学的d o r o t h yd e n n i n g 幕i s r l c s l ( s r ! 公司计算祝科学实 验嶷) 的p e t e rn e u m a n n 研究出了一个实时入侵检测系统模型，取名为i d e s t l 2 l ( 入侵检测专 家系统) 该模型由六个部分组成：主体、对象、审计记录、轮廓特征、异常记录、活动规 则。它独立于特定的系统平台、应用环境、系统弱点以及入侵类型，为构建入侵捡测系统提 供了一个通用的框架。 1 9 8 7 年，d o r o t h yd e n n i n g 在其发表的经典论文“觚i n t r u s i o nd e t e c t i o nm o d e l ”( t 3 l 中首 次提出了入侵检测的基本模型。 1 9 9 0 年是入侵检测系统发展史上熊一个分水岭。这一年，攘州大学戴维新分校的毛t h e b e r l e i n 等人开发出了n s m ( n e t w o r ks e c u r i t ym o n i t o r ) 1 4 1 该系统第一次直接将网络流作 为审计数据来源，因而可以在不将审计数据转换成统一格式的情况下监控异种主机。从此之 后，入侵检测系统发展史翻开7 叛的一页，两大阵营正式形成：基于网络的i d s 和基予主机 的i d s 。 1 9 8 8 年的莫里斯蠕虫事件l l 硼发生之嚣，耀络安全右真正引起了军方、学术界器l 企业的 高度重视。美国空军、国家安全局和能源部共同资助空军密码支持中心、劳伦斯利弗摩尔国 家实验室、加州大学戴维凝分校、h a y s t a c k 实验室，开展对分布式入侵检测系统( d i d s ) i 6 i 的研究，将基于主机和基于网络的检测方法集成到一起。d i d s 是分布式入侵检测系统历史 上的一个里程碑式的产品，它的检测模塑采用了分层结构，包括数据、事件、圭体、上下文、 威胁、安全状态等6 层。 从2 0 世纪9 0 年代到现在，入侵检测系统的研发呈现国百家争鸣的繁荣局面，并在智能化 和分布式两个方向取褥了长足的进展。s r i c s l 、普渡大学、加州大学戴维斯分校、洛斯阿 拉莫斯圜家实验室、哥伦比亚大学，新墨西哥大学等机构在这些方面的研究代表了当前的最 离水平。 随着黑客技术的不断发展，入侵行为表现为不确定性、复杂性、多样性等特点。一些黑 客组织西经将如何绕过入侵检测系统( i d s ) 或攻击i d s 作势研究重点。从髫前国夕 入侵检测 研究的发展趋势来看，今后入侵检测的工作将侧重在以下几个方面： ( 1 ) 如何解决高速交换网络环境下的入侵检测问题。高速网络，尤其是交换技术的发展 以及通过加密信道的数据通信使得共享网段侦听的网络数据采集方法显得不足，而巨大的通 信量对数据分析也提出了新的要求。 大规摸分毒式的入侵检测系统殴及异构系统之阕的协作和数据共享问题。需要铡定 统一的入侵模式库，为不同系统的入侵描述建立转换机制。 ( 3 ) 入侵检测的智能性闷题。入侵检测方法越来越多样纯与综合纯，尽管己经有神经霹 络与遗传算法等模式识别方法应用在入侵检测上，但是这只是初步的研究工作，需要对智能 化的i d s 加以进一步的研究以提高其自学习与自适应熊力。 4 ) 入侵检测的自我保护闽题。i d s 自身的安全性至关重要，瓣要和其他的安全机制配 合使用。 5 ) 建立有效的入侵检测评测方法。用户在选择i d s 时，需要对众多的i d s 进行评价， 评价指标包括i d s 的检测范围、系统资源占用、i d s 系统自身的可靠性与鲁棒性等。因此设 2 南京翔莛大学矮圭学位论文分布式聚类及其在入覆梭测孛的应用研究 计通用的入侵检测系统测试与评传的平台，实现对多种i d s 系统的统评佶，鑫成为当 i 蓼 i d s 的另重要研究与发展领域。 ( 6 ) 与其他网络安全技术的结合。比如结合防火墙、安全电子交易等网络安全与电子商 务技术，提供完整的阚络安全保障。 目前，我国计算机网络的发展水平、安全技术和管理手段都落后于国际水平。我阕在安 全方瑟的研究缀历了通信保密、计算枫数据保护两个发展阶段，正在进入隧终安全的研究阶 段。对系统脆弱性评估及入侵检测的研究，囡内还刚刚开始，入侵检测的发展还处于初级阶 段，其研究领域菲常广阔，涉及酶内容也菲常的多，许多关键技术都未取得突破性进展。兔 了提高信息系统的防护能力，应加强入侵检测技术的研究。为此，本文将分布式聚类用于入 侵检测模型的建立，研究基于分布式聚类的入侵检测方法 1 2 研究现状 聚类( c l u s t e r i n g ) 源予许多研究领域，包括数据挖握、统计学、模式识别、机器学习 等。在多元统计领域【1 7 1 ，聚类分析( 也叫群分析) 用来研究实现类型未知的样品的分类问 题，具体的方法有：系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、豳论聚类法、 聚类预报法等。其中，系统聚类法又细分为八种，即最短距离法、最长距离法、中间距离法、 重心法、类平均法、可变类平均法、可变法、离箍平方和。在模式识躐领域驻磁，有两种对 数据集进行聚类的非监督学习方法，即迭代的动态聚类法( 如k - 均值算法) 和非迭代的分级 聚类算法。在机器学习领域，聚类是无指导学习的一个例子。 县翦在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。 如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能 揭示的缭果。大体上，主要於聚类算法可以分为以下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) i i ”训 对予一个包含n 个数据对象或元缀盼数据库，构建l ( ( k n ) 个分组( 簇) ，搜褥每一个 簇中至少包含一个对象，每一个对象属于且仅属于一个簇，并鼠要求同一簇中的对象越接近 越好、不同簇中的对象越远越好。对于给定k 值，算法首先给出一个初始的分缝，以后通过 反复迭代来改变分组，使褥每一次迭代后的分组方案都较前一次好。分组方案的好坏用一个 目标函数来衡髓，算法进行反复迭代的过程就是最优化目标函数的过程，因此划分方法也称 为最优化方法。该类方法有k - m e a n s 算法、p a m 算法、c l a r a 算法、s t l 姝算法等。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) t “叱m 层次方法对给定数据对象集合进行层次的分瓣，壹裂满足终壹条箨药止。根据层次分解 是自底向上还是自顶向下形成，层次聚类的方法可以进一步分为凝聚和分裂。 凝聚方法又称自底向上昀方法，开始时将每个对象作为单独的一个组然后栩继的合并裰 近的对象或组，直到合并为一个组或达到终止条件。终此条件可以是簇的数目，或者是进行 合并的闽值。该类方法有b i r c h 算法、c u r e 算法、r o c k 算法等。 分裂方法又称自顶向下的方法，开始时假定所有的对象熙于一个组，在每一步迭代中， 根据分裂具有最大相异性的对象原则，将组分裂为更小的组，直到每一个组中只包含个对 象或至l 达终丘条件。终止条俘可以是簇的数罄，或者是进行分裂的阙鏖。该类方法有a r h p 算法、p d d p 算法等。 层次聚类的缺陷在予，一旦一个步骤( 合并或分类) 完成，它就不能被撤消，因而不裁 更正错误的决定。为弥补分鳃与合并的不足，层次方法经常要与其它聚类方法棚结合，如循 环定位；或者利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优 化：或者利用圈定数目童表对象来表示摺应聚类，然后对各聚类按照指定量( 向聚类中心) 3 南京师范大学硕士学位论文分布式聚类及其在入侵检测中的应用研究 进行收缩；还有的利用聚类间的连接进行聚类合并，在层次聚类时构造动态模型。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 争驯 基于密度的聚类方法的提出是为了发现任意形状的聚类结果。其主要思想：只要临近区 域的密度超过某个阈值，就继续聚类，最终相对高密度的区域被相对低密度的区域分割开来 形成簇。这样的方法可以用来过滤“噪声”，离群点等发现任意形状的聚簇。典型的基于 密度的方法包括：d b s c a n 算法、o p t i c s 算法、g d b s c a n 算法、d b c l a s d 算法等。 ( 4 ) 基于网格的方法( g a d b a s e dm e t h o d ) ”u j 。 基于网格的聚类方法采用一个多分辨率的网格数据结构，把对象空间量化为有限数目的 单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。这种方法的主要优点 是处理速度很快，其处理时间与数据集的规模大小无关，只与量化空间中每一维的单元数目 有关。典型的这类方法包括s t i n g 算法、w a v e c l u s t e r 算法、o p t i g r i d 算法等。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 1 3 1 1 基于模型的方法事先为每个簇假定了一个模型( 可能是数据点在空间中的密度分布函数 或者其他) ，然后寻找数据对给定模型的最佳拟合。该方法基于如下假定：目标数据集是根 据潜在的概率分布生成的。该类方法主要有两类：统计学方法和神经网络方法。统计学方法 有c o b w e b 算法、c l a s s i t 算法、a u t o c l a s s 算法等；神经网络方法有竞争学习法和自组 织特征映射法( s o m ) 等。 传统的数据挖掘方式是集中式的，在当前很多分布式计算环境( 例如：因特网、企业内 网、局域网、高速无限网络和传感器网络) 中不能很好工作。分布式数据挖掘是随着数据挖 掘领域的不断延伸而扩展出的一个新领域。目前，分布式数据挖掘研究较少，现有的分布式 数据挖掘算法大多是传统数据挖掘算法在分布式环境下的扩展与改进。文献【9 ，3 2 3 4 探讨 了分布式数据库环境下聚类的相关问题。 分布式数据挖掘系统按照结构可分为两大类：紧密耦合系统和松散耦合系统。紧密耦合 系统主要是指多处理器的并行系统，即基于共享内存的多处理器并行模式或有特殊的通信线 路连接的分布式非共享的并行系统。在松散耦合系统中，每个c p u 拥有独立的存储器，相互 间通过通信线路来连接，也就是我们所说的局域网、广域网、互联网等。松散耦合系统按照 其组成的计算机种类又可分为同构型分布式系统和异构型分布式系统。实际上我们更常见的 是异构型分布式系统。 在分布式环境下，影响数据挖掘执行的不仅仅是网络通信模型，数据的分布也对挖掘策 略有着重要影响。根据数据的集中或分散，我们可以采用两种策略，即任务并行化方法和数 据并行化方法。 在任务并行化挖掘中，各处理器面对的是一个数据整体。挖掘任务被划分为若干子任务 分配给各处理器，各处理器根据全局数据独立获得各自的局部知识，最后将各局部知识合并 为全局知识。任务并行化挖掘的优点是各处理器独立完成各自任务，减少了通信量。它的问 题是如何平衡各处理器的负载。解决的办法是采用多次分配任务的方法，即任务的划分不是 一次性的，而是每次根据计算的中间结果重新划分任务，以使各处理器负载得到平衡。显然， 这种办法所付出的代价是通信开销。因此多次划分的方法较适合紧耦合的分布式系统。 在数据并行化方法中，全局数据被分为若干区域，各处理器有自己的局部数据。根据不 同的网络模型，可以采取两种方法：同步方式和异步方式。在同步的方法中，各处理器必须 同步以构造相同的模式，为达到这一目的，各处理器必须交换信息同步挖掘。这种方法通信 量大，单个处理器的开销较小，较适合紧耦合的结构。在异步的方法中，各处理器根据本地 数据集获得局部知识，然后归并各局部知识以获得全局知识。在这种方式下，各处理器不必 多次交换同步信息，通信量较小，适合松耦合结构。但在这种方式下，归并各局部知识时会 带来处理器的额外开销，它的本地开销要比同步方式大。 4 南衷魉范大学硕士学位论文 分森式聚类及其旋入侵捡测孛豹应用研究 分布式数攥挖掘爨有集中式数据挖掘觞特性，褥对，由于它的分布性，歇丽基有了更多 新的特点。 ( 1 ) 全局挖掘霸局部挖掘 和任何分布式系统一样，在分布式数据挖掘系统中，数据的物理位置可以是分散的，单 个节点的数据在逻辑上是一个整体。对于一个数据挖掘任务而富，如果它是针对所有数据的， 萸| j 称为全局挖掘；如果它是针对本地数据，则稼为岗部挖掘。对于一个局部挖撼，它既可以 独囊于全局挖捌，也可以作为全局挖掘的一部分；而对予一个全局挖掘，它既是一个不可分 割的整体，毽可以由若干髑部挖蒎通过一定的方式组合在一起。 ( 2 ) 全局知识和局部知识 全局挖掘的结果，称为全局知识；局部挖掘的结粟，称为蜀部翔识。全局知识并不是局 部知识简单的合并，局部知识必须经过一定方式的组合和调整才能构成全局知识。任何一部 分局部知识的变化，都将影响到全局知识的变化。 0 ) 挖掘部件的分毒 这里的挖掘部件可以理解为个挖掘算法。在分布式数据挖掘系统中，不但数据、知识 是分布存储豹，各挖勰部件也可分布。它包括两静情况：( 参备节点宥独立完整熊挖掘郯馋。 这种情况下，备挖掘部件可以独立完成挖掘任务，获得局部知识，也可以综合这魑局部知识， 获得全局知识。备节点只存放部分挖掘部件，由它们可以构成一个完楚的挖掘部件。这 种情况下。各节点的挖掘部传不能独立完成挖掘任务，必须相互配合，共网完成全局知识的 获墩 ( 4 ) 挖掘的透明性 对于一个全局挖掘过程而言，它涉及到分布在各节点的数据。而对于一个全局用户来说， 该过程应该是透明的。如果分布式数据挖撼系统楚建立在分布式数据库系统基勰之上的，那 么，全局挖掘过程由分布式数据库中的全局概念模式支持，挖掘的透明性是依靠分布式数据 库实现的。如果分布式数据挖掘系统是建立在多个数据库系统之上，郎没有全局概念模式熊 支持，则它必须自己实现挖掘过程的透明。对于无全局模式支持的情况，挖掘透明性是通过 任务的分解和结果的合并实现的。 ( 5 ) 并行他挖掘 在分布式系统中，数据挖掘算法效率与通信模型和数据的分布密切相关。对于不同的体 系结构，必须采用不阕的并行挖掘策略。例如，目前的些并行数据挖撼算法，如f d m 等， 它们大多是用于多处理器的紧耦合方式，对于松耦合方式，如在l a n 等环境下，由予带宽、 赞输延迟等褥络参数的不褥，这些并行数据挖掘算法- 并不适用。因就，在分布式环境中，应 根据不周的通信模型，选择适当的数据挖掘算法。同时，根据数据分布的不同，也应选择相 应的并行化策略。 ( 6 ) 知识的增量式更新 当数据发生变化或挖掘时的参数发生变化，都需要更新挖掘结果。如果将挖掘过程重新 运行一遍，代价无疑是非常昂贵的。通常豹办法是，充分利用已有的挖掘结果，只针对改变 的部分数据或参数进行挖掘，然后调整修改已有的规则。在分布式数据挖掘中，知识的更新 主要是指对全局知识的更新，主要有鹾种方式：( d 根据数据竣参数的变化，点接对已有的 全局知识进行增量式更新。根据数据或参数的变化，先对局部知识进行增量式更新，然 后根据局部知识的变化，调整更新全局知识。 ( 7 ) 数据的实时挖撼 分布式数据挖掘中，挖掘是分布在各节点进行的，相对预先收集数据再集中处理的挖撅 方式，功能的分布使分布式数据挖越系统熊适合动态的、变化较抉的数据懿分析处理。 5 毒衰鳎筑大学须圭学缎论文 分奄式聚类及其在入爱硷溯巾豹斑霸研究 通常情况下，个分布式数据挖掘系统至少应该包含以下功能： ( 1 ) 数据的预处理。主要完成数据的获取和整理工作，包括获取、过滤、翻译、优化、 元数据生成等。 ( 2 ) 任务酶解释和分解。主要完成对挖掘经务的解释，势将其划分为若干予任务，包括 接收、解释、策略选择、分解和发送。 ( 3 ) 挖掘的执行。选择并执行分布式数据挖搠算法。 ( 4 ) 规则豹合并。主要指将各节点相应挖掘算法所产生的局部挖掘结采通过适当的方式 合莽隽阕户所需的全局知识。 ( 5 ) 挖掘任务的控制。主要是指控制和监视整个数据挖掘任务的执行过程，通过用户的 干预和交互，调整挖掘任务的执行。同时还包括将挖掘任务的执行过程和当前状态，以可视 化的方式呈现给j 户。 西) 规则的赢魅毽。主要是对挖掘的结果进行处理，包括表现、清洗、存储。 ( 7 ) 规则的增鬣式维护。负责全局知识和局部知识的维护。警数据库上的数据发生变化 时，骤根据变化更新局部知识和全局知识，同时，要保证系统全周知识和局部知识的一致性。 ( 8 ) 其它。除以上各部分功能外，一个分布式挖掘系统还应具备其它一些功能，如用户 管理、教障诊断、任务恢复、安全性等。 弧m 系统是美国哥伦眈亚大学s a l v a t o r e s 教授帮佛罗璺达理工学院p h i l i p c 教授 等人设计的一个分布式数据挖掘系统，该系统可以从各个独立金融机构的数据库中挖掘出关 于诈骗的知识模式 重。3 研究内容 本文以江苏省自然科学基金项目“基于分布式数据挖掘的分布式入侵榆测技术研究 ( b k 2 0 0 5 1 3 5 ) ”为背景开展研究，对分布式聚类算法及其在入侵检测当中的癍用作了一些 探讨，全文共分麓六章，各章的穗美壳容安捧魏下。 第一章阐述了分布式聚类的概念、产生背景岛些应用研究的进展，同时网顾了入侵检 测技术的发展历程。 第二章介绍了基于距离的分布式聚类算法。提出了高效的分布式k 均值聚类算法 d k - m e a n s 。该算法在站点阍只传送k 个聚簇傣息，有效降低了分布式聚类过程孛懿数据通 信鹫，并能达到与k 均值算法等效的聚类质量。瑷论分析及实验结果表明，d k m e a n s 是一 种有效可行的分布式聚类算法，对予高维数据集同样有效。此外，针对聚类数目难以确定的 问题，提出了分布式聚类算法仪d k m e a n s ，通过分割和合并聚簇将训练数据集划分成适当 数爨的聚簇而不必预设聚簇半径。实验结果表骥，算法o c - d k - m e a n s 是有效霹行的。 第三章介绍了蒸于密度鲶分布式聚类算法。针对算法d b d c 通信量大、效率低的缺点， 提出了一种基于密度的分布式聚类算法d b d c * 。有效降低了分布式聚类过程中的数据通信 量，全局聚类时综合考虑了各站点数据的分布情况，能够对任意形状分布的数据进行聚类。 实验结果表明，算法d b d c * 是一种有效可行的分布式聚类算法，对于高维数据集同样有效。 第图章阐述了入侵检测的相关内容。提出了一耪适用予入笈检测的数据预处理方法，定 义了类别型属性各取值之间的差异度使得在对训练集进行无靛督学习，生成检测模型过程 中，能够同时有效地处理数值型属性和类别型属性。理论分析表明我们所定义的类别型属性 值麓异度既保留了类别型属性各取值之问的本质特征，同时也没有改变数据集的原始维数。 实验结栗表骥，采耀我们的预处毽方法进行聚类所建立的入侵检测模型麓更有效的检测攻 击。此外，本章还提滋了一种基于分布式聚类的异常入侵检测方法i d - d c ，该方法建立在一 种无中心的多a g e n t 分布式体系结构之上，通过对训练集进行分布式聚类产生聚簇模型，采 6 南京师范大学硕士学位论文 分布式聚类及其在入侵检测中的应用研究 用基于双参考点的标识算法标记异常簇，不需要具有类别标签的训练集且可自动确定聚簇模 型的个数。实验结果表明，通过我们的分布式聚类算法建立的分布式入侵检测模型可有效检 测攻击。 第五章在j a 、，a 平台下设计并实现了基于a g e n t 的分布式入侵检测系统原型，在该系统 中实现了基于分布式聚类的入侵检测算法。 第六章对全文进行了总结，并且展望了分布式聚类的研究前景。 7 露窳戆范大学矮士攀彼论文 分豢式聚类及其在入整捡澜中鹃瘫霸耩究 第2 章基于距离的分布式聚类研究 2 1 概述 聚类分析就是在没有任何竞验知谈酶蘸提下，本着群物i 基类聚”的思想，将数据聚合成 不同的类，使得网类中的元素尽w 能相似，不阋类中的元素差别