Li X, Yin H, Zhou K, et al. Semi-supervised clustering with deep metric learning and graph embedding[J]. World Wide Web, 2020, 23(2): 781-798.

摘要翻譯

聚類作為社交網(wǎng)絡(luò)中的一種常見技術(shù)，因其高性能而引起了廣泛的研究興趣，并提出了許多聚類方法。現(xiàn)有聚類方法是基于無(wú)監(jiān)督學(xué)習(xí)的。事實(shí)上，我們通?？梢栽趯?shí)際應(yīng)用中得到少數(shù)的標(biāo)記樣本。最近，人們提出了幾種半監(jiān)督聚類方法，盡管還有很多改進(jìn)的空間。本文的目標(biāo)是解決半監(jiān)督聚類過(guò)程中的兩個(gè)研究問(wèn)題：(i)如何學(xué)習(xí)更有鑒別性的特征以提升聚類過(guò)程的；(ii)如何有效地利用已標(biāo)記的數(shù)據(jù)和未標(biāo)記的數(shù)據(jù)來(lái)提高聚類的性能。為了解決這兩個(gè)問(wèn)題，論文提出了一種新的基于深度度量學(xué)習(xí)(SCDML)的半監(jiān)督聚類方法，它以一種新的方法有效地利用了深度度量學(xué)習(xí)和半監(jiān)督學(xué)習(xí)。為了使提取的數(shù)據(jù)貢獻(xiàn)特征更具有代表性，標(biāo)簽傳播網(wǎng)絡(luò)更適合實(shí)際應(yīng)用，論文在深度度量學(xué)習(xí)網(wǎng)絡(luò)中采用 triplet loss，并將bedding？與標(biāo)簽傳播策略相結(jié)合，動(dòng)態(tài)地將未標(biāo)簽數(shù)據(jù)更新為已標(biāo)簽數(shù)據(jù)，進(jìn)一步改進(jìn)了聚類，稱為 semi-supervised clustering with deep metric learning and graph embedding (SCDMLGE)。SCDMLGE增強(qiáng)了度量學(xué)習(xí)網(wǎng)絡(luò)的魯棒性，提高了聚類的準(zhǔn)確性。在多個(gè)基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)，說(shuō)明了模型的有效性。

聚類歸納

The unsupervised clustering technique has drawn a tremendous amount
of research attention, and many clustering methods have been proposed in the past.

這些聚類方法通常可以分為三種類型：

• 基于特征學(xué)習(xí)的方法。該方法試圖通過(guò)結(jié)合數(shù)據(jù)降維技術(shù)或子空間學(xué)習(xí)技術(shù)來(lái)尋找更具有區(qū)分性的特征。
• 基于度量學(xué)習(xí)的方法。此方法旨在學(xué)習(xí)訓(xùn)練數(shù)據(jù)的一個(gè)適當(dāng)?shù)木嚯x度量。在學(xué)習(xí)的距離度量下，它可以將相似的樣本組合在一起并同時(shí)將不相似的樣本分離。
• 基于圖的聚類。這種方法根據(jù)數(shù)據(jù)的成對(duì)相似性將數(shù)據(jù)劃分為不同的類簇。

semi-supervised clustering with deep metric learning框架

SCDML--可以利用深度度量學(xué)習(xí)模型提取可判別的特征，同時(shí)，通過(guò)KNN標(biāo)簽更新策略優(yōu)化聚類結(jié)果，動(dòng)態(tài)增加標(biāo)記數(shù)據(jù)集，然后進(jìn)一步提升度量學(xué)習(xí)網(wǎng)絡(luò)的性能。

圖（a）展示了現(xiàn)有的半監(jiān)督的固定輸入聚類模型訓(xùn)練網(wǎng)絡(luò)模型，而在論文的網(wǎng)絡(luò)模型中，該模型通過(guò)增量地不斷更新標(biāo)記數(shù)據(jù)，如圖（b）所示。

該框架貢獻(xiàn)點(diǎn)總結(jié)

• 設(shè)計(jì)了一種新的半監(jiān)督聚類模型，其中包括一個(gè)半監(jiān)督深度度量學(xué)習(xí)子網(wǎng)和一個(gè)標(biāo)簽傳播子網(wǎng)。

SCDML

• 在深度度量學(xué)習(xí)子網(wǎng)中，通過(guò)使用Siamese CNNs來(lái)抽取可判別的特征來(lái)最小化聚類誤差。
• 在標(biāo)簽傳播子網(wǎng)中，通過(guò)KNN標(biāo)記更新策略將無(wú)標(biāo)記數(shù)據(jù)轉(zhuǎn)換為有標(biāo)記數(shù)據(jù)。并以此增強(qiáng)深度度量學(xué)習(xí)子網(wǎng)的性能。

（1） semi-supervised deep metric learning network

step 1: 將已標(biāo)記的樣本對(duì)輸入到Siamese CNNs，來(lái)抽取可識(shí)別的特征。該網(wǎng)絡(luò)的損失函數(shù)為對(duì)比損失:

contrastive loss

step 2: 然后通過(guò)訓(xùn)練好的度量學(xué)習(xí)網(wǎng)絡(luò)對(duì)所有數(shù)據(jù)，包括標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)進(jìn)行編碼，以獲得其對(duì)應(yīng)特征。
step 3: 最后，根據(jù)編碼特征對(duì)未標(biāo)記數(shù)據(jù)進(jìn)行分類，并將分類結(jié)果記錄為未標(biāo)記數(shù)據(jù)的標(biāo)簽。

（2） k-nearest neighbors label updating strategy

給定數(shù)據(jù)集，所有的數(shù)據(jù)屬于個(gè)類簇，每個(gè)類簇包含有限的標(biāo)記數(shù)據(jù)，大量的未標(biāo)記數(shù)據(jù)。為了充分利用未標(biāo)記數(shù)據(jù)的特性，我們每次將個(gè)新的未標(biāo)記數(shù)據(jù)添加到標(biāo)記數(shù)據(jù)集。KNN標(biāo)簽更新策略的主要流程如下。
step 1: 通過(guò)有標(biāo)簽的數(shù)據(jù)來(lái)計(jì)算每個(gè)類簇的中心：

step 2: 計(jì)算每個(gè)無(wú)標(biāo)簽數(shù)據(jù)到類簇中心的距離，并選擇top k樣本添加到有標(biāo)簽數(shù)據(jù)中：

在SCDML的(b)圖中的實(shí)點(diǎn)表示標(biāo)記數(shù)據(jù)，空心點(diǎn)表示未標(biāo)記數(shù)據(jù)。在找到每個(gè)類簇的標(biāo)記數(shù)據(jù)中心后，將距離該中心最近的未標(biāo)記樣本（top k）作為新的標(biāo)記數(shù)據(jù)。

隨著標(biāo)記數(shù)據(jù)數(shù)量的增加，度量模型可以學(xué)習(xí)更魯棒性和有鑒別性的特征，這將進(jìn)一步提高聚類的準(zhǔn)確性。

Improved semi-supervised clustering with deep metric learning

進(jìn)一步作者考慮到：(i)度量函數(shù)的選擇會(huì)影響數(shù)據(jù)特征提取的準(zhǔn)確性，進(jìn)而影響聚類結(jié)果的準(zhǔn)確性; (ii)在實(shí)際應(yīng)用中，由于每個(gè)簇的密度、被標(biāo)記數(shù)據(jù)的數(shù)量以及它們?cè)诿總€(gè)簇中的分布不同，KNN標(biāo)簽更新策略不是很適用。
由此進(jìn)行了兩個(gè)方面的改進(jìn)：(i)將triplet CNNs作為度量學(xué)習(xí)模型，并以triplet loss作為模型的損失來(lái)訓(xùn)練網(wǎng)絡(luò)。(ii)設(shè)計(jì)了一個(gè)更合理的標(biāo)簽傳播網(wǎng)絡(luò)，將未標(biāo)記數(shù)據(jù)動(dòng)態(tài)轉(zhuǎn)換為標(biāo)記數(shù)據(jù)。改進(jìn)后的總體框架如下圖所示：

SCDMLGE

（1） Semi-supervised deep metric learning and classification network

step 1: 用帶有標(biāo)記數(shù)據(jù)來(lái)訓(xùn)練網(wǎng)絡(luò)。首先，通過(guò) triplet CNNs提取可識(shí)別特征，然后利用特征訓(xùn)練分類器。為了同時(shí)學(xué)習(xí)特征提取和訓(xùn)練分類網(wǎng)絡(luò)，改論文設(shè)計(jì)了半監(jiān)督深度度量學(xué)習(xí)和分類網(wǎng)絡(luò)的損失函數(shù)如下：

L Loss

triplet loss

classification loss

（2）Semi-supervised clustering labeling propagation network

通過(guò)深度度量學(xué)習(xí)和分類網(wǎng)絡(luò)，可以獲得未標(biāo)記數(shù)據(jù)的標(biāo)簽，稱為弱標(biāo)簽。為了獲得未標(biāo)記數(shù)據(jù)的強(qiáng)標(biāo)簽，論文設(shè)計(jì)了一個(gè)半監(jiān)督的標(biāo)簽傳播網(wǎng)絡(luò)。它包括半監(jiān)督聚類和標(biāo)記傳播兩部分。

在半監(jiān)督聚類的過(guò)程中，提出了一種改進(jìn)的圖聚類算法。

• 首先構(gòu)造一個(gè)相似度矩陣。
  W
  其中，表示樣本點(diǎn)的鄰域?qū)挾?，?img class="math-inline" src="https://math.jianshu.com/math?formula=%CF%83" alt="σ" mathimg="1">越大，樣本點(diǎn)之間的相似性就越大。
  然后構(gòu)造度矩陣。
  D
  
  得到拉普拉斯矩陣。
  L
• 接下來(lái)，對(duì)拉普拉斯矩陣進(jìn)行矩陣分解（附：矩陣分解的意義）使用的top k特征向量（列向量）形成一個(gè)新的矩陣(k為特征向量的個(gè)數(shù)，N為特征向量的維數(shù))。然后，利用k-means聚類算法得到了聚類結(jié)果。(注：這里作者沒(méi)說(shuō)怎么用，我認(rèn)為形成的就是譜聚類中對(duì)應(yīng)的降維后的矩陣，原來(lái)的矩陣被轉(zhuǎn)換成的矩陣，然后利用k-means聚類)
• 最后利用聚類結(jié)果對(duì)無(wú)標(biāo)簽數(shù)據(jù)的CNN特征表示進(jìn)行標(biāo)記，是的聚類標(biāo)簽。(注：這里作者也沒(méi)說(shuō)聚類標(biāo)簽和分類標(biāo)簽的對(duì)應(yīng)，因?yàn)閷?duì)于分類標(biāo)簽來(lái)說(shuō)有明確的標(biāo)簽信息，而在聚類中只存在相似性。因此，我猜測(cè)可能是通過(guò)每個(gè)類簇中有標(biāo)簽數(shù)據(jù)的Tag來(lái)對(duì)類簇標(biāo)記進(jìn)行統(tǒng)一明確的？歡迎一起討論)

當(dāng)同時(shí)得到未標(biāo)記數(shù)據(jù)的分類標(biāo)簽和聚類標(biāo)簽時(shí)，由此進(jìn)行標(biāo)記傳播策略。

假設(shè)表示新增的強(qiáng)標(biāo)簽數(shù)據(jù)， 它可通過(guò)以下方式獲得：

ΔS

update data

完整的算法過(guò)程如下：

SCDMLGE

從deep metric learning角度來(lái)說(shuō)，在特征學(xué)習(xí)網(wǎng)絡(luò)部分并沒(méi)有改進(jìn)，只是同時(shí)引入了聚類算法和分類算法對(duì)數(shù)據(jù)的標(biāo)簽信息進(jìn)行了增強(qiáng)，并在標(biāo)簽傳播模塊使用了一種圖聚類方法（包括W的構(gòu)建和矩陣分解對(duì)應(yīng)的聚類），以數(shù)據(jù)更新的方式詮釋了半監(jiān)督聚類中有標(biāo)簽數(shù)據(jù)和無(wú)標(biāo)簽數(shù)據(jù)的重要性，并以有標(biāo)簽數(shù)據(jù)為指導(dǎo)，充分發(fā)揮隱藏在無(wú)標(biāo)簽數(shù)據(jù)中的特性，以提高聚類效果。