基于集合枚舉樹的最小屬性約簡算法

成都信息工程學(xué)院 軟件工程學(xué)院，成都 610225

JIANG Yu

成都信息工程學(xué)院 軟件工程學(xué)院，成都 610225

College of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China

粗糙集理論是由波蘭學(xué)者Pawlak于1982年提出的[1-2]，是一種刻劃具有不完整性和不確定性信息的全新數(shù)學(xué)工具。其主要思想是在保證知識(shí)庫的分類能力不變的前提下，通過知識(shí)約簡導(dǎo)出問題的決策或分類規(guī)則。知識(shí)約簡問題是粗糙集理論的一個(gè)核心問題[3-4]。所謂知識(shí)約簡，就是在保證知識(shí)庫分類能力不變的條件下刪除其中不相關(guān)或不重要的冗余知識(shí)。

一般來講，一個(gè)決策表的屬性約簡不是唯一的，通常人們往往希望能夠找到一個(gè)冗余度最小的屬性約簡，該屬性約簡被稱為最小屬性約簡。對(duì)任一給定決策表，若屬性約簡算法能確保找到其最小屬性約簡，則該算法稱為最小屬性約簡完備算法。然而，S.K.M Wong和W.Ziarko已經(jīng)證明了找一個(gè)決策表的最小約簡是NP-hard問題[3]。導(dǎo)致NP-hard問題的主要原因是屬性的組合爆炸問題。目前已存在一些屬性約簡算法能夠找到?jīng)Q策表的最小屬性約簡[4-12]，但它們要么不是完備的最小屬性約簡算法，要么通過窮舉求出問題的所有約簡或所有最小約簡。

本文重新定義了屬性重要度，給出了條件屬性集上的序關(guān)系，基于該序關(guān)系構(gòu)建集合枚舉樹，提出了一種基于集合枚舉樹的最小屬性約簡算法。該算法采用至頂向下、層優(yōu)先搜索策略遍歷集合枚舉樹從而找到最小屬性約簡。為了減少搜索空間，提高算法效率，該算法采用了兩種剪枝策略剪去集合枚舉樹中冗余節(jié)點(diǎn)。……