地球信息科学学报

图/表详细信息

基于局部集聚特征尺度判定的兴趣点离群分布探测及其可解释性分析

吴鹏, 哈斯巴根, 秦福莹

地球信息科学学报, 2024, 26(7): 1594-1610. DOI: 10.12082/dqxxkx.2024.240039

算法名称	算法复杂度	算法复杂度说明	算法描述
KNN	$O (N 2 l o g N)$	对于KNN、LOF、COF及其集成算法的复杂度均采用大O计数法表达，其中N为POI要素的规模	KNN: 计算每个点与其他点的距离，并选择最近的K个邻居
LOF	$O (N 2 l o g N)$		LOF: 通过比较每个点与其邻域点的密度，计算局部离群因子
COF	$O (N 3)$		COF: 基于LOF，考虑全局信息，计算局部离群因子的平均值
Ensembling	$O (N l o g N) + O (N l o g N) + O (N 3)$		Ensembling: 构建共现矩阵(相似度图)；计算拉普拉斯矩阵；特征值分解
MC-DTIN	$O (N l o g N) + O (M) + O (N * m)$	MC-DTIN算法中N为POI要素的规模；M为初始Delaunay三角网的边数； m为删除全局长边后的各点的邻域个数	MC-DTIN: 构建Delaunay三角网；分别基于三层边长约束指标提取离群点
本文方法	$O (N l o g N) + O (K N) + O (N p) +$ $O (N s u b_g (K + 1 + E) l o g (K + 1))$	本文方法中N为POI的规模； K为邻域个数； N_p为新边集规模； N_sub_{_}_g为连通子图数量； E为子图中边数	构建Delaunay三角网；识别显著局部集聚尺度并生成新边集(N_p)；根据边长约束指标提取离群点，并在剩余点集(连通子图数量为N_sub_{_}_g)中识别离群簇

表1 各离群点探测方法详细信息

本文的其它图/表