# K-Means++ Clustering Algorithm in Categorization of Glass Cultural Relics
## 3 K-Means++ Subclass Classification
### K-Means++ Algorithm  
Next, we performed the subclass classification based on high-potassium glass and lead-barium glass. In the absence of a priori knowledge of the subclass classification criteria and no real labels for reference, we first chose to use the unsupervised clustering algorithm K-Means for modeling and analysis, using the three PCs obtained in the PCA section as three feature variables in the clustering. The K-Means algorithm at random uniformly selects K points as the center of mass at initialization, and in each iteration, calculates the distance from each point to the K centers of mass, divides the samples into the clusters corresponding to the closest center of mass, and at the same time, calculates the mean value of all samples within each cluster and updates the center of mass of the cluster using this mean value, until the position change of the center of mass is less than the specified threshold (default 0.0001) or the maximum number of iterations is reached [19; 20; 21; 22]. Because the classification of glass products is not related to weathering, it was necessary to eliminate the influence of weathering on chemical composition and classification and to select the PCA obtained above. The three-factor index was used as the factor parameter of the sample. The weakness of K-Means lies in its initialization. Because the probability of choosing any data point as the center of mass is equal, there is a significant chance that several close points are simultaneously selected as centers, which means that in the later process of iteration, these points are highly likely to be divided into different clusters. However, if two points are close to each other in the context of feature variables, they should be in the same cluster for unsupervised learning. Therefore, we considered improving the initialization strategy and developing K-Means++. Since K-Means is more sensitive to initial values, the algorithm was improved. After setting the probability of each sample point becoming a cluster center to be inversely proportional to the distance from the current cluster center, the more distant the sample point is from the existing cluster center, the more likely it is to be selected as the next cluster center. In the mathematical formulation, we denoted the set of existing cluster centers as S, and the probability of choosing x as the next cluster center is  
\[\mathrm{p(x)}=\frac{\mathrm{min}\mathrm{d}\mathrm{D(x,\,a)}}{ \sum_{\mathrm{x}}\mathrm{min}\mathrm{D(x,\,a)}}\] \[\mathrm{in\,\,which\,\,D(x,a)=\,\,Similarity}_{x,a}\mathrm{2}.\]  
In other words, K-Means++ is most likely to select the point which is far from all the existing cluster centers. In this way, the initialization will guarantee enough divergence (in the sense of distance) among different clusters, which improves the effectiveness of clustering and the convergence rate. The algorithm was tested and found to be significantly less sensitive, so the improved algorithm was named K-Means++. All 67 samples were classified into six classes using the K-Means++ algorithm, and the classification results are shown in Figure 7 and Table 2. By contrast, the classification result of K-Means is shown in Figure 8.  
In order to see the improvement in the sensitivity of K-Means++, we compared K-Means++ with K-Means in the classification results, i.e., we ran both algorithms 1000 times in clustering the 67 samples. Initially, we obtained a result for both algorithms, as shown in Figures 7 and 8. Every time, we got a classification result with six cluster centers, and we recorded the accumulated difference among these six centers from the initial six centers (represented by the absolute difference of center distance). The larger the accumulated difference is, the more volatile the classification is and the more sensitive the algorithm is. From Figure 9, we can see that the accumulated difference of K-Means++ increases more slowly than that of K-Means, which verifies the sensitivity improvement. Figure 8: Three-dimensional K-Means clustering visualization.