Lezioni 15 16

Analisi di Attributi

Uno dei modi più comuni per descrivere una risorsa, è quello di elencare gli attributi che appartengono a quella risorsa, quindi descrivere questa risorsa come un vettore di termini.
Con attributo indichiamo un predicato unario: P1(x), P2(x).
Questa risorsa possiede un certo predicato, ed è in contrapposizione con l'analisi di reti(grafi), perchè in quel caso parlavamo di predicati binari: A(n1,n2)…. ed eravamo interessati agli archi che connettevano due risorse.

Per capire quali strumenti possiamo utilizzare per analizzare risorse descritte come insiemi di attributi, riprendiamo il concetto di:

  • Estensione= elementi che appartengono all'insieme
  • Intensione= le proprietà vere per quell'insieme

Queste nozioni sono state già viste nei casi dei paradossi linguistici. Con il concetto di estensione possiamo richiamare la nozione di denotazione del linguaggio(linguaggio che indica qualche cosa). Intensione richiama la nozione di connotazione(descrizione di un oggetto con delle proprietà). Prendiamo ad esempio la frase "L'attuale Re di Francia è calvo" sappiamo che non esiste nessun Re di Francia quindi è una connotazione priva di denotazione.
Grazie a questi concetti è possibile dare la definizione di concetto:

  • un concetto è una connotazione che fornisce la denotazione di un insieme di individui non connotabili altrimenti.

E' facile notare come all'ampliamento della connotazione denoterebbe un numero più ristretto di individui, mentre diminuendo la connotazione vengono denotati un maggior numero di individui.
C'è una teoria matematica che ha dato delle definizioni precise delle definizioni di concetto e di come costruire una gerarchia di concetto.

Formal Concept Analysis

Su questa nozione è stata definita una teoria matematica che permette di ottenere la gerarchia dei concetti espressi da una contesto di oggetti e attributi descritto da una matrice booleana (Tabella). Per costruire la tabella mettiamo da un lato gli oggetti, dall'altro un insieme di proprietà che descrivono gli individui.

Tabella

Definiamo un contesto formale come una tripla fatta da oggetti, attributi e di relazioni binarie. Oppure in maniera più formale un formal context K e una tripla (O, A, I). O è un insieme i cui elementi sono detti formal objects, A è un insieme i cui elementi sono detti formal attributes, I ⊆ O × A è una relazione binaria tra essi.
Introduciamo quindi due operatori di derivazione:

  • P(O) → P(A)
  • P(A) → P(O)

Il primo è un operatore che ci permette di passare dagli oggetti agli oggetti che hanno in comune, mentre il secondo svolge il compito inverso. Un concetto formale è dato quindi da una coppia di oggetti e attributi, nel quale le operazioni definite danno lo stesso risultato. Oppure detto in maniera formale definiamo le operazioni precedenti su un insieme di oggetti Q ⊆ O e su un insieme di attributi E ⊆ A:

  • P(Q): restituisce gli attributi in A condivisi dagli oggetti in Q
  • P(E): restituisce gli oggetti in O che hanno tutti gli attributi in E

Un formal concept è una coppia (Q, E) tale che P(Q) = E e P(E) = Q.

Nel caso identificassimo un concetto diremo che l'insieme degli attributi rappresenta l'intensione(connotazione), mentre gli individui rappresentano l'estensione(denotazione).
Dati un insieme di attributi E verifichiamo che individuino un insieme di oggetti Q che non possiedeno altri attributi e abbiamo identificato un concetto formale.

L'obiettivo della FCA è quindi quello di dare definizioni formali e di inserirle in una teoria in grado di permettere l'organizzazione dei concetti in strutture gerarchiche seguendo il Teorema fondamentale della FCA, cioè: per ogni formal context K = (O, A, I) l'insieme dei suoi formal concepts forma un reticolo completo, detto concept lattice (grafo dei concetti), ordinato dalla relazione di super/sotto-concetto.

La relazione di super/sotto concetto viene definita nel modo seguente:
(Q, E) ≤ (C, D) = Q ⊆ C ⇔ D ⊆ E

Grazie al teorema possiamo costruire un reticolo dei concetti come nella figura sottostante

Reticolo

In questo caso tutto l'insieme dei concetti rappresenta il nodo iniziale(quello in alto), nel momento in cui incontriamo un attributo, questo sarà condiviso dai sottoconcetti del concetto incontrato nel reticolo. Per gli oggetti tutti i concetti sopra quello che introduce un certo oggetto avranno quell'oggetto nell'estensione. Quindi il concetto introduttore di un oggetto e il più
basso tra quelli che lo hanno.
Gli archi sono elementi della relazione di super/sotto- concetto. Dato che tale relazione è transitiva, si possono omettere gli archi impliciti.
A questo tipo di reticolo possono essere fatte diverse interrogazioni:

  • Quali oggetti hanno gli stessi attributi ? (vado al concetto dove si incontrano)
  • Quali attributi condividono gli oggetti ? (Vado al concetto dove si uniscono)
  • Qual'è l'estensione del concetto ? Vai giù fino al bottom collezionando gli oggetti che incontra
  • Qual'è l'intensione ? Vai su fino al top collezionando gli attributi che incontra

I problemi nascono quando non riusciamo a rappresentare in maniera binaria le relazioni tra oggetti e attributi. A quel punto creiamo delle scale negli attributi e poi assegniamo una relazione binaria. Guardiamo un esempio:

ScalaReticolo


In questo caso è difficile rappresentare in maniera binaria le relazioni

ScalaReticolo2




allora per rendere il tutto più semplice modifichiamo la tabella inserendo delle scale all'interno degli attributi come nella figura qui a lato

E' facile intuire che reticolo ricavato

ScalaReticolo3

è ottenuto dall'unione delle 2 tabelle sottostanti:

ScalaReticolo4

A questo punto possiamo istituire delle regole di associazione che non sono altro che delle regole di tipo “IF a THEN b”. Esse servono per vedere se le associazioni sono regolari nel contesti in analisi.

Definiamo a questo punto anche i concetti di :

  • Confidenza di una regola: il rapporto tra i casi che soddisfano sia condizione che conseguenza e i casi che soddisfano la condizione.
  • Supporto di una regola: il rapporto tra i casi che soddisfano sia condizione che conseguenza e il totale dei casi.

E' ovvio che se confidenza e supporto sono al 100% non trovo molto interesse, perchè non vi sono irregolarità da analizzare.
Le regole di associazione vengono usate per esempio nelle fidaty card dei supermercati, in cui da descrizioni sommarie posso risalire a diversi comportamenti della clientela.

Prendiamo ad esempio la seguente tabella:

RegolaAssocia

Ammettiamo di voler valutare l'associazione fra sesso e voti presi dagli studenti, trasformiamo la tabella in questo modo:

RegolaAssocia2Giusto

Dopo creiamo il reticolo dei concetti che ci permette visivamente di vedere in modo semplice le cardinalità degli attributi e di calcolare la confidenza di ogni regola.

RegolaAssocia3

La FCA è quindi un elegante teoria in grado di mostrare come un insieme di descrizioni di oggetti che fanno riferimento ad uno stesso contesto possano essere organizzare in una gerarchia formale.
Abbiamo visto che può supportare diverse applicazioni:

  • regole di associazione (association rules)
  • visualizzazione comunità
  • viene utilizzata anche per organizzare la costruzione delle classi nell'ingegneria del software
  • per organizzare corpi formali di documentazione

Raffinamenti Query

Nel raffinamento delle query, il problema tipico riguarda la sinonimia e della polisemia, soprattutto la polisemia. Ad esempio la parola Ruby può avere diversi significati e rende la ricerca più difficile, con la FCA anche se uso un termine ambiguo, posso organizzare i diversi gruppi di parole chiave legate ad una ricerca, in una gerarchia che può essere navigata. Ad esempio la parola Ruby può corrispondere a diversi significati

RafQuery

Il problema si pone quando non riusciamo a distinguere la rilevanza dei sottoinsiemi. In questo caso bisogna sempre ricordarsi che:

  • la dimensione non corrisponde alla rilevanza
  • si possono utilizzare dei vocabolari, ma il linguaggio si evolve e quindi è difficile che siano completi

Visualizzazione Comunità

Quando invece la utilizziamo per visualizzare le comunità dobbiamo ricordarci che la FCA lavora per fattorizzazione di insiemi di attributi, calcolando tutti i sotto di un insieme (capaci di identificare insieme di oggetti). Sarà quindi utile quando possiamo vedere una struttura come formata da due categorie di oggetti, e siamo interessati alle loro relazioni cioè a collegamenti tra categorie e non tra oggetti della stessa categoria. Viene utilizzata per analizzare strutture su grafi bipartiti o eventualmente su uno stesso insieme di risorse ripartite su più grafi bipartiti.

Il tipico esempio, è quello molto in voga al momento della condivisione di risorse tramite social tagging o tramite folksonomies ad esempio:

L'utilizzo dei tag può essere ben rappresentato dalla figura sottostante in cui il triangolo descrive la relazione tra le risorse, gli utenti e i tag che vengono utilizzati per descrivere le risorse

Tag

Bisogna anche ricordarsi che l'utilizzo dei tag segue una legge ad invarianza di scala, cioè i tag più utilizzati vengono resi più visibili e quindi ulteriormente utilizzati.
Il problema della FCA è di riportare la descrizione di un tag in forma binaria. Nel caso più semplice colleghiamo le risorse ai tag, oppure le risorse agli utenti, però in questo modo perdiamo l'informazione che lega le cose assieme(la risorsa ai tag dallo specifico utente), però possiamo usare lo stesso una semplificazione dicendo che siamo interessati ad analizzare questa relazione binaria.
Le tabelle sottostanti invece mostrano come possono essere costruiti questi ambienti di social tagging

Tabella1
Tabella2

Ci si accorge quindi di essere ancora in presenza del problema della similarità. Per vedere infatti se due nodi appartengono allo stesso gruppo, bisogna valutare la similarità strutturale. Per farlo possiamo utilizzare una funzione generica:

Similarità

Prima di applicare una analisi sulla gerarchia è utile definire delle trasformazioni sul contesto, tipicamente sugli attributi.

Ad esempio si può decidere di non considerare l’attributo ma una classe a cui appartiene.
E' importante trasformare la relazione in binaria visto che non è possibile fare un'analisi sulla gerarchia senza questo requisito.

Prendiamo ad esempio la comunità di baratto Zerorelativo, potremmo analizzare gli scambi stessi, in base alla distanza e in base al tipo di consegna.

Zerorelativo

Un analisi di questo tipo è complementare a un tipo di analisi legata alle relazioni tra individui, in un grafo in cui gli oggetti sono della stessa categoria. La prima cosa da fare è vedere se sono in grado di organizzare un grafo bipartito, altrimenti provo a modificarlo in un altra cosa oppure l'analisi non è significativa. Il risultato è quello evidenziato nella figura sottostante:

Zerorelativo2

La complessità di questi algoritmi non è semplice infatti:

  • Algoritmo LATTICE O(|O|2 ×|A|)
  • Algoritmo NEXTCONCEPT O(|C|2 )

Problemi
Tipici problemi che sono legati all'analisi che usano parole chiave (tag, ricerca di termini), oltre ai problemi di polisemia, bisogna notare che i termini descrivono già gerarchie logiche. Vi sono reti di relazioni tra termini(Semantic Networks), esse sono regolate da:

  • meronimia: un termine descrive una parte di un altro termine
  • iperonimia: il termine è superclasse di un altro termine
  • iponimia: un termine può essere contenuto da un altro

Queste relazioni esistono e non possono essere valutate attraverso una semplice analisi dei termini stessi. Quindi durante le nostre analisi ci sono relazioni implicite che non venendo rappresentate, sfalsano le nostre analisi. Per aiutarci è possibile utilizzare Wordnet(vocabolari che mostrano le relazioni di iponimia, meronimia, iperonimia), che possono essere interrrogati da applicazioni attraverso API. Il problema di Wordnet è la genericità che viene a mancare in alcuni ambiti molto tecnici. Altro problema è il fatto che la lingua essendo in continua evoluzione, rende difficile e costoso mantenerlo aggiornato.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License