基于多类支持向量机的多准则库存分类研究

肖智，王明恺，谢林林重庆大学经济与工商管理学院（400030）E-mail:[e-mail]摘要：本文将多类支持向量机方法引入到多准则库存分类中，提出了一种可以较为准确地预测库存产品类别的方法。这种方法的优点是模型中的参数较少，对于样本数据的分布和数量要求并不严格，并且能够寻找到全局最优解。给出了多类支持向量机的训练和测试流程。实例研究中，通过对不同总体样本分割比率进行了多组实验，寻找到泛化能力最好的一组来训练分类器，得到了最优的参数解。将预测结果与BP神经网络方法得到的结果进行了比较，表明了基于多类支持向量机的多准则库存分类预测方法可以得到更高的预测准确率，反映了将多类支持向量机方法应用在库存分类领域是可行的、有效的。关键词：多类支持向量机；多准则；库存管理；ABC分类1.引言ABC分类法是目前库存控制中应用最为广泛的一种库存分类方法，它的主要思想是重点管理少数价值高的物品，常采用以库存中单个品种的年库存资金使用量占整个库存资金的累计百分比进行排序。通常将项目排序前20%的库存品种划分为A类，控制年库存资金总使用量的80%；项目排序后50-60%构成C类，占用很少的库存资金；而两类之间的即为B类。一般地，对于A类进行紧缩的管理控制，而对于C类的控制相对较松一些，B类的控制处于它们之间。传统的ABC分类法仅仅考虑了单一的准则——年库存资金使用量，由于该方法简单易于实施，使其在企业中得到了广泛的运用。但是在今天多变的市场环境下，由于其只考虑了单一分类准则会引发许多问题，例如，提前期较长的C类产品和易于变质的A类产品对生产的干扰或者占有较大的库存量都可能会带来经济上的损失。近年来，国内外许多学者针对传统的单准则ABC分类法的弊端提出了多准则ABC分类法，考虑了更多的分类准则：提前期、订购需求、产品价格、订货费用、紧急程度、缺货的影响程度以及产品报废率等。当前被国内外学者广泛研究的多准则ABC分类方法有层次分析法[1-3]、模糊聚类[4]以及神经网络法[5-7]等。然而这些预测方法本身存在一定的局限性。运用层次分析法（AHP）方法时，需要大量的经验知识，对于主观判定依赖程度大，并且经常会产生判断矩阵的不一致性；模糊聚类（FCM）本质上是一种局部搜索优化算法，如果初始值选择不当，它就会收敛到局部极小点上；神经网络方法被文献[5]和文献[6]证实比AHP或者多元判别分析具有更高的分类准确率，但是它要求大量训练样本，输入节点也不能过多，同时易于陷入局部极小，具有过度适应数据的倾向，可能导致模型应用于新数据时迅速恶化，并且难以获得易于解释的输出结果。1本课题得到重庆市自然基金(CSTC.2004BB2183)资助。-1-支持向量机是最近发展起来的神经网络技术，但是它基于的是结构风险最小化原理，而不是经验风险最小化原理，避免了人工神经网络方法的过学习现象，能较好地解决非线性、小样本以及局部极小等学习问题。由于其出色的学习性能，已成为机器学习界的研究热点之一，它在分类以及回归等领域获得了良好的应用[8][9]。基于以上分析，本文提出了基于多类支持向量机的多准则库存产品分类方法，并且将实例结果与其他方法进行对比分析，以验证多类支持向量机方法在库存控制领域中的应用效果。2.多类支持向量机模型2.1基本的二类支持向量机支持向量机（SupoortVectorMachines,SVM）是建立在统计学习理论(SLT)的VC维理论和结构风险最小化原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力[10]。SVM方法的基本思想是：基于1909年Mercer核展开定理，通过非线性映射φ，把样本空间映射到一个高维乃至于无穷维的特征空间（又称Hilbert空间），使在特征空间中可以应用线性学习机的方法解决样本空间中的高度非线性分类和回归等问题。为了说明清楚原理，我们先考虑一个二类分类情况。假设训练样本集为{(x1,y1),(x2,y2),…,(xl,yl)}，其中xi∈Rn，yi{+1,∈-1}，i=1,2,…,l，其分类超平面定义如下：iiibxyξω−≥+⋅1)((1)其中是超平面上的点，ixω是超平面的法向量，是偏置量，也称为分类阀值（classificationthreshold），biξ为松弛变量，表示对错分样本的惩罚程度。在满足约束为式(1)的基础上，SVM解一个凸二次规划：Min⎥⎥⎦⎤⎢⎢⎣⎡+∑=liiC1221ξω(2)C是常数，用来控制对错分样本惩罚的程度，实现在错分样本数与模型复杂性之间的折衷，当取C值为零时对应的是线性可分情况。上面的二次规划可以通过其对偶问题解决：Max⎥⎥⎦⎤⎢⎢⎣⎡⋅−∑∑==ljijijijiliixxkyyaaa1,1)(21s.t.,01=∑=liiiya0≤≤C，i=1,2,…,l.(3)ia其中，为拉格朗日乘子（Lagrangemultiplier），是满足Mercer条件的核函数，根据最优理论中的KKT条件，只有少量样本的值不为零（决策函数值等于1的样本和错分样本），它们就是支持向量（SupportVector,SV）。ia),(jixxkia±核形式的决策函数为：-2-(x)=i=1,2,…,N为支持向量(4)))((1bxxkyaSgnNiiii+⋅∑=最优分类超平面的法向量为：∑==liiiixya1ω(5)2.2多类支持向量机SVM一开始为二类分类设计，但是大多数识别问题涉及的都是多类，所以这就要求将SVM方法扩展到多类识别中。通常多类识别的方法有“一对一”策略和“一对多”策略[11][12]。两种策略的基本思想都是把多类问题约简为二类问题集，从而便于基本SVM方法的应用，但在细节上，两种方法各不相同。1)在“一对一”（one-against-one）策略中，一系列的分类器被应用到每一类，对n个类别共需构造n(n-1)/2个分类器，每个分类器的训练样本是相关的两个类。在测试时，采取“最赢策略”（max-win）将测试样本x输入到关于i,j(i,j=1,…,n;i≠j)两类训练得到的分类器中，如果根据决策输出推测x分布在第i类中，则它属于第i类的票数就增加1，否则属于第j类的票数增加1，最后测试样本x被预测到所得票数最多的类中。2)在“一对多”（one-against-all）策略中，对n个类别仅需要构造n个支持向量机，每一个支持向量机分别将某一类的数据从其他类别中分离开来。在测试时，取决策函数输出值最大的类别为测试样本的类别。此外，通过将多个分类面的参数求解合到一个最优化问题中，然后求解该最优化问题“一次性”地实现多类分类，也是方法之一。不过该方法尽管看起来简洁，但是在最优化问题求解过程中的变量远远多于上述两类方法，训练速度也不及它们，而且在分类精度上也不占优。当训练样本数非常大时，这一问题更加突出。因此，该方法很少使用。3.基于多类支持向量机的多准则库存分类方法基本的支持向量机用于分类时，需要根据具体的研究对象构造指标体系，指标体系由一系列影响研究对象的因素或者准则构成，因素或准则之间可设置为递进层级结构。指标体系就构成了研究对象样本所处的特征空间。然后在特征空间内，结合指标体系定义研究所需的超平面。在由研究对象样本数据构成的特征空间中，选取距离超平面最近的样本，它们就是所谓的“支持向量”，分类方法的基础是由这些支持向量建立的决策规则。最后，把预测样本作为输入数据输入到模型中，输出的是由决策规则得到的计算值，它们使预测样本位于超平面不同的方向（左侧或者右侧），按照事先设定的标准，对预测样本进行分类，根据不同的预定目的做出决策方案。本文利用“一对一”的多类判别策略处理ABC库存分类问题，涉及三类样本：A类产品、B类产品和C类产品，多类系统的训练过程和测试过程分别如图1和图2所示。-3-数据来源为了验证多类支持向量机在多准则库存分类应用中的效果，本文使用文献[13]中的实际数据进行了实例分析。实例中，库存产品基于4个准则进行描述，依次为单位价格($/unit)、年资金使用量($/year)、关键因子以及提前期(weeks,1-7)，其中关键因子为离散型数据（1代表非常关键；0.01代表非常不关键；0.50代表中等关键）。库存产品的类别是由AHP加权方法得到的，尽管AHP方法依赖于主观因素，但是在这样的环境下可以最大限度地降低主观因素的影响：负责库存项目管理的公司管理者熟悉库存控制方法及流程，并且具有最终决定权[1][5][13]。经由这样的公司管理者对少量典型的库存产品打分后运用AHP方法得到的分类结果就比较符合实际，这也是本文采用这种方法收集原始数据进行库存分类研究的原因所在，通过比较真实的原始数据达到更好的预测效果。数据样本共47个，其中A类库存产品样本10个，B类库存产品样本14个，C类库存产品样本23个。在运用多类支持向量机分类前，将总体样本分为两部分，一部分是训练样本集，另一部分是测试样本集。4.2数据预处理为了防止具有较大初始域的准则相对于具有较小初始域的权重过大而影响预测效果，本文对样本数据进行了预处理和规范化，将相应的指标正规化到[-1,1]的区间内：1)min()max()min(2~−−−=pppppii(6)-4-过程与结果分析在总体样本中，A类与C类以及B类与C类的库存产品样本数差异是明显的，这是一种不平衡的现象，但是可以在训练过程中对不同的类设定不同的权重来获得平衡，不至于使分类器“过学习”[14]。此外，使各类样本的分布尽可能均匀，这样将更有利于选择更好的支持向量机参数，以便找到性能最好的分类器。为了寻找性能优良的分类器，本文选择文献[15]的方法将总体样本按照不同的分割比率得到不同的训练样本集和测试样本集，在不同的分割比率下进行了多次实验。其中，选择径向基函数（RadialBasisFunction,RBF）作为支持向量机的核函数（k(xi,xj)=exp(-γ||xi-xj||2)），采用的支持向量机是由Chih-ChungChang和Chih-JenLin构造的libsvm（version2.6）[16]。PC机配置为IntelPentiumⅢ处理器，内存256Mb(548Mhz)。在不同总体样本分割比率情况下，获得的分类正确率如表1所示。表1不同总体样本分割比率下的分类正确率ratioTrainingacuuracyPredictiveaccuracyCross-validationaccuracyAverageaccuracy20%50.00%51.35%40.00%47.12%30%100.00%84.85%64.29%83.05%40%100.00%67.86%73.68%80.51%50%83.33%73.91%79.17%78.80%55%84.62%71.43%80.77%78.94%60%92.86%73.68%82.14%82.89%65%100%87.50%83.87%90.46%70%87.88%78.57%75.76%80.74%83%92.31%100.00%76.92%89.74%90%95.24%60.00%78.57%77.94%注：ratio为总体样本的分割比率，且ratio=训练样本数÷总体样本数，以下同。在表1中，有四种分类正确率，分别为训练正确率、预测正确率、交叉检验正确率和平均正确率，其中交叉检验正确率是在训练过程中将训练样本分割成几部分进行交叉检验获得的分类正确率，本文采用的是5-flod交叉检验。从上表中总体上可以看出，分类正确率与总体样本分割比率并不成正比关系，也不同方向变动。总体样本分割比率为30%和40%时，训练正确率都为100%