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

Из Википедије, слободне енциклопедије

У тражењу података учење правилом асоцијације је популаран и добро истражен метод за откривање интересантних односа између променљивих у великим базама података. Намењено је проналажењу јаких закона откривеним у базама података коришћењем различитих мера интересантности.[1] Засновано на концепту јаких закона, Ракеш Агравал ет ал. (Rakesh Agrawal et al.)[2] је увео правила асоцијације за откривање регуларности између продуката у трансакцијама података великих размера забележених од стране места продаје (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

Пратећи првобитну дефиницију Агравала ет ал.[2] проблем претраживања учењем правилом асоцијације је дефинисано као: Нека су 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), вероватноћа налажења следбеника овог правила у трансакцијама под условом да ове трансакције такође садрже претходник.[3]
  • [[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 потпуно случајна.

Процес[уреди]

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

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

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

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

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

Историја[уреди]

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

Алтернативне мере занимљивости[уреди]

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

  • Потпуно поверење[7]
  • Колективна снага[8]
  • Убеђење[9]
  • Предност[10]
  • Лифт[11]

Дефиниција ових мера може бити нађена овде. Још неколико мера је представљено и упоређено од стране Тан ет ал.[12] Тражење техника које представљају шта је корисник знао (и коришћење ових модела као мера интересантности) је тренутно активно истраживање под именом "Субјективна занимљивост".

Статистички важне асоцијације[уреди]

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

Алгоритми[уреди]

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

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

Априори алгоритам[уреди]

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

Еклат алгоритам[уреди]

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

ФП-раст алгоритам[уреди]

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

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

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

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

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

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

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

ОПУС претрага[уреди]

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

Знање[уреди]

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

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

Остали типови тражења асоцијација[уреди]

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

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

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

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

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

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

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

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

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

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

Референце[уреди]

  1. ^ Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
  2. ^ а б в г д Agrawal, R.; Imieliński, T.; Swami, A. (1993). „Mining association rules between sets of items in large databases“. Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. pp. 207. DOI:10.1145/170035.170072. ISBN 0-89791-592-5. 
  3. ^ Hipp, J.; Güntzer, U.; Nakhaeizadeh, G. (2000). „Algorithms for association rule mining --- a general survey and comparison“. ACM SIGKDD Explorations Newsletter 2: 58. DOI:10.1145/360402.360421. 
  4. ^ Tan, Pang-Ning; Michael, Steinbach; Kumar, Vipin (2005). „Chapter 6. Association Analysis: Basic Concepts and Algorithms“. Introduction to Data Mining. Addison-Wesley. ISBN 0-321-32136-7. 
  5. ^ Hájek, Petr; Havel, Ivan; Chytil, Metoděj; The GUHA method of automatic hypotheses determination, Computing 1 (1966) 293-308
  6. ^ Hájek, Petr; Feglar, Tomas; Rauch, Jan; and Coufal, David; The GUHA method, data preprocessing and mining, Database Support for Data Mining Applications, Springer, 2004. ISBN 978-3-540-22479-2.
  7. ^ Omiecinski, Edward R.; Alternative interest measures for mining associations in databases, IEEE Transactions on Knowledge and Data Engineering, 15(1):57-69, Jan/Feb 2003
  8. ^ Aggarwal, Charu C.; and Yu, Philip S.; A new framework for itemset generation, in PODS 98, Symposium on Principles of Database Systems, Seattle, WA, USA, 1998, pages 18-24
  9. ^ Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 255-264
  10. ^ Piatetsky-Shapiro, Gregory; Discovery, analysis, and presentation of strong rules, Knowledge Discovery in Databases, 1991, pp. 229-248
  11. ^ Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; and Tsur, Shalom; Dynamic itemset counting and implication rules for market basket data, in SIGMOD 1997, Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 1997), Tucson, Arizona, USA, May 1997, pp. 265-276
  12. ^ Tan, Pang-Ning; Kumar, Vipin; and Srivastava, Jaideep; Selecting the right objective measure for association analysis, Information Systems, 29(4):293-313, 2004
  13. ^ Webb, Geoffrey I. (2007); Discovering Significant Patterns, Machine Learning 68(1), Netherlands: Springer, pp. 1-33 online access
  14. ^ Gionis, Aristides; Mannila, Heikki; Mielikäinen, Taneli; and Tsaparas, Panayiotis; Assessing Data Mining Results via Swap Randomization, ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 1, Issue 3 (December 2007), Article No. 14
  15. ^ Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition
  16. ^ Rauch, Jan; Logical calculi for knowledge discovery in databases, in Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, Springer, 1997, pp. 47-57
  17. ^ Hájek, Petr; and Havránek, Tomáš (1978). Mechanizing Hypothesis Formation: Mathematical Foundations for a General Theory. Springer-Verlag. ISBN 3-540-08738-9. 
  18. ^ а б Webb, Geoffrey I. (1995); OPUS: An Efficient Admissible Algorithm for Unordered Search, Journal of Artificial Intelligence Research 3, Menlo Park, CA: AAAI Press, pp. 431-465 online access
  19. ^ Bayardo, Roberto J., Jr.; Agrawal, Rakesh; Gunopulos, Dimitrios (2000). „Constraint-based rule mining in large, dense databases“. Data Mining and Knowledge Discovery 4 (2): 217–240. DOI:10.1023/A:1009895914772. 
  20. ^ Webb, Geoffrey I. (2000); Efficient Search for Association Rules, in Ramakrishnan, Raghu; and Stolfo, Sal; eds.; Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000), Boston, MA, New York, NY: The Association for Computing Machinery, pp. 99-107 online access
  21. ^ а б http://www.dssresources.com/newsletters/66.php
  22. ^ Menzies, Tim; and Hu, Ying; Data Mining for Very Busy People, IEEE Computer, October 2003, pp. 18-25
  23. ^ Wong, Andrew K.C.; Wang, Yang (1997). „High-order pattern discovery from discrete-valued data“. IEEE Transactions on Knowledge and Data Engineering (TKDE): 877–893. 
  24. ^ Salleb-Aouissi, Ansaf; Vrain, Christel; and Nortet, Cyril (2007). „QuantMiner: A Genetic Algorithm for Mining Quantitative Association Rules“. International Joint Conference on Artificial Intelligence (IJCAI): 1035–1040. 
  25. ^ Zaki, Mohammed J. (2001); SPADE: An Efficient Algorithm for Mining Frequent Sequences, Machine Learning Journal, 42, pp. 31–60

Литература[уреди]