论文部分内容阅读
基于距离（也称为度量）的层次聚类算法自出现以来,在生命科学、信息科学、计算机等领域发挥着重要作用。其一方面能够完成对数据进行聚类分析的基本功能,另一方面能够揭示数据内部结构—类与类—之间的关系,从而备受青睐。其聚类结果以聚类树的形式展示,提供了更加丰富的信息,尤其在那些聚类树本身具有明确物理意义的领域是不二选择。实际应用中距离数据具有不确定性,如存在测量误差或生成模型具有随机性,直接对数据进行层次聚类本质上是将带有测量误差距离的聚类结果视为真值,未考虑不确定性的统计特征。本文侧重理论研究,建立了以层次聚类结果为参数、以距离测量值为观测样本的统计模型,立足于参数估计理论实现最近邻层次聚类（Single Linkage Hierarchical Clustering,SLHC）结果的最优估计,分析了估计的统计性质,提出了基于最大似然的计算可行的估计算法,并成功应用于无线传感器网络（Wireless Sensor Network,WSN）设计和雷达高分辨距离像（High Resolution Range Profile,HRRP）目标识别分帧领域。本文的工作提出了在数据具有不确定性条件下层次聚类的最优实现方法,开辟了（层次）聚类理论研究的新领域,启发了解决实际问题的新思路。第一章为绪论,阐述了课题研究的意义,总结了层次聚类算法的理论研究和应用现状,指出了SLHC在理论上的优越性,即满足公理化规范、具有稳定性和收敛性,因此本文主要研究基于估计实现的SLHC算法。第二章简要介绍了层次聚类的基础知识,考虑距离输入数据的统计特性,建立了以聚类树（等效表示为超度量u）为参数的似然概率模型,并研究了SLHC估计的统计性质。将直接对测量数据进行SLHC简称为SLHC,以区别本文提出的估计SLHC实现算法。在计算SLHC的积分似然概率时,综合利用图论、泛函分析以及拓扑理论,详细分析了度量空间作为SLHC映射原像空间的几何结构和性质,依据最小张树（Minimum Spanning Tree,MST）将积分区间分为多个凸的子空间;证明了在满足一定模型条件下,SLHC等效于利用部分观测数据进行的估计—最大偏剖面似然估计（Maximum Partial Profile Likelihood Estimate,MPPLE）,从理论上间接证明了估计算法的优越性;另外,若将SLHC视为一个估计实现,同时证明了其具有一致性。为了解决无解析表达式的优化问题,第三章基于以上统计模型,提出了基于数值近似的聚类树结构的最大似然估计算法。利用蒙特卡洛积分近似似然概率,提出了基于狄利克雷（Dirichlet）分布的高度矢量参数a的均匀抽样方法。最大似然估计是在聚类树结构空间上最大化似然概率,本质上属于组合优化问题,当聚类点数为n时,组合数目过大—n!（n-1）!/2n-1—使得全局寻优无法计算,因此,提出了一种基于似然概率的缩小寻优空间策略。基于少量点的仿真实验证明了最大似然估计在获得准确聚类结果的性能上优于SLHC,但是该方法的计算复杂度随着聚类点数n的增大迅速增加。为了降低计算复杂度,第四章引入了拟似然概率（Pseudo-Likelihood）模型,并采用蒙特卡洛期望最大化（Monte Carlo EM,MCEM）算法实现估计。拟似然概率用各个变量的条件似然概率的乘积近似联合分布,用于处理联合分布复杂难以计算的问题。本问题最大的难点在于度量的三角形不等式约束关系使得联合概率函数无法计算,拟似然概率的思想被用来放宽三角形不等式约束—即只考虑那些距离较近的变量之间存在的三角形不等式约束。该估计算法极大地降低了计算复杂度,可有效处理数百个点的聚类问题。为了验证算法在一般度量上的性能,本章提出了一种递增地随机生成度量的方法,可高效地生成满足度量公理的随机高维度量。对100个点的SLHC估计仿真实验结果表明,该近似模型有效,通过MCEM算法可以估计得到比SLHC更准确的聚类结果。第五章为算法的应用研究,在WSN设计领域,提出了一种基于估计SLHC的WSN路由协议,有效降低了网络的能量消耗。本算法改进了基于层次聚类的WSN设计,在类内部采用PEDAP算法,同时,基于估计的SLHC算法在具有距离测量噪声的条件下比直接进行SLHC算法能量利用效率更高。仿真实验通过对比网络的平均能量消耗以及生命周期两项指标证明了算法的优越性。在雷达HRRP目标识别领域,提出了一种基于估计SLHC的分帧方法,对全方位角的HRRP幅度样本数据采用估计SLHC算法聚类,合并同一类内的HRRP得到平均距离像。仿真实验表明,基于估计聚类HRRP模板匹配的目标识别优于等间隔分帧和非估计聚类分帧方法。第六章结束语总结了本文的主要工作和创新点,并展望了未来的研究前景。