A big homework to merge Lazy Learning and Formal Concept Analysis. Created for the course Ordered Sets in Data Analysis (GitHub repo) taught in Data Science Master programme in HSE University, Moscow.
This homework serves as an entry point for students into the data science world.
So it introduces students to three main topics:
- Typical machine learning project:
The pipeline of loading a dataset, feature engineering, designing a new predictive algorithm, results comparison; - Lazy learning:
Predicting labels for small or rapidly changing data; - Rule-learning (on part with FCA):
Viewing data as binary descriptions of objects (instead of points in a space of real numbers).
- Bare minimum (4 pts.)
- Find a dataset for binary classification:
Ideal dataset would be: openly available, with various datatypes (numbers, categories, graphs, etc), with hundreds of rows; - Describe scaling (binarization) strategy for the dataset features,
- Describe prediction quality measure best suited for the dataset
(e.g. accuracy, f1 score, or any measure that you find reasonable), - Adapt the pipeline from lazyfca.ipynb to your task.
- Find a dataset for binary classification:
- Good solution (5-8 pts.):
- Improve the baseline algorithm:
- Achieve better asymptotic time complexity;
- Improve the runtime of examples comparison:
Rewrite the intersections of sets into the intersection of the corresponding bitmasks. Would it make the algorithm faster?
(numpy, bitarray, and other python packages may be of help); - Modify the algorithm to achieve better quality of predictions.
- Or simply design a new lazy algorithm to beat the baseline
in terms of algorithmic time complexity, runtime, and prediction quality; - Compare the proposed algorithm with popular rule-based models
i.e. decision tree, random forest, XGBoost, CatBoost in terms of runtime and prediction quality.
- Improve the baseline algorithm:
- Perfect solution (9-10 pts.)
- Incorporate pattern structures into the pipeline to avoid the scaling (binarization);
- Test the proposed algorithm on more datasets (at least 3 others)
This homework focuses on the task of binary classification.
That is, we are given the data
To estimate the quality of predictions we split the data
The original data
The following algorithm is used in the homework as a baseline algorithm for lazy FCA-based classification. And it is called "Generators framework".
Assume that we want to make a prediction for description
First, we split all examples
To classify the descriptions
- Count the number of counterexamples for positive examples
For each positive example$x_{pos} \in X_{pos}$ we compute the intersection$x \cap x_{pos}$ . Then, we count the counterexamples for this intersection, that is the number of negative examples$x_{neg} \in X_{neg}$ containing intersection$x \cap x_{pos}$ ; - Dually, count the number of counterexamples for negative examples
For each negative example$x_{neg} \in X_{neg}$ we compute the intersection$x \cap x_{neg}$ . Then, we count the counterexamples for obtained intersection, that is the number of positive examples$x_{pos} \in X_{pos}$ containing intersection$x \cap x_{neg}$ .
Finally, we compare the average number of counterexamples for positive and negative examples.
We classify