張其文 王培瑾

(蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院 甘肅 蘭州 730050)

0 引 言

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

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

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

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

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

1.1 基本概念

形式概念分析FCA(Formal Concept Analysis)[13]自1982年作為一種數(shù)據(jù)處理的理想工具被德國數(shù)學(xué)家Wille.R提出后，一直廣泛應(yīng)用于數(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=e8m0qk0表示決策屬性，且滿足A∩D=φ，W=∪(A∪D)表示屬性值集合，I滿足映射：I：I(U,A∪D)∈W。

在不完備決策形式背景中，條件屬性的缺失，會(huì)加大決策難度，甚至有時(shí)決策屬性也會(huì)缺失。在四元組表示的決策形式背景中，用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)對應(yīng)R的商空間為([X],[f],[T])，稱[X]是X關(guān)于R的商集，[f]為商屬性，[T]為商拓?fù)洹?/p>

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

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

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

定義5X上的兩個(gè)模糊近似關(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為最細(xì)粒度。模糊近似關(guān)系R下，得到分層遞階結(jié)構(gòu)，不同的截等關(guān)系對應(yīng)不同的商空間結(jié)構(gòu)。隨著λ的減小，約束條件逐漸減弱，粒度加粗，每一個(gè)粒子的形態(tài)結(jié)構(gòu)也越大，包含的對象個(gè)數(shù)越多，其反應(yīng)的信息精細(xì)程度與相應(yīng)的求解也就越模糊。

1.2 近似精度

定義6設(shè)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í)的基數(shù)。

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

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

(2)

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

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

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

I(uj,ak)=*

1.3 模糊近似評估矩陣

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

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

(3)

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

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

表2 模糊近似評估矩陣

對模糊近似評估矩陣用平方法作傳遞閉包運(yùn)算，得到包含模糊近似關(guān)系R上的最小傳遞關(guān)系的模糊等價(jià)評估矩陣M*。然后對對象集U進(jìn)行?；凑詹煌募s束條件Ci(i=1,2,…,n)取不同的粒度劃分，得到樹形的分層遞階結(jié)構(gòu)。根據(jù)實(shí)際需求，確定閾值，由定義5，求解出模糊關(guān)系R下的Rλ截矩陣。形成商集[X]λ={[X1],[X2],[X3],…}。可以看出，每一個(gè)截等關(guān)系對應(yīng)一分層遞階結(jié)構(gòu)，本質(zhì)說來，商集即是對象粒，表示為:

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

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

(X,f,T)對應(yīng)的商空間為([X],[f],[T])，由于原始對象中的屬性在?；笾苯佑绊懮虒傩缘娜≈担碳瘜?yīng)的商屬性取值也就不止一種情況，不同近似度閾值也會(huì)有不同的填補(bǔ)結(jié)果。為準(zhǔn)確描述不同的填補(bǔ)值權(quán)值分布，引入支持度和置信度：

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

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

(4)

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

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

Weight(w)=confidence(w)×η

(5)

2 基于商空間的填補(bǔ)算法

2.1 算法描述

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

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

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

Step3計(jì)算α、ω，導(dǎo)出模糊近似評估矩陣M。

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

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

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

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

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

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

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

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

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

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

2.2 實(shí)例分析

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

表3 模糊等價(jià)評估矩陣

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

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}}；

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

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

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

表5 完備決策形式背景

填補(bǔ)結(jié)果分析：

在粒度X(0.7)ω=0.6下，實(shí)現(xiàn)了對象集的?；?，完成了對商屬性的數(shù)據(jù)填補(bǔ)。其中，對象u8的決策屬性為2，但在該粒度下屬于[X1]，決策屬性Weight(1)=0.46、Weight(2)=0.34，表明對象u8與決策屬性為1的對象在條件屬性取值上差異很小。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)分析

為了進(jìn)一步驗(yàn)證本文提出的算法有效性，選用完備數(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個(gè)屬性，每個(gè)屬性包含至少3種不同的值，數(shù)據(jù)具體描述見表6。實(shí)驗(yàn)選用500條數(shù)據(jù)，選取數(shù)據(jù)總數(shù)按照類別分布等比例選取，見表7。按照屬性相對重要度Safety>Persons>Buying>Lug_boot>Doors>Maint，人工對條件屬性與決策屬性添加缺失。實(shí)驗(yàn)環(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ù)填補(bǔ)算法中，對決策形式背景來講，完成數(shù)據(jù)填補(bǔ)工作的同時(shí)，得到其準(zhǔn)確的決策屬性也是至關(guān)重要的。抑或是在缺失率較大的情況下，通過較大粒度的商集，來判定對象的決策屬性。為客觀的分析算法的實(shí)際效果，實(shí)驗(yàn)操作從填補(bǔ)后的決策屬性準(zhǔn)確率進(jìn)行分析說明，針對不同的?；撝担玫讲煌奶钛a(bǔ)結(jié)果。填補(bǔ)準(zhǔn)確率公式為：

(6)

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

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

(a) 缺失率為5%

(b) 缺失率為15%

(c) 缺失率為25%

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

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

3.2 對比分析

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

圖2 準(zhǔn)確率對比分析

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

4 結(jié) 語

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