王文劍 祁曉博 郭虎升

(1.山西大學計算機與信息技術學院,太原,030006;2.山西大學計算智能與中文信息處理教育部重點實驗室,太原,030006)

一種高斯區(qū)間核SVM分類模型*

王文劍1,2祁曉博1郭虎升1

(1.山西大學計算機與信息技術學院,太原,030006;2.山西大學計算智能與中文信息處理教育部重點實驗室,太原,030006)

區(qū)間型數據(Interval data, ID)是屬性特征取值為區(qū)間的一類數據，針對區(qū)間型數據的分類問題，本文提出一種高斯區(qū)間核支持向量機分類模型(Support vector machine based on Gauss interval kernel, GIK_SVM)。該方法引入半寬因子，在區(qū)間型數據的中值與半寬度之間進行折中，并據此構造高斯區(qū)間核用以衡量兩個區(qū)間型數據間的相似性，然后用SVM模型進行分類。在人造數據集和真實數據集上的實驗結果表明，本文提出的算法對區(qū)間數據有更好的分類性能。

區(qū)間型數據； 半寬因子； 區(qū)間核； GIK_SVM模型

引 言

隨著互聯網與信息技術的迅猛發(fā)展，數據的獲取與使用逐漸便捷，不僅數據量每年都在飛速增長，數據的復雜性也日趨明顯[1,2]。其中有一類數據與人們的生產、生活息息相關，如某一地區(qū)一段時間的氣溫變化、某一段時間內的交通流量和工業(yè)總產值增長率等，這類數據的特點是：每個屬性特征的取值不確定，而是一個區(qū)間，這類數據稱為區(qū)間型數據。這類數據的出現可能是由于屬性值的多次測量、置信區(qū)間估計或取值范圍有界等。相較于離散數據，區(qū)間型數據可以從全局把握數據對象的內在結構特征，更有利于揭示隱含在數據內部的規(guī)律。因此，區(qū)間型數據可以表示數據的不確定性和可變性，在決策支持中具有重要的應用價值。與離散數據(確定性數據)不同，目前關于區(qū)間型數據的處理方法主要有3大類。(1)模糊集方法[3]，這類方法通過計算元素關于集合的隸屬程度來近似描述不確定性，將每個區(qū)間離散化為一個確定值(通常是符號屬性數據)，再用傳統方法進行處理。這類方法中隸屬函數大多為專家憑經驗給出，帶有強烈的主觀意志。(2)中值法[4]，即用區(qū)間中值作為區(qū)間型數據的特殊點，再用傳統方法進行處理。該方法只考慮了區(qū)間型數據的內部情況，丟失了區(qū)間大小這一相關信息。(3)采用上下邊界值替代區(qū)間型數據[5-7]，即將區(qū)間型數據離散化為兩個確定性數值，再用傳統方法進行處理。這類方法只用上下邊界值進行計算，未考慮區(qū)間型數據的內部分布情況。因此又有學者提出改進方法，在上下界基礎上考慮中值信息[8-10]，這樣不僅考慮到區(qū)間邊界，還將內部分布一并融合進去，使區(qū)間型數據表示更加全面。文獻[8]利用區(qū)間中值與寬度表示區(qū)間型數據，運用傳統的回歸方法分別對區(qū)間中值與區(qū)間半寬度生成回歸方程，然后通過這兩個方程對區(qū)間上下限進行預測。文獻[9]用區(qū)間中值與寬度表示區(qū)間變量，在這兩個獨立的確定性變量上用對稱線性回歸模型進行預測。文獻[10]提取區(qū)間值數據的區(qū)間中值與寬度，分別作為Gauss分布函數的期望和方差，用Gauss分布函數表示區(qū)間值數據并對其進行相似度量。

目前關于區(qū)間型數據的處理主要集中在聚類和回歸分析中[4-11]，分類問題的研究相對較少[12]?？紤]到區(qū)間型數據的特點及支持向量機(Support vector machine, SVM)良好的泛化能力[13-14]，本文提出一種高斯區(qū)間核SVM分類模型。該模型采用區(qū)間中值與半寬度表示區(qū)間型數據，設計了一個可調的半寬因子，并構造了高斯區(qū)間核，進而利用高斯區(qū)間核SVM模型對區(qū)間型數據進行分類。

1 基于高斯型區(qū)間核的SVM分類模型

1.1 高斯區(qū)間核

(1)

(2)

(3)

其中

(4)

(5)

聯立式(3～5)，可得

(6)

1.2 算法的主要步驟

算法1 GIK_SVM算法

(1) 根據式(1,2)分別計算出Tr和Te上區(qū)間型樣本的區(qū)間中值與區(qū)間半寬度；

(2) 根據式(6)在訓練集Tr上計算高斯區(qū)間核矩陣；

(3) 根據所得高斯區(qū)間核矩陣建立SVM分類模型，并在Te上進行測試；

(4) 算法結束。

將本文算法與基于區(qū)間中值的SVM分類算法(Supportvectormachinebasedonintervalmedian,IM_SVM)和基于區(qū)間邊界值的SVM分類算法(Supportvectormachinebasedonintervalboundaryvalue,IBV_SVM)進行比較，其中，IM_SVM算法只考慮區(qū)間型數據中值這一主要因素，IBV_SVM算法只考慮區(qū)間的上下兩個邊界值，兩種算法的主要步驟分別如下。

算法2 IM_SVM算法

(2) 用傳統高斯核在新的訓練集T′r上計算高斯核矩陣；

(3) 根據所得高斯核矩陣建立SVM分類模型，并在T′e上進行測試；

(4) 算法結束。

算法3 IBV_SVM算法

(2) 用傳統高斯核在新的訓練集T′r上計算高斯核矩陣；

(3) 根據所得高斯核矩陣建立SVM分類模型，并在T′e上進行測試；

(4) 算法結束。

2 實驗結果及分析

2.1 實驗環(huán)境及實驗數據

表1 實驗使用的數據集

Fig.1 Distributions of artificial datasets

2.2 半寬因子對算法的影響

本實驗中，TB_Ds上σ=0.1，在其他數據集上σ=0.25。為簡單起見，本文實驗中令α1=α2=…=αk=α，用α來表示半寬因子。圖2為3種算法預測準確率隨α變化的實驗結果。由圖2可以看出IM_SVM算法和IBV_SVM算法與半寬因子α值無關，所以其準確率曲線不發(fā)生變化。GIK_SVM的預測準確率隨著半寬因子α的調整不斷變化，在Ds1上，GIK_SVM整體優(yōu)于另兩種算法，在α=0.05處，取到最優(yōu)準確率；在Ds2上，GIK_SVM介于另兩種算法之間，在α=0.01處，GIK_SVM算法的準確率也達到了最優(yōu)值；在Ds3與Ds4這兩個數據集上，GIK_SVM浮動較大，Ds3中，在α=0.1與α=0.75處，GIK_SVM算法的準確率優(yōu)于另兩種算法，且當α=0.75時，達到最優(yōu)；在Ds4中，當α=0.025時，GIK_SVM雖與IM_SVM算法十分接近，但仍取到最優(yōu)準確率。從這4個圖中也能看出，除Ds2外，本文算法的最優(yōu)準確率明顯高于另外兩個算法。從它們的分布來看，Ds1中兩類數據分布緊密，但界限很清晰；Ds3與Ds4中則是混合重疊較多，數據較分散；而Ds2中兩類數據不僅分布緊密，還混合重疊較多，這也造成了GIK_SVM方法的分類準確率不如在其他人造數據集上效果好，且不如IBV_SVM方法準確率高。IM_SVM算法在兩個人造數據集上的準確率優(yōu)于IBV_SVM算法，而在另外兩個人造數據集上的準確率則不如IBV_SVM算法。由于人造數據集的構造方法較簡單，使得本文算法與另兩種算法在人造數據集上的比較結果相差并不大，因此，本文又在真實數據集上進行了實驗。

圖2 3種算法的預測準確率隨α變化的實驗結果Fig.2 Experimental results of the prediction accuracy with α for three algorithms

2.3 參數σ對算法的影響

本實驗主要考察參數σ對算法的影響。選取圖2中GIK_SVM的最優(yōu)準確率對應的α值作為本實驗各數據集的默認α值，圖3為3種算法預測準確率隨σ變化的實驗結果。由圖3可以看出不同的σ值對準確率的影響很大。當σ<2時，在Ds1與2個真實數據集上，GIK_SVM預測準確率較高；在其余數據集上，3種算法的準確率相當。當σ>2時，3種算法的準確率都開始降低。在Ds1上，GIK_SVM仍優(yōu)于另外兩種算法；在HS_Ds上，GIK_SVM介于另兩種算法之間；在TB_Ds上，3種算法的準確率相當；在其他3個數據集上，IBV_SVM算法準確率快速降低，GIK_SVM與IM_SVM算法準確率大體一致。目前關于高斯核參數σ的優(yōu)化已有很多研究，而本文主要關注高斯區(qū)間核度量區(qū)間型數據相似性的有效性，所以未對σ進行進一步優(yōu)化，后續(xù)實驗中，本文選取σ<2的值。

圖3 3種算法預測準確率隨σ變化的實驗結果Fig.3 Experimental results of prediction accuracy with σ for three algorithms

2.4 本算法與決策樹模型的比較

圖4 GIK_SVM與決策樹模型預測準確率隨α值變化的實驗結果Fig.4 Experimental results of prediction accuracy with α for GIK_SVM and decision tree models

為了進一步驗證GIK_SVM算法的有效性，本文還與3種決策樹模型進行比較?；谥兄蛋雽挼臎Q策樹模型(Decisiontreebasedonintervalmedianandboundaryvalue,IMBV_DT)將中值與半寬度分別作為判別屬性；基于中值的決策樹模型(Decisiontreebasedonintervalmedian,IM_DT)只將中值作為判別屬性；基于邊界值的決策樹模型(Decisiontreebasedonintervalboundaryvalue,IBV_DT)將區(qū)間的上下邊界值作為判別屬性。本實驗中，TB_Ds上σ=0.1，在其他數據集上σ=0.25。圖4為GIK_SVM算法與決策樹模型預測準確率隨α值變化的實驗結果。由圖4可以看出GIK_SVM算法的準確率明顯高于3種決策樹模型，其準確率高出5%～9%左右。在4個人造數據集上，GIK_SVM方法準確率曲線都高于其余3條曲線，決策樹模型的3條曲線則比較鄰近。在兩個真實數據集上，除去α取到邊界值0和1時，GIK_SVM算法的準確率也都明顯比決策樹模型高，即使在邊界值上，GIK_SVM的準確率仍高于IM_DT算法。實驗結果最終表明，SVM模型優(yōu)于決策樹模型。

3 結 論

區(qū)間型數據是一類常見然而較為特殊的數據形式，目前關于區(qū)間型數據處理的高效分類方法研究還相對較少。本文通過引入半寬因子，很好地折中了區(qū)間中值與區(qū)間半寬度對區(qū)間型數據挖掘的影響，此外構建了高斯區(qū)間核，并用高斯區(qū)間核SVM模型對區(qū)間型數據進行分類，提高了分類預測性能。在后續(xù)研究中，將考慮針對不同的區(qū)間型特征值，選取不同的半寬因子，以取得更好的效果。另外，將探索構造更多的有效區(qū)間核，進一步提高處理區(qū)間型數據的有效性。

[1] 何清, 李寧, 羅文娟, 等. 大數據下的機器學習算法綜述[J]. 模式識別與人工智能, 2014, 27(4): 327-336.

HeQing,LiNing,LuoWenjuan,etal.Asurveyofmachinelearningalgorithmsforbigdata[J].PattemRecognitionandAitificialIntelligence, 2014, 27(4): 327-336.

[2] 潘志松, 唐斯琪, 邱俊洋, 等. 在線學習算法綜述[J]. 數據采集與處理, 2016, 31(6): 1067-1082.

PanZhisong,TangSiqi,QiuJunyang,etal.Surveyononlinelearningalgorithms[J].JournalofDataAcquisitionandProcessing, 2016, 31(6): 1067-1082.

[3] 胡凱, 孟廣武, 于西昌. 區(qū)間值模糊集上的上(下)近似[J]. 模糊系統與數學,2007, 21(1): 123-127.

HuKai,MengGuangwu,YuXichang.Upper(lower)approximationofaninterval-valuedfuzzyset[J].FuzzySystemandMathematics, 2007, 21(1): 123-127.

[4]BillardL,DidayE.Regressionanalysisforinterval-valueddata[C]//DataAnalysis,ClassificationandRelatedMethods,ProceedingsoftheSeventhConferenceoftheInternationalFederationofClassificationSocieties(IFCS’00).Berlin,Heidelberg:Springer-VerlagPress, 2000: 369-374.

[5]BillardL,DidayE.Symbolicregressionanalysis[C]//Classification,ClusteringandDataAnalysis,ProceedingsoftheEighthConferenceoftheInternationalFederationofClassificationSocieties(IFCS’02).Berlin,Heidelberg:Springer-VerlagPress, 2002: 281-288.

[6]CabanesG,BennaniY,DestenayR.Anewtopologicalclusteringalgorithmforintervaldata[J].PatternRecognition, 2013,46(11):3030-3039.

[7]CarvalhoFDATD.AfuzzyclusteringalgorithmforsymbolicintervaldatabasedonasingleadaptiveEuclideandistance[C]//Proceedingsofthe13thInternationalConferenceonNeuralInformationProcessing(ICONIP2006).Berlin,Heidelberg:Springer-VerlagPress, 2006: 1012-1021.

[8]LimaNetoEDA,DeCarvalhoFDAT.Centreandrangemethodforfittingalinearregressionmodeltosymbolicintervaldata[J].ComputationalStatisticsandDataAnalysis, 2008, 52(3):1500-1515.

[9] Domingues M A.O, Souza R M C R D, Cysneiros F J A. A robust method for linear regression of symbolic interval data[J]. Pattern Recognition Letters, 2010, 31:1991-1996.

[10]呂澤華, 金海, 袁平鵬, 等. 基于Gauss分布函數的區(qū)間值數據的模糊聚類算法[J]. 電子學報,2010,38(2):295-300.

Lü Zehua, Jin Hai, Yuan Pingpeng, et al. A fuzzy clustering algorithm for interval-valued data based on gauss distribution functions[J]. Acta Electronica Sinica, 2010, 38(2): 295-300.

[11]于洋, 張穎, 胡舒涵. 區(qū)間型數據聚類的FCM新算法[C]//中國通信學會第六屆學術年會論文集(下).北京：中國通信學會,2009: 249-253.

Yu Yang, Zhang Ying, Hu Shuhan. The new FCM algorithm of interval data clustering[C]//Proceedings of the 6th Academic Annual Conference of China Communication Association. Beijing: China Institute of Communications Press, 2009: 249-253.

[12]陳建凱, 王鑫, 何強, 等. 區(qū)間值屬性的單調決策樹算法[J]. 模式識別與人工智能, 2016, 29(1): 47-53.

Chen Jiankai, Wang Xin, He Qiang, et al. Interval-valued attributes based monotonic decision tree algorithm[J].Pattem Recognition and Aitificial Intelligence, 2016, 29(1): 47-53.

[13]Vapnik V. Statistical learning theory[M]. New York: Springer-Verlag Press, 1998:493-520.

[14]Cortes C, Vapnik V. Support vector networks[J]. Machine Learning, 1995(20): 273-297.

[15]中國6603個居民點天氣[EB/OL]. http://rp5.ru/中國天氣_, 2016-04.

Support Vector Machine Classification Model Based on Gauss Interval Kernel

Wang Wenjian1,2, Qi Xiaobo1, Guo Husheng1

(1.School of Computer and Information Technology, Shanxi University, Taiyuan, 030006, China; 2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan, 030006,China)

Interval data (ID) is a kind of data which the attribute values are the interval. Aiming at the classification problem of interval data, a support vector machine classification model based on Gauss interval kernel (GIK_SVM) is proposed. In the method, the half-width factor is introduced which makes a compromise between the median and the half width of interval data. Then, the Gauss interval kernel is constructed to measure the similarity between two interval data. SVM model is applied to classify the samples.Experiment results on artificial and real datasets demonstrate that the proposed GIK_SVM has a better classification performance for interval data.

interval data(ID); half-width factor; interval kernal; GIK_SVM model

國家自然科學基金(61673249, 61503229, 61273291)資助項目；山西省回國留學人員科研項目(2016-004)資助項目；山西省自然科學青年基金(2015021096)資助項目；山西省高等學校科技創(chuàng)新(2015110)資助項目。

2016-11-30；

2017-01-07

TP18

A

王文劍(1968-)，女，博士，教授，研究方向：神經網絡，支持向量機，計算智能和數據挖掘， E-mail:wjwang@sxu.edu.cn。

祁曉博(1992-)，女，碩士研究生，研究方向：機器學習和數據挖掘。

郭虎升(1986-)，男，博士，副教授，研究方向：支持向量機，機器學習和數據挖掘。