擬單層覆蓋粗糙集中近似集的增量更新算法

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

（河南理工大學計算機科學與技術學院，河南焦作 454003）

0 概述

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

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

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

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

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

1 基本概念

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

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

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

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

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

2 近似集的增量更新

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

2.1 對象增加時近似集動態(tài)更新

2.2 對象移除時近似集動態(tài)更新

3 本文算法

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

3.1 靜態(tài)算法

在定義2 和定理1 的理論基礎上，本文設計相應的靜態(tài)算法。

3.2 對象集添加時近似集的增量更新算法

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

3.3 對象集移除時近似集的增量更新算法

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

本文通過對比靜態(tài)算法和兩個增量算法的時間復雜度可知，無論對象集被添加還是被移除，增量算法的時間復雜度總低于靜態(tài)算法的時間復雜度。

4 實驗結果與分析

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

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

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

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

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

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

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

圖1 當對象增加時算法1 和算法2 的計算時間對比Fig.1 Computation time comparison of algorithm 1 and algorithm 2 when objects are added

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

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

表2 算法1 與算法2 運行時間的比值Table 2 Running time ratio of algorithm 1 and algorithm 2

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

圖2 當對象移除時算法1 和算法3 的計算時間對比Fig.2 Computation time comparison of algorithm 1 and algorithm 3 when objects are removed

當對象移除率為10%、50%和100%時，靜態(tài)算法1和增量算法3 計算所需運行時間的比值如表3 所示。

表3 算法1與算法3運行時間的比值Table 3 Running time ratio of algorithm 1 and algorithm 3

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

表4 在不同對象移除率下的結果Table 4 Result of under different object removal ratio

表4 在不同對象移除率下的結果Table 4 Result of under different object removal ratio

5 結束語

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