Unit-5

Cluster Analysis
● Cluster Analysis: Cluster analysis or simply 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.
● Clustering is known as unsupervised learning because the class label information is
not present. For this reason, clustering is a form of learning by observation, rather than
learning by examples
● Clustering is also called data segmentation in some applications because clustering
partitions large data sets into groups according to their similarity. Clustering can also
be used for outlier detection, where outliers (values that are “far away” from any
cluster) may be more interesting than common cases.
● Because a cluster is a collection of data objects that are similar to one another within
the cluster and dissimilar to objects in other clusters, a cluster of data objects can be
treated as an implicit class. In this sense, clustering is sometimes called automatic
classification. Again, a critical difference here is that clustering can automatically find
the groupings. This is a distinct advantage of cluster analysis.
● Example: 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.
Requirements for Cluster Analysis
● Scalability: Many clustering algorithms work well on small data sets containing fewer
than several hundred data objects; however, a large database may contain millions or
even billions of objects, particularly in Web search scenarios. Clustering on only a
sample of a given large data set may lead to biased results.
● Requirements for domain knowledge to determine input parameters: Many
clustering algorithms require users to provide domain knowledge in the form of input
parameters such as the desired number of clusters. Consequently, the clustering results
may be sensitive to such parameters.
● Discovery of clusters with arbitrary shape: Many clustering algorithms determine
clusters based on Euclidean or Manhattan distance measures (Chapter 2). Algorithms
based on such distance measures tend to find spherical clusters with similar size and
density. However, a cluster could be of any shape. Consider sensors, for example,
 which are often deployed for environment surveillance. Cluster analysis on sensor
readings can detect interesting phenomena
● Ability to deal with different types of attributes: Many algorithms are designed to
cluster numeric (interval-based) data. However, applications may require clustering
other data types, such as binary, nominal (categorical), and ordinal data, or mixtures of
these data types.
● Ability to deal with noisy data: Most real-world data sets contain outliers and/or
missing, unknown, or erroneous data. Sensor readings, for example, are often noisy—
some readings may be inaccurate due to the sensing mechanisms, and some readings
may be erroneous due to interferences from surrounding transient objects. Clustering
algorithms can be sensitive to such noise and may produce poor-quality clusters.
Therefore, we need clustering methods that are robust to noise.
● Interpretability and usability: Users want clustering results to be interpretable,
comprehensible, and usable. That is, clustering may need to be tied in with specific
semantic interpretations and applications.
Aspects with which clustering methods can be compared:
● The partitioning criteria: In some methods, all the objects are partitioned so that no
hierarchy exists among the clusters. That is, all the clusters are at the same level
conceptually. Such a method is useful, for example, for partitioning customers into
groups so that each group has its own manager. Alternatively, other methods partition
data objects hierarchically, where clusters can be formed at different semantic levels.
For example, in text mining, we may want to organize a corpus of documents into
multiple general topics, such as “politics” and “sports,” each of which may have
subtopics, For instance, “football,” “basketball,” “baseball,” and “hockey” can exist as
subtopics of “sports.” The latter four subtopics are at a lower level in the hierarchy than
“sports.”
● Separation of clusters: Some methods partition data objects into mutually exclusive
clusters. When clustering customers into groups so that each group is taken care of by
one manager, each customer may belong to only one group. In some other situations,
the clusters may not be exclusive, that is, a data object may belong to more than one
cluster.
● Similarity measure: Some methods determine the similarity between two objects by
the distance between them. Such a distance can be defined in Euclidean space, a road
network, a vector space, or any other space. In other methods, the similarity may be
defined by connectivity based on density or contiguity, and may not rely on the
absolute distance between two objects.
● Clustering space: Many clustering methods search for clusters within the entire given
data space. These methods are useful for low-dimensional data sets. With high-
dimensional data, however, there can be many irrelevant attributes, which can make
similarity measurements unreliable. Consequently, clusters found in the full space are
often meaningless. It’s often better to instead search for clusters within different
subspaces of the same data set
Difference between Partitioning methods and Hierarchical methods
● 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.
This requirement may be relaxed, for example, in fuzzy partitioning
[Link] 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 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
[Link] partitioning methods can be extended for
subspace clustering, rather than searching the full data space.
Achieving global optimality in partitioning-based clustering is often
computationally prohibitive, potentially requiring an exhaustive
enumeration of all the possible partitions. Instead, most
applications adopt popular heuristic methods, such as greedy
approaches like the k-means and the k-medoids algorithms, which
progressively improve the clustering quality and approach a local
optimum. These heuristic clustering methods work well for finding
spherical-shaped clusters in small- to medium-size databases.
● 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 continuity-based. Various extensions of hierarchical methods consider
clustering in subspaces as well. 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.
This is a single-linkage approach in that each cluster is represented by all the objects in the
cluster, and the similarity between two clusters is measured by the similarity of the closest pair
of data points belonging to different clusters
A tree structure called a dendrogram is commonly used to represent the process of hierarchical
clustering. It shows how objects are grouped together (in an agglomerative method) or
partitioned (in a divisive method) step-by-step
 Text Mining:

Focus:
● Analyzing and extracting patterns, information, and knowledge from
unstructured text data, including documents, articles, and social media posts.
Example - Sentiment Analysis:
● Utilizing natural language processing (NLP) techniques to assess the sentiment
expressed in customer reviews, helping businesses gauge public opinion.
Application:
● Enhancing customer experience, product development, and marketing strategies
by understanding sentiments and preferences expressed in textual data.
Techniques:
● Involves a range of techniques, such as tokenization, part-of-speech tagging,
named entity recognition, and machine learning algorithms for sentiment
classification.
Outcome:
● Transforms unstructured text into structured data, enabling businesses to make
data-driven decisions based on textual information.

Data Mining:

Focus:
● Extracting hidden patterns, relationships, and valuable insights from large and
diverse datasets, irrespective of data types.
Example - Market Basket Analysis:
● Examining transaction data to identify associations between products, informing
strategic decisions for product placement and marketing.
Application:
● Used in various industries for fraud detection, customer segmentation, predictive
maintenance, and personalized marketing.
Techniques:
● Involves clustering algorithms (e.g., k-means), classification algorithms (e.g.,
decision trees), association rule mining, regression analysis, and anomaly
detection.
Outcome:
● Empowers organizations to make informed decisions, optimize processes, and
uncover actionable insights from large datasets.

Web Mining:

Focus:
 ● Extracting knowledge from web-related data, covering aspects like web pages,
hyperlinks, and user behavior.
Example - Web Content Mining:
● Extracting relevant information from web pages to identify trends, keywords,
and themes, aiding in content understanding.
Application:
● Enhancing search engine results, improving website usability, and providing
insights into user behavior for website optimization.
Categories:
● Web Content Mining analyzes the content, Web Structure Mining examines the
link structure, and Web Usage Mining studies user interactions.
Outcome:
● Provides valuable insights into web content, structure, and user behavior,
facilitating improvements in web-based applications and services.

Base for Data Mining Text Mining Web Mining

Comparison

Concept Data mining is the Text mining is Web mining is a

statistical the subset of subset of Data
technique of Data Mining that Mining that
processing raw involves involves
data into processing processing which
structural form. unstructured text data related to
documents into the Web. It can
a structured be Web Logs,
format. Web Structure
data, or Web
Contact data.

Data Retrieval Data is mined and Text Data are Web Data can be
then stored in the stored in Text in the form of
data warehouse. Documents, Structure,
The data stored in emails, and logs Content, and
Databases and and then usage data and
spreadsheets are processed to is later converted
used to gather gather high- into useful
information and quality information.
 perform analysis. information.

Types of Data The discovery of Text Mining Web mining

knowledge from involves data mainly deals with
structured Data is from text three types of
homogeneous documents, data, i.e., Web
and easy to emails, logs, Structure Data,
access. PDFs, etc. Web Content
Data, and Web
Usage Data.

Application Data Mining is Text Mining is Web Mining is

used in fields like used in the fields used to extract
medicine, like customer information from
marketing, profile analysis, the web, and
healthcare, etc. bioscience, etc. analyze weblogs,
etc.

Data Format In Data Mining the In Text Mining, In Web Mining,

data is stored in a the data is the data is
structured format stored in an structured as well
unstructured as unstructured.
format The data format
depends upon
the type of
Mining method.

Skills Required To retrieve Text mining In web mining,

meaningful data requires pattern Application-level
from Data Mining, recognition knowledge, Data
one must be techniques and engineering,
aware of Data Natural statistics, and
cleansing language probability are
techniques, processing to required to
machine learning enrich the successfully
algorithms, meaning of the retrieve the
statistics, and text. information from
 probability weblogs.

Techniques Statistical In Text Mining, In web mining,

Used techniques are Computational Sequential
most helpful in linguistic pattern,
analyzing data. principles are clustering, and
used to evaluate associative
the meaning of mining principles
the text. are used.

Difference between agglomerative clustering and

Divisive clustering:

Agglomerative Divisive
[Link]. Parameters
Clustering Clustering

1. Category Bottom-up approach Top-down approach

each data point starts

all data points start
in its own cluster, and
in a single cluster,
the algorithm
and the algorithm
recursively merges the
recursively splits
2. Approach closest pairs of
the cluster into
clusters until a single
smaller sub-clusters
cluster containing all
until each data point
the data points is
is in its own cluster.
obtained.
 Agglomerative
clustering is generally Comparatively less
more computationally expensive as
expensive, especially divisive clustering
for large datasets as only requires the
this approach requires calculation of
3. Complexity-level
the calculation of all distances between
pairwise distances sub-clusters, which
between data points, can reduce the
which can be computational
computationally burden.
expensive.

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

Agglomerative divisive clustering

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

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

Here are some of the

Here are some of
applications in which
the applications in
Agglomerative
Divisive Clustering:
Clustering is used:

Market
Image segmentation,
7. Example segmentation,
Customer
Anomaly detection,
segmentation, Social
Biological
network analysis,
classification,
Document clustering,
Natural language
Genetics, genomics,
processing, etc.
etc., and many more.