小波聚类算法的研究及应用.pdf

《小波聚类算法的研究及应用.pdf》由会员分享，可在线阅读，更多相关《小波聚类算法的研究及应用.pdf（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大连理工大学 硕士学位论文 小波聚类算法的研究及应用 姓名：毕玲 申请学位级别：硕士 专业：软件工程 指导教师：吴国伟 20061217 大连理工大学硕士学位论文 摘要 随着全球信息化的发展，数据库中存储的数据量急剧增大，为了挖掘出隐藏在大量 数据之后的重要信息，数据挖掘技术的研究就成为了一种迫切的需要。聚类分析是数据 挖掘研究中最活跃的领域之一，用于将数据对象分组为多个类或簇，使得簇内对象尽可 能相似而簇间对象尽可能相异。聚类分析技术已经广泛研究了许多年，并应用于诸多领 域中，包括模式识别、数据分析、图像处理等领域。聚类分析技术可以帮助人们更快地 找到所需要的信息，在现实生活中有着重要的意义

2、。 由于传统聚类算法在低维空间小数据集中能够有效地进行聚类，但在高维大数据集 中，由于其数据的稀疏性，存在大量孤立点等问题，使得传统聚类处理的效果不理想。 本论文在分析各种经典的聚类算法的基础上，着重对基于小波分析的聚类分析技术( 简 称小波聚类算法，W a v e C l u s t e r ) 进行研究和改进。小波聚类算法非常有效，检测簇的计 算复杂度为0 ( N ) 。结果不受噪声影响，对输入顺序不敏感。算法可以在不同精度找到 任意复杂结构的簇，而且不用假设任意特定形状的簇。算法不需要关于簇数量的先验知 识。但是，估计簇的数量可以帮助选择合适的簇的结果。针对小波聚类的低维性进行了 算法改

3、进，改进后算法可适用于高维聚类，并对时间复杂度和空间复杂度进行了分析， 通过实验验证了算法的有效性。 论文最后把改进后算法应用到入侵检测系统当中，针对入侵检测系统的两个指标： 检测率、误检率进行仿真实验。实验结果证明改进后算法能有效提高入侵检测的检测率， 降低误报率。 关键词：数据挖掘；聚类分析；小波变换；入侵检测 小波聚类算法的研究及应用 R e s e a r c ha n dA p p l i c a t i o no fW a v e C l u s t e r A b s t r a c t A l o n g w i t ht h ed e v e l o p m e n to f

4、 g l o b a lc o m m u n i c a t i o n , t h en u m b e ro f s t o r a g eo f d a t a b a s e s u d d e n l yi n c r e a s e ，i no r d e r t om i n et h ei m p o r t a n ti n f o r m a t i o nh i d i n gb e h i n dt h el a r g ed a t a , t h e s t u d yo fd a t a b a s em i n i n gt e c h n o l o g y

5、b e c o m eai n s t a n tr e q u i r e C l u s t e r i n l n ga n a l y s i s ，w h i c hi s a ni m p o r t a n td a t am m a g p r o b l e m , g r o u p st h ed a mi n t oc l a s s e so rc l u s t e r sS Ot h a to b j e c t s w i t h i nac l u s t e rh a v eh i g l ls i m i l a r i t yi nc o m p a r

6、 i s o nt oo n ea n o t h e r , b u ta r ev e r yd i s s i m i l a rt O o b j e c t si no t h e rc l u s t e r s I th 舔b e e nw i d e l yu s e di nn k l l n c r O U Sa p p l i c a t i o n s , i n c l u d i n gp a t t e r n r e c o g n i t i o n , d a t aa n a l y s i sa n di l n a g ep r o c c s s i

7、 n g C l u s t e r i n ga n a l y s i st e c h n o l o g yc a nh e l p p e o p l er a p i d l yf i n dt h er e q u i r e di n f o r m a t i o n , i ti sv e r ys i g n i f i c a n ti nr e a lw o r l d T r a d i t i o n a lc l u s t e r i n gm e t h o d sc a nw o r ke 蚯c i e n t l yi nl O Wd i m e n s

8、 i o n a ld a t a I nh i 西 d i m e n s i o n a ld a t a , h o w e v e r , e f f i c i e n c ya n de f f e c to f t r a d i t i o n a lc l u s t e r i n gm e t h o d sa r en o tw e l l I x ，c a u s eo fd a t as p a r s i t y , d i s t a n c es i m i l a r i t ya n dm o r eo u t l i e ri nt h ed a t a

9、 I nt h i sp a p e r , b a s e d o na n a l y z i n ge v e r yk i n d so fc l a s s i c a lc l u s t e r i n gm e t h o d , i ti se m p h a s i z e do ns t u d y i n ga n d i m p r o v i n gt h ew a v e l e t - b a s e dc l u s t e r i n gt e c h n o l o g y ( s h o r tf o rW a v e C l u s t e r ) n

10、 地p r o p o s e d a p p r o a c hi sv e r ye f f i c i e n t , t h ec o m p u t a t i o n a lc o m p l e x i t yo f d e t e c t i n gc l u s t e r si nO U tm e t h o di s 0 ( b D n l er e s u l t sa r cn o ta f f e c t 村b yn o i s ea n dt h em e t h o di sn o ts e n s i t i v et ot h eo r d e ro f i

11、 n p mo b j e c t st ob ep r o c e s s e d W a v e C l u s t e ri sw e l lc a p a b l eo ff i n d i n ga r b i t r a r y s h a p ec l u s t e r s w i t hc o m p l e xs t r u c t u r e sa td i f f e r e n ts c a l e s ，a n dd o e sn o ta s S U l l l ea n ys p e c i f i cs h a p ef o rt h e c l u s t

12、e r s Ap r i o r i h l o w l e d g ea b o u tt h ee x a c tn u m b e ro fc l u s t e r si sn o tr e q u i r e di n W a v e C l u s t e r H O W e v c r , a l le s t i m a t i o no fe x p e c t e dn u m b e ro fc l u s t e r sh e l p si nc h o o s i n gt h e a p p r o p r i a t er e s u l to fc l u s

13、t e r s T h e n , i na l l u s i o nt ot h el O Wd i m e n s i o n a lp r o p e r t yo f W a v e C l u s t e r , i m p r o v et h em e t h o d T h ei m p r o v e dm e t h o dC a nu s i n gi nh i g hd i m e n s i o n a l c l l l s t e f i n 岛a n dt h e na n a l y s i st h et i m ec o m p l e x i t ya

14、 n ds p a c ec o m p l e x i t y T h er e s u l to f e x p e r i m e n tc 觚p r o v et h ee f f e c t i v i t yo f i m p r o v e dm e t h o d I nt h ee n d , i ti su s i n gt h ei m p r o v e dm e t h o di nt h eI n t r u s i o nD e t e c t i o nS y s t e m , i na l l u s i o n t ot h ed e t e c t i

15、o nr a t e ，t h ef a l s ea l a r mr a t e ，a n dp r o v i d e dw i t hc o m p u t e rs i m u l a t i o n s 1 1 1 e e x p e r i m e n tr e s u l tp r o v e st h a tt h ei m p r o v e dm e t h o dc a ne f f e c t i v e l ya 妇c et h ed e t e c t i o nm t e a n dr e d u c et h ef a l s ea l a r mr a t

16、e K e yW o r d s ：D a t am i n i n g ；C l u s t e r i n ga n a l y s i s ：W a v e l e tt r a n s f o r m ；I n t r u s i o nD e t e c t i o n I I 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确

17、的说明并表示了谢意。 作者签名：垡L 日搬亏：f 之：丝 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：毕西作者签名：芏! 呈 导师签名墨亟焦 迎立年丝月幽 大连理工大学硕士学位论文 1 绪论 1 1 研究背景和意义 2 0 世纪9 0 年代以来，随着信

18、息技术和数据库技术的迅猛发展，人们可以非常方便 地获取和存储大量的数据【”。面对大规模的海量的数据，传统的数据分析工具( 如管理 信息系统) 只能进行一些表层的处理( 如查询、统计等) ，而不能获得数据之间的内在 关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境f 2 】，人们迫切需要一种能 够智能自动地把数据转换成有用信息和知识的技术和工具，这种对强有力数据分析技术 的迫切需求使得数据挖掘技术应运而生。 数据挖掘( D a t aM i n i n g ，D M ) 是一门广义的交叉学科，汇聚了数据库，人工智能、 机器学习、统计学、模式识别、可视化、并行计算和神经网络等不同学科和领域，

19、近年 来受到各界的广泛关注。 聚类分析技术是一种重要的数据挖掘技术1 3 。它识别一个有限种类集合或簇集合， 从而描述数据。通过聚类，人们毹够识别密集的和稀疏的区域，因而发现全局的分布模 式，以及数据属性之间的相互关系。聚类分析技术已经广泛研究了许多年，并应用于诸 多领域中，包括模式识别、数据分析、图像处理等1 4 】。聚类分析技术可以帮助人们更快 地找到所需要的信息，在现实生活中有着重要的意义。 1 2 国内外研究现状 1 2 1 国外研究现状 目前，国外数据挖掘的发展趋势及其研究方法主要是对知识发现( K n o w l e d g e D i s c o v e r yi nD a t

20、a b a s e ，K D D ) 方法的研究。到目前为止，由美国人工智能协会主办的 K D D 国际研讨会已经召开了8 次，规模由原来的专题讨论发展到国际学术大会，研究 重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科 之间的相互渗透。此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊 物也纷纷开辟了K D D 专题或专刊。I E E E 的K n o w l e d g ea n dD a t aE n g i n e e r i n g 会刊率先在 1 9 9 3 年出版了K D D 技术专刊，所发表的5 篇论文代表了当时K D D 研究的最新成果

21、和 动态，较全面的论述了K D D 系统方法论、发现结果的评价、K D D 系统设计的逻辑方法 等。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知 识发现列为专题和专刊讨论。 小波聚类算法的研究及应用 聚类分析作为数据挖掘的一个研究重点，国外已经提出了许多算法，这些算法可分 为4 类：划分方法( P a r t i t i o n i n ga l g o r i t h m s ) ，层次方法( H i e r a r c h i c a la l g o r i t h m s ) ，基 于密度的方法( D e n s i t y - b a s e da l g

22、 o r i t h m s ) 和基于网格的方法( G r i d - b a s e da l g o r i t h m s ) ( 1 ) 划分方法( P a r t i t i o n i n ga l g o r i t h m s ) 划分方法建立一个有N 个对象的数据库，把它划分为K 个簇。一般我们首先以一 个初始划分开始，使用一种迭代控制策略优化目标函数。主要有两个方法；i ) k - 平均方 法，该算法中，每个簇用该簇中对象的重心表示；i i ) k - 中心点算法，该算法中，每个簇 用接近簇中心的一个对象表示。 P A M i s 使用k - 中心点算法识别簇。P A M

23、 首先在n 个对象中随机抽取k 个对象( 选 择对象) 作为聚类中心，将余下的n - k 个对象( 非选择对象) 依据与聚类中心距离或相 异程度最小原则划分到上述k 个聚类中。即如果O ，是未选择对象，D ，是中心点，如果 d ( D ，q ) - - m i n d ( O j ，q ) ，晓中心点集合) ，则D ，属于以q 为中心点的聚类。d ( D ，D f ) 表示D ，与q 对象之间的距离或相异程度。然后，从非选择对象中选择一个对象D 。来与 Q 交换，如果交换导致聚类质量提高，则用q 替换Q 作为中心点。P A M 用对象与整个 数据库作比较来找中心点，因此，它的处理时间很慢，一次

24、循环的时间复杂度为 O ( K ( N 一足) ) 2 ，算法的总时间复杂度是D ( ( 1 + 卢) 足( 一置) ) 2 ，卢是成功交换的次数。 为减少P A I M 算法的运算复杂度，C L A R A ( C l u s t e r i n gL A R g eA p p l i c a t i o n s ) 抽取数据 集的一小部分作为数据的样本，对样本做P A M ，从而找到样本的中心点。如果样本是 以非常随机的方式选取的，它应当足以代表原来的数据集合。C L A R A 的时间复杂度为 O ( K ( s + 置) 2 + K ( N 一置) ) ，其中S 为从n 个对象中随机抽

25、取的s 个对象。算法的有效性 取决于样本的大小C L A R A 在抽取的样本中搜索最佳的k 个中心点，如果任何取样得 到的中心点不属于最佳中心点，算法将不能得到最佳聚类。 N g 和H a n 提出了C L A R A N S ( C l u s t e r i n gL a r g eA p p l i c a t i o nb a s e do nR A N d o m i z e d S e a r c h ) 【6 1 ，这是一个改进的l p 中心点算法。算法将己知1 1 个对象，发现k 个中心点的过 程抽象为图的搜索过程。在这个图中( 表示为q ) ，一个节点是k 个对象的集合 0

26、 _ ， o I 朋。 ，吼，仉。是选择的中心点。图中所有节点的集合为： o k ，吨。 I O = t ， 仉是数据集中的对象 。如果两个节点仅有一个对象不同，则称此两节点是邻居。每个 节点有k ( n - k ) 个邻居。C L A R A N S 不检查节点的每个邻居，而是仅检查一个节点所有邻 居的样本，这是C L A R A N S 与P M 的区别。与C I A R A 不同，C L A R A N S 并不将它的 搜索限制在特定的子图范围内，而是搜索原始图瓯。C L A R A N S 是第一个应用聚类技 一2 一 大连理工大学硕士学位论文 术到空间数据挖掘的算法，它克服了大多数传

27、统聚类技术在大数据集上的缺点。虽然 C L A R A N S 比P A M 快，但它仍然很慢，文献阴中显示它的计算复杂度为Q ( 剧2 ) 。此 外，由于它的随机性，对于N 比较大的值，结果的质量不能保证。一般，簇结构比较复 杂时，k 中心点算法不能给出足够的空间信息。 ( 2 ) 层次方法( H i e r a r c h i c a la l g o r i t h m s ) 层次方法创建数据库的分解层次。分解层次可以表现为树状图 s I 。算法迭代地把数 据库分裂为更小的子集，直到满足一个终止的条件。层次方法不需要K 作为输入参数， 这就比划分方法更有利。缺点是必须指定终止条件。 B

28、 I R C H ( B a l a n c e dI t e r a t i v eR e a u c i n ga n dO u s t e d n gu s i n gH i e r a r c h i e s ) 9 1 使用层次数 据结构C F 树对增量和动态聚类非常有效。C F 树是高度平衡的树，它存储了层次聚类 的聚类特征。B I R C H 想用可用的资源产生最好的簇。可用内存是有限的( 比数据集的 大小少得多) ，想减少I O 的时间。B I R C H 中，数据库的一次扫描可以产生好的簇，更 多次( 可选) 的扫描可以改善聚类结果。所以B I R C H 的计算复杂度是0

29、( N ) 。B I R C H 也是第一个处理噪声的聚类算法。C F 树中的每个节点因为它大小的限制只能存储有限 数量的条目，所以C F 树节点并不总是对应于一个自然聚类。此外，对于相同数据的不 同输入顺序，它可能产生不同的簇，即它是顺序敏感的。另外，如果簇是“球”形的或 凸起的形状，B I R C H 聚类得很好；但是对于其他形状的，B I R C H 工作的不是很好。这 是因为它用了半径或直径的概念来控制聚类的边界。 C U R E ( C l u s t e I i n gu s i I l gR e p r e s e n t a t i v e s ) 【1 0 】是针对大型数据库

30、而设计的聚类算法， 不过该算法采取了介于基于中心点和基于所有对象聚类算法之间的中间策略，选择固定 数目的具有代表性的对象代表一个簇，这些代表对象较好地描述了簇的形状和尺寸。然 后，使用预先定义的收缩因子a 控制，将这些代表对象朝簇中心收缩。调节收缩因子口 可以使C U R E 针对不同类型的簇聚类。为了使算法能适用于大型数据库海量数据集的聚 类，C U R E 采取了两种技术。其一是随机采样技术。与B I R C H 采用的预处理技术不同， C U R E 采用随机采样技术从数据库中随机选择一定数目的对象聚类，而不是针对整个数 据集聚类。使用随机采样技术一方面聚类对象数显著减少，适合将数据装入

31、内存进行处 理，减少了算法的运行时间；另一方面，随机采样技术过滤掉大部分孤立点，并进一步 拉大了孤立点间的差异度，提高了聚类结果的质量。文献0 0 给出了在最大概率减少丢 失条件下，采样样本大小的计算方法。其二是分区聚类技术。将随机采样得到的样本空 间划分为P 个区域，每个区域包含n ，p 个对象，n 是杨本数。然后针对每个区域聚类， 直到聚类个数减至W ( p q ) ，q l 为止。C U R E 算法最坏情况下的时间复杂度是O ( n 2l o g m 。 小波聚类算法的研究及应用 n 是随机采样对象个数，而不是数据及对象数N 。对低维数据集，时间复杂度减少为 O ( n 2 ) 。 f

32、 3 ) 基于密度的方法( D e n s i t y - b a s e da l g o r i t h m s ) P a u w e l s 等人提出了一个无监督的聚类算法，通过构造反映数据点空间分布的密度 函数来找出簇【l l 】。他们通过两种方法修正无参数密度估计问题。首先，他们使用反确认 来选择围绕核心的适当宽度。第二，使用高斯差分( D O G s ) ，这可以更好的聚类，并 且不需要选择任意的分离点极限。这个方法可以找到任意形状的簇，而且不用假设潜在 的数据分布。算法成功地应用在颜色分割问题上。这个算法的计算复杂度非常大。所以 对于大数据库来说，这个算法不是很现实。 E s

33、t e r 等提出了D B S C A N ( D e n s i t yB a s c dS p a t i a lC l u s t e r i n g o f A p p l i c a t i o n w i t h N o i s e ) 方法【l2 】。它可以发现任意形状的簇。D B S C A N 的主要思想是：对于簇中的每个点，给 定半径的邻域至少包含最小数量的点，例如，邻域中的密度需要超过某些极限值。 D B S C A N 算法其优点为可以分割噪音并发现任意形状的簇；使用空间存取方法，对大 型数据库而言是高效的。其缺点为：对参数敏感；当有稠密点串连接两个簇时，算法将 两个簇

34、合并为一个簇；算法没有采取任何预处理手段，直接针对整个数据集计算，对大 型数据库而言，会导致I O 开销增大；没有考虑对象分布特性，当对象分布差异较大时， 得到的聚类结果质量不高；算法不能处理高维数据。算法使用R 树会达到更好的效果。 D B S C A N 的平均运行复杂度是D ( N l o g ) ，如果不采用空间索引，则算法复杂度为 O ( N 2 、，N 为对象数。 O P T I C S ( O r d e r i n gP o i n t sT oI d e n t i f yt h eC l u s t e r i n gS t r u c t u r e ) 【1 3 】算法

35、是对D B S C A N 算法的拓展，主要目的是解决许多数据集使用全局密度参数不能刻划其聚类结构特征的 问题。O P T I C S 没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个 簇次序( c l u s t e ro r d e r i n g ) 。这个次序代表了数据的基于密度的聚类结构。它包含的信 息，等同于一个宽广的参数设置范围所获得的基于密度的聚类。O P T I C S 与D B S C A N 不 同之处在于它不将对象分配到不同簇中，而是存储对象被处理的次序和将被扩展 D B S C A N 算法使用来分配成员到不同簇中的信息。O P T I C S 的时间复

36、杂度与D B S C A N 相近，约为D B S C A N 的1 6 倍。 ( 4 ) 基于网格的方法 目前，有很多算法将空间量化为有限数目的单元，所有操作都在量化空间上进行。 这些方法的主要特点是执行时间快速，主要体现在与数据对象数量无关。它只依赖于量 化空间中每一维上的单元数量。 - 4 - 大连理工大学硕士学位论文 W a n g 等提出了S T I N G ( S T a t i s t i c a lI N f o r m a t i o nG r i d - b a s e d ) ”1 算法用于空间数据挖 掘。他们使用层次结构把空间区域划分成矩形单元。在单元中存储对象的每个数

37、字属性 的统计参数( 例如，平均值、方差、最小值、最大值、分布类型等) 。S T I N G 通过检查 一次数据库来计算单元的统计参数，因此产生簇的时间复杂度是O ( N ) 。之前其他的算 法没有说明聚类信息如何用来做一个查找或新对象如何加入到簇中。在S T I N G 中，网 格的层次结构用来处理这样的问题。在产生层次结构后，查找的响应时间是0 ( K ) ，其 中K 是最底层瞬格单元的数量【7 l 。一般K 心甜时算法比较快。但是，在层次中，不考虑 子单元与用来构造母单元的邻域单元间的空间关系。这就是导致簇形状单一的原因，即 所有的簇边缘不是水平的就是竖直的，没有斜的。尽管算法处理时间很

38、快，但这降低了 簇的质量和精确度。 X u 等提出了D B C L A S D ( D i s t r i b u t i o nB a s e dC l u s t e r i n go fL A r g e S p a t i a l D a t a b a s e s ) 。D B C L A S D 假设簇中的点均一地分布。对于簇中的每个点，检测不在簇 中的最近的点。定义最近邻域集为簇中每个点闯的所有距离和离它们最近的簇外的点的 距离的集合。则簇为有必要信任级的预计分布的最近邻域集。只要结果簇的最近邻域集 符合预计分布，D B C L A S D 就通过邻域点递增的增加初始簇。D B

39、C L A S D 可以找到任意 形状的簇。D B c L A s D 不需要输入参数来聚类。X u 的实验结果显示它比D B S C A N 慢。 因为它假设簇中的点均一地分布，所以不能应用在很多领域。 1 2 2 国内研究现状 与国外相比，国内对数据挖掘的研究稍晚，力量相对较小。国内从事数据挖掘研究 的人员主要在大学，也有部分在研究所或公司。所涉及的研究领域很多，一般集中于学 习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研究。1 9 9 9 年，亚太 地区在北京召开的第三届P A I D 会议收到1 5 8 篇论文，空前热烈。目前进行的大多数 研究项目是由政府资助进行的，如果

40、加自然科学基金、8 6 3 计划、“九五”计划等，数 据挖掘的研究和应用受到了学术界、实业界和政府部门的越来越多的重视。最近两年， 数据挖掘成为了一个熟点，各个大学都开设了数据挖掘课程，数据挖掘方面的书籍也涌 现了很多，有翻译国外的，也有很多国内自己写的。很多移动公司、电信公司、银行都 在进行数据挖掘项目的实验研究。 在国内对聚类分析算法的研究主要是对已有聚类算法进行改进，如杨燕等在对蚁群 算法的改进方面，提出了一种多蚁群聚类组合算法M A C C A 1 5 ；周水庚等人在对 D B S C A N 算法的改进方面，提出了S D B S C A N 1 q ；孔锐等人提出了基于核的K - 均

41、值聚 类【1 7 1 ；汪加才等人提出了V R 2 S O M t l 柳等等。 小波聚类算法的研究及应用 1 3 论文主要内容 本文所研究的小波聚类算法是一个基于网格的算法。此算法非常有效，尤其对于大 数据库。检测簇的计算复杂度为0 ( N ) 。结果不受噪声影响，对输入顺序不敏感。算法 可以在不同精度找到任意复杂结构的簇，例如凹形或嵌套形，而且不用假设任意特定形 状的簇。算法不需要关于簇数量的先验知识。但是，估计簇的数量可以帮助选择合适的 簇的结果。针对小波聚类的低维性进行了算法改进，改进后算法适用于高维聚类，通过 进行实验验证了算法的有效性。论文最后把改进后算法应用到入侵检测当中，针对入

42、侵 检测系统的两个指标：检测率、误检率进行仿真实验。实验结果证明改进后算法能有效 提高入侵检测的检测率，降低误报率。 一6 一 大连理工大学硕士学位论文 2 聚类技术 聚类( C l u s t e r i n g ) 就是按照某个特定标准把一个数据集分割成不同的类或簇 ( C l u s t e r ) ，使得在同一个簇内的数据对象的相似性尽可能的大，同时不在同一个簇中 的数据对象的相异性尽可能的大。也就是说，聚类后同一类别的数据尽可能的聚集在一 起，而不同的数据尽量分离。聚类分析是数据挖掘的一个重要方法，在许多领域都是得 到了广泛的研究和应用。 2 1 聚类的定义 聚类可以定义如下【1 9

43、 】：在数据空间A 中，数据集X 由许多数据点( 或数据对象) 组成，数据点蕾= ，劫) A ，t 的每个属性( 或特征、维度) x , j 既可以是数值型 的，也可以是枚举型的。数据集x 相当于是一个N d 矩阵。假设数据集X 中有N 个对 象工。( i - 1 ，N ) 。聚类的最终目的是把数据集x 划分为k 个分割C ( m - - 1 ， k ) ，也 可能有些对象不属于任何一个分割，这些就是噪声e 。所有这些分割与噪声的并集就 是数据集x ，并且这些分割之间没有交集，即X = C 。u u C ku G 且c ln C j = 妒( f ，) ， 这些分割C 就是聚类。 聚类分析的应

44、用非常广泛，比较典型的应用有：模式识别，在地理信息系统( G I S ) 中，通过聚类发现特征空间来建立主题索引；空间数据分析；图像处理：文档分类；通 过分析W e b 日志数据来发现相似的访问模式的。 具体应用如：在市场营销方面，帮助市场人员发现顾客中的不同群体，并且概括出 每一类消费者的消费模式即习惯，然后用这些知识来制定出目标明确的销售方案；在保 险行业中，对购买汽车保险的客户，标识那些有较高平均赔偿成本的顾客：在城市规划 中，根绝类型、价格、地理位置等来划分不同类型的住宅；在地震研究中，根据地质断 层的特点，把已观测到的地震中心分成不同的类；在生物学中，辅助研究动、植物的分 类，可以用

45、来分类具有相似功能的基因，还可以用来发现人类中的一些潜在的结构等； 在地理方面，从数据库中识别出具有相似土地用途的区域，从一个城市的房地产信息数 据库中，根据房型、房价及地理位置分成不同的类等等。 2 2 聚类算法的要求 聚类是一个富有挑战性的研究领域，研究主要集中在聚类算法的可伸缩性、聚类复 杂形状和类型数据的有效性、高维聚类分析技术以及针对大型数据库中混合数值和分类 数据的聚类方法，对聚类算法的典型要求只要有 ： 下几个方面： 小波聚类算法的研究及应用 ( 1 ) 可伸缩性 许多聚类算法在小于2 0 0 个数据对象的小数据集合上工作得很好；但是，一个大规 模数据库可能包含几百万个对象，在这

46、样的大数据集合样本上进行聚类可能会导致有偏 差的结果。可伸缩性要求算法要能够处理大数据量的数据库对象，比如处理上百万条记 录的数据库。这就要求算法的时间复杂度不能太高。聚类算法对小数据集和大规模数据 既要同样有效。 ( 2 ) 处理不同类型属性的能力 许多算法被设计用来聚类数值类型的数据，但是在应用当中，可能要求聚类其他类 型的数据，例如布尔型、枚举型、序数型、混合型等。即算法不仅要能处理数值型字段， 还要有处理其它类型字段的能力。 ( 3 ) 能发现任意形状的聚类 许多聚类算法采用基于欧氏距离或者曼哈坦距离度量方法，这一类算法发现的聚类 通常是一些球状的、大小和密度相近的类，但在实际应用中，

47、现实数据库的聚类可以是 任意形状的。故要求算法有发现任意形状聚类的能力，比如球形的、嵌套的、中空的等 任意复杂形状和结构的聚类。 ( 4 ) 使决定输入参数的领域知识最小化 很多聚类算法都要求用户输入一些参数，例如需要发现的聚类书对结果的支持度、 置信度等，聚类分析的结果通常都对这些参数很敏感。而且对于高维数据这些参数又是 难以确定的。这样就加重了用户的使用负担，使得分析的结果很难控制。聚类算法要尽 可能地减少用户估计参数的最佳取值所需要的领域知识。 ( 5 ) 能够有效地处理噪声数据 现实数据库中常常包含有异常数据，例如孤立点、空缺、未知数据或者错误的数据。 有一些聚类算法可能会对这些数据很

48、敏感，可能导致低质量的聚类结果。聚类算法要能 处理现实世界的数据库中普遍包含的异常数据。 ( 6 ) 对于输入记录的顺序不敏感 有些算法对记录的输入顺序非常敏感，比如对同一个数据集，将它以不同的顺序输 入到同一个分析算法中，得到的结果差别很大，这是我们不希望的。应该开发出对不同 的次序地记录输入应具有相同聚类结果的聚类算法。 ( 7 ) 高维性 一个数据库或者数据仓库都有很多的字段或者说维数，一些算法在处理维数比较少 的数据集时表现不错，例如2 ，3 维的数据，人的理解能力也可以对2 、3 维数据的聚类 分析结果的质量做出较好的辨别。但对于高维数据就无能为力，所以对高维数据的聚类 一8 一 大

49、连理工大学硕士学位论文 是很具有挑战的。聚类算法不仅要擅长处理低维的数据集，而且要能够处理高维的数据 集。 ( 8 ) 基与约束的聚类 现实的应用中总会出现各种其他的限制，我们希望聚类算法可以在考虑这些限制的 情况下仍有较好的表现。聚类结果既要满足特定的约束，又要具有良好的聚类特性。 ( 9 ) 可解释性和可用性 聚类的结果最终都要面向用户，用户希望聚类结果应该是容易解释和理解的，并且 是可用的。这就要求聚类算法必须与一定的语义环境及语义解释相关联。 2 3 聚类分析中的数据类型 本节，研究在聚类分析中经常出现的数据类型，以及如何对其进行预处理。假设要 聚类的数据集合包含1 1 个数据对象。许多聚类算法选择如下两种有代表性的数据结构： 数据矩阵：它用P 个变量( 也称为度量或属性) 来表现n 个对象。这种数据结构是关系 表的形式，或者看成n * p 的矩阵。 1 x I ，二而， x n x 0 x 9 x n l x q x 图2 1 数据矩阵 F 嘻2 1D a m r n a 俩x 相异度矩阵：存储n 个对象两两之间的近似性，表现形式是一个n * n 维的矩阵。 O d ( 2 ，1 ) 0 d ( 3 ，1 ) d O ，2 ) 0 d ( n ，1 ) d 伽，2 ) 0 图2 2 相异度矩