## 3 The Proposed HSDW-MI Algorithm
### Two Phases of the HSDW-MI Algorithm
#### 3.2.1 Hybrid Sampling Phase of HSDW-MI Algorithm
If the number of samples of the minority class is lower than the number of samples to be sampled, the samples of the current class are extracted from the sample storage pool and added to the data chunk, and then the over-sampling phase is performed. As a result, the balanced data chunk is obtained and the original data distribution is well maintained. The hybrid sampling phase of the HSDW-MI algorithm determines the number of each class to be sampled based on the class ratio and uses adaptive spectral clustering to cluster each class and then sample it, which can better maintain the original data distribution. Meanwhile, sampling based on sample safety factor can retain samples with high safety factor, thus helping the classifier to better identify minority and majority classes. In addition, setting the sample storage pool to store samples with high safety factor and updating them continuously during the training process allows the algorithm to adapt to extremely imbalanced data streams and data streams with variable class proportions. The pseudo-code of the hybrid sampling phase of the HSDW-MI algorithm is shown in Algorithm 1. ```
Input: Data stream \(S=\{D_{1},\ldots,D_{l-1},D_{l}\}\), Data chunk \(D_{l}=<x_{i}\), \(y_{i}>\), Data chunk \(D_{l}\) size \(d\), Sample storage pool \(SP\), The number of neighbors \(k=7\); Output: Balanced Balanced data chunks \(\left\{D_{1}^{\prime},\ldots,D_{t-1}^{\prime},D_{t}^{\prime}\right\}\)
1 Initialize sample storage pool \(SP\leftarrow\varnothing\)
2 for\(D_{l}\) in \(S\)
3 According to \(D_{l}\) to obtain the number of classes \(m\), the ratio of classes \(\frac{1}{m}\) and the number of samples of each class;
4 Calculate the size of the sample storage pool \(SP\) according to Equation (7) \(d_{sp}\);
5 for\(i\)\(\leftarrow\)1 to \(m\) do
6 Calculate \(n_{c_{i}}^{\prime}\), which is the number of classes \(c_{i}\) to be sampled, according to Equation (1);
7 Initialize \(s_{max}\) and \(p_{best}\);
8 for\(p\)\(\leftarrow\)2 to 10 do
9 Calculate the Calinski-Harbasz index \(s\) for class \(c_{i}\) at cluster \(p\) according to Equation (2);
10 if\(s>s_{max}\)
11 \(s_{max}=s\);
12 \(p_{best}=p\);
13 End if
14 End for
15 Dividing class \(c_{i}\) into \(p_{best}\) clusters by adaptive spectral clustering;
16 for\(p\)\(\leftarrow\)2 to \(p_{best}\) do
17 Calculate the number of \(n_{p}^{\prime}\) to be sampled for each cluster in class \(c_{i}\) according to Equation (3);
18 for each sample \(x_{j}\) in cluster \(p\)
19 Find the \(k\) samples which are near to sample \(x_{j}\) by using \(k\)-NN;
20 Calculate the safety factor of sample \(x_{j}\) according to Equations (5) and (6);
21 End for
22 Sort each sample in cluster \(p\) in descending order based on the safety factor;
23 if\(\pi_{c_{i}}\) is full
24 Remove \(\frac{n_{c_{i}}^{\prime}}{n_{p}}\) old samples from \(\pi_{c_{i}}\);
25 End if
26 for\(x_{j}\) in cluster \(p\)
27\(\pi_{c_{i}}\leftarrow\pi_{c_{i}}\cup\left\{x_{j}\right\}\);
28 End for
29 if\(n_{p}^{\prime}<0\)
30 Remove the last \(n_{p}^{\prime}\) samples from the cluster \(p\);
31 else
32 if\(n_{p}<n_{p}^{\prime}\)
33 Extract the top \(n_{p}^{\prime}-n_{p}\) samples from \(\pi_{c_{i}}\) and add them to the cluster \(p\);
34 End if
35 Copy the top \(n_{p}^{\prime}\) samples from cluster p and add them to cluster \(p\);
36 End for
37 End for
38 End for
```  
**Algorithm 1**The Hybrid Sampling Phase of HSDW-MI  
Lines 1-4 of Algorithm 1 represent the initialization of the sample storage pool and the acquisition of the initial parameter values of the current data chunk. Lines 5-6 represent the determination of the number of samples to be sampled for the current class based on the class ratio. Lines 7-17 represent the adaptive spectral clustering to find the best number of clusters and calculate the number of samples to be sampled for each cluster. Lines 18-21 represent the calculation of the sample safety factor. Lines 22-28 represent obtaining samples with high safety factor from the clusters and storing them in the sample storage pool.