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

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

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

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

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

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