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

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

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

中圖分類號：TP13

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

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

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

1.1?特征選擇

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

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

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

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

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

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

1.2?樣本聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2?實驗研究

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

2.1?實驗過程

本研究所有算法均基于仿真軟件MATLAB 20I2a進(jìn)行實驗，仿真計算機(jī)系統(tǒng)為Windows 7，處理器為Intel i5-7500，內(nèi)存為16.00 GB，處理器頻率為2.93 GHz。在海量樣本中進(jì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ù)集，而各個樣本數(shù)據(jù)集在非線性情形與線性情形中，其最優(yōu)樣本分類精度所分別對應(yīng)的樣本特征個數(shù)，如圖3所示。

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

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

2.2?實驗結(jié)果

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

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

3?總結(jié)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

（收稿日期：2019.07.30）