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

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

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

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

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