Testo italiano
MODELLI STATISTICI DI CLASSIFICAZIONE E DI SEGMENTAZIONE PER L'ANALISI DI DATI STRUTTURATI IN FORMA COMPLESSA: METODOLOGIE, SOFTWARE E APPLICAZIONITesto inglese
STATISTICAL MODELS FOR CLASSIFICATION AND SEGMENTATION OF COMPLEX DATA STRUCTURES: METHODOLOGIES, SOFTWARE AND APPLICATIONS
SICILIANO | ROBERTA | |
---|---|---|
(cognome) | (nome) | |
Università degli Studi di NAPOLI "Federico II" | Facoltà di ECONOMIA | |
(università) | (facoltà) | |
S01A | Dipartimento di MATEMATICO-STATISTICO | |
(settore scient.discipl.) | (Dipartimento/Istituto) |
r.sic@dmsna.dms.unina.it |
---|
(E-mail) |
MALERBA | DONATO | |
---|---|---|
(cognome) | (nome) |
Professore associato | 13/11/1964 | MLRDNT64S13F376W |
---|---|---|
(qualifica) | (data di nascita) | (codice di identificazione personale) |
Università degli Studi di BARI | Facoltà di SCIENZE MATEMATICHE FISICHE e NATURALI |
---|---|
(università) | (facoltà) |
K05A | Dipartimento di INFORMATICA |
(settore scient.discipl.) | (Dipartimento/Istituto) |
080/5443269 | 080/5443196 | malerba @ di.uniba.it |
---|---|---|
(prefisso e telefono) | (numero fax) | (E-mail) |
S01A | K05A |
Testo italiano
CLASSIFICAZIONE AD ALBERO ; REGRESSIONE AD ALBERO ; ALGORITMI DI PARTECIPAZIONE ; PRUNING ; DATI LONGITUDINALI ; DATI TEMPORALI ; TECNICHE DI CONSENSO ; OGGETTI SIMBOLICI
Testo inglese
CLASSIFICATION TREE ; REGRESSION TREE ; PARTICIPATION ALGORITHMS ; PRUNING ; LONGITUDINAL DATA ; TEMPORAL DATA ; CONSENSUS TECHNIQUES ; SYMBOLIC OBJECTS
Testo italiano
Donato Malerba è professore associato dell'Università di Bari, Dipartimento di Informatica, dove insegna nei corsi di "Basi di Dati Attive" e "Programmazione II". Nel 1992 è stato assistant specialist presso lo Institute of Computer Science, dell'Università della California, Irvine. La sua attività scientifica ha riguardato principalmente l'apprendimento automatico, in modo particolare l'integrazione di metodi sia simbolici (concettuali) sia numerici (statistici) per l'inferenza induttiva, la definizione di una funzione di matching flessibile per la classificazione in ambienti rumorosi, l'induzione di alberi di classificazione e di regressione, la costruzione di modelli causali probabilistici. Gli studi condotti hanno trovato applicazione al data mining (progetto ESPRIT 20821 "SODAS") e Web mining, all'elaborazione intelligente di documenti (progetti ESPRIT 5203 "INTREPID", 29159 "CONCERTO"), e all'interpretazione automatica di carte topografiche. Ha fatto parte del comitato di programma della Conferenza Internazionale di Apprendimento Automatico (ICML'96, ICML'99), e di altri workshop sull'apprendimento automatico e data mining.Testo inglese
Donato Malerba is an associate professor at the University of Bari in the Department of Informatics, where he teaches in the courses of "Active Data Bases" and "Computer Programming II". In 1992 he was assistant specialist at the Institute of Computer Science, University of California, Irvine. His research activity mainly concerns machine learning, in particular the integration of symbolic (conceptual) and numeric (statistical) methods for inductive inference, the definition of a flexible matching function for classification in noisy environments, the induction of classification and regression trees, and the construction of probabilistic causal models. His studies have been applied to data mining (ESPRIT project 20821 "SODAS") and Web mining, to intelligent document processing (ESPRIT projects 5203 "INTREPID", 29159 "CONCERTO"), and to topographic map interpretation. He has served in the program committee of the International Conference on Machine Learning (ICML'96, ICML'99), and other workshops on machine learning and data mining.
Nº | Cognome | Nome | Dipart./Istituto | Qualifica | Settore scient. |
Mesi uomo |
|
---|---|---|---|---|---|---|---|
1999 | 2000 | ||||||
1 | MALERBA | DONATO | INFORMATICA | Prof. associato | K05A | 2 | 6 |
2 | ALTAMURA | ORONZO | INFORMATICA | Ricercatore | K01X | 6 | 6 |
3 | ESPOSITO | FLORIANA | INFORMATICA | Prof. ordinario | K05A | 2 | 6 |
4 | LANZA | ANTONIETTA | INFORMATICA | Ricercatore | K05B | 2 | 6 |
1.10.2 Personale universitario di altre Università
Nº | Cognome | Nome | Università | Dipart./Istituto | Qualifica | Settore scient. |
Mesi uomo |
|
---|---|---|---|---|---|---|---|---|
1999 | 2000 | |||||||
1.10.3 Titolari di assegni di ricerca
Nº | Cognome | Nome | Dipart./Istituto | Anno del titolo | Mesi uomo |
---|
Nº | Cognome | Nome | Dipart./Istituto | Anno del titolo | Mesi uomo |
---|
Nº | Qualifica | Costo previsto | Mesi uomo |
---|---|---|---|
1. | Ricercatore | 18 | 6 |
Nº | Cognome | Nome | Dipart./Istituto | Qualifica | Mesi uomo |
---|---|---|---|---|---|
1. | LISI | FRANCESCA ALESSANDRA | Information Systems Institute - Technische Universitaet Wien - Vienna - Austria | Assistant specialist | 11 |
2. | TAMMA | VALENTINA | Computer Science Dept. - Univ. of Liverpool (UK) | Phd Student (2nd year) | 11 |
Testo italiano
Metodi di semplificazione per alberi di classificazione e di regressioneTesto inglese
Simplification methods for classification and regression trees
Testo italiano
Molti sforzi di ricerca sono stati dedicati alla definizione di modelli di classificazione privi delle classiche assunzioni restrittive. I modelli strutturati ad albero forniscono un'alternativa ai modelli lineari per la classificazione e regressione su dati. Essi sono intrinsecamente più flessibili, possono facilmente gestire complicate interazioni tra fattori anche numerosi, e fornire risultati di facile interpretazione. I modelli strutturati ad albero sono caratterizzati dal tipo della variabile dipendente (o risposta), che è di tipo categorico nel caso degli alberi di classificazione, e di tipo numerico continuo nel caso di alberi di regressione. Sono state proposte varie strategie per la costruzione di modelli strutturati ad albero, tra queste la più nota è la top-down [11]. Secondo questa strategia, la costruzione di un modello strutturato ad albero può essere ottenuta risolvendo tre problemi fondamentali [1]: 1) associare un modello ad una foglia 2) selezionare la miglior partizione di dati per un nodo interno e 3) decidere quando terminare il partizionamento ricorsivo.
Storicamente il terzo problema è stato ritenuto cruciale per la costruzione di alberi di classificazione accurati. Il problema può essere affrontato in due modi: decidere prospetticamente quando terminare la costruzione dell'albero, oppure ridurre retrospettivamente la grandezza di un albero completamente espanso operando una potatura dei rami. Il secondo approccio, noto come potatura o semplificazione di alberi, è di solito preferito al primo in quanto non è affetto dalla miopia tipica delle cosiddette strategie golose adottate nella costruzione top-down di modelli ad albero.
In letteratura si trovano numerosi metodi di potatura, dai quali possono derivare molte varianti. La maggior parte dei metodi di semplificazione è stata proposta per alberi di classificazione e solo alcune tecniche di potatura sono state ideate per alberi di regressione. Questi metodi ottimizzano differenti funzioni di valutazione e applicano diverse strategie di ricerca ed operatori di semplificazione. Queste differenze determinano un metodo più adatto di altri per un particolare insieme di dati.
L'unità di Bari intende sviluppare specifiche tecniche di semplificazione per alberi di regressione, come pure un metodo per la selezione automatica, basata sulle caratteristiche dei dati in esame, di un algoritmo di potatura adatto. La suddetta unità ha già maturato una precedente esperienza estendendo con diversi algoritmi di potatura il noto sistema di induzione di alberi di classificazione C4.5 [10]; un confronto empirico, basato sulla procedura di ricampionamento senza ripetizioni, ha già evidenziato alcune caratteristiche dei metodi [2,3,4,5,9]. La suddetta unità, inoltre, ha sviluppato un sistema innovativo che costruisce alberi di regressione utilizzando, come criterio di selezione del migliore partizionamento, il coefficiente di correlazione di Fisher eta-quadro, e come criterio di terminazione, un test di ipotesi sul rapporto (varianza tra i gruppi)/(varianza nei gruppi) [6,7,8]. Il sistema, che è stato progettato secondo i criteri di modularità (coesione, information hiding e interfacciamento esplicito), può essere facilmente esteso allo scopo di incorporare quei metodi di semplificazione che verranno proposti per gli alberi di regressione.
Partecipando a questo progetto intendiamo sviluppare uno strumento di data mining che guidi l'utente sia nella costruzione di alberi di classificazione e regressione, sia nella selezione di un metodo di potatura idoneo.Testo inglese
Many research efforts have been dedicated towards devising classification and regression models free from some of the restrictive classical assumptions. Tree-based models provide an alternative to linear models for classification and regression data. They are inherently more flexible, can easily handle complicated interactions among factors and large number of factors, and give results that are simple to interpret. Tree-based models are characterized by the level measurement of the dependent (or response) variable, which is categorical in the case of classification trees and continuous in the case of regression trees. Various strategies have been proposed for the construction of tree-based models, among which the most widely known is the top-down strategy [11]. According to this strategy, the construction of a tree-based model can be performed by solving three key problems [1]: 1) associating a model to a leaf; 2) selecting the best data partitioning at an internal node, and 3) deciding when the recursive partitioning should be stopped.
Historically, the third problem is deemed critical for the construction of good decision trees. There are two different ways to cope with it: Either prospectively deciding when to stop the growth of a tree or retrospectively reducing the size of a fully expanded tree by pruning some branches. The second approach, known as tree pruning or tree simplification, is generally preferred to the first approach, since it does not suffer from the short-sightedness problems typical of the greedy strategies adopted in top-down construction of tree models.
Many pruning methods have been proposed in the literature and several variants can be derived from them. Most of simplification methods have been proposed for classification trees and only some pruning techniques have been devised for regression trees. These methods optimize different evaluation functions and apply different search strategies and simplification operators. These differences make a method more suitable then others given a particular data set.
The Unit of Bari intends to develop specific simplification techniques for regression trees, as well as a method for the automated selection of a suitable pruning algorithm based on the characteristics of the data set under study. We already experienced the extension of the well-known classification tree induction system C4.5 [10] with several pruning methods; an empirical comparison based on the holdout resampling procedure has already pointed out some characteristics of the methods [2,3,4,5,9]. We have also developed a novel system that builds regression trees by computing Fisher's correlation coefficient eta-square as criterion for split selection, and by performing a hypothesis test on the ratio (variance between the groups)/(variance within the groups) as stopping criterion [6,7,8]. The system, which has been designed by respecting modularity criteria (cohesion, information hiding, explicit interfacing), can be easily extended in order to embed those simplification methods that will be devised for regression trees.
By participating to this Project we intend to develop a data mining tool that guide the users both in the construction of classification and regression trees and in the selection of a suitable pruning method.
1. Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and regression trees, Belmont, CA: Wadsworth International.
2. F. Esposito, D. Malerba, & G. Semeraro (1993). Decision Tree Pruning as a Search in the State Space. In P.B. Bradzil (Ed.), Machine Learning: ECML-93, Lectures Notes in Artificial Intelligence, 667, 165-184, Springer-Verlag, Berlin, Germany.
3. F. Esposito, D. Malerba, & G. Semeraro (1995). Simplifying Decision Trees by Pruning and Grafting: New Results. (Extended Abstract). In N. Lavrac e S. Wrobel (Eds.), Machine Learning: ECML-95, Lectures Notes in Artificial Intelligence, 912, 287-290, Springer, Berlin, Germany.
4. F. Esposito, D. Malerba, & G. Semeraro (1997). A Comparative Analysis of Methods for Pruning Decision Trees. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19, 5, 476-491.
5. F. Esposito, D. Malerba, & G. Semeraro (1997). The Effects of Pruning Methods on Predictive Accuracy of Induced Decision Trees: A New Experimentation with Cross-Validation. Proceedings VIII International Symposium on Applied Stochastic Models and Data Analysis, 129-134, Rocco Curto Editore, Naples.
6. F. Esposito, D. Malerba, & V. Tamma (1998). Efficient Data-Driven Construction of Model-Trees. Proceedings of the Int. Seminar on New Techniques & Technologies for Statistics NTTS'98, 163-168.
7. A. Fino, D. Malerba, & V. Tamma (1997). Induction of Tree-Based Regression Models, Proc. of Joint Workshop of the AI*IA Groups on Natural Language Processing and Machine Learning, Turin.
8. A. Lanubile, & D. Malerba (1997). Induction of Regression Trees with RegTree, Atti della Riunione Scientifica del Gruppo di Classificazione IFCS, 253-256, Pescara, Italy.
9. D. Malerba, F. Esposito, & G. Semeraro (1996). A Further Comparison of Simplification Methods for Decision-Tree Induction. Chapter 35 in D. Fisher e H.-J. Lenz (Eds.), Learning from Data: Artificial Intelligence and Statistics V, Lecture Notes in Statistics, 112, 365-374, Springer, Berlino, Germania.
10. Quinlan, J.R. (1993). C4.5: Programs for machine learning.San Mateo, CA: Morgan Kaufmann.
11. S.R. Safavian, & D. Landgrebe (1991). A survey of decision tree classifier methodology, IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, no. 3, pp. 660-674.
Testo italiano
L'unità di ricerca dell'Università di Bari intende partecipare al progetto approfondendo gli aspetti metodologici alla base dello sviluppo di strumenti di data mining che siano efficaci e di facile uso. In particolare, la ricerca mira ad estendere sistemi di induzione di alberi di regressione e classificazione sia con metodi di potatura proposti in letteratura, sia con tecniche di semplificazione innovative definite per questo Progetto. Un Dimostratore sarà prodotto alla fine del Progetto. Il Dimostratore permetterà di indurre tanto alberi di classificazione quanto alberi di regressione per mezzo della stessa interfaccia, ed assisterà l'utente nel definire gli appositi parametri del sistema che influenzano il processo di apprendimento. In particolare, il Dimostratore suggerirà l'eventuale metodo di potatura che restituisce l'albero più accurato e/o più semplice. La scelta del metodo migliore sarà effettuata sulla base sia delle caratteristiche del metodo di potatura, sia dei risultati sperimentali raccolti durante il Progetto.
I problemi di ricerca da considerare nello sviluppo del Dimostratore sono:
· Il framework da utilizzare per classificare i vari metodi di semplificazione proposti in letteratura.
· I fondamenti teorici dei metodi di potatura e la loro correttezza.
· L'estensione agli alberi di regressione delle tecniche di potatura proposte per alberi di classificazione.
· L'individuazione di una eventuale interazione tra criterio di partizionamento e strategia di potatura.
· La valutazione dei modelli strutturati ad albero in base alla loro accuratezza predittiva, utilità, efficienza e comprensibilità.
· La descrizione degli insiemi di dati e l'individuazione delle caratteristiche realmente legate alla strategia di semplificazione.
· Dato un criterio di ottimizzazione (dimensione dell'albero, accuratezza dell'albero, ecc.), l'associazione delle caratteristiche di un campione di dati alle caratteristiche di un metodo di semplificazione.
L'unità dell'Università di Bari intende contribuire al Progetto studiando, in particolare, l'induzione di alberi di classificazione e regressione con i seguenti obiettivi:
i) Definire nuovi metodi di potatura per modelli di regressione strutturati ad albero.
ii) Analizzare similarità e differenze di metodi di potatura sulla base di framework unificanti.
iii) Definire operatori di semplificazione per modelli di regressione strutturati ad albero.
iv) Definire il concetto di albero potato in modo ottimale rispetto ad un insieme di operatori di semplificazione.
v) Caratterizzare empiricamente i metodi di classificazione e i loro effetti sia sull'accuratezza predittiva, sia sulla dimensione degli alberi costruiti.
COMPITI DI RICERCA
Nel COMPITO 1, l'attività di questa Unità si concentrerà principalmente sulla raccolta, analisi, estensione e implementazione di metodi di semplificazione per alberi di classificazione e di regressione. Per ogni metodo, si studieranno sia la complessità computazionale, sia i fondamenti teorici.
Nel COMPITO 2, l'unità esaminerà le loro proprietà empiriche su diversi insiemi di dati artificiali e reali, mirando alla derivazione automatica di regole per guidare la selezione del metodo di semplificazione. Tali regole saranno integrate in uno strumento di data mining che assisterà l'utente nel compito di costruire dai dati i modelli strutturati ad albero.Testo inglese
The research unit of the University of Bari intends to participate in the Project by investigating the methodological aspects useful for developing effective, user-friendly data mining tools. In particular, the research aims at extending classification and regression tree induction systems with both pruning methods proposed in the literature and novel simplification techniques defined for this Project.
A Demonstrator will be produced at the end of the Project. It will be able to induce both classification and regression trees by means of the same interface, and it will assist the user in setting the appropriate system parameters that affect the learning process. In particular, the Demonstrator will recommend the possible application of the pruning method that leads to the most accurate and/or simplest tree. The choice of the best method will be made basing upon both the characteristics of the pruning methods and the experimental results collected in the Project.
The Research Issues to be considered in developing the Demonstrator are:
· Which framework can be used for categorizing the various simplification methods proposed in the literature.
· Which are the theoretical foundations of the pruning methods and in which respect they can be considered sound.
· How pruning techniques proposed for classification trees can be extended to regression trees.
· Whether an interaction exists between partitioning criteria and pruning strategy.
· How tree models have to be evaluated, by considering their predictive accuracy, as well as utility, efficiency and understandability.
· How data sets can be described and which features are actually related to the simplification strategy.
· Given an optimization criterion (tree size, tree accuracy, ecc.), how to match the characteristics of a data set with the characteristics of the simplification methods.
We plan to contribute to the Project by studying, in particular, the induction of classification and regression trees with the following Goals:
i) Defining new pruning methods for tree-based regression models.
ii) Analyzing similarities and differences of pruning methods basing upon a unifying framework.
iii) Defining simplification operators for tree-based regression models.
iv) Defining the concept of optimally pruned tree with respect to a set of simplification operators.
v) Empirically characterizing simplification methods and their effect on both the predictive accuracy and the size of the constructed trees.
RESEARCH TASKS
In TASK 1, the activity of this Unit will be mainly focused on collecting, analyzing, extending and implementing simplification methods for both tree-based classification and regression models. For each method, we will investigate both its computational complexity and its theoretical foundations.
In TASK 2, we will investigate empirical properties of the methods on a number of laboratory-sized and real data sets, aiming at the automatic derivation of rules to be used while assisting the user in the selection of a simplification method. Such rules will be integrated into a data mining tool that assists users in the task of building tree-based models from data.
Nº | Anno di acquisizione | Descrizione | |
---|---|---|---|
Testo italiano | Testo inglese | ||
1. | 1997 | SUN - Ultrasparc2 (2) | SUN -Ultrasparc2 (2) |
2. | 1997 | SUN - Ultrasparc1 (8) | SUN - Ultrasparc1 (8) |
3. | |||
4. | |||
5. |
Attrezzatura I
Descrizione
valore presunto (milioni) percentuale di utilizzo per il programma
Attrezzatura II
Descrizione
valore presunto (milioni) percentuale di utilizzo per il programma
Voce di spesa | Spesa | Descrizione | ||
---|---|---|---|---|
M£ | Euro | Testo italiano | Testo inglese | |
Materiale inventariabile | 4 | 2.066 | Acquisto di libri e riviste inerenti il progetto. Acquisto di software specializzato (CART, Developer Studio 6.0) | Purchase of books and journals concerning the Project. Purchase of specific software products (CART, Developer Studio 6.0) |
Grandi Attrezzature | ||||
Materiale di consumo e funzionamento | 3 | 1.549 | Acquisto di carta, dischetti, nastri per il funzionamento. Manutenzione macchine. Fotocopie. | Purchase of paper, diskettes, tape for the functioning. Machine maintenance. Photocopies. |
Spese per calcolo ed elaborazione dati | ||||
Personale a contratto | 18 | 9.296 | Sviluppo di un prototipo di sistema di data mining. | Development of prototypical data mining system. |
Servizi esterni | ||||
Missioni | 20 | 10.329 | Spesa prevista su 5 partecipanti, una media di 4 milioni su 2 anni per partecipare a eventi e incontri. | Expected cost for partecipation to meetings and events: 4 millions lire for 5 participants in two years. |
Altro |
M£ | Euro | |
---|---|---|
Costo complessivo del Programma dell'Unità di Ricerca | 45 | 23.241 |
Costo minimo per garantire la possibilità di verifica dei risultati | 35 | 18.076 |
Fondi disponibili (RD) | 14 | 7.230 |
Fondi acquisibili (RA) | 0 | |
Cofinanziamento richiesto al MURST | 31 | 16.010 |
QUADRO RD
Provenienza | Anno | Importo disponibile | nome Resp. Naz. | Note | |
---|---|---|---|---|---|
M£ | Euro | ||||
Università | 1998 | 14 | 7.230 | Esposito | |
Dipartimento | |||||
MURST (ex 40%) | |||||
CNR | |||||
Unione Europea | |||||
Altro | |||||
TOTAL | 14 | 7.230 |
4.1.1 Altro
QUADRO RA
Provenienza | Anno della domanda o stipula del contratto | Stato di approvazione | Quota disponibile per il programma | Note | |
---|---|---|---|---|---|
M£ | Euro | ||||
Università | |||||
Dipartimento | |||||
CNR | |||||
Unione Europea | |||||
Altro | |||||
TOTAL | 0 |
4.2.1 Altro
Firma ____________________________________________ |
---|
Firma ____________________________________________ | 30/03/1999 13:53:52 |
---|