粗集決策表屬性約簡(jiǎn)算法的研究.pdf

1、Roughsets是Pawlak提出的一種處理模糊和不確定性的數(shù)學(xué)工具，在粗糙集的各種研究方向中，屬性約簡(jiǎn)算法一直是粗糙集理論研究的重點(diǎn)問題。 本文在Roughsets理論基礎(chǔ)上，對(duì)決策表屬性約簡(jiǎn)算法進(jìn)行了初步系統(tǒng)的研究，針對(duì)決策表屬性約簡(jiǎn)算法存在的三個(gè)問題：求決策表全部屬性約簡(jiǎn)和求決策表最小屬性約簡(jiǎn)是NP難題，及現(xiàn)有Rough集決策表約簡(jiǎn)算法計(jì)算的低效性，在一定程度上限制了Rough集的廣泛應(yīng)用；給出了相應(yīng)的解決算法：第一，給

2、出了基于格Hasse圖的寬度優(yōu)先搜索算法，該算法采用啟發(fā)式搜索策略能得到?jīng)Q策表的全部約簡(jiǎn)，與在原問題上求解相比，大大降低了求解問題的復(fù)雜度；第二，重新定義了屬性的重要度，在此基礎(chǔ)上給出了一種基于差別矩陣的最小屬性約簡(jiǎn)算法，該算法具有多項(xiàng)式時(shí)間復(fù)雜度，在最壞的情況下時(shí)間復(fù)雜度為min(O(|C|2|U|4)，O(|C|222|C|))；最后給出了一種快速約簡(jiǎn)算法，使其時(shí)間復(fù)雜度降低為O(|C||U|2)其中，|C|為條件屬性的個(gè)數(shù)，|U|