(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf_第1页
(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf_第2页
(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf_第3页
(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf_第4页
(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf_第5页
已阅读5页,还剩54页未读 继续免费阅读

(计算机应用技术专业论文)智能聚类方法中的克隆网络聚类算法研究与应用.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

硬圭学袋论文 攀邕宣e 墨鼍鼍量| 葺麓麟瓣奠曼曼曼皇嘲皇曼量笪皇皇皇曼舅嫩燮i i i l l 黼奠皇鼍墨鼍鼍詈鼍璺黛舅曼曼置皇_ 摘要 近年来兴起的数据挖掘技术是一种能够自动处理海蹙数据资源并将其转化 为商意义知识的脊利工具。聚类分析作为数据挖掘领域的关键技术,谶年来已经 逐澎成蔻堑雾内的研究热点,楚一个富有挑战性熬硬究谖越。它可以按照事物阍 驹相似性用数学的方法研究和始理给定对象的分类,在戴过程中舞没蠢教薅的獾 导,是一种无般督的分类方法。 本文对现有聚类技术进彳予t 较深入的研究。首先,农分析传统聚类算法的基 穰土,铮对传绞嚣法酶不蹩,豢子警麓鼓念萎耱静鼹纛,终磅究重赢旋在7 基手 智能融合技术的聚类算法方丽,讨论基于计算智能的聚类方法。计算智能的方法 具肖良好的优化特性和自学习、自适应能力。将其引入猁聚类分析中,得到的智 缝聚类算法不段弼竣竟羧健绕算法懿缺点,嚣豆其毒鞍凑豹蘩类套效缝秘可月 健。 。 其次,本文嫩过对现有的几种智能聚类方法的深入分析和讨论,综合其缺点 和不足,l ;数据分辑为中心,提出了解决穷褰,即基于巍隆弼络的聚类算法。该 冀法将免疫竞陵策略用子阏缀结构聚类孛,结含改速静炎舜冀予窝蔡慧尧隆操俸 对原始数据进杼学习,进化出一个克隆网络来反映原始数据在状态瘢问中的分 布。这种无监督的聚类算法不仅能够有效宠服一般方法对初始化敏感、依赖聚类 骧爨、浚毁速爱後等疑点,露麓与数据分农茏关,照够处理海耋、多缭、羼蛙复 杂的网络数据。本文通过仿真实验严格的验证了算法的裔效性。同时,探讨了克 降瞬络聚类算法韵应用研究,将其用于网络数据分析,通过异常检测嶷验验证了 算法熬可用性_ 秘阿解释性。 关键词:数据挖掘、无监督聚类分析、克隆峭络、免疫巍隆策略、昴常检测 餐襞聚类蠢法中嚣壳瀣疆络聚类算法研变与痰矮 i ii iq i l l l l li i i | ! ! ! ! s ! ! 舞烹邕鳖基鲁! ! 鲁! 曾舞麓酋目曹! j a b s t r a c t d a t a m i n i n gt e c h n o l o g y , a san e we m e r g i n ga d v a n t a g e o u sm e t h o d , c a n a u t o m a t i c a l l ya n a l y 站m a g n a n i m i t yd a t u m r e s o u r c e sa n dt r a n s f o r mi tt ot h e s i g n i f i c a n tk n o w l e d g e c l u s t e r i n ga n a l y s i sa sak e yt e c h n o l o g yi nt h ed o m a i no fd a t a m i n i n g , g r a d u a l l yh a sb e c o m et h eh o ta n dc h a l l e n g i n gr e s e a r c ht o p i ci nr e c e n ty e a r s 。 磁蠊u s i n gm a t h e m a t i cm e t h o d si nr e s e a r c h i n ga n dp r o c e s s i n go fo b j e c td a t u m c l u s t e r i n ga n a l y s i sc a nc l a s s i f yt h eg i v e no b j e c t sb yc o m p a r i n gt h es i m i l a r i t i e s b e t w e e nt h e mw i t h o u tt e a c h e r sg u i d a n c ei nt h i sc o u r s e , s oi tb e l o n p 零t ot h e u n s u p e r v i s e dc l a s s i f i c a t i o n t h i sa r t i c a lh a sc a r r i e do nd e e p e rr e s e a r c ht oe x i s t i n gc l u s t e r i n ga l g o r i t h m s 。f i r s t 蟥a 1 1 b a s e do na n a l y s i st h ee x i s t i n gt r a d i t i o n a lc l u s t e r i n ga i g o r i t h m s ,i nv i e wo ft h e t r a d i t i o n a la l g o r i t h mi n s u f f i c i e n c y , a l s oc l o s e l yt i d i n gw i t ht h ev i e w p o i n to fi n t e l l i g e n t f u s i o na n ds u p p l e m e n t a r y , t h i sa r t i c l ef o c u so no n eu n i q u ec l u s t e r i n ga l g o r i t h mw h i c h b a s e do i li n t e l l i g e n tf u s i o nt e c h n o l o g y i n t e l l i g e n tc o m p u t a t i o nh a st h eg o o do p t i m i z e d c h a r a c t e r i s t i ca n ds e l f - s t u d y 、a u t o - a d a p t e da b i l i t y w i 壤i n t r o d u c i n gi n t e l l i g e n t c o m p u t a t i o nm e t h o di n t oc l u s t e r i n ga n a l y s i s t h en e wa c h i e y i n gi n t e l l i g e n ta l g o r i t h m d o e s u to n l yc a no v e r c o m et h ei n s u f f i c i e n c yo ft r a d i t i o n a lo n e s b u ta l s oh a sh i g h e r c l u s t e r sv a l i d i t ya n du s a b i l i t y f o l l o w e d ,b a s e do ng a t h e r i n g 、r e s e a t o ha n da n a l y s i st h ee x i s t i n gt r a d i t i o n a l c l u s t e r i n ga l g o r i t h m ,i nv i e wo ft h et r a d i t i o n a la l g o r i t h mi n s u f f i c i e n c y , t h i sa r t i c l e h a sp r o p o s e dan e wk i n do fc l u s t e r i n ga l g o r i t h mw h i c hb a s e do ni n t e l l i g e n tf u s i o n t e c h n o l o g y 儆a l g o r i t h mu s e st h ei m m u n i t yc l o n a ls t r a t e g yi n t ot h en e t w o r k a r c h i t e c t u r e , c o m b i n i n gw i | hm u t a t i o no p e r a t o ra n dt h ef o r b i d d e nc l o n a lo p e r a t i o n t o g e t h e rt ot r a i nt h eg i v e no r i g i n a ld a t af o rs t u d y , f u r t h e re v o l v e sac l o n a ln e t w o r kt o r e t i e c tt h eo r i g i n a id a t ai nt h es t a t es p a c e 。懒k i n dc a nn o tm e r e l yo v e r c o m et h e g e n e r a lm e t h o dt ot h es h o r t c o m i n go fi n i t i a l i z i n gs e n s i t i v l y ,r e l y i n go nc l u s t e r s p r o t o t y p eo rd i s a p p e a r i n gs l o w l y , b u te f f e c t i v e l yw h i l ed i s t r i b u t e dm v i n gn o t h i n gt o 酗酒t ht h eg i v e nd a t a a l s oc a nd e a lw i t ht h en e t w o r kd a t aw i t hc o m p l i c a t e d m a g n a n i m i t y ,m n l t i d i m e n s i o no rm u l f i a t t r i b u t i o n t h i sa r t i c l ep a s s e st h ev a l i d i t yo f t h ev e r i f i c a t i o na l g o r i t h mo fe m u l a t i o nw i t hs t r i c te x p e r i m e n t 啪u s i n gt h i s u n s u p e r v i s e dc l u s t e r i n ga l g o r i t h mf o ra b n o r m a li n t r u s i o nd e t e c t i o n , an e wa b n o r m a l i n t r u s i o nd e t e c t i v ea l g o r i t h mi s p r o p o s e db a s e d0 1 1c l o n a ln e t w o r kc l u s t e r i n g 1 陲e c o m p u t e rs i m u l a t i o no nt h ek d d c u p 9 9d a t a s o ts h o w st h a tt h i sm e t h o di sf e a s i b l e a n de f f e c t i v e k e yw o r d s :d a t am i n i n g ;u n s u p e r v i s e d ;c l o n a ln e t w o r k ;c h m t e r t n gi m m u n i t y c i o n a ls t r a t e g y ;a b n o r m a l l yi n t r u s i o n 兰州理工大学 学位论文原翎性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所 墩缮的研究成祭。除了文申特剃拥数标注弓| 翔戆内寨耱,本论文苓氢含任 何其他个人或集体已经发表绒撰写的成果作品。对本文的研究做出重要贡 献麴个人和集体,均已在文巾以明确方戏标明。本人完全意识到本声明的 法律后果由本人承担。 络者签名: 掘名砖 基麓2 岬年二男 争基 学位论文版权使用授权书 零学位论文作者完全7 解学校有关豫整、搜鬟学位论文鹣裁定,嗣意 学校保留并向嘲家有关部门绒机构送交论文的复印件和电子版,允许论文 放签凝秘辔鞫。本入授权兰髑建工大学霹菠赘本学像论文夔全郝或部分蠹 容编入有关数据库进行检索,可以采用影印、缩印躐扫描等复制手段保存 弱滋缓本学诬论文。 本学位论文属于 1 、保密口,在年勰镪后适用本授权书。 2 、不保密团。 ( 满在以上相_ 陂方框内打“”) 作者签名:;屯弥 导烬签名:强立f 日期。唧年j 月三r 日 日期:扣叼年f 月比日 | 硕士学位论文 i 1 研究背景 第1 章绪论 随着数据库技术、信息技术以及网络技术的飞速发展和广泛应用,人们积累了 大量的数据信息,信息爆炸为人们带来了诸多益处,但也不可避免的造成了弊端, 即知识的“污染”。如何从浩如烟海的数据中去其糟粕,取其精华,得到数据背后 隐藏的那些重要信息和知识是计算机应用技术面临的一大难题。 数据信息每日都在激增,人们正在被数据淹没,但却饥渴于知识。面对海量 的数据,人类迫切需要能够自动处理数据资源并能将其转化为有用知识的自动工 具。数据挖掘技术应运而生【l j 。 如果说数据库技术是人类记忆和管理能力的延伸,那么数据挖掘则是人类分 析、管理数据能力的延伸。 数据挖掘日( d a t am j e l m g ) 的目的就是从海量的、不完全的、有噪声的、模糊 的、随机的实际应用数据中,提取出隐含的、先前未知的、目标明确的、针对性 强的、精练准确的、对决策有潜在价值的规则。数据挖掘的过程需要不断学习、 反复交互以及用户的参与。它作为一种发现知识的工具,可以从数据集中识别出 有效的、新颖的、潜在的、有用的、可理解的知识和模式。这些知识和模式可以 用来做出预测,也能帮助我们进行科学的决策。 近十几年来,数据挖掘技术有了长足的进步,已经发展成为数据库领域的关 键技术和研究热点。它是分析大规模数据集提取有用知识的有效手段。同时,数 据挖掘也是一项数据库应用技术,存在着广泛的实际应用需求。因此,无论是数 据挖掘的理论研究,还是其应用实践,都是有意义的。 除了是数据库领域的关键技术,数据挖掘还涉及到了人工智能、模式识别、 统计学、机器学习、专家系统等领域,其应用已经拓展到数理理论、信息安全、 图形图像设计、工程设计、基因工程研究和科学探索等多个方面,其发展速度必 将大大影响全球信息化的进程,对其进行系统、深入、全面、详尽地研究更是信 息化发展的客观需要。 当人们进入2 1 世纪以后,可以预见数据挖掘的研究将形成一个新的高潮。数 据挖掘技术本身涉及到众多科学领域,可见,如何将不同领域的理论和技术融合 将是下一阶段研究的中心。况且,网络的普及、第三代通信技术的出现、计算机 技术的发展将为其提供更有利的硬件平台,对数据挖掘的研究将会更加深入。大 量实用产品的问世指日可待。所以数据挖掘技术是一个极具发展潜力和充满挑战 性的研究领域。 智能聚类方法中的克隆网络聚类算法研究与应用 数据挖掘分析方法从功能上可以分为4 种:关联分析方法、序列模式分析、 分类分析以及聚类分析。聚类技术是一种典型的挖掘算法,和分类不同,聚类前 需要划分的类是未知的,它按照数据对象之间的相似程度将其分组为多个类或簇 ( 3 1 分组过程中没有教师的指导,是一种无监督的分类方法。 作为无监督模式分类的一个分支,聚类技术已经成为数据挖掘领域乃至人工 智能领域里一个非常活跃的研究课题。甚至可以说是该领域内的研究热点和难点, 极具挑战性。所以,本课题有理由以聚类技术作为切入点进行纵深的研究。同时, 受到数据挖掘技术发展趋势和人工智能方法的启发,重点研究聚类技术和智能方 法的融合问题。 在人工智能领域,传统的人工智能属于符号主义,以知识为基础,通过推理 进行问题求解。然而计算智能的方法则是以数据为基础,以连接主义的思想为主, 通过训练建立联系,进行问题的求解【4 】。计算智能的方法正得到越来越多学者的研 究和完善,并与传统的人工智能技术互相交叉、取长补短,使得人工智能研究与 应用呈现出向上的发展趋势。我们有理由相信,基于智能融合互补的观点,将计 算智能的方法和传统聚类思想结合,新的聚类算法会更适合数据挖掘技术发展的 需要。 1 2 数据挖掘技术研究现状 什么是知识? 从广义上理解,数据、信息也是知识的表示形式,但是人们更 注重把概念、规则、模式、规律和约束等看作是知识。 人们把数据看成是知识的源泉,就像从矿石中采矿或淘金一样。原始数据可 以是结构化的,比如数据库中的数据;也可以是非结构化的,如文本、图形和图 像数据;甚至可以是分布在网络上的异构型数据。而发现知识的方法可以是数学 的,也可以是非数学的;可以是演绎的,也可以是归纳的。发现的知识可以被用 于信息管理,查询优化,决策支持和过程控制等,还可以用于数据自身的维护。 简单来说,数据挖掘就是提取或挖掘这些知识,它是一种高级数据分析工具,也 是信息化技术自然演化的结果。 数据挖掘技术能挖掘的数据类型包括【5 l : 1 定性的概念描述,即对含有大量数据的数据集合进行概述性的总结并获得简 明、准确的描述: 2 关联分析:从给定的数据集发现频繁出现的项集模式知识; 3 分类和预测:在已知训练数据的特征和分类结果的基础上。为每一种类别找到 一个合理的描述或模型,然后再用这些分类的描述或模型对未知的新数据进行 分类: 2 硕士学位论文 4 聚类分析:根据相同簇内部数据对象间的相似度最大化;而不同簇对象之间的 相似度最小化这一准则,以及度量数据对象问相似度的标准准则,将原始数据 对象划分为若干个簇,这一过程无教师指导; 5 孤立点分析:在数据库中,经常存在一些数据对象,它们不符合数据的一般模 型,这样的数据对象被称为孤立点( o u t l i e r ) 。孤立点在某种尺度下与其他点不 同或不一致。孤立点分析就是为了寻找这些“噪声”数据; 6 演化分析:专门描述行为随时问变化的对象的规律或趋势,并对其建模。 正是因为数据挖掘能对各种类型的知识进行分析和提取,近年来它已经成为 一个十分活跃的研究领域。从数据库中发现知识( k d d ) 一词首先出现在1 9 8 9 年 举行的第十一届国际联合人工智能学术会议上,从1 9 8 9 年到1 9 9 4 年举行了4 次 k d d 国际研讨会。1 9 9 5 年,召开了第一届知识发现与数据挖掘国际学术会议。1 9 9 8 年建立了新的学术组织a c m s i g k d d ,( a c m 下的数据库中的知识发现专业组) 。 1 9 9 9 年该组织承办了第五届知识发现与数据挖掘国际学术会议( k d d 9 9 ) 。此外, 知识发现与数据挖掘太平洋亚洲会议( p a k d d ) 、数据库中的知识发现原理与实践 欧洲会议( s i g m o d ) 、数据工程国际会议( i c d t ) 、美国人工智能协会主办的k d d 国际会议等以研讨数据挖掘和知识发现( k d d m ) 为主的会议已经召开了多次, 规模也由早先的专题讨论会发展到国际学术大会,与会人员年平均增长率4 0 。 自1 9 9 9 年后,每年更是有数十个国际会议列有k d d m 的专题。近几年,从事数 据挖掘研发工作的人员已经遍部全世界8 0 多个国家。相关的软件产品研发公司遍 部全球。国内也有相当多的k d d m 研究会议和研究成果,一些大学也成功的承办 了相关的国际会议。 近年来,i n t e r n e t 挖掘和w e b 挖掘已经成为一个新的焦点问题:以电子商务 应用为背景的k d d m 已被实践证明具有巨大的商业应用前景。目前,k d d m 的研 究重点逐渐从发现方法的研究转向实际的系统应用,国外各大软件公司每年都有 新的基于某种挖掘目标的产品问世。k d d m 型的公司极力主张所谓“d w ( 数据 仓库) + d m ( 数据挖掘) = $ a v i n g ”的口号,更加说明了数据挖掘的价值所在。 由此,可以看出全球对k d d m 的研究呈现一片欣欣向荣的景象。 尽管如此,数据挖掘仍面临一些重大问题1 6 j : 1 巨大的数据量以及高维数据问题 目前,数据集合中拥有数百万条记录的数据库已经大量存在,对这种数据库 进行优化分析会产生数据的组合爆炸,因此要考虑将最优解转换为可接受解,并 使用降维、去噪等处理方法。 2 数据缺失问题 由于数据库不是为知识发现定做的,因而就会有一些重要的数据或重要属性 缺失的问题出现。 智能聚类方法中的克隆网络聚类算法研究与应用 3 变化的数据和知识问题 变化的数据有可能使原有的模式不正确,因此要考虑模式的更新功能,并且 要能够利用原来的知识发现新模式,减少分析量。 4 模式的易读性 要使知识发现结果易于非计算机专业人员理解,即需要进一步加强人机对话 能力。 5 与其他系统集成问题 数据库的发展趋势是不仅要存储数字化数据,而且要存储许多非标准化数据, 与这类模型的数据接口问题日益严重,只有实现这些不同模型数据的有效结合, 数据挖掘才具有实际应用价值。 面对海量数据存在的维数灾难及小样本问题,以及不确定性、非线性、非高 斯、非标号、“小世界”无尺度性等特征,如何实现有效的智能数据挖掘成为一个 有重大应用潜力的课题,相应的方法也面临着新的挑战。 随着计算机应用技术的发展,人们不断向自然进化、免疫遗传学习,向人脑 学习,在此基础上,提出了多种仿生智能信息处理的方法。如:模糊逻辑、进化 计算、神经计算、人工免疫系统、免疫克隆计算、支撑矢量机等方法。如何将智 能的方法与数据挖掘技术有效的融合,解决海量、多维、异构的数据分析问题, 将是未来数据挖掘技术发展的重中之重。 1 3 聚类技术研究现状 1 3 1 研究现状 虽然数据挖掘技术只有二十几年的发展历程,而作为数据挖掘中的重要分支 和有效工具,聚类分析并不是一个新领域。它应该算是一个古老的问题,从最初 的物以类聚到现存的各类聚类算法,聚类技术伴随着人类社会的产生和发展而不 断深化,人类要认识世界就必须区别不同的事物并认识事物间的相似性。 近年来,国际和国内的许多学者对聚类分析的研究十分重视,i e e e 会刊中的 模式分析与机器智能、系统、模糊系统、人和控制等杂志,几乎每天 都有关于聚类分析的文章。许多国际会议都设专题讨论聚类的研究进展和发展现 状。我国作为模糊聚类研究的大国,不仅在基础理论研究上取得了硕果,而且在 模糊聚类的应用研究上成果瞩目,比如将模糊聚类应用于医学诊断、天气预报、 矿藏识别等领域。当前,众多研究者孜孜不倦的探讨聚类分析的相关技术及其应 用;从不同的切入点出发,力求能够得到高效的聚类算法并积极寻找聚类算法和 其它信息处理方法的有效结合。在这种研究背景和大环境下,聚类技术研究的意 义和重要性已不言而喻。 4 硕士学位论文 目前存在大量的聚类算法,传统的聚类分析m 是一种硬划分,他把每个待辨识 的对象严格的划分到某类中,具有非此即彼的性质,因此这种分类的类别界限是 分明的而实际上大多数对象并没有严格的属性,它们在性态和类属方面存在着 中介性,具有亦此亦彼的性质,适合进行软划分 z a d e h 8 1 在1 9 6 5 年提出的模糊集理论为这种软划分提供了有力的分析工具,人 们开始用模糊的方法来处理聚类问题,并称之为模糊聚类分析。由于模糊聚类得 到的样本属于各个类别的不确定性程度,表达了样本类属的中介性,即建立起了 样本对于类别的不确定性的描述,能更客观地反映现实世界,从而成为当时聚类 分析研究的主流。 模糊划分的概念最早由r u s p i n i1 9 在1 9 6 9 年提出,随后,研究人员利用这一概 念提出了许多聚类方法,比较典型的有:基于相似性关系和模糊关系的方法【1 川( 包 括聚合法和分裂法) ,基于模糊图论的方法【1 l 】、基于模糊图论的最大树方法1 1 2 1 、基 于模糊等价关系的传递闭刨”烽。然而,这些传统的方法均不适合大数据集的聚 类,难以满足实时性要求较高的场合,因此其实际应用并不广泛,所以现在对这 些方面的研究已经逐渐减少了。 与此同时,基于目标函数的聚类方法越来越受到人们的关注,这类算法把聚 类问题归结为一个带约束的非线性规划问题,通过优化目标函数获得数据集的划 分矩阵和聚类结果。这类方法设计简单、解决问题的范围广、还可以转化为优化 闯题而借助经典数学的非线性规划理论求解,并且易于在计算机上实现。因此, 基于目标函数的聚类方法已经成为当今聚类研究的主流。 传统的基于目标函数的算法如c 均值聚类算法【州、模糊c - 均值聚类【瑚等。 这些算法以聚类中心为原型,所以不能检测特征空问中非线性子空间中存在的聚 类,为此有人对聚类原型模式进行了扩展,形成从特征空间中的点到线、面、壳 以及二次曲线等多类原型,按聚类原型的不同有c 簇、c - 线、c _ 面、c 壳、c 函 数等聚类算法f 1 6 l0 7 1 1 1 8 l1 1 9 1 。这些基于不同原型的聚类算法对不同分布的数据集会 采用不同的距离度量方式,实现了对呈球形、椭球形、线形、平面以及球壳、椭 球壳和某种函数关系分布的数据集的聚类分析 这些传统的和改进的基于目标函数的聚类算法存在一些较大的缺点:首先, 它们依赖先验知识,对初始化较敏感。其次,依赖聚类原型,对每个子集的分析 采用的是同一种聚类原型,只是原型的参数有所差别,从而限制了其实际应用的 范围针对这一问题,有人提出了一种多类原型模糊聚类算法l 硎,将现有的原型 聚类算法集成并统一在一起,但此方法增加了初始化的难度。 为此,人们考虑将计算智能方法融合到聚类算法中,用其智能性、进化性改 善原算法的性能。克服原有算法依赖先验知识、初试化敏感、收敛速度慢、不能 处理大规模数据和容易陷入局部极值的问题。计算智能又称为“软计算”1 2 “,主 5 智能聚类方法中的克隆网络聚类算法研究与应用 要由进化计算、人工免疫方法、模糊逻辑和人工神经网络等方法组成。以下可以 简单概括一下基于这些智能方法的聚类算法性能。 基于神经网络的聚类方法,最显著的优势在于神经阿络的并行处理能力,而 在数据挖掘中大数据集聚类分析是相当耗时的,利用此类方法正好能够解决这个 问题l 硐。 进化计算是建立在生物进化基础之上基于自然选择和群体遗传机理的随机搜 索算法,它模拟自然进化的过程,实质是一种优化技术。由于该算法能够全局并 行搜索,所以能以较高概率获得全局最优解。基于进化计算的聚类算法包括基于 模拟退火算法的聚类、基于遗传算法以及基于进化策略( 免疫、克隆选择等) 的聚类 等。这些算法在一定程度上克服了传统聚类算法容易陷入局部极值的缺点。 基于人工免疫系统理论的网络结构聚类算法无监督、与数据分布无关,尤其 适合处理海量、多维、异构的数据。 本文将在以后章节中详细介绍以上几类聚类算法的性能。 1 3 2 聚类技术存在的问题 从聚类分析理论的研究现状来看,人们已经提出了诸多算法,这些算法适合 于解决某些特定的问题,但是作为数据挖掘研究领域中一个异常活跃的研究课题, 现有聚类方法还有许多需要解决的问题。 1 可扩展性不强 许多聚类方法在小于2 0 0 个数据对象的集合上性能良好,但是面对大规模数 据库里的百万个对象,就无能为力。而现有的聚类算法只有极少数适合处理大规 模数据集,而且只能处理数值型的数据,无法分析数据挖掘中经常遇到的类属型 数据。 2 缺乏处理不同类型属性的能力 很多算法只是针对数值属性数据而设计的,然而在实际应用中,会遇到不同 类型属性的数据,比如二元型、类属型等。现有的大部分聚类方法根本不能分析 不同类型特征的数据。 3 需要先验知识去决定输入参数,即输入参数对领域知识的依赖性很强。 大多数聚类算法在进行聚类前需要知道许多参数,如聚类的类别数,并且聚 类的结果对参数十分敏感。但是,有些输入参数很难确定,特别是数据挖掘中的 高维数据更是如此。而且要求使用者输入参数也增加了用户的负担,使得聚类的 质量难以控制。最重要的是,聚类技术以无监督学习著称,而这类算法就不能算 是真正意义上的无监督学习了。 4 无法辨别任意形状的聚类 一般聚类方法都采用欧氏距离或曼哈顿距离作为相似度的衡量标准,基于这 6 硕士学位论文 样距离度量标准的方法趋向于发现具有相似尺度和密度的球形簇。而在实际中, 一个簇可能是任意形状的所以,好的算法应该能有效的发现任意形状的聚类簇, 即与数据分布无关。 5 缺乏处理噪声数据的能力 很多数据库中都包含了孤立点,噪声等,如果算法对于这样的数据敏感,就 会影响聚类性能,导致结果的质量降低。因此,好的算法必须可以过滤噪声数据 与离群值。 1 4 本文研究的目的和意义 数据挖掘中的聚类算法是一个富有挑战性的研究领域,在社会生活的许多方 面都有着广泛的应用。随着计算机网络的发展和普及,网络信息数据在激增的同 时,却给人们带来知识匮乏的尴尬。如何从数据的海洋中提取出对人们有用的知 识,是数据挖掘技术的任务。而聚类技术作为数据挖掘的关键和热点技术,不仅 具有无监督学习的特性,而且好的聚类算法对海量的、多属性的数据分析均十分 有效,解决问题的能力很强,可拓展性高、实用性好。 本文的研究重点是从数据出发,以高维、异构、海量的数据为中心,在分析 已有方法优点和不足的基础上,探讨能够有效处理该类数据的聚类算法。 现存的聚类算法都具有各自的优点和不足,了解这些优点和缺点更有助于我 们利用特定的算法去解决特定的问题。如上节所述,传统的硬聚类方法不适合处 理较大规模的数据集,缺乏可拓展性和可用性。经典的基于目标函数的聚类算法 由于其自身缺陷很难找到全局最优解,并且对初始化比较敏感。 针对经典算法对初始化敏感、容易陷入局部最优而产生错误分类的缺点,可 以将智能的方法和数据挖掘的方法融合互补,利用现有的模拟退火、遗传算法、 进化策略、人工免疫理论等先进的优化算法对目标函数进行优化,从而使聚类算 法得到全局最优解的概率大大增加,得到性能好、效果优的算法。所以本文工作 的重点就是研究现有的基于计算智能的混合聚类算法,分析这些算法的优缺点, 根据不足设计改进的方案。 在对现有智能聚类方法分析时,我们发现以下几个问题: ( 1 ) 基于神经网络的聚类算法以其并行性和自学习性而著称,能够克服传统 基于目标函数的聚类算法在处理大数据集时费时间的缺点,但由于其算法是基于 梯度下降的,因此无法避免会陷入局部最优。 ( 2 ) 在利用进化算法优化聚类目标函数的多种改进算法中,要重点考虑进化 算子构造、参数选取、收敛速度、运算时间等直接影响算法性能的问题。这样使 得该类方法依赖参数和先验知识 7 智能聚类方法中的克隆网络聚类算法研究与应用 ( 3 ) 现存的大多数聚类算法都是基于距离的方法,一般聚类算法在计算数据 相似程度时往往采用欧氏距离作为衡量标准,只能处理数据的数值属性。而实际 中,大量数据都来源于互联网,网络数据都是具有数值属性和类属属性的混合属 性数据,所以一般聚类算法在处理网络数据时,通常只考虑其数值属性的值,而 忽略非数值属性的任何信息,这样势必会影响聚类的效果。 因此,我们在研究聚类算法的时候,有必要将注意力放在提高聚类的性能和 速度上来克服以上方法的缺点,并重视能处理混合属性的聚类方法研究( 这一点 可以通过改进数据差异度来解决) 。 另外,本论文以分析数据、获取知识为中心,所以数据的选取尤为重要,我 们选择k d dc u p 9 9 网络入侵检测数据进行分析,该类数据规模庞大、高维异构、 属性类型不单一,存在孤立点,对聚类分析算法极其挑剔。十分适合对高质量聚 类方法的检测和验证。将本文方法应用于异常检测,提出基于本文聚类方法的异 常检测算法,通过仿真实验,证明新聚类算法的可拓展性和可用性。从而得到本 文的聚类方法满足信息处理对聚类分析的典型要求这一结论。 1 5 本文主要内容 本文针对数据挖掘领域的聚类技术进行了深入的研究和探讨,研究工作主要 体现在以下两个方面: 1 概括了现有聚类聚算法的性能和特点,对现阶段的主流聚类技术一基于目标函 数的聚类方法进行了较深入的研究和分析,总结了优缺点。通过多种方法的分 析、比较,努力探寻改进的方法弥补已有方法的不足。根据聚类技术的研究现 状和发展趋势,以传统聚类方法和智能方法的融合技术为切入点,进行深入的 研究。 2 综合现有智能聚类方法的优缺点,提出改进的算法解决现有聚类算法存在的某 些问题。同时,验证了该方法的在实际中的可用性,将其应用于网络异常数据 的分析,提出一种基于克隆网络聚类的异常检测算法,并验证了其有效性。以 此证明本文的智能聚类算法具有较高的有效性和可用性。 本文第一章为绪论部分。首先简单介绍了本文的研究背景,其次概述了数据 挖掘和聚类分析的研究现状以及存在的问题。概括分析了现有聚类技术的优缺点, 提出本文研究的方向和重点,最后简要说明了论文所做工作的目的、范围、切入 点和研究方法。 第二章是计算智能概述,分析现有智能方法的总体特性,并详细介绍了与论 文内容相关的遗传算法、免疫算法、克隆算法以及免疫网络,分析了算法性能。 第三章介绍了聚类技术的基本概念、现有聚类算法及其分类概述。从数据挖 8 硕士学位论文 掘的角度分析了经典聚类算法的性能。然后重点分析了几种智能聚类算法,包括 神经网络聚类、遗传聚类算法、免疫遗传聚类、基于克隆选择的聚类以及进化人 工免疫网络聚类方法 第四章综合现有智能聚类技术的特点,介绍改进的无监督聚类算法一克隆网 络聚类。详细的分析了算法的操作算子、参数选择以及性能指标。并给出了其应 用研究。以入侵检测数据作为本文算法的数据对象进行异常数据的分析和提取。 严格的验证了算法的有效性和可用性。 最后,对本文的研究工作进行了概括和评价,提出将来可能的发展方向和研 究空间。 9 智能聚类方法中的克隆网络聚类算法研究与应用 第2 章计算智能概述 数据挖掘需要从数据集中识别出有意义的、潜在有用的、可理解的知识和模 式,这个提取、挖掘知识的过程可以看成是一个模式识别的过程,因此模式识别 和人工智能领域的许多技术和方法经过一定的处理和改进便可以在数据挖掘的过 程中起重要的作用。计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ) 方法是传统人工智能方 法的扩展,以连接主义的方法为基础、以处理数据为中心,是模式识别和人工智 能技术发展的新阶段,将c i 技术用于聚类分析中,是聚类分析乃至数据挖掘技术 发展的主要方向之一。 计算智能是借助生物界的自然规律,根据其原理,模仿设计求解问题的算法。 该方法集中了许多领域知识的最新成果,运用这些技术对数据仓库中的模式进行 聚类分析有着巨大的发展潜力。目前这方面的技术很多,包括:进化算法、神经 网络、人工免疫系统、模拟退火技术和群集智能技术、d n a 计算以及量子计算等。 计算智能方法具有自适应、自组织和自学习性,不需蓦建立问题本身的精确 模型,也不依赖知识的表示,而是直接对输入的数据进行处理并通过学习得到结 果。因此,它可以解决许多传统人工智能方法无法解决的模式识别问题。特别是 对高维、非线性、随机或动态系统的分析。 利用计算智能的方法进行数据挖掘的过程体现为:通过数据库接口,从各类 真实的数据仓库中读出数据例子,利用计算智能的方法挖掘出数据聚类、分类、 关联模式等知识,再经过专家决策系统的评估和分析,最终获得可视化的结果。 计算智能方法种类繁多,以下仅对和本文相关的方法进行介绍。 2 1 神经网络 人工神经网纠纠( a r t i 丘c i a ln e u r a ln e t w o r k s ) 是模仿和延伸人脑智能、思维、意 识等功能的非线性自适应动力学系统。可以作为联想记忆器或分类器、聚类器以 及优化计算方法。 神经网络学习算法对事物和环境具有很强的自学习、自适应和自组织能力, 网络的知识积累是自动的。因此,神经网络是一种全新计算结构的智能信息处理 系统。它可以模仿人脑处理不完整的、不准确的、甚至处理非常模糊的信息,并 能联想记忆,从部分信息中获得全部信息。 神经网络适合解决非线性、非平稳性和非高斯的问题,近年来被广泛的应用 于各个领域中。它得以广泛应用的主要原因在于其学习能力、多输入并行处理能 力、非线性映射和容错能力、以及通过新的学习获得自适应性的能力。 在数据挖掘领域,应用比较广泛的神经网络模型包括b p 网络、自组织映射网 1 0 硕士学位论文 络( s o m ) 、循环聊网络等。其中s o m 网络包括k o h o n e n m 络和自适应共振网络 ( a r t ) 。s o m 网络模型适合对数据进行聚类分析,它是一种基于欧氏距离的、 通过对数据对象反复进行聚类并不断修改聚类中心,最终获得满意解的动态聚类 方法。 2 2 进化计算 进化计算( e v o l u t i o n a r ya l g o r i t h m ,e a ) 是一类模拟生物进化过程与机制求解问 题的自组织、自适应人工智能技术。它建立在达尔文和孟德尔的遗传变异理论基 础上,模拟生物的繁殖、变异、竞争、选择等机制。采用某种编码来表示复杂的 结构,并将每个编码称之为一个个体( i n d i v i d u a l ) 。算法维持一定数目的编码集 合,称为种群( p o p u l a t i o n ) ,并通过对种群中的个体进行一系列遗传操作来模拟 进化过程,最终获得一些具有较高性能指标的编码。 进化计算中常用的算子( 操作) 包括:选择、交叉和变异。其中选择操作是 模拟自然界的优胜劣汰过程;变异操作模拟自然界中生物遗传物质的变异;而交 叉则是模拟有性生殖过程中的染色体交换过程。 2 2 1 进化算法 进化算法是借鉴生物界自然进化过程与机制而产生的一类随机搜索方法。它 们模拟由个体组成的群体的集体学习过程。其中每个个体表示给定问题搜索空间 中的一个点。进化算法从任一初始的群体出发,通过选择、变异、交叉过程,使 群体进化到搜索空间中越来越好的区域。选择过程使群体中适应性好的个体比适 应性差的个体有更多的生存机会;交叉算子使得个体继承父代的基因信息;而变 异算子则是在群体中引入新的个体。 在计算机科学中,进化实质上是一种优化处理过程,与传统的优化方法不同, 传统的方法用代价函数来衡量动作的行为,从而通过选择一个好的动作使操作的 对象得到优化,大多数典型的优化方法都是通过计算代价函数的梯度或高阶统计 值进行优化,一般情况下,该类方法只能得到局部极优值,而且容易受到随机干 扰的影响。而进化算法符合达尔文适者生存和随机交换的思想,可以消除解中的 不适应因素,同时还利用了原有解中的知识,不需要微分等高阶信息,从而使得 优化过程速度加快,最终获得全局最优解。 一般,进化算法可以认为是遗传算法、进化策略、进化规划的总称,它们都 是模拟生物在自然环境中遗传和进化的原理而形成的计算方法。这三种方法在本 质上是相同的,但它们之间又存在区别: 1 进化规划和遗传算法的区别: ( 1 ) 遗传算法包含三个基本的操作:交叉、变异和选择。与遗传算法不同的是, 1 1 智能聚类方法中的克隆网络聚类算法研究与应用 进化规划侧重于个体行为的变化,没有利用个体之间的信息交换,所以就省 去了交叉和选择算子而只保留了变异操作。 ( 2 ) 进化规划的变异操作不依赖于线性编码,它往往可以根据待求问题的具体情 况采取较为灵活的组织方式,而普通遗传算法通常要把问题的解编码成一串 表达符号( 基因组) 的形式。 2 进化规划与进化策略的区别: ( 1 ) 在编码结构方面:进化规划将种群类比为编码结构,而进化策略则把个体类 比为编码结构,所以进化规划不需要用选择操作来产生新的候选解。 ( 2 ) 在竞争与选择方面:进化规划需要通过某种适当的选择方式,从父代和当前 予代中选取优胜者组成下一代群体,而进化策略通过一种确定性的选择,按 适应值的大小,直接将当前优秀个体和父代最佳个体保留到下一代中。 由于自然进化和生命现象的不可知性,以遗传算法为代表的三种典型进化算 法不可避免的存在概率算法的缺陷。普通进化算法最明显的缺点就是收敛问题( 收 敛速度慢或早熟) ,改进的进化计算方法包括免疫进化计算、量子进化计算、协 同进化计算等。 2 2 2 遗传算法 遗传算法1 2 4 1 ( g e n e t i c a l g o r i t h r a ) 是一种以达尔文的自然进化论与遗传变异理 论为基础的求解复杂全局优化问题的仿生型算法。它借鉴生物界自然选择和自然 遗传机制,以概率论为基础在解空间中进行随机化搜索,最终找到问题的最优解。 该方法是随机选择与适者生存的结合,模拟了自然选择和自然遗传过程中发 生的繁殖、交配和突变现象。将每个可能的解看作是群体( 所有可能解) 中的一 个个体,并将每个个体编码成字符串的形式,根据预定目标函数对每个个体进行 评价,给出一个适应度值。开始时总是随机地产生一些个体( 候选解) ,根据这些 个体的适应度利用遗传算子对这些个体进行操作,得到一群新个体,这群新个体 由于继承了上一代的一些优良性状,因而优于上一代,这样逐步朝着更优解的方 向进化。 遗传算法在每一代同时搜索参数空间的不同区域,然后把注意力集中到解空 间中期望值最高的部分,从而使获得全局最优解的可能性大大增加。遗传算子包 括选择、交叉、变异三个步骤。在一定条件下,该算法可以在搜索空间中收敛到 全局最优解。同时,遗传算法是一种通用性好和鲁棒性强的并行搜索算法。下面 简单介绍三种遗传算子: 1 选择算子( s e l e c t i o no p e r a t o r ) 选择算子的作用是选择群体中适应度较高的个体构成新一代的群体。其中每 个个体被选中的概率取决于该个体对环境的适应程度。 硕士学位论文 这是从群体中选择出较适应环境的个体,这些选中的个体用于繁殖下一代 因此有时也称这一操作为再生( r e p r o d u c t i o n ) 。由于在选择用于繁殖下一代的个体 时,是根据个体对环境的适应度而决定其繁殖量的,故有时也称为非均匀再生。 其中,适应度表示遗传空间中每一个个体对于其环境的适应程度;适应度函 数是遗传算法中的一个重要控制参数,一般来说,个体适应度函数的值越大,该

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论