面向區間型數據的不同區間核SVM分類模型

祁曉博，宋金玉，史穎，3，亓慧，穆曉芳

（1.太原師范學院 計算機科學與技術學院，山西 晉中 030619；2.太原師范學院 數學與統計學院，山西 晉中 030619；3.山西大學 計算機與信息技術學院，山西 太原 030006）

0 引言

大數據時代的到來，不僅帶來了數據量的指數型增長，還使數據的復雜性與日俱增。區間型數據（Interval-valued data，IVD）是一種常見的定量符號數據，它的特點是每個屬性特征都不再是一個數值，而是一個區間范圍。一般來說，區間型數據包含更多的數據內在結構特征，因此相較于傳統數值型數據，更有利于揭示隱含在數據內部的變化規律。然而區間型數據的表現形式較為特殊，使得一般分類方法無法直接對其進行處理，除非如同區間型數據的主成分分析［1-2］、判別分析［3-5］、回歸分析［6-9］和聚類分析［10-12］等其他分析方法，在使用前對它進行合理的數值表示。表示后的區間型數據也并不十分完美，要么損失大量信息，要么特征數是原始數據的2 倍，這些不足不僅會影響分類器的分類性能和效果，還會增加內存存儲和時間復雜度。為了使區間型數據在分類過程中克服這些不足，分類方法的選擇十分重要。

分類問題是機器學習領域中一項重要任務，它的目的是將已有數據中學習到的規律用于新數據的預測和分析，為人們的決策提供理論指導。主流的分類方法可以分為單一分類方法和集成分類方法。神經網絡分類、決策樹分類、K 近鄰分類及支持向量機分類（Support Vector Machine，SVM）等是常用的單一分類方法。盡管這些單一分類方法發展迅速，但實際生活中的一些復雜問題仍然無法用這些方法得到有效解決，因此集成分類方法應運而生，其中Bagging 系列和Boosting 系列方法是集成分類的典型。目前不管是單一分類方法還是集成分類方法都是針對傳統數值型數據的，面對區間型數據時，這些方法就顯得有些力不從心。

相較于其他分類方法，支持向量機是一種運用核函數將原始空間樣本投影到高維特征空間進行分類的算法，而核函數最早且最成功的應用也是在支持向量機上。由于核函數是基于結構風險最小化原則的，因此以它為核心的支持向量機同樣具有核函數的優勢，在理論基礎和泛化能力方面表現十分出色。常用的核函數有多項式核、線性核、高斯核及Sigmoid 核［13］。一般來說，不存在萬能核函數，實際問題中人們往往根據具體的應用背景構造新的核函數［14］。Ozer 等［15］將切比雪夫多項式推廣成向量形式，并由此構造切比雪夫核函數用于支持向量機分類。此外Zhang 等［16-17］提出的基于洛倫茲函數構造的核函數、勒讓德核函數及Zhang 等［18］的最優松弛因子核函數極大豐富了核函數的種類。

上述基于不同核函數的支持向量機方法對傳統數據是有效的，但是并不能很好地完成區間型數據的分類。鑒于此，文獻［19］中在高斯核基礎上構造出高斯區間核函數，提出的高斯區間核SVM 分類模型（Support Vector Machine Based on Sigmoid Interval Kernel，GIK_SVM）能更好地適應區間型數據的分類，且分類結果較好。核函數的種類雖然在不斷地增長，但是仍存在以下兩方面問題：一是核函數的性能總是相對具體數據集而言的，二是核參數優化的可行性要在考慮范圍內。針對這兩個問題，本文提出了面向區間型數據的不同區間核SVM 分類模型，除包含之前的GIK_SVM 外，該方法還提出了適用于區間型數據的線性區間核、多項式區間核和Sigmoid 區間核，并構建相應的分類模型，即線性區間核SVM 分類模型（Support Vector Machine Based on Linear Interval Kernel，LIK_SVM），多項式區間核SVM 分類模型（Support Vector Machine Based on Polynomial Interval Kernel，PIK_SVM），Sigmoid 區間核SVM分類模型（Support Vector Machine Based on Sigmoid Interval Kernel，SIK_SVM）。在人造數據集和真實數據集上的實驗結果表明不同區間型數據集適用不同的區間核函數SVM 分類模型。

1 區間核SVM分類模型

在支持向量機中，核函數的類型及其參數直接決定了SVM 的學習能力和泛化能力。由于區間型數據結構的特殊性，SVM 中常用的核函數不能直接用于區間型數據。在高斯區間核［19］基礎上，考慮到實際問題中樣本數據的特征往往未知，本文提出不同的區間核，使其能夠直接用于區間型數據并取得較好的分類精度。

1.1 區間型數據矩陣

二元區間數在表示屬性內涵的基礎上，能夠有效克服由于模糊性而帶來的數值上的不確定性，具體定義如下［20］：

定義1（二元區間數）設R 表示實數集，對任意u-，u+∈R 且u-≤u+，記

稱u=[u-，u+]為一個標準的二元區間數。其中，u+為上極限，稱為二元區間數的大元，u-為下極限，稱為二元區間數的小元。

性質1對任意u∈I(R)（全體二元區間數的集合），如果u-=u+，則u=[u-，u+]退化為一個普通的實數，即u=u-=u+，故R ∈I(R)。所以區間數是實數的推廣。

根據二元區間數的定義，給出區間型數據矩陣、區間中值與區間半徑的定義。

定義2（區間型數據矩陣）設區間型數據，則U=[uij]為n×p區間型數據矩陣，即

定義3（區間型數據中值）設區間型數據，則區間型數據uij的中值為

定義4（區間型數據半徑）設區間型數據，則區間型數據uij的半徑為

1.2 區間核構造

核方法是機器學習中解決非線性問題的一種重要技術，它通過核函數描述特征空間向量間的內積，避免非線性映射的顯示表達。根據區間型數據的定義以及高斯區間核的構造方法，本文相繼提出線性區間核、多項式區間核和sigmoid 區間核。對于任意兩個區間型樣本和，三種區間核構造方法如下：

（1）線性區間核：

（2）多項式區間核：

（3）Sigmoid 區間核：

其中，上述三種核中的參數α表示意義相同，α∈[0，1]，是區間型數據的調節因子，使區間中值與區間半徑對樣本的相似性度量達到有效折中。當α=1 時，三種區間核只考慮區間中值；當α=0 時，三種區間核只考慮區間半徑；當α∈(0，1)時，區間中值與區間半徑可以做到有效平衡。多項式區間核與Sigmoid 區間核中的參數γ、r也相同，γ為核函數系數，r為核函數獨立項。多項式區間核中的參數d為階數，決定多項式的最高次冪。

1.3 算法的主要步驟

設區間型數據集T={(U，Y)}，U為區間型數據矩陣，Y為分類標簽。本文提出的區間核SVM 分類模型的主要思想是：首先計算出區間型數據的區間中值與區間半徑，然后根據數據集的分布特征構造合適的區間核矩陣，最后用構建的區間核SVM 分類模型進行分類。IK_SVM 算法的主要步驟如下：

輸入：區間型數據矩陣U，區間核參數γ，r，d，調節因子α；

輸出：分類精度acc。

①根據公式（3）和（4）分別計算出區間中值和區間半徑；

②構造區間核矩陣并建立相應的區間核SVM 模型：

Switch（kernel）｛

case ‘Linear’：構造線性區間核矩陣并建立線性區間核SVM 分類模型LIK_SVM；

case ‘Poly’：構造多項式區間核矩陣并建立多項式區間核SVM 分類模型PIK_SVM；

case ‘RBF’：構造高斯區間核矩陣并建立高斯區間核SVM 分類模型GIK_SVM［19］；

case ‘Sigmoid’：構造Sigmoid 區間核矩陣并建立Sigmoid 區間核SVM 分類模型SIK_SVM；｝

③在數據集上進行訓練和測試，計算分類精度acc；

④算法結束。

1.4 時間復雜度分析

對于n×p維區間型數據矩陣，n為樣本個數，p為特征數。

線性SVM 的時間復雜度為O(np)，非線性核SVM 的時間復雜度一般是在O(n2p) 與O(n3p)之間。由于α將區間中值與區間半徑調節為一個整體，特征維數并未增加，所以LIK_SVM 的時間復雜度為O(np)，PIK_SVM 與SIK_SVM 的時間復雜度也在O(n2p)與O(n3p)之間。

2 實驗結果與分析

2.1 實驗數據與實驗設計

本文實驗采用4 個人造數據集和2 個真實數據集。為了便于比較，數據集與文獻［19］相同。其中Ds1、Ds2、Ds3 和Ds4 是人造數據集，構造方法與文獻［19］一致，由種子數據生成，構造公式為[z-r，z+r]，z是根據正態分布生成的種子數據，r是從均分布中提取的寬度。數據集的類別主要由種子數據的位置區分，圖1 為4 個人造數據集上隨機選取200 個數據的分布圖，紅色和藍色分別為兩類不同的區間型數據。HS_Ds 和TB_Ds 是真實數據集，來源于“Reliable Prognosis”站點（rp5.ru）提供的氣象數據［21］。實驗數據詳見表1。為了保證方法的穩定性，本文的每個實驗都是10 次實驗結果的平均值。實驗部分均在MATLAB R2014a 平臺下實現，所用計算機環境為Intel（R） Core（TM）i7-4790，3.60 GHz，內存8 GB，64 位操作系統。

圖1 人造數據集的分布Fig.1 Distributions of synthetic datasets

表1 實驗數據集Table 1 Experimental datasets

本文首先驗證參數α和γ分別對所提LIK_SVM、PIK_SVM 和SIK_SVM 的影響，多項式區間核和Sigmoid 區間核參數r都設為默認值0，多項式區間核參數d為默認值3。隨后將上述三種方法與GIK_SVM 方法進行分類精度的比較，說明不同區間型數據集適用不同的區間核函數SVM 分類模型。

2.2 實驗結果及分析

（1） 調節因子α的影響

本實驗中，γ設為默認值，α在[0，1]之間取值，驗證調節因子α對分類精度的影響并確定三種方法在各數據集上的最優值。LIK_SVM、PIK_SVM 和SIK_SVM 在各個數據集上的分類精度隨α變化情況如圖2 所示。圖中清晰顯示了α對三種分類模型在不同數據集上的影響。LIK_SVM 在6 個數據集上基本呈上升趨勢，在α=0.01 時，上升趨勢尤為明顯，Ds1 和TB_Ds在α=1 處有下降。PIK_SVM 除了在HS_Ds 上起伏較大外，在其余5 個數據集上也基本呈上升趨勢。Ds1-Ds4 在α=0.25 處，有明顯上升，在0.75 處達到最優。SIK_SVM 在TB_Ds 上變化不大，在另外5 個數據集上呈上升趨勢，α=0.01 處，起伏最大。TB_Ds 在α=0 時，達到最優值。SIK_SVM 在真實數據集上的結果不是很理想，HS_Ds 和TB_Ds 的分類精度最高在50%左右。

圖2 調節因子α的影響Fig.2 Influence of adjustment factor α

為了更好地描述不同方法隨調節因子α在各個數據集上的變化，每種方法在各數據集上的最優α值見表2 所示。表中可以看出不同的數據集分布各不相同，三種方法隨α值的變化也不盡相同，最優α值基本分布在0，1 之間，其中SIK_SVM 方法在TB_Ds 上略有不同，在α取0 時，分類精度最大，根據公式（7）知此時區間型數據只保留了區間半徑，沒有區間中值。

表2 各方法的最優α值Table 2 Best α of each method

（2） 參數γ的影響

由于LIK_SVM 沒有參數γ，PIK_SVM、SIK_SVM 和GIK_SVM 在各個數據集上的分類精度隨γ變化情況如圖3 所示。PIK_SVM 和SIK_SVM 選取表2 中最優α值，GIK_SVM 使用文獻［19］的最優α值。圖中可以看出不同的γ值對分類精度的影響很大。在Ds1 和Ds2 上，GIK_SVM 的變化較為平緩。PIK_SVM 在γ=0.25 時，上升變化明顯，分類精度超過GIK_SVM，隨后趨于平緩。SIK_SVM 開始與GIK_SVM 相差不大，在γ=10 時開始下降。在Ds3 和 Ds4 上，GIK_SVM 在 PIK_SVM 和SIK_SVM 之上，且變化不大。PIK_SVM 在γ=0.1 處有小幅上升，隨后上升幅度減少；在γ=50 時有下降，隨后有小幅波動。在HS_Ds 上，GIK_SVM 在γ=10 時下降，但分類精度仍優于PIK_SVM 和SIK_SVM。PIK_SVM 波動較大，但整體呈下降趨勢。SIK_SVM 在γ=0.5 處明顯下降，隨后較平緩。在TB_Ds 上，PIK_SVM雖有波動，但整體優于GIK_SVM 和SIK_SVM。GIK_SVM 整體呈下降趨勢。SIK_SVM 則起伏不大，較為平緩。參數γ對分類精度確有一定的影響，本文不對γ做詳細優化，主要關注調節因子α的有效性。從實驗中可以看出，γ在2 之前已有較好的分類精度。

圖3 參數γ對測試精度的影響Fig.3 Influence of parameter γ on test accuracy

為了更好地描述不同方法隨參數γ在各個數據集上的變化，每種方法在各數據集上的最優γ值見表3 所示。表中可以看出不同的數據集上最優γ值不盡相同。GIK_SVM 的最優γ值多集中在0.25 上，只有TB_Ds 在0.01 處最優。PIK_SVM 的最優γ值相對較大，Ds1-Ds4 上的最優值都大于等于2，在HS_Ds 和TB_Ds 上的最優γ值小于1。SIK_SVM 的最優值也都小于1，Ds2 和Ds3 上最優值為0.5，HS_Ds 和TB_Ds為0.01，另外兩個數據集上的最優γ值分別為0.25 和0.1。（3） 與文獻［19］中GIK_SVM等方法的比較

表3 各方法的最優γ值Table 3 Best γ of each method

將LIK_SVM、PIK_SVM 和SIK_SVM 與文獻［19］中的GIK_SVM、IM_SVM 和IBV_SVM方法進行比較。參數r和d都設為默認值，α和γ分別選取表2-3 以及文獻［19］中各個數據集上的最優值，六種方法在各數據集上的分類精度如表4 所示。在Ds1 和Ds2 上，PIK_SVM分類效果最優，在Ds3 上，SIK_SVM 分類效果最好，在Ds4、HS_Ds 和TB_Ds 上，則是GIK_SVM 分類精度最高。由圖1 知，Ds1 和Ds2 中兩類數據分布緊密，但是界限較為清晰，此類分布的數據，PIK_SVM 具有更好的處理能力。Ds3 和Ds4 混合重疊較多，數據較分散，SIK_SVM 在這類分布的數據上具有較好的分類效果。Ds4 上的最優結果雖然是GIK_SVM方法，但是LIK_SVM、SIK_SVM、IM_SVM 和IBV_SVM 分類精度與其相差不大。在HS_Ds和TB_Ds 上，GIK_SVM 表現最優，LIK_SVM 和PIK_SVM 次之，IM_SVM 和IBV_SVM 又略低，而SIK_SVM 分類精度最低，只有50% 左右。表中可以反映出不同分布的數據集上最優結果主要集中在GIK_SVM、PIK_SVM 和SIK_SVM 上。

表4 六種方法精度比較Table 4 Comparison of accuracy among six methods

綜上所述，中值-半徑構造的區間核SVM模型整體比中值與邊界值模型分類性能佳，GIK_SVM、PIK_SVM 和SIK_SVM 在一些數據集上均能達到最優值，GIK_SVM 最優值最多，LIK_SVM 方法在6 個數據集上雖沒有最優值，但其分類精度在各數據集上居于中間水平，不是最高也不是最低。在6 個數據集上，PIK_SVM 的平均分類精度最高，GIK_SVM 和LIK_SVM 雖低于PIK_SVM，但其相差不大。SIK_SVM 雖在Ds3 上的分類精度明顯高于其余五種算法，但在兩個真實數據集上的結果較差。實驗說明不同分布的區間型數據集適用不同的區間核函數。

3 結論

綜合考慮區間型數據的特殊結構及其數據不同分布的影響，本文提出面向區間型數據的不同區間核SVM 分類模型。通過調節因子對區間中值與區間半徑進行有效折中，相較于中值與邊界值的分類模型，中值-半徑構造的區間核明顯優勢更大。本文方法將這些區間核函數集成在一個分類模型中，之后可以根據數據集類型選擇區間核函數進行分類。實驗結果表明，區間核SVM 分類模型更適用于區間型數據的分類處理，其中不同分布的區間型數據集選擇合適的區間核分類模型也是非常重要的。

不同數據集上的最優分類精度由不同區間核SVM 模型得出，故幾類區間核的分類性能與數據集的分布是相關的，這將是未來研究工作的一部分重要內容，另外，適用于更多分布的多種區間核函數構造方法也將是一項重要研究內容。