（计算机软件与理论专业论文）基于特征点选择的聚类算法研究与应用.pdf

、j1一 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：罐! 坌生日期：碰：笙：主 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本入授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丞! 至! 鱼竺导师签名 -lp 1j1j 山东大学硕士学位论文 目录 摘要i a b s t r a c t ： 第一章绪论1 1 1 研究背景及意义1 1 2 国内外研究现状2 1 3 当前聚类分析研究中存在的问题一4 1 4 论文的主要内容5 1 5 论文的组织结构5 第二章聚类分析一7 2 1 聚类分析的基本概念7 2 1 1 聚类的定义7 2 1 2 数据挖掘算法对聚类的典型要求8 2 1 3 相似性的度量方法9 2 2 聚类分析评价标准1 0 2 3 聚类分析中的数据类型1 2 2 3 1 区间标度变量1 2 2 3 2 二元变量1 3 2 3 3 标称型变量1 4 2 3 4 序数型变量( o r d i n a l ) 1 4 2 3 5 比例标度型变量( r a t i o s c a l e d ) 1 5 2 3 6 混合类型的变量1 5 2 4 主要聚类算法1 5 2 4 1 划分方法1 6 2 4 2 层次方法1 7 2 4 3 基于密度的方法1 8 2 4 4 基于网格的方法1 8 ，l r l 山东大学硕士学位论文 2 4 5 基于模型的方法1 9 2 5 本章小结1 9 第三章基于特征点选择的聚类2 1 3 1k - m e a n s 聚类算法分析2 l 3 2 基于特征点选择的聚类2 3 3 3c f p s 算法2 5 3 4 实验分析2 6 3 5 结论3l 3 6 本章小结3l 第四章基于特征点选择的聚类算法在入侵检测中的应用3 2 4 1 入侵检测技术介绍3 2 4 2 基于聚类的入侵检测系统3 4 4 2 1 基于聚类的入侵检测系统的优点3 4 4 2 2 入侵检测对聚类分析算法的性能要求3 5 4 3 实验分析3 6 4 3 1 数据源说明及分析3 6 4 3 2 数据预处理4 0 4 3 3 仿真实验结果与分析4 2 4 4 本章小结4 4 第五章总结与展望4 5 参考文献4 7 致谢，5 3 攻读学位期间发表的学术论文目录5 4 jj 山东大学硕士学位论文 t a b l eo fc o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h c h a p t e r1i n t r o d u c t i o n j 1 1 1b a c k g r o u n da n d m e a n i n g 1 1 2c u r r e n tr e s e a r c hs t a t u sa th o m ea n da b r o a d 2 1 3s h o r t c o m i n g so f c u r r e n tr e s e a r c hi nc l u s t e r i n ga n a l y s i s 4 1 4m a i nc o n t e n t 5 1 5o r g a n i z a t i o n 5 c h a p t e r2c l u s t e r i n ga n a l y s i s ，7 2 1b a s i cc l u s t e r i n ga n a l y s i sc o n c e p t s 7 2 1 1c l u s t e r i n gd e f i n i t i o n 7 2 1 2t y p i c a lr e q u i r e m e n to f c l u s t e r i n gi nd a t a m i n i n g 8 2 1 3s i m i l a r i t e sm e a s u r e m e n t 9 2 2e v a l u a t i o ns t a n d a r d so f c l u s t e r a n 甜y s i s 1 0 2 3t y p e so f d a t ai nc l u s t e r i n ga n a l y s i s 1 2 2 3 1i n t e r v a l s c a l e dv a i l a b l e s 1 2 2 3 2b i n a r yv a r i a b l e s 1 3 2 3 3n o m i n a l a b l e s 1 4 2 3 4o r d i n a lv a r i a b l e s 。1 4 2 3 5r a t i o s c a l e dv a r i a b l e s 1 5 2 3 6v a r i a b l e so f m i x e dt y p e s 1 5 2 4m a i nc l u s t e r i n ga l g o r i t h m 1 5 2 4 1p a r t i t i o n i n gm e t h o d s 1 6 2 4 2h i e r a r c h i c a lm e t h o d s 。1 7 2 4 3d e n s i t y - b a s e dm e t h o d s 1 8 卜l r 山东大学硕士学位论文 2 4 4g r i d b a s e dm e t h o d s 1 8 2 4 5m o d e l b a s e dm e t h o d s 1 9 2 5s u m m a r y 1 9 c h a p t e r3c l u s t e r i n ga l g o r i t h mb a s e do nf e a t u r ep o i n ts e l e c t i o n 2 1 3 1k m e a n sc l u s t e r i n ga n a l y s i s 2 1 3 2c l u s t e r i n ga l g o r i t h mb a s e do nf e a t u r ep o i n ts e l e c t i o n 2 3 3 3t h ec f p sa l g o r i t h m 2 5 3 4e x p e r i m e n t sa n dr e s u l ta n a l y s i s 2 6 3 5c o n c l u s i o n s 3 1 3 6s u m m a r y 3 1 c h a p t e r4a p p l i c a t i o no fc f p sa l g o r i t h mi ni n t r u s i o nd e t e c t i o n 3 2 4 1i n t r o d u c t i o no f i n t r u s i o nd e t e c t i o nt e c h n o l o g y 3 2 4 2i n t r u s i o nd e t e c t i o ns y s t e mb a s e do nc l u s t e r i n g 3 4 4 2 1t h es u p e r i o r i t yo f i n t r u s i o nd e t e c t i o ns y s t e mb a s e do nc l u s t e r i n g 3 4 4 2 2r e q u i r e m e n to f i n t r u s i o nd e t e c t i o nb a s e do nc l u s t e r i n g 3 5 4 3e x p e r i m e n t sa n dr e s u l ta n a l y s i s 3 6 4 3 1d e s c r i p t i o na n da n a l y s i so f t h ed a t as o u r c e 3 6 4 3 2d a t ap r e p r o c e s s i n g 4 0 4 3 3s i m u l a t i o ne x p e r i m e n t sa n dr e s u l ta n a l y s i s 4 2 4 4s u m m a r y 4 4 c h a p t e r5c o n c l u s i o na n do u t l o o k 4 5 r e f e r e n c e ：4 7 a c k n o w l e d g m e n t 5 3 a c a d e m i cp a p e r sp u b l i s h e d 5 4 1 山东大学硕士学位论文 摘要 随着全球信息量的爆炸式的增长，数据挖掘技术已成为新世纪计算机 科学技术的研究热点。聚类分析是数据挖掘的最主要的功能之一，聚类就 是将数据对象分组为多个类或簇，在同一个簇中的对象之间具有较高的相 似度，而不同簇中的对象差别较大。聚类分析主要解决的问题是如何在没 有先验知识的前提下，实现满足这种要求的聚簇的集合。到目前为止，人 们提出了各种各样数据挖掘的聚类算法，但这些算法仅适用于特定的应用 以及用户，而且它们在理论和方法上还有待完善，甚至还有严重的不足之 处。k m e a n s 聚类算法在数据挖掘领域具有非常重要的应用价值。但随着应 用领域的拓展和新的问题需求，k m e a n s 本身存在的局限越来越突出。在应 用中聚类个数通常根据用户视觉和使用方便性假定，但用户往往不能准确 的确定聚类个数，聚类个数一旦确定在整个聚类过程中都不能更改，最终 得到的簇的数目就是初始的聚类个数。并且初始聚类中心的选取不同也同 样会影响聚类算法的效果，因此用户一般不会得到准确的聚类。k m e a n s 算 法这两个重要缺点严重影响了它在聚类算法中的应用范围。 本文在分析了当前各种聚类算法的思想和方法的同时，针对k m e a n s 算 法存在的一些缺陷和不足，提出了基于特征点选择的聚类算法c f p s ( c l u s t e r i n ga l g o r i t h mb a s e d0 1 1f e a t u r ep o i n ts e l e c t i o n ) 。c f p s 算法同样也 属于划分聚类算法，c f p s 算法在聚类过程中引入了适应度函数，算法根据 对象间的距离和适应函数的值进行聚类和调整聚类个数k ，c f p s 算法不用选 取初始聚类中心，算法开始时每个聚类对象自成一类，因此聚类结果稳定， 算法不会陷入局部最优的聚类结果。实验结果表明c f p s 聚类算法在数据挖 掘中与其它聚类算法相比，c f p s 算法提高了聚类精度和效率。因此用户可 以方便地使用本文提出c f p s 算法，不需要配置复杂的参数，并且能得到更 好或一样的结果 聚类分析及相关技术在入侵检测中的应用是当前入侵检测研究的一个 r l l 卜r k 山东大学硕士学位论文 热点，本文尝试将c f p s 聚类算法应用于入侵检测系统中，并使用k d dc u p 1 9 9 9 数据集作为实验数据，对k m e a n s 算法与c f p s 算法进行了仿真实验，算 法分析与实验结果表明c f p s 算法具有较好的检测性能，可以获得较高的检 测率和较低的误报率，该方法克服了传统k m e a n s 算法需要人为确定k 值和 受初始聚类中心点选择影响的问题。 关键词：数据挖掘；聚类分析；k 一均值；入侵检测 i i ，】j， 、1jj 1 月 i n t oc l a s s e so rc l u s t e r s ，i nw h i c hs i m i l a ro b j e c t sa r eg r o u p e di nt h es a m ec l u s t e r w h i l ed i f f e r e n to b je c t sa r ei nd i f f e r e n tc l u s t e r s c l u s t e r i n gp r o c e s s e sa r e a l w a y s c a r r i e do u ti nt h ec o n d i t i o nw i t h o u tp r e k n o w nk n o w l e d g e ，s ot h em a i nt a s ki s t os o l v et h a th o wt o g e tt h ec l u s t e r i n gr e s u l ti nt h i sp r e m i s e u pt op r e s e n t ， m a n yc l u s t e r i n ga l g o r i t h m sh a v eb e e np r e s e n t e d ，b u tt h e s ea l g o r i t h m sa r eo n l y s u i t e d s p e c i a lp r o b l e m sa n du s e r s f u r t h e r m o r e ，t h e ya r ei m p e r f e c tb o t h t h e o r e t i c a l l ya n dm e t h o d o l o g i c a l l y ，e v e ns e v e r ef a u l t t h ek m e a n sa l g o r i t h m h a st h ee x t r e m e l yi m p o r t a n ta p p l i c a t i o nv a l u ei nd a mm i n i n g ，b u tw i t ht h e a p p l i c a t i o nd e v e l o p m e n ta n dt h en e wq u e s t i o nd e m a n d ，k m e a n sl i m i t a t i o n s b e c o m ei n c r e a s i n g l yp r o m i n e n t t h en u m b e ro fc l u s t e r si n a p p l i c a t i o n sa r e u s u a l l yb a s e do nt h eu s e ra s s u m e s b u tu s e r so f t e nd on o ts e tt h ee x a c tn u m b e r o fc l u s t e r s t h en u m b e ro fc l u s t e r so n c eh a v eb e e s t a b l i s h e d ，i nt h ew h o l e c l u s t e r i n gp r o c e s sc a nn o tb ec h a n g e d ，t h ef i n a lc l u s t e r sn u m b e ri st h ei n i t i a l n u m b e ro fc l u s t e r s a n ds e l e c td i f f e r e n ti n i t i a lc o r en o d e so ft h ed a t aa l s ow i l l a f f e c tt h ee f f e c t i v e n e s so fc l u s t e r i n ga l g o r i t h m ，s ot h eu s e rg e n e r a l l yw i l ln o t g e ta na c c u r a t ec l u s t e r i n g t h e s et w oi m p o r t a n ts h o r t c o m i n g ss e r i o u si m p a c t k 。m e a n sa l g o r i t h m sa p p l i c a t i o ns c o p ei nc l u s t e r i n ga l g o r i t h m s t h i sd i s s e r t a t i o ns y s t e m a t i c a l l y ，d e e p l y ，r o u n d l ya n dd e t a i l e d l ys t u d i e sa n d a n a l y s e st h et e c h n i q u ea n dm e t h o d so fc l u s t e r i n ga n a l y s i s ，p u t sf o r w a r da n i m p r o v e dc l u s t e r i n ga l g o r i t h mb a s e do nf e a t u r ep o i n ts e l e c t i o n ( c f p s ) ， c o n s i d e r i n gt h ef a u l to fk - m e a n sc l u s t e r i n ga l g o r i t h m t h ec f p sa l g o r i t h ma l s o b e l o n g st ot h ed a t a b a s es e g m e n t a t i o nc a t e g o r y c f p sa l g o r i t h mu s eaf i t n e s s f u n c t i o nd u r i n gc l u s t e r i n g ，c f p sa l g o r i t h ma c c o r d i n gt ot h ed i s t a n c eo fc l u s t e r s i i i 加lr h l r i 山东大学硕士学位论文 a n dt h ef i t n e s sf u n c t i o no ft h ep o i n t st oc l u s t e r i n ga n da d ju s tp a r a m e t e rko f c l u s t e r s ，t h i sa l g o r i t h md o n tn e e ds e l e c tt h ei n i t i a lc o r en o d e so f t h ed a t a ，a tt h e b e g i n n i n ge a c ho b je c tb e l o n g st oac l u s t e r ，s ot h er e s u l to fc l u s t e r i n gi ss t a b l e ， c f p sa l g o r i t h md o e sn o tf a l li n t ol o c a lo p t i m u mc l u s t e r i n gr e s u l t 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 ec f p sc l u s t e r i n ga l g o r i t h mi nd a t am i n i n g ，c o m p a r e dw i t h o t h e rc l u s t e r i n ga l g o r i t h m s ，c f p sa l g o r i t h mi m p r o v e st h ec l u s t e r i n ga c c u r a c y a n de f f i c i e n c y s ou s e r sc a r le a s i l yu s et h ea l g o r i t h mp r o p o s e di nt h i sp a p e r w i t h o u tc o n f i g u r ec o m p l e xp a r a m e t e r s ，a n dc a ng e tb e t t e ro rt h es a m ea st h e r e s u l t so fo t h e rc l u s t e r i ga l g o r i t h m c l u s t e ra n a l y s i sa n dr e l a t e dt e c h n o l o g i e si ni n t r u s i o nd e t e c t i o ni n t r u s i o n d e t e c t i o ni s c u r r e n t l yah o tt o p i c ，t h i sd i s s e r t a t i o na t t e m p t s t ou s ec f p s c l u s t e r i n ga l g o r i t h mi ni n t r u s i o nd e t e c t i o ns y s t e m s ，a n du s e t h ek d dc u p19 9 9 d a t as e ta st h ee x p e r i m e n t a ld a t a ，t h ek m e a n sa l g o r i t h ma n d c f p sa l g o r i t h m h a v eb et e s t e d ，a l g o r i t h ma 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 ec f p s a l g o r i t h mh a sb e t t e rd e t e c t i o np e r f o r m a n c e ，g e tah i g h e rd e t e c t i o nr a t ea n dl o w f a l s ea l a r mr a t e ，t h em e t h o dc a no v e r c o m et h et r a d i t i o n a lk m e a n sa l g o r i t h m n e e d st om a n m a d ed e t e r m i n et h ekv a l u ea n db yt h ei n i t i a lc l u s t e r i n gc e n t e ro f c h o i c ei m p l i c a t i o n s k e y w 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 ；k m e a n s ；i n t r u s i o n d e t e c t i o n i v jj， 一j1一 k - 山东大学硕士学位论文 第一章绪论 本章对论文涉及的研究领域进行了较为详细的综述。简要介绍了数据挖掘 中聚类分析的研究背景和意义。在对研究现状进行简要综述的基础上，分 析了该领域存在的主要问题，进而引出了论文的主要研究内容，最后对论 文的章节安排作了介绍。 研究背景及意义 近年来随着计算机软、硬件的飞速发展，各行各业都开始采用计算机 及相应的信息技术进行管理和决策，这使得各企事业单位生成、收集、存 贮和处理数据的能力大大提高，与此同时各个领域产生了大量的数据，如 人类对太空的探索，证券业、银行业每天的巨额交易数据。其主要原因是 随着数据库技术的成熟和数据应用的普及，各个领域积累的数据量正在以 指数速度增长。同样也推动了数据库技术【1 ，2 】的极大发展，但是面对不断增 加如潮水般的数据，传统的数据库技术和数据处理手段己经不能满足要求， 提出了深层次问题：能不能从数据中提取信息或者知识为决策服务，就数 据库技术而言已经显得无能为力了。同样，传统的统计技术也面临着极大 的挑战。这就急需有新的方法来处理这些海量般的数据。因此，一门新兴 的自动信息提取技术：数据挖掘( 也称知识发现k d d ) ，应运而生并得到迅 速发展。 数据挖掘【3 ，4 】可以从大型数据库中的大量原始数据中提取人们感兴趣 的、隐含的、尚未被发现的有用的信息和知识。数据挖掘作为一门新兴的 研究领域，融合了诸如机器学习 5 1 ，模式识别6 1 ，统计学 7 , s l ，可视化【9 1 ，信 息科学技术，数据库和人工智能【1 0 】等众多学科。它的发展不仅为商务管理、 科学研究、查询优化、过程控制等领域提供了决策和支持，而且为相关的 计算机学科注入新的活力，从而推动计算机科学向纵深方向发展。从挖掘 的任务可以把数据挖掘分为：聚类、关联规则和分类发现等三大类。 p p o 山东大学硕士学位论文 聚类( c l u s t e r i n g ) 是数据挖掘中重要的研究课题之一，聚类分析在客户分 类、基因识别、文本分类12 1 、空间数据处理【1 3 】、医疗图像自动检测、入 侵检测1 4 d7 1 、天气预报【1 8 1 等领域有着广泛的应用，而其本身的研究也是一 个蓬勃发展的领域，数据挖掘、统计学、机器学习、空间数据库技术、生 物学和市场学的发展推动着聚类分析研究的进展，使它已成为数据挖掘研 究中的一个热点。数据挖掘中的聚类研究主要集中在针对海量数据的有效 和实用的聚类方法上，聚类方法的可伸缩性、高维聚类分析、分类属性数 据聚类、具有混合属性数据的聚类和非距离模糊聚类等问题是目前数据挖 掘研究人员最为感兴趣的。聚类的主要任务是从数据库的记录集中寻找数 据间的相似性，并以此对数据进行分类，使得不同类别中的数据尽可能相 异，而同一类数据之间尽可能相似，即“物以类聚，通过聚类，人们能够 识别密集和稀疏的区域，发现全局的分布模式以及数据属性之间有趣的相 互关系，同时它也可以作为其他算法的预处理步骤。 1 。2 国内外研究现状 近年来，数据挖掘引起了信息产业界的极大关注。国内外各研究机构 纷纷开展了对数据挖掘技术的研究和探索工作。1 9 8 9 年8 月在美国底特律 召开的第11 届国际人工智能联合会议的专题讨论会上首次出现 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 这个术语。随后在1 9 91 年、19 9 3 年和1 9 9 4 年都举行过k d d 专题讨论会，汇集来自各个领域的研究人员和 应用开发者，集中讨论数据统计、海量数据分析算法、知识表示、知识运 用等问题。随着参与人员的不断增多，k d d 国际会议逐渐发展成为年会。 研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术 的集成，以及多种学科之间的相互渗透。其他相关专题会议也把数据挖掘 和知识发现列为议题之一，数据库、人工智能、信息处理、知识工程等领 域的国际学术刊物也纷纷开辟了k d d 专题或专刊。其中，i e e e 的k n o w l e d g e a 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 研究的最新成果和动态。数据挖掘已经成为当前计 2 1_， h i 上 山东大学硕士学位论文 算机科学界的一大研究热点。 目前，国外数据挖掘的研究和应用得到迅速发展。在研究方面，对知 识发现方法的研究取得新的进展，如近年来注重对b a y e s ( 贝叶斯) 1 1 9 - 2 2 方法 ) 及b o o s t i n g t 2 3 艺5 1 方法的研究和提高；k d d 与数据库的紧密结合。在应用方 面，k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统， 而不是孤立的过程。国外很多计算机公司非常重视数据挖掘的开发应用， i b m 和微软都成立了相应的研究中心，一些公司的相关软件也开始在国内销 售，如p l a t i n u m 以及i b m 。 群体智能的研究国外进行的比较早，当前主要是对蚁群算法【2 6 。0 1 的研 究。自1 9 9 1 年d o r i g o 首次提出蚁群算法以来，蚁群算法己在路由、优化组 合、数据挖掘等多个领域取得了非常突出的成就。目前研究和应用主要集 中在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国开始启 动。1 9 9 8 年和2 0 0 0 年在比利时布鲁塞尔大学召开了第一届和第二届蚂蚁优 化国际研讨会。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量，1 9 9 3 年 国家自然科学基金首次支持对该领域的研究项目。从事数据挖掘研究的人 员主要集中在大学，也有部分在研究所或公司。所涉及的研究领域很多， 一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据挖掘理论 方面的研究。许多科研单位和高等院校竞相开展知识发现的基础理论及其 应用研究，如清华大学、中科院计算技术研究所、空军第三研究所、海军 装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的 应用进行了较深入的研究；北京大学开展对数据立方体代数的研究：华中 科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉 林大学等单位开展了对关联规则挖掘算法的优化和改造。此外，国内也有 关于蚁群算法的公开报道和研究成果，但严格理论基础尚未奠定，有关研 究仍停留在实验探索阶段，大多是对算法的研究和改进等。 聚类分析作为统计学、机器学习和数据挖掘等领域的交叉学科，吸引 了众多研究者投身其中，使之成为数据挖掘研究领域的一个非常活跃的研 3 l r l ，暖 似il 山东大学硕士学位论文 究课题。聚类分析已有多年的研究历史，这些研究主要集中在基于距离的 聚类分析3 1 1 方面。随着数据挖掘研究的深入，借鉴相关学科的理论方法， 涌现出大量新的聚类算法，在各自特定应用领域取得了一定进步。例如蚁 群算法、遗传算法、模拟退火算法、基于力学的算法等。 近年来，对聚类分析技术的研究有向处理高维度的海量数据的方向发 展的趋势，但数据维度的增长会导致聚类效果的恶化，因此要考虑在聚类 分析中结合降低数据维数。对于海量数据，则需要降低聚类算法复杂度或 采用抽样技术。此外，由于一般用户难以理解和接受复杂的聚类分析算法， 而可视化技术可以以其直观性来弥补这一缺陷，使用户从可视化的角度更 直观地理解数据分析和聚类分析整个过程，因此可视化聚类技术也得到了 进一步的发展。 由于应用数据库所包含的数据量越来越大。聚类分析已成为数据挖掘 研究中一个非常活跃的研究课题。在数据挖掘中，大多数工作都集中在设 计能够有效、高效的对大数据库进行聚类分析的方法上。相关的研究课题 包括：聚类方法的可扩展性、复杂形状和复杂数据类型的聚类分析及其有 效高效性、高维聚类技术、以及混合数值属性与符号属性数据库中的聚类 分析方法等。 1 。3 当前聚类分析研究中存在的问题 聚类是一个具有挑战性的研究领域，它的潜在应用提出了各自特殊的 要求。尽管目前提出了许多聚类算法，但没有一种聚类方法能在各个方面 都达到理想要求。在数据挖掘领域中，研究工作主要集中在为大型数据库 的有效和实际的聚类分析寻找适当的方法。基于划分方法中的k m e a n s 算法 3 2 - 3 4 1 ，其聚类结果依赖于初始值的设定，但是k 值的选定往往要经过很多次 实验才能找到最佳聚类个数；k m e a n s 算法采用随机法选取初始聚类中心， 选取点的不同，聚类结果可能就不同，这样的依赖性就导致聚类结果的不 稳定性，且容易陷入局部最优而非全局最优聚类结果：对噪声点和孤立点 很敏感且只能发现球状簇。另外，在划分方法中，聚类个数通常根据用户 4 i j 1 l _jj 如 l h i 山东大学硕士学位论文 视觉和使用方便性假定。聚类个数一旦确定在整个聚类过程中都不能更改， 最终得到的簇的数目就是初始的聚类个数。但用户往往不能准确设定聚类 个数，从而得到的划分也是不准确的。 1 4 论文的主要内容 、 本文在系统归纳数据挖掘的一般原理、一般方法以及相关技术的基础 上，针对当前研究中存在的主要问题，对数据挖掘中关键技术之一的聚类 分析进行了探索性的研究，主要研究内容如下： 在认真研究当前各种聚类算法的基础上，针对基于划分的k m e a n s 聚类 算法中存在的聚类结果的不稳定性，以及不能准确设定聚类个数的问题， 提出了基于特征点选择的聚类算法c f p s 3 5 1 ( c l u s t e r i n ga l g o r i t h mb a s e do n f e a t u r ep o i n ts e l e c t i o n ) 。通过理论分析和实验验证表明改进算法克服了原 算法的缺点，算法能自动聚类和调整聚类数k ，c f p s 算法不用选取初始聚类 中心，因此聚类结果稳定，不会陷入局部最优的聚类结果。 1 5 论文的组织结构 本文共分五章，各章的主要内容如下： 第一章绪论，简要介绍了课题的研究背景、当前国内外的研究现状以 及研究中存在的问题；概括介绍了论文的主要内容和组织结构。 第二章聚类分析，聚类分析是数据挖掘的一个重要组成部分，本章主 要介绍聚类分析的基本原理、步骤、应用、常用的聚类算法，并分析了各 自的优缺点及适用条件。 第三章基于特征点选择的聚类算法研究，简单介绍了k m e a n s 聚类算 法的基本知识，存在的主要问题，从而引出基于特征点选择的聚类算法， 阐述基于特征点选择的聚类算法基本思想，并对算法进行了分析和验证。 第四章基于特征点选择的聚类算法在入侵检测中的应用，首先简单介 绍了入侵检测的基本知识，并介绍了基于聚类的入侵检测的优点和对聚类 5 一卜聩 山东大学硕士学位论文 分析算法的性能要求，最后采用k d dc u p1 9 9 9 数据集对c f p s 算法用于入 侵检测进行了实验分析。 第五章总结与展望，对本文的研究工作和成果进行概括总结，并指明 今后的研究方向。 6 l j f i t 山东大学硕士学位论文 第二章聚类分析 聚类( c l u s t e r i n g ) 分析是数据挖掘的主要方法之一，由于其简单、有效， 已成为数据挖掘研究领域中一个非常活跃的研究方向，而聚类算法是聚类 分析研究的核心。聚类就是把一组个体按照相似性划分成若干个类别，跟 人们常说的“物以类聚，人以群分”相似。聚类的目的是使得属于同一类 别的个体之间的相似性尽可能的大，而不同类别上的个体间的相似性尽可 能的小。 2 1 聚类分析的基本概念 将物理或抽象对象的集合