You are given one-dimensional sorted data points. Write a program to cluster these points into two clusters such that the WCSS (Within-Cluster Squared Sum) metric is minimized. O(n^2) solution is acceptable for this problem.

Note : Ensure the clustering results exhibit repeatability, meaning that if the program is executed multiple times, all the data points within a cluster will always remain in the same cluster. Additionally, guarantee optimality in the clustering results. These characteristics are not ensured in the standard K-Means algorithm, where cluster assignments can vary with each execution.

Example 1 : [1, 5, 7, 8, 15, 29, 100] will be clustered into
cluster 1 : [1, 5, 7, 8, 15]
cluster 2 : [29, 100]
Inputs

• x : sorted list of data points
• K = 2, divide into 2 clusters

Output

• Two lists
  • cluster 1 : All the data points in cluster 1
  • Cluster 2 : All the data points in cluster 2
• Min value of WCSS

Solution

---

We are given a sorted array of points and want to divide it into two clusters. For every index p (partition point), we split the array into:

• Left Cluster : points[0:p+1]
  This cluster contains points from the start of the array to the partition point p.

• Right Cluster : points[p+1:n]
  This cluster contains points from p+1 to the end of the array.

For each split, compute the Within-Cluster Squared Sum (WCSS) for the left and right clusters and keep track of the partition that gives the minimum total WCSS.

WCSS Calculation:

For a cluster with points x_1, x_2, . . x_m :

• Compute the mean of the cluster:

  $$ \text{mean} = \frac{\sum_{i=1}^{m} x_i}{m} $$

• Compute the WCSS:

  $$ WCSS = \sum_{i=1}^{m} (x_i - \text{mean})^2 $$

This metric measures the sum of squared deviations of points from their cluster mean.

Algorithm Steps:

1. Try Every Partition Point: Loop through every possible partition point p from 0 to n-2.
2. Compute WCSS for Each Split:
   • For the left cluster points[0:p+1], compute its mean and WCSS.
   • For the right cluster points[p+1:n], compute its mean and WCSS.
3. Track the Minimum: Keep track of the partition point p that gives the lowest total WCSS.
4. Return Clusters: Use the best partition point to form the two clusters.

Time Complexity :

---

• WCSS Calculation:
  Computing WCSS for a cluster of size m takes O(m).

• Partitioning:
  For n points, we try n-1 partitions. For each partition, WCSS is computed for two clusters, taking O(n) work.

• Total Complexity:
  The total complexity is O(n^2).

Python Code:

import numpy as np
class Solution:

    def calculate_wcss(self, points):
        """Calculate WCSS for a given cluster of points."""
        mean = np.mean(points)
        return sum((x - mean) ** 2 for x in points)

    def two_cluster_partition(self, points):
        """Find the optimal partition for two clusters using O(n^2) solution."""
        n = len(points)
        
        
        min_wcss = float('inf')
        best_partition = -1

        # Try every partition point
        for p in range(n - 1):
            # Left and right clusters
            left_cluster = points[:p + 1]
            right_cluster = points[p + 1:]

            # Compute WCSS for both clusters
            wcss_left = self.calculate_wcss(left_cluster)
            wcss_right = self.calculate_wcss(right_cluster)
            total_wcss = wcss_left + wcss_right

            # Update the minimum WCSS and partition
            if total_wcss < min_wcss:
                min_wcss = total_wcss
                best_partition = p

        # Form the clusters
        cluster1 = points[:best_partition + 1]
        cluster2 = points[best_partition + 1:]

        return min_wcss, [cluster1, cluster2]