王小君

（深圳信息职业技术学院 深圳 518172）

1 引言

随着大数据时代的到来，用户的服务器，终端中存放的海量的历史数据，而且每天持续快速增长。数据分类作为最基本的数据挖掘基础［1］，将信息按照类别属性或者特征来对数据进行区别。数据感知系统（SIMP-DAS）［2］可协助用户解决杂乱无章数据中的敏感数据。其中，感知机由美国心理学家Rosenblatt于1957年首次提出［3］，使人脑所具备的学习功能在基于符号处理的数学模型中得到了一定程度的模拟，它的参数在迭代过程中不断修正，实现对训练数据集的正确分类及识别等功能。感知机是最早被设计并被实现的人工神经网络［4］，它在人工神经网络的发展史上具有重要的地位，目前在模式识别［5］、数据挖掘［6］和线性系统控制［7］中都得到了广泛的成功应用。

数据分类感知机模型是定义在特征空间中所有线性分类模型（linear classification model）［8］或线性分类器（linear classifier）［9］，即函数集合，其学习策略是将损失函数最小化，损失函数是，表示误分类点到分离超平面的总距离，由误分类驱动，采用了随机梯度下降法［10］。该方法要求损失函数是参数的连续可导函数，这就限制了该迭代方法的应用范围。人工蜂群算法（ABC）［11］模拟蜜蜂的采蜜行为，实现信息的共享和交流，使得求出的分离超平面具有更好泛化能力，提高了分类和预测的精度。

本研究在整理了数据分类的感知机学习算法的基础上，重点分析了分离超平面的误分点的参数优化问题，通过引入人工蜂群算法（ABC）解决了数据分类感知机模型的损失函数在离散或连续时的通用性，使得改进后的数据分类感知机算法更加灵活、高效。

2 数据分类的感知机学习算法

感知机学习算法是对给定一个训练数据集：

其中，xi∈χ=Rn，yi∈Y={-1，1}，i=1，…，N ，求分离超平面：

其中，ω和b满足：

其中，M为误分类点的集合。相应的感知机模型为

该感知机模型能将特征空间Rn划分为两个部分，对应的点分别称为正、负类［12］。其算法步骤为

步骤1：选取初值ω0，b0；

步骤 2：对训练集中的样本点 (xi，yi)，如果yi(ω⋅xi+b)≤0，则对于任意的常数η，如下式恒成立：

步骤3：转至步骤2，直至训练集中没有误分类点。

这种算法直观上是当一个实例点被误分类，则调整ω，b的值，使分离超平面向该误分类点的一侧移动，直至超平面越过该误分类点使其被正确分类。

由于该算法要求损失函数是参数ω，b的连续可导函数，因此它所解决的是连续优化问题，这限制了该算法的适用范围。但人工蜂群算法的适应度函数不要求连续可导，对离散或连续的损失函数均适用，所以人工蜂群算法具有更广的应用范围。

3 人工蜂群算法（ABC）

人工蜂群算法是模拟蜜蜂采蜜的过程（即寻找高浓度的蜜源），其类似于搜索待求解问题最优解的过程［13］。传统的ABC算法包括采蜜蜂、观察蜂和侦察蜂三种不同功能的蜜蜂。采蜜蜂利用已有记忆中的食物源信息寻找新的食物源，并进行更新。若新食物源优于原食物源则将蜜源信息通过摇摆舞的方式传递给观察蜂，观察蜂在蜂房中通过观察采蜜蜂摇摆舞的持续时间判断食物源的浓度和位置，通过评估所有采蜜蜂的蜜源信息，根据轮盘赌法则［14］对已有最优食物源进行更新。若某个食物源经过预设L次循环之后没有得到改善，那么这个食物源就要被放弃，与这个食物源相应的采蜜蜂转变为侦察蜂，随机产生新的食物源。整个蜂群的目标是寻找花蜜浓度最大的食物源。

假设问题是在n维空间求解的，蜂群规模设置为NP，一个可行解对应一个食物源的位置，适应度函数视为食物源浓度并决定着整个算法的迭代方向［15］，整个采蜜过程相当于最优解的搜索过程。

本文在感知机算法的基础上引入蜂群算法，分类损失函数反映误分类点的个数，目标是使得误分类点的个数达到最少。为了能够使用蜂群算法求出感知机，需要对感知机模型作一个变形。

在感知机模型中令原感知机模型（4）变为

相应的损失函数如下修改：

1）如果 (xi，yi)是误分类点，则此时表达式表示(xi，yi)是一个误分类点。

2） 如 果 (xi，yi) 是 一 个 正 确 分 类 点 ，则此表达式表示(xi，yi)是一个正确分类点。

计算误分类点的个数为

因感知机的损失函数要求是误分类点的个数最少，所以感知机迭代就是极小化损失函数，即

从上式可以看出：误分类点越少，误分类点离超平面就越近，损失函数值就越小，直至所有的误分类点被正确分类。由于蜂群算法的适应度函数是求极大，寻找食物浓度最大的食物源，而感知机模型是使得误分类点数最少，即L(ω*)。为与蜂群算法吻合，在极小化前面加上一个负号，就变成极大，作为蜂群算法的适应度函数，即

算法中一个采蜜蜂与一个食物源是相对应的，与第i个食物源相对应的采蜜蜂和观察蜂在以为中心，为最大半径的范围内进行邻域搜索，搜索公式如下

其中，i=1，…，NP ，d=1，…，n，k≠i，表示第i个食物源的第d个分量，为记忆中随机选取的第k个食物源的第d个分量，n为待优化参数的个数，ϕid是区间[-1，1]上的随机数用于控制搜索的范围。

ABC算法将新生成的可能解代入适应度函数 fit(w*)计算新食物源的浓度，将其与原来的食物源作比较，并采用贪婪选择策略保留较好的食物源。每一个观察蜂根据轮盘赌法随机选择食物源，令

其中，Pi是用轮盘赌法随机选择食物源的概率。对于被选择的食物源，观察蜂根据上面概率公式搜寻新的可能解。当所有的采蜜蜂和观察蜂都搜索完整个搜索空间时，如果一个食物源的适应值在给定的步骤内（定义为控制参数“L”）没有被提高，则丢弃该食物源，而与该食物源相对应的采蜜蜂变成侦查蜂，侦查蜂基于以前记忆中食物源的信息通过以下公式生成新的食物源［16］：

其中，r是区间[0，1]上的随机数是第n维的下界和上界，r保证了新生成食物源范围在原记忆中最优和最差食物源之间。

4 蜂群感知机算法的步骤

步骤1：初始化控制参数，随机生成食物源的初始值。设蜂群规模为NP，循环次数为L，最大迭代步数为maxcycle，当前迭代步数iter，算法跳出循环标准criter；

步骤2：计算每个食物源的适应度函数值fitness。记最大适应度所对应的食物源为GlobalParams和最优解为GlobalMin；

步骤3：采蜜蜂根据搜索更新法则更新食物源，并计算相应的适应度函数值。如果新食物源的适应度函数值大于原食物源，则用新食物源代替原食物源，否则不变。

步骤4：观察蜂根据采蜜蜂所提供的信息，根据轮盘赌法则更新被选中的食物源。

步骤5：更新最大适应度所对应的食物源GlobalParams和最优解GlobalMin。

步骤6：确定侦察蜂。若经过有限的循环次数L之后，某食物源没有得到更新，则放弃该食物源，同时该食物源所对应的采蜜蜂转变为侦察蜂产生新的食物源。

步骤7：若食物源一直没有得到更新的循环步数小于 criter，且iter＜maxcycle，iter=iter+1，返回步骤2；否则，跳出循环，保存全局最优解，停止。

5 检验算例

本文设置蜂群规模为200，食物源更新控制参数L=50，最大迭代步数maxcycle=10000以及跳出循环条件criter=200，对实例数据和模拟数据进行检验，考察本文算法的有效性。

5.1 汽车引擎分类实例数据检验

采集 Ghanaati［17］所做的两种引擎类型（ET）y的分类数据，汽车的样本容量为38，体现引擎类型燃料效率包含7个指标，分别为英里每加仑（MPG）x1、加仑每百英里（GPM）x2、汽车重量（WT）x3、立方英寸（DIS）x4、缸数（NC）x5、马力（HP）x6和加速度（ACC）x7。将38个样本数据分为两个相等的部分，前19个样本数据作为训练数据集，后19个样本数据作为测试数据集。

运用两种算法得出的超平面对测试集的分类准确率均为84.21%，无显著差异。因此调整蜂群规模为400，跳出循环条件值也为400，所学习的分离超平面为

相应的蜂群感知机模型为

利用传统的感知机模型和蜂群感知机模型对19个样本测试集进行检验，检验的结果如表1所示。

从表1可以看出，蜂群感知机的分类准确率89.47%高于传统感知机的分类准确率84.21%，说明本文算法更加灵活，高效。

5.2 模拟数据分类检验

我们在[-1，1]随机生成样本容量为200的一组数据，取前100个样本作为训练集，后100个样本作为测试集，对训练集分别运用人工蜂群算法和感知机的随机梯度下降算法学习分类超平面，分别对测试集分类，分类准确率的结果如表2所示。

表1 算法对测试集的检验结果表

表2 模拟数据分类效率比较

为进一步说明本文算法得出超平面的分类效率，用同样的方法随机生成100次样本容量为200的线性可分的二分类数据集，其中任选100个数据作为样本训练集，剩余100个数据作为测试集，分别用感知机模型和蜂群感知机模型对测试集分类，测试结果如表3所示。

表3 算法对不同模拟数据测试集的分类

在100次模拟中，平均有79次人工蜂群算法优于感知机的随机梯度下降算法。这说明我们解决二分类的算法在处理模拟数据时优于感知机的随机梯度下降算法。

6 结语

本文提出一种基于人工蜂群的感知机算法对于分类精度有明显提高，说明蜂群感知机算法优于传统的感知机算法，且更加灵活、高效。由于感知机是支持向量机的基础，可以用蜂群算法求支持向量机的分离超平面，有广阔的应用前景。

［1］毛国君，胡殿军，谢松燕.基于分布式数据流的大数据分类模型和算法［J］.计算机学报，2017，40（1）：161-175.MAO Guojun，HU Dianjun，XIE Songyan.Large data classification model and algorithm based on distributed data stream［J］.Journal of Computer Science，2017，40（1）：161-175.

［2］于瑞云，周岩.参与式感知系统中基于压缩感知的数据采集算法［J］.东北大学学报（自然科学版），2015，36（2）：194-198.YU Ruiyun，ZHOU Yan.Data compression algorithm based on compressed sensing in participatory sensing system［J］.Journal of Northeastern University（Natural Science Edition），2015，36（2）：194-198.

［3］杨戈，张威强，黄静.一个感知机神经网络字符识别器的实现［J］.电子技术应用，2015，41（3）：120-122，129.YANG Ge，ZHANG Weiqiang，HUANG Jing.Implementation of a perceptron neural network character recognizer［J］.Application of electronic technology，2015，41（3）：120-122，129.

［4］曾晓勤，何嘉晟.单隐层感知机神经网络对权扰动的敏感性计算［J］.河海大学学报（自然科学版），2013，41（4）：360-364.ZENG Xiaoqing，HE Jiasheng.Sensitivity calculation of single hidden layer perceptron neural network to weight disturbance［J］.Journal of Hohai University（Natural Science Edition），2013，41（4）：360-364.

［5］吴建宁，徐海东，凌雲.基于块稀疏贝叶斯学习的人体运 动 模 式 识 别［J］.计 算 机 应 用 ，2016，36（4）：1039-1044.WU Jianning，XU Haidong，LIN Yun.Human motion pattern recognition based on block sparse Bayesian learning［J］.Computer application，2016，36（4）：1039-1044.

［6］李良，邱晓彤，赵强.基于数据挖掘的IPTV QoE评价方法［J］.华中科技大学学报（自然科学版），2016，44（11）：48-52.LI Liang，QIU Xiaotong，ZHAO Qiang.IPTV QoE evaluation method based on Data Mining［J］.Journal of Huazhong University of Science and Technology（Natural Science Edition），2016，44（11）：48-52.

［7］郭振雄，陈玉叶，肖可.一种基于非线性系统的动态感知系数的自适应PSO算法［J］.厦门大学学报（自然科学版），2017（5）：1-15.GUO Zhenxiong，CHEN Yuye，XIAO Ke.An adaptive PSO algorithm for dynamic perceptual coefficients based on Nonlinear Systems［J］.Journal of Xiamen University（Natural Science Edition），2017（5）：1-15.

［8］黄骥，许威威，刘复昌.基于核线性分类分析的三维模型检索算法［J］.微型机与应用，2016，35（15）：24-27.HUANG Ji，XU Weiwei，LIU Fuchang.A 3D model retrieval algorithm based on kernel linear classification analysis［J］.Microcomputer and Application，2016，35（15）：24-27.

［9］朱静雯，向仕兵.常用线性分类器算法及基于Mathematica三维可视化［J］.现代计算机（专业版），2017（7）：14-19.ZHU Jingwen，XIANG Shibing.Commonly used linear classifier algorithm and 3D visualization based on Mathematica［J］.Modern computer（Professional Edition），2017（7）：14-19.

［10］史苇杭，林楠.一种联合的时序数据特征序列分类学习算法［J］.计算机工程，2016，42（6）：196-200，207.SHI Weihang，LIN Nan.A combined sequential data classification algorithm for feature sequences［J］.Computer Engineering，2016，42（6）：196-200，207.

［11］鲁建厦，翁耀炜，李修琳.混合人工蜂群算法在混流装配线排序中的应用［J］.计算机集成制造系统，2014，20（1）：121-127.LU Jiansha，WEN Yaowei，LI Xiulin.Application of hybrid artificial bee colony algorithm to scheduling of mixed model assembly lines［J］.Computer integrated manufacturing system，2014，20（1）：121-127.

［12］华却才让，姜文斌，赵海兴.基于感知机模型藏文命名实体识别［J］.计算机工程与应用，2014（15）：172-176.HUAQUE Cairang，JIANG Wenbing，ZHAO Haixing.Tibetan named entity recognition based on perceptron model［J］.Computer engineering and Applications，2014（15）：172-176.

［13］秦全德，程适，李丽.人工蜂群算法研究综述［J］.智能系统学报，2014，9（2）：127-135.QIN Quande，CHENG Shi，LI Li.A survey of artificial bee colony algorithm［J］.Journal of Intelligent Systems，2014，9（2）：127-135.

［14］许烁，王阳，孙成恺.模块化可重构服务机器人群的任务规划［J］.电子学报，2016，44（1）：101-109.XU Shuo，WANG Yang，SUN Chengkai.Task planning for a modular reconfigurable service machine population［J］.Journal of Electronics，2016，44（1）：101-109.

［15］喻金平，郑杰，梅宏标.基于改进人工蜂群算法的K均值 聚 类 算 法［J］.计 算 机 应 用 ，2014，34（4）：1065-1069，1088.YU Jinping，ZHENG Jie，MEI Hongbiao.K mean clustering algorithm based on improved artificial bee colony algorithm［J］.Computer application，2014，34（4）：1065-1069，1088.

［16］周长喜，毛力，吴滨.基于当前最优解的人工蜂群算法［J］.计算机工程，2015，41（6）：147-151.ZHOU Changxi，MAO Li，WU Bing.Artificial bee colony algorithm based on current optimal solution［J］.Computer Engineering，2015，41（6）：147-151.

［17］Ghanaati A，Said M F M，Darus I Z M.Comparative analysis of different engine operating parameters for on-board fuel octane number classification［J］.Applied Thermal Engineering，2017，124：327-336.