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

A SUFFICIENT AND NECESSARY PARALLELIZATION FAST METHOD FOR TESTING LINEAR SEPARABILITY OF TWO SETS

作　　者：吕欢 钟水明[2] 王保卫[1,3,4] 薛羽 刘琦[2] Lyu Huan;Zhong Shuiming;Wang Baowei;Xue Yu;Liu Qi(School of Computer Science,Nanjing University of Information Science&Technology,NanJing 210000,China;School of Software,Nanjing University of Information Science&Technology,NanJing 210000,China;Jiangsu Collaborative Innovation Center for Atmospheric Environment and Equipment Technology,NanJing 210000,China;Digital Forensics Engineering Research Center of the Ministry of Education,NanJing 210000,China)

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

出　　处：《计算数学》2024年第4期424-448,共25页Mathematica Numerica Sinica

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

摘　　要：随着大模型所代表的AI技术革命浪潮的兴起,以数据为中心的AI研究(Data-centric AI)快速崛起,使得包括线性可分性在内的数据分析技术愈发受到研究者的重视.线性可分判定作为数据分析的基础性数学问题,在大数据时代的应用背景下,高效的判定方法依然是个未被充分满足的需求.本文提出并论证了一种基于球面模型的点与集合线性可分的充分必要条件;并基于该充要条件,进一步提出并论证了两集合线性可分的并行化快速初筛检测方法.本文方法的优势在于:(1)内在并行化特点,具备低时间复杂度,执行效率要远优于现有方法.(2)并行化适用性,任何线性可分性判定方法均可以使用本文的并行化框架来实现加速.文中基于基准数据集和人工数据集的验证实验也充分展示了本文方法的准确性和实现的高效性.With the rise of the AI technology revolution represented by ChatGPT,data-center AI research is rapidly emerging.Data analysis techniques including linear separability have received increasing attention from researchers.Linear separability is a fundamental mathematical problem in data analysis,but in the current big data era,an efficient method for testing linear separability is still an unsatisfied demand.This paper proposes and proves a sufficient and necessary condition for the linear separability between a point and a set based on the sphere model;and based on this necessary and sufficient condition,a parallel rapid preliminary screening method for determining the linear separability between two sets is further proposed and demonstrated.The advantages of the method proposed in this paper are:(1)its inherent parallelization properties enable low time complexity in implementation and more efficiency compared to the existing methods;and(2)the universality of the parallel framework.Any method for determining linear separability can be accelerated using the parallel framework described in this paper.The verification experiments based on benchmark data sets and artificial data sets in this paper also fully demonstrate the accuracy of the method of this paper and the efficiency in implementation.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]