王小君

（深圳信息職業(yè)技術(shù)學(xué)院 深圳 518172）

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，用戶的服務(wù)器，終端中存放的海量的歷史數(shù)據(jù)，而且每天持續(xù)快速增長。數(shù)據(jù)分類作為最基本的數(shù)據(jù)挖掘基礎(chǔ)［1］，將信息按照類別屬性或者特征來對(duì)數(shù)據(jù)進(jìn)行區(qū)別。數(shù)據(jù)感知系統(tǒng)（SIMP-DAS）［2］可協(xié)助用戶解決雜亂無章數(shù)據(jù)中的敏感數(shù)據(jù)。其中，感知機(jī)由美國心理學(xué)家Rosenblatt于1957年首次提出［3］，使人腦所具備的學(xué)習(xí)功能在基于符號(hào)處理的數(shù)學(xué)模型中得到了一定程度的模擬，它的參數(shù)在迭代過程中不斷修正，實(shí)現(xiàn)對(duì)訓(xùn)練數(shù)據(jù)集的正確分類及識(shí)別等功能。感知機(jī)是最早被設(shè)計(jì)并被實(shí)現(xiàn)的人工神經(jīng)網(wǎng)絡(luò)［4］，它在人工神經(jīng)網(wǎng)絡(luò)的發(fā)展史上具有重要的地位，目前在模式識(shí)別［5］、數(shù)據(jù)挖掘［6］和線性系統(tǒng)控制［7］中都得到了廣泛的成功應(yīng)用。

數(shù)據(jù)分類感知機(jī)模型是定義在特征空間中所有線性分類模型（linear classification model）［8］或線性分類器（linear classifier）［9］，即函數(shù)集合，其學(xué)習(xí)策略是將損失函數(shù)最小化，損失函數(shù)是，表示誤分類點(diǎn)到分離超平面的總距離，由誤分類驅(qū)動(dòng)，采用了隨機(jī)梯度下降法［10］。該方法要求損失函數(shù)是參數(shù)的連續(xù)可導(dǎo)函數(shù)，這就限制了該迭代方法的應(yīng)用范圍。人工蜂群算法（ABC）［11］模擬蜜蜂的采蜜行為，實(shí)現(xiàn)信息的共享和交流，使得求出的分離超平面具有更好泛化能力，提高了分類和預(yù)測(cè)的精度。

本研究在整理了數(shù)據(jù)分類的感知機(jī)學(xué)習(xí)算法的基礎(chǔ)上，重點(diǎn)分析了分離超平面的誤分點(diǎn)的參數(shù)優(yōu)化問題，通過引入人工蜂群算法（ABC）解決了數(shù)據(jù)分類感知機(jī)模型的損失函數(shù)在離散或連續(xù)時(shí)的通用性，使得改進(jìn)后的數(shù)據(jù)分類感知機(jī)算法更加靈活、高效。

2 數(shù)據(jù)分類的感知機(jī)學(xué)習(xí)算法

感知機(jī)學(xué)習(xí)算法是對(duì)給定一個(gè)訓(xùn)練數(shù)據(jù)集：

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

其中，ω和b滿足：

其中，M為誤分類點(diǎn)的集合。相應(yīng)的感知機(jī)模型為

該感知機(jī)模型能將特征空間Rn劃分為兩個(gè)部分，對(duì)應(yīng)的點(diǎn)分別稱為正、負(fù)類［12］。其算法步驟為

步驟1：選取初值ω0，b0；

步驟 2：對(duì)訓(xùn)練集中的樣本點(diǎn) (xi，yi)，如果yi(ω?xi+b)≤0，則對(duì)于任意的常數(shù)η，如下式恒成立：

步驟3：轉(zhuǎn)至步驟2，直至訓(xùn)練集中沒有誤分類點(diǎn)。

這種算法直觀上是當(dāng)一個(gè)實(shí)例點(diǎn)被誤分類，則調(diào)整ω，b的值，使分離超平面向該誤分類點(diǎn)的一側(cè)移動(dòng)，直至超平面越過該誤分類點(diǎn)使其被正確分類。

由于該算法要求損失函數(shù)是參數(shù)ω，b的連續(xù)可導(dǎo)函數(shù)，因此它所解決的是連續(xù)優(yōu)化問題，這限制了該算法的適用范圍。但人工蜂群算法的適應(yīng)度函數(shù)不要求連續(xù)可導(dǎo)，對(duì)離散或連續(xù)的損失函數(shù)均適用，所以人工蜂群算法具有更廣的應(yīng)用范圍。

3 人工蜂群算法（ABC）

人工蜂群算法是模擬蜜蜂采蜜的過程（即尋找高濃度的蜜源），其類似于搜索待求解問題最優(yōu)解的過程［13］。傳統(tǒng)的ABC算法包括采蜜蜂、觀察蜂和偵察蜂三種不同功能的蜜蜂。采蜜蜂利用已有記憶中的食物源信息尋找新的食物源，并進(jìn)行更新。若新食物源優(yōu)于原食物源則將蜜源信息通過搖擺舞的方式傳遞給觀察蜂，觀察蜂在蜂房中通過觀察采蜜蜂搖擺舞的持續(xù)時(shí)間判斷食物源的濃度和位置，通過評(píng)估所有采蜜蜂的蜜源信息，根據(jù)輪盤賭法則［14］對(duì)已有最優(yōu)食物源進(jìn)行更新。若某個(gè)食物源經(jīng)過預(yù)設(shè)L次循環(huán)之后沒有得到改善，那么這個(gè)食物源就要被放棄，與這個(gè)食物源相應(yīng)的采蜜蜂轉(zhuǎn)變?yōu)閭刹旆?，隨機(jī)產(chǎn)生新的食物源。整個(gè)蜂群的目標(biāo)是尋找花蜜濃度最大的食物源。

假設(shè)問題是在n維空間求解的，蜂群規(guī)模設(shè)置為NP，一個(gè)可行解對(duì)應(yīng)一個(gè)食物源的位置，適應(yīng)度函數(shù)視為食物源濃度并決定著整個(gè)算法的迭代方向［15］，整個(gè)采蜜過程相當(dāng)于最優(yōu)解的搜索過程。

本文在感知機(jī)算法的基礎(chǔ)上引入蜂群算法，分類損失函數(shù)反映誤分類點(diǎn)的個(gè)數(shù)，目標(biāo)是使得誤分類點(diǎn)的個(gè)數(shù)達(dá)到最少。為了能夠使用蜂群算法求出感知機(jī)，需要對(duì)感知機(jī)模型作一個(gè)變形。

在感知機(jī)模型中令原感知機(jī)模型（4）變?yōu)?/p>

相應(yīng)的損失函數(shù)如下修改：

1）如果 (xi，yi)是誤分類點(diǎn)，則此時(shí)表達(dá)式表示(xi，yi)是一個(gè)誤分類點(diǎn)。

2） 如 果 (xi，yi) 是 一 個(gè) 正 確 分 類 點(diǎn) ，則此表達(dá)式表示(xi，yi)是一個(gè)正確分類點(diǎn)。

計(jì)算誤分類點(diǎn)的個(gè)數(shù)為

因感知機(jī)的損失函數(shù)要求是誤分類點(diǎn)的個(gè)數(shù)最少，所以感知機(jī)迭代就是極小化損失函數(shù)，即

從上式可以看出：誤分類點(diǎn)越少，誤分類點(diǎn)離超平面就越近，損失函數(shù)值就越小，直至所有的誤分類點(diǎn)被正確分類。由于蜂群算法的適應(yīng)度函數(shù)是求極大，尋找食物濃度最大的食物源，而感知機(jī)模型是使得誤分類點(diǎn)數(shù)最少，即L(ω*)。為與蜂群算法吻合，在極小化前面加上一個(gè)負(fù)號(hào)，就變成極大，作為蜂群算法的適應(yīng)度函數(shù)，即

算法中一個(gè)采蜜蜂與一個(gè)食物源是相對(duì)應(yīng)的，與第i個(gè)食物源相對(duì)應(yīng)的采蜜蜂和觀察蜂在以為中心，為最大半徑的范圍內(nèi)進(jìn)行鄰域搜索，搜索公式如下

其中，i=1，…，NP ，d=1，…，n，k≠i，表示第i個(gè)食物源的第d個(gè)分量，為記憶中隨機(jī)選取的第k個(gè)食物源的第d個(gè)分量，n為待優(yōu)化參數(shù)的個(gè)數(shù)，?id是區(qū)間[-1，1]上的隨機(jī)數(shù)用于控制搜索的范圍。

ABC算法將新生成的可能解代入適應(yīng)度函數(shù) fit(w*)計(jì)算新食物源的濃度，將其與原來的食物源作比較，并采用貪婪選擇策略保留較好的食物源。每一個(gè)觀察蜂根據(jù)輪盤賭法隨機(jī)選擇食物源，令

其中，Pi是用輪盤賭法隨機(jī)選擇食物源的概率。對(duì)于被選擇的食物源，觀察蜂根據(jù)上面概率公式搜尋新的可能解。當(dāng)所有的采蜜蜂和觀察蜂都搜索完整個(gè)搜索空間時(shí)，如果一個(gè)食物源的適應(yīng)值在給定的步驟內(nèi)（定義為控制參數(shù)“L”）沒有被提高，則丟棄該食物源，而與該食物源相對(duì)應(yīng)的采蜜蜂變成偵查蜂，偵查蜂基于以前記憶中食物源的信息通過以下公式生成新的食物源［16］：

其中，r是區(qū)間[0，1]上的隨機(jī)數(shù)是第n維的下界和上界，r保證了新生成食物源范圍在原記憶中最優(yōu)和最差食物源之間。

4 蜂群感知機(jī)算法的步驟

步驟1：初始化控制參數(shù)，隨機(jī)生成食物源的初始值。設(shè)蜂群規(guī)模為NP，循環(huán)次數(shù)為L，最大迭代步數(shù)為maxcycle，當(dāng)前迭代步數(shù)iter，算法跳出循環(huán)標(biāo)準(zhǔn)criter；

步驟2：計(jì)算每個(gè)食物源的適應(yīng)度函數(shù)值fitness。記最大適應(yīng)度所對(duì)應(yīng)的食物源為GlobalParams和最優(yōu)解為GlobalMin；

步驟3：采蜜蜂根據(jù)搜索更新法則更新食物源，并計(jì)算相應(yīng)的適應(yīng)度函數(shù)值。如果新食物源的適應(yīng)度函數(shù)值大于原食物源，則用新食物源代替原食物源，否則不變。

步驟4：觀察蜂根據(jù)采蜜蜂所提供的信息，根據(jù)輪盤賭法則更新被選中的食物源。

步驟5：更新最大適應(yīng)度所對(duì)應(yīng)的食物源GlobalParams和最優(yōu)解GlobalMin。

步驟6：確定偵察蜂。若經(jīng)過有限的循環(huán)次數(shù)L之后，某食物源沒有得到更新，則放棄該食物源，同時(shí)該食物源所對(duì)應(yīng)的采蜜蜂轉(zhuǎn)變?yōu)閭刹旆洚a(chǎn)生新的食物源。

步驟7：若食物源一直沒有得到更新的循環(huán)步數(shù)小于 criter，且iter＜maxcycle，iter=iter+1，返回步驟2；否則，跳出循環(huán)，保存全局最優(yōu)解，停止。

5 檢驗(yàn)算例

本文設(shè)置蜂群規(guī)模為200，食物源更新控制參數(shù)L=50，最大迭代步數(shù)maxcycle=10000以及跳出循環(huán)條件criter=200，對(duì)實(shí)例數(shù)據(jù)和模擬數(shù)據(jù)進(jìn)行檢驗(yàn)，考察本文算法的有效性。

5.1 汽車引擎分類實(shí)例數(shù)據(jù)檢驗(yàn)

采集 Ghanaati［17］所做的兩種引擎類型（ET）y的分類數(shù)據(jù)，汽車的樣本容量為38，體現(xiàn)引擎類型燃料效率包含7個(gè)指標(biāo)，分別為英里每加侖（MPG）x1、加侖每百英里（GPM）x2、汽車重量（WT）x3、立方英寸（DIS）x4、缸數(shù)（NC）x5、馬力（HP）x6和加速度（ACC）x7。將38個(gè)樣本數(shù)據(jù)分為兩個(gè)相等的部分，前19個(gè)樣本數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集，后19個(gè)樣本數(shù)據(jù)作為測(cè)試數(shù)據(jù)集。

運(yùn)用兩種算法得出的超平面對(duì)測(cè)試集的分類準(zhǔn)確率均為84.21%，無顯著差異。因此調(diào)整蜂群規(guī)模為400，跳出循環(huán)條件值也為400，所學(xué)習(xí)的分離超平面為

相應(yīng)的蜂群感知機(jī)模型為

利用傳統(tǒng)的感知機(jī)模型和蜂群感知機(jī)模型對(duì)19個(gè)樣本測(cè)試集進(jìn)行檢驗(yàn)，檢驗(yàn)的結(jié)果如表1所示。

從表1可以看出，蜂群感知機(jī)的分類準(zhǔn)確率89.47%高于傳統(tǒng)感知機(jī)的分類準(zhǔn)確率84.21%，說明本文算法更加靈活，高效。

5.2 模擬數(shù)據(jù)分類檢驗(yàn)

我們?cè)赱-1，1]隨機(jī)生成樣本容量為200的一組數(shù)據(jù)，取前100個(gè)樣本作為訓(xùn)練集，后100個(gè)樣本作為測(cè)試集，對(duì)訓(xùn)練集分別運(yùn)用人工蜂群算法和感知機(jī)的隨機(jī)梯度下降算法學(xué)習(xí)分類超平面，分別對(duì)測(cè)試集分類，分類準(zhǔn)確率的結(jié)果如表2所示。

表1 算法對(duì)測(cè)試集的檢驗(yàn)結(jié)果表

表2 模擬數(shù)據(jù)分類效率比較

為進(jìn)一步說明本文算法得出超平面的分類效率，用同樣的方法隨機(jī)生成100次樣本容量為200的線性可分的二分類數(shù)據(jù)集，其中任選100個(gè)數(shù)據(jù)作為樣本訓(xùn)練集，剩余100個(gè)數(shù)據(jù)作為測(cè)試集，分別用感知機(jī)模型和蜂群感知機(jī)模型對(duì)測(cè)試集分類，測(cè)試結(jié)果如表3所示。

表3 算法對(duì)不同模擬數(shù)據(jù)測(cè)試集的分類

在100次模擬中，平均有79次人工蜂群算法優(yōu)于感知機(jī)的隨機(jī)梯度下降算法。這說明我們解決二分類的算法在處理模擬數(shù)據(jù)時(shí)優(yōu)于感知機(jī)的隨機(jī)梯度下降算法。

6 結(jié)語

本文提出一種基于人工蜂群的感知機(jī)算法對(duì)于分類精度有明顯提高，說明蜂群感知機(jī)算法優(yōu)于傳統(tǒng)的感知機(jī)算法，且更加靈活、高效。由于感知機(jī)是支持向量機(jī)的基礎(chǔ)，可以用蜂群算法求支持向量機(jī)的分離超平面，有廣闊的應(yīng)用前景。

［1］毛國君，胡殿軍，謝松燕.基于分布式數(shù)據(jù)流的大數(shù)據(jù)分類模型和算法［J］.計(jì)算機(jī)學(xué)報(bào)，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］于瑞云，周巖.參與式感知系統(tǒng)中基于壓縮感知的數(shù)據(jù)采集算法［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），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］楊戈，張威強(qiáng)，黃靜.一個(gè)感知機(jī)神經(jīng)網(wǎng)絡(luò)字符識(shí)別器的實(shí)現(xiàn)［J］.電子技術(shù)應(yīng)用，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ī)神經(jīng)網(wǎng)絡(luò)對(duì)權(quán)擾動(dòng)的敏感性計(jì)算［J］.河海大學(xué)學(xué)報(bào)（自然科學(xué)版），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］吳建寧，徐海東，凌雲(yún).基于塊稀疏貝葉斯學(xué)習(xí)的人體運(yùn) 動(dòng) 模 式 識(shí) 別［J］.計(jì) 算 機(jī) 應(yīng) 用 ，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］李良，邱曉彤，趙強(qiáng).基于數(shù)據(jù)挖掘的IPTV QoE評(píng)價(jià)方法［J］.華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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］郭振雄，陳玉葉，肖可.一種基于非線性系統(tǒng)的動(dòng)態(tài)感知系數(shù)的自適應(yīng)PSO算法［J］.廈門大學(xué)學(xué)報(bào)（自然科學(xué)版），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］黃驥，許威威，劉復(fù)昌.基于核線性分類分析的三維模型檢索算法［J］.微型機(jī)與應(yīng)用，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］.現(xiàn)代計(jì)算機(jī)（專業(yè)版），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］史葦杭，林楠.一種聯(lián)合的時(shí)序數(shù)據(jù)特征序列分類學(xué)習(xí)算法［J］.計(jì)算機(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］魯建廈，翁耀煒，李修琳.混合人工蜂群算法在混流裝配線排序中的應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)，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ī)模型藏文命名實(shí)體識(shí)別［J］.計(jì)算機(jī)工程與應(yīng)用，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］.智能系統(tǒng)學(xué)報(bào)，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］許爍，王陽，孫成愷.模塊化可重構(gòu)服務(wù)機(jī)器人群的任務(wù)規(guī)劃［J］.電子學(xué)報(bào)，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］喻金平，鄭杰，梅宏標(biāo).基于改進(jìn)人工蜂群算法的K均值 聚 類 算 法［J］.計(jì) 算 機(jī) 應(yīng) 用 ，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］周長喜，毛力，吳濱.基于當(dāng)前最優(yōu)解的人工蜂群算法［J］.計(jì)算機(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.