Учење правилом асоцијације

У тражењу података учење правилом асоцијације је популаран и добро истражен метод за откривање интересантних односа између променљивих у великим базама података. Намењено је проналажењу јаких закона откривеним у базама података коришћењем различитих мера интересантности. Засновано на концепту јаких закона, Ракеш Агравал et al. (Rakesh Agrawal et al.) је увео правила асоцијације за откривање регуларности између продуката у трансакцијама података великих размера забележених од стране места продаје (POS) система у супермаркетима. На пример, правило $\{\mathrm {luk,krompir} \}\Rightarrow \{\mathrm {pljeskavica} \}$ нађено у подацима о продаји супермаркета значи да ако купац пазари лук и кромпир заједно највероватније да ће такође купити и месо за пљескавицу. Такве информације могу бити коришћене као основа за одлуке о маркетиншким активностима као што су промотивне цене или распоређивање производа. Као додатак горенаведеном из анализе потрошачких корпи асоцијативна правила су данас укључена у многе области као што су претраживање коришћења веба, детекције упада, непрекидне продукције и биоинформатике. Насупрот претраживању низова учење правилом асоцијације обично не узима у обзир редослед појмова или у или кроз трансакције.

Дефиниција

Primer baze sa 4 proizvoda i 5 transakcija

Broj transakcije	mleko	hleb	puter	pivo
1	1	1	0	0
2	0	0	1	0
3	0	0	0	1
4	1	1	1	0
5	0	1	0	0

Пратећи првобитну дефиницију Агравала et al. проблем претраживања учењем правилом асоцијације је дефинисано као: Нека су $I=\{i_{1},i_{2},\ldots ,i_{n}\}$ сет $n$ бинарних атрибута названих ставке. Нека је $D=\{t_{1},t_{2},\ldots ,t_{m}\}$ сет трансакција назван базом података. Свака трансакција у $D$ има јединствену идентификацију и садржи подниз ставки у $I$. Правило је дефинисано као импликација израза $X\Rightarrow Y$ где је $X,Y\subseteq I$ и $X\cap Y=\emptyset$. Низови ставки $X$ and $Y$ се називају претходници (лева страна или LHS - left-hand-side) и следбеници (десна страна или RHS - right-hand-side).

Да бисмо илустровали концепте, користимо кратки пример из области супермаркета. Листа ставки је $I=\{\mathrm {mleko,hleb,puter,pivo} \}$ и мала база података која садржи ставке (1 кодира присуство а 0 одсуство ставке у трансакцији) је приказана у табели са десне стране. Пример правила за супермаркет може да буде $\{\mathrm {puter,hleb} \}\Rightarrow \{\mathrm {mleko} \}$ што може да значи да ако би купци узели хлеб и путер, такође би узели и млеко.

Напомена: овај пример је изузетно мали. У практичној примени правило мора да буде поткрепљено са неколико стотина трансакција пре него што би било сматрано статистички значајним, а групе података често садрже хиљаде или милионе трансакција.

Корисни концепти

Да бисмо одабрали интересантна правила из групе свих могућих правила, ограничења на различитим мерилима значаја могу бити коришћена. Најпознатија ограничења су минимални прагови подршке и поверења.

• Подршка $\mathrm {supp} (X)$ групе ставки $X$ је дефинисана као пропорција трансакција у групи података која садржи ту групу ставки. У примеру базе података група ставки $\{\mathrm {mleko,hleb,puter} \}$ има подршку $1/5=0.2$ јер се дешава у 20% свих трансакција (у једној од пет трансакција).
• Поверење правила је дефинисано $\mathrm {conf} (X\Rightarrow Y)=\mathrm {supp} (X\cup Y)/\mathrm {supp} (X)$ . На пример, правило $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ има поверење $0.2/0.4=0.5$ у бази података, што значи да је за 50% трансакција које садрже млеко и хлеб правило исправно (50% од свих ситуација када купац узме млеко и хлеб, узима и путер). Будите опрезни када читате израз: Овде supp(X∪Y) значи "подршка за ситуације трансакција у којима се X и Y појављују, а не подршка за ситуације трансакција где се или X или Y појављују". Аргумент $\mathrm {supp} ()$ је група предуслова, па с тим постаје рестриктивнија како расте (уместо више инклузивна).
• Поверење може да буде интерпретирано као процена вероватноће $P(Y|X)$, вероватноћа налажења следбеника овог правила у трансакцијама под условом да ове трансакције такође садрже претходник.
• [[Lift (eksploracija podataka)|Лифт] правила је дефинисан као $\mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}$ или учесталост посматране подршке онога што је очекивано ако су X и Y независни. Правило $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ има лифт ${\frac {0.2}{0.4\times 0.4}}=1.25$.
• Конвикција правила је дефинисана као $\mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}$. Правило $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ има конвикцију ${\frac {1-0.4}{1-.5}}=1.2$, и може бити интерпретирано као удео очекиване учесталости којом се X појављује без Y (односно учесталост којом правило чини погрешно предвиђање) ако су X и Y независни и подељени посматраном учесталошћу нетачних предвиђања. У овом примеру, вредност конвикције од 1.2 показује да ће правило $\{\mathrm {mleko,hleb} \}\Rightarrow \{\mathrm {puter} \}$ бити нетачно 20% чешће ако је повезаност између X и Y потпуно случајна.

Процес

Боја правоугаоника показује колико трансакција садржи комбинацију ставки. Узмите у обзир да нижи нивои графика садрже највише минимални број својих родитеља - ставки. Ово се зове могућност затварања надоле.

Правила асоцијације често морају да задовољавају минималну подршку назначену од стране корисника, као и минимално поверење у исто време. Израда правила асоцијације је обично подељена на два одвојена корака:

1. Минимална подршка се примењује како би биле пронађене учестале групе ставки у бази података.
2. Ове учестале групе ставки и ограничење минималног поверења се користе за израду правила.

Док је други корак директан, први корак захтева више пажње.

Налажење свих учесталих група ставки у бази података је тешко зато што оно укључује претрагу свих могућих група ставки (комбинације ставки). Скуп могућих група ставки је [[Партитивни скуп|надскуп] од $I$ величине $2^{n}-1$ (искључујући празан скуп који није валидан скуп ставки). Иако веичина надскупа расте експоненцијално у броју ставки $n$ у $I$, ефикасна претрага је могућа користећи могућност затварања надоле што гарантује да за чест скуп ставки сви његови подскупови су такође чести и стога за редак скуп ставки сви његови надскупови морају бити такође ретки. Истражујући ову особину, ефикасни алгоритми могу наћи све честе скупове ставки.

Историја

Концепт асоцијативних правила је популаризован највише захваљујући чланку Агравала ет. ал из 1993. који је прибавио више од 6000 цитата и стога је један од најцитиранијих радова у области прикупљања података. Ипак, могуће је да су сада звана "правила асоцијације" слична ономе што се појављује у раду 1966. године. На Гуха, општем методу претраге података развијеном од стране Petr Hájek et al.

Алтернативне мере занимљивости

Поред поверења и друге мере интересантности су предложене за правила. Неке популарне мере су:

• Потпуно поверење
• Колективна снага
• Убеђење
• Предност
• Лифт

Дефиниција ових мера може бити нађена овде Архивирано на сајту Wayback Machine (2. август 2018). Још неколико мера је представљено и упоређено од стране Тан et al. Тражење техника које представљају шта је корисник знао (и коришћење ових модела као мера интересантности) је тренутно активно истраживање под именом "Субјективна занимљивост".

Статистички важне асоцијације

Једно ограничење стандардног приступа откривању асоцијација је што претрага великог броја могућих асоцијација у потрази за колекцијама ставки које се повезују, повлачи велики ризик за проналажење много сумњивих асоцијација. Ово су колекције ставки које се дешавају неочекиваном учесталошћу у подацима, али само случајно. На пример, претпоставимо да у колекцији од 10 000 ставки тражимо правила која садрже две ставке у левој страни и једну у десној. Приближно има 1 000 000 000 000 таквих правила. Ако применимо статистички текст за независност са нивоом значаја од 0.05 то значи да постоји само 5% шансе за прихватање правила ако не постоји асоцијација. Ако претпоставимо да асоцијације не постоје, без обзира на то можемо очекивати да нађемо 50 000 000 000 правила. Откривање статистички значајних асоцијација контролише овај ризик, у већини случајева смањујући ризик налажења било каквих лажних асоцијација за ниво кориснички дефинисан ниво значаја.

Алгоритми

Многи алгоритми за прављење правила асоцијације су временом приказани.

Неки познати алгоритми су Априори, Еклат и ФП-раст, али они раде само пола посла, због тога што су алгоритми за проналажење учесталих скупова ставки. Још један корак мора бити урађен да би се направила правила из учесталих скупова ставки нађених у бази података.

Априори алгоритам

Априори алгоритам - априори је најпознатији алгоритам за претраживање правила асоцијације. Користи БФС стратегију (претрага у ширину) за бројање скупова ставки и користи функцију налажења кандидата која има особину затварања надоле.

Еклат алгоритам

Еклат је алгоритам за претрагу у дубину који користи пресецање скупова.

ФП-раст алгоритам

ФП означава учестали шаблон (на енглеском).

У првом пролазу, алгоритам броји појављивање ставки (парови атрибут-вредност) у скупу података, и учитава их у 'хедер табелу'. У другом пролазу прави ФП стабло тако што убацује инстанце. Ставке у свакој инстанци морају бити сортиране у опадајућем поретку према својој учесталости у скупу података, тако да стабло може бити брзо обрађено. Ставке у свакој инстанци које не задовољавају праг минималне покривености се одбацују. Ако много инстанци дели најучесталије ставке, ФП стабло пружа високу компресију у близини корена стабла.

Рекурзивно обрађивање ових компресованих верзија главног скупа података ствара велике скупове ставки директно, уместо прављења ставки кандидата и тестирања истих у односу на целу базу података. Раст почиње са дна табеле заглавља (хедер табеле која има најдуже гране), налажењем свих инстанци које одговарају датом услову. Прави се ново дрво са тачкама из првобитног дрвета у односу на скуп инстанци које су условљене атрибутом, са сваким чвором који садржи суму тачака своје деце. Рекурзивни раст се завршава када ни једна ставка условљена атрибутом не достигне минимални праг подршке и процесирање се наставља на остатку ставки заглавља првобитног ФП дрвета.

Када се рекурзивни процес једном заврши сви велики скупови ставки са минималном покривеношћу су нађени и почиње стварање правила асоцијације.

ГУХА процедура

ГУХА је уопштени метод за анализу података који има теоретски темељ у израчунавању посматрањем.

АССОЦ процедура је ГУХА метод који тражи генерализована правила асоцијације користећи брзе операције бит стрингa. Правила асоцијације пронађена овим методом су више уопштена него она нађена априори методом, на пример "ставке" могу бити повезане и са конјукцијом и са дисјункцијом и релација између претходника и следбеника правила није ограничена на постављање минималне подршке и поверења као у априори-у: комбинација подржаних мера интересовања може бити коришћена.

ОПУС претрага

ОПУС је ефикасан алгоритам за промалажење правила који, супротно многима алтернативама, не захтева ни монотона ни антимонотона ограничења као што су минимална подршка. Првобитно коришћено за проналажење правила за фиксирану и доследну, а проширен за налажење правила за било коју ставку као доследну. Опус претрага је кључна технологија у популарном Magnum Opus систему откривања асоцијација.

Знање

Позната прича о проналажењу правила асоцијације је прича о "пиву и пелени". Анкета о понашању купаца у супермаркету открила је да купци (млади мушкарци најчешће) који купе пелене врло често купе и пиво. Ова анегдота је постала популарна као пример тога како неочекивана правила асоцијације могу бити нађена у подацима из свакодневице. Постоје различита мишљења о томе колико је ова прича тачна. Daniel Powers says:

1992. године, Томас Блишок, менаџер консалтинг групе у "Терадата", заједно са својим запосленима, припремио је анализу 1,2 милиона потрошачких корпи из отприлике 25 продавница Оско. Упитник је израђен за препознавање склоности. Анализа "је открила да су потрошачи између пет и седам часова поподне куповали пиво и пелене". Менаџери у Оску НИСУ искористили повезаност пива и пелена тако што би померили производе ближе један другом на полицама.

Остали типови тражења асоцијација

Учење различитих скупова је облик асоцијативног учења. Они који га користе, користе правила која значајно одступају у својој распоређености кроз потскупове.

Учење оптерећених класа је још један облик асоцијативног учења у коме оптерећеност можће бити додељена класама како би дала фокус одређеном проблему за потрошача резултата проналажења података.

Откривање шаблона високог реда - ове технике убрзавају хватање шаблона високог реда (политетичких) или асоцијација догађаја унутар комплексних података стварног света.

К-оптимално откривање шаблона омогућава алтернативу стандардном приступу учењу правила асоцијације које захтева да се сваки шаблон понавља у подацима.

Генерализована правила асоцијације - концептна хијерархија.

Квантитативна правила асоцијације - категорични и квантитативни подаци.

Правила асоцијације података у интервалима.

Максимална правила асоцијације.

Проналажење секвенцијалних шаблона - низ је уређена листа трансакција.

Секвенцијална правила - откривање повезаности између ставки узимајући у обзир временску распоређеност. Најчешће се примењује на базу података низова. На пример, секвенцијално правило нађено у бази података низова трансакција потрошача може бити да потрошачи који су купили компјутер и цд-ромове, касније купе веб камеру.

Литература

• Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). „Chapter 6. Association Analysis: Basic Concepts and Algorithms” (PDF). Introduction to Data Mining. Addison-Wesley. ISBN 978-0-321-32136-7. 
• Hájek, Petr (1978). Mechanizing Hypothesis Formation: Mathematical Foundations for a General Theory. and Havránek, Tomáš. Springer-Verlag. ISBN 978-3-540-08738-0.