Based on a graph-theoretic concept of a cluster, dominant sets clustering has been shown to be an attractive clustering algorithm with many useful properties. In this study, the authors conduct a comprehensive study of related issues in dominant sets clustering, in an endeavour to explore the potential of this algorithm and obtain the best clustering results. Specifically, they empirically investigate how similarity parameters, similarity measures and game dynamics influence the dominant sets clustering results. From experiments on eight datasets, they conclude that distance-based similarity measures perform evidently better than cosine and histogram intersection similarity measures potentially, and they need to find the best-performing similarity parameter to make use of this advantage. They then study the effect of similarity parameter on dominant sets clustering results and induce the range of the best-performing similarity parameters. Furthermore, they find that the recently proposed infection and immunisation dynamics performs better than the replicator dynamics in most cases while being much more efficient than the latter. These observations are helpful in applying dominant sets clustering to practical problems, and also indicate directions for further improvement of this algorithm.

References

1. 1)
  - 4. Hou, J., Xu, E., Liu, W.X., Xia, Q., Qi, N.M.: ‘A density based enhancement to dominant sets clustering’, IET Comput. Vis., 2013, 7, (5), pp. 354–361 (doi: 10.1049/iet-cvi.2013.0072).
2. 2)
  - 7. Hamid, R., Maddi, S., Johnson, A.Y., Bobick, A.F., Essa, I.A., Isbell, C.: ‘A novel sequence representation for unsupervised analysis of human activities’, Artif. Intell., 2009, 173, (14), pp. 1221–1244 (doi: 10.1016/j.artint.2009.05.002).
3. 3)
  - 18. Hou, J., Zhang, B.P., Qi, N.M., Yang, Y.: ‘Evaluating feature combination in object classification’. Proc. Int. Symp. Visual Computing, 2011, pp. 597–606.
4. 4)
  - 11. Rota Bulo, S., Pelillo, M., Bomze, I.M.: ‘Graph-based quadratic optimization: a fast evolutionary approach’, Comput. Vis. Image Underst., 2011, 115, (7), pp. 984–995 (doi: 10.1016/j.cviu.2010.12.004).
5. 5)
  - 9. Hou, J., E, X., Chi, L., Xia, Q., Qi, N.M.: ‘Dominant sets and target clique extraction’. Proc. Int. Conf. Pattern Recognition, 2012, pp. 1831–1834.
6. 6)
  - 8. Hou, J., Pelillo, M.: ‘A simple feature combination method based on dominant sets’, Pattern Recognit., 2013, 46, (11), pp. 3129–3139 (doi: 10.1016/j.patcog.2013.04.005).
7. 7)
  - 3. Torsello, A., Rota Bulo, S., Pelillo, M.: ‘Beyond partitions: allowing overlapping groups in pairwise clustering’. Proc. Int. Conf. Pattern Recognition, 2008, pp. 1–4.
8. 8)
  - 14. Chang, H., Yeung, D.Y.: ‘Robust path-based spectral clustering’, Pattern Recognit., 2008, 41, (1), pp. 191–203 (doi: 10.1016/j.patcog.2007.04.010).
9. 9)
  - 22. Daszykowski, M., Walczak, B., Massart, D.L.: ‘Looking for natural patterns in data: part 1. Density-based approach’, Chemometr. Intell. Lab. Syst., 2001, 56, (2), pp. 83–92 (doi: 10.1016/S0169-7439(01)00111-3).
10. 10)
  - 10. Hou, J., E, X., Chi, L., Xia, Q., Qi, N.M.: ‘DSET++ : a robust clustering algorithm’. Proc. Int. Conf. Image Processing, 2013, pp. 3795–3799.
11. 11)
  - 12. Torsello, A., Rota Bulo, S., Pelillo, M.: ‘Grouping with asymmetric affinities: a game-theoretic perspective’. Proc. Int. Conf. Computer Vision and Pattern Recognition, 2006, pp. 292–299.
12. 12)
  - 5. Yang, X.W., Liu, H.R., Laecki, L.J.: ‘Contour-based object detection as dominant set computation’, Pattern Recognit., 2012, 45, (5), pp. 1927–1936 (doi: 10.1016/j.patcog.2011.11.010).
13. 13)
  - 23. Pavan, M., Pelillo, M.: ‘Dominant sets and pairwise clustering’, IEEE Trans. Patt. Anal. Mach. Intell., 2007, 29, pp. 167–172 (doi: 10.1109/TPAMI.2007.250608).
14. 14)
  - 13. Gionis, A., Mannila, H., Tsaparas, P.: ‘Clustering aggregation’, ACM Trans. Knowl. Discov. Data, 2007, 1, (1), pp. 1–30 (doi: 10.1145/1217299.1217303).
15. 15)
  - 6. Frommlet, F.: ‘Tag SNP selection based on clustering according to dominant sets found using replicator dynamics’, Adv. Data Anal. Classif., 2010, 4, (1), pp. 65–83 (doi: 10.1007/s11634-010-0059-2).
16. 16)
  - 20. Ester, M., Kriegel, H.P., Sander, J., Xu, X.W.: ‘A density-based algorithm for discovering clusters in large spatial databases with noise’. Proc. Int. Conf. Knowledge Discovery and Data Mining, 1996, pp. 226–231.
17. 17)
  - 1. Pavan, M., Pelillo, M.: ‘A graph-theoretic approach to clustering and segmentation’. Proc. Int. Conf. Computer Vision and Pattern Recognition, 2003, pp. 145–152.
18. 18)
  - 16. Fu, L., Medico, E.: ‘FLAME, a novel fuzzy clustering method for the analysis of DNA microarray data’, BMC Bioinf., 2007, 8, (1), pp. 1–17 (doi: 10.1186/1471-2105-8-3).
19. 19)
  - 19. Albarelli, A., Rota Bulo, S., Torsello, A., Pelillo, M.: ‘Matching as a non-cooperative game’. Proc. Int. Conf. Computer Vision, 2009, pp. 1319–1326.
20. 20)
  - 15. Jain, A.K., Law, M.H.C.: ‘Data clustering: a user's dilemma’. Proc. Int. Conf. Pattern Recognition and Machine Intelligence, 2005, pp. 1–10.
21. 21)
  - 17. Veenman, C.J., Reinders, M.J.T., Backer, E.: ‘A maximum variance cluster algorithm’, IEEE Trans. Pattern Anal. Mach. Intell., 2002, 24, (9), pp. 1273–1280 (doi: 10.1109/TPAMI.2002.1033218).
22. 22)
  - 21. Shi, J., Malik, J.: ‘Normalized cuts and image segmentation’, IEEE Trans. Pattern Anal. Mach. Intell., 2000, 22, (8), pp. 167–172.

Experimental study on dominant sets clustering

References

Related content