scikit-learn: machine learning in Python

Aim: Analyzing how the performance of different clustering algorithms for different datasets change on adding noise with different dimensions:

This demo is a Jupyter Notebook documentation describing the effect of the addition of different dimensions of noise on a dataset. Here different types of synthetic datasets are generated on which the experiment is performed. To these datasets Gaussian noise of different dimensions are added, and the performance of each clustering algorithm is measured after noise addition. This is repeated for noise with different variances.

Output: The plots that compare the effect of varying noise dimensions on different clustering algorithms for each of the datasets. In this set of subplots, the variance of the added noise changes along the column and the dataset changes along the row.

Link to the demo: https://nbviewer.jupyter.org/github/sree0917/scikit-learn/blob/master/clustering_comparison_pr.ipynb

It will be a document showing the Effect of Dimensionality Reduction on the accuracy of different classifiers. The document will have simulations On High dimensional dataset of different shapes: Each dataset is synthesized from sklearn established Datasets. Each dataset has 1000 dimensions with only 2 dimensions of data and rest are noise dimensions.

Questions to answer:

Analyzing how dimensionality reduction helps in classification for different classifiers. Analyzing how classifiers perform with a different number of reduced datasets from the main high dimensional dataset. Pipeline to be followed:

Defining a dataset with sklearn established synthetic datasets with High dimensions. Performing classification on data and measuring accuracy for quantification of the process. performing the Dimensionality reduction technique keeping varying numbers of reduced dimensions. Checking the performance of classification again after reducing dimension after each iteration. The output of the PR would be a figure showing different datasets, comparing accuracies of different classifiers with and without dimensionality reduction and a plot showing varying accuracies over reduced dimensions.

Experiments to follow: https://github.com/parimal173/scikit-learn/blob/parimal173-patch-1/Final_50trials_9datasets.ipynb

This is an example of how to get builder to work with the different types of split records.

This is functionally but I do not like the malloc + free in the builder.

All the setup.py language="c++" changes were needed to get the PR to compile on my machine

CC @adam2392

I did not have the rights to directly push to the PR branch.

There is no reason to skip a common test for a new PR, so I removed the new classes from the ignorelist. If common tests fail, they should be fixed.

Co-Authored-By: p-teng [email protected]

Reference Issues/PRs

Fixes: #23

What does this implement/fix? Explain your changes.

Any other comments?

Reference Issues/PRs

Compare TC of OF against RF using bench_tree.py criteria

What does this implement/fix? Explain your changes.

[x] Add a notebook that compares TC of RF and OF varying max_features

Any other comments?

@adam2392 - I've made a separate dev_notebook folder where I placed the notebook

Reference Issues/PRs

N/A

What does this implement/fix? Explain your changes.

• [x] ObliqueRandomForestClassifier() initializes correctly
• [x] ObliqueRandomForestClassifier() can be found in sklearn.ensemble

Any other comments?

@adam2392 -- please review the correction

Reference Issues/PRs

scikit-learn#18888 scikit-learn#18889

What does this implement/fix? Explain your changes.

Add partial_fit function to DecisionTreeClassifier

Any other comments?

It will be a document showing the Effect of Dimensionality Reduction on the accuracy of different classifiers. The document will have simulations On High dimensional dataset of different shapes: Each dataset is synthesized from sklearn established Datasets. Each dataset has 1000 dimensions with only 2 dimensions of data and rest are noise dimensions.

Questions to answer:

Analyzing how dimensionality reduction helps in classification for different classifiers. Analyzing how classifiers perform with a different number of reduced datasets from the main high dimensional dataset. Pipeline to be followed:

Defining a dataset with sklearn established synthetic datasets with High dimensions. Performing classification on data and measuring accuracy for quantification of the process. performing the Dimensionality reduction technique keeping varying numbers of reduced dimensions. Checking the performance of classification again after reducing dimension after each iteration. The output of the PR would be a figure showing different datasets, comparing accuracies of different classifiers with and without dimensionality reduction and a plot showing varying accuracies over reduced dimensions.

Experiments to follow: https://github.com/NeuroDataDesign/team-forbidden-forest/blob/master/Parimal%20Joshi/Final_pr_2.ipynb

Reference Issues/PRs

Fixes: #23

What does this implement/fix? Explain your changes.

This aims to implement the binning capabilities to massively improves the speed of training decision trees. Currently, this is trying to add the binning capabilities that play well with the existing codebase.

Unfortunately, the code from #24 is far from complete and does not do the job.

Right now, what is missing is:

• how to implement binning that is consistent in fitting and predicting (i.e. apply) API
• can we simplify the API?

Any other comments?

Describe the workflow you want to enable

I am part of the @neurodata team. Binning features have resulted in highly efficient and little loss in performance in gradient-boosted trees. This feature should not only be used in gradient-boosted trees, but should be available within all decision trees [1].

By including binning as a feature for decision trees, we would enable massive speedups for decision trees that operate on high-dimensional data (both in features and sample sizes). This would be an additional tradeoff that users can take. The intuition behind binning for decision trees would be exactly that of Gradient Boosted Trees.

Describe your proposed solution

We propose introducing binning to the decision tree classifier and regressor.

An initial PR is proposed here: https://github.com/neurodata/scikit-learn/pull/24#pullrequestreview-1009913319 However, it seems that many of the files were copied and it is not 100% clear if needed. Perhaps we can explore how to consolidate the _binning.py/pyx files using the current versions under ensemble/_hist_gradient_boosting/*.

Changes to the Cython codebase

TBD

Changes to the Python API

The following two parameters would be added to the DecisionTreeClassifier and Regressor:

hist_binning=False,
max_bins=255

where the default number of bins follows that of histgradient boosting.

Additional context

These changes can also trivially be applied to Oblique Trees.

References: [1] https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree

Reference Issues/PRs

What does this implement/fix? Explain your changes.

Add 3 interpretability example notebooks

• [x] Iris notebook
• [x] Simulation notebook
• [x] MNIST notebook

Any other comments?

Reference Issues/PRs

Fixes:

What does this implement/fix? Explain your changes.

Adds cythonized oblique trees to the tree module. This is known as Forest-RC in the Breiman 2001 paper.

• _oblique_tree.pxd/pyx: This file implements i) the ObliqueTree(Tree), which defines a few additional class members for storing the projection weight and indices and a new function for adding and oblique node and then ii) the ObliqueTreeBuilder(TreeBuilder), which defines how to build the oblique tree.
• _oblique_splitter.pxd/pyx: This is the main change, which i) defines an ObliqueSplitRecord for keeping track of oblique splits, and ii) defines an ObliqueSplitter(Splitter) which gets oblique node splits and samples projection matrices, while also storing additional hyperparameters.
• _classes.py: Defines new Python interfaces for the Oblique trees and forests

Any other comments?

I'm not an expert in cython and c++ interplay, but I suspect that if we can "generalize" the Node struct to carry projection vector and weight information (not used in Forest-RI, or axis-aligned Random Forest), then much of the tree, tree building code is not even necessary. The only thing that is different at a fundamental level is the idea of a sample_proj_mat at each node of the tree, which samples sparse combinations.

Another missing component currently is the implementation on sparse data, but this should be easily added in I presume.

Code That Can Be Shortened

New data structures and classes, ObliqueSplitRecord, ObliqueSplitter, ObliqueTree are defined. However, if the existing SplitRecord, Splitter, Tree can be generalized, then the existing functions can just be used to build Oblique Trees too.

However, I'm not sure if the scikit-learn devs would want that, rather then just replicating some code across these two cases?

Describe the workflow you want to enable

Currently, the sklearn.manifold.SpectralEmbedding is restricted to symmetric affinity matrices, and if an asymmetric matrix is passed it is converted through sklearn.utils.validation.check_symmetric into a symmetric matrix. However, in doing so, one loses the underlying asymmetries and potential directional clusters present in the adjacency matrix of the directed graph input.

Describe your proposed solution

The algorithms I propose adding use singular value decomposition, as opposed to eignendecomposition, and a modified Laplacian to perform spectral embedding on directed graphs/asymmetric matrices. Specifically I would like to propose adding Adjacency / Laplacian spectral embedding, ASE and LSE respectively. My thoughts would be to add a new class,sklearn.manifold.DirectedSpectralEmbedding, which users may call directly, or is dispatched to when an asymmetric matrix is passed to sklearn.manifold.SpectralEmbedding. Similarly to SpectralEmbedding, users would specify between ASE and LSE through an affinity parameter.

Additional context

These algorithms have been implemented in GraSPy, (available at ASE and LSE), inputing a graph represented as a dense or sparse matrix, and returning the appropriate embedding.