基于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.

作者簡介

荀振宇，碩士，主研領域：數據挖掘，人工智能。

王衛濤，碩士，主研領域：數據挖掘，人工智能。