所属栏目：新闻中心发布时间：2026-04-22浏览量:791
南京信息工程大学计算机学院吕欢团队在《计算数学》发表论文《一种并行化快速两集合线性可分检测方法》，该研究针对线性可分性这一机器学习与数据分析中的基础判定难题，创新性地提出了一种基于计算几何的、具备高度并行化特性的快速初筛检测新方法。该方法通过构建“球面模型”并推导出点与集合线性可分的充要条件，成功将两集合的判定问题分解为大量可并行执行的子任务，在保证理论完备性的同时，实现了远优于现有主流方法的时间效率，为高维大数据场景下的线性可分性分析提供了高效的解决方案。
线性可分判定是判断空间中两个点集能否被一个超平面完全分离的基础数学问题，它在机器学习模型选择、神经网络结构设计、计算几何优化等领域具有重要指导意义。然而，现有方法如单纯形法、内点法、子空间投影法(SP)及基于凸包的方法，普遍存在时间复杂度高、对高维数据适应性差、或仅为近似判断等局限，难以满足大数据时代对效率的迫切需求。
该研究的核心理论创新在于构建了一个严谨的“球面模型”与判定准则。研究团队首先证明了“点与集合线性可分的方向不变性”，即可分性仅取决于相对方向，与距离无关。基于此，他们提出以被判定点为中心构建单位球面，将原始点集投影至该球面，从而将问题转化为“球心与球面点集的可分性”问题。研究发现，该球面点集与球心可分的充要条件是：该点集的最小包围球半径严格小于模型球半径。这一几何化判据，将复杂的代数不等式求解转化为了更易计算的几何包围球问题。
在此基础上，研究团队进一步提出了两集合判定的并行化框架。他们在排除了“异质间隙性交叠”(HGO)这一特殊情形后，严格证明：在非HGO情形下，两集合线性可分，当且仅当其中任一集合的每一个点，都与另一个集合线性可分。这一定理成为了算法并行化的基石。基于此设计的算法(算法1)可描述为：并行地检查集合A(或B)中的每一个点，利用上述球面模型判断其是否与另一集合B(或A)线性可分;若所有检查均通过，则两集合线性可分，否则不可分。
该方法在理论与实践上均展现出显著优势。理论上，其最坏时间复杂度为O(nd²)，其中n为总点数，d为维度，且具备高度的内在并行性。实践上，团队在Iris、Glass、MNIST、Fashion-MNIST等基准数据集及大量人工生成数据上，与SP、单纯形法、内点法、凸包法进行了详尽的对比实验。结果表明，尤其是在高维(如784维)和大规模(数万点)场景下，本文方法的时间效率显著优于所有对比方法，耗时通常仅为传统方法的数十分之一甚至更少，且在执行时间超过5小时的极限测试中，本文方法仍能在数秒内完成判定。同时，实验验证了该方法的并行化框架可有效加速其他传统算法。在准确性方面，该方法对所有线性可分任务均能准确判断，对线性不可分任务，在除极罕见的HGO分布情形外，也具有接近100%的准确率。
该研究为解决线性可分判定这一经典问题提供了一条全新的、高效的技术路径。其提出的并行化框架与快速初筛策略，不仅可直接应用于机器学习工作流中以指导模型选择与结构设计，提升分析效率，也为以凸包技术为代表的一系列计算几何方法的性能优化提供了新的理论工具与实现思路，具有重要的理论价值与广泛的工程应用前景。