一种多尺度聚类方法的研究

一种多尺度聚类方法的研究

0网格多尺度聚类方法空间分组是空间点数据集的扩展方法。多尺度空间聚类算法可分为层次聚类算法和多分辨率网格聚类算法针对上述研究的不足,本文提出一种基于低通保边滤波和尺度约束大津法的网格多尺度聚类方法,将数据尺度和观察尺度引入空间聚类,从不同角度刻画空间数据的多尺度性。在数据尺度上,通过改变网格的大小表征不同网格粒度下聚类结果的空间结构;在观察尺度上,借鉴图像滤波算法,通过低通保边滤波器的迭代提取同一网格划分下的低频信息,以捕捉由微观到宏观的空间分布规律;通过将观察尺度作为参数引入大津法,实现尺度驱动的阈值提取,最终生成两种尺度因子共同作用下的一组空间聚类结果,辅助用户挖掘空间点的多尺度分布特征。11.1空间多尺度方法的引入不同学科和应用场景对尺度的定义不尽相同,本文基于数据对象多分辨率采样的必要性和固定分辨率下空间规律的多层次性,从影响空间多尺度聚类结果的尺度因子中选取了数据尺度与观察尺度作为多尺度聚类的影响因素。数据尺度是与观测目标相关的多尺度因子,指空间数据的采样尺度,与本文的网格大小相对应。可塑性面积单元问题(ModifiableArealUnitProblem,MAUP)是地理分析中普遍存在的问题观察尺度用于表征确定网格划分下的数据集从微观到宏观的多层次规律。在空间规律的多尺度系统中,高层次空间规律涉及范围广、稳定性强、更注重宏观趋势,低层次空间规律涉及范围小、稳定性弱、更注重微观细节宏观规律是微观规律的组合表现,通过逐步整合局部细节所蕴含的整体性趋势,可得宏观空间规律,而低通卷积滤波器能够实现局部空间信息的整合,有利于发现多个局部信息中更稳定的整体性规律1.2低频信息提取——低通保边滤波器本文空间多尺度聚类算法流程(图3a)为:首先,根据实际应用的精度需求设计多个数据尺度,并对原始空间点进行网格划分得到网格密度矩阵,将密度矩阵输入到观察尺度的处理流程中进行低通滤波,得到网格空间的低频信息;然后,确定低频空间的密度阈值,提取出高于密度阈值的网格单元作为兴趣区域,计算兴趣区域连通区,每个连通区即为一个聚类簇,将结果映射到空间数据点上,得到该层观察尺度上每个点的聚类信息,在上一层观察尺度低频空间的基础上迭代进行低通滤波,重复密度阈值提取、聚类簇生成与空间点映射的过程,得到下一层观察尺度的聚类结果,直到密度阈值为零或所有点均聚成一个聚类簇为止;最后,改变数据尺度划分方式并重复上述过程,得到各数据尺度上的多个观察尺度,形成数据尺度-观察尺度联合的一组多尺度空间聚类结果(图3b)。图3a中,数据尺度的网格大小根据精度需求人为指定,观察尺度的迭代由观察尺度层级与数据特征驱动,而低频信息提取和顾及尺度层级的密度阈值提取是算法的关键步骤。低频信息提取是对细节信息整合成结构规律的过程,当提取结果平滑过度时,聚类边缘细节损失过多,影响聚类的精度,当低频滤波平滑不足时,则难以有效消除噪声;而当密度阈值较小时,过多网格被识别为聚类,使得聚类融合速度过快,当密度阈值过大时,聚类融合速度慢,多观察尺度间聚类结果存在冗余。为此,本文针对低频信息提取问题,设计了一种一维低通保边滤波器,在平滑噪声的同时保持聚类边缘细节;针对密度阈值提取问题,将观察尺度作为约束项对大津法进行改进,设计了一种阈值提取方法,以有效平衡聚类融合速度与聚类结果冗余的矛盾。1.2.1目标网格的方法低通滤波常用于提取离散网格的低频信号,代表性方法有均值滤波、高斯滤波、中值滤波、小波滤波等′=*式中:a-e为相邻5个网格的编号,c为目标网格;1.2.2聚类聚类值设置在观察尺度的多尺度变换过程中,密度阈值的设置对聚类结果有显著影响。目前,常见的自动阈值提取方法有大津法、直方图凹面分析法等(4)式中:引入2实验结果与分析针对观察尺度低频信息提取、密度阈值选取、多尺度聚类结果精度、算法时间复杂度以及在真实大规模点数据集上的应用,通过如下实验综合验证本文方法的可行性:1)观察尺度低频信息的提取实验,验证本文低通保边滤波方法去噪和保边效果的有效性;2)观察尺度密度阈值的提取实验与多观察尺度聚类算法精度的对比实验,验证顾及观察尺度层级的密度阈值提取的合理性;3)算法时间复杂度的对比实验,验证本方法在海量空间数据集下的高效性;4)应用案例实验,验证本方法在实际多尺度空间规律挖掘场景下的可用性。2.1验数据及来源本文涉及定量分析的实验数据来自东芬兰大学及相关学术论文常用的带标注的8组公开数据集2.2聚类区域边缘提取本文通过与小波滤波结果对比,验证滤波算法在观察尺度低频信息提取中的去噪和保边效果。实验对每个数据集采用统一的网格划分,并分别进行低通保边滤波(图6)和小波滤波(图7)处理,然后用大津法提取相应的分割阈值,采用查准率、查全率和由图8可知,在查全率上二者相差不大,均能有效去除实验数据集中的噪点,但在查准率上,本文方法显著优于小波滤波,能更好地保留聚类的边缘信息。如图6中数据集b、c、d、h的结果所示,本文方法识别出的聚类区域边缘更加整齐、噪点少,聚类内部也更加均匀,保边与平滑效果更好。在图7所示的结果中,虽然小波滤波在数据集a、f、g上的查全率更高,但其查准率较差,在综合指标2.3密度阈值提取实验针对中国大陆基础设施POI数据集,分别使用大津法与本文方法进行多观察尺度上的密度阈值提取,定性评价本方法提取多层次空间规律的可行性;同时,分别使用DBSCAN和本文方法对图5中的数据集进行聚类,定量评价两种聚类方法的精度,以证明本方法的有效性。对于POI数据,实验分别采用大津法和本文方法剔除其中的背景噪点,结果如图9所示。大津法仅从数据特性出发,力求前景/背景差异最大化,导致在不同观察尺度提取的结果差异不大,效果欠佳;本方法提取了从局部高密度聚簇向周边中高密度面域式发散的多尺度特征,直观展现了数据东南多、西北少的格局与向中部延展的整体趋势,结果的层次更加丰富。对于公开数据集,固定每个数据的网格划分(数据尺度),采用本文方法提取密度阈值,得到图10(彩图见附录1)所示的多观察尺度聚类结果。随着观察尺度层级的递增,数据集a、c、e、f、g、h聚类结果中的局部细节被逐步平滑,小的聚类簇逐渐融合成大的聚类簇,留下更加宏观的规律特征;数据集d在观察尺度层级较小时,也呈现逐渐融合的趋势,但随着观察尺度层级的递增,由于数据集d右边聚类簇密度相对较低且无法连通到更大的聚类簇构成结构性要素,这些聚类又逐渐被当成噪声剔除,呈现先融合、后消失的特点;而数据集b中不同聚类簇之间的间隔较大,始终无法通过网格连通完成聚类簇的合并。综合以上结果可知,本文的密度阈值提取方法在一定程度上能够捕捉数据集所蕴含的多层次结构特征,支持从微观到宏观空间模式的立体分析。在定量分析实验中,将本文方法与DBSCAN算法聚类结果的调整兰德指数(AdjustedRandIndex,ARI)整体上看,DBSCAN算法聚类精度略优于本文方法,但本文方法能够在精度损失较小的情况下,实现多观察尺度上参数阈值的自动提取。在海量空间点聚类场景中,算法的调参过程尤为复杂且时间复杂度高,本文的自动密度阈值结果可以作为参考依据,具有一定的实际应用价值。甚至在数据集d和数据集f的结果中,本文方法聚类精度优于DBSCAN。这是因为这两个数据集的噪点分布均匀,DBSCAN很难选取到合适的参数将噪点分开;而本文方法在去噪的同时也考虑了密度值的差异,并且会通过调节权重将区域差异放大,因此能较好地区分噪声区域和聚类区域。2.4实验结果分析从中国大陆基础设施POI数据中随机抽取20万至200万数据点构成本实验数据集,在保证本文方法的网格大小与DBSCAN扫描面积、密度阈值与最小包含点数大致相同的情况下,对比本文方法和DBSCAN方法的运行时间(图12)。其中,DBSCAN基于scikit-learn0.20.3实现,并使用K-DTree索引避免计算全距离矩阵,本方法基于Python3.6.5实现。实验环境为Windows10操作系统台式机,CPU为4核E3-1240v6处理器,内存为16GB。可以看出,本文方法的时间复杂度与原始点数量基本呈线性相关(2.5核心高密度区域的空间结构以中国大陆基础设施POI数据为例,由细到粗将数据尺度划分为5个网格大小等级,运用本文方法进行多尺度网格聚类,结果如图13(彩图见附录2)所示。可以看出,当数据尺度细、分析尺度层级低时,聚类结果的细节破碎,展现出微观视角下核心高密度区域的空间结构;当数据尺度粗或分析尺度层级高时,结果的宏观趋势更加明显。在同一数据尺度下,随着观察尺度层级的提升,聚类簇的总数量不断减少,各聚类簇的空间范围也逐步扩大,细节信息被逐步剔除,展现出更宏观的结果;在不同数据尺度下,由于数据信息量存在差异,得到的观察尺度层级数量也有所不同。随着数据尺度变粗,虽然能够较好地捕捉整体的空间结构,但聚类的边缘细节损失严重,表现出较为明显的锯齿状。基于中国大陆基础设施POI数据分布的基本常识可以发现,本文方法在数据尺度与观察尺度上提取的多种聚类结果与观察者的多层次空间认知结果较为符合,能够一定程度上辅助海量空间点数据多层次空间结构的挖掘与可视化分析。3基于数据尺度自适应选取原则本文联合数据尺度和观察尺度两种尺度因子,设计了一种基于低通保边滤波的空间多尺度网格聚类算法。实验结果表明,本文的低通保边滤波器能在提取宏观低频信息