层次聚类算法应用

安徽三联学院题目：层次聚类算法应用姓名张翔专业计算机科学与技术班级计一系本科2班指导教师张林完成日期：2011年11月16日摘要本文围绕层次聚类分析算法展开研究．首先根据样本间的相似性关系定义分类后类与类间的分离性，以及同一个类别内部的一致性，并进行计算，从而使得计算过程得到简化．利用层次聚类算法实现分层聚类．在基于电价区域划分的实际问题中，这里结合人类视觉感知理论，提出了获取最优聚类的条件，从而实现了最佳的分类．本文的主要研究工作如下：第一章：说明了层次聚类分析的定义及研究方法，对层次聚类分析方法的有效性做出了细致的研究，并提出了基于相似矩阵的有效性函数．第二章：将层次聚类分析方法应用在电价区域的空间尺度划分问题中，进而实现了电价区域的划分．关键词层次聚类分析；有效性；空间尺度第1章绪论-1-目录摘要..........................................2目录...........................错误!未定义书签。第1章层次聚类分析算法及其研究...............21.1层次聚类分析算法..................................................................................................21.2层次聚类分析算法的有效性研究..........................................................................21.3本章小结..................................................................................................................5第2章层次聚类算法的应用.....................62.1多机系统分析意义..................................................................................................62.2节点电价的特征类提取..........................................................................................62.3基于尺度空间聚类的电价区域划分........................................................................82.4本章小结..................................................................................................................13结论.........................................14安徽三联学院-2-第1章层次聚类分析算法及其研究1.1层次聚类分析算法层次聚类算法[1]，也称为树聚类算法，它的目标是对于具有n个样本的集合dnRX，首先通过相似性函数计算样本间的相似性并构成相似性矩阵nnijrR)(，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到n的聚类序列．这个序列有着二叉树的形式，即每个树的结点有两个分支，从而使得聚类结果构成样本集X的系统树图{}12,,,qHHHH=,nq使得jjHC1,lmq且有jiCC或jiCC对所有的ij都成立．从系统树图形成的方式来看，层次聚类算法包括2种形式：凝聚式算法和分裂式算法．凝聚式算法是以“自底向上”的方式进行的．首先将每个样本作为一个聚类，然后合并相似性最大的聚类为一个大的聚类，直到所有的聚类都被融合成一个大的聚类．它以n个聚类开始，以1个聚类结束，分裂式算法是以一种“自顶向下”的方式进行的．一开始它将整个样本看做一个大的聚类，然后，在算法进行的过程中考察所有可能的分裂方法把整个聚类分成若干个小的聚类．第1步分成2类，第2步分成3类，这样一直能够进行下去直到最后一步分成n类．在每一步中选择一个使得相异程度最小的分裂．运用这种方法，可以得到一个相反结构的系统树图，它以1个聚类开始，以n个聚类结束．与分裂式算法相比，由于凝聚式算法在计算上简单、快捷，而且得到相近的最终结果，所以绝大多数层次聚类方法都是凝聚式的，它们只是在聚类的相似性度量的定义上有所不同．层次聚类算法是一个非常有用的聚类算法，它在迭代的过程中直到所有的数据都属于同一个簇才停止迭代，但是层次聚类也存在几个缺点，如聚类的时空复杂度[4]高、聚类的簇效率底、误差较大等．1.2层次聚类分析算法的有效性研究针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的第2章层次聚类分析算法及其研究-3-聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个聚类的有效性函数．在人工和实际数据集上的实验都表明了该有效性函数具有良好的性能．层次聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛[5]．虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题．根据模糊集理论[6]，系统树结构的每一层是由阈值l决定的．因此，最优聚类结果的选取问题就是最优阈值的选取问题．对于最优阈值的选取问题，使用F-统计量是研究者们比较认可的方法．当然随着模糊数学研究的深入，近几年来也有新的解决方法，Nasibov和Ulutagay提出了一个对于噪声更为稳定的FJP(fuzzyjointpoints)算法．该算法的基本思想是根据样本点与样本点之间的距离计算模糊关系矩阵，对于某一]1,0(，建立截集和等价类．此时，这些等价类决定了模糊聚类的每个截集．但并非对每个]1,0(都计算截集，而是只计算影响聚类个数的对应的截集．最终的截集是由取值区间上的最大值确定的．FJP算法已被证明能成功检测团装数据集及流形状数据集，即使添加噪声点后FJP算法也能成功识别流形状数据集．如何衡量一个聚类结果的好坏，以及如何确定最优聚类个数，这些都是聚类有效性问题．关于模糊C均值算法聚类有效性问题的研究也已经有了很丰硕的成果，从1974年开始研究者们提出了许多有效性函数．这些有效性函数构建聚类有效性指标的定义应当是客观的．通常情况下，刻画聚类有效性有2个标准：类内致密性和类间分离性．F-统计量也是从类内致密性和类间分离性2个方面考虑的．对于层次聚类算法的有效性研究，很多研究者还试图从模糊数学理论着手．范九伦和吴成茂对基于模糊集合定义的若干公式在聚类有效性方面的性质进行了讨论，并对分类性能进行实验，筛选出2有应用价值的公式．这里通过样本间的相似性关系定义类与类间的分离性以及同一个类别内部的一致性，从而使得计算过程得到简化．1.2.1有效性函数的定义字典上将类定义为许多相似或同事物的综合．这个定义包含2层含义：第1安徽三联学院-4-层，在同一个类内的样本相互之间具有相似或相同的属性，也就是说，聚类的致密性度量的值应该是极小化的，否则，如果属性不同的样本被划分到同一个类内，那么这个类的类内致密性度量的值就会较大；第2层是好的聚类的各个类别间的分离性[7]应该是很好的，如果本应属于同一个类的样本被分到不同类别内，那么类与类之间的重叠就会较大，也就是说，一个好的聚类结果得到的类别之间具有较大的离散性．本文将通过样本间的相似性度量给出类内致密性度量和类间离散性[7]度量的定义．设样本集X通过某相似性度量得到的相似性矩阵为nnR，其通过凝聚式层次聚类算法得到的系统树图为{}12,,nHHHH=．对于此系统树图中的任何一层kH，设其中包含c个聚类，每个聚类中含有in个样本，1,2,ic=．本文将所有样本间的相似性的算术平均值叫做样本集的平均相似性向量r，即niiRnr11．对于一个类，这里把类内所有样本间相似性的算术平均值叫做类内平均相似性向量)(ir．类是具有相似属性样本的集合，同一类内样本相互间的相似性差异相对较小．也就是说，每个样本与其他样本的相似性与类内平均相似性向量就会相对小．于是有下面的定义：定义1(类内致密性度量)设kH是样本集X的层次聚类系统树图中某一层，并设其中包含c个聚类{}12,,,cCCC每个聚类iC中含有in个样本，1,2,ic=．样本集X的聚类结果的类内致密性度量定义为：21)(1||||1injjjciiinrRnR(2-1)若要类与类间的分离性较好，各类的平均相似性向量与样本集平均相似性向量的差异必然要大．由此本文通过类内平均相似性向量与样本集平均相似性向量的距离来定义类间离散性度量．定义2(类间离散性度量)设kH是样本集X的层次聚类系统树图中某一层，并设其中包含c个聚类{}12,,,cCCC，每个聚类iC中含有in个样本，1,2,ic=样本集X的这种聚类结果的类间离散性度量定义为：第2章层次聚类分析算法及其研究-5-2)(1||||1rrnnRiciibe(2-2)对于一个好的聚类，同一个类内的样本越相似越好，而不同类别间的样本相似性越小越好．于是类内致密性度量的值越小越好，而类间离散性度量的值越大越好．定义3(新的有效性指标)建立新的有效性指标为：inbeRRV(2-3)聚类结果对应的V越大，聚类的结果越好．1.3本章小结层次聚类算法，也称为树聚类算法，它的目标是对于具有n个样本的集合dnRX，首先通过相似性函数计算样本间的相似性并构成相似性矩阵nnijrR)(，再根据样本间的相似性矩阵把样本集组成一个分层结构，产生一个从1到n的聚类序列．针对如何从层次聚类算法得到样本集的多种聚类结果中获得用户最满意的聚类结果，在深入研究聚类有效性的基础上，通过模糊相似性关系刻画聚类的类内致密性和类间分离性，可以建立一个新的聚类有效性函数．层次聚类算法，特别是凝聚式算法在计算上简单、快捷，而且能够得到相近的最终结果，所以层次聚类算法的应用较为广泛．虽然该类算法把数据集的多种分类结果都展现了出来，但是从算法所得到的各类分类结果中获得用户最满意的分类情况却成了一个问题．因此可以建立一个新的基于相似性矩阵的有效性函数，使得聚类效果更好．安徽三联学院-6-第2章层次聚类算法的应用2.1多机系统分析意义在实际的电力市场运营中，准确、合理地划分电价区域是提供正确电价的前提和保证．为了实现准确的电价区域划分，这里以节点注入功率对阻塞线路传输功率的灵敏度系数作为节点电价的特征量，借助模拟人类视觉系统的尺度空间理论，提出了一种基于尺度空间层次聚类的电价区域划分方法，在无需事先设定任何区域划分信息的情况下实现了准确、合理的电价区域划分．准确的电价区域划分是制定有效、简洁的区域电价的关键．不准确的电价区域划分[10]将会造成市场电价的歪曲，导致阻塞发生频率的增加．目前，在实际运行的电力市场中，一般都基于系统运行人员的经验和判断来划分电价区域．然而由于输电网络的庞大和复杂，仅仅凭借人的经验制定的电价区域划分方案很难做到准确、合理．文献[11]介绍了输电网为辐射网络时，以阻塞线路为区域边界的电价区域划分方法．然而，实际的输电网却是环形网络，仅以阻塞线路为边界将无法实现输电网络的区域分割．提出了根据节点间电价的相似性来划分输电网络的思想，却没有给出具体的实现方法．为了实现准确的电价区域[12]划分，本文引入模拟人类视觉系统的尺度空间层次聚类算法，提出了一种新的电价区域划分方法．该方法通过提取节点注入功率对阻塞线路传输功率的灵敏度系数来表征节点电价的特征，形成节点的聚类样本；借助基于尺度空间的层次聚类算法实现了样本点集的不断融合，结合电价区域划