Introduction to data mining

The process of knowledge discovery in databases can be shown in the picture below.

The purpose of preprocessing is to transform the raw input data into an appropriate format for subsequent analysis.

The steps involved in data preprocessing include fusing data from multiple sources, cleaning data to remove noise and duplicate observations, and selecting records and features that are relevant to the data mining task at hand.

Such integration requires a postprocessing step to ensure that only valid and useful results are incorporated into the decision support system. An example of postprocessing is visualization, which allows analysts to explore the data and the data mining results from a variety of viewpoints.

Hypothesis testing methods can also be applied during postprocessing to eliminate spurious data mining results.

Challenges for data mining nowadays

Scalability

It is hard to put all the datasets in memory, or it may take such a long time to do data mining, because the dataset may be TB or PB. So we have to use distributed or more efficient ways.

Some data mining algo may use special search strategies to solve exponential search problems. Some data structures are designed. For example, when the datasets cannot be put in memory, we may need out-of-core algos. Sampling and Parallel algo and Distributed algos.

High Dimensionality

When we need a model to find out the time space personality and other dimensionality, it will be more complex.

Heterogeneous and Complex Data

We need to solve more complex data like web & social media and DNA.

Graph connectivity

We need to solve the IM or the hyperlink in a network, which may be a circle.

Parent-child relationships

Such as XML, we need to solve the parent root and the child node.

Data Ownership and Distribution

If the data is stored in different spaces, we need a more efficient way to solve the problem. Then we need distributed data mining techniques.

The usual problems we are facing are:

1. how to reduce the network cost.
2. how to efficiently put the different datasets together?
3. how to solve the safety and privacy problem?

The Origins of Data Mining

Data mining is always part of the KDD (knowledge discovery in databases).

The data mining researchers learned from such methods.

1. statistics
   1. sampling
   2. estimation
   3. hypothesis testing
2. AI & pattern recognition & machine learning
   1. search algos
   2. modeling techniques
   3. learning theories.

Data-Driven Approach

We do not need so much extensive domain knowledge because we can just use a model to help us find the hidden relationship in the data. Just like the neural networks and the deep learning do.

Data mining tasks

Data mining tasks are usually put into 2 sides.

First: Predictive tasks

According to the explanatory variables, we predict the target.

And the predictive tasks can be divided into 2 categories.

1. Classification: discrete target variables, like we predict whether a web user will buy on the network bookshelf, because the value is binary-valued.
2. Regression: continuous target variables, like predicting the price of the stock.

Second: Descriptive tasks:

They are usually exploratory and need postprocessing techniques to check and explain the results.

We may learn these 4 tasks later.

Examples of stream data include:

• Network traffic
• Multimedia streams
• Stock prices

When mining data streams, several issues need to be considered, such as:

• The limited amount of memory available;
• The need for online analysis;
• Changes in the data over time.

Another area of interest is:

• Recommender systems
• Collaborative filtering systems

These systems suggest things that a person might like, such as:

• Movies
• Television shows
• Books
• Products
• And so on

In many cases, this problem, or at least a component of it, is treated as a prediction problem, and therefore data mining techniques can be applied [4, 51].

Data mining Terminologies

• Concepts/Patterns: things that can be discovered or learned from data.
  • E.g. the relation between a patient’s characteristics and the probability of being diabetic.
• Samples/Records/Objects: the individual, independent examples of a concept.
  • E.g. a patient, a candidate drug, etc.
• Attributes/Features: the measurable aspects of a sample.
  • E.g. age, weight, lab tests, microarray data, etc.
• Labels/Ground-truth: the true value of a sample (normally the attribute we are most interested in).
  • E.g. diabetic/non-diabetic, or the probability of being diabetic.
• Predictions/Model outputs: the value predicted by the model.
  • E.g. diabetic/non-diabetic, or the probability of being diabetic.

Classification

Given a collection of records (the training set), where each record contains a set of attributes and one of them is the class:

• Find a model for the class attribute as a function of the values of the other attributes.
• Goal: previously unseen records should be assigned a class as accurately as possible.
• A test set is used to determine the accuracy of the model. Usually the given dataset is divided into training and test sets: the training set is used to build the model and the test set is used to evaluate it.
• Sometimes we need another validation set to tune the model’s hyper-parameters.

Regression

Predict the value of a given continuous variable based on the values of other variables, assuming a linear or nonlinear model of dependency.

• Similar to the classification task, except for the prediction target:
  • Classification: categorical values / classes.
  • Regression: continuous real values.
• Greatly studied in the statistics and neural network fields.

Classification VS Regression

Both are supervised: they need ground truth to train a model. The difference is the type of the target.

Classification predicts a categorical target, so the ground truth is a class label.

Regression is the same idea, but the ground truth is a number, so we use that numeric ground truth to train the model.

(There are some examples on the slides that I can review later.)

Association Rule Discovery: Definition

Given a set of records, each of which contains some number of items from a given collection, produce dependency rules that predict the occurrence of an item based on the occurrences of other items.

Sequential Pattern Discovery: Definition

• Given a set of objects, each associated with its own timeline of events, find rules that predict strong sequential dependencies among different events.
• Rules are formed by first discovering patterns. Event occurrences in the patterns are governed by timing constraints.

Clustering Definition

Given a set of data points, each having a set of attributes, and a similarity measure among them, find clusters such that:

• Data points in one cluster are more similar to one another.
• Data points in separate clusters are less similar to one another.

Similarity measures:

• Euclidean distance if the attributes are continuous.
• Other problem-specific measures.

Questions

• How do we judge the standard when there is no ground truth?
• How do we quantify a similarity measure?

Classification VS Clustering

Classification is supervised: we already have labelled classes and train a model to assign new records to them. Clustering is unsupervised: there are no predefined labels, so we group data points purely by their similarity.