Asociační analýza

Asociační analýza v oblasti dobývání znalostí z databází je metoda nalézání asociačních pravidel spojujících zároveň se vyskytující atributy (události, položky…) u zkoumaných objektů. Častým použitím je analýza nákupního košíku: jestliže objektem je nákup jednoho zákazníka v obchodě a atributy tohoto nákupu jsou názvy položek, jež zákazník zakoupil, tak příkladem jednoho pravidla může být

{párky} —> {hořčice, chléb},

což znamená, že zákazníci nakupující párky mají často ve svém nákupu rovněž hořčici a chléb. Rozumí se, že taková pravidla nemusejí platit vždy (v našem příkladu se mohou vyskytnout zákazníci, kteří si nekoupili hořčici nebo chléb, i když si koupili párky), ale očekává se, že platí obvykle, takže je na nich možné založit prakticky užitečnou akci (například dát v prodejně k párkům reklamu na hořčici, která se k nim hodí).

Množina atributů před šipkou asociačního pravidla (v našem příkladu {párky}) se označuje jako předpoklad, levá strana pravidla či antecedent, zatímco množina atributů za šipkou (v příkladě {hořčice, chléb}) se nazývá závěr, pravá strana pravidla či sukcedent.

Koncept asociační analýzy se poprvé objevil roku 1966 v článku The GUHA method of automatic hypotheses determination, jehož autory jsou Petr Hájek, Ivan Havel a Metoděj Chytil. Metodu však znovu vynalezli a zpopularizovali až v 90. letech Rakesh Agrawal, Tomasz Imieliński, Arun Swami a Ramakrishnan Srikant. K úspěchu přispěl také efektivní algoritmus pro hledání asociačních pravidel Apriori, který publikovali Agrawal a Srikant.

Kvalita asociačních pravidel

Na větších datových souborech lze obvykle najít obrovské množství aspoň poněkud vyhovujících asociačních pravidel. Proto je potřeba je třídít a vybírat podle jejich kvality, aby analytik svou pozornost věnoval jenom těm nejnadějnějším K posouzení kvality pravidel se nejčastěji používají tyto ukazatele:

• podpora (support) je počet objektů, pro které pravidlo platí (v našem příkladu počet nákupů, obsahujících zároveň párky, hořčici i chléb). Podpora může být také vyjádřena relativně vztažením k celkovému počtu objektů (nákupů) jako podíl či procento. Tento ukazatel říká, jak široce lze pravidlo aplikovat.
• spolehlivost (confidence) je počet objektů, pro které pravidlo platí, dělený počtem objektů, pro které platí předpoklad pravidla (tj. pravděpodobnost závěru podmíněná platností předpokladu), případně vyjádřeno v procentech. V našem příkladu to je počet nákupů, obsahujících zároveň párky, hořčici i chléb, dělený počtem všech nákupů obsahujících párky. Tento ukazatel měří, jak spolehlivě můžeme z předpokladu usuzovat na závěr.
• pokrytí (coverage) je počet objektů, pro které pravidlo platí, dělený počtem objektů, pro které platí závěr pravidla (tj. pravděpodobnost předpokladu podmíněná platností závěru), případně vyjádřeno v procentech. V našem příkladu to je počet nákupů, obsahujících zároveň párky, hořčici i chléb, dělený počtem všech nákupů obsahujících hořčici a chléb. Pokrytí analytikovi ukazuje, jak často lze závěr vyložil coby důsledek předpokladu.

Zpravidla se do výstupu vypisují jen pravidla, která překračují analytikem stanovené dolní meze těchto nebo dalších ukazatelů kvality, případně jejich vážených součtů s vhodně stanovenými vahami.