Spectral clustering versus Watanabe theorem

• Autorzy: Kłopotek, Mieczysław A.
• Języki publikacji: EN

Abstrakty

EN

We devote this paper to a special case of Graph Spectral Clustering of graphswith identical distances between nodes. This study is motivated by the special theorempresented by Watanabe which claims that given all derivable attributes are taken intoaccount, all distinct objects are at the same distance. As the multi-view clusteringbecomes popular, the mentioned Watanabe theorem may imply serious problems forrecovering the intrinsic structure of the collection of objects. We show that GraphSpectral Clustering should not be affected in the most favourable case that is blockstructure of similarity matrix in theory, but in practice the underlying𝑘-means algorithmintroduces up to 20% error rate in assignment of elements to clusters.

Słowa kluczowe

EN

Ugly Duckling Theorem; Graph Spectral Clustering; k-means clustering algorithm; Fiedler vector

• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2024
• Tom: vol. 1 (30)
• Strony: 21--34
• Opis fizyczny: Bibliogr. 37 poz., wykr.

Twórcy

autor

Kłopotek, Mieczysław A.

• Institute of Computer Science of Polish Academy of Sciences, ul. Jana Kazimierza 5, 01-248 Warszawa, Poland,

Bibliografia

• 1. Alshammari, M., Takatsuka,M.: Approximate spectral clustering with eigenvector selection and self-tuned k.Pattern Recognition Letters122, 31-37 (may2019). https://doi.org/10.1016/ j.patrec.2019.02.006
• 2. Bartlett, S.J.:The species problem and its logic: Inescapable ambiguity and framework-relativity (2015)
• 3. Blumson, B.:Does everything resemble everything else to the same degree (2022), National University of Singapore; https://ap5.fas.nus.edu.sg/fass/phibrkb/uglyduckling.pdf
• 4. Blumson, B.: The metaphysical significance of the ugly duckling theorem. In: Australian National University, School of Philosophy Lectures (2014), https://philosophy.cass.anu.edu.au/events/ ben-blumson-singapore-metaphysical-significance-ugly-duckling-theorem
• 5. Boedihardjo, M., Deng, S.,Strohmer,T.:A performance guarantee for spectral clustering(2020)
• 6. Borkowski, P., Kłopotek, M.A., Starosta,B., Wierzchoń,S.T., Sydow,M.: Eigenvalue based spectral classification. PloS ONE 18 (4) ,e0283413(2023).https://doi.org/https://doi.org/10.1371/journal.pone.0283413
• 7. Caruana, R., Elhawary, M.F., Nguyen, N.,Smith, C.: Metaclustering. In:Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006),18-22 December 2006, Hong Kong, China. pp.107-118. IEEE Computer Society(2006). https://doi.org/10.1109/ICDM.2006.103, https://doi.org/10.1109/ICDM.2006.103
• 8. Chao,G., Sun, S.,Bi, J.:A survey on multi-view clustering. IEEE Transactions on Artificial Intelligence2(2),146-168(2021)
• 9. Fisher, D.H.: Noise-tolerant conceptual clustering. In: Proceedings of the 11th International Joint Conference on Artificial Intelligence-Volume 1. p. 825-830. IJCAI’89, Morgan Kaufmann Publishers Inc.,San Francisco, CA, USA(1989)
• 10. Fujimoto, T., Ikuine, F.: Industrial Competitiveness and Design Evolution. Springer Tokyo(01 2018). https://doi.org/10.1007/978-4-431-55145-4
• 11. Hatakeyama-Sato, K. ,Watanabe, S., Yamane, N.,Igarashi, Y.,Oyaizu, K.:Using gpt-4-in parameter selection of materials informatics: Improving predictive accuracy amidst data scarcity and ’ugly duckling’ dilemma. Chem Rxiv. Cambridge: Cambridge Open Engage(2023)
• 12. Hong, X., Gao, J.,Wei, H., Xiao, J.,Mitchell, R.:Two-step scalable spectral clustering algorithm usinglandmarks and probability density estimation. Neurocomputing 519, 173-186 (2023). https: //doi.org/https://doi.org/10.1016/j.neucom.2022.11.063
• 13. Ilachinski,A.:Cellular Automata:A Discrete Universe. World Scientific, Singapore(2001)
• 14. Kamishima,T.,Akaho,S.:Considerations on recommendation independence for a find-good-items task. In:Proc. Fairness, Accountability and Transparency in Recommender Systems (082017). https://doi.org/10.18122/B2871W
• 15. Klopotek, M.A.:On the phenomenon of flattening "flexible prediction" concept hierarchy. In: Jorrand, P., Kelemen, J. (eds.) Fundamentals of Artificial Intelligence Research, International Workshop FAIR’91, Smolenice, Czechoslovakia, September8-13, 1991, Proceedings.Lecture Notes in Computer Science, vol.535,pp.99-111. Springer(1991). https://doi.org/10.1007/ 3-540-54507-7_9,https://doi.org/10.1007/3-540-54507-7_9
• 16. Klopotek, M.A.: On seeking consensus between document similarity measures. Fundam. Informaticae156(1), 43-68(2017). https://doi.org/10.3233/FI-2017-1597,https://doi.org/ 10.3233/FI-2017-1597
• 17. Klopotek, M.A., Matuszewski, A.: On irrelevance of attributes in flexible prediction. In: Proc. 2nd Int. Conf. on New Techniques and Technologies for Statistics (NTTS’95), vol. abs/2005.11979, pp. 282-293. GMD Sankt Augustin, Bonn, Germany(1995), https://arxiv.org/abs/2005.11979
• 18. Klus, S., Djurdjevac Conrad, N.: Koopman-based spectral clustering of directed and time evolving graphs. JNonlinearSci33(8)(2023).https://doi.org/https://doi.org/10.1007/ s00332-022-09863-0
• 19. Kłopotek, M.: Zależność funkcji oceny od współczynnika korelacji w metodzie formowania pojęć "flexible prediction". In: P. Sienkiewicz, J. Tchórzewski Eds.: Sztuczna Inteligencja i Cybernetyka Wiedzy(cybernetyka- inteligencja- rozwój, CIR’91), PTC, WSRPwSiedlcach,pp.37-42.Siedlce (1991)
• 20. Liang, W., Zhou, S., Xiong, J., Liu, X., Wang, S., Zhu, E., Cai, Z., Xu, X.: Multi-view spectral clustering with high-order optimal neighborhood laplacian matrix. CoRR abs/2008.13539 (2020), https://arxiv.org/abs/2008.13539
• 21. vonLuxburg,U.: Atutorial on spectral clustering. Statistics and Computing 17(4), 395-416 (2007). https://doi.org/https://doi.org/10.48550/arXiv.0711.0189
• 22. M.A.Kłopotek, S.T.Wierzchoń, K.Ciesielski, M.Dramiński, D.Czerski: Klasteryacja i metaklasteryzacja w świetle twierdzenia watanabe. In: Systemy Wspomagania Decyzji, pp. 83-97. Wydawnictwo Instytut Informatyki Uniwersytetu S‘la‘skiego (2012)
• 23. Ng,A.Y.,Jordan,M.I.,Weiss,Y.:On spectral clustering: Analysis and an algorithm.In: ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS. pp. 849-856. MIT Press(2001),http: //citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100
• 24. Peng, P., Yoshida, Y.: Average sensitivity of spectral clustering (2020)
• 25. Starosta, B., Kłopotek, M., Wierzchoń, S., Czerski, D.: Hashtag discernability- competitiveness study of graph spectral and other clustering methods. In: accepted for the 18th Conference on Computer Science and Intelligence Systems FedCSIS 2023 (IEEE #57573) Warsaw, Poland, 17-20 September, 2023 (2023)
• 26. Stone, J.V.: Vision and Brain: How We Perceive the World. MIT Press (2012)
• 27. Strehl, A., Ghosh, J.: Cluster ensembles - A knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res. 3, 583-617 (2002), http://jmlr.org/papers/v3/strehl02a. html
• 28. Towster, E.: Two ugly duckling theorems for concept-formers. Information Sciences 8(4), 359-368 (1975). https://doi.org/https://doi.org/10.1016/0020-0255(75)90047-X,https:// www.sciencedirect.com/science/article/pii/002002557590047X
• 29. Wang, H., Zong, L., Liu, B., Yang, Y., Zhou, W.: Spectral perturbation meets incomplete multi view data. In: Proc. of the 28-th Intl, Joint Conference on Artificial Intelligence (IJCAI-19). pp. 3677-3683 (2019)
• 30. Watanabe, S.: Theorem of the ugly duckling. In: Knowing and Guessing: A Quantitative Study of Inference and Information, pp. 376-377+. Wiley (1969)
• 31. Watanabe, S.: Pattern Recognition, Human and Mechanical. John-Willey and Sons, New York (1987)
• 32. Wen, J., Zhang, Z., Fei, L., Zhang, B., Xu, Y., Zhang, Z., Li, J.: A survey on incomplete multi view clustering. IEEE Transactions on Systems, Man, and Cybernetics: Systems (Early Access) (2022)
• 33. Wierzchon, S.T., Klopotek, M.A.: Spectral cluster maps versus spectral clustering. In: Computer Information Systems and Industrial Management. LNCS, vol. 12133, pp. 472-484. Springer (2020). https://doi.org/10.1007/978-3-030-47679-3_40, https://doi.org/ 10.1007/978-3-030-47679-3_40
• 34. Wierzchoń,S.,M.A.Kłopotek: Modern Clustering Algorithms, Studies in Big Data,vol.34.Springer Verlag (2018)
• 35. Xu, Y., Srinivasan, A., Xue, L.: A Selective Overview of Recent Advances in Spectral Clustering and Their Applications, pp. 247-277. Springer International Publishing, Cham (2021). https: //doi.org/10.1007/978-3-030-72437-5_12
• 36. Yang, Y., Wang, H.: Multi-view clustering: A survey. Big Data Mining and Analytics 1(2), 83-107(2018). https://doi.org/10.26599/BDMA.2018.9020003, https://www.sciopen.com/article/10.26599/BDMA.2018.9020003
• 37. Zhao,J.,Xie,X.,Xu,X.,Sun,S.:Multi-view learning overview: Recen tprogress and new challenges. Information Fusion 38, 41-54 (2017)

Identyfikatory

DOI

10.34739/si.2024.30.02