TiliNG——用于密度不敏感状态空间生成的新型增长神经气体（GNG）变体及其应用

《Array》：TiliNG – A new Growing Neural Gas variant for density insensitive state space generation and its applications

　　

TiliNG：一种新型增长神经气体（Growing Neural Gas, GNG）变体，能够生成密度不敏感且均匀的状态空间表示，并仅需一个可解释的超参数（半径R）。非平稳数据处理：与标准GNG变体不同，TiliNG能够在遗忘先前学习结构的前提下，适应突然和渐进的数据分布变化。密度均匀性：TiliNG避免了高密度区域的过度表示及对稀有观测的忽略，使其非常适用于异常检测。参数选择方法：为满足期望的节点数量，提出了选择R参数的实用方法。广泛适用性：TiliNG被验证为聚类、分类、异常检测以及LiDAR点云降采样中的有效工具，在状态空间均匀性方面持续优于标准GNG、GNG-U和AING。

**TiliNG：一种用于密度不敏感状态空间生成的新型增长神经气体（GNG）变体及其应用**

**一、研究背景与问题**

在大数据时代，持续增长的高维样本（?ⁿ）为数据分析带来了巨大挑战。样本的紧凑表示既需保留相关信息，又需具备追踪数据趋势的能力。增长神经气体（Growing Neural Gas, GNG）算法因其能够以少量离散状态实时表示和聚类大规模观测数据，自1995年提出以来在机器人三维环境感知、网络入侵检测、非平稳数据流学习等领域得到广泛应用。然而，现有GNG变体存在三个主要缺陷：其一，面对非平稳分布时，多数GNG算法仅能通过遗忘旧知识来适应新分布，难以同时保留历史行为；其二，超参数数量过多（如学习率、边年龄阈值、插入间隔等），只能依赖启发式调整，且最终状态空间表示强烈依赖于参数选择；其三，标准GNG将更多节点分配到高密度区域，稀有观测可能被完全忽略，这不利于异常检测等任务。针对上述不足，研究人员提出了TiliNG算法，旨在实现密度不敏感、均匀覆盖状态空间，且仅需单一可解释超参数R。该算法能够在不遗忘旧结构的前提下处理突变和渐变分布变化，并在聚类、分类、异常检测及LiDAR点云缩减等多项应用中得到验证。论文发表在《Array》期刊。

**二、研究内容与总体结论**

TiliNG以覆盖K维观测空间为目标，使用K维球（K-ball）均匀填充整个空间，球体半径为唯一超参数R，R值越小表示分辨率越高、节点数越多。算法通过训练、适应和删除三个步骤在线构建状态空间：当样本与最近节点（最佳匹配单元，BMU）的距离大于R时创建新节点；否则将该样本分配给BMU，并执行适应和删除操作。适应步骤通过最小化节点与其局部邻域（2R范围内节点）的距离方差来调整BMU位置，同时受样本坐标边界约束；删除步骤则依据重叠体积大小去除冗余节点。相比标准GNG、GNG-U和AING，TiliNG在状态空间均匀性上持续最优，且能很好地记忆过去行为。更重要的是，TiliNG天然保留稀有观测节点，使其成为异常检测的理想基础。

**三、关键技术方法**

研究人员采用了如下关键技术（无样本队列，数据来源包括公开真实数据集[ForestCover、CreditcardFraud、Musk、HTTP、SMTP、Mammography]及LiDAR点云数据[27]）：（1）利用空间索引结构（如R\*-tree）将最近节点搜索复杂度降至??(log n)；（2）采用Karush-Kuhn-Tucker（KKT）定理和不动点迭代近似求解带约束的距离方差最小化问题；（3）使用不完全Beta函数计算K维球体之间的相对重叠体积，以此决定删除节点；（4）提出三种R参数选择方法：二分法、基于多元正态分布协方差椭球的解析边界法，以及两者结合的组合方法；（5）在图结构构建中引入边拓扑校正算法，消除相交边以保证拓扑保持性；（6）采用C++并行实现并提供Python接口。

**四、主要研究结果**

**5.1 TiliNG评估**：在二维单位正方形均匀采样和Fibonacci螺线数据上，TiliNG均生成均匀分布且贴合边界的节点；在三维楔形结构数据上，其状态空间表示同样均匀；在真实基准数据集上，TiliNG的表示均匀性优于对比算法。

**5.2 与GNG变体的比较**

**5.2.1 密度不敏感表示**：在二维正态分布数据上，标准GNG和GNG-U仅表示高密度区域，完全忽略离群点；AING保留离群点但过度表示高密度区；TiliNG则保持离群点可辨识且避免高密度区过表示。采用k近邻距离的中位数归一化局部MAD评分（S^(k)）量化节点均匀性，TiliNG在2-6NN评分中均取得最低值，表明其节点间距最均匀。

**5.2.2 记忆过去行为**：在非平稳基准（突变为矩形、连续移动圆、回到初始圆）上，标准GNG无法适应突变且节点无法删除；GNG-U适应但遗忘旧区域；AING与TiliNG均保留新旧区域，但AING对老区域覆盖不均。批次误差和总体误差曲线显示，TiliNG在整个训练过程中保持稳定且最低的误差水平。

**6.1 聚类**：将TiliNG与BFS连通分量检测结合，可正确识别嵌套半圆和双螺旋数据集上的簇结构，且效果优于SOINN；TiliNG预处理后接DBSCAN可显著减少计算时间，并推荐以2R作为DBSCAN的epsilon近似值。在MNIST高维数据上，TiliNG表现中等，反映高维聚类的固有困难。

**6.2 分类**：在MNIST数据集上，研究人员将60,000个训练样本输入TiliNG（R=7，产生3700个节点），按多数投票对节点赋予标签，再以最近节点分类剩余的10,000个测试样本，取得0.89的总体准确率。

**6.3 异常检测**：在六个真实数据集上，监督实验中异常分数取样本到最近节点的欧氏距离；无监督实验中分别将隔离森林（Isolation Forest, IF）和轻量在线异常检测器（LODA）应用于TiliNG的节点表示，并利用样本计数器计算重叠体积加权后的异常分数。结果显示，TiliNG能够保留异常观测，AUC得分大多与直接使用专用异常检测算法相当，甚至有所提高（例如ForestCover上IF+TiliNG为0.95，优于直接IF的0.88）。

**6.4 点云缩减**：在682个LiDAR点云上，将TiliNG与体素网格滤波比较，无论使用等体积节点还是匹配节点数，TiliNG的Chamfer距离均始终小于体素网格，说明TiliNG状态空间更忠实于原始点云。

**五、讨论与结论**

讨论部分指出，TiliNG不使用老化机制，因此不会删除由稀有样本创建的节点，这保证了观测支撑集的完整覆盖；样本计数器能够区分稀疏与密集区域，供应用层自主判断。长期运行时节点数不会无限增长，因为仅当样本距最近节点大于R时才插入新节点；若需要严格有界模型，可设置最大节点数并删除最久未更新节点，或动态增大R后执行删除扫描。TiliNG局部使用欧氏距离，对非线性流形数据仍能保持良好性能。结论为：研究人员引入了TiliNG，一种基于神经气体的密度不敏感状态空间表示方法，仅需单一超参数R；它在平稳和非平稳数据上均表现良好，能适应突变与渐变同时保留旧知识，表示均匀性优于标准GNG、GNG-U和AING；所提出的R参数选择方法增强了其实用性；作为预处理及建模工具，TiliNG在聚类、分类、异常检测和LiDAR点云缩减中均展现了高有效性和广泛适用性。