（电力电子与电力传动专业论文）基于神经网络的智能数据挖掘方法及应用研究.pdf

墓于 a n n的d m方法及皮用研究 a n n - b a s e d d a t a mi n i n g a p p r o a c h a n d i t s a p p l i c a t i o n s i n gi s abstract d a t a m i n i n g i s a n o n t r i v i a l p r o c e s s t h a t w e c a n i d e n t if y t h e e ff e c t i v e , u n k n o w n , p o t e n t i a l ly u s e f u l a n d u lt i ma t e ly a p p r e h e n s i b l e p a t t e r n f r o m d a t a b a s e s . d a t a mi n i n g t e c h n i q u e i s a c r o s s mu l t i - f i e l d f o r r e s e a r c h e s a n d a p p l i c a t i o n s . s o i t r e c e i v e s mo r e a t t e n t i o n a n d b e c o me s o n e o f mo s t p o p u l a r r e s e a r c h i n r e c e n t l y . c l u s t e r i n g a n a l y s i s i s a n i mp o rt a n t a p p r o a c h o f d a t a m i n i n g , a n d a n i mp o rt a n t c o n t e n t o f h u m a n a c t iv it y . a s a b r a n c h o f s t a t i s t i c s , c l u s t e r in g a n a l y s i s h a s a l o n g r e s e a r c h h is t o r y . t h i s a rt i c l e t a k e s a s t e p f o r w a r d i n t h e a l g o r i t h ms o f c l u s t e r i n g a n a l y s i s a n d d i s c u s s e s t w o k i n d s o f c l u s t e r i n g a n a l y s i s m e t h o d s : k - m e a n s a l g o r i t h m m e r g e d i n d e n s it y - b a s e d , k - me a n s a l g o r i t h m m e r g e d i n c o mp e t i t iv e l e a r n i n g o f n e u r a l n e t w o r k s . o n t h e b a s e o f t h e d is c u s s i o n , a n e w i n t e g r a t e d c l u s t e r i n g a n a ly s i s a l g o r i t h m, a n d a n i m p r o v e d i n t e g r a t e d c l u s t e r i n g a n a l y s i s a l g o r it h m w i l l b e p r e s e n t e d . c o mp a r i n g t h e f o u r m e t h o d s , t h e i m p r o v e d i n t e g r a t e d c l u s t e r i n g a n a l y s i s a l g o r i t h m h a s m o r e v a l u a b l e i n d a t a m i n i n g . i n t h e d e s i g n o f s h i p r o u t e , f i r s t i s t o c h o o s e a n a r e a , i n o t h e r w o r d t o t a k e o u t o f s o me d a t a , t h e n t o p r e p r o c e s s t h e d a t a , a n d t h e n t o u s e t h e i m p r o v e d i n t e g r a t e d c l u s t e r i n g a n a l y s i s a l g o r i t h m t o f i n d c l u s t e r i n g p o i n t s , la s t o f a l l i s t o g e t c e n t r a l d e n s i t y p o i n t t h r o u g h c a l c u l a t i o n , c o n n e c t i n g w it h a l l o f t h e c e n t r a l d e n s i t y p o i n t s i s t h e s h i p r o u t e . a r t i f i c ia l n e u r a l n e t w o r k s a r e i mp o r t a n t a p p r o a c h e s o f d a t a mi n i n g , t o o . a n n c a n a p p r o x i ma t e a r b i t r a r i l y t o n o n l i n e a r m a p p i n g b y le a r n i n g . h o w e v e r , a l l o f t h e a n n p r e d ic t i v e m o d e l s j u s t c a n b e u s e d t o p r e d i c t 基于a n n的 d m 方法及应用研究 t h i n g s w i t h o n e a t t r i b u t o r , f o r e x a m p l e s t o c k f o r e c a s t . t h e r e h a v e n o t b e e n r e s e a r c h e s t o b e f o u n d f o r p r e d i c t i o n o f t h i n g s w it h m o r e a t t r i b u t o r s . t h i s a r t i c l e p r e s e n t s a n e w mu l t i - d i me n s i o n p r e d i c t i v e mo d e l b a s e d o n t h e d i a g o n a l r e c u r r e n t n e u r a l n e t w o r k s ( p d r n n ) w i t h a p a r a l l e l l e a r n i n g a l g o r i t h m. t h i s m e t h o d c a n b e u s e d t o p r e d i c t n o t o n l y v a l u e s , b u t a l s o s o me p o i n t s i n t h e mu l t i - d i me n s i o n s p a c e . a n d a l s o i t s a p p l i c a t i o n s i n d a t a m i n i n g w i l l b e d i s c u s s e d i n t h e p a p e r . s o m e a n a l y s i s r e s u l t s s h o w t h e s i g n i f i c a n t i mp r o v e me n t t o s h i p r o u t e p r e d i c t i o n u s i n g t h e p d r n n a lg o r it h m i n d a t a b a s e o f g e o g r a p h i c i n f o r m a t i o n s y s t e m ( gi s ) . i n a d d i t i o n , t h i s a rt i c l e h a s ma d e l o t s o f p r e d i c t i o n w i t h m a t l a b l a n g u a g e a n d g o t s a t i s f y i n g e f f e c t s . t h i s a rt i c l e g e t s s o me v a l u a b l e r e s u lt s i n t h e d a t a m i n i n g o f g i s w i t h t h e i mp r o v e d i n t e g r a t e d c l u s t e r i n g a n a l y s i s a lg o r i t h m a n d mu l t i - d i me n s i o n p r e d i c t i v e m o d e l b a s e d o n t h e d i a g o n a l r e c u r r e n t n e u r a l n e t w o r k s ( p d r n n ) w i t h a p a r a l l e l l e a r n i n g a l g o r i t h m . wa n g t i a n z h e n ( p o w e r e l e c t r o n i c s a n d e l e c t r i c d r i v e ) d i r e c t e d b y t a n g t i a n h a o k e y wo r d s : d a t a m i n i n g , c l u s t e r i n g a n a l y s i s , a n n , g i s 论文独创性声明 本 论文 是我 个人 在导师 指导下 进行的 研究 工作及取得的 研 究成 果。 论文 中 除 了 特 另 咖以 标注和 致 谢的 地方 外， 不包 含 其 他人 或其他机 构已 经发 表或 撰写过的 研究成果。 其他同志对本研究的 启发和所做的贡献均已 在论文中作 了明 确的 声明并表示了谢意。 作者签名: _日 期 论文使用授权声明 本人同 意上海海运学院有关保留、使用学位论文的规定，即: 学校有权 保留 送交 论文复印件， 允许论文被查阅 和借阅; 学校可以 上网 公布论文的 全 部或 部分内 容， 可以 采用 影印 、 缩印 或者其它 复 制手段保 存论文. 保密的 论 文在解密后遵守此规定。 作 者 签 名: 一 一 一 一 一 导 师 签 名:日 期: 羞于a n n的d m方法及应用研究 第一章引言 研 究背景 计算机与信息技术经历了半个世纪的发展，给人类社会带来了巨大 的进步和影响。近十几年来， 人们利用信息技术生产和搜集数据的能力大 幅度提高，干千万万个数据库被用于商业管理、政府办公、科学研究和 工程开发等等，据估计，1 9 9 3年全球数据存储容量约为 2 0 0 0 t b( ， 丁 = 1 0 2 4 g) ，到2 0 0 0年增加到 3 0 。 万t b ，面对这极度膨胀的数据信息量， 人们受到 “ 信息爆炸” 、 “ 混沌信息空间”( i n f o r m a t io n c h a o t ic s p a c e ) 和 “ 数据过剩 ( d a t a g l u t )的巨大压力。因此，面对 “ 人们被数据淹 没，人们却饥饿于知识”的挑战，数据挖掘( d a t a m i n i n g 筒称d m) 技 术和知识发现 ( k n o w l e d g e d i s c o v e ry i n d a t a b a s e , 简称 k d d ) 技术应 运而生，并得以蓬勃发展，越来越显示出其强大的生命力 们 。 d m就是从大量数据中抽取挖掘出未知的、 有价值的模式或规律等知 识的复杂过程。它的原始数据可以是结构化的，如关系数据库中的数据， 也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上 的异构型数据 2 3 。发现知识的方法可以是数学的，也可以是非数学的; 可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、 查询优化、袂策支持、过程控制等，还可以用于数据自身的维护。因此， d m是一门范围广泛的交叉学科， 它汇聚了不同领域的研究者， 尤其是数 据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技 术人员。在很多重要的领域。如银行、电信、保险、交通、零售、远程 通信、产品质量保证等，d m都可以发挥积极促进的作用。 当前，d m研究正方兴未艾，预计在 2 ， 世纪还会形成更大的高潮， 研究焦点可能会集中到以下几个方面: 研究专门用于 k d d的数据挖掘语 言，也许会像 s ql语言一样走向形式化和标准化:寻求 d m过程中的可 视化方法，使得 k d d的过程能够被用户理解。也便于在 k d d过程中的 人机交互;研究在网络环境下的 d m技术，特别是在 i n t e r n e t 上建立 d m 服务器，与数据库服务器配合，实现 d m;加强对各种非结构化数据的挖 掘，如文本数据、图形图像数据、多媒体数据。 基于a n n的d m方法及应用研究 1 . 2发展概况 为有效解决信息爆炸这一问题，自2 0世纪 8 0年代开始，d m技术逐 步发展起来，d m可以视为数据管理与分析技术的自然进化产物e k d d一 词首次出现在 ， 9 8 9年 8月举行的第 1 1 届国际联合人工智能学术会议上。 迄今为止，由美国人工智能协会主办的 k d d国际研讨会己经召开了7次， 规模由原来的专题讨论会发展到国际学术大会，人数由二三十人到七八百 人， 论文收录比例从 2比 ，到 6比 ， ，研究重点也逐渐从方法研究转向系 统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互 渗透。 其他内容的专题会议也把 d m和 k d d列为议题之一， 成为当前计算 机科学界的一大热点 3 1 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊 物也纷纷开辟了 k d d 专题或专刊。i e e e 的 k n o w l e d g e a n d d a t a e n g i n e e r i n g会刊领先在， 9 9 3 年出版了k d d技术专刊， 所发表的5 篇论 文代表了当时 k d d研究的最新成果和动态， 较全面地论述了k d d 系统方 法论、发现结果的评价、k d d系统设计的逻辑方法，集中讨论了鉴于数据 库的动态性冗余、高噪声和不确定性、空值等问题，k d d系统与其它传统 的机器学习、专家系统、人工神经网络、 数理统计分析系统的联系和区别， 以及相应的基本对策 4 1 . 6篇论文摘要展示了 k d d在从建立分子模型到 设计制造业的具体应用 。 不仅如此， 在 i n t e r n e t上还有不少 k d d 电子出版物，其中以半月刊 k n o w le d g e d is c o v e r y n u g g e t s 最为权威，另一份在线周刊为d s ( d s 代 表决策支持) , 1 9 9 7年 ， 0月7日开始出版。 在网上， 还有一个自由论坛 d m e m a i l c l u b ，人们通过电子邮件相互讨论 d m k d的热点问题。而领导整个 潮流的d mk d开发和研究中心， 当数设在美国e md e n的旧m公司开发部。 神经网络是 d m的重要方法之一，现在神经网络的研究己经获得许 多方面的进展和成果，提出了大量的网络模型，发现了许多学习算法， 对神经网络的系统理论进行了成功的探讨和分析.在此基础上，人工神 经网络还在模式分类、机器视觉、机器听觉、智能计算、机器人控制、 信号处理、组合优化问题求解、联想记忆、编码理论、医学诊断、金融 决策、d m等领域获得了卓有成效的应用 5 3 墓于a n n的d m方法及应用研究 1 . 3数据挖掘存在的问题 经过十多年的工作，数据挖掘技术的研究与应用已取得了很大的成 果，然而，我们还面临着许多问题: ( ， )各种数据挖掘问题及挖掘方法基于不同的模型和技术，彼此互 相孤立 ，联系很少; ( 2 )数据挖掘处理高维数据的能力有待提高; ( 3 )数据挖掘系统仅提供孤立的知识发现功能，难于嵌入大型应用; ( 4 )数据挖掘在其应用领域上还可以扩展等; ( 5 )数据挖掘中的具体算法在解决具体问题时还需完善。 聚类分析是一个正在蓬勃发展的领城。聚类分析所涉及的领域包括: 数据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等 6 1 由于各种应用数据库所包含的数据量越来越大，聚类分析已成为数据挖掘 中一个非常活跃的研究课题。但聚类分析本身也不是尽善尽美的，存在一 定的问题，比如:可扩展性、复杂形状和复杂数据类型的聚类分析及其有 效高效性、高维聚类技术，以及混合数值属性与符号属性数据库中的聚类 分析方法等。这些鱼待解决的问题是当前 d m领域的研究热点之一。 神经网络是数据挖掘的重要方法之一，迄今为止，己经有 3 0多种人 工神经网络模型被开发和应用。因为神经网络对噪声数据有较好的适应能 力，并且对未知数据也具有较好的预测分类能力。但现在的预测只局限于 一维空间的时序预测 7 ，对于多维空间的时序预测还未见报道。 1 . 4本文的工作 本文来源于上海市教委重点学科建设项目【 沪教委科( 2 0 0 1 ) 7 1 】 的资 助，并获得来自中法国际合作项目中的 g p s数据支持。本文在基于 a n n 的d m方法上进行了研究与探索，针对目前在 d m存在的问题，从方法论 角度探讨了基于 a n n聚类分析方法和多维预测方法; 在此基础上， 将所研 究的结果应用于船舶航运信息的数据挖掘，得到的主要研究结果如下: 1 、采用自组织竞争神经网络算法进行船舶航线设计; 2 、提出一种复合聚类分析方法进行船舶航线设计; 3 、提出一种改进的复合聚类分析算法进行船舶航线设计: 墓于a n n的d m方法及应用研究 4 、提出一种基于并行对角递归神经网络的预测模型，可以对多维 ( 属性) 的事物进行预测 : 5 、将这个预测模型应用在 gi s系统的船位预测当中; 6 、在 p d r n n网络中采用输入调正法， 提高了网络的预测精度， 缩短了网 络 的计算 时间。 本文共分六章，第一章是引言，简要地介绍本文的研究背景、数据挖 掘 的发展情况 ，以及存在的 问题 。 第二章主要介绍数据挖掘的基本原理与方法。主要介绍了传统的聚类 分析方法和神经网络方法。还介绍了现在较为流行的数据挖掘软件。 第三章采用基于密度方法和神经网络方法进行聚类分析，提出一种复 合聚类算法和一种改进的复合聚类算法。文中给出了聚类效果图。 第四章提出了一种基于并行对角递归神经网络的预测模型，并推导了 算法， 将其应用于多维空间的时序预测。 文中给出了预测效果图和流程图。 第五章主要介绍了基于 a n n的 d m方法在 g i s中的应用，首先简单 介绍了gi s的构成， 以及 g i s在航海中的应用。 详细介绍了聚类分析算法、 神经网络方法在 g i s中的应用。 第六章总结全文，并展望下一步的工作。 基于a n n的d m方法及应用研究 第二章 数据挖掘的基本原理与方法 2 . 1数据挖掘的基本原理 d m是2 0世纪末刚刚兴起的数据智能分析技术， 它可以从数据库或数 据仓库 ，以及其他各种大量数据类型中， 自动抽取或发现有用的模式知识 d m又称为数据库中知识发现，是整个知识挖掘过程的一个主要步骤 “ 。 一个典型的 d m系统如图 2 - ，所示。 可视化 解释评价 交换 预处理 透排与转换 数据仓库目标数据预处理数据 知 识 图 2 - t d m过程示意图 . 数据选择与转换:确定发现任务的操作对象，即目标数据 ( t a r g e t d a t a ) ，并将数据转换为易于进行 d m的数据存储形式。 . 数据预处理 ( d a t a p r e p r o c e s s i n g ) :一般可能包括消除噪声、推导计 算缺失数据、消除重复记录、完成数据类型转换等 9 7 . 数据变换 ( d a t a t r a n s f o r m a t io n ) :消减数据维数或降维 ( d i me n s i o n r e d u c t i o n ) ， 即从初始特征中找出真正有用的特征以减少数据开采时要 考虑的特征或变量个数。 . d m:利用智能方法挖掘数据模式或规律知识。 . 解释评价: 根据一定评估标准 ( i n t e r e s t i n g m e a s u r e ) 从挖掘结果筛选 出有意义的模式知识。 墓于a n n的d m方法及应用研究 2 . 1 . 1 数据挖掘的功能 d m 技术可以帮助或者决策所需的多种知识，比如:广义型知识一一 反映同类事物共同性质的知识;特征型知识一一反映事物各方面的特征知 识;差异型知识一一反映不同事物之间属性差别的知识 ;关联型知识一一 反映事物之间依赖或关联的知识;预测型知识一一根据历史的和当前的数 据推测未来数据;偏离型知识一一揭示事物偏离常规的异常现象。所有这 些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到 中观再到宏观，以满足不同用户、不同层次决策的需要 01 。 d m的功能如下所示: 1 .数据总结 数据总结的目的是对数据进行浓缩， 给出它的紧凑描述。 传统的也是 最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、 方差值等统计值，或者用直方图、饼状图等图形方式表示。 d m主要关心从数据泛化的角度来讨论数据总结。 数据泛化是一种把 数据库中的有关数据从低层次抽象到高层次的过程。数据泛化目前主要 有两种技术:多维数据分析方法和面向属性的归纳方法1 1 。 2 .概念描述 一个概念常常是对一个含大量数据的数据集合总体情况的概述。概 念描述是对含有大量数据的数据集合进行概述性的总结并获得简明、准 确的描述。获得概念描述的方法主要有以下两种: . 利 用 更 为 广 阔 的属 性 ，对 所 分 析 数 据 进 行 概 要 总 结 (d a t a c h a r a c t e r iz a t i o n ) ;其中被分析的数据就成为目标数据集 ( t a r g e t cl a s s ) . . 对两类所分析的数据特点进行对比并对对比结果给出概要性总结， 而其 中两类 被 分析 的数据 集 分别被 称 为 目标数据 集和对 比数 据集 ( c o n t r a s t i n g c la s s ) 1 2 1 。 3 .分类 分类是 d m中一项非常重要的任务。分类就是找出一组能够描述数据 集合典型特征的模型 ( 或函数) ，以便能够分类识别未知数据的归属或类 基于a n n的d m方法及应用研究 别，即将未知事例映射到某种离散类别之一。分类挖掘所获得的非类模 型可以采用多种形式加以描述输出 1 3 1 4 .聚类 聚类是根据数据的不同特征，将其划分为不同的数据类。它的目的 是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个 体之间的距离尽可能的大。在统计方法中，聚类亦称聚类分析，它是多 元数据分析的三大方法之一 1 4 1 。 本文在下一小节中将会详细介绍聚类的 一些方法 。 5 .相关性分析 相关性分析的目的是发现特征之间或数据之间的相互依赖关系。数 据相关性代表了一类重要的可发现的知识。一个依赖关系存在于两个元 素之间。如果从一个元素a的值可以推出另一个元素 b的值，则称 b依 赖于 a 。 这里所谓元素可以是字段， 也可以是字段间的关系。数据依赖关 系有广泛的作用( 1 5 1 o 6 .偏差分析 偏差分析包括分类中的反常事例、例外模式、观测结果对期望值的 偏离以及侧量值随时间的变化等，其基本思想是寻找观察结果与参照量 之间的有意义的差别 6 j 。 通过发现异常， 可以引起人们对特殊情况加倍 注意。异常包括如下几种可能引起人们兴趣的模式:不满足常规类的异 常例子;出现在其它模式边缘的奇异点;与父类 ( 父子关系)或兄弟类 ( 并列关系)不同的类;在不同时刻发生了显著变化的某个元素或集合; 观察值与模型推测的期望值之间有显著差异的事例等。偏差分析的一个 重要特征就是它可以有效地过滤大量的不感兴趣的模式。 7 .建模 建模就是通过 d m ，构造描述一种活动或状态的数学模型 1 7 1 。 机器 学习中的知识发现，实际上就是对一些自然现象进行建模，重新发现科 学定律 。 现在关于d m和k d d的研究人员来自各行各业， 也取得了一定的成果， 预计在本世纪还会形成更大的高潮，d m 的功能将会更加完善，渗透在许 多领域的决策支持和应用中。 基子a n n的d m方法及应用研究 2 . 2 dm 方 法 d m 包含很多的方法，如分类与预测中有基于决策树的分类、贝叶斯 分类方法、 神经网络分类方法等; 聚类分析中有层次方法、 基于密度方法、 基于网格方法、基于模型聚类方法等，还有现在比较热门的粗糙集方法。 因为本文主要研究聚类分析和预测的方法，所以将聚类的方法，还有 预测的方法介绍一下，做一下比较分析。 2 . 2 . 1聚类分析方法 聚类的定义 :将一个数据集划分为若干组 过程并使的同一组 内对象具有较高的相似度， 不相似 的 。 ( c l a s s )或类 ( c l u s t e r )的 而不 同组 中的数据对象则是 1 、划分方法:给定包含 n个数据对象的数据库和所要形成的聚类个数 k , 划分算法将对象集合划分为k 份 ( k 5 n ) ，其中，每个划分代表一个聚类。 所形成的聚类使得一个客观划分标准 ( 常称为相似函数，如:距离)最优 化， 从而使得一个聚类中的对象是“ 相似”的， 而不同聚类中的对象是“ 不 相似”的。最常用也是最知名的划分方法就是 k - me a n s算法和 k - m e d o id s 算法。k - m e a n s 算法的各聚类本身尽可能紧凑，各聚类之间尽可能分开。 计算复杂度o ( n k t ) ， 处理大数据库相对有效 ( 具有可扩展性) ， 终止于局部 最优 1 8 3 。不足之处是只适应于聚类均值有意义的情况 ( 如，资料集包含 符号属性时，直接用次算法有困难) ;用户还必须事先指定聚类个数 k :不 适于发现非凸形状的聚类或具有不同大小的聚类;对噪声和异常数据也很 敏感。k - m e d o i d s 聚类算法比k - m e a n s 聚类算法在处理异常数据和噪声数 据方面更为鲁棒， 但 k - m e d o i d s 聚类算法比k - m e a n s 聚类算法的处理时间 长 。 2 、层次方法:是通过将数据组织为若干形成一个相应的树来进行聚类的。 基本的层次聚类方法又可以分为自 上而下和自下而上层次聚类两种 拍 。 一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到 影响。目前的研究都强调 自下而上层次聚类与循环再定位方法相结合。 b i r c h ( b a l a n c e d i t e r a t iv e r e d u c i n g a n d c l u s t e r i n g u s i n g h i e r a r c h i e s ) 方法是一个集成的层次聚类方法，这种方法能获得较好的聚类速度，可对 基于a n i% 的d m方法及应用研究 大数据库进行处理的可扩展性。在进行增量和动态聚类时也很有效，实验 结果表明:就对象数目和聚类的质量而言，此算法表现出线性可扩展性。 存在的不足:由于大小限制， c f树中的每个节点仅能容纳有限的入口，因 此一个 c f树节点并不能对应用户所认为的一个自然聚类。如果聚类不是 圆状，则会由于次算法是利用半径来控制一个聚类半径的，从而导致算法 的性能变差。 c h e m a l e o n是一个探索层次聚类中动态模型的聚类算法， 在其聚类 过程中，如果两个聚类间的连接度和相似度与聚类内部的连接度和相似度 相近，那么就合并这两个聚类 2 0 1 。基于动态模型的合并过程将有助于发 现自然和同质的聚类，并在定义了有关相似函数的情况下适应于任何的数 据类型。 不足之处是在最坏情况下处理高维资料还可能需要。 ( n 2 ) 时间。 3 、基于密度方法: 能够帮助发现具有任意形状的聚类。 一般在一个数据空 间中，高密度的对象区域被低密度 稀疏)的对象区域 ( 通常就认为是噪 声数据 )所 分 割 o d b s c a n ( d e n s it y - b a s e d s p a t ia l c l u s t e r i n g o f a p p l i c a t i o n w it h n o i s e ) 是一个基于密度的聚类算法， 该算法通过不断生长 足够高密度区域来进行聚类，它能从含有噪声的空间数据库中发现任意形 状的聚类。计算复杂度o ( n l o g ) 。该算法不足之处是对用户所要设置的参 数敏感。 为t克服这一问 题， 人们提出o p t i c s ( o r d e r i n g p o i n t s t o i d e n t if y t h e c lu s t e r i n g s t r u c t u r e ) 算法，这种算法并不明确产生一个聚类，而是为 自动交互的聚类分析计算出一个增强聚类顺序.计算复杂度。 ( n l o g ) , 4 、 基于网格方法: 利用多维网格数据结构， 将空间环分为有限数目的单元， 以构成一个可以进行聚类分析的网格结构。s t i n g ( s t a t i s t i c a l i n f o r m a t i o n g r i d ) 是一个基于网格多分辨率的聚类方法，这种方法与查询要求无关;有 助于实现并行运行和增量更新;仅扫描一边数据库以获得各单元的统计信 息，产生聚类时间复杂度为。( n ) ，进行查询的实际复杂度为o ( g ) , g 为最低层所有网格数， g 比n 小的多 2 1 7 。 缺点是所获得聚类形状是直方的， 没有对角边界，尽管处理速度很快，但会降低聚类的质量和准确性。 c l i q u e ( c l u s t e r i n g i n q u e s t )算法将基于密度与基于网格方法结合 起来。它在处理大数据库中的高维资料比较有效，能自动发现最高维中所 存在的密度聚类，对输入资料元组顺序不敏感，也不需要假设任何特定的 资料分布，它与输入资料大小成线性关系，并当资料维数增加时具有较好 的可扩展性。但是在追求方法简单的同时，往往就会降低聚类的准确性。 _基于a n n的。 m方 祛及 应用 研究 5 、 基于模型聚类方法: 就是试图将给定数据与某个数学模型达成最佳拟合。 基于模型聚类的方法主要由两种:统计方法和神经网络方法。 c o b we b是统计方法的一种， 一个常用且简单的增量式概念聚类， 它 是采用分类树的形式来创建一个层次聚类，有能力自动调整一个划分中的 聚类个数 2 2 1 。存在的缺点就是:基于各属性的概率分布均是相互独立的 假设，由于属性间经常存在相互关联，因此这种假设并不总是成立;聚类 的概率分布表示使得它较难更新和存储聚类;对于分布异常的资料所产生 的分类树并不一定是平衡的，同时也会导致时间和空间复杂度急剧增大。 神经网络聚类算法是将每一个聚类描述成一个例证，是把算法和结果 统一为一体的系统，这是一种硬拌和软件的混合体，由于在某种程度上模 拟大脑的结构， 所以这种系统有更高的智慧并可能有更快的计算速度1 2 3 1 它的自由度增加，使存储空间扩大，因而存储容量可以更大:容错性大为 提高，这是因为高维空间中每一状态有更多的近邻，使多体效应更加复杂 和显著，另外，多维空间会有相变，对知识的存储和学习有重要意义;高 维空间更易于分类，分类就是识别事物，其原则是使同类事物更聚类，异 类事物更分离，此原则在高维空间中更易实现。 2 . 2 . 2人工神经网络方法 目前人工神经网络 ( a n n )模型己有 4 0多种，按照网络结构可分为前 馈型和反馈性: 按照学习方式可分为有导师 ( 指导) 学习、 无导师学习( 自 组织学习包括在内) 、再励 ( 强化)学习; 按照网络的性能分为连续性和离 散性、确定性和随机性网络 2 4 1 。按照突触连接的性质分为一阶线性关联 与高阶非线性关联网络。以下按照神经网络的学习方式介绍一下神经网络 的模型以及学习算法 ， 1 .神经网络的结构 a n n的结构基本上分为两类 ，即前馈网络反馈网络和简介如下: ( ， )前愤网络 前馈网络具有递阶分层结构，有一些同层神经元间不存在互联的层级 组成 一 层 从输入层至输出层的信号通过单向连接流通 不存在同层神经元间的连接，如图 2 - 2所示 ，神经元从一层接至下 基于a n n的o m方法及应用研究 2 )反馈网络 在反馈网络中多个神经元互联以组织一个互联神经网络，如图 2 - 3所 示。有些神经元的输出被反馈至同层或前层神经元。因此，信号能够从正 向和 反向流通 。 _ _ 一 反 cl ft - - , 翰入层隐层抽 出层 图 2 - 2 前恢网络图 2 - 3 递 归网络 2 .神经网络的学习方式 通过向环境小组学习获取知识并改进 自身性能是神经网络的一个重要 特点。在一般情况下，性能的改善是按某种预定的度量通过调节自身参数 ( 如权值)逐步达到的。学习方式有三种1 2 5 1 ( 1 )监督学习 ( 有导师学习) 如图 2 - 4所示 ， 这种学习 方式需要外界存在一个 “ 教 师” ，它可对给定一组输入提 供应有的输出结果，这组已 知的输入一输出数据成为训 练样本集，学习系统 ( 神经 网络)可根据已知输出与实 际输出之间的差值 ( 误差信 号)来调节系统参数。 图 2 - 4 有导师指导的学习框图 2 )非监督学习 ( 无导师学习) 如图 2 - 5所示，非监督学习不存在 外部教师，学习系统完全按照环境提供 图 2 - 5 无导师指导的学习框图 基于a n n的d m方法及应用研究 数据的某些统计规律来调节自身参数或结构 ( 这是一种自组织过程) ， 以表 示出外部输入的某些固有特性 ( 如聚类或某种统计上的分布特征) 。 ( 3 )再励学习 ( 强化学 习) 如图 2 - 6所示，这种学习介于上述 两种情况之间，外部环境对系统输出结 果只给出评价信息 ( 奖或惩)而不是给 出正确答案( 2 6 1 。学习系统通过强化那 些受奖的动作来改善自身的性能。 动 作 学 习系 统环 境 状 态 图 2 - 6再励学习框 图 3 .神经网络的学习算法 ( 学习规则 ) ( 1 )误差纠正学习 令y k ( n )为输入x k ( n )时， 神经元在n 时刻的实际输出， d k ( n ) 表示应有 的输出 ( 可由训练样本给出) ，则误差信号可表示为 e k ( n ) =成( ” ) 一 y k ( n )( 2 . 1 ) 误差纠正学习的最终目的是使某一基于 e k ( n )的目标函数达到最小， 以使网络中每一输出单元的实际输出在某种统计意义上逼近应有输出。- 旦选定了目标函数形式，误差纠正学习就变成了一个典型的最优化问题。 最常用的目标函数就是均方误差判据，定义为误差平方和的均值: ， 一 1万 e22 k k问 ( 2 . 2) 其中e为求期望算子，上式的前提是被学习的过程是平稳的，具体方法可 用最优梯度下降法。直接用 j 作为目标函数时需要知道整个过程的统计特 性，为解决这一问题，通常用在j 时刻n 的瞬时值聋 ( 的代替，即 g (n ) = _12 乒(n) ( 2 . 3) 问题变为求叔 n ) 对权值 气 w 的极小值，根据梯度下降法可得 = r) e k ( n ) x , ( n )( 2 . 4) 其中r1 为学习步长，这就是通常所说的误差纠正学习规则 ( 或称d e l t a 学习规则) 2 7 1 。 在自 适应滤波器理论中， 对这种学习的收敛性及其统计特 性有较深入的分析 。 基于a n n的d m方法及 应用研究 ( 2 ) h e b b学习 由神经心理学家 h e b b提出的学习规则可归纳为 “ 当某一突触( 连接) 两端的神经元同步激活 ( 同为激活或同为抑制)时，该连接的强度应增强， 反之应减弱”c 2 8 1 。用数学方式可描述为 、 ， 一 二 wn )x ; (n ) ) 式中y k ( n )， x j ( n ) 分别为， kj 两端神经元的状态， 是 ( 2 . 5: 其中最常用的一种情况 嘴 = ?7y , ( n ) x ; ( n ) ( 2 . 6) 由于 w 4 与y k ( n )， x i ( n )有关，有时称为相关学习规则。 ( 3 )竞争 ( c o m p e t i t i v e )学习 在竟争学习时，网络各输出单元互相竟 争， 最后达到只有一个最强者徽活， 最常见的 一种情况是输出神经元之间有侧向抑制性连 接，这样原来输出单元中如有某一单元较强， 则它将获胜并抑制其它单元 ， 最后只有此强者 处于徽活状态。最常用的竞争学习规则可写 为 : 田 2 - 7具有翻向抑刹性 连接的竞争学习网络 = f a x , 一 w) ， = 0 若神经元1 竞争获胜 若神经元j 竞争失败 2 . 2 . 2 . 4神经网络学习与自适应问题 当学习系统所处环境平稳时 ( 统 计特性不随时间变化) ， 从理论上 讲通过监督学习可以学到环境的 统计特性，这些统计特性可被学 习系统 ( 神经网络)作为经验记 住 。如果环境是非平稳的 ( 统计 特性随时间变化) ， 通常的监督学 习没有能力跟踪这些变化，为解 决此 问题 适应能 力 需要网络有一定的 自 此时对于每一不同输 入都作为一个新的例子来对待 。 图 2 - s 自适应系统框图 基于a n n的d m方法及应用研究 其工作过程如图 2 - 8 2 9 1 所示，此时模型 ( 即神经网络)被当作一个预测 器，基于前一时刻x ( n - 1 )和模型在 ( n - 1 )时刻的参数，它估计n时刻的输 出z ( n ) , ac ( n ) 与实际值x ( n ) ( 作为应有的正确答案)比较， 其差值称为“ 新 息” ，如新息 e ( n ) =0 ，则不修正模型参数，否则应修正模型参数以便跟踪 环境 变化 。 2 . 3 d m的主要软件工具 2 0世纪 9 0年代以来，一些 d m软件被先后开发出来。经过近十年 的发展，现在 d m软件已经得到相当广泛的应用。根据 d m软件的适用 范围可以分为专用 d m软件和通用 d m软件。专用 d m软件针对某个特 定领域的问题提供解决方案，在设计算法的时候充分考虑到数据、需求 的特殊性，并作了优化。而通用 d m 工具不区分具体数据的含义，采用 通用的挖掘算法，处理常见的数据类型。以下介绍了几种常用的 d m软 件 。 2 . 3 . 1 ma t l a b工具箱 m a t l a b语言起源于 1 9 8 0年美国学者 c l e v e r m o l e r 教授在线性代数 领域的早期工作，在科学运算、自动控制及其他工程领域它都作为首选的 计算机工具。m a t l a b 具有强大的数学运算能力、方便使用的绘图功能及语 言的高度集成性，在其他科学领域的应用也是越来越广。 1 . m a t l a b神经网络工具箱 神经网络工具箱以人工神经网络理论为基础， 用 ma t l a b语言构造出典 型神经网络的激活函数，如 s型、线性、竞争层、饱和线性等激活函数， 使设计者对所选定网络输出的计算，变成对激活函数的调用。 2 . ma t l a b数理统计工具箱 数理统计工具箱包含 d m中的许多方法，例如聚类分析方法、主成分 分析方法、鲁棒回归等等。其中也有一些模型，例如常用线性模型、非线 性回归模型以及一些直接可调用的分布函数。 ma t l a b的功能和各种各样的工具箱，使它具有如下特点: 基子a n n的d m方法及应用研究 开放式的体系结构; 先进的界面技术 ; 丰富的技术支持 ; 集成了许多领域专家的智慧。 勺3 2 . 3 . 2 p o l y a n a l y s t ( p a )简介 尸 八可对数据集进行的处理有:查看、编辑、创建和删除数据集，以及 根据用户指定的参数随机对数据集进行抽样， 等宽等深分隔， 逻辑运算等。 p a还可以从多数据源中导入数据: 它所能提供的是一种套 d m算法， 实现 了多策略挖掘;而且具有层次化体系，可以在不同阶段采用不同算法;p a 还有强大的结果显示功能，支持 s r l ，提供时间和日期函数，既可以用于 已 有数据的属性生成新的属性，也