基于Chinese Whispers的人臉動(dòng)態(tài)聚類(lèi)

張陳歡，史燕中

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

0 引 言

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

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

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

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

1 相關(guān)知識(shí)

1.1 相關(guān)定義

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

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

(1)

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

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

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

(2)

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

(3)

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

(4)

1.2 Chinese Whispers算法

Chinese Whispers(簡(jiǎn)稱(chēng)CW)是一種比較簡(jiǎn)單的無(wú)監(jiān)督的分類(lèi)方法，描述如下：

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

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

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

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

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

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

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

2 Chinese Whispers動(dòng)態(tài)聚類(lèi)算法

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

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

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

算法流程如圖1所示。

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

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

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

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

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

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

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

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

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

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ā)布的百萬(wàn)級(jí)人臉數(shù)據(jù)集，也是目前公開(kāi)人臉數(shù)據(jù)集中人臉圖片數(shù)量最多的數(shù)據(jù)集，包含100 000個(gè)ID超過(guò)10M張圖片。因此，文中采用該數(shù)據(jù)集作為人臉特征提取網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)；LFW是目前較主流的人臉驗(yàn)證測(cè)試評(píng)估數(shù)據(jù)集，包含5 749個(gè)ID超過(guò)13K張圖片；VGGFace2是從谷歌下載的大規(guī)模人臉數(shù)據(jù)集，包含9 131個(gè)ID超過(guò)3.31M張圖片；CASIA-Webface是中科院整理發(fā)布的大規(guī)模人臉數(shù)據(jù)集，包含10 575個(gè)ID超過(guò)494K張圖片。

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

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

數(shù)據(jù)集樣本數(shù)/個(gè)類(lèi)別數(shù)/個(gè)人均圖片數(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)行人臉檢測(cè)和人臉對(duì)齊；

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

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

3.4 F-measure指標(biāo)

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

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時(shí)，聚類(lèi)結(jié)果趨于穩(wěn)定。

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

圖2 不同聚類(lèi)方法的時(shí)間

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

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

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

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

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

4 結(jié)束語(yǔ)

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