空間相關性分析的符號數據分類方法*

付康安，王文劍，郭虎升

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

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

1 引言

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

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

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

2 空間相關性分析的符號數據分類方法

2.1 屬性與標簽的空間相關性分析

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

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

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

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

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

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

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

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

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

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

2.2 基于空間相關性分析的分類方法

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

2.2.1 SCA_SVM算法

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

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

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

步驟4根據O-I(xi)或O-H(xi)將測試集TestX轉換為相應的數值數據OTestX(xi),用得到的分類超平面f進行分類測試。調參數得到最優的分類的超平面f*，并統計實驗結果。

2.2.2 SCA_KNN算法

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

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

步驟3根據O-I(xi)或O-H(xi)將測試集TestX轉換為相應的數值數據OTestX(xi)。

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

3 實驗結果與分析

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

3.1 數據集與性能評價指標

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

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

Table 1 Description of experimental data sets from UCI表1 UCI上的實驗數據集描述

評價指標。其定義如下：

3.2 結果比較與分析

3.2.1 兩種相關性度量的比較

Table 2 Confusion matrix表2 混淆矩陣

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

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

3.2.2 與Chen方法的比較

Chen方法[12]是一種基于核方法的分類方法，可以用于樸素貝葉斯分類器（NBC）、K-最近鄰（KNN）等模型中，具有良好的分類性能。本小節將SCA_SVM和SCA_KNN與之比較，比較結果如表3所示。由于文獻[12]中沒有給出詳細的算法，只列出了結果。因此，這里只在6個相同的數據集上進行實驗結果的對比，最優的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上要好。尤其在數據集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個數據集上的結果更優，而在另外的dermatology和breast_cancer上相差不大。

3.2.3 與其他方法的比較

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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