付康安，王文劍，郭虎升

1.山西大學 計算機與信息技術(shù)學院，太原 030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原 030006

1 引言

在現(xiàn)實生活中，符號數(shù)據(jù)（categorical data）[1-2]在實際應(yīng)用領(lǐng)域普遍存在，例如在生物醫(yī)學中，構(gòu)成DNA序列的核苷酸屬性由A、T、G和C四種離散的符號編碼而成，血型分為A、B、O和AB型等。這類數(shù)據(jù)的屬性取值是一個有限的符號集合，是定性的，僅描述數(shù)據(jù)的特征，不提供實際的大小和數(shù)量，包括標稱屬性和序數(shù)屬性。其中，標稱屬性的屬性值彼此之間沒有順序，只有兩種狀態(tài)，即“等”或“不等”，例如“性別”屬性，有“男”和“女”之分；而序數(shù)屬性的屬性值彼此之間有順序，但相互之間的差值是未知的，屬性值關(guān)系是“大于”“小于”“等于”，如“飲料量”屬性有“大杯”“中杯”“小杯”等屬性值，很明顯，“大杯”和“小杯”之間的差異性要比“大杯”和“中杯”之間的差異性大。盡管在公開的數(shù)據(jù)集上下載的符號數(shù)據(jù)集中大多數(shù)是1、2、3等數(shù)字，但那只是表示不同的屬性值，僅僅是為了方便存儲等考慮，不能進行定量分析。

由于符號數(shù)據(jù)缺乏數(shù)值數(shù)據(jù)固有的幾何特性，因此對于數(shù)值數(shù)據(jù)分析的理論和算法無法直接應(yīng)用在符號數(shù)據(jù)上。目前關(guān)于符號數(shù)據(jù)的分析主要集中在聚類分析方面[3-7]。對于符號數(shù)據(jù)的分類，較經(jīng)典的算法有決策樹算法、貝葉斯分類器，其中代表性的算法有C4_5決策樹算法[8-9]、樸素貝葉斯分類器[1-2]（naive Bayes classifier，NBC），也有采用0-1相異性度量的K-最近鄰算法[2,10]（K-nearest neighbor，KNN）。盡管這些算法能夠進行符號數(shù)據(jù)分類，但是這些方法要么簡單地假定符號屬性之間是相互獨立的，而這又與實際情況不符；要么通過簡單的0-1相異性度量或者其擴展版本，但這種度量方法并不能很好地揭示符號數(shù)據(jù)的內(nèi)在組成結(jié)構(gòu)，這些問題都會影響最終的分類結(jié)果。同時，相較于數(shù)值數(shù)據(jù)分類算法，符號數(shù)據(jù)的分類算法在分類性能上仍然有很大的提升空間。因而，為了有效地提高符號數(shù)據(jù)的分類性能，研究符號數(shù)據(jù)的分類方法仍然有很大的應(yīng)用價值。

綜上所述，由于符號數(shù)據(jù)缺乏數(shù)值數(shù)據(jù)固有的幾何特性，使得那些性能優(yōu)越的數(shù)值數(shù)據(jù)的分類方法無法直接處理符號數(shù)據(jù)。為了有效提高符號數(shù)據(jù)的分類性能，通過深入挖掘符號數(shù)據(jù)不同屬性值與標簽之間可能存在的空間結(jié)構(gòu)關(guān)系，結(jié)合互信息和條件熵信息度量方法，定義了一種符號數(shù)據(jù)空間表示方法。該方法既能夠保留符號數(shù)據(jù)的原始信息，也體現(xiàn)出屬性值與標簽之間的相關(guān)性，還能夠有效地度量不同屬性值之間的差異性。在此基礎(chǔ)上，分別與SVM（support vector machine）[11]和KNN模型分類器相融合，提出一種基于空間相關(guān)性分析的符號數(shù)據(jù)分類方法SCA_SVM（SVM classification algorithm based on space correlation analysis）算法和SCA_KNN（KNN classification algorithm based on space correlation analysis）算法。在UCI標準數(shù)據(jù)集上，通過與其他傳統(tǒng)的符號數(shù)據(jù)分類方法進行實驗對比，結(jié)果表明SCA_SVM算法和SCA_KNN算法能夠有效地提高分類性能。

2 空間相關(guān)性分析的符號數(shù)據(jù)分類方法

2.1 屬性與標簽的空間相關(guān)性分析

給定一個樣本集D={(x1,y1),(x2,y2),…,(xn,yn)}其,中xi為樣本，yi∈{1,2,…,C}為樣本標簽，A={a1,a2,…,am}是m個特征屬性的集合，aj的取值范圍為{aj1,為變量（對應(yīng)當前屬性可取值的個數(shù)，|d|≥ 2），xij是樣本xi在特征屬性aj下的符號屬性值。

為了進一步計算符號數(shù)據(jù)特征屬性中不同屬性值之間的距離或相似度，首先將原始符號數(shù)據(jù)的特征屬性通過獨熱編碼（直觀來說就是有多少個狀態(tài)就有多少比特，而且只有一個比特為1，其他全為0的一種碼制）的方式映射到歐式空間，也就是進行特征擴容，這樣屬性值之間的距離就可以在歐式空間中進行幾何運算。在此基礎(chǔ)上，為了更好地度量不同屬性值之間的距離或差異性，通過分析屬性值和標簽之間的相關(guān)性，定義了一個符號數(shù)據(jù)量化表示方法。

在新的表示方法中，首先分析屬性值和標簽之間的相關(guān)性，這里借鑒互信息和條件熵兩種信息度量方法，定義了兩個不同的相關(guān)性計算方法I(·)和H(·)。特征屬性aj下屬性值ajk和標簽c的相關(guān)性和計算方法如下：

其中，p(ajk)、p(yc)、p(yc,ajk)和p(yc|ajk)分別表示屬性aj取值為ajk的概率，標簽yi取值為c的概率，ajk與yc的聯(lián)合概率和條件概率。依據(jù)大數(shù)定律，這里使用頻率來近似表示相應(yīng)的概率。計算方法如下：

式中，IF(·)是一個指示函數(shù)，即IF(tr ue)=I1,F(false)=0。

由式（1）～式（3）可以得到兩個屬性值ajk與標簽的相關(guān)性矩陣O-I(ajk)和O-H(ajk)，表示形式如下：

對于特征屬性aj，其不同屬性值的O-I(aj)表示過程如下所示：

O-H(aj)的形成過程與O-I(aj)類似，其展開形式如下：

對于樣本xi，基于空間相關(guān)性分析的O-I(xi)和O-H(xi)表示形式如下：

通過挖掘符號數(shù)據(jù)不同屬性值與標簽之間的相關(guān)性，定義一個符號數(shù)據(jù)量化表示方法，該方法不僅可以保持原始符號數(shù)據(jù)的信息完整性，而且能夠有效度量不同屬性值之間的差異性。

2.2 基于空間相關(guān)性分析的分類方法

基于空間相關(guān)性分析的符號數(shù)據(jù)表示方法將符號數(shù)據(jù)特征屬性的屬性值映射到空間表示的結(jié)構(gòu)中，使得傳統(tǒng)的面向數(shù)值數(shù)據(jù)的分類方法都能得到應(yīng)用。本文采用兩種通用的分類模型SVM和KNN，與相關(guān)性度量方法I(·)和H(·)結(jié)合進行分類學習，得到SCA_SVM-I、SCA_SVM-H、SCA_KNN-I、SCA_KNN-H四種模型。

2.2.1 SCA_SVM算法

步驟1對于訓(xùn)練集TrainU，根據(jù)式（1）或式（2）分別計算出各屬性值和各個標簽之間的相關(guān)性或。

步驟2通過空間相關(guān)性分析方法，根據(jù)式（6）或式（7）將符號數(shù)據(jù)重新表示在相關(guān)性矩陣O-I(xi)或O-H(xi)中。

步驟3在新的O-I(xi)或O-H(xi)上用SVM進行訓(xùn)練，得到分類超平面f。

步驟4根據(jù)O-I(xi)或O-H(xi)將測試集TestX轉(zhuǎn)換為相應(yīng)的數(shù)值數(shù)據(jù)OTestX(xi),用得到的分類超平面f進行分類測試。調(diào)參數(shù)得到最優(yōu)的分類的超平面f*，并統(tǒng)計實驗結(jié)果。

2.2.2 SCA_KNN算法

步驟1對于訓(xùn)練集TrainU，根據(jù)式（1）或式（2）分別計算出各屬性值和各個標簽之間的相關(guān)性或。

步驟2通過空間相關(guān)性分析方法，根據(jù)式（6）或式（7）將符號數(shù)據(jù)重新表示在相關(guān)性矩陣O-I(xi)或O-H(xi)中。

步驟3根據(jù)O-I(xi)或O-H(xi)將測試集TestX轉(zhuǎn)換為相應(yīng)的數(shù)值數(shù)據(jù)OTestX(xi)。

步驟4根據(jù)歐氏距離的度量方法，找到最近的K個樣本點，按照投票的方式進行標簽預(yù)測，并統(tǒng)計實驗結(jié)果。

3 實驗結(jié)果與分析

為了驗證算法的有效性，本文將SCA_SVM和SCA_KNN算法應(yīng)用于UCI數(shù)據(jù)集，并與C4_5、NBC、KNN和Chen[12]算法進行比較。由于本文的重點在于如何挖掘不同屬性值和標簽之間的關(guān)系，因此有關(guān)KNN和SVM模型參數(shù)選擇將不在文中具體討論，相關(guān)內(nèi)容可參考文獻[13-14]。這里KNN模型的參數(shù)K取3，SVM模型采用RBF的核函數(shù)，核參數(shù)取1，懲罰參數(shù)c設(shè)置為1 000，本文算法的屬性權(quán)重wj參數(shù)全部設(shè)置為1/m。為了減少實驗的隨機性，所有實驗重復(fù)10次，取均值為實驗結(jié)果。

3.1 數(shù)據(jù)集與性能評價指標

本文選取了UCI數(shù)據(jù)庫[15]上9個常用的符號數(shù)據(jù)集進行實驗分析，如表1所示。

本文采用“微F1”（micro-F1）[2]作為分類性能的

Table 1 Description of experimental data sets from UCI表1 UCI上的實驗數(shù)據(jù)集描述

評價指標。其定義如下：

3.2 結(jié)果比較與分析

3.2.1 兩種相關(guān)性度量的比較

Table 2 Confusion matrix表2 混淆矩陣

其中，nup和ndown分別表示測試準確率大于和小于平均分類性能指標的個數(shù)。

從圖1可以看出，對于相關(guān)性度量方法I(·)和H(·)，從評價指標micro-F1上看，KNN模型分類器，相關(guān)性度量方法I(·)在7個數(shù)據(jù)集上的micro-F1指標更高，其中的3個數(shù)據(jù)集（promote、Hayes-Roth和balance）上優(yōu)勢比較明顯，而在另外的兩個數(shù)據(jù)集(dermatology和Tic-Tac-Toe)上的結(jié)果與度量方法H(·)相差不大。SVM模型分類器，兩種度量方法的micro-F1指標基本一致。從標準差STD上來看，兩種度量方法的STD的差別不太明顯，離散程度基本一致，表明算法的魯棒性較好。

3.2.2 與Chen方法的比較

Chen方法[12]是一種基于核方法的分類方法，可以用于樸素貝葉斯分類器（NBC）、K-最近鄰（KNN）等模型中，具有良好的分類性能。本小節(jié)將SCA_SVM和SCA_KNN與之比較，比較結(jié)果如表3所示。由于文獻[12]中沒有給出詳細的算法，只列出了結(jié)果。因此，這里只在6個相同的數(shù)據(jù)集上進行實驗結(jié)果的對比，最優(yōu)的micro-F1值由下劃線標出。

Fig.1 Comparison of micro-F1 between two measures on same model圖1 兩種度量方法對同類模型micro-F1的比較

Table 3 Comparison of micro-F1 with Chen approaches表3 與Chen方法的micro-F1對比 %

從表3可以看出，本文提出的SCA_SVM算法比Chen提出的基于不同分類器下的6種算法在評價指標micro-F1上要好。尤其在數(shù)據(jù)集balance上的micro-F1值更明顯，相較于KNB（kernel na?ve Bayes）模型提高了10.34%(98.24%-87.90%)，相較于K2NN（kernelK-nearest neighbor）模型提高了28.14%(98.24%-70.10%），相較于KPBC（kernel prototype-based classification）模 型 提 高 了 28.94%(98.24%-69.30%)。SCA_KNN算法比Chen提出的基于KNN模型分類器的K2NN算法以及KPBC算法在4個數(shù)據(jù)集上的結(jié)果更優(yōu)，而在另外的dermatology和breast_cancer上相差不大。

3.2.3 與其他方法的比較

在9個UCI符號數(shù)據(jù)集上，本文4種算法與C4_5決策樹、NBC算法和KNN算法3種傳統(tǒng)的符號數(shù)據(jù)分類算法評價指標micro-F1（均值±標準差）的實驗對比結(jié)果如表4所示。每個數(shù)據(jù)集上最優(yōu)的micro-F1值由下劃線標出，↑表示本文方法比其他3種方法最優(yōu)micro-F1值更好。其中KNN方法采用0-1相異性度量方法計算距離。

從表4可以看出，在采用的9個UCI數(shù)據(jù)集中，相比其他3種算法，本文算法在絕大多數(shù)的數(shù)據(jù)集上的分類性能是最優(yōu)的。其中，基于SVM模型分類器的兩種算法在8個數(shù)據(jù)集上都提高了分類性能，而在另外的breast_cancer上的結(jié)果也與最優(yōu)的結(jié)果相近，差距為-1.44%，在balance上的準確率提高值最大，提高值為27.65%；基于KNN模型分類器的SCA_KNN-I算法在7個數(shù)據(jù)集上都提高了分類性能，在另外的dermatology和breast_cancer上的差距分別為-2.3%和-1.9%，而SCA_KNN-H算法在3個數(shù)據(jù)集（dermatology、Tic-Tac-Toe和splice）上提高了分類性能，在另外5個數(shù)據(jù)集上的結(jié)果與最優(yōu)的結(jié)果相近，僅僅在balance上表現(xiàn)得不是太好。此外，從測試結(jié)果的標準差來看，相比其他3種算法，在micro-F1比較接近的數(shù)據(jù)集promote、vote和breast_cancer上，本文的SCA_SVM和SCA_KNN算法僅僅在breast_cancer上的標準差較大一些，這表明本文算法有更好的穩(wěn)定性。

為了更直觀地觀察各算法的統(tǒng)計分布情況，圖2給出各算法對9個數(shù)據(jù)集micro-F1指標的箱線圖，并在圖中分別用圓圈“○”和星形“*”標注均值和中值。

由圖2可以看出，本文方法在7個數(shù)據(jù)集上的上下限范圍較小，尤其在dermatology、balance、Tic-Tac-Toe和splice上的上下線范圍最小，表現(xiàn)出非常高的穩(wěn)定性。雖然本文方法在Hayes-Roth和breast_cancer的穩(wěn)定性有較小的下降，但更高的上限值表明本文方法具有達到最優(yōu)分類性能的能力，并在大多數(shù)數(shù)據(jù)集上有更高的上限。

為了進一步說明本文算法的有效性，對實驗結(jié)果的評價指標micro-F1進行了T檢驗(T-test)并獲得相應(yīng)的P值(P-values)，一般以P-values＜0.05為顯著，P-values＜0.01為非常顯著。首先，建立假設(shè)H0，SCA_KNN(或SCA_SVM)算法與其他算法之間的micro-F1沒有顯著性差異；假設(shè)H1，SCA_KNN(或SCA_SVM）算法與其他算法之間存在顯著性差異。T-test對評價指標micro-F1產(chǎn)生的P-value如表5、表6所示（大于0.05的P-values值由下劃線標出）。

Table 4 Comparison of micro-F1 index by different algorithms on data sets表4 數(shù)據(jù)集上不同算法的micro-F1指標對比 %

Fig.2 Boxplot of micro-F1 index for different algorithms on 9 data sets圖2 不同算法在9個數(shù)據(jù)集的micro-F1指標的箱線圖

從表5可以看出，絕大多數(shù)的P-values都小于0.05，并且大部分的P-values也都小于0.01，甚至遠小于該值。這說明H0假設(shè)是不成立的，即假設(shè)H1成立，也就是本文的SCA_SVM算法與其他算法之間存在顯著性差異。此外，對于在數(shù)據(jù)集dermatology、vote和breast_cancer上出現(xiàn)的不顯著現(xiàn)象是符合實際情況的，因為從圖2和表4上的結(jié)果可以看出這些數(shù)據(jù)集上的指標micro-F1值比較接近，具有相似的統(tǒng)計分布。

從表6可以看出，絕大多數(shù)的P-values都小于0.05，并且大部分的P-values也都小于0.01，甚至遠小于該值。這說明H0假設(shè)是不成立的，即假設(shè)H1成立，也就是本文的SCA_KNN算法與其他算法之間存在顯著性差異。此外，對于SCA_KNN-H算法出現(xiàn)比較多的不顯著現(xiàn)象也是符合實際情況的，因為從圖2和表4上的結(jié)果可以看出SCA_KNN-H算法的實驗結(jié)果micro-F1與其他算法比較接近。

從上述的實驗分析可以看出，在SVM模型分類器上，SCA_SVM-I算法和SCA_SVM-H算法相對于其他3種傳統(tǒng)的符號數(shù)據(jù)分類算法以及Chen提出的算法具有更高的分類精度，且算法的魯棒性也更好；在KNN模型分類器上，SCA_KNN-I和SCA_KNN-H這兩種算法也比傳統(tǒng)的KNN算法在分類性能上要更好。因此，本文提出的基于空間相關(guān)性的符號數(shù)據(jù)分類方法具有更好的分類性能。

Table 5 P-values produced by T-test for micro-F1 index（SCA_SVM algorithm）表5 T-test對指標micro-F1產(chǎn)生的P-values（SCA_SVM算法）

Table 6 P-values produced by T-test for micro-F1 index（SCA_KNN algorithm）表6 T-test對指標micro-F1產(chǎn)生的P-values（SCA_KNN算法）

4 結(jié)束語

本文針對符號數(shù)據(jù)分類方法分類精度低的問題，充分挖掘了屬性值與標簽的關(guān)聯(lián)信息，提出了一種基于空間相關(guān)性分析的符號數(shù)據(jù)分類方法，通過定義兩種屬性值和標簽的空間相關(guān)性表示方法，不僅可以保持原始符號數(shù)據(jù)的信息完整性，而且能夠有效度量不同屬性值之間的差異性，從而有效提高了符號數(shù)據(jù)的分類性能。另外，本文的研究工作也是對SVM和KNN模型分類器應(yīng)用的擴充。然而，由于在數(shù)據(jù)的再表示過程中，為了保留符號數(shù)據(jù)的完整性，對原始數(shù)據(jù)進行了特征擴容，這就直接提升了原始數(shù)據(jù)集的維度，造成了分類模型復(fù)雜化。在未來的工作中，針對該問題將考慮引入特征選擇的方法或者針對特征屬性設(shè)置閾值，以評價是否對該特征進行特征擴容，從而避免由于維度災(zāi)難導(dǎo)致的模型復(fù)雜化和分類效率降低。