In questo articolo esporrò lo pseudo codice dell’algoritmo A-Priori e una versione funzionante in Go.
L’algoritmo A-Priori si può riassumere nel seguente modo:
Ammettiamo di avere questo Dataset
| Transazioni | Cestino |
| 1 | {“Mela”,”Lampone”,”Ananas”} |
| 2 | {“Mela”,”Kiwi”,”Ananas”} |
| 3 | {“Lampone”,”Ananas”} |
| 4 | {“Banana”,”Kiwi”,”Ananas”} |
| 5 | {“Kiwi”} |
| 6 | {“Mela”,”Kiwi”} |
Primo passaggio di Apriori
Creiamo un insieme contenente tutti i nostri elementi singoli presi dal Dataset e creiamo una mappa contenete la frequenza dei nostri oggetti
Set = {“Mela”,”Kiwi”,”Ananas”,”Lampone”,”Banana”}
Frequency Set = {“Mela”: 3, “Kiwi”,4 “Ananas”: 4, “Lampone”: 1, “Banana”: 1}
Ammettiamo di avere settato un valore di supporto parti a 0.2, eliminiamo ora tutti gli elementi che nel Frequency Set non hanno supporto pari a 0.2. Otteniamo quindi:
Set = {“Mela”,”Kiwi”,”Ananas”,”Lampone”}
Frequency Set = {“Mela”: 3, “Kiwi”,4 “Ananas”: 4}
Secondo passaggio di A-Priori
Creiamo i nuovi insieme di candidati dal Set precedente a 2 a 2, cioè
Set = {“Mela-Kiwi”,”Mela-Ananas”,”Kiwi-Ananas”}
Questo è il nostro nuovo set di candidati che sottoporremo alla regola del supporto.
Terzo passaggio di A-Priori
Verifichiamo se il set di candidati ha nuovi elementi frequenti:
Set = {“Mela-Kiwi”,”Mela-Ananas”,”Kiwi-Ananas”}
Frequency Set = {“Mela-Kiwi”: 2 ,”Mela-Ananas”: 2,”Kiwi-Ananas”:2}
Quarto passaggio di A-Priori
Creiamo i nuovi set di candidati dal Set precedente a 3 a 3, cioè
Set = {“Mela-Kiwi-Ananas”}
Quinto passaggio di A-Priori:
Set = {“Mela-Kiwi-Ananas”}
Frequency Set = {“Mela-Kiwi-Ananas”: 1}
L’insieme di elementi piu’ frequente generato da A-Priori è “Mela-Kiwi-Ananas”, e ogni sotto insieme generato da questo è a sua volta il più frequente.
Si deduce da questo processo quindi il seguente algoritmo:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| L[1] = Genera gli elementi di dimensione 1 | |
| Calcola la frequenza degli elementi di dimensione 1 che superano minsup | |
| C[1] = L[1] | |
| Per K=2, finchè L[K-1] != vuoto; k++ { | |
| C[K] = genera le coppie da L[K-1] con cardinalità K | |
| L[K] = Calcola la frequenza degli elementi in C[K] che superano minsup | |
| } | |
| Ritorna L[K] |
Il pattern con cui ci muoviamo è quindi questo:
Prima filtriamo i dati e poi costruiamo i dati successivi finchè non otteniamo il nostro risultato finale.
Ho scritto un codice in Go che ci permette di applicare A-Priori come specificato dal nostro algoritmo.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "github.com/deckarep/golang-set" | |
| "strings" | |
| "fmt" | |
| "sort" | |
| ) | |
| func main() { | |
| dataset := [][]string{ | |
| []string{"pane", "cereali", }, | |
| []string{"pane", "latte", "caffè"}, | |
| []string{"latte", "cereali"}, | |
| []string{"latte", "caffè"}, | |
| []string{"pane", "latte", "cereali"}, | |
| []string{"latte", "cereali"}, | |
| []string{"pane", "cereali"}, | |
| []string{"pane", "latte", "te"}, | |
| []string{"pane", "latte", "cereali", "te"}, | |
| []string{"pane", "te"}, | |
| []string{"pane","caffè"}, | |
| } | |
| minimumSupport := 0.4 | |
| minConfidence := 0.2 | |
| apriori(dataset, minimumSupport, minConfidence) | |
| } | |
| func apriori(dataset [][]string, support float64, confidence float64) { | |
| elements := elements(dataset) | |
| freqSet := make(map[string]float64) | |
| largeSet := make(map[int]mapset.Set) | |
| oneCSet := returnItemsWithMinSupport(elements, dataset, support, &freqSet) | |
| currentLSet := oneCSet | |
| k := 2 | |
| for currentLSet.Cardinality() != 0 { | |
| largeSet[k-1] = currentLSet | |
| currentLSet = joinSet(currentLSet, k) | |
| currentCSet := returnItemsWithMinSupport(currentLSet, dataset, support, &freqSet) | |
| currentLSet = currentCSet | |
| k = k + 1 | |
| } | |
| fmt.Println(largeSet) | |
| } | |
| func returnItemsWithMinSupport(itemSet mapset.Set, dataset [][]string, minSupport float64, freqSet *map[string]float64) mapset.Set { | |
| localItemSet := mapset.NewSet() | |
| localSet := make(map[string]float64) | |
| for _, item := range (itemSet.ToSlice()) { | |
| dkey := strings.Split(item.(string), "-") | |
| sort.Strings(dkey) | |
| for _, line := range(dataset) { | |
| if contains(line, dkey) { | |
| key := strings.Join(dkey, "-") | |
| (*freqSet)[key] += 1.0 | |
| localSet[key] += 1.0 | |
| } | |
| } | |
| } | |
| for item, count := range (localSet) { | |
| support := count / float64(len(dataset)) | |
| if support >= minSupport { | |
| localItemSet.Add(item) | |
| } | |
| } | |
| return localItemSet | |
| } | |
| func joinSet(itemSet mapset.Set, length int) mapset.Set { | |
| ret := mapset.NewSet() | |
| for _, i := range (itemSet.ToSlice()) { | |
| for _, j := range (itemSet.ToSlice()) { | |
| i := i.(string) | |
| j := j.(string) | |
| i_a := strings.Split(i, "-") | |
| j_a := strings.Split(j, "-") | |
| dkey := (union(i_a, j_a)) | |
| if len(dkey) == length { | |
| sort.Strings(dkey) | |
| key := strings.Join(dkey, "-") | |
| ret.Add(key) | |
| } | |
| } | |
| } | |
| return ret | |
| } | |
| func union(a []string, b []string) []string { | |
| ret := mapset.NewSet() | |
| for _, v := range (a) { | |
| ret.Add(v) | |
| } | |
| for _, v := range (b) { | |
| ret.Add(v) | |
| } | |
| rets := []string{} | |
| for _, v := range (ret.ToSlice()) { | |
| rets = append(rets, v.(string)) | |
| } | |
| return rets | |
| } | |
| func elements(dataset [][]string) mapset.Set { | |
| ret := mapset.NewSet() | |
| for i := 0; i < len(dataset); i++ { | |
| for j := 0; j < len(dataset[i]); j++ { | |
| if ret.Contains(dataset[i][j]) == false { | |
| ret.Add(dataset[i][j]) | |
| } | |
| } | |
| } | |
| return ret | |
| } | |
| func contains_dataset(s [][]string, e []string) bool { | |
| ret := false | |
| for _, v := range (s) { | |
| ret = contains(v, e) | |
| if ret == true { | |
| break | |
| } | |
| } | |
| return ret | |
| } | |
| func contains_element(s []string, e string) bool { | |
| ret := false | |
| for _, a := range s { | |
| if a == e { | |
| ret = true | |
| break | |
| } | |
| } | |
| return ret | |
| } | |
| func contains(s []string, e []string) bool { | |
| count := 0 | |
| if len(s) < len(e) { | |
| return false | |
| } | |
| mm := make(map[string]bool) | |
| for _, a := range e { | |
| mm[a] = true | |
| } | |
| for _, a := range s { | |
| if _, ok := mm[a]; ok { | |
| count += 1 | |
| } | |
| } | |
| return count == len(e) | |
| } |
Limitazioni di A-Priori
- È molto esoso dal punto di vista della computazione. Seppure riducendo il numero di candidati da considerare, il numero di questi è sempre molto grande quando il numero di elementi nei cestini della gente è alto o quando il valore limite di supporto è basso.
- Associazioni False. Riducendo il valore limite di supporto per notare alcuni tipi di associazioni, può succede che ci siano delle associazioni non giuste e quindi false. Per ridurre questo problema occorre filtrare prima il Dataset o verificare il valore di supporto e confidenza in un Test Set separato.
Conclusioni
A-Priori si dimostra essere un algoritmo molto interessate per studiare le associazioni all’interno di un Dataset con transazioni. Nonostante abbia delle limitazioni ci sono stati degli algoritmi che lo hanno migliorato come ad esempio l’algoritmo PCY o l’algoritmo Multistage.