# How to generate a rule-based system based on binary data?

I have a dataset where each row is a sample and each column is a binary variable. The meaning of $$X_{i, j} = 1$$ is that we've seen feature $$j$$ for sample $$i$$. $$X_{i, j} = 0$$ means that we haven't seen this feature but we might will. We have around $$1000$$ binary variables and around $$200k$$ samples.

The target variable, $$y$$ is categorical.

What I'd like to do is to find subsets of variables that precisely predict some $$y_k$$.

For example, we could find the following rule:

$$\{ v_1: 1, v_8: 1, v_{12}: 0 \} \mapsto y_2$$

In words, If $$v_1$$ and $$v_8$$ was seen but $$v_{12}$$ was not then predict $$y_2$$.

I think precision is important more than recall. That is, it's more important to me not to make a misclassification rather than have a high recall (per rule)

What I have tried:

1. Logistic regression: With this model I was able to rank the features (with clf.coef_ using scikit-learn) but it is still unclear which subset of rules to choose
2. Decision Tree: The idea was to train a DTree and then collect all the paths to the leaves. Each path can be interpreted as a rule. The data is highly imbalance and even though I used different configurations (including class_weight="imbalance") most of the rules included many "not exist" features and fewer "exist" features. Also, many of them suffered from low precision or a very low recall.

What do you think about my current approaches?