k-medoids clustering - MATLAB kmedoids (2024)

This example uses "Mushroom" data set [3][4][5] [6][7] from the UCI machine learning archive [7], described in https://archive.ics.uci.edu/dataset/73/mushroom. The data set includes 22 predictors for 8,124 observations of various mushrooms. The predictors are categorical data types. For example, cap shape is categorized with features of 'b' for bell-shaped cap and 'c' for conical. Mushroom color is also categorized with features of 'n' for brown, and 'p' for pink. The data set also includes a classification for each mushroom of either edible or poisonous.

Since the features of the mushroom data set are categorical, it is not possible to define the mean of several data points, and therefore the widely-used k-means clustering algorithm cannot be meaningfully applied to this data set. k-medoids is a related algorithm that partitions data into k distinct clusters, by finding medoids that minimize the sum of dissimilarities between points in the data and their nearest medoid.

The medoid of a set is a member of that set whose average dissimilarity with the other members of the set is the smallest. Similarity can be defined for many types of data that do not allow a mean to be calculated, allowing k-medoids to be used for a broader range of problems than k-means.

Using k-medoids, this example clusters the mushrooms into two groups, based on the predictors provided. It then explores the relationship between those clusters and the classifications of the mushrooms as either edible or poisonous.

This example assumes that you have downloaded the "Mushroom" data set [3][4][5] [6][7] from the UCI database (https://archive.ics.uci.edu/dataset/73/mushroom) and saved the text files agaricus-lepiota.data and agaricus-lepiota.names in your current directory. There is no column header line in the data, so readtable uses the default variable names.

clear alldata = readtable('agaricus-lepiota.data','ReadVariableNames',false);

Display the first 5 mushrooms with their first few features.

data(1:5,1:10)

ans = Var1 Var2 Var3 Var4 Var5 Var6 Var7 Var8 Var9 Var10 ____ ____ ____ ____ ____ ____ ____ ____ ____ _____ 'p' 'x' 's' 'n' 't' 'p' 'f' 'c' 'n' 'k' 'e' 'x' 's' 'y' 't' 'a' 'f' 'c' 'b' 'k' 'e' 'b' 's' 'w' 't' 'l' 'f' 'c' 'b' 'n' 'p' 'x' 'y' 'w' 't' 'p' 'f' 'c' 'n' 'n' 'e' 'x' 's' 'g' 'f' 'n' 'f' 'w' 'b' 'k'

Extract the first column, labeled data for edible andpoisonous groups. Then delete the column.

labels = data(:,1);labels = categorical(labels{:,:});data(:,1) = [];

Store the names of predictors (features), which are described in agaricus-lepiota.names.

VarNames = {'cap_shape' 'cap_surface' 'cap_color' 'bruises' 'odor' ... 'gill_attachment' 'gill_spacing' 'gill_size' 'gill_color' ... 'stalk_shape' 'stalk_root' 'stalk_surface_above_ring' ... 'stalk_surface_below_ring' 'stalk_color_above_ring' ... 'stalk_color_below_ring' 'veil_type' 'veil_color' 'ring_number' .... 'ring_type' 'spore_print_color' 'population' 'habitat'};

Set the variable names.

data.Properties.VariableNames = VarNames;

There are a total of 2480 missing values denoted as '?'.

sum(char(data{:,:}) == '?')

ans = 2480

Based on the inspection of the data set and its description,the missing values belong only to the 11th variable (stalk_root).Remove the column from the table.

data(:,11) = [];

kmedoids only accepts numeric data.You need to cast the categories you have into numeric type. The distancefunction you will use to define the dissimilarity of the data willbe based on the double representation of the categorical data.

cats = categorical(data{:,:});data = double(cats);

kmedoids can use any distance metricsupported by pdist2 to cluster. For this example you will clusterthe data using the Hamming distance because this is an appropriatedistance metric for categorical data as illustrated below. The Hammingdistance between two vectors is the percentage of the vector componentsthat differ. For instance, consider these two vectors.

v1 = [1 0 2 1];

v2 = [1 1 2 1];

They are equal in the 1st, 3rd and 4th coordinate. Since 1 ofthe 4 coordinates differ, the Hamming distance between these two vectorsis .25.

You can use the function pdist2 to measurethe Hamming distance between the first and second row of data, thenumerical representation of the categorical mushroom data. The value.2857 means that 6 of the 21 features of the mushroom differ.

pdist2(data(1,:),data(2,:),'hamming')

ans = 0.2857

In this example, you’re clustering the mushroomdata into two clusters based on features to see if the clusteringcorresponds to edibility. The kmedoids functionis guaranteed to converge to a local minima of the clustering criterion;however, this may not be a global minimum for the problem. It is agood idea to cluster the problem a few times using the 'replicates' parameter.When 'replicates' is set to a value, n,greater than 1, the k-medoids algorithm is run n times,and the best result is returned.

To run kmedoids to cluster data into 2clusters, based on the Hamming distance and to return the best resultof 3 replicates, you run the following.

rng('default'); % For reproducibility[IDX, C, SUMD, D, MIDX, INFO] = kmedoids(data,2,'distance','hamming','replicates',3);

Let's assume that mushrooms in the predicted group 1 arepoisonous and group 2 are all edible. To determine the performanceof clustering results, calculate how many mushrooms in group 1 areindeed poisonous and group 2 are edible based on the known labels.In other words, calculate the number of false positives, false negatives,as well as true positives and true negatives.

Construct a confusion matrix (or matching matrix), where thediagonal elements represent the number of true positives and truenegatives, respectively. The off-diagonal elements represent falsenegatives and false positives, respectively. For convenience, usethe confusionmat function, which calculates aconfusion matrix given known labels and predicted labels. Get thepredicted label information from the IDX variable. IDX containsvalues of 1 and 2 for each data point, representing poisonous andedible groups, respectively.

predLabels = labels; % Initialize a vector for predicted labels.predLabels(IDX==1) = categorical({'p'}); % Assign group 1 to be poisonous.predLabels(IDX==2) = categorical({'e'}); % Assign group 2 to be edible.confMatrix = confusionmat(labels,predLabels)

confMatrix = 4176 32 816 3100

Out of 4208 edible mushrooms, 4176 were correctly predictedto be in group 2 (edible group), and 32 were incorrectly predictedto be in group 1 (poisonous group). Similarly, out of 3916 poisonousmushrooms, 3100 were correctly predicted to be in group 1 (poisonousgroup), and 816 were incorrectly predicted to be in group 2 (ediblegroup).

Given this confusion matrix, calculate the accuracy, which isthe proportion of true results (both true positives and true negatives)against the overall data, and precision, which is the proportion ofthe true positives against all the positive results (true positivesand false positives).

accuracy = (confMatrix(1,1)+confMatrix(2,2))/(sum(sum(confMatrix)))

accuracy = 0.8956

precision = confMatrix(1,1) / (confMatrix(1,1)+confMatrix(2,1))

precision = 0.8365

The results indicated that applying the k-medoids algorithmto the categorical features of mushrooms resulted in clusters thatwere associated with edibility.

X — Data
numeric matrix

Data, specified as a numeric matrix. The rows of X correspondto observations, and the columns correspond to variables.

k — Number of medoids
positive integer

Number of medoids in the data, specified as a positive integer.