一種基於稀疏分解l₀圖的局部全局一致性分類方法

2023-06-13 04:56:51

專利名稱：一種基於稀疏分解l0圖的局部全局一致性分類方法
技術領域：
本發明涉及一種基於稀疏分解Itl圖的局部全局一致性分類方法，屬於一種基於圖的半監督分類方法。
背景技術：
近年來同時使用少量有標記數據和大量無標記數據的半監督學習得到了深入的研究，該方法在提高分類器性能的同時降低了人工標註成本，其研究成果已廣泛應用到網頁檢索、圖像分類等各個領域。現有的半監督學習方法有Self-training算法、 Co-training算法、半監督SVM以及基於圖的半監督分類方法等。
基於圖的半監督學習方法通常先定義一個圖，圖上結點是有標記和無標記數據的集合，根據某種相似度準則確定邊的權重，然後定義能量函數優化框架並求解，能量函數由損失項和正則項構成。此類算法本質上是一種無參的、可判別的、直推的學習方法，直接或間接的利用了流形假設，具有較好的數學基礎，是當前半監督學習的一個研究熱點。Blum和 Chawla將半監督學習方法看作圖的最小割問題，Zhu等人利用高斯隨機場以及諧波函數來解決圖上的半監督學習。受高斯隨機場的影響，^iou於2004年提出了局部與全局一致性學習算法，這些算法最本質的區別就是採用了不同的損失函數和正則項。有研究指出，在基於圖的半監督學習中，構造一個合適的圖比選擇優化方法更重要，但圖的構造方法至今也得到很好的研究，目前使用較多的圖有RBF圖、KNN圖、ε -圖以及LLE圖等。
2009年，Wright提出的基於稀疏分解的SRC方法在人臉識別中取得了較好的效果。他指出在足夠多訓練樣本情況下，若以訓練樣本作為稀疏分解的字典，則測試樣本可用訓練樣本的線性組合來表示，而且理想情況下，每個測試樣本係數非零所對應的樣本將屬於同一類。Yan等受Wright的啟發提出了基於稀疏分解的L1構圖法，該構圖過程利用基追蹤法進行稀疏分解，通過尋求信號在冗餘字典中的最稀疏表示，用儘可能少的原子儘可能精的表示信號，獲得信號的內在本質特徵。但該過程並不適用於獲取圖的最相似結點，並且由於基追蹤法要在字典的所有原子中極小化一個全局目標函數，計算量非常大。發明內容
要解決的技術問題
為了避免現有技術的不足之處，本發明提出一種基於稀疏分解Itl圖的局部全局一致性分類方法，
本發明的思想在於基於貪心選擇原理，能夠選擇出最能逼近待分解數據幾個原子，並根據稀疏係數向量確定圖的鄰接結構和權重。Itl圖過程首先利用KMEANS算法選擇待分解數據的稀疏分解字典，然後有限次的迭代匹配追蹤算法找出最能逼近待分解數據幾個原子及其權重，提高了算法效率，並將得到的圖引用到局部全局一致性分類方法。
技術方案
一種基於稀疏分解Itl圖的局部全局一致性分類方法，其特徵在於步驟如下
步驟1稀疏分解Itl圖的構造
步驟a 使用KMEANS聚類算法將整個待分類數據X劃分為k個子集，k為類別數；
步驟b 定義一個nXn的鄰接矩陣W，其元素初始化為0，η為待分類數據總數；
步驟c 以第i個待分類數據Xi為待分解信號，稀疏分解字典Di由Xi所屬聚類子集構成，Xi不包括在Di中，1 < i < η，η為待分類數據總數；
步驟d 預設最大迭代次數為T，迭代終止誤差為ε stop,當前迭代次數t初始化為 0，對待分解信號Xi，基於字典Di利用
\\jer
選出最能逼近Xi的原子ds，稀疏係數向量α對應的值滿足as = ，s e Γ, Γ為字典Di中原子的下標集合；
步驟e:利用
= Xi^Xi, ds>ds
計算第t次迭代後的信號殘差rS 1彡t彡T，1彡i彡η，η為待分類數據總數， s e Γ，Γ為字典Di中原子的下標集合；
步驟f:若 rt> εst。p且t<T，更新
Xi = t = t+1
返回步驟d執行，否則執行步驟g，其中1 < i Sn，η為待分類數據總數，t為當前迭代次數；
步驟g:根據稀疏係數向量α確定鄰接矩陣W。其中若頂點i和j間的係數 O； "0，則數據Xi和~相似，權重％ =| < I;若i彡n，返回步驟C執行，否則執行步驟h，其中 Ι^ ^η,Ι^為待分類數據總數；
步驟h 利用W = W+W'將非對稱的鄰接矩陣W轉化對稱矩陣，W'為鄰接矩陣W的轉置矩陣，轉置矩陣為稀疏分解Itl圖；η
步驟2 利用S = D-172WD"172將鄰接矩陣W對稱地歸一化，其中D(W) = Σψν 『J=IΙ^ ^η,η為待分類數據總數；
步驟3:定義一個nXk的矩陣Y存儲所有待分類數據的初始標記信息，若有標記數據Xi屬於第j類，那麼Yij = 1，否則Yij = 0，對所有的未標記數據，令Yij = 0，其中 1彡i彡n，1彡j彡k，η為待分類數據總數，k為類別數；
步驟4 定義一個nXk的矩陣F(t)存儲第t次迭代所有待分類數據屬於每類的概率，初始化F(O) = Y，利用
F(t+1) = nSF(t) + (l- η)γ
讓每個樣本的標記信息迭代地向其近鄰樣本點傳播，直到收斂；t為迭代次數，n 指大量的信息是來自於其近鄰還是初始標記樣本信息，n ^ I，n為待分類數據總數，k 為類別數；
步驟5 記序列{F(t)}為步驟4迭代t次的結果，極限定義為廣，則利用
= arg max7St F*
求出數據Xi的類標，其中，巧是第i個樣本屬於第j類的概率，1彡i彡n，n為待分類數據總數，k為總類別數。
有益效果
本發明提出的一種基於稀疏分解Itl圖的局部全局一致性分類方法，有益效果是 充分利用稀疏分解能有效捕捉信號的各種結構特徵和內部屬性的特性，以及匹配追蹤的貪心選擇原理，提出了一種基於稀疏分解Itl圖的局部全局一致性分類方法，Itl構圖法能夠比較精確的確定出圖的鄰接結構和權重，從而使得局部全局一致性分類方法泛化能力和分類精度得到了提高。


圖1 是本發明方法的流程示意圖具體實施方式
現結合實施例、附圖對本發明作進一步描述
步驟1 稀疏分解1。圖的構造
步驟a 使用KMEANS聚類算法將整個待分類數據X劃分為k個子集，k為類別數；
步驟b 定義一個nXn的鄰接矩陣W，其元素初始化為0，η為待分類數據總數；
步驟c 以第i個待分類數據Xi為待分解信號，稀疏分解字典Di由Xi所屬聚類子集構成，Xi不包括在Di中，1 < i < η，η為待分類數據總數；
步驟d 預設最大迭代次數為T = 5，迭代終止誤差為ε stop = 0. 001，當前迭代次數t初始化為0，對待分解信號Xi，基於字典Di利用
權利要求
1. 一種基於稀疏分解Itl圖的局部全局一致性分類方法，其特徵在於步驟如下 步驟1稀疏分解Itl圖的構造步驟a 使用KMEANS聚類算法將整個待分類數據X劃分為k個子集，k為類別數； 步驟b 定義一個nXn的鄰接矩陣W，其元素初始化為0，η為待分類數據總數； 步驟c 以第i個待分類數據Xi為待分解信號，稀疏分解字典Di由Xi所屬聚類子集構成，Xi不包括在Di中，1 < i < η，η為待分類數據總數；步驟d 預設最大迭代次數為T，迭代終止誤差為ε stop,當前迭代次數t初始化為0，對待分解信號Xi，基於字WDi利用 |〈戈，式〉|= sup 丨〈 ·， I選出最能逼近Xi的原子ds，稀疏係數向量α對應的值滿足α s = ，s e Γ, Γ 為字典Di中原子的下標集合； 步驟e 利用Tt = Xi-iCxi, ds>ds計算第t次迭代後的信號殘差f，1彡t彡T，1彡i彡η，η為待分類數據總數，s e Γ, Γ為字典Di中原子的下標集合；步驟f 若rt> ￡_且1<1\更新Xi = r', t = t+1返回步驟d執行，否則執行步驟g，其中1 < i Sn，η為待分類數據總數，t為當前迭代次數；步驟g:根據稀疏係數向量α確定鄰接矩陣W。其中若頂點i和j間的係數…*0，則數據Xi和Xj相似，權重％ =I a) I;若i彡n，返回步驟c執行，否則執行步驟h，其中1彡i彡n， 1 ^ j ^ η, η為待分類數據總數；步驟h:利用W = W+W'將非對稱的鄰接矩陣W轉化對稱矩陣，W'為鄰接矩陣W的轉置矩陣，轉置矩陣為稀疏分解Itl圖；η步驟2 利用S = D-172WD-172將鄰接矩陣W對稱地歸一化，其中D(W) = ΣΚ ^ ^η,Mη為待分類數據總數；步驟3 定義一個nXk的矩陣Y存儲所有待分類數據的初始標記信息，若有標記數據Xi 屬於第j類，那麼Yij = 1，否則Yij = 0，對所有的未標記數據，令Yij = 0，其中1彡i彡n， 1 ^ j ^ k, η為待分類數據總數，k為類別數；步驟4 定義一個nXk的矩陣F(t)存儲第t次迭代所有待分類數據屬於每類的概率， 初始化F(O) =Y，利用F (t+i) = nSF(t) + (i- η)γ讓每個樣本的標記信息迭代地向其近鄰樣本點傳播，直到收斂；t為迭代次數，Il指大量的信息是來自於其近鄰還是初始標記樣本信息，η < 1，η為待分類數據總數，k為類別數；步驟5:記序列{F(t)}為步驟4迭代t次的結果，極限定義為廣，則利用 y,= BIgmaxjik F*求出數據Xi的類標，其中，巧是第i個樣本屬於第j類的概率，l^i^n, η為待分類數據總數，k為總類別數。
全文摘要
本發明涉及一種基於稀疏分解l0圖局部全局一致性分類方法。充分利用了稀疏分解可以有效捕捉信號的本質特徵和內在結構的特性，以及匹配追蹤的貪心選擇原理，根據稀疏分解係數向量確定出l0圖的鄰接結構和權值，並將其應用到局部全局一致性分類方法中。實驗結果表明，本發明與傳統的構圖法以及l1構圖法相比，能得到較好的分類結果。
文檔編號G06K9/62GK102509107SQ20111031105
公開日2012年6月20日 申請日期2011年10月13日 優先權日2011年10月13日
發明者張曉潔, 李映 申請人:西北工業大學