代價(jià)約束下的屬性選擇問(wèn)題.pdf

1、實(shí)際生活中存在各種代價(jià)，包括測(cè)試代價(jià)、誤分類代價(jià)、計(jì)算代價(jià)和延遲代價(jià)等。測(cè)試數(shù)據(jù)需要付出一定代價(jià)，我們稱之為測(cè)試代價(jià)。這些代價(jià)包括金錢、時(shí)間和其它各種資源。當(dāng)我們對(duì)實(shí)例做出錯(cuò)誤分類的時(shí)候，同樣也需要付出代價(jià)。這些由錯(cuò)誤分類造成的代價(jià)，我們稱之為誤分類代價(jià)。等待而沒(méi)有做有意義的事情所浪費(fèi)的時(shí)間，我們稱為延遲代價(jià)。代價(jià)敏感學(xué)習(xí)問(wèn)題逐漸成為研究的熱點(diǎn)。
　　在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中，約束滿足問(wèn)題是一類常見(jiàn)而有意義的問(wèn)題。在各個(gè)方面，如金融

2、經(jīng)濟(jì)、組合數(shù)學(xué)，計(jì)算復(fù)雜性理論、密碼安全學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中約束滿足問(wèn)題的變類得到廣泛的應(yīng)用。正是因?yàn)楝F(xiàn)實(shí)世界中各種代價(jià)的存在，而很多時(shí)候我們的資源是有限的，我們所能夠承擔(dān)的代價(jià)并不能滿足完成所有的測(cè)試或者其他代價(jià)的要求。如何利用有限的資源來(lái)盡量的完成測(cè)試需求或者其他方面需求的問(wèn)題，正受到越來(lái)越多的研究人員的關(guān)注和研究分析。目前，已有不少研究者做了部分約束滿足方面的研究工作，通過(guò)定義不同的約束條件來(lái)研究代價(jià)敏感約束滿足問(wèn)題。
　　

3、代價(jià)敏感學(xué)習(xí)是數(shù)據(jù)挖掘的研究熱點(diǎn)，約束滿足問(wèn)題是人工智能和機(jī)器學(xué)習(xí)領(lǐng)域著名的問(wèn)題之一。因此本文利用粗糙集知識(shí)研究這兩個(gè)熱點(diǎn)問(wèn)題，提出了代價(jià)約束下的屬性選擇問(wèn)題。研究目標(biāo)是處理不同類型數(shù)據(jù)模型的代價(jià)敏感約束滿足問(wèn)題以及獲得不同的約束條件下的高效解決算法。
　　本文主要分為兩大部分。
　　第一部分詳細(xì)研究了基于代價(jià)敏感粗糙集理論的名詞性數(shù)據(jù)的屬性選擇問(wèn)題。首先，我們提出了在時(shí)間代價(jià)約束下的隨機(jī)算法來(lái)處理名詞性數(shù)據(jù)的屬性選擇問(wèn)題。

4、時(shí)間代價(jià)約束是算法設(shè)計(jì)的一個(gè)主要目標(biāo)，主要是為了在盡可能短的時(shí)間內(nèi)獲得良好的實(shí)驗(yàn)結(jié)果。
　　其次，為了進(jìn)一步降低算法的運(yùn)行時(shí)間，我們?cè)诳焖匐S機(jī)算法的基礎(chǔ)上提出了重啟策略優(yōu)化的隨機(jī)算法來(lái)解決最小測(cè)試代價(jià)屬性選擇問(wèn)題。實(shí)驗(yàn)結(jié)果表明重啟策略優(yōu)化的隨機(jī)算法在單位時(shí)間內(nèi)能夠獲得最優(yōu)的屬性子集。重啟策略優(yōu)化的隨機(jī)算法在處理大規(guī)模數(shù)據(jù)集有著突出的表現(xiàn)，不足之處就是算法在固定實(shí)驗(yàn)次數(shù)的情況下，實(shí)驗(yàn)結(jié)果差于啟發(fā)式算法。
　　在處理名詞性數(shù)據(jù)的

5、屬性選擇問(wèn)題的最后一部分，我們提出了代價(jià)約束下的屬性選擇問(wèn)題，首次考慮了測(cè)試代價(jià)和誤分類代價(jià)對(duì)于約束問(wèn)題的影響?；跍y(cè)試代價(jià)和誤分類代價(jià)對(duì)代價(jià)約束下屬性選擇問(wèn)題的影響，我們提出了一類新的啟發(fā)式算法。實(shí)驗(yàn)結(jié)果表明，我們?cè)O(shè)計(jì)的算法能夠在代價(jià)約束下獲得不錯(cuò)的效果。
　　第二部分詳細(xì)研究了同時(shí)考慮測(cè)試代價(jià)和誤分類代價(jià)這兩類代價(jià)的數(shù)值型數(shù)據(jù)的代價(jià)約束屬性選擇問(wèn)題。在處理數(shù)值型數(shù)據(jù)的問(wèn)題上我們采用了鄰域粗糙集的相關(guān)知識(shí)。通過(guò)計(jì)算對(duì)象的不一致對(duì)