Подбор важности фич для k-nearest neighbors (ну или других гиперпараметров) спуском похожим на градиентный

Вы практически переизобрели metric learning.
http://contrib.scikit-learn.org/metric-learn/introduction.html

И у дерева и knn есть серьёзное отличие: параметрический или нет, метод.

Входная концепция, масштабировать по важности дерева мне понравилась, не делал так :)