In practical applications of knowledge space theory, knowledge states can be conceived as partially ordered clusters of individuals. Existing extensions of the theory to polytomous data lack methods for building "polytomous" structures. To this aim, an adaptation of the k-median clustering algorithm is proposed. It is an extension of k-modes to ordinal data in which the Hamming distance is replaced by the Manhattan distance, and the central tendency measure is the median, rather than the mode. The algorithm is tested in a series of simulation studies and in an application to empirical data. Results show that there are theoretical and practical reasons for preferring the k-median to the k-modes algorithm, whenever the responses to the items are measured on an ordinal scale. This is because the Manhattan distance is sensitive to the order on the levels, while the Hamming distance is not. Overall, k-median seems to be a promising data-driven procedure for building polytomous structures.
Keywords: Clustering algorithms; Knowledge space theory; Polytomous KST; k-median; k-modes.