Nearest centroid classification is arguably the simplest machine learning technique to predict a discrete value. I created a demo, using the Python language, from scratch. My demo predicts the species (Adelie, Chinstrap, or Gentoo) of a male penguin based on bill length, bill width, flipper length, and body mass.
Briefly, in nearest centroid classification, if there are n classes, you compute the n centroids of the data. Centroids are also called vector means or vector averages. Then, to classify a data item, you compute the Euclidean distance from the item to each of the n centroids, and predict the class/label of the centroid that’s closest to the item being classified.
A few weeks ago, I put together a demo using the C# language. One rainy Saturday morning, I figured I’d refactor that demo to Python.
Nearest centroid classification (NCC) is simple, works well with small datasets, works without modification for both binary and multi-class classification, and is highly interpretable. But, and this is a big but, NCC is not very powerful because it doesn’t take into account the interactions between predictor variables. That said, for some datasets, NCC works very well.
My demo uses the Penguin Dataset. The raw training data looks like:
2, 50.0, 16.3, 230.0, 5700.0 0, 39.1, 18.7, 181.0, 3750.0 1, 38.8, 17.2, 180.0, 3800.0 2, 39.3, 20.6, 190.0, 3650.0 0, 39.2, 19.6, 195.0, 4675.0 2, 50.0, 15.2, 218.0, 5700.0 1, 50.0, 19.5, 196.0, 3900.0 . . .
The fields are species (0 = Adelie, 1 = Chinstrap, 2 = Gentoo), bill length, bill width, flipper length, body mass. The full Penguin Dataset has 345 items and has addition columns such as sex and island where measured. My demo data uses just 30 items for training and 10 items for testing. I didn’t use categorical predictor variables because NCC doesn’t work directly with categorical data. I used only male penguins.
Nearest centroid classification requires you to normalize the predictor variables so that variables with large magnitudes, such as body mass, don’t overwhelm variables with small magnitudes when computing Euclidean distance.
My demo loads the training data and applies min-max normalization like so:
import numpy as np
train_file = ".\\Data\\penguin_train_30.txt"
test_file = ".\\Data\\penguin_test_10.txt"
train_X = np.loadtxt(train_file, usecols=[1,2,3,4],
delimiter =",", comments="#", dtype=np.float64)
mins_maxs = mat_mins_maxs(train_X)
train_X = normalize_using(train_X, mins_maxs)
train_y = np.loadtxt(train_file, usecols=0,
delimiter =",", comments="#", dtype=np.int64)
. . .
I implemented a from-scratch normalize_using() function rather than take a dependency on an external library function such as the scikit-learn sklearn.preprocessing.MinMaxScaler module. The normalized data looks like:
First four normalized predictors: [[0.8508 0.2571 1.0000 0.9412] [0.2486 0.6000 0.0200 0.1765] [0.2320 0.3857 0.0000 0.1961] [0.2597 0.8714 0.2000 0.1373]]
The demo creates and trains a nearest centroid classifier using these statements:
ncc = NearestCentroidClassifier(3)
ncc.train(train_X, train_y)
print("Done ")
print(ncc.centroids)
. . .
The program-defined NearestCentroidClassifier train() method just computes the 3 centroids of the training data, which are:
Model centroids: [[0.2700 0.7786 0.2025 0.3174] [0.8432 0.6418 0.2969 0.1931] [0.7103 0.2095 0.6956 0.7996]]
The demo uses the trained model to predict the species of a new, previously unseen penguin:
x = np.array([46.5, 17.9, 192, 3500], dtype=np.float64)
x = normalize_using(x, mins_maxs)
print("Normalized x = ")
print(x)
pred_probs = ncc.predict_probs(x)
print("Prediction probs: ")
print(pred_probs)
distances = np.zeros(ncc.num_classes)
for i in range(len(distances)):
distances[i] = np.linalg.norm(x - ncc.centroids[i])
print("\nDistances to centroids: ")
print(distances)
. . .
The output is:
Predicting species for 46.5, 17.9, 192, 3500 Normalized x = [0.6575 0.4857 0.2400 0.0784] Prediction probs: [0.2791 0.5522 0.1686] Distances to centroids: [0.5426 0.2743 0.8981]
The NearestCentroidClassifier definition has a predict() method and a predict_probs() method. The predict() method returns the predicted class/label/species — 0, 1, or 2. The predict_probs() method returns pseudo-probabilities that sum to 1, and so the predicted class is the index of the pseudo-probability associated with the largest probability, in this case [1] which is associated with pp = 0.5522.
The three distances from the item-to-classify to the three centroids are computed using Euclidean distance via the not-at-all-obvious np.linalg.norm(a-b) function. I could have implemented a program-defined euclidean_dist() function but because I already had a dependency on NumPy, I just used the built-in norm() function. The predicted class is the index of the smallest distance — again [1], associated with dist = 0.2743.
My demo concludes by evaluating the model accuracy. The statements are:
test_X = np.loadtxt(test_file, usecols=[1,2,3,4],
delimiter =",", comments="#", dtype=np.float64)
test_X = normalize_using(test_X, mins_maxs)
test_y = np.loadtxt(test_file, usecols=0,
delimiter =",", comments="#", dtype=np.int64)
acc_train = ncc.accuracy(train_X, train_y)
print("Accuracy on training data = %0.4f " % acc_train)
acc_test = ncc.accuracy(test_X, test_y)
print("Accuracy on test data = %0.4f " % acc_test)
cm = ncc.confusion_matrix(train_X, train_y)
print("\nConfusion matrix for training data: ")
ncc.show_confusion(cm)
. . .
And the outputs are:
Accuracy on training data = 0.9333 Accuracy on test data = 1.0000 Confusion matrix for training data: actual 0: 8 0 0 | 8 | 1.0000 actual 1: 1 12 0 | 13 | 0.9231 actual 2: 1 0 8 | 9 | 0.8889
The nearest centroid classification technique worked surprisingly well on the demo data. In fact, I had to change two of the class labels/species in the training data in order to get any incorrect predictions at all. If you look at the centroids, you can see that species 0 = Adelie is unambiguously determined by small bill length and large bill width. Species 1 = Chinstrap is determined by large bill length and small body mass. Species 2 = Gentoo is determined by large flipper length and large body mass.
Good fun on a Saturday morning.
An Internet search for “centroid” returned an image of the structure of vanadinite, an uncommon mineral. Vanadinite contains element #23 vanadium. Vanadium is added to steel, which makes the steel lighter and stronger. The first widespread industrial use of vanadium steel was in the chassis of the Ford Model T.
Demo code. Replace the “lt” (less than) with Boolean operator symbol (my blog editor chokes on symbols).
# nearest_centroid_classification.py
import numpy as np
class NearestCentroidClassifier:
def __init__(self, num_classes):
self.num_classes = num_classes
self.centroids = None
# consider adding self.distances here
def train(self, train_X, train_y):
# compute centroid of each class
n = len(train_X)
dim = len(train_X[0])
self.centroids = np.zeros((self.num_classes,dim),
dtype=np.float64)
counts = np.zeros(self.num_classes)
for i in range(n):
c = train_y[i] # current class
self.centroids[c] += train_X[i]
counts[c] += 1
for j in range(self.num_classes):
self.centroids[j] /= counts[j]
def predict_probs(self, x):
# returns pseudo-probs
distances = np.zeros(self.num_classes)
for i in range(self.num_classes):
distances[i] = \
np.linalg.norm(x - self.centroids[i])
if distances[i] "lt" 0.00000001:
distances[i] = 0.00000001 # avoid div by 0
inv_dists = 1 / distances
probs = inv_dists / np.sum(inv_dists)
return probs
def predict(self, x):
# returns predicted class
distances = np.zeros(self.num_classes)
for i in range(self.num_classes):
distances[i] = \
np.linalg.norm(x - self.centroids[i])
pred_class = np.argmin(distances)
return pred_class
def accuracy(self, data_X, data_y):
n_correct = 0; n_wrong = 0
for i in range(len(data_X)):
x = data_X[i]
trgt_y = data_y[i]
pred_y = self.predict(x)
if pred_y == trgt_y: n_correct += 1
else: n_wrong += 1
return n_correct / (n_correct + n_wrong)
def confusion_matrix(self, data_X, data_y):
nc = self.num_classes
result = np.zeros((nc,nc), dtype=np.float64)
for i in range(len(data_X)):
x = data_X[i]
act_y = data_y[i]
pred_y = self.predict(x)
result[act_y][pred_y] += 1
return result
def show_confusion(self, cm):
nc = self.num_classes
counts = np.zeros(nc, dtype=np.int64)
accs = np.zeros(nc, dtype=np.float64)
counts = np.sum(cm, axis=1) # collapse cols, do rows
for i in range(nc):
accs[i] = cm[i][i] / counts[i]
for i in range(nc):
print("actual " + str(i) + ": ", end="")
for j in range(nc):
print("%4.0f" % cm[i][j], end="")
print(" | %4d " % counts[i], end="")
print(" | %7.4f " % accs[i])
# -----------------------------------------------------------
def mat_mins_maxs(data_X):
n_cols = len(data_X[0])
mins_maxs = np.zeros((2,n_cols), dtype=np.float64)
mins = data_X.min(axis=0) # collapse rows == process cols
maxs = data_X.max(axis=0)
mins_maxs[0] = mins; mins_maxs[1] = maxs
return mins_maxs
# -----------------------------------------------------------
def minmax_normalize(data_X):
n_rows = len(data_X); n_cols = len(data_X[0])
result = np.zeros((n_rows,n_cols), dtype=np.float64)
mins_maxs = np.zeros((2,n_cols), dtype=np.float64)
mins = data_X.min(axis=0) # collapse rows == process cols
maxs = data_X.max(axis=0)
mins_maxs[0] = mins; mins_maxs[1] = maxs
result = (data_X - mins) / (maxs - mins)
return (result, mins_maxs)
# -----------------------------------------------------------
def normalize_using(x, mins_maxs):
# x can be either a data matrix or single vector
return (x - mins_maxs[0]) / (mins_maxs[1] - mins_maxs[0])
# -----------------------------------------------------------
def main():
print("\nBegin nearest centroid classification demo ")
print("\nPredict penguin species from bill length, bill ")
print(" width, flipper length, body mass ")
print("Species: 0 = Adelie, 1 = Chinstrap, 2 = Gentoo ")
train_file = ".\\Data\\penguin_train_30.txt"
test_file = ".\\Data\\penguin_test_10.txt"
train_X = np.loadtxt(train_file, usecols=[1,2,3,4],
delimiter =",", comments="#", dtype=np.float64)
np.set_printoptions(precision=1, suppress=True,
floatmode='fixed')
print("\nFirst four raw training data predictors: ")
print(train_X[0:4,:])
print("\nApplying min-max normalization to raw data ")
mins_maxs = mat_mins_maxs(train_X)
train_X = normalize_using(train_X, mins_maxs)
# train_X, mins_maxs = minmax_normalize(train_X)
np.set_printoptions(precision=4, suppress=True,
floatmode='fixed')
print("\nFirst four normalized predictors: ")
print(train_X[0:4,:])
train_y = np.loadtxt(train_file, usecols=0,
delimiter =",", comments="#", dtype=np.int64)
print("\nTraining data target values: ")
print(train_y)
print("\nTraining nearest centroid classifier ")
ncc = NearestCentroidClassifier(3)
ncc.train(train_X, train_y)
print("Done ")
print("\nModel centroids: ")
np.set_printoptions(precision=4, suppress=True,
floatmode='fixed')
print(ncc.centroids)
print("\nPredicting species for 46.5, 17.9, 192, 3500")
x = np.array([46.5, 17.9, 192, 3500], dtype=np.float64)
x = normalize_using(x, mins_maxs)
print("\nNormalized x = ")
print(x)
pred_probs = ncc.predict_probs(x)
print("\nPrediction probs: ")
print(pred_probs)
distances = np.zeros(ncc.num_classes)
for i in range(len(distances)):
distances[i] = np.linalg.norm(x - ncc.centroids[i])
print("\nDistances to centroids: ")
print(distances)
print("\nEvaluating model accuracy ")
test_X = np.loadtxt(test_file, usecols=[1,2,3,4],
delimiter =",", comments="#", dtype=np.float64)
test_X = normalize_using(test_X, mins_maxs)
test_y = np.loadtxt(test_file, usecols=0,
delimiter =",", comments="#", dtype=np.int64)
acc_train = ncc.accuracy(train_X, train_y)
print("Accuracy on training data = %0.4f " % acc_train)
acc_test = ncc.accuracy(test_X, test_y)
print("Accuracy on test data = %0.4f " % acc_test)
cm = ncc.confusion_matrix(train_X, train_y)
print("\nConfusion matrix for training data: ")
ncc.show_confusion(cm)
print("\nEnd demo ")
if __name__ == "__main__":
main()
Training data:
# penguin_train_30.txt # male only # train mins = (34.60, 14.50, 180.00, 3300.00) # train maxs = (52.70, 21.50, 230.00, 5850.00) # # 30 items # actual: 0, 38.8, 17.2, 180.0, 3800.0 # replaced by: 1, 38.8, 17.2, 180.0, 3800.0 # # actual: 0, 39.3, 20.6, 190.0, 3650.0 # replaced by 2, 39.3, 20.6, 190.0, 3650.0 # to generate at least one bad prediction # 2, 50.0, 16.3, 230.0, 5700.0 0, 39.1, 18.7, 181.0, 3750.0 # 0, 38.8, 17.2, 180.0, 3800.0 # true data 1, 38.8, 17.2, 180.0, 3800.0 # 0, 39.3, 20.6, 190.0, 3650.0 # true data 2, 39.3, 20.6, 190.0, 3650.0 0, 39.2, 19.6, 195.0, 4675.0 2, 50.0, 15.2, 218.0, 5700.0 1, 50.0, 19.5, 196.0, 3900.0 1, 51.3, 19.2, 193.0, 3650.0 0, 38.6, 21.2, 191.0, 3800.0 1, 52.7, 19.8, 197.0, 3725.0 2, 47.6, 14.5, 215.0, 5400.0 1, 51.3, 18.2, 197.0, 3750.0 2, 46.7, 15.3, 219.0, 5200.0 1, 51.3, 19.9, 198.0, 3700.0 0, 34.6, 21.1, 198.0, 4400.0 1, 51.7, 20.3, 194.0, 3775.0 1, 52.0, 18.1, 201.0, 4050.0 2, 46.8, 15.4, 215.0, 5150.0 0, 42.5, 20.7, 197.0, 4500.0 1, 50.5, 19.6, 201.0, 4050.0 1, 50.3, 20.0, 197.0, 3300.0 2, 49.0, 16.1, 216.0, 5550.0 0, 46.0, 21.5, 194.0, 4200.0 1, 49.2, 18.2, 195.0, 4400.0 2, 48.4, 14.6, 213.0, 5850.0 2, 49.3, 15.7, 217.0, 5850.0 0, 37.7, 18.7, 180.0, 3600.0 0, 38.2, 18.1, 185.0, 3950.0 1, 48.5, 17.5, 191.0, 3400.0 1, 50.6, 19.4, 193.0, 3800.0
Test data:
# penguin_test_10.txt # male only # 10 items 0, 40.6, 18.6, 183.0, 3550.0 0, 40.5, 18.9, 180.0, 3950.0 0, 37.2, 18.1, 178.0, 3900.0 0, 40.9, 18.9, 184.0, 3900.0 1, 52.0, 19.0, 197.0, 4150.0 1, 49.5, 19.0, 200.0, 3800.0 1, 52.8, 20.0, 205.0, 4550.0 2, 49.2, 15.2, 221.0, 6300.0 2, 48.7, 15.1, 222.0, 5350.0 2, 50.2, 14.3, 218.0, 5700.0
.NET Test Automation Recipes
Software Testing
SciPy Programming Succinctly
Keras Succinctly
R Programming
Visual Studio Live
Microsoft MLADS Conference
DevIntersection Conference
Machine Learning Week
Ai4 Conference
G2E Conference
iSC West Conference
You must be logged in to post a comment.