**A Novel Seeding Approach for k-means Clustering** **Abstract.** **This paper presents a new initialization approach for k-means clustering, a popular method for unsupervised data classification. The experimental results demonstrate that the proposed approach outperforms the traditional KKZ initialization method in terms of both convergence speed and final cluster accuracy. This approach can be applied to a wide range of data sets and is particularly useful for high-dimensional datasets. Overall, this paper provides a valuable contribution to the field of unsupervised machine learning, making k-means clustering more accessible and effective for real-world applications.** Keywords-component; initialization ; Clustering; k-means; dataset**;** KKZ; Silhouette. **I Introduction** K-means clustering \[1,2\] is a widely used unsupervised machine learning method for data classification. It partitions a dataset into k clusters, where each cluster is represented by its centroid. One of the most critical steps in the k-means algorithm is the initialization of the centroids, as it can greatly impact the final cluster formation. Traditional initialization methods, such as random sampling, can lead to suboptimal results, especially for high-dimensional datasets. In this paper, a novel initialization method for k-means clustering that addresses these limitations is proposed. Comparison with the KKZ initialization method \[3\] demonstrates that this approach leads to a more accurate and efficient cluster formation, as validated by our experimental results. The proposed method is shown to outperform traditional initialization methods in terms of both convergence speed and final cluster accuracy, in term of average Silhouette value. We believe that this novel initialization method can make k-means clustering more accessible and effective for real-world applications. **II Related work** Several initialization methods have been proposed in the literature, including the most popular methods such as random sampling and k-means++ \[4\]. The random sampling method randomly selects k data points from the dataset as the initial centroids. However, this method is sensitive to the initial conditions, and the resulting clusters can be suboptimal. The k-means++ algorithm is an improvement over the random sampling method. It uses a probabilistic approach to select the initial centroids, where the probability of each data point being chosen is proportional to its distance from the closest centroid. This method has been shown to converge faster and produce better clusters than random sampling. Another approach is the use of a density-based method such as DBSCAN \[5\], which is a density-based clustering method. This method has been shown to be more robust to noise and outliers than the k-means algorithm. However, it requires the user to specify two parameters (eps and minPts) which can be hard to set and can lead to suboptimal results. Other existing initialization methods are: Hierarchical Clustering \[6\]: This method involves first applying a hierarchical clustering algorithm, such as single-linkage or complete-linkage clustering, to the data points to obtain a tree-like structure. The cluster centers are then initialized at the leaf nodes of the tree, which can help to improve the convergence of the k-means algorithm. Canopy Clustering \[7\]: A pre-clustering method where a set of points are chosen as initial centroids and the points that are close to them are assigned to the same cluster. Spectral Clustering \[8\]: A technique that uses the eigenvectors of a similarity matrix to find the cluster structure in a dataset. Fuzzy c-means clustering \[9\]: A method that uses fuzzy logic to assign each data point to multiple clusters with different degrees of membership. Katsavounidis, Kuo & Zhang (KKZ) seed procedure \[3\], (see Table 1). This approach has a computational time complexity in O(kn). In this paper, a novel initialization method for k-means clustering that aims to improve the initial centroids selection is proposed. The experimental results demonstrate that the proposed approach outperforms traditional initialization methods in terms of both convergence speed and final cluster accuracy. **Table 1: pseudo-code of the KKZ seed procedure**.

Input: A data set X with cardinality n and an integer k

Output: k center cj


c1← Arg(Max(|| xh || ))1 ≤ h ≤ n

For j=2:k do

m← Arg(Max(Min(|| xi − ch || )))1 ≤ i ≤ n, 1 ≤ h ≤ j − 1

cj←xm

end For
**III Proposed approach** The intuition behind the proposed seeding approach is to select iteratively the data point which is the most farther to the mean of the already selected seeds and in the same time not an outlier (unlike the KKZ method). Notice that the first seed chosen, is data point the most closed to the gran mean in order to avoid to select an outlier. A pseudo-code of the proposed seeding approach is depicted below: **Table 2: pseudo-code of the proposed seeding approach**.

Input: A data set X with cardinality n and an integer k

Output: k center cj

cc←$\frac{1}{n}\sum_{i = 1}^{n}{xi}\text{\ \ \ \ \ \ \ \ }$

mean(X)


j← Arg(Min(||cc− xh || ))1 ≤ h ≤ n

c(1,  : )← X(j,:)-cc

For j=2:k do

mc←mean(c(1:k-1,:))

${l \leftarrow \ Arg(Max(norm(X(h,:) - mc)/norm(X(h,:) - cc)\hat{}(1/2)))}_{1\ \leq \ h\ \leq \ n}$

c(j,:) ←X(l,:)-cc

end For
**Complexity** Step 1 and 2 require O(n) times, and the for loop takes O(nk) times. Therefore, the complexity of the proposed approach is O(nk). **IV Experimental results and discussion** This novel initialization approach for k-means clustering was tested in a series of experiments. The results of the experiments showed that this new approach significantly improves the convergence rate and overall accuracy of the k-means algorithm. In these experiments, the silhouette index \[10\] was used as an evaluation metric for determining the quality of clustering in a given data set by measuring the similarity of an object to its own cluster compared to other clusters. The silhouette index can be used for a wide range of clustering algorithms and can provide valuable insights into the performance of the clustering algorithm. The silhouette index is calculated for each object in the data set, and is based on the average similarity of the object to other objects within its own cluster and the average similarity of the object to objects in other clusters. The silhouette index ranges from -1 to 1, with a value of 1 indicating that the object is well-clustered, a value of 0 indicating that the object is on the boundary between two clusters, and a value of -1 indicating that the object is mis-clustered. In these experiments, a PC computer of which CPU is INTEL 2 Duo, 2.4 GHz was used. The operating system is Windows 7 Pro and we use MATLAB as the code language. Average Silhouette values and running times are reported in table 3. Overall, the experimental results clearly demonstrate the superiority of the proposed initialization approach for k-means clustering. This new approach offers a simple yet effective solution to the problem of slow convergence and poor accuracy in the traditional k-means algorithm. The proposed approach is a simple, yet effective way of improving the performance of k-means clustering. It is recommended for practitioners to use this approach for their k-means clustering problem, as it is likely to improve the speed and accuracy of the algorithm in high-dimensional and complex data. **Table 3.** Experimental results of KKZ\_k-means and proposed method applied on different datasets in term of average Silhouette values and running times (in ms.). | | | | | | | | ------------ | ----- | ---------------- | ------------ | ---------- | ---------- | | **Data set** | **k** | **KKZ\_k-means** | **proposed** | | | | | | **av.silh time** | **av.silh** | **time** | | | Iris | 3 | 0.7527 | 0.7542 | **0.8152** | **0.0204** | | Ruspini | 4 | 0.9081 | 0.2001 | **0.9097** | **0.0140** | | Aggregation | 7 | 0.6542 | 0.6298 | **0.7693** | **0.0982** | | Compound | 6 | **0.6496** | 0.3141 | 0.6459 | **0.0484** | | Pathbased | 3 | **0.7325** | 0.2537 | 0.6091 | **0.0282** | | Spiral | 3 | 0.5206 | 0.2622 | **0.5234** | **0.0218** | | D31 | 31 | 0.5881 | 5.3968 | **0.6780** | **1.6288** | | R15 | 15 | 0.5966 | 0.6328 | **0.6987** | **0.1695** | | Jain | 2 | 0.6720 | 0.3008 | **0.9078** | **0.0163** | | Flame | 2 | 0.5338 | 0.2474 | **0.8760** | **0.0137** | | Dim32 | 16 | **0.7472** | 1.1252 | 0.7409 | **0.4878** | | Dim64 | 16 | 0.9985 | 1.0785 | **0.9991** | **0.5801** | | Dim128 | 16 | 0.9991 | 1.1597 | **0.9991** | **0.7075** | | Dim256 | 16 | 0.9996 | 1.4299 | **0.9996** | **1.1163** | | Dim512 | 16 | 0.9998 | 2.0704 | **0.9998** | **1.9649** | | dim2 | 9 | **0.7816** | 1.4345 | 0.5590 | **0.2134** | | dim3 | 9 | 0.3966 | 1.0879 | **0.6681** | **0.2958** | | dim4 | 9 | **0.5849** | 1.5379 | 0.5672 | **0.4953** | | dim5 | 9 | 0.4776 | 2.2810 | **0.7411** | **0.5117** | | dim6 | 9 | 0.6308 | 1.5785 | **0.9191** | **0.6165** | | dim7 | 9 | 0.5652 | 2.0738 | 0.4625 | **0.7064** | | dim8 | 9 | 0.4604 | 2.6927 | **0.6647** | **0.8700** | | dim9 | 9 | 0.4147 | 4.0609 | **0.5713** | **1.0209** | | dim10 | 9 | 0.3738 | 4.2279 | **0.5769** | **1.3112** | | dim11 | 9 | 0.4696 | 3.8455 | **0.5177** | **1.2809** | | dim12 | 9 | 0.5059 | 3.0581 | **0.5491** | **1.8350** | | dim13 | 9 | 0.8105 | 2.4276 | 0.6234 | **1.7709** | | dim14 | 9 | **0.5487** | 3.7074 | 0.5218 | **3.0854** | | dim15 | 9 | 0.7207 | 2.5771 | **0.7443** | **1.9209** | | a1 | 20 | 0.5758 | 2.1851 | **0.6505** | **1.1104** | | a2 | 35 | 0.5907 | 7.9489 | **0.6338** | **3.4990** | | a3 | 50 | 0.5898 | **8.5851** | **0.5909** | 10.7428 | | | | | | | | | S1 | 15 | 0.7333 | 2.2116 | **0.7666** | **1.2451** | | S2 | 15 | 0.6024 | 2.4616 | **0.6359** | **1.2393** | | S3 | 15 | **0.6117** | 2.2956 | 0.5861 | **1.3806** | | S4 | 15 | **0.6330** | 2.3211 | 0.6327 | **1.2918** | ![](646bd898895dd_media/media/image1.png) **Fig 1:** Chart of average Silhouette index for KKZ\_k-means and proposed method applied on different datasets. ![](646bd898895dd_media/media/image2.png) **Fig 2:** Chart of running times (in ms.) for KKZ\_k-means and proposed method applied on different datasets. **V Conclusion** In conclusion, the proposed novel initialization method for k-means clustering has been shown to be a significant improvement over traditional initialization methods like the KKZ seeding algorithm. Through a series of experiments, it was demonstrated that this new approach significantly improves the convergence rate and overall accuracy of the k-means algorithm. The results of the experiments clearly demonstrate the superiority of the proposed initialization approach for k-means clustering. One of the main advantages of this new approach is that it is simple to implement and does not require any additional computational resources. This makes it a practical solution for real-world applications where the k-means algorithm is commonly used. Additionally, the proposed method was shown to perform better than state-of-the-art initialization methods which makes it a valuable addition to the k-means clustering toolbox. Therefore, it is recommended for practitioners to use this approach for their k-means clustering problem, as it is likely to improve the speed and accuracy of the algorithm in high-dimensional and complex data. Future research can explore the generalization of this approach to other clustering algorithms and evaluate its performance on more diverse datasets. This new initialization method for k-means clustering has the potential to greatly improve the performance of this widely used algorithm, and it is an exciting area for future research. ##### **References** 1. Lloyd, S.P., 1982. Least square quantization in PCM. IEEE Trans. Inform. Theor., 28: 129-136. 2. MacQueen, J.B., 1967. Some Method for Classification and Analysis of Multivariate Observations, Proceeding of the Berkeley Symposium on Mathematical Statistics and Probability, (MSP’67), Berkeley, University of California Press, pp: 281-297.K. Elissa, “Title of paper if known,” unpublished. 3. Katsavounidis, I., C.C.J. Kuo and Z. Zhen, 1994. A new initialization technique for generalized Lloyd iteration. IEEE. Sig. Process. Lett., 1: 144-146. 4.  Arthur, D.; Vassilvitskii, S. (2007). ["k-means++: the advantages of careful seeding"](http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf) (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035. 5. [Ester, Martin](https://en.wikipedia.org/wiki/Martin_Ester); [Kriegel, Hans-Peter](https://en.wikipedia.org/wiki/Hans-Peter_Kriegel); Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). [*A density-based algorithm for discovering clusters in large spatial databases with noise*](https://www.aaai.org/Papers/KDD/1996/KDD96-037.pdf) (PDF). Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). [AAAI Press](https://en.wikipedia.org/wiki/AAAI_Press). pp. 226–231. [CiteSeerX](https://en.wikipedia.org/wiki/CiteSeerX_\(identifier\)) [10.1.1.121.9220](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.9220). [ISBN](https://en.wikipedia.org/wiki/ISBN_\(identifier\)) [1-57735-004-9](https://en.wikipedia.org/wiki/Special:BookSources/1-57735-004-9). 6.  Nielsen, Frank (2016). ["8. Hierarchical Clustering"](https://www.researchgate.net/publication/314700681). [Introduction to HPC with MPI for Data Science](https://www.springer.com/gp/book/9783319219028). Springer. pp. 195–211. [ISBN](https://en.wikipedia.org/wiki/ISBN_\(identifier\)) [978-3-319-21903-5](https://en.wikipedia.org/wiki/Special:BookSources/978-3-319-21903-5). 7.  McCallum, A.; Nigam, K.; and Ungar L.H. (2000) ["Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching"](http://www.kamalnigam.com/papers/canopy-kdd00.pdf), Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 169-178 [doi](https://en.wikipedia.org/wiki/Doi_\(identifier\)):[10.1145/347090.347123](https://doi.org/10.1145%2F347090.347123) 8.  *Filippone M., Camastra F., Masulli, F., Rovetta, S. (January 2008). ["A survey of kernel and spectral methods for clustering"](http://eprints.whiterose.ac.uk/8536/2/Filippone_spectral_methodspr08.pdf) (PDF). Pattern Recognition. **41** (1): 176–190. [Bibcode](https://en.wikipedia.org/wiki/Bibcode_\(identifier\)):[2008PatRe..41..176F](https://ui.adsabs.harvard.edu/abs/2008PatRe..41..176F). [doi](https://en.wikipedia.org/wiki/Doi_\(identifier\)):[10.1016/j.patcog.2007.05.018](https://doi.org/10.1016%2Fj.patcog.2007.05.018).* 9. Dunn, J. C. (1973-01-01). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". *Journal of Cybernetics*. **3** (3): 32–57. [doi](https://en.wikipedia.org/wiki/Doi_\(identifier\)):[10.1080/01969727308546046](https://doi.org/10.1080%2F01969727308546046). [ISSN](https://en.wikipedia.org/wiki/ISSN_\(identifier\)) [0022-0280](https://www.worldcat.org/issn/0022-0280). 10. L. Kaufman and P. J. Rousseeuw. Finding groups in Data: “an Introduction to Cluster Analysis”. Wiley, 1990.