{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T17:10:16Z","timestamp":1718125816622},"reference-count":34,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2018,7,10]],"date-time":"2018-07-10T00:00:00Z","timestamp":1531180800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61703115","61673125"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Frontier and Key Technology Innovation Special Funds of Guangdong Province","award":["2016B090910003","2014B090919002"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"In kernel methods, Nystr\u00f6m approximation is a popular way of calculating out-of-sample extensions and can be further applied to large-scale data clustering and classification tasks. Given a new data point, Nystr\u00f6m employs its empirical affinity vector, k, for calculation. This vector is assumed to be a proper measurement of the similarity between the new point and the training set. In this paper, we suggest replacing the affinity vector by its projections on the leading eigenvectors learned from the training set, i.e., using k*=\u2211i=1ckTuiui instead, where ui is the i-th eigenvector of the training set and c is the number of eigenvectors used, which is typically equal to the number of classes designed by users. Our work is motivated by the constraints that in kernel space, the kernel-mapped new point should (a) also lie on the unit sphere defined by the Gaussian kernel and (b) generate training set affinity values close to k. These two constraints define a Quadratic Optimization Over a Sphere (QOOS) problem. In this paper, we prove that the projection on the leading eigenvectors, rather than the original affinity vector, is the solution to the QOOS problem. The experimental results show that the proposed replacement of k by k* slightly improves the performance of the Nystr\u00f6m approximation. Compared with other affinity matrix modification methods, our k* obtains comparable or higher clustering performance in terms of accuracy and Normalized Mutual Information (NMI).<\/jats:p>","DOI":"10.3390\/e20070519","type":"journal-article","created":{"date-parts":[[2018,7,10]],"date-time":"2018-07-10T13:24:01Z","timestamp":1531229041000},"page":"519","source":"Crossref","is-referenced-by-count":1,"title":["Projected Affinity Values for Nystr\u00f6m Spectral Clustering"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-0261-4068","authenticated-orcid":false,"given":"Li","family":"He","sequence":"first","affiliation":[{"name":"Department of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2463-4564","authenticated-orcid":false,"given":"Haifei","family":"Zhu","sequence":"additional","affiliation":[{"name":"Department of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China"}]},{"given":"Tao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China"}]},{"given":"Honghong","family":"Yang","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Edmonton, AB T6G 2R3, Canada"},{"name":"School of Automation, Northwestern Polytechnical University, Xi\u2019an 710072, China"}]},{"given":"Yisheng","family":"Guan","sequence":"additional","affiliation":[{"name":"Department of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China"}]}],"member":"1968","published-online":{"date-parts":[[2018,7,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"4339","DOI":"10.1109\/TSP.2015.2442958","article-title":"Phase Transitions in Spectral Community Detection","volume":"63","author":"Chen","year":"2015","journal-title":"IEEE Trans. Signal Proc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"17106","DOI":"10.1109\/ACCESS.2017.2740962","article-title":"Efficient Vector Influence Clustering Coefficient Based Directed Community Detection Method","volume":"5","author":"Deng","year":"2017","journal-title":"IEEE Access"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.patcog.2017.03.012","article-title":"Unsupervised hierarchical image segmentation through fuzzy entropy maximization","volume":"68","author":"Yin","year":"2017","journal-title":"Pattern Recognit."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/j.patcog.2015.10.019","article-title":"Iterative ensemble normalized cuts","volume":"52","author":"He","year":"2016","journal-title":"Pattern Recognit."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1356","DOI":"10.1109\/TIP.2015.2401516","article-title":"Integrated Foreground Segmentation and Boundary Matting for Live Videos","volume":"24","author":"Gong","year":"2015","journal-title":"IEEE Trans. Image Proc."},{"key":"ref_6","first-page":"5640","article-title":"Two-Stage Clustering Technique Based on the Neighboring Union Histogram for Hyperspectral Remote Sensing Images","volume":"5","author":"Yang","year":"2017","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1567","DOI":"10.3390\/e15051567","article-title":"Kernel Spectral Clustering for Big Data Networks","volume":"15","author":"Mall","year":"2013","journal-title":"Entropy"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1109\/TSP.2013.2295553","article-title":"Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds","volume":"62","author":"Dong","year":"2013","journal-title":"IEEE Trans. Signal Proc."},{"key":"ref_9","unstructured":"Williams, C., and Seeger, M. (2001, January 3\u20138). Using the Nystr\u00f6m method to speed up kernel machines. Proceedings of the 14th Annual Conference on Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Nie, F., Wang, X., Jordan, M.I., and Huang, H. (2016, January 12\u201317). The Constrained Laplacian Rank Algorithm for Graph-Based Clustering. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10302"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Nie, F., Wang, X., and Huang, H. (2014, January 24\u201327). Clustering and projected clustering with adaptive neighbours. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA.","DOI":"10.1145\/2623330.2623726"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.neucom.2016.12.085","article-title":"Fast Kernel Spectral Clustering","volume":"268","author":"Langone","year":"2017","journal-title":"Neurocomputing"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1109\/TPAMI.2008.292","article-title":"Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA","volume":"32","author":"Alzate","year":"2010","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Zhu, W., Nie, F., and Li, X. (2017, January 5\u20139). Fast Spectral Clustering with Efficient Large Graph Construction. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7952605"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Luo, D., Ding, C., Huang, H., and Nie, F. (2011, January 11\u201316). Consensus spectral clustering in near-linear time. Proceedings of the 2011 IEEE 27th International Conference Data Engineering (ICDE), Hannover, Germany.","DOI":"10.1109\/ICDE.2011.5767925"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Langone, R., Van Barel, M., and Suykens, J. (2016). Entropy-Based Incomplete Cholesky Decomposition for a Scalable Spectral Clustering Algorithm: Computational Studies and Sensitivity Analysis. Entropy, 18.","DOI":"10.3390\/e18050182"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2108","DOI":"10.1109\/TIP.2018.2796860","article-title":"Kernel K-Means Sampling for Nystrom Approximation","volume":"27","author":"He","year":"2018","journal-title":"IEEE Trans. Image Proc."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2765","DOI":"10.1109\/TPAMI.2013.57","article-title":"Sparse Subspace Clustering: Algorithm, Theory, and Applications","volume":"35","author":"Elhamifar","year":"2013","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Nasihatkon, B., and Hartley, R. (2011, January 20\u201325). Graph connectivity in sparse subspace clustering. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Colorado Springs, CO, USA.","DOI":"10.1109\/CVPR.2011.5995679"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Lu, C.Y., Min, H., Zhao, Z.Q., Zhu, L., Huang, D.S., and Yan, S. (2012, January 7\u201313). Robust and efficient subspace segmentation via least squares regression. Proceedings of the European Conference on Computer Vision, Florence, Italy.","DOI":"10.1007\/978-3-642-33786-4_26"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","article-title":"Nonlinear Dimensionality Reduction by Locally Linear Embedding","volume":"290","author":"Roweis","year":"2000","journal-title":"Science"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1137\/S1052623499356071","article-title":"Minimizing a quadratic over a sphere","volume":"12","author":"Hager","year":"2001","journal-title":"SIAM J. Optim."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0719026","article-title":"Newton\u2019s Method with a Model Trust Region Modification","volume":"19","author":"Sorensen","year":"1982","journal-title":"Siam J. Numer. Anal."},{"key":"ref_24","unstructured":"Dua, D., and Karra Taniskidou, E. (2018, July 10). UCI Machine Learning Repository. Available online: http:\/\/archive.ics.uci.edu\/ml\/datasets.html."},{"key":"ref_25","unstructured":"(2018, July 10). The Infinite MNIST Dataset. Available online: http:\/\/leon.bottou.org\/projects\/infimnist."},{"key":"ref_26","unstructured":"(2018, July 10). The EMNIST Dataset, Available online: https:\/\/www.nist.gov\/itl\/iad\/image-group\/emnist-dataset."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Cohen, G., Afshar, S., Tapson, J., and van Schaik, A. (2018, July 10). EMNIST: An Extension of MNIST to Handwritten Letters. Available online: https:\/\/arxiv.org\/abs\/1702.05373.","DOI":"10.1109\/IJCNN.2017.7966217"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Yan, J., and Pollefeys, M. (2006, January 7\u201313). A General Framework for Motion Segmentation: Independent, Articulated, Rigid, Non-rigid, Degenerate and Non-degenerate. Proceedings of the European Conference on Computer Vision, Graz, Austria.","DOI":"10.1007\/11744085_8"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Tron, R., and Vidal, R. (2007, January 17\u201322). A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, USA.","DOI":"10.1109\/CVPR.2007.382974"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1016\/j.neucom.2015.05.064","article-title":"Unsupervised neighbourhood component analysis for clustering","volume":"168","author":"Qin","year":"2015","journal-title":"Neurocomputing"},{"key":"ref_31","first-page":"583","article-title":"Cluster ensembles\u2014A knowledge reuse framework for combining multiple partitions","volume":"3","author":"Strehl","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"16904","DOI":"10.1109\/ACCESS.2017.2741221","article-title":"Generalized Pair-counting Similarity Measures for Clustering and Cluster Ensembles","volume":"5","author":"Zhang","year":"2017","journal-title":"IEEE Access"},{"key":"ref_33","unstructured":"Zelnik-Manor, L., and Perona, P. (2004, January 1). Self-Tuning Spectral Clustering. Proceedings of the Advances in Neural Information Processing Systems, Vancouver, BC, Canada."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Qian, Y., Gong, M., and Cheng, L. (2015, January 2\u20135). STOCS: An Efficient Self-Tuning Multiclass Classification Approach. Proceedings of the Canadian Conference on Artificial Intelligence, Halifax, NS, Canada.","DOI":"10.1007\/978-3-319-18356-5_26"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/7\/519\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T16:34:59Z","timestamp":1718123699000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/7\/519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,10]]},"references-count":34,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2018,7]]}},"alternative-id":["e20070519"],"URL":"https:\/\/doi.org\/10.3390\/e20070519","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,10]]}}}