混合屬性數(shù)據(jù)集分布一致性度量的新方法

何玉林，金 一，戴德鑫，黃柏皓，黃家杰

1)深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東深圳 518060；2)深圳大學(xué)大數(shù)據(jù)系統(tǒng)計(jì)算技術(shù)國家工程實(shí)驗(yàn)室，廣東深圳 518060；3)中國刑事警察學(xué)院刑事科學(xué)技術(shù)學(xué)院，遼寧沈陽 110854

分治[1]是對大數(shù)據(jù)進(jìn)行處理和分析的有效途徑之一，當(dāng)前流行的大數(shù)據(jù)計(jì)算框架，如MapReduce[2]和Spark[3]均是基于分治思想開展對大數(shù)據(jù)存儲和計(jì)算的．最近，一種新的以分治策略為基礎(chǔ)的大數(shù)據(jù)管理模型——隨機(jī)樣本劃分(random sample partition, RSP)[4-5]被提出并用于大數(shù)據(jù)的處理和分析中．該模型通過將大數(shù)據(jù)劃分成與大數(shù)據(jù)保持概率分布一致性的RSP數(shù)據(jù)塊實(shí)現(xiàn)對大數(shù)據(jù)的學(xué)習(xí)和挖掘，其中大數(shù)據(jù)RSP數(shù)據(jù)塊的生成和判定是模型的核心．

RSP數(shù)據(jù)塊[6]是指在給定顯著性水平下具有相同概率分布的數(shù)據(jù)塊，包括連續(xù)屬性、離散屬性和混合屬性數(shù)據(jù)塊．用于度量不同樣本之間相似性的指標(biāo)很多，如歐氏距離、馬氏距離、余弦相似度、相關(guān)系數(shù)和Jaccard相似系數(shù)等．然而，用于度量不同數(shù)據(jù)集分布相似性或一致性的指標(biāo)卻很少，最經(jīng)典的就是用于度量連續(xù)屬性數(shù)據(jù)集分布一致性的最大平均差異(maximum mean discrepancy, MMD)方法[7]．MMD在再生核希爾伯特空間(reproducing kernel Hilbert space, RKHS)中構(gòu)建度量標(biāo)準(zhǔn)來檢驗(yàn)不同數(shù)據(jù)集是否來自同一概率分布．李洪奇等[8]給出了一種度量離散屬性數(shù)據(jù)集分布相似性方法，本研究將其記為基于二值化的相似性度量(binarization-based similarity measure, BSM)方法．該方法首先將原始數(shù)據(jù)集轉(zhuǎn)換成二進(jìn)制數(shù)據(jù)集；之后計(jì)算二進(jìn)制數(shù)據(jù)集的單項(xiàng)目集和雙項(xiàng)目集的特征頻率，并將他們組合，得到原數(shù)據(jù)集的特征向量；最后通過計(jì)算不同數(shù)據(jù)集特征向量之間的距離來度量分布相似性．MMD方法適用于判定連續(xù)屬性數(shù)據(jù)集之間的分布一致性，BSM方法適用于判定離散屬性數(shù)據(jù)集之間的分布相似性．經(jīng)檢索，迄今尚未發(fā)現(xiàn)對混合屬性數(shù)據(jù)集進(jìn)行分布一致性判定的相關(guān)研究工作的報(bào)道．

在當(dāng)今大數(shù)據(jù)時(shí)代背景下，數(shù)據(jù)表現(xiàn)形式的多樣性[9-11]是大數(shù)據(jù)的一個(gè)顯著特征．如何將RSP模型應(yīng)用到混合屬性大數(shù)據(jù)的處理與分析中是RSP模型研究的重點(diǎn)．對于混合屬性大數(shù)據(jù)RSP數(shù)據(jù)塊的生成而言，其中最關(guān)鍵的就是數(shù)據(jù)集分布一致性的度量．度量混合屬性數(shù)據(jù)集分布一致性的難點(diǎn)主要體現(xiàn)在兩個(gè)方面：① 通過對連續(xù)屬性進(jìn)行離散化處理，將混合屬性數(shù)據(jù)集轉(zhuǎn)化為離散屬性數(shù)據(jù)集，這會導(dǎo)致原始數(shù)據(jù)集信息量的丟失，最顯著的后果就是伴隨著連續(xù)屬性離散化，數(shù)據(jù)之間的序關(guān)系會丟失；② 通過對離散屬性進(jìn)行獨(dú)熱編碼處理，將混合屬性數(shù)據(jù)集轉(zhuǎn)化為連續(xù)屬性數(shù)據(jù)集，本質(zhì)上并沒有起到離散屬性連續(xù)化的目的，而僅是將原有的離散屬性用更多0和1的二值的離散屬性進(jìn)行了表示．

本研究提出一種基于深度編碼(deep encoding, DE)和MMD的混合屬性數(shù)據(jù)集分布一致性度量方法，簡稱DE-MMD方法，基于該方法實(shí)現(xiàn)了對混合屬性大數(shù)據(jù)RSP數(shù)據(jù)塊的判定．該方法的核心是通過自編碼神經(jīng)網(wǎng)絡(luò)得到混合屬性數(shù)據(jù)集的深度編碼表示形式，再利用混合屬性數(shù)據(jù)集的深度編碼表示進(jìn)行分布一致性的度量．在4個(gè)標(biāo)準(zhǔn)混合屬性數(shù)據(jù)集上對DE-MMD方法進(jìn)行的性能測試結(jié)果表明，與基于離散屬性獨(dú)熱編碼的MMD方法和連續(xù)屬性二進(jìn)制化的BSM方法[8]相比，新方法能夠更加準(zhǔn)確地對混合屬性數(shù)據(jù)集進(jìn)行分布一致性的度量．

1 離散屬性的獨(dú)熱編碼

(1)

其中，n=1,2,…,N;q=1,2,…,Q;m=1,2,…,Mq．

表1 混合屬性數(shù)據(jù)集

表2 獨(dú)熱編碼數(shù)據(jù)集

經(jīng)過對原始數(shù)據(jù)集中離散屬性的獨(dú)熱編碼處理，離散屬性Bq，q=1, 2, …,Q， 被擴(kuò)展成Mq個(gè)二值屬性B(q)1,B(q)2, …,B(q)Mq．其中，B(q)m的取值為0或1;m=1, 2, …,Mq．

2 基于自編碼神經(jīng)網(wǎng)絡(luò)的深度編碼

(2)

(3)

自編碼神經(jīng)網(wǎng)絡(luò)的隱含層使用sigmoid激活函數(shù)，因此可得hnl∈(0, 1)，n=1, 2, …,N;l=1, 2, …,L． 至此，完成了從混合屬性數(shù)據(jù)集D向連續(xù)屬性數(shù)據(jù)集H的轉(zhuǎn)換．

3 基于MMD的分布一致性度量

MMD方法[7]通過在再生核希爾伯特空間(reproducing kernel Hilbert space, RKHS)構(gòu)建統(tǒng)計(jì)量，檢驗(yàn)不同數(shù)據(jù)集是否來自同一概率分布．

設(shè)有一個(gè)D維連續(xù)屬性數(shù)據(jù)集S={si|si=(si1,si2, …,siD)∈RD,i=1, 2, …,M}和T={tj|tj=(tj1,tj2, …,tjD)∈RD,j=1, 2, …,N}， 采用MMD方法構(gòu)建的檢驗(yàn)量為

(4)

當(dāng)

(5)

時(shí)，數(shù)據(jù)集S和T具有一致的概率分布．其中，ε為一致性閾值，ε>0；K為核函數(shù)K(u,v)的上界，

(6)

其中，u=(u1,u2, …,uD)和v=(v1,v2, …,vD)為兩個(gè)D維連續(xù)屬性向量,σ2為核寬度．

利用自編碼神經(jīng)網(wǎng)絡(luò)獲得兩個(gè)混合屬性數(shù)據(jù)集D1和D2對應(yīng)的深度編碼數(shù)據(jù)集H1和H2之后，基于MMD方法的MMD(H1,H2)判斷D1和D2是否具有一致的概率分布．

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

基于表3的Adult、Australian、CRX和German標(biāo)準(zhǔn)KEEL[15]混合屬性數(shù)據(jù)集，對所提的基于深度編碼和最大平均差異的混合屬性數(shù)據(jù)集分布一致性度量方法DE-MMD的可行性和有效性進(jìn)行驗(yàn)證．

表3 四個(gè)標(biāo)準(zhǔn)KEEL數(shù)據(jù)集

4.1 DE-MMD方法的可行性

4.1.1 自編碼神經(jīng)網(wǎng)絡(luò)對混合屬性數(shù)據(jù)集深度編碼穩(wěn)定性的影響

采用代入熵(re-substitution entropy, RE)[16]衡量混合屬性數(shù)據(jù)集所轉(zhuǎn)換的連續(xù)屬性數(shù)據(jù)集所包含的信息量．對于給定的含有N個(gè)樣本和D個(gè)連續(xù)屬性的數(shù)據(jù)集

(7)

代入熵為

(8)

(9)

這里，hd是窗口寬度參數(shù)，且有

(10)

圖1 自編碼神經(jīng)網(wǎng)絡(luò)對混合屬性數(shù)據(jù)集深度編碼穩(wěn)定性的影響Fig.1 The impact of autocoder neural network on transformation of mixed-attribute data set

對每個(gè)數(shù)據(jù)集隨機(jī)抽取200個(gè)樣本，然后利用自編碼神經(jīng)網(wǎng)絡(luò)(權(quán)重最多更新2 000次，終止閾值為1×10-4)進(jìn)行屬性轉(zhuǎn)換，再計(jì)算轉(zhuǎn)換后數(shù)據(jù)集的代入熵，重復(fù)該過程500次，并統(tǒng)計(jì)500個(gè)代入熵的均值m和標(biāo)準(zhǔn)差s． 圖1給出了針對4個(gè)混合屬性數(shù)據(jù)集的代入熵計(jì)算結(jié)果．由圖1可見，自編碼神經(jīng)網(wǎng)絡(luò)能夠穩(wěn)定地對混合屬性數(shù)據(jù)集進(jìn)行深度編碼，因?yàn)閷τ诿恳粋€(gè)數(shù)據(jù)集，500次轉(zhuǎn)換的代入熵RE值基本上位于區(qū)間[m-3s,m+3s]內(nèi)(Adult 數(shù)據(jù)集有498次、Australian數(shù)據(jù)集有500次、CRX數(shù)據(jù)集有499次、German數(shù)據(jù)集有499次)．該實(shí)驗(yàn)證實(shí)了利用自編碼神經(jīng)網(wǎng)絡(luò)對混合屬性數(shù)據(jù)集進(jìn)行深度編碼是可行的，它基本能夠保證轉(zhuǎn)換后所得連續(xù)屬性數(shù)據(jù)集所含信息量的穩(wěn)定．

4.1.2 DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定

當(dāng)利用DE-MMD方法判定不同數(shù)據(jù)集D1和D2的概率分布一致性時(shí)，從式(5)可發(fā)現(xiàn)閾值ε會對判定結(jié)果產(chǎn)生影響．由GRETTON等[7]的推導(dǎo)可知，當(dāng)M=N時(shí)，

(11)

其中，K=1為式(6)所示的核函數(shù)上界；α為顯著性水平．圖2給出了N={100, 200, …, 10 000}和α={0.001, 0.002, …, 0.100}時(shí)，對應(yīng)的ε取值情況．

圖2 閾值ε與樣本個(gè)數(shù)和顯著性水平α之間的關(guān)系Fig.2 The relationship among threshold, size of data set, and significance level

由圖2可見，較小的樣本數(shù)量和顯著性水平對應(yīng)較大的閾值，而較大的樣本數(shù)量和顯著性水平往往對應(yīng)較小的閾值．在MMD方法的分布一致性判別式(式(5))中，發(fā)現(xiàn)閾值實(shí)際上僅與數(shù)據(jù)集的規(guī)模相關(guān)，而與數(shù)據(jù)集的具體性質(zhì)無關(guān)．本研究給出一種基于“數(shù)據(jù)驅(qū)動”的方式來確定閾值．

首先，將式(5)修改為

MMD(S,T)<ε′

(12)

其中，ε′為修正的一致性閾值，且ε′>0． 確定閾值ε′的具體流程為：

1)確定數(shù)據(jù)集S的RSP數(shù)據(jù)塊Si1、Si2和數(shù)據(jù)集T的RSP數(shù)據(jù)塊Ti1、Ti2．其中，

(13)

(14)

RSP數(shù)據(jù)塊的生成方法見文獻(xiàn)[6，17]，在此不再贅述．

2)分別計(jì)算MMD(Si1,Si2)和MMD(Ti1,Ti2)的值．

3)重復(fù)步驟1)和步驟2)I次，并令

(15)

針對表3中的每一個(gè)數(shù)據(jù)集分別抽取2個(gè)非RSP數(shù)據(jù)塊和2個(gè)RSP數(shù)據(jù)塊，使用DE-MMD方法分別度量非RSP數(shù)據(jù)塊和RSP數(shù)據(jù)塊之間的分布一致性．其中，兩個(gè)數(shù)據(jù)塊的規(guī)模均為200，自編碼神經(jīng)網(wǎng)絡(luò)的權(quán)重最大更新次數(shù)為5×104，權(quán)重更新終止閾值為1×10-6， 一致性閾值計(jì)算公式執(zhí)行I=10次， 核寬度σ2=9．

圖3至圖6分別顯示了在4個(gè)混合屬性數(shù)據(jù)集上DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定情況．

圖3 在Adult數(shù)據(jù)集上DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定(ε′=0.013 1)Fig.3 The distribution consistency determined by DE-MMD method on non-RSP and RSP data blocks of Adult data set (ε′=0.013 1)

圖4 在Australian數(shù)據(jù)集上DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定(ε′=0.109 8)Fig.4 The distribution consistency with determined by DE-MMD method on non-RSP and RSP data blocks of Australian data set (ε′=0.109 8)

圖5 在CRX數(shù)據(jù)集上DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定(ε′=0.039 7)Fig.5 The distribution consistency with determined by DE-MMD method on non-RSP and RSP data blocks of CRX data set (ε′=0.039 7)

圖6 在German數(shù)據(jù)集上DE-MMD方法對非RSP和RSP數(shù)據(jù)塊分布一致性的判定(ε′=0.038 1)Fig.6 The distribution consistency with determined by DE-MMD method on non-RSP and RSP data blocks of German data set (ε′=0.038 1)

由圖3至圖6可見，對于非RSP數(shù)據(jù)塊，其選定的離散屬性和連續(xù)屬性在分布上差異非常明顯；而對于RSP數(shù)據(jù)塊，其選定的離散屬性和連續(xù)屬性在分布上基本保持了一致．對于非RSP數(shù)據(jù)塊，MMD值不滿足式(12)，即不同數(shù)據(jù)塊的MMD值大于閾值；而對于RSP數(shù)據(jù)塊，MMD值滿足了式(12)，即不同數(shù)據(jù)塊的MMD值小于閾值．實(shí)驗(yàn)結(jié)果表明，DE-MMD方法能夠量化不同混合屬性數(shù)據(jù)集的概率分布一致情況并做出判定．

4.2 DE-MMD方法的有效性

4.2.1 基于離散屬性獨(dú)熱編碼的OE-MMD方法和離散屬性二進(jìn)制化的BSM方法

OE-MMD方法是基于表2的獨(dú)熱編碼數(shù)據(jù)集，使用MMD方法對不同混合屬性數(shù)據(jù)集的分布一致性進(jìn)行檢驗(yàn)．對于OE-MMD方法，同樣使用式(12)判定數(shù)據(jù)塊的分布一致性，閾值按照4.1.2節(jié)設(shè)計(jì)方法確定．

基于連續(xù)屬性二進(jìn)制化的BSM方法[8]首先對連續(xù)屬性進(jìn)行離散化處理，將混合屬性數(shù)據(jù)集轉(zhuǎn)換成離散屬性數(shù)據(jù)集，為簡便起見，在本實(shí)驗(yàn)對連續(xù)值屬性采用二值離散化；之后對離散屬性數(shù)據(jù)集進(jìn)行獨(dú)熱編碼，得到獨(dú)熱編碼數(shù)據(jù)集；然后計(jì)算獨(dú)熱編碼數(shù)據(jù)集對應(yīng)的單項(xiàng)目集和雙項(xiàng)目集的特征頻率向量；最后對單項(xiàng)目集和雙項(xiàng)目集的特征頻率向量進(jìn)行歸一化處理，得到混合屬性數(shù)據(jù)集對應(yīng)的特征向量．

BSM方法通過計(jì)算特征向量之間的距離判斷混合屬性數(shù)據(jù)集之間的相似性：距離越小，數(shù)據(jù)集相似性越高；距離越大，數(shù)據(jù)集相似性越低．假設(shè)現(xiàn)有兩個(gè)混合屬性數(shù)據(jù)集對應(yīng)的特征向量w1=(w1,1,w1,2, …,w1,18)和w2=(w2,1,w2,2, …,w2,18)， 當(dāng)時(shí)，表明兩個(gè)混合屬性數(shù)據(jù)集具有相似的概率分布．其中，δ為相似性閾值，且δ>0．

(16)

4.2.2 DE-MMD方法與OE-MMD方法和BSM方法的比較

針對表3的每一個(gè)標(biāo)準(zhǔn)混合屬性數(shù)據(jù)集，對其RSP數(shù)據(jù)塊分別使用OE-MMD、BSM和DE-MMD方法進(jìn)行概率分布一致性判定．其中，自編碼神經(jīng)網(wǎng)絡(luò)的權(quán)重最大更新次數(shù)為5×104，權(quán)重更新終止閾值為1×10-6，I=10， 核寬度σ2=9． 針對每個(gè)數(shù)據(jù)集，選取3種不同規(guī)模(200、 300和400 個(gè))的RSP數(shù)據(jù)塊．對每種規(guī)模的數(shù)據(jù)塊分別進(jìn)行100次的分布一致性判定，并統(tǒng)計(jì)判定的準(zhǔn)確率、閾值參數(shù)的選取，對比結(jié)果如表4—表7和圖7所示．

RSP數(shù)據(jù)塊具有一致的概率分布[5-6]，從對比結(jié)果可以發(fā)現(xiàn)，DE-MMD方法在4個(gè)混合分布數(shù)據(jù)集上均獲得了優(yōu)于OE-MMD和BSM方法的一致性判別準(zhǔn)確率，證明本研究提出的DE-MMD方法是有效的．在此，本研究嘗試對DE-MMD方法取得優(yōu)勢的原因進(jìn)行討論：① 與基于離散屬性獨(dú)熱編碼的OE-MMD方法相比，DE-MMD方法并沒有直接使用0和1二值化的離散屬性進(jìn)行分布一致性度量，因?yàn)橹苯邮褂?和1的二值化離散屬性在計(jì)算不同數(shù)據(jù)集的MMD值時(shí)容易增加式(4)失效的概率．舉一個(gè)最極端情況的例子：假設(shè)有兩組數(shù)據(jù)(1, 0)和(0, 1)以及(2, 2)和(1, 1)， 經(jīng)計(jì)算可發(fā)現(xiàn)這兩組數(shù)據(jù)對應(yīng)的MMD值相同，但是相比數(shù)據(jù)(1, 0)和(0, 1)之間的分布一致性，(2, 2)和(1, 1)應(yīng)該具有更大的分布一致性．② 與基于連續(xù)屬性二進(jìn)制化的BSM方法相比，DE-MMD 方法是通過確定原始數(shù)據(jù)集的一種深度編碼形式來計(jì)算數(shù)據(jù)集之間的分布一致性，這種深度編碼通過輸入和輸出完全相同的神經(jīng)網(wǎng)絡(luò)將數(shù)據(jù)轉(zhuǎn)化過程中的信息丟失率達(dá)到最小化，從而保證了基于深度編碼的分布一致性能夠反映原始數(shù)據(jù)的分布一致性．

表4 OE-MMD、BSM和DE-MMD在Australian數(shù)據(jù)集對應(yīng)的RSP數(shù)據(jù)塊上的對比

表5 OE-MMD、BSM和DE-MMD在Adult數(shù)據(jù)集對應(yīng)的RSP數(shù)據(jù)塊上的對比

表6 OE-MMD、BSM和DE-MMD在CRX數(shù)據(jù)集對應(yīng)的RSP數(shù)據(jù)塊上的對比

表7 OE-MMD、BSM和DE-MMD方法在German數(shù)據(jù)集對應(yīng)的RSP數(shù)據(jù)塊上的對比

圖7 OE-MMD、BSM和DE-MMD在4個(gè)KEEL數(shù)據(jù)集上的對比結(jié)果Fig.7 The comparison of results of OE-MMD, BSM, and DE-MMD on 4 KEEL data sets

結(jié) 語

提出一種新的基于深度編碼和最大平均差異的混合屬性數(shù)據(jù)集分布一致性度量方法DE-MMD，它能夠?qū)旌蠈傩詳?shù)據(jù)集的分布一致性進(jìn)行有效度量，其表現(xiàn)優(yōu)于基于離散屬性獨(dú)熱編碼的OE-MMD方法和基于連續(xù)屬性二進(jìn)制化的BSM方法．不同于OE-MMD方法和現(xiàn)有的BSM方法，DE-MMD方法并未直接使用0和1的二值離散屬性表示連續(xù)屬性也沒有對連續(xù)屬性進(jìn)行離散化處理，因此不僅沒有增加分布一致性判定過程中的不確定性，且最大限度地保留了原始數(shù)據(jù)集屬性轉(zhuǎn)化中的信息量．通過對自編碼神經(jīng)網(wǎng)絡(luò)的使用，DE-MMD將原始數(shù)據(jù)集轉(zhuǎn)換成可靠的深度編碼表示形式，這對增強(qiáng)數(shù)據(jù)集分布一致性判定方法的穩(wěn)定性起著至關(guān)重要的作用．

下一步研究計(jì)劃結(jié)合不確定性理論深入分析DE-MMD方法的優(yōu)勢，嘗試采用JS散度替換MMD進(jìn)行分布一致性的度量，并考慮將DE-MMD方法應(yīng)用到混合屬性大數(shù)據(jù)的隨機(jī)樣本劃分生成方法中，同時(shí)考慮使用極限學(xué)習(xí)機(jī)(extreme learning machine, ELM)[18-19]替換本研究的自編碼神經(jīng)網(wǎng)絡(luò)以提升DE-MMD方法的判別速率．

致謝:衷心感謝張曉亮博士對本文數(shù)學(xué)公式的推導(dǎo)及檢查．