優(yōu)先級k-中心問題的FPT近似算法

馮啟龍，龍睿，吳小良，仲文明

(1. 中南大學 計算機學院，湖南 長沙，410083；2. 湘江實驗室，湖南 長沙，410205；3. 中南大學 外國語學院，湖南 長沙，410083)

當今社會已進入信息化時代。研究人員通過數(shù)據(jù)挖掘技術從海量數(shù)據(jù)中獲取信息資源，其中，聚類算法是數(shù)據(jù)挖掘的主要技術之一，其作用是將海量數(shù)據(jù)集劃分為多個類簇，使同一類簇中數(shù)據(jù)點相似性盡可能大，不在同一類簇中的數(shù)據(jù)點差異性盡可能大[1]，即相似數(shù)據(jù)盡量聚集，差異數(shù)據(jù)盡量分離。聚類算法在生物學[2]、文本分類[3]、商業(yè)分析[4]、設施選址[5]和隱私保護[6]等方面都有著廣泛應用。常見的聚類問題包括k-平均問題[7]、k-中心問題[8-9]、k-中值問題[10]、k-設施選址問題[11-13]、容錯設施選址問題[14-16]、帶容量的設施選址問題[17-19]、不帶容量的設施選址問題[20-22]和優(yōu)先級k-中心問題[23-30]等。本文對優(yōu)先級k-中心問題進行研究，該問題是k-中心問題的一種變形問題。給定度量空間中1 個大小為n的集合X和1 個正整數(shù)k∈N+。k-中心問題目標是求解1 個大小為k的子集S?X，使得集合X中所有的點到其最近中心點的最大距離最小。假設集合X是由n個城市組成的集合，在實際生活中，人們希望所在城市離服務中心越近越好，以此來降低日常的生活開銷。PLESNIK 等[23]通過賦予集合X中的每個點權重，提出了帶權重的k-中心問題。GORTZ等[24]將帶權重的k-中心問題命名為優(yōu)先級k-中心問題。優(yōu)先級k-中心問題是NP難問題[23]，不存在多項式時間求解的算法，因此，研究人員大多考慮使用近似算法求解優(yōu)先級k-中心問題。雖然近似算法得到的可行解不是最優(yōu)的，其與最優(yōu)解之間存在一定誤差，但可以保證誤差在一定范圍內(nèi)。近似比是衡量近似解和最優(yōu)解之間差距的指標，其值越小表示算法求出的近似解與最優(yōu)解越接近，算法效果越好。因此，近似算法的設計目標是給出盡可能小的近似比。目前，對于優(yōu)先級k-中心問題，GORTZ等[24]給出了近似比為2的近似算法，并且2-近似也是該問題的近似下界[9]。固定參數(shù)可解(fixed-parameter tractability, FPT)的近似算法采用參數(shù)計算方法尋求問題的近似解，是實際中處理NP-難問題的一種新的有效手段。因此，本文考慮優(yōu)先級k-中心問題FPT時間內(nèi)的近似算法，給出1個FPT時間內(nèi)的(1+?)-近似算法，其中?(?＞0)是用于控制算法近似比的參數(shù)。本文提出的算法是在時間復雜度和近似比之間尋找折中方案。當?趨近于0時，算法給出的近似解將無限接近于最優(yōu)解。當?越大時，算法時間復雜度越小。在近似比方面，相比于2-近似算法，本文給出的算法近似比更低。

1 問題定義

本節(jié)主要給出相關問題的定義。

定義1(度量空間)：度量空間是1 個有序?qū)?M，d)，其 中M是1 個 點 集，d為1 個 映 射M×M→R+。對于任意a，b，c∈M，映射d滿足以下3個 性 質(zhì)：1) 如 果d(a，b) =0 當 且 僅 當a=b；2)d(a，b) =d(b，a)；3)d(a，b) +d(b，c) ≥d(a，c)。

給定度量空間(M，d)中的1 個集合X，對任意半徑R＞0 和點v∈X，令Ball(v，R) ={x∈X∣d(v，s)≤R}，表示以點v為中心、R為半徑的集合。對任意點v∈X和集合S?X，令d(v，s)表示點v到集合S的距離，其中，d(v，s)=mins∈Sd(v，s)。

定義2(k-中心問題)：給定度量空間(M，d)中的1 個集合X和正整數(shù)k∈N+，目標是求解1 個大小為k的集合S?X，使得集合X中所有的點到其最近中心點的最大距離最小，即最小化目標函數(shù)maxv∈Xd(v，S)。

記(X，d，k)為k-中心問題的1 個實例。給定集合X的1 個子集S，令C(S) =maxv∈Xd(v，S)表示S關于X的代價。

定義3(優(yōu)先級k-中心問題)：給定度量空間(M，d)中的1 個集合X和正整數(shù)k∈N+，其中集合X中的每個點v被賦予1個優(yōu)先級參數(shù)r(v) ∈R+，求解1個大小為k的集合S?X，考慮集合X中任意數(shù)據(jù)點到集合S的距離與r(v)之間比值，找到最大比值，目標是最小化該比值，即使目標函數(shù)maxv∈Xd(v，S)/r(v)最小化。

記(X，d，k，r)為優(yōu)先級k-中心問題的1 個實例。當優(yōu)先級參數(shù)r(v)都相同時，優(yōu)先級k-中心問題變?yōu)閗-中心問題。

定義4(加倍度量維度)：給定度量空間(M，d)中的1 個集合X，若對任意點v∈X和半徑R＞0，以點v為中心、R為半徑的集合Ball(v，R)可以被數(shù)量小于等于D個半徑為r/2 的集合覆蓋，則稱D為集合X的加倍度量維度。

2 研究現(xiàn)狀

k- 中心問題是NP難問題[8]， 目前，HOCHBAUM 等[8]提出了k-中心問題近似比為2 的近似算法，并且所得到的近似比是k-中心問題當前最好的結果。PLESNIK[23]提出了帶權重的k-中心問題，基于k-中心問題中的貪心算法，給出了1個多項式時間內(nèi)的2-近似算法。因為k-中心問題的近似下界是2，所以，帶權重的k-中心問題的近似下界也是2。GORTZ等[24]將帶權重的k-中心問題命名為優(yōu)先級k-中心問題。

此后，研究人員開始對帶其他約束條件的優(yōu)先級k-中心問題或相關的優(yōu)先級問題如帶噪聲的優(yōu)先級k-中心問題[25,29]、優(yōu)先級k-均值問題[26-28]、優(yōu)先級k-中值問題[26-28]和優(yōu)先級k-供應商問題[29-30]等進行了研究，并提出了許多近似算法以解決這些問題。針對帶噪聲的優(yōu)先級k-中心問題，HARRIS等[25,29]基于線性規(guī)劃和最小費用流技術提出了1個多項式時間內(nèi)的9-近似算法。針對優(yōu)先級k-均值問題和優(yōu)先級k-中值問題，NEGAHBANI等[26]基于線性規(guī)劃方法，在放松優(yōu)先級約束條件下，給出了近似比為8的算法。VAKILIAN等[27]考慮了優(yōu)先級k-中值問題，通過將其轉(zhuǎn)換為擬陣中值問題[28]，給出了1個多項式時間內(nèi)的(7.081+?)-近似算法。針對優(yōu)先級k-供應商問題，BAJPAI等[29]給出了1個多項式時間內(nèi)的3-近似算法。LEE等[30]考慮了歐氏空間的優(yōu)先級k-供應商問題，通過將其轉(zhuǎn)換為最小邊覆蓋問題[31]，給出了多項式時間內(nèi)近似比為的近似算法。

算法的時間復雜度與輸入實例大小和參數(shù)相關，目前還沒有解決該問題的固定參數(shù)可解時間內(nèi)的近似算法。目前，大多數(shù)算法在解決優(yōu)先級k-中心問題或相關問題時，都是基于貪心策略來選取中心點。受貪心策略的啟發(fā)，本文提出了新的中心點選取方法，該方法通過選擇一定規(guī)模的候選中心點集，并且保證該候選中心點集中存在非常接近最優(yōu)解的可行解，從而將原先的近似比2改進為(1+?)，其中?是用于控制算法近似比的參數(shù)。相比于先前的算法，本文提出的算法近似比更小，求解的近似解與最優(yōu)解之間的差距更小。當?趨于0 時，該近似比將無限趨近于1，表明該算法給出的近似解無限接近問題實例最優(yōu)解，在實際應用中具有更好的效果。優(yōu)先級k-中心問題及相關問題的研究現(xiàn)狀見表1。

表1 優(yōu)先級k-中心問題及相關問題近似結果Table 1 Approximate results for priority k-center and related problems

3 優(yōu)先級k-中心問題算法

給定優(yōu)先級k-中心問題的1 個實例I=(X，d，k，r)，基于k-中心問題的貪心策略，提出新的中心點選取算法Priority-k-Center。下面證明本文提出的算法近似比為(1+?)，時間復雜度為(k?-1)O(k)·nO(1)，其中，n=|X|。

給定優(yōu)先級k-中心問題的實例I=(X，d，k，r)，算法Priority-k-Center 主要包含2 步：首先，通過調(diào)用算法Selection 得到大小為k·(4/?)D的候選中心點集合T，其中D為集合X的加倍度量維度。然后，對集合T中每個大小為k的子集S，調(diào)用算法Assignment 將集合X中的點分配給子集S，最后輸出代價最小的子集S。算法Priority-k-Center 的具體過程如圖1所示。

圖1 求解優(yōu)先級k-中心問題算法Fig. 1 An algorithm for the priority k-center problem

下面給出本文的主要結果。

定理1：給定優(yōu)先級k-中心問題的1個實例I=(X，d，k，r)和實數(shù)?＞0，算法Priority-k-Center 給出了實例I的(1+?)-近似解，其時間復雜度為(k?-1)O(k)·nO(1)，其中，n=|X|。

3.1 候選中心點集的選取

算法Selection 的主要思路是利用貪心策略選取更多的候選中心點，使得候選中心點中存在一些點接近最優(yōu)中心點。算法Selection 首先調(diào)用k-中心問題的1 個貪心算法，記為k-Center，得到k個中心點。算法k-Center的具體過程如下：給定k-中心問題的1個實例(X，d，k)，k-Center首先在集合X中隨機地選取1 個點作為初始中心點，然后，對于剩余的每個點，計算距最近現(xiàn)有中心的距離，選擇與其最近中心的距離最大的點作為下一個中心，迭代上述過程至k個中心點被選擇為止。

定理2[8]：給定k-中心問題的1個實例(X，d，k)，算法k-Center 是k-中心問題的1 個2-近似算法，其時間復雜度為O(|X|k)。

上述定理說明當選取的中心點數(shù)量為k時，能得到1個2-近似解。因此，若選取更多的中心點，則基于選取中心點得到的聚類代價與最優(yōu)解代價的差值變小?；谏鲜龇治?，算法Selection 的具體過程如下：給定優(yōu)先級k-中心問題的1 個實例I=(X，d，k，r)和實數(shù)?＞0，算法Selection 首先調(diào)用k-Center(X，d，k)得到1 個大小為k的集合U；令T=U，選擇距離集合T最遠的數(shù)據(jù)點并加入集合T中，迭代上述過程至C(T) ＞(?/2)·C(U)，其中，?為近似比控制參數(shù)。算法Selection 的具體過程如圖2所示。

圖2 候選中心點集的選取算法Fig. 2 A selection algorithm for candidate centers

引理1：給定優(yōu)先級k-中心問題的1個實例I=(X，d，k，r)和實數(shù)?＞0，算法Selection返回1個大小為k·(4/?)D的集合T，其中，D為集合X的加倍度量維度。算法Selection的時間復雜度為O(nk·(4/?)D)，其中，n=|X|。

證明：令集合T為算法Selection返回的解。這里首先證明|T|=k·(4/?)D，其中D為集合X的加倍度量維度。令集合U為算法Selection 第二步返回的結果。若集合X中的每個點被分配到集合U中最近的中心點，則集合X被劃分為k個集合，其中每個集合的半徑不超過C(U)?；诩颖抖攘靠臻g的性質(zhì)，對于其中任意的1 個集合，都可以最多被(4/?)D個集合覆蓋，其中，每個集合的半徑不超過(?/4)·C(U)，因此，共存在最多k·(4/?)D個這樣的集合可以覆蓋集合X。當|T|=k·(4/?)D時，算法Selection 停止執(zhí)行，此時，C(T)≤(?/2)·C(U)成立。假設當|T|=k·(4/?)D時，C(T) ＞(?/2)·C(U)，即存在一些點y∈X，使得d(y，T)＞(?/2)·C(U)成立。由于貪心策略每次選取距離集合T最遠的點作為中心點，因此，集合T中任意2 點之間的距離至少為d(y，T)，否則，點y將作為中心點被添加到集合T中。又因為d(y，T)＞(?/2)·C(U)，所以，T∪{y}中任意2 點之間的距離大于(?/2)·C(U)。由上述證明可知，共存在最多k·(4/?)D個半徑不超過(?/4)·C(U)的集合覆蓋集合X。因為|T∪{y}|=k·(4/?)D+1，所以，在同一個集合中，T∪{y}中一定存在2 點（記為t1和t2），基于三角不等式，有

這與T∪{y}中任意2 點之間的距離大于(?/2)·C(U)矛盾。因此，當算法Selection 停止執(zhí)行時，|T|=k·(4/?)D。

由定理2可知，算法Selection第二步時間復雜度為O(nk)。算法Selection 最多執(zhí)行k·(4/?)D次循環(huán)，其中，每次花費O(n)時間遍歷集合X去選擇距離集合T最遠的點，因此，算法Selection的時間復雜度為O(nk·(4/?)D)。

給定優(yōu)先級k-中心問題的1 個實例I=(X，d，k，r) 和實數(shù)?＞0，令集合T為調(diào)用算法Selection 返回的解。下面證明集合T中存在1 個大小為k的子集S，其中S產(chǎn)生的代價接近實例I最優(yōu)解產(chǎn)生的代價。

引理2：令集合T為算法Selection 返回的解，則一定存在1 個大小為k的子集S?T，使得，其中，為實例I的最優(yōu)解代價。

證明：令為優(yōu)先級k-中心問題實例最優(yōu)解，R*為k-中心問題實例最優(yōu)解。因為優(yōu)先級k-中心問題實例(X，d，k，r)的解也是k-中心問題實例(X，d，k)的解，所以，。令表示Ip的最優(yōu)解，對任意i∈{1，2，…，k}，令表示集合T中距離點最近的點。對任意v∈X，不失一般性，假設點v屬于點所在的最優(yōu)簇。根據(jù)三角不等式，有

因此，一定存在1 個大小為k的子集，使得。

3.2 分配算法

給定優(yōu)先級k-中心問題的1 個實例I=(X，d，k，r) 和實數(shù)?＞0，令集合T為調(diào)用算法Selection 返回的解。對于集合T中任意1 個大小為k的子集，算法Assignment 將集合X中的點分配給該子集，并輸出得到的聚類代價。實際上，算法Priority-k-Center 最后輸出代價最小的子集S。算法Assignment 中的參數(shù)R*p是優(yōu)先級k-中心問題實例的最優(yōu)解。對于優(yōu)先級k-中心問題的1 個實例I=(X，d，k，r)，I的最優(yōu)解值是集合X中某2 點間的距離，所以，通過枚舉集合X中2點間的所有距離可以得到實例I的最優(yōu)解值。算法Assignment的具體過程如圖3所示。

圖3 分配算法Fig. 3 An assignment algorithm

圖4 2個數(shù)據(jù)點集合相交情況示例Fig. 4 An example for two intersecting doint sets

因為優(yōu)先級k-中心問題是優(yōu)化點到中心點距離與其優(yōu)先級之間的比值，所以，對?v∈H，無論將點v分配給si或者sj，都不會影響集合X中點到集合S的最大距離與其優(yōu)先級的比值最小的目標。根據(jù)就近原則，若將集合X中點分配到集合S中距離其最近的中心點，則這種分配方式產(chǎn)生的代價最多為。

綜上所述，若集合S?T是實例I的1個?-近似解，則算法Assignment 按照最近分配原則產(chǎn)生的代價不超過。

因為將數(shù)據(jù)點分配給集合S花費的時間為O(nk)，所以，算法Assignment 的時間復雜度為O(nk)。

3.3 時間復雜度分析

由引理1可知，選取候選中心點集T的時間復雜度為O(nk·(4/?)D)?？紤]集合T中所有大小為k的子集，當加倍維度D為常數(shù)時，枚舉的次數(shù)為|T|k=kk·(4/?)kD=(k?-1)O(k)。

對于集合T中每個大小為k的子集S，由引理3可知，算法Assignment 的時間復雜度為O(nk)。因此，算法Priority-k-Center 總的時間復雜度為(k?-1)O(k)·nO(1)。

綜上所述，定理1成立。

4 結論

1) 對優(yōu)先級k-中心問題基于貪心策略，提出了新的中心點選取方法，利用加倍度量維度的性質(zhì)去限制中心點集合的大小，并給出了相應證明，實現(xiàn)了1個FPT時間內(nèi)的(1+?)-近似算法，降低了目前求解該問題的近似比。

2) 帶噪聲的優(yōu)先級k-中心問題仍然沒有給出FPT時間內(nèi)的近似算法，能否應用本文提出的算法解決該問題仍有待進一步研究。