基于商空间粒度理论的大规模SVM分类算法摘要：利用商空间粒度理论对已有的SVM分类算法进行改进，给出了一种新的SVM分类算法――SVM-G。该算法将SVM分类问题划分成两个或多个子问题，从而降低了SVM分类复杂度。实验表明，改进的算法适用于处理大数据量的样本，能在保持分类精度的情况下有效地提高支持向量机的学习和分类速度。关键词：粒度；商空间；支持向量机;分类;机器学习：TP301.6文献标志码：A：1001-3695(2008)08-2299-03Large-scaleSVMclassificationalgorithmbasedongranularityofientspacetheoryWENGui-hua??a,XIANGJun??b,DINGYue-hua??b(a.SchoolofComputerScienceEngineering,b.ResearchInstituteofComputerApplicationEngineering,SouthChinaUniversityofTechnology,Guangzhou510641,China)Abstract:ThispaperimprovedtheexistingSVMalgorithmwiththegranularityoftheientspacetheory,proposedanewSVMalgorithm（SVM-G）.TheimprovedalgorithmdividedSVMclassificationproblemintotwoormoresub-issues,therebyreducingthecomputationcomplexityofSVMclassification.ExperimentalresultsindicatethattheimprovedalgorithmissuitableforprocessinglargenumberofobservationsandcaneffectivelyacceleratethespeedsofSVMlearningandclassifyingwhilekeepingtheclassificationprecision.Keywords：granularity；ientspace；SVM(supportvectormachine);classification;machinelearning粒度计算是信息处理的一种新的概念和计算范式[1]。目前,研究得较多且较成熟的一种粒度计算理论是商空间理论[2]。文献[2]提出了基于商空间的问题求解理论,商空间将问题表述成不同的粒度世界,进而进行相应的粒度计算。粒度计算的优点在于使对问题的解决摆脱了一些繁琐且非关键的过程，抓住问题的关键或本质，从适当的层次（粒度）来研究问题，最终可快速获得问题的精确解或近似解[3~5]。支持向量机（SVM）是由Vapnik[6]于20世纪90年代初提出的一种新的机器学习方法。SVM算法利用凸二次规划（quadraticprogramming，QP）、Mercer核、稀疏解和松弛向量等多项技术，具有结构简单、训练误差低和泛化能力好等优点，因而被广泛地应用于分类学习问题中。但是当样本规模较大时，SVM算法在二次寻优过程中需要存储核矩阵和进行大量矩阵运算，使得运算时间过长。目前，改进算法主要有Vapnik等人[7]提出的选块算法、Osuna等人[8]提出的分解算法、Platt[9]提出的序列最小最优化法(sequentialminimaloptimization，SMO)等。以上几种改进算法，虽然有效地改进了SVM分类速度，但仍是对原始样本集进行处理，也即一直是在较精的粒度上进行运算。基于问题求解的商空间理论用可用空间结构来表示样本的结构。本文依据这个理论,将商空间粒度计算应用于SVM分类,采用距离度量空间的手段来解决大规模样本集的SVM分类问题。据此,提出一种基于商空间理论的SVM分类算法（SVM-G），该算法用空间距离表示信息粒度,采用分层递阶的方法，由粗到精地处理样本点。实验表明，该算法对大样本集的分类能在保持训练精度的同时进一步提高训练和分类的速度，具有降低计算复杂度和空间复杂度、适于处理样本数较多的SVM分类问题等优点。1理论准备1.1商空间理论在实际问题求解过程中，随着求解问题的不同，需要不同粒度的世界描述。有时解决某一问题时，同时需要若干不同粒度的世界。商空间理论用三元组??(X,f,T)??描述一个问题。其中：??x??表示问题的论域；??f(?)??是论域属性；??T??是论域的结构，指论域??X??中各元素的相互关系。分析或求解问题??(X,f,T)??是指对论域??X??及其有关的结构、属性进行分析、研究。可以对??X??的大小粒度进行简化，产生一个新的较大粒度的论域??[X]??，那么把原问题??(X,f,T)??变成新的层次上的问题??([X],[f],[T])??，即从较粗粒度??[X]??去考察问题。1.1.1不同粒度世界的描述定义1设??X、Y??是两个集合，??X×Y??是??X??与??Y??的积集，??R??X×Y????。设????(x,y)∈X×Y??，有??(x,y)∈R??，则称??X??与??Y??有关系??R??,记为??xRy??。称??R??为??X×Y??上的一个关系。定义2????x∈X??，令??[x]={y|x~...
