[19]
中华人民共和国国家知识产权局
[12]发明专利申请公布说明书
[11]公开号CN 101127029A [43]公开日2008年2月20日
[21]申请号200710045242.2[22]申请日2007.08.24
[21]申请号200710045242.2
[71]申请人复旦大学
地址200433上海市邯郸路220号
[72]发明人李斌 池明旻 薛向阳 [74]专利代理机构上海正旦专利代理有限公司代理人陆飞 盛志范
[51]Int.CI.G06F 15/18 (2006.01)G06F 17/30 (2006.01)G06K 9/62 (2006.01)
权利要求书 2 页 说明书 8 页 附图 1 页
[54]发明名称
方法
[57]摘要
本发明属于统计机器学习技术领域，具体涉及
一种用于在大规模数据分类问题中训练SVM分类器
果，把具有相同标签的样本分别拟合成高斯模型，
作为训练的基本信息单元；然后根据K个高斯模型
建立K×K的核矩阵，并建立带约束的二次规划问题，
用数值方法求解之；最后利用该二次规划问题的解
得到分类器的决策函数，使用该决策函数对测试样
本进行预测。本发明方法对时间复杂度和空间复杂
度都大有降低；可广泛应用于多媒体信息检索、生
物信息识别、金融信息处理等领域。
200710045242.2权 利 要 求 书第1/2页
1.一种用于在大规模数据分类问题中训练SVA分类器的方法，其特征在于具体步
骤如下：
(1)训练样本的聚类
给定一个包含N＝N++N-个训练样本的集合其中N+表示正样本数，
N-表示负样本数，样本x i∈R D，其中D为输入空间的维数，标签y i∈{1，-1}；
在分类器的训练阶段，对N+个正样本和N-个负样本首先分别进行聚类，得到K+个
正集和K-个负集，共计K＝K++K-个集；然后，按照聚类结果的集标签，把具
有相同标签的样本拟合成高斯模型，这样，共得到K+个正样本高斯模型和K-个负样本高
斯模型，表示为C＝{(Θk，y k)}K k＝1，其中生成模型Θk＝(P k，μk，∑k)包含了第k个高斯模型的先验概率P k、均值μk、以及协方差矩阵∑k，y k则表示该高斯模型的标签；这里，作为
训练基本单元的高斯模型的先验概率按照如下公式计算：P k+＝N k+/N+，其中N k+表示正样
本中第k个高斯模型包含的样本数，N+表示正样本的总数；负样本高斯模型的先验概率
按照同样方法计算，即P k-＝N k-/N-；
(2)核矩阵的构建
使用步骤(1)中得到的K个高斯模型构建一个K×K的核矩阵，其中每个元素根据公
式(2)或公式(3)计算得到：
其中上标T表示矩阵或者向量的转置。
这里，σk(d)，σl(d)分别为高斯型协方差矩阵∑k和∑l的第d个对角线元素；
(3)目标函数的优化
使用步骤(2)中得到的核矩阵建立带约束的二次规划问题，即公式(9)，使用数值方法
求解该二次规划问题，得到系数αk，k＝1，...，K的值：
200710045242.2权 利 要 求 书 第2/2页
<0≤αk≤P k C，k＝1，...，K
(4)决策函数的建立
把从步骤(3)中得到的系数αk，k＝1，...，K，代入公式(10)，即可得到分类器的决策函数，使用该决策函数对测试样本X进行预测：
200710045242.2说 明 书第1/8页
用于在大规模数据分类问题中训练SVM分类器的方法
技术领域
本发明属于统计机器学习技术领域，具体涉及一种分类器的训练方法，主要解决大规模数据分类问题中快速有效地训练分类器的问题。
技术背景
随着计算机网络技术与存储设备的迅速发展，各应用领域的信息化程度不断提高，例如政府、企业、学校都在使用大规模数据库来管理与存储信息化数据。然而，除了简单地对数据进行管理与存储操作，人们更希望从这些海量的数据库中挖掘出一些有意义的规则或知识，例如门户网站希望自动对文档或图片进行分类。然而，在实际应用中，数据库中数据量通常是非常庞大的，其数量级通常会达到太字节(T B)以上，如果把所有样本都作为训练数据来训练分类器，其时空复杂性将无比巨大。
对于大规模数据的分类问题，国内外研究者已经做过大量工作，他们从不同角度提出了许多解决方案，比如：分解技术[16，12，17，3，13]通过将原有大规模分类器学习问题分解为较小的子问题进行迭代学习，每次只对一个工作子集进行训练，并利用该次训练的结果指导选择下一个工作子集用于训练；增量技术[2，8，14]每次仅读入一个样本，对分类器进行增量式更新；并行技术[4，9]一般使用集成方法，先把总体样本平分为多个样本子集，并把得到的样本子集作为独立的任务交给不同的处理器进行训练，最后把各处理器得到的结果通过某种技术合并为一个总的分类器；近似技术[7，15]则使用近似的计算公式降低原有算法的复杂性。以上这些技术需要对所有样本都进行训练，其复杂度难以降低。
还有一类技术通过在原数据集中选取代表点训练分类器，其思想在于使用一定的方式，在原有大规模数据集中选取小部分的代表性样本训练分类器，以达到降低训练样本数量的目的。较典型的方法包括：“主
动学习”[18]通过启发式地选取代表点；C B-S V M[22]通过层次化聚类选取类中心作为代表点；[19]选取聚类超球表面的样本作为代表点；
C V M[20]使用“核心集”作为代表点；[1，23]则选取聚类中心作为代表点。由于代表点的选取技术大多基于不同的假设，并不适合所有的应用场景，并且会丢失原数据集的统计信息。
经过大量观察以及实际应用，我们发现现有的针对大规模数据分类问题的分类器训练方法都在不同程度上存在以下一些局限性：(1)在训练阶段所需要的时间复杂性和空
200710045242.2说 明 书 第2/8页间复杂性极高；(2)丢失部分原数据集的统计信息；(3)基于较强的假设条件与前提条件；(4)对于硬件设备与资源的要求相当高；(5)算法实现非常复杂。
以上分析说明，如果用大规模训练样本进行训练，其时间复杂性必然会居高不下，即使通过各种优化与近似手段后，依然无法奏效；如果使用代表点技术，即基于一定的假设条件在原大规模数据中抽取一部分代表样本进行训练，又必定会丢失部分统计信息，影响分类器的性能。
如果有一种方法既能使样本数量减少，又能使原有的统计信息尽量不丢失，则可以达到在保持与现有分类器相似的分类准确率的条件下，显著降低训练阶段时空复杂性——本发明就是通过事先把训练样本聚类成高斯模型作为分类器训练的基本信息单元，从而达到既减少样本数量又能保持原有统计信息的目的；
同时，本发明设计出的一种兼容的核函数使训练阶段得到的支撑高斯模型可以直接用于测试阶段，线性组合成最终的分类器。
参考文献
[1]Boley，D.and Cao，D.，Training Support Vector Machine Using Adaptive Clustering，In Proc.of the SIAM Int’ Data Mining，2004.
[2]Cauwenberghs，G.and Poggio，T.，Incremental and Decremental Support Vector Machine L e a r n i n g，A d v a n c e d N e u r a l I n f o r m a t i o n P r o c e s s i n g S y s t e m s，2000，C a m b r i d g e，M A：M I T Press.
[3]Collobert，R.and Bengio，S.，SVMTorch：Support Vector Machines for Large-scale R e g r e s s i o n P r o b l e m s，J.o f M a c h i n e L e a r n i n g R e s e a r c h，2001，v o l.1，p p.143-160.
[4]Collobert，R.，Bengio，S.，and Bengio，Y.，A Parallel Mixture of SVMs for Very Large Scale P r o b l e m s，A d v a n c e d N e u r a l I n f o r m a t i o n P r o c e s s i n g S y s t e m s，2001，C a m b r i d g e，M A：M I T Press.
[5]Dempster，A.P.，Laird，N.M.，and Rubin，D.B.，Maximum Likelihood from Incomplete
D a t a v i a t h e
E M A l g o r i t h m，J o u r n a l o f t h e R o y a l S t a t i s t i c a l S o c i e t y，S e r i e s B (Methodological)，1977，vol.39，pp.1-38.
[6]Friedman，M.and Kandel，A.，Introduction to Pattern Recognition，chapter Distance Functions，pp.70-73，London，UK：Imperial College Press，1999.
[7]Fung，G.and Mangasarian，O.L.，Proximal Support Vector Machine Classifiers，In Proc.of t h e A C M S I G K D D I n t’l C o n f.o n K n o w l e d g e D i s c o v e r y a n d D a t a M i n i n g，2001，p p.77-86.
[8]Fung，G.and Mangasarian，O.L.，Incremental Support Vector Machine Classification，In Proc.of the SIAMInt’Data Mining，2002.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议