Knowledge Discovery in Databases

Introduction

Knowledge Discovery in Databases

It is a practical application of the methodologies of machine learning (Knowledge Discovery in Databases, KDD) It is of great interest to analyze immense amount of data that is stored in databases in order to obtain any value that it can have The problem is that to do this manually is impossible Some methodologies are needed to automate the process of discovery

We are drowning in information and starving for knowledge

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

1 / 22

Knowledge Discovery in Databases

Introduction

Knowledge Discovery in Databases

The high point of KDD starts in early 2000 Many companies have shown their interest in obtaining the (possibly) valuable information stored in their databases The goal is to obtain information that can lead to better commercial strategies and practices (better knowledge of the consumers preferences and their behaviour) Many companies are putting a lot of eort to this kind of technology (Microsoft, IBM, Daimler-Benz, VISA, consulting companies...) Several buzz words have appeared: Business Intelligence, Business Analytics, Predictive Analytics, Data Science, Big Data, ...

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

2 / 22

Knowledge Discovery in Databases

Introduction

Knowledge Discovery in Databases

Not only business applications are the promoters of this area The necessity to analyze scientic data has supposed an important part of the methodologies developed
Space probes Satellites Astronomical observations Genome Project Bioinformatics

Frequently data grows faster that the ability to analyze

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

3 / 22

Knowledge Discovery in Databases

Introduction

KDD: Origins and inuences

KDD is an area of research that is the intersection of dierent areas: Statistical data analysis: Classical data analysis and modelling methodologies Machine learning and pattern recognition: Methods for machine knowledge discovery and knowledge characterization Databases: Data access eciency Data visualization: Tool to help in the discovery process and interpretation

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

4 / 22

Knowledge Discovery in Databases

Introduction

KDD denitions

It is the search of valuable information in great volumes of data It is the explorations and analysis, by automatic or semiautomatic tools, of great volumes of data in order to discover patterns and rules It is the nontrivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

5 / 22

Knowledge Discovery in Databases

Introduction

Elements of KDD

Pattern: Any representation formalism capable to describe the common characteristics of a group if instances Valid: A pattern is valid if it is able to predict the behaviour of new information with a degree of certainty Novelty: It is novel any knowledge that it is not know respect the domain knowledge and any previous discovered knowledge Useful: New knowledge is useful if it allows to perform actions that yield some benet given a established criteria Understandable: The knowledge discovered must be analyzed by an expert in the domain, in consequence the interpretability of the result is important

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

6 / 22

Knowledge Discovery in Databases

Introduction

Elements of KDD

KDD methodologies have to search in the space of patterns optimizing those characteristics We need a heuristic able to measure them (some are very dicult to assess) The discovery step is the central part of KDD (Data mining) The process needs other additional steps that complete the process of KDD Some general methodologies exists for the process of KDD (CRISP-DM or SEMMA)

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

7 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (I)

Steps of the Knowledge Discovery in DB process

1 2 3 4 5 6 7 8 9

Domain study Creating the dataset Data preprocessing Dimensionality reduction Selection of the discovery goal Selection of the adequate methodologies Data Mining Result assessment and interpretation Using the knowledge

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

8 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (II)

1. Study of the domain Gather information about the domain. Characteristics, goal of the discovering process (attributes, representative examples, types of pattern, sources of data) 2. Creating the dataset From the information of the previous step it is decided what source of data will be used. It has to be decided what attributes will describe the data and what examples are needed for the goals of the discovery process

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

9 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (III)

3. Data preprocessing and cleaning It has to be studied the circumstances that aect the quality of the data
Outliers Noise (exists, presents any pattern, it can be reduced) Missing values Discretization of continuous values

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

10 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (IV) - Discretization

Discretization allows to use methods that only treat qualitative values It can improve the interpretability of the results Automatic methods for discretization:
Direct: Equal size bins, Equal frequency bins Statistical distribution approximation: Histograms, function tting Entropy based

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

11 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (V)

4. Data reduction and projection We have to study what attributes are relevant to our goal (depending on the task some techniques can be used to measure the relevance of the attributes) and the number of examples that are needed. Not all the datamining algorithms are scalable
Instance selection (do we need all the examples? sampling techniques) Attribute selection (what is really relevant?)

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

12 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (VI) - Attribute selection

It is very important to use methods for attribute selection: Reduces the dimensionality, eliminates irrelevant and redundant information, the result of the process is usually better (curse of dimensionality) Attribute selection techniques;
Mathematical/Statistical techniques: Principal component analysis (PCA), projection pursuit, Multidimensional scaling Heuristics functions for attribute relevance (ranking of attributes, search in the space of subsets of attributes)

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

13 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (VII)

5. Selecting the discovery goal The characteristics of the data, the domain and the aim of the project determines what kind of analysis are feasible or possible (group partitioning, summarization, classication, discovery of attribute relations, ...) 6. Selecting the adequate methodologies The goal and the characteristics of the data determines the more adequate methodologies

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

14 / 22

Knowledge Discovery in Databases

The KDD process

The KDD process (VIII)

7. Applying the methodologies The dierent parameters of the chosen methodologies has to be adjusted by experimentation and analysis in order to obtain the best possible results 8. Interpreting the results From the knowledge of the domain (expert) it will be assessed the relevance and importance of the result. This interpretation step could suppose feedback for the previous steps, it is possible that some adjustments are needed or some previous decisions have to be changed 9. Incorporating the new knowledge The new knowledge is used to perform the intended task goal of the discovery process

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

15 / 22

Knowledge Discovery in Databases

The KDD process

Goals of the KDD process

There are dierent goals that can be pursued as the result of the discovery process, among them: Classication: We need models that allow to discriminate instances that belong to a previously known set of groups (the model could or could not be interpretable) Clustering/Partitioning/Segmentation: We need to discover models that clusters the data in groups with common characteristics (a characterizations of the groups is desirable) Regression: We look for models that predicts the behaviour of continuous variables as a function of others

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

16 / 22

Knowledge Discovery in Databases

The KDD process

Goals of the KDD process

Summarization: We look for a compact description that summarizes the characteristics of the data Causal dependence: We need models that reveal the causal dependence among the variables and assess the strength of this dependence Structure dependence: We need models that reveal patterns among the relatinos that describe the structure of the data Change: We need models that discover patterns in data that has temporal or spatial dependence

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

17 / 22

Knowledge Discovery in Databases

Methodologies

Methodologies for KDD

There are a lot of methodologies that can be applied in the discovery process, the more usual are: Decision trees, decision rules:
Usually are interpretable models Can be used for: Classication, regression, and summarization trees: C4.5, CART, QUEST, rules: RIPPER, CN2, ..

Classicators, Regression:
Low interpretability but good accuracy Can be used for: Classication and regression Statistical regression, function approximation, Neural networks, Support Vector Machines, k-NN, Local Weighted Regression, ...

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

18 / 22

Knowledge Discovery in Databases

Methodologies

Methodologies for KDD

Clustering:
Its goal is to partition datasets or discover groups Can be used for: Clustering, summarization Statistical Clustering, Unsupervised Machine learning, Unsupervised Neural networks (Self-Organizing Maps)

Dependency models (attribute dependence, temporal dependence, graph substructures)

Its goal is to obtain models (some interpretables) of the dependence relations (structural, causal temporal) among attributes/instances Can be used for: causal dependence discovery, temporal change, substructure discovery Bayesian networks, association rules, Markov models, graph algorithms, ...

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

19 / 22

Knowledge Discovery in Databases

Applications

Applications
The number of applications are uncountable Bussines: Costumer segmentation, costumer preferences (publicity campaigns, marketing), fraud detection (credit cards), control of industrial processes WWW: User behaviour, on-line recommendation, user proling (WEB mining) Scientic applications: Pharmacology (Drug discovery, screening, in-silicon testing), Astronomy (astronomical bodies identication), Genetics (gen identication, DNA microarrays, bioinformatics), satelite data analysis (meteorology, astronomy, geological, ...) Spying! (Echelon, FBI carnivore, TIA, ...)

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

20 / 22

Knowledge Discovery in Databases

Applications

Tools for KDD

There are a lot of tools available for KDD Some are tools developed in universities (C5.0, CART/MARS, QUEST, ...) that have become a commercial product Big sh eats little sh (C5.0 Clementine SPSS-clementine IBM DBMiner) Data analysis companies incorporate KDD techniques inside classical data analysis tools (SPSS, SAS) Companies selling databases add KDD tools as an added value (IBM DB2 (intelligent Miner), SQL Server, Oracle)

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

21 / 22

Knowledge Discovery in Databases

Applications

Open problems/future goals

Scalability (More data, more attributes) Parallel/Distributed algorithms (Map Reduce) Overtting/Statistical signicance (patterns with low interest) Methods for data cleaning (Missing data and noise) Mining of relational/structured data, temporal data, sequences Pattern comprehensibility Use of domain knowledge Integration with other techniques (OLAP, DataWarehousing, Business Intelligence, Intelligent Decision Support Systems) Bridging the gap Data mining for the masses Privacy

Javier B ejar c b e a (LSI-FIB-UPC)

Machine Learning

2010/2011

22 / 22