侯作勛韓培張宏偉安然

（1 北京空間機(jī)電研究所，北京 100190）（2 中國(guó)科學(xué)院空間應(yīng)用工程與技術(shù)中心，北京 100190）

一種硬件友好型自適應(yīng)K-均值學(xué)習(xí)算法

侯作勛1韓培2張宏偉1安然1

（1 北京空間機(jī)電研究所，北京 100190）（2 中國(guó)科學(xué)院空間應(yīng)用工程與技術(shù)中心，北京 100190）

文章提出了一種適合于嵌入式平臺(tái)實(shí)現(xiàn)的自適應(yīng)K-均值學(xué)習(xí)算法，用于解決標(biāo)準(zhǔn)K-均值算法中存在的無(wú)法自主確定類(lèi)屬數(shù)量、難以確定合理的初始化種子集和運(yùn)算時(shí)間過(guò)長(zhǎng)的問(wèn)題。算法通過(guò)引入變異比準(zhǔn)則（VRC）對(duì)聚類(lèi)結(jié)果進(jìn)行定量評(píng)估，并通過(guò)迭代運(yùn)算尋找 VRC最大值的方法有效解決了類(lèi)屬數(shù)量的自主確定問(wèn)題；提出了一種分布式最大-最小初始化種子選擇方法，利用漸進(jìn)尋找類(lèi)內(nèi)距離最大樣本的方法解決了K值遞增時(shí)初始化種子集的確定問(wèn)題；并給出了利用FPGA實(shí)現(xiàn)該算法的有效途徑。仿真實(shí)驗(yàn)結(jié)果表明，該算法針對(duì)各種類(lèi)型的樣本向量均能夠準(zhǔn)確高效的完成聚類(lèi)處理任務(wù)，VRC評(píng)估結(jié)果與理論預(yù)期一致，初始化種子集選擇正確。為進(jìn)一步實(shí)現(xiàn)目標(biāo)分類(lèi)、圖像分割等智能圖像處理任務(wù)奠定了基礎(chǔ)。

自適應(yīng) K-均值 硬件友好 圖像處理 航天遙感

0 引言

無(wú)監(jiān)督學(xué)習(xí)是智能航天遙感的重要手段，是實(shí)現(xiàn)遙感圖像分割、目標(biāo)分類(lèi)等任務(wù)的基礎(chǔ)。無(wú)監(jiān)督學(xué)習(xí)的核心研究?jī)?nèi)容是當(dāng)機(jī)器采集到一匹類(lèi)屬標(biāo)志完全未知的樣本數(shù)據(jù)時(shí)，通過(guò)一定的準(zhǔn)則將它們分為有限的幾類(lèi)并賦予它們類(lèi)屬標(biāo)志。在航天的很多應(yīng)用領(lǐng)域，由于原始樣本較少，缺乏先驗(yàn)信息，機(jī)器必須通過(guò)無(wú)監(jiān)督學(xué)習(xí)獲取智能。例如對(duì)于外星探測(cè)機(jī)器人[1-2]，其主要工作是探測(cè)未知星體的表面形貌和巖土特征等。由于缺乏先驗(yàn)知識(shí)，機(jī)器人只有通過(guò)對(duì)采集的樣本進(jìn)行無(wú)監(jiān)督學(xué)習(xí)，才能不斷積累知識(shí)，并逐步完成更加復(fù)雜的任務(wù)。常見(jiàn)的無(wú)監(jiān)督學(xué)習(xí)算法包括 K-均值聚類(lèi)（K-means）[3]、隨機(jī)搜索聚類(lèi)（CLARANS）[4]、平衡迭代削減聚類(lèi)（BIRCH）[5]、基于密度的聚類(lèi)（DBSCAN）[6]等。其中，K-均值聚類(lèi)學(xué)習(xí)算法的處理效果較好，對(duì)不同類(lèi)型樣本的適應(yīng)性強(qiáng)，已經(jīng)成功應(yīng)用于一些智能圖像處理系統(tǒng)中，并且不斷有學(xué)者對(duì)標(biāo)準(zhǔn) K-均值聚類(lèi)算法進(jìn)行優(yōu)化以期解決更加復(fù)雜的問(wèn)題[7]。然而標(biāo)準(zhǔn) K-均值算法仍存在三個(gè)主要問(wèn)題。第一，現(xiàn)有算法無(wú)法根據(jù)樣本的大小和分布情況自主決策應(yīng)該生成的類(lèi)屬數(shù)量，也就是說(shuō) K值需要人工指定。而且絕大多數(shù)其它聚類(lèi)算法也存在類(lèi)似的問(wèn)題；第二，在標(biāo)準(zhǔn)K-均值算法中，一組初始化種子（簡(jiǎn)稱(chēng)初始化種子集）的選取質(zhì)量（quality，下同）會(huì)影響最終的聚類(lèi)效果；第三，標(biāo)準(zhǔn)K-均值算法的計(jì)算復(fù)雜度同樣本向量的總數(shù)N、聚類(lèi)類(lèi)屬總數(shù)K、樣本向量的維度D以及迭代的次數(shù)t的乘積成正比（即算法的復(fù)雜度為O（NKDt））。一般N遠(yuǎn)大于K、D和t，是影響運(yùn)算速度的主要因素。因此，當(dāng)樣本向量的總數(shù)N很大時(shí)，算法的時(shí)間開(kāi)銷(xiāo)急劇增加，無(wú)法滿(mǎn)足很多應(yīng)用場(chǎng)合對(duì)運(yùn)算速度的要求。上述三項(xiàng)問(wèn)題限制了K-均值聚類(lèi)算法的應(yīng)用。雖然已有一些算法試圖解決其中部分問(wèn)題，但是這些算法的計(jì)算復(fù)雜度普遍較高，難以采用嵌入式平臺(tái)進(jìn)行處理。少數(shù)能夠通過(guò)嵌入式平臺(tái)實(shí)現(xiàn)的處理算法，受限于硬件資源的約束，總體性能依然較差。例如，文獻(xiàn)[8]提出了利用貝葉斯索引準(zhǔn)則（BIC）進(jìn)行K值評(píng)估的算法；文獻(xiàn)[9]通過(guò)集成專(zhuān)用BIC處理器設(shè)計(jì)實(shí)現(xiàn)了該算法的專(zhuān)用硬件處理系統(tǒng)，但由于BIC計(jì)算復(fù)雜度較高，因此專(zhuān)用BIC處理器的消耗資源較多，且最終實(shí)現(xiàn)的嵌入式系統(tǒng)限定了樣本向量的維度不能超過(guò)4維，總的類(lèi)屬數(shù)量介于1～4之間，因此應(yīng)用領(lǐng)域非常有限。而且該處理系統(tǒng)采用隨機(jī)法生成初始化種子，選種質(zhì)量很差。

隨著人工智能應(yīng)用需求的不斷擴(kuò)展，近年來(lái)，學(xué)界提出了很多新的聚類(lèi)處理算法，例如譜聚類(lèi)算法（Spectral Clustering，SP）[10]和基于快速搜索與確定密度極值聚類(lèi)算法（Clustering by Fast Search and Find of Density Peaks，CFSFDP）[11]。這兩種算法在很多復(fù)雜聚類(lèi)任務(wù)中取得了好的聚類(lèi)效果，但是算法的復(fù)雜度相對(duì)較高，同樣本向量總數(shù)N的平方成正比，遠(yuǎn)大于K-均值算法的復(fù)雜度。這些算法同樣存在著需要人工指定參數(shù)的問(wèn)題，而且參數(shù)的選取嚴(yán)重影響著聚類(lèi)的質(zhì)量。存在的問(wèn)題限制了算法在飛行器嵌入式處理系統(tǒng)中的應(yīng)用。另一方面，文獻(xiàn)[12]對(duì)比了不同算法的處理效果，結(jié)果表明，在很多復(fù)雜聚類(lèi)問(wèn)題中，K-均值聚類(lèi)算法能夠取得同最新的算法相似的處理效果。

同時(shí)，受限于質(zhì)量和功耗等方面的要求，航天載荷系統(tǒng)的核心處理算法一般需要運(yùn)行于嵌入式硬件處理平臺(tái)。要求設(shè)計(jì)適合于航天系統(tǒng)應(yīng)用的專(zhuān)用智能圖像處理算法，在算法設(shè)計(jì)階段統(tǒng)籌考慮算法的復(fù)雜度、可移植性、魯棒性和處理精度，即需要考慮算法的硬件友好性。

因此，本文致力于設(shè)計(jì)一種適合于航天系統(tǒng)應(yīng)用的新型K-均值處理算法統(tǒng)籌解決上述問(wèn)題。本文創(chuàng)新性提出了基于變異比（VRC）準(zhǔn)則[13]和分布式最大-最小初始化種子選擇方法的自適應(yīng)K-均值學(xué)習(xí)算法著重解決前兩項(xiàng)問(wèn)題。同時(shí)，作者已在文獻(xiàn)[14]中設(shè)計(jì)了高效的 VRC硬件評(píng)估模塊，并提出了基于FPGA進(jìn)行K-均值并行計(jì)算的硬件結(jié)構(gòu)，為有效解決計(jì)算復(fù)雜度高的問(wèn)題奠定了基礎(chǔ)。最終論文通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法在航天領(lǐng)域嵌入式智能圖像處理應(yīng)用中可行性。

1 自適應(yīng)K-均值學(xué)習(xí)算法

1.1 標(biāo)準(zhǔn)K-均值學(xué)習(xí)算法

如前所述，標(biāo)準(zhǔn)K-均值聚類(lèi)算法的主要目標(biāo)是將N個(gè)樣本聚合為有限的K類(lèi)，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的聚類(lèi)結(jié)果表現(xiàn)為類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。

標(biāo)準(zhǔn)K-均值聚類(lèi)的典型處理流程主要包括兩大步驟：初始化處理和迭代優(yōu)化處理。在初始化處理時(shí)，通過(guò)某些種子選擇算法[15]，將K個(gè)樣本向量備選為初始化種子集（中心集）。之后，執(zhí)行迭代優(yōu)化處理；每次迭代處理后產(chǎn)生優(yōu)化的中心集，直到相鄰兩次迭代后的中心集差值滿(mǎn)足精度要求為止，亦即達(dá)到收斂。圖1通過(guò)一個(gè)實(shí)例給出了標(biāo)準(zhǔn)K-均值聚類(lèi)的具體處理流程。假設(shè)樣本集由二維向量Xi=(x1, x2)，i=1, 2, 3, …, N組成，向量的每一個(gè)元素取值歸一化至[0, 1]，無(wú)需考慮元素的單位。圖中橫軸表示元素x1取值，縱軸表示元素x2取值。第一步，如圖1（a）所示，選取K個(gè)樣本向量作為初始化種子向量，在該示例中，K=3。第二步，計(jì)算每一個(gè)樣本向量同每一個(gè)種子向量之間的距離（稱(chēng)為距離計(jì)算）；依次尋找每一個(gè)樣本向量同K個(gè)初始化種子之間距離的最小值，并將每一個(gè)樣本向量同最小值對(duì)應(yīng)的種子向量聚合為一類(lèi)（稱(chēng)為類(lèi)屬更新）。如圖1（b）所示，所有N個(gè)樣本向量執(zhí)行完距離計(jì)算和類(lèi)屬更新后，N個(gè)樣本向量初步聚合為K類(lèi)。第三步，如圖1（c）所示，計(jì)算每一個(gè)聚類(lèi)中所有樣本向量的均值作為該聚類(lèi)的中心，可以得到一個(gè)由K個(gè)聚類(lèi)中心構(gòu)成的中心集（稱(chēng)為優(yōu)化中心集計(jì)算）。第四步，如圖1（d）所示，以中心集替代種子向量進(jìn)行距離計(jì)算和類(lèi)屬更新，并生成新的中心集，即重復(fù)執(zhí)行第二步和第三步；直到相鄰兩次中心集的差異小于某一閾值，認(rèn)為迭代優(yōu)化過(guò)程達(dá)到了收斂。

通過(guò)對(duì)標(biāo)準(zhǔn)K-均值聚類(lèi)算法的處理流程進(jìn)行分析可以再次明確引言部分的結(jié)論：該算法的處理效果很大程度上取決于K值以及初始化種子的選擇。針對(duì)該問(wèn)題，本文提出了一種基于VRC準(zhǔn)則和分布式最大-最小初始化種子選取方法的自適應(yīng)K-均值學(xué)習(xí)算法。

1.2 VRC準(zhǔn)則

優(yōu)良的K-均值聚類(lèi)結(jié)果應(yīng)該具有較小的類(lèi)內(nèi)距離以保持類(lèi)內(nèi)的緊湊性，同時(shí)具有較大的類(lèi)間距離以保持類(lèi)間的可辨識(shí)性。VRC準(zhǔn)則即直接通過(guò)計(jì)算類(lèi)內(nèi)距離和類(lèi)間距離構(gòu)建評(píng)價(jià)函數(shù)，其具體計(jì)算方式如式（1）～（3）所示。

式中 Sample為樣本值；N表示總的樣本數(shù)量；K表示聚類(lèi)的類(lèi)屬數(shù)量；i和j分別表示類(lèi)屬和樣本的索引；GG表示全體樣本的中心；Centroidi表示第i類(lèi)中心；SNi表示第i類(lèi)中的樣本總數(shù)；SSb表示了類(lèi)間距離的總和；SSw表示類(lèi)內(nèi)距離的總和；SSb/(K-1)反映了平均類(lèi)間距離；SSw/(N-K)反映平均類(lèi)內(nèi)距離，其比值即為VRC的值，反映了總的聚類(lèi)質(zhì)量。

分析可知，當(dāng)某一聚類(lèi)結(jié)果同時(shí)具備較大的類(lèi)間距離和較小的類(lèi)內(nèi)距離時(shí)，聚類(lèi)質(zhì)量較好，此時(shí)VRC值較大。實(shí)際中，伴隨K值的變化，聚類(lèi)結(jié)果的類(lèi)內(nèi)距離和類(lèi)間距離往往會(huì)同時(shí)增大或減小，因此尋找理想K值的過(guò)程本質(zhì)是求解VRC最大值或局部最大值的過(guò)程。這就是利用VRC準(zhǔn)則構(gòu)建自適應(yīng)K-均值聚類(lèi)算法的基本思想。

作為比較，本文也給出了BIC準(zhǔn)則的評(píng)價(jià)函數(shù)[8]，如式(4)所示：

假設(shè)所有N個(gè)數(shù)據(jù)分別屬于有限的幾個(gè)分布，其中BIC表達(dá)式中的第一項(xiàng)表示數(shù)據(jù)δ符合第j個(gè)分布且處于最大似然點(diǎn)時(shí)的對(duì)數(shù)似然比。Pj表示分布中參數(shù)的數(shù)量，其值一般等于(D+1)×K，D為樣本向量的維度。

聚類(lèi)結(jié)果的方差σ2的極大似然估計(jì)值可以表示為

經(jīng)簡(jiǎn)化，BIC準(zhǔn)則的近似表達(dá)式為

式中 α和β為兩個(gè)常數(shù)，使得BIC值非負(fù)，SNi為第i類(lèi)的樣本數(shù)量。SNi×2logSNi同平均類(lèi)間距離相關(guān)，方差項(xiàng)反映了平均類(lèi)內(nèi)距離，其它項(xiàng)對(duì)于BIC值的影響較小。分析可知，同VRC準(zhǔn)則類(lèi)似，優(yōu)化的聚類(lèi)結(jié)果對(duì)應(yīng)較大的BIC值。

比較可知，相對(duì)于BIC聚類(lèi)評(píng)估準(zhǔn)則，VRC值的求取過(guò)程主要為求取絕對(duì)差的運(yùn)算以及少量乘法、除法運(yùn)算，未包括任何復(fù)雜的運(yùn)算處理。而B(niǎo)IC值的求取過(guò)程涉及到平方運(yùn)算和對(duì)數(shù)運(yùn)算等較為復(fù)雜的運(yùn)算處理。因此，VRC準(zhǔn)則是一種硬件友好型的K-均值聚類(lèi)質(zhì)量評(píng)估準(zhǔn)則，更適合于通過(guò)嵌入式處理平臺(tái)實(shí)現(xiàn)。

1.3 自適應(yīng)K-均值聚類(lèi)算法流程

圖2～3給出了基于VRC聚類(lèi)評(píng)估準(zhǔn)則的自適應(yīng)K-均值聚類(lèi)算法原理：對(duì)于相同的樣本采用遞增的K值分別進(jìn)行標(biāo)準(zhǔn)K-均值聚類(lèi)；依次利用VRC準(zhǔn)則對(duì)聚類(lèi)結(jié)果進(jìn)行評(píng)價(jià)；尋找對(duì)應(yīng)VRC最大值（局部最大值）時(shí)的K值，該K值為最優(yōu)聚類(lèi)數(shù)量，而相應(yīng)的聚類(lèi)結(jié)果即為最優(yōu)結(jié)果。

以圖2所示的樣本為例，仍然假設(shè)樣本集由二維向量Xi=(x1, x2), i=1, 2, 3, …, N組成，即向量的維度D=2，圖中N=10，橫軸為x1的值，縱軸為x2的值。算法按照?qǐng)D3所示的流程進(jìn)行處理。K的初值設(shè)定為K=2，即首先將所有樣本按照標(biāo)準(zhǔn)K-均值算法聚合為兩類(lèi)（如圖2（b）中的橢圓灰框所示）；然后計(jì)算其對(duì)應(yīng)的VRC值，對(duì)該聚類(lèi)結(jié)果進(jìn)行聚類(lèi)效果評(píng)估。依次類(lèi)推，對(duì)于K=3, 4, …分別執(zhí)行標(biāo)準(zhǔn)K-均值聚類(lèi)并采用VRC進(jìn)行聚類(lèi)效果評(píng)估，直到VRC取得最大值（或局部最大值）為止。圖4給出了K值變化時(shí)對(duì)應(yīng)聚類(lèi)結(jié)果的VRC值變化情況。其中，K=2時(shí)，VRC=6.7；K=3時(shí)，VRC=12.7；K=4時(shí)，VRC=10.9，表明K=3為優(yōu)化的類(lèi)屬數(shù)量。至此，本次自適應(yīng)K-均值聚類(lèi)處理結(jié)束，輸出K=3時(shí)的聚類(lèi)結(jié)果作為最終的聚類(lèi)結(jié)果。

1.4 分布式最大-最小初始化種子選擇方法

上述算法流程解決了最優(yōu)K值得選取問(wèn)題，但沒(méi)有解決初始化種子集的選擇問(wèn)題。因?yàn)榧词乖谙嗤臉颖竞?K值下，選擇不同的初始化種子集最終產(chǎn)生的聚類(lèi)效果差異很大。該問(wèn)題對(duì)于自適應(yīng) K-均值學(xué)習(xí)算法這種通過(guò)迭代尋找最優(yōu)解的處理方式的影響更加顯著。因此，本文基于最大-最小（max-min）法這種較為理想的初始化種子選擇方法，設(shè)計(jì)了一種稱(chēng)為分布式最大-最小初始化種子選擇方法的改進(jìn)算法，該算法適合于自適應(yīng)K-均值聚類(lèi)算法流程，在保證了種子選取質(zhì)量的前提下降低了選種時(shí)間。

已知最大-最小法的基本思想是使不同的種子盡可能彼此遠(yuǎn)離（這些種子歸屬于不同類(lèi)屬的先驗(yàn)概率很大），這樣有利于將它們歸屬于不同的類(lèi)屬。其具體處理過(guò)程包括以下幾步：第一步，計(jì)算所有樣本向量的全局中心GG；第二步，選擇距離GG最遠(yuǎn)的樣本向量作為第一個(gè)初始化種子（初始化中心）；第三步，計(jì)算所有樣本向量同第一個(gè)初始化種子的距離；第四步，選擇距離第一個(gè)初始化種子最遠(yuǎn)的樣本向量作為第二個(gè)初始化種子；第五步，依次計(jì)算每一個(gè)樣本向量同現(xiàn)有的初始化種子之間距離，并將其同最小值對(duì)應(yīng)的種子聚合為一類(lèi)；第六步，尋找所有樣本向量與所在類(lèi)包含的初始化種子之間距離的最大值，該最大值對(duì)應(yīng)的樣本向量選為下一個(gè)初始化種子。重復(fù)執(zhí)行第五和第六步，直到尋找到K個(gè)初始化種子。

分步式最大-最小初始化種子選擇算法繼承了最大-最小法的基本處理思想；同時(shí)考慮到自適應(yīng) K-均值學(xué)習(xí)算法對(duì)于遞增的K值依次聚類(lèi)時(shí)每次聚類(lèi)得到的聚類(lèi)中心即符合彼此遠(yuǎn)離的條件，因此在完成對(duì)于某一K值的聚類(lèi)后，將K個(gè)聚類(lèi)中心作為K=K+1時(shí)的K個(gè)初始化種子，并額外尋找一個(gè)種子即可實(shí)現(xiàn)新的初始化種子集的選取。

按照該思想設(shè)計(jì)了分布式最大-最小初始化種子選擇方法的具體步驟，如圖4所示。

1）將全局樣本中心GG和距離GG最遠(yuǎn)的樣本選為K=2時(shí)的初始化種子集；

2）根據(jù)K=2的聚類(lèi)結(jié)果，保留兩個(gè)聚類(lèi)中心作為K=3時(shí)的種子，并將擁有類(lèi)內(nèi)最大距離的樣本點(diǎn)加入到K=3時(shí)的初始化種子集；

3）依次類(lèi)推，當(dāng)K=K+1時(shí)，將之前的K個(gè)聚類(lèi)中心保留作為種子，并選取之前的K類(lèi)中擁有類(lèi)內(nèi)最大距離的樣本點(diǎn)作為新加入的初始化種子。

這樣的處理流程同自適應(yīng)K-均值處理流程是完全吻合的，因?yàn)橐环矫婢垲?lèi)結(jié)束后，就可計(jì)算得到各樣本的類(lèi)內(nèi)距離，因而很容易尋找到新的種子；另一方面，當(dāng)類(lèi)屬數(shù)量增加時(shí)，每次只需要重新生成一個(gè)種子。因此，相對(duì)于處理每一個(gè) K值時(shí)都需要重新生成所有初始化種子的方法，這種分步式最大-最小初始化種子選擇方法可有效降低種子選擇的運(yùn)算量和計(jì)算的復(fù)雜度；同時(shí)相對(duì)于隨機(jī)選取種子的方法，本方法在K值遞增1時(shí)，之前K個(gè)聚類(lèi)中心得以保留，因此對(duì)于不同的K值，聚類(lèi)結(jié)果具有強(qiáng)的繼承性，平均迭代次數(shù)顯著減少。該方法也明顯優(yōu)于對(duì)每一個(gè)K值聚類(lèi)時(shí)均采用隨機(jī)法生成種子的策略[9]。

由于樣本向量的總數(shù)N是影響運(yùn)算速度的主要因素（一般N遠(yuǎn)大于K、D和t）。因此，當(dāng)N很大時(shí)，算法的時(shí)間開(kāi)銷(xiāo)也相應(yīng)增大。如前所述，文獻(xiàn)[14]中設(shè)計(jì)了高效的VRC硬件評(píng)估模塊，并提出了基于FPGA實(shí)現(xiàn)N個(gè)樣本數(shù)據(jù)的全并行計(jì)算的硬件結(jié)構(gòu)?；谠摻Y(jié)構(gòu)，本文提出的基于VRC和分布式最大-最小初始化種子選擇方法的自適應(yīng)K-均值學(xué)習(xí)算法的計(jì)算復(fù)雜度僅同聚類(lèi)類(lèi)屬總數(shù)K、樣本向量的維度D以及迭代的次數(shù)t的乘積成正比（大約降低N倍），使得FPGA平臺(tái)完成實(shí)時(shí)自適應(yīng)K-均值學(xué)習(xí)成為可能。

2 自適應(yīng)K-均值聚類(lèi)算法的仿真測(cè)試與分析

為了對(duì)自適應(yīng)K-均值聚類(lèi)算法的性能進(jìn)行綜合評(píng)測(cè)，基于Matlab軟件平臺(tái)對(duì)于算法的完整流程進(jìn)行全面仿真，仿真測(cè)試程序運(yùn)行在一個(gè)Intel Core i5 4-core（3GHz）通用CPU上。

2.1 高斯分布樣本數(shù)據(jù)的自適應(yīng)K-均值聚類(lèi)實(shí)驗(yàn)

對(duì)空間星點(diǎn)進(jìn)行彌散成像時(shí)，所成像點(diǎn)均符合高斯分布。在進(jìn)行星點(diǎn)類(lèi)型分析時(shí)，需要利用自適應(yīng)K-均值算法開(kāi)展研究。因此，設(shè)計(jì)了基于高斯分布樣本數(shù)據(jù)的仿真驗(yàn)證。首先，分別生成K組符合高斯分布但類(lèi)屬中心Centroidi（i=1, 2, 3, …, K）不同的樣本向量，樣本的類(lèi)屬中心隨機(jī)生成，且保證類(lèi)屬中心每個(gè)維度同其它所有類(lèi)屬中心同樣維度的值之間的差異大于0.2（歸一化后的數(shù)值），樣本方差為0.05。并將所有樣本向量組合起來(lái)作為完整的測(cè)試樣本集（即預(yù)設(shè)了 K值）；其次，對(duì)于測(cè)試樣本集進(jìn)行自適應(yīng) K-均值聚類(lèi)處理；最后，比較自主決策得到的類(lèi)屬數(shù)量是否為預(yù)設(shè)的 K值。同時(shí)，為了確保算法的魯棒性，采用不同的數(shù)據(jù)樣本開(kāi)展了100次實(shí)驗(yàn)。經(jīng)實(shí)驗(yàn)測(cè)試，分別改變測(cè)試樣本集的類(lèi)屬數(shù)量K、樣本數(shù)量N、樣本維度D時(shí)，最終由算法判定得到的類(lèi)屬數(shù)量均同預(yù)設(shè)值一致。

測(cè)試時(shí)，預(yù)設(shè)的測(cè)試樣本集內(nèi)，N=400，K=8，D=64，即理論上400個(gè)測(cè)試樣本應(yīng)分為8類(lèi)。表1給出了其中一組測(cè)試結(jié)果的具體數(shù)值，分別給出了對(duì)應(yīng)自適應(yīng)K-均值聚類(lèi)過(guò)程中不同K值時(shí)VRC的具體數(shù)值和迭代運(yùn)算的次數(shù)t。由表可知，K=8時(shí)，伴隨著自適應(yīng)K-均值聚類(lèi)過(guò)程，VRC取得了局部最大值（2 019.9），由1.3節(jié)可知，算法評(píng)估認(rèn)為將該測(cè)試樣本聚合為8類(lèi)時(shí)聚類(lèi)效果最佳。該結(jié)果與實(shí)驗(yàn)的預(yù)設(shè)條件完全一致。

表1 高斯分布樣本數(shù)據(jù)的自適應(yīng)K-均值聚類(lèi)實(shí)驗(yàn)結(jié)果Tab.1 Adaptive K-means clustering result for Guassian distribution samples

2.2 基于自適應(yīng)K-均值聚類(lèi)的圖像分割實(shí)驗(yàn)

探測(cè)機(jī)器人對(duì)未知目標(biāo)抵近操作時(shí)，需要基于圖像分割的結(jié)果開(kāi)展目標(biāo)局部特征的識(shí)別。作為有效的圖像分割處理手段，有必要對(duì)算法的圖像分割能力進(jìn)行驗(yàn)證。如圖5（a）所示，實(shí)驗(yàn)選取了多張標(biāo)志圖片的灰度圖像作為測(cè)試集，直接利用像素點(diǎn)的灰度值進(jìn)行自適應(yīng)K-均值聚類(lèi)運(yùn)算。自適應(yīng)K-均值聚類(lèi)得到的不同聚類(lèi)類(lèi)屬分別以不同的顏色標(biāo)記，如圖5（b）所示。

比較原始圖片和經(jīng)圖像分割后的圖片可知，經(jīng)自適應(yīng)K-均值聚類(lèi)處理，原始圖片按照灰度等級(jí)得到了合理的劃分，生成的每一個(gè)聚類(lèi)分別對(duì)應(yīng)于原始圖片中的一個(gè)局部區(qū)域，而且局部區(qū)域的數(shù)量和分布情況同主觀感受一致。

2.3 圖像的自適應(yīng)K-均值聚類(lèi)實(shí)驗(yàn)

探測(cè)機(jī)器人進(jìn)入一個(gè)未知環(huán)境后，需要基于無(wú)監(jiān)督學(xué)習(xí)構(gòu)建最初的認(rèn)知。因此應(yīng)該通過(guò)實(shí)驗(yàn)驗(yàn)證算法的圖像聚類(lèi)處理能力。用于實(shí)驗(yàn)的樣本圖片選自COIL-100數(shù)據(jù)庫(kù)（Columbia University Object Image Library）[16]，如圖6所示。在具體實(shí)驗(yàn)時(shí)，共抽選了來(lái)自該數(shù)據(jù)庫(kù)8個(gè)類(lèi)屬中的64張圖片用于測(cè)試。圖中分別給出了每類(lèi)樣本圖片中的一個(gè)典型樣本作為代表。為了進(jìn)行有效的學(xué)習(xí)處理，借助于PPED特征向量對(duì)樣本圖片進(jìn)行表征[17]，這是一種基于方向邊緣的硬件友好型特征表示方法，特征的表示能力較強(qiáng)。仿真實(shí)驗(yàn)遵照?qǐng)D3所示的處理流程進(jìn)行，并采用所提出的分布式最大-最小初始化種子選擇方法進(jìn)行種子選取。

仿真實(shí)驗(yàn)結(jié)果如表2所示，表中分別給出了對(duì)應(yīng)自適應(yīng)K-均值聚類(lèi)過(guò)程中不同K值時(shí)VRC的具體數(shù)值。由表可知，當(dāng)K=8時(shí)，自適應(yīng)K-均值聚類(lèi)過(guò)程取得了VRC最大值（1 400.1），即認(rèn)為測(cè)試樣本應(yīng)該聚合為8類(lèi)，該結(jié)果與實(shí)驗(yàn)的預(yù)設(shè)條件完全一致。

表2 圖像的自適應(yīng)K-均值聚類(lèi)實(shí)驗(yàn)結(jié)果Tab.2 Adaptive K-means clustering result for sample images

2.4 VRC與BIC性能比較

本文設(shè)計(jì)了仿真實(shí)驗(yàn)比較利用VRC和BIC準(zhǔn)則進(jìn)行聚類(lèi)質(zhì)量評(píng)估時(shí)的性能優(yōu)劣。仍然采用2.1節(jié)的符合高斯分布的測(cè)試樣本集作為測(cè)試樣本。對(duì)于相同的樣本，分別基于VRC準(zhǔn)則和BIC準(zhǔn)則計(jì)算自適應(yīng)K-均值聚類(lèi)時(shí)對(duì)應(yīng)不同K值時(shí)的定量評(píng)估值。公平起見(jiàn)，仿真時(shí)均采用分布式最大-最小初始化種子選擇方法進(jìn)行種子選取。

表3記錄了不同K值時(shí)的VRC和BIC定量評(píng)估結(jié)果。當(dāng)K=8時(shí)，VRC和BIC同時(shí)取得了最大值。因此，在該實(shí)驗(yàn)中通過(guò)兩者均可判定出最優(yōu)類(lèi)屬數(shù)量值。但是比較兩者的數(shù)據(jù)分布不難發(fā)現(xiàn)，雖然它們的總體分布情況相似，但是當(dāng)K＞7時(shí)，BIC值的變化幅度很小，例如，當(dāng)K=8時(shí)，BIC的值為2 020.5，而當(dāng)K=9，10時(shí)，BIC的值分別為2 020.1和2 019.7，盡管聚類(lèi)K值不同，但BIC的值變化很小，亦即靈敏度下降，而VRC值的變化幅度仍然較大。因此，相對(duì)于BIC準(zhǔn)則，采用VRC準(zhǔn)則進(jìn)行K-均值聚類(lèi)質(zhì)量的定量評(píng)估，算法的靈敏度更高。

此外，文章利用 BIC準(zhǔn)則對(duì) 2.3節(jié)的樣本開(kāi)展了聚類(lèi)測(cè)試。結(jié)果表明，即使同樣采用分布式最大-最小初始化種子選擇方法進(jìn)行種子選取，K=9時(shí)BIC取得極值，即錯(cuò)誤的判定樣本應(yīng)該分為9類(lèi)，對(duì)應(yīng)的結(jié)果是將圖8中的第2類(lèi)和第8類(lèi)劃分為了3類(lèi)。

表3 VRC和BIC定量評(píng)測(cè)結(jié)果比較Tab.3 Comparison of quantitative evaluation results based on VRC and BIC

2.5 分布式最大-最小初始化種子選擇方法的有效性

同樣采用2.1節(jié)的符合高斯分布的測(cè)試樣本集作為測(cè)試樣本。對(duì)于隨機(jī)選擇法和分布式最大-最小初始化種子選擇法進(jìn)行測(cè)試比較。當(dāng)采用隨機(jī)選擇法生成初始化種子時(shí)，仿照自適應(yīng) K-均值的處理流程，依次對(duì)于K取2～10時(shí)執(zhí)行標(biāo)準(zhǔn)K-均值聚類(lèi)，分別計(jì)算相應(yīng)的VRC值，記錄相應(yīng)的迭代次數(shù)t。同本文提出的自適應(yīng)K-均值聚類(lèi)算法的區(qū)別在于：對(duì)于不同的K值，每次均采用隨機(jī)選擇法生成所有初始化種子。

表4記錄了采用隨機(jī)選擇法時(shí)的測(cè)試結(jié)果。對(duì)比表1可知，表4中的VRC值普遍偏低。分析可知，按照這種方式進(jìn)行處理時(shí)，對(duì)應(yīng)每一個(gè)K值的聚類(lèi)結(jié)果都很難達(dá)到最優(yōu)，而且不同K值之間的結(jié)果不具有連續(xù)性，因此很容易出現(xiàn)錯(cuò)誤。例如，表4的結(jié)果中，K=7時(shí)的VRC值大于K=8時(shí)的VRC值，錯(cuò)誤的判斷了最優(yōu)的類(lèi)屬數(shù)量。此外，在表1中，不同K值進(jìn)行聚類(lèi)時(shí)的迭代次數(shù)均為2；在表4中，迭代次數(shù)普遍偏高，最大達(dá)到了11，因此運(yùn)算時(shí)間更長(zhǎng)。

表4 基于隨機(jī)選擇法生成種子的K-均值聚類(lèi)的定量評(píng)測(cè)結(jié)果Tab.4 Quantitative evaluation result for K-means clustering based on random seeds selection method

由實(shí)驗(yàn)結(jié)果可知，采用分布式最大-最小法作為自適應(yīng)K-均值聚類(lèi)算法的初始化種子選擇方法，有效保證了K-均值聚類(lèi)的質(zhì)量和不同K值時(shí)聚類(lèi)結(jié)果的連續(xù)性，使得自主決策最優(yōu)K值并得到相應(yīng)的聚類(lèi)結(jié)果成為可能。相對(duì)于由隨機(jī)選擇法生成的初始化種子進(jìn)行聚類(lèi)處理，運(yùn)算過(guò)程的迭代次數(shù)更少，速度更快且得到的聚類(lèi)結(jié)果更優(yōu)。

2.6 實(shí)時(shí)計(jì)算結(jié)構(gòu)的加速能力

為了驗(yàn)證FPGA嵌入式處理平臺(tái)對(duì)算法處理速度提升的能力，本文利用通用CPU和FPGA對(duì)相同樣本開(kāi)展圖像聚類(lèi)實(shí)驗(yàn)。已知文獻(xiàn)[13]中FPGA工作于25MHz時(shí)，對(duì)N=256、K=8、D=64圖像聚類(lèi)時(shí)，自適應(yīng)K-均值聚類(lèi)時(shí)間約為0.42ms；同樣的樣本利用Intel Core i5 4-core（3GHz）通用CPU仿真時(shí)平均耗時(shí)62ms；即FPGA平臺(tái)加速了147倍，加速比同樣本數(shù)量N處于同一量級(jí)。當(dāng)樣本數(shù)量增加時(shí)，利用FPGA平臺(tái)處理的耗時(shí)增加很少，但利用通用CPU處理耗時(shí)會(huì)線(xiàn)性增加，加速比顯著提高。

3 結(jié)束語(yǔ)

無(wú)監(jiān)督學(xué)習(xí)是智能遙感衛(wèi)星實(shí)現(xiàn)圖像分割，探測(cè)機(jī)器人實(shí)現(xiàn)自主目標(biāo)分類(lèi)等任務(wù)的基礎(chǔ)。本文以標(biāo)準(zhǔn)K-均值聚類(lèi)算法為基礎(chǔ)，針對(duì)現(xiàn)有算法存在的三項(xiàng)主要問(wèn)題，提出了一種面向航天載荷系統(tǒng)應(yīng)用的自適應(yīng)K-均值學(xué)習(xí)算法。提出了基于VRC評(píng)估準(zhǔn)則自動(dòng)決定最優(yōu)聚類(lèi)類(lèi)屬數(shù)量的處理方法和流程；以最大-最小初始化種子選擇方法為依據(jù)，結(jié)合自適應(yīng)K-均值聚類(lèi)算法的處理流程，提出了一種分布式最大-最小初始化種子選擇方法，該方法不但能夠選取更加優(yōu)化的初始化種子集，而且能夠有效降低選種的時(shí)間；進(jìn)而分析了利用FPGA嵌入式平臺(tái)實(shí)現(xiàn)該算法的可行性。最終，對(duì)算法的性能進(jìn)行了全面的仿真測(cè)試，結(jié)果表明，針對(duì)各種類(lèi)型的樣本向量集，該算法均能夠自主確定最優(yōu)類(lèi)屬數(shù)量，并完成相應(yīng)的聚類(lèi)，其結(jié)果與理論預(yù)期一致，為實(shí)現(xiàn)目標(biāo)分類(lèi)、圖像分割等智能圖像處理任務(wù)奠定了基礎(chǔ)。此外，利用VRC與BIC對(duì)相同的測(cè)試樣本集進(jìn)行了聚類(lèi)質(zhì)量評(píng)估，比較可知，VRC具有更高的靈敏度，驗(yàn)證了基于VRC準(zhǔn)則進(jìn)行K-均值聚類(lèi)評(píng)估的可靠性。進(jìn)而，通過(guò)與初始化種子的隨機(jī)選擇法進(jìn)行橫向比較，證明了分布式最大-最小初始化種子選擇方法的有效性和可靠性。

References)

[1]岳宗玉, 邸凱昌. 好奇心號(hào)巡視器及其特點(diǎn)分析[J]. 航天器工程, 2012, 21(5)： 110-116. YUE Zongyu, DI Kaichang. Mars Curiosity Rover and Its Characteristics[J]. Spacecraft Engineering, 2012, 21(5)： 110-116. (in Chinese)

[2]KIM D, SUN J, SANG M O, et al. Traversability Classification Using Unsupervised on-line Visual Learning for Outdoor Robot Navigation[C]//International Conference on Robotics and Automation, IEEE, Orlando, FL, USA, 2006： 518-525. DOI：10.1109/ROBOT.2006.1641763

[3]MACQUEEN J. Some Methods for Classification and Analysis of Multivariate Observations[C]//The Fifth Berkeley Symposium on Mathematical Statistics and Probability, Univ. California Press, California, USA, 1967： 281-297.

[4]NG R T, HAN Jiawei. CLARANS： A Method for Clustering Objects for Spatial Data Mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5)： 1003-1016.

[5]ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH： An Efficient Data Clustering Method for Very Large Databases[C]// ACM International Conference on Management of Data, IEEE. Montreal, 1996： 103-114.

[6]ESTER M, KRIEGEL H P, SANDER J, et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]//ACM Conference on Knowledge Discovery and Data Mining, 1996： 226-231.

[7]JAIN AK. Data Clustering： 50 Years Beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8)： 651-666. DOI：10.1007/978-3-540-87479-9_3

[8]PELLEG D, MOORE A W. X-means： Extending K-means with Efficient Estimation of the Number of Clusters[C]// Seventeenth International Conference on Machine Learning. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 2000： 727-734.

[9]CHEN T W, SUN C H, SU H H, et al. Power-efficient Hardware Architecture of K-means Clustering with Bayesianinformation-criterion Processor for Multimedia Processing Applications[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2011, 1(3)： 357-368.

[10]LUXBURG U V. A Tutorial on Spectral Clustering[J]. Statistics and Computing, 2007, 17(4)： 395-416.

[11]RODRIGUEZ A, LAIO A. Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191)： 1492-1496.

[12]張文開(kāi). 基于密度的層次聚類(lèi)算法研究[D]. 合肥： 中國(guó)科學(xué)技術(shù)大學(xué), 2015. ZHANG Wenkai. Research on Density-based Hierarchical Clustering Algorithm[D]. Hefei： University of Science and Technology of China, 2015. (in Chinese)

[13]CALINSKI T, HARABASZ J. A Dendrite Method for Cluster Analysis[J]. Communications in Statistics, 1974, 3(1)： 1-27.

[14]HOU Z, MA Y, ZHU H, et al. Real-time Very Large-scale Integration Recognition System with an On-chip Adaptive K-means Learning Algorithm[J]. Japanese Journal of Applied Physics, 2013, 52(4)： 04CE11.

[15]HE J, LAN M, TAN C L, et al. Initialization of Cluster Refinement Algorithms： A Review and Comparative Study[C]// IEEE International Joint Conference on Neural Networks, IEEE, Budapest, Hungary, 2004： 297-302. DOI：10.1109/IJCNN.2004.1379917

[16]NAYAR S K, NENE S A, MURASE H. Real-time 100 Object Recognition System[C]//IEEE International Conference on Robotics and Automation, IEEE, Minneapolis, MN, USA, 1996： 2321-2325. DOI： 10.1109/ROBOT.1996.506510

[17]YAGI M, SHIBATA T. An Image Representation Algorithm Compatible with Neural Associative Processor-based Hardware Recognition Systems[J]. IEEE Transactions on Neural Networks, 2003, 14(5)： 1144-1161.

An Hardware-friendly Adaptive K-means Learning Algorithm

HOU Zuoxun1HAN Pei2ZHANG Hongwei1AN Ran1
（1 Beijing Institute of Space Mechanics & Electricity, Beijing 100190, China）（2 Technology and Engineering Center for Space Utilization, Chinese Academy of Sciences, Beijing 100190, China）

This paper proposes a hardware-friendly adaptive K-means learning algorithm to solve the basic problems of the standard K-means algorithm which include determining the cluster number and the reasonable initial seeds automatically, and improving the computing speed effectively. The proposed algorithm uses the variance ratio criterion (VRC) to quantatively evaluate the clustering result, and finds the optimized cluster number by seeking the maximal value of the VRC. The distributed max-min initial seeds selection method is proposed to find the optimized initial seeds for different K by searching for the sample with maximal inner-cluster distance gradually. Also, this paper introduces the possible scheme of implementing the algorithm by FPGA. The simulations show that the proposed algorithm can finish the clustering tasks for different kinds of samples accurately and efficiently. The VRC evaluating results completely satisfy the theoretical prospective, and the found initial seeds are reasonable. It can be used in some intelligent image processing tasks, such as the object classification and image segmentation.

adaptive; K-means; hardware friendly; image processing; space remote sensing

TP72

A

1009-8518(2017)03-0068-10

10.3969/j.issn.1009-8518.2017.03.008

侯作勛，男，1986年生，2015年獲西安交通大學(xué)控制科學(xué)與工程專(zhuān)業(yè)博士學(xué)位，工程師。研究方向?yàn)槟Ｊ阶R(shí)別與智能系統(tǒng)、數(shù)字電路設(shè)計(jì)。E-mail： hzx_007xjtu@163.com。

（編輯：毛建杰）

2016-12-13

國(guó)家重點(diǎn)研發(fā)計(jì)劃（2016YFB0501300，2016YFB0501302）