測(cè)試代價(jià)敏感粗糙集中屬性約簡(jiǎn)算法的研究.pdf

1、粗糙集是一種刻畫(huà)不完整和不確定性問(wèn)題的數(shù)學(xué)工具，其不需要任何先驗(yàn)知識(shí)對(duì)數(shù)據(jù)進(jìn)行分析和處理。面對(duì)如今高速的信息時(shí)代中海量數(shù)據(jù)的形成，粗糙集在分析處理數(shù)據(jù)中發(fā)揮了重要的作用。屬性約簡(jiǎn)作為粗糙集理論研究的重要內(nèi)容之一，其核心思想就是保證知識(shí)庫(kù)的分類(lèi)能力不變的前提下，刪除冗余、錯(cuò)誤或者不需要的知識(shí)。而代價(jià)敏感學(xué)習(xí)是目前機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域研究熱點(diǎn)之一，代價(jià)包括測(cè)試代價(jià)、誤分類(lèi)代價(jià)、計(jì)算代價(jià)和獲取樣本的代價(jià)等，其目的是以最小代價(jià)為目標(biāo)建立分類(lèi)

2、器。將代價(jià)敏感學(xué)習(xí)引入粗糙集理論中的屬性約簡(jiǎn)問(wèn)題值得深入研究，目前將誤分類(lèi)代價(jià)引入粗糙集理論中的相關(guān)研究取得了不錯(cuò)的研究的成果，而測(cè)試代價(jià)敏感粗糙集理論的相關(guān)研究近幾年才開(kāi)始發(fā)展。
　　本文主要研究測(cè)試代價(jià)敏感粗糙集中屬性約簡(jiǎn)問(wèn)題，分別以完備決策表和不完備決策表作為研究對(duì)象，主要的研究工作有以下幾個(gè)方面。
　　(1)為了解決測(cè)試代價(jià)敏感屬性約簡(jiǎn)的高效性和準(zhǔn)確性問(wèn)題，提出一種基于免疫量子粒子群優(yōu)化的最小測(cè)試代價(jià)屬性約簡(jiǎn)算法。依

3、據(jù)條件信息熵和測(cè)試代價(jià)因素定義適當(dāng)?shù)倪m應(yīng)值函數(shù)，將最小測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題轉(zhuǎn)化為0-1組合優(yōu)化問(wèn)題，提出最小屬性的屬性約簡(jiǎn)問(wèn)題是一種具有特殊測(cè)試代價(jià)的最小測(cè)試代價(jià)屬性約簡(jiǎn)問(wèn)題。最后結(jié)合量子粒子群和人工免疫方法給出約簡(jiǎn)算法，實(shí)驗(yàn)分別對(duì)比已有的最小屬性約簡(jiǎn)算法和測(cè)試代價(jià)敏感屬性約簡(jiǎn)算法，實(shí)驗(yàn)結(jié)果表明該算法是有效可行的。
　　(2)在不完備決策表中，給出高效的計(jì)算容差類(lèi)算法。提出不一致對(duì)象概念，研究不一致對(duì)象的性質(zhì)，根據(jù)其性質(zhì)給出在不一

4、致對(duì)象下的核屬性和屬性約簡(jiǎn)的定義并設(shè)計(jì)求核屬性算法。提出一個(gè)新的屬性重要性定義，最后依據(jù)新的屬性重要性定義設(shè)計(jì)一個(gè)最壞情況下時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(k|C|2|U|)和O（|U|）的啟發(fā)式屬性約簡(jiǎn)算法，其中k為條件屬性中缺省對(duì)象所產(chǎn)生的容差類(lèi)最大的個(gè)數(shù)。算法過(guò)程只需逐步要求容差類(lèi)的基數(shù)，大大減少了算法的計(jì)算過(guò)程。最后通過(guò)理論分析、實(shí)例分析和實(shí)驗(yàn)分析說(shuō)明該算法是高效和可行性的屬性約簡(jiǎn)算法，并且該算法同時(shí)適用于不一致不完備決策表和一

5、致不完備決策表，給不完備決策表屬性約簡(jiǎn)算法提供了新的方法。
　　(3)提出不完備決策表測(cè)試代價(jià)敏感屬性約簡(jiǎn)問(wèn)題，給出不一致對(duì)象集定義以及求解不一致對(duì)象集的算法。根據(jù)不一致對(duì)象的性質(zhì)改進(jìn)屬性重要性定義，考慮測(cè)試代價(jià)因素以及不一致對(duì)象個(gè)數(shù)的改變量給出一個(gè)新的屬性重要性的定義和屬性重要性中權(quán)重的設(shè)置方法，并給出屬性重要性的計(jì)算算法。在此基礎(chǔ)上，給出一個(gè)時(shí)間復(fù)雜度O(k|C|2|U|)和空間復(fù)雜度為O（|U|）啟發(fā)式屬性約簡(jiǎn)算法，其中k為