王 怡，常 青，王耀力，郝慧琴

（1.太原理工大學(xué)信息與計算機學(xué)院，山西 晉中 030600；2.中國電信股份有限公司山西分公司，山西太原 030000）

當(dāng)前，數(shù)據(jù)摘要逐漸成為機器學(xué)習(xí)的研究熱點。然而數(shù)據(jù)摘要算法被證明在性別、種族和民族等敏感屬性方面存在偏見[1-2]，尤其在教育、招聘、銀行和司法系統(tǒng)等領(lǐng)域中[3-5]，所引起的公平性問題[6]得到了廣泛的關(guān)注。

對于上述問題，該文引入流式子模最大化算法[7]，在此基礎(chǔ)上改進算法約束，考慮數(shù)據(jù)項的組成性，在每組中選取指定范圍內(nèi)的元素構(gòu)成具有代表性的子集，從而使提取出的子集更具有公平性和多樣性。

1 基于公平約束的流式子模算法

1.1 擬陣約束下的流式子模最大化模型

在很多情況下，考慮算法的穩(wěn)定性以及成本等問題，通常采用擬陣約束下的流式子模優(yōu)化模型[8-10]。

定義1：假設(shè)V表示原有數(shù)據(jù)集中n個元素的集合，V1…Vm是V的一個分劃，即是m個非負(fù)整數(shù)，k為基數(shù)約束，S為最優(yōu)子集。記:

則(V,L)是定義在V上的擬陣，稱為分劃擬陣。在分劃擬陣約束下的流式子模最大化模型可表示為：

1.2 改進后的約束——公平約束

鑒于上述擬陣約束得到的集合S，當(dāng)原始數(shù)據(jù)集合V中含有某些如年齡、性別、種族等特定屬性時，會造成對某些特定屬性數(shù)據(jù)的代表性不足或者過強，無法保證集合S的公平性與多樣性。為了使選取出的集合S能夠公平代表原始數(shù)據(jù)集合V，對上述擬陣約束進行改進，提出了一種公平約束。

該文借鑒文獻[11-14]有關(guān)公平的思想，要求獲得的解集S與數(shù)據(jù)某些特定屬性(如種族、性別)相平衡，提出流式子模最大化下的公平約束，定義如下：

假定給定的數(shù)據(jù)集V是有顏色的，即給每個元素賦予一種顏色。對于顏色c=1,2,…,C，用Vc表示顏色c的元素集合，則b=1,2,…,C。對于每種顏色c，提取后的解集S必須包含每個顏色c的元素個數(shù)在指定的下界lc和上界uc之間。設(shè)k?Z是一個全局基數(shù)約束，該公平約束表示為：

則基于該公平約束下的流式子模最大化模型為:

由公平約束的定義可知，S滿足以下條件：

該文將滿足上述條件的S表示為“可擴展”的。

2 公平約束下的流式子模算法

2.1 公平約束下的流式子模最大化算法

文獻[8]提出的擬陣約束子模優(yōu)化算法A(MSM算法)是目前性能最好的擬陣子模優(yōu)化算法，但該算法未考慮公平問題。因此該文基于MSM 算法進行改進，提出公平約束下的流式子模算法(FSM 算法)，步驟如下：

1）FSM 算法通過運行A來構(gòu)造一個近似最大化f的解集SA。SA必定滿足上界，同時，對于每種顏色c，并行收集一個大小為|Bc|=lc的備份集Bc。

2）若SA不滿足其下界，則將SA擴展為一個可行的解決方案S，即對于每一種顏色c，如果|SA∩Vc|＜lc，則從Bc中添加lc-|SA∩Vc|個元素來滿足下界。

FSM 算法偽代碼如下：

2.2 算法可行性分析

當(dāng)去掉公平約束F中的下界約束|S∩Vc|≥lc時，剩下的約束將會與式（1）相同，得到一個擬陣。然而在該擬陣約束下的流式子模最大化算法A得到的解可能會違反下界約束。為了兼顧下界約束，該文算法通過從A并行流中收集備份元素來擴大解決方案，使之成為一個可行的解決方案。

然而，僅僅擴大解決方案來滿足下界約束，可能會違反全局基數(shù)約束|S|≤k。正確的約束是解決方案具有式（5）的條件：“可擴展”到一個可行集。為了說明該文所提出的算法能有效地找到可行解，需要證明符合公平約束的V的可擴展子集的集合F仍然能構(gòu)成一個擬陣。下面給出公平約束符合擬陣約束性質(zhì)的證明。

定義2：若～2V是V的所有可擴展子集的集族，那么是一個擬陣。

證明如下：若是擬陣，必然滿足以下公理：設(shè)B包含擬陣中的所有極大集。則B滿足以下兩個公理：

①B。

②如果B1,B2∈B和x∈B1B2，則存在y∈B2B1，使得B1-x+y∈B（向下封閉性）。

這些公理表明向下封閉性的B（集合的所有子集）是一個擬陣。但是，B的向下封閉性等于，因為V的任何子集只要能推廣到一個可行解，也能推廣到一個極大可行解。因此，只需要證明公理①和公理②。

公理①的證明只需假設(shè)≠?，即可得到B≠?。

對于公理②：已知B1,B2∈B,x∈B1B2,設(shè)c是x的顏色，一種簡單的情況是當(dāng)B2B1包含某個元素y∈Vc，那么B1-x+y中每種顏色的元素數(shù)與B1相同，因此B1-x+y也在B中。

現(xiàn)在假設(shè)另一種情況，即Vc∩B2?B1-x。那么有：

3 仿真實驗與分析

3.1 實驗概述

該文討論的是公平約束下的數(shù)據(jù)摘要問題，為此通過以下指標(biāo)來進行對比實驗：

1）使用函數(shù)效用值和時間復(fù)雜度（運行時間）來衡量算法的性能。

2）將違反公平的次數(shù)error(S)=定義為衡量公平的標(biāo)準(zhǔn)，總和項的每一項是依靠違反上界和下界元素的個數(shù)來量化的。

3）查看不同算法每個分組的選取元素的個數(shù)來衡量提取數(shù)據(jù)的多樣性。

實驗所采用的效用函數(shù)為f(S)=M-d(v,e) 。其中，為數(shù)據(jù)集中的所有數(shù)據(jù)之和，其個數(shù)為n。

此外，平均每個分組提取到的元素為k/t，其中t表示分組的個數(shù)，根據(jù)該實驗數(shù)據(jù)集的分組個數(shù)，設(shè)置上界uc=0.2k與下界lc=0.1k，以確保每個分組包含子集的10%～20%。

在很多應(yīng)用中，比如電影推薦[15-16]、圖形檢測[17]等，感興趣的是從龐大的數(shù)據(jù)集中提取出的部分集合與原始數(shù)據(jù)集相似，涵蓋想要的所有的屬性。

為了評估該文算法FSM 的可使用性，選用了兩種不同的數(shù)據(jù)集，第一種數(shù)據(jù)集為公共數(shù)據(jù)集Cencus1990，其中含有一些可能導(dǎo)致算法偏見的屬性（如年齡、身高、體重、性別、種族等），該實驗選用該數(shù)據(jù)中的50 060 條記錄，希望從該數(shù)據(jù)集中提取到能夠涵蓋原始數(shù)據(jù)集的所有年齡段的子集。該實驗根據(jù)年齡將數(shù)據(jù)分為六組：[0,29]、[30,39]、[40,49]、[50,59]、[60,69]、[70+]，各個年齡段的記錄數(shù)分別如下：1 379、18 093、15 354、8 210、6 521、503。

第二種數(shù)據(jù)集是從呂梁山山脈觀測得到的森林覆蓋類型數(shù)據(jù)，該數(shù)據(jù)集共包含8 種可燃物林木類型：華北落葉松（1）、云杉（2）、白樺（3）、山楊（4）、遼東櫟（5）、青木千（6）、側(cè)柏（7）、醋柳（8），包含每種可燃物類型對應(yīng)的海拔高度、土壤類型、坡度、坡向等12 種屬性。每種可燃物類型分別有87 145、60 450、58 762、45 040、42 098、20 625、534、456 條數(shù)據(jù)。由統(tǒng)計數(shù)據(jù)可得側(cè)柏（7）與醋柳（8）兩種可燃物類型的數(shù)據(jù)量較少，傳統(tǒng)算法在訓(xùn)練時容易忽略小樣本數(shù)據(jù)。

將該文的FSM 算法與隨機提取算法和MSM 算法進行比較。

3.2 不同算法下?lián)p失成本及運行時間對比

該文針對流式子模最大化算法進行改進，為驗證該算法的有效性，對比上述幾種算法的函數(shù)效用值以及運行時間。

如圖1 所示，該文FSM 算法的函數(shù)效用值略低于MSM 算法，但優(yōu)于隨機提取算法。這是由于復(fù)雜約束的引入會不可避免導(dǎo)致算法效用降低。從實驗來看，F(xiàn)SM 算法與MSM 算法相比效用值近似，甚至在提取的個數(shù)越大時，F(xiàn)SM 效用值與MSM 算法一致。

圖1 不同算法下的函數(shù)效用值

流式子模最大化算法的運行時間是通過子模函數(shù)調(diào)用的次數(shù)來衡量的[7]，與隨機提取算法運行時間定義不一致，因此隨機提取算法未涉及運行時間的對比。

如圖2 所示，該文提出的FSM 算法的運行時間明顯低于其他算法。且隨著k的增大，F(xiàn)SM 算法對比MSM 算法運行效率有顯著提升。在“森林”數(shù)據(jù)集下，當(dāng)k為70 時，F(xiàn)SM 的算法比MSM 算法運行時間降低了8.6%。說明FSM 算法能大大減少時間復(fù)雜度，尤其在應(yīng)用大型數(shù)據(jù)摘要問題中，F(xiàn)SM 算法更具有優(yōu)越性。

圖2 不同算法下的運行時間

3.3 不同算法下違反公平的次數(shù)對比

該文通過設(shè)置上界uc和下界lc來保證算法提取出的子集包含想要的數(shù)據(jù)屬性值的所有范圍，以此顯示該文算法的公平性。因此將違反上界和下界元素的個數(shù)定義為違反公平的次數(shù)error 。通過對比不同算法違反公平的次數(shù)error 來驗證該文算法的公平性。

由圖3 可知，隨著提取元素個數(shù)k的不斷增大，MSM 算法與隨機提取算法會出現(xiàn)不同程度的error。如當(dāng)k設(shè)定為70，Cencus1990 數(shù)據(jù)集下隨機提取算法的error 為28，MSM 算法的error 為21。而該文FSM 算法違反公平的次數(shù)始終為0，可有效保證提取的子集不會違反上界和下界，證明了該文算法的公平性。

圖3 不同算法下的違反公平的次數(shù)情況

3.4 不同算法下的各個分組元素提取情況

該文所提算法的目的在于能夠提取各個分組的元素，以使提取出的代表性子集具有多樣性。通過分析查看不同算法下各個分組元素提取情況來證明算法的有效性。

分別選取k=30、k=70 不同情況來查看不同算法下的各個分組元素提取情況，如表1-4 所示。

表1 Cencus1990 k=30 時不同算法下不同年齡段元素提取情況

表2 Cencus1990 k=70 時不同算法下不同年齡段元素提取情況

表3 “森林”k=30 時不同算法下不同林型元素提取情況

該文所提FSM 算法的核心在于對每個屬性分組數(shù)據(jù)的提取添加了上界uc與下界lc約束。如表1-表4 所示，當(dāng)提取數(shù)據(jù)k為30 時，上界值為0.2k=6，下界值為0.1k=3。因此屬性每個分組被提取出的數(shù)據(jù)個數(shù)應(yīng)當(dāng)在3-6 之間。對比在Cencus1990 公共數(shù)據(jù)集和“森林”數(shù)據(jù)集下，隨機提取算法與MSM 算法無法保證提取到所有分組類型的數(shù)據(jù)。在“森林”數(shù)據(jù)集中，當(dāng)提取元素個數(shù)k=70 時，隨機提取算法未提取到林型（8）的數(shù)據(jù)，MSM 算法未能提取到林型（7）和林型（8）的數(shù)據(jù)。可以看出，不論k取何值，F(xiàn)SM 算法提取的子集更具有代表性與多樣性，證明了該文算法有良好的魯棒性。

表4 “森林”k=70 時不同算法下不同林型元素提取情況

4 結(jié)論

該文討論了數(shù)據(jù)摘要的代表性問題，提出了一種公平約束下的流式子模最大化算法，使選出的代表性子集能夠涵蓋提取屬性的所有范圍。實驗表明，在該文模型下采用流式子模優(yōu)化算法，相比其他流式算法，時間復(fù)雜度減少8.6%以上，且提取出的摘要的多樣性與穩(wěn)定性更強，可以適用于更復(fù)雜的場景中。