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

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

（1.太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600；2.山西省林業(yè)科學(xué)研究院，山西太原 030000）

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

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

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

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

1.1 傳統(tǒng)貪婪子模覆蓋算法

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

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

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

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

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

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

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

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

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

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

Step2：ESC 流算法-響應(yīng)查詢

已知值，執(zhí)行以下步驟：

1：在S0,…,St上進(jìn)行二分查找；

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

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

2 改進(jìn)的流式子模覆蓋算法

2.1 算法流程

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

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

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

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

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

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

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

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

step1：SRSC 算法-選擇代表集

2.2 算法性能分析

2.2.1 下界

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

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

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

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

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

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

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

由于ALG將I(π)的s*大小近似小于的一個(gè)因數(shù)，概率至少為2/3，因此PRTCL 輸出MPJT,p+1概率至少為2/3?；叵胗螒騇PJT,p+1是在p+1 個(gè)玩家中進(jìn)行的，從定義2 中可以知道，M必須至少為

2.2.2 魯棒性

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

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

根據(jù)貪婪算法可以得到：

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

再將式（7）帶入得到：

最終得到：

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

表1 流式子模覆蓋算法邊界總結(jié)

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

3.1 實(shí)驗(yàn)概述

在很多應(yīng)用中，例如社交網(wǎng)絡(luò)中的影響最大化，圖形中的社區(qū)檢測等，重點(diǎn)的是從龐大的圖形中選擇小部分頂點(diǎn)，這些頂點(diǎn)在某種意義上“覆蓋”了一個(gè)圖的很大一部分。

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

3.2 支配集問題

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

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

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

3.3 頂點(diǎn)覆蓋問題

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

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

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

圖2 不同算法下頂點(diǎn)覆蓋情況

3.4 魯棒性測試

文中算法不僅可以動(dòng)態(tài)提取代表性的集合，也可以預(yù)先知道哪些元素將被刪除，保證代表集合的穩(wěn)定性，文中將選取上述數(shù)據(jù)集“ego-Twitter”，在支配集的問題中比較，刪除不同k值時(shí)對集合覆蓋的影響。

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

圖3 刪除給定數(shù)據(jù)情況下兩種算法支配集問題的表現(xiàn)

4 結(jié)論

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