Априори алгоритам
Овај чланак можда захтева чишћење и/или прерађивање како би се задовољили стандарди квалитета Википедије. Проблем: Унос унутрашњих веза и референци. (децембар 2016) |
Многи од алгоритама за проналажење шаблона као што су стабла одлучивања, правила одлучивања и кластеровање који се често користе за истраживање података су произведени за машинско учење. Истраживање честих шаблона и правила асоцијације су једни од пар изузетака у овој традицији. Његово увођење убрзало је истраживање података и његов утицај је огроман. Априори алгоритам први пут је описан у[1] и користи се за проналажење правила придруживања анализирањем трансакција. Представљa класичан, врло користан алгоритам за откривање правила асоцијације.
Априори својство
Ако дати скуп није велики скуп, тада нити један његов надскуп не може бити велики скуп.
Априори принцип је заснован на својству антимонотоности за support меру
Примена
уредиУ пракси, подаци су углавном сирови и вероватноћa проналажења правила у таквом скупу је веома ниска. Истраживање правила може да се изведе неколико пута, сваки пут са различитим параметрима, како би се повећала вероватноћa наласка одговарајућих, нетривијалних правила. To је домен, где је једноставност и лакоћa генерисања огромног скупа правила Априори алгоритма, готово непобедива. Потрага за специфичним правилима, не треба увек да иде у дубину, из тог разлога, што би даљим спецификовањем само правило изгубило на значају и постало тривијално[2].
Првим проласком кроз базу, пребројава се свака појава појединог елемента, како бисмо открили све велике 1-itemsetove L1 (frequent itemsets[3]). У другој итерацији парови елемената из скупа L1, постају кандидати, тачније елементи скупа кандидата C2. Пролазећи кроз базу, утврђујемо значај сваког елемента из C2, сви они елементи чији је значај већи од минималног постају елементи скупа L2. Тако се за сваки следећи корак, нпр. корак k, може рећи да се састоји од две фазе:
- У првој фази се велики itemset Lk-1 (који је пронађен у k-1 кораку) користи за стварање скупа кандидата Ck, користећи apriori-gen функцију.
- У другој фази се утврђује значај сваког појединог кандидата из скупа кандидата Ck. Они кандидати који имају значај већи од минималног, и чији се сви подскупови налазе у Lk-1, постају елементи скупа Lk.
Априори алгоритам изводимо у онолико корака колико нам је потребно (a то је одређено са параметром који дефинише максималну даљину правила K), или док itemset Lk не постане празан скуп. На крају кад су пронађени сви велики itemsetovi од њих се формирају правила и то тако да се у обзир узимају само правила чија је поузданост већа од минималне.
Псеудокод
уредиЛогички се apriori алгоритам може написати у псеудокоду:
1 L1 = {large 1-itemsets};
2 for ( k = 2; Lk-1 ≠ 0; k++ ) do begin
3 Ck = apriori-gen(Lk-1); // нови кандидати
4 forall transactions t D do begin
5 Ct = subset(Ck, t); // кандидати садржани у t
6 forall candidates c ∈ Ct do
7 c.count++;
8 end
9 Lk = {c ∈ Ck ∈ c.count ≥ minsup}
10 L1 = {large 1-itemsets};
11 Answer = ;
Lk - представља скуп великих k-itemsetova, Ck - представља скуп кандидата k-itemset. Функција apriori-gen служи за откривање кандидата. Њен аргумент је Lk-1, скуп свих великих (k-1)-itemsetova, a као резултат добијемо скуп кандидата Ck, величине k. Функција се састоји од два корака: "join step" (корак уједињавања) i "prune step" (корак прочишћавања).
У првом кораку спајамо елементе скупа Lk-1 са циљем добијања скупа кандидата Ck. Овај корак се може описати како проналажење свих парова {U,V} где су U и V из Lk-1 таквих да је њихова унија има даљину k. Комплексност овог корака је у најгорем случају гдје је број великих itemsetova величине к-1. Но у пракси та сложеност је најчешћe линеарна с обзиром на број великих itemsetova у сваком кораку.
У другом кораку прочишћавамо скуп кандидата Ck на начин да бришемо све оне кандидате c из Ck чији се неки од подскупа величине (к-1) не налази у Lk-1.
Пример за apriori-gen функцију:
Нека је
Након "join step" скуп кандидата је . У следећем кораку добијамо за , скуп његових (к-1) подскупова a за , скуп његових (к-1) подскупова је . Како се скупови и не налазе у , ћемо избацити из и као коначно решење apriori-gen функције добићемо .
Последњи корак алгоритма, кад су пронађени је да се у обзир узму само она правила чија је поузданост већа од задане вредности.
Значај кандидата из скупа Ck се одређује тако што се преброји колико трансакција садржи те кандидате. Значај појединог кандидата можемо одредити једноставним начином: пролазећи кроз базу како би за сваку трансакцију утврдили садржи ли она тај кандидат, што с обзиром да се врло често ради o великом броју трансакција и могућих кандидата овај начин чини јако спорим и стога неупотребљивим. Због тога се користе разни трикови који убрзавају проналажење кандидата који имају значај већи од заданог примера организовањем кандидата у структуре сличне стаблима који се онда брже могу претраживати.
Имплементација у Јави
уреди 1
2
3 // Fajlovi:
4 // Neophodni ulazni fajlovi:
5 // 1. config.txt - tri linije, svaka linija na ulazu sadrzi ceo broj
6 // linija 1 - broj stavki po transakciji
7 // linija 2 - broj transakcija
8 // linija 3 - minsup
9 // 2. transa.txt - transakcioni fajl, svaka linija predstavlja transakciju, stavke su razdvojene belinama
10
11
12 package apriori;
13 import java.io.*;
14 import java.util.*;
15
16 public class Apriori {
17
18 public static void main(String[] args) {
19 AprioriCalculation ap = new AprioriCalculation();
20
21 ap.aprioriProcess();
22 }
23 }
24 //*****************************************************************************
25 // Ime klase : AprioriCalculation
26 // Namena : generise Apriori skup stavki
27 //*****************************************************************************/
28 class AprioriCalculation
29 {
30 Vector<String> candidates=new Vector<String>(); //trenutni kandidati
31 String configFile="config.txt"; //konfiguracioni fajl
32 String transaFile="transa.txt"; //transakcioni fajl
33 String outputFile="apriori-output.txt";//izlazni fajl
34 int numItems; //broj stavki po transakciji
35 int numTransactions; //broj transakcija
36 double minSup; //minimalna podrska za ceste skupove stavki
37 String oneVal[]; //niz vrednosti po kolonama koje ce biti trenirane kao '1'
38 String itemSep = " "; //belina predstavlja separator za vrednosti stavki u bazi
39
40 //************************************************************************
41 // Ime metode : aprioriProcess
42 // Namena : Generise apriori skup stavki
43 // Parametri : Nema
44 // Vraca : Nema
45 //************************************************************************
46 public void aprioriProcess()
47 {
48 Date d; //datum objekat za vremenske namene
49 long start, end; //pocetno i zavrsno vreme
50 int itemsetNumber=0; //trenutna stavka koja se posmatra
51
52 getConfig();
53
54 System.out.println("Apriori algoritam je startovan\n");
55
56 //startovanje tajmera
57 d = new Date();
58 start = d.getTime();
59
60 //sve dok se ne zavrsi
61 do
62 {
63 //uvecaj posmatrani broj stavki
64 itemsetNumber++;
65
66 //generisi kandidate
67 generateCandidates(itemsetNumber);
68
69 //odredi i prikazi ceste skupove stavki
70 calculateFrequentItemsets(itemsetNumber);
71 if(candidates.size()!=0)
72 {
73 System.out.println("Frequent " + itemsetNumber + "-itemsets");
74 System.out.println(candidates);
75 }
76 //ako postoji <=1 cestih stavki, tada je kraj
77 }while(candidates.size()>1);
78
79 //zavrsi tajmer
80 d = new Date();
81 end = d.getTime();
82
83 //prikazi proteklo vreme
84 System.out.println("Execution time is: "+((double)(end-start)/1000) + " seconds.");
85 }
86
87 //************************************************************************
88 // Ime metode : getInput
89 // Namena : uzmi korisnikov ulaz iz datoteke System.in
90 // Parametri : Nema
91 // Vraca : Pocetna vrednost korisnikovog ulaza
92 //************************************************************************
93 public static String getInput()
94 {
95 String input="";
96 //citaj iz System.in
97 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
98
99 //pokusaj da uzmes korisnikov ulaz, u slucaju greske stampaj poruku
100 try
101 {
102 input = reader.readLine();
103 }
104 catch (Exception e)
105 {
106 System.out.println(e);
107 }
108 return input;
109 }
110
111 //************************************************************************
112 // Ime metode : getConfig
113 // Namena : izimanje konfiguracionih informacija (config filename, transaction filename)
114 // : configFile i transaFile ce se menjati najverovatnije
115 // Parametri : Nema
116 // Vraca : Nema
117 //************************************************************************
118 private void getConfig()
119 {
120 FileWriter fw;
121 BufferedWriter file_out;
122
123 String input="";
124 //ukoliko zelimo da menjamo konfiguraciju
125 System.out.println("Default Configuration: ");
126 System.out.println("\tRegular transaction file with '" + itemSep + "' item separator.");
127 System.out.println("\tConfig File: " + configFile);
128 System.out.println("\tTransa File: " + transaFile);
129 System.out.println("\tOutput File: " + outputFile);
130 System.out.println("\nPress 'C' to change the item separator, configuration file and transaction files");
131 System.out.print("or any other key to continue. ");
132 input=getInput();
133
134 if(input.compareToIgnoreCase("c")==0)
135 {
136 System.out.print("Enter new transaction filename (return for '"+transaFile+"'): ");
137 input=getInput();
138 if(input.compareToIgnoreCase("")!=0)
139 transaFile=input;
140
141 System.out.print("Enter new configuration filename (return for '"+configFile+"'): ");
142 input=getInput();
143 if(input.compareToIgnoreCase("")!=0)
144 configFile=input;
145
146 System.out.print("Enter new output filename (return for '"+outputFile+"'): ");
147 input=getInput();
148 if(input.compareToIgnoreCase("")!=0)
149 outputFile=input;
150
151 System.out.println("Filenames changed");
152
153 System.out.print("Enter the separating character(s) for items (return for '"+itemSep+"'): ");
154 input=getInput();
155 if(input.compareToIgnoreCase("")!=0)
156 itemSep=input;
157
158
159 }
160
161 try
162 {
163 FileInputStream file_in = new FileInputStream(configFile);
164 BufferedReader data_in = new BufferedReader(new InputStreamReader(file_in));
165 //broj stavki
166 numItems=Integer.valueOf(data_in.readLine()).intValue();
167
168 //broj transakcija
169 numTransactions=Integer.valueOf(data_in.readLine()).intValue();
170
171 //minsup
172 minSup=(Double.valueOf(data_in.readLine()).doubleValue());
173
174 //izlazna informacija za korisnika
175 System.out.print("\nInput configuration: "+numItems+" items, "+numTransactions+" transactions, ");
176 System.out.println("minsup = "+minSup+"%");
177 System.out.println();
178 minSup/=100.0;
179
180 oneVal = new String[numItems];
181 System.out.print("Enter 'y' to change the value each row recognizes as a '1':");
182 if(getInput().compareToIgnoreCase("y")==0)
183 {
184 for(int i=0; i<oneVal.length; i++)
185 {
186 System.out.print("Enter value for column #" + (i+1) + ": ");
187 oneVal[i] = getInput();
188 }
189 }
190 else
191 for(int i=0; i<oneVal.length; i++)
192 oneVal[i]="1";
193
194 //kreiranje izlaznog fajla
195 fw= new FileWriter(outputFile);
196 file_out = new BufferedWriter(fw);
197 //stavljanje broja transakcije u izlazni fajl
198 file_out.write(numTransactions + "\n");
199 file_out.write(numItems + "\n******\n");
200 file_out.close();
201 }
202 //u slucaju greske stampati poruku
203 catch(IOException e)
204 {
205 System.out.println(e);
206 }
207 }
208
209 //************************************************************************
210 // Ime metode : generateCandidates
211 // Namena : Generise sve moguce kandidate za e n skupova stavki
212 // : ovi kandidati su smesteni u vektor klasu kandidata
213 // Parametri : n - celobrojna vrednost koja reprezentuje skup stavki koji ce se kreirati
214 // Vraca : Nista
215 //************************************************************************
216 private void generateCandidates(int n)
217 {
218 Vector<String> tempCandidates = new Vector<String>(); //privremeni kandidati u string vektoru
219 String str1, str2; //stringovi koji ce se koristiti za poredjenje
220 StringTokenizer st1, st2;
221
222 //u slucaju prvog skupa kandidati su samo brojevi
223 if(n==1)
224 {
225 for(int i=1; i<=numItems; i++)
226 {
227 tempCandidates.add(Integer.toString(i));
228 }
229 }
230 else if(n==2) //drugi skup stavki predstavlja samo sve kombinacije prvog skupa stavki
231 {
232 //dodavanje stavki iz prethodnih cestih skupova staki zajedno
233 for(int i=0; i<candidates.size(); i++)
234 {
235 st1 = new StringTokenizer(candidates.get(i));
236 str1 = st1.nextToken();
237 for(int j=i+1; j<candidates.size(); j++)
238 {
239 st2 = new StringTokenizer(candidates.elementAt(j));
240 str2 = st2.nextToken();
241 tempCandidates.add(str1 + " " + str2);
242 }
243 }
244 }
245 else
246 {
247 //za svaki skup stavki
248 for(int i=0; i<candidates.size(); i++)
249 {
250 //poredi sa sledecim skupom stavki
251 for(int j=i+1; j<candidates.size(); j++)
252 {
253 //kreiranje stringova
254 str1 = new String();
255 str2 = new String();
256 //kreiranje tokena
257 st1 = new StringTokenizer(candidates.get(i));
258 st2 = new StringTokenizer(candidates.get(j));
259
260 //kreiraj string od prvih n-2 tokena stringa
261 for(int s=0; s<n-2; s++)
262 {
263 str1 = str1 + " " + st1.nextToken();
264 str2 = str2 + " " + st2.nextToken();
265 }
266
267 //ukoliko imaju istih n-2 tokena, dodaj ih zajedno
268 if(str2.compareToIgnoreCase(str1)==0)
269 tempCandidates.add((str1 + " " + st1.nextToken() + " " + st2.nextToken()).trim());
270 }
271 }
272 }
273 //brisanje starih kandidata
274 candidates.clear();
275 //postavi nove kandidate
276 candidates = new Vector<String>(tempCandidates);
277 tempCandidates.clear();
278 }
279
280 //************************************************************************
281 // Ime metode : calculateFrequentItemsets
282 // Namena : Odredjivanje koji kandidati su cesti u n-tom skupu stavki
283 // : od svih mogucih kandidata
284 // Parametri : n - celobrojna reprezentacija trenutnog skupa stavki koji se evaluira
285 // Vraca : Nista
286 //************************************************************************
287 private void calculateFrequentItemsets(int n)
288 {
289 Vector<String> frequentCandidates = new Vector<String>(); //cesti kandidati za trenutni skup stavki
290 FileInputStream file_in; //fajl ulazni stream
291 BufferedReader data_in; //izlazni stream za podatke
292 FileWriter fw;
293 BufferedWriter file_out;
294
295 StringTokenizer st, stFile; //token za kandidate i transakcije
296 boolean match; //da li transakcija ima sve stavke u jednom skupu stavki
297 boolean trans[] = new boolean[numItems]; //niz koji sadrzi transakcije koje ce biti proverene
298 int count[] = new int[candidates.size()]; //broj uspesnih poredjenja
299
300 try
301 {
302 //izlazni fajl
303 fw= new FileWriter(outputFile, true);
304 file_out = new BufferedWriter(fw);
305 //ucitavanje transakcionog fajla
306 file_in = new FileInputStream(transaFile);
307 data_in = new BufferedReader(new InputStreamReader(file_in));
308
309 //za svaku transakciju
310 for(int i=0; i<numTransactions; i++)
311 {
312
313 stFile = new StringTokenizer(data_in.readLine(), itemSep); //citanje linije iz fajla za token
314 //stavljanje sadrzaja te linije u transakcioni niz
315 for(int j=0; j<numItems; j++)
316 {
317 trans[j]=(stFile.nextToken().compareToIgnoreCase(oneVal[j])==0); //ako nije nula dodeli vrednost tacno
318 }
319
320 //proveri svakog kandidata
321 for(int c=0; c<candidates.size(); c++)
322 {
323 match = false; //resetovanje match na netacno
324
325 st = new StringTokenizer(candidates.get(c));
326 //proveri za svaku stavku u skupu stavki da li je prisutna u transakciji
327 while(st.hasMoreTokens())
328 {
329 match = (trans[Integer.valueOf(st.nextToken())-1]);
330 if(!match) //ukoliko nije prisutna u transakciji prestani sa provrom
331 break;
332 }
333 if(match) //ukoliko je sada uspesno poredjenje uvecaj brojac
334 count[c]++;
335 }
336
337 }
338 for(int i=0; i<candidates.size(); i++)
339 {
340
341 //ukoliko brojac nije veci od minimalne podrske dodaj kandidata u cesti skup stavki
342 if((count[i]/(double)numTransactions)>=minSup)
343 {
344 frequentCandidates.add(candidates.get(i));
345 //prosledi cest skup stavki u izlazni fajl
346 file_out.write(candidates.get(i) + "," + count[i]/(double)numTransactions + "\n");
347 }
348 }
349 file_out.write("-\n");
350 file_out.close();
351 }
352 //ukoliko dodje do greske stampaj je na izlazu
353 catch(IOException e)
354 {
355 System.out.println(e);
356 }
357 //brisanje starih kandidata
358 candidates.clear();
359 //novi kandidati su stari cesti kandidati
360 candidates = new Vector<String>(frequentCandidates);
361 frequentCandidates.clear();
362 }
363 }
Пример
уредиИД Трансакције | Елементи |
---|---|
T100 | хлеб, млеко, кикирики |
T200 | млеко, jaja |
T300 | млеко, пиво |
T400 | хлеб, млеко, jaja |
T500 | хлеб, пиво |
T600 | млеко, пиво |
T700 | хлеб, пиво |
T800 | хлеб, млеко, пиво, кикирики |
T900 | хлеб, млеко, пиво |
Чести једночлани скупови ставки
Скупови ставки | Подршка (Support) |
---|---|
{хлеб} | 6 |
{млеко} | 7 |
{пиво} | 6 |
{jaja} | 2 |
{кикирики} | 2 |
L1 = {хлеб, млеко, пиво, jaja, кикирики}
Чести двочлани скупови ставки
Корак уједињавања
Скупови ставки | Подршка |
---|---|
{хлеб, млеко} | 4 |
{хлеб, пиво} | 4 |
{хлеб, jaja} | 1 |
{хлеб, кикирики} | 2 |
{млеко, пиво} | 4 |
{млеко, jaja} | 2 |
{млеко, кикирики} | 2 |
{пиво, jaja} | 0 |
{пиво, кикирики} | 1 |
{jaja, кикирики} | 0 |
Скупови ставки | Подршка |
---|---|
{хлеб, млеко} | 4 |
{хлеб, пиво} | 4 |
{хлеб, кикирики} | 2 |
{млеко, пиво} | 4 |
{млеко, jaja} | 2 |
{млеко, кикирики} | 2 |
Чести трочлани скупови ставки
Корак уједињавања
Скупови ставки |
---|
{хлеб, млеко, пиво} |
{хлеб, млеко, кикирики} |
{хлеб, пиво, кикирики} |
{млеко, пиво, jaja} |
{млеко, пиво, кикирики} |
{млеко, jaja, кикирики} |
Корак прочишћавања
Скупови ставки | Подршка |
---|---|
{хлеб, млеко, пиво} | 2 |
{хлеб, млеко, кикирики} | 2 |
Скупови ставки | Подршка |
---|---|
{хлеб, млеко, пиво} | 2 |
{хлеб, млеко, кикирики} | 2 |
Корак уједињавања
Скупови ставки |
---|
{хлеб, млеко, кикирики} |
Корак прочишћавања
Временска сложеност
уредиВременска сложеност априори алгоритма дата је следећим изразом[3]:
Где је |Ck| број кандидата даљине к, К максимална даљина правила, n укупни број трансакција и p број различитих елемената који се појављују у трансакцијама. Из израза је очигледно да се на временско извођење алгоритма може утицати на више начина:
- Ограничавање броја кандидата у свакој од итерација алгоритма – To се постиже подешавањем параметра Supp (минимални значај правила). Ако се тај параметар постави премали онда се излажемо опасности да број кандидата Ck у свакој итерацији алгоритма буде превелики тако да алгоритам не буде изводљив у реалном времену, a ако се постави велики онда се може догодити да се не пронађе нити једно правило које задовољава постављени услов. Због тога је код имплементације апликација које користе априори алгоритам за проналажење правила придруживања добро одредити границе у којима се може кретати минимални износ значаја. Te границе се одређују експериментално a условљене су бројем различитих елемената који се појављују у трансакцијама те бројем трансакција.
- Ограничавање максималне дуљине правила К – У пракси нас обично интересирају правила мањих дуљина (обично не више од 5). Правила с већим бројем елемената обично имају занемарљиве значаје у односу на правила с мањим бројем елемената.
- Смањивање броја трансакција које се анализирају n – Ово се постиже узимањем репрезентативног узорка из цијелог скупа података. Том приликом треба бити опрезан и стварно се осигурати да је узорак репрезентативан иначе се добијени резултати не могу односити на целу популацију.
- Смањивање броја различитих елемената p – Према једнакости овај параметар утиче на вријеме извођења алгоритма експлицитно и имплицитно тако што утјече на број кандидата за велике itemsetove у свакој итерацији алгоритма. На њега се може утицати увођењем одговарајућe таксономије при чему се елементи могу груписати у више група (или класа) према својим својствима. Одабирање добре таксономије може имати драстичан утицај на скраћивање времена извођења алгоритма a уз истодобно задржавање основних законитости због којих се правила придруживања уопште и анализирају. На пример информација o куповини пива и чипса заједно из правила (“Чили Чипс” “Јелен пиво”) у правилу (“Чипс” “Пиво”) је сачувана. Наравно део информације o врсти чипса и пива који се купују заједно је овим путем изгубљен a то је цена која се плаћa за убрзавање извођења алгоритма. Уколико се начини добра таксономија могу се бирати нивои на којима се врши анализа података у зависности од специфичног интереса аналитичара.
Закључак
уредиИстраживање асоцијативних правила производи огромну количину правила, од којих је већина редундантна. Да бисмо видели априори алгоритам у пуном светлу, потребна нам је велика база података и велико знање o природи проблема.
Референце
уреди- ^ Agrawal,R;Srikant,R:”Fast algorithms for mining association rules in large databases”, Proceedings of the Twentieth International Conference on Very Large Databases (VLDB'94),pp. 487-499, 1994.
- ^ G Webb and S Zhang, "Removing trivial association in association rule discovery," in Proceedings of the 1st International NAISO Congress on Autonomous Intelligent Systems (ICAIS), Geelong, Australia, 2002.
- ^ а б Hand,D.;Manilla,H.;Smyth,P.:“Principles of Data Mining”, MIT Press, 2001.