一種硬件友好型自適應K-均值學習算法

侯作勛韓培張宏偉安然

（1 北京空間機電研究所，北京 100190）（2 中國科學院空間應用工程與技術中心，北京 100190）

一種硬件友好型自適應K-均值學習算法

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

（1 北京空間機電研究所，北京 100190）（2 中國科學院空間應用工程與技術中心，北京 100190）

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

自適應 K-均值 硬件友好 圖像處理 航天遙感

0 引言

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

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

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

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

1 自適應K-均值學習算法

1.1 標準K-均值學習算法

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

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

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

1.2 VRC準則

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

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

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

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

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

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

經簡化，BIC準則的近似表達式為

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

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

1.3 自適應K-均值聚類算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 高斯分布樣本數據的自適應K-均值聚類實驗

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

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

表1 高斯分布樣本數據的自適應K-均值聚類實驗結果Tab.1 Adaptive K-means clustering result for Guassian distribution samples

2.2 基于自適應K-均值聚類的圖像分割實驗

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

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

2.3 圖像的自適應K-均值聚類實驗

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

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

表2 圖像的自適應K-均值聚類實驗結果Tab.2 Adaptive K-means clustering result for sample images

2.4 VRC與BIC性能比較

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

表3記錄了不同K值時的VRC和BIC定量評估結果。當K=8時，VRC和BIC同時取得了最大值。因此，在該實驗中通過兩者均可判定出最優類屬數量值。但是比較兩者的數據分布不難發現，雖然它們的總體分布情況相似，但是當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-均值聚類質量的定量評估，算法的靈敏度更高。

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

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

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

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

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

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

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

2.6 實時計算結構的加速能力

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

3 結束語

無監督學習是智能遙感衛星實現圖像分割，探測機器人實現自主目標分類等任務的基礎。本文以標準K-均值聚類算法為基礎，針對現有算法存在的三項主要問題，提出了一種面向航天載荷系統應用的自適應K-均值學習算法。提出了基于VRC評估準則自動決定最優聚類類屬數量的處理方法和流程；以最大-最小初始化種子選擇方法為依據，結合自適應K-均值聚類算法的處理流程，提出了一種分布式最大-最小初始化種子選擇方法，該方法不但能夠選取更加優化的初始化種子集，而且能夠有效降低選種的時間；進而分析了利用FPGA嵌入式平臺實現該算法的可行性。最終，對算法的性能進行了全面的仿真測試，結果表明，針對各種類型的樣本向量集，該算法均能夠自主確定最優類屬數量，并完成相應的聚類，其結果與理論預期一致，為實現目標分類、圖像分割等智能圖像處理任務奠定了基礎。此外，利用VRC與BIC對相同的測試樣本集進行了聚類質量評估，比較可知，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]. 合肥： 中國科學技術大學, 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年獲西安交通大學控制科學與工程專業博士學位，工程師。研究方向為模式識別與智能系統、數字電路設計。E-mail： hzx_007xjtu@163.com。

（編輯：毛建杰）

2016-12-13

國家重點研發計劃（2016YFB0501300，2016YFB0501302）