MNISTclassification / DT /DecisionTree.py
amirTamer's picture
Added DT
3d97c90
Raw History Blame Contribute Delete
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
])