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

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

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

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

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