基于HSIC的多標簽圖數(shù)據(jù)特征選擇算法研究.pdf

1、作為一種最常用的數(shù)據(jù)結構之一，圖可以用來表示數(shù)據(jù)對象之間的復雜關系，廣泛的應用于許多領域。因為圖的這些優(yōu)勢，基于圖的圖數(shù)據(jù)分類是圖數(shù)據(jù)挖掘研究領域的一個重要分支。在實際應用中，每個圖數(shù)據(jù)都會同時具有多個標簽集。并且通常在需要處理的多標簽數(shù)據(jù)中，都存在著大量冗余的、不相干的特征數(shù)據(jù)。對這些數(shù)據(jù)的處理可能會耗費大量時間，并且降低分類性能。因此多標簽數(shù)據(jù)通常應該先進行特征選取，再進行分類。然而，傳統(tǒng)分類方法把主要研究方向放在單標簽分類（二分類

2、）問題上，它明確或模糊的假設每一個圖只有一個標簽。對于單標簽分類問題，傳統(tǒng)特征選取方法可以擴展并用于找出單標簽圖數(shù)據(jù)集中的最具價值的子圖特征。但是在多標簽分類問題上，每一個圖擁有多個標簽，多個特征子圖集需要挖掘，因此傳統(tǒng)特征選取算法無法直接用于多標簽特征選擇。
　　本文算法根據(jù)圖的多個標簽之間存在某種相關聯(lián)性特點，基于HSIC（Hilbert-Schmidt Independence Criterion）評估標準，提出了一種用于評

3、估多標簽子圖特征集有用性的評估標準。主要研究內(nèi)容如下：
　　（1）針對在現(xiàn)實應用中，訓練圖集的子圖特征數(shù)量非常多的問題。為了避免詳細列舉子圖，從而導致算法時間復雜度過高。我們把評估標準加到子圖模式挖掘步驟中，設定一個上界值作為約束，通過約束修剪搜索空間。因此，在第四章我們根據(jù)圖的多個標簽之間的關聯(lián)性提出了一種上界值的計算方法。
　?。?）針對多標簽圖數(shù)據(jù)的特點，即一個樣本屬于多個類別。提出了一種基于HSIC評估標準的多標簽圖

4、數(shù)據(jù)特征選取算法，用來評估樣本和標簽的相關性。隨后將這個評估標準加到子圖模式挖掘步驟中，在對搜索空間進行遍歷的過程中對子圖進行評估，達到特征選取的目的。
　?。?）針對提出的多標簽特征選擇算法，本文提出了一種交替最優(yōu)化算法解決算法最優(yōu)化問題。在算法的目標方程中有子圖 g和標簽權重β兩個變量，但是前人的研究表明并不存在它的全局最優(yōu)結果。所以本文采用交替最優(yōu)化算法，先固定變量β對g進行優(yōu)化，選擇最優(yōu)的t個子圖。然后固定變量g對β進行優(yōu)