"""
@author : Zhaoqing Liu
@email : Zhaoqing.Liu-1@student.uts.edu.au
"""
import ctypes
import multiprocessing
from abc import ABCMeta
import numpy as np
from fuzzytrees.fdt_base import FuzzyDecisionTreeWrapper
from fuzzytrees.fdts import FuzzyCARTClassifier, FuzzyCARTRegressor
from fuzzytrees.util_tree_criterion_funcs import majority_vote, mean_value
from fuzzytrees.util_preprocessing_funcs import resample_bootstrap
[docs]class BaseFuzzyRDF(metaclass=ABCMeta):
"""
Base fuzzy random decision forests (RF) class that encapsulates all
base functions to be inherited by all derived classes (and attributes,
if required). This algorithm is a fuzzy extension of the random decision
forests proposed by Tin Kam Ho [1]_.
Warnings
--------
This class should not be used directly.
Use derived classes instead.
Attention
---------
Note that sharing data between processes may not be the best option due to
various unknowable synchronisation issues, but using ``Pipe`` or ``Queue``
to communicate between multiple processes instead whenever possible. See also
Python documentation:
As mentioned above, when doing concurrent programming it is usually best to
avoid using shared state as far as possible. This is particularly true when
using multiple processes. However, if you really do need to use some shared
data then multiprocessing provides a couple of ways of doing so.
Parameters
----------
disable_fuzzy : bool, default=False
Set whether the specified fuzzy decision tree uses the fuzzification.
If disable_fuzzy=True, the specified fuzzy decision tree is equivalent
to a naive decision tree.
fuzzification_options : FuzzificationOptions, default=None
Protocol message class that encapsulates all the options of the
fuzzification settings used by the specified fuzzy decision tree.
criterion_func : {"gini", "entropy"}, default="gini", for classification; {"mse", "mae"}, default="mse", for regression
In classification, the criterion function used by the function that
calculates the impurity gain of the target values.
In regression, the criterion function used by the function that
calculates the impurity gain of the target values.
n_estimators : int, default=100
The number of fuzzy decision trees to be used.
max_depth : int, default=3
The maximum depth of the tree to be trained.
min_samples_split : int, default=2
The minimum number of samples required to split a node. If a node has a
sample number above this threshold, it will be split, otherwise it
becomes a leaf node.
min_impurity_split : float, default=1e-7
The minimum impurity required to split a node. If a node's impurity is
above this threshold, it will be split, otherwise it becomes a leaf node.
max_features : int, default=None
The maximum threshold value of the qualified feature number in the
training dataset when training each fuzzy decision tree.
multi_process_options : MultiProcessOptions, default=None
Protocol message class that encapsulates all the options of the
multi-process settings.
If it is left as None, adopt non-parallel computing mode.
Attributes
----------
_estimators : ndarray of FuzzyDecisionTreeClassification
The collection of sub-estimators as base learners.
_res_func : function, default=None
In classification, get the final result from the classes given by the
forest by majority voting method. In regression, calculate the average
of the predicted values given by the forest as the final result.
_n_processes : int, default=None
Number of CPU cores requested in parallel computing mode.
Notes
-----
About RF
The first algorithm for random decision forests was created by Tin Kam Ho [1]_
using the random subspace method [2]_, which, in Ho's formulation, is a way to
implement the "stochastic discrimination" approach to classification proposed
by Eugene Kleinberg.
An extension of the algorithm was developed by Leo Breiman [4]_ and Adele Cutler
[5]_. The extension combines Breiman's "bagging" idea and random selection of
features, introduced first by Ho [1]_ and later independently by Amit and
Geman [3]_ in order to construct a collection of decision trees with controlled
variance.
The randomness of RF is reflected in two aspects:
1. RF uses the bootstrapping sampling method to randomly selects n samples
from the original dataset to train each tree as the base learner,
where n is the sample size of the original dataset.
NB: The sample size of each training dataset is the same as that of
the original dataset, but the bootstrapping sampling method may make
the elements in the same training dataset duplicate, or the elements
in different training datasets duplicate.
2. During the construction of each tree, RF also randomly selects m
features of the training dataset, and then searches the optimal
features from the randomly selected features each time when splitting
a tree node to find the best splitting point.
Different RFs have different random feature selection methods. For
example, Tin Kam Ho's RF adopts tree-level random feature selection,
i.e. the RF randomly selects m features of the training dataset for
subsequently splitting all tree nodes. By contrast, Leo Breiman's RF
adopts node-level random feature selection, i.e. the RF randomly
selects m features of the training dataset when splitting a node
every time.
Let M be the total number of features of data and m be the number
of selected features. Generally, the value can be tried from the
following usual practices:
- For classification problems, :math:`m = 1 / 3 * M`;
- For regression problems, :math:`m = \log_{2} (M + 1)`;
- By defaults, :math:`m = \sqrt{M}`.
References
----------
.. [1] Ho, T.K., 1995, August. Random decision forests. In Proceedings
of 3rd international conference on document analysis and
recognition (Vol. 1, pp. 278-282). IEEE.
.. [2] Ho, T.K., 1998. The random subspace method for constructing
decision forests. IEEE transactions on pattern analysis and
machine intelligence, 20(8), pp.832-844.
.. [3] Amit, Y. and Geman, D., 1997. Shape quantization and recognition
with randomized trees. Neural computation, 9(7), pp.1545-1588.
.. [4] Breiman, L., 2001. Random forests. Machine learning, 45(1),
pp.5-32.
.. [5] RColorBrewer, S. and Liaw, M.A., 2018. Package ‘randomForest’.
University of California, Berkeley: Berkeley, CA, USA.
"""
def __init__(self, disable_fuzzy, fuzzification_options, criterion_func, n_estimators,
max_depth, min_samples_split, min_impurity_split, max_features, multi_process_options):
self.disable_fuzzy = disable_fuzzy
self.fuzzification_options = fuzzification_options
self.criterion_func = criterion_func
self.n_estimators = n_estimators
self.max_depth = max_depth
self.min_samples_split = min_samples_split
self.min_impurity_split = min_impurity_split
self.max_features = max_features
self.multi_process_options = multi_process_options
self._estimators = [] # Forest initialised in derived classes.
self._res_func = None
self._n_processes = None
if self.multi_process_options is not None:
self._n_processes = multiprocessing.cpu_count() if self.multi_process_options.n_cpu_cores_req is None else self.multi_process_options.n_cpu_cores_req
[docs] def fit(self, X_train, y_train):
"""
Fit the fuzzy random decision forest model (in multi-process mode).
Process consists of:
St.1. Randomly resample instances through bootstrapping sampling (WR).
St.2. Random select features.
St.3. Construct trees.
St.4. Majority vote (classification) or simple average (regression) to
prevent overfitting and reduce variance.
Parameters
----------
X_train : array-like of shape (n_samples, n_features)
Input instances to be predicted.
y_train : array-like of shape (n_samples,)
Target values (non-negative integers in classification,
real numbers in regression)
NB: The input array needs to be of integer dtype, otherwise a
TypeError is raised.
"""
# Randomly select n_estimators training subsets through bootstrapping sampling.
X_train_subsets, y_train_subsets = resample_bootstrap(X_train, y_train, n_subsets=self.n_estimators)
# Get the number of the data features.
n_features = X_train.shape[1]
if not self.disable_fuzzy:
# NB: Except the columns of fuzzy degrees of membership.
n_features = int(n_features / (self.fuzzification_options.conv_k + 1))
if self.max_features is None:
self.max_features = int(np.sqrt(n_features))
# Train each tree in the forest.
# NB: Iterate the n_estimators training subsets generated above, training a tree in each iteration.
if self.multi_process_options: # When self.multi_process_options is not None
# In multi-process mode.
with multiprocessing.Manager() as mg:
# Create a connection used to communicate between main process and its child processes.
q = multiprocessing.Manager().Queue()
# Create a pool for main process to manage its child processes in parallel.
pool = multiprocessing.Pool(processes=self._n_processes)
for i in range(self.n_estimators):
pool.apply_async(self._fit_one, args=(X_train_subsets[i], y_train_subsets[i], n_features, i, q,))
pool.close()
pool.join()
# Replace all the estimators in the forest with the ones returned by the sub-processes.
idx = 0
while not q.empty():
estimator = q.get()
self._estimators[idx] = estimator
print("Replaced the {}-th estimators in the forest.".format(idx))
idx += 1
else:
# In single-process mode.
for i in range(self.n_estimators):
self._fit_one(X_train_subsets[i], y_train_subsets[i], n_features, i)
def _fit_one(self, X_train_subset, y_train_subset, n_features, i, q=None):
# Randomly select features.
idxs = np.random.choice(n_features, self.max_features, replace=True)
if not self.disable_fuzzy:
# Select the columns of fuzzy degrees of membership at the same time.
idxs_cp = np.copy(idxs)
for idx in idxs_cp:
# Columns of the idx-th feature's degrees of membership start from
# "n_original_features + feature_idx * self.fuzzification_options.conv_k + 1", and end with
# "n_original_features + (feature_idx + 1) * self.fuzzification_options.conv_k + 1".
start = n_features + idx * self.fuzzification_options.conv_k
stop = n_features + (idx + 1) * self.fuzzification_options.conv_k
idxs_dm = np.arange(start=start, stop=stop, step=1, dtype=int)
idxs = np.concatenate((idxs, idxs_dm), axis=0)
X_train_subset = X_train_subset[:, idxs]
# Fit an estimator and record the indexes of fitted features to prepare for predictions.
self._estimators[i].fit(X_train_subset, y_train_subset)
self._estimators[i].feature_idxs = idxs
# In multi-process mode, the trained estimator needs to be passed back to the master process because
# the sub-process cannot update the global variables in the master process.
if self.multi_process_options:
if not q.full():
q.put(self._estimators[i])
print("{}-th tree fitting is complete.".format(i))
[docs] def predict(self, X):
"""
Predict results for X.
Parameters
----------
X : array-like of shape (n_samples, n_features)
Input instances to be predicted.
Returns
-------
y_pred : ndarray of shape (n_samples,)
The predicted values.
Notes
-----
When to use multiple processes?
Divide a prediction calculation into subunits and run them in
multi-process mode, making sure that each subunit is sufficiently
complex. Otherwise, when the complexity of each subunit falls below
a certain threshold, depending on the hardware and software
environment, the time consumed by CPU scheduling will be greater
than the time saved by multiple processes. As an example, here is
a comparison of the elapsed times for multi-process `predict` and
non-multi-process `predict` on the dataset provided by
`sklearn.datasets.load_digits()`.
100 fuzzy trees with other parameters by default：
- Time elapsed to load data: 0.049551s;
- Time elapsed to preprocess fuzzification: 1.6184s;
- Time elapsed to partition data: 0.0041816s;
- Time elapsed to train a fuzzy classifier: 5.7213s;
- Time elapsed to predict by the fuzzy classifier:
- (Multi-process `predict`) 8.3837s;
- (Non-multi-process `predict`) 0.22926s.
1,000 fuzzy trees with other parameters by default:
- Time elapsed to load data: 0.049702s;
- Time elapsed to preprocess fuzzification: 1.6178s;
- Time elapsed to partition data: 0.0043864s;
- Time elapsed to train a fuzzy classifier: 52.689s;
- Time elapsed to predict by the fuzzy classifier:
- (Multi-process `predict`) 817.67s;
- (Non-multi-process `predict`) 2.2753s.
10,000 fuzzy trees with other parameters by default:
- Time elapsed to load data: 0.050004s;
- Time elapsed to preprocess fuzzification: 1.6821s;
- Time elapsed to partition data: 0.0041745s;
- Time elapsed to train a fuzzy classifier: 515.57s;
- Time elapsed to predict by the fuzzy classifier:
- (Multi-process `predict`) unknown (probably greater than 100 * 817.67s);
- (Non-multi-process `predict`) 23.225s.
As shown in the above experimental results, in multi-process mode,
:math:`WallTime_curr / WallTime_prev ≈ (NumberEstimators_curr / NumberEstimators_prev)^2`,
while in non-multi-process mode,
:math:`WallTime_curr / WallTime_prev ≈ NumberEstimators_curr / NumberEstimators_prev`.
Therefore, `predict` is not complex enough to be a subunit of
multi-process computation, and using multi-process mode on it is
usually not the best choice.
"""
y_preds = []
for i in range(self.n_estimators):
idxs = self._estimators[i].feature_idxs
X_subset = X[:, idxs]
y_pred = self._estimators[i].predict(X_subset)
y_preds.append(y_pred)
y_preds = np.array(y_preds).T
return self._res_func(y_preds)
[docs]class BaseFuzzyRDFClassifier(BaseFuzzyRDF):
"""
Fuzzy random decision forests classifier.
Attention
---------
For classification tasks, the class that is the mode of
the classes of the individual trees is returned.
See derived classes for descriptions of all parameters
and attributes in this class.
Parameters
----------
disable_fuzzy : bool, default=False
Set whether the specified fuzzy decision tree uses the fuzzification.
If disable_fuzzy=True, the specified fuzzy decision tree is equivalent
to a naive decision tree.
fuzzification_options : FuzzificationOptions, default=None
Protocol message class that encapsulates all the options of the
fuzzification settings used by the specified fuzzy decision tree.
criterion_func : {"gini", "entropy"}, default="gini"
The criterion function used by the function that calculates the impurity
gain of the target values.
NB: Only use a criterion function for decision tree classifier.
n_estimators : int, default=100
The number of fuzzy decision trees to be used.
max_depth : int, default=3
The maximum depth of the tree to be trained.
min_samples_split : int, default=2
The minimum number of samples required to split a node. If a node has a
sample number above this threshold, it will be split, otherwise it
becomes a leaf node.
min_impurity_split : float, default=1e-7
The minimum impurity required to split a node. If a node's impurity is
above this threshold, it will be split, otherwise it becomes a leaf node.
max_features : int, default=None
The maximum threshold value of the qualified feature number in the
training dataset when training each fuzzy decision tree.
multi_process_options : MultiProcessOptions, default=None
Protocol message class that encapsulates all the options of the
multi-process settings.
If it is left as None, adopt non-parallel computing mode.
Attributes
----------
_estimators : ndarray of FuzzyDecisionTreeClassification
The collection of sub-estimators as base learners.
_res_func : function, default=None
In classification, get the final result from the classes given by the
forest by majority voting method. In regression, calculate the average
of the predicted values given by the forest as the final result.
"""
def __init__(self, disable_fuzzy, fuzzification_options, criterion_func, n_estimators=100,
max_depth=3, min_samples_split=2, min_impurity_split=1e-7, max_features=None,
multi_process_options=None):
super().__init__(disable_fuzzy=disable_fuzzy,
fuzzification_options=fuzzification_options,
criterion_func=criterion_func,
n_estimators=n_estimators,
max_depth=max_depth,
min_samples_split=min_samples_split,
min_impurity_split=min_impurity_split,
max_features=max_features,
multi_process_options=multi_process_options)
# Initialise the forest.
for _ in range(self.n_estimators):
estimator = FuzzyDecisionTreeWrapper(fdt_class=FuzzyCARTClassifier,
disable_fuzzy=disable_fuzzy,
fuzzification_options=fuzzification_options,
criterion_func=criterion_func,
max_depth=max_depth,
min_samples_split=min_samples_split,
min_impurity_split=min_impurity_split)
self._estimators.append(estimator)
# Specify to get the final classification result by majority voting method.
self._res_func = majority_vote
[docs]class BaseFuzzyRDFRegressor(BaseFuzzyRDF):
"""
Fuzzy random decision forests regressor.
Attention
---------
For regression tasks, the mean or average prediction of
the individual trees is returned.
Parameters
----------
disable_fuzzy : bool, default=False
Set whether the specified fuzzy decision tree uses the fuzzification.
If disable_fuzzy=True, the specified fuzzy decision tree is equivalent
to a naive decision tree.
fuzzification_options : FuzzificationOptions, default=None
Protocol message class that encapsulates all the options of the
fuzzification settings used by the specified fuzzy decision tree.
criterion_func : {"mse", "mae"}, default="mse"
The criterion function used by the function that calculates the impurity
gain of the target values.
NB: Only use a criterion function for decision tree regressor.
n_estimators : int, default=100
The number of fuzzy decision trees to be used.
max_depth : int, default=3
The maximum depth of the tree to be trained.
min_samples_split : int, default=2
The minimum number of samples required to split a node. If a node has a
sample number above this threshold, it will be split, otherwise it
becomes a leaf node.
min_impurity_split : float, default=1e-7
The minimum impurity required to split a node. If a node's impurity is
above this threshold, it will be split, otherwise it becomes a leaf node.
max_features : int, default=None
The maximum threshold value of the qualified feature number in the
training dataset when training each fuzzy decision tree.
multi_process_options : MultiProcessOptions, default=None
Protocol message class that encapsulates all the options of the
multi-process settings.
If it is left as None, adopt non-parallel computing mode.
Attributes
----------
_estimators : ndarray of FuzzyDecisionTreeRegressor
The collection of sub-estimators as base learners.
_res_func : function, default=None
In classification, get the final result from the classes given by the
forest by majority voting method. In regression, calculate the average
of the predicted values given by the forest as the final result.
"""
def __init__(self, disable_fuzzy, fuzzification_options, criterion_func, n_estimators=100,
max_depth=3, min_samples_split=2, min_impurity_split=1e-7, max_features=None,
multi_process_options=None):
super().__init__(disable_fuzzy=disable_fuzzy,
fuzzification_options=fuzzification_options,
criterion_func=criterion_func,
n_estimators=n_estimators,
max_depth=max_depth,
min_samples_split=min_samples_split,
min_impurity_split=min_impurity_split,
max_features=max_features,
multi_process_options=multi_process_options)
# Initialise forest.
for _ in range(self.n_estimators):
estimator = FuzzyDecisionTreeWrapper(fdt_class=FuzzyCARTRegressor,
disable_fuzzy=disable_fuzzy,
fuzzification_options=fuzzification_options,
criterion_func=criterion_func,
max_depth=max_depth,
min_samples_split=min_samples_split,
min_impurity_split=min_impurity_split)
self._estimators.append(estimator)
# Specify to get the final regression result by averaging method.
self._res_func = mean_value