Bank Intelligence: Un sistema per il monitoraggio del settore incassi e

pagamentiUn’esperienza (reale) di utilizzo di Data Mining

Giuseppe MancoICAR-CNR, Rende

giuseppe.manco@icar.cnr.it

Intermezzo: dove trovare il materiale del workshop

Sito web del corso “Data Mining e Scoperta di Conoscenza”– http://www.icar.cnr.it/manco– Da lì, seguire i links

Sommario

Data Warehousing e Mining per l’analisi del rischioLa proposta in Bank-IntelligenceIl problema della normalizzazione dei datiRiconoscitore Anagrafico

Processi decisionali e data Processi decisionali e data warehousingwarehousing

Motivazioni: richieste tipiche nei processidecisionali

Qual è il volume degli effetti per provincia e categorie di attività durante l’ultimo anno?Come si correlano gli importi degli effetti delle società edili con gli insoluti trimestrali? In che modo gli incassi degli effetti si esplicitano nel corso dell’anno?

Un approccio unificante: Il Data Warehousing

processo di integrazione di sorgenti di datiindipendenti in un singolo archivio (data warehouse) su cui gli utenti finali possonoeseguire query, generare report ed effettuareanalisi in modo– facile– efficace– efficiente

Il modello concettuale di riferimento

Dati multidimensionali– E’ il paradigma di interrogazione dei dati più utilizzato per le analisi

OLAP sui BIW

Permette di modellare ed interrogare i dati sulla base dei seguenti concetti:

– fatto rappresenta un processo o un eventoè il concetto sul quale si centra l’analisi

– misurauna proprietà atomica di un fatto da analizzarele misure sono solitamente valori numerici su domini continuo

– dimensioneuna prospettiva rispetto alla quale effettuare l’analisile dimensioni descrivono domini discreti, solitamente organizzati in livelli di aggregazione

Il Data Il Data MartMart per lper l’’analisi del analisi del rischiorischio

La proposta in Bank-Intelligence

Fatto: effetti presentati allo sconto/incassoDimensioni principali

– OrdinanteIl creditore -> colui che presenta l’effetto in banca

– DestinatarioIl debitore -> il soggetto che deve pagare l’effetto

– Tipo prodottoMAV, RID, RIBA, ecc.Può essere caratterizzato dal altre proprietà

– EventoDescrive la storia dell’effettoUn effetto può essere insoluto, protestato, con azione giudiziaria in corso, ecc.

Adeguatezza del modello

Permette di modellare business needsestremamente complicati– Applicazioni come interfacce a query specifiche

Strumento chiave: MDX– Multi-Dimensional eXpressions– Linguaggio per la manipolazione di dati su cubi

Definito da Microsoft, implementato su SQL Server– Essenzialmente, linguaggio per la manipolazione di

fogli di calcolo a più dimensioni– Non strettamente necessario

Il modello permette le manipolazioniSemplifica significativamente il task di specifica della query

Esempi di interrogazioni OLAP

Determinare il numero degli effetti presentati a Dicembre 2003 e che hanno cambiato stato a Gennaio 2004 (possibili stati: {IN,PG,SC…})

with member Measures.[Situazione effetti a Gennaio 2004] as'SUM( DESCENDANTS([Forma Tecnica].CURRENTMEMBER, [Numero Effetto]),IIF(Importo,Evento.CurrentMember,[Data Evento].[All Data

Evento].[2004].[January])>0 AND (Importo, [Evento].[All Evento].[PR],[Data Evento].[All Data Evento].[2003].[December])>0, 1, 0) )'

select {Measures.[ProdottiPresentati e...]} on columns,{[Evento].[Evento].members} on rowsfrom [MarketBasket]

Esempi di interrogazioni OLAP

Esempi di interrogazioni OLAP

Determinare la percentuale di insoluti su presentati calcolata sugli importi totali indipendentemente dal destinatario e dall’ordinante:

with member Measures.[Presentati e Insoluti] as 'SUM( DESCENDANTS([Forma Tecnica].CURRENTMEMBER, [Numero Effetto]),IIF((Importo,Evento.[All Evento].[IN])>0 AND (Importo, [Evento].[All Evento].[PR],[Data

Evento].currentmember)>0, Importo, 0))'member Measures.[Presentati] as '([Evento].[All Evento].[PR],[DataEvento].currentmember,Measures.[Importo])'member Measures.[Insoluti su Presentati] as

'IIF(Measures.[Presentati]> 0, Measures.[Presentati e Insoluti]/Measures.[Presentati],0)',format_string='#.00%'

select {Measures.[Presentati e Insoluti],[Measures].[Presentati],Measures.[Insoluti suPresentati]} on columns,

{[Data Evento].[Month].members} on rowsfrom [MarketBasket]

Esempi di interrogazioni OLAP

Esempi di interrogazioni OLAP: ANALISI ANDAMENTALE

Determinare, con cadenza mensile, la quantità degli effetti impagati e scaduti relativi alla relazione tra un dato ordinante ed un dato destinatario

with member Measures.[Analisi Andamentale] as'SUM(Descendants([Forma Tecnica].currentmember,[Numero Effetto]), IIF( (([Evento].[All

Evento].[IN],[Data Evento].currentmember,Importo)>0 and ([Evento].[AllEvento].[SC],[Data Evento].currentmember,Importo)>0),1,0 ))'

select {Measures.[Analisi Andamentale]} on columns,{[Data Evento].[Month].members} on rowsfrom [MarketBasket]where ([Ordinante].[All Ordinante].[PI].[Calci].[Via di Pandi].[BIZZOTTO SRL],

[Destinatario].[All Destinatario].[MI].[Milano].[*VIA* FORGITELLE].[LEONI UGO])

Esempi di interrogazion OLAP

Esempi di interrogazioni OLAP

Si vuole sapere,raggruppati per ordinante e mese, l'importo e lequantità di tutti gli effetti di pertinenza di un certo debitore(EVENTO=PR):

select {Measures.[Importo],Measures.[Codice]} on columns,{crossjoin(Head([Ordinante1].[Intestazione].members,1000),[Data

Evento].[Month].members)} on rowsfrom [MarketBasket]where ([Destinatario].[All Destinatario].[MI].[Milano].[*VIA*

FORGITELLE].[LEONI UGO])

Esempi di interrogazione OLAP

Architettura generale proposta

Le principali problematiche

Le dimensioni vanno costruite opportunamente!– Aspetto “sintattico”

Attribuire le giuste aggregazioni– Pulizia dei dati– Riconoscimento anagrafico

OrdinanteDestinatario

– Aspetto semanticoCome modellare alcune dimensioni in modo che garantiscano

– Flessibilità– Efficienza

Gli eventi sono particolarmente problematici da modellareSoluzione prospettata: utilizzo di tecniche di data mining per la ricostruzione delle dimensioni

– Case-based reasoning per la ricostruzione dell’anagrafica– Market-basket analysis per l’analisi degli eventi

Il problema della normalizzazione Il problema della normalizzazione dei Datidei Dati

Il problema della normalizzazione

Problema principale– Soggetti semanticamente omogenei,

sintatticamente scorrelati– Come ricostruire l’omogeneità?– Tre tipi di disomogeneità

Valori non normalizzati– E.g. località non corrispondente al CAP

Valori difformi– E.g., Giuseppe Manco <-> G. Manco

Mancanza di formattazione

Il problema della normalizzazione [1/5]

La memorizzazione dei dati anagrafici soffre inevitabilmente l’incoerenza e la ridondanza dovute alla difformità nella compilazione manuale– Esempio:

Dati relativi a utenti di servizi bancari Compilazione da parte degli operatori presso gli sportelli bancari.

Il problema della normalizzazione: un esempio [2/5]

Destinatario (ID, Intestazione, Indirizzo, CAP, Provincia, Località, CF_PI, Cod_SIA, Cod_NDG)

Intestazione Indirizzo CAP Provincia Località

"IL PUNTO" DI CASULLI GIOVANNI & C. S.A.S

VIA P UMBERTO 74 70015 BA NOCI

IL PUNTO -G.CASULLI & C.SAS

VIA PRINCIPE UMBERTO 74- 86

70015 N O C I Bari

Il problema della normalizzazione: un esempio [3/5]

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

nel primo record la denominazione IL PUNTO appare fra virgolette,

nel secondo record è solo separata con un trattino dal resto del testo

nel secondo record non appare la stringa DIil nome GIOVANNI, presente nel primo record, è abbreviato con la sola G. nel secondo recordle stringhe non presentano lo stesso ordine di parole nei due record

Il problema della normalizzazione: un esempio [4/5]

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

nel primo record la stringa PRINCIPE è abbreviata con Pnel secondo record compare anche il numero 86, assente nel primorecord

Il problema della normalizzazione: un esempio [5/5]

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

N O C I Bari N O C I Bari 7001570015VIA PRINCIPE VIA PRINCIPE UMBERTO 74UMBERTO 74-- 86 86

IL PUNTO IL PUNTO --G.CASULLI & G.CASULLI & C.SAS C.SAS

NOCI NOCI BABA7001570015VIA P UMBERTO 74 VIA P UMBERTO 74 "IL PUNTO" DI CASULLI "IL PUNTO" DI CASULLI GIOVANNI & C. S.A.SGIOVANNI & C. S.A.S

LocalitàLocalitàProvinciaProvinciaCAPCAPIndirizzoIndirizzoIntestazioneIntestazione

nel secondo record manca la sigla della provincia

nel secondo record la stringa NOCI è stata digitata lasciando uno spazio fra ogni carattere (N O C I) la presenza della stringa BARI è superflua nel campo Localitàmentre è necessaria nel campo Provincia.

Il nostro approccio

Input: database utenti della bancaOutput: database normalizzatoMetodo:

– CleaningParsingRipulitura dei dati

– NormalizzazioneCompletamento dei dati Eliminazione delle ridondanzeFormattazione uniforme dei dati

Un ulteriore problema…

In alcuni casi i dati non sono formattati in campi– “Rumore” sul rumore…

FRENOFLEX S.R.L. VIA ROBERTO BRACCO, 1 20159 MILANO MI METALSA STAGNO SRL VIA ACHILLE GRANDI 15 20017 RHO MI "COMETE" DI MURARO LORENZO SPA VIA PASUBIO 51-53 OLMO DI CREAZZO 3D disinfettanti s.r.l. Via R. Wenner, 20-a - Zo84131 Salerno SA A&C ADIVAR-COMIFAR S.P.A. VIA NOCERA UMBRA 75 ROMA A.E.R.P. S.A.S. DI RICCARDO BOLGIANI EC VIA D. VITTORIO 4 LOGRATO ZAF S.p.A. S.S. 35 dei Giovi 9 Zibido S.Giacomo MI

Riformattazione

Estrazione corretta dei campi relativi all’ordinante:– Intestazione,Indirizzo,CAP,Provincia,Località

Da preprocessare in una fase successiva

Approccio base– Preprocessing della stringa– Inserimento, per ogni parola, di alcuni tag

identificativi della semantica della parola stessa– Estrazione dei vari campi

Regolarità osservabili (euristiche)

il primo campo è l’intestazione dell’azienda, a volte completato dalla forma sociale (S.p.a, S.r.l., etc.);dopo l’intestazione spesso viene inserito l’indirizzo (introdotto dalle parole VIA, LARGO, STRADA, etc);l’ultimo campo è quello relativo alla località, spesso identificata soltanto dal Comune e dalla provincia (il C.A.P. èquasi sempre omesso).Problema:

– Le euristiche dipendono dal “modus operandi” dell’operatore di sportello

– Come renderle “adattative”?

Una soluzione: classificatore automatico

Utilizzo di tecniche di classificazione supervisionataOgni oggetto rappresenta una singola parola all’interno della stringa DENOMINAZIONE

– Attributi:la posizione che essa occupa nella stringa, la stringa prefissa, La stringa postfissa,

Obiettivo– Predire l’etichetta giusta da utilizzare

Metodo– Utilizziamo un campione supervisionato dei dati– Cerchiamo regole generali che profilino tali risultati

Un esempio

“LEVONI SPA VIA”, MATTEOTTI, “23 COSENZA”– Pre: “LEVONI SPA VIA”– Parola da etichettare: “MATTEOTTI”– Post: “23 COSENZA”

Sappiamo (in qualche modo…) che l’etichetta è<locazione>Da utilizzare come training per un classificatore di etichette

– Risultati attesi dal classificatore:

– If Pre = *via AND Post[0] IS NUMERIC THEN Tag=<locazione>

Risultati

0%

20%

40%

60%

80%

100%

Confidenza

Perc

entu

ali

unclassmisclasscorrect

unclass 23,17 16,54 14,61 10,54

misclass 0,99 4,04 4,68 6,97

correct 75,83 79,41 80,7 82,48

0,95 0,9 0,85 0,8

Riconoscitore Anagrafico

Premessa

Obiettivo: Riconoscimento anagraficoidentificare gruppi di record distinti che fanno riferimento ad uno stesso utente

Idea: Case-Based reasoningClustering di utenti per riconoscere destinatari ugualiClassificazione dei casi futuri confrontandoli con i prototipi dei clusters

Classificazione k-nearest neighbors

I classificatori Nearest Neighbors si basano su learning per analogia

Dato un nuovo oggetto ‘o’, vengono cercati gli oggetti simili ad ‘o’ tra tutti quelli già classificati

In base alla loro classificazione, viene scelta la classe di ‘o’ secondo una politica di voting

k-nearest neighbors per il riconoscimento di sinonimie

while( (obj = ReadNextObject())) { //lettura di un nuovo oggetto objset<Object> neighbors; //oggetti vicini e relative distanze

NearestNeighbors(obj,neighbors,k); //calcolo dei vicini ad obj

if ( ! (IdentityFound(neighbors) ) {obj->new identity; //assegna ad un nuovo cluster

}else

obj->SetIdentity(neighbors); //assegna al cluster di maggioranza}//while

Classificazione Nearest-Neighbor

Triangolazione: Calcolo delle distanze

Definizione delleRegioni di influenza

Indice:Istanze etichettate

+

-

-

--

-

+

+

+

+

-

Istanza da classificarexq

?

Calcolo dei neighbors

NearestNeighbors(obj, neighbors, k):

- Viene interrogato un indice e vengono restituiti i primi k oggetti (neighbors) più simili ad obj

- Il costo di questa operazione è determinante per l’efficienza complessiva della classificazione

- Misure: numero di confronti effettuati, numero di accessi al disco- Studiate (implementate) due strutture ad indice

- Albero metrico- Simile ai B-tree, oggetti raggruppati per similarità

- Hash gerarchico- Una variante (efficiente) degli indici a liste invertite

Albero Metrico: Distanze puntuali

IO Read puntuali

IO Write puntuali

Hash Gerarchico: distanze puntuali

IO Reads puntuali

IO writes puntuali

Conclusioni

Costruzione di un data warehouse estremamente vantaggiosa

– Indipendenza dal front-end– Modello di query generalizzato

basato sulla definizione delle dimensioni

Estensioni con applicazioni di data mining evolute– Analisi di eccezioni– Market-basket analysis

Data mining per la risoluzione dei problemi– Mirato alla generazione del data warehouse

Creazione gerarchieRisoluzione di conflitti