非負低秩親和度圖的構建

1非負局部約束低秩子空間算法在過去幾十年中，他研究了子空間。譜聚類算法的關鍵步驟在于構建親和度圖。構建親和度圖的方案分為基于局部距離和基于全局線性表示兩種。基于局部距離的方法利用成對點之間的歐氏距離建立親和度圖,如拉普拉斯特征圖稀疏子空間聚類算法與基于稀疏方法相比,基于低秩的方法旨在找到所有數據的最低秩表示,即rank(Z),s.t.X=XZ。此方法更適合追求數據空間的全局和內在信息。然而,低秩表示算法不能利用數據之間局部線性結構,這將導致構造的親和度矩陣通常是密集的,并且低秩表示中的負值在構建親和度矩陣上沒有任何意義。為了兼顧數據的全局和局部結構,本文提出了非負局部約束低秩子空間算法,該算法在低秩表示的基礎上,將數據的局部稀疏結構作為約束集成到統一公式中。此外,原始數據作為字典不具有代表性,基于學習的字典對噪聲有良好的魯棒性?？紤]到最終結果的準確性,在預處理數據時,采用Wei2相關工作2.1子空間的集合令X=[x其中第i個塊Z2.2低秩表示算法低秩表示算法旨在探索多個子空間結構,從而找到一組數據向量的最低秩表示。對于無噪聲的情況,低秩表示算法將數據本身作為字典,并尋找最低秩表示矩陣Z:由于秩函數不是凸的難以求得最優值,式(2)最優化問題可以放寬到以下凸優化問題:其中||?||對于存在噪聲的情況,低秩表示算法通過向目標函數(3)添加列和范數項處理噪聲數據,使得噪聲稀疏:雖然實驗結果表明直觀地,該模型消除了大部分噪聲,并采用干凈數據作為字典,當數據本身嚴重損壞時,最終的聚類效果比低秩表示算法有明顯提升。3正則項參數平衡稀疏與低秩約束及法典更新在2.1節中,說明了對于塊對角矩陣Z如果字典是過于完備的(比如用數據本身作為字典)可以有無窮多個可行解,為了解決這個問題,對所求的表示矩陣Z加入稀疏與低秩約束:式(6)中β>0是正則項參數平衡稀疏性與低秩性,表示矩陣Z的每一列z其中||?||同時,也要考慮到噪聲的影響,加入噪聲項E的同時,對字典進行更新:典D根據2.2節Wei該模型具體來說,每個數據點由其他數據點的線性組合得到,表示矩陣Z是非負且稀疏的3.2交替方向乘子法對于式(8),雖然在求解過程時固定其他變量求解單一變量可以確保函數為凸函數,但計算量仍非常巨大。因此在確定字典時,基于Wei根據引理1可以將式(8)近似地轉化為如下兩式:式(9)用核范數近似替代秩函數(rank),利用增廣拉格朗日方法去除約束條件后,借由Lin具體迭代求解流程見算法1,其中Θ對于式(10),交替方向乘子法(ADM)在求解時需要引入兩個輔助變量,每個變量迭代都需要龐大的矩陣計算。因此,采用線性交替方向自適應法(LADMAP)首先,引入輔助變量H使目標函數變量可分離:式(12)的增廣拉格朗日方程為:為后續計算簡便,式(13)化簡為:線性交替方向自適應法(LADMAP)通過求解單一變量時,固定其他變量為最小值來交替更新變量Z、H和E,其中二次項其中?為關于Z的偏微分操作,Θ、S、Ω分別是奇異值閾值操作、收縮閾值操作、l完整迭代算法流程見算法2。3.3親水矩陣的建立得到表示系數矩陣Z3.4非負局部限制低質子空間算法定義親和度矩陣W后,剩下工作為構建親和度圖,圖中的每個頂點對應著每個數據點x4視覺任務性能本章將評估非負局部約束低秩子空間算法(NLRSI)對合成數據和實際計算機視覺任務(運動分割和手寫數字聚類)的性能。為了直觀表達效果,將與基于譜聚類的最先進的子空間聚類算法,如稀疏子空間算法(SSC)對于比較的算法,采用引用文獻中的參數作為輸入參數,其中對于Hopkins155運動分割數據庫4.1局部約束低秩算法當p=0與p=0.3時,圖2與圖3顯示了親和度矩陣W或者表示系數矩陣Z通過圖2與圖3的對比可以看出,非負低秩稀疏表示算法(NNLRSR)與非負局部約束低秩算法(NLRSI)對噪聲的魯棒性能較好,這表明通過局部約束強制更改矩陣結構可以消除大量無關噪聲,使得聚類效果提升,這也在圖1的準確率變化趨勢圖中有所體現。4.2hopcs1-pcr聚類誤差運動分割是指從視頻序列中提取一組二維點軌跡,將軌跡對應于不同的剛體運動。這里,數據矩陣X的尺寸為2F×N,其中N是二維軌跡的數量,F是視頻中的幀數。在仿射投影模型下,n個不同運動對象相關聯的二維軌跡位于n個仿射子空間的組成的R本部分采用Hopkins155數據庫表1顯示了Hopkins155數據庫中155個序列聚類誤差,圖5與圖6展示了155個序列應用非負局部約束低秩子空間算法(NLRSI)各自的聚類誤差,明顯的,二物體比三物體聚類誤差更小。同時從表1中的數據可以看出NLRSI算法的聚類誤差比其他算法誤差小,雖然低秩表示算法(LRR)的中位值更低,但是從平均值結果來看,低秩表示算法對于某些序列的聚類效果不穩定,導致了誤差過大,拉高了平均值。4.3寫數字手寫數字聚類是指由不同人筆跡構成的一組數字圖像,將數字相同的圖像分離出。這里采用美國郵政手5聚類算法的比較本文提出了非負局部約束低秩子空間算法(NLRSI),該算法利用數據的局部稀疏結構和子空間的全局低秩特征,構造體現數據向量之間特點的親和度矩陣。理論分析保證了算法獲得的最優親和度矩陣具有良好的聚類效果。同時實驗結果表明,非負局部約束低秩子空間算法在運動分割和手寫數字聚類任務中,優于現存的幾種最先進的聚類算法。但是該算法也