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

(1. 中南大學(xué) 計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙，410083；2. 湘江實(shí)驗(yàn)室，湖南 長(zhǎng)沙，410205；3. 中南大學(xué) 外國(guó)語(yǔ)學(xué)院，湖南 長(zhǎng)沙，410083)

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

1 問(wèn)題定義

本節(jié)主要給出相關(guān)問(wèn)題的定義。

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

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

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

記(X，d，k)為k-中心問(wèn)題的1 個(gè)實(shí)例。給定集合X的1 個(gè)子集S，令C(S) =maxv∈Xd(v，S)表示S關(guān)于X的代價(jià)。

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

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

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

2 研究現(xiàn)狀

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

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

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

表1 優(yōu)先級(jí)k-中心問(wèn)題及相關(guān)問(wèn)題近似結(jié)果Table 1 Approximate results for priority k-center and related problems

3 優(yōu)先級(jí)k-中心問(wèn)題算法

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

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

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

下面給出本文的主要結(jié)果。

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

3.1 候選中心點(diǎn)集的選取

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

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

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

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

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

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

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

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

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

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

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

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

3.2 分配算法

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

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

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

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

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

因?yàn)閷?shù)據(jù)點(diǎn)分配給集合S花費(fèi)的時(shí)間為O(nk)，所以，算法Assignment 的時(shí)間復(fù)雜度為O(nk)。

3.3 時(shí)間復(fù)雜度分析

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

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

綜上所述，定理1成立。

4 結(jié)論

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

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