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

侯作勛韓培張宏偉安然

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

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

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

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

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

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

0 引言

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

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

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

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

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

1.1 標準K-均值學(xué)習算法

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

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

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

1.2 VRC準則

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

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

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

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

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

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

經(jīng)簡化，BIC準則的近似表達式為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 基于自適應(yīng)K-均值聚類的圖像分割實驗

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

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

2.3 圖像的自適應(yīng)K-均值聚類實驗

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

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

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

2.4 VRC與BIC性能比較

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

References)

[1]岳宗玉, 邸凱昌. 好奇心號巡視器及其特點分析[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]張文開. 基于密度的層次聚類算法研究[D]. 合肥： 中國科學(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é)與工程專業(yè)博士學(xué)位，工程師。研究方向為模式識別與智能系統(tǒng)、數(shù)字電路設(shè)計。E-mail： hzx_007xjtu@163.com。

（編輯：毛建杰）

2016-12-13

國家重點研發(fā)計劃（2016YFB0501300，2016YFB0501302）