Monotonic Reducts Generation Using Fbhash in Rough Set

利用前後雜湊產生粗糙集合單調縮減集

在粗糙集合中，縮減集扮演著利用最少的屬性集合保留資料表原始知識，過去的文獻提出許多不同的縮減集，而用於產生這些縮減集最普遍的方法是利用區別矩陣，而利用區別矩陣來產生縮減集與核心最大的限制是沒有效能。為了設計一個縮減集的產生方法來涵蓋先前文獻所提及縮減集，本篇文章中提出一個先前文獻縮減集的宇集合，稱為單調縮減集。本篇文章提出一個特殊的雙向雜湊方法來計算單調縮減集，在無需任何前提假設下，先前文獻所涵蓋縮減集如確定縮減集、可能縮減集、S-縮減集、通用縮減集以及μ-決策縮減集均可在O(k2n)時間複雜度與O(kn)空間複雜度來產生，而k為屬性個數，n為資料筆數。縮減集的核心亦可在O(kn)時間複雜度與O(kn)空間複雜度來產生。除了本文所涵蓋之縮減集，凡是縮減集的定義滿足本文所提之單調縮減集，也可以用本文所提的方法來產生。相較於先前文獻所提之方法，向前向後雜湊的方法是簡單、具效能、可量度並適用於任何系統。

In Rough Set, reducts serve to preserve the same level of determinism of the table with a minimal number of attributes. Different reducts have been proposed in previous literatures and many of them are generated using the discernibility matrix. However, one of the major limitations using the discernibility matrix is its inefficiency in generating reducts and the core. In this paper, the generation of monotonic reducts, a superset of some previ-ously proposed reducts, is presented. To compute the monotonic reduct, a special two-way hashing mechanism, forward and backward, is proposed. With no prerequisites needed, the generation of monotonic reducts, like certain reducts, possible reducts, S-reducts, generalized reducts, and μ-decision reducts, takes O(k2n) time with O(kn) space using the fbHash, where n is the total number of instances and k is the number of attributes while the generation of core takes O(k2n) time with O(kn) space. fbHash is also applicable to other types of reducts if they meet the definition of the monotonic reduct. Compared with other computations proposed in previous liter-atures, the fbHash algorithm is simple, efficient, scalable, and applicable to every system.