Abstract
Spectral clustering is the type of unsupervised learning that separates data based on their connectivity instead of convexity. However, its computational demands increase cubically with the number of points n. This triggered a stream of studies to ease these demands. An effective solution is to provide an approximated graph \( G^{*} = \left( {V^{*} ,E^{*} } \right) \) for the input data with a reduced set of vertices and edges. Recent similarity measures used to construct the approximated graph \( G^{*} = \left( {V^{*} ,E^{*} } \right) \) have some deficiencies such as: (1) weights on edges highly depend on the cluster density, and (2) larger memory footprint compared to conventional similarity measures. In this work, we employed topology preserving methods (e.g., neural gas) to obtain \( G^{*} = \left( {V^{*} ,E^{*} } \right) \) due to their ability to preserve input data topology. Then we used a conventional similarity measure to assign weights on the graph. The experiments reveal that graphs obtained through topology preserving methods and passed to a locally scaled similarity measure, produce performances comparable to the recent measures with a significantly smaller memory footprint.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Yan, D., Huang, L., Jordan, M.I.: Fast approximate spectral clustering. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 907–916 (2009)
Tasdemir, K.: Vector quantization based approximate spectral clustering of large datasets. Pattern Recogn. 45, 3034–3044 (2012)
Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems (2002)
Zelnik-Manor, L., Perona, P.: Self-tuning spectral clustering. In: Proceedings of the 17th International Conference on Neural Information Processing Systems, pp. 1601–1608 (2004)
Martinetz, T., Schulten, K.: Topology representing networks. Neural Netw. 7, 507–522 (1994)
Kohonen, T.: The self-organizing map. Proc. IEEE 78, 1464–1480 (1990)
Martinetz, T., Schulten, K.: A “Neural-Gas” Network Learns Topologies. University of Illinois at Urbana-Champaign, Champaign (1991)
Fritzke, B.: A growing neural gas network learns topologies. In: Advances in Neural Information Processing Systems, pp. 625–632 (1995)
Sugiyama, M.: Dimensionality reduction of multimodal labeled data by local fisher discriminant analysis. J. Mach. Learn. Res. 8, 1027–1061 (2007)
Zhang, X., Li, J., Yu, H.: Local density adaptive similarity measurement for spectral clustering. Pattern Recogn. Lett. 32, 352–358 (2011)
Martinetz, T.: Competitive hebbian learning rule forms perfectly topology preserving maps. In: Gielen, S., Kappen, B. (eds.) ICANN 1993, pp. 427–434. Springer, London (1993). https://doi.org/10.1007/978-1-4471-2063-6_104
Von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17, 395–416 (2007)
Arbelaez, P., Maire, M., Fowlkes, C., Malik, J.: Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 33, 898–916 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Alshammari, M., Takatsuka, M. (2018). Approximate Spectral Clustering Using Topology Preserving Methods and Local Scaling. In: Cheng, L., Leung, A., Ozawa, S. (eds) Neural Information Processing. ICONIP 2018. Lecture Notes in Computer Science(), vol 11304. Springer, Cham. https://doi.org/10.1007/978-3-030-04212-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-04212-7_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04211-0
Online ISBN: 978-3-030-04212-7
eBook Packages: Computer ScienceComputer Science (R0)