Neúplná informace

Zpracování neúplné informace je jeden z důležitých problémů data mining. Při vývoji metody GUHA byl tento problém řešen od sedmdesátých let minulého století, viz např. články The GUHA method and the three-valued logic a Ein Beitrag zu der GUHA Methode in der dreiwertigen Logik. Důležité výsledky o neúplné informaci jsou shrnuty v monografii Mechanizing Hypothesis Formation (Mathematical Foundations for a General Theory), některé další výsledky jsou i v monografii Observational Calculi and Association Rules. Porovnání přístupů k neúplné informací v proceduře 4ft-Miner a v arules package v systému R je v článku Apriori and GUHA – Comparing two approaches to data mining with association rules, viz též příklad.

Nejdůležitějším výsledkem je zabezpečený přístup k neúplné informaci, kdy je asociační pravidlo považováno za pravdivé v matici dat s neúplnou informací, pokud je pravdivé ve všech možných doplněních matice skutečnými hodnotami.

Alternativním přístupem k neúplné informaci je optimistické doplnění. V souvislosti s metodou GUHA se používá i vynechání neúplné informace. V proceduře 4ft-Miner je implementován i přístup ignorování neúplné informace implementovaný v arules package, který je součástí systému R.

Zvláštní pozornost v souvislosti s neúplnou informací je věnována podmíněným asociačním pravidlům.

Zabezpečený přístup k neúplné informaci vychází z pojmů matice dat s neúplnou informací a doplnění matice dat s neúplnou informací. V levé části následujícího obrázku je ukázka matice dat s neúplnou informací, chybějící hodnoty se značí X. V pravé části doplnění této matice, všechny chybějící hodnoty jsou nahrazeny přípustnými hodnotami.

Zabezpečený přístup k neúplné informaci se týká všech formulí Φ souvisejících s asociačními pravidly, tedy základních booleovských atributů, odvozených booleovských atributů i asociačních pravidel. Určuje se hodnota formule Φ v matici dat M^X s neúplnou informací, každá formule nabývá jednu z hodnot 0, 1, X. Hodnota formule Φ v matici dat M^X s neúplnou informací je

• 1, pokud je hodnota této formule 1 v každém doplnění matice M^X
• 0, pokud je hodnota této formule 0 v každém doplnění matice M^X
• X jindy, tedy pokud existují doplnění M₁ a M₂ matice M^X tak, že
  • hodnota formule Φ v M₁ je 1
  • hodnota formule Φ v M₂ je 0.

Podrobnosti o určení hodnot v matici dat s neúplnou informací

• pro základní a odvozené booleovské atributy jsou zde
• pro asociační pravidla jsou ve formě úvah a příkladů zde, formálnější popis je zde.

Podstatou optimistického doplnění je, že asociační pravidlo je považováno za pravdivé v matici dat s neúplnou informací, pokud je pravdivé alespoň v jednom doplnění této matice. Podrobnosti jsou uvedeny zde.

Podstatou vynechání neúplné informace je, že se pro verifikaci využije čtyřpolní tabulka vzniklá z devítipolní tabulky vynecháním polí, která se týkají chybějící informace. Podrobnosti jsou zde.

Při zpracování se neúplná informace ignoruje v tom smyslu, že kód chybějící hodnoty X se považuje za speciální kategorii. Tato kategorie zůstává skryta a nelze ji použít při zadání relevantních koeficientů. Podrobnosti jsou zde.

Pro podmíněná asociační pravidla φ≈ψ/χ je možno s jistým, dále popsaným omezením, používat všechny čtyři možnosti práce s neúplnou informací jako pro nepodmíněná pravidla φ≈ψ. Rozdíl je v tom, že verifikace podmíněného asociačního pravidla v matici dat M^X s neúplnou nevychází z devítipolní tabulky 9ft(φ,ψ,M^X), ale ze dvou devítipolních tabulek 9ft(φ,ψ,M^X/χ₁) a 9ft(φ,ψ,M^X/χ_X), viz následující obrázek.

Devítipolní tabulka 9ft(φ,ψ,M^X/χ₁) se týká trojhodnotových atributů φ a ψ v matici dat M^X/χ₁, která se skládá ze všech řádku matice M^X, pro které je atribut χ pravdivý. Tedy f_1,1,1 je počet řádků matice M^X pro které jsou atributy φ, ψ i χ pravdivé; f_1,X,1 je počet řádků matice M^X pro které jsou atributy φ a χ pravdivé a atribut ψ nabývá hodnotu X, atd.

Devítipolní tabulka 9ft(φ,ψ,M^X/χ_X) se týká trojhodnotových atributů φ a ψ v matici dat M^X/χ_X, která se skládá ze všech řádku matice M^X, pro které atribut χ nabývá hodnotu X. Tedy f_1,1,X je počet řádků matice M^X pro které jsou atributy φ a ψ pravdivé a atribut χ nabývá hodnotu X; f_1,X,X je počet řádků matice M^X pro které je atribut φ pravdivý a atributy ψ a χ nabývají hodnotu X, atd.

Z těchto devítipolních tabulek se vypočítá čtyřpolní tabulka pro verifikaci v závislosti na tom, zda se jedná o zabezpečené doplnění, optimistické doplnění, vynechání neúplné informace nebo ignorování neúplné informace.

V případě zabezpečeného doplnění je podmíněné asociační pravidlo považováno za pravdivé v matici dat s neúplnou informací, pokud je pravdivé ve všech možných doplněních matice skutečnými hodnotami. Podrobnosti jsou zde.

Při optimistickém doplnění je podmíněné asociační pravidlo považováno za pravdivé v matici dat s neúplnou informací, pokud je pravdivé alespoň v jednom doplnění této matice. Podrobnosti jsou zde.

Podstatou vynechání neúplné informace je, že se pro verifikaci využije čtyřpolní tabulka vzniklá vynecháním polí, která se týkají chybějící informace. Podrobnosti jsou zde.

Při zpracování se neúplná informace ignoruje v tom smyslu, že kód chybějící hodnoty X se považuje za speciální kategorii. Tato kategorie zůstává skryta a nelze ji použít při zadání relevantních koeficientů. Podrobnosti jsou zde.