Data Mining (DM) Outline
Outliers
All Methods
Approaches (How to use)
Supervised Method
Unsupervised Method
Clustering
Definition
Applications
Clustering Quality Measures
Data Types
Similarity and Dissimilarity
How to Measure Similarity/Dissimilarity
Partitioning Methods
K-Means
K-Medoids
DATA MINING (DM) EXAM NOTES
1. Outlier
Definition
An outlier is a data value or object that is very different from the other
data. It does not follow the normal pattern of the dataset.
Example
A person usually spends Rs. 2,000 with a credit card but suddenly spends
Rs. 5,00,000. This transaction is an outlier.
Types of Outliers
1. Global Outlier
A data object that is very different from all other data in the dataset.
Example: A student gets 100 marks while all others score between 40–60.
2. Contextual Outlier
A data object that is unusual only in a specific situation (context), such as
time or location.
Example: A temperature of 40°C is normal in summer but unusual in winter.
3. Collective Outlier
A group of data objects that together behave abnormally, even if each
individual object looks normal.
Example: Many computers sending attack packets together in a network.
Applications
Credit card fraud detection
Telecom fraud detection
Medical analysis
Customer segmentation
2. Outlier Detection Methods
Definition
Outlier Detection Methods are the techniques used to identify unusual or
abnormal data objects (outliers) in a dataset. Different methods use
different ways to find outliers.
Types of Outlier Detection Methods
1. Statistical Method
Definition:
The Statistical Method assumes that normal data follows a statistical model
(such as a normal distribution). Any data that does not fit the model is
considered an outlier.
Advantages
Simple to understand.
Works well when data follows a known distribution.
Disadvantages
Does not work well if data does not follow the assumed model.
Example
A student's marks are normally between 60–90, but one student gets 10
marks. This value may be an outlier.
2. Proximity-Based Method
Definition:
This method measures the distance between data objects. If a data object is
far away from its nearest neighbors, it is considered an outlier.
Advantages
Easy to understand.
Good for distance-based data.
Disadvantages
Distance calculation becomes expensive for large datasets.
Example
One house is located very far from all other houses, so it is treated as an
outlier.
3. Clustering-Based Method
Definition:
This method first creates clusters. Data objects that do not belong to any
cluster or belong to very small or sparse clusters are considered outliers.
Advantages
No labeled data is required.
Can detect unusual groups of data.
Disadvantages
Clustering takes more time.
Performance depends on the clustering algorithm.
Example
If one customer is very different from all customer groups, that customer is
an outlier.
4. Classification-Based Method
Definition:
This method uses a machine learning classifier to separate normal data
from outliers using training data.
Advantages
Fast prediction after training.
Can detect new outliers.
Disadvantages
Requires good quality labeled training data.
Example
An email classifier detects spam emails as outliers.
3. Approaches (How to Use Outlier Detection)
There are three approaches to detect outliers.
1. Supervised Approach
Definition
The supervised approach uses labeled data (normal and outlier examples)
to train a model. The model then identifies new outliers.
Advantages
High accuracy
Detects known outliers effectively
Disadvantages
Needs labeled data
Collecting labels is difficult
2. Unsupervised Approach
Definition
The unsupervised approach does not require labeled data. It assumes that
normal data forms clusters, while data far from the clusters is an outlier.
Advantages
No training data required.
Useful when labels are unavailable.
Disadvantages
May detect false outliers.
Cannot detect collective outliers effectively.
3. Semi-Supervised Approach
Definition
The semi-supervised approach uses a small amount of labeled data
together with unlabeled data to detect outliers.
Advantages
Better than unsupervised when a few labels are available.
Improves detection accuracy.
Disadvantages
Needs some labeled data.
More complex than the other approaches.
4. Clustering
Definition
Clustering is the process of grouping similar data objects into the same
cluster and separating different objects into different clusters. It is an
unsupervised learning technique because there are no predefined classes.
Example
Students with similar marks can be placed in one group, while students with
different marks can be placed in another group.
5. Applications of Clustering
Clustering is used in many fields:
1. Marketing
To identify groups of customers with similar buying behavior.
2. Pattern Recognition
To recognize patterns in data.
3. Image Processing
To group similar images or image pixels.
4. Document Classification
To organize similar documents together.
5. Insurance
To identify customers with high claim costs.
6. City Planning
To group houses according to location and value.
7. Earthquake Studies
To identify earthquake areas.
6. Clustering Quality Measures
Definition
Clustering quality measures are used to check how good the clusters are.
Good Clustering Should Have:
1. High Intra-Cluster Similarity
Objects inside the same cluster should be very similar.
2. Low Inter-Cluster Similarity
Objects from different clusters should be very different.
Example
If students with marks 80–90 are in one cluster and students with marks
40–50 are in another cluster, then clustering is good.
7. Data Types in Clustering
Different types of data are used in clustering:
1. Interval Data
Numerical values with equal intervals.
Example: Temperature, Age
2. Binary Data
Data having only two values.
Example: Yes/No, Male/Female
3. Nominal Data
Data with names or categories.
Example: Red, Blue, Green
4. Ordinal Data
Data with order or ranking.
Example: 1st, 2nd, 3rd Position
5. Ratio Data
Numerical data having a true zero point.
Example: Height, Weight
6. Mixed Data
Combination of different data types.
8. Similarity and Dissimilarity
Similarity
Definition
Similarity shows how much two objects are alike.
Example:
Two students having marks 85 and 87 are similar.
Dissimilarity
Definition
Dissimilarity shows how different two objects are.
Example:
A student with 90 marks and another with 30 marks are dissimilar.
9. How to Measure Similarity and Dissimilarity
Different distance measures are used.
1. Manhattan Distance
Measures distance by adding absolute differences.
Formula:
d = |x₁-y₁| + |x₂-y₂|
2. Euclidean Distance
Measures straight-line distance.
Formula:
d = √[(x₁-y₁)² + (x₂-y₂)²]
3. Jaccard Coefficient
Used for asymmetric binary data.
4. Simple Matching Coefficient
Used for symmetric binary data.
10. Partitioning Methods
Definition
Partitioning methods divide a dataset into K clusters, where each object
belongs to only one cluster.
Main Partitioning Methods:
1. K-Means
2. K-Medoids
11. K-Means Algorithm
Definition
K-Means is a partitioning clustering algorithm that divides data into K
clusters. Each cluster is represented by its centroid (mean point).
Working Steps
Step 1: Choose the number of clusters (K).
Step 2: Divide the data into K groups.
Step 3: Calculate the centroid (mean) of each cluster.
Step 4: Assign each data object to the nearest centroid.
Step 5: Recalculate the centroids.
Step 6: Repeat the process until no data object changes its cluster.
Advantages
Simple and easy to understand.
Fast and efficient for large datasets.
Easy to implement.
Disadvantages
Value of K must be given before clustering.
Sensitive to noise and outliers.
Cannot handle categorical data.
Cannot find non-convex shaped clusters.
Example
Suppose we have marks of students:
40, 42, 45, 80, 82, 85
If K = 2, K-Means will create:
Cluster 1: 40, 42, 45
Cluster 2: 80, 82, 85
12. K-Medoids Algorithm
Definition
K-Medoids is a partitioning clustering algorithm in which each cluster is
represented by a real data object (medoid) instead of the mean.
Working Steps
Step 1: Select K data objects as initial medoids.
Step 2: Assign every object to the nearest medoid.
Step 3: Calculate the swapping cost.
Step 4: Replace the medoid if a better one is found.
Step 5: Repeat until there is no change.
Advantages
Less affected by noise and outliers.
Uses actual data objects.
Produces more stable clusters.
Disadvantages
Slower than K-Means.
Not suitable for very large datasets.
Example
Suppose the data values are:
10, 12, 15, 60, 65, 70
Instead of calculating the mean, K-Medoids selects an actual value (such as
12 or 65) to represent each cluster.
Difference Between K-Means and K-Medoids
K-Means K-Medoids
Uses Centroid (Mean) Uses Medoid (Actual Data Object)
Faster Slower
Sensitive to outliers Less sensitive to outliers
Uses average value Uses real data point
Suitable for numerical Better when data contains noise or
data outliers
NUMERICAL QUESTIONS