Testo italiano

MODELLI STATISTICI DI CLASSIFICAZIONE E DI SEGMENTAZIONE PER L'ANALISI DI DATI STRUTTURATI IN FORMA COMPLESSA: METODOLOGIE, SOFTWARE E APPLICAZIONI

Testo 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.

1. ESPOSITO F., MALERBA D., TAMMA V., "Efficient data-driven construction of model-trees" , Rivista: Proc. of NTTS'98, Int. Seminar on New Techniques & Technologies for Statistics , pp.: 163-168 , (1998) .
2. ESPOSITO F., MALERBA D., SEMERARO G., "A Comparative Analysis of Methods for Pruning Decision Trees" , Rivista: IEEE Transactions on Pattern Analysis and Machine Intelligence , Volume: PAMI-19 , pp.: 476-491 , (1997) .
3. ESPOSITO F., MALERBA D., SEMERARO G., "The effects of pruning methods on Predictive Accuracy of Induced Decision Trees: A New Experimentation with Cross-Validation" , Rivista: Proc. VIII Int. Symposium on Applied Stochastic Models and Data Analysis , pp.: 129-134 , (1997) .
4. ESPOSITO F., MALERBA D., RIPA V., SEMERARO G., "Discovering Causal Rules in Relational Databases" , Rivista: Applied Artificial Intellingence: An International Journal , Volume: 11 , pp.: 71-83 , (1997) Received the best paper award as paper presented at the Symposium on "Knowledge Discovery in Databases" - 13th European Meeting on Cybernetics and Systems Research. .
5. MALERBA D., ESPOSITO F., SEMERARO G., "A Further Comparison of Simplification Methods for Decision-Tree Induction." , Rivista: In D. Fisher & H.-J. Lenz (Eds.), Learning from Data,Lecture Notes in Statistics , Volume: 112 , pp.: 365-374 , (1996) Chapter 35 .

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

1.10.4 Titolari di borse per Dottorati di Ricerca e ex L. 398/89 art.4 (post-dottorato e specializzazione)

Nº	Cognome	Nome	Dipart./Istituto	Anno del titolo	Mesi uomo

1.10.5 Personale a contratto da destinare a questo specifico programma

Nº	Qualifica	Costo previsto	Mesi uomo
1.	Ricercatore	18	6

1.10.6 Personale extrauniversitario dipendente da altri Enti

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 regressione

Testo 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

QUADRO RD

4.1.1 Altro

QUADRO RA

4.2.1 Altro

Firma ____________________________________________

(per la copia da depositare presso l'Ateneo e per l'assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati; legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")

Firma ____________________________________________	30/03/1999 13:53:52