一种并行化快速两集合线性可分检测方法

来源：计算数学杂志2024年第4期北京时间：

作者：吕欢, 钟水明, 王保卫, 薛羽, 刘琦

单位：1 南京信息工程大学计算机学院, 南京 210000;2 南京信息工程大学软件学院, 南京 210000;3 江苏省大气环境与装备技术协同创新中心, 南京 210000;4 数字取证教育部数字取证工程研究中心, 南京 210000

摘要：随着大模型所代表的AI技术革命浪潮的兴起, 以数据为中心的AI研究(Data-centric AI)快速崛起, 使得包括线性可分性在内的数据分析技术愈发受到研究者的重视. 线性可分判定作为数据分析的基础性数学问题, 在大数据时代的应用背景下, 高效的判定方法依然是个未被充分满足的需求. 本文提出并论证了一种基于球面模型的点与集合线性可分的充分必要条件；并基于该充要条件, 进一步提出并论证了两集合线性可分的并行化快速初筛检测方法. 本文方法的优势在于: (1)内在并行化特点, 具备低时间复杂度, 执行效率要远优于现有方法. (2)并行化适用性, 任何线性可分性判定方法均可以使用本文的并行化框架来实现加速. 文中基于基准数据集和人工数据集的验证实验也充分展示了本文方法的准确性和实现的高效性.

关键词：线性可分,计算几何,凸技术,数据分析,并行化

基金资助：国家自然科学基金(61972207,U22B2062,62172232);国家重点研发计划(2021YFB2700900);江苏省基础研究计划自然科学基金(BK20200039);江苏高校优势学科建设工程资助项目(PAPD);大气环境与装备技术协同创新中心(CICAEET)基金资助.