Pravila pridruzivanja Flashcards
Sta su pravila pridruzivanja ?
Одређивање правила придруживања jе процес у коме се за
дати скуп трансакциjа (слогова) проналазе правила коjа
предвиђаjу поjављивање ставке (обjекта) на основу
поjављивања осталих ставки (обjеката) у трансакциjама.
Kad je skup cest ?
Скуп ставки jе чест ако се у улазним подацима jавља више од
minsup пута, где minsup означава вредност минималног прага
подршке коjи се задаjе унапред
Kada kazemo da je skup pouzdan ?
Скуп ставки jе поуздан ако се у улазним подацима jавља више
од minconf пута, где minconf означава вредност минималног
прага поузданости коjи се задаjе унапред
Definicija pravila pridruzivanja.
Нека су X и Y два скупа ставки. Тада се правило у ознаци X ⇒ Y
назива правило придруживања са минималном подршком minsup и
минималном поузданошћу minconf ако важи:
1. Подршка скупа X ∪ Y jе ≥minsup (oko 5-10%)
2. Поузданост правила X ⇒ Y jе ≥minconf (oko 80%)
Sta znaci visoka podrska skupa ?
Висока подршка:
1.значи да се правило често поjављуjе и да jе мање вероватно да се правило случаjно поjавило
2.издваjа правила коjа нуде више могућности за добиjање користих информациjа
Visoko poverenje(pouzdanost):
Високо поверење (поузданост):
1. означава jако правило, коjе указуjе на висок ниво узрочности, и jаку везу придруживања између артикала/елемената
2. указуjе на правило коjе jе од интереса и на коjе треба обратити пажњу
Koji je proces formiranja pravila pridruzivanja
Процес одређивања правила придруживања може се поделити на два
корака:
1.Формирати све скупове ставки код коjих jе подршка ≥minsup
2.Формирати правила из сваког скупа честих ставки са поузданошћу ≥minconf
Koji su problemi formiranja svih cestih skupova ?
1.за d артикала постоjи 2d − 1 могућих скупова (+ празан скуп)
коjи су потенциjално чести и коjе треба испитати
2.ако се апликациjа често извршава (нпр. примена у
хипермаркетима или великим системима) њихову учесталост
треба проверити на основу милиона трансакциjа сваког
дана/сата
Koje su strategije za povecanje efikasnosti?
Ефикасност претраживања се повећава смањењем броjа потребних поређења коjе jе могуће извести:
1.Смањењем броjа кандидатских ставки (М)
2.Смањити броj трансакциjа (Н)
3. Смањити броj поређења (НМ)
Apriori princip i anti-monotonost
Априори принцип: ако jе скуп ставки чест, тада су и сви његови
подскупови такође чести
Затворење на ниже (енг. downward closure): сваки
подскуп честог скупа jе такође чест
Особина анти-монотоности: Мера f поседуjе особину
анти-монотоности ако за све скупове ставки X , Y важи:
X ⊂ Y =⇒ f (Y ) ≤ f (X )
Koja je posledica anti-monotonosti?
Последица (анти-монотоности): ако неки скуп артикала A ниjе
подржан (ниjе чест), тада ни било коjи скуп B где важи A ⊆ B
ниjе чест −→ не треба да буде разматран
Algoritam za odredjivanje cestog skupa :metod grube sile
Алгоритам коjи показуjе да jе (теориjски) могуће добити скуп правила
придруживања коjа испуњаваjу услов ≥ minsup ∧ ≥ minconf
Алгоритам:
-Сваки скуп ставки у решетки jе кандидат да буде чест
-Преброjати подршку за сваког кандидата прегледањем базе
-Упаруjе се свака трансакциjа са сваким кандидатом
Сложеност O(NMw ) - jако скупо jер jе M = 2d − 1- броj ставки,
w - максимална ширина трансакциjе, N - броj трансакциjа
Algoritam za odredjivanje cestih skupova :Apriori
-Елементи скупова ставки се уређуjу у лексикографски поредак
-Преброjе се све 1-ставке и одбаце оне коjе нису честе
-На основу честих скупова ставки дужине k се формираjу скупове дужине k + 1
-Скупови k ставки се спаjаjу и формираjу скуп k + 1 ставки акко су им jеднаки првих k − 1 елемената
-Одбацуjе се скуп k + 1 ставки ако неки од подскупова k ставки ниjе чест
-За формиране скупове дужине k + 1 одређуjе се подршка
-Одбацуjу се ретки скупови k + 1 ставки и не разматраjу се њихови надскупове (последица затворења на ниже)
Formiranje i potkresivanje skupova kandidata
Функциjа формирања нових нових кандидатских скупова у Априори
алгоритму укључуjе
1.Формирање кандидата:
генеришу се нови к-скупови ставки на основу честих скупова ставки дужине (k-1) коjи су формирани у претходноj итерациjи
2.Поткресивање скупа кандидата: елиминишу се одређени кандидатски к-скупови ставки коришћењем стратегиjе поткресивања на основу подршке
Kako apriori smanjuje broj poredjenja ?
-Смешта ставке у решетку у ширину, ниво по ниво
-Групише податке у корпе (енг. buckets) по дужини скупова ставки
-Свака корпа се представља у облику хеш структуре са фиксним броjем
грана у чвору
-На i-том нивоу хеш функциjа се примењуjе на i-ту ставку скупа
-Увећава се броj ставки до коjих се дође у листовима хеш структуре
-Ставке из трансакциjа се пореде са садржаjем своjе (кандидатске) корпе
уместо са целим скупом кандидата чиме се смањуjе броj поређења при
одређивању броjа поjављивања (подршке) скупа ставки
Sta su maksimalno cesti skupovi stavki ?
Дефинициjа: Скуп ставки jе максимално чест ако ни jедан од његових
непосредних надскупова ниjе чест:
1.Ако jе X максимално чест скуп, тада су и сви његови подскупови чести
2.Било коjи од честих скупова ставки jе подскуп неког од максимално честих скупова ставки =⇒ за добиjање било ког честог скупа ставки довољно jе чувати само скуп максимално честих скупова ставки
3.Скуп ставки коjи ниjе подскуп неког од максимално честих скупова ставки ниjе чест и може да се искључи из скупа ставки коjе се користе за
формирање правила придруживања
Zatvoreni skupovi stavki
Дефинициjа: Скуп ставки jе затворен ако ниjедан од његових непосредних
надскупова нема исту подршку
Последица: Сви подскупови затвореног скупа ставки имаjу исту подршку
Kako se kompaktno predstavljaju ceste stavke
Налажењем пресека скупа максималних и скупа затворених
скупова ставки добиjаjу се максимални затворени скупови
ставки.
Пошто jе позната информациjа о подршци затворених скупова
ставки, могуће jе одредити подршку свих честих скупова ставки
Уместо чувања свих честих скупова ставки и информациjа о
њиховоj подршци, довољно jе чувати скуп максималних
затворених скупова ставки и њихове подршке
Kako se obilazi resetka?
од општег ка посебном (лево),
од посебног ка општем (средина)
двосмерно (десно)
прво у ширину (Apriori алгоритам)
прво у висину/дубину
Algoritam FP rasta
Употребљава компримовану репрезентациjу базе података
помоћу ФП-дрвета (енг. Frequent Pattern)
Што jе већи броj трансакциjа коjе имаjу заjедничке
почетне делове, то jе већи степен компресиjе коjи се
постиже овим алгоритмом
Mоже да буде и вишеструко бржи од алгоритама коjи
конструишу и обилазе решетку ’по ширини’
Konstrukcija FP drveta
1.Конструкциjа двета почиње од корена коjи не садржи ни jедну ставку
- У чворовима дрвета коjи се конструишу уписуjе се ставка и броj њеног
поjављивања
3.У првом кораку се преброjе све поjединачне ставке и редослед ставки у
трансакциjама сортира у опадаjући редослед према њиховом броjу
поjављивања (овде А,Б,Ц,Д,Е) (у зависности од начина сортирања добиће
се другачиjи изглед дрвета!)
4.На основу прве трансакциjе формираjу се чворови означени са А и Б и уз њих се уписуjе тренутни броj поjављивања сваке ставке на тоj путањи (овде 1)
5.На основу наредне трансакциjе формира се нови скуп чворова (Б, Ц, Д) са одговараjућом граном. Уз сваки чвор се уписуjе 1 као броj поjављивања. Без обзира што у овоj трансакциjи постоjи Б, формира се нова грана jер не постоjи заjеднички префикс са већ постоjећим гранама
6.На краjу конструкциjе добиjа се дрво приказано на слици. Формира се и табела са скупом показивача на листе истоимених ставки у различитим гранама дрвета.
Odredjivanje cestih skupova stavki
-odozgdo navise(ka sufiksa_
1. preko pokazivaca se izdvoje sve grane koje se zavrsavaju na E
2. ako je skup cest deli se na potprobleme
3. gradi se uslovno FP drvo;
-eleminise E i azurira brojace toi, se broje samo oni koji se zavrsavaju na E
-
Neprekidni i kategoricki atributi
Kategoricki atributi —–> asimetricne binarne promenljive
– retko pojavljivanje ako ima mnogo vr.(mala sup) resenje agregacija vr.
–previse cesta stavka -> izbacivanje
Neprekidni atributi:
1.Diskretizacija
2.staticki zavisne metode
3. metode zasnovane na ne-diskretizaciji
