Comparison of partial orders clustering techniques
https://doi.org/10.15514/ISPRAS-2014-26(4)-7
Abstract
In this paper, we compare three approaches of clustering partial ordered subsets of a set of items. First approach was k-medoids clustering algorithm with distance function based on Levenshtein distance. The second approach was k-means algorithm with cosine distance as distance function after vectorization of partial orders. And the third one was k-medoids algorithm with Kendall's tau as a distance function. We use Adjusted Rand Index as a measure of quality of clustering and find out that clustering with all three methods get stable results when variance of number of items ranked is high. Vectorization of partial orders get best results if number of items ranked is low.
References
1. A. Ukkonen. Clustering algorithms for chains. Journal of Machine Learning Research, 12:1389-1423, 2011.
2. L. Kaufman, P. Rousseeuw. Clustering by means of medoids. In Dodge, Y. (Ed.) Statistical Data Analysis based on the L1 Norm. Elsevier/North Holland, Amsterdam, 1987, pp. 405-416.
3. V.I. Levenshein. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady. Vol. 10, No. 8, 1966, pp. 707-710
4. T. Kamishima, J. Fujiki. Clustering orders. Proceedings of the 6th International Conference on Discovery Science, 2003, pp.194-207
5. M. Kendall, J.D. Gibbons. Rank Correlation Methods. A Charles Griffin Title, 1990. 272 p.
6. W.M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association. Vol. 66, No. 336, 1971, pp. 846-850
7. L. Hubert, A. Phipps. Comparing partitions. Journal of Classification. Vol. 2, No. 1, pp.193-218
Review
For citations:
Raskin A. Comparison of partial orders clustering techniques. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(4):91-98. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(4)-7
Email this article 