基于HOG特征提取的近邻传播聚类算法

荀振宇 王卫涛

摘 要 本文针对近邻传播聚类算法在高维图像数据集上聚类效果不好的特点提出了HWAP算法。首先，通过HOG特征提取提取图像的重要特征;然后，通过核函数映射计算出加权的相似度矩阵;最后，根据相似度矩阵计算出聚类结果。最终实验分析表明本文提出的HWAP算法在高维图像数据集上具有良好的聚类效果。

关键词 HOG特征提取;核函数;权重;近邻传播

Affinity Propagation clustering algorithm Based On Canonical Correlation Analysis

Xun Zhenyu1  Wang Weitao2

1. The First Military Representative Office of the Maritime Equipment Shenyang Bureau in Dalian， Dalian 116000，Liaoning，China

2. 713th Research Institute China Ship Building Industry Corporation， Zhengzhou 116000，Henan，China

Abstract This paper proposes the HWAP algorithm based on the feature that the Affinity propagation cluster-ing algorithm does not perform well on high-dimensional image dataset. First， Extract important features of an image through HOG feature extraction; Second， A weighted similarity matrix is calculated through the kernel function mapping; Last， Calculate the clustering result based on the similarity matrix. Finally， The experi-mental results show that the HWAP algorithm proposed in this paper has a good effect on high-dimensional image datasets.

Key word HOG; Kernel function; Weights; Affinity propagation

引言

2007年Frey和Dueck在Science上发表了Points Clustering by Passing Messages Between Data，系统阐述了近邻传播聚类算（Affinity Propagation， AP）的原理和应用。近邻传播算法不需要事先设定聚类的个数，不需要初始化聚类中心点，是一种快速有效的聚类算法。但是在研究的过程中，发现近邻传播算法在处理高维图像数据集时效果不好，而现实生活中的各种图像数据是非常多见的，并且不具有一定的规律性，因此如何处理高维图像的数据是一个需要讨论的热点。

本文针对上述提到的问题，提出了HWAP算法。首先，通过HOG特征提取出图像的重要特征;然后，计算出通过核函数映射后的相似度矩阵，最终通过相似度矩阵计算出聚类结果。通过实验结果分析表明本文提出的HWAP算法在聚类高维图像数据集时聚类良好的效果。

1近邻传播聚类算法（AP）

近邻传播聚类算法根据样本点之间的相似度进行迭代计算。其中计算相似度矩阵的公式如下：

（1）

该算法在计算过程中引入了归属度矩阵A和吸引度矩阵R。其中：， 。计算公式如下：

（2）

（3）

（4）

（5）

在计算归属度矩阵相似度矩阵过程中，引入了阻尼因子来增强算法的稳定性，计算公式如下：

（6）

（7）

其中聚类目标函数如下：

（8）

式中，为样本点i的聚类中心点，是由组成的向量。计算公式如下：

（9）

迭代结束之后通过计算的值来确定聚类中心点，当时，样本点即為聚类中心点[1-9]。各个样本点的聚类中心点的计算公式如下：

（10）

2HOG特征提取

（1）色彩和伽马归一化：

（11）

其中，为常量参数;

（2）计算图像梯度：

（12）

其中，为水平方向梯度，为垂直方向梯度，为像素值，为梯度幅值，为梯度方向;

（3）构建方向的直方图：为图像提供一个编码，能够保持对图像外观的敏锐性;

（4）将细胞单元合并成为较大的区间：把特征向量组合起来，形成每一个block的HOG特征;

（5）收集HOG特征：将所有重叠的块进行特征收集。

3HWAP算法

3.1 算法原理及步骤

将第2节计算出的特征值H[10-15]作为聚类算法的输入，然后计算出样本点之间的相似度S，，

其中，，

。式中，指数是核函数的调整因子，调整其映射空间的范围。其中，，均为系数，取值范围为。

在计算相似度矩阵S后，然后根据第1节中介绍的计算步骤去计算出最终的聚类结果。

4實验结果与分析

4.1 数据集介绍

4.2 评价指标

为了更加客观的反映聚类算法的优劣，本文选取F-Measure作为算法的评价指标。计算公式如下：

（13）

其中，，。是指被聚在一起的两个样本点被正确分类的个数，是指不该被放在一起的样本点而被聚在一起的个数，不该分开的样本点而被错误的分开的个数。

4.3 结果对比分析

本节从准确率、聚类类数等角度做了分析。对比算法有AP、PAP[16]两种算法，其中，PAP算法是通过PCA提取特征后进行聚类。对比结果见表2：

首先，从聚类准确率的角度分析，AP算法在三个数据库上效果较差，PAP算法再ORL以及JAFFE数据库上效果相对AP算法较优，而本文提出的HWAP算法在三个数据库上效果均最优。

其次，从类数的角度分析，AP算法聚类的类数均与原始数据库相差较远， PAP算法在其中两个数据库中聚类准确。本文提出的HWAP算法的聚类结果类数与原始类数都相同。

最后，综合上述对比分析，HWAP算法在聚类准确率以及聚类类数都是最优的，因此本文改进的算法在这些数据集上具有良好的适用性。

5结束语

本文介绍了近邻传播（AP）的原理与步骤，同时介绍了多重集核典型相关分析的原理及步骤，然后通过HOG特征提取出重要特征，作为近邻传播聚类算法的输入，然后通过核函数计算出加权的相似度矩阵，最终根据相似度矩阵计算出聚类结果。最终通过在三个人脸数据库上的实验对比分析，本文提出的HWAP算法具有良好的适用性。

参考文献

[1] G Hongyu. Research on term weighting algorithm based on information entropy theory[J]. Computer Engineering & Applications，2013，49（10）：140-146.

[2] Hardoon D R，Szedmak S R，Shawe-Taylor J R. Canonical Correlation Analysis：An Overview with Application to Learning Methods[J]. Neural Computation，2004，16（12）：2639.

[3] Kalsum U，Nawi N M，Kasim S . Classify a Protein Domain Using Sigmoid Support Vector Machine[C].Icisa：International Conference on Information Science & Application. IEEE，2014：9-11.

[4] Prajapati G L，Patle A . On Performing Classification Using SVM with Radial Basis and Polynomial Kernel Functions[C].International Conference on Emerging Trends in Engineering & Technology. IEEE，2010：512-515.

[5] Gan G，Ng K P. Subspace clustering using affinity propagation[J]. Pattern Recognition，2015，48（4）：1455-1464.

[6] Jia H，Ding S，Meng L，et al. A density-adaptive affinity propagation clustering algorithm based on spectral dimension reduction[J]. Neural Computing & Applications，2014，25（7-8）：1557-1567.

[7] Zhang Xiaoqin，Zhao Chihang，Sha Yuejin，et al.Vehicle brand recognition based on HOG feature and support vector machine[J]. Journal of Southeast University（Natural Science Edition），2013，（S2）：107.

[8] HUANG Feifei，CAO Jiangtao，JI Xiaofei，et al. Research on Human Interaction Recognition Algorithm Based on Mixed Features[J]. Journal of Frontiers of Computer Science and Technology，2017，（2）：294-302.

[9] U Ang，ZHANG Yueqiang，YANG Xia，et al. Fast circle filter HOG for car detection from aerial images[J]. Journal of National University of Defense Technology，2017，（1）：137-141.

[10] Li Ming，Peng Xiujiao，Wang Yan. Facial Expression Recognition Based on Improved Dictionary Learning and Sparse Representation[J]. Journal of System Simulation，2018，（1）：141.

[11] WU Zhanjun，NIU Min，XU Bing，et al. Research on Recognition Method Based on Spectral Regression and Back Propagation Neural Network[J]. Journal of Electronics & Information Technology，2016，（4）：109.

[12] ZOU Bei-ji，GUO Jian-jing，ZHU Cheng-zhang，et al. Image classification based on BOW-HOG feature[J].Journal of Zhejiang University（Engineering Science），2017，（12）：39.

[13] SUN Rui，WANG Jing-Jing. A Vehicle Recognition Method Based on Kernel K-SVD and Sparse Representation[J]. Pattern Recognition and Artificial Intelligence，2014，（5）：435-442.

[14] Tang Yongbo，Xiong Yinguo. Transformer Fault Diagnosis Based on Feature Extraction of Relative Transformation Principal Component Analysis[J]. Journal of System Simulation，2018，（3）：18.

[15] Gu Yu，Xu Zongben，Sun Jian，et al. An Intrusion Detection Ensemble System Based on the Features Extracted by PCA and ICA[J].Journal of Computer Research and Development，2006，（4）：393.

[16] YUAN Ba，YAO Ping，ZHENG Tianyao. Radar Emitter Signal Identification Based on Weighted Normalized Singular-value Decomposition[J]. Journal of Radars，2019，（1）：51-57.

作者简介

荀振宇，碩士，主研领域：数据挖掘，人工智能。

王卫涛，硕士，主研领域：数据挖掘，人工智能。