层次聚类算法应用

1、精选优质文档-倾情为你奉上 安 徽 三 联 学 院 题目：层次聚类算法应用 姓 名 张 翔 专 业 计算机科学与技术 班 级 计一系本科2班 指导教师 张 林 完成日期： 2011年 11 月 16 日摘 要专心-专注-专业本文围绕层次聚类分析算法展开研究首先根据样本间的相似性关系定义分类后类与类间的分离性，以及同一个类别内部的一致性，并进行计算，从而使得计算过程得到简化利用层次聚类算法实现分层聚类在基于电价区域划分的实际问题中，这里结合人类视觉感知理论，提出了获取最优聚类的条件，从而实现了最佳的分类本文的主要研究工作如下：第一章：说明了层次聚类分析的定义及研究方法，对层次聚类分析方法的有效性

2、做出了细致的研究，并提出了基于相似矩阵的有效性函数第二章：将层次聚类分析方法应用在电价区域的空间尺度划分问题中，进而实现了电价区域的划分关键词 层次聚类分析；有效性；空间尺度目 录2225666 2.3 基于尺度空间聚类的电价区域划分.8 2.4 本章小结.134第1章 层次聚类分析算法及其研究1.1 层次聚类分析算法层次聚类算法1，也称为树聚类算法，它的目标是对于具有个样本的集合，首先通过相似性函数计算样本间的相似性并构成相似性矩阵，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到的聚类序列这个序列有着二叉树的形式，即每个树的结点有两个分支，从而使得聚类结果构成样本集的系统树

3、图, 使得有或对所有的都成立从系统树图形成的方式来看，层次聚类算法包括2种形式：凝聚式算法和分裂式算法凝聚式算法是以“自底向上”的方式进行的首先将每个样本作为一个聚类，然后合并相似性最大的聚类为一个大的聚类，直到所有的聚类都被融合成一个大的聚类它以个聚类开始，以1个聚类结束，分裂式算法是以一种“自顶向下”的方式进行的一开始它将整个样本看做一个大的聚类，然后，在算法进行的过程中考察所有可能的分裂方法把整个聚类分成若干个小的聚类第1步分成2类，第2步分成3类，这样一直能够进行下去直到最后一步分成类在每一步中选择一个使得相异程度最小的分裂运用这种方法，可以得到一个相反结构的系统树图，它以1个聚类开始

4、，以个聚类结束与分裂式算法相比，由于凝聚式算法在计算上简单、快捷，而且得到相近的最终结果，所以绝大多数层次聚类方法都是凝聚式的，它们只是在聚类的相似性度量的定义上有所不同层次聚类算法是一个非常有用的聚类算法，它在迭代的过程中直到所有的数据都属于同一个簇才停止迭代，但是层次聚类也存在几个缺点，如聚类的时空复杂度4高、聚类的簇效率底、误差较大等1.2 层次聚类分析算法的有效性研究针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个聚类的有效性函数在人工和实际数据集上的实验都表明了该有

5、效性函数具有良好的性能层次聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛5虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题根据模糊集理论6，系统树结构的每一层是由阈值决定的因此，最优聚类结果的选取问题就是最优阈值的选取问题对于最优阈值的选取问题，使用统计量是研究者们比较认可的方法当然随着模糊数学研究的深入，近几年来也有新的解决方法，Nasibov和Ulutagay提出了一个对于噪声更为稳定的FJP(fuzzy joint points)算法该算法的基本思想是根据样本点

6、与样本点之间的距离计算模糊关系矩阵，对于某一，建立截集和等价类此时，这些等价类决定了模糊聚类的每个截集但并非对每个都计算截集，而是只计算影响聚类个数的对应的截集最终的截集是由取值区间上的最大值确定的FJP算法已被证明能成功检测团装数据集及流形状数据集，即使添加噪声点后FJP算法也能成功识别流形状数据集如何衡量一个聚类结果的好坏，以及如何确定最优聚类个数，这些都是聚类有效性问题关于模糊均值算法聚类有效性问题的研究也已经有了很丰硕的成果，从1974年开始研究者们提出了许多有效性函数这些有效性函数构建聚类有效性指标的定义应当是客观的通常情况下，刻画聚类有效性有2个标准：类内致密性和类间分离性统计量也

7、是从类内致密性和类间分离性2个方面考虑的对于层次聚类算法的有效性研究，很多研究者还试图从模糊数学理论着手范九伦和吴成茂对基于模糊集合定义的若干公式在聚类有效性方面的性质进行了讨论，并对分类性能进行实验，筛选出2有应用价值的公式这里通过样本间的相似性关系定义类与类间的分离性以及同一个类别内部的一致性，从而使得计算过程得到简化1.2.1 有效性函数的定义字典上将类定义为许多相似或同事物的综合这个定义包含2层含义：第1层，在同一个类内的样本相互之间具有相似或相同的属性，也就是说，聚类的致密性度量的值应该是极小化的，否则，如果属性不同的样本被划分到同一个类内，那么这个类的类内致密性度量的值就会较大；第

8、2层是好的聚类的各个类别间的分离性7应该是很好的，如果本应属于同一个类的样本被分到不同类别内，那么类与类之间的重叠就会较大，也就是说，一个好的聚类结果得到的类别之间具有较大的离散性本文将通过样本间的相似性度量给出类内致密性度量和类间离散性7度量的定义设样本集通过某相似性度量得到的相似性矩阵为，其通过凝聚式层次聚类算法得到的系统树图为对于此系统树图中的任何一层，设其中包含个聚类，每个聚类中含有个样本，本文将所有样本间的相似性的算术平均值叫做样本集的平均相似性向量，即对于一个类，这里把类内所有样本间相似性的算术平均值叫做类内平均相似性向量类是具有相似属性样本的集合，同一类内样本相互间的相似性差异相

9、对较小也就是说，每个样本与其他样本的相似性与类内平均相似性向量就会相对小于是有下面的定义：定义1 (类内致密性度量)设是样本集的层次聚类系统树图中某一层，并设其中包含个聚类每个聚类中含有个样本，样本集的聚类结果的类内致密性度量定义为： (2-1)若要类与类间的分离性较好，各类的平均相似性向量与样本集平均相似性向量的差异必然要大由此本文通过类内平均相似性向量与样本集平均相似性向量的距离来定义类间离散性度量定义2 (类间离散性度量)设是样本集X的层次聚类系统树图中某一层，并设其中包含个聚类，每个聚类中含有个样本，样本集的这种聚类结果的类间离散性度量定义为： (2-2)对于一个好的聚类，同一个类内的

10、样本越相似越好，而不同类别间的样本相似性越小越好于是类内致密性度量的值越小越好，而类间离散性度量的值越大越好定义3 (新的有效性指标)建立新的有效性指标为： (2-3)聚类结果对应的越大，聚类的结果越好1.3 本章小结层次聚类算法，也称为树聚类算法，它的目标是对于具有个样本的集合，首先通过相似性函数计算样本间的相似性并构成相似性矩阵，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到的聚类序列针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个新的聚类有效性函数层次

11、聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题因此可以建立一个新的基于相似性矩阵的有效性函数，使得聚类效果更好第2章 层次聚类算法的应用2.1 多机系统分析意义在实际的电力市场运营中，准确、合理地划分电价区域是提供正确电价的前提和保证为了实现准确的电价区域划分，这里以节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价的特征量，借助模拟人类视觉系统的尺度空间理论，提出了一种基于尺度空间层次聚类的电价区域划分方法，在无需

12、事先设定任何区域划分信息的情况下实现了准确、合理的电价区域划分准确的电价区域划分是制定有效、简洁的区域电价的关键不准确的电价区域划分10将会造成市场电价的歪曲，导致阻塞发生频率的增加目前，在实际运行的电力市场中，一般都基于系统运行人员的经验和判断来划分电价区域然而由于输电网络的庞大和复杂，仅仅凭借人的经验制定的电价区域划分方案很难做到准确、合理文献11介绍了输电网为辐射网络时，以阻塞线路为区域边界的电价区域划分方法然而，实际的输电网却是环形网络，仅以阻塞线路为边界将无法实现输电网络的区域分割提出了根据节点间电价的相似性来划分输电网络的思想，却没有给出具体的实现方法为了实现准确的电价区域12划分

13、，本文引入模拟人类视觉系统的尺度空间层次聚类算法，提出了一种新的电价区域划分方法该方法通过提取节点注入功率对阻塞线路传输功率的灵敏度系数来表征节点电价的特征，形成节点的聚类样本；借助基于尺度空间的层次聚类算法实现了样本点集的不断融合，结合电价区域划分的实际问题，提出了获取最优聚类的条件，从而在无需事先设定任何区域划分信息的情况下实现准确、合理的电价区域划分2.2 节点电价的特征量提取电价区域划分的实质是按照节点电价的相似程度，即以节点电价作为节点聚类的特征量来实现对节点的汇集然而直接采用节点电价作为聚类的特征量却会带来以下问题：(1) 输电网节点众多，节点电价的计算复杂；(2) 节点电价随时间

14、不断变化的特点会引起电价区域划分边界频繁变更，不利于市场的稳定因此，直接采用节点电价作为聚类特征量在实际应用中并不理想下面从节点电价求解的直流潮流模型出发，获得既能映射出节点电价的大小，又较为稳定(不会随时变化)的特征量指标基于直流潮流，系统调度的优化模型如下： (4-1)式(4-1)中为维节点注入有功功率矢量(不包括平衡节点)；为平衡节点的注入有功功率；为维矩阵，代表节点注入功率对线路传输功率的灵敏度系数，它只与输电网的电纳矩阵和节点线路关联矩阵有关；为维全1矢量；为维线路传输功率限值矢量；为维节点成本函数矢量，为平衡节点的成本函数，它们可依据市场参与者的报价曲线推出；为输电网的节点总数，为

15、线路总数构建优化问题(1)的Lagrange函数： (4-2) 由，可以获得节点电价的计算公为：(4-3)式中为平衡节点的节点电价；维节点电价矢量(不包括平衡节点)；为功率平衡等式约束的Lagrange乘子；维线路传输功率不等式约束的Lagrange乘子矢量当线路阻塞时，线路功率的不等式约束成为有效约束，其对应的Lagrange乘子；当线路不处于阻塞状态时，线路功率的不等式约束为无效约束，其对应的Lagrange乘子由式(4-3)可以看出，节点电价的大小与平衡节点的边际成本(即节点电价)、阻塞线路的影子价格(即Lagrange乘子)以及节点注入功率对线路传输功率的灵敏度系数有关两节点和的电价之

16、差为： (4-4)式中、分别为节点和的节点电价；代表阻塞线路集合；为矩阵的第行元素；、为矩阵的第行列和列元素从式(4-4)可见，节点间的电价差与节点注入功率对阻塞线路传输功率的灵敏度系数之差成比例只要节点间的灵敏度系数相近，则无论阻塞线路影子价格的数值大小如何，节点间的电价始终会相近，虽然相近的程度会随着系统运行状态的变化及阻塞线路影子价格的不同而改变因而，采用节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价的特征量来进行节点的聚类，可以很好地完成对电价相近节点的汇集而且灵敏度系数不会随输电网运行状态的改变而变化，只要输电网的拓扑结构不变，灵敏度系数的数值将会保持不变因此，采用该指标作为

17、节点电价的特征量来进行节点的聚类，在一段时间内可以获得较为稳定的电价区域边界2.3 基于尺度空间聚类的电价区域划分2.3.1 尺度空间理论随着神经生理学的发展和计算机辅助解剖学的研究，人们已经提出了几个相当精确的初级视觉系统计算模型它们分别建模于视觉系统的不同层次、不同部分，尺度空间理论便是其中之一它定量地描述出由视网膜侧向联接所造成的图像模糊化效应13在人类的视觉过程中，眼睛将外部场景成像在视网膜上，大脑中形成的图像可视为一群空间中的光点集合随着尺度的增加或分辨率的下降，图像逐渐模糊化，每个小光点将融合成光斑，直至当尺度充分大时，整个图像成为一个大光斑在不同尺度下的图像形成了一个分层结构，大

18、光斑由小光组成，每个光斑仅在一定的尺度范围内存在，当尺度小于此范围时，光斑分裂成数个小光斑，而当尺度大于此范围时，光斑将与其它光斑融合对于给定的维空间的光点集，数学上光点可由Dirac广义函数表示，即：，(4-5)于是，由光点集在空间形成的图像为： (4-6)根据视觉前端系统的尺度空间理论，图像的多尺度可表示为为与高斯核的卷积，即： (4-7)式中为高斯函数，高斯函数的参数称为尺度函数，由构成的空间即为尺度空间在给定尺度下，光斑的中心定义为关于的一个极大值点，光斑则为关于梯度系统的吸引域，记为，即： (4-8)其中为梯度系统初值问题： (4-9)在给定尺度下，验证点是否属于光斑可以通过求解上述

19、方程来完成近年来，有学者将视觉前端系统的尺度空间理论引入聚类算法，将样本的聚类过程比于人眼对事物的感知方式，提出了基于尺度空间的层次聚类算法，该方法具有无需设定初始划分，通过局部寻优即可确定聚类中心，且能够有效判定最优聚类中心和类别个数等一系列的有点，从而避免了划分聚类法，如均值，模糊均值聚类算法都需要设定初始划分、寻找全局最优聚类和难以确定聚类有效性的缺点，同时也克服了系统聚类法，如离差平法和法、最短距离法、最长距离法，难以准确度量样本间的相似度和难以合理选取最优聚类截取水平的缺点，为有效解决电价区域划分问题提供了一条新的途径2.3.2 基于尺度空间层次聚类的电价区域划分1. 聚类样本在划分

20、电价区域前，根据输电网的实际运行情况，确定出在一段时间内可能出现的阻塞线路(这一步骤的具体实现可以在考虑市场中各种不确定因素的情况下通过采用Mont Carlo模拟法来对输电网的阻塞情况进行概率分析，从而确定出最可能发生阻塞的线路，此处不再详述)，将它们归入阻塞线路集合，针对这些阻塞线路，计算出每个节点电价的特征量，即节点注入功率的灵敏系数然后，将他们映射到高位空间上，(空间位数为阻塞线路数)，形成聚类的样本点集通过对样本点的聚类，便可以按照节点电价的相似度，实现节点的汇集，从而完成电价区域的划分2. 基于尺度空间的区域划分将尺度空间理论引入到输电网节点的聚类之中，需要聚类的每个样本被视作空间

21、中的一个光点，即光点集式中，为节点的注入功率对阻塞线路传输功率的灵敏度系数，为阻塞线路总数随着尺度的增加，光点逐渐融合成光斑，每个光斑被视为一个样本的聚类，它由落在该光斑内的所有光点构成，并由相应的光斑中心表示光斑逐渐融合的过程可类比为样本相互聚集融合，直到最后全部归并为一个大光斑，即所有的样本聚合成一个类，于是形成了随尺度空间变化的层次聚类树光斑中心或聚类中心为光点集关于台的极大值点，它可以通过求解微分方程(4-9)来获得运用Euler数值微分方法来求解，并且微分方程(4-9)的解在各时刻(为步长，, )处的值形成了序列, 采用对数坐标，于是聚类中心求取的迭代公式为： (4-10)式中一般取

22、0.2，以便迭代过程可以获得较好的收敛特性综合上述样本的融合过程，基于尺度空间层次聚类的具体步骤如下：1) 置迭代次数，设定充分小的初始尺度，使每个样本成为一个聚类，它为该类的中心；2) 对于尺度下的每个聚类中心，通过式(4-10)的迭代计算，求出尺度下新的聚类中心当两个类的聚类中心相同时，两个类便融合为一个新的类，两个类中的样本便归并到新的类中；3) 当存在两个及以上的类时，以一定的比例改变尺度大小，即，设，重复步骤2)；4) 直到只有一个类为止，生成完整的聚类树3. 聚类的有效性在样本点集的层次聚类过程中，生成了完整的聚类树在不同尺度上，出现了不同的聚类，获得了不同大小的电价区域在这众多的

23、电价区域中，哪些电价区域是最优的，即节点聚类的有效性问题，将借助尺度空间层次聚类算法中的聚类有效性标准，并结合电价区域划分的特点来解决 存活时间每个类都是在一定的尺度范围内才会存在当尺度超出此范围时，该类分裂或融合成其它类依据Witkin的心理实验结果，即在人的视觉系统中，那些在较大尺度范围内可观察的物体结构较之那些在较小尺度范围内可观察到的物体结构更容易被感知，故可以得出聚类的一个有效性检验标准：存活时间，存活时间长的类优于存活时间短的类类的存活时间是指类从产生到消亡的对数尺度范围，即： (4-11)式中为该类产生的尺度，为该类消亡的尺度(即该类与其它类融合为新类的尺度) 紧凑程度和孤立程度

24、直观上讲，同类样本间的距离越小，类与类的样本间距离越大，则聚类效果越好基于此，提出了两个有效性检验标准：紧凑程度和孤立程度对于某一个类来说，紧凑程度和孤立程度的定义如下： (4-12) (4-13)式(4-12)和(4-13)中为类的聚类中心；为样本点；表示在尺度样本点与所有聚类中心之间的距离；表示在尺度下所有样本点与第个聚类中心之间的距离对于一个好的聚类来说，类的紧凑程度和孤立程度应该接近于1采用上面给出的3个聚类有效性标准，结合电价区域划分问题，完成最优聚类的选取，从而获得输电网的电价区域最优聚类的选取步骤如下：第1步 选取满足一定要求的聚类，形成有效聚类点集从聚类树的顶结点开始向下搜索，将具有以下条件的结点形成聚类点集1) 类的紧凑程度和孤立程度大于一定阈值；2) 类中样本点(或节点数)多于一定个数；3) 类中样本点之间的距离小于一定数值，或类中节点间的电价差小于一定阈值，即： (4-13)式中为阻塞线路影子价格的期望值；为