Многи од алгоритама за проналажење шаблона као што су стабла одлучивања, правила одлучивања и кластеровање који се често користе за истраживање података су произведени за машинско учење. Истраживање честих шаблона и правила асоцијације су једни од пар изузетака у овој традицији. Његово увођење убрзало је истраживање података и његов утицај је огроман. Априори алгоритам први пут је описан у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. и користи се за проналажење правила придруживања анализирањем трансакција. Представљa класичан, врло користан алгоритам за откривање правила асоцијације.
Априори својство
Ако дати скуп није велики скуп, тада нити један његов надскуп не може бити велики скуп.
Априори принцип је заснован на својству антимонотоности за support меру
Примена
У пракси, подаци су углавном сирови и вероватноћa проналажења правила у таквом скупу је веома ниска. Истраживање правила може да се изведе неколико пута, сваки пут са различитим параметрима, како би се повећала вероватноћa наласка одговарајућих, нетривијалних правила. To је домен, где је једноставност и лакоћa генерисања огромног скупа правила Априори алгоритма, готово непобедива. Потрага за специфичним правилима, не треба увек да иде у дубину, из тог разлога, што би даљим спецификовањем само правило изгубило на значају и постало тривијално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..
Првим проласком кроз базу, пребројава се свака појава појединог елемента, како бисмо открили све велике 1-itemsetove L1 (frequent itemsetsHand,D.;Manilla,H.;Smyth,P.:“Principles of Data Mining”, MIT Press, 2001.). У другој итерацији парови елемената из скупа 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");