代價(jià)敏感屬性約簡(jiǎn)的歸并算法研究

《代價(jià)敏感屬性約簡(jiǎn)的歸并算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、困書分類號(hào)ＴＰ３學(xué)校代碼：１０６１５：朵喪／５襪樂(lè)費(fèi)ＩＩ攀位觀±擎?zhèn)幍挛模崳娬撐念}目代價(jià)敏感屬性約簡(jiǎn)的歸并算法研究碩±生姓名張愛(ài)婷第一導(dǎo)師姓名晚沒(méi)濱第二導(dǎo)師姓名圏ｊｉ專業(yè)學(xué)位類型工提專＃當(dāng)化工程領(lǐng)域名稱軟件工程研究方向數(shù)據(jù)挖掘二〇—六年六月西南石油大學(xué)研究生學(xué)位論文知識(shí)產(chǎn)權(quán)聲巧書及學(xué)位論文版權(quán)使用授權(quán)書，目Ｐ工本人完全了解學(xué)校有關(guān)保護(hù)知識(shí)產(chǎn)權(quán)的規(guī)定；研究生在校攻讀學(xué)位期間論文作的知識(shí)產(chǎn)權(quán)單位屬于西南石油大學(xué)。學(xué)校有權(quán)保留并向國(guó)家有關(guān)部口或機(jī)構(gòu)送交論文的復(fù)印件和電子版レッ將本學(xué)位論文的全部或部分。

2、本人允許論文被查閱和借閱。學(xué)?？?，可皆內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索、采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)一位論文，，律注明作者單。同時(shí)本人保證畢業(yè)后結(jié)合學(xué)位論文研究課題再撰寫的文章位為西南石油大學(xué)。本學(xué)位論文屬于１、保密（），在年解密后適用本授權(quán)書。２、不保密）（＼／＂＂（請(qǐng)?jiān)冢咨舷鄳?yīng)括號(hào)內(nèi)打Ｖ）學(xué)位論文作者簽名：指導(dǎo)教師簽名：曰／年＞曰如（年（月＾３。（月３西南石油大學(xué)研究生學(xué)位論文獨(dú)劍性聲明本人聲明：所呈交的研究生學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研巧工作及取得的。，研巧成果據(jù)我所知，除了文中特別加Ｗ標(biāo)注和致謝的地方

3、外本論文不包含其他人己經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含其他人為獲得西南石油大學(xué)或其它教育機(jī)構(gòu)的學(xué)一位或證書而使用過(guò)的材料。與我同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均己在論文中作了明確的說(shuō)明并表示謝意。學(xué)位論文作者簽名；年月、曰＾摘要數(shù)據(jù)挖掘又稱數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｉｎＤａｔａｂａｓｅ，ＫＤＤ），是目前人工智能和數(shù)據(jù)庫(kù)領(lǐng)域研究的熱點(diǎn)問(wèn)題，。在現(xiàn)實(shí)世界中數(shù)據(jù)集中存儲(chǔ)的屬性有幾十、幾百、甚至上千種。這些屬性中有很多是兀余的，它們會(huì)干擾數(shù)據(jù)挖掘的過(guò)程，也很大一一程度上會(huì)影響算法的效率。因此，人們提出了

4、屬性約簡(jiǎn)這預(yù)處理技術(shù)。另方面，現(xiàn)實(shí)世界中的行為或者事物都有各種代價(jià)，，如測(cè)試代價(jià)、誤分類代價(jià)、延遲代價(jià)等涉及金錢、時(shí)間、人工等方面的開銷。代價(jià)敏感學(xué)習(xí)致力于涉及各類代價(jià)的挖掘問(wèn)題。’當(dāng)前被研究的代價(jià)敏感屬性約簡(jiǎn)問(wèn)題包括：最小測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題、簡(jiǎn)單公共測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題、最小測(cè)試時(shí)間代價(jià)問(wèn)題等。人們將不同算法框架應(yīng)用于這些具體問(wèn)題。啟發(fā)式算法的速度很快，但是由于它們常常會(huì)收斂于局部最優(yōu)解，因此正確率。不高?；厮菟惴m然能夠保證找到最優(yōu)解，但是運(yùn)行時(shí)間往往不能被接受仿生算法也、常常能找到最優(yōu)解，不過(guò)其耗費(fèi)的時(shí)間代價(jià)過(guò)大。最近還有學(xué)者提出半貪屯

5、算法，能夠一定時(shí)間內(nèi)得到較好的結(jié)果在。一本文將分治算法與回溯算法相結(jié)合，提出種歸并算法，Ｗ改善回溯算法的不足。本文的歸并算法包含Ｈ個(gè)關(guān)鍵技術(shù)：分組與合并、回溯算法、Ｗ及競(jìng)爭(zhēng)機(jī)制。該算法先一些屬性子集組的大小對(duì)算法的性能有很大的影響將屬性隨機(jī)分組，得到，ｇ。在極端情況下，，組的大小與屬性數(shù)目相同的情況下歸并算法將退回為回溯算法。屬性子集通過(guò)回溯算法得到屬性子集的約簡(jiǎn)一，然后將每對(duì)相鄰的約簡(jiǎn)合并成個(gè)新的屬性子集。重復(fù)Ｗ上過(guò)程直到只剩一個(gè)屬性子集，這個(gè)屬性子集的約簡(jiǎn)就是原問(wèn)題的約簡(jiǎn)。屬性分組，后，全局重要的屬性可能在局部約簡(jiǎn)時(shí)被刪除導(dǎo)致歸并算法得到

6、的解不是全局最優(yōu)解。因此我們采用競(jìng)爭(zhēng)機(jī)制，運(yùn)行歸并算法Ｐ次，得到Ｐ個(gè)解，再?gòu)倪@Ｐ個(gè)解中選取最優(yōu)解。本文將該算法運(yùn)用于最小測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題、簡(jiǎn)單公共測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題ｅｒｓ－及最小測(cè)試時(shí)間代價(jià)問(wèn)題這Ｈ個(gè)問(wèn)題。并使用來(lái)自ＵＣＩ（ＵｎｉｖｉｔｙｏｆＣａｌｉｆｏｒｎｉａＩｒｖｉｎｅ）數(shù)據(jù)庫(kù)中的四個(gè)真實(shí)數(shù)據(jù)集對(duì)提出的歸并算法進(jìn)行實(shí)驗(yàn)。其中每種數(shù)據(jù)集使用了Ｈ種不同分布的測(cè)試代價(jià)。通過(guò)實(shí)驗(yàn)我們得知：競(jìng)爭(zhēng)機(jī)制能有效提高結(jié)果的質(zhì)量；對(duì)于不同問(wèn)題，Ｐ值大于６之后算法結(jié)果趨于穩(wěn)定；最優(yōu)ｇ值對(duì)于不同情況略有不同，在最小測(cè)試代價(jià)問(wèn)題中為６，簡(jiǎn)單公共測(cè)試代價(jià)、

7、最小測(cè)試時(shí)間代價(jià)問(wèn)題中均為７。與現(xiàn)有的啟發(fā)式算法、蟻群算法和回溯算法相比，歸并算法在保持較高的正確率的情況下，一能夠大大縮短運(yùn)行時(shí)間，本文提出的歸并算法是針對(duì)該類問(wèn)題的種有效并且高。因此效的算法。關(guān)鍵詞：代價(jià)敏感學(xué)習(xí)；粗糖集；屬性約簡(jiǎn)；分治；回溯算法；競(jìng)爭(zhēng)機(jī)制ＡｂｓｔｒａｃｔＤａｔａｍｉ打ｉｎｇ，ａｌｓｏｋｎｏｗｎａｓｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙｉｎｄａｔａｂａｓｅｓ（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｉｎＤａｔａｂａｓｅＫＤＤｌｉｆｉｌｌｉｉｓｃｕｒｒｅｎ