(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf_第1页
(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf_第2页
(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf_第3页
(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf_第4页
(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf_第5页
已阅读5页,还剩58页未读, 继续免费阅读

(计算机软件与理论专业论文)面向高维数据的变密度空间聚类研究.pdf.pdf 免费下载

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

文档简介

面向高维数据的变密度空间聚类研究 摘要 伴随着信息技术的飞速发展和广泛应用,海量的高维数据被冗余地存储,如何从 数据的沙漠中挖掘出宝贵的知识业已成为当前最迫切的需求。聚类( c l u s t e r i n g ) 分析 作为数据挖掘领域中的一个重要分支,研究从海量未知数据中挖掘出有用的知识,在 模式识别、图像处理、市场研究以及生命科学等众多学科领域具有广泛的应用前景。 然而,现实世界中数据的高维、分布稀疏及不可避免的噪声普遍存在,特别是数据的 变密度分布,使得传统聚类算法难以使用。为此,设计能高效处理变密度高维数据的 聚类模型和算法成为本文的研究核心。 本文的主要工作如下: ( 1 )深入探讨和分析了聚类分析的概念、要求及所用数据类型,详细介绍各聚 类方法的思想、原理及实现,及其各自的优势与存在的不足。 ( 2 ) 针对基于密度聚类算法的优势及其存在的不足和缺陷,引入层次树模型描 述子聚类信息并利用基于密度的聚类思想进行聚类探测,形成算法d c h t 。 算法不仅具备基于密度聚类的优势性能,而且从根本上摒除该类算法因结 构设计粗糙而导致的种种不足。 ( 3 )针对传统聚类方法难以处理变密度空间聚类的现状,引入改进的层次树结 构描述数据集分布信息,并动态、自适应地调整局部参数来处理变密度高 维聚类难题,形成s v c 算法。 理论和实验共同验证了以上所提两种算法的有效性和高效性。 关键词:数据挖掘,聚类,基于密度聚类,高维,变密度 r e s e a r c ho nv a r y i n g - d e n s i t ys p a t i a lc l u s t e r i n gi n h i g h d i m e n s i o n a ld a t a a b s t r a c t w i t ht h er a p i dd e v e l o p m e n ta n dw i d ea p p l i c a t i o no fi n f o r m a t i o nt e c h n o l o g y , t h eh i g h d i m e n s i o n a ld a t aa r es t o r e dr e d u n d a n t l y h o wt od i s c o v e rk n o w l e d g ef r o m t h ed e s e r to fd a t ah a sb e c o m et h em o s tp r e s s i n gr e q u i r e m e n t a sa ni m p o r t a n ta n d a c t i v eb r a n c ho fd a t am i n i n g ,c l u s t e r i n ga t t e m pt od i s c o v e rv a l u a b l ek n o w l e d g e f r o mh u g eu n k n o w n d a t a b a s e f u r t h e r m o r e ,c l u s t e r i n gh a sb e e nb r o a d l ya p p l y i n gi n p a t t e r nr e c o g n i t i o n ,i m a g ep r o c e s s i n g ,m a r k e tr e s e a r c h ,l i f es c i e n c ea n ds oo n h o w e v e r ,t h er e a ld a t aa r eo f t e nh i g h - d i m e n s i o n a l ,s p a r s ea n dn o i s y ;e s p e c i a l l yf o r i t sd i s t r i b u t i o no fv a r y i n g d e n s i t y , w h i c hm a k e st h et r a d i t i o n a lc l u s t e r i n g a l g o r i t h m s f a l l i n p r e d i c a m e n t t h e r e f o r e ,t h ed e s i g no fe f f i c i e n tm o d e la n d a l g o r i t h mf o rc l u s t e r i n gh i g h - d i m e n s i o n a la n dv a r y i n gd e n s i t yd a t ab e c o m e st h e c o r eo ft h i ss t u d y t h em a i nw o r k sa r ea sf o l l o w s : ( 1 ) t h ei d e a s ,p r i n c i p l e s ,i m p l e m e n t s ,a d v a n t a g e sa n dd i s a d v a n t a g e so fk i n d s o fc l u s t e r i n gm e t h o d sa r ef i r s t l yp r o b e di n t oa n da n a l y z e dd e e p l y ( 2 ) a i m i n ga tt h ea d v a n t a g e sa n dd e f i c i e n c i e so fd e n s i t y - b a s e dc l u s t e r i n g a l g o r i t h m ,ah i e r a r c h i c a lt r e e ( h - t r e e ) m o d e li si n t r o d u c e dt od e s c r i b es u b c l u s t e r i n f o r m a t i o n ,t h e nt h ei d e a ro fd e n s i t y b a s e dc l u s t e r i n gi sa d o p t e dt od e t e c tc l u s t e r s a n df o r md c h ta l g o r i t h m ,w h i c hn o t o n l yp o s s e s s e st h ea d v a n t a g e s o f d e n s i t y b a s e dc l u s t e r i n g ,b u ta l s or e m o v e si t sd e f e c t sr e s u l t e di nt h er o u g ha n d i n a d e q u a t ed e s i g no fs t r u c t u r e ( 3 ) i nt h ef a c eo ft h ea c t u a l i t yt h a tt 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 ed i f f i c u l t t od e a lw i t hv a r y i n gd e n s i t ys p a t i a lc l u s t e r i n g ,a ni m p r o v d dh - t r e em o d e li s i n t r o d u c e dt op r e t r e a tt h ed a t a b a s ea n dg e tt h ed i s t r i b u t i o ni n f o r m a t i o n ;t h e nt h e l o c a lp a r a m e t e rt u n ed y n a m i c a l l ya n ds e l f - a d a p t i v e l y a f t e r w a r d s ,an e w a l g o r i t h m s v cu t i l i z e st h i sl o c a lp a r a m e t e rt os o l v et h ep r o b l e m so f v a r y i n gd e n s i t ys p a t i c i a l c l u s t e r i n gw e l l 。 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 sc o n f i r ma n dd e m o n s t r a t et h e e f f i c i e n c ya n de f f e c t i v e n e s so ft h ea b o v et w oa l g o r i t h m 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 g ,d e n s i t y b a s e dc l u s t e r i n g ,h i g h - d i m e n s i o n a l , v a r y i n gd e n s i t y i i 插图清单 1 1k d d 处理过程模型3 1 2 小波理论模型9 3 1 基于密度聚类中的密度可达和密度相连2 6 3 2 层次树模型。2 9 3 3 包含任意形状聚类的数据集3 2 3 - 4 算法时间性能比较3 2 4 1 变密度聚类实例3 4 4 2 建树算法描述。3 7 4 3 聚类探测的处理类型4 2 4 4 等密度、任意形状的三个聚类4 4 4 5 变密度的两个聚类“ 4 6 算法时间性能与数据维数的关系4 5 4 7 算法时间性能与数据规模的关系1 4 6 4 8 算法时间性能与数据规模的关系2 4 6 4 9 算法时间性能与数据规模的关系3 4 6 v l 图图图图围图图图图图图图图图图 表格清单 表2 1 二元变量的可能性取值表1 8 表4 1 实验所用数据集。4 5 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知,除了文中特别加以标志和致谢的地方外,论文中不包含其他人已经发表或撰写过的 研究成果,也不包含为获得金目e 王些塞堂 或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 一签掣魄7 帅口日 学位论文版权使用授权书 本学位论文作者完全了解盒月些太堂有关保留,使用学位论文的规定,有权保留 并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借阅。本人授权金 匿i 些盔堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索,可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文 签字日期 学位论文 导师签名 签字日期: 日 膨衍7 吖y 豫叫谚 语孙电耶 致谢 三年的硕士研究生生活即将划上句号,在这三年的学习和生活中,老师、 同学、亲人、朋友们给予我的关心和帮助将永远珍藏在我心灵最深处。 首先,我要感谢我的导师胡学钢教授。胡老师治学严谨、工作踏实、知识 渊博、思维开阔,学术见解新颖独到。我在硕士期间所取得的成绩,离不开胡 老师的悉心指导和鼓励。胡老师在这三年中以他在数据挖掘领域深厚的理论基 础和对研究方向前瞻的把握,指引我从事科学研究,让我的科研之旅少了很多 的荆棘与曲折。此外,胡老师一直以来不断教导我们做人的直谛,要热爱生活、 热心工作,并身体力行,这种耳濡目染的熏陶和教化无疑将是我一生受用无穷 的宝贵财富。 另外,我要感谢吴信东教授。吴老师作为国际数据挖掘领域的知名专家, 对该领域有着极其深刻且高瞻的理解和领悟,其高屋建瓴地指点和教导,让我 对学术科研之思路、方法有了更加深刻地认识。另外,吴老师严谨治学的态度 和真诚朴实的作风使我更加明晰了为人之道。 还有,我要感谢吴共庆老师和王德兴老师,他们的谆谆教导和倾力相授让 科研阶段的沟壑变成坦途;另外,感谢史君华、李楠、张圆圆、李洋、谢飞、 刘卫和俞奎,与他们的交流和讨论拓宽了我的视野和思路。感谢0 5 级与0 6 级 的师弟师妹们,与他们一起学习生活的点点滴滴都是愉快而难忘的。 最后,我要感谢我的家人,感谢他们这么多年来一如既往的无私关怀,不 仅从物质上给予鼎力支持,更从精神上赋予无尽的关爱,鼓舞我战胜困难、不 断前行。没有他们,就没有我的全部。 1 1 1 作者:王东波 2 0 0 7 年3 月 第一章绪论 2 0 世纪以来,计算机与信息科学、技术的迅速发展,特别是在存储技术、 数据库技术以及计算机硬件等方面所取得的令人瞩目的成绩,大大地推动了商 用数据库与信息产业的发展。随之,海量数据的收集、存储不仅只是可能;然 而,伴随着人们所获得的数据量的不断增多,人们的注意力越发成为一种宝贵 的资源,人们常常埋没于大量的数据中,却又无法得到足够多的有用知识。“数 据丰富,但信息贫乏! ” 1 】成为这一状况的真实写照。特别是在严重依赖数据 分析的领域中,面对海量和结构复杂的原始数据源,无论是从时间意义上还是 从空间意义上,传统的数据分析方法已经很难满足人们对获取隐藏在数据背后 的内在联系和信息的需要。正是在这种情况下,产生了对能更加有效、更加强 壮地进行数据分析的理论和方法的需求;人们希望有一种新的技术和工具来帮 助人们完成对大量原始数据的分析任务,进而获得人们所需要的有用知识。这 些技术和工具正是数据库知识发现( 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 ,k d d ) 1 ,2 ,3 ,4 ,8 】这一新兴领域的研究主题。 1 1 数据库知识发现 1 1 1k d d 的提出 随着计算机科学与技术的飞速发展,人类产生和收集数据的能力已经迅速 提高,起作用的因素包括如:商业事务、政府事务、农业生产和科学研究过程 的信息化。条形码( b a rc o d e s ) 在大部分商业产品中的广泛使用;快速、高性能 和廉价的存储设备;更好的数据库管理系统和数据仓库技术等信息技术和数据 存贮技术的发展。 由于计算机技术和信息技术地进一步融合,在全球范围内掀起了信息化的 浪潮,信息产生的渠道越来越多,信息更新的频率日益加快,各行各业产生了 数以亿计的数据库,数据库中存储的数据量急剧增大。然而,从如此大量的信 息中,获取我们有用的知识却变得越来越困难了,这就是被j o h nn a i s b e r t 称之 为“信息丰富而知识贫乏”的窘境,因此,有效的利用和处理大量的数据成为当 前世界范围内所共同关心的问题。 正是在这种客观需要的推动下,数据库知识发现( k d d ) 技术应运而生, 并得到迅速发展,越来越显示出其强大的生命力,成为数据库研究、开发和应 用最活跃的分支之一;2 0 世纪9 0 年代开始更是有了突飞猛进的发展,成为目 前涉及人工智能、数据库理论与技术、电子商务等学科的一个非常活跃的研究 领域;在商务管理、生产控制、市场分析、工程设计和科学探索等方面表现出 很好的应用前景,例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e 大学的 k d d 研究组,对其拥有的十多年的客户数据进行分析。该研究组在科学分析的 基础上,提出了新的电话收费和管理办法,制定了既有利于公司又有利于客户 的新政策。 经过几十年的发展,知识发现研究的重点逐渐从发现方法转向系统应用, 并且注重多种发现策略和技术的集成,多种学科之间的相互交叉渗透;随着其 后的不断发展,形成为一个建立在数据库技术的基础上,结合人工智能、机器 学习、统计学、神经网络等多种学科技术的具有很强生命力的新研究领域。特 别需要指出的是,数据挖掘技术从一开始就是面向应用的。它不仅是面向特定 数据库的简单查询,而且要对这些数据库进行微观和宏观的分析和推理,企图 发现事件发生的背后所隐藏的规律、模式等有用信息,以指导实际问题的求解、 对未来活动进行预测等。k d d 是一个交叉学科,它从其它诸如:人工智能、机 器学习、数据库、统计学、神经网络等学科吸取营养。因此,统计学方法、神 经网络方法、模糊论方法等都对k d d 过程产生了影响;这种影响依赖于给定 的数据挖掘任务、所挖掘的数据类型等因素。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第1 1 届国际人工智能联合会 议上首次提出的,这届学术会议上举行了以k d d 为主题的学术讨论,在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年相继举行了k d d 专题讨论会。随着对k d d 的深入研究 以及k d d 在许多领域的广泛成功的应用,于1 9 9 5 年,在加拿大召开了第一届 知识发现和数据挖掘国际学术会议,此后每年召开一次。第一本关于k d d 的 国际学术杂志d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) ) 也于1 9 9 7 年3 月创刊 发行。亚太地区于1 9 9 7 年在新加坡召开了首次k d d 国际学术研讨会。 目前,在i j c a i ,a a a i ,v l d b ,a c m s i g m o d 等代表人工智能与数据库 技术研究最高水平的国际学术会议上,对k d d 的研究都占有较大的比例,k d d 己经成为当今计算机科学与技术研究、应用的热点领域之一。随着k d d 在国 际上的兴起,我国也积极地开展了相应的研究和应用。目前国内许多学术会议, 如数据库学术会议、机器学习会议等,也都将k d d 列为重要的研究方向。 1 1 2k d d 的定义和处理过程 数据库知识发现的定义几经变化,其中比较公认比较完整、深刻和全面的 一个定义是由德国人f a y y a d z 等在1 9 9 6 年发表在会议论文 f r o m d a t a m i n i n g t o k n o w l e d g ed i s c o v e r y ) ) 一文【5 】中将k d d 定义为: ”t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ,n o v e lp o t e n t i a l l yu s e f u i ,a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a ” 即k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、 并能最终被入理解的模式的非平凡的处理过程。 2 一般地。将k d d 中进行知识发现的阶段称为数据挖掘( d a t am i n i n g , d m ) 4 1 ,某些应用领域对数据挖掘与k d d 不加区分地使用,而在某种意义上 二者可看作同一个概念。 从该定义可以看出k d d 是一个高级的处理过程 6 】,它从数据集中识别出 以模式来表示的知识。k d d 的过程是一个多步骤的处理过程,如图l l 所示, 多步骤之间相互影响,反复调整,形成一种螺旋式的上升过程,主要包括以下 一些处理步骤: lii 1 一数据准备叫_ 一数据挖掘_ 1 结果表达和解释i 图1 1k d d 处理过程模型 ( 1 ) 数据准备 k d d 的处理对象是大量的数据,这些数据一般存储在数据库系统中,是长 期积累的结果,往往不适合直接在这些数据上面进行知识挖掘,需要做数据准 备工作,一般包括数据的选择( 选择相关的数据) 、净化( 消除噪音、冗余数据) 、 推测( 推算缺失数据) 、转换( 离散值数据与连续值数据之间的相互转换,数据值 的分组分类,数据项之阃的计算组合等) 、数据缩减( 减少数据量) 。如果k d d 的对象是数据仓库,那么这些工作往往在生成数据仓库时已经准备妥当。数据 准备是k d d 的第一个步骤,也是比较重要的一个步骤。数据准备是否做好, 将影响到数据挖掘的效率和准确度以及最终模式的有效性。 ( 2 ) 数据挖掘 数据挖掘是k d d 中最关键的步骤,既是研究重点,同时也是技术难点之 所在。研究k d d 的人员大部分都在研究数据挖掘技术,采用较多的技术有分 类、聚类、关联、时序等。数据挖掘根据k d d 的目标,选取相应算法的参数, 分析数据,得到可能形成知识的模式模型。 ( 3 ) 评估、解释模式模型 上面得到的模式模型,有可能是没有实际意义或没有实用价值的,也有可 3 能是不能准确反映数据的真实意义,甚至在某些情况下是与事实相反的,因此 需要评估,确定哪些是有效的、有用的模式。评估可以根据用户多年的经验, 有些模式也可以直接用数据来检验其准确性。这个步骤还包括把模式以易于理 解的方式呈现给用户。 ( 4 ) 巩固知识 用户理解的、并被认为是符合实际和有价值的模式模型形成了知识,还要 注意对知识做一致性检查,解决与以前得到的知识互相冲突、矛盾的地方,使 知识得到巩固。 ( 5 ) 运用知识 发现知识是为了运用,如何使知识能被运用也是k d d 的步骤之一运用知 识有两种方法,一种是只需看知识本身所描述的关系或结果,就可以对决策提 供支持;另一种是要求对新的数据运用知识,由此可能产生新的问题,需要对 知识做进一步的优化。 1 1 3k d d 的特性 k d d 就是利用机器学习的方法从d b 中提取有价值知识的过程 7 】,是数据 库技术和机器学习两个学科的交叉学科。数据库技术侧重于对数据存储处理的 高效率方法的研究,而机器学习则侧重于设计新的方法从数据中提取知识。 k d d 利用数据库技术对数据进行前端处理,而利用机器学习方法从处理后的数 据中提取有用的知识。k d d 与其他学科也有很强的联系,如统计学、数学、人 工智能和可视化技术等等。 k d d 有如下几个特性: ( 1 ) k d d 是从现实世界中存在的一些具体数据中提取知识。这些数据在 k d d 出现之前早已存在,对现实世界很有意义。 ( 2 ) k d d 使用的数据来源予d b ,处理的数据量可能很大。因此,k d d 中 学习算法的效率和可扩充性就显得尤为重要。 ( 3 ) k d d 所处理的数据来自现实世界,数据的完整性、一致性和正确性都 很难保证,因此如何将这些数据加工成学习算法可以接收的数据也需要进行深 入的研究。 ( 4 ) k d d 利用目前数据库技术所取得的研究成果来加快学习过程,提高学 习效率。 ( 5 ) k d d 处理的数据来自于实际的数据库,丽与这些数据库数据有关的还 有其他一些背景知识,这些背景知识的合理运用也会提高学习算法的效率。 4 1 2 数据挖掘 1 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和 决策支持等。这个定义包括好几层含义:数据源必须是真实的、大量的、含噪 声的;发现的是用户感兴趣的知识;发现的知识是要可接受、可理解、可运用 的;并不要求发现放之四海皆准的知识,仅要求其支持特定的发现问题。 1 2 2 数据挖掘的对象 数据挖掘技术从兴起到发展的十几年问,主要面对的挖掘对象是以结构化 数据为主的关系数据库和数据仓库。但随着数据库技术和i n t e r n e t 技术的迅速 发展。大量的复杂类型的数据不断涌现,恰恰正是在这些数据里隐含了更具价 值的知识和信息。因此数据挖掘对象的进一步发展就是针对复杂类型数据的挖 掘。复杂类型数据的挖掘主要包括:空间数据挖掘,多媒体数据挖掘,时序数 据挖掘,文本数据挖掘,w e b 数据挖掘,流数据挖掘。 ( 1 ) 空间数据挖掘 空间数据挖掘( s p a t i a ld a t a m i n i n g ) ,是指对空间数据库中非显式存在的知识 空间关系或其它有意义的模式等的提取。 ( 2 ) 多媒体数据挖掘 多媒体数据挖掘( m u l t i m e d i ad a t am i n i n g ) ,主要是指对多媒体数据库中多媒 体数据的相似性搜索,多维分析,分类和预测分析,以及多媒体数据的关联挖 掘。 ( 3 ) 时序数据挖掘 时序数据挖掘( t i m e s e r i e sd a t am i n i n g ) ,主要指对时序数据库中时序数据的 趋势分析,相似性搜索,与时间有关数据的序列模式挖掘和周期模式挖掘。 ( 4 ) 文本数据挖掘 文本数据挖掘( t e x td a t a m i n i n g ) ,当数据挖掘的对象完全由文本这种数据类 型组成时,这个挖掘过程就称为文本数据挖掘。 ( 5 ) w e b 数据挖掘 w e b 数据挖掘( w e bm i n i n g ) ,是将数据挖掘技术应用于w e b ,以实现对w e b 存取模式、w e b 结构和规则,以及动态的w e b 内容的查找。一般将w e b 挖掘 分为三类:w e b 内容挖掘( w e bc o n t e n tm i n i n g ) ,w e b 结构挖掘( w e bs t r u c t u r e m i n i n g ) 和w e b 使用汜录的挖掘( w e bu s a g em i n i n g ) 。 值得一提的是x m l 技术的出现,不仅为互联网上的电子数据交换提供了 一个标准。而且x m l 技术从数据的角度提供了一个更好地表示数据内容以及 数据所代表的意义的手段。因此基于x m l 技术进行数据挖掘为数据挖掘的研 究提供了新的契机。对于w e b 数据挖掘的研究也逐渐与x m l 结合起来。 ( 6 ) 流数据挖掘 流数据挖掘( s t r e a m i n gd a t am i n i n g ) ,在数据挖掘和数据分析研究领域中, 最近出现了一个新的研究方向,即流数据的挖掘与分析。流数据是指那些数据 量非常巨大的,无法全部存放在存储介质上进行分析和计算的数据。其特点是 数据持续到达,且速度快、规模宏大;其研究核心是设计高效的单遍数据集扫 描算法,在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构, 使得在任何时候都能够根据这个结构迅速获得近似查询结果。 1 2 3 数据挖掘的功能 数据挖掘不仅能对过去的数据进行查询和遍历,并且能够对将来的趋势和 行为进行预测,并自动探测以前未发现的模式,从而很好地支持人们的决策。 被挖掘出来的信息,能够用于信息管理、查询处理、决策支持、过程控制以及 许多其它应用。数据挖掘按其功能划分主要包括以下几类: ( 1 ) 分类 分类是数据挖掘中应用的最多的方法。分类是找出一个类别的概念描述, 它代表了这类数据的整体信息,即该类的内涵描述,一般用规则或决策树模式 表示。一个类的内涵描述分为特征性描述和区别性描述。特征性描述是对类中 对象的共同特征的描述,区别性描述是对两个或多个类之间区别的描述。分类 规则挖掘过程通常分为二个步骤:第一步,通过对训练数据集的分析形成学习 模型;第二步是首先使用测试数据评估分类规则的准确率,若模型被认为是可 接受的,则可以进而利用模型对新的类标号未知的数据集进行分类。 ( 2 ) 关联分析 关联分析是指发现大量数据集合中项集之间有趣的关联或相关关系,展示 属性值频繁地在给定数据集中一起出现的条件,通俗地说就是挖掘数据库中一 组对象之间某种关联关系的规则,这种关联关系可以是诸如“同时发生”、“形 如a j b 的蕴涵式”。由此可知,关联规则挖掘首先找出频繁项集,然后由频 繁项集产生关联规则。大量数据之间的关联规则在决策分析领域或商业管理方 面是有用的,然而并非所有的关联规则都是有趣的;并且一般认为关联规则可 以作为进一步探查的切入点,而不应当直接用于没有进一步分析或领域知识的 预测。关联分析的目的是找出数据库中隐藏的关联网,在大型数据库中,这种 关联规则是很多的,一般用“支持度”,“可信度”两个阈值来淘汰那些无用的关 联规则。 6 ( 3 ) 聚类分析 聚类分析问题的基本特征就是将具有相似属性的一些目标对象化归为同一 个集合;也就是说,在对数据集进行分析时,训练数据中对象的类标记未知, 我们可以通过聚类产生这种类标记。类标记的产生是根据“最大化类内对象的 相似性,最小化类间对象的相似性”的原则进行分组,形成对象的聚类。这里 所形成的对象聚类可以视为对象类,由此导出类规则。它又称为无指导的分类, 与分类不同的地方在于聚类规则挖掘是直接针对原始数据进行的,而分类规则 挖掘则是基于类标记已知的数据。聚类增强了人们对客观现实的认识,即通过 聚类建立宏观概念。 ( 4 ) 时间序列模式分析 ( 可与关联分析相合并,此模式主要是加入时间因素的前后关联分析) 。时 间序列模式根据对随时间变化的对象分析,建立模型描述对象的变化规律和趋 势,这类分析的重要特点是考虑时间因素。在一定程度上时间序列模式分析与 关联模式分析相类似,但时间序列模式侧重考虑数据之间在时间影响下的关系。 ( 5 ) 偏差检验 也称为孤立点分析。在大量的数据中可能包含这样一类数据,他们与其它 绝大多数数据的行为或特征不一致。这些数据对象称为孤立点,其行为可以称 为有偏差的行为。偏差包括很多潜在的知识,如分类中的反常实例、不满足规 则的特例、观测结果与模型预测值的偏差、量值随时间的变化等。偏差检验主 要就是寻找出原始数据中的这些孤立点、描述出其偏差行为特征:然后进行分 析,判断这些孤立点的产生是由于操作或误差所导致,还是由于其它原因所导 致。偏差检测的基本方法是寻找观测结果与参照之间的差别,其有着广泛的应 用,如用于欺诈监测,探测不寻常的信用卡使用或电信服务;医疗分析中用于 发现对多种治疗方式的不寻常的反应等。 ( 6 ) 预测 预测是利用历史数据找出变化规律,即建立模型,并用此模型来预测未来 数据的种类、特征等。其模型的建立往往依据以上提到的种种数据挖掘功能。 尽管数据挖掘的任务按其功能可主要划分为如上几种类型,但是无论何种 类型的知识,其发现过程都是以用户需求为导向的。任何数据挖掘活动都是为 了寻找对用户而言是有趣的模式;除此之外,数据挖掘没有其它任何的目的。 1 2 4 数据挖掘的方法 ( 1 ) 粗糙集合( r o u g hs e t s ) 王l j 论 1 4 ,1 5 】 粗糙集理论是一种研究不精确、不确定性知识的数学工具,由波兰科学家 z p a w l a k 在1 9 8 2 年首先提出,这一方法在数据挖掘中具有重要的作用,通常 处理含糊性和不确定的问题,发现不准确数据或噪音数据内在的结构关系,还 7 可用于特征的约简和相关分析中。知识工程研究中,一直存在着信息的含糊性 ( v a g u e n e s s ) 等问题。含糊性有三种:术语的模糊性,如高矮:数据的不确定 性,如噪音引起的;知识自身的不确定性,如规则的前提与结果之间的依赖 关系并不是完全可靠的。 人工智能的基础理论之一一经典逻辑不足以解决这些不确定性问题。为此, 人们提出了一些解决方法,包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论,但这些方法都有一些内在缺陷或限定范围。例如,基于统计的方法 在理论上还难以令人信服;而模糊集方法则存在一个本质问题即如何确定成员 隶属度,相比之下,粗糙集方法则有几个优点! 不需要预先知道的额外信息,如 统计中要求的先验概率和模糊集中要求的隶属度,算法简单,易于操作。 租糙集对不精确概念的描述是通过上近似( u p p e ra p p r o x i m a t i o n ) 和下近似 ( 1 0 w e ra p p r o x i m a t i o n ) 这两个精确概念来实现的。一个概念( 或集合) 的下近似是 指其中的元组肯定属于该撅念;一个概念( 或集合) 的上近似是指其中的元组可 能属于该概念。 ( 2 ) 统计分析( s t a t i s t i c a la n a l y s i s ) 【9 】 统计分析的理论基础主要是统计学和概率论的原理,是一种较为精确的数 据挖掘技术,它是一种基于模型的方法,包括回归分析、因子分析和判别分析 等,该方法比较容易理解,对结果描述精确。但是当利用大规模数据集来学习 时,统计分析的评估代价变的很敏感。收集关于数据的各种统计量的代价随着 实例数目的增长而增大。尽管最近的收集技术可能减少这个收集活动的代价, 但对每个新的我们所要的统计量集合仍然要花费大量的时间。 ( 3 ) 概念格( c o n c e p tl a t t i c e ) 模型【7 ,1 2 】 r w i l l e 等提出了根据一个二元关系来建立相应概念格或g a l o i s 格的基本 思想,它在本质上描述了对象与属性之间的联系,表明了概念之闯泛化与例化 之间的关系。概念格的非形式化定义为: 给定上下文( c o n t e x t ) 为三元组t = ( o ,d ,r ) ,其中o 是对象集合,d 是性质 集合,r 是。和d 之间的二元关系,则存在唯一的偏序集合与之对应,并且这 个偏序集合产生一种格结构。这种由上下文所诱导出的格称为概念格。x r x 表 示0 中的一个元素x 与d 中一个元素x 之间有关系r 。格中每个结点是一个序 偶( 即概念) ,记为( a ,b ) ,其中a p ( 0 ) ,b p ( d ) ,p ( o ) 是0 的幂集,p ( d ) 是d 的幂集,称a 为概念的外延( e x t e n s i o n ) ,称b 为概念的内涵( i n t e n s i o n ) 。概念格 是一种完备的概念层次结构在信息检索、数字图书馆、软件工程、知识分类、 类的设计、网络管理和k d d 等领域,概念格已经显示出一定的应用价值。 ( 4 ) 决策树( d e c i s i o nt r e e ) 模型【1 6 ,1 7 1 决策树是通过一系列规则对数据进行分类的过程。它以信息论中的互信息 ( 信息增益) 原理为基础寻找数据库中具有最大信息量的字段,建立决策树的 s 一个结点,再根据字段的不同取值建立树的分枝;在每个分枝中集中重复建树 的下层结点和分技的过程,即可建立决策树。采用决策树,可以将数据规则可 视化,其输出结果也容易理解。该类方法的实用效果好,影响较大。 ( 5 ) 贝叶斯网络( b a y e s i a n n e t w o r k ) f 1 8 ,1 9 】 贝叶斯网络基于后验概念的贝叶斯定理,是建立在数据进行统计处理基础 上的方法。它将不确定事件通过网络连接起来,可以对于其他相关事件的结果 进行预测:此外其网络变量可以是可见的,也可隐藏在训练样本中。贝叶斯网 络具有分类、聚类、预测和因果关系分析的功能,其优点是易于理解,预测效 果较好,缺点是对发生频率很低的事件预测效果不好。其在医学和制造业等领 域的应用具有较好的效果。 ( 6 ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 2 0 ,2 1 1 人工神经网络建立在可以自学习的数学模型的基础之上。它可以对大量复 杂的数据进行分析,并可以完成对人脑或其他计算机来说极为复杂的模式抽取 及趋势分析。 神经网络系统由一系列类似于人脑神经元一样的处理单元组成,我们称之 为节点( n o d e ) 。这些节点通过网络彼此互连,如果有数据输入。它们便可以进 行确定数据模式的工作。神经网络的处理过程主要是通过网络的学习功能找到 一个恰当的连接加权值来得到最佳结果。其比较典型的学习方法是回溯法。它 通过将输出结果同一些已知值进行一系列比较,加权值不断调整,得到一个新 的输出值,再经过不断的学习过程,最后该神经网络得到一个稳定的结果。 ( 7 ) 小波理论( w a v e l e tt h e o r y ) i t 3 】 由于小波变换具有数学显微镜的特点和带有滤波的特性,因而特别适合于 非平稳信号的处理,将它应用于数据挖掘领域是十分有效的。随着小波理论的 不断完善,它必将与数据挖掘技术珠联璧合,天衣无缝。小波理论应用于数据 挖掘领域的结构模型如图1 2 所示。 图l 一2 小波理论模型 ( 8 ) 遗传算法( g e n e t i ca l g o r i t h m ) 2 2 ,2 3 】 这是模拟生物进化过程的算法,由三个基本算子组成:繁殖( 选择) 是从 一个父代选出生命力强的个体,产生新种群( 后代) 的过程;交叉( 重组) 选择两 9 个不同个体( 染色体) 的部分( 基因) 进行交换,形成新个体;变异( 突变) 对某些个 体的某些基因进行变异。 遗传算法可起到产生优良后代的作用。这些后代需满足适应值,经过若干 代的遗传,将得到满足要求的后代( 问题的解) 。 1 2 5 数据挖掘面临的挑战及研究热点 知识发现是当前涉及人工智能、数据库理论与技术、统计学以及电子商务 等学科的一个非常活跃的研究与应用领域。鉴于数据、数据挖掘任务和数据挖 掘方法的多样性,数据挖掘面l 临着许多挑战。如:更大规模数据库上的知识发 现问题:知识的评价和模式理解;挖掘过程中用户的交互等问题。 目前,数据挖掘的研究热点主要有数据挖掘语言的设计,高效而实用的数 据挖掘方法和系统的开发,以及应用数据挖掘技术解决实际应用问题等。 1 2 6 数据挖掘的发展方向 虽然数据挖掘领域已取得令人瞩目的进展。但由于数据挖掘技术还很不成 熟,其应用还有很大的局限性,一些急需解决和完善的问题也摆在了研究者的面 前: ( 1 ) 大规模数据的挖掘 有些挖掘算法在小规模数据库上可获得很好的挖掘结果,但在进行大规模 数据分析时的时空代价却比较大。大规模数据的挖掘技术是近年来研究人员研 究的重点。 ( 2 ) 复杂类型数据的挖掘 以前的数据挖掘面对的主要是以结构化数据为主的关系数据库、事务数据 库和数据仓库,随着数据处理工具、先进数据库技术以及w w w 技术的迅速发展, 空间数据、多媒体数据、时间序列数据、文本数据、w e b 数据复杂类型的数据 不断涌现。 ( 3 ) 证实技术的局限性 数据挖掘使用特定的分析方法或逻辑形式发现知识,但系统可能没有能力 去交互证实发现的知识,使得发现的知识没有普遍适应性而不能成为有用的知 识。 ( 4 ) 知识的维护和更新 新的数据积累可能导致以前发现的知识失效,这些知识需要动态维护和及 时更新,目前主要采用增量更新的方法来维护已有的知识。 ( 5 ) 数据挖掘语言的标准化 标准的数据挖掘语言或其他方面的标准化工作将有助于数据挖掘系统的开 1 0 发,改进多个数据挖掘系统和功能间的互操作,促进数据挖掘系统在企业和社会 中的使用。 1 3 本文的研究内容与组织 聚类分析作为数据挖掘领域中的一个重要分支,在模式识别、图像处理、 市场研究以及数据压缩等领域有着广泛的应用,出现了大量的研究和成果。本 文在对数据挖掘进行概述的基础上引入聚类分析技术及方法的相关介绍,客观 分析现有算法的优劣性,并结合现实世界数据特性及实际应用情况,提出面向 高维数据的变密度空间聚类算法研究。全文由五章组成: 第一章首先简述数据库知识发现产生的原因以及发展前景,概述了知识 发现的处理过程和特性,然后详细阐述了知识发现的核心技术- 数据挖掘的定 义、处理对象、功能、方法以及发展方向,最后介绍了在数据挖掘中引入抽样 技术的原因:适应大规模数据集的挖掘要求。 第二章首先介绍了聚类分析的概念、应用及潜在要求,探讨了聚类分析 中代表性的数据结构,并引入了各种类型数据之间的相异度计算问题;最后, 对主要聚类方法进行分类介绍并给出简要分析。 第三章剧增的数据规模要求聚类算法具有处理高维数据的良好时空性能 和聚类质量。其中,基于密度的聚类分析方法具有显著的优势,然而其自身的 设计缺陷导致其时空性能及适应性等方面的劣势,本章将在分析该类聚类分析 方法的基础上,给出行之有效的解决策略和方法,并从理论及实验上验证其合 理性和高效性。 第四章信息描述及存储技术的不断进步,使得现实世界中的数据呈现出 高维、变密度等复杂特性,也使得当前的聚类分析方法在处理此类数据时不可 避免地陷入困境。本章引入层次树模型对数据预处理,并动态、自适应地调整 局部参数进行聚类探测合并子聚类信息,获得了处理变密度聚类的优势性能。 第五章总结全文并对下一步工作进行展望。 第二章数据挖掘中的聚类分析 信息技术的飞速发展、分布式数据库的普遍应用、数据仓库技术的出现以 及由此带来的数据爆炸性增长业已激起对新技术和智能工具的需求,数据挖掘 作为一门新兴的、有希望的、欣欣向荣的前沿学科,方便我们从海量数据发现 隐含的、有价值的、以前未知的、可以被理解的信息和知识。 聚类分析【2 4 ,2 5 ,2 6 ,2 7 作为数据挖掘领域中的一个重要分支,在数据挖 掘、模式识别、图像处理、市场研究以及数据压缩等领域有着广泛的应用;此 外,聚类分析可以作为其他数据挖掘算法( 如特征和分类等) 的预处理步骤, 这些算法再在生成的簇上进行处理。 聚类( c l u s t e r i n g ) 就是将数据对象分组成为多个类或簇( c l u s t e r ) ,使得同一

温馨提示

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

评论

0/150

提交评论