（计算机应用技术专业论文）基于gmdh的自组织数据挖掘算法研究.pdf

中国科学技术大学硕士学位论文 摘要 数据挖掘是从大量、不完全、有噪声的数据中提取隐含于其中的并不为人们 所知，但又是潜在有用的信息和知识的过程。目前大部分的数据挖掘方法往往对 使用者具有很高的要求，而引入人为因素往往会影响建模的质量。自组织数据挖 掘方法以数据分组处理方法( g r o u pm e t h o do f d a t ah a n d l i n g , g m d h ) 为核心，使 用演化( 交叉、变异和选择) 的原则实现模型结构综合和模型确认的自动过程，所 得模型在记忆能力和泛化能力间达到最佳的平衡。自组织数据挖掘方法针对不同 的应用问题设计了一系列算法，其中最具普适性、应用最为广泛的是g m d h 多 层建模算法。本文针对g m d h 多层建模算法的以下两个方面问题进行了研究： ( 1 ) 对g m d h 多层建模算法中部分多项式( 参考函数) 的改进。原有的部分多 项式求解算法使得模型复杂度增长过快，很多潜在的能够更好的描述未知系统的 模型将被忽略；另外由于部分多项式的求解基于回归分析，因此回归分析中多重 共线性的问题也难以避免。本文从分析快速递归算法( f a s tr e c u r s i v ea l g o r i t h m ， f r a ) 中潜在的多重共线性问题入手，提出一种回归项线性相关的检测算法，改 进后的快速递归算法被用于g m d h 多层建模算法的部分多项式系数估计，新算 法建立的模型具有更强的泛化能力且结构更加简单。与同类型的改进算法相比， 该算法具有更小的计算开销。 ( 2 ) 提出一种选择性g m d h 网络集成学习算法。g m d h 多层建模算法能够在 对训练样本进行划分的基础上建立在记忆能力和泛化能力达到最佳平衡的最优 复杂度模型，但不同的样本划分将得到不同的模型，因此难以保证模型的全局最 优性。本文基于集成学习理论提出一种选择性g m d h 网络集成算法。首先将惩 罚性样本划分算法用于候选个体的构造，从而提高了候选个体之间的多样性；再 利用遗传算法选取候选个体集合的最优子集进行集成从而解决了如何确定 g m d h 网络集成规模的问题。 关键词：自组织数据挖掘，数据分组处理方法，回归分析，快速递归算法，选择 性集成学习 中国科学技术大学硕士学位论文 a b s t r a c t d a t an l i i l i n gi sap r o c e s sw h i c ha i m st oe x t r a c tp o t e n t i a l l yu s e f u li n f o r m a t i o na n d k n o w l e d g ef r o mm a s s i v ed a t ac o l l e c t e di n c o m p l e t e l ya n dn o i s i l y m o s to ft h eu pt o d a t ed a t am i n i n gm e t h o do f t e na s kf o r t h er s e r sw i t hs u p e r i o rc a p a b i l i t y h o w e v e r , t h e a r t i f i c i a le x p e r i e n c e sw i l la f f e c tt h eq u a l i t yo f t h ec o n s t r u c t e dm o d e l b a s e do ng r o u p m e t h o do fd a t ah a n d l i n g ( g m d i - d ，s e l f - o r g a n i z e dd a t am i n i n gm e t h o di m p l e m e n t s t h ea u t o m a t i cp r o c e s so fm o d e ls t r u c t u r es y n t h e s i sa n dm o d e lv e r i f i c a t i o nb yh i r i n g t h ee v o l u t i o n a r yo p e r a t i o n s ( c r o s s o v e r , m u t a t i o na n ds e l e c t i o n ) t h ec o n s t r u c t e d m o d e lm a yr e a c ht h eo p t i m a lb a l a n c eb e t w e e nm e m o r i z a t i o na n dg e n e r a l i z a t i o n v a r i e t i e so fs e l f - o r g a n i z e dd a t aa l g o r i t h m sa r ep r o p o s e da n de a c ha l m sa ts o l v i n g s o m es p e c i a lp r o b l e m sw h i l et h eg m d hm u l t i l a y e ra l g o r i t h mi st h em o s tw i d e l y u s e do n ef o ri t su n i v e r s a l i t y t h i st h e s i sf o c u s e so nt h ef o l l o w i n gt w oi s s u e s ： ( 1 ) i m p r o v et h ep a r t i a ld e s c r i p t i o n ( r e f e r e n c ef u n c t i o n ) i ng m d hm u l t i l a y e r a l g o r i t h m t h eo r i g i n a la l g o r i t h mf o rs o l v i n gt h ec o e f f i c i e n t so f t h ep a r t i a ld e s e r i p t i o n m a yl e a dt ot h eo v e r - i n c r e a s i n go ft h em o d e l sc o m p l e x i t y t h u sm a n ym o d e l sw h i c h m a yd e s c r i b et h eu n k n o w ns y s t e mb e t t e rm a yb ei g n o r e dd u r i n gt h ec o n s t r u c t i n g p r o c e s s b e s i d e s ，s i n c et h eo r i g i n a la l g o r i t h mi sb a s e do nr e g r e s s i o na n a l y s i s ，t h e p r o b l e mo fm u l t i c o l l i n e a r i t ym a yn o tb ea v o i d e d s t a r t i n gw i t l lt h ea n a l y s i so ft h e p o t e n t i a lp r o b l e mo fm u l t i c o l l i n e a r i t yi n f a s tr e c u r s i v ea l g o r i t h m ( f r a ) ，a l l a l g o r i t h mf o rd e t e c t i n gt h ec o l l i n e a r i t yb e t w e e nt h er e g r e s s o r si sp r o p o s e di nt h e t h e s i sa sa ni m p r o v e m e n ti nf r a a st h em a i np a r to fg m d h m u l t i l a y e ra l g o r i t h m ， t h ei m p r o v e df r ai st h e nh i r e df o rs o l v i n gt h ec o e f f i c i e n t so f t h ep a r t i a ld e s c f i p t i o n s t h em o d i f i e dg m d hm u l t i l a y e ra l g o r i t h mm a yc o n s t r u c tt h em o d e lw i t hs u p e r i o r g e n e r a l i z a t i o nc a p a b i l i t y i nap a r s i m o n i o u s s t y l e c o m p a r e dw i mt h e s i m i l a r m o d i f i c a t i o ni ng m d hm u l i t - l a y e ra l g o r i t h m ，t h en e wa l g o r i t h mm a yr e d u c et h e c o m p u t a t i o nc o s ts i g n i f i c a n t l y ( 2 ) p r o p o s eas e l e c t i v eg m d hn e t w o r ke n s e m b l ea l g o r i t h m g m d hm u l t i l a y e r f l g o r i t h mm a yc o n s t r u c tt h em o d e lw h i c hm a yr e a c ht h eo p t i m a lb a l a n c eb e t w e e n 中国科学技术大学硕士学位论文 m e m o r i z a t i o na n dg e n e r a l i z a t i o n h o w e v e r , d i f f e r e n td a t ap a r t i t i o nm a yl e a dt o d i f f e r e n tm o d e l s ，s ot h eg l o b a lo p t i m a l i t ym a yn o tb ee n s u r e d b a s e d0 1 1t h et h e o r yo f e n s e m b l el e a r n i n g ，as e l e c t i v eg m d hn e t w o r ke n s e m b l ea l g o r i t h mi sp r o p o s e di nt h i s t h e s i s f i r s t l y , ap u n i t i v ed a t ap a r t i t i o na l g o r i t h mi sh i r e df o rc o n s t r u c t i n gt h e c a n d i d a t ei n d i v i d u a l st oi m p r o v et h ed i v e r s i t yb e t w e e nt h ei n d i v i d u a l s t h e nt h e g e n e t i ca l g o r i t h mi sh i r e df o rs e l e c t i n gt h eb e s ts u b s e to ft h ec a n d i d a t ei n d i v i d u a l st o f o r mt h ee n s e m b l e i nt h i sw a y , t h es i z eo f t h ee n s e m b l em a yb es e t t l e da u t o m a t i c a l l y k e y w o r d s ：s e l f - o r g a n i z e d d a t am i n i n g ，g r o u pm e t h o do fd a t a h a n d l i n g ， r e g r e s s i o na n a l y s i s ，f a s tr e c u r s i v ea l g o r i t h m , s e l e c t i v ee n s e m b l el e a r n i n g 中国科学技术大学硕士学位论文 图表目录 图1 1 数据挖掘过程3 图1 2 组合算法建模示意图6 图1 3 多层算法建模示意图7 图1 4o s a 建模示意图1 1 图2 1g m d h 网络结构示意图2 2 图2 2 误差下降比例3 2 图2 3 g m d h 算法学习训练样本能力示意图3 4 图2 4i f r a - g m d h 算法学习训练样本能力示意图3 5 图2 5g m d h 算法对新样本的预测能力示意图3 5 图2 6i f r a g m d h 算法对新样本的预测能力示意图3 6 图3 1 最小拟合方差4 0 表1 1g m d h 算法分类5 表1 2 神经网络与g m d h 多层建模算法的比较1 3 表1 3b p 神经网络与g m d h 多层建模算法的比较。1 4 表2 1 基本g m d h 和i f r a g m d h 预测太阳黑子活动数量的比较3 4 表2 2 1 1 中三种分类方法得到的分类结果及标准差j 3 7 表2 3g m d h 与f r a g m d h 分类结果的详细比较3 7 表3 1f r i e d m a n l ，f r i e d m a n 2 ，m u l t i 样本描述o 5 2 表3 2 平均相对方差结果比较5 4 表3 3 ( 续表3 2 ) 平均相对方差结果比较5 4 表3 4 惩罚性划分与随机划分的平均相对方差结果比较5 5 表3 5 ( 续表3 - 4 ) 惩罚性划分与随机划分的平均相对方差结果比较5 5 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复印 件和电子版，允许论文被查阅或借阅，可以将学位论文编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 捌专 叼6 扫 作者签名：鲎壁鱼 跏7 年月争日 中国科学技术大学硕士学位论文 第1 章绪论 随着信息技术的飞速发展，如今人类活动中每一个领域都充斥着大量的统计 观测数据，信息的增长呈现出超指数上升的趋势。虽然现代计算机技术与数据库 技术已可以支持存储并快速检索大规模的数据，但是无论在时间意义上还是空间 意义上，传统的数据分析手段还是难以应付，人们无法理解并有效地使用这些数 据。数据挖掘技术由此而生并致力于从数据中获得知识，一种好的数据挖掘方法 首先应该能够自动完成数据挖掘过程，以排除人们主观认识对建模结果的影响， 同时不应对用户在数学、统计学等方面知识有过高的要求【l 】。自组织数据挖掘【2 】 以数据分组处理技术为核心，在过程动态分析的基础上，利用启发式方法选择模 型结构，然后在模型结构的基础上估计模型的参数。这种方法降低了在数据挖掘 的建模过程中人为附加因素的影响，使产生的模型能够具有更强的泛化能力。本 章首先回顾数据挖掘的发展历程，接下来主要针对自组织数据挖掘的概念、发展 进行了综述，并给出该方法与常见的数据挖掘技术的比较与分析。最后提出了自 组织数据挖掘方法的研究趋势及不足并概述了本文的主要研究内容及章节安排。 1 1 数据挖掘概述 1 1 1 数据挖掘的背景 数据库中的知识发现( k d d ) 是指从数据库的数据中抽取出其中隐含的、新颖 的、有用的信息的非平凡过程【3 】。 数据挖掘( d a t am i n i n g ，简称d m ) 是k d d 的核心步骤，指的是用人们可以接 受的计算效率，找出数据源中的模式或模型。知识、规则或高层次信息等都可以 从包括关系数据库、数据仓库、交易数据库、空间数据库、时态数据库、时间序 列数据库、文本数据库、多媒体数据库、w o r l dw i d ew e b 数据等各种数据源中 挖掘。数据挖掘能从各种角度对它们进行分析和应用，从而为人们从事科研和经 济实践提供丰富的知识库。 国际上首次关于数据挖掘与知识发现的研讨会是于1 9 8 9 年6 月在美国底特 中国科学技术大学硕士学位论文 律召开的。1 9 9 5 年开始召开的第一届国际k d d 大会至今，己召开了数届国际 k d d 学术大会。从9 7 年开始，k d d 有了自己的专门杂志。此外，还有一些这 一主题的地区性国际大会，如亚太地区数据挖掘与知识发现国际大会( p a k d d ) 等。所有这些大会和研讨会都对该领域的兴起与蓬勃发展起了巨大的推动作用， 在世界上逐渐形成了k d d 的研究热点和高潮。 数据挖掘的概念最早于1 9 9 5 年在美国计算机年会( a c m ) 上被提出，数据挖 掘在这里被定义为：从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 1 1 2 数据挖掘过程及问题 数据挖掘是一个多阶段的处理过程，一般包括以下几个步骤，如图1 1 【4 】。 ( 1 ) 数据准备与选择：了解相关领域的情况，熟悉有关的背景知识；根据用户的 要求，选取一个数据集或一个数据采样的子集。 ( 2 ) 数据预处理：对选择产生的数据集进行再加工，检查数据的完整性与一致性， 除去数据中的噪声，对丢失的数据进行填补。 ( 3 ) 数据约简：对经过数据预处理的数据，根据知识发现的任务目标，寻求能表 示数据的有用特征，利用属性约简或变换的方法对其操作，以减少数据量。 ( 4 ) 确定数据挖掘的目标：根据用户的要求，确定要发现何种类型的知识，因为 对k d d 的不同要求会在具体的知识发现过程中采用不同的知识发现算法。 ( 5 ) 确定数据挖掘算法：根据所确定的任务，选择合适的知识发现算法，这包括 选择合适的模型和参数。 ( 6 ) 数据建模：运用特定的知识发现算法，从数据集中搜索用户需要的模式，如 分类规则、关联规则、回归模型或预测模型等。 ( 7 ) 模型解释：对所发现的模式进行解释 。 ( 8 ) 知识评价：将所发现的知识以用户能了解的方式呈现给用户。这期间也包含 对知识的一致性的检查，以确保所发现的知识不与已有的知识相冲突。 在以上过程中。在某几个阶段之间可以重复进行，也可以在整个流程中进行 循环，以确保所发现的知识准确可靠。 2 中国科学技术大学硕士学位论文 图1 1 数据挖掘过程 对于目前的大多数数据挖掘算法，它们要求用户参与其中的很多步骤，整个 数据挖掘过程是在用户的组织、安排和协调下进行的，这样的数据挖掘过程可以 归纳为“他组织数据挖掘” 5 】。“他组织数据挖掘”对作为组织者的用户提出了 很高的要求：在数据的选择和预处理阶段要求用户具备深厚的行业知识和从业经 验；在数据挖掘算法的选择中要求用户具备丰富的关于数据挖掘工具、方法学和 模型的知识；在对所提取得到的模型模式评价阶段需要用户具备丰富的模型知 识和行业经验。用户的知识水平和行业经验在很大程度上影响了他组织数据挖掘 结果的好坏。因此，如何降低用户的主观行为在数据挖掘过程中的影响成为数据 挖掘研究领域中的一个重要内容。 1 2 自组织数据挖掘的基本思想g m d h 自组织数据挖掘起源于乌克兰控制专家a g i v a k l m e n k o 在上世纪六、七十年 代提出的数据分组处理方法( g r o u p m e t h o d o f d a t a h a n d l i n g ) 6 - 8 】，因此自组织数 据挖掘算法通常又被称为g m d h 算法。g m d h 基于启发式自组织方法，启发式 自组织方法在过程动态分析的基础上利用启发式方法选择模型结构，然后在模型 结构的基础上估计模型的参数。它不要求给出模型的具体形式，只要给出函数的 类型、生成函数的形式及选择准则就可以了，并且函数的选择也不是原则性的问 题。其中的自组织是一种过程，复杂动态系统的组织在这个过程中产生、繁殖和 中国科学技术大学硕士学位论文 完善。在利用自组织原则的方法中，寻求复杂系统动态模型的过程是通过模型结 构由简单到复杂而逐渐实现的，即在归纳判断方法的基础上进行的。 数据分组处理方法( g m d h ) 以启发式自组织原则的5 个阶段为前提【1 】： ( 1 ) 建模过程从确定模型所属类型开始，其类型有线性或非线性、静态或动态、 定常或时变等。给出模型类别，这是在对建模过程认识基础上实现的第一次启发 ( 2 ) 确定建模环境，即给出与建模过程有关的自变量( 因素) 组。建模环境很大 程度上依赖于我们对过程的认识。对过程运行条件的先期分析、因果关系及其形 式的解释，利用数理统计去揭示影响被研究过程最本质的交量等，这些工作对选 择建模环境具有实质性的作用 ( 3 ) 复杂化法则的确定。它在选择生成函数的基础上实现，由这些生成函数可以 产生新的竞争模型。通常，这些生成函数是比较简单的，它能使模型逐步复杂。 ( 4 ) 外准则估计。外准则是在竞争模型参数估计时没有使用过的数据信息上进行 计算的，它是g m d h 中使用的独特的启发式方式，g m d h 算法根据外准则值选 择候选模型以产生下一层更复杂的竞争模型 ( 5 ) 给出停止规则。模型自组织过程的最后一个步骤就是如何自发的停止模型复 杂度的增长，g m d h 使用外准则获得具有最优复杂度的模型，该模型在泛化能 力及对已知样本的记忆能力上达到最优 ”自然界中的生物的演变是从简单到复杂的，其间还受到优胜劣汰，适者生存 这一法则的约束，生物在进化过程中，不断受n ； i - 界环境的制约能够与之相互协 调，使得物种逐步地发生变化。在进行大批量育种过程中，为了得至新的一代， 每一次大批量淘汰的过程都应该筛选出具有某些较好特性、但还需要继续改进的 那些生物，并利用这些生物继续育种。经过一些阶段的选择以后，就可以培育出 理想的物种。数据分组处理方法( g m d h ) 再现了自然界生物发展的过程。在建模 的初始阶段存在一批简单的初始组织，建模过程中不断有复杂度更高的候选模型 产生，外准则在这时被用来选择出有竞争力的模型以继续模型的生长过程，而这 些有竞争力的模型积累了前面模型过去的经验，表现出遗传的特征。 由上我们可以把自组织数据挖掘方法的基本思想可以被归纳为：从对系统有 影响的因素样本出发，其样本数据被用来产生许多模型，并且根据某个( 些) 外 部准则，从模型集合中选出一个所谓的最优复杂度模型。【1 】 4 中国科学技术大学硕士学位论交 1 3 自组织数据挖掘算法综述 1 3 1 自组织数据挖掘算法分类 随着对自组织数据挖掘方法的深入研究，在此基础上产生了一系列基于 g m d h 的算法并在不同领域中得到了广泛的应用。按照是否需要估计模型中的 参数可将g m d h 算法分为参数g m d h 算法和非参数g m d h 算法。两类算法仍 可做如下的进一步划分，如表1 - 1 所示。 表1 1g m d h 算法分类 g m d h 算法 参数g m i ) h 算法( p a r a m e t r i c ) 非参数g m d h算法 ( n o n p a r a m e t r i c ) 组合算法( c o m b i n a t o r i a lc o m b i )客观聚类分析算法( o b j e c t i v e 多层算法( m u l t i l a y e r e di t e r a t i o n a lm i a )c o m p u t e rc l u s t e d z a t i o no c c ) 调和算法( h a r m o n i a l l相似体合成算法( a n a l o g u e s 客观系统分析( o b j e c t i v es y s t e ma n a l y s i sc o m p l e x i n ga c ) o s a ) 组合算法【9 1 组合算法是最早的一种g m d h 算法，该算法能够产生输出关于输入的线性 组合。假定x l , x 2 ，锄为系统的册个可测变量，为样本个数。首先对样本数据 进行分组：w = a u b ，a 为训练集合，b 为选择集合。a ，b 中的样本数一般是 相等的，输出为y ，算法流程如图1 - 2 所示： 第一步：建立所有自变量关于因变量的一次一项式 j ，= a 0 + a l x i ，f = 1 , 2 ，m ( 1 1 ) 在样本集合a 上通过最小二乘回归得到式( 1 - 1 ) 的系数向量值，将b 中样本代入 式( 1 2 ) m 计算： a r ( s ) = 吉( y ，一允( 丑) ) 2 ( 1 - 2 ) o b i = 1 中国科学技术大学硕士学位论文 在所得到的1 1 1 个一元一次回归式中选择a r 值最小的f 1 个进入下一轮的构造并 记下该层最小的a r 值记为a r l _ _ _ i 号模型尹 f _ _ 二 y i j _ | 恂一哟哕 m i n 2 ff i 一 。 k 1 一一一一1 = i 1yf 7 1 一”一”圳l 7 乒71 ， ：； 一 一 1im y 舢旷咖尚旧 y 1f i l 图1 2 组合算法建模示意图 第二步：建立第二层模型 y = a o + a l x f + a 2 x j ，f 局，j = 1 , 2 ，m ( 1 - 3 ) 使用训练样本a 求得模型对应的系数向量，再将b 样本代入式中计算a r 值。 选定其中f 2 个a r 值最小的模型进入下一层的构造并记下该层最小的a r 值a r 2 以后各步骤与前面步骤相同，即都是在前一层的所得的每一个较优的模型上 拼接一个新的变量以获得更复杂的模型。整个构造过程将在a r i 的值开始上升时 终止，即a 鼢a 艮1 ，则第f - 1 的具有最小a r 值的模型将被选择出来作为整个系 统的模型。组合算法所能够产生的仅仅是输出关于输入的一个线性模型，而通常 情况下所需建立的模型往往比较复杂，这大大限制了组合算法的可用范围。 6 中国科学技术大学硕士学位论文 多层算法1 1 0 l 多层算法是目前g m d h 算法中得到最广泛应用的一种，该算法与组合算法 一样都是在算法进行过程中产生复杂度逐渐增长的模型，而区别在于多层算法在 获得一批最优的中间模型后对这些模型进行两两拼接，以产生更复杂的模型。 令柏, x 2 , x m 为系统的扰个可测变量，为样本个数。首先对样本数据进行 分组：w = a u b ，a 为训练集合，b 为选择集合。a ，b 中的样本数一般是相等 的，输出为y ，算法流程如图1 3 所示： 输入层 第一层 第二层 输出层 图1 3 多层算法建模示意图 第一步：将输入变量两两组合产生初始模型 y t = + 4 l f + a 2 x ；+ a 3 x i + a 4 x j + 口5 x i x j ( 1 4 ) f ，j = l 2 ，m ；k = l 2 ，岛 在样本集合a 上通过最b - - - 乘回归得到式( 1 4 ) 的系数向量值，将b 中样本代入 式( 1 - 4 ) 中计算： 在所得到的m 个一元一次回归式中选择a r 值最小的f 1 个进入下一轮的构造并 记下该层最小的a r 值记为a r i 第二步：将第一层所得的f 1 个模型两两组合，生成第二层模型 7 中国科学技术大学硕士学位论文 u k = n 口+ n t ) 毒+ n 2 y 2 ，+ n 3 y i + a 4 y j + a s y i y j ( 1 - 5 ) f ，= 1 , 2 ，f l ；七= 1 , 2 ，c 夤 使用训练样本a 求得模型对应的系数向量，再将b 样本代入式中计算a r 值。 选定其中的f 2 个a r 值最小的模型进入下一层的构造并记下该层最小的a r 值 a r 2 以后各步骤与前面步骤相同，即都是用前一层的所得的较优的模型通过部分 多项式两两组合以获得更复杂的模型。整个构造过程将在a 的值开始上升时终 止，即a r p a 艮l ，则第扣1 层具有最小a r 值的模型将被选择出来作为整个系统 的模型。 多层算法能够根据样本自组织的建立起输出关于输入的具有极强非线性的 模型，在实际应用中，该算法是自组织数据挖掘领域内被使用最为普遍的一种算 法，在模式分类 1 1 】，时间序列建模【1 2 等方面都得到了广泛应用。 调和算法1 1 0 1 调和算法将自组织原理用于振动过程和周期性过程。该方法假设了被研究的 系统可以被一组调和项来进行描述，这些调和项分别具有离散的频率 w i , w 2 ，辨。 厂( f ) = a ks i n ( w t f ) + c o s ( w k t ) = o ( w k ，f ) ( 1 - 6 ) k = lk = l 其中a 和瞰是系数，且w l 坳f ：，0 w l ，f = 1 , 2 ，聊。该过程总的时间区间 长度为( 1 t 册。对于任一固定点i 和任意的p ，由式( 1 - 6 ) 可得。 f ( i + p ) + f ( i - p ) = 2 e c o s ( p w k ) o ( w k ，f ) ( 1 - 7 ) k = l 在式( 1 7 ) 中，令p 取0 ，, m - 1 ，将得到的m 个式子分别赋予权重po ，l l i ，i j * i 并相加得到： m-,，(f+p)+，(fp)】=2巾(m，f)【。+，cos(pw-i t ) 】 mm i p 。 “1 p l ( 1 - 8 ) = 2 o ( w k ，i ) c o s ( m w ) = 州+ 肌) + 厂( f 一肌) k t i 中国科学技术大学硕士学位论文 令 m - i b = 【( f + ，珂) + ，( f 一，”) 卜p l 厂o + p ) + 厂。一p ) 】( 1 - 9 ) p = o 根据训练样本可以通过最小二乘法估计得到u0 ，i li ，i l 纠的值。而当u0 ， i il ，n 。1 已知时，可以找到c o s 肌使式( 1 l o ) 成立 m - i 鳓+ 卢口c o s ( p w k ) = c o s ( m w k ) ( 1 - 1 0 ) p = l 并可继续转化为 d m ( c o sw ) “+ d 所_ l ( c o s w ) m - 1 + + d ic o s ( w ) + d o = 0 ( 1 - 1 1 ) 其中d f 可由1 t0 ，l il ”，p ，i 的组合得副，这样就可以得到w 的在【0 ，】之间 的m 个根。因此，对于一个时间序列，确定其调和趋势a t ) 的过程如下： 第一步：样本集划分为a 和b 两部分，根据式( 1 - 9 ) 在a 上估计得到po ， “i ，1 , 1 i 第二步：将0 ，pl ，1 2 。l 的估计值代入式( 1 一i o ) q ，唯一确定w 的k 个根 第三步：将w 的k 个根传送至组合算法中，在样本集a 上估计以和风的值。其 中式( 1 9 ) 可被用作评价标准选择哪些生成的模型可以进入下一轮构造，并确定构 造过程的结束。 客观系统分析【1 1 1 基本原理 o s a 的基本原理是通过某种演进机制和评价准则，最终确定一个方程系统 ( 方程组) 来描述被研究的系统。方程组中所含方程的结构和个数是基于整个模 型的一致性而得来的。所谓的一致性是指当加入新的数据时，方程组中方程的结 构和个数不会发生太大的变化，在两个不同的数据子样本上得到的方程组也具有 最小的偏差。在o s a 中，这种方程组的筛选过程是自动的。这也是该方法叫做 客观系统分析方法的原因。由于o s a 源于自组织数据挖掘理论，因而其演进机 制就是方程组复杂度的不断增加，而选用的基本评价准则是作为外准则的最小偏 差准则。 9 中国科学技术大学硕士学位论文 2 基本步骤 假设得到被研究系统的一组数据样本w 如下： 而lx 2 1 x t 2 x t x 2 n 其中x b x 2 ，, x m 为系统的册个可测变量，为样本个数，斯表示第i 个变量的第 j 个样本值。首先对样本数据进行分组：w = a u b ，其中a ，b 中的样本数相等， 记尹= l ，2 ，雕 ，俨 l 2 ，嬲其步骤如图1 4 所示。 首先根据最小偏差准则设定系统偏差为： c r y , , = 吉c r 卜c + + c r ； ( 1 1 2 ) c r , = 专喜学只御 小啪 其中0 ( 七) 表示在a 样本上估计得到的参数，# ( | j ) 表示在b 样本上估计得到的 模型。 第一步：建立单变量模型 x r t ) = a o + a l x i ( t 一1 ) ( 1 1 4 ) 分别在a ，b 样本上建立式( 1 1 4 ) 的模型( 考虑一步延迟) ，利用最小偏差准则选 定c r 。最小的f 1 个较优的模型，记其中最小偏差值的最小值为nl 第二步：建立两变量方程组模型 髅盛：q邪誉)+aw2xj(t)+aaxj(t一-x?(1-15)j(t b , x j ( t + b 3 x , ( t 1 1) = 6 b +一1 ) + 如砖( f )一) 、 分别在a ，b 样本上建立式( 1 1 5 ) 的模型( 考虑一步延迟) ，利用最小偏差准则选 定c r ，。最小的f 2 个较优的模型，记其中最小偏差值的最小值为i l2 第三步：建立三变量方程组模型 i t ( f ) = a o + a i x , ( t 一1 ) + 2 x ，( t ) + a 3 x j ( t 一1 ) + a 4 x , ( t ) + a s x k ( t 一1 ) x j ( t ) = b o + b j x j ( t o + b 2 一( f ) + 6 3 t ( f 1 ) + 6 4 以o ) + 以工i o 一1 ) ( 1 - 1 6 ) 【x t ( t ) = c o + c l x t ( t 1 ) + c 2 x i ( t ) + c 3 x l ( t 1 ) + c 4 x ( f ) + c 5 x j ( t 一1 ) i o k ；钿 中国科学技术大学硕士学位论文 分别在a ，b 样本上建立式( 1 1 6 ) f 1 0 模型( 考虑一步延迟) ，利用最小偏差准则选 定a k 。最小的f 3 个较优的模型，记其中最小偏差值的最小值为t l3 图1 - 4o s a 建模示意图 一直重复这个过程，直到最小偏差准则值的最小值r i f 开始上升时，即 t l p1 1 f - 1 时停止构造。这样，整个筛选过程确定了复杂系统的变量集以及他们的 线性结构( 也可以是非线性结构) 。 其他g m d h 算法简介 自g m d h 技术提出后一些建立在此技术基础上的新的算法也不断被提出， 并分别用于不同的领域中。如在多层算法及组合算法基础上，通过采用不同精度 的多种采样间隔形成多水平预测，以达到扩大可预测范围的g m d h 两水平算法 1 】；为了解决聚类问题中类别的最优个数和变量组成而将g m d h 理论中样本划 分的思想运用于其中，一部分产生类，另一部分确定类的最优数量及变量组成的 客观聚类分析 1 3 1 ；相似体合成算法( a c ) 【1 4 提一种对复杂对象预测、聚类和分 类的一种序列模式识别方法，使用自组织数据挖掘方法解决了其中相似模式个数 的选择以及相似模式组合时权系数的取值问题，进一步增强了a c 的可用性 1 5 1 。 中国科学技术大学硕士学位论文 1 3 2g m d h 多层算法的研究意义 数据挖掘的重要步骤之一就是在已有数据上面建立预测模型，一般来说，数 据挖掘技术的恰当选择要求建模者不仅具备丰富的关于数据挖掘工具、方法学和 模型的知识，同时还要具备在实际工作中的成功经验。人们的主观判断在这个过 程中至关重要 5 】，但这些条件往往限制了数据挖掘过程中数据建模的客观性。 在数据挖掘中，有一些可以近乎自动地从实验数据中生成数学模型的方法， 其中非常流行的如神经网络，遗传规划，以及统计学中常用的回归分析方法。自 组织数据挖掘算法由于其具有的自组织特性可以通过更少的先验信息或专家知 识，而仅仅通过使用样本生成数学模型。不同的自组织数据挖掘算法针对的应用 领域有所不伺，例如调和算法侧重于周期性过程的建模，客观系统分析和相似体 合成算法更多的被用于时间序列的建模中【1 】。基于g m d h 的组合算法和基于 g m d h 的多层算法是自组织数据挖掘方法中较为通用的两种算法，而组合算法 所能够产生的仅仅是输出关于输入的一个线性模型，而通常情况下所需建立的模 型往往比较复杂，这大大限制了组合算法的可用范围。g m d h 多层算法在应用 中可以根据样本自组织地生成模型，且生成的模型具有较强的非线性同时能够达 到记忆能力与泛化能力之间的最优平衡( 最优复杂度 2 】) ，因此得到了广泛的应 用。i v a k h n e n k o 在 1 6 】提出了主动神经元的概念，他指出相对于神经网络中神经 元建立过程的被动性来说，g m d h 多层算法生成的网络中的节点其产生的过程 具有更强的自主性。也正是因为i v a k h n e n k o 提出的这一概念使得g m d h 网络与 神经网络之间具有了一定的相似性 1 7 】，而这种相似性也促使更多的学者开始致 力于g m d h 多层网络的算法研究。 以下作者将分别给出自组织数据挖掘的典型算法g m d h 多层算法与以上几 种常用方法的比较，经过比较可以发现与其他几种常用的建模算法相比，g m d h 多层算法具有多方面的优势。 g m d h 多层算法v s 神经网络 人工神经网络1 1 8 是由大量并行分布式处理单元组成的简单处理单元。它模 仿人脑神经元结构及连接特征，通过调整连接强度而从经验知识进行学习的能 力。g m d h 多层算法与神经网络具有相似的结构，都能够建立关于样本集的黑 1 2 中国科学技术大学硕士学位论文 盒模型，下面通过表格给出两种建模方法的比较： 表1 - 2 神经网络与g m d h 多层建模算法的比较 b p 神经网络g m d h 多层建模算法 结构三层或多层结构，预先人结构预先不固定，通过演 为设定化方式逐渐生成 神经元之间的连接层间全连接层间部分连接 自组织性层次数和神经元数量均层次和神经元数量均在 事先给定，缺乏白组织性建模中依据外部准则演 化而得到，自组织性强 参数估计方法 误差反传调整参数，迭代回归分析估计参数，一次 过程费时性完成节点参数的估计， 速度快 样本使用全部作为训练样本调整一部分训练样本调整参 参数，容易过拟合数，另一部分训练样本用 于选优 计算适合于多处理器并行处适合于多处理器并行处 理，单机处理速度慢理，也适合于单处理器 模型的可解释性建立黑盒模型，但模型难建立黑盒模型，模型容易 于被理解被理解，且能够解释各变 量的对预测的重要程度 收敛性较难于收敛到全局最优j所得模型的记忆能力及 容易过拟合，与模型初始泛化能力达到最优平衡 状态有关且与模型初始状态无关 g m d h 多层算法v s 进化规划 进化规划( g e n e t i cp r o g r a m m i n g ) 1 9 是演化计算的一个分支，演化算法采用随 机搜索机制找出问题最优解。进化规划的基本思想是将演化算法延伸到计算机程 序设计领域用以繁殖计算机程序的群体，并从中获得关于优化问题的最优解。在 进化规划的执行过程中，函数的结构被看作一个程序，建立函数预测模型的问题 中国科学技术大学硕士学位论文 就转化为一个最优程序设计的问题，把函数的自变量和运算符看作程序的输入， 把函数的因变量看作程序的输出，并把整个程序用一棵语法树来表示。以上这些 特征都是与g m d h 多层算法相类似，下面也通过表格给出进化规划与g m d h 多层算法的比较： 裹1 3 b p 神经网络与g m d h 多层建模算法的比较 进化规划g m d h 多层建模算法 结构结构预先不固定，在解空结构预先不固定，建模过 间完全随机搜