﻿ 基于改进K_Medoids算法的高光谱图像聚类
«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2018, Vol. 39 Issue (9): 1574-1581  DOI: 10.11990/jheu.201706108 0

### 引用本文

WANG Liguo, MA Henan, ZHAO Liang, et al. Hyperspectral image clustering based on improved K_Medoids algorithm[J]. Journal of Harbin Engineering University, 2018, 39(9), 1574-1581. DOI: 10.11990/jheu.201706108.

### 文章历史

Hyperspectral image clustering based on improved K_Medoids algorithm
WANG Liguo, MA Henan, ZHAO Liang, SHI Yao
College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
Abstract: It is a difficult problem to summarize the clustering combination with high reference value in the complex hyperspectral image with huge quantity. In this paper, an improved K_Medoids algorithm based on manifold was proposed and applied to the clustering practice of hyperspectral images. Firstly, the improved Canopy algorithm was used to select the initial value, then the clustering process of K_Medoids algorithm was completed by the pixel element distance matrix generated by the manifold-based geometric distance. The algorithm can properly suppress some defects difficult to be extinguished in the traditional clustering algorithms. The algorithm was tested by AVIRIS image and the experimental results show that it can achieve better results than the traditional method on the aspects of five evaluation criteria including intraclass distance, interclass distance, Jaccard coefficient, Rand coefficient and intuitionistic contrast of clustering images.
Keywords: hyperspectral    K_Medoids algorithm    Canopy algorithm    isometric mapping algorithm    geometric distance    clustering

1 理论基础 1.1 K_Medoids算法

K_Means算法是最为经典的聚类算法之一, 其基本实现思想为：首先随机选定K个原始聚类中心的位置, 计算其余样本目标与聚类中心的欧氏距离, 并把样本赋予到最近的聚类之中；然后计算每个类内部各样本的平均值进而得到新的聚类中心。反复迭代以上步骤, 直到目标函数收敛为止。其均值的平方误差目标函数为

 $J = \sum\limits_{n = 1}^N {\sum\limits_{k = 1}^K {{{\left\| {{x_n} - {\mu _k}} \right\|}^2}} }$ (1)

K_Medoids算法是在K_Means算法的基础上改进而来, 不同之处在于K_Medoids的初始聚类中心是选择当前簇内的中值点, 也就是到其他簇内各样本点的距离之和最小的样本点。这样做有两大好处：1)削弱了离群点的负面影响；2)能够把K_Means的应用领域拓展到离散样本空间。基于K_Medoids的典型算法是Kaufman和Rousseeuw提出的PAM(partitioning around medoid)算法[9], 以及他们之后提出的基于抽样的CLARA(clustering LARge applications)算法[10]。K_Medoids的基本算法流程为

1) 为每个簇随机选择一个初始聚类中心, 剩余对象根据其距离中心的距离分给最近的指定簇；

2) 用非中心点来代替中心点, 重新计算其到簇内各个样本点的距离, 如果满足条件则替换聚类中心。

 ${d_{\mathit{\boldsymbol{ab}}}} = \sqrt {\sum\limits_{k = 1}^n {{{({x_{1k}} - {x_{2k}})}^2}} }$ (2)

3) 聚类结果的质量用目标函数来评估, 该函数评估了对象与其聚类中心的相似程度。当聚类中心的变化小于某阈值时, 计算过程结束。其误差的平方和为

 $J = \sum\limits_{j = 1}^K {\mathop \sum \limits_{p \in {c_j}} ({{\left\| {p - {o_i}} \right\|}^2})}$ (3)

1.2 Canopy算法

Canopy算法是一种“粗”聚类算法, 快速简单。该算法最大的优势是不用预先设定K的取值, 因此非常适合作为K_Means或K_Medoids算法的预处理算法, 能够在一定程度上解决K值选择的盲目性。在Canopy算法的基础上在选择出来的局部Canopy里进行K_Means或K_Medoids算法, 能够有效减少相似计算的数量。

Canopy算法基本实现步骤如下：

1) 将数据集经过向量化处理为一个list, 预先设定两个阈值：T1T2, 其中T1>T2

2) 在list中随机取一点P, 计算点P与所有Canopy之间的距离(首次计算时把点P设置为第一个Canopy), 将点P归属到与其距离在T1以内的Canopy内；

3) 如果点P距离某个Canopy在T2以内, 此时需在list中移除点P

4) 重复步骤2)、3), 直到list为空结束。

1.3 ISOMAP与测地距离

“等距映射”主要体现在降维之后样本点之间的距离不变, 此时的距离即为测地距离。通俗地说, 从A城市到B城市的欧氏距离是两城市的直线长度, 而测地距离是经过沿途各城镇距离之和中的最短距离。测地距离与欧氏距离的对比如图 3

 Download: 图 3 测地距离与欧氏距离对比示意图 Fig. 3 Comparison of geodesic distance and Euclidean distance

2 基于流形的Canopy-K_Medoids联合算法

Canopy算法和K_Medoids算法是用来聚类的常用算法, Canopy算法的主要功能是预先划分聚类区域, 为其后的聚类算法提供参考；K_Medoids算法是以簇内中值点位聚类中心, 利用簇内各点距离作为衡量标准进行聚类的算法。文献[11]运用Canopy算法对K_Means算法进行改进, 应用在多类UCI数据集上取得了很好的效果, 借鉴其算法思想并进行改进, 将改进的Canopy和K_Medoids的联合算法应用在高光谱图像的无监督聚类上。首先使用基于“最大最小”原则的Canopy改进算法对整个数据集进行预处理, 在此基础上再应用基于测地距离的K_Medoids算法进行聚类。

2.1 Canopy算法进行预处理过程描述

1) 初始化。

2) Canopy算法的聚类中心点位置设定。

 $\left\{ \begin{array}{l} {\rm{Dist}}D = \max (\min ({d_1}, {d_2}))\\ {\rm{Dist}}D = \max (\min ({d_1}, {d_2}, \cdots , {d_M})) \end{array} \right.$ (4)

3) Canopy算法的聚类中心个数K的设定。

① 通过上个步骤确定M个聚类中心备选点, 在一定合理区间内逐步增加聚类中心点的个数C, 调整T1的值, 当D内数据被全部囊括在Canopies中后停止调整T1值的大小；

② 记录每次C值变动后各Canopy内各样本点到聚类中心的平均距离ds

③ 选取适当的突变点并保存此时的C值, 将此数计为K值；

④ 终止。设置终止条件为最大迭代次数N1

2.2 基于测地距离的K_Medoids聚类算法过程描述

1) 初始化。

2) 计算数据样本数据D内各样本间的最短路径矩阵。

3) 应用K_Medoids算法对数据点进行聚类。

Canopy粗聚类提供了K参考值和初始聚类中心位置, 同时加载上一步生成的最短路径矩阵HG, 在此基础上可以进行K_Medoids聚类运算。其算法步骤如下:

① 按照Canopy算法的运算结果, 设置K个初始聚类中心D1, D2, …, Dk

② 通过最短路径矩阵HG找到其他样本点距离最短的聚类中心, 为样本点寻找所应归属的簇O1, O2, …, Ok

③ 在每个簇Oi内, 顺序选取各点Di, 计算Di到其余簇内各点的距离之和${d_{{D_i}}} = \mathop \sum \limits_{j \in {O_i}} d({D_i}, {D_j})$, 也即计算绝对误差值, 选取绝对误差最小的点作为新的聚类中心。

④ 重复执行②~③直到聚类中心的位置不再变化为止。

4) 终止条件。

2.3 基于流形的Canopy-K_Medoids算法在高光谱图像聚类上的应用

 Download: 图 4 本文算法整体流程图 Fig. 4 The overall flow chart of this algorithm
3 实验与评估

 Download: 图 6 印第安纳州农林混合实验场图像参考地物 Fig. 6 Indiana agriculture and forestry mixed test site image reference

 $D = \sum\limits_{i = 1}^K {\sum\limits_{{x_{ik}} \in {\varphi _j}, k = 1}^{N({\varphi _j})} {|{x_{ik}} - {{\bar x}_i}|} }$ (6)

 $L = \sum\limits_{i = 1}^K {|{x_i} - x'|}$ (7)

Jaccard系数和Rand指数是常用于评价聚类效果好坏的标准, 其取值越大说明聚类效果越好。设数据集X的一个聚类结构为C={C1, C2, …, Cm}, 数据集已知的划分为P={P1, P2, …, Ps}, 可通过比较CP的比较来评价聚类的质量。遍历所有数据点, 对数据集中任一对点, 计算下列项：

1) 两个点同属C, 且同属P, 则a++；

2) 两个点同属C, 但不同属P, 则b++；

3) 两个点不属于同一个C, 但同属P, 则c++；

4) 两个点既不属于同一个C, 也不同属P, 则d++。

 $R = \left( {a + b} \right)/\left( {a + b + c + d} \right)$ (8)

Jaccard系数为

 $J' = a/\left( {a + b + c} \right)$ (9)

 Download: 图 7 萨利纳斯山谷8种地物下6种算法的效果对比图 Fig. 7 Comparsion of 6 algorthms for 8 classes in Salinas valley images
 Download: 图 8 印第安纳州农林混合实验场8种地物下6种算法的效果对比图 Fig. 8 Comparsion of 6 algorithms for 8 classes in the Indiams agriculture and forestry mixed text site

4 结论

1) 通过对照实验, 证明了提出算法所使用的改进的Canopy算法预聚类算法有效地克服了传统聚类算法所具有的初值敏感的问题；使用测地距离改进样本距离度量标准有效的克服了传统聚类算法所具有的离群点敏感、初值敏感、易陷入局部最优的问题, 获得了较为理想的聚类效果。与其他主流聚类算法的对比实验证明了本文算法的有效性和优越性。

2) 高光谱图像数据因其匮乏有标签数据, 所以其聚类分析往往是分类的前提。在合理的聚类结果基础上再进行分类分析, 往往更加方便可靠。本文所提出的改进聚类算法对于高光谱图像的聚类分析有一定的应用价值, 所提出的聚类效果判定标准对于聚类分析有一定的指导意义。

3) 在实验中发现提出算法需要计算所有样本点之间的距离, 而测地距离作为一种图论距离本身也十分庞大。这就导致本文算法在运行时间上要远远长于其他传统算法, 对实验设备的性能要求也比较高, 这一点目前尚没有较好的解决途径。

 [1] 李翔.高光谱影像的聚类分析及应用[D].北京: 北京交通大学, 2015. LI Xiang. Clustering analysis of hyperspectral image and its application[D]. Beijing: Beijing Jiaotong University, 2015. http://cdmd.cnki.com.cn/Article/CDMD-10004-1015594115.htm (0) [2] 李波. 高维数据的流形学习分析方法[M]. 武汉: 武汉大学出版社, 2016. LI Bo. Manifold learning analysis method for high dimensional data[M]. Wuhan: Wuhan University, 2016. (0) [3] YUE Xia, WANG Man, YUE Jun, et al. Parallel K-Medoids++ spatial clustering algorithm based on MapReduce[J]. arXiv preprint arXiv: 1608.06861, 2016. http://cn.arxiv.org/abs/1608.06861 (0) [4] AGHAEE A, GHADIRI M, BAGHSHAH M S. Active distance-based clustering using K-Medoids[M]//BAILEY J, KHAN L, WASHIO T, et al. Advances in Knowledge Discovery and Data Mining. Cham: Springer International Publishing, 2016. (0) [5] 曹丹阳, 杨炳儒, 李广原, 等. 一种基于CF树的K-Medoids聚类算法[J]. 计算机应用研究, 2011, 28(9): 3260-3263. CAO Danyang, YANG Bingru, LI Guangyuan, et al. K-Medoids clustering algorithm based on CF tree[J]. Application research of computers, 2011, 28(9): 3260-3263. DOI:10.3969/j.issn.1001-3695.2011.09.015 (0) [6] 马箐, 谢娟英. 基于粒计算的K-Medoids聚类算法[J]. 计算机应用, 2012, 32(7): 1973-1977. MA Qing, XIE Juanying. New K-Medoids clustering algorithm based on granular computing[J]. Journal of computer applications, 2012, 32(7): 1973-1977. (0) [7] 王常武, 刘小凤, 王宝文, 等. IC-Kmedoids:适用于RNA二级结构预测的聚类算法[J]. 生物医学工程学杂志, 2015, 32(1): 99-103. WANG Changwu, LIU Xiaofeng, WANG Baowen, et al. IC-Kmedoids:a clustering algorithm for RNA secondary structure prediction[J]. Journal of biomedical engineering, 2015, 32(1): 99-103. (0) [8] 赵烨, 黄泽君. 蚁群K-Medoids融合的聚类算法[J]. 电子测量与仪器学报, 2012, 26(9): 800-804. ZHAO Ye, HUANG Zejun. Clustering algorithm based on fusion of ant colony algorithm and K-Medoids[J]. Journal of electronic measurement and instrument, 2012, 26(9): 800-804. (0) [9] KAUFMAN L, ROUSSEEUW P J. Partitioning around medoids (Program PAM)[M]//KAUFMAN L, ROUSSEEUW P J. Finding groups in Data: An Introduction to Cluster Analysis. Hoboken: John Wiley & Sons, Inc., 2008: 68-125. (0) [10] KAUFMAN L, ROUSSEEUW P J. Clustering large applications (Program CLARA)[M]//KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: An Introduction to Cluster Analysis. Hoboken: John Wiley & Sons, Inc., 2008: 126-163. (0) [11] 赵庆. 基于Hadoop平台下的Canopy-Kmeans高效算法[J]. 电子科技, 2014, 27(2): 29-31. ZHAO Qing. Efficient algorithm of Canopy-Kmeans based on Hadoop platform[J]. Electronic science & technology, 2014, 27(2): 29-31. (0) [12] TENENBAUM J B, DE SILVA V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319-2323. DOI:10.1126/science.290.5500.2319 (0) [13] 孙岩.湿地植物高光谱特征分析与物种识别模型构建[D].北京: 清华大学, 2008. SUN Yan. Hyperspectral characters and species identification model for wetland plants[D]. Beijing: Tsinghua University, 2008. http://cdmd.cnki.com.cn/Article/CDMD-10003-2009083317.htm (0) [14] XIANG Shiming, NIE Feiping, ZHANG Changshui. Learning a mahalanobis distance metric for data clustering and classification[J]. Pattern recognition, 2008, 41(12): 3600-3612. DOI:10.1016/j.patcog.2008.05.018 (0) [15] KEERTHI S S, SHEVADE S K, BHATTACHARYYA C, et al. A fast iterative nearest point algorithm for support vector machine classifier design[J]. IEEE transactions on neural networks archive, 2000, 11(1): 124-136. (0) [16] MO Jiahui, KIANG M Y, ZOU Peng, et al. A two-stage clustering approach for multi-region segmentation[J]. Expert systems with applications, 2010, 37(10): 7120-7131. DOI:10.1016/j.eswa.2010.03.003 (0) [17] 李荟娆. K-means聚类方法的改进及其应用[D].哈尔滨: 东北农业大学, 2014. LI Huirao. Improved K-means clustering method and its application[D]. Harbin: Northeast Agricultural University, 2014. http://d.wanfangdata.com.cn/Thesis_Y2621098.aspx (0) [18] 张人.一种新的动态XML文档聚类方法[D].长春: 吉林大学, 2012. ZHANG Ren. A novel clustering method for dynamic XML documents[D]. Changchun: Jilin University, 2012. http://cdmd.cnki.com.cn/Article/CDMD-10183-1013118753.htm (0)