一种硬件友好型自适应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-均值学习算法这种通过迭代寻找最优解的处理方式的影响更加显著。因此，本文基于最大-最小（max-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个样本数据的全并行计算的硬件结构。基于该结构，本文提出的基于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）