Apriori algoritam

Mnogi od algoritama za pronalaženje šablona kao što su stabla odlučivanja, pravila odlučivanja i klasterovanje koji se često koriste za istraživanje podataka su proizvedeni za mašinsko učenje. Istraživanje čestih šablona i pravila asocijacije su jedni od par izuzetaka u ovoj tradiciji. Njegovo uvođenje ubrzalo je istraživanje podataka i njegov uticaj je ogroman. Apriori algoritam prvi put je opisan u^[1] i koristi se za pronalaženje pravila pridruživanja analiziranjem transakcija. Predstavlja klasičan, vrlo koristan algoritam za otkrivanje pravila asocijacije.

Apriori svojstvo

Ako dati skup nije veliki skup, tada niti jedan njegov nadskup ne može biti veliki skup.

Apriori princip je zasnovan na svojstvu antimonotonosti za support meru $\forall X,Y:(X\subseteq Y)\Rightarrow s(X)\geq s(Y)$

Primena uredi

U praksi, podaci su uglavnom sirovi i verovatnoća pronalaženja pravila u takvom skupu je veoma niska. Istraživanje pravila može da se izvede nekoliko puta, svaki put sa različitim parametrima, kako bi se povećala verovatnoća nalaska odgovarajućih, netrivijalnih pravila. To je domen, gde je jednostavnost i lakoća generisanja ogromnog skupa pravila Apriori algoritma, gotovo nepobediva. Potraga za specifičnim pravilima, ne treba uvek da ide u dubinu, iz tog razloga, što bi daljim specifikovanjem samo pravilo izgubilo na značaju i postalo trivijalno^[2].

Prvim prolaskom kroz bazu, prebrojava se svaka pojava pojedinog elementa, kako bismo otkrili sve velike 1-itemsetove L1 (frequent itemsets^[3]). U drugoj iteraciji parovi elemenata iz skupa L1, postaju kandidati, tačnije elementi skupa kandidata C2. Prolazeći kroz bazu, utvrđujemo značaj svakog elementa iz C2, svi oni elementi čiji je značaj veći od minimalnog postaju elementi skupa L2. Tako se za svaki sledeći korak, npr. korak k, može reći da se sastoji od dve faze:

U prvoj fazi se veliki itemset Lk-1 (koji je pronađen u k-1 koraku) koristi za stvaranje skupa kandidata Ck, koristeći apriori-gen funkciju.

U drugoj fazi se utvrđuje značaj svakog pojedinog kandidata iz skupa kandidata Ck. Oni kandidati koji imaju značaj veći od minimalnog, i čiji se svi podskupovi nalaze u Lk-1, postaju elementi skupa Lk.

Apriori algoritam izvodimo u onoliko koraka koliko nam je potrebno (a to je određeno sa parametrom koji definiše maksimalnu daljinu pravila K), ili dok itemset Lk ne postane prazan skup. Na kraju kad su pronađeni svi veliki itemsetovi od njih se formiraju pravila i to tako da se u obzir uzimaju samo pravila čija je pouzdanost veća od minimalne.

Pseudokod uredi

Logički se apriori algoritam može napisati u pseudokodu:

 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 =  $\bigcup _{k}Lk$ ;

Lk - predstavlja skup velikih k-itemsetova, Ck - predstavlja skup kandidata k-itemset. Funkcija apriori-gen služi za otkrivanje kandidata. Njen argument je Lk-1, skup svih velikih (k-1)-itemsetova, a kao rezultat dobijemo skup kandidata Ck, veličine k. Funkcija se sastoji od dva koraka: "join step" (korak ujedinjavanja) i "prune step" (korak pročišćavanja).

U prvom koraku spajamo elemente skupa Lk-1 sa ciljem dobijanja skupa kandidata Ck. Ovaj korak se može opisati kako pronalaženje svih parova {U,V} gde su U i V iz Lk-1 takvih da je njihova unija ima daljinu k. Kompleksnost ovog koraka je u najgorem slučaju $O(|L_{k-1}|^{3})$ gdje je $|L_{k-1}|$ broj velikih itemsetova veličine k-1. No u praksi ta složenost je najčešće linearna s obzirom na broj velikih itemsetova u svakom koraku.

U drugom koraku pročišćavamo skup kandidata Ck na način da brišemo sve one kandidate c iz Ck čiji se neki od podskupa veličine (k-1) ne nalazi u Lk-1.

Primer za apriori-gen funkciju:

Neka je $L3=\{\{123\},\{124\},\{134\},\{135\},\{234\}\}$

Nakon "join step" skup kandidata je $C_{4}=\{\{1234\},\{1345\}\}$ . U sledećem koraku dobijamo za $c_{1}=\{1234\}$ , skup njegovih (k-1) podskupova $s_{1}=\{\{123\},\{124\},\{134\},\{234\}\}$ a za $c_{2}=\{1345\}$ , skup njegovih (k-1) podskupova je $s_{2}=\{\{134\},\{135\},\{145\},\{345\}\}$ . Kako se skupovi $\{345\}$ i $\{145\}$ ne nalaze u $L_{3}$ , $c_{2}$ ćemo izbaciti iz $C_{4}$ i kao konačno rešenje apriori-gen funkcije dobićemo $C_{4}=\{\{1234\}\}$ .

Poslednji korak algoritma, kad su pronađeni je da se u obzir uzmu samo ona pravila čija je pouzdanost veća od zadane vrednosti.

Značaj kandidata iz skupa Ck se određuje tako što se prebroji koliko transakcija sadrži te kandidate. Značaj pojedinog kandidata možemo odrediti jednostavnim načinom: prolazeći kroz bazu kako bi za svaku transakciju utvrdili sadrži li ona taj kandidat, što s obzirom da se vrlo često radi o velikom broju transakcija i mogućih kandidata ovaj način čini jako sporim i stoga neupotrebljivim. Zbog toga se koriste razni trikovi koji ubrzavaju pronalaženje kandidata koji imaju značaj veći od zadanog primera organizovanjem kandidata u strukture slične stablima koji se onda brže mogu pretraživati.

Implementacija u Javi uredi

     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	}

Primer uredi

ID Transakcije	Elementi
T100	hleb, mleko, kikiriki
T200	mleko, jaja
T300	mleko, pivo
T400	hleb, mleko, jaja
T500	hleb, pivo
T600	mleko, pivo
T700	hleb, pivo
T800	hleb, mleko, pivo, kikiriki
T900	hleb, mleko, pivo

Česti jednočlani skupovi stavki

Skupovi stavki	Podrška (Support)
{hleb}	6
{mleko}	7
{pivo}	6
{jaja}	2
{kikiriki}	2

L1 = {hleb, mleko, pivo, jaja, kikiriki}

Česti dvočlani skupovi stavki

Korak ujedinjavanja

Skupovi stavki	Podrška
{hleb, mleko}	4
{hleb, pivo}	4
{hleb, jaja}	1
{hleb, kikiriki}	2
{mleko, pivo}	4
{mleko, jaja}	2
{mleko, kikiriki}	2
{pivo, jaja}	0
{pivo, kikiriki}	1
{jaja, kikiriki}	0

$C_{2}$

$C_{2}>min.supp$

Skupovi stavki	Podrška
{hleb, mleko}	4
{hleb, pivo}	4
{hleb, kikiriki}	2
{mleko, pivo}	4
{mleko, jaja}	2
{mleko, kikiriki}	2

$L_{2}$

Česti tročlani skupovi stavki

Korak ujedinjavanja

Skupovi stavki
{hleb, mleko, pivo}
{hleb, mleko, kikiriki}
{hleb, pivo, kikiriki}
{mleko, pivo, jaja}
{mleko, pivo, kikiriki}
{mleko, jaja, kikiriki}

Korak pročišćavanja

Skupovi stavki	Podrška
{hleb, mleko, pivo}	2
{hleb, mleko, kikiriki}	2

$C_{3}>min.supp$

Skupovi stavki	Podrška
{hleb, mleko, pivo}	2
{hleb, mleko, kikiriki}	2

$L_{3}>min.supp$

Korak ujedinjavanja

Skupovi stavki
{hleb, mleko, kikiriki}

$C_{4}^{'}$

Korak pročišćavanja $\rightarrow \{\}=C_{4}$

Vremenska složenost uredi

Vremenska složenost apriori algoritma data je sledećim izrazom^[3]:

$O(\sum _{k}^{K}|C_{k}|np)$

Gde je |Ck| broj kandidata daljine k, K maksimalna daljina pravila, n ukupni broj transakcija i p broj različitih elemenata koji se pojavljuju u transakcijama. Iz izraza je očigledno da se na vremensko izvođenje algoritma može uticati na više načina:

Ograničavanje broja kandidata u svakoj od iteracija algoritma – To se postiže podešavanjem parametra Supp (minimalni značaj pravila). Ako se taj parametar postavi premali onda se izlažemo opasnosti da broj kandidata Ck u svakoj iteraciji algoritma bude preveliki tako da algoritam ne bude izvodljiv u realnom vremenu, a ako se postavi veliki onda se može dogoditi da se ne pronađe niti jedno pravilo koje zadovoljava postavljeni uslov. Zbog toga je kod implementacije aplikacija koje koriste apriori algoritam za pronalaženje pravila pridruživanja dobro odrediti granice u kojima se može kretati minimalni iznos značaja. Te granice se određuju eksperimentalno a uslovljene su brojem različitih elemenata koji se pojavljuju u transakcijama te brojem transakcija.

Ograničavanje maksimalne duljine pravila K – U praksi nas obično interesiraju pravila manjih duljina (obično ne više od 5). Pravila s većim brojem elemenata obično imaju zanemarljive značaje u odnosu na pravila s manjim brojem elemenata.

Smanjivanje broja transakcija koje se analiziraju n – Ovo se postiže uzimanjem reprezentativnog uzorka iz cijelog skupa podataka. Tom prilikom treba biti oprezan i stvarno se osigurati da je uzorak reprezentativan inače se dobijeni rezultati ne mogu odnositi na celu populaciju.

Smanjivanje broja različitih elemenata p – Prema jednakosti ovaj parametar utiče na vrijeme izvođenja algoritma eksplicitno i implicitno tako što utječe na broj kandidata za velike itemsetove u svakoj iteraciji algoritma. Na njega se može uticati uvođenjem odgovarajuće taksonomije pri čemu se elementi mogu grupisati u više grupa (ili klasa) prema svojim svojstvima. Odabiranje dobre taksonomije može imati drastičan uticaj na skraćivanje vremena izvođenja algoritma a uz istodobno zadržavanje osnovnih zakonitosti zbog kojih se pravila pridruživanja uopšte i analiziraju. Na primer informacija o kupovini piva i čipsa zajedno iz pravila (“Čili Čips” $\rightarrow$ “Jelen pivo”) u pravilu (“Čips” $\rightarrow$ “Pivo”) je sačuvana. Naravno deo informacije o vrsti čipsa i piva koji se kupuju zajedno je ovim putem izgubljen a to je cena koja se plaća za ubrzavanje izvođenja algoritma. Ukoliko se načini dobra taksonomija mogu se birati nivoi na kojima se vrši analiza podataka u zavisnosti od specifičnog interesa analitičara.

Zaključak uredi

Istraživanje asocijativnih pravila proizvodi ogromnu količinu pravila, od kojih je većina redundantna. Da bismo videli apriori algoritam u punom svetlu, potrebna nam je velika baza podataka i veliko znanje o prirodi problema.

Reference uredi

^ 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.
^ ^a ^b Hand,D.;Manilla,H.;Smyth,P.:“Principles of Data Mining”, MIT Press, 2001.

[1] 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.

[2] 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.

[r1-3] Hand,D.;Manilla,H.;Smyth,P.:“Principles of Data Mining”, MIT Press, 2001.

[1]

[2]

[3]