Several optimal algorithms for M-clustering problem using hyperplane based k-d tree and subspace vector quantization are proposed. Based on the property of hyperplane k-d tree structure, an adaptive hyperplane generation is presented. The vector quantization complexity is further lowered by a novel relative distance quantization rule. Misclassification problem associated with hyperplane decision is eliminated by a multilevel back-tracing algorithm. Triangular inequality is applied to lower bound the search distance, thus eliminated a large number of the sub-tree in the k-d search tree during back-tracing. The multinodes tree algorithm is modified to a novel multilinkage subspace tree clustering to limit the possible candidate codewords in the codebook to a small subset and thus achieves...[ Read more ]

Several optimal algorithms for M-clustering problem using hyperplane based k-d tree and subspace vector quantization are proposed. Based on the property of hyperplane k-d tree structure, an adaptive hyperplane generation is presented. The vector quantization complexity is further lowered by a novel relative distance quantization rule. Misclassification problem associated with hyperplane decision is eliminated by a multilevel back-tracing algorithm. Triangular inequality is applied to lower bound the search distance, thus eliminated a large number of the sub-tree in the k-d search tree during back-tracing. The multinodes tree algorithm is modified to a novel multilinkage subspace tree clustering to limit the possible candidate codewords in the codebook to a small subset and thus achieves reduction in computational complexity. An associated clustering algorithm, multiple exchange clustering, is proposed to cluster the input data efficiently. In order to further improve the clustering algorithm, the proposed algorithm optimizes the selection of data subspace for splitting and the generation of hyperplane that splits the data subspace. The performance of all proposed algorithms is evaluated by the total sum of squares error and the peak signal to noise ratio of the vector quantization image coding of real world images. The computational complexity of the algorithm is evaluated by the computation time and number of floating point operation. Simulation results showed that the proposed algorithms are efficient by reducing the total sum of squares error of the clustering results, and hence achieves better clusters. At the same time, lower computational complexity is achieved in searching the clusters.