基于改进的支持向量机决策树电梯载重分类方法研究

（华中科技大学无锡研究院，江苏 无锡 214100）

SVM是机器学习中经典分类器之一，常被用于解决低维数据线性不可分问题，通过核函数将低维数据映射到高维空间，因此在模式识别、小样本等问题中，SVM有着不可比拟的优势。然而，SVM本身是一个二类分类器，对于多类分类问题，可以通过两种方法进行问题推广：①通过二次优化来描述整个问题；②将一个问题分成多个问题，如：1-a-1、1-a-r、DAGSVM以及SVMDT。

张先武等人分别详细阐述了1-a-1、1-a-r、DAGSVM的基本思路：1-a-1是通过投票方法决策，在票数相同的情况下，存在不可分区域；1-a-r将N类问题分成N个分类器，在分类过程，分类速度较快，但每次构造分类器都要将整个工作集作为训练样本，训练速度会变慢；DAGSVM是在1-a-1的基础上提出来的，在分类阶段只需要使用N-1个分类器，分类速度比1-a-1和1-a-r都要快，但该方法的泛化能力与有向无环图中的位置有关。Kumar和Jair Cervantes等人在传统SVM的基础上，提出使用DT算法在SVM决策边界上划分3个类节点，通过使用参数来确定数据属于哪类。Anish Jindal等人将SVMDT方法引入到工业能源分类问题中，准确率有了很大提高。然而引入来搭建树结构时存在一个问题，当树根节点出现分类误差时，误差会随着树的层数的增加而积累越多，最终分类结果与实际结果之间相差甚远。王道明和Shih-Wei Lin等人在此基础上提出了基于自变异粒子群（PSO）聚类的决策树SVM的算法，在每个SVM训练前针对每个子节点通过PSO聚类算法进行二分类划分，确定各子分类器的位置以及训练样本，该方法以增加训练样本时间来换取优良的分类性能。

虽然通过引入粒子群算法优化树结构，但仍然存在缺陷，PSO算法容易陷入局部最优。基于此本文引入模拟退火算法，既保障粒子群算法的全局寻优能力，也避免了粒子群算法易陷入局部最优，使得模型的训练效果达到最优。

1 支持向量机决策树

1．1 支持向量机

SVM是机器学习中较为常见的方法之一，被广泛应用于分类和回归问题，它的核心思想就是在正、负样本之间寻找最优分类超平面。

假设训练集样本为(xi, yi)，xi为第i 个样本数据，i = 1,2,...,I ，I为样本数，xi∈Rq(R为实数域，q为输入数据的维度)；yi为第i 个样本数据的类标签，yi∈{- 1 ,+1}。

当样本集线性不可分类时，引入松弛变量ξi(ξi>0)，i = 1,2,...,I ，利用式(1)和(2)求解最优分类面。

其约束条件为：

式中：C为惩罚因子，表示目标函数的损失情况；C越大，损失越大。

在以上基础上引入Lagrange函数L(w,b,a)为：

式中：a为Lagrange因子。

在低维空间，样本无法进行线性分类时，SVM通过核函数K(xi, xj)将样本数据xi从低维空间映射到高维空间进行线性分类，根据Mercer条件得到最优决策函数F(xi)：

式中：aj表示a的其中第j个解。

在本文中，选取高斯核函数K(xi, xj)为：

式中：σ为宽度参数，控制取值范围。

1．2 支持向量机决策树

SVMDT的核心思想是将多分类问题分解为多个二分类问题，通过比较不同类之间的欧氏距离进行分类，距离越大越容易分。将整个样本集有选择的分为正样本集和负样本集，分别记为C1和C2，N1和N2分别为C1和C2的类别个数；N=N1+N2为所有节点需要划分的总类别数；Zn表示第n类样本，n= 1,2,...,N；Zn的样本数为ln。分类器的建立过程如下：

（1）利用式(6)计算出N个类中每个类的样本中心An为：

式中：zu为Zn中第u个样本向量。

（2）同样计算出正、负样本集C1和C2的中心e1和e2，并利用式(7)计算C1、C2之间的欧氏距离为：

（3）利用式(8)计算正样本集中每个类的样本中心到正样本集中心e1的平均距离为，负样本集中每个类的样本中心到负样本集中心e2的平均距离为，如下式：

式中：Zn∈C1表示Zn是正样本集中的样本，则利用式(8)上式计算；否则利用式(8)下式计算。

（4）利用式(9)计算最大距离值d，以此来划分出类：

（5）重复上面2到4步，知道所有的类分出来为止。

2 粒子群优化的支持向量机决策树

SVMDT虽然缩短了训练和分类的时间，提高了分类精度，但在构建树结构时，若根节点出现分类错误，会顺着子节点的延续而往下积累，最终导致与实际结果相差很大。基于此，通过引入PSO聚类算法来优化树结构，可将数据集进行最优划分。

2．1 PSO 算法

PSO源于鸟群捕食行为的研究，核心思想是通过群体中个体之间的协作和信息共享来寻找最优解。PSO算法需要预设类簇个数，每个粒子代表各类簇的类中心，粒子Xi以及速度Vi如下:

式中：Cij表示第i个粒子所代表的第j个类中心。Vij表示第i个粒子第j类的速度。PSO算法具体流程如下：

（1）设定进化次数以及种群规模，初始粒子和速度。

（2）根据粒子适应度函数f计算每个粒子的适应度值，更新个体极值，如式(11)；

式中：je为类内离散度之和，N为类的个数，Pm属于Cij所在的类。

（3）寻找全局极值和全局极值位置。

（4）根据式(12)和式(13)更新粒子的位置及速度。

（5）若达到结束条件，则输出最优解位置；否则返回2。

2．2 PSO-SVMDT 算法

通过PSO将训练样本进行二分类，生成最优决策树以实现最大样本分离。基于PSO的SVMDT具体生成步骤如下：

Step1：将整个训练样本作为初始根节点，利用PSO算法将初始根节点划分为两类，形成两个子类点。

Step2：判断子节点是都包含一个类，若是转向Step4，否则跳至Step3。

Step3：调用PSO算法再将节点划分为两个子节点，跳回Step2。

Step4：节点为叶子节点，算法结束。

3 基于模拟退火的粒子群优化的支持向量机决策树

3．1 模拟退火算法的原理

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983年,S.Kirkpatrick等人成功地将退火思想引入组合优化领域。它是基于蒙特卡洛迭代求解策略的一种随机寻优算法[10]。具体算法如下：

Step1：初始化参数，如Metropolis步长因子、初始温度、终止温度、Boltzmann常数。

Step2：在当前解Xi和新的解Xi+1可接受度(P)定义如下：

式中：f表示目标方程。Δf=f(Xi+1) -f(Xi)；T是温度。依照min(P) >R[0,1]，则接受Xi+1。其中R[0,1]表示0到1之间的随机数。

式中：C表示0到1之间的衰减因子。如果满足收敛条件，则算法结束，否则返回Step2。

由于有退火温度T控制着最优值的优化问题，并且同时以e-Δf/T来接受解。

3．2 基于模拟退火的粒子群优化算法

算法的具体步骤如图1所示。

图1 SA-PSO算法流程图

4 实验验证与分析

4．1 实验数据选择

本文实验所用数据参数包括：时间、速度、电压、电流、频率以及当前楼层，由于电梯中使用变频控制，并且每台电梯在出厂后，运行速度曲线都是预设好的，而当前楼层只是显示电梯轿厢的位置，因此，通过可视化已有数据后发现不同载重下的电压不相同，如图2所示。

图2 不同载重时上升过程电压变化曲线

图3 不同载重时下降过程电压变化曲线

图2和图3中，共五种载重情况，0kg对应电梯空载情况，150kg对应电梯25%额定载重情况，275kg对应电梯50%额定载重情况（半载），380kg对应于电梯75%载重情况，550kg对应满载情况。

显然，不同载重情况可以通过变化曲线反映出来，因此可以通过分离不同电压变化情况来区分不同载重情况。选取处理好并已知载重情况的数据对本文所提出的改进分类算法进行验证。

4．2 实验仿真

本次仿真是在matlab软件下进行，电脑内存6G，CPU2.10GHz，操作系统Win10。测试样本中载重情况共五类：空载、轻载、半载、重载以及满载。本文通过对比基于粒子群算法(PSO)、模拟退火算法(SA)、遗传算法(GA)的分类精度，来验证本文所提方法在所测数据集中的分类效果。

本文所选用SVM核函数为高斯核函数，参数C=100，σ=10。PSO算法的c1=c2=1.5，粒子群的规模为20，迭代次数为300，SA初始温度设为900℃，终止温度设为0.001℃，衰减因子为0.85。将SA-PSO与GA、SA和PSO优化算法进行对比，结果如图4所示。

从图中可以发现，SA-PSO优化后的算法不仅收敛速度比其它三种优化算法的快，而且迭代次数也是四种算法中最少的，分类精度也高于其他算法，SA-PSO的收敛性能更好。实验结果如表1所示。

图4 PSO与SA-PSO的分类精度比较图

表1 不同改进算法分类结果比较

由于在实际电梯运行过程中，空载运行次数相比于其他四种载重情况的运行次数要多，因此，实验中以空载情况的分类正确率作为整个算法的分类精度。在表中可以发现，基于GA算法的分类精度比PSO优化算法要高，但训练时间比较长，基于SA算法的训练时间虽然最短，但分类精度较低。本文所提算法所耗时间较短，相比SA和PSO优化算法，分类精度有了较大的提高，这也证明了本文所提改进算法的可行性。

5 结语

本文基于粒子群算法寻找全局最优能力强以及易陷入局部最优的缺陷，提出了一种基于模拟退火的粒子群优化算法，相比一些传统的优化算法，在分类精度上有了一定的提高。