代價約束下的屬性選擇問題.pdf

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

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

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

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

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