# An Optimal and Stable Algorithm for Clustering Numerical Data
## 2 Preliminaries  
### k-Means Clustering Framework  
The traditional k-means algorithm is based on a center-based clustering framework ([PERSON] and [PERSON], 1965) in which objects are partitioned into a cluster according to their distances to the cluster centers. Generally, the objective of k-means is to partition a dataset \(X\) into \(C\) cluster with the number of clusters, \(k\), set as a priori. Let \(X=\{X_{1},X_{2},\ldots,X_{n}\}\) be a set of \(n\) objects and \(X_{i}\) be represented with its attributes as \([x_{i,1},x_{i,2},\ldots,x_{i,m}]\). In addition, let \(Z=\{Z_{1},Z_{2},\ldots,Z_{k}\}\) be a set of \(k\) cluster centers and \(Z_{l}\) be represented with its attributes as \([z_{l,1},z_{l,2},\ldots,z_{l,m}]\). Finally, \(C=\{C_{1},C_{2},\ldots,C_{k}\}\) is a set of \(k\) clusters. Generally, using the k-means framework, \(X\) is partitioned into \(C\) through the following steps:  
Step 1--First, initialize the number of clusters, \(k\).  
Step 2--Randomly select \(Z\) from \(X\) as the center of clusters (better known as centroids).  
Step 3--Assign \(X\) to the closest cluster centroid based on the distance of each \(X\) and \(Z\). The distance is typically calculated using Euclidean distance as Equation (1).  
\[d_{\textit{euc}}(X_{i},Z_{l})=\sqrt{\sum_{j=1}^{m}|x_{ij}-z_{lj}|^{2}} \tag{1}\]  
Step 4--Update the centroids of the newly formed clusters, \(C\), using mean. The updating process is computed as Equation (2).  
\[z_{li}=\frac{\sum_{i=1}^{n}w_{li}x_{i}}{\sum_{i=1}^{n}w_{li}} \tag{2}\]where \(w_{li}\) is \((n\times k)\) matrix satisfying the following Equations (3)-(6),  
\[w_{li}=\begin{cases}1,&ifd_{enc}(X_{i},Z_{l})=min^{d_{enc}(X_{i},Z_{l}),1\leq l \leq k}\\ 0,&Otherwise\end{cases} \tag{3}\]  
\[w_{li}\in\{0,1\},1\leq i\leq n,1\leq l\leq k, \tag{4}\]  
\[\sum_{i=1}^{k}w_{li}=1,1\leq i\leq n, \tag{5}\]  
\[\sum_{i=1}^{n}w_{li}>0,1\leq l\leq k, \tag{6}\]  
Step 5--Repeat Steps 3 and 4 and stop when the process intra- and inter-cluster dissimilarity objective function are minimized. The objective function is computed as in Equation (7)  
\[F(W,D)=\sum_{l=1}^{k}\sum_{i=1}^{n}W_{li}d_{enc}(X_{i},Z_{l}), \tag{7}\]  
For fuzzy approach, the algorithm is called fuzzy c-means algorithm and uses the same framework as above. However, the objective function is minimized as Equation (8),  
\[F(W,D)=\sum_{l=1}^{k}\sum_{i=1}^{n}w_{li}^{\psi}d_{enc}(X_{i},Z_{l}), \tag{8}\]  
which is subject to the following Equations (9)-(11),  
\[w_{li}\in[0,1],1\leq i\leq n,1\leq l\leq k, \tag{9}\]  
\[\sum_{i=1}^{k}w_{li}=1,1\leq i\leq n, \tag{10}\]  
\[\sum_{i=1}^{n}w_{li}>0,1\leq l\leq k, \tag{11}\]  
where \(\psi\in[1,\infty)\) is a weighting exponent that is typically greater than 1.0. The partition matrix, also known as fuzzy membership, \(W\), is updated as Equation (12)  
\[w_{li}=\frac{d_{enc}(X_{i},Z_{l})^{-\frac{1}{\psi-1}}}{\sum_{l=1}^{k}d_{enc}(X_ {i},Z_{l})^{-\frac{1}{\psi-1}}},1\leq l\leq k,1\leq i\leq n \tag{12}\]  
and the centroid of fuzzy c-means is updated as Equation (13)  
\[z_{li}=\frac{\sum_{i=1}^{n}w_{li}^{\psi}x_{i}}{\sum_{i=1}^{n}w_{li}^{\psi}} \tag{13}\]  
The fuzzy c-means algorithm can be formalized in the form of pseudocode as Algorithm 1.  
```
Input: dataset \(X\), number of clusters \(k\), and weighting exponent \(\psi\)

Output: Set of clusters \(C=\{C_{1},C_{2},\ldots,C_{k}\}\)
```
1: Select \(Z_{l}\) randomly from \(X\), where \(1\leq l\leq k\)
2:for each \(Z_{l}\)do
3:for each \(X_{i}\)do
4: Calculate \(F(W,D)\) as Equation (8)
5:if\(F(W,D)\) is minimized then
6: Update \(Z_{l}\) as Equation (13)
7:endif
8:endfor
9:endfor
10: Assign \(X_{i}\) to \(C_{l}\) for all \(l\), \(1\leq l\leq k\) and \(i\), \(1\leq i\leq n\)
11:Output results ```
**Algorithm 1** FUZZY C-MEANS (\(X,k,\psi\)).