（计算机应用技术专业论文）模糊聚类研究及其在水文分区中的应用.pdf

模糊聚类研究及其在水文分区中的应用 摘要 聚类分析是数据挖掘中的一个分支，模糊聚类是聚类中的重要方法，已经 取得了丰富的成果，其中的模糊c 一均值( f c m ) 算法具有良好的性能和广泛的 应用价值。然而，f c m 算法对初始聚类中心的敏感问题影响了实际应用的质量 和效果。本文针对这一问题展开研究，并将研究成果应用于安徽省淮河流域水 文分区。 主要工作如下： ( 1 ) 研究分析了数据挖掘及模糊聚类的现状及存在问题，描述了模糊理论 中的相关方法。 ( 2 ) 研究了神经网络和模拟退火聚类算法。分别对基于模糊逻辑的神经元 网络聚类和使用c a u c h y 训练的模拟退火聚类算法进行了单独和混合实验，对 聚类过程中能量的变化、聚类有效性和聚类耗时等方面做出了分析和总结。 ( 3 ) 在研究分析f c m 模糊聚类算法的基础上，提出了模糊聚类算法n f c 。 该算法首先运用基于模糊逻辑的神经元网络和c a u c h y 训练的模拟退火聚类算 法求解初始聚类中心，然后运用f c m 进行聚类，解决了f c m 对初始聚类中心敏 感和局部极值的问题，在随机给出初始聚类中心的实验中有效率高达9 9 。 ( 4 ) 将所提出的n f c 算法应用于安徽省淮河流域的水文分区。对采集的 1 2 4 7 1 6 个原始水文数据，首先采用主成分分析法获得主成分属性，然后运用n f c 算法聚类。实验表明，与传统分区方法相比，有效地改善了时间性能，提高了 求解精度，为水文站网规划做出了有益的尝试。 关键词：模糊聚类f c mn f c主成分分析法 水文分区 r e s e a r c ha n d a p p l i c a t i o no ff u z z yc l u s t e r i n gi n h y d r o l o g yd i s t r i b u t i o n a b s t r a c t c l u s t e r i n ga n a l y s i si sab r a n c ho fd a t am i n g 。a n df u z z yc l u s t e ri sak i n do fc l u s t e r , m a n ya c h i e v e m e n t sh a v eb e e np r o p o s e d i nw h i c h , f u z z yc m e a n sc l u s t e r i n gh a sg o o d p e r f o r m a n c ea n dv a l u e h o w e v e r t h et r o u b l es e n s i t i v et ot h ei n i t i a lc l u s t e rc e n t e ra f f e c tt h e q u a l i t ya n dp e r f o r m a n c eo fi t sa p p l i c a t i o n i nt h i sd i s s e r t a t i o n , t h er e s e a r c ho nt h et r o u b l ei s d o n e ，t h ec o n t r i b u t i o na r ea sf o l l o w i n g ( 1 ) t h ep r o b l e m sa n dt h es t a t eo f d a t am i n i n ga n df u z z yc l u s t e r i n ga r eo v e r v i e w d ，a n d t h er e l a t e dc o n c e p t sa n dr e s e a r c ha r ei n t r o d u c e d ( 2 ) n e u r a ln e t w o r ka n ds i m u l a t e da n n e a l i n ga l g o r i t h ma r ed i s c u s s e d s e p a r a t ea n d m i x e de x p e r i m e n t so nn e u r a ln e t w o r kc l u s t e r i n ga r ea l s op e r f o r m e d ，b a s e do nf u z z yl o g i c a n ds i m u l a t e da n n e a l i n ga l g o r i t h m , u s i n gc a u c h y a v a i l a b i l i t y , n e c e s s a r yt i m ea n de n e r g y c h a n g eo f c l u s t e r i n ga r ea n a l y z e da n dc o n c l u d e d ( 3 ) an e wf u z z yc l u s t e r i n ga l g o r i t h mn f cb a s e do nf u z z yl o g i cn e u r a ln e t w o r ka n d s i m u l a t e da n n e a l i n ga l g o r i t h mi sp r o p o s e d ，w h i c hu s ef u z z yl o g i cn e u r a ln e t w o r ka n d c a n c h ys i m u l a t e da n n e a l i n ga l g o r i t h m 的f i n dt h ec l u s t e rc e n t e r , t h e nc l u s t e r i n gw i mf c m a l g o r i t h m e x p e r i m e n t ss h o wn f ci sn o ts e n s i t i v et oi n i t i a lr a n d o mc e n t e r , a n dh a sg o o d p e r f o r m a n c ew i t has u c c e s sr a t eo f9 9 7 6p e r c e n t ，a n da v o i d i n gt h ep r o b l e mo fl o c a l o p t i m i z a t i o n ( 4 ) n f ci sa p p l i e dt oh y d r o l o g yd i s t r i b u t i o no ft h eh u a i h er i v e ri na n h u ip r o v i n c e i n w h i c h ，t h em a i nf a c t o ra n a l y s i si su s e dt os e l e c tr e l e v a n ta t t r i b u t e ，a n dn f ci su s e dt o c l u s t e r i n g t h ee x p e r i m e n t so nc o l l e c t e d1 2 4 7 1 6r a wh y d r o l o g i cd a t a c o m p a r e dw i t h t r a d i t i o n a lm e t h o d s 。i ti m p r o v e st h et i m ep e r f o r m a n c e ，a c c u r a c ya n dr e s u l tr e f l e c t sp r e s e n t s t a t eo f h y d r o l o g yd i s t r i b u t i o no b j e c t i v e l y t h a ti st oh e l pt op l a nt h en e t w o r ko f h y d r o l o g y s i t ea n di sc o n v e n i e n tt ob ea p p l i e di nt h ef u t u r e k e yw o r d s ：f u z z yc l u s t e r i n g ，f u z z yc m e a n s ， n f c ， m a i nf a c t o r a n a l y s i s ， h y d r o l o g yd i s t r i b u t i o n n i 插图清单 图2 1 谱系示意图9 图2 2 集合的特征函数1 5 图2 3 点集映射1 5 图2 4 扩展原理1 6 图3 1b p 网络结构示意图- 2 3 图3 2b p 网络结构中的结点2 3 图3 3 模糊逻辑神经元网络结构2 7 图3 4 基于模糊逻辑的神经元网络聚类算法流程图2 9 图3 5 基于模糊逻辑的神经元网络聚类算法实验( 1 ) 2 9 图3 6 基于模糊逻辑的神经元网络聚类算法实验( 2 ) 3 0 图3 7 基于模糊逻辑的神经元网络聚类算法实验( 3 ) 3 0 图3 8 修改参数后仍不能避免局部极值3 2 图3 9s a 中局部最小与全局最小3 3 图3 1 0 模拟退火的有效聚类3 6 图3 1 1 模拟退火的无效聚类3 6 图4 1 原始数据4 l 图4 2 有效聚类比较4 3 图4 3 三种算法的耗时分析4 4 图4 4 能量分析4 4 图4 5 无效的模糊聚类4 7 图4 6 有效的模糊聚类( 1 ) 4 7 图4 7 有效的模糊聚类( 2 ) 4 7 图4 8 模糊聚类能量变化图4 8 图5 1n f c 模糊聚类在水文分区中的应用模型5 4 图5 2 水文因子样本点一一5 5 图5 3 打开原始水文数据5 6 图5 4 克里金插值5 6 图5 5 提取安徽省淮河流域样本点一5 6 图5 6 主成分分析5 7 图5 7n f c 算法对圭成分进行模糊聚类“, 5 9 图5 8 模糊聚类结果5 9 图5 9 以g 1 ，g 为纵横坐标绘制的主成分聚类结果6 0 图5 1 0 以经纬度为纵横坐标绘制的主成分聚类结果6 0 图5 1 l 模糊聚类后的水文分区6 l 表格清单 表4 1 神经元算法和局部混合算法实验结果4 3 表4 2 模拟退火算法实验分析4 4 表4 3 神经元算法耗时统计4 5 表4 4 能量分析表4 6 表4 5f c k t 算法有效性分析 4 8 表4 6n f c 算法的有效性分析 4 8 表5 1 特征值五以及特征向量屹成果表6 0 表5 2 前两位主成分成果表6 l v i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 也不包含为获得金肥王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 籼一签剩一瓤夕洲。日 学位论文版权使用授权书 本学位论文作者完全了解盒目l 王些盍堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒蟹王些太 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索。可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 致谢 值此论文完成之际，首先我要衷心感谢我的指导老师胡学钢教授! 从选题、 定题到论文的修改和完成，每一步都离不开胡老师的悉心教导。在论文的研究 过程中，他总是及时地给我指点迷津，督查进展，对于提出的问题总是耐心地 讲解和精心地指导。胡老师以高度负责的工作责任心和精湛的专业水平指导着 每一个学生，他严谨的治学精神、渊博的专业知识、脚踏实地的科学态度将对 我以后的工作、学习和生活产生深远的影响。师恩如海，永生不忘。 感谢计算机学院和研究生部的全体老师，感谢他们的指导、关心和帮助。 感谢安徽省水文局的领导和专家，感谢他们在论文研究过程中的帮助。 感谢安徽水利水电职业技术学院的张志红、何永太等各位老师，大家在一 起集思广益、共同研讨，这对我顺利完成论文有很大帮助! 感谢我的妻子多年来对我学习的支持和生活上的关心，她勤恳辛苦，料理 家务，照顾孩子，使我能够克服种种压力，勤奋学习，刻苦钻研。 最后，我要向所有关心、支持和帮助过我的老师、同学、同事、朋友和亲 人表示深厚的感谢! 作者：丁亚明 2 0 0 7 年4 月 1 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 ) ，以及相应的数据 挖掘( d a t am i n i n g ) 。 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识 别有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。也就 是在数据中挖掘出数据间重要的但容易被人工分析忽略的知识和信息，自动地 发现隐藏在数据间的模式，做出预测性分析。数据挖掘又称作数据库中的知识 发现。数据挖掘的概念有广义和狭义之分，但是无论从哪个角度来定义数据挖 掘，都应体现数据挖掘的3 个基本特性，即：潜在性、价值性与可理解性。潜 在性是指挖掘出来的知识是隐藏在数据中的，事先不知道的；价值性指数据挖 掘的结果是用户感兴趣的，有用的知识和模式；理解性是指挖掘的结果应该具 有可解释性，并可以被人们所接受和利用的知识。数据挖掘是一门新兴的交叉 学科，融合数据库技术、人工智能、机器学习、统计学、模糊数学、神经网络、 模式识别、知识库系统、高性能计算、数据可视化等多个领域的理论和技术。 社会需求是科学发展与创新的源动力。自2 0 世纪末提出来后，引起了许多 专家学者的关注，并迅速在多个行业得到广泛的应用。在银行业，数据挖掘主 要用于信用欺诈的建模和预测、风险评估、趋势分析、收益分析以及辅助直销 等活动。在金融市场，已经将神经网络用于股票价格预测、债券等级评估、商 品价格预测以及金融危机预测方面。在医疗领域，如n e u r o m e d i a l 系统公司采 用神经网络技术进行油性流质食物辅助诊断；v y s i s 采用神经网络技术为药品开 发进行蛋白质分析等。在市场营销、竞技运动、教育教学等各领域都得到了应 用。数据挖掘将成为一种利用信息资源的有效方法和途径，具有广阔的开发前 景和应用市场。 随着数据库技术的不断发展，数据库系统中不断引入新的数据模型，如扩 充关系模型、面向对象模型、对象关系模型和演绎模型等。根据数据的特性又 分为空间的、时间的、多媒体的等数据库。相应地数据挖掘涉及的数据种类日 益多样化，这些给数据挖掘提出了许多挑战性的课题。 数据挖掘未来研究方向之一是对各种非结构化数据的挖掘，如对文本和 w e b 数据、图形数据、视频图像数据等的挖掘；对各种复杂数据类型的挖掘方 法；新的研究还包括新应用的探索，算法的可伸缩性，基于约束的挖掘和可视 化方法，数据挖掘与数据仓库和数据库系统的集成，数据挖掘语言的标准化， 以及数据隐私保护和安全等等。 1 2 模糊聚类研究现状及存在问题 1 2 1 模糊聚类研究概述 数据挖掘具有自动预测趋势和行为、关联分析、聚类、概念描述和偏差检 测等五类功能，其中聚类是数据挖掘重要的研究方向之一。“物以类聚，人以群 分”，聚类是人们一项最基本的活动。所谓聚类，就是按照事物的某些属性，把 事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。传统的聚类分析 是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，具有“非此即 彼”的性质，所以这种划分的界限很分明。但实际上现实生活中大多数对象并 没有严格的属性，它们在形态和类属性方面存在着中介性，具有“亦此亦彼” 的性质，因此比较适合进行软化分。模糊聚类更能客观地反映现实世界，从而 成为聚类分析研究的主流。 聚类分析是数据分析中的一种重要技术，它的应用极为广泛。聚类应用包 括动植物分类、疾病分类、图像处理、模式识别、文本检索、客户关系管理( c r m ) 等。数据聚类分析广泛应用于模式识别、数据挖掘、市场分析、计算机视觉、 空间数据库技术等。国际和国内的学者都对聚类分析的研究非常重视，i e e e 的 汇刊中模式分析与机器智能( p a m i ) 、系统、人和控制( s m c ) 、模糊系统 ( f s ) 、神经网络( n n ) 、信号处理( s p ) 等杂志中几乎每期都有讨论聚类 分析问题的文章。聚类分析研究的意义和实用价值是不言而喻的。最早应用聚 类的领域之一是生物分类学，最近的应用包括从w e b 日志数据来检测使用模式 等。 聚类算法有很多种，需要根据应用所涉及的数据类型、聚类的目的以及具 体应用要求来选择合适的聚类算法。采用不同的聚类方法，对于相同的数据集 可能有不同的聚类结果。通常聚类算法的分类为：划分法、层次法、基于密度 的方法、基于网格的方法、模糊聚类的方法、基于模型的方法等。聚类算法有： 基于模糊等价矩阵的传递闭包法和布尔矩阵法、直接聚类法、最大树法、编网 法；模糊聚类算法有：k - 均值法、k 一中心点法、最小生成树、最近邻算法、 2 f c m 、基于遗传算法的聚类、基于神经网络的聚类等。 1 2 2 常用模糊聚类算法研究现状及存在问题 模糊c 一均值聚类算法( f u z z yc - m e a n s ，f c m ) 是目前应用较广的模糊聚类 方法之一。f c m 以及由f c m 聚类算法推得的其它聚类算法在语音识别、图像处 理及空间导航系统等领域被广泛采用，目前已经是模糊聚类的主要实用算法。 f c m 算法是一种逐步迭代的算法，每步迭代都沿着目标函数减小的方向进行。 由于f c h t 是基于目标函数的聚类过程，如果初始化不当，可能导致算法收敛于 局部极小而得不到全局最优解【2j 。因此，f c m 算法的缺点是对初始聚类中心敏 感，难以聚得全局最优。目前，对f c m 聚类算法的研究与改进，主要体现在三 个方面：初始聚类中心、聚类有效性函数和加权指数r 。 神经网络( n e u r a ln e t w o r k ，n n ) 也被称为人工神经网络，它是依据人脑 的工作方式建模的。人工神经网络模型是对生理学上的真实人脑神经网络的结 构和功能，以及若干基本特性的某种理论抽象、简化和模拟而构成的一种信息 处理系统。神经网络技术具有学习功能、分布式存贮和并行处理等特点。基于 模糊逻辑的神经元网络聚类算法【3 】，主要利用模糊逻辑算子来完成网络计算， 通过竞争学习得到网络输出，它可以提高运算速度且易于硬件实现，该算法大 大改善和提高了聚类有效性。但由于采用竞争学习算法，必然面临死点问题。 死点的出现是由于竞争学习算法中只有获胜的点才能进行学习，而在聚类过程 中，由于初始点选取的不合理，使某些初始点始终没有获胜的机会，因此无法 进行学习最终导致聚类无效。竞争学习的神经网络对初始化较敏感，除非权值 初始值置在聚类中心附近，否则有的节点会不响应变成死点。为了避免算法中的 死点问题，h e c h t 和v i e l s e n 提出了频率敏感性竞争学习算法( f s c c ) ，其主要是加入 频率参数r ，但仍不能避免陷入局部极值闯题。目前，神经网络算法有：k o h o n e n 聚类神经网络、f s c l 算法、r p c l 算法、b p 网络算法、基于模糊逻辑的神经元 网络聚类算法等。 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 1 4 1 由k i r k p a r t r i c k 于1 9 8 3 年 提出的一种随机优化算法，现在已经应用到各门学科中以解决非线性系统中的 优化闻题。其出发点是基于物理中固体物质的退火过程与一般组合优化问题的 相似性，模拟高温金属降温的热力学过程产生的。s a 通过模拟金属降温的热力 学过程，在搜索的过程中，不但接收邻域中使能量函数减少的解，而且以特定 概率接收使能量增加的解，从而避免搜索过程陷入局部最优解的情况。它是一 种著名的全局寻优算法，具有描述简单、应用灵活并极少受初始条件限制等优 点，但存在收敛慢、费机时的缺陷。目前，根据随机变量的空间搜索方式和退火 策略的不同，派生出不同的模拟退火算法，如b o l t z m a n 模拟退火( b s a ) 、快速模拟退 火( f s a ) 、极快速模拟再退火( v f s a ) 等。 1 3 模糊聚类在水文分区中应用现状及意义 水文分区是水文站网规划的基础。水文分区的目的在于从空间上揭示水文 特性的相似性与差异性、共性与个性，以便经济合理地布设水文站网，探索水 文规律，内插出无资料地区的各种水文特征值。水文站网的布设在某种意义上 则是以有限站点的观测来满足无限地点的需要。水文分区是规划区域代表站的 依据，将流域内水文因素变化一致的区域，划为一个水文分区。 水文分区一直是站网规划中比较关键的问题，得到国内外水文工作者的高 度关注。目前国内常用的水文分区方法【5 】主要有地理景观法、等值线图法、产 流特性分区法、暴雨洪水参数法、流域水文模型参数法、主成分聚类分析法等。 其中有些方法在分区时不得不依赖于分区者个人的经验判断，因此不同的水文 专家可能会得到不同的分区结果。而有些方法对资料的要求很高，并不适合资 料短缺的地区。所有这些分区方法大致可归为3 大类：( 1 ) 自然地理水文分区 法，如地理景观法；( 2 ) 从成因角度出发的成因分区方法，如流域水文模型参 数法；( 3 ) 以统计参数为指标进行水文分区的统计水文分区法。美国和加拿大， 在站网规划中都曾采用过统计水文分区法。统计水文分区法在站网规划中的作 用是确定每一地区的最小站数和所设站的大概位置，评定其他来源的资料对站 网的有效性，以及无资料时，对移用资料误差的评定。统计水文分区法包括多 元回归法、方格网法等。美国大多采用多元回归法，加拿大采用方格网法。 安徽省境内有三大流域，即长江、淮河、新安江流域。淮河自西向东流经 安徽省境，全长4 3 l k m ，我省境内流域面积6 6 9 万k m 2 ，占全省面积的4 8 0 ， 占整个淮河流域总面积的3 5 8 。全省现有水文站“7 个，其中基本水文站1 1 1 个。淮河流域水文站有5 1 个( 其中基本站4 7 个) ；长江流域水文站有5 9 个( 其 中基本站5 7 个) ；新安江流域水文站有7 个。其中大河控制站4 9 个，区域代表 站4 8 个，小河站1 8 个。我省现有水文站网存在的主要问题是：区域代表站部 分已达到设站目的，存在站网资源浪费，部分站因受水利工程影响，收集到的 水文资料在区域上代表性较差；小河站网尚未达到分区、分类、分级的完善配 套，尤其是沿江水网区和下垫面土层较薄的地区几乎为站网空白区；淮北地区 “三水转化”规律急待探索。 随着经济社会发展，水资源供需矛盾日益突出，现有水文站网明显不能满 足经济和社会发展对水文的要求。由于人类社会的影响，原布设的区域代表站、 小河站网代表功能削弱，不能满足水文资料广泛移用的要求。随着水资源日益 紧张，现有站网不能满足以行政区划为单元的区域水资源管理、水环境保护以 及水土保持工作的需求，等等。因此，应用性能良好的模糊聚类算法，进行水 文因子的聚类分析，科学合理地划分水文分区，有着十分重要的现实意义。 4 1 4 本文的研究内容与组织结构 本文认真研究和分析了数据挖掘的基本原理和一些常用的方法，充分详实 地研究了数据挖掘技术中的聚类问题。给出了聚类的相关概念、模糊聚类分析 的一般步骤、样本间相似性度量的各种方法，对当前数据挖掘中分层、划分等 聚类算法进行了分析和研究。对神经网络、模拟退火、f c m 模糊聚类进行了较 深入地研究，通过理论分析，指出它们各自的不足和优点。在此基础上提出改 进的模糊聚类算法n f c ，实验证明，n f c 算法在一定程度上解决了f c m 局部 极值问题，在大多数情况下可以获得有效的模糊聚类。最后采用主成分聚类分 区法和n f c 聚类算法对安徽省淮河流域进行水文分区，形成了安徽省淮河流域 水文分区图。在研究过程中，开发了n f c 模糊聚类水文分区的软件。本文的研 究，有着良好的的工程实用价值。全文共分六章。 第一章绪论。介绍了数据挖掘的研究现状；模糊聚类研究现状及存在问 题；模糊聚类在水文分区中应用现状及意义。 第二章相关的背景知识。首先介绍了聚类的相关概念、模糊聚类分析的 一般步骤，对聚类算法进行了分析和研究，然后对模糊聚类中所使用的模糊理 论进行了详细的介绍，描述了由特征函数到隶属函数的变化。 第三章神经网络模糊聚类。对神经网络聚类算法、模拟退火算法进行了 较深入地研究，通过理论分析，指出它们各自的不足和优点。对基于模糊逻辑 的神经元网络聚类和使用c a u c h y 训练的模拟退火聚类算法进行了实验，对聚 类过程中能量的变化，聚类有效性和聚类耗时等方面做出了分析和总结。 第四章改进的模糊聚类算法n f c 。本章主要介绍了模糊聚类的面向目标 函数的算法f c m ，研究分析了f c m 算法的优劣所在；给出了以基于模糊逻辑 的神经元网络的聚类算法和c a u c h y 训练的模拟退火算法为基础的f c m 算法一 n f c 。实验证明，改进的模糊聚类算法n f c 在一定程度上解决了f c m 算法局 部极值问题且有效性非常高。 第五章n f c 在水文分区中的应用。本章介绍了主成分聚类分析的原理与 方法步骤。用n f c 模糊聚类算法对安徽省淮河流域进行了水文分区。并用j a v a 实现该软件的开发。 第六章结论与展望。对已做的工作进行总结，并对下一步的工作进行了 展望。 第二章相关的背景知识 模糊聚类具有“亦此亦彼”的性质，更能客观地反映现实世界，从而成为 聚类分析研究的主流，模糊集理论的提出为这种软划分提供了有力的分析工具。 本章主要介绍聚类和相关的模糊理论。 2 1 聚类 2 1 1 聚类定义 聚类分析的基本思想是根据“物以类聚”的原理，对样本进行分类。 所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽 量小，类内相似性尽量大。 定义2 1 川给定由一些元组组成的数据库d = ，f 2 ，) 和整数值k ，则聚类问 题就是定义一个映射厂：d 寸 l 一，k ) ，其中第，个元组t 被映射到第_ ，个簇k ，中去。第 _ ，个簇t ，由所有被映射到该簇中的元组组成，即足，= l ( ) = k ，1 ，k ，e d 。 聚类的非形式化定义如下： 定义2 2聚类( c l u s t e r i n g ) 是一种在无导师的情况下根据对象间的相似 程度自动地将其分割为一组有意义的类的处理过程。聚类生成的组自然数簇 ( c l u s t e r ) ，簇是数据对象的集合，簇内部的任意两个对象之间具有较高的相似 度，而属于不同簇的两个对象之间具有较高的相异度。 对于上面聚类的定义有以下几点需要说明： ( 1 ) 无导师是指待分类对象没有预先给定的类标示，这是聚类与分类最大 区别。 ( 2 ) 对象在数据库中包括记录和属性，对记录的聚类称为q 型聚类，对 属性的聚类称为r 型聚类。 ( 3 ) 有意义是指聚类的结果应该反映原始数据的自然结构特征。一个好的 聚类要使类内( i n t r a c l u s t e r ) 相似性尽可能的大，类间( i n t e r c l u s t e r ) 相似性 尽可能的小，同时希望聚类能发现数据中一些隐含特征。 ( 4 ) 聚类结构的好坏取决于算法设计者对聚类的具体定义和表示，对象间 的相似度定义及聚类算法的具体实现。 2 1 2 样本间。相似性”度量0 6 i 当对n 个变量进行聚类时，用相似系数衡量变量间的关联程度。一般地，称，；i 为 6 变量t 和x ，间的相似系数。对一切满足： i ej s l lr i ；l _ 1 r j = 匕i 其中：0 i 。越接近于l ，说明变量和工，间的关系越密切。 确定= r ( ，x ，) 主要有相似系数法、距离法以及其他方法。具体用什么方法， 可据问题的性质选取某一公式计算气。 ( 1 ) 距离法 d ( ，j ，) 表示和x ，的距离，c 为适当选取的参数，它使得0 l 。 海明( h a m m i n g ) 距离法 勺= 1 - c d ( x , ，_ )其中d ( t ，一) = i l - - x 业l k = l 欧几里得( e u c l i d ) 距离法r o = 1 - c d ( x , ，_ ) 其中d ( t ，x j ) = 、i j 。一。1 2 ik = l 切比雪夫( c h e b y s h e v ) 距离法 o = l e d ( x , ，_ )其中d ( 薯，_ ) = 兰k 一靠l 绝对值倒数法 = 二 k 一哳 绝对值指数法 = e x p ( 一i - x , k 1 ) ( 2 ) 相似系数法 数量积法 ，1 ，| 【，2 上m 杰。 一 墉 p 夹角余弦法 02 当f 等， 当f 当f = j 当其d p m = m a x ( z i ：i x i k 溉j k ) 7 ktx 。 相关系数法 勺2 其中 k i i jx p i t = l i-=互= z ，历- - 2 。；：，x i k 一1 亡 x ，2 石毛 指数相似系数法 _ = 去喜e 卅三避芋， 其中轳i 1 善n ( 一珊而一x k = - ：e 。x m ( ，2 ，1 1 1l i l 注：在原始数据矩阵中，当不同的行来自不同的母体时，采用相关系数法；当不 同的列来自不同的母体时，采用指数相似系数法。 最大最小法 ( h x 一) ，= 专l 一 ( x 雎vx p ) 算术平均最小法 ( x 砖 x 一) 勺 睾窆( + )1 么、一睹j t7 几何平均最小法 ( 石庸 x ，t ) ，= 与 = m t = l ( 3 ) 主观评分法 请专家或有实际经验者直接对x ： i l x j 的相似程度评分，作为r , i 的值。例如， 请n 个专家组成专家组 p l ，段，岛 ，每一位专家仇( 女= 1 ，2 ，) 考虑对象和x ， 的相似程度，( ) ，设a ，( 女) 为p k 对自己所判断的自信程度( 有把握的程度) ， 则相似系数定义为： a 1 2 ( 七) 啦耻) ，= j l 二l 一 口“( 七) 相似系数究竟选择上述诸方法中的哪一种，需要根据问题的性质及使用方便来选 择。 2 1 3 模糊聚类分析的一般步骤 聚类分析算法一般经过特征提取、聚类策略和选取阈值三个步骤： ( 1 ) 特征提取 从样本中提取感兴趣的特征，使用这些特征进行聚类分析计算。特征的选 取将直接影响聚类的结果，合理的特征选取应当使得分类结果中同类样本距离 较小，异类样本距离较大。特征提取，一般包括从样本提取原始特征并对其进 行去量纲化和规格化，把这些数据映射到 0 ，1 区间。规格化后的数据一般是 订所矩阵，即n 个样本，每个样本含有肌维特征。这玎肼矩阵中的元素均是介 于 0 ，1 之间的数据。 x = 毛lx 1 2 x 2 1 而2 lx 2 。 屯。 。 其中0 x o s l 。 ( 2 ) 聚类策略 根据聚类分析的需要，合理地选取聚类算法进行聚类运算。目前聚类分析 算法有数千种之多，但是很多算法仍是不成熟，选取什么聚类分析算法将直接 影响聚类的结果和结果的有效性。 聚类策略实际上是根据样本特征将样本进行归类，经过规格化后的数据已 经没有其实际意义，聚类过程不需 要再有知识领域的专家参与。聚类 结果可以画成一个谱系图。 ( 3 ) 选取阈值 阈值的选取往往需要有领域专 家根据经验和领域知识，结合具体 情况和应用场所决定阈值的大小。 没有领域专家的参与，仅仅根据聚 类谱系图寻找阈值，或者求最小生 9 图2 1 谱系示意图 成树，往往不能得到满意的结果。领域专家结合领域知识可以进一步分析数据， 从而加深对样本的了解，加深对特征的认识。 2 1 4 数据挖掘中聚类算法研究 聚类算法有很多种，需要根据应用所涉及的数据类型、聚类的目的以及具 体应用要求来选择合适的聚类算法。采用不同的聚类方法，对于相同的数据集 可能有不同的聚类结果【7 1 。一般地，聚类算法可分为层次聚类和划分聚类两大 类，但根据应用对象的不同和处理过程的差异，聚类算法又有：基于密度的聚 类、基于网格的聚类、字符属性聚类、高维数据聚类等。这种分类并非完备正 交的，相互之间有交叉，每种分类又包括多种算法，有的算法同时包含了多种 类型算法的设计思想。以下将介绍划分法、层次法、基于密度的方法、基于网 格的方法和模糊聚类的方法等聚类算法。 ( 1 ) 基于层次的聚类1 8 j 所谓层次聚类是指产生一个嵌套的簇集。在层次体系中，每层都有一些分 开的簇。在最底层，每一个元组都组成一个单独的簇；在最高层，所有的元组 都属于同一个簇。在层次聚类中，不必输入簇的数目，可以用谱系图 ( d e n d r o g r a m ) 的树形数据结构表示层次聚类技术以及不同的簇集。其基本思 想是将模式样本按距离准则逐步聚类，直到满足分类要求为止，其聚类过程可 表示为一个二叉层次树，叶结点表示一个样本，中间结点表示将数据分割为两 个不同的类，或一个类由它的两个子类合并而成。层次的方法可以分为凝聚和 分裂方法。 凝聚聚类 指产生簇的过程是“自底向上”的。凝聚算法在初始时，每一个成员都组 成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇， 直到所有的成员组成一个簇为止。不同的层次凝聚算法在每一层上合并簇的方 式也不同。如单连接、全连接和平均连接是著名的凝聚技术。采用凝聚方法的 典型聚类算法有：b i r c h 、c u r e 、c h a m e l o no 分裂聚类 指产生簇的过程是“自顶向下”的。分裂聚类在初始时，每一个成员都属 于同一个簇，然后将上层的簇重复地分裂为两个下层簇，直到所有的成员组成 一个单独的簇，或者达到一个终止条件为止。其主要思想是将那些成员之间不 是非常紧密的簇进行分裂。通常情况下，凝聚方法优于分裂方法。d i a n a 是分 裂方法的代表。 层次聚类算法的优点在于算法能得到不同粒度上的多层次聚类结构，弱点 在于合并或分裂点的选取问题，因为一组对象一旦合并或分裂，就不能有u n d o 的操作；另外，层次聚类算法的时间复杂度为0 ( n 2 ) ，对于处理大数据量存在 i o 性能问题。 ( 2 ) 基于划分的聚类 对于一个给定的”个对象或元组的数据库，采用目标函数最小化的策略， 通过迭代把数据分成k 个划分块，每个划分块为一个簇，这就是划分方法。划 分方法满足两个条件：1 ) 每个分组至少包含一个对象；2 ) 每个对象必属于且 仅属于某一个分组1 9 l 。 基于划分的聚类算法，通常采用两阶段反复循环过程：1 ) 指定聚类。将样 本归到某一个聚类，使得它与这个聚类中心的距离比它与其他聚类中心的距离 要近；2 ) 修改聚类中心。当聚类中的对象发生增减时，需重新计算聚类中心， 当各个聚类中的样本不再发生变化时，计算终止。当采用聚类内的距离的平方 和作为评价函数时，聚类内的所有点向聚类中心汇集，因此采用基于距离的划 分评价函数方法得到时聚类是球形的。 聚类算法分为三类：概率模型算法、目标函数算法和模糊目标函数算法。 概率模型算法 将类看成参数未知的模型，将数据看成从多概率分布混合模型中抽取的样 本。分布模型中每个单峰值周围区域内的点属于一个类。该类型算法中比较有 代表性的是期望最大化e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法【1 0 s n o b 算法。 目标函数法 通过优化目标函数( 类间距离、类内距离或者其它表达式) 进行聚类，运算 复杂度是0 ( ) ( n 为样本总数，下同) 。目标函数算法又分两类：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 d o i d s 算法是p a m ( p a r t i t i o n i n ga r o u n d m e d o i d s ) 算法和c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n s ) 算法j 。 k - m e a n s 算法是应用最为广泛的聚类算法i i n 。该算法以类中各样本的加权 均值( 称为质心) 代表该类，只用于数字属性数据的聚类，抗干扰性较差。通 常以各样本与其质心欧几里德距离总和作为目标函数，也可将目标函数修改为 各类中任意两点间欧几里德距离总和，这样既考虑了类的分散度也考虑了类的 紧致度。如果将目标函数看成分布归一化混合模型的似然率对数，k - m e a n s 算 法就可以看成概率模型算法的推广。目前对该算法的研究非常深入，提出了很 多改进算法：改变预置质心的方式j 3 j 、采用遗传算法、模拟退火算法f i 5 j 都能 得到更好的优化效果。引入调和均值的概念将样本在类之间进行软分配，通过 调整权值反映各样本与各质心的关系，大大改善了性能。x - m e a n s 算法l l 州不仅 能减少运算复杂度，还能同时进行最佳类数目估计。 模糊目标函数算法 为了弥补目标函数法硬划分所带来的诸多缺陷而引入了软划分的概念，也 就是样本按照一定的概率归属于某类，而不是像目标函数法那样硬性分配。模 糊c 一均值( f c m ) 算法是其中最重要且应用最广泛的算法【1 7 2 0 ，但该算法并没有 完全克服其易陷入局部极小值和对初始化敏感的缺点。 基于划分的聚类算法一般要求所有的数据都装入内存，限制了它们在大规 模数据上的应用；需要预置聚类的类别数，但实际应用中聚类数是未知的；划 分算法只使用某一固定的原则来决定聚类，这就使得当聚类的形状不规则或大 小差别很大时，聚类结果不能令人满意。划分的聚类适用于类数固定，偏好球 形的聚类。主要算法有：k 一均值法、k 一中心点法( p a m ) 、最小生成树、最近邻 算法、f c m 、基于遗传算法的聚类、基于神经网络的聚类等。 ( 3 ) 基于密度的聚类方法 基于密度的方法与其他方法的一个根本区别是：它不是基于各种各样距离 的，而是基于密度的。将类看成稠密连接的样本，且随着密度的变化可以向任 意方向延伸，这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。 这个方法的思想就是：只要一个区域中的点的密度大于某个阈值，就把它加到 与之相近的聚类中。基于密度的方法有可能不够精确，但该方法对于噪声数据 和孤立点不敏感，可以发现任意形状的聚类。 d b s c a n ( d e n s i t yb a s e ds p a t i a lc l u s t e r i n go fa p p l i c a t i o nw i t hn o i s e ) 算法【2 1 1 是该类算法的代表，它不受数据属性、维数或数据形状的限制，且不受 数据排序的影响，计算复杂度为o ( n ( 1 0 9 n ) ) 。该算法有两种推广：g d b s c a n 算 法1 2 2 】将对空间点的处理推广为对空间多边形的处理；o p t i c s ( o r d e r i n gp o i n t s t oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 算法口3 j 对数据不同部分采用不同的 参数，将数据进行递增排序便于迭代处理。这些算法都考虑了样本空间的局部 密度，需要预置参数。d b c l a s d (