SOKNL: A novel way of integrating K-nearest neighbours with adaptive random forest regression for data streams

Most research in machine learning for data streams has focused on classification algorithms, whereas regression methods have received a lot less attention. This paper proposes Self-Optimising K-Nearest Leaves (SOKNL), a novel forest-based algorithm for streaming regression problems. Specifically, the Adaptive Random Forest Regression, a state-of-the-art online regression algorithm is extended like this: in each leaf, a representative data point - also called centroid - is generated by compressing the information from all instances in that leaf. During the prediction step, instead of letting all trees in the forest participate, the distances between the input instance and all centroids from relevant leaves are calculated, only k trees that possess the smallest distances are utilised for the prediction. Furthermore, we simplify the algorithm by introducing a mechanism for tuning the k values, which is dynamically and automatically optimised based on historical information. This new algorithm produces promising predictive results and achieves a superior ranking according to statistical testing when compared with several standard stream regression methods over typical benchmark datasets. This improvement incurs only a small increase in runtime and memory consumption over the basic Adaptive Random Forest Regressor.

Automated summary

Most research in machine learning for data streams has focused on classification algorithms, with less attention on regression methods. This paper presents a novel forest-based algorithm, called Self-Optimising K-Nearest Leaves (SOKNL), for streaming regression problems. The algorithm extends the Adaptive Random Forest Regression, by generating representative data points (centroids) in each leaf and utilizing only the k trees with the smallest distances for prediction. The algorithm also introduces a mechanism for tuning the k values based on historical information. Experimental results show that the proposed algorithm outperforms standard stream regression methods.