一種語義數(shù)據(jù)的核分類方法

李志華,任秋英,顧 言,王士同

(江南大學(xué) 信息工程學(xué)院,江蘇 無錫 214122)

0 引言

分類算法大多依賴于樣本間的相似性或相異性度量測(cè)度，如歐拉距離、內(nèi)積等,但其中大部分只能針對(duì)連續(xù)屬性樣本，而不能實(shí)現(xiàn)語義數(shù)據(jù)的度量。語義數(shù)據(jù)的分布是無序的、分布不平衡[1]，并且樣本集中不同類之間的差異很微弱，甚至互相交錯(cuò)[2，4]，要對(duì)其相異性進(jìn)行度量比較困難。目前的主要度量方式有：交迭度量(Overlap Metric)[2]、值相異度量[3](Value Difference Metric,VDM)、自適應(yīng)的相異性度量[4](Adaptive Dissimilarity Matrix,ADM)、 海明距離度量[5-6]，但這些方法或多或少地存在一些不足，如文獻(xiàn)[3，5-6]的度量方式都是基于這樣的假設(shè)：若樣本相異，則其相異程度相同，即要么為“0”要么為“1”，沒有體現(xiàn)出樣本間相異程度的不同；又如文獻(xiàn)[4]的度量方式雖然體現(xiàn)了樣本間相異的不同程度，但它同樣是基于樣本的屬性是相互獨(dú)立的假設(shè)，這不符合現(xiàn)實(shí)。另外，許多核聚類或核分類方法，如支撐向量機(jī)通過把輸入空間中交錯(cuò)的樣本映射到特征空間，從而拉開樣本之間的距離，通過極大化分類間隔(margin)來提高分類器的分類能力,在處理小樣本時(shí)具有很好的泛化能力[7]，但同樣無法實(shí)現(xiàn)語義數(shù)據(jù)的內(nèi)積計(jì)算。

本文提出一種語義數(shù)據(jù)相異性度量測(cè)度的新定義，給出一種計(jì)算語義數(shù)據(jù)內(nèi)積的簡(jiǎn)化方法，通過進(jìn)一步研究核方法和支撐向量機(jī)中的核函數(shù)，提出一種語義數(shù)據(jù)的核分類方法(KNDC)，并向語義數(shù)據(jù)和連續(xù)屬性的異構(gòu)數(shù)據(jù)集進(jìn)行了拓展,能比較好地實(shí)現(xiàn)語義數(shù)據(jù)和異構(gòu)數(shù)據(jù)的分類計(jì)算。

1 核方法及支撐向量機(jī)中的核函數(shù)簡(jiǎn)介

根據(jù)Mercer核理論可知,只要一種運(yùn)算滿足Mercer核條件, 那么這種運(yùn)算就可以作為內(nèi)積函數(shù)[8], 這一命題可以解決復(fù)雜的非線性分類問題, 并且計(jì)算復(fù)雜度基本不會(huì)增加，這是核方法的基本出發(fā)點(diǎn)。著名的支撐向量機(jī)(Support Vector Machine, SVM)是核方法的一個(gè)成功應(yīng)用，SVM中的核函數(shù)主要分為兩大類[10]：基于距離的核、基于內(nèi)積的核。如，基于Euclid距離和基于Euclid內(nèi)積的核分別具有如式(1)、式(2)的通用形式：

(1)

(2)

其中dU(xi,xj)、I(xi,xj)分別為向量xi,xj在輸入空間中的Euclid距離和Euclid內(nèi)積，f(·)是輸入空間到特征空間的一個(gè)映射函數(shù)。

2 語義數(shù)據(jù)的核分類方法

語義數(shù)據(jù)中沒有任何相似性的概念，甚至沒有次序關(guān)系[11]，如顏色“白”與“黑”，它們之間的區(qū)別再明確不過了，但在經(jīng)典模式識(shí)別領(lǐng)域卻很難找到一個(gè)“距離”去度量它們之間的相似性或相異性，即使語義數(shù)據(jù)從形式上看是離散的，由于非度量(nonmetric)性的客觀存在[11-12]，要進(jìn)行語義數(shù)據(jù)分類依然是一個(gè)難點(diǎn)問題。本文提出一個(gè)廣義度量距離，并從核的角度研究語義數(shù)據(jù)的分類問題。

2.1 樣本的相異性度量

假設(shè)有樣本集：xi∈X，xi=(xi1,xi2,…,xid,xi(d+1),…,xi(d+m))T，1≤i≤n，且前d維為語義屬性，后m維為連續(xù)屬性，即X為異構(gòu)數(shù)據(jù)集。本文定義語義數(shù)據(jù)間的相異性度量測(cè)度dsymbolic如式(4)所示。

定義 語義數(shù)據(jù)的相異性度量測(cè)度：

(3)

(i≠j,1≤i≤n,1≤j≤n,1≤p≤l)

dsymbolic(xi,xj)=[dims-s(xi,xj)]/dims

(4)

其中dims是語義數(shù)據(jù)的維數(shù)。式(4)同文獻(xiàn)[2-4]中的度量方法相比較，有以下明顯好處：把語義數(shù)據(jù)的相異性度量成區(qū)間[0,1]之上的一個(gè)不確定性，克服了文獻(xiàn)[2]中度量成非“0”即“1”的那種絕對(duì)情況，顯然式(4)的度量更加客觀實(shí)際；式(4)的值域?yàn)閇0,1]，起到歸一化的作用，有利于同其他度量方法結(jié)合使用。

若連續(xù)屬性的樣本間的相異性直接采用歐氏距離的度量方式，則異構(gòu)樣本之間的距離用式(5)計(jì)算：

(i≠j,1≤i≤n,1≤j≤n,1≤h≤m)

(5)

不難證明公式(5)總能滿足距離的：①非負(fù)性，即d(xi,xj)≥0；②對(duì)稱性，即d(xi,xj)=d(xj,xi)；③規(guī)范性，d(xi,xj)=0當(dāng)且僅當(dāng)xi與xj完全相同，但不能總是滿足三角不等式的距離測(cè)度原則，所以公式(5)是一個(gè)半度量的(Semi-metric)距離測(cè)度,也稱為廣義(Generalized) 距離測(cè)度。式(5)具有“距離”定義的通用形式，綜合考慮了不同屬性之間的相異性。

2.2 異構(gòu)屬性樣本的核分類方法

假設(shè)有一個(gè)二分類問題的訓(xùn)練樣本如下：

(x1,y1),(x2,y2),…,(xi,yi),…,(xm,ym)

其中，xi∈X,xi是異構(gòu)樣本，類標(biāo)記yi∈{-1,1}。

核方法的本質(zhì)就是把一個(gè)輸入空間變換到一個(gè)內(nèi)積空間的過程，從而實(shí)現(xiàn)各種算法，而語義數(shù)據(jù)集、異構(gòu)數(shù)據(jù)集上通常無法定義內(nèi)積，本文的解決辦法是選用高斯核函數(shù)作為核方法中的核投影函數(shù)，用相異性度量測(cè)度代替投影中的范數(shù)，通過此方法來完成輸入空間到特征空間的映射，其好處是：既完成了核方法中的核變換，又簡(jiǎn)化了語義數(shù)據(jù)和異構(gòu)數(shù)據(jù)的內(nèi)積運(yùn)算。最終的核函數(shù)定義為：

(6)

其中，式(6)中的d即式(5)。根據(jù)核矩陣在核方法中的作用可知，通過式(6)的核變換以后，支撐向量的求解過程實(shí)質(zhì)上同樣是一個(gè)二次規(guī)劃問題，上述過程描述成如下算法。

語義數(shù)據(jù)的核分類(Kernel-based Nominal Data Classification,KNDC)方法：

步驟 1 根據(jù)式(5)計(jì)算樣本集X的d；

步驟 2 用式(6)計(jì)算樣本X的內(nèi)積,并求解二次規(guī)劃問題：

得到最優(yōu)解：

α*={α1,α2,…,αl}

步驟3 用α*構(gòu)造超平面：

其決策函數(shù)為：

F(x)=sign(f(x)+b) 其中b為決策閾值；

步驟4 計(jì)算F(x)的值，對(duì)樣本進(jìn)行分類：

由于語義數(shù)據(jù)和異構(gòu)數(shù)據(jù)中很難界定噪聲數(shù)據(jù), 所以上述算法中那些被拒識(shí)的樣本很可能會(huì)增加誤識(shí)所造成的損失。

KNDC方法同SVM算法相比能一次性構(gòu)造任意給定的語義數(shù)據(jù)樣本集或異構(gòu)數(shù)據(jù)樣本集的核函數(shù)，克服了SVM算法中有關(guān)核矩陣計(jì)算量過大的不足，顯著地提高了算法的收斂速度，并有效地?cái)U(kuò)展了SVM的應(yīng)用范圍。

3 標(biāo)準(zhǔn)樣本集的仿真實(shí)驗(yàn)及分析

(1) 分類器的衡量指標(biāo)

本節(jié)用錯(cuò)分率來衡量分類器對(duì)不同樣本的分類精度，錯(cuò)分率是指被錯(cuò)分的樣本數(shù)量占樣本總數(shù)的比值。如式(7)所示，分類正確率如式(8)所示：

(7)

(8)

numberi為正類和負(fù)類中被錯(cuò)誤分類的樣本個(gè)數(shù)，n為樣本的總數(shù)。γerror值越小，就說明分類準(zhǔn)確度高，分類效果好, 越大，則剛好相反。

(2) 樣本的組成及初始化方法

為了評(píng)價(jià)核分類器的分類能力，仿真實(shí)驗(yàn)使用了三個(gè)純語義數(shù)據(jù)樣本集[2，4]和一個(gè)異構(gòu)屬性數(shù)據(jù)樣本集[1]，樣本集的組成如表1所示[16]，并把方法在網(wǎng)絡(luò)異常檢測(cè)中進(jìn)行了應(yīng)用研究，除monks-1、 monks-3兩個(gè)樣本集有固定的訓(xùn)練樣本集和測(cè)試樣本集外，其余樣本的訓(xùn)練樣本均是簡(jiǎn)斷無回放地從樣本集中抽取。實(shí)驗(yàn)中對(duì)樣本集中的連續(xù)屬性用極差標(biāo)準(zhǔn)化方法進(jìn)行預(yù)處理，見式(9)：

(9)

處理后的變化區(qū)間在[0,1]之間，以方便算法的處理。

第1、2個(gè)樣本集是Monks難題，它一共有3組樣本集，每一組樣本集都有自己的專門的訓(xùn)練樣本和測(cè)試樣本，是國際上第一次用來比較學(xué)習(xí)算法的標(biāo)準(zhǔn)樣本，本文采用了其中的兩個(gè)樣本集monks-1、monks-3，每個(gè)樣本集均分為兩類，其中monks-3訓(xùn)練樣本集中有5%的離群數(shù)據(jù)；第3個(gè)樣本集是tic-tac-toe游戲樣本集，數(shù)據(jù)集中的樣本是對(duì)tic-tac-toe游戲最后結(jié)束時(shí)所有可能造型結(jié)果的編碼。第4個(gè)澳大利亞信用憑證樣本集(Australian Credit Approval)，描寫的是信用卡的應(yīng)用記錄，樣本屬性的真實(shí)值全部被符號(hào)化，分為兩大類：正類307個(gè)樣本、負(fù)類383個(gè)樣本。

表1 實(shí)驗(yàn)樣本集的組成

(3) 分類器中的參數(shù)選擇

KNDC方法同樣面臨懲罰因子C和核參數(shù)δ的優(yōu)化選取問題，由于這兩個(gè)參數(shù)與樣本本身的分布密切相關(guān)，所以具有一般指導(dǎo)意義的共性選擇方法不是很多見[12-13]，本文采用試探法選擇核分類器的參數(shù)。通過對(duì)表1中各訓(xùn)練樣本選用不同的懲罰因子和核參數(shù)的組合反復(fù)實(shí)驗(yàn)。實(shí)驗(yàn)中對(duì)懲罰因子的選擇，并不要求支撐向量的個(gè)數(shù)為零或者不再變化，而是只要求分類器滿足穩(wěn)定性條件，并且懲罰因子的改變對(duì)支撐向量、邊界支撐向量數(shù)目影響不大即可。因?yàn)檫^多考慮懲罰因子對(duì)分類器的影響，其一意味著使用了可分模型；其二增加了參數(shù)選擇的難度。這是不可取的。實(shí)驗(yàn)結(jié)果如圖1、圖2所示。

圖1、圖2分別說明了分類準(zhǔn)確率與分類器中的兩個(gè)重要參數(shù)的關(guān)系。圖1說明：當(dāng)懲罰因子C一定時(shí)，分類準(zhǔn)確率隨sigma的變化情況。sigma在[0.1,1.0]區(qū)間變化時(shí)，若分類準(zhǔn)確率缺省，則表示當(dāng)前的分類算法無法實(shí)現(xiàn)樣本集的分類，并且，從圖1不難發(fā)現(xiàn)，所有四個(gè)樣本集的曲線都向上凸，說明在當(dāng)前的條件，其分類準(zhǔn)確率存在最優(yōu)。當(dāng)從圖1中得到分類準(zhǔn)確率最好的參數(shù)sigma的值后，反過來求在sigma一定時(shí)，分類準(zhǔn)確率隨懲罰因子C的變化情況，如圖2所示，特別值得注意的是，當(dāng)懲罰因子超過一定的值后，分類準(zhǔn)確率不再受其影響，即分類算法很穩(wěn)定，這一現(xiàn)象說明：雖然分類算法中參數(shù)初始值的選擇具有一定的偶然性，但取值是合理的。綜合考慮圖1、圖2，可以比較方便地確定算法中的兩個(gè)重要參數(shù)，懲罰因子C=5時(shí)，樣本monks1、monks3、tic-tac-toe、credit的參數(shù)sigma分別取：0.7、0.4、0.7、0.9。

圖1 分類準(zhǔn)確率與sigma的關(guān)系

圖2 分類準(zhǔn)確率與懲罰因子的關(guān)系

(4) 實(shí)驗(yàn)結(jié)果及分析

表2給出了KNDC算法、C4.5算法、文獻(xiàn)[2-4]算法的錯(cuò)分率比較結(jié)果。由于C4.5是一種決策分類算法，沒有用到“度量”的概念，并且該算法根據(jù)信息增益來約簡(jiǎn)和選擇分類屬性，不一定能保持最優(yōu)，所以對(duì)其中3個(gè)樣本集的錯(cuò)分率最高，對(duì)于樣本集monks-3的錯(cuò)分率稍低于文獻(xiàn)[2]；文獻(xiàn)[2]首先把待比較的屬性轉(zhuǎn)換成“串”，最后采用類似海明距離進(jìn)行度量，文獻(xiàn)[3]是用待比較的兩個(gè)屬性相對(duì)同一個(gè)類屬性的條件概率之差的平方加權(quán)的方式進(jìn)行度量，文獻(xiàn)[2-3]都是基于樣本屬性是相互獨(dú)立的假設(shè)，復(fù)略了屬性之間的關(guān)聯(lián)性，均采用RBF分類器。文獻(xiàn)[4]是把待比較的兩個(gè)向量的各維屬性間的“距離”構(gòu)成一個(gè)相異性矩陣，并用Hadamard內(nèi)積近似計(jì)算矩陣[4]，最后通過對(duì)結(jié)果優(yōu)化尋找類別判定的估計(jì)函數(shù)，文獻(xiàn)[4]雖然考慮了屬性間的關(guān)聯(lián)性，但算法的計(jì)算復(fù)雜。文獻(xiàn)[4]及本文算法KNDC均采用SVM分類器。對(duì)于credit、tic-tac-toe、monks-1這些屬性間的關(guān)聯(lián)性比較強(qiáng)的樣本，KNDC和文獻(xiàn)[4]的算法錯(cuò)分率遠(yuǎn)低于其他三個(gè)算法，并且對(duì)于前兩個(gè)樣本集KNDC算法的錯(cuò)分率低于文獻(xiàn)[4]的算法，事實(shí)上對(duì)于monks-1樣本， KNDC算法僅有一個(gè)樣本被錯(cuò)分，而對(duì)于異構(gòu)樣本集credit，KNDC算法的錯(cuò)分率在所有參與比較的算法中最低，這充分說明考慮樣本屬性間關(guān)聯(lián)性的重要性；樣本集monks-3比較特殊，有5%的離群數(shù)據(jù)[2，4]，KNDC方法的錯(cuò)分率高于文獻(xiàn)[3-4]，而低于文獻(xiàn)[2]和著名的C4.5算法，可見KNDC算法具有一定的抗離群數(shù)據(jù)干擾能力。

表2 不同方法的錯(cuò)分率比較

4 分類方法的應(yīng)用示例

網(wǎng)絡(luò)實(shí)際環(huán)境中正常連接記錄往往要比異常攻擊記錄多得多，即異常連接記錄占整個(gè)網(wǎng)絡(luò)連接記錄的比例極小?；谶@樣的認(rèn)識(shí)，完全可以認(rèn)為網(wǎng)絡(luò)異常檢測(cè)就是一個(gè)發(fā)現(xiàn)離群數(shù)據(jù)的過程。著名的KDD CUP 1999樣本集，通常使用它的10%的子集來測(cè)試方法的性能,子集中有23種攻擊方式，歸成四大類入侵DOS、Probe、R2L和U2R，已有文獻(xiàn)研究表明[14]，該樣本集是一個(gè)分布極度不平衡的樣本，并且樣本集屬性組成比較復(fù)雜，含有大量的語義數(shù)據(jù)，如TCP、ICMP、SF等，又包含有大量的連續(xù)屬性。實(shí)驗(yàn)中分別按1%、2%、3%、4%、5%、10%的比例來選取不同類別的攻擊樣本，選取樣本總數(shù)分別為1 000、2 000、3 000、4 000和5 000的5個(gè)獨(dú)立的樣本子集，實(shí)驗(yàn)中每間隔10條抽取一條作為訓(xùn)練樣本，剩余的作為測(cè)試樣本，實(shí)驗(yàn)中用文獻(xiàn)[13]的兩個(gè)指標(biāo)檢測(cè)正確率和錯(cuò)分率來衡量方法的實(shí)用價(jià)值。檢測(cè)正確率和錯(cuò)分率隨異常樣本所占比例的變化如圖3、圖4所示，圖中的檢測(cè)正確率和錯(cuò)分率是在5個(gè)樣本子集上進(jìn)行10次實(shí)驗(yàn)的統(tǒng)計(jì)平均。

圖3 檢測(cè)率隨異常比例的變化圖

圖4 錯(cuò)報(bào)率隨異常比例的變化圖

由于U2R類攻擊的樣本總數(shù)為48條，所以U2R所占比例最多只能達(dá)到5%，即為不平衡數(shù)據(jù)。從圖3、圖4可以看出，本文的分類方法對(duì)于U2R、Probe和R2L三類攻擊的檢測(cè)結(jié)果趨勢(shì)明顯，檢測(cè)率隨著異常樣本所占比例的升高呈下降趨勢(shì)，錯(cuò)報(bào)率隨著比例的升高有微弱的上升趨勢(shì)，指標(biāo)總體上比較理想，說明算法針對(duì)異構(gòu)屬性數(shù)據(jù)集分類問題的優(yōu)越性、具有一定的應(yīng)用價(jià)值。對(duì)于比例為3%、4%的DOS類攻擊的檢測(cè)正確率和錯(cuò)報(bào)率都有一個(gè)明顯的突變，通過深入研究樣本數(shù)據(jù)的組成發(fā)現(xiàn)，主要是因?yàn)樵谒?個(gè)樣本子集中，隨機(jī)抽取的這兩個(gè)比例值的DOS類攻擊樣本大多只有neptune和smurf兩類，這兩類樣本，特別是neptune同正常網(wǎng)絡(luò)連接記錄normal重復(fù)率極高[14-15]，造成正常和異常間的分類邊界不清晰，樣本的拒識(shí)率增加，最終造成檢測(cè)準(zhǔn)確率急激下降、錯(cuò)報(bào)率急激上升。

5 結(jié)束語

本文研究了語義數(shù)據(jù)的分類問題，提出了一種語義數(shù)據(jù)的核分類方法，并向語義數(shù)據(jù)和連續(xù)屬性的異構(gòu)屬性數(shù)據(jù)集進(jìn)行了拓展，有意義地拓展了非線性支撐向量機(jī)的適用范圍。從實(shí)驗(yàn)中發(fā)現(xiàn)算法的總體性能優(yōu)于著名的C4.5算法，對(duì)大多數(shù)標(biāo)準(zhǔn)樣本集的分類指標(biāo)優(yōu)于文獻(xiàn)[2-4]，特別是對(duì)于異構(gòu)屬性數(shù)據(jù)集的分類，在參預(yù)比較的各種分類方法中，KNDC方法的指標(biāo)最佳、性能最優(yōu)。并通過在異常檢測(cè)領(lǐng)域的應(yīng)用研究發(fā)現(xiàn)，KNDC方法具有一定的抗離群數(shù)據(jù)干擾能力和處理不平衡數(shù)據(jù)的能力，但對(duì)標(biāo)準(zhǔn)樣本集的仿真實(shí)驗(yàn)說明，KNDC方法的抗離群數(shù)據(jù)干擾能力不及文獻(xiàn)[3-4]，如何進(jìn)一步提高KNDC方法的抗離群數(shù)據(jù)干擾能力是下一步的研究重點(diǎn)。

[1] Minho Kim,R.S.Ramakrishna,Projected Clustering for Categorical Datasets[J].Pattern Recognition Letters,2006,27：1405-1417.

[2] F.Esposito,D.Malerba,V.Tamma,H.H.Bock,Classical resemblance measure,in：H.-H.Bock,E.Diday(Eds.),Analysis of Symbolic Data,Springer[C]//Berlin,2000,139-152.

[3] C.Stanfill,D.Waltz,Towards memory-based reasoning[J].Commun,ACM,1986, 29(12)：1213-1228.

[4] Victor Cheng,Chun-Hung Li,James T.Kwokb,Chi-Kwong Lic,Dissimilarity learning for nominal data[J].Pattern Recognition, 2004,37：1471-1477.

[5] J.C.Gower,P.Legendre,Metric and Euclidean properties of dissimilarity coefficients[J].J.Classif.1986,3：5-48.

[6] H.Spath,Cluster Analysis Algorithm for Data Reduction and Classification[J].Ellis Horwood,Chichester,1980.

[7] Burges J.C.,A tutorial on support vector machine for pattern recognition[J].Data Mining and Knowledge Discoverty,1998,2(2)：121-167.

[8] V apnik V N. Statistical learning theo ry [M]. New York：John W iley & Sons, INC, 1998.

[9] Scholkopf B, MIka S, Burges C, et al. Input Space Versus Feature Space in Kernel-based Methods [J]. IEEE Trans on Neural Networks, 1999,10(5)：1000-1017.

[10] Defeng Wang,Daniel S.Yeung,Eric C.C.Tsang,Weighted Mahalanobis Distance Kernels for Support Vector Machines[J]. IEEE Transaction on Neural networks,2007,18：1453-1462.

[11] Richard O.Duda,Peter E.Hart,David G.Stork,Pattern Classification,John Wiley,2001：318-347.

[12] 韓先培,趙軍. 基于Wikipedia 的語義元數(shù)據(jù)生成[J].中文信息學(xué)報(bào),2009,23(2)：108-114.

[13] 李文法,段毅,劉 悅,孫春來. 一種面向流分類的特征選擇算法[J].中文信息學(xué)報(bào),2009,23(3)：51-57.

[14] 孫濟(jì)洲.網(wǎng)絡(luò)入侵檢測(cè)技術(shù)的研究[D].博士學(xué)位論文,天津大學(xué),2003.

[15] 李志華,王士同，等.基于離群聚類的異常檢測(cè)研究[J].系統(tǒng)工程與電子技術(shù),2009,31(5)：1227-1230.(LI Zhi-hua,WANG Shi-tong,Clustering with outliers-based anomalous intrusion detection[J].Systems Engineering and Electronics,2009,31(5)：1227-1230.

[16] UCI repository of machine learning database[EB/OL]. http://www.ics.UCI.edu/～mlearn/MLRepository.html,1998.