Results: We present an algorithm that efficiently constructs a k-ary tree, where each node can have up to k children, and then optimally orders the leaves of that tree. By combining k clusters at each step our algorithm becomes more robust against noise and missing values. By optimally ordering the leaves of the resulting tree we maintain the pairwise relationships that appear in the original method, without sacrificing the robustness.
Our k-ary construction algorithm runs in O(n3) regardless of k and our ordering algorithm runs in O(4k n3). We present several examples that show that our k-ary clustering algorithm achieves results that are superior to the binary tree results in both global presentation and cluster identification.
Availability: We have implemented the above algorithms in C++ on the Linux operating system. Source code is available upon request from firstname.lastname@example.org.