Reguły asocjacyjne przypominają reguły decyzyjne omawiane na poprzednim wykładzie. Tym razem jednak decyzja (prawa strona implikacji) nie jest z góry określona, tzn. nie wiemy, na którym atrybucie ma się opierać. Jest to przykład nauki bez nauczyciela: algorytm nie ma określonej z góry prawidłowej odpowiedzi, zamiast tego ma opisać wewnętrzne zależności między atrybutami.

Mamy dane następujące informacje o transakcjach w jednym z hipermarketów:

Zadaniem algorytmu odkrywającego reguły asocjacyjne będzie odpowiedź napytanie: Jakie są zależności pomiędzy kupowanymi produktami?

Pytanie Patrząc na zbiór uczący w tabeli powyżej wypisz reguły które będą określać jakie produkty są kupowane najczęściej razem.

Z powyższego zbioru uczącego możemy łatwo wywnioskować następujące reguły:

if Piwo then Jajka
if Jajka then Piwo
if Jabłka then Seler
if Seler then Jabłka

Pozostałe reguły intuicyjnie odrzuciliśmy ponieważ ich częstotliwość w zbiorze uczącym jest niewielka, i w związku z tym mamy małą pewność co do ich prawdziwości. W celu automatycznego określenia tych parametrów stosuje się dwa wskaźniki: support (wsparcie) i confidence (wiarygodność)

Wskaźnik ten określa częstotliwość (prawdopodobieństwo) danej reguły w stosunku do wszystkich transakcji. Innymi słowy jest to stosunek ilości transakcji zawierających dane elementy wchodzące w skład reguły do wszystkich transakcji.

Dla przykładu z tabeli powyżej, support reguły

If Piwo then Jajka 

jest równy , ponieważ 3 transakcje zawierają Piwo i Jajka, natomiast ilość wszystkich transakcji jest równa 4.

Pytanie Jaki jest support dla reguły poniżej?

 if Jabłka then Seler 

Wskaźnik ten określa siłę implikacji w regule. Innymi słowy jest on definiowany jako stosunek ilości transakcji zawierających elementy wchodzące w skład reguły do wszystkich transakcji zawierających elementy z części warunkowej reguły.

Dla przykładu z tabeli powyżej, confidence reguły

If Piwo then Jajka 

jest równy , ponieważ 3 transakcje zawierają Piwo i Jajka, natomiast ilość transakcji zawierających elementy z części warunkowej tej reguły (czyli w tym wypadku Piwo) jest także równa 3.

Pytanie Jaki jest confidence dla reguł poniżej?

 
if Seler then Jabłka 
if Jabłka then Seler

Patrząc na przykłady powyżej odnalezienie dobrych reguł asocjacyjnych sprowadza się tak naprawdę do dwóch kroków

• wyszukania zbiorów elementów które mają support większy lub równy jakiemuś zadanemu supportowi granicznemu - są tak zwanymi zbiorami częstymi (frequent itemsets)
• wybrania spośród nich tych konfiguracji, które maja największy confidence.

W przypadku reguł asocjacyjnych, zbiory które zawierają k elementów nazywane są k-zbiorami (k-temsets).