基于確定性因子的啟發(fā)式屬性值約簡模型

余順坤，閆泓序

（華北電力大學經(jīng)濟與管理學院，北京 102206）

0 引言

作為一種新型軟計算理論與智能算法，粗糙集理論可以有效處理具有不確定、不精確或不完整信息的數(shù)據(jù)［1-2］。它能夠在不依靠任何先驗知識的情況下，只根據(jù)數(shù)據(jù)本身完成挖掘和推理［3］，是對專家系統(tǒng)進行數(shù)據(jù)挖掘的強大工具［4-5］。屬性值約簡是粗糙集理論研究和應用的核心課題之一，也是構(gòu)建規(guī)則提取算法［6-13］和歸納規(guī)則分類器［14-15］的重要技術基礎。屬性值約簡是指在不影響決策系統(tǒng)知識表達能力的前提下，去除其中冗余屬性值的過程［16］，它不但能夠從原始數(shù)據(jù)庫中直接提取出可讀性高、便于應用的簡約規(guī)則，而且還能在不降低專家系統(tǒng)可分辨性的基礎上提高其清晰度，并從中揭示出以往未知、有潛在價值的信息，從而實現(xiàn)知識發(fā)現(xiàn)［10，16］。

目前，針對構(gòu)建屬性值約簡模型這一問題，學術界已經(jīng)取得一定進展，主要包括基于區(qū)分矩陣的屬性值約簡模型［10，13，17-19］以及啟發(fā)式屬性值約簡模型［20-23］兩個建模方向。其中，基于區(qū)分矩陣的屬性值約簡模型思想簡單，易于理解；但當將其應用于大規(guī)模數(shù)據(jù)集時，往往需要構(gòu)造與遍歷大型矩陣，導致算法的時間與空間復雜度較高。另一方面，大多數(shù)啟發(fā)式屬性值約簡模型程序復雜，難以實現(xiàn)，且計算復雜度較高。最近，Chen 等［9］提出了一種基于決策依賴度的啟發(fā)式屬性值約簡模型，能夠有效控制算法的時?空復雜度，但僅適用于具有較高重復性或冗余性的數(shù)據(jù)集，對數(shù)據(jù)本身特征要求較高。除此之外，現(xiàn)有屬性值約簡模型大多傾向于產(chǎn)生極簡短規(guī)則，導致專家系統(tǒng)的決策能力受到較大程度削弱，并且未能對數(shù)據(jù)庫進行多層次挖掘以獲得多元豐富的決策描述，導致數(shù)據(jù)知識的本質(zhì)特征和內(nèi)在規(guī)律沒有被充分發(fā)現(xiàn)與理解。

針對以上問題，在現(xiàn)有研究的基礎上，本文提出了一種基于確定性因子的啟發(fā)式屬性值約簡模型。首先，簡要闡述粗糙集理論的相關理論基礎；然后，開發(fā)了幾種不同性質(zhì)的屬性集工具，用韋恩圖的形式直觀展示它們的邏輯聯(lián)系，并提出相關定理與證明；其次，構(gòu)造一個約簡信息函數(shù)，為約簡屬性賦值；再次，將確定性因子作為啟發(fā)信息，提出一種新的屬性值約簡模型，簡稱CerFac 模型，并給出其程序偽代碼，以直觀展示模型運行路徑；最后，采用已有研究中的模擬數(shù)據(jù)開展模型應用與驗證，并對模型特點進行總結(jié)與討論。研究表明，CerFac 模型可以有效去除冗余信息，并能導出多元簡約規(guī)則，同時易于編程實現(xiàn)。特別地，新模型適用于重復或冗余較少的數(shù)據(jù)集，對數(shù)據(jù)結(jié)構(gòu)要求低，且應用范圍廣泛。

1 理論基礎

先簡要回顧粗糙集理論的相關理論基礎［1-2］。

定義1決策系統(tǒng)。設S=(U，A，V，f)為一個信息系統(tǒng)，其中，U={x1，x2，…，xn}為非空有限對象集，稱為論域；A={a1，a2，…，am}為非空有限屬性集；V為屬性值域，即V=，其中k=1，2，…，m，這里表示屬性ak∈A的取值；f：U×A→V稱為信息函數(shù)，它根據(jù)每個屬性為每個對象賦予一個信息值，即?xi∈U，?ak∈A，f(xi，ak)=。特別地，若A由一個條件屬性集C和一個決策屬性集D組成，且二者滿足C∪D=A，C∩D=?，則稱S為決策系統(tǒng)，表示為S=(U，C∪D，V，f)。當D中只有一個決策屬性d時，通常將決策系統(tǒng)表示為S=(U，C∪j5i0abt0b，V，f)。

定義2等價類。設S=(U，C∪j5i0abt0b，V，f)為決策系統(tǒng)，?xi，xj∈U，?P?C，P≠?，定義對象間關于P的不可分辨關系為：IND(P)={(xi，xj)|(xi，xj)∈U×U，?ak∈P，f(xi，ak)=f(xj，ak)}。對象x（ii≤n）關于IND（P）的等價類定義為：

[xi]IND(P)={xj|(xi，xj)∈IND(P)}

定義3確定性因子。設S=(U，C∪j5i0abt0b，V，f)為決策系統(tǒng)，?xi∈U，?P?C，P≠?，定義決策對象xi關于不可分辨關系IND（P）與IND（d）的確定性因子為：

顯然0

2 CerFac模型

下面先介紹本文CerFac 模型的相關概念與符號。

定義4k-屬性集。設S=(U，C∪j5i0abt0b，V，f)為決策系統(tǒng)，其中：|C|=m；?aj∈C（j=1，2，…，m），定義含有k個屬性的集合為k-屬性集，表示為Ak，即Ak={A?C||A|=k}，其所含元素總數(shù)為從m個屬性中隨機抽取k個的組合數(shù)。A*k={Ak|1≤k≤m，k∈Z}為決策系統(tǒng)中條件屬性的全部可能組合，稱之為系統(tǒng)屬性格結(jié)構(gòu)，k為格結(jié)構(gòu)的層次。

特定對象xi的k-屬性集稱為k-對象屬性集，表示為Ai，k，將Ai，k中的各屬性元素ai，k∈Ai，k按照以下標準進行劃分：

1）若決策對象xi關于ai，k的信息表達能力與關于屬性集C的一致，則將ai，k定義為xi的k-核屬性（或集合），全部k-核屬性（或集合）稱為k-核屬性集，表示為coreAi，k，即cer(coreAi，k，xi)=cer(C，xi)。反之，則將ai，k定義為xi的k-非核屬性（或集合），全部k-非核屬性（或集合）稱為k-非核屬性集，表示為ncoreAi，k，即cer(ncoreAi，k，xi)≠cer(C，xi)。

2）若ai，k為xi的最小k-核屬性（或集合），則將ai，k定義為xi的k-約簡屬性（或集合），全部k-約簡屬性（或集合）稱為k-約簡屬性集，表示為redAi，k，即redAi，k=，其中，?ni，k-1∈ncoreAi，k-1。反之，則將ai，k定義為xi的k-非約簡屬性（或集合），全部k-非約簡屬性（或集合）稱為k-非約簡屬性集，表示為nredAi，k。有nredAi，k=ncoreAi，k+sredAi，k，其中，sredAi，k表示xi的k-約簡屬性集超集，它是一種包含（k-1）層約簡屬性的k-核屬性集，它雖能保持xi的信息表達能力不變，但并非最小集合，因此屬于k-非約簡屬性集。

3）對象xi的k-屬性集Ai，k由redAi，k、sredAi，k與ncoreAi，k綜合構(gòu)造而成，即Ai，k=redAi，k+sredAi，k+ncoreAi，k。

為了清晰形象地說明Ai，k、coreAi，k、ncoreAi，k、redAi，k、nredAi，k與sredAi，k之間的邏輯關系，以下進一步給出其韋恩圖，如圖1 所示的k-對象屬性集元素韋恩圖，其中redAi，k、sredAi，k與ncoreAi，k不同時為空集。

圖1 k-對象屬性集元素韋恩圖Fig.1 Venn diagram for elements within a k-object attribute set

定義5k-候選約簡屬性集。定義決策對象的潛在k-約簡屬性集為k-候選約簡屬性集，表示為candAi，k，其由（k-1）層非核屬性（或集合）構(gòu)造而成，即candAi，k=，其中，?ni，k-1∈ncoreAi，k-1。對于candAi，k，有以下定理成立：

定理1對于決策系統(tǒng)S中某對象xi，其k-候選約簡屬性集由k-約簡屬性集及k-非核屬性集構(gòu)成，即?xi∈U，有candAi，k=redAi，k+ncoreAi，k成立。

證明 因為?xi∈U（k=1，2，…，m），redAi，k-1、sredAi，k-1與ncoreAi，k-1不同時為空集。根據(jù)定義4，第k層屬性集Ai，k由第k-1 層屬性集redAi，k-1、sredAi，k-1與ncoreAi，k-1構(gòu)成；又因為redAi，k-1或sredAi，k-1將構(gòu)成sredAi，k，所以Ai，k=sredAi，k+，其中，?ni，k-1∈ncoreAi，k-1；根據(jù)定義4，有Ai，k=sredAi，k+redAi，k+ncoreAi，k，所以=redAi，k+ncoreAi，k；又根據(jù)定義5，有candAi，k=，即candAi，k=redAi，k+ncoreAi，k，綜上得證。

根據(jù)定義5 和定理1，即可構(gòu)造CerFac 模型，其基本思想是：對于特定決策對象的某一屬性格層k，首先應用確定性因子過濾出k-1 層非核屬性；然后將其進行組合，構(gòu)造形成第k層候選約簡屬性集；據(jù)此，再次利用確定性因子進行過濾，即可獲取決策對象的第k層約簡屬性集。

定義6約簡信息函數(shù)。設S=(U，C∪j5i0abt0b，V，f)為決策系統(tǒng)，dred(S)=(U，A*∪j5i0abt0b，V*，f*)為論域?qū)傩灾导s簡系統(tǒng)，由每個決策對象xi∈U的屬性值約簡dred(Si)組合而成。其中：A*i為對象xi的非空有限k-屬性組合；V*i為對象xi的約簡屬性信息值域；f*為約簡信息函數(shù)，它為決策對象的每個屬性組合賦予特定的信息值。?xi∈U（i=1，2，…，n），A*i=redA*i∪ncoreA*i∪sredA*i，?a*i∈A*i，?aj∈a*i（j=1，2，…，m），定義約簡信息函數(shù)f*如下：

應用CerFac 模型獲取的dred（S）中存在大量重復條目信息行，對其執(zhí)行去重操作，將得到非重復論域?qū)傩灾导s簡系統(tǒng)，記為ddred(S)=(U*，A*∪j5i0abt0b，V*，f*)，系統(tǒng)排列方式按照約簡層次k與k-屬性組合的形式進行分布，對其依照決策系統(tǒng)的分布形式進行格式標準化，即可得到?jīng)Q策屬性值約簡系統(tǒng)，記為red(S)=(R，C∪j5i0abt0b，V*，f*)。

3 CerFac屬性值約簡模型

應用以上不同性質(zhì)的屬性集工具，將確定性因子作為啟發(fā)信息，即可自底向上地搜索到?jīng)Q策系統(tǒng)的全部約簡屬性，再應用約簡信息函數(shù)對約簡屬性進行賦值，即可獲取決策系統(tǒng)的全體屬性值約簡。在此，構(gòu)建基于確定性因子的屬性值約簡模型CerFac，模型程序偽代碼如下所示，其主要包括三大模塊：

1）模塊A。首先，在k屬性格層上，將對象xi的候選約簡屬性集candAi，k作為中間變量，獲取其約簡屬性集redAi，k；其次，利用約簡信息函數(shù)f*為redAi，k賦值Vi，k；然后，綜合以上結(jié)果獲取決策對象xi的屬性值約簡dred（Si）；最后，循環(huán)以上步驟，生成論域內(nèi)每個決策對象的屬性值約簡，再將其進行組合，形成論域?qū)傩灾导s簡系統(tǒng)dred（S）。

2）模塊B。對dred（S）執(zhí)行去重操作，生成非重復論域?qū)傩灾导s簡系統(tǒng)ddred（S）。

3）模塊C。對ddred（S）進行格式標準化，最終獲取決策屬性值約簡系統(tǒng)red（S）。

模塊A 是CerFac 模型的核心模塊，其主要功能是對特定決策對象的屬性組合類型進行精準劃分，通過一個具體例子，來對該模塊的執(zhí)行過程進行形象直觀說明，如圖2 所示的CerFac 模型中模塊A 執(zhí)行概覽。

圖2 中展示了某決策對象的屬性格結(jié)構(gòu)，其中，自上而下依次為第0 至第m（條件屬性總數(shù)）層屬性格。相鄰兩屬性格層之間的連線代表將多個屬性（或集合）組合成為更大的屬性集。假設圖中某一決策對象xi的條件屬性集為｛A，B，C，D｝，其所有可供構(gòu)造的k-屬性組合如圖所示。以第k=1 屬性格層為例，若屬性A經(jīng)確定性因子檢查是核屬性（在此，亦為約簡屬性），那么其超集｛｛A，B｝，｛A，C｝，｛A，D｝｝（格層k=2）、｛｛A，B，C｝，｛A，B，D｝，｛A，C，D｝｝（格層k=3）以及｛A，B，C，D｝（格層k=4）將不再執(zhí)行算法在高序格層上的循環(huán)遍歷。同時，在第k=1 格層上的非核屬性｛B｝、｛C｝和｛D｝，將構(gòu)成k=2 格層上的候選約簡屬性集｛B，C｝、｛B，D｝和｛C，D｝，再次利用確定性因子進行檢查，將其中保持對象確定性因子不變的非核屬性集標記為此格層的約簡屬性集，如｛B，C｝、｛B，D｝，其他則仍舊作為本格層的非核屬性集，如｛C，D｝。若本格層的非核屬性集總數(shù)不小于下一格層編碼，則繼續(xù)組合本格層的非核屬性集，以作為下一格層的候選約簡屬性集，進而循環(huán)算法；反之，則終止算法。

圖2 CerFac模型中模塊A執(zhí)行概覽Fig.2 Execution overview of CerFac model-Module A

由此可知，CerFac 模型秉承自下而上的屬性值約簡策略，即從決策對象的低屬性格層出發(fā)，一旦在低格層上搜索到約簡屬性（或集合），那么對于其他所有高格層中包含該約簡屬性（或集合）的屬性組合將不再運行本文算法，這將顯著提升算法的時?空效率。

4 仿真算例

以文獻［9］中的算例數(shù)據(jù)為例，舉例說明本文模型CerFac 的應用步驟，其中算例數(shù)據(jù)集、模型應用過程及相應結(jié)果如圖3 所示的仿真算例分析所示。模型具體應用過程如下：

1）模塊A。圖3（a）為算例數(shù)據(jù)集，從中可看出，該數(shù)據(jù)集為相容決策系統(tǒng)，表示為S=（U，C∪｛e｝，V，f），其中論域U=｛x1，x2，…，x27｝，條件屬性集C=｛a，b，c，d｝，決策屬性為e。以對象x9為例，展示應用本模型搜索其屬性值約簡的具體過程。

首先，根據(jù)定義4，生成x9的k-對象屬性集A9，k，其中k∈{1，2，3，4}，得A*k={A9，1，A9，2，A9，3，A9，4}={{a，b，c，d}，{ab，ac，ad，bc，bd，cd}，{abc，abd，acd，bcd}，{abcd}}。

然后，根據(jù)定義5 獲取各k層候選約簡屬性集以及約簡屬性（或集合）：

當k=1 時，對象x9的候選約簡屬性集為candA9，1=｛a，b，c，d｝，根據(jù)定義3，計算candA9，1內(nèi)各元素在論域范圍內(nèi)的確定性因子cer（candA9，1，x9）=｛2/9，1，2/3，3/7｝，據(jù)此，將確定性因子1 對應的屬性反選為對象x9的約簡屬性，即redA9，1=｛b｝，那么x9的非核屬性集為ncoreA9，1=candA9，1-redA9，1=｛a，c，d｝，因為|ncoreA9，1|>k+1，因而進行下一循環(huán)。

當k=2 時，同理，對象x9的候選約簡屬性集由k=1 層的非核屬性組合而成，即candA9，2=｛ac，ad，cd｝，其中各元素確定性因子為cer（candA9，2，x9）=｛1，2/5，1｝，則對象x9的約簡屬性集為redA9，2=｛ac，cd｝，那么對象x9的非核屬性集為ncoreA9，2=｛ad｝，由于|ncoreA9，2|

由此獲取到對象x9的各層約簡屬性（或集合），根據(jù)定義6，應用約簡信息函數(shù)為全部所得約簡結(jié)果賦予約簡信息值，即可生成對象x9的各層屬性值約簡dred（S9）。同理，可搜索到論域范圍內(nèi)其他全部對象的屬性值約簡dred（Si），再次根據(jù)定義6，將其進行組合，即可形成各約簡層次上的論域?qū)傩灾导s簡系統(tǒng)dred（S），相關結(jié)果如圖3（b）～（d）所示，其中：圖3（b）為決策系統(tǒng)S在k=1 約簡層次上的論域?qū)傩灾导s簡系統(tǒng)；圖3（c）為S在k=2 層的論域?qū)傩灾导s簡系統(tǒng)；圖3（d）為S在k=3 層的論域?qū)傩灾导s簡系統(tǒng)。

2）模塊B。經(jīng)模塊A，在dred（S）中生成了較多條目的重復屬性值約簡信息行，對其執(zhí)行去重操作，即可得到非重復論域?qū)傩灾导s簡系統(tǒng)ddred（S）。圖3（e）為決策系統(tǒng)S在各約簡層次上的非重復論域?qū)傩灾导s簡系統(tǒng)。

3）模塊C。經(jīng)模塊B，獲取到屬性依照約簡層次k及屬性組合Ak排列的非重復論域?qū)傩灾导s簡系統(tǒng)，對其按決策系統(tǒng)S進行格式標準化，最終生成決策屬性值約簡系統(tǒng)red（S）。圖3（f）為決策系統(tǒng)S的決策屬性值約簡系統(tǒng)。

圖3 仿真算例分析Fig.3 Simulation example analysis

5 討論

與現(xiàn)有研究相比，應用本文CerFac 模型搜索到的屬性值約簡具有更高預測精度。比如，文獻［9］從此算例數(shù)據(jù)集中先后挖掘得到的、能夠匹配對象x19({a3∧b1∧c1∧d2→e3})的屬性值約簡依次為{a*∧b*∧c1∧d2→e2}與{a*∧b*∧c1∧d*→e3}，它無論基于規(guī)則覆蓋率（匹配具有更多一致屬性值的約簡規(guī)則），還是規(guī)則生成順序（匹配優(yōu)先生成的約簡規(guī)則），都無法準確預測對象x19，但是CerFac 模型所推演出的屬性值約簡能對文獻［9］中的全部算例數(shù)據(jù)實現(xiàn)精準預測。

CerFac 模型并非一種逐步剪枝策略，即無需一步步地去除約簡屬性超集，就可直接得到特定對象的屬性約簡。此外，新模型聚焦于某決策對象較低格層的非核屬性集，將確定性因子作為啟發(fā)信息，經(jīng)過簡單掃描，即可獲取較高格層的屬性值約簡，亦即直接生成多元、簡約，且不影響決策對象信息表達能力的規(guī)則描述，這些優(yōu)勢使得CerFac 模型易于計算、編程和執(zhí)行。

CerFac 模型所生成的簡明規(guī)則具有較強泛化性與描述力，這使得基于CerFac 模型的分類器具有比較高的穩(wěn)健性。此外，新模型能夠深度挖掘出決策對象多種可能的屬性值約簡結(jié)果，利用某些個性化篩選標準對其進行提取，如規(guī)則置信度、規(guī)則提升度及規(guī)則覆蓋度等，即可提取出符合需求、有價值的簡約規(guī)則，因此CerFac 模型為基于確定性因子的粗糙規(guī)則提取算法奠定了技術基礎。

CerFac 模型的算法復雜度與決策系統(tǒng)中每個實例對象的條件屬性取值及數(shù)據(jù)規(guī)模有關，如設某決策系統(tǒng)含有n個對象，m個條件屬性，則：當系統(tǒng)中每一條決策對象的條件屬性取值均各不相同時，模型處于最好情況，此時算法時間復雜度為O（n2m）；而當系統(tǒng)中每一條決策對象的條件屬性取值均相同，而決策屬性值不同時（即完全矛盾系統(tǒng)），模型處于最差情況，此時算法時間復雜度為O（2mn2）。由此，當模型應用于海量數(shù)據(jù)時，對決策系統(tǒng)先行進行純化處理［24-25］，或基于MapReduce［26-27］并行運算框架，優(yōu)先完成行（元組）約簡與列（屬性）約簡［28-30］，將使本模型的運行成本得到進一步改善，這也是下一步的研究方向。此外，新模型將為決策系統(tǒng)推導出多元豐富的簡約規(guī)則，因此，適用于需要全面性規(guī)則來指導實踐的研究領域，如市場營銷［12，31］等，或是針對成熟專家系統(tǒng)，要求較高預測精度的知識發(fā)現(xiàn)任務，如醫(yī)療診斷［32］等。

6 結(jié)語

本文針對現(xiàn)有屬性值約簡模型的不足，構(gòu)建了一種基于確定性因子的自底向上型啟發(fā)式屬性值約簡模型。首先，根據(jù)粗糙集理論，設計了幾種不同性質(zhì)的屬性集工具，并將確定性因子作為啟發(fā)信息，從中分層搜索特定決策對象的約簡屬性；然后，開發(fā)了約簡信息函數(shù)，從而實現(xiàn)為決策對象的約簡屬性賦值；其次，以程序偽代碼的形式，直觀展示了模型的布置路徑與運行流程；再次，以現(xiàn)有研究中的仿真數(shù)據(jù)為載體，對模型進行了應用與驗證；最后，討論了模型的優(yōu)勢、適用性與延展性。研究表明，新模型可行有效、科學先進，同時具有廣闊的應用前景。未來的研究將集中于以下幾個方面：1）從行、列約簡的角度提升算法效率；2）構(gòu)建基于CercFac 模型的規(guī)則提取算法；3）構(gòu)建基于CercFac 模型的歸納規(guī)則分類器。