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

馬捍超 沈杰鑫 徐路強 于海

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

關鍵詞：海量樣本;線性可分;支持向量機;分組算法

中圖分類號：TP13

文獻標志碼：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?引言

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

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

1.1?特征選擇

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

利用分值方法對海量樣本進行特征選擇。首先針對樣本集X進行相似對應矩陣的構造，如式（2）。

根據分值方法的基礎理論[3]，分值矩陣，如式（3）。

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

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

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

1.2?樣本聚類

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

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

根據圖1可進行具體操作如下。

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

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

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

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

1.3?實現樣本分組

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

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

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

在特征子集上對聚類技術進行執行，從而將訓練集T劃分為相關組。

對優化問題進行求解，獲取決策函數。重復迭代步驟，直至j0=n。

對最佳決策函數進行選取并對其進行輸出，從而實現線性可分支持向量機分組框架[12]。

利用線性可分支持向量機分組框架分組樣本，實現面向海量樣本的線性可分支持向量機分組算法。

2?實驗研究

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

2.1?實驗過程

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

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

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

2.2?實驗結果

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

根據表1的樣本分組正確率數據可知，面向海量樣本的線性可分支持向量機分組算法的樣本分組正確率始終高于傳統線性可分支持向量機分組算法。

3?總結

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

參考文獻

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

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

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

[4]?薛章鷹， 劉興權. 結合ReliefF、GA和SVM的面向對象建筑物目標識別特征選擇方法[J]. 測繪工程， 2017， 26（32）：2152-2156.

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

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

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

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

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

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

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

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

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

（收稿日期：2019.07.30）