Pregled bibliografske jedinice broj: 1243036
On the complexity of redescription mining
On the complexity of redescription mining // Theoretical Computer Science, 944 (2023), 113673, 12 doi:10.1016/j.tcs.2022.12.023 (međunarodna recenzija, članak, znanstveni)
CROSBI ID: 1243036 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
On the complexity of redescription mining
Autori
Mihelčić, Matej ; Kurdija, Adrian Satja
Izvornik
Theoretical Computer Science (0304-3975) 944
(2023);
113673, 12
Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni
Ključne riječi
Data mining ; Redescription mining ; NP-completeness ; CLIQUE problem ; Set cover problem
Sažetak
Redescription mining is an important data mining task with the main goals of discovering subsets of instances that can be characterized in multiple ways and constructing the appropriate characterizations. Such characterizations, presented in a form of tuples of logical formulae, are understandable to the domain experts and offer unique insights in different interactions between relevant, presented attributes. In this work, we analyse variants of this task where the input data consists of one or more views – disjoint sets of attributes. The goal of this work is to formally define decision variants of redescription mining tasks with several sets of constraints and to provide corresponding proofs that the decision variants of these tasks are NP-complete. Proofs are realized by reductions from well known decision variants of CLIQUE and Set cover NP- complete problems. We also show that the enumeration variant of the task is NP-hard.
Izvorni jezik
Engleski
Znanstvena područja
Matematika, Računarstvo
Citiraj ovu publikaciju:
Časopis indeksira:
- Current Contents Connect (CCC)
- Web of Science Core Collection (WoSCC)
- Science Citation Index Expanded (SCI-EXP)
- SCI-EXP, SSCI i/ili A&HCI
- Scopus
