流式魯棒子模覆蓋算法的圖集覆蓋問題的研究

田 歌，王耀力，常 青，孫永明

（1.太原理工大學信息與計算機學院，山西晉中 030600；2.山西省林業科學研究院，山西太原 030000）

數據匯總是機器學習中的一個主要挑戰，它的任務是從大型數據集中找到可管理大小的代表性子集。包括圖像摘要、文檔和語料庫摘要、推薦系統和非參數學習等許多應用程序。獲得數據匯總的一般方法是：首先選擇數據元素的子集，然后對所選集合的“代表性”進行量化，以構成優化效用函數。通常，用于匯總的效用函數表現出子模性，即自然遞減的收益性質[1]。換句話說，子模性意味著隨著摘要中包含更多數據點，數據集中任何元素的增加值都會減少收益。因此，可以將數據匯總問題自然地歸結為子模覆蓋問題[2]。數據匯總通常采用集中式算法，但集中式算法對于大型數據集來說不切實際。因為順序選擇單個機器上的元素在速度和內存方面受到很大的限制。因此，為了大規模地解決上述子模優化問題，需要利用MapReduce式的并行計算模型，或借助于流算法[3]。

而在實際應用當中，應用程序往往受限于數據存儲容量與數據存取速度等因素，流算法往往是其可行的選擇。流算法來源于大數據。自1987 年以來，世界人均存儲信息的能力每40 個月翻一番。算法面臨著存儲、通信、分析等挑戰。流算法僅需存儲少量可用數據，而且內存大小可以遠小于輸入數據的大小。流算法不僅可以避免對內存的大量隨機訪問，而且可根據當前數據及時提供數據預測，從而促進實時數據分析[4]。

但在很多情況下，人們希望提取的代表集合是具有魯棒性的。例如網絡中的結點出現故障或者結點本身的變化，異或是當集合中的某些元素被移除時，希望集合還能保持其穩定性和代表性[5]。綜上所述，文中對現有流式子模覆蓋算法進行改進，同時加入魯棒性判斷，使其選出的代表性集合可以最多抵抗m元素的可能移除。

1 基于流算法的子模覆蓋問題

1.1 傳統貪婪子模覆蓋算法

標準子模覆蓋(SC)問題中，目標就是找到最小的子集S∈V使其滿足特定的效用Q，即：

SC 問題是一個典型NP 問題，一種簡單的貪婪策略是在每個階段選擇被覆蓋元素最多的集合[6]。該算法的偽代碼如下。集合C包含覆蓋集合的指標，集合U存儲X中未覆蓋的元素。最初C為空，U←x，反復選擇覆蓋U元素最多的S集合，將其添加到覆蓋項中。

貪婪集和覆蓋算法的偽代碼如下：

1.2 基于流算法的子模覆蓋算法

引入流算法主要是解決子模覆蓋問題，同時保持較小的內存并且不對數據流進行大量傳遞[7-9]。

2017 年，Baharan 等人提出解決大規模數據問題時可以將數據分發給幾個機器，尋求并行的計算方法，或者使用流算法來擴大子模優化[10]。2009 年，Barna 等人首次將流算法應用到集覆蓋問題的研究中，主要集中在半流模型上，其內存被限制為O(n)[11]。2014 年，Emek 等人證明，如果將流算法限制為僅對數據流執行一次傳遞，最佳的近似保證為[12]。2015 年，Chakrabarti 等人通過放寬單通道約束，設計了一個p-pass 半流(p+1)n1/(p+1)近似算法，并證明其本質上是嚴格的(p+1)3的因子[13]。2016 年，Ashkan等人提出了首個流式子模覆蓋算法ESC-流算法，它僅需按任意順序對數據進行一次傳遞，并提供任何ε>0，就可以得到最佳解決方案的2/ε的近似值，同時達到指定效用的1-ε，該算法僅需要O((klogk)/ε)的內存[14]。

定義1：對于任何數量的p通道和任何m大小的流，p通道流算法至少以的概率將子模數覆蓋問題近似為小于的因子，必須使用大小至少為的內存。

用m表示數據流的大小。當p=1 時，任何近似比大于m/2 的單程流算法都必須至少使用Ω(m)的內存。ESC流算法采用兩個階段，第一個階段允許內存大小的參數M作為輸入。該算法保留t+1=logM/2+1 大小的代表集。每個代表集最大為2j，并且具有對應的閾值。一旦新元素e到達流中，它將被添加到所有未完全填充的代表性集合中，并且這些元素的邊際增益高于相應的閾值，即該算法僅需要對數據流進行一次傳遞。該算法第一階段對于流的每個元素的運行時間都是O(log logM),因為每個元素的計算成本是O(logM)次的oracle 調用[15-16]。

ESC 流式子模覆蓋的偽代碼如下：

step1：ESC 流算法-選擇代表集

Step2：ESC 流算法-響應查詢

已知值，執行以下步驟：

1：在S0,…,St上進行二分查找；

2：返回最小集合Si，使得f(s)≥(1-ε)Q；

3：如果不存在這樣的集合，則返回“違反假設”。

2 改進的流式子模覆蓋算法

2.1 算法流程

鑒于目前提取的代表集合中，當集合元素變化時或者某些元素增加刪除時，無法保證集合的穩定性。為了使選出的代表集合能夠具有抵抗部分元素被移除和替換的性能，對以上流式子模覆蓋算法進行改進。

對于任何集合E?V，其中|E|≤m，存在一個最大為k的子集Z?SE，滿足：

則認為對于參數m，集合S是魯棒的。c是一個近似率。用OPT(k,VE)表示VE大小為k的最佳子集（即在刪除E個元素后）。

基于以上定義，文中改進后的流式魯棒子模覆蓋算法(SRSC)的步驟如下，該算法也需要兩個階段:

階段1：需要輸入一個非遞減的單調子模函數，基數約束為k、魯棒性參數為m、閾值參數為t。對于部分α∈(0,1]，參數t是對于f(OPT(k,VE))的α近似值。因此，它依賴于f(OPT(k,VE))，但是f(OPT(k,VE))是未知的。因此在所提算法中假設f(OPT(k,VE))是已知的。該算法同ESC流算法一樣，只需要對數據流進行一次傳遞，并輸出一組最優元素。

階段2：SRSC 接收在流傳輸階段構造的集合S，去除元素E?S的集合，將基數約束k作為輸入。然后返回最大為k的集合Z，該集合只需要在集合SE上運行上述簡單貪婪算法即可獲得。

文中所提算法為流式魯棒子模覆蓋算法(SRSC)。

流式魯棒子模覆蓋算法的偽代碼如下：

step1：SRSC 算法-選擇代表集

2.2 算法性能分析

2.2.1 下界

首先分析算法的下界，由于流算法可以被概念化為知道輸入流不同段的玩家間的通信問題。因此，必要通信總量的下限產生流算法所需的內存量的下界。通信的下界意味著流的下界。

而合適的通信對復雜問題始于多玩家指針跳躍問題。

定義2：令T為深度l≥1 的完整t進制數（因此k=l+1 ≥2 層），則：

令MPJT,p+1為具有p+1 級別的完整t進制數T上的多玩家指針跳躍問題的實例，而π 為問題的輸入，分布在p+1 個玩家P1,P2,…,Pp+1中。因此在m集合中，文中構造了SRSCt,p+1,l中的一個實例I()π，對于一些整數l≥t，有：

在文中的例子中k=p+1。

p-pass流算法ALG使用M大小的內存將SRSCt,p+1,l近似為小于的因數，其中，流由P1的集合和P2的集合組成，依此類推。文中使用ALG為MPJT,p+1設計一個[p,(p+1)M,1/3]協議PRTCL如下：

在i=1,…p的每個回合中，在ALG中模擬第i次傳遞；當ALG中處理流與P1對應最后一組集合時，將內存的內容廣播到所有玩家。然后，在ALG完成流上的P2，依此類推直至Pp+1之后執行相同的操作。

由于ALG將I(π)的s*大小近似小于的一個因數，概率至少為2/3，因此PRTCL 輸出MPJT,p+1概率至少為2/3。回想游戲MPJT,p+1是在p+1 個玩家中進行的，從定義2 中可以知道，M必須至少為

2.2.2 魯棒性

對于流式魯棒子模覆蓋問題，文中讓OPT(k,VE)代表選出子集的最優：

于SRSC 對數據集執行一次傳遞并且構造一個集合S，其大小最多是O((k+mlogk)logk)個元素。對于這樣一個集合S和任意集合E∈V，滿足 |E|≤m，則：

根據貪婪算法可以得到：

文中先從貪婪算法中得出：

再將式（7）帶入得到：

最終得到：

總結文中結論與過去的流式子模覆蓋問題，給出了這些算法實現的近似因子、傳遞次數和空間界限。流式子模覆蓋算法邊界總結如表1 所示。

表1 流式子模覆蓋算法邊界總結

3 仿真實驗與分析

3.1 實驗概述

在很多應用中，例如社交網絡中的影響最大化，圖形中的社區檢測等，重點的是從龐大的圖形中選擇小部分頂點，這些頂點在某種意義上“覆蓋”了一個圖的很大一部分。

為了評估SRSC 算法的可使用性。文中考慮了兩個基本的集合覆蓋問題：“支配集合”和“頂點覆蓋”問題。并將其應用到網絡圖中3 個不同大小、不同類型的數據集中進行分析和比較。分別是由爬蟲BUbiNG 得到的“eu-2015”，這是在2015 年底拍攝的一個大型的歐盟國家的快照。它由1 070 557 254個節點和91 792 261 600 條邊組成。人類活動生成的有向社交網絡“enwiki-2013”，是2013 年2 月底維基百科英文部分的快照。它由4 206 785個節點和101 355 853 條邊組成。從公共來源抓取的“ego-Twitter”由來自Twitter 的“圈子”(或“列表”)組成。它由81 306 個節點和1 768 149 條邊組成。以上3 種圖都是稀疏的，因此需要較大的覆蓋解決方案。將文中算法與隨機選擇和ESC 流算法進行比較。

3.2 支配集問題

給定具有頂點集V和邊集E的圖G(V,E)：ρ(S)表示圖中S的頂點領域，δ(S)表示圖中的邊連接到S中的一個頂點。支配集即是選擇覆蓋頂點集V（即頂點集）的最小集的問題。其對應的效用函數為：f(s)=|ρ(S)∪S|，為單調子模函數。設置算法中M=520 MB,a=2，Q=0.7|V|。

在支配集問題中，從圖1 中可以得出，文中SRSC算法與ESC 流算法的性能基本保持一致，甚至在數據集越大且頂點選擇覆蓋越多時性能略優于流算法。

圖1 不同算法下支配集問題情況

3.3 頂點覆蓋問題

給定具有頂點集V和邊集E的圖G(V,E)：δ(S)表示圖中的邊連接到S中的一個頂點。頂點覆蓋是選擇覆蓋邊緣集E的最小集合問題。其對應的效用函數為：f(s)=|δ(S)|，為單調子模函數。

設置算法中M=320 MB,a=2,Q=0.8|E|。

在頂點覆蓋問題中，從圖2 中可以得出，文中算法卻略差于ESC 流算法，但比起隨機選擇已經有了相當大的提升。

圖2 不同算法下頂點覆蓋情況

3.4 魯棒性測試

文中算法不僅可以動態提取代表性的集合，也可以預先知道哪些元素將被刪除，保證代表集合的穩定性，文中將選取上述數據集“ego-Twitter”，在支配集的問題中比較，刪除不同k值時對集合覆蓋的影響。

由圖3 可知，在刪除數據k值從100 至500 變化時，文中算法比ESC 流算法受到刪除元素的影響少，其穩定性提高了10%以上。

圖3 刪除給定數據情況下兩種算法支配集問題的表現

4 結論

文中討論了流式子模覆蓋問題的優化，對其集合加入魯棒性判斷，使其算法選出的代表集可以在部分元素被刪除時還能具有其對應的穩定性和代表性。實驗證明，在文中模型下采用流式魯棒子模覆蓋算法，相比其他流式算法，集合穩定性提高了10%以上，可以適用于更復雜的場景。