## 3 The Proposed HSDW-MI Algorithm
### Two Phases of the HSDW-MI Algorithm
#### 3.2.1 Hybrid Sampling Phase of HSDW-MI Algorithm
\(k\)-NN uses the Euclidean distance as the distance metric between samples, as shown in Equation (4). \[E_{distance}=\sqrt{\sum_{i=1}^{n}\left(a_{i}-b_{i}\right)^{2}} \tag{4}\]  
[PERSON] et al. [30] suggested the application of similarity to extend sample type identification in the study of imbalanced problems, utilizing the safety level factor formula proposed by [PERSON] et al. [31]. This approach achieved improved results in the domain of static imbalanced classification. Consequently, this paper adopts the safety level factor based on the similarity between classes to address multi-class imbalanced data streams. The degree of similarity between classes is presented in Equation (5). \[\mu_{c_{i}c_{j}}=\frac{min\big{(}n_{c_{i}},n_{cj}\big{)}}{max\big{(}n_{c_{i}},n_{ cj}\big{)}} \tag{5}\]  
where \(n_{c_{i}}\) is the number of samples of class \(c_{i}\), \(n_{cj}\) is the number of samples of class \(c_{j}\), and \(\mu_{c_{i}c_{j}}\) is the similarity between class \(c_{i}\) and class \(c_{j}\). This method of calculating the similarity between classes is to better distinguish the minority class from the majority class. If the number of samples between class \(c_{i}\) and class \(c_{j}\) is close, these two classes will be more similar and have less impact on each other. Conversely, the larger the difference in sample size between class \(c_{i}\) and class \(c_{j}\), the lower the similarity between the two classes and majority class will have the more negative effect on the classification of the minority class. The calculation of the sample safety factor based on the level of similarity between classes is shown in Equation (6). \[safe(x_{c_{i}})=\frac{1}{k}\sum_{j=1}^{k}k_{c_{j}}\mu_{c_{i}c_{j}} \tag{6}\]  
where \(x_{c_{i}}\) is a sample of class \(c_{i}\), \(k_{c_{j}}\) is the number of samples from this class \(c_{j}\) in the neighborhood of \(c_{i}\), and \(k\) is the total number of neighbors. Meanwhile, a sample storage pool is introduced to store samples with high safety factors in both minority and majority classes of the data chunk. The selected samples for each class are independently stored within the sample storage pool. When the number of minority class samples in the subsequent data chunk does not reach the required amount for oversampling, the samples of the current minority class, stored from the previous chunk, are extracted from the storage pool and added to the present data chunk for oversampling purposes, catering to extremely imbalanced data streams. Storage pools also store samples of majority classes to address data streams with varying class ratios. In such data streams, majority classes may transition into minority classes as the stream evolves. The samples in the sample storage pool are continuously updated as new chunks arrive, with fresh samples possessing high safety factors replacing the older ones. The sample storage pool should not be excessively large, as this may result in increased memory consumption. In this paper, the size of the sample storage pool is determined based on the chunk size and the number of classes, as illustrated in Equation (7). \[d_{sp}=\frac{d}{c} \tag{7}\]  
where \(d\) is the chunk size, \(c\) is the number of classes, and \(d_{sp}\) is the size of the sample storage pool. In the sample storage pool, each class stores a total of \(n_{c_{i}}^{d_{sp}}=\frac{d_{sp}}{c}\) samples, and the storage space of class \(c_{i}\) is noted as \(\pi_{c_{i}}\). Finally, judge whether the current class is a minority class and sample the clusters of each class based on the adaptive spectral clustering, as well as the sample safety factor. If the current class is majority class, under-sampling is performed, and samples with low safety factor are removed according to each cluster in the current class that needs to be sampled. If the current class is a minority class, oversampling is performed and the samples with high safety factor are copied into the data chunk according to each cluster in the current class.