基于流形距離核的自適應遷移譜聚類算法

齊曉軒 都 麗 洪振麒

1(沈陽大學應用技術學院 遼寧 沈陽 110044)2(沈陽大學信息工程學院 遼寧 沈陽 110044)

0 引 言

聚類[1-2]作為數據挖掘領域中重要的方法，主要是將同類對象劃分為同一簇，不同類對象劃分到不同簇的過程。聚類方法有很多種，如C-means、FCM、MECA[3-5]等算法，但這些算法在高斯分布數據集上聚類效果良好，在非高斯分布數據集上聚類效果卻不太理想，容易受樣本形狀影響。譜聚類算法(SC)[6-10]作為一種圖論演化而來的算法，不受樣本空間形狀的制約，且收斂于全局最優解，在一定程度上解決了這個問題。

SC算法首先根據給定的樣本集計算任意兩點的相似度矩陣W，然后計算特征矩陣，最后使用特征矩陣進行聚類，所以相似度矩陣W的選取直接影響特征矩陣的構造，進而影響聚類效果。Kong等[10]通過建立新的相似圖來構造相似度矩陣;ZelnikManor等[13]利用數據點的鄰域分布，自動調節尺度參數，增加其泛化能力。Wang等[3]針對相似度矩陣構造存在尺度敏感問題，利用密度差來調整樣本點之間的相似度。范子靜等[14]利用模糊劃分改進譜聚類中硬化分，調整相似性度量函數。以上方法皆是以歐氏距離作為相似性度量方法，無法反映空間分布結構特征。張建朋等[15]通過使用流形距離代替歐氏距離構造相似性矩陣來改進AP算法,較好地解決了數據分布的全局結構問題；Tao等[16]使用流形距離計算相似度矩陣，但沒有考慮數據點全部的鄰域信息，對于復雜分布點效果依然不理想。

在實際環境中，領域中可用數據的匱乏或者數據受到污染，樣本特征信息稀疏，傳統的聚類算法很難達到良好效果。針對此種情況，遷移學習可以有效利用在某個不同但相關領域上學習到的知識或模式(源域)指導當前領域(目標域)中數據量匱乏的聚類任務，輔助提高聚類效果。在聚類中加入遷移學習已幫助學者們解決了很多問題[16-19]：Dai等[20]通過同時聚類目標和輔助數據提出一種基于協同聚類的自學習聚類(STC);Jiang等[21]通過聯合聚類方法提出遷移譜聚類方法(TSC);魏彩娜等[22]提出基于F-范數正則項的遷移譜聚類方法(TSC-IDFR);Qian等[23]提出使用中心與隸屬度信息遷移的TI-KT-CM和TII-KT-CM方法。

為提高譜聚類的領域適應能力，降低樣本數量、數據空間分布對譜聚類的性能影響，本文提出一種基于流形距離核的自適應遷移譜聚類算法。具體包括兩個方面的改進：① 考慮數據分布的全局一致性，使用流形距離作為相似性計算方法，且面對簇邊緣分布不均勻或不同簇邊緣分布密度相近，局部密度情況復雜會導致錯分的問題，對核函數進行自適應調整，提高譜聚類對復雜數據集的處理能力；② 考慮領域數據匱乏問題，引入遷移學習方法，使用源域的知識輔助目標域進行譜聚類。經實驗驗證，本文算法與原始譜聚類算法相比有明顯提升。

1 相關概念

1.1 SC算法

SC算法(見圖1)主要思想是把樣本點連接起來構造無向權重圖，根據距離遠近賦予權重高低，根據子圖內權重和高、子圖間權重和低的最優劃分原則對圖進行最優劃分，從而完成聚類。

圖1 SC算法原理示意圖

SC算法的最優化模型為：

maxtr(UTLU)U∈RN×k

(1)

s.t.UTU=I

算法實現過程：

輸入：n個樣本點X=x1,x2,…,xn，聚類個數k

輸出：聚類簇c1,c2,…,ck

步驟1構造無向權重圖G(V,E),計算相似度矩陣W：

(2)

步驟2計算度矩陣D:

(3)

步驟3計算拉普拉斯矩陣L:

L=D-W

(4)

標準化L：

(5)

步驟4計算L的前k個最小特征值的特征向量組成矩陣且對其進行標準化，得到特征矩陣U={u1,u2,…,uk},U∈Rn×k。

步驟5采用C-means或FCM等對U進行聚類，得到聚類結果{c1,c2,…,ck}。

1.2 流形距離

歐氏距離是最快捷簡單的距離度量方法。但使用歐氏距離計算的聚類算法往往會忽略數據的空間分布特征，無法滿足聚類的全局一致性。為了解決這個問題，有學者提出流形距離，具體形式如下：

局部流形距離即流形上的點到點的線段長度，在同一流形結構中，數據集任意兩點xi、xj之間的流形距離為：

Ld(xi,xj)=ρdist(xi,xj)-1

(6)

式中：dist(xi,xj)為xi和xj兩點之間的歐氏距離。

全局流形距離：構造數據點間的加權無向圖G(V,E)，V為圖的頂點,E為圖邊集合。令p={p1,p2,…,pk}∈Vl表示圖上一條連接點p1與pk的路徑，其中邊(pm,pm+1)∈E，1≤m

設P=(p1,p2,…,pk)是xi和xj之間的一條最短路徑,則全局流形距離為連接兩點之間的最短路徑的所有局部距離之和：

(7)

式中：pi,j是xi和xj之間的最短路徑。

(8)

該方法可增大不同流形上數據點的距離，縮小不同流形上數據點的距離。

2 算法設計

2.1 基于流形距離核的自適應譜聚類算法(ASC-MDK)

SC算法用高斯核函數構建相似度矩陣，但是歐氏距離在計算距離時受結構影響較大，當數據集為復雜的流形結構時，會損失很多結構特征，使用流形距離代替歐氏距離能在一定程度上解決這個問題。

本文以流形距離計算任意兩點的距離，且對核函數進行調整，使其面對更復雜的分布時，保留更多樣本特征信息，提高聚類準確率。歐氏距離計算的核函數為：

(9)

本文用流形距離作為距離度量方法，流形距離核函數為：

(10)

該核函數雖能考慮數據的整體結構分布，但參數σ均是通過反復測試得到，時間復雜度高，若取固定值，則影響核函數的泛化性，制約聚類效果。為了取得合適參數，ZelnikManor等[13]提出使用數據點的鄰域信息計算一種自動選擇尺度參數σ的方法，為每一個樣本點選擇一個σi，定義的核函數為：

(11)

式中:σi為點xi到第k個近鄰的歐氏距離，但該k近鄰方法易受噪聲點影響。本文尺度參數取點xi的加權距離，可在一定程度上提高核函數的自適應能力，降低噪聲點的干擾，具體表示為：

(12)

(13)

式中:參數σi取點xi的第k個近鄰點xk的加權距離。由此可以得到融入加權參數和流形距離的核函數，具體表示為：

(14)

使用流形距離計算的相似度矩陣考慮了全局一致性，加權參數可減小參數對特征矩陣的影響。但當簇間密度差異較大、簇邊緣分布不均勻或不同簇邊緣分布密度相近時，局部密度情況復雜會導致錯分，仍會影響聚類效果。以圖2和圖3為例，利用式(14)計算圖2中點的相似度，a、b位于較稠密的簇中,c、d處于較稀疏的簇中，且它們都處于簇的邊緣，正確聚類有一定難度，已知dist(a,b)=dist(b,c)=dist(c,d)，可知當σb<σd、σbσc<σdσc，得K(b,c)

圖2 樣密度分布不均勻示意圖

圖3為雙月形分布，已知dist(e,f)=dist(f,g)，當σe=σg時，σeσf=σgσf，表明e、f和g、f的相似度相同，但e、f應聚為一類，所以g影響了f的聚類，可能使f聚為錯誤的一類。所以應該賦予e、f更高的相似性。

圖3 雙月形分布示意圖

為解決上述問題，提高聚類準確率，本文使用共享近鄰方法(SNN)[24]來調整相似度矩陣，SNN定義為求兩個點共享的近鄰點的個數。xi和xj表示樣本集{x1,x2,…,xn}的任意兩點，兩點的相似度為共享最近鄰點的個數，即：

(15)

(16)

當共享近鄰數為0時，SNN(xi,xj)+1=1，即對相似性不作調整。因為a、b處于稠密的簇中，可知a、b的共享近鄰的個數多于b、c的共享近鄰個數，所以SNN(a,b)+1>SNN(b,c)+1，可以對相似性進行調整，使a、b的相似性更大，使聚為一類的概率更高。e、f處于同一流形中，g處于另一流形中，可知e、f共享近鄰多于g、f，所以SNN(e,f)+1>SNN(f,g)+1，可以對相似性進行調整，使e、f的相似性更大，更可能聚為一類。

綜上，基于SC算法提出了一種改進的計算相似度函數的方法：“加權局部密度自適應的流形距離核”，表示為：

(17)

該核函數得到的距離空間是離散值，區間為[0，+∞]，相似度空間區間為[0，+∞]。通過式(17)，可知該函數滿足以下基本性質：

1) 非負性：Kij≥0；

2) 自反性：Kij=0；

3) 對稱性：Kij=Kji；

4) 一致性：當S(xa,xb)

2.2 ATSC-MDK算法

ASC-MDK在樣本充分時，可通過考慮數據聚類的全局分布，局部復雜分布情況，進行自適應調節。但當數據匱乏時，該方法依然不會得到理想效果，由此引入遷移學習解決這個問題。基于F-范數的正則項遷移譜聚類方法(TSC-IDFR)[21]在SC算法上，引入遷移學習機制形成了基于高級知識遷移的譜聚類算法，即把源域提取出的高級知識進行遷移，指導目標域數據集的聚類。

TSC-IDFR通過減小目標域數據和源域數據上的知識之間的不相似程度，得優化函數為：

(18)

式中:U(C)和U(O)分別表示目標域數據和源域數據的特征矩陣；KU(C)和KU(O)分別表示U(C)和U(O)對應的相似度矩陣。經過變換，得到優化目標函數：

(19)

式(19)通過最小化目標函數，即最大化tr(U(C)U(C)TU(O)U(O)T),作為遷移正則項加入譜聚類原始優化函數中，那么TSC-IDFR的最優化模型為：

(20)

s.t.U(C)TU(C)=I

經變換得：

(21)

s.t.U(C)TU(C)=I

式中：λ為調整目標域關于源域知識的遷移程度，其參考取值范圍為(0.1,1.0)。

在該遷移譜聚類方法基礎上，融入ASC-MDK算法，提出基于流形距離核的自適應遷移譜聚類算法(ATSC-MDK)，其最優化模型為：

(22)

2.3 算法流程

輸入：源域數據集data(O)，目標域數據集data(C),聚類個數c,伸縮因子ρ，最近鄰點數k

輸出：目標域數據點的劃分c1，c2,…,ck

步驟1使用第K近鄰機制為輸入的目標域數據集data(C)從源域數據集data(O)中挑選可參照樣本集(采用網格搜索方法)。

(1) 通過迪杰特斯拉算法[25]進行數據集任意相鄰兩點最短路徑選擇，并通過式(8)計算最短路徑和。

(2) 根據式(12)、式(13)計算參數σi和σj。

(3) 根據共享近鄰算法計算SNN(xi,xj)+1；最后計算式(17)得到Kij。

(4) 計算數據集的拉普拉斯矩陣L，其中：

對角元素為：Kii=0,1≤i,j

構造拉普拉斯矩陣：L=D-K。

算法流程圖如圖4所示。

圖4 ATSC-MDK算法流程圖

3 實 驗

3.1 算法分析

3.1.1 相似度對比分析

相似度矩陣對于譜聚類算法進行特征提取而言是至關重要的一步，會直接影響聚類結果。如圖5所示，以雙月型數據集(如圖3所示)為例，(a)為以本文提出的距離核計算的相似度矩陣，(b)為傳統譜聚類的高斯核計算的相似度矩陣。以高斯核計算的距離矩陣類別分布不明顯，無明顯規律可循，說明以歐氏距離計算的相似度矩陣很大程度上忽略復雜數據集的分布結構，而本文距離核計算的點陣顏色分布及深淺較明顯，呈塊對角模式，可看到明顯分類。這表明，本文方法能更好地反映數據集的內在結構和整體分布，采用的流形距離測度較空間分布形狀不敏感，更能考慮流形分布對聚類的影響。且通過考慮邊緣密度情況，降低邊緣密度影響造成錯分情況。最后采用加權自適應核參數，避免了參數敏感，且降低了噪聲點的干擾。

(a) 距離核 (b) 高斯核圖5 兩種方法相似度矩陣計算對比

3.1.2 復雜度分析

本文算法主要執行任務是計算ATSC-MDK算法的迭代過程。ATSC-MDK運行一次需要分別進行源域和目標域的ASC-MDK算法。選取來自源域的樣本數據時間復雜度是O(m×n2)，利用Dijkstra算法搜索最短路徑的空間復雜度為O(n2)，構建KNN網絡并賦權的計算徑向基參數時間復雜度為O(n2)，SNN共享近鄰時間復雜度O(n2)，調整系數λ時間復雜度O(n)，本文整體迭代次數為T,因此算法的時間復雜度為O(m×n2+3n2+n)。本文所提算法處理數據量較大時，可利用GPU對算法進行加速，增加算法的實用性。

3.2 算法對比

為驗證ATSC-MDK算法的有效性，將使用三組人工模擬數據集和三組公共數據集進行實驗對比。本文除了與SC算法比較，還將與ASC-MDK、FCM、TI-KT-CM、TII-KT-CM、TSC-IDFR算法進行對比。

實驗采用歸一化互信息(NMI)和蘭德指數(RI)[26]兩大常用方法作為評價標準。

(23)

式中：P(i,j)為同時聚類到U類和類標簽為V的概率，P(i)為聚類到U類的概率，P′(j)為聚類到V類的概率。NMI取值范圍為[0,1],越趨近于1，聚類效果越好。

(24)

實驗環境：所用PC為Xeon處理器，2.8 GHz，16 GB RAM, 算法編程使用MATLAB2016a。

3.2.1 模擬數據集及實驗

遷移學習的場景要求領域相關且不相同，為此本文在以下場景進行實驗：

(1) 高斯分布遷移數據集M1-M2:如圖6所示的低維人工模擬數據集。(a)為采用高斯概率分布函數隨機生成4類共800個數據樣本的源域數據集；(b)-(h)為采用高斯概率分布函數隨機生成4類320個數據樣本的目標域數據集。

圖6 高斯分布遷移數據集M1-M2

(2) 雙月型遷移數據集L1-L2：如圖7所示，(a)不含噪聲，共121個數據點且分為上下兩類；(b)-(h)為受噪聲干擾，共120個數據點且上下分類界限有重疊，邊緣分布較復雜。

圖7 雙月型遷移數據集L1-L2

(3) Threecircles遷移數據集C1-C2：如圖8所示，(a)為三個同心圓圍起來的源域數據集；(b)-(h)為非同心圓，且有交叉的目標域數據集。

圖8 Threecircles遷移數據集C1-C2

由圖6-圖8和表1可得：SC算法在人工數據集上表現效果較差，ATSK-MDK算法在兩大評價指標上均高于其余對比算法，可以得到較好的聚類效果。

表1 人工模擬數據集的各類算法聚類效果對比

M1-M2：凸形數據集中，ATSC-MDK,TSK-IDFR是在SC算法基礎上進行知識遷移,TI-KT-CM和TII-KT-CM是在FCM算法上進行知識遷移，經過表1數據聚類結果對比，均在原始算法上有所提升，說明在場景遷移中，來自源域的歷史信息可以進行有效的遷移，提高目標域聚類效果。

L1-L2：L1為絕對流形數據集，L2目標域數據集為數據分布較分散，數據相互重疊的流形數據集，邊緣數據分布較復雜，容易造成錯誤聚類，且為典型的非凸型數據集。在考慮數據流形分布的情況下，可充分體現流形距離優勢。基于FCM下進行知識遷移的TI-KT-CM和TII-KT-CM很明顯對于非凸形數據集聚類效果不佳，但效果依舊有所提升，進一步說明遷移學習的有效性。而SC算法可以適應任意形狀的數據且不易陷入局部最優，所以對于非凸形數據集有明顯優勢。在此基礎上，考慮到這種特殊的流形分布，ASC-MDK明顯優于歐氏距離的SC，加入流形距離的ATSC-MDK算法明顯優于歐氏距離的TSC-IDFR算法。且根據實驗結果，在此種分布下，考慮數據的分布結構比加入遷移學習方法提升效果更為突出。

C1-C2：FCM是通過尋找聚類中心的方法進行聚類，在此種多流形分布下，聚類中心非常難找，沒考慮分布結構的情況下，聚類錯誤率非常高，正確率不超過30%，所以隸屬度進行遷移的TI-KT-CM,TII-KT-CM算法，提升效果微乎其微。此種形狀的數據集，SC算法的優勢非常明顯，ASC-MDK算法可以更進一步考慮分布的全局一致性，面對復雜邊緣分布，且可自適應調節，效果有所提升。ATSC-MDK針對以上問題，面對分布結構，邊緣密度等復雜情況，聚類效果較好。

3.2.2 真實數據集實驗結果分析

為了進一步驗證算法的有效性，在三個公共數據集上驗證，該數據集為遷移學習、聚類效果常用的驗證數據集，具有一定的基準性。

(1) 數據集1：來自UCI的人類活動時間序列數據集。從中選取來自志愿者的6類自然活動：走路，上樓梯，下樓梯，坐下，站立，躺下。本文源域選取494條女性數據記錄，目標域選取312條男性數據記錄，并進行降維處理。

(2) 數據集2：來自ESF數據庫的垃圾郵件數據集。本文源域使用公共消息資源的4 000條數據記錄，目標域使用用戶的1 800條數據。

(3) 數據集3：來自Brodatz紋理數據庫。圖9為源域紋理圖像，圖10為目標域紋理圖像(有噪聲)。通過濾波方法對紋理特征進行提取，且對維度進行處理，構成了最終TIS紋理數據。

圖9 源域

圖10 目標域

真實遷移場景數據與真實數據集的各類算法聚類效果對比如表2、表3所示。

表2 真實遷移場景數據

表3 真實數據集的各類算法聚類效果對比

由表2和3可得：ATSC-MDK算法在NMI和RI指標中均高于其余算法，雖然在人類活動序列數據集中，提高不太明顯，但是在垃圾郵件數據集中提高比較明顯，所以總體聚類效果有所提升。在考慮到數據的空間分布時，ASC-MDK在經典譜聚類的基礎上對核函數機型改進，對比SC效果有明顯的提升，說明考慮空間分布可以較好地提高聚類效果。TSC-IDFR中融合ASC-MDK所建立的ATSC-MDK算法，克服數據數量影響聚類性能的問題，對比SC聚類效果有很大提升。

真實目標域數據集與源域數據集分布相似但不相同，在分布時有一定的差異性，所以ATSC-MDK、TSC-IDFR、TI-KT-CM、TII-KT-CM均可獲得來自源域的有用信息，提高目標域的聚類有效性。ATSC-MDK不僅選取有用數據集，考慮源域和目標域的空間分布特征，因此選取最有效的指導目標域的數據集，在一定程度上有效避免了負遷移。

4 結 語

為提高SC算法的領域適應能力，降低數據空間分布、樣本數量等對其性能的影響，本文提出一種基于流形距離核的自適應遷移譜聚類算法(ATSC-MDK)。考慮數據分布的全局一致性，使用流形距離作為相似性計算方法，充分考慮全部局部鄰域信息，對核函數進行自適應調整，提高譜聚類對復雜數據集的處理能力；考慮領域數據匱乏問題，引入遷移學習，使用源域的知識輔助目標域進行譜聚類。實驗結果表明，本文算法性能與原始譜聚類算法相比有明顯提升。