Unit 4: UNSUPERVISED LEARNING: CLUSTERING AND PATTERN DETECTION - Subjective Questions

Unsupervised learning is a machine learning approach in which the algorithm learns from data without predefined target labels. It attempts to discover hidden structures, groups, relationships, or patterns in the data.

Difference from supervised learning:

• Supervised learning uses labeled data containing input-output pairs.
• Unsupervised learning uses unlabeled data.
• Supervised learning predicts known outcomes, such as class labels or numerical values.
• Unsupervised learning discovers unknown groupings or associations.

Importance in predictive analytics:

• Clustering helps segment customers, products, or transactions.
• Pattern detection identifies frequent relationships among variables.
• These methods support customer profiling, anomaly detection, recommendation systems, and market analysis.
• The discovered structure can later be used as input for supervised predictive models.

K-means clustering partitions observations into clusters so that observations within the same cluster are as similar as possible.

The intuition is based on repeatedly assigning each observation to the nearest representative point and then improving those representative points.

Main concepts:

• A centroid is the mean position of all observations assigned to a cluster.
• During cluster assignment, each observation is assigned to the centroid with the smallest distance, commonly Euclidean distance.
• During centroid updating, the mean of all observations in each cluster is recalculated.
• These two steps are repeated until assignments stop changing or the improvement becomes negligible.

The objective is to minimize the within-cluster sum of squared errors:

where is cluster and is its centroid.

The K-means algorithm can be performed as follows:

1. Select the desired number of clusters, .
2. Initialize centroids, usually by randomly selecting observations or using a controlled initialization method.
3. Calculate the distance between every observation and every centroid.
4. Assign each observation to the nearest centroid.
5. Recalculate each centroid as the mean of the observations assigned to it.
6. Repeat the distance calculation, assignment, and updating steps.
7. Stop when one of the following conditions is met:
   • Cluster assignments no longer change.
   • Centroid movement is below a selected tolerance.
   • The reduction in the objective function is insignificant.
   • A maximum number of iterations is reached.

The algorithm attempts to minimize the within-cluster sum of squared errors. Because it is iterative, its final result depends partly on the initial centroid positions.

The random initialization trap occurs because K-means may converge to a local minimum rather than the globally best clustering solution. Different randomly selected starting centroids can therefore produce different final clusters.

Reasons for the problem:

• The objective function is non-convex with respect to cluster assignments and centroids.
• Poorly placed initial centroids may cause several centroids to move toward the same region.
• Some clusters may be missed or become empty.
• The algorithm may converge quickly to a suboptimal arrangement.

Methods for reducing the problem:

• Run K-means multiple times with different initializations.
• Select the solution with the lowest within-cluster sum of squared errors.
• Use K-means++, which spreads initial centroids across the data space using distance-based selection.
• Set a fixed random seed when reproducibility is required.
• Check whether the resulting clusters are stable across repeated runs.

K-means++ is an initialization strategy designed to choose well-separated starting centroids.

Procedure:

1. Choose the first centroid randomly from the observations.
2. For every remaining observation, calculate its squared distance from the nearest selected centroid.
3. Select the next centroid with probability proportional to .
4. Repeat until centroids have been selected.
5. Apply the normal K-means iteration.

Observations far from existing centroids have a greater chance of becoming initial centroids. This tends to spread the starting points across different regions of the data.

Advantages:

• Reduces the chance that multiple centroids begin in the same region.
• Often produces lower initial clustering error.
• Improves convergence speed and solution quality.
• Provides more stable results than a single arbitrary random initialization.

It does not guarantee the global optimum, so repeated runs may still be useful.

For an observation and a centroid , Euclidean distance is calculated as:

K-means assigns each observation to the centroid having the smallest distance. The squared version is commonly used in the objective function because it avoids repeated square-root calculations.

Importance of feature scaling:

• Features measured in large units can dominate the distance calculation.
• For example, annual income may overpower age if both are used without scaling.
• Standardization transforms a feature using its mean and standard deviation:
  
• Min-max normalization can also scale values to a common interval.

Scaling ensures that features contribute more comparably. However, scaling should reflect the analytical purpose, because it can also change the interpretation of distance and cluster structure.

Selecting is important because K-means requires the number of clusters before training. Common methods include:

• Elbow method: Plot the within-cluster sum of squared errors against different values of and identify the point where additional clusters provide only small improvements.
• Silhouette analysis: Measure how similar an observation is to its own cluster compared with other clusters. Higher average silhouette values indicate better separation and cohesion.
• Gap statistic: Compare the observed clustering performance with that expected under a reference null distribution.
• Domain knowledge: Use business or scientific understanding to determine a meaningful number of segments.
• Stability analysis: Repeat clustering on samples or with different initializations and check whether the clusters remain consistent.

The elbow method examines:

As increases, decreases. The preferred value is often near the bend where the reduction begins to level off.

Hierarchical clustering builds a nested sequence of clusters rather than producing only one fixed partition. In agglomerative hierarchical clustering, each observation begins as an individual cluster.

Procedure:

1. Start with clusters, one for each observation.
2. Calculate distances between all pairs of clusters.
3. Merge the two closest clusters.
4. Recalculate distances between the new cluster and the remaining clusters.
5. Continue until all observations form one cluster.

The results are displayed in a dendrogram:

• The leaves represent individual observations.
• Each joining point represents a cluster merge.
• The height of a joining point indicates the dissimilarity at which the merge occurred.
• A horizontal cut across the dendrogram creates a selected number of clusters.

Agglomerative clustering does not require the number of clusters at the beginning, although a cut level must be chosen for interpretation.

K-means and agglomerative hierarchical clustering differ in several ways:

• Input requirements: K-means requires the number of clusters in advance. Hierarchical clustering can produce a dendrogram before selecting the final number of clusters.
• Output: K-means produces one partition for a chosen . Hierarchical clustering produces a hierarchy of nested partitions.
• Cluster shape: K-means works best with compact, roughly spherical clusters. Hierarchical methods can represent more varied structures depending on the linkage method.
• Interpretability: A dendrogram provides a visual explanation of how observations merge. K-means is easier to interpret when centroids have clear meanings.
• Computational cost: K-means is usually more scalable for large data sets. Hierarchical clustering often requires substantial memory and computation because many pairwise distances are stored.
• Sensitivity: K-means is sensitive to initialization and feature scaling. Hierarchical clustering is sensitive to the distance metric, linkage rule, and early merging decisions.

The best method depends on the data size, structure, and analytical objective.

Single linkage defines the distance between two clusters as the minimum distance between any observation in the first cluster and any observation in the second cluster:

Advantages:

• Can identify elongated or non-spherical clusters.
• Conceptually simple and easy to calculate.
• Useful when clusters are connected through nearby observations.

Disadvantages:

• It is highly sensitive to noise and outliers.
• A sequence of intermediate observations can connect otherwise separate groups.
• It may produce poorly separated clusters.

This behavior is called the chaining effect. A long chain of points can cause two dense groups to be merged because each neighboring pair is close, even though the two groups as a whole are far apart.

Complete linkage defines the distance between two clusters as the maximum distance between any observation in one cluster and any observation in the other:

Comparison with single linkage:

• Single linkage uses the closest pair of observations; complete linkage uses the farthest pair.
• Single linkage may create elongated chains; complete linkage generally creates compact clusters.
• Complete linkage is less affected by the chaining effect.
• Complete linkage is more sensitive to outliers because a single distant observation can determine the inter-cluster distance.
• Single linkage can discover irregular shapes more easily, while complete linkage is better for well-separated, compact groups.

Complete linkage is often preferred when the goal is to obtain clusters whose members are all reasonably close to one another.

Average linkage defines the distance between two clusters as the average distance between all pairs of observations across the clusters:

It provides a compromise between single and complete linkage. It is less affected by chaining than single linkage and less dominated by extreme pairs than complete linkage.

Centroid linkage calculates the distance between the centroids of two clusters:

where and are the cluster centroids.

Practical comparison:

• Average linkage considers all cross-cluster distances.
• Centroid linkage summarizes each cluster using one representative point.
• Average linkage often produces balanced and stable clusters.
• Centroid linkage is computationally convenient but may produce reversals in a dendrogram, where a later merge can appear at a lower height than an earlier merge.
• Both methods depend on the selected distance measure and feature scaling.

The four linkage methods differ in how they measure the distance between clusters:

• Single linkage: Uses the minimum pairwise distance. It can detect irregular shapes but is vulnerable to chaining and noise.
• Complete linkage: Uses the maximum pairwise distance. It produces compact clusters but is sensitive to outliers.
• Average linkage: Uses the mean of all pairwise distances. It provides a balance between single and complete linkage and is often relatively stable.
• Centroid linkage: Uses the distance between cluster centroids. It is simple and efficient but can produce unusual dendrogram behavior and may hide internal cluster structure.

The choice depends on the data:

• Use single linkage when connectivity and irregular shapes are important.
• Use complete linkage when compact, tightly grouped clusters are desired.
• Use average linkage for a compromise between the extremes.
• Use centroid linkage when cluster centers are meaningful and computational simplicity is useful.

Feature scaling and the distance metric should be selected consistently for all methods.

An association rule expresses a relationship between itemsets in the form:

where is the antecedent and is the consequent, with .

• An itemset is a collection of one or more items, such as bread and butter.
• The antecedent is the left-hand side .
• The consequent is the right-hand side .
• Support measures how frequently and occur together:
  
• Confidence measures the conditional probability of purchasing when occurs:
  
• Lift compares the rule with random co-occurrence:
  
  A lift greater than suggests a positive association.

Suppose a store has transactions. Assume:

• transactions contain bread.
• transactions contain butter.
• transactions contain both bread and butter.

For the rule :

• Support:
  
  Thus, bread and butter occur together in of transactions.

• Confidence:
  
  Therefore, of customers who purchase bread also purchase butter.

• Lift:
  
  The purchase of butter is twice as likely among bread buyers as in the overall transaction population.

The rule has reasonable support, confidence, and lift greater than , indicating a positive association. However, business usefulness also depends on price, profitability, and actionability.

The process generally includes the following stages:

1. Represent each transaction as a set of purchased items.
2. Select a minimum support threshold.
3. Find itemsets whose support is at least the threshold. These are called frequent itemsets.
4. For each frequent itemset, divide it into possible antecedent and consequent subsets.
5. Calculate confidence for each candidate rule.
6. Retain rules whose confidence meets the selected minimum confidence.
7. Evaluate lift and other measures to remove misleading or uninteresting rules.
8. Interpret the remaining rules using domain knowledge.

Algorithms such as Apriori use the downward-closure property: if an itemset is infrequent, every larger itemset containing it must also be infrequent. This property enables pruning of the search space. Other approaches, such as FP-Growth, use a compressed tree structure to find frequent patterns more efficiently.

The Apriori principle states that every subset of a frequent itemset must also be frequent. Equivalently, if an itemset is infrequent, every larger itemset containing it must be infrequent.

For example, if the itemset does not satisfy the minimum support threshold, then and every other superset containing and can be discarded.

Use in Apriori:

• Generate candidate one-itemsets and count their support.
• Remove itemsets below minimum support.
• Join frequent itemsets to generate larger candidates.
• Prune candidates containing an infrequent subset.
• Repeat until no larger frequent itemsets can be generated.
• Generate rules from the frequent itemsets.

Without pruning, all possible item combinations would need to be examined. The Apriori principle substantially reduces candidate generation, although the method can still be expensive for large data sets or low support thresholds.

Market basket analysis examines transaction records to discover items that are frequently purchased together. It uses association rules to identify relationships in customer purchasing behavior.

A retailer can use the results to:

• Place related products near one another.
• Create product bundles or combination discounts.
• Recommend complementary products during online checkout.
• Improve targeted advertising and coupon distribution.
• Forecast demand for related items.
• Optimize shelf placement and store layout.
• Identify products that serve as gateways to additional purchases.

For example, a rule such as with high confidence may support a recommendation or bundle. The retailer should also consider lift and support. A rule with high confidence but very common consequent may not be especially informative. Rules should be evaluated for profitability, inventory availability, seasonality, and whether they lead to a practical action.

Correlation usually measures statistical dependence between numerical variables, often focusing on the strength and direction of a relationship. Association rules discover co-occurrence relationships among categorical or transactional items.

A high-confidence rule does not automatically imply usefulness because:

• The consequent may be extremely common in the whole data set.
• Confidence does not account for the baseline probability of the consequent.
• A rule can have high confidence but low support, making it unreliable or applicable to very few transactions.
• Co-occurrence does not prove causation.
• The relationship may be caused by seasonality, promotions, or customer subgroups.
• The rule may not provide an actionable or profitable business decision.

Lift helps address the baseline issue:

A lift near suggests that and occur independently, while a lift greater than indicates positive association. Support, confidence, lift, statistical validation, and domain knowledge should be considered together.

In hierarchical clustering, the dendrogram contains a complete sequence of merges. The selected number of clusters depends on where the dendrogram is cut.

Effect of the number of clusters:

• A low cut produces a small number of broad groups.
• A high cut produces more detailed subgroups.
• Cutting at a large vertical gap often gives clusters with relatively strong separation.
• The selected level should be supported by validation measures and domain knowledge.

Effect of linkage:

• Single linkage tends to connect observations through chains.
• Complete linkage favors compact and separated groups.
• Average linkage balances all pairwise distances.
• Centroid linkage focuses on the distance between group centers.

Consequently, the same data may produce different dendrogram structures under different linkage methods. Analysts should compare methods, inspect cluster sizes and profiles, and assess whether the resulting groups are meaningful and stable.