Can missing values linked with outcome variable be a source of bias in machine learning

Question

Background: In a binary classification problem (healthy vs. patients), I have a relatively small sample size (40 patients and 40 healthy subjects). I can include some additional subjects in both the groups but some of the features might be missing in these additional subjects. The missing values are not randomly distributed; the patient group, in general, tends to have more missing values than healthy subjects on an average. One of my professors suggested using boosted trees (xgboost) or other decision trees methods (random forest) as they can handle missing data and therefore my overall sample size would increase.

My concern with this is that the classifier might end up learning this bias of more missing values in the patient group. I have not seen any discussions on whether these tree methods can learn missing values as a "feature" itself. Perhaps I am missing some keywords? My intuition would be to avoid any systematic difference between the groups (which is not related to healthy/patient labels) out of the picture.

Additional information: My features come from multiple kinds of tests/assessments that individuals go through. Each test would give me ~50-80 features and there are 5 tests. The missing information arises from the fact that patients may not cooperate for one or two of these 5 tests. The probability of the label being a patient if the data of one or two tests are missing is quite high.

Question: Can tree-based methods (or other ML methods in general) learn these kinds of systematic differences or are my concerns trivial? Are there ways to deal with these (except for not considering those subjects who have missing data)?

Answer 1

Your concern is warranted. XGBoost treats missing values by first splitting the feature without considering missings, then sending the missings down whichever path is more appropriate. So it very likely will end up learning the predictiveness of your missing tests.

Not all tree models work this way. See:
How do decision tree learning algorithms deal with missing values (under the hood)
Meaning of Surrogate Split
In particular, using C4.5 with its approach of splitting rows missing the feature across both children with appropriate weights should work quite well.

Otherwise, you'll need to either drop or impute. Imputation should also be done with care: simply imputing the mean will still allow a tree to isolate that value. Something based on other features (including @EdM's suggestion for multiple imputation, but also e.g. KNN imputation) will reduce that effect.