軒書婷，劉驚雷

（煙臺大學計算機與控制工程學院，山東煙臺 264005）

0 引言

聚類是一種重要的數(shù)據(jù)分析技術(shù)，它將一個對象的集合分成不同的類從而描述數(shù)據(jù)。通過聚類，可以識別數(shù)據(jù)中稀疏和密集的區(qū)域，從而發(fā)現(xiàn)全局的模式以及數(shù)據(jù)之間的相互關(guān)系。它的目標是將具有相似結(jié)構(gòu)或模式的數(shù)據(jù)項分類到同一個組中，降低數(shù)據(jù)的復雜性并促進解釋。在計算機視覺［1-2］和數(shù)據(jù)挖掘領(lǐng)域［3-4］中，數(shù)據(jù)聚類是基礎(chǔ)研究課題，而且聚類分析也應用到了各個領(lǐng)域，包括模式識別、數(shù)據(jù)分析、圖像處理以及市場研究等。

聚類分析指將物理或抽象對象的集合分組為由類似的對象組成的多個類的分析過程。聚類分析的目標就是在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類源于很多領(lǐng)域，包括數(shù)學、計算機科學等。在不同的應用領(lǐng)域，很多聚類技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中。它可以作為其他算法的預處理步驟，利用聚類進行數(shù)據(jù)預處理，獲得數(shù)據(jù)的基本情況，并在此基礎(chǔ)上進行數(shù)據(jù)的抽取選擇以提高精確度和挖掘的效率。

傳統(tǒng)聚類方法是基于原始數(shù)據(jù)構(gòu)造的正規(guī)圖矩陣來構(gòu)造拉普拉斯矩陣的，主要是在數(shù)據(jù)空間進行聚類。限制聚類性能的原因有兩個：1）數(shù)據(jù)的多樣性和復雜分布，由于成對策略，普通的圖不能全面考慮數(shù)據(jù)的復雜相關(guān)性；2）原始數(shù)據(jù)通常具有冗余特征，這些冗余嚴重影響數(shù)據(jù)的分布。因此，由原始數(shù)據(jù)構(gòu)造的拉普拉斯矩陣不能輸出可靠的譜表示以及取得最佳的聚類性能。如今，隨著數(shù)據(jù)量史無前例的快速增長，高維數(shù)據(jù)在許多應用中無處不在，例如圖像處理。這對于像Facebook、Instagram 和谷歌這樣的照片分享網(wǎng)站的流行來說尤為重要。考慮到網(wǎng)上有海量的照片，如何有效地組織它們是一個有待解決的問題。數(shù)據(jù)都是從不同的數(shù)據(jù)源收集出來的，對于這一部分可視化的數(shù)據(jù)，數(shù)據(jù)量大，并且數(shù)據(jù)的維度多，導致對數(shù)據(jù)進行聚類成為一個挑戰(zhàn)性的問題。

Gong 等［5］開發(fā)了一種二進制聚類方法，該方法由生成二進制碼和二進制進行聚類兩個獨立階段組成，其主要缺點是二進制碼采用與數(shù)據(jù)無關(guān)的方法獲得，同時兩步聚類破壞了二進制碼與數(shù)據(jù)分割的關(guān)系。經(jīng)典聚類算法K-means 算法是一種典型的基于距離的算法，它以距離作為評價相似度的指標。兩個對象的距離越近，相似度越大。該算法需要不斷地對對象進行分類調(diào)整，不斷計算調(diào)整后新的聚類中心點，因此當數(shù)據(jù)量非常大時，算法的時間開銷非常大。

哈希方法以其查詢速度快、存儲成本低等優(yōu)勢，特別是基于學習的哈希，由于其驚人的存儲和搜索效率而受到了相當多的關(guān)注，已經(jīng)成為解決各種大規(guī)模計算機視覺和機器學習問題的流行工具，包括目標檢測、目標識別、聚類等。該方法的目標是將原始特征空間中的數(shù)據(jù)點投影后嵌入到漢明空間中，并在漢明空間中保持數(shù)據(jù)點之間的相似度。在漢明空間中，每個二進制碼表示一個數(shù)據(jù)點。計算二進制碼的漢明距離僅涉及的運算，使用短碼進行散列，計算速度快，所以將高維特征向量編碼為緊湊的二進制碼可以節(jié)省計算的時間，從而實現(xiàn)快速聚類。圖像聚類面臨的最大挑戰(zhàn)是速度和存儲問題，哈希方法不僅可以有效提高圖像聚類的效率，還可以在存儲和計算性能方面獲得顯著的提高。

為了解決上述問題，提出了一種基于離散哈希的聚類（Clustering based on Discrete Hashing，CDH）。圖1 顯示了所提方法的主要框架，主要工作如下：

圖1 所提方法的主要框架Fig.1 Main framework of proposed method

1）提出了一個基于離散哈希的聚類框架來解決圖像聚類問題。該框架將哈希碼學習和二元聚類放到一個聯(lián)合優(yōu)化目標中進行。與傳統(tǒng)聚類方法相比，所提方法是在對數(shù)據(jù)進行二進制編碼的同時，將轉(zhuǎn)換后的二進制編碼在漢明空間進行聚類（如式（10）所示）。

2）使用L21范數(shù)的自適應特征選擇特性，對輸入數(shù)據(jù)進行數(shù)據(jù)的自動特征選擇，通過多次迭代選擇原始數(shù)據(jù)中最有用的特征，從而完成數(shù)據(jù)的降維。即將原始數(shù)據(jù)空間的維度d維降到漢明空間的維度l(l?d)。

3）在低維、稀疏的漢明空間對降維后的數(shù)據(jù)進行低秩矩陣分解和譜嵌入，從而完成二值漢明空間中稀疏數(shù)據(jù)的快速聚類。

4）在基準數(shù)據(jù)集上進行實驗，與幾種經(jīng)典的聚類方法相比，在聚類精度、標準化互信息和純度指標上進行分析，CDH 在聚類性能上有提高，實驗結(jié)果證明了所提方法的優(yōu)越性。

1 相關(guān)定義及方法

1.1 相關(guān)符號

在本節(jié)中，首先介紹使用到的一些基本符號，隨后對所提方法所涉及的相關(guān)定義和概念進行簡單的介紹。

矩陣用大寫字母（例如C）表示，向量用小寫字母（例如c）表示。c.j為C的第j列，ci.為C的第i行，ci.j為C的第i行第j列上的元素。具體基本符號表示如表1 所示。

表1 基本符號Tab.1 Basic symbols

1.2 聚類分析

聚類分析是研究數(shù)據(jù)間邏輯上或物理上相互關(guān)系的技術(shù)，它通過一定的規(guī)則將數(shù)據(jù)集劃分為在性質(zhì)上相似的數(shù)據(jù)點構(gòu)成的若干個類。聚類的結(jié)果不僅可以揭示數(shù)據(jù)間的內(nèi)在聯(lián)系與區(qū)別，同時也為進一步的數(shù)據(jù)分析與知識的發(fā)現(xiàn)提供重要依據(jù)，如數(shù)據(jù)間的關(guān)聯(lián)規(guī)則以及數(shù)據(jù)的變化趨勢等。聚類分析常用于現(xiàn)實生活的不同領(lǐng)域或一些建設(shè)性目標［6］中。真實聚類的目標是揭示數(shù)據(jù)中固有的真實分組，例如系統(tǒng)發(fā)育分析和其他生命科學聚類應用程序在數(shù)據(jù)中尋找真正的分組，因此具有現(xiàn)實的目標。相比之下，無論是否存在固有的聚類結(jié)構(gòu)，當聚類應該發(fā)生時，結(jié)構(gòu)聚類都是相關(guān)的。然而，聚類的目標是建設(shè)性的，例如，雖然聚類分析在市場細分中的應用可能主要是建設(shè)性的，但是當數(shù)據(jù)中存在真實的群體時，用戶可能對這些群體感興趣。

聚類分析固有的模糊性使有效性要求變得復雜。算法對于給定的應用程序是否有效取決于該應用程序的需求［6］。對于高維的數(shù)據(jù)集，需要將數(shù)據(jù)的維度降低再進行聚類，這樣可以更好地提高聚類的效率。故將高維的數(shù)據(jù)空間聚類轉(zhuǎn)換到低維的漢明空間，在降維后的空間使用K-means 和譜聚類結(jié)合的聚類方式，使聚類效果更佳。

1.2.1 K-means聚類

K-means 算法的主要內(nèi)容是給定一組含有n個數(shù)據(jù)點的Y=｛y1，y2，…，yn｝在Rd中，并且給定一個整數(shù)k。它要解決的問題是隨機選取k個聚類質(zhì)心點在Rd中，以便使下面的錯誤函數(shù)最小化

K-means 算法有3 個步驟［7-8］：第1 步是為待聚類的點尋找聚類中心；第2 步是計算每個點到聚類中心的距離，將每個點聚類到離該點最近的聚類中心；第3 步是計算每個聚類中所有點的坐標平均值，并將這個平均值作為新的聚類中心。反復執(zhí)行第2、3 步，直到聚類中心不再進行大范圍的移動或者聚類次數(shù)達到要求，整個聚類過程則結(jié)束。

｛b1，b2，…，bn｝是B的列向量，｛μ1，μ2，…，μk｝為k個質(zhì)心，當?shù)趇個數(shù)據(jù)點分配給第j個簇(1≤j≤k)時，gi=j。對二進制矩陣B進行K-means 聚類的目標為：

1.2.2 譜聚類

譜聚類作為一種廣泛應用的基于圖的聚類方法，有著最先進的聚類性能。譜聚類算法的目標是利用捕捉數(shù)據(jù)非線性結(jié)構(gòu)的相似矩陣來尋找聚類隸屬度。譜聚類包括一個兩階段的過程，通過這個過程建立一個相似圖，然后利用幾個標準對圖進行劃分。

傳統(tǒng)的光譜聚類表示為：

其中矩陣S的每一項表示數(shù)據(jù)對（i，j）之間的相似性。對于傳統(tǒng)的光譜聚類，由于忽略了先驗信息，聚類性能在很大程度上取決于所構(gòu)建的親和圖的質(zhì)量。

譜聚類的優(yōu)點有：1）直接通過求解拉普拉斯矩陣的特征向量進行劃分，不含有凸球形數(shù)據(jù)分布的隱性假設(shè)，從而能夠識別非凸類型的簇；2）譜聚類僅與數(shù)據(jù)點的數(shù)目有關(guān)，與維數(shù)無關(guān)，因此可以避免高維特征向量造成的奇異性問題；3）能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)。

譜聚類的缺點有：1）譜聚類將原始數(shù)據(jù)空間映射到低維的線性測度空間，然后再線性測度空間中進行聚類，經(jīng)常選用傳統(tǒng)的K-means 算法進行聚類，從而導致算法具有初始值敏感的問題，將會影響聚類結(jié)果；2）譜聚類需要計算矩陣的特征值與特征向量，通常這種計算的代價很大，求解非稀疏矩陣的所有特征向量的標準解法需要O(n3)。當應用到大規(guī)模數(shù)據(jù)時，相似度矩陣也很大，可能會超出計算機的內(nèi)存。

CDH 所提出的二元聚類方法是在漢明空間中將K-means 與譜聚類聯(lián)合到一個框架中，滿足了各自的約束條件，在聚類精度和標準互信息指標上都有所提高。

1.2.3 LSC-K聚類

基于地標的K-means 光譜聚類簡稱為LSC-K（Landmarkbased Spectral Clustering using K-means）［9］。在稀疏編碼［10］和可伸縮半監(jiān)督學習［11］的啟發(fā)下，為解決大規(guī)模的問題提出了一種可伸縮的譜聚類方法——基于界標的譜聚類（Landmark-based Spectral Clustering，LSC）?；诮鐦说淖V聚類的基本思想是設(shè)計一種高效的圖構(gòu)造和拉普拉斯矩陣特征分解方法，而該LSC-K 聚類對比方法則是由LSC 衍生出來的一種聚類方式，它的缺點是運行時間比較慢。

1.2.4 CKM聚類

壓縮K-means 的簡稱為CKM（Compressed K-Means），用于快速大規(guī)模聚類。具體來說，高維數(shù)據(jù)被壓縮成適合快速聚類的短二進制碼。CKM 聚類方法有兩個主要的優(yōu)點：1）通過將數(shù)據(jù)點表示為二進制碼，可以顯著減少存儲；2）使用漢明度量進行二進制碼間的距離計算非常有效。

1.3 哈希碼學習

網(wǎng)絡(luò)上分享的圖片會出現(xiàn)維度較高等問題。雖然這些高維度的圖像包含的內(nèi)容較為豐富，但在進行聚類時往往存在噪聲、不精確和不完整等問題，導致在高維度圖像聚類中性能不理想，并且耗費的時間較長，所以要對哈希碼進行學習，在學習過程中進行自動特征選擇，選擇最有用的特征。

來自高維度圖像的標簽有兩個屬性：低秩和錯誤稀缺性［12-14］。作為文本信息的一種，圖像標簽也因此具有這種低秩屬性。此外，網(wǎng)絡(luò)上上傳的大量照片維度較高，在對照片進行組織時較為困難，有些照片的標簽提供得相當準確，注釋標簽的數(shù)量與標簽總數(shù)相比本質(zhì)上是稀疏的。因此，圖像的標簽矩陣的誤差是稀疏的。在此基礎(chǔ)上，通過將圖像的標簽矩陣分解為其低秩和稀疏分量，揭示了本征低秩矩陣。然后將低秩矩陣作為語義源進行語義增強，以增強學習到的哈希碼的識別能力。對于給定的圖像的標簽矩陣F，圖像標簽細化的目的是揭示理想的標簽矩陣G和標簽錯誤矩陣E。通過魯棒主成分分析（Robust Principal Component Analysis，RPCA）的研究［15］，可以將該問題表示為一個矩陣分解問題［16］。

其中λ1為正加權(quán)參數(shù)。

利用離散的方式來豐富哈希碼的語義，對哈希碼進行學習，進而對圖像進行聚類。為此，引入了標簽矩陣W，將哈希碼與通過特征選擇的圖像直接關(guān)聯(lián)，從而轉(zhuǎn)移到哈希碼中。其中，W定義為W=[w1，w2，…，wn]∈Rl×n，其中wk∈Rl×n是k位哈希碼的語義相關(guān)向量，目標是盡量減少二進制哈希碼和經(jīng)過特殊選擇的特征之間的差異。為了學習W，并給出了以下優(yōu)化的問題：

圖像哈希就是尋找漢明距離與語義相似度匹配的緊湊二進制碼。這表明語義上相似的圖像應該在較短的漢明距離內(nèi)映射到相似的二進制碼。為了有效地將圖像的語義相似性保存到二值哈希碼中，利用圖模型來解決這個問題。圖像之間的相關(guān)性可以簡單地用相似矩陣S表示。形式上，計算S的第i行第j列的元素（圖像i和圖像j之間的語義相似性）為：

其中：Nk(x)表示x的k個最近鄰的集合，通過局部縮放自動確定；(xj；)表示特征表示模型，Wˉ表示圖模型的參數(shù)集。為了保持圖像的相似性，尋求最小化加權(quán)漢明距離的總和：

其中L=diag(S1n)-S為圖的拉普拉斯矩陣。通過上述公式可以得到，如果兩個相似的圖像相距較遠，就會受到更大的影響。因此，相似的圖像可以被映射成漢明距離較短的哈希碼。

為了避免計算n×n矩陣S和L，將采用錨圖的方案，即：

這里Z∈Rn×m錨圖矩陣的相似性計算所有圖片和m錨點，并且Λ=diag(ZT1)，錨圖的構(gòu)建減少了離群點噪聲的影響，并且對數(shù)據(jù)的精細結(jié)構(gòu)進行了詳細的描述。

1.4 特征選擇

特征選擇［17-18］也稱特征子集選擇，是指從全部特征中選取一個特征子集，從原始數(shù)據(jù)特征中選擇最有用的特征，使構(gòu)造出來的模型更好。同時，在對特征選擇時會存在三種策略：單變量統(tǒng)計、基于模型的選擇以及迭代選擇。

特征選擇用到的方法是迭代選擇，構(gòu)建一系列的模型，每一個模型使用不同數(shù)量的特征。在特征投影過程中，目標是最大限度地減少原始數(shù)據(jù)的冗余［19］，因此通過約束條件PTXXTP=I（其中I表示n階的單位矩陣，若數(shù)據(jù)集的大小一致，則用I表示）進行特征學習，目的是使低維特征更具鑒別性。主要方法是在低維數(shù)據(jù)空間中尋找最優(yōu)的低秩重構(gòu)矩陣和將原始數(shù)據(jù)點投影到低維子空間的特征選擇投影矩陣。

1.5 二元聚類結(jié)構(gòu)學習

除了哈希二進制碼表示學習之外，還考慮到將哈希二進制碼進行方差約束之后，將這些二進制碼在漢明空間內(nèi)進行聚類［20］。由于傳統(tǒng)的K-means 聚類和矩陣分解的等價性，通過以下方式進行構(gòu)建哈希二進制碼結(jié)構(gòu)學習：

其中：C和G分別是聚類中心和標簽矩陣。為了產(chǎn)生高效的代碼使每一位的信息最大化，對聚類中心施加平衡約束。對聚類算法在每次迭代中的數(shù)據(jù)點的分配策略進行修改，達到對每個簇可包含的數(shù)據(jù)點數(shù)目上限進行約束的目的。同時，算法支持用戶自定義簇可包含的數(shù)據(jù)點數(shù)目的上限，滿足平衡約束聚類需求，使其適應二進制聚類任務(wù)。

2 離散哈希的聚類方法

在本章中，將介紹所提出的CDH 方法。首先，詳細描述了CDH 方法；然后，給出了CDH 的優(yōu)化算法。

2.1 CDH方法

本節(jié)主要研究基于離散哈希的聚類問題。使用離散哈希的方法對二進制碼進行重構(gòu)，選取數(shù)據(jù)中的最優(yōu)特征，完成對數(shù)據(jù)二進制碼的學習。將二進制碼對圖在漢明空間內(nèi)進行聚類時，有效提高聚類精度，提高聚類的性能是一個重要研究問題。離散哈希方法能夠優(yōu)化聚類過程中的信息損失，提高聚類精度以及減小存儲成本，將離散哈希方法和聚類算法表示集合到一個統(tǒng)一的框架，最終將其結(jié)合得到目標函數(shù)：

其中：B為哈希碼矩陣，C是聚類中心矩陣，L是圖的拉普拉斯矩陣，W為圖的映射矩陣，G為指標矩陣，α、β、γ、λ為正則化參數(shù)。

1）CDH 旨在將圖像投射到一個共同的漢明空間中，在投影過程中，為了解決區(qū)域位移的非線性問題，所以進一步將所提方法推廣到復制再生核希爾伯特空間（Reproducing Kernel Hilbert Space，RKHS）中基于核的非線性框架中，并建立了一個非線性的區(qū)域位移框架。令其中的Y=?(x) ∈Rm，R→{-1，1}l×n。

因此，公式第一部分中，輸入訓練數(shù)據(jù)集Y后，需要一個哈希函數(shù)來有效地將這一個新的訓練集Y編碼成為二進制代碼。采用簡單的線性哈希函數(shù)：

對訓練集進行轉(zhuǎn)換，轉(zhuǎn)換成計算機可識別的二進制代碼，這里可以通過可用的訓練數(shù)據(jù)和代碼求解一個線性回歸系統(tǒng)來進行學習。也就是可以通過式（13）解決。

對于拉普拉斯正則化項，約束在原始數(shù)據(jù)空間中非常接近的兩個數(shù)據(jù)點xi和xj，那么它們在投影的低維子空間中的映射和表示的系數(shù)也使相似的。

3）tr(WY)(WY)T表示對投影后的數(shù)據(jù)方差進行約束，方差表示兩個數(shù)據(jù)之間的相互關(guān)系，方差變大，二進制碼更分散，這樣就會更好地達到平衡位。這是二進制碼學習［22］的典型要求。

5）tr(GLBGT)的調(diào)節(jié)使為了保持相似度，實現(xiàn)高價平滑，對數(shù)據(jù)進行投影后，尋找出最小加權(quán)的漢明距離。

6）從實際應用中收集的數(shù)據(jù)集通常包含冗余，這很難使聚類總體上取得顯著的結(jié)果，因此需要降低數(shù)據(jù)的維數(shù)。許多譜聚類方法通常通過子空間學習構(gòu)造低維譜表示，即將高維數(shù)據(jù)投影到低維子空間，同時保持數(shù)據(jù)的結(jié)構(gòu)特征。例如，局部保持投影在子空間學習和譜聚類中被廣泛使用，因為它可以保持原始特征數(shù)據(jù)的最近相關(guān)性（即數(shù)據(jù)的重要相關(guān)性）。提出的基于離散哈希的聚類公式如下：

其中的L=D-S是圖的拉普拉斯矩陣。D是一個對角矩陣，矩陣中第i個元素定義為。此外，S=也就是說，如果第i個樣本是第i個樣本的k個最近鄰居之一，則相應的sij可以由熱核函數(shù)［23］定義。例如，其中的σ是一個協(xié)調(diào)參數(shù)。在相似矩陣的約束下，投影矩陣W也保持了樣本與原始數(shù)據(jù)的相似性。

利用超圖構(gòu)造拉普拉斯矩陣，并進一步利用超圖拉普拉斯矩陣約束表示，以保持原始數(shù)據(jù)的復雜高階關(guān)系。所以，式（15）可以改寫為：

其中LB是超圖拉普拉斯矩陣，它可以由超圖構(gòu)造方法構(gòu)造。與超圖的其他構(gòu)造方法相比，該方法使用自適應學習方法來獲得本質(zhì)超圖結(jié)構(gòu)，從而容易獲得魯棒的拉普拉斯矩陣。

考慮到進一步選擇特征以減輕冗余特征的影響，可以學習魯棒的譜表示，它的公式被定義為：

如果兩個相似的圖像的距離很遠，那么就難以估計。所以，類似的圖像可以被映射成漢明距離的較短的哈希碼，通過哈希碼的稀疏情況，對圖像更好地聚類，提高它的速度。

2.2 CDH算法求解

在本節(jié)中，將介紹通過在以下3 個子問題之間交替求解聯(lián)合優(yōu)化問題（10）的算法：

1）通過輸入Y求解二進制哈希碼結(jié)構(gòu)來表示問題，而求出W、B、C、G。

2）使用基于離散哈希的方法，對圖像進行哈希二進制編碼，對投影矩陣進行自動特征選擇，將其應用的子問題進行求解，約束矩陣W。

3）利用二元聚類結(jié)構(gòu)學習對二進制碼進行聚類，通過對符號函數(shù)進行松弛到帶符號的量級，將目標函數(shù)進行表示。

優(yōu)化問題（10）涉及離散約束問題。在本節(jié)中將使用一種交替優(yōu)化策略，它將問題分成幾個子問題，這樣每個子問題都是可處理的。具體地，在優(yōu)化目標函數(shù)時，每個部分分別看作一個變量，固定其他變量，在固定其他變量時交替更新每個變量。迭代步驟的詳細內(nèi)容如下。

更新W通過固定除W之外的所有變量，可以將問題寫為：

為了方便計算，可以對式（18）中的單步進行形式轉(zhuǎn)化：

將式（19）代入式（18）得：

去除不含W的項得出：

計算式（21）的導數(shù)并設(shè)為0，通過求導得到的封閉解

其中Λ是一個對角矩陣，它的對角元素可以寫成：

為了保證分母有意義，在分母上添加一個足夠小的正常數(shù)Δ，此使，Λ轉(zhuǎn)化成Λ′=diag(Λ′11，Λ′22，…，Λ′ll)，對角線元素可以寫成：

用Λ′更換Λ時，式（22）可以改寫成如下形式：

更新B問題（10）同樣涉及B，通過固定除B之外的所有變量，可以將問題簡化為：

式（26）可以重寫為：

con是一個恒定值，因為tr(BBT)=tr(BTB)是一個常數(shù)，同時可將式（26）改為：

它的最優(yōu)解是：

更新C和G這一部分是在漢明空間中優(yōu)化二元聚類結(jié)構(gòu)，是將K-means 和譜聚類聯(lián)合到一個共同的框架中。通過除去不相關(guān)性，得到如下二元聚類公式：

式（30）中的C和G中都不是凸的。因此，期望算法找到全局最小值不能現(xiàn)實。本節(jié)將介紹用乘法更新規(guī)則實現(xiàn)局部極小值的迭代算法。首先討論如何最小化目標函數(shù)式（30），它可以重寫為：

由于矩陣具有以下性質(zhì)：tr(GB)=tr(BG)，tr(B)=tr(BT)，所以可以得到第二個等式。ψik和?jk分別為約束cik≥0 和gik≥0 的拉格朗日乘子，并且Ψ=[ψik]，Φ=[?jk]，拉格朗日L是：

L關(guān)于C和G的偏導是：

使用階優(yōu)化條件KKT（Karush-Kuhn-Tucker）使ψikcik=0和?jkgjk=0，得到了關(guān)于cik和gik的方程：

這些方程導致了以下更新規(guī)則：

算法1 總結(jié)了所提出的CDH 的主要步驟。

算法1 離散哈希的聚類算法CDH。

輸入 數(shù)據(jù)矩陣Y={y1，y2，…，yn}，參數(shù)α，β，γ，λ；

輸出 標簽矩陣G。

3 算法的性質(zhì)分析

3.1 收斂性分析

提出的CDH 方法可以找到最優(yōu)解，為了證明其收斂性，在本節(jié)中，提供了算法1 的收斂性分析。首先引入一個重要的引理。

引理1給定兩個正常數(shù)a和b，有以下不等式成立：

證明 給定兩個正常數(shù)a和b，有

算法1 將迭代地降低問題（10）的目標函數(shù)值，即經(jīng)過多次迭代返回G的解。通過迭代優(yōu)化，式（10）的目標函數(shù)值在每次迭代時都單調(diào)遞減并向下界靠攏。此外，在圖像數(shù)據(jù)集上的實驗也驗證了該方法的收斂性。

K-means 和CDH 方法在相同數(shù)據(jù)集上收斂速度圖比較如圖2 所示，可以清楚地看到K-means 和CDH 方法的收斂速度非常高，大概在100 次以內(nèi)迭代值就會達到收斂。

圖2 兩種方法在COIL20數(shù)據(jù)集上的收斂曲線Fig.2 Convergence curves of two methods on COIL20 dataset

3.2 復雜性分析

基于離散哈希的聚類方法的計算負擔主要由哈希二進制碼學習以及在漢明空間中對二進制碼聚類兩部分組成。首先在數(shù)據(jù)集預處理部分對原始數(shù)據(jù)集進行一個錨圖構(gòu)造，錨圖的構(gòu)造包括錨的生成和錨與圖像之間的距離計算。該過程的時間復雜度為O(dmn)，d是數(shù)據(jù)的維度，m是錨點個數(shù)，n是原始樣本數(shù)。為了節(jié)省式（10）中的時間，在整個算法主要是在迭代之外，對映射矩陣W進行投影，其代價為O(dmn)。計算離散表示的二進制碼B消耗O(lmn+lcn)。因此，對離散哈希二進制碼學習的時間復雜度為O(lmn+lcn+dmn)，c表示聚類簇的數(shù)目。聚類是在漢明空間對二進制碼進行聚類。更新計算K-means 中的每一次迭代運算其實很簡單，但由上節(jié)的更新C、G中需要注意的一點是A是一個稀疏矩陣，這里需要O(n2d)的時間復雜度來構(gòu)建p最近鄰圖。假設(shè)更新是在t次之后停止，那么K-means 的時間復雜度是O(tdnc)，這樣整個對二進制碼進行聚類的時間復雜度是O(tdnc+n2d)。綜上可得，整個基于離散哈希的聚類方法所使用的時間復雜度是O((l+d)mn+(l+td)nc+n2d)。

3.3 參數(shù)敏感度

根據(jù)是否采用離散方法優(yōu)化二進制碼，現(xiàn)有的數(shù)據(jù)依賴的哈希方法可以進一步分解為連續(xù)的哈希方法和離散的哈希方法。在對哈希碼進行選擇時，短的哈希碼表示能力弱，會使得聚類的復雜度較低；而長哈希則表示能力強，其聚類的復雜度高。

基于離散哈希的聚類方法采用的是離散的哈希碼學習方式，在對定義哈希碼長度時，假設(shè)哈希碼長度為l，一共有c個聚類中心，則需要滿足l>lbc，否則，哈希碼將無法區(qū)分不同類別，這是哈希碼長度的下限。

同時，當一個參數(shù)的值發(fā)生變化時，其他參數(shù)在這些實驗中被設(shè)置為相同的值，最終的結(jié)果也會跟著發(fā)生變化。圖3顯示α和γ值對Caltech101數(shù)據(jù)集的HOG視圖準確度（Accuracy，Acc）［24］、歸一化互信息（Normalized Mutual Information，NMI）［25-26］、純度（Purity）［27］的影響。

圖3 α和γ值對Caltech101數(shù)據(jù)集的HOG視圖Acc、NMI、純度的影響Fig.3 Effects ofα andγ values on HOG view Acc，NMI，Purity for Caltech101 dataset

圖4 顯示了根據(jù)不同的λ相對應的Acc、NMI 和Purity 的變化。

圖4 Acc、NMI和純度相對于不同λ的變化Fig.4 Acc，NMI and Purity changes with respect to differentλ

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

在本章中，為了驗證CDH 的聚類效果，從聚類性能、計算效率和內(nèi)存負載等方面評估了所提CDH 方法對于圖像聚類任務(wù)的有效性。在大量的基準數(shù)據(jù)集上，實驗結(jié)果選用三個最常用的評價指標，即Acc［24］、NMI［25-26］和Purity［27］作為評價標準，將其與幾種代表性方法進行比較，對于每個評價指標，值越大表示結(jié)果越好。

4.1 實驗數(shù)據(jù)集

本節(jié)主要總結(jié)了實驗中使用的數(shù)據(jù)集的特征，評估使用了Caltech101、Yale、COIL20 和ORL 這4 個數(shù)據(jù)集。具體數(shù)據(jù)集總結(jié)如圖5 所示。

圖5 用于實驗的數(shù)據(jù)樣本集示例Fig.5 Samples of datasets for experiments

表2 總結(jié)了實驗中所使用的這些數(shù)據(jù)集的特征。特別地，把Caltech101 多視圖數(shù)據(jù)集的每一個維度看作成一個單視圖。

表2 數(shù)據(jù)集特征Tab.2 Dataset characteristics

1）Caltech101 數(shù)據(jù)集由9 144 幅圖像組成，包含101 個對象和1 個背景類別。選用文獻［28］中Caltech101 數(shù)據(jù)集的實驗特性，將Caltech101 中的六個不同特征分別看作成一個視圖，用于實驗的數(shù)據(jù)樣本集中。

2）Yale 數(shù)據(jù)集選用Yale 數(shù)據(jù)庫中的由15 個人組成的4 096 張人臉圖像。

3）COIL20 是一個圖像數(shù)據(jù)集，它有1 440 幅圖像。數(shù)據(jù)集包含20 個物體，每個物體水平旋轉(zhuǎn)360°，每5°拍攝一次，每個物體總共72 張圖片。

4）ORL 是一個包含10 組400 幅圖像的人臉數(shù)據(jù)集。由40 個不同年齡、性別的對象組成的圖像。對于一些受試者，在不同的時間拍攝圖像，改變燈光、面部表情（睜開/閉上眼睛、微笑/不微笑）和面部細節(jié)（戴眼鏡/不戴眼鏡）。

4.2 評價指標

本節(jié)中將會使用Acc、NMI 以及Purity 三個評價指標對相關(guān)的比較方法進行實驗性能評價，這些評價指標的具體定義如下。

Acc 定義如下：

其中：map（ri）是一個置換映射函數(shù)，用于使簇標簽ri與數(shù)據(jù)集中的等價標簽匹配；n為數(shù)據(jù)點個數(shù)，ri是Xi的預測標簽，li是對應的真實簇標簽；δ(a，b)是一個脈沖函數(shù)，如果a=b則函數(shù)值為1，其他為0。

H(X)為：

其中p(i)=|X|/N是從X中隨機選擇的一個對象落在第Xi類中的概率。

Purity 是聚類評價方法，它只需計算正確聚類的數(shù)據(jù)占總數(shù)據(jù)的比例：

其中：Ω={ω1，ω2，…，ωk}是聚類的集合，ωk表示第k個聚類的集合；C={c1，c2，…，cj}是文檔集合，cj表示第j個文檔。N表示聚類數(shù)據(jù)總數(shù)。

4.3 比較方法

為了評價CDH 方法的性能，將會從以下幾種聚類方法和CDH 方法作比較：

1）K-means 聚類方法的思想很簡單，對于給定的樣本集，按照樣本之間的距離大小將樣本集劃分為k個簇，讓簇內(nèi)的點盡量緊密地連在一起，而讓簇間的距離盡量大［9］。

2）譜聚類（Spectral Clustering，SC）是一種基于圖論的聚類方法，通過對樣本數(shù)據(jù)的拉普拉斯矩陣的特征向量進行聚類，從而達到對樣本數(shù)據(jù)聚類。譜聚類可以理解為將高維空間的數(shù)據(jù)映射到低維，然后在低維空間用其他聚類算法（如K-means）進行聚類［28-29］。

3）LSC-K：基于標記表示的大規(guī)模譜聚類方法利用K-means 進行地標選擇，可以從作者的網(wǎng)站（http：//www.cad.zju.edu.cn/home/dengcai/）下載Matlab 代碼［30］。

4）LSH+bk-means：單臺機器上的Web 級照片哈希聚類首先使用局部敏感哈希（Locality Sensitive Hash，LSH）生成一個隨機高斯矩陣，數(shù)據(jù)點被哈希成二進制碼。將bk-means應用于生成的二進制碼進行聚類。這種樸素的兩步聚類方法可以被視為基于二進制編碼的聚類方法的基線［5，31-33］。

5）CKM 用于大規(guī)模聚類［22］。

6）多視圖K-means 聚類（Multi-View K-Means clustering，MVKM）［34］，該方法使用典型相關(guān)分析（Canonical Correlation Analysis，CCA）將每個視圖中的數(shù)據(jù)投射到一個低維子空間之后再進行聚類［35］。

7）自動加權(quán)多重圖學習（Auto-weighted Multiple Graph Learning，AMGL），該方法在描述時有相同的實例可以由多個異構(gòu)特征表示，并且可以自動學習每個圖的最優(yōu)權(quán)值［36］。

8）RPCA：稱為魯棒主成分分析，是目前應用最廣泛的降維方法［15，37］。

9）非負矩陣分解（Nonnegative Matrix Factorization，NMF）［38］。

10）考慮數(shù)據(jù)的非線性結(jié)構(gòu)的圖正則非負矩陣分解（Graph regularized Nonnegative Matrix Factorization，GNMF），由NMF 演化得到。

這里包含了最為經(jīng)典的K-means 聚類方式，以及單視圖聚類方法：SC、LSC-K 和兩種現(xiàn)有的二元聚類方法：LSH+bkmeans 和CKM。同時，AMGL 和MVKM 代表了對大規(guī)模的數(shù)據(jù)進行聚類的方式，與CDH 方法進行了比較。經(jīng)過實驗比較可以得出不同方法在數(shù)據(jù)集上的精度、NMI 以及純度，如表3～8 所示。

表3 不同方法在Caltech101數(shù)據(jù)集上的精度對比Tab.3 Accuracy comparison of different methods on Caltech101 dataset

表4 不同方法在Caltech101數(shù)據(jù)集上的NMI對比Tab.4 NMI comparison of different methods on Caltech101 dataset

表5 不同方法在Caltech101數(shù)據(jù)集上的純度對比Tab.5 Purity comparison of different methods on Caltech101 dataset

表6 不同方法在不同數(shù)據(jù)集的精度對比Tab.6 Accuracy comparison of different methods on different datasets

表7 不同方法在不同數(shù)據(jù)集的NMI對比Tab.7 NMI comparison of different methods on different datasets

表8 不同方法在不同數(shù)據(jù)集的純度對比Tab.8 Purity comparison of different methods on different datasets

4.4 實驗設(shè)計與分析

在與其他先進的單視圖聚類相比，從表3～8 中可以觀察到基于離散哈希的聚類在大多數(shù)情況下優(yōu)于所比較的實值和二元聚類方法。具體來說，CDH 通過對自動特征選擇，選取最有用的信息進行哈希學習可以在單個視圖上獲得更好的結(jié)果，這表明通過哈希學習的離散表示對于聚類是有效的。對于單視圖方法，如K-means、SC 和LSC-K，可以發(fā)現(xiàn)直接對未進行任何處理的數(shù)據(jù)進行聚類，在大多數(shù)情況下可能導致冗余信息。由于哈希二進制碼學習和二元聚類結(jié)構(gòu)構(gòu)建在一個更好的統(tǒng)一框架上，CDH 明顯優(yōu)于現(xiàn)有的二進制聚類方法，例如SC 和LSC-K。

同時，基于離散哈希的聚類方法的時間效率與其他聚類方法相比更具有優(yōu)勢，它比其他聚類方法快得多，例如：Caltech101 數(shù)據(jù)集的Gabor 視圖，K-means 需要27 s，SC 需要200 s，CDH 只需要3.4 s。主要原因是基于離散哈希的聚類算法受益于使用漢明距離來測量而不是歐幾里德距離測量的高效距離計算［39］?；陔x散哈希的聚類算法比其他所有的比較方法花費更少的時間，這也證明了所提出的高效離散優(yōu)化算法的優(yōu)越性。

表3～8 中的結(jié)果表明，與真實值聚類方法相比，基于離散哈希的聚類有更高的聚類性能，主要原因是該聚類方法所提出的有效的離散優(yōu)化方法，其中的自動特征選擇可以很好地消除了原始實值特征中的一些冗余和噪聲信息，同時，使用二進制碼進行聚類可以更高效地處理高維數(shù)據(jù)。

通過實驗可以得到CDH 方法的4 個優(yōu)點：

1）CDH 方法使用哈希學習，將數(shù)據(jù)投影成二進制碼，對數(shù)據(jù)在漢明空間中進行聚類，運行速度快，減少存儲空間。

3）對轉(zhuǎn)化成二進制碼的數(shù)據(jù)約束，進行特征選擇，選擇更有價值的信息，這樣能夠提高聚類的聚類精度。

3）離散哈希碼優(yōu)化直接求解哈希碼，沒有量化誤差。

4）利用相關(guān)圖像標簽中有價值的語義增強圖像哈希碼的識別能力，同時去除其中可能降低聚類性能的不利噪聲。

5 結(jié)語

在現(xiàn)有的一些聚類方法中，將原始數(shù)據(jù)在數(shù)據(jù)空間中聚類，對數(shù)據(jù)聚類時存在噪聲情況，存在一些信息精度不高問題，提出的一種二值聚類方法——基于離散哈希的聚類方法。在聚類過程中，將哈希碼學習和二元聚類結(jié)構(gòu)放到同一個框架中，該方法可以直接學習二進制哈希碼，并將數(shù)據(jù)投影到漢明空間中進行聚類，計算的效率高，存儲成本較低，適合用于高維度的圖像聚類。建立了一個基于離散哈希的學習模型，可以使用哈希函數(shù)來解決離散化的問題，實現(xiàn)高維數(shù)據(jù)集的數(shù)據(jù)聚類。此外，提出的一種基于離散哈希的聚類優(yōu)化方法可以直接求解二進制碼，可以更有效地提高聚類的效率。實驗結(jié)果表明，基于離散哈希的聚類方式與傳統(tǒng)的聚類方法相比更具有優(yōu)勢。接下來考慮將本文方法進行拓展應用于多視圖聚類任務(wù)。