荀振宇 王衛(wèi)濤

摘 要 本文針對(duì)近鄰傳播聚類算法在高維圖像數(shù)據(jù)集上聚類效果不好的特點(diǎn)提出了HWAP算法。首先，通過HOG特征提取提取圖像的重要特征;然后，通過核函數(shù)映射計(jì)算出加權(quán)的相似度矩陣;最后，根據(jù)相似度矩陣計(jì)算出聚類結(jié)果。最終實(shí)驗(yàn)分析表明本文提出的HWAP算法在高維圖像數(shù)據(jù)集上具有良好的聚類效果。

關(guān)鍵詞 HOG特征提取;核函數(shù);權(quán)重;近鄰傳播

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上發(fā)表了Points Clustering by Passing Messages Between Data，系統(tǒng)闡述了近鄰傳播聚類算（Affinity Propagation， AP）的原理和應(yīng)用。近鄰傳播算法不需要事先設(shè)定聚類的個(gè)數(shù)，不需要初始化聚類中心點(diǎn)，是一種快速有效的聚類算法。但是在研究的過程中，發(fā)現(xiàn)近鄰傳播算法在處理高維圖像數(shù)據(jù)集時(shí)效果不好，而現(xiàn)實(shí)生活中的各種圖像數(shù)據(jù)是非常多見的，并且不具有一定的規(guī)律性，因此如何處理高維圖像的數(shù)據(jù)是一個(gè)需要討論的熱點(diǎn)。

本文針對(duì)上述提到的問題，提出了HWAP算法。首先，通過HOG特征提取出圖像的重要特征;然后，計(jì)算出通過核函數(shù)映射后的相似度矩陣，最終通過相似度矩陣計(jì)算出聚類結(jié)果。通過實(shí)驗(yàn)結(jié)果分析表明本文提出的HWAP算法在聚類高維圖像數(shù)據(jù)集時(shí)聚類良好的效果。

1近鄰傳播聚類算法（AP）

近鄰傳播聚類算法根據(jù)樣本點(diǎn)之間的相似度進(jìn)行迭代計(jì)算。其中計(jì)算相似度矩陣的公式如下：

（1）

該算法在計(jì)算過程中引入了歸屬度矩陣A和吸引度矩陣R。其中：， 。計(jì)算公式如下：

（2）

（3）

（4）

（5）

在計(jì)算歸屬度矩陣相似度矩陣過程中，引入了阻尼因子來增強(qiáng)算法的穩(wěn)定性，計(jì)算公式如下：

（6）

（7）

其中聚類目標(biāo)函數(shù)如下：

（8）

式中，為樣本點(diǎn)i的聚類中心點(diǎn)，是由組成的向量。計(jì)算公式如下：

（9）

迭代結(jié)束之后通過計(jì)算的值來確定聚類中心點(diǎn)，當(dāng)時(shí)，樣本點(diǎn)即為聚類中心點(diǎn)[1-9]。各個(gè)樣本點(diǎn)的聚類中心點(diǎn)的計(jì)算公式如下：

（10）

2HOG特征提取

（1）色彩和伽馬歸一化：

（11）

其中，為常量參數(shù);

（2）計(jì)算圖像梯度：

（12）

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

（3）構(gòu)建方向的直方圖：為圖像提供一個(gè)編碼，能夠保持對(duì)圖像外觀的敏銳性;

（4）將細(xì)胞單元合并成為較大的區(qū)間：把特征向量組合起來，形成每一個(gè)block的HOG特征;

（5）收集HOG特征：將所有重疊的塊進(jìn)行特征收集。

3HWAP算法

3.1 算法原理及步驟

將第2節(jié)計(jì)算出的特征值H[10-15]作為聚類算法的輸入，然后計(jì)算出樣本點(diǎn)之間的相似度S，，

其中，，

。式中，指數(shù)是核函數(shù)的調(diào)整因子，調(diào)整其映射空間的范圍。其中，，均為系數(shù)，取值范圍為。

在計(jì)算相似度矩陣S后，然后根據(jù)第1節(jié)中介紹的計(jì)算步驟去計(jì)算出最終的聚類結(jié)果。

4實(shí)驗(yàn)結(jié)果與分析

4.1 數(shù)據(jù)集介紹

4.2 評(píng)價(jià)指標(biāo)

為了更加客觀的反映聚類算法的優(yōu)劣，本文選取F-Measure作為算法的評(píng)價(jià)指標(biāo)。計(jì)算公式如下：

（13）

其中，，。是指被聚在一起的兩個(gè)樣本點(diǎn)被正確分類的個(gè)數(shù)，是指不該被放在一起的樣本點(diǎn)而被聚在一起的個(gè)數(shù)，不該分開的樣本點(diǎn)而被錯(cuò)誤的分開的個(gè)數(shù)。

4.3 結(jié)果對(duì)比分析

本節(jié)從準(zhǔn)確率、聚類類數(shù)等角度做了分析。對(duì)比算法有AP、PAP[16]兩種算法，其中，PAP算法是通過PCA提取特征后進(jìn)行聚類。對(duì)比結(jié)果見表2：

首先，從聚類準(zhǔn)確率的角度分析，AP算法在三個(gè)數(shù)據(jù)庫上效果較差，PAP算法再ORL以及JAFFE數(shù)據(jù)庫上效果相對(duì)AP算法較優(yōu)，而本文提出的HWAP算法在三個(gè)數(shù)據(jù)庫上效果均最優(yōu)。

其次，從類數(shù)的角度分析，AP算法聚類的類數(shù)均與原始數(shù)據(jù)庫相差較遠(yuǎn)， PAP算法在其中兩個(gè)數(shù)據(jù)庫中聚類準(zhǔn)確。本文提出的HWAP算法的聚類結(jié)果類數(shù)與原始類數(shù)都相同。

最后，綜合上述對(duì)比分析，HWAP算法在聚類準(zhǔn)確率以及聚類類數(shù)都是最優(yōu)的，因此本文改進(jìn)的算法在這些數(shù)據(jù)集上具有良好的適用性。

5結(jié)束語

本文介紹了近鄰傳播（AP）的原理與步驟，同時(shí)介紹了多重集核典型相關(guān)分析的原理及步驟，然后通過HOG特征提取出重要特征，作為近鄰傳播聚類算法的輸入，然后通過核函數(shù)計(jì)算出加權(quán)的相似度矩陣，最終根據(jù)相似度矩陣計(jì)算出聚類結(jié)果。最終通過在三個(gè)人臉數(shù)據(jù)庫上的實(shí)驗(yàn)對(duì)比分析，本文提出的HWAP算法具有良好的適用性。

參考文獻(xiàn)

[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.

作者簡(jiǎn)介

荀振宇，碩士，主研領(lǐng)域：數(shù)據(jù)挖掘，人工智能。

王衛(wèi)濤，碩士，主研領(lǐng)域：數(shù)據(jù)挖掘，人工智能。