Efficient Breadth-First Reduct Search
This paper formulates the problem of determining all reducts of an information system as a graph search problem. The search space is represented in the form of a rooted graph. The proposed algorithm uses a breadth-first search strategy to search for all reducts starting from the graph root. It expan...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-05-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/5/833 |
| _version_ | 1827716439737368576 |
|---|---|
| author | Veera Boonjing Pisit Chanvarasuth |
| author_facet | Veera Boonjing Pisit Chanvarasuth |
| author_sort | Veera Boonjing |
| collection | DOAJ |
| description | This paper formulates the problem of determining all reducts of an information system as a graph search problem. The search space is represented in the form of a rooted graph. The proposed algorithm uses a breadth-first search strategy to search for all reducts starting from the graph root. It expands nodes in breadth-first order and uses a pruning rule to decrease the search space. It is mathematically shown that the proposed algorithm is both time and space efficient. |
| first_indexed | 2024-03-10T19:41:39Z |
| format | Article |
| id | doaj.art-4f22a29256ab432da1eb07c1a1e95fee |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T19:41:39Z |
| publishDate | 2020-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-4f22a29256ab432da1eb07c1a1e95fee2023-11-20T01:12:45ZengMDPI AGMathematics2227-73902020-05-018583310.3390/math8050833Efficient Breadth-First Reduct SearchVeera Boonjing0Pisit Chanvarasuth1Department of Computer Engineering, Faculty of Engineering, King Mongkut’s Institute of Technology Ladkrabang, Ladkrabang, Bangkok 10520, ThailandSchool of Management Technology, Sirindhorn International Institute of Technology, Thammasat University, Pathum Thani, Bangkok 10200, ThailandThis paper formulates the problem of determining all reducts of an information system as a graph search problem. The search space is represented in the form of a rooted graph. The proposed algorithm uses a breadth-first search strategy to search for all reducts starting from the graph root. It expands nodes in breadth-first order and uses a pruning rule to decrease the search space. It is mathematically shown that the proposed algorithm is both time and space efficient.https://www.mdpi.com/2227-7390/8/5/833reductsubsetfeature selectionbreadth-first searchrooted graph |
| spellingShingle | Veera Boonjing Pisit Chanvarasuth Efficient Breadth-First Reduct Search Mathematics reduct subset feature selection breadth-first search rooted graph |
| title | Efficient Breadth-First Reduct Search |
| title_full | Efficient Breadth-First Reduct Search |
| title_fullStr | Efficient Breadth-First Reduct Search |
| title_full_unstemmed | Efficient Breadth-First Reduct Search |
| title_short | Efficient Breadth-First Reduct Search |
| title_sort | efficient breadth first reduct search |
| topic | reduct subset feature selection breadth-first search rooted graph |
| url | https://www.mdpi.com/2227-7390/8/5/833 |
| work_keys_str_mv | AT veeraboonjing efficientbreadthfirstreductsearch AT pisitchanvarasuth efficientbreadthfirstreductsearch |