安徽三联学院题目：层次聚类算法应用姓名张翔专业计算机科学与技术班级计一系本科2班指导教师张林完成日期：2011年11 月16 日摘要本文围绕层次聚类分析算法展开研究．首先根据样本间的相似性关系定义分类后类与类间的分离性，以及同一个类别内部的一致性，并进行计算，从而使得计算过程得到简化．利用层次聚类算法实现分层聚类．在基于电价区域划分的实际问题中，这里结合人类视觉感知理论，提出了获取最优聚类的条件，从而实现了最佳的分类．本文的主要研究工作如下：第一章：说明了层次聚类分析的定义及研究方法，对层次聚类分析方法的有效性做出了细致的研究，并提出了基于相似矩阵的有效性函数．第二章：将层次聚类分析方法应用在电价区域的空间尺度划分问题中，进而实现了电价区域的划分．关键词层次聚类分析；有效性；空间尺度第1章绪论目录摘要 (2)目录 ........................... 错误!未定义书签。

第1章层次聚类分析算法及其研究 (2)1.1 层次聚类分析算法 (2)1.2 层次聚类分析算法的有效性研究 (2)1.3 本章小结 (5)第2章层次聚类算法的应用 (6)2.1 多机系统分析意义 (6)2.2 节点电价的特征类提取 (6)2.3 基于尺度空间聚类的电价区域划分 (8)2.4 本章小结 (13)结论 (14)安徽三联学院第1章 层次聚类分析算法及其研究1.1 层次聚类分析算法层次聚类算法[1]，也称为树聚类算法，它的目标是对于具有n 个样本的集合d n R X ⨯∈，首先通过相似性函数计算样本间的相似性并构成相似性矩阵n n ij r R ⨯=)(，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到n 的聚类序列．这个序列有着二叉树的形式，即每个树的结点有两个分支，从而使得聚类结果构成样本集X 的系统树图12,,,q H H H H , n q ≤使得j j H C ∈1,l m q 且有j i C C ⊂或φ=⋂j i C C 对所有的i j ≠都成立．从系统树图形成的方式来看，层次聚类算法包括2种形式：凝聚式算法和分裂式算法．凝聚式算法是以“自底向上”的方式进行的．首先将每个样本作为一个聚类，然后合并相似性最大的聚类为一个大的聚类，直到所有的聚类都被融合成一个大的聚类．它以n 个聚类开始，以1个聚类结束，分裂式算法是以一种“自顶向下”的方式进行的．一开始它将整个样本看做一个大的聚类，然后，在算法进行的过程中考察所有可能的分裂方法把整个聚类分成若干个小的聚类．第1步分成2类，第2步分成3类，这样一直能够进行下去直到最后一步分成n 类．在每一步中选择一个使得相异程度最小的分裂．运用这种方法，可以得到一个相反结构的系统树图，它以1个聚类开始，以n 个聚类结束．与分裂式算法相比，由于凝聚式算法在计算上简单、快捷，而且得到相近的最终结果，所以绝大多数层次聚类方法都是凝聚式的，它们只是在聚类的相似性度量的定义上有所不同．层次聚类算法是一个非常有用的聚类算法，它在迭代的过程中直到所有的数据都属于同一个簇才停止迭代，但是层次聚类也存在几个缺点，如聚类的时空复杂度[4]高、聚类的簇效率底、误差较大等．1.2 层次聚类分析算法的有效性研究针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的第2章 层次聚类分析算法及其研究聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个聚类的有效性函数．在人工和实际数据集上的实验都表明了该有效性函数具有良好的性能．层次聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛[5]．虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题．根据模糊集理论[6]，系统树结构的每一层是由阈值决定的．因此，最优聚类结果的选取问题就是最优阈值的选取问题．对于最优阈值的选取问题，使用F 统计量是研究者们比较认可的方法．当然随着模糊数学研究的深入，近几年来也有新的解决方法，Nasibov 和Ulutagay 提出了一个对于噪声更为稳定的FJP(fuzzy joint points)算法．该算法的基本思想是根据样本点与样本点之间的距离计算模糊关系矩阵，对于某一]1,0(∈α，建立-α截集和等价类．此时，这些-α等价类决定了模糊聚类的每个-α截集．但并非对每个]1,0(∈α都计算-α截集，而是只计算影响聚类个数α的对应的-α截集．最终的截集是由α取值区间上的最大值确定的．FJP 算法已被证明能成功检测团装数据集及流形状数据集，即使添加噪声点后FJP 算法也能成功识别流形状数据集．如何衡量一个聚类结果的好坏，以及如何确定最优聚类个数，这些都是聚类有效性问题．关于模糊C 均值算法聚类有效性问题的研究也已经有了很丰硕的成果，从1974年开始研究者们提出了许多有效性函数．这些有效性函数构建聚类有效性指标的定义应当是客观的．通常情况下，刻画聚类有效性有2个标准：类内致密性和类间分离性．F 统计量也是从类内致密性和类间分离性2个方面考虑的．对于层次聚类算法的有效性研究，很多研究者还试图从模糊数学理论着手．范九伦和吴成茂对基于模糊集合定义的若干公式在聚类有效性方面的性质进行了讨论，并对分类性能进行实验，筛选出2有应用价值的公式．这里通过样本间的相似性关系定义类与类间的分离性以及同一个类别内部的一致性，从而使得计算过程得到简化．1.2.1 有效性函数的定义字典上将类定义为许多相似或同事物的综合．这个定义包含2层含义：第1安徽三联学院层，在同一个类内的样本相互之间具有相似或相同的属性，也就是说，聚类的致密性度量的值应该是极小化的，否则，如果属性不同的样本被划分到同一个类内，那么这个类的类内致密性度量的值就会较大；第2层是好的聚类的各个类别间的分离性[7]应该是很好的，如果本应属于同一个类的样本被分到不同类别内，那么类与类之间的重叠就会较大，也就是说，一个好的聚类结果得到的类别之间具有较大的离散性．本文将通过样本间的相似性度量给出类内致密性度量和类间离散性[7]度量的定义．设样本集X 通过某相似性度量得到的相似性矩阵为n n R ⨯，其通过凝聚式层次聚类算法得到的系统树图为12,,n H H H H ．对于此系统树图中的任何一层k H ，设其中包含c 个聚类，每个聚类中含有i n 个样本，1,2,i c ．本文将所有样本间的相似性的算术平均值叫做样本集的平均相似性向量r ，即∑==ni i R n r 11．对于一个类，这里把类内所有样本间相似性的算术平均值叫做类内平均相似性向量)(i r ．类是具有相似属性样本的集合，同一类内样本相互间的相似性差异相对较小．也就是说，每个样本与其他样本的相似性与类内平均相似性向量就会相对小．于是有下面的定义：定义1 (类内致密性度量) 设k H 是样本集X 的层次聚类系统树图中某一层，并设其中包含c 个聚类12,,,c C C C 每个聚类i C 中含有i n 个样本，1,2,i c ．样本集X 的聚类结果的类内致密性度量定义为：21)(1||||1∑∑==-=i n j j j c i i in r R n R (2-1)若要类与类间的分离性较好，各类的平均相似性向量与样本集平均相似性向量的差异必然要大．由此本文通过类内平均相似性向量与样本集平均相似性向量的距离来定义类间离散性度量．定义2 (类间离散性度量) 设k H 是样本集X 的层次聚类系统树图中某一层，并设其中包含c 个聚类12,,,c C C C ，每个聚类i C 中含有i n 个样本，1,2,i c 样本集X 的这种聚类结果的类间离散性度量定义为：第2章 层次聚类分析算法及其研究2)(1||||1r r n n R i ci i be -=∑= (2-2) 对于一个好的聚类，同一个类内的样本越相似越好，而不同类别间的样本相似性越小越好．于是类内致密性度量的值越小越好，而类间离散性度量的值越大越好．定义3 (新的有效性指标) 建立新的有效性指标为：in be R R V -=λ (2-3)聚类结果对应的λV 越大，聚类的结果越好．1.3 本章小结层次聚类算法，也称为树聚类算法，它的目标是对于具有n 个样本的集合d n R X ⨯∈，首先通过相似性函数计算样本间的相似性并构成相似性矩阵n n ij r R ⨯=)(，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到n 的聚类序列．针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个新的聚类有效性函数．层次聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛．虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题．因此可以建立一个新的基于相似性矩阵的有效性函数，使得聚类效果更好．安徽三联学院第2章层次聚类算法的应用2.1 多机系统分析意义在实际的电力市场运营中，准确、合理地划分电价区域是提供正确电价的前提和保证．为了实现准确的电价区域划分，这里以节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价的特征量，借助模拟人类视觉系统的尺度空间理论，提出了一种基于尺度空间层次聚类的电价区域划分方法，在无需事先设定任何区域划分信息的情况下实现了准确、合理的电价区域划分．准确的电价区域划分是制定有效、简洁的区域电价的关键．不准确的电价区域划分[10]将会造成市场电价的歪曲，导致阻塞发生频率的增加．目前，在实际运行的电力市场中，一般都基于系统运行人员的经验和判断来划分电价区域．然而由于输电网络的庞大和复杂，仅仅凭借人的经验制定的电价区域划分方案很难做到准确、合理．文献[11]介绍了输电网为辐射网络时，以阻塞线路为区域边界的电价区域划分方法．然而，实际的输电网却是环形网络，仅以阻塞线路为边界将无法实现输电网络的区域分割．提出了根据节点间电价的相似性来划分输电网络的思想，却没有给出具体的实现方法．为了实现准确的电价区域[12]划分，本文引入模拟人类视觉系统的尺度空间层次聚类算法，提出了一种新的电价区域划分方法．该方法通过提取节点注入功率对阻塞线路传输功率的灵敏度系数来表征节点电价的特征，形成节点的聚类样本；借助基于尺度空间的层次聚类算法实现了样本点集的不断融合，结合电价区域划分的实际问题，提出了获取最优聚类的条件，从而在无需事先设定任何区域划分信息的情况下实现准确、合理的电价区域划分．2.2 节点电价的特征量提取电价区域划分的实质是按照节点电价的相似程度，即以节点电价作为节点聚类的特征量来实现对节点的汇集．然而直接采用节点电价作为聚类的特征量却会带来以下问题：(1) 输电网节点众多，节点电价的计算复杂；(2) 节点电价随时第4章 层次聚类算法的应用间不断变化的特点会引起电价区域划分边界频繁变更，不利于市场的稳定．因此，直接采用节点电价作为聚类特征量在实际应用中并不理想．下面从节点电价求解的直流潮流模型出发，获得既能映射出节点电价的大小，又较为稳定(不会随时变化)的特征量指标．基于直流潮流，系统调度的优化模型如下：⎪⎩⎪⎨⎧=+⋅≤⋅+0..)()(min max N T N N T p p e z P H t s p c p c e (4-1)式(4-1)中p 为1)1(⨯-N 维节点注入有功功率矢量(不包括平衡节点N )；N p 为平衡节点的注入有功功率；H 为)1(-⨯N L 维矩阵，代表节点注入功率对线路传输功率的灵敏度系数，它只与输电网的电纳矩阵和节点——线路关联矩阵有关；e 为1)1(⨯-N 维全1矢量；max z 为1⨯L 维线路传输功率限值矢量；)(p c 为1)1(⨯-N 维节点成本函数矢量，()N N c p 为平衡节点的成本函数，它们可依据市场参与者的报价曲线推出；N 为输电网的节点总数，L 为线路总数．构建优化问题(1)的Lagrange 函数：)()()()(max z p H p p e p c p c e L T N T N N T -⋅-+⋅-+=μλ (4-2) 由0,0=∂∂=∂∂N p L p L ，λρ=∂=N N N N p p c )(可以获得节点电价的计算公为：μλρλρT N N N N H e p p c p p c +⋅=∂∂==∂∂=/)()( (4-3)式中N ρ为平衡节点N 的节点电价；1)1(⨯-N 维节点电价矢量(不包括平衡节点N )；为功率平衡等式约束的Lagrange 乘子；1⨯L 维线路传输功率不等式约束的Lagrange 乘子矢量．当线路l 阻塞时，线路功率的不等式约束成为有效约束，其对应的Lagrange 乘子0≠l μ；当线路l 不处于阻塞状态时，线路功率的不等式约束为无效约束，其对应的Lagrange 乘子0=μ．由式(4-3)可以看出，节点电价的大小与平衡节点的边际成本(即节点电价)、阻塞线路的影子价格(即Lagrange 乘子)以及节点注入功率对线路传输功率的灵敏度系数有关．两节点i 和j 的电价之差为：∑∑∑Ω⊂Ω⊂Ω⊂-=-=-l lj li l l lj l l li l j i h h h h )(μμμρρ (4-4)安徽三联学院式中i 、j 分别为节点i 和j 的节点电价；Ω代表阻塞线路集合；l 为矩阵的第l 行元素；li h 、lj h 为矩阵H 的第l 行i 列和j 列元素．从式(4-4)可见，节点间的电价差与节点注入功率对阻塞线路传输功率的灵敏度系数之差成比例．只要节点间的灵敏度系数相近，则无论阻塞线路影子价格的数值大小如何，节点间的电价始终会相近，虽然相近的程度会随着系统运行状态的变化及阻塞线路影子价格的不同而改变．因而，采用节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价的特征量来进行节点的聚类，可以很好地完成对电价相近节点的汇集．而且灵敏度系数不会随输电网运行状态的改变而变化，只要输电网的拓扑结构不变，灵敏度系数的数值将会保持不变．因此，采用该指标作为节点电价的特征量来进行节点的聚类，在一段时间内可以获得较为稳定的电价区域边界．2.3 基于尺度空间聚类的电价区域划分2.3.1 尺度空间理论随着神经生理学的发展和计算机辅助解剖学的研究，人们已经提出了几个相当精确的初级视觉系统计算模型．它们分别建模于视觉系统的不同层次、不同部分，尺度空间理论便是其中之一．它定量地描述出由视网膜侧向联接所造成的图像模糊化效应[13]．在人类的视觉过程中，眼睛将外部场景成像在视网膜上，大脑中形成的图像可视为一群空间中的光点集合．随着尺度的增加或分辨率的下降，图像逐渐模糊化，每个小光点将融合成光斑，直至当尺度充分大时，整个图像成为一个大光斑．在不同尺度下的图像形成了一个分层结构，大光斑由小光组成，每个光斑仅在一定的尺度范围内存在，当尺度小于此范围时，光斑分裂成数个小光斑，而当尺度大于此范围时，光斑将与其它光斑融合．对于给定的d 维空间的光点集),2,1:(N i R x X d i =∈=，数学上光点可由Dirac 广义函数)(i x x -δ表示，即：⎩⎨⎧=∞+≠=-ii i x x x x x x ,,0)(δ，1)(=-⎰+∞∞-dx x x i δ (4-5)于是，由光点集在空间形成的图像()p x 为：)(1)(1∑=-=Ni i x x N x p δ (4-6)根据视觉前端系统的尺度空间理论，图像()p x 的多尺度可表示为),(σx P 为()p x 与高斯核的卷积，即：22||||12211),(*)(),(σπσσσi x x N i e N x g x p x P --=∑= (4-7)式中),(σx g 为高斯函数，222||||221),(σπσσx e x g -=，高斯函数的参数σ称为尺度函数，由),(σx 构成的空间即为尺度空间．在给定尺度下，光斑的中心*x 定义为),(σx P 关于σ的一个极大值点，光斑则为*x 关于梯度系统),(σx P dt dx x ∇=的吸引域，记为*()B x ，即：{}*00*),(lim :)(x x t x R x x B t d =∈=+∞→ (4-8)其中0(,)x t x 为梯度系统初值问题：⎪⎩⎪⎨⎧=∇=00),0(),(x x x x P dt dx x σ (4-9)在给定尺度σ下，验证点0x 是否属于光斑*()B x 可以通过求解上述方程来完成．近年来，有学者将视觉前端系统的尺度空间理论引入聚类算法，将样本的聚类过程比于人眼对事物的感知方式，提出了基于尺度空间的层次聚类算法，该方法具有无需设定初始划分，通过局部寻优即可确定聚类中心，且能够有效判定最优聚类中心和类别个数等一系列的有点，从而避免了划分聚类法，如k 均值，模糊C 均值聚类算法都需要设定初始划分、寻找全局最优聚类和难以确定聚类有效性的缺点，同时也克服了系统聚类法，如离差平法和法、最短距离法、最长距离法，难以准确度量样本间的相似度和难以合理选取最优聚类截取水平的缺点，为有效解决电价区域划分问题提供了一条新的途径．2.3.2 基于尺度空间层次聚类的电价区域划分1. 聚类样本在划分电价区域前，根据输电网的实际运行情况，确定出在一段时间内可能出现的阻塞线路(这一步骤的具体实现可以在考虑市场中各种不确定因素的情况下通过采用Mont Carlo 模拟法来对输电网的阻塞情况进行概率分析，从而确定出最可能发生阻塞的线路，此处不再详述)，将它们归入阻塞线路集合Ω，针对这些阻塞线路，计算出每个节点电价的特征量，即节点注入功率的灵敏系数．然后，将他们映射到高位空间上，(空间位数为阻塞线路数)，形成聚类的样本点集．通过对样本点的聚类，便可以按照节点电价的相似度，实现节点的汇集，从而完成电价区域的划分．2. 基于尺度空间的区域划分将尺度空间理论引入到输电网节点的聚类之中，需要聚类的每个样本被视作空间中的一个光点，即光点集),,1:(N i R x X d i =∈=式中(,,)ili dl x h h ，(1,,)li h l d 为节点i 的注入功率对阻塞线路l 传输功率的灵敏度系数，d 为阻塞线路总数．随着尺度的增加，光点逐渐融合成光斑，每个光斑被视为一个样本的聚类，它由落在该光斑内的所有光点构成，并由相应的光斑中心表示．光斑逐渐融合的过程可类比为样本相互聚集融合，直到最后全部归并为一个大光斑，即所有的样本聚合成一个类，于是形成了随尺度空间变化的层次聚类树．光斑中心或聚类中心为光点集),(σx p 关于σ台的极大值点，它可以通过求解微分方程(4-9)来获得．运用Euler 数值微分方法来求解，并且微分方程(4-9)的解0(,)x t x 在各时刻t nh (h 为步长，0h , 0,1,n )处的值形成了序列()x n , ),(σx p 采用对数坐标，于是聚类中心求取的迭代公式为：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=-+=∇⋅+=+∑∑=--=--012||)(||12||)(||2)0())(()()),((ln )()1(2222x x e e n x x h n x n x P h n x n x N i x n x N i x n x i x i i σσσσ (4-10)式中h 一般取0.2，以便迭代过程可以获得较好的收敛特性．综合上述样本的融合过程，基于尺度空间层次聚类的具体步骤如下：1) 置迭代次数1i，设定充分小的初始尺度0σ，使每个样本成为一个聚类，它为该类的中心；2) 对于尺度1-i σ下的每个聚类中心，通过式(4-10)的迭代计算，求出尺度i σ下新的聚类中心．当两个类的聚类中心相同时，两个类便融合为一个新的类，两个类中的样本便归并到新的类中；3) 当存在两个及以上的类时，以一定的比例改变尺度大小，即i i k σσ=+1，设1i i ，重复步骤2)；4) 直到只有一个类为止，生成完整的聚类树．3. 聚类的有效性在样本点集的层次聚类过程中，生成了完整的聚类树．在不同尺度上，出现了不同的聚类，获得了不同大小的电价区域．在这众多的电价区域中，哪些电价区域是最优的，即节点聚类的有效性问题，将借助尺度空间层次聚类算法中的聚类有效性标准，并结合电价区域划分的特点来解决．Ⅰ 存活时间每个类都是在一定的尺度范围内才会存在．当尺度超出此范围时，该类分裂或融合成其它类．依据Witkin 的心理实验结果，即在人的视觉系统中，那些在较大尺度范围内可观察的物体结构较之那些在较小尺度范围内可观察到的物体结构更容易被感知，故可以得出聚类的一个有效性检验标准：存活时间，存活时间长的类优于存活时间短的类．类的存活时间是指类从产生到消亡的对数尺度范围，即：12ln ln σσ-=l (4-11)式中1σ为该类产生的尺度，2σ为该类消亡的尺度(即该类与其它类融合为新类的尺度)．Ⅱ 紧凑程度和孤立程度直观上讲，同类样本间的距离越小，类与类的样本间距离越大，则聚类效果越好．基于此，提出了两个有效性检验标准：紧凑程度和孤立程度．对于某一个类i C 来说，紧凑程度P 和孤立程度S 的定义如下：∑∑∑∈--∈--=i j i t C x j x x C x x x ee P 22*22*2||||2||||σσ (4-12) ∑∑--∈--=x x x C x x x i i i eeS 22*22*2||||2||||σσ (4-13)式(4-12)和(4-13)中*ix 为类i C 的聚类中心；x 为样本点；∑--j x x j e 22*2||||σ表示在尺度σ样本点与所有聚类中心之间的距离；∑--x x x i e 22*2||||σ表示在尺度σ下所有样本点与第i 个聚类中心之间的距离．对于一个好的聚类来说，类的紧凑程度和孤立程度应该接近于1．采用上面给出的3个聚类有效性标准，结合电价区域划分问题，完成最优聚类的选取，从而获得输电网的电价区域．最优聚类的选取步骤如下：第1步 选取满足一定要求的聚类，形成有效聚类点集．从聚类树的顶结点开始向下搜索，将具有以下条件的结点形成聚类点集{}K C C C C ,,,21 =1) 类的紧凑程度和孤立程度大于一定阈值；2) 类中样本点(或节点数)多于一定个数；3) 类中样本点之间的距离小于一定数值，或类中节点间的电价差小于一定阈值，即：εμρρ≤-=-∑=d l lj li lj i h h 1)( (4-13)式中l μ为阻塞线路l影子价格的期望值；为电价区内允许的最大电价差值；在实际的电力市场运营中，l μ取输电网在不同运行状态下线路影子价格的平均值；ε应根据输电网的系统边际成本(即平衡节点的节点电价)，由市场参与者和系统调度员共同协商确定．第2步 从有效聚类点集{}K C C C C ,,,21 =中选取存活时间最长的聚类，获得最优聚类集合U (其中每个子集代表一个电价区域)，完成电价区域划分．最优聚类集合的选取过程如下：1) 初始化最优聚类集合U 为空集；2) 找出C 中存活时间最长的聚类点集k C ，把k C 加入U 中，并在C 中删除结点、包含结点k C 的所有上层结点以及被结点k C 包含的所有下层结点．重复步骤2)，直到C 为空集．2.4 本章小结以节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价聚类的特征量，不仅可以映射出节点电价的大小，而且不会随时变化，从而可以获得在一段时间内较为稳定且合理的电价区域划分．基于尺度空间层次聚类模拟了人类视觉的图像模糊化效应，随着尺度空间由小到大的逐步变化，在各样本点集的融合过程中生成聚类树．基于电价区域划分的实际问题，结合人类视觉感知理论，提出了获取最优聚类的条件，从而实现了最佳的分类．在实际应用过程中，可以进一步融入电力市场运营的专家知识，获得更为合理的聚类选取法则．。