Frequent patterns are patterns (e.g., itemsets, subsequences, or substructures) that appear frequently in a data set.

For example, a set of items, such as milk and bread, that appear frequently together in a transaction data set is a
frequent itemset. A subsequence, such as buying first a PC, then a digital camera, and then a memory card, if it
occurs frequently in a shopping history database, is a (frequent) sequential pattern. Finding frequent patterns plays
an essential role in mining associations, correlations, and many other interesting relationships among data.
Moreover, it helps in data classification, clustering, and other data mining tasks

Market Basket Analysis

A typical example of frequent itemset mining is market basket analysis. This process analyzes customer buying
habits by finding associations between the different items that customers place in their “shopping baskets”. The
discovery of these associations can help retailers develop marketing strategies by gaining insight into which items
are frequently purchased together by customers. For instance, if customers are buying milk, how likely are they to
also buy bread (and what kind of bread) on the same trip

“Which groups or sets of items are customers likely to purchase on a given trip to the store?” To answer your
question, market basket analysis may be performed on the retail data of customer transactions at your store. You can
then use the results to plan marketing or advertising strategies, or in the design of a new catalog. For instance,
market basket analysis may help you design different store layouts. In one strategy, items that are frequently
purchased together can be placed in proximity to further encourage the combined sale of such items. If customers
who purchase computers also tend to buy antivirus software
at the same time, then placing the hardware display close to the software display may help increase the sales of both
items. In an alternative strategy, placing hardware and software at opposite ends of the store may entice customers
who purchase such items to pick up other items along the way. For instance, after deciding on an expensive
computer, a customer may observe security systems for sale while heading toward the software display to purchase
antivirus software, and may decide to purchase a home security system as well. Market basket analysis can also help
retailers plan which items to put on sale at reduced prices. If customers tend to purchase computers and printers
together, then having a sale on printers may encourage the sale of printers as well as computers.

These patterns can be represented in the form of association rules. For example, the information that customers who
purchase computers also tend to buy antivirus software at the same time is represented in the following association
rule:

computer  antivirus_software [support = 2%,confidence = 60%]

Rule support and confidence are two measures of rule interestingness. They respectively reflect the usefulness and
certainty of discovered rules. A support of 2% for means that 2% of all the transactions under analysis show that
computer and antivirus software are purchased together. A confidence of 60% means that 60% of the customers who
purchased a computer also bought the software. Typically, association rules are considered interesting if they satisfy
both a minimum support threshold and a minimum confidence threshold. These thresholds can be a set by users
or domain experts. Additional analysis can be performed to discover interesting statistical correlations between
associated items.

association rule mining can be viewed as a two-step process:

1. Find all frequent itemsets: By definition, each of these itemsets will occur at least as frequently as a
predetermined minimum support count, min sup.

2. Generate strong association rules from the frequent itemsets: By definition, these rules must satisfy minimum
support and minimum confidence.

Support

Support refers to the default popularity of any product. You find the support as a quotient of the division of the
number of transactions comprising that product by the total number of transactions. Hence, we get

Support (Biscuits) = (Transactions relating biscuits) / (Total transactions)

= 400/4000 = 10 percent.

Confidence

Confidence refers to the possibility that the customers bought both biscuits and chocolates together. So, you need to
divide the number of transactions that comprise both biscuits and chocolates by the total number of transactions to
get the confidence.

Hence,

Confidence = (Transactions relating both biscuits and Chocolate) / (Total transactions involving Biscuits)

= 200/400

= 50 percent.

It means that 50 percent of customers who bought biscuits bought chocolates also.

Lift

Consider the above example; lift refers to the increase in the ratio of the sale of chocolates when you sell biscuits.
The mathematical equations of lift are given below.

Lift = (Confidence (Biscuits - chocolates)/ (Support (Biscuits)

= 50/10 = 5

It means that the probability of people buying both biscuits and chocolates together is five times more than that of
purchasing the biscuits alone. If the lift value is below one, it requires that the people are unlikely to buy both the
items together. Larger the value, the better is the combination.
Classification is a form of data analysis that extracts models describing important data classes. Such models, called
classifiers, predict categorical (discrete, unordered) class labels. For example,we can build a classification model to
categorize bank loan applications as either safe or risky. Such analysis can help provide us with a better
understanding of the data at large.

Eg: A bank loans officer needs analysis of her data to learn which loan applicants are “safe” and which are “risky”
for the bank. A marketing manager at AllElectronics needs data analysis to help guess whether a customer with a
given profile will buy a new computer. In each of these examples, the data analysis task is classification, where a
model or classifier is constructed to predict class (categorical) labels, such as “safe” or “risky” for the loan
application data; “yes” or “no” for the marketing data; or “treatment A,” “treatment B,” or “treatment C” for the
medical data.

Classification and Prediction:

 Classification and prediction are two forms of data analysis that can be used to extractmodels describing
important data classes or to predict future data trends.
 Classificationpredicts categorical (discrete, unordered) labels, prediction models
continuousvaluedfunctions.
 For example, we can build a classification model to categorize bankloan applications as either safe or risky,
or a prediction model to predict the expendituresof potential customers on computer equipment given their
income and occupation.
 A predictor is constructed that predicts a continuous-valued function, or ordered value, as opposed to a
categorical label.
 Regression analysis is a statistical methodology that is most often used for numeric prediction.
 Many classification and prediction methods have been proposed by researchers in machine learning, pattern
recognition, and statistics.
 Most algorithms are memory resident, typically assuming a small data size. Recent data mining research
has built on such work, developing scalable classification and prediction techniques capable of handling
large disk-resident data.
Because the class label of each training tuple is provided, this step is also known as supervised learning (i.e., the
learning of the classifier is “supervised” in that it is told to which class each training tuple belongs). It contrasts with
unsupervised learning (or clustering), in which the class label of each training tuple is not known, and the number
or set of classes to be learned may not be known in advance. For example, if we did not have the loan decision data
available for the training set, we could use clustering to try to determine “groups of like tuples,” which may
correspond to risk groups within the loan
application data.

Supervised Learning Unsupervised Learning

Uses Known and Labeled Data
Input Data Uses Unknown Data as input
as input
Less Computational
Computational Complexity More Computational Complex
Complexity
 Supervised Learning Unsupervised Learning
Uses Real-Time Analysis of
Real-Time Uses off-line analysis
Data
The number of Classes is The number of Classes is not
Number of Classes
known known
Moderate Accurate and
Accuracy of Results Accurate and Reliable Results
Reliable Results
The desired, output is not
Output data The desired output is given.
given.
In supervised learning it is not In unsupervised learning it is
possible to learn larger and possible to learn larger and
Model
more complex models than in more complex models than in
unsupervised learning supervised learning
In supervised learning training In unsupervised learning
Training data
data is used to infer model training data is not used.
Supervised learning is also Unsupervised learning is also
Another name
called classification. called clustering.
Test of model We can test our model. We can not test our model.
Example Optical Character Recognition Find a face in an image.

Classification by Decision Tree Induction:

Decision tree induction is the learning of decision trees from class-labeled training tuples. A decision tree is a
flowchart-like tree structure, where each internal node (nonleaf node) denotes a test on an attribute, each branch
represents an outcome of the test, and each leaf node (or terminal node) holds a class label. The topmost node in a
tree is the root node.
How Decision Trees Work?

The process of creating a decision tree involves:

1. Selecting the Best Attribute: Using a metric like Gini impurity, entropy, or information gain, the best
attribute to split the data is selected.

2. Splitting the Dataset: The dataset is split into subsets based on the selected attribute.

3. Repeating the Process: The process is repeated recursively for each subset, creating a new internal node or
leaf node until a stopping criterion is met (e.g., all instances in a node belong to the same class or a
predefined depth is reached).

Attribute Selection Measures

An attribute selection measure is a heuristic for selecting the splitting criterion that “best” separates a given data
partition, D, of class-labeled training tuples into individual classes. The attribute selection measure provides a
ranking for each attribute describing the given training tuples. The attribute having the best score for the measure4 is
chosen as the splitting attribute for the given tuples.
attribute selection measures—information gain, gain ratio, and Gini index.

Information Gain:

The expected information needed to classify a tuple in D is given by

where pi is the nonzero probability that an arbitrary tuple in D belongs to class Ci and
is estimated by|Ci,Dj| / |Dj|. A log function to the base 2 is used, because the information is encoded in bits. Info(D)
is just the average amount of information needed to identify the class label of a tuple in D. Note that, at this point,
the information we have is based solely on the proportions of tuples of each class. Info(D) is also known as the
entropy of D.

How much more information would we still need (after the partitioning) to arrive at an exact classification? This
amount is measured by

Information gain is defined as the difference between the original information

requirement (i.e., based on just the proportion of classes) and the new requirement (i.e.,
obtained after partitioning on A). That is,

Metrics for Evaluating Classifier Performance

True positives .TP/: These refer to the positive tuples that were correctly labeled by the classifier. Let TP be the
number of true positives.
True negatives .TN/: These are the negative tuples that were correctly labeled by the classifier. Let TN be the
number of true negatives.
False positives .FP/: These are the negative tuples that were incorrectly labeled as positive (e.g., tuples of class buys
computer D no for which the classifier predicted buys computer D yes). Let FP be the number of false positives.
False negatives .FN/: These are the positive tuples that were mislabeled as negative (e.g., tuples of class buys
computer D yes for which the classifier predicted buys computer D no). Let FN be the number of false negatives
K-Nearest Neighbor(KNN) Algorithm

 K-Nearest Neighbour is one of the simplest Machine Learning algorithms based on Supervised
Learning technique.
 K-NN algorithm assumes the similarity between the new case/data and available cases and put
the new case into the category that is most similar to the available categories.
 K-NN algorithm stores all the available data and classifies a new data point based on the
similarity. This means when new data appears then it can be easily classified into a well suite
category by using K- NN algorithm.
 K-NN algorithm can be used for Regression as well as for Classification but mostly it is used for
the Classification problems.
 K-NN is a non-parametric algorithm, which means it does not make any assumption on
underlying data.
 It is also called a lazy learner algorithm because it does not learn from the training set
immediately instead it stores the dataset and at the time of classification, it performs an action
on the dataset.
 KNN algorithm at the training phase just stores the dataset and when it gets new data, then it
classifies that data into a category that is much similar to the new data.
 Example: Suppose, we have an image of a creature that looks similar to cat and dog, but we
want to know either it is a cat or dog. So for this identification, we can use the KNN algorithm, as
it works on a similarity measure. Our KNN model will find the similar features of the new data
set to the cats and dogs images and based on the most similar features it will put it in either cat
or dog category.
Why do we need a K-NN Algorithm?
Suppose there are two categories, i.e., Category A and Category B, and we have a new data point x1, so this data
point will lie in which of these categories. To solve this type of problem, we need a K-NN algorithm. With the help
of K-NN, we can easily identify the category or class of a particular dataset. Consider the below diagram:

How does K-NN work?

The K-NN working can be explained on the basis of the below algorithm:

 Step-1: Select the number K of the neighbors

 Step-2: Calculate the Euclidean distance of K number of neighbors
 Step-3: Take the K nearest neighbors as per the calculated Euclidean distance.
 Step-4: Among these k neighbors, count the number of the data points in each category.
 Step-5: Assign the new data points to that category for which the number of the neighbor is maximum.
 Step-6: Our model is ready.

Suppose we have a new data point and we need to put it in the required category. Consider the below image:

 Firstly, we will choose the number of neighbors, so we will choose the k=5.
 Next, we will calculate the Euclidean distance between the data points. The Euclidean distance is the
distance between two points, which we have already studied in geometry. It can be calculated as:
  By calculating the Euclidean distance we got the nearest neighbors, as three nearest neighbors in category
A and two nearest neighbors in category B. Consider the below image:

 As we can see the 3 nearest neighbors are from category A, hence this new data point must belong to
category A.

What is the impact of curse of dimensionality on KNN?

As KNN is a distance based method , it gets directly impacted by high dimensional [Link]
individual distances between the points gets less significant in high dimensional spaces hence the
dimensional space becomes [Link] effects are

1. Increased Computational Cost: The number of distance calculations increases with the
number of dimensions.

2. Distance Uniformity: In high dimensions, the distances between points tend to become
similar. This uniformity makes it difficult to distinguish between close and far points.

3. Overfitting: High-dimensional spaces can lead to overfitting, where the model learns
noise in the training data rather than the actual patterns.
 Clustering
Cluster analysis or clustering is the process of partitioning a set of data objects (or observations) into subsets. Each
subset is a cluster, such that objects in a cluster are similar to one another, yet dissimilar to objects in other clusters.
The set of clusters resulting from a cluster analysis can be referred to as a clustering. In this context, different
clustering methods may generate different clusterings on the same data set. The partitioning is not performed by
humans, but by the clustering algorithm. Hence, clustering is useful in that it can lead to the discovery of previously
unknown groups within the data.

Cluster analysis has been widely used in many applications such as business intelligence, image pattern recognition,
Web search, biology, and security. In business intelligence, clustering can be used to organize a large number of
customers into groups, where customers within a group share strong similar characteristics. This facilitates the
development of business strategies for enhanced customer relationship management. Moreover, consider a
consultant company with a large number of projects. To improve project management, clustering can be applied to
partition projects into categories based on similarity so that project auditing and diagnosis (to improve project
delivery and outcomes) can be conducted effectively.

Applications of Cluster Analysis:

• Clustering analysis is broadly used in many applications such as market research, pattern recognition,
data analysis, and image processing.
• Clustering can also help marketers discover distinct groups in their customer base. And they can
characterize their customer groups based on the purchasing patterns.
• In the field of biology, it can be used to derive plant and animal taxonomies, categorize genes with similar
functionalities and gain insight into structures inherent to populations.
• Clustering also helps in identification of areas of similar land use in an earth observation database. It
also helps in the identification of groups of houses in a city according to house type, value, and geographic
location.
• Clustering also helps in classifying documents on the web for information discovery.
• Clustering is also used in outlier detection applications such as detection of credit card fraud.
• As a data mining function, cluster analysis serves as a tool to gain insight into the distribution of data to
observe characteristics of each cluster.

Requirements of Clustering in Data Mining:

• Scalability − We need highly scalable clustering algorithms to deal with large databases.
• Ability to deal with different kinds of attributes − Algorithms should be capable to be applied on any
kind of data such as interval-based (numerical) data, categorical, and binary data.
• Discovery of clusters with attribute shape − The clustering algorithm should be capable of detecting
clusters of arbitrary shape. They should not be bounded to only distance measures that tend to find
spherical cluster of small sizes.
• High dimensionality − The clustering algorithm should not only be able to handle low-dimensional data
but also the high dimensional space.
• Ability to deal with noisy data − Databases contain noisy, missing or erroneous data. Some algorithms are
sensitive to such data and may lead to poor quality clusters.
• Interpretability − The clustering results should be interpretable, comprehensible, and usable.
Clustering Methods

1. Partitioning methods: Given a set of n objects, a partitioning method constructs k partitions of the data, where
each partition represents a cluster and k _ n. That is, it divides the data into k groups such that each group must
contain at least one object. In other words, partitioning methods conduct one-level partitioning on data sets. The
basic partitioning methods typically adopt exclusive cluster separation. That is,each object must belong to exactly
one group.

Most partitioning methods are distance-based. Given k, the number of partitions to construct, a partitioning method
creates an initial partitioning. It then uses an iterative relocation technique that attempts to improve the
partitioning by moving objects from one group to another. The general criterion of a good partitioning is that objects
in the same cluster are “close” or related to each other, whereas objects in different clusters are “far apart” or very
different. There are various kinds of other criteria for judging the quality of partitions. Traditional partitioning
methods can be extended for subspace clustering, rather than searching the full data space. This is useful when there
are many attributes and the data are sparse.

Hierarchical methods: A hierarchical method creates a hierarchical decomposition of the given set of data objects.
A hierarchical method can be classified as being either agglomerative or divisive, based on how the hierarchical
decomposition is formed. The agglomerative approach, also called the bottom-up approach, starts with each object
forming a separate group. It successively merges the objects or groups close to one another, until all the groups are
merged into one (the topmost level of the hierarchy), or a termination condition holds. The divisive approach, also
called the top-down approach, starts with all the objects in the same cluster. In each successive iteration, a cluster is
split into smaller clusters, until eventually each object is in one cluster, or a termination condition holds.
Hierarchical clustering methods can be distance-based or density- and continuitybased.

Hierarchical methods suffer from the fact that once a step (merge or split) is done, it can never be undone. This
rigidity is useful in that it leads to smaller computation costs by not having to worry about a combinatorial number
of different choices. Such techniques cannot correct erroneous decisions; however, methods for improving the
quality of hierarchical clustering have been proposed.

Density-based methods: Most partitioning methods cluster objects based on the distance between objects. Such
methods can find only spherical-shaped clusters and encounter difficulty in discovering clusters of arbitrary shapes.
Other clustering methods have been developed based on the notion of density. Their general idea is to continue
growing a given cluster as long as the density (number of objects or data points) in the “neighborhood” exceeds
some threshold. For example, for each data point within a given cluster, the neighborhood of a given radius has to
contain at least a minimum number of points. Such a method can be used to filter out noise or outliers and discover
clusters of arbitrary shape. Density-based methods can divide a set of objects into multiple exclusive clusters, or a
hierarchy of clusters. Typically, density-based methods consider exclusive clusters only, and do not consider fuzzy
clusters. Moreover, density-based methods can be extended from full space to subspace clustering.

Grid-based methods: Grid-based methods quantize the object space into a finite number of cells that form a grid
structure. All the clustering operations are performed on the grid structure (i.e., on the quantized space). The main
advantage of this approach is its fast processing time, which is typically independent of the number of data objects
and dependent only on the number of cells in each dimension in the quantized space. Using grids is often an efficient
approach to many spatial data mining problems, including clustering. Therefore, grid-based methods can be
integrated with other clustering methods such as density-based methods and hierarchical methods.

Difference between agglomerative clustering and Divisive

clustering :
S.
Parameters Agglomerative Clustering Divisive Clustering
No.

1. Category Bottom-up approach Top-down approach

each data point starts in its own cluster, and the

all data points start in a single cluster, and the
algorithm recursively merges the closest pairs of
2. Approach algorithm recursively splits the cluster into smaller
clusters until a single cluster containing all the data
sub-clusters until each data point is in its own cluster.
points is obtained.

Agglomerative clustering is generally more

computationally expensive, especially for large Comparatively less expensive as divisive clustering
3. Complexity level datasets as this approach requires the calculation of only requires the calculation of distances between sub-
all pairwise distances between data points, which clusters, which can reduce the computational burden.
can be computationally expensive.

divisive clustering may create sub-clusters around

Agglomerative clustering can handle outliers better outliers, leading to suboptimal clustering
4. Outliers than divisive clustering since outliers can be results.
absorbed into larger clusters

Agglomerative clustering tends to produce more

divisive clustering can be more difficult to interpret
interpretable results since the dendrogram shows the
Interpretability since the dendrogram shows the splitting process of
5. merging process of the clusters, and the user can
the clusters, and the user must choose a stopping
choose the number of clusters based on the desired
criterion to determine the number of clusters.
level of granularity.

Scikit-learn provides multiple linkage methods for divisive clustering is not currently implemented in
Implementation
6. agglomerative clustering, such as “ward,” Scikit-
“complete,” “average,” and “single,” learn.
S.
Parameters Agglomerative Clustering Divisive Clustering
No.

Here are some of the applications in which

Here are some of the applications in which Divisive
Agglomerative Clustering is used :
Clustering is used :
7. Example
Image segmentation, Customer segmentation,
Market segmentation, Anomaly detection, Biological
Social network analysis, Document clustering,
classification, Natural language processing, etc.
Genetics, genomics, etc., and many more.

k-Means Algorithm: A Centroid-Based Technique

• K-means algorithm in data mining starts with a first group of randomly selected centroids,
• the centroid of a cluster is its center point.
• which are used as the beginning points for every cluster, and
• then performs iterative (repetitive) calculations to optimize the positions of the centroids
It halts creating and optimizing clusters when either:
• The centroids have stabilized — there is no change in their values because the clustering has been
successful.
The defined number of iterations has been achieve

 First it randomly selects k of the objects in D, each of which initially represents a cluster mean or center.

 For each of the remaining objects, an object is assigned to the cluster to which it is the most similar, based
on the Euclidean distance between the object and the cluster mean.

 The k-means algorithm then iteratively improves the within-cluster variation.

 For each cluster, it computes the new mean using the objects assigned to the cluster in the previous
iteration.

 All the objects are then reassigned using the updated means as the new cluster centers.

 The iterations continue until the assignment is stable, that is, the clusters formed in the current round are
the same as those formed in the previous round.
k-Medoids Algorithm:

• The k-means algorithm is sensitive to outliers

• because such objects are far away from the majority of the data, and thus, when assigned to a cluster, they
can dramatically distort the mean value of the cluster.
• This inadvertently affects the assignment of other objects to clusters.
• It is more robust to noise and outliers than k-means.
• K-means attempts to minimize the total squared error, while k-medoids minimizes the sum of dissimilarities
between points labeled to be in a cluster and a point designated as the center of that cluster.
• In contrast to the k-means algorithm, k-medoids chooses datapoints as centers.

DBSCAN Algorithm: Density-based spatial clustering of applications with noise

• The DBSCAN algorithm uses two parameters:
• minPts: The minimum number of points (a threshold) clustered together for a region to be considered
dense.
• eps (ε): A distance measure that will be used to locate the points in the neighborhood of any point.

• Core — This is a point that has at least m points within distance n from itself. Border — This is a point
that has at least one Core point at a distance n. Noise — This is a point that is neither a Core nor a Border.
And it has less than m points within distance n from itself

How does DBSCAN find clusters?

• Initially, all objects in a given data set D are marked as “unvisited.”

• DBSCAN randomly selects an unvisited object p, marks p as “visited,” and checks whether the -
neighborhood of p contains at least MinPts objects.
• If not, p is marked as a noise point.
• Otherwise, a new cluster C is created for p, and all the objects in the -neighborhood of p are added to a
candidate set, N.
• DBSCAN iteratively adds to C those objects in N that do not belong to any cluster.
• In this process, for an object p0 in N that carries the label “unvisited,” DBSCAN marks it as “visited” and
checks its -neighborhood.
• If the -neighborhood of p0 has at leastMinPts objects, those objects in the -neighborhood of p0 are added to
N.
• DBSCAN continues adding objects to C until C can no longer be expanded, that is, N is empty. At this
time, cluster C is completed, and thus is output.
• To find the next cluster, DBSCAN randomly selects an unvisited object from the remaining ones. The
clustering process continues until all objects are visited