面向海量樣本的線性可分支持向量機(jī)分組算法

馬捍超 沈杰鑫 徐路強(qiáng) 于海

摘 要：傳統(tǒng)線性可分支持向量機(jī)分組算法面對(duì)海量樣本進(jìn)行分組時(shí)，存在正確率較低的問(wèn)題，對(duì)此提出一種面向海量樣本的線性可分支持向量機(jī)分組算法。面向海量樣本給定一個(gè)樣本集，對(duì)其樣本集進(jìn)行特征提取，利用分值方法進(jìn)行樣本特征選擇，通過(guò)線性可分支持向量機(jī)進(jìn)行樣本聚類，并建立線性可分支持向量機(jī)分組框架，利用該框架實(shí)現(xiàn)樣本分組。為了驗(yàn)證面向海量樣本的線性可分支持向量機(jī)分組算法的樣本分組正確率，將該算法與傳統(tǒng)線性可分支持向量機(jī)分組算法進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果證明該算法的樣本分組正確率更高，說(shuō)明本研究所提算法更適用于海量樣本的分組。

關(guān)鍵詞：海量樣本;線性可分;支持向量機(jī);分組算法

中圖分類號(hào)：TP13

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-757X（2020）11-0082-04

Abstract：The traditional linear divisible support vector machine grouping algorithm has the problem of low accuracy when grouping mass samples. A mass sample set is given to be extracted， and the sample feature selection is performed by the score method. The sample clustering is carried out by the linear divisible support vector machine. In order to verify the sample grouping accuracy of the linear divisible support vector machine grouping algorithm for mass samples， the algorithm is supported with the traditional linearity. The results show that the proposed algorithm has more accuracy， which illustrates that the algorithm is more suitable for the mass sample set.

Key words：massive samples;linear separability;support vector machine;grouping algorithm

0?引言

信息技術(shù)與計(jì)算機(jī)技術(shù)的高速發(fā)展，使互聯(lián)網(wǎng)上流動(dòng)的資源與分布的內(nèi)容呈現(xiàn)出了多元化、海量化的膨脹趨勢(shì)，數(shù)據(jù)存儲(chǔ)技術(shù)與數(shù)據(jù)收集技術(shù)的迅速發(fā)展也使各種機(jī)構(gòu)組織能夠積累并獲取大量的數(shù)據(jù)。這些數(shù)據(jù)呈現(xiàn)出使用態(tài)、傳輸態(tài)以及靜態(tài)等多種狀態(tài)，既有正?？捎玫亩嘣獞?yīng)用數(shù)據(jù)，如政府、教育、醫(yī)學(xué)、市場(chǎng)、金融等行業(yè)數(shù)據(jù)及系統(tǒng)日志、安全策略、流量、即時(shí)通信、微博、新聞組、電子郵件、新聞等系統(tǒng)內(nèi)容資源，也有網(wǎng)絡(luò)經(jīng)濟(jì)犯罪、僵尸病毒網(wǎng)絡(luò)攻擊流、惡意軟件、個(gè)人隱私、欺詐廣告、垃圾郵件、色情網(wǎng)站、釣魚(yú)網(wǎng)站、虛假信息等影響國(guó)家重大利益、危害社會(huì)穩(wěn)定、誤導(dǎo)公眾、泄露敏感信息、影響資源以及信息可用性的內(nèi)容。對(duì)于正?？捎玫亩嘣獞?yīng)用數(shù)據(jù)，從信息數(shù)據(jù)的有效性、可用性角度，需要根據(jù)各個(gè)領(lǐng)域、不同行業(yè)的用戶需要，高效、快速的對(duì)有用的數(shù)據(jù)進(jìn)行分組，并對(duì)數(shù)據(jù)進(jìn)行提取、分析;而對(duì)于影響資源以及信息可用性的內(nèi)容，無(wú)論從內(nèi)容安全角度，還是從合法性、道德性、可用性、真實(shí)性等角度，都有必要對(duì)這些正在或即將泄露的不安全數(shù)據(jù)進(jìn)行分組，并對(duì)其進(jìn)行保護(hù)與檢測(cè)，對(duì)存在誘導(dǎo)、惡意、虛假的行為或內(nèi)容進(jìn)行分析、過(guò)濾、分組，能夠及時(shí)對(duì)攻擊源或受害者進(jìn)行定位，同時(shí)利用智能處理系統(tǒng)對(duì)知識(shí)進(jìn)行學(xué)習(xí)，并對(duì)數(shù)據(jù)進(jìn)行處理[1]。然而，在資源信息高度網(wǎng)絡(luò)化與數(shù)字化的今天，數(shù)據(jù)的分組仍然困難重重，不管是從內(nèi)容安全還是從數(shù)據(jù)管理角度，都需要對(duì)各種數(shù)據(jù)迅速進(jìn)行分組，以實(shí)現(xiàn)高效的信息安全保護(hù)，因此提出一種面向海量樣本的線性可分支持向量機(jī)分組算法[2]。

1?面向海量樣本的線性可分支持向量機(jī)分組算法

1.1?特征選擇

首先面向海量樣本進(jìn)行特征選擇：給定一個(gè)樣本集T，對(duì)其樣本集進(jìn)行特征提取，如式（1）。

利用分值方法對(duì)海量樣本進(jìn)行特征選擇。首先針對(duì)樣本集X進(jìn)行相似對(duì)應(yīng)矩陣的構(gòu)造，如式（2）。

根據(jù)分值方法的基礎(chǔ)理論[3]，分值矩陣，如式（3）。

完成殘差的獲取后，獨(dú)立看待各個(gè)特征，并對(duì)第i個(gè)特征的分值進(jìn)行定義，如式（8）。

設(shè)需要選擇的樣本數(shù)據(jù)特征的總體個(gè)數(shù)為d′，對(duì)每個(gè)數(shù)據(jù)特征的分值分別進(jìn)行計(jì)算，將各個(gè)數(shù)據(jù)特征對(duì)應(yīng)的分值依照由小到大的次序排列，從中挑選出d′個(gè)數(shù)據(jù)分值的相應(yīng)特征。具體的挑選方法如下。

首先輸入需要選擇的樣本數(shù)據(jù)特征的總體個(gè)數(shù)r與樣本集X，按照特征分值的定義公式計(jì)算出r個(gè)數(shù)據(jù)特征分值，分別記錄為S1，S2，…，Sr;對(duì)這些數(shù)據(jù)特征分值進(jìn)行排序：Sr（k1），Sr（k2），…，Sr（kn）;最后輸出r個(gè)數(shù)據(jù)分值相應(yīng)特征的特征因子S′，實(shí)現(xiàn)了面向海量樣本的特征選擇[4]。

1.2?樣本聚類

完成面向海量樣本的特征選擇后，利用線性可分支持向量機(jī)進(jìn)行樣本聚類。線性可分支持向量機(jī)的樣本聚類流程主要分為兩個(gè)階段：首先利用線性可分支持向量機(jī)的訓(xùn)練集對(duì)海量樣本的特征進(jìn)行聚類訓(xùn)練，從而構(gòu)建支持函數(shù);確認(rèn)線性可分支持向量機(jī)的超平面邊界長(zhǎng)度，在超平面邊界中進(jìn)行簇的標(biāo)定，也就是在海量樣本的特征中任選兩個(gè)作為樣本，對(duì)它們之間的線段實(shí)施采樣，并判斷數(shù)據(jù)集合中心與采樣點(diǎn)之間的距離，以對(duì)兩個(gè)樣本進(jìn)行簇的分類，判斷其是否屬于相同的簇[5]。

樣本聚類的實(shí)施涉及到簇的標(biāo)定、對(duì)偶問(wèn)題的求解以及參數(shù)的選擇等，具體實(shí)施步驟如下：利用線性可分支持向量機(jī)的訓(xùn)練集對(duì)海量樣本的特征進(jìn)行聚類訓(xùn)練首先需要對(duì)數(shù)據(jù)特征樣本進(jìn)行類別標(biāo)簽的設(shè)定，并尋找一個(gè)可以對(duì)所有數(shù)據(jù)特征樣本進(jìn)行包圍，并且盡可能遠(yuǎn)離原點(diǎn)的超平面作為訓(xùn)練的分界面，并利用這個(gè)分界面對(duì)數(shù)據(jù)特征樣本的簇輪廓進(jìn)行描述[6]。由于在聚類訓(xùn)練中普遍存在一些線性不可分狀況，因此必須將數(shù)據(jù)特征樣本在特征空間中映射并對(duì)其進(jìn)行分析。在特征空間中對(duì)數(shù)據(jù)特征樣本進(jìn)行數(shù)據(jù)輪廓描述，并對(duì)新樣本或外點(diǎn)進(jìn)行聚類訓(xùn)練，尋找一個(gè)最小的并且可以對(duì)所有數(shù)據(jù)特征樣本進(jìn)行包圍的超平面，對(duì)其進(jìn)行逆向映射操作，使其映射到輸入空間中，從而獲得可以描述數(shù)據(jù)特征樣本輪廓的邊界[7]。聚類步驟流程圖，如圖1所示。

根據(jù)圖1可進(jìn)行具體操作如下。

給定N個(gè)數(shù)據(jù)特征樣本的數(shù)據(jù)集，并對(duì)超平面中心進(jìn)行設(shè)定，從而獲取聚類訓(xùn)練的目標(biāo)函數(shù)[8]。在聚類訓(xùn)練的目標(biāo)函數(shù)中，訓(xùn)練樣本中有一部分是允許出現(xiàn)在超平面標(biāo)準(zhǔn)半徑外的，并且在該函數(shù)中，利用懲罰因子C對(duì)松弛因子和半徑的比重進(jìn)行平衡，并對(duì)噪聲數(shù)據(jù)點(diǎn)進(jìn)行抑制以及對(duì)外點(diǎn)規(guī)模進(jìn)行控制，通常懲罰因子C的取值范圍在零到一之間。在聚類訓(xùn)練的目標(biāo)函數(shù)中引入分值方法中的乘子，可以得到聚類訓(xùn)練的對(duì)偶式。通過(guò)聚類訓(xùn)練的對(duì)偶式可以對(duì)樣本和超平面邊界長(zhǎng)度與超平面中心的距離進(jìn)行精準(zhǔn)的判斷，并且便于進(jìn)行簇的標(biāo)定。在對(duì)聚類訓(xùn)練的對(duì)偶式進(jìn)行求解的過(guò)程中，即可獲得可以描述數(shù)據(jù)特征樣本輪廓的邊界。當(dāng)對(duì)偶式的解等于零時(shí)，則在特征空間中可以判斷樣本處于超平面外部，可以稱之為孤立點(diǎn)或外點(diǎn)[9]，但該樣本對(duì)超平面的構(gòu)造是有貢獻(xiàn)的，因此也將其稱為受限線性可分支持向量，如圖2所示。

當(dāng)對(duì)偶式的解大于零時(shí)，則在特征空間中可以判斷樣本處于超平面表面，稱之為線性可分支持向量。

當(dāng)對(duì)偶式的解等于零時(shí)，則在特征空間中可以判斷樣本處于超平面內(nèi)部，稱之為內(nèi)點(diǎn)[10]。

通過(guò)外點(diǎn)、線性可分支持向量與內(nèi)點(diǎn)即可獲得可以描述數(shù)據(jù)特征樣本輪廓的邊界?？梢园l(fā)現(xiàn)這個(gè)邊界是閉合的，并且上面的樣本點(diǎn)與超平面中心的距離相同。處于邊界內(nèi)部的那些樣本點(diǎn)由于同時(shí)位于超平面內(nèi)部，其與超平面中心的距離比超平面邊界長(zhǎng)度的距離要小，因此這些樣本點(diǎn)可以歸類在一個(gè)簇中。通過(guò)聚類簇標(biāo)定算法對(duì)各個(gè)樣本點(diǎn)的簇標(biāo)號(hào)進(jìn)行確定，實(shí)現(xiàn)海量樣本特征的樣本聚類。

1.3?實(shí)現(xiàn)樣本分組

完成海量樣本特征的樣本聚類后，建立線性可分支持向量機(jī)分組框架，利用樣本特征的樣本聚類結(jié)果對(duì)數(shù)據(jù)特征樣本的訓(xùn)練分組信息進(jìn)行獲取，并將訓(xùn)練分組信息引入線性可分支持向量機(jī)分組框架中，從而獲取最佳的分劃超平面。其中訓(xùn)練樣本的分組步驟如下：首先通過(guò)分值方法對(duì)其重要特征進(jìn)行選取，接著以選取的樣本聚類技術(shù)為依據(jù)對(duì)分組信息進(jìn)行獲取[11]。獲取訓(xùn)練分組信息后，在線性可分支持向量機(jī)分組框架中引入訓(xùn)練分組信息，并利用迭代算法實(shí)現(xiàn)線性可分支持向量機(jī)分組框架，具體實(shí)現(xiàn)步驟如下。

輸入核函數(shù)K（x，x′）與Kr（x，x′）、樣本集的總體特征個(gè)數(shù)r、權(quán)衡參數(shù)μ、懲罰因子C、特征因子S′，進(jìn)行初始化，如式（9）。

通過(guò)特征選擇方法的執(zhí)行在樣本集X上對(duì)特征因子S′進(jìn)行獲取，并對(duì)初始化結(jié)果進(jìn)行更新，如式（10）。

在特征子集上對(duì)聚類技術(shù)進(jìn)行執(zhí)行，從而將訓(xùn)練集T劃分為相關(guān)組。

對(duì)優(yōu)化問(wèn)題進(jìn)行求解，獲取決策函數(shù)。重復(fù)迭代步驟，直至j0=n。

對(duì)最佳決策函數(shù)進(jìn)行選取并對(duì)其進(jìn)行輸出，從而實(shí)現(xiàn)線性可分支持向量機(jī)分組框架[12]。

利用線性可分支持向量機(jī)分組框架分組樣本，實(shí)現(xiàn)面向海量樣本的線性可分支持向量機(jī)分組算法。

2?實(shí)驗(yàn)研究

為了檢測(cè)本研究提出的面向海量樣本的線性可分支持向量機(jī)分組算法，設(shè)計(jì)了對(duì)比實(shí)驗(yàn)。

2.1?實(shí)驗(yàn)過(guò)程

本研究所有算法均基于仿真軟件MATLAB 20I2a進(jìn)行實(shí)驗(yàn)，仿真計(jì)算機(jī)系統(tǒng)為Windows 7，處理器為Intel i5-7500，內(nèi)存為16.00 GB，處理器頻率為2.93 GHz。在海量樣本中進(jìn)行實(shí)驗(yàn)樣本的選取，共選取十個(gè)實(shí)驗(yàn)樣本數(shù)據(jù)集，包括Tonosphere樣本數(shù)據(jù)集、WPBC樣本數(shù)據(jù)集、Seed樣本數(shù)據(jù)集、Diabetes樣本數(shù)據(jù)集、BUPA樣本數(shù)據(jù)集、Teaching樣本數(shù)據(jù)集、Haberman樣本數(shù)據(jù)集、Breast樣本數(shù)據(jù)集、Heartstatlog樣本數(shù)據(jù)集和Hepatitis樣本數(shù)據(jù)集，而各個(gè)樣本數(shù)據(jù)集在非線性情形與線性情形中，其最優(yōu)樣本分類精度所分別對(duì)應(yīng)的樣本特征個(gè)數(shù)，如圖3所示。

本次實(shí)驗(yàn)通過(guò)網(wǎng)格搜索法獲取最優(yōu)參數(shù)，在參數(shù)的選取中，根據(jù)K值自適應(yīng)的SA-KNN算法對(duì)樣本參數(shù)中的的計(jì)算結(jié)果[13]將近鄰參數(shù)設(shè)定為5;將權(quán)衡參數(shù)的取值范圍設(shè)定為10-3-10-1;將懲罰參數(shù)的取值范圍設(shè)定為10-1-102;將高斯核參數(shù)的取值范圍設(shè)定為2-2-22。而對(duì)于聚類時(shí)截?cái)嗑嚯x的取值則要遵循訓(xùn)練樣本與平均近鄰點(diǎn)數(shù)的比值為2%的原則。

為了保證本次實(shí)驗(yàn)的有效性，使用基于網(wǎng)格搜索的線性可分支持向量機(jī)分組算法、基于特征數(shù)據(jù)集的線性可分支持向量機(jī)分組算法、基于結(jié)構(gòu)信息的線性可分支持向量機(jī)分組算法與本研究提出的面向海量樣本的線性可分支持向量機(jī)分組算法進(jìn)行比較，并分別進(jìn)行15次實(shí)驗(yàn)，比較各個(gè)算法樣本分組正確率的高低。

2.2?實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)樣本分組正確率結(jié)果，如表1所示。

根據(jù)表1的樣本分組正確率數(shù)據(jù)可知，面向海量樣本的線性可分支持向量機(jī)分組算法的樣本分組正確率始終高于傳統(tǒng)線性可分支持向量機(jī)分組算法。

3?總結(jié)

本研究所提算法通過(guò)線性可分支持向量機(jī)分組框架實(shí)現(xiàn)了樣本的分組，仿真實(shí)驗(yàn)結(jié)果顯示其樣本分組正確率高于傳統(tǒng)線性可分支持向量機(jī)分組算法，可突出海量樣本的線性可分支持向量機(jī)分組算法優(yōu)勢(shì)，對(duì)線性可分支持向量機(jī)分組領(lǐng)域具有重要意義。但是本研究所提算法尚未進(jìn)行深入研究和應(yīng)用，應(yīng)擴(kuò)展研究角度、落實(shí)應(yīng)用實(shí)踐，以期為線性可分支持向量機(jī)分組領(lǐng)域做出更大貢獻(xiàn)。

參考文獻(xiàn)

[1]?冉瓊， 于浩洋， 高連如. 結(jié)合超像元和子空間投影支持向量機(jī)的高光譜圖像分類[J]. 中國(guó)圖象圖形學(xué)報(bào)， 2018， 23（31）：1195-1205.

[2]?楊志民， 王甜甜， 邵元海. 面向不均衡分類的隸屬度加權(quán)模糊支持向量機(jī)[J]. 計(jì)算機(jī)工程與應(yīng)用， 2018， 11（22）：1168-1175.

[3]?樂(lè)琦. 直覺(jué)模糊環(huán)境下考慮匹配意愿的雙邊匹配決策[J]. 中國(guó)管理科學(xué)， 2017， 25（6）：161-168.

[4]?薛章鷹， 劉興權(quán). 結(jié)合ReliefF、GA和SVM的面向?qū)ο蠼ㄖ锬繕?biāo)識(shí)別特征選擇方法[J]. 測(cè)繪工程， 2017， 26（32）：2152-2156.

[5]?岳鵬程， 張林梁， 馬閱軍. 基于模糊時(shí)序和支持向量機(jī)的高速公路SO_2濃度預(yù)測(cè)算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2017， 26（36）：2241-2248.

[6]?業(yè)巧林， 閆賀. 基于最小二乘的孿生有界支持向量機(jī)分類算法[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 46（53）：2213-2213.

[7]?王石， 蔣寧寧， 楊舒卉. 基于壓縮K近鄰邊界向量的支持向量預(yù)抽取算法[J]. 海軍工程大學(xué)學(xué)報(bào)， 2018， 30（36）：2278-2283.

[8]?李振， 曹慶貴， 楊濤. 基于支持向量機(jī)與連續(xù)蟻群算法建立的煤礦企業(yè)安全投入模型研究[J]. 礦業(yè)安全與環(huán)保， 2019， 46（51）：1109-1113.

[9]?何宏煒， 吳志航， 于召新. 四進(jìn)制自由空間激光通信信號(hào)的支持向量機(jī)檢測(cè)算法[J]. 光學(xué)學(xué)報(bào)， 2018， 38（41）：1414-1421.

[10]?趙彩云， 吳長(zhǎng)勤， 葛華. 基于有效迭代算法的魯棒L1范數(shù)非平行近似支持向量機(jī)[J]. 計(jì)算機(jī)應(yīng)用， 2017， 37（41）：3069-3074.

[11]?劉治超， 李侍林， 黃毅，等. 基于支持向量機(jī)的機(jī)載吊艙故障診斷優(yōu)化算法[J]. 計(jì)算機(jī)測(cè)量與控制， 2018， 26（31）：2171-2175.

[12]?劉陽(yáng)， 孫華東， 張艷榮，等. 基于支持向量機(jī)的糖尿病預(yù)測(cè)模型研究[J]. 哈爾濱商業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2018， 34（41）：2256-2278.

[13]?梁聰， 夏書(shū)銀， 陳子忠. 基于參考點(diǎn)的改進(jìn)k近鄰分類算法[J]. 計(jì)算機(jī)工程， 2019， 45（2）：173-178.

（收稿日期：2019.07.30）