一、說明。
所謂決策表,類似於關系數據庫的二位數據表,形如:
4 3 0
1 0 1
8 1 0
1 2 0
1 2 1
7 3 1
7 4 0
排序後輸出:
1 0 1
1 2 0
1 2 1
4 3 0
7 3 1
7 4 0
8 1 0
二、問題由來。
決策表約簡是粗糙集的一個經典問題。
關於如何解釋粗糙集約簡問題,我有一個很簡單的解釋,不過不會在這裡寫出。
簡而言之約簡就是在保持原有數據集分類能力的前提下刪除冗余屬性。
粗糙集的創始者Pawlak有著一個近乎偏執的理念:知識就是分類。
完成分類是進一步完成粗糙集約簡的基礎。
所以針對如何分類就有了各種各樣的解法。
蠻力算法就是兩兩比較,完成分類,這個復雜度很高。
在這種情況下,先排序再分類是一個進步的方法。
當然排序的方法也很多,基數排序、快速排序都是排序,也的確都有人進行過嘗試。
我這裡的這個排序方法來自於《計算機學報》上的一篇《屬性序下的快速約簡算法》。
文章的作者當時發了兩篇文章,這篇約簡的文章建立在另外一篇《二維表快速排序的復雜度分析》之上。
這裡我只是簡單實現了原文算法。
三、實現代碼,只是想重復這個實驗,然後用我的方法與此相比較。
View Code四、實驗結果摘錄
所有實驗數據來自UCI數據庫。
實驗機器: i3 2100 + 4G + win7 32bit
VS 2012 32bit Release Mode
Forest CoverType
581012 條數據,每數據 54 條件屬性。
0.234s
Poker Hand
1025010 數據, 每數據 10條件屬性。
0.359s