（控制理论与控制工程专业论文）数据挖掘的模糊系统实现.pdf

摘要 的实验也证明了这两种输入选择方法的有效性。 本文对许多著名数据挖掘问题进行了较全面的分析，如m p g 预测问题， b o xj e n i k i n 煤气炉问题，波士顿住房问题，得到了许多形象、生动、有趣的 结沦。 杨灿 于浙江人学 2 0 0 5 年1 1 月 引言 本课题的研究背景 引言 “我们淹没在信息的海洋里，却因缺乏知识而饥渴万分。” 一r o u t h e r f o r dd r o g e r 随着信息时代和计算机时代的到来，对我们人类而言，数据与信息的获得 都更加方便和快捷。但是，数据处理的问题却因大量的、复杂的数据而变得更 加棘手。这些大量的数据能告诉我们什么呢? 这就是“数据挖掘”的目标。我 们要从错综复杂的数据中去发现某种重要的模式、某些重要的趋势，真平地去 理解数据的内涵，这就是从数据中获耿知识。 因此，我们需要一种理论，能系统地描述人类知识并将其同其它信息一起 嵌入到实际系统中去。模糊系统正是这样的一个理想的系统。一般地讲，一个 好的工程理论应该能够有效地利用得到的信息。对于大多数实际系统来说，有 两个重要的信息来源：一个是用自然语言描述系统性能的专家；另一个是传感 器提供的测量数据和根据自然法则推导出来的数学模型。因此，一项重要的任 务就是怎样将这两类信息整合到系统设计巾去。实现这种整合的关键在于怎样 将人类知识整合到同传感器测量结果及数学模型类似的“框架”中。基于规则 的模糊系统允许以人类语言的形式来表述各种信息，因此使模型极易被人理 解。模糊集合在真值变量与语言变量问起到了极其重要的作用。从数学的角度 讲，模糊系统是一个万能逼近器，可以任意精度地逼近任意连续函数。正如王 立新教授( w a n g ，19 9 7 ) 所指出的： “模糊系统理论有以下特点： 强调充分利用各种所能获得的信息，包括数据信息，模型信息，语言信 息等。 将各种信息融为一体，在一个统一的数学框架下进行研究。 强调实用性与理论完备性相结合，以实用性为先导。 应用对象不限于某个邻域，而广泛适用于工程、经济、金融、管理、社 会等各个邻域。” 引言 但是，这并不意味着模糊系统己经完美无缺。现有的模糊系统依然存在着 一些问题，我们把这些问题归为两个大类： 1 现有的许多模糊建模方法仅仅是从函数逼近这个角度来研究，即如何改 进函数逼近精度以及建模的速度。这只是根据模糊系统万能逼近的性质来进行 模糊建模，如何更加充分地利用各种信息尤其是来自于数据的信息呢? 这就是 数据挖掘提出的新要求! 模糊系统因为它的规则库而倍受人们的关注与青睐，这是因为规则库能够 向人们提供所研究问题的信息，这是其它建模方法所无法比拟的。然而，现有 的模糊建模方法还没有能很好地考虑这一点，而仅仅是从函数逼近这个角度来 进行研究，还没有真证充分发挥模糊系统的优越性。 以函数逼近为目标的众多方法中，j a n g ( 1 9 9 3 ) 的a n f i s 是最为出色的。据 我们了解，到目前为止尚未有方法从逼近速度和精度两个方面同时超过 a n f i s 。a n f l s ( 图1 ) 的参数辨识采取了混合辨识算法，隶属度函数部分的 非线性参数采用最速下降法，结论部分的线性参数用最小_ 二乘法，因此a n f i s 具有十分快速和高精度的逼近能力。但是由于a n f i s 只从函数逼近角度考虑， 所得到的模糊规则较难以解释；更令人焦虑的是，a n f i s 擅长于对数据内插值 而不善于外推( 这点在本文的第四章中有实例) 。这些缺点对于数据挖掘而言 是致命的。 y 图1 a n f i s 的结构图 z w a n g ( 1 9 9 4 ) 的最近邻聚类法和c h i u ( 1 9 9 4 ) 掣j 减法聚类法是两种非常快速的 建模方法( 速度比a n f i s 更快，但精度稍差) 。这两种方法的最人不足是无法 引言 提供特别有意义的规则库，因而模糊系统独特的优势还是没能发挥出来。还有 的方法，如w a n g ( 1 9 9 4 ) 的正交最小二乘法，t a k a g i 和s u g e n o ( 1 9 8 5 ) 的连续划分 法，b r o w n 和h a r r i s ( 1 9 9 4 ) 的样条构造法等等，都存在这样的问题，详见综述 文章g u i l l a u m e ( 2 0 0 1 ) 。 构建高精度、可解释的模糊系统是我们的建模目标，从而能更加充分地提 取数据信息。 2 面对高维数据，现有的模糊系统几乎都面i 临着维教灾难的问题：模糊规 则的指数增长；大量参数需要拟合而却只有十分稀疏的数据散落在高维空间。 问题的复杂度随涉及变量数目的增加而指数上升是一个常见现象，这不为 模糊系统所独有。b e l l m a n ( 1 9 6 1 ) 称这种现象为“维数灾难”，h a s t i e ( 2 0 0 1 ) 也详 细地描述过这种现象。模糊系统在处理高维问题时主要面对着两方面的问题： 一是模糊规则随维数的升高而指数增长，具体地讲，假设有以个输入变量，每 个输入变量定义m 个模糊集合，则模糊系统的规则数为m ”。当n 值较大时， 珊”将是一个巨大的数，在实际中，有五个输入变量并不鲜见，当n = 5 ，m = 3 ( 通 常每个变量需要定义3 个模糊集合) 时，m = 2 4 3 ；如果m = 5 ，这比m = 3 更接 近实际，则m = 3 1 2 0 。在一个模糊系统中要采用数千条规则是不现实的，所以 模糊系统应用所面临的一个严峻的考验就是如何处理这一规则爆炸的问题。 在高维空间中出现了规则爆炸问题，如果仅仅是规则数量大因而增加了计 算量，降低了模糊系统的效率还勉强可以忍受，毕竟计算机的计算速度是惊人 的。事实上，问题的本质是如何在高维空间中去生成规则! 这个问题的难度在 于高维空间中数据的稀疏性( 见下页图示) 。对于中等复杂程度的维问题， 通常需要1 0 个数据：对于二维问题，通常需要l o o 个数据点。如果对于二维问题， 仅有1 0 个数据点，那么在这个二维空间罩，数据将是非常稀疏的。在如此稀疏 的数据空问，如何产生能够覆盖全论域空间的规则库是一个极具挑战性的问 题。 因此，目前有两个方向的研究可以解决模糊系统的“维数灾难”： 第一，选择最重要的输入变量进行建模。 笫二，改造现有的模糊系统使之适应高维问题。 引言 图2 随维数增加的“数据稀疏性” 可以看出，第_ 种方案是一种最根本的解决方案，其难度要大于第一种方 案。解决高维问题的最著名的方法有投影追随( f r i e d m a n ，1 9 8 1 ；h a s t i e ，2 0 0 1 ) 等。 神经网络的功能就很像投影追随，因此在面临高维问题的时候，神经网络依然 能运用自如。但神经刚络在数据挖掘上的致命弱点就是，它很难提供让我们容 易理解的知识。模糊系统的改造应该使之也具有这种投影追随的功能。这方面 的研究还很少，可以参见w a n g ( 2 0 0 1 ) 。然而，第一种解决方案，即输入选择， 也不失为一种重要的手段。 引言 本文的主要工作及其结论 在国家自然科学基金项目( n o 6 0 5 7 4 0 7 9 ) 和浙江省自然科学基金项目 ( n o 6 0 1 1 1 2 ) 的支持下，针对前面提到的两个大类的问题，我们提出了自己比较 系统的模糊建模方法。 1 我们处理规则爆炸的基本思想来源于聚类。所谓“人以群分，物以类聚”， 相似的数据被划分为一类，然后对每一类仅用一条规则进行描述。这样规则数 将不会随维数的增长而指数增长，而是与数据本身的特征联系起来。 2 为了获得更为有效的论域划分，我们研究了现有的各种聚类方法，比较 了它们各自的优缺点( 见第二章) ，并最终提出了两种基于m c v 聚类的模糊建 模新方法( 第三章) 。我们详细地讨论了两种方法获取的隶属度函数的特点， 以及参数估计方面的性质，并把两种方法与其它经典方法进行了大量的比较。 从数据挖掘这个角度看，我们的方法不仅具有很好的预测能力，还提供了更简 洁的规则库，为分析问题的本质和发现数据中隐含的知识提供了更好的工具。 我们通过聚类方法，不仅解决了规则的爆炸问题，也同时注意到了规则的 含义，即从规则中提取潜藏在数据中的知识，因而起到了两方面的效果。但是 对于高维问题中的数据稀疏性，到此为止依然还没有克服。于是我们进一步提 出了高维问题的解决思路。 3 如何处理高维问题? 输入选择应该是关键的第一步。它不仅起到了降维 的作用，还能增加模型可解释性并减少计算量。 输入选择的问题吸引了许多学者的注意，但是绝大多数的方法都是基于模 型的，这些方法均需要建立一个模型，然后通过各种评估的方法来选择输入。 这不是一个十分令人信服的好方法，因为从哲学的角度讲，某个输入的重要性 不会随着模型结构的不同而发生变化，这就是人们熟悉的“数据的内敛性”。 因此，提出一种不基于模型的方法是非常重要的。 我们在本文的第四章中提出了两种基于常识的输入选择方法，一种是基于 灵敏度分析的输入选择( 4 2 节) ，另一种是基于数据一致性的输入选择( 4 3 节) 。这两种方法的出发点看似完全不同的概念，其实是等价的，我们在文章 中的分析( 4 3 1 小节) 表明了这两种方法本质上的联系。大量的实验也证明 了两种输入选择方法的有效性，然而我个人更偏爱基于数据。致性的输入选择 引言 方法，因为它的计算更加高效快捷。 我们相信，随着以后研究的不断深入，这项有意义的工作将不仅仅会发现 新的事实或者技术的进步，而且还会改变我们推理的方式。 引言 三、本文组织结构 本文一共分为五章： 黼i 模糊规则- 了 数据挖掘_ 第一章模糊系统：介绍了模糊系统的基本概念，为第三章的模糊建模提供 了基本概念。 第二章聚类算法评述：不仅分析了各种聚类算法数学概念，还给出了大量 的实例演示，从模糊建模的角度来比较各种聚类算法，进一步为第 三章的分析作准备。 第三章基于最小体积聚类的模糊建模：本章是本文的重点之一，在这章罩 我们提出了两种模糊建模的方法，并且通过大量实例与经典的建模 方法进行了比较。 引言 第四章输入选择问题：本章也是本文的重点之一，在这一章里我们提出了 两种输入选择方法，并与经典的建模方法进行了比较，我们的方法 显出了较大的优势。 第五章结语：本章是对本文主要内容的进一步总结，也写下了自己的一些 感悟和体会。 我们的工作主要集中在第三、四章，第二章中对各种算法的评述也是我们工 作的重要组成部分。 为了方便阅读，我们在每章前都给出了摘要，更加明确各章内容以及它们之 间的联系。在每章的最后有每章的小结，包括了本章工作的总结和最重要的参 考文献。 第一章模糊系统 第一章模糊系统 本章介绍了模糊系统的基本概念，为本文的第三章的模糊建模提供妊要的 理论基础1 1 节介绍了模糊集合，模糊集合的运算( 模糊补，模糊并和模糊 交) ：模糊i f t h e n 规则和模糊推理是模糊系统的本质所在，1 2 节和1 3 节对 这些概念作了较详细的介绍；1 4 节介绍了模糊器和解模糊器的思想；两种最 常用的模糊系统：m a d a m n i 模糊系统和t s k 模糊系统，在1 5 节里介绍。值得 一提的是，对模糊规则含义的理解还会在第四章输入选择时用到。 1 1 模糊集合与模糊逻辑 1 1 1 模糊集合 设u 为论域或全集，它是具有某种特定性质或用途的元素的全体。回顾一 下论域【，中经典集合爿的概念，集合爿可以定义为集合中元素的穷举( 列举 法) ，或描述为集合中元素所具有的性质( 描述法) 。列举法仅用于有限集，描 述法比较常用。在描述法中，集合a 可以表示为 爿 x u lx 满足某些条件) 还有第三种定义集合爿的方法一一隶属度法，该方法引入了集合爿的0 一l 隶属度函数，用队( x ) 来表示，它满足 “加k ： ， 集合爿等价于其隶属度函数胁0 ) ，从这个意义上讲，知道m ( x ) 和知道一是 一样的。 模糊集合的定义：论域u 上的模糊集合是用隶属度函数m0 ) 来表征的， 肌的取值范围是 o ，1 。 因此，模糊集合是经典集合的一种推广，它允许隶属度函数在区间【o ，l 】内 任意取值。由定义看出，模糊集合一点都不模糊，它只是一个带有连续隶属度 函数的集合。 第一章模糊系统 “ 蔓 0 ( a ) c r i s ps e tf o2 04 06 08 0 1 0 0 图1 1 隶属度函数 隶属度函数还有很多种形式，如三角，梯形，高斯，钟形等等如图1 2 。 ( a ) t r i a n g u l a rm f o2 04 06 08 01 0 0 ( b ) t r a p e z o i d a lm f 1 0 5 0 图1 2 隶属度函数 模糊集合描述的现象的特征通常是模糊的，如“接近0 的数”就是一个不 精确的描述。因此，可以用不同的隶属度函数来描述同一对象。但隶属度函数 本身就不是模糊的一一它们是精确的数学函数，一旦隶属度函数表征了模糊的 性质，则一切都不再模糊了。一种常见的对模糊集合理论的误解是，认为模糊 集合理论试图使世界模糊化，但实际恰恰相反，模糊集合是消除实际的模糊。 佩盏苎口工业皿芒。至 协p1邑jo旦c宕jeqeo乏忻。量。垦c世mdem王o口雹。旦c贮ociem至 ， o ， ：宝 。 协口巴。璺l笆。qeo苫o量o dic毫imdem苫mp副。皂lisjaqem至 第一章模糊系统 紧跟着这一结论的是另一个重要问题：如何确定隶属度函数? 隶属度函数 有各种各样的选择，如何从中选择呢? 从概念上讲，有两种确定隶属度函数的 方法。第一种方法是利用人类专家的知识，通常这种方法仅能给出一个粗略的 公式，还需要微调：第二种方法就是从数据中来确定隶属度函数。具体地讲， 首先指定隶属度函数类型，然后根据数据对隶属度参数进行微调。本文将主要 阐述第二种方法。 1 1 2 模糊逻辑 模糊系统是基于模糊规则的系统。模糊规则总是表达为逻辑蕴含的形式 ( i f t h e n ) 。命题逻辑与集合理论有如表1 1 的一些重要的等价形式： 表1 1 命题逻辑与集合理论的一些重要等价形式 集合逻辑代数 隶属关系真假值 成员( 属于)真( t ) 1 非成员( 不属于)假( f ) o 交与( a n d ，v )乘积 并或( o r ， ) 和 补非( )补 可用一种简单的方式来表达这种等价关系：xea 以命题的形式表达就是 “x 是a ”。而模糊关系与经典关系的不同在于隶属度脚( 砷。 1 1 2 1 模糊集合的运算 模糊集合运算是对经典集合运算的扩展，其扩展原则是只要当模糊集合退 化为经典集合时依然保持经典集合的运算性质。这罩主要介绍运用最广泛的模 糊集合运算。 模糊交( t 算子) ： ( 1 2 ) 第一章模糊系统 极小( m i n m i m u m ) ：。0 ，= m i n ( a , b ) 代数积( p r o d u c o ：丁如( 口，b ) = a b ， 有界积( b o u n d e dp r o d u c t ) ：p ( 口，b ) 2m a x ( 0 ，a + b 一1 ) 强积( d i r e c t e d p r o d u c t ) ：t d p ( a ，b ) = 0 ( 如果a ，b 都小于1 ) 否则曲。 当a 和b 在0 和1 之间变化时，可以绘制以a 与b 为函数的交算子的曲面， 如图1 3 的第一行。图1 3 的第二行给出了当a = t r a p e z o i d ( x ；3 ，8 ，1 2 ，1 7 ) 和b = t r a p e z o i d ( y ；3 ，8 ，1 2 ，1 7 ) 时，这四个算子的相应曲面图。 与模糊交类似， 模糊并( s 算子) ： ( 1 3 ) 极大( m a x i m u m ) ：s ( a ，b ) = m a x ( a ，b ) 代数和( p r o d u c 0 ：剐“，6 ) = + b a b ， 有界积( b o u n d e dp r o d u c t ) ：取m6 ) = m i n ( 1 ，a b ) 强和( d i r e c t e ds u m ) ：联，b ) = 1 ( 如果口，b 都大于0 ) 否则a + b 。 当a 和b 在0 和l 之间变化时，可以绘制以口与b 为函数的交算子的曲面， 如图1 4 的第一行。图1 4 的第二行给出了当a = t r a p e z o i d ( x ；3 ，8 ，1 2 ，1 7 ) 和b = t r a p e z o i d ( y ；3 ，8 ，1 2 ，1 7 ) b 寸，这四个算子的相应曲面图。 t a ) m i n( b ) a l g e b r a i cp r o o u c t ( c ) b o u n d e dp r o d u e _ 【( d ) d 锵t i cp r o d u c t y 1 0 5 o 2 0 1 图1 3 模糊交算子 n蔺。 夏矿妞们m斌蠲仲m 蓝 驻k溢喵溢 圆 第一章模糊系统 ( a ) m a x( b ) a l g e b r a i cs u m( c ) b o u n d e ds u m( d ) d r a s t i cs u m 模糊补： 百= l g s u g e n o 朴味加高 y a g e r ：c 。( 口) = ( 1 一口。) ”。 图1 4 模糊并算子 0 x = a 05 1 2i f t h e n 规则 1 2 1 语言变量 z 图i ，5 模糊补算子 定义：如果一个变量能够取普通语言中的词语为值，则称该变量为语言变 量。这里，词语由定义在论域上的模糊集合束描述，变量也是在论域上定义的。 8 6 4 2 o 0 o 0 0 第一章模糊系统 为什么语言变量的概念重要呢? 这是因为，语言变量是人类专家知识表达 的最基本元素，当用传感器测量某一个变量时，传感器会给出一个数值，而当 征求专家意见时，专家会给出语言。例如，当使用雷达枪来测量汽车速度时， 雷达枪会给出诸如3 9 m p h ，4 2 m p h 等数值，而当让某人告诉我们汽车的速度时， 他通常会说“它开得慢”、“它开得快”。因此，引入语言变量的概念就是使自 然语言的模糊描述形成精确的数学描述，这是人类知识系统有效嵌入工程系统 的第一步。 1 2 2 模糊规则库 模糊规则库是由模糊i 卜t h e n 规则集合组成： r 7 ：如果工l 为a 7 l 且且x n 为爿0 ，则y 为； ( 1 4 ) 其中，a 。和分别为u i c r 和m 皿上的模糊集合，x = 口l , x 2 ， ) 7 u 和y e v 分别是模糊系统的输入和输出变量。形如( 1 4 ) 式的规则叫做标准模糊规则， 因为它包括了许多其它类型的模糊规则和模糊命题： ( a ) “不完整规则” 如果x l 为a 。l 且且h 为爿f m ，则y 为：其中m o ，v i ( 2 1 3 ) 后面我们会看到，也正是由于这个不得已的约束，g k 算法通常只能对每个类 具有大致相等的体积的情况下，有很好的性能。如果当各个聚类的体积相差很 多时，g k 算法不能有特别理想的分类效果。 下面总结一下g k 算法的具体计算方法