ISSUES OF DATA MINING:

1.3 DATA MINING ISSUES

There are several important challenges in implementing data mining.

1. Human Interaction

• Data mining problems are often not clearly defined.

• Both technical experts (to write queries and interpret results) and
domain experts/users (to provide training data and expected results) are needed.

2. Overfitting

• A model should work not only for the training data but also for future
data.
• Overfitting happens when the model fits the training data too closely
but fails on new data.

• Example: If a small employee database is used, the model might

wrongly classify “short” people as under 5’8” just because of limited data.

3. Outliers

• Some data entries don’t fit well into the model.

• If included, these outliers can make the model behave poorly for
normal data.

• This problem is bigger with very large databases.

4. Interpretation of Results

• The output of data mining can be complex.

• Often, only experts can correctly understand the results.

5. Visualization of Results

• Graphs and visual tools make the results easier to understand.

6. Large Datasets

• Data mining usually involves massive amounts of data.

• Specialized tools are needed to handle this scalability problem.

7. High Dimensionality

• Databases may have too many attributes (features).

• Not all attributes are useful; some may reduce efficiency or give wrong
results.

• This problem is called the curse of dimensionality.

• A solution is dimensionality reduction—removing unnecessary

attributes.

8. Multimedia Data
• Traditional algorithms mainly handle numbers, text, etc.

• Multimedia data (images, video, GIS data) makes mining more

complex and breaks many existing algorithms.

9. Missing Data

• In preprocessing, missing data is sometimes replaced with estimates.

• Wrong handling of missing values can give invalid results.

10. Irrelevant Data

• Some attributes may not matter for the mining task.

11. Noisy Data

• Some data values may be incorrect.

• These need correction before analysis.

12. Changing Data

 • Databases often change, but most mining algorithms assume static
data.

• This means the algorithm must be rerun every time the database
updates.

13. Integration

• Data mining is often treated as a special task, separate from normal

database operations.
• Integrating data mining into regular DBMS systems is a desirable goal.

14. Application

• The biggest challenge is not running the algorithms, but using the
results effectively.

• Businesses may need to change their practices to apply the new

knowledge.

BUSINESS INTELLIGENCE APPLICATIONS

Business Intelligence (BI) tools support decision-making by offering up-to-date

metrics and insights. Regardless of industry, managers use BI to optimize
processes, understand customers, reduce costs, and boost performance. Below are
key areas where BI and data mining are widely applied:

1. Customer Relationship Management (CRM)

• Marketing Optimization: Analyzing customer feedback improves
message targeting.

• Customer Retention (Churn Analysis): Predicts which customers are

likely to leave, allowing preemptive actions like personalized offers.

• Customer Value Maximization: Encourages cross-selling and up-selling

by analyzing needs and past behaviors.
• High-Value Customer Engagement: Identifies and delights loyal
customers through segmented marketing and loyalty programs.
 • Brand Image Management: Monitors social media sentiment to
manage public perception in real time.

2. Healthcare and Wellness

• Disease Diagnosis: Tools like IBM Watson analyze patient and

historical data for accurate diagnoses.

• Treatment Optimization: BI recommends effective treatments based on

medical history and drug interactions.
• Wellness Tracking: Continuously monitors patient data to prevent
illness.

• Fraud Detection: Identifies overbilling or unnecessary procedures.

• Public Health Management: Forecasts outbreaks using search and

trend data (e.g., Google flu predictions).

3. Education

• Student Recruitment and Retention: Models predict the likelihood of

enrollment and dropout risks.

• Course Planning: Uses past enrolment data to suggest popular future

courses.

• Fundraising: Predicts which alumni are most likely to donate,

optimizing outreach efforts.

4. Retail

• Inventory Optimization: Predicts product demand across locations to

reduce costs and stock-outs.

• Store Layout & Promotions: Market basket analysis helps in product

placement and bundle creation.

• Seasonal Logistics: Tracks regional weather or demand to reposition

seasonal goods.

• Perishable Goods Management: Uses trend data to discount and sell

near-expiry items.

5. Banking
 • Loan Automation: Uses data-driven models to assess credit risk and
streamline approval.

• Fraud Detection: Detects unusual transactions for intervention.

• Customer Value Growth: Offers personalized banking products to
existing customers.

• Liquidity Forecasting: Predicts withdrawal patterns to balance cash

reserves and investments.

6. Financial Services

• Stock/Bond Price Prediction: Models forecast market movements for

better trading strategies.

• Event Impact Analysis: Assesses how geopolitical or economic events

affect financial markets.
• Fraud Prevention: Detects insider trading or irregular market behavior
using anomaly detection.

7. Insurance

• Claim Forecasting: Predicts disaster-related losses for better resource

planning.

• Rate Optimization: Sets competitive yet profitable pricing using risk

models.
• Targeted Marketing: Uses micro-segmentation to attract the most
profitable customers.
• Fraud Detection: Flags suspicious claims using predictive models.

8. Manufacturing

• Product Quality Enhancement: Identifies defect patterns for root cause

analysis and quality improvement.

• Machinery Failure Prediction: Schedules preventive maintenance

based on performance data to avoid breakdowns.

9. Telecom
 • Churn Management: Predicts customer switch likelihood to tailor
retention strategies.

• Customer Profiling: Analyzes call records (CDRs) to build behavior-

based marketing bundles.

• Network Management: Predicts equipment failure for timely

maintenance.

• Fraud Detection: Identifies suspicious subscription or usage behavior in

real-time.

10. Public Sector

• Law Enforcement: Predictive policing based on crime history (e.g.,

LAPD reduced property crimes with BI).

• Scientific Research: Pattern discovery in large datasets across

disciplines like microbiology and nuclear physics.

• National Health: Tracks disease spread using real-time search trends

and health data.

DECISION TREES

A decision tree is a predictive modeling technique used for classification, clustering,

and prediction tasks.

It uses a divide-and-conquer strategy, breaking a large problem into smaller subsets

until a solution is found.

The method is similar to the children’s game “Twenty Questions”. In the game, each
question helps narrow down the possible answers. Similarly, in a decision tree:

• The root node is the first question.

• Each internal node represents further questions.

• Leaf nodes represent the final predictions (the correct guess).

Like a binary search, good questions divide the search space into roughly equal
parts. Poorly chosen questions (e.g., asking “Is it my mother?” right at the start) fail
because they don’t split the space effectively.

Example 3.6:” The Game of “Twenty Questions”

Buma tries to guess an object Sahana has in mind by asking up to 20 questions.

1. First question: “Is it alive?”

• If “no” → go down the “not alive” branch.

• If “yes” → ask another question.

2. If alive: “Is it a person?”

3. If yes: “Is it a friend?” → If no, then “Is it someone in my family?”

4. From here, Buma can quickly narrow down the search.

This process (shown in Figure 3.4) is exactly how decision trees split the problem
into smaller, manageable parts.

Definition 3.3: Decision Tree

• A decision tree (DT) is a tree where:

• The root and each internal node is labeled with a question.

• Arcs (branches) represent possible answers.

• Leaf nodes give the prediction (final solution).

Definition 3.4: Decision Tree Model

A decision tree model consists of three components:

1. The decision tree itself.

2. An algorithm to build the tree.

3. An algorithm to apply the tree to data and solve the problem.

The tree can be built in two ways:

• By using a training dataset.

• Or by a domain expert.

Different decision tree techniques vary mainly in how the tree is created.

Applying a Decision Tree (Algorithm 3.2)

To use a decision tree for prediction:

1. Start at the root node.

2. For a given tuple (record), answer the question at that node.

3. Follow the correct branch to the next node.

4. Repeat until a leaf node is reached.

5. The label at the leaf node is the prediction.

The complexity of this process depends on:

• The number of levels in the tree.

• The branching factor (how many branches each node can have).

Example 3.7: Student Classification

Suppose we want to classify university students as short, medium, or tall.

• Database schema includes: name, address, gender, height, age, year,

major.

• For classification, we focus on gender, age, and height.

Observations:

• A female of 1.95m is considered tall, but a male of the same height

may not be.
 • A 10-year-old child at 1.5m may be considered tall for that age, but
since university students are mostly over 17, such children are treated as outliers
and classified separately.

So, the tree uses only gender and height for classification.

• Example:

• If female and height < 1.3m → Short.

• If height between 1.3m and 1.8m → Medium.

• If height > 1.8m → Tall.

The tree is built using a training sample with known classifications. A sample output
tree is shown in Figure 3.5.

Decision Trees (Simplified with One Example)

A decision tree is a method used for classification, prediction, and clustering tasks.

It works like a series of yes/no questions, breaking down a big problem into smaller
parts until a final answer is reached.

Think of it like a game of asking questions: each question helps you eliminate
possibilities until you find the correct choice.

SIMPLE EXAMPLE

Example: Deciding Breakfast

Suppose you are deciding what to eat for breakfast.

1. First question (root node): Do I want something sweet?

• If yes → ask the next question: Do I want something light?

• If yes → Fruit.

• If no → Pancakes.
• If no → ask another question: Do I want something quick?
 • If yes → Toast.

• If no → Omelette.

Here:

• Root node = “Do I want something sweet?”

• Internal nodes = more questions like “Do I want something light?”

• Leaf nodes = final predictions: fruit, pancakes, toast, or omelette.

Formal Definitions (with the example in mind)

• Definition 1 (Decision Tree):

A tree where each internal node is a question (e.g., “Do I want something sweet?”).

Each branch is a possible answer (yes or no).

Each leaf node is the final choice (fruit, pancakes, toast, omelette).

• Definition 2 (Decision Tree Model):

A complete decision tree system includes:

1. The tree (questions and answers).

2. An algorithm to build the tree (e.g., looking at past breakfast choices).

3. An algorithm to use the tree for prediction (walking through the

questions to reach a decision).

How It Works (Algorithm in Simple Steps)

To use the tree:

1. Start at the root question.

2. Answer it based on the current situation.

3. Follow the branch to the next question.

4. Repeat until you reach a leaf.

5. The leaf is your final prediction/decision.

For example:

• Today you want something sweet → follow “yes.”

• Then you want something light → follow “yes.”

• Result = Fruit.

K NEAREST NEIGHBOUR

The K Nearest Neighbors (KNN) algorithm is a distance-based classification method.

It works on the principle that items close to each other in the feature space are likely
to belong to the same class.

The key assumption is that the training set contains both the data points and their
known class labels. This means that the training data itself acts as the model—no
separate model-building step is required.

When a new item needs to be classified, the algorithm follows these steps:

1. Compute the distance of the new item from every item in the training
set.

2. Select the K closest items (neighbors).

3. Assign the new item to the class that appears most frequently among
these K neighbors.

This makes KNN a simple yet effective classification method. The value of K is
usually chosen based on experimentation:

• A small K may be sensitive to noise.

• A larger K makes the classification smoother but may ignore local

patterns.

Complexity of KNN

If there are q elements in the training set, then for each new item we must compare it
to all q elements. This requires O(q) time per item.
If there are n items to classify, the overall time is O(nq).

• Since q (training size) is fixed but possibly large, the problem is often
treated as O(n) in practice.

Thus, while KNN is simple, it can be computationally heavy for large datasets,
especially during classification.

Explanation of Figures

Figure 4.9 – Classification using Simple Distance Algorithm

This diagram shows three classes (A, B, and C).

• Each class has a central reference point (CA, CB, CC), which acts as a
representative for the group.

• The dashed lines show distances from class members to their

respective centers.

• A new item would be classified by finding which class center it is

closest to.

This method uses class representatives instead of considering all neighbors. It’s
simpler but less flexible than KNN.

Figure 4.10 – Classification using KNN

This diagram illustrates how KNN works with K = 3.

• The X’s represent training data points belonging to different classes.

• The point t is the new item that needs classification.

• The three closest training points (neighbors) to t are connected with

dashed lines.

• The class of t will be determined by the majority vote of these 3

neighbors.

Here, instead of using a single class center, KNN checks the local neighborhood
around t, making it more adaptive and accurate for irregularly shaped classes.
 HEIRARCHICAL ALGORITHMS

5.4 Hierarchical Algorithms

Hierarchical clustering algorithms create sets of clusters that can be organized into
different levels. The relationships between clusters are usually shown using a
dendrogram (a tree-like diagram).

• At the root of the dendrogram, all elements belong to a single cluster.

• At the leaves, each element is its own cluster.

• Internal nodes represent clusters formed by merging child clusters.

• Each level corresponds to a distance threshold used for merging.

Thus, clusters formed at a given level exist because the distance between their
elements is smaller than the threshold value for that level.

Example 5.2

Six elements (A, B, C, D, E, F) are clustered step by step:

• (a) Each element starts as its own cluster.

• (b) Four clusters are formed: two pairs of closely related elements.

• (c) A new element joins one of the two-element clusters to form a three-
element cluster.

• (d) The two-element cluster and the three-element cluster merge into a
five-element cluster, leaving F separate.

• (e) Finally, all six elements merge into one cluster.

This example shows how clusters are gradually combined based on proximity.

Complexity of Hierarchical Algorithms

 • Space complexity: O(n) for storing the adjacency matrix.

• Space for dendrogram: O(kn), much smaller than O(n²).

• Time complexity: Typically O(kn²), since each dendrogram level

requires an iteration.

• In some cases, time can be O(maxd × n²), where maxd is the

maximum distance between points.

• Different methods may merge clusters differently, either by choosing

the closest clusters or forming new ones at increasing distances.

Hierarchical clustering is especially useful when data naturally forms nested groups,
such as taxonomies in biology.

5.4.1 Agglomerative Algorithms

Agglomerative algorithms follow a bottom-up approach:

• Start with each item as a separate cluster.

• Merge clusters step by step until only one cluster remains.

• The merging strategy defines the specific algorithm used.

The input is an adjacency matrix (n × n) with pairwise distances. The output is a

dendrogram, which shows the merging process. Each level in the dendrogram can
be described as a triple:

• d: threshold distance

• k: number of clusters
• K: set of clusters formed

By cutting the dendrogram at a chosen distance threshold, different clustering results

can be obtained.

Algorithm 5.1 (General Agglomerative Algorithm)

• Input: set of elements, adjacency matrix.

• Output: dendrogram (DE).
Steps:

1. Start with each item as its own cluster.

2. Increase threshold distance gradually.

3. Merge clusters that are close enough.

4. Record new clusters in the dendrogram.

5. Repeat until one final cluster remains.

The merging behavior depends on the method (e.g., pairwise merging vs. multiple
merges).

Challenges of Agglomerative Algorithms

• High time and space requirements: adjacency matrix uses O(n²) space.

• The matrix is accessed repeatedly during clustering.

• Complexity depends on merging procedure; large datasets become

costly.

• Not incremental: if new data is added, the algorithm must be rerun from
the start.

Variants of Agglomerative Algorithms

1. Single Link (Nearest Neighbor)

• Two clusters are merged if any pair of points between them has
a distance ≤ threshold.

• Equivalent to finding connected components in a graph.

• Problem: Can create long “chains” of clusters.

• Complexity: ~O(n³).

Variation (MST-based):

• Builds a Minimum Spanning Tree (MST).

• Merges clusters based on edge distances.

• More efficient than repeated component searches.
 2. Complete Link (Farthest Neighbor)

• Opposite of single link.

• Two clusters merge only if all points are within the threshold.

• Produces compact, spherical clusters.

• Complexity: ~O(n³).

3. Average Link
• Uses the average distance between all points in two clusters.

• More balanced than single or complete link.

• Threshold increments can vary (e.g., 0.5, 1), slightly changing

dendrograms.

Example (Simplified from Example 5.3)

For five items (A, B, C, D, E):

• At distance 1: A merges with B, C merges with D → 3 clusters remain.

• At distance 2: (A,B) merges with (C,D) → 2 clusters remain.

• At distance 3: All items merge into one cluster.

The dendrogram shows these steps clearly with distance levels.

5.4.2 Divisive Clustering

Divisive clustering is the opposite approach:

• Start with all items in one cluster.

• Repeatedly split clusters into two until each item stands alone.

• Splits are made when some elements are not sufficiently close to
others.

This top-down method is less common than agglomerative but can be effective when
clusters are clearly separable.
 AGGLOMERATIVE ALGORITM

5.4.1 Agglomerative Algorithms

Agglomerative algorithms are a type of hierarchical clustering technique. The

process begins with each item as its own individual cluster. Step by step, clusters are
merged until eventually all items belong to a single cluster. The difference between
various agglomerative algorithms lies in how they decide which clusters to merge at
each stage.

The input to such algorithms is usually an adjacency matrix (n × n), where each entry
holds the distance between two elements. The output is a dendrogram (a tree-like
diagram), which shows the merging process at different distance thresholds. Each
entry in a dendrogram is represented as a triple:

• d: threshold distance,
• k: number of clusters at that stage,

• K: set of clusters formed.

This means the user can choose different clustering outcomes by cutting the
dendrogram at a desired distance threshold.

Algorithm 5.1 (General Agglomerative Algorithm)

• Input:

• Set of elements.
• Distance (adjacency) matrix.

• Output: Dendrogram (DE).

Steps:

1. Start with each item as its own cluster.

2. Gradually increase the threshold distance (d).
 3. At each level, merge clusters that are close enough.

4. Record the new clusters in the dendrogram.

5. Repeat until only one cluster remains.

The exact behavior depends on the NewClusters procedure, which defines how
merging is done. Different agglomerative methods differ at this step (e.g., merging
two vs. multiple clusters at a time).

Challenges of Agglomerative Algorithms

• High time and space cost:

• Adjacency matrix takes O(n²) space.

• The matrix must be accessed repeatedly during clustering.

• Complexity depends on the merging procedure and can be expensive

for large datasets.

• Not incremental: If new data is added or removed, the whole algorithm

must be rerun.

Variants of Agglomerative Algorithms

1. Single Link (Nearest Neighbor)

• Two clusters are merged if any pair of points between them has
a distance ≤ threshold.

• Equivalent to finding connected components in a graph.

• Problem: Can create long “chains” of clusters.

• Complexity: ~O(n³).

Variation (MST-based):

• Builds a Minimum Spanning Tree (MST).

• Merges clusters based on edge distances.

• More efficient than repeated component searches.

2. Complete Link (Farthest Neighbor)

• Opposite of single link.
 • Two clusters merge only if all points are within the threshold.

• Produces compact, spherical clusters.

• Complexity: ~O(n³).

3. Average Link

• Uses the average distance between all points in two clusters.

• More balanced than single or complete link.

• Threshold increments can vary (e.g., 0.5, 1), slightly changing

dendrograms.

Example (Simplified from Example 5.3)

Suppose we have five items A, B, C, D, and E with distances given in a table.

• At distance 1, A joins B and C joins D (three clusters form).

• At distance 2, (A,B) merges with (C,D) (two clusters form).

• At distance 3, everything merges into (A,B,C,D,E).

The dendrogram shows this merging process clearly, with levels marked by the
distance thresholds.

DATA MINING TASKS

1.1 Basic Data Mining Tasks

Data mining involves different tasks that help discover useful patterns, predictions,
and summaries from data. These tasks may work independently or be combined to
create more advanced applications.

1.1.1 Classification

Classification maps data into predefined classes or groups. It is known as supervised

learning because the categories are already known before analysis. The algorithm
learns the characteristics of each class from training data and then uses these rules
to classify new data.

• Example uses: deciding whether to approve a bank loan, identifying

credit risks.

• Pattern recognition is a type of classification, where an input (like an

image or sound) is assigned to the class it most closely resembles.

Example 1.2: At an airport, a passenger’s face is scanned, and its features (eye
distance, mouth shape, head shape, etc.) are compared with a database of known
offenders. If it matches, the passenger is flagged.

1.1.2 Regression (Learning)

Regression predicts a real-valued outcome by learning a mathematical function that

maps input data to the output. The model assumes the relationship fits a certain type
of function (e.g., linear, logistic) and chooses the best one using error analysis.

• Example uses: predicting stock prices, estimating income levels,

forecasting demand.

Example 1.3: A professor predicts his retirement savings using past data and a linear
regression model. Based on the results, he adjusts his investment strategy.

1.1.3 Time Series Analysis

This involves studying how an attribute’s value changes over time. Data is collected
at regular intervals (daily, weekly, hourly, etc.) and analyzed using plots and distance
measures.

Three key functions:

• Compare similarities between different time series.

• Analyze the structure of the data to classify its behavior.

• Use past values to predict future trends.

Example 1.4: Mr. Raghavan tracks the daily stock prices of three companies for a
month. He observes that stock X is less volatile but still shows better growth, so he
invests in it.

1.1.4 Prediction

Prediction is similar to classification but focuses on future states rather than current
ones. It uses historical and current data to forecast future outcomes. Methods
include regression, time series, or specialized algorithms.

• Example uses: flood prediction, weather forecasting, speech

recognition, machine learning.

Example 1.5: River monitors collect data such as water level, rainfall, and humidity.
This data is used to predict the likelihood of flooding downstream at future times.

1.1.5 Clustering

Clustering groups data into clusters based on similarity without predefined classes.
This is known as unsupervised learning or segmentation. The goal is to discover
natural groupings in data.

• Example uses: customer segmentation, market research,

bioinformatics.

Example 1.6: A department store clusters customers based on income, age, location,
and physical traits to target catalogs to different groups.

Segmentation is often treated as the same as clustering, though sometimes it

specifically refers to partitioning a database into disjoint subsets.

1.1.6 Summarization

Summarization reduces data into compact, descriptive information. It can either

retrieve representative subsets or calculate statistics like averages. This helps give
an overview of the data without analyzing every detail.
Example 1.7: U.S. News & World Report ranks universities partly by the average
SAT/ACT scores of admitted students. This average is a summarization of student
quality.

1.1.7 Association Rules

Association (or affinity analysis) finds relationships between items in data. The most
common example is market basket analysis, which identifies products that are often
purchased together.

• Example uses: marketing, recommendation systems, telecom failure

prediction.

Example 1.8: A grocery store finds that customers who buy bread also frequently buy
pretzels and jelly. The manager places pretzels and jelly near the bread section to
increase sales.

⚠ Note: These associations are correlations, not causal relationships, and may not
always hold in the future.

1.1.8 Sequence Discovery

Sequence discovery looks for patterns over time. Unlike association rules (which link
items bought together), it finds events that tend to happen in a sequence.

• Example uses: customer behavior analysis, web browsing patterns,

purchase timelines.

Example 1.9: A webmaster studies how users navigate a website. He notices that
70% of visitors who start at page A eventually reach page C through various paths.
To simplify access, he adds a direct link from A to C.

NEURAL NETWORKS

3.5 Neural Networks

Neural networks (NN), also known as artificial neural networks (ANN), are inspired
by the working of the human brain. Although the concept of an artificial neuron was
introduced in 1943, their practical use in computing only became common in the
1980s. A neural network is essentially an information processing system built as a
directed graph consisting of nodes (processing elements like neurons) and arcs
(connections between them). Each node processes inputs locally and independently,
which makes NNs well-suited for distributed or parallel computing environments.

Structure of Neural Networks

The NN is represented as a directed graph with three main types of nodes:

• Input nodes – located in the input layer, representing features or

attributes.

• Hidden nodes – located in one or more hidden layers, which perform

intermediate transformations.

• Output nodes – located in the output layer, providing the final prediction
or classification.

A tuple (data record) is passed through the input layer and processed by the hidden
layers before reaching the output nodes. Unlike decision trees, which remain fixed
once built, a neural network can learn and update itself by adjusting weights on arcs
while keeping the structure constant.

Learning in Neural Networks

Neural networks can learn from past mistakes. If a poor solution is given, the
network updates its weights to perform better in future. This ability makes them
powerful for solving complex problems. However, a major drawback is their lack of
interpretability—unlike decision trees, they are not easily understandable to end
users. They also work best with numeric data.

In practical use:

• Input values pass through layers.

• Each arc has a weight.

• Each node applies a function to its weighted inputs to produce an
output.
For example, the output of a hidden node depends on input values, the weights, and
an activation function that transforms the sum into a meaningful result.

Formal Definitions

• Definition 3.5 (Neural Network structure):

A neural network is a directed graph with:

• Input, hidden, and output nodes arranged in layers.

• Connections (arcs) between adjacent layers.

• Each arc labeled with a weight (wij).

• Each node labeled with a function (fi) that defines how it processes
inputs.

• Definition 3.6 (Neural Network model):

An NN model includes three parts:

1. Graph structure (the data representation).

2. Learning algorithm (how the network improves).

3. Recall technique (how outputs are obtained during prediction).

Applications of Neural Networks

NNs have been applied widely in:

• Pattern and speech recognition

• Medical diagnosis and drug design

• Fault detection and robot control

• Computer vision

• Business decision-making (e.g., optimizing airline seat booking)

They are very flexible and can approximate almost any function. However, they
require long training times, which makes them unsuitable for real-time applications.

Types of Neural Networks

• Feedforward networks – connections only move forward to later layers.
 • Feedback (recurrent) networks – connections can loop back to earlier
layers.

Learning approaches:

• Supervised learning – requires labeled training data.

• Unsupervised learning – discovers patterns without labels.

Overfitting in Neural Networks

A risk with NNs is overfitting: the network memorizes the training set too closely and
performs poorly on new data.

Ways to reduce overfitting:

• Use smaller networks.

• Employ early stopping during training.

• Train with larger datasets.

Activation Functions (3.5.1)

Each node’s output depends on its activation function, which transforms the
weighted sum of inputs. This is similar to how neurons in the brain fire only when
input exceeds a threshold.

Common activation functions include:

1. Linear function

• Simple proportional output:

f(S) = cS

• No upper or lower bounds.

2. Threshold (Step) function

• Outputs 0 or 1 depending on whether input exceeds a threshold.

• Variants include piecewise linear (ramp) functions.

3. Sigmoid function
 • S-shaped curve, outputs values between 0 and 1 (or -1 and 1).

• Smooth and differentiable, widely used.

• Example: Logistic function.

4. Hyperbolic Tangent (tanh)

• Similar to sigmoid but centered at 0 (range -1 to 1).

5. Gaussian function

• Bell-shaped curve, output between 0 and 1.

Bias in Neural Networks

Many nodes also include a bias input (constant value of 1). The bias allows shifting
the activation function along the x-axis, improving flexibility in fitting data.

TYPES OF DATA MARTS:

1.2.1 Types of Data Marts

Data marts are mainly divided into two groups:

1. Multidimensional (MDDB OLAP or MOLAP)

2. Relational OLAP (ROLAP)

There is also a hybrid approach that combines the features of both.

Multidimensional Data Marts (MDDB / MOLAP)

A multidimensional data mart stores numeric data in a way that reflects its natural
multidimensional nature. This makes it possible to slice and dice the data freely,
without being limited by the rigid table structure of relational databases.

Example: Imagine we are storing commodity prices.

• In a relational database (RDBMS), the data will usually be stored in

plain tables (rows and columns).
• But commodity prices are actually multidimensional—they vary by
commodity type, by year, and by region.
In an RDBMS, this multidimensional structure is lost, since everything is flattened
into tables. In contrast, in an MDDB, the data can be viewed in its full
multidimensional form. This means we can easily ask queries like:

• “What was the price trend of rice in Asia over the last 5 years?”

• “How do wheat prices in 2024 compare across different regions?”

This makes analysis and query processing far more powerful than in an RDBMS
environment. However, this power comes with a cost—only specialized DBMSs or
engines can support the MDDB model.

Relational OLAP Data Marts (ROLAP)

A ROLAP data mart is based on relational databases. Unlike MOLAP, it can handle
both numeric and text data, and does not require specialized software since it uses
standard RDBMS technology.

ROLAP is mainly used for Decision Support System (DSS) analysis, and it works
well with schemas such as the star schema (where data is organized into fact and
dimension tables).

Queries in ROLAP can be of two types:

• Ad hoc queries → created on the spot, flexible and exploratory.

• Predefined queries → written in advance for repeated use.

The processing in ROLAP is more predictable, since it organizes both summary data
(aggregated results) and detailed data (raw information) in the data mart. This
predictability makes ROLAP useful for routine business reporting and general-
purpose analysis.

Hybrid Approach

Apart from MOLAP and ROLAP, there also exists a hybrid approach. This approach
tries to combine the strengths of both MOLAP and ROLAP. For example, it may store
some data multidimensionally (for faster analysis of numeric values) and some data
relationally (to support flexibility and text-based queries).
 OLAP TOOLS

2.5.1 Categories of OLAP Tools

OLAP tools are broadly divided into two main categories:

1. MOLAP (Multidimensional OLAP)

2. ROLAP (Relational OLAP)

There are also hybrid approaches that combine both MOLAP and ROLAP features,
often called multirelational database systems.

All these tools typically use star schema or snowflake schema designs (discussed
earlier).

Applications

• Business: sales analysis, marketing campaigns, sales forecasting,

capacity planning.

• Government: commodity price monitoring, forecasting, plan

formulation, agricultural production forecasting (e.g., based on rainfall).

The range of applications is very wide, and case studies later in the book show this
in detail.

MOLAP

• Definition: MOLAP tools organize, navigate, and analyze data stored in

a multidimensional database (MDDB).

• Data Storage:

• Data is stored in an aggregated form.

• Uses efficient techniques like sparse data storage to minimize space

and improve response time.
 • Some systems add time as an extra dimension for time series analysis
(e.g., Pilot’s Software Analysis Server).

• Capabilities: Some tools (e.g., Oracle Express Server) add strong

analytical features directly into the database.

Best suited for:

• Applications that require iterative and comprehensive time series

analysis (e.g., financial analysis, budgeting).

Examples of MOLAP products:

• Arbor Software’s Essbase

• Oracle Express Server

• Pilot Software’s Lightship Server

• Sinper’s TM/1

• Planning Science’s Gentium

• Kenan Technology’s Multiway

Challenges:

• Supporting multiple subject areas in RDBMS can be difficult.

• Some vendors solve this by allowing MOLAP tools to access detailed

RDBMS data (useful in data warehouses with multiple subject areas).

• Example: sales data measured by multiple dimensions (product,

region) can be stored in a persistent structure, reducing overhead during application
initialization.

ROLAP

• Definition: Relational OLAP works directly with relational databases

(RDBMS) and is currently the fastest growing OLAP technology.

• Key Feature: Uses a metadata dictionary layer to create

multidimensional views from relational tables.

• Advantage: No need to create a separate multidimensional structure

like MOLAP.
Capabilities:

• Can generate multiple SQL statements to handle complex user

requests.

• Works with strong SQL engines, aware of RDBMS optimizers.

Flexibility:

• ROLAP allows multiple views without restructuring data.

• Often uses denormalized database designs (like star schema).

• Recently, there is a shift toward middleware technology and hybrid

OLAP, reducing the strict separation between ROLAP and MOLAP.

Vendors of ROLAP tools:

• Microstrategy (DSS Agent / DSS Server)

• Platinum/Prodea (Beacon)

• Information Advantage (AxSys)

• Informix/Stanford Technology Group (Metacube) – later acquired by

IBM

• SyBASE (HighGate Project)

2.5.2 Managed Query Environment (MQE)

Recent Trend:
• OLAP tools now allow users to run limited analysis directly against
RDBMS or by using an intermediate MOLAP server.

How it works:

• A query selects data from the DBMS.

• The data is delivered to the desktop system and stored in a data cube.
• The cube can be stored locally, allowing the user to perform:
 • Slice and dice operations

• Pivoting

• Other multidimensional analysis

Alternative approach:

• Data flows from RDBMS → MOLAP server → desktop.

Advantages:
• Easy to install, administer, and use.

• Provides advanced analysis to users already familiar with RDBMS.

• Lower cost compared to complex OLAP products.

Challenges:

• Data cubes must be built and maintained on desktops or servers.

• This causes data redundancy and network strain when many users are
involved.

• Lack of consistency between user-built cubes.

• Only relatively small amounts of data can be efficiently managed.

DATA MINING VERSUS KNOWLEDGE DISCOVERY IN DATABASES

The terms knowledge discovery in databases (KDD) and data mining are often used
as if they mean the same thing. In reality, they are not identical. KDD refers to the
whole process of finding useful hidden patterns in data, while data mining is only one
step of this process.

Over time, this activity has been given many other names, including knowledge
extraction, information discovery, exploratory data analysis, information harvesting,
and unsupervised pattern recognition.
In this book, KDD is seen as the larger process, and data mining as a step within it.

Definition 1.1: KDD is the process of finding useful information and patterns in data.

Definition 1.2: Data mining is the use of algorithms to extract the information and
patterns that are part of the KDD process.

The KDD Process

The KDD process is often said to be nontrivial, meaning it is not simple. A basic SQL
query can be viewed as a small part of KDD, but today it may feel trivial, even
though 30 years ago it was considered advanced. Similarly, techniques seen as
complex now may seem trivial in the future.

The word “useful” is central in the definition of KDD. Some definitions say “potentially
useful,” but this book argues that if the discovered information is not actually useful,
it should not be considered information at all. Of course, usefulness depends on the
individual user’s goals.

KDD is:

• A process with many steps.

• Takes data as input and produces useful information as output.

• Interactive and may take a lot of time.

• Dependent on both domain experts (who know the application area)

and technical experts (who know the algorithms and tools).

The Steps of the KDD Process

The KDD process consists of five main steps (FPSS96c):

1. Selection – Data needed for mining may come from many different and
heterogeneous sources such as databases, files, or even non-electronic sources.

2. Preprocessing – Data may have errors, missing values, or anomalies.

Activities here include correcting or removing erroneous data and filling in missing
values (sometimes using data mining tools).
 3. Transformation – Data is converted into a common format for
processing. It may also be encoded into more usable formats or reduced to fewer
values, making analysis easier.

4. Data Mining – Algorithms are applied to the transformed data,

depending on the specific mining task. This step generates the actual patterns and
results.

5. Interpretation/Evaluation – Results must be presented clearly to users.

Visualization and graphical tools are often used, since the usefulness of results
depends heavily on how well they are communicated.

Transformation

Transformation prepares data so it can be mined more effectively and produce more
meaningful results. This step may involve:

• Modifying the distribution of data to match the needs of certain mining

methods.

• Combining attribute values into new attributes (e.g., replacing current

date and birth date with age).

• Substituting one attribute for another (e.g., replacing actual values with
differences between consecutive values).

• Handling continuous values by grouping them into ranges.

• Removing outliers (rare extreme values that can distort results).

• Applying mathematical functions to data (e.g., taking the logarithm of

values).

These techniques reduce complexity, reduce variability, and can improve result
quality. However, if transformations are misapplied, they may distort the data and
lead to inaccurate results.

Visualization

Visualization refers to presenting data and mining results visually so that users can
better understand them. A common saying, “a picture is worth a thousand words,”
applies here because visual representations are often easier to grasp than formulas
or raw numbers. For example, a line graph of data distribution may be more
informative than the corresponding mathematical equation.
Visualization techniques include:

• Graphical – bar charts, pie charts, histograms, line graphs.

• Geometric – box plots, scatter diagrams.

• Icon-based – using figures, colors, or icons.

• Pixel-based – each data value shown as a colored pixel.

• Hierarchical – dividing the screen into regions based on data values.

• Hybrid – combining several approaches.

Visualizations may be 2D or 3D. They can also be used both to summarize data as
part of mining itself and to present complex mining results.

BAYESIAN CLASSIFICATION

Bayesian classification is a probabilistic approach to classification. It is based on

Bayes’ theorem, which helps us calculate the probability that a given data item
belongs to a particular class. Instead of just making hard rules, this method uses
statistics and prior knowledge to make predictions.

The Idea:

Imagine we want to classify a data point into one of several possible categories.
Bayesian classification asks:

• “Given the evidence (the attributes of this data point), what is the
probability that it belongs to Class A, Class B, etc.?”

It then assigns the data point to the class with the highest probability.

Bayes’ Theorem

The foundation is Bayes’ theorem:

P(H|E) = \frac{P(E|H) \times P(H)}{P(E)}

• H = a hypothesis (e.g., “this email is spam”)

• E = evidence or data (e.g., “the word ‘discount’ appears in the email”)

• P(H|E) = probability that the hypothesis is true given the evidence

• P(E|H) = probability of seeing the evidence if the hypothesis is true

• P(H) = prior probability of the hypothesis

• P(E) = overall probability of the evidence

Example

Suppose you’re trying to classify whether a fruit is an apple or an orange.

• Evidence: The fruit is round, about 8 cm, and red.

• Bayesian classifier looks at past data: how often apples vs oranges

have these features.

• If the probability is higher that these features occur in apples, then the
fruit is classified as an apple.

Characteristics

• Probabilistic, not absolute: Instead of saying “definitely Class A,” it says

“there’s an 80% chance it’s Class A.”

• Handles uncertainty: Works well when data is noisy or incomplete.

• Requires prior data: It learns from a training dataset that provides

probabilities.

Naïve Bayes

A common version is Naïve Bayes, which assumes that the features (e.g., color,
size, shape) are independent of each other. Even though this assumption is often
unrealistic, in practice it works surprisingly well for many applications, such as spam
filtering, document classification, and medical diagnosis.