張陳歡，史燕中

(1.北京航天長峰科技工業(yè)集團(tuán)有限公司，北京 100039；2.中國航天科工集團(tuán)第二研究院，北京 100039；3.北京航天長峰股份有限公司，北京 100039)

0 引 言

在數(shù)據(jù)大爆炸的時代，人臉數(shù)據(jù)迅速增加。如何對人臉大數(shù)據(jù)進(jìn)行聚類，提取出有價值的信息，是目前亟需解決的問題。一般來說，人臉聚類效果的好壞主要取決于人臉特征的提取和聚類算法的選擇[1-2]。

人臉特征的提取既要保證具有高精度的可分性，又要盡可能降低特征值的維度，保證分類的效率。隨著深度學(xué)習(xí)的發(fā)展，卷積神經(jīng)網(wǎng)絡(luò)由于其深層的結(jié)構(gòu)、強(qiáng)大的學(xué)習(xí)能力和分層的非線性映射，成為人臉特征提取的主流方法[3]。

聚類的本質(zhì)是將數(shù)據(jù)按其特征進(jìn)行分組，使得組內(nèi)數(shù)據(jù)的相似度盡可能大，組間數(shù)據(jù)相似度盡可能小。K-means[4]是較為經(jīng)典同時也是應(yīng)用最為廣泛的聚類算法，但是需要預(yù)先設(shè)定分類數(shù)量K，而K的設(shè)定需要對數(shù)據(jù)集有一定的認(rèn)識。與K-means算法不同，Chinese Whispers[5]算法不需要預(yù)先設(shè)定類別數(shù)量，是一種可以自動查找類別個數(shù)的高效圖形聚類算法，在自然語言處理和人臉聚類應(yīng)用廣泛[6]。但該算法也存在一定的弊端，主要有：第一，聚類結(jié)果會受到相似度門限值的影響；第二，算法在類別數(shù)較多的情況下，可能會有較差的結(jié)果，即類別越多，當(dāng)前空間下的特征向量區(qū)分性越差；第三，對于小的圖形，算法的隨機(jī)性較大；第四，算法相似度矩陣計算的時間復(fù)雜度為O(n2)，對于大規(guī)模的人臉聚類，該算法聚類速度緩慢。

針對Chinese Whispers算法存在的不足，在Chinese Whispers算法的基礎(chǔ)上，文中提出一種對人臉增量數(shù)據(jù)用代表點(diǎn)[7]的算法進(jìn)行處理的人臉動態(tài)聚類方法。該方法保持了Chinese Whispers算法對于一定規(guī)模數(shù)據(jù)聚類的快速有效性，利用類中心作為代表點(diǎn)來描述類別信息，每次對一定規(guī)模的增量數(shù)據(jù)進(jìn)行初步聚類選出代表點(diǎn)，然后對這些代表點(diǎn)和已有數(shù)據(jù)的代表點(diǎn)進(jìn)行再聚類，在保證聚類精度的基礎(chǔ)上用可能少的數(shù)據(jù)完成聚類更新，從而達(dá)到提升時間效率的目的。

1 相關(guān)知識

1.1 相關(guān)定義

假設(shè)A={ai|ai∈Rm,i=1,2,…,n}為包含n個數(shù)據(jù)的數(shù)據(jù)集，其中每個數(shù)據(jù)為m維向量，Ci(i=1,2,…,k)表示k個類別，c(C1)，c(C2)，…，c(Ck)分別表示k個聚類中心。有如下定義：

定義1：設(shè)向量ai=(ai1,ai2,…,aim)和向量aj=(aj1,aj2,…,ajm)分別表示兩個m維的數(shù)據(jù)對象，它們之間的余弦距離定義為：

(1)

定義2：設(shè)相似度門限值為threshold，數(shù)據(jù)ai、aj通過一定的相似度規(guī)則計算后得到的相似度值為S(ai,aj)，若S(ai,aj)>threshold，則認(rèn)為數(shù)據(jù)ai、aj是相似的，否則不相似。

假設(shè)TP(Ture Positive)表示同一類的數(shù)據(jù)被分到同一簇的數(shù)目，TN(Ture Negative)表示不同類的數(shù)據(jù)被分到不同簇的數(shù)目，F(xiàn)P(False Positive)表示不同類的數(shù)據(jù)被分到同一簇的數(shù)目，F(xiàn)N(False Negative)表示同一類的數(shù)據(jù)被分到不同簇的數(shù)目。有如下定義：

定義3：準(zhǔn)確率(Precision)為：

(2)

定義4：召回率(Recall)為：

(3)

定義5：F-measure指標(biāo)為：

(4)

1.2 Chinese Whispers算法

Chinese Whispers(簡稱CW)是一種比較簡單的無監(jiān)督的分類方法，描述如下：

步驟1：構(gòu)建無向圖。對于每一個節(jié)點(diǎn)ai，都賦值一個初始的類class(ai)=i；計算不同節(jié)點(diǎn)之間的相似度，若大于相似度門限值threshold，則形成關(guān)聯(lián)邊，權(quán)重為相似度；

步驟2：迭代。隨機(jī)選取一個節(jié)點(diǎn)ai，若鄰居中有多個節(jié)點(diǎn)屬于同一類，則將這些節(jié)點(diǎn)權(quán)重相加；選取該節(jié)點(diǎn)下的所有鄰居節(jié)點(diǎn)權(quán)重最大的類別j作為當(dāng)前節(jié)點(diǎn)的類別；

步驟3：當(dāng)所有節(jié)點(diǎn)都完成后，就完成了一次迭代，重復(fù)步驟2，直到達(dá)到迭代次數(shù)；

步驟4：算法結(jié)束，得到k個簇。

1.3 Chinese Whispers算法的優(yōu)缺點(diǎn)

在網(wǎng)絡(luò)具有小世界特性的情況下，用CW算法進(jìn)行聚類具有如下優(yōu)點(diǎn)：第一，CW算法不需要預(yù)先設(shè)定聚類類簇的數(shù)目，可以自動查找類別個數(shù)，更適用于復(fù)雜環(huán)境下的聚類情況；第二，CW算法對于小世界網(wǎng)絡(luò)聚類的時間復(fù)雜度為O(n)，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，算法的處理時間呈線性增長，算法的效率較高；第三，CW算法適用于處理大小不同、分布不均勻的類群，算法的可伸縮性較好；第四，CW算法的收斂速度很快，尤其對于加權(quán)圖，只需要幾次迭代就能達(dá)到穩(wěn)定的狀態(tài)。

當(dāng)然，CW算法也存在一些不足之處：第一，該算法在節(jié)點(diǎn)數(shù)較小的情況下具有不確定性，產(chǎn)生的聚類結(jié)果往往存在顯著性差異，這是因?yàn)樵谛【W(wǎng)絡(luò)中，迭代過程從哪個節(jié)點(diǎn)開始更重要，而在大網(wǎng)絡(luò)中，起點(diǎn)的相關(guān)性消失了，因此CW算法適用于大網(wǎng)絡(luò)的聚類；第二，在真實(shí)情況下，小世界網(wǎng)絡(luò)中邊的權(quán)重是未知的，需要根據(jù)一定規(guī)則計算得到，如人臉聚類，由于構(gòu)建小世界圖的鄰接矩陣的需要計算不同節(jié)點(diǎn)之間的相似度，其時間復(fù)雜度為O(n2)，因而導(dǎo)致聚類速度緩慢；第三，聚類結(jié)果會受到相似度門限值的影響；第四，算法在類別數(shù)較多的情況下，可能會有較差的結(jié)果，即類別越多，當(dāng)前空間下的特征向量區(qū)分性越差，因此將該算法應(yīng)用于類別數(shù)較多的情況，需要提取高區(qū)分性的特征向量。

2 Chinese Whispers動態(tài)聚類算法

文中提出的Chinese Whispers動態(tài)聚類算法，針對1.3節(jié)的優(yōu)缺點(diǎn)，對于大規(guī)模數(shù)據(jù)的聚類，提出兩點(diǎn)優(yōu)化原則：

(1)將數(shù)據(jù)集按照適合Chinese Whispers算法的數(shù)據(jù)規(guī)模P進(jìn)行分塊聚類，即每次從數(shù)據(jù)集選取數(shù)據(jù)規(guī)模為P的數(shù)據(jù)集進(jìn)行聚類，好的P值既可以保證聚類結(jié)果的穩(wěn)定性，又可以保證聚類算法的性能。

(2)使用代表點(diǎn)算法在有新增數(shù)據(jù)時快速完成聚類更新。其核心在于用相對較少的數(shù)據(jù)點(diǎn)來描述數(shù)據(jù)集的特點(diǎn)，對于新增數(shù)據(jù)和原有數(shù)據(jù)分別利用代表類簇的代表點(diǎn)進(jìn)行聚類，并根據(jù)聚類結(jié)果進(jìn)行類別合并從而完成聚類更新，減少每次參與聚類的數(shù)據(jù)量，提高聚類效率。

算法流程如圖1所示。

圖1 改進(jìn)的Chinese Whispers算法流程

其步驟可總結(jié)如下：

(1)確定相似度門限threshold值，迭代次數(shù)和P值；

(2)從數(shù)據(jù)集中選取P個數(shù)據(jù)進(jìn)行Chinese Whispers聚類；

(3)將新產(chǎn)生的類中心與已有的類中心進(jìn)行Chinese Whispers聚類；

(4)合并類中心被聚為一類的類；

(5)從數(shù)據(jù)集中刪除已經(jīng)進(jìn)行聚類的P個數(shù)據(jù)；

(6)若數(shù)據(jù)集非空，跳轉(zhuǎn)至步驟2，否則結(jié)束。

3 實(shí)驗(yàn)測試

3.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用的人臉數(shù)據(jù)集分別為MS-celeb-1M[8]、LFW[9]、VGGFace2[10]和CASIA-Webface[11]。MS_celeb-1M是微軟公司發(fā)布的百萬級人臉數(shù)據(jù)集，也是目前公開人臉數(shù)據(jù)集中人臉圖片數(shù)量最多的數(shù)據(jù)集，包含100 000個ID超過10M張圖片。因此，文中采用該數(shù)據(jù)集作為人臉特征提取網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)；LFW是目前較主流的人臉驗(yàn)證測試評估數(shù)據(jù)集，包含5 749個ID超過13K張圖片；VGGFace2是從谷歌下載的大規(guī)模人臉數(shù)據(jù)集，包含9 131個ID超過3.31M張圖片；CASIA-Webface是中科院整理發(fā)布的大規(guī)模人臉數(shù)據(jù)集，包含10 575個ID超過494K張圖片。

對于MS-celeb-1M，由于數(shù)據(jù)集噪聲較大，存在一些錯誤樣本，文中采用Wu X[12]提出的方法進(jìn)行數(shù)據(jù)清洗；對于LFW，由于數(shù)據(jù)集數(shù)據(jù)分布不均勻，文中只選用每人2張以上圖像的數(shù)據(jù)集；對于VGGFace2和CASIA-Webface，數(shù)據(jù)規(guī)模較大，由于實(shí)驗(yàn)設(shè)備的限制，文中只選用人均圖片數(shù)較多的部分?jǐn)?shù)據(jù)進(jìn)行聚類實(shí)驗(yàn)。具體數(shù)據(jù)見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

數(shù)據(jù)集樣本數(shù)/個類別數(shù)/個人均圖片數(shù)MS-celeb-1M5 049 82479 077≈64LFW7 606901≈8VGGFace2180 826325≈556CASIA-Webface187 266980≈191

3.2 特征提取模型

為了提取有效的人臉特征，文中采用目前實(shí)驗(yàn)結(jié)果較好的CNN+ArcFace Loss[13]方法進(jìn)行特征提取，具體步驟如下：

(1)采用MTCNN[14]進(jìn)行人臉檢測和人臉對齊；

(2)采用ResNet[15]網(wǎng)絡(luò)框架結(jié)構(gòu)和MS-celeb-1M數(shù)據(jù)集進(jìn)行模型訓(xùn)練，輸出的特征向量維度為512。

3.3 相關(guān)參數(shù)的確定

通過對不同規(guī)模(100,200,…,2 000)的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)P值為1 000時，Chinese Whispers算法的聚類結(jié)果開始趨于穩(wěn)定，非確定性消失，且算法性能較好。

文中采用CNN+ArcFace Loss方法提取的特征向量(512維)的余弦距離作為數(shù)據(jù)的相似性度量值，通過逐個比較不同的相似性門限值以及迭代次數(shù)的聚類結(jié)果，進(jìn)而得到最優(yōu)的相似性門限值和迭代次數(shù)。

3.4 F-measure指標(biāo)

在聚類評價中，聚類的準(zhǔn)確率指的是某一類別的數(shù)目與該簇總樣本數(shù)目的比率(式2)，衡量的是聚類結(jié)果的查準(zhǔn)率。聚類的召回率指的是某一類別的數(shù)目與該類別樣本總數(shù)的比率(式3)，衡量的是聚類結(jié)果的查全率。精度和召回率兩者越接近于1，說明聚類效果越好，但實(shí)際上隨著樣本規(guī)模的增大，兩者具有一定的互斥性，即精度高時，召回率低，召回率高時，精度低。F-measure是綜合精度和召回率的評價指標(biāo)(式4)，反映了整體的聚類質(zhì)量。當(dāng)F-measure值越接近于1，說明相應(yīng)的聚類方法越有效。

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

由于LFW數(shù)據(jù)集較小，P值設(shè)為1 000，VGGFace2、CASIA-Webface數(shù)據(jù)集較大，P值設(shè)為2 000；threshold分別為0.49、0.40、0.40；迭代次數(shù)為8時，聚類結(jié)果趨于穩(wěn)定。

分別對不同的數(shù)據(jù)集特征向量采用Chinese Whispers算法和改進(jìn)的Chinese Whispers動態(tài)聚類算法進(jìn)行聚類，并從F-measure值和時間效率兩個方面進(jìn)行評估。實(shí)驗(yàn)結(jié)果見圖2、圖3和表2。

圖2 不同聚類方法的時間

由圖2可以看出，隨著數(shù)據(jù)規(guī)模的增大，Chinese Whispers算法的聚類時間呈平方增長趨勢，改進(jìn)的Chinese Whispers動態(tài)聚類算法的聚類時間呈線性增長趨勢。

圖3 不同聚類方法的F-measure指標(biāo)

由圖3可以看出，對于不同規(guī)模的數(shù)據(jù)，Chinese Whispers動態(tài)聚類算法的F-measure指標(biāo)略低于Chinese Whispers算法的F-measure指標(biāo)，但相差不大。

表2 實(shí)驗(yàn)結(jié)果對比

由表2可見，Chinese Whispers動態(tài)聚類算法的F-measure值略低于Chinese Whispers 算法的F-measure值，但仍穩(wěn)定在90%以上，時間效率卻分別提高了4倍、65倍、29倍。說明改進(jìn)后的Chinese Whispers算法對于大規(guī)模數(shù)據(jù)有較好的聚類效果，且對于數(shù)據(jù)規(guī)模相近的數(shù)據(jù)集，類別數(shù)越少，聚類效果越好。

4 結(jié)束語

文中采用MTCNN進(jìn)行人臉檢測和對齊，采用CNN+ArcFace Loss方法進(jìn)行特征提取，通過對Chinese Whispers算法的改進(jìn)，提出一種大規(guī)模數(shù)據(jù)下的人臉動態(tài)聚類算法。在LFW、VGGFace2和CASIA-Webface三個公開人臉數(shù)據(jù)集上進(jìn)行測試，從F-measure和時間效率兩個方面進(jìn)行評估，結(jié)果表明在F-measure稍微下降的情況下，該算法大大提高了時間效率，實(shí)驗(yàn)總體效果有了較大提升，時間復(fù)雜度由原來的O(n2)變?yōu)镺(n*p)。因此，針對大規(guī)模人臉數(shù)據(jù)的聚類，該算法更為有效。但該算法也存在一定不足，即對類別數(shù)較多的數(shù)據(jù)集，時間提升效果不明顯。因此，下一步將著重研究對于類別較多的大規(guī)模數(shù)據(jù)集的有效聚類方法。