荀振宇 王衛(wèi)濤

摘 要 本文針對近鄰傳播聚類算法在高維圖像數(shù)據(jù)集上聚類效果不好的特點提出了HWAP算法。首先，通過HOG特征提取提取圖像的重要特征;然后，通過核函數(shù)映射計算出加權(quán)的相似度矩陣;最后，根據(jù)相似度矩陣計算出聚類結(jié)果。最終實驗分析表明本文提出的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è)定聚類的個數(shù)，不需要初始化聚類中心點，是一種快速有效的聚類算法。但是在研究的過程中，發(fā)現(xiàn)近鄰傳播算法在處理高維圖像數(shù)據(jù)集時效果不好，而現(xiàn)實生活中的各種圖像數(shù)據(jù)是非常多見的，并且不具有一定的規(guī)律性，因此如何處理高維圖像的數(shù)據(jù)是一個需要討論的熱點。

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

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

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

（1）

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

（2）

（3）

（4）

（5）

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

（6）

（7）

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

（8）

式中，為樣本點i的聚類中心點，是由組成的向量。計算公式如下：

（9）

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

（10）

2HOG特征提取

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

（11）

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

（2）計算圖像梯度：

（12）

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

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

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

（5）收集HOG特征：將所有重疊的塊進行特征收集。

3HWAP算法

3.1 算法原理及步驟

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

其中，，

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

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

4實驗結(jié)果與分析

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

4.2 評價指標(biāo)

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

（13）

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

4.3 結(jié)果對比分析

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

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

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

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

5結(jié)束語

本文介紹了近鄰傳播（AP）的原理與步驟，同時介紹了多重集核典型相關(guān)分析的原理及步驟，然后通過HOG特征提取出重要特征，作為近鄰傳播聚類算法的輸入，然后通過核函數(shù)計算出加權(quán)的相似度矩陣，最終根據(jù)相似度矩陣計算出聚類結(jié)果。最終通過在三個人臉數(shù)據(jù)庫上的實驗對比分析，本文提出的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.

作者簡介

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

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