Voronoi-Markov chain and spatial entropy for point pattern analysis¶
会议: NeurIPS 2026
arXiv: 2609.36158
代码: https://github.com/nadeemlab/SMProfiler
领域: 其他
关键词: 空间点模式分析, Voronoi划分, 稠密盆地熵, 马尔可夫链谱隙, 空间病理学
一句话总结¶
针对空间点模式无监督分析中缺乏严格零模型与跨尺度交互度量的问题，本文基于Voronoi剖分与Ord分布提出了对聚集敏感的稠密盆地熵，并构建了模拟平面布朗运动的Voronoi-Markov链，利用谱隙与熵率实现了对点集聚集和双集重合度的锐利判别。
研究背景与动机¶
空间点模式分析（Point Pattern Analysis）是定量解析生态调查、地理流行病学以及计算组织病理学（如单细胞显微图像中细胞核空间分布）的核心基础。在这些前沿场景中，从海量复杂的空间点集里区分纯随机噪声与具有潜在生物学机制的非随机分布，对于科学假说发现至关重要。然而，现有主流空间分析指标（例如 Moran's I 与 Geary's C 空间自相关系数、Ripley's K 函数以及邻域富集分数）通常依赖于监督学习范式，核心症结在于这些经验统计量在真实的有限空间域与几何约束下缺乏明确的零假设（Null Model）基准，其实际抽样分布难以解析推导，因而在无监督探索性分析中受限严重。尽管经典的泊松点过程（Poisson Point Process）常被假定为无偏理论基准，但实际显微成像中的细胞实体具备不可忽略的物理直径，表现出严格的最小间距排斥特征（即简单顺序抑制，SSI），导致连续密度或泊松均匀性假设往往与现实严重脱节。
早期将香农信息论熵扩展至空间几何的研究，大多局限于规则网格划分或均匀几何离散化。当直接将平面点集转化为Voronoi多边形剖分时，若直接采用多边形面积比例定义所谓的均匀盆地分布（Uniform Basin Distribution），其概率测度实际上只是在数值上逼近整个平面的均匀勒贝格测度，无法承载点集本身的非随机集聚信息；与此同时，经典的Delaunay三角化角度几何统计量虽然具备解析零分布，但仅能聚合孤立多边形或三角形的局部形态，完全割裂了空间元素之间的邻居连通性与跨尺度相互作用机制。
本文的切入视角是重新审视Voronoi多边形作为吸引盆地（Basin）的动力学意义：一方面通过反比于面积的Ord离散分布直接捕捉点密度的局部积聚，另一方面将Voronoi胞腔拓扑骨架提升为离散马尔可夫跳跃过程以模拟连续域中的二维布朗运动。核心 idea：基于Voronoi剖分引入Ord分布定义对点聚集高度敏感的稠密盆地熵，并构建以盆地界面几何加权的Voronoi-Markov链，通过其谱隙、熵率及不变测度提供具有严谨下界与高区分度的无监督点模式表征。
方法详解¶
整体框架¶
输入为二维欧几里得平面上的离散点集 \(\{v_i \in \mathbb{R}^2\}_{i=1}^N\)，整体分析流程主要涵盖空间盆地剖分、稠密盆地熵计算、Voronoi-Markov转移矩阵构建，以及多集联合对齐度量四个阶段。首先利用QHull算法生成点集的Voronoi多边形（面积为 \(A_i\)）与对偶Delaunay三角剖分网络；在此几何基础上，利用Ord分布赋予每个盆地反比于面积的概率权重并计算稠密盆地熵，同时结合生物排斥约束推导其理论边界；随后，以相邻多边形共享的边界脊（ridge）长度与点间距离所张成的三角形面积为权重，构建行随机的马尔可夫转移矩阵以逼近连续维纳过程，提取其代数谱隙与熵率；最后，利用第一点集导出的马尔可夫链稳态不变测度，将第二点集做最近邻胞腔投影，计算两点集在动力学平衡意义下的对齐一致性。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入离散点集<br/>{v_i} 与空间边界"] --> B["Voronoi盆地剖分<br/>计算单元面积 A_i 与邻接脊"]
B --> C["稠密盆地熵构建<br/>Ord分布归一化反面积"]
B --> D["Voronoi-Markov链建模<br/>三角形面积加权转移矩阵"]
C --> E["单集空间聚集度量<br/>稠密盆地熵 H_db 与 SSI 理论下界"]
D --> F["动力学谱特征提取<br/>谱隙 σ、熵率与特征模态"]
D --> G["双集联合对齐分析<br/>不变测度 μ 与最近邻分箱 ν"]
E --> H["下游空间模式判别<br/>合成集中圆盘与病理单细胞组织分析"]
F --> H
G --> H关键设计¶
1. 稠密盆地熵与SSI几何理论下界：克服均匀离散化缺陷的聚集度量 针对均匀盆地分布无法表征空间聚集的本质缺陷，本文引入Ord密度估计思想构建稠密盆地分布（Dense Basin Distribution）。每个非无穷Voronoi盆地 \(i\) 分配的概率反比于其面积 \(A_i\)，即 \(p_i^{\text{db}} = (1 / A_i) / Z\)，其中归一化常数 \(Z = \sum_j (1 / A_j)\)。稠密盆地熵即为该分布的香农熵 \(H_{\text{db}} = \sum_i p_i^{\text{db}} (-\log p_i^{\text{db}})\)。在满足简单顺序抑制（SSI）假设的实际细胞组织中，任意两点间距大于 \(2r\)，每个有效盆地面积均有物理下界 \(A_i \ge a = \pi r^2\)。设区域内总有限面积为 \(A = \sum_{i=1}^N A_i\) 且 \(N > 2\)，利用对称多项式展开不等式可严格证明各盆地概率存在常数下界： $\(p_i^{\text{db}} > c := \left(\frac{a}{A}\right)^N (N-1)!, \quad H_{\text{db}} \ge N \cdot \min\left\{F(c), F(1-(N-1)c)\right\}\)$ 其中 \(F(x) = -x \log x\) 为凹函数。该解析下界与基于极端点集构型的启发式单点聚集下界高度契合，证明了当点集出现空间局部聚集时，\(H_{\text{db}}\) 会单调且显著降低，形成严谨的聚集判别准则。
2. 模拟二维布朗运动的Voronoi-Markov链：捕获跨尺度邻接连通性 孤立的多边形几何属性无法感知跨尺度的连通拓扑与邻居交互。为此，本文将点集构造成有限状态马尔可夫链的状态空间，使颗粒在盆地之间的跳跃近似平面连续布朗运动（维纳过程）。设盆地 \(i\) 与邻居 \(j\) 共享一条长度为 \(r\) 的边界脊（ridge），两点欧几里得距离为 \(u = |v_i - v_j|\)，该脊与 \(v_i\) 所围成的三角形面积恰好为 \(ru/4\)。转移概率正比于此过渡三角面积，并在对角线上保留可选正则化自转移权重 \(a\)： $\(p_{ij}^{\text{VM}} = \begin{cases} \frac{1}{4}ru / z_i, & v_i, v_j \text{ 为相邻邻居} \\ a / z_i, & i = j \end{cases}, \quad z_i = a + \sum_{j \in \mathcal{N}(i)} \frac{1}{4} r_{ij} u_{ij}\)$ 在无自转移设定（\(a \approx 0\)）下，内点单元的归一化因子严格等于该盆地总面积 \(z_i = A_i\)。该行随机转移矩阵不仅具有明确的微观粒子扩散几何解释，其代数特征提供了强大的宏观统计量：谱隙 \(\sigma = 1 - |\lambda_2|\)（\(\lambda_2\) 为第二大特征值模长）精确控制了马尔可夫扩散趋向平衡的收敛速度，对空间全局连通瓶颈高度敏感；而马尔可夫链的熵率（Entropy Rate）则定量刻画了随机游走在邻接网络中跳跃的信息不确定性衰减速度。
3. 基于不变测度的双点集一致性对齐：两类空间模式的跨集关联 在多细胞表型分析中，通常需要衡量第二类点集（如免疫浸润细胞）与第一类基底点集（如肿瘤细胞）之间的空间依赖或重合趋势。本文利用第一点集导出的Voronoi-Markov链的不变概率测度 \(\mu\)（满足 \(\mu P^{\text{VM}} = \mu\)），并将第二点集的点通过最近邻划分分配至第一点集的对应盆地中，得到经验频率分布 \(\nu\)。通过构造 VM 一致性度量及其反向一致性度量： $\(\text{Concordance} = \frac{1}{\sum_i \mu_i \nu_i}, \quad \text{Inverted Concordance} = \sum_i \frac{\nu_i}{\mu_i}\)$ 由于不变测度 \(\mu_i\) 在直观上正比于盆地面积（即反比于局部点密度），\(\nu_i / \mu_i\) 能以极高特异性捕捉两点集在高密度核心区的精密对齐，有效抑制了空间漂移带来的假阳性关联。
实验关键数据¶
主实验¶
为了验证所提出的空间熵及Voronoi-Markov特征在复杂生物微环境中的模式判别能力，本文在真实临床单细胞显微成像数据集上进行了系统验证，包括 536 例肺部肿瘤免疫微环境样本（Sorin et al.）与 30 例骨髓细胞地形图样本（Sarachakov et al.），对年轻与老年骨髓原红细胞以及不同肿瘤浸润表型进行无监督区分。
| 数据集 / 任务 | 评估指标 | 最佳案例 AUC | t 检验 p 值 | 表现评价与判别能力 |
|---|---|---|---|---|
| 骨髓单细胞地形图 (原红细胞年龄分层) | VM 谱隙 \(\sigma\) | 0.96 | 9.0e-4 | 全局最优，锐利捕获细胞微环境的拓扑稀疏与聚集转变 |
| 骨髓单细胞地形图 (原红细胞年龄分层) | 稠密盆地熵 \(H_{\text{db}}\) | 0.95 | 0.05 | 次优，有效反映强异质聚集带来的局域面积坍缩 |
| 骨髓单细胞地形图 (原红细胞年龄分层) | Delaunay 最小角 \(\alpha_{\min}\) 检验 | 0.93 | 3.0e-3 | 强基线，捕获局部三角形状各向异性偏差 |
| 肺癌免疫微环境 / 骨髓多表型 | 均匀盆地熵 \(H_{\text{ub}}\) | <= 0.64 | >= 0.29 | 无效，完全无法区分生物样本中的非随机空间结构 |
消融实验¶
为了精确解耦点集几何向心聚集对各度量的影响机制，作者设计了可控的集中圆盘模型（Concentrated Disc Model），将单位圆盘上的均匀分布沿径向施加变换 \(r \mapsto r \cdot r^q\)（\(q\) 为聚集浓度参数，\(q=0\) 为均匀泊松参考态）。100 次重复独立仿真的指标响应对比如下：
| 聚集参数配置 \(q\) | 归一化稠密盆地熵 \(H_{\text{db}}/\log_2 N\) | VM 谱隙 \(\sigma\) (归一化尺度) | VM 熵率响应行为 | Delaunay \(\alpha_{\min}\) 拟合优度 p 值 |
|---|---|---|---|---|
| \(q = 0.0\) (均匀泊松分布基准) | ~0.98 (接近理论上限 1.0) | 高稳态平台 (~1.0) | 基准高位状态 | p > 0.05 (与解析均匀分布高度拟合) |
| \(q = 1.0\) (向心集聚初显阶段) | ~0.72 (平滑显著衰减) | 急剧断崖式下跌 (~0.35) | 呈线性平缓衰退 | 显著性开始显现 (p 接近临界值) |
| \(q = 2.0\) (高度局部中心坍缩) | ~0.48 (较基准近似腰斩) | 趋近于零低位平台 (<0.05) | 持续线性降低 | p < 1.0e-3 (极显著拒绝泊松假设) |
关键发现¶
- 谱隙具有尖锐的相变响应：在集中圆盘实验中，随着聚集参数 \(q\) 增大，VM 谱隙在 \(q \approx 1\) 附近呈现出急剧的 Sigmoid 形截断突变，而稠密盆地熵则呈现近乎线性的平滑下降，这使得谱隙非常适合作为点集发生非均匀聚集的阈值探测器。
- 互补性与正交性：在真实肺癌与骨髓数据中，各指标联合分布的KDE图显示，VM谱隙、稠密盆地熵与Delaunay形态统计量之间展现出高度的统计独立性，各自捕捉了点模式的不同空间特征（全局扩散瓶颈 vs 局部面积离散度 vs 局部角分布），形成有力互补。
- 双集对齐度量的灵敏度与特异性权衡：VM一致性在 \(q > 2\) 时具备广谱的高灵敏度，但对大位移存在假阳性；而反向 VM 一致性则具备极高特异性，仅在两点集位移极小时激发出极高响应。
亮点与洞察¶
- 将几何剖分与随机扩散过程有机结合：把点集转化为具有严格物理扩散对应关系的Markov链，不仅克服了传统点模式指标缺乏高阶连通性信息的缺点，还赋予了特征值和谱隙明确的动力学演化含义。
- 揭示了非均匀点过程下空间熵的几何约束：利用SSI模型的最小排斥距离推导出了稠密盆地熵的非平凡理论下界，填补了经验空间熵缺乏几何约束支撑的理论空白。
- 扩展至多点集联合分析：通过不变测度将离散马尔可夫稳态与跨集合点频数关联，为复杂的免疫微环境细胞交互模式提供了轻量且稳健的量化工具。
局限与展望¶
- 缺乏解析形式的真实零分布：虽然讨论了泊松分布下Delaunay角的解析分布，但稠密盆地熵和VM谱隙在更现实的SSI零模型下的精确零分布尚未解析求解，目前主要依赖经验置换检验。
- 大规模点集的特征值计算开销：VM链谱隙计算需要对 \(N \times N\) 矩阵进行特征分解。虽然矩阵具有极度稀疏性（平均度仅为Voronoi邻居数，约6），但在 \(N > 10000\) 的超高分辨率组织图像中需要专门的稀疏迭代求解器优化。
- 边界效应处理：边界处存在未闭合的无限Voronoi多边形，目前方法直接截断或丢弃，在点集较少或边缘点占比较高时可能引入局部偏差。
相关工作与启发¶
- vs Ripley's K / Moran's I: 传统空间自相关或K函数高度依赖预设尺度半径且缺乏零模型解析分布，本文提出的Voronoi划分自适应于局部密度且无需调参。
- vs 经典均匀盆地熵 (Chapman 1970 / Batty 1974): 早期方法按多边形面积比例定义熵，本质逼近均匀测度对聚集不敏感；本文的Ord分布反比于面积，对聚集形成直接响应。
- vs 空间组学 Squidpy / 深度图学习: 相比黑盒特征抽取或依赖超参数的近邻图，本文提供了几何直观、无监督且数学可解释的拓扑谱指标。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次将Voronoi几何骨架与近似布朗运动的Markov链及Ord分布熵融为一体，为点模式分析开辟了全新视角。
- 实验充分度: ⭐⭐⭐⭐ 包含合成集中圆盘实验、双集偏移模拟以及两套真实生物组织病理学微环境数据集，数据扎实。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨，几何直觉与物理图景结合清晰。
- 价值: ⭐⭐⭐⭐ 为计算病理学、空间转录组学以及更广泛的空间统计学提供了一套免调参、高可解释性的开源工具库。