Unsupervised K-Means Clustering Algorithm

### Describe the workflow you want to enable

"the k-means algorithm and its extensions are always influenced by initializations with a necessary number of clusters a priori. That is, the k-means algorithm is not exactly an unsupervised clustering method. In this paper, we construct an unsupervised learning schema for the k-means algorithm so that it is free of initializations without parameter selection and can also simultaneously find an optimal number of clusters." from the abstract. 

### Describe your proposed solution

"To construct the k-means clustering algorithm with free of initializations and automatically find the number of clusters, we use the entropy concept. We borrow the idea from the EM algorithm by Yang et al." from section 3 (THE UNSUPERVISED K-MEANS CLUSTERING ALGORITHM).

### Describe alternatives you've considered, if relevant

R-EM, C-FS, X-Means, and RL-FCM

### Additional context

https://ieeexplore.ieee.org/document/9072123

309 citations (according to Google Scholar, not sure why IEEE shows a different number), released in 20 April 2020. I think there are up to 5 parameters "γ, β, c, a K, a K,"  might be wrong.

The total computational complexity for the U-k-means algorithm is O(ncd), where n is the number of data points, c is the number of clusters, and d is the dimension of data points.

Name of the authors: Kristina P. Sinaga, Miin-Shen Yang

COMMENT:
> Would love to pick this up if no one is working on this.

@MrinalTyagi 

I converted the authors MATLAB code to Python using Copilot
```
# load dataset
iris = datasets.load_iris()

# define input data
points = iris.data
y = iris.target
label = y

# define parameters
thres = 0.1
beta = 1
gamma = 1
rate = 0

# initializations
cluster_n = points.shape[0]
clust_cen = points + 0.0001
alpha = np.ones((1, cluster_n)) * 1 / cluster_n
err = 10

t_max = 100

c_history = []

while cluster_n > 1 and err >= thres:
    rate = rate + 1

    # Step 2: Compute membership
    u = np.zeros((points.shape[0], cluster_n))
    D7 = []
    for k in range(cluster_n):
        D1 = np.subtract(points, clust_cen[k, :])
        D2 = np.power(D1, 2)
        D3 = np.sum(D2, 1)
        D4 = D3
        D5 = gamma * math.log(alpha[0, k])
        D6 = np.subtract(D4, D5)
        D7 = np.concatenate((D7, D6), axis=1)

    if rate == 1:
        D8 = D7
        np.fill_diagonal(D7, np.nan)
        val, idx = np.nanmin(D7, axis=1)
        np.fill_diagonal(D7, np.diag(D8))
    else:
        val, idx = np.min(D7, axis=1)

    for i in range(points.shape[0]):
        u[i, idx[i]] = 1
    u

    # Step 3: Compute gamma
    gamma = math.exp(-cluster_n / 450)

    # Step 4: Update alpha
    new_alpha = np.zeros((1, cluster_n))
    for k in range(cluster_n):
        temp1 = np.power(u[:, k], beta)
        temp2 = np.sum(temp1)
        temp3 = temp2 / points.shape[0]
        new_alpha[0, k] = temp3

    # Step 5: Update beta
    eta = 1 / points.shape[0]
    temp9 = 0
    for k in range(cluster_n):
        temp8 = math.exp(-eta * points.shape[0] * abs(new_alpha[0, k] - alpha[0, k]))
        temp9 = temp9 + temp8
    temp9 = temp9 / cluster_n
    temp10 = 1 - max(np.sum(u, 1) / points.shape[0])
    temp11 = sum(alpha[0, :] * np.log(alpha[0, :]))
    temp12 = temp10 / (-max(alpha[0, :]) * temp11)

    new_beta = min(temp9, temp12)

    # Step 6: Update number of clusters
    index = np.where(new_alpha <= 1 / points.shape[0])

    # ADJUST ALPHA
    adj_alpha = new_alpha
    adj_alpha = np.delete(adj_alpha, index)
    adj_alpha = adj_alpha / sum(adj_alpha)
    new_alpha = adj_alpha
    if new_alpha.shape[1] == 1:
        new_alpha = alpha
        break

    # Update NUMBER OF CLUSTER
    new_cluster_n = new_alpha.shape[1]

    # ADJUST MEMBERSHIP(U)
    adj_u = u
    adj_u = np.delete(adj_u, index, 1)
    adj_u = adj_u / np.sum(adj_u, 1)[:, None]
    adj_u[np.isnan(adj_u)] = 0
    new_u = adj_u

    if rate >= 60 and new_cluster_n - cluster_n == 0:
        new_beta = 0

    # Update Cluster Centers
    new_clust_cen = []
    for k in range(new_cluster_n):
        temp4 = np.zeros((1, points.shape[1]))
        temp5 = 0
        for i in range(points.shape[0]):
            temp4 = temp4 + new_u[i, k] * points[i, :]
            temp5 = temp5 + new_u[i, k]
        new_clust_cen = np.concatenate((new_clust_cen, temp4 / temp5), axis=0)

    new_clust_cen[np.isnan(new_clust_cen)] = sum(np.mean(points))

    # STEP 8: Convergence criteria
    error = []
    for k in range(new_cluster_n):
        error = np.concatenate((error, np.linalg.norm(new_clust_cen[k, :] - clust_cen[k, :])))

    err = max(error)

    clust_cen = new_clust_cen
    cluster_n = new_cluster_n
    alpha = new_alpha
    beta = new_beta
    u = new_u
    c_history = np.concatenate((c_history, cluster_n))

# Step 9: Cluster labeling
clust = []
for i in range(points.shape[0]):
    clust = np.concatenate((clust, idx[i]))
```

Labels: New Feature, module:cluster, Needs Decision - Include Feature