挖掘數(shù)據(jù)模式結(jié)構(gòu)信息的混合數(shù)據(jù)分類(lèi)方法

2

(1.常州輕工職業(yè)技術(shù)學(xué)院 信息工程學(xué)院, 江蘇 常州 213164;2.江南大學(xué) 數(shù)字媒體學(xué)院, 江蘇 無(wú)錫 214122)

0 引言

數(shù)據(jù)分類(lèi)通過(guò)訓(xùn)練帶有標(biāo)簽信息的樣本生成分類(lèi)模型以預(yù)測(cè)未標(biāo)記樣本的歸屬類(lèi)別，是模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘及統(tǒng)計(jì)學(xué)等領(lǐng)域最基本、最重要的問(wèn)題之一。傳統(tǒng)的數(shù)據(jù)分類(lèi)方法，如支持向量機(jī)(Support Vector Machine, SVM)[1-3]、隨機(jī)森林(Random Forest, RF)[4]、k近鄰算法(k-Nearest Neighbor, kNN)[5]、決策樹(shù)(C4.5)[6]以及樸素貝葉斯(Naive Bayesian, NB)[7]等，在訓(xùn)練階段利用數(shù)據(jù)的物理特征(如距離、相似性等)構(gòu)建數(shù)據(jù)分類(lèi)模型，在分類(lèi)階段，通過(guò)確定測(cè)試樣本與所建立數(shù)據(jù)分類(lèi)模型之間的相似性預(yù)測(cè)測(cè)試樣本的真實(shí)標(biāo)簽類(lèi)型。在大多數(shù)情況下，傳統(tǒng)的分類(lèi)方法僅僅依靠數(shù)據(jù)之間的距離、相似度等物理特征信息構(gòu)建數(shù)據(jù)分類(lèi)模型，事實(shí)上，實(shí)際數(shù)據(jù)集中的每個(gè)數(shù)據(jù)并不是孤立的，數(shù)據(jù)之間存在關(guān)聯(lián)，數(shù)據(jù)整體上都會(huì)呈現(xiàn)一定的模式結(jié)構(gòu)，而且數(shù)據(jù)模式結(jié)構(gòu)中蘊(yùn)含著豐富的數(shù)據(jù)關(guān)聯(lián)信息[8-10]。Thiago等[11]提出一種基于網(wǎng)絡(luò)的高層次數(shù)據(jù)分類(lèi)方法，該方法在建立的復(fù)雜網(wǎng)絡(luò)中通過(guò)挖掘數(shù)據(jù)相互間的關(guān)聯(lián)信息探索網(wǎng)絡(luò)的同質(zhì)性、聚集系數(shù)以及度等網(wǎng)絡(luò)屬性捕捉隱藏的數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)信息，將數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)信息與數(shù)據(jù)物理特征相結(jié)合形成一種智能分類(lèi)方法；Sun等[12]針對(duì)傳統(tǒng)推薦系統(tǒng)并未考慮社交網(wǎng)絡(luò)中各個(gè)用戶之間的關(guān)系，提出社交正則化方法整合用戶間的朋友等社交關(guān)系；Jiang等[13]研究時(shí)尚、建筑及漫畫(huà)等不同數(shù)據(jù)模式，針對(duì)現(xiàn)有大部分風(fēng)格分類(lèi)方法從數(shù)據(jù)局部模式中提取的鑒別特征過(guò)于多樣化導(dǎo)致較差的分類(lèi)性能，提出賦予不同特征相應(yīng)權(quán)重的一致風(fēng)格聚集自動(dòng)編碼策略學(xué)習(xí)魯棒數(shù)據(jù)風(fēng)格特征表示。

圖1展示了傳統(tǒng)分類(lèi)方法用于實(shí)際數(shù)據(jù)分類(lèi)過(guò)程中存在的不足。假設(shè)有一數(shù)據(jù)集包含三類(lèi)數(shù)據(jù)A、B及C，運(yùn)用傳統(tǒng)分類(lèi)技術(shù)對(duì)這三類(lèi)數(shù)據(jù)進(jìn)行訓(xùn)練并構(gòu)建數(shù)據(jù)分類(lèi)模型。當(dāng)向已建好的數(shù)據(jù)分類(lèi)器輸入測(cè)試樣本A1-t時(shí)(圖1(b))，由于傳統(tǒng)分類(lèi)方法僅僅利用數(shù)據(jù)物理特征信息構(gòu)建數(shù)據(jù)分類(lèi)器，從顏色特征角度看，測(cè)試樣本A1-t與B1、C1樣本有著相同的顏色特征，它們之間有著極高的相似度，此時(shí)A1-t將被歸為紅色一類(lèi)而不能獲得真實(shí)的標(biāo)簽類(lèi)型A。如果在構(gòu)建數(shù)據(jù)分類(lèi)器的過(guò)程中還考慮到訓(xùn)練樣本之間的模式結(jié)構(gòu)關(guān)系，如從整體的角度看，A1、A2、A3它們都是圓，共同組成圓類(lèi)A，它們之間的關(guān)聯(lián)比較密切。將樣本之間的關(guān)聯(lián)信息用于數(shù)據(jù)分類(lèi)模型的建立，構(gòu)建的數(shù)據(jù)分類(lèi)器將會(huì)正確地對(duì)測(cè)試樣本A1-t進(jìn)行分類(lèi)。因此，將各種經(jīng)典的分類(lèi)技術(shù)用于實(shí)際數(shù)據(jù)分類(lèi)時(shí)除了應(yīng)考慮數(shù)據(jù)物理特征外還應(yīng)有效地結(jié)合數(shù)據(jù)間的關(guān)聯(lián)等這樣一層模式結(jié)構(gòu)關(guān)系，充分利用模式結(jié)構(gòu)關(guān)系中數(shù)據(jù)間的關(guān)聯(lián)作用信息，這樣才能符合實(shí)際狀況下數(shù)據(jù)分類(lèi)并保證優(yōu)越分類(lèi)性能。

圖1 傳統(tǒng)分類(lèi)方法的分類(lèi)過(guò)程

本文將僅僅利用數(shù)據(jù)物理特征信息的傳統(tǒng)分類(lèi)技術(shù)作為普通分類(lèi)方法，將挖掘并采用數(shù)據(jù)關(guān)聯(lián)信息的分類(lèi)技術(shù)作為高級(jí)分類(lèi)方法，基于這兩種類(lèi)型的分類(lèi)方法，針對(duì)數(shù)據(jù)間相互關(guān)聯(lián)的事實(shí)，提出一種挖掘數(shù)據(jù)模式結(jié)構(gòu)信息的混合數(shù)據(jù)分類(lèi)方法(HDCM)。HDCM將輸入的訓(xùn)練樣本映射成復(fù)雜網(wǎng)絡(luò)，在復(fù)雜網(wǎng)絡(luò)中挖掘數(shù)據(jù)模式結(jié)構(gòu)信息(網(wǎng)絡(luò)節(jié)點(diǎn)效率、影響力)用于構(gòu)建高級(jí)分類(lèi)方法。使用任意一種傳統(tǒng)分類(lèi)方法以及高級(jí)分類(lèi)方法分別計(jì)算測(cè)試樣本對(duì)所有數(shù)據(jù)類(lèi)型的隸屬度，利用模糊分類(lèi)技術(shù)將測(cè)試樣本歸為具有最大隸屬度的數(shù)據(jù)類(lèi)中，從而實(shí)現(xiàn)數(shù)據(jù)分類(lèi)。由于HDCM考慮了數(shù)據(jù)關(guān)聯(lián)信息，數(shù)據(jù)分類(lèi)的泛化性能也有了明顯提高。

1 高級(jí)分類(lèi)模型描述

本文所提的數(shù)據(jù)分類(lèi)模型由傳統(tǒng)分類(lèi)方法和高級(jí)分類(lèi)方法混合而成，這里主要介紹構(gòu)建高級(jí)分類(lèi)模型的基礎(chǔ)工作，包括構(gòu)建k近鄰復(fù)雜網(wǎng)絡(luò)、確定有別于數(shù)據(jù)物理特征的數(shù)據(jù)模式結(jié)構(gòu)特征：網(wǎng)絡(luò)節(jié)點(diǎn)與子網(wǎng)絡(luò)的效率以及節(jié)點(diǎn)影響力。

1.1 復(fù)雜網(wǎng)絡(luò)

在建立復(fù)雜網(wǎng)絡(luò)用于數(shù)據(jù)分類(lèi)的所有方法中，基于k近鄰算法的復(fù)雜網(wǎng)絡(luò)是最常使用的方法[8,11,14]，且能夠方便、簡(jiǎn)單地表達(dá)數(shù)據(jù)之間的關(guān)聯(lián)，其過(guò)程可描述如下：對(duì)于輸入的整個(gè)訓(xùn)練集X={x1,x2,…,xN}中某一樣本xi，xi∈Rd，選取與其距離最小的前k個(gè)樣本xj，這里的距離為歐氏距離。如果樣本xi與樣本xj有相同標(biāo)簽，即Lxi=Lxj，則樣本xi可關(guān)聯(lián)于樣本xj，記為xi→xj，對(duì)應(yīng)于復(fù)雜網(wǎng)絡(luò)則可建立節(jié)點(diǎn)i到節(jié)點(diǎn)j的有向邊eij，節(jié)點(diǎn)i為有向邊eij的起始點(diǎn)，節(jié)點(diǎn)j為有向邊eij的結(jié)束點(diǎn)。賦予復(fù)雜網(wǎng)絡(luò)中不同有向邊相應(yīng)權(quán)重ωij，使得當(dāng)節(jié)點(diǎn)間的距離越小時(shí)權(quán)重ωij越大，權(quán)重ωij定義如下：

(1)

其中:ωij取值范圍為(0,1)，N為復(fù)雜網(wǎng)絡(luò)所有節(jié)點(diǎn)數(shù)，即訓(xùn)練樣本總數(shù)，dij為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離。

當(dāng)輸入的數(shù)據(jù)集包含L類(lèi)數(shù)據(jù)，即C={c1,c2,…,cL}，由利用k近鄰算法建立復(fù)雜網(wǎng)絡(luò)的過(guò)程可知，建立的復(fù)雜網(wǎng)絡(luò)包含L個(gè)子網(wǎng)絡(luò)，即CN={cn1,cn2,…,cnL}，且子網(wǎng)絡(luò)之間無(wú)關(guān)聯(lián)，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)i與樣本xi相對(duì)應(yīng)。

1.2 模式結(jié)構(gòu)效率特征

除了顏色、距離等物理特征信息外，數(shù)據(jù)的模式結(jié)構(gòu)關(guān)系中蘊(yùn)含著豐富的數(shù)據(jù)關(guān)聯(lián)信息[15-17]，應(yīng)該挖掘并將數(shù)據(jù)關(guān)聯(lián)信息用于數(shù)據(jù)分類(lèi)。如上述描述傳統(tǒng)方法分類(lèi)的例子中(圖1)，如果僅依據(jù)顏色可將數(shù)據(jù)分為紅、綠、藍(lán)三類(lèi)，建立的分類(lèi)模型將不能正確分類(lèi)測(cè)試樣本A1-t，若進(jìn)一步考慮數(shù)據(jù)間的關(guān)聯(lián)作用，可將數(shù)據(jù)分為圓、正方形、正六邊形三類(lèi)，按照2.1節(jié)可建立圓之間的連接、正方形之間的連接以及正六邊形之間的連接三個(gè)子網(wǎng)絡(luò)組成復(fù)雜網(wǎng)絡(luò)，從而建立的分類(lèi)模型可使得測(cè)試樣本A1-t獲得真實(shí)標(biāo)簽類(lèi)型。賦予復(fù)雜網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)效率概念以區(qū)別網(wǎng)絡(luò)中的其他節(jié)點(diǎn)，建立數(shù)據(jù)模式結(jié)構(gòu)關(guān)系中的網(wǎng)絡(luò)效率特征。社交網(wǎng)絡(luò)中最常采用PageRank方法[18-19]計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)的聲譽(yù)，其基本思想是網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)連接其他節(jié)點(diǎn)數(shù)越多，說(shuō)明該節(jié)點(diǎn)聲譽(yù)越高；網(wǎng)絡(luò)中其他節(jié)點(diǎn)連接某個(gè)節(jié)點(diǎn)越多，說(shuō)明該節(jié)點(diǎn)聲譽(yù)越高，本文復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)效率計(jì)算方法正是源于PageRank方法。為了充分考慮節(jié)點(diǎn)之間的關(guān)聯(lián)作用，對(duì)于復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)i的效率定義如下：

(2)

(3)

(4)

(5)

其中:Ni代表以節(jié)點(diǎn)i為起始點(diǎn)的有向邊個(gè)數(shù)，Nk代表以節(jié)點(diǎn)i為結(jié)束點(diǎn)的有向邊個(gè)數(shù)，Nd代表節(jié)點(diǎn)i與其他節(jié)點(diǎn)相關(guān)聯(lián)的有向邊個(gè)數(shù)，即Nd=Ni+Nk，ξ為一較小值，賦予離群點(diǎn)或噪聲點(diǎn)較小的效率，其對(duì)于分類(lèi)樣本所起的作用可忽略不計(jì)。

當(dāng)計(jì)算出復(fù)雜網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)效率后，與訓(xùn)練集每一類(lèi)數(shù)據(jù)相對(duì)應(yīng)的子網(wǎng)絡(luò)cnl效率便可確定，子網(wǎng)絡(luò)效率定義如下：

(6)

其中:φcnl代表與訓(xùn)練集第cl類(lèi)數(shù)據(jù)相對(duì)應(yīng)的子網(wǎng)絡(luò)cnl的效率，Ncnl為子網(wǎng)絡(luò)cnl包含的節(jié)點(diǎn)個(gè)數(shù)。復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)及子網(wǎng)絡(luò)的效率為基于挖掘數(shù)據(jù)模式結(jié)構(gòu)信息的高級(jí)分類(lèi)模型預(yù)測(cè)測(cè)試樣本標(biāo)簽提供可靠依據(jù)，2.4節(jié)將有詳細(xì)內(nèi)容介紹。

1.3 模式結(jié)構(gòu)影響力特征

在利用數(shù)據(jù)模式結(jié)構(gòu)信息建立高級(jí)分類(lèi)模型的過(guò)程中，訓(xùn)練集中的每個(gè)數(shù)據(jù)樣本對(duì)分類(lèi)未標(biāo)記測(cè)試樣本所起的作用大小各不相同，有的數(shù)據(jù)樣本對(duì)預(yù)測(cè)結(jié)果可能起決定性作用，有的數(shù)據(jù)樣本影響力可能很弱[18-19]。這里定義復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)影響力如下：

(7)

公式(7)中1/N表示訓(xùn)練樣本是均勻分布的，而大多情況下實(shí)際數(shù)據(jù)集中的數(shù)據(jù)并不是均勻分布，每一個(gè)數(shù)據(jù)樣本在一定距離范圍內(nèi)被不同個(gè)數(shù)的其他數(shù)據(jù)樣本所包圍[21]，類(lèi)似的，復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)在一定距離范圍內(nèi)被不同個(gè)數(shù)的其他節(jié)點(diǎn)所包圍，由此產(chǎn)生節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的濃度概念。復(fù)雜網(wǎng)絡(luò)中第i個(gè)節(jié)點(diǎn)濃度定義為:

(8)

其中:dc代表截?cái)嗑嚯x，可根據(jù)實(shí)際的數(shù)據(jù)分類(lèi)效果手動(dòng)確定，或者使節(jié)點(diǎn)在dc距離范圍內(nèi)被占復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)3%～5%的其他節(jié)點(diǎn)包圍[21]，當(dāng)dij-dc<0時(shí)χ(·)=1，否則χ(·)=0。在復(fù)雜網(wǎng)絡(luò)中以傳播節(jié)點(diǎn)濃度的方式計(jì)算每個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的真實(shí)影響力大小，定義如下：

(9)

當(dāng)滿足以下迭代條件時(shí)計(jì)算節(jié)點(diǎn)真實(shí)影響力的迭代過(guò)程將會(huì)停止。

(10)

其中:θ的取值可根據(jù)實(shí)際數(shù)據(jù)集分類(lèi)的效果手動(dòng)選取，根據(jù)大量的實(shí)驗(yàn)結(jié)果表明θ=10-4即可。

1.4 高級(jí)分類(lèi)技術(shù)

經(jīng)典的數(shù)據(jù)分類(lèi)技術(shù)利用數(shù)據(jù)間的距離、相似性等物理特征實(shí)現(xiàn)數(shù)據(jù)分類(lèi)，典型的方法如SVM及其改進(jìn)方法。但是，實(shí)際數(shù)據(jù)集數(shù)據(jù)樣本之間總會(huì)存在關(guān)聯(lián)，當(dāng)將數(shù)據(jù)集映射成復(fù)雜網(wǎng)絡(luò)時(shí)這樣的關(guān)聯(lián)便顯而易見(jiàn)，整體上數(shù)據(jù)樣本具有一定的模式結(jié)構(gòu)關(guān)系，并不是數(shù)據(jù)越靠近哪一類(lèi)，它的標(biāo)簽就與該類(lèi)相同，還應(yīng)考慮數(shù)據(jù)的模式結(jié)構(gòu)信息來(lái)確定數(shù)據(jù)的真實(shí)標(biāo)簽類(lèi)型[8,22]。本文結(jié)合復(fù)雜網(wǎng)絡(luò)在數(shù)據(jù)分類(lèi)方面存在的優(yōu)勢(shì)，充分挖掘并利用蘊(yùn)含在模式結(jié)構(gòu)關(guān)系中的數(shù)據(jù)關(guān)聯(lián)信息實(shí)現(xiàn)高級(jí)分類(lèi)技術(shù)，定義如下：

(11)

其中:εcnl代表子網(wǎng)絡(luò)cnl的效率，dtj為測(cè)試樣本t與節(jié)點(diǎn)j間的歐氏距離，γ為平衡系數(shù)，用于平衡數(shù)據(jù)物理特征和數(shù)據(jù)模式結(jié)構(gòu)關(guān)系之間的作用，γ越大則說(shuō)明數(shù)據(jù)模式結(jié)構(gòu)關(guān)系作用越大，反之則說(shuō)明數(shù)據(jù)物理特征作用越大。

當(dāng)輸入一個(gè)未標(biāo)記測(cè)試樣本時(shí)，高級(jí)分類(lèi)技術(shù)將依據(jù)Λt,j確定未標(biāo)記測(cè)試樣本與每個(gè)子網(wǎng)絡(luò)的連接集，定義如下：

Ωcnl={j|j∈cnl&Λt,j>0}

(12)

兩種情況可將子網(wǎng)絡(luò)cnl中的節(jié)點(diǎn)j加入到連接集Ωcnl中：1)當(dāng)測(cè)試樣本與子網(wǎng)絡(luò)cnl中節(jié)點(diǎn)j的Λt,j大于0時(shí)將節(jié)點(diǎn)j加入連接集Ωcnl中；2)當(dāng)測(cè)試樣本與每個(gè)子網(wǎng)絡(luò)cnl中節(jié)點(diǎn)的Λt,j都小于0時(shí)，則將與最接近于0的Λt,j對(duì)應(yīng)的節(jié)點(diǎn)j加入到連接集Ωcnl中。高級(jí)分類(lèi)模型將依據(jù)測(cè)試樣本與子網(wǎng)絡(luò)連接集影響力之和來(lái)判斷測(cè)試樣本標(biāo)簽類(lèi)別，最大連接集影響力之和定義如下：

(13)

高級(jí)分類(lèi)模型將未標(biāo)記測(cè)試樣本歸為與具有最大影響力之和的連接集所對(duì)應(yīng)的類(lèi)別中。

如圖2所示演示了高級(jí)分類(lèi)方法的詳細(xì)分類(lèi)過(guò)程。針對(duì)第2節(jié)高級(jí)分類(lèi)模型的描述可知，高級(jí)分類(lèi)方法涉及3個(gè)參數(shù)，即k近鄰算法中的參數(shù)k，截?cái)嗑嚯xdc以及平衡系數(shù)γ。圖2中3個(gè)參數(shù)分別設(shè)置為k=2、dc=3及γ=0.3。圖2(a)為利用k近鄰算法建立的復(fù)雜網(wǎng)絡(luò)，包含兩個(gè)獨(dú)立的子網(wǎng)絡(luò)：“■”類(lèi)，標(biāo)簽為0；“·”類(lèi)，標(biāo)簽為1。圖2(b)展示了節(jié)點(diǎn)的屬性?xún)?nèi)容：部分節(jié)點(diǎn)之間的歐氏距離(如d12=0.81)及節(jié)點(diǎn)的度(如deg2=3)，可用于計(jì)算節(jié)點(diǎn)的效率。圖2(c)為利用公式(2) ～ (5)計(jì)算出的節(jié)點(diǎn)效率(如ε1=1.76)及利用公式(6)計(jì)算出的子網(wǎng)絡(luò)效率(如“■”類(lèi)：φ0=1.57)。圖2(d)展示了復(fù)雜網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的影響力(如In1=0.60)；根據(jù)公式(11)可建立測(cè)試樣本(“▲”)與每個(gè)子網(wǎng)絡(luò)的連接集，如圖2(e)所示。最終將測(cè)試樣本歸入到與具有最大連接集節(jié)點(diǎn)影響力之和對(duì)應(yīng)的類(lèi)中，如圖2(f)所示預(yù)測(cè)測(cè)試樣本的標(biāo)簽類(lèi)型為0。

圖2 高級(jí)分類(lèi)方法分類(lèi)示例

2 混合數(shù)據(jù)分類(lèi)方法

本文混合數(shù)據(jù)分類(lèi)方法由普通分類(lèi)方法和高級(jí)分類(lèi)方法混合而成，一方面，普通分類(lèi)方法(如SVM、RF及kNN等)依據(jù)數(shù)據(jù)的物理特征(如距離、相似性等)訓(xùn)練數(shù)據(jù)分類(lèi)模型并預(yù)測(cè)測(cè)試樣本的標(biāo)簽類(lèi)型；另一方面，高級(jí)分類(lèi)方法首先根據(jù)數(shù)據(jù)之間的關(guān)聯(lián)作用將訓(xùn)練樣本映射成復(fù)雜網(wǎng)絡(luò)，在復(fù)雜網(wǎng)絡(luò)中挖掘節(jié)點(diǎn)(每一個(gè)節(jié)點(diǎn)與數(shù)據(jù)樣本相對(duì)應(yīng))的模式結(jié)構(gòu)特征：節(jié)點(diǎn)及子網(wǎng)絡(luò)效率和節(jié)點(diǎn)影響力，當(dāng)輸入一個(gè)測(cè)試樣本時(shí)，根據(jù)高級(jí)分類(lèi)技術(shù)(式(11))建立測(cè)試樣本與每個(gè)子網(wǎng)絡(luò)的連接集，最終將測(cè)試樣本歸為與具有最大影響力之和的連接集相對(duì)應(yīng)的類(lèi)中。所提混合分類(lèi)模型定義如下：

(14)

(15)

(16)

本文混合數(shù)據(jù)分類(lèi)方法一方面能夠在建立的復(fù)雜網(wǎng)絡(luò)中探索并挖掘數(shù)據(jù)模式結(jié)構(gòu)信息用于數(shù)據(jù)訓(xùn)練與分類(lèi)；另一方面由公式(11)可知，從數(shù)據(jù)物理特征的角度，當(dāng)一個(gè)測(cè)試樣本的物理特征(如距離)與訓(xùn)練樣本中的任何一類(lèi)數(shù)據(jù)都不相似時(shí)，高級(jí)分類(lèi)方法將起主要作用，從數(shù)據(jù)模式結(jié)構(gòu)關(guān)系的角度，當(dāng)一個(gè)測(cè)試樣本的結(jié)構(gòu)并不遵從訓(xùn)練樣本中任何一類(lèi)數(shù)據(jù)的結(jié)構(gòu)關(guān)系時(shí)，普通分類(lèi)方法將起主要作用。

3 實(shí)驗(yàn)與結(jié)果

為了驗(yàn)證所提混合數(shù)據(jù)分類(lèi)方法的分類(lèi)性能及其有效性，實(shí)驗(yàn)采用對(duì)比的方式將該方法與模糊SVM[1]、模糊C4.5[6]、加權(quán)的kNN[23]、模糊分類(lèi)方法0-階TSK及1-階TSK[24-25]分別在人造數(shù)據(jù)集以及UCI真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)結(jié)果與分析突出所提混合分類(lèi)方法與傳統(tǒng)分類(lèi)方法的區(qū)別。其中，SVM采用線性及高斯兩種核類(lèi)型的算法，為了公平起見(jiàn)，所有對(duì)比算法涉及的參數(shù)均采用網(wǎng)格搜索結(jié)合交叉驗(yàn)證的方法進(jìn)行確定。所有對(duì)比算法均在Matlab軟件平臺(tái)上實(shí)現(xiàn)程序編寫(xiě)并在配置有處理器為Intel(R) Core(TM) i3-3240、CPU主頻為3.40 GHz、內(nèi)存大小為4.00 G、操作系統(tǒng)為windows 7 ultimate system的臺(tái)式電腦上進(jìn)行仿真。

3.1 高級(jí)分類(lèi)方法

為了詳細(xì)地了解所提高級(jí)分類(lèi)方法的分類(lèi)性能，組織5組高斯數(shù)據(jù)集實(shí)驗(yàn)，如圖3所示，每組高斯數(shù)據(jù)集包含3類(lèi)數(shù)據(jù)，具有各自的數(shù)據(jù)模式結(jié)構(gòu)，3類(lèi)數(shù)據(jù)分別被標(biāo)記為“·”類(lèi)、“■”類(lèi)及“▲”類(lèi)，類(lèi)之間有不同程度的交叉重疊，如圖3(e)所示的高斯數(shù)據(jù)集中3類(lèi)數(shù)據(jù)的交叉程度已達(dá)到80%，根據(jù)我們的知識(shí)和經(jīng)驗(yàn)，這對(duì)于傳統(tǒng)分類(lèi)技術(shù)是一項(xiàng)十分具有挑戰(zhàn)性的分類(lèi)任務(wù)。

圖3 5組高斯數(shù)據(jù)集

圖4分別展示了利用高級(jí)分類(lèi)技術(shù)對(duì)5組高斯數(shù)據(jù)集不同參數(shù)組合下的數(shù)據(jù)分類(lèi)結(jié)果，其中，k的取值范圍為[1,15][11]，截?cái)嗑嚯xdc使得復(fù)雜網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)被周?chē)脊?jié)點(diǎn)總數(shù)3%～5%的其他節(jié)點(diǎn)包圍[21]，取值范圍為[0.01,0.1]，設(shè)定平衡系數(shù)γ的取值范圍為[0.1,1.5]。圖中“Acc”代表分類(lèi)精度，顏色條從下至上代表分類(lèi)精度越來(lái)越高，所有實(shí)驗(yàn)結(jié)果均為運(yùn)行程序10次后取得的平均結(jié)果。由圖4實(shí)驗(yàn)結(jié)果可知，隨著數(shù)據(jù)交叉程度的增加，數(shù)據(jù)分類(lèi)精度逐漸降低，當(dāng)數(shù)據(jù)交叉程度達(dá)到80%，由于能夠挖掘并利用數(shù)據(jù)模式結(jié)構(gòu)信息，所提高級(jí)分類(lèi)方法依然能夠取得較高的分類(lèi)精度(如圖4(e)所示的最高分類(lèi)精度為70%)，充分彰顯了所提高級(jí)分類(lèi)方法魯棒的分類(lèi)性能。

圖4 5組高斯數(shù)據(jù)集不同參數(shù)組合下的分類(lèi)結(jié)果

3.2 人造數(shù)據(jù)集仿真

挖掘并將數(shù)據(jù)模式結(jié)構(gòu)信息用于數(shù)據(jù)分類(lèi)的HDCM通過(guò)混合傳統(tǒng)分類(lèi)方法和高級(jí)分類(lèi)方法兩種類(lèi)型的分類(lèi)技術(shù)來(lái)彌補(bǔ)傳統(tǒng)分類(lèi)方法僅僅采用數(shù)據(jù)物理特征進(jìn)行模型訓(xùn)練及分類(lèi)的缺陷。HDCM包含的兩種不同類(lèi)型分類(lèi)技術(shù)在數(shù)據(jù)分類(lèi)過(guò)程中所起的作用不同，如圖5所示，當(dāng)數(shù)據(jù)之間關(guān)聯(lián)緊密，數(shù)據(jù)具有典型的模式結(jié)構(gòu)時(shí)(藍(lán)色“■”類(lèi))，HDCM在分類(lèi)過(guò)程中將以高級(jí)分類(lèi)方法為主導(dǎo)，即公式(14)中參數(shù)λ的取值偏大。這里將通過(guò)圖5所示的數(shù)據(jù)集具體地演示參數(shù)λ如何平衡HDCM中兩種不同類(lèi)型分類(lèi)器對(duì)數(shù)據(jù)分類(lèi)所起的作用。圖5所示的數(shù)據(jù)集“·”類(lèi)包含500個(gè)樣本，“■”類(lèi)包含的樣本數(shù)為40，實(shí)驗(yàn)中選取廣泛使用的SVM作為比較算法[1]，算法相關(guān)參數(shù)設(shè)置如下：對(duì)于線性SVM，懲罰系數(shù)C=28；高斯型SVM中懲罰系數(shù)C=28，核寬度σ=2-3；混合分類(lèi)方法中截?cái)嗑嚯xdc=1，參數(shù)k=5以及公式(11)中平衡系數(shù)γ=0.1。表1記錄了參數(shù)λ取不同值時(shí)采用不同分類(lèi)方法計(jì)算的測(cè)試樣本(“▲”)對(duì)于數(shù)據(jù)集中不同類(lèi)數(shù)據(jù)的隸屬度，其中，普通分類(lèi)方法對(duì)應(yīng)Blue列，HDCM對(duì)應(yīng)Red列。

圖5 HDCM的解釋性示例

由圖5可知，“·”類(lèi)的樣本數(shù)明顯多于“■”類(lèi)，且測(cè)試樣本距離“·”類(lèi)較近，如果使用傳統(tǒng)分類(lèi)方法，測(cè)試樣本將被錯(cuò)誤地歸入到“·”類(lèi)，即屬于“·”類(lèi)的模糊隸屬度較大，如表1中當(dāng)λ=0。隨著λ值逐漸變大，混合分類(lèi)方法中傳統(tǒng)分類(lèi)方法的作用逐漸減弱，由于“■”類(lèi)數(shù)據(jù)呈現(xiàn)明顯的模式結(jié)構(gòu)，且HDCM能夠有效地挖掘數(shù)據(jù)之間的關(guān)聯(lián)作用信息并用于數(shù)據(jù)分類(lèi)，因此，HDCM能夠精確地預(yù)測(cè)測(cè)試樣本的真實(shí)標(biāo)簽類(lèi)型。結(jié)合圖5和表1可知，當(dāng)使用某種分類(lèi)方法進(jìn)行分類(lèi)時(shí)，測(cè)試樣本并不一定屬于距離它較近的數(shù)據(jù)類(lèi)，還應(yīng)該考慮數(shù)據(jù)之間的關(guān)聯(lián)。

表1 不同λ值對(duì)分類(lèi)的影響

挖掘數(shù)據(jù)模式結(jié)構(gòu)信息的混合數(shù)據(jù)分類(lèi)方法在考慮數(shù)據(jù)物理特征的基礎(chǔ)上，還通過(guò)構(gòu)建復(fù)雜網(wǎng)絡(luò)并探索數(shù)據(jù)的模式結(jié)構(gòu)，并將數(shù)據(jù)模式結(jié)構(gòu)信息用于數(shù)據(jù)分類(lèi)。這里利用三組人造數(shù)據(jù)集來(lái)驗(yàn)證HDCM的數(shù)據(jù)分類(lèi)性能。三組人造數(shù)據(jù)集分別為Circles、Moons以及Rectangle，如圖6所示，Circles中三類(lèi)包含的樣本數(shù)分別為2001、1001及601；Moons中兩類(lèi)包含的樣本數(shù)分別為1001、501；Rectangle中兩類(lèi)包含的樣本數(shù)分別為500、1000。每組數(shù)據(jù)集中的數(shù)據(jù)呈現(xiàn)明顯的模式結(jié)構(gòu)，分別為圓、月牙形以及長(zhǎng)方形，不同數(shù)據(jù)類(lèi)之間有重復(fù)交叉且包含不平衡樣本數(shù)，即一類(lèi)包含的樣本數(shù)明顯多于另一類(lèi)，如Moons中左類(lèi)樣本數(shù)為1001，而右類(lèi)樣本數(shù)只有501，這樣的數(shù)據(jù)集對(duì)于傳統(tǒng)分類(lèi)方法具有一定挑戰(zhàn)性。

圖6 三組人造數(shù)據(jù)集

數(shù)據(jù)集方法SVM(Linear)(C)SVM(Gaussian)(C,σ)Circles單一90.27±0.43(210)89.58±0.11(1,212)混合96.24±3.87(4,0.2,0.9)95.78±0.24(8,0.2,0.9)Moons單一92.33±1.98(211)88.33±0.71(28,210)混合94.34±1.78(5,0.1,0.8)93.82±2.24(6,0.1,0.8)Rectangle單一95.00±1.52(29)96.00±1.52(22,29)混合97.10±3.31(4,0.2,0.9)97.34±2.49(5,0.3,0.8)

實(shí)驗(yàn)中，對(duì)于每一組人造數(shù)據(jù)集，隨機(jī)選取樣本總數(shù)的80%作為訓(xùn)練樣本，其余作為測(cè)試樣本。仍然選取最為經(jīng)典的分類(lèi)方法SVM作為比較方法，這里使用模糊SVM方法[1]。針對(duì)Circles、Moons以及Rectangle，HDCM中截?cái)嗑嚯xdc大小具體設(shè)置為0.7、0.1及0.2，算法涉及最優(yōu)參數(shù)經(jīng)網(wǎng)格搜索結(jié)合5折交叉驗(yàn)證的方法獲得，具體參數(shù)設(shè)置如表2所示。實(shí)驗(yàn)所得數(shù)據(jù)為運(yùn)行程序5次后的平均結(jié)果。

表2列出了所有對(duì)比算法在人造數(shù)據(jù)集上的詳細(xì)數(shù)據(jù)分類(lèi)結(jié)果，其中，“單一”表示只使用某一種傳統(tǒng)方法進(jìn)行數(shù)據(jù)分類(lèi)，“混合”表示使用本文HDCM進(jìn)行數(shù)據(jù)分類(lèi)，分類(lèi)精度及其標(biāo)準(zhǔn)差、算法最優(yōu)參數(shù)分別表示為**±**(**)。

由于圖6三組人造數(shù)據(jù)集中的數(shù)據(jù)之間關(guān)聯(lián)緊密，數(shù)據(jù)整體上呈現(xiàn)典型的模式結(jié)構(gòu)，即使在發(fā)生明顯數(shù)據(jù)重疊的情況下，使用本文所提的混合數(shù)據(jù)分類(lèi)技術(shù)取得的分類(lèi)結(jié)果普遍優(yōu)于傳統(tǒng)分類(lèi)方法。人造數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明HDCM能夠有效地挖掘數(shù)據(jù)之間的關(guān)聯(lián)信息，也正因?yàn)閷?shù)據(jù)模式結(jié)構(gòu)信息用于分類(lèi)模型的訓(xùn)練及數(shù)據(jù)分類(lèi)，使得HDCM具備良好的數(shù)據(jù)分類(lèi)性能。

3.3 真實(shí)數(shù)據(jù)集仿真

除了人造數(shù)據(jù)集仿真實(shí)驗(yàn)，本文還將HDCM在UCI真實(shí)數(shù)據(jù)集[26]上進(jìn)行實(shí)驗(yàn)，觀察所提混合分類(lèi)方法的實(shí)際分類(lèi)性能。UCI真實(shí)數(shù)據(jù)集的詳細(xì)介紹如表3所示，其中，數(shù)據(jù)集中的樣本數(shù)范圍為178 ～ 4174，最大和最小的數(shù)據(jù)特征維數(shù)分別為3、18，數(shù)據(jù)集包含的類(lèi)別數(shù)最小為2，最大為28。綜上所述，所選取的真實(shí)數(shù)據(jù)集配置符合驗(yàn)證HDCM實(shí)際分類(lèi)性能的需求。

表3 UCI真實(shí)數(shù)據(jù)集

實(shí)驗(yàn)中，對(duì)于每一組真實(shí)數(shù)據(jù)集，隨機(jī)選取樣本總數(shù)的80%作為訓(xùn)練樣本，其余當(dāng)作測(cè)試樣本。所有對(duì)比算法參數(shù)設(shè)置作如下介紹：HDCM算法共涉及四個(gè)參數(shù)，即高級(jí)分類(lèi)方法中的k、dc、γ以及混合分類(lèi)技術(shù)中用于平衡數(shù)據(jù)物理特征與模式結(jié)構(gòu)關(guān)系特征作用的系數(shù)λ。由于截?cái)嗑嚯xdc使得復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)被占節(jié)點(diǎn)總數(shù)3%～5%的其他節(jié)點(diǎn)包圍，這里主要設(shè)置參數(shù)k、γ及λ。根據(jù)大量的實(shí)驗(yàn)結(jié)果，k、γ及λ的取值可分別在{1,2,…,14,15}、{0.1,0.2,…,2.9,3}以及{0,0.1,…,0.9,1}范圍內(nèi)進(jìn)行搜索，另外，針對(duì)參數(shù)dc，表1中的真實(shí)數(shù)據(jù)集從上往下分別設(shè)置為3.3、0.08、2.9、4.1、0.6、0.2以及0.8。線性SVM中的懲罰系數(shù)C取值范圍為{2-3,2-2,…,211,212}，高斯型SVM的性能除了與懲罰系數(shù)C相關(guān)外，還與核寬度σ的設(shè)置有關(guān)，其取值范圍為{2-3,2-2,…,211,212}。加權(quán)的k近鄰算法中參數(shù)k的設(shè)置與HDCM相同，其分類(lèi)結(jié)果主要取決于測(cè)試樣本與其所有近鄰的加權(quán)之和，這里的權(quán)值大小為測(cè)試樣本與其近鄰之間歐氏距離的倒數(shù)。經(jīng)典模糊分類(lèi)方法TSK的數(shù)據(jù)分類(lèi)性能主要與模糊規(guī)則數(shù)R及正則化參數(shù)τ相關(guān)，實(shí)驗(yàn)中這兩個(gè)參數(shù)的取值搜索范圍分別設(shè)置為{5,10,…,195,200}及{10-5,10-4,…,104,105}。模糊C4.5[6]及對(duì)比算法的其他參數(shù)均采用默認(rèn)設(shè)置。實(shí)驗(yàn)中的算法最優(yōu)參數(shù)均由網(wǎng)格搜索結(jié)合5折的交叉驗(yàn)證方法確定，實(shí)驗(yàn)數(shù)據(jù)為運(yùn)行程序15次后取得的平均結(jié)果，分類(lèi)精度及其標(biāo)準(zhǔn)差、算法最優(yōu)參數(shù)分別表示為**±**(**)。表4給出的混合分類(lèi)方法最優(yōu)參數(shù)為(k,γ,λ)，“-” 代表參數(shù)的取值為空，表明HDCM中高級(jí)分類(lèi)方法對(duì)分類(lèi)結(jié)果未起作用。另外，為了探討高級(jí)分類(lèi)方法的實(shí)際分類(lèi)性能，表4最后一列給出在UCI真實(shí)數(shù)據(jù)集上單一使用高級(jí)分類(lèi)方法的分類(lèi)效果，“---”表示無(wú)需使用HDCM進(jìn)行分類(lèi)。

如表4所示，通過(guò)對(duì)比算法在UCI真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可得出以下幾點(diǎn)分析：1)當(dāng)傳統(tǒng)分類(lèi)方法與HDCM所取得的數(shù)據(jù)分類(lèi)結(jié)果一致時(shí)，在混合分類(lèi)技術(shù)分類(lèi)過(guò)程中傳統(tǒng)分類(lèi)方法將起主導(dǎo)作用，HDCM可智能地弱化高級(jí)分類(lèi)方法的作用，即公式(14)中的參數(shù)λ=0，如高斯型SVM對(duì)于數(shù)據(jù)集Vehicle、加權(quán)的kNN對(duì)于數(shù)據(jù)集Contraceptive等；2)當(dāng)傳統(tǒng)分類(lèi)方法在真實(shí)數(shù)據(jù)集上所取得的分類(lèi)精度較低時(shí)，公式(14)中參數(shù)λ的值將等于或接近1，HDCM中的高級(jí)分類(lèi)方法將對(duì)預(yù)測(cè)測(cè)試樣本的標(biāo)簽類(lèi)型起決定性作用，如線性SVM對(duì)于數(shù)據(jù)集Abalone、加權(quán)的kNN對(duì)于數(shù)據(jù)集Contraceptive、模糊C4.5對(duì)于數(shù)據(jù)集Abalone等；3)對(duì)于每一組真實(shí)數(shù)據(jù)集，混合分類(lèi)方法都給出了不同的γ值，表明數(shù)據(jù)集中數(shù)據(jù)之間的確存在關(guān)聯(lián)作用信息，且所提方法能夠有效挖掘并利用這些不同于數(shù)據(jù)物理特征的數(shù)據(jù)信息來(lái)提高傳統(tǒng)分類(lèi)方法的分類(lèi)性能；4)當(dāng)單一使用高級(jí)分類(lèi)方法時(shí)，通過(guò)與普通分類(lèi)方法相比較，高級(jí)分類(lèi)方法表現(xiàn)出了具有競(jìng)爭(zhēng)力的分類(lèi)性能，表明挖掘并使用數(shù)據(jù)模式結(jié)構(gòu)信息確實(shí)能夠有助于改善分類(lèi)方法的性能。

表5給出了兩種典型的傳統(tǒng)分類(lèi)器與所提分類(lèi)技術(shù)在數(shù)據(jù)集Wine、Contraceptive以及Haberman上的算法運(yùn)行時(shí)間對(duì)比。由表2結(jié)合表4可知HDCM分類(lèi)精度均高于普

表5 算法運(yùn)行時(shí)間分析

通分類(lèi)方法，但由于所提混合數(shù)據(jù)分類(lèi)方法結(jié)合普通分類(lèi)方法與高級(jí)分類(lèi)方法，因此，從算法復(fù)雜度角度，HDCM并不占明顯優(yōu)勢(shì)。

3.4 工業(yè)應(yīng)用案例

本文還進(jìn)行工業(yè)應(yīng)用案例分析，將HDCM應(yīng)用于人臉識(shí)別。如圖7所示，選取的6組人臉圖像來(lái)自Pointing’04 ICPR Workshop[27]，它所包含的人臉圖像均為基準(zhǔn)的人臉識(shí)別數(shù)據(jù)集。每一組人臉圖像包含15幅序列圖像，圖像中的人臉姿勢(shì)以15°的間隔在[-90° 90°]范圍內(nèi)變化，實(shí)驗(yàn)中選取序列圖像的前7或者后7幅圖像組成人臉圖像數(shù)據(jù)集。每一幅人臉圖像的分辨率定為80(120，且利用主成分分析法(Principle Component Analysis, PCA)對(duì)圖像特征進(jìn)行降維[28]，根據(jù)實(shí)驗(yàn)效果維度大小設(shè)置為30。實(shí)驗(yàn)中選取每一組人臉圖像的前5幅作為訓(xùn)練樣本，其他圖像作為測(cè)試樣本。由圖7可知，由于每個(gè)人臉的特征不同(如發(fā)型、面部表情等)，且每個(gè)人臉姿勢(shì)或朝右或朝左，因此，對(duì)應(yīng)于每個(gè)不同人臉的數(shù)據(jù)整體上會(huì)呈現(xiàn)明顯的模式結(jié)構(gòu)，十分適合驗(yàn)證挖掘并利用數(shù)據(jù)模式結(jié)構(gòu)信息的混合分類(lèi)方法的有效性及其分類(lèi)性能。實(shí)驗(yàn)中，HDCM的參數(shù)dc=6，對(duì)比算法給出的所有最優(yōu)參數(shù)均由網(wǎng)格搜索結(jié)合5折的交叉驗(yàn)證方法獲得，實(shí)驗(yàn)數(shù)據(jù)為運(yùn)行程序15次后所取的平均結(jié)果(表4最后一行數(shù)據(jù))。

圖7 人臉識(shí)別數(shù)據(jù)集

由實(shí)驗(yàn)結(jié)果可知，SVM等傳統(tǒng)分類(lèi)方法因在構(gòu)建分類(lèi)模型以及分類(lèi)的過(guò)程中依賴(lài)單一的數(shù)據(jù)物理特征而忽略了數(shù)據(jù)之間存在關(guān)聯(lián)信息的事實(shí)，在人臉識(shí)別數(shù)據(jù)集上的分類(lèi)精度明顯低于所提的混合分類(lèi)方法，尤其當(dāng)使用0-階TSK及1-階TSK模糊分類(lèi)方法時(shí)實(shí)驗(yàn)對(duì)比效果更加明顯。人臉識(shí)別數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果充分證明了HDCM不僅能夠挖掘數(shù)據(jù)之間的關(guān)聯(lián)信息、識(shí)別數(shù)據(jù)的模式結(jié)構(gòu)關(guān)系，而且可有效地結(jié)合傳統(tǒng)分類(lèi)方法和高級(jí)分類(lèi)方法兩種不同類(lèi)型的分類(lèi)技術(shù)進(jìn)行數(shù)據(jù)分類(lèi)。

4 結(jié)束語(yǔ)

數(shù)據(jù)集中數(shù)據(jù)之間往往存在關(guān)聯(lián)，數(shù)據(jù)并不是孤立的存在，在構(gòu)建數(shù)據(jù)分類(lèi)模型以及分類(lèi)的過(guò)程中應(yīng)考慮這樣一種有別于數(shù)據(jù)物理特征的數(shù)據(jù)關(guān)聯(lián)信息。本文所提的混合數(shù)據(jù)分類(lèi)方法一方面兼顧了數(shù)據(jù)的物理特征，另一方還能夠有效地識(shí)別數(shù)據(jù)的模式結(jié)構(gòu)，并將數(shù)據(jù)之間的關(guān)聯(lián)作用信息用于訓(xùn)練數(shù)據(jù)分類(lèi)模型及數(shù)據(jù)分類(lèi)。人造數(shù)據(jù)集及真實(shí)數(shù)據(jù)集上的仿真實(shí)驗(yàn)結(jié)果證明了HDCM的有效性，HDCM實(shí)際分類(lèi)性能優(yōu)于傳統(tǒng)的分類(lèi)方法。實(shí)驗(yàn)中發(fā)現(xiàn)，HDCM還能夠解決數(shù)樣本比例不平衡情況下的數(shù)據(jù)分類(lèi)[29]，如人造數(shù)據(jù)集Moons及真實(shí)數(shù)據(jù)集Yeast，樣本比例分別為2、2.46，因此，在今后的工作中將對(duì)此作進(jìn)一步研究。另外，根據(jù)圖論知識(shí)，一個(gè)復(fù)雜網(wǎng)絡(luò)除了節(jié)點(diǎn)的度等常見(jiàn)屬性外，還包含有同質(zhì)性、聚類(lèi)系數(shù)等[30]，如何將除了度之外其他屬性結(jié)合進(jìn)來(lái)探索復(fù)雜網(wǎng)絡(luò)局部與全局特征作為數(shù)據(jù)分類(lèi)的輔助信息[31]也將是今后的研究?jī)?nèi)容。