# Method of Feature Reduction in Short Text Classification Based on Feature Clustering
## 3 The Proposed Approach
### Two-Stage Feature Clustering
#### 3.2.2 Loose Clustering Based on Graph Depth-First Traversal  
The clustering in the second stage is carried out within each initial feature cluster that was obtained in the first stage. This phase consists of the following steps:  
Step 1. Pairing. In our approach, pairing is the process of connecting any two words whose cosine similarity is higher than the threshold values of 0.35, 0.4, 0.45, 0.5, 0.6, or other values. The similarity is calculated while using the word's 300-dimension vector derived from the Word2 Vec model. The Word2 Vec model is trained by a 5 GB Wikipedia Chinese corpus. For example, the words \"strawberry\" and \"grapes\" have a similarity of 0.46, as calculated from Word2 Vec, so \"strawberry\" and \"grapes\" are paired when the similarity threshold is 0.45. The similarity between \"strawberry\" and \"grapes\" is estimated by calculating the cosine similarity between the vectors that are represented by \(V\) and \(E\); that is, \(\text{sim}\ (V,E)=\text{cosine}\ (V,E)\), defined as follows:  
\[cosine(V,E)=\frac{\sum_{i=1}^{n}\left(v_{i}\times v_{E_{i}}\right)}{\sqrt{\sum _{i=1}^{n}V_{i}^{2}\times\sum_{i=1}^{n}V_{E}^{2}}} \tag{1}\]  
where \(V\) and \(E\) are the vector of length \(n\). Therefore, we declare that, if the cosine similarity of feature word \(V\) and \(E\) exceeds the threshold, then \(V\) and \(E\) are paired. Semantically related words are combined by direct links that are based on a loose clustering strategy. This strategy can intuitively select suitable words to form a similar feature cluster, rather than cluster all of the words together in one. Obviously, not all of the words are suitable for entering a similar feature cluster, because they do not have a high semantic similarity with respect to any other words in the feature word bag. At the same time, it avoids the influence of an improper number of clusters on the clustering results. In addition, this method can cover more effective keywords, because the complex and strict clustering algorithm is not used. Step 2. Building the adjacency list. The feature adjacency list is composed of pairs of feature words with similarities of 0.4, 0.45, 0.5, 0.55, and 0.6, respectively. This structure can also be represented as an undirected linkage graph, which is the basis for determining the final cluster of similar features. Within each initial feature cluster, the feature adjacency list is composed of paired feature pairs. Figure 2 shows the graph of feature pairs with undirected connections. The points in the figure are feature words, the lines between the two points represent the pairing relationship, and the numbers represent the cosine similarity. Since Chinese word vectors are used in this method, English words may not represent the elements in the graph, but it is a word in Chinese. The optimal similarity threshold is determined by the word vector model. The optimal similarity threshold will be different with different word vector models. The results of different similar feature clusters caused by different thresholds will be further described in the following experiments. Step 3. Clustering. Depth-first traversal is performed on the adjacency list that is obtained in Step 2. Each iteration traversal forms a similar feature cluster, and multiple similar feature clusters are then obtained. Note that our traversal does not directly jump to a new node that has not been visited. During each traversal, if all existing nodes have been visited and no new feature pairs are found, the nodes that have been visited will be clustered into a cluster and the next iteration will then begin. Within each initial feature cluster, a similar feature cluster is constructed by traversing the feature adjacency list. Once these clusters are formed, these clusters will be used in text vectorization. This method of feature reduction is driven by the idea that it is not necessary to keep all of the semantically similar features separate.