基于商空間的不完備形式背景填補方法研究

張其文 王培瑾

(蘭州理工大學計算機與通信學院 甘肅 蘭州 730050)

0 引 言

實際生活中，因為人為因素、設備故障、隱私保護等原因，常常導致信息缺失。關(guān)于不完備決策形式背景，傳統(tǒng)處理方法直接刪除不完備信息記錄或采用擴展屬性的方法[1-2]。這雖然有助于更快地解決問題，但也破壞了原信息的完整性，降低了知識獲取的準確度。

為解決傳統(tǒng)填補算法的不足，提高補齊數(shù)據(jù)的識別率，相繼提出了基于屬性重要度與近似關(guān)系為主線的填補策略[3-6]。這類方法在特征屬性缺失率較大時，填補效果較差。Huang等[7]提出K近鄰補全算法；武森等[8]基于不完備數(shù)據(jù)聚類算法對缺失數(shù)據(jù)進行填補。這些方法的不足之處是填補效果完全取決于聚類的精度與樣本數(shù)據(jù)的平均值，在填補選擇上具有一定的局限性。張孫力等[9]利用數(shù)據(jù)的偏向特性，根據(jù)k個近鄰數(shù)據(jù)與缺失數(shù)據(jù)之間的距離，對k個近鄰賦予不同的權(quán)值，使補全的數(shù)據(jù)更加有效、合理。袁景凌等[10]針對綠色數(shù)據(jù)中心數(shù)據(jù)收集不完備和斷電等因素造成的數(shù)據(jù)缺失情況，提出了基于完備相容類的不完備大數(shù)據(jù)填補算法，其填補算法架構(gòu)在云平臺上通過并行化處理，提高了算法的時間和空間效率。

粒計算GrC(Granular Computing)[11]作為目前的熱門研究領(lǐng)域，在解決大量復雜數(shù)據(jù)時，通過粒的思想把復雜的問題抽象化為簡單問題來分析與求解。商空間是張鈴等[12]提出來的一種粒計算模型。用三元組(X,f,T)來替代描述問題，X表示問題的對象集，f表示對象對應的屬性集，T表示對象集上的結(jié)構(gòu)，代指對象間的相互關(guān)系。在不同粒度上對問題進行觀察，并在其間相互轉(zhuǎn)換，對不同的問題取不同的粒度來求解，這樣的思維方式稱之為商空間法。

本文在粒度思想的指導下，通過粒計算商空間模型，定義了不完備決策形式背景上的近似關(guān)系，構(gòu)造了模糊近似評估矩陣。通過傳遞閉包算法得到最小傳遞關(guān)系的模糊等價評估矩陣，實現(xiàn)了對對象集的?；?，得到了不同粒度大小的商集，探討了商屬性取值分布情況，給出了完整的缺失數(shù)據(jù)填補方法。實驗結(jié)果分析表明，選擇適宜的粒度劃分，能夠得到較高準確率的填補結(jié)果。

1 基本概念與相關(guān)定理

1.1 基本概念

形式概念分析FCA(Formal Concept Analysis)[13]自1982年作為一種數(shù)據(jù)處理的理想工具被德國數(shù)學家Wille.R提出后，一直廣泛應用于數(shù)據(jù)挖掘、信息檢索、故障診斷等眾多領(lǐng)域。

定義1形式背景由三元組(U,A,I)構(gòu)成，U為對象集，A為屬性集，I表示U和A之間的二元關(guān)系，有u∈U,a∈A，用(u,a)∈I(或‘uIa’)表示對象u具有屬性a，相反的，若對象u不具有屬性a，記作(u,a)?I(或‘uI-a’)。

定義2決策形式背景(U,A∪D,W,I)，U={u1,u2,…，un}表示對象集，A∪D表示屬性集，其中A={a1,a2,…,ak}表示條件屬性，D=j5i0abt0b表示決策屬性，且滿足A∩D=φ，W=∪(A∪D)表示屬性值集合，I滿足映射：I：I(U,A∪D)∈W。

在不完備決策形式背景中，條件屬性的缺失，會加大決策難度，甚至有時決策屬性也會缺失。在四元組表示的決策形式背景中，用W=*(包含空值)表示對象與屬性之間的缺失情況或未知情況，即有?u∈U，?a∈A,d∈D，I(u,a)=*orI(u,d)=*，‘*’代表的信息是存在的，也是不確定的，其在屬性上的取值也是多形態(tài)分布的。如表1所示。

表1 不完備決策形式背景

定義3[12]問題(X,f,T)，有X上模糊近似關(guān)系R，令[X]={[x]|x∈X}，則(X,f,T)對應R的商空間為([X],[f],[T])，稱[X]是X關(guān)于R的商集，[f]為商屬性，[T]為商拓撲。

定義4給定X上的模糊近似關(guān)系R，設Rλ為截等關(guān)系，有:

Rλ={(x1,x2)|R(x1,x2)≥λ}

式中：λ∈[0,1]，截等關(guān)系Rλ對應的商空間為([X],[f],[T])λ，X(λ)為X上的分層遞階結(jié)構(gòu)。

定義5X上的兩個模糊近似關(guān)系R1、R2，若存在?(x1,x2)∈X×X，有R1(x1,x2)?R2(x1,x2)，稱R1的粒度比R2的粒度粗，記作R1?R2。

由定義5，得到商空間([X]，[f],[T])λ上的近似關(guān)系序列為：R1?R2?…?Ri-1?Ri，R1為最粗粒度，Ri為最細粒度。模糊近似關(guān)系R下，得到分層遞階結(jié)構(gòu)，不同的截等關(guān)系對應不同的商空間結(jié)構(gòu)。隨著λ的減小，約束條件逐漸減弱，粒度加粗，每一個粒子的形態(tài)結(jié)構(gòu)也越大，包含的對象個數(shù)越多，其反應的信息精細程度與相應的求解也就越模糊。

1.2 近似精度

定義6設K=(U,A∪D,W,I)為不完備決策形式背景，對于?ui,uj∈U，ak∈A，滿足映射：uj→tui(uj)∈[0,1]，(i,j=1,2,…,n)，t為近似函數(shù)，對象之間的近似度表示如下：

tui(uj)=

(1)

可以看出，對象ui、uj越近似，tui(uj)的值越大，反之，其值越小。其中，|I(ui,ak)∩I(uj,ak)|表示取對象ui與uj在條件屬性取值相同時的基數(shù)。

由定義6，得到如下推論：

推論任一對象u∈U相對于對象ui∈U-u,(i=1,2,…,n)的平均近似度為:

(2)

由于屬性是取多值的，在計算帶有缺失數(shù)據(jù)的對象近似度時，不能直接認定|*∩*|=1，于是提出近似度上界、下界描述對象之間的近似關(guān)系，具體定義如下：

定義7對象ui、uj若在條件屬性取值上存在如下一種或同時缺失的情況：

I(ui,ak)=*∧I(uj,ak)=*∧I(ui,ak)=

I(uj,ak)=*

1.3 模糊近似評估矩陣

在不完備決策形式背景上，由于存在缺失數(shù)據(jù)。傳統(tǒng)的模糊近似矩陣不能真實的反應對象間的近似關(guān)系，故重新定義為模糊近似評估矩陣為：

定義9模糊近似評估矩陣M=(mij)n×n中的元素mij=[α,ω]定義為：

(3)

式中:i,j=1,2,…,n，n=|U|。在矩陣中每一個元素包含兩個值，α表示對象ui、uj的模糊近似度。

由表1得到模糊近似評估矩陣如表2所示。

表2 模糊近似評估矩陣

對模糊近似評估矩陣用平方法作傳遞閉包運算，得到包含模糊近似關(guān)系R上的最小傳遞關(guān)系的模糊等價評估矩陣M*。然后對對象集U進行?；?，按照不同的約束條件Ci(i=1,2,…,n)取不同的粒度劃分，得到樹形的分層遞階結(jié)構(gòu)。根據(jù)實際需求，確定閾值，由定義5，求解出模糊關(guān)系R下的Rλ截矩陣。形成商集[X]λ={[X1],[X2],[X3],…}?？梢钥闯觯恳粋€截等關(guān)系對應一分層遞階結(jié)構(gòu)，本質(zhì)說來，商集即是對象粒，表示為:

[X]={u|u∈U∨Rλ(u)∈C}

由分層遞階結(jié)構(gòu)可以知道，隨著λ的減小，商集所描述的對象粒的粒度也就越粗。

(X,f,T)對應的商空間為([X],[f],[T])，由于原始對象中的屬性在?；笾苯佑绊懮虒傩缘娜≈担碳瘜纳虒傩匀≈狄簿筒恢挂环N情況，不同近似度閾值也會有不同的填補結(jié)果。為準確描述不同的填補值權(quán)值分布，引入支持度和置信度：

定義10商屬性[f]中，包含屬性值w(w∈W)的支持度、置信度分別為support(w)、confidence(w)。

定義11商屬性[f]中，屬性a(a∈A)的值域為W，那么商集[X]在a的取值w的置信度為：

(4)

式中：support(W)表示商集[X]中屬性值的個數(shù)。

定義12商屬性[f]中，屬性值w權(quán)重計算公式為：

Weight(w)=confidence(w)×η

(5)

2 基于商空間的填補算法

2.1 算法描述

不完備決策形式背景K=(U,A∪D,W,I)中，基于粒計算商空間模型的填補算法：

輸入：不完備決策形式背景K=(U,A∪D,W,I)；

Step1初始化，A≠φ,D≠φ。

Step3計算α、ω，導出模糊近似評估矩陣M。

Step4借助傳遞閉包算法，得到模糊等價評估矩陣M*。

Step5從M*上得到商空間分層遞階結(jié)構(gòu)序列，根據(jù)實際需求，確定閾值α、ω，得到截等關(guān)系Rλ，劃分商集[X]α。

Step6填補缺失數(shù)據(jù)

1) 商集[X]中對象屬性值w無缺失。

(1) 各對象屬性值w相同時，商屬性值[f]=w。

(2) 各對象屬性值w不同時，商屬性值[f]=w→max{confidence(w)}。

2) 商集[X]中對象屬性值w缺失。

(1) 缺失條件屬性A(?a∈A)，即I(u,a)=*時，[f](A)=w→max{Weight(w)}。

(2) 缺失決策屬性D(?d∈D)，即I(u,d)=*時，[f](D)=w→max{Weight(w)}。

基于商空間的填補算法，具有“高內(nèi)聚、低耦合”的特性，在不同的實際復雜問題中選取不同的粒度，并在其中相互轉(zhuǎn)換對比，得到不同的填補結(jié)果。將低近似度或完全獨立的不完備對象，劃分到一個粒中完成填補。在算法的應用環(huán)境上更具有普適性，對不同的結(jié)構(gòu)化數(shù)據(jù)填補能起到良好的效果。

2.2 實例分析

按照2.1節(jié)算法的描述，由表2得到表3的模糊等價評估矩陣。

表3 模糊等價評估矩陣

該模糊近似關(guān)系下，取近似精度ω≤0.6，其對應的分層遞階商空間序列為：

X(α1≥0)={{u1,u2,u3,u4,u5,u6,u7,u8,u9,u10}}

X(α2≥0.4)={{u1,u2,u3,u4,u5,u6,u7,u8,u9,u10}}

X(α3≥0.6)={{u1,u2,u4,u5,u6,u8,u9,u10},{u3,u7}}

X(α4≥0.7)={{u1,u4,u5,u8,u9},{u2,u6,u10},{u3,u7}}

X(α5≥0.8)={{u1,u4,u5,u9},{u2,u6},{u3,u7},{u8},{u10}}

X(α6≥1)={{u1},{u2},{u3},{u4},{u5},{u6},{u7},{u8},{u9},{u10}}

選取上述分層遞階結(jié)構(gòu)中α=0.7，得到商集[X]0.7={[X1],[X2],[X3]}，其中：

[X1]={{1}，{4},{5}，{8}，{9}}；
[X2]={{2}，{6}，{10}}；
[X3]={{3}，{7}}；

在該閾值下，得到商屬性填補值權(quán)重分布情況如表4所示。

表4 [X1]、[X2]、[X3]商屬性填補值權(quán)值分布

上述商屬性填補值分布表中可以看出，在實際問題分析中，屬性取值的多樣性，更有利于解決復雜問題，避免了遺漏關(guān)鍵小概率屬性值而導致獲取的知識不全。填補過程中，根據(jù)實際需要選擇不同的填補標準。完備決策形式背景取最大權(quán)值填補屬性后如表5所示(注：填補值權(quán)值相同時，同時填補到商屬性中)。

表5 完備決策形式背景

填補結(jié)果分析：

在粒度X(0.7)ω=0.6下，實現(xiàn)了對象集的?；瓿闪藢ι虒傩缘臄?shù)據(jù)填補。其中，對象u8的決策屬性為2，但在該粒度下屬于[X1]，決策屬性Weight(1)=0.46、Weight(2)=0.34，表明對象u8與決策屬性為1的對象在條件屬性取值上差異很小。

3 仿真實驗

3.1 實驗分析

為了進一步驗證本文提出的算法有效性，選用完備數(shù)據(jù)集Car Evaluation Data Set(數(shù)據(jù)庫來自：http://archive.ics.uci.edu/ml/datasets/Car+Evaluation)，數(shù)據(jù)庫總數(shù)1 728條，每條數(shù)據(jù)包含6個屬性，每個屬性包含至少3種不同的值，數(shù)據(jù)具體描述見表6。實驗選用500條數(shù)據(jù)，選取數(shù)據(jù)總數(shù)按照類別分布等比例選取，見表7。按照屬性相對重要度Safety>Persons>Buying>Lug_boot>Doors>Maint，人工對條件屬性與決策屬性添加缺失。實驗環(huán)境為：操作系統(tǒng)Windows7 64位，CPU Intel CORE i5 2.6 GHz，內(nèi)存6 GB。

表6 汽車評估數(shù)據(jù)集

表7 汽車評估數(shù)據(jù)集類別分布

基于商空間的數(shù)據(jù)填補算法中，對決策形式背景來講，完成數(shù)據(jù)填補工作的同時，得到其準確的決策屬性也是至關(guān)重要的。抑或是在缺失率較大的情況下，通過較大粒度的商集，來判定對象的決策屬性。為客觀的分析算法的實際效果，實驗操作從填補后的決策屬性準確率進行分析說明，針對不同的?；撝?，得到不同的填補結(jié)果。填補準確率公式為：

(6)

式中：c∈[0,1]，n表示決策屬性填補準確的個數(shù)，N表示數(shù)據(jù)總數(shù)。

圖1給出在缺失率為5%、15%、25%與35%情況下，隨著α與ω不同取值下準確率的變化情況。

(a) 缺失率為5%

(b) 缺失率為15%

(c) 缺失率為25%

(d) 缺失率為35%圖1 不同缺失率下的準確率變化

整體上，在粒度閾值取α偏大，ω偏小時，得到的準確率最高。圖1中，隨著α的增大，準確率出現(xiàn)下降的情況，因為此時的約束條件越來越嚴格，?；潭仍絹碓礁?。當α=1時，商集則表示獨立的對象個體，對象中屬性包含缺失數(shù)據(jù)，故準確率降低。在四種缺失率中，隨著缺失率的增大，α對應準確率到達峰值的取值逐漸減小，故在實際生活運用中，可以根據(jù)實際的需要去?；瘜ο?，獲取最優(yōu)解。

3.2 對比分析

為進一步驗證本文提出的基于商空間填補算法的有效性，選擇文獻[5]中IATS算法進行對比分析，利用文獻中兩種數(shù)據(jù)缺失類型：常規(guī)缺失(MIN)和異常缺失(MIA)，生成同樣的缺失數(shù)據(jù)集比例進行填補研究，分析結(jié)果如圖2所示。

圖2 準確率對比分析

由圖2可知，在缺失率較低時，IATS的準確率略微高于本文填補算法，但隨著缺失率的增大，本文提出的填補算法準確率逐漸高于IATS，體現(xiàn)出本文算法在缺失率較高時的優(yōu)勢。

4 結(jié) 語

本文提出的基于商空間的缺失數(shù)據(jù)填補方法，在處理缺失率較大的數(shù)據(jù)集時，能有效地提高填補效率。實驗結(jié)果表明，合理粒度下，在推估、填補不完備信息時能保持較高準確度。在下一步的工作中，將研究如何選取更合理的閾值。