====== GUHA asociační pravidlo ======

===== Asociační pravidlo =====
Asociační pravidla byla definována v devadesátých letech minulého století jako nástroj pro zkoumání chování 
zákazníků v supermarketech. Článek [[http://dl.acm.org/citation.cfm?doid=170035.170072&preflayout=flat| Mining association rules between sets of items in large databases]] 
je jedním z prvních článků na toto téma. Asociačním pravidlem se rozumí výraz X → Y kdy X a Y jsou 
disjunktní množiny položek vyskytujících se v nákupních košících. 
Asociační pravidlo {máslo, sýr} → {chléb} vyjadřuje fakt, že zákazníci nakupující máslo a sýr 
často nakupují i chléb. Myšlenka asociačních pravidel byla později zobecněna na matice dat. 
Asociačním pravidlem se tedy obvykle rozumí výraz A → S kde A i S jsou konjunkce dvojic atribut-hodnota. 
Příkladem je asociační pravidlo \\ 
**Vzdělání(//PhD//)** ∧ **Povolání(//ředitel//)** → **Příjem(//vysoký//)**.   

Konfidence asociačního pravidla A → S je podíl (počet řádků splňujících A i S)/(počet řádků splňujících S), podpora  pravidla A → S je podíl (počet řádků splňujících A i S)/(počet řádků matice dat). Úlohou dobývání asociačních pravidel se obvykle rozumí úloha nalezení všech asociačních pravidel jejichž konfidence i podpora jsou větší nebo rovny zadaným  mezím. 

===== Metoda GUHA a asociační pravidla =====

Koncept asociačního pravidla však byl definován a studován již v šedesátých letech minulého století v rámci vývoje metody GUHA. Článek  [[https://link.springer.com/article/10.1007/BF02345483|The GUHA method of automatic hypotheses determination]] byl jedním z prvních článků o metodě GUHA. Další články z počátků metody GUHA jsou k dispozici [[lm_guha_te_publikace#1966 - 1981|zde]]. Významným mezníkem ve vývoji metody GUHA je kniha 
[[https://www.springer.com/gp/book/9783540087380|Mechanizing hypothesis formation (Mathematical foundations for a general theory)]], která je k dispozici i ve formě [[http://www.cs.cas.cz/~hajek/guhabook/|internetové edice]]. 

Asociační pravidla byla v rámci vývoje metody GUHA zkoumána jako obecný vztah dvojice 
obecných booleovských atributů odvozených ze sloupců analyzované matice dat. Procedury ASSOC a IMPL byly 
vyvinuty jako nástroj pro dolování GUHA asociačních pravidel. Podrobnosti viz například [[https://www.sciencedirect.com/journal/international-journal-of-man-machine-studies/vol/10/issue/1|Special Issue on GUHA, Int. J. Man-Mach. Stud. 10 (1) (1978)]] a 
[[https://www.sciencedirect.com/journal/international-journal-of-man-machine-studies/vol/15/issue/3|Second Special Issue Int. J. Man-Mach. Stud. on GUHA]].

Taková asociační pravidla budeme nazývat // GUHA asociační pravidla// pokud budeme chtít zdůraznit, že se 
jedná o obecný vztah dvou odvozených booleovských atributů.  Pokud nebude nebezpečí nedorozumění, budeme používat výraz "asociační pravidlo" nebo pouze "pravidlo" i pro GUHA asociační pravidla. 


Od devadesátých let minulého století je GUHA rozvíjena jako metoda pro dobývání znalostí z databází, viz článek [[https://dl.acm.org/citation.cfm?id=1655709|The GUHA method and its meaning for data mining]].  

Podrobnosti o vztahu GUHA asociačních pravidel a asociačních pravidel jsou např. v článku [[https://content.iospress.com/articles/intelligent-data-analysis/ida160069|Apriori and GUHA – Comparing two approaches to data mining with association rules]]. Teorie vyvinutá pro GUHA asociační pravidla zahrnuje i speciální přístup k práci s [[lm_guha_te_missings|neúplnou informací]]. Jsou také k dispozici výsledky o [[lm_guha_te_oc_prehled|teoretických vlastnostech asociačních pravidel]].   
Dále používáme syntaxi zavedenou v knize [[http://link.springer.com/book/10.1007/978-3-642-11737-4|Observational Calculi and Association Rules]]. 


===== GUHA asociační pravidlo =====

 
GUHA asociačním pravidlem rozumíme výraz φ≈ψ, kde 
  * φ a ψ jsou [[lm_guha_te_bool|booleovské atributy]] které nemají společný atribut
  * ≈ je[[lm_guha_te_pravidlo#4ft-kvantifikátor| 4ft-kvantifikátor]]. 

Booleovský atribut φ se nazývá //antecedent//, ψ je //sukcedent// (//konsequent//). 

Určení, zda [[lm_guha_te_pravidlo#Asociační pravidlo je pravdivé v matici dat|GUHA asociační pravidlo φ≈ψ je pravdivé v matici dat M]] se provádí na základě [[lm_guha_te_pravidlo#4ft-tabulka|4ft-tabulky 4ft(φ,ψ,M)]].

Je možno pracovat i s [[lm_guha_te_pravidlo#Podmíněné asociační pravidlo|podmíněnými GUHA asociační pravidl]]y φ≈ψ/χ kde χ je booleovský atribut. 
===== 4ft-tabulka =====

//4ft-tabulkou// 4ft(φ,ψ,**M**) //antecedentu// φ a //sukcedentu// ψ //pro matici dat// **M** rozumíme čtveřici čísel ‹ //a//,//b//,//c//,//d// › kde 
  * //a// je počet řádků matice dat **M** splňujících oba booleovské atributy φ a ψ 
  * //b// je počet řádků matice dat **M** splňujících φ a nesplňujících ψ
  * //c// je počet řádků matice dat **M** nesplňujících φ a splňujících ψ
  * //d// je počet řádků matice dat **M** nesplňujících ani φ ani ψ.  

4ft-tabulka 4ft(φ,ψ,**M**) je často prezentována ve formě čtyřpolní tabulky dle následujícího obrázku. 
{{ :4ft_tabulka.png?150 |}}

===== 4ft-kvantifikátor =====

Symbol "≈" v GUHA asociačním pravidle φ≈ψ se nazývá 4ft-kvantifikátor. 
Definuje podmínku týkající se čtveřic  celých nezáporných čísel ‹ //a//,//b//,//c//,//d// ›. 
Podmínka definovaná 4ft-kvantifikátorem ≈ je formalizována pomocí //asociované funkce// F<sub>≈</sub> // 
4ft-kvantifikátoru// ≈ .  Funkce F<sub>≈</sub> přiřazuje každé  čtveřici nezáporných celých 
čísel \\ ‹ //a//,//b//,//c//,//d// › hodnotu 1 (pokud podmínka je splněna) nebo 0 (pokud podmínka není splněna). 

Příkladem je asociovaná funkce F<sub>→</sub> 4ft-kvantifikátoru → s konfidencí //C// a supportem //S//. Tato funkce je definována takto: 
  * F<sub>→</sub>(//a//,//b//,//c//,//d//) = 1 pokud platí zároveň jak  //a// / (//a//+//b//) ≥ //C// tak i //a// / (//a//+//b//+//c//+//d//) ≥ //S//
  * F<sub>→</sub>(//a//,//b//,//c//,//d//) = 0 v opačném případě. 

4ft-kvantifikátory implementované v GUHA proceduře 4ft-Miner jsou popsány [[lm_guha_te_4ft_kvantifikator|zde]]. 

Pojem asociované funkce kvantifikátoru byl definován v knize [[https://www.springer.com/gp/book/9783540087380|Mechanizing hypothesis formation (Mathematical foundations for a general theory)]] a je používán i v knize [[http://link.springer.com/book/10.1007/978-3-642-11737-4|Observational Calculi and Association Rules]]. Cílem je důsledně rozlišit mezi kvantifikátorem jako symbolem jazyka a jeho interpretací. 

Pokud nebude nebezpečí nedorozumění, nebudeme  pro jednoduchost dále rozlišovat 4ft-kvantifikátor od jeho asociované funkce. 4ft-kvantifikátor ≈ budeme tedy chápat i jako {0,1}-hodnotovou funkci definovanou pro čtveřice nezáporných celých čísel ‹ //a//,//b//,//c//,//d// ›.  To znamená například 
  * →(//a//,//b//,//c//,//d//) = 1 pokud platí zároveň jak  //a// / (//a//+//b//) ≥ //C// tak i //a// / (//a//+//b//+//c//+//d//) ≥ //S//
  * →(//a//,//b//,//c//,//d//) = 0 v opačném případě. 

===== Asociační pravidlo je pravdivé v matici dat=====

Pravdivost GUHA asociačního pravidla φ≈ψ  v matici dat **M** je definována pomocí 4ft-tabulky 4ft(φ,ψ,**M**) = 
 ‹//a//,//b//,//c//,//d//›: 
 
  * φ≈ψ je pravdivé v matici dat **M** pokud platí  ≈(//a//,//b//,//c//,//d//) = 1, formálně zapisujeme Val(φ≈ψ, **M**) = 1
  * φ≈ψ je nepravdivé v matici dat **M** pokud platí  ≈(//a//,//b//,//c//,//d//) = 0, formálně zapisujeme Val(φ≈ψ, **M**) = 0. 


===== Podmíněné asociační pravidlo =====

Podmíněné GUHA asociační pravidlo je výraz φ≈ψ/χ kde φ≈ψ je asociační pravidlo a χ je 
booleovský atribut který nazýváme podmínkou. Booleovský atribut χ nemá žádný společný atribut s 
booleovskými atributy φ a ψ. Intuitivní význam podmíněného pravidla  φ≈ψ/χ je, že  pokud je splněna podmínka χ, 
pak asociační pravidlo φ≈ψ je pravdivé. 
Jinými slovy, podmíněné asociační pravidlo φ≈ψ/χ je pravdivé v matici dat **M** pokud asociační pravidlo φ≈ψ je 
pravdivé v matici dat **M/χ**. 

Tomu odpovídá i definice:  
   * Podmíněné asociační pravidlo φ≈ψ/χ je pravdivé v matici dat **M** pokud je asociační pravidlo φ≈ψ pravdivé v matici dat **M/χ**. Formálně píšeme Val(φ≈ψ/χ, **M**) = 1. 
   
   * Podmíněné asociační pravidlo φ≈ψ/χ je nepravdivé v matici dat **M** pokud je asociační pravidlo φ≈ψ nepravdivé v matici dat **M/χ**. Formálně píšeme Val(φ≈ψ/χ, **M**) = 0. 

GUHA asociačním pravidlem nadále rozumíme jak pravidlo φ≈ψ, tak i podmíněné pravidlo φ≈ψ/χ.