不完全數(shù)據(jù)集上的半?yún)⒔M群差異檢測

張師超

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

0 引 言

在智能數(shù)據(jù)分析領(lǐng)域，兩數(shù)據(jù)集間的差異檢測是一個應用非常廣泛的研究課題.例如，在醫(yī)學中，要檢測一種新藥甲能否大批量生產(chǎn)，通常要把其與已有的一些效果很好的舊藥(假如藥品乙)進行一些差別比較，從而得到新藥甲的一些特性，為新藥甲的大批量投產(chǎn)或繼續(xù)改進提供科學依據(jù).檢測差別的方法有均值差異檢測法和分布函數(shù)差異檢測法(或分位數(shù)差異檢測法).在檢測過程中，藥物甲和乙通常稱為對比群(也可以稱為對比集或?qū)Ρ瓤傮w等)[1].在統(tǒng)計和數(shù)據(jù)挖掘領(lǐng)域中，均值差異檢測、分布函數(shù)差異檢測或分位數(shù)差異檢測一般統(tǒng)稱為結(jié)構(gòu)差異檢測.結(jié)構(gòu)差異檢測在統(tǒng)計和數(shù)據(jù)挖掘方面取得了很大的發(fā)展，例如實驗數(shù)據(jù)分析[2]、變化挖掘[3-4]等.

結(jié)構(gòu)差異檢測能得到廣泛的應用是由于它在數(shù)據(jù)挖掘領(lǐng)域得到了較大的發(fā)展.例如在信息安全方面，檢測出垃圾郵件和非垃圾郵件的差異對有效阻止垃圾郵件起著關(guān)鍵的作用[5].組群差異檢測已被廣泛應用于數(shù)據(jù)挖掘的各種領(lǐng)域，如多元數(shù)據(jù)分析[3,5-6]、基于決策樹上的變化挖掘[7-9]等.然而，當前組群差異檢測面臨著以下幾個問題：1)數(shù)據(jù)集經(jīng)常出現(xiàn)缺失現(xiàn)象.很多工業(yè)數(shù)據(jù)集缺失率高達85%，一些基因數(shù)據(jù)集的缺失率甚至高達90%以上[10].常見的組群差異檢測方法都是假設(shè)需處理的數(shù)據(jù)集是完全數(shù)據(jù)集(即沒有缺失)[11].如果把數(shù)據(jù)集中缺失的事例去掉，只使用沒有缺失的數(shù)據(jù)集進行差異分析，顯然會浪費很多信息，而且使用那些少量沒有缺失的事例進行差異檢測，肯定不能代表整個數(shù)據(jù)集的真實情況.2)常見的統(tǒng)計模型經(jīng)常會對所處理的數(shù)據(jù)集有無先驗知識作出假設(shè).如果對所處理的數(shù)據(jù)有先驗知識，則一般可采用參數(shù)方法對數(shù)據(jù)進行差異檢測[12]；如果對所處理的數(shù)據(jù)沒有任何先驗知識，則通常采用非參差異檢測方法[13].事實上，這2種情形都是極端的，面對2個數(shù)據(jù)集，用戶通常會有些先驗知識，此時采用非參差異檢測方法是非常合適的[1].3)常見的差異檢測方法都是面向2個數(shù)據(jù)集[14-16].但是，在實際應用中有時需要在一個數(shù)據(jù)集上進行差異檢測，如在一個文本數(shù)據(jù)集上檢測垃圾郵件和非垃圾郵件的差異，或者在一個數(shù)據(jù)集上檢測良性病癥和惡性病癥的差異，等等.此外，常見的差異檢測集中在一個問題的2個對立面，但在實際應用中通常有多類問題，即類標簽類別個數(shù)多于2類.多類問題中的組群差異問題也能在實際應用中發(fā)現(xiàn)，例如如何檢測一個氣象數(shù)據(jù)集中類別“晴”與其他類別(如“風”、“多云”、“雨”)的差異.然而，一個數(shù)據(jù)集上的差異檢測，或者多類問題中的差異檢測，都還未引起研究者的注意.

本文提出的不完全數(shù)據(jù)集的差異檢測方法為解決以上3個方面的問題提供了理論和技術(shù)支撐.首先，采用一種新穎的填充方法對數(shù)據(jù)集進行填充；其次，在填充得到的數(shù)據(jù)集上使用經(jīng)驗似然方法，在某個置信水平下推斷出2個組群之間的置信區(qū)間，對得到的置信區(qū)間進行差異檢測；再次，討論和提出了缺失數(shù)據(jù)填充問題及置信區(qū)間的構(gòu)造；最后，通過實驗檢測，驗證了本算法的優(yōu)越性.

1 殼填充缺失數(shù)據(jù)算法

1.1 缺失數(shù)據(jù)介紹

由于在實際應用中數(shù)據(jù)缺失的現(xiàn)象非常普遍，因此缺失填充一直是數(shù)據(jù)挖掘、統(tǒng)計等領(lǐng)域中的一個研究熱點.研究者發(fā)現(xiàn)，這些數(shù)據(jù)的缺失會影響從數(shù)據(jù)集中抽取模式(或規(guī)則)的正確性和準確性，從而導致建立錯誤的數(shù)據(jù)挖掘模型.

通常，對缺失數(shù)據(jù)的處理方法有刪除、不處理、填充和部分填充四大類.1)刪除方法就是將缺失數(shù)據(jù)所在的事例整個刪除，差異分析就在剩下的所有無缺失的事例上進行.這種方法簡單但會丟掉很多有用信息.2)不處理方法就是在有缺失數(shù)據(jù)的數(shù)據(jù)集中直接學習.這類方法包括貝葉斯網(wǎng)絡(luò)(Bayesian Network)和人工神經(jīng)網(wǎng)絡(luò)(Artificial Neural Networks)等.但此類方法還不十分成熟，算法的復雜度也很高.3)缺失數(shù)據(jù)填充方法是根據(jù)完全數(shù)據(jù)構(gòu)造一個模型，然后給缺失數(shù)據(jù)一個估計值.然而，經(jīng)常會由于不正確的估計而引入噪音.4)部分填充方法是在最近的文獻[17-18]中被提出的，認為沒有必要對全部缺失數(shù)據(jù)進行填充，只需選擇其中一部分進行填充，效果會更好.

在研究缺失數(shù)據(jù)處理問題上，決策方法通常會與數(shù)據(jù)缺失的機制有關(guān).因此，在對缺失數(shù)據(jù)進行處理前了解數(shù)據(jù)缺失的機制和形式十分重要.因此，把數(shù)據(jù)缺失機制分成以下3類[18]：

1)完全隨機缺失(Missing Completely at Random，MCAR).假如條件屬性表示為X(X為n維向量)，決策屬性為Y.MCAR只說明Y中有缺失值，且與X和Y都無關(guān).這種現(xiàn)象在現(xiàn)實生活中很少見到，一般只會在統(tǒng)計理論中論及.

2)隨機缺失(Missing at Random，MAR).缺失數(shù)據(jù)的可能值僅僅依賴于數(shù)據(jù)集中不含缺失值的其他變量，也就是說，Y的缺失是與X密切相關(guān)的.這種缺失機制簡單易行，在機器學習和數(shù)據(jù)挖掘領(lǐng)域中研究得比較多，通常為默認的缺失機制.本文算法的缺失機制就是這種在機器學習和數(shù)據(jù)挖掘中經(jīng)常涉及的MAR缺失機制.

3)非隨機缺失(Not Missing at Random，NMAR).缺失數(shù)據(jù)的可能值不僅依賴于其他變量，還依賴于不完全數(shù)據(jù)本身.也就是說，對于Y的缺失，除了與X相關(guān)外，還與Y本身相關(guān).這種情況在現(xiàn)實生活中很常見，但由于限制條件比較復雜，研究起來比較麻煩，研究成果也不多.

本文提出的填充算法是基于第2種缺失類型(即MAR)和第4種缺失數(shù)據(jù)處理方法.

1.2 殼近鄰填充(SNI)算法

1)首先對數(shù)據(jù)集進行規(guī)范化；

2)for 每個缺失數(shù)據(jù)z=(X′,Y′){//其中X′為數(shù)據(jù)的屬性，Y′為類標號}；

3)計算和每個完全數(shù)據(jù)(X,Y)∈D之間的距離dist(X′,X)；

4)選擇離z最近的k個完全數(shù)據(jù)的集合Dz?D；

算法1第6步中缺失數(shù)據(jù)z決策屬性的預測值由DS中的完全數(shù)據(jù)確定.

2 經(jīng)驗似然法構(gòu)造半?yún)⒔M群差異模型

用F(x)和Gθ0(y)表示2個組群(或稱為隨機變量)X和Y的分布函數(shù).其中：G已知；F和θ0未知.假設(shè)在2個數(shù)據(jù)集中，其中一個數(shù)據(jù)集的信息(如G)已知，另外一個數(shù)據(jù)集的信息未知(如F)，則這種模型被稱為半?yún)⒛Ｐ?本文的重點在于使用經(jīng)驗似然方法構(gòu)造半?yún)⒛Ｐ偷木挡町惡头植己瘮?shù)差異置信區(qū)間.在這種前提條件下，參數(shù)和半?yún)⒛Ｐ投疾贿m用.有關(guān)經(jīng)驗似然的理論及應用見文獻[19-20].

記任意2個組群差異為Δ,則

Eω(x,θ0,Δ)=0.

(1)

式(1)中的ω是一個已知函數(shù)形式.根據(jù)式(1)，2個組群X和Y的均值差異和分布函數(shù)差異可分別定義為：

1)均值差異：μ1=E(x),μ2=E(y)=μ(θ0),Δ=μ2-μ1，其中ω(x,θ0,Δ)=x-μ(θ0)+Δ;

2)分布函數(shù)差異：對任意固定的值x0,取p1=F(x0),p2=Gθ0(x0)=p(θ0),Δ=p2-p1，且ω(x,θ0,Δ)=I(x≤x0)-p(θ0)+Δ,其中I(5)是示性函數(shù).

接著，記(x,δx)和y分別為(xi,δxi)和yj，i=1,2,…,m;,j=1,2,…,n.其中

(2)

本文假設(shè)隨機變量X和Y的缺失機制為MAR，(x,δx)和y是獨立的.

表1給出了一個例子，顯示本節(jié)主要解決的問題.表1中的數(shù)據(jù)集來自于UCI乳腺癌(Breast Cancer)數(shù)據(jù)集[21].

表1 UCI乳腺癌數(shù)據(jù)集

根據(jù)表1可以提出2個問題：1)什么是良性和惡性乳腺癌患者之間的差異；2)已知兩者之間的差異，如何衡量什么樣的差異值是可信的？

顯然，可以通過考察這2個隨機變量的一些特性，根據(jù)一些簡單的統(tǒng)計方法或者數(shù)據(jù)挖掘方法解決以上2個問題.例如，采用文獻[21-23]的方法可以解決第1個問題.對含有缺失數(shù)據(jù)的隨機變量的差異(即第2個問題)，本文采用經(jīng)驗似然的方法構(gòu)建2個隨機變量的置信區(qū)間(在某顯著性水平α下).

(3)

2.1 對差異Δ構(gòu)造置信區(qū)間

本節(jié)構(gòu)造的組群差異Δ置信區(qū)間的經(jīng)驗似然統(tǒng)計的漸進分布可以被證明是一個加權(quán)的卡方分布 (詳見定理 1 ).首先，半?yún)⑺迫缓瘮?shù)定義為

(4)

(5)

式(5)中:

R(Δ,θ)=

應用拉格朗日乘子法得到

(6)

λ(θ)由下式?jīng)Q定：

(7)

1)θ0∈Ω及Ω均為開區(qū)間;

2)A={y|gθ(y)>0}完全獨立于θ;

3)?y∈A,gθ(y)關(guān)于θ的三次微分均存在；

定理1假設(shè)條件1)～8)都滿足，則式(6)中的θ存在一個解，此解使R(Δ,θ)局部最小,且

(8)

式(8)中：

i=1,2,…,n;

β0=E[α(x,θ0,Δ)];

2.2 基于經(jīng)驗似然的Δ置信區(qū)間

假設(shè)tα滿足P(χ2≤tα)=1-α，根據(jù)定理1, 關(guān)于Δ的基于經(jīng)驗似然的置信區(qū)間漸進收斂于1-α為

(9)

式(9)可以直接對Δ進行假設(shè)檢驗.例如，如果H0:Δ=Δ0,H1:Δ≠Δ0,那么,首先根據(jù)式(9)為Δ構(gòu)建置信區(qū)間，然后檢測初始值Δ0是否在得到的區(qū)間內(nèi).如果Δ0在區(qū)間內(nèi)，則接受假設(shè);否則，拒絕假設(shè).

使用經(jīng)驗似然方法構(gòu)建置信區(qū)間的算法(算法2)如下：

Input:數(shù)據(jù)集x,y

Output:均值和分布函數(shù)的置信區(qū)間

1)Begin

2)Δ=(E(y)-E(x))-a

3)MeanLeft=FindEndPoint(left,Δ)

4)Δ=(E(y)-E(x))+a

5)MeanRight=FindEndPoint(right,Δ)

6)Δ=(DFG(X0)-DFF(X0))-b

7)DFLeft=FindEndPoint(left,Δ)

8)Δ=(DFG(X0)-DFF(X0))+b

9)DFRight=FindEndPoint(right,Δ)

10)Output CIs:(MeanLeft,MeanRight),(DFLeft,DFRight)

Sub procedure FindEndPoint(direction,Δ)

11)If (directin=left) step=1e-2 else step=-1e-2

12)While (1)

13)(λ,θ)←the roots of eq. (6) and (7)

14)compute (8) based on (λ,θ) and datasetx,y

15)if ((9) is satisfied) returnΔelseΔ=Δ+step

End sub

(note thata,bare random selected constants with respect toΔ)

3 實驗分析

為了檢測算法的優(yōu)越性，把本文算法(記為SNIEL)同常見的構(gòu)造置信區(qū)間算法——解鞋帶重抽樣算法[24](Bootstrap re-sampling算法，本文記為BOOT)及使用最近鄰填充缺失數(shù)據(jù)算法2構(gòu)建置信區(qū)間方法(記為NNEL)在UCI真實數(shù)據(jù)集上進行比較，評價指標為構(gòu)造出的置信區(qū)間的長度和真實值在置信區(qū)間中的覆蓋率.置信區(qū)間的長度越短且覆蓋率越大，說明構(gòu)造出的置信區(qū)間效果越好.首先，對有缺失的數(shù)據(jù)集(2個組群均含有相同比例的缺失數(shù)據(jù))，算法SNIEL和算法BOOT均使用算法1填充缺失數(shù)據(jù)，NNEL算法使用k-近鄰算法填充缺失數(shù)據(jù)，2種填充算法都需要設(shè)置參數(shù)k, 在實驗中統(tǒng)一取k=5.在完全的數(shù)據(jù)集中，SNIEL和NNEL使用算法2構(gòu)建均值和分布函數(shù)的置信區(qū)間，BOOT使用解鞋帶重抽樣算法[14]構(gòu)建置信區(qū)間.對比實驗有3組，分別為單一組群并且無類標簽的對比實驗；2個組群類標簽為兩類的對比實驗；2個組群類標簽為多類的對比實驗.要注意的是：1)實驗過程中的置信水平統(tǒng)一設(shè)為1-α，其中α=0.05；2)本文實驗數(shù)據(jù)集均為無缺失數(shù)據(jù)集(為了跟原始數(shù)據(jù)進行比較)，實驗過程中統(tǒng)一使用MAR方法,隨機使20%的事例含有缺失數(shù)據(jù)，稱其缺失率為20%.

3.1 單一組群對比實驗

單一組群實驗是為了檢測2種方法(經(jīng)驗似然法和解鞋帶重抽樣法)構(gòu)建的置信區(qū)間是否為緊(即置信區(qū)間長度較短).若置信區(qū)間的長度趨于0，則說明在這個組群里抽樣出來的2個樣本服從同一分布.在實際應用或者理論研究中，都可以利用這個方法檢測設(shè)計的抽樣算法是否有效.

實驗數(shù)據(jù)集為abalone 數(shù)據(jù)集，共有4 177 事例，每個事例有9個屬性.實驗設(shè)計中，首先隨機把abalone 數(shù)據(jù)集分成2個部分:一個部分含有2 581個事例,記為D1;另一部分為 1 596 事例,記為D2.這里只對第3，5和6個屬性建立置信區(qū)間.實驗樣本為200，實驗次數(shù)1 000次，記錄每次實驗的原始均值和分布函數(shù)，最終結(jié)果為1 000次的平均值.由于實驗在一個數(shù)據(jù)集中進行，因此2個組群的差異Δ理論上應為0.

表2 均值置信區(qū)間平均長度及覆蓋率比較

表3 分布函數(shù)置信區(qū)間平均長度及覆蓋率比較

由表2及表3說明：3種算法構(gòu)造的均值區(qū)間的長度都接近于0，且覆蓋率均超過了95%，說明3種方法都是有效的.但對比兩種使用算法2構(gòu)造置信區(qū)間的方法，算法BOOT無論在分布函數(shù)還是均值置信區(qū)間上都處于劣勢，說明構(gòu)造置信區(qū)間算法優(yōu)于解鞋帶重抽樣法.對比2種使用經(jīng)驗似然構(gòu)造置信區(qū)間的算法發(fā)現(xiàn),算法SNIEL的各評價指標均優(yōu)于算法NNEL，這是因為SNIEL算法使用了殼近鄰填充算法，而NNEL使用的是近鄰填充算法.因此，殼近鄰填充算法在構(gòu)造不完全組群置信區(qū)間方面要優(yōu)于最近鄰算法.

3.2 兩類實驗

單個組群差異檢測可顯示一個組群中的2個樣本是否來自同一個分布，2類組群差異檢測則可以顯示2個組群(即使是具有不同分布，甚至只知道其中1個組群分布情況)的差異情況.

實驗選取數(shù)據(jù)集Wisconsin breast cancer dataset，共有569個事例和32個屬性.類屬性有2個類，其中良性患者類有357個事例，惡性患者有212個.只對第4，15和27個屬性進行實驗.結(jié)果如表4和表5所示.在2個組群的比較實驗中，用經(jīng)驗似然方法估計置信區(qū)間的算法無論是置信區(qū)間的平均長度或真實值在置信區(qū)間的覆蓋率都要比用解鞋帶重抽樣構(gòu)造置信區(qū)間的算法好.

表4 均值置信區(qū)間平均長度及覆蓋率比較

表5 分布函數(shù)置信區(qū)間平均長度及覆蓋率比較

3.3 多類實驗

現(xiàn)實數(shù)據(jù)集的類標簽經(jīng)常含有多類情況.例如，一個有關(guān)氣象數(shù)據(jù)集的類標簽有“晴”、“多云”、“風”和“下雨”.若需估計一個數(shù)據(jù)集中含有多類標簽間的差異，則可以先對這些類標簽做組合(如“晴”跟“多云”、“晴”跟“風”、“晴”跟“下雨”等各做一個組合)，然后再檢測這些組合的差異性.但是，此方法至少含有2個問題：1)這樣的組合勢必加大計算量；2)如果只分析2個類別之間的差異，而不考慮其他類標簽的組合(如只分析“晴”跟“風”的差異，不考慮“晴”跟“多云”及“晴”跟“下雨”等的組合)，顯然是不合理的.本文把“晴”作為一類，其他作為一類，就可以解決以上2個問題.實驗數(shù)據(jù)集為Wine數(shù)據(jù)集(有3個類)、Iris數(shù)據(jù)集(3個類)和Yeast數(shù)據(jù)集(10個類).結(jié)果如表6和表7所示.實驗結(jié)果與表2～表5的一樣，唯一不同的是，算法BOOT在多類問題中不太穩(wěn)定，這可能是由于解鞋帶重抽樣方法的不穩(wěn)定性造成的.

表6 均值置信區(qū)間平均長度及覆蓋率比較

表7 分布函數(shù)置信區(qū)間平均長度及覆蓋率比較

4 結(jié) 論

由于理論保證，經(jīng)驗似然方法在3種實驗比較中都優(yōu)于解鞋帶重抽樣方法.這是因為,雖然經(jīng)驗似然方法的實驗結(jié)果顯示了較短的置信區(qū)間,但卻具有更高的覆蓋率.

參考文獻：

[1]Huang Huijing,Qin Yongsong,Zhu Xiaofeng,et al.Difference Detection between Two Contrast Sets[M].Berlin:Springer,2006:481-490.

[2]Bay S D,Pazzani M J.Characterizing Model Errors and Differences[C]// Proceedings of the Seventeenth International Conference on Machine Learning.New York:ACM,2000:49-56.

[3]Bay S D,Pazzani M J.Detecting Change in Categorical Data:Mining Contrast Sets[C]// Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,1999:302-306.

[4]Au W H,Chan K C C.Mining changes in association rules:a fuzzy approach[J].Fuzzy Sets and Systems,2005,149(1):87-104.

[5]Bay S D,Pazzani M J.Detecting Group Differences:Mining Contrast Sets[J].Data Mining and Knowledge Discovery,2001,5(3):213-246.

[6]Webb G I,Butler S M,Newlands D A.On detecting differences between groups[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2003:256-265.

[7]Cong Gao,Liu Bing.Speed-up Iterative Frequent Itemset Mining with Constraint Changes[C]//Proceedings of the International Conference on Data Mining.New York:IEEE,2002:107-114.

[8]Liu Bing,Hsu W,Han H S,et al.Mining Changes for Real-Life Applications[M].Berlin:Springer,2000:337-346.

[9]Wang Ke,Zhou Senqiang,Fu C A,et al.Mining Changes of Classification by Correspondence Tracing[C]//SIAMDM ’03,SIAM International Conference on Data Mining.San Francisco:SIAM,2003.

[10]Lakshminarayan K,Harp S A,Samad T.Imputation of missing data in industrial databases[J].Applied Intelligence,1999,11(3):259-275.

[11]Zhang Shichao.Detecting Differences between Contrast Groups[J].IEEE Transactions on Information Technology in Biomedicine,2008,12(6):739-745.

[12]Jing Bingyi.Two-sample empirical likelihood method[J].Statistics and Probability Letters,1995,24(4):315-319.

[13]Qin Yongsong,Zhang Shichao.Empirical Likelihood Confidence Intervals for Differences between Two Datasets with Missing Data[J].Pattern Recognition Letters,2008,29(6):803-812.

[14]Hall P,Martin M.On the bootstrap and two-sample problems[J].Austral J Statist,1988,30A(1):179-192.

[15]Wang Qihua,Rao J N K.Empirical likelihood-based inference in linear models with missing data[J].Scand J Statist,2002,29(3):563-576.

[16]Wang Qihua,Rao J N K.Empirical likelihood-based inference under imputation for missing response data[J].Ann Statist,2002,30(3):896-924.

[17]Zhang Shichao,Member S,IEEE.Parimputation:From imputation and null-imputation to partially imputation[J].IEEE Intelligent Informatics Bulletin,2008,9(1):32-38.

[18]Zhang Shichao.Shell-Neighbor method and its application in missing data imputation[EB/OL].(2010-02-20)[2010-02-28].http://www.springerlink.com/content/666244u672v6171v/.

[19]Owen A.Empirical likelihood[M].New York:Chapman & Hall,2001.

[20]Owen A.Data Squashing by Empirical Likelihood[J].Data Mining and Knowledge Discovery,2003,7(1):101-113.

[21]Blake C,Merz C.UCI Repository of machine learning database[ED/OL].[2009-08-21].http://www.ics.uci.edu/～mlearn/MLResoesitory.html.

[22]Cho Y B,Cho Y H,Kim S H.Mining changes in customer buying behavior for collaborative recommendations[J].Expert Systems with Applications,2005,28(2):359-369.

[23]Ying A T T,Murphy G C,Raymond T N,et al.Predicting Source Code Changes by Mining Change History[J].IEEE Trans Software Eng,2004,30(9):574-586.

[24]Little R,Rubin D.Statistical analysis with missing data[M].2nd ed.New York:John Wiley & Sons,2002.