# Privacy-Preserving Data Mining on Blockchain-Based WSNs
## 4 Methodology
### Distributed Data Mining
#### 4.3.3 Distributed Data Mining Algorithm  
Due to the context of distributed data, where only limited local data is available for processing, we cannot run the same algorithms as in Section 4.2. Instead, we look at the Hoeffding tree [46], a very fast decision tree algorithm proposed for stream data. The algorithm builds a decision tree as data arrives, without the need to reuse instances from already-processed data. This is achieved by maintaining the statistics needed for splitting attributes in each leaf node and determining when a split should occur as data arrives, using the Hoeffding's bound [47]. The Hoeffding probability bound enables us to compute \(\varepsilon\), which can be used as a confidence interval for the estimation of the split. Figure 4: Incremental learning with Hoeffding trees. Figure 3: Data partitioning according to the round-robin method. \(R\) is the range of the random variable \(r\). By performing \(N\)-independent observations of the variable \(r\), and computing their mean \(\overline{r}\), the Hoeffding bound enables us to state with confidence \(1-\delta\) that \(\overline{r}\) is within \(\varepsilon\) distance from the true mean of the variable \(r\). In [46], it was shown that the Hoeffding tree output is asymptotically nearly identical to that of a traditional batch learner in infinitely many examples. We use the Python implementation provided in the scikit-multiflow [48] library, specifically, the regression variant named _HoeffdingTreeRegressor_. Development of the scikit-multiflow library stopped in the year 2020, when the developers of scikit-multiflow and Creme [49], another Python library for data stream mining, decided to merge their efforts and release a new library named River [50]. Even though the state of the art of data stream mining is currently implemented in the River library, we decided to employ the _HoeffdingTreeRegressor_ implemented in the scikit-multiflow since this implementation allowed us to control the tree size in bytes. The _HoeffdingTreeRegressor_ algorithm at the base of the implementation in River is identical to the one in scikit-multiflow. The algorithm is based on the Fast and Incremental Model Trees (FIMT-DD) method described in [51], without concept drift adaptation. The pseudo-code is given in Algorithm 1. From the code, it is possible to notice that the algorithm starts with an empty tree that keeps statistics at the leaves from arriving data. Each time \(k\) values arrive at a leaf, the algorithm finds the best split for each attribute and ranks the attributes according to the standard deviation reduction (SDR) measure [51]. Therefore, attributes are ranked such that the standard deviation is maximally reduced, if splitting by the highest ranked attribute, by considering the ratio of the SDR values between any of the attributes and the highest-ranked attribute as the random variable \(r\) with range \(R\in[0,1]\). If the inequality \(\overline{r}+\varepsilon<1\) holds, then the highest-ranked attribute is the best split over the whole distribution for that portion of data. ```
1 Begin with an empty leaf (root)
2 repeat
3 Read the next example;
4 Traverse the example to a leaf;
5 Update statistics in the leaf;
6 ifk examples were readthen
7 Find best split per attribute;
8 Rank attributes using the SDR measure;
9 ifsplitting criterion is satisfiedthen
10 Make a split on the best attribute;
11 make two new branches leading to (empty) leaves;
12
13 end if
14
15 end if
16
17 untilEnd of the stream;
```  
**Algorithm 1**Pseudo-code of the _HoeffdingTreeRegressor_. We ran the ML algorithm with the sample average leaf predictor for the following maximal model sizes: \(M=\{5k,10k,25k,50k,100k,250k,500k,1M,2.5M,5M\}\) (bytes). In the provided code snippet (Listing 1), the MAX_TREE_SIZE parameter on line 8 corresponds to one of the values of \(M\). The algorithm was run on the partitioned pre-processed GAMS IAQ dataset.