吳正江，張亞寧，張 真，梅秋雨，楊 天

（河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454003）

0 概述

經(jīng)典的粗糙集［1］在沒(méi)有任何先驗(yàn)知識(shí)的情況下，通過(guò)上下近似集表示某個(gè)確定的概念，能夠處理具有不確定性、不一致性等特點(diǎn)的數(shù)據(jù)集。粗糙集理論廣泛應(yīng)用于數(shù)據(jù)挖掘［2］、推薦系統(tǒng)［3］、工業(yè)控制系統(tǒng)［4-5］等領(lǐng)域。

信息系統(tǒng)可能伴有部分缺失值或集值。研究人員提出了容差關(guān)系［6］、非對(duì)稱相似關(guān)系［7］、限制性容差關(guān)系［8］、最大相容類［9］等二元關(guān)系代替不可區(qū)分關(guān)系，使得泛化的粗糙集模型能夠處理集值信息系統(tǒng)。文獻(xiàn)［10-11］提出擬單層覆蓋粗糙集界于一般覆蓋與劃分之間，是一個(gè)特殊的鄰域系統(tǒng)。近似質(zhì)量是衡量一個(gè)模型的標(biāo)準(zhǔn)，文獻(xiàn)［12］將擬單層覆蓋粗糙集應(yīng)用于集值信息系統(tǒng)中，并在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，證明了該模型在近似質(zhì)量和計(jì)算效率方面均優(yōu)于容差關(guān)系、非對(duì)稱相似關(guān)系、限制性容差關(guān)系以及最大相容類，但是該模型無(wú)法應(yīng)用于動(dòng)態(tài)集值信息系統(tǒng)。

隨著時(shí)間的推移，信息系統(tǒng)也會(huì)持續(xù)不斷地發(fā)生變化。求解近似集的效率將直接影響規(guī)則提取和屬性約簡(jiǎn)的效率。當(dāng)信息系統(tǒng)發(fā)生改變時(shí)，快速獲取更新系統(tǒng)中的近似集成為亟待解決的難題。

增量學(xué)習(xí)是指充分利用已知的信息并且避免從頭開始計(jì)算，從而達(dá)到提升計(jì)算效率的目的。將增量學(xué)習(xí)靈活運(yùn)用于動(dòng)態(tài)信息系統(tǒng)中近似集的求解可以顯著提升其計(jì)算效率。信息系統(tǒng)結(jié)構(gòu)的動(dòng)態(tài)變化方式有屬性集的變化［13-15］、屬性值的變化［16-17］以及對(duì)象集的變化。關(guān)于對(duì)象集發(fā)生變化的情況，文獻(xiàn)［18］基于模糊優(yōu)勢(shì)鄰域粗糙集提出動(dòng)態(tài)區(qū)間值有序數(shù)據(jù)的增量特征選擇方法。根據(jù)云平臺(tái)下的并行模型MapReduce，文獻(xiàn)［19］提出經(jīng)典粗糙集的并行增量算法，用于更新大規(guī)模數(shù)據(jù)的近似集。當(dāng)對(duì)象批量發(fā)生變化時(shí)，文獻(xiàn)［20］提出一種鄰域決策粗糙集模型的增量式更新算法。針對(duì)混合型信息系統(tǒng)，文獻(xiàn)［21］提出基于鄰域決策粗糙集矩陣方法的增量式更新算法。文獻(xiàn)［22］提出鄰域多粒度粗糙集模型的矩陣化方法并設(shè)計(jì)了相應(yīng)的增量更新方法，用于更新正域、負(fù)域及其邊界域。文獻(xiàn)［23］研究了優(yōu)勢(shì)粗糙集模型中動(dòng)態(tài)有序數(shù)據(jù)的增量屬性約簡(jiǎn)方法。

本文提出擬單層覆蓋粗糙集中近似集的增量更新算法。當(dāng)一個(gè)對(duì)象集添加至原始系統(tǒng)時(shí)或一個(gè)對(duì)象集從原始系統(tǒng)移除時(shí)，通過(guò)分析擬單層覆蓋集中信息單元的變化情況，根據(jù)信息單元的變化對(duì)各近似集可靠單元和爭(zhēng)議單元的相關(guān)可靠單元集的影響，設(shè)計(jì)相應(yīng)的更新算法。在此基礎(chǔ)上，通過(guò)計(jì)算更新系統(tǒng)中各近似集的最終結(jié)果，從而提高近似集的計(jì)算效率。

1 基本概念

集值信息系統(tǒng)S=(U，A，V，f)是一個(gè)四元組。其中：U是一個(gè)非空有限的對(duì)象集，稱為論域；A是有限的屬性集；V為屬性的值域且是從U×A到V的集值映射。

定義1令S=(U，A，V，f)為集值信息系統(tǒng)，其中A=(a1，a2，…，an)。對(duì)象x∈U的信息解釋是一個(gè)集值向量。表達(dá)式=，其中f(x，ai)是集合。

定義2令S=(U，A，V，f)為集值信息系統(tǒng)。是S上的一個(gè)信息單元，且x∈Cellx，。如果中的任意值均為單值，則該信息單元被稱為可靠單元。如果中存在集值，則該信息單元被稱為爭(zhēng)議單元。Cellc的相關(guān)可靠單元集記為RS(Cellc)，其中RS(Cellc)=(Cellr∈RC|?ai∈A，x∈Cellx，y∈Celly，f(x，ai)?f(y，ai))。

可靠單元和爭(zhēng)議單元分別記為Cellr和Cellc，并且所有可靠元和爭(zhēng)議元的集合分別記為RC 和CC。

定理1令S=(U，A，V，f)為集值信息系統(tǒng)。RC和CC 分別包含S中所有的可靠單元和爭(zhēng)議單元。對(duì)應(yīng)任意X?U，S上X的DA0 和DE0 近似集如下：

2 近似集的增量更新

當(dāng)論域發(fā)生變化時(shí)，擬單層覆蓋粗糙集中的近似集也會(huì)發(fā)生變化。傳統(tǒng)的靜態(tài)方法將從頭開始計(jì)算近似集，會(huì)浪費(fèi)大量的時(shí)間。本文提出當(dāng)對(duì)象集變化時(shí)擬單層覆蓋粗糙集的增量更新方法，充分利用已知的計(jì)算結(jié)果，達(dá)到提高計(jì)算效率的目的。

2.1 對(duì)象增加時(shí)近似集動(dòng)態(tài)更新

2.2 對(duì)象移除時(shí)近似集動(dòng)態(tài)更新

3 本文算法

本文設(shè)計(jì)增量更新算法，算法1 為靜態(tài)算法，算法2 和算法3 分別為對(duì)象集增加時(shí)和減少時(shí)的增量更新算法。

3.1 靜態(tài)算法

在定義2 和定理1 的理論基礎(chǔ)上，本文設(shè)計(jì)相應(yīng)的靜態(tài)算法。

3.2 對(duì)象集添加時(shí)近似集的增量更新算法

當(dāng)原始系統(tǒng)中添加一個(gè)對(duì)象集時(shí)，根據(jù)2.1 節(jié)提出的方法設(shè)計(jì)相應(yīng)的增量更新算法。

3.3 對(duì)象集移除時(shí)近似集的增量更新算法

當(dāng)原始系統(tǒng)中移除一個(gè)對(duì)象集時(shí)，根據(jù)2.2 節(jié)提出的方法設(shè)計(jì)相應(yīng)的增量更新算法。

本文通過(guò)對(duì)比靜態(tài)算法和兩個(gè)增量算法的時(shí)間復(fù)雜度可知，無(wú)論對(duì)象集被添加還是被移除，增量算法的時(shí)間復(fù)雜度總低于靜態(tài)算法的時(shí)間復(fù)雜度。

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

本文通過(guò)在真實(shí)數(shù)據(jù)集上的一系列實(shí)驗(yàn)驗(yàn)證增量算法的有效性。在計(jì)算結(jié)果保持一致的前提下，本文計(jì)算擬單層覆蓋粗糙集中近似集所消耗的時(shí)間，對(duì)比靜態(tài)算法和增量算法的效率。

本文實(shí)驗(yàn)分為對(duì)象添加和對(duì)象移除兩種情況。這兩種情況下的對(duì)比實(shí)驗(yàn)均在UCI 數(shù)據(jù)集上進(jìn)行。數(shù)據(jù)集的具體描述如表1 所示。

表1 數(shù)據(jù)集描述Table 1 Data sets description

本文對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理形成對(duì)應(yīng)的集值信息系統(tǒng)，分別計(jì)算每個(gè)屬性的最小值、最大值、平均數(shù)和中位數(shù)，將其從小到大排列產(chǎn)生3 個(gè)間隔。如果該列的某個(gè)屬性值位于第1 個(gè)間隔，則該屬性值對(duì)應(yīng)于單值記錄。如果其位于第3 個(gè)間隔，則該屬性值對(duì)應(yīng)于與前者不同的單值記錄，否則該值對(duì)應(yīng)于前兩者組成的集值記錄。

實(shí)驗(yàn)環(huán)境的操作系統(tǒng)為Windows 10，CPU 為Intel?CoreTMi7-9750H，內(nèi)存為16 GB。本文使用Java 編程語(yǔ)言在IDEA 平臺(tái)上實(shí)現(xiàn)靜態(tài)和增量算法，其中Java 虛擬機(jī)版本為JVM 1.8。

當(dāng)對(duì)象集發(fā)生變化時(shí)，本文在保持原始數(shù)據(jù)集包含對(duì)象數(shù)不變的前提下，依次增加發(fā)生變化（被添加到原始系統(tǒng)或從原始系統(tǒng)中移除）的對(duì)象數(shù)，對(duì)比靜態(tài)算法和增量算法的計(jì)算時(shí)間，以驗(yàn)證增量理論和對(duì)應(yīng)算法的有效性。

對(duì)于一個(gè)對(duì)象集被添加至原始集值信息系統(tǒng)的情況，本文對(duì)數(shù)據(jù)集進(jìn)行如下處理：1）取出前50%的對(duì)象作為原始數(shù)據(jù)；2）將后50%的對(duì)象平均劃分為10 份；3）依次將10%，20%，…，100%添加至原始數(shù)據(jù)。針對(duì)算法1 和算法2，本文使用以上產(chǎn)生的10 組添加對(duì)象數(shù)不同的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。在不同的數(shù)據(jù)集上，當(dāng)對(duì)象增加時(shí)算法1 和算法2 計(jì)算時(shí)間的對(duì)比如圖1 所示。

圖1 當(dāng)對(duì)象增加時(shí)算法1 和算法2 的計(jì)算時(shí)間對(duì)比Fig.1 Computation time comparison of algorithm 1 and algorithm 2 when objects are added

從圖1 可以看出，隨著添加至原始數(shù)據(jù)集中對(duì)象數(shù)目的增加，算法1 和算法2 的計(jì)算時(shí)間都呈增加趨勢(shì)，但算法1 對(duì)應(yīng)曲線的斜率更大，并且計(jì)算時(shí)間比算法2 多。因此，算法1 的效率低于算法2。當(dāng)數(shù)據(jù)集中包含對(duì)象增加時(shí)，信息單元（可靠單元和爭(zhēng)議單元）的數(shù)目也會(huì)隨之增加。根據(jù)算法1 和算法2 的時(shí)間復(fù)雜度可知，2 個(gè)算法隨著對(duì)象集的增加所需的計(jì)算時(shí)間也會(huì)增加，即圖1 的結(jié)果也與時(shí)間復(fù)雜度的分析保持一致。

當(dāng)對(duì)象添加率為10%、50%和100%時(shí)，靜態(tài)算法1和增量算法2 計(jì)算近似集所需運(yùn)行時(shí)間的比值如表2 所示。從表2 可以看出，隨著對(duì)象添加率的增加，算法1 和算法運(yùn)行時(shí)間的比值越來(lái)越小。在Sensorless 數(shù)據(jù)集上，當(dāng)對(duì)象添加率達(dá)到100%時(shí)，算法1 的執(zhí)行時(shí)間為4.155 s，而算法2 僅需0.224 s，前者仍是后者的18 倍。

表2 算法1 與算法2 運(yùn)行時(shí)間的比值Table 2 Running time ratio of algorithm 1 and algorithm 2

對(duì)于一個(gè)對(duì)象集從原始集值信息系統(tǒng)中移除的情況，本文對(duì)數(shù)據(jù)集進(jìn)行如下處理：1）將完整的數(shù)據(jù)集作為原始數(shù)據(jù)；2）將后50%的對(duì)象平均劃分為10 份；3）依次將10%，20%，…，100%從原始數(shù)據(jù)中移除。針對(duì)算法1 和算法3，本文使用以上產(chǎn)生的10 組移除對(duì)象數(shù)中不同的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。在不同的數(shù)據(jù)集上，當(dāng)對(duì)象移除率增加時(shí)算法1 和算法3 的計(jì)算時(shí)間對(duì)比如圖2 所示。從圖2 可以看出，隨著移除對(duì)象的增加，算法1 呈下降趨勢(shì)，而算法3 呈上升趨勢(shì)，但是算法3 的曲線總在算法1 對(duì)應(yīng)曲線的下方。因此，當(dāng)論域中部分對(duì)象集移除時(shí)算法3 的效率更高。

圖2 當(dāng)對(duì)象移除時(shí)算法1 和算法3 的計(jì)算時(shí)間對(duì)比Fig.2 Computation time comparison of algorithm 1 and algorithm 3 when objects are removed

當(dāng)對(duì)象移除率為10%、50%和100%時(shí)，靜態(tài)算法1和增量算法3 計(jì)算所需運(yùn)行時(shí)間的比值如表3 所示。

表3 算法1與算法3運(yùn)行時(shí)間的比值Table 3 Running time ratio of algorithm 1 and algorithm 3

從表3可以看出，當(dāng)對(duì)象移除率增加時(shí)，靜態(tài)算法1和增量算法3 計(jì)算所需運(yùn)行時(shí)間的比值越來(lái)越小。在Sensorless 數(shù)據(jù)集上，當(dāng)對(duì)象移除率達(dá)到100%時(shí)，算法1 的執(zhí)行時(shí)間為2.489 s，而算法3 僅需0.221 s，前者是后者的11.26 倍。

表4 在不同對(duì)象移除率下的結(jié)果Table 4 Result of under different object removal ratio

表4 在不同對(duì)象移除率下的結(jié)果Table 4 Result of under different object removal ratio

5 結(jié)束語(yǔ)

因集值信息系統(tǒng)中的對(duì)象集隨時(shí)間的推移而增加或移除，導(dǎo)致擬單層覆蓋粗糙集中的近似集發(fā)生變化。本文結(jié)合增量學(xué)習(xí)與擬單層覆蓋粗糙集，提出近似集的增量更新算法。通過(guò)設(shè)計(jì)信息單元、可靠單元和爭(zhēng)議單元的更新方法，以達(dá)到提高計(jì)算效率的目的。構(gòu)建與更新算法相對(duì)應(yīng)的增量算法，并分析其時(shí)間復(fù)雜度。在UCI 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，當(dāng)對(duì)象集發(fā)生變化時(shí)，本文算法相較于靜態(tài)算法的近似集計(jì)算效率高。下一步將擬單層覆蓋粗糙集增量更新算法與大數(shù)據(jù)框架相結(jié)合，并對(duì)本文增量更新算法的并行化問(wèn)題進(jìn)行研究，使其能夠?qū)崟r(shí)處理海量數(shù)據(jù)。