Recently, a large amount of work has been done in XML data mining. However, most of the existing work focuses on the snapshot XML data, while XML data is dynamic in practical application. In order to mine knowledge hidden in the frozen structures (FS) which are not changed or very little changed during the historical changing process of an XML document, we present a method for clustering XML documents via FS. Also, a novel algorithm called weighted cosine measure (WCM) improved from the traditional algorithm has been proposed, and using which we can calculate the similarity between two clusters. Otherwise, we propose a method using the agglomerative hierarchical during the cluster process. Experiments results on our new algorithm indicate that the proposed solution performs significantly. XML documents can be effectively clustered and the results of using the WCM are better than using the traditional cosine measure. Then, XML documents in each cluster have similar structures not often changed.