Trzy przykłady problemów zapewne NP-trudnych z dziedzin przetwarzania i eksploracji danych

Prelegent(ci)

Dominik Ślęzak

Afiliacja

Uniwersytet Warszawski

Termin

21 marca 2014 14:15

Pokój

p. 5820

Seminarium

Research Seminar of the Logic Group: Approximate reasoning in data mining

---

Przedstawię przykłady trzech obszarów problemów optymalizacyjnych, które najprawdopodobniej są NP-trudne, lecz których NP-trudność nie jest jeszcze udowodniona.

 

Pierwszy przykład dotyczy wyznaczania z danych przybliżonych sieci Bayesowskich o minimalnej liczbie krawędzi, czyli minimalnych grafów acyklicznych, które kodują za pomocą d-separacji przybliżone niezależności warunkowe pomiędzy atrybutami, o zadanym stopniu przybliżenia wyznaczanym z danych.

 

Drugi przykład dotyczy ładowania danych do granularnej bazy danych typu Infobright, gdzie dane są przechowywane w paczkach powstałych w wyniku dekompozycji ze względu na atrybuty i podzbiory wierszy, a gdzie zależy nam na minimalizacji liczby paczek danych o zbyt heterogenicznej zawartości.

 

Trzeci przykład dotyczy wyznaczania z danych stabilnych podzbiorów atrybutów w formie przybliżonych reduktów decyzyjnych, które to podzbiory mają szansę pozostać reduktami na zadowalającym poziomie przybliżenia dla zmieniających się danych.

---