di ·0 commenti

In questo articolo spiegherò come creare degli oggetti Clusterizzati in Python usando la libreria SciPy.
SciPy mette a disposizione per noi un sacco di metodi per il Clustering, noi utilizzeremo quelli che abbiamo visto nell’articolo precedente.

Il seguente file IPython fa vedere perfettamente la procedura con un metodo di collegamento fra i cluster di tipo singolo basato sulla distanza euclidea.

Il file ha i commenti che indicano ogni singola operazione avvenuta.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

clustering.ipynb

hosted with ❤ by GitHub

di ·0 commenti

L’analisi del cluster è un processo in cui si raggruppano insiemi di oggetti in modale tale da creare insiemi di oggetti i cui elementi siano piu’ simili fra loro rispetto agli elementi negli altri gruppi. I gruppi vengono detti Cluster

Schermata del 2017-08-27 12-59-16

Il clustering è una tecnica base del data mining e viene usata in altri ambiti molto simili (Machine learning, pattern recognition, analisi immagini,ecc)

Per Clustering Gerarchico (Hierarchical Clustering) si intende un metodo di analisi dei cluster che vuole ottenere gerarchie di cluster. Si può effettuare in due modi:

  • Agglomerativo: Si parte dai dati singoli e si uniscono via via i cluster
  • Divisorio: Si parte da un unico cluster e si dividono via via

Per capire quale cluster va diviso o unito si fa riferimento alla metrica, cioè una misura di similarità o dissimilarità, la metrica viene usata come distanza fra le coppie.

Le metriche (Metric) sono influenzate dal tipo di dati che abbiamo, esse possono essere:

  • Distanza Euclidea
  • Distanza Euclidea Quadra
  • Distanza di Manhattan
  • Distanza Massima
  • Distanza di Mahalanobis
  • Distanza di Hamming
  • Distanza di Levenshtein

Per capire invece quando degli insiemi vanno uniti si usano i Criteri di Collegamento (Linkage Criteria). I criteri di collegamento vengono effettuati basandosi sulle distanze fra gli elementi dei cluster e fanno capire se occorre unire i cluster o meno. I criteri sono:

  • Collegamento Singolo (Single Linkage): la distanza di collegamento fra due cluster viene definita come la distanza minima fra i due elementi del cluster

Schermata del 2017-08-27 12-51-59

  • Collegamento completo (Complete Linkage): la distanza di collegamento fra due cluster viene definita come la distanza massima fra i due elementi del cluster

Schermata del 2017-08-27 12-52-06

  • Collegamento Medio (Average Linkage): la distanza di collegamento fra due cluster viene definita come la distanza media fra tutti i punti del cluster con tutti gli altri punti del cluster

Schermata del 2017-08-27 12-59-02

Nel prossimo articolo illustrerò un esempio di clustering gerarchico con codice in Python!

di ·0 commenti

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:


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]

view raw

gistfile1.txt

hosted with ❤ by GitHub

Il pattern con cui ci muoviamo è quindi questo:
Schermata del 2017-08-22 19-28-54

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.


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)
}

view raw

Apriori.go

hosted with ❤ by GitHub

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.

di ·0 commenti

L’algoritmo A-Priori ha un semplice obiettivo, trovare oggetti comprati assieme dentro dei carrelli, cioè trovare le regole di associazione degli elementi all’interno di un insieme di dati.

Il nome A-Priori deriva da come l’algoritmo opera, cioè senza avere nessuna conoscenza effettiva dei dati, ma lavorando sull’intuizione delle associazioni fra gli elementi.

Quando un cliente compra in un supermercato ha di solito una lista delle cose che vuole comprare. Ogni cliente ha bisogni diversi, dalla casalinga al lavoratore single, ma dietro questi clienti ci sono pattern di oggetti comprati spesso assieme. Scoprire questi pattern è molto utile in quanto permette di fare promozioni questi oggetti quando sono comprati assieme.

Un problema che tratta le regole di associazione di elementi si basa su un Dataset formato in questo modo:

Transazioni Cestino
1 {“Mela”,”Lampone”,”Ananas”}
2 {“Mela”,”Kiwi”,”Ananas”}
3 {“Lampone”,”Ananas”}
4 {“Banana”,”Kiwi”,”Ananas”}
5 {“Kiwi”}
6 {“Mela”,”Kiwi”}
… …

Abbiamo cioè delle transazioni con carrelli di frutta comprati assieme, dobbiamo trovare quindi quando un elemento è stato comprato assieme ad un altro.
L’algoritmo utilizza un approccio bottom-up, parte cioè dai singoli elementi per arrivare poi a creare insiemi di oggetti.

L’effettività dell’algoritmo A-Priori si basa sul fatto che l’insieme degli oggetti  frequenti derivato dall’insieme di tutti gli oggetti è monotono.

Per monotono si intende questo:

Se per il nostro Dataset, l’insieme di elementi {“A”,”B”,”C”} è il più frequente (cioè l’insieme di elementi che compare più spesso), allora i sottoinsiemi di questo (cioè {“A”,”B”},{“B”,”C”},{“A”,”C”},{“A”},{“B”},{“C”}) saranno a loro volta fra i più frequenti.

Trovando cioè la transizione più lunga più frequente, sappiamo automaticamente che tutti i sottoinsieme derivati da questa sono frequenti!

Un altro vantaggio dell’algoritmo A-Priori è che riduce la memoria necessaria a individuare gli insiemi di oggetti associati. Senza l’algoritmo A-Priori dovremmo enumerare tutti i gli insiemi possibili di oggetti a 2 a 2, a 3 a 3, a 4 a 4 e trovare poi i più frequenti nel nostro Dataset.

Le regole associative dei nostri dati si basano sugli attributi che legano i valori delle transazioni. Le regole associative sono nella forma A=>B,  che si legge come: Le transazioni in cui compare A compare anche B.

Le regole associative sono soddisfatte quando superano due valori statistici: Il supporto e la confidenza.

Per supporto intendo la percentuale di transazioni che contengono sia A che B sul totale. Per confidenza invece intendo la percentuale percentuale di transazioni che contengono sia A che B sul numero di transazioni che contengono A.

Nel nostro caso precedente se prendiamo il dataset della frutta troviamo che:

Supporto(Mela,Kiwi) = 2/6
Confidenza(Mela,Kiwi) = 2/2

Abbiamo cosi’ notato che la confidenza che Mela e Kiwi siano comprate assieme è molto alta mentre il numero valore di supporto è basso.

Formalmente quindi l’algoritmo A-Priori si basa sull’estrarre regole di associazione in un dato Dataset con un supporto superiore al minimo stabilito e/o una confidenza superiore alla minima stabilita.

Le regole che soddisfano questi dati sono dette Regole di associazione forte.

Nel prossimo articolo illustrerò lo pseudo codice e il codice per l’algoritmo A-Priori che utilizza come metrica il supporto.