Spaces:
Sleeping
Sleeping
Download DT/DecisionTree.py from mnistMLProject/MNISTclassification: direct link, hf CLI and curl.
- Browser
- Download file 7.5 kB
-
https://huggingface.co/spaces/mnistMLProject/MNISTclassification/resolve/main/DT/DecisionTree.py
- Command line
-
hf download hf://spaces/mnistMLProject/MNISTclassification/DT/DecisionTree.py
-
curl -L -o DecisionTree.py https://huggingface.co/spaces/mnistMLProject/MNISTclassification/resolve/main/DT/DecisionTree.py
7.5 kB
| import numpy as np | |
| import math | |
| class DecisionTree: | |
| class Node: | |
| def __init__(self, feature=None, threshold=None, left=None, right=None, decision=None): | |
| self.feature = feature | |
| self.threshold = threshold | |
| self.left = left | |
| self.right = right | |
| self.decision = decision | |
| def __init__(self, | |
| maxDepth=None, | |
| minSamplesSplit=2, | |
| criterion="gini", | |
| maxFeatures=None, | |
| minSampleLeafs=1, | |
| classWeights=None, | |
| randomState=None): | |
| self.maxDepth = maxDepth | |
| self.minSamplesSplit = minSamplesSplit | |
| self.minSampleLeafs = minSampleLeafs | |
| self.criterion = criterion | |
| self.maxFeatures = maxFeatures | |
| self.allowedCriteria = ["entropy", "gini"] | |
| self.classWeights = classWeights | |
| # NEW: deterministic randomness | |
| self.randomState = randomState | |
| self.rng = np.random.default_rng(randomState) | |
| if criterion not in self.allowedCriteria: | |
| raise ValueError("Criterion has to be either entropy or gini") | |
| self.root = None | |
| def majorityLabel(self, labels): | |
| counts = np.bincount(labels) | |
| return np.argmax(counts) | |
| def getThreshold(self, featureValues, labels): | |
| entropy = [] | |
| labelCount = len(labels) | |
| sortedIndices = np.argsort(featureValues) | |
| sortedFeatureValues = featureValues[sortedIndices] | |
| sortedLabels = labels[sortedIndices] | |
| leftLabelCounts = np.zeros(np.max(labels) + 1, dtype=int) | |
| rightLabelCounts = np.bincount(sortedLabels, | |
| minlength=np.max(labels) + 1) | |
| thresholds = [] | |
| for i in range(len(sortedLabels) - 1): | |
| leftLabelCounts[sortedLabels[i]] += 1 | |
| rightLabelCounts[sortedLabels[i]] -= 1 | |
| if np.sum(leftLabelCounts) < self.minSampleLeafs: | |
| continue | |
| if np.sum(rightLabelCounts) < self.minSampleLeafs: | |
| continue | |
| if sortedFeatureValues[i] == sortedFeatureValues[i + 1]: | |
| continue | |
| w_entropy = self.computeImpurity( | |
| leftLabelCounts, | |
| rightLabelCounts, | |
| labelCount | |
| ) | |
| threshold = ( | |
| sortedFeatureValues[i] + | |
| sortedFeatureValues[i + 1] | |
| ) / 2 | |
| thresholds.append(threshold) | |
| entropy.append(w_entropy) | |
| if len(entropy) == 0: | |
| return None, None | |
| minEntropyIndex = np.argmin(entropy) | |
| return thresholds[minEntropyIndex], entropy[minEntropyIndex] | |
| def computeImpurity(self, | |
| leftLabelCounts, | |
| rightLabelCounts, | |
| labelCount): | |
| leftEntropy = 0 | |
| rightEntropy = 0 | |
| if self.classWeights is not None: | |
| weightsArr = np.array([ | |
| self.classWeights.get(i, 1) | |
| for i in range(leftLabelCounts.size) | |
| ]) | |
| else: | |
| weightsArr = np.ones(leftLabelCounts.size) | |
| weightedCountsL = weightsArr * leftLabelCounts | |
| weightedCountsR = weightsArr * rightLabelCounts | |
| wLeftLabelCount = np.sum(weightedCountsL) | |
| wRightLabelCount = np.sum(weightedCountsR) | |
| totalWeight = wLeftLabelCount + wRightLabelCount | |
| for count in weightedCountsL: | |
| if count == 0: | |
| continue | |
| prob = count / wLeftLabelCount | |
| if self.criterion == "entropy": | |
| leftEntropy += -prob * np.log2(prob) | |
| else: | |
| leftEntropy += prob ** 2 | |
| for count in weightedCountsR: | |
| if count == 0: | |
| continue | |
| prob = count / wRightLabelCount | |
| if self.criterion == "entropy": | |
| rightEntropy += -prob * np.log2(prob) | |
| else: | |
| rightEntropy += prob ** 2 | |
| if self.criterion == "entropy": | |
| w_entropy = ( | |
| (wLeftLabelCount / totalWeight) * leftEntropy + | |
| (wRightLabelCount / totalWeight) * rightEntropy | |
| ) | |
| else: | |
| w_entropy = ( | |
| (wLeftLabelCount / totalWeight) * (1 - leftEntropy) + | |
| (wRightLabelCount / totalWeight) * (1 - rightEntropy) | |
| ) | |
| return w_entropy | |
| def getFeature(self, trainingData, labels): | |
| entropy = [] | |
| thresholds = [] | |
| featureIndices = [] | |
| noOfFeatures = trainingData.shape[1] | |
| if self.maxFeatures is not None: | |
| current_max = self.maxFeatures | |
| if current_max == "sqrt": | |
| current_max = int(math.sqrt(noOfFeatures)) | |
| elif current_max == "log2": | |
| current_max = int(np.log2(noOfFeatures)) | |
| featureArr = self.rng.choice( | |
| noOfFeatures, | |
| size=current_max, | |
| replace=False | |
| ) | |
| else: | |
| featureArr = np.arange(noOfFeatures) | |
| for j in featureArr: | |
| featureValues = trainingData[:, j] | |
| optimalThreshold, minEntropy = self.getThreshold( | |
| featureValues, | |
| labels | |
| ) | |
| if optimalThreshold is None: | |
| continue | |
| entropy.append(minEntropy) | |
| thresholds.append(optimalThreshold) | |
| featureIndices.append(j) | |
| if len(entropy) == 0: | |
| return None, None | |
| minEntropyIndex = np.argmin(entropy) | |
| return ( | |
| featureIndices[minEntropyIndex], | |
| thresholds[minEntropyIndex] | |
| ) | |
| def buildTree(self, data, labels, depth=0): | |
| if len(np.unique(labels)) == 1: | |
| return self.Node(decision=np.unique(labels)[0]) | |
| if self.maxDepth is not None and depth >= self.maxDepth: | |
| return self.Node(decision=self.majorityLabel(labels)) | |
| if len(labels) < self.minSamplesSplit: | |
| return self.Node(decision=self.majorityLabel(labels)) | |
| feature, threshold = self.getFeature(data, labels) | |
| if feature is None: | |
| return self.Node(decision=self.majorityLabel(labels)) | |
| leftMask = data[:, feature] <= threshold | |
| rightMask = ~leftMask | |
| leftChild = self.buildTree( | |
| data[leftMask], | |
| labels[leftMask], | |
| depth + 1 | |
| ) | |
| rightChild = self.buildTree( | |
| data[rightMask], | |
| labels[rightMask], | |
| depth + 1 | |
| ) | |
| return self.Node( | |
| feature, | |
| threshold, | |
| leftChild, | |
| rightChild | |
| ) | |
| def fit(self, trainingData, labels): | |
| self.root = self.buildTree(trainingData, labels) | |
| def traverseTree(self, dataPoint, node): | |
| if node.decision is not None: | |
| return node.decision | |
| if dataPoint[node.feature] <= node.threshold: | |
| return self.traverseTree(dataPoint, node.left) | |
| return self.traverseTree(dataPoint, node.right) | |
| def predict(self, datapoints): | |
| if self.root is None: | |
| raise ValueError( | |
| "Decision tree has not been trained. Call fit() first." | |
| ) | |
| return np.array([ | |
| self.traverseTree(point, self.root) | |
| for point in datapoints | |
| ]) |