Non-redundant implicational base of formal context with constraints using SAT
An implicational base is knowledge extracted from a formal context. The implicational base of a formal context consists of attribute implications which are sound, complete, and non-redundant regarding to the formal context. Non-redundant means that each attribute implication in the implication base...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2024-01-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-1806.pdf |
| _version_ | 1797332398000570368 |
|---|---|
| author | Taufiq Hidayat Asmala Ahmad Hea Choon Ngo |
| author_facet | Taufiq Hidayat Asmala Ahmad Hea Choon Ngo |
| author_sort | Taufiq Hidayat |
| collection | DOAJ |
| description | An implicational base is knowledge extracted from a formal context. The implicational base of a formal context consists of attribute implications which are sound, complete, and non-redundant regarding to the formal context. Non-redundant means that each attribute implication in the implication base cannot be inferred from the others. However, sometimes some attribute implications in the implication base can be inferred from the others together with a prior knowledge. Regarding knowledge discovery, such attribute implications should be not considered as new knowledge and ignored from the implicational base. In other words, such attribute implications are redundant based on prior knowledge. One sort of prior knowledge is a set of constraints that restricts some attributes in data. In formal context, constraints restrict some attributes of objects in the formal context. This article proposes a method to generate non-redundant implication base of a formal context with some constraints which restricting the formal context. In this case, non-redundant implicational base means that the implicational base does not contain all attribute implications which can be inferred from the others together with information of the constraints. This article also proposes a formulation to check the redundant attribute implications and encoding the problem into satisfiability (SAT) problem such that the problem can be solved by SAT Solver, a software which can solve a SAT problem. After implementation, an experiment shows that the proposed method is able to check the redundant attribute implication and generates a non-redundant implicational base of formal context with constraints. |
| first_indexed | 2024-03-08T07:49:36Z |
| format | Article |
| id | doaj.art-2ed16507b94845938785edda57881020 |
| institution | Directory Open Access Journal |
| issn | 2376-5992 |
| language | English |
| last_indexed | 2024-03-08T07:49:36Z |
| publishDate | 2024-01-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj.art-2ed16507b94845938785edda578810202024-02-02T15:05:19ZengPeerJ Inc.PeerJ Computer Science2376-59922024-01-0110e180610.7717/peerj-cs.1806Non-redundant implicational base of formal context with constraints using SATTaufiq Hidayat0Asmala Ahmad1Hea Choon Ngo2Faculty of Information and Communication Technology, Universiti Teknikal Malaysia Melaka, Melaka, MalaysiaFaculty of Information and Communication Technology, Universiti Teknikal Malaysia Melaka, Melaka, MalaysiaFaculty of Information and Communication Technology, Universiti Teknikal Malaysia Melaka, Melaka, MalaysiaAn implicational base is knowledge extracted from a formal context. The implicational base of a formal context consists of attribute implications which are sound, complete, and non-redundant regarding to the formal context. Non-redundant means that each attribute implication in the implication base cannot be inferred from the others. However, sometimes some attribute implications in the implication base can be inferred from the others together with a prior knowledge. Regarding knowledge discovery, such attribute implications should be not considered as new knowledge and ignored from the implicational base. In other words, such attribute implications are redundant based on prior knowledge. One sort of prior knowledge is a set of constraints that restricts some attributes in data. In formal context, constraints restrict some attributes of objects in the formal context. This article proposes a method to generate non-redundant implication base of a formal context with some constraints which restricting the formal context. In this case, non-redundant implicational base means that the implicational base does not contain all attribute implications which can be inferred from the others together with information of the constraints. This article also proposes a formulation to check the redundant attribute implications and encoding the problem into satisfiability (SAT) problem such that the problem can be solved by SAT Solver, a software which can solve a SAT problem. After implementation, an experiment shows that the proposed method is able to check the redundant attribute implication and generates a non-redundant implicational base of formal context with constraints.https://peerj.com/articles/cs-1806.pdfImplicational baseFormal contextSAT problemAttribute implicationFormal concept analysis |
| spellingShingle | Taufiq Hidayat Asmala Ahmad Hea Choon Ngo Non-redundant implicational base of formal context with constraints using SAT PeerJ Computer Science Implicational base Formal context SAT problem Attribute implication Formal concept analysis |
| title | Non-redundant implicational base of formal context with constraints using SAT |
| title_full | Non-redundant implicational base of formal context with constraints using SAT |
| title_fullStr | Non-redundant implicational base of formal context with constraints using SAT |
| title_full_unstemmed | Non-redundant implicational base of formal context with constraints using SAT |
| title_short | Non-redundant implicational base of formal context with constraints using SAT |
| title_sort | non redundant implicational base of formal context with constraints using sat |
| topic | Implicational base Formal context SAT problem Attribute implication Formal concept analysis |
| url | https://peerj.com/articles/cs-1806.pdf |
| work_keys_str_mv | AT taufiqhidayat nonredundantimplicationalbaseofformalcontextwithconstraintsusingsat AT asmalaahmad nonredundantimplicationalbaseofformalcontextwithconstraintsusingsat AT heachoonngo nonredundantimplicationalbaseofformalcontextwithconstraintsusingsat |