# Practical Challenge of Shredded Documents: Clustering of Chinese Homologous Pieces
## 3 Experimental Results and Discussion
### Summary  
After performing the processing described in Section 3.1 to Section 3.4, the clustering results in the test dataset are obtained, as shown in Table 2. The average accuracy of clustering is 97.19% (449/462), 12 shreds are not classified, and one shred is misclassified. These results show that the clustering method proposed in this paper has a high accuracy and a low error rate. Moreover, for homologous pieces that appear indistinguishable, the method proposed in this paper can fully exploit their internal relationships and differences to achieve effective clustering. Although a shortage of shred processing occurs in area 3 of a document, considering the complexity of real shreds, which are affected by noise interference, information loss, and other factors, the clustering results of Table 2 are satisfactory. Additionally, from the point of view of time complexity, the complexity of our algorithm in various stages is not high, with the exception of the process of Section 2.1. The time consumption of this algorithm is acceptable. The time complexity is \(O(n^{3})\) in Section 2.1 (process of computing the clustering number). Because the training and testing of the classifier for recognizing five different types of blocks in shreds is very time-consuming. The time complexity is \(O(n^{2})\) in Section 2.2 (process of identifying the starting point of clusters). Since the number of shreds that are processed in this stage is substantially less than the total number of shreds, the time consumption in this stage is minimal. The time complexity is \(O(n^{2})\) in Section 2.3 (process of achieving piece clustering based on the regional division). In this stage, the complexity of the piece clustering in area 1 and area 3 is greater than the complexity of the piece clustering in area 2. Figure 24: Results of processing residual sparse pieces. Additionally, to clearly demonstrate the clustering effect of our method, we employ k-means clustering and hierarchical clustering to test the dataset based on the features of the paragraph layout proposed in this paper. We compared the clustering effect of these two methods with the method proposed in this paper. We use the common clustering evaluation indexes--purity and silhouette coefficient--as the standards of evaluation. the expression of purity [7] is expressed as:  
\[P=\frac{1}{n}\sum\limits_{i=1}^{n}\max\limits_{j}\frac{\left|C_{i}\cap K_{j} \right|}{\left|C_{i}\right|}\quad j=1,\cdot\cdot\cdot,m\enspace, \tag{13}\]  
where \(P\) indicates purity, \(n\) indicates the number of clusters, \(m\) indicates the number of predefined classes, \(C_{i}\) indicates the \(i\)-th cluster, and \(K_{j}\) indicates the \(j\)-th class. The expression of silhouette coefficients is expressed as:  
\[S=\frac{1}{m}\sum\limits_{i=1}^{m}\frac{B_{i}-A_{i}}{\max\{A_{i},B_{i}\}}, \tag{14}\]  
where \(S\) indicates Silhouette coefficient, \(m\) indicates the number of clustered pieces, \(A_{i}\) indicates the average dissimilarity of the \(i\)-th piece with all other pieces within the same cluster, \(B_{i}\) indicates the lowest average dissimilarity of the \(i\)-th piece to any other cluster, of which the \(i\)-th piece is not a member. Table 3 shows the clustering effect of different algorithms. The clustering number of k-means clustering is ten. Because the initialization of k-means clustering is random, the purity and silhouette coefficient are the averaging results of 10,000 runs. The clustering number of hierarchical clustering is ten. We use the minimum variance algorithm to create a hierarchical cluster tree in the process of clustering. As shown in Table 3, compared with other two methods, the method proposed in this paper has obvious advantages in terms of the clustering effect. This is because, at the beginning of the clustering, our method can accurately obtain the starting points of clusters (namely the leftmost and the rightmost pieces from the same page), and these starting points can provide clear guidance for the clustering